thrapp@cod.NOSC.MIL (Gary R. Thrapp) (01/07/88)
-
I need to decompose some large (> 1000 vertices) polygons into
smaller (<= 200 vertices) polygons that our hardware can fill.
The polygons represent map coastlines so you can imagine the
effect that long coves and bays have on the shape of the polygons.
Can this decomposition be done mathematically? The goal would
be to call a routine with 3 parameters for an arbitrary size polygon:
1) number of vertices, 2) array of x components of the vertices,
3) array of y components of the vertices and have the routine fill
the polygon by filling an equivalent set of polygons each with <= 200
vertices.
If anyone has software to do this or just advice it would be
greatly appreciated. Thank you.
-------------------------------------------------------------
Gary R. Thrapp
Naval Ocean Systems Center
San Diego, CA
DDN: thrapp@nosc.mil
UUCP: {ihnp4,akgua,decvax,dcdwest,ucbvax}!sdcsvax!noscvax!thrappnelson@esunix.UUCP (Scott Nelson) (01/12/88)
in article <937@cod.NOSC.MIL>, thrapp@cod.NOSC.MIL (Gary R. Thrapp) says: > > I need to decompose some large (> 1000 vertices) polygons into > smaller (<= 200 vertices) polygons that our hardware can fill. > The polygons represent map coastlines so you can imagine the > effect that long coves and bays have on the shape of the polygons. > > Can this decomposition be done mathematically? The goal would > be to call a routine with 3 parameters for an arbitrary size polygon: > 1) number of vertices, 2) array of x components of the vertices, > 3) array of y components of the vertices and have the routine fill > the polygon by filling an equivalent set of polygons each with <= 200 > vertices. > > If anyone has software to do this or just advice it would be > greatly appreciated. Thank you. > > Gary R. Thrapp > Naval Ocean Systems Center > San Diego, CA I have a program which will decompose any polygon into optimal triangles. This may not be exactly what you wanted, but it is close and should be of interest to others. The program code follows this note in comp.graphics (for you comp.sources.wanted readers). The code assumes all screen-space transformations have already been performed and cuts the polygons into triangles optimized for drawing on the screen. It wouldn't take much to modify it to transform the polygon based on the surface normal before cutting into triangles. The code is currently being used in a research polygon renderer and has worked correctly for all cases we have fed it so far. This does not mean, however that it is perfect. All suggestions are appreciated. --- Scott R. Nelson Evans & Sutherland Computer Corporation UUCP Address: {decvax,ucbvax,ihnp4,allegra}!decwrl!esunix!nelson Alternates: ihnp4!utah-cs!esunix!nelson usna!esunix!nelson "Proofread carefully to see if you words out."