search

hmeyer / tessellation

Tessellation is a library for 3d tessellation, e.g. it will create a set of triangles from any implicit function of volume.
Apache License 2.0
42 stars 10 forks source link

watertight triangulation? #7

Open benmkw opened 3 years ago

benmkw commented 3 years ago

Using the sphere example from the readme I get the following result (tried a few variations of parameters but with basically the same results):

Bildschirmfoto 2020-11-05 um 11 52 08

I'm wondering if this is intended or a user error on my side as truescad does not seem to have this issue.

https://www.researchgate.net/publication/310783747_Watertight_and_2-manifold_Surface_Meshes_Using_Dual_Contouring_with_Tetrahedral_Decomposition_of_Grid_Cubes

However, DC is unable to guarantee 2-manifold and watertight meshes due to the fact that it produces only one vertex for each grid cube. We present a modified Dual Contouring algorithm that is capable of overcoming this limitation.

seems to indicate that this may be limitation of the algorithm?

hmeyer commented 3 years ago

Thanks for opening this issue. This looks like a bug to me, b/c this library uses Manifold DC, which is an extension to DC that guarantees water tight meshes.

virtualritz commented 3 years ago

I can for now confirm that the mesh from the sphere sample does look like it's not a 2D manifold. I tried to cleanup this mesh, exported as OBJ in Wings3D, and got a crash. From almost 20 years of experience with Wings3D I can say that this app is one of the most lenient ones in dealing with non-manifold topologies. Which suggests something is pretty bad. In my fork I added the sample from the docs to an examples folder which creates below mesh.

Here is an image from within Wings3D. I selected the three bad quads that are somehow weirdly connected to the rest of the mesh:

Screen Shot 2020-11-27 at 21 00 51
hmeyer commented 3 years ago

Thanks for looking into this in more detail. And thanks for the screenshot. It looks like indeed there is some lingering bug in the meshing. How much post processing was applied to above mesh? I'm asking b/c it looks like the some of the faces (e.g. the two large faces close to the top) seem to be 5-gons. And I wonder how this algorithm could possibly have produced those.

If somehow possible we should try to reduce this buggy example to an even simpler one and then try to find the step where things go wrong. One thing we can do for debugging is to disable subsample_octtree(), which tries to simplify the vertex structure by merging vertices that are within some error margin.

virtualritz commented 3 years ago

The above mesh has zero post processing. But what Wings3D does, on import, is turn the mesh into a 2D manifold. I.e. it may delete some non-manifold topological features locally and that may have caused this.

hmeyer commented 3 years ago

I added https://github.com/hmeyer/tessellation/commit/47fe5c2fe51e4e24b5104a1293a3cfe0b0fc642d, which exposes this bug. It also shows this bug seems to happen in the simplification step (as it is not triggered, when simplification is turned off).

DanielJoyce commented 10 months ago

Wonderful that I found a impl of Manifold dual contouring in Rust, I also know of another impl that under the hood uses a machine translated C -> Unsafe Rust version.

I'm working on some 3D stuff which would need this feature. Do we have an idea where the bug may lie?

DanielJoyce commented 10 months ago

This one has a impl in C#

https://github.com/Lin20/isosurface

This one is also in rust, but the dual contouring SVD/QEF solver was machine ported from C to unsafe Rust

https://github.com/swiftcoder/isosurface

DanielJoyce commented 10 months ago

I'm currently banging out a hashed linear octree.