"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