68 /* adjust bounding box */ |
68 /* adjust bounding box */ |
69 BBox shapebb = aShape->get_bbox(); |
69 BBox shapebb = aShape->get_bbox(); |
70 if (shapebb.L.x < bbox.L.x) bbox.L.x = shapebb.L.x; |
70 if (shapebb.L.x < bbox.L.x) bbox.L.x = shapebb.L.x; |
71 if (shapebb.L.y < bbox.L.y) bbox.L.y = shapebb.L.y; |
71 if (shapebb.L.y < bbox.L.y) bbox.L.y = shapebb.L.y; |
72 if (shapebb.L.z < bbox.L.z) bbox.L.z = shapebb.L.z; |
72 if (shapebb.L.z < bbox.L.z) bbox.L.z = shapebb.L.z; |
73 if (shapebb.R.x > bbox.R.x) bbox.R.x = shapebb.R.x; |
73 if (shapebb.H.x > bbox.H.x) bbox.H.x = shapebb.H.x; |
74 if (shapebb.R.y > bbox.R.y) bbox.R.y = shapebb.R.y; |
74 if (shapebb.H.y > bbox.H.y) bbox.H.y = shapebb.H.y; |
75 if (shapebb.R.z > bbox.R.z) bbox.R.z = shapebb.R.z; |
75 if (shapebb.H.z > bbox.H.z) bbox.H.z = shapebb.H.z; |
76 } |
76 } |
77 }; |
77 }; |
78 |
78 |
79 Shape *Container::nearest_intersection(const Shape *origin_shape, const Ray &ray, |
79 Shape *Container::nearest_intersection(const Shape *origin_shape, const Ray &ray, |
80 float &nearest_distance) |
80 float &nearest_distance) |
110 |
110 |
111 SortableShapeList::iterator sh; |
111 SortableShapeList::iterator sh; |
112 for (sh = sslist.begin(); sh != sslist.end(); sh++) |
112 for (sh = sslist.begin(); sh != sslist.end(); sh++) |
113 { |
113 { |
114 splitlist.push_back(SplitPos(sh->bbox.L.cell[axis])); |
114 splitlist.push_back(SplitPos(sh->bbox.L.cell[axis])); |
115 splitlist.push_back(SplitPos(sh->bbox.R.cell[axis])); |
115 splitlist.push_back(SplitPos(sh->bbox.H.cell[axis])); |
116 } |
116 } |
117 sort(splitlist.begin(), splitlist.end()); |
117 sort(splitlist.begin(), splitlist.end()); |
118 // remove duplicate splits |
118 // remove duplicate splits |
119 splitlist.resize(unique(splitlist.begin(), splitlist.end()) - splitlist.begin()); |
119 splitlist.resize(unique(splitlist.begin(), splitlist.end()) - splitlist.begin()); |
120 |
120 |
129 { |
129 { |
130 spl->lnum++; |
130 spl->lnum++; |
131 continue; |
131 continue; |
132 } |
132 } |
133 // if shape is completely contained in split plane |
133 // if shape is completely contained in split plane |
134 if (spl->pos == sh->bbox.L.cell[axis] == sh->bbox.R.cell[axis]) |
134 if (spl->pos == sh->bbox.L.cell[axis] == sh->bbox.H.cell[axis]) |
135 { |
135 { |
136 if (spl->pos - bbox.L.cell[axis] < bbox.R.cell[axis] - spl->pos) |
136 if (spl->pos - bbox.L.cell[axis] < bbox.H.cell[axis] - spl->pos) |
137 { |
137 { |
138 // left subcell is smaller -> if not empty, put shape here |
138 // left subcell is smaller -> if not empty, put shape here |
139 if (spl->lnum) |
139 if (spl->lnum) |
140 spl->lnum++; |
140 spl->lnum++; |
141 else |
141 else |
148 spl->lnum++; |
148 spl->lnum++; |
149 } |
149 } |
150 sh->setMark(); |
150 sh->setMark(); |
151 } else |
151 } else |
152 // if shape is on left side of split plane |
152 // if shape is on left side of split plane |
153 if (sh->bbox.R.cell[axis] <= spl->pos) |
153 if (sh->bbox.H.cell[axis] <= spl->pos) |
154 { |
154 { |
155 spl->lnum++; |
155 spl->lnum++; |
156 sh->setMark(); |
156 sh->setMark(); |
157 } else |
157 } else |
158 // if shape occupies both sides of split plane |
158 // if shape occupies both sides of split plane |
159 if (sh->bbox.L.cell[axis] < spl->pos && sh->bbox.R.cell[axis] > spl->pos) |
159 if (sh->bbox.L.cell[axis] < spl->pos && sh->bbox.H.cell[axis] > spl->pos) |
160 { |
160 { |
161 spl->lnum++; |
161 spl->lnum++; |
162 spl->rnum++; |
162 spl->rnum++; |
163 } else |
163 } else |
164 // if shape is on right side of split plane |
164 // if shape is on right side of split plane |
179 BBox lbb = bbox; |
179 BBox lbb = bbox; |
180 BBox rbb = bbox; |
180 BBox rbb = bbox; |
181 for (spl = splitlist.begin(); spl != splitlist.end(); spl++) |
181 for (spl = splitlist.begin(); spl != splitlist.end(); spl++) |
182 { |
182 { |
183 // calculate SAH cost of this split |
183 // calculate SAH cost of this split |
184 lbb.R.cell[axis] = spl->pos; |
184 lbb.H.cell[axis] = spl->pos; |
185 rbb.L.cell[axis] = spl->pos; |
185 rbb.L.cell[axis] = spl->pos; |
186 float SAL = 2*(lbb.w()*lbb.h() + lbb.w()*lbb.d() + lbb.h()*lbb.d()); |
186 float SAL = 2*(lbb.w()*lbb.h() + lbb.w()*lbb.d() + lbb.h()*lbb.d()); |
187 float SAR = 2*(rbb.w()*rbb.h() + rbb.w()*rbb.d() + rbb.h()*rbb.d()); |
187 float SAR = 2*(rbb.w()*rbb.h() + rbb.w()*rbb.d() + rbb.h()*rbb.d()); |
188 float splitcost = K + SAL/SAV*(K+spl->lnum) + SAR/SAV*(K+spl->rnum); |
188 float splitcost = K + SAL/SAV*(K+spl->lnum) + SAR/SAV*(K+spl->rnum); |
189 |
189 |
207 v.cell[axis] = splitpos->pos; |
207 v.cell[axis] = splitpos->pos; |
208 v.cell[(axis+1)%3] = bbox.L.cell[(axis+1)%3]; |
208 v.cell[(axis+1)%3] = bbox.L.cell[(axis+1)%3]; |
209 v.cell[(axis+2)%3] = bbox.L.cell[(axis+2)%3]; |
209 v.cell[(axis+2)%3] = bbox.L.cell[(axis+2)%3]; |
210 F << "v " << v.x << " " << v.y << " " << v.z << endl; |
210 F << "v " << v.x << " " << v.y << " " << v.z << endl; |
211 v.cell[(axis+1)%3] = bbox.L.cell[(axis+1)%3]; |
211 v.cell[(axis+1)%3] = bbox.L.cell[(axis+1)%3]; |
212 v.cell[(axis+2)%3] = bbox.R.cell[(axis+2)%3]; |
212 v.cell[(axis+2)%3] = bbox.H.cell[(axis+2)%3]; |
213 F << "v " << v.x << " " << v.y << " " << v.z << endl; |
213 F << "v " << v.x << " " << v.y << " " << v.z << endl; |
214 v.cell[(axis+1)%3] = bbox.R.cell[(axis+1)%3]; |
214 v.cell[(axis+1)%3] = bbox.H.cell[(axis+1)%3]; |
215 v.cell[(axis+2)%3] = bbox.R.cell[(axis+2)%3]; |
215 v.cell[(axis+2)%3] = bbox.H.cell[(axis+2)%3]; |
216 F << "v " << v.x << " " << v.y << " " << v.z << endl; |
216 F << "v " << v.x << " " << v.y << " " << v.z << endl; |
217 v.cell[(axis+1)%3] = bbox.R.cell[(axis+1)%3]; |
217 v.cell[(axis+1)%3] = bbox.H.cell[(axis+1)%3]; |
218 v.cell[(axis+2)%3] = bbox.L.cell[(axis+2)%3]; |
218 v.cell[(axis+2)%3] = bbox.L.cell[(axis+2)%3]; |
219 F << "v " << v.x << " " << v.y << " " << v.z << endl; |
219 F << "v " << v.x << " " << v.y << " " << v.z << endl; |
220 F << "f " << f+1 << " " << f+2 << " " << f+3 << " " << f+4 << endl; |
220 F << "f " << f+1 << " " << f+2 << " " << f+3 << " " << f+4 << endl; |
221 f += 4; |
221 f += 4; |
222 #endif |
222 #endif |
236 children[1].addShape(sh->shape); |
236 children[1].addShape(sh->shape); |
237 continue; |
237 continue; |
238 } |
238 } |
239 if (state == 0) |
239 if (state == 0) |
240 { |
240 { |
241 if (sh->bbox.R.cell[axis] < split) |
241 if (sh->bbox.H.cell[axis] < split) |
242 { // left |
242 { // left |
243 children[0].addShape(sh->shape); |
243 children[0].addShape(sh->shape); |
244 } else |
244 } else |
245 if (sh->bbox.R.cell[axis] > split) |
245 if (sh->bbox.H.cell[axis] > split) |
246 { |
246 { |
247 if (sh->bbox.L.cell[axis] < split) |
247 if (sh->bbox.L.cell[axis] < split) |
248 { // both |
248 { // both |
249 children[0].addShape(sh->shape); |
249 children[0].addShape(sh->shape); |
250 children[1].addShape(sh->shape); |
250 children[1].addShape(sh->shape); |
252 { // right |
252 { // right |
253 children[1].addShape(sh->shape); |
253 children[1].addShape(sh->shape); |
254 state = 1; |
254 state = 1; |
255 } |
255 } |
256 } else |
256 } else |
257 { // R == split |
257 { // H == split |
258 if (sh->bbox.L.cell[axis] < split) |
258 if (sh->bbox.L.cell[axis] < split) |
259 { // left |
259 { // left |
260 children[0].addShape(sh->shape); |
260 children[0].addShape(sh->shape); |
261 } else |
261 } else |
262 { // contained |
262 { // contained |
263 if (split - bbox.L.cell[axis] < bbox.R.cell[axis] - split) |
263 if (split - bbox.L.cell[axis] < bbox.H.cell[axis] - split) |
264 { |
264 { |
265 // left subcell is smaller -> if not empty, put shape here |
265 // left subcell is smaller -> if not empty, put shape here |
266 if (lnum) |
266 if (lnum) |
267 children[0].addShape(sh->shape); |
267 children[0].addShape(sh->shape); |
268 else |
268 else |
404 nearest_distance = dist; |
404 nearest_distance = dist; |
405 return nearest_shape; |
405 return nearest_shape; |
406 } |
406 } |
407 |
407 |
408 /* pop from the stack */ |
408 /* pop from the stack */ |
|
409 delete enPt; |
409 enPt = exPt; /* the signed distance intervals are adjacent */ |
410 enPt = exPt; /* the signed distance intervals are adjacent */ |
410 |
411 |
411 /* retrieve the pointer to the next node, it is possible that ray traversal terminates */ |
412 /* retrieve the pointer to the next node, it is possible that ray traversal terminates */ |
412 node = enPt->node; |
413 node = enPt->node; |
413 |
414 |
414 // pop |
415 // pop |
415 exPt = st.top(); |
416 exPt = st.top(); |
416 st.pop(); |
417 st.pop(); |
417 } /* while */ |
418 } /* while */ |
|
419 |
|
420 delete enPt; |
418 |
421 |
419 /* ray leaves the scene */ |
422 /* ray leaves the scene */ |
420 return NULL; |
423 return NULL; |
421 } |
424 } |
422 |
425 |