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?).
Frustum culling, collision detection and ray tracing
Depends on the kind of game and the amount of precision required, I guess.
Collision on the triangle-level is probably way too slow/precise to even be usefull, but you can create geometry that closely approximates the model, like "convex hull". Since that doesn't work that well for animated meshes, you'd often just specify a fixed collision geometry like a capsule yourself, unless your game requires really tight collision checks (ie. fighting games where you check each limb).
For raycasting, you'd probably want to be able to tell what to use on each cast. For example, unreal lets you specify whether to use simplified or complex geometry:
https://docs.unrealengine.com/latest/INT/BlueprintAPI/Collision/LineTraceByChannel/index.html
Frustum culling almost always works with bounding spheres/boxes from what I've read. Since frustum culling mostly saves you CPUI-time by removing unnecessary API-calls/bindings, you don't want to spend too much time on checking complex geometry.
So you see, there's no real "standard"; but yes, different systems usually use different representations of geometry. If you are talking about generic game engines, they allow the user to choose what to do based on their needs. If you are talking about a specific game, evaluate the requirements and decide based on that.
Author
For raycasting, you'd probably want to be able to tell what to use on each cast. For example, unreal lets you specify whether to use simplified or complex geometry: https://docs.unrealengine.com/latest/INT/BlueprintAPI/Collision/LineTraceByChannel/index.html
But this "complex geometry" is not equal to the real geometry?
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
