brad@gcc-opus.ARPA (Brad Parker) (11/26/84)
[ is something supposed to go here? :-> ]
Could someone please point me towards a nifty algorithm for determining
if a line intersects an arbitrary polygon?
("can you say r-a-y t-r-a-c-i-n-g?"). There must be at least 4-5 ways to
do this. I'm too lazy to go do through old Siggraph proceedings, though
I will if I have to.
(they're all saying "now that you've those smooth shaded spheres,
when are we going to see something REALLY interesting?")
Thanks in advance.
--
-----
J Bradford Parker
uucp: siesmo!harvard!gcc-opus!brad
"Their is no language in our lungs!"
-----jwp@utah-cs.UUCP (John W Peterson) (11/28/84)
You can substitute the line equation into the plane equation of the polygon (derived from its normal), to find where the line (or ray) intersects the plane. (If you find yourself dividing by zero someplace, the line and plane are parallel). Once you've found the intersection point, there is a nifty algorithm (for convex polygons) to determine if the point is inside the polygon. This algorithm, along with an excellent discussion of the geometry involved, is given in: Sutherland, I, Sproull, R., and Schumacker, R., "A Characterization of Ten Hidden-Surface Algorithms", Computer Surveys, 6(1):1, March, 1974. This paper is a must-read for anybody doing 3D shaded graphics, whether it's ray-tracing or scanlines. It has an amazing store of good information and handy tricks.
keithd@cadovax.UUCP (Keith Doyle) (11/29/84)
[] >Could someone please point me towards a nifty algorithm for determining >if a line intersects an arbitrary polygon? >J Bradford Parker I'd like to hear about this one too! Thanks, Keith Doyle {ucbvax,ihnp4,decvax}!trwrb!cadovax!keithd "You'll PAY to know what you REALLY think!"
nst@uvaee.UUCP (12/17/84)
> You can substitute the line equation into the plane equation of the polygon > (derived from its normal), to find where the line (or ray) intersects > the plane. (If you find yourself dividing by zero someplace, the line > and plane are parallel). > > Once you've found the intersection point, there is a nifty algorithm > (for convex polygons) to determine if the point is inside the polygon. > > This algorithm, along with an excellent discussion of the geometry involved, > is given in: > > Sutherland, I, Sproull, R., and Schumacker, R., "A Characterization > of Ten Hidden-Surface Algorithms", Computer Surveys, 6(1):1, > March, 1974. > > This paper is a must-read for anybody doing 3D shaded graphics, whether it's > ray-tracing or scanlines. It has an amazing store of good information and > handy tricks. *** REPLACE THIS LINE WITH YOUR MESSAGE ***