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."
I look forward to re-doing my back yard with a nice quadratic mesh algorithm with pseudo-fractal post-processing.
Don't blame Durga. I voted for Centauri.
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.
for (int x = 0; x 320;x++) for (int y = 0; x 249; y++) drawpixel(x,y,data[x,y]) What ever happened to the simpler times...
je suis parce que j'aime
I hate when something is called a refresher course when it's something I never learned to begin with...
Matt Fahrenbacher
James Tiberius Kirk: "Spock, the women on your planet are logical. No other planet in the galaxy can make that claim."
They for the TNA Algorithm - Tactile Natural Assimilation, for realistic representation of the skin around a woman's Breasts and Backside. This is the money maker, used for everything from Tomb Raider (Lara Croft) to Mario's bulbous (read: breastlike) nose in the popular Super Mario Bros. games.
An egregious ommision.
They have a show for this now, "Trading Mesh Algorithms with Pseudo-fractal Post-processing" or TMAWPFPP for short.
Will they use quadratic?
Who knows!?!
Pure excitement...
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.
Holy?
We could have a true-to-life Mars landscape to traverse with these more accurate algorithms. Or, say, ride along the top of a microprocessor that's been nrought to scale with human size.
BLING BLING. Meet the architecture that's changing everything.
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'
(I am a Game Developer) and I'm trying to work out why this article was posted. Its too advanced for beginners, its not detailed enough for professionals. Its basically a list of the names & very basic approaches of a few graphics algorithms. I suppose people vaguely interested who know the basics but haven't tried some of these out are the target audience.
Anyone there fit the bill? Did you like this article? Was it helpful and informative?
Game dev and music blog
Yeah, but since it was a version I downloaded from Nintendo.com, I have to periodically spray for pokemon.
Don't blame Durga. I voted for Centauri.
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
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.
There was not a single illustration in the article. That is kind of ridiculous.
This article is like the 10,000,000-foot view of these things.
Man my 'advanced graphics algorithm' basically stops at 'thou shalt not blink' -- and I forget how I even did that.
400 poke(32768 + pos +1, 219)
410 poke(32768 + pos, 32)
or something like that.
(now I'm all grown up and all I do is database and web app stuff)
For the socially retarded among you, the amusing part of that is that anyone actually cares enough to bother!
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!
http://www.farcry-thegame.com/uk/
no comment
All current graphics accelerators that I am aware of don't do voxels. They start with polygons, apply transforms to those, apply textures, lighting and such, and then rasterize that to pixels. Well since they don't support voxels, a voxel based game would probably just suck. Graphics cards way outstrip CPUs in terms of crunching power because they are specialised for what they do. However that means that if you don't do things the way they want, they aren't useful and you are back to pure CPU processing.
No one is going to be able to market a blocky looking voxel game next to stuff like FarCry and Half Life 2. Even if the voxel engine is "technically" superior, it's not going to matter because lacking hardware acceleration, the end result will be far less impressive.
this being /. your normal bedtime reading is probably pr0n... you certainly "know the basics but haven't tried some of these [sex] out."
har har har!
Alright! AGA!
i've had an interest in generating worlds from random noise, particularly a network of probabilitsic methods and adaptive systems on top of a complex perlin noise engine. i still havent gotten to heavily into render code though, and i've definately made a backup of this page as reference materials for when i get around to turning my world into an actual optimized engine.
this seems to be his purpose: reference materials. he brushes upon everything needed to be useful and leaves the details of implementation as the due exercise. `graphics processors are optimized for sets of 500 - 4000 verticies,' BAM, fact #1 in quad-terrain methods. Ok, so my grid will be 24 x 24 point meshes: 576 vertexes and 1152 tris. 256 x 256 mesh is ~1.5 - 6 megs depending on how much your storing, I'll be using a lot of meta data and was planning on having at least a couple hundred meshes, storing intermediary stages of mesh addition, that means my world mesh alone comes dangerously close to taxing a full 64 mb.
He does a lot of the math for you, and in such a way that it can be applied readily to most problems. When you want to know more, there are references.
i've been leaning heavily towards a synthetic quad tree (makes a lot of sense with the perlin noise) and portal engine. Quick read gets my mind churning on the couple trouble spots in generating such a system (dynamic terrain). good stuff.
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.
OTOH tribes / tribes2 network protocol blows.
Mispredicts, jerkiness up the wazoo, even when there's little going on.
quake3's network protocol is much better.
I think the writer simply wanted to write a huge "smart" article so that he'd seem impressive. How can someone write an article on on CLOD without ever mentioning our friend Bezier? If someone wanted to write a "smart" article about graphics programming, he would have been better off writing one on GPU programming.
"Good, Fast, Cheap: Pick any two" -- RFC 1925
Given that the patent mentioned in a previous post is dated as filed in 1993, it sound fair to say there was prior art on that one too...
Forget thrust, drag, lift and weight. Airplanes fly because of money.
The problem is that everyone is striving for such a perfect level of abstraction with graphics that I can't figure out what you are supposed to do in the darned system. Forget the hierarchy of raster, image, graphics context (as in the baroque edifice called Java 2-D). I guess we are to assume such high-res displays that we are supposed to abstract away pixels and do all of our 2-D f(x,y) displays using some kind of 3-D vertex-tiled-pipelined mishmosh.
Lame joke after lame joke, modded higher than you think they should be. Welcome to Slashdot, newbie!
Don't blame Durga. I voted for Centauri.
The title "advanced graphics algorithms" is highly misleading. These algorithms are only really any use for real-time 3D graphics, which is a fairly small subset of computer graphics in general.
Admittedly, it happens to be an area that's worth a fair amount of money these days (i.e. games), but if you're considering it as a career, the deadlines are tight, the hours are lousy and the pay isn't great. Consider another area of advanced computer graphics instead.
sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
what? no pictures?
my associative arrays can kick your hash - TCL
Is there any possible role for NURBS in a game engine? Can contemporary GPUs offer any hardware assistance to utilizing them?
Please excuse ontopic post.
Article describes basics of ROAM algorithm, I am familiar with it, and I finished coding it long ago. I am aware of fact that ROAM is very CPU intensive, and everyone say that "ROAM should not be used today".
Has anyone tried ROAM 2.0??
I was searching for any other documents related to new ROAM version, but failed, I am still not sure how "AGP Chunking" really works (picture of triangulated patch would help much) and how to fast operate on diamonds (instead triangles). Could you give any links? Thanks in advance.
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.
There has been talk of implementing higher order surfaces in APIs like OpenGL and DirectX and then on teh coresponding hardware, but as far as I know, hasn't been done yet.
Not sure how feasable it is, either. Vertex shaders work so well because, with polygons, it's all just matrix math. So you build a killer vector unit, bang, you can do it at high speed on your graphics chip. I'm pretty sure the same kind of math doesn't apply to NURBS, you need something more complex.
Someday maybe. Or maybe the cards will take NURBS data, and translate it to polygons. However I don't think that is yet happening.