4 Replies Latest reply on Sep 6, 2006 11:44 AM by Sonic2004

# Triangulation in Lingo

Hi there folks. So, are there any hidden or suprisingly obvious methods within Shockwave 3D to triangulate non-convex polygons with n sides? One form of this is called Delaunay Triangulation, but there are other methods as well. I am just about to embark on a journey to create this in Lingo (or potentially in an xTra), but I am hoping that there is already a solution out there.

Thank you for any help in advance,
David Gilardi
• ###### 1. Re: Triangulation in Lingo
there is no embedded algorithm for such things. Only the normal generation of meshes where you have to tell via lingo which three vertices have to be used for each polygon.

If you can do a xtra here, this would be great!

regards!
• ###### 2. Re: Triangulation in Lingo
Thank you for your reply Hondo. I had that feeling, but was hoping someone would tell me otherwise. Whatever I end up doing I will let you know.

Thanks again,
Dave
• ###### 3. Re: Triangulation in Lingo
Hey there Hondo. Ok, I was able to create a triangulation Xtra, but I cannot release the Xtra to the public. What I can do is say this. I used C code that was generated by Narkhede and Manocha based off of Seidel's algorithm. This can be found here:
http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html. An absolutely great resource for anyone handling 3D programming is here: http://compgeom.cs.uiuc.edu/~jeffe/compgeom/. I was able to integrate their code into an Xtra with no changes to their implementation other than linking. In general, this Xtra allows a set of points in anti-clockwise direction (reverses order if not anti-clockwise) to return a set of triangles without adding any vertices. This means that for those who are dealing with non-convex irregular polygons that are created dynamically you can send the Xtra the contour points and get traingles back that you just plugin into your faceList upon mesh generation. It is rather easy and simple once implemented and can triangulate any polygon even with holes as long as the input data is formed correctly. Unless one creates an object in an external program and imports into Director I do not know of any way to to it otherwise, especially at runtime.
Anyway, if someone takes a shot at it for public use feel free to ask me about it.

Have fun,
Sonic2004

BTW: I want to thank Narkhede and Manocha for going through the trouble to implement Seidel's alogrithm in C. From my point of view it is not trivial.
• ###### 4. Re: Triangulation in Lingo
Hi again. I noticed that the first link does not work for some reason. Go here instead: http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html#poly and then go the the link Fast polygon triangulation code.