Rem bbdoc: noddybox.algorithm EndRem Module noddybox.algorithm ModuleInfo "Framework: Various algorithm routines" ModuleInfo "Copyright: Public Domain" ModuleInfo "Author: Ian Cowburn" ModuleInfo "Version: $Revision$" ' $Id$ Strict Import brl.math Import brl.linkedlist Rem bbdoc: Used to return integer points from algorithms. EndRem Type TAlgoPoint Rem bbdoc: The X co-ordinate of the point EndRem Field x:Int Rem bbdoc: The Y co-ordinate of the point EndRem Field y:Int Rem bbdoc: Create a point. returns: Newly created point. about: @x and @y are initialised with the passed parameters. EndRem Function Create:TAlgoPoint(x:Int, y:Int) Local o:TAlgoPoint=New TAlgoPoint o.x=x o.y=y Return o End Function 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. about: @px1, @py1, @px2 and @py2 are the end points of the line. EndRem Function DoLine:TList(p1x:Int, p1y:Int, p2x:Int, p2y:Int) Local list:TList=CreateList() Local f:Int Local dx:Int Local dy:Int Local ix:Int Local iy:Int Local incrE:Int Local incrNE:Int Local d:Int Local x:Int Local y:Int Local ymode:Int dx=p2x-p1x dy=p2y-p1y ix=Sgn(dx) iy=Sgn(dy) dx=Abs(dx) dy=Abs(dy) If dy>dx ymode=True d=dx*2-dy incrE=dx*2 incrNE=(dx-dy)*2 Else ymode=False d=dy*2-dx incrE=dy*2 incrNE=(dy-dx)*2 EndIf x=p1x y=p1y list.AddLast(TAlgoPoint.Create(x,y)) If ymode While y<>p2y If d<=0 d:+incrE y:+iy Else d:+incrNE y:+iy x:+ix EndIf list.AddLast(TAlgoPoint.Create(x,y)) Wend Else While x<>p2x If d<=0 d:+incrE x:+ix Else d:+incrNE y:+iy x:+ix EndIf list.AddLast(TAlgoPoint.Create(x,y)) Wend EndIf Return list End Function Rem bbdoc: Returns the points for degrees 0-359 on the described circle. returns: A list of points making up the circle. about: @x, @y is the centre of the circle, @r it's radius. EndRem Function DoCircle:TAlgoPoint[](x:Int, y:Int, r:Int) Local p:TAlgoPoint[]=New TAlgoPoint[360] Local f:Int AlgoStatic.Init() For f=0 To 359 p[f]=TAlgoPoint.Create(x+r*AlgoStatic.si[f],y+r*AlgoStatic.co[f]) Next 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 Global done:Int=False Global si:Double[] Global co:Double[] Function Init() If Not done si=New Double[360] co=New Double[360] For Local f:Int=0 To 359 si[f]=Sin(f) co[f]=Cos(f) Next done=True EndIf End Function End Type Function Square:Double(x:Double) Return x*x End Function