lukaskalbertodt/lox

Fast polygon mesh library with different data structures and traits to abstract over those.

lox's Issues

Properly update Criterion

Criterion 0.3 soft-deprecated a couple of functions our benchmarks use. These should be update to BenchmarkGroup, presumably.

Probably move `cast` module into separate crate

The module is very involved and seems like it could better be its own crate, also to reduce the API surface area of lox.

Implement additional mesh formats

Reading and writing files should be easy. Thus this library should support a variety of mesh format. These are the ones we absolutely want:

• PLY
• STL
• OBJ
• OFF

But we probably want to implement even more than that. Related Wiki page.

Tests for fev-map

All map implementations should have an extensive test suite. Since all those tests are nearly identical, we should create a macro to quickly create a bunch of tests.

Tracking issue: unstable features

TODO: Fill out later, once this library is more complete

Add half edge API

The EdgeMesh offers users to explicitly reference edges. We should also have a similar interface for half edges as this is useful in several situations. However, this could be tricky as different data structures deal with this differently. HEM has boundary half edges, DEM does not, for example.

Decide on syntax for `mesh!` macro

We have two arrays: vertices and faces. For each element we can specify additional properties after the "core info". The question is how to specify multiple properties. Potential syntaxes:

• As tuple:

  vertices: [
      v0: (prop0, prop1, prop2), // multiple
      v1 : (prop0), // single
  ]
  

  Simple, but feels like too many parenthesis, especially for a single element.

• As tuple with special casing single value:

  vertices: [
      v0: (prop0, prop1, prop2), // multiple
      v1 : prop0, // single
  ]
  

  Problem: if someone tries to specify a position as tuple (after all (f32, f32, f32) implements Pos3Like), strange errors will occur (it will be parsed as three properties instead of one). Generally, it feels like too much magic IMO.

• Comma separated, with semicolon seperated elements

  vertices: [
      v0: prop0, prop1, prop2; // multiple
      v1 : prop0; // single
  ]
  

  This diverges from the normal Rust "list like syntax": [a, b, c].

Random open questions from my notes

Not sure how much of this still makes sense, but I wanted to transfer everything from private notes to GitHub.

• Open Questions
  • Maybe impl Deref<Target=Handle> for ElementRef
  • Make {Element}Ref thingies a single pointer? Also make them always valid, i.e. non constructable by users.
  • Add add_vertex(pos) and the like methods to fat meshes (automatically?)
  • derive(FatMesh) to add several methods like add_vertex(position).
  • Think about abstracting over (core mesh, position) again to make passing fat meshes into algorithms easier
• Final touches
  • Rename {Element}Ref to {Element}?
  • Maybe remove derive_more dependency
  • Guard more stuff behind features
  • Go through all TODOs
  • Remove profile.release debug=true
• IO
  • Write edges and edge data
  • Think about more fat meshes? Vertex normals?
  • Make ErrorKind nicer
  • Add null sink
  • Config::into_writer should be in a trait (and then we can add wrote_to_mem)
• hsize and handles
  • Add cargo feature to use u64 as hsize
  • Add cargo feature to check for overflow in release mode too
  • Think about how to avoid using handles in wrong universes
  • Think about how to avoid using handles to already deleted things
  • Derive Handle for structs with one hsize field
• Unsorted
  • Think about indexing Prop-thingies with Into<Handle> or so
  • Think about implementing conversions between meshes + maybe a way to quickly add all faces and only fix adjacency info afterwards?
  • Add fat::EmptyMesh or implement Mem* for all core mesh types
  • Think about futures and progress bars
  • Add try_add_face which returns a result
  • Let user disable deletion to avoid storing the bitvec?

Ideas/new features for `lox-cli info` tool

• Print properties of the mesh that require analysis:
  • Is closed?
  • How many connected parts?
  • All faces triangular? Quad faces?
  • Unconnected vertices
  • ...
• Output infos in different formats (including JSON)
• Make it possible to pass multiple files to the command
• Maybe specific questions like --query is_solid where it just prints true or false?

IO improvements and ideas

An issue to capture everything related to IO that needs or could need improvements.

• Let the MemSink communicate with the StreamingSource before actually starting the transfer. This enables the following:
  • The sink could be able to return an error, saying that it's not compatible with the source.
  • The sink and/or source could prepare stuff already then.
  • The sink could indicate a preferred type for specific property. E.g. the sink could say that it prefers f64 positions; which could tell the source to parse ASCII floats as f64 directly. But this is crazy fancy stuff. Not important.

Tracking issue: returning iterators from trait methods

Returning iterators from trait methods is difficult as (a) usually every implementing type has a different iterator type and (b) this iterator type borrows from the collection. This is currently not (easily) expressible in Rust. The situation will be vastly improved by GATs. impl Trait for trait methods would make it even easier.

Until those features are implemented, we have to work around the problem. This is done in a number of different ways:

• Mesh::{faces, vertices, edges}: here, there exists only one iterator type which uses the next_*_handle and last_*_handle methods of the Mesh trait. This means we have extracted the iterator logic into two "normal" functions in the trait. This only works because the iterator state is the same for all implementing types: a handle as the current "position" is sufficient. So this workaround doesn't work for situations where different implementors need different iterator state or the iterator logic is more complex.

• Adjacency queries of meshes: here, a funky type system trick was used to work around the lack of GATs. It produces a bunch of verbose filler code, but it works. Each implementor has its own type.

• PropStore: here, dynamic dispatch is used for now. Currently there is no urgent need to improve the speed of this iteration. This workaround could probably be replaced by the one of the adjacency queries, but it's not worth it yet.

Use memory mapped files to improve IO performance

On platforms that support mmap, we should probably just mmap files and read from there. However, this is only useful when we use the slice directly so that the ParseBuf overhead is completely gone.

Fix intra-doc links

Intra-doc links are still somewhat experimental and break from time to time. Breakage is especially bad in the fev crate where things from other crates are reexported.

Extend core mesh API (`Mesh`, `MeshMut`, ...)

• Mutating methods
  • add_face/add_triangle
  • add_vertex
  • remove_face
  • remove_isolated_vertex
  • remove_vertex_with_adjacent_faces (and maybe find a shorter name): this can have a default implementation. This should probably be bounded by Self: FullAdj, right?
  • remove_all_faces/remove_all_vertices: improve documentation and fix semantics, especially regarding reuse of handles
  • split_face (1-to-n split)
  • flip_edge
  • split_edge_with_faces (although: maybe rename)
  • collapse_edge
  • Mutable iterator (this requires a bit more thinking, also about the exact semantics of Ref)
• Non-mutating
  • num_*
  • contains_*
  • valence_of_*?
  • is_manifold_vertex?

Add more known properties to IO traits

We (might) want to know about these useful properties:

• Vertex position
• Vertex normal
• Vertex color
• Vertex texcoord (2D & 3D)
• Face normal
• Face color
• Face texcoord (2D & 3D)
• Face texindex
• Edge color
• Arbitrary, named properties

To add a known property, changes in several places are necessary:

• MemSink trait
• MemSource trait
• derive(MemSink) code
• derive(MemSource) code
• io::PropKind
• Update sources that could provide those new infos
• Write new tests

Blockers:

• Figuring out texture coordinates

Try replacing `next_handle_from` based iteration

Iterating over all vertices/faces/edges of a mesh is currently implemented via next_vertex_handle_from and last_vertex_handle. This was originally done to work around the lack of GATs. Now we have GATs and could solve this properly... except for vertex_handles_mut: an iterator that iterates over vertex handles but also gives mutable access to the underlying mesh. It's not possible to easily implement it due to borrowing the vertices.iter() immutable for the handles, but also the whole mesh. So it is necessary to pull out the iteration logic instead of using the provided one of the relevant DenseMap.

I'm not yet sure how to best solve this. Maybe use the GAT solution for element_handles() and elements(), but still use the manual iteration for the mut iterator. But that should probably be hidden as well, i.e. have a IterMut<'s> type in the trait and remove the next_handle_from functions from the Mesh trait.

Initial experimentation roadmap

Unsorted, random things to do:

Week 2018-12-03: "Finish" sink/source system

• Finish convert tool for now (if that works, the sink/source system is probably fine)
• Read into a mesh and PropMaps where we can decide what kinds of properties we want (e.g. read this into a mesh and position prop map).
• PLY Source impl
• Adjust and add tests
• Adjust and add documentation

Week 2018-11-26

• "Finish" sink/source system
• Sink:
  • Read into a mesh and PropMaps where we can decide what kinds of properties we want (e.g. read this into a mesh and position prop map) -> postponed
  • STL file → No! Files cannot implement Sink due to source-determined ordering of add-opertions
• Source:
  • Implement map_vertex and map_face
• Evtl PLY Reader
• Evtl PLY Sink/Source impl -> postponed
• Adjust and add tests -> postponed
• Adjust and add documention -> postponed

Later

• Implement HEM
• Think about mesh traits

Think about IO errors

Currently, every file format has its own error type. Those error types are pretty similar though. It might be better to create one io::Error type instead to simplify API and duplicate code.

Decide on naming scheme for main IO types and traits

So the high level interface for everything IO is defined by StreamingSink and StreamingSource. The question is how to call the types implementing those traits.

For StreamingSource both are called Reader right now which sounds OK to me. But for the StreamingSink, it's stl::Sink while stl::Writer offers a more raw and non-abstract interface. PLY doesn't have such an implementation yet, but ply::Writer already exists and also offers the more raw interface.

Furthermore, there are two traits related to these raw writers, currently called MeshWriter and IntoMeshWriter. At least MeshWriter needs to continue to exist, but should probably be renamed. Maybe just RawWriter?

Wishlist for `#[derive(MemSink, MemSource)]`

Wishlist for #[derive(MemSink)]:

• Global cast mode instead of each field
• Name a field mesh (or so) but explicitly opt out of it being used (does not apply anymore)
• Modify finish() behavior: what is required and so on
• Specify cast mode without specifying what it's for: #[lox(cast = "lossy")]
• Specify how to deal with the alpha channel for colors (ignore additional, require one, ..)

Wishlist for #[derive(MemSource)]:

• ...

Tracking issue: GAT improvements

This issue collects all major parts of the library that can be improved with generic associated types. This library won't be released as 1.x before GATs have landed and these improvements have been implemented, as they a central to a fast and convenient API.

• Element iterators: Explicit{Edge, Face, Vertex}::{edges, faces, vertices}() currently return Box<Iterator>. Instead, those traits should have a GAT {Edge, Face, Vertex}Iter<'s> instead which is returned by the methods. -> #32
• PropMap: the trait currently uses a hack from the boo module. -> done
• IntoMeshWriter could also move its parameters to the function and an GAT

fev-map documentation

fev-map needs better documentation. An incomplete list of things we need to do:

• Mentions the aliases everywhere

Reintroduce IO functionality

As explained in the docs, IO code was thrown out to reduce the scope of the initial release. Of course, IO is important for many use cases, so it should be added back. The code lives in old_code/ and was fully working (and fast!), but it needs quite a bit of adjustments still to:

• Make it compile on stable
• Improve/polish the API
• Make it maintainable

Here is an incomplete and unsorted list of things that need to be addressed:

• Use GATs where possible (IntoMeshWriter?)
• Adjust to make it compile again with the recent code changes.
• Get rid of duplication in set_vertex_positions, set_vertex_colors, ...
  • I think that's the main thing I'm currently concerned about. It results on tons of code, making it very unmaintainable. It would be great if I could replace all those props methods with a single generic method. set_prop::<VertexPositions>() or sth like that.
• Take a look at all the API again and see what can be simplified or improved
• Adjust derives to have fewer special cases and be easier to maintain. The derive code is biiig and a bit of a mess.
• Think about "fat meshes" again, maybe use a different name.
• ...

Implement `Stream{Source, Sink}` for `T: Mem{Source,Sink}` and add super trait bound

A Mem{Source, Sink} is worth more than a Stream{SourceSink}, as in: can always do more. It would be really useful to:

• Add the : Stream* super trait bound to Mem* traits
• Add a default implementation of Stream* for all types T: Mem* (this implementation would likely be similar to PLYs impl: many function pointers)

This would make it possible to easily transfer data from one MemSource to a MemSink.

Reintroduce features that were left out from the initial release

I should do that one step at a time, to not get overwhelmed with work again. Some things are certainly more important than others.

• Core IO: traits, loading from PLY/STL, derives. Important I think. #33
• Shapes: This requires IO and is very little code on top of it, so it should be easy to introduce that.
• Fuzzing tests: these are for IO. Might want to reintroduce them with IO?
• Face delegate mesh: I'm not even sure what that is, it was commented out a good while ago. I think it might be a new data structure I came up with. Not sure if it's any useful, but might be worth looking into.
• Benchmarks: Would be very useful to make them compile again and have a way of quickly extracting their data.
• Fat any mesh: I think only useful for loxi, so leave it for now.
• loxi: useful CLI tool for working with meshes. No high priority.

Deny missing docs in CI when merging into master

Later, when the project is more complete and not breaking all the time, missing docs should lead to a CI failure when merging into master.

PLY performance improvements

PLY reading and writing speed is not bad, but could be improved a lot. The difficult part is that PLY has a dynamic type system, so to say: we have to read the header to know what types to expect. This leads to a lot of complexity everywhere.

I have two main ideas how to improve PLY speed.

(a) RawSource has to be changed. Currently it is forced to write to the "serializer" once for each property. That means we cannot do any optimizations such as "have a temporary buffer with all vertex properties and write to the writer only once per vertex". This is bad. So this certainly needs to be improved.

(b) And here is where it gets funny: write a JIT codegen. The optimal assembly code to read "normal" binary PLY files is actually super simple. It's just a memcopy, mostly. However, due to the fact that the data layout is dynamic, the Rust compiler can't do any optimizations in that regard. So the idea is to generate x86-64 machine code after reading the PLY header. This code is then optimized for the PLY data layout. I bet this could increase raw read performance at least five-fold if not a lot more. But it's a lot of work and unsafe code and platform-dependent stuff and and and. Not sure if worth it -- it would be a super interesting project though.

Niche optimization in HalfEdgeMesh

Just looking through the HalfEdge implementation, it looks as though it should be possible to implement a niche optimization

lox/src/core/half_edge/mod.rs

Line 194 in 80c0e20

half_edges: DenseMap<HalfEdgeHandle, HalfEdge<C>>,

with HalfEdge defined as

lox/src/core/half_edge/mod.rs

Line 101 in 80c0e20

struct HalfEdgeHandle(hsize);

If that were switched from using DenseMap which uses a StableVec internally to a map using InlineStableVec which would use Option, then define HalfEdge using the NonZero variants then adding/subtracting on creation indexing.

It looks like trying it out would be a bit involved but overall doesn't really require any major refactors that would impact other parts of the code base, with the main thing being the alternative to DenseMap and NonZero Handle implementation. Was curious if you had tried that, or if feel like it's worth trying.

Edit:
What would be really nice here if there was a NonMax* as mentioned in rust-lang/rust#45842
That would allow for just checking when the handle is created rather than having to do arithmetic whenever it is used.
unfortunately afaik nothing in std which implements niches for _::MAX.
There is this crate though that emulates it https://crates.io/crates/nonmax but it is just a wrapper around NonZero*.

Add more useful basic algorithms

The algo module is sadly empty right now. It should be filled with lots of standard algorithms, maybe just the easy ones for now. Implementing a sqrt(3) takes some time, but there surely is a lot of low hanging fruit that's quick to implement and useful.

• Visitors: BFS, DFS
• ...

Casting between numerical types

This is not trivial. It's questionable when and how we cast between numerical types. Going the strict path (think std::convert::{Into, From}) probably leads to an annoying API. Going the relaxed path and just casting everything when necessary, regardless of precision loss, might lead to surprising bad behavior.

We could let the user decide, but this could very well add trait bounds everywhere, making the API less easy to read. Here is a possible design for a conversion trait. It requires specialization to be generic, but works without it when restricting to primitives.