POV-Ray : Newsgroups : povray.programming : bounding boxes problem and solution Server Time
3 Jul 2024 06:14:57 EDT (-0400)
  bounding boxes problem and solution (Message 3 to 12 of 12)  
<<< Previous 2 Messages Goto Initial 10 Messages
From: ABX
Subject: Re: bounding boxes problem and solution
Date: 1 Dec 2003 08:08:39
Message: <dvemsvosrq540v1i0fhtkuqk5m1qdfjtkv@4ax.com>
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

From: Slime
Subject: Re: bounding boxes problem and solution
Date: 1 Dec 2003 08:19:09
Message: <3fcb3fcd$1@news.povray.org>
> 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

From: Christopher James Huff
Subject: Re: bounding boxes problem and solution
Date: 1 Dec 2003 14:13:28
Message: <cjameshuff-4B130B.14124301122003@netplex.aussie.org>
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

From: Andrew Clinton
Subject: Re: bounding boxes problem and solution
Date: 1 Dec 2003 21:40:02
Message: <web.3fcbfb50a497fd62611ee4e60@news.povray.org>
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

From: Andrew Clinton
Subject: Re: bounding boxes problem and solution
Date: 1 Dec 2003 21:45:02
Message: <web.3fcbfc04a497fd62611ee4e60@news.povray.org>
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

From: ABX
Subject: Re: bounding boxes problem and solution
Date: 2 Dec 2003 01:34:34
Message: <l7cosv8kfg5ofeb3grs6jdlng4khvhpa5d@4ax.com>
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

From: Slime
Subject: Re: bounding boxes problem and solution
Date: 2 Dec 2003 18:52:53
Message: <3fcd25d5@news.povray.org>
> 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

From: Andreas Kaiser
Subject: Re: bounding boxes problem and solution
Date: 9 Dec 2003 06:23:00
Message: <3fd59943.1015270521@news.povray.org>
"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

From: Andrew Clinton
Subject: Re: bounding boxes problem and solution
Date: 9 Dec 2003 20:00:02
Message: <web.3fd66ec7a497fd62611ee4e60@news.povray.org>
While your method sounds very nice, I'm not sure how you are attacking some
of the practical problems... For example, for most primitive types you will
need to choose the set of planes to use for bounding.  If you choose the
wrong set (eg. the 6 axis planes for a sphere) then your method really
isn't better that what I described.  If you want a more accurate set of
planes you will need more (for a sphere you would need infinity), which
will make it slow.  Also, you will need to define methods to create
efficient sets of bounding planes for each object if you want it to be
fast.

How are you doing the degeneration to a AB?  It doesn't seem like it would
be easy...

Isn't a set of bounding planes called bounding slabs?

Andrew


Post a reply to this message

From: Andreas Kaiser
Subject: Re: bounding boxes problem and solution
Date: 10 Dec 2003 09:33:08
Message: <3fd7284e.83234655@news.povray.org>
"Andrew Clinton" <ajc### [at] uwaterlooca> wrote:

>While your method sounds very nice, I'm not sure how you are attacking some
>of the practical problems... For example, for most primitive types you will
>need to choose the set of planes to use for bounding.  If you choose the

You are right, but this is the only object specific part of the
bounding planes. From then on (keeping track of transformations and
calculating the resulting AABB) everything is generic (independent of
specific object type).

>wrong set (eg. the 6 axis planes for a sphere) then your method really
>isn't better that what I described.  If you want a more accurate set of
>planes you will need more (for a sphere you would need infinity), which
>will make it slow.  Also, you will need to define methods to create
>efficient sets of bounding planes for each object if you want it to be
>fast.

My goal was to create and keep a 'good enough' AABB, not a perfect
one. Your sphere example: I just use the 6 axis planes. Sphere
intersection is so cheap that it doesn't matter if the AABB isn't
perfect.

>
>How are you doing the degeneration to a AB?  It doesn't seem like it would
>be easy...

There is no longer a degeneration due to transformations.
Do you mean the calculation of an AABB from a set of bounding planes?
That is not so difficult, simply calculate the edge/corner of each
pair/triple of bounding planes.

>
>Isn't a set of bounding planes called bounding slabs?

May be, but as i used POV's 'plane' object i called it bounding plane.

Andreas


Post a reply to this message

<<< Previous 2 Messages Goto Initial 10 Messages

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