POV-Ray : Newsgroups : povray.binaries.images : AABB reduction by Singular Value Decomposition Server Time
17 Sep 2021 03:48:46 EDT (-0400)
  AABB reduction by Singular Value Decomposition (Message 1 to 8 of 8)  
From: Bald Eagle
Subject: AABB reduction by Singular Value Decomposition
Date: 2 Apr 2021 21:40:00
Message: <web.6067c66d2a07e751f9dae3025979125@news.povray.org>
So I contacted this Greek grad student working on his PhD in Switzerland, and
started checking things and restructuring the scene to clarify what I wanted,
what I had tried, and where things were going wrong.

During the course of that, I re-ran the SVD - literally just copy-pasting the
data that I posted here over a year ago - and I noticed that the values I had in
the scene were different.  I commented those out, placed the new values in
and....

Ho-Lee Krappp
It's perfectly aligned!

23% of the original bounding box size.   :)

Now to see where we can go from here.


Post a reply to this message


Attachments:
Download 'svd_ellipse_test2.png' (149 KB)

Preview of image 'svd_ellipse_test2.png'
svd_ellipse_test2.png


 

From: Tor Olav Kristensen
Subject: Re: AABB reduction by Singular Value Decomposition
Date: 4 Apr 2021 20:05:00
Message: <web.606a535ed8cfb0efd6f19eb189db30a9@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:
> So I contacted this Greek grad student working on his PhD in Switzerland, and
> started checking things and restructuring the scene to clarify what I wanted,
> what I had tried, and where things were going wrong.
>
> During the course of that, I re-ran the SVD - literally just copy-pasting the
> data that I posted here over a year ago - and I noticed that the values I had in
> the scene were different.  I commented those out, placed the new values in
> and....
>
> Ho-Lee Krappp
> It's perfectly aligned!
>
> 23% of the original bounding box size.   :)
>
> Now to see where we can go from here.

Well done!

What other uses than bounding box minimization do you have in mind for your SVD
code ?

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


Post a reply to this message

From: Tor Olav Kristensen
Subject: Re: AABB reduction by Singular Value Decomposition
Date: 4 Apr 2021 20:15:00
Message: <web.606a5656d8cfb0efd6f19eb189db30a9@news.povray.org>
"Tor Olav Kristensen" <tor### [at] TOBEREMOVEDgmailcom> wrote:
>...
> What other uses than bounding box minimization do you have in mind for your SVD
> code ?

Sorry: Not "bounding box minimization", but "minimum volume bounding ellipsoid"

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


Post a reply to this message

From: Bald Eagle
Subject: Re: AABB reduction by Singular Value Decomposition
Date: 4 Apr 2021 20:25:00
Message: <web.606a5802d8cfb0ef1f9dae3025979125@news.povray.org>
"Tor Olav Kristensen" <tor### [at] TOBEREMOVEDgmailcom> wrote:

> Well done!

Thanks, but I wish I had been more rigorous in my first go-around.
I am happy that it works, but not knowing why it didn't work the first time -
bothers me.

I checked everything that I could, and even used 4-5 different online SVD
calculators to see if the numbers that came out were the same - and they were.
Which is doubly troubling   ;)

> What other uses than bounding box minimization do you have in mind for your SVD
> code ?

Well, that's a very good question.
I think that now that the proof-of-concept experiment has [finally] been
successful, the key thing will be to get a robust SVD algorithm coded in SDL,
c++ for calling from a shell-out, or for inserting into the POV-Ray source code.
Because I have no "SVD code" - it's just the application of the matrix transform
that comes out of an online SVD calculator.  (It choked on ~28,000 vertices of
an stl file)

That may take some time, although I know that I have an implementation of a
Jacobi algorithm in POV-Ray format [ :O ] bookmarked
https://stackoverflow.com/questions/10781639/how-to-compute-normal-vector-to-least-square-plane-in-povray-only

So that will be a head start.

As for other applications, I will have to think about that, since most of the
people I have contacted for assistance always commented that they'd never
thought of using it for 3D data...


Post a reply to this message

From: Bald Eagle
Subject: Re: AABB reduction by Singular Value Decomposition
Date: 7 Apr 2021 18:50:00
Message: <web.606e36b7d8cfb0ef1f9dae3025979125@news.povray.org>
"Tor Olav Kristensen" <tor### [at] TOBEREMOVEDgmailcom> wrote:

> Sorry: Not "bounding box minimization", but "minimum volume bounding ellipsoid"

Actually, it IS the bounding box we're minimizing.   The ellipsoid is just the
simplest anisotropic primitive to generate the surface point cloud from, and it
also comports with the dozens of SVD illustrations online.

Convex hulls and bounding ellipsoids are something I have yet to embark on.

I spent far too long converting a FORTRAN90 subroutine for calculating SVD into
SDL - which was tricky, given it has a GOTO statement that jumps BACK in the
code...
The dozen other GOTOs were pretty straightforward once I saw what I had to do.

I hacked the heck out of it and got it to run with no errors, and spit out some
matrices, but I don't get any useful results from it.  I'm sure I botched
something in my marathon editing session, so I have to track down where THIS has
gone off the rails.


Post a reply to this message


Attachments:
Download 'svd.inc.txt' (23 KB)

From: Tor Olav Kristensen
Subject: Re: AABB reduction by Singular Value Decomposition
Date: 8 Apr 2021 23:25:00
Message: <web.606fc889d8cfb0ef8e52cc8789db30a9@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:
> "Tor Olav Kristensen" <tor### [at] TOBEREMOVEDgmailcom> wrote:
>
> > Sorry: Not "bounding box minimization", but "minimum volume bounding ellipsoid"
>
> Actually, it IS the bounding box we're minimizing.   The ellipsoid is just the
> simplest anisotropic primitive to generate the surface point cloud from, and it
> also comports with the dozens of SVD illustrations online.
>
> Convex hulls and bounding ellipsoids are something I have yet to embark on.

Ok. I see.


> I spent far too long converting a FORTRAN90 subroutine for calculating SVD into
> SDL - which was tricky, given it has a GOTO statement that jumps BACK in the
> code...
> The dozen other GOTOs were pretty straightforward once I saw what I had to do.
>
> I hacked the heck out of it and got it to run with no errors, and spit out some
> matrices, but I don't get any useful results from it.  I'm sure I botched
> something in my marathon editing session, so I have to track down where THIS has
> gone off the rails.

That FORTRAN spaghetti code looks like a little nightmare to rewrite in a
structured way.

I just had a quick look at FORTRAN 90 - and it seems like it could have
been written in a much better way with the features available there.

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


Post a reply to this message

From: Bald Eagle
Subject: Re: AABB reduction by Singular Value Decomposition
Date: 9 Apr 2021 06:45:00
Message: <web.60702fa3d8cfb0ef1f9dae3025979125@news.povray.org>
"Tor Olav Kristensen" <tor### [at] TOBEREMOVEDgmailcom> wrote:

> That FORTRAN spaghetti code looks like a little nightmare to rewrite in a
> structured way.

Most of it was a lot easier than I initially thought.
Almost every instance was just a piss poor way of doing what an #if - #else -
#end block would do.  So I just switched out the GOTOs with #ELSEs, and that
seemed to be what the intent was.
The GOTO 520 that jumped back in the code was trickier, but I used a #while, and
a flag that kept the #while loop going until the code exited by another route.

> I just had a quick look at FORTRAN 90 - and it seems like it could have
> been written in a much better way with the features available there.

Yep - but I suppose there was a lot of that in the "early days".
I think right now the thing that's going to be the biggest stumbling block is
the lack of comments in the code and my own abysmal ignorance of how SVD works
and the specific matrix operations that get performed.  And it would be a lot
easier to work through if there weren't so many different ways to go about it,
with various optimizations, etc.
Part of my rationale for choosing this specific code was that it was from a
stable and thoroughly tested "standard" code library, and the fact that it was
old and unoptimized ("elegant") likely meant that all of the operations would be
simple and readable and easier to follow and puzzle out the purpose.

But I could be wildly wrong about that. ;)


Made a few changes to see about fixing it - now it's wrong in a different,
better way.   :D


Post a reply to this message


Attachments:
Download 'svd.inc.txt' (26 KB)

From: Bald Eagle
Subject: Re: AABB reduction by Singular Value Decomposition
Date: 10 Apr 2021 19:00:00
Message: <web.60722d99d8cfb0ef1f9dae3025979125@news.povray.org>
Posting this here because this is truly one of the best explanations I have come
across so far.

https://www.youtube.com/watch?v=DG7YTlGnCEo


Post a reply to this message

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