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."
AWESOME Rock Music Here
___
Advanced Graphics Algorithms
By: Henri Hakl
1. Introduction
Graphics representation of reality - or at least virtual reality - in games, simulations, movies, commercial and military applications have become increasingly convincing and immersed a growing audience in disbelieve - and at times even utter belief. This process has, in part at least, been facilitated by exponentially growing processing speeds and in more recent years the advent of hardware acceleration of graphics rendering.
However, even in spite of being able to process several giga-flops every second, a brute force approach to rendering is not able to produce nearly as realistic real-time environments and worlds as we find portrayed in games and interactive simulations. The reason is that numerous algorithms are used that approximate or compromise reality in order to achieve interactive rendering rates. These algorithms include methods to simplify scenes, to efficiently cull invisible parts or to simply ignore realistic computations in favour of faster approaches that, though inaccurate, portray reality.
Following the introduction we present a section on several graphics rendering concepts that feature in this article. In the remainder of this article we will discuss six popular algorithms for indoor and outdoor rendering of environments, namely:
quad-based static rendering of environments
a continuous level-of-detail (CLOD) rendering of height fields as described by Roettger et al [1]
real-time optimally adapting meshes (ROAM) for terrain rendering
portal-based rendering of indoor environments
binary space partitions (BSP) of indoor environments
potential visibility sets (PVS)
We will discuss each approach, offering a high-level description of each as well as implementation considerations where appropriate. Finally each algorithm will be discussed in terms of its application in modern graphics system before we conclude the article.
2. Concepts in Graphics Rendering
This section offers a broad overview into several key concepts in graphics rendering. These include the graphics pipeline, vertex representations, scene reduction techniques and graphics models - for a more extensive description we refer the interested reader to Alan Watt's 3D Computer Graphics [2].
2.1 The Graphics Pipeline
Graphics rendering is concerned with reducing a scene, a collection of three-dimensional data, to a smaller, visible subset and rendering this subset. To render a scene subset we note that a scene consists of polygons that are usually reduced to sets of triangles for hardware rendering purposes. The rendering process goes through a graphics pipeline during which the vertices of a triangle are transformed according to the current point-of-view and then projected from world space onto screen space according to the viewing frustum. The point-of-view determines the position and direction from which the world is rendered, while the viewing frustum determines the scope of the field-of-view (FOV).
After transformation and projection the triangle is lighted (meaning lighting calculations are performed on it) and clipped (meaning only visible parts are drawn) and then finally drawn to the graphics buffer. A number of approaches can be adopted during the drawing of the triangle, such as wire-frame only, solid, textured and bump-mapped.
Wire-framing only renders the lines connecting polygon vertices, solid renders color information only, texturing uses bitmap or procedural data that is projected onto the polygon, bump-mapping textures the polygon and utilizes some form of shadowing technique that creates a sense of depth to the image.
2.2 Vertex Representation
The triangle vertices used during the graphics pipeline can be represented in a number of ways, the simplest being a triangle-list. A triangle-list simply stores the vertices in sets of three, corresponding
Perhaps I missed "Graphics Algorithms 101" in a previous /. article, but after reading (or trying to read) TFA my response is: wibble.
John.
This is one of the best collections of graphics algorithms on the net I'm aware of:
comp.graphics.algorithms FAQ
Another favorite of mine is Ray Tracing News, but there haven't been any new issues in a few years.
What other people's favorite collections of algorithms?
-jim
This stuff isn't advanced, it's basic. It's more a refresher course on fundamental methods of organizing scenes. There's nothing difficult or amazing about portals, for example. In fact, much of the tech outlined in the article is outdated. Portals and BSPs (for rendering, not collision detection) are of much less use than they used to be. This quote shows that the author is just reiterating Quake-era views and hasn't written a modern renderer: "BSP trees are supremely efficient in rendering indoor environments." This is completely wrong. On a modern graphics card, it's much faster to throw the scene at the GPU and it let it render it all than it is to iterate through a BSP. Much faster.
I used to work for a voxel rendering company, Voxar. I developed the fastest software voxel rendering algorithm for opaque surface rendering of its time, around ten years ago. It wasn't used in games - and still isn't - because it'll always be a performance loser for gaming applications for as long as PCs include dedicated polygon hardware.
Comanche Maximum Overkill does not use voxels. I don't know why they chose that word to refer to the heightfields they do use.
Xenu loves you!
Didn't the pc games "Outcast" and it's sequel use voxels? I believe they did. They also used some skeletal animation and some interesting bone physics so that when my character strafed next to an incline, on foot would be higher than the other, his leg would be bent, and both feet would be in good contact with the ground. I've not seen another game do this, except maybe MechWarrior, but I don't remember.
Heya :)
;)
;) - hence the somewhat formal and academic style; however, in its current form as an article on DevMaster it is intended for intermediate readers. Those that look for some additional insight into (spatial) graphics algorithms. The article isn't a tutorial and (given its history) is not bothered with technical details, however, it does make reference to useful starting places for those that wish to explore the matter some more.
;) Those that really need them should go to the website.
I'm the author of the article. So I guess I can explain a few things.
Originally the article was written 3 years ago as a technical report for a small course I needed to do. DevMaster found this work and asked me whether they could make it available.
The course took place over 8 weeks, covering each algorithm in a week - and 2 weeks for the report at the end. The actual course work is still accessable at
http://www.cs.sun.ac.za/~henri/advgfx.html
And includes pictures and sources to keep everybody happy.
To those that are uncertain who the intended target audience is - well, originally my supervisor...
Although I agree - pretty pics would've been nice.
The choice of algorithms reflects not the state-of-the-art, nor the best approaches to solving graphics issues. The algorithms were, however, easily accessable to me at the time - and hence featured in my one-algorithm-a-week plan.
Somebody mentioned that BSPs are outdated, this isn't true - though they have been around for ages, they are still the work-horse for most indoor engines around. Sure, BSPs are rarely used for the actual rendering process (as mentioned in the article), but in terms of processability of spatial organization they are hard to beat.
I stand to be corrected but I'm rather sure Doom3 makes use of some form of BSPs as well. That should be good enough for anybody.
That means..
To write < you have to type <
and to write < you have to type &lt;
-- When did Ignorance Become a Point of View?