The thesis provides background on 3D graphics, type systems, and Rust, and reviews related literature and practical work. As its primary contribution it presents a case study of the geometry API of my software renderer library, Retrofire, which is more strongly typed than almost all similar APIs while striving for good developer experience and minimal time or space overhead.
Abstract:
This thesis investigates the use of type-level techniques for reducing programming errors in 3D graphics programming, in particular as relates to the representation of geometry and coordinate transformations. Existing theoretical and practical work on the subject is fairly scarce, and a review of several popular 3D programming APIs reveals that none attempt to alleviate or prevent such errors either at runtime or compile time.
A case study of Retrofire, a software 3D rendering library written in the Rust programming language, is presented. Retrofire employs generic types (parametric polymorphism), traits (type classes), and tag (phantom) types to rule out many of the identified programming errors at compile time, with a goal of minimal or zero impact on runtime performance.
The library is evaluated from the viewpoints of performance and developer experience. The conclusion is that the API is useful and helps prevent bugs in real-world programming, but more experience in writing complex applications with Retrofire is required for deeper understanding of its ergonomics. The library also appears to attain its goal of minimal performance overhead compared to a more conventional API; questions requiring further study include optimal memory management and use of SIMD vector operations.
Ah, I see you stuck with the traditional Point-vs-Vector distinction.
Admittedly I just skimmed it -- 100+ pages is long -- but I didn't see any notes about how often you ended up doing things like point - ORIGIN to to point-to-vector conversions and such. How did it feel to use? I remember last I played with something like this it wasn't quite as nice as I'd wished.
I've been curious if something that erased the strict distinction by leaning into homogeneous coordinates more would help the ergonomics. I previously described this a bit in
because the strict point-vs-vector distinction means you can't get a triangle centroid via (p1 + p2 + p3) / 3, for example, but a different encoding in types might improve that.
Yes, that's certainly one of the main ergonomics issues I've found. My solution is to basically concede that in a Euclidean space points do have a known canonical (but non-privileged) origin, so:
points and vectors can be interconverted at will by simple to_vec() and to_pt(); there are no From impls currently but I wouldn't be totally against the idea;
points and vectors can be converted to homogeneous coordinate vectors and back with to_hom() and to_real() if needed (the latter does w division – which does mean that (p.to_hom()+q.to_hom()+r.to_hom()).to_real() magically becomes the centroid :D);
points have Mul<Scalar> overloads; you could do the same with a matrix anyway and it's just too useful not to support;
there's a method for affine combinations (and centroids as a special case), but admittedly it's not maximally ergonomic; a macro might help.
Of course, not all affine spaces have canonical origins, but for ℝn points it works fine.
It would indeed be great to encode the homogeneous component with const generics so that Goldman's "legitimate" operations like (p+q+r)/3 would magically have point/vector types but "illicit" ones would not[1]. In the absence of generic_const_exprs, it could be prototyped with C++, I haven't found existing code in the wild that tries to do that though. (Also, it now occurs to me that I could've discussed this a bit in the "future directions" section but oh well :D)
Returning a "useless" type instead of just failing to compile has its own ergonomics issues though, of course. ↩︎
Well, don't get too eager to dismiss origin privilege! Games as recent and high profile as Halo Infinite had issues with animation (IIRC) due to being too far from the world origin in f32 coordinates.
Haven't looked at the paper yet, so I'm assuming there's some reference to this already, but some kind of type tagging vectors with application semantics is something I could imagine being incredibly handy; for the issue above (other than just busting up to f64 which is what I'm guessing they did) you could easily ensure animations run in "player local" coordinates that need to be mapped from world coordinates.
This also reminds me of Jon Gjengset's coordinate library for aeronautics Sguaba, I'll be interested to see what the overlap is there, since that's not particularly formally based (other than the international standards it implements) to my knowledge
True, the finiteness of floats is often the reason we can't have nice things
some kind of type tagging vectors with application semantics is something I could imagine being incredibly handy;
Yep, that's basically what I did. Being a 3D graphics library, Retrofire works with mostly the standard model, world, view, clip, ndc, and screen spaces (frames) and so defines tag types for those in particular, but they're not special and custom tag types can be written at will.
Yeah, I cite Sguaba in the related work section! Geographical coordinate systems are definitely something that benefits a lot from type-level encoding of what kind of coordinates you are in exactly. I haven't delved into the API particularly deeply though.
Oh, I should also note that I decided to go with distinct point vs vector (and color) types (rather than aliases of some more general type) because type aliases have some ergonomics issues – particularly the fact that often (but not always) the generic name is exposed in compiler error messages, which usually makes them more verbose and harder to decipher.
(Speaking of colors, they're weird and the more you stare at them the weirder they get. They don't really fit nicely into the linear vs affine classification (and not just because nonlinear colors are nonlinear), RGBA colors do not behave like 4-vectors because the alpha channel is Different(tm), and so on.)
Oh god, I hadn't even considered trying to "correctly" handle color!
Honestly the closest you can do to a "correct" color representation is a CIE XYZ vector and recognize that alpha is a completely separate issue to color (eg you might be using coverage, order independent rendering techniques have their own weird approach to storing it), but that's pretty impractical when you're dealing with textures with aggressively limited bitdepth...
I'm looking forwards to seeing what you're doing there!
Thanks! I went with LaTeX (and Overleaf) mostly because the faculty had a LaTeX thesis template and it was the path of least (initial, maybe not long-term) resistance. I did recently write another project report in Typst though.
