A Set Operation Algorithm Combining Totally 4D Homogeneous Processing with Exact Computation for Extended Triangle-based BRep

摘要

Triangle-based BRep is the simplest among the BRep models in terms of algorithms and data structures. However, it has a fatal weak point that the number of triangular faces in- creases dramatically when ed operations are carried out. In the past we abated this problem and improved the capabilities of triangle-based BRep by introducing a so-called Zero tri- angle, whose three vertices are collinear. As compared with the polygon-based BRep, the triangles-based BRep is highly robust because of its simplicity. But it cannot get away from sensitivities caused by numerical computation errors. In order to avoid such sensitivities, several approaches have been proposed. We think that the best way of solving this problem is to combine totally four dimensional homogeneous processing with exact numerical compu- tation. In this paper we propose a new set operation algorithm using that combination. By introducing Zero triangles, we achieve the algorithm that does not cause numerical figures to increase beyond a least upper bound. In computational experiments, however, it turned out that this proposed algorithm performs several hundred times slower than the previous one.