source: obsolete/trunk/VUT/chcdemo/HierarchyNode.cpp @ 345

Revision 345, 10.8 KB checked in by mattausch, 19 years ago (diff)

fixed bug in chc when traversing node two times because of priority queue. left debug info in there

Line 
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
153unsigned int HierarchyNode::LastVisited()
154{
155        return mLastVisited;
156}
157
158void HierarchyNode::SetLastVisited(unsigned 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
461void HierarchyNode::SetDistance(float distance)
462{
463        mDistance = distance;
464}
Note: See TracBrowser for help on using the repository browser.