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.
Not to mention others like arbitrary region management, collision detection with large numbers of objects, and manipulating color data in different color spaces.
File under 'M' for 'Manic ranting'
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.
I would have guessed he meant one of the platonic solids: teapotahedron
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."
Hmm, Doom 3 makes extensive use of both - that's fairly current tech eh? :)
Doom 3 does not use BSP trees for rendering. Neither did Quake 3. It uses BSP trees for other things, like collision detection.
"Portals" used to mean something other than it does now. You used to clip polygons against a portal, because this was faster in software. Now you just say "please draw the rooms adjacent to the current room." The "clipping" happens automatically on the GPU. "Room based rendering" would be a better term than "portal." There's no magic to this at all. It's just simple and common sense.
I make part of my living from commercial sale of scientific visualization software. It performs in software what used to require a $20,000 special-purpose instrument using embedded DSP processors (ouch, more buzzwords). The software is locked into Windows because it uses 1) CreateDIBSection() to allow direct manipulation of pixels in the manner of the post to which I was responding, 2) ScrollWindowEx() so the display can be scrolled using video card hardware, requiring the software to only redraw a small portion with each update, and 3) IDirectDraw::WaitForVerticalBlank() to synchronize scrolls and redraws with the vertical retrace for tear-free video.
Those three calls in Windows came about because Microsoft was trying to wean game developers away from DOS, where the direct control of copying pixel values into a video frame buffer was highly valued. Those three calls were to make 2-D games possible under Windows; those calls also happened to make my data visualization software possible.
There is almost but not quite like it in Java 2D. The direct manipulation of pixels is performed using multiple layers of objects pretty much according to the buzzword pipeline layed out in my original post. The vertical retrace synchronization is also there in some or another BufferManager object, but how it works on different OS's is anyone's guess. The hardware assisted scroll is not there, but hey, everyone is supposed to have such fast computers and video cards.
I was also commenting on 3-D techniques. You got me on that one because I don't have a clue as to 3-D techniques apart from the buzzwords, but it seems I am going to have to learn the 3-D techniques because no one makes 2-D games anymore. My data display goes back some 50 years when it was implemented using hardware filters and thermal paper, and that type of data display will probably be the standard in another 50 years, and I am going to have to figure out how to implement when no one supports 2-D graphics anymore (i.e. pixel-raster displays -- first "they" wouldn't let us touch the frame buffer because that was "too device dependent" and now "they" -- Microsoft with Longhorn, but others will follow -- won't let us touch individual pixels any more).
As software comes up with more advanced abstractions to separate software from specific hardware, it becomes increasingly hard to do interesting things apart from those things anticipated by the abstractions. I was seconding the view of the post to which I was responding that capabilities to do certain things will become lost.