"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

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

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

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

"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)

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

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

Thomas de Groot <tho### [at] degrootorg> wrote:

> >> ... I wrote a macro which "scans" an object's BB ...
> >
> > find attached an updated version of 'Bounder'.

So - those are pretty impressive differences between what POV-Ray does and what
you trim it down to!  :O

The methods I suggested are probably too complex to see any implementation any
time soon, but maybe if someone who reads and translates c++ or other languages
into SDL faster (and more accurately) than I can, converts a script or two -
then it would be a powerful tool for this as well as point clouds and other
tasks.
I doubt they'd be included into source - but I can dream a little.


I'm curious about how your BB compares to the native one aside from just size.
Does it shift?
Does the center move?  Is the space on either side equal for all 3 axes?
Presumably your bounding box is TIGHT - if you difference away an inverse box,
do you get points of overlap / coincident surfaces?
I'm just wondering if you ought to include a tiny buffer of 2x10E-6 or whatever
the safe distance is on either side, depending on usage.

Maybe have a switch in the macro call to omit or include that buffer space.

Perhaps an interesting addition would be to add an animation .ini file that
rotates the CSG object around an axis by some fraction of 45 degrees and then
does the analysis - to see if the _AA_BB gets any smaller.




Pretty nice work, and a striking demonstration of how much empty space an
automatically generated bounding box can have.
I knew there was some, but:   WOW.

I can see this being really useful for BB dependent operations like scanning
with trace (), and probably a few others that I can't clearly envision at the
moment.  Basically anywhere that a lot of ray-object intersections need to be
tested.


This is solid.

Post a reply to this message

hi,

"Bald Eagle" <cre### [at] netscapenet> wrote:
> > >> ... I wrote a macro which "scans" an object's BB ...
> > > find attached an updated version of 'Bounder'.
>
> So - those are pretty impressive differences between what POV-Ray does and what
> you trim it down to!  :O

agree.  for the Boy's Surface which got me going, the BB went from 11^3 units to
8.2^3, a reduction of well over 50%.

> The methods I suggested are probably too complex to see any implementation any
> time soon, but maybe if someone who reads and translates c++ or other languages
> into SDL faster (and more accurately) than I can, converts a script or two -
> then it would be a powerful tool for this as well as point clouds and other
> tasks.
> I doubt they'd be included into source - but I can dream a little.

as I wrote, I'm game for collaboration.  if you can express the spherical
bounding you're thinking off as "pseudo code" at least, I'm sure we could work
on something.

> I'm curious about how your BB compares to the native one aside from just size.
> Does it shift?
> Does the center move?  Is the space on either side equal for all 3 axes?
> Presumably your bounding box is TIGHT - if you difference away an inverse box,
> do you get points of overlap / coincident surfaces?
> I'm just wondering if you ought to include a tiny buffer of 2x10E-6 or whatever
> the safe distance is on either side, depending on usage.

the algorithm goes something like this, for each axis:
  - using the resolution, work out the required axis scan increments.
  - work along the scan axis until you hit the object:
    - scan the "face" looking +axis.  if no inside() test succeeded, remember
      that face as outside.
    - scan the "face" looking -axis.  as above.

the advantage is that the last stored coords are always outside of the object.
the art, I guess, will be finding the lowest resolution "good" for the object.
(low res like for the Boy's Surface wouldn't work for, say, a model of a sea
urchin, where one would presumably miss many of the spikes)

> Maybe have a switch in the macro call to omit or include that buffer space.

the 'Bounder' is only meant to give you (the user) guide figures, by up to which
you can tighten the BB if useful.

> Perhaps an interesting addition would be to add an animation .ini file that
> rotates the CSG object around an axis by some fraction of 45 degrees and then
> does the analysis - to see if the _AA_BB gets any smaller.

that's an interesting thought, re-orienting the object.  need to think about
that.

> Pretty nice work, and a striking demonstration of how much empty space an
> automatically generated bounding box can have.
> I knew there was some, but:   WOW.

yeah, Thomas's "reference"-style image did that for me too.  :-)

> I can see this being really useful for BB dependent operations like scanning
> with trace (), and probably a few others that I can't clearly envision at the
> moment.  Basically anywhere that a lot of ray-object intersections need to be
> tested.

gut feeling: scenes with a number of CSG shapes with "difficult" materials, like
glass, will benefit.  also, after a first glance, 'blob' shapes too look like
good candidates.

> This is solid.

merci bien.


regards, jr.

Post a reply to this message

"jr" <cre### [at] gmailcom> wrote:

> as I wrote, I'm game for collaboration.  if you can express the spherical
> bounding you're thinking off as "pseudo code" at least, I'm sure we could work
> on something.

See below (*)


> the art, I guess, will be finding the lowest resolution "good" for the object.
> (low res like for the Boy's Surface wouldn't work for, say, a model of a sea
> urchin, where one would presumably miss many of the spikes)

That sounds like something that one of those space-partitioning algorithms might
be useful for.
On the other hand - if the primitives are mathematical equations, then in thory
one should already know where the object is, and this searching in the dark with
rays is not the way to go.
How _exactly_ to do it differently might be why people have taken to ray
marching instead of raytracing.

I think we could use a hybrid to speed up the initial search with a ray march
type phase, and then do the fine tuning / final result with the ray tracing.



> that's an interesting thought, re-orienting the object.  need to think about
> that.

(*)  Well that's what I was getting at with the ellipsoid and the rotating
calipers.

Right now, you can imagine the the bounding box is determined in a very
hands-off kinda way.   If you took a book that was not axis-aligned, and
squeezed it with axis-aligned calipers, it would "straighten out" until it was
aligned with the minimal width parallel to the axis of measurement.

Of course, we can see how difficult it is for POV-Ray to even do the plain old
hands-off AABB determination, so how does one mathemagically determine not only
the bounding box - but one that is the tightest fit, given that the object may
be "UNaligned"?

The answer to that lies in what I envisioned, and has been worked out and
implemented by those clever people out there.

It has to do with analyzing the orientation of the vectors - the trace ()
results that you get from your "scan".

So, just think about how you'd center an off-axis sphere.
You'd add up the vectors to get an average, which would be the off-axis center
of the sphere, and then translate that in the opposite direction in order to
place it at the origin.

So far so good.

If we have a non symmetric shape, however, we need to also rotate it so that the
minimum widths (if there is one) are along the cardinal axes.

So now we just look for rotational fixes rather than a translational one.

Don't get bogged down in the details.  Just think about it like a linear
regression or a curve-fitting thing on a calculator or in a spreadsheet.
It works, it's used _all the time_ everywhere, from IQ scores to search engine
results, to Facebook and Twitter ranking algorithms, to product and video
suggestions, to facial recognition and machine learning.

The way to do this, unfortunately, or perhaps fortunately, is with matrices.
And I always return to these, I guess because they are so fundamental to what we
do with computer graphics and solid geometry.

So the gist is,
1. we enclose the CSG thing in a bounding sphere.
2. we then shrink an axis of the sphere until we touch the CSG
     but the narrowest part may not be on a principal axis,
     so we just do it until we get whatever axis is the narrowest way
     we can do it.
3. do that to the remaining axis (because the original sphere is already
     defined by the largest axis of the final ellipsoid
4. Now look at the rotation of those ellipsoidal axes and align them
     with x, y, and z

But it's accomplished in a much more straightforward manner using the raw
vectors.

This goes by many names, but I found Singular Value Decomposition (SVD)
but I guess there's Principal Component Analysis (PCA), Eigen Value
Decomposition, etc.  Which can be different but are more or less equivalent and
are often used interchangeably.

Over here (1/4 to 1/3 of the way down):
https://blog.statsbot.co/singular-value-decomposition-tutorial-52c695315254
he says, "Suppose we have two, two-dimensional vectors, x₁=(x₁,
y₁), and x₂=(x₂, y₂). We can fit an ellipse with major
axis, a, and minor axis, b, to these two vectors as shown in the figure."

And then look here at the 7:00 mark:
https://www.youtube.com/watch?v=_4jaLZCoLPI

https://www.youtube.com/watch?v=PFDu9oVAE-g&list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab&index=14

So apparently there are libraries that exist to do this reliably, and maybe just
a c++ script could be run to analyze the data and then spit out the rotation
vectors for POV-Ray to use in the scene.

Or some maniac could convert it to SDL just for funsies.

(This is usually where TOK pops in and mentions that he coded this on a lark way
back in 2004 and didn't think anyone would be interested or find it useful or
something...  ;)  )


"This is crazy, Bill."
(No it's not, Thomas - the dried frog pills are _working_!!!)

Well, yes - and no.  Because I can already see an application to your sphere
slicing troubles in POV-Ray, the existing root-finding problems that Bill
Pokorny is grappling with, and SVD.

If the problem with your sphere slicing arises from root-finding troubles that
POV-Ray experiences when trying to solve for rays that are parallel, or nearly
so, to the object surface, then maybe if you added a "wiggle" to the object,
solved for the root, and then unwiggled the intersection before rendering the
result - then you'd get better renders with less holes.

So if we implemented it in source - them maybe it could be applied to solve a
lot of long-standing, underlying problems.  Or something like it.

Essentially, why look at it parallel, when you could rotate it 90 degrees, look
at it perpendicularly, and then rotate it back.  I don't know if that possible
or realistic in the forest of the source code, but it's not far off from the
camera pigment function {} stuff that he's proposing.


So right now, I'm working off of this:
https://github.com/minillinim/ellipsoid/blob/master/ellipsoid.py
and this:
https://www.codeproject.com/Articles/1268576/Singular-Values-Decomposition-SVD-In-Cplusplus11-B

and one of the popular libraries used for this kind of thing is:
https://github.com/opencollab/arpack-ng

It's also available in numpy
https://towardsdatascience.com/pca-and-svd-explained-with-numpy-5d13b0d2a4d8

From:
https://stats.stackexchange.com/questions/159325/what-fast-algorithms-exist-for-computing-truncated-svd

"All reasonable programming languages and statistic packages (Matlab, R, Python
numpy, you name it) use the same Fortran libraries to perform
eigen/singular-value decompositions. These are LAPACK and ARPACK. ARPACK stands
for ARnoldi PACKage, and it's all about Arnoldi/Lanczos iterations. E.g. in
Matlab there are two functions for SVD: svd performs full decomposition via
LAPACK, and svds computes a given number of singular vectors via ARPACK and it
is actually just a wrapper for an eigs call on the "square-ized" matrix."

Post a reply to this message