00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
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
00023
00024
00025
00026
00027
00028
00029
00030 void HeightfieldTesselator::
00031 fix_heightfield(int size) {
00032
00033
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
00042 if ((xpadded == _heightfield.get_x_size()) &&
00043 (ypadded == _heightfield.get_y_size()) &&
00044 (_heightfield.is_grayscale())) {
00045 return;
00046 }
00047
00048
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
00067
00068
00069
00070
00071
00072
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
00102
00103
00104
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
00137
00138
00139
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
00201
00202
00203
00204
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
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261
00262 void HeightfieldTesselator::
00263 generate_square(NodePath root, int scale, int x, int y, bool forceclose) {
00264
00265
00266
00267
00268
00269
00270
00271
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
00327
00328
00329
00330
00331
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
00361
00362
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
00376
00377
00378
00379
00380
00381
00382
00383
00384
00385
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
00396
00397
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
00415
00416
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 }