3次元動的衝突領域の高速算出

概要

論文の詳細を見る
This paper establishes a high-speed algorithm to compute three dimensional collision domain of two input domains, such as a workpiece and a tool. When the tip of the tool is located in the collision domain, the tool must collide with the workpiece. Collision domain can well be computed by Inverted Template Method using envolope operation. Studies have been made to develop algorithms for three dimensional envelope operation. In order to save on storage, oct-tree is adopted to describe three dimensional objects.An oct-tree is generated by recursive dividing of cubic cells. The top cell must involve the object to be described and the descendant cells are classified by four cell values; outside, inside, boundary and unchecked. Among them, only boundary cells are subdivided into eight. The cell value of the output collision domain is determined by matching two cells extracted from each input domains. Matching strategy is most crucial to the speed of envelope operation. We designed three strategies; Breadth-first, Depth-first and Weighted Depth-first-matching. Comparing the computing speeds among the three, Weighted Depth-first-matching shows the highest efficiency owing to the effect of pruning the unnecessary matching of the oct-trees.
公益社団法人精密工学会の論文
1992-09-05