Distinguishing affine and vector quantities in the type system

This is essentially a copy-paste of a question I asked in the uom repository. I asked it there originally, because that's the crate in the context of which I was inspired to have these thoughts.

But now I realize that they may be relevant to a wider audience. Off the top of my head I'm aware of the existence of dimensioned, which is similar to uom; and the ideas may be relevant to people who don't use either of these or actively read their issues.

So I hope it's not inappropriate to repeat the question here.

In trying to use uom to get the Rust type system to help me understand my simulation code better and to reduce the bugs in it, I'm wondering to what extent I should distinguish between 3D Points and 3D Vectors. For example

  • Point - Point should give Vector
  • Point + Point should not be allowed
  • Vector - Vector should give Vector
  • Vector + Vector should give Vector
  • Point + Vector should give Point
  • Scalar * Vector should give Vector
  • Scalar * Point should not be allowed
  • etc.

and I'd like the type system to be aware of it. This can be done without much trouble (beyond verbosity) by defining separate Vector and Point types and implementing the relevant std::ops traits accordingly.

But it's not clear to me whether these Vectors and Points should have the same uom types representing their components: should the above rules apply to the components of Point and Vector at the type level, too? For example, should

  • point.x be some affine version of Length,
  • point1.x - point2.x return some vector version of Length,
  • point1.x + point2.x be disallowed by the type system?

This, in turn, makes me wonder about the distinction when it comes to other scalar quantities that appear in my code, and that leads me to wonder more generally about the distinction of affine and vector quantities in physical units.

It seems that the distinction has been recognized as important by the software development community in the context of dates and times: most languages' date/time libraries distinguish between (affine) dates, and (vector) durations, tough they don't use the affine/vector nomenclature explicitly.

But I don't see any evidence of this distinction being used much in scientific code.

Do you have any thoughts or relevant experience? Would it be worthwhile to explain these differences to the type system? Would it be more trouble than it is worth? How would it fit in with uom?

4 Likes

A related issue is keeping track of reference frames. If you're writing a vehicle simulation, for example, you will likely have some Points and Vectors that are world-centric and others that are vehicle-centric. Adding a vehicle-vector to a world-vector naïvely is unlikely to produce the correct result: You need to account for the vehicle's rotation first.

2 Likes

When applied properly, this technique is worth its weight in gold!

Something I've used it for is CAD applications. Often you are dealing with different coordinate spaces and when everything is a Point it's super easy to interpret a coordinate in model space (i.e. cartesian coordinates for where a component is logically located in your model) when it is actually in canvas space (i.e. location on the screen).

Ages ago I made a toy CAD engine to experiment with some ideas I'd been wanting to roll into our CAD application at work, and one of them was using the euclid crate to tag each graphical type with the space it is in. From there, the only way to convert a Point<f32, DrawingSpace> to a Point<f32, CanvasSpace> was by going through a Viewport (this contained things like the current zoom level, which part of the model the camera was centred on, etc.), which would do the corresponding flip about Y, scaling, and translation.

From the arcs::CanvasSpace docs:

The coordinate system used for graphical objects rendered to a canvas.

The convention is for the canvas/window's top-left corner to be the origin, with positive x going to the right and positive y going down the screen.

To convert from DrawingSpace to CanvasSpace you'll need a crate::components::Viewport representing the area on the drawing the canvas will display. The crate::window module exposes various utility functions for converting back and forth, with crate::window::to_drawing_coordinates() and crate::window::to_canvas_coordinates() being the most useful.

I think the reason you don't tend to see this used much in the science realm is because scientists don't particularly care about preventing these sorts of bugs at compile time. To a lot of scientists a number is just a number, and the type system stuff would just get in their way.

It's also the case that most scientific code is used once then thrown away, so it's not worth going to the effort to make your code more maintainable when you can just look at the processed data, realise it's wrong, add a x * METRES_PER_MILE to the offending line, and continue with your work.

That's one of the reasons you see most scientific code written in Python and suffering from a bad case of primitive obsession.

2 Likes

So, here is some theory.
Given a vector space, one can extract an affine space.
But given an affine space, one cannot get a vector space canonically (without any choice, functorial). (One can get the vector space by choosing an origin)

Moreover, there are affine maps between affine spaces, for example the coordinate projections.
But there is no affine map from R^3 (as affine space) to R^1 as vector space (because this question makes no sense, similar to adding values having different units.

Upshot:
In my experience, as in michael's, this often helps a lot. And not only for physical units, but always when you have objects from different categories.

But: (this is pre const-generics experience)
If you try to support this in a generic way, for example, for all vector space dimensions, than this is a lot of effort (hint: dimension is not a number, but a locally constant function if you need to support enums ...)

So, as always, do as you like ( I would try to implement this)

I don't know whether Rust's current const generics would make this nice, but you could try out something I'll call "compile-time homogeneous coordinates".

It'd be something like this:

struct Homogeneous<T, const W: isize>([T; 3]);
type Point<T> = Homogeneous<T, 1>;
type Vector<T> = Homogeneous<T, 0>;

Then you have

impl<T, const W1: usize, const W2: usize> Add<Homogeneous<T, W2>> for Homogeneous<T, W1> {
    type Output = Homogeneous<T, W1 + W2>;
    ...
}
impl<T, const W1: usize, const W2: usize> Sub<Homogeneous<T, W2>> for Homogeneous<T, W1> {
    type Output = Homogeneous<T, W1 - W2>;
    ...
}

That means you can do p1 + p2 - p3 and still get a Point as it should be, without needing to p1 + (p2 - p3) to fit the intermediate types into what you've defined. Similarly, it'd be fine to Neg a point, it just would give you something distinct from both Points and Vectors, but if you added another Point to it you'd get back to a Vector.

It also has the nice advantage that you don't need to write separate Sub impls for Point-Point, Point-Vector, and Vector-Vector, since they all just work and do the thing you wanted.

(I assume someone else has thought of this before, but I've not actually seen it.)

7 Likes

Exactly what I've been thinking about implementing at some point for my software renderer. And also differentiating between Euclidean, projective (clip space), and z-divided (NDC space) points, after having gotten them confused way too many times… Maybe also distinguishing between object, world and view space.

You can also implement averaging of Points:

impl<T, const W: usize> Homogeneous<T, W> {
  /// Example: (p1 + p2 + p3).avg_point()
  fn avg_point(&self) -> Point<T> {
    Point<T>([self.0 / W, self.1 / W, self.2 / W])
  }
}

I take it that homogeneous does NOT allude to these homogeneous coordinates.

Do the types with W > 1 have any meaning, beyond bookkeeping to ensure that the final result makes sense?

If you wanted to make the type system aware of the affine/absolute vs vector/relative distinction at the level of the components of Point and Vector, presumably you'd push W down into T, along these lines:

struct Homogeneous<T>([T; 3]);
type Point<T> = Homogeneous<Coordinate<T, 1>>;
type Vector<T> = Homogeneous<Coordinate<T, 0>>;

struct Coordinate<T, const W: isize>(T);

It's absolutely those homogeneous coordiates, just with the w moved to a compile-time W.

That's why @riking 's example above of dividing through by W works.

Did you have a place where you'd expect that to be useful? I can't think of any situation in which I'd want that.

Which would make instances of Vector (W = 0) represent points at infinity, rather than the vector space of translations in the Point affine space.

Furthermore Point::new(1,1,1) and Homogeneous<T, 2>::new(2,2,2) should be different representations of the same point in 3D space, and yet here the type system considers them to be two completely different things.

Clearly I'm missing something.

I find this very puzzling. If you see why it might be useful to have the type system distinguish between 3-dimensional vector spaces and 3-dimensional affine spaces, why would you consider in not useful for the type system to distinguish N-dimensional vector spaces from N-dimensional affine spaces in general, including the specific case N=1?

Yes. I'd expect this to be useful everywhere where both of the following conditions hold

  • I find it useful to distinguish between the affine space of Points and the vector space of Vectors, and
  • I want to perform computations on the individual components of those Points and Vectors.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.