Help function to know a triangle-box intersection

Blitz3D Forums/Blitz3D Programming/Help function to know a triangle-box intersection

patmaba

(Posted 2008) [#1]

Hi,

I have found a c++ routine to know if a trianle overlapping a box.

http://jgt.akpeters.com/papers/AkenineMoller01/tribox.html

I need a function in blitz who do the same job, but the function use define blitz don't support define like function. Does exist similar b3d function code who return a boolean result when triangle is in contact with a box ?

thanks

Ross C

(Posted 2008) [#2]

Wouldn't it be easier to do a line intersect function?

Dreamora

(Posted 2008) [#3]

Mesh intersect ...

Thats the only solution beside doing 3 linepicks (for each side) or doing it really fully mathematical at which point I would recommand creating a userlib from the C++ code for performance reasons.

Jasu	(Posted 2008) [#4]

I'd go with Ross. Use line intersects. I use them alot and they are speedy enough. Just don't use them 'everything against everything'. But only if objects are near enough from each other.

Problem is if you can have a situation where the box can be completely inside the triangle or vice versa. In that case I would use line intersects along with orientation and point-in-triangle functions. The orientation math calculates if a point C is on the left or right side of A to B.

I can provide you the functions if interested. Though I think trying to recode the c++ example to blitz would be more sophisticated. You don't need to have those defines in blitz, just understanding what they do (they don't have to be functions at all). After all, code is just a representation of a solution to a problem. No matter what language it's in.

patmaba

(Posted 2008) [#5]

I'm interested by your function Jasu.

During your post I have try to convert the link but i have problem with the define function.

this is my first step of my translation to bmax code without testing.

Function FINDMINMAX(x0:Float, x1:Float, x2:Float, p_fmin:Float var, p_fmax:Float var) 
  p_fmin = x0
  p_fmax = x0
  If(x1 < p_fmin) Then p_fmin = x1
  If(x1 > p_fmax) Then p_fmax = x1
  If(x2 < p_fmin) Then p_fmin = x2
  If(x2 > p_fmax) Then p_fmax = x2
EndFunction
  
Function planeBoxOverlap:Int(normal:Vector var, d:Float, maxbox:Vector var) 
  Local vmin:Vector = Vector.Create() 
  Local vmax:Vector = Vector.Create() 
  
  If(normal.x > 0.0) 
      vmin.x = -maxbox.x
      vmax.x = maxbox.x
  Else
      vmin.x = maxbox.x
      vmax.x = -maxbox.x
  EndIf

  If(normal.y > 0.0) 
      vmin.y = -maxbox.y
      vmax.y = maxbox.y
  Else
      vmin.y = maxbox.y
      vmax.y = -maxbox.y
  EndIf

  If(normal.z > 0.0) 
      vmin.z = -maxbox.z
      vmax.z = maxbox.z
  Else
      vmin.z = maxbox.z
      vmax.z = -maxbox.z
  EndIf
      
  If(normal.DotP(vmin) + d > 0.0) Then Return 0
  If(normal.DotP(vmax) + d >= 0.0) Then Return 1
  
  Return 0
EndFunction


'======================== X-tests ========================
'#define AXISTEST_X01(a, b, fa, fb)			   \
'	p0 = a*v0[Y] - b*v0[Z];			       	   \
'	p2 = a*v2[Y] - b*v2[Z];			       	   \
'       if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} \
'	rad = fa * boxhalfsize[Y] + fb * boxhalfsize[Z];   \
'	If(min > rad | | max < - rad) Return 0;

Function AXISTEST_X01:Int(a:Float, b:Float, fa:Float, fb:Float, p0:Float, p2:Float, v0:vector, v2:vector, p_fMin:Float, p_fMax:Float, boxhalfsize:Vector) 
	p0 = a * v0.y - b * v0.z
	p2 = a * v2.y - b * v2.z
    If(p0 < p2) 
		p_fMin = p0
		p_fMax = p2
	Else
		p_fMin = p2
		p_fMax = p0
	EndIf
	Local rad:Float = fa * boxhalfsize.y + fb * boxhalfsize.z
	If(p_fMin > rad Or p_fMax < - rad) Then Return 0
EndFunction

'#define AXISTEST_X2(a, b, fa, fb) \
'	p0 = a * v0[Y] - b * v0[Z] ; \
'	p1 = a*v1[Y] - b*v1[Z];			       	   \
 '       if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
'	rad = fa * boxhalfsize[Y] + fb * boxhalfsize[Z];   \
'	if(min>rad || max<-rad) return 0;

Function AXISTEST_X2:Int(a:Float, b:Float, fa:Float, fb:Float, p0:Float, p1:Float, v0:vector var, v1:vector var, p_fMin:Float, p_fMax:Float, boxhalfsize:vector var) 
	p0 = a * v0.y - b * v0.z
	p1 = a * v1.y - b * v1.z
    If(p0 < p1) 
		p_fMin = p0
		p_fMax = p1
	Else
		p_fMin = p1
		p_fMax = p0
	EndIf
	Local rad:Float = fa * boxhalfsize.y + fb * boxhalfsize.z
	If(p_fMin > rad Or p_fMax < - rad) Return 0
EndFunction
'======================== Y-tests ========================
'#define AXISTEST_Y02(a, b, fa, fb)			   \
'	p0 = -a*v0[X] + b*v0[Z];		      	   \
'	p2 = -a*v2[X] + b*v2[Z];	       	       	   \
'        if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} \
'	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Z];   \
'	if(min>rad || max<-rad) return 0;

Function AXISTEST_Y02:Int(a:Float, b:Float, fa:Float, fb:Float, p0:Float, p2:Float, v0:vector var, v2:vector var, p_fMin:Float, p_fMax:Float, boxhalfsize:vector var) 
	p0 = -a * v0.x + b * v0.z
	p2 = -a * v2.x + b * v2.z
    If(p0 < p2) 
		p_fMin = p0
		p_fMax = p2
	Else
		p_fMin = p2
		p_fMax = p0
	EndIf
	Local rad:Float = fa * boxhalfsize.x + fb * boxhalfsize.z
	If(p_fMin > rad Or p_fMax < - rad) Return 0
EndFunction

'#define AXISTEST_Y1(a, b, fa, fb)			   \
'	p0 = -a*v0[X] + b*v0[Z];		      	   \
'	p1 = -a*v1[X] + b*v1[Z];	     	       	   \
'        if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
'	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Z];   \
'	if(min>rad || max<-rad) return 0;

Function AXISTEST_Y1:Int(a:Float, b:Float, fa:Float, fb:Float, p0:Float, p1:Float, v0:vector var, v1:vector var, p_fMin:Float, p_fMax:Float, boxhalfsize:vector var) 
	p0 = -a * v0.x + b * v0.z
	p1 = -a * v1.x + b * v1.z
    If(p0 < p1) 
		p_fMin = p0
		p_fMax = p1
	Else
		p_fMin = p1
		p_fMax = p0
	EndIf
	Local rad:Float = fa * boxhalfsize.x + fb * boxhalfsize.z
	If(p_fMin > rad Or p_fMax < - rad) Then Return 0
EndFunction
'======================== Z-tests ========================

'#define AXISTEST_Z12(a, b, fa, fb)			   \
'	p1 = a*v1[X] - b*v1[Y];			           \
'	p2 = a*v2[X] - b*v2[Y];			       	   \
 '       if(p2<p1) {min=p2; max=p1;} else {min=p1; max=p2;} \
'	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Y];   \
'	if(min>rad || max<-rad) return 0;

Function AXISTEST_Z12:Int(a:Float, b:Float, fa:Float, fb:Float, p1:Float, p2:Float, v1:vector var, v2:vector var, p_fMin:Float, p_fMax:Float, boxhalfsize:vector var) 
	p1 = a * v1.x - b * v1.y
	p2 = a * v2.x - b * v2.y
    If(p2 < p1) 
		p_fMin = p2
		p_fMax = p1
	Else
		p_fMin = p1
		p_fMax = p2
	EndIf
	Local rad:Float = fa * boxhalfsize.x + fb * boxhalfsize.y
	If(p_fMin > rad Or p_fMax < - rad) Then Return 0
EndFunction

	
'#define AXISTEST_Z0(a, b, fa, fb)			   \
'	p0 = a*v0[X] - b*v0[Y];				   \
'	p1 = a*v1[X] - b*v1[Y];			           \
'        if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
'	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Y];   \
'	if(min>rad || max<-rad) return 0;

Function AXISTEST_Z0:Int(a:Float, b:Float, fa:Float, fb:Float, p0:Float, p1:Float, v0:vector var, v1:vector var, p_fMin:Float, p_fMax:Float, boxhalfsize:vector var) 
	p0 = a * v0.x - b * v0.y
	p1 = a * v1.x - b * v1.y
    If(p0 < p1) 
		p_fMin = p0
		p_fMax = p1
	Else
		p_fMin = p1
		p_fMax = p0
	EndIf
	local rad:Float = fa * boxhalfsize.x + fb * boxhalfsize.y
	If(p_fMin > rad Or p_fMax < - rad) Then Return 0
EndFunction

		
Function isTriangleBoxOverlap(p_vBoxcenter:Vector, p_vBoxHalfSize:Vector, p_v0:Vector, p_v1:Vector, p_v2:Vector) 
   ' use separating axis theorem To test overlap between triangle And box 
   '   need to test for overlap in these directions: 
   ' 1) the {x,y,z}-directions (actually, since we use the AABB of the triangle 
   '       we do not even need to test these) 
   '    2) normal of the triangle 
   '    3) crossproduct(edge from tri, {x,y,z}-directin) 
   '       this gives 3x3=9 more tests 
   
   Local l_v0:Vector = Vector.Create() 
   Local l_v1:Vector = Vector.Create() 
   Local l_v2:Vector = Vector.Create() 
   Local l_fMin:Float
   Local l_fMax:Float
   Local d:Float
   Local p0:Float
   Local p1:Float
   Local p2:Float
   Local fex:Float
   Local fey:Float
   Local fez:Float
   Local normal:Vector = Vector.Create() 
   Local e0:Vector = Vector.Create() 
   Local e1:Vector = Vector.Create() 
   Local e2:Vector = Vector.Create() 
   
   ' This is the fastest branch on Sun 
   ' move everything so that the boxcenter is in (0,0,0)
   l_v0 = p_v0.Sub(p_vboxcenter) 
   l_v1 = p_v1.Sub(p_vboxcenter) 
   l_v2 = p_v2.Sub(p_vboxcenter) 

   'compute triangle edges
   e0 = l_v1.sub(l_v0)     ' tri edge 0
   e1 = l_v2.sub(l_v1)        ' tri edge 1
   e2 = l_v0.sub(l_v2)        'tri edge 2 

   ' Bullet 3: '
   ' test the 9 tests first (this was faster) 
   fex = Abs(e0.x) 
   fey = Abs(e0.y) 
   fez = Abs(e0.z) 
   AXISTEST_X01(e0.z, e0.y, fez, fey, p0, p2, l_v0, l_v2, l_fMin, l_fMax, p_vBoxHalfSize) 
   AXISTEST_Y02(e0.z, e0.x, fez, fex, p0, p2, l_v0, l_v2, l_fMin, l_fMax, p_vBoxHalfSize) 
   AXISTEST_Z12(e0.y, e0.x, fey, fex, p1, p2, l_v1, l_v2, l_fMin, l_fMax, p_vBoxHalfSize) 

   fex = Abs(e1.x) 
   fey = Abs(e1.y) 
   fez = Abs(e1.z) 
   AXISTEST_X01(e1.z, e1.y, fez, fey, p0, p2, l_v0, l_v2, l_fMin, l_fMax, p_vBoxHalfSize) 
   AXISTEST_Y02(e1.z, e1.x, fez, fex, p0, p2, l_v0, l_v2, l_fMin, l_fMax, p_vBoxHalfSize) 
   AXISTEST_Z0(e1.y, e1.X, fey, fex, p0, p1, l_v0, l_v1, l_fMin, l_fMax, p_vBoxHalfSize) 

   fex = Abs(e2.X) 
   fey = Abs(e2.Y) 
   fez = Abs(e2.Z) 
   AXISTEST_X2(e2.z, e2.y, fez, fey, p0, p1, l_v0, l_v1, l_fMin, l_fMax, p_vBoxHalfSize) 
   AXISTEST_Y1(e2.z, e2.x, fez, fex, p0, p1, l_v0, l_v1, l_fMin, l_fMax, p_vBoxHalfSize) 
   AXISTEST_Z12(e2.y, e2.x, fey, fex, p1, p2, l_v1, l_v2, l_fMin, l_fMax, p_vBoxHalfSize) 

   ' Bullet 1: 
   '  first test overlap in the {x,y,z}-directions 
   '  find min, max of the triangle each direction, and test for overlap in 
   '  that direction -- this is equivalent to testing a minimal AABB around 
   '  the triangle against the AABB 

   ' test in X-direction 
   FINDMINMAX(l_v0.x, l_v1.X, l_v2.X, l_fMin, l_fMax) ;
   If(l_fMin > p_vBoxhalfsize.x Or l_fMax < - p_vBoxhalfsize.x) Then Return 0

   ' test in Y-direction 
   FINDMINMAX(l_v0.y, l_v1.y, l_v2.y, l_fMin, l_fMax) ;
   If(l_fMin > p_vBoxhalfsize.y Or l_fMax < - p_vBoxhalfsize.y) Then Return 0

   ' test in Z-direction 
   FINDMINMAX(l_v0.z, l_v1.z, l_v2.z, l_fMin, l_fMax) ;
   If(l_fMin > p_vBoxhalfsize.z Or l_fMax < - p_vBoxhalfsize.z) Then Return 0

   ' Bullet 2: 
   '  test if the box intersects the plane of the triangle 
   '  compute plane equation of triangle: normal*x+d=0 
   normal = e0.CrossP(e1) 
   d = -normal.DotP(l_v0)   ' plane eq: normal.x+d=0 
   If(planeBoxOverlap(normal, d, p_vBoxhalfsize) = False) Then Return 0

   Return 1   ' box and triangle overlaps 
End Function

here the vector class

http://www.blitzmax.com/codearcs/codearcs.php?code=1550

Ross C

(Posted 2008) [#6]

Jasu, figuring out if the shape lines with the box should be easy. If all three intersects fail, take any point of the triangle and see if it lies within the bounds of the box. I assume we are talking about 2d shapes here btw :o)

patmaba

(Posted 2008) [#7]

I have merge all functions into a class TriOverlapBox

How to use TriOverlapBox. Easy.
Define the box position and size and your 3 vertices triangle using vector definition.

Like this:

CenterOfBox:Vector = Vector.Create(0, 0, 0) 
BoxHalfSize:Vector = Vector.Create(50, 50, 50) 
TriangleVertex1:Vector = Vector.Create(100, 0, 0) 
TriangleVertex2:Vector = Vector.Create(- 100, 0, 0) 
TriangleVertex3:Vector = Vector.Create(0, 100, 0) 

' Put your vector as parameters
TriOverlapBox.isTriangleBoxOverlap(CenterOfBox, BoxHalfSize, TriangleVertex1, TriangleVertex2, TriangleVertex3)

the function "isTriangleBoxOverlap" return 1 when Triangle overlap your box. Else return 0

All the code is merged into class TriOverlapBox

Type TriOverlapBox
' Date 2007/Jan/06
'
' Class Who test triangle-box intersection 
' Code converted by Patmaba from C code to Bmax code
' http://jgt.akpeters.com/papers/AkenineMoller01/tribox.html
'
' Thanks to Alexx and all members of Blitz3d who help me
' 
' Sample how to use
'CenterOfBox:Vector = Vector.Create(0, 0, 0) 
'BoxHalfSize:Vector = Vector.Create(50, 50, 50) 
'TriangleVertex1:Vector = Vector.Create(100, 0, 0) 
'TriangleVertex2:Vector = Vector.Create(- 100, 0, 0) 
'TriangleVertex3:Vector = Vector.Create(0, 100, 0) 

' Put your vector as parameters
'TriOverlapBox.isTriangleBoxOverlap(CenterOfBox, BoxHalfSize, TriangleVertex1, TriangleVertex2, TriangleVertex3) 	
   Global g_v0:Vector = Vector.Create() 
   Global g_v1:Vector = Vector.Create() 
   Global g_v2:Vector = Vector.Create() 
   Global boxhalfsize:Vector = Vector.Create() 
   Global p0:Float
   Global p1:Float
   Global p2:Float
   Global g_fMin:Float
   Global g_fMax:Float
   	
	Function FINDMINMAX(x0:Float, x1:Float, x2:Float, p_fmin:Float var, p_fmax:Float var) 
  		p_fmin = x0
  		p_fmax = x0
  		If(x1 < p_fmin) Then p_fmin = x1
  		If(x1 > p_fmax) Then p_fmax = x1
  		If(x2 < p_fmin) Then p_fmin = x2
  		If(x2 > p_fmax) Then p_fmax = x2
	EndFunction
  
	Function planeBoxOverlap:Int(normal:Vector var, d:Float, maxbox:Vector var) 
  		Local vmin:Vector = Vector.Create() 
  		Local vmax:Vector = Vector.Create() 
  
  		If(normal.x > 0.0) 
      		vmin.x = -maxbox.x
      		vmax.x = maxbox.x
  		Else
      		vmin.x = maxbox.x
      		vmax.x = -maxbox.x
  		EndIf

  		If(normal.y > 0.0) 
      		vmin.y = -maxbox.y
      		vmax.y = maxbox.y
  		Else
      		vmin.y = maxbox.y
      		vmax.y = -maxbox.y
  		EndIf

  		If(normal.z > 0.0) 
      		vmin.z = -maxbox.z
      		vmax.z = maxbox.z
  		Else
      		vmin.z = maxbox.z
      		vmax.z = -maxbox.z
  		EndIf
      
  		If(normal.DotP(vmin) + d > 0.0) Then Return 0
  		If(normal.DotP(vmax) + d >= 0.0) Then Return 1
  
		Return 0
	EndFunction


	'======================== X-tests ========================
	'#define AXISTEST_X01(a, b, fa, fb)			   \
	'	p0 = a*v0[Y] - b*v0[Z];			       	   \
	'	p2 = a*v2[Y] - b*v2[Z];			       	   \
	'       if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} \
	'	rad = fa * boxhalfsize[Y] + fb * boxhalfsize[Z];   \
	'	If(min > rad | | max < - rad) Return 0;

	Function AXISTEST_X01:Int(a:Float, b:Float, fa:Float, fb:Float) 
		p0 = a * g_v0.y - b * g_v0.z
		p2 = a * g_v2.y - b * g_v2.z
    	If(p0 < p2) 
			g_fMin = p0
			g_fMax = p2
		Else
			g_fMin = p2
			g_fMax = p0
		EndIf
		Local rad:Float = fa * boxhalfsize.y + fb * boxhalfsize.z
		If (g_fMin > rad Or g_fMax < - rad) Then
   			Return 0
		Else
   			Return 1
		End If
	EndFunction

	'#define AXISTEST_X2(a, b, fa, fb) \
	'	p0 = a * v0[Y] - b * v0[Z] ; \
	'	p1 = a*v1[Y] - b*v1[Z];			       	   \
 	'       if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
	'	rad = fa * boxhalfsize[Y] + fb * boxhalfsize[Z];   \
	'	if(min>rad || max<-rad) return 0;

	Function AXISTEST_X2:Int(a:Float, b:Float, fa:Float, fb:Float) 
		p0 = a * g_v0.y - b * g_v0.z
		p1 = a * g_v1.y - b * g_v1.z
    	If(p0 < p1) 
			g_fMin = p0
			g_fMax = p1
		Else
			g_fMin = p1
			g_fMax = p0
		EndIf
		Local rad:Float = fa * boxhalfsize.y + fb * boxhalfsize.z
		If (g_fMin > rad Or g_fMax < - rad) Then
   			Return 0
		Else
   			Return 1
		End If
	EndFunction
	'======================== Y-tests ========================
	'#define AXISTEST_Y02(a, b, fa, fb)			   \
	'	p0 = -a*v0[X] + b*v0[Z];		      	   \
	'	p2 = -a*v2[X] + b*v2[Z];	       	       	   \
	'        if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} \
	'	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Z];   \
	'	if(min>rad || max<-rad) return 0;

	Function AXISTEST_Y02:Int(a:Float, b:Float, fa:Float, fb:Float) 
		p0 = -a * g_v0.x + b * g_v0.z
		p2 = -a * g_v2.x + b * g_v2.z
    	If(p0 < p2) 
			g_fMin = p0
			g_fMax = p2
		Else
			g_fMin = p2
			g_fMax = p0
		EndIf
		Local rad:Float = fa * boxhalfsize.x + fb * boxhalfsize.z
		If (g_fMin > rad Or g_fMax < - rad) Then
   			Return 0
		Else
   			Return 1
		End If
	EndFunction

	'#define AXISTEST_Y1(a, b, fa, fb)			   \
	'	p0 = -a*v0[X] + b*v0[Z];		      	   \
	'	p1 = -a*v1[X] + b*v1[Z];	     	       	   \
	'        if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
	'	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Z];   \
	'	if(min>rad || max<-rad) return 0;

	Function AXISTEST_Y1:Int(a:Float, b:Float, fa:Float, fb:Float) 
		p0 = -a * g_v0.x + b * g_v0.z
		p1 = -a * g_v1.x + b * g_v1.z
    	If(p0 < p1) 
			g_fMin = p0
			g_fMax = p1
		Else
			g_fMin = p1
			g_fMax = p0
		EndIf
		Local rad:Float = fa * boxhalfsize.x + fb * boxhalfsize.z
		If (g_fMin > rad Or g_fMax < - rad) Then
   			Return 0
		Else
   			Return 1
		End If
	EndFunction
	'======================== Z-tests ========================

	'#define AXISTEST_Z12(a, b, fa, fb)			   \
	'	p1 = a*v1[X] - b*v1[Y];			           \
	'	p2 = a*v2[X] - b*v2[Y];			       	   \
 	'       if(p2<p1) {min=p2; max=p1;} else {min=p1; max=p2;} \
	'	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Y];   \
	'	if(min>rad || max<-rad) return 0;

	Function AXISTEST_Z12:Int(a:Float, b:Float, fa:Float, fb:Float) 
		p1 = a * g_v1.x - b * g_v1.y
		p2 = a * g_v2.x - b * g_v2.y
	    If(p2 < p1) 
			g_fMin = p2
			g_fMax = p1
		Else
			g_fMin = p1
			g_fMax = p2
		EndIf
		Local rad:Float = fa * boxhalfsize.x + fb * boxhalfsize.y
		If (g_fMin > rad Or g_fMax < - rad) Then
   			Return 0
		Else
   			Return 1
		End If
	EndFunction

	'#define AXISTEST_Z0(a, b, fa, fb)			   \
	'	p0 = a*v0[X] - b*v0[Y];				   \
	'	p1 = a*v1[X] - b*v1[Y];			           \
	'        if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
	'	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Y];   \
	'	if(min>rad || max<-rad) return 0;
	Function AXISTEST_Z0:Int(a:Float, b:Float, fa:Float, fb:Float) 
		p0 = a * g_v0.x - b * g_v0.y
		p1 = a * g_v1.x - b * g_v1.y
    	If(p0 < p1) 
			g_fMin = p0
			g_fMax = p1
		Else
			g_fMin = p1
			g_fMax = p0
		EndIf
		Local rad:Float = fa * boxhalfsize.x + fb * boxhalfsize.y
		If (g_fMin > rad Or g_fMax < - rad) Then
   			Return 0
		Else
   			Return 1
		End If
	EndFunction

		
	Function isTriangleBoxOverlap(p_vBoxcenter:Vector, p_vBoxHalfSize:Vector, p_triverts0:Vector, p_triverts1:Vector, p_triverts2:Vector) 
   		' use separating axis theorem To test overlap between triangle And box 
   		'   need to test for overlap in these directions: 
   		' 1) the {x,y,z}-directions (actually, since we use the AABB of the triangle 
   		'       we do not even need to test these) 
   		'    2) normal of the triangle 
   		'    3) crossproduct(edge from tri, {x,y,z}-directin) 
   		'       this gives 3x3=9 more tests 
   
   		Local d:Float
   		Local fex:Float
   		Local fey:Float
   		Local fez:Float
   		Local normal:Vector = Vector.Create() 
   		Local e0:Vector = Vector.Create() 
   		Local e1:Vector = Vector.Create() 
   		Local e2:Vector = Vector.Create() 
   
		InitGlobalsVariables() 
   		' This is the fastest branch on Sun * / 
   		' move everything so that the boxcenter is in (0,0,0) */
   		'SUB(v0,triverts[0],boxcenter);
   		'SUB(v1,triverts[1],boxcenter);
   		'SUB(v2,triverts[2],boxcenter);
   		g_v0 = p_triverts0.Sub(p_vboxcenter) 
   		g_v1 = p_triverts1.Sub(p_vboxcenter) 
   		g_v2 = p_triverts2.Sub(p_vboxcenter) 

   
   		' compute triangle edges */
   		'SUB(e0,v1,v0);      /* tri edge 0 */
   		'SUB(e1,v2,v1);      /* tri edge 1 */
   		'SUB(e2,v0,v2);      /* tri edge 2 */   
   		' This is the fastest branch on Sun 
   		' move everything so that the boxcenter is in (0,0,0)

   		'compute triangle edges
   		e0 = g_v1.sub(g_v0)         ' tri edge 0
   		e1 = g_v2.sub(g_v1)          ' tri edge 1
   		e2 = g_v0.sub(g_v2)          'tri edge 2 

   		' Bullet 3: '
   		' test the 9 tests first (this was faster) 
		'   fex = fabs(e0[X] ) ;
		'   fey = fabs(e0[Y]);
		'   fez = fabs(e0[Z]);
		'   AXISTEST_X01(e0[Z], e0[Y], fez, fey);
		'   AXISTEST_Y02(e0[Z], e0[X], fez, fex);
		'   AXISTEST_Z12(e0[Y], e0[X], fey, fex);   
   		fex = Abs(e0.x) 
   		fey = Abs(e0.y) 
   		fez = Abs(e0.z) 

   		If AXISTEST_X01(e0.z, e0.y, fez, fey) = 0 Then Return 0
   		If AXISTEST_Y02(e0.z, e0.x, fez, fex) = 0 Then Return 0
   		If AXISTEST_Z12(e0.y, e0.x, fey, fex) = 0 Then Return 0

   		fex = Abs(e1.x) 
   		fey = Abs(e1.y) 
   		fez = Abs(e1.z) 
   		If AXISTEST_X01(e1.z, e1.y, fez, fey) = 0 Then Return 0
   		If AXISTEST_Y02(e1.z, e1.x, fez, fex) = 0 Then Return 0
   		If AXISTEST_Z0(e1.y, e1.X, fey, fex) = 0 Then Return 0

   		fex = Abs(e2.X) 
   		fey = Abs(e2.Y) 
   		fez = Abs(e2.Z) 
   		If AXISTEST_X2(e2.z, e2.y, fez, fey) = 0 Then Return 0
   		If AXISTEST_Y1(e2.z, e2.x, fez, fex) = 0 Then Return 0
   		If AXISTEST_Z12(e2.y, e2.x, fey, fex) = 0 Then Return 0

   		' Bullet 1: 
   		'  first test overlap in the {x,y,z}-directions 
   		'  find min, max of the triangle each direction, and test for overlap in 
   		'  that direction -- this is equivalent to testing a minimal AABB around 
   		'  the triangle against the AABB 

   		' test in X-direction 
   		FINDMINMAX(g_v0.x, g_v1.X, g_v2.X, g_fMin, g_fMax) 
   		If(g_fMin > p_vBoxhalfsize.x Or g_fMax < - p_vBoxhalfsize.x) Then Return 0
		
   		' test in Y-direction 
   		FINDMINMAX(g_v0.y, g_v1.y, g_v2.y, g_fMin, g_fMax) 
   		If(g_fMin > p_vBoxhalfsize.y Or g_fMax < - p_vBoxhalfsize.y) Then Return 0

   		' test in Z-direction 
   		FINDMINMAX(g_v0.z, g_v1.z, g_v2.z, g_fMin, g_fMax) ;
   		If(g_fMin > p_vBoxhalfsize.z Or g_fMax < - p_vBoxhalfsize.z) Then Return 0

   		' Bullet 2: 
   		'  test if the box intersects the plane of the triangle 
   		'  compute plane equation of triangle: normal*x+d=0 
   		normal = e0.CrossP(e1) 
   		d = -normal.DotP(g_v0)     ' plane eq: normal.x+d=0 
   		If(planeBoxOverlap(normal, d, p_vBoxhalfsize) = False) Then Return 0

   		Return 1   ' box and triangle overlaps 		
	End Function

	Function InitGlobalsVariables() 
		g_v0:Vector = Vector.Create() 
		g_v1:Vector = Vector.Create() 
		g_v2:Vector = Vector.Create() 
		boxhalfsize:Vector = Vector.Create() 
		p0 = 0.0
		p1 = 0.0
		p2 = 0.0
		g_fMin = 0.0
		g_fMax = 0.0
	End Function
End Type

Post any comment if you encounter error, please

Jasu	(Posted 2008) [#8]

I added my functions to the code archives.
http://www.blitzbasic.com/codearcs/codearcs.php?code=2180

For determening if a point is in a triangle, use to one by Rob Farley that was already there. That's what I'm using.
http://www.blitzbasic.com/codearcs/codearcs.php?code=1992