POV-Ray : Newsgroups : povray.text.scene-files : bounding box calculator Server Time
28 Mar 2024 08:29:38 EDT (-0400)
  bounding box calculator (Message 1 to 10 of 43)  
Goto Latest 10 Messages Next 10 Messages >>>
From: jr
Subject: bounding box calculator
Date: 27 Oct 2019 11:05:01
Message: <web.5db5b0ff51c96acafeeb22ff0@news.povray.org>
hi,

as part of some stuff I'm playing with, I noticed that the bounding box of the
"Boy's Surface"[1] contains a lot of .. air.  :-)  after reading up on things, I
wrote a macro which "scans" an object's BB to find the actual dimensions (using
'inside()' tests), and print out information about how much "slack" is found[2]
between object and bounding box face(s).

[1]
<http://news.povray.org/povray.general/thread/%3Cweb.5b1bb8bbb1f83992458c7afe0%40news.povray.org%3E/>

[2] v basic still.  only distinguishes three scenarios: up to 1% space all
around, up to 5%, and over 5%.

I've tested the code with a handful of different objects, and so far, so good.
perhaps someone else will find use(s) for it too.  it is a work in progress
though, and it would be nice if one or two wanted to be "guinea pigs", beta
test, and help find bugs/problems, suggest improvements.

there is no documentation apart from a few header lines in the .inc, but the
macro is easy to use:

  macro Bounder(object, optional resolution)

where object is some object identifier, and the resolution an integer, or a
3-vector of ints, giving the number of "probes" per POV unit.

the simplest usage example is something like:
-----<snip>-----
#version 3.8;
global_settings {...}
#declare O = cylinder {...};
#include "bounder.inc"
Bounder(O,)
-----<snip>-----

uses the default resolution <50,50,50>.

the cut'n'paste stuff below shows the before and after for the 'boy-file.pov'
(with minimal adaptations, and renamed), with timings.  the difference is that
for the second run I'd added a 'clipped_by {box {}}' calculated from the values
in the "diff" lines, and a 'bounded_by {clipped_by}', as suggested in the docs.


enjoy, jr.

-----<snip>-----
the 'povparse' command is a BASH alias, shown here in case it's of interest to a
Linux user, useful when only the '#debug' output matters:
  alias povparse='nice -n 19 povray -w32 -h32 -D -F -GS -GR +i'


Script started on Sun 27 Oct 2019 12:16:05 GMT
jr@crow:1:bounder$ time povparse bta.pov
Persistence of Vision(tm) Ray Tracer Version 3.8.0-alpha.10013324.unofficial
  ...
==== [Parsing...] ==========================================================
----------[Bounder info]------------------------------------------------
  resolutions (per POV unit): <20, 20, 20>
     object "as is" (BB) min: <-6.000000, -6.000000, -6.000000>
     object "as is" (BB) max: <5.000000, 5.000000, 5.000000>
     object aligned (BB) max: <11.000000, 11.000000, 11.000000>
    axis 'X' scan resolution: 220
             probes per face: 48400
         scan axis increment: 0.05000000
          face col increment: 0.05000000
          face row increment: 0.05000000
                           -: ...scanning...
Parsing 140263K tokens
              total # probes: 3000800
    axis 'Y' scan resolution: 220
             probes per face: 48400
         scan axis increment: 0.05000000
          face col increment: 0.05000000
          face row increment: 0.05000000
                           -: ...scanning...
Parsing 289350K tokens
              total # probes: 3049200
    axis 'Z' scan resolution: 220
             probes per face: 48400
         scan axis increment: 0.05000000
          face col increment: 0.05000000
          face row increment: 0.05000000
                           -: ...scanning...
Parsing 432765K tokens
              total # probes: 3000800
    --------------------
            diff lower bound: 1.95000000,2.00000000,1.95000000
            diff upper bound: 0.95000000,0.95000000,0.95000000
  object bounding box has at least 5% "slack".
------------------------------------------------------------------------
==== [Rendering...] ========================================================
Rendered 1024 of 1024 pixels (100%)
POV-Ray finished

real 1m37.487s
user 1m36.884s
sys 0m0.041s


Script started on Sun 27 Oct 2019 12:18:31 GMT
jr@crow:4:bounder$ time povparse bt2.pov
Persistence of Vision(tm) Ray Tracer Version 3.8.0-alpha.10013324.unofficial
   ...
==== [Parsing...] ==========================================================
----------[Bounder info]------------------------------------------------
  resolutions (per POV unit): <20, 20, 20>
     object "as is" (BB) min: <-4.100000, -4.100000, -4.100000>
     object "as is" (BB) max: <4.100000, 4.100000, 4.100000>
     object aligned (BB) max: <8.200000, 8.200000, 8.200000>
    axis 'X' scan resolution: 164
             probes per face: 26896
         scan axis increment: 0.05000000
          face col increment: 0.05000000
          face row increment: 0.05000000
                           -: ...scanning...
Parsing 4616K tokens
              total # probes: 161376
    axis 'Y' scan resolution: 164
             probes per face: 26896
         scan axis increment: 0.05000000
          face col increment: 0.05000000
          face row increment: 0.05000000
                           -: ...scanning...
Parsing 9246K tokensParsing 13950K tokens
              total # probes: 161376
    axis 'Z' scan resolution: 164
             probes per face: 26896
         scan axis increment: 0.05000000
          face col increment: 0.05000000
          face row increment: 0.05000000
                           -: ...scanning...
Parsing 18627K tokensParsing 23261K tokens
              total # probes: 161376
    --------------------
            diff lower bound: 0.05000000,0.05000000,0.05000000
            diff upper bound: 0.05000000,0.05000000,0.05000000
  object bounding box is (near) optimal.
------------------------------------------------------------------------
==== [Rendering...] ========================================================
Rendered 1024 of 1024 pixels (100%)
POV-Ray finished

real 0m5.896s
user 0m5.236s
sys 0m0.006s


Post a reply to this message


Attachments:
Download 'bounder.inc.txt' (9 KB)

From: Bald Eagle
Subject: Re: bounding box calculator
Date: 27 Oct 2019 16:35:06
Message: <web.5db5fe5b34d8ef064eec112d0@news.povray.org>
"jr" <cre### [at] gmailcom> wrote:

> I've tested the code with a handful of different objects, and so far, so good.
> perhaps someone else will find use(s) for it too.  it is a work in progress
> though, and it would be nice if one or two wanted to be "guinea pigs", beta
> test, and help find bugs/problems, suggest improvements.

Sounds nice.
It brings to mind some of the stuff I've played with concerning isosurfaces,
parametrics, creating meshes from objects in SDL, and working with the camera
view frustum.

First, maybe add the option of making two wireframe AA-BB's - the original, and
the optimized so that the result can be seen in a render.

Second - this is dealing with axis-aligned bounding boxes, which immediately
brings up a million questions about what if I have a long, narrow box that's at
45 degrees to 2 axes .... is there some way to optimize the orientation of the
object itself.
Especially if you try to apply this to an infinitely long cylinder, or plane,
or....

I always get the feeling that we might be trying to reinvent some wheel that may
exist - somewhere, out there - in RenderMan or Blender, or Grasshopper, or Maya,
or....

I used to shim nuclear magnetic resonance spectrometers to get a good clean
spectrum and a high signal-to-noise ratio.  But there were lots of knobs for
strange "axes" of the magnetic field, and we only had a "trace" signal that went
up or down.
(28 shims available, which are on-axis: Z1, Z2, Z3, Z4, Z5, Z6 and off-axis: X,
Y, XZ, YZ, XZ2, YZ2, XZ3, YZ3, XZ4, YZ4, X2-Y2, XY, (X2-Y2)Z, XYZ, (X2-Y2)Z2,
XYZ2, (X2-Y2)Z3, XYZ3, X3, Y3, X3Z, Y3Z
So we were flying blind around this N-dimensional field, and you had to stay
aware of the fact that just because the signal went up didn't mean for sure that
the shim settings were getting better - because it might just be a local maximum
that wasn't as high as the global maximum, and you might want to traverse a
region in a local minimum in order to get over to that global maximum - so
sometimes a weaker signal was good - in the short run.

"So what, Bill, you incoherent maniac?"

;)  Well, - what if we try to calculate a bounding _sphere_ from a set of
trace() results, and then run another series of traces or insidedness tests when
we squish that sphere into a spheroid or ellipsoid?
Graph those results.   Look at them.   I'm sure they'll say something.
Just like the trace level on the NMR, we'd be looking for a global _minimum_ on
each of the axes of the ellipsoid, that tightly girdle the shape.
Then you'd have 3 axes of the ellipsoid, and could orient those axes to the
global axes, and THEN do the AABB.

I really need to go through things like the Graphics Gems series, (and IIRC
there is a GPU Gems series as well,) that may have some great algorithms that we
can use.


Post a reply to this message

From: Bald Eagle
Subject: Re: bounding box calculator
Date: 27 Oct 2019 17:15:00
Message: <web.5db6083b34d8ef064eec112d0@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:

> I always get the feeling that we might be trying to reinvent some wheel that may
> exist - somewhere, out there -

Like this:

https://www.geometrictools.com/Documentation/MinimumVolumeBox.pdf

from:

https://www.geometrictools.com/Source/ComputationalGeometry.html


Post a reply to this message

From: Bald Eagle
Subject: Re: bounding box calculator
Date: 27 Oct 2019 18:10:00
Message: <web.5db6157d34d8ef064eec112d0@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:

> we squish that sphere into a spheroid or ellipsoid?
> Graph those results.   Look at them.   I'm sure they'll say something.
> Just like the trace level on the NMR, we'd be looking for a global _minimum_ on
> each of the axes of the ellipsoid, that tightly girdle the shape.
> Then you'd have 3 axes of the ellipsoid,

Sounds great, Bill.
Some folks already did that, like 30 years ago...
Good job...

http://geomalgorithms.com/a08-_containers.html
"Nevertheless, especially in higher dimensions, the bounding ellipsoid is
superior to the minimal cuboid in many ways. It is unique, whereas the minimal
cuboid is not. There is a reasonable algorithm to implement it. And it is a good
approximation of the object it contains, much better than the minimal cuboid."


https://www.ics.uci.edu/~eppstein/junkyard/rcg.html

https://inf.ethz.ch/personal/emo/PublFiles/SmallEnclDisk_LNCS555_91.pdf


Post a reply to this message

From: jr
Subject: Re: bounding box calculator
Date: 27 Oct 2019 19:05:00
Message: <web.5db6217834d8ef06feeb22ff0@news.povray.org>
hi,

"Bald Eagle" <cre### [at] netscapenet> wrote:
> "jr" <cre### [at] gmailcom> wrote:
> > I've tested the code with a handful of different objects, and so far, so good.
> > perhaps someone else will find use(s) for it too.  it is a work in progress
> > though, and it would be nice if one or two wanted to be "guinea pigs", beta
> > test, and help find bugs/problems, suggest improvements.
>
> Sounds nice.

ah.  'useful' is the adjective I was [fw]ishing for.  ;-)

> ...
> First, maybe add the option of making two wireframe AA-BB's - the original, and
> the optimized so that the result can be seen in a render.

future stuff, perhaps.  :-)  the idea is simply to get guide figures to tighten
the bounds if wanted/necessary.

> Second - this is dealing with axis-aligned bounding boxes, which immediately
> brings up a million questions about what if I have a long, narrow box that's at
> 45 degrees to 2 axes .... is there some way to optimize the orientation of the
> object itself.

no.  the object is where it is.  a copy of the object is aligned to origin to
make the calculations .. bearable.  (up to) the diff figures can be then be
applied to the original.

"optimise the orientation" in which way?  not sure I understand.

> Especially if you try to apply this to an infinitely long cylinder, or plane,
> or....

yeah.  as I wrote, the macro uses 'inside()' to do the probing, with all that
implies.  in the end though one has to trust the user to know not to drive
screws with a hammer.

> ...
> ;)  Well, - what if we try to calculate a bounding _sphere_ ...

too advanced for me.  (as are your references in the other two follow-ups I
read)

> ...


regards ,jr.


Post a reply to this message

From: Thomas de Groot
Subject: Re: bounding box calculator
Date: 28 Oct 2019 04:20:10
Message: <5db6a4ba$1@news.povray.org>
Op 27/10/2019 om 16:00 schreef jr:
> as part of some stuff I'm playing with, I noticed that the bounding box of the
> "Boy's Surface"[1] contains a lot of .. air.:-)   after reading up on things, I
> wrote a macro which "scans" an object's BB to find the actual dimensions (using
> 'inside()' tests), and print out information about how much "slack" is found[2]
> between object and bounding box face(s).
> 

Thanks! I am certainly going to play with this useful little toy. I 
second Bald Eagle's suggestion about additional wireframes. I am a 
visual guy, and such things would help me no end.

-- 
Thomas


Post a reply to this message

From: jr
Subject: Re: bounding box calculator
Date: 28 Oct 2019 10:10:01
Message: <web.5db6f57834d8ef06feeb22ff0@news.povray.org>
hi,

Thomas de Groot <tho### [at] degrootorg> wrote:
> Op 27/10/2019 om 16:00 schreef jr:
> > ... a macro which ...
>
> Thanks! I am certainly going to play with this useful little toy.

thank you for giving it a try.  since it is a WIP, feedback on the .. user
"experience", problems etc will be valuable.

> I second Bald Eagle's suggestion about additional wireframes. I am a
> visual guy, and such things would help me no end.

that makes three if us.  :-)  blame POV-Ray (really, I mean it).  so I use a "X
Windows" environment, and here's provision for the following: I write a small UI
utility 'A' which can make use of the abilities of program 'B', so in 'A' I
create an empty frame (window) and when I run 'B' I tell it btw, here's a handle
to a window, please display yourself in that, and voila.  alas, the 3.6.x
versions of POV-Ray were the last "good X Windows citizens", since then it has
yoked itself to the SDL, a multimedia+gaming "sub-system", which doesn't play by
the same rules.  </rant>

however, I'd be happy to cooperate on solutions, if you (and or Bald Eagle) can
see a way to utilise the 'Bounder' output.

regards, jr.


Post a reply to this message

From: jr
Subject: Re: bounding box calculator
Date: 29 Oct 2019 10:15:01
Message: <web.5db8483634d8ef06feeb22ff0@news.povray.org>
"jr" <cre### [at] gmailcom> wrote:
> ... I wrote a macro which "scans" an object's BB ...

find attached an updated version of 'Bounder'.

the changes are largely cosmetic, I've tried to make the output less confusing,
and now refer to "inside() calls" instead of "probes" etc.  under the hood I
managed to tighten things up a bit, removing a few variables and ..
embarrassments.


enjoy, jr.


Post a reply to this message


Attachments:
Download 'bounder.inc.txt' (8 KB)

From: Thomas de Groot
Subject: Re: bounding box calculator
Date: 3 Nov 2019 03:33:38
Message: <5dbe90e2@news.povray.org>
Op 29/10/2019 om 15:09 schreef jr:
> "jr" <cre### [at] gmailcom> wrote:
>> ... I wrote a macro which "scans" an object's BB ...
> 
> find attached an updated version of 'Bounder'.
> 
> the changes are largely cosmetic, I've tried to make the output less confusing,
> and now refer to "inside() calls" instead of "probes" etc.  under the hood I
> managed to tighten things up a bit, removing a few variables and ..
> embarrassments.
> 

I suggest you change the wording in line 125, from:

bndr_emit3V("object aligned (BB) max",dims_,6)

into:

bndr_emit3V("object aligned (BB) dimension",dims_,6)

I suppose that was an overlook ;-)

-- 
Thomas


Post a reply to this message

From: jr
Subject: Re: bounding box calculator
Date: 3 Nov 2019 09:00:02
Message: <web.5dbedcac34d8ef06feeb22ff0@news.povray.org>
hi,

Thomas de Groot <tho### [at] degrootorg> wrote:
> Op 29/10/2019 om 15:09 schreef jr:
> > "jr" <cre### [at] gmailcom> wrote:
> >> ... I wrote a macro which "scans" an object's BB ...
> > find attached an updated version of 'Bounder'.
> > ...
> I suggest you change the wording in line 125, from:
> bndr_emit3V("object aligned (BB) max",dims_,6)
> into:
> bndr_emit3V("object aligned (BB) dimension",dims_,6)
> I suppose that was an overlook ;-)

yes, another one.  :-)  thanks.  after some thought I've changed it to "BB
aligned dimensions".  also, I've removed the parentheses in the lines above in
output, and the dashed line above the 'difference' lines.  I shall wait a few
days before posting a final version, in case other improvements get suggested.


regards, jr.


Post a reply to this message

Goto Latest 10 Messages Next 10 Messages >>>

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