[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 Duchaineau
To: 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