Frustum-Culling.html (38217B)
1 <!DOCTYPE html> 2 <html lang="ja"> 3 <head> 4 <meta charset="utf-8"/> 5 <title>LearnOpenGL</title> 6 <link rel="shortcut icon" type="image/ico" href="/favicon.ico" /> 7 <link rel="stylesheet" href="../static/style.css" /> 8 <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml.js"> </script> 9 <script src="/static/functions.js"></script> 10 </head> 11 <body> 12 <nav> 13 <ol> 14 <li id="Introduction"> 15 <a href="https://learnopengl.com/Introduction">はじめに</a> 16 </li> 17 <li id="Getting-started"> 18 <span class="closed">入門</span> 19 <ol> 20 <li id="Getting-started/OpenGL"> 21 <a href="https://learnopengl.com/Getting-started/OpenGL">OpenGL </a> 22 </li> 23 <li id="Getting-started/Creating-a-window"> 24 <a href="https://learnopengl.com/Getting-started/Creating-a-window">ウィンドウの作成</a> 25 </li> 26 <li id="Getting-started/Hello-Window"> 27 <a href="https://learnopengl.com/Getting-started/Hello-Window">最初のウィンドウ</a> 28 </li> 29 <li id="Getting-started/Hello-Triangle"> 30 <a href="https://learnopengl.com/Getting-started/Hello-Triangle">最初の三角形</a> 31 </li> 32 <li id="Getting-started/Shaders"> 33 <a href="https://learnopengl.com/Getting-started/Shaders">シェーダー</a> 34 </li> 35 <li id="Getting-started/Textures"> 36 <a href="https://learnopengl.com/Getting-started/Textures">テクスチャ</a> 37 </li> 38 <li id="Getting-started/Transformations"> 39 <a href="https://learnopengl.com/Getting-started/Transformations">座標変換</a> 40 </li> 41 <li id="Getting-started/Coordinate-Systems"> 42 <a href="https://learnopengl.com/Getting-started/Coordinate-Systems">座標系</a> 43 </li> 44 <li id="Getting-started/Camera"> 45 <a href="https://learnopengl.com/Getting-started/Camera">カメラ</a> 46 </li> 47 <li id="Getting-started/Review"> 48 <a href="https://learnopengl.com/Getting-started/Review">まとめ</a> 49 </li> 50 </ol> 51 </li> 52 <li id="Lighting"> 53 <span class="closed">Lighting </span> 54 <ol> 55 <li id="Lighting/Colors"> 56 <a href="https://learnopengl.com/Lighting/Colors">Colors </a> 57 </li> 58 <li id="Lighting/Basic-Lighting"> 59 <a href="https://learnopengl.com/Lighting/Basic-Lighting">Basic Lighting </a> 60 </li> 61 <li id="Lighting/Materials"> 62 <a href="https://learnopengl.com/Lighting/Materials">Materials </a> 63 </li> 64 <li id="Lighting/Lighting-maps"> 65 <a href="https://learnopengl.com/Lighting/Lighting-maps">Lighting maps </a> 66 </li> 67 <li id="Lighting/Light-casters"> 68 <a href="https://learnopengl.com/Lighting/Light-casters">Light casters </a> 69 </li> 70 <li id="Lighting/Multiple-lights"> 71 <a href="https://learnopengl.com/Lighting/Multiple-lights">Multiple lights </a> 72 </li> 73 <li id="Lighting/Review"> 74 <a href="https://learnopengl.com/Lighting/Review">Review </a> 75 </li> 76 </ol> 77 </li> 78 <li id="Model-Loading"> 79 <span class="closed">Model Loading </span> 80 <ol> 81 <li id="Model-Loading/Assimp"> 82 <a href="https://learnopengl.com/Model-Loading/Assimp">Assimp </a> 83 </li> 84 <li id="Model-Loading/Mesh"> 85 <a href="https://learnopengl.com/Model-Loading/Mesh">Mesh </a> 86 </li> 87 <li id="Model-Loading/Model"> 88 <a href="https://learnopengl.com/Model-Loading/Model">Model </a> 89 </li> 90 </ol> 91 </li> 92 <li id="Advanced-OpenGL"> 93 <span class="closed">Advanced OpenGL </span> 94 <ol> 95 <li id="Advanced-OpenGL/Depth-testing"> 96 <a href="https://learnopengl.com/Advanced-OpenGL/Depth-testing">Depth testing </a> 97 </li> 98 <li id="Advanced-OpenGL/Stencil-testing"> 99 <a href="https://learnopengl.com/Advanced-OpenGL/Stencil-testing">Stencil testing </a> 100 </li> 101 <li id="Advanced-OpenGL/Blending"> 102 <a href="https://learnopengl.com/Advanced-OpenGL/Blending">Blending </a> 103 </li> 104 <li id="Advanced-OpenGL/Face-culling"> 105 <a href="https://learnopengl.cm/Advanced-OpenGL/Face-culling">Face culling </a> 106 </li> 107 <li id="Advanced-OpenGL/Framebuffers"> 108 <a href="https://learnopengl.com/Advanced-OpenGL/Framebuffers">Framebuffers </a> 109 </li> 110 <li id="Advanced-OpenGL/Cubemaps"> 111 <a href="https://learnopengl.com/Advanced-OpenGL/Cubemaps">Cubemaps </a> 112 </li> 113 <li id="Advanced-OpenGL/Advanced-Data"> 114 <a href="https://learnopengl.com/Advanced-OpenGL/Advanced-Data">Advanced Data </a> 115 </li> 116 <li id="Advanced-OpenGL/Advanced-GLSL"> 117 <a href="https://learnopengl.com/Advanced-OpenGL/Advanced-GLSL">Advanced GLSL </a> 118 </li> 119 <li id="Advanced-OpenGL/Geometry-Shader"> 120 <a href="https://learnopengl.com/Advanced-OpenGL/Geometry-Shader">Geometry Shader </a> 121 </li> 122 <li id="Advanced-OpenGL/Instancing"> 123 <a href="https://learnopengl.com/Advanced-OpenGL/Instancing">Instancing </a> 124 </li> 125 <li id="Advanced-OpenGL/Anti-Aliasing"> 126 <a href="https://learnopengl.com/Advanced-OpenGL/Anti-Aliasing">Anti Aliasing </a> 127 </li> 128 </ol> 129 </li> 130 <li id="Advanced-Lighting"> 131 <span class="closed">Advanced Lighting </span> 132 <ol> 133 <li id="Advanced-Lighting/Advanced-Lighting"> 134 <a href="https://learnopengl.com/Advanced-Lighting/Advanced-Lighting">Advanced Lighting </a> 135 </li> 136 <li id="Advanced-Lighting/Gamma-Correction"> 137 <a href="https://learnopengl.com/Advanced-Lighting/Gamma-Correction">Gamma Correction </a> 138 </li> 139 <li id="Advanced-Lighting/Shadows"> 140 <span class="closed">Shadows </span> 141 <ol> 142 <li id="Advanced-Lighting/Shadows/Shadow-Mapping"> 143 <a href="https://learnopengl.com/Advanced-Lighting/Shadows/Shadow-Mapping">Shadow Mapping </a> 144 </li> 145 <li id="Advanced-Lighting/Shadows/Point-Shadows"> 146 <a href="https://learnopengl.com/Advanced-Lighting/Shadows/Point-Shadows">Point Shadows </a> 147 </li> 148 </ol> 149 </li> 150 <li id="Advanced-Lighting/Normal-Mapping"> 151 <a href="https://learnopengl.com/Advanced-Lighting/Normal-Mapping">Normal Mapping </a> 152 </li> 153 <li id="Advanced-Lighting/Parallax-Mapping"> 154 <a href="https://learnopengl.com/Advanced-Lighting/Parallax-Mapping">Parallax Mapping </a> 155 </li> 156 <li id="Advanced-Lighting/HDR"> 157 <a href="https://learnopengl.com/Advanced-Lighting/HDR">HDR </a> 158 </li> 159 <li id="Advanced-Lighting/Bloom"> 160 <a href="https://learnopengl.com/Advanced-Lighting/Bloom">Bloom </a> 161 </li> 162 <li id="Advanced-Lighting/Deferred-Shading"> 163 <a href="https://learnopengl.com/Advanced-Lighting/Deferred-Shading">Deferred Shading </a> 164 </li> 165 <li id="Advanced-Lighting/SSAO"> 166 <a href="https://learnopengl.com/Advanced-Lighting/SSAO">SSAO </a> 167 </li> 168 </ol> 169 </li> 170 <li id="PBR"> 171 <span class="closed">PBR </span> 172 <ol> 173 <li id="PBR/Theory"> 174 <a href="https://learnopengl.com/PBR/Theory">Theory </a> 175 </li> 176 <li id="PBR/Lighting"> 177 <a href="https://learnopengl.com/PBR/Lighting">Lighting </a> 178 </li> 179 <li id="PBR/IBL"> 180 <span class="closed">IBL </span> 181 <ol> 182 <li id="PBR/IBL/Diffuse-irradiance"> 183 <a href="https://learnopengl.com/PBR/IBL/Diffuse-irradiance">Diffuse irradiance </a> 184 </li> 185 <li id="PBR/IBL/Specular-IBL"> 186 <a href="https://learnopengl.com/PBR/IBL/Specular-IBL">Specular IBL </a> 187 </li> 188 </ol> 189 </li> 190 </ol> 191 </li> 192 <li id="In-Practice"> 193 <span class="closed">In Practice </span> 194 <ol> 195 <li id="In-Practice/Debugging"> 196 <a href="https://learnopengl.com/In-Practice/Debugging">Debugging </a> 197 </li> 198 <li id="In-Practice/Text-Rendering"> 199 <a href="https://learnopengl.com/In-Practice/Text-Rendering">Text Rendering </a> 200 </li> 201 <li id="In-Practice/2D-Game"> 202 <span class="closed">2D Game </span> 203 <ol> 204 <li id="In-Practice/2D-Game/Breakout"> 205 <a href="https://learnopengl.com/In-Practice/2D-Game/Breakout">Breakout </a> 206 </li> 207 <li id="In-Practice/2D-Game/Setting-up"> 208 <a href="https://learnopengl.com/In-Practice/2D-Game/Setting-up">Setting up </a> 209 </li> 210 <li id="In-Practice/2D-Game/Rendering-Sprites"> 211 <a href="https://learnopengl.com/In-Practice/2D-Game/Rendering-Sprites">Rendering Sprites </a> 212 </li> 213 <li id="In-Practice/2D-Game/Levels"> 214 <a href="https://learnopengl.com/In-Practice/2D-Game/Levels">Levels </a> 215 </li> 216 <li id="In-Practice/2D-Game/Collisions"> 217 <span class="closed">Collisions </span> 218 <ol> 219 <li id="In-Practice/2D-Game/Collisions/Ball"> 220 <a href="https://learnopengl.com/In-Practice/2D-Game/Collisions/Ball">Ball </a> 221 </li> 222 <li id="In-Practice/2D-Game/Collisions/Collision-detection"> 223 <a href="https://learnopengl.com/In-Practice/2D-Game/Collisions/Collision-detection">Collision detection </a> 224 </li> 225 <li id="In-Practice/2D-Game/Collisions/Collision-resolution"> 226 <a href="https://learnopengl.com/In-Practice/2D-Game/Collisions/Collision-resolution">Collision resolution </a> 227 </li> 228 </ol> 229 </li> 230 <li id="In-Practice/2D-Game/Particles"> 231 <a href="https://learnopengl.com/In-Practice/2D-Game/Particles">Particles </a> 232 </li> 233 <li id="In-Practice/2D-Game/Postprocessing"> 234 <a href="https://learnopengl.com/In-Practice/2D-Game/Postprocessing">Postprocessing </a> 235 </li> 236 <li id="In-Practice/2D-Game/Powerups"> 237 <a href="https://learnopengl.com/In-Practice/2D-Game/Powerups">Powerups </a> 238 </li> 239 <li id="In-Practice/2D-Game/Audio"> 240 <a href="https://learnopengl.com/In-Practice/2D-Game/Audio">Audio </a> 241 </li> 242 <li id="In-Practice/2D-Game/Render-text"> 243 <a href="https://learnopengl.com/In-Practice/2D-Game/Render-text">Render text </a> 244 </li> 245 <li id="In-Practice/2D-Game/Final-thoughts"> 246 <a href="https://learnopengl.com/In-Practice/2D-Game/Final-thoughts">Final thoughts </a> 247 </li> 248 </ol> 249 </li> 250 </ol> 251 </li> 252 <li id="Guest-Articles"> 253 <span class="closed">Guest Articles </span> 254 <ol> 255 <li id="Guest-Articles/How-to-publish"> 256 <a href="https://learnopengl.com/Guest-Articles/How-to-publish">How to publish </a> 257 </li> 258 <li id="Guest-Articles/2020"> 259 <span class="closed">2020 </span> 260 <ol> 261 <li id="Guest-Articles/2020/OIT"> 262 <span class="closed">OIT </span> 263 <ol> 264 <li id="Guest-Articles/2020/OIT/Introduction"> 265 <a href="https://learnopengl.com/Guest-Articles/2020/OIT/Introduction">Introduction </a> 266 </li> 267 <li id="Guest-Articles/2020/OIT/Weighted-Blended"> 268 <a href="https://learnopengl.com/Guest-Articles/2020/OIT/Weighted-Blended">Weighted Blended </a> 269 </li> 270 </ol> 271 </li> 272 <li id="Guest-Articles/2020/Skeletal-Animation"> 273 <a href="https://learnopengl.com/Guest-Articles/2020/Skeletal-Animation">Skeletal Animation </a> 274 </li> 275 </ol> 276 </li> 277 <li id="Guest-Articles/2021"> 278 <span class="closed">2021 </span> 279 <ol> 280 <li id="Guest-Articles/2021/CSM"> 281 <a href="https://learnopengl.com/Guest-Articles/2021/CSM">CSM </a> 282 </li> 283 <li id="Guest-Articles/2021/Scene"> 284 <span class="closed">Scene </span> 285 <ol> 286 <li id="Guest-Articles/2021/Scene/Scene-Graph"> 287 <a href="https://learnopengl.com/Guest-Articles/2021/Scene/Scene-Graph">Scene Graph </a> 288 </li> 289 <li id="Guest-Articles/2021/Scene/Frustum-Culling"> 290 <a href="https://learnopengl.com/Guest-Articles/2021/Scene/Frustum-Culling">Frustum Culling </a> 291 </li> 292 </ol> 293 </li> 294 <li id="Guest-Articles/2021/Tessellation"> 295 <span class="closed">Tessellation </span> 296 <ol> 297 <li id="Guest-Articles/2021/Tessellation/Height-map"> 298 <a href="https://learnopengl.com/Guest-Articles/2021/Tessellation/Height-map">Height map </a> 299 </li> 300 </ol> 301 </li> 302 </ol> 303 </li> 304 </ol> 305 </li> 306 <li id="Code-repository"> 307 <a href="https://learnopengl.com/Code-repository">Code repository </a> 308 </li> 309 <li id="Translations"> 310 <a href="https://learnopengl.com/Translations">Translations </a> 311 </li> 312 <li id="About"> 313 <a href="https://learnopengl.com/About">About </a> 314 </li> 315 </ol> 316 </nav> 317 <main> 318 <div id="content"> 319 <h1 id="content-title">Frustum Culling</h1> 320 <h1 id="content-url" style='display:none;'>Guest-Articles/2021/Scene/Frustum-Culling</h1> 321 <p> 322 Now we know how to create a Scene graph and organize your object in a scene, we are going to see how to limit your GPU usage thanks to a technical name's the frustum culling. 323 This technique is simple to understand. 324 Instead of sending all information to your GPU, you will sort visible and invisible elements and render only visible elements. 325 Thanks to this technique, you will earn GPU compute time. 326 You need to know that when information travels toward another unit in your computer, it takes a long time. 327 For example, information from your GPU to your ram takes time. 328 It's the same if you want to send information from your CPU to your GPU like a model matrice. 329 It's for this reason that the "draw instance" is so powerful. 330 You send a large block to your GPU instead of sending elements one by one. 331 But this technique isn’t free. 332 To sort your element, you need to create a physical scene to compute some stuff with math. 333 This chapter will start with an introduction to the mathematical concept that will allow us to understand how frustum culling works. 334 Next, we are going to implement it. 335 Finally, we are going to study possible optimizations and talk about the balance of the technical. 336 </p> 337 338 <video width="850" controls> 339 <source src="/img\guest\2021\Frustum_culling\frustumExample.mp4" type="video/mp4"> 340 Your browser does not support the video tag. 341 </video> 342 343 <p> 344 In this video illustrating frustum culling in a forest, the yellow and red shape on the left side is the bounding volume that contains the mesh. 345 Red color means that the mesh is not visible and not sent to the GPU. 346 Yellow means that the mesh is rendered. 347 As you can see lots of things are rendered and few are visible for the player. 348 </p> 349 350 <h2>Mathematical concept</h2> 351 352 <p> 353 Let's start the mathematical parts from top to bottom. 354 Firstly, what is a frustum? 355 As we can see in <a href="https://en.wikipedia.org/wiki/Frustum" target="_blank"> Wikipedia</a>, frustum is a portion of a solid like a cone or pyramid. 356 The frustum is usually used in game engine to speak about the camera frustum. 357 Camera frustum represents the zone of vision of a camera. 358 Without limit, we have a pyramid but with near and far we have a frustum. 359 </p> 360 361 <img src="/img/guest/2021/Frustum_culling/VisualCameraFrustum.png" alt="Camera frustum shape"/> 362 363 <p> 364 How to mathematically represent a frustum? 365 Thanks to 6 plans: near, far, right, left top and bottom plans. 366 So, an object is visible if it is forward or on the 6 plans. 367 Mathematically a plan is represented with a normal vector and distance to the origin. 368 A plan doesn't have any size or limit as a quad. 369 </p> 370 371 <img src="/img/guest/2021/Frustum_culling/plan.png" width="600" alt="Plan representation"/> 372 373 <p> 374 So, create a struct to represent a plan: 375 </p> 376 <pre><code> 377 struct Plan 378 { 379 // unit vector 380 glm::vec3 normal = { 0.f, 1.f, 0.f }; 381 382 // distance from origin to the nearest point in the plan 383 float distance = 0.f; 384 385 [...] 386 }; 387 </code></pre> 388 389 <p> 390 We can now create <fun>Frustum</fun> structure: 391 </p> 392 393 <pre><code> 394 struct Frustum 395 { 396 Plan topFace; 397 Plan bottomFace; 398 399 Plan rightFace; 400 Plan leftFace; 401 402 Plan farFace; 403 Plan nearFace; 404 }; 405 </code></pre> 406 407 <p> 408 Reminder: a plan can be built with a point and a normal. 409 For the near, the normal is the front vector of the camera. 410 For the far plan, it's the opposite. 411 The normal of the right face we will need to do a cross product. 412 The cross product is the second wonderful tool for the programmer who likes vectors. 413 It allows you to get a perpendicular vector to a plan created with two vectors. 414 To go forward, we need to do the cross product of the right axis per up. 415 We will use it like that: 416 </p> 417 418 <img src="/img/guest/2021/Frustum_culling/RightNormal.png" alt="Plan representation"/> 419 420 <p> 421 But to know the direction of each vector from the camera to the far plan we will know the side length of the far quad: 422 </p> 423 <img src="/img/guest/2021/Frustum_culling/hAndVSide.png" alt="Plan representation"/> 424 425 <p> 426 hSide and vSide are the far quad limited by the other plans of the camera frustum. 427 To compute its edge, we will need of trigonometry. 428 As you can see in the image above, we have two rectangle triangles and we can apply the trigonometric functions. 429 So, we would like to obtain vSide which is the opposite side and we have zFar that is the adjacent side of the camera. 430 Tan of fovY is equal to the opposite side (vSide) divided by the adjacent side (zFar). 431 In conclusion, if I move the adjacent side on the left on our equation, tan of fovY multiplied by the zFar is equal to the vSide. 432 We now need to compute hSide. 433 Thanks to the aspect that is a ratio of the width by the height, we can easily obtain it. 434 So, hSide is equal to the vSide multiplied by the aspect as you can see on the right side of the image above. 435 We can now implement our function: 436 </p> 437 438 <pre><code> 439 Frustum createFrustumFromCamera(const Camera& cam, float aspect, float fovY, 440 float zNear, float zFar) 441 { 442 Frustum frustum; 443 const float halfVSide = zFar * tanf(fovY * .5f); 444 const float halfHSide = halfVSide * aspect; 445 const glm::vec3 frontMultFar = zFar * cam.Front; 446 447 frustum.nearFace = { cam.Position + zNear * cam.Front, cam.Front }; 448 frustum.farFace = { cam.Position + frontMultFar, -cam.Front }; 449 frustum.rightFace = { cam.Position, 450 <function id='61'>glm::cross</function>(cam.Up,frontMultFar + cam.Right * halfHSide) }; 451 frustum.leftFace = { cam.Position, 452 <function id='61'>glm::cross</function>(frontMultFar - cam.Right * halfHSide, cam.Up) }; 453 frustum.topFace = { cam.Position, 454 <function id='61'>glm::cross</function>(cam.Right, frontMultFar - cam.Up * halfVSide) }; 455 frustum.bottomFace = { cam.Position, 456 <function id='61'>glm::cross</function>(frontMultFar + cam.Up * halfVSide, cam.Right) }; 457 458 return frustum; 459 } 460 </code></pre> 461 <note> 462 In this example, the camera doesn't know the near, aspect but I encourage you to include this variable inside your Camera class. 463 </note> 464 465 <h3>Bounding volume</h3> 466 467 <p> 468 Let's take a minute to imagine an algorithm that can detect collisions with your mesh (with all types of polygons in general) and a plan. 469 You will start to say that image is an algorithm that checks if a triangle is on or outside the plane. 470 This algorithm looks pretty and fast! But now imagine that you have hundreds of mesh with thousands of triangles each one. 471 Your algorithm will sign the death of your frame rate fastly. 472 Another method is to wrap your objects in another geometrical object with simplest properties such as a sphere, a box, a capsule... 473 Now our algorithm looks possible without creating a framerate black hole. 474 Its shape is called bounding volume and allows us to create a simpler shape than our mesh to simplify the process. 475 All shapes have their own properties and can correspond plus or minus to our mesh. 476 </p> 477 <img src="/img/guest/2021/Frustum_culling/boundingVolumeQuality.png" alt="Bounding volume quality vs computation speed"/> 478 479 <p> 480 All shapes also have their own compute complexity. 481 The <a href="https://en.wikipedia.org/wiki/Bounding_volume" target="_blank">article</a> on Wikipedia is very nice and describes some bounding volumes with their balance and application. 482 In this article, we are going to see 2 bounding volumes: the sphere and the AABB. 483 Let's create a simple abstract struct Volume that represent all our bounding volumes: 484 </p> 485 486 <pre><code> 487 struct Volume 488 { 489 virtual bool isOnFrustum(const Frustum& camFrustum, 490 const Transform& modelTransform) const = 0; 491 }; 492 </code></pre> 493 494 <h4>Sphere</h4> 495 496 <img src="/img/guest/2021/Frustum_culling/boundingSphere.png" alt="Bounding sphere example"/> 497 498 <p> 499 The bounding sphere is the simplest shape to represent a bounding volume. 500 It is represented by center and radius. 501 A sphere is ideal to encapsulate mesh with any rotation. 502 It must be adjusted with the scale and position of the object. 503 We can create struct Sphere that inheritance from volume struct: 504 </p> 505 506 <pre><code> 507 struct Sphere : public Volume 508 { 509 glm::vec3 center{ 0.f, 0.f, 0.f }; 510 float radius{ 0.f }; 511 512 [...] 513 } 514 </code></pre> 515 516 <p> 517 This struct doesn't compile because we haven't defined the function isOnFrustum. 518 Let's make it. 519 Remember that our bounding volume is processed thanks to our meshes. 520 That assumes that we will need to apply a transform to our bounding volume to apply it. 521 As we have seen in the previous chapter, we will apply the transformation to a scene graph. 522 </p> 523 524 <pre><code> 525 bool isOnFrustum(const Frustum& camFrustum, const Transform& transform) const final 526 { 527 //Get global scale is computed by doing the magnitude of 528 //X, Y and Z model matrix's column. 529 const glm::vec3 globalScale = transform.getGlobalScale(); 530 531 //Get our global center with process it with the global model matrix of our transform 532 const glm::vec3 globalCenter{ transform.getModelMatrix() * glm::vec4(center, 1.f) }; 533 534 //To wrap correctly our shape, we need the maximum scale scalar. 535 const float maxScale = std::max(std::max(globalScale.x, globalScale.y), globalScale.z); 536 537 //Max scale is assuming for the diameter. So, we need the half to apply it to our radius 538 Sphere globalSphere(globalCenter, radius * (maxScale * 0.5f)); 539 540 //Check Firstly the result that have the most chance 541 //to faillure to avoid to call all functions. 542 return (globalSphere.isOnOrForwardPlan(camFrustum.leftFace) && 543 globalSphere.isOnOrForwardPlan(camFrustum.rightFace) && 544 globalSphere.isOnOrForwardPlan(camFrustum.farFace) && 545 globalSphere.isOnOrForwardPlan(camFrustum.nearFace) && 546 globalSphere.isOnOrForwardPlan(camFrustum.topFace) && 547 globalSphere.isOnOrForwardPlan(camFrustum.bottomFace)); 548 }; 549 </code></pre> 550 <note> 551 To compute the globalCenter we can’t only add the current center with the global position because we need to apply translation caused by rotation and scale. 552 This is the reason why we use the model matrix. 553 </note> 554 555 <p> 556 As you can see, we used a function undefined for now called <fun>isOnOrForwardPlan</fun>. 557 This implementation method is called top/down programming and consists to create a high-level function to determine which kind of function need to be implemented. 558 It avoids to implement too many unused functions that can be the case in "bottom/up". 559 So to understand how this function works, let's make a drawing : 560 </p> 561 562 <img src="/img/guest/2021/Frustum_culling/SpherePlanDetection.png" width="400" height="400" alt="Sphere plan collision shema"/> 563 564 <p> 565 We can see 3 possible cases: Sphere is inside the plan, back or forward. 566 To detect when a sphere is colliding with a plan we need to compute the nearest distance from the center of the sphere to the plan. 567 When we have this distance, we need to compare this distance with radius. 568 </p> 569 570 <pre><code> 571 bool isOnOrForwardPlan(const Plan& plan) const 572 { 573 return plan.getSignedDistanceToPlan(center) > -radius; 574 } 575 </code></pre> 576 577 <note> 578 We can see the problem in the other way and create a function called <fun>isOnBackwardPlan</fun>. 579 To use it we simply need to check if bounding volume IS NOT on the backward plan 580 </note> 581 582 <p> 583 Now we need to create the function <fun>getSignedDistanceToPlan</fun> in the </un>Plan</fun> structure. 584 Let me realize my most beautiful paint for you : 585 </p> 586 587 <img src="/img/guest/2021/Frustum_culling/SignedDistanceDraw.png" width="400" height="400" alt="Signed distance to plan shema"/> 588 589 <p> 590 Signed distance is a positive distance from a point if this point is forward the plan. 591 Otherwise this distance will be negative. 592 To obtain it, we will need to call a friend: The dot product. 593 Dot product allows us to obtain the projection from a vector to another. 594 The result of the dot product is a scale and this scalar is a distance. 595 If both vectors go oppositely, the dot product will be negative. 596 Thanks to it, we will obtain the horizontal scale component of a vector in the same direction as the normal of the plan. 597 Next, we will need to subtract this dot product by the nearest distance from the plan to the origin. 598 Hereafter you will find the implementation of this function : 599 </p> 600 601 <pre><code> 602 float getSignedDistanceToPlan(const glm::vec3& point) const 603 { 604 return glm::dot(normal, point) - distance; 605 } 606 </code></pre> 607 608 <h4>AABB</h4> 609 <img src="/img/guest/2021/Frustum_culling/boundingAABB.png" alt="Bounding AABB example"/> 610 611 <p> 612 AABB is the acronym of Axis aligned bounding box. 613 It means that this volume has the same orientation as the world. 614 It can be constructed as different can be we generally create it with its center and its half extension. 615 The half extension is a distance from center to the edge in the direction of an axis. 616 The half extension can be called Ii, Ij, Ik. In this chapter, we will call it Ix, Iy, Iz. 617 </p> 618 619 <img src="/img/guest/2021/Frustum_culling/AABBRepresentation.png" width="400" alt="AABB representation"/> 620 621 <p> 622 Let's make the base of this structure with few constructors to made its creation the simplest 623 </p> 624 625 <pre><code> 626 struct AABB : public BoundingVolume 627 { 628 glm::vec3 center{ 0.f, 0.f, 0.f }; 629 glm::vec3 extents{ 0.f, 0.f, 0.f }; 630 631 AABB(const glm::vec3& min, const glm::vec3& max) 632 : BoundingVolume{}, 633 center{ (max + min) * 0.5f }, 634 extents{ max.x - center.x, max.y - center.y, max.z - center.z } 635 {} 636 637 AABB(const glm::vec3& inCenter, float iI, float iJ, float iK) 638 : BoundingVolume{}, center{ inCenter }, extents{ iI, iJ, iK } 639 {} 640 641 [...] 642 }; 643 </code></pre> 644 645 <p> 646 We now need to add the function <fun>isOnFrustum</fun> and <fun>isOnOrForwardPlan</fun>. 647 The problem is not easy as a bounding sphere because if I rotate my mesh, the AABB will need to be adjusted. 648 An image talks much than a text : 649 </p> 650 651 <img src="/img/guest/2021/Frustum_culling/AABBProblem.png" alt="AABB rotation probleme"/> 652 653 <p> 654 To solve this problem lets draw it : 655 </p> 656 657 <img src="/img/guest/2021/Frustum_culling/AABB orientation.png" alt="AABB orientation problem explication"/> 658 659 <p> 660 Crazy guys want to rotate our beautiful Eiffel tower but we can see that after its rotation, the AABB is not the same. 661 To make the Shema more readable, assume that referential is not a unit and represented the half extension with the orientation of the mesh. 662 To adjust it, we can see in the third picture that the new extension is the sum of the dot product with the world axis and the scaled referential of our mesh. 663 The problem is seen in 2D but in 3D it's the same thing. Let's implement the function to do it. 664 </p> 665 666 <pre><code> 667 bool isOnFrustum(const Frustum& camFrustum, const Transform& transform) const final 668 { 669 //Get global scale thanks to our transform 670 const glm::vec3 globalCenter{ transform.getModelMatrix() * glm::vec4(center, 1.f) }; 671 672 // Scaled orientation 673 const glm::vec3 right = transform.getRight() * extents.x; 674 const glm::vec3 up = transform.getUp() * extents.y; 675 const glm::vec3 forward = transform.getForward() * extents.z; 676 677 const float newIi = std::abs(glm::dot(glm::vec3{ 1.f, 0.f, 0.f }, right)) + 678 std::abs(glm::dot(glm::vec3{ 1.f, 0.f, 0.f }, up)) + 679 std::abs(glm::dot(glm::vec3{ 1.f, 0.f, 0.f }, forward)); 680 681 const float newIj = std::abs(glm::dot(glm::vec3{ 0.f, 1.f, 0.f }, right)) + 682 std::abs(glm::dot(glm::vec3{ 0.f, 1.f, 0.f }, up)) + 683 std::abs(glm::dot(glm::vec3{ 0.f, 1.f, 0.f }, forward)); 684 685 const float newIk = std::abs(glm::dot(glm::vec3{ 0.f, 0.f, 1.f }, right)) + 686 std::abs(glm::dot(glm::vec3{ 0.f, 0.f, 1.f }, up)) + 687 std::abs(glm::dot(glm::vec3{ 0.f, 0.f, 1.f }, forward)); 688 689 //We not need to divise scale because it's based on the half extention of the AABB 690 const AABB globalAABB(globalCenter, newIi, newIj, newIk); 691 692 return (globalAABB.isOnOrForwardPlan(camFrustum.leftFace) && 693 globalAABB.isOnOrForwardPlan(camFrustum.rightFace) && 694 globalAABB.isOnOrForwardPlan(camFrustum.topFace) && 695 globalAABB.isOnOrForwardPlan(camFrustum.bottomFace) && 696 globalAABB.isOnOrForwardPlan(camFrustum.nearFace) && 697 globalAABB.isOnOrForwardPlan(camFrustum.farFace)); 698 }; 699 </code></pre> 700 701 <p> 702 For the function <fun>isOnOrForwardPlan</fun>, I have taken an algorithm that I found in a wonderful <a href="https://gdbooks.gitbooks.io/3dcollisions/content/Chapter2/static_aabb_plan.html" target="_blank">article</a>. 703 I invite you to have a look at it if you want to understand how it works. 704 I just modify the result of its algorithm to check if the AABB is on or forward my plan. 705 </p> 706 707 <pre><code> 708 bool isOnOrForwardPlan(const Plan& plan) const 709 { 710 // Compute the projection interval radius of b onto L(t) = b.c + t * p.n 711 const float r = extents.x * std::abs(plan.normal.x) + 712 extents.y * std::abs(plan.normal.y) + extents.z * std::abs(plan.normal.z); 713 714 return -r <= plan.getSignedDistanceToPlan(center); 715 } 716 </code></pre> 717 718 <p> 719 To check if our algorithm works, we need to check that every object disappeared in front of our camera when we moved. 720 Then, we can add a counter that is incremented if an object is displayed and another for the total displayed in our console. 721 </p> 722 723 <pre><code> 724 // in main.cpp main lopp 725 unsigned int total = 0, display = 0; 726 ourEntity.drawSelfAndChild(camFrustum, ourShader, display, total); 727 std::cout << "Total process in CPU : " << total; 728 std::cout << " / Total send to GPU : " << display << std::endl; 729 730 // In the drawSelfAndChild function of entity 731 void drawSelfAndChild(const Frustum& frustum, Shader& ourShader, 732 unsigned int& display, unsigned int& total) 733 { 734 if (boundingVolume->isOnFrustum(frustum, transform)) 735 { 736 ourShader.setMat4("model", transform.getModelMatrix()); 737 pModel->Draw(ourShader); 738 display++; 739 } 740 total++; 741 742 for (auto&& child : children) 743 { 744 child->drawSelfAndChild(frustum, ourShader, display, total); 745 } 746 } 747 </code></pre> 748 749 <img src="/img/guest/2021/Frustum_culling/result.png" alt="Result"/> 750 751 <p> 752 Ta-dah ! The average of objects sent to our GPUrepresents now about 15% of the total and is only divided by 6. 753 A wonderful result if your GPU process is the bottleneck because of your shader or number of polygons. 754 You can find the code <a href="https://learnopengl.com/code_viewer_gh.php?code=src/8.guest/2021/1.scene/2.frustum_culling/frustum_culling.cpp" target="_blank">here</a>. 755 </p> 756 757 <h2>Optimization</h2> 758 <p> 759 Now you know how to make your frustum culling. 760 Frustum culling can be useful to avoid computation of things that are not visible. 761 You can use it to not compute the animation state of your entity, simplify its AI... 762 For this reason, I advise you to add a IsInFrustum flag in your entity and do a frustum culling pass that fills this variable. 763 </p> 764 <h3>Space partitionning</h3> 765 <p> 766 In our example, frustum culling is a good balance with a small number of entities in the CPU. 767 If you want to optimize your detection, you now will need to partition your space. 768 To do it, a lot of algorithms exist and each has interesting properties which depend on your usage : 769 - BSH (Bounding sphere hierarchy or tree) : 770 Different kinds exist. The simplest implementation is to wrap both nearest objects in a sphere. 771 Wrap this sphere with another group or objetc etc... 772 <img src="/img/guest/2021/Frustum_culling/BSH.png" width="400" height="400" alt="BSH example"/> 773 </p> 774 <note> 775 In this example, only 2 checks allow us to know that 3 objects are in frustum instead of 6 because if the bounding sphere is totally inside the frustum all its content is also inside. 776 If the bounding sphere is not inside when needed to inter and check its content. 777 </note> 778 <p> 779 - <a href="https://en.wikipedia.org/wiki/Quadtree" target="_blank">Quadtree</a> : 780 The main idea is that you will split space into 4 zones that can be split into four zones etc... until an object wasn't wrapped alone. 781 Your object will be the leaf of this diagram. 782 The quadtree is very nice to partition 2D spaces but also if you don't need to partition height. It can be very useful in strategy games like 4x (like age of empire, war selection...) because you don't need height partitioning. 783 <img src="/img/guest/2021/Frustum_culling/quadtree.png" width="400" height="400" alt="Quatree example"/> 784 - <a href="https://en.wikipedia.org/wiki/Octree" target="_blank">Octree</a> : 785 It's like a quadtree but with 8 nodes. It's nice if you have a 3D game with elements in different height levels. 786 <img src="/img/guest/2021/Frustum_culling/octree.png" width="500" alt="Octree example"/> 787 - <a href="https://en.wikipedia.org/wiki/Binary_space_partitioning" target="_blank">BSP (binary space partitioning)</a> : 788 It's a very fast algorithm that allows you to split space with segments. You will define a segment and the algorithm will sort if an object is in front of this segment or behind. 789 It's very useful with a map, city, dungeon... The segments can be created at the same time if you generate a map and can be fast forward. 790 <img src="/img/guest/2021/Frustum_culling/BSP.png" alt="BSP example"/> 791 - Lot of other methods exist, be curious. 792 I don't implement each of these methods, I just learn it to know that they exist if one day I need specific space partitioning. 793 Some algorithm is great to parallelize like octree of quadtree if you use multithread and must also balance on your decision. 794 </p> 795 796 <h3>Compute shader</h3> 797 <p> 798 Compute shader allows you to process computation on shader. 799 This technique must be used only if you have a high parallelized task like check collision with a simple list of bounds. 800 I never implemented this technique for the frustum culling but it can be used in this case to avoid updating space partitioning if you have a lot of objects that move. 801 </p> 802 803 <h2>Additional resources</h2> 804 <ul> 805 <li><a href="http://www.cs.otago.ac.nz/postgrads/alexis/planExtraction.pdf" target="_blank"> 806 Article about camera frustum extraction</a>: Fast Extraction of Viewing Frustum Plans from the WorldView-Projection Matrix by Gil Gribb and Klaus Hartmann</li> 807 808 <li><a href="https://gdbooks.gitbooks.io/3dcollisions/content/Chapter1/aabb.html" target="_blank"> 809 Article about collisions detection</a>: A wonderful resource for collision detection and another approach about volume, culling and mathematic concept</li> 810 811 <li><a href="https://www.gamedev.net/tutorials/programming/general-and-gameplay-programming/frustum-culling-r4613/" target="_blank"> 812 Article to go further</a>: A good article to go further on GPU culling process, multithreading and OBB</li> 813 </ul> 814 815 816 <author> 817 <strong>Article by: </strong>Six Jonathan<br> 818 <strong>Contact: </strong><a href="Six-Jonathan@orange.fr" target="_blank">e-mail</a><br> 819 <strong>Date: </strong> 09/2021<br> 820 <div> 821 <a href="https://github.com/Renardjojo"> 822 <svg height="32" aria-hidden="true" viewBox="0 0 16 16" version="1.1" width="32" data-view-component="true" class="octicon octicon-mark-github v-align-middle"> 823 <path fill-rule="evenodd" d="M8 0C3.58 0 0 3.58 0 8c0 3.54 2.29 6.53 5.47 7.59.4.07.55-.17.55-.38 0-.19-.01-.82-.01-1.49-2.01.37-2.53-.49-2.69-.94-.09-.23-.48-.94-.82-1.13-.28-.15-.68-.52-.01-.53.63-.01 1.08.58 1.23.82.72 1.21 1.87.87 2.33.66.07-.52.28-.87.51-1.07-1.78-.2-3.64-.89-3.64-3.95 0-.87.31-1.59.82-2.15-.08-.2-.36-1.02.08-2.12 0 0 .67-.21 2.2.82.64-.18 1.32-.27 2-.27.68 0 1.36.09 2 .27 1.53-1.04 2.2-.82 2.2-.82.44 1.1.16 1.92.08 2.12.51.56.82 1.27.82 2.15 0 3.07-1.87 3.75-3.65 3.95.29.25.54.73.54 1.48 0 1.07-.01 1.93-.01 2.2 0 .21.15.46.55.38A8.013 8.013 0 0016 8c0-4.42-3.58-8-8-8z"></path> 824 </svg> 825 </a> 826 <a href="https://www.linkedin.com/in/jonathan-six-4553611a9/"> 827 <svg xmlns="http://www.w3.org/2000/svg" width="32" height="32" viewBox="0 0 34 34" class="global-nav__logo"> 828 <path d="M34,2.5v29A2.5,2.5,0,0,1,31.5,34H2.5A2.5,2.5,0,0,1,0,31.5V2.5A2.5,2.5,0,0,1,2.5,0h29A2.5,2.5,0,0,1,34,2.5ZM10,13H5V29h5Zm.45-5.5A2.88,2.88,0,0,0,7.59,4.6H7.5a2.9,2.9,0,0,0,0,5.8h0a2.88,2.88,0,0,0,2.95-2.81ZM29,19.28c0-4.81-3.06-6.68-6.1-6.68a5.7,5.7,0,0,0-5.06,2.58H17.7V13H13V29h5V20.49a3.32,3.32,0,0,1,3-3.58h.19c1.59,0,2.77,1,2.77,3.52V29h5Z" fill="currentColor"></path> 829 </svg> 830 </a> 831 </div> 832 </author> 833 834 </div> 835 836 </main> 837 </body> 838 </html>