Jump to content
  • Advertisement
Sign in to follow this  

Frustum culling, collision detection and ray tracing

This topic is 896 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Do game engines provide three different data structures to support frustum culling, collision detection and ray casting? I don't mean ray casting in the context of rendering, but in the context of gameplay programming. Does such ray casting go to the individual triangle level or does it stay at some intermediate level consisting of bounding volumes? The same for collision detection, does it make sense in general to go to the individual triangle level (the leaves of a tree?).

Share this post

Link to post
Share on other sites
There are as many systems as needed.
As mentioned, frustum culling works with bounding boxes and may be performed over a brute-force array of objects or stored in a bounding volume hierarchy (BVH), octree/quadtree, or some other spacial representation.

Physics engines are often written as their own modules with their own structures for spacial representation and structures specifically designed to speed up collision detection, such as the sweep-and-prune sorted records.

In all 3 cases (frustum culling, collision detection, and ray-casting), a single approach is not used.
For frustum culling, standard objects will be as described above with bounding boxes, whereas terrain will be culled as an implicit part of its rendering algorithm (see GeoMipmapping and GeoClipmapping) (and LOD systems are implicit as well, etc.)
For collision detection, collision between standard world objects and terrain are also often determined differently—collisions are always handled the same as they are just a matter of running math on vectors and forces, but to actually gather contacts may be separated into an algorithm to handle general world objects (such as sweep & prune) and an algorithm more tailored towards heightmaps, where the terrain can be divided into grid squares and 2 triangles checked, or other simplifications can be applied based on the assumption that the ground is always the bottom thing and is organized into a neat grid.
The same grid-based structure of terrain can also be used to simplify ray-casts, which means even ray-casts are likely to be handled differently for testing against terrain vs. standard objects.

A typical "world" ray-cast may cast against world objects first, and then against terrain, using any hits with objects from the previous test as an early-out when checking against the terrain. Meaning that if you hit an object 5 feet in front of you, you can stop the ray-cast against the terrain after only 5 feet. Terrain is checked 2nd because it is least likely to be the closest object a ray will hit, and thus can provide fewer early-outs for the test against world objects.

Frustum culling the "world" involves one algorithm to cull standard world objects, one to render/cull/LOD the terrain by itself, same for oceans, another for vegetation, etc.

"Global" collision detection may involve first generating contacts between standard objects using one method such as sweep & prune, following by generating more contacts with a method specifically for terrain, and maybe another method using compute shaders for vegetation.

There is no silver bullet. Just a lot of systems optimized to work certain ways, with algorithms designed around them to take advantage of their features.

L. Spiro Edited by L. Spiro

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!