[ROAM Algorithm Homepage] [ROAM Algorithm Version 2 work in progress]
Subject: Re: ROAM 2.0 textures Date: Sun, 29 Dec 2002 12:35:31 -0800 From: Mark DuchaineauTo: XXXXXXXXXXXXXXXXXXXXXXXX Hi Nicholas, I'm glad to hear that my previous notes to you were of use. You are correct that textures are somewhat more challenging to get right than the basic diamond data structures. Certainly if you want any significant detail, then a single large texture will not work. Let's consider a few possible solutions. What some have suggested is to divide your terrain into a fixed set of square tiles, and provide variable resolutions on those tiles (example: 4x4, 8x8, ... 1024x1024). Do mipmapping on these. Load the finer res only when you estimate that the mipmapping will actually access it, otherwise back off to a lower res version. This offers a fair level of scaling to higher detail textures, but is still limited to some fixed amount of zooming in. It also gets higher latencies to swap textures as you zoom in, and the transitions (if visible, as is likely given limited i/o bandwidth), will be very abrupt over large regions. Another suggestion is to use a quadtree of textures, where each quadtree cell has a fixed number of texels, say 256x256, with coarser mip levels as well. If you estimate that a quadtree cell's texture will be access in mip mapping at a finer resolution that it is currently, then it should be split. If none of a cell's children will be accessed at their finest resolutions, then that cell should be merged. This is quite scalable, but makes factor-of-four jumps in resolution, which can cause somewhat high latencies and large jumps in memory use when only a few texels are accessed at fine res, and the mip blend factor has only a tiny weight on the finest res. Also you require mip mapping for this to be high quality, which can slow performance on What I have been using is something that is a natural match to the diamond data layout. When you split/merge the diamonds for triangle rendering purposes, you can have textures associated with the diamonds somewhat higher up in the hierarchy (just add a texture add-on field to the diamond data structure, which is NULL when not in use). Recall that a diamond has four corners {a0,a1,a2,a3}, listed in counterclockwise order, where a0 is the quadtree parent, a1,a3 are the parents, and a2 is an older ancestor. A texture is just an NxN array of texel values indexed by (i,j) with i,j in {0,1,...,N-1}. Let's glue these two ideas together by associating the i axis with the a0->a1 axis, and the j axis with the a0->a3 axis, for the following diamond d: a2 /.\ / . \ / . \ a3 d a1 +- \ . / -+ |\ \ . / /| j \./ i \ a0 / This is the central idea, but we need to define more precisely where the texel values are located, how they map to (u,v) floating-point texel coordinates, how the low-pass filtering is done, and how the texture split/merge decisions are made, and finally how a triangle's (u,v) coordiantes are determined. First the (i,j) layout. Let's say N=128, and let's say you are doing bilinear interpolation between texel values (*not* nearest, which gives lower quality). Then the (i,j) grid must exactly cover the diamond area, meaning that the texture is like a little piece of graph paper with 127x127 cells and each texel value is like a vertex at the corners of those cells in a 128x128 array. I'll rotate the previous figure clockwise 45 degrees to show this layout: j=127 -> a3--o---o---o-...-o---a2 | | | | | | | | | | ... | | | | | | | | o---o---o---o-...-o---o | | | | | | | | | | ... | | | | | | | | o---o---o---o-...-o---o | . | | | . | . | . . . | . | | | . | . | j=1 -> o---o---o---o-...-o---o | | | | | | | | | | ... | | | | | | | | j=0 -> a0--o---o---o-...-o---a1 ^ ^ ^ | | | i=0 i=1 i=127 There is a subtle thing with the actual floating-point (u,v) coordinates for bilinear textures, at least in OpenGL. OpenGL thinks of each texel value as being in the center of a texel. So u=0 is actually off the left of this figure by 0.5 of an i unit, and u=1 is off the right by another 0.5 of an i unit. So from OpenGL's standpoint, there are 128 i units across. Since we are not using boundary texels, those extra half an i unit areas are not meaningful, and the (u,v) coordinates that we use are in the range [0.5/128.0,127.5/128]. We have just defined a diamond texture hierarchy. Now for low-pass filtering. Low-pass filtering is performed by wieghted averaging from fine to coarse scales. Specifically, a parent diamond texture is made from weighted averages of the values from its four kids. Let's draw the four kids {k0,k1,k2,k3} of parent diamond d as follows: o-------------a2------------o | /|\ | | / | \ | | / | \ | | / | \ | | / | \ | | / | \ | | k2 | k1 | | / | \ | | / | \ | | / | \ | | / | \ | | / | \ | |/ | \| a3............d.............a1 |\ | /| | \ | / | | \ | / | | \ | / | | \ | / | | \ | / | | k3 | k0 | | \ | / | | \ | / | | \ | / | | \ | / | | \ | / | | \|/ | o-------------a0------------o After flipping the i,j indices of the kids to this orientation, and overlapping the values on their boundaries in the center (example, i=127 for k3 is the same as i=0 for k0), then you have a total of 127+126=253 texel values and 252 texel cells on each side. The texel values from diamond d form a checkerboard pattern within these kid texel values. The (i=0,j=0) texel for parent diamond d is matched to the glued kid texel value (i=127,j=0). The (i=1,j=0) texel value in d is (i=128,j=1) in the glued kid texel value array. Similarly, (i=0,j=1) maps to (i=127,j=1). This parent (i,j) to glued-kids (i,j) mapping is linear, and you can deduce what it is from the facts we just stated. That is enough to do simple subsampling. For higher quality, use the following weights: 1/8 1/8 1/2 1/8 1/8 where the 1/2 value is placed where you would have taken your subsample. You will notice that, on the texel values at the four corners of diamond d, that one of the finer-res texel values is missing. In that case change the weighting as follows (this is for a0 -- a1,a2,a3 are similar): 1/7 1/7 4/7 1/7 0/7 The next steps are selecting texture LODs based on geometry and viewpoint, and computing the (u,v) coordinates for the triangle vertices. I'll leave that for a later note when I get back from a family trip a week from now. Please let me know how things are going and send a reminder in one week for me to finish this note...thanks! Cheers, --Mark >Subject: Hello again >Date: Mon, 23 Dec 2002 22:33:54 +1100 >From: Nicholas Cooper >To: duchaine@llnl.gov > >Hello again, your previous responses have been incredibly helpful, so here >I come to ask you again about ROAM 2.0. > >There is only one, but quite difficult problem this time, and that is >concerned with texturing the mesh. My problem is I would like to have 1 >large texture for the entire terrain because it would be very simple to >implement, but I'm afraid texture resolution hasn't approached what is >required just yet, so my problem is then how can I tile textures across >the terrain [not the same texture], with just for example, a 512x512 >texture for every 128x128 heightmap points, perhaps even a quadtree >like structure for texture level of detail. What do you think, and >how is it possible to achieve this? > > Thankyou in advance > Nicholas Cooper
-- Mark Duchaineau
Updated 2003-02-20 -- duchaine@llnl.gov