Thread: Solution to earlier quad-tree culling

  1. #1
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001

    Solution to earlier quad-tree culling

    Many of you who have been here for some time know I've been working on a quad-tree terrain renderer. My early version had serious problems with the quad-tree frustum culling code.

    Well I've been doing research on procedural texture generation and other types of texturing and came across an article on gamedev that explains my earlier problem.

    I was not 'looking' for the solution but rather looking for a way to generate textures inside of my pixel shaders and then output them to the screen. What this means, I think, is no more SetTexture() calls. Rather I 'tell' the video card what should be there. I'm still not exactly sure how it works or if you have to start out with a blank texture and then pass that into the shader? I just don't know, but I'll figure it out.

    Anyways this quote:
    I'm progressing well on the terrain integration. I have fixed a problem in the frustum culling code, which caused some planets to disapear when they were close to the edge of the screen. This actually wasn't a bug, but a restriction that i was unaware of, to the standard frustum culling algorithm ( the bbox vs 6 planes one ) regarding on how close the znear plane can be, which i fixed by adjusting the distance to the znear plane.

    The two screens above are again at sunset ( or close to ), to "hide" the lack of detail texture on the terrain ( yeah i'm cheating ). The terrain is still very simple, until i add all the details and noise back.
    Was the exact issue I was having. And the thread earlier about the Z buffer issue with very close Z near's is the EXACT solution I needed. It seems that when the z buffer near plane is too close, the precision in a float falters as you move off into the distance. Well if you understand 3D, you realize that most of what is culled is on the edges of the screen. The bottom edge is going to be the most precise while on the ground which is why it worked. The left and right edges will lose precision as you move up the screen and eventually it will be so far off that areas will 'fail' the bbox test when they should pass it.

    If you also recall from my earlier posts when you viewed the terrain from above looking down, all edges failed. This now makes sense. This was due to the fact that all the culling was happening in the distance since I was above the terrain looking down. So the precision really caused a lot of problems.

    I'm going to re-code the entire quad-tree culling algo with my new Z distances, ambient/diffuse/specular/bump mapping shaders combined with a sky-scattering article I found on ATI's website from some time ago. The math is a bit heavy but I'll figure it out.

    Also I found an easy way to do sphere texturing for planets. Instead of doing spherical mapping which distorts no matter what, I'll environment map the sphere using a distorted cube map. Then when I texture it I'll use a environment map shader that pulls from a cube map. It should work correctly w/o the distortion issues.

    Here are some pictures of the problem I was having with my first version of the terrain system.

    The first image clearly shows the problems.

    The second image does not show the issue b/c it was taken when the camera was not moving. It was only occuring when the camera was moving or rotating. The second image also shows the power of the quad-tree. This is a 2048x2048 height map on a GeForce 3 card with 64MB RAM and NO shaders. My current system now runs at 350+ FPS with a brute-force 256x256 grid. I can't wait to see what the quad-tree does to it.
    Last edited by VirtualAce; 03-12-2011 at 11:42 AM.

  2. #2
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Hehe, that's a kick in the pants aint it? When you have a problem with one system, and you find out it's not's just that another system isn't quite working right.
    no more SetTexture() calls
    No more slow SetTexture calls yes, but also a lot of pixel processing, which will bog down another part of the pipeline. That's not to say it isn't going to be awesome or perform horribly.

    With all this graphics works you're doing Bubba, you NEED to get a new card ;-) I'm waiting for a DX10 card.....maybe even with 1GB of vram. That would be sweet.

  3. #3
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    My old card was the GeForce 3, my new card is the GeForce 7800 GS. There is no way I'd ever get 350+ FPS on a GeForce 3 with a 256x256 brute force grid, shaders, and 12500 trees - also brute force.

    That's what amazes me. This card does brute force better than some cards do quad trees.

    Brute force is not all that bad for some games and I believe many of them use it. Most FPS games are happening in tight, controlled sections of terrain and/or buildings. Very rarely in an FPS (save for Joint Ops) do you get huge vistas of terrain. I remember MOHAA on the Normandy level when you could see the edges of the ocean you were coming in on. Pacific Assault does not do much better. So most of them are cramming as many polies as they can down your throat - but they are doing this all at close range which anybody can do.

    Now games like FarCry, Joint Ops, Delta Force 3 and BHD, Pacific Fighters, Train Simulator, Microsoft Flight Simulator 2004, etc, etc cannot just cram as much as they can at close range. These game probably have some of the best and most efficient graphics algorithms out there - Joint Ops and the Delta Force Xtreme (old Delta Force 1 missions in a new updated Joint Ops engine) games are nothing short of amazing. All those graphics, explosions, sounds, and other peeps running around blasting the hell outta each other...and still good framerates. Joint Ops can stutter some, but the stutter has been fixed in Delta Force Extreme. Two thumbs up to Novalogic.

    Also MS Flight Simulator is the best at caching in new terrain and caching old out while maintaining frame rates. It does take a hefty system, but man does it look good.

    My feeble attempts here do not come close to these engines, but someday hopefully it might.

    My problem is I can go so far with graphics but without a good artist my work suffers. Writing shaders is only the beginning - you gotta have great art and top-notch models to use them on. Also graphics algorithms have to be dead on or you get some really odd issues. So graphics knowledge only takes you so far - the rest is raw talent.
    Anyone can add/subtract vectors, perform transformations, concatenate matrices, etc, etc - but only the talented can put all this to use and create something amazing.

    I tip my hat to all those companies who create the types of games that really stretch the computer far beyond what hardware can realistically do. And yet they still get it to work, look great, and maintain interactive frame rates.
    Last edited by VirtualAce; 08-09-2006 at 11:18 PM.

  4. #4
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Where circles begin.
    I still don't see what's wrong with just storing the terrain in VRAM (as it's static anyway), rather than using quad-trees, octrees, or whatever you wish to use. I must be missing something here.

    Quote Originally Posted by Bubba
    Anyone can add/subtract vectors, perform transformations, concatenate matrices, etc, etc
    Yep, even my Grandmother.
    M.Eng Computer Engineering Candidate
    B.Sc Computer Science

    Robotics and graphics enthusiast.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problem in creating a tree
    By Lorin_sz in forum C++ Programming
    Replies: 2
    Last Post: 09-26-2005, 01:28 PM
  2. OpenGL, loading BMP Textures?
    By Zeusbwr in forum Game Programming
    Replies: 12
    Last Post: 12-09-2004, 05:16 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Tutorial review
    By Prelude in forum A Brief History of
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  5. Request for comments
    By Prelude in forum A Brief History of
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM