Abstract: In the ray-tracing community, the surface-area heuristic (SAH) is used as a de facto standard strategy for building high-quality kd-trees. Although widely accepted as the best kd-tree construction method, it is based only on the surface-area measure, which often fails to reflect effectively the rendering characteristics of a given scene. This paper presents new cost metrics that help produce improved kd-trees for static scenes by considering the visibility of geometric objects, which can affect significantly the actual distribution of rays during ray tracing. Instead of the SAH, we apply a different heuristic based on the new concept of voxel visibility, which allows more sophisticated estimation of the chance of a voxel being hit by rays. The first cost metric we present aims at constructing a single kd-tree that is used to trace both primary and secondary rays, whereas the second one is more relevant to secondary rays, involving reflection/refraction or shadowing, whose distribution properties differ from those for primary rays. Our experiments, using both CPU-based and GPU-based computation with several test scenes, demonstrate that the presented cost metrics can reduce markedly the cost of ray-traversal computation and increase significantly the overall frame rate for ray tracing.