Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!ames!cit-vax!oberon!sdcrdcf!trwrb!wiley!cbn
From: cbn@wiley.UUCP
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited...
Message-ID: <771@jethro.UUCP>
Date: Tue, 16-Jun-87 13:09:59 EDT
Article-I.D.: jethro.771
Posted: Tue Jun 16 13:09:59 1987
Date-Received: Sat, 20-Jun-87 00:38:45 EDT
References: <948@elrond.CalComp.COM>
Reply-To: cbn@wiley.UUCP (Chris Newton)
Organization: TRW Inc., Redondo Beach, CA
Lines: 49
Keywords: ray tracing, graphics, polygon intersection
Summary: Sounds similar to a scan-conversion problem...

The problem you describe in three dimensions has a very similar counterpart
in two dimensions, if I understand your problem correctly.  A popular
algorithm for scan converting polygons in 2D performs a similar
"intersection counting" function.  First, the algorithm attempts generates
a list of the points at which the edges of a given polygon intersect with
the scan lines of the raster device.  This is similar to your calculation
of ray intersections with the object planes.

Once the list of intersections is generated, they are sorted by scan line
and the points on a given scan line are "paired up".  The pairing is
similar to your "odd-even" test, in that the space between any two pairs
should be inside the polygon (on that scan line) and can be displayed with
that polygon's color.

The problem occurs when a scan line EXACTLY intersects a vertex of the
polygon. (Sound familiar?) Depending upon the type of vertex, you either
count it as a single or double intersection.  Your
first example (if considered a 2D polygon in the xy plane) would count
as a single intersection, while your second example would count as two
intersections.  In the latter case, the resulting two intersections
would pair up and either be displayed as a point, or as nothing at all.

The way you determine what type of vertex you're dealing with, is to
examine the slope of the edges that make up the vertex.  In the 2D case,
if the y values of the edges are BOTH LARGER than at the vertex in question,
the point is a local "minimum".  Conversely, if the y values of the edges are
BOTH SMALLER than at the vertex in question, the point is a local "maximum".
If the vertex is a local maximum or minimum, count the point as TWO
intersections, otherwise count it as one.

Now, there must be a similar mechanism in the 3D world.  Look at the
equations of the planes that intersect at the edge in question and see if the
produce an edge that is a local maximum or minimum.  Your first
exanmple should not satisfy the test and should be counted as a single
intersection, instead of two.  The second case is definitely a maximum (
with respect to the vertical axis in your drawing) and should be counted
as two intersection (or possibly no intersections, depending upon
your need.)

Most good graphics texts discuss scan conversion. Maybe referring to them
will be of help.  I can recommend "Procedural Elements of Computer
Graphics" by David F. Rogers (McGraw-Hill) as a good, all-around treatment
of the subject. I've implemented several scan conversion algorithms and this
one works well.  I haven't yet done any ray-tracing, so this is postulation
of a known solution to what seems to be a very similar problem.  Good Luck.

Chris B. Newton
TRW, Redondo Beach, Ca.
cbn@wiley