OPC_OptimizedTree.cpp File Reference

#include "Stdafx.h"

Go to the source code of this file.

Macros
#define	FIND_MAX_VALUES
#define	INIT_QUANTIZATION
#define	PERFORM_QUANTIZATION
#define	REMAP_DATA(member)

Functions
static void	_BuildCollisionTree (AABBCollisionNode *linear, const udword box_id, udword &current_id, const AABBTreeNode *current_node)
static void	_BuildNoLeafTree (AABBNoLeafNode *linear, const udword box_id, udword &current_id, const AABBTreeNode *current_node)
inline_ void	OPComputeMinMax (Point &min, Point &max, const VertexPointers &vp)

Variables
static bool	gFixQuantized = true

Detailed Description

Contains code for optimized trees. Implements 4 trees:

• normal
• no leaf
• quantized
• no leaf / quantized

Author

Pierre Terdiman

Date

March, 20, 2001

Definition in file OPC_OptimizedTree.cpp.

Macro Definition Documentation

#define FIND_MAX_VALUES

Value:

/* Get max values */                                                                        \
	Point CMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);                                               \
	Point EMax(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);                                               \
    for(i=0;i<mNbNodes;i++)                                                             \
    {                                                                                           \
        if(fabsf(Nodes[i].mAABB.mCenter.x)>CMax.x)  CMax.x = fabsf(Nodes[i].mAABB.mCenter.x);   \
        if(fabsf(Nodes[i].mAABB.mCenter.y)>CMax.y)  CMax.y = fabsf(Nodes[i].mAABB.mCenter.y);   \
        if(fabsf(Nodes[i].mAABB.mCenter.z)>CMax.z)  CMax.z = fabsf(Nodes[i].mAABB.mCenter.z);   \
        if(fabsf(Nodes[i].mAABB.mExtents.x)>EMax.x) EMax.x = fabsf(Nodes[i].mAABB.mExtents.x);  \
        if(fabsf(Nodes[i].mAABB.mExtents.y)>EMax.y) EMax.y = fabsf(Nodes[i].mAABB.mExtents.y);  \
        if(fabsf(Nodes[i].mAABB.mExtents.z)>EMax.z) EMax.z = fabsf(Nodes[i].mAABB.mExtents.z);  \
    }

Definition at line 479 of file OPC_OptimizedTree.cpp.

#define INIT_QUANTIZATION

Value:

udword nbc=15;  /* Keep one bit for sign */                             \
	udword nbe=15; /* Keep one bit for fix */                              \
    if(!gFixQuantized) nbe++;                                               \
                                                                            \
    /* Compute quantization coeffs */                                       \
    Point CQuantCoeff, EQuantCoeff;                                         \
    CQuantCoeff.x = CMax.x!=0.0f ? float((1<<nbc)-1)/CMax.x : 0.0f;         \
    CQuantCoeff.y = CMax.y!=0.0f ? float((1<<nbc)-1)/CMax.y : 0.0f;         \
    CQuantCoeff.z = CMax.z!=0.0f ? float((1<<nbc)-1)/CMax.z : 0.0f;         \
    EQuantCoeff.x = EMax.x!=0.0f ? float((1<<nbe)-1)/EMax.x : 0.0f;         \
    EQuantCoeff.y = EMax.y!=0.0f ? float((1<<nbe)-1)/EMax.y : 0.0f;         \
    EQuantCoeff.z = EMax.z!=0.0f ? float((1<<nbe)-1)/EMax.z : 0.0f;         \
    /* Compute and save dequantization coeffs */                            \
    mCenterCoeff.x = CQuantCoeff.x!=0.0f ? 1.0f / CQuantCoeff.x : 0.0f;     \
    mCenterCoeff.y = CQuantCoeff.y!=0.0f ? 1.0f / CQuantCoeff.y : 0.0f;     \
    mCenterCoeff.z = CQuantCoeff.z!=0.0f ? 1.0f / CQuantCoeff.z : 0.0f;     \
    mExtentsCoeff.x = EQuantCoeff.x!=0.0f ? 1.0f / EQuantCoeff.x : 0.0f;    \
    mExtentsCoeff.y = EQuantCoeff.y!=0.0f ? 1.0f / EQuantCoeff.y : 0.0f;    \
    mExtentsCoeff.z = EQuantCoeff.z!=0.0f ? 1.0f / EQuantCoeff.z : 0.0f;    \

Definition at line 493 of file OPC_OptimizedTree.cpp.

#define PERFORM_QUANTIZATION

Definition at line 514 of file OPC_OptimizedTree.cpp.

#define REMAP_DATA

(

member)

Value:

/* Fix data */                                  \
    Data = Nodes[i].member;                             \
    if(!(Data&1))                                   \
    {                                       \
        /* Compute box number */                        \
		udword Nb = (Data - uintptr_t(Nodes))/Nodes[i].GetNodeSize(); \
        Data = uintptr_t(&mNodes[Nb]);                      \
    }                                       \
    /* ...remapped */                               \
    mNodes[i].member = Data;

Definition at line 556 of file OPC_OptimizedTree.cpp.

Function Documentation

static void _BuildCollisionTree ( AABBCollisionNode *  linear, const udword  box_id, udword &  current_id, const AABBTreeNode *  current_node  )

static

Definition at line 101 of file OPC_OptimizedTree.cpp.

{
    // Current node from input tree is "current_node". Must be flattened into "linear[boxid]".

    // Store the AABB
    current_node->GetAABB()->GetCenter(linear[box_id].mAABB.mCenter);
    current_node->GetAABB()->GetExtents(linear[box_id].mAABB.mExtents);
    // Store remaining info
    if(current_node->IsLeaf())
    {
        // The input tree must be complete => i.e. one primitive/leaf
        OPASSERT(current_node->GetNbPrimitives()==1);
        // Get the primitive index from the input tree
        udword PrimitiveIndex = current_node->GetPrimitives()[0];
        // Setup box data as the primitive index, marked as leaf
        linear[box_id].mData = (PrimitiveIndex<<1)|1;
    }
    else
    {
        // To make the negative one implicit, we must store P and N in successive order
        udword PosID = current_id++;    // Get a new id for positive child
        udword NegID = current_id++;    // Get a new id for negative child
        // Setup box data as the forthcoming new P pointer
        linear[box_id].mData = (uintptr_t)&linear[PosID];
        // Make sure it's not marked as leaf
        OPASSERT(!(linear[box_id].mData&1));
        // Recurse with new IDs
        _BuildCollisionTree(linear, PosID, current_id, current_node->GetPos());
        _BuildCollisionTree(linear, NegID, current_id, current_node->GetNeg());
    }
}

static void _BuildNoLeafTree ( AABBNoLeafNode *  linear, const udword  box_id, udword &  current_id, const AABBTreeNode *  current_node  )

static

Definition at line 152 of file OPC_OptimizedTree.cpp.

{
    const AABBTreeNode* P = current_node->GetPos();
    const AABBTreeNode* N = current_node->GetNeg();
    // Leaf nodes here?!
    OPASSERT(P);
    OPASSERT(N);
    // Internal node => keep the box
    current_node->GetAABB()->GetCenter(linear[box_id].mAABB.mCenter);
    current_node->GetAABB()->GetExtents(linear[box_id].mAABB.mExtents);

    if(P->IsLeaf())
    {
        // The input tree must be complete => i.e. one primitive/leaf
        OPASSERT(P->GetNbPrimitives()==1);
        // Get the primitive index from the input tree
        udword PrimitiveIndex = P->GetPrimitives()[0];
        // Setup prev box data as the primitive index, marked as leaf
        linear[box_id].mPosData = (PrimitiveIndex<<1)|1;
    }
    else
    {
        // Get a new id for positive child
        udword PosID = current_id++;
        // Setup box data
        linear[box_id].mPosData = (uintptr_t)&linear[PosID];
        // Make sure it's not marked as leaf
        OPASSERT(!(linear[box_id].mPosData&1));
        // Recurse
        _BuildNoLeafTree(linear, PosID, current_id, P);
    }

    if(N->IsLeaf())
    {
        // The input tree must be complete => i.e. one primitive/leaf
        OPASSERT(N->GetNbPrimitives()==1);
        // Get the primitive index from the input tree
        udword PrimitiveIndex = N->GetPrimitives()[0];
        // Setup prev box data as the primitive index, marked as leaf
        linear[box_id].mNegData = (PrimitiveIndex<<1)|1;
    }
    else
    {
        // Get a new id for negative child
        udword NegID = current_id++;
        // Setup box data
        linear[box_id].mNegData = (uintptr_t)&linear[NegID];
        // Make sure it's not marked as leaf
        OPASSERT(!(linear[box_id].mNegData&1));
        // Recurse
        _BuildNoLeafTree(linear, NegID, current_id, N);
    }
}

inline_ void OPComputeMinMax	(	Point &	min,
		Point &	max,
		const VertexPointers &	vp
	)

Definition at line 353 of file OPC_OptimizedTree.cpp.

References Opcode::Point::Max(), Opcode::Point::Min(), Opcode::VertexPointers::Vertex, Opcode::Point::x, Opcode::Point::y, and Opcode::Point::z.

{
    // Compute triangle's AABB = a leaf box
#ifdef OPC_USE_FCOMI    // a 15% speedup on my machine, not much
    min.x = FCMin3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);
    max.x = FCMax3(vp.Vertex[0]->x, vp.Vertex[1]->x, vp.Vertex[2]->x);

    min.y = FCMin3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);
    max.y = FCMax3(vp.Vertex[0]->y, vp.Vertex[1]->y, vp.Vertex[2]->y);

    min.z = FCMin3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
    max.z = FCMax3(vp.Vertex[0]->z, vp.Vertex[1]->z, vp.Vertex[2]->z);
#else
    min = *vp.Vertex[0];
    max = *vp.Vertex[0];
    min.Min(*vp.Vertex[1]);
    max.Max(*vp.Vertex[1]);
    min.Min(*vp.Vertex[2]);
    max.Max(*vp.Vertex[2]);
#endif
}

Variable Documentation

bool gFixQuantized = true

static

Compilation flag:

• true to fix quantized boxes (i.e. make sure they enclose the original ones)
• false to see the effects of quantization errors (faster, but wrong results in some cases)

Definition at line 78 of file OPC_OptimizedTree.cpp.