From 1f56cad02eced27d162eb6a32c3372203bc2416c Mon Sep 17 00:00:00 2001
From: Ian C <ianc@noddybox.co.uk>
Date: Tue, 4 Oct 2005 00:47:59 +0000
Subject: Added CircleIntersects()

---
 algorithm.mod/algorithm.bmx | 89 ++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 87 insertions(+), 2 deletions(-)

diff --git a/algorithm.mod/algorithm.bmx b/algorithm.mod/algorithm.bmx
index 187d2bb..1cac89f 100644
--- a/algorithm.mod/algorithm.bmx
+++ b/algorithm.mod/algorithm.bmx
@@ -15,7 +15,7 @@ Import brl.math
 Import brl.linkedlist
 
 Rem
-bbdoc: Used to return points from algorithms.
+bbdoc: Used to return integer points from algorithms.
 EndRem
 Type TAlgoPoint
 	Rem
@@ -41,6 +41,38 @@ Type TAlgoPoint
 	
 End Type
 
+Rem
+bbdoc: Used to return 3D points from algorithms.
+EndRem
+Type TAlgoPoint3D
+	Rem
+	bbdoc: The X co-ordinate of the point
+	EndRem
+	Field	x:Double
+	Rem
+	bbdoc: The Y co-ordinate of the point
+	EndRem
+	Field	y:Double
+	Rem
+	bbdoc: The Z co-ordinate of the point
+	EndRem
+	Field	z:Double
+	
+	Rem
+	bbdoc: Create a point.
+	returns: Newly created point.
+	about: @x, @y and @z are initialised with the passed parameters.
+	EndRem
+	Function Create:TAlgoPoint3D(x:Double, y:Double, z:Double)
+		Local o:TAlgoPoint3D=New TAlgoPoint3D
+		o.x=x
+		o.y=y
+		o.z=z
+		Return o
+	End Function
+	
+End Type
+
 Rem
 bbdoc: Implements a Bresenham style line.
 returns: A list of points making up the line.
@@ -136,6 +168,55 @@ Function DoCircle:TAlgoPoint[](x:Int, y:Int, r:Int)
 	Return p
 End Function
 
+
+Rem
+bbdoc: Returns the points where a sphere intersects a 3D line.
+returns: null if they don't intersect, one point if it intersects as a tangent, two points otherwise.
+about: @x1, @y1, @z1, @x2, @y2 and @z2 describe the line.  @cx, @cy, @cz and @rad describe the sphere.
+about: Leave the Z co-ords as zero to do a 2D check.
+EndRem
+Function CircleIntersects:TAlgoPoint3D[](x1:Double, y1:Double, z1:Double, x2:Double, y2:Double, z2:Double, cx:Double, cy:Double, cz:Double, rad:Double)
+	Local a:Double = Square(x2-x1) + Square(y2-y1) + Square(z2-z1)
+	Local b:Double = 2 * ( (x2-x1)*(x1-cx) + (y2-y1)*(y1-cy) + (z2-z1)*(z1-cz) )
+	Local c:Double = Square(x1) + Square(y1) + Square(z1) + Square(cx) + Square(cy) + Square(cz) - 2 * ( cx*x1 + cy*y1 + cz*z1 ) - Square(rad)
+	Local i:Double = b*b-4*a*c
+	
+	If i<0
+		Return Null
+	ElseIf i=1.0
+		Local m:Double = -b/(2*a)
+		If m<0.0 Or m>1.0
+			Return Null
+		EndIf
+		Local p:TAlgoPoint3D[]=New TAlgoPoint3D[1]
+		p[0]=TAlgoPoint3D.Create( x1+m*(x2-x1), y1+m*(y2-y1), z1 + m*(z2-z1))
+		Return p
+	Else
+		Local e:Double = Sqr(Square(b) - 4*a*c)
+		Local m1:Double = (-b + e) / (2*a)
+		Local m2:Double = (-b - e) / (2*a)
+		
+		If (m2<0.0 Or m2>1.0) And (m1<0.0 Or m1>1.0)
+			Return Null
+		ElseIf (m1<0.0 Or m1>1.0)
+			Local p:TAlgoPoint3D[]=New TAlgoPoint3D[1]
+			p[0]=TAlgoPoint3D.Create( x1+m2*(x2-x1), y1+m2*(y2-y1), z1+m2*(z2-z1))
+			Return p
+		ElseIf m2<0.0 Or m2>1.0
+			Local p:TAlgoPoint3D[]=New TAlgoPoint3D[1]
+			p[0]=TAlgoPoint3D.Create( x1+m1*(x2-x1), y1+m1*(y2-y1), z1+m1*(z2-z1))
+			Return p
+		Else
+			Local p:TAlgoPoint3D[]=New TAlgoPoint3D[2]
+			p[0]=TAlgoPoint3D.Create( x1+m1*(x2-x1), y1+m1*(y2-y1), z1+m1*(z2-z1))
+			p[1]=TAlgoPoint3D.Create( x1+m2*(x2-x1), y1+m2*(y2-y1), z1+m2*(z2-z1))
+			Return p
+		EndIf
+	EndIf
+
+End Function
+
+
 Private
 
 Type AlgoStatic
@@ -156,4 +237,8 @@ Type AlgoStatic
 			done=True
 		EndIf
 	End Function
-End Type
\ No newline at end of file
+End Type
+
+Function Square:Double(x:Double)
+	Return x*x
+End Function
-- 
cgit v1.2.3