Path: utzoo!utgpu!watserv1!watmath!att!occrsh!uokmax!apple!julius.cs.uiuc.edu!wuarchive!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!sdd.hp.com!decwrl!sgi!shinobu!odin!bruceh From: bruceh@sgi.com (Bruce R. Holloway) Newsgroups: comp.graphics Subject: Re: Point in Polygon; a few more comments Message-ID: <1990Sep11.231339.21084@odin.corp.sgi.com> Date: 11 Sep 90 23:13:39 GMT References: <33619@cup.portal.com> <1990Sep11.163420.13592@odin.corp.sgi.com> Sender: news@odin.corp.sgi.com (Net News) Organization: Silicon Graphics, Inc., Mountain View, CA Lines: 61 In article <1990Sep11.163420.13592@odin.corp.sgi.com> robert@sgi.com writes: > >In article , 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)