Integrate PGA (Projective Geometric Algebra) in Godot

[xiongyaohua]

Describe the project you are working on

I have been working on a road traffic simulator on and off for several years. It involves quite some geometrical calculations for things such as describing road networks, vehicle trajectories, sensor emulation etc.

Describe the problem or limitation you are having in your project

When I worked on my own project and contributed to Godot, I was doing geometrical calculation with the standard matrix + quaternion. There are always several things bother me:

1. The code is not intuitive. Because in the problem domain I was thinking with geometrical terms such as points, lines, plains, translates in some direction, rotate around something, but when writing code I need to convert them into vectors, matrices, quaternions, etc.
2. The code is long and full of corner cases. For example when finding intersection of two line, what if they are parallel; interpolating a polyline, what if there are sharp corners. Handle these corner cases make the code long, and it is also easy to miss some corner cases, leading to to bugs or undefined behaviors.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Recently I was introduced to something called PGA(Projective Geometric Algebra), and got convinced that it is a better way to do geometrical calculations in general, because

1. It is intuitive. Think directly in geometrical terms instead of some surrogate concepts.
2. It is powerful. For rigid body transform, it is equivalent with matrices and could supersedes quaternions.
3. It is efficient. It could be implemented with more or less the same number of instructions as matrices and quaternions.
4. It just works. Most operations always produce meaningful results, reduce the number of special cases. For example, the intersection of two parallel lines is a "point" at infinity, which can be used in further calculations.

To get a taste of PGA, the following course is recommended. https://www.youtube.com/watch?v=pq9YfdPHhIo&list=PLsSPBzvBkYjxrsTOr0KLDilkZaw7UE2Vc

It is 3 hours in total, and the last two lectures implemented with very concise PGA code several quite demanding programs, such as ray tracing through lens, IK system, rigid body simulation, showing the power of PGA.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Although in theory the PGA can be a general substitute for matrices and quaternions(e.g. PGA only rendering pipeline https://enkimute.github.io/LookMaNoMatrices/), it is currently too radical. It is better to start with places with low effort and immediate benefits. So I propose the following plan.

Step 1. Add a PGA library as third party dependencies, and re-implement Curve2D and Curve3D with it. There are several C++ library for PGA, but https://github.com/jeremyong/klein seems to be the most appropriate, as it is specialized and optimized for computer graphics.

Think of this step as follow ups for these efforts https://github.com/godotengine/godot/pull/64212 https://github.com/godotengine/godot/pull/69043 https://github.com/godotengine/godot/pull/80753

Step 2. If step 1 is going well, do produce more concise, clear and correct code, other self contained geometrical code of the engine can be considered, for example Line2D, CSG, Geometry2D, Geometry3D.

Step 3. In previous steps, the PGA is an implementation detail, and not seen by end user of the engine. If there is general interest from the end user, it can be exposed to GDScript. This step is more involving because of API design issues, probably requiring its own proposal.

If this enhancement will not be used often, can it be worked around with a few lines of script?

No

Is there a reason why this should be core and not an add-on in the asset library?

For one specific application it could be an gdextension, but to be generally available for different part of the engine, it needs to be in core.

[Calinou]

Note that as per the Best practices for engine contributors, we try to avoid integrating new large libraries in the engine as they pose a lot of problems:

• Buildsystem complexity goes up by a lot, along with compilation times. This is particularly the case with libraries that make extensive use of modern C++ features. We also need to make sure the library keeps building correctly when C++ exceptions and threads are disabled, as Godot does not use exceptions and threads aren't a hard requirement for building Godot as of 4.3.
• Binary size will go up by a non-negligible amount, which directly affects load times on mobile/web platforms.
• Applying dependency updates requires a lot of manual work.

We need to make sure the gain is worth it when integrating such a library.

[maxeonyx]

@xiongyaohua I don't know if you have looked at many PGA libraries, but they are actually quite small. It would be suitable to write or port a PGA "library" into godot itself. Ideally, it wouldn't really be a library, but instead implementing PGA semantics/conversions on Godot's existing types. I like the idea, also having recently learned about geometric algebra. It seems a much more intuitive way to work with 3D transformations and objects at a low level.

[xiongyaohua]

@Calinou > try to avoid integrating new large libraries in the engine

@maxeonyx > but instead implementing PGA semantics/conversions on Godot's existing types.

Thank you for the advice. After some consideration, I believe we may not need code as highly optimized as in klein. After all the Godot math classes, such as Vector, Transform, and Quaternion, are written in straightforward code.

I'll give it a try and see if I can come up with a reasonable PGA implementation myself.