glgeometry.h

/*
Copyright (c) 2000-2007 Lee Thomason (www.grinninglizard.com)
Grinning Lizard Utilities.

This software is provided 'as-is', without any express or implied 
warranty. In no event will the authors be held liable for any 
damages arising from the use of this software.

Permission is granted to anyone to use this software for any 
purpose, including commercial applications, and to alter it and 
redistribute it freely, subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must 
not claim that you wrote the original software. If you use this 
software in a product, an acknowledgment in the product documentation 
would be appreciated but is not required.

2. Altered source versions must be plainly marked as such, and 
must not be misrepresented as being the original software.

3. This notice may not be removed or altered from any source 
distribution.
*/



#ifndef GRINLIZ_GEOMETRY_INCLUDED
#define GRINLIZ_GEOMETRY_INCLUDED

#include "glvector.h"
#include "glrectangle.h"
#include "glmatrix.h"

#include <vector>

namespace grinliz {

template< class T>
inline void CrossProduct( const Vector2<T>& u, const Vector2<T>& v, Vector3<T>* w )
{
        w->x = 0.0f;
        w->y = 0.0f;
        w->z = u.x * v.y - u.y * v.x;
}

template< class T>
inline T CrossProductZ( const Vector2<T>& u, const Vector2<T>& v )
{
        return u.x * v.y - u.y * v.x;
}


template< class T>
inline T DotProduct( const Vector2<T>& v0, const Vector2<T>& v1 )
{
        return v0.x*v1.x + v0.y*v1.y;
}


template< class T>
inline void CrossProduct( const Vector3<T>& u, const Vector3<T>& v, Vector3<T>* w )
{
        GLASSERT( &u != w && &v != w );

        w->x = u.y * v.z - u.z * v.y;
        w->y = u.z * v.x - u.x * v.z;
        w->z = u.x * v.y - u.y * v.x;
}


template< class T>
inline Vector3<T> CrossProduct( const Vector3<T>& u, const Vector3<T>& v )
{
        Vector3<T> w;

        w.x = u.y * v.z - u.z * v.y;
        w.y = u.z * v.x - u.x * v.z;
        w.z = u.x * v.y - u.y * v.x;
        return w;
}


template< class T>
inline T DotProduct( const Vector3<T>& v0, const Vector3<T>& v1 )
{
        return v0.x*v1.x + v0.y*v1.y + v0.z*v1.z;
}


struct BoundingSphere
{
        Vector3F        point;
        float           rad;

};


struct Ray
{
        Vector3F        origin;
        Vector3F        direction;      // should always have a length of 1.0f
        float           length;
};

struct Plane
{
        static void CreatePlane( const Vector3F* vertices, Plane* plane );

        Vector3F        n;      
        float           d;      

        float Z( float x, float y ) const { return -( d + (n.x * x) + (n.y * y) ) / ( n.z ); }

        void Normalize()
        {
                float div = 1.0f / sqrtf( ( n.x * n.x ) + ( n.y * n.y ) + ( n.z * n.z ) );
                n.x *= div;
                n.y *= div;
                n.z *= div;
                d   *= div;
        }

        void ProjectToPlane( const Vector3F& vector, Vector3F* projected ) const;
};

float CalcSphereTexture( float x, float y, bool roundHigh );

enum TessellateSphereMode
{
        TESS_SPHERE_NORMAL,
        TESS_SPHERE_TOPHALF,
        TESS_SPHERE_MIRROR,
};

void TessellateSphere( int iterations, float radius, bool innerNormals, 
                                          std::vector< Vector3F >* _vertex, 
                                          std::vector< U32 >* _index, 
                                          std::vector< Vector3F >* _normal = 0,
                                          std::vector< Vector2F >* _texture = 0,
                                          TessellateSphereMode mode = TESS_SPHERE_NORMAL );


struct LineNode
{
        grinliz::Vector2F       point;          // the point on the line
        LineNode*       prev;
        LineNode*       next;
        float           value;                          // optional interpolation info

        LineNode( const grinliz::Vector2F& p ) : point( p ), prev( 0 ), next( 0 ), value( 0.0f ) {}
        LineNode( float x, float y ) : prev( 0 ), next( 0 ), value( 0.0f ) { point.Set( x, y ); }
        LineNode( float x, float y, float val ) : prev( 0 ), next( 0 ), value( val ) { point.Set( x, y ); }
        ~LineNode() {}
};


class LineLoop
{
public:
        LineLoop()      : first( 0 )    {}
        ~LineLoop()     { Clear(); }

        void Clear();
        void Delete( LineNode* del );
        void AddAtEnd( LineNode* node );
        void AddAfter( LineNode* me, LineNode* add );
        LineNode* First()       { return first; }
        const LineNode* First() const   { return first; }
        void SortToTop();
        void Bounds( grinliz::Rectangle2F* bounds );

        void Render( float* surface, int width, int height, bool fill=false );

        #ifdef DEBUG
        void Dump();
        #endif
 
private:
        LineNode* first;
};


template< int X0, int X1, int XC >
struct Quad3F
{
        enum { NUM_VERTEX = 4 };
        Vector3F vertex[NUM_VERTEX];

        Quad3F( float x0, float y0, float x1, float y1, float c ) 
        {
                vertex[0].X(X0) = x0;   vertex[0].X(X1) = y0;   vertex[0].X(XC) = c;
                vertex[1].X(X0) = x1;   vertex[1].X(X1) = y0;   vertex[1].X(XC) = c;
                vertex[2].X(X0) = x1;   vertex[2].X(X1) = y1;   vertex[2].X(XC) = c;
                vertex[3].X(X0) = x0;   vertex[3].X(X1) = y1;   vertex[3].X(XC) = c;
        }
};

typedef Quad3F< 0, 1, 2 > Quad3Fz;


template< int X0, int X1 >
struct Quad2F
{
        enum { NUM_VERTEX = 4 };
        Vector2F vertex[NUM_VERTEX];

        Quad2F( float x0, float y0, float x1, float y1 ) 
        {
                vertex[0].X(X0) = x0;   vertex[0].X(X1) = y0;
                vertex[1].X(X0) = x1;   vertex[1].X(X1) = y0;
                vertex[2].X(X0) = x1;   vertex[2].X(X1) = y1;
                vertex[3].X(X0) = x0;   vertex[3].X(X1) = y1;
        }
};

typedef Quad2F< 0, 1 > Quad2Fz;



class Quaternion
{
public:
        Quaternion() : x( 0.0f ), y( 0.0f ), z( 0.0f ), w( 1.0f )       {}

        void Normalize();

        const void ToAxisAngle( Vector3F* axis, float* angleOut ) const;
        const void ToMatrix( Matrix4* matrix ) const;
        void FromRotationMatrix( const Matrix4& matrix );
        void FromAxisAngle( const Vector3F& axis, float angle );

        static void SLERP( const Quaternion& start, const Quaternion& end, float t, Quaternion* result );
        static void Multiply( const Quaternion& a, const Quaternion& b, Quaternion* result );

        float x, y, z, w;
};


enum
{
        REJECT = 0,             // No intersection.
        INTERSECT,              // Intersected
        POSITIVE,               // All comparison positive
        NEGATIVE,               // All Comparison negative
        INSIDE,                 // An intersection, expected to be outside of the object, is originating inside
};

enum 
{
        // Reordering would be bad. x=0, y=1, z=2
        YZ_PLANE,
        XZ_PLANE,
        XY_PLANE
};


int ComparePlaneAABB( const Plane&, const Rectangle3F& aabb );

int ComparePlanePoint( const Plane&, const Vector3F& p );

inline int IntersectPlaneAABB( const Plane& p, const Rectangle3F& aabb )
{
        return ( ComparePlaneAABB( p, aabb ) == INTERSECT ) ? INTERSECT : REJECT; 
}


int IntersectRayTri(    const Vector3F& point, const Vector3F& dir,
                                                const Vector3F& vert0, const Vector3F& vert1, const Vector3F& vert2,
                                                Vector3F* intersect );

int IntersectRayAAPlane(        const Vector3F& point, const Vector3F& dir,
                                                        int planeType, float planeLoc,
                                                        Vector3F* intersect,
                                                        float* t );
                                                 
int IntersectRayAABB(   const Vector3F& origin, const Vector3F& dir,
                                                const Rectangle3F& aabb,
                                                Vector3F* intersect,
                                                float* t );

int IntersectRayAABB(   const Vector2F& origin, const Vector2F& dir,
                                                const Rectangle2F& aabb,
                                                Vector2F* intersect,
                                                float* t, int* planeIndex=0, int* quadrant=0 );

int IntersectionRayAABB(        const Ray& ray,
                                                        const Rectangle3F& aabb,
                                                        Rectangle3F* result );

int IntersectRayZPlane( const Vector3F& origin, const Vector3F& dir,
                                                float z,
                                                Vector3F* intersect );

int IntersectLinePlane( const Vector3F& a0, const Vector3F& a1,
                                                const Plane& plane, 
                                                Vector3F* out,
                                                float* t );

int IntersectLineLine(  const Vector3F& a0, const Vector3F& a1,
                                                const Vector3F& b0, const Vector3F& b1,
                                                Vector3F* out0, 
                                                Vector3F* out1 );

int IntersectLineLine(  const Vector2F& a0, const Vector2F& a1,
                                                const Vector2F& b0, const Vector2F& b1,
                                                Vector2F* out,
                                                float* t0,
                                                float* t1 );


int PointInPolygon( const Vector2F& p, const Vector2F* vertex, int numVertex );

float PointBetweenPoints( const Vector3F& p0, const Vector3F& p1, const Vector3F& pi );

int Intersect3Planes( const Plane& p0, const Plane& p1, const Plane& p2, Vector3F* intersection );

};      // namespace grinliz
#endif

---