Path: chuka.playstation.co.uk!argonet.co.uk!argbc08 From: R Fred Williams Newsgroups: scee.yaroze.programming.3d_graphics Subject: Re: Poly Intersections Date: Sun, 03 Jan 1999 22:18:51 GMT Organization: ArgoNet, but does not reflect its views Lines: 94 Distribution: world Message-ID: References: <3689671E.AA01BBAB@hinge.mistral.co.uk> Reply-To: R Fred Williams NNTP-Posting-Host: userl747.uk.uudial.com X-Newsreader: NewsAgent 0.84 for RISC OS X-NNTP-Poster: NewsHound v1.37ß2 In article <3689671E.AA01BBAB@hinge.mistral.co.uk>, Craig Graham wrote: > Anyone got a nice quick way of doing the ray plane intersect? > (an O(1) algorithm would be good) Extract from the comp.graphics.algorithms faq... -------------- Subject 5.05: How do I find the intersection of a line and a plane? If the plane is defined as: a*x + b*y + c*z + d = 0 and the line is defined as: x = x1 + (x2 - x1)*t = x1 + i*t y = y1 + (y2 - y1)*t = y1 + j*t z = z1 + (z2 - z1)*t = z1 + k*t Then just substitute these into the plane equation. You end up with: t = - (a*x1 + b*y1 + c*z1 + d)/(a*i + b*j + c*k) When the denominator is zero, the line is contained in the plane if the numerator is also zero (the point at t=0 satisfies the plane equation), otherwise the line is parallel to the plane. -------------- Well, that's nice & quick, but... The cga faq, while being a very handy thing to have on call, has a habit of missing out important things like... If your source data's a polygon, then the abcd plane equation needs to be derived from three polygon points, using the "determinant" version of the plane equation... |(x-x1) (y-y1) (z-z1) | |(x2-x1) (y2-y1) (z2-z1)| = 0 |(x3-x1) (y3-y1) (z3-z1)| (I'd read that as p1 being the "angle", not that it matters beyond the clockwise/anti issue) Good luck with all the plusses & minuses on that, & you'll end up with a,b,c,d in terms of x1,x2,x3,y1,y2,y3,z1,z2,z3. ---- OK, to save you looking it up (I started doing 3d code 10 years after learning this o-level maths stuff, and having to re-learn all the bits I'd forgotten was a major pain ;) Definition of 3*3 matrix-determinants:- |a b c| = a * |e f| - b * |d f| + c * |d e| |d e f| |h i| |g i| |g h| |g h i| and of 2*2's |w x| = w*z - x*y |y z| In this case, all the 2*2 determinants are constant, which is handy. ---- NB - scan your poly for 3 points with a decent angle between 'em. Specifically, bear in mind that sooner or later someone *will* throw a poly at you with colinear, or even duplicate, points in it. Come to that, artists will, at some point, give you entirely colinear "polygons" to contend with, which (obviously) have no fixed plane equation :) It's worth precalcing the abcd equation for your planes *anyway*, coz "which side of a plane is a point on?" is simply a matter of plugging xyz into the abcd, and seeing if the result is >,=,< zero, and that's a *very* quick & easy first test for poly->plane intersection. Forgive me if I'm stating the bleedin' obvious here (or indeed in any of the above)! Source is left to the interested reader ;) (my code for this is at work, I'm on holiday, and in any case, it'd suffer from copyright issues) ttfn Fred (yaroze /~RFREDW)