Back to index

extremetuxracer  0.5beta
quadtree.cpp
Go to the documentation of this file.
00001 // quadtree.cpp      -thatcher 9/15/1999 Copyright 1999-2000 Thatcher Ulrich
00002 
00003 // Code for quadtree terrain manipulation, meshing, and display.
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 #include "textures.h"
00017 #include "course_load.h"
00018 #include "fog.h"
00019 #include "gl_util.h"
00020 #include "course_render.h"
00021 #include "game_config.h"
00022 
00023 
00024 #include "ppgltk/alg/defs.h"
00025 
00026 #include "quadtree.h"
00027 
00028 
00029 /* Amount to scale terrain errors by in order to be comparable to
00030    height errors */
00031 #define TERRAIN_ERROR_SCALE 0.1
00032 
00033 /* Distance at which we force the activation of vertices that lie on
00034    texture edges */
00035 #define VERTEX_FORCE_THRESHOLD 120
00036 
00037 /* Maximum Distance at which we magnify the error term (to minimize
00038    popping near the camera */
00039 #define ERROR_MAGNIFICATION_THRESHOLD 30
00040 
00041 /* Amount to magnify errors by within ERROR_MAGNIFICATION_THRESHOLD */
00042 #define ERROR_MAGNIFICATION_AMOUNT 3
00043 
00044 /* Environment map alpha value, integer from 0-255 */ 
00045 #define ENV_MAP_ALPHA 50
00046 
00047 /* Useful macro for setting colors in the color array */
00048 #define colorval(j,ch) \
00049 VNCArray[j*STRIDE_GL_ARRAY+STRIDE_GL_ARRAY-4+(ch)]
00050 
00051 
00052 extern terrain_tex_t terrain_texture[NUM_TERRAIN_TYPES];
00053 extern unsigned int num_terrains;
00054 
00055 int terrain_count[NUM_TERRAIN_TYPES];
00056 
00057 //
00058 // quadsquare functions.
00059 //
00060 
00061 GLuint *quadsquare::VertexArrayIndices[NUM_TERRAIN_TYPES]; 
00062 GLuint quadsquare::VertexArrayCounter[NUM_TERRAIN_TYPES];
00063 GLuint quadsquare::VertexArrayMinIdx[NUM_TERRAIN_TYPES];
00064 GLuint quadsquare::VertexArrayMaxIdx[NUM_TERRAIN_TYPES];
00065 
00066 quadsquare::quadsquare(quadcornerdata* pcd)
00068 {
00069     pcd->Square = this;
00070        
00071     // Set static to true if/when this node contains real data, and
00072     // not just interpolated values.  When static == false, a node
00073     // can be deleted by the Update() function if none of its
00074     // vertices or children are enabled.
00075     Static = false;
00076 
00077     unsigned int     i;
00078 
00079        Child[0] = (quadsquare*) NULL;
00080        Child[1] = (quadsquare*) NULL;
00081        Child[2] = (quadsquare*) NULL;     
00082        Child[3] = (quadsquare*) NULL;
00083 
00084 
00085     EnabledFlags = 0;
00086        
00087        SubEnabledCount[0] = 0;
00088        SubEnabledCount[1] = 0;
00089 
00090        
00091     // Set default vertex positions by interpolating from given corners.
00092     // Just bilinear interpolation.
00093     Vertex[0] = 0.25 * (pcd->Verts[0] + pcd->Verts[1] + pcd->Verts[2] + pcd->Verts[3]);
00094     Vertex[1] = 0.5 * (pcd->Verts[3] + pcd->Verts[0]);
00095     Vertex[2] = 0.5 * (pcd->Verts[0] + pcd->Verts[1]);
00096     Vertex[3] = 0.5 * (pcd->Verts[1] + pcd->Verts[2]);
00097     Vertex[4] = 0.5 * (pcd->Verts[2] + pcd->Verts[3]);
00098 
00099     for (i = 0; i < 2; i++) {
00100        Error[i] = 0;
00101     }
00102     for (i = 0; i < 4; i++) {
00103        Error[i+2] = fabs((Vertex[0] + pcd->Verts[i]) - (Vertex[i+1] + Vertex[((i+1)&3) + 1])) * 0.25;
00104     }
00105 
00106     // Compute MinY/MaxY based on corner verts.
00107     MinY = MaxY = pcd->Verts[0];
00108     for (i = 1; i < 4; i++) {
00109        float  y = pcd->Verts[i];
00110        if (y < MinY) MinY = y;
00111        if (y > MaxY) MaxY = y;
00112     }
00113 
00114     if ( pcd->Parent == NULL ) {
00115               print_debug( DEBUG_QUADTREE, "initializing root node" );
00116               for (int i=0; i< NUM_TERRAIN_TYPES; i++){
00117                      VertexArrayIndices[0] = NULL;             
00118               }
00119               Terrain = get_course_terrain_data();
00120     }
00121 }
00122 
00123 
00124 quadsquare::~quadsquare()
00126 {
00127     // Recursively delete sub-trees.
00128     for (int i = 0; i < 4; i++) {
00129               if (Child[i]) delete Child[i];
00130               Child[i] = (quadsquare*) NULL;
00131     }
00132 }
00133 
00134 
00135 void   quadsquare::SetStatic(const quadcornerdata& cd)
00139 {
00140     if (Static == false) {
00141        Static = true;
00142               
00143               // Propagate static status to ancestor nodes.
00144               if (cd.Parent && cd.Parent->Square) {
00145                   cd.Parent->Square->SetStatic(*cd.Parent);
00146               }
00147     }
00148 }
00149 
00150 
00151 int    quadsquare::CountNodes()
00153 {
00154     int       count = 1;    // Count ourself.
00155 
00156     // Count descendants.
00157     for (int i = 0; i < 4; i++) {
00158               if (Child[i]) count += Child[i]->CountNodes();
00159     }
00160 
00161     return count;
00162 }
00163 
00164 
00165 float  quadsquare::GetHeight(const quadcornerdata& cd, const float x, const float z)
00167 {
00168     int       half = 1 << cd.Level;
00169 
00170     float     lx = (x - cd.xorg) / float(half);
00171     float     lz = (z - cd.zorg) / float(half);
00172 
00173     int       ix = (int) floor(lx);
00174     int       iz = (int) floor(lz);
00175 
00176     // Clamp.
00177     if (ix < 0) ix = 0;
00178     if (ix > 1) ix = 1;
00179     if (iz < 0) iz = 0;
00180     if (iz > 1) iz = 1;
00181 
00182     int       index = ix ^ (iz ^ 1) + (iz << 1);
00183     if (Child[index] && Child[index]->Static) {
00184        // Pass the query down to the child which contains it.
00185        quadcornerdata       q;
00186        SetupCornerData(&q, cd, index);
00187        return Child[index]->GetHeight(q, x, z);
00188     }
00189 
00190     // Bilinear interpolation.
00191     lx -= ix;
00192     if (lx < 0) lx = 0;
00193     if (lx > 1) lx = 1;
00194        
00195     lz -= iz;
00196     if (lx < 0) lz = 0;
00197     if (lz > 1) lz = 1;
00198 
00199     float     s00, s01, s10, s11;
00200     switch (index) {
00201     default:
00202     case 0:
00203        s00 = Vertex[2];
00204        s01 = cd.Verts[0];
00205        s10 = Vertex[0];
00206        s11 = Vertex[1];
00207        break;
00208     case 1:
00209        s00 = cd.Verts[1];
00210        s01 = Vertex[2];
00211        s10 = Vertex[3];
00212        s11 = Vertex[0];
00213        break;
00214     case 2:
00215        s00 = Vertex[3];
00216        s01 = Vertex[0];
00217        s10 = cd.Verts[2];
00218        s11 = Vertex[4];
00219        break;
00220     case 3:
00221        s00 = Vertex[0];
00222        s01 = Vertex[1];
00223        s10 = Vertex[4];
00224        s11 = cd.Verts[3];
00225        break;
00226     }
00227 
00228     return (s00 * (1-lx) + s01 * lx) * (1 - lz) + (s10 * (1-lx) + s11 * lx) * lz;
00229 }
00230 
00231 
00232 quadsquare*   quadsquare::GetNeighbor(const int dir, const quadcornerdata& cd) const
00236 {
00237     // If we don't have a parent, then we don't have a neighbor.
00238     // (Actually, we could have inter-tree connectivity at this level
00239     // for connecting separate trees together.)
00240     if (cd.Parent == 0) return 0;
00241        
00242     // Find the parent and the child-index of the square we want to locate or create.
00243     quadsquare*      p = 0;
00244        
00245     int       index = cd.ChildIndex ^ 1 ^ ((dir & 1) << 1);
00246     bool      SameParent = ((dir - cd.ChildIndex) & 2) ? true : false;
00247        
00248     if (SameParent) {
00249        p = cd.Parent->Square;
00250     } else {
00251        p = cd.Parent->Square->GetNeighbor(dir, *cd.Parent);
00252               
00253        if (p == 0) return 0;
00254     }
00255        
00256     quadsquare*      n = p->Child[index];
00257        
00258     return n;
00259 }
00260 
00261 float  quadsquare::RecomputeError(const quadcornerdata& cd)
00265 {
00266     int       i;
00267     int j;
00268     unsigned int t;
00269     int       half = 1 << cd.Level;
00270     int       whole = half << 1;
00271     float terrain_error;
00272        
00273     // Measure error of center and edge vertices.
00274     float     maxerror = 0;
00275 
00276     // Compute error of center vert.
00277     float     e;
00278     if (cd.ChildIndex & 1) {
00279        e = fabs(Vertex[0] - (cd.Verts[1] + cd.Verts[3]) * 0.5);
00280     } else {
00281        e = fabs(Vertex[0] - (cd.Verts[0] + cd.Verts[2]) * 0.5);
00282     }
00283     if (e > maxerror) maxerror = e;
00284 
00285     // Initial min/max.
00286     MaxY = Vertex[0];
00287     MinY = Vertex[0];
00288 
00289     // Check min/max of corners.
00290     for (i = 0; i < 4; i++) {
00291        float  y = cd.Verts[i];
00292        if (y < MinY) MinY = y;
00293        if (y > MaxY) MaxY = y;
00294     }
00295        
00296     // Edge verts.
00297     e = fabs(Vertex[1] - (cd.Verts[0] + cd.Verts[3]) * 0.5);
00298     if (e > maxerror) maxerror = e;
00299     Error[0] = e;
00300        
00301     e = fabs(Vertex[4] - (cd.Verts[2] + cd.Verts[3]) * 0.5);
00302     if (e > maxerror) maxerror = e;
00303     Error[1] = e;
00304 
00305     // Terrain edge checks
00306     if ( cd.Level == 0 && cd.xorg <= RowSize-1 && cd.zorg <= NumRows-1 ) {
00307 
00308        // Check South vertex
00309        int x = cd.xorg + half;
00310        int z = cd.zorg + whole;
00311        int idx = x  + z * RowSize;
00312        bool different_terrains = false;
00313 
00314        terrain_error = 0.f;
00315 
00316        check_assertion( x >= 0, "x coordinate is negative" );
00317        check_assertion( z >= 0, "z coordinate is negative" );
00318 
00319         if ( x < RowSize && z < NumRows ) {
00320 
00321            if ( x < RowSize - 1 ) {
00322               if ( Terrain[idx] != Terrain[idx+1] ) {
00323                   different_terrains = true;
00324               }
00325            }
00326            if ( z >= 1 ) {
00327               idx -= RowSize;
00328               if ( Terrain[idx] != Terrain[idx+1] ) {
00329                   different_terrains = true;
00330               }
00331            }
00332 
00333            if ( different_terrains ) {
00334               ForceSouthVert = true;
00335               terrain_error = TERRAIN_ERROR_SCALE * whole * whole;
00336            } else {
00337               ForceSouthVert = false;
00338            }
00339 
00340            if ( terrain_error > Error[0] ) {
00341               Error[0] = terrain_error;
00342            }
00343            if ( Error[0] > maxerror ) {
00344               maxerror = Error[0];
00345            }
00346        }
00347 
00348        // Check East vertex
00349        x = cd.xorg + whole;
00350        z = cd.zorg + half;
00351        idx = x  + z * RowSize;
00352        terrain_error = 0;
00353        different_terrains = false;
00354 
00355         if ( x < RowSize && z < NumRows ) {
00356 
00357            if ( z >= 1 ) {
00358               if ( Terrain[idx] != Terrain[idx-RowSize] ) {
00359                   different_terrains = true;
00360               }
00361            }
00362            if ( z >= 1 && x < RowSize - 1 ) {
00363               idx += 1;
00364               if ( Terrain[idx] != Terrain[idx-RowSize] ) {
00365                   different_terrains = true;
00366               }
00367            }
00368 
00369            if ( different_terrains ) {
00370               ForceEastVert = true;
00371               terrain_error = TERRAIN_ERROR_SCALE * whole * whole;
00372            } else {
00373               ForceEastVert = false;
00374            }
00375 
00376            if ( terrain_error > Error[1] ) {
00377               Error[1] = terrain_error;
00378            }
00379            if ( Error[1] > maxerror ) {
00380               maxerror = Error[1];
00381            }
00382         }
00383     }
00384 
00385     // Min/max of edge verts.
00386     for (i = 0; i < 4; i++) {
00387        float  y = Vertex[1 + i];
00388        if (y < MinY) MinY = y;
00389        if (y > MaxY) MaxY = y;
00390     }
00391        
00392     // Check child squares.
00393     for (i = 0; i < 4; i++) {
00394        quadcornerdata       q;
00395        if (Child[i]) {
00396            SetupCornerData(&q, cd, i);
00397            Error[i+2] = Child[i]->RecomputeError(q);
00398 
00399            if (Child[i]->MinY < MinY) MinY = Child[i]->MinY;
00400            if (Child[i]->MaxY > MaxY) MaxY = Child[i]->MaxY;
00401        } else {
00402            // Compute difference between bilinear average at child center, and diagonal edge approximation.
00403            Error[i+2] = fabs((Vertex[0] + cd.Verts[i]) - (Vertex[i+1] + Vertex[((i+1)&3) + 1])) * 0.25;
00404        }
00405        if (Error[i+2] > maxerror) maxerror = Error[i+2];
00406     }
00407 
00408     //
00409     // Compute terrain_error
00410     //
00411      int terrain;
00412 
00413     //int *terrain_count = new int[(int)num_terrains];
00414 
00415     for (t=0; t<num_terrains; t++) {
00416               terrain_count[t] = 0;
00417     }
00418        
00419        
00420        int i_min = (cd.xorg<0) ? 0 : cd.xorg;
00421        
00422        int i_max = ( (cd.xorg+whole) >= RowSize) ? (RowSize-1) : cd.xorg+whole;
00423        
00424        int j_min = (cd.zorg<0) ? 0 : cd.zorg;
00425        
00426        int j_max = ( (cd.zorg+whole) >= NumRows) ? (NumRows-1) : cd.zorg+whole;
00427 
00428        for (i=i_min; i<=i_max; i++) {
00429        for (j=j_min; j<=j_max; j++) {
00430 
00431            terrain = (int) Terrain[ i + RowSize*j ];
00432            check_assertion( terrain >= 0 && 
00433                           terrain < int(num_terrains),
00434                           "Invalid terrain type" );
00435            terrain_count[ terrain ] += 1;
00436        }
00437     }
00438 
00439     int max_count = 0;
00440     int max_type = 0;
00441     int total = 0;
00442     for (t=0; t<num_terrains; t++) {
00443        if ( terrain_count[t] > max_count ) {
00444            max_count = terrain_count[t];
00445            max_type = t;
00446        }
00447        total += terrain_count[t];
00448     }
00449 
00450     //delete [] terrain_count;
00451 
00452     /* Calculate a terrain error that varies between 0 and 1 */
00453     if ( total > 0 ) {
00454        terrain_error = (1.0 - max_count / total);  
00455        if ( num_terrains > 1 ) {
00456            terrain_error *= num_terrains / ( num_terrains - 1.0 );
00457        }
00458     } else {
00459        terrain_error = 0;
00460     }
00461 
00462     /* and scale it by the square area */
00463     terrain_error *= whole * whole;
00464 
00465     /* and finally scale it so that it's comparable to height error */
00466     terrain_error *= TERRAIN_ERROR_SCALE;
00467 
00468     if ( terrain_error > maxerror ) {
00469        maxerror = terrain_error;
00470     }
00471 
00472     if ( terrain_error > Error[0] ) {
00473        Error[0] = terrain_error;
00474     }
00475     if ( terrain_error > Error[1] ) {
00476        Error[1] = terrain_error;
00477     }
00478 
00479 
00480     // The error  and MinY/MaxY values for this node and descendants are correct now.
00481     Dirty = false;
00482        
00483     return maxerror;
00484 }
00485 
00486 
00487 void   quadsquare::ResetTree()
00489 {
00490        for (int i = 0; i < 4; i++) {
00491               if (Child[i]) {
00492                      Child[i]->ResetTree();
00493                      if (Child[i]->Static == false) {
00494                             delete Child[i];
00495                             Child[i] = 0;
00496               }
00497               }
00498     }
00499     EnabledFlags = 0;
00500     SubEnabledCount[0] = 0;
00501     SubEnabledCount[1] = 0;
00502     Dirty = true;
00503 }
00504 
00505 
00506 void   quadsquare::StaticCullData(const quadcornerdata& cd, const float ThresholdDetail)
00510 {
00511     // First, clean non-static nodes out of the tree.
00512     ResetTree();
00513 
00514     // Make sure error values are up-to-date.
00515     if (Dirty) RecomputeError(cd);
00516        
00517     // Recursively check all the nodes and do necessary removal.
00518     // We must start at the bottom of the tree, and do one level of
00519     // the tree at a time, to ensure the dependencies are accounted
00520     // for properly.
00521     for (int level = 0; level <= cd.Level; level++) {
00522               StaticCullAux(cd, ThresholdDetail, level);
00523     }
00524 }
00525 
00526 
00527 void   quadsquare::StaticCullAux(const quadcornerdata& cd, const float ThresholdDetail, const int TargetLevel)
00530 {
00531     int       i;
00532     quadcornerdata   q;
00533 
00534     if (cd.Level > TargetLevel) {
00535               // Just recurse to child nodes.
00536               for (int j = 0; j < 4; j++) {
00537                      if (j < 2) i = 1 - j;
00538                      else i = j;
00539 
00540                      if (Child[i]) {
00541                             SetupCornerData(&q, cd, i);
00542                             Child[i]->StaticCullAux(q, ThresholdDetail, TargetLevel);
00543                      }
00544               }
00545               return;
00546     }
00547 
00548     // We're at the target level.  Check this node to see if it's OK to delete it.
00549 
00550     // Check edge vertices to see if they're necessary.
00551     float size = 2 << cd.Level;    // Edge length.
00552     if (Child[0] == NULL && Child[3] == NULL && Error[0] * ThresholdDetail < size) {
00553               quadsquare*   s = GetNeighbor(0, cd);
00554               if (s == NULL || (s->Child[1] == NULL && s->Child[2] == NULL)){
00555 
00556                      // Force vertex height to the edge value.
00557                      float  y = (cd.Verts[0] + cd.Verts[3]) * 0.5;
00558                      Vertex[1] = y;
00559                      Error[0] = 0;
00560                      
00561                      // Force alias vertex to match.
00562                      if (s) s->Vertex[3] = y;
00563                      
00564                      Dirty = true;
00565               }
00566     }
00567 
00568     if (Child[2] == NULL && Child[3] == NULL && Error[1] * ThresholdDetail < size) {
00569        quadsquare*   s = GetNeighbor(3, cd);
00570        if (s == NULL || (s->Child[0] == NULL && s->Child[1] == NULL)) {
00571            float     y = (cd.Verts[2] + cd.Verts[3]) * 0.5;
00572            Vertex[4] = y;
00573            Error[1] = 0;
00574                      
00575            if (s) s->Vertex[2] = y;
00576                      
00577            Dirty = true;
00578        }
00579     }
00580 
00581     // See if we have child nodes.
00582     bool      StaticChildren = false;
00583     for (i = 0; i < 4; i++) {
00584        if (Child[i]) {
00585            StaticChildren = true;
00586            if (Child[i]->Dirty) Dirty = true;
00587        }
00588     }
00589 
00590     // If we have no children and no necessary edges, then see if we can delete ourself.
00591     if (StaticChildren == false && cd.Parent != NULL) {
00592        bool   NecessaryEdges = false;
00593        for (i = 0; i < 4; i++) {
00594            // See if vertex deviates from edge between corners.
00595            float     diff = fabs(Vertex[i+1] - (cd.Verts[i] + cd.Verts[(i+3)&3]) * 0.5);
00596            if (diff > 0.00001) {
00597               NecessaryEdges = true;
00598            }
00599        }
00600 
00601        if (!NecessaryEdges) {
00602            size *= 1.414213562;    // sqrt(2), because diagonal is longer than side.
00603            if (cd.Parent->Square->Error[2 + cd.ChildIndex] * ThresholdDetail < size) {
00604               delete cd.Parent->Square->Child[cd.ChildIndex];  // Delete this.
00605               cd.Parent->Square->Child[cd.ChildIndex] = 0;     // Clear the pointer.
00606            }
00607        }
00608     }
00609 }
00610 
00611 
00612 int    MaxCreateDepth = 0;
00613 
00614 
00615 void
00616 quadsquare::EnableEdgeVertex(int index, const bool IncrementCount, const quadcornerdata& cd)
00619 {
00620     if ((EnabledFlags & (1 << index)) && IncrementCount == false) return;
00621        
00622     // Turn on flag and deal with reference count.
00623     EnabledFlags |= 1 << index;
00624     if (IncrementCount == true && (index == 0 || index == 3)) {
00625               SubEnabledCount[index & 1]++;
00626     }
00627 
00628     // Now we need to enable the opposite edge vertex of the adjacent square (i.e. the alias vertex).
00629 
00630     // This is a little tricky, since the desired neighbor node may not exist, in which
00631     // case we have to create it, in order to prevent cracks.  Creating it may in turn cause
00632     // further edge vertices to be enabled, propagating updates through the tree.
00633 
00634     // The sticking point is the quadcornerdata list, which
00635     // conceptually is just a linked list of activation structures.
00636     // In this function, however, we will introduce branching into
00637     // the "list", making it in actuality a tree.  This is all kind
00638     // of obscure and hard to explain in words, but basically what
00639     // it means is that our implementation has to be properly
00640     // recursive.
00641 
00642     // Travel upwards through the tree, looking for the parent in common with our desired neighbor.
00643     // Remember the path through the tree, so we can travel down the complementary path to get to the neighbor.
00644     quadsquare*      p = this;
00645     const quadcornerdata* pcd = &cd;
00646     int       ct = 0;
00647     int       stack[32];
00648     for (;;) {
00649               int    ci = pcd->ChildIndex;
00650 
00651               if (pcd->Parent == NULL || pcd->Parent->Square == NULL) {
00652                   // Neighbor doesn't exist (it's outside the tree), so there's no alias vertex to enable.
00653                   return;
00654               }
00655               p = pcd->Parent->Square;
00656               pcd = pcd->Parent;
00657 
00658               bool SameParent = ((index - ci) & 2) ? true : false;
00659               
00660               ci = ci ^ 1 ^ ((index & 1) << 1);  // Child index of neighbor node.
00661 
00662               stack[ct] = ci;
00663               ct++;
00664               
00665               if (SameParent) break;
00666     }
00667 
00668     // Get a pointer to our neighbor (create if necessary), by walking down
00669     // the quadtree from our shared ancestor.
00670     p = p->EnableDescendant(ct, stack, *pcd);
00671        
00672 /*
00673   // Travel down the tree towards our neighbor, enabling and creating nodes as necessary.  We'll
00674   // follow the complement of the path we used on the way up the tree.
00675   quadcornerdata     d[16];
00676   int  i;
00677   for (i = 0; i < ct; i++) {
00678   int  ci = stack[ct-i-1];
00679 
00680   if (p->Child[ci] == NULL && CreateDepth == 0) CreateDepth = ct-i;   //xxxxxxx
00681               
00682   if ((p->EnabledFlags & (16 << ci)) == 0) {
00683   p->EnableChild(ci, *pcd);
00684   }
00685   p->SetupCornerData(&d[i], *pcd, ci);
00686   p = p->Child[ci];
00687   pcd = &d[i];
00688   }
00689 */
00690 
00691     // Finally: enable the vertex on the opposite edge of our neighbor, the alias of the original vertex.
00692     index ^= 2;
00693     p->EnabledFlags |= (1 << index);
00694     if (IncrementCount == true && (index == 0 || index == 3)) {
00695               p->SubEnabledCount[index & 1]++;
00696     }
00697 }
00698 
00699 
00700 quadsquare*   quadsquare::EnableDescendant(int count, int path[], const quadcornerdata& cd)
00704 {
00705     count--;
00706     int       ChildIndex = path[count];
00707 
00708     if ((EnabledFlags & (16 << ChildIndex)) == 0) {
00709               EnableChild(ChildIndex, cd);
00710     }
00711        
00712     if (count > 0) {
00713               quadcornerdata q;
00714               SetupCornerData(&q, cd, ChildIndex);
00715               return Child[ChildIndex]->EnableDescendant(count, path, q);
00716     } else {
00717               return Child[ChildIndex];
00718     }
00719 }
00720 
00721 
00722 void
00723 quadsquare::CreateChild(int index, const quadcornerdata& cd)
00725 {
00726     if (Child[index] == 0) {
00727               quadcornerdata       q;
00728               SetupCornerData(&q, cd, index);
00729               Child[index] = new quadsquare(&q);
00730     }
00731 }
00732 
00733 
00734 void
00735 quadsquare::EnableChild(int index, const quadcornerdata& cd)
00738 {
00739     if ((EnabledFlags & (16 << index)) == 0) {
00740               EnabledFlags |= (16 << index);
00741               EnableEdgeVertex(index, true, cd);
00742               EnableEdgeVertex((index + 1) & 3, true, cd);
00743               if (Child[index] == 0) {
00744                   CreateChild(index, cd);
00745               }
00746     }
00747 }
00748 
00749 
00750 int    BlockDeleteCount = 0;       //xxxxx
00751 int    BlockUpdateCount = 0;       //xxxxx
00752 
00753 
00754 void
00755 quadsquare::NotifyChildDisable(const quadcornerdata& cd, int index)
00758 {
00759     // Clear enabled flag for the child.
00760     EnabledFlags &= ~(16 << index);
00761        
00762        // Update child enabled counts for the affected edge verts.
00763     quadsquare*      s;
00764        
00765     if (index & 2) s = this;
00766     else s = GetNeighbor(1, cd);
00767     if (s) {
00768               s->SubEnabledCount[1]--;
00769     }
00770        
00771     if (index == 1 || index == 2) s = GetNeighbor(2, cd);
00772     else s = this;
00773     if (s) {
00774               s->SubEnabledCount[0]--;
00775     }
00776        
00777     /* We don't really want to delete nodes when they're disabled, do we?     
00778        if (Child[index]->Static == false) {
00779        delete Child[index];
00780        Child[index] = 0;
00781 
00782        BlockDeleteCount++;//xxxxx
00783        }
00784      */
00785 }
00786 
00787 
00788 static float DetailThreshold = 100;
00789 
00790 
00791 bool
00792 quadsquare::VertexTest(int x, float y, int z, float error, const float Viewer[3], int level, vertex_loc_t vertex_loc )
00796 {
00797     float     dx = fabs(x - Viewer[0]) * fabs( ScaleX );
00798     float     dy = fabs(y - Viewer[1]);
00799     float     dz = fabs(z - Viewer[2]) * fabs( ScaleZ );
00800     float     d = MAX( dx, MAX( dy, dz ) );
00801 
00802 
00803     if ( vertex_loc == South && ForceSouthVert && d < VERTEX_FORCE_THRESHOLD ) 
00804     {
00805               return true;
00806     }
00807     if ( vertex_loc == East && ForceEastVert && d < VERTEX_FORCE_THRESHOLD ) 
00808     {
00809               return true;
00810     }
00811     if ( d < ERROR_MAGNIFICATION_THRESHOLD ) {
00812               error *= ERROR_MAGNIFICATION_AMOUNT;
00813     }
00814 
00815     return error * DetailThreshold  > d;
00816 }
00817 
00818 
00819 bool
00820 quadsquare::BoxTest(int x, int z, float size, float miny, float maxy, float error, const float Viewer[3])
00824 {
00825     // Find the minimum distance to the box.
00826     float     half = size * 0.5;
00827     float     dx = ( fabs(x + half - Viewer[0]) - half ) * fabs(ScaleX);
00828     float     dy = fabs((miny + maxy) * 0.5 - Viewer[1]) - (maxy - miny) * 0.5;
00829     float     dz = ( fabs(z + half - Viewer[2]) - half ) * fabs(ScaleZ);
00830     float     d = MAX( dx, MAX( dy , dz ) );
00831 
00832     if ( d < ERROR_MAGNIFICATION_THRESHOLD ) {
00833               error *= ERROR_MAGNIFICATION_AMOUNT;
00834     }
00835 
00836     if ( error * DetailThreshold > d ) {
00837               return true;
00838     }
00839 
00840     // Check to see if this box crosses the heightmap boundary
00841     if ( ( x < RowSize-1 && x+size >= RowSize ) ||
00842         ( z < NumRows-1 && z+size >= NumRows ) ) 
00843     {
00844               return true;
00845     }
00846 
00847     return false;
00848 }
00849 
00850 void
00851 quadsquare::Update(const quadcornerdata& cd, const float ViewerLocation[3], const float Detail)
00855 {
00856 
00857     float Viewer[3];
00858 
00859     DetailThreshold = Detail;
00860 
00861     Viewer[0] = ViewerLocation[0] / ScaleX;
00862     Viewer[1] = ViewerLocation[1];
00863     Viewer[2] = ViewerLocation[2] / ScaleZ;
00864        
00865     UpdateAux(cd, Viewer, 0, SomeClip);
00866 }
00867 
00868 
00869 void
00870 quadsquare::UpdateAux(const quadcornerdata& cd, const float ViewerLocation[3], const float CenterError, clip_result_t vis )
00872 {
00873     BlockUpdateCount++;     //xxxxx
00874 
00875     check_assertion( vis != NotVisible, "Invalid visibility value" );
00876     if ( vis != NoClip ) {
00877               vis = ClipSquare( cd );
00878               if ( vis == NotVisible ) {
00879               return;
00880               }
00881     }
00882        
00883     // Make sure error values are current.
00884     if (Dirty) {
00885               RecomputeError(cd);
00886     }
00887 
00888     const int half = 1 << cd.Level;
00889     const int whole = half << 1;
00890 
00891     // See about enabling child verts.
00892 
00893     // East vert.
00894     if ( (EnabledFlags & 1) == 0 && 
00895         VertexTest(cd.xorg + whole, Vertex[1], cd.zorg + half, 
00896                   Error[0], ViewerLocation, cd.Level, East) == true ) 
00897     {
00898               EnableEdgeVertex(0, false, cd);    
00899     }
00900 
00901     // South vert.
00902     if ( (EnabledFlags & 8) == 0 && 
00903         VertexTest(cd.xorg + half, Vertex[4], cd.zorg + whole, 
00904                   Error[1], ViewerLocation, cd.Level, South) == true ) 
00905     {
00906               EnableEdgeVertex(3, false, cd);    
00907     }
00908 
00909     if (cd.Level > 0) {
00910        if ((EnabledFlags & 32) == 0) {
00911            if (BoxTest(cd.xorg, cd.zorg, half, MinY, MaxY, Error[3], ViewerLocation) == true) EnableChild(1, cd);      // nw child.er
00912        }
00913        if ((EnabledFlags & 16) == 0) {
00914            if (BoxTest(cd.xorg + half, cd.zorg, half, MinY, MaxY, Error[2], ViewerLocation) == true) EnableChild(0, cd);      // ne child.
00915        }
00916        if ((EnabledFlags & 64) == 0) {
00917            if (BoxTest(cd.xorg, cd.zorg + half, half, MinY, MaxY, Error[4], ViewerLocation) == true) EnableChild(2, cd);      // sw child.
00918        }
00919        if ((EnabledFlags & 128) == 0) {
00920            if (BoxTest(cd.xorg + half, cd.zorg + half, half, MinY, MaxY, Error[5], ViewerLocation) == true) EnableChild(3, cd);      // se child.
00921        }
00922               
00923        // Recurse into child quadrants as necessary.
00924        quadcornerdata       q;
00925               
00926        if (EnabledFlags & 32) {
00927            SetupCornerData(&q, cd, 1);
00928            Child[1]->UpdateAux(q, ViewerLocation, Error[3], vis);
00929        }
00930        if (EnabledFlags & 16) {
00931            SetupCornerData(&q, cd, 0);
00932            Child[0]->UpdateAux(q, ViewerLocation, Error[2], vis);
00933        }
00934        if (EnabledFlags & 64) {
00935            SetupCornerData(&q, cd, 2);
00936            Child[2]->UpdateAux(q, ViewerLocation, Error[4], vis);
00937        }
00938        if (EnabledFlags & 128) {
00939            SetupCornerData(&q, cd, 3);
00940            Child[3]->UpdateAux(q, ViewerLocation, Error[5], vis);
00941        }
00942     }
00943        
00944     // Test for disabling.  East, South, and center.
00945     if ( (EnabledFlags & 1) && 
00946         SubEnabledCount[0] == 0 && 
00947         VertexTest(cd.xorg + whole, Vertex[1], cd.zorg + half, 
00948                   Error[0], ViewerLocation, cd.Level, East) == false) 
00949     {
00950               EnabledFlags &= ~1;
00951               quadsquare*   s = GetNeighbor(0, cd);
00952               if (s) s->EnabledFlags &= ~4;
00953     }
00954 
00955     if ( (EnabledFlags & 8) && 
00956         SubEnabledCount[1] == 0 && 
00957         VertexTest(cd.xorg + half, Vertex[4], cd.zorg + whole, 
00958                   Error[1], ViewerLocation, cd.Level, South) == false) 
00959     {
00960               EnabledFlags &= ~8;
00961               quadsquare*   s = GetNeighbor(3, cd);
00962               if (s) s->EnabledFlags &= ~2;
00963     }
00964 
00965     if (EnabledFlags == 0 &&
00966        cd.Parent != NULL &&
00967        BoxTest(cd.xorg, cd.zorg, whole, MinY, MaxY, CenterError, 
00968               ViewerLocation) == false)
00969     {
00970        // Disable ourself.
00971               cd.Parent->Square->NotifyChildDisable(*cd.Parent, cd.ChildIndex);     // nb: possibly deletes 'this'.
00972     }
00973 }
00974 
00975 GLuint VertexIndices[9];
00976 int VertexTerrains[9];
00977 
00978 //void
00979 inline int
00980 quadsquare::InitVert(const int i, const int x,const int z)
00983 {
00984     const int idx = (x >= RowSize ? (RowSize - 1) : x) + RowSize * (  z >= NumRows ? (NumRows - 1)  : z);
00985 
00986     VertexIndices[i] = idx;
00987 
00988        return (VertexTerrains[i] = Terrain[idx]);
00989 }
00990 
00991 GLubyte *VNCArray;
00992 
00993 void
00994 quadsquare::DrawTris(int terrain)
00995 {
00996     int tmp_min_idx = VertexArrayMinIdx[terrain];
00997     if ( glLockArraysEXT_p && getparam_use_cva()) {
00998 
00999        if ( getparam_cva_hack() ) {
01000            /* This is a hack that seems to fix the "psychedelic colors" on 
01001               some drivers (TNT/TNT2, for example)
01002             */
01003            if ( tmp_min_idx == 0 ) {
01004               tmp_min_idx = 1;
01005            }
01006        } 
01007        
01008        glLockArraysEXT_p( tmp_min_idx, 
01009                       VertexArrayMaxIdx[terrain] - tmp_min_idx + 1 ); 
01010     }
01011 
01012     glDrawElements( GL_TRIANGLES, VertexArrayCounter[terrain],
01013                   GL_UNSIGNED_INT, VertexArrayIndices[terrain] );
01014 
01015     if ( glUnlockArraysEXT_p && getparam_use_cva()) {
01016               glUnlockArraysEXT_p();
01017     }
01018 }
01019 
01020 void
01021 quadsquare::DrawEnvmapTris(GLuint MapTexId, int terrain) 
01022 {
01023     if ( VertexArrayCounter[terrain] > 0 ) {
01024        
01025               glTexGeni( GL_S, GL_TEXTURE_GEN_MODE, GL_SPHERE_MAP );
01026               glTexGeni( GL_T, GL_TEXTURE_GEN_MODE, GL_SPHERE_MAP );
01027 
01028               glBindTexture( GL_TEXTURE_2D, MapTexId);
01029 
01030               DrawTris(terrain);
01031 
01032               glTexGeni( GL_S, GL_TEXTURE_GEN_MODE, GL_OBJECT_LINEAR );
01033               glTexGeni( GL_T, GL_TEXTURE_GEN_MODE, GL_OBJECT_LINEAR );
01034        } 
01035 }
01036 
01037 void
01038 quadsquare::InitArrayCounters()
01039 {
01040     for (unsigned int i=0; i<num_terrains ; i++){
01041               VertexArrayCounter[i] = 0;
01042               VertexArrayMinIdx[i] = INT_MAX;
01043               VertexArrayMaxIdx[i] = 0;
01044        }
01045 }
01046 
01047 void
01048 quadsquare::Render(const quadcornerdata& cd, GLubyte *vnc_array)
01050 {
01051     VNCArray = vnc_array;
01052     const bool fog_on=fogPlane.isEnabled();
01053     int i,idx;
01054     int nx, ny;
01055     get_course_divisions( &nx, &ny );
01056 
01057     /*
01058      * Draw the "normal" blended triangles
01059      */
01060 
01061        InitArrayCounters();
01062        RenderAux(cd, SomeClip);
01063 
01064        
01065        //for (j=0; j<(int)num_terrains; j++) {
01066        
01067        std::list<int>::iterator it;
01068        for (it=usedTerrains.begin(); it!=usedTerrains.end(); it++) {
01069               
01070               if ( VertexArrayCounter[(*it)] == 0 ) {
01071                      continue;
01072               } 
01073 
01074               for (i=0; i<(int)VertexArrayCounter[(*it)];i++){
01075                      idx = VertexArrayIndices[(*it)][i];
01076                      //colorval(idx, 3) =  ( (*it)<= Terrain[idx] ) ? 255 : 0;
01077                      colorval(idx, 3) =  ( terrain_texture[(*it)].wheight<= terrain_texture[Terrain[idx]].wheight ) ? 255 : 0;
01078               }
01079 
01080               glBindTexture( GL_TEXTURE_2D, terrain_texture[(*it)].texbind );
01081               DrawTris((*it));
01082 
01083               if ( terrain_texture[(*it)].envmapbind != 0  && getparam_terrain_envmap() ) {
01084                   /* Render Ice with environment map */
01085                   glDisableClientState( GL_COLOR_ARRAY );
01086                   glColor4f( 1.0, 1.0, 1.0, ENV_MAP_ALPHA / 255.0 );
01087 
01088                   DrawEnvmapTris(terrain_texture[(*it)].envmapbind, (*it));  
01089 
01090                   glEnableClientState( GL_COLOR_ARRAY );
01091               }
01092 
01093     }
01094 
01095     /*
01096      * Draw the "special" triangles that have different terrain types
01097      * at each of the corners 
01098      */
01099     if ( getparam_terrain_blending() &&
01100         getparam_perfect_terrain_blending()) {
01101 
01102        /*
01103         * Get the "special" three-terrain triangles
01104         */
01105        InitArrayCounters();
01106        RenderAuxSpezial( cd, SomeClip);
01107        
01108        if ( VertexArrayCounter[0] != 0 ) {
01109            /* Render black triangles */
01110            glDisable( GL_FOG );
01111            
01112            /* Set triangle vertices to black */
01113            for (i=0; i<(int)VertexArrayCounter[0]; i++) {
01114                      colorval( VertexArrayIndices[0][i], 0 ) = 0;
01115                      colorval( VertexArrayIndices[0][i], 1 ) = 0;
01116                      colorval( VertexArrayIndices[0][i], 2 ) = 0;
01117                      colorval( VertexArrayIndices[0][i], 3 ) = 255;
01118            }
01119            
01120            /* Draw the black triangles */
01121            glBindTexture( GL_TEXTURE_2D, terrain_texture[0].texbind);
01122            DrawTris(0);
01123            
01124            /* Now we draw the triangle once for each texture */
01125            if (fog_on) {
01126                      glEnable( GL_FOG );
01127            }
01128 
01129            /* Use additive blend function */
01130            glBlendFunc( GL_SRC_ALPHA, GL_ONE );
01131 
01132            /* First set triangle colors to white */
01133            for (i=0; i<(int)VertexArrayCounter[0]; i++) {
01134                      colorval( VertexArrayIndices[0][i], 0 ) = 255;
01135                      colorval( VertexArrayIndices[0][i], 1 ) = 255;
01136                      colorval( VertexArrayIndices[0][i], 2 ) = 255;
01137            }
01138 
01139               //for (int j=0; j<(int)num_terrains; j++) {
01140               for(it=usedTerrains.begin(); it != usedTerrains.end(); it++){
01141                      
01142                      glBindTexture( GL_TEXTURE_2D, terrain_texture[(*it)].texbind);
01143 
01144                      /* Set alpha values */
01145                      for (i=0; i<(int)VertexArrayCounter[0]; i++) {
01146                             colorval( VertexArrayIndices[0][i], 3 ) = 
01147                             (Terrain[VertexArrayIndices[0][i]] == int(*it) ) ? 
01148                             255 : 0;
01149                      }
01150 
01151                      DrawTris(0);
01152            }
01153 
01154 
01155            /* Render Ice with environment map */
01156            if ( getparam_terrain_envmap() ) {
01157               glBlendFunc( GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA );
01158            
01159               /* Need to set alpha values for ice */
01160                      
01161               /*
01162               for (i=0; i<VertexArrayCounter; i++) {
01163                   colorval( VertexArrayIndices[i], 3 ) = 
01164                      (Terrain[VertexArrayIndices[i]] == Ice) ? 
01165                      ENV_MAP_ALPHA : 0;
01166               }
01167               */
01168                      
01169               //the ice stuff should be rewritten...
01170               for (i=0; i<(int)VertexArrayCounter[0]; i++) {
01171                   colorval( VertexArrayIndices[0][i], 3 ) = 
01172                      (Terrain[VertexArrayIndices[0][i]] == 0) ? 
01173                      ENV_MAP_ALPHA : 0;
01174               }                    
01175                      
01176               DrawEnvmapTris(getparam_terrain_envmap(),0);
01177            }
01178        }
01179     }
01180 
01181     glBlendFunc( GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA );
01182 }
01183 
01184 clip_result_t
01185 quadsquare::ClipSquare( const quadcornerdata& cd )
01186 {
01187     if ( cd.xorg >= RowSize-1 ) {
01188               return NotVisible;
01189     } 
01190 
01191     if ( cd.zorg >= NumRows-1 ) {
01192               return NotVisible;
01193     }
01194        
01195     const int whole = 2 << cd.Level;
01196        
01197        pp::Vec3d Min(cd.xorg*ScaleX, MinY, cd.zorg*ScaleZ);
01198     pp::Vec3d Max((cd.xorg + whole) * ScaleX, MaxY,(cd.zorg + whole) * ScaleZ);
01199 
01200     /* If the scales are negative we'll need to swap */
01201     if ( Min.x > Max.x ) {
01202               float tmp = Min.x;
01203               Min.x = Max.x;
01204               Max.x = tmp;
01205     }
01206 
01207     if ( Min.z > Max.z ) {
01208               float tmp = Min.z;
01209               Min.z = Max.z;
01210               Max.z = tmp;
01211     }
01212 
01213     const clip_result_t clip_result = clip_aabb_to_view_frustum(Min, Max);
01214 
01215     if ( clip_result == NotVisible || clip_result == SomeClip ) {
01216               return clip_result;
01217     }
01218 
01219     if ( cd.xorg + whole >= RowSize ) {
01220               return SomeClip;
01221     }
01222     if ( cd.zorg + whole >= NumRows ) {
01223               return SomeClip;
01224     }
01225 
01226     return clip_result;
01227 }
01228 
01229 
01230 typedef void (*make_tri_func_t)( int a, int b, int c, int terrain );
01231 
01232 /* Local macro for setting alpha value based on terrain */
01233 #define setalphaval(i) colorval(VertexIndices[i], 3) = \
01234     ( terrain <= VertexTerrains[i] ) ? 255 : 0 
01235 
01236 #define update_min_max( idx,terrain ) \
01237     if ( idx > VertexArrayMaxIdx[terrain] ) { \
01238         VertexArrayMaxIdx[terrain] = idx; \
01239     } \
01240     if ( idx < VertexArrayMinIdx[terrain] ) { \
01241         VertexArrayMinIdx[terrain] = idx; \
01242     }
01243        
01244 inline void quadsquare::MakeTri( int a, int b, int c, int terrain )
01245 {
01246     if ( ( VertexTerrains[a] == terrain || 
01247           VertexTerrains[b] == terrain || 
01248           VertexTerrains[c] == terrain ) )
01249     { 
01250        VertexArrayIndices[terrain][VertexArrayCounter[terrain]++] = VertexIndices[a]; 
01251        //setalphaval(a); 
01252        update_min_max( VertexIndices[a], terrain );
01253        VertexArrayIndices[terrain][VertexArrayCounter[terrain]++] = VertexIndices[b]; 
01254        //setalphaval(b); 
01255        update_min_max( VertexIndices[b], terrain );
01256        VertexArrayIndices[terrain][VertexArrayCounter[terrain]++] = VertexIndices[c]; 
01257        //setalphaval(c); 
01258        update_min_max( VertexIndices[c], terrain );
01259     }
01260 }
01261 
01262 
01263 inline void quadsquare::MakeSpecialTri( int a, int b, int c) 
01264 {
01265     if ( VertexTerrains[a] != VertexTerrains[b] && 
01266         VertexTerrains[a] != VertexTerrains[c] && 
01267         VertexTerrains[b] != VertexTerrains[c] ) 
01268     { 
01269        VertexArrayIndices[0][VertexArrayCounter[0]++] = VertexIndices[a]; 
01270        update_min_max( VertexIndices[a],0 );
01271        VertexArrayIndices[0][VertexArrayCounter[0]++] = VertexIndices[b]; 
01272        update_min_max( VertexIndices[b],0 );
01273        VertexArrayIndices[0][VertexArrayCounter[0]++] = VertexIndices[c]; 
01274        update_min_max( VertexIndices[c],0 );
01275     }
01276 }
01277 
01278 inline void quadsquare::MakeNoBlendTri( int a, int b, int c, int terrain )
01279 {
01280     if ( ( VertexTerrains[a] == terrain || 
01281           VertexTerrains[b] == terrain || 
01282           VertexTerrains[c] == terrain ) &&
01283         ( VertexTerrains[a] >= terrain &&
01284           VertexTerrains[b] >= terrain &&
01285           VertexTerrains[c] >= terrain ) )
01286     { 
01287        VertexArrayIndices[terrain][VertexArrayCounter[terrain]++] = VertexIndices[a]; 
01288        setalphaval(a); 
01289        update_min_max( VertexIndices[a],terrain );
01290        VertexArrayIndices[terrain][VertexArrayCounter[terrain]++] = VertexIndices[b]; 
01291        setalphaval(b);
01292        update_min_max( VertexIndices[b],terrain );
01293        VertexArrayIndices[terrain][VertexArrayCounter[terrain]++] = VertexIndices[c];
01294        setalphaval(c);
01295        update_min_max( VertexIndices[c],terrain );
01296     }
01297 }
01298 
01299 
01300 static bool terraintest[NUM_TERRAIN_TYPES];
01301 
01302 void
01303 quadsquare::RenderAux(const quadcornerdata& cd, clip_result_t vis)
01306 {
01307     int       flags = 0;
01308     int       mask = 1;
01309     quadcornerdata q;
01310        
01311     for (int i = 0; i < 4; i++, mask <<= 1) {
01312               if (EnabledFlags & (16 << i)) {
01313                      SetupCornerData(&q, cd, i);
01314                      if (vis != NoClip) {
01315                             if ((vis = ClipSquare( q ))!= NotVisible ) {
01316                                Child[i]->RenderAux(q, vis);
01317                             }
01318                      }else{        
01319                             Child[i]->RenderAux(q, vis);
01320                      }
01321               } else {
01322                   flags |= mask;
01323               }
01324     }
01325     if (flags == 0) return;
01326 
01327        
01328     // Init vertex data.  Here's a diagram of what's going on.
01329     // Yes, this diagram is fucked, but that's because things are mirrored 
01330     // in the z axis for us (z coords are actually -z coords).
01331     //
01332     // (top of course) 
01333     //        N                
01334     //    +---+---+ (xorg, zorg)
01335     //   2|  3   4|        
01336     //    |(1) (2)|
01337     // E  +   +   +  W
01338     //   1|  0   5|
01339     //    |(8) (4)|
01340     //    +---+---+
01341     //   8   7   6
01342     //        S
01343     // (bottom of course)
01344     //
01345     // Values in parens are bitmask values for the corresponding child squares
01346     //
01347 
01348            // Make the list of triangles to draw.
01349 #define make_tri_list(tri_func,terrain) \
01350     if ((EnabledFlags & 1) == 0 ) { \
01351        tri_func(0, 2, 8, terrain); \
01352     } else { \
01353        if (flags & 8) tri_func(0, 1, 8, terrain); \
01354        if (flags & 1) tri_func(0, 2, 1, terrain); \
01355     } \
01356     if ((EnabledFlags & 2) == 0 ) {  \
01357        tri_func(0, 4, 2, terrain);  \
01358     } else { \
01359        if (flags & 1) tri_func(0, 3, 2, terrain); \
01360        if (flags & 2) tri_func(0, 4, 3, terrain); \
01361     } \
01362     if ((EnabledFlags & 4) == 0 ) { \
01363        tri_func(0, 6, 4, terrain); \
01364     } else { \
01365        if (flags & 2) tri_func(0, 5, 4, terrain); \
01366        if (flags & 4) tri_func(0, 6, 5, terrain); \
01367     } \
01368     if ((EnabledFlags & 8) == 0 ) { \
01369        tri_func(0, 8, 6, terrain); \
01370     } else { \
01371        if (flags & 4) tri_func(0, 7, 6, terrain); \
01372        if (flags & 8) tri_func(0, 8, 7, terrain); \
01373     }
01374 
01375        
01376        {
01377               //bool terraintest[num_terrains];
01378               for (unsigned int i=0; i<num_terrains; i++) terraintest[i]=false;
01379               
01380               const int     half = 1 << cd.Level;
01381        const int     whole = 2 << cd.Level;
01382 
01383        terraintest[ InitVert(0, cd.xorg + half, cd.zorg + half) ] = true;
01384        terraintest[ InitVert(1, cd.xorg + whole, cd.zorg + half) ] = true;
01385        terraintest[ InitVert(2, cd.xorg + whole, cd.zorg) ] = true;
01386        terraintest[ InitVert(3, cd.xorg + half, cd.zorg) ] = true;
01387        terraintest[ InitVert(4, cd.xorg, cd.zorg) ] = true;
01388        terraintest[ InitVert(5, cd.xorg, cd.zorg + half) ] = true;
01389               terraintest[ InitVert(6, cd.xorg, cd.zorg + whole) ] = true;
01390            terraintest[ InitVert(7, cd.xorg + half, cd.zorg + whole) ] = true;
01391            terraintest[ InitVert(8, cd.xorg + whole, cd.zorg + whole) ] = true;
01392        
01393               for (unsigned int j=0; j<num_terrains; j++) {
01394                       if (terraintest[j]==true){                
01395                             if ( getparam_terrain_blending() ){make_tri_list(MakeTri,j);}
01396                             else{make_tri_list(MakeNoBlendTri,j);}
01397                       }
01398               } 
01399        }
01400 }
01401 
01402 
01403 void
01404 quadsquare::RenderAuxSpezial(const quadcornerdata& cd, clip_result_t vis)
01407 {
01408     /*
01409        // If this square is outside the frustum, then don't render it.
01410   
01411        //if (vis != NoClip) {
01412 
01413               if ((vis = ClipSquare( cd ))== NotVisible ) {
01414            // This square is completely outside the view frustum.
01415                   return;
01416               }
01417        // else vis is either NoClip or SomeClip.  If it's NoClip, then child
01418        // squares won't have to bother with the frustum check.
01419     }
01420        */
01421        
01422     int       flags = 0;
01423     int       mask = 1;
01424     quadcornerdata q;
01425        
01426     for (int i = 0; i < 4; i++, mask <<= 1) {
01427               if (EnabledFlags & (16 << i)) {
01428                      SetupCornerData(&q, cd, i);
01429                      if (vis != NoClip) {
01430                             if ((vis = ClipSquare( q ))!= NotVisible ) {
01431                                Child[i]->RenderAuxSpezial(q, vis);
01432                             }
01433                      }else{        
01434                             Child[i]->RenderAuxSpezial(q, vis);
01435                      }
01436               } else {
01437                   flags |= mask;
01438               }
01439     }
01440     if (flags == 0) return;
01441 
01442        
01443     // Init vertex data.  Here's a diagram of what's going on.
01444     // Yes, this diagram is fucked, but that's because things are mirrored 
01445     // in the z axis for us (z coords are actually -z coords).
01446     //
01447     // (top of course) 
01448     //        N                
01449     //    +---+---+ (xorg, zorg)
01450     //   2|  3   4|        
01451     //    |(1) (2)|
01452     // E  +   +   +  W
01453     //   1|  0   5|
01454     //    |(8) (4)|
01455     //    +---+---+
01456     //   8   7   6
01457     //        S
01458     // (bottom of course)
01459     //
01460     // Values in parens are bitmask values for the corresponding child squares
01461     //
01462 
01463        
01464 
01465        int terraintest=0;
01466        {
01467               const int     half = 1 << cd.Level;
01468        const int     whole = 2 << cd.Level;
01469 
01470        terraintest += InitVert(0, cd.xorg + half, cd.zorg + half);
01471        terraintest += InitVert(1, cd.xorg + whole, cd.zorg + half);
01472        terraintest += InitVert(2, cd.xorg + whole, cd.zorg);
01473        terraintest += InitVert(3, cd.xorg + half, cd.zorg);
01474        terraintest += InitVert(4, cd.xorg, cd.zorg);
01475        terraintest += InitVert(5, cd.xorg, cd.zorg + half);
01476               terraintest += InitVert(6, cd.xorg, cd.zorg + whole);
01477            terraintest += InitVert(7, cd.xorg + half, cd.zorg + whole);
01478            terraintest += InitVert(8, cd.xorg + whole, cd.zorg + whole);
01479        }
01480               
01481               
01482     // Make the list of triangles to draw.
01483 #define make_spezialtri_list(tri_func) \
01484     if ((EnabledFlags & 1) == 0 ) { \
01485        tri_func(0, 2, 8); \
01486     } else { \
01487        if (flags & 8) tri_func(0, 1, 8); \
01488        if (flags & 1) tri_func(0, 2, 1); \
01489     } \
01490     if ((EnabledFlags & 2) == 0 ) {  \
01491        tri_func(0, 4, 2);  \
01492     } else { \
01493        if (flags & 1) tri_func(0, 3, 2); \
01494        if (flags & 2) tri_func(0, 4, 3); \
01495     } \
01496     if ((EnabledFlags & 4) == 0 ) { \
01497        tri_func(0, 6, 4); \
01498     } else { \
01499        if (flags & 2) tri_func(0, 5, 4); \
01500        if (flags & 4) tri_func(0, 6, 5); \
01501     } \
01502     if ((EnabledFlags & 8) == 0 ) { \
01503        tri_func(0, 8, 6); \
01504     } else { \
01505        if (flags & 4) tri_func(0, 7, 6); \
01506        if (flags & 8) tri_func(0, 8, 7); \
01507     }
01508        
01509        //if (terraintest>0){
01510               make_spezialtri_list(MakeSpecialTri);     
01511        //}
01512 }
01513 
01514 
01515 
01516 void
01517 quadsquare::SetupCornerData(quadcornerdata* q, const quadcornerdata& cd, const int ChildIndex)
01521 //
01522 // ChildIndex mapping:
01523 // +-+-+
01524 // |1|0|
01525 // +-+-+
01526 // |2|3|
01527 // +-+-+
01528 //
01529 // Verts mapping:
01530 // 1-0
01531 // | |
01532 // 2-3
01533 //
01534 // Vertex mapping:
01535 // +-2-+
01536 // | | |
01537 // 3-0-1
01538 // | | |
01539 // +-4-+
01540 {
01541     const int half = 1 << cd.Level;
01542 
01543     q->Parent = &cd;
01544     q->Square = Child[ChildIndex];
01545     q->Level = cd.Level - 1;
01546     q->ChildIndex = ChildIndex;
01547        
01548     switch (ChildIndex) {
01549     default:
01550     case 0:
01551        q->xorg = cd.xorg + half;
01552        q->zorg = cd.zorg;
01553        q->Verts[0] = cd.Verts[0];
01554        q->Verts[1] = Vertex[2];
01555        q->Verts[2] = Vertex[0];
01556        q->Verts[3] = Vertex[1];
01557        break;
01558 
01559     case 1:
01560        q->xorg = cd.xorg;
01561        q->zorg = cd.zorg;
01562        q->Verts[0] = Vertex[2];
01563        q->Verts[1] = cd.Verts[1];
01564        q->Verts[2] = Vertex[3];
01565        q->Verts[3] = Vertex[0];
01566        break;
01567 
01568     case 2:
01569        q->xorg = cd.xorg;
01570        q->zorg = cd.zorg + half;
01571        q->Verts[0] = Vertex[0];
01572        q->Verts[1] = Vertex[3];
01573        q->Verts[2] = cd.Verts[2];
01574        q->Verts[3] = Vertex[4];
01575        break;
01576 
01577     case 3:
01578        q->xorg = cd.xorg + half;
01579        q->zorg = cd.zorg + half;
01580        q->Verts[0] = Vertex[1];
01581        q->Verts[1] = Vertex[0];
01582        q->Verts[2] = Vertex[4];
01583        q->Verts[3] = cd.Verts[3];
01584        break;
01585     }  
01586 }
01587 
01588 int quadsquare::RowSize;
01589 int quadsquare::NumRows;
01590 
01591 void
01592 quadsquare::AddHeightMap(const quadcornerdata& cd, const HeightMapInfo& hm)
01596 {
01597     RowSize = hm.RowWidth;
01598     NumRows = hm.ZSize;
01599 
01600     if ( cd.Parent == NULL ) {
01601               if ( VertexArrayIndices[0] != NULL ) {
01602                      for (int i=0; i< NUM_TERRAIN_TYPES; i++){
01603                             if (VertexArrayIndices[i]!=NULL)
01604                                           delete VertexArrayIndices[i];
01605                      }
01606               }
01607 
01608        /* Maximum number of triangles is 2 * RowSize * NumRows 
01609           This uses up a lot of space but it is a *big* performance gain.
01610        */
01611               for (unsigned int i=0; i<num_terrains; i++){     
01612                      VertexArrayIndices[i] = new GLuint[6 * RowSize * NumRows];
01613               }
01614     }
01615 
01616     // If block is outside rectangle, then don't bother.
01617     int       BlockSize = 2 << cd.Level;
01618     if (cd.xorg > hm.XOrigin + ((hm.XSize + 2) << hm.Scale) ||
01619        cd.xorg + BlockSize < hm.XOrigin - (1 << hm.Scale) ||
01620        cd.zorg > hm.ZOrigin + ((hm.ZSize + 2) << hm.Scale) ||
01621        cd.zorg + BlockSize < hm.ZOrigin - (1 << hm.Scale))
01622     {
01623        // This square does not touch the given height array area; no need to modify this square or descendants.
01624        return;
01625     }
01626 
01627     if (cd.Parent && cd.Parent->Square) {
01628        cd.Parent->Square->EnableChild(cd.ChildIndex, *cd.Parent);     // causes parent edge verts to be enabled, possibly causing neighbor blocks to be created.
01629     }
01630        
01631     int       i;
01632        
01633     int       half = 1 << cd.Level;
01634 
01635     // Create and update child nodes.
01636     for (i = 0; i < 4; i++) {
01637        quadcornerdata       q;
01638        SetupCornerData(&q, cd, i);
01639                             
01640        if (Child[i] == NULL && cd.Level > hm.Scale) {
01641            // Create child node w/ current (unmodified) values for corner verts.
01642            Child[i] = new quadsquare(&q);
01643        }
01644               
01645        // Recurse.
01646        if (Child[i]) {
01647            Child[i]->AddHeightMap(q, hm);
01648        }
01649     }
01650        
01651     // Deviate vertex heights based on data sampled from heightmap.
01652     float     s[5];
01653     s[0] = hm.Sample(cd.xorg + half, cd.zorg + half);
01654     s[1] = hm.Sample(cd.xorg + half*2, cd.zorg + half);
01655     s[2] = hm.Sample(cd.xorg + half, cd.zorg);
01656     s[3] = hm.Sample(cd.xorg, cd.zorg + half);
01657     s[4] = hm.Sample(cd.xorg + half, cd.zorg + half*2);
01658 
01659     // Modify the vertex heights if necessary, and set the dirty
01660     // flag if any modifications occur, so that we know we need to
01661     // recompute error data later.
01662     for (i = 0; i < 5; i++) {
01663               if (s[i] != 0) {
01664                   Dirty = true;
01665                   Vertex[i] += s[i];
01666               }
01667     }
01668 
01669     if (!Dirty) {
01670        // Check to see if any child nodes are dirty, and set the dirty flag if so.
01671        for (i = 0; i < 4; i++) {
01672            if (Child[i] && Child[i]->Dirty) {
01673               Dirty = true;
01674               break;
01675            }
01676        }
01677     }
01678 
01679     if (Dirty) SetStatic(cd);
01680 }
01681 
01682 float quadsquare::ScaleX;
01683 float quadsquare::ScaleZ;
01684 int* quadsquare::Terrain;