"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

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

So the issues I'm running into currently, are that SDL doesn't have the syntax
needed to replicate statements in python or c++, or POV-Ray simply doesn't have
the ability to perform certain of the operations.

So I need to interpret certain statements to first even understand what they do,

http://news.povray.org/povray.programming/thread/%3Cweb.5db79f027e60be924eec112d0%40news.povray.org%3E/

and then rewrite those parts in a way that can be performed in SDL.

for (std::uint32_t row = 0; row < m_size && (index % 100) == 0; row++)

m[row].resize(m[row].size() + 100);

etc.

That's why I figured using the existing, working, tested libraries in c++,
python, Fortran, Ruby, R, Matlab, etc. would be fastest and most reliable.

I mean I could be wrong, but I think it would pay dividends.

And I still can't understand why the value of the FFT isn't understood.  ALL of
the major graphics packages use FFT for myriad effects, edge detection, etc...

Post a reply to this message

hi,

"Bald Eagle" <cre### [at] netscapenet> wrote:
> "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.
>
> So the issues I'm running into currently, are that SDL doesn't have the syntax
> needed to replicate statements in python or c++, or POV-Ray simply doesn't have
> the ability to perform certain of the operations.

unfortunately I'll not be much help there, I do not speak c++ nor python.
however, the SDL is Turing complete aiui.  (though too cumbersome for all sorts
of stuff)

> So I need to interpret certain statements to first even understand what they do,
>
http://news.povray.org/povray.programming/thread/%3Cweb.5db79f027e60be924eec112d0%40news.povray.org%3E/
>
> and then rewrite those parts in a way that can be performed in SDL.
>
> for (std::uint32_t row = 0; row < m_size && (index % 100) == 0; row++)
>
> m[row].resize(m[row].size() + 100);
>
> etc.

what is it you're doing that requires a row to grow?


> That's why I figured using the existing, working, tested libraries in c++,
> python, Fortran, Ruby, R, Matlab, etc. would be fastest and most reliable.
>
> I mean I could be wrong, but I think it would pay dividends.
>
> And I still can't understand why the value of the FFT isn't understood.  ALL of
> the major graphics packages use FFT for myriad effects, edge detection, etc...

back to the subject on hand.  the problem would be having to scan points on the
surface of a sphere, with some precision/resolution, followed by consecutively
smaller spheres, until "contact".  what did I miss?


regards, jr.

Post a reply to this message

Op 03/11/2019 om 16:40 schreef jr:
> 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.
> 

A few thoughts derived from this.

- rotating the object changes the 'tightness' of the standard BB. I did 
that with a simple cylinder: when properly aligned along one of the 
axis, the BB test is always optimal; rotate the cylinder (e.g. 
<45,45,45>) and do the test, and the standard BB becomes too wide.

- the test is also useful with hyperboloid, superellipsoid, and 
isosurface objects. Quartic and parametric objects do no comply, 
probably they are not 'solid'? I did not test this thoroughly.

- I include the test scene file for you to play with.
-- 
Thomas

Post a reply to this message

Attachments:
Download 'utf-8' (9 KB)

hi,

Thomas de Groot <tho### [at] degrootorg> wrote:
> Op 03/11/2019 om 16:40 schreef jr:
> > "Bald Eagle" <cre### [at] netscapenet> wrote:
> >>>>> ... I wrote a macro which "scans" an object's BB ...
> >>>> find attached an updated version of 'Bounder'.
> > ...
> A few thoughts derived from this.
>
> - rotating the object changes the 'tightness' of the standard BB. I did
> that with a simple cylinder: when properly aligned along one of the
> axis, the BB test is always optimal; rotate the cylinder (e.g.
> <45,45,45>) and do the test, and the standard BB becomes too wide.

need to let this info .. stew :-) for a while.  looks like BE's idea of an ini
driven animation to explore the possible orientations and post-process results
is a way to go.

> - the test is also useful with hyperboloid, superellipsoid, and
> isosurface objects. Quartic and parametric objects do no comply,
> probably they are not 'solid'? I did not test this thoroughly.

great news.  I'd initially assumed the macro would be a .. single trick pony,
only good for CSG.

> - I include the test scene file for you to play with.

thank you v much for this.  not only do I get those natty presentation settings
:-), but looking at the code I surmise you replaced the 'local's of the
difference vectors with 'declare's?  that's given me another idea for an
improvement: create two variables, 'Bounder_{min,max}_diff' and export
('declare') them for in-scene use.  thoughts?


regards, jr.

Post a reply to this message

hi,

"Bald Eagle" <cre### [at] netscapenet> wrote:
> "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.
> ...
> > 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.
> ...
> It has to do with analyzing the orientation of the vectors - the trace ()
> results that you get from your "scan".

off the top of my head, write out the points/vectors to a CSV format file, then
either use your spreadsheet-fu or describe the the necessary actions in kinda
pseudo code so we can discuss whether/how to implement as a script/compiled
utility.

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

quick viewed the vids.  agree with 3Blue1Brown that "confusion" arises from
having a "shaky" understanding of the basics.  :-)  (although a frown would be
more appropriate)

so, anything .. matrix you'd have to work through with me -- bite size.

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

chorus: "Oh no, they're not."  :-)

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

I can "see" the concept, and like it.  potential problem: registration, to get
exact re-alignment.

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

I'm working myself up to trying Bill P's custom POV-Ray soon.  but yes, support
in the program source sounds like the way forward.

> ...


regards, jr.

Post a reply to this message

"jr" <cre### [at] gmailcom> wrote:
> Thomas de Groot <tho### [at] degrootorg> wrote:
> > ...
> > - I include the test scene file for you to play with.
>
> thank you v much for this.  not only do I get those natty presentation settings
> :-), but looking at the code I surmise you replaced the 'local's of the
> difference vectors with 'declare's?  that's given me another idea for an
> improvement: create two variables, 'Bounder_{min,max}_diff' and export
> ('declare') them for in-scene use.  thoughts?

d'oh!  finally got the "why".  :-)  with yr permission will add the calculator,
also will adopt the "proper" labelling in existing output.  thanks.


regards, jr.

Post a reply to this message

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

> need to let this info .. stew :-) for a while.  looks like BE's idea of an ini
> driven animation to explore the possible orientations and post-process results
> is a way to go.

The ini was just to showcase what you've got and point out that the initial
object orientation might not yield the tightest bounding box possible.

As a tool, I'd probably do some sort of iteration with loops, first fixing one
axis, then another, then another, and then checking to see if there's any
improvement on a second go-'round.  If there is, repeat, if not, all done.

> > - the test is also useful with hyperboloid, superellipsoid, and
> > isosurface objects. Quartic and parametric objects do no comply,
> > probably they are not 'solid'? I did not test this thoroughly.
>
> great news.  I'd initially assumed the macro would be a .. single trick pony,
> only good for CSG.

Great job Thomas - those results are surprising, given the absolute mathematical
nature of those shapes.

I would have imagined that with something like a parametric, you'd be able to
cycle through u and v real quick, and get a min and max value for each axis to
use for the AABB dimensions.   I'm also still completely mystified as to why the
parametric is such a slow-to-render object, and why the triangle approximation
isn't a source-coded native primitive.

Post a reply to this message

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

> off the top of my head, write out the points/vectors to a CSV format file, then
> either use your spreadsheet-fu or describe the the necessary actions in kinda
> pseudo code so we can discuss whether/how to implement as a script/compiled
> utility.

From what I can gather, there are several approaches to this, and most of them
are iterative - which makes the spreadsheet thing difficult.
It's been a loooong time since I've written macros for spreadsheets, and the
last mammoth spreadsheet I wrote used _zero_ macros - for "security" (you can't
complain about having to enable macros, can you?) and as a sort of little
challenge.  ;)


> quick viewed the vids.  agree with 3Blue1Brown that "confusion" arises from
> having a "shaky" understanding of the basics.  :-)  (although a frown would be
> more appropriate)
>
> so, anything .. matrix you'd have to work through with me -- bite size.

Yeah, I've been watching Grant's videos for a while, and working through the
matrix stuff and linear algebra bit by bit for a while now.  I think there's
like 14 episodes in the linear algebra series, and if you just pop them on while
you're chilling out for a while, you'll get the gist and figure out which ones
focus on specific parts that make everything clear.   I usually cycle through 2
or 3 at a time and rewatch them so I can start to put it all together.

But like I said - all of the code exists already, so it's mostly a matter of
choosing whether to call it for use as an outside routine where the results are
then used by POV-Ray, finding a way insert the relevant code to perform the SVD
into a POV-Ray fork, or converting the code to SDL where anyone can play with
it.

But since the code is complicated, I'd rather have a reliable library that we
just implement to get the right results, so that if we decide we want to do the
work of converting it, then we can compare the output to what we know is right.
Otherwise debugging will be an unimaginable nightmare.

So I think it's less "understanding what SVD does and how it works" and just
blindly getting the code that does it to work for us.  Once it reliably spits
out the right numbers, then it's a toy/tool to use to learn what and how it does
it - if you want.

I'm envisioning a test scene where we take a unit sphere and scale it by 1/2
along one axis, by 1/3 along another, and then give it a < 45deg rotation around
all three axes.
When we "Undo" the rotations with SVD (which I think is what the eigenvectors
allow us to do), we already know exactly what we should end up with - the axis
aligned, scaled sphere (ellipsoid).

Using the
VRand_On_Sphere(Stream): Returns a random vector on the surface of a unit-radius
sphere located at the origin.
from rand.inc
and applying the scaling and rotations to those points (vectors), we can run the
SVD on that data and see what it does.



> > ...
> > "This is crazy, Bill."
> > (No it's not, Thomas - the dried frog pills are _working_!!!)
>
> chorus: "Oh no, they're not."  :-)

No really - TRY SOME.   :D
"Like, dude - if you thought that sRGB with radiosity was good, wait 'till you
see THESE colors...!"   B)

> I can "see" the concept, and like it.  potential problem: registration, to get
> exact re-alignment.

Well, I wasn't so much worried about that, as with how to integrate such a thing
with the ray-object root solver code.

Take any object, matrix transform it, and then just apply the inverse, and you
get exactly what you started with.

transform { Whatever }
followed by
transform { Whatever inverse }
is the same as doing nothing.

So the idea is sorta like trying to render the side of a cube that juuuuuust
slightly rotated so that you can just barely get a glimpse of the side that
rotated toward you.   Instead of trying to squint or zoom in to get a better
look, just rotate the cube the full 90 deg, get a solid unambiguous view of that
face, and then rotate it back once you KNOW what's there.

Eventually you can push things to the point where you run into rounding and
floating point precision, and propagated error - but that's true with everything
we do now.

> I'm working myself up to trying Bill P's custom POV-Ray soon.  but yes, support
> in the program source sounds like the way forward.

Well if you get it installed, give me some tips on how to shoe-horn it onto my
system.  I'm still not so good with the github and compile-it-yourself approach
to software installation.  For most things, I cross my fingers and hope that
there's a package.

Post a reply to this message

hi,

"Bald Eagle" <cre### [at] netscapenet> wrote:
> "jr" <cre### [at] gmailcom> wrote:
> ...
> So right now, I'm working off of this:
> ...
> and this:
>
https://www.codeproject.com/Articles/1268576/Singular-Values-Decomposition-SVD-In-Cplusplus11-B

had a quick look, the page appears to give you the lot.

thinking you ought to have a look at the GSL (GNU Scientific Library); I just
found an index entry for singular value decomp.

<https://www.gnu.org/software/gsl/>

regards, jr.

Post a reply to this message