A method that approximates a solid object by object oriented bounding box tree (OBB-Tree) having minimal summed volume outside the object is proposed. First, the outside volume for a single OBB is defined and computed by a hardware-accelerated algorithm. Then, the construction of one OBB-Tree is formulated into a variational approximation. To solve such an approximation, this paper presents an algorithm that minimizes the total outside volume over all OBBs in the same level using the iterative Lloyd clustering and using a variant of iterative MultiGrid among levels. In experiments, comparing against a state-of-the-art alternative, the resulting OBB-Tree is tighter and has better performance in the test of collision detection.