Seminar Details
2009-10-06 (14.00) : Fast computation on SO(3) of optimal oriented bounding box
At Euler building
Organized by Mathematical Engineering
Speaker :
CHANG Chia-Tche
GORISSEN Bastien (CESAME)
Abstract :
Photorealistic realtime rendering and physically correct simulations of
3D scenes are at the bleeding edge of what can be done with today's
computers. Such applications involve collision detection and visibility
tests using methods based on oriented bounding boxes (OBB) enclosing 3D
objects. Joseph O'Rourke published in 1985 an algorithm that computes the
exact solution in cubic time, but is extremely hard to implement. In
practice, faster PCA-based and brute force heuristics are used. The
computation of the minimal-volume OBB is formulated as an unconstrained
optimization problem on the rotation group SO(3). It is solved using a
hybrid method combining the genetic and Nelder-Mead algorithms. This
method is analyzed then compared to the current state-of-the-art, and it
turns out to be either faster or more accurate.