Collaboration / Discussion
gnzlbg opened this issue · 5 comments
I am also writing a library for 1d/2d/3d geometry manipulation in Rust, maybe we can collaborate or discuss approaches if you are interested :)
I was aiming at something more like CGAL, but CGAL partially overlaps with PCL, e.g., for point cloud processing CGAL also has "point sets" build on top of trees and algorithms that work on that.
In my experience every application of "geometry" has its own particular idiosynchrasies and is going to want to work with their own types. For example some might want to store a triangle as "3 points in a struct", while others might want to store it as a "pointer to a point_set/mesh and 3 indices into the mesh vertices", or associate some data with the triangle centroid/edges/vertices/...
So what I would like is a library in which the primitives are abstracted using traits, and the algorithms are implemented on top of these traits, so that users can have their own types with their peculiarities, and by implementing a couple of traits, get access to most of the algorithms.
Ideally, this would be bundled together with an implementation of the most common primitive types, that users could reuse to build their own types if so desired, as well as some common data-structures and I/O (VTK's VTU, STL, PLY...).
Discovering the set of traits required to implement the algorithms is where the meat of the work would be at, and having some implementation of the basic types as well as algorithms for those would is crucial for nailing this right.
The types and data-structures I was thinking about are: point1/2/3d, vector1/2/3d, line1/2/3d, ray1/2/3d, segment1,2,3d, polygon1/2/3d, box1/2/3d, aabb1/2/3d, triangle2/3d, plane2/3d, polyline1,2,3d, polysurface3d and polyhedra3d. For the data-structures at least point_set<T: Point> (on top of a binary/quad/oct-tree for point clouds), half_edge<T: Polygon> (a half-edge data-structure for triangulations), a bounding volume hierarchy bvh<T: AABB>, and a kd-tree.
The set of traits I was thinking about would be something like: AmbientDimension, PrimitiveDimension, VertexIterable, EdgeIterable, FaceIterable, Point: AmbientDimension + PrimitiveDimension + VertexIterable, Segment<Vertex: Point>: AmbientDimension + PrimitiveDimension + VertexIterable + FaceIterable, Line, Ray, Plane, PolyLine, Polygon, Polyhedra, ... Triange: Polygon, ...
The algorithms I am interested about are computing the centroid of a primitive, integrals (e.g. lenght/surface/volumes), set operations: merging (e.g. two polylines), intersection (e.g. ray-triangle, ray-aabb, polygon-polygon...), splitting (polygon-polyine, polyhedra-plane, polyhedra-polysurface), distance between primitives, bounding box computations, ... working with signed-distance fields (Marching Cubes...).
Anyhow hopefully once one has the "fundamental" traits, adding more algorithms in the spirit of the PCL (keypoints, segmentation...) should be orthogonal to adding more algorithms in e.g. signed-distance fields. The "advanced" algorithms typically require the "basic" ones anyways (e.g. computing the normal of a triangle/polygon).
Comparing this with PCL, the main difference is that this sounds "way more generic" (hence why I think it is closer to CGAL). I wouldn't want "genericity" to get in the way of pragmatism though, and luckily Rust traits make genericity easier to achieve sanely than C++'s templates. As mentioned above, the only reason I want "genericity" is to allow users to have their own types for points, edges, volumes with their own application specific particularities without having to reinvent the algorithms, which I think is a goal worth pursuing.
All in all it is a huge amount of work, but I think it is fun, and hard tasks like figuring out the set of traits are better tackled in a team.
gnzlbg sounds good. I also already implemented quite a lot in https://github.com/I3ck/lib_2d , some more trees in https://github.com/I3ck/HGE2D and https://github.com/I3ck/LazyTrees . Especially the C++ code could be easily merged into this.
I also split the traits into true-readonly, constructable and mutable, which should make it possible to write algorithms for the minimal trait, making it easy for users of the library to implement their own types.
Yes, besides the polysurface/polyhedra and the half-edge data-structure I have already implemented most of this in C++ as well, will definetely take a look at your implementations!
I'll close this issue. Feel free to request any algorithm / structure or to provide references (just open new issues then)