# kd-tree triangle selection

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

## 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 on other sites
Hi, this is an article about a raytracer, and it includes a description of kd-trees, so it might be useful for you.

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

1. 1
Rutin
47
2. 2
3. 3
4. 4
5. 5

• 13
• 10
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632994
• Total Posts
3009769
• ### Who's Online (See full list)

There are no registered users currently online

×