# Delaunay triangulation / delaunay mesh

Hey there,
i want to generate a 2d mesh using a delaunay algorithm based on random points. It should look something like this: https://t3.ftcdn.net/jpg/00/91/56/90/240_F_91569022_0eajNAhuqgUjlBQDc26KXANMbscGn9Dd.jpg
So I want to be able to color every triangle individually. Also I want to be able to move the mesh, like a moving surface.
I already tried different things like the “Delaunay (2d Triangle)” - node. But I never got the result i wanted. Can anybody help me? Has anybody something like a help-file for the “Delaunay (2d Triangle)” - node? Thanks
Greetings

it should have all the information you need to do what you want.

Thanks for this link. But the problem is that this delaunay algorithm only creates lines, so i am not able to fill the triangles with a color. (right?) The “Delaunay (2d Triangle)” -node for example gives my coordinates for triangles. But somehow I am not able to handle it right…

indeed it seems the information of which points to connect to triangles is missing. maybe @darrellp has an idea here…

instead of the Triangle one have a look at the Delaunay (2d) node. it comes with a helppatch and is essentially the same as the triangle version only it returns the indices referring to the input points. if the helppatch is not enough please upload a patch where you tried to achieve what you wanted to do and point out where you fail, so we can help you with the next step…

and there’s a delauney/voronoi combo in the imagepack. it works quite like the usual ones but is a lot faster which means more points withe the same framerate :)

Been a while since I’ve messed with this stuff. I’m assuming that you want colors to range smoothly from triangle to triangle. Maybe this is wrong - if you just want to paint triangles randomly from a palette so all you need is a list of triangles, then this becomes much easier as all you need is a list of triangles. I’m assuming this smooth color change from triangle to triangle is part of your solution though.

Really, in my mind, there are two issues here. One is getting your list of triangles and which border which and the second is stepping through such a list. Sadly, the current Delaunay node of VVVV just gives you points on each triangle with no connection information. At first I thought maybe the “indices” referred to the indices of neighboring triangles, but sadly, they just give you the index of the corresponding points in the original spread which is essentially redundant info (well, the points themselves are redundant since you can just use the indices to pull out the points from the input spread).

You could theoretically get such a list with VoronoiComplex. For instance, you could start at each node, step around it’s edges recording the node on the opposite side of the edges and adjacent points in that stepping would also be connected to form the third edge of the triangle. The main problem is that you would produce many triangles more than once and you would have to recognize that which would be messy. Perhaps you could sort the result and then eliminate the duplicates. Messy, but perhaps doable.

I really think doing another C# node would be ideal and not that hard. I would probably only return 6 indices - three to index points in the original (input) spread and three to index into the spread of output triangles giving the three adjacent triangles.

But the second problem is at least as serious IMHO. Suppose I were to write such a node (and it would not be a bad idea I think). Then what? How are you going to index through all the triangles in some sort of reasonable order? It’s actually not easy. Ideally, you’d want to somehow step from one triangle to adjacent triangles giving each of them a random “nearby” color and end up visiting every triangle. I’m pretty sure that’s not actually possible as stated. I needed to do something similar once while walking through meshes for a 3D game and it was difficult. You’ll be forced to stop going from adjacent triangle and make a jump to an as yet unvisited triangle. Not only that, you’ll need to make sure that you don’t visit a triangle that’s adjacent to one you colored long ago and has a completely different color. This is all going to be difficult. My best guess would be that maybe if you assigned some original colors by stepping and then went back and averaged colors between adjacent triangles that you would eventually come to some reasonable coloration.

I guess that, in my opinion, this second step would be best handled by a C# node also. It’s probably doable by storing colors of visited delaunay triangles in spreads and constantly referencing that spread to see which triangles have been visited and what colors were assigned to them, but it would really end up being very messy. I know this isn’t much help unless you want to write some C# code to do all this, but I think it’s inherently a bit of a messy problem. I guess something that I’d probably try if I got the Delaunay info mentioned above is just walking through all the triangles without concern for adjacency and then do an averaging pass some number of times over the result. Not sure how well that would turn out, but it might turn out something like what you’re looking for.

I guess I didn’t give any definite answers here (though I think you could tease the info from VoronoiComplex with some effort). I’ll thing about adding a Delaunay node which takes a VoronoiComplex and produces the output I mentioned above.

Argh! Sometimes it pays to take a step back. I think you could just use a perlin noise function and use the position of a triangle to pull the value from the noise function. That would easily take care of the second problem of stepping through the triangles. Would that work? In that case all you need is a list of triangles which is the less difficult problem. You may “paint” each triangle three times but that’s likely acceptable. Anyway, just realized this. I feel stupid for not seeing it before!

Hey, sadly it’s been a while since my last reply. Mainly because now i have a lot of other stuff to do…anyway, thanks so much for your answers. Thanks @sebl for the tipp, i will have a look at it ;).
And thanks @darrellp for your thoughts. Actually i really just want the triangles to color randomly ;) I will think this hole thing trough again, and who knows maybe I’m going to write that C# node haha. (not really experienced in that…).
So again: thanks so much for your time, I will let you know when I have found a reasonable solution.
Greetings

i have no patch at hand, but iirc i simply connected the voronoi (or delauney) to a polygon and voilà…

now i have a patch at hand

DelauneyVoronoi.v4p (10.8 KB)

but:
those are the imagepack-nodes

Hey @sebl,
your patch seemed pretty interesting so i tried to get the imagepack working. But sadly I failed. Somehow the Delauny and Voronoi patches are missing (red). When i follow the given path to the node->plugins folder, there are no .dll files. Just the help patches. Also in the older versions of the Image pack the patches are not there because they were added later, i guess.
Can you somehow help me?

hmyes, those nodes are only available in the head of this branch
best would be to clone the repo into your packs folder, checkout the branch linked above and compie it.

my latest x64 version that works for me on 34.2_x64 with latest dx11 installed is uploaded here

Thanks again @sebl,
Now the ImagePack is working. Next step will be to let the triangle move randomly but the triangles should keep their colors. Any idea how to accomplish that? The goal is to get a colored Triangle-Polygon-Mesh with the single vertices keep moving randomly.
Greetings

hm, i did it once with voronoi (moving the whole thing and display images on the polygons) and i didn’t experience any spread swapping or similar. the polygons simply kept their order, which i guessed was related to how the opencv-code works internally. but i never had a reason to investigate deeper.

anyway, the beaviour of delauney might be quite different.

ok… after a quick look into the helppatches of both nodes. delauney behaves different (and i have no idea on how to easily sort the triangles).

render to slice is your option with Tex array renderer, you can discard everything but the color you want. There should be an easier option to do that.

DelauneyVoronoiAnimated.v4p (11.8 KB)

@antokhio this patch displays the problem and different behaviour of both nodes. i don’t know how a texArray renderer could help here?

Ok i see what you mean ;] Tex array def not gonna help here, i’m not sure about delauney,i thought it pretty same with voronoi, can’t rember the difference, but i should have an old implementation of delaunay in some project, if i find something i’ll let you know.

This topic was automatically closed 365 days after the last reply. New replies are no longer allowed.