Sign in to follow this  

KD Tree Traversal For Frustum Culling

This topic is 3858 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 have a small game engine I've been developing. At the moment I'm working on the aspects of visual culling and collision detection. This is my first time actually implementing these kinds of techniques so I do not know if they are the best, although I have studied enough and believe that my first stab will be with a KD Tree. I have already build most of the functionality and I'm able to load a level model and then create the KD Tree with that data. Although when trying to actually cull the geometry inside of the KD Tree against my camera frustum I have found that this is a bit more difficult then I have first imagined. My simple implementation at the moment will go through the KD Tree starting at the top. It will test all eight of the frustum corner points against the current node's plane to see if the frustum is on one side or is split, then traverse down to the children depending on the results. I quickly found out that by using this method I get false splits later down the line because I am not compensating for the sections of frustum that are being removed at each node. Instead of what I should be getting, I will get all of the leafs which are contained in a axis aligned box around the frustum. Since realizing this I have been brain storming and doing a bit of research, although I have not found an acceptable solution for my problem. For example, I could certainly calculate what points are removed and what points are created when I split the frustum at each node, although this is way to much work to really be efficient. My question is if anyone know of a good or better way to go about this which will yield the correct results. I'm sure that I'm not the only one who has run into this issue since the method should be similar to what is implemented in a BSP tree. Thanks for looking, Kiro

Share this post


Link to post
Share on other sites
The algorithm you are looking for is called 'MLRTA', there's a paper describing it by Reshetov et al., link:
ftp://download.intel.com/technology/computing/applications/download/mlrta.pdf

Share this post


Link to post
Share on other sites
Thank you very much, I have not had the time to look through all of the document yet although it appears to be exactly what I need. Once I do get sit down and write a implementation of this I will reply back and post a short description of how it works for anyone else who may later want to know about this down the road.

Happy Coding ^^
- Chase

Share this post


Link to post
Share on other sites

This topic is 3858 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this