I've been looking through the code that is used by POV-Ray to create
bounding boxes for objects, and have found a fairly serious performance
issue for bounding box creation with csg objects.  The problem can be
observed with this very simple scene:

------

camera {
 location <0,0,-4>
 look_at 0
}
light_source {
 <-10,10,-10>
 color rgb 1
}
intersection {
 sphere {
  <0.5,0,0>,1
 }
 sphere {
  <-0.5,0,0>,1
 }
 rotate z*45
 rotate z*-45
 pigment { color rgb 1 }
}

--------

What I observe is that when the scene is rendered with the transformations
on the intersection{}, there is a increase in the number of rays tested
against the intersection of about 4x, even though the scene renders exactly
the same way as without the transformations.

The problem results from the fact that bounding boxes for csg objects are
expanded independently for every transformation that is applied to the csg
while parsing, without considering the effect on the underlying objects.

I think that one way this could be fixed is by separating the bounding box
creation code from parsing.  This could be done by removing all the code
from parse.cpp that computes object bounding boxes, removing all calls to
Recompute_BBox from per-object transformation methods, and removing all
calls to Compute_*_BBox from per-object transformation methods.  Then, the
Compute_BBox method could be made a standard method on all objects, and a
new routine could be made that iterates through all the objects and
produces bounding boxes using the general Compute_BBox method.  This could
be done at some time later than parsing.  This would solve the problem
above, because the CSG bounding box compute method could correctly take
into account the bounding boxes of its children AFTER all transformations
have been applied.  It would also clean up the code.

I'm wondering if anyone has input on this solution?  I would like to
implement something like this in my patch.  If there is some reason that it
will not work as described let me know.

Andrew

Post a reply to this message

> I'm wondering if anyone has input on this solution?  I would like to
> implement something like this in my patch.  If there is some reason that
it
> will not work as described let me know.

I don't know much about bounding box in povray but your solution will
probably break min/max_extent .. Anyway, better bbox for csg would certainly
be cool :)

M

Post a reply to this message

On Sun, 30 Nov 2003 18:07:36 EST, "Andrew Clinton" <ajc### [at] uwaterlooca>
wrote:
> rotate z*45
> rotate z*-45

I would suggest to change Parse_Object_Mods in parse.cpp to cause above lines
to be executed as in 

transform{
  rotate z*45
  rotate z*-45
}

(Storing transformations in Local_Matrix and applying then on exit from
Parse_Object_Mods or if some object modifier needs bounding box to be
specified)

ABX

Post a reply to this message

> The problem results from the fact that bounding boxes for csg objects are
> expanded independently for every transformation that is applied to the csg
> while parsing, without considering the effect on the underlying objects.

Ouch.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

In article <3fcb359b$1@news.povray.org>, "Mael" <mae### [at] hotmailcom> 
wrote:

> I don't know much about bounding box in povray but your solution will
> probably break min/max_extent ..

Not necessarily. Bounding of a shape could be computed when those 
functions are called. The main thing is that they need to be completely 
recomputed when transformed, rather than repeatedly transforming the 
basic bounding box.


> Anyway, better bbox for csg would certainly be cool :)

It certainly would...

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

ABX wrote:
>
>I would suggest to change Parse_Object_Mods in parse.cpp to cause above lines
>to be executed as in
>
>transform{
>  rotate z*45
>  rotate z*-45
>}
>
>(Storing transformations in Local_Matrix and applying then on exit from
>Parse_Object_Mods or if some object modifier needs bounding box to be
>specified)
>
>ABX
>

That's not the worst of the problem...  Even if there were only one
transformation eg.

intersection { sphere{...} sphere{...} rotate z*45 }

the final bounding box might not be the tightest, because it assumes that
the rotated spheres are bounded like rotated boxes.  Of course the rotated
sphere is bounded tighter than a rotated box.

The only way to fix this is to compute all the bounding boxes from the
bottom up after all the transformations have been parsed and applied.

Andrew

Post a reply to this message

Christopher James Huff wrote:
>
>Not necessarily. Bounding of a shape could be computed when those
>functions are called. The main thing is that they need to be completely
>recomputed when transformed, rather than repeatedly transforming the
>basic bounding box.
>

You are right, min_extent will need to be modified to take into account
these changes.

With the responses so far, I think I'll go ahead with it (it should not be
too much work...)

Andrew

Post a reply to this message

On Mon,  1 Dec 2003 21:39:12 EST, "Andrew Clinton" <ajc### [at] uwaterlooca>
wrote:
> The only way to fix this is to compute all the bounding boxes from the
> bottom up after all the transformations have been parsed and applied.

Fine, but doing it in another step after parsing coan make it impossible to
effectively use bboxes during parsing (in trace(), in patches with pigments
delivering rendering of other parts of the scene). Applying from the bottom
can be still achieved in parsing object modifiers rather than in another stage
of processing between parsing and rendering.

ABX

Post a reply to this message

> Fine, but doing it in another step after parsing coan make it impossible
to
> effectively use bboxes during parsing (in trace(), in patches with
pigments
> delivering rendering of other parts of the scene).

The best way to handle this is probably to:

 - keep track of the object's transformation
 - during parsing, when the bounding box is called for (it can be made into
a function call or something for parsing-related functions), compute it from
the current transformation. Remember it in case it is needed again before
the object is transformed again, but once the object has been transformed,
throw away the current bounding box. (And set a flag that it needs to be
recomputed.) Note that the "base" bounding box will have to be stored
separately or recalculated each time the true bounding box is recalculated.
 - after parsing, calculate the final bounding box (from the base bounding
box with the final transformation).

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

"Andrew Clinton" <ajc### [at] uwaterlooca> wrote:

>[...]

>The problem results from the fact that bounding boxes for csg objects are
>expanded independently for every transformation that is applied to the csg
>while parsing, without considering the effect on the underlying objects.
>
>[...]

This happens not only for csg objects but for almost any object.
Successive transformations lead to a degeneration of bounding boxes.
IMHO the solution is to use bounding planes during the parsing stage
(I've done this in my private version i'm working on for some years
now :).
The intersection of all bounding planes makes up the bounding volume
of an object.
When the scene has been parsed completely, the post-processing stage
is entered where the final axis aligned bounding box for each object
is calculated.

The benefits are:
- no degradation due to transformations
- cleaner code: you can remove most of the object specific
  recalculation when transforming an object. Any bounding plane can
  simply be transformed without any object specific handling.
- CSG Intersections can be bounded much more efficiently. For example
  imagine the intersection of several planes that make up some kind of
  Crystal (there's an example scene in the distribution). As these
  planes are not oriented towards the coordinate system's axis, each
  individual plane has an inifinite bounding box as has the resulting
  CSG.
  Using bounding planes instead you get an bounding box that fits the
  intersection object perfectly.

Intersection of CSG-Intersection object can be improved significantly
but i think i will present this for discussion in another post.

Andreas

Post a reply to this message