7 |
7 |
8 #include "octree.h" |
8 #include "octree.h" |
9 |
9 |
10 OctreeNode::~OctreeNode() |
10 OctreeNode::~OctreeNode() |
11 { |
11 { |
12 if (shapes != NULL) |
12 if (isLeaf()) |
|
13 { |
|
14 leaf = leaf^1; // zero leaf bit |
13 delete shapes; |
15 delete shapes; |
|
16 } |
14 else |
17 else |
15 delete[] children; |
18 delete[] children; |
16 } |
19 } |
17 |
20 |
18 void OctreeNode::subdivide(BBox bbox, int maxdepth) |
21 void OctreeNode::subdivide(BBox bbox, int maxdepth) |
19 { |
22 { |
20 // make children |
23 ShapeList *l_shapes = getShapes(); |
21 children = new OctreeNode[8]; |
24 |
|
25 // prepare children (this also sets this node as non-leaf) |
|
26 makeChildren(); |
22 |
27 |
23 // evaluate centres for axes |
28 // evaluate centres for axes |
24 const Float xsplit = (bbox.L.x + bbox.H.x)*0.5; |
29 const Float xsplit = (bbox.L.x + bbox.H.x)*0.5; |
25 const Float ysplit = (bbox.L.y + bbox.H.y)*0.5; |
30 const Float ysplit = (bbox.L.y + bbox.H.y)*0.5; |
26 const Float zsplit = (bbox.L.z + bbox.H.z)*0.5; |
31 const Float zsplit = (bbox.L.z + bbox.H.z)*0.5; |
40 } |
45 } |
41 |
46 |
42 // distribute shapes to children |
47 // distribute shapes to children |
43 ShapeList::iterator sh; |
48 ShapeList::iterator sh; |
44 unsigned int shapenum = 0; |
49 unsigned int shapenum = 0; |
45 for (sh = shapes->begin(); sh != shapes->end(); sh++) |
50 for (sh = l_shapes->begin(); sh != l_shapes->end(); sh++) |
46 { |
51 { |
47 for (int i = 0; i < 8; i++) |
52 for (int i = 0; i < 8; i++) |
48 if ((*sh)->intersect_bbox(childbb[i])) |
53 if ((*sh)->intersect_bbox(childbb[i])) |
49 { |
54 { |
50 getChild(i)->addShape(*sh); |
55 getChild(i)->addShape(*sh); |
51 shapenum++; |
56 shapenum++; |
52 } |
57 } |
53 } |
58 } |
54 |
59 |
55 if ((shapes->size() <= 8 && shapenum > 2*shapes->size()) |
60 if ((l_shapes->size() <= 8 && shapenum > 2*l_shapes->size()) |
56 || shapenum >= 6*shapes->size()) |
61 || shapenum >= 6*l_shapes->size()) |
57 { |
62 { |
58 // bad subdivision, revert |
63 // bad subdivision, revert |
59 delete[] children; |
64 delete[] children; |
|
65 setShapes(l_shapes); |
60 return; |
66 return; |
61 } |
67 } |
62 |
68 |
63 // remove shapes and set this node to non-leaf |
69 // remove shapes and set this node to non-leaf |
64 delete shapes; |
70 delete l_shapes; |
65 shapes = NULL; |
|
66 |
71 |
67 // recursive subdivision |
72 // recursive subdivision |
68 for (int i = 0; i < 8; i++) |
73 for (int i = 0; i < 8; i++) |
69 if (maxdepth > 1 && getChild(i)->shapes->size() > 4) |
74 if (maxdepth > 1 && getChild(i)->getShapes()->size() > 4) |
70 children[i].subdivide(childbb[i], maxdepth-1); |
75 children[i].subdivide(childbb[i], maxdepth-1); |
71 } |
76 } |
72 |
77 |
73 void Octree::build() |
78 void Octree::build() |
74 { |
79 { |
194 if (node->isLeaf()) |
199 if (node->isLeaf()) |
195 { |
200 { |
196 ShapeList::iterator shape; |
201 ShapeList::iterator shape; |
197 //register Float mindist = max3(tx0,ty0,tz0); |
202 //register Float mindist = max3(tx0,ty0,tz0); |
198 register Float dist = min(nearest_distance, min3(tx1,ty1,tz1)); |
203 register Float dist = min(nearest_distance, min3(tx1,ty1,tz1)); |
199 for (shape = node->shapes->begin(); shape != node->shapes->end(); shape++) |
204 for (shape = node->getShapes()->begin(); shape != node->getShapes()->end(); shape++) |
200 if (*shape != origin_shape && (*shape)->intersect(ray, dist)) |
205 if (*shape != origin_shape && (*shape)->intersect(ray, dist)) |
201 { |
206 { |
202 nearest_shape = *shape; |
207 nearest_shape = *shape; |
203 nearest_distance = dist; |
208 nearest_distance = dist; |
204 } |
209 } |