Silhouette of a facetted polyhedra

[Dickinson, John]

More unfortunately for me is that I don't have neighbourhood information for
the model and in fact never did.

I am working with a non-convex polyhedra, described by a list of triangles
described by their vertices.  No shared edge or vertex information exists,
the polyhedra could potentially have holes/missing facets, as well as assume
shapes like donuts with holes through them.

Initial attempts to address this problem can be off-line (non-real time)
though.

Kind of a sticky problem.

So far the best suggestion for my particular set of circumstances came from
Guenter Rote 
with "The simplest thing to suggest is a planesweep of the projection by a
vertical plane with increasing x-coordinate, maintaining the intersection
intervals with each triangle.
This works for an unrelated collection of triangles. You can accumulate the
area and momentum that are needed for the centroid as you go. There are more
advanced methods for computing unions of triangles, but they are probably
not good for practice."

Still non-trivial to implement but not too costly for pre-processing.
John

-----Original Message-----
From: Lutz Kettner [mailto:kettner at inf.ethz.ch]
Sent: Wednesday, April 11, 2001 1:44 PM
To: John.Dickinson at nrc.ca
Subject: Re: Silhouette of a facetted polyhedra


Hi John,

Do you still have neighborhood information for the facets? An
approach using contour edges might speed up things. I implemented
a still simple sweep line algorithm for my thesis to compute the
silhouette of polyhedral surfaces (my name for your problem ;-).
If you are interested, you can check out my thesis

  Lutz Kettner. Software Design in Computational Geometry and
  Contour-Edge Based Polyhedron Visualization. PhD Thesis, ETH Zürich,
  Institute of Theoretical Computer Science, 148 pages, September
  1999.

from my web page

  http://www.cs.unc.edu/~kettner/pub/

Unfortunately for you, no sources released.

Best regards,

Lutz

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.