Line data Source code
1 : /* Copyright (C) 2023 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 "SilhouetteRenderer.h"
21 :
22 : #include "graphics/Camera.h"
23 : #include "graphics/HFTracer.h"
24 : #include "graphics/Model.h"
25 : #include "graphics/Patch.h"
26 : #include "graphics/ShaderManager.h"
27 : #include "maths/MathUtil.h"
28 : #include "ps/CStrInternStatic.h"
29 : #include "ps/Profile.h"
30 : #include "renderer/DebugRenderer.h"
31 : #include "renderer/Renderer.h"
32 : #include "renderer/Scene.h"
33 :
34 : #include <cfloat>
35 :
36 : extern int g_xres, g_yres;
37 :
38 : // For debugging
39 : static const bool g_DisablePreciseIntersections = false;
40 :
41 6 : SilhouetteRenderer::SilhouetteRenderer()
42 : {
43 6 : m_DebugEnabled = false;
44 6 : }
45 :
46 0 : void SilhouetteRenderer::AddOccluder(CPatch* patch)
47 : {
48 0 : m_SubmittedPatchOccluders.push_back(patch);
49 0 : }
50 :
51 0 : void SilhouetteRenderer::AddOccluder(CModel* model)
52 : {
53 0 : m_SubmittedModelOccluders.push_back(model);
54 0 : }
55 :
56 0 : void SilhouetteRenderer::AddCaster(CModel* model)
57 : {
58 0 : m_SubmittedModelCasters.push_back(model);
59 0 : }
60 :
61 : /*
62 : * Silhouettes are the solid-colored versions of units that are rendered when
63 : * standing behind a building or terrain, so the player won't lose them.
64 : *
65 : * The rendering is done in CRenderer::RenderSilhouettes, by rendering the
66 : * units (silhouette casters) and buildings/terrain (silhouette occluders)
67 : * in an extra pass using depth and stencil buffers. It's very inefficient to
68 : * render those objects when they're not actually going to contribute to a
69 : * silhouette.
70 : *
71 : * This class is responsible for finding the subset of casters/occluders
72 : * that might contribute to a silhouette and will need to be rendered.
73 : *
74 : * The algorithm is largely based on sweep-and-prune for detecting intersection
75 : * along a single axis:
76 : *
77 : * First we compute the 2D screen-space bounding box of every occluder, and
78 : * their minimum distance from the camera. We also compute the screen-space
79 : * position of each caster (approximating them as points, which is not perfect
80 : * but almost always good enough).
81 : *
82 : * We split each occluder's screen-space bounds into a left ('in') edge and
83 : * right ('out') edge. We put those edges plus the caster points into a list,
84 : * and sort by x coordinate.
85 : *
86 : * Then we walk through the list, maintaining an active set of occluders.
87 : * An 'in' edge will add an occluder to the set, an 'out' edge will remove it.
88 : * When we reach a caster point, the active set contains all the occluders that
89 : * intersect it in x. We do a quick test of y and depth coordinates against
90 : * each occluder in the set. If they pass that test, we do a more precise ray
91 : * vs bounding box test (for model occluders) or ray vs patch (for terrain
92 : * occluders) to see if we really need to render that caster and occluder.
93 : *
94 : * Performance relies on the active set being quite small. Given the game's
95 : * typical occluder sizes and camera angles, this works out okay.
96 : *
97 : * We have to do precise ray/patch intersection tests for terrain, because
98 : * if we just used the patch's bounding box, pretty much every unit would
99 : * be seen as intersecting the patch it's standing on.
100 : *
101 : * We store screen-space coordinates as 14-bit integers (0..16383) because
102 : * that lets us pack and sort the edge/point list efficiently.
103 : */
104 :
105 : static const u16 g_MaxCoord = 1 << 14;
106 : static const u16 g_HalfMaxCoord = g_MaxCoord / 2;
107 :
108 : struct Occluder
109 : {
110 : CRenderableObject* renderable;
111 : bool isPatch;
112 : u16 x0, y0, x1, y1;
113 : float z;
114 : bool rendered;
115 : };
116 :
117 : struct Caster
118 : {
119 : CModel* model;
120 : u16 x, y;
121 : float z;
122 : bool rendered;
123 : };
124 :
125 : enum { EDGE_IN, EDGE_OUT, POINT };
126 :
127 : // Entry is essentially:
128 : // struct Entry {
129 : // u16 id; // index into occluders array
130 : // u16 type : 2;
131 : // u16 x : 14;
132 : // };
133 : // where x is in the most significant bits, so that sorting as a uint32_t
134 : // is the same as sorting by x. To avoid worrying about endianness and the
135 : // compiler's ability to handle bitfields efficiently, we use uint32_t instead
136 : // of the actual struct.
137 :
138 : typedef uint32_t Entry;
139 :
140 0 : static Entry EntryCreate(int type, u16 id, u16 x) { return (x << 18) | (type << 16) | id; }
141 0 : static int EntryGetId(Entry e) { return e & 0xffff; }
142 0 : static int EntryGetType(Entry e) { return (e >> 16) & 3; }
143 :
144 0 : struct ActiveList
145 : {
146 : std::vector<u16> m_Ids;
147 :
148 0 : void Add(u16 id)
149 : {
150 0 : m_Ids.push_back(id);
151 0 : }
152 :
153 0 : void Remove(u16 id)
154 : {
155 0 : ssize_t sz = m_Ids.size();
156 0 : for (ssize_t i = sz-1; i >= 0; --i)
157 : {
158 0 : if (m_Ids[i] == id)
159 : {
160 0 : m_Ids[i] = m_Ids[sz-1];
161 0 : m_Ids.pop_back();
162 0 : return;
163 : }
164 : }
165 0 : debug_warn(L"Failed to find id");
166 : }
167 : };
168 :
169 0 : static void ComputeScreenBounds(Occluder& occluder, const CBoundingBoxAligned& bounds, CMatrix3D& proj)
170 : {
171 0 : u16 x0 = std::numeric_limits<u16>::max();
172 0 : u16 y0 = std::numeric_limits<u16>::max();
173 0 : u16 x1 = std::numeric_limits<u16>::min();
174 0 : u16 y1 = std::numeric_limits<u16>::min();
175 0 : float z0 = std::numeric_limits<float>::max();
176 0 : for (size_t ix = 0; ix <= 1; ++ix)
177 : {
178 0 : for (size_t iy = 0; iy <= 1; ++iy)
179 : {
180 0 : for (size_t iz = 0; iz <= 1; ++iz)
181 : {
182 0 : CVector4D svec = proj.Transform(CVector4D(bounds[ix].X, bounds[iy].Y, bounds[iz].Z, 1.0f));
183 0 : x0 = std::min(x0, static_cast<u16>(g_HalfMaxCoord + static_cast<u16>(g_HalfMaxCoord * svec.X / svec.W)));
184 0 : y0 = std::min(y0, static_cast<u16>(g_HalfMaxCoord + static_cast<u16>(g_HalfMaxCoord * svec.Y / svec.W)));
185 0 : x1 = std::max(x1, static_cast<u16>(g_HalfMaxCoord + static_cast<u16>(g_HalfMaxCoord * svec.X / svec.W)));
186 0 : y1 = std::max(y1, static_cast<u16>(g_HalfMaxCoord + static_cast<u16>(g_HalfMaxCoord * svec.Y / svec.W)));
187 0 : z0 = std::min(z0, svec.Z / svec.W);
188 : }
189 : }
190 : }
191 : // TODO: there must be a quicker way to do this than to test every vertex,
192 : // given the symmetry of the bounding box
193 :
194 0 : occluder.x0 = Clamp(x0, std::numeric_limits<u16>::min(), static_cast<u16>(g_MaxCoord - 1));
195 0 : occluder.y0 = Clamp(y0, std::numeric_limits<u16>::min(), static_cast<u16>(g_MaxCoord - 1));
196 0 : occluder.x1 = Clamp(x1, std::numeric_limits<u16>::min(), static_cast<u16>(g_MaxCoord - 1));
197 0 : occluder.y1 = Clamp(y1, std::numeric_limits<u16>::min(), static_cast<u16>(g_MaxCoord - 1));
198 0 : occluder.z = z0;
199 0 : }
200 :
201 0 : static void ComputeScreenPos(Caster& caster, const CVector3D& pos, CMatrix3D& proj)
202 : {
203 0 : CVector4D svec = proj.Transform(CVector4D(pos.X, pos.Y, pos.Z, 1.0f));
204 0 : u16 x = g_HalfMaxCoord + static_cast<int>(g_HalfMaxCoord * svec.X / svec.W);
205 0 : u16 y = g_HalfMaxCoord + static_cast<int>(g_HalfMaxCoord * svec.Y / svec.W);
206 0 : caster.x = Clamp(x, std::numeric_limits<u16>::min(), static_cast<u16>(g_MaxCoord - 1));
207 0 : caster.y = Clamp(y, std::numeric_limits<u16>::min(), static_cast<u16>(g_MaxCoord - 1));
208 0 : caster.z = svec.Z / svec.W;
209 0 : }
210 :
211 0 : void SilhouetteRenderer::ComputeSubmissions(const CCamera& camera)
212 : {
213 0 : PROFILE3("compute silhouettes");
214 :
215 0 : m_DebugBounds.clear();
216 0 : m_DebugRects.clear();
217 0 : m_DebugSpheres.clear();
218 :
219 0 : m_VisiblePatchOccluders.clear();
220 0 : m_VisibleModelOccluders.clear();
221 0 : m_VisibleModelCasters.clear();
222 :
223 0 : std::vector<Occluder> occluders;
224 0 : std::vector<Caster> casters;
225 0 : std::vector<Entry> entries;
226 :
227 0 : occluders.reserve(m_SubmittedModelOccluders.size() + m_SubmittedPatchOccluders.size());
228 0 : casters.reserve(m_SubmittedModelCasters.size());
229 0 : entries.reserve((m_SubmittedModelOccluders.size() + m_SubmittedPatchOccluders.size()) * 2 + m_SubmittedModelCasters.size());
230 :
231 0 : CMatrix3D proj = camera.GetViewProjection();
232 :
233 : // Bump the positions of unit casters upwards a bit, so they're not always
234 : // detected as intersecting the terrain they're standing on
235 0 : CVector3D posOffset(0.0f, 0.1f, 0.0f);
236 :
237 : #if 0
238 : // For debugging ray-patch intersections - casts a ton of rays and draws
239 : // a sphere where they intersect
240 : for (int y = 0; y < g_yres; y += 8)
241 : {
242 : for (int x = 0; x < g_xres; x += 8)
243 : {
244 : SOverlaySphere sphere;
245 : sphere.m_Color = CColor(1, 0, 0, 1);
246 : sphere.m_Radius = 0.25f;
247 : sphere.m_Center = camera.GetWorldCoordinates(x, y, false);
248 :
249 : CVector3D origin, dir;
250 : camera.BuildCameraRay(x, y, origin, dir);
251 :
252 : for (size_t i = 0; i < m_SubmittedPatchOccluders.size(); ++i)
253 : {
254 : CPatch* occluder = m_SubmittedPatchOccluders[i];
255 : if (CHFTracer::PatchRayIntersect(occluder, origin, dir, &sphere.m_Center))
256 : sphere.m_Color = CColor(0, 0, 1, 1);
257 : }
258 : m_DebugSpheres.push_back(sphere);
259 : }
260 : }
261 : #endif
262 :
263 : {
264 0 : PROFILE("compute bounds");
265 :
266 0 : for (size_t i = 0; i < m_SubmittedModelOccluders.size(); ++i)
267 : {
268 0 : CModel* occluder = m_SubmittedModelOccluders[i];
269 :
270 : Occluder d;
271 0 : d.renderable = occluder;
272 0 : d.isPatch = false;
273 0 : d.rendered = false;
274 0 : ComputeScreenBounds(d, occluder->GetWorldBounds(), proj);
275 :
276 : // Skip zero-sized occluders, so we don't need to worry about EDGE_OUT
277 : // getting sorted before EDGE_IN
278 0 : if (d.x0 == d.x1 || d.y0 == d.y1)
279 0 : continue;
280 :
281 0 : u16 id = static_cast<u16>(occluders.size());
282 0 : occluders.push_back(d);
283 :
284 0 : entries.push_back(EntryCreate(EDGE_IN, id, d.x0));
285 0 : entries.push_back(EntryCreate(EDGE_OUT, id, d.x1));
286 : }
287 :
288 0 : for (size_t i = 0; i < m_SubmittedPatchOccluders.size(); ++i)
289 : {
290 0 : CPatch* occluder = m_SubmittedPatchOccluders[i];
291 :
292 : Occluder d;
293 0 : d.renderable = occluder;
294 0 : d.isPatch = true;
295 0 : d.rendered = false;
296 0 : ComputeScreenBounds(d, occluder->GetWorldBounds(), proj);
297 :
298 : // Skip zero-sized occluders
299 0 : if (d.x0 == d.x1 || d.y0 == d.y1)
300 0 : continue;
301 :
302 0 : u16 id = static_cast<u16>(occluders.size());
303 0 : occluders.push_back(d);
304 :
305 0 : entries.push_back(EntryCreate(EDGE_IN, id, d.x0));
306 0 : entries.push_back(EntryCreate(EDGE_OUT, id, d.x1));
307 : }
308 :
309 0 : for (size_t i = 0; i < m_SubmittedModelCasters.size(); ++i)
310 : {
311 0 : CModel* model = m_SubmittedModelCasters[i];
312 0 : CVector3D pos = model->GetTransform().GetTranslation() + posOffset;
313 :
314 : Caster d;
315 0 : d.model = model;
316 0 : d.rendered = false;
317 0 : ComputeScreenPos(d, pos, proj);
318 :
319 0 : u16 id = static_cast<u16>(casters.size());
320 0 : casters.push_back(d);
321 :
322 0 : entries.push_back(EntryCreate(POINT, id, d.x));
323 : }
324 : }
325 :
326 : // Make sure the u16 id didn't overflow
327 0 : ENSURE(occluders.size() < 65536 && casters.size() < 65536);
328 :
329 : {
330 0 : PROFILE("sorting");
331 0 : std::sort(entries.begin(), entries.end());
332 : }
333 :
334 : {
335 0 : PROFILE("sweeping");
336 :
337 0 : ActiveList active;
338 0 : CVector3D cameraPos = camera.GetOrientation().GetTranslation();
339 :
340 0 : for (size_t i = 0; i < entries.size(); ++i)
341 : {
342 0 : Entry e = entries[i];
343 0 : int type = EntryGetType(e);
344 0 : u16 id = EntryGetId(e);
345 0 : if (type == EDGE_IN)
346 0 : active.Add(id);
347 0 : else if (type == EDGE_OUT)
348 0 : active.Remove(id);
349 : else
350 : {
351 0 : Caster& caster = casters[id];
352 0 : for (size_t j = 0; j < active.m_Ids.size(); ++j)
353 : {
354 0 : Occluder& occluder = occluders[active.m_Ids[j]];
355 :
356 0 : if (caster.y < occluder.y0 || caster.y > occluder.y1)
357 0 : continue;
358 :
359 0 : if (caster.z < occluder.z)
360 0 : continue;
361 :
362 : // No point checking further if both are already being rendered
363 0 : if (caster.rendered && occluder.rendered)
364 0 : continue;
365 :
366 : if (!g_DisablePreciseIntersections)
367 : {
368 0 : CVector3D pos = caster.model->GetTransform().GetTranslation() + posOffset;
369 0 : if (occluder.isPatch)
370 : {
371 0 : CPatch* patch = static_cast<CPatch*>(occluder.renderable);
372 0 : if (!CHFTracer::PatchRayIntersect(patch, pos, cameraPos - pos, NULL))
373 0 : continue;
374 : }
375 : else
376 : {
377 : float tmin, tmax;
378 0 : if (!occluder.renderable->GetWorldBounds().RayIntersect(pos, cameraPos - pos, tmin, tmax))
379 0 : continue;
380 : }
381 : }
382 :
383 0 : caster.rendered = true;
384 0 : occluder.rendered = true;
385 : }
386 : }
387 : }
388 : }
389 :
390 0 : if (m_DebugEnabled)
391 : {
392 0 : for (size_t i = 0; i < occluders.size(); ++i)
393 : {
394 0 : DebugRect r;
395 0 : r.color = occluders[i].rendered ? CColor(1.0f, 1.0f, 0.0f, 1.0f) : CColor(0.2f, 0.2f, 0.0f, 1.0f);
396 0 : r.x0 = occluders[i].x0;
397 0 : r.y0 = occluders[i].y0;
398 0 : r.x1 = occluders[i].x1;
399 0 : r.y1 = occluders[i].y1;
400 0 : m_DebugRects.push_back(r);
401 :
402 0 : DebugBounds b;
403 0 : b.color = r.color;
404 0 : b.bounds = occluders[i].renderable->GetWorldBounds();
405 0 : m_DebugBounds.push_back(b);
406 : }
407 : }
408 :
409 0 : for (size_t i = 0; i < occluders.size(); ++i)
410 : {
411 0 : if (occluders[i].rendered)
412 : {
413 0 : if (occluders[i].isPatch)
414 0 : m_VisiblePatchOccluders.push_back(static_cast<CPatch*>(occluders[i].renderable));
415 : else
416 0 : m_VisibleModelOccluders.push_back(static_cast<CModel*>(occluders[i].renderable));
417 : }
418 : }
419 :
420 0 : for (size_t i = 0; i < casters.size(); ++i)
421 0 : if (casters[i].rendered)
422 0 : m_VisibleModelCasters.push_back(casters[i].model);
423 0 : }
424 :
425 0 : void SilhouetteRenderer::RenderSubmitOverlays(SceneCollector& collector)
426 : {
427 0 : for (size_t i = 0; i < m_DebugSpheres.size(); i++)
428 0 : collector.Submit(&m_DebugSpheres[i]);
429 0 : }
430 :
431 0 : void SilhouetteRenderer::RenderSubmitOccluders(SceneCollector& collector)
432 : {
433 0 : for (size_t i = 0; i < m_VisiblePatchOccluders.size(); ++i)
434 0 : collector.Submit(m_VisiblePatchOccluders[i]);
435 :
436 0 : for (size_t i = 0; i < m_VisibleModelOccluders.size(); ++i)
437 0 : collector.SubmitNonRecursive(m_VisibleModelOccluders[i]);
438 0 : }
439 :
440 0 : void SilhouetteRenderer::RenderSubmitCasters(SceneCollector& collector)
441 : {
442 0 : for (size_t i = 0; i < m_VisibleModelCasters.size(); ++i)
443 0 : collector.SubmitNonRecursive(m_VisibleModelCasters[i]);
444 0 : }
445 :
446 0 : void SilhouetteRenderer::RenderDebugBounds(
447 : Renderer::Backend::IDeviceCommandContext* UNUSED(deviceCommandContext))
448 : {
449 0 : if (m_DebugBounds.empty())
450 0 : return;
451 :
452 0 : for (size_t i = 0; i < m_DebugBounds.size(); ++i)
453 0 : g_Renderer.GetDebugRenderer().DrawBoundingBox(m_DebugBounds[i].bounds, m_DebugBounds[i].color, true);
454 : }
455 :
456 0 : void SilhouetteRenderer::RenderDebugOverlays(
457 : Renderer::Backend::IDeviceCommandContext* deviceCommandContext)
458 : {
459 0 : if (m_DebugRects.empty())
460 0 : return;
461 :
462 : // TODO: use CCanvas2D for drawing rects.
463 0 : CMatrix3D m;
464 0 : m.SetIdentity();
465 0 : m.Scale(1.0f, -1.f, 1.0f);
466 0 : m.Translate(0.0f, (float)g_yres, -1000.0f);
467 :
468 0 : CMatrix3D proj;
469 0 : proj.SetOrtho(0.f, g_MaxCoord, 0.f, g_MaxCoord, -1.f, 1000.f);
470 0 : m = proj * m;
471 :
472 0 : if (!m_ShaderTech)
473 : {
474 0 : m_ShaderTech = g_Renderer.GetShaderManager().LoadEffect(
475 : str_solid, {},
476 0 : [](Renderer::Backend::SGraphicsPipelineStateDesc& pipelineStateDesc)
477 : {
478 0 : pipelineStateDesc.rasterizationState.polygonMode = Renderer::Backend::PolygonMode::LINE;
479 0 : pipelineStateDesc.rasterizationState.cullMode = Renderer::Backend::CullMode::NONE;
480 0 : });
481 :
482 0 : const std::array<Renderer::Backend::SVertexAttributeFormat, 1> attributes{{
483 : {Renderer::Backend::VertexAttributeStream::POSITION,
484 : Renderer::Backend::Format::R32G32_SFLOAT, 0, sizeof(float) * 2,
485 : Renderer::Backend::VertexAttributeRate::PER_VERTEX, 0}
486 : }};
487 0 : m_VertexInputLayout = g_Renderer.GetVertexInputLayout(attributes);
488 : }
489 :
490 0 : deviceCommandContext->BeginPass();
491 0 : deviceCommandContext->SetGraphicsPipelineState(
492 0 : m_ShaderTech->GetGraphicsPipelineState());
493 :
494 0 : Renderer::Backend::IShaderProgram* shader = m_ShaderTech->GetShader();
495 0 : deviceCommandContext->SetUniform(
496 0 : shader->GetBindingSlot(str_transform), proj.AsFloatArray());
497 :
498 0 : const int32_t colorBindingSlot = shader->GetBindingSlot(str_color);
499 0 : for (const DebugRect& r : m_DebugRects)
500 : {
501 0 : deviceCommandContext->SetUniform(
502 0 : colorBindingSlot, r.color.AsFloatArray());
503 : const float vertices[] =
504 : {
505 0 : r.x0, r.y0,
506 0 : r.x1, r.y0,
507 0 : r.x1, r.y1,
508 0 : r.x0, r.y0,
509 0 : r.x1, r.y1,
510 0 : r.x0, r.y1,
511 0 : };
512 :
513 0 : deviceCommandContext->SetVertexInputLayout(m_VertexInputLayout);
514 :
515 0 : deviceCommandContext->SetVertexBufferData(
516 0 : 0, vertices, std::size(vertices) * sizeof(vertices[0]));
517 :
518 0 : deviceCommandContext->Draw(0, 6);
519 : }
520 :
521 0 : deviceCommandContext->EndPass();
522 : }
523 :
524 0 : void SilhouetteRenderer::EndFrame()
525 : {
526 0 : m_SubmittedPatchOccluders.clear();
527 0 : m_SubmittedModelOccluders.clear();
528 0 : m_SubmittedModelCasters.clear();
529 3 : }
|
