You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
366 lines
10 KiB
C++
366 lines
10 KiB
C++
///////////////////////////////////////////////////////////////////////////////
|
|
//
|
|
// ## ######
|
|
// ###### ### 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
|