Silhouette of a facetted polyhedra

[Dickinson, John]

Good suggestion, applicable to my situation with no edge, no vertex sharing
information (which I should have mentioned at the outset).

Thanks, I'll look into it further.
John

-----Original Message-----
From: Guenter Rote [mailto:rote at inf.fu-berlin.de]
Sent: Wednesday, April 11, 2001 11:40 AM
To: Dickinson, John
Subject: Re: Silhouette of a facetted polyhedra


"Dickinson, John" wrote:
> 
> I want to get the shadow or projection of a 3D facetted polyhedra on a
> plane.  In other words I want to project all the triangles that describe
the
> surface of the polyhedra onto a plane and union them so that I have a
> polygon possibly with inclusions or holes (e.g. project a donut onto a
plane
> perpendicular to the axis of its hole).
> 
> Can anyone point me to some code or papers that would give decent
algorithms
> for doing this (specifically the union of all the facets into a polygon)?
> 
> The goal of this is to determine the centroid and area of the resultant
> projection.  Is there a way to do this without building the projected
> polygon first?

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.

Possible improvements may depend on the data that you have.
Is it a topologically complicated polyhedron with relatively few faces,
such as a tree or a gutter? Or even with topological inconsistencies/
self intersections due to data errors?
Or is it a relatively smooth surface with thousands of triangles,
like a donut?
In that case it might pay off to concentrate on those edges that
have a supporting light ray which does not (locally) penetrate the
surface, the "contour" edges.



-- 
G"unter Rote               (Germany=49)30-838-75150 (office)
Freie Universit"at Berlin                    -75103 (secretary)
Institut f"ur Informatik       FAX (49)30-838-75109
Takustrase 9                       (49)30-84108844 (home)
D-14195 Berlin, GERMANY  electronic mail: rote at inf.fu-berlin.de

-------------
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.