/*
Copyright (C) 1997, 1998, 1999 by Alex Pfaffe
(Digital Dawn Graphics Inc)
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free
Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#ifndef _ddgBinTree_Class_
#define _ddgBinTree_Class_
#include "struct/ddgtmesh.h"
#include "struct/ddgcntxt.h"
typedef unsigned short ddgPriority;
#define ddgMAXPRI 0xFFFF
#define ddgMINPRI 0
const unsigned int ddgBintreeOffset[32] =
{ 0x1, 0x2, 0x4, 0x8,
0x10, 0x20, 0x40, 0x80,
0x100, 0x200, 0x400, 0x800,
0x1000, 0x2000, 0x4000, 0x8000,
0x10000, 0x20000, 0x40000, 0x80000,
0x100000, 0x200000, 0x400000, 0x800000,
0x1000000, 0x2000000, 0x4000000, 0x8000000,
0x10000000,0x20000000,0x40000000,0x80000000
};
class WEXP ddgTBinTree {
static ddgTBinMesh *_mesh;
int _dc;
int _dr;
bool _mirror:1;
unsigned int _index;
ddgCacheIndex *_cacheIndex;
short *_rawHeight;
short *_rawMinVal;
short *_rawMaxVal;
ddgVisState _vis;
ddgTBinTree *_pNeighbourDiag;
ddgTBinTree *_pNeighbourTop;
ddgTBinTree *_pNeighbourLeft;
static ddgContext *_ctx;
static ddgVector2 _pos;
static ddgVector2 _forward;
static float _farClip;
static float _nearClip;
static float _farClipSQ;
static int _clipPlanes;
static float _cosHalfFOV;
static float _varianceScale;
static ddgMSTri *_stri;
static ddgTCache *_tcache;
ddgCacheIndex _chain;
unsigned int _visTriangle;
ddgPriority forceSplit2( ddgTriIndex tindex);
public:
ddgTBinTree(ddgTreeIndex i, int dr = 0, int dc = 0, bool mirror = false);
~ddgTBinTree(void);
void freeChain(void) {
_chain = 0;
}
ddgCacheIndex chain(void) {
return _chain;
}
unsigned int visTriangle(void) { return _visTriangle; }
void visTriangle(unsigned int v) { _visTriangle = v; }
ddgTBinTree* pNeighbourDiag(void) { return _pNeighbourDiag; }
ddgTBinTree* pNeighbourTop(void) { return _pNeighbourTop; }
ddgTBinTree* pNeighbourLeft(void) { return _pNeighbourLeft; }
void pNeighbourDiag(ddgTBinTree* t) { _pNeighbourDiag = t; }
void pNeighbourTop(ddgTBinTree* t) { _pNeighbourTop = t; }
void pNeighbourLeft(ddgTBinTree* t) { _pNeighbourLeft = t; }
int dc(void) { return _dc; }
int dr(void) { return _dr; }
bool mirror(void) { return _mirror; }
bool init(void);
private:
unsigned int row(unsigned int i);
unsigned int col(unsigned int i);
unsigned int mrow(unsigned int i);
unsigned int mcol(unsigned int i);
static unsigned int offset(unsigned int l)
{
return ddgBintreeOffset[l];
}
public:
static unsigned int level(ddgTriIndex i)
{
unsigned int l = 0;
if (i > 0)
while ((i=i/2) > 1)
l++;
return l;
}
static bool isRight(ddgTriIndex i)
{
return ((i%2) == 1);
}
static bool isLeft(ddgTriIndex i)
{
return ((i%2) == 0);
}
static ddgTriIndex parent(ddgTriIndex i)
{
// asserts (i < _triNo,"Invalid element number.");
if (i == 0)
return 0; // Was _triNo
if (i == 1) return 0;
return i/2;
}
static ddgTriIndex right(ddgTriIndex i)
{
return i*2;
}
static ddgTriIndex left(ddgTriIndex i)
{
return right(i)+1;
}
private:
ddgTriIndex neighbour( ddgTriIndex i);
ddgTBinTree *neighbourTree( ddgTriIndex i);
public:
void tcacheId( ddgTriIndex tindex, ddgCacheIndex ci )
{
_cacheIndex[tindex] = ci;
}
ddgCacheIndex tcacheId( ddgTriIndex tindex )
{
return _cacheIndex[tindex];
}
short rawHeight( ddgTriIndex tindex )
{
return _rawHeight[tindex];
}
short rawMinVal( ddgTriIndex tindex )
{
return _rawMinVal[tindex];
}
short rawMaxVal( ddgTriIndex tindex )
{
return _rawMaxVal[tindex];
}
private:
ddgTNode *gnode(ddgTriIndex tindex);
ddgTNode *snode(ddgTriIndex tindex);
public:
ddgVisState vis(void) { return _vis; }
ddgVisState vis(ddgTriIndex tindex) { return gnode(tindex)->vis(); }
void vis(ddgTriIndex tindex, ddgVisState v) { snode(tindex)->vis(v); }
int priority(ddgTriIndex tindex) { return gnode(tindex)->priority(); }
void priority(ddgTriIndex tindex, int p) { snode(tindex)->priority( p ); }
float priorityFactor(ddgTriIndex tindex) { return gnode(tindex)->priorityFactor(); }
void priorityFactor(ddgTriIndex tindex, float pf) { snode(tindex)->priorityFactor( pf ); }
ddgCacheIndex qscacheIndex(ddgTriIndex tindex){ return gnode( tindex)->qscacheIndex(); }
void qscacheIndex(ddgTriIndex tindex, ddgCacheIndex i) { snode( tindex)->qscacheIndex(i); }
ddgCacheIndex qmcacheIndex(ddgTriIndex tindex){ return gnode( tindex)->qmcacheIndex(); }
void qmcacheIndex(ddgTriIndex tindex, ddgCacheIndex i) { snode( tindex)->qmcacheIndex(i); }
float heightByPos(unsigned int r, unsigned int c);
float treeHeight(unsigned int r, unsigned int c, float dx, float dz);
void vertex(ddgTriIndex tindex, ddgVector3 *vout);
void textureC(unsigned int tindex, ddgVector2 *vout)
{
if (_mirror)
vout->set(ddgTBinMesh_size-row(tindex),ddgTBinMesh_size-col(tindex));
else
vout->set(row(tindex),col(tindex));
vout->multiply( 1.0 / (float)ddgTBinMesh_size);
}
ddgVisState visibilityTriangle(ddgTriIndex tvc);
bool visible(ddgTriIndex i)
{
return (vis(i) != ddgOUT) ? true : false;
}
bool fullyvisible(ddgTriIndex i)
{
return (vis(i) == ddgIN) ? true : false;
}
void initTriangle( unsigned int level,
ddgTriIndex va,
ddgTriIndex v1,
ddgTriIndex v0,
ddgTriIndex vc);
void insertSQ(ddgTriIndex tindex, ddgPriority p, ddgCacheIndex ci, ddgVisState parentVis );
ddgCacheIndex removeSQ(ddgTriIndex tindex);
void insertMQ(ddgTriIndex tindex, ddgPriority p);
void removeMQ(ddgTriIndex tindex);
void forceSplit( ddgTriIndex tindex);
void forceMerge( ddgTriIndex tindex);
void updateSplit(ddgTriIndex tindex, ddgVisState newVis );
void updateMerge(ddgTriIndex tindex, ddgPriority pr);
ddgPriority priorityCalc(ddgTriIndex tindex, float priorityFactor);
unsigned int index(void) { return _index; }
static void initContext( ddgContext *context, ddgTBinMesh *mesh );
static void updateContext( ddgContext *context, ddgTBinMesh *mesh );
bool rayTest( ddgVector3 p1, ddgVector3 p2, ddgTriIndex tindex, int depth = -1 );
};
#ifdef DDGSTREAM
WEXP ostream& WFEXP operator << ( ostream&s, ddgTBinTree v );
WEXP ostream& WFEXP operator << ( ostream&s, ddgTBinTree* v );
#endif // DDGSTREAM
#endif
