Hooking up ROAM base triangles from tiles

The first step in performing display optimization of .qtile geometry+texture, after reading in the raw buffers, is hooking up bintree triangles (two per tile) to form a properly-connected base (coarsest-level) mesh.  Each tile is a quad face as part of an oriented surface (right-hand rules apply when appropriate). The arrays are laid out with the x (or u or i) axis going from edge 3 to edge 1, and the y (or v or j) axis going from edge 0 to edge 2.

The LibGen source code includes tile2qtile.l, which reads a .tile file and converts it to a binary form (.qtile files) with a texture computed from the .tile normals. Also included is a reader in qscene.l that takes in this .qtile file and creates a base mesh with OpenGL textures loaded and the bintree base mesh all hooked up properly.

On a general surface there is no single "alignment" or (u,v) parameterization.  "Orientation" does not mean we can put a single (u,v) parameterization on the surface, just that locally you can march around the surface and not get confused as to which side is which. You must use array/uv indexing only locally within a tile's array. To get neighbors you should build links from the top down as you subdivide. The main trick is to get the connections for the top-level bintree root triangles.  Then the usual ROAM split/merge rules work just fine.

Here's how this works. Let's suppose you have a tile and its neighbors. First create all the bintree triangles within the tiles, without hooking them up. Let's always do it this way:

    |      2      /|
    |            / |
    |           /  |
    |   q0     /   |
    |         /    |
    |        /     |
    |       /      |
    |3     /      1|
    |     /        |
    |    /         |
    |   /    q1    |
    |  /           |
    | /            |
    |/     0       |
Now that all the triangles have been put in place, let's hook them up. First, a bit on notation: q's are bintree triangles, qt's are tiles. A qt has a list of neighbor tiles qt->qt[0..3] and edge indexes within the neighbors that point back qt->qt_ei[0..3]. A q has links q->q0, q->q1 and q->qb which are the left, right and base neighbors:
                         / \
                  q->q0 /   \ q->q1
                       /     \
                      /   q   \
                     /         \

One pass through the tiles will work. For each tile you set the left (->q0), right (->q1) and base (->qb) links as follows:
    // hook them all up
    for (qt=qs->qt0;qt;qt=qt->qt1) {
        q0=qt->q0; q1=qt->q1;
        q0->qb=q1; q1->qb=q0;
        if (qt->qt_ei[0]<2) q1->q1=qt->qt[0]->q1; else q1->q1=qt->qt[0]->q0;
        if (qt->qt_ei[1]<2) q1->q0=qt->qt[1]->q1; else q1->q0=qt->qt[1]->q0;
        if (qt->qt_ei[2]<2) q0->q1=qt->qt[2]->q1; else q0->q1=qt->qt[2]->q0;
        if (qt->qt_ei[3]<2) q0->q0=qt->qt[3]->q1; else q0->q0=qt->qt[3]->q0;

Contact Information

Mark A. Duchaineau -- duchaineau1@llnl.gov

Updated Dec 21, 1999