-
Notifications
You must be signed in to change notification settings - Fork 2
/
quadtree.h
149 lines (125 loc) · 4.96 KB
/
quadtree.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/* --------------------------------------------------------------------
Author of the quadtree algorithm is Ulrich Thatcher. To get the code running
in Tuxracer it was modified by Jasmin F. Patry. I've modified the code
again for Bunny Hill (old version). With this modification it was possible
to use more terrains than the 3 standard terrains (snow, rock and ice). For
the current version of ETR I've rearranged the modules. The
quadgeom.cpp ist not required because all needed mathematical functions are
available in the mathlib unit (now called "mathlib"). Furthermore the functions
of "course_quad.cpp" are integrated in quadtree.cpp. These functions were
purposed to acess the C++ quadtree from the other modules which were completely
written in C. The new Bunny Hill code or ETR code is C++-orientated though
not rigorously adapted to C++.
The quadtree algorithm works well but has some disadvantages. One disadvantage
ist the kind of blurring at adjacent terrain tiles, detailed terrain texturing
is not possible in this way. Another, more weightly disadvantage is the
performance that depends on the count of different terrains. Many terrains on
a course slow down the race appreciably. It's not urgent but anytime this
algorithm should be replaced with a more convenient quadtree algorithm.
--------------------------------------------------------------------- */
#ifndef QUADTREE_H
#define QUADTREE_H
#include "bh.h"
#include "view.h"
typedef enum {
East,
South,
Center
} vertex_loc_t;
typedef unsigned short uint16;
typedef unsigned int uint32;
typedef short int16;
typedef int int32;
struct HeightMapInfo {
double *Data;
int XOrigin, ZOrigin;
int XSize, ZSize;
int RowWidth;
int Scale;
float Sample(int x, int z) const;
};
struct VertInfo { float Y; };
struct quadsquare;
class quadcornerdata {
public:
const quadcornerdata* Parent;
quadsquare* Square;
int ChildIndex;
int Level;
int xorg, zorg;
VertInfo Verts[4];
};
struct quadsquare {
quadsquare* Child[4];
VertInfo Vertex[5];
float Error[6];
float MinY, MaxY;
unsigned char EnabledFlags;
unsigned char SubEnabledCount[2];
bool Static;
bool Dirty;
bool ForceEastVert;
bool ForceSouthVert;
static double ScaleX, ScaleZ;
static int RowSize, NumRows;
static char *Terrain;
static GLuint TexId[MAX_TERR_TYPES];
static GLuint EnvmapTexId;
static GLushort *VertexArrayIndices;
static GLuint VertexArrayCounter;
static GLuint VertexArrayMinIdx;
static GLuint VertexArrayMaxIdx;
static void MakeTri( int a, int b, int c, int terrain );
static void MakeSpecialTri( int a, int b, int c, int terrain );
static void MakeNoBlendTri( int a, int b, int c, int terrain );
static void DrawTris();
static void DrawEnvmapTris();
static void InitArrayCounters();
quadsquare (quadcornerdata* pcd);
~quadsquare();
void AddHeightMap(const quadcornerdata& cd, const HeightMapInfo& hm);
void StaticCullData(const quadcornerdata& cd, float ThresholdDetail);
float RecomputeError(const quadcornerdata& cd);
int CountNodes();
void Update(const quadcornerdata& cd,
const float ViewerLocation[3], float Detail);
void Render(const quadcornerdata& cd, GLubyte *vnc_array);
float GetHeight(const quadcornerdata& cd, float x, float z);
void SetScale(double x, double z);
void SetTerrain (char *terrain);
private:
quadsquare* EnableDescendant(int count, int stack[],
const quadcornerdata& cd);
quadsquare* GetNeighbor(int dir, const quadcornerdata &cd);
clip_result_t ClipSquare( const quadcornerdata &cd );
void EnableEdgeVertex(int index, bool IncrementCount,
const quadcornerdata &cd);
void EnableChild(int index, const quadcornerdata &cd);
void NotifyChildDisable(const quadcornerdata& cd, int index);
void ResetTree();
void StaticCullAux (const quadcornerdata &cd, float ThresholdDetail,
int TargetLevel);
void CreateChild(int index, const quadcornerdata &cd);
void SetupCornerData (quadcornerdata *q, const quadcornerdata &pd,
int ChildIndex);
void UpdateAux(const quadcornerdata &cd, const float ViewerLocation[3],
float CenterError, clip_result_t vis);
void RenderAux(const quadcornerdata &cd, clip_result_t vis,
int terrain);
void SetStatic (const quadcornerdata &cd);
void InitVert(int i, int x, int z);
bool VertexTest(int x, float y, int z, float error, const float Viewer[3],
int level, vertex_loc_t vertex_loc );
bool BoxTest(int x, int z, float size, float miny, float maxy,
float error, const float Viewer[3]);
};
// --------------------------------------------------------------------
// global calls
// --------------------------------------------------------------------
void ResetQuadtree();
void InitQuadtree (double *elevation, int nx, int nz,
double scalex, double scalez,
TVector3 view_pos, double detail );
void UpdateQuadtree (TVector3 view_pos, float detail );
void RenderQuadtree();
#endif