Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to generate a 3d signed distance field for a origin centered ellipsoid. For a sphere this is pretty easy: $$\sqrt{x^2 + y^2 + z^2}-r$$ where $r$ is the radius.

I'm not sure what the best approach is for an ellipsoid. I expect plugging values into the implicit equation: $$f(x,y,z) = \frac{x^2}{a^2}+\frac{y^2}{b^2} + \frac{z^2}{c^2} - 1$$ would give me something close (certainly it should give the correct sign). Any ideas?

Thanks!

share|improve this question
1  
Would you mind explaining briefly or pointing to a reference as to what a 3D signed distance field is? –  Eric Haengel Dec 8 '11 at 4:39
1  
Sure. The signed distance is the distance to the closest point on the surface. For points inside, this is negative, and outside the object it is positive (that's the signed part). The surface itself is the 0-level set of the signed distance function (all the points where the distance to the surface is 0). Does that help? –  Ben Jones Dec 8 '11 at 5:00
1  
Wikipedia reference: en.wikipedia.org/wiki/Signed_distance –  Ben Jones Dec 8 '11 at 5:12
add comment

3 Answers

up vote 3 down vote accepted

From what I can see the signed distance you are asking about should not possess a closed form expression. Elliptical coordinates are not a constant distance apart, see http://en.wikipedia.org/wiki/Elliptic_coordinate_system

Evidently this is a difficult computational problem, http://http.developer.nvidia.com/GPUGems3/gpugems3_ch34.html

However, you can get a fair amount of the functionality you need with simple differential geometry, as you do not need to define the ellipsoid as a mesh. You can tell instantly whether a point is outside or inside based on your $f(x,y,z),$ so your comment about $\pm$ sign is entirely correct.

If a point is outside the ellipsoid ($f > 0,$) you can find the closest point on the ellipsoid by fairly rapid numerical methods. The closest point to some $(r,s,t)$ is the point $(x,y,z)$ in the same octant where the normal vector at $(r,s,t)$ is parallel to the vector $(x,y,z) - (r,s,t).$ The normal vector at $(r,s,t)$ is just a positive multiple of $$ \left(\frac{r}{a^2}, \frac{s}{b^2},\frac{t}{c^2}\right).$$ So, take as seed value the multiple $(\lambda x,\lambda y, \lambda z).$ At each stage, update the point on the ellipse by projecting the vector $(x,y,z) - (r,s,t)$ onto the tangent plane at $(r,s,t).$ Then, say, project that radially onto the ellipsoid.

I'll need to think about speed. For computer applications, a fast enough algorithm may be good enough, when a closed-form expression is not available.

Inside the ellipsoid, there is not necessarily a unique closest point on the surface. I might recommend just scaling your $f,$ just $- \sqrt{|f|}.$

Meanwhile, I recommended a certain book to Joseph O'Rourke, who does this sort of thing. John Thorpe, Elementary Topics in Differential Geometry.

share|improve this answer
    
Looks like it's harder than I thought! I'm doing some analysis of surface curvature which I get from doing finite differences on the signed distance field and was hoping this would be an easy example to play with. If there's no closed form solution, I think I'd initialize the cells that contain the surface and then use fast marching to propagate the field. I suppose I could also probably do the differentiation analytically for an elipsoid. Thanks! –  Ben Jones Dec 8 '11 at 7:44
    
It really depends on how it is to be used. If an approximation is good enough this can be done very quickly indeed. If you need to know the actual signed distance when you are close to the surface, either just inside or just outside, then you want the line segment from your point that meets the surface orthogonally, that is Lagrange multipliers. –  Will Jagy Dec 8 '11 at 22:32
add comment

A simple proposal is to use the average of the Euclidean distances to the foci, minus half the length of the major axis. This is zero on the ellipsoid, negative inside it, positive outside it, and asymptotic to the distance from the center of the ellipsoid in the far field.

share|improve this answer
1  
Does an ellipsoid with distinct $a,b,c$ have foci? –  Will Jagy Dec 8 '11 at 7:19
    
I'm actually interested in the signed distance close to the surface, so this won't work for me, but thanks for the idea! –  Ben Jones Dec 8 '11 at 7:45
    
@Will, of course you're right; it doesn't. I wrote the answer for an ellipse, then realized it needed to be an ellipsoid at the last minute. Obviously the edit was too hasty :). –  mjqxxxx Dec 10 '11 at 2:48
    
Hi, mjqxxxx, I still do not know how this information is to be used, so I don't know whether an approximation is acceptable. The nice part is that the person asking has his own resources for experimenting with different approaches. –  Will Jagy Dec 10 '11 at 4:06
add comment

Thanks to Will Jagy for his clear exposition, and many references. And thanks to pointing to me. But in fact, none of my books address this problem. However, Dave Eberly has addressed it quite extensively in his manuscript "Distance from a Point to an Ellipse, an Ellipsoid, or a Hyperellipsoid," which you may retrieve from this PDF link. Eberly is not only a master of the mathematics, but he cares about actually computing these quantities. He works out various cases, one of which may lead to a critical function having six roots!
     Eberly Fig. 3.2

share|improve this answer
    
Hi, Joseph. There may be something a little off in your pdf link. To me it shows an ellipsis ... which sometimes is a stand-in for other text, anyway it tells me Not Found at that server. –  Will Jagy Dec 10 '11 at 2:10
    
@Will: You are absolutely correct! I fixed the link. Sorry about that! –  Joseph O'Rourke Dec 10 '11 at 2:14
    
On MO you are editing images...If you get a chance, I am very fond of the "Jungle" paintings by Henri Rousseau, mostly 1905-1910. sunsite.utk.edu/FINS/loversofdemocracy/TheDream-Review.htm –  Will Jagy Dec 10 '11 at 3:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.