///////////////////////////////////////////////////////////////////////////////
//
//      ##  ######          
//       ######  ###        Based on:
//  ## ###############      
//   ########## # # #       Shark 3D Engine (www.shark3d.com)
//    ########
//   ######### # # #        Copyright (c) 1996-2001 Spinor GmbH.
//  ##   ##########         
//      ##                  
//        
///////////////////////////////////////////////////////////////////////////////
//
// G A M E.O.N.E - LOW LEVEL LIB V1.0
// Copyright (C) 2001 LEVEL ONE ENTERTAINMENT, 
// Licensed under the terms of LGPL.
//:---------------------------------------------------------------------------
//:Description
//
// LOW LEVEL 3D GEO3 UTIL HEADERFILE
//
//:---------------------------------------------------------------------------

#ifndef _LL3D_GEO3_H
#define _LL3D_GEO3_H


#include "ll3d_math.h"
#include "ll3d_vec3.h"
#include "ll3d_vec4.h"

namespace ll3d {

template<typename T> struct CGeo3;

typedef CGeo3<float>	CGeo3f;
typedef CGeo3<double>	CGeo3d;
	

/*
 * Geometric Tests
 */
	
template<typename T>
struct CGeo3
{
    // Is the unit box transformed by Bound 
    // touching the box of extension Extend?
    // If the box is smaller than Prec in transformed coordinates,
    // return false.
    static bool IsUnitBoxTouchingBound(
                const CMat4x4<T> &Bound, 
                const CVec3<T> &Extend, const CVec3<T> &Prec);

    // Is the box transformed by Bound 
    // touching the box of extension Extend?
    // If the box is smaller than Prec in transformed coordinates,
    // return false.
    static bool IsAlignedBoxTouchingBound(
                const CVec3<T> &BoxCenter, 
                const CVec3<T> &BoxExtend,
                const CMat4x4<T> &Bound, 
                const CVec3<T> &Extend, const CVec3<T> &Prec);

    // Is the box transformed by Bound 
    // touching the box of extension Extend?
    // If the box is smaller than Prec in transformed coordinates,
    // return false.
    static bool IsFreeBoxTouchingBound(
                const CVec3<T> &BoxCenter, 
                const CMat3x3<T> &BoxExtend,
                const CMat4x4<T> &Bound, 
                const CVec3<T> &Extend, const CVec3<T> &Prec);

    static bool IsAlignedBoxTouchingLine(
                const CVec3<T> &BoxCenter, 
                const CVec3<T> &BoxExtend,
                const CVec3<T> &Start, const CVec3<T> &End);

    static bool IsFreeBoxTouchingLine(
                const CVec3<T> &BoxCenter, 
                const CMat3x3<T> &BoxExtend,
                const CVec3<T> &Start, const CVec3<T> &End);

};

/*
 * Inplementation
 */

template<typename T>
bool CGeo3<T>::IsUnitBoxTouchingBound(
                const CMat4x4<T> &Bound, 
                const CVec3<T> &Extend, const CVec3<T> &Prec)
{
    float RefXX = Bound.m_wx * Extend.m_x;
    float RefXY = Bound.m_wy * Extend.m_x;
    float RefXZ = Bound.m_wz * Extend.m_x;
    float RefXW = Bound.m_ww * Extend.m_x;
    if(RefXW + Bound.m_xw 
            + Abs(RefXX + Bound.m_xx)
            + Abs(RefXY + Bound.m_xy)
            + Abs(RefXZ + Bound.m_xz) <= 0)
        return false;
    if(RefXW - Bound.m_xw
            + Abs(RefXX - Bound.m_xx)
            + Abs(RefXY - Bound.m_xy)
            + Abs(RefXZ - Bound.m_xz) <= 0)
        return false;

    float RefYX = Bound.m_wx * Extend.m_y;
    float RefYY = Bound.m_wy * Extend.m_y;
    float RefYZ = Bound.m_wz * Extend.m_y;
    float RefYW = Bound.m_ww * Extend.m_y;
    if(RefYW + Bound.m_yw
            + Abs(RefYX + Bound.m_yx)
            + Abs(RefYY + Bound.m_yy)
            + Abs(RefYZ + Bound.m_yz) <= 0)
        return false;
    if(RefYW - Bound.m_yw
            + Abs(RefYX - Bound.m_yx)
            + Abs(RefYY - Bound.m_yy)
            + Abs(RefYZ - Bound.m_yz) <= 0)
        return false;

    float RefZX = Bound.m_wx * Extend.m_z;
    float RefZY = Bound.m_wy * Extend.m_z;
    float RefZZ = Bound.m_wz * Extend.m_z;
    float RefZW = Bound.m_ww * Extend.m_z;
    if(RefZW + Bound.m_zw
            + Abs(RefZX + Bound.m_zx)
            + Abs(RefZY + Bound.m_zy)
            + Abs(RefZZ + Bound.m_zz) <= 0)
        return false;
    if(RefZW - Bound.m_zw
            + Abs(RefZX - Bound.m_zx)
            + Abs(RefZY - Bound.m_zy)
            + Abs(RefZZ - Bound.m_zz) <= 0)
        return false;

    float MinW = Bound.m_ww 
            - Abs(Bound.m_wx) 
            - Abs(Bound.m_wy)
            - Abs(Bound.m_wz);
    if(MinW > 0)
    {
        bool Ok = false;

        if(Prec.m_x < FLT_MAX)
        {
            float ExtX = Abs(Bound.m_xx)
                       + Abs(Bound.m_xy)
                       + Abs(Bound.m_xz);
            if(ExtX >= Prec.m_x * MinW)
                Ok = true;
        }

        if(Prec.m_y > 0)
        {
            float ExtY = Abs(Bound.m_yx)
                       + Abs(Bound.m_yy)
                       + Abs(Bound.m_yz);
            if(ExtY >= Prec.m_y * MinW)
                Ok = true;
        }

        if(Prec.m_z > 0)
        {
            float ExtZ = Abs(Bound.m_zx)
                       + Abs(Bound.m_zy)
                       + Abs(Bound.m_zz);
            if(ExtZ >= Prec.m_z * MinW)
                Ok = true;
        }

        if(!Ok)
            return false;
    }

    return true;
}

template<typename T>
bool CGeo3<T>::IsAlignedBoxTouchingBound(
                const CVec3<T> &BoxCenter, 
                const CVec3<T> &BoxExtend,
                const CMat4x4<T> &Bound, 
                const CVec3<T> &Extend, const CVec3<T> &Prec)
{
    CMat4x4f EffBound;
    EffBound.SetSubVV(Bound.GetSubVV().GetScaledCols(BoxExtend));
    EffBound.SetSubWV(Bound.GetSubWV().CompProd(BoxExtend));
    EffBound.SetSubVW(Bound.ProdOneV(BoxCenter));
    EffBound.SetSubWW(Bound.ProdOneW(BoxCenter));
    return IsUnitBoxTouchingBound(EffBound, Extend, Prec);
}

template<typename T>
bool CGeo3<T>::IsFreeBoxTouchingBound(
                const CVec3<T> &BoxCenter, 
                const CMat3x3<T> &BoxExtend,
                const CMat4x4<T> &Bound, 
                const CVec3<T> &Extend, const CVec3<T> &Prec)
{
    CMat4x4f EffBound;
    EffBound.SetSubVV(Bound.GetSubVV() * BoxExtend);
    EffBound.SetSubWV(Bound.GetSubWV() * BoxExtend);
    EffBound.SetSubVW(Bound.ProdOneV(BoxCenter));
    EffBound.SetSubWW(Bound.ProdOneW(BoxCenter));
    return IsUnitBoxTouchingBound(EffBound, Extend, Prec);
}

template<typename T>
bool CGeo3<T>::IsAlignedBoxTouchingLine(
                const CVec3<T> &BoxCenter, const CVec3<T> &BoxExtend,
                const CVec3<T> &Start, const CVec3<T> &End)
{
    CVec3f EffStart = Start - BoxCenter;
    CVec3f EffEnd = End - BoxCenter;

    CVec3f EffMin = EffStart.CompMin(EffEnd);
    CVec3f EffMax = EffStart.CompMax(EffEnd);
    if(EffMax.IsAnyCompLe( - BoxExtend))
        return false;
    if(EffMin.IsAnyCompGe(BoxExtend))
        return false;

    float GradX = EffEnd.m_x - EffStart.m_x;
    float FrontDistX, BackDistX;
    if(GradX > 0)
    {
        FrontDistX = - EffStart.m_x - BoxExtend.m_x;
        BackDistX = - EffStart.m_x + BoxExtend.m_x;
    }
    else
    {
        GradX = - GradX;
        FrontDistX = EffStart.m_x - BoxExtend.m_x;
        BackDistX = EffStart.m_x + BoxExtend.m_x;
    }

    float GradY = EffEnd.m_y - EffStart.m_y;
    float FrontDistY, BackDistY;
    if(GradY > 0)
    {
        FrontDistY = - EffStart.m_y - BoxExtend.m_y;
        BackDistY = - EffStart.m_y + BoxExtend.m_y;
    }
    else
    {
        GradY = - GradY;
        FrontDistY = EffStart.m_y - BoxExtend.m_y;
        BackDistY = EffStart.m_y + BoxExtend.m_y;
    }

    float GradZ = EffEnd.m_z - EffStart.m_z;
    float FrontDistZ, BackDistZ;
    if(GradZ > 0)
    {
        FrontDistZ = - EffStart.m_z - BoxExtend.m_z;
        BackDistZ = - EffStart.m_z + BoxExtend.m_z;
    }
    else
    {
        GradZ = - GradZ;
        FrontDistZ = EffStart.m_z - BoxExtend.m_z;
        BackDistZ = EffStart.m_z + BoxExtend.m_z;
    }

    if(FrontDistX > GradX)
        return false;
    if(FrontDistY > GradY)
        return false;
    if(FrontDistZ > GradZ)
        return false;

    float FrontGrad = 1;
    float FrontDist = 0;
    float CVec3f::*Side = 0;
    if(FrontDistX * FrontGrad > FrontDist * GradX)
    {
        FrontGrad = GradX;
        FrontDist = FrontDistX;
        Side = &CVec3f::m_x;
    }
    if(FrontDistY * FrontGrad > FrontDist * GradY)
    {
        FrontGrad = GradY;
        FrontDist = FrontDistY;
        Side = &CVec3f::m_y;
    }
    if(FrontDistZ * FrontGrad > FrontDist * GradZ)
    {
        FrontGrad = GradZ;
        FrontDist = FrontDistZ;
        Side = &CVec3f::m_z;
    }

    if(Side != &CVec3f::m_x)
    {
        if(FrontDist * GradX > BackDistX * FrontGrad)
            return false;
    }
    if(Side != &CVec3f::m_y)
    {
        if(FrontDist * GradY > BackDistY * FrontGrad)
            return false;
    }
    if(Side != &CVec3f::m_z)
    {
        if(FrontDist * GradZ > BackDistZ * FrontGrad)
            return false;
    }

    return true;
}

template<typename T>
bool CGeo3<T>::IsFreeBoxTouchingLine(
                const CVec3<T> &BoxCenter, 
                const CMat3x3<T> &BoxExtend,
                const CVec3<T> &Start, const CVec3<T> &End)
{
    CVec3f EffBoxExtend(1, 1, 1);
    CVec3f DirX = BoxExtend.GetColX();
    CVec3f DirY = BoxExtend.GetColY();
    CVec3f DirZ = BoxExtend.GetColZ();
    float DirXSq = DirX.GetSqLen();
    float DirYSq = DirY.GetSqLen();
    float DirZSq = DirZ.GetSqLen();
    float Delta = FLT_EPSILON * (DirXSq + DirYSq + DirZSq);
    if(DirXSq < Delta)
    {
        DirX = DirY ^ DirZ;
        EffBoxExtend.m_x = 0;
    }
    if(DirYSq < Delta)
    {
        DirY = DirZ ^ DirX;
        EffBoxExtend.m_y = 0;
    }
    if(DirZSq < Delta)
    {
        DirZ = DirX ^ DirY;
        EffBoxExtend.m_z = 0;
    }

    CMat3x3f Mat = CMat3x3f::ByCols(DirX, DirY, DirZ);
    float Det = Mat.GetDet();
    if(Det > 0)
    {
        CMat3x3f InvMat = Mat.GetSubDet().GetTransposed() / Det;
        CVec3f EffStart = InvMat * Start;
        CVec3f EffEnd = InvMat * End;
        CVec3f EffBoxCenter = InvMat * BoxCenter;
        return IsAlignedBoxTouchingLine(EffBoxCenter, EffBoxExtend,
                                    EffStart, EffEnd);
    }
    else
        return false;
}


}//namespace ll3d
#endif //_LL3D_GEO3_H