Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!mips!sgi!shinobu!odin!surfside!jindak
From: jindak@surfside.sgi.com (Chris Schoeneman)
Newsgroups: comp.graphics
Subject: Re: Point in Polygon Problem
Message-ID: <1990Aug23.174650.3592@odin.corp.sgi.com>
Date: 23 Aug 90 17:46:50 GMT
References: <5990@milton.u.washington.edu> <1990Aug22.022743.4139@twinsun.com> <2018@idunno.Princeton.EDU> <1990Aug23.000651.10581@twinsun.com> <2034@idunno.Princeton.EDU>
Sender: news@odin.corp.sgi.com (Net News)
Distribution: comp.graphics
Organization: Silicon Graphics, Inc., Mountain View, CA
Lines: 63

In article <2034@idunno.Princeton.EDU> markv@gauss.Princeton.EDU (Mark VandeWettering) writes:
>>Mark came up with a smart solution for the "ambiguous ray-edge intersection"
>>(AREI) problem (anyone agrees with this name?). I like his article.
>>But his solution has a little glitch.
>
>Apply the rule I gave you blindly, lets assume we break ties by assuming 
>they are in above the point in question.  Therfore 1 & 2 count as zero 
>intersections, and 3 & 4 count as 1 intersection.  Now, on to the case
>you gave:
>
>>Consider this polygon...
>>
>>               +--------------------------------+
>>               |                                |
>>               |                                |
>>               |         D     E     F          |
>>y=0  - - o - - o----o----o - - o - - o----o-----o - - o - -
>>         A     B    C    |           |    G     H     I
>>                         |           |
>>                         |           |
>>                         +-----------+
>>
>Mark

Mark is right, of course:  the same code works.  But I feel this solution
can be stated more clearly, and make acceleration techniques more obvious.
After all, speed is what it's all about, isn't it?

    The ray interesects an edge if and only if the edge crosses the x-axis.
A vertex on the x-axis is considered above it, that is: zero is considered
to be positive.

*	If we assume 0 is positive, the answer presents itself:
*	count an edge if and only if sign(y1)!=sign(y2).

    Now we can determine a crossing very fast.  Two's-compliment (integer)
numbers of n bits can be XOR'd and then AND'd with 2^(n-1).  Non-zero
means a crossing, zero means no crossing.

    But in 3D floating point is the norm.  What do we do?  The SAME thing!
Many floating point storage schemes are arranged like so:
	+-+----------+----------------+
  MSB	|S| Exponent |    Mantissa    |   LSB
	+-+----------+----------------+
The S is the sign bit, and it gives the sign of the mantissa, i.e. the sign
of the overall number.  Like two's-compliment, zero has a zero sign bit;
it is in this sense positive.  If your floating point is stored this way,
then you can XOR and AND, just like before.  This is NOT portable, some
fp's may be stored differently.

    Some floating points have both a positive and negative zero.  (You can
get a negative zero by, say, multiplying -1.0E-25 * 1.0E-25.  The answer
has no significant digits, but is definitely negative.)  Is this a
problem?  No, a point will have a negative zero y value if it IS below
(but very close) to the x-axis.  If the other side is above the x-axis
then a crossing should be, and is, detected.

-Chris Schoeneman

	       Chris Schoeneman | I was neat, clean, shaved and sober,
    jindak@surfside.esd.sgi.com | and I didn't care who knew it.
	 Silicon Graphics, Inc. |		-Raymond Chandler
	      Mountain View, CA |		 (The Big Sleep)