Rudy Wuite wrote;
>One of the problems I am having with
com.sun.j3d.utils.geometry.Triangulator
>is that it can give triangles of bad aspect ratio (i.e. they are long and
thin, shape far from isosceles)
>Has anyone ever written some routines that will triangulate polygons into
triangles of better aspect ratio ?
>or
>Does anyone have any suggestions as to how I can design a solution ?
----- Original Message -----
From: Peter Kryszkiewicz
To: Rudy Wuite
Sent: Thursday, July 03, 2003 10:13 AM
Subject: Re: [JAVA3D] Triangulator and Aspect Ratio
Depends how much control you have over the subdivision of your polygons. If
you have a long thin poly, say 100 units long by 1 unit wide, either your
user or your algorithm would have to come up with the best partitioning
scheme, before you even started triangulating. This is not a trivial
problem. If you can control the distribution of points within the polygon
(even if its random) you can use Delaunay triangulation, which yields close
to ideal triangles that won't give you ill-conditioned matrices.
I wrote a couple of programs that took a TIN (Triangulated Irregular
Network) of points representing elevations, and turned them into a
triangular mesh using the Delaunay method. It makes surprisingly good
choices when it builds the face list, and when it has a choice between
'long,thin" and "fat", it always picks on the ideal side. Here is the
pseudocode;
Find the convex hull of your set of points (the corners of resulting polygon
subdivisions) or create your own (I used a 'supertriangle' that gets removed
in the end. It encloses all the points, but is not the ideal convex hull for
a long thin set. My maps were mostly symmetric in x and y)
1- initialize a triangle container (trilist), and a vertex container
(vertlist)
2- construct The supertri
3- add supertri to end of vertlist
4- add supertri to trilist
5 * for each sample point in vertlist
-- initialize an edge buffer
--- for each tri in trilist
---- calculate the triangle's circumcircle (CC) center and
radius
---- if point lies in CC
----- add 3 edges to edge buffer
----- remove tri from trilist
---- endif
--- endfor
-- delete all doubly specified edges from edgebuf (this leaves only the
enclosing polygon)
-- add to trilist all triangles formed between point and edges
* endfor
6 - remove tris from trilist that use supertri verts.
7 - remove supertri verts from vertlist.
------------------------------------------------
Your resulting triangle objects, with corresponding included edglists and
per-vertex normal lists, can then easily be arranged in fans or strips from
there.
There are quite a few polygon subdivision algorithms out there, but the one
above is probably the simplest, and I've found in practice, the most
elegant.
Hope this helps.
Peter
===========================================================================
To unsubscribe, send email to [EMAIL PROTECTED] and include in the body
of the message "signoff JAVA3D-INTEREST". For general help, send email to
[EMAIL PROTECTED] and include in the body of the message "help".
