Fitting oriented bounding boxes (OBBs) in real-time applications, such as the rapid rendering of 3D scenes and the discovery of interference, is an open research problem. Hierarchical OBB trees are used to minimize the computational time in the detection of two intersecting objects to identify disjoint pieces [1]. A variety of methods can be used for computing an OBB for a triangular mesh. Algorithms for fitting OBBs based on the minimum volume, the distribution of mesh points, and the distribution of mesh triangles exist in the literature [2]. The execution time is not typically an issue with these methods of fitting OBBs because they apply a preprocessing phase in real-time applications. However, how should practical algorithms, with a linear asymptotic time, for identifying the complexity of the convex hull of objects such as the heart work?

Chang et al. point out the time deficiencies of the well-known algorithms for finding the best OBBs. They critique O’Rourke’s algorithm [3], the heuristics based on the principal component analysis, and the brute force approaches to locating the best OBBs as computationally inefficient for real-life applications. Consequently, they present a derivative-free optimization technique equipped with a genetic algorithm for finding the best OBBs.

The authors articulate “the search of the minimal volume OBB as an optimization problem defined on a manifold.” The objective function of the OBB optimization is tri-linear and the constraints are linear. The objective function “is not differentiable at every rotation matrix ... that brings at least one face of the OBB to be flush with one edge of the convex hull.” These matrix rotations hypothetically produce the local minima of this OBB objective function. The hybrid bounding box rotation identification (HYBBRID) method is used to locate the global minimum volume of the OBB. The HYBBRID method contains a stochastic genetic algorithm and an a priori deterministic Nelder-Mead multi-scale grid search algorithm. The genetic algorithm is used to compute the initial condition that guarantees convergence in the determination of the global minimum using the Nelder-Mead simplex search algorithm. The performance of the HYBBRID method was evaluated with numerous replications of experiments designed to identify objects such as a ball, a hand, a heart, and a globe. Overall, the method was successful in locating an optimal OBB for each object.

The authors succinctly review algorithms for exploring derivative-free optimization techniques that guarantee convergence to a local minimum, and meta-heuristics for locating the global optimum in an entire OBB search problem space. The graphical illustrations of the issues of, and solutions to, the fitting of OBBs in this paper are insightful and remarkable. Nevertheless, I challenge applied mathematicians to read this mind-bending paper, and recommend parameters that might be useful in genetic algorithms to guarantee the location of all solutions in the search spaces of data mining algorithms for real-time OBB applications.