Triangle Mesh Delauney

mathieulesourd's picture

Hello,

I am trying to get similar effect (http://www.liambrazier.com/) using Delaunay triangle algorithm, do you any shader or filter that could give me similar result ?

Thanks.

Mathieu

gtoledo3's picture
Re: Triangle Mesh Delauney

The voronoi and delaunay calculations of a series of points are related, but not the same. "The Delaunay triangulation is a triangulation which is equivalent to the nerve of the cells in a Voronoi diagram, i.e., that triangulation of the convex hull of the points in the diagram in which every circumcircle of a triangle is an empty circle (Okabe et al. 1992, p. 94)."

This is a good applet for immediately seeing the difference:

http://www.cs.cornell.edu/home/chew/Delaunay.html

Make some points with the voronoi, then flip to delaunay calc.

This is reasonably quick, because you're making the points yourself as you go along, not performing a calculation on a large number of preset points (or points that are moving every frame). No image analysis is happening either.

With those pictures, I don't necessarily think that there's delaunay calculation, or filtering going on, I think there are probably just some aesthetic sensibilities that are reminiscent of it. It looks more like deliberate placement and coloring of triangles.

In general, a delaunay calculation is fairly slow. There are various derivative methods that get close to working realtime, but those are sort of slow too. This certainly isn't the fastest running process, but this actually does do a pretty good job at showing the fairly slow speed of different algorithms, when performing on a set of points:

http://www.cse.unsw.edu.au/~lambert/java/3d/delaunay.html

Consider that if you're doing something like this on an image, you'll need to:

  • Be grabbing some points with OpenCV probably. You'll probably want to run an edge detection, and work over the minimum distance of steps between points pretty hard, to figure out what looks sweet for your given source.

  • Perform one of the various Delaunay triangulation methods, all of which I've found are darn slow when working "the right way". You might have do some kind of thing like process the image in chunks, highly downsample it (1/4-1/8 res?) before running through CV, etc., if it needs to look like some kind of realtime effect. Being heavy handed with thresholding out your image will probably help generate less points, which will help things look faster, and be more related to whatever is in the foreground.

  • Use the point data to render triangles.

  • You'll need to sample pixel average info to roughly associate with the color of your triangles with what's on top, so that you aren't just painting a bunch of triangles that are unrelated in color.

I think you could probably rig something like this, but I'm unsure how well it would work realtime. You may have to take some real heavy liberties, to the point where you could call it delauney triangulation, but it's like when a restaurant stacks up a bunch of cold veg slices and calls it a "lasagna".

You might want to start with something like just drawing triangles using whatever coordinate points various OpenCV processes pump out, and see what you get. From there, you could probably see how far you need to go with regrouping/sorting the numbers to draw the triangles where you want them to be for the look you need.

I noticed that K2D has a great patch (the whole patch is really great), that performs a Delauney triangulation on some of it's input data, and is fairly quick, but it's not really having to do it every frame either. Maybe someone @ kineme could give some insight on that triangulation schema if it seems applicable.

Another thought, after looking at the images, is to use something like a Crystallize filter, or some kind of Worley Noise shader, but that's not exactly the same thing either.

benoitlahoz's picture
Re: Triangle Mesh Delauney

You should have a look at the poly2tri lib : http://code.google.com/p/poly2tri/

I made an implem you can see at : http://vimeo.com/32904669

I should make it available soon, but there are some bugs I have to resolve.

gtoledo3's picture
Re: Triangle Mesh Delauney

(mild point out that constrained delaunay isn't the same as delaunay, it's the kind of fast cheat I was suggesting. Good head's up on that.)

benoitlahoz's picture
Re: Triangle Mesh Delauney

In fact poly2tri is using a sweep-line algorithm for Constrained Delaunay, that results really fast (about 20 fps for a 640x480 video running at 30fps, after performing the OpenCV contours). But the OpenCV Delaunay (not constrained) is quite fast too. This video : http://vimeo.com/32836134 , is a screenflow capture with contours, convex hull, bounding box and Delaunay calculation. It's running at around 15 fps with a full 640x480 video (30fps).

The only bug in poly2tri is that some points sequences are crashy (eg. 3 points on the same line). Its conceptors, who are really kind, are working on this.

gtoledo3's picture
Re: Triangle Mesh Delauney

Ah, cool. To clarify, when I was talking about Delaunay=slow, I was thinking about a resolution of detail where you could resolve facial features, etc. When I was talking about "how to speed it up" with thresholding, edge algo, etc., this is basically right along the lines of what I meant, except w/out the color analysis/coloring of triangles.

How does it work, are you making a processor patch that takes in a bunch of points, and outputs the sorted points, or does it have to work directly on an image feed? It's nice...Does it just work on 2D data, or 3d as well?

gtoledo3's picture
Re: Triangle Mesh Delauney

Oh, I see it works w/ image. You might consider just processing a data set of keyed or indexed data from one patch to another - so one would process data and get the convex hull, the next would delaunay it, if desired, etc.

benoitlahoz's picture
Re: Triangle Mesh Delauney

You're right. These patches are of no use for me for the moment, as I only want to get the Delaunay of an OpenCV contour. Embedding everything in a single patch prevents having to create new specific arrays of vectors each time, which I guess is better for performance.

Unfortunately it is not working in 3D but the CGAL lib could do that I guess. It seems difficult to implement though. But it would be easy to add a Z parameter which would deprnd of luminosity or alpha for example. I'll think about it ! Thanks.

gtoledo3's picture
Re: Triangle Mesh Delauney

...and you're right :-)... probably at least! I agree with what you mean about the fact that it tends to be way easier/more efficient to get good performance with everything inside of one patch. If the contour grabber is really good, why not, I guess :-)

You might be able to pass everything as a GFList instead, or forget about converting to structure between patches, and output the raw data from one patch to another as a virtual or custom type. I don't know how much speed would be gained, but some, I think. I don't know the code you're working with exactly, but another cool idea might be to id the blobs.

Delaunay on 3d data sets usually isn't handled quite the same, or what works for 2D won't for 3D (as you already know).

Is the patch available? Would you mind if I checked it out? I'd be happy to help however I could as well, and if I do anything worthwhile, for you to feel free to re-integrate into your project as yours.

On another note, I was running a realtime voronoi on some points gathered from cv/iSight cam (image attached)... I can't remember what algo I was using (I was trying a few), but probably just CV Canny? I can sorta see where "I" am(kinda the middle where the voronoi parts are bigger), where my back wall was really bright(the left side), and where my room was darker (the right side). This is actually just using OpenGL to draw the voronoi, and not any kind of sorting algo at all, so it's pretty fast.

PreviewAttachmentSize
v.png
v.png91.54 KB

benoitlahoz's picture
Re: Triangle Mesh Delauney

The thing is that I'm working with the standard API, because I didn't take the time to involve in the Skanky SDK :-/

'ID-ing' the blob is my next step, but it means implementing camshift, or the cvblob lib, which is not as easy as it seems. Someone by here wrote that he was working on it. Waiting for news.

Your Voronoi is great, I wish I could make a GPU constrained Delaunay (with OpenCL may be, so I can output the triangles to my Box2D plugin, which was the first purpose of this OpenCV plugin).

I would be glad you help on this plugin. I'll publish the whole Carasuelo OpenCV plugin these days. I can post the source to your mail, please write at : benoit (dot) lahoz (at) carasuelo (dot) org and I'll send it to you.

It has a big bug with the poly2tri library : the lib doesn't remove itself collinear points and crashes when it find some. It happens generally on the edges, so I need to make a vignette when working with the webcam for example. It's working great with a Kinect/shadow tracking image, though.

Another thing : the plugin makes QuartzCrystal crash... :-( Don't know why and didn't take the time to check.

[edit : it WAS making Quartz Crystal crash ! Now it seems that it works well :-)]

PreviewAttachmentSize
Delaunay01.jpg
Delaunay01.jpg71.9 KB
Delaunay02.jpg
Delaunay02.jpg56.25 KB
Delaunay03.jpg
Delaunay03.jpg211.87 KB

gtoledo3's picture
Re: Triangle Mesh Delauney

I understand...

On the id-ing, I have some ideas but, then, I also am kind of doing this as work, on the SIDE of work :-) It might just be able to be done with some clever openGL programming. For instance, see the attached pic - I'm running a voronoi process, and normalizing the color results within the tracked blob, so that body parts kind of have an ersatz coordinate map (and the medial axis is somewhat defined as well). I could probably be getting some better results/be able to run some different process with a higher bit depth source image - using the kinect tools depth map, which is 8 bit.

I think if I monitor the middle position, or run a coordinate texture over the entire render space, and monitor what the overall pixel value is for each mask, it should be possible to id ok, and I think the past frame comparison might even just be able to be done with a feedback loop.

I'm most interested to see about hammering on the bugs, adding some new features if I can, and if either of us benefit, awesome.

Nice pics by the way.

PreviewAttachmentSize
shader.jpg
shader.jpg29.57 KB

benoitlahoz's picture
Re: Triangle Mesh Delauney

Sorry for the private message...

Hi George, I've sent the source on your mail but have no news from you. Did you receive it ?

Scratchpole's picture
Re: Triangle Mesh Delauney

This is looking great guys, working on a project with a very similar aesthetic at the moment as well. Going the handmade route: lots of tooing and froing from AI to wings3d and then into qtz....Look forward to seeing further results.

Scratchpole's picture
Re: Triangle Mesh Delauney

See this for a great implementation! http://vimeo.com/30611196

comboy's picture
Re: Triangle Mesh Delauney

Hello, I wonder if it is possible to download the composition?

gtoledo3's picture
Re: Triangle Mesh Delauney

I'd seen that, but it seems like it is still processing a still image and the user needs to edit stuff to get it looking sweet. If that's the bar, that could be achieved in QC similarly. The vid clip one isn't that accurate... I guess it's thresholding luminosity and placing triangles pretty liberally. Might still be cool!