POV-Ray : Newsgroups : povray.programming : CSG Bounding box algorithm Server Time: 10 Dec 2018 07:30:50 GMT
  CSG Bounding box algorithm (Message 1 to 10 of 10)  
From: Bald Eagle
Subject: CSG Bounding box algorithm
Date: 23 Aug 2017 12:10:01
Message: <web.599d7065357d842fc437ac910@news.povray.org>
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?

I worked out some (messy but fully functional) code to do this, and it appears
to handle the few typical cases that I tested it with.

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)

If this is still an issue, are there certain cases that are especially
problematic for certain CSG operations?
Could we develop this into a small, fast part of the POV-Ray source code?


Thanks


Post a reply to this message

From: clipka
Subject: Re: CSG Bounding box algorithm
Date: 23 Aug 2017 18: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

From: omniverse
Subject: Re: CSG Bounding box algorithm
Date: 24 Aug 2017 01:05:01
Message: <web.599e2632818ca7929c5d6c810@news.povray.org>
clipka <ano### [at] anonymousorg> wrote:
> 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.
--->8---
> > 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.
---8<---
> > 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.

Interesting, as usual.

I was wondering about this after coming across something about the automatic
bounding from the version 3.5 sample scene chess2.pov while rendering some of
those old files.
Chess2 uses quartics and I changed them to isosurfaces, cone and cylinder for
the various shapes some time ago when I modified it for version 3.7.

Except for the Rook chess piece, removal of the manual bounding appears okay on
all other pieces, and the reason I remember commenting that out for v3.5 was
because of improvements for automatic bounding made back then.
You know, progress; so was thinking move ahead and leave manual bounding behind
if at all possible.

No idea how the malformed Rook was overlooked, if it always was, and I'm unable
to run version 3.5 right now to check on it from there so I can only look at it
from 3.7 with version setting of 3.5. At least the bounded_by { sphere { <0, 5,
0>, 5.831 } } is still there allowing uncommenting as a fix.

According to what is said here, I suppose that particular CSG object must be a
problem due to the intersecting planes and quartics (infinite shapes). And
curiously, for me anyhow, is that the deformation changes depending on
orientation or camera view. From chess2.pov:

#version 3.5;

#include "shapes.inc"

#declare Cylinder_Y =
 quadric
  {<1, 0, 1>,
   <0, 0, 0>,
   <0, 0, 0>, -1
  }

#declare Rook = union {
   intersection {
      union {
         plane { +x, -0.5 }
         plane { -x, -0.5 }
         plane { y, 9 }
      }

      union {
         plane { +z, -0.5 }
         plane { -z, -0.5 }
         plane { y, 9 }
      }

      plane { y, 10 }
      object { Cylinder_Y scale <2, 1, 2> }
      object { Cylinder_Y scale <1.2, 1, 1.2> inverse }
      plane { -y, -8 }
   }

   intersection {
      plane { y, 8 }
      object { Hyperboloid_Y
         scale <1, 1.5, 1>
         translate 5.401924*y
      }
      plane { -y, -3 }
   }

   sphere { <0, 0, 0>, 1
      scale <2.5, 0.5, 2.5>
      translate 2.8*y
   }

//   object { PieceBase }
}

#declare WRook = object {
   Rook

   // bounded_by { sphere { <0, 5, 0>, 5.831 } }

   texture {
     // WWood
      pigment { rgb 1 }
   }
}

object {
    WRook
   // rotate <-90,90,0>/2 // change shape?
}

light_source {<10,100,-100>,1}
camera {location <0,6,-18>}


Post a reply to this message

From: clipka
Subject: Re: CSG Bounding box algorithm
Date: 24 Aug 2017 08:48:26
Message: <599e92da@news.povray.org>
Am 24.08.2017 um 03:04 schrieb omniverse:

> I was wondering about this after coming across something about the automatic
> bounding from the version 3.5 sample scene chess2.pov while rendering some of
> those old files.
...
> According to what is said here, I suppose that particular CSG object must be a
> problem due to the intersecting planes and quartics (infinite shapes).

Thanks for spotting this one.

Looks like the b'box computation for quadrics (sorry, not quartics; got
that wrong in the previous post) fails to respect the `inverse` keyword
for /some/ reason.

> And
> curiously, for me anyhow, is that the deformation changes depending on
> orientation or camera view.

Bounding boxes have that effect. Essentially your shape gets clipped in
"image space" by the outline of the b'box, which changes shape as the
b'box is viewed from different angles: Head-on it's a rectangle, while
at other angles it changes into an irregular hexagon.


Post a reply to this message

From: omniverse
Subject: Re: CSG Bounding box algorithm
Date: 24 Aug 2017 09:50:01
Message: <web.599ea041818ca7929c5d6c810@news.povray.org>
clipka <ano### [at] anonymousorg> wrote:
> Am 24.08.2017 um 03:04 schrieb omniverse:
>
> > I was wondering about this after coming across something about the automatic
> > bounding from the version 3.5 sample scene chess2.pov while rendering some of
> > those old files.
> ...
> > According to what is said here, I suppose that particular CSG object must be a
> > problem due to the intersecting planes and quartics (infinite shapes).
>
> Looks like the b'box computation for quadrics (sorry, not quartics; got
> that wrong in the previous post) fails to respect the `inverse` keyword
> for /some/ reason.

Oops, yep, quadric is what I meant too. Checked with versions 3.6.2, 3.7.0 and
that same Rook example I posted here is okay. It's 3.7.1-rc1 causing the missing
parts. Likewise same for beta 9.

> > curiously, for me anyhow, is that the deformation changes depending on
> > orientation or camera view.
>
> Bounding boxes have that effect. Essentially your shape gets clipped in
> "image space" by the outline of the b'box, which changes shape as the
> b'box is viewed from different angles: Head-on it's a rectangle, while
> at other angles it changes into an irregular hexagon.

Makes sense now that you said it, and "bounding slabs" per the docs, I should
have obviously read that first. I get to thinking there might be fancy things
going on like sphere shapes for bounding being used automatically as well.

And I forget about the ability to show those bounding boxes too. Or so I
thought... hmmmm... doesn't Vista_Buffer=on or +UV do that?
Tried just now in v3.6.2, v3.7.0, v3.7.1-beta9 and v3.7.1-rc1, nothing seen of
bounding boxes in render window.


Post a reply to this message

From: Bald Eagle
Subject: Re: CSG Bounding box algorithm
Date: 24 Aug 2017 11:55:00
Message: <web.599ebe8e818ca792c437ac910@news.povray.org>
clipka <ano### [at] anonymousorg> wrote:

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

Sorry - I was having a hard time understanding exactly what the situation was,
and not having access to that page and the SDL for those specific instances left
me to my own devices.   And by that time, I was pretty damned tired, so ....

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

Because I was just adapting some internet question-answerer's ridiculous code,
and they had a zero in their min/max formulae - presumably because they were
concerned with the _volume_ of the intersection .... and I was just too frazzled
to work it out from scratch like I should have.

> 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.

Yes, I suspected that, but the Little Voice was too tiny, and my fatigued brain
inertia was too strong.

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

I see that a lot better now, and understand what those docs were getting at -
and why those cases present such difficulty.  Sometimes, for whatever reason,
the wording of some sections makes it a little hard to follow.


Post a reply to this message

From: Bald Eagle
Subject: Re: CSG Bounding box algorithm
Date: 24 Aug 2017 12:05:01
Message: <web.599ec080818ca792c437ac910@news.povray.org>
"omniverse" <omn### [at] charternet> wrote:

> Oops, yep, quadric is what I meant too. Checked with versions 3.6.2, 3.7.0 and
> that same Rook example I posted here is okay. It's 3.7.1-rc1 causing the missing
> parts. Likewise same for beta 9.

Looks like I have a real knack for finding these little bugs - even when I don't
know they're there, and I'm doing something completely wrong and pointless  :D

> And I forget about the ability to show those bounding boxes too. Or so I
> thought... hmmmm... doesn't Vista_Buffer=on or +UV do that?
> Tried just now in v3.6.2, v3.7.0, v3.7.1-beta9 and v3.7.1-rc1, nothing seen of
> bounding boxes in render window.

That would be a neat feature!
I checked the docs and didn't see anything like that.
I've written my own bounding-box visualization macro to do that, as well as show
the min/max extent in the debug window ("WHERE'D my object{} go????")
I think I threw in my camera-object-distance based auto-cylinder radius thing to
give a nice consistent look to it as well whether it's 5 units or 50,000 units
from the camera.
Still needs a slight bit of fine-tuning.


Post a reply to this message

From: omniverse
Subject: Re: CSG Bounding box algorithm
Date: 24 Aug 2017 17:35:03
Message: <web.599f0e15818ca7929c5d6c810@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:
> "omniverse" <omn### [at] charternet> wrote:
>
> > Oops, yep, quadric is what I meant too. Checked with versions 3.6.2, 3.7.0 and
> > that same Rook example I posted here is okay. It's 3.7.1-rc1 causing the missing
> > parts. Likewise same for beta 9.
>
> Looks like I have a real knack for finding these little bugs - even when I don't
> know they're there, and I'm doing something completely wrong and pointless  :D
>
> > And I forget about the ability to show those bounding boxes too. Or so I
> > thought... hmmmm... doesn't Vista_Buffer=on or +UV do that?
> > Tried just now in v3.6.2, v3.7.0, v3.7.1-beta9 and v3.7.1-rc1, nothing seen of
> > bounding boxes in render window.
>
> That would be a neat feature!
> I checked the docs and didn't see anything like that.

Found what it was, Draw_Vistas=on or +UD on command line, goes back to v3.1g.
Although I'm not seeing it in v3.6.2 and above there's actually a message stream
acknowledgement of it being "on".

See v3.1g doc: http://www.cacr.caltech.edu/~slombey/asci/povray/pov134.htm

> I've written my own bounding-box visualization macro to do that, as well as show
> the min/max extent in the debug window ("WHERE'D my object{} go????")
> I think I threw in my camera-object-distance based auto-cylinder radius thing to
> give a nice consistent look to it as well whether it's 5 units or 50,000 units
> from the camera.
> Still needs a slight bit of fine-tuning.

Well that's something I've needed time and again!
Imagine how a render display would look if it could show arrows and labels for
everything outside of view (ignoring the potential complexity!), or a way to
make the camera find things with a simple look_at ObjectName (by extracting its
defined location vector).


Post a reply to this message

From: Bald Eagle
Subject: Re: CSG Bounding box algorithm
Date: 24 Aug 2017 18:35:00
Message: <web.599f1c34818ca792c437ac910@news.povray.org>
"omniverse" <omn### [at] charternet> wrote:

> Well that's something I've needed time and again!
> Imagine how a render display would look if it could show arrows and labels for
> everything outside of view (ignoring the potential complexity!), or a way to
> make the camera find things with a simple look_at ObjectName (by extracting its
> defined location vector).

Yes, that's why I wrote it - I may have posted it here, if not, I'll do so soon
(remind me if I have a memory lapse)

There may be some include file / usage flag coding errors, but I hope to get
those fixed soon.

[incidentally, there are some issues with things like shapes2.inc that require
shapes.inc to work without error ...]

I'm also working on some experimental code to make "parameterized shapes" -
where you can have easy access to pre-calculated things like corners or edges or
faces of cubes, etc., as well as assign an object number to each new thing you
add to a scene.

I think that with a raytracer where mostly everything is defined with code, then
there needs to be a lot more helpful tools and examples, and algorithms, and
newbie-friendly, or advanced-accelerating snippets so that there aren't so many
instances where a seemingly small task turns into a computer-science-coding
_project_ to get past that single hurdle.


Post a reply to this message

From: omniverse
Subject: Re: CSG Bounding box algorithm
Date: 25 Aug 2017 12:05:00
Message: <web.59a011df818ca7929c5d6c810@news.povray.org>
clipka <ano### [at] anonymousorg> wrote:
> Looks like the b'box computation for quadrics (sorry, not quartics; got
> that wrong in the previous post) fails to respect the `inverse` keyword
> for /some/ reason.

Curiouser and curiouser, I was able to get the correct CSG shape (almost) by
changing the Cylinder_Y to:

 quadric
  {<1, 0, 1>,
   <0, 0.000000001, 0>, // one billionth
   <0, 0, 0>, -1
  }

Not perfect because of a slight xz offset, which can be seen when enclosing it
with semi-transparent cylinders with the same size.

Not only that, this causes Bald Eagle's bounding macro to go wild, reporting the
dimensions to be 10 billion in every direction from <0,0,0>.

Seems like a precision problem, but I wouldn't know so thought I would mention
this here in case it means something.


Post a reply to this message

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