This topic is 2 pages long:   1  2  |
Author Topic:   Heightmaps and Quadtrees
Lithium
Member
posted December 11, 2000 01:41 AM         
I was wondering if someone could please explain to me how to create a
simple quadtree (no LOD) from a (n^2)+1 x (n^2)+1 heightmap.

Also, could you tell me exactly what kind of data the quadtree nodes
should contain? If I wanted to use a large heightmap like 1025 x 1025,
how does this effect my quadtree structure?

And after the quadtree has been setup, how do I find a quadtree node
given a (x,z) grid coordinate?

Thanks.

[This message has been edited by Lithium (edited December 11, 2000).]

IP:

Sigg
New Member
posted December 17, 2000 06:57 PM            
The 1025x1025 height map represent the corner vertices of the terrain mesh (i.e. you get a 1024x1024 grid mesh). What you do is divide the terrain in four equal sized quadratic nodes, then divide the four nodes into another four nodes and countinues with this until you end up at a desired level. You must keep track of the children of each node like in a structure similar to this:

struct quad_node {

void *nodeData;

quad_node *upperLeftChild;
quad_node *lowerLeftChild;
quad_node *upperRightChild;
quad_node *lowerRightChild;
};

To find find point(X,Y), you have to start at the top of the tree and check where in the node the point lies and travel down until you reach the end of the tree.

There is must be better resources on the net (I think Tatcher Ulrich or somebody had an article on if not, then there must be some articles on [URL=http://www.gamedev.net]www.gamedev.net and www.flipcode.com).

The roam paper and Rottger paper do require a couple of re-reads before you really get the grasp of the algorithms (escpesially the roam paper)....

P.S.: PhD's are people too.....

[This message has been edited by Sigg (edited December 17, 2000).]

IP:

Lithium
Member
posted December 17, 2000 08:48 PM         
Ok, this is good, but I have a lot of very specific questions.

What I really would like to understand is the relationship between
an array's indices and a quadtree a little more. Let the array be
defined as:

heightmap[x + y*num_rows]

And the quadtree be defined as:

typedef struct _QUADTREE {

// some data //

struct _QUADTREE *quads[4];

} QUADTREE;


Couple questions:

Are the child pointers the minimal amount of data I need to create a
quadtree from an array?

I understand how to divide a quadtree into four quadrants,
by recursively creating more and more nodes, but how does this
relate to my array's indices?

If I'm able to finally build my quadtree, each node in tree
will contain "some data" to create vertices from my heightmap.
But I probably will only be interested in the leaves, or the
lowest nodes of the tree that have no children.

And consider that a 1025 x 1025 map is pretty big, these
quadtrees can't possibly store all I data I want. I would to
know the minimal amount of data I can store in my quadtree, and
create the vertices directly from my heightmap.

Some numbers:

The quadtree would have a maximum of 10 levels with 1,398,101 nodes.
How big can I allocate a data structure before Windows start complaining?

A basic quadtree data structure with 10 levels, takes up 16 bytes
for the child pointers. If I want 16 bytes for data:

32*1,398,101 = 44739232 = 42.6MB

It becomes huge.

And this is putting everything else aside, like LOD, textures,
lighting, etc.. I just want to draw a large wireframe terrain
using just a heightmap and a generated quadtree, using the least
amount of data, and no pre-calculated vertices.

Can someone help me out with a few suggestions?

[This message has been edited by Lithium (edited December 18, 2000).]

IP:

Lithium
Member
posted December 19, 2000 01:59 AM         
Anybody doing terrain??

IP:

Klaus Hartmann
Member
posted December 20, 2000 10:14 PM            
Lithium,

Building a quadtree for a 2^n+1 by 2^n+1 (like 1025x1025) height field is very easy, because the tree is already represented by the height field.

Take a sheet of paper a draw a regular grid of 9x9 data points (i.e. a top-down view of a 9x9 height field).
You can address each point in this grid by its coordinates, (column, row), where the origin (0, 0) is in the upper-left corner of the grid.
The bounding rectangle of the whole grid now represents the root node of the quadtree.
Now take a pencil with another color and subdivide the root node (i.e. the whole grid) into four equal-sized squares. That means, draw a line from (4, 0) to (4, 8), and draw a second line from (0, 4) to (8, 4).
You have just split the root-node into four children. You should also notice, that those two lines intersect at (4, 4). Please mark that intersection point with a fat dot.
Now take the yet another color, and subdivide each of the four new children. This'll result in 16 new children, and you'll have new intersection points at (2, 2), (6, 2), (2, 6), and at (6, 6). You could now go ahead an subdivide these 16 new children into 64 new children (each child is subdivided into 4 children, hence the name "quad"-tree).

Now imagine, that you height field was much larger, say 1025x1025. You can subdivide this large field in the same way as described above...
Now ask yourself the following question: Is it possible, that the intersection points are ever used twice? That is, can an additional split result in an intersection point that has already been used? Obviously, the answer to that question is NO. All these intersection points have unique coordinates in the grid.
This is great, because it means that you can uniquely identify each quadtree node by its intersection point in the height field. That means:
The root node is uniquely identified by the grid point (4, 4), which is equal to (fieldSize / 2, fieldSize / 2), where "/" denotes an integer division, and hence 9/2=4.
The upper-left child of the root node is uniquely identified by the grid point (2, 2), the upper-right child of the root node is uniquely identified by the grid point (6, 2), the lower-left child of the root node is uniquely identified by the grid point (2, 6), and the lower-right child of the root node is uniquely identified by the grid point (6, 6).
Now how exactly does the above information help you? The answer is: "You can traverse the height field in a quadtree-like fashion without actually creating a quadtree". Have a look at the following pseudo code:

void traverse(int colCenter, int rowCenter, int halfSize)
{
..// If the halfSize (explained below) is less than 1,
..// than we've exceeded the deepest possible level
..// in the quadtree. Hence, we do nothing and just return.
..
..if (halfSize < 1) return;
..
..// do whatever you want to do with the node
..
..// now descend into the children. Their "halfSize" will exactly be half
..// the "halfSize" of the current node, and therefore, we divide "halfSize" by 2.
..halfSize /= 2;
..
..// The new "halfSize" is now also the distance
..// from the current (colCenter, rowCenter) to each
..// child node. Therefore, we can just call traverse()
..// with new coordinates.
..
..// upper-left child
..traverse(colCenter-halfSize, rowCenter-halfSize, halfSize);
..
..// upper-right child
..traverse(colCenter+halfSize, rowCenter-halfSize, halfSize);
..
..// lower-left child
..traverse(colCenter-halfSize, rowCenter+halfSize, halfSize);
..
..// lower-right child
..traverse(colCenter+halfSize, rowCenter+halfSize, halfSize);
}

where (colCenter, rowCenter) uniquely identifies a node (i.e. (4, 4) for the root node), and "halfSize" is half the width and height of the node. For the root node in a 9x9 grid, the halfSize would be 4 (the distance from (4, 4) to the edges).

In order to traverse the whole tree, you call the above function like this:

traverse(fieldSize / 2, fieldSize / 2, fieldSize / 2);

where fieldSize is the size of the grid along one dimension, and it has to be 2^n+1.

I hope you were able to follow my description, because it's kinda cumbersome to explain this in words. If you understood this, then you'll notice, that you don't need a true quadtree structure (i.e. one that uses pointers to its children). Therefore, your 1025x1025 height field (including the quadtree) would cost 1025*1025*sizeof(height_field_data_type) bytes.

As for axis-aligned bounding boxes. You'll note, that it's easy to determine the width and length of any node's axis-aligned bounding box. The height of the bounding boxes, however, are a problem, because it can vary depending on the elevation in your height field. But... you say, that you are not going to use LOD. This also means, that (for performance reasons) you are not going to traverse the quadtree to its full depth. For example, you could say that the smallest quadtree nodes contain 33x33 data points. In this case, it wouldn't be a problem to store the AABBs in an array or so. For a 1025x1025 height field with a minum node size of 33x33 this would result in (4^5-1)/3 = 341 AABBs. If each AABB takes 24 bytes of memory, then you have 341*24=8184 bytes of extra storage for the AABBs.

HTH,
Niki

IP:

Lithium
Member
posted December 21, 2000 04:44 AM         
Niki, excellent.

I understand your gridspace traversal scheme and I will try to implement
it very soon. I like this uniqueness because I can store my node data
as an array too (AABBs, etc..), and they can have the same xy coordinates
as the node they belong to in gridspace. But since the nodes do not
occupy every gridpoint, there would be some empty array entries. However,
I could create an array of pointers to data, and only create the
ones I want.

I notice you stop subdividing when the halfsize reaches 1, and I think
this is convenient because a node will always lie exactly on a heightmap
coordinate in gridspace. At first I wanted to go all the way down to 0.5,
so I could draw the surrounding points as a triangle fan. But now, I think
I will stop at 1 and draw them as a batch of lists or strips.

You suggested that I should only go down to 5 levels, but I would like
to go down as far I can go for a 1025x0125 heightmap without thrashing
Window's virtual memory. I need storage for bounding boxes (24 bytes)
and clip flags (1 byte) for each node, so:

10 levels = 349525*25 = 8.3MB
9 levels = 87381*25 = 2MB

I think performance would not be so bad for ~8MB. At least it is way
better than my initial 50MB quadtree.

I am wondering if bounding spheres would be better than AABBs for
frustum culling. I would have to calculate a radius every time
from the AABB info. And I also need a center position from the AABB.
I guess I will find out soon enough.

Other things in Treadmarks come to mind, like deformable terrain
and wrapping terrain. I'm not sure how to wrap terrain using this
setup, but for deformable terrain, I would probably have to re-calculate
the bounding boxes of a node and all its children every time I deform
it. It doesn't seem too difficult.

Thanks for the great info!

IP:

Klaus Hartmann
Member
posted December 21, 2000 09:33 AM            
Lithium,

I'm glad to hear that you understood the explanation

The reason why I mentioned the 33x33 minimum has nothing to do with the memory required to store the bounding box information. My reasons are these:

[1] At some point the quadtree traversal and the culling take more processing time than the hardware needs to clip and render the triangles. Therefore, you should limit the recursion depth to some level of the quadtree (you'll have to experiment to find a good level).

[2] Hardware like the GeForce and GeForce2 like large indexed triangle strips. If you limit the node sizes to 33x33 (or something similiar), then this is perfect, because you can easily create large strips for the nodes to be rendered. The same sort of applies to hardware that prefers indexed triangle lists. It'll be much easier to generate the indices.

As for the bounding spheres... Bounding spheres are not really much cheaper than AABBs. This is especially true for terrain, because AABBs are the near-optimal bounding volumes for axis-aligned terrains. So you better stay with AABBs. Just ask, if you don't know how to quickly cull AABBs.

As for the deformation of the terrain... I wouldn't worry too much about the recalculation of the AABBs, because normally you'll only need to update a few boxes (unless you decide to change huge areas of the terrain at once). If you are changing a vertex in the middle of a node of a tree that has 5 levels, then you'll have to recalculate up to 5 bounding volumes.

IP:

Lithium
Member
posted December 21, 2000 01:44 PM         
quote:

As for the bounding spheres... Bounding spheres are not really much
cheaper than AABBs. This is especially true for terrain, because AABBs
are the near-optimal bounding volumes for axis-aligned terrains. So you
better stay with AABBs. Just ask, if you don't know how to quickly
cull AABBs.

That's a good point. Tight-fitting volumes are much better for culling.
I could be drawing less vertices, and hence faster rendering. The tradeoff
would be doing 8 point-in-frustum tests for an arbitrary box as opposed
to 1 point-in-frustum test for spheres.

Found this great page that explains it in good detail: http://www.markmorley.com/opengl/frustumculling.html

IP:

Klaus Hartmann
Member
posted December 22, 2000 12:52 AM            
Lithium,

I have had a quick look at the web-site you have mentioned, and it seems to be quite good. However, here is a slightly different approach for AABB/frustum culling, which I believe will perform a bit faster (but I'm not really sure about that, because I haven't compared the two approaches). I hope this stays readable, because it's just a copy and paste:

//-----------------------------------------------------------------------------
// Name: CullAABB
//
// Desc: Culls an axis-aligned bounding box. The return codes are:
// -- CULL_EXCLUSION (completely outside the frustum)
// -- CULL_INTERSECT (partially visible)
// -- CULL_INCLUSION (completely inside the frustum)
//-----------------------------------------------------------------------------

CullCode CullAABB(const D3DVECTOR& aabbMin, const D3DVECTOR& aabbMax)
{
D3DVECTOR minExtreme, maxExtreme;
bool intersect;

// Initialize the intersection indicator.
intersect = false;

// For each of the six frustum planes
for (int i = 0; i < 6; i++)
{
// Find the minimum and maximum extreme points along the plane's
// normal vector. Just understand this normal as a line of all
// real numbers. 0 then lies on the plane, negative numbers are
// in the halfspace opposing the normal, and positive numbers
// are in the other halfspace. The terms "minimum" and "maximum"
// should now make sense.
for (int j = 0; j < 3; j++) // for each component x, y, and z.
{
if (m_frustumPlanes[i].m_normal[j] >= 0.0f)
{
minExtreme[j] = aabbMin[j];
maxExtreme[j] = aabbMax[j];
}
else
{
minExtreme[j] = aabbMax[j];
maxExtreme[j] = aabbMin[j];
}
}

// If minimum extreme point is outside, then the whole AABB
// must be outside.
if (m_frustumPlanes[i].DistanceToPoint(minExtreme) > 0.0f) return CULL_EXCLUSION;

// The minimum extreme point is inside. Hence, if the maximum
// extreme point is outside, then the AABB must intersect with
// the plane. However, the AABB may still be outside another
// plane.
if (m_frustumPlanes[i].DistanceToPoint(maxExtreme) >= 0.0f) intersect = true;
}

// The AABB is either partially or fully visible.
if (intersect) return CULL_INTERSECT;
return CULL_INCLUSION;
}

A couple of notes:

[1] The plane equation is Ax+By+Cz+D=0. Hence, DistanceToPoint = Dot(plane.normal, point) + plane.D;

[2] The plane normals need to point away from the frustum.

[3] There are cases where an AABB will be reported as partially inside, even though it is completely outside. The performance of the above outweighs this flaw, though.

[4] m_frustumPlanes is just an array of 6 planes.

If you are going to test both approaches, then please let us know which one's faster.

Niki

IP:

Klaus Hartmann
Member
posted December 22, 2000 01:03 AM            
I forgot to mention this... The plane equations don't need to be normalized, because you are not interested in the true distance of a point to the plane. You only want to know on which side of a plane a point lies (this does not require true distances).

Niki

IP:

Lithium
Member
posted December 22, 2000 03:14 PM         
I put both routines in my program (yours and the one I found
on the above webpage) and toggled them back and forth while
flying around on my terrain. I looked at the fps and the num.
of vertices being culled, and I couldn't notice a real difference.

The num. of vertices culled was always the same for both tests,
so I am guessing the real performance is solely on how fast the
functions execute.

I don't have a profiler to get real performance statistics,
so my test isn't very accurate. But I would say yours might
be slightly faster by just looking at the code. It looks like
you only do at most 2 point-to-distance tests, while the other
one could do at most 8 for each plane.

btw, I have all my frustum normals pointing in, so I reversed
the sign on the DistanceToPoint tests, and also reversed the
comparison on the min,max extreme point test. It seemed to
work ok, but some reason, far away visible vertices were being
culled too early. Perhaps I setup the function incorrectly?

These are the lines I changed:

quote:

if (m_frustumPlanes[ i ].m_normal[ j ] < 0.0f) {

if (m_frustumPlanes[ i ].DistanceToPoint(minExtreme) <= 0.0f)

if (m_frustumPlanes[ i ].DistanceToPoint(maxExtreme) <= 0.0f)


IP:

Lithium
Member
posted December 22, 2000 07:46 PM         
I tried something different and negated the plane's normal and D value
(I think this should invert the frustum inside out) instead of reversing
the comparisons. It worked the same way as before, but still it is
culling too early for far away vertices.

Anway, something different:

Does anyone know the correct terrain scaling for Treadmark .VED maps?

I'm scaling the 0-255 raw data height by 1/4 and scaling the width, length
by both 1. The map is only stored as 1024x1024, so I had to bump it up
to 1025x1025 to work with my program. But this is too slow to view
without LOD, so I have to either increase the scaling so less vertices
are visible on the screen, or don't traverse all the way to 10 levels.

IP:

Klaus Hartmann
Member
posted December 23, 2000 01:05 AM            
Lithium, I don't know why your app culls far away vertices too early. I know that my AABB culling code is correct so that can't be it. Maybe it's a bug in the plane extraction code you are using? So here's my extraction code for verification:

//-----------------------------------------------------------------------------
// Name: CCamera::ExtractPlanes
//
// Desc: Extracts the frustum planes from the combined view/projection matrix.
//-----------------------------------------------------------------------------

void CCamera::ExtractPlanes()
{
D3DMATRIX comboMatrix;

comboMatrix = m_viewMatrix * m_projMatrix;

// Left clipping plane
m_frustumPlanes[0].m_normal.x = -(comboMatrix._14 + comboMatrix._11);
m_frustumPlanes[0].m_normal.y = -(comboMatrix._24 + comboMatrix._21);
m_frustumPlanes[0].m_normal.z = -(comboMatrix._34 + comboMatrix._31);
m_frustumPlanes[0].m_distance = -(comboMatrix._44 + comboMatrix._41);

// Right clipping plane
m_frustumPlanes[1].m_normal.x = -(comboMatrix._14 - comboMatrix._11);
m_frustumPlanes[1].m_normal.y = -(comboMatrix._24 - comboMatrix._21);
m_frustumPlanes[1].m_normal.z = -(comboMatrix._34 - comboMatrix._31);
m_frustumPlanes[1].m_distance = -(comboMatrix._44 - comboMatrix._41);

// Top clipping plane
m_frustumPlanes[2].m_normal.x = -(comboMatrix._14 - comboMatrix._12);
m_frustumPlanes[2].m_normal.y = -(comboMatrix._24 - comboMatrix._22);
m_frustumPlanes[2].m_normal.z = -(comboMatrix._34 - comboMatrix._32);
m_frustumPlanes[2].m_distance = -(comboMatrix._44 - comboMatrix._42);

// Bottom clipping plane
m_frustumPlanes[3].m_normal.x = -(comboMatrix._14 + comboMatrix._12);
m_frustumPlanes[3].m_normal.y = -(comboMatrix._24 + comboMatrix._22);
m_frustumPlanes[3].m_normal.z = -(comboMatrix._34 + comboMatrix._32);
m_frustumPlanes[3].m_distance = -(comboMatrix._44 + comboMatrix._42);

// Near clipping plane
m_frustumPlanes[4].m_normal.x = -(comboMatrix._14 + comboMatrix._13);
m_frustumPlanes[4].m_normal.y = -(comboMatrix._24 + comboMatrix._23);
m_frustumPlanes[4].m_normal.z = -(comboMatrix._34 + comboMatrix._33);
m_frustumPlanes[4].m_distance = -(comboMatrix._44 + comboMatrix._43);

// Far clipping plane
m_frustumPlanes[5].m_normal.x = -(comboMatrix._14 - comboMatrix._13);
m_frustumPlanes[5].m_normal.y = -(comboMatrix._24 - comboMatrix._23);
m_frustumPlanes[5].m_normal.z = -(comboMatrix._34 - comboMatrix._33);
m_frustumPlanes[5].m_distance = -(comboMatrix._44 - comboMatrix._43);
}

The plane normals point away from the frustum, and the plane equations are NOT normalized. Note, that "m_distance" is a rather bad term, though
I know the above is Direct3D code, but it also works with OpenGL (except for the D3DMATRIX, of course).

As for the .VED scaling... I don't know, but I'm sure someone from LDA is reading along

Niki

IP:

Lithium
Member
posted December 23, 2000 03:34 AM         

But if my frustum plane normals point in (I was already using this
setup and I don't want to change it just yet), then can't I put in
a small hack to test your function by inverting them all first?

Can a plane's normal be inverted by negating all the plane values,
A,B,C,D?

if Ax+By+Cz+D=0, then I should be able to flip the normals inside
out by doing:
-(Ax+By+Cz+D) = -0

So when I use my planes with your function, I invert them all first:

n = -n;
D = -D;

I know my frustum transformation is working correctly, because I
used it before. The AABB code from the webpage works with them ok
with no problems. I'll have to look over your code again.

Btw, I'm using D3D and I use D3DXPlaneTransform() to transform my
planes.

IP:

Lithium
Member
posted December 24, 2000 01:21 AM         
Ok, I removed all my frustum code and I am now extracting it from
the view/projection matrix, and I am using the CullAABB function
exactly how it is. No more hacks. aabbMin and aabbMax contain
the xyz min/max values of my AABB boxes. And guess what happened?
Nothing. It still culls too early. Strange thing is, if I slowly
increase my far z distance to 1000 and not move the camera, the terrain
starts to cull more and more.

The other AABB function still works perfectly, even without true
distances. I can't understand what's up with this function.

IP:

Klaus Hartmann
Member
posted December 24, 2000 01:58 AM            
I decided to experimented with my own code, and modified it so that it works with normals that point inside the frustum. It works perfectly.

What I did is the same as you did. I negated A, B, C, and D of the plane equation, and modified the culling code in the same way as you did.

Now I'm going to have a look at the plane extraction on that web-site you mentioned:

Verifying matrix multiplication... OK
Right plane... OK
Left plane... OK
Bottom plane... OK
Top plane... OK
Near plane... OK
Far plane... OK
Normalizations... OK

Okay, the code is basically identical, except that the plane normals are pointing inside.

The two CubeInFrustum() functions are also correct, but they define an AABB by its center point and a halflength, whereas in my code, an AABB is defined by its minimum and maximum points (component-wise). This could be a potential place for a code-bug. Are you sure you pass correct AABB parameters to my function?

I don't want to sound arrogant now, but I'm sure there's a bug on your end. My AABB culling code has been tested by me and a LOT of other people who used a sample of mine as a reference. I use it all the time, and I've never experienced any problems. I'm sure I could go ahead and test that CubeInFrustum() function in my code, and the results would be identical.

Personally, I only see two options here. [1] You pass wrong parameters to my function, or [2] your D3DXPlaneTransform code doesn't work as it should. May I ask what you use D3DXPlaneTransform for? Do you use it to transform the planes into object space? If that's the case, then you don't really need it, because:

[1] Extracting the frustum planes from the projection matrix gives you the planes in camera space.

[2] Extracting the frustum planes from the "view*projection" matrix gives you the planes in world space.

[3] Extracting the frustum planes from the "world*view*projection" matrix gives you the planes in object space.

Niki

IP:

Klaus Hartmann
Member
posted December 24, 2000 03:40 AM            
Almost missed your last post, because you sent it while I was writing mine

Anyway, I tried the code from that web-site, and attached two screen shots of the results.
http://www.thecore.de/TheCore/frustum1.jpg http://www.thecore.de/TheCore/frustum2.jpg

FRUSTUM1.JPG uses my code, and FRUSTUM2.jpg uses the code from that web-site.

I use a quad-tree like approach to render the quads, and that's why the blocks differ in size. Anyway, the green blocks are fully visible, and the blue blocks are partially visible. Invisible blocks are of course not shown here, but I verified that both functions return invisible blocks, too (I shrunk the frustum and rendered them in red).

Now, which image looks correct? FRUSTUM1.JPG looks correct while FRUSTUM2.JPG does not, because some of the fully visible blocks are rendered as partially visible blocks.

I'll do some further research and try to figure why one algorithm works, and the other does not. I think it's a logical bug, but I'm not sure yet. I'll let you know once I understand the problem.

Niki

IP:

Klaus Hartmann
Member
posted December 24, 2000 04:00 AM            
Okay... I found out where the difference between the two images come from... stupid really!

The problem was that my code handles arbitrary AABBs, while the other code handles ***cubes***. I changed the cube-code to handle arbitrary AABBs, and now they yield identical results. That means, you'll need to use 3 halflengths (sizes), and not only one. This proves that both algorithms are perfectly correct.

Niki

IP:

Lithium
Member
posted December 24, 2000 04:48 PM         
Ok, this might be my fault .

This is what I pass:

aabbMin contains min_x, min_y, min_z of my AABB
aabbMax contains max_x, max_y, max_z of my AABB

min_x, min_y, min_z are worldspace coordinates.
max_x, max_y, max_z are worldspace coordinates.

The AABB box is axis-aligned with x positive to the right,
y positive up, and z positive in.

y+ z+
| /
|/
+--x+

All of my AABBs can be arbitrary size.

My version of DistanceToPoint:

DotProduct(test_point, plane_normal) + plane_D

Does this look correct?

[This message has been edited by Lithium (edited December 24, 2000).]

IP:

Klaus Hartmann
Member
posted December 25, 2000 10:35 AM            
Yes, this looks correct. The problem has to be somewhere else. The question is "where?". I'm beginning to believe that the problem is not buried in the plane extraction or the culling function.
Lithium... if your test project is not too large, then you may send it to my private e-mail address (in compilable and executable form). It's got to be something simple, maybe so simple that you don't see the problem. My private e-mail address is:
mailto:k_hartmann@osnabrueck.netsurf.de

Niki

IP:

coax
Administrator
posted December 26, 2000 05:00 AM            
ok, i just gotta know, what are you guys talking about

IP:

Lithium
Member
posted December 26, 2000 05:44 AM         
Niki,

Ok, how about an exchange of code then?

After I email my project code to you, you can look it over, and send
me a simple terrain engine that you wrote with similar limited features
so I can see how it is suppose to work.

My project zipped is about 200k with one or two graphic files. I'll
try to send it to you tomorrow, so be patient.

IP:

Klaus Hartmann
Member
posted December 26, 2000 06:33 AM            
Lithium -- No way, I'm afraid I don't have anything simple and/or limited, and it would take too much time to make a special version for you.
All I have is a small AABB culling sample (the one I used to make the screen shots).

Coax -- The thread has become a multitopic thread (sort of). The main goal of this thread is to render the visible parts of a terrain by not rendering those that are invisible. We were introducing a way to quickly reject huge areas of the terrain from the rendering process. To do this, we use a so-called quadtree (a tree, where each node has up to 4 child nodes). Quadtrees basically enable us to do some fast hierarchical culling.

Niki

IP:

Lithium
Member
posted December 26, 2000 06:06 PM         
Argh. I found my bug while cleaning it up!

The two culling functions perform the same recursive subdivision of the
quadtree, and when I copied the same code over for your culling function,
I didn't change the recursive calls. So it initially called your function,
but then it recursed using the other culling function. It was a copy and
paste error. Sorry about that.

And I'm still willing to exchange some code (snippets, etc.) if you think
mine might be a worthwhile trade.

Anyway, in one of your previous posts, you said you function didn't work
in certain cases [note 3]. Can I ask in what cases does it fail to cull?

IP:

coax
Administrator
posted December 27, 2000 02:02 AM            
ok lets start with something easier whats a quadtree?

IP:

This topic is 2 pages long:   1  2