next »

[nova++]

Oh man, this is not exactly my specialty. As the title says - I need to find the distance from a given point to the surface of a three-axis ellipsoid. Not the intersection point of the surface between the point and the center, mind you, but the nearest point on the actual surface itself

Edit: For further clarification to anyone reading this top post, what I really need is the nearest point on the surface, from which the distance can easily be produced.



(It can be assumed that the point and the ellipsoid are in the same coordinate space)

I have found this document on the subject:

http://eaas-journal.org/survey/userfiles/files/v4i1103%20TRIAXIAL%20ELL%C4%B0PSO%C4%B0D(1).pdf

But like I said... this isn't really my area of expertise and I am rather intimidated, unfortunately, so if nothing else, some "explain-like-I'm-five"-ing of that paper would help a ton.


Thanks in advance~

[qMopey]

This is a very difficult problem to solve. Here's an explanation: https://www.geometrictools.com/Documentation/DistancePointEllipseEllipsoid.pdf. Mind you David's code is all very over-engineered, but he usually does write robust stuff. All solutions will involve some kind of approximation, since the core of the problem results in a big nasty high degree polynomial, which must be solved iteratively.

Personally if I really needed ellipse to point, I would approximate the ellipse with a polygon (maybe like 16 faces or something). Then I would use the GJK algorithm to compute closest points between the point and the ellipse. Then the distance between these points is what you're after. I have an implementation of GJK here: cute_c2.h. To use GJK in cute_c2.h to solve your problem, it could look something like this:

Code:

c2Poly poly;
MyInitializePolyAsEllipse(&poly);

c2v point = MyGetPoint();
c2Circle point_as_circle;
point_as_circle.p = point;
point_as_circle.r = 0;

c2v witnessA, witnessB;
int dont_use_radius = 0;
float dist = c2GJK(&poly, C2_POLY, NULL, &point_as_circle, C2_CIRCLE, NULL, &witnessA, &witnessB, dont_use_radius);

witnessA and witnessB would be your closest points, and dist is your distance. One last thing for cute_c2.h, you want to modify C2_MAX_POLYGON_VERTS from 8 to something like 16 (so you can approximate your ellipse better).

To generate a nice ellipse approximation as a polygon, you can use any function to generate a sphere. Then scale your sphere by shrinking/growing your axes however you need. Once you have your array of points on the ellipse, you can use c2Norms to quickly compute all the normals, and then setup your c2Poly with your array of points, and array of normals.

This is just my own personal take, and it has a lot of benefits:

• Will work robustly in all cases. Very practical solution.
• GJK is a very fast function, and my implementation is a pretty good one. It's going to be faster than alternative root finders requiring a bunch of trig functions.
• The approximation can be tuned, and you can get a very accurate result, or you can get a "good enough" result very quickly.
• The implementation I have is already tested and known to be working. Just hook it up and go, and then forget about it.
• You can upgrade to shape casts if you need to later (sweep your ellipse over time). This is a feature you get from using the GJK algorithm -- sweep tests become pretty straightforward when using GJK as the work-horse. I'm adding sweeps to cute_c2 in a couple days.
• cute_c2.h is a single-header lib, so just drop it directly into your codebase and go. No need to even adjust your build system.

Anyways, hope that helps!

[nova++]

Since I'm doing this in Unity, I might have found something that does what you described for me - the convenient ClosestPoint function, with an ellipsoidal mesh collider: https://docs.unity3d.com/ScriptReference/Collider.ClosestPoint.html

However, it's complicated a bit by the fact I'm doing this at fairly large scales (planets) in double precision for translation down into something that the engine can digest a bit better (It's Complicated). So using a typical mesh collider doesn't seem like it'd work too well. And in that case, I'd have to do it myself anyway.

Dashed are my naive hopes that there would be a nice simple mathematical solution... Oh well. There's something out there, anyway.

I'm gonna see if I can get my head round the GJK algorithm, at any rate. Thanks for that.

[qMopey]

Well you should probably be scaling your points down to a tiny scale, with a really tiny planet mesh. There's no reason you need to do the collision detection at a huge scale. Once you get your result, you can transform the result back into your big world scale.

One guy was porting cute_c2.h to C# so he could use it in Unity... https://github.com/RandyGaul/cute_headers/issues/102. But he's disappeared Also I don't think cute_c2 will work for you, since it sounds like you're doing 3D stuff. cute_c2 is 2D only.

Anyways, if you ever find a solution I'd be curious what you come up with My intuition says you may have to adjust your game design to use spheres instead of ellipses though  

[nova++]

Well you should probably be scaling your points down to a tiny scale, with a really tiny planet mesh. There's no reason you need to do the collision detection at a huge scale. Once you get your result, you can transform the result back into your big world scale.

Yeah, that's what I'm moving towards. For what I need this for (information readout, very rough raycasts, etc), I don't really need any decimal places of precision, so it should be just fine.
(It also is already scaling the points down for display to the player rather than trying to render things 1:1, so I can just work with it at that scale)

In general, the double precision stuff is kept to a minimum - storing planet orbital parameters, positions, rotations, and velocities, as well as the player's viewing position. I know I could probably get away with reworking everything to float, but this is just what I've found most agreeable for myself.

One guy was porting cute_c2.h to C# so he could use it in Unity... https://github.com/RandyGaul/cute_headers/issues/102. But he's disappeared Also I don't think cute_c2 will work for you, since it sounds like you're doing 3D stuff. cute_c2 is 2D only.

Yeah, that's a shame... I still appreciate the reference a lot, though. Thank you again

Anyways, if you ever find a solution I'd be curious what you come up with

I'll definitely post about it, either here or on the devlog thread I plan to make at some point!

My intuition says you may have to adjust your game design to use spheres instead of ellipses though 

It was spheres at first, then I started working toward ellipsoidal planets for the extra variety and realism, since it's not something often depicted... and, well, we all make decisions we have to live with I guess


Edit:

Hmmmmm.



Hmmmmmmmmmmmmmmmmmm.

So, I think I'm independently arriving at a solution that was described elsewhere? In a weird way, of course.

Basically, I'm taking a mesh asset reference - in this case an icosphere exported from Blender - and copying its triangle and vertex list. I iterate through all the triangles and use each one's vertices to make a plane.

Then, I take the dot product of the normal of that plane and the direction from the triangle's center to the check position, and compare it with previous ones, eventually finding the largest, thus finding which triangle is aimed at the test position the best.

With that triangle, I use its plane to produce the closest point on said plane to the check position, and hey presto, I have my distance.

But...

It's weird. As you can see in the gif, the final closest point jumps around and is rarely confined to the triangle. At the same time, it somehow doesn't seem to be affecting the result. The distance readout isn't really making any obvious jumps, even when I veeeery slowly nudge it along. Hell, maybe I can try graphing the value over time to visually check if that's the case.

It's so close to working. I can almost lick it.




Edit 2: I honestly think it IS working. I made a slider thingy to serve as a visual indicator of what's going on, as well as mapping out the number, and watched the thing go at 1/100th timestep to spot any shenanigans but there were none to be found. The oddest thing is something I expected, the actual rate of change is a bit "pulsed" - just a side effect of it checking against a rotating plane.

It seems to be working, but it's bugging me. It's very unsettling that it's somehow not resulting in any error.

[qMopey]

You've implemented the Separating Axis Theorem (SAT). GJK will be more efficient, but SAT is perfectly fine, assuming it's fast enough for your game

Good job! Looks great  

P.S.

You solution also gives me an idea: you can compute squared distance from each point on the ellipse to your query point. Then keep the shortest distance. This will give very similar results to what you have now, but be even faster than computing planes.

You can take this one step further, and just use a dot product for each vertex (keep track of the max signed value), assuming you've transformed your ellipse to the origin, and applied that transform to your query point. The maximal dot product, in this case, will be correspond to the closest vertex. It will be hard to beat this one in terms of performance, and, it's also very simple. This is what GJK would be doing internally!

[nova++]

I was about to say that it seems like just getting the nearest vertex would result in a very jumpy and steppy result but... it wouldn't, would it? Considering the only "jump" happens when one vertex is found to be infinitesimally closer than another one, meaning there's no noticeable stepping. I'll have to give that a try.


Edit:

Well, I tried it. It does work, and it is slightly faster, but it's definitely a lot more stuttery by just measuring vertex positions. There are no big jumps but there are points where it "bounces" slightly, and I can visibly see the stutters on the marker whereas I couldn't with the (apparently) SAT implementation.


Edit2:

Here's another gif of the two side by side.



If you look close, the nearest-vertex approximation is noticeably jumpier, especially during the peaks. Ignore the jump when it reaches the bottom of its travel, that's just from an incorrectly-timed loop.

Both are off just enough to irritate me... I'm also annoyed at the mathematicians of the world for not having come up with a nice and simple formula for this

Sigh...this is why it takes me so long to get anything done...

[qMopey]

SAT will be slightly less jumpy because you're sliding across the plane (presumably, if you're snapping to the plane). Vertex makes only discrete jumps across vertices. If you want a "less jumpy" number, then smooth your distance over time. I'm assuming your game isn't going to be drawing lines to your planet, right? You just need a distance value, right?

Code:

player.distance = lerp(player.distance, calc_actual_distance_approximation(player.position, ellipse), 0.1);

The above line lerps from the previous distance to the new one, biasing by a factor of 10 the previous one. Or in other words, a rolling average of the last 10 ticks. Ta da. Smooth.

Edit: Actually, even if you're drawing lines to your planet, you can just smooth the closest point over time as well! Smoothing

[nova++]

SAT will be slightly less jumpy because you're sliding across the plane (presumably, if you're snapping to the plane). Vertex makes only discrete jumps across vertices. If you want a "less jumpy" number, then smooth your distance over time. I'm assuming your game isn't going to be drawing lines to your planet, right? You just need a distance value, right?

Code:

player.distance = lerp(player.distance, calc_actual_distance_approximation(player.position, ellipse), 0.1);

The above line lerps from the previous distance to the new one, biasing by a factor of 10 the previous one. Or in other words, a rolling average of the last 10 ticks. Ta da. Smooth.

Edit: Actually, even if you're drawing lines to your planet, you can just smooth the closest point over time as well! Smoothing

Mm. I appreciate the idea but I don't know how well it will work. In the case of the game, the planets are large enough that I'm not sure how noticeable the discrepancies might actually be... I suppose to really find out I'll have to just implement it in the game proper soon.

Edit: I've got someone else who's deep down the mathematics and geometry hole who is going to be looking into this for me sometime soon. He's convinced there's a non-iterative solution, but we'll see if his gut feeling turns out right.

[Daid]

As your objects most likely don't "jump" trough space often, and thus are near the previous location. Won't the iterative solution work very well if you use the data from the previous tick? With large movements the distance calculation would be less accurate, but won't that sort of simulate real sensors that have issues with this as well? Might just work for your game.

[nova++]

As your objects most likely don't "jump" trough space often, and thus are near the previous location. Won't the iterative solution work very well if you use the data from the previous tick? With large movements the distance calculation would be less accurate, but won't that sort of simulate real sensors that have issues with this as well? Might just work for your game.

Yeah, that's kinda what I'm thinking. However, I'm holding out for that person I mentioned - a non-iterative solution would be useful enough I'm putting off implementing the iterative one until I find whether or not it can really be done. Or at least simplified to a nicer iterative solution.

[gimymblert]

Code:

float sdEllipsoid( in vec3 p, in vec3 r )
{
    float k0 = length(p/r);
    float k1 = length(p/(r*r));
    return k0*(k0-1.0)/k1;
}

http://www.iquilezles.org/www/articles/distfunctions/distfunctions.htm

[nova++]

Code:

float sdEllipsoid( in vec3 p, in vec3 r )
{
    float k0 = length(p/r);
    float k1 = length(p/(r*r));
    return k0*(k0-1.0)/k1;
}

http://www.iquilezles.org/www/articles/distfunctions/distfunctions.htm

Ah - thanks! I didn't even see this reply. I have not tried that function yet, but I have a feeling it unfortunately might not be what I'm looking for. I'm increasingly realizing that I need more than just the distance - I need an actual position on the surface.

[gimymblert]

look around in that site it might have what you need, probably

[Zaphos]

Code:

float sdEllipsoid( in vec3 p, in vec3 r )
{
    float k0 = length(p/r);
    float k1 = length(p/(r*r));
    return k0*(k0-1.0)/k1;
}

http://www.iquilezles.org/www/articles/distfunctions/distfunctions.htm

(Note the website say this is a bound on the distance, not an exact distance ...)

[nova++]

So, I tried that distance function and it does indeed appear to work, so that's something at least.

I just need to figure out how to turn that into an actual position on the surface.

Edit: Well, it doesn't seem like that function is fully accurate actually...



Unless I'm horribly mistaken and you can't actually make an ellipsoid by scaling a sphere in 3 axes.

[Zaphos]

If you want an exact/direct solution I don't think you'll find a better answer than the one in the Eberly PDF ... unfortunately it's just not that easy of a problem ...

[nova++]

If you want an exact/direct solution I don't think you'll find a better answer than the one in the Eberly PDF ... unfortunately it's just not that easy of a problem ...

Yeah, I just need to really sit down for a few hours and try to work through it I guess, which is kind of what I've been avoiding all along.

[raigan]

I don't understand the obsession with ellipsoids.. just use a union of spheres or capsules! Your collision tests will be much simpler to implement, plus you can easily do dynamic-vs-dynamic sweep tests (good luck sweeping two ellipsoids against each other).

In 3D, absolutely no one is going to be able to tell the difference between an ellipsoid and a couple dozen well-chosen spheres/capsules. In 2D you can write some code to nicely cover an ellipsoid with circles/capsules to get a very accurate approximation without going crazy trying to actually deal with real ellipsoids at runtime.

Along with quadtrees (instead of a simple grid) ellipsoids seem to be a recurring obsession for gamedevs where it's just not worth the effort. IMO

[nova++]

I don't understand the obsession with ellipsoids.. just use a union of spheres or capsules! Your collision tests will be much simpler to implement, plus you can easily do dynamic-vs-dynamic sweep tests (good luck sweeping two ellipsoids against each other).

In 3D, absolutely no one is going to be able to tell the difference between an ellipsoid and a couple dozen well-chosen spheres/capsules. In 2D you can write some code to nicely cover an ellipsoid with circles/capsules to get a very accurate approximation without going crazy trying to actually deal with real ellipsoids at runtime.

Along with quadtrees (instead of a simple grid) ellipsoids seem to be a recurring obsession for gamedevs where it's just not worth the effort. IMO

If there's some quick algorithm to placing spheres in such a way that you can reliably get a surface position at a given point on an ellipsoid, I'd certainly love to hear it. I'm open to approximate/iterative solutions even as I search for a mathematical one. I am not doing collision, by the way. I am doing things very similarly to collision tests, but I just need that surface point.

Also, I was not aware that ellipsoids were an obsession (and am confused by the quadtrees vs grids thing, although that's probably out of scope for this thread  )