pelegrin@geocub.greco-prog.fr (04/09/90)
In article <2094@crash.cts.com> jcs@crash.cts.com (John Schultz) writes: > Here's a similar problem I've been working on in 3-space- finding >the intersection of a line with a polygon. The solution I worked out >involves computing the line/plane intersection point and then checking >to see if the point is bounded by the polygon by rotating the polygon >and point into a plane so that the point can be checked in 2-space, then >check to see if the point is bounded by the polygon by determining >the orientation of the polygon (clockwise or counter) and computing >cross-products with each line segment. The sign can be checked to see >which side the point lies on. > John I suggest some improvements : - Use dot products instead of cross products : for each segment [Ai;Ai+1], compute a vector Vi parallel to the plane, orthogonal to the given segment, and directed to the interior of the convex polygon. To check if a point is inside, perform for each segment the dot product : Vi . AiM If any of these is negative, the point is outside the polygon. (precompute the Vi and store them with the polygon data). M _+ / _/ \Polygon / _/ /|\Vi \ /_/ | \ // | \ -----------------+---------------- Ai Ai+1 - You may use first the intersection with a sphere to check if your plane/line intersection point will not be in an infinite distance. f.p. ------------------------------------------------------------------------------- | Zeu<FP> : The craziest programmer in France | _________ | |------------------------------------------------| / | \ \ | | Francois Pellegrini is : | / |__ ___/ \ | | goofi!pelegrin@geocub.greco-prog.fr | \ | | / | | mcsun!inria!geocub!goofi!pelegrin@uunet.uu.net | \ | | / | | goofi!pelegrin@geocub.UUCP | | -------------------------------------------------------------------------------
eliot@pixar.UUCP (Eliot Smyrl) (04/11/90)
In article <10077@pixar.UUCP> I wrote: >In article <2094@crash.cts.com> jcs@crash.cts.com (John Schultz) writes: >>[finding] the intersection of a line with a polygon. The solution I worked out >[ algorithm description ] > >This is exactly the method used by the UgRay raytracer at UC Berkeley, > >If you need to see the Tech. Report on UgRay explaining his method, I >can email you the info. There was enough interest that I will post this: to obtain this Tech. Report, send a check for $6 made out to 'UC Regents' to Publications 571 Evans Hall UC Berkeley Berkeley, CA 94720 and ask for Tech. Report # 87/360, "UgRay: An Efficient Ray-Tracing Renderer for UniGrafix", by Donald M. Marsh. (And obviously include info telling them where to mail it). If you want to call them, the person to talk to is Jean Root at (415) 643-6619. But they won't send it without a check from you. The report is well-written and is a good introduction to many of the standard problems in ray-tracing and some practical design decisions about how to deal with them. By the way, Don did in fact use the enhancement described by Mark V., in which the polygon is not rotated but projected into the coordinated plane in which it has the largest projected area (for maximum numerical accuracy). This decision requires just two comparisons to determine the largest coordinate of the polygon's plane normal, and as Mark mentioned, the projection itself is essentially a null operation - you just ignore one of the coordinates. Eliot Smyrl {ucbvax,sun}!pixar!eliot