Support for n-gon mesh output?

[virtualritz]

I would like to integrate this crate with a Rust-based creative coding environment for non-realtime 3D rendering.

Most offline renderers can deal dandy with n-gon meshes and even render them as subdivision surfaces (see my polyhedron-ops crate for some examples). Reading this article I learned the dual contouring algorithm seems to generate meshes that are well suited, as-is (mostly quads).

I.e. the current Mesh struct could be renamed to TriangleMesh. The new Mesh struct would have a faces that is a Vec<Vec<usize>> so that each face can have an arbitrary arity.

[hmeyer]

Thanks for you interest in this library! And thanks for your proposal. The requested change should be quite easy, b/c as you mentioned the main primitive of DC is a quad. Note though, that there is no guarantee that the quad is planar - can you confirm this is still useful?

In the case of Manifold DC, this quad can sometimes collapse to a Triangle (or a line or point) - so we'd need support quads and triangles.

Face = Vec would be simplest to implement. Another option would be: Face = SmallVec<[usize; 4]> (using https://crates.io/crates/smallvec or similar).

I'd welcome a PR in that regard - let me know if you need any help!

[hmeyer]

Also: I took a look at https://crates.io/crates/polyhedron-ops - the images are beautiful! Do you also support Catalan solids? I've always wanted to add basic solids (Platonic, Catalan, Archimedean) to https://github.com/hmeyer/truescad - so maybe your crate is the way to go. Although I wasn't able to get https://crates.io/crates/polyhedron-ops up and running without registering and downloading 3delight.com - is this strictly required?

[virtualritz]

Strictly quads: not required. The mesh can be a mix of faces of any arity.

Planarity: not required.

3Delight: required only for the example, I think. The crate has a feature flag, nsi, that is off by default and will pull the nsi dependency in which in term depends on 3Delight for now.

I will expose the download_lib3delight feature flag from nsi to polyhedron-ops. That way you can use it w/o registering.

I will make nsi a flag for the polyhedron-ops/playground example. Then that will work w/o 3Delight too.

[virtualritz]

I wasn't aware of Truescad.

I will add Catalan an Archimedian solids, prism and anti-prisms to polyhedron-ops at some stage. Open to PRs. :)

If you like to play with code-based geometry as in OpenSCAD Languageo or Lua via Truescad: I just added support for rendering with 3Delight into a Jupyter notebook running on a Rust kernel via evcxr. Still needs some polishing but will be in nsi soon.

[virtualritz]

Actually, Catalan & Archimedian solids can easily be created using Platonic solids and operators in this crate.

I just published a new version of polyheron-ops which should work w/o 3Delight (but you won't be able to make those pretty images then).

[virtualritz]

If I add this, is it ok to have tessellate() always return a Mesh and add a method, triangulate(), that returns a TriangleMesh?

The option is using generics is quite involved because of how Mesh::faces differs. I.e. being either a Vec<Vec<usize>> or a Vec[usize; 3].

[hmeyer]

There is currently no way the chosen algorithm can output a 5 or higher-gon. So I think Face = SmallVec<[usize; 4]> (using https://crates.io/crates/smallvec or similar) is the way to go. Adding triangulate() would a good solution to make code work that depends on TriangleMeshes.

[virtualritz]

Wait, the code in crate suggests a the mesh is a mix of triangles and quads when the contouring is finished. I do not want to represent triangles as degenerate quads.

[hmeyer]

SmallVec<[usize; 4]> is almost the same as Vec, except length can be at most 4 and it doesn't require any heap allocations. So we could use this to represent Triangles and Quads in a clean way.

[virtualritz]

Ok, I need to understand one thing: does the algorithm initially generate only quads it generate a mix of quads and triangles? The code at the end of compute_quad() suggests to me that meshes are a mix, initially.

This then means that to (finally) output a quad mesh w/o degenerate triangles (where two vertices of a face share a point) requires additional checks at runtime.

So I'd rather have two flat Vecs instead. One face_arities: Vec<usize> which has the number of vertices for each face (i.e. it will be a mix of 3s and 4s for the quad+tri mesh and only 3s for the tri mesh case). Memory use is the same for a tri mesh because each face in your proposal carries an unused usize which will exactly the memory used by face_arities. The current faces would be a Vec<usize> instead (i.e. flat) and looked up by a running index from summing up face_arities. That makes looking up face n slower but if we assume what users want is to prepare the mesh for display/rendering this shouldn't matter because then you need to build flat buffers which means iterating which is additions only in the memory layout.

And they can be allocated once each, with_capacity().

[hmeyer]

Yes, faces are a mix of Tris and Quads. I wouldn't know of a striaght forward way to convert this mix to a quad mesh w/o degenerate triangles. E.g. consider converting a tetrahedron....

Two flat vectors would work - but indexing would be a pain. Do you dislike Vec<SmallVec<[usize; 4]>> b/c of the additional wasted usize for each Triangle?

[virtualritz]

While random indexing is a pain I wonder who needs random indexing? The crate doesn't seem to do anything with Mesh::faces besides adding faces to it.

And once you want to export the mesh to e.g. OBJ or display it you need to convert it into a GPU/renderer-compatible buffer format which means iterating over the whole thing which, as I said, is just additions when you use the double index buffer. Read: painless & fast.

But actually, most GPU/realtime rendering crates I used use a Vec<usize> flat buffer to describe the topology. I.e. if we used the two flat buffers I suggested, after a triangulate(), a user can just pass the faces buffer directly to the GPU renderer, w/o any modifications, (assuming they want to just render it smooth shaded).

When writing the geometry out to an OBJ or the like you also need to iterate the whole mesh – i.e. indexing is not a pain.

I wouldn't know of a striaght forward way to convert this mix to a quad mesh w/o degenerate triangles. E.g. consider converting a tetrahedron....

I think there is a misunderstanding. The class of (offline) renderers I'm mainly targeting –, Blender's Cycles, RenderMan, VRay, 3Delight, can deal with meshes that are a mix of faces of any arity in a single mesh (and, as an aside, including holes). They do not have a concept of triangle mesh or quad mesh at all. All they know is a mesh where each face's description to the renderer includes the number of vertices it has.

I.e. a quad mesh makes no sense if some of those quads are degenerate triangles. They should be filtered out and turned into real triangles because some of those renderers won't do that by themselves and that can lead to all sorts of funky shit during shading (zero derivatives for texture filtering e.g).

I do not dislike the wasted space. I just do not see the point. If the crate doesn't need to index (unless I miss something) and the users of the crate are unlikely to index randomly, why satisfy this constraint?

In any case, you are the author so it's your decision.

I will provide two adapter functions, behind a feature gate, to get a mixed (tris & quads) mesh from Mesh.

One is to e.g. use this with polyhedron-ops which requires exactly the Vec<Vec<usize>> buffer and one for aforementioned renderers which eat exactly the two flat buffers I described in the previous reply. One of them could be zero cost if we use the double flat buffer.

[virtualritz]

Disregard my last reply. I deleted it. I missed the outside Vec around SmallVec in your reply. :)

[virtualritz]

So, have a look here. I will add some example(s) tomorrow and create a PR then.

[hmeyer]

Cool. Overall this looks good to me. I added some comments. Also I think the obj & pops export should go into a separate crate (similar to https://crates.io/crates/stl_io). Looking forward to your PR.

[virtualritz]

Also I think the obj & pops export should go into a separate crate [...]

You can't define a trait like From outside a crate where neither type/struct the trait is implemented for is defined. I.e. I can add this to either polyhedron-ops or tessellation. Another crate would mean it's not a core trait anymore but a utility function. That being said, I'm happy to add it to polyhedron-ops instead.

[virtualritz]

OBJ export is a few lines of code and very handy for testing. I.e. it doesn't make the crate slower to download and/or to build (obj feature is off by default). I suggest to leave it in for now and retire it, once there is support for writing out OBJs that do not consist entirely of triangles, in some crate. All OBJ crates are import-only or they only support triangle meshes.

In the meantime I will ask Will, the author of tobj to add support for writing too. His crate is the only OBJ crate that supports loading non-triangle meshes, afaik.

[hmeyer]

sorry for the late reply - sounds like a plan