line segment/triangle intersection in 3D (Real Studio games Mailinglist archive)
Back to the thread list
Previous thread: Re: Shadows
Next thread: OBJ and 3DS support for vertex colors
line segment/triangle intersection in 3D |
Date: 19.08.05 00:14 (Thu, 18 Aug 2005 16:14:38 -0700) |
From: Joe Raffanti |
Has anyone written a RB line segment / triangle intersection
detection test? If so, could I use it? thanks, Joe Raffanti _______________________________________________ Unsubscribe or switch delivery mode: <http://www.realsoftware.com/support/listmanager/> Search the archives of this list here: <http://support.realsoftware.com/listarchives/lists.html> |
Re: line segment/triangle intersection in 3D |
Date: 19.08.05 00:57 (Thu, 18 Aug 2005 19:57:14 -0400) |
From: Lars Jensen |
> Has anyone written a RB line segment / triangle intersection
> detection test? If so, could I use it? http://www.rbdeveloper.com/browse/3.4/3415/ "Polygon Hit Testing: Is a point inside a polygon?" Do the test for each endpoint, and if one is in and the other is out, they intersect. lj _______________________________________________ Unsubscribe or switch delivery mode: <http://www.realsoftware.com/support/listmanager/> Search the archives of this list here: <http://support.realsoftware.com/listarchives/lists.html> |
Re: line segment/triangle intersection in 3D |
Date: 19.08.05 01:00 (Thu, 18 Aug 2005 20:00:41 -0400) |
From: Lars Jensen |
> Do the test for each endpoint, and if one is in and the other is out, they
> intersect. Actually that's not a sufficient test -- it could still intersect even if both points are out -- but as I recall the article goes into that too. lj _______________________________________________ Unsubscribe or switch delivery mode: <http://www.realsoftware.com/support/listmanager/> Search the archives of this list here: <http://support.realsoftware.com/listarchives/lists.html> |
Re: line segment/triangle intersection in 3D |
Date: 19.08.05 15:27 (Fri, 19 Aug 2005 08:27:10 -0600) |
From: Joseph J. Strout |
At 7:57 PM -0400 8/18/05, Lars Jensen wrote:
>http://www.rbdeveloper.com/browse/3.4/3415/ > >"Polygon Hit Testing: Is a point inside a polygon?" I don't think that will work well in 3D. Best, - Joe |
Re: line segment/triangle intersection in 3D |
Date: 19.08.05 15:52 (Fri, 19 Aug 2005 10:52:54 -0400) |
From: Lars Jensen |
>> http://www.rbdeveloper.com/browse/3.4/3415/
>> >> "Polygon Hit Testing: Is a point inside a polygon?" > > I don't think that will work well in 3D. Correct -- it didn't occur to me that it was a 3D question until after I posted... :/ lj _______________________________________________ Unsubscribe or switch delivery mode: <http://www.realsoftware.com/support/listmanager/> Search the archives of this list here: <http://support.realsoftware.com/listarchives/lists.html> |
Re: line segment/triangle intersection in 3D |
Date: 19.08.05 01:10 (Thu, 18 Aug 2005 17:10:08 -0700) |
From: Lo Saeteurn |
I am currently going through the same problem.
I found a function in Quesa that handles this, but I have yet to test it. If you're already using Quesa, it shouldn't be a problem: Declare Function Q3Ray3D_IntersectTriangle Lib QuesaLib (theRay as Ptr, point1 as Ptr, point2 as Ptr, point3 as Ptr, cullBackfacing as boolean, hitPoint as Ptr) as Boolean On Aug 18, 2005, at 4:14 PM, Joe Raffanti wrote: > Has anyone written a RB line segment / triangle intersection > detection test? If so, could I use it? > > thanks, > Joe Raffanti > _______________________________________________ > Unsubscribe or switch delivery mode: > <http://www.realsoftware.com/support/listmanager/> > Search the archives of this list here: > <http://support.realsoftware.com/listarchives/lists.html> _______________________________________________ Unsubscribe or switch delivery mode: <http://www.realsoftware.com/support/listmanager/> Search the archives of this list here: <http://support.realsoftware.com/listarchives/lists.html> |
Re: line segment/triangle intersection in 3D |
Date: 19.08.05 15:26 (Fri, 19 Aug 2005 08:26:44 -0600) |
From: Joseph J. Strout |
At 4:14 PM -0700 8/18/05, Joe Raffanti wrote:
>Has anyone written a RB line segment / triangle intersection detection test? I think there's one in Renegades, or in its precursor, the FPS demo described in RB Developer issue 1.3. >If so, could I use it? Sure, help yourself. If that doesn't do what you need, then do a search for "Paul Bourke Geometry" -- Paul is an astronomer in Australia who has a ton of amazingly useful tutorials for this sort of thing. Best, - Joe |
Re: line segment/triangle intersection in 3D |
Date: 20.08.05 01:27 (Fri, 19 Aug 2005 17:27:17 -0700) |
From: Joe Raffanti |
Thanks for all the feedback, everyone.
I think this is what you were referring to in Renegades: Function PlaneIntersection(planeNormal As Vector3D, planeD As Double, p0 As Vector3D, p1 As Vector3D) As Vector3D // Find the intersection of the line from p0 to p1 with the given plane. // See Lengyel p. 85. Dim t As Double Dim V As Vector3D V = p1.Minus(p0) t = -(planeNormal.dot(p0) + planeD) / (planeNormal.Dot(V)) return p0.Plus(V.Times(t)) End Function This looks like the right thing, but what does planeD refer to? ...I assume it is plane Depth or something like that, but then what do I measure the depth from? How would I set up the plane? thanks, Joe Raffanti >At 4:14 PM -0700 8/18/05, Joe Raffanti wrote: > >>Has anyone written a RB line segment / triangle intersection detection test? > >I think there's one in Renegades, or in its precursor, the FPS demo >described in RB Developer issue 1.3. > >>If so, could I use it? > >Sure, help yourself. If that doesn't do what you need, then do a >search for "Paul Bourke Geometry" -- Paul is an astronomer in >Australia who has a ton of amazingly useful tutorials for this sort >of thing. > >Best, >- Joe > >-- >Joe Strout REAL Software, Inc. > >Vote for REALbasic (twice!) in the LinuxWorld Reader's Choice Awards: >http://linux.sys-con.com/general/readerschoice.htm >_______________________________________________ >Unsubscribe or switch delivery mode: ><http://www.realsoftware.com/support/listmanager/> >Search the archives of this list here: ><http://support.realsoftware.com/listarchives/lists.html> _______________________________________________ Unsubscribe or switch delivery mode: <http://www.realsoftware.com/support/listmanager/> Search the archives of this list here: <http://support.realsoftware.com/listarchives/lists.html> |
Re: line segment/triangle intersection in 3D |
Date: 20.08.05 17:21 (Sat, 20 Aug 2005 09:21:46 -0700) |
From: Lo Saeteurn |
I used this function that I translated from C. An intersection occurs
when it returns 1 or 2. I is the point of intersection. Function RayTriangleIntersect(P0 as vector3D, P1 as vector3D, v0 as vector3D, v1 as vector3D, v2 as vector3D, BYREF I as vector3D) as integer dim dir, w0, w,u,v,n as Vector3d // ray vectors dim r, a, b as Double // params to calc ray-plane intersect dim uu, uv, vv, wu, wv, D as Double dim s, t as Double const SMALL_NUM00000001 // get triangle edge vectors and plane normal u = V1.Minus(V0) v = V2.minus(V0) n = u.cross(v) // cross product if (n.LenSquared then // triangle is degenerate return -1 // do not deal with this case end if dir = P1.minus(P0) // ray direction vector w0 = P0.minus(V0) a = -n.dot(w0) b = n.dot(dir) if (abs(b) < SMALL_NUM) then // ray is parallel to triangle plane if (a = 0) then // ray lies in triangle plane return 2 else return 0 end if // ray disjoint from plane end if // get intersect point of ray with triangle plane r = a / b if (r < 0.0) then// ray goes away from triangle return 0 // => no intersect end if // for a segment, also test if (r > 1.0) => no intersect I = P0.plus(dir.Times(r)) // intersect point of ray and plane // is I inside T? uu = u.dot(u) uv = u.dot(v) vv = v.dot(v) w = I.minus(V0) wu = w.dot(u) wv = w.dot(v) D = uv * uv - uu * vv // get and test parametric coords s = (uv * wv - vv * wu) / D if (s < 0.0 or s > 1.0) then // I is outside T return 0 end if t = (uv * wu - uu * wv) / D if (t < 0.0 or (s + t) > 1.0) then // I is outside T return 0 end if return 1 // I is in T End Function On Aug 19, 2005, at 5:27 PM, Joe Raffanti wrote: > Thanks for all the feedback, everyone. > I think this is what you were referring to in Renegades: > > Function PlaneIntersection(planeNormal As Vector3D, planeD As > Double, p0 As Vector3D, p1 As Vector3D) As Vector3D > // Find the intersection of the line from p0 to p1 with the > given plane. > // See Lengyel p. 85. > Dim t As Double > Dim V As Vector3D > V = p1.Minus(p0) > t = -(planeNormal.dot(p0) + planeD) / (planeNormal.Dot(V)) > return p0.Plus(V.Times(t)) > End Function > > This looks like the right thing, but what does planeD refer > to? ...I assume it is plane Depth or something like that, but then > what do I measure the depth from? How would I set up the plane? > > thanks, > Joe Raffanti > >> At 4:14 PM -0700 8/18/05, Joe Raffanti wrote: >> >>> Has anyone written a RB line segment / triangle intersection >>> detection test? >>> >> I think there's one in Renegades, or in its precursor, the FPS >> demo described in RB Developer issue 1.3. >> >>> If so, could I use it? >>> >> Sure, help yourself. If that doesn't do what you need, then do a >> search for "Paul Bourke Geometry" -- Paul is an astronomer in >> Australia who has a ton of amazingly useful tutorials for this >> sort of thing. >> >> Best, >> - Joe >> >> -- >> Joe Strout REAL Software, Inc. >> >> Vote for REALbasic (twice!) in the LinuxWorld Reader's Choice Awards: >> http://linux.sys-con.com/general/readerschoice.htm >> _______________________________________________ >> Unsubscribe or switch delivery mode: >> <http://www.realsoftware.com/support/listmanager/> >> >> Search the archives of this list here: >> <http://support.realsoftware.com/listarchives/lists.html> >> > _______________________________________________ > Unsubscribe or switch delivery mode: > <http://www.realsoftware.com/support/listmanager/> > Search the archives of this list here: > <http://support.realsoftware.com/listarchives/lists.html> _______________________________________________ Unsubscribe or switch delivery mode: <http://www.realsoftware.com/support/listmanager/> Search the archives of this list here: <http://support.realsoftware.com/listarchives/lists.html> |
Re: line segment/triangle intersection in 3D |
Date: 22.08.05 16:22 (Mon, 22 Aug 2005 09:22:53 -0600) |
From: Joseph J. Strout |
At 5:27 PM -0700 8/19/05, Joe Raffanti wrote:
>Thanks for all the feedback, everyone. >I think this is what you were referring to in Renegades: > >Function PlaneIntersection(planeNormal As Vector3D, planeD As >Double, p0 As Vector3D, p1 As Vector3D) As Vector3D No, that just fines the intersection of a line with a plane -- which is *part* of finding a line/triangle intersection, but only part. Lo posted code that should do what you need; I suggest just using that. If you ever do need to intersect a line with a plane, bring this up again and I'll explain how to define a plane for use with this function. Best, - Joe |
Re: line segment/triangle intersection in 3D |
Date: 19.08.05 23:35 (Fri, 19 Aug 2005 12:35:26 -1000) |
From: Thomas Cunningham |
_______________________________________________
Unsubscribe or switch delivery mode: <http://www.realsoftware.com/support/listmanager/> Search the archives of this list here: <http://support.realsoftware.com/listarchives/lists.html> |
Re: line segment/triangle intersection in 3D |
Date: 19.08.05 23:37 (Fri, 19 Aug 2005 12:37:02 -1000) |
From: Thomas Cunningham |
Ugh, sorry for the noise, first response had an attachment. This is for a line and a box from code by David Eberly of Magic Software and his #D Game engine book. Sorry, but a casual search for his web site is coming up empty. Function LineBoxIntersection(segment As LineSegment3D, box As Box3D) As Boolean // return value is 'true' if and only if objects intersect // Clipping of a linear component 'origin'+t*'direction' against an // axis-aligned box [-e0,e0]x[-e1,e1]x[-e2,e2] where 'extent'=(e0,e1,e2). // The values of t0 and t1 must be set by the caller. // If the component is a segment, set t0 = 0 and t1 = 1. // The values are (possibly) modified by the clipper. Dim AWdu(2),ADdu(2),AWxDdu(2), Rhs As Double Dim sDirection, sCenter, Diff As Vector3D sDirection = New Vector3D() sDirection = segment.direction.Times(0.50) sCenter = New Vector3D sCenter = segment.origin.Plus(sDirection) Diff = New Vector3D Diff = sCenter.Minus(box.center) // tests requires a change in the coord. system // x AWdu(0) = ABS(sDirection.Dot(box.axis(0))) ADdu(0) = ABS(Diff.Dot(box.axis(0))) Rhs = box.extent(0) + AWdu(0) If ADdu(0) > Rhs Then Return False End // y AWdu(1) = ABS(sDirection.Dot(box.axis(1))) ADdu(1) = ABS(Diff.Dot(box.axis(1))) Rhs = box.extent(1) + AWdu(1) If ADdu(1) > Rhs Then Return False End // z AWdu(2) = ABS(sDirection.Dot(box.axis(2))) ADdu(2) = ABS(Diff.Dot(box.axis(2))) Rhs = box.extent(2) + AWdu(2) If ADdu(2) > Rhs Then Return False End Dim WxD As Vector3D WxD = sDirection.Cross(Diff) // AWxDdu(0) = ABS(WxD.Dot(box.axis(0))) Rhs = box.extent(1) * AWdu(2) + box.extent(2) * AWdu(1) if AWxDdu(0) > Rhs Then Return False End // AWxDdu(1) = ABS(WxD.Dot(box.axis(1))) Rhs = box.extent(0) * AWdu(2) + box.extent(2) * AWdu(0) if AWxDdu(1) > Rhs Then Return False End // AWxDdu(2) = ABS(WxD.Dot(box.axis(2))) Rhs = box.extent(0) * AWdu(1) + box.extent(1) * AWdu(0) if AWxDdu(2) > Rhs Then Return False End // Return True End Function LineSegment3D is a direction As Vector3D origin As Vector3D Box3D is a axis(2) As Vector3D center As Vector3D extent(2) As Double Perhaps that would help you. Thomas C. _______________________________________________ Unsubscribe or switch delivery mode: <http://www.realsoftware.com/support/listmanager/> Search the archives of this list here: <http://support.realsoftware.com/listarchives/lists.html> |