POV-Ray : Newsgroups : povray.programming : CSG Bounding box algorithm : Re: CSG Bounding box algorithm Server Time
5 Dec 2021 15:49:22 EST (-0500)
  Re: CSG Bounding box algorithm  
From: clipka
Date: 23 Aug 2017 14:15:53
Message: <599dc659$1@news.povray.org>
Am 23.08.2017 um 14:09 schrieb Bald Eagle:
> Can anyone tell me if this is still the case?
> 
> From (bottom of page):
> http://www.povray.org/documentation/view/3.6.0/184/
> 
> But this automatic bounding is not perfect. There are situations where a perfect
> automatic bounding is very hard to calculate. One situation is the difference
> and the intersection CSG operations. POV-Ray does what it can, but sometimes it
> makes a pretty poor job. This can be specially seen when the resulting CSG
> object is very small compared to the CSG member objects. For example:
> intersection
> { sphere { <-1000,0,0>,1001 }
>   sphere { <1000,0,0>,1001 }
> }
> (This is the same as making a difference with the second sphere inversed)
> In this example the member objects extend from <-2001,-1001,-1001> to
> <2001,1001,1001> although the resulting CSG object is a pretty small lens-shaped
> object which is only 2 units wide in the x direction and perhaps 10 or 20 or
> something wide in the y and z directions. As you can see, it is very difficult
> to calculate the actual dimensions of the object (but not impossible).
> In this type of cases POV-Ray makes a huge bounding box which is useless. You
> should bound this kind of objects by hand (specially when the it has lots of
> member objects). This can be done with the bounded_by keyword.
> 
> ---------------------------------------------
> 
> This didn't seem to me to be a factual representation - I believe there are some
> straightforward algorithms for determining the bounding box of the intersection
> for any two overlapping axis-aligned bounding boxes (AABB).
> Am I wrong?

Eyeballing the axis-aligned bounding box of an intersection as the
intersection of the children's axis-aligned bounding boxes is indeed
trivial, and that's why POV-Ray already does exactly that by default.

(*Well, not /totally/ exactly: When planes or quartics are involved,
POV-Ray tries to come up with tighter bounds for them by using the
b'boxes of the sibling objects as constraints.)

The problem hinted at by the docs is that sometimes this simple
algorithm gives you a bounding box far larger than necessary, and in
such cases providing a "hand-made" bounding box will increase rendering
speed.

There is no generic algorithm to compute the exact b'box of an
intersection. Each specific combination of primitives would need its own
algorithm.

> The only tricky part was getting it handle cases outside of Quadrant I, but I
> just implemented a faux-translation of the union {} of the two bounding boxes to
> place its min_extent at the origin. (I add in that correction vector for the
> intermediate calculations)

??? Why would you need special handling for the quadrants?

To compute the intersection of multiple axis-aligned b'boxes, all you
need to do is get the highest low bounds for all axes and the lowest
high bound for all axes.

> If this is still an issue, are there certain cases that are especially
> problematic for certain CSG operations?

Yes: All cases and none at all. Almost /any/ combination of primitives
can be used to come up with pathological cases.


Post a reply to this message

Copyright 2003-2021 Persistence of Vision Raytracer Pty. Ltd.