Panda3D
Loading...
Searching...
No Matches
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
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 */
25void HeightfieldTesselator::
26fix_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 */
66get_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 */
94int HeightfieldTesselator::
95get_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 */
128generate() {
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 */
189void HeightfieldTesselator::
190calculate_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 */
240void HeightfieldTesselator::
241generate_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 */
303int HeightfieldTesselator::
304count_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 */
332void HeightfieldTesselator::
333add_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 */
351void HeightfieldTesselator::
352add_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 */
360void HeightfieldTesselator::
361open_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 */
377void HeightfieldTesselator::
378close_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}
A node that holds Geom objects, renderable pieces of geometry.
Definition geomNode.h:34
Defines a series of disconnected triangles.
This defines the actual numeric vertex data stored in a Geom, in the structure defined by a particula...
static const GeomVertexFormat * get_v3n3()
Returns a standard vertex format with a 3-component normal and a 3-component vertex position.
This object provides a high-level interface for quickly writing a sequence of numeric values from a v...
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.
A container for geometry primitives.
Definition geom.h:54
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.
NodePath is the fundamental system for disambiguating instances, and also provides a higher-level int...
Definition nodePath.h:159
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:599
int get_x_size() const
Returns the number of pixels in the X direction.
static bool is_grayscale(ColorType color_type)
This static variant of is_grayscale() returns true if the indicated image type represents a grayscale...
int get_y_size() const
Returns the number of pixels in the Y direction.
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
void clear()
Frees all memory allocated for the image, and clears all its parameters (size, color,...
Definition pnmImage.cxx:48
float get_gray(int x, int y) const
Returns the gray component color at the indicated pixel.
Definition pnmImage.I:799
void set_gray_val(int x, int y, xelval gray)
Sets the gray component color at the indicated pixel.
Definition pnmImage.I:545
A basic node of the scene graph or data graph.
Definition pandaNode.h:65
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.