Photos Blog Random Things Links Guest Book Resume : #Lecture

Future of Terrain Programming

Feb 19, 2003
Times are in CST

[21:02] <trent> - I have several demos and figures to accompany this discussion (and a TON of links), so there is a lot of "extracirricular" activity :)
[21:02] <trent> That said, let's get started!
[21:03] <trent> Over the past few years, terrain programing has really become popular in games and many other fields. A lot of advancements have been made to allow programmers to have the best looking terrain possible. Games such as TreadMarks and Black and White made extensive use of terrain for their environments.
[21:04] <trent> In the past (keyword here being "past"), terrain algorithms such as ROAM (Real-Time Optimally Adapting Mesh) and VIPM (View Independent Progressive Mesh) were used for terrain engines in games and visualization applications. These algorithms put an emphasis on putting extra triangles were the terrain was coarse, and less triangles where areas where "flat" and "featureless."
[21:06] <trent> However, in the past couple years, extreme advancements have been made in GPU technology. We are no longer so concerned about how many triangles we send to the graphics card. So, to reflect this change in technology, the common terrain algorithms used must also be changed. ROAM and VIPM, while being great for their time, aren't really useful for games anymore in that they are very CPU intensive and not very GPU intensive.
[21:07] <trent> This is simply because the algorithms focused on triangle distribution more than anything else.
[21:08] <trent> However, if you are interested in these "old" algorithms, you can find several implementations and information at the following links: (very good site for any sort of terrain information), and you can find the ROAM whitepaper at
[21:12] <Vox> trent, are the algo's u going to present gonna be easily adaptable for coldet?
[21:12] <cppman> trent..but you could argue that bf terrain won't ever be totally applicable
[21:12] <spec_> bf?
[21:12] <Fruny> trent - view-dependent simplification algorithms ?
[21:12] <spec_> brute force?
[21:12] <Phantal> NeroX, for outdoor terrain they use something along the lines of a heightmap ...
[21:12] <cppman> brute force
[21:12] <impossible> Spindle: Unreal is all bruteforce
[21:12] <pseudo> its too obvious anymore or when the polycounts get low like with torque
[21:12] <trent> Vox: yes, very
[21:12] <trent> cppman: Yes, and I will
[21:12] <Spindle> mmmm
[21:12] <Vox> kewl
[21:12] <TRE> nuffer: think of it this way ... if the graphics card can handle it, why bog down the cpu?
[21:12] <TRE> you dont want to be cpu limited
[21:12] <Zygote-> lets get on with the lecture
[21:12] <Dcower> trent: Are nurbs or curved surfaces used for terrain any commercial engines, or is it even practical?
[21:12] <spec_> fruny - view-dependent has to be done with runtime refinement.
[21:12] <Zygote-> :)
[21:12] <trent> okay, I'm going to continue now, as you know, just /notice me when you have something to say
[21:12] <Zygote-> this could go on all night
[21:12] <illume> roam etc are still good for working on the cpu. on low power machines etc
[21:12] <TRE> trent: what dcower said
[21:12] <trent> Dcower: you can, but it is not practical.
[21:12] <impossible> Spindle: with the normal portal culling and whatnot that unreal has, no LOD though
[21:12] <Dcower> *in any
[21:12] <Phantal> impossible, the older one may have been, the newer engine uses something like a heightmap for outdoor terrain ... just wanted to know more about how they pull it off
[21:13] <trent> Now, I'm going to continue the lecture and get into the "guts" of tonight's discussion. :)
[21:13] <trent> The real question I'm betting that some of you have right now, is "What does a good algorithm need to do?"
[21:13] <trent> Well, as I alluded to a bit earlier, a good algorithm needs to minimize the amount of CPU cycles taken up per-frame, and maximize GPU effenciency.
[21:14] <trent> Remember, when it comes to graphics, we want to abstain from using the CPU as much as possible, since operations such as physics, AI and game logic need it far more.
[21:16] <trent> So, for the algorithms, not only do we want to minimize CPU usage, maximize GPU effenciency, but we also want to damn-near eliminate popping as much as we possibly can.
[21:16] <trent> For the uninformed, popping is the nasty effect that occurs when you switch from one level of detail to another. You will witness this effect in a demo I will be showing later on.
[21:17] <RedBeard> (popping is visible changes in the geometry)
[21:17] <trent> exactly
[21:17] <trent> and it is very distracting to the viewer
[21:17] <trent> Imagine you are in a very great-looking landscape
[21:17] <trent> and, as you get closer to a mountain, you notice that, at one point, it suddenly changes and becomes more detailed.
[21:18] <trent> This effect can completely take away the realism that is built up by the rest of the surroundings... After all, how often do you say geometry suddenly change in your daily life?
[21:18] <RedBeard> (or as was seen with ROAM, it gradually morphs from an indistinct hill to a craggy rock face)
[21:19] <trent> This nasty artifact can be covered up in part by using fog, but that's cheating, and after a while, the user will catch on. :)
[21:19] <trent> However, we will cover this a bit later.
[21:20] <trent> Right now, I want to cover the first of a few algorithms that will be covered in this lecture. It is called Geomipmapping, and it was first presented by Willem H. de Boer (which you can download here
[21:21] <trent> The basic idea of this algorithm is that you divide the entire landscape into several "patches" of land. And you change the LOD (level of detail, in case you forgot :) ) of each individual patch as needed.
[21:22] <trent> And now, I refer you to Figure 1 of this lecture, which can be found at
[21:23] <trent> Now, we will order our level of details from 0 -> x
[21:23] <trent> where 0 is the most detailed level of detail, and x is the least detailed
[21:23] <trent> Level 0 detail, in reference to the 5x5 vertex patch shown in Figure 1, would involve all vertices shown in the patch.
[21:24] <trent> To create a level 1 detailed patch, you would create the patch out of only the vertices marked in black.
[21:24] <trent> Also, for those that had troubles with the link, remove the ending punctuation
[21:25] <trent> Here are the links again though:
[21:25] <trent> The geomipmapping whitepaper by Willem H. de Boer:
[21:25] <trent> Figure 1 of this presentation
[21:26] <trent> If anyone does not understand the patch LOD concept, /notice me now.
[21:28] * trent explains the LOD patch concept to some people, hold on a moment.
[21:29] <trent> Okay, now, continuing. :)
[21:29] <trent> You may be wondering how we are going to be rendering each and every patch
[21:30] <trent> Well, what we are going to do, is organize all the height data into a vertex buffer (I am assuming, for this discussion, that we are using a height map for the terrain data).
[21:30] <trent> Once the vertex buffer has been built, our goal is to build indices into said vertex buffer for each LOD for every patch.
[21:30] <RedBeard> (interjected note: if you'd like to discuss the lecture topics in here without disrupting lecture, drop in to #backoftheclass)
[21:31] <trent> And, the dimensions of the height map should be (2^n) + 1 in size
[21:31] <trent> That is not a necessity, but it helps to create a uniform patch/vertex setup :)
[21:32] <RedBeard> it makes for 2^n quads in each row/column, which divides by 2 very nicely
[21:33] <trent> The index buffer building for each patch and LOD is actually quite simple, and you can see an example of it in the geomipmapping demo I will present towards the end of this explanation. It is not very complicated at all, and as long as you have a solid understanding of your API of choice (which you really should have, if you want to work with any sort of complex geometry).
[21:33] <trent> The problem is, when you have a series of patches, all with different levels of detail, a graphics artifact known as "cracking" occurs.
[21:34] <trent> This happens due to the fact that there is going to be a detailed patch next to a less-detailed patch, so it is only natural that the inconsistant vertex arrangement would create a hole in the geometry.
[21:35] <trent> The first thing we need to ensure, is that patches NEVER differ by more than one level of detail, this helps us greatly in our crack-fixing efforts.
[21:35] <trent> With that said, we have several "tools" to fix cracks at our disposal, Thatcher Ulrich presents 3 of these in his Chunked-LOD paper (more on this later), which you can find at
[21:35] <trent> However, my favorite way to fix cracks is to use something called a "skirt."
[21:37] <trent> Basically, this "skirt" is a line of quads that patches up the cracks, and extends a "safe" distance below the mesh. This will cause slight texture stretching, but the user would have to be very close to the mesh to notice this artifact. The joy of our implementation, however, is that once the user is that close the mesh, all surrounding patches will be of the highest level of detail, so no skirt will be needed at all!
[21:37] <trent> A little figure of a skirt in action can be seen at
[21:38] <trent> This wraps up the basics of the algorithm, you can find the 2.6mb demo at
[21:38] <trent> However, when you run the demo, you'll notice one glaring graphics artifact. And that is the "popping" that I mentioned a bit earlier.
[21:39] <trent> Since an entire patch of vertices is changing in detail, the popping is quite a glaring flaw too, as Superpig pointed out at the start of this discussion.
[21:39] <trent> This is where a popping-fixing technique known as "geomorphing" comes into play.
[21:40] <trent> Geomorphing is the process of slowly morphing a vertex's height over a set interval of time so that instead of a sudden change in detail, you have a slow progression that changes the detail in increments so minor that the user will never notice.
[21:41] <trent> And, since we are using indices into a vertex buffer (in OpenGL anyway), and the vertex buffer is not static, we can simply alter the vertex buffer as needed.
[21:41] <trent> However, this is a very "brute-force" fix to the problem, and, to make matters worse, if you're using a completely static vertex buffer, you are, in essence, fucked.
[21:42] <trent> However, to OpenGL users, NVidia offers the VAR extension, which allows you to essentialy create "write-only" vertex buffers... Very handy indeed!
[21:44] <trent> Also, another flaw to this algorithm is the high data-consumption necessary for holding several detail levels per patch, in an essentially large terrain dataset.
[21:44] <trent> This problem, unfortunately, cannot be fixed, but it can be minimized, which we are doing by using indices into a vertex buffer, rather than several vertex buffers per patch.
[21:45] <trent> This is the end of my discussion of this algorithm, I will now open the channel to discussion of the topics talked about thus far... and I need a change in music. :)
[21:45] <lostsheep> lol
[21:45] <CodeDemon> heh
[21:46] <FuriousBroccoli> please comment: real terrain can overlap and overhang...the days of heightmapped terrain are numbered...what would have to change for similar algorithms to be used for arbitrary meshes?
[21:46] <spec_> shadows.
[21:46] <Vox> which music should we switch to?
[21:46] <spec_> furious - ehhh please don't bring that up. :)
[21:46] <FuriousBroccoli> heh sorry
[21:46] <CodeDemon> does anyone know if ati and other vendors offer gl extensions for dynamic vertex buffers?
[21:46] <trent> FuriousBroccoli: not much of the actual algorith implementation needs to be changed, you just need to make the implementation support triangle-soup data :)
[21:46] <Squint> furious - it can... there is no reason why you cant mipmap an arbitrary mesh
[21:46] <Squint> but I think a skirt would be a night mare to implement
[21:46] <Superpig> Furious: presumably he's going to discuss an algorithm that deals with things like overhang. Or at least, he'd better. :)
[21:47] <lostsheep> i just got back from a meeting, is the lecture log gonna be hosted somewhere?
[21:47] <Dcower> he said a bad word...;)
[21:47] <trent> Superpig: hehe, not really, but I do have a reference that will discuss it.
[21:47] <nuffer> are the normal gl vertex buffers always locked?
[21:47] <RedBeard> yes, the logs are all hosted on my website
[21:47] <trent> lostsheep: yup
[21:47] <trent> Excuse me for a moment while I go get a new drink :)
[21:47] <lostsheep> trent: where?
[21:47] <Superpig> CD: it'd be worth looking into the ARB stuff - maybe they're considering making it part of OpenGL2?
[21:47] <BlabberBoy> spec_: how come you said "shadows."?
[21:47] <Inferna|> are there algorithms faster than geomipmapping?
[21:47] <spec_> furious - it's possible to wisely choose coordinate systems so you can have pretty good flexibility and still have single-valued data (wrt to a LOCAL coordinate system - not a global one). but i think having arbitrary topolgy (i.e. holes) would be real hard.
[21:47] <CodeDemon> Superpig: yeah
[21:47] <Locke-> You'd only need a sjirt for a dip, not a hill, as you will always be lookinf from a higher detailed patch toa lower one?
[21:47] <spec_> blabber - because it's tricky.
[21:47] <FuriousBroccoli> so in a sense it would be similar to a progressive mesh that tesselates more on one side than another
[21:47] <trent> Inferna|: an algorithm is only as good as its implementation. :) But yes, there are.
[21:48] <Inferna|> the CPU load for GMM after compiling of the LOD meshes is quite low
[21:48] <BlabberBoy> just wondering cause you said it last time it was opened up, and aren't really expanding on the one word...
[21:48] <masterg> Inferna| Relative to what I'm pretty sure trent will discuss soon, chunked lod is the current alter norm.
[21:48] <terminate> if you just need terrain, not "specific terrain", you could always generate it on the video card
[21:48] <Superpig> Locke: I think that's right
[21:48] <CodeDemon> Locke-: what if you were to move the camera to the bottom, and then look up the hill?
[21:49] <RedBeard> trent: instead of doing a selection of every other vertex, could you not do a non-grid-based VIPM (or other) simplification for each LOD step, and then swap those out instead of slicing things up on a grid? In my experience, adaptive simplification is much nicer than rigid simplification.
[21:49] <Superpig> CD: but you would still be looking from a high-detail patch to a low-detail patch, though, wouldn't you?
[21:49] <trent> RedBeard: yes, and I'm getting to that.
[21:49] <nuffer> whats a good save file format for non-heightmap terrain?
[21:49] <spec_> furious - i think a lot of the problem with the non-singlevalued terrain is that no one can make good data for it.
[21:49] <trent> nuffer: your own.
[21:49] <nuffer> like how would it store data...
[21:49] <The_Is> it just seems that by the time you determine that none of the high detail verts are under the low detail ones, you couldve already been done drawing the skirt
[21:50] <pseudo> could do a voxel format
[21:50] <nuffer> just vertex coords, or something else?
[21:50] <spec_> satellite data is single-valued, and even game data is single-valued (like paint a monochrome surface for a heightfield)
[21:50] <pseudo> that'd be lots of data tho
[21:50] <CodeDemon> Superpig: yes, but without a skirt, looking upwards, you would see a gap in this case - looking down from the top, you wouldn't see any gaps
[21:50] <Phantal> trent, that rar seems to be corrupt
[21:50] <pseudo> curved surfaces would be the best way
[21:50] <trent> Phantal: shouldn't be, it fully uploaded
[21:50] <Superpig> CD, ok
[21:50] <trent> Phantal: how large is the one you downloaded?
[21:50] <Locke-> It's not corrupt
[21:50] <FuriousBroccoli> right, so any feasible solution would seem to be an arbitrary mesh
[21:51] <Dcower> the .rar isn't corrupt
[21:51] <spec_> furious - i suppose you could recognize where the terrain failed to be single valued, then include triangle soup just for that patch
[21:51] <RedBeard> spec_ - consider something like America's Army. There's one map in there which is obviously man-made and using grid-based geometry, and it has a huge valley with no outlet for water to flow out of... just for the sake of "reality" i think having a cave or something just put in by hand would be great, but it apparently couldnt handle that
[21:51] <Phantal> trent, 2.59 MB (2,717,747 bytes)
[21:51] <Squint> you can do several terrains in the same place for multiple heights ...
[21:51] <Superpig> ...odd, the file is only 2654k...
[21:51] <Phantal> trent, i just get a bunch of lines that say this: 1 GMM[1].rar: Unknown method in GeoMipMappingOGL\Data\ps_height_1k.raw
[21:51] <Phantal> for every file
[21:51] <CodeDemon> Phantal: WinArc is known not to decompress certain files compressed with other utilities
[21:51] <spec_> redbeard - that's just bad game design. i wouldn't fault terrain technology. you can always add in caves and things as models
[21:52] <Phantal> CodeDemon, i'm using winrar
[21:52] <CodeDemon> er
[21:52] <CodeDemon> winrar I mean, sorry
[21:52] <The_Is> and sim city 2000/roller coaster tycon cells
[21:52] <trent> Phantal: I just unpacked it and tried it, worked fine.
[21:52] <CodeDemon> winrar is evil, heh
[21:52] <RedBeard> you should be able to take the GMM concept from a 2D to a 3D mesh (quad division to oct division) using VIPM-like simplification instead of every-other-vertex
[21:52] <BlabberBoy> worked fine for me with winrar
[21:52] <Phantal> i'll try winzip
[21:52] <Zygote-> worked for me witn winrar
[21:52] <Zygote-> :)
[21:52] <Superpig> spec: yet as far as the collision detection would be concerned, you'd be inside a solid mountain. I guess portals would be the answer
[21:52] <masterg> Phantal: WinRAR should work fine; Update, if necessary as I just did (
[21:52] <RedBeard> and thus apply it to an arbitrary mesh
[21:53] <Dcower> i'm using winrar and it extracts fine....
[21:53] <Dcower> version 8
[21:53] <Phantal> hrm
[21:53] <FuriousBroccoli> for the terrain mipmapping, do you use the heightmaps mip map to generate that?
[21:53] <RedBeard> I'm personally using portals in my engine, but I'm interested in unified solutions to visibility and coldet
[21:53] <Phantal> err ... hrm
[21:53] <Phantal> version 8?
[21:53] <Dcower> Phantal: Try downloading it again
[21:53] <masterg> FuriousBroccoli: Are you referring to the geomipmapping? (As the mipmaps are generated from the procedurally generated texture)
[21:53] <Phantal> i just got this version i have like ... 6 months ago, and it says beta 5 of 2.7
[21:53] <RedBeard> furious: i think you basically just create a vertex buffer from the base heightmap, throw away the heightmap, and then simplify the data you made
[21:53] <spec_> superpig - in practice i don't think that would be a big deal.
[21:53] <Dcower> it's a beta i think...
[21:54] <Dcower> oops, version 3
[21:54] <masterg> RedBeard: IIRC, Trent keeps the heightmap
[21:54] <FuriousBroccoli> yes I meant geo-mip mapping, thanks
[21:54] <Vox> hmm UltimateZip downloaded twice corrupt getting WinRar
[21:54] <Phantal> oh, heh, was worried there
[21:54] <Superpig> spec: indeed. that's the sort of problem portal engines were formulated to handle, anyway...
[21:54] <Inferna|> in trents demo, the heightmap is only used to generate the vertex buffer. nothing else
[21:54] <trent> correct
[21:55] <Inferna|> the indices are done using a simple for loop and an increment value
[21:55] <masterg> heh, i've gotta' reinstall msvc to check out his latest demo
[21:55] <trent> alright guys, finish discussions up, I'm about to start up the next segment.
[21:55] <masterg> or at least switch over pcs
[21:55] <spec_> trent - you store each LOD seperately, right?
[21:55] <spec_> i.e. you should get 1/3 waste with deboer?
[21:55] <trent> Vox: I meant to, it was too late when I realized I used RARs
[21:55] <Vox> k
[21:55] <trent> spec_: hmmm, there isn't much waste at all.
[21:56] <terminate> everyone able to download the demo ok?
[21:56] <spec_> trent - eh. well what if you are zoomed out far enough to see the whole terrain? you can't fit all the vertices in vram.
[21:56] * Dcower goes to get some more water
[21:56] <Superpig> term: still downloading - 56K :(
[21:56] <Locke-> terminate: yeah
[21:56] <terminate> ok good
[21:56] <CodeDemon> sorry, whats the link for the demo again?
[21:56] <RUebaiYaT> is the lecture over ?
[21:56] <trent> no
[21:56] <spec_> no\
[21:56] <terminate> my server is wimpy :P
[21:56] <Locke-> no
[21:56] <UndNoC> is there a zoom key on the demo?
[21:56] <trent> spec_: hmm, I'm missing your point, but I'll talk to you later about it.
[21:56] <Superpig> no
[21:56] <trent> UndNoC: use the arrow guys
[21:56] <trent> *arrow keys
[21:56] <UndNoC> ok thanks
[21:56] <trent> anyway, time to continue the discussion.
[21:57] <Locke-> cool
[21:57] <RedBeard> trent: i think he's talking about storing a 2048x2048 vertex buffer in vram
[21:57] <spec_> yeah it ain't going to happen.
[21:57] <RedBeard> .calc 2048^2*32
[21:57] <X2> RedBeard: 1.342177E+08
[21:57] <Zygote-> discussions can take place in #backoftheclass
[21:57] <trent> We are now going to discuss Thatcher Ulrich's Chunked-LOD algorithm
[21:58] <trent> All of the information for which can be found at the algorithm's site
[21:58] <trent> The demo, in concept, is very similar to the geomipmapping algorithm.
[21:58] <trent> There are, however, two main differences that greatly affect performance and effenciency
[21:59] <trent> First of all, the mesh arrangement functions like a quadtree. The lowest level of detail has a single node.
[21:59] <trent> Then, as more detail is required, the mesh subdivides as needed.
[22:01] <trent> The other main difference between the Chunked-LOD algorithm and the geomipmapping algo comes in the form of the triangle arrangement.
[22:01] <trent> Instead of using a rigid triangle arrangement like the geomipmapping algorithm, the Chunked-LOD algorithm simplifies the mesh, adding more triangles in coarse areas of the mesh, and less triangles in flat/featureless areas of the mesh.
[22:02] <trent> This creates a great performance increase, as it reduces the total number of triangles present.
[22:03] <trent> As for the precise implementation details of this process (aka. whether it is done as a preprocessing step, or whether it is done in real-time), I'm not totally sure. I haven't delved into the Chunked-LOD world very much, due to the fact that I jumped from writing "Focus on 3D Terrain" to "Windows and Linux Game Programming."
[22:03] <trent> However, Jonathon Blow, in his new GDMag column, is covering this precise algorithm in great detail. So you can follow his column, to see how his implementation turns out.
[22:04] <trent> Superpig asked a very good question: -Superpig- but what if your terrain was coarse all round? wouldn't that produce an increase in total number of triangles?
[22:04] <trent> If you had very coarse terrain, yes, it would produce an increase in the total number of triangles, and a very flat-ish terrain would produce a decrease the average amount of triangles.
[22:05] <trent> However, it is very important to note, as spec_ pointed out, that the amount of triangles is limited by the resolution of the data that the terrain is defined by.
[22:06] <trent> In a height-map based system, you cannot have a level of detail greater than that of the height map. However, you can have an infinte level of detail if you use base your terrain off of a fractal data set. But that is quite a bit more complicated than the scope of this lecture allows. :)
[22:07] <trent> I'm going to briefly open the room to discussion, very briefly though, I need to get some Warcraft 3 in. :)
[22:07] <FuriousBroccoli> teh craft is broke I say!
[22:07] <Superpig> ... but of course, what trent fails to realise, is that everything's being discussed in #backoftheclass as he types it. :)
[22:08] <Locke-> hehehehe, I don't remember any professer ever pausing a lecture for WC3
[22:08] <trent> Locke-: yeah, well, I'm an odd duck. :)
[22:08] <Superpig> Locke: but any professors pausing WC3 for a lecture? ;)
[22:08] <spec_> locke- he just said that. he's really hitting the scotch.
[22:08] <NeroX> anyone know if these chunkedlod gdmag articles will appear on gamasutra?
[22:08] <trent> NeroX: its probable, but doubtful
[22:08] <FuriousBroccoli> the code will
[22:08] <The_Is> my tree logic is a bit rusty, how many total vertexes in a patch of size n,n when stored in a quad tree? i.e. how many nodes?
[22:08] <trent> Even so, the source code of Jonathon Blow's code will be online.
[22:08] <NeroX> thats true
[22:09] <krogoth> The_Is: for nxn quads you need (n+1)^2 verts
[22:09] <Locke-> brb, gonna reboot in this time
[22:09] <NeroX> what algo is used in chunked lod to tessellate the different lod levels for each chunk?
[22:09] <The_Is> oh ok thats not so bad
[22:10] <trent> NeroX: I don't believe it is discussed in the Chunked-LOD paper
[22:10] <trent> But Blow is usingthe "Garland Heckbert Error Quadric Simplification" algo.
[22:10] <NeroX> It looks like roam in the source but I'm not sure
[22:11] <spec_> what's this thing about Blow?
[22:11] <RedBeard> roam is view-dependent, the stuff for chunked lod is independent, precomputed generally
[22:11] <trent> spec_: its a new column in teh newest issue of Game Developer Magazine.
[22:11] <Superpig> spec: Johnathon Blow's articles
[22:11] <raydogg> how come you can't zoom in on the demo :-(
[22:11] <raydogg> i want to run through the mountains
[22:11] <trent> you can
[22:11] <trent> use the mouse. :)
[22:11] <NeroX> "roam like"
[22:11] <raydogg> how do you "zoom"
[22:11] <trent> hold teh mouse button down and move the mouse.
[22:11] <nuffer> does perspective affect what algorithims you choose?
[22:12] <raydogg> that moves the map
[22:12] <Dcower> Johnaton Blow......?
[22:12] <raydogg> i want to get down and dirty
[22:12] <spec_> Blow is credited with vertex envelopes for view-dependent LOD in lindstrom2001
[22:12] <spec_> this is something different, in gdm i mean?
[22:12] <trent> raydogg: bitch to Thatcher Ulrich then. :P
[22:12] <trent> spec_: yes
[22:12] <FuriousBroccoli> top down doesnt need it unless you zoom way out :)
[22:13] <raydogg> lol
[22:13] <trent> Okay, we're moving on to the next subject now... its a very short one, so I'll be moving into texturing directly after it.
[22:13] <trent> The next algorithm I want to briefly cover (if you can call it that, I'm basically telling you that it exists, and showing you a few demos) is ROAM 2.0.
[22:14] <trent> The main problem in discussing this algorithm at the moment is that the official whitepaper hasn't been released yet, so the amount I can tell you, without writing a 20 page dissertation on it is very minimal. :)
[22:14] * RedBeard gets out the Top Secret stamp and some red ink
[22:14] <trent> ROAM 2.0 is completely unlike geomipmapping and Chunked-LOD, it functions like the original ROAM algorithm (big surprise there), except makes it a bit more hardware-friendly.
[22:15] <trent> Mark Duchaineau and I created a set of 4 "steps" to introduce you to the algorithm, but until the official whitepaper is released, or you buy my book (MWUAHAHA!), there just isn't much to discuss. :)
[22:15] <trent> The demos can be found at
[22:16] <trent> If you have questions about the demo, feel free to e-mail me at or contact me via a private message sometime.
[22:16] <trent> However, now we are going to briefly cover texturing techniques.
[22:17] <trent> There are multiple ways to texture terrain, some much better than others (I'm better texture shaders would be a huge help here, but I digress).
[22:18] <trent> In my book, I simply generated one 256x256 or 512x512 pixel texture map as a pre-processing step using various individual texture tiles, and then used a detail map to make it more detailed.
[22:18] <trent> A screenshot of a terrain patch with a simple stretched texture map can be found at
[22:19] <trent> And the same patch, except with a detail map applied to it, can be found at
[22:19] <trent> As you can see, the detail map makes the once-bland texture seem A LOT more detailed than it really is, so that is just a nifty little trick that you can use in your texturing.
[22:20] <trent> A nifty little texture-generation tutorial can be found at
[22:20] <trent> It is very simple to follow, and implementing it yourself is also a very easy step, but if you have any troubles with it, feel free to contact me, and I'll help ya through it. :)
[22:23] <trent> spec_ asked an interesting question: -spec_- this detail texture is synthesized inside the pixel shader?
[22:24] <trent> No, the detail texture is applied simply using hardware multitexturing, nothing more
[22:24] <trent> Also, another very useful texturing concept is presented by Charles Bloom, and it is called "Texture Splatting."
[22:24] <trent> You can find this very detailed text file at
[22:25] <trent> CodeDemon asked another interesting question: -CodeDemon- using the standard detail mapping method--ie, the detail texture fades in as you get closer to the geometry, and fades out as you get farther away?
[22:25] <trent> No, while you can do that if you'd like, you can simply leave the detail texture as it is no matter the viewer's distance.
[22:26] <trent> Okay, I am now opening the channel to its last discussion before the lecture's end.
[22:27] <CodeDemon> yay
[22:27] <BlabberBoy> trent: thought you said your connection would be ok once you started...
[22:27] <BlabberBoy> :)
[22:27] <trent> BlabberBoy: My ISP hasn't been too great all day.
[22:27] <trent> :P
[22:27] <CodeDemon> I wish flipcode had printer-friendly versions of their documents
[22:27] <Pion> where will the log available?
[22:27] <Inferna|> is Roam2.0 potentially faseter than chunked terrain?
[22:27] <terminate> Pion > yes
[22:27] <Inferna|> er faster
[22:27] <Pion> i mean where?
[22:27] <trent>
[22:28] <Pion> oh thx
[22:28] <trent> Inferna|: no, ROAM 2 is not very useful for games.
[22:28] <Zygote-> roam 2 has very large pixel errors
[22:28] <trent> ROAM 2.0 is a much better visualization algorithm.
[22:28] <Zygote-> :P
[22:28] <FuriousBroccoli> it seems to tesselate to sick levels, even when zoomed in very far
[22:29] <trent> it does. :)
[22:29] <FuriousBroccoli> did you work on ROAM 2, trent?
[22:29] <nuffer> ...
[22:29] <trent> No, I'm just helping Mark advertise it and get people interested.
[22:29] <trent> I helped him with the teaching steps though
[22:29] <FuriousBroccoli> nice
[22:30] <spec_> if it isn't good for games, what is it good for?
[22:30] <FuriousBroccoli> lol
[22:30] <trent> spec_: terrain visualization
[22:30] <impossible> cool tech demos
[22:30] <Locke-> spec: he said visualisations
[22:30] <FuriousBroccoli> nuclear warfare!
[22:30] <impossible> that too
[22:30] <trent> Terrain has MANY applications outside of games.
[22:30] <asdf> such as?
[22:30] <spec_> ehm yes but how is it better than chunked LOD for general terrain visualization?
[22:30] <trent> asdf: check out, they have a complete list of the uses.
[22:30] <Superpig> just because it's not a real-time situtation doesn't mean you don't want it to be fast :)
[22:30] <asdf> ah
[22:30] <woz> Real Time Cllimate analysis
[22:30] <Superpig> asdf: example - mapping mars
[22:31] <impossible> Those Nasa fly-bys
[22:31] <spec_> if it is anything like the original ROAM, you have to store the full raw mesh in memory if not on harddrive. and storage is really the killer in GIS visualization.
[22:31] <woz> earthquake studies
[22:31] <trent> spec_: Chunked-LOD is horrible for LARGE datasets
[22:31] <trent> Anyway, I'm going to finish this last segment of the lecture up guys. Very cool demo to come for those that aren't GDMag fanboys. :)
[22:31] <spec_> trent - it's perfect.
[22:31] <Inferna|> oooh
[22:31] <spec_> Chunked LOD is the best for large++ datasets.
[22:31] * RedBeard suspects spec uses chunked LOD for his Earth visualizer
[22:31] <NeroX> I thought chunkedlod was made for large datasets and out of core terrain
[22:31] <Locke-> Who's giving the lecture here? =p
[22:32] <CodeDemon> I wish I had a subscription to GDMag :(
[22:32] <spec_> redbeard - yeah but i don't even save the full vertices. i only save heights (the order in which they appear in refinement) and decision bits so i can refine at runtime.
[22:32] <trent> Alright, the last section of this lecture is on lighting.
[22:32] <trent> There are two algorithms I'm going to be covering. The first of which is the incredibly simple Slope Lighting algorithm.
[22:33] <trent> Slope-Lighting is the kind of lighting you'd want to implement into a quick terrain demo just to impress people. It is HORRIBLE to do real-time on a CLOD mesh, but you can bake it into textures for a nice static effect, not to mention the fact that you can build it into almost any engine in less than a half hour.
[22:34] <trent> Basically, the slope lighting algorithm revolves around shading areas that don't receive light from a set light source. The entire algorithm is explained in one figure:
[22:35] <trent> You are simply checking one vertex's height value against another, and if the vertex getting tested is lower than the subject vertex, then you shade the vertex getting tested accordingly.
[22:36] <trent> The light vector given defines the direction in which the two vertex's heights are tested
[22:37] <trent> The entire algorithm is explained in full at
[22:37] <trent> This is the perfect algorithm for generating light maps for static light sources.
[22:38] <trent> RedBeard presents an interesting point: -RedBeard- and you can do it with multiple light sources of course, not just "the sun"
[22:38] <trent> The truth is, no, you cannot.
[22:39] <trent> Well, I'm sorry, I take that back.
[22:39] <trent> You can make several shading passes, but it makes the implementation of the algorithm a bit trickier
[22:43] <trent> Anyway, as I was saying, the ridiculously complex lighting algorithm I am about to present was developed by Naty Hoffman and Kenny Mitchell.
[22:44] <trent> It has been discussed in several places; such as Game Developer Magazine, Game Programminge Gems 3 and a few web sources
[22:44] <trent> This algorithm is much more useful than the Slope-Lighting algorithm if you just think slope lighting is too damn simple, or simply not robust enough to suit your needs.
[22:44] <trent> However, it is very hard for the average joe to implement.
[22:45] <trent> So, if you are interested, look in said resources for a complete overview of it. A demo of the lighting algorithm in action can be found at
[22:45] <trent> The demo, without a doubt, will cause you to drool endlessly (the lighting is that nice).
[22:45] <trent> And that, ladies and gentlemen, is your solution to terrain programming for the next couple years.
[22:46] <trent> If you have any questions or comments about this lecture, feel free to e-mail me at
[22:46] <trent> I hope you enjoyed the lecture, and thank you for your time.
[23:49] <terminate>
[23:49] <terminate>
[23:49] <terminate> the first is just trent
[23:49] <terminate> the second includes discussion
[23:49] <terminate> enjoy

Text file last modified on April 28, 2007, 10:28:24 PM, MST.

All content Copyright 2022 Andy Campbell.
Permission to reproduce content, in any format,
by explicit written permission of author only.
"I find television very educating. Every time somebody turns on the set, I go into the other room and read a book."
- Groucho Marx