Slashdot Mirror
Refresh your Memory: Advanced Graphics Algorithms
subtle writes "DevMaster.net has posted an interesting article about advanced graphics algorithms. The article discusses six widely used algorithms in graphics rendering of indoor and outdoor environments, namely: quad-based static terrain, Roettger's approach to continuous levels-of-detail in terrain, real-time optimally adapting meshes, portals, BSPs and PVSs. In each case the algorithm is discussed and some aspects of implementation are considered, as well as analyize each algorithm for its application in modern graphics systems."
This is the first graphics programming article I've seen in a long time with no visual aids. I think the writer simply wanted to write a huge "smart" article so that he'd seem impressive. Missed some good algorithms for terrain rendering (tilemap, octrees, frustrum culling). If you want a really good site about graphics algorithms, check out Paul Debevec's homepage (famous for his contributions to The Matrix)
-=-=-=-=-=
I'd rather be flamed than ignored.
This is a very hot technical issue in gaming right now. The last 5 years have netted us decent techniques for doing network communications for low-latency gaming; with those in place now, we turn again to graphics.
Tribes and Tribes 2 were some of the first games to take on outdoor environments and do them well. Now, we have Unreal Tournament 2004 and Far Cry leading the pack with gloriously realistic outdoor playspaces.
It's only a matter of time before next generation gaming engines like these turn to non-linear gameplay such as what's in GTA 3 and we wind up with a world simulation that has a level of realism approaching reality.
Back in the day, I had a game on my Amiga called "Shadow of the Third moon", a space flight sim, that used voxels. It was quite a novelty at the time and I only had 16MB RAM.
Now that even cheap 3D cards have 128MB RAM on them, average systems have 256MB RAM, where are voxels used now?
google for voxels
Overall I enjoyed the article. I'm a complete beginner when it comes to computer graphics, but I'm really interested in computational theory and algorithms and I think I'm pretty good with those subjects (classes I've enjoyed the most on my road to being a CS major are algorithms and mathematical courses for the most part).
;)
The article touches on many subjects I haven't heard about and I learned what a BSP (binary space partitioning) tree is, at least. Graphics are probably the next thing I'll try to get into, and I still have an OpenGL manual lying around that's only been opened once.
Perhaps as a game programmer, you'd probably see that it's not as in-depth as you'd want, and it's probably not simple enough to be understood by everyone, but the article caters to, I guess, intermediate level people with a developing interest in computer graphics? Hits the sweet spot with me.
www.google.com
There was not a single illustration in the article. That is kind of ridiculous.
Ok, and what does the GPU do? Let me guess ... maybe using one of the well known algorithms? Ah, no, can't be, they are all outdated ... Ah I know: The GPU just throws it at the GPU ...
The GPU just transforms vertices and draws triangles, plus it runs per-vertex and per-pixel shaders. It does nothing involving scene representation or high-level culling. It just draws everything you throw at it.
BSP trees--for rendering--were useful back when there was a massive expensive involved in rasterizing each triangle on the CPU. You never wanted to draw a triangle, then have another one completely obscure it. But with modern graphics cards this is irrelevant. You just pass a bunch of pre-packaged vertices to the graphics card and it does the rest. You never want to break things down into individual triangles.
So, no, the GPU doesn't use one of these "well known algorithms."