Panda3D

heightfieldTesselator.cxx

00001 // Filename: heightfieldTesselator.cxx
00002 // Created by:  jyelon (17jul06)
00003 //
00004 ////////////////////////////////////////////////////////////////////
00005 //
00006 // PANDA 3D SOFTWARE
00007 // Copyright (c) Carnegie Mellon University.  All rights reserved.
00008 //
00009 // All use of this software is subject to the terms of the revised BSD
00010 // license.  You should have received a copy of this license along
00011 // with this source code in a file named "LICENSE."
00012 //
00013 ////////////////////////////////////////////////////////////////////
00014 
00015 #include "heightfieldTesselator.h"
00016 #include "geomNode.h"
00017 #include "transformState.h"
00018 #include "sceneGraphReducer.h"
00019 #include "lvector3.h"
00020 
00021 ////////////////////////////////////////////////////////////////////
00022 //     Function: HeightfieldTesselator::fix_heightfield
00023 //       Access: Published
00024 //  Description: Makes sure that the heightfield is a grayscale
00025 //               image of valid dimensions.  If necessary, adds a
00026 //               band of zeros onto two sides of the heightfield,
00027 //               so as to make the size of the heightfield a multiple
00028 //               of the given size plus one.
00029 ////////////////////////////////////////////////////////////////////
00030 void HeightfieldTesselator::
00031 fix_heightfield(int size) {
00032   
00033   // Calculate the padded size of the heightfield.
00034   int xsize = _heightfield.get_x_size();
00035   int ysize = _heightfield.get_y_size();
00036   int xcells = (xsize + size - 2) / size;
00037   int ycells = (ysize + size - 2) / size;
00038   int xpadded = xcells * size + 1;
00039   int ypadded = ycells * size + 1;
00040 
00041   // If the heightfield is already in good shape, done.
00042   if ((xpadded == _heightfield.get_x_size()) &&
00043       (ypadded == _heightfield.get_y_size()) &&
00044       (_heightfield.is_grayscale())) {
00045     return;
00046   }
00047 
00048   // Pad the heightfield, and convert to grey.
00049   PNMImage unfixed(_heightfield);
00050   _heightfield.clear(xpadded, ypadded, 1,
00051                      unfixed.get_maxval(), 
00052                      unfixed.get_type());
00053   for (int y = 0; y < ysize; y++) {
00054     for (int x = 0; x < xsize; x++) {
00055       _heightfield.set_gray_val(x, y, unfixed.get_gray_val(x, y));
00056     }
00057   }
00058   for (int y = ysize; y < ypadded; y++) {
00059     for (int x = xsize; x < xpadded; x++) {
00060       _heightfield.set_gray_val(x, y, 0);
00061     }
00062   }
00063 }
00064 
00065 ////////////////////////////////////////////////////////////////////
00066 //     Function: HeightfieldTesselator::get_elevation
00067 //       Access: Private
00068 //  Description: Fetches the elevation at (x,y), where the input
00069 //               coordinate is specified in pixels.  This ignores the
00070 //               current tesselation level and instead provides an
00071 //               accurate number.  Linear blending is used for 
00072 //               non-integral coordinates.
00073 ////////////////////////////////////////////////////////////////////
00074 double HeightfieldTesselator::
00075 get_elevation(double x, double y) {
00076   int scale = 7;
00077   int size = 1 << scale;
00078   fix_heightfield(size);
00079   int xlo = (int)x;
00080   int ylo = (int)y;
00081   if (xlo < 0) xlo = 0;
00082   if (ylo < 0) ylo = 0;
00083   if (xlo > _heightfield.get_x_size()-2)
00084     xlo = _heightfield.get_x_size()-2;
00085   if (ylo > _heightfield.get_y_size()-2)
00086     ylo = _heightfield.get_y_size()-2;
00087   int xhi = xlo+1;
00088   int yhi = ylo+1;
00089   double xoffs = x - xlo;
00090   double yoffs = y - ylo;
00091   double grayxlyl = _heightfield.get_gray(xlo,ylo);
00092   double grayxhyl = _heightfield.get_gray(xhi,ylo);
00093   double grayxlyh = _heightfield.get_gray(xlo,yhi);
00094   double grayxhyh = _heightfield.get_gray(xhi,yhi);
00095   double lerpyl = grayxhyl * xoffs + grayxlyl * (1.0 - xoffs);
00096   double lerpyh = grayxhyh * xoffs + grayxlyh * (1.0 - xoffs);
00097   return lerpyh * yoffs + lerpyl * (1.0 - yoffs);
00098 }
00099 
00100 ////////////////////////////////////////////////////////////////////
00101 //     Function: HeightfieldTesselator::get_vertex
00102 //       Access: Private
00103 //  Description: Fetches the vertex at (x,y), or if the vertex
00104 //               does not exist, creates it.
00105 ////////////////////////////////////////////////////////////////////
00106 int HeightfieldTesselator::
00107 get_vertex(int x, int y) {
00108   int xsize = _heightfield.get_x_size();
00109   int vtx = _vertex_index[x+y*xsize];
00110   if (vtx >= 0) {
00111     return vtx;
00112   }
00113   int nx = x-1;
00114   int px = x+1;
00115   int ny = y-1;
00116   int py = y+1;
00117   if (nx < 0) nx++;
00118   if (ny < 0) ny++;
00119   if (px >= _heightfield.get_x_size()) px--;
00120   if (py >= _heightfield.get_y_size()) py--;
00121   double drx = _heightfield.get_gray(px,y) - _heightfield.get_gray(nx,y);
00122   double dry = _heightfield.get_gray(x,py) - _heightfield.get_gray(x,ny);
00123   LVector3 normal(drx * _vertical_scale * 0.5, dry * _vertical_scale * 0.5, _horizontal_scale);
00124   normal.normalize();
00125   double z = _heightfield.get_gray(x,y);
00126   _vertex_writer->add_data3(x*_horizontal_scale,-y*_horizontal_scale,z*_vertical_scale);
00127   _normal_writer->add_data3(normal);
00128   vtx = _next_index++;
00129   _dirty_vertices[vtx] = x+y*xsize;
00130   _vertex_index[x+y*xsize] = vtx;
00131   return vtx;
00132 }
00133 
00134 
00135 ////////////////////////////////////////////////////////////////////
00136 //     Function: HeightfieldTesselator::generate
00137 //       Access: Published
00138 //  Description: Generates a tree of nodes that represents the
00139 //               heightfield.  This can be reparented into the scene.
00140 ////////////////////////////////////////////////////////////////////
00141 NodePath HeightfieldTesselator::
00142 generate() {
00143   int scale = 7;
00144   int size = 1 << scale;
00145   fix_heightfield(size);
00146   int xsize = _heightfield.get_x_size();
00147   int ysize = _heightfield.get_y_size();
00148   int xcells = (xsize + size - 2) / size;
00149   int ycells = (ysize + size - 2) / size;
00150 
00151   _vertex_index = new int[xsize * ysize];
00152   _dirty_vertices = new int[xsize * ysize];
00153   _triangle_totals = new int[xsize * ysize];
00154   for (int y=0; y<ysize; y++) {
00155     for (int x=0; x<xsize; x++) {
00156       _vertex_index[y*xsize+x] = -1;
00157     }
00158   }
00159   
00160   if (!_radii_calculated) {
00161     int saved_focal_x = _focal_x;
00162     int saved_focal_y = _focal_y;
00163 
00164     _focal_x = _heightfield.get_x_size() >> 1;
00165     _focal_y = _heightfield.get_y_size() >> 1;
00166     
00167     calculate_radii(scale);
00168     
00169     _focal_x = saved_focal_x;
00170     _focal_y = saved_focal_y;
00171     
00172     _radii_calculated = true;
00173   }
00174   
00175   PT(PandaNode) result = new PandaNode(get_name());
00176   NodePath root(result);
00177 
00178   int total = 0;
00179   for (int y=0; y<ycells; y++) {
00180     for (int x=0; x<xcells; x++) {
00181       total += count_triangles(scale,x*size,y*size);
00182     }
00183   }
00184   for (int y=0; y<ycells; y++) {
00185     for (int x=0; x<xcells; x++) {
00186       generate_square(root,scale,x*size,y*size,true);
00187     }
00188   }
00189   delete[] _vertex_index;
00190   delete[] _dirty_vertices;
00191   delete[] _triangle_totals;
00192   _vertex_index =0;
00193   _dirty_vertices =0;
00194   _triangle_totals =0;
00195 
00196   return root;
00197 }
00198 
00199 ////////////////////////////////////////////////////////////////////
00200 //     Function: HeightfieldTesselator::calculate_radii
00201 //       Access: Private
00202 //  Description: Sets the radii appropriately to achieve the
00203 //               desired polygon count.  This is achieved by binary
00204 //               search.
00205 ////////////////////////////////////////////////////////////////////
00206 void HeightfieldTesselator::
00207 calculate_radii(int scale) {
00208   int size = 1 << scale;
00209   int xsize = _heightfield.get_x_size();
00210   int ysize = _heightfield.get_y_size();
00211   int xcells = (xsize + size - 2) / size;
00212   int ycells = (ysize + size - 2) / size;
00213   
00214   double lo = 5.0;
00215   double hi = _heightfield.get_x_size() + _heightfield.get_y_size();
00216   while (1) {
00217     double mid = (lo + hi) * 0.5;
00218     for (int i=0; i<16; i++) {
00219       _radii[i] = (int)(mid * (1<<i));
00220     }
00221     int total = 0;
00222     for (int y=0; y<ycells; y++) {
00223       for (int x=0; x<xcells; x++) {
00224         total += count_triangles(scale,x*size,y*size);
00225       }
00226     }
00227     if (total > _poly_count) {
00228       hi = mid;
00229     } else {
00230       lo = mid;
00231     }
00232     if (hi - lo < 1.0) {
00233       break;
00234     }
00235   }
00236   double mid = (lo + hi) * 0.5;
00237   for (int i=0; i<16; i++) {
00238     _radii[i] = (int)(mid * (1<<i));
00239   }
00240 }
00241 
00242 ////////////////////////////////////////////////////////////////////
00243 //     Function: HeightfieldTesselator::generate_square
00244 //       Access: Private
00245 //  Description: Adds a square region to the current geom.
00246 //               This relies on the following preconditions:
00247 //
00248 //               1. A square of scale N can be adjacent to
00249 //               a square of scale N or scale N-1, but not
00250 //               scale N-2 or smaller.
00251 //               
00252 //               2. A square of scale N can be adjacent to
00253 //               at most one square of scale N-1.
00254 //
00255 //               Precondition 1 is assured by spacing out the 
00256 //               detail radii sufficiently.  Precondition 2 is
00257 //               assured by using rectangular detail radii.
00258 //
00259 //               I may someday rewrite this code to eliminate
00260 //               precondition 2, to allow circular detail radii.
00261 ////////////////////////////////////////////////////////////////////
00262 void HeightfieldTesselator::
00263 generate_square(NodePath root, int scale, int x, int y, bool forceclose) {
00264   // There are nine possible vertices in the square,
00265   // which are labeled as follows:
00266   //
00267   //    G--H--I
00268   //    |     |
00269   //    D  E  F
00270   //    |     |
00271   //    A--B--C
00272 
00273   int size = 1<<scale;
00274   int hsize = size>>1;
00275 
00276 #define POINTA get_vertex(x      ,y)
00277 #define POINTB get_vertex(x+hsize,y)
00278 #define POINTC get_vertex(x+size ,y)
00279 #define POINTD get_vertex(x      ,y+hsize)
00280 #define POINTE get_vertex(x+hsize,y+hsize)
00281 #define POINTF get_vertex(x+size ,y+hsize)
00282 #define POINTG get_vertex(x      ,y+size)
00283 #define POINTH get_vertex(x+hsize,y+size)
00284 #define POINTI get_vertex(x+size ,y+size)
00285 
00286   if (_triangles == 0) {
00287     open_geom();
00288   }
00289   if (subdivide(scale, x, y)) {
00290     int xc = x+(size>>1);
00291     int yc = y+(size>>1);
00292     if (_triangle_totals[yc*_heightfield.get_x_size()+xc] > _max_triangles) {
00293       if (_next_index) close_geom(root);
00294       NodePath subroot = root.attach_new_node(get_name() + " interior");
00295       generate_square(subroot, scale-1, x,  y , true);
00296       generate_square(subroot, scale-1, xc, y , true);
00297       generate_square(subroot, scale-1, xc, yc, true);
00298       generate_square(subroot, scale-1, x,  yc, true);
00299     } else {
00300       generate_square(root, scale-1, x,  y , false);
00301       generate_square(root, scale-1, xc, y , false);
00302       generate_square(root, scale-1, xc, yc, false);
00303       generate_square(root, scale-1, x,  yc, false);
00304     }
00305   } else if (subdivide(scale, x+size, y)) {
00306     add_quad(POINTG,POINTA,POINTI,POINTF);
00307     add_quad(POINTA,POINTA,POINTF,POINTC);
00308   } else if (subdivide(scale, x-size, y)) {
00309     add_quad(POINTG,POINTD,POINTI,POINTI);
00310     add_quad(POINTD,POINTA,POINTI,POINTC);
00311   } else if (subdivide(scale, x, y+size)) {
00312     add_quad(POINTG,POINTA,POINTH,POINTA);
00313     add_quad(POINTH,POINTA,POINTI,POINTC);
00314   } else if (subdivide(scale, x, y-size)) {
00315     add_quad(POINTG,POINTA,POINTI,POINTB);
00316     add_quad(POINTI,POINTB,POINTI,POINTC);
00317   } else {
00318     add_quad(POINTG,POINTA,POINTI,POINTC);
00319   }
00320   if (forceclose || (_next_index > _max_triangles)) {
00321     close_geom(root);
00322   }
00323 }
00324 
00325 ////////////////////////////////////////////////////////////////////
00326 //     Function: HeightfieldTesselator::count_triangles
00327 //       Access: Private
00328 //  Description: Calculates how many triangles are inside
00329 //               the given region.  The result is stored in
00330 //               the _poly_totals array, in the center of the
00331 //               square.
00332 ////////////////////////////////////////////////////////////////////
00333 int HeightfieldTesselator::
00334 count_triangles(int scale, int x, int y) {
00335   int size = 1<<scale;
00336   if (subdivide(scale, x, y)) {
00337     int xc = x + (size>>1);
00338     int yc = y + (size>>1);
00339     int n = 0;
00340     n += count_triangles(scale-1, x,  y );
00341     n += count_triangles(scale-1, xc, y );
00342     n += count_triangles(scale-1, x,  yc);
00343     n += count_triangles(scale-1, xc, yc);
00344     _triangle_totals[yc*_heightfield.get_x_size() + xc] = n;
00345     return n;
00346   } else if (subdivide(scale, x+size, y)) {
00347     return 3;
00348   } else if (subdivide(scale, x-size, y)) {
00349     return 3;
00350   } else if (subdivide(scale, x, y+size)) {
00351     return 3;
00352   } else if (subdivide(scale, x, y-size)) {
00353     return 3;
00354   } else {
00355     return 2;
00356   }
00357 }
00358 
00359 ////////////////////////////////////////////////////////////////////
00360 //     Function: HeightfieldTesselator::add_quad_to_strip
00361 //       Access: Private
00362 //  Description: Adds a quad to the current triangle strip.
00363 ////////////////////////////////////////////////////////////////////
00364 void HeightfieldTesselator::
00365 add_quad_to_strip(int v1, int v2, int v3, int v4) {
00366   if ((v1 != v2)&&(v2 != v3)&&(v1 != v3)) {
00367     _triangles->add_vertices(v1,v3,v2);
00368   }
00369   if ((v3 != v2)&&(v2 != v4)&&(v4 != v3)) {
00370     _triangles->add_vertices(v3,v4,v2);
00371   }
00372 }
00373 
00374 ////////////////////////////////////////////////////////////////////
00375 //     Function: HeightfieldTesselator::add_quad
00376 //       Access: Private
00377 //  Description: Adds a quad to the current geom.
00378 //
00379 //               Eventually, I plan to reimplement this.  It is
00380 //               going to add a quad to a table of quads.  A
00381 //               post-processing pass is going to traverse the
00382 //               table, calling add_quad_to_strip in the optimal
00383 //               order.  For now, though, this routine just calls
00384 //               add_quad_to_strip directly, which is quite
00385 //               inefficient.
00386 //
00387 ////////////////////////////////////////////////////////////////////
00388 void HeightfieldTesselator::
00389 add_quad(int v1, int v2, int v3, int v4) {
00390   add_quad_to_strip(v1, v2, v3, v4);
00391 }
00392 
00393 
00394 ////////////////////////////////////////////////////////////////////
00395 //     Function: HeightfieldTesselator::open_geom
00396 //       Access: Private
00397 //  Description: Initiates the construction of a geom.
00398 ////////////////////////////////////////////////////////////////////
00399 void HeightfieldTesselator::
00400 open_geom() {
00401   _vdata = new GeomVertexData
00402     ("heightfield", GeomVertexFormat::get_v3n3(), Geom::UH_static);
00403   _vertex_writer = new GeomVertexWriter(_vdata, InternalName::get_vertex());
00404   _normal_writer = new GeomVertexWriter(_vdata, InternalName::get_normal());
00405   _triangles = new GeomTriangles(Geom::UH_static);
00406   _triangles->set_shade_model(Geom::SM_uniform);
00407 
00408   _next_index = 0;
00409   _last_vertex_a = -1;
00410   _last_vertex_b = -1;
00411 }
00412 
00413 ////////////////////////////////////////////////////////////////////
00414 //     Function: HeightfieldTesselator::close_geom
00415 //       Access: Private
00416 //  Description: Completes the construction of a geom.
00417 ////////////////////////////////////////////////////////////////////
00418 void HeightfieldTesselator::
00419 close_geom(NodePath root) {
00420   if (_triangles == 0) {
00421     return;
00422   }
00423   _triangles->close_primitive();
00424   PT(Geom) geom = new Geom(_vdata);
00425   geom->add_primitive(_triangles);
00426   PT(GeomNode) gnode = new GeomNode(get_name() + " patch");
00427   gnode->add_geom(geom);
00428   root.attach_new_node(gnode);
00429   delete _vertex_writer;
00430   delete _normal_writer;
00431   
00432   for (int i=0; i<_next_index; i++) {
00433     _vertex_index[_dirty_vertices[i]] = -1;
00434   }
00435 
00436   _next_index = 0;
00437   _last_vertex_a = -1;
00438   _last_vertex_b = -1;
00439   _vertex_writer = 0;
00440   _normal_writer = 0;
00441   _triangles = 0;
00442 }
 All Classes Functions Variables Enumerations