As for sharing code... I only asked for your code, because I wanted to help you to fix that bug. I never wanted to exchange code in the first place. Normally, I don't have any problems with sharing code. But in the case of my terrain engine, I really *can't*. Snippets would probably be okay, but it depends on what snippets you are interested in. Tell me what you are looking for, and I'll see if I can help.

As for the culling flaw... The CubeInFrustum() function has the exact same problem. Have a look at the following image: http://www.thecore.de/TheCore/flaw.jpg

This image shows a top-down view of a viewing frustum. The blue AABB will be reported as partially visible, even though it is invisible. The problem is, that for each plane, there always a point of the AABB that is in the "inside"-halfspace, and therefore there's no case where *all* points of the AABB are "outside" of any plane.

This flaw is not a bad thing, if you are using hierarchical culling, because the AABBs become smaller the deeper you descend into the quadtree, and therefore the possibility for this special case to occur is quite small. In any case, these AABB culling algorithms will perform much faster than an exact AABB culling algorithm. In other words, you are using the right algorithm here, even if it has this flaw.

BTW, the same problem exists with spheres and OBBs.

I like how my terrain is developing at the moment, but there is one thing
that is bothering me. It's how I access my AABB info. It is wasting
a lot of memory. This is my basic structure:

struct QUAD_AABB {

D3DXVECTOR3 min_aabb;
D3DXVECTOR3 max_aabb;
BOOL visible_flag;
};

struct QUAD_NODE {

struct QUAD_AABB *aabb;
};

struct QUAD_TREE {

struct QUAD_NODE *nodes;
};

For example, for a 5x5 heightmap, I create an array of quad nodes:

QUAD_TREE quadtree;

// 25
quadtree.nodes = new QUAD_NODE[5*5];

But I only need to use 5 of these array entries for my AABBs.
This is for 4 leaves + 1 root. For these 5 entries, I allocate my
AABB data.

quadtree.nodes[i].aabb = new QUAD_AABB;

The rest of the entries (20) is wasted space, about 80 bytes of NULL pointers.
For a 1025x1025 heightmap, this is over 1MB of wasted space.

I do this because I want to relate the AABB array index with
the node array index, which are the same, so I know where the
AABB data is.

Can you suggest a better way to do this?

Suppose you have an apple. You can now go ahead and break this apple up into two pieces. Each of these pieces can in turn be broken up into two new pieces, which can again be split into two new pieces each... and so forth.
You can illustrate this behavior with a diagram: http://www.thecore.de/TheCore/tree.jpg

Note, that this diagram sort of looks like a tree (if you turn it upside down). The colored dots are the so-called nodes, and these nodes are connected by branches. The blue node, which represents the initial apple, is the so-called root node, the red nodes are called interior nodes, and the green nodes are called leaf nodes.
The important thing is that each node (except the leaf nodes) is split into two new nodes.

More generally, we can say that a tree is made up of nodes that are connected by branches, where the following conditions need to be satisfied:

[1] There's only one root node.
[2] Each node can be split into any number of child nodes. In the case of our apples we split each node into two child nodes, but that was just an example (I had to start somewhere
[3] Each node has exactly one parent node. The exception is the root node which has no parent node.

Our apple tree is called a binary tree, because each node is split into up to two child nodes (binary means "2"). In a quadtree (quad means "4"), each node is broken up into up to four child nodes. In an octree (octal means "8"), each node is broken up into up to eight child nodes.

In other words, the name of a tree normally comes from the maximum allowed number of splits per node. It's the programmer who defines this "maximum". In the case of our terrain we decided it to be "4" (a quadtree).

Now you (hopefully) know what a quadtree is. There's nothing more about it. Quadtrees can be used for a huge variety of things, like 'displaying' terrain on the screen, but that's another story. I'd prefer not to explain this terrain stuff in more detail, but I'll give you a small example:

Suppose you have a square-mile of terrain. You can enclose this area with a square-shaped fence. This outer square represents the root node of the quadtree. Now you can go ahead and split this outer square into four new squares of equal size, and these new squares can again be split into four new squares each, and so on. In other words, you are creating a hierarchy of squares, and this hierarchy is used to determine which pieces of the terrain are visible on the screen (and hence need to be rendered).

Yes, you are wasting major amounts of memory there. Remember the recursive quadtree traversal function I gave you? You use that one to do the culling.

Now let's have a look at the function header again:

void traverse(int colCenter, int rowCenter, int halfSize)

The above almost defines the AABB (except for its height):

aabbMin.x = colCenter - halfSize;
aabbMin.y = ????
aabbMin.z = rowCenter - halfSize;

aabbMax.x = colCenter + halfSize;
aabbMax.y = ????
aabbMax.z = rowCenter + halfSize;

All you need to do now is to find a good way to fill aabbMin.y and aabbMax.y. There are several approaches to this problem:

[1] Scan the height field for each AABB and find the minimum and maximum elevations. Obviously, this approach isn't exactly great, so forget this as quickly as possible.

[2] The second solution is to set aabbMin.y to the minimum elevation in the entire terrain, and to set aabbMax.y to the maximum elevation in the entire terrain. This solution is far from perfect, but it can be okay (depends on your needs).

[3] A quadtree with N levels has ((4^n)-1)/3 nodes. You can now allocate an array with ((4^n)-1)/3 elements, where each elements contains the aabbMin.y and aabbMax.y of the corresponding AABB. This way you wouldn't waste any memory (BTW, what the heck do you need that visibility flag for???).
Of course, you'll need to find a way to determine the array-index that belongs to a particular node. This, however, should be quite easy. Let's see...

I don't give any guarantee that the following is correct.

First off, draw a 9x9 grid, and mark all nodes with a dot (use different colors - one color for each level). This gives us:

- 1 node on level #0
- 4 nodes on level #1
- 16 nodes on level #2

In other words it would make sense to have an array like this:

- index #0 belongs to level #0 (root node)
- indices #1 - #4 belong to level #1
- indices #5 - #20 belong to level #2

In other words that means: The first index that belongs to level #k is:
first_index = ((4^(k+1))-1)/3, for 0 <= k < n

You can speed this up by using a lookup table:
long indexTable[] =
{
1, 5, 21, 85, 341, et cetera
};

first_index = indexTable[k];

The next thing is to determine an offset, so that "first_index + offset = index of the element we are looking for":

colOffset = colCenter / (halfSize << 1);
rowOffset = rowCenter / (halfSize << 1);
offset = colOffset + rowOffset * (1 << level);

Then:
final_index = first_index + offset;

Note, that "halfSize << 1" is always a power of 2. Hence, there might be a way to replace the division "/" with the binary shift-right.

Please let me know, if the above is correct, because I didn't actually try it. If you can't get it working then I'll implement it myself and let you know about the results.

long indexTable[] =
{
0, 1, 5, 21, 85, 341, et cetera
};

Before, I rendered my terrain in two separate steps. I first culled
it, and then rendered the vertices. Both times I recursed the quadtree.
The first traversal set the visible flag, and the second traversal
checked the flag, and if it was set, it rendered the vertices.

I did it this way at first, because I wanted to separate rendering
from everthing else. But I see what you mean, the visible_flag is
taking up space. I can do the culling and rendering in one step
and get rid of it. As well as the min,max x,z values too.

I think I understand your explanation of converting x,y grid coordinates
into a quadnode index, but let me try go through it myself:

For a 9x9 heightmap, it has 3 levels with (4^(3) -1)/3 = 21 nodes.
so we just need to allocate 21 indices for AABB info.

To convert x,y grid coords. to the quadnode index we first divide
the x,y coords. by (halfsize * 2). Then we convert these x,y coordinates
using:

index = x + (y * (level*2));

Then we add the num. of nodes for that specific level where the node
is located. This can be pre-calculated beforehand into a table.
We should now arrive at the correct index.

Level 0 root has a halfsize of 4, so
4,4 = 2/8,2/8 = 0,0 = 0 + 0 = 0

Level 1 nodes have a halfsize of 2, so
2,2 = 2/4,2/4 = 0,0 = 0 + 1 = 1
6,2 = 6/4,2/4 = 1,0 = 1 + 1 = 2
2,6 = 2/4,6/4 = 0,1 = 2 + 1 = 3
6,6 = 6/4,6/4 = 1,1 = 3 + 1 = 4

Level 2 leaves have a halfsize of 1, so
1,1 = 1/2,1/2 = 0,0 = 0 + 5 = 5
3,1 = 3/2,1/2 = 1,0 = 1 + 5 = 6
1,3 = 1/2,3/2 = 0,1 = 2 + 5 = 7
3,3 = 3/2,3/2 = 1,1 = 3 + 5 = 8
...
5,5 = 5/2,5/2 = 2,2 = 12 + 5 = 17
7,5 = 7/2,5/2 = 3,2 = 13 + 5 = 18
5,7 = 5/2,7/2 = 2,3 = 14 + 5 = 19
7,7 = 7/2,7/2 = 3,3 = 15 + 5 = 20

You know this line is the same as converting x,y grid coords.
into a Morton index:

index = x + (y * (level*2));

level 2:
3,3 = 3 + (3*4) = 15

interleave x,y bits:
3,3 = 0 0 1 1 = 0000 | 1111 = 0x0F = 15
.....0 0 1 1

This line:

index = x + (y * (level*2));

does not create unique indices.

For example, a 17x17 heightmap, there are 4 levels, with 85 nodes.
Let's pick two different coordinates, (13,13) and (1,15).

halfsize of 1 at level 3
13,13 = 13/2,13/2 = 6,6 = 42 + 21 = 63

halfsize of 1 at level 3
1,15 = 1/2,15/2 = 0,7 = 42 + 21 = 63

They produce the same index. But using Morton indexing:

.0 0 0 0 = 0010 | 1010 = 0x2A = 42 + 21 = 63
0 1 1 1

.0 1 1 0 = 0011 | 1100 = 0x3C = 60 + 21 = 81
0 1 1 0

And I don't know what you mean by the coords. will always be
the same?? All quadnodes have unique xy grid coordinates, so they
will never have the same coords. And the only way I've found to
convert them to an unique array index is using Morton indexing.

Sounds like everything's working fine now I'm a bit curious now, so let me ask a few questions:

[1] What's the size of your terrain, and how many quad-levels do you use?

[2] Do you use strips, fans, or indexed lists to render the leaves?

[3] How many triangles are visible per frame, and what's the average frame rate?

[4] What hardware do you use?

I'm really quite curious, because I never did full-resolution terrain. I always used some kind of CLOD, and I'd like to know how your full-resolution terrain performs

Niki