UC Berkeley

This thesis describes geometric algorithms to check the cleanability of a design during the manufacturing process. The automotive industry needs a computational tool to determine how to clean their products due to the trend of miniaturization and increased geometric complexity of mechanical parts. A newly emerging concept in a product design, Design-for-Cleanability, necessitates algorithms to help designers to design parts that are easy to clean during the manufacturing process. In this thesis, we consider cleaning using high-pressure water jets to clean off the surfaces of workpieces. Specifically, we solve the following two problems purely from a geometric perspective: predicting water trap regions of a workpiece and finding a rotation axis to drain a workpiece.

Finding an orientation that minimizes the potential water trap regions and/or controls their locations when the workpiece is fixtured for water jet cleaning is important to increase the cleaning efficiency. Trapped water leads to stagnation areas, preventing efficient flow cleaning. Minimizing the potential water trap also reduces the draining time and effort after cleaning. We propose a new pool segmentation data structure and algorithm based on topological changes of 2D slices with respect to the gravity direction. Then, we can quickly predict potential water trap regions of a given geometry by analyzing our directed graph based on the segmented pools.

Given a workpiece filled with water after cleaning, to minimize the subsequent drying time, our industrial partner first mounts workpieces on a slowly rotating carrier so that gravity can drain out as much water as possible. We propose an algorithm to find a rotation axis that drains the workpiece when the rotation axis is set parallel to the ground and the workpiece is rotated around the axis. Observing that all water traps contain a concave vertex, we solve our problem by constructing and analyzing a directed "draining graph" whose nodes correspond to concave vertices of the geometry and whose edges are set according to the transition of trapped water when we rotate the workpiece around the given axis. We first introduce an algorithm to test whether a given rotation axis can drain the workpiece. We then extend these concepts to design an algorithm to find the set of all rotation axes that drain the workpiece. If such a rotation axis does not exist, our algorithm will also detect that. To the best of our knowledge, our work is the first to tackle the draining problem and to give an algorithm for the problem.