Sign in to follow this  

kd-tree triangle selection

This topic is 3629 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

Hi guys, I'm researching into kd-trees for my hobby game where I'll be splitting arrays of triangles (levels). As I understand it, you simply split each node into 2 with either the world's x, y or z axis, but one part I don't get is how to choose the splitting plane. All sites I've looked at describe the median of a group of points, but I'm using triangles so what algorithms can I use to determine this plane?

Share this post


Link to post
Share on other sites
That article was perfect, thanks :)

I'm wondering though, after reading that article, if it's the best way to go for me. I've got a futuristic racing ship on a track suspended in air (so it's only the track) and I was using an octree, and a kd-tree aims to increase empty space in each node. I'm not sure that will help me, as most of the time (99%) the ship will be on the track so instead of trying to avoid polygon collisions by maximising empty space in nodes, I'm definately going to be colliding with polygons every frame, and splitting polygons without much space in a nodw would be very similar with either an octree or a kd-tree no?

Are kd-trees faster for traversing? If they are that would give me a reason to implement it I guess.

Share this post


Link to post
Share on other sites
I've decided I'll give it a shot, to at least compare it to my octree. The problem now is that all sites I've found (including the link above) deal with separating objects. I want to separate the actual triangles within a single mesh, and haven't found an algorithm to choose a separating plane based on that. Any clues?

Share this post


Link to post
Share on other sites
I am developing a raytracer, and I don't know much about space partitioning, but I think you should threat every single triangle of the mesh as a separated object.

Share this post


Link to post
Share on other sites

This topic is 3629 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