scm@onion.cs.reading.ac.uk (Stephen Marsh) (11/18/86)
Can anyone help me with some 3D geometry? I am looking
for an algorithm which will enable me to test if a line in a
three-coordinate system with equation r=a+lambda*b intersects
a polygon with vertices v1,v2,....,vn (n>=3,v = (x,y,z)) which
lies in the plane n.r/|n| = p.
What I need is NOT the line-plane intersection point,
but an algorithm which tests to see if the intersection point
is contained within the 3D polygon.
Many Thanks.garry@batcomputer.tn.cornell.edu (Garry Wiegand) (11/20/86)
In a recent article scm@onion.cs.reading.Ac.Uk (Stephen Marsh) wrote: >... What I need is NOT the line-plane intersection point, >but an algorithm which tests to see if the intersection point >is contained within the 3D polygon. The simple minded approach is to project it down into a convenient 2-D plane and apply the usual point-in-polygon algorithms. For example, given the 3-D intersection point and polygon, and given (for this example) that the polygon is not perpendicular to the XY plane, project it down into that plane. Do this by ignoring the Z-values! Once there, start anywhere on the polygon and walk around. At each step, test to see if the edge passes above-to-below or below-to-above with respect to the test point. (Note: For purposes of "passing", the start vertex of the edge does NOT count, and the end vertex DOES count.) If it *does* pass, figure whether it passes to the left or right of the test point: If the test edge is horizontal and includes the test point, declare it "in" and exit. If the edge is horizontal and doesn't include the test point, forget it. If it's not horizontal, see if the edge is completely left or right of the test point. If it's not completely left or right, then compute the intersection with the horizontal and see whether *that* is left or right. If the intersection is right on top, declare the point "in" and exit. Remember how many times you pass to the left, say. If this ends up odd, the point's in. Otherwise it's out. In the normal "in" case you'll need to compute maybe *one* edge/axis intersection. Whew. (We need a picture.) You can improve the computation with bounding boxes and other such tricks. If you know the polygon's convex, you of course won't need a counter, and you'll only need to look at at most (n+1)/2 edges (often far fewer) (exercise left for the reader.) (If you're working in floating-point, be careful about tests-for- equality!) (If the original polygon WAS perpendicular to the XY plane, project into the YZ plane, say, and apply a tweaked version of the above algorithm.) I trust I've been complete. Wonder if it's right - I've never gotten around to reading about this subject (who said computer graphics wasn't ffun ? :-) garry wiegand (garry%cadif-oak@cu-arpa.cs.cornell.edu)
poslfit@utcs.UUCP (11/20/86)
In article <90@onion.cs.reading.ac.uk> scm@onion.cs.reading.Ac.Uk (Stephen Marsh) writes: > > Can anyone help me with some 3D geometry? I am looking > for an algorithm which will enable me to test if a line in a > three-coordinate system with equation r=a+lambda*b intersects > a polygon with vertices v1,v2,....,vn (n>=3,v = (x,y,z)) which > lies in the plane n.r/|n| = p. > What I need is NOT the line-plane intersection point, > but an algorithm which tests to see if the intersection point > is contained within the 3D polygon. As far as I can tell, this is a 2-D problem. Unless the polygon is perpendicular to the x-y plane (i.e. its normal is //z) project it and the line-polygon intersection point into said plane by dropping z co-ordinates. Then treat it as a two-dimensional problem. Remember that if the line and polygon are generally independently chosen and the polygon is nice and convex, you'd probably save comparisons by testing non-consecutive polygon edges (n-s-e-w rather than n-e-s-w order). Of course, if the polygon is _|_ to x-y, just project it onto the x-z or y-z plane. -- from the serial port of john j. chew (v3.0) a/k/a poslfit@utcs.UUCP just another ninja toad dicing with death and looking for that Talisman -- *** THIS LINE HAS BEEN REPLACED BY... from the serial port of john j. chew (v3.0) a/k/a poslfit@utcs.UUCP just another ninja toad dicing with death and looking for that Talisman
brad@gcc-milo.UUCP (11/21/86)
> > Can anyone help me with some 3D geometry? I am looking > for an algorithm which will enable me to test if a line in a > three-coordinate system with equation r=a+lambda*b intersects > a polygon with vertices v1,v2,....,vn (n>=3,v = (x,y,z)) which > lies in the plane n.r/|n| = p. Last time I did this was for ray tracing polygons (where is Jim Kajia when you need him?). And the easiest way I found was to find the point of intersection between the line and the plane formed by three of the vertices (let's assume they're co-planer) . This yields a 3d point. Then, I translated the point and verticies into 2d (actually, I just translated the point as the plane was defined via a plane equation) and then performed the following: Calculate the sum of the angles formed by two adjacent verticies and the point. i.e. draw lines from the point to two adjacent vertices. Do this for all the sets of vertices. If the sum of the angles is != 360, you are outside of the polygon. Does this make sense? The idea is correct, but the particulars may be off. Anyone have a better way to do this? -- J Bradford Parker General Computer (HyperDrive Beach, 3rd Cabana) harvard!gcc-milo!brad Good Sex is easier than a good slow roll. ("Left Stick! Right Rudder!...")
falk@sun.UUCP (11/23/86)
> > > > Can anyone help me with some 3D geometry? I am looking > > for an algorithm which will enable me to test if a line in a > > three-coordinate system with equation r=a+lambda*b intersects > > a polygon with vertices v1,v2,....,vn (n>=3,v = (x,y,z)) which > > lies in the plane n.r/|n| = p. > > Last time I did this was for ray tracing polygons (where is Jim Kajia > when you need him?). And the easiest way I found was to find the point > of intersection between the line and the plane formed by three of the > vertices (let's assume they're co-planer) . This yields a 3d point. > Then, I translated the point and verticies into 2d (actually, I just translated > the point as the plane was defined via a plane equation) and then performed > the following: > > Calculate the sum of the angles formed by two adjacent verticies > and the point. i.e. draw lines from the point to two adjacent > vertices. Do this for all the sets of vertices. If the sum of the > angles is != 360, you are outside of the polygon. > > Does this make sense? The idea is correct, but the particulars may be off. This is one of the classic ways to test for point-inside-polygon. The problem is that it requires some trigonometry for each vertex of the polygon (inverse tangent). That's kind of expensive. Also, you're dealing with real numbers and approximations, so there's going to be an error that has to be tolerated. I.e. the sum will never be EXACTLY 360 or 0. A faster, but harder to implement algorithm is where you project half-lines from the point being tested to infinity (preferably along one of the axes). Intersect this half-line with all of the edges of the polygon and count the intersections. If it's odd, the point is inside the polygon. When the half-line exactly intersects a vertex, you have a special case because that's only supposed to count as one intersection. The solution to this special case is to only count vertex intersections at the "endpoint" of the edges and not the "startpoint". Note that you don't actually have to compute the points of intersection, just test for their existance (method left to the student). If the polygon is known to be convex, it becomes a much simpler problem. For instance, take the dot-products of all of the pairs of vectors from the test point to adjecent vertices. These dot-products will be strictly negative or strictly positive if the test point is inside the polygon. > Good Sex is easier than a good slow roll. ("Left Stick! Right Rudder!...") Yeah, but right after a slow roll, you're ready for another. -- -ed falk, sun microsystems terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO. (The above is food for the NSA line eater.)
garry@batcomputer.tn.cornell.edu (Garry Wiegand) (11/24/86)
In a recent article falk@sun.uucp (Ed Falk) wrote: >A faster, but harder to implement algorithm is where you project half-lines >from the point being tested to infinity (preferably along one of the >axes). Intersect this half-line with all of the edges of the polygon >and count the intersections... >... >Note that you don't actually have to compute the points of intersection, >just test for their existance (method left to the student). Yes, I think you do have to compute the intersection in one special case - the case where you *know* the full-line intersects but the half- line begins somewhere within the edge in question. See the method I posted a few days ago for the glitch point. (Or am I not seeing something?) >If the polygon is known to be convex, it becomes a much simpler problem. >For instance, take the dot-products of all of the pairs of vectors from >the test point to adjecent vertices. These dot-products will be strictly >negative or strictly positive if the test point is inside the polygon. Yes, this is simpler, but it involves more computation than the half-line method. Specifically, the half-line method requires two or three comparisons per point, and only looking at half the points (average convex case), while the dot-products require 4 subtracts and 2 multiplies per point, and looking at *every* point. Also, if you're working in floating-point you still have to worry about roundoff errors, and if you're in integers you probably have to use long ints to avoid overflows. Anyhow, I've noticed since my first posting that if the points are stored in an array rather than a list, and if there are enough of them to make more computation per step worthwhile, then the convex case can be reduced from O(n) to O(log n)! (Do a binary search.) garry wiegand (garry%cadif-oak@cu-arpa.cs.cornell.edu)