ccomparebounding-boxoctree

Get the tighest bounding box


I think the code is self explanatory:

// Set the bbox min and max of the lower node
current_min_bound = lower_get_bbox_min(buf, lower_handle);
current_max_bound = lower_get_bbox_max(buf, lower_handle);
// Set lower node bbox 
if(current_min_bound.x > leaf_node->bbox_min.x) {
    current_min_bound.x = leaf_node->bbox_min.x;
} 
if(current_min_bound.y > leaf_node->bbox_min.y) {
    current_min_bound.y = leaf_node->bbox_min.y;
}
if(current_min_bound.z > leaf_node->bbox_min.z) {
    current_min_bound.z = leaf_node->bbox_min.z;
}
if(current_max_bound.x < leaf_node->origin.x + highest_voxel_coord.x) {
    current_max_bound.x = leaf_node->origin.x + highest_voxel_coord.x;
}
if(current_max_bound.y < leaf_node->origin.y + highest_voxel_coord.y) {
    current_max_bound.y = leaf_node->origin.y + highest_voxel_coord.y;
}
if(current_max_bound.z < leaf_node->origin.z + highest_voxel_coord.z) {
    current_max_bound.z = leaf_node->origin.z + highest_voxel_coord.z;
}
lower_set_bbox_min(buf, lower_handle, current_min_bound);
lower_set_bbox_max(buf, lower_handle, current_max_bound);

So I would like to know if there is a faster way to compare and get the tighest bounding box in a given 3D coord system? I think so many comparations are killing my CPU performance here. The data structure is a tree but I think it doesn't matter for this problem.

Cheers.

Whether it is possible to code a faster way to calculate the math problem.

EDIT:

It looks like using the ternary conditional operator allows compiler to optimize the code:

                // Set lower node bbox min
                current_min_bound.x = (current_min_bound.x > leaf_node->origin.x + lowest_voxel_coord.x) ? leaf_node->origin.x + lowest_voxel_coord.x : current_min_bound.x;
                current_min_bound.y = (current_min_bound.y > leaf_node->origin.y + lowest_voxel_coord.y) ? leaf_node->origin.y + lowest_voxel_coord.y : current_min_bound.y;
                current_min_bound.z = (current_min_bound.z > leaf_node->origin.z + lowest_voxel_coord.z) ? leaf_node->origin.z + lowest_voxel_coord.z : current_min_bound.z;
                // Set lower node bbox max
                current_max_bound.x = (current_max_bound.x < leaf_node->origin.x + highest_voxel_coord.x) ? leaf_node->origin.x + highest_voxel_coord.x : current_max_bound.x;
                current_max_bound.y = (current_max_bound.y < leaf_node->origin.y + highest_voxel_coord.y) ? leaf_node->origin.y + highest_voxel_coord.y : current_max_bound.y;
                current_max_bound.z = (current_max_bound.z < leaf_node->origin.z + highest_voxel_coord.z) ? leaf_node->origin.z + highest_voxel_coord.z : current_max_bound.z;

Iterations: 27 546

Same iterations previous code: 0.860708 in seconds Same iterations current code: 0.717957 in seconds


Solution

  • Branch prediction failure can slow things down.

    You could try "branchless" comparisons:

    static int min( int x, int y ) { return y ^ ((x^y) & -(x<y)); }
    static int max( int x, int y ) { return y ^ ((x^y) & -(x>y)); }
    

    Leaving it to you to convert these to macros, perhaps.