Efficient simplex computation for fixture layout design

Fixture, to hold an object by making multiple contacts, is a fundamental tool in manufacturing. A fixture layout is an arrangement of contacts on an object’s surface. Designing a fixture layout of an object can be reduced to computing the largest simplex and the resulting simplex is classified using the radius of the largest inscribed ball centered at the origin. We present three different algorithms to compute such a simplex: a simple randomized algorithm, an interchange algorithm, and a branch-and-bound algorithm. We also present methods to combine different algorithms to improve the performance and highlight their performance on complex 3D models consisting of thousands of triangles. Our randomized algorithm computes a feasible fixture layout in linear time and is well-suited for real-time applications. The interchange algorithm computes an optimal simplex in linear time such that no single vertex can be changed to enlarge the simplex, and it provides a practical method for complex 3D objects. The branch-and-bound algorithm computes the largest simplex by using lower and upper bounds on the radius of the inscribed ball, by which the computation time is reduced by a factor of five in comparison with the brute-force search.

► We propose three algorithms to compute fixture layouts. ► The randomized algorithm computes a feasible fixture layout in milliseconds. ► The interchange algorithm takes several seconds to compute a near-optimal result. ► The branch-and-bound algorithm finds the globally optimal fixture layout in hours. ► Hybrid uses of these algorithms can produce a good result in a shorter time.