After much research and review of linear algebra and matrices, I've managed to
work out the basics of this whole Singular Value Decomposition. As with most of
these things, some parts were more difficult, some simpler in retrospect.

So here's what I have so far:

Top left: a unit sphere with a number of randomly placed points on its surface.

Top right: The sphere and points scaled and rotated to give an off-axis
ellipsoid and it's corresponding data points [these will be acquired by trace()
in future version(s) ]

3. The ellipsoid after attempting to axis-align it using a matrix derived from
the SVD.

4. Step 3 rotated 90 deg.

Looks like the new BB is almost 1/3 of the original (which looks horrible to
begin with).

The side view looks a bit tilted, so something's still off, so I will keep
experimenting - hopefully I can streamline the process so I don't have to keep
manually entering values.

Post a reply to this message

Attachments:
Download 'svd_ellipse_test.png' (267 KB)

Preview of image 'svd_ellipse_test.png'

"Bald Eagle" <cre### [at] netscapenet> wrote:
> After much research and review of linear algebra and matrices, I've managed to
> work out the basics of this whole Singular Value Decomposition. As with most of
> these things, some parts were more difficult, some simpler in retrospect.
>
> So here's what I have so far:
>
> Top left: a unit sphere with a number of randomly placed points on its surface.
>
> Top right: The sphere and points scaled and rotated to give an off-axis
> ellipsoid and it's corresponding data points [these will be acquired by trace()
> in future version(s) ]
>
> 3. The ellipsoid after attempting to axis-align it using a matrix derived from
> the SVD.
>
> 4. Step 3 rotated 90 deg.
>
> Looks like the new BB is almost 1/3 of the original (which looks horrible to
> begin with).
>
> The side view looks a bit tilted, so something's still off, so I will keep
> experimenting - hopefully I can streamline the process so I don't have to keep
> manually entering values.

If you have an SVD solver/generator coded in POVRay SDL, I wold very much like
to see it,

JimT

Post a reply to this message

"JimT" <nomail@nomail> wrote:

> If you have an SVD solver/generator coded in POVRay SDL, I wold very much like
> to see it,

I'm working towards that, at the moment, I'm trying to use various 3rd party SVD
tools to just get the V transpose matrix and apply that, but - the eigenvectors
I get aren't lining up properly with my ellipsoid data.

I need to learn if there are any pitfalls, tricks, checks, etc. so I can debug
what the problem is.   My current working theory is some mistake of mine
assigning the axes, or maybe the LH coordinate system...

So, I'm going to get a "real" SVD solver to do the work for the moment, then a
cpp script that maybe a POV-Ray .ini can call, and then maybe I can work out the
tricky bits in SDL.

I probably have a few more matrix macros to write - especially one that applies
a matrix transform to a pseudo-matrix array [m][n]{} - just to make my life
easier for certain tasks.

Post a reply to this message

OK,
It is, at the moment, working the way it ought to.

I'd like to do more - like reverse the scaling in order to get the original
sphere, and have the ellipse get rotated back to the original position (I'm
probably going to have to learn about Euler angles next...) - but this is
functional.

I got the proper axes to use, and the proper matrix transform to use in order to
re-align those axes with the cardinal ones.

Holy Byzantine odyssey.

Post a reply to this message

Attachments:
Download 'svd_ellipse_test.png' (302 KB)

Preview of image 'svd_ellipse_test.png'

Posting this here as reference material in regard to my present issues with the
matrix V-transpose.

SVD calculator used is:
http://engineerjs.com/?sidebar=doc/ejs/engine/linalg-1/_svd.html

The data and script can be copied and pasted:
------------------------------------------------------------------------------

A = [0.09, -0.41, 0.42, 0.43, -0.40, 0.18, -0.01, 0.35, 0.19, 0.27, -0.43, 0.49,
-0.17, -0.35, -0.06, -0.01, -0.35, 0.50, -0.23, 0.31, -0.49, 0.43, -0.32, -0.40,
 0.24, 0.07, -0.43, 0.35, 0.51, -0.38, 0.40, 0.30, 0.39, 0.23, -0.22, 0.34,
-0.38, -0.43, -0.14, 0.29, -0.24, 0.21, 0.25, -0.28, -0.37, -0.14, -0.42, -0.27,
 -0.39, 0.42, 0.42, 0.01, -0.04, 0.02, -0.17, -0.43, -0.41, 0.22, -0.31, -0.27,
-0.44, 0.33, -0.51, -0.03, -0.46, 0.32, -0.32, 0.34, 0.21, 0.47, -0.37, -0.42,
 0.19, 0.05, -0.02, 0.45, 0.10, 0.42, -0.25, 0.24, -0.13, -0.36, 0.50, -0.20,
-0.20, -0.35, 0.34, 0.42, -0.47, -0.41, 0.37, 0.09, 0.46, -0.41, 0.41, 0.35,
 -0.24, -0.11, -0.10, 0.26, -0.02, -0.18, -0.33, 0.48, 0.24, -0.02, -0.14,
-0.23, -0.51, -0.12, 0.17, -0.39, 0.25, -0.50, 0.26, 0.06, 0.44, -0.02, -0.47,
0.01,
 0.41, 0.40, 0.36, -0.40, -0.27, -0.46, 0.06, 0.47, -0.16, -0.33, 0.14, -0.38,
0.24, 0.06, 0.38, 0.50, 0.01, 0.42, -0.24, 0.23, 0.24, -0.28, -0.48, 0.25, 0.49,
 -0.18, 0.36, -0.15, -0.21, 0.06, -0.17, 0.50, 0.31, 0.06, 0.01, 0.27, -0.31,
-0.01, 0.26, -0.51, -0.27, 0.22, -0.26, -0.06, 0.33, -0.23, -0.42, 0.33, -0.03,
 0.39, 0.41, 0.26, -0.17, 0.25, -0.40, -0.12, -0.07, -0.20, -0.42, -0.46, -0.10,
-0.00, 0.51, -0.14, -0.41, 0.24, -0.34, 0.36, -0.28, -0.14, -0.48, 0.09, 0.28,
 0.38, -0.28, -0.08, 0.48, -0.06, 0.06, 0.03, 0.40, 0.31, 0.09, -0.08, 0.36,
-0.45, -0.24, 0.36, 0.28, 0.19, 0.05, -0.50, -0.29, 0.48, -0.09, 0.35, 0.12,
-0.41,
 0.35, 0.50, -0.33, -0.22, 0.43, -0.24, -0.27, 0.44, -0.45, 0.12, 0.32, -0.40,
0.13, -0.08, -0.48, 0.08, 0.46, 0.14, -0.18, -0.23, -0.22, -0.10, 0.27, 0.40,
 -0.16, 0.03, -0.38, -0.46, 0.37, 0.06, 0.38, -0.24, -0.23, -0.29, 0.02, -0.26,
0.38, -0.08, 0.38, -0.33, 0.08, -0.11, -0.37, 0.15, -0.13, 0.50, 0.40, 0.47,
 0.36, -0.40, -0.17, -0.30, -0.23, -0.42, 0.06, 0.33, -0.47, 0.17, 0.34, -0.11,
-0.22, 0.44, -0.02, 0.25, 0.05, -0.29, -0.49, -0.43, 0.03, 0.36, -0.32, 0.47,
 -0.22, -0.20, -0.26, 0.49, 0.25, 0.28, 0.24, -0.21, 0.14, -0.13, -0.20, -0.30,
-0.17, -0.38, 0.32, 0.17, 0.40, -0.10, -0.38, -0.16, 0.36, 0.46, -0.27, 0.09,
 -0.10, -0.41, 0.47, 0.29, 0.24, 0.25, 0.50, -0.27, -0.16, -0.09, -0.41, 0.20,
0.41, -0.33, -0.38, 0.12, -0.18, 0.08, 0.12, 0.41, -0.33, 0.41, -0.20, -0.13,
 -0.51, -0.43, -0.32, 0.22, 0.16, 0.36, -0.15, 0.04, -0.09, 0.25, -0.19, -0.27,
-0.19, 0.05, 0.38, 0.03, 0.06, 0.38, -0.41, -0.27, -0.33, -0.05, 0.49, 0.12,
 0.22, 0.24, 0.25, -0.05, 0.24, -0.42, 0.34, -0.05, -0.49, -0.46, -0.11, 0.34,
0.38, -0.10, -0.42, 0.19, -0.07, -0.18, -0.41, 0.46, -0.33, -0.48, 0.01, 0.03,
 0.26, -0.17, -0.46, 0.08, 0.32, 0.34, -0.03, 0.19, 0.15, -0.39, -0.18, -0.04,
-0.12, -0.20;
-0.33, 0.10, 0.02, 0.12, -0.43, -0.25, 0.45, 0.73, -0.17, 0.90, -0.65, 0.41,
0.05, 0.18, -0.37, 0.53, 0.13, 0.35, -0.57, -0.22, -0.47, 0.80, 0.08, 0.12,
-0.25,
 -0.34, -0.15, 0.22, 0.34, -0.67, -0.03, 0.78, 0.46, -0.10, -0.82, -0.18, -0.74,
-0.82, 0.59, 0.57, 0.14, 0.83, 0.53, -0.41, -0.71, 0.17, -0.51, -0.91, -0.11,
 0.75, 0.40, 0.04, -0.78, 0.59, -0.90, -0.25, -0.44, -0.24, -0.51, 0.29, -0.69,
-0.27, -0.56, 0.32, -0.28, 0.46, -0.41, 0.02, 0.74, 0.65, -0.81, -0.46, 0.21,
 -0.74, 0.76, 0.48, 0.58, 0.24, 0.10, 0.90, 0.47, -0.88, 0.53, -0.91, -0.91,
0.10, -0.14, 0.21, -0.31, -0.00, 0.71, 0.33, 0.48, 0.02, -0.08, 0.37, 0.47,
0.29,
 0.07, -0.42, -0.06, -0.85, -0.20, 0.45, 0.47, 0.76, 0.58, -0.24, -0.40, 0.65,
-0.45, 0.02, 0.78, -0.35, -0.23, 0.14, 0.05, 0.26, -0.74, 0.38, 0.55, -0.13,
 0.47, 0.11, -0.44, -0.10, -0.54, 0.20, 0.13, -0.91, -0.32, -0.40, 0.90, 0.82,
-0.04, 0.38, 0.47, 0.83, 0.47, 0.03, -0.24, 0.04, -0.21, 0.73, 0.44, -0.89,
 -0.11, -0.34, 0.04, -0.29, -0.60, 0.62, 0.38, -0.66, -0.48, 0.09, -0.36, 0.50,
-0.43, -0.40, -0.83, -0.51, 0.27, 0.25, -0.30, -0.30, -0.83, -0.26, 0.38, 0.48,
 0.05, 0.55, 0.57, 0.01, -0.33, 0.57, -0.60, -0.12, -0.80, -0.16, 0.31, 0.10,
0.52, -0.19, -0.71, 0.17, -0.74, -0.12, 0.29, -0.76, -0.26, -0.34, 0.81, 0.72,
 -0.86, 0.12, 0.72, -0.83, -0.08, 0.58, 0.86, 0.17, -0.32, 0.34, 0.05, -0.68,
0.44, 0.88, 0.82, 0.03, -0.08, -0.47, -0.43, 0.25, 0.69, 0.56, -0.65, -0.14,
0.10,
 0.34, -0.86, 0.49, 0.50, 0.04, -0.92, 0.67, -0.07, -0.01, 0.91, 0.10, 0.85,
0.70, -0.52, 0.64, 0.62, 0.26, 0.14, 0.14, 0.50, 0.66, 0.88, 0.75, -0.39, -0.57,
 -0.60, -0.19, -0.17, 0.82, 0.30, -0.88, -0.79, -0.83, -0.76, -0.26, 0.88,
-0.27, 0.06, -0.59, 0.19, -0.52, -0.63, 0.83, 0.39, 0.28, -0.09, 0.44, -0.05,
0.09,
 -0.88, -0.09, 0.45, -0.18, 0.65, -0.16, -0.66, 0.13, -0.03, 0.49, -0.48, 0.08,
0.76, 0.69, 0.82, -0.83, -0.64, -0.21, -0.74, 0.12, -0.67, 0.64, -0.90, -0.45,
 -0.08, 0.22, 0.72, -0.22, 0.90, 0.17, -0.59, 0.18, 0.54, -0.08, 0.50, -0.62,
0.90, -0.53, -0.11, 0.32, -0.30, 0.40, 0.01, 0.11, 0.13, -0.21, 0.44, -0.70,
0.72,
 -0.08, 0.35, 0.47, 0.30, -0.64, 0.61, 0.63, -0.75, 0.27, 0.72, -0.63, 0.14,
0.67, -0.48, 0.84, 0.80, 0.66, -0.71, 0.74, 0.43, -0.35, -0.50, -0.30, -0.52,
0.78,
 -0.58, 0.18, -0.52, -0.75, -0.19, -0.42, -0.42, -0.88, 0.54, 0.25, 0.75, 0.67,
-0.61, 0.05, 0.08, -0.91, 0.26, 0.49, 0.24, -0.10, 0.80, 0.85, -0.33, 0.69,
 -0.16, -0.02, 0.33, -0.83, -0.62, -0.29, -0.38, 0.87, 0.32, 0.68, 0.05, 0.86,
0.47, -0.67, -0.26, 0.07, 0.16, -0.71, -0.74, 0.01, 0.91, -0.54, -0.52, -0.42,
 -0.30, 0.46, -0.24, 0.13, -0.54, -0.83, -0.08, 0.10, -0.70, 0.52;
-0.34, 0.24, -0.10, -0.08, 0.00, -0.36, -0.32, -0.04, 0.22, -0.11, 0.10, -0.38,
-0.25, 0.04, -0.29, 0.24, 0.01, -0.22, -0.13, -0.32, 0.16, -0.34, -0.06, 0.23,
 -0.35, 0.30, 0.07, -0.46, -0.28, 0.04, -0.08, -0.02, 0.01, 0.19, 0.33, -0.02,
0.41, 0.24, -0.06, 0.08, -0.16, -0.32, -0.45, 0.47, 0.43, 0.39, 0.05, 0.24,
0.42,
 -0.40, -0.46, -0.38, 0.19, -0.30, 0.13, 0.43, 0.03, 0.16, -0.08, -0.06, 0.14,
-0.08, 0.33, -0.34, 0.10, 0.09, -0.09, 0.07, 0.07, -0.19, 0.38, 0.46, -0.46,
 0.01, -0.01, -0.44, 0.20, -0.03, 0.41, -0.11, -0.19, 0.20, -0.38, 0.16, 0.19,
-0.02, -0.34, -0.03, 0.13, 0.07, -0.05, -0.41, -0.43, 0.34, -0.18, 0.07, 0.07,
 -0.27, -0.30, -0.18, -0.36, 0.01, -0.09, -0.16, -0.46, 0.00, -0.10, -0.19,
0.32, -0.02, 0.15, 0.37, 0.02, 0.20, -0.35, -0.41, -0.14, 0.34, 0.32, -0.35,
-0.03,
 -0.21, -0.47, 0.26, -0.14, 0.21, 0.24, -0.16, -0.25, 0.23, 0.23, 0.47, -0.26,
-0.17, -0.37, -0.23, -0.33, -0.30, 0.05, 0.20, -0.36, 0.42, 0.19, -0.40, -0.18,
 0.23, -0.03, -0.24, -0.22, -0.34, 0.41, -0.29, 0.10, -0.13, 0.31, 0.16, 0.48,
0.26, -0.13, 0.33, 0.03, -0.10, 0.33, -0.32, -0.09, 0.47, 0.25, -0.04, -0.32,
 -0.47, -0.38, -0.45, 0.13, -0.44, -0.01, -0.13, 0.34, 0.45, 0.19, 0.15, 0.34,
-0.37, -0.26, 0.44, 0.09, -0.46, 0.03, -0.34, 0.30, 0.32, 0.36, -0.33, -0.36,
 -0.42, 0.33, -0.32, -0.30, 0.03, -0.39, 0.21, -0.24, -0.46, -0.34, 0.33, 0.04,
0.40, 0.20, -0.18, -0.03, 0.24, -0.38, 0.19, -0.12, -0.35, -0.04, 0.03, 0.04,
 0.03, 0.05, -0.34, 0.34, 0.16, -0.45, 0.43, 0.17, -0.42, 0.32, -0.42, -0.26,
0.27, -0.02, -0.04, 0.41, -0.33, -0.14, 0.26, -0.23, -0.17, 0.12, 0.09, -0.31,
 -0.11, -0.23, -0.22, 0.02, 0.37, -0.10, -0.17, 0.03, 0.07, -0.03, 0.05, -0.00,
0.47, -0.25, -0.30, -0.41, -0.04, -0.41, -0.22, 0.01, -0.27, 0.31, -0.28, -0.28,
 -0.13, 0.01, 0.28, 0.22, 0.45, -0.02, 0.42, -0.31, 0.02, 0.18, 0.25, -0.41,
-0.20, -0.16, -0.12, 0.02, 0.07, -0.02, 0.36, 0.23, 0.42, 0.11, 0.04, -0.02,
-0.16,
 0.10, -0.19, 0.45, -0.31, 0.05, -0.34, -0.27, 0.39, -0.14, 0.39, 0.09, 0.45,
0.22, 0.02, -0.17, -0.19, -0.17, 0.34, 0.47, 0.30, 0.03, -0.31, -0.12, -0.37,
 -0.24, 0.09, -0.34, -0.41, -0.47, -0.46, -0.21, -0.07, 0.07, -0.12, 0.40,
-0.46, -0.41, -0.03, 0.08, -0.35, 0.44, -0.14, 0.05, -0.43, 0.01, -0.12, 0.26,
0.43,
 0.28, 0.44, 0.47, -0.36, -0.14, 0.06, 0.41, 0.03, 0.42, -0.21, 0.45, 0.08,
0.15, 0.31, -0.08, -0.27, 0.20, -0.00, 0.17, 0.24, 0.25, 0.27, -0.33, 0.29,
-0.34,
 -0.32, -0.30, 0.12, -0.39, 0.11, 0.08, 0.03, 0.38, 0.41, 0.42, -0.32, -0.47,
0.01, 0.27, -0.03, -0.26, 0.39, 0.45, -0.20, -0.02, 0.35, 0.15, 0.35, -0.25,
 -0.18, 0.43, 0.26, -0.20, -0.47, 0.39, -0.45, -0.20, 0.16, -0.24, 0.38, -0.13,
0.00
];

  print("Non-square matrix").title()
  A
  print("Calculate S, U, and V-transpose").title()
  s = ejs.svd(A,true,true)

  print("Show that U-transpose x U = I (small numbers = 0)").title()
  s.u'*s.u //!!

  print("Show that V x V-transpose = I (small numbers = 0)").title()
  s.v*s.v'

  print("Show that U x S x V = A, the original matrix").title()
  s.u*diag(s.d)*s.v

------------------------------------------------------------------------------

Running that will give you U, S, and V (presumably V-transpose, but it hardly
matters, as the matrix has scaling and is not purely rotational)

The first three columns get copied into POV-Ray for use as a transform matrix as
follows:

#declare VC1 = <-0.04816, -0.07305, -0.01401>;
#declare VC2 = <-0.03091,  0.07824, -0.01210>;
#declare VC3 = < 0.06011, -0.05455,  0.01822>;

#declare VR1 = <VC1.x, VC2.x, VC3.x>;
#declare VR2 = <VC1.y, VC2.y, VC3.y>;
#declare VR3 = <VC1.z, VC2.z, VC3.z>;

#declare V = transform {
matrix
<
 VR1.x, VR2.x, VR3.x, //
 VR1.y, VR2.y, VR3.y, //
 VR1.z, VR2.z, VR3.z, //
 0.000, 0.000, 0.000  //
>
}

Attached is a render showing - in the strip between -1 and 1 from top to bottom
- a sphere transformed by U.  No change, as it's a purely rotational matrix.

Two small ellipsoids.   These are created by taking a sphere and transforming
with V and V-transpose.   Obvious scaling takes place.

One larger ellipsoid - created by applying V and then S.

Applying only S gives an ellipsoid that is so large that it blots out everything
else in the render.

Post a reply to this message

Attachments:
Download 'svd_ellipse_test.png' (316 KB)

Preview of image 'svd_ellipse_test.png'

hi,
#
"Bald Eagle" <cre### [at] netscapenet> wrote:
> Posting this here as reference material in regard to my present issues with the
> matrix V-transpose.
> ...
> Attached is a render ...

BB volume reduced by over 75%.  nice.  (worth having).


regards, jr.

Post a reply to this message

Did a rework of this using simple BB measurements and plain old SDL code.
After the usual stupid mistakes and typos, it seems to work for a simple
cylinder.

Will play some more with some more complex shapes as time allows.

Also need to employ some sanity checks and logic for if this gets applied to
something like a sphere.

And probably add a second level of refinement using trace() in case automatic
bounding doesn't give any usable metrics.

Post a reply to this message

Attachments:
Download 'gradientbounding.png' (75 KB)

Preview of image 'gradientbounding.png'

"Bald Eagle" <cre### [at] netscapenet> wrote:
> Did a rework of this using simple BB measurements and plain old SDL code.
> After the usual stupid mistakes and typos, it seems to work for a simple
> cylinder.
>
> Will play some more with some more complex shapes as time allows.
>
> Also need to employ some sanity checks and logic for if this gets applied to
> something like a sphere.
>
> And probably add a second level of refinement using trace() in case automatic
> bounding doesn't give any usable metrics.

Interesting.

Have you seen this article ?

"Fast oriented bounding box optimization on the rotation group SO(3, R)"
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.717.9566&rep=rep1&type=pdf
https://dl.acm.org/doi/10.1145/2019627.2019641

--
Tor Olav
http://subcube.com
https://github.com/t-o-k

Post a reply to this message

Hi, buddy :)

It is an interesting problem given how simple it appears to be at first glance.
I was disappointed that I haven't [yet] figured out the problems with the
Singular Value Decomposition method.

The paper looks interesting, of course - but then again I get emails all the
time from Academia.edu about computer graphics :D  And of course many of them
yammer on about what they do - but there's no code.

But I did find this:
https://github.com/chadogome/OptimalOBB

So I will look into it.   :)


Thanks for the link!

Post a reply to this message

"Bald Eagle" <cre### [at] netscapenet> wrote:

> It is an interesting problem given how simple it appears to be at first glance.

And indeed it looks simple, and simple cases like a cylinder or box get handles
nicely; however, when I make an "L", a curious thing happens.   First, I don't
get anything near what I'd imagine is an even poorly-optimized orientation, and
second, I sometimes get a worse result.  But the really interesting thing is
that the algorithm registers 90 degrees as the optimum rotation for y and 0 for
z and x no matter what seed value I use for the initial randomization of the
orientation.

So, something is seriously amiss, yet I'm looking right past it.  Ugh.

Post a reply to this message

Attachments:
Download 'gradientbounding.png' (131 KB)

Preview of image 'gradientbounding.png'