Line data Source code
1 : /* Copyright (C) 2021 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 : /*
19 : * Determine intersection of rays with a heightfield.
20 : */
21 :
22 : #include "precompiled.h"
23 :
24 : #include "HFTracer.h"
25 :
26 : #include "graphics/Patch.h"
27 : #include "graphics/Terrain.h"
28 : #include "maths/BoundingBoxAligned.h"
29 : #include "maths/MathUtil.h"
30 : #include "maths/Vector3D.h"
31 :
32 : #include <cfloat>
33 :
34 : // To cope well with points that are slightly off the edge of the map,
35 : // we act as if there's an N-tile margin around the edges of the heightfield.
36 : // (N shouldn't be too huge else it'll hurt performance a little when
37 : // RayIntersect loops through it all.)
38 : // CTerrain::CalcPosition implements clamp-to-edge behaviour so the tracer
39 : // will have that behaviour.
40 : static const int MARGIN_SIZE = 64;
41 :
42 : ///////////////////////////////////////////////////////////////////////////////
43 : // CHFTracer constructor
44 0 : CHFTracer::CHFTracer(CTerrain *pTerrain):
45 : m_pTerrain(pTerrain),
46 0 : m_Heightfield(m_pTerrain->GetHeightMap()),
47 0 : m_MapSize(m_pTerrain->GetVerticesPerSide()),
48 : m_CellSize((float)TERRAIN_TILE_SIZE),
49 0 : m_HeightScale(HEIGHT_SCALE)
50 : {
51 0 : }
52 :
53 :
54 : ///////////////////////////////////////////////////////////////////////////////
55 : // RayTriIntersect: intersect a ray with triangle defined by vertices
56 : // v0,v1,v2; return true if ray hits triangle at distance less than dist,
57 : // or false otherwise
58 0 : static bool RayTriIntersect(const CVector3D& v0, const CVector3D& v1, const CVector3D& v2,
59 : const CVector3D& origin, const CVector3D& dir, float& dist)
60 : {
61 0 : const float EPSILON=0.00001f;
62 :
63 : // calculate edge vectors
64 0 : CVector3D edge0=v1-v0;
65 0 : CVector3D edge1=v2-v0;
66 :
67 : // begin calculating determinant - also used to calculate U parameter
68 0 : CVector3D pvec=dir.Cross(edge1);
69 :
70 : // if determinant is near zero, ray lies in plane of triangle
71 0 : float det = edge0.Dot(pvec);
72 0 : if (fabs(det)<EPSILON)
73 0 : return false;
74 :
75 0 : float inv_det = 1.0f/det;
76 :
77 : // calculate vector from vert0 to ray origin
78 0 : CVector3D tvec=origin-v0;
79 :
80 : // calculate U parameter, test bounds
81 0 : float u=tvec.Dot(pvec)*inv_det;
82 0 : if (u<-0.01f || u>1.01f)
83 0 : return false;
84 :
85 : // prepare to test V parameter
86 0 : CVector3D qvec=tvec.Cross(edge0);
87 :
88 : // calculate V parameter and test bounds
89 0 : float v=dir.Dot(qvec)*inv_det;
90 0 : if (v<0.0f || u+v>1.0f)
91 0 : return false;
92 :
93 : // calculate distance to intersection point from ray origin
94 0 : float d=edge1.Dot(qvec)*inv_det;
95 0 : if (d>=0 && d<dist) {
96 0 : dist=d;
97 0 : return true;
98 : }
99 :
100 0 : return false;
101 : }
102 :
103 : ///////////////////////////////////////////////////////////////////////////////
104 : // CellIntersect: test if ray intersects either of the triangles in the given
105 : // cell - return hit result, and distance to hit, if hit occurred
106 0 : bool CHFTracer::CellIntersect(int cx, int cz, const CVector3D& origin, const CVector3D& dir, float& dist) const
107 : {
108 0 : bool res=false;
109 :
110 : // get vertices for this cell
111 0 : CVector3D vpos[4];
112 0 : m_pTerrain->CalcPosition(cx,cz,vpos[0]);
113 0 : m_pTerrain->CalcPosition(cx+1,cz,vpos[1]);
114 0 : m_pTerrain->CalcPosition(cx+1,cz+1,vpos[2]);
115 0 : m_pTerrain->CalcPosition(cx,cz+1,vpos[3]);
116 :
117 0 : dist=1.0e30f;
118 0 : if (RayTriIntersect(vpos[0],vpos[1],vpos[2],origin,dir,dist)) {
119 0 : res=true;
120 : }
121 :
122 0 : if (RayTriIntersect(vpos[0],vpos[2],vpos[3],origin,dir,dist)) {
123 0 : res=true;
124 : }
125 :
126 0 : return res;
127 : }
128 :
129 : ///////////////////////////////////////////////////////////////////////////////
130 : // RayIntersect: intersect ray with this heightfield; return true if
131 : // intersection occurs (and fill in grid coordinates of intersection), or false
132 : // otherwise
133 0 : bool CHFTracer::RayIntersect(const CVector3D& origin, const CVector3D& dir, int& x, int& z, CVector3D& ipt) const
134 : {
135 : // If the map is empty (which should never happen),
136 : // return early before we crash when reading zero-sized heightmaps
137 0 : if (!m_MapSize)
138 : {
139 0 : debug_warn(L"CHFTracer::RayIntersect called with zero-size map");
140 0 : return false;
141 : }
142 :
143 : // intersect first against bounding box
144 0 : CBoundingBoxAligned bound;
145 0 : bound[0] = CVector3D(-MARGIN_SIZE * m_CellSize, 0, -MARGIN_SIZE * m_CellSize);
146 0 : bound[1] = CVector3D((m_MapSize + MARGIN_SIZE) * m_CellSize, 65535 * m_HeightScale, (m_MapSize + MARGIN_SIZE) * m_CellSize);
147 :
148 : float tmin,tmax;
149 0 : if (!bound.RayIntersect(origin,dir,tmin,tmax)) {
150 : // ray missed world bounds; no intersection
151 0 : return false;
152 : }
153 :
154 : // project origin onto grid, if necessary, to get starting point for traversal
155 0 : CVector3D traversalPt;
156 0 : if (tmin>0) {
157 0 : traversalPt=origin+dir*tmin;
158 : } else {
159 0 : traversalPt=origin;
160 : }
161 :
162 : // setup traversal variables
163 0 : int sx=dir.X<0 ? -1 : 1;
164 0 : int sz=dir.Z<0 ? -1 : 1;
165 :
166 0 : float invCellSize=1.0f/float(m_CellSize);
167 :
168 0 : float fcx=traversalPt.X*invCellSize;
169 0 : int cx=(int)floor(fcx);
170 :
171 0 : float fcz=traversalPt.Z*invCellSize;
172 0 : int cz=(int)floor(fcz);
173 :
174 0 : float invdx = 1.0e20f;
175 0 : float invdz = 1.0e20f;
176 :
177 0 : if (fabs(dir.X) > 1.0e-20)
178 0 : invdx = float(1.0/fabs(dir.X));
179 0 : if (fabs(dir.Z) > 1.0e-20)
180 0 : invdz = float(1.0/fabs(dir.Z));
181 :
182 0 : do {
183 : // test current cell
184 0 : if (cx >= -MARGIN_SIZE && cx < int(m_MapSize + MARGIN_SIZE - 1) && cz >= -MARGIN_SIZE && cz < int(m_MapSize + MARGIN_SIZE - 1))
185 : {
186 : float dist;
187 :
188 0 : if (CellIntersect(cx,cz,origin,dir,dist)) {
189 0 : x=cx;
190 0 : z=cz;
191 0 : ipt=origin+dir*dist;
192 0 : return true;
193 0 : }
194 : }
195 : else
196 : {
197 : // Degenerate case: y close to zero
198 : // catch travelling off the map
199 0 : if ((cx < -MARGIN_SIZE) && (sx < 0))
200 0 : return false;
201 0 : if ((cx >= (int)(m_MapSize + MARGIN_SIZE - 1)) && (sx > 0))
202 0 : return false;
203 0 : if ((cz < -MARGIN_SIZE) && (sz < 0))
204 0 : return false;
205 0 : if ((cz >= (int)(m_MapSize + MARGIN_SIZE - 1)) && (sz > 0))
206 0 : return false;
207 : }
208 :
209 : // get coords of current cell
210 0 : fcx=traversalPt.X*invCellSize;
211 0 : fcz=traversalPt.Z*invCellSize;
212 :
213 : // get distance to next cell in x,z
214 0 : float dx=(sx==-1) ? fcx-float(cx) : 1-(fcx-float(cx));
215 0 : dx*=invdx;
216 0 : float dz=(sz==-1) ? fcz-float(cz) : 1-(fcz-float(cz));
217 0 : dz*=invdz;
218 :
219 : // advance ..
220 : float dist;
221 0 : if (dx<dz) {
222 0 : cx+=sx;
223 0 : dist=dx;
224 : } else {
225 0 : cz+=sz;
226 0 : dist=dz;
227 : }
228 :
229 0 : traversalPt+=dir*dist;
230 0 : } while (traversalPt.Y>=0);
231 :
232 : // fell off end of heightmap with no intersection; return a miss
233 0 : return false;
234 : }
235 :
236 0 : static bool TestTile(u16* heightmap, int stride, int i, int j, const CVector3D& pos, const CVector3D& dir, CVector3D& isct)
237 : {
238 0 : u16 y00 = heightmap[i + j*stride];
239 0 : u16 y10 = heightmap[i+1 + j*stride];
240 0 : u16 y01 = heightmap[i + (j+1)*stride];
241 0 : u16 y11 = heightmap[i+1 + (j+1)*stride];
242 :
243 0 : CVector3D p00( i * TERRAIN_TILE_SIZE, y00 * HEIGHT_SCALE, j * TERRAIN_TILE_SIZE);
244 0 : CVector3D p10((i+1) * TERRAIN_TILE_SIZE, y10 * HEIGHT_SCALE, j * TERRAIN_TILE_SIZE);
245 0 : CVector3D p01( i * TERRAIN_TILE_SIZE, y01 * HEIGHT_SCALE, (j+1) * TERRAIN_TILE_SIZE);
246 0 : CVector3D p11((i+1) * TERRAIN_TILE_SIZE, y11 * HEIGHT_SCALE, (j+1) * TERRAIN_TILE_SIZE);
247 :
248 0 : int mid1 = y00+y11;
249 0 : int mid2 = y01+y10;
250 0 : int triDir = (mid1 < mid2);
251 :
252 0 : float dist = FLT_MAX;
253 :
254 0 : if (triDir)
255 : {
256 0 : if (RayTriIntersect(p00, p10, p01, pos, dir, dist) || // lower-left triangle
257 0 : RayTriIntersect(p11, p01, p10, pos, dir, dist)) // upper-right triangle
258 : {
259 0 : isct = pos + dir * dist;
260 0 : return true;
261 : }
262 : }
263 : else
264 : {
265 0 : if (RayTriIntersect(p00, p11, p01, pos, dir, dist) || // upper-left triangle
266 0 : RayTriIntersect(p00, p10, p11, pos, dir, dist)) // lower-right triangle
267 : {
268 0 : isct = pos + dir * dist;
269 0 : return true;
270 : }
271 : }
272 0 : return false;
273 : }
274 :
275 0 : bool CHFTracer::PatchRayIntersect(CPatch* patch, const CVector3D& origin, const CVector3D& dir, CVector3D* out)
276 : {
277 : // (TODO: This largely duplicates RayIntersect - some refactoring might be
278 : // nice in the future.)
279 :
280 : // General approach:
281 : // Given the ray defined by origin + dir * t, we increase t until it
282 : // enters the patch's bounding box. The x,z coordinates identify which
283 : // tile it is currently above/below. Do an intersection test vs the tile's
284 : // two triangles. If it doesn't hit, do a 2D line rasterisation to find
285 : // the next tiles the ray will pass through, and test each of them.
286 :
287 : // Start by jumping to the point where the ray enters the bounding box
288 0 : CBoundingBoxAligned bound = patch->GetWorldBounds();
289 : float tmin, tmax;
290 0 : if (!bound.RayIntersect(origin, dir, tmin, tmax))
291 : {
292 : // Ray missed patch; no intersection
293 0 : return false;
294 : }
295 :
296 0 : int heightmapStride = patch->m_Parent->GetVerticesPerSide();
297 :
298 : // Get heightmap, offset to start at this patch
299 0 : u16* heightmap = patch->m_Parent->GetHeightMap() +
300 0 : patch->m_X * PATCH_SIZE +
301 0 : patch->m_Z * PATCH_SIZE * heightmapStride;
302 :
303 : // Get patch-space position of ray origin and bbox entry point
304 : CVector3D patchPos(
305 0 : patch->m_X * PATCH_SIZE * TERRAIN_TILE_SIZE,
306 : 0.0f,
307 0 : patch->m_Z * PATCH_SIZE * TERRAIN_TILE_SIZE);
308 0 : CVector3D originPatch = origin - patchPos;
309 0 : CVector3D entryPatch = originPatch + dir * tmin;
310 :
311 : // We want to do a simple 2D line rasterisation (with the 3D ray projected
312 : // down onto the Y plane). That will tell us which cells are intersected
313 : // in 2D dimensions, then we can do a more precise 3D intersection test.
314 : //
315 : // WLOG, assume the ray has direction dir.x > 0, dir.z > 0, and starts in
316 : // cell (i,j). The next cell intersecting the line must be either (i+1,j)
317 : // or (i,j+1). To tell which, just check whether the point (i+1,j+1) is
318 : // above or below the ray. Advance into that cell and repeat.
319 : //
320 : // (If the ray passes precisely through (i+1,j+1), we can pick either.
321 : // If the ray is parallel to Y, only the first cell matters, then we can
322 : // carry on rasterising in any direction (a bit of a waste of time but
323 : // should be extremely rare, and it's safe and simple).)
324 :
325 : // Work out which tile we're starting in
326 0 : int i = Clamp<int>(entryPatch.X / TERRAIN_TILE_SIZE, 0, PATCH_SIZE - 1);
327 0 : int j = Clamp<int>(entryPatch.Z / TERRAIN_TILE_SIZE, 0, PATCH_SIZE - 1);
328 :
329 : // Work out which direction the ray is going in
330 0 : int di = (dir.X >= 0 ? 1 : 0);
331 0 : int dj = (dir.Z >= 0 ? 1 : 0);
332 :
333 0 : do
334 : {
335 0 : CVector3D isct;
336 0 : if (TestTile(heightmap, heightmapStride, i, j, originPatch, dir, isct))
337 : {
338 0 : if (out)
339 0 : *out = isct + patchPos;
340 0 : return true;
341 : }
342 :
343 : // Get the vertex between the two possible next cells
344 0 : float nx = (i + di) * (int)TERRAIN_TILE_SIZE;
345 0 : float nz = (j + dj) * (int)TERRAIN_TILE_SIZE;
346 :
347 : // Test which side of the ray the vertex is on, and advance into the
348 : // appropriate cell, using a test that works for all 4 combinations
349 : // of di,dj
350 0 : float dot = dir.Z * (nx - originPatch.X) - dir.X * (nz - originPatch.Z);
351 0 : if ((di == dj) == (dot > 0.0f))
352 0 : j += dj*2-1;
353 : else
354 0 : i += di*2-1;
355 : }
356 0 : while (i >= 0 && j >= 0 && i < PATCH_SIZE && j < PATCH_SIZE);
357 :
358 : // Ran off the edge of the patch, so no intersection
359 0 : return false;
360 3 : }
|
