Ellipsoid Shape?

[Kermalis]

Hello, I'm toying around with a Jolt project for the first time. I saw this image in the docs:
I found it here.

It looks like a screenshot from Blender, but it got me curious about an ellipsoid shape in the engine because other physics engines I've tried usually don't have it (not counting mesh/hull). I know Jolt has a ScaledShape, but I read here that SphereShape cannot be scaled non-uniformly like this.

Since a (colliding dynamic) ellipsoid would be more useful to me compared to a box, I wonder, have you considered adding it to the library without requiring the user to make a custom shape class? I looked around and couldn't find other references to this shape with Jolt.

An example of a game that heavily relies on ellipsoids is TrackMania:

You can see that the entire car is made of them rather than cylinders/boxes. It's a great approximation and makes the game feel intuitive too. That game is from the mid-2000s, so I assume performance wouldn't be a concern for that shape, but that's just a guess on my part.

...

Unrelated, but I also saw on another discussion that you'd be open to having a Discord community if there was more demand for it. I'd like to also let you know I'd find it useful, and you can use the search feature to find previously asked questions too. I'm in a Discord community for https://github.com/bepu/bepuphysics2 and it has been useful for really small/quick questions compared to opening up several discussions on GitHub (which I have also done).

Thanks for your time :)

[jrouwe]

Making an ellipsoid shape would be possible. A naive implementation would inherit from ConvexShape and mostly require implementing a GetSupportFunction function (see e.g. TaperedCapsuleShape for the functions that need implementing). Mathematically it's not a nice shape to work with because of its quadratic function (x^2/a^2 + y^2/b^2 + z^2/c^2 = 1). This means that if you try to speed up the basic collision detection implementation provided by ConvexShape it becomes complex quite quickly.

E.g. solving the closest point to an ellipsoid requires an iterative solver:

JoltPhysics/Jolt/Geometry/Ellipse.h

Lines 30 to 63 in c5997c5

	Float2 GetClosestPoint(const Float2 &inPoint) const
	{
	float a_sq = Square(mA);
	float b_sq = Square(mB);
	// Equation of ellipse: f(x, y) = (x/a)^2 + (y/b)^2 - 1 = 0 [1]
	// Normal on surface: (df/dx, df/dy) = (2 x / a^2, 2 y / b^2)
	// Closest point (x', y') on ellipse to point (x, y): (x', y') + t (x / a^2, y / b^2) = (x, y)
	// <=> (x', y') = (a^2 x / (t + a^2), b^2 y / (t + b^2))
	// Requiring point to be on ellipse (substituting into [1]): g(t) = (a x / (t + a^2))^2 + (b y / (t + b^2))^2 - 1 = 0
	// Newton Raphson iteration, starting at t = 0
	float t = 0.0f;
	for (;;)
	{
	// Calculate g(t)
	float t_plus_a_sq = t + a_sq;
	float t_plus_b_sq = t + b_sq;
	float gt = Square(mA * inPoint.x / t_plus_a_sq) + Square(mB * inPoint.y / t_plus_b_sq) - 1.0f;
	// Check if g(t) it is close enough to zero
	if (abs(gt) < 1.0e-6f)
	return Float2(a_sq * inPoint.x / t_plus_a_sq, b_sq * inPoint.y / t_plus_b_sq);
	// Get derivative dg/dt = g'(t) = -2 (b^2 y^2 / (t + b^2)^3 + a^2 x^2 / (t + a^2)^3)
	float gt_accent = -2.0f *
	(a_sq * Square(inPoint.x) / Cubed(t_plus_a_sq)
	+ b_sq * Square(inPoint.y) / Cubed(t_plus_b_sq));
	// Calculate t for next iteration: tn+1 = tn - g(t) / g'(t)
	float tn = t - gt / gt_accent;
	t = tn;
	}
	}

(this is for an ellipse, but it's the same for an ellipsoid)

Capsules are much easier to work with and cheaper to evaluate and optimize for. So if you can get away with those I would.

Unrelated, but I also saw on another discussion that you'd be open to having a Discord community if there was more demand for it.

Someone created this channel (that I look at approx. once per year):

https://discord.com/channels/827044312902139924/952370256163266770

For me Discord does not work as there are many conversations interleaved on the same timeline. That makes it really hard for me to track what has been answered and what not. Also, other people cannot learn from the answers unless they browse the entire timeline.

[Kermalis]

Hello again, I'm still looking for improvements I can make to my hitbox system.

I've been using a regular box collider ever since I created this thread here. It works decently but I need something more accurate. This week I'm finally testing out compounds but they're not necessarily fitting my needs.

The red box is the hitbox I've been using which is the simple box.

The purple ones are the compound I'm currently trying to get working. It approximates the roof and spoiler of the cars better, but the issue is really the corners. Since the top/bottom of the box is poking above the capsules, there are really bad collisions when anything catches those portions. It also defeats the goal of having rounded corners, since I still have sharp boxy corners.

Unfortunately I don't really see a good way of solving this problem with uniformly-scaled primitives. A sphere for the top would be too thin horizontally/laterally but too tall vertically. I want the smooth corners from the capsules, but don't see how the front of the car would work with the box connecting the capsules. If I had 1 capsule stretched across the entire car and 1 for the roof/spoiler, then it would work. However, that would require being able to scale them on their X axis non-uniformly, which they currently can't. Ideally it'd be like this:

Also, I haven't performance tested it yet, but this compound has 6 shapes which is more than I anticipated using. I have good performance with the box but can't afford too much more here per car.

Any suggestions? I don't need it to be ultra accurate, but I do need smoothness along the top, sides, and corners. 2 ellipsoids really would be a perfect solution in this case, or just 2 capsules that could scale on one axis non-uniformly. Now I'm also considering a very low poly convex hull, but then the corners still aren't smooth, and that's potentially way more expensive than what's worth since these are dynamics. I'm not sure what to do here. If I had the skills, I'd implement the ellipsoid shape myself (and possibly create a PR since I believe it can be a great addition despite the performance). In my case, the shape would be worth the performance tradeoff, depending on how expensive they would be. I'm also not sure what I'd need to do to create a capsule shape that can scale in this way I would like.

[jrouwe]

I would simply go for a low poly convex hull shape. I doubt that anyone is going to notice the sharp corners. If you do notice, then you can easily tesselate those corners a bit more. Performance wise I don't think it should be a big issue.

[60k41p]

Hi,

I've implemented support for ellipsoids as a collision shape in 60k41p/godot#4 , in the Jolt physics module of the Godot game engine.

Would you like to see this upstreamed ?

[Kermalis]

I'm interested in this still, but of course it's up to jrouwe. I'm not sure how you managed to avoid the iterativeness while keeping it accurate, since I didn't see loops, but I'm not the expert here.

Have you done any performance testing? How does it line up with sphere/capsule/box/etc?

I guess this is a good time to mention what I ended up doing with the above situation. I did end up using a convex hull, and in my specific case, it ended up being the same performance as the box, which I was definitely not expecting. Even with 64-128 cars, which is way more than I'll be using, it had no performance decrease. So my project is clearly not bottlenecked by the dynamic bodies moving (they don't collide often since they're driving above the ground due to raycast springs).

The hull I am using ended up at 101 vertices, which is a lot compared to what I expected to use, but when I initially switched, it was over 200 vertices, so I got away with shaving a lot away over time in Blender while still keeping round-ish sides and corners.

However, the car can get stuck faceplanting a wall even if it's not 100% perpendicular because it's not truly round, and no amount of steering will get it automatically unstuck. It will always resolve to a flat part of the hull no matter what, and that's where an ellipsoid could really save the day.

So yeah for me an ellipsoid would still be really useful to mess around with, even if I stick with this hull I've been using for almost a year. I'd see how it deals with the faceplanting situation in my project. But again it depends on how performant it is :)

That's my story, so maybe it can give some insight into how the library could be used

[60k41p]

On the iterativeness: there are no loops because the collision detection never solves a closest point directly. The shape only implements GetSupportFunction, and the support point of an ellipsoid has a closed form, so it's exact and O(1) per query. My understaind is that the iteration happens inside Jolt's existing generic GJK/EPA implementation which other convex shapes are also subject to.

With the second commit the shape now treats radii as the exact outer surface (collision surface = the ellipsoid itself, with the convex radius used only as an internal margin, like in box/capsule).

On performance: No 'proper' benchmarks yet. I think I'll just see how it behaves in the real scenes and keep an eye out for performance anomalies. My guess is that contact query complexity should be in the sphere/capsule ballpark. Ray/shape casts will fall back to the generic GJK so expected to be slower than spheres and capsules. Happy to run a more proper comparison if this is gets greenlit for merge.

In theory this should address the faceplanting issue with your car. Since there are no flat regions the contact normal rotates continuously with wall angle.

One concern I have that probably won't apply in your case is the extreme-aspect ellipsoids, as I will have very thin ellipsoids in some cases. I'm yet to test it... But continuous collision detection is a likely solution there (with the performance hit).

[jrouwe]

Nice! You reused almost all of the code from the base class, resulting in a very simple and clean implementation. Some collision detection functions could be specialized because there exist faster analytical solutions than GJK/EPA. I think it could be integrated into Jolt like this, but I'm a bit torn if this should be a separate shape or if I should merge the functionality into the SphereShape. An ellipsoid is a non-uniformly scaled sphere, so a ScaledShape containing a SphereShape could be used to make it more generic / not need an additional shape. This option would come with a bit of extra overhead as SphereShape would need to test if the incoming scale is non-uniform and then fall back to a different implementation for certain functions.

Please keep your branch alive, I'm going to look into this when I have a bit more time.

[Kermalis]

In my opinion, I'd prefer it as a separate shape. Sphere is extremely important for performance and in my case, specially handled as well. An EllipsoidShape on its own indicates a specialized class, and can be assumed to be slower to evaluate than a Sphere. Also, this way we could capture separate shape types rather than checking a sphere's scale additionally (for whatever reason).

Last point is that some people could additionally assume a scaled sphere has no performance impact (even if you wrote it in the docs) since that's how box works. Someone could measure performance incorrectly in benchmarks, especially if they're less experienced with physics engines or even a vibecoder paying little attention.