Panda3D
 All Classes Functions Variables Enumerations
heightfieldTesselator.cxx
1 // Filename: heightfieldTesselator.cxx
2 // Created by: jyelon (17jul06)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #include "heightfieldTesselator.h"
16 #include "geomNode.h"
17 #include "transformState.h"
18 #include "sceneGraphReducer.h"
19 #include "lvector3.h"
20 
21 ////////////////////////////////////////////////////////////////////
22 // Function: HeightfieldTesselator::fix_heightfield
23 // Access: Published
24 // Description: Makes sure that the heightfield is a grayscale
25 // image of valid dimensions. If necessary, adds a
26 // band of zeros onto two sides of the heightfield,
27 // so as to make the size of the heightfield a multiple
28 // of the given size plus one.
29 ////////////////////////////////////////////////////////////////////
30 void HeightfieldTesselator::
31 fix_heightfield(int size) {
32 
33  // Calculate the padded size of the heightfield.
34  int xsize = _heightfield.get_x_size();
35  int ysize = _heightfield.get_y_size();
36  int xcells = (xsize + size - 2) / size;
37  int ycells = (ysize + size - 2) / size;
38  int xpadded = xcells * size + 1;
39  int ypadded = ycells * size + 1;
40 
41  // If the heightfield is already in good shape, done.
42  if ((xpadded == _heightfield.get_x_size()) &&
43  (ypadded == _heightfield.get_y_size()) &&
44  (_heightfield.is_grayscale())) {
45  return;
46  }
47 
48  // Pad the heightfield, and convert to grey.
49  PNMImage unfixed(_heightfield);
50  _heightfield.clear(xpadded, ypadded, 1,
51  unfixed.get_maxval(),
52  unfixed.get_type());
53  for (int y = 0; y < ysize; y++) {
54  for (int x = 0; x < xsize; x++) {
55  _heightfield.set_gray_val(x, y, unfixed.get_gray_val(x, y));
56  }
57  }
58  for (int y = ysize; y < ypadded; y++) {
59  for (int x = xsize; x < xpadded; x++) {
60  _heightfield.set_gray_val(x, y, 0);
61  }
62  }
63 }
64 
65 ////////////////////////////////////////////////////////////////////
66 // Function: HeightfieldTesselator::get_elevation
67 // Access: Private
68 // Description: Fetches the elevation at (x,y), where the input
69 // coordinate is specified in pixels. This ignores the
70 // current tesselation level and instead provides an
71 // accurate number. Linear blending is used for
72 // non-integral coordinates.
73 ////////////////////////////////////////////////////////////////////
75 get_elevation(double x, double y) {
76  int scale = 7;
77  int size = 1 << scale;
78  fix_heightfield(size);
79  int xlo = (int)x;
80  int ylo = (int)y;
81  if (xlo < 0) xlo = 0;
82  if (ylo < 0) ylo = 0;
83  if (xlo > _heightfield.get_x_size()-2)
84  xlo = _heightfield.get_x_size()-2;
85  if (ylo > _heightfield.get_y_size()-2)
86  ylo = _heightfield.get_y_size()-2;
87  int xhi = xlo+1;
88  int yhi = ylo+1;
89  double xoffs = x - xlo;
90  double yoffs = y - ylo;
91  double grayxlyl = _heightfield.get_gray(xlo,ylo);
92  double grayxhyl = _heightfield.get_gray(xhi,ylo);
93  double grayxlyh = _heightfield.get_gray(xlo,yhi);
94  double grayxhyh = _heightfield.get_gray(xhi,yhi);
95  double lerpyl = grayxhyl * xoffs + grayxlyl * (1.0 - xoffs);
96  double lerpyh = grayxhyh * xoffs + grayxlyh * (1.0 - xoffs);
97  return lerpyh * yoffs + lerpyl * (1.0 - yoffs);
98 }
99 
100 ////////////////////////////////////////////////////////////////////
101 // Function: HeightfieldTesselator::get_vertex
102 // Access: Private
103 // Description: Fetches the vertex at (x,y), or if the vertex
104 // does not exist, creates it.
105 ////////////////////////////////////////////////////////////////////
106 int HeightfieldTesselator::
107 get_vertex(int x, int y) {
108  int xsize = _heightfield.get_x_size();
109  int vtx = _vertex_index[x+y*xsize];
110  if (vtx >= 0) {
111  return vtx;
112  }
113  int nx = x-1;
114  int px = x+1;
115  int ny = y-1;
116  int py = y+1;
117  if (nx < 0) nx++;
118  if (ny < 0) ny++;
119  if (px >= _heightfield.get_x_size()) px--;
120  if (py >= _heightfield.get_y_size()) py--;
121  double drx = _heightfield.get_gray(px,y) - _heightfield.get_gray(nx,y);
122  double dry = _heightfield.get_gray(x,py) - _heightfield.get_gray(x,ny);
123  LVector3 normal(drx * _vertical_scale * 0.5, dry * _vertical_scale * 0.5, _horizontal_scale);
124  normal.normalize();
125  double z = _heightfield.get_gray(x,y);
126  _vertex_writer->add_data3(x*_horizontal_scale,-y*_horizontal_scale,z*_vertical_scale);
127  _normal_writer->add_data3(normal);
128  vtx = _next_index++;
129  _dirty_vertices[vtx] = x+y*xsize;
130  _vertex_index[x+y*xsize] = vtx;
131  return vtx;
132 }
133 
134 
135 ////////////////////////////////////////////////////////////////////
136 // Function: HeightfieldTesselator::generate
137 // Access: Published
138 // Description: Generates a tree of nodes that represents the
139 // heightfield. This can be reparented into the scene.
140 ////////////////////////////////////////////////////////////////////
143  int scale = 7;
144  int size = 1 << scale;
145  fix_heightfield(size);
146  int xsize = _heightfield.get_x_size();
147  int ysize = _heightfield.get_y_size();
148  int xcells = (xsize + size - 2) / size;
149  int ycells = (ysize + size - 2) / size;
150 
151  _vertex_index = new int[xsize * ysize];
152  _dirty_vertices = new int[xsize * ysize];
153  _triangle_totals = new int[xsize * ysize];
154  for (int y=0; y<ysize; y++) {
155  for (int x=0; x<xsize; x++) {
156  _vertex_index[y*xsize+x] = -1;
157  }
158  }
159 
160  if (!_radii_calculated) {
161  int saved_focal_x = _focal_x;
162  int saved_focal_y = _focal_y;
163 
164  _focal_x = _heightfield.get_x_size() >> 1;
165  _focal_y = _heightfield.get_y_size() >> 1;
166 
167  calculate_radii(scale);
168 
169  _focal_x = saved_focal_x;
170  _focal_y = saved_focal_y;
171 
172  _radii_calculated = true;
173  }
174 
175  PT(PandaNode) result = new PandaNode(get_name());
176  NodePath root(result);
177 
178  int total = 0;
179  for (int y=0; y<ycells; y++) {
180  for (int x=0; x<xcells; x++) {
181  total += count_triangles(scale,x*size,y*size);
182  }
183  }
184  for (int y=0; y<ycells; y++) {
185  for (int x=0; x<xcells; x++) {
186  generate_square(root,scale,x*size,y*size,true);
187  }
188  }
189  delete[] _vertex_index;
190  delete[] _dirty_vertices;
191  delete[] _triangle_totals;
192  _vertex_index =0;
193  _dirty_vertices =0;
194  _triangle_totals =0;
195 
196  return root;
197 }
198 
199 ////////////////////////////////////////////////////////////////////
200 // Function: HeightfieldTesselator::calculate_radii
201 // Access: Private
202 // Description: Sets the radii appropriately to achieve the
203 // desired polygon count. This is achieved by binary
204 // search.
205 ////////////////////////////////////////////////////////////////////
206 void HeightfieldTesselator::
207 calculate_radii(int scale) {
208  int size = 1 << scale;
209  int xsize = _heightfield.get_x_size();
210  int ysize = _heightfield.get_y_size();
211  int xcells = (xsize + size - 2) / size;
212  int ycells = (ysize + size - 2) / size;
213 
214  double lo = 5.0;
215  double hi = _heightfield.get_x_size() + _heightfield.get_y_size();
216  while (1) {
217  double mid = (lo + hi) * 0.5;
218  for (int i=0; i<16; i++) {
219  _radii[i] = (int)(mid * (1<<i));
220  }
221  int total = 0;
222  for (int y=0; y<ycells; y++) {
223  for (int x=0; x<xcells; x++) {
224  total += count_triangles(scale,x*size,y*size);
225  }
226  }
227  if (total > _poly_count) {
228  hi = mid;
229  } else {
230  lo = mid;
231  }
232  if (hi - lo < 1.0) {
233  break;
234  }
235  }
236  double mid = (lo + hi) * 0.5;
237  for (int i=0; i<16; i++) {
238  _radii[i] = (int)(mid * (1<<i));
239  }
240 }
241 
242 ////////////////////////////////////////////////////////////////////
243 // Function: HeightfieldTesselator::generate_square
244 // Access: Private
245 // Description: Adds a square region to the current geom.
246 // This relies on the following preconditions:
247 //
248 // 1. A square of scale N can be adjacent to
249 // a square of scale N or scale N-1, but not
250 // scale N-2 or smaller.
251 //
252 // 2. A square of scale N can be adjacent to
253 // at most one square of scale N-1.
254 //
255 // Precondition 1 is assured by spacing out the
256 // detail radii sufficiently. Precondition 2 is
257 // assured by using rectangular detail radii.
258 //
259 // I may someday rewrite this code to eliminate
260 // precondition 2, to allow circular detail radii.
261 ////////////////////////////////////////////////////////////////////
262 void HeightfieldTesselator::
263 generate_square(NodePath root, int scale, int x, int y, bool forceclose) {
264  // There are nine possible vertices in the square,
265  // which are labeled as follows:
266  //
267  // G--H--I
268  // | |
269  // D E F
270  // | |
271  // A--B--C
272 
273  int size = 1<<scale;
274  int hsize = size>>1;
275 
276 #define POINTA get_vertex(x ,y)
277 #define POINTB get_vertex(x+hsize,y)
278 #define POINTC get_vertex(x+size ,y)
279 #define POINTD get_vertex(x ,y+hsize)
280 #define POINTE get_vertex(x+hsize,y+hsize)
281 #define POINTF get_vertex(x+size ,y+hsize)
282 #define POINTG get_vertex(x ,y+size)
283 #define POINTH get_vertex(x+hsize,y+size)
284 #define POINTI get_vertex(x+size ,y+size)
285 
286  if (_triangles == 0) {
287  open_geom();
288  }
289  if (subdivide(scale, x, y)) {
290  int xc = x+(size>>1);
291  int yc = y+(size>>1);
292  if (_triangle_totals[yc*_heightfield.get_x_size()+xc] > _max_triangles) {
293  if (_next_index) close_geom(root);
294  NodePath subroot = root.attach_new_node(get_name() + " interior");
295  generate_square(subroot, scale-1, x, y , true);
296  generate_square(subroot, scale-1, xc, y , true);
297  generate_square(subroot, scale-1, xc, yc, true);
298  generate_square(subroot, scale-1, x, yc, true);
299  } else {
300  generate_square(root, scale-1, x, y , false);
301  generate_square(root, scale-1, xc, y , false);
302  generate_square(root, scale-1, xc, yc, false);
303  generate_square(root, scale-1, x, yc, false);
304  }
305  } else if (subdivide(scale, x+size, y)) {
306  add_quad(POINTG,POINTA,POINTI,POINTF);
307  add_quad(POINTA,POINTA,POINTF,POINTC);
308  } else if (subdivide(scale, x-size, y)) {
309  add_quad(POINTG,POINTD,POINTI,POINTI);
310  add_quad(POINTD,POINTA,POINTI,POINTC);
311  } else if (subdivide(scale, x, y+size)) {
312  add_quad(POINTG,POINTA,POINTH,POINTA);
313  add_quad(POINTH,POINTA,POINTI,POINTC);
314  } else if (subdivide(scale, x, y-size)) {
315  add_quad(POINTG,POINTA,POINTI,POINTB);
316  add_quad(POINTI,POINTB,POINTI,POINTC);
317  } else {
318  add_quad(POINTG,POINTA,POINTI,POINTC);
319  }
320  if (forceclose || (_next_index > _max_triangles)) {
321  close_geom(root);
322  }
323 }
324 
325 ////////////////////////////////////////////////////////////////////
326 // Function: HeightfieldTesselator::count_triangles
327 // Access: Private
328 // Description: Calculates how many triangles are inside
329 // the given region. The result is stored in
330 // the _poly_totals array, in the center of the
331 // square.
332 ////////////////////////////////////////////////////////////////////
333 int HeightfieldTesselator::
334 count_triangles(int scale, int x, int y) {
335  int size = 1<<scale;
336  if (subdivide(scale, x, y)) {
337  int xc = x + (size>>1);
338  int yc = y + (size>>1);
339  int n = 0;
340  n += count_triangles(scale-1, x, y );
341  n += count_triangles(scale-1, xc, y );
342  n += count_triangles(scale-1, x, yc);
343  n += count_triangles(scale-1, xc, yc);
344  _triangle_totals[yc*_heightfield.get_x_size() + xc] = n;
345  return n;
346  } else if (subdivide(scale, x+size, y)) {
347  return 3;
348  } else if (subdivide(scale, x-size, y)) {
349  return 3;
350  } else if (subdivide(scale, x, y+size)) {
351  return 3;
352  } else if (subdivide(scale, x, y-size)) {
353  return 3;
354  } else {
355  return 2;
356  }
357 }
358 
359 ////////////////////////////////////////////////////////////////////
360 // Function: HeightfieldTesselator::add_quad_to_strip
361 // Access: Private
362 // Description: Adds a quad to the current triangle strip.
363 ////////////////////////////////////////////////////////////////////
364 void HeightfieldTesselator::
365 add_quad_to_strip(int v1, int v2, int v3, int v4) {
366  if ((v1 != v2)&&(v2 != v3)&&(v1 != v3)) {
367  _triangles->add_vertices(v1,v3,v2);
368  }
369  if ((v3 != v2)&&(v2 != v4)&&(v4 != v3)) {
370  _triangles->add_vertices(v3,v4,v2);
371  }
372 }
373 
374 ////////////////////////////////////////////////////////////////////
375 // Function: HeightfieldTesselator::add_quad
376 // Access: Private
377 // Description: Adds a quad to the current geom.
378 //
379 // Eventually, I plan to reimplement this. It is
380 // going to add a quad to a table of quads. A
381 // post-processing pass is going to traverse the
382 // table, calling add_quad_to_strip in the optimal
383 // order. For now, though, this routine just calls
384 // add_quad_to_strip directly, which is quite
385 // inefficient.
386 //
387 ////////////////////////////////////////////////////////////////////
388 void HeightfieldTesselator::
389 add_quad(int v1, int v2, int v3, int v4) {
390  add_quad_to_strip(v1, v2, v3, v4);
391 }
392 
393 
394 ////////////////////////////////////////////////////////////////////
395 // Function: HeightfieldTesselator::open_geom
396 // Access: Private
397 // Description: Initiates the construction of a geom.
398 ////////////////////////////////////////////////////////////////////
399 void HeightfieldTesselator::
400 open_geom() {
401  _vdata = new GeomVertexData
402  ("heightfield", GeomVertexFormat::get_v3n3(), Geom::UH_static);
403  _vertex_writer = new GeomVertexWriter(_vdata, InternalName::get_vertex());
404  _normal_writer = new GeomVertexWriter(_vdata, InternalName::get_normal());
405  _triangles = new GeomTriangles(Geom::UH_static);
406  _triangles->set_shade_model(Geom::SM_uniform);
407 
408  _next_index = 0;
409  _last_vertex_a = -1;
410  _last_vertex_b = -1;
411 }
412 
413 ////////////////////////////////////////////////////////////////////
414 // Function: HeightfieldTesselator::close_geom
415 // Access: Private
416 // Description: Completes the construction of a geom.
417 ////////////////////////////////////////////////////////////////////
418 void HeightfieldTesselator::
419 close_geom(NodePath root) {
420  if (_triangles == 0) {
421  return;
422  }
423  _triangles->close_primitive();
424  PT(Geom) geom = new Geom(_vdata);
425  geom->add_primitive(_triangles);
426  PT(GeomNode) gnode = new GeomNode(get_name() + " patch");
427  gnode->add_geom(geom);
428  root.attach_new_node(gnode);
429  delete _vertex_writer;
430  delete _normal_writer;
431 
432  for (int i=0; i<_next_index; i++) {
433  _vertex_index[_dirty_vertices[i]] = -1;
434  }
435 
436  _next_index = 0;
437  _last_vertex_a = -1;
438  _last_vertex_b = -1;
439  _vertex_writer = 0;
440  _normal_writer = 0;
441  _triangles = 0;
442 }
void set_gray_val(int x, int y, xelval gray)
Sets the gray component color at the indicated pixel.
Definition: pnmImage.I:568
A basic node of the scene graph or data graph.
Definition: pandaNode.h:72
This object provides a high-level interface for quickly writing a sequence of numeric values from a v...
The name of this class derives from the fact that we originally implemented it as a layer on top of t...
Definition: pnmImage.h:68
float get_gray(int x, int y) const
Returns the gray component color at the indicated pixel.
Definition: pnmImage.I:928
This is a three-component vector distance (as opposed to a three-component point, which represents a ...
Definition: lvector3.h:100
int get_x_size() const
Returns the number of pixels in the X direction.
int get_y_size() const
Returns the number of pixels in the Y direction.
This defines the actual numeric vertex data stored in a Geom, in the structure defined by a particula...
A container for geometry primitives.
Definition: geom.h:58
void add_data3(PN_stdfloat x, PN_stdfloat y, PN_stdfloat z)
Sets the write row to a particular 3-component value, and advances the write row. ...
NodePath generate()
Generates a tree of nodes that represents the heightfield.
double get_elevation(double x, double y)
Fetches the elevation at (x,y), where the input coordinate is specified in pixels.
void clear()
Frees all memory allocated for the image, and clears all its parameters (size, color, type, etc).
Definition: pnmImage.cxx:50
Defines a series of disconnected triangles.
Definition: geomTriangles.h:25
static bool is_grayscale(ColorType color_type)
This static variant of is_grayscale() returns true if the indicated image type represents a grayscale...
bool normalize()
Normalizes the vector in place.
Definition: lvecBase3.h:782
NodePath is the fundamental system for disambiguating instances, and also provides a higher-level int...
Definition: nodePath.h:165
A node that holds Geom objects, renderable pieces of geometry.
Definition: geomNode.h:37
NodePath attach_new_node(PandaNode *node, int sort=0, Thread *current_thread=Thread::get_current_thread()) const
Attaches a new node, with or without existing parents, to the scene graph below the referenced node o...
Definition: nodePath.cxx:723