Xojo Conferences
MBSSep2018MunichDE
XDCMay2019MiamiUSA

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


[ANN] Preview of RBD 2.4   -   Marc Zeedar
  line segment/triangle intersection in 3D   -   Joe Raffanti
   Re: line segment/triangle intersection in 3D   -   Lars Jensen
    Re: line segment/triangle intersection in 3D   -   Lars Jensen
    Re: line segment/triangle intersection in 3D   -   Joseph J. Strout
     Re: line segment/triangle intersection in 3D   -   Lars Jensen
   Re: line segment/triangle intersection in 3D   -   Lo Saeteurn
   Re: line segment/triangle intersection in 3D   -   Joseph J. Strout
   Re: line segment/triangle intersection in 3D   -   Joe Raffanti
   Re: line segment/triangle intersection in 3D   -   Lo Saeteurn
   Re: line segment/triangle intersection in 3D   -   Joseph J. Strout
   Re: line segment/triangle intersection in 3D   -   Thomas Cunningham
   Re: line segment/triangle intersection in 3D   -   Thomas Cunningham

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>