Triangulation in Lingo

[Sonic2004]

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

[hondo3000]

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!

[Sonic2004]

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

[Sonic2004]

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:
[url]http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html[/url]. An absolutely great resource
for anyone handling 3D programming is here:
[url]http://compgeom.cs.uiuc.edu/~jeffe/compgeom/[/url]. 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.

[Sonic2004]

Hi again. I noticed that the first link does not work for some reason. Go
here instead: [url]http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html#poly[/url] and
then go the the link Fast polygon triangulation code.