Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!rutgers!topaz.rutgers.edu!brandx.rutgers.edu!webber From: webber@brandx.rutgers.edu (Webber) Newsgroups: comp.graphics Subject: Re: Point inside of polygon revisited... (It's easy) Message-ID: <278@brandx.rutgers.edu> Date: Fri, 3-Jul-87 07:27:54 EDT Article-I.D.: brandx.278 Posted: Fri Jul 3 07:27:54 1987 Date-Received: Sat, 4-Jul-87 12:58:34 EDT References: <948@elrond.CalComp.COM> <260@brandx.rutgers.edu> <1365@xanth.UUCP> <1007@elrond.CalComp.COM> Organization: Rutgers Univ., New Brunswick, N.J. Lines: 47 Keywords: ray tracing, graphics, polygon intersection Summary: actually this is enough to see some problems In article <1007@elrond.CalComp.COM>, amamaral@elrond.CalComp.COM (Alan Amaral) writes: > In article <3772@spool.WISC.EDU>, planting@colby.WISC.EDU ( W. Harry Plantinga) writes: > > Does the point lie inside or outside of the triangle? If it is very > > close to the edge of the triangle and if the angle of the edge is > > appropriate, the precision of computation needed to get the right > > answer can be surprisingly high. ^^^^^ > ^^^^^ > Please define "RIGHT"... I'm sure this problem has been suitably solved > a number of times with INTEGER math, no more, but then again I'm sure > the applicable definitions of "RIGHT" differ... RIGHT is always relative to the application. If you are attempting realistic modelling, then anything that results in a percievably different image from the intended, is WRONG. If you are doing some kind of geometric application, anything that violates the geometric properties you are assuming can mean WRONGness, e.g., you expect the answer from the intersection between x and y to be the same as between y and x (even though arithmetic on computers does not always commute) -- also, if x is isomorphic to z, then the intersection of x with y and the intersection of z with y should lead to the same answer. Many systems have deep bugs because these properties are assumed by the programmer although the implementation does not support them. INTEGER math is not magic unless you are on a machine that supports arithmetic on integers of arbitrary size in a reasonable way (perhaps a Connection machine?). Otherwise you run into problems with precision -- try and set up the rotation matrices for integer arithmetic and see what happens as you try and show that when you rotate an image full circle it comes back to the same location. Of course, all of this is probably solvable. When you solve it, please post the code :-) >> By the way, handwaving does not "an actual counter-example" make. Please >> be more specific, like supply real NUMBERS, not vague pictures. "Very >> close to the edge" and "appropriate angle" are hard to calculate... Exact counter-examples are often machine and code dependant. I would certainly say that the principles involved are not so opaque that the only way to demonstrate that there is a problem is to run an actual simulation. If a simulation is needed, perhaps it would be easier for you to supply a piece of code and the set of intersection properties you are interested in simulating and then one can address the question of does this really happen. There is alot not known about the tradeoffs involved here. ----- BOB (webber@aramis.rutgers.edu ; rutgers!aramis.rutgers.edu!webber)