Add your own alternative version
Stats
61K views 6.2K downloads 45 bookmarked
Posted
3 May 2013

Comments and Discussions


Hello,
Thank you for sharing your work. Very helpful for C++ nonexpert!
I am interested in 3D triangulation. In that regard, I have 2 questions for you.
1) You mention "However, when you provide it with 3D points, (XY and Z values), it gives back a fourth value. I don't know what that fourth value is, so triangleList_out() is ignoring it." A 2D Delaunay triangulation (obviously) generates triangles (3 vertices). But a 3D Delaunay triangulation should generate tetrahedrons (4 vertices). Could the code generate tetra when providing 3D points (X,Y and Z)? This fourth value would be the fourth vertex of the tetrahedron.
2) I still have trouble to correctly interpret the output format (triangleIndexList). I have this example of a 20x20x20 cube:
int g_numTestPoints = 8;
int num_dimensions = 3;
int numTriangleVertices;
float *temp_array = new float [g_numTestPoints*num_dimensions];
temp_array[0] = 10.0;
temp_array[1] = 10.0;
temp_array[2] = 10.0;
temp_array[3] = 10.0;
temp_array[4] = 10.0;
temp_array[5] = 10.0;
temp_array[6] = 10.0;
temp_array[7] = 10.0;
temp_array[8] = 10.0;
temp_array[9] = 10.0;
temp_array[10] = 10.0;
temp_array[11] = 10.0;
temp_array[12] = 10.0;
temp_array[13] = 10.0;
temp_array[14] = 10.0;
temp_array[15] = 10.0;
temp_array[16] = 10.0;
temp_array[17] = 10.0;
temp_array[18] = 10.0;
temp_array[19] = 10.0;
temp_array[20] = 10.0;
temp_array[21] = 10.0;
temp_array[22] = 10.0;
temp_array[23] = 10.0;
WORD *triangleIndexList = BuildTriangleIndexList(
temp_array,
10,
g_numTestPoints,
num_dimensions,
1,
&numTriangleVertices);
I get 18 elements in triangleIndexList. In one of your answer, you mention "You use the indexes in groups of three. The first three values identify the first triangle, the second three values identify the second triangle, etc.". So, in my case, it gives "only" 6 triangles (it should give 18 triangles, or 6 tetrahedrons). Am I missing or misinterpreting something?
Thank you for your help!





I keep trying to compile this in visual studio 2013, but there seems to be a dependency issue inside the DXUT.h library itself. Do you know if there is a reason for this?





I don't know you mean by a "dependency issue". Can you provide more details on the problem?
I installed the DirectX SDK, which included the DXUT header and library files. You can also download DXUT separately at this page:
DXUT for Direct3D 11  Home
I assume that is the same as what came with the DirectX SDK.
The program I created was just a modification of one of Microsoft's DirectX tutorials, so if you can get their tutorials to compile, then this should compile, also.
It should be noted that the DXUT header files create hundreds of warning messages that you have to ignore.





Probably you won't see this because it has been a few month since your last update :P
But I want say thanks, this really helps.
I have a little suggestion about the produced triangles in 3D.
That is,the program breaks if there are more than 20 3Dpoints in the input.
After viewing the source code, I found that it had something to do with maxOutputEntries.
As long as I made the value of maxOutputEntries larger, everything worked perfectly.
It seems that maybe the problem was due to the overflow of it.
Thanks again!
(PS. sorry about my English, I'm Taiwanese xD





See my reply in another thread below:
A Delaunay triangulation function in C[^]
Basically, you can make it resize the output array when needed. The problem is that the array is allocated once with a guess of how many triangles there might be.
Edit: Link doesn't seem to work... I'll just copy the post:
I was having issues with 3 dimensions as well.
One thing you need to do is to resize the output array when needed. It is allocated once with a "guessed" size, and if you end up producing more triangles, it just keeps writing outside the buffer.
In the triangleList_out method, you need this:
if (v0 >= 0 && v1 >= 0 && v2 >= 0 && v3 >= 0) {
if (currenOutputIndex+3 >= maxOutputEntries)
{
maxOutputEntries*=3;
ptrToOutputList = (WORD*)realloc(ptrToOutputList, (maxOutputEntries + 1) * sizeof(WORD));
(void*)ptrToOutputList).arg((int)((void*)ptrToOutputList)+((maxOutputEntries + 1) * sizeof(WORD)));
}
I'm still having other issues with 3 dimensions, but I got past the crashing part with this.
I also laughed when I saw this just a few lines later:
I read this as: "It worked for me, so let's just take a guess and assume we will not ever write outside the buffer"





That is a simple way to solve the memory overrun problem, although I would have increased maxOutputEntries by a fixed value rather than multiplying it by three each time.
Anyway, as for why I didn't deal with the possible memory overrun problem, I suppose it was because his original program was doing a lot of checks, and if any of them failed, he called exit() , which is tolerable in a standalone DOS program, but irritating as a function, so I suppose I got tired of dealing with all of the calls to exit() and deleted the test since it didn't seem necessary. But now that you mention it, that was a ridiculous thing for me to do!
Also, maybe the memory overrun problems occur only with 3D points.
Some people complained that 3D points are not triangulated properly, so maybe I messed up the function when I converted it, or maybe the function was never tested properly for 3D points. I don't understand the function well enough to know why the 3D points don't work. I use it only for 2D points, so I never noticed.





Thanks for the excellent work.
Is it possible to compute the Voronoi diagram using the program?





Dear Author,
I have tried your solution. It works perfectly for 2D case, but for 3D points it generates 0 triangles. Could you tell me what is wrong with my test. I define three 3D points:
int numPoints = 3;
int dimension = 3;
float * testPointsXYZ = new float [numPoints*dimension];
testPointsXYZ[0] = 0;
testPointsXYZ[1] = 0;
testPointsXYZ[2] = 2;
testPointsXYZ[3] = 0;
testPointsXYZ[4] = 0.1;
testPointsXYZ[5] = 1;
testPointsXYZ[6] = 0;
testPointsXYZ[7] = 0.2;
testPointsXYZ[8] = 3;
and call
int numTriangleVertices;
WORD *triangleIndexList =
BuildTriangleIndexList(
testPointsXYZ, 10, numPoints, dimension, 1, &numTriangleVertices);
It gives me 0 triangles. I have tested same points for 2D case (just dropping Zaxis) and my test was successfull.
What am I doing wrong?
Regards
Anton





You are giving the function three points, and then asking it how to create a triangle from those three points. Ken Clarkson wrote that function under the assumption that you are going to give it at least four points.
The function actually returns the three points, but it identifies them as points in the convex hull rather than as triangles. In the functiontriangleList_out()
I have the following test to ignore the points of the convex hull and return only the points that form triangles:
if (v0 >= 0 && v1 >= 0 && v2 >= 0 && v3 >= 0)
However, the function doesn't return triangles when you have only one of them.





Thank you for the fast replay. I followed your tip and added one more point
int numPoints = 4;
int dimension = 3;
float * testPointsXYZ = new float [numPoints*dimension];
testPointsXYZ[0] = 0;
testPointsXYZ[1] = 0;
testPointsXYZ[2] = 2;
testPointsXYZ[3] = 0;
testPointsXYZ[4] = 0.1;
testPointsXYZ[5] = 1;
testPointsXYZ[6] = 1;
testPointsXYZ[7] = 0;
testPointsXYZ[8] = 3;
testPointsXYZ[9] = 1;
testPointsXYZ[10] = 0.1;
testPointsXYZ[11] = 2;
but as before I get 0 triangles back. To sum up, I have two major questions:
1. Why the function behaves differently in case of 3 points? (I mean it produces one triangle for 2D and 0 for 3D points)
2. And more essentially: I need trianglulation for 3D point sets. All my tries failed. What am I doing wrong?
Thanks a lot for the help
Regards
Anton





It looks like you discovered a bug or limitation of the function when asking for triangulation in 3D. The points that you selected are all in the same plane, and the function fails with points that are all in one plane. I tried it with five points in the same plane, and it failed with that, also.
In order for the function to work with 3D points, at least one of the points must be off the plane of the other points. If I make just one tiny change to any of your points, such as changing testPointsXYZ[10] = 0.1 to 0.2, it works fine.
It is possible that Clarkson never considered that somebody would give the function 3D points that are all in the same plane. It is also possible that I messed something up when I converted his function. I don't understand the function well enough to debug it. Perhaps somebody who understands what the function is doing can fix it and post an improved version.





Hello,
I put into the function a list of 8 points with 3 coordinates (2 polygons) but the triangles that the function return doesn't cover the 6 faces of the cube.
For example: if i put my list in this order: P1, P5, P2, P6, P3, P7, P4, P8 or in the good one, the function never returned a combinations with the point P6 in the first order or P5 in the second one.
Can you help me to correct this please ?
PS: sorry for my english, i'm French ^^
modified 25Jun14 11:44am.





First, it does not matter what order you provide the points. The function will analyze your points and return the triangles according to the rule that it is following, as explained here:
http://en.wikipedia.org/wiki/Delaunay_triangulation
Second, I don't know what values you gave the function, or what you are expecting the function to do for you, so I can't help you. Maybe you need a mesh function, not a triangulation function.





I would like to display a piece of wood thanks to a list of points regroups in polygons.
The problem is that I don't always have 4 points in the polygons, i can have more or less.
That's why I need to use triangles: to represent a polyhedron and then use a triangleList to display them.





Thank you so much for distilling Clarkson's code into something usable!!





I don't knowmuch about this.
am i supposed to give a pointer to [n][2] as input.Also how to use the output.I have points and i only want to triangulate them and plot them.





Sorry for the late response. I just noticed my the notifications of messages were going in my spam folder.
If you are giving it only X and Y values, you give the function a simple list of those values.
For example, you could create the list like this:
float *pointList;
pointList = (float*)malloc (12345);
pointList[0] = the 1st x value
pointList[1] = the 1st y value  this is 1st point
pointList[2] = the 2nd x value
pointList[3] = the 2nd y value  this is 2nd point
etc
You call the function with the number of points, not the number of values in the array.
And you also call it with the number of dimensions, either 2 for X and Y values, or 3 for XY and Z values.
The output of the function is a list of integer values. That list is the same as the "indexed lists" that OpenGL and DirectX use for displaying triangles.
The values are indexes into the point list that you gave to the function. You use the indexes in groups of three. The first three values identify the first triangle, the second three values identify the second triangle, etc.
For example, assume the function returns a list with these values in it:
7, 1, 5, 6, 8, 2, 3, 4, ...
7, 1, 5,  this identifies the first triangle
The values are indexes into your point list. At pointList[7], you will find the first vertex of the first triangle:
pointList[7]  the X value of vertex 1 of the 1st triangle
pointList[7+1]  the Y value of vertex 2
pointList[1]  the X value of vertex 3
pointList[1+1]  the Y value of vertex 1 of the 2nd triangle
pointList[5]  the X value of vertex 2
pointList[5+1]  the Y value of vertex 3
The code you need to get those values can be a bit confusing. Here is an example using a "typedef" that allows your list of points to be regarded as having X and Y values:
typedef float (*xy2dArray)[2];
xy2dArray pointList; // pointList is a 2d array
int numTriangleVertices;
INT16 *triangleIndexList, *ptr;
triangleIndexList = BuildTriangleIndexList (
pointList,
1000., numInputPoints, 2, NO,
&numTriangleVertices);
int *ptr = triangleIndexList ; // This example uses a pointer to the output list
while (numTriangleVertices > 0) {
numTriangleVertices = 3;
= pointList[ ptr[0] ][0]; // vertex 1, x
= pointList[ ptr[0] ][1]; // vertex 1, y
ptr++;
= pointList[ ptr[0] ][0]; // vertex 2, x
= pointList[ ptr[0] ][1];
ptr++;
= pointList[ ptr[0] ][0]; // vertex 3, x
= pointList[ ptr[0] ][1];
pPtr++;
}
Once you understand this concept of "indexed list", you will be able to use the indexed lists in OpenGL or DirectX.





Thank you for such function. I needed in it for my diploma





Hi,
Can you post a sample of the format of the point array expected for void *pointList? Is this a structure of x,y,z? I will be using x,y&z coords.
Thanks for the help. I've got it compiled in my CAD software but just don't understand what format the point array is in.
Curt





Sorry for the late response. I just noticed the notifications of messages were going to my spam folder.
The format for the array for XYZ values is just a simple list.
For example, you could create the list like this:
float *pointList;
pointList = (float*)malloc (12345);
pointList[0] = the 1st x value \
pointList[1] = the 1st y value  this is one point
pointList[2] = the 1st Z value /
pointList[3] = the 2nd x value
pointList[4] = the 2nd y value
pointList[4] = the 2nd z value
etc
You call the function with the number of points, not the number of values in the array.
And you also call it with the number of dimensions, either 2 for X and Y values, or 3 for XY and Z values.
modified 25Jun14 12:29pm.





Hi,
Where did you see a "no strings attached" license in Clarkson's work http://netlib.sandia.gov/voronoi/hull.html? I can't find any license at all, which would mean he gives no license to use it. I tried to ask him but his email address didn't work.
Kimmo





You did not find any license information on that webpage because he provided only a description of the software on that page, not licensing information or warning messages about its use.
If you download his source code, you will find the following comment at the top of his files:
* Permission to use, copy, modify, and distribute this software for any
* purpose without fee is hereby granted, provided that this entire notice
* is included in all copies of any software which is or includes a copy
* or modification of this software and in all copies of the supporting
* documentation for such software.
I interpret his comment to mean that we can do whatever we please with his source code. All he asks is that we leave his message in the source code, which I did.
By comparison, software from people at universities usually has restrictions, such as this from Jonathan Shewchuk:
Please note that although Triangle and Show Me are freely available, it is copyrighted by the author and may not be sold or included in commercial products without a license.
http://www.cs.cmu.edu/~quake/showme.html[^]
Usually when a person is restricting his software, he puts a warning message on the description page in addition to the source code so that everybody can clearly see it. When a person doesn't bother with any licensing information in a description of his software, it is usually an indication that his doesn't impose any restrictions.
Finally, you assume that if you don't find licensing information for some source code, that we are not allowed to use it. I don't know the laws of different nations, but I think the opposite philosophy would be more practical. Specifically, if a person posts his source code on the Internet without any restrictions, then it should be interpreted as freely available. People who want to provide source code, photographs, drawings, etc., to the public should not have to be bothered to include legal messages that it is freely available.





This is a great inspiring article. I am pretty much pleased with your good work. You put really very helpful information. Keep it up once again.





I vote you a 5 for your ordeal with macro hell





when change NUM_DIMENSIONS to 3, Exception occurs when call BuildTriangleIndexList





When I tested the function for three dimensions, I generated only six random points by setting:
int g_numTestPoints = 6;
I just did some more testing, and the function seems to fail regularly when given more than about 12 random points. I suppose that more than 12 random points are too unrealistic. We would need some sets of realistic 3D points to test it with.
By the way, in order to see the 3D rectangles, you need to turn off the culling mode. If you are not familiar with that, I did it by adding this block of code to the end of the InitDevice() function:
<br />
InitDevice()<br />
{<br /> <... initialize graphics, set pixel shaders, etc. ..><br />
ID3D11RasterizerState* NoCullingTriangles; // Create a variable for the raster state<br />
D3D11_RASTERIZER_DESC wfdesc;<br />
ZeroMemory(&wfdesc, sizeof(D3D11_RASTERIZER_DESC));<br />
wfdesc.FillMode = D3D11_FILL_SOLID; // or try D3D11_FILL_WIREFRAME<br />
wfdesc.CullMode = D3D11_CULL_NONE; // this stops the clipping of triangles<br />
g_pd3dDevice>CreateRasterizerState(&wfdesc, &NoCullingTriangles); <br />
g_pImmediateContext>RSSetState(NoCullingTriangles); // set the state<br />
NoCullingTriangles>Release(); // Apparently you can release this immediately<br />
// if nothing is going to change the state<br />





Thanks for your reply！！
I just got some real data
4.119 11.621 1.128
7.509 10.311 2.936
7.282 10.358 2.647
6.861 10.773 2.465
6.259 10.875 2.159
5.893 10.958 1.754
5.2 11.017 1.478
4.766 11.324 1.393
4.267 11.316 1.202
4.119 11.621 1.128
4.068 11.875 1.053
3.75 11.701 0.823
3.573 11.916 0.859
3.408 11.961 0.754
3.235 12.148 0.722
3.079 12.2 0.653
2.931 12.163 0.499
2.756 12.36 0.561
It works！！
I'm planning using open gl for display





That reminds me, if you are going to use this function for 3D triangles, my functions IsTriangleClockwise() and IsFloatTriangleClockwise() for determining whether the triangles are clockwise or anticlockwise might not be of any value.
If you are generating triangles for a shape that wraps around itself, such as a tube or a sphere, you may have to take into account which triangles are in "front", and which are in "back".
I looked into the issue of how to set the direction of 3D triangles, and I came to the conclusion that I don't know what would be best. That is why I only did it for 2D triangles.





thanks for your advise.
about the triangle clockwise thing, I just set to 0.
I built the project with Dev C++ IDE using opengl for 3d drawing. It runs well.
Now I'm stuck when changing it to VS2010 with error lnk2019: unresolved external symbol unsigned short * __cdecl BuildTriangleIndexList(void *,float,int,int,int,int *).
Before I've run your demo project in vs2010 using directx. It works all right.
Things just get so complicated.
All in all, thank you for your help!





I know I'm resurrecting an old thread, but this might be useful:
I was having issues with 3 dimensions as well.
One thing you need to do is to resize the output array when needed. It is allocated once with a "guessed" size, and if you end up producing more triangles, it just keeps writing outside the buffer.
In the triangleList_out method, you need this:
if (v0 >= 0 && v1 >= 0 && v2 >= 0 && v3 >= 0) {
if (currenOutputIndex+3 >= maxOutputEntries)
{
maxOutputEntries*=3;
ptrToOutputList = (WORD*)realloc(ptrToOutputList, (maxOutputEntries + 1) * sizeof(WORD));
(void*)ptrToOutputList).arg((int)((void*)ptrToOutputList)+((maxOutputEntries + 1) * sizeof(WORD)));
}
I'm still having other issues with 3 dimensions, but I got past the crashing part with this.
I also laughed when I saw this just a few lines later:
I read this as: "It worked for me, so let's just take a guess and assume we will not ever write outside the buffer"
On a side note, in case you haven't figured it out by now... The problem is that the code is using WORD as 'unsigned int' (32 bit), while WORD is defined as a short unsigned int (16 bit) in most environments. In your code where you use the function, you should declare it as if it returns an unsigned int*. In ClarksonDelaunay.cpp, note that there's a #define WORD unsigned int at the top, so the code in this file can use 'WORD'. Anywhere outside that .cpp, you'll want to use unsigned int instead.





it's ok now
I can download it
thanks





Your demo project cannot be downloaded
can you fix it ?





I think I fixed it. It worked for me. Give it a try now.






General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

