Described is a technology for constructing kd-trees on GPUs, in a manner that is sufficiently fast to achieve real-time performance by exploiting GPU-bsaed parallelism during the kd-tree construction. Tree nodes are built in breadth-first search order, e.g., to use a thread for each node at each level. For large nodes at upper tree levels, computations are parallelized over geometric primitives (instead of nodes). To this end, large nodes are split into child nodes by cutting off empty space based until an empty space ratio is achieved, and thereafter performing spatial splitting. Small nodes are split based on split candidate costs, e.g., computed by a surface area heuristic or a voxel volume heuristic (VVH).