| 230 | } |
| 231 | |
| 232 | void LASkdtreeRectangles::build_recursive(LASkdtreeRectanglesNode* node, I32 plane, LASkdtreeRectangle curr_bb, my_rectangle_list* insertion_list, I32 unchanged) |
| 233 | { |
| 234 | // is list small enough? |
| 235 | if (insertion_list->size() <= 4) |
| 236 | { |
| 237 | node->list = insertion_list; |
| 238 | return; |
| 239 | } |
| 240 | |
| 241 | // did last 4 recursions not make list smaller? |
| 242 | if (unchanged >= 4) |
| 243 | { |
| 244 | node->list = insertion_list; |
| 245 | return; |
| 246 | } |
| 247 | |
| 248 | F64 split = (curr_bb.min[plane] + curr_bb.max[plane]) / 2; |
| 249 | |
| 250 | my_rectangle_list* list_left = new my_rectangle_list; |
| 251 | my_rectangle_list* list_right = new my_rectangle_list; |
| 252 | |
| 253 | my_rectangle_list::iterator list_element = insertion_list->begin(); |
| 254 | |
| 255 | U32 total = 0; |
| 256 | U32 total_left = 0; |
| 257 | U32 total_right = 0; |
| 258 | |
| 259 | while (TRUE) |
| 260 | { |
| 261 | if (list_element == insertion_list->end()) |
| 262 | { |
| 263 | break; |
| 264 | } |
| 265 | |
| 266 | LASkdtreeRectangle rectangle = (*list_element); |
| 267 | |
| 268 | total++; |
| 269 | |
| 270 | if (rectangle.min[plane] < split) |
| 271 | { |
| 272 | list_left->push_back(rectangle); |
| 273 | total_left++; |
| 274 | } |
| 275 | if (split <= rectangle.max[plane]) |
| 276 | { |
| 277 | list_right->push_back(rectangle); |
| 278 | total_right++; |
| 279 | } |
| 280 | |
| 281 | list_element++; |
| 282 | } |
| 283 | |
| 284 | // input list was divided into two output lists and no longer useful |
| 285 | |
| 286 | delete insertion_list; |
| 287 | |
| 288 | // split the bounding box |
| 289 | |