triangle C++ wrapper / 2d mesh & delauny

resources
#1

I just discovered this c++ wrapper to the “triangle” library:

http://www.compgeom.com/~piyush/scripts/triangle/

and I have to say that it works really well - I’ve used triangle before
but it’s a bit of a pain, since it’s c style code, and this is a c++ wrapper that use stl to do mesh generation / delauny etc for point sets. I’m using it now and super happy about it…

a couple of notes, I didn’t use the makefile, so I threw the code into a project. I had to put these compile defines into the code (at the top of triangle_impl.hpp)

  
  
#define REDUCED  
#define ANSI_DECLARATORS  
#define TRILIBRARY  
#define CDT_ONLY

this is an example of drawing the delauny triangulation of a vector of particles:

  
  
Delaunay::Point tempP;  
vector< Delaunay::Point > v;  
  
for (int i = 0; i < particles.size(); i++){  
	tempP[0] = particles[i].pos.x;  
	tempP[1] = particles[i].pos.y;  
	v.push_back(tempP);  
}  
  
ofSetColor(0x444444);  
Delaunay delobject(v);  
delobject.Triangulate();  
  
for(Delaunay::fIterator fit  = delobject.fbegin();  
						fit != delobject.fend();  
					  ++fit){  
  
	for(int i =0; i < 3; ++i){  
  
		int pta = delobject.Org(fit);  
		int ptb = delobject.Sym(fit,i);  
		ofLine(particles[pta].pos.x, particles[pta].pos.y, particles[ptb].pos.x, particles[ptb].pos.y);  
		  
	}  
}  
ofSetColor(0xffffff);

take care!!
zach

#2

also interesting :

http://www.cs.umd.edu/~mount/ANN/

I was using delauny to optimize particle-particle interaction (ie, particles only exerting a force on their nearest neighbors) – this library calculates nearest neighbors quickly… gonna give it a try too.

  • zach
#3

I’ve been using ANN for some time and it works well, but the biggest problem with it is that it’s not dynamic. AFAICT, you have to create and destroy the entire KD-tree if a point moves. I would love to be wrong about this, but I’ve looked over the docs and source code quite a bit and unfortunately don’t think I am. I have thought about hacking it but haven’t found the time.

OTOH, there is Breve which has this kind of thing built-in http://www.spiderland.org/node/2717. Any other ideas about dynamic particle-particle interaction? There’s the BSP tree from ODE as well. Unfortunately, this stuff doesn’t scale well on the CPU-side beyond about a few hundred objects.

Another possibility is the use of fields, which is really only useful in 2D. On the GPU is is trivial to simulate large (> 1000x1000) field. If particles interact with the field, the field can act as a mediator between particle-particle interactions. To do this right though you need unclamped floating point textures, but recent hardware supports this pretty well, so it’s not such a big deal.

Also…
For Delaunay and Voronoi, I’ve been using CGAL http://www.cgal.org/. Their code is actually quite fast for what it’s doing. I can do hundreds of points in Delauany/Voronoi diagrams in real-time. In 3D, I can do about 100 in a Delaunay/Voronoi Diagram in real-time. The one issue you’ll find with CGAL is the over-the-top-but-actually-necessary use of templates. Reading their papers on the CGAL kernel design is quite enlightening. What’s really interesting about CGAL is the Exact_predicates_inexact_constrctions kernel, which exactly follows geometric axioms in the analysis of point locations but speed up the actual geometric constructions with less but still really excellent precision. With DT/VD, having this capability is essential in handling edge cases where there might be 3 or more colinear points (a condition that is degenerate in a triangulation). CGAL handles this quite elegantly, but the code is a bear to get started with due to templates.

Some images:

#4

trimesh2 compares pretty well I think …
http://www.cs.princeton.edu/gfx/proj/trimesh2/

#5

wow nice –

I didn’t know that about ANN –

I’m mostly doing 2d stuff, and I’ve always done hand done binning, and can get about 800-1000 particles bouncing, ie:
http://tmema.org/messa/messa.html
http://tmema.org/messa/img/messa-jaapso-…-287015.jpg

with triangle++ and just doing particle particle interaction across the meshes I can get about 6000 moving and repelling, etc in realtime, the bigger burden is in optimizing my physics so that there is less calculation. it can be optimized a bit more. I’ll post what I’m doing shortly -

graphics card, gpu stuff is interesting, as I was working on this, I thought that either (a) threading or (b) gpu would be ideal. I’m going to investigate and post what I find out.

thanks for the links!!

take care,
zach

#6

Starting to catchup on this thread love these libs - this looks great. I know that this is way simpler compared to those libraries but I like the explantation.

http://www.shiffman.net/2006/04/07/optimize/

I have been working this Zach’s Opensorcery example of finger tracking, video-here. I want to learn more about this and analyzing contors/lines and shapes.

http://www.cgal.org/ looks really interesting, reading now.

#7

oh snaps ! nice video -

I have better finger tracking, will upload it in a sec. it does better job of line fitting and uses some metric to detect false positives…

we were trying to figure out what to do with it, I built a funny middle finger based animation. someone suggested fake fingernails.

I’m also doing some new magic tricks w/ a class that’s working with a magician in new york (marco tempest - check him on youtube). we’re hacking on some different opensourcery type tricks. our website (which is most pixel processing type stuff so far) is here:
http://a.parsons.edu/~magicplusplus

  • zach
#8

CGAL is great for what it is. I really like the fact that people researching computational geometry are the ones writing and using it. As a case in point, CGAL is about to get periodic triangulations, which AFAIK, no other software (at least public domain software) has. This was used recently to prove the existence of the ever elusive Higgs Boson. Seriously … CGAL == Nobel prize [1]

That said, the functionality it contains is not always suited for media arts purposes. So far, I’ve only found the 2D and 3D triangulations / Voronoi packages to be useful. If you want another type of voronoi, they also have voronoi of line segments and higher-order voronoi (haven’t tried but it could be interesting). I posted a video of a dynamic 3D Voronoi yesterday (http://www.vimeo.com/877882 ). I have tried their isosurface package and it is super slow (but also super accurate).

Here’s a link to their research on tiling periodic spaces as well as spherical and hyberbolic geometries (I can imagine both of these being very very useful for media arts projects): http://www-sop.inria.fr/geometrica/team/Monique.Teillaud/other-geometries/

From a recent email on the CGAL list
[1] Geneva, April 2008

The Large Hadron Collider Together With the CGAL Periodic Triangulations
Prove the Existence of the Higgs Boson

The Higgs boson was a hypothetical massive scalar elementary particle
predicted to exist by the Standard Model of particle physics.
Until yesterday, the Higgs Boson was the only Standard Model particle
not yet observed. The proof of its existence is crucial to explain how
otherwise massless elementary particles still manage to construct mass
in matter.

What turned hypothetical existence in reality is the combination
of (i) the photon collisions observed in the recently inaugurated
Large Hadron Collider (LHC, http://en.wikipedia.org/wiki/Large-Hadron-Collider )
together with (ii) the Periodic Triangulation package of CGAL, which allows
to compute Delaunay triangulations of toroidal spaces in order to apply
finite difference simulations without dealing with artificial boundary
conditions.

“We knew that hardware alone, buried in a circular tunnel under the Alps,
and combined with a 128K triple-core processor grid, simply wouldn’t do
the job,”, said Irene Eneri, the LHC project leader, “What it additionaly
needed were cleverly designed algorithms for complex shapes, and what we got
from the folks of the CGAL project was beyond the keenest expectations
of everybody – even of the project officer of our EU funded Hicks project.”

The downside of this breakthrough result is that the PhD student who worked
on the periodic triangulations stopped working, telling everybody, that whatever
he still finds out during his career is irelevant, as he expects to get the
Fields Medal in about 9, and the Nobel Prize for Physics in about 32 years.

Champagne !!! (Higgs)

The directors,

Robert Aymar (CERN), Andreas Fabri (GeometryFactory), Sylvain Pion (cgal.org)

#9

Ohhh man wish I was there for that class, I need to come visit, miss parsons. I would love to check out the new finger tracking. I’m working on something I post soon.

Thanks T

#10

Hi Zach & Vanderlin,

Any chance u guys can release an example code of your finger tracking?

Would love to have a look at it!

#11

there is finger tracking in this code:

http://thesystemis.com/opensourcery/

but I’ve been working on a better system based on similar concepts but more adjustable.

this code is based of of earlier version of OF and may feature some modification of the contour finder.

I’ll try to post a 0.05 version soon if I can - todd may have the finger stuff from opensourcery in quicker to thrown in format.

hope that helps!
best,
zach

#12

Hey fellas,

I am bringing this thread up again because I am currently trying to figgure out which libs to use. I want to do 2D trinagulation for concave shapes and tried CGAL so far which works fine but is pretty annoying to use since it is way too powerful for what I want to do. I think triangle library looks really promising especially with the c++ wrapper. did ánybody try to triangulate concave shapes with it and maybe has an example? that would be super cool!

PS: I am also aware of Pat Longs ofxDelauney addon but as far as I can see its pretty basic and only supports convex shapes?

#13

Hello Moka,
I’m also trying to find the right tesselation / triangulation library. After looking at other solutions like CGAL (needs boost - really not lightweight), GTS (some compile problems), GlutTesselator (too mush “slivers”), … I tried Triangle++ and for what I understood (correct me if I’m wrong) this wrapper only wrap the Delaunay part of Triangle…

Of course, you could use just Delaunay and test every triangles to see if it’s inside the polygon but I don’t really like this solution and it’s not going to produce a good mesh enough for what I’m trying to do! Actually it really depend on what kind of mesh you want. A “raw” Delaunay triangulation without any refinement, constrained or adaptive method produce a lot of slivers in your mesh wich is not always wanted! It’s a bit better than what you get with gluTesselator but if you have any plan of animating or “exploding” the mesh, forget it that’s not the solution you are looking for!

Here’s some pictures from Triangle website to illustrate what I mean by slivers and “bad mesh”, this is what you will get if you use simple delaunay:

But … Triangle is mush more powerful than just delaunay triangulation, actually it’s also a very good mesh generator but the C++ wrapper doesn’t cover this part. Look how pretty the same concave polygon with holes is triangulated using their mesh generator :

This is a good mesh!!! :slight_smile:

But… as there is always a “but”! I’m getting a lot of problem to understand how the C library works… As zach said at the beginning of the thread you have to add a serie of define to make it work and one of this define is needed for the mesh generator… and I got a lot of errors if I don’t defined it:

  
  
#define CDT_ONLY  
  
/*   Define the CDT_ONLY symbol to eliminate   */  
/*   all meshing algorithms above and beyond constrained Delaunay            */  
/*   triangulation; specifically, the -r, -q, -a, -u, -D, -S, and -s         */  
/*   switches. */

I’m not sure if we need to continue this in another thread or not, but if someone could help a bit I would love to make an easy C++ wrapper for this Mesh generator part of Triangle.

Does someone have understood how those “switches” work or did any body succeed in compiling the library without this "CDT_ONLY’ define?

Any advice is welcome!

Simon.

#14

By the way,

Please note that although Triangle is freely available, it is copyrighted by the author and may not be sold or included in commercial products without a license.

…

Tomorrow I’m going to give a try at Trimesh at least this one is GPL … I’ll post what I’ll found here!

#15

I’ve used Triangle, and spoken to the author of the library about a license. As long as your application isn’t distributed and sold, you don’t need a license. In fact he was very helpful and keen to see the library used and see the results.

#16

well I actually ended up writing my own wrapper for gluTesselator and it works just fine.- I also looked up benchmarks and gluTesselator seems to be one of the best in terms of speed.- It also supports 3D which is a big plus.

It actually would be great to have it in the OF Core.- What I basically did is that instead of drawing the triangulated mesh directly, it simply gives you a vector of the points so you dont have to recalculate everything every frame.

#17

Hehe!
I also wrote an ofxTesselator based on GLU but now that I’ve seen those nice adaptive meshes I cant use it anymore! :slight_smile:
Actually I really need to animate triangles by triangles and look at those ugly triangles :

Tesselation with gluTesselator:

[attachment=1:2r1qllw6]tesselationGLU.png[/attachment:2r1qllw6]

Tesselation with Delaunay:

[attachment=0:2r1qllw6]tesselationDelaunay.png[/attachment:2r1qllw6]

The triangles are too long to be use for any particles animations or any physics based stuffs…

#18

Maybe you know this already but for the tesselationDelaunay.jpg one you can remove the exterior triangles by doing a point in poly test for the center of each triangle vs the outline of the letter.
If the center lies outside of the letter you can discard the triangle.

also another way to get nicer triangles is to do a polyline simplify on the shape so that long straight lines use just two points. There is code for this in ofTrueTypeFont.cpp.

#19

Thank you theo,
Actually I quickly put a picture without doing this polytest because I just wanted to show the “long slivers” problem… Removing those triangles won’t resolve this problem, it will still produce a “bad mesh” as I explained before… I think that what I need is a refinement algorithm…

#20

Ok, so today I tried to mess abit with Trimesh, wich looks great. It has a method called “remove_sliver_faces” but maybe I’m not using it correctly because it doesn’t remove anything. I spent to much time trying to make it work so I had to find another solution…

Anyway here’s the quick and dirty method I found for refining my mesh. It’s not very efficient but well it’s doing the job pretty well for what I need:

So here’s the raw mesh produced with a delaunay triangulation:

[attachment=2:1v6lfhoa]tesselation0.png[/attachment:1v6lfhoa]

(Because of size / compression You will have to zoom on the picture to clearly see the triangles.)

The dark areas of the mesh are small sliver triangles that will make my animation look very bad… One solution would be to add random points to the triangulation. The result is not perfect but it’s already a bit better.

[attachment=1:1v6lfhoa]tesselation1.png[/attachment:1v6lfhoa]

You can still see the slivers (dark areas near the contour), but we can again use a bit of random (I know! This is bad!). If we “spawn” some more random points just around contours points we get this :

[attachment=0:1v6lfhoa]tesselation3.png[/attachment:1v6lfhoa]

Wish is really better! With a mesh like that, you can do every particles / physics animations you can dream of!

Sorry for spamming this thread! I hope it will be useful for someone!

PS: Does a method with some constrained string (so we can control the space between every points) sounds ridiculous or not?