I was trying to render a 3D puzzle by intersecting generic
puzzle tiles with a desired target shape and found it rendered
very slowly, even when intersecting the individual tiles before
creating a union. The effect was curious as it turned out

intersection
{
   object {A}
   object {B}
   bounded_by {B}
}

was much faster than

intersection
{
   object {A}
   object {B}
}

After some investigation I found that the problem was related to
the number of puzzle tiles completely outside the target shape, so
there seems to be some problem with empty intersections. I think
these should be discarded or at least get a small bounding box,
but they seem to be sticking around unbounded.

Also, I had originally expected to be able to use "split_union"
so I wouldn't have to intersect individual tiles (it's a bit more
effort due to scaling of final object size), but then found it was
only for photons. Such a setting might also be useful for bounding.

A small sample scene demonstrating both effects is attached.

Tested using 3.7 RC3

Post a reply to this message

Attachments:
Download 'us-ascii' (5 KB)

Christian Froeschlin <chr### [at] chrfrde> wrote:
> I was trying to render a 3D puzzle by intersecting generic
> puzzle tiles with a desired target shape and found it rendered
> very slowly, even when intersecting the individual tiles before
> creating a union. The effect was curious as it turned out
>
> intersection
> {
>    object {A}
>    object {B}
>    bounded_by {B}
> }
>
> was much faster than
>
> intersection
> {
>    object {A}
>    object {B}
> }
>
> After some investigation I found that the problem was related to
> the number of puzzle tiles completely outside the target shape, so
> there seems to be some problem with empty intersections. I think
> these should be discarded or at least get a small bounding box,
> but they seem to be sticking around unbounded.
>

For any CSG, a bounding box is made as a single object that is known to contain
everything in the CSG.  So for an intersection operation, the bounding box will
be big enough to contain both (or all) your objects, regardless of how big the
remaining part is.  This is espescially an issue if one or mor objects doesn't
interesect, as it still gets included in the ray testing.

Fortunately in some cases, you have the benefit of knowing what your bounded
area should be and make a manual bounding box as you have done, and greatly
speed up rendering.  However, it is much more difficult to get POV to recognize
the need for a smaller bounding box.

This is even more extreme in difference operations as POV treats them as an
intersection of the first object with inverses of the subtracting objects.
Essentially the subtractiong objects are infinite in size.  (Try rendering a
plate with 10000 round holes in it for example.)

-tgq

Post a reply to this message

Trevor G Quayle wrote:

> For any CSG, a bounding box is made as a single object that is known to contain
> everything in the CSG.  So for an intersection operation, the bounding box will
> be big enough to contain both (or all) your objects, regardless of how big the
> remaining part is.  

Are you sure about this? The intersection of two finite
objects is contained in the intersection of their bounding
boxes so this should be more efficient than you describe.
In fact it seems to work quite well for my intersections,
even though one of the shapes is large.

There is only an issue when intersections turns out
to be empty and I think this is a fixable problem.

> This is even more extreme in difference operations as POV treats them as an
> intersection of the first object with inverses of the subtracting objects.
> Essentially the subtractiong objects are infinite in size.

Of course, an infinite box doesn't help much. Still I'd expect
the bounding box of the difference to be the bounding box of the
original finite object (which is still slow for many holes).

Post a reply to this message

Christian Froeschlin <chr### [at] chrfrde> wrote:
> Trevor G Quayle wrote:
>
> > For any CSG, a bounding box is made as a single object that is known to contain
> > everything in the CSG.  So for an intersection operation, the bounding box will
> > be big enough to contain both (or all) your objects, regardless of how big the
> > remaining part is.
>
> Are you sure about this? The intersection of two finite
> objects is contained in the intersection of their bounding
> boxes so this should be more efficient than you describe.
> In fact it seems to work quite well for my intersections,
> even though one of the shapes is large.
>
> There is only an issue when intersections turns out
> to be empty and I think this is a fixable problem.
>
> > This is even more extreme in difference operations as POV treats them as an
> > intersection of the first object with inverses of the subtracting objects.
> > Essentially the subtractiong objects are infinite in size.
>
> Of course, an infinite box doesn't help much. Still I'd expect
> the bounding box of the difference to be the bounding box of the
> original finite object (which is still slow for many holes).

Post a reply to this message

Christian Froeschlin <chr### [at] chrfrde> wrote:
> Trevor G Quayle wrote:
>
> > For any CSG, a bounding box is made as a single object that is known to contain
> > everything in the CSG.  So for an intersection operation, the bounding box will
> > be big enough to contain both (or all) your objects, regardless of how big the
> > remaining part is.
>
> Are you sure about this? The intersection of two finite
> objects is contained in the intersection of their bounding
> boxes so this should be more efficient than you describe.
> In fact it seems to work quite well for my intersections,
> even though one of the shapes is large.
>
> There is only an issue when intersections turns out
> to be empty and I think this is a fixable problem.
>
> > This is even more extreme in difference operations as POV treats them as an
> > intersection of the first object with inverses of the subtracting objects.
> > Essentially the subtractiong objects are infinite in size.
>
> Of course, an infinite box doesn't help much. Still I'd expect
> the bounding box of the difference to be the bounding box of the
> original finite object (which is still slow for many holes).

You may be right.  I am uncertain I guess how intersection is treated.  Perhaps
it is just an issue with non-intersecting boxes.

For subtraction, I do know I have tried in the past as an example to make a golf
ball from a sphere with many spheres subtracted.  This was unbearably slow.  But
switching to a blob with negative blob dimples was quite fast by comparison.

Maybe better answered by someone who knows the inner workings of bounding.

-tgq

Post a reply to this message

Am 28.02.2011 18:57, schrieb Trevor G Quayle:

> For any CSG, a bounding box is made as a single object that is known to contain
> everything in the CSG.  So for an intersection operation, the bounding box will
> be big enough to contain both (or all) your objects, regardless of how big the
> remaining part is.  This is espescially an issue if one or mor objects doesn't
> interesect, as it still gets included in the ray testing.

No; actually it's just the other way round: An intersection's bounding 
box will be computed as the intersection of all its elements' bounding 
boxes, with the effect that all elements' bounding boxes include the 
/full/ intersection's bounding box.

For instance, the intersection of a sphere {<0,0,0>,1} and a 
sphere{<0,0,1>,0.5} would be computed as follows:

1st sphere bounding box = box { <-1,-1,-1>, <1,1,1> }
2nd sphere bounding box = box { <-0.5,-0.5,0.5>, <0.5,0.5,1.5> }

intersection bounding box = box {
   <max(-1,-0.5),max(-1,-0.5),max(-1,0.5)>,
   <min(1,0.5),min(1,0.5),min(1,1.5)>
}
= box { <-0.5,-0.5,0.5>, <0.5,0.5,1> }

However, if the elements' bounding boxes don't have a common 
intersection at all, this doesn't work out; e.g.:

1st element bounding box = box { <-1,-1,-1>, <1,1,1> }
2nd element bounding box = box { <-0.5,-0.5,1.5>, <0.5,0.5,2.5> }

intersection bounding box = box {
   <max(-1,-0.5),max(-1,-0.5),max(-1,1.5)>,
   <min(1,0.5),min(1,0.5),min(1,2.5)>
}
= box { <-0.5,-0.5,1.5>, <0.5,0.5,1> }

which has a "smallest z" larger than its "largest z", which 
mathematically doesn't make any sense. My first guess would be that this 
is exactly what POV-Ray computes, but that it doesn't recognize it as 
bullshit.

> This is even more extreme in difference operations as POV treats them as an
> intersection of the first object with inverses of the subtracting objects.
> Essentially the subtractiong objects are infinite in size.  (Try rendering a
> plate with 10000 round holes in it for example.)

Not exactly; with differences, the problem is not that the difference's 
bounding box would be infinite (it isn't, because the volume covered by 
the difference is obviously at most the volume of the main object), nor 
that the subtracted objects would have an infinite bounding box (they 
actually don't either, because AFAIK the bounding boxes actually don't 
contain "all that is part of the object", but "all that is part of the 
object's surface"); instead, the problem is that for each intersection 
found with the main object, each and every differenced-away element is 
tested for insideness, without using any bounding box hierarchy that 
might speed things up. (Using the full scene's bounding hierarchy might 
be too expensive with large scenes, and individual CSG objects don't 
have any "private" bounding hierarchy.)

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> Am 28.02.2011 18:57, schrieb Trevor G Quayle:
>
> > For any CSG, a bounding box is made as a single object that is known to contain
> > everything in the CSG.  So for an intersection operation, the bounding box will
> > be big enough to contain both (or all) your objects, regardless of how big the
> > remaining part is.  This is espescially an issue if one or mor objects doesn't
> > interesect, as it still gets included in the ray testing.
>
> No; actually it's just the other way round: An intersection's bounding
> box will be computed as the intersection of all its elements' bounding
> boxes, with the effect that all elements' bounding boxes include the
> /full/ intersection's bounding box.
>
> For instance, the intersection of a sphere {<0,0,0>,1} and a
> sphere{<0,0,1>,0.5} would be computed as follows:
>
> 1st sphere bounding box = box { <-1,-1,-1>, <1,1,1> }
> 2nd sphere bounding box = box { <-0.5,-0.5,0.5>, <0.5,0.5,1.5> }
>
> intersection bounding box = box {
>    <max(-1,-0.5),max(-1,-0.5),max(-1,0.5)>,
>    <min(1,0.5),min(1,0.5),min(1,1.5)>
> }
> = box { <-0.5,-0.5,0.5>, <0.5,0.5,1> }
>
> However, if the elements' bounding boxes don't have a common
> intersection at all, this doesn't work out; e.g.:
>
> 1st element bounding box = box { <-1,-1,-1>, <1,1,1> }
> 2nd element bounding box = box { <-0.5,-0.5,1.5>, <0.5,0.5,2.5> }
>
> intersection bounding box = box {
>    <max(-1,-0.5),max(-1,-0.5),max(-1,1.5)>,
>    <min(1,0.5),min(1,0.5),min(1,2.5)>
> }
> = box { <-0.5,-0.5,1.5>, <0.5,0.5,1> }
>
> which has a "smallest z" larger than its "largest z", which
> mathematically doesn't make any sense. My first guess would be that this
> is exactly what POV-Ray computes, but that it doesn't recognize it as
> bullshit.
>
> > This is even more extreme in difference operations as POV treats them as an
> > intersection of the first object with inverses of the subtracting objects.
> > Essentially the subtractiong objects are infinite in size.  (Try rendering a
> > plate with 10000 round holes in it for example.)
>
> Not exactly; with differences, the problem is not that the difference's
> bounding box would be infinite (it isn't, because the volume covered by
> the difference is obviously at most the volume of the main object), nor
> that the subtracted objects would have an infinite bounding box (they
> actually don't either, because AFAIK the bounding boxes actually don't
> contain "all that is part of the object", but "all that is part of the
> object's surface"); instead, the problem is that for each intersection
> found with the main object, each and every differenced-away element is
> tested for insideness, without using any bounding box hierarchy that
> might speed things up. (Using the full scene's bounding hierarchy might
> be too expensive with large scenes, and individual CSG objects don't
> have any "private" bounding hierarchy.)

Thanks for correcting and clearing that up for me.  I was in over my head on my
understanding of the inner workings and thought it was just an easy answer.

As far as the non-intersecting bounding box issue, perhaps someone should track
exactly how POV is handling the negative dimensions.  Perhaps there is a simple
fix in the code to clear that part up, eg either max all dimensions to 0 so
negatives aren't allowed, or ignore intersection if any dimension is less than
0.  The second is probably the best as the first can still leave a flat plate
bounding box if only one dimension is negative.

-tgq

Post a reply to this message

Am 01.03.2011 06:02, schrieb Trevor G Quayle:

> As far as the non-intersecting bounding box issue, perhaps someone should track
> exactly how POV is handling the negative dimensions.  Perhaps there is a simple
> fix in the code to clear that part up, eg either max all dimensions to 0 so
> negatives aren't allowed, or ignore intersection if any dimension is less than
> 0.  The second is probably the best as the first can still leave a flat plate
> bounding box if only one dimension is negative.

There's actually already code in POV-Ray that checks for this condition; 
it just takes an unsuitable action: Apparently presuming something went 
wrong during bounding box computations, it leaves the bounding box at 
its initialization value, which is "infinite" (and is intended to print 
a warning, but that code is disabled).

Post a reply to this message