path: root/game/code/roads/geometry.h

//=============================================================================
// Copyright (C) 2002 Radical Entertainment Ltd.  All rights reserved.
//
// File:        geometry.h
//
// Description: Some linear algebra/geometry stuff mostly used in traffic
//              Also contains some useful structures.
//
// History:     09/09/2002 + Created -- Dusit Eakkachaichanvet
//
//=============================================================================



#ifndef GEOMETRY_H
#define GEOMETRY_H

// *************************
// 2D & 3D GEOMETRY HELPERS
// *************************
#include <radmath/radmath.hpp>
#include <raddebug.hpp> // for rAssert & other debug print outs

/* 
//////////////////////////////////////////////////////////////////////////////
// OLD OLD OLD STUFF
//////////////////////////////////////////////////////////////////////////////
#ifndef PI_F
#define PI_F 3.1415926535897932384626433832795f
#endif
#define MYEPSILON 0.001
#ifndef NULL
    #define NULL 0
#endif
struct Line 
{
	float x1;
	float y1;
	float x2;
	float y2;
	float slope;
	float b;
	bool isVertical;
	bool isInfinite;
	bool isFinishLine;
};

struct Point 
{
	float x;
	float y;
	int id;
};
bool fequals(float a, float b);
bool fequals(float a, float b, float epsilon);
bool isVerticalLine( Line line );
Line getLine( float x1, float y1, float x2, float y2, bool isInfinite );
bool isPointOnLine( Line line, Point p );
bool IntersectLines2D( rmt::Vector p1, 
                       rmt::Vector dir1, 
                       rmt::Vector p2, 
                       rmt::Vector dir2,
                       rmt::Vector& p );
*/

//////////////////////////////////////////////////////////////////////////////
// CUBIC BEZIER SHEEYATSU
//////////////////////////////////////////////////////////////////////////////

class CubicBezier
{
public:
    enum 
    {
        MAX_CONTROL_POINTS = 4, // total control points (including start & end points)
        MAX_CURVE_POINTS = 30   // total curve points including start & end points
    };

    static void InitOnceLUTs();

    static bool sIsInitialized;
    static float B0[MAX_CURVE_POINTS];
    static float B1[MAX_CURVE_POINTS];
    static float B2[MAX_CURVE_POINTS];
    static float B3[MAX_CURVE_POINTS];

    CubicBezier();
    ~CubicBezier();

    void GetCubicBezierCurve(rmt::Vector*& pts, int& nCurvePts);
    void GetCubicBezierCurve2D(rmt::Vector*& pts, int& nCurvePts);
    void AddControlPoint(const rmt::Vector& cp);
    void SetControlPoint(const rmt::Vector& cp, int index);


protected:

    void CreateCubicBezierCurve();
    void CreateCubicBezierCurve2D();

    rmt::Vector mCurve[MAX_CURVE_POINTS];
    rmt::Vector mCurve2D[MAX_CURVE_POINTS];
    rmt::Vector mControlPoints[MAX_CONTROL_POINTS];
    int mNumControlPointsAdded;
    bool mCurveIsCreated;
    bool mCurveIsCreated2D;

    //Prevent wasteful constructor creation.
    CubicBezier( const CubicBezier& CubicBezier );
    CubicBezier& operator=( const CubicBezier& CubicBezier );

};



//////////////////////////////////////////////////////////////////////////////
// DListArray
//////////////////////////////////////////////////////////////////////////////

class DListArray
{

public:

    enum
    {
        MAX_ELEMS = 20
    };

    DListArray();
    void Clear();

    // returns index value of found element, -1 on error
    int Find( void* data );

    // returns the index value of the newly added element
    // or -1 on error
    int AddLast( void* data );

    // returns the index value of the newly added element
    // or -1 on error
    int AddFirst( void* data );

    // returns index value of the newly inserted element
    // or -1 on error
    int InsertAfter( void* data, int i );

    // Note: this incurs a linear search
    bool Remove( void* data );

    bool Remove( int i );

    int GetNumElems() const;

    int GetFree() const;

    void* GetDataAt( int i ) const;

    int GetNextOf( int i ) const;

    int GetPrevOf( int i ) const;

    void* GetFirst() const;

    void* GetLast() const;

    int GetHead() const;
    
    int GetTail() const;
    
private:

    struct DLAElem 
    {
        void* data;
        int next;
        int prev;
    };

    DLAElem mElems[MAX_ELEMS];
    int mnElems;
    int mHead;
    int mTail;
    int mFree;

};

inline int DListArray::GetNumElems() const
{
    return mnElems;
}
inline int DListArray::GetFree() const 
{
    return mFree;
}
inline void* DListArray::GetDataAt(int i) const
{
    return mElems[i].data;
}

inline void* DListArray::GetFirst() const
{
    if( mHead != -1 )
    {
        return mElems[mHead].data;
    }
    return NULL;
}
inline void* DListArray::GetLast() const
{
    if( mTail != -1 )
    {
        return mElems[mTail].data;
    }
    return NULL;
}
inline int DListArray::GetHead() const
{
    return mHead;
}
inline int DListArray::GetTail() const
{
    return mTail;
}

inline int DListArray::GetNextOf( int i ) const
{
    rAssert( 0 <= i && i < MAX_ELEMS );
    return mElems[i].next;
}

inline int DListArray::GetPrevOf( int i ) const
{
    rAssert( 0 <= i && i < MAX_ELEMS );
    return mElems[i].prev;
}


// history tracking
template <class T, int HISTORY_SIZE> class History
{
public:
    History() : mNextSpot(0) {}
    ~History() {}

    void Init( const T& t )
    {
        mNextSpot = 0;

        for( int i=0; i< HISTORY_SIZE; i++ )
        {
            mHistory[i] = t;
        }

        mAverage = t;
    }

    void UpdateHistory( const T& t)
    {
        // first get the old value & recalculate our average
        mAverage -= (mHistory[mNextSpot] - t) / (float)(HISTORY_SIZE);
        mHistory[mNextSpot] = t;
        mNextSpot = (mNextSpot + 1) % HISTORY_SIZE;
    }

    void GetAverage( T& t )
    {
        t = mAverage;
    }

    T GetEntry( int i )
    {
        rAssert( 0 <= i && i < HISTORY_SIZE );
        return mHistory[i];
    }

    T GetLastEntry()
    {
        int i = mNextSpot - 1;
        if( i == -1 )
        {
            i = HISTORY_SIZE - 1;
        }
        rAssert( 0 <= i && i < HISTORY_SIZE );
        return mHistory[i];
    }

    int GetSize()
    {
        return HISTORY_SIZE;
    }

private:
    int mNextSpot;
    T mHistory[HISTORY_SIZE];
    T mAverage;
};

template <int HISTORY_SIZE> class VectorHistory : public History<rmt::Vector, HISTORY_SIZE>
{
public:
    VectorHistory() {}
    ~VectorHistory() {}

    void Init( const rmt::Vector& t )
    {
        History<rmt::Vector,HISTORY_SIZE>::Init(t);
        GetAverage(mNormalizedAverage);
    }

    void GetNormalizedAverage( rmt::Vector& vec )
    {
        if( rmt::Epsilon( mNormalizedAverage.MagnitudeSqr(), 1.0f, 0.0005f ) )
        {
            vec = mNormalizedAverage;
        }
        else
        {
            mNormalizedAverage.NormalizeSafe(); 
            vec = mNormalizedAverage;
        }
    }

    void UpdateHistory( const rmt::Vector& vec )
    {
        History<rmt::Vector,HISTORY_SIZE>::UpdateHistory(vec);
        GetAverage(mNormalizedAverage);
    }

protected:

    rmt::Vector mNormalizedAverage;
};

//////////////////////////////////////////////////////////////////////////////
// MISC
//////////////////////////////////////////////////////////////////////////////

const float KPH_2_MPS = 1.0f/3.60f;

// returns true if projection point is on line segment
bool PointToLineProjection2D( const rmt::Vector& in, 
                              const rmt::Vector& linePt1, 
                              const rmt::Vector& linePt2, 
                              rmt::Vector& out  );

rmt::Vector GetProjectionVector( const rmt::Vector& source, 
                                 const rmt::Vector& target );

// MAYA:                           GAME:
// Right-hand coord                 Left-hand coord
//                              
//         +y (forefinger)                  +y (forefinger)
//          |                                |
//          |                                |
//          |                                |
//          /\                               /\
//        /    \                           /    \
//      /        \                       /        \
//   +z (middle)  +x (thumb)        +x(thumb)     +z(middle)
//

// In Lefthand coordinate system, turn vector to
// the left (counter-clockwise) 90 degrees & return new vector
rmt::Vector Get90DegreeLeftTurn( const rmt::Vector& orig );

// In Lefthand coordinate system, turn vector to
// the right (clockwise) 90 degrees & return new vector
rmt::Vector Get90DegreeRightTurn( const rmt::Vector& orig );

float GetRotationAboutY( float x, float z );

// returns the number of intersections and po   ints q1 & q2
int IntersectLineSphere( const rmt::Vector& p1, 
                         const rmt::Vector& p2, 
                         const rmt::Sphere& s, 
                         rmt::Vector* intPts);

// just test if line segment intersects sphere... don't bother 
// finding the intersection point(s)
bool TestIntersectLineSphere( const rmt::Vector& lOrig,
                              const rmt::Vector& lDir,
                              const rmt::Sphere& s );



// Test using (normalized) myHeading DOT vectorFromMyHeadingToTarget
bool WillCollide( const rmt::Vector& myPos, 
                  const rmt::Vector& myHeading, // Must be normalized
                  const rmt::Vector& mySide,    // Must be normalized
                  float myRadius, 
                  float myLookAheadDist,
                  const rmt::Vector& targetPos,
                  bool& targetOnMyRightSide );

rmt::Vector UpdateVUP( const rmt::Vector& position, const rmt::Vector& target );

// Given points P1 and P2, and two points that define a line, A and B
// P1 and P2 are on the same side of the line, if the Normals for BAxP1A
// and BAxP2A are pointing on the same side of the plane (i.e. 
// N1-dot-N2 >= 0)

bool PointsOnSameSideOfLine( const rmt::Vector& P1,
                             const rmt::Vector& P2,
                             const rmt::Vector& A,
                             const rmt::Vector& B );



// Given triangle with vertices v1, v2, v3 and a point p
// p is inside triangle if it is on the same side of line v1v2 as v3
// and on the same side of line v2v3 as v1, 
// and on the same side of line v1v3 as v2
//
bool PointLiesInTriangle ( const rmt::Vector& p, 
                           const rmt::Vector& v1, 
                           const rmt::Vector& v2, 
                           const rmt::Vector& v3 );


// Given a point "p", and a line starting at point "start" and ending 
// at point "end", determine if p lies on the left side of the line
// (assuming that the line is looking in the direction of start-to-end
//
bool PointOnLeftSideOfLine( const rmt::Vector& p, 
                            const rmt::Vector& start,
                            const rmt::Vector& end );

// Ditto.. but for the right side
//
bool PointOnRightSideOfLine( const rmt::Vector& p, 
                            const rmt::Vector& start,
                            const rmt::Vector& end );

// Given a line segment described by vector from start to end,
// and an arbitrary point... return the point on the line segment
// closest to this arbitrary point and the float parameter along
// the line segment at which this closest point occurs
float FindClosestPointOnLine( const rmt::Vector& start,
                             const rmt::Vector& end,
                             const rmt::Vector& p,
                             rmt::Vector& closestPt );

float GetLineSegmentT( const rmt::Vector& segStart, 
                       const rmt::Vector& segEnd, 
                       const rmt::Vector& pt );

#endif // GEOMETRY_H