Add support for 3 component points

[Makogan]

This project is really cool, I have been trying to get PGA working in a project of mine but there is a lot of minutia with numerical stability and I think this project's implementation is more robust than what I can make.

It would be awesome if it could support points that are 3xf32 under the hood in addition to the 4xf32 point struct it has.

For graphics and real time applications, not storing the last component and renormalizing between operations represents a memory foot print reduction on about 25%.

Many operations in games are raw data operations, e.g. copying buffers from CPU to GPU or searching for an item in a list. That additional f32 is a non negligible penalty that the user should have the option not to incur.

The only reason I was forced to make an inferior PGA library is that all available rust libs have no support for 3 component points.

Would it be possible to add an additional ComapctPoint that uses 3 floats and not 4?

[wrnrlr]

Tradeoffs between time and space are always difficult to estimate but one guesses that always having to normalise a point by dividing by its homogeneous coordinate using the Newton-Raphson method (for numerical stability) is probably slower for most usecases then having to copy one more float.

For optimal performance this library uses SIMD instructions and those are either 2, 4, or 8 in length which are lucky fit for our 4 dimensional space.

If you want to store points or transfer them to the GPU there is an implementation of From<mint::Point3<f32>> to get the x, y and z coordinate of a point, but remember to normalise first.

At the end of the day one can use this library just for the geometric algebra and then convert back and forth to traditional linear algebra vectors but this leaves one with two math libraries with multiple representations. For example In the glam crate they make a distinction between a Vec3 which uses 3 floats and an AVec3 which uses a f32x4.

One of the design goals of this library is for it to be conceptually easy to use and not have developers worry about implementation details like this.

[Makogan]

Tradeoffs between time and space are always difficult to estimate but one guesses that always having to normalise a point by dividing by its homogeneous coordinate using the Newton-Raphson method (for numerical stability) is probably slower for most usecases then having to copy one more float.

it depends on the frequency of operations, if the system is dominated by the PGA operations then you are 100% right. But if the system is dominated by iterations over the elements and copying then it is not.

At the end of the day one can use this library just for the geometric algebra and then convert back and forth to traditional linear algebra vectors but this leaves one with two math libraries with multiple representations. For example In the glam crate they make a distinction between a Vec3 which uses 3 floats and an AVec3 which uses a f32x4.

Having two math libraries for points is doubly problematic. On one end one needs to convert back and forth between the two, which leads to lots of useless data copying which slows down the system. It also makes things harder to work with as data is no longer uniform across the program, some functions would operate on PGA types, some on glam or nalgebra types.

One of the design goals of this library is for it to be conceptually easy to use and not have developers worry about implementation details like this.

This goes beyond just an implementation detail.

Let us say we want to use this library for animation. A character model commonly has about 80k vertices. If 10 skinned animated objects are on screen this yields 800k total vertices.

With 3 component points. The memory footprint is 800k 3 8 = 19200k bytes of memory. With 4 components per vector it would be 25600k bytes. So a difference of 6400k bytes. A single 3 component model with 80k vertices occupies 1920k bytes.

So if we take out the last component in the vertices we can push 3 additional animated elements in the space being occupied by the last component.

This is not just an implementation detail. It's a major memory overhead. The primary applications for PGA are Games, Engineering CAD systems, Physics simulators and similar systems.

All of these care about memory usage and speed, by not giving an option for a compact vertex type the library becomes less suitable for the kinds of systems that could best make use of it.

I think it would be really helpful to have the option to have compact points. Copying the points to a different data type is not an option in memory nor speed bound systems, which are common in the domains where PGA is most common.

[wrnrlr]

I've not run into memory problems yet, but I am not against this in principle. Lets call this new type Vec3 instead of CompactPoint, how would this Vec3 work in practice?

The most minimal approach would be to just add the extra Vec3 type and keep the other elements as they are. Then you still need to implement the join, meet, sandwich, and contraction operators. At least the sandwich operator for rotos, translators and motors, and contraction or operators between vec3s will be the most used. For this we can't use the current implementation in /maths because they also use simd. To implement these without using simd one has to suffle these out of their register. Maybe also some new methods to process Vec3s in bulk, so the variants only need to be shuffled once? Or maybe we need pre-shuffled transformations anyway, but this will make our API a lot more complicated?

I don't know if this is worth it. For example I am using this library to write a physics simulation and for this I am associating one or more motors for every point to represent forces acting on this point.

The usecase you describe makes sense for rigid bodies but for things like finite element methods the transformations are more expensive then the points anyway. The optimisation you suggest makes sense but this is not a bridge I want to cross before I really need to.

If you have a specific need for this feel free to try this in a branch ad see how far you can get.

[Makogan]

I will try to do so, but I am not super optimistic :sweat_smile: part of the reason I am looking for PGA libraries is because I tried to roll my own and I am finding some numeric issues that are clearly an implementation bug.

The usecase you describe makes sense for rigid bodies

Note, not just for rigid bodies, I used the skinned animation example because it's an in between of rigid bodies and per point transformations. In a skinned model you only compute transformations per joint in a skeleton, this typically means that you have orders of magnitude less transforms than you do vectors. Making the primary bottleneck data transfer operations instead of data transform operations.

I don't know if this is worth it. For example I am using this library to write a physics simulation and for this I am associating one or more motors for every point to represent forces acting on this point.

This is fair. I will try to modify the library for these operations but it might take me a while. If I do so I would do the naive approach of internally casting a Vec3 into a 4 coordinate homogeneous point, calling the relevant operation and casting back. It would be a waste of cycles and memory reads, but at least it would be easy to prove correctness and a more optimal solution could be implemented in th efuture.

[Makogan]

I want to make a suggestion. I think there might be a way to easily enable interoperability of this library with foreign data types.

One could define the Mul/Add etc operations generically on a type implementing a simple point_castable trait. That trait would have a single method fn to_point(&self) which returns a 4 floating point compatible g3 point.

It would then use the already defined operations on the point type meaning that in terms of additional code it's relatively negligible. This could all go into a single file that is optionally enabled by a configuration macro.

The biggest advantage is that if someone needs to interoperate between this library and a popular alternative, like say nalgebra. It is trivial to do so.

I can give it a try if you are willing to coach me as to where and how I could add the mentioned feature. And if you think the change is a good idea of course.

[wrnrlr]

I am not familiar with this technique, the way I understand your proposal is something like this:

trait PointCastable {
    fn to_point(&self)->[f32;4]
}

impl Add<PointCastable> for Point {
    fn add(&self, other:trait PointCastable)->Point {
        //...
    }
}

The one question I have about this is what would be the difference between this and and using the From and Into traits that are used throughout the rust ecosystem?

There is the mint package that has specified a number of interface for these kind of Math INTerchange problems.

For mint::Point3 I have implemented:

#[cfg(feature = "mint")] impl From<mint::Point3<f32>> for Point { #[inline] fn from(v: mint::Point3<f32>)->Point { Self::new(v.x,v.y,v.z) } }
#[cfg(feature = "mint")] impl From<Point> for mint::Point3<f32> { #[inline] fn from(v: Point) -> Self { Self { x: v.x(), y: v.y(), z: v.z() } } }

Arguably the From<Point> is not the most efficient and maybe should be using a transmute::<f32x4,[f32;4]>(simd_swizzle!(v.0, [1,2,3,0])) or something like this.

I also don't know if implementing these traits is transitive, so having mint for g3 and mint for glam gives you g3 for glam. Maybe not or if it does it might not be very efficient and in that case maybe having feature flags for glam and nalgebra is a good idea.

At any rate playing nice with other math libraries is in scope, I just haven't done much research/testing into the best way.

[Makogan]

The trait I was suggesting would not be meaningfully diffrent from the standard Into trait. So that's probably a better idea.

But yes the suggestion would be:

impl Add<T> for Point 
where T : Into<Point>
{
    fn add(&self, other : T)->Point {
        self + Into<Point>(other)
    }
}

i.e. create generic products/sums, etc... for any type that can be casted into Point. This means immediate interoperability with any math library. All the user needs to do is define the into trait for their use case, which is 3 lines of code.

If you think this is a good suggestion, I could try to add the generic methods and a couple of unit tests, if you point me to the right location.

[wrnrlr]

Me thinks it is awkward to just have addition between two different type where one is sneakily cast to the other. This breaks all sorts of conventions like a + b == b + a and a - b == a + b*-1, not to mention all the other operators. Except if you want to define those other operators too, but then you end up with a zoo of traits. Like why is nalgebra not implementing this for g3 😎. The Into and From are two things from Rust I never quite liked but I think better to stick to the conventions when interchanging between crates.

[Makogan]

So this is a no, from what I am hearing?

[jamen]

I think its a good idea to lean into arrays for interop with other libraries. For example glam has

impl From<Vec3> for [f32; 3] { .. }
impl From<[f32; 3]> for Vec3 { .. }
impl Vec3 { fn to_array() -> [f32; 3] { .. } }

Lets say there was a math function you wanted to use, but it only accepted glam::Vec3 (like one of glam's own functions)

fn foo(x: glam::Vec3) { .. }

if g3::Point had impls similar to glam above, we could go like:

foo(point.to_array().into())

Which isn't too bad imo.

It does get more complicated beyond points and vectors. It might make sense to have a few different functions dealing with arrays, instead of (or in addition to) the From/Into traits. Like in glam, there is Mat4::to_cols_array and from_cols_array for example.

This does give you a way to do wrong stuff, like doing Vec4 -> [f32; 4] -> Quat is probably wrong unless you're doing something weird/intentional. But thats already possible with a bit more work (manually passing the components around), and to me array types kind of convey a sense of type erasure, interoperability, or data transfer in a math library.

[jamen]

A better example would've been libraries like rapier3d or parry3d using nalgebra types. Or lyon and etagere using euclid types. Almost every math library deals with arrays in some way, so it makes for a nice way of doing interoperability imo. Often you can avoid wrangling with dependencies by just doing [x, y, z].into()

[wrnrlr]

I agree that array are a good use for this. There are already a number of implementations of it, maybe there should be more but here is where we can find what we already have:

https://github.com/wrnrlr/g3/blob/main/src/point.rs#L85