1147 lines
28 KiB
C++
1147 lines
28 KiB
C++
|
|
#ifdef HAVE_CONFIG_H
|
|
#include <etr_config.h>
|
|
#endif
|
|
|
|
#include "quadtree.h"
|
|
#include "textures.h"
|
|
#include "course.h"
|
|
#include "ogl.h"
|
|
|
|
#include <climits>
|
|
#include <cstring>
|
|
|
|
#define TERRAIN_ERROR_SCALE 0.1f
|
|
#define VERTEX_FORCE_THRESHOLD 100
|
|
#define ERROR_MAGNIFICATION_THRESHOLD 20
|
|
#define ERROR_MAGNIFICATION_AMOUNT 3
|
|
#define ENV_MAP_ALPHA 50
|
|
#define colorval(j,ch) \
|
|
VNCArray[j*STRIDE_GL_ARRAY+STRIDE_GL_ARRAY-4+(ch)]
|
|
|
|
#define setalphaval(i) colorval(VertexIndices[i], 3) = \
|
|
( terrain <= VertexTerrains[i] ) ? 255 : 0
|
|
|
|
#define update_min_max( idx ) \
|
|
if ( idx > VertexArrayMaxIdx ) { \
|
|
VertexArrayMaxIdx = idx; \
|
|
} \
|
|
if ( idx < VertexArrayMinIdx ) { \
|
|
VertexArrayMinIdx = idx; \
|
|
}
|
|
|
|
static void make_tri_list(void(*tri_func)(int, int, int, int), unsigned char EnabledFlags, int flags, int terrain) {
|
|
if ((EnabledFlags & 1) == 0) {
|
|
tri_func(0, 2, 8, terrain);
|
|
} else {
|
|
if (flags & 8) tri_func(0, 1, 8, terrain);
|
|
if (flags & 1) tri_func(0, 2, 1, terrain);
|
|
}
|
|
if ((EnabledFlags & 2) == 0) {
|
|
tri_func(0, 4, 2, terrain);
|
|
} else {
|
|
if (flags & 1) tri_func(0, 3, 2, terrain);
|
|
if (flags & 2) tri_func(0, 4, 3, terrain);
|
|
}
|
|
if ((EnabledFlags & 4) == 0) {
|
|
tri_func(0, 6, 4, terrain);
|
|
} else {
|
|
if (flags & 2) tri_func(0, 5, 4, terrain);
|
|
if (flags & 4) tri_func(0, 6, 5, terrain);
|
|
}
|
|
if ((EnabledFlags & 8) == 0) {
|
|
tri_func(0, 8, 6, terrain);
|
|
} else {
|
|
if (flags & 4) tri_func(0, 7, 6, terrain);
|
|
if (flags & 8) tri_func(0, 8, 7, terrain);
|
|
}
|
|
}
|
|
|
|
GLuint *quadsquare::VertexArrayIndices = nullptr;
|
|
GLuint quadsquare::VertexArrayCounter;
|
|
GLuint quadsquare::VertexArrayMinIdx;
|
|
GLuint quadsquare::VertexArrayMaxIdx;
|
|
|
|
quadsquare::quadsquare(quadcornerdata* pcd) {
|
|
pcd->Square = this;
|
|
Static = false;
|
|
ForceEastVert = false;
|
|
ForceSouthVert = false;
|
|
Dirty = true;
|
|
|
|
for (int i = 0; i < 4; i++) {
|
|
Child[i] = (quadsquare*) nullptr;
|
|
}
|
|
|
|
EnabledFlags = 0;
|
|
|
|
for (int i = 0; i < 2; i++) SubEnabledCount[i] = 0;
|
|
|
|
Vertex[0].Y = 0.25f * (pcd->Verts[0].Y
|
|
+ pcd->Verts[1].Y + pcd->Verts[2].Y + pcd->Verts[3].Y);
|
|
Vertex[1].Y = 0.5f * (pcd->Verts[3].Y + pcd->Verts[0].Y);
|
|
Vertex[2].Y = 0.5f * (pcd->Verts[0].Y + pcd->Verts[1].Y);
|
|
Vertex[3].Y = 0.5f * (pcd->Verts[1].Y + pcd->Verts[2].Y);
|
|
Vertex[4].Y = 0.5f * (pcd->Verts[2].Y + pcd->Verts[3].Y);
|
|
|
|
for (int i = 0; i < 2; i++) Error[i] = 0;
|
|
for (int i = 0; i < 4; i++) {
|
|
Error[i+2] = std::fabs((Vertex[0].Y + pcd->Verts[i].Y)
|
|
- (Vertex[i+1].Y + Vertex[((i+1)&3) + 1].Y)) * 0.25f;
|
|
}
|
|
|
|
MinY = MaxY = pcd->Verts[0].Y;
|
|
for (int i = 1; i < 4; i++) {
|
|
float y = pcd->Verts[i].Y;
|
|
if (y < MinY) MinY = y;
|
|
if (y > MaxY) MaxY = y;
|
|
}
|
|
}
|
|
|
|
quadsquare::~quadsquare() {
|
|
for (int i = 0; i < 4; i++) {
|
|
if (Child[i]) delete Child[i];
|
|
}
|
|
}
|
|
|
|
void quadsquare::SetStatic(const quadcornerdata &cd) {
|
|
if (Static == false) {
|
|
Static = true;
|
|
if (cd.Parent && cd.Parent->Square) {
|
|
cd.Parent->Square->SetStatic(*cd.Parent);
|
|
}
|
|
}
|
|
}
|
|
|
|
int quadsquare::CountNodes() {
|
|
int count = 1;
|
|
for (int i = 0; i < 4; i++) {
|
|
if (Child[i]) count += Child[i]->CountNodes();
|
|
}
|
|
return count;
|
|
}
|
|
|
|
float quadsquare::GetHeight(const quadcornerdata &cd, float x, float z) {
|
|
int half = 1 << cd.Level;
|
|
|
|
float lx = (x - cd.xorg) / float(half);
|
|
float lz = (z - cd.zorg) / float(half);
|
|
|
|
int ix = (int)std::floor(lx);
|
|
int iz = (int)std::floor(lz);
|
|
|
|
if (ix < 0) ix = 0;
|
|
if (ix > 1) ix = 1;
|
|
if (iz < 0) iz = 0;
|
|
if (iz > 1) iz = 1;
|
|
|
|
int index = (ix ^ (iz ^ 1)) + (iz << 1);
|
|
if (Child[index] && Child[index]->Static) {
|
|
quadcornerdata q;
|
|
SetupCornerData(&q, cd, index);
|
|
return Child[index]->GetHeight(q, x, z);
|
|
}
|
|
|
|
lx -= ix;
|
|
if (lx < 0) lx = 0;
|
|
if (lx > 1) lx = 1;
|
|
|
|
lz -= iz;
|
|
if (lx < 0) lz = 0;
|
|
if (lz > 1) lz = 1;
|
|
|
|
float s00, s01, s10, s11;
|
|
switch (index) {
|
|
default:
|
|
case 0:
|
|
s00 = Vertex[2].Y;
|
|
s01 = cd.Verts[0].Y;
|
|
s10 = Vertex[0].Y;
|
|
s11 = Vertex[1].Y;
|
|
break;
|
|
case 1:
|
|
s00 = cd.Verts[1].Y;
|
|
s01 = Vertex[2].Y;
|
|
s10 = Vertex[3].Y;
|
|
s11 = Vertex[0].Y;
|
|
break;
|
|
case 2:
|
|
s00 = Vertex[3].Y;
|
|
s01 = Vertex[0].Y;
|
|
s10 = cd.Verts[2].Y;
|
|
s11 = Vertex[4].Y;
|
|
break;
|
|
case 3:
|
|
s00 = Vertex[0].Y;
|
|
s01 = Vertex[1].Y;
|
|
s10 = Vertex[4].Y;
|
|
s11 = cd.Verts[3].Y;
|
|
break;
|
|
}
|
|
|
|
return (s00 * (1-lx) + s01 * lx) * (1 - lz) + (s10 * (1-lx) + s11 * lx) * lz;
|
|
}
|
|
|
|
quadsquare* quadsquare::GetNeighbor(int dir, const quadcornerdata& cd) {
|
|
if (cd.Parent == 0) return 0;
|
|
quadsquare* p = 0;
|
|
|
|
int index = cd.ChildIndex ^ 1 ^ ((dir & 1) << 1);
|
|
bool SameParent = ((dir - cd.ChildIndex) & 2) ? true : false;
|
|
|
|
if (SameParent) {
|
|
p = cd.Parent->Square;
|
|
} else {
|
|
p = cd.Parent->Square->GetNeighbor(dir, *cd.Parent);
|
|
if (p == 0) return 0;
|
|
}
|
|
quadsquare* n = p->Child[index];
|
|
return n;
|
|
}
|
|
|
|
float quadsquare::RecomputeError(const quadcornerdata& cd) {
|
|
int half = 1 << cd.Level;
|
|
int whole = half << 1;
|
|
float terrain_error;
|
|
float maxerror = 0;
|
|
float e;
|
|
|
|
std::size_t numTerr = Course.TerrList.size();
|
|
if (cd.ChildIndex & 1) {
|
|
e = std::fabs(Vertex[0].Y - (cd.Verts[1].Y + cd.Verts[3].Y) * 0.5f);
|
|
} else {
|
|
e = std::fabs(Vertex[0].Y - (cd.Verts[0].Y + cd.Verts[2].Y) * 0.5f);
|
|
}
|
|
if (e > maxerror) maxerror = e;
|
|
|
|
MaxY = Vertex[0].Y;
|
|
MinY = Vertex[0].Y;
|
|
|
|
for (int i = 0; i < 4; i++) {
|
|
float y = cd.Verts[i].Y;
|
|
if (y < MinY) MinY = y;
|
|
if (y > MaxY) MaxY = y;
|
|
}
|
|
|
|
|
|
e = std::fabs(Vertex[1].Y - (cd.Verts[0].Y + cd.Verts[3].Y) * 0.5f);
|
|
if (e > maxerror) maxerror = e;
|
|
Error[0] = e;
|
|
|
|
e = std::fabs(Vertex[4].Y - (cd.Verts[2].Y + cd.Verts[3].Y) * 0.5f);
|
|
if (e > maxerror) maxerror = e;
|
|
Error[1] = e;
|
|
|
|
if (cd.Level == 0 && cd.xorg <= RowSize-1 && cd.zorg <= NumRows-1) {
|
|
|
|
int x = cd.xorg + half;
|
|
int z = cd.zorg + whole;
|
|
int idx = x + z * RowSize;
|
|
bool different_terrains = false;
|
|
|
|
terrain_error = 0.f;
|
|
|
|
if (x < RowSize && z < NumRows) {
|
|
|
|
if (x < RowSize - 1) {
|
|
if (Fields[idx].terrain != Fields[idx + 1].terrain) {
|
|
different_terrains = true;
|
|
}
|
|
}
|
|
if (z >= 1) {
|
|
idx -= RowSize;
|
|
if (Fields[idx].terrain != Fields[idx + 1].terrain) {
|
|
different_terrains = true;
|
|
}
|
|
}
|
|
|
|
if (different_terrains) {
|
|
ForceSouthVert = true;
|
|
terrain_error = TERRAIN_ERROR_SCALE * whole * whole;
|
|
} else {
|
|
ForceSouthVert = false;
|
|
}
|
|
|
|
if (terrain_error > Error[0]) {
|
|
Error[0] = terrain_error;
|
|
}
|
|
if (Error[0] > maxerror) {
|
|
maxerror = Error[0];
|
|
}
|
|
}
|
|
|
|
x = cd.xorg + whole;
|
|
z = cd.zorg + half;
|
|
idx = x + z * RowSize;
|
|
terrain_error = 0;
|
|
different_terrains = false;
|
|
|
|
if (x < RowSize && z < NumRows) {
|
|
|
|
if (z >= 1) {
|
|
if (Fields[idx].terrain != Fields[idx - RowSize].terrain) {
|
|
different_terrains = true;
|
|
}
|
|
}
|
|
if (z >= 1 && x < RowSize - 1) {
|
|
idx += 1;
|
|
if (Fields[idx].terrain != Fields[idx - RowSize].terrain) {
|
|
different_terrains = true;
|
|
}
|
|
}
|
|
|
|
if (different_terrains) {
|
|
ForceEastVert = true;
|
|
terrain_error = TERRAIN_ERROR_SCALE * whole * whole;
|
|
} else {
|
|
ForceEastVert = false;
|
|
}
|
|
|
|
if (terrain_error > Error[1]) {
|
|
Error[1] = terrain_error;
|
|
}
|
|
if (Error[1] > maxerror) {
|
|
maxerror = Error[1];
|
|
}
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < 4; i++) {
|
|
float y = Vertex[1 + i].Y;
|
|
if (y < MinY) MinY = y;
|
|
if (y > MaxY) MaxY = y;
|
|
}
|
|
|
|
for (int i = 0; i < 4; i++) {
|
|
if (Child[i]) {
|
|
quadcornerdata q;
|
|
SetupCornerData(&q, cd, i);
|
|
Error[i+2] = Child[i]->RecomputeError(q);
|
|
|
|
if (Child[i]->MinY < MinY) MinY = Child[i]->MinY;
|
|
if (Child[i]->MaxY > MaxY) MaxY = Child[i]->MaxY;
|
|
} else {
|
|
Error[i+2] = std::fabs((Vertex[0].Y + cd.Verts[i].Y)
|
|
- (Vertex[i+1].Y + Vertex[((i+1)&3) + 1].Y)) * 0.25f;
|
|
}
|
|
if (Error[i+2] > maxerror) maxerror = Error[i+2];
|
|
}
|
|
|
|
std::size_t *terrain_count = new std::size_t[numTerr];
|
|
std::memset(terrain_count, 0, sizeof(*terrain_count)*numTerr);
|
|
|
|
for (int i=cd.xorg; i<=cd.xorg+whole; i++) {
|
|
for (int j=cd.zorg; j<=cd.zorg+whole; j++) {
|
|
|
|
if (i < 0 || i >= RowSize ||
|
|
j < 0 || j >= NumRows) {
|
|
continue;
|
|
}
|
|
|
|
int terrain = (int) Fields[i + RowSize*j].terrain;
|
|
terrain_count[ terrain ] += 1;
|
|
}
|
|
}
|
|
|
|
std::size_t max_count = 0;
|
|
std::size_t total = 0;
|
|
for (std::size_t t=0; t<numTerr; t++) {
|
|
if (terrain_count[t] > max_count) {
|
|
max_count = terrain_count[t];
|
|
}
|
|
total += terrain_count[t];
|
|
}
|
|
|
|
delete [] terrain_count;
|
|
|
|
if (total > 0) {
|
|
terrain_error = (1.f - ((float)max_count / (float)total));
|
|
if (numTerr > 1) {
|
|
terrain_error *= numTerr / (numTerr - 1.f);
|
|
}
|
|
terrain_error *= whole * whole;
|
|
terrain_error *= TERRAIN_ERROR_SCALE;
|
|
} else terrain_error = 0;
|
|
|
|
if (terrain_error > maxerror) maxerror = terrain_error;
|
|
if (terrain_error > Error[0]) Error[0] = terrain_error;
|
|
if (terrain_error > Error[1]) Error[1] = terrain_error;
|
|
|
|
Dirty = false;
|
|
|
|
return maxerror;
|
|
}
|
|
|
|
void quadsquare::ResetTree() {
|
|
for (int i = 0; i < 4; i++) {
|
|
if (Child[i]) {
|
|
Child[i]->ResetTree();
|
|
if (Child[i]->Static == false) {
|
|
delete Child[i];
|
|
Child[i] = 0;
|
|
}
|
|
}
|
|
}
|
|
EnabledFlags = 0;
|
|
SubEnabledCount[0] = 0;
|
|
SubEnabledCount[1] = 0;
|
|
Dirty = true;
|
|
}
|
|
|
|
|
|
void quadsquare::StaticCullData(const quadcornerdata& cd, float ThresholdDetail) {
|
|
ResetTree();
|
|
if (Dirty) RecomputeError(cd);
|
|
for (int level = 0; level <= cd.Level; level++) {
|
|
StaticCullAux(cd, ThresholdDetail, level);
|
|
}
|
|
}
|
|
|
|
|
|
void quadsquare::StaticCullAux(const quadcornerdata& cd, float ThresholdDetail, int TargetLevel) {
|
|
quadcornerdata q;
|
|
|
|
if (cd.Level > TargetLevel) {
|
|
for (int j = 0; j < 4; j++) {
|
|
int i;
|
|
if (j < 2) i = 1 - j;
|
|
else i = j;
|
|
|
|
if (Child[i]) {
|
|
SetupCornerData(&q, cd, i);
|
|
Child[i]->StaticCullAux(q, ThresholdDetail, TargetLevel);
|
|
}
|
|
}
|
|
return;
|
|
}
|
|
float size = 2 << cd.Level; // Edge length.
|
|
if (Child[0] == nullptr && Child[3] == nullptr && Error[0] * ThresholdDetail < size) {
|
|
quadsquare* s = GetNeighbor(0, cd);
|
|
if (s == nullptr || (s->Child[1] == nullptr && s->Child[2] == nullptr)) {
|
|
|
|
float y = (cd.Verts[0].Y + cd.Verts[3].Y) * 0.5f;
|
|
Vertex[1].Y = y;
|
|
Error[0] = 0;
|
|
if (s) s->Vertex[3].Y = y;
|
|
|
|
Dirty = true;
|
|
}
|
|
}
|
|
|
|
if (Child[2] == nullptr && Child[3] == nullptr && Error[1] * ThresholdDetail < size) {
|
|
quadsquare* s = GetNeighbor(3, cd);
|
|
if (s == nullptr || (s->Child[0] == nullptr && s->Child[1] == nullptr)) {
|
|
float y = (cd.Verts[2].Y + cd.Verts[3].Y) * 0.5f;
|
|
Vertex[4].Y = y;
|
|
Error[1] = 0;
|
|
|
|
if (s) s->Vertex[2].Y = y;
|
|
Dirty = true;
|
|
}
|
|
}
|
|
|
|
bool StaticChildren = false;
|
|
for (int i = 0; i < 4; i++) {
|
|
if (Child[i]) {
|
|
StaticChildren = true;
|
|
if (Child[i]->Dirty) Dirty = true;
|
|
}
|
|
}
|
|
|
|
if (StaticChildren == false && cd.Parent != nullptr) {
|
|
bool NecessaryEdges = false;
|
|
for (int i = 0; i < 4; i++) {
|
|
float diff = std::fabs(Vertex[i+1].Y - (cd.Verts[i].Y
|
|
+ cd.Verts[(i+3)&3].Y) * 0.5f);
|
|
if (diff > 0.00001f) {
|
|
NecessaryEdges = true;
|
|
}
|
|
}
|
|
|
|
if (!NecessaryEdges) {
|
|
size *= 1.414213562f;
|
|
if (cd.Parent->Square->Error[2 + cd.ChildIndex] * ThresholdDetail < size) {
|
|
delete cd.Parent->Square->Child[cd.ChildIndex];
|
|
cd.Parent->Square->Child[cd.ChildIndex] = 0;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void quadsquare::EnableEdgeVertex(int index, bool IncrementCount, const quadcornerdata& cd) {
|
|
int ct = 0;
|
|
int stack[32];
|
|
|
|
|
|
if ((EnabledFlags & (1 << index)) && IncrementCount == false) return;
|
|
|
|
EnabledFlags |= 1 << index;
|
|
if (IncrementCount == true && (index == 0 || index == 3)) {
|
|
SubEnabledCount[index & 1]++;
|
|
}
|
|
quadsquare* p = this;
|
|
const quadcornerdata* pcd = &cd;
|
|
for (;;) {
|
|
int ci = pcd->ChildIndex;
|
|
if (pcd->Parent == nullptr || pcd->Parent->Square == nullptr) return;
|
|
p = pcd->Parent->Square;
|
|
pcd = pcd->Parent;
|
|
|
|
bool SameParent = ((index - ci) & 2) ? true : false;
|
|
|
|
ci = ci ^ 1 ^ ((index & 1) << 1);
|
|
|
|
stack[ct] = ci;
|
|
ct++;
|
|
|
|
if (SameParent) break;
|
|
}
|
|
|
|
p = p->EnableDescendant(ct, stack, *pcd);
|
|
|
|
index ^= 2;
|
|
p->EnabledFlags |= (1 << index);
|
|
if (IncrementCount == true && (index == 0 || index == 3)) {
|
|
p->SubEnabledCount[index & 1]++;
|
|
}
|
|
}
|
|
|
|
|
|
quadsquare* quadsquare::EnableDescendant(int count, int path[], const quadcornerdata& cd) {
|
|
count--;
|
|
int ChildIndex = path[count];
|
|
|
|
if ((EnabledFlags & (16 << ChildIndex)) == 0) {
|
|
EnableChild(ChildIndex, cd);
|
|
}
|
|
|
|
if (count > 0) {
|
|
quadcornerdata q;
|
|
SetupCornerData(&q, cd, ChildIndex);
|
|
return Child[ChildIndex]->EnableDescendant(count, path, q);
|
|
} else {
|
|
return Child[ChildIndex];
|
|
}
|
|
}
|
|
|
|
|
|
void quadsquare::CreateChild(int index, const quadcornerdata& cd) {
|
|
if (Child[index] == 0) {
|
|
quadcornerdata q;
|
|
SetupCornerData(&q, cd, index);
|
|
|
|
Child[index] = new quadsquare(&q);
|
|
}
|
|
}
|
|
|
|
void quadsquare::EnableChild(int index, const quadcornerdata& cd) {
|
|
if ((EnabledFlags & (16 << index)) == 0) {
|
|
EnabledFlags |= (16 << index);
|
|
EnableEdgeVertex(index, true, cd);
|
|
EnableEdgeVertex((index + 1) & 3, true, cd);
|
|
|
|
if (Child[index] == 0) {
|
|
CreateChild(index, cd);
|
|
}
|
|
}
|
|
}
|
|
|
|
void quadsquare::NotifyChildDisable(const quadcornerdata& cd, int index) {
|
|
EnabledFlags &= ~(16 << index);
|
|
quadsquare* s;
|
|
|
|
if (index & 2) s = this;
|
|
else s = GetNeighbor(1, cd);
|
|
if (s) {
|
|
s->SubEnabledCount[1]--;
|
|
}
|
|
|
|
if (index == 1 || index == 2) s = GetNeighbor(2, cd);
|
|
else s = this;
|
|
if (s) {
|
|
s->SubEnabledCount[0]--;
|
|
}
|
|
}
|
|
|
|
static float DetailThreshold = 100;
|
|
|
|
|
|
bool quadsquare::VertexTest(int x, float y, int z, float error,
|
|
const float Viewer[3], int level, vertex_loc_t vertex_loc) const {
|
|
float dx = std::fabs(x - Viewer[0]) * std::fabs(ScaleX);
|
|
float dy = std::fabs(y - Viewer[1]);
|
|
float dz = std::fabs(z - Viewer[2]) * std::fabs(ScaleZ);
|
|
float d = std::max(dx, std::max(dy, dz));
|
|
|
|
if (vertex_loc == South && ForceSouthVert && d < VERTEX_FORCE_THRESHOLD) {
|
|
return true;
|
|
}
|
|
if (vertex_loc == East && ForceEastVert && d < VERTEX_FORCE_THRESHOLD) {
|
|
return true;
|
|
}
|
|
if (d < ERROR_MAGNIFICATION_THRESHOLD) {
|
|
error *= ERROR_MAGNIFICATION_AMOUNT;
|
|
}
|
|
|
|
return error * DetailThreshold > d;
|
|
}
|
|
|
|
bool quadsquare::BoxTest(int x, int z, float size, float miny, float maxy, float error, const float Viewer[3]) {
|
|
float half = size * 0.5f;
|
|
float dx = (std::fabs(x + half - Viewer[0]) - half) * std::fabs(ScaleX);
|
|
float dy = std::fabs((miny + maxy) * 0.5f - Viewer[1]) - (maxy - miny) * 0.5f;
|
|
float dz = (std::fabs(z + half - Viewer[2]) - half) * std::fabs(ScaleZ);
|
|
float d = std::max(dx, std::max(dy, dz));
|
|
|
|
if (d < ERROR_MAGNIFICATION_THRESHOLD) {
|
|
error *= ERROR_MAGNIFICATION_AMOUNT;
|
|
}
|
|
|
|
if (error * DetailThreshold > d) {
|
|
return true;
|
|
}
|
|
if ((x < RowSize-1 && x+size >= RowSize) ||
|
|
(z < NumRows-1 && z+size >= NumRows)) {
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
void quadsquare::Update(const quadcornerdata& cd, const TVector3d& ViewerLocation, float Detail) {
|
|
float Viewer[3];
|
|
|
|
DetailThreshold = Detail;
|
|
Viewer[0] = ViewerLocation.x / ScaleX;
|
|
Viewer[1] = ViewerLocation.y;
|
|
Viewer[2] = ViewerLocation.z / ScaleZ;
|
|
UpdateAux(cd, Viewer, 0, SomeClip);
|
|
}
|
|
|
|
|
|
void quadsquare::UpdateAux(const quadcornerdata& cd,
|
|
const float ViewerLocation[3], float CenterError, clip_result_t vis) {
|
|
if (vis != NoClip) {
|
|
vis = ClipSquare(cd);
|
|
|
|
if (vis == NotVisible) {
|
|
return;
|
|
}
|
|
}
|
|
if (Dirty) {
|
|
RecomputeError(cd);
|
|
}
|
|
|
|
int half = 1 << cd.Level;
|
|
int whole = half << 1;
|
|
if ((EnabledFlags & 1) == 0 &&
|
|
VertexTest(cd.xorg + whole, Vertex[1].Y, cd.zorg + half,
|
|
Error[0], ViewerLocation, cd.Level, East) == true) {
|
|
EnableEdgeVertex(0, false, cd);
|
|
}
|
|
|
|
if ((EnabledFlags & 8) == 0 &&
|
|
VertexTest(cd.xorg + half, Vertex[4].Y, cd.zorg + whole,
|
|
Error[1], ViewerLocation, cd.Level, South) == true) {
|
|
EnableEdgeVertex(3, false, cd);
|
|
}
|
|
|
|
if (cd.Level > 0) {
|
|
if ((EnabledFlags & 32) == 0) {
|
|
if (BoxTest(cd.xorg, cd.zorg, half, MinY, MaxY, Error[3],
|
|
ViewerLocation) == true) EnableChild(1, cd);
|
|
}
|
|
if ((EnabledFlags & 16) == 0) {
|
|
if (BoxTest(cd.xorg + half, cd.zorg, half, MinY, MaxY,
|
|
Error[2], ViewerLocation) == true) EnableChild(0, cd);
|
|
}
|
|
if ((EnabledFlags & 64) == 0) {
|
|
if (BoxTest(cd.xorg, cd.zorg + half, half, MinY, MaxY,
|
|
Error[4], ViewerLocation) == true) EnableChild(2, cd);
|
|
}
|
|
if ((EnabledFlags & 128) == 0) {
|
|
if (BoxTest(cd.xorg + half, cd.zorg + half, half, MinY, MaxY,
|
|
Error[5], ViewerLocation) == true) EnableChild(3, cd);
|
|
}
|
|
|
|
quadcornerdata q;
|
|
|
|
if (EnabledFlags & 32) {
|
|
SetupCornerData(&q, cd, 1);
|
|
Child[1]->UpdateAux(q, ViewerLocation, Error[3], vis);
|
|
}
|
|
if (EnabledFlags & 16) {
|
|
SetupCornerData(&q, cd, 0);
|
|
Child[0]->UpdateAux(q, ViewerLocation, Error[2], vis);
|
|
}
|
|
if (EnabledFlags & 64) {
|
|
SetupCornerData(&q, cd, 2);
|
|
Child[2]->UpdateAux(q, ViewerLocation, Error[4], vis);
|
|
}
|
|
if (EnabledFlags & 128) {
|
|
SetupCornerData(&q, cd, 3);
|
|
Child[3]->UpdateAux(q, ViewerLocation, Error[5], vis);
|
|
}
|
|
}
|
|
if ((EnabledFlags & 1) &&
|
|
SubEnabledCount[0] == 0 &&
|
|
VertexTest(cd.xorg + whole, Vertex[1].Y, cd.zorg + half,
|
|
Error[0], ViewerLocation, cd.Level, East) == false) {
|
|
EnabledFlags &= ~1;
|
|
quadsquare* s = GetNeighbor(0, cd);
|
|
if (s) s->EnabledFlags &= ~4;
|
|
}
|
|
|
|
if ((EnabledFlags & 8) &&
|
|
SubEnabledCount[1] == 0 &&
|
|
VertexTest(cd.xorg + half, Vertex[4].Y, cd.zorg + whole,
|
|
Error[1], ViewerLocation, cd.Level, South) == false) {
|
|
EnabledFlags &= ~8;
|
|
quadsquare* s = GetNeighbor(3, cd);
|
|
if (s) s->EnabledFlags &= ~2;
|
|
}
|
|
|
|
if (EnabledFlags == 0 &&
|
|
cd.Parent != nullptr &&
|
|
BoxTest(cd.xorg, cd.zorg, whole, MinY, MaxY, CenterError,
|
|
ViewerLocation) == false) {
|
|
cd.Parent->Square->NotifyChildDisable(*cd.Parent, cd.ChildIndex);
|
|
}
|
|
}
|
|
|
|
GLuint VertexIndices[9];
|
|
int VertexTerrains[9];
|
|
|
|
void quadsquare::InitVert(int i, int x, int z) {
|
|
if (x >= RowSize) x = RowSize-1;
|
|
if (z >= NumRows) z = NumRows - 1;
|
|
|
|
int idx = x + RowSize * z;
|
|
|
|
VertexIndices[i] = idx;
|
|
VertexTerrains[i] = Fields[idx].terrain;
|
|
}
|
|
|
|
GLubyte *VNCArray;
|
|
|
|
void quadsquare::DrawTris() {
|
|
int tmp_min_idx = VertexArrayMinIdx;
|
|
|
|
if (glLockArraysEXT_p) {
|
|
if (tmp_min_idx == 0) tmp_min_idx = 1;
|
|
glLockArraysEXT_p(tmp_min_idx, VertexArrayMaxIdx - tmp_min_idx + 1);
|
|
}
|
|
|
|
glDrawElements(GL_TRIANGLES, VertexArrayCounter,
|
|
GL_UNSIGNED_INT, VertexArrayIndices);
|
|
if (glUnlockArraysEXT_p) glUnlockArraysEXT_p();
|
|
}
|
|
|
|
void quadsquare::InitArrayCounters() {
|
|
VertexArrayCounter = 0;
|
|
VertexArrayMinIdx = INT_MAX;
|
|
VertexArrayMaxIdx = 0;
|
|
}
|
|
|
|
void quadsquare::Render(const quadcornerdata& cd, GLubyte *vnc_array) {
|
|
VNCArray = vnc_array;
|
|
|
|
std::size_t numTerrains = Course.TerrList.size();
|
|
for (std::size_t j=0; j<numTerrains; j++) {
|
|
if (Course.TerrList[j].texture != nullptr) {
|
|
InitArrayCounters();
|
|
RenderAux(cd, SomeClip, (int)j);
|
|
if (VertexArrayCounter == 0) continue;
|
|
|
|
Course.TerrList[j].texture->Bind();
|
|
DrawTris();
|
|
}
|
|
}
|
|
|
|
if (param.perf_level > 1) {
|
|
InitArrayCounters();
|
|
RenderAux(cd, SomeClip, -1);
|
|
|
|
if (VertexArrayCounter != 0) {
|
|
glDisable(GL_FOG);
|
|
for (GLuint i=0; i<VertexArrayCounter; i++) {
|
|
colorval(VertexArrayIndices[i], 0) = 0;
|
|
colorval(VertexArrayIndices[i], 1) = 0;
|
|
colorval(VertexArrayIndices[i], 2) = 0;
|
|
colorval(VertexArrayIndices[i], 3) = 255;
|
|
}
|
|
Course.TerrList[0].texture->Bind();
|
|
DrawTris();
|
|
//if (fog_on)
|
|
glEnable(GL_FOG);
|
|
glBlendFunc(GL_SRC_ALPHA, GL_ONE);
|
|
for (GLuint i=0; i<VertexArrayCounter; i++) {
|
|
colorval(VertexArrayIndices[i], 0) = 255;
|
|
colorval(VertexArrayIndices[i], 1) = 255;
|
|
colorval(VertexArrayIndices[i], 2) = 255;
|
|
}
|
|
|
|
for (std::size_t j=0; j<numTerrains; j++) {
|
|
if (Course.TerrList[j].texture != nullptr) {
|
|
Course.TerrList[j].texture->Bind();
|
|
|
|
for (GLuint i=0; i<VertexArrayCounter; i++) {
|
|
colorval(VertexArrayIndices[i], 3) =
|
|
(Fields[VertexArrayIndices[i]].terrain == (char)j) ? 255 : 0;
|
|
}
|
|
DrawTris();
|
|
}
|
|
}
|
|
}
|
|
}
|
|
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
|
|
}
|
|
|
|
clip_result_t quadsquare::ClipSquare(const quadcornerdata& cd) {
|
|
if (cd.xorg >= RowSize-1) {
|
|
return NotVisible;
|
|
}
|
|
|
|
if (cd.zorg >= NumRows-1) {
|
|
return NotVisible;
|
|
}
|
|
|
|
int whole = 2 << cd.Level;
|
|
TVector3d minimum(
|
|
cd.xorg * ScaleX,
|
|
MinY,
|
|
cd.zorg * ScaleZ);
|
|
TVector3d maximum(
|
|
(cd.xorg + whole) * ScaleX,
|
|
MaxY,
|
|
(cd.zorg + whole) * ScaleZ);
|
|
|
|
if (minimum.x > maximum.x)
|
|
std::swap(minimum.x, maximum.x);
|
|
|
|
if (minimum.z > maximum.z)
|
|
std::swap(minimum.z, maximum.z);
|
|
|
|
clip_result_t clip_result = clip_aabb_to_view_frustum(minimum, maximum);
|
|
|
|
if (clip_result == NotVisible || clip_result == SomeClip) {
|
|
return clip_result;
|
|
}
|
|
|
|
if (cd.xorg + whole >= RowSize) {
|
|
return SomeClip;
|
|
}
|
|
if (cd.zorg + whole >= NumRows) {
|
|
return SomeClip;
|
|
}
|
|
|
|
return clip_result;
|
|
}
|
|
|
|
|
|
inline void quadsquare::MakeTri(int a, int b, int c, int terrain) {
|
|
if ((VertexTerrains[a] == terrain ||
|
|
VertexTerrains[b] == terrain ||
|
|
VertexTerrains[c] == terrain)) {
|
|
VertexArrayIndices[VertexArrayCounter++] = VertexIndices[a];
|
|
setalphaval(a);
|
|
update_min_max(VertexIndices[a]);
|
|
VertexArrayIndices[VertexArrayCounter++] = VertexIndices[b];
|
|
setalphaval(b);
|
|
update_min_max(VertexIndices[b]);
|
|
VertexArrayIndices[VertexArrayCounter++] = VertexIndices[c];
|
|
setalphaval(c);
|
|
update_min_max(VertexIndices[c]);
|
|
}
|
|
}
|
|
|
|
|
|
inline void quadsquare::MakeSpecialTri(int a, int b, int c, int terrain) {
|
|
if (VertexTerrains[a] != VertexTerrains[b] &&
|
|
VertexTerrains[a] != VertexTerrains[c] &&
|
|
VertexTerrains[b] != VertexTerrains[c]) {
|
|
VertexArrayIndices[VertexArrayCounter++] = VertexIndices[a];
|
|
update_min_max(VertexIndices[a]);
|
|
VertexArrayIndices[VertexArrayCounter++] = VertexIndices[b];
|
|
update_min_max(VertexIndices[b]);
|
|
VertexArrayIndices[VertexArrayCounter++] = VertexIndices[c];
|
|
update_min_max(VertexIndices[c]);
|
|
}
|
|
}
|
|
|
|
inline void quadsquare::MakeNoBlendTri(int a, int b, int c, int terrain) {
|
|
if ((VertexTerrains[a] == terrain ||
|
|
VertexTerrains[b] == terrain ||
|
|
VertexTerrains[c] == terrain) &&
|
|
(VertexTerrains[a] >= terrain &&
|
|
VertexTerrains[b] >= terrain &&
|
|
VertexTerrains[c] >= terrain)) {
|
|
VertexArrayIndices[VertexArrayCounter++] = VertexIndices[a];
|
|
setalphaval(a);
|
|
update_min_max(VertexIndices[a]);
|
|
VertexArrayIndices[VertexArrayCounter++] = VertexIndices[b];
|
|
setalphaval(b);
|
|
update_min_max(VertexIndices[b]);
|
|
VertexArrayIndices[VertexArrayCounter++] = VertexIndices[c];
|
|
setalphaval(c);
|
|
update_min_max(VertexIndices[c]);
|
|
}
|
|
}
|
|
|
|
void quadsquare::RenderAux(const quadcornerdata& cd, clip_result_t vis, int terrain) {
|
|
int half = 1 << cd.Level;
|
|
int whole = 2 << cd.Level;
|
|
if (vis != NoClip) {
|
|
vis = ClipSquare(cd);
|
|
if (vis == NotVisible) return;
|
|
}
|
|
|
|
int flags = 0;
|
|
int mask = 1;
|
|
quadcornerdata q;
|
|
|
|
for (int i = 0; i < 4; i++, mask <<= 1) {
|
|
if (EnabledFlags & (16 << i)) {
|
|
SetupCornerData(&q, cd, i);
|
|
Child[i]->RenderAux(q, vis, terrain);
|
|
} else {
|
|
flags |= mask;
|
|
}
|
|
}
|
|
|
|
if (flags == 0) return;
|
|
|
|
InitVert(0, cd.xorg + half, cd.zorg + half);
|
|
InitVert(1, cd.xorg + whole, cd.zorg + half);
|
|
InitVert(2, cd.xorg + whole, cd.zorg);
|
|
InitVert(3, cd.xorg + half, cd.zorg);
|
|
InitVert(4, cd.xorg, cd.zorg);
|
|
InitVert(5, cd.xorg, cd.zorg + half);
|
|
InitVert(6, cd.xorg, cd.zorg + whole);
|
|
InitVert(7, cd.xorg + half, cd.zorg + whole);
|
|
InitVert(8, cd.xorg + whole, cd.zorg + whole);
|
|
if (terrain == -1) {
|
|
make_tri_list(MakeSpecialTri, EnabledFlags, flags, terrain);
|
|
} else if (param.perf_level > 1) {
|
|
make_tri_list(MakeTri, EnabledFlags, flags, terrain);
|
|
} else {
|
|
make_tri_list(MakeNoBlendTri, EnabledFlags, flags, terrain);
|
|
}
|
|
|
|
}
|
|
|
|
|
|
void quadsquare::SetupCornerData(quadcornerdata* q, const quadcornerdata& cd, int ChildIndex) {
|
|
int half = 1 << cd.Level;
|
|
|
|
q->Parent = &cd;
|
|
q->Square = Child[ChildIndex];
|
|
q->Level = cd.Level - 1;
|
|
q->ChildIndex = ChildIndex;
|
|
|
|
switch (ChildIndex) {
|
|
default:
|
|
case 0:
|
|
q->xorg = cd.xorg + half;
|
|
q->zorg = cd.zorg;
|
|
q->Verts[0] = cd.Verts[0];
|
|
q->Verts[1] = Vertex[2];
|
|
q->Verts[2] = Vertex[0];
|
|
q->Verts[3] = Vertex[1];
|
|
break;
|
|
|
|
case 1:
|
|
q->xorg = cd.xorg;
|
|
q->zorg = cd.zorg;
|
|
q->Verts[0] = Vertex[2];
|
|
q->Verts[1] = cd.Verts[1];
|
|
q->Verts[2] = Vertex[3];
|
|
q->Verts[3] = Vertex[0];
|
|
break;
|
|
|
|
case 2:
|
|
q->xorg = cd.xorg;
|
|
q->zorg = cd.zorg + half;
|
|
q->Verts[0] = Vertex[0];
|
|
q->Verts[1] = Vertex[3];
|
|
q->Verts[2] = cd.Verts[2];
|
|
q->Verts[3] = Vertex[4];
|
|
break;
|
|
|
|
case 3:
|
|
q->xorg = cd.xorg + half;
|
|
q->zorg = cd.zorg + half;
|
|
q->Verts[0] = Vertex[1];
|
|
q->Verts[1] = Vertex[0];
|
|
q->Verts[2] = Vertex[4];
|
|
q->Verts[3] = cd.Verts[3];
|
|
break;
|
|
}
|
|
}
|
|
|
|
int quadsquare::RowSize;
|
|
int quadsquare::NumRows;
|
|
|
|
void quadsquare::AddHeightMap(const quadcornerdata& cd, const HeightMapInfo& hm) {
|
|
RowSize = hm.RowWidth;
|
|
NumRows = hm.ZSize;
|
|
|
|
if (cd.Parent == nullptr) {
|
|
if (VertexArrayIndices != nullptr) {
|
|
delete[] VertexArrayIndices;
|
|
}
|
|
VertexArrayIndices = new GLuint[6 * RowSize * NumRows];
|
|
}
|
|
int BlockSize = 2 << cd.Level;
|
|
if (cd.xorg > hm.XOrigin + ((hm.XSize + 2) << hm.Scale) ||
|
|
cd.xorg + BlockSize < hm.XOrigin - (1 << hm.Scale) ||
|
|
cd.zorg > hm.ZOrigin + ((hm.ZSize + 2) << hm.Scale) ||
|
|
cd.zorg + BlockSize < hm.ZOrigin - (1 << hm.Scale)) {
|
|
return;
|
|
}
|
|
|
|
if (cd.Parent && cd.Parent->Square) {
|
|
cd.Parent->Square->EnableChild(cd.ChildIndex, *cd.Parent);
|
|
}
|
|
|
|
int half = 1 << cd.Level;
|
|
for (int i = 0; i < 4; i++) {
|
|
quadcornerdata q;
|
|
SetupCornerData(&q, cd, i);
|
|
|
|
if (Child[i] == nullptr && cd.Level > hm.Scale) {
|
|
Child[i] = new quadsquare(&q);
|
|
}
|
|
if (Child[i]) {
|
|
Child[i]->AddHeightMap(q, hm);
|
|
}
|
|
}
|
|
float s[5];
|
|
s[0] = hm.Sample(cd.xorg + half, cd.zorg + half);
|
|
s[1] = hm.Sample(cd.xorg + half*2, cd.zorg + half);
|
|
s[2] = hm.Sample(cd.xorg + half, cd.zorg);
|
|
s[3] = hm.Sample(cd.xorg, cd.zorg + half);
|
|
s[4] = hm.Sample(cd.xorg + half, cd.zorg + half*2);
|
|
|
|
for (int i = 0; i < 5; i++) {
|
|
if (s[i] != 0) {
|
|
Dirty = true;
|
|
Vertex[i].Y += s[i];
|
|
}
|
|
}
|
|
|
|
if (!Dirty) {
|
|
for (int i = 0; i < 4; i++) {
|
|
if (Child[i] && Child[i]->Dirty) {
|
|
Dirty = true;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (Dirty) SetStatic(cd);
|
|
}
|
|
|
|
double quadsquare::ScaleX;
|
|
double quadsquare::ScaleZ;
|
|
void quadsquare::SetScale(double x, double z) {
|
|
ScaleX = x;
|
|
ScaleZ = z;
|
|
}
|
|
|
|
CourseFields* quadsquare::Fields;
|
|
void quadsquare::SetFields(CourseFields* fields) {
|
|
Fields = fields;
|
|
}
|
|
|
|
float HeightMapInfo::Sample(int x, int z) const {
|
|
if (x >= XSize) {
|
|
x = XSize - 1;
|
|
}
|
|
if (z >= ZSize) {
|
|
z = ZSize - 1;
|
|
}
|
|
return Data[ x + z * RowWidth ].elevation;
|
|
}
|
|
|
|
// --------------------------------------------------------------------
|
|
// global calls
|
|
// --------------------------------------------------------------------
|
|
|
|
#define CULL_DETAIL_FACTOR 25
|
|
|
|
static quadsquare *root = (quadsquare*) nullptr;
|
|
static quadcornerdata root_corner_data = {(quadcornerdata*)nullptr };
|
|
|
|
void ResetQuadtree() {
|
|
if (root != nullptr) {
|
|
delete root;
|
|
root = (quadsquare*) nullptr;
|
|
}
|
|
}
|
|
|
|
static int get_root_level(int nx, int nz) {
|
|
return (int)std::log2(static_cast<double>(std::max(nx, nz)));
|
|
}
|
|
|
|
|
|
void InitQuadtree(CourseFields* fields, int nx, int nz,
|
|
double scalex, double scalez, const TVector3d& view_pos, double detail) {
|
|
HeightMapInfo hm;
|
|
|
|
hm.Data = fields;
|
|
hm.XOrigin = 0;
|
|
hm.ZOrigin = 0;
|
|
hm.XSize = nx;
|
|
hm.ZSize = nz;
|
|
hm.RowWidth = hm.XSize;
|
|
hm.Scale = 0;
|
|
|
|
root_corner_data.Square = nullptr;
|
|
root_corner_data.ChildIndex = 0;
|
|
root_corner_data.Level = get_root_level(nx, nz);
|
|
root_corner_data.xorg = 0;
|
|
root_corner_data.zorg = 0;
|
|
|
|
for (int i=0; i<4; i++) {
|
|
root_corner_data.Verts[i].Y = 0;
|
|
root_corner_data.Verts[i].Y = 0;
|
|
}
|
|
|
|
root = new quadsquare(&root_corner_data);
|
|
root->AddHeightMap(root_corner_data, hm);
|
|
root->SetScale(scalex, scalez);
|
|
root->SetFields(&Course.Fields[0]);
|
|
|
|
root->StaticCullData(root_corner_data, CULL_DETAIL_FACTOR);
|
|
|
|
for (int i = 0; i < 10; i++) {
|
|
root->Update(root_corner_data, view_pos, detail);
|
|
}
|
|
}
|
|
|
|
void UpdateQuadtree(const TVector3d& view_pos, float detail) {
|
|
root->Update(root_corner_data, view_pos, detail);
|
|
}
|
|
|
|
void RenderQuadtree() {
|
|
GLubyte *vnc_array = Course.GetGLArrays();
|
|
|
|
glEnableClientState(GL_VERTEX_ARRAY);
|
|
glVertexPointer(3, GL_FLOAT, STRIDE_GL_ARRAY, vnc_array);
|
|
|
|
glEnableClientState(GL_NORMAL_ARRAY);
|
|
glNormalPointer(GL_FLOAT, STRIDE_GL_ARRAY,
|
|
vnc_array + 4 * sizeof(GLfloat));
|
|
|
|
glEnableClientState(GL_COLOR_ARRAY);
|
|
glColorPointer(4, GL_UNSIGNED_BYTE, STRIDE_GL_ARRAY,
|
|
vnc_array + 8 * sizeof(GLfloat));
|
|
|
|
root->Render(root_corner_data, vnc_array);
|
|
|
|
glDisableClientState(GL_VERTEX_ARRAY);
|
|
glDisableClientState(GL_NORMAL_ARRAY);
|
|
glDisableClientState(GL_COLOR_ARRAY);
|
|
}
|