76 setLeaf(); |
76 setLeaf(); |
77 return; |
77 return; |
78 } |
78 } |
79 |
79 |
80 // choose split axis |
80 // choose split axis |
81 axis = 0; |
81 /*axis = 0; |
82 if (bounds.h() > bounds.w() && bounds.h() > bounds.d()) |
82 if (bounds.h() > bounds.w() && bounds.h() > bounds.d()) |
83 axis = 1; |
83 axis = 1; |
84 if (bounds.d() > bounds.w() && bounds.d() > bounds.h()) |
84 if (bounds.d() > bounds.w() && bounds.d() > bounds.h()) |
85 axis = 2; |
85 axis = 2; |
86 |
86 */ |
87 // create sorted list of shape bounds (= find all posible splits) |
87 // create sorted list of shape bounds (= find all posible splits) |
88 vector<ShapeBound> edges[3]; |
88 vector<ShapeBound> edges[3]; |
89 ShapeList::iterator shape; |
89 ShapeList::iterator shape; |
90 for (shape = shapes->begin(); shape != shapes->end(); shape++) |
90 for (shape = shapes->begin(); shape != shapes->end(); shape++) |
91 { |
91 { |
92 BBox shapebounds = (*shape)->get_bbox(); |
92 BBox shapebounds = (*shape)->get_bbox(); |
93 // for (int ax = 0; ax < 3; ax++) |
93 for (int ax = 0; ax < 3; ax++) |
94 // { |
94 { |
95 edges[axis].push_back(ShapeBound(*shape, shapebounds.L[axis], 0)); |
95 edges[ax].push_back(ShapeBound(*shape, shapebounds.L[ax], 0)); |
96 edges[axis].push_back(ShapeBound(*shape, shapebounds.H[axis], 1)); |
96 edges[ax].push_back(ShapeBound(*shape, shapebounds.H[ax], 1)); |
97 // } |
97 } |
98 } |
98 } |
99 sort(edges[axis].begin(), edges[axis].end()); |
99 for (int ax = 0; ax < 3; ax++) |
|
100 sort(edges[ax].begin(), edges[ax].end()); |
100 |
101 |
101 // choose best split pos |
102 // choose best split pos |
102 const Float K = 1.4; // constant, K = cost of traversal / cost of ray-triangle intersection |
103 const Float K = 1.4; // constant, K = cost of traversal / cost of ray-triangle intersection |
103 Float SAV = (bounds.w()*bounds.h() + // surface area of node |
104 Float SAV = (bounds.w()*bounds.h() + // surface area of node |
104 bounds.w()*bounds.d() + bounds.h()*bounds.d()); |
105 bounds.w()*bounds.d() + bounds.h()*bounds.d()); |
105 Float cost = SAV * (K + shapes->size()); // initial cost = non-split cost |
106 Float cost = SAV * (K + shapes->size()); // initial cost = non-split cost |
106 BBox lbb = bounds; |
107 |
107 BBox rbb = bounds; |
108 vector<ShapeBound>::iterator edge, splitedge = edges[2].end(); |
108 |
109 for (int ax = 0; ax < 3; ax++) |
109 vector<ShapeBound>::iterator edge, splitedge = edges[axis].end(); |
110 { |
110 int lnum = 0, rnum = shapes->size(); |
111 int lnum = 0, rnum = shapes->size(); |
111 for (edge = edges[axis].begin(); edge != edges[axis].end(); edge++) |
112 BBox lbb = bounds; |
112 { |
113 BBox rbb = bounds; |
113 if (edge->end) |
114 for (edge = edges[ax].begin(); edge != edges[ax].end(); edge++) |
114 rnum--; |
|
115 |
|
116 // calculate SAH cost of this split |
|
117 lbb.H.cell[axis] = edge->pos; |
|
118 rbb.L.cell[axis] = edge->pos; |
|
119 Float SAL = (lbb.w()*lbb.h() + lbb.w()*lbb.d() + lbb.h()*lbb.d()); |
|
120 Float SAR = (rbb.w()*rbb.h() + rbb.w()*rbb.d() + rbb.h()*rbb.d()); |
|
121 Float splitcost = K*SAV + SAL*(K + lnum) + SAR*(K + rnum); |
|
122 |
|
123 if (splitcost < cost) |
|
124 { |
115 { |
125 splitedge = edge; |
116 if (edge->end) |
126 cost = splitcost; |
117 rnum--; |
127 split = edge->pos; |
118 |
|
119 // calculate SAH cost of this split |
|
120 lbb.H.cell[ax] = edge->pos; |
|
121 rbb.L.cell[ax] = edge->pos; |
|
122 Float SAL = (lbb.w()*lbb.h() + lbb.w()*lbb.d() + lbb.h()*lbb.d()); |
|
123 Float SAR = (rbb.w()*rbb.h() + rbb.w()*rbb.d() + rbb.h()*rbb.d()); |
|
124 Float splitcost = K*SAV + SAL*(K + lnum) + SAR*(K + rnum); |
|
125 |
|
126 if (splitcost < cost) |
|
127 { |
|
128 axis = ax; |
|
129 splitedge = edge; |
|
130 cost = splitcost; |
|
131 split = edge->pos; |
|
132 } |
|
133 |
|
134 if (!edge->end) |
|
135 lnum++; |
128 } |
136 } |
129 |
137 } |
130 if (!edge->end) |
138 |
131 lnum++; |
139 if (splitedge == edges[2].end()) |
132 } |
|
133 |
|
134 if (splitedge == edges[axis].end()) |
|
135 { |
140 { |
136 setLeaf(); |
141 setLeaf(); |
137 return; |
142 return; |
138 } |
143 } |
139 |
144 |
160 f += 4; |
165 f += 4; |
161 #endif |
166 #endif |
162 |
167 |
163 // split this node |
168 // split this node |
164 delete shapes; |
169 delete shapes; |
|
170 BBox lbb = bounds; |
|
171 BBox rbb = bounds; |
|
172 lbb.H.cell[axis] = split; |
|
173 rbb.L.cell[axis] = split; |
165 children = new KdNode[2]; |
174 children = new KdNode[2]; |
|
175 |
166 for (edge = edges[axis].begin(); edge != splitedge; edge++) |
176 for (edge = edges[axis].begin(); edge != splitedge; edge++) |
167 if (!edge->end) |
177 if (!edge->end && edge->shape->intersect_bbox(lbb)) |
168 children[0].addShape(edge->shape); |
178 children[0].addShape(edge->shape); |
169 for (edge = splitedge; edge < edges[axis].end(); edge++) |
179 for (edge = splitedge; edge < edges[axis].end(); edge++) |
170 if (edge->end) |
180 if (edge->end && edge->shape->intersect_bbox(rbb)) |
171 children[1].addShape(edge->shape); |
181 children[1].addShape(edge->shape); |
172 |
|
173 lbb.H.cell[axis] = split; |
|
174 rbb.L.cell[axis] = split; |
|
175 |
182 |
176 children[0].subdivide(lbb, maxdepth-1); |
183 children[0].subdivide(lbb, maxdepth-1); |
177 children[1].subdivide(rbb, maxdepth-1); |
184 children[1].subdivide(rbb, maxdepth-1); |
178 } |
185 } |
179 |
186 |