Changeset 4924 in orxonox.OLD for orxonox/trunk/src/lib
- Timestamp:
- Jul 21, 2005, 4:46:41 PM (19 years ago)
- Location:
- orxonox/trunk/src/lib
- Files:
-
- 5 edited
-
collision_detection/cd_engine.cc (modified) (6 diffs)
-
collision_detection/cd_engine.h (modified) (2 diffs)
-
graphics/spatial_separation/quadtree.cc (modified) (7 diffs)
-
graphics/spatial_separation/quadtree.h (modified) (3 diffs)
-
graphics/spatial_separation/quadtree_node.cc (modified) (17 diffs)
Legend:
- Unmodified
- Added
- Removed
-
orxonox/trunk/src/lib/collision_detection/cd_engine.cc
r4923 r4924 71 71 72 72 73 73 /** 74 * this checks the collisions with the objects 75 */ 74 76 void CDEngine::checkCollisionObjects() 75 77 { … … 96 98 97 99 100 /** 101 * this checks the collisions with the ground 102 */ 98 103 void CDEngine::checkCollisionGround() 99 104 { … … 103 108 104 109 110 /** 111 * this draws the bounding volume tree 112 * @param depth until which depth to draw the tree 113 * @param drawMode mod which states how to draw it 114 */ 105 115 void CDEngine::drawBV(int depth, int drawMode) const 106 116 { … … 116 126 } 117 127 delete iterator; 118 //model->draw();119 128 } 120 129 121 130 122 123 124 131 /** 132 * some debug output on the class 133 */ 125 134 void CDEngine::debug() 126 135 { … … 133 142 } 134 143 144 145 /** 146 * this spawns a tree for debug purposes only 147 */ 135 148 void CDEngine::debugSpawnTree(int depth, sVec3D* vertices, int numVertices) 136 149 { … … 140 153 } 141 154 155 156 /** 157 * this draws the debug spawn tree 158 */ 142 159 void CDEngine::debugDraw(int depth, int drawMode) 143 160 { -
orxonox/trunk/src/lib/collision_detection/cd_engine.h
r4919 r4924 55 55 56 56 void debug(); 57 void debugSpawnTree(int depth, sVec3D* vertices, int numVertices); 58 void debugDraw(int depth, int drawMode); 57 59 58 60 59 private: … … 66 65 void checkCollisionObjects(); 67 66 void checkCollisionGround(); 67 68 void debugSpawnTree(int depth, sVec3D* vertices, int numVertices); 69 void debugDraw(int depth, int drawMode); 68 70 69 71 -
orxonox/trunk/src/lib/graphics/spatial_separation/quadtree.cc
r4923 r4924 9 9 any later version. 10 10 11 11 ### File Specific: 12 12 main-programmer: Patrick Boenzli 13 13 co-programmer: ... … … 19 19 20 20 #include "quadtree_node.h" 21 #include "vector.h" 22 21 23 #include "material.h" 22 #include "vector.h" 24 23 25 24 26 using namespace std; … … 27 29 /** 28 30 * standard constructor 29 @todo this constructor is not jet implemented - do it 30 */ 31 */ 31 32 Quadtree::Quadtree (modelInfo* pModelInfo, const int treeDepth) 32 33 { 33 34 35 34 this->setClassID(CL_QUADTREE, "Quadtree"); 35 this->pModelInfo = pModelInfo; 36 this->treeDepth = treeDepth; 36 37 37 38 39 40 41 42 43 44 45 46 47 38 /* initialize the materials for debug draw */ 39 this->materials = new Material*[4]; 40 for(int i = 0; i < 4; ++i) 41 { 42 materials[i] = new Material(); 43 materials[i]->setIllum(3); 44 } 45 materials[0]->setAmbient(0.0, 0.3, 0.0); 46 materials[1]->setAmbient(0.4, 0.0, 0.2); 47 materials[2]->setAmbient(1.0, 0.0, 0.0); 48 materials[3]->setAmbient(5.0, 3.0, 1.0); 48 49 49 50 50 /* build the tree */ 51 this->rootNode = new QuadtreeNode(this->pModelInfo, this, this->treeDepth); 51 52 52 53 54 55 56 57 printf("============================\n");58 this->rootNode->buildHashTable(this->nodes, index);59 }60 61 53 /* make an array with access to the leafs of the Quad-Tree */ 54 this->nodes = new QuadtreeNode*[(int)pow(4, treeDepth)]; 55 int* index = new int; *index = 0; 56 for(int i = 0; i < (int)pow(2, treeDepth); ++i) 57 { 58 this->rootNode->buildHashTable(this->nodes, index); 59 } 60 /* sort and revert the hash table to fit the right position */ 61 this->sortHashTable(this->nodes); 62 this->revertHashTable(this->nodes); 62 63 63 for(int i = 0; i < (int)pow(4, treeDepth); ++i) 64 { 65 printf("node %i, %f, %f \n", i, this->nodes[i]->getDimension()->getCenter()->x, this->nodes[i]->getDimension()->getCenter()->z); 66 } 67 68 this->quadLength = this->nodes[0]->getDimension()->getAxis() * 2.0f; 69 Rectangle* r = this->rootNode->getDimension(); 70 71 Vector* offset = new Vector(); 72 float xOff = r->getCenter()->x - r->getAxis(); 73 float yOff = r->getCenter()->z - r->getAxis(); 74 this->offset->x = xOff; 75 this->offset->z = yOff; 76 77 this->maxIndex = (int)pow(2, this->treeDepth); 64 /* define some important and often used variables */ 65 this->quadLength = this->nodes[0]->getDimension()->getAxis() * 2.0f; 66 Rectangle* r = this->rootNode->getDimension(); 67 Vector* offset = new Vector(); 68 float xOff = r->getCenter()->x - r->getAxis(); 69 float yOff = r->getCenter()->z - r->getAxis(); 70 this->offset->x = xOff; 71 this->offset->z = yOff; 72 this->maxIndex = (int)pow(2, this->treeDepth); 78 73 } 79 74 … … 81 76 /** 82 77 * standard deconstructor 83 84 */ 78 */ 85 79 Quadtree::~Quadtree () 86 80 { … … 93 87 94 88 /** 95 \briefthis function rotates the array and mirrors it in the middle96 \param nodes: the nodes to translate89 * this function rotates the array and mirrors it in the middle 90 * @param nodes: the nodes to translate 97 91 98 92 since the original matrix is counted from the right upper edge to the right lower one, we have to reorganize the elements … … 123 117 } 124 118 119 125 120 /** 126 \brief sorts the hash table using their positions 127 \param nodes the nodes to use 128 121 * sorts the hash table using their positions 122 * @param nodes the nodes to use 129 123 */ 130 124 void Quadtree::sortHashTable(QuadtreeNode** nodes) … … 158 152 159 153 /** 160 \briefmaps a position to a quadtree161 \param position the position so look for162 \return the quadtree154 * maps a position to a quadtree 155 * @param position the position so look for 156 * @return the quadtree 163 157 164 158 this function will return the quadtree that contains the position -
orxonox/trunk/src/lib/graphics/spatial_separation/quadtree.h
r4922 r4924 1 1 /*! 2 2 \file quadtree.h 3 3 * Definition of a spatial data separation using quadtree 4 4 5 */ 5 This is the top element of the quadtree framework. A Quadtree is build of QuadtreeNodes, which are again separated 6 into QuadtreeNodes until a certain depth is reached 7 */ 6 8 7 9 #ifndef _QUADTREE_H … … 20 22 class Quadtree : public BaseObject { 21 23 22 public:23 Quadtree(modelInfo* pModelInfo, const int treeDepth);24 virtual ~Quadtree();25 24 26 QuadtreeNode* getQuadtreeFromPosition(const Vector& position); 25 public: 26 Quadtree(modelInfo* pModelInfo, const int treeDepth); 27 virtual ~Quadtree(); 27 28 28 void drawTree() const; 29 inline Material* getMaterial(int indexNode) const { return this->materials[indexNode % 4]; } 29 QuadtreeNode* getQuadtreeFromPosition(const Vector& position); 30 31 void drawTree() const; 32 inline Material* getMaterial(int indexNode) const { return this->materials[indexNode % 4]; } 33 30 34 31 35 private: … … 33 37 void sortHashTable(QuadtreeNode** nodes); 34 38 35 private:36 QuadtreeNode* rootNode; //!< reference to the root node of the quadtree37 modelInfo* pModelInfo; //!< reference to the modelInfo of the object38 int treeDepth; //!< depth of the tree39 39 40 float quadLength; //!< length of the leaf quadtree nodes 41 Vector* offset; //!< vector to the left lower corner of the root quadtree node 42 int maxIndex; //!< maximal index for the nodes array 40 private: 41 QuadtreeNode* rootNode; //!< reference to the root node of the quadtree 42 QuadtreeNode** nodes; //!< reference to all quadtree nodes (only leafs of the quad tree) 43 modelInfo* pModelInfo; //!< reference to the modelInfo of the object 44 int treeDepth; //!< depth of the tree 43 45 44 Material** materials; //!< materials for debug drawing purposes 46 float quadLength; //!< length of the leaf quadtree nodes 47 Vector* offset; //!< vector to the left lower corner of the root quadtree node 48 int maxIndex; //!< maximal index for the nodes array 45 49 46 QuadtreeNode** nodes; //!< reference to all quadtree nodes (only leafs of the quad tree)50 Material** materials; //!< materials for debug drawing purposes 47 51 }; 48 52 -
orxonox/trunk/src/lib/graphics/spatial_separation/quadtree_node.cc
r4923 r4924 9 9 any later version. 10 10 11 11 ### File Specific: 12 12 main-programmer: Patrick Boenzli 13 13 co-programmer: ... … … 29 29 /** 30 30 * standard constructor 31 */31 */ 32 32 QuadtreeNode::QuadtreeNode (sTriangleExt** triangles, int numTriangles, 33 33 const float* pVertices, int numVertices, … … 36 36 ) 37 37 { 38 /* save all important variables localy */ 38 39 this->pTriangles = triangles; 39 40 this->numTriangles = numTriangles; 40 41 this->pVertices = pVertices; 41 42 this->numVertices = numVertices; 42 43 43 this->quadtree = quadtree; 44 44 this->parent = parent; 45 46 45 this->pDimension = rect; 47 46 this->treeDepth = treeDepth; … … 49 48 this->indexNode = index; 50 49 51 52 50 /* debug output */ 53 51 for( int i = 0; i < this->treeDepth; ++i) … … 69 67 QuadtreeNode::QuadtreeNode(modelInfo* pModelInfo, Quadtree* quadtree, const int maxDepth) 70 68 { 69 /* save all important variables localy */ 71 70 this->pModelInfo = pModelInfo; 72 71 this->quadtree = quadtree; 72 this->maxDepth = maxDepth; 73 73 74 74 /* create an array of triangle references */ … … 80 80 this->pTriangles[i] = &this->pModelInfo->pTriangles[i]; 81 81 82 this->treeDepth = 0;83 this->maxDepth = maxDepth;84 this->indexNode = 0;85 86 82 /* debug output */ 87 83 for( int i = 0; i < this->treeDepth; ++i) … … 89 85 PRINT(3)(" | +-| (Event) Building Node Nr. %i Depth: %i/%i, pointer: %p\n", this->indexNode, treeDepth, maxDepth, this); 90 86 87 /* set some important variables */ 88 this->treeDepth = 0; 89 this->indexNode = 0; 91 90 this->pDimension = this->getDimFromModel(); 91 92 92 this->init(); 93 93 } … … 101 101 this->setClassID(CL_QUADTREE_NODE, "QuadtreeNode"); 102 102 103 /* init the rest of the variables for both init types */ 103 104 this->offset = 0.0f; 104 105 this->nodeIter = -1; … … 114 115 this->nodes[i] = NULL; 115 116 117 /* now separate the nodes */ 116 118 if( this->treeDepth < this->maxDepth) 117 119 this->separateNode(); … … 137 139 138 140 /** 139 \briefthis functions builds up a hash table containing all leafs of the Quadtree in a sorted array140 \param nodeList the nodelist array to add them141 \param index the current index in the array141 * this functions builds up a hash table containing all leafs of the Quadtree in a sorted array 142 * @param nodeList the nodelist array to add them 143 * @param index the current index in the array 142 144 143 145 The algorithm used for this purpose is home-brown. its not to fast but and the nodes are not always in the right … … 166 168 * gives the signal to separate the model into a quadtree 167 169 * @param treeDepth the max depth, the steps to go if treeDept == 0 leaf reached 170 171 * @todo ATTENION: This function is currently not used and not implemented, but would be a nice addon 168 172 */ 169 173 void QuadtreeNode::separateNode(float minLength) … … 185 189 * gives the signal to separate the model into a quadtree 186 190 * @param treeDepth the max depth, the steps to go if treeDept == 0 leaf reached 187 */191 */ 188 192 void QuadtreeNode::separateNode() 189 193 { 194 /* separate the four regions into the four lists */ 190 195 tList<sTriangleExt*>* listA = new tList<sTriangleExt*>(); //!< triangle list of nodeA 191 196 tList<sTriangleExt*>* listB = new tList<sTriangleExt*>(); //!< triangle list of nodeB … … 197 202 rectCenter = this->pDimension->getCenter(); 198 203 for( int i = 0; i < this->numTriangles; ++i) 204 { 205 for( int j = 0; j < 3; ++j) 199 206 { 200 for( int j = 0; j < 3; ++j) 201 { 202 pVert = &this->pVertices[this->pTriangles[i]->indexToVertices[j]]; 203 if( pVert[0] > rectCenter->x + this->offset && pVert[2] > rectCenter->z + this->offset) 204 listA->add(&this->pTriangles[i]); 205 if( pVert[0] < rectCenter->x + this->offset && pVert[2] > rectCenter->z + this->offset) 206 listB->add(&this->pTriangles[i]); 207 if( pVert[0] < rectCenter->x + this->offset && pVert[2] < rectCenter->z + this->offset) 208 listC->add(&this->pTriangles[i]); 209 if( pVert[0] > rectCenter->x + this->offset && pVert[2] < rectCenter->z + this->offset) 210 listD->add(&this->pTriangles[i]); 211 } 207 pVert = &this->pVertices[this->pTriangles[i]->indexToVertices[j]]; 208 if( pVert[0] > rectCenter->x + this->offset && pVert[2] > rectCenter->z + this->offset) 209 listA->add(&this->pTriangles[i]); 210 if( pVert[0] < rectCenter->x + this->offset && pVert[2] > rectCenter->z + this->offset) 211 listB->add(&this->pTriangles[i]); 212 if( pVert[0] < rectCenter->x + this->offset && pVert[2] < rectCenter->z + this->offset) 213 listC->add(&this->pTriangles[i]); 214 if( pVert[0] > rectCenter->x + this->offset && pVert[2] < rectCenter->z + this->offset) 215 listD->add(&this->pTriangles[i]); 212 216 } 213 for( int i = 0; i < treeDepth; ++i) 214 PRINT(3)(" |"); 215 PRINT(3)(" | +-| (II) Quadtree Counts - separating: A: %i, B: %i, C: %i, D: %i\n", listA->getSize(), listB->getSize(), listC->getSize(), listD->getSize()); 216 217 /* Separating into to the triangle lists */ 217 } 218 for( int i = 0; i < treeDepth; ++i) 219 PRINT(3)(" |"); 220 PRINT(3)(" | +-| (II) Quadtree Counts - separating: A: %i, B: %i, C: %i, D: %i\n", listA->getSize(), listB->getSize(), listC->getSize(), listD->getSize()); 221 222 223 /* Separating into to the triangle arrays */ 218 224 sTriangleExt** pTriA; //!< Triangle array A 219 225 sTriangleExt** pTriB; //!< Triangle array B … … 238 244 pTriD = new sTriangleExt*[listD->getSize()]; 239 245 240 241 246 counter = 0; 242 247 iterator = listA->getIterator(); 243 248 tempTri = iterator->nextElement(); 244 249 while( tempTri) 245 { 246 pTriA[counter] = *tempTri; 247 tempTri = iterator->nextElement(); 248 ++counter; 249 } 250 250 { 251 pTriA[counter] = *tempTri; 252 tempTri = iterator->nextElement(); 253 ++counter; 254 } 251 255 counter = 0; 252 256 iterator = listB->getIterator(); 253 257 tempTri = iterator->nextElement(); 254 258 while( tempTri) 255 { 256 pTriB[counter] = *tempTri; 257 tempTri = iterator->nextElement(); 258 ++counter; 259 } 260 259 { 260 pTriB[counter] = *tempTri; 261 tempTri = iterator->nextElement(); 262 ++counter; 263 } 261 264 counter = 0; 262 265 iterator = listC->getIterator(); 263 266 tempTri = iterator->nextElement(); 264 267 while( tempTri) 265 { 266 pTriC[counter] = *tempTri; 267 tempTri = iterator->nextElement(); 268 ++counter; 269 } 270 268 { 269 pTriC[counter] = *tempTri; 270 tempTri = iterator->nextElement(); 271 ++counter; 272 } 271 273 counter = 0; 272 274 iterator = listD->getIterator(); 273 275 tempTri = iterator->nextElement(); 274 276 while( tempTri) 275 276 277 278 279 277 { 278 pTriD[counter] = *tempTri; 279 tempTri = iterator->nextElement(); 280 ++counter; 281 } 280 282 281 283 /* now do cleanup */ … … 288 290 289 291 /* now create the rectangle dimensions */ 290 Vector v; 292 Vector v; //!< temp saving place 293 Rectangle* rA; //!< new size of the node A 294 Rectangle* rB; //!< new size of the node B 295 Rectangle* rC; //!< new size of the node C 296 Rectangle* rD; //!< new size of the node D 297 291 298 292 299 v.x = this->pDimension->getCenter()->x + this->pDimension->getAxis() / 2.0f; 293 300 v.y = 0.0; 294 301 v.z = this->pDimension->getCenter()->z + this->pDimension->getAxis() / 2.0f; 295 Rectangle* rA = new Rectangle(v, this->pDimension->getAxis() / 2.0f); 296 302 rA = new Rectangle(v, this->pDimension->getAxis() / 2.0f); 297 303 v.z = this->pDimension->getCenter()->z - this->pDimension->getAxis() / 2.0f; 298 Rectangle* rB = new Rectangle(v, this->pDimension->getAxis() / 2.0f); 299 304 rB = new Rectangle(v, this->pDimension->getAxis() / 2.0f); 300 305 v.x = this->pDimension->getCenter()->x - this->pDimension->getAxis() / 2.0f; 301 Rectangle* rC = new Rectangle(v, this->pDimension->getAxis() / 2.0f); 302 306 rC = new Rectangle(v, this->pDimension->getAxis() / 2.0f); 303 307 v.z = this->pDimension->getCenter()->z + this->pDimension->getAxis() / 2.0f; 304 Rectangle*rD = new Rectangle(v, this->pDimension->getAxis() / 2.0f);305 306 /* now propagate*/308 rD = new Rectangle(v, this->pDimension->getAxis() / 2.0f); 309 310 /* now create the new nodes */ 307 311 this->nodeA = new QuadtreeNode(pTriA, lenA, this->pVertices, this->numVertices, this->quadtree, this, rA, this->treeDepth + 1, this->maxDepth, (this->treeDepth + 1) * 10 + 0); 308 309 312 this->nodeB = new QuadtreeNode(pTriB, lenB, this->pVertices, this->numVertices, this->quadtree, this, rB, this->treeDepth + 1, this->maxDepth, (this->treeDepth + 1) * 10 + 1); 310 311 313 this->nodeC = new QuadtreeNode(pTriC, lenC, this->pVertices, this->numVertices, this->quadtree, this, rC, this->treeDepth + 1, this->maxDepth, (this->treeDepth + 1) * 10 + 2); 312 313 314 this->nodeD = new QuadtreeNode(pTriD, lenD, this->pVertices, this->numVertices, this->quadtree, this, rD, this->treeDepth + 1, this->maxDepth, (this->treeDepth + 1) * 10 + 3); 315 314 316 /* map the array references, this is for faster and automatical interfacing \todo: use only array */ 315 317 this->nodes[0] = this->nodeA; … … 321 323 322 324 /** 323 \briefgets the maximal dimension of a model324 \return the dimension of the AbstractModel as a Rectangle325 * gets the maximal dimension of a model 326 * @return the dimension of the AbstractModel as a Rectangle 325 327 326 328 The rectangle is x-z axis aligned. ATTENTION: if there are any vertices in the model, that exceed the … … 368 370 369 371 /** 370 371 372 372 * checks if a point is included in this quadtree 373 * @param v the vector to be checked 374 * @returns true if the vector is included 373 375 */ 374 376 bool QuadtreeNode::includesPoint(const Vector& v)
Note: See TracChangeset
for help on using the changeset viewer.
