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