   bsp balancing heuristic
  I'm making BSP trees out of all my models for fast ray casting. However, I'm having trouble with picking partitioning planes. Because this is for ray casting, all I care about is balance (I've read it's possible to do ray casting without splitting, so I just store references to the same triangle twice if a triangle is split). My current algorithm is:select_partition( triangles )    best_plane = none    for each P in triangles   for each T in triangle  determine whether T is in front or behind P   if P is the "most balanced" so far, best_plane = P    return best_plane Of course, this causes my makeBsp algorithm to be O(n^3), which takes way too long for large models. Obviously I need some sort of heuristic to bring it down to O(n^2), which is more acceptable. What heuristics are generally used to attempt to balance a BSP tree? I was thinking that it might be possible to compare the volume of space in front and behind the plane and use the plane where the ratio between the two volumes was closest to 1. However, I'm not entirely sure how I would compute the volumes, since they are defined by planes, so computing them would bring me back up to O(n^3). I could approximate them using aabbs, but that would work poorly with non-axis-aligned partition planes. I could try to find some way to align bounding boxes to the planes; I'm currently trying to figure out how to do this. Anyway, how is this usually done?OR, alternatively, should I even use BSPs? What about Kd-trees - those seem to be more common these days.   
  For static scenes in ray tracing, kd-trees yield, the best results on average, when used with surface area heuristics (SAH, see Havran et al). A equi-balanced kd-tree is far inferior to a tree where there are large empty spaces near the top of the tree (i.e., large empty space can be skipped, and you can concentrate on the relevant parts of your tree).kd-trees are just a special case of bsp-trees, with the advantage that intersecting the splitting planes is lighting fast, and the nodes can be made down to as much as 8 bytes (see also Ingo Wald's thesis, which in the meanwhile is a bit dated, but gives still a great introduction, see also ompf.org/forum).   ;  Thanks, I will look into that. By ray casting, I actually meant for collision detection-related tasks, rather than ray tracing. Are surface area heuristics still recommended for that?   ;  Sure :)The task of SAH is: Find the shortest path through the data-swamp towards the temples of interest.edit: That is, of course, SAH is not easy to implement. And as long as your ray-caster is not overall performance bottleneck, "naive" trees might be good enough (conforming to YAGNI paradigm)   ;  BSP and KD-Tree are useful for ray-vs-tree checks, if your collision detection is rather object-vs-tree, then you might have faster results with AABB or OBB trees, just 'cause you can test more complex primitives vs primitives (e.g. a AABbox vs box is faster than a hierarchy of split planes vs box).This is especially true if you have big hiearchys that cause lot of cache misses. There are some paper that even suggest to flatten binary AABB-trees to 4 or 8 AABB per hierarchy level for better cache and vectorization usage.AABB contrustion also tends to be faster, a perfectly made bottom-up AABB-Tree also cost's O(n^3) in theory, but you can cache quite some values to make it nearly O(n*n).   