Understanding Triangulation

Feb 14, 2012 at 5:01 PM

Trying to do a 3D Delaunay.  My input data is a point cloud of a non-smooth cylinder, that is, it has an open "top" (that just happens to be aligned with the z-axis, if that matters).  I want to draw a surface in 3D.

The "cell" results have 4 elements (each) in the Vertices and Adjacency fields.  I'm surprised; I was expecting 3.  What am I missing?  The comments for Adjacency actually say "Array of length "dimension"".

I don't understand Adjacency.  What does each element represent?  Can anyone expound on the documentation:  "If F = Adjacency[i] then the vertices shared with F are Vertices[j] where j != i.  In the context of triangulation, can be null (indicates the cell is at boundary)."

Finally, for now, am I way off base?  I created the triangulation, iterated over the resulting cells, and used vertices 0-3 for my triangles.  The resulting figure was sort-of right, but had some odd triangles that seemed to be backwards (i.e. they were in the background color).

any thoughts appreciated.


Feb 17, 2012 at 5:42 PM

Hi Reilly,

you understood it right. The problem with the back facing triangles is that the vertex orientation is not correct for some reason... That might be either problem in the miconvexhull code or an error on your part.

There are several ways to fix the problem:

- There might a problem if the points all lie on the same plane. In this case, introducing some noise to the data usually solves the problem.

- If you want to draw the surface, find the convex hull (as the boundary of the Delaunay triangulation is a convex hull). Then the triangles *should* be aligned correctly (I don't remember if it was clockwise or CCW ordering now). However, this will not work if there are redundant coplanar points

- For each of the triangles you correctly identified from the tetrahedrons, calculate the triangle normal and see which way it's pointing. As a pivot you might use for example the centroid of the tetrahedron. If it points towards the centroid and your original triangle has vertices x, y, z simply reverse their order to fix the normal orientation.

Beyond this I might be able to help you if I've actually seen the code.


Feb 21, 2012 at 12:26 PM

Hi David,

Thanks for your reply.  Your second suggestion (find the convex hull) gets me part of the way there.  I had started out this way; just modifying the 3DConvexHullWPF project to use my points.  The issue then was two-fold.

1.  Is this what I want?  I want to draw the surface as a series of interconnected vertices, not necessarily a bounding convex hull, which, as I understand it, does not include "internal" points.  It is a bounding hull, not a mesh of all points.

2.  The "top" of my figure is open (i.e. it is a cylinder with an open top and rounded bottom), but the convex hull is a closed surface.  So how to remove the "top"?

I have used MATLAB "triscatteredinterp" to plot the raw data, and their documentation indicates that they use a Delaunay triangulation of my points.  So I was using your code to just do the Delaunay part, not the convex hull, which I don't think is what I want.  I want something to create a mesh from my points.  And I don't have point normals, so triangulation seemed to fit the bill.

Computational geometry is a new area for me and I'm fighting the terminology.  Any guidance will be greatly appreciated.



Feb 21, 2012 at 1:05 PM

Well, removing the "top" is easy if you know which vertices belong to it. If the triangle/tetrahedron contains any of the top vertices, simply don't draw it.

As for your issue with normals. Point normals are interpolated from the normals of surrounding triangles. Triangle normal is computed as a cross product of its vertices. If you don't provide the normals, they are computed automatically and the result is determined by the orientation (ie. clockwise or counterclockwise) of the triangle vertices. Now, if you extract the vertices from the tetrahedron (i.e. the vertices of the TriangulationCell  class), the ordering of the vertices is not uniquely determined. That is why some of the triangles are "backwards". On the other hand, if you use the convex hull, every face/triangle has a clockwise ordering (or was it CCW, I don't remember now) and you get the correct orientation. Fortunately, you can fix the orientation by knowing which direction is the correct one. That is usually the one going "away" from the geometrical center of the corresponding tetrahedron.

Now to the MATLAB's interpolation function. It simply uses the triangulation to determine which data points to use for the interpolation - if you query a point v, it finds the tetrahedron to which v belongs and uses its vertices to interpolate the value for v. Either way, the order of points in the TriangulationCell class has zero effect on the value from get from the interpolation. Additionally, if you actually want to use miconvexhull to do some interpolating, the data structure used to store the tetrahedron's isn't the best because it does not support point location ...

To be honest, I still struggle to understand what is it you are exactly trying to achieve....

Feb 21, 2012 at 3:18 PM

Simply put:  mesh generation.  I have a machine which uses a laser to scan the inside of a part on the micrometer level.  And am looking at rendering the x,y,z data.  I was trying to draw a surface using WPF, so I need to generate a triangular mesh.  Most of the surface generation methods I've seen will smooth the data, which I do not want.  I was hoping Delaunay would interconnect my points so I could draw the irregular surface.

This problem *seems* to me (naively) easier than it has turned out to be.

Thanks, David.  Good code, and fast.

Feb 21, 2012 at 4:05 PM

Yeah, I imagine the solution to your problem requires a good deal of post-processing the triangulation.

One thought I have is that you know what the average distance between 2 measured points is. Using this, you can identify tetrahedrons, that are too big (ie. contain a long edge). These tetrahedrons will (at least in most cases) also have at least one side, that is "small" (ie. all edges will be short). These sides will then correspond to the boundary of your surface and you can easily render them. This average distance can be a user defined parameter (or it could be guessed from the input data). Due to the nature of the data there will most likely be some bad triangles, but this should get you pretty close to what you are after.

Anyway, if you feel like it send me the code with some sample data (thru the profile here you can contact me directly). I have spent a good part of the last year removing tetrahedrons from triangulations so I might be able to help.

Mar 8, 2012 at 6:31 PM

After getting sidetracked for weeks, I came back and read your last couple of posts, and finally got what you were saying.  In rendering, I added a simple check to find the length of an edge.  If the face edge was greater than a threshold, I dropped it.  Solid.  Gold.

The performance is amazing.  Convex hull on 17,640 points in 0.26 sec.  [Win7 64-bit, 2.5 GHz Core i5, 8GB RAM]

I would have sent you my code, but just can't bring myself to take advantage of you that way without the opportunity to at least buy you a Grape Nehi.

I am an electrical engineer with all the required undergrad math, but I know nothing of computational geometry.  If you felt like posting a reference or two to add to my knowledge, I'd appreciate it.

Thanks a ton.


Mar 9, 2012 at 9:39 AM

Glad that it worked :)

Here are the two computational geometry books: http://www.cs.uu.nl/geobook/http://www.amazon.com/Triangulations-Applications-Mathematics-Visualization-%C3%98yvind/dp/354033260X

Mar 9, 2012 at 10:52 AM

Just remembered one thing: the thing you want is called "alpha complex" (by removing the big tetrahedrons, you are actually computing an approximation of it).

Basically what you do is order (ascending) the tetrahedrons by the radius of their circum-spheres. Then you keep adding the tetrahedrons (using the ordering) until you have "covered" all points. Maybe you will be able to achieve more accurate results using this approach.

Mar 22, 2012 at 7:55 PM

Hi David,

I had to use the Delaunay triangulation, as opposed to the Convex Hull, because internal details of my part were not being triangulated.  Which I should have suspected because the hull is, well, convex.

So my question now is, what is the ordering of the vertices?  Or should it even matter to me?  A Delaunay "cell" has the 4 vertices (0,1,2,3) of a tetrahedron.  Which 3 vertices make up the tet's base?



BTW- I started reading the referenced texts.  They are written in a very accessible style.

Mar 23, 2012 at 3:42 PM

Well, it really depends on what approach you are going to use. Overall tho, there is no specific ordering other than relating the vertices to the adjacency.

Ie. if y = x.Adjacency[i] then x and y share vertices x.Vertices[j] where j != i.

In your case it should not really matter to the point where some triangles would be "facing" backwards. However, this can be detected easily or BackMaterial could be set to the same value as the "front" one...

Beyond what I wrote I am not sure I can help you any further without seeing the actual data/code. I have realized now that you did the "removing" on the hull. You can apply the same principle (or the the one I described in the previous post) to the triangulation as well.