gfx/povray/csg.c

   1 /****************************************************************************
   2 *                   csg.c
   3 *
   4 *  This module implements routines for constructive solid geometry.
   5 *
   6 *  from Persistence of Vision(tm) Ray Tracer
   7 *  Copyright 1996,1999 Persistence of Vision Team
   8 *---------------------------------------------------------------------------
   9 *  NOTICE: This source code file is provided so that users may experiment
  10 *  with enhancements to POV-Ray and to port the software to platforms other
  11 *  than those supported by the POV-Ray Team.  There are strict rules under
  12 *  which you are permitted to use this file.  The rules are in the file
  13 *  named POVLEGAL.DOC which should be distributed with this file.
  14 *  If POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  15 *  Team Coordinator by email to team-coord@povray.org or visit us on the web at
  16 *  http://www.povray.org. The latest version of POV-Ray may be found at this site.
  17 *
  18 * This program is based on the popular DKB raytracer version 2.12.
  19 * DKBTrace was originally written by David K. Buck.
  20 * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  21 *
  22 *****************************************************************************/
  23
  24 #include "frame.h"
  25 #include "povray.h"
  26 #include "vector.h"
  27 #include "povproto.h"
  28 #include "bbox.h"
  29 #include "csg.h"
  30 #include "hfield.h"
  31 #include "matrices.h"
  32 #include "objects.h"
  33 #include "planes.h"
  34 #include "quadrics.h"
  35
  36
  37
  38 /*****************************************************************************
  39 * Local preprocessor defines
  40 ******************************************************************************/
  41
  42
  43
  44
  45 /*****************************************************************************
  46 * Static functions
  47 ******************************************************************************/
  48
  49 static int All_CSG_Union_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack);
  50 static int All_CSG_Merge_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack);
  51 static int All_CSG_Intersect_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack);
  52 static int Inside_CSG_Union (VECTOR point, OBJECT *Object);
  53 static int Inside_CSG_Intersection (VECTOR point, OBJECT *Object);
  54 static CSG *Copy_CSG (OBJECT *Object);
  55 static void Translate_CSG (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans);
  56 static void Rotate_CSG (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans);
  57 static void Scale_CSG (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans);
  58 static void Transform_CSG (OBJECT *Object, TRANSFORM *Trans);
  59 static void Destroy_CSG (OBJECT *Object);
  60 static void Invert_CSG_Union (OBJECT *Object);
  61 static void Invert_CSG_Intersection (OBJECT *Object);
  62
  63
  64 /*****************************************************************************
  65 * Local variables
  66 ******************************************************************************/
  67
  68 METHODS CSG_Union_Methods =
  69 {
  70   All_CSG_Union_Intersections,
  71   Inside_CSG_Union, NULL /*Normal*/,
  72   (COPY_METHOD)Copy_CSG,
  73   Translate_CSG, Rotate_CSG,
  74   Scale_CSG, Transform_CSG, Invert_CSG_Union, Destroy_CSG
  75 };
  76
  77 METHODS CSG_Merge_Methods =
  78 {
  79   All_CSG_Merge_Intersections,
  80   Inside_CSG_Union, NULL /*Normal*/,
  81   (COPY_METHOD)Copy_CSG,
  82   Translate_CSG, Rotate_CSG,
  83   Scale_CSG, Transform_CSG, Invert_CSG_Union, Destroy_CSG
  84 };
  85
  86 METHODS CSG_Intersection_Methods =
  87 {
  88   All_CSG_Intersect_Intersections,
  89   Inside_CSG_Intersection, NULL /*Normal*/,
  90   (COPY_METHOD)Copy_CSG,
  91   Translate_CSG, Rotate_CSG,
  92   Scale_CSG, Transform_CSG, Invert_CSG_Intersection, Destroy_CSG
  93 };
  94
  95
  96
  97 /*****************************************************************************
  98 *
  99 * FUNCTION
 100 *
 101 *   All_CSG_Union_Intersections
 102 *
 103 * INPUT
 104 *
 105 * OUTPUT
 106 *
 107 * RETURNS
 108 *
 109 * AUTHOR
 110 *
 111 *   POV-Ray Team
 112 *
 113 * DESCRIPTION
 114 *
 115 *   -
 116 *
 117 * CHANGES
 118 *
 119 *   Sep 1994 : Added code to count intersection tests. [DB]
 120 *
 121 ******************************************************************************/
 122
 123 static int All_CSG_Union_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack)
 124 {
 125   int Found;
 126   OBJECT *Current_Sib, *Clip;
 127   ISTACK *Local_Stack;
 128   INTERSECTION *Sibling_Intersection;
 129
 130   Increase_Counter(stats[Ray_CSG_Union_Tests]);
 131
 132   Found = FALSE;
 133
 134   /* Use shortcut if no clip. */
 135
 136   if ((Clip = Object->Clip) == NULL)
 137   {
 138     for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
 139     {
 140       if (Ray_In_Bound (Ray, Current_Sib->Bound))
 141       {
 142         if (All_Intersections (Current_Sib, Ray, Depth_Stack))
 143         {
 144           Found = TRUE;
 145         }
 146       }
 147     }
 148   }
 149   else
 150   {
 151     Local_Stack = open_istack();
 152
 153     for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
 154     {
 155       if (Ray_In_Bound (Ray, Current_Sib->Bound))
 156       {
 157         if (All_Intersections (Current_Sib, Ray, Local_Stack))
 158         {
 159           while ((Sibling_Intersection = pop_entry(Local_Stack)) != NULL)
 160           {
 161             if (Point_In_Clip (Sibling_Intersection->IPoint, Clip))
 162             {
 163               push_copy (Depth_Stack, Sibling_Intersection);
 164
 165               Found = TRUE;
 166             }
 167           }
 168         }
 169       }
 170     }
 171
 172     close_istack (Local_Stack);
 173   }
 174
 175   if (Found)
 176   {
 177     Increase_Counter(stats[Ray_CSG_Union_Tests_Succeeded]);
 178   }
 179
 180   return (Found);
 181 }
 182
 183
 184
 185 /*****************************************************************************
 186 *
 187 * FUNCTION
 188 *
 189 *   All_CSG_Intersection_Intersections
 190 *
 191 * INPUT
 192 *
 193 * OUTPUT
 194 *
 195 * RETURNS
 196 *
 197 * AUTHOR
 198 *
 199 *   POV-Ray Team
 200 *
 201 * DESCRIPTION
 202 *
 203 *   -
 204 *
 205 * CHANGES
 206 *
 207 *   Sep 1994 : Added code to count intersection tests. [DB]
 208 *
 209 ******************************************************************************/
 210
 211 static int All_CSG_Intersect_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack)
 212 {
 213   int Maybe_Found, Found;
 214   OBJECT *Current_Sib, *Inside_Sib;
 215   ISTACK *Local_Stack;
 216   INTERSECTION *Sibling_Intersection;
 217
 218   Increase_Counter(stats[Ray_CSG_Intersection_Tests]);
 219
 220   Local_Stack = open_istack ();
 221
 222   Found = FALSE;
 223
 224   for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
 225   {
 226     if (Ray_In_Bound (Ray, Current_Sib->Bound))
 227     {
 228       if (All_Intersections (Current_Sib, Ray, Local_Stack))
 229       {
 230         while ((Sibling_Intersection = pop_entry(Local_Stack)) != NULL)
 231         {
 232           Maybe_Found = TRUE;
 233
 234           for (Inside_Sib = ((CSG *)Object)->Children; Inside_Sib != NULL; Inside_Sib = Inside_Sib->Sibling)
 235           {
 236             if (Inside_Sib != Current_Sib)
 237             {
 238               if (!Inside_Object (Sibling_Intersection->IPoint, Inside_Sib))
 239               {
 240                 Maybe_Found = FALSE;
 241
 242                 break;
 243               }
 244             }
 245           }
 246
 247           if (Maybe_Found)
 248           {
 249             if (Point_In_Clip (Sibling_Intersection->IPoint, Object->Clip))
 250             {
 251               push_copy(Depth_Stack, Sibling_Intersection);
 252
 253               Found = TRUE;
 254             }
 255           }
 256         }
 257       }
 258     }
 259   }
 260
 261   close_istack (Local_Stack);
 262
 263   if (Found)
 264   {
 265     Increase_Counter(stats[Ray_CSG_Intersection_Tests_Succeeded]);
 266   }
 267
 268   return (Found);
 269 }
 270
 271
 272
 273 /*****************************************************************************
 274 *
 275 * FUNCTION
 276 *
 277 *   All_CSG_Merge_Intersections
 278 *
 279 * INPUT
 280 *
 281 * OUTPUT
 282 *
 283 * RETURNS
 284 *
 285 * AUTHOR
 286 *
 287 *   POV-Ray Team
 288 *
 289 * DESCRIPTION
 290 *
 291 *   -
 292 *
 293 * CHANGES
 294 *
 295 *   Sep 1994 : Added code to count intersection tests. [DB]
 296 *
 297 ******************************************************************************/
 298
 299 static int All_CSG_Merge_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack)
 300 {
 301   int Found, inside_flag;
 302   OBJECT *Sib1, *Sib2;
 303   ISTACK *Local_Stack;
 304   INTERSECTION *Sibling_Intersection;
 305
 306   Increase_Counter(stats[Ray_CSG_Merge_Tests]);
 307
 308   Found = FALSE;
 309
 310   Local_Stack = open_istack ();
 311
 312   for (Sib1 = ((CSG *)Object)->Children; Sib1 != NULL; Sib1 = Sib1->Sibling)
 313   {
 314     if (Ray_In_Bound (Ray, Sib1->Bound))
 315     {
 316       if (All_Intersections (Sib1, Ray, Local_Stack))
 317       {
 318         while ((Sibling_Intersection = pop_entry (Local_Stack)) !=  NULL)
 319         {
 320           if (Point_In_Clip (Sibling_Intersection->IPoint, Object->Clip))
 321           {
 322             inside_flag = TRUE;
 323
 324             for (Sib2 = ((CSG *)Object)->Children; Sib2 != NULL && inside_flag == TRUE; Sib2 = Sib2->Sibling)
 325             {
 326               if (Sib1 != Sib2)
 327               {
 328                 if (Inside_Object(Sibling_Intersection->IPoint, Sib2))
 329                 {
 330                   inside_flag = FALSE;
 331                 }
 332               }
 333             }
 334
 335             if (inside_flag == TRUE)
 336             {
 337               Found = TRUE;
 338
 339               push_copy (Depth_Stack, Sibling_Intersection);
 340             }
 341           }
 342         }
 343       }
 344     }
 345   }
 346
 347   close_istack (Local_Stack);
 348
 349   if (Found)
 350   {
 351     Increase_Counter(stats[Ray_CSG_Merge_Tests_Succeeded]);
 352   }
 353
 354   return (Found);
 355 }
 356
 357
 358
 359 /*****************************************************************************
 360 *
 361 * FUNCTION
 362 *
 363 *   Inside_CSG_Union
 364 *
 365 * INPUT
 366 *
 367 * OUTPUT
 368 *
 369 * RETURNS
 370 *
 371 * AUTHOR
 372 *
 373 *   POV-Ray Team
 374 *
 375 * DESCRIPTION
 376 *
 377 *   -
 378 *
 379 * CHANGES
 380 *
 381 *   -
 382 *
 383 ******************************************************************************/
 384
 385 static int Inside_CSG_Union (VECTOR IPoint, OBJECT *Object)
 386 {
 387   OBJECT *Current_Sib;
 388
 389   for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
 390   {
 391     if (Inside_Object (IPoint, Current_Sib))
 392     {
 393       return (TRUE);
 394     }
 395   }
 396
 397   return (FALSE);
 398 }
 399
 400
 401
 402 /*****************************************************************************
 403 *
 404 * FUNCTION
 405 *
 406 *   Inside_CSG_Intersection
 407 *
 408 * INPUT
 409 *
 410 * OUTPUT
 411 *
 412 * RETURNS
 413 *
 414 * AUTHOR
 415 *
 416 *   POV-Ray Team
 417 *
 418 * DESCRIPTION
 419 *
 420 *   -
 421 *
 422 * CHANGES
 423 *
 424 *   -
 425 *
 426 ******************************************************************************/
 427
 428 static int Inside_CSG_Intersection (VECTOR IPoint, OBJECT *Object)
 429 {
 430   OBJECT *Current_Sib;
 431
 432   for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
 433   {
 434     if (!Inside_Object (IPoint, Current_Sib))
 435     {
 436       return (FALSE);
 437     }
 438   }
 439
 440   return (TRUE);
 441 }
 442
 443
 444
 445 /*****************************************************************************
 446 *
 447 * FUNCTION
 448 *
 449 *   Translate_CSG
 450 *
 451 * INPUT
 452 *
 453 * OUTPUT
 454 *
 455 * RETURNS
 456 *
 457 * AUTHOR
 458 *
 459 *   POV-Ray Team
 460 *
 461 * DESCRIPTION
 462 *
 463 *   -
 464 *
 465 * CHANGES
 466 *
 467 *   -
 468 *
 469 ******************************************************************************/
 470
 471 static void Translate_CSG (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans)
 472 {
 473   OBJECT *Sib;
 474
 475   for (Sib = ((CSG *) Object)->Children; Sib != NULL; Sib = Sib->Sibling)
 476   {
 477     Translate_Object(Sib, Vector, Trans);
 478   }
 479
 480   Recompute_BBox(&Object->BBox, Trans);
 481 }
 482
 483
 484
 485 /*****************************************************************************
 486 *
 487 * FUNCTION
 488 *
 489 *   Rotate_CSG
 490 *
 491 * INPUT
 492 *
 493 * OUTPUT
 494 *
 495 * RETURNS
 496 *
 497 * AUTHOR
 498 *
 499 *   POV-Ray Team
 500 *
 501 * DESCRIPTION
 502 *
 503 *   -
 504 *
 505 * CHANGES
 506 *
 507 *   -
 508 *
 509 ******************************************************************************/
 510
 511 static void Rotate_CSG (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans)
 512 {
 513   OBJECT *Sib;
 514
 515   for (Sib = ((CSG *) Object)->Children; Sib != NULL; Sib = Sib->Sibling)
 516   {
 517     Rotate_Object(Sib, Vector, Trans);
 518   }
 519
 520   Recompute_BBox(&Object->BBox, Trans);
 521 }
 522
 523
 524
 525 /*****************************************************************************
 526 *
 527 * FUNCTION
 528 *
 529 *   Scale_CSG
 530 *
 531 * INPUT
 532 *
 533 * OUTPUT
 534 *
 535 * RETURNS
 536 *
 537 * AUTHOR
 538 *
 539 *   POV-Ray Team
 540 *
 541 * DESCRIPTION
 542 *
 543 *   -
 544 *
 545 * CHANGES
 546 *
 547 *   -
 548 *
 549 ******************************************************************************/
 550
 551 static void Scale_CSG (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans)
 552 {
 553   OBJECT *Sib;
 554
 555   for (Sib = ((CSG *) Object)->Children; Sib != NULL; Sib = Sib->Sibling)
 556   {
 557     Scale_Object(Sib, Vector, Trans);
 558   }
 559
 560   Recompute_BBox(&Object->BBox, Trans);
 561 }
 562
 563
 564
 565 /*****************************************************************************
 566 *
 567 * FUNCTION
 568 *
 569 *   Transform_CSG
 570 *
 571 * INPUT
 572 *
 573 * OUTPUT
 574 *
 575 * RETURNS
 576 *
 577 * AUTHOR
 578 *
 579 *   POV-Ray Team
 580 *
 581 * DESCRIPTION
 582 *
 583 *   -
 584 *
 585 * CHANGES
 586 *
 587 *   -
 588 *
 589 ******************************************************************************/
 590
 591 static void Transform_CSG (OBJECT *Object, TRANSFORM *Trans)
 592 {
 593   OBJECT *Sib;
 594
 595   for (Sib = ((CSG *) Object)->Children; Sib != NULL; Sib = Sib->Sibling)
 596   {
 597     Transform_Object (Sib, Trans);
 598   }
 599
 600   Recompute_BBox(&Object->BBox, Trans);
 601 }
 602
 603
 604
 605 /*****************************************************************************
 606 *
 607 * FUNCTION
 608 *
 609 *   Invert_CSG_Union
 610 *
 611 * INPUT
 612 *
 613 * OUTPUT
 614 *
 615 * RETURNS
 616 *
 617 * AUTHOR
 618 *
 619 *   POV-Ray Team
 620 *
 621 * DESCRIPTION
 622 *
 623 *   -
 624 *
 625 * CHANGES
 626 *
 627 *   -
 628 *
 629 ******************************************************************************/
 630
 631 static void Invert_CSG_Union (OBJECT *Object)
 632 {
 633   OBJECT *Sib;
 634
 635   Object->Methods = &CSG_Intersection_Methods;
 636
 637   for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
 638   {
 639     Invert_Object (Sib);
 640   }
 641
 642   Invert_Flag(Object, INVERTED_FLAG);
 643 }
 644
 645
 646
 647 /*****************************************************************************
 648 *
 649 * FUNCTION
 650 *
 651 *   Invert_CSG_Intersection
 652 *
 653 * INPUT
 654 *
 655 * OUTPUT
 656 *
 657 * RETURNS
 658 *
 659 * AUTHOR
 660 *
 661 *   POV-Ray Team
 662 *
 663 * DESCRIPTION
 664 *
 665 *   -
 666 *
 667 * CHANGES
 668 *
 669 *   -
 670 *
 671 ******************************************************************************/
 672
 673 static void Invert_CSG_Intersection (OBJECT *Object)
 674 {
 675   OBJECT *Sib;
 676
 677   Object->Methods = &CSG_Merge_Methods;
 678
 679   for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
 680   {
 681     Invert_Object (Sib);
 682   }
 683
 684   Invert_Flag(Object, INVERTED_FLAG);
 685 }
 686
 687
 688
 689 /*****************************************************************************
 690 *
 691 * FUNCTION
 692 *
 693 *   Create_CSG_Union
 694 *
 695 * INPUT
 696 *
 697 * OUTPUT
 698 *
 699 * RETURNS
 700 *
 701 * AUTHOR
 702 *
 703 *   POV-Ray Team
 704 *
 705 * DESCRIPTION
 706 *
 707 *   -
 708 *
 709 * CHANGES
 710 *
 711 *   -
 712 *
 713 ******************************************************************************/
 714
 715 CSG *Create_CSG_Union ()
 716 {
 717   CSG *New;
 718
 719   New = (CSG *)POV_MALLOC(sizeof (CSG), "union");
 720
 721   INIT_OBJECT_FIELDS(New, UNION_OBJECT, &CSG_Union_Methods)
 722
 723   New->Children = NULL;
 724
 725   return (New);
 726 }
 727
 728
 729
 730 /*****************************************************************************
 731 *
 732 * FUNCTION
 733 *
 734 *   Create_CSG_Merge
 735 *
 736 * INPUT
 737 *
 738 * OUTPUT
 739 *
 740 * RETURNS
 741 *
 742 * AUTHOR
 743 *
 744 *   POV-Ray Team
 745 *
 746 * DESCRIPTION
 747 *
 748 *   -
 749 *
 750 * CHANGES
 751 *
 752 *   -
 753 *
 754 ******************************************************************************/
 755
 756 CSG *Create_CSG_Merge ()
 757 {
 758   CSG *New;
 759
 760   New = (CSG *)POV_MALLOC(sizeof (CSG), "merge");
 761
 762   INIT_OBJECT_FIELDS(New, MERGE_OBJECT, &CSG_Merge_Methods)
 763
 764   New->Children = NULL;
 765
 766   return (New);
 767 }
 768
 769
 770
 771 /*****************************************************************************
 772 *
 773 * FUNCTION
 774 *
 775 *   Create_CSG_Intersection
 776 *
 777 * INPUT
 778 *
 779 * OUTPUT
 780 *
 781 * RETURNS
 782 *
 783 * AUTHOR
 784 *
 785 *   POV-Ray Team
 786 *
 787 * DESCRIPTION
 788 *
 789 *   -
 790 *
 791 * CHANGES
 792 *
 793 *   -
 794 *
 795 ******************************************************************************/
 796
 797 CSG *Create_CSG_Intersection ()
 798 {
 799   CSG *New;
 800
 801   New = (CSG *)POV_MALLOC(sizeof (CSG), "intersection");
 802
 803   INIT_OBJECT_FIELDS(New, INTERSECTION_OBJECT, &CSG_Intersection_Methods)
 804
 805   New->Children = NULL;
 806
 807   return (New);
 808 }
 809
 810
 811
 812 /*****************************************************************************
 813 *
 814 * FUNCTION
 815 *
 816 *   Copy_CSG
 817 *
 818 * INPUT
 819 *
 820 * OUTPUT
 821 *
 822 * RETURNS
 823 *
 824 * AUTHOR
 825 *
 826 *   POV-Ray Team
 827 *
 828 * DESCRIPTION
 829 *
 830 *   -
 831 *
 832 * CHANGES
 833 *
 834 *   -
 835 *
 836 ******************************************************************************/
 837
 838 static CSG *Copy_CSG (OBJECT *Object)
 839 {
 840   CSG *New;
 841   OBJECT *Old_Sib, *New_Sib, *Prev_Sib;
 842
 843   New = (CSG *)POV_MALLOC(sizeof (CSG), "csg");
 844
 845   *New = *(CSG *)Object;
 846
 847   New->Children = Prev_Sib = NULL;
 848
 849   for (Old_Sib = ((CSG *)Object)->Children; Old_Sib != NULL; Old_Sib = Old_Sib->Sibling)
 850   {
 851     New_Sib = Copy_Object (Old_Sib);
 852
 853     if (New->Children == NULL)
 854     {
 855       New->Children = New_Sib;
 856     }
 857
 858     if (Prev_Sib != NULL)
 859     {
 860       Prev_Sib->Sibling = New_Sib;
 861     }
 862
 863     Prev_Sib = New_Sib;
 864   }
 865
 866   return (New);
 867 }
 868
 869
 870
 871 /*****************************************************************************
 872 *
 873 * FUNCTION
 874 *
 875 *   Destroy_CSG
 876 *
 877 * INPUT
 878 *
 879 * OUTPUT
 880 *
 881 * RETURNS
 882 *
 883 * AUTHOR
 884 *
 885 *   POV-Ray Team
 886 *
 887 * DESCRIPTION
 888 *
 889 *   -
 890 *
 891 * CHANGES
 892 *
 893 *   -
 894 *
 895 ******************************************************************************/
 896
 897 static void Destroy_CSG (OBJECT *Object)
 898 {
 899   Destroy_Object (((CSG *) Object)->Children);
 900
 901   POV_FREE (Object);
 902 }
 903
 904
 905
 906 /*****************************************************************************
 907 *
 908 * FUNCTION
 909 *
 910 *   Compute_CSG_BBox
 911 *
 912 * INPUT
 913 *
 914 * OUTPUT
 915 *
 916 * RETURNS
 917 *
 918 * AUTHOR
 919 *
 920 *   POV-Ray Team
 921 *
 922 * DESCRIPTION
 923 *
 924 *   -
 925 *
 926 * CHANGES
 927 *
 928 *   Sep 1994 : Improved bounding of quadrics used in CSG intersections. [DB]
 929 *
 930 ******************************************************************************/
 931
 932 void Compute_CSG_BBox (OBJECT *Object)
 933 {
 934   int i, count;
 935   DBL Old_Volume, New_Volume;
 936   VECTOR NewMin, NewMax, TmpMin, TmpMax, Min, Max;
 937   OBJECT *Sib;
 938   QUADRIC **Quadrics;
 939
 940   if (Object->Methods == &CSG_Intersection_Methods)
 941   {
 942     /*
 943      * Calculate the bounding box of a CSG intersection
 944      * by intersecting the bounding boxes of all children.
 945      */
 946
 947     Make_Vector(NewMin, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);
 948     Make_Vector(NewMax,  BOUND_HUGE,  BOUND_HUGE,  BOUND_HUGE);
 949
 950     count = 0;
 951
 952     Quadrics = NULL;
 953
 954     /* Process all children. */
 955
 956     for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
 957     {
 958       /* Inverted objects and height fields mustn't be considered */
 959
 960       if (!Test_Flag(Sib, INVERTED_FLAG) && (Sib->Methods != &HField_Methods))
 961       {
 962         /* Store quadrics since they'll be processed last. */
 963
 964         if (Sib->Methods == &Quadric_Methods)
 965         {
 966           Quadrics = (QUADRIC **)POV_REALLOC(Quadrics, (count+1)*sizeof(QUADRIC *), "temporary quadric list");
 967
 968           Quadrics[count++] = (QUADRIC *)Sib;
 969         }
 970         else
 971         {
 972           if (Sib->Methods == &Plane_Methods)
 973           {
 974             Compute_Plane_Min_Max((PLANE *)Sib, TmpMin, TmpMax);
 975           }
 976           else
 977           {
 978             Make_min_max_from_BBox(TmpMin, TmpMax, Sib->BBox);
 979           }
 980
 981           NewMin[X] = max(NewMin[X], TmpMin[X]);
 982           NewMin[Y] = max(NewMin[Y], TmpMin[Y]);
 983           NewMin[Z] = max(NewMin[Z], TmpMin[Z]);
 984           NewMax[X] = min(NewMax[X], TmpMax[X]);
 985           NewMax[Y] = min(NewMax[Y], TmpMax[Y]);
 986           NewMax[Z] = min(NewMax[Z], TmpMax[Z]);
 987         }
 988       }
 989     }
 990
 991     /* Process any quadrics. */
 992
 993     for (i = 0; i < count; i++)
 994     {
 995       Assign_Vector(Min, NewMin);
 996       Assign_Vector(Max, NewMax);
 997
 998       Compute_Quadric_BBox(Quadrics[i], Min, Max);
 999
1000       Make_min_max_from_BBox(TmpMin, TmpMax, Quadrics[i]->BBox);
1001
1002       NewMin[X] = max(NewMin[X], TmpMin[X]);
1003       NewMin[Y] = max(NewMin[Y], TmpMin[Y]);
1004       NewMin[Z] = max(NewMin[Z], TmpMin[Z]);
1005       NewMax[X] = min(NewMax[X], TmpMax[X]);
1006       NewMax[Y] = min(NewMax[Y], TmpMax[Y]);
1007       NewMax[Z] = min(NewMax[Z], TmpMax[Z]);
1008     }
1009
1010     if (Quadrics != NULL)
1011     {
1012       POV_FREE(Quadrics);
1013     }
1014   }
1015   else
1016   {
1017     /* Calculate the bounding box of a CSG merge/union object. */
1018
1019     Make_Vector(NewMin,  BOUND_HUGE,  BOUND_HUGE,  BOUND_HUGE);
1020     Make_Vector(NewMax, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);
1021
1022     for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
1023     {
1024       Make_min_max_from_BBox(TmpMin, TmpMax, Sib->BBox);
1025
1026       NewMin[X] = min(NewMin[X], TmpMin[X]);
1027       NewMin[Y] = min(NewMin[Y], TmpMin[Y]);
1028       NewMin[Z] = min(NewMin[Z], TmpMin[Z]);
1029       NewMax[X] = max(NewMax[X], TmpMax[X]);
1030       NewMax[Y] = max(NewMax[Y], TmpMax[Y]);
1031       NewMax[Z] = max(NewMax[Z], TmpMax[Z]);
1032     }
1033   }
1034
1035   if ((NewMin[X] > NewMax[X]) || (NewMin[Y] > NewMax[Y]) || (NewMin[Z] > NewMax[Z]))
1036   {
1037     Warning(0.0, "Degenerate CSG bounding box (not used!).\n");
1038   }
1039   else
1040   {
1041     New_Volume = (NewMax[X] - NewMin[X]) * (NewMax[Y] - NewMin[Y]) * (NewMax[Z] - NewMin[Z]);
1042
1043     BOUNDS_VOLUME(Old_Volume, Object->BBox);
1044
1045     if (New_Volume < Old_Volume)
1046     {
1047       Make_BBox_from_min_max(Object->BBox, NewMin, NewMax);
1048
1049       /* Beware of bounding boxes to large. */
1050
1051       if ((Object->BBox.Lengths[X] > CRITICAL_LENGTH) ||
1052           (Object->BBox.Lengths[Y] > CRITICAL_LENGTH) ||
1053           (Object->BBox.Lengths[Z] > CRITICAL_LENGTH))
1054       {
1055         Make_BBox(Object->BBox, -BOUND_HUGE/2, -BOUND_HUGE/2, -BOUND_HUGE/2,
1056           BOUND_HUGE, BOUND_HUGE, BOUND_HUGE);
1057       }
1058     }
1059   }
1060 }