source: trunk/VUT/chcdemo/HierarchyNode.cpp @ 10

Revision 10, 10.9 KB checked in by gametools, 20 years ago (diff)

vienna university of technology first files

RevLine 
[10]1#include "HierarchyNode.h"
2#include "glInterface.h"
3#include <math.h>
4#include <limits.h>
5#include <float.h>
6
7typedef vector<Geometry *> GeometryList;
8
9// criteria and values partly taken from Piringer's thesis
10
11// values used as termination criteria for the tree generation
12// the overall surface
13float HierarchyNode::sSurfaceThreshold;
14// the maximum tree depth
15int HierarchyNode::sMaxDepth;
16// maximum number of objects in a node
17int HierarchyNode::sGeometryThreshold;
18
19// percentage of allowed deviation from the center split plane
20float HierarchyNode::sSplitBandwith;
21
22// also render bounding volume
23bool HierarchyNode::sRenderBoundingVolume = false;
24
25HierarchyNode::HierarchyNode(): mVisible(false), mLastVisited(0),
26mParent(NULL), mOcclusionQuery(0), mAABValid(false), mLeftChild(NULL), mRightChild(NULL),
27mNumHierarchyNodes(1), mSplitAxis(X_AXIS), mLastRendered(-1), mSplitValue(0),
28mDepth(0), mEnclosedSpaceValid(false), mDistance(0)
29{
30        copyVector3Values(mBoundingBox.min, 0, 0, 0);
31        copyVector3Values(mBoundingBox.max, 0, 0, 0);
32
33        copyVector3Values(mEnclosedSpace.min, 0, 0, 0);
34        copyVector3Values(mEnclosedSpace.max, 0, 0, 0);
35
36        // bounding box color
37        mBoxColor[0] = mBoxColor[2] = 0; mBoxColor[1] = 1.0;
38}
39
40HierarchyNode::HierarchyNode(const Vector3 boundLower, const Vector3 boundUpper,
41                                                         HierarchyNode *parent, int depth)
42:mNumHierarchyNodes(1), mOcclusionQuery(0), mLeftChild(NULL),
43mRightChild(NULL), mSplitAxis(X_AXIS), mVisible(false),
44mLastVisited(0), mParent(parent), mAABValid(false),
45mLastRendered(-1), mSplitValue(0), mDepth(depth),
46mEnclosedSpaceValid(true), mDistance(0)
47{
48        copyVector3Values(mBoundingBox.min, 0, 0, 0);
49        copyVector3Values(mBoundingBox.max, 0, 0, 0);
50
51        copyVector3(mEnclosedSpace.min, boundLower);
52        copyVector3(mEnclosedSpace.max, boundUpper);
53
54        float vol = calcAABoxSurface(mEnclosedSpace);
55
56        mBoxColor[0] = mBoxColor[2] = 0; mBoxColor[1] = 1.0;
57}
58
59
60void HierarchyNode::InitKdTree(HierarchyNode *root)
61{
62        sMaxDepth = (int)((log((float) root->GetGeometry().size())/log(2.0f)) * 20.0f);
63
64        sSurfaceThreshold = FLT_MAX;
65
66        // factor times mininal surface as determination criterium
67        const float factor = 2.5;
68
69        for (GeometryList::const_iterator it = root->GetGeometry().begin(); it != root->GetGeometry().end(); it++)
70        {
71                // same geometry can possible be in to or more nodes => also test for them
72                float surface = calcAABoxSurface((*it)->GetBoundingVolume()) * factor;
73
74                if(surface < sSurfaceThreshold) sSurfaceThreshold = surface;
75        }
76
77        // number of objects in a leaf
78        sGeometryThreshold = 1;
79
80        // percentage of allowed deviation from the center split plane
81        sSplitBandwith = 0.15;
82}
83
84
85HierarchyNode::~HierarchyNode()
86{
87        if(mLeftChild)
88                delete mLeftChild;
89
90        if(mRightChild)
91                delete mRightChild;
92}
93
94int HierarchyNode::Render()
95{
96        int renderedGeometry = 0;
97
98        if(sRenderBoundingVolume)
99        {
100                glColor3fv(mBoxColor);
101        RenderBoundingVolumeForVisualization();
102        }
103
104        // prevent the geometry to be rendered several times in the same frame
105        if(mLastRendered != mLastVisited)
106        {
107                for (GeometryList::const_iterator it = mGeometry.begin(); it != mGeometry.end(); it++)
108                {
109                        // same geometry can possible be in to or more nodes => also test for them
110                        if((*it)->GetLastVisited() != mLastVisited)
111                        {
112                                (*it)->SetLastVisited(mLastVisited);
113                                (*it)->Render();
114                                renderedGeometry ++;
115                        }
116                }
117                mLastRendered = mLastVisited;
118        }
119
120        return renderedGeometry;
121}
122
123bool HierarchyNode::Visible()
124{
125        return mVisible;
126}
127
128void HierarchyNode::SetVisible(bool visible)
129{
130        mVisible = visible;
131}
132
133void HierarchyNode::SetLeftChild(HierarchyNode *child)
134{
135        mLeftChild = child;
136}
137
138void HierarchyNode::SetRightChild(HierarchyNode *child)
139{
140        mRightChild = child;
141}
142
143HierarchyNode *HierarchyNode::GetLeftChild()
144{
145        return mLeftChild;
146}
147
148HierarchyNode *HierarchyNode::GetRightChild()
149{
150        return mRightChild;
151}
152
153int HierarchyNode::LastVisited()
154{
155        return mLastVisited;
156}
157
158void HierarchyNode::SetLastVisited(int lastVisited)
159{
160        mLastVisited = lastVisited;
161}
162
163bool HierarchyNode::IsLeaf()
164{
165        return (!mLeftChild && !mRightChild);
166}
167
168void HierarchyNode::AddGeometry(Geometry *geometry)
169{
170        mGeometry.push_back(geometry);
171               
172        if(!mAABValid)
173        {
174                copyVector3(mBoundingBox.min, geometry->GetBoundingVolume().min);
175                copyVector3(mBoundingBox.max, geometry->GetBoundingVolume().max);
176
177                mAABValid = true;
178        }
179        else
180                combineAABoxes(&mBoundingBox, geometry->GetBoundingVolume());
181
182        // root node
183        if(mDepth == 0)
184        {
185                if(!mEnclosedSpaceValid)
186                {
187                        copyVector3(mEnclosedSpace.min, geometry->GetBoundingVolume().min);
188                        copyVector3(mEnclosedSpace.max, geometry->GetBoundingVolume().max);
189
190                        mEnclosedSpaceValid = true;
191                }
192                else
193                        combineAABoxes(&mEnclosedSpace, geometry->GetBoundingVolume());
194        }
195        else
196        {
197                // cut boxes so they fit into the enclosed space
198                clipAABoxByAABox(&mBoundingBox, mEnclosedSpace);
199        }
200}
201
202HierarchyNode *HierarchyNode::GetParent()
203{
204        return mParent;
205}
206
207int HierarchyNode::GetOcclusionQuery()
208{
209        return mOcclusionQuery;
210}
211
212void HierarchyNode::SetOcclusionQuery(int occlusionQuery)
213{
214        mOcclusionQuery = occlusionQuery;
215}
216
217void HierarchyNode::RenderBoundingVolume()
218{
219        Vector3x8 vertices;
220
221        calcAABoxPoints(vertices, mBoundingBox);
222
223        //glPolygonMode(GL_FRONT, GL_LINE);
224        //     7+------+6
225        //     /|     /|
226        //    / |    / |
227        //   / 4+---/--+5
228        // 3+------+2 /    y   z
229        //  | /    | /     |  /
230        //  |/     |/      |/
231        // 0+------+1      *---x
232
233        //---- render AABB
234        glBegin(GL_TRIANGLE_FAN);
235                glVertex3dv(vertices[6]);
236                glVertex3dv(vertices[5]);
237                glVertex3dv(vertices[4]);
238                glVertex3dv(vertices[7]);
239                glVertex3dv(vertices[3]);
240                glVertex3dv(vertices[2]);
241                glVertex3dv(vertices[1]);
242                glVertex3dv(vertices[5]);
243        glEnd();
244
245        //---- render second half of AABB
246        glBegin(GL_TRIANGLE_FAN);
247                glVertex3dv(vertices[0]);
248                glVertex3dv(vertices[1]);
249                glVertex3dv(vertices[2]);
250                glVertex3dv(vertices[3]);
251                glVertex3dv(vertices[7]);
252                glVertex3dv(vertices[4]);
253                glVertex3dv(vertices[5]);
254                glVertex3dv(vertices[1]);
255        glEnd();
256}
257
258
259void HierarchyNode::RenderBoundingVolumeForVisualization()
260{
261        glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
262        glDisable(GL_LIGHTING);
263        glDisable(GL_CULL_FACE);
264               
265        RenderBoundingVolume();
266
267        glEnable(GL_CULL_FACE);
268        glEnable(GL_LIGHTING);
269        glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
270}
271
272
273
274const AABox &HierarchyNode::GetBoundingVolume()
275{
276        return mBoundingBox;
277}
278
279int     HierarchyNode::GenerateKdTree()
280{
281        // check the termination criterium (a heuristic)
282        if (SimpleEnough())
283        {
284                return 1;
285        }
286
287        // largest dimension will be split
288        Vector3 size;
289        diffVector3(size, mBoundingBox.max, mBoundingBox.min);
290   
291        if (size[X_AXIS] > size[Y_AXIS])       
292                mSplitAxis      = (size[X_AXIS] > size[Z_AXIS]) ? X_AXIS : Z_AXIS;
293        else                                   
294                mSplitAxis      = (size[Y_AXIS] > size[Z_AXIS]) ? Y_AXIS : Z_AXIS;
295
296        // select the value of the split plane
297        mSplitValue = ComputeSplitPlane();
298       
299        // generate the children
300        Vector3 changedLower;
301        Vector3 changedUpper;
302
303        copyVector3(changedLower, mEnclosedSpace.min);
304        copyVector3(changedUpper, mEnclosedSpace.max);
305               
306        changedLower[mSplitAxis] = mSplitValue;
307        changedUpper[mSplitAxis] = mSplitValue;
308
309        mLeftChild      = new HierarchyNode(mEnclosedSpace.min, changedUpper, this, mDepth + 1);
310        mRightChild     = new HierarchyNode(changedLower, mEnclosedSpace.max, this, mDepth + 1);
311
312        // add the geometry to the according children
313        for (GeometryList::iterator it = mGeometry.begin(); it != mGeometry.end(); it++)
314        {
315                if ((*it)->GetBoundingVolume().min[mSplitAxis] >= mSplitValue)
316                {
317                        // box lies completely within right part
318                        mRightChild->AddGeometry(*it);
319                }
320                else if ((*it)->GetBoundingVolume().max[mSplitAxis] <= mSplitValue)
321                {
322                        // box lies completely within left part
323                        mLeftChild->AddGeometry((*it));
324                }
325                else
326                {
327                        //---- box intersects both parts
328                        mLeftChild->AddGeometry((*it));
329                        mRightChild->AddGeometry((*it));
330                }
331        }
332
333        //---- we continue with the children
334        int leftSize  = mLeftChild->GenerateKdTree();
335        int rightSize = mRightChild->GenerateKdTree();
336
337        // since the geometry is now referenced by the children
338        mGeometry.clear();
339       
340        mNumHierarchyNodes = leftSize + rightSize + 1;
341
342        return mNumHierarchyNodes;
343}
344
345bool HierarchyNode::SimpleEnough()
346{
347        return ((mGeometry.size() <= (unsigned int)sGeometryThreshold) ||
348                    (calcAABoxSurface(mBoundingBox) <= sSurfaceThreshold) ||
349                        (sMaxDepth <= mDepth));
350}
351
352float HierarchyNode::ComputeSplitPlane()
353{
354        float left      = mBoundingBox.min[mSplitAxis];
355        float right     = mBoundingBox.max[mSplitAxis];
356
357        // the smaller the value returned from the heuristic, the better => big starting value
358        float bestValue = FLT_MAX;
359        float result = 0.0f;
360
361        bool found      = false;
362
363        // calculate the borders of the band
364        float currLeft, currRight;
365        currLeft = currRight = (left + right) / 2.0f;
366       
367        currLeft  -= (right - left) * sSplitBandwith;
368        currRight += (right - left) * sSplitBandwith;
369
370        // check all geometry within that node
371        for (GeometryList::const_iterator it = mGeometry.begin(); it != mGeometry.end(); it++)
372        {
373                // one border of the geometry's AABB
374                float leftPlane  = (*it)->GetBoundingVolume().min[mSplitAxis];
375                // the other border of the geometry's AABB
376                float rightPlane = (*it)->GetBoundingVolume().max[mSplitAxis];
377               
378                // only consider planes that lie within the band
379                if ((leftPlane > currLeft) && (leftPlane < currRight))
380                {
381                        // compute the heuristic for the left plane and note the value if it was good
382                        float currValue = ComputeHeuristics(leftPlane);
383
384                        if (currValue < bestValue)
385                        {
386                                bestValue = currValue;
387                                result    = leftPlane;
388                                found     = true;
389                        }
390                }
391
392                if ((rightPlane > currLeft) && (rightPlane < currRight))
393                {
394                        // compute the heuristic for the right plane and note the value if it was good
395                        float currValue = ComputeHeuristics(rightPlane);
396
397                        if (currValue < bestValue)
398                        {
399                                bestValue       = currValue;
400                                result          = rightPlane;
401                                found           = true;
402                        }
403                }
404        }
405
406        // in case we haven't found any proper plane, we simply take the center
407        if (!found)     
408                result = (left + right) / 2.0f;
409                       
410        return result;
411}
412
413float HierarchyNode::ComputeHeuristics(float pos)
414{
415        // this implements a very simple heuristic: it simply counts the nodes being intersected by the splitplane
416        float result = 0.0f;
417
418        for (GeometryList::const_iterator it = mGeometry.begin(); it != mGeometry.end(); it++)
419        {
420                if (((*it)->GetBoundingVolume().min[mSplitAxis] < pos) &&
421                        ((*it)->GetBoundingVolume().max[mSplitAxis] > pos))
422                {
423                        result += 1.0f;
424                }
425        }
426
427        return result;
428}
429
430int HierarchyNode::GetNumHierarchyNodes()
431{
432        return mNumHierarchyNodes;
433}
434
435void HierarchyNode::PushChildrenOrdered(const Vector3 viewpoint, TraversalStack &traversalStack)
436{
437        if(viewpoint[mSplitAxis] > mSplitValue)
438        {
439                traversalStack.push(mLeftChild);
440                traversalStack.push(mRightChild);
441        }
442        else
443        {
444                traversalStack.push(mRightChild);
445                traversalStack.push(mLeftChild);
446        }
447}
448
449
450void HierarchyNode::SetRenderBoundingVolume(bool renderBoundingVolume)
451{
452        sRenderBoundingVolume = renderBoundingVolume;
453}
454
455
456GeometryList &HierarchyNode::GetGeometry()
457{
458        return mGeometry;
459}
460
461
462float HierarchyNode::GetDistance()
463{
464        return mDistance;
465}
466
467
468void HierarchyNode::SetDistance(float distance)
469{
470        mDistance = distance;
471}
Note: See TracBrowser for help on using the repository browser.