1 /*****************************************************************************
2 * bsphere.cpp
3 *
4 * This module implements the bounding sphere calculations.
5 *
6 * from Persistence of Vision(tm) Ray Tracer version 3.6.
7 * Copyright 1991-2003 Persistence of Vision Team
8 * Copyright 2003-2004 Persistence of Vision Raytracer Pty. Ltd.
9 *---------------------------------------------------------------------------
10 * NOTICE: This source code file is provided so that users may experiment
11 * with enhancements to POV-Ray and to port the software to platforms other
12 * than those supported by the POV-Ray developers. There are strict rules
13 * regarding how you are permitted to use this file. These rules are contained
14 * in the distribution and derivative versions licenses which should have been
15 * provided with this file.
16 *
17 * These licences may be found online, linked from the end-user license
18 * agreement that is located at http://www.povray.org/povlegal.html
19 *---------------------------------------------------------------------------
20 * This program is based on the popular DKB raytracer version 2.12.
21 * DKBTrace was originally written by David K. Buck.
22 * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
23 *---------------------------------------------------------------------------
24 *
25 *===========================================================================
26 * This file is part of MegaPOV, a modified and unofficial version of POV-Ray
27 * For more information on MegaPOV visit our website:
28 * http://megapov.inetart.net/
29 *===========================================================================
30 *
31 * $RCSfile: bsphere.cpp,v $
32 * $Revision: 1.12 $
33 * $Author: chris $
34 *
35 *****************************************************************************/
36
37 #include "frame.h"
38 #include "vector.h"
39 #include "bsphere.h"
40 #include "povray.h"
41
42 #include <algorithm>
43
44 BEGIN_POV_NAMESPACE
45
46 /*****************************************************************************
47 * Local preprocessor defines
48 ******************************************************************************/
49
50 const int BRANCHING_FACTOR = 4;
51
52
53
54 /*****************************************************************************
55 * Local typedefs
56 ******************************************************************************/
57
58
59
60 /*****************************************************************************
61 * Local variables
62 ******************************************************************************/
63
64 static int maxelements, Axis; // GLOBAL VARIABLE
65
66
67
68 /*****************************************************************************
69 * Static functions
70 ******************************************************************************/
71
72 static void merge_spheres (VECTOR C, DBL *r, VECTOR C1, DBL r1, VECTOR C2, DBL r2);
73 static void recompute_bound (BSPHERE_TREE *Node);
74 static int CDECL comp_elements (const void *in_a, const void *in_b);
75
76 /*****************************************************************************
77 *
78 * FUNCTION
79 *
80 * merge_spheres
81 *
82 * INPUT
83 *
84 * C, r - Center and radius^2 of new sphere
85 * C1, r1, C2, r2 - Centers and radii^2 of spheres to merge
86 *
87 * OUTPUT
88 *
89 * C, r
90 *
91 * RETURNS
92 *
93 * AUTHOR
94 *
95 * Dieter Bayer
96 *
97 * DESCRIPTION
98 *
99 * Calculate a sphere that encloses two given spheres.
100 *
101 * CHANGES
102 *
103 * Jul 1994 : Creation.
104 *
105 * Oct 1994 : Added test for enclosed spheres. Calculate optimal sphere. [DB]
106 *
107 ******************************************************************************/
108
merge_spheres(VECTOR C,DBL * r,VECTOR C1,DBL r1,VECTOR C2,DBL r2)109 static void merge_spheres(VECTOR C, DBL *r, VECTOR C1, DBL r1, VECTOR C2, DBL r2)
110 {
111 DBL l, r1r, r2r, k1, k2;
112 VECTOR D;
113
114 VSub(D, C1, C2);
115
116 VLength(l, D);
117
118 /* Check if one sphere encloses the other. */
119
120 r1r = sqrt(r1);
121 r2r = sqrt(r2);
122
123 if (l + r1r <= r2r)
124 {
125 Assign_Vector(C, C2);
126
127 *r = r2;
128
129 return;
130 }
131
132 if (l + r2r <= r1r)
133 {
134 Assign_Vector(C, C1);
135
136 *r = r1;
137
138 return;
139 }
140
141 k1 = (1.0 + (r1r - r2r) / l) / 2.0;
142 k2 = (1.0 + (r2r - r1r) / l) / 2.0;
143
144 VLinComb2(C, k1, C1, k2, C2);
145
146 *r = Sqr((l + r1r + r2r) / 2.0);
147 }
148
149
150
151 /*****************************************************************************
152 *
153 * FUNCTION
154 *
155 * recompute_bound
156 *
157 * INPUT
158 *
159 * Node - Pointer to node
160 *
161 * OUTPUT
162 *
163 * Node
164 *
165 * RETURNS
166 *
167 * AUTHOR
168 *
169 * Dieter Bayer
170 *
171 * DESCRIPTION
172 *
173 * Recompute the bounding sphere of a given node in the bounding hierarchy,
174 * i. e. find the bounding sphere that encloses the bounding spheres
175 * of all nodes.
176 *
177 * NOTE: The sphere found is probably not the tightest sphere possible!
178 *
179 * CHANGES
180 *
181 * Jul 1994 : Creation.
182 *
183 * Oct 1994 : Improved bounding sphere calculation. [DB]
184 *
185 ******************************************************************************/
186
recompute_bound(BSPHERE_TREE * Node)187 static void recompute_bound(BSPHERE_TREE *Node)
188 {
189 short i;
190 DBL r2;
191 VECTOR C;
192
193 Assign_Vector(C, Node->Node[0]->C);
194
195 r2 = Node->Node[0]->r2;
196
197 for (i = 1; i < Node->Entries; i++)
198 {
199 merge_spheres(C, &r2, C, r2, Node->Node[i]->C, Node->Node[i]->r2);
200 }
201
202 Assign_Vector(Node->C, C);
203
204 Node->r2 = r2;
205 }
206
207
208
209 /*****************************************************************************
210 *
211 * FUNCTION
212 *
213 * comp_elements
214 *
215 * INPUT
216 *
217 * in_a, in_b - elements to compare
218 *
219 * OUTPUT
220 *
221 * RETURNS
222 *
223 * int - result of comparison
224 *
225 * AUTHOR
226 *
227 * Dieter Bayer
228 *
229 * DESCRIPTION
230 *
231 * -
232 *
233 * CHANGES
234 *
235 * Oct 1994 : Creation. (Derived from the bounding slab creation code)
236 *
237 ******************************************************************************/
238
comp_elements(const void * in_a,const void * in_b)239 static int CDECL comp_elements(const void *in_a, const void *in_b)
240 {
241 DBL am, bm;
242
243 am = (*(BSPHERE_TREE **)in_a)->C[Axis];
244 bm = (*(BSPHERE_TREE **)in_b)->C[Axis];
245
246 if (am < bm - EPSILON)
247 {
248 return (-1);
249 }
250 else
251 {
252 if (am > bm + EPSILON)
253 {
254 return (1);
255 }
256 else
257 {
258 return (0);
259 }
260 }
261 }
262
263
264
265 /*****************************************************************************
266 *
267 * FUNCTION
268 *
269 * find_axis
270 *
271 * INPUT
272 *
273 * OUTPUT
274 *
275 * RETURNS
276 *
277 * AUTHOR
278 *
279 * Dieter Bayer
280 *
281 * DESCRIPTION
282 *
283 * -
284 *
285 * CHANGES
286 *
287 * Oct 1994 : Creation. (Derived from the bounding slab creation code)
288 *
289 ******************************************************************************/
290
find_axis(BSPHERE_TREE ** Elements,int first,int last)291 static int find_axis(BSPHERE_TREE **Elements, int first, int last)
292 {
293 int which = X;
294 int i;
295 DBL e, d = - BOUND_HUGE;
296 VECTOR C, mins, maxs;
297
298 Make_Vector(mins, BOUND_HUGE, BOUND_HUGE, BOUND_HUGE);
299 Make_Vector(maxs, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);
300
301 for (i = first; i < last; i++)
302 {
303 Assign_Vector(C, Elements[i]->C);
304
305 mins[X] = min(mins[X], C[X]);
306 maxs[X] = max(maxs[X], C[X]);
307
308 mins[Y] = min(mins[Y], C[Y]);
309 maxs[Y] = max(maxs[Y], C[Y]);
310
311 mins[Z] = min(mins[Z], C[Z]);
312 maxs[Z] = max(maxs[Z], C[Z]);
313 }
314
315 e = maxs[X] - mins[X];
316
317 if (e > d)
318 {
319 d = e; which = X;
320 }
321
322 e = maxs[Y] - mins[Y];
323
324 if (e > d)
325 {
326 d = e; which = Y;
327 }
328
329 e = maxs[Z] - mins[Z];
330
331 if (e > d)
332 {
333 which = Z;
334 }
335
336 return (which);
337 }
338
339
340
341 /*****************************************************************************
342 *
343 * FUNCTION
344 *
345 * build_area_table
346 *
347 * INPUT
348 *
349 * OUTPUT
350 *
351 * RETURNS
352 *
353 * AUTHOR
354 *
355 * Dieter Bayer
356 *
357 * DESCRIPTION
358 *
359 * Generates a table of bounding sphere surface areas.
360 *
361 * CHANGES
362 *
363 * Oct 1994 : Creation. (Derived from the bounding slab creation code)
364 *
365 ******************************************************************************/
366
build_area_table(BSPHERE_TREE ** Elements,int a,int b,DBL * areas)367 static void build_area_table(BSPHERE_TREE **Elements, int a, int b, DBL *areas)
368 {
369 int i, imin, dir;
370 DBL r2;
371 VECTOR C;
372
373 if (a < b)
374 {
375 imin = a; dir = 1;
376 }
377 else
378 {
379 imin = b; dir = -1;
380 }
381
382 Assign_Vector(C, Elements[a]->C);
383
384 r2 = Elements[a]->r2;
385
386 for (i = a; i != (b + dir); i += dir)
387 {
388 merge_spheres(C, &r2, C, r2, Elements[i]->C, Elements[i]->r2);
389
390 areas[i-imin] = r2;
391 }
392 }
393
394
395
396 /*****************************************************************************
397 *
398 * FUNCTION
399 *
400 * sort_and_split
401 *
402 * INPUT
403 *
404 * OUTPUT
405 *
406 * RETURNS
407 *
408 * AUTHOR
409 *
410 * Dieter Bayer
411 *
412 * DESCRIPTION
413 *
414 * -
415 *
416 * CHANGES
417 *
418 * Oct 1994 : Creation. (Derived from the bounding slab creation code)
419 *
420 ******************************************************************************/
421
sort_and_split(BSPHERE_TREE ** Root,BSPHERE_TREE *** Elements,int * nElem,int first,int last)422 static int sort_and_split(BSPHERE_TREE **Root, BSPHERE_TREE ***Elements, int *nElem, int first, int last)
423 {
424 int size, i, best_loc;
425 DBL *area_left, *area_right;
426 DBL best_index, new_index;
427 BSPHERE_TREE *cd;
428
429 Axis = find_axis(*Elements, first, last);
430
431 size = last - first;
432
433 if (size <= 0)
434 {
435 return (1);
436 }
437
438 Do_Cooperate(1);
439
440 /*
441 * Actually, we could do this faster in several ways. We could use a
442 * logn algorithm to find the median along the given axis, and then a
443 * linear algorithm to partition along the axis. Oh well.
444 */
445
446 QSORT((void *)(*Elements + first), size, sizeof(BSPHERE_TREE *), comp_elements);
447
448 /*
449 * area_left[] and area_right[] hold the surface areas of the bounding
450 * boxes to the left and right of any given point. E.g. area_left[i] holds
451 * the surface area of the bounding box containing Elements 0 through i and
452 * area_right[i] holds the surface area of the box containing Elements
453 * i through size-1.
454 */
455
456 area_left = (DBL *)POV_MALLOC(size * sizeof(DBL), "blob bounding hierarchy");
457 area_right = (DBL *)POV_MALLOC(size * sizeof(DBL), "blob bounding hierarchy");
458
459 /* Precalculate the areas for speed. */
460
461 build_area_table(*Elements, first, last - 1, area_left);
462 build_area_table(*Elements, last - 1, first, area_right);
463
464 best_index = area_right[0] * (size - 3.0);
465
466 best_loc = - 1;
467
468 /*
469 * Find the most effective point to split. The best location will be
470 * the one that minimizes the function N1*A1 + N2*A2 where N1 and N2
471 * are the number of objects in the two groups and A1 and A2 are the
472 * surface areas of the bounding boxes of the two groups.
473 */
474
475 for (i = 0; i < size - 1; i++)
476 {
477 new_index = (i + 1) * area_left[i] + (size - 1 - i) * area_right[i + 1];
478
479 if (new_index < best_index)
480 {
481 best_index = new_index;
482 best_loc = i + first;
483 }
484 }
485
486 POV_FREE(area_left);
487 POV_FREE(area_right);
488
489 /*
490 * Stop splitting if the BRANCHING_FACTOR is reached or
491 * if splitting stops being effective.
492 */
493
494 if ((size <= BRANCHING_FACTOR) || (best_loc < 0))
495 {
496 cd = (BSPHERE_TREE *)POV_MALLOC(sizeof(BSPHERE_TREE), "blob bounding hierarchy");
497
498 cd->Entries = (short)size;
499
500 cd->Node = (BSPHERE_TREE **)POV_MALLOC(size*sizeof(BSPHERE_TREE *), "blob bounding hierarchy");
501
502 for (i = 0; i < size; i++)
503 {
504 cd->Node[i] = (*Elements)[first+i];
505 }
506
507 recompute_bound(cd);
508
509 *Root = cd;
510
511 if (*nElem >= maxelements)
512 {
513 /* Prim array overrun, increase array by 50%. */
514
515 #ifdef AVOID_TYPE_CONVERSION_WARNINGS_PATCH
516 maxelements = (int)( 1.5 * (DBL) maxelements );
517 #else
518 maxelements = 1.5 * maxelements ;
519 #endif
520
521 /* For debugging only. */
522
523 Debug_Info("Reallocing elements to %d\n", maxelements);
524
525 *Elements = (BSPHERE_TREE **)POV_REALLOC(*Elements, maxelements * sizeof(BSPHERE_TREE *), "bounding slabs");
526 }
527
528 (*Elements)[*nElem] = cd;
529
530 (*nElem)++;
531
532 return (1);
533 }
534 else
535 {
536 sort_and_split(Root, Elements, nElem, first, best_loc + 1);
537
538 sort_and_split(Root, Elements, nElem, best_loc + 1, last);
539
540 return (0);
541 }
542 }
543
544
545
546 /*****************************************************************************
547 *
548 * FUNCTION
549 *
550 * Build_Bounding_Sphere_Hierarchy
551 *
552 * INPUT
553 *
554 * nElem - number of elements in Elements
555 * Elements - array containing nElem elements
556 *
557 * OUTPUT
558 *
559 * Root - root node of the hierarchy
560 *
561 * RETURNS
562 *
563 * AUTHOR
564 *
565 * Dieter Bayer
566 *
567 * DESCRIPTION
568 *
569 * Create the bounding sphere hierarchy for a given set of elements.
570 * One element consists of an element number (index into the array
571 * of elements; e.g. blob components, triangles) and a bounding
572 * sphere enclosing this element (center and squared radius).
573 *
574 * CHANGES
575 *
576 * Oct 1994 : Creation. (Derived from the bounding slab creation code)
577 *
578 ******************************************************************************/
579
Build_Bounding_Sphere_Hierarchy(BSPHERE_TREE ** Root,int nElem,BSPHERE_TREE *** Elements)580 void Build_Bounding_Sphere_Hierarchy(BSPHERE_TREE **Root, int nElem, BSPHERE_TREE ***Elements)
581 {
582 int low, high;
583
584 /*
585 * This is a resonable guess at the number of elements needed.
586 * This array will be reallocated as needed if it isn't.
587 */
588
589 maxelements = 2 * nElem;
590
591 /*
592 * Do a sort on the elements, with the end result being
593 * a tree of objects sorted along the x, y, and z axes.
594 */
595
596 if (nElem > 0)
597 {
598 low = 0;
599 high = nElem;
600
601 while (sort_and_split(Root, Elements, &nElem, low, high) == 0)
602 {
603 low = high;
604 high = nElem;
605
606 Do_Cooperate(0);
607 }
608 }
609 }
610
611
612
613 /*****************************************************************************
614 *
615 * FUNCTION
616 *
617 * Destroy_Bounding_Sphere_Hierarchy
618 *
619 * INPUT
620 *
621 * Node - Pointer to current node
622 *
623 * OUTPUT
624 *
625 * Node
626 *
627 * RETURNS
628 *
629 * AUTHOR
630 *
631 * Dieter Bayer
632 *
633 * DESCRIPTION
634 *
635 * Destroy bounding sphere hierarchy.
636 *
637 * CHANGES
638 *
639 * Aug 1994 : Creation.
640 *
641 * Dec 1994 : Fixed memory leakage. [DB]
642 *
643 ******************************************************************************/
644
Destroy_Bounding_Sphere_Hierarchy(BSPHERE_TREE * Node)645 void Destroy_Bounding_Sphere_Hierarchy(BSPHERE_TREE *Node)
646 {
647 short i;
648
649 if (Node != NULL)
650 {
651 if (Node->Entries > 0)
652 {
653 /* This is a node. Free sub-nodes. */
654
655 for (i = 0; i < Node->Entries; i++)
656 {
657 Destroy_Bounding_Sphere_Hierarchy(Node->Node[i]);
658 }
659
660 POV_FREE(Node->Node);
661 }
662
663 POV_FREE(Node);
664 }
665 }
666
667 END_POV_NAMESPACE
668