Silhouette of a facetted polyhedra

[Dickinson, John]

I hadn't thought of this but unfortunately I don't have shared edge/vertex
information available.  Good point about nonconvex polyhedra having holes in
shadows even if they don't have them in 3D.

John

-----Original Message-----
From: Tom Shermer [mailto:shermer at cs.sfu.ca]
Sent: Tuesday, April 10, 2001 6:22 PM
To: John.Dickinson at nrc.ca
Cc: shermer at cs.sfu.ca
Subject: Re: Silhouette of a facetted polyhedra


Hi John,

	the edges that are on the silhouette have a normal whose dot
product with the normal of the projection plane is zero.  (Depending on your

definition of silhouette, the silhouettes are either exactly those with
a normal with zero dot product, or a subset of them.)  The easiest
way I know of to test this is to take all face normals and compute
their dot product with the plane normal.  Then, any edge having faces with
differently-signed dot products is a "silhouette" edge.  If one keeps this
information directly in the edge data structure, we can consider this as
a coloring of the edges of the polyhedron where, say, red represents 
"silhouette" and blue represents "non-silhouette".  Then by examining a
separate list of silhouette edges, one can find connected components in the
red graph and use these to form polygons.  Decisions to throw out some
chains
can be made locally at high-degree vertices.

If the polyhedron is convex, rather than testing all pairs, find an extreme
vertex in some direction contained in the projection plane.  This vertex
will
be in the silhouette, so check the edges around it to find one that is 
silhouette.  Cross this edge and repeat at the next vertex, until you return
to the start.

If the polyhedron is nonconvex, then life is trickier.  First, one must
decide
if holes are allowed in the silhouette.  A silhouette can have holes even if
the
polyhedron doesn't.  If holes are not allowed, then one can just take the
union 
of all of the polygons that corresponding to "positive" (non-hole)
silhouettes.
["Negative" (hole) silhouettes locally do not contain the object, as in the 
silhouette in the center of a torus.]  If holes are allowed in the
silhouette,
I'm not quite sure how to proceed.

For centroid, one only needs to identify the silhouette vertices.  To
compute
area, take any point p on the projection plane.  For each silhouette edge 
(again, what these are differ depending on your definition of silhouette)
and orient it so that the polyhedron appears on the left as one walks from
tail
to the head (as viewed from above the polyhedron, where the projection plane
is 
below).  Then, compute the signed area (positive if the edge is oriented 
counterclockwise around p, negative otherwise) of the triangle formed by p
and 
the projection of this edge.  The sum of these, over all such triangles, is
the
area of the silhouette.  (no construction of polygon required.)


	Tom
	shermer at cs.sfu.ca
	
	
> From: "Dickinson, John" <John.Dickinson at nrc.ca>
> To: "'compgeom-discuss at research.bell-labs.com'" 
<compgeom-discuss at research.bell-labs.com>
> Subject: Silhouette of a facetted polyhedra
> Date: Mon, 9 Apr 2001 09:26:50 -0400 
> MIME-Version: 1.0
> 
> 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?
> 
> John
> 
> --
> -((Insert standard disclaimer here))-|--- Washington Irving (1783-1859)
----
> John Kenneth Dickinson               |   "A sharp tongue is the only
> Research Council Officer  IMTI-NRC   |    edge tool that grows keener
> email: john.dickinson at nrc.ca         |    with constant use."
> http://publish.uwo.ca/~jkdickin/     |
> 
> 
> 
> -------------
> 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.

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