Line data Source code
1 : /* Copyright (C) 2022 Wildfire Games.
2 : * This file is part of 0 A.D.
3 : *
4 : * 0 A.D. is free software: you can redistribute it and/or modify
5 : * it under the terms of the GNU General Public License as published by
6 : * the Free Software Foundation, either version 2 of the License, or
7 : * (at your option) any later version.
8 : *
9 : * 0 A.D. is distributed in the hope that it will be useful,
10 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : * GNU General Public License for more details.
13 : *
14 : * You should have received a copy of the GNU General Public License
15 : * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16 : */
17 :
18 : #include "precompiled.h"
19 :
20 : #include "graphics/Terrain.h"
21 :
22 : #include "graphics/Patch.h"
23 : #include "graphics/TerrainProperties.h"
24 : #include "graphics/TerrainTextureEntry.h"
25 : #include "graphics/TerrainTextureManager.h"
26 : #include "lib/sysdep/cpu.h"
27 : #include "maths/FixedVector3D.h"
28 : #include "maths/MathUtil.h"
29 : #include "ps/CLogger.h"
30 : #include "renderer/Renderer.h"
31 : #include "simulation2/helpers/Pathfinding.h"
32 :
33 : #include <string.h>
34 :
35 : ///////////////////////////////////////////////////////////////////////////////
36 : // CTerrain constructor
37 19 : CTerrain::CTerrain()
38 : : m_Heightmap(0), m_Patches(0), m_MapSize(0), m_MapSizePatches(0),
39 19 : m_BaseColor(255, 255, 255, 255)
40 : {
41 19 : }
42 :
43 : ///////////////////////////////////////////////////////////////////////////////
44 : // CTerrain constructor
45 38 : CTerrain::~CTerrain()
46 : {
47 19 : ReleaseData();
48 19 : }
49 :
50 :
51 : ///////////////////////////////////////////////////////////////////////////////
52 : // ReleaseData: delete any data allocated by this terrain
53 48 : void CTerrain::ReleaseData()
54 : {
55 48 : m_HeightMipmap.ReleaseData();
56 :
57 48 : delete[] m_Heightmap;
58 48 : delete[] m_Patches;
59 48 : }
60 :
61 :
62 : ///////////////////////////////////////////////////////////////////////////////
63 : // Initialise: initialise this terrain to the given size
64 : // using given heightmap to setup elevation data
65 22 : bool CTerrain::Initialize(ssize_t patchesPerSide, const u16* data)
66 : {
67 : // clean up any previous terrain
68 22 : ReleaseData();
69 :
70 : // store terrain size
71 22 : m_MapSize = patchesPerSide * PATCH_SIZE + 1;
72 22 : m_MapSizePatches = patchesPerSide;
73 : // allocate data for new terrain
74 22 : m_Heightmap = new u16[m_MapSize * m_MapSize];
75 22 : m_Patches = new CPatch[m_MapSizePatches * m_MapSizePatches];
76 :
77 : // given a heightmap?
78 22 : if (data)
79 : {
80 : // yes; keep a copy of it
81 13 : memcpy(m_Heightmap, data, m_MapSize*m_MapSize*sizeof(u16));
82 : }
83 : else
84 : {
85 : // build a flat terrain
86 9 : memset(m_Heightmap, 0, m_MapSize*m_MapSize*sizeof(u16));
87 : }
88 :
89 : // setup patch parents, indices etc
90 22 : InitialisePatches();
91 :
92 : // initialise mipmap
93 22 : m_HeightMipmap.Initialize(m_MapSize, m_Heightmap);
94 :
95 22 : return true;
96 : }
97 :
98 : ///////////////////////////////////////////////////////////////////////////////
99 : // CalcPosition: calculate the world space position of the vertex at (i,j)
100 : // If i,j is off the map, it acts as if the edges of the terrain are extended
101 : // outwards to infinity
102 295951 : void CTerrain::CalcPosition(ssize_t i, ssize_t j, CVector3D& pos) const
103 : {
104 295951 : ssize_t hi = Clamp<ssize_t>(i, 0, m_MapSize - 1);
105 295951 : ssize_t hj = Clamp<ssize_t>(j, 0, m_MapSize - 1);
106 295951 : u16 height = m_Heightmap[hj*m_MapSize + hi];
107 295951 : pos.X = float(i*TERRAIN_TILE_SIZE);
108 295951 : pos.Y = float(height*HEIGHT_SCALE);
109 295951 : pos.Z = float(j*TERRAIN_TILE_SIZE);
110 295951 : }
111 :
112 : ///////////////////////////////////////////////////////////////////////////////
113 : // CalcPositionFixed: calculate the world space position of the vertex at (i,j)
114 15 : void CTerrain::CalcPositionFixed(ssize_t i, ssize_t j, CFixedVector3D& pos) const
115 : {
116 15 : ssize_t hi = Clamp<ssize_t>(i, 0, m_MapSize - 1);
117 15 : ssize_t hj = Clamp<ssize_t>(j, 0, m_MapSize - 1);
118 15 : u16 height = m_Heightmap[hj*m_MapSize + hi];
119 15 : pos.X = fixed::FromInt(i) * (int)TERRAIN_TILE_SIZE;
120 : // fixed max value is 32767, but height is a u16, so divide by two to avoid overflow
121 15 : pos.Y = fixed::FromInt(height/ 2 ) / ((int)HEIGHT_UNITS_PER_METRE / 2);
122 15 : pos.Z = fixed::FromInt(j) * (int)TERRAIN_TILE_SIZE;
123 15 : }
124 :
125 :
126 : ///////////////////////////////////////////////////////////////////////////////
127 : // CalcNormal: calculate the world space normal of the vertex at (i,j)
128 3 : void CTerrain::CalcNormal(ssize_t i, ssize_t j, CVector3D& normal) const
129 : {
130 3 : CVector3D left, right, up, down;
131 :
132 : // Calculate normals of the four half-tile triangles surrounding this vertex:
133 :
134 : // get position of vertex where normal is being evaluated
135 3 : CVector3D basepos;
136 3 : CalcPosition(i, j, basepos);
137 :
138 3 : if (i > 0) {
139 3 : CalcPosition(i-1, j, left);
140 3 : left -= basepos;
141 3 : left.Normalize();
142 : }
143 :
144 3 : if (i < m_MapSize-1) {
145 3 : CalcPosition(i+1, j, right);
146 3 : right -= basepos;
147 3 : right.Normalize();
148 : }
149 :
150 3 : if (j > 0) {
151 3 : CalcPosition(i, j-1, up);
152 3 : up -= basepos;
153 3 : up.Normalize();
154 : }
155 :
156 3 : if (j < m_MapSize-1) {
157 3 : CalcPosition(i, j+1, down);
158 3 : down -= basepos;
159 3 : down.Normalize();
160 : }
161 :
162 3 : CVector3D n0 = up.Cross(left);
163 3 : CVector3D n1 = left.Cross(down);
164 3 : CVector3D n2 = down.Cross(right);
165 3 : CVector3D n3 = right.Cross(up);
166 :
167 : // Compute the mean of the normals
168 3 : normal = n0 + n1 + n2 + n3;
169 3 : float nlen=normal.Length();
170 3 : if (nlen>0.00001f) normal*=1.0f/nlen;
171 3 : }
172 :
173 : ///////////////////////////////////////////////////////////////////////////////
174 : // CalcNormalFixed: calculate the world space normal of the vertex at (i,j)
175 3 : void CTerrain::CalcNormalFixed(ssize_t i, ssize_t j, CFixedVector3D& normal) const
176 : {
177 3 : CFixedVector3D left, right, up, down;
178 :
179 : // Calculate normals of the four half-tile triangles surrounding this vertex:
180 :
181 : // get position of vertex where normal is being evaluated
182 3 : CFixedVector3D basepos;
183 3 : CalcPositionFixed(i, j, basepos);
184 :
185 3 : if (i > 0) {
186 3 : CalcPositionFixed(i-1, j, left);
187 3 : left -= basepos;
188 3 : left.Normalize();
189 : }
190 :
191 3 : if (i < m_MapSize-1) {
192 3 : CalcPositionFixed(i+1, j, right);
193 3 : right -= basepos;
194 3 : right.Normalize();
195 : }
196 :
197 3 : if (j > 0) {
198 3 : CalcPositionFixed(i, j-1, up);
199 3 : up -= basepos;
200 3 : up.Normalize();
201 : }
202 :
203 3 : if (j < m_MapSize-1) {
204 3 : CalcPositionFixed(i, j+1, down);
205 3 : down -= basepos;
206 3 : down.Normalize();
207 : }
208 :
209 3 : CFixedVector3D n0 = up.Cross(left);
210 3 : CFixedVector3D n1 = left.Cross(down);
211 3 : CFixedVector3D n2 = down.Cross(right);
212 3 : CFixedVector3D n3 = right.Cross(up);
213 :
214 : // Compute the mean of the normals
215 3 : normal = n0 + n1 + n2 + n3;
216 3 : normal.Normalize();
217 3 : }
218 :
219 0 : CVector3D CTerrain::CalcExactNormal(float x, float z) const
220 : {
221 : // Clamp to size-2 so we can use the tiles (xi,zi)-(xi+1,zi+1)
222 0 : const ssize_t xi = Clamp<ssize_t>(floor(x / TERRAIN_TILE_SIZE), 0, m_MapSize - 2);
223 0 : const ssize_t zi = Clamp<ssize_t>(floor(z / TERRAIN_TILE_SIZE), 0, m_MapSize - 2);
224 :
225 0 : const float xf = Clamp(x / TERRAIN_TILE_SIZE-xi, 0.0f, 1.0f);
226 0 : const float zf = Clamp(z / TERRAIN_TILE_SIZE-zi, 0.0f, 1.0f);
227 :
228 0 : float h00 = m_Heightmap[zi*m_MapSize + xi];
229 0 : float h01 = m_Heightmap[(zi+1)*m_MapSize + xi];
230 0 : float h10 = m_Heightmap[zi*m_MapSize + (xi+1)];
231 0 : float h11 = m_Heightmap[(zi+1)*m_MapSize + (xi+1)];
232 :
233 : // Determine which terrain triangle this point is on,
234 : // then compute the normal of that triangle's plane
235 :
236 0 : if (GetTriangulationDir(xi, zi))
237 : {
238 0 : if (xf + zf <= 1.f)
239 : {
240 : // Lower-left triangle (don't use h11)
241 0 : return -CVector3D(TERRAIN_TILE_SIZE, (h10-h00)*HEIGHT_SCALE, 0).Cross(CVector3D(0, (h01-h00)*HEIGHT_SCALE, TERRAIN_TILE_SIZE)).Normalized();
242 : }
243 : else
244 : {
245 : // Upper-right triangle (don't use h00)
246 0 : return -CVector3D(TERRAIN_TILE_SIZE, (h11-h01)*HEIGHT_SCALE, 0).Cross(CVector3D(0, (h11-h10)*HEIGHT_SCALE, TERRAIN_TILE_SIZE)).Normalized();
247 : }
248 : }
249 : else
250 : {
251 0 : if (xf <= zf)
252 : {
253 : // Upper-left triangle (don't use h10)
254 0 : return -CVector3D(TERRAIN_TILE_SIZE, (h11-h01)*HEIGHT_SCALE, 0).Cross(CVector3D(0, (h01-h00)*HEIGHT_SCALE, TERRAIN_TILE_SIZE)).Normalized();
255 : }
256 : else
257 : {
258 : // Lower-right triangle (don't use h01)
259 0 : return -CVector3D(TERRAIN_TILE_SIZE, (h10-h00)*HEIGHT_SCALE, 0).Cross(CVector3D(0, (h11-h10)*HEIGHT_SCALE, TERRAIN_TILE_SIZE)).Normalized();
260 : }
261 : }
262 : }
263 :
264 : ///////////////////////////////////////////////////////////////////////////////
265 : // GetPatch: return the patch at (i,j) in patch space, or null if the patch is
266 : // out of bounds
267 1293 : CPatch* CTerrain::GetPatch(ssize_t i, ssize_t j) const
268 : {
269 : // range check (invalid indices are passed in by the culling and
270 : // patch blend code because they iterate from 0..#patches and examine
271 : // neighbors without checking if they're already on the edge)
272 1293 : if( (size_t)i >= (size_t)m_MapSizePatches || (size_t)j >= (size_t)m_MapSizePatches )
273 0 : return 0;
274 :
275 1293 : return &m_Patches[(j*m_MapSizePatches)+i];
276 : }
277 :
278 :
279 : ///////////////////////////////////////////////////////////////////////////////
280 : // GetTile: return the tile at (i,j) in tile space, or null if the tile is out
281 : // of bounds
282 0 : CMiniPatch* CTerrain::GetTile(ssize_t i, ssize_t j) const
283 : {
284 : // see comment above
285 0 : if( (size_t)i >= (size_t)(m_MapSize-1) || (size_t)j >= (size_t)(m_MapSize-1) )
286 0 : return 0;
287 :
288 0 : CPatch* patch=GetPatch(i/PATCH_SIZE, j/PATCH_SIZE); // can't fail (due to above check)
289 0 : return &patch->m_MiniPatches[j%PATCH_SIZE][i%PATCH_SIZE];
290 : }
291 :
292 0 : float CTerrain::GetVertexGroundLevel(ssize_t i, ssize_t j) const
293 : {
294 0 : i = Clamp<ssize_t>(i, 0, m_MapSize - 1);
295 0 : j = Clamp<ssize_t>(j, 0, m_MapSize - 1);
296 0 : return HEIGHT_SCALE * m_Heightmap[j*m_MapSize + i];
297 : }
298 :
299 0 : fixed CTerrain::GetVertexGroundLevelFixed(ssize_t i, ssize_t j) const
300 : {
301 0 : i = Clamp<ssize_t>(i, 0, m_MapSize - 1);
302 0 : j = Clamp<ssize_t>(j, 0, m_MapSize - 1);
303 : // Convert to fixed metres (being careful to avoid intermediate overflows)
304 0 : return fixed::FromInt(m_Heightmap[j*m_MapSize + i] / 2) / (int)(HEIGHT_UNITS_PER_METRE / 2);
305 : }
306 :
307 0 : fixed CTerrain::GetSlopeFixed(ssize_t i, ssize_t j) const
308 : {
309 : // Clamp to size-2 so we can use the tiles (i,j)-(i+1,j+1)
310 0 : i = Clamp<ssize_t>(i, 0, m_MapSize - 2);
311 0 : j = Clamp<ssize_t>(j, 0, m_MapSize - 2);
312 :
313 0 : u16 h00 = m_Heightmap[j*m_MapSize + i];
314 0 : u16 h01 = m_Heightmap[(j+1)*m_MapSize + i];
315 0 : u16 h10 = m_Heightmap[j*m_MapSize + (i+1)];
316 0 : u16 h11 = m_Heightmap[(j+1)*m_MapSize + (i+1)];
317 :
318 : // Difference of highest point from lowest point
319 0 : u16 delta = std::max(std::max(h00, h01), std::max(h10, h11)) -
320 0 : std::min(std::min(h00, h01), std::min(h10, h11));
321 :
322 : // Compute fractional slope (being careful to avoid intermediate overflows)
323 0 : return fixed::FromInt(delta / TERRAIN_TILE_SIZE) / (int)HEIGHT_UNITS_PER_METRE;
324 : }
325 :
326 0 : fixed CTerrain::GetExactSlopeFixed(fixed x, fixed z) const
327 : {
328 : // Clamp to size-2 so we can use the tiles (xi,zi)-(xi+1,zi+1)
329 0 : const ssize_t xi = Clamp<ssize_t>((x / static_cast<int>(TERRAIN_TILE_SIZE)).ToInt_RoundToZero(), 0, m_MapSize - 2);
330 0 : const ssize_t zi = Clamp<ssize_t>((z / static_cast<int>(TERRAIN_TILE_SIZE)).ToInt_RoundToZero(), 0, m_MapSize - 2);
331 :
332 0 : const fixed one = fixed::FromInt(1);
333 :
334 0 : const fixed xf = Clamp((x / static_cast<int>(TERRAIN_TILE_SIZE)) - fixed::FromInt(xi), fixed::Zero(), one);
335 0 : const fixed zf = Clamp((z / static_cast<int>(TERRAIN_TILE_SIZE)) - fixed::FromInt(zi), fixed::Zero(), one);
336 :
337 0 : u16 h00 = m_Heightmap[zi*m_MapSize + xi];
338 0 : u16 h01 = m_Heightmap[(zi+1)*m_MapSize + xi];
339 0 : u16 h10 = m_Heightmap[zi*m_MapSize + (xi+1)];
340 0 : u16 h11 = m_Heightmap[(zi+1)*m_MapSize + (xi+1)];
341 :
342 : u16 delta;
343 0 : if (GetTriangulationDir(xi, zi))
344 : {
345 0 : if (xf + zf <= one)
346 : {
347 : // Lower-left triangle (don't use h11)
348 0 : delta = std::max(std::max(h00, h01), h10) -
349 0 : std::min(std::min(h00, h01), h10);
350 : }
351 : else
352 : {
353 : // Upper-right triangle (don't use h00)
354 0 : delta = std::max(std::max(h01, h10), h11) -
355 0 : std::min(std::min(h01, h10), h11);
356 : }
357 : }
358 : else
359 : {
360 0 : if (xf <= zf)
361 : {
362 : // Upper-left triangle (don't use h10)
363 0 : delta = std::max(std::max(h00, h01), h11) -
364 0 : std::min(std::min(h00, h01), h11);
365 : }
366 : else
367 : {
368 : // Lower-right triangle (don't use h01)
369 0 : delta = std::max(std::max(h00, h10), h11) -
370 0 : std::min(std::min(h00, h10), h11);
371 : }
372 : }
373 :
374 : // Compute fractional slope (being careful to avoid intermediate overflows)
375 0 : return fixed::FromInt(delta / TERRAIN_TILE_SIZE) / (int)HEIGHT_UNITS_PER_METRE;
376 : }
377 :
378 0 : float CTerrain::GetFilteredGroundLevel(float x, float z, float radius) const
379 : {
380 : // convert to [0,1] interval
381 0 : float nx = x / (TERRAIN_TILE_SIZE*m_MapSize);
382 0 : float nz = z / (TERRAIN_TILE_SIZE*m_MapSize);
383 0 : float nr = radius / (TERRAIN_TILE_SIZE*m_MapSize);
384 :
385 : // get trilinear filtered mipmap height
386 0 : return HEIGHT_SCALE * m_HeightMipmap.GetTrilinearGroundLevel(nx, nz, nr);
387 : }
388 :
389 6 : float CTerrain::GetExactGroundLevel(float x, float z) const
390 : {
391 : // Clamp to size-2 so we can use the tiles (xi,zi)-(xi+1,zi+1)
392 6 : const ssize_t xi = Clamp<ssize_t>(floor(x / TERRAIN_TILE_SIZE), 0, m_MapSize - 2);
393 6 : const ssize_t zi = Clamp<ssize_t>(floor(z / TERRAIN_TILE_SIZE), 0, m_MapSize - 2);
394 :
395 6 : const float xf = Clamp(x / TERRAIN_TILE_SIZE - xi, 0.0f, 1.0f);
396 6 : const float zf = Clamp(z / TERRAIN_TILE_SIZE - zi, 0.0f, 1.0f);
397 :
398 6 : float h00 = m_Heightmap[zi*m_MapSize + xi];
399 6 : float h01 = m_Heightmap[(zi+1)*m_MapSize + xi];
400 6 : float h10 = m_Heightmap[zi*m_MapSize + (xi+1)];
401 6 : float h11 = m_Heightmap[(zi+1)*m_MapSize + (xi+1)];
402 :
403 : // Determine which terrain triangle this point is on,
404 : // then compute the linearly-interpolated height on that triangle's plane
405 :
406 6 : if (GetTriangulationDir(xi, zi))
407 : {
408 0 : if (xf + zf <= 1.f)
409 : {
410 : // Lower-left triangle (don't use h11)
411 0 : return HEIGHT_SCALE * (h00 + (h10-h00)*xf + (h01-h00)*zf);
412 : }
413 : else
414 : {
415 : // Upper-right triangle (don't use h00)
416 0 : return HEIGHT_SCALE * (h11 + (h01-h11)*(1-xf) + (h10-h11)*(1-zf));
417 : }
418 : }
419 : else
420 : {
421 6 : if (xf <= zf)
422 : {
423 : // Upper-left triangle (don't use h10)
424 6 : return HEIGHT_SCALE * (h00 + (h11-h01)*xf + (h01-h00)*zf);
425 : }
426 : else
427 : {
428 : // Lower-right triangle (don't use h01)
429 0 : return HEIGHT_SCALE * (h00 + (h10-h00)*xf + (h11-h10)*zf);
430 : }
431 : }
432 : }
433 :
434 65031 : fixed CTerrain::GetExactGroundLevelFixed(fixed x, fixed z) const
435 : {
436 : // Clamp to size-2 so we can use the tiles (xi,zi)-(xi+1,zi+1)
437 65031 : const ssize_t xi = Clamp<ssize_t>((x / static_cast<int>(TERRAIN_TILE_SIZE)).ToInt_RoundToZero(), 0, m_MapSize - 2);
438 65031 : const ssize_t zi = Clamp<ssize_t>((z / static_cast<int>(TERRAIN_TILE_SIZE)).ToInt_RoundToZero(), 0, m_MapSize - 2);
439 :
440 65031 : const fixed one = fixed::FromInt(1);
441 :
442 65031 : const fixed xf = Clamp((x / static_cast<int>(TERRAIN_TILE_SIZE)) - fixed::FromInt(xi), fixed::Zero(), one);
443 65031 : const fixed zf = Clamp((z / static_cast<int>(TERRAIN_TILE_SIZE)) - fixed::FromInt(zi), fixed::Zero(), one);
444 :
445 65031 : u16 h00 = m_Heightmap[zi*m_MapSize + xi];
446 65031 : u16 h01 = m_Heightmap[(zi+1)*m_MapSize + xi];
447 65031 : u16 h10 = m_Heightmap[zi*m_MapSize + (xi+1)];
448 65031 : u16 h11 = m_Heightmap[(zi+1)*m_MapSize + (xi+1)];
449 :
450 : // Intermediate scaling of xf, so we don't overflow in the multiplications below
451 : // (h00 <= 65535, xf <= 1, max fixed is < 32768; divide by 2 here so xf1*h00 <= 32767.5)
452 65031 : const fixed xf0 = xf / 2;
453 65031 : const fixed xf1 = (one - xf) / 2;
454 :
455 : // Linearly interpolate
456 130062 : return ((one - zf).Multiply(xf1 * h00 + xf0 * h10)
457 195093 : + zf.Multiply(xf1 * h01 + xf0 * h11)) / (int)(HEIGHT_UNITS_PER_METRE / 2);
458 :
459 : // TODO: This should probably be more like GetExactGroundLevel()
460 : // in handling triangulation properly
461 : }
462 :
463 6 : bool CTerrain::GetTriangulationDir(ssize_t i, ssize_t j) const
464 : {
465 : // Clamp to size-2 so we can use the tiles (i,j)-(i+1,j+1)
466 6 : i = Clamp<ssize_t>(i, 0, m_MapSize - 2);
467 6 : j = Clamp<ssize_t>(j, 0, m_MapSize - 2);
468 :
469 6 : int h00 = m_Heightmap[j*m_MapSize + i];
470 6 : int h01 = m_Heightmap[(j+1)*m_MapSize + i];
471 6 : int h10 = m_Heightmap[j*m_MapSize + (i+1)];
472 6 : int h11 = m_Heightmap[(j+1)*m_MapSize + (i+1)];
473 :
474 : // Prefer triangulating in whichever direction means the midpoint of the diagonal
475 : // will be the highest. (In particular this means a diagonal edge will be straight
476 : // along the top, and jagged along the bottom, which makes sense for terrain.)
477 6 : int mid1 = h00+h11;
478 6 : int mid2 = h01+h10;
479 6 : return (mid1 < mid2);
480 : }
481 :
482 13 : void CTerrain::ResizeAndOffset(ssize_t size, ssize_t horizontalOffset, ssize_t verticalOffset)
483 : {
484 13 : if (size == m_MapSizePatches && horizontalOffset == 0 && verticalOffset == 0)
485 : {
486 : // Inexplicable request to resize terrain to the same size, ignore it.
487 2 : return;
488 : }
489 :
490 33 : if (!m_Heightmap ||
491 18 : std::abs(horizontalOffset) >= size / 2 + m_MapSizePatches / 2 ||
492 7 : std::abs(verticalOffset) >= size / 2 + m_MapSizePatches / 2)
493 : {
494 : // We have not yet created a terrain, or we are offsetting outside the current source.
495 : // Let's build a default terrain of the given size now.
496 4 : Initialize(size, 0);
497 4 : return;
498 : }
499 :
500 : // Allocate data for new terrain.
501 7 : const ssize_t newMapSize = size * PATCH_SIZE + 1;
502 7 : u16* newHeightmap = new u16[newMapSize * newMapSize];
503 7 : memset(newHeightmap, 0, newMapSize * newMapSize * sizeof(u16));
504 7 : CPatch* newPatches = new CPatch[size * size];
505 :
506 : // O--------------------+
507 : // | Source |
508 : // | |
509 : // | Source Center (SC) |
510 : // | X |
511 : // | A------+----------------+
512 : // | | | Destination |
513 : // | | | |
514 : // +-------------+------B |
515 : // | Dest. Center (DC) |
516 : // | X |
517 : // | |
518 : // | |
519 : // | |
520 : // | |
521 : // +-----------------------+
522 : //
523 : // Calculations below should also account cases like:
524 : //
525 : // +----------+ +----------+ +----------+ +---+--+---+ +------+
526 : // |S | |D | |S | |S | | D| |D |
527 : // | +---+ | | +---+ | +-+-+ | | | | | | +---+--+
528 : // | | D | | | | S | | |D| | | +---+--+---+ +--+---+ |
529 : // | +---+ | | +---+ | +-+-+ | | S|
530 : // +----------+ +----------+ +----------+ +------+
531 : //
532 : // O = (0, 0)
533 : // SC = (m_MapSizePatches / 2, m_MapSizePatches / 2)
534 : // DC - SC = (horizontalOffset, verticalOffset)
535 : //
536 : // Source upper left:
537 : // A = (max(0, (m_MapSizePatches - size) / 2 + horizontalOffset),
538 : // max(0, (m_MapSizePatches - size) / 2 + verticalOffset))
539 : // Source bottom right:
540 : // B = (min(m_MapSizePatches, (m_MapSizePatches + size) / 2 + horizontalOffset),
541 : // min(m_MapSizePatches, (m_MapSizePatches + size) / 2 + verticalOffset))
542 : //
543 : // A-B is the area that we have to copy from the source to the destination.
544 :
545 : // Restate center offset as a window over destination.
546 : // This has the effect of always considering the source to be the same size or smaller.
547 : const ssize_t sourceUpperLeftX = std::max(
548 7 : static_cast<ssize_t>(0), m_MapSizePatches / 2 - size / 2 + horizontalOffset);
549 : const ssize_t sourceUpperLeftZ = std::max(
550 7 : static_cast<ssize_t>(0), m_MapSizePatches / 2 - size / 2 + verticalOffset);
551 :
552 : const ssize_t destUpperLeftX = std::max(
553 7 : static_cast<ssize_t>(0), (size / 2 - m_MapSizePatches / 2 - horizontalOffset));
554 : const ssize_t destUpperLeftZ = std::max(
555 7 : static_cast<ssize_t>(0), (size / 2 - m_MapSizePatches / 2 - verticalOffset));
556 :
557 : const ssize_t width =
558 7 : std::min(m_MapSizePatches, m_MapSizePatches / 2 + horizontalOffset + size / 2) - sourceUpperLeftX;
559 : const ssize_t depth =
560 7 : std::min(m_MapSizePatches, m_MapSizePatches / 2 + verticalOffset + size / 2) - sourceUpperLeftZ;
561 :
562 215 : for (ssize_t j = 0; j < depth * PATCH_SIZE; ++j)
563 : {
564 : // Copy the main part from the source. Destination heightmap:
565 : // +----------+
566 : // | |
567 : // | 1234 | < current j-th row for example.
568 : // | 5678 |
569 : // | |
570 : // +----------+
571 208 : u16* dst = newHeightmap + (j + destUpperLeftZ * PATCH_SIZE) * newMapSize + destUpperLeftX * PATCH_SIZE;
572 208 : u16* src = m_Heightmap + (j + sourceUpperLeftZ * PATCH_SIZE) * m_MapSize + sourceUpperLeftX * PATCH_SIZE;
573 208 : std::copy_n(src, width * PATCH_SIZE, dst);
574 208 : if (destUpperLeftX > 0)
575 : {
576 : // Fill the preceding part by copying the first elements of the
577 : // main part. Destination heightmap:
578 : // +----------+
579 : // | |
580 : // |1111234 | < current j-th row for example.
581 : // | 5678 |
582 : // | |
583 : // +----------+
584 96 : u16* dst_prefix = newHeightmap + (j + destUpperLeftZ * PATCH_SIZE) * newMapSize;
585 96 : std::fill_n(dst_prefix, destUpperLeftX * PATCH_SIZE, dst[0]);
586 : }
587 208 : if ((destUpperLeftX + width) * PATCH_SIZE < newMapSize)
588 : {
589 : // Fill the succeeding part by copying the last elements of the
590 : // main part. Destination heightmap:
591 : // +----------+
592 : // | |
593 : // |1111234444| < current j-th row for example.
594 : // | 5678 |
595 : // | |
596 : // +----------+
597 208 : u16* dst_suffix = dst + width * PATCH_SIZE;
598 208 : std::fill_n(
599 : dst_suffix,
600 208 : newMapSize - (width + destUpperLeftX) * PATCH_SIZE,
601 208 : dst[width * PATCH_SIZE - 1]);
602 : }
603 : }
604 : // Copy over heights from the preceding row. Destination heightmap:
605 : // +----------+
606 : // |1111234444| < copied from the row below
607 : // |1111234444|
608 : // |5555678888|
609 : // | |
610 : // +----------+
611 71 : for (ssize_t j = 0; j < destUpperLeftZ * PATCH_SIZE; ++j)
612 : {
613 :
614 64 : u16* dst = newHeightmap + j * newMapSize;
615 64 : u16* src = newHeightmap + destUpperLeftZ * PATCH_SIZE * newMapSize;
616 64 : std::copy_n(src, newMapSize, dst);
617 : }
618 : // Copy over heights from the succeeding row. Destination heightmap:
619 : // +----------+
620 : // |1111234444|
621 : // |1111234444|
622 : // |5555678888|
623 : // |5555678888| < copied from the row above
624 : // +----------+
625 62 : for (ssize_t j = (destUpperLeftZ + depth) * PATCH_SIZE; j < newMapSize; ++j)
626 : {
627 55 : u16* dst = newHeightmap + j * newMapSize;
628 55 : u16* src = newHeightmap + ((destUpperLeftZ + depth) * PATCH_SIZE - 1) * newMapSize;
629 55 : std::copy_n(src, newMapSize, dst);
630 : }
631 :
632 : // Now build new patches. The same process as for the heightmap.
633 20 : for (ssize_t j = 0; j < depth; ++j)
634 : {
635 36 : for (ssize_t i = 0; i < width; ++i)
636 : {
637 23 : const CPatch& src =
638 23 : m_Patches[(sourceUpperLeftZ + j) * m_MapSizePatches + sourceUpperLeftX + i];
639 23 : CPatch& dst =
640 23 : newPatches[(destUpperLeftZ + j) * size + destUpperLeftX + i];
641 23 : std::copy_n(&src.m_MiniPatches[0][0], PATCH_SIZE * PATCH_SIZE, &dst.m_MiniPatches[0][0]);
642 : }
643 23 : for (ssize_t i = 0; i < destUpperLeftX; ++i)
644 170 : for (ssize_t jPatch = 0; jPatch < PATCH_SIZE; ++jPatch)
645 : {
646 160 : const CMiniPatch& src =
647 160 : newPatches[(destUpperLeftZ + j) * size + destUpperLeftX]
648 : .m_MiniPatches[jPatch][0];
649 2720 : for (ssize_t iPatch = 0; iPatch < PATCH_SIZE; ++iPatch)
650 : {
651 2560 : CMiniPatch& dst =
652 2560 : newPatches[(destUpperLeftZ + j) * size + i]
653 : .m_MiniPatches[jPatch][iPatch];
654 2560 : dst = src;
655 : }
656 : }
657 20 : for (ssize_t i = destUpperLeftX + width; i < size; ++i)
658 : {
659 119 : for (ssize_t jPatch = 0; jPatch < PATCH_SIZE; ++jPatch)
660 : {
661 112 : const CMiniPatch& src =
662 112 : newPatches[(destUpperLeftZ + j) * size + destUpperLeftX + width - 1]
663 : .m_MiniPatches[jPatch][PATCH_SIZE - 1];
664 1904 : for (ssize_t iPatch = 0; iPatch < PATCH_SIZE; ++iPatch)
665 : {
666 1792 : CMiniPatch& dst =
667 1792 : newPatches[(destUpperLeftZ + j) * size + i].m_MiniPatches[jPatch][iPatch];
668 1792 : dst = src;
669 : }
670 : }
671 : }
672 : }
673 :
674 11 : for (ssize_t j = 0; j < destUpperLeftZ; ++j)
675 18 : for (ssize_t i = 0; i < size; ++i)
676 238 : for (ssize_t iPatch = 0; iPatch < PATCH_SIZE; ++iPatch)
677 : {
678 224 : const CMiniPatch& src =
679 224 : newPatches[destUpperLeftZ * size + i].m_MiniPatches[0][iPatch];
680 3808 : for (ssize_t jPatch = 0; jPatch < PATCH_SIZE; ++jPatch)
681 : {
682 3584 : CMiniPatch& dst =
683 3584 : newPatches[j * size + i].m_MiniPatches[jPatch][iPatch];
684 3584 : dst = src;
685 : }
686 : }
687 10 : for (ssize_t j = destUpperLeftZ + depth; j < size; ++j)
688 13 : for (ssize_t i = 0; i < size; ++i)
689 170 : for (ssize_t iPatch = 0; iPatch < PATCH_SIZE; ++iPatch)
690 : {
691 160 : const CMiniPatch& src =
692 160 : newPatches[(destUpperLeftZ + depth - 1) * size + i].m_MiniPatches[0][iPatch];
693 2720 : for (ssize_t jPatch = 0; jPatch < PATCH_SIZE; ++jPatch)
694 : {
695 2560 : CMiniPatch& dst =
696 2560 : newPatches[j * size + i].m_MiniPatches[jPatch][iPatch];
697 2560 : dst = src;
698 : }
699 : }
700 :
701 : // Release all the original data.
702 7 : ReleaseData();
703 :
704 : // Store new data.
705 7 : m_Heightmap = newHeightmap;
706 7 : m_Patches = newPatches;
707 7 : m_MapSize = newMapSize;
708 7 : m_MapSizePatches = size;
709 :
710 : // Initialise all the new patches.
711 7 : InitialisePatches();
712 :
713 : // Initialise mipmap.
714 7 : m_HeightMipmap.Initialize(m_MapSize, m_Heightmap);
715 : }
716 :
717 : ///////////////////////////////////////////////////////////////////////////////
718 : // InitialisePatches: initialise patch data
719 29 : void CTerrain::InitialisePatches()
720 : {
721 112 : for (ssize_t j = 0; j < m_MapSizePatches; j++)
722 : {
723 352 : for (ssize_t i = 0; i < m_MapSizePatches; i++)
724 : {
725 269 : CPatch* patch = GetPatch(i, j); // can't fail
726 269 : patch->Initialize(this, i, j);
727 : }
728 : }
729 29 : }
730 :
731 : ///////////////////////////////////////////////////////////////////////////////
732 : // SetHeightMap: set up a new heightmap from 16-bit source data;
733 : // assumes heightmap matches current terrain size
734 0 : void CTerrain::SetHeightMap(u16* heightmap)
735 : {
736 : // keep a copy of the given heightmap
737 0 : memcpy(m_Heightmap, heightmap, m_MapSize*m_MapSize*sizeof(u16));
738 :
739 : // recalculate patch bounds, invalidate vertices
740 0 : for (ssize_t j = 0; j < m_MapSizePatches; j++)
741 : {
742 0 : for (ssize_t i = 0; i < m_MapSizePatches; i++)
743 : {
744 0 : CPatch* patch = GetPatch(i, j); // can't fail
745 0 : patch->InvalidateBounds();
746 0 : patch->SetDirty(RENDERDATA_UPDATE_VERTICES);
747 : }
748 : }
749 :
750 : // update mipmap
751 0 : m_HeightMipmap.Update(m_Heightmap);
752 0 : }
753 :
754 :
755 : ///////////////////////////////////////////////////////////////////////////////
756 :
757 0 : void CTerrain::MakeDirty(ssize_t i0, ssize_t j0, ssize_t i1, ssize_t j1, int dirtyFlags)
758 : {
759 : // Finds the inclusive limits of the patches that include the specified range of tiles
760 0 : ssize_t pi0 = Clamp<ssize_t>( i0 /PATCH_SIZE, 0, m_MapSizePatches-1);
761 0 : ssize_t pi1 = Clamp<ssize_t>((i1-1)/PATCH_SIZE, 0, m_MapSizePatches-1);
762 0 : ssize_t pj0 = Clamp<ssize_t>( j0 /PATCH_SIZE, 0, m_MapSizePatches-1);
763 0 : ssize_t pj1 = Clamp<ssize_t>((j1-1)/PATCH_SIZE, 0, m_MapSizePatches-1);
764 :
765 0 : for (ssize_t j = pj0; j <= pj1; j++)
766 : {
767 0 : for (ssize_t i = pi0; i <= pi1; i++)
768 : {
769 0 : CPatch* patch = GetPatch(i, j); // can't fail (i,j were clamped)
770 0 : if (dirtyFlags & RENDERDATA_UPDATE_VERTICES)
771 0 : patch->CalcBounds();
772 0 : patch->SetDirty(dirtyFlags);
773 : }
774 : }
775 :
776 0 : if (m_Heightmap)
777 : {
778 0 : m_HeightMipmap.Update(m_Heightmap,
779 0 : Clamp<ssize_t>(i0, 0, m_MapSize - 1),
780 0 : Clamp<ssize_t>(j0, 0, m_MapSize - 1),
781 0 : Clamp<ssize_t>(i1, 1, m_MapSize),
782 0 : Clamp<ssize_t>(j1, 1, m_MapSize)
783 : );
784 : }
785 0 : }
786 :
787 64 : void CTerrain::MakeDirty(int dirtyFlags)
788 : {
789 320 : for (ssize_t j = 0; j < m_MapSizePatches; j++)
790 : {
791 1280 : for (ssize_t i = 0; i < m_MapSizePatches; i++)
792 : {
793 1024 : CPatch* patch = GetPatch(i, j); // can't fail
794 1024 : if (dirtyFlags & RENDERDATA_UPDATE_VERTICES)
795 1024 : patch->CalcBounds();
796 1024 : patch->SetDirty(dirtyFlags);
797 : }
798 : }
799 :
800 64 : if (m_Heightmap)
801 64 : m_HeightMipmap.Update(m_Heightmap);
802 64 : }
803 :
804 0 : CBoundingBoxAligned CTerrain::GetVertexesBound(ssize_t i0, ssize_t j0, ssize_t i1, ssize_t j1)
805 : {
806 0 : i0 = Clamp<ssize_t>(i0, 0, m_MapSize - 1);
807 0 : j0 = Clamp<ssize_t>(j0, 0, m_MapSize - 1);
808 0 : i1 = Clamp<ssize_t>(i1, 0, m_MapSize - 1);
809 0 : j1 = Clamp<ssize_t>(j1, 0, m_MapSize - 1);
810 :
811 0 : u16 minH = 65535;
812 0 : u16 maxH = 0;
813 :
814 0 : for (ssize_t j = j0; j <= j1; ++j)
815 : {
816 0 : for (ssize_t i = i0; i <= i1; ++i)
817 : {
818 0 : minH = std::min(minH, m_Heightmap[j*m_MapSize + i]);
819 0 : maxH = std::max(maxH, m_Heightmap[j*m_MapSize + i]);
820 : }
821 : }
822 :
823 0 : CBoundingBoxAligned bound;
824 0 : bound[0].X = (float)(i0*TERRAIN_TILE_SIZE);
825 0 : bound[0].Y = (float)(minH*HEIGHT_SCALE);
826 0 : bound[0].Z = (float)(j0*TERRAIN_TILE_SIZE);
827 0 : bound[1].X = (float)(i1*TERRAIN_TILE_SIZE);
828 0 : bound[1].Y = (float)(maxH*HEIGHT_SCALE);
829 0 : bound[1].Z = (float)(j1*TERRAIN_TILE_SIZE);
830 0 : return bound;
831 3 : }
|
