![]() ![]() I used the Matlab code as reference, with some improvements in the 2D calipers algorithm and in the calculation of average rotations. ![]() My C implementation for MeshLab has already been merged to the extra plugins repository, and can be found here (this was the original PR). The minimization function is not convex and not differentiable, although continuous, so this combination of algorithms works really well. ![]() The genetic algorithm does a global sampling of the space of rotation matrices, while Nelder-Mead and 2D rotating calipers try to find a local minimum. Finally, it applies a further refinement to the best solution by applying the 2D rotating calipers algorithm 3 to each rotated axis. With the ones that produce the smaller volumes, it applies the Nelder-Mead algorithm to find a local optimum. Without digging too much into the details (I defer to the paper for that), the HYBBRID algorithm applies a genetic algorithm to sets of rotation matrices. The most important part to obtain an optimal OBB is finding the rotation matrix, as once we have it it is trivial to calculate the other parameters by rotating the vertices with \(R^T\) and then finding the minimum and maximum coordinates in the x, y, and z axis. They called this algorithm HYBBRID because it mixes genetic algorithms with the Nelder-Mead optimization method, that can be used when derivatives for the target function cannot be calculated.Īn OBB is defined by a rotation matrix \(R\), the center of the box, and the size of each dimension. Also importantly, the authors published Matlab sources for it, so I chose that one for implementation in MeshLab. The one from Chang et al 2 looked fast and results were very near to O’Rourke’s solution. There is an exact algorithm to find optimal OBBs found by O’Rourke 1, but it is known to be slow (complexity is \(O(N^3)\) being \(N\) the number of vertices) and difficult to implement, so I looked at approximate algorithms. I put my hands on the task and started to dig into the literature on the topic. And optimal packaging might be an application as well indeed. Also, optimal OBBs have very important applications, such as fast rendering of 3D scenes, collision detection, and others. That seemed like a nice fit to try MeshLab plugins and learn how to do measurements on 3D reconstructions at the same time. This is called the optimal OBB in the literature. I had some fun last year with finding optimal rectangles for videoconferences, so somewhat following that line of thought, I wondered how easy was to put an irregular object into an oriented bounding box (OBB) with minimal size, that is, the rectangular parallelepiped of minimal volume that encloses the object. As I wanted to research what sort of measurements I could take on my 3D reconstructions, it looked like writing a MeshLab plugin was a great way to do this and be able to visualize and interact with the results easily. Some of them are integrated in the main MeshLab repository, but some others can be found in the MeshLab extra plugins repo. MeshLab can be extended via plugins, of which there is an extensive list. And here again we have excellent open source software for this task, like MeshLab. Once you create a 3D object with this tool, you have a set of vertices and textures that can be manipulated with specialized 3D editing software. There is excellent open source software that is able to do this, like Meshroom, which is based on the Alice Vision framework. I have some interest in photogrammetry, and, more concretely, in the ways to extract 3D information from a set of photographies of an object.
0 Comments
Leave a Reply. |