Panda3D
|
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 }