1. Coin3D
  2. Coin

Source

Coin / src / base / SbOctTree.cpp

Morten Eriksen a59180e 
Marius Kintel 3ba6b41 




























Morten Eriksen a59180e 

Morten Eriksen f4e00cb 









Tom Fredrik Blen… 9244e9d 


Morten Eriksen f585669 
Morten Eriksen 4de3b3b 


Morten Eriksen 8744c49 
Morten Eriksen 4de3b3b 
Morten Eriksen f4e00cb 
Morten Eriksen 4de3b3b 


Morten Eriksen e89bc94 
Morten Eriksen d28d892 
Morten Eriksen e89bc94 
Morten Eriksen c548bb9 
Morten Eriksen e89bc94 


Morten Eriksen 1b70596 
Morten Eriksen d28d892 


Morten Eriksen f585669 
Morten Eriksen 1b70596 
Morten Eriksen d28d892 

Morten Eriksen f585669 
Morten Eriksen d28d892 


Morten Eriksen f585669 

Morten Eriksen d28d892 


Morten Eriksen f585669 

Morten Eriksen 1b70596 
Morten Eriksen c548bb9 
Morten Eriksen f4e00cb 

Morten Eriksen 4de3b3b 



Morten Eriksen c548bb9 
Morten Eriksen 4de3b3b 


Morten Eriksen c548bb9 
Morten Eriksen 1b70596 

Morten Eriksen 4de3b3b 





Morten Eriksen c548bb9 

Morten Eriksen 4de3b3b 




Morten Eriksen 1b70596 
Morten Eriksen 4de3b3b 
Morten Eriksen c548bb9 





Morten Eriksen 4de3b3b 


Morten Eriksen 1b70596 
Morten Eriksen 4de3b3b 

Morten Eriksen c548bb9 




Morten Eriksen 4de3b3b 


Morten Eriksen 1b70596 

Morten Eriksen 4de3b3b 
Morten Eriksen 1b70596 

Morten Eriksen 4de3b3b 
Tom Fredrik Blen… 9244e9d 
Morten Eriksen c548bb9 
Morten Eriksen 4de3b3b 
Morten Eriksen c548bb9 
Morten Eriksen 1b70596 
Morten Eriksen 4de3b3b 




Morten Eriksen f4e00cb 

Morten Eriksen 4de3b3b 


Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 
Morten Eriksen c548bb9 

Morten Eriksen 1b70596 
Morten Eriksen e89bc94 
Morten Eriksen c548bb9 
Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 
Morten Eriksen c548bb9 

Morten Eriksen 1b70596 
Morten Eriksen c548bb9 


Morten Eriksen 1b70596 
Morten Eriksen c548bb9 


Morten Eriksen 1b70596 
Morten Eriksen 4de3b3b 
Morten Eriksen c548bb9 


Morten Eriksen 1b70596 
Morten Eriksen c548bb9 
Morten Eriksen e89bc94 


Peder Blekken a5ab033 
Morten Eriksen 4de3b3b 
Morten Eriksen f585669 
Morten Eriksen 18212d9 

Morten Eriksen f585669 
Morten Eriksen c548bb9 
Morten Eriksen e89bc94 

Morten Eriksen c548bb9 
Morten Eriksen 1b70596 
Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 

Morten Eriksen f585669 






Morten Eriksen 18212d9 
Morten Eriksen f585669 






Peder Blekken a5ab033 
Morten Eriksen e89bc94 
Peder Blekken a5ab033 
Morten Eriksen f585669 

Peder Blekken a5ab033 
Morten Eriksen f585669 

Morten Eriksen e89bc94 

Morten Eriksen f585669 






Morten Eriksen 18212d9 
Morten Eriksen f585669 
Morten Eriksen e89bc94 
Peder Blekken a5ab033 



Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 


Morten Eriksen 4de3b3b 

Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 

Morten Eriksen 4de3b3b 



Morten Eriksen 18212d9 
Morten Eriksen 4de3b3b 




Morten Eriksen c548bb9 
Morten Eriksen 1b70596 
Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 
Morten Eriksen 18212d9 
Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 

Morten Eriksen 4de3b3b 


Peder Blekken a5ab033 


Morten Eriksen e89bc94 

Morten Eriksen 7322fc3 



Morten Eriksen 4de3b3b 






Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 

Morten Eriksen f585669 
Morten Eriksen e89bc94 

Morten Eriksen 4de3b3b 




Morten Eriksen f585669 
Morten Eriksen 4de3b3b 
Morten Eriksen c548bb9 

Morten Eriksen 4de3b3b 





Morten Eriksen 1b70596 



Morten Eriksen 4de3b3b 
Morten Eriksen 18212d9 
Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 


Morten Eriksen 4de3b3b 






Morten Eriksen c548bb9 
Morten Eriksen 1b70596 



Morten Eriksen 4de3b3b 




Morten Eriksen c548bb9 
Morten Eriksen 1b70596 



Morten Eriksen 4de3b3b 
Morten Eriksen 18212d9 
Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 
Morten Eriksen c548bb9 
Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 






Morten Eriksen 1b70596 



Morten Eriksen 4de3b3b 




Morten Eriksen c548bb9 
Morten Eriksen 1b70596 



Morten Eriksen 4de3b3b 
Morten Eriksen 18212d9 
Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 
Morten Eriksen c548bb9 
Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 




Morten Eriksen 1b70596 
Morten Eriksen c548bb9 
Morten Eriksen 1b70596 



Morten Eriksen 4de3b3b 




Morten Eriksen c548bb9 
Morten Eriksen 4de3b3b 
Morten Eriksen 1b70596 



Morten Eriksen 4de3b3b 
Morten Eriksen 18212d9 
Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 


Morten Eriksen 4de3b3b 






Morten Eriksen 1b70596 




Morten Eriksen 4de3b3b 




Morten Eriksen c548bb9 
Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 

Morten Eriksen c548bb9 
Morten Eriksen 4de3b3b 

Morten Eriksen c548bb9 




Morten Eriksen 4de3b3b 


Morten Eriksen c548bb9 
Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 

Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 


Morten Eriksen c548bb9 
Morten Eriksen f585669 
Morten Eriksen 4de3b3b 



Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 


Morten Eriksen f585669 




Morten Eriksen e89bc94 
Morten Eriksen 7322fc3 
Morten Eriksen e89bc94 






Morten Eriksen 7322fc3 
Morten Eriksen e89bc94 


Morten Eriksen f585669 
Morten Eriksen 29089be 
Morten Eriksen 7322fc3 
Morten Eriksen 4de3b3b 

Morten Eriksen f4e00cb 
Morten Eriksen 4de3b3b 


Morten Eriksen 1b70596 


Morten Eriksen c548bb9 
Morten Eriksen e89bc94 
Morten Eriksen 1b70596 

Morten Eriksen 4de3b3b 











Morten Eriksen 1b70596 

Morten Eriksen 4de3b3b 

Morten Eriksen 1b70596 
Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 




Morten Eriksen c548bb9 
Morten Eriksen 4de3b3b 

Morten Eriksen 954c0ac 
















Morten Eriksen 8744c49 









Morten Eriksen e89bc94 
Morten Eriksen f585669 

Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 

Morten Eriksen 29d9ecb 
Morten Eriksen 1b70596 
Morten Eriksen 29d9ecb 
Morten Eriksen 4de3b3b 
Morten Eriksen c548bb9 
Morten Eriksen 4de3b3b 

Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 

Morten Eriksen 29d9ecb 
Morten Eriksen 1b70596 

Morten Eriksen 29d9ecb 
Morten Eriksen 1b70596 



Morten Eriksen 954c0ac 

Morten Eriksen 4de3b3b 

Morten Eriksen 1b70596 


Morten Eriksen c548bb9 
Morten Eriksen 954c0ac 













Morten Eriksen 4de3b3b 
Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 



Morten Eriksen 1b70596 




Morten Eriksen 954c0ac 

Morten Eriksen 4de3b3b 
Morten Eriksen c548bb9 
Morten Eriksen 1b70596 

Morten Eriksen 4de3b3b 

Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 



Morten Eriksen 1b70596 




Morten Eriksen 954c0ac 

Morten Eriksen 4de3b3b 
Morten Eriksen c548bb9 
Morten Eriksen 1b70596 


Morten Eriksen 4de3b3b 

Morten Eriksen e89bc94 
Morten Eriksen 4de3b3b 

Morten Eriksen 29d9ecb 
Morten Eriksen 1b70596 







Morten Eriksen 29d9ecb 
Morten Eriksen 954c0ac 

Morten Eriksen 4de3b3b 
Morten Eriksen c548bb9 
Morten Eriksen 4de3b3b 
Morten Eriksen 1b70596 


Morten Eriksen 4de3b3b 

Morten Eriksen e89bc94 
Morten Eriksen 1b70596 
Morten Eriksen 4de3b3b 

Morten Eriksen 29d9ecb 
Morten Eriksen d28d892 
Morten Eriksen 1b70596 
Morten Eriksen 29d9ecb 
Morten Eriksen 1b70596 
Morten Eriksen d28d892 
Morten Eriksen 1b70596 
Morten Eriksen d28d892 
Morten Eriksen e89bc94 
Morten Eriksen d28d892 
Peder Blekken a5ab033 




Morten Eriksen e89bc94 
Peder Blekken a5ab033 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
/**************************************************************************\
 * Copyright (c) Kongsberg Oil & Gas Technologies AS
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the copyright holder nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
\**************************************************************************/

/*!
  \class SbOctTree SbOctTree.h Inventor/SbOctTree.h
  \brief The SbOctTree class defines a generic oct tree for fast geometry searches.
  \ingroup base

  \COIN_CLASS_EXTENSION
*/

// *************************************************************************

#include <cassert>
#include <cfloat>
#include <cstddef>

#include <Inventor/SbOctTree.h>
#include <Inventor/SbSphere.h>
#include <Inventor/SbPlane.h>
#include <Inventor/errors/SoDebugError.h>

// *************************************************************************

/*!
  \struct SbOctTreeFuncs SbOctTree.h Inventor/SbOctTree.h

  The SbOctTreeFuncs struct is used to specify callback functions for
  working with items in an SbOctTree.

  The only function pointer that \e must be set up is \c
  insideboxfunc. The other functions must be set if you intend to use
  the corresponding find methods in SbOctTree.
*/

/*!
  \var SbOctTreeFuncs::ptinsidefunc
  Should return whether a point is inside item.
*/
/*!
  \var SbOctTreeFuncs::insideboxfunc
  Should return whether item is either fully or partly inside a box.
 */
/*!
  \var SbOctTreeFuncs::insidespherefunc
  Should return whether item is either fully or partly inside a
  sphere.
 */
/*!
  \var SbOctTreeFuncs::insideplanesfunc
  Should return whether item is either fully or partly inside a set of
  planes.
*/

// *************************************************************************

//
// got to have unique intersection funcs, therefore the standard
// Inventor intersection functions won't do. E.g. SbBox3f::pointInside()
// will return TRUE for all eight child-boxes if the center point of the
// parent box is tested, which is correct, but not really usable for an
// oct tree.
//

static SbBool
intersect_box_sphere(const SbBox3f & box,
                     const SbSphere & sphere)
{
  const SbVec3f &C = sphere.getCenter();
  const SbVec3f &Bmin = box.getMin();
  const SbVec3f &Bmax = box.getMax();
  float dmin = 0;
  for (int i = 0; i < 3; i++) {
    if (C[i] < Bmin[i]) dmin += SbSqr(C[i] - Bmin[i]);
    else if (C[i] > Bmax[i]) dmin += SbSqr(C[i] - Bmax[i]);
  }
  return (dmin <= SbSqr(sphere.getRadius()));
}

static SbBool
intersect_box_box(const SbBox3f & box1, const SbBox3f & box2)
{
  return ! (box1.getMin()[0] >= box2.getMax()[0] ||
            box1.getMax()[0] < box2.getMin()[0] ||
            box1.getMin()[1] >= box2.getMax()[1] ||
            box1.getMax()[1] < box2.getMin()[1] ||
            box1.getMin()[2] >= box2.getMax()[2] ||
            box1.getMax()[2] < box2.getMin()[2]);
}

static SbBool
point_inside_box(const SbVec3f & pt, const SbBox3f & box)
{
  return ! (pt[0] < box.getMin()[0] ||
            pt[0] >= box.getMax()[0] ||
            pt[1] < box.getMin()[1] ||
            pt[1] >= box.getMax()[1] ||
            pt[2] < box.getMin()[2] ||
            pt[2] >= box.getMax()[2]);
}

static SbBool
box_inside_planes(const SbBox3f & box, const SbPlane * const planes,
                  const int numplanes)
{
  // Uses box "radius" for speed.
  // FIXME: consider just checking all 8 points of the box. pederb, 20000811
  SbVec3f size = (box.getMax() - box.getMin()) * 0.5f;
  float radius = static_cast<float>(sqrt(size[0]*size[0] + size[1]*size[1] + size[2]*size[2]));

  SbVec3f center = (box.getMin() + box.getMax()) * 0.5f;

  for (int i = 0; i < numplanes; i++) {
    if (planes[i].getDistance(center) < -radius) return FALSE;
  }
  return TRUE;
}

// *************************************************************************

class SbOctTreeNode
{
public:
  SbOctTreeNode(const SbBox3f & b);
  ~SbOctTreeNode();

  void addItem(void * const item,
               const SbOctTreeFuncs & itemfuncs,
               const int maxitems);
  void removeItem(void * const item,
                  const SbOctTreeFuncs & itemfuncs);
  void findItems(const SbVec3f &pos,
                 SbList <void*> &destarray,
                 const SbOctTreeFuncs &itemfuncs,
                 const SbBool removeduplicates) const;
  void findItems(const SbBox3f &box,
                 SbList <void*> &destarray,
                 const SbOctTreeFuncs &itemfuncs,
                 const SbBool removeduplicates) const;
  void findItems(const SbSphere &sphere,
                 SbList <void*> &destarray,
                 const SbOctTreeFuncs &itemfuncs,
                 const SbBool removeduplicates) const;
  void findItems(const SbPlane * const planes,
                 const int numPlanes,
                 SbList <void*> &destarray,
                 const SbOctTreeFuncs &itemfuncs,
                 const SbBool removeduplicates) const;

  const SbBox3f & getBBox(void) const { return this->nodesize; }

  void debugTree(FILE *fp, const int indent) const;

private:
  SbBool isLeaf(void) const { return this->children[0] == NULL; }
  SbBool isGroup(void) const { return ! this->isLeaf(); }

  unsigned int totalNumberOfItems(void) const;

  static void split3Way(const SbBox3f & box, SbBox3f * destarray);
  SbBool splitNode(const SbOctTreeFuncs & funcs);

  SbOctTreeNode * children[8];
  SbList <void*> items;
  SbBox3f nodesize;
};

// Returns all items of the node, including all items in child nodes
// if we're not a leaf node.
unsigned int
SbOctTreeNode::totalNumberOfItems(void) const
{
  unsigned int nr = this->items.getLength();

  if (this->isGroup()) {
    for (int i = 0; i < 8; i++) {
      nr += this->children[i]->totalNumberOfItems();
    }
  }
  return nr;
}

void 
SbOctTreeNode::debugTree(FILE *fp, const int indent) const
{
  (void)fprintf(fp, "%02d", indent - 1);

  int i;
  for (i = 0; i < indent; i++) { (void)fprintf(fp, "  "); }

  const SbVec3f & vmin = this->nodesize.getMin();
  const SbVec3f & vmax = this->nodesize.getMax();

  (void)fprintf(fp, "%s, %d items, ",
                this->isLeaf() ? "Leaf" : "Group", this->totalNumberOfItems());
  (void)fprintf(fp, "box==<%.2f, %.2f, %.2f>-<%.2f, %.2f, %.2f>",
                vmin[0], vmin[1], vmin[2], vmax[0], vmax[1], vmax[2]);
  (void)fprintf(fp, "\n");

  if (this->isGroup()) {
    for (i = 0; i < 8; i++) {
      this->children[i]->debugTree(fp, indent+1);
    }
  }
}

static void
add_to_array(SbList<void *> & array, void * ptr)
{
  // FIXME: this is rather awful, resulting in n^2 algorithm time.
  // Should change to using the array as a sorted set. 20050512 mortene.
  if (array.find(ptr) == -1) { array.append(ptr); }
}

SbOctTreeNode::SbOctTreeNode(const SbBox3f & b)
{
  for (int i = 0; i < 8; i++) {
    this->children[i] = NULL;
  }
  this->nodesize = b;
}

SbOctTreeNode::~SbOctTreeNode()
{
  if (this->isGroup()) {
    for (int i = 0; i < 8; i++) delete children[i];
  }
}

void
SbOctTreeNode::addItem(void * const item,
                       const SbOctTreeFuncs & itemfuncs,
                       const int maxitems)
{
  if (this->isGroup()) { // node has been split
    for (int i = 0; i < 8; i++) {
      if (itemfuncs.insideboxfunc(item, this->children[i]->nodesize)) {
        this->children[i]->addItem(item, itemfuncs, maxitems);
      }
    }
  }
  else if (this->items.getLength() >= maxitems) {
    // avoid trying a split too often by using a modulo
    if ((this->items.getLength() % (maxitems+1) == maxitems) &&
        this->splitNode(itemfuncs)) {
      this->addItem(item, itemfuncs, maxitems);
    }
    else {
      this->items.append(item);
    }
  }
  else {
    this->items.append(item);
  }
}

void
SbOctTreeNode::removeItem(void * const item, const SbOctTreeFuncs & itemfuncs)
{
  if (children[0]) {
    for (int i = 0; i < 8; i++) {
      if (itemfuncs.insideboxfunc(item, this->children[i]->nodesize)) {
        this->children[i]->removeItem(item, itemfuncs);
      }
    }
  }
  else {
    int n = this->items.getLength();
    for (int i = 0; i < n; i++) {
      if (this->items[i] == item) {
        this->items.removeFast(i);
        n--;
      }
    }
  }
}

void
SbOctTreeNode::findItems(const SbVec3f & pos,
                         SbList <void*> & destarray,
                         const SbOctTreeFuncs & itemfuncs,
                         const SbBool removeduplicates) const
{
  if (this->isGroup()) {
    for (int i = 0; i < 8; i++) {
      if (point_inside_box(pos, this->children[i]->nodesize)) {
        this->children[i]->findItems(pos, destarray,
                                     itemfuncs, removeduplicates);
      }
    }
  }
  else {
    int n = this->items.getLength();
    for (int i = 0; i < n; i++) {
      void *item = this->items[i];
      if (itemfuncs.ptinsidefunc(item, pos)) {
        if (removeduplicates)
          add_to_array(destarray, item);
        else
          destarray.append(item);
      }
    }
  }
}

void
SbOctTreeNode::findItems(const SbBox3f & box,
                         SbList <void*> & destarray,
                         const SbOctTreeFuncs & itemfuncs,
                         const SbBool removeduplicates) const
{
  if (this->isGroup()) {
    for (int i = 0; i < 8; i++) {
      if (intersect_box_box(box, this->children[i]->nodesize))
        this->children[i]->findItems(box, destarray,
                                     itemfuncs, removeduplicates);
    }
  }
  else {
    int n = this->items.getLength();
    for (int i = 0; i < n; i++) {
      void *item = this->items[i];
      if (itemfuncs.insideboxfunc(item, box)) {
        if (removeduplicates)
          add_to_array(destarray, item);
        else
          destarray.append(item);
      }
    }
  }
}

void
SbOctTreeNode::findItems(const SbSphere & sphere,
                         SbList <void*> & destarray,
                         const SbOctTreeFuncs & itemfuncs,
                         const SbBool removeduplicates) const
{
  if (this->isGroup()) {
    for (int i = 0; i < 8; i++) {
      if (intersect_box_sphere(this->children[i]->nodesize, sphere))
        this->children[i]->findItems(sphere, destarray,
                                     itemfuncs, removeduplicates);
    }
  }
  else {
    int n = this->items.getLength();
    for (int i = 0; i < n; i++) {
      void * item = this->items[i];
      if (itemfuncs.insidespherefunc(item, sphere)) {
        if (removeduplicates)
          add_to_array(destarray, item);
        else
          destarray.append(item);
      }
    }
  }
}

void
SbOctTreeNode::findItems(const SbPlane * const planes,
                         const int numplanes,
                         SbList <void*> & destarray,
                         const SbOctTreeFuncs & itemfuncs,
                         const SbBool removeduplicates) const
{
  if (this->isGroup()) {
    for (int i = 0; i < 8; i++) {
      if (box_inside_planes(this->children[i]->nodesize, planes, numplanes)) {
        this->children[i]->findItems(planes, numplanes,
                                     destarray, itemfuncs, removeduplicates);
      }
    }
  }
  else {
    int n = this->items.getLength();
    for (int i = 0; i < n; i++) {
      void *item = this->items[i];
      if (itemfuncs.insideplanesfunc(item, planes, numplanes)) {
        if (removeduplicates)
          add_to_array(destarray, item);
        else
          destarray.append(item);
      }
    }
  }
}

void
SbOctTreeNode::split3Way(const SbBox3f & box, SbBox3f * dest)
{
  SbVec3f mid = (box.getMin() + box.getMax()) * 0.5f;

  for (int i = 0; i < 8; i++) {
    dest[i].setBounds((i & 4) ? box.getMin()[0] : mid[0],
                      (i & 2) ? box.getMin()[1] : mid[1],
                      (i & 1) ? box.getMin()[2] : mid[2],
                      (i & 4) ? mid[0] : box.getMax()[0],
                      (i & 2) ? mid[1] : box.getMax()[1],
                      (i & 1) ? mid[2] : box.getMax()[2]);
  }
}

SbBool
SbOctTreeNode::splitNode(const SbOctTreeFuncs & itemfuncs)
{
  SbBox3f childbox[8];
  SbOctTreeNode::split3Way(this->nodesize, childbox);
  int i;
  for (i = 0; i < 8; i++) {
    this->children[i] = new SbOctTreeNode(childbox[i]);
  }

  const int n = this->items.getLength();
  for (i = 0; i < n; i++) {
    void *item = this->items[i];
    for (int j = 0; j < 8; j++) {
      if (itemfuncs.insideboxfunc(item, childbox[j])) {
        this->children[j]->items.append(item);
      }
    }
  }

  // Check to see if one or more of the new nodes contains *all* items
  // from the parent node (i.e. this node). If so, the split won't
  // gain us any in processing time (it will likely be hurtful), so
  // decide against splitting.

  for (i = 0; i < 8; i++) {
    if (this->children[i]->items.getLength() == n) {
      for (int j = 0; j < 8; j++) {
        delete this->children[j];
        this->children[j] = NULL;
      }
      return FALSE;
    }
  }

  // Box was indeed split, we're now a group node, so truncate our
  // list of items and carry on with new tree structure.

  this->items.truncate(0, TRUE);
  return TRUE;
}

// *************************************************************************

/*!
  Constructor.
*/
SbOctTree::SbOctTree(const SbBox3f & bbox,
                     const SbOctTreeFuncs & itemfuncs,
                     const int maxitems)
  : topnode(new SbOctTreeNode(bbox)),
    itemfuncs(itemfuncs),
    maxitemspernode(maxitems)
{
}

/*!
  Destructor.
*/
SbOctTree::~SbOctTree()
{
  delete this->topnode;
}

/*!
  Restores this oct tree to an empty oct tree. The bounding
  box will still be the same though.
*/
void
SbOctTree::clear(void)
{
  SbBox3f bbox = this->topnode->getBBox();
  delete this->topnode;
  this->topnode = new SbOctTreeNode(bbox);
}

/*!
  Adds an item to this oct tree.
*/
void
SbOctTree::addItem(void * const item)
{
  // Note that the assert() below can hit due to floating point
  // inaccuracies.
  //
  // When that happens, an easy and fairly decent fix is usually to
  // add a bit of slack on the caller side to the input bbox argument
  // to SbOctTree::SbOctTree().

  // FIXME: a better solution would be to not force an static bbox
  // upon the SbOctTree through its constructor, but let it
  // dynamically expand / re-structure itself as items are added.
  //
  // An easy, but a bit inefficient, way to do that would be to simply
  // store a copy of all items in the octtree structure, destruct it,
  // restore a new top-level node, and then re-add all items to let a
  // new octtree structure build itself.
  //
  // 20050512 mortene.
#if COIN_DEBUG && 0 // debug
  const SbBox3f & b = this->topnode->getBBox();
  if (!this->itemfuncs.insideboxfunc(item, b)) {
    const SbVec3f & bmin = b.getMin();
    const SbVec3f & bmax = b.getMax();
    SoDebugError::post("SbOctTree::addItem",
                       "tree bbox==<%f, %f, %f>, <%f, %f, %f>",
                       bmin[0], bmin[1], bmin[2], bmax[0], bmax[1], bmax[2]);
  }
#endif // debug
  assert(this->itemfuncs.insideboxfunc(item, this->topnode->getBBox()) &&
         "bbox of item outside the octtree top-level bbox");

  this->topnode->addItem(item, this->itemfuncs, this->maxitemspernode);
}

/*!
  Removes the item from the octtree. The octtree will not be
  modified/simplified even when all items are removed.
*/
void
SbOctTree::removeItem(void * const item)
{
  this->topnode->removeItem(item, this->itemfuncs);
}

/*!
  Finds all items which contains the point \a pos. Items are
  returned in \a destarray.

  If \a removeduplicates is TRUE (the default), \a destarray will not
  contain duplicate items. This is not an optimized process, so if
  you're looking for speed you should set this to FALSE and do
  your own postprocessing of the array of returned items.

  \DANGEROUS_ALLOC_RETURN
*/
void
SbOctTree::findItems(const SbVec3f & pos,
                     SbList <void*> & destarray,
                     const SbBool removeduplicates) const
{
  // FIXME: passing in an SbList is dangerous under MS Windows, as
  // allocation and deallocation can then happen on different
  // C-library's heaps. The other findItems() functions below have the
  // same problem. 20050512 mortene.

  // FIXME: should be straightforward to drop the removeduplicates
  // argument -- it's a hack. We just need to optimize the
  // add_to_array() function above to keep a _sorted_ array.
  //
  // This also goes for the other findItems() functions below, of
  // course.
  //
  // 20050512 mortene.

  assert(this->itemfuncs.ptinsidefunc);
  topnode->findItems(pos, destarray, this->itemfuncs, removeduplicates);
}

/*!
  Finds all items inside \a box. Items are returned in \a destarray.

  If \a removeduplicates is TRUE (the default), \a destarray will not
  contain duplicate items. This is not an optimized process, so if
  you're looking for speed you should set this to FALSE and do
  your own postprocessing of the array of returned items.

  \DANGEROUS_ALLOC_RETURN
*/
void
SbOctTree::findItems(const SbBox3f & box, SbList <void*> & destarray,
                     const SbBool removeduplicates) const
{
  assert(this->itemfuncs.insideboxfunc);
  this->topnode->findItems(box, destarray, this->itemfuncs, removeduplicates);
}

/*!
  Finds all items inside \a sphere. Items are returned in \a destarray.

  If \a removeduplicates is TRUE (the default), \a destarray will not
  contain duplicate items. This is not an optimized process, so if
  you're looking for speed you should set this to FALSE and do
  your own postprocessing of the array of returned items.

  \DANGEROUS_ALLOC_RETURN
*/
void
SbOctTree::findItems(const SbSphere & sphere,
                     SbList <void*> & destarray,
                     const SbBool removeduplicates) const
{
  assert(this->itemfuncs.insidespherefunc);
  this->topnode->findItems(sphere, destarray, this->itemfuncs, removeduplicates);
}

/*!
  Finds all items inside \a planes. The method
  SbPlane::isInHalfSpace() should be used, and only items which are
  (partly) inside \e all planes are returned. Items are returned in \a
  destarray.

  If \a removeduplicates is TRUE (the default), \a destarray will not
  contain duplicate items. This is not an optimized process, so if
  you're looking for speed you should set this to FALSE and do
  your own postprocessing of the array of returned items.

  \DANGEROUS_ALLOC_RETURN
*/
void
SbOctTree::findItems(const SbPlane * const planes,
                     const int numplanes,
                     SbList <void*> & destarray,
                     const SbBool removeduplicates) const
{
  assert(this->itemfuncs.insideplanesfunc);
  this->topnode->findItems(planes, numplanes, destarray, this->itemfuncs,
                           removeduplicates);
}

/*!
  Returns a bounding box enclosing all the elements in the tree.
  This is just the same bounding box which was supplied to the
  constructor.
*/
const SbBox3f &
SbOctTree::getBoundingBox(void) const
{
  return this->topnode->getBBox();
}

void 
SbOctTree::debugTree(FILE * fp)
{
  fprintf(fp, "Oct Tree:\n");
  if (this->topnode) { this->topnode->debugTree(fp, 1); }
}