Factor spatial and geometric traits into a separate crate.

[olson-sean-k]

Traits in geometry::space and geometry::ops allow Plexus to interpret foreign types in a way that represent Euclidean spaces. This is important for providing the spatial operations required for working with meshes.

The geometry::query module begins to expand the scope of these traits. What if an application wants to use Plexus and perform geometric queries (e.g., collision detection) with MeshGraph as well as types from other crates? Today, this code is often duplicated among purpose-built crates.

The alga crate provides a great abstraction over algebraic concepts, including linear algebra and Euclidean spaces. Unfortunately, these types and traits are very general and difficult or impossible to implement for simpler types (e.g., the vector types from cgmath). Moreover, it seems unlikely that many crates will implement these types.

A crate that provides a minimal set of algebraic primitives strictly for Euclidean spaces could provide a lot of value. Such a crate could provide feature flags to implement these traits for commonly used types in the Rust ecosystem (rather than relying on adoption).

In order to support a broad set of simple types, related or composed operations could be used to avoid needing to express certain mathematical relationships. For example, to avoid requiring distinct representations for column and row vectors (duals), operations like Dot could be used in place of proper dual multiplication. This would likely work for crates like cgmath.

This could also allow geometric queries to be implemented in a generic way that works with nalgebra, cgmath, and any types for which users can implement spatial traits. An application using Plexus could also use this factored out crate for geometric queries elsewhere.

Such an API could be difficult to design, and any foreign types would need to provide access to their spatial data, which could involve expensive copies or complex references. For example, how would MeshGraph provide its geometry to this API? The alternative is probably to limit the scope of geometric traits and have users rely on crates that work specifically with their geometric types for queries.

[olson-sean-k]

I'm experimenting with this on a branch using a yet unpublished crate called theon. It moves the abstraction of Euclidean spaces and implementations for foreign types out of Plexus. I've also used this branch to redesign generators. This allows most of the geometry module to be removed, including the Duplet and Triplet types. 🎉

The theon crate uses traits to describe types in terms of linear algebra and limits the scope of its abstraction. These traits are more fast and loose than alga, which allows them to be more easily implemented. So far, I've been able to implement geometric queries in terms of these traits. Here's an excerpt of tests:

#[cfg(test)]
mod tests {
    use nalgebra::{Point2, Point3};

    use crate::query::{Aabb, Intersection, Ray, Unit};
    use crate::space::{Basis, EuclideanSpace};
    use crate::Converged;

    type E2 = Point2<f64>;
    type E3 = Point3<f64>;

    #[test]
    fn aabb_ray_intersection_2() {
        let aabb = Aabb::<E2> {
            origin: EuclideanSpace::origin(),
            extent: Converged::converged(1.0),
        };
        let ray = Ray::<E2> {
            origin: EuclideanSpace::from_xy(-1.0, 0.5),
            direction: Unit::try_from_inner(Basis::x()).unwrap(),
        };
        assert_eq!(Some((1.0, 2.0)), ray.intersection(&aabb));
        assert_eq!(None, ray.reverse().intersection(&aabb));
    }

    #[test]
    fn aabb_ray_intersection_3() {
        let aabb = Aabb::<E3> {
            origin: EuclideanSpace::origin(),
            extent: Converged::converged(1.0),
        };
        let ray = Ray::<E3> {
            origin: EuclideanSpace::from_xyz(-1.0, 0.5, 0.5),
            direction: Unit::try_from_inner(Basis::x()).unwrap(),
        };
        assert_eq!(Some((1.0, 2.0)), ray.intersection(&aabb));
        assert_eq!(None, ray.reverse().intersection(&aabb));
    }
}

This is a bit more obtuse than I expect user code to be, because it is expressed in terms of traits instead of types, but it illustrates the abstraction. This code also works for cgmath types; changing the E2 and E3 type aliases is all that is needed and these tests compile and pass as is.

[virtualritz]

I just wanted to say that you're really doing some kick ass work on this crate. 🎉🥳
Sorry about the OT comment. 😜

[olson-sean-k]

Work on this branch is almost complete. Before it's ready to land, the documentation and tests need to be updated and some changes to theon traits are needed.

Generators have also been changed. Instead of emitting convertible types that do not support any useful operations, each generator function specifies a type that implements EuclideanSpace.

use decorum::N64;
use nalgebra::Point3;
use plexus::graph::MeshGraph;
use plexus::prelude::*;
use plexus::primitive::sphere::UvSphere;

let mut graph = UvSphere::default()
    .polygons_with_position::<Point3<N64>>()
    .triangulate()
    .collect::<MeshGraph<Point3<N64>>>();

Finally, this change reorganizes types and traits from the geometry module, which is no longer exported and only implements conversions for foreign types based on Cargo features. Most traits have been moved to the crate root or into the graph module.

[olson-sean-k]

This is just about ready to land. I have reintroduced the geometry module as a home for conversion traits. Because theon requires that types implement a suite of traits, it could still be useful to have very basic types in plexus. Realistically those types would only be used when users first experiment with Plexus, so I'm still hoping to avoid reintroducing them.

The changes on the theon branch now support basic spatial operations and at least one example of an operation that requires solving an arbitrarily large linear system (see FaceView::plane and FaceView::flatten). There are some caveats, but this demonstrates that this approach is viable.

[olson-sean-k]

The theon branch has landed. 🎉