Triangulation of SDFs

[Sébastien Pierre]

I was reading this https://github.com/doug-moen/curv/blob/99c2c84d9f5ee5c7e72c547523c96b7888977202/ideas/geometry/Voronoi and this reminded of the main challenge that I was thinking about in my own SDF-related explorations: the identification of feature points. It's not super clear for me, but here's what I had in mind so far:

- Marching cubes typically don't work very well with sharp (let's say the corner of a rotated cube) and require a uniform sampling rate (see http://mikolalysenko.github.io/Isosurface/ and http://tdhooper.github.io/glsl-marching-cubes/). However, there are some adaptive variants, such as dual contouring http://faculty.cs.tamu.edu/schaefer/research/dualcontour.pdf that seem to give good results.

- Libfive keeps the symbolic representation of the SDF in its math kernel and seems to be able to compute the derivative for at least a subset of the expressions (see https://github.com/libfive/libfive/blob/master/libfive/src/eval/eval_deriv.cpp). I assume they leverage this information for the meshing, although I did not investigate further.

My intuition from that is the following:

- If we're able to calculate the first, and even better the second derivative of an SDF, we have all the information we need for efficient meshing.

- A discontinuity or a high value in the first derivative will give us the sharp corners/ruptures in the curvature.

- The second order derivative will tell us when to locally increase the sampling rate (any non-null value would indicate a change in the curvature)

What I find very appealing in the idea of GVD, although I have no idea how that would work in practice, is that it has the potential to encode an approximation of the SDF (like polynomials can approximate arbitrary functions) in something that has straightforward properties and predictable computational cost. I wonder if there is a mathematical tool that would support that.

[Doug Moen]

Marching cubes is what I currently use, and yes it's terrible. It's just a placeholder until I get around to doing better. Although, the current mesher produces high quality meshes, which are watertight, 2-manifold, with no self intersections, degenerate triangles, or flipped triangles. Most algorithms that do edge detection, eg Dual Contouring, produce defective meshes, which is a problem for tools that consume meshes.

Libfive now has a mesher based on:

"Isosurfaces Over Simplicial Partitions of Multiresolution Grids"

(2010) Josiah Manson and Scott Schaefer

http://faculty.cs.tamu.edu/schaefer/research/iso_simplicial.pdf

It looks like an awesome algorithm. There is nothing inherent in this algorithm that requires Libfive's symbolic representation of the SDF. AFAIK It can work with just a Curv distance function.

LIbfive's symbolic distance field representation is designed to improve rendering performance. I don't think it's required to create a good mesh. Curv uses the GPU to increase rendering performance, which leads to rather different data structures and algorithms, including the compute shader requirement that I mentioned in another post.

Integrating Libfive's new mesher into Curv is on my TODO list. Good meshing algorithms are hard to write, and Matt Keeter has a lot more experience in this area than I do, so I'm happy to reuse his work.

That set of notes about GVD is rather speculative. If you want to see better quality research on data structures for representing SDFs, in the context of meshing, take a look at Dual Marching Cubes, and also the paper I cited above (Isosurfaces ...).

I'm still interested in generalized data structures for signed distance fields, but my interest has moved on to data structures for the GPU, to support fast rendering of complex objects that are not well supported by the current pure functional representation.

Doug Moen.

--

You received this message because you are subscribed to the Google Groups "Curv" group.

To unsubscribe from this group and stop receiving emails from it, send an email to curv+uns...@googlegroups.com.

To post to this group, send email to cu...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/curv/343faf99-7fce-4a27-a6f2-aeed08a99020%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Sébastien Pierre]

Thanks for the reference, I hadn't come across this article before. Good stuff! Just out of curiosity, which types of objects are not well supported by the F-Rep currently used by curv?

-- Sébastien

[Doug Moen]

On Wed, Jan 2, 2019, at 7:40 AM, Sébastien Pierre wrote:

Thanks for the reference, I hadn't come across this article before. Good stuff! Just out of curiosity, which types of objects are not well supported by the F-Rep currently used by curv?

The two use cases I want to address first are:

* large polyhedra: efficient import and rendering of mesh files (eg, STL)

* large unions (unions with a large number of elements)

I would also like to be able to render "algebraic" distance fields. For example,

// http://mathworld.wolfram.com/KleinBottle.html

make_shape {

    dist(x,y,z,t) =

        let p = [x,y,z];

            a = dot(p,p);

            b = 2*y - 1;

            d = (a+b)*((a-b)^2 - 8*z^2) + 16*x*z*(a-b);

        in d;

    bbox = [[-3,-3,-3.2],[3,3,3.2]]; // very approximate

    is_3d = true;

}

This can be exported to a mesh, but it cannot be viewed using sphere-tracing, because the distance function is not Lipschitz(1).

[Sébastien Pierre]

I'm curious to see how you'll attack these problems, do you have anything in the ideas folder regarding that? Otherwise, please share on the group, I'm interested!

-- Sébastien

[Doug Moen]

On Thu, Jan 3, 2019, at 6:50 AM, Sébastien Pierre wrote:

I'm curious to see how you'll attack these problems, do you have anything in the ideas folder regarding that? Otherwise, please share on the group, I'm interested!

1. Large polyhedra: efficient import and rendering of mesh files (eg, STL)

Method 1, perform an offline conversion of a mesh file to a voxel grid (a 3D array of distance values, aka a discrete signed distance field). Then import the voxel grid as a shape. This is the best approach for huge meshes where the triangles approximate a curved surface. Modern GPUs have hardware support for voxel grids (ie, 3D textures), so it's relatively easy to implement; rendering and distance field operations can be reasonably efficient. The voxel grid is an approximation of the mesh.

See also: github.com/xx3000/mTec, which implements this using a lot of clever optimizations (which require compute shaders).

Method 2, convert the mesh into a signed distance field by constructing a BVH (bounding volume hierarchy) for the triangles in the mesh. With this method, we preserve each triangular face in the resulting SDF, but it probably doesn't scale as well as the previous method. But good if your mesh is an exact representation of a polyhedral model, rather than an approximation. I think that the BVH data structure that I need here is basically the same as the "acceleration structures" used for ray tracing meshes, so I believe I should be able to leverage existing ray-tracing code.

2. Large unions.

I have two main ideas:

* I could assemble the bounding boxes of all of the shapes being unioned into a BVH (see above).

* The mTec project (see above) has a set of clever optimizations for large unions.

3. Ray-casting non-Lipschitz implicit surfaces

The "grid-tracer" algorithm: -Otracer=grid (default sphere).

glsl-function-grapher by Michael Firmin on github

another idea:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.417.5616&rep=rep1&type=pdf

Real-Time Ray-Tracing of Implicit Surfaces on the GPU

[Torleif Ceder]

I fond this link in my bookmarks 

A small and old list of algorithms, 

Missing from the list is for example Marching Tetraeder and  Dual Marching Tetraeder, both with some guarantees of producing 2-manifold.

Loads to pick from for sure.
Harder to find is one that does all of:  

- Mandatory, 2-manifold. and non self intersecting,
- Preferably, preserve sharp features and adaptive resolution ,
- And if possible. tolerant of lower quality distance fields, and nice edge flow.

from: https://swiftcoder.wordpress.com/planets/isosurface-extraction/

Marching Cubes

This is the original cubic method. Desipte its age, the technique is still very much in use, but if you are interested in using marching cubes, I would suggest skipping straight to a more modern derivative.

Surface Nets

This is mentioned purely as a historical note – I believe this to be the earliest of the dual methods.

Extended Marching Cubes

This seems to be the first technique to combine cubic and dual methods.

Dual Contouring of Hermite Data

This is a newer (and generally better) combination of cubic and dual methods, plus generalistaion to octrees.

Dual Marching Cubes: Primal Contouring of Dual Grids

This is an extension of Dual Contouring to better utilise adaptive octrees.

Manifold Dual Contouring

An extension to Dual Contouring which better preserves the manifold nature of the surface.

Isosurfaces Over Simplicial Partitions of Multiresolution Grids

Improves upon Dual Marching Cubes to eliminate self-intersecting triangles in the result.

Cubical Marching Squares

An alternate approach which works on the faces of the cube rather than its content. Unique among the newer techniques, a reference implementation is provided.

Adaptive Skeleton Climbing

An entirely different approach, which operates on a large chunk of voxels at one time, generating much larger polygons as a result.

The Transvoxel™ Algorithm

An adaptation of Marching Cubes that extends the tables/lookup to prevent cracks at the boundaries between neighboring chunks that differ in level-of-detail. Used extensively in the C4 Engine’s terrain implementation.

[Doug Moen]

Harder to find is one that does all of:  

- Mandatory, 2-manifold. and non self intersecting,
- Preferably, preserve sharp features and adaptive resolution ,
- And if possible. tolerant of lower quality distance fields, and nice edge flow.

"Isosurfaces Over Simplicial Partitions of Multiresolution Grids"

http://faculty.cs.tamu.edu/schaefer/research/iso_simplicial.pdf

makes the following claims:

* 2-manifold

* non self intersecting

* reconstructs sharp features

* reconstructs *thin* features smaller than the sampling grid resolution

* adaptive resolution

It's the only algorithm I've been able to find with all these features.

What does "tolerant of lower quality distance fields" mean? The Isosurfaces... paper says "we only assume that the function is piecewise smooth and does not have to be a distance function". Which is reasonable for any algorithm that does edge detection. You can't use this method on fractals, which are not piecewise smooth, but I'm planning a different approach for fractals anyway.

I can't comment about "nice edge flow", since I haven't tested the algorithm yet. But since it has been added to libfive, I assume that the algorithm is a good one.

Cubical Marching Squares

An alternate approach which works on the faces of the cube rather than its content. Unique among the newer techniques, a reference implementation is provided.

Correction: this is a borderline fraudulent method. Nobody has been able to implement this algorithm in a way that matches the claims in the paper, including the original authors. The so called reference implementation from the original authors doesn't work correctly. The authors published before they had a working implementation, assuming they could fix the bugs later. Afterwards, they tried to fix the bugs, couldn't, and gave up. I also read a masters thesis by somebody who independently tried and failed to implement the algorithm.

Also, other methods cited in this list do have reference implementations provided by the original authors. I have personally looked at the ref implementations of Dual Contouring and Isosurfaces..., and I wouldn't be surprised if some other methods also have reference implementations.

Doug Moen.

--

You received this message because you are subscribed to the Google Groups "Curv" group.

To unsubscribe from this group and stop receiving emails from it, send an email to curv+uns...@googlegroups.com.

To post to this group, send email to cu...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/curv/15da614c-a79b-4f7b-b150-6403bb6ec476%40googlegroups.com.

[Doug Moen]

While I was googling this stuff, I found a 2015 algorithm called SHREC, based on a 2013 algorithm called MergeSharp, which fixes bugs in Dual Contouring. This is university research; one author, Wenger, has published a book called "Isosurfaces" that deals with this stuff.

"Constructing Isosurfaces with Sharp Edges and Corners using Cube Merging" 2013

http://web.cse.ohio-state.edu/~wenger.4/papers/sharpiso.pdf

"Experimental Results on MergeSharp" 2013

ftp://ftp.cse.ohio-state.edu/pub/tech-report/2013/TR05.pdf

"SHREC: SHarp REConstruction of isosurfaces" 2015

ftp://ftp.cse.ohio-state.edu/pub/tech-report/2015/TR22.pdf

https://github.com/rafewenger/sharpiso

SHREC is a subproject. C++, LGPL, 982 commits over 3.7 years

The SHREC paper makes the following claim about the Simplicial... algorithm: Unfortunately, these algorithms create “notches” along sharp edges, degenerate, zero area triangles or quadrilaterals, and “folds” in the mesh with “flipped” triangles. (See Figure 1 for illustrations of these problems.)

The MergeSharp paper claims to fix the problems of degenerate triangles and self intersections caused by Dual Contouring, and in addition, is tolerant of noise in the distance function. This claim of robustness in the presence of noise is something I haven't seen before. There is one weakness: in the 2013 paper, the output is not guaranteed to be manifold. However, there is 2 years worth of additional work in the SHREC code, visible in git commits, which appears to address this problem.

The SHREC paper is a little more honest. "While MergeSharp reduced the mesh problems, it did not eliminate them, with many meshes still having one or two locations with degenerate mesh polygons or folds in the mesh." And: "SHREC, which almost completely eliminates the mesh problems listed above." And: "SHREC produces far fewer polygons with normal errors than any other software we tested, but it still occasionally produces such errors."

The implication of the SHREC paper is that nobody has a perfect SDF meshing algorithm that also detects sharp edges. The fewer errors you produce, the slower the algorithm is. (SHREC is slow.)

[Matthew Keeter]

Greetings from the meshing tarpit!  I’ve implemented a bunch of different algorithms over the years,

and have been meaning to write them up in a single place; this email is a start.

Doug listed a bunch of different properties; the ones that I group by are:

- Watertight

- Manifold

- Not self-intersecting

- Hierarchical (i.e. meshing flat planes with fewer triangles)

- Correctly reproducing sharp features (corners / edges)

- Correctly reproducing thin features

Marching cubes: not self-intersecting, no other desirable properties

Has issues with manifold / watertight / hierarchy, and edges are bevelled

Marching tetrahedrons: watertight, manifold(?), not self-intersecting

Is manifold / watertight, but non-hierarchical and edges remain bevelled.

There’s also a stronger non-isotropic behavior, based on how you build the tets

Cubical Marching Squares: Weird.

I agree with Doug’s assessment of this one.  For a while, I had the main implementation

on the internet (in kokopelli); but it only implemented about 50% of the paper.

George Rassovsky wrote a different implementation after we corresponded, but I haven’t

looked into it – this algorithm is best left alone.

Feature Sensitive Surface Extraction from Volume Data: sharp features

This paper describes a way to detect triangles that are likely to contain an edge + corner,

and bump out an extra vertex to improve sharp feature performance.  It’s got a good explanation

of QEFs and how they can be built from position + normal samples and used to position vertices.

Dual contouring: watertight(?), hierarchical, sharp features

This is a strong local maxima in meshing algorithms – it’s not too hard to implement,

and works really well.  The main limitation is that meshes have self-intersections

and can be non-manifold.  There’s a good companion paper called “Dual Contouring:

The Secret Sauce” which talks about implementation details.

Dual Marching Cubes (Nielsen): Weird, and I don’t remember much about it,

but it apparently inspired Manifold Dual Contouring

Manifold dual contouring: manifold, watertight, hierarchical, sharp features

This is a worthwhile minor improvement to Dual Contouring, and the primary algorithm in libfive

It allows more than one vertex in a cell, to avoid non-manifold cases.  The main limitation

remains self-intersections.

Intersection-free Contouring on An Octree Grid: watertight, hierarchical, sharp features, not self-intersecting (probably)

This is an alternate improvement to Dual contouring, which tries to address the self-intersection issue.

It’s okay, but not great – it doesn’t handle the case where vertices completely escape their

containing octree cell.  It’s also not compatible with manifold dual contouring: if you try to

combine the two, then you can end up with self-intersections in a multi-vertex cell.

Dual Marching Cubes (Warren): manifold, watertight, hierarchical, sharp features, thin features

There are clever ideas to internalize, but I’ve found obvious cases where it just doesn’t work;

I’m not sure if I’m misunderstanding something or the algorithm just isn’t that great.  On the other

hand, the idea of positioning vertices on sharp features of the underlying field led to….

Isosurfaces Over Simplicial Partitions of Multiresolution Grids: watertight, manifold, not self-intersecting, hierarchical, sharp features, thin features (everything!)

This is what I’m trying to implement in libfive right now.  It’s a very clever algorithm that has

all of the desirable properties, and builds on a lot of other ideas (Dual Contouring, Warren’s DMC

and Marching Tetrahedrons).  It’s not too much more complicated than dual contouring in theory, but

you have to be really comfortable with QEFs – I ended up writing a long explainer while digging

through the math.  It’s much harder to make fast, and produces many more triangles unless you implement

some of the bonus algorithms from the paper.  Also, the paper only describes top-down construction,

which I’m skeptical about, so I’ve developed a bottom-up way to build the octree (to guarantee finding

shapes above a certain size, rather than trusting a heuristic + sampling).

Those new papers look interesting – I’ll have to give them a read-through!

Regards,

Matt Keeter

-- 
You received this message because you are subscribed to the Google Groups "Curv" group.
To unsubscribe from this group and stop receiving emails from it, send an email to curv+uns...@googlegroups.com.
To post to this group, send email to cu...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/curv/1546561000.3560550.1625002872.638F13E2%40webmail.messagingengine.com.

[Andy Baker]

Sorry to revive this long-deceased thread but have any of you heard of Vorocrust?

Is it relevant to this discussion at all? I've only skimmed the info about it and I might be misunderstanding what it's for.

There's examples of it being used in the wild if you search Github.

[Doug Moen]

Thanks for the pointer. My main issue with Vorocrust is that it isn't open source, and it is patented. So I can't even use the algorithm. The output looks very nice, though.

My current thought is that I should use the variant of dual contouring that is free of self-intersections, and that I should deal with the non-manifold problem by vertex splitting to produce a manifold OBJ or 3MF file. The output will be manifold and defect free as defined by the 3MF standard. I can get an open source implementation of the basic algorithm in C or C++ from github, then hack it to perform vertex splitting. This trick won't give me manifold STL files, or work with OpenSCAD. But it does satisfy the requirements of modern 3D printer slicer programs and it works with Meshlab, all of which will consider these files to be defect free meshes. It's pretty simple to implement compared with all the alternatives that I have considered. It's the only approach I've found that supports sharp edge detection while producing guaranteed defect free output (for at least one definition of this term). But I've been too distracted with other things to work on this yet.

Doug.

--

You received this message because you are subscribed to the Google Groups "Curv" group.

To unsubscribe from this group and stop receiving emails from it, send an email to curv+uns...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/curv/dd6d664a-e0ec-422c-af58-75e3b283e8ea%40googlegroups.com.