Could Bevy support non-Euclidean geometry?

[finegeometer]

Euclidean geometry is the geometry we're used to. Triangles have angles adding to 180°, circles have circumference 2πr, et cetera. But there are also non-Euclidean geometries. In hyperbolic geometry, for example, there's more space than you expect — circles have circumference 2π*sinh(r), which grows exponentially! On the other hand, spherical geometry has less space than you expect, eventually curling around on itself; the whole universe has finite volume.

OpenGL, and similar systems, are made for rendering scenes in Euclidean geometry. Yet if you know what you're doing, it's no harder to render scenes in, say, spherical geometry!

(Proof: Here's the code for a simple Euclidean geometry renderer, and here's the code for a corresponding spherical geometry renderer. The latter is only fourteen lines longer, and that's mainly because I used a more complicated mesh.)

This is possible because GL doesn't really care about precise distances or angles. It matters which surfaces are in front of which others, but not how far in front. As a result, the differences between Euclidean and spherical geometry are unimportant to GL; it'll happily render either.

Geometry without a concept of distance and angle is called projective geometry. And OpenGL works with projective geometry the whole way through.

Could Bevy do the same? What would it take to generalize Bevy to support projective geometry, and hence simple non-Euclidean geometries?

Projective Geometry, and Vec3 vs. Vec4

In projective geometry, we represent points as nonzero Vec4s. Two points are the same if one vector is a scaled copy of the other. For example, (3,4,5,1) is a point. (6,8,10,2) is the same point, but (3,4,5,2) is a different point.

Projective transformations are just invertible Mat4s. Since (for real numbers k) M * (k * v) = k * (M * v), projective transformations correctly take equal points to equal points.

This is why you see vec4s and mat4s all over OpenGL.

---

In the Euclidean case, it is convenient to always write a point as a vector whose last coordinate is one. (If you have (x,y,z,w), rewrite it as (x/w, y/w, z/w, 1).) We then often drop that last coordinate, representing a point as a Vec3.

But in other geometries, that convention is unhelpful. In spherical geometry, for instance, it is instead convenient to represent a point as a vector whose length is one. Other geometries will have other conventions, most of which don't yield a convenient simplification to Vec3.

The upshot is that when generalizing to projective geometry, most instances of Vec3 in the code should be replaced with Vec4.

Transform

Bevy's Transform and GlobalTransform types are currently tied to Euclidean geometry; they consist of a translation, rotation, and scale. But there is already appetite to change this. RFC 53, for instance, suggests dedicated RectTransform and Transform2D types specialized for UIs and 2D games. I've also heard talk of a potential f64-based Transform, for when more precision is required. So we might as well allow users to define their own Transform types, including non-Euclidean ones.

What's needed from a Transform type?

• Transform must be composable, so that it can be propagated up the hierarchy.
• Composition must be associative, so the behavior of transform_propagate_system doesn't depend on implementation details.
• I'm not sure if there needs to be an identity Transform, but it will probably exist. The same is true for inverses.
• Transform must be convertible to Mat4. If we don't support non-Euclidean geometry, strengthen that to Affine3A.
• Composition of Transforms should be compatible with multiplication of Affine3A/Mat4s.

(Actually, Bevy's non-uniform scale breaks that last rule. Therefore, I don't like non-uniform scale. But that's a discussion for another time.)

In other words, Transform should be a group, equipped with a group homomorphism to Affine3A/Mat4.

Issue with GlobalTransform

GlobalTransform seems to have two different purposes.

From the user's point of view, GlobalTransform is a way to learn the absolute position of an entity, even if it's buried in a hierarchy. Maybe you want to position a bullet relative to a gun, but the gun is held in a hand, which is attached to an arm, which is attached to a player. So you set the bullet's Transform equal to the gun's GlobalTransform.

From this perspective, we clearly want GlobalTransform to have the same representation as Transform. In pull request #4168, @alice-i-cecile even suggests that it should be replaced by something like Inherited<Transform>. So if we have several Transform types, we'll want several GlobalTransforms as well.

But GlobalTransform serves another purpose. The renderer basically uses it as an Affine3A. In this use-case, we definitely do not want multiple GlobalTransforms; that'd force us to duplicate all of the render systems!

Since there's currently only one Transform type, Bevy can get away with using GlobalTransform for both purposes. But this won't work when we have several Transform types. We'll need different types — maybe something like Inherited<Transform> and RenderTransform?

Rendering

As I mentioned, bevy_render basically uses GlobalTransform as an Affine3A. If we can generalize that to Mat4, bevy_render should work for non-Euclidean geometry as well.

I believe this can be done, with some thought. Some Vec3s will become Vec4s; some computations will need rethinking. But it should be possible.

A potential issue is that axis-aligned bounding boxes don't generalize well to non-Euclidean geometry. I don't understand Bevy's rendering process well enough to know if this is a problem.
Bounding ellipsoids would generalize, but I suspect those would be more computationally expensive.

bevy_pbr will be trickier — some parts of it, like the shader, might just need to be rewritten for each geometry. But other parts, like materials, should be reusable. We'll want it to be easy to replace the geometry-specific parts without having to copy-paste the geometry-independent parts,

More Info

There's certainly more I could say on this topic.

• I could talk about holonomy and tangent spaces, and why working with vectors is tricker in non-Euclidean space.
• I could talk about how to implement Transform for spherical or hyperbolic geometry.
• I could talk about how to create a geometry from a symmetric 4x4 matrix.

And those are just the things I already wrote up for this post, before I realized I was including way too much detail.

If you'd like to know about those, or anything else about non-Euclidean geometry, feel free to ask! I'll be happy to answer your questions.

[alice-i-cecile]

One of the simplest and most important bits of non-Euclidean geometry is simple 2D wrapping (think Joust).

How do you think users should implement this sort of problem: both in terms of a current design, and under a hypothetical non-Euclidean future?

[finegeometer]

One of the simplest and most important bits of non-Euclidean geometry is simple 2D wrapping (think Joust).

How do you think users should implement this sort of problem: both in terms of a current design, and under a hypothetical non-Euclidean future?

I think I'm using a more restrictive definition of "non-Euclidean" than you are. I'd say that example has nontrivial topology, but still Euclidean geometry. Other games in that category would include Portal or Manifold Garden. For true non-Euclidean geometry, see HyperRogue or the newly released Hyperbolica.

In any case, this proposal has little effect on how I would deal with nontrivial topology. Even if I were to make a game with both wrapping and non-Euclidean geometry (e.g. a hyperbolic octagon with all 45° angles, with opposite edges glued together), I would treat the two issues separately.

[alice-i-cecile]

Right, you're totally correct. My example has locally Euclidean geometry, even if its topology is more exotic.

[alice-i-cecile]

In other words, Transform should be a group, equipped with a group homomorphism to Affine3A/Mat4.

Firmly agree. I really appreciate how you've laid this out for folks without a math background.

This sort of insight is critical to designing user-controllable transform types. We already have at least 3 extremely compelling and distinct use cases (2D, 3D and UI), with candidates such as fixed point and f64 transforms emerging.

A potential issue is that axis-aligned bounding boxes don't generalize well to non-Euclidean geometry. I don't understand Bevy's rendering process well enough to know if this is a problem.

Frustums and rays are the other key geometric primitive used for camera culling and occlusion; I'm not sure that they'll play nicely with non-Euclidean geometry out of the box.

We'll want it to be easy to replace the geometry-specific parts without having to copy-paste the geometry-independent parts,

Agreed. We should aim to optimize common case performance, but provide clean escape hatches for users trying to do very unusual things.

From this perspective, we clearly want GlobalTransform to have the same representation as Transform. In pull request #4168, @alice-i-cecile even suggests that it should be replaced by something like Inherited. So if we have several Transform types, we'll want several GlobalTransforms as well.

But GlobalTransform serves another purpose. The renderer basically uses it as an Affine3A

This is a helpful and clear insight: we should try to keep this in mind when redesigning.

[finegeometer]

In other words, Transform should be a group, equipped with a group homomorphism to Affine3A/Mat4.

Firmly agree. I really appreciate how you've laid this out for folks without a math background.

Thanks!

Frustums and rays are the other key geometric primitive used for camera culling and occlusion; I'm not sure that they'll play nicely with non-Euclidean geometry out of the box.

Those should work fine. Any concept which can be defined in projective geometry will work equally well in Euclidean geometry, spherical geometry, et cetera. This includes concepts like "point", "line", "plane", "conic", and between. And a frustum, for instance, is just a region bounded by six oriented planes.

(There are more complicated non-Euclidean geometries, which aren't special cases of projective geometry, for which this could cause trouble. But I intentionally did not suggest supporting those geometries, because they don't play nicely with OpenGL either.)

In fact, planes need no changes to work in projective geometry. A plane can still be represented as a Vec4 (really a covector). And just as in the Euclidean case, you test a point against a plane by comparing their dot product to zero. The only difference is that the point's Vec4 might not have the form (x,y,z,1).

I did notice that the calculation of the far plane in Frustum::from_view_projection was phrased in a Euclidean-specific way, but after some thinking, I found an equivalent calculation that generalizes to the non-Euclidean case.

(talking about the two uses of GlobalTransform)

This is a helpful and clear insight: we should try to keep this in mind when redesigning.

Thanks! I figured this out by experimenting with implementing my proposal, because this problem was making the code ugly. But this issue will apply as soon as there are multiple Transform types, even if non-Euclidean geometry isn't supported.

[finegeometer]

Meta question: Should I be using the "Write a reply" feature on your comments, or the "Write a comment" feature on the discussion?

[alice-i-cecile]

Meta question: Should I be using the "Write a reply" feature on your comments, or the "Write a comment" feature on the discussion?

Use reply to specific comments; use Write a Comment when you want to start a new sub-thread :)

[james7132]

I'll be the devil's advocate here and ask for a generalized use case. The split of the hierarchy from Transforms is largely being driven by the need to use it for more than just transforms, or non 3D Euclidean space where there are two existing very common use cases already in-engine (2D and UI). The desire to have a f64/fixed point transform system are nice and have their use cases, but they're likely to be something ecosystem crates provide, not bevy proper. Other than specialized games like Hyperbolica and Portal, I can't immediately think of big use cases for non-Euclidean transforms. While fun, those games are rather rare. Is there a compelling use case in typical game development for these kinds of spaces? If not, could this not live as an ecosystem crate?

[james7132]

The core render pipeline is built with three separate phases: Extract, Prepare, and Render. The one that is needed here is Extract, this stage pulls the GlobalTransform from the app world into the render world by queuing commands that generate both the view projection and the individual mesh transforms. You'll need to make equivalent copies of these extraction systems that use your Transform types(s) and spawn the same rendering info (i.e. mesh/texture/material) handles. These systems typically aren't too complex to handle either particularly since they're entirely focused on stripping down only the requisite rendering information. Beyond that, the prepare and render phases will run as is.

You normally would hook into the AABBs for entities, which then is used to compute the visibility of objects, but you'll likely need to make your own visibility systems here too.

[finegeometer]

Thanks for the help!

I continued following your suggested path:

• Replace Transform/GlobalTransform with your own types.
• Compute visibility with your own types.
• Add two custom extract systems in the RenderStage::Extract that extract the view matrix and transformation matrices.
• Provide a custom vertex shader to accommodate the change in space.

The first point was easy. I could basically ignore the second point, by just assuming everything's visible. That'll have a performance cost, but I'm still prototyping.

But the third point ran into an unexpected problem: bevy_render::view::ExtractedView contains GlobalTransform.

This is entirely unnecessary. Bevy only ever uses ExtractedView.transform in two ways:

• transform.compute_matrix()
• transform.translation
  And both of those are easily computable from an Affine3, or even a Mat4.

Anyway, since I couldn't reuse ExtractedView, I tried duplicating all of the queries on it. It felt like it should be unnecessary, but at least it would work...

Nope. That didn't work either.

• bevy_render::view::prepare_view_uniforms queries bevy_render::view::ExtractedView.
• bevy_render::view::prepare_view_uniforms directly accesses the fields of bevy_render::view::ViewUniform.
• The fields of bevy_render::view::ViewUniform are private.

So I'm stuck again.

[james7132]

This is entirely unnecessary. Bevy only ever uses ExtractedView.transform in two ways:

* `transform.compute_matrix()`

* `transform.translation`
  And both of those are easily computable from an `Affine3`, or even a `Mat4`.

I wouldn't call this unnecessary. A Clone call is faster here than compute_matrix, and the transform type is smaller than either of those two types, allowing for better cache coherency during extract and prepare. Offloading the matrix computation to the prepare phase allows it to run in parallel instead of blocking the one hard sync point with the app world. That said, we could probably just use compute_matrix in the extract system and use either of those two types, given the view count is typically pretty small. I'd open a PR to change this.

However, if you run into this for meshes and other objects, you'll likely need to find an alternative here because computing the matrix during extract for those is probably going to negatively impact rendering performance for everyone who isn't leveraging this.

[finegeometer]

However, if you run into this for meshes and other objects, you'll likely need to find an alternative here because computing the matrix during extract for those is probably going to negatively impact rendering performance for everyone who isn't leveraging this.

Mesh extraction already does this conversion. Cameras and lights don't.

[cheako]

@james7132 Was there ever an example published? To respond to the devil "Other than specialized games" that's literally every game that's going to be popular once finished! I heard the same nonsense from the perl guys and there poe framework, in there eyes if the application hadn't already been written then it wasn't worth writing and *they stuck to that. Just banned me for outlining my requirements, I guess they thought I was too demanding. * It was just one guy, but it was "the guy" and he didn't care that someone else might have been able to answer my questions.

[ickk]

It will be useful to have a couple of tests or examples to use as a reference if/when this is undertaken.

Even might be worth making a fork with just the specific changes to transform and render required to get each example to function, as it will illustrate precisely where issues are and inform & expedite the design and review of a proper generalisation.