geometry.pas

Delphi7编程80例(完全版)

unit Geometry;

// This unit contains many needed types, functions and procedures for
// quaternion, vector and matrix arithmetics. It is specifically designed
// for geometric calculations within R3 (affine vector space)
// and R4 (homogeneous vector space).
//
// Identifiers containing no dimensionality (as affine or homogeneous)
// and no datatype (integer..extended) are supposed as R4 representation
// with 'single' floating point type (examples are TVector, TMatrix,
// and TQuaternion). The default data type is 'single' ('GLFloat' for OpenGL)
// and used in all routines (except conversions).
//
// Routines with an open array as argument can either take
// Func([1,2,3,4,..]) or Func(Vect). The latter is prefered, since
// no extra stack operations is required.
// NOTE: Be careful while passing open array elements! If you pass more elements
// than there's room in the result, then the behaviour will be unpredictable.
//
// If not otherwise stated, all angles are given in radians
// (instead of degrees). Use RadToDeg or DegToRad from Math.pas
// to convert between them.
//
// Geometry.pas was assembled from different sources (like GraphicGems)
// and relevant books or based on self written code, respectivly.
//
// NOTE: Some aspects need to be considered when using Delphi and pure
//       assembler code. Delphi esnures that the direction flag is always
//       cleared while entering a function and expects it cleared on return.
//       The registeres EDI, ESI and EBX (as well as the stack management
//       registers EBP and ESP) must not be changed! EAX, ECX and EDX are
//       freely available.
//
// last change : 03. January 1998
// Done by: Dipl.-Ing. Mike Lischke ([e-mail])

interface

uses Math;

type // data types needed for 3D graphics calculation,
     // included are 'C like' aliases for each type (to be
     // conformal with OpenGL types)

     PByte            = ^Byte;
     PWord            = ^Word;
     PInteger         = ^Integer;
     PFloat           = ^Single;
     PDouble          = ^Double;
     PExtended        = ^Extended;
     PPointer         = ^Pointer;

     // types to specify continous streams of a specific type
     // switch off range checking to access values beyond the limits
     PByteVector = ^TByteVector;
     TByteVector = array[Word] of Byte;

     PWordVector = ^TWordVector;
     TWordVector = array[Word] of Word;

     PIntVector = ^TIntVector;
     TIntVector = array[Word] of Integer;

     PFloatVector = ^TFloatVector;
     TFloatVector = array[Word] of Single;

     PDblVector = ^TDblVector;
     TDblVector = array[Word] of Double;

     // common vector and matrix types
     // indices correspond like: x -> 0
     //                          y -> 1
     //                          z -> 2
     //                          w -> 3

     PHomogeneousByteVector = ^THomogeneousByteVector;
     THomogeneousByteVector = array[0..3] of Byte;
     TVector4b              = THomogeneousByteVector;

     PHomogeneousWordVector = ^THomogeneousWordVector;
     THomogeneousWordVector = array[0..3] of Word;
     TVector4w              = THomogeneousWordVector;

     PHomogeneousIntVector  = ^THomogeneousIntVector;
     THomogeneousIntVector  = array[0..3] of Integer;
     TVector4i              = THomogeneousIntVector;

     PHomogeneousFltVector  = ^THomogeneousFltVector;
     THomogeneousFltVector  = array[0..3] of Single;
     TVector4f              = THomogeneousFltVector;

     PHomogeneousDblVector  = ^THomogeneousDblVector;
     THomogeneousDblVector  = array[0..3] of Double;
     TVector4d              = THomogeneousDblVector;

     PHomogeneousExtVector  = ^THomogeneousExtVector;
     THomogeneousExtVector  = array[0..3] of Extended;
     TVector4e              = THomogeneousExtVector;

     PHomogeneousPtrVector  = ^THomogeneousPtrVector;
     THomogeneousPtrVector  = array[0..3] of Pointer;
     TVector4p              = THomogeneousPtrVector;

     PAffineByteVector      = ^TAffineByteVector;
     TAffineByteVector      = array[0..2] of Byte;
     TVector3b              = TAffineByteVector;

     PAffineWordVector      = ^TAffineWordVector;
     TAffineWordVector      = array[0..2] of Word;
     TVector3w              = TAffineWordVector;

     PAffineIntVector       = ^TAffineIntVector;
     TAffineIntVector       = array[0..2] of Integer;
     TVector3i              = TAffineIntVector;

     PAffineFltVector       = ^TAffineFltVector;
     TAffineFltVector       = array[0..2] of Single;
     TVector3f              = TAffineFltVector;

     PAffineDblVector       = ^TAffineDblVector;
     TAffineDblVector       = array[0..2] of Double;
     TVector3d              = TAffineDblVector;

     PAffineExtVector       = ^TAffineExtVector;
     TAffineExtVector       = array[0..2] of Extended;
     TVector3e              = TAffineExtVector;

     PAffinePtrVector       = ^TAffinePtrVector;
     TAffinePtrVector       = array[0..2] of Pointer;
     TVector3p              = TAffinePtrVector;

     // some simplified names
     PVector                = ^TVector;
     TVector                = THomogeneousFltVector;

     PHomogeneousVector     = ^THomogeneousVector;
     THomogeneousVector     = THomogeneousFltVector;

     PAffineVector          = ^TAffineVector;
     TAffineVector          = TAffineFltVector;

     PVectorArray           = ^TVectorArray;
     TVectorArray           = array[Word] of TAffineVector;

     // matrices
     THomogeneousByteMatrix = array[0..3] of THomogeneousByteVector;
     TMatrix4b              = THomogeneousByteMatrix;

     THomogeneousWordMatrix = array[0..3] of THomogeneousWordVector;
     TMatrix4w              = THomogeneousWordMatrix;

     THomogeneousIntMatrix  = array[0..3] of THomogeneousIntVector;
     TMatrix4i              = THomogeneousIntMatrix;

     THomogeneousFltMatrix  = array[0..3] of THomogeneousFltVector;
     TMatrix4f              = THomogeneousFltMatrix;

     THomogeneousDblMatrix  = array[0..3] of THomogeneousDblVector;
     TMatrix4d              = THomogeneousDblMatrix;

     THomogeneousExtMatrix  = array[0..3] of THomogeneousExtVector;
     TMatrix4e              = THomogeneousExtMatrix;

     TAffineByteMatrix      = array[0..2] of TAffineByteVector;
     TMatrix3b              = TAffineByteMatrix;

     TAffineWordMatrix      = array[0..2] of TAffineWordVector;
     TMatrix3w              = TAffineWordMatrix;

     TAffineIntMatrix       = array[0..2] of TAffineIntVector;
     TMatrix3i              = TAffineIntMatrix;

     TAffineFltMatrix       = array[0..2] of TAffineFltVector;
     TMatrix3f              = TAffineFltMatrix;

     TAffineDblMatrix       = array[0..2] of TAffineDblVector;
     TMatrix3d              = TAffineDblMatrix;

     TAffineExtMatrix       = array[0..2] of TAffineExtVector;
     TMatrix3e              = TAffineExtMatrix;

     // some simplified names
     PMatrix                = ^TMatrix;
     TMatrix                = THomogeneousFltMatrix;

     PHomogeneousMatrix     = ^THomogeneousMatrix;
     THomogeneousMatrix     = THomogeneousFltMatrix;

     PAffineMatrix          = ^TAffineMatrix;
     TAffineMatrix          = TAffineFltMatrix;

     // q=([x,y,z],w)
     TQuaternion        = record
                            case Integer of
                              0 : (Axis   : TAffineVector;
                                   Angle  : Single);
                              1 : (Vector : TVector);
                          end;

     TRectangle         = record
                            Left, Top, Width, Height: Integer;
                          end;

     TTransType = (ttScaleX,ttScaleY,ttScaleZ,
                   ttShearXY,ttShearXZ,ttShearYZ,
                   ttRotateX,ttRotateY,ttRotateZ,
                   ttTranslateX,ttTranslateY,ttTranslateZ,
                   ttPerspectiveX,ttPerspectiveY,ttPerspectiveZ,ttPerspectiveW);

     // used to describe a sequence of transformations in following order:
     // [Sx][Sy][Sz][ShearXY][ShearXZ][ShearZY][Rx][Ry][Rz][Tx][Ty][Tz][P(x,y,z,w)]
     // constants are declared for easier access (see MatrixDecompose below)
     TTransformations  = array[TTransType] of Extended;

    
const // useful constants

      // standard vectors
      XVector    : TAffineVector = (1,0,0);
      YVector    : TAffineVector = (0,1,0);
      ZVector    : TAffineVector = (0,0,1);
      NullVector : TAffineVector = (0,0,0);

      IdentityMatrix : TMatrix = ((1,0,0,0),
                                  (0,1,0,0),
                                  (0,0,1,0),
                                  (0,0,0,1));
      EmptyMatrix    : TMatrix = ((0,0,0,0),
                                  (0,0,0,0),
                                  (0,0,0,0),
                                  (0,0,0,0));
      // some very small numbers
      EPSILON  = 1E-100;
      EPSILON2 = 1E-50;

//------------------------------------------------------------------------------

// vector functions
function  VectorAdd(V1,V2: TVector): TVector;
function  VectorAffineAdd(V1,V2: TAffineVector): TAffineVector;
function  VectorAffineCombine(V1,V2: TAffineVector; F1,F2: Single): TAffineVector;
function  VectorAffineDotProduct(V1,V2: TAffineVector): Single;
function  VectorAffineLerp(V1,V2: TAffineVector; t: Single): TAffineVector;
function  VectorAffineSubtract(V1,V2: TAffineVector): TAffineVector;
function  VectorAngle(V1,V2: TAffineVector): Single;
function  VectorCombine(V1,V2: TVector; F1,F2: Single): TVector;
function  VectorCrossProduct(V1,V2: TAffineVector): TAffineVector;
function  VectorDotProduct(V1,V2: TVector): Single;
function  VectorLength(V: array of Single): Single;
function  VectorLerp(V1,V2: TVector; t: Single): TVector;
procedure VectorNegate(V: array of Single);
function  VectorNorm(V: array of Single): Single; 
function  VectorNormalize(V: array of Single): Single;
function  VectorPerpendicular(V,N: TAffineVector): TAffineVector;
function  VectorReflect(V, N: TAffineVector): TAffineVector;
procedure VectorScale(V: array of Single; Factor: Single);
function  VectorSubtract(V1,V2: TVector): TVector;

// matrix functions
function  CreateRotationMatrixX(Sine, Cosine: Single): TMatrix;
function  CreateRotationMatrixY(Sine, Cosine: Single): TMatrix;
function  CreateRotationMatrixZ(Sine, Cosine: Single): TMatrix;
function  CreateScaleMatrix(V: TAffineVector): TMatrix;
function  CreateTranslationMatrix(V: TAffineVector): TMatrix;
procedure MatrixAdjoint(var M: TMatrix);
function  MatrixAffineDeterminant(M: TAffineMatrix): Single;
procedure MatrixAffineTranspose(var M: TAffineMatrix);
function  MatrixDeterminant(M: TMatrix): Single;
procedure MatrixInvert(var M: TMatrix);
function  MatrixMultiply(M1, M2: TMatrix): TMatrix;
procedure MatrixScale(var M: TMatrix; Factor: Single);
procedure MatrixTranspose(var M: TMatrix);

// quaternion functions
function  QuaternionConjugate(Q: TQuaternion): TQuaternion;
function  QuaternionFromPoints(V1,V2: TAffineVector): TQuaternion;
function  QuaternionMultiply(qL, qR: TQuaternion): TQuaternion;
function  QuaternionSlerp(QStart,QEnd: TQuaternion; Spin: Integer; t: Single): TQuaternion;
function  QuaternionToMatrix(Q: TQuaternion): TMatrix;
procedure QuaternionToPoints(Q: TQuaternion; var ArcFrom, ArcTo: TVector);

// mixed functions
function  ConvertRotation(Angles: TAffineVector): TVector;
function  CreateRotationMatrix(Axis: TAffineVector; Angle: Single): TMatrix;
function  MatrixDecompose(M: TMatrix; var Tran: TTransformations): Boolean;
function  VectorAffineTransform(V: TAffineVector; M: TAffineMatrix): TAffineVector;
function  VectorTransform(V: TVector; M: TMatrix): TVector;

// miscellaneous functions
function  MakeAffineDblVector(V: array of Double): TAffineDblVector;
function  MakeDblVector(V: array of Double): THomogeneousDblVector; 
function  MakeAffineVector(V: array of Single): TAffineVector;
function  MakeVector(V: array of Single): TVector;
function  PointInPolygon(xp, yp : array of Single; x,y: Single): Boolean;
function  VectorAffineDblToFlt(V: TAffineDblVector): TAffineVector;
function  VectorDblToFlt(V: THomogeneousDblVector): THomogeneousVector;
function  VectorAffineFltToDbl(V: TAffineVector): TAffineDblVector;
function  VectorFltToDbl(V: TVector): THomogeneousDblVector;

//------------------------------------------------------------------------------

implementation

const // FPU status flags (high order byte)
      C0 =   1;
      C1 =   2;
      C2 =   4;
      C3 = $40;

      // to be used as descriptive indices
      X  =   0;
      Y  =   1;
      Z  =   2;
      W  =   3;

//------------------------------------------------------------------------------

function MakeAffineDblVector(V: array of Double): TAffineDblVector; register; assembler;

// create a vector from given values
// EAX contains address of V
// ECX contains address to result vector
// EDX contains highest index of V

asm
              PUSH EDI
              PUSH ESI
              MOV EDI,ECX
              MOV ESI,EAX
              MOV ECX,6
              REP MOVSD
              POP ESI
              POP EDI
end;

//------------------------------------------------------------------------------

function MakeDblVector(V: array of Double): THomogeneousDblVector; register; assembler;

// create a vector from given values
// EAX contains address of V
// ECX contains address to result vector
// EDX contains highest index of V

asm
              PUSH EDI
              PUSH ESI
              MOV EDI,ECX
              MOV ESI,EAX
              MOV ECX,8
              REP MOVSD
              POP ESI
              POP EDI
end;

//------------------------------------------------------------------------------

function MakeAffineVector(V: array of Single): TAffineVector; register; assembler;

// create a vector from given values
// EAX contains address of V
// ECX contains address to result vector
// EDX contains highest index of V

asm
              PUSH EDI
              PUSH ESI
              MOV EDI,ECX
              MOV ESI,EAX
              MOV ECX,3
              REP MOVSD
              POP ESI
              POP EDI
end;

//------------------------------------------------------------------------------

function MakeVector(V: array of Single): TVector; register; assembler;

// create a vector from given values
// EAX contains address of V
// ECX contains address to result vector
// EDX contains highest index of V

asm
              PUSH EDI
              PUSH ESI
              MOV EDI,ECX
              MOV ESI,EAX
              MOV ECX,4
              REP MOVSD
              POP ESI
              POP EDI
end;

//------------------------------------------------------------------------------

function VectorLength(V: array of Single): Single; register; assembler;