quadtree question
I'm drawing terrain without using any culling against the viewing frustrum or anything, so basicly every triangle is being drawn all the time. I get 90 fps with 64x64 terrain and only 24 fps with 128x128 terrain.
To improve speed I thought about using quadtree, but there's one thing I wonder:
How to test if a square part of the terrain is visible or not? I have no clue. I only know that just testing of the 4 corner points are visible is not good at all because it's possible that they aren't visible while a part of the square is. Oh and it also has a heightmap so that makes it even harder.
You're right that testing the corners isn't enough. You'll need to build a bounding representation of your terrain pieces. A good one for terrains is Axis Aligned Bounding Boxes. To create an AABB you basicly just get the maximum and minimum values for each axis for all of the vertices in each quadtree node. You can then test your AABB (or quadtree of AABBs) against the frustum.
There's quite a bit of info and code on the web about AABBS, so you should be able to find better explainations than mine.
There's quite a bit of info and code on the web about AABBS, so you should be able to find better explainations than mine.
Hi. It's really late so I need to make this short - if you need more help then say so and I'll elaborate in the morning.
What you need to do is 'build' a quadtree from your heightmap. This means that you need to fill out all the layers until you reach some arbitary limit. Then, you construct a model of the frustrum(do a search for frustrum culling with google), and check if the current level is fully or partly inside the frustrum. If the level is fully within the frustrum, render the whole thing. If it's partly inside, repeat this process on it's four children. If it's fully outside the frustrum, then it isn't visible and can be thrown away(or rather, ignored until the view frustrum changes(you move the camera).
From my experience, a pure heightmap isn't going to be much good once you want to make the rendering a bit more effective. It might be good to have to perform terrain colissions and such though.
Hope the explanation helps,
Eric
What you need to do is 'build' a quadtree from your heightmap. This means that you need to fill out all the layers until you reach some arbitary limit. Then, you construct a model of the frustrum(do a search for frustrum culling with google), and check if the current level is fully or partly inside the frustrum. If the level is fully within the frustrum, render the whole thing. If it's partly inside, repeat this process on it's four children. If it's fully outside the frustrum, then it isn't visible and can be thrown away(or rather, ignored until the view frustrum changes(you move the camera).
From my experience, a pure heightmap isn't going to be much good once you want to make the rendering a bit more effective. It might be good to have to perform terrain colissions and such though.
Hope the explanation helps,
Eric
Quote:I'm drawing terrain without using any culling against the viewing frustrum or anything, so basicly every triangle is being drawn all the time. I get 90 fps with 64x64 terrain and only 24 fps with 128x128 terrain.Before making a suggestion I have one question: what constraints does your camera have on it? For example, can it roll side to side like in a space shooter, or is it a 'no roll' camera like in an FPS?
To improve speed I thought about using quadtree, but there's one thing I wonder:
How to test if a square part of the terrain is visible or not? I have no clue. I only know that just testing of the 4 corner points are visible is not good at all because it's possible that they aren't visible while a part of the square is. Oh and it also has a heightmap so that makes it even harder.
[Edit: Oop, beaten. You might still tell us about your camera, as there may be some shortcuts you can take if it's an FPS style camera.]
The camera has no constraints at all, it can roll, yaw, pitch, fly high above the terrain, and it can also change FOV on the fly, zoom in/out, and skew. The terrain too can rotate, so it's possible to use it as fake "displacement mapped" brick wall if you give it a brick pattern and put it vertically against a wall.
Quote:The camera has no constraints at all, it can roll, yaw, pitch, fly high above the terrain, and it can also change FOV on the fly, zoom in/out, and skew.Right, I knew that - we were discussing it in your other thread.
In that case you'll need a general solution. There are different ways to build the frustum in world space, but my favorite method is detailed here. It's nice because it handles any combination of camera and projection transforms uniformly.
Once you have the frustum planes, I think the other posters pretty much summed it up. You want to build an AABB tree out of your terrain and then cull by AABBs. In the case of the terrain you can take some shortcuts; the extents of the AABBs in two of the three dimensions can be computed in the same way you'd construct a quadtree, and the third extent can be computed from the minimum and maximum height in that cell. (If that makes sense...)
Quote:Original post by Lode
How to test if a square part of the terrain is visible or not? I have no clue. I only know that just testing of the 4 corner points are visible is not good at all because it's possible that they aren't visible while a part of the square is. Oh and it also has a heightmap so that makes it even harder.
Since you can roll the camera, you need to do a full 3D test using an AABB for each quadtree node (as mrbastard and jyk suggested) It is simple to test an AABB against a frustum: if all of the corners of the AABB are outside of any frustum plane, then the AABB is outside of the view frustum, otherwise it might be visible. This isn't perfect because it will say that some regions are visible when they really aren't, but that should not be a problem.
Thanks for the help, I'll look into AABB and getting the frustum planes tomorrow, I hope they'll help increasing the framerate. I'm off for today.
I'll show what I got so far in a screenshot, but do ignore the ugly testing textures :)
I'll show what I got so far in a screenshot, but do ignore the ugly testing textures :)
You can also test your AABB against the frustum using the separating axis test, which only requires two dot products per plane and is very fast. There are other optimizations you can employ, but a simple implementation should work just fine. As John said, these methods will return some false positives, but this is usually ok for frustum culling purposes.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement