Ray->Box intersection

Blitz3D Forums/Blitz3D Programming/Ray->Box intersection

bytecode77(Posted 2007) [#1]
hi!
continuing from this thread:http://www.blitzbasic.com/Community/posts.php?topic=71628

i suppose the old thread is to full to ask more questions, so i opened a nwe one.

this is a ray->box intersection routine.
http://www.blitzbasic.com/codearcs/codearcs.php?code=1029

it works properly except that the intersection POINT is not calculated. what i need to calculate is the intersection point. since i dont know how cube picking works...
also i need the picking not to pick "backwards" and not to be infinite
i need your help :)

i will be thankful for any help i get from you :)


bytecode77(Posted 2007) [#2]
please. i need some help :(
i'm in class 10 school, and we didnt have this kind of maths yet ;(


sswift(Posted 2007) [#3]
See: CLIP_Line_Intersect_Plane()

; -----------------------------------------------------------------------------------------------------------------------------------
; PolyClip - Swift Polygon Clipping System - Copyright 2004 Shawn Swift
; -----------------------------------------------------------------------------------------------------------------------------------
;
; Find out more about my shadow, and other systems, here:
;
; 	Shadows, Terrains, GUI/HUD/2D Overlays in 3D:
; 	http://www.blitzbasic.com/logs/userlog.php?user=963&log=147
;
; 	2D sprite system for all versions of Blitz with five blending modes including alpha, add, and multiply:
; 	http://www.blitzbasic.com/toolbox/toolbox.php?tool=58
;
; I accept payment via Paypal, Western Union, personal checks made out in US dolalrs, and bank transfers.
; Paypal is the preffered method.  If you wish to pay via paypal, send payment to scswift@...
;
; -----------------------------------------------------------------------------------------------------------------------------------
;
; This system supports polygons with any number of sides, but it defaults to a max of 4 sides per input poly.  The output polygons
; may have up to 10 sides.  Change the constant CLIP_MAX_POLY_SIDES to increase the number of sides you can use on input polygons.
; And keep in mind that if you clip a polygon and then re-input it into the system for additional clipping, you'll have to make
; sure that CLIP_MAX_POLY_SIDES is large enough to support the potentially much larger resulting polygon.
;
; The system also defaults to allowing only six clipping planes, which may not be enough if you want to clip polygons against shapes
; other than cubes.  Again, increasing CLIP_MAX_POLY_SIDES will increase this value.  See CLIP_MAX_POLY_SIDES for more details.
;
;
; What can you do with this system?
;
; 1. Cut a polygon with a plane, returning only the half on the inside side of the plane. (Side facimg away from plane's normal)
; 2. Clip a polygon to the viewport by specifying a iew frustrum with 4, 5 or 6 planes.
; 3. Quickly determine if an individual triangle is in a frustrum or other polyhedra formed by planes, without having to set up 
;    a polygon or delete the returned data.
;
; Instructions:
;
; 	If you want to clip a polygon, create some planes like so:
;
; 		TopPlane.CLIP_Plane = CLIP_CreatePlane(A#, B#, C#, D#)
;
; 	Then create a polygon like this:
;	
;		ThisPoly.CLIP_Poly = CLIP_CreateTri(X1#, Y1#, Z1#, X2#, Y2#, Z2#, X3#, Y3#, Z3#)
;
; 		Or, create one manually with the CLIP_CreatePoly() and CLIP_AddVertex() commands.
;		You can also adjust the values for a vertex.  If a polygon has 4 vertcies, you can index them with the values 0..3.
;		AddVertex also returns the index number of the most recently created vertex if you would like to use that.
;
;	Why set the normal, color, alpha, or texture coordinates of a vertex?
;
;	When the system clips a polygon, it creates a new polygon, sometimes with additional vertices. 	By specifying these values,
; 	you can have all of them automaitcally interpolated and computed for all the vertices in the new polyon!
;
;	And finally, call ClipPoly to clip an individual polygon, or ClipPolys to clip all polygons at once.
;
;	You can also skip the polygon creation steps and test tris against a region bounded by planes with CLIP_TriInFrustum().
;
; -----------------------------------------------------------------------------------------------------------------------------------
;
; This system uses the Sutherland-Hodgeman polygon clipping algorithm.  
;
; Here is some pseudocode that describes the algorithm:
;
;
;	 	CURRENT_POLYGON = Polygon to be clipped.
;
; 		For each plane in the frustum:
;
; 			For each pair of vertices (v1,v2) forming an edge of CURRENT_POLYGON:
;
;				(Inside means a vertex is on the side of the current plane that faces away from the plane's normal.)
;
; 				If v1 inside,  v2 inside  = output v2
; 				If v1 inside,  v2 outside = output intersection
; 				If v1 outside, v2 outside = no output
; 				If v1 outside, v2 inside  = output v2 and intersection
;
;			Next
;
;			CURRENT_POLYGON = Polygon formed by vertcies output from for loop.
;			If no vertcies in CURRENT_POLYGON exit loop.
;
;	 	Next
;
;		Resulting polygon is clipped to frustum.  
;
;		Returned points will have same winding as input points.  In other words, if input polygon is wound counterclockwise,
; 		resulting polygon will also have its vertices wound counterclockwise.
;
; 		If no vertices in resulting polygon, polygon was completely outside frustum.
;
; -----------------------------------------------------------------------------------------------------------------------------------
;
; Rather than use this system to do all your clipping as-is, you should use it in conjunction with a hash-table using
; "clipping flags" for each vertex, and use that to determine if you should send the triangle to this system.  You can do the
; vertex text with the CLIP_Point_Inside_Plane() function after you have set up your planes.
;
; Read this article for more info:
; http://www.gamasutra.com/features/19990507/polygon_clipping_01.htm
;
; -----------------------------------------------------------------------------------------------------------------------------------


; CLIP_MAX_POLY_SIDES is the maximum number of sides a polygon can have. 
; It must ALWAYS be larger than the total number of sides on the polygons you input into the system!
;
; You can calculate this number like so:  (Max sides on input polygon) + (Max number of clipping planes)
;
; The default value of 10 assumes that the input polygon will have 3 or 4 sides, (tri or quad) and that there will be 
; a maximum of 6 clipping planes.
Const CLIP_MAX_POLY_SIDES = 10


Type CLIP_Plane

	Field A#	
	Field B#
	Field C#
	Field D#

End Type


; 564 bytes
Type CLIP_Poly
	
	Field Vertices
	
	Field Vx#[CLIP_MAX_POLY_SIDES]
	Field Vy#[CLIP_MAX_POLY_SIDES]
	Field Vz#[CLIP_MAX_POLY_SIDES]
	
	Field Vnx#[CLIP_MAX_POLY_SIDES]
	Field Vny#[CLIP_MAX_POLY_SIDES]
	Field Vnz#[CLIP_MAX_POLY_SIDES]
		
	Field Vu0#[CLIP_MAX_POLY_SIDES]
	Field Vv0#[CLIP_MAX_POLY_SIDES]
	Field Vu1#[CLIP_MAX_POLY_SIDES]
	Field Vv1#[CLIP_MAX_POLY_SIDES]

	Field Vr#[CLIP_MAX_POLY_SIDES]
	Field Vg#[CLIP_MAX_POLY_SIDES]
	Field Vb#[CLIP_MAX_POLY_SIDES]
	
	Field Va#[CLIP_MAX_POLY_SIDES]
	
End Type	


; These variables will contain the output from CLIP_Line_Intersect_Plane()
Global CLIP_Intersect_X#
Global CLIP_Intersect_Y#
Global CLIP_Intersect_Z#
Global CLIP_Intersect_U#

; These variables will contain the output from CLIP_InterpolateNormal()
Global CLIP_Normal_X#
Global CLIP_Normal_Y#
Global CLIP_Normal_Z#

; These variables will contain the output from CLIP_CalculateTriPlane() and CLIP_Calculate2DLine().
Global CLIP_A#
Global CLIP_B#
Global CLIP_C#
Global CLIP_D#

; These variables will contain the output from CLIP_CalculateTriNormal()
Global POLY_Temp.CLIP_Poly = New CLIP_Poly


; -----------------------------------------------------------------------------------------------------------------------------------
; This function creates a new clipping plane with the specified plane equation.
;
; Returns a pointer to the plane, but you don't need to save it because there is no function in the system you need to pass 
; that pointer to.  It is just there for future expansion. 
;
; Use CLIP_FreePlanes() to free all the planes you've created when you're done with them and want to make new ones.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_CreatePlane.CLIP_Plane(A#, B#, C#, D#)

	Local NewPlane.CLIP_Plane
	
	NewPlane = New CLIP_Plane

	NewPlane\A# = A#
	NewPlane\B# = B#
	NewPlane\C# = C#
	NewPlane\D# = D#
	
	Return NewPlane
	
End Function	


; -----------------------------------------------------------------------------------------------------------------------------------
; This function creates a new triangle and returns a pointer to it.
;
; It does not matter if polygons in this system are wound clockwise or counterclockwise.
; They are all clipped the same, and the resulting polygon will have the same winding as the original.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_CreateTri.CLIP_Poly(X1#, Y1#, Z1#, X2#, Y2#, Z2#, X3#, Y3#, Z3#)

	Local NewPoly.CLIP_Poly
	
	NewPoly = New CLIP_Poly
	
	CLIP_AddVertex(NewPoly, X1#, Y1#, Z1#)
	CLIP_AddVertex(NewPoly, X2#, Y2#, Z2#)
	CLIP_AddVertex(NewPoly, X3#, Y3#, Z3#)
	
	Return NewPoly
	
End Function	
	

; -----------------------------------------------------------------------------------------------------------------------------------
; This function creates a new quad and returns a pointer to it.
;
; It does not matter if polygons in this system are wound clockwise or counterclockwise.
; They are all clipped the same, and the resulting polygon will have the same winding as the original.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_CreateQuad.CLIP_Poly(X1#, Y1#, Z1#, X2#, Y2#, Z2#, X3#, Y3#, Z3#, X4#, Y4#, Z4#)

	Local NewPoly.CLIP_Poly
	
	NewPoly = New CLIP_Poly
	
	CLIP_AddVertex(NewPoly, X1#, Y1#, Z1#)
	CLIP_AddVertex(NewPoly, X2#, Y2#, Z2#)
	CLIP_AddVertex(NewPoly, X3#, Y3#, Z3#)
	CLIP_AddVertex(NewPoly, X4#, Y4#, Z4#)
	
	Return NewPoly
	
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function creates a new polygon and returns a pointer to it.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_CreatePoly.CLIP_Poly()
	Return New CLIP_Poly
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function adds a vertex to a polygon, and returns its index number.
;
; Vertices must be added in order, and if wound in a clockwise direction the face normal will point towards you.
;
; Vertex indices range from 0 to vertices-1.
;
; Poly is the polygon to add the vertex to.
; XYZ is the vertex position. (Optional)
; Vertex color defaults to 255,255,255.
; Vertex alpha defaults to 1. 
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_AddVertex(Poly.CLIP_poly, X#=0, Y#=0, Z#=0)

	Local Index
	
	Index = Poly\Vertices
	Poly\Vertices = Poly\Vertices + 1
	
	Poly\Vx#[Index] = X#
	Poly\Vy#[Index] = Y#
	Poly\Vz#[Index] = Z#
	
	Poly\Vr#[Index] = 255
	Poly\Vg#[Index] = 255
	Poly\Vb#[Index] = 255
	
	Poly\Va#[Index] = 1
	
	Return Index

End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function sets the position of a vertex.
;
; Poly is the poly which contains the vertex.
; Index is the vertex index returned from CLIP_AddVertex().
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_SetVertexPosition(Poly.CLIP_Poly, Index, X#, Y#, Z#)

	Poly\Vx#[Index] = X#
	Poly\Vy#[Index] = Y#
	Poly\Vz#[Index] = Z#
	
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function sets the normal of a vertex.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_SetVertexNormal(Poly.CLIP_Poly, Index, Nx#, Ny#, Nz#)

	Poly\Vnx#[Index] = Nx#
	Poly\Vny#[Index] = Ny#
	Poly\Vnz#[Index] = Nz#
	
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function sets the texture coordinates of a vertex.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_SetVertexUV(Poly.CLIP_Poly, Index, U#, V#, Coord_Set=0)

	If Coord_Set = 0
		Poly\Vu0#[Index] = U#
		Poly\Vv0#[Index] = V#
	Else
		Poly\Vu1#[Index] = U#
		Poly\Vv1#[Index] = V#
	EndIf	
	
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function sets the color of a vertex.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_SetVertexColor(Poly.CLIP_Poly, Index, R#, G#, B#)

	Poly\Vr#[Index] = R#
	Poly\Vg#[Index] = G#
	Poly\Vb#[Index] = B#

End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function sets the alpha of a vertex.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_SetVertexAlpha(Poly.CLIP_Poly, Index, Alpha#)

	Poly\Va#[Index] = Alpha#

End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function gets the position of a vertex.
; Set XYZ to 0 if you want the X component, 1 for Y, and 2 for Z.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_GetVertexPosition#(Poly.CLIP_Poly, Index, XYZ)
	
	Select XYZ
		Case 0 Return Poly\Vx#[Index]
		Case 1 Return Poly\Vy#[Index]
		Case 2 Return Poly\Vz#[Index]
	End Select
	
End Function

; -----------------------------------------------------------------------------------------------------------------------------------
; This function gets the normal of a vertex.
; Set XYZ to 0 if you want the X component, 1 for Y, and 2 for Z.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_GetVertexNormal#(Poly.CLIP_Poly, Index, XYZ)
	
	Select XYZ
		Case 0 Return Poly\Vnx#[Index]
		Case 1 Return Poly\Vny#[Index]
		Case 2 Return Poly\Vnz#[Index]
	End Select
	
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function gets the texture coordinates of a vertex.
;
; Set UV to 0 to get the U component, and 1 to get the V.
; Set Coord_Set to 0 to get the first set of UV coordinates, and 1 to get the second.  (Optional)
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_GetVertexUV#(Poly.CLIP_Poly, Index, UV, Coord_Set=0)

	If Coord_Set = 0
		If UV = 0 Then Return Poly\Vu0#[Index] 
		If UV = 1 Then Return Poly\Vv0#[Index] 
	Else
		If UV = 0 Then Return Poly\Vu1#[Index] 
		If UV = 1 Then Return Poly\Vv1#[Index] 
	EndIf	
	
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function gets the color of a vertex.
;
; Set RGB to 0 if you want the R component, 1 for G, and 2 for B.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_GetVertexColor#(Poly.CLIP_Poly, Index, RGB)
	
	Select RGB
		Case 0 Return Poly\Vr#[Index]
		Case 1 Return Poly\Vg#[Index]
		Case 2 Return Poly\Vb#[Index]
	End Select

End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function gets the alpha of a vertex.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_GetVertexAlpha#(Poly.CLIP_Poly, Index)
	Return Poly\Va#[Index]
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function deletes all planes that have been added to the system.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_FreePlanes()

	Local LOOP_Plane.CLIP_Plane

	For LOOP_Plane = Each CLIP_Plane
		Delete LOOP_Plane
	Next

End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function deletes all polygons that have been added to the system.
; CLIP_TriInFrustum does NOT leave any polygons lying around that you need to delete later.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_FreePolys()

	Local LOOP_Poly.CLIP_Poly

	For LOOP_Poly = Each CLIP_Poly
		Delete LOOP_Poly
	Next

	; Recreate the polygon that we use for scratch.
	POLY_Temp = New CLIP_Poly

End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function frees Kevin Mitnick and returns a pointer to a high profile computer security job.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_FreeKevinMitnick()
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function returns TRUE if the specified triangle is intersecting/inside the region bounded by the clipping planes.
; CLIP_TriInFrustum does NOT leave any polygons lying around that you need to delete later.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_TriInFrustum(X1#, Y1#, Z1#, X2#, Y2#, Z2#, X3#, Y3#, Z3#)

	Local POLY_Input.CLIP_Poly
	
	; Do a quick but inaccurate test first.
	; If this test is positive, triangle MAY be inside frustum.
	If CLIP_FastTriInFrustum(X1#, Y1#, Z1#, X2#, Y2#, Z2#, X3#, Y3#, Z3#) 
	
		; Quick test says triangle MAY be inside frustum. 
		; Do slower, accurate test.
		
		; Create the triangle.
	
			POLY_Input = New CLIP_Poly
		
			POLY_Input\Vertices = 3

			POLY_Input\Vx#[0] = X1#
			POLY_Input\Vy#[0] = Y1#
			POLY_Input\Vz#[0] = Z1#

			POLY_Input\Vx#[1] = X2#
			POLY_Input\Vy#[1] = Y2#
			POLY_Input\Vz#[1] = Z2#

			POLY_Input\Vx#[2] = X3#
			POLY_Input\Vy#[2] = Y3#
			POLY_Input\Vz#[2] = Z3#
	
		; Clip the triangle.
	
			CLIP_ClipPoly(POLY_Input, False)
	
		; Was the polygon in the frustum?

			If POLY_Input\Vertices > 0 

				; Poly has vertices. 
				; Tri was inside or intersecting the frustum.
				Delete POLY_Input
				Return True
			
			Else
		
				; Poly has no vertices. 
				; Tri was completely outside the frustum.
			 	Delete POLY_Input
				Return False
			
			EndIf

	Else

		; Quick test says triangle was DEFINITELY outside the frustum.
		Return False
		
	EndIf
	
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function is a fast test that returns TRUE if a triangle is MIGHT be in a frustum. 
; Note that this test is INACCURATE, and will only tell you for sure that a triangle is NOT in the frustum.
; A more accurate test needs to be done after to say for sure that the triangle IS in the frustum.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_FastTriInFrustum(X1#, Y1#, Z1#, X2#, Y2#, Z2#, X3#, Y3#, Z3#)

	Local LOOP_Plane.CLIP_Plane
	Local A#, B#, C#, D#
	
	For LOOP_Plane = Each CLIP_Plane
	
		A# = LOOP_Plane\A#
		B# = LOOP_Plane\B#
		C# = LOOP_Plane\C#
		D# = LOOP_Plane\D#
	
		; Are all three vertcies of this triangle outside this plane?
		If (X1#*A# + Y1#*B# + Z1#*C# + D#) > 0
			If (X2#*A# + Y2#*B# + Z2#*C# + D#) > 0
				If (X3#*A# + Y3#*B# + Z3#*C# + D#) > 0
					
					; Yes.
					; Triangle is DEFINITELY outside frustum!
					Return False
					
				EndIf
			EndIf
		EndIf
		
	Next
	
	; Triangle MAY be inside frustum, but we can't be sure.
	Return True
	
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function is a fast test that returns TRUE if a triangle is MIGHT be in a frustum. 
; Note that this test is INACCURATE, and will only tell you for sure that a triangle is NOT in the frustum.
; A more accurate test needs to be done after to say for sure that the triangle IS in the frustum.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_FastPolyInFrustum(Poly.CLIP_poly)

	Local LOOP_Plane.CLIP_Plane
	Local A#, B#, C#, D#
	Local LOOP_Vertex
	Local Outside
	
	For LOOP_Plane = Each CLIP_Plane
	
		Outside = True
	
		; For each vertex in the polygon...
		For LOOP_Vertex = 0 To Poly\Vertices-1
	
			; Is this vertex inside this plane?
			If (Poly\Vx#[LOOP_Vertex]*LOOP_Plane\A# + Poly\Vy#[LOOP_Vertex]*LOOP_Plane\B# + Poly\Vz#[LOOP_Vertex]*LOOP_Plane\C# + LOOP_Plane\D#) < 0
				
				; Vertex is inside plane.
				; Polygon cannot be outside this plane.  Skip rest of vertices, and check poly against next plane.
				Outside = False
				Exit
			
			Else
			
				; Vertex is outside plane.
				
			EndIf
				
		Next
		
		If Outside
			
			; All vertcies were outside the last plane.
			; Polygon is DEFINITELY outside frustum.
			Return False
			
		EndIf
		
	Next
	
	; Polygon was not outside any planes.  
	; Polygon MAY be inside frustum, but we can't be sure.
	Return True
	
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function returns the distance of a point from a plane.
;
; If the point is in front of the plane, this distance will be positive.
; If the vertex is behind the plane, the distance will be negative.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_Point_Distance_From_Plane(X#, Y#, Z#, A#, B#, C#, D#)

	Return (X#*A# + Y#*B# + Z#*C# + D#)

End Function 


; -----------------------------------------------------------------------------------------------------------------------------------
; This function returns true if a point is on the back side of a plane.
; A plane's front side is the direction in which its normal points.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_Point_Inside_Plane(X#, Y#, Z#, A#, B#, C#, D#)

	If (X#*A# + Y#*B# + Z#*C# + D#) < 0 Then Return True
	Return False

End Function 


; -----------------------------------------------------------------------------------------------------------------------------------
; This function returns TRUE if the specified sphere is intersecting/inside the region bounded by the clipping planes.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_PointInFrustum(X#, Y#, Z#)

	Local LOOP_Plane.CLIP_Plane

	; For each clipping plane...	
	For LOOP_Plane = Each CLIP_Plane
		If Not ((X#*LOOP_Plane\A# + Y#*LOOP_Plane\B# + Z#*LOOP_Plane\C# + LOOP_Plane\D#) < 0) Then Return False
	Next
	
	Return True

End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function returns true if a sphere is intersecting or behind the specified plane.
;
; XYZ    = Sphere center
; Radius = Sphere radius
; ABCD   = Plane equation
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_Sphere_Inside_Plane(X#, Y#, Z#, Radius#, A#, B#, C#, D#)

	If (X#*A# + Y#*B# + Z#*C# + D#) < Radius# Then Return True
	Return False

End Function 


; -----------------------------------------------------------------------------------------------------------------------------------
; This function returns TRUE if the specified sphere is intersecting/inside the region bounded by the clipping planes.
;
; This function is sloppy.  While it finds all spheres inside/intersecting the region, it may also give false positives for 
; some spheres outside the region but near it's corners.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_SphereInFrustum(X#, Y#, Z#, Radius#)

	Local LOOP_Plane.CLIP_Plane
	Local A#, B#, C#, D#

	; For each clipping plane...	
	For LOOP_Plane = Each CLIP_Plane

		; Store this clipping plane's equation.
		A# = LOOP_Plane\A#
		B# = LOOP_Plane\B#
		C# = LOOP_Plane\C#
		D# = LOOP_Plane\D#

		If Not CLIP_Sphere_Inside_Plane(X#, Y#, Z#, Radius#, A#, B#, C#, D#) Then Return False
		
	Next
	
	Return True

End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function takes a line segment and a plane as input, and outputs:
;
; 1. The global position at which the line intersects the plane, in CLIP_Intersect_XYZ#.
;
; 2. The line-relative position, in CLIP_Intersect_U#, where a value of 0..1 means the intersection point lies between V1 and V2,
;    and a value less than 0 or greater than 1 means the intersection occured at a location outside the line segment.
;
; 3. TRUE if the line intersects the plane, and FALSE if the line runs near-parralel to the plane.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_Line_Intersect_Plane(V1x#, V1y#, V1z#, V2x#, V2y#, V2z#, Pa#, Pb#, Pc#, Pd#)

	Local Nx#, Ny#, Nz#
	Local Dot#
		
	; Calculate the normal of the line.
	Nx# = V2x#-V1x#
	Ny# = V2y#-V1y#
	Nz# = V2z#-V1z#

	; Calculate the dot product of the line's normal and the plane's normal.
	Dot# = Pa#*Nx# + Pb#*Ny# + Pc#*Nz#

	; If the line is nearly parralel to the plane, they do not intersect.
	If (Abs(Dot#) < 0.0001) Then Return False	

	; Calculate the position on the line where the plane intersects it.
 	CLIP_Intersect_U# = -(Pd# + Pa#*V1x# + Pb#*V1y# + Pc#*V1z#) / Dot#
	CLIP_Intersect_X# = V1x# + CLIP_Intersect_U#*Nx#
	CLIP_Intersect_Y# = V1y# + CLIP_Intersect_U#*Ny#
	CLIP_Intersect_Z# = V1z# + CLIP_Intersect_U#*Nz#
    
	; Line intersects the plane.  
	Return True

End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function clips the specified polygon with the planes you have created. 
; The original polygon's data is overwritten with the new clipped polygon.
;
; If the resulting polygon has 0 vertices, then the polygon was completely outside the region bounded by the clipping planes.
;
; Note:
; You can even call this function with a single clipping plane specified, and the polygon will be cut by that plane. 
; The half which was on the inside side of the plane will be the polygon that is returned.
;
; The Fast flag allows you to enable to disable the interpolation of vertex appearance information.
; In other words, the final output polygon will have incorrect colors, normals, texture coordinates, and alpha.
; Even the original vertices will have these properties wiped out.
; The positions, however, will be correct.
;
; FAST mode is intended for use when you need to test to see if a polygon is in a frustum, but you don't care if those other
; properties are interpolated.  
;
; You should also call CLIP_FastPolyInFrustum() before calling this function to check to see if the polygon is wholly outside
; the frustum, and should not be clipped at all.
;
; IMPORTANT NOTE!
; There may be a bug with interpolating UV coordinates in this function, or in the InterpolatedVertex function.
; I was getting some UV glitches and I cannot find the bug in these two functions, if there even is one.
; All other interpolations seem to work fine.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_ClipPoly(POLY_Clip.CLIP_Poly, Fast=False)	

	Local POLY_Input.CLIP_Poly, POLY_Output.CLIP_Poly, POLY_Swap.CLIP_Poly
	Local LOOP_Plane.CLIP_Plane
	Local LOOP_Vertex
	Local V1_Index, V2_Index, VI_Index, VN_Index
	Local V1_Inside, V2_Inside
	Local Vertices
	
	; Set up the input/output buffer pointers.	
		POLY_Input  = POLY_Clip
		POLY_Output = POLY_Temp	

	; For each clipping plane...	
	For LOOP_Plane = Each CLIP_Plane
				
		; Clear all vertcies from the output polygon.
		POLY_Output\Vertices = 0
		
		; Is the first vertex on the backside of the clipping plane?
		V1_Inside = CLIP_Vertex_Inside_Plane(POLY_Input, 0, LOOP_Plane)
				
		; For each edge in the input polygon...
		For LOOP_Vertex = 0 To POLY_Input\Vertices-1

			; Calculate the vertices that form this edge.

				V1_Index = LOOP_Vertex
				V2_Index = LOOP_Vertex+1
		
				If V2_Index = POLY_Input\Vertices Then V2_Index = 0
				
			; Is the endpoint of this edge on the back side of the clipping plane?
			V2_Inside = CLIP_Vertex_Inside_Plane(POLY_Input, V2_Index, LOOP_Plane)
		
			Select True

				; Output V2.			
				Case ((V1_Inside=True) And (V2_Inside=True))
			
					; Add V2 (endpoint of edge) to output polygon.
					
					If Fast
					
						; Create a new vertex in the destination polygon and copy only the vertex's position.
						VN_Index = POLY_Output\Vertices
						POLY_Output\Vertices = POLY_Output\Vertices + 1
	
						POLY_Output\Vx#[VN_Index] = POLY_Input\Vx#[V2_Index]
						POLY_Output\Vy#[VN_Index] = POLY_Input\Vy#[V2_Index]
						POLY_Output\Vz#[VN_Index] = POLY_Input\Vz#[V2_Index]
					
					Else	
						
						; Create a new vertex in the destination polygon and copy all properties.	
						CLIP_CopyVertex(POLY_Input, V2_Index, POLY_Output)
						
					EndIf

				; Output intersection point.	
				Case ((V1_Inside=True) And (V2_Inside=False))

					; Find the point at which the edge intersects this plane.
					CLIP_Edge_Intersect_Plane(POLY_Input, V1_Index, V2_Index, LOOP_Plane)
				
					; Add intersection point.
					If Fast 

						VN_Index = POLY_Output\Vertices
						POLY_Output\Vertices = POLY_Output\Vertices + 1
	
						POLY_Output\Vx#[VN_Index] = CLIP_Intersect_X#
						POLY_Output\Vy#[VN_Index] = CLIP_Intersect_Y#
						POLY_Output\Vz#[VN_Index] = CLIP_Intersect_Z#

					Else
					
						CLIP_Add_Interpolated_Vertex(POLY_Input, V1_Index, V2_Index, CLIP_Intersect_U#, POLY_Output)
					
					EndIf

				; No output.	
				Case ((V1_Inside=False) And (V2_Inside=False))
			
					; Both vertcies are on the outside side of the plane. 
					; Don't add any vertices to the polygon.
		
			
				; Output Intersection point and V2.
				Case ((V1_Inside=False) And (V2_Inside=True))

					; Find the point at which the edge intersects this plane.
					CLIP_Edge_Intersect_Plane(POLY_Input, V1_Index, V2_Index, LOOP_Plane)

					; Add intersection point.
					If Fast 

						VN_Index = POLY_Output\Vertices
						POLY_Output\Vertices = POLY_Output\Vertices + 1
	
						POLY_Output\Vx#[VN_Index] = CLIP_Intersect_X#
						POLY_Output\Vy#[VN_Index] = CLIP_Intersect_Y#
						POLY_Output\Vz#[VN_Index] = CLIP_Intersect_Z#

					Else
					
						CLIP_Add_Interpolated_Vertex(POLY_Input, V1_Index, V2_Index, CLIP_Intersect_U#, POLY_Output)
					
					EndIf

					
					; Add V2.
					If Fast
					
						; Create a new vertex in the destination polygon and copy only the vertex's position.
						VN_Index = POLY_Output\Vertices
						POLY_Output\Vertices = POLY_Output\Vertices + 1
	
						POLY_Output\Vx#[VN_Index] = POLY_Input\Vx#[V2_Index]
						POLY_Output\Vy#[VN_Index] = POLY_Input\Vy#[V2_Index]
						POLY_Output\Vz#[VN_Index] = POLY_Input\Vz#[V2_Index]
					
					Else	
						
						; Create a new vertex in the destination polygon and copy all properties.	
						CLIP_CopyVertex(POLY_Input, V2_Index, POLY_Output)
						
					EndIf
														
			End Select 		

			; V2 will be the start of next edge, V1, so since we already checked it, use it's state in the next loop for V1.
			V1_Inside = V2_Inside

		Next
	
		; If there are no vertices in the final polygon...
		If POLY_Output\Vertices = 0
		
			; The polygon has been completely clipped away.
					
			; Delete all vertices from the original polygon, delete the temporary storage buffer, and exit the function early.
			POLY_Clip\Vertices = 0
			Return
			
		EndIf	

		; Swap the pointers to the input polygon data and the output polygon data
		; This makes the output data from the last loop the input data to the next,
		; and uses the old input location to store the new output data.
		POLY_Swap   = POLY_Output
		POLY_Output = POLY_Input
		POLY_Input  = POLY_Swap
		
	Next	

	; If we've made it this far, we have a clipped polygon that lies within the frustum!

	; Copy the final output over the original polygon data, delete the temporary storage buffer, and exit the function.
	; (We swapped input and output at the end of the last loop, so input really points to the final output.)
	CLIP_CopyPoly(POLY_Input, POLY_Clip, Fast)
	Return 
		
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function clips all polygons against the clipping planes.  See CLIP_ClipPoly() for more details.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_ClipPolys()	
	
	Local ThisPoly.CLIP_Poly

	For ThisPoly = Each CLIP_Poly
		CLIP_ClipPoly(ThisPoly)
	Next

End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function copies one polygon to another.
; If fast copy is enabled, only the positions are copied.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_CopyPoly.CLIP_Poly(POLY_Src.CLIP_Poly, POLY_Dest.CLIP_Poly, Fast=False)

	Local LOOP_Vertex

	POLY_Dest\Vertices = POLY_Src\Vertices

	If Fast
	
		For LOOP_Vertex = 0 To POLY_Src\Vertices-1
			
			POLY_Dest\Vx#[LOOP_Vertex] = POLY_Src\Vx#[LOOP_Vertex]
			POLY_Dest\Vy#[LOOP_Vertex] = POLY_Src\Vy#[LOOP_Vertex]
			POLY_Dest\Vz#[LOOP_Vertex] = POLY_Src\Vz#[LOOP_Vertex]
		
		Next
		
	Else

		For LOOP_Vertex = 0 To POLY_Src\Vertices-1

			POLY_Dest\Vx#[LOOP_Vertex]  = POLY_Src\Vx#[LOOP_Vertex]
			POLY_Dest\Vy#[LOOP_Vertex]  = POLY_Src\Vy#[LOOP_Vertex]
			POLY_Dest\Vz#[LOOP_Vertex]  = POLY_Src\Vz#[LOOP_Vertex]

			POLY_Dest\Vnx#[LOOP_Vertex] = POLY_Src\Vnx#[LOOP_Vertex]
			POLY_Dest\Vny#[LOOP_Vertex] = POLY_Src\Vny#[LOOP_Vertex]
			POLY_Dest\Vnz#[LOOP_Vertex] = POLY_Src\Vnz#[LOOP_Vertex]
	
			POLY_Dest\Vr#[LOOP_Vertex]  = POLY_Src\Vr#[LOOP_Vertex]
			POLY_Dest\Vg#[LOOP_Vertex]  = POLY_Src\Vg#[LOOP_Vertex]
			POLY_Dest\Vb#[LOOP_Vertex]  = POLY_Src\Vb#[LOOP_Vertex]
			POLY_Dest\Va#[LOOP_Vertex]  = POLY_Src\Va#[LOOP_Vertex]

			POLY_Dest\Vu0#[LOOP_Vertex] = POLY_Src\Vu0#[LOOP_Vertex]
			POLY_Dest\Vv0#[LOOP_Vertex] = POLY_Src\Vv0#[LOOP_Vertex]
			POLY_Dest\Vu1#[LOOP_Vertex] = POLY_Src\Vu1#[LOOP_Vertex]
			POLY_Dest\Vv1#[LOOP_Vertex] = POLY_Src\Vv1#[LOOP_Vertex]
	
		Next	
		
	EndIf
	
	Return POLY_Dest
	 
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function interpolates between two values.
;
; In other words, it takes two numbers, and calculates a number that is somewhere between them.
;
; A# and B# are the two numbers to interpolate between.
; Weight# is how much each affects the final output.
;
; In other words, a weight of 0 will return A#, and a weight of 1 will return B#. 
; And a weight of 0.5 will give you a value halfway between them. 
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_Interpolate#(A#, B#, Weight#)

	
	Return (A#*(1.0-Weight#) + B#*Weight#)

End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function linearly interpolates a normal.
;
; In other words, it takes two normals, and calculates a normal that is somewhere between them.
; It uses a linear interpolation, so it is slightly inaccurate, but for most things it will be good enough.
;
; N1xyz and N2xyz are the two normals to interpolate between.
; Weight# is how much each affects the final output.
;
; In other words, a weight of 0.5 will give you a normal halfway between them.  A weight of 0.25 will give you a normal which is
; more like the first.   And a weight of 1.0 will give you a normal which is exactly the same as Normal 2.
;
; The interpolated normal is returned in CLIP_Normal_X#, CLIP_Normal_Y#, and CLIP_Normal_Z#
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_InterpolateNormal(N1x#, N1y#, N1z#, N2x#, N2y#, N2z#, Weight#)

	; Calculate interpolated normal.
	CLIP_Normal_X# = N1x#*(1.0-Weight#) + N2x#*Weight#
	CLIP_Normal_Y# = N1y#*(1.0-Weight#) + N2y#*Weight#
	CLIP_Normal_Z# = N1z#*(1.0-Weight#) + N2z#*Weight#

	; Renormalize.	(Make normal's length = 1)
	Length# = Sqr(CLIP_Normal_X#*CLIP_Normal_X# + CLIP_Normal_Y#*CLIP_Normal_Y# + CLIP_Normal_Z#*CLIP_Normal_Z#)
	
	If Length# > 0
		CLIP_Normal_X# = CLIP_Normal_X# / Length#
		CLIP_Normal_Y# = CLIP_Normal_Y# / Length#
		CLIP_Normal_Z# = CLIP_Normal_Z# / Length#
	Else
		CLIP_Normal_X# = 0
		CLIP_Normal_Y# = 0
		CLIP_Normal_Z# = 0
	EndIf	
	
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function returns true if the specified vertex of the specified polygon is on the back side of the specified plane.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_Vertex_Inside_Plane(Poly.CLIP_Poly, Index, Plane.CLIP_Plane)
	Return CLIP_Point_Inside_Plane(Poly\Vx#[Index], Poly\Vy#[Index], Poly\Vz#[Index], Plane\A#, Plane\B#, Plane\C#, Plane\D#)
End Function 


; -----------------------------------------------------------------------------------------------------------------------------------
; This function determines the location along a line where a polygon edge, defined by two vertices, intersects a clipping plane.
; V1 and V2 are the indices of the vertcies in the specified polygon.
; Returns the location of the intersetion in CLIP_Intersect_XYZ# and CLIP_Intersect_U#
; Returns true if an intersection actually occured.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_Edge_Intersect_Plane(Poly.CLIP_Poly, V1, V2, Plane.CLIP_Plane)
	Return CLIP_Line_Intersect_Plane(Poly\Vx#[V1], Poly\Vy#[V1], Poly\Vz#[V1], Poly\Vx#[V2], Poly\Vy#[V2], Poly\Vz#[V2], Plane\A#, Plane\B#, Plane\C#, Plane\D#)
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function copies the specified vertex from the specified polygon to the specified polygon, 
; and returns the index of the new vertex.
;
; If FAST is enabled, only the vertex's position will be copied to the new vertex.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_CopyVertex(POLY_Src.CLIP_Poly, Src_Index, POLY_Dest.CLIP_Poly, Fast=False)

	Local Dest_Index

	Dest_Index = CLIP_AddVertex(POLY_Dest)

	If Fast

		POLY_Dest\Vx#[Dest_Index] = POLY_Src\Vx#[Src_Index]
		POLY_Dest\Vy#[Dest_Index] = POLY_Src\Vy#[Src_Index]
		POLY_Dest\Vz#[Dest_Index] = POLY_Src\Vz#[Src_Index]

	Else
	
		POLY_Dest\Vx#[Dest_Index]  = POLY_Src\Vx#[Src_Index]
		POLY_Dest\Vy#[Dest_Index]  = POLY_Src\Vy#[Src_Index]
		POLY_Dest\Vz#[Dest_Index]  = POLY_Src\Vz#[Src_Index]

		POLY_Dest\Vnx#[Dest_Index] = POLY_Src\Vnx#[Src_Index]
		POLY_Dest\Vny#[Dest_Index] = POLY_Src\Vny#[Src_Index]
		POLY_Dest\Vnz#[Dest_Index] = POLY_Src\Vnz#[Src_Index]

		POLY_Dest\Vr#[Dest_Index]  = POLY_Src\Vr#[Src_Index]
		POLY_Dest\Vg#[Dest_Index]  = POLY_Src\Vg#[Src_Index]
		POLY_Dest\Vb#[Dest_Index]  = POLY_Src\Vb#[Src_Index]
		POLY_Dest\Va#[Dest_Index]  = POLY_Src\Va#[Src_Index]

		POLY_Dest\Vu0#[Dest_Index] = POLY_Src\Vu0#[Src_Index]
		POLY_Dest\Vv0#[Dest_Index] = POLY_Src\Vv0#[Src_Index]
		POLY_Dest\Vu1#[Dest_Index] = POLY_Src\Vu1#[Src_Index]
		POLY_Dest\Vv1#[Dest_Index] = POLY_Src\Vv1#[Src_Index]
	
	EndIf
	
	Return Dest_Index
	
End Function	


; -----------------------------------------------------------------------------------------------------------------------------------
; This function adds a new vertex to the specified polygon. 
; It's properties are calculated by interpolating between V1 annd V2 of the specified polygon, using the specified weighting value.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_Add_Interpolated_Vertex(POLY_Src.CLIP_Poly, Vertex1, Vertex2, Weight#, POLY_Dest.CLIP_poly)
	
	Local Vertex_I
	Local X#, Y#, Z#
	Local R#, G#, B#, A#
	Local U0#, V0#, U1#, V1#	
	Local Nx#, Ny#, Nz#
	
	; Create the new vertex.			
	Vertex_I = CLIP_AddVertex(POLY_Dest)

	; Calculate the interpolated properties of the vertex.
		X# = CLIP_Interpolate(POLY_Src\Vx#[Vertex1], POLY_Src\Vx#[Vertex2], Weight#)
		Y# = CLIP_Interpolate(POLY_Src\Vy#[Vertex1], POLY_Src\Vy#[Vertex2], Weight#)
		Z# = CLIP_Interpolate(POLY_Src\Vz#[Vertex1], POLY_Src\Vz#[Vertex2], Weight#)

		R# = CLIP_Interpolate(POLY_Src\Vr#[Vertex1], POLY_Src\Vr#[Vertex2], Weight#)
		G# = CLIP_Interpolate(POLY_Src\Vg#[Vertex1], POLY_Src\Vg#[Vertex2], Weight#)
		B# = CLIP_Interpolate(POLY_Src\Vb#[Vertex1], POLY_Src\Vb#[Vertex2], Weight#)
		A# = CLIP_Interpolate(POLY_Src\Va#[Vertex1], POLY_Src\Va#[Vertex2], Weight#)	

		U0# = CLIP_Interpolate(POLY_Src\Vu0#[Vertex1], POLY_Src\Vu0#[Vertex2], Weight#) 
		V0# = CLIP_Interpolate(POLY_Src\Vv0#[Vertex1], POLY_Src\Vv0#[Vertex2], Weight#)
		U1# = CLIP_Interpolate(POLY_Src\Vu1#[Vertex1], POLY_Src\Vu1#[Vertex2], Weight#)		
		V1# = CLIP_Interpolate(POLY_Src\Vv1#[Vertex1], POLY_Src\Vv1#[Vertex2], Weight#)
		
		CLIP_InterpolateNormal(POLY_Src\Vnx#[Vertex1], POLY_Src\Vny#[Vertex1], POLY_Src\Vnz#[Vertex1], POLY_Src\Vnx#[Vertex2], POLY_Src\Vny#[Vertex2], POLY_Src\Vnz#[Vertex2], Weight#)
		Nx# = CLIP_Normal_X#
		Ny# = CLIP_Normal_Y#
		Nz# = CLIP_Normal_Z#
	
	; Set the properties of the new vertex.		
				
		CLIP_SetVertexPosition(POLY_Dest, Vertex_I, X#, Y#, Z#)
		CLIP_SetVertexColor(POLY_Dest, Vertex_I, R#, G#, B#)
		CLIP_SetVertexAlpha(POLY_Dest, Vertex_I, A#)
		CLIP_SetVertexUV(POLY_Dest, Vertex_I, U0#, V0#, 0)
		CLIP_SetVertexUV(POLY_Dest, Vertex_I, U1#, V1#, 1)
		CLIP_SetVertexNormal(POLY_Dest, Vertex_I, Nx#, Ny#, Nz#)
		
	; Return the index number of the next vertex.
		Return Vertex_I	
		
End Function


; -------------------------------------------------------------------------------------------------------------------
; This function calculates the plane equation for a triangle.
; It returns the results in the global variables CLIP_A#, CLIP_B#, CLIP_C#, and CLIP_D#.
;
; ABC is the triangle's normal.  D is the distance of the plane from the origin.  Distance is negative if the normal
; points away from the origin, and positive if it points toward it.
;
; The normal points in the direction the triangle is facing.
; Wind vertices clockwise to have normal point towards you. 
;
; In other words, a triangle aligned with the X, Z axis, wound counterclockwise when looking down, at a height of 5,
; will have a normal pointing downwards, and a value for D# of 5.
; -------------------------------------------------------------------------------------------------------------------
Function CLIP_CalculateTriPlane(V1x#, V1y#, V1z#, V2x#, V2y#, V2z#, V3x#, V3y#, V3z#)

	Local Px#, Py#, Pz#
	Local Qx#, Qy#, Qz#
	Local Nx#, Ny#, Nz#, Nl#
		
	; Create two vectors from the sides of the triangle.
		Px# = V1x#-V3x#
		Py# = V1y#-V3y#
		Pz# = V1z#-V3z#

		Qx# = V2x#-V3x#
		Qy# = V2y#-V3y#
		Qz# = V2z#-V3z#

	; Compute their cross product.
		Nx# = (Py#*Qz#) - (Qy#*Pz#)
		Ny# = (Pz#*Qx#) - (Qz#*Px#) 	
		Nz# = (Px#*Qy#) - (Qx#*Py#)
	
	; Calculate the length of the vector.
		Nl# = Sqr(Nx#*Nx# + Ny#*Ny# + Nz#*Nz#)
	
	; Calculate the plane equation for the triangle.  

		; ABC is the triangle's normal.

		; Normalize the vector so it has a length of 1.
		; This is the normal of the triangle.
		CLIP_A# = Nx# / Nl#
		CLIP_B# = Ny# / Nl#
		CLIP_C# = Nz# / Nl#
	 
		; Calculate minimum distance of plane the triangle lies in, from the origin.
		; This is the shortest distance to the surface of the plane from 0,0,0.
		CLIP_D# = -(CLIP_A#*V1x# + CLIP_B#*V1y# + CLIP_C#*V1z#)

End Function
			
			
; -----------------------------------------------------------------------------------------------------------------------------------
; This function calculates the equation of a 2D line.
;
; The equation of a 2D line is the same as the equation of a plane, except that the C component (Normal Z) is assumed to be 0.
; If facing down the line from point 1 to point 2, the line's normal will point left.
; In other words, if the line is an edge of a triangle wound clockwise, the resulting edge normals will point outwards.
;
; Function assumes positive Y is up, unlike screen coordinates.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_Calculate2DLine(X1#, Y1#, X2#, Y2#)

	Local Nx#, Ny#, Nl#

	; Calculate the normal of the line, (A = Nx, B = Ny) and the distance of the line (D) from the origin (0,0,0).
	Nx# = Y2# - Y1# 
	Ny# = X1# - X2#

	; Normalize the normal.
	Nl# = Sqr(Nx#*Nx# + Ny#*Ny#)
	
	CLIP_A# = Nx# / Length#
	CLIP_B# = Ny# / Length#
	CLIP_D# = -(CLIP_A#*X1# + CLIP_B#*Y1#)
	
End Function


; -----------------------------------------------------------------------------------------------------------------------------------
; This function determines if a circle is intersecting a line, or on the inside side of a line.
;
; XY is the position of the circle.
; Radius is the circle's radius.  
; ABD is the equation of the line.
; -----------------------------------------------------------------------------------------------------------------------------------
Function CLIP_CircleInsideLine(X#, Y#, Radius#, A#, B#, D#)

	If (X#*A# + Y#*B# + D#) < Radius# Then Return True
	Return False

End Function 
			
			
; -----------------------------------------------------------------------------------------------------------------------------------
; This function determines if a circle is intersecting/inside a triangle, in 2D.
;
; XY is the position of the circle.
; Radius is the circle's radius.  
; Vx, Vy are the vertices of the triangle, wound in clockwise order.
; -----------------------------------------------------------------------------------------------------------------------------------
;Function CLIP_CircleInsideTri(X#, Y#, Radius#, Vx1#, Vy1#, Vx2#, Vy2#, Vx3#, Vy3#)

	; If the circle is intersecting or on the inside side

;End Function 


; -------------------------------------------------------------------------------------------------------------------
; This function returns the X axis scale of an entity, as set by ScaleEntity().
; -------------------------------------------------------------------------------------------------------------------
Function CLIP_EntityScaleX#(Entity)

	Vx# = GetMatElement(Entity, 0, 0)
	Vy# = GetMatElement(Entity, 0, 1)
	Vz# = GetMatElement(Entity, 0, 2)	
	
	Scale# = Sqr(Vx#*Vx# + Vy#*Vy# + Vz#*Vz#)
	
	Return Scale#

End Function


; -------------------------------------------------------------------------------------------------------------------
; This function returns the Y axis scale of an entity, as set by ScaleEntity().
; -------------------------------------------------------------------------------------------------------------------
Function CLIP_EntityScaleY#(Entity)

	Vx# = GetMatElement(Entity, 1, 0)
	Vy# = GetMatElement(Entity, 1, 1)
	Vz# = GetMatElement(Entity, 1, 2)	
	
	Scale# = Sqr(Vx#*Vx# + Vy#*Vy# + Vz#*Vz#)
	
	Return Scale#

End Function


; -------------------------------------------------------------------------------------------------------------------
; This function returns the Z axis scale of an entity, as set by ScaleEntity().
; -------------------------------------------------------------------------------------------------------------------
Function CLIP_EntityScaleZ#(Entity)

	Vx# = GetMatElement(Entity, 2, 0)
	Vy# = GetMatElement(Entity, 2, 1)
	Vz# = GetMatElement(Entity, 2, 2)	
	
	Scale# = Sqr(Vx#*Vx# + Vy#*Vy# + Vz#*Vz#)
	
	Return Scale#

End Function



sswift(Posted 2007) [#4]
The CLIP_Line_Intersect_Plane function in the above code will tell you where a line intersects a plane in global space. A cube has six planes. You'll get a point for each one that tells where the line passed through that plane.

Since planes are infinite, some of these points may not lie on the surface of the cube.

You can figure out which points are on the surface of the cube by using CLIP_Point_Inside_Plane.

If you set up all your planes so the normals point outwards from the middle of the cube, then for each side calculate the intersection point. For each of the four adjacent sides, but not the side on the other side of the cube, check to see if that point is on their inside side. You're basically seeing if the point is inside a four sided infinitely long cylinder. If it is, then it's on the surface of that cube on that side. Otherwise it's off the surface of the cube.

Do this for all six sides/intersection points. For each point, store the U cordinate returned that tells you where the point is along the line. Once you know all the points which are on the surface of the cube, pick the one with the lowest U coordinate, the one which is closest to the start point of your ray, and that is your first intersection point. I think you should only have two points that are on the surface of the cube, so the other one is your exit point, if that's of any use to you. You can use the distance between them to calculate how much of the cube you passed through too, which would be useful for transparency effects.


Didn't you make a stencil shadow system? I'd think you'd have to know this stuff to do that.


bytecode77(Posted 2007) [#5]
cool, someone answered my post ;)
this pick function is good and fast, too!
but there are 2 problems

- "backward" picking; the ray does a backward pick
- infinite picking. the ray must not pick infinite far.

Didn't you make a stencil shadow system? I'd think you'd have to know this stuff to do that.

yes, but i did it with tformpoints, which is easier. also the volume part is by daredevil ;)


sswift(Posted 2007) [#6]

; 2. The line-relative position, in CLIP_Intersect_U#, where a value of 0..1 means the intersection point lies between V1 and V2,
; and a value less than 0 or greater than 1 means the intersection occured at a location outside the line segment.




Use the U coordinate returned for where the pick point is on the line to determine whether the pick point is behind your start point, or beyond your endpoint.

The U coordinate will be less than 0 if the pick point is "behind" the first point you specify in the pick, and greater than 1 if it's beyond the second point.

And if only one of your pick points is outside this range, then you're inside the cube, assuming your start point is the camera's position.


bytecode77(Posted 2007) [#7]
ok, (d < 0) is OK. it works! dont know why that didnt work before... now the other problem is infinite picking...

edit: got that, too now!
thank you very much for your help :)