# Conversion of unstructured points to a connected unstructured grid (auto add edges)

I’m trying to convert a 3D point cloud into an unstructured grid where the tetrahedral cells produced comprise of only 4 points and 6 edges each and do not contain any other points within their volume. I don’t have any information relating to which point connects to each and want to generate those relationships inherently off of their position alone. Think of it as trying to create as many individual cells as possible in a volume without letting the cells overlap in space.

I figured the simplest way to do this would be to generate a tetrahedron at random, pick the closest point to the center of the tetrahedron and then subdivide and just keep going until the mesh was complete but that would produce vastly irregular cells. I think that a density based approach would make the most sense however I wanted to see if an existing method is already implemented in VTK/Paraview before diving in.

I’ve attached some images of how TetGen makes its cells (unfortunately displayed as a surface so you can’t see the points within the volume), I was hoping for something like this:

Note that the edges present in the image pass thorough the grid and are not simply a surface, I basically want a volumetric mesh.

You can try `Filters -> Delaunay3D`, that will produce tetrahedrons from points.

Using Delaunay3D seems to only give me cells at the surface rather than dividing the space into tetrahedral regions (which makes sense from what I know about Delaunay triangulations), the behaviour that I’d like is to create polyhedra that have no points within them which is more a space-division technique rather than finding the boundary points.

I’m rendering the resulting Delaunay3D using wireframe mode, unless the inside edges are hidden I don’t think the filter does what I want. I’d expect to see each point connected with at least 4 edges if they were visible.

You’re right. You will need to implement this yourself.

I feared as much, I have a feeling that irregular grid interpolators have to form the kinds of simplices I want in their calculations so I’ll look in that direction instead. Thanks for the confirmation anyways.

After a bit of investigation it was easy enough to implement this using SciPy’s Delaunay function. I’m still a little puzzled as to why this isn’t a feature of the existing Delaunay3D filter as it seems like your current implementation only generates the convex hull of the points sampled.

For anyone hoping to replicate this I simply exported the points array, provided that as an input to Scipy’s Delaunay triangulation, removed duplicate edges using a set and then iteratively generated a new unstructured grid from the unique edges. Seems like a long walk for a glass of water though.

I hope that the team working on VTK can see the value in having a filter that does this natively, the use of structures like this in Finite Element Analysis is incredibly common.

That is not the case. ParaView will show you the surface, but if you cut the resulting mesh with a Clip filter and look at the interior of the result of Delaunay3D, you will see the tetrahedral mesh.

Alternatively, you can extract all edges in the dataset with the Extract Edges filter to see all the edges you were expecting.

2 Likes

That makes a lot of sense, applying Extract Edges does seem to give me the format I was originally expecting. I do find it a little weird that the convex hull surface is the default output of a Delaunay3D filter rather than the edge representation but maybe that’s just me.

Thanks for providing me the necessary information for me to continue my work, this solution is likely far more efficient than my workaround so I’ve marked it as the solution.

Thanks @cory.quammen for being thorough.

That is not the data that is produced, but what is represented. That’s an important concept in ParaView. You have the data produced by a reader or filter, and you have different ways to display it. For unstructured grids, usually the “Surface” representation is used to provide a good balance between the size of the data that is rendered and depicting at least the outer boundaries of the dataset, which is useful in a lot of cases. The sheer number of internal edges from an unstructured dataset of any useful size would be too large and result in a blob of unintelligible white in most cases in the render view.

1 Like