~ubuntu-branches/debian/sid/ember/sid

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

* OPCODE - Optimized Collision Detection

* Homepage: http://www.codercorner.com/Opcode.htm

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

/**

* Contains code for a versatile AABB tree.

* \file OPC_AABBTree.h

* \author Pierre Terdiman

* \date March, 20, 2001

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Include Guard

#ifndef __OPC_AABBTREE_H__

#define __OPC_AABBTREE_H__

#ifdef OPC_NO_NEG_VANILLA_TREE

//! TO BE DOCUMENTED

#define IMPLEMENT_TREE(base_class, volume) \

public: \

/* Constructor / Destructor */ \

base_class(); \

~base_class(); \

/* Data access */ \

inline_ const volume* Get##volume() const { return &mBV; } \

/* Clear the last bit */ \

inline_ const base_class* GetPos() const { return (const base_class*)(mPos&~1); } \

inline_ const base_class* GetNeg() const { const base_class* P = GetPos(); return P ? P+1 : null;} \

/* We don't need to test both nodes since we can't have one without the other */ \

inline_ bool IsLeaf() const { return !GetPos(); } \

/* Stats */ \

inline_ udword GetNodeSize() const { return sizeof(*this); } \

protected: \

/* Tree-independent data */ \

/* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/ \

/* Whatever happens we need the two children and the enclosing volume.*/ \

volume mBV; /* Global bounding-volume enclosing all the node-related primitives */ \

size_t mPos; /* "Positive" & "Negative" children */

#else

//! TO BE DOCUMENTED

#define IMPLEMENT_TREE(base_class, volume) \

public: \

/* Constructor / Destructor */ \

base_class(); \

~base_class(); \

/* Data access */ \

inline_ const volume* Get##volume() const { return &mBV; } \

/* Clear the last bit */ \

inline_ const base_class* GetPos() const { return (const base_class*)(mPos&~1); } \

inline_ const base_class* GetNeg() const { return (const base_class*)(mNeg&~1); } \

/* inline_ bool IsLeaf() const { return (!GetPos() && !GetNeg()); } */ \

/* We don't need to test both nodes since we can't have one without the other */ \

inline_ bool IsLeaf() const { return !GetPos(); } \

/* Stats */ \

inline_ udword GetNodeSize() const { return sizeof(*this); } \

protected: \

/* Tree-independent data */ \

/* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/ \

/* Whatever happens we need the two children and the enclosing volume.*/ \

volume mBV; /* Global bounding-volume enclosing all the node-related primitives */ \

size_t mPos; /* "Positive" child */ \

size_t mNeg; /* "Negative" child */

#endif

typedef void (*CullingCallback) (udword nb_primitives, udword* node_primitives, BOOL need_clipping, void* user_data);

class AABBTreeNode

{

// IMPLEMENT_TREE(AABBTreeNode, IceMaths::AABB)

public:

/* Constructor / Destructor */

AABBTreeNode();

~AABBTreeNode();

/* Data access */

inline_ const IceMaths::AABB* GetAABB() const { return &mBV; }

/* Clear the last bit */

inline_ const AABBTreeNode* GetPos() const { return (const AABBTreeNode*)(mPos&~1); }

inline_ const AABBTreeNode* GetNeg() const { const AABBTreeNode* P = GetPos(); return P ? P+1 : null;}

/* We don't need to test both nodes since we can't have one without the other */

inline_ bool IsLeaf() const { return !GetPos(); }

/* Stats */

inline_ udword GetNodeSize() const { return sizeof(*this); }

protected:

/* Tree-independent data */

/* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/

/* Whatever happens we need the two children and the enclosing volume.*/

IceMaths::AABB mBV; /* Global bounding-volume enclosing all the node-related primitives */

100

size_t mPos; /* "Positive" & "Negative" children */

101

public:

102

// Data access

103

inline_ const udword* GetPrimitives() const { return mNodePrimitives; }

104

inline_ udword GetNbPrimitives() const { return mNbPrimitives; }

105

106

protected:

107

// Tree-dependent data

108

udword* mNodePrimitives; //!< Node-related primitives (shortcut to a position in mIndices below)

109

udword mNbPrimitives; //!< Number of primitives for this node

110

// Internal methods

111

udword Split(udword axis, AABBTreeBuilder* builder);

112

bool Subdivide(AABBTreeBuilder* builder);

113

void _BuildHierarchy(AABBTreeBuilder* builder);

114

void _Refit(AABBTreeBuilder* builder);

115

};

116

117

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

118

/**

119

* User-callback, called for each node by the walking code.

120

* \param current [in] current node

121

* \param depth [in] current node's depth

122

* \param user_data [in] user-defined data

123

* \return true to recurse through children, else false to bypass them

124

125

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

126

typedef bool (*WalkingCallback) (const AABBTreeNode* current, udword depth, void* user_data);

127

128

class AABBTree : public AABBTreeNode

129

{

130

public:

131

// Constructor / Destructor

132

AABBTree();

133

~AABBTree();

134

// Build

135

bool Build(AABBTreeBuilder* builder);

136

void Release();

137

138

// Data access

139

inline_ const udword* GetIndices() const { return mIndices; } //!< Catch the indices

140

inline_ udword GetNbNodes() const { return mTotalNbNodes; } //!< Catch the number of nodes

141

142

// Infos

143

bool IsComplete() const;

144

// Stats

145

udword ComputeDepth() const;

146

udword GetUsedBytes() const;

147

udword Walk(WalkingCallback callback, void* user_data) const;

148

149

bool Refit(AABBTreeBuilder* builder);

150

bool Refit2(AABBTreeBuilder* builder);

151

private:

152

udword* mIndices; //!< Indices in the app list. Indices are reorganized during build (permutation).

153

AABBTreeNode* mPool; //!< Linear pool of nodes for complete trees. Null otherwise. [Opcode 1.3]

154

// Stats

155

udword mTotalNbNodes; //!< Number of nodes in the tree.

156

};

157

158

#endif // __OPC_AABBTREE_H__

Older »