Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 


Submitted by Jason Wood, posted on February 05, 2001




Image Description, by Jason Wood



This is my first IOTD. It shows some 2D meshes generated using the technique of incremental Delaunay Triangulation using my test app. You can obtain an interactive version of this app from http://www.geocities.com/forwardnullinfinity/DT_page.html. It will allow you to see 2D meshes of the entire WingDings font set under Windows. These meshes are generated solely from the contour info (points, edge segments) contained in the WingDings.TTF file.

On the tech side, I use a variation on the Half-Edge Data Structure to manipulate the topology of the mesh. I also use a novel technique (as far as I know, 'cuz I haven't seen it mentioned anywhere in the literature) to generate the constrained edges once the initial unconstrained triangulation is made.

After messing around with other 2D mesh-generation techniques, I found incremental Delaunay to be the most elegant approach.

Jason Wood
www.geocities.com/forwardnullinfinity


[prev]
Image of the Day Gallery
www.flipcode.com

[next]

 
Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
The Wolf

February 05, 2001, 02:26 PM

very nice, any chance of going 3D?
This same triangulation is used in some AI path techniques

WOW! 1st post too :)

 
TheDeathLord

February 05, 2001, 02:59 PM

Great posting Jason, Especially like the skull and cross bone wingding, wait a minute those are all wingdings, anyhow very nice images, I'll have to talk to you later

-Ira

 
morgan

February 05, 2001, 04:09 PM

Nice! How hard was it to write the triangulator (i.e. how much code, how much math)?

I've wanted one for a while but never got around to coding it.

-m

 
Max

February 05, 2001, 04:32 PM

Which incremental method did you use? I did a quick survey about a month ago and Knuth's method seemed to be the best and easiest to implement.

Max

 
DragonL

February 05, 2001, 06:51 PM

Sure looks cool, but what can it be used for? Enlighten me :)

 
Jason Wood

February 05, 2001, 08:58 PM

Hi,

Thanks for the kind remarks. =)

3D Delaunay is something I have yet to do any serious research into, although the interest is there; it's still an active field of academic research and there's not as much info on it as for 2D Delaunay.

Not too much code to do the triangulator itself, maybe 1000 lines total. Math-wise, about all you need is some knowledge of graph theory and geometry to understand the basic principles.

The incremental method I used is basically the one proposed by Guibas and Stolfi in their 1985 paper called something like "Primitives for the manipulation of Voronoi diagrams" (don't have it under my nose). The next thing I would try to implement out of that paper would be the divide-and-conquer algorithm which is provably the best performance-wise (not necessarily the easiest to implement).

What's it used for? Well, it has applications in FEM (Finite EleMent) related research where scientists need to do some kind of a simulation on a building or structure and they need to turn the structure into a mesh using the best possible triangulation; also, AI pathfinding as mentioned above, computer graphics (also, the geometric dual of a Delaunay Triangulation is a Voronoi Diagram - which are widely used in CG). A concrete example of its use in CG is for generating triangles for 3D Text by simply extruding the outline and using the tris generated during the triangulation as end caps for the extruded character. Similarly, arbitrarily complex end caps for other types of extrusion objects can be generated. I'm sure one can think of other uses besides these...

-Jason

 
Jukka Liimatta

February 05, 2001, 11:40 PM

>Sure looks cool, but what can it be used for? Enlighten me :)

I am not the original author, but I would find it quite useful for comverting 2D outlines into solid areas made out of triangles.

First thing that pops into mind is to take TrueType font, and generate back+front faces, and then loft solid font objects to rotate in 3D.

I am sure people with better imagination can find alternative, and more creative uses. ;-)


--j

 
MrBenn

February 06, 2001, 06:40 AM

I used a 2d Delauney triangulation in my final year project at Uni. It was needed there to turn a soup of arbitrary samples in 3d into a recognisable surface for visualisation purposes (I basically turned the points into a heightmap - but without the regularly sampled data you normally need for heightmap rendering)...

There might be some cool applications in modelling software for the 3D triangulation I suppose, although a convex hull might do just as good a job

Anyway - good work - its nice to see someone dragging out some of the more obscure graphics algoritms for a bit of a dust now and then - now if we could do that in realtime some of those particle system demo's could get a new lease of life... ;-)

 
mbk3de

February 06, 2001, 07:33 AM

some variation of this can probably be used for generating landscape meshes with _real_ features such as roads, rivers, fields, boundaries between different vegetation types, forests (forest seen from more than a certain distance apears just like 1 big flat tree... sigh... the underestimated power of hand crafted LOD again:)

 
EGreg

February 06, 2001, 01:22 PM

Okay, folks, this one's a hooter.

-Greg

 
This thread contains 10 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.