Questions tagged [kd-tree]
A k-d tree is a spatial partitioning data structure used to organize points in k-dimensional space.
5
questions
0
votes
0
answers
28
views
Spatial Partitioning: Strategy for obtaining current room (x,y,w,h) given a position (x,y)
In my game, dungeons are represented by rooms and hallways, both defined like this:
...
0
votes
1
answer
1k
views
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 ...
- 5,253
14
votes
2
answers
15k
views
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 ...
- 604
5
votes
3
answers
4k
views
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 ...
- 89
12
votes
1
answer
3k
views
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 ...
- 17.1k