How to Triangulate a Concave Mesh Surface Without Explicit Constraints?

[rami]

Hi everyone,
I’m excited to post again in the JMonkey Hub!

I’m working on creating a mesh surface around a complex object (composed of a group of geometries). Using a complex algorithm, I’ve managed to generate a set of points that surround the object. Now, I need to triangulate these points to form a 3D mesh. I started searching for a way to triangulate the points to create a 3D mesh. There where many libraries for 2D triangulation but less for 3D. I found some good options such as TetGen Library, JTriangle and most of them support Delaunay and ear clipping triangulation. However, all of them can handle concave shape efficiently, but can’t handle concave shapes. Some of them need constraints that describe the general layout of the mesh to generate correct triangles like general boundaries of the mesh like the following image.

However, as my mesh is not regular such as those designed using CAD software I can’t generate such information. The surface is something like this:

It can have random shape and can have holes. How can I triangulate my concave shaped mesh without having explicit constraints?
Also, I suggest including the triangulation functionality in JME. This can be very useful for games were meshes can be modified in real time such as the ability to cut objects with a sword or puncturing a wall with a bullet.

[richtea]

Arguably an object with holes can’t be uniquely defined by points. You could always string a hole inbetween the points; how is the triangulaiser to know.

Can you produce voxels for your shape? I wonder if that would allow you to find the contraints the later library wants

[pspeed]

As richtea says, what you are trying to do is mathematically impossible in the general case.

What is it that you are actually trying to do? What is the source of the data? Why are you trying to do this?

All of those may be indicators of where assumptions can be made in order to generate a mesh from a point cloud. Otherwise, it’s not possible.

[rami]

Thanks @richtea and @pspeed. I assumed this is possible as Delaunay algorithm can triangulate any set of points into convex shape.

My object is composed of collection of small balls connected to each other. I want to create a surface for this object that is slightly larger than it so the surface covers all the balls but don’t touch any of them (the distance between the surface and each exterior ball is 1.4m). I iterated over all balls and tested on each ball 12 vectors with 1.4m length for all directions if its distance with all other ball is more than 1.4m I will count this point. The collected points now can cover all the object with no points in the object core.

I started thinking about iterating over the object in circles like the one used to build a sphere .

[richtea]

Wouldnt it be easier to create a larger ball for each prime ball, then merge all those large balls together. You’d get some redundant internal geometry but it might be easier to eliminate redundant internal triangles than to calculate your outer shape (assuming it matters, if you dont have that many balls it might not)

[pspeed]

@rami

I assumed this is possible as Delaunay algorithm can triangulate any set of points into convex shape.

Yes, convex is possible.

CONCAVE is impossible in the general case. It’s trivial to find examples of even 5 points that could result in several different concave shapes.

@rami

I want to create a surface for this object that is slightly larger than it so the surface covers all the balls but don’t touch any of them

But why are your trying to do this? You’ve told us technically what you want to do but not what you are actually trying to do.

I’m trying to make sure we’re not close to a “How do I inject things into my stomach” conversation:

Problem to add texture to a Mesh

@aprouzeau said: Ok I get this now, but how define the index in order to draw a surface passing by all the points defined ? Knowing the fact that I don’t know the coordinates of the points when I write the code. This is starting to feel kind of like a “How do I inject something right into my stomach?” sort of conversation (*). You have already ended up at some strange end place when chances are there were earlier choices to make that would make it a non-issue. Unfortunately, we don’t know what…

[pspeed]

@richtea

Wouldnt it be easier to create a larger ball for each prime ball, then merge all those large balls together.

Or just use marching cubes.

It’s not clear to me what the intent actually is so it’s tough to assume what concessions can be made.

[rami]

@richtea

Wouldnt it be easier to create a larger ball for each prime ball, then merge all those large balls together. You’d get some redundant internal geometry but it might be easier to eliminate redundant internal triangles than to calculate your outer shape (assuming it matters, if you dont have that many balls it might not)

I thought about it. However, I couldn’t figure out how to merge the balls into one mesh and to smothen out the resulting mesh.

@pspeed

But why are your trying to do this? You’ve told us technically what you want to do but not what you are actually trying to do.

Simply I just want to create surface to a slightly complex object so I can color certain regions on that surface. It is just for visualizing the surface and maybe used for calculations based on this surface. This is for a chemistry and physics project I am currently working on.

[sgold]

@rami

I couldn’t figure out how to merge the balls into one mesh and to smothen out the resulting mesh.

Typical JME meshes can be combined using the MyMesh.merge() method in the Heart library. Smoothing could be more difficult.

[pspeed]

@rami

I couldn’t figure out how to merge the balls into one mesh and to smothen out the resulting mesh.

If you treat each point like a ‘signal’ where you want to draw a surface at a certain signal level… then “Iso-surfaces” (also called meta-balls Metaballs - Wikipedia ) are what you are maybe looking for. Marching cubes is the approach to rendering smooth isosurface meshes.

I created a marching cubes implementation a long time ago. It can be found here:

IsoSurface/src/main/java at master · Simsilica/IsoSurface

…old-style build, though. Essentially, create a density field that adds up the inverse square distances from your points and then generates a mesh for it at a certain value.

[rami]

This is the result of merging spheres from the dots I have. It is somewhat similar to what I want. However, merging function in the Heart library doesn’t exactly merge the meshes to create a unified surface. Maybe the marching cubes algorithm would be suitable for a smooth surface.