Path: utzoo!attcan!uunet!samsung!sdd.hp.com!zaphod.mps.ohio-state.edu!rpi!uupsi!eye!erich
From: erich@eye.com (	Eric Haines)
Newsgroups: comp.graphics
Subject: Point in Polygon; a few more comments
Summary: a few more points of interest
Message-ID: <1990Sep06.124709.996@eye.com>
Date: 6 Sep 90 12:47:09 GMT
Sender: Eric Haines
Reply-To: erich@eye.com (	Eric Haines)
Organization: 3D/Eye Inc., Ithaca, NY
Lines: 70

(Here's my big chance to test out our own real live news feed!  Maybe it'll
work this time...)

Mark VandeWettering writes about the point in polygon test:
>[... much talk of the shoot a ray to the right & count crossings method ...]
>Hardly my own idea.  It was shown to me by Eric Haines originally, but I 
>don't think he claims credit for it either.  Any takers?  Is it patented 
>by Unisys as well :-)?

	Anyway, having an ego and all that, I do indeed claim to be the
inventor of the "consider all points on the line to be above the line"
solution, which gets rid of those pesky special cases where vertices are on the
test ray.  I started with some very complicated special case code in 1986
which worried about whether the points were on the ray.  Months went by...
One day, looking at the code, I noticed another stupid special case that I
didn't handle correctly (something like "if the last point is on the ray and
the first point is on the ray...").  I looked at the problem again and
realized that the only property of the ray that I really cared about was that
it was a divider, not that it was a set of points forming a ray.  Eureka,
Arkansas!  Get rid of those points, and so define away the problem - no points
can lie on the ray, if we define the ray as having no points.  O happy day, it
even worked.  Anyway, it's all written up in my section of "An Introduction to
Ray Tracing", edited by Andrew Glassner, Academic Press.

	Historical note:  the earliest reference I have to the point in
polygon test is the classic "A Characterization of Ten Hidden-Surface
Algorithms" by Ivan Sutherland et al, 1974, ACM Computing Surveys v6 n1.  This
has both the ray crossing test and the sum of the angles test, plus the convex
polygon test (check if the point is inside all lines by substitution into each
edge's 2D line equation).

	Computational geometry fiends noted that the method has the problem of
being indeterminate on edges:  if your intersection point is exactly on an
edge, it's arbitrary whether the point is determined to be inside or outside
the polygon (that is, do you consider an edge crossing the point to be to the
right or left of the point, or do you want a third category, such as "on"?).

	However, there is a general consistency to the ray crossing test for
ray tracing.  If the point being tested is along the edge joining two visible
polygons (which both face the same general direction, i.e. not a silhouette
edge) and the polygons are projected consistently upon the plane perpendicular
to the ray, the point is guaranteed to be considered to be inside one and only
one of the polygons.  That is, no point will be considered within any two
non-overlapping polygons, nor will it "fall in the crack" between polygons.

	Think about it this way:  if points on the left edges of the polygon
are considered outside, then the points on the right edges will be considered
inside.  This is because we would then consider an edge crossing the x axis at
exactly 0 as being to the right of the test point.  Since one polygon's left
edge is another's right edge, it all balances out to make each point be inside
only one polygon in a polygon mesh.  Horizontal edges are treated the same
way:  if a point is actually on such an edge, when tested, the point will be
categorized as "below" the edge consistently.  This will lead it to be inside
one and only one polygon in a mesh.

	In reality, when ray tracing you very rarely get points that are
exactly on an edge, so this is something of a non-problem.  But if you really
really care about this possibility, make sure to always cast your polygons
onto the plane perpendicular to the ray (this plane is also good for
consistency if you want to get edges for Gouraud RGB interpolation, Phong
normal interpolation, etc).

	Finally, for you incredibly demonic CompGeom types: yes, indeed,
points on silhouette edges are still inconsistent.

Eric Haines
erich@eye.com

P.S.  As our patent on the 90 degree angle was successful, the pending patent
on the Jordan Curve Theorem should come through any day now... ;-)