[bb] Ray / Line Segment Intersection by sswift [ 1+ years ago ]

Started by BlitzBot, June 29, 2017, 00:28:39

Previous topic - Next topic
Print
Go Down Pages1
User actions

BlitzBot

June 29, 2017, 00:28:39
Title : Ray / Line Segment  Intersection
Author : sswift
Posted : 1+ years ago

Description : The Ray_Intersect_Triangle function I have provided here provides functionality which even Blitz's own line intersect function does not.

It provides the ability to define a line segment instead of a ray just as you can with Blitz's line intersect function, but it also allows infinite rays, and it allows backface culling, so if you fire a ray from inside a mesh it will be as if the mesh does not exist.  This is very useful for light map calculations, which is why I wrote it.

The Ray_Intersect_Mesh function is an extension of the Ray_Intersect_Triangle function.  It behaves more like Blitz's line intersect function because it checks whole meshes rather than just a single triangle.  It examines all triangles in all surfaces until it hits one and then it exits early.

This early out functionality should make it faster than Blitz's own lineintersect function.  The drawback is that it does not tell you what the CLOSEST intersection was like Blitz's lineintersect function, but you could easily modify the Ray_Intersect_Mesh function to provide that capability.

Code :
Code (blitzbasic) Select
; -------------------------------------------------------------------------------------------------------------------
; This function returns TRUE if a ray intersects a triangle.
; It also calculates the UV coordinates of said colision as part of the intersection test,
; but does not return them.
;
; V0xyz, V1xyz, and V2xyz are the locations of the three vertices of the triangle.
;
; These vertices should be wound in CLOCKWISE order.  By clockwise I mean that if you face the front side of the
; trianngle, the vertcies go around the trangle from V0 to V1 to V2 in a clockwise direction.  This is the same
; as Blitz, so just pass the vertcies for a triangle in the same order that Blitz does.
;
; The UV's generated by the function are set up as follows:
; V0 is the location of UV(0,0)
;   V1 is the location of UV(0,1)
;   V2 is the location of UV(1,0)
;
; This is useful to know if you want to know the exact location in texture space of the collision.
; You can easily modify the function to return the values of T#, U#, and V#.
;
; Pxyz is a the start of the line.
; Triangles which are "behind" this point are ignored.
; "Behind" is defined as the direction opposite that which Dxyz points in.
;
; Dxyz is a vector providing the slope of the line.
; Dxyz does not have to be normalized.
;
; If Extend_To_Infinity is set to false, then the length of Dxyz is how far the ray extends.
; So if you want an endpoint on your ray beyond which no triangles will be detected, subtract the position
; of Pxyz from your endpoint's position, and pass that ato the function as Dxyz.  Ie: (Dx = P2x-P1x)
;
; If Cull_Backfaces is set to true, then if the specified ray passes through the triangle from it's back side, then
; it will not register that it hit that triangle.
; -------------------------------------------------------------------------------------------------------------------
Function Ray_Intersect_Triangle(Px#, Py#, Pz#, Dx#, Dy#, Dz#, V0x#, V0y#, V0z#, V1x#, V1y#, V1z#, V2x#, V2y#, V2z#, Extend_To_Infinity=True, Cull_Backfaces=False)

; crossproduct(b,c) =
; ax = (by * cz) - (cy * bz)
; ay = (bz * cx) - (cz * bx)
; az = (bx * cy) - (cx * by)

; dotproduct(v,q) =
; (vx * qx) + (vy * qy) + (vz * qz)
; DP =  1 = Vectors point in same direction.          (  0 degrees of seperation)
; DP =  0 = Vectors are perpendicular to one another. ( 90 degrees of seperation)
; DP = -1 = Vectors point in opposite directions.     (180 degrees of seperation)
;
; The dot product is also reffered to as "the determinant" or "the inner product"

; Calculate the vector that represents the first side of the triangle.
E1x# = V2x# - V0x#
E1y# = V2y# - V0y#
E1z# = V2z# - V0z#

; Calculate the vector that represents the second side of the triangle.
E2x# = V1x# - V0x#
E2y# = V1y# - V0y#
E2z# = V1z# - V0z#

; Calculate a vector which is perpendicular to the vector between point 0 and point 1,
; and the direction vector for the ray.
; Hxyz = Crossproduct(Dxyz, E2xyz)
Hx# = (Dy# * E2z#) - (E2y# * Dz#)
Hy# = (Dz# * E2x#) - (E2z# * Dx#)
Hz# = (Dx# * E2y#) - (E2x# * Dy#)

; Calculate the dot product of the above vector and the vector between point 0 and point 2.
A# = (E1x# * Hx#) + (E1y# * Hy#) + (E1z# * Hz#)

; If we should ignore triangles the ray passes through the back side of,
; and the ray points in the same direction as the normal of the plane,
; then the ray passed through the back side of the plane,  
; and the ray does not intersect the plane the triangle lies in.
If (Cull_Backfaces = True) And (A# >= 0) Then Return False

; If the ray is almost parralel to the plane,
; then the ray does not intersect the plane the triangle lies in.
If (A# > -0.00001) And (A# < 0.00001) Then Return False

; Inverse Determinant. (Dot Product)
; (Scaling factor for UV's?)
F# = 1.0 / A#

; Calculate a vector between the starting point of our ray, and the first point of the triangle,
; which is at UV(0,0)
Sx# = Px# - V0x#
Sy# = Py# - V0y#
Sz# = Pz# - V0z#

; Calculate the U coordinate of the intersection point.
;
; Sxyz is the vector between the start of our ray and the first point of the triangle.
; Hxyz is the normal of our triangle.
;
; U# = F# * (DotProduct(Sxyz, Hxyz))
U# = F# * ((Sx# * Hx#) + (Sy# * Hy#) + (Sz# * Hz#))

; Is the U coordinate outside the range of values inside the triangle?
If (U# < 0.0) Or (U# > 1.0)

; The ray has intersected the plane outside the triangle.
Return False

EndIf

; Not sure what this is, but it's definitely NOT the intersection point.
;
; Sxyz is the vector from the starting point of the ray to the first corner of the triangle.
; E1xyz is the vector which represents the first side of the triangle.
; The crossproduct of these two would be a vector which is perpendicular to both.
;
; Qxyz = CrossProduct(Sxyz, E1xyz)
Qx# = (Sy# * E1z#) - (E1y# * Sz#)
Qy# = (Sz# * E1x#) - (E1z# * Sx#)
Qz# = (Sx# * E1y#) - (E1x# * Sy#)

; Calculate the V coordinate of the intersection point.
;
; Dxyz is the vector which represents the direction the ray is pointing in.
; Qxyz is the intersection point I think?
;
; V# = F# * DotProduct(Dxyz, Qxyz)
V# = F# * ((Dx# * Qx#) + (Dy# * Qy#) + (Dz# * Qz#))

; Is the V coordinate outside the range of values inside the triangle?
; Does U+V exceed 1.0?  
If (V# < 0.0) Or ((U# + V#) > 1.0)

; The ray has intersected the plane outside the triangle.
Return False

; The reason we check U+V is because if you imagine the triangle as half a square, U=1 V=1 would
; be in the lower left hand corner which would be in the lower left triangle making up the square.
; We are looking for the upper right triangle, and if you think about it, U+V will always be less
; than or equal to 1.0 if the point is in the upper right of the triangle.

EndIf

; Calculate the distance of the intersection point from the starting point of the ray, Pxyz.
; This distance is scaled so that at Pxyz, the start of the ray, T=0, and at Dxyz, the end of the ray, T=1.
; If the intersection point is behind Pxyz, then T will be negative, and if the intersection point is
; beyond Dxyz then T will be greater than 1.
T# = F# * ((E2x# * Qx#) + (E2y# * Qy#) + (E2z# * Qz#))

; If the triangle is behind Pxyz, ignore this intersection.
; We want a directional ray, which only intersects triangles in the direction it points.
If (T# < 0) Then Return False

; If the plane is beyond Dxyz, amd we do not want the ray to extend to infinity, then ignore this intersection.
If (Extend_To_Infinity = False) And (T# > 1) Return False

; The ray intersects the triangle!
Return True

End Function


; -------------------------------------------------------------------------------------------------------------------
; This function returns true if a ray intersects a mesh.
;
; This function differs from LinePick in that the specified mesh does not need to have a pickmode set,
; and this function can optionally ignore backfacing polygons in the mesh.  So if you do a pick from
; inside a mesh, it will not register a hit.
; -------------------------------------------------------------------------------------------------------------------
Function Ray_Intersect_Mesh(Mesh, Px#, Py#, Pz#, Dx#, Dy#, Dz#, Extend_To_Infinity=True, Cull_Backfaces=False)

Surfaces = CountSurfaces(Mesh)

; Make sure there's a surface, because the mesh might be empty.
If Surfaces > 0

For SurfaceLoop = 1 To Surfaces

Surface = GetSurface(Mesh, SurfaceLoop)

; Examine all triangles in this surface.
Tris  = CountTriangles(Surface)
For TriLoop = 0 To Tris-1

V0 = TriangleVertex(Surface, TriLoop, 0)
V1 = TriangleVertex(Surface, TriLoop, 1)
V2 = TriangleVertex(Surface, TriLoop, 2)

V0x# = VertexX#(Surface, V0)
V0y# = VertexY#(Surface, V0)
V0z# = VertexZ#(Surface, V0)

V1x# = VertexX#(Surface, V1)
V1y# = VertexY#(Surface, V1)
V1z# = VertexZ#(Surface, V1)

V2x# = VertexX#(Surface, V2)
V2y# = VertexY#(Surface, V2)
V2z# = VertexZ#(Surface, V2)

TFormPoint V0x#, V0y#, V0z#, Mesh, 0
V0x# = TFormedX#()
V0y# = TFormedY#()
V0z# = TFormedZ#()

TFormPoint V1x#, V1y#, V1z#, Mesh, 0
V1x# = TFormedX#()
V1y# = TFormedY#()
V1z# = TFormedZ#()

TFormPoint V2x#, V2y#, V2z#, Mesh, 0
V2x# = TFormedX#()
V2y# = TFormedY#()
V2z# = TFormedZ#()

Intersected = Ray_Intersect_Triangle(Px#, Py#, Pz#, Dx#, Dy#, Dz#, V0x#, V0y#, V0z#, V1x#, V1y#, V1z#, V2x#, V2y#, V2z#, Extend_To_Infinity, Cull_Backfaces)
If Intersected Then Return True

Next

Next

EndIf

Return False

End Function

Comments : none...
Print
Go Up Pages1
User actions