[4805] | 1 | /* |
---|
| 2 | orxonox - the future of 3D-vertical-scrollers |
---|
| 3 | |
---|
| 4 | Copyright (C) 2004 orx |
---|
| 5 | |
---|
| 6 | This program is free software; you can redistribute it and/or modify |
---|
| 7 | it under the terms of the GNU General Public License as published by |
---|
| 8 | the Free Software Foundation; either version 2, or (at your option) |
---|
| 9 | any later version. |
---|
| 10 | |
---|
| 11 | ### File Specific: |
---|
| 12 | main-programmer: Patrick Boenzli |
---|
| 13 | co-programmer: ... |
---|
| 14 | */ |
---|
| 15 | |
---|
[4808] | 16 | #define DEBUG_SPECIAL_MODULE DEBUG_MODULE_SPATIAL_SEPARATION |
---|
[4805] | 17 | |
---|
| 18 | #include "quadtree_node.h" |
---|
[4851] | 19 | #include "list.h" |
---|
| 20 | #include "vector.h" |
---|
[4805] | 21 | |
---|
| 22 | using namespace std; |
---|
| 23 | |
---|
| 24 | |
---|
| 25 | /** |
---|
[4836] | 26 | * standard constructor |
---|
[4805] | 27 | */ |
---|
[4813] | 28 | QuadtreeNode::QuadtreeNode (sTriangleExt* triangles, int numTriangles, Quadtree* quadtree) |
---|
[4805] | 29 | { |
---|
[4852] | 30 | this->init(); |
---|
[4805] | 31 | } |
---|
| 32 | |
---|
| 33 | |
---|
| 34 | /** |
---|
[4845] | 35 | * standard constructor |
---|
| 36 | */ |
---|
| 37 | QuadtreeNode::QuadtreeNode(modelInfo* pModelInfo) |
---|
| 38 | { |
---|
| 39 | this->pModelInfo = pModelInfo; |
---|
[4851] | 40 | |
---|
| 41 | /* create an array of triangle references */ |
---|
| 42 | this->pTriangles = new sTriangleExt*[this->pModelInfo->numTriangles]; |
---|
| 43 | this->numTriangles = this->pModelInfo->numTriangles; |
---|
| 44 | this->pVertices = this->pModelInfo->pVertices; |
---|
| 45 | for( int i = 0; i < this->pModelInfo->numTriangles; ++i) |
---|
| 46 | this->pTriangles[i] = &this->pModelInfo->pTriangles[i]; |
---|
[4852] | 47 | |
---|
| 48 | this->init(); |
---|
[4845] | 49 | } |
---|
| 50 | |
---|
[4852] | 51 | |
---|
| 52 | /** |
---|
| 53 | * takes the rest of the initialisation process |
---|
| 54 | */ |
---|
| 55 | void QuadtreeNode::init() |
---|
| 56 | { |
---|
| 57 | this->setClassID(CL_QUADTREE_NODE, "QuadtreeNode"); |
---|
| 58 | |
---|
| 59 | this->offset = 0.0f; |
---|
| 60 | } |
---|
| 61 | |
---|
[4851] | 62 | |
---|
[4845] | 63 | /** |
---|
[4836] | 64 | * standard deconstructor |
---|
[4852] | 65 | */ |
---|
[4805] | 66 | QuadtreeNode::~QuadtreeNode () |
---|
| 67 | { |
---|
| 68 | } |
---|
[4812] | 69 | |
---|
| 70 | |
---|
| 71 | /** |
---|
[4836] | 72 | * gives the signal to separate the model into a quadtree |
---|
| 73 | * @param treeDepth the max depth, the steps to go if treeDept == 0 leaf reached |
---|
[4812] | 74 | */ |
---|
[4819] | 75 | void QuadtreeNode::separateNode(int treeDepth) |
---|
[4852] | 76 | { |
---|
| 77 | this->separateNode(); |
---|
| 78 | } |
---|
[4812] | 79 | |
---|
| 80 | |
---|
| 81 | /** |
---|
[4836] | 82 | * gives the signal to separate the model into a quadtree |
---|
| 83 | * @param treeDepth the max depth, the steps to go if treeDept == 0 leaf reached |
---|
[4819] | 84 | */ |
---|
| 85 | void QuadtreeNode::separateNode(float minLength) |
---|
[4852] | 86 | { |
---|
| 87 | this->separateNode(); |
---|
| 88 | } |
---|
[4819] | 89 | |
---|
| 90 | |
---|
| 91 | /** |
---|
[4851] | 92 | * gives the signal to separate the model into a quadtree |
---|
| 93 | * @param treeDepth the max depth, the steps to go if treeDept == 0 leaf reached |
---|
| 94 | */ |
---|
| 95 | void QuadtreeNode::separateNode() |
---|
| 96 | { |
---|
[4852] | 97 | PRINTF(0)("got command to separate node\n"); |
---|
[4853] | 98 | |
---|
| 99 | this->pDimension = this->getDimension(this->pModelInfo); |
---|
| 100 | |
---|
[4851] | 101 | tList<sTriangleExt*>* listA = new tList<sTriangleExt*>(); //!< triangle list of nodeA |
---|
| 102 | tList<sTriangleExt*>* listB = new tList<sTriangleExt*>(); //!< triangle list of nodeB |
---|
| 103 | tList<sTriangleExt*>* listC = new tList<sTriangleExt*>(); //!< triangle list of nodeC |
---|
| 104 | tList<sTriangleExt*>* listD = new tList<sTriangleExt*>(); //!< triangle list of nodeD |
---|
| 105 | const float* pVert; //!< pointer to the vertices |
---|
| 106 | const Vector* rectCenter; //!< vector to the center of the rect |
---|
| 107 | |
---|
| 108 | rectCenter = this->pDimension->getCenter(); |
---|
| 109 | for( int i = 0; i < this->numTriangles; ++i) |
---|
| 110 | { |
---|
| 111 | for( int j = 0; j < 3; ++j) |
---|
| 112 | { |
---|
| 113 | pVert = &this->pVertices[this->pTriangles[i]->indexToVertices[j]]; |
---|
[4853] | 114 | if( pVert[0] > rectCenter->x + this->offset && pVert[2] > rectCenter->z + this->offset) |
---|
| 115 | listA->add(&this->pTriangles[i]); |
---|
[4852] | 116 | if( pVert[0] > rectCenter->x + this->offset && pVert[2]< rectCenter->z + this->offset) |
---|
[4853] | 117 | listB->add(&this->pTriangles[i]); |
---|
[4852] | 118 | if( pVert[0] < rectCenter->x + this->offset && pVert[2] > rectCenter->z + this->offset) |
---|
[4853] | 119 | listC->add(&this->pTriangles[i]); |
---|
[4852] | 120 | if( pVert[0] < rectCenter->x + this->offset && pVert[2] < rectCenter->z + this->offset) |
---|
[4853] | 121 | listD->add(&this->pTriangles[i]); |
---|
[4851] | 122 | } |
---|
| 123 | } |
---|
[4853] | 124 | printf("Temp. list Num. o El: A: %i, B: %i, C: %i, D: %i\n", listA->getSize(), listB->getSize(), listC->getSize(), listD->getSize()); |
---|
| 125 | |
---|
| 126 | |
---|
| 127 | /* Separating into to the triangle lists */ |
---|
| 128 | sTriangleExt** pTriA; //!< Triangle array A |
---|
| 129 | sTriangleExt** pTriB; //!< Triangle array B |
---|
| 130 | sTriangleExt** pTriC; //!< Triangle array C |
---|
| 131 | sTriangleExt** pTriD; //!< Triangle array D |
---|
| 132 | float lenA; //!< length array A |
---|
| 133 | float lenB; //!< length array B |
---|
| 134 | float lenC; //!< length array C |
---|
| 135 | float lenD; //!< length array D |
---|
| 136 | tIterator<sTriangleExt*>* iterator; //!< iterator for the list iterations |
---|
[4855] | 137 | sTriangleExt** tempTri; //!< temp save place for triangle pointer |
---|
[4854] | 138 | int counter; //!< counter for the while loops |
---|
[4853] | 139 | |
---|
| 140 | lenA = listA->getSize(); |
---|
| 141 | lenB = listB->getSize(); |
---|
| 142 | lenC = listC->getSize(); |
---|
| 143 | lenD = listD->getSize(); |
---|
| 144 | |
---|
| 145 | pTriA = new sTriangleExt*[listA->getSize()]; |
---|
| 146 | pTriB = new sTriangleExt*[listB->getSize()]; |
---|
| 147 | pTriC = new sTriangleExt*[listC->getSize()]; |
---|
| 148 | pTriD = new sTriangleExt*[listD->getSize()]; |
---|
| 149 | |
---|
| 150 | |
---|
[4854] | 151 | counter = 0; |
---|
[4853] | 152 | iterator = listA->getIterator(); |
---|
[4855] | 153 | tempTri = iterator->nextElement(); |
---|
[4854] | 154 | while( tempTri) |
---|
| 155 | { |
---|
[4855] | 156 | pTriA[counter] = *tempTri; |
---|
| 157 | tempTri = iterator->nextElement(); |
---|
[4854] | 158 | ++counter; |
---|
| 159 | } |
---|
[4853] | 160 | |
---|
[4854] | 161 | counter = 0; |
---|
| 162 | iterator = listB->getIterator(); |
---|
[4855] | 163 | tempTri = iterator->nextElement(); |
---|
[4854] | 164 | while( tempTri) |
---|
| 165 | { |
---|
[4855] | 166 | pTriB[counter] = *tempTri; |
---|
| 167 | tempTri = iterator->nextElement(); |
---|
[4854] | 168 | ++counter; |
---|
| 169 | } |
---|
| 170 | |
---|
| 171 | counter = 0; |
---|
| 172 | iterator = listC->getIterator(); |
---|
[4855] | 173 | tempTri = iterator->nextElement(); |
---|
[4854] | 174 | while( tempTri) |
---|
| 175 | { |
---|
[4855] | 176 | pTriC[counter] = *tempTri; |
---|
| 177 | tempTri = iterator->nextElement(); |
---|
[4854] | 178 | ++counter; |
---|
| 179 | } |
---|
[4853] | 180 | |
---|
[4854] | 181 | counter = 0; |
---|
| 182 | iterator = listD->getIterator(); |
---|
[4855] | 183 | tempTri = iterator->nextElement(); |
---|
[4854] | 184 | while( tempTri) |
---|
| 185 | { |
---|
[4855] | 186 | pTriD[counter] = *tempTri; |
---|
| 187 | tempTri = iterator->nextElement(); |
---|
[4854] | 188 | ++counter; |
---|
| 189 | } |
---|
[4853] | 190 | |
---|
| 191 | PRINTF(0)("separation complete\n"); |
---|
[4851] | 192 | } |
---|
| 193 | |
---|
| 194 | |
---|
[4853] | 195 | |
---|
[4851] | 196 | /** |
---|
[4836] | 197 | * draws the debug quadtree boxes around the model |
---|
[4812] | 198 | */ |
---|
| 199 | void QuadtreeNode::drawTree(int depth, int drawMode) const |
---|
| 200 | {} |
---|
[4845] | 201 | |
---|
| 202 | |
---|
| 203 | /** |
---|
| 204 | \brief gets the maximal dimension of a model |
---|
| 205 | * @param playerModel the model that this measurement is based on |
---|
| 206 | \return the dimension of the AbstractModel as a Rectangle |
---|
| 207 | |
---|
| 208 | The rectangle is x-z axis aligned. ATTENTION: if there are any vertices in the model, that exceed the |
---|
[4846] | 209 | size of 999999.0, there probably will be some errors in the dimensions calculations. Write an email to |
---|
| 210 | patrick@orxonox.ethz.ch if you will ever encounter a model bigger than 999999.0 units, I will realy be |
---|
| 211 | happy to see orxonox used to extensivly :) |
---|
[4845] | 212 | */ |
---|
| 213 | Rectangle* QuadtreeNode::getDimension(modelInfo* pModelInfo) |
---|
| 214 | { |
---|
| 215 | float maxX, maxY; //!< the maximal coordinates axis |
---|
| 216 | float minX, minY; //!< minimal axis coorindates |
---|
| 217 | const float* pVertices; //!< pointer to the current vertices |
---|
| 218 | |
---|
| 219 | maxX = -999999; maxY = -999999; |
---|
| 220 | minX = 999999; minY = 999999; |
---|
| 221 | /* get maximal/minimal x/y */ |
---|
| 222 | for( int i = 0; i < pModelInfo->numVertices; ++i) |
---|
| 223 | { |
---|
| 224 | pVertices = &pModelInfo->pVertices[i * 3]; |
---|
| 225 | if( pVertices[0] > maxX) |
---|
| 226 | maxX = pVertices[0]; |
---|
| 227 | if( pVertices[2] > maxY) |
---|
| 228 | maxY = pVertices[2]; |
---|
| 229 | |
---|
| 230 | if( pVertices[0] < minX) |
---|
| 231 | minX = pVertices[0]; |
---|
| 232 | if( pVertices[2] < minY) |
---|
| 233 | minY = pVertices[2]; |
---|
| 234 | } |
---|
| 235 | |
---|
| 236 | Rectangle* rect = new Rectangle(); |
---|
| 237 | rect->setCenter((maxX + minX) / 2.0f, 0.0f, (maxY + minY) / 2.0f); /* this is little strange, since y is in opengl the up vector */ |
---|
| 238 | rect->setAxis(fmax(((fabs(maxX) + fabs(minX)) / 2.0f), ((fabs(maxY) + fabs(minY)) / 2.0f))); |
---|
| 239 | |
---|
| 240 | PRINTF(0)("Dimension Informationation: X: min/max %f/%f Y: min/max %f/%f\n", minX, maxX, minY, maxY); |
---|
[4855] | 241 | PRINTF(0)("Center: %f, %f, %f Axis: %f\n", rect->getCenter()->x, rect->getCenter()->y, rect->getCenter()->z, rect->getAxis()); |
---|
[4845] | 242 | return rect; |
---|
| 243 | } |
---|
| 244 | |
---|