42 childbb[(i<<1)+1].L.z = zsplit; // 1,3,5,7 |
42 childbb[(i<<1)+1].L.z = zsplit; // 1,3,5,7 |
43 } |
43 } |
44 |
44 |
45 // distribute shapes to children |
45 // distribute shapes to children |
46 ShapeList::iterator sh; |
46 ShapeList::iterator sh; |
47 BBox shbb; |
|
48 int child, both; |
|
49 unsigned int shapenum = 0; |
47 unsigned int shapenum = 0; |
50 for (sh = shapes->begin(); sh != shapes->end(); sh++) |
48 for (sh = shapes->begin(); sh != shapes->end(); sh++) |
51 { |
49 { |
52 child = 0; |
50 for (int i = 0; i < 8; i++) |
53 both = 0; |
51 if ((*sh)->intersect_bbox(childbb[i])) |
54 shbb = (*sh)->get_bbox(); |
|
55 |
|
56 if (shbb.L.x >= xsplit) |
|
57 child |= 4; //right |
|
58 else if (shbb.H.x > xsplit) |
|
59 both |= 4; // both |
|
60 // for left, do nothing |
|
61 |
|
62 if (shbb.L.y >= ysplit) |
|
63 child |= 2; |
|
64 else if (shbb.H.y > ysplit) |
|
65 both |= 2; |
|
66 |
|
67 if (shbb.L.z >= zsplit) |
|
68 child |= 1; |
|
69 else if (shbb.H.z > zsplit) |
|
70 both |= 1; |
|
71 |
|
72 if (!both) |
|
73 { |
|
74 getChild(child)->addShape(*sh); |
|
75 shapenum++; |
|
76 } |
|
77 else |
|
78 { |
|
79 // shape goes to more than one child |
|
80 if (both == 7) |
|
81 { |
52 { |
82 for (int i = 0; i < 8; i++) |
53 getChild(i)->addShape(*sh); |
83 getChild(i)->addShape(*sh); |
54 shapenum++; |
84 shapenum += 8; |
|
85 } |
55 } |
86 else if (both == 3 || both >= 5) |
|
87 { |
|
88 if (both == 3) |
|
89 { |
|
90 for (int i = 0; i < 4; i++) |
|
91 getChild(child + i)->addShape(*sh); |
|
92 } |
|
93 else if (both == 5) |
|
94 { |
|
95 for (int i = 0; i < 4; i++) |
|
96 getChild(child + i+(i>>1<<1))->addShape(*sh); |
|
97 } |
|
98 else if (both == 6) |
|
99 { |
|
100 for (int i = 0; i < 4; i++) |
|
101 getChild(child + (i<<1))->addShape(*sh); |
|
102 } |
|
103 shapenum += 4; |
|
104 } |
|
105 else |
|
106 { |
|
107 getChild(child)->addShape(*sh); |
|
108 getChild(child+both)->addShape(*sh); |
|
109 shapenum += 2; |
|
110 } |
|
111 } |
|
112 } |
56 } |
113 |
57 |
114 if (shapes->size() <= 8 && shapenum > 2*shapes->size()) |
58 if (shapes->size() <= 8 && shapenum > 2*shapes->size()) |
115 { |
59 { |
116 // bad subdivision, revert |
60 // bad subdivision, revert |
314 Float ty0 = (bbox.L.y - ro.y) / rdir.y; |
258 Float ty0 = (bbox.L.y - ro.y) / rdir.y; |
315 Float ty1 = (bbox.H.y - ro.y) / rdir.y; |
259 Float ty1 = (bbox.H.y - ro.y) / rdir.y; |
316 Float tz0 = (bbox.L.z - ro.z) / rdir.z; |
260 Float tz0 = (bbox.L.z - ro.z) / rdir.z; |
317 Float tz1 = (bbox.H.z - ro.z) / rdir.z; |
261 Float tz1 = (bbox.H.z - ro.z) / rdir.z; |
318 |
262 |
319 //Octree *node = root; |
|
320 if (max(max(tx0,ty0),tz0) < min (min(tx1,ty1),tz1)) |
263 if (max(max(tx0,ty0),tz0) < min (min(tx1,ty1),tz1)) |
321 return proc_subtree(a,tx0,ty0,tz0,tx1,ty1,tz1,root, |
264 return proc_subtree(a,tx0,ty0,tz0,tx1,ty1,tz1,root, |
322 origin_shape, ray, nearest_distance); |
265 origin_shape, ray, nearest_distance); |
323 else |
266 else |
324 return NULL; |
267 return NULL; |