Polygon Indices List
Before getting into the answer, let us first study some facts about polygon indices lists:
- A polygon indices list is a list of tuples each of which include the indices of the vertices each polygon is composed of.
- The order of indices of each polygon does not matter, so the polygon (triangle) with indices
(0, 1, 2) is the same as (1, 2, 0), (2, 0, 1), (2, 1, 0), (1, 0, 2) and (0, 2, 1). However, the normals of the first three triangles will be the inverse of the later three, that is due to the fact that the mathematical operation used to compute polygon normals cares about the order.
- A polygon indices list can not contain:
- Two similar polygons, so only one of the indices mentioned in the previous point can exist in the list.
- Each indices has to have at least 3 indices.
- The indices should be of existing vertices, so if there are
n number of vertices, the maximum index that can be used is n-1.
Generating Polygon Indices
The underlying structure used in the Find Close Points node is the KD Tree and we will be using it to generate our polygons as well. A KD Tree can provide you with the indices of the n closest vertices to a given point--Which can be any arbitrary point. If we used those indices to create a polygon where n=3 we will get the polygon indices of the triangles you wanted. if we used n=4, we will get quads and so on.
So we create a loop that takes the KD Tree that represents the vertices locations and n as inputs, a list of arbitrary vectors as an iterator and returns the created polygon indices as an output:
If we attempts to use the output directly, AN may return an error, that is because some indices might have been created more than one time, this is due to the fact that the same n vertices might be the closest to multiple arbitrary vector. So it is obvious that we have to make sure no polygon is created twice (Remember that a polygon can take multiple forms since order of indices doesn't matter).
To make sure we don't add two similar polygons, we keep track of the polygons created in previous iterations and only add the polygon generated in the current iteration if and only if it wasn't similar to any of the polygons created in the previous iterations. To keep track of the polygons already created, we create an empty polygon indices list as an input, append the created polygon and reassign the list:
Study Loops in the documentation to understand how this reassign works. We then need to check if the current polygon exist in the list of polygons we just created by appending and reassigning, this can be done by using a simple python generator:
not any(set(p) == polygon for p in polygons)
Where polygon is the set of the indices of the current polygon and polygons is the list of polygons we just created by appending and reassigning. We simply convert the polygons to sets (Because order doesn't matter, remember) and check if they are equal, If any of them is True, True will be returned and False otherwise, the not invert the boolean so that we can use it as a condition in the loop generator:
By using the condition input in the generator, we only add the polygon if all the booleans in the list is False.
And by using the loop we created, we get:
By setting the amount to four, we get quads, however, quads might not always be coplanar nor convex, so the results might be messy:
So far we have been using the vertices locations as the arbitrary vector list, and it works, but better result may come out when you use different vector lists (In my case another random vector list but with different seed):
