Back to index

extremetuxracer  0.5beta
quadtree.h
Go to the documentation of this file.
00001 // quadtree.hpp      -thatcher 9/15/1999 Copyright 1999-2000 Thatcher Ulrich
00002 
00003 // Data structures for quadtree terrain storage.
00004 
00005 // This code may be freely modified and redistributed.  I make no
00006 // warrantees about it; use at your own risk.  If you do incorporate
00007 // this code into a project, I'd appreciate a mention in the credits.
00008 //
00009 // Thatcher Ulrich <tu@tulrich.com>
00010 
00011 // Modified for use in Tux Racer by Jasmin Patry <jfpatry@cgl.uwaterloo.ca>
00012 
00013 // Modifications for use in ppracer by Volker Stroebel <volker@planetpenguin.de>
00014 
00015 
00016 
00017 #ifndef _QUADTREE_H_
00018 #define _QUADTREE_H_
00019 
00020 
00021 #include "viewfrustum.h"
00022 
00023 typedef enum {
00024     East,
00025     South,
00026     Center
00027 } vertex_loc_t;
00028 
00029 struct HeightMapInfo {
00030     //double *Data;
00031        float *Data;
00032     int       XOrigin, ZOrigin;
00033     int       XSize, ZSize;
00034     int       RowWidth;
00035     int       Scale;
00036 
00037        inline float Sample(int x, int z) const{
00038               if ( x >= XSize ) {
00039                      x = XSize - 1;
00040               }
00041               if ( z >= ZSize ) {
00042                      z = ZSize - 1;
00043               }
00044               return Data[ x + z * RowWidth ];
00045        }
00046 
00047 };
00048 
00049 class quadsquare;
00050 
00051 // A structure used during recursive traversal of the tree to hold
00052 // relevant but transitory data.
00053 struct quadcornerdata {
00054     const quadcornerdata* Parent;
00055     quadsquare*      Square;
00056     int       ChildIndex;
00057     int       Level;
00058     int       xorg, zorg;
00059        float Verts[4];
00060 };
00061 
00062 
00063 class quadsquare {
00064     quadsquare*      Child[4];
00065 
00066     float     Vertex[5];    // center, e, n, w, s
00067     float     Error[6];     // e, s, children: ne, nw, sw, se
00068     float     MinY, MaxY;   // Bounds for frustum culling and error testing.
00069     unsigned char    EnabledFlags; // bits 0-7: e, n, w, s, ne, nw, sw, se
00070     unsigned char    SubEnabledCount[2];  // e, s enabled reference counts.
00071     bool      Static;
00072     bool      Dirty; // Set when vertex data has changed, but error/enabled data has not been recalculated.
00073 
00074     bool ForceEastVert;
00075     bool ForceSouthVert;
00076        
00077 
00078     static float ScaleX, ScaleZ;
00079     static int RowSize, NumRows;
00080     static int* Terrain;
00081 
00082     static GLuint *VertexArrayIndices[NUM_TERRAIN_TYPES];
00083     static GLuint VertexArrayCounter[NUM_TERRAIN_TYPES];
00084     static GLuint VertexArrayMinIdx[NUM_TERRAIN_TYPES];
00085     static GLuint VertexArrayMaxIdx[NUM_TERRAIN_TYPES];
00086 
00087     static void MakeTri( int a, int b, int c, int terrain );
00088     static void MakeSpecialTri( int a, int b, int c);
00089     static void MakeNoBlendTri( int a, int b, int c, int terrain );
00090 
00091     static void DrawTris(int terrain);
00092     static void DrawEnvmapTris(GLuint MapTexId, int terrain);
00093     static void InitArrayCounters();
00094 
00095 public:
00096     quadsquare(quadcornerdata* pcd);
00097     ~quadsquare();
00098 
00099     void      AddHeightMap(const quadcornerdata& cd, const HeightMapInfo& hm);
00100     void      StaticCullData(const quadcornerdata& cd, const float ThresholdDetail);       
00101     float     RecomputeError(const quadcornerdata& cd);
00102     int       CountNodes();
00103        
00104     void      Update(const quadcornerdata& cd, const float ViewerLocation[3], const float Detail);
00105     void      Render(const quadcornerdata& cd, GLubyte *vnc_array);
00106 
00107     float     GetHeight(const quadcornerdata& cd, const float x, const float z);
00108 
00109        inline void SetScale(const float x, const float z)
00110        {
00111        ScaleX = x;
00112        ScaleZ = z;
00113        };
00114 
00115        inline void   SetTerrain(int *terrain){Terrain = terrain;};
00116        
00117 private:
00118     void      EnableEdgeVertex(int index, const bool IncrementCount, const quadcornerdata& cd);
00119     quadsquare*      EnableDescendant(int count, int stack[], const quadcornerdata& cd);
00120     void      EnableChild(int index, const quadcornerdata& cd);
00121     void      NotifyChildDisable(const quadcornerdata& cd, int index);
00122 
00123     void      ResetTree();
00124     void      StaticCullAux(const quadcornerdata& cd, const float ThresholdDetail, const int TargetLevel);
00125 
00126     quadsquare*      GetNeighbor(const int dir, const quadcornerdata& cd) const;
00127     void      CreateChild(int index, const quadcornerdata& cd);
00128     void      SetupCornerData(quadcornerdata* q, const quadcornerdata& pd, const int ChildIndex);
00129 
00130     void      UpdateAux(const quadcornerdata& cd, const float ViewerLocation[3], const float CenterError, clip_result_t vis);
00131     void      RenderAux(const quadcornerdata& cd, clip_result_t vi);
00132     void      RenderAuxSpezial(const quadcornerdata& cd, clip_result_t vis);
00133     void      SetStatic(const quadcornerdata& cd);
00134        int InitVert(const int i, const int x, const int z);
00135 
00136     bool      VertexTest(int x, float y, int z, float error, const float Viewer[3], int level, vertex_loc_t vertex_loc );
00137     bool      BoxTest(int x, int z, float size, float miny, float maxy, float error, const float Viewer[3]);
00138     clip_result_t ClipSquare( const quadcornerdata& cd );
00139 };
00140 
00141 #endif // _QUADTREE_H_