Approximate a 3D object by an ellipsoid

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Approximate a 3D object by an ellipsoid

Ekinoks
Hello,

I would like to approximate a 3D object by an ellipsoid.
By approximate I mean to get an ellipsoid of equivalent volume in such a way
that it maximizes the intersection with the object to be approximated.

Does anyone have an idea how to do this with a simple method?

Do not hesitate to answer if you have any idea.
Thank you :)



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Approximate a 3D object by an ellipsoid

adrianv
Your problem is to vague to propose a specific solution.  The basic approach
that occurs to me is to set this up as an optimization problem to maximize
the intersection volume subject to a constraint on the ellipsoid volume.  If
you have a simple way to compute the intersection volume then you can
probably apply standard optimization methods.  

On the other hand, if you don't have a way to compute the intersection
volume I suppose you could represent your object in a 3d grid and then
estimate intersection volume numerically.  This would be a fairly slow
calculation and it wouldn't have well behaved derivatives unless you did a
good job at the boundaries---but if you did that you might still be able to
apply an optimization method (e.g. steepest descent or a Newton method).  

If you don't do a good job at the boundaries then you have a
nondifferentiable optimization problem.  You could attack it by brute force:
evaluate for many ellipsoids and pick the best one.  


Ekinoks wrote

> Hello,
>
> I would like to approximate a 3D object by an ellipsoid.
> By approximate I mean to get an ellipsoid of equivalent volume in such a
> way
> that it maximizes the intersection with the object to be approximated.
>
> Does anyone have an idea how to do this with a simple method?
>
> Do not hesitate to answer if you have any idea.
> Thank you :)
>
>
>
> --
> Sent from: http://forum.openscad.org/
>
> _______________________________________________
> OpenSCAD mailing list

> Discuss@.openscad

> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org





--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Approximate a 3D object by an ellipsoid

Kenneth Sloan
In reply to this post by Ekinoks
There are several ways to get approximate answers to your question.

The method I prefer is to use principal component analysis (Eigenvectors). First, you need a well-distributed set of points from the object.  Since we are approximating, perhaps the set of vertices on the boundary is sufficient.  Check wikipedia for the details on PCA, Hessian, and Eigenvectors.  This will get you a set of 3 axes.  You can then scale these to make the volume of the ellipsoid match the volume of the object.

Finding an exact solution looks extremely difficult.  I’m not even sure the solution is unique.

--
Kenneth Sloan
[hidden email]
Vision is the art of seeing what is invisible to others.


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Approximate a 3D object by an ellipsoid

Ekinoks
In reply to this post by Ekinoks
Thanks a lot for your answers!
I see, getting an exact solution to this problem seems very complex. I will look into Kenneth's idea then and try to get an approximate value based on eigenvectors.

Thanks again :)

Le mar. 23 juin 2020 à 22:24, Kenneth Sloan <[hidden email]> a écrit :
There are several ways to get approximate answers to your question.

The method I prefer is to use principal component analysis (Eigenvectors). First, you need a well-distributed set of points from the object.  Since we are approximating, perhaps the set of vertices on the boundary is sufficient.  Check wikipedia for the details on PCA, Hessian, and Eigenvectors.  This will get you a set of 3 axes.  You can then scale these to make the volume of the ellipsoid match the volume of the object.

Finding an exact solution looks extremely difficult.  I’m not even sure the solution is unique.

--
Kenneth Sloan
[hidden email]
Vision is the art of seeing what is invisible to others.


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org