POV-Ray : Newsgroups : povray.binaries.images : Improved bounding box by alignment via SVD Server Time: 15 Dec 2019 20:35:06 GMT
  Improved bounding box by alignment via SVD (Message 1 to 6 of 6)  
From: Bald Eagle
Subject: Improved bounding box by alignment via SVD
Date: 10 Nov 2019 23:55:01
Message: <web.5dc8a318adf09f614eec112d0@news.povray.org>
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'
svd_ellipse_test.png


 

From: JimT
Subject: Re: Improved bounding box by alignment via SVD
Date: 11 Nov 2019 21:00:12
Message: <web.5dc94df835e3eb7be7517870@news.povray.org>
"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

From: Bald Eagle
Subject: Re: Improved bounding box by alignment via SVD
Date: 11 Nov 2019 21:45:00
Message: <web.5dc9d60635e3eb74eec112d0@news.povray.org>
"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

From: Bald Eagle
Subject: Re: Improved bounding box by alignment via SVD
Date: 12 Nov 2019 22:20:06
Message: <web.5dcb2fe935e3eb74eec112d0@news.povray.org>
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'
svd_ellipse_test.png


 

From: Bald Eagle
Subject: Re: Improved bounding box by alignment via SVD
Date: 19 Nov 2019 00:50:00
Message: <web.5dd33bd735e3eb74eec112d0@news.povray.org>
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'
svd_ellipse_test.png


 

From: jr
Subject: Re: Improved bounding box by alignment via SVD
Date: 19 Nov 2019 12:35:01
Message: <web.5dd3e07435e3eb7feeb22ff0@news.povray.org>
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

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