I'm learning graphics programming by iterating on a cubes demo I've been working on. The demo currently has 10000 cubes being rendered, but only a fraction of those are on screen at any given time in most cases. I know the GPU hardware typically takes care of only rendering what it needs to, and clipping out the rest, but before rendering, I still have to calculate animation positions and so forth. This only actually needs to be done if a given cube is going to be on-screen though, which leaves me wondering if there's an easy way to only perform CPU-wise calculations on cubes that are going to be visible in camera space. Is this effectively a collision detection problem, i.e. working out if each cube overlaps the camera area? What's the usual approach?
Beginner: not performing CPU-wise calculations on objects outside of camera space
Crossbones+ - Reputation: 9281
Posted 10 March 2014 - 04:47 AM
This is called frustum culling, and is usually performed in batches as the GPU already does it at some point in the pipeline for individual triangles (so doing it on each cube on the CPU is mostly a waste of time). So usually you group your cubes according to some spatial data structure, the simplest being fixed grid buckets, where you test each bucket for intersection and ignore all cubes in the bucket if it doesn't intersect the camera's frustum, that way you can save a lot of work for the GPU down the line with comparatively little work done by the CPU. Then for whatever cubes are (potentially) visible, you can run other stuff that doesn't need to be done if the cube isn't on screen.
The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.
- Pessimal Algorithms and Simplexity Analysis
Crossbones+ - Reputation: 5332
Posted 12 March 2014 - 08:16 PM
You can also represent your individual objects with a bounding object to simplify the calculations. Bounding spheres are really simple to test against a frustum, but since they don't fit exactly to the enclosed object then it gives you a conservative list of what is inside the frustum (and hence should be drawn). You can then build your spatial data structure using the bounding volumes as well.
Jason Zink :: DirectX MVP
Direct3D 11 engine on CodePlex: Hieroglyph 3
Direct3D Books: Practical Rendering and Computation with Direct3D 11, Programming Vertex, Geometry, and Pixel Shaders
Articles: Dual-Paraboloid Mapping Article :: Parallax Occlusion Mapping Article (original):: Fast Silhouettes Article
Games: Lunar Rift