Triangulation in ICE

[Daniel Brassard]

Here is something that I would like to do, maybe someone can help.

I have a bunch of points that I would like to triangulate. The Indexes are not sequential. I have sorted the indices and select the first point in the array of indices. I use a closest point location to select two more points to create the triangle. Here are my questions:

How do I determine the CCW order to create the triangle and make sure all triangles are facing the same as their neighbour?

How do I mark a point as being visited or part of a triangle so that when I move to the next point, I don't select points already part of a triangle?

Say you have four points at index 03, 07, 33 and 45 arranged in a square configuration. You select the first point and find the closest points are 07 and 33. You create the triangle in the order of 03, 07, 33. Easy enough, you have a triangle and normal. You move to the next point, the closest points to 07 are 03 and 45. If I create the triangle 03, 07, 45 i have a problem with the first triangle, how do I avoid this in ICE?

Thanks for the help!

[grahamef]

One way to do this is to keep track of the edges that you have already done, and those that you need to do. When you add (07, 33) to your DONE list, you search your TODO list for (33, 07). If it's there, you remove it. If it's not, you add it. Then you grab the next edge in your TODO list and look for a suitable point to form a triangle. Continue until the TODO list is empty.

EDIT: Wait, that's not quite right. When you add (07, 33) to your DONE list, you search your TODO list for it. If it's there, you remove it. You also search your DONE list for (33, 07). If it's not there, you add it to your TODO list.

[TwinSnakes007]

Yeah, I'm gonna be watching this topic. Traversing the mesh data is the last step I have left in recreating Guillaume's PolygonIslandTransform using only ICE Modelling [no scripts].

So I need to be able to do something similar to you Daniel: Evaluating the vertex neighbors and building groups of connected polygons without overlapping and including all polygons into a unique group.

Triangulation?....Hmm so Daniel, you trying to wire up your own mesher in ICE?

[Daniel Brassard]

Triangulation?....Hmm so Daniel, you trying to wire up your own mesher in ICE?

Am I that obvious?

[gustavoeb]

you guys are way too advanced... not fair

[Daniel Brassard]

I'm doing some reading on the Marching Triangles algorithm, look promising.

http://epubs.surrey.ac.uk/110986/2/hilton96mt.pdf
http://gc2009.graphicon.ru/files/gc2009 ... _Paper.pdf
http://liris.cnrs.fr/~egalin/Pdf/2001-triangle.pdf

Let's see what we get from those research papers.

[Daniel Brassard]

I have created my points and fed to the topo node and set topology of the ICE tree.

I select the fist point in the array. ICE return the index and point coordinates. So far so good.

If I try "find closest points" or "get closest points" feeding the geometry and first point location, I get the origin, not the closest point? I tried other methods, to no avail. It's like the points don't exist (possible) and ICE return the default point coordinate! (I have 600000+ of those points)

If I feed the index manually (0,1,2,-2) to the polygon description port of the topology node, I get the polygon. So the points are there, I just can't access them.

Any suggestion?

[grahamef]

I have created my points and fed to the topo node and set topology of the ICE tree.

I select the fist point in the array. ICE return the index and point coordinates. So far so good.

If I try "find closest points" or "get closest points" feeding the geometry and first point location, I get the origin, not the closest point? I tried other methods, to no avail. It's like the points don't exist (possible) and ICE return the default point coordinate! (I have 600000+ of those points)

If I feed the index manually (0,1,2,-2) to the polygon description port of the topology node, I get the polygon. So the points are there, I just can't access them.

Any suggestion?

So just to be clear, you've added the vertices without creating polygons, and then set the topology?

In that case, the vertices aren't part of a valid geometry yet, and the geo queries won't really work properly on them. The first thing that comes to mind is to put the positions in an array and find the closest ones in the array.

[Daniel Brassard]

So just to be clear, you've added the vertices without creating polygons, and then set the topology?

In that case, the vertices aren't part of a valid geometry yet, and the geo queries won't really work properly on them.

I suspected that much!

The first thing that comes to mind is to put the positions in an array and find the closest ones in the array.

The points are already in an array. Does it need to be in a pointposition array?
I'll post the ICETree tonight!

Something to test. Thanks Grahamef.

[Daniel Brassard]

OK, here is my ICETree test bed, so to speak.

Tried a few things, still not selecting the neighbour point next to index 0.

[Daniel Brassard]

OK, I am getting somewhere with this ICETree. It works like this:
* select a point index in the array (for this example, I selected index 3000),
* find in the array all the points in the array that are some distance apart from the selected point (controlled by the epsilon value, in this example 0.26),
* give me the index array of those points,
* select those points in the array.

So if I feed manually the points in the build array for the polygon description in the correct triangle order, I get some polygons at the correct location of the surface.

Now to figure out how to order those points automatically!