Discuss practical usages of algebraic structures in real world code

[brendanzab]

At the end of the day, the intention of this library is to provide a common basis for generic programming in Rust. It would be good to experiment with real world use cases, and then use those to drive the design of the library. It would also allow us to convince people of the benefits of this approach. As asked by @nical on gitter:

I'm going to ask some rather silly questions, I am more used to focusing on maths to fix a specific problem (like building a graphics engine) rather than design abstractions around math concepts. silly question 1) what are the common use cases for high level math abstractions like this ? Or phrased differently, can we list (roughly) the motivations

At the end of the day, we want this to be of a benefit as opposed to a hindrance. I can certainly see that we could get side-tracked down the route of mathematical taxonomic insanity without considering whether this is actually useful and confusing to end users. Thoughts?

[nical]

In particular, I am interested in cases where it is more practical and/or useful to reason with abstract vector spaces rather than just implicitly work with a simple euclidean space and the implied rules.

The taxonomy is definitely intimidating, but if it has its uses we should not shy away from accepting it as the right tool for the right job. As a newcomer I don't know what these right jobs are.

[sebcrozet]

[...] to reason with abstract vector spaces rather than just implicitly work with a simple euclidean space and the implied rules

I'm not sure I understand what you mean here. Are you wondering what is the point of defining traits for vector spaces where we could just work with the exact types like Vector3? What do you mean by simple euclidean space (what is "simple")?

Or phrased differently, can we list (roughly) the motivations

I can give a concrete example by listing the motivations behind my contributions to this library. For ncollide, I need three kinds of abstractions:

• dimensional-genericity: most algorithms will work fine for 2D, 3D, et often higher dimensions. There is usually no point in writing a 2D or 3D-specific version because given the proper abstract mechanisms they are all equivalent. Of course some algorithms (like convex hull computation) still require a dedicated implementation in which case we can select the right one at runtime by testing the dimension of the vector space (and this test will probably be optimized away by llvm).
• representation-genericity: transformation groups (isometries, rotations, translations, etc.) are often seen as matrix groups. However, other representations are possible and may be preferred by the user for some reasons. For example, 3D rotations (the group SO(3)) have two major representations: 3x3 matrices and (unit) quaternions. Both have their advantages and inconvenient depending on the applications so I want to let the user choose which one he wants.
• substructure-genericity: this one is the most useful and allows code refactoring and performances improvements! I'll take the specific example of ray-casting here, but that applies at many, many places on ncollide. To cast a ray you need three elements:
  • a geometrical shape s (a ball, a cube, a convex polyhedra, etc.)
  • the position p of that shape (typically an isometry: translation * rotation * reflexion)
  • the ray r (its origin and direction).

A typical ray-casting function will thus usually take three arguments: cast_ray(s, p, r) -> hitpoint and returns a hit point. If the implementation works for isometries, it will work for any of its subgroups as well. Thus p may be a pure rotation or a pure translation. Being generic wrt the transformation group will allow you to sometimes pass for p only a 3D vector (pure translation), a 3D matrix (pure rotation) or a 3x4 matrix (isometriy). Obviously, the specialized version using a 3D vector will be faster than the one using the 3x4 matrix. But it goes even further! It is not unusual for the positions of the shape to be already encoded inside of the shape data structure itself. For example a ball in space can either be fully described as a center and a radius:

Ball { center: Point, radius: Scalar }

or as a radius alone and a separate transformation matrix:

Ball { radius: Scalar }
Isometry { translation: center, rotation: identity }`

This also applies to more complicated structures (convex polyhedra, triangle meshes, etc.) that may not be rotation-invariant. If we don't have substructure-genericity, a user of cast_ray will be forced to pass a 3x4 matrix which will always be the identity transformation. Obviously multiplying anything by this matrix will be a complete waste of computational time. With substructure-genericity, we can use a very special subgroup of the isometry group: the 0-dimensional subgroup which contains only the identity element. In nalgebra, this is the Identity structure. The implementation of multiplications by it are all no-ops so the compiler will just remove them when it will specialize the call to cast_ray(s, Identity::new(), r).

_By the way, I know that we could just expose ray-casting with cast_ray(s, r) -> hitpoint where r is the ray multiplied by the inverse of p. But all my preceding reasoning applies in more complex situations, e.g., the GJK algorithm, where the multiplication by the transformation must be inside of a loop and may become a bottleneck._

So I need all those kinds of abstractions and they are all well expressed by common mathematical concepts: finite-dimensional vector spaces, group actions and subgroups. Euclidean spaces tie all of them together.

[sebcrozet]

(For people interested in this discussion, it is continuing on gitter).