KD-Tree

Characteristics #

1. splits don’t always happen in the middle
2. splits are axis aligned
3. splits happen in an order (eg x -> y -> z)

KD-Trees as Spacial Hierarchy #

Construction #

auto build_kd_tree_rec(Triangle* tris, Voxel v) -> Node* {
    if (good_enough(tris, v))
        return make_leaf_node(tris, v);

    Plane p = find_good_plane(tris, v);
    Voxel v_left, v_right;

    split(v, p, &v_left, &v_right);

    Triangle* tris_left  = all_tris_in_voxel(tris, v_left);
    Triangle* tris_right = all_tris_in_voxel(tris, v_right);

    return make_inner_node(p,
                           build_kd_tree_rec(tris_left,  v_left),
                           build_kd_tree_rec(tris_right, v_right));
}

auto build_kd_tree(Triangle* tris) -> Node* {
    Voxel v = whole_scene_voxel();
    return build_kd_tree_rec(tris, v);
}

Generating split planes #

Chose planes that are aligned with faces of objects’ bounding boxes.

Finding good split planes #

1. generate candidate split planes
2. evaluate a “cost” for each candidate depending how good/bad the objects are split
3. choose the one with the lowest cost

The cost function for split planes #

• The cost of a region with more objects should be higher

• large regions should only have a few objects, as the are hit by many rays

  

with:

• traversal time
• probability that a ray hits region a (proportional to its surface/volume compared to b)
• number of objects in region a
• intersection time

Construction #

auto build_kd_tree_rec(Triangle* tris, Voxel v) -> Node* {
    if (good_enough(tris, v))
        return make_leaf_node(tris, v);

    Plane p = find_good_plane(tris, v);
    Voxel v_left, v_right;

    split(v, p, &v_left, &v_right);

    Triangle* tris_left  = all_tris_in_voxel(tris, v_left);
    Triangle* tris_right = all_tris_in_voxel(tris, v_right);

    return make_inner_node(p,
                           build_kd_tree_rec(tris_left,  v_left),
                           build_kd_tree_rec(tris_right, v_right));
}

auto build_kd_tree(Triangle* tris) -> Node* {
    Voxel v = whole_scene_voxel();
    return build_kd_tree_rec(tris, v);
}

Generating split planes #

Chose planes that are aligned with faces of objects’ bounding boxes.

Finding good split planes #

1. generate candidate split planes
2. evaluate a “cost” for each candidate depending how good/bad the objects are split
3. choose the one with the lowest cost

The cost function for split planes #

• The cost of a region with more objects should be higher

• large regions should only have a few objects, as the are hit by many rays

  

with:

• traversal time
• probability that a ray hits region a (proportional to its surface/volume compared to b)
• number of objects in region a
• intersection time