Jump to content
  • Advertisement
Sign in to follow this  
Lode

quadtree question

This topic is 4771 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

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.
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?

[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.]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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...)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 :)

Free Image Hosting at www.ImageShack.us

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!