7:55:28gingeraleI want to play Astral Chain again. It's too bad they never made a sequel
8:26:28gingeraleBy the way, how do you balance a k-d tree?
9:07:27shinmeraWent on a rather aimless walk. I'm quite cold now
9:08:48shinmeragingerale: uhhh. balance in what way
9:09:07gingeraleRebalance when you add or remove nodes into the tree
9:11:07shinmerainserting just does the standard tree strategy of traversing until you reach the deepest fit and adding it to the leaf. If the leaf's too big, split the leaf
9:11:56gingeraleWhat if you re-insert something because it moved in space?
9:12:51shinmerathe easiest is to just remove and reinsert, keeping in mind the tallest bounding box that still fits
9:13:57shinmeraI don't know what the "optimal strategy" is, but you don't need to do stuff like rotating nodes or whatever that happens in balanced trees
9:14:29gingeraleHmm.. I feel it might become slanted over time but I suppose it's not a big worry unless the tree's big.
9:15:13shinmerathat's a problem with all space partitioning schemes. you either make each update expensive, or the tree deteriorates over time
9:15:44shinmeraI don't know if this is the case for kd, but often computing an optimal tree is very expensive
9:16:06shinmeralike, bsp-trees are a good example, they're pretty much only used for ahead-of-time
9:16:19shinmerathey're great for querying, but building them is costly