erich@eye.com ( Eric Haines) (09/06/90)
(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... ;-)
ekalenda@cup.portal.com (Edward John Kalenda) (09/07/90)
Sorry to be a poop Eric, but my boss at Calma, Steve Hoffman, told me about the "points on the ray are above the ray" thing in 1981. He claimed someone told HIM several years before. I think it's one of those things that just need to be attributed to the anonamous coder. Ed ekalenda@cup.portal.com
zap@lysator.liu.se (H}kan Andersson) (09/07/90)
erich@eye.com ( Eric Haines) writes: >(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" > 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). /* Eric blatheres on.... */ >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... ;-) As I Think I Posted earlier, this is somewhat similar to my own approach in getting rid of special cases: Assume we are testing for a ray along X axis... For all line segments, swap 'em, so it's "first" point is upwards (Have a lower Y coordinate). Then, for each segment, test if the point's Y > firstY. If not, discard (This, in essence, is a version of Eric's idea, only mine :-) then, check if Y <= lastY. If not, discard. IMPORTANT ISSUE HERE is that I actually CARE about the 'second' point of the line, and include it in the check, thats MY way of getting rid of problem of a corner pointing downwards: It will yield 2 intersections, Eric's method yields none. No big Deal, really.... after this simple boundstest, it's time for the dreary math on checking if the intersection is on POSITIVE X, i.e. if X > firstX && X > lastX, discard, and last but not least, check the real intersection with som math (Left as an exer- cise for the reader :-). OBTW, fr'gor! FIRST, you check if (LastY - Y) * (FirstY - Y) is > 0. If so, discard. All for now. "Zap" Andersson
erich@eye.com ( Eric Haines) (09/07/90)
In article <33619@cup.portal.com> ekalenda@cup.portal.com (Edward John Kalenda) writes: >Sorry to be a poop Eric, but my boss at Calma, Steve Hoffman, told me >about the "points on the ray are above the ray" thing in 1981. He claimed >someone told HIM several years before. > >I think it's one of those things that just need to be attributed to the >anonamous coder. Oh, well, at least I can claim to be the first to publish! Sadly enough, the word still hasn't fully percolated out. The latest Foley & Van Dam (& Feiner & Hughes) says on page 34: "Next, choose a ray that starts at the test point and extends infinitely in any direction, and that does not pass through any vertices". Page 339 makes reference to "intersections at vertices" being a "special case". Passing through a vertex is still considered to be a problem (even though it isn't). It's this kind of thing that makes me happy to see books like "Graphics Gems" come out. Letting the world know about the little tricks of the trade saves us all a lot of time and replication of effort (I sure wish I had known about the "above the ray" trick in 1986 - it would have saved me hours of struggle). Eric Haines
peter@ficc.ferranti.com (Peter da Silva) (09/10/90)
In article <33619@cup.portal.com> ekalenda@cup.portal.com (Edward John Kalenda) writes: > Sorry to be a poop Eric, but my boss at Calma, Steve Hoffman, told me > about the "points on the ray are above the ray" thing in 1981. He claimed > someone told HIM several years before. > I think it's one of those things that just need to be attributed to the > anonamous coder. Another of those obvious techniques like the XOR-cursor. Good thing nobody patented *this* one... -- Peter da Silva. `-_-' +1 713 274 5180. 'U` peter@ferranti.com
robert@texas.asd.sgi.com (Robert Skinner) (09/11/90)
In article <KPS5FNC@xds1.ferranti.com>, peter@ficc.ferranti.com (Peter da Silva) writes: |> In article <33619@cup.portal.com> ekalenda@cup.portal.com (Edward John Kalenda) writes: |> > Sorry to be a poop Eric, but my boss at Calma, Steve Hoffman, told me |> > about the "points on the ray are above the ray" thing in 1981. He claimed |> > someone told HIM several years before. |> |> > I think it's one of those things that just need to be attributed to the |> > anonamous coder. |> |> Another of those obvious techniques like the XOR-cursor. Good thing nobody |> patented *this* one... |> -- |> Peter da Silva. `-_-' |> +1 713 274 5180. 'U` |> peter@ferranti.com I didn't see any smiley's after this one Peter. I'm sure that many readers don't realize that the XOR-cursor in hardware *IS* patented. ... and that's not the only obvious technique that this particular company has a patent on. Robert Skinner robert@sgi.com Watch out where the Huskies go, and don't you eat that yellow snow. - Frank Zappa
bruceh@sgi.com (Bruce R. Holloway) (09/12/90)
In article <1990Sep11.163420.13592@odin.corp.sgi.com> robert@sgi.com writes: > >In article <KPS5FNC@xds1.ferranti.com>, peter@ficc.ferranti.com (Peter >da Silva) writes: >|> In article <33619@cup.portal.com> ekalenda@cup.portal.com (Edward >John Kalenda) writes: >|> > Sorry to be a poop Eric, but my boss at Calma, Steve Hoffman, told me >|> > about the "points on the ray are above the ray" thing in 1981. He claimed >|> > someone told HIM several years before. >|> > >|> > I think it's one of those things that just need to be attributed to the >|> > anonymous coder. >|> >|> Another of those obvious techniques like the XOR-cursor. Good thing nobody >|> patented *this* one... > >I didn't see any smiley's after this one Peter. I'm sure that >many readers don't realize that the XOR-cursor in hardware *IS* patented. > >... and that's not the only obvious technique that this particular >company has a patent on. This thread is a riot. My old boss at Calma, Joe Sukonick, patented the XOR-cursor technique based on work he did around 1974, when I went to work there. I remember meeting Jim Clark for the first time around 1979 in front of Stacey's bookstore in Palo Alto before he became famous for the Geometry Engine. He was married to a friend of mine from Calma (whom we were all in love with!) & said he didn't think Joe's patent was valid because it wasn't original. I agree with him. One of the things the patent says is that XOR works because it is "idempotent". Joe had a Ph.D. in math from MIT & liked to use words like that, but I thought AND & OR were idempotent & XOR worked because it wasn't! What you need is any operation that can be undone, or inverted, like ADD, say. (What is XOR but an ADD without carry?) Anyway, the patent is now owned by Cadtrak, a corporate shell whose charter is to sue everyone under the sun over that patent. Last I heard, Western Digital was going to take them to court to overturn it. Now as to the "points on the ray are above the ray", this is really the same as the idea of half-open intervals which has broad usage in computer graphics. When you point-sample a polygon, this is how you make sure that rectangles of area m*n hit exactly m*n pixels, even if they lie on your sample grid. When I was just a kid at Calma, I wrote two programs that used that idea. One was a program to cross-hatch concave (and convex) polygons for making plots of overlapping layers on ICs. Another was a program which intersected arbitrary closed polygons with each other. This was an application program written in Calma's GPL which was used to calculate the capacitance between layers of a chip, by finding the areas of all the overlaps. Both of these algorithms needed to use the half-open idea to take care of the corner cases. I left Calma in 1976, too inexperienced to realize what a singular place it had been. After the ownership changed, most everyone scattered to the four corners of the globe. Later, I actually had a contract job working for Cal & Irma Hefte, the founders of Calma. Cal passed away some years ago-- he seemed to me to be a lot like Willy Loman in "Death of a Salesman". He told me "people are the most complicated & interesting things in the world". Mrs. Hefte and her daughters have a flower shop on Blossom Hill Rd. A genuine Silicon Valley story! (There's a lot more.) Regards, bruceh (apricot eater from way back)
elf@dgp.toronto.edu (Eugene Fiume) (09/13/90)
In article <1990Sep06.124709.996@eye.com> erich@eye.com ( Eric Haines) writes: > >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... ;-) If you were at the SIGGRAPH Bowl, you may remember that Alain Fournier has already claimed a patent on all calculus in hardware. That, unfortunately includes the JCT. Tread carefully. -- Eugene Fiume, Dynamic Graphics Project Department of Computer Science, University of Toronto elf@dgp.toronto.edu, (416) 978-5472