Questions tagged [kd-tree]

A k-d tree is a spatial partitioning data structure used to organize points in k-dimensional space.

Filter by
Sorted by
Tagged with
0 votes
1 answer

Why do KD trees put the median split exactly on a point?

I've understood that KD tree split points using the median while cycling on each axis. I've also understood that at each node traversal, a nearest search must use a sphere to store to nearest neighbor ...
jokoon's user avatar
  • 5,243
14 votes
2 answers

Fully dynamic KD-Tree vs. Quadtree?

Working on my game, I'm at the point where I need to track all of the units in the world so that I can do nearest-neighbor checks for combat. This is an RTS-like game, with potentially thousands of ...
Nairou's user avatar
  • 584
5 votes
3 answers

Scene graphs and spatial partitioning structures: What do you really need?

I've been fiddling with 2D games for awhile and I'm trying to go into 3D game development. I thought I should get my basics right first. From what I read scene graphs hold your game objects/entities ...
tapirath's user avatar
12 votes
1 answer

What is the kd tree intersection logic?

I'm trying to figure out how to implement a KD tree. On page 322 of "Real time collision detection" by Ericson The text section is included below in case Google book preview doesn't let you see it ...
bobobobo's user avatar
  • 17k