Export shape with multiple disjoint meshes

[zeeyang]

Describe the bug
When exporting a shape with multiple bodies, e.g. two boxes: curv -o gltf -x row[box, box]. Both x3d and gltf would export all polygons into a single mesh.

I suppose the distance function would have no means of detecting disjoint bodies. Is it possible to see if shape has multiple bodies using the voxel grid, or with OpenVDB volumeToMesh?

Curv Program
curv -o gltf -x row[box, box]

Expected behavior
A mesh for each body.

Additiona context
This is just a nice to have. I'm just curious about voxels.

[doug-moen]

You want to separate a shape into 'multiple bodies', and you assume that each 'body' corresponds to a single mesh. This isn't quite true.

I will define a Mesh as a connected set of triangles that form a single watertight 3D surface that encloses a single 3D shape.

Consider a hollow sphere, such as sphere >> shell .5. This contains a single spherical void, invisible from the outside. It will be represented by two distinct Meshes, one for the outer surface, and one for the inner surface. I will use the term Bulk to denote a single contiguous 3D shape. A Bulk has one Mesh for the exterior surface, and one additional Mesh for each interior void.

A Model consists of one or more Bulks. The following image is of a geared model with moving parts, consisting of 8 separate bulks. But the model cannot be disassembled, it has to be printed as a single unit:

Another case where a model has multiple Bulks is multicolour FDM printing, where the 3D printer has the ability to switch between different filaments while printing. Each contiguous volume of a single colour or material is represented by a separate Bulk. In this case, you need to associate a Material ID with each Bulk.

Some 3D printing file formats have the ability to contain multiple Models in a single file. So we have a 3 level hierarchy: a Bulk contains multiple Meshes, a Model contains multiple Bulks (with optional material IDs), and a file contains multiple Models.

The only reliable way to decompose a shape into its component Meshes is to render the shape as a triangle set, then traverse the triangle set to identify the separate Meshes. But this probably doesn't solve your problem, because you are probably interested in one of the higher level elements that I mentioned, such as a Bulk or a Model. To fully implement the 3 level hierarchy that I described requires adding additional information to the Curv program.

Which file formats support this 3 level hierarchy? That would be 3MF (https://3mf.io/).

Finally, you said "I'm just curious about voxels.". This could refer to 2 different things. In Minecraft, a shape is represented as a collection of tiny cubes, called voxels. But in my notes for Curv, I most frequently use "voxel grid" to refer to a discretely sampled signed distance field: a 3 dimensional array where each element is the signed distance from that grid position to the surface of the shape. Trilinear interpolation is used to look up the signed distance for an arbitrary point [x,y,z] using the voxel grid. It's not easy to use a signed distance field (either discrete or continuous) to separate a shape into a set of disconnected components. This would be easier with a Minecraft voxel grid.

[zeeyang]

Thanks for the insightful feedback @doug-moen. Yes, my intention was to find unconnected bulks in a model.

My original thought was to traverse the voxel grid to find bulks: group each cluster of distance >=0 as a bulk. But consider this program:

let
    redbox = box >> colour red;
    bluebox = box >> move [0.5, 0.5] >> colour blue;
    // boxes = union [bluebox, redbox];
    boxes = union [redbox, bluebox];
    pattern = gyroid >> shell .5 >> lipschitz 1.5;

in
intersection [boxes, pattern]

You would want the blue and red as two separate bulks for 3d printing. Maybe curv needs a concept of material ID or part ID to correctly separate the bulks in this case. This could be a useful concept for the viewer too - toggle on/off part of a shape to help debugging.

[doug-moen]

Maybe curv needs a concept of material ID or part ID to correctly separate the bulks in this case.

I have several ideas on how to implement this.

1. One idea is to add a part operator to Curv, as in this proposal: color(), material() and part() [$325] openscad/openscad#1608.
   This makes sense in OpenSCAD, but I have given no thought to how it would work in Curv, and how rendering would work.
2. I have also considered adding a 'part' or 'material' function to the definition of a shape, where this is a continuous function that maps arbitrary [x,y,z] to a part or material. This approach is more appropriate for Shapeway's Stratasys J750 3D printer, which is a voxel printer that can vary colour and material properties at each voxel. This idea also works for a computer graphics application of Curv where you want to render a realistic looking 3D shape using PBR (physically based rendering), where it would support continuously variable material properties.

So then the question becomes, how do you render these shapes, and how do you convert them to triangle meshes? One thought is that the Dual Contouring meshing algorithm has direct support for multi-material meshing, whereas the OpenVDB meshing algorithm I'm using right now does not. https://people.engr.tamu.edu/schaefer/research/dualcontour.pdf

I don't have access to a multi-material FDM printer, so I haven't really developed these ideas further. More development is required.

[zeeyang]

The "part" function proposal for scad is what I was thinking. Instead of overriding parent part name, maybe it can be preserved to form an array for hierarchical parts.

let
    redbox = box >> colour red >> part "red";
    bluebox = box >> move [0.5, 0.5] >> colour blue >> part "blue";
    boxes = union [redbox, bluebox];
    pattern = gyroid >> shell .5 >> lipschitz 1.5;
in
intersection [boxes, pattern] >> part "widget"

In Compiled_Shape, part would be a discrete function. e.g. input [x, y, z] and returns ["widget", "red"]. Exporter can use the part array to construct hierarchical model for 3MF, GLTF. The viewer can toggle parts on/off. @doug-moen if you are comfortable with the syntax change maybe I can take a swing at the implementation.

[doug-moen]

This strikes me as a very "researchy" project, requiring iteration over multiple designs.

In Compiled_Shape, part would be a discrete function. e.g. input [x, y, z] and returns ["widget", "red"]

Yes, but how do you export a mesh using this representation?

One of my goals for mesh export is to support sharp feature detection. A cube exports as a cube (the edges and corners are not rounded off). The current meshing algorithm (from OpenVDB) has the benefit of creating defect-free meshes, and the output looks reasonable for a wide range of models. But it doesn't do sharp feature detection, which is something I want, and which libfive supports. The problem with sharp feature detection is that it can produce defective meshes, in all the algorithms I've surveyed, which means you may need to repair the mesh before importing it into OpenSCAD, and you may also need mesh repair before 3D printing, depending on the slicer and the nature of the defects. So that means I want to provide a choice of meshing algorithms: one is defect free, one does edge detection. The obvious next step is to add support for the libfive meshing algorithm. I've also considered the TMC meshing algorithm, which generates all quads (no triangles), and is defect free. TMC occasionally screws up edges and corners worse than OpenVDB, but the problem is avoided if you mesh at a high enough resolution. The main benefit of TMC is to satisfy the requirements of 3D artists who use Z-Brush for editing meshes: this tool works better if the model is all quads (or so I have been told). TMC is also interesting because it can be executed on a GPU, in which case it is very fast. TMC has a CUDA implementation, which I've fantasized about translating into Curv after I've done the WebGPU port and added support for GPU compute pipelines.

So imagine a future where Curv supports OpenVDB, libfive and TMC as the 3 meshing algorithms (defaulting to OpenVDB).

Here's my point: However part is implemented, the shape representation has to be compatible with existing meshing algorithms, which usually do not have native multi-material support. The obvious approach is to have a loop that constructs a different Compiled_Shape for each part, and meshes each part independently. So that means we need to generate a signed distance field for a single part, from the shape representation. Maybe we can implement our own multi-material meshing algorithm that does better than this (faster, and generates high quality parts that are guaranteed to fit together exactly), but a custom mesher would have its own strengths and weaknesses, and could not be used as the only meshing algorithm.

So what is the representation of a shape? The first idea that comes into my head is that a shape contains a collection of [distance function, bounding box] pairs, one for each part. At first glance, this would require the entire shape library to be rewritten, and would add significant complication to every operation that takes shapes as arguments. Because you'd have to add boilerplate to all of these operations to iterate over the part tree. With a sufficiently clever design, it may be possible to abstract away the boilerplate.

[zeeyang]

My original idea was to start with the distance voxel grid, segment it into multiple voxel grids using part function, and step through the array replacing bulk edges with 0 to form the isosurface. That's a half baked idea and probably wouldn't work at all with OpenVDB volumeToMesh. I realized under estimated this by a mile.

[zeeyang]

I suppose you can also define individual parts in its own curv file. Use include file to stitch them together. Then use a script to export them individually.

[doug-moen]

My original idea was to start with the distance voxel grid, segment it into multiple voxel grids using part function, and step through the array replacing bulk edges with 0 to form the isosurface.

A signed distance field needs to be a continuous function, and this idea wouldn't create a continuous function. However, a minor variant of your idea creates a minecraft-style voxel grid, which each grid element contains 1 for elements inside a specified bulk, and 0 for elements outside. There are techniques for meshing a minecraft voxel grid, although I don't really know anything about them. My intuition says that a minecraft voxel grid contains less information than a continuous signed distance function, so in theory the quality of the resulting mesh should be worse than a mesh constructed from a signed distance field. In other words, your data structure requires a new meshing algorithm different from the SDF meshing algorithms I've been investigating, and the output quality may be worse.

Looking at the OpenVDB documentation, the two voxel grid types are called "level set" (meaning SDF) and "fog volume" (a generalization of minecraft voxel grids where voxel values are density values between 0 and 1). It appears that volumeToMesh works on both types of grids but uses a different algorithm for the two cases.

[doug-moen]

I suppose you can also define individual parts in its own curv file. Use include file to stitch them together. Then use a script to export them individually.

We can start with this idea and automate it a bit. Define a "multipart shape" as a shape value with an additional field called parts. The parts field contains a record of name/shape pairs. If you view a multipart shape in the preview window, then you see the assembled shape. But when you export a shape to a mesh, if the -Oparts option is specified, then each shape in the parts record is exported into a separate file, using the field names to construct the file names (an extension is added).

Then you can write some helper functions to make it easier to construct a multipart shape value.

[lf94]

I kind of see no reason for this. Curv supports importing files, and so you can easily have a makefile or build process which can generate either an assembly, or the individual parts. For other Code CADs my project structure of src/{parts/, assembly.file} has worked well as long as the Code CAD provides an include directive.