2024-03-28T20:54:32Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000125402022-10-21T05:24:51Z00581:00703:00707
超3角形BRepにおける無誤差完全4次元処理を用いた形状演算アルゴリズムA Set Operation Algorithm Combining Totally 4D Homogeneous Processing with Exact Computation for Extended Triangle - based BRepjpn論文http://id.nii.ac.jp/1001/00012540/Journal Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=12540&item_no=1&attribute_id=1&file_no=1Copyright (c) 1999 by the Information Processing Society of Japanコンピュータグラフィクス郵政省通信総合研究所情報通信部情報処理研究室早稲田大学理工学部機械工学科荒川, 佳樹山口, 富士夫我々は3角形BRepに 3つの頂点が同一直線上となるゼロ3角形を導入した超3角形BRepを提案してきている. 超3角形BRepでは 多角形BRepに比べて単純なデータ構造および処理アルゴリズムとなるので その処理系の高信頼性を確保しやすいといえる. しかしながら それでも演算誤差による破綻は免れない. この幾何演算の誤差による破綻の問題を根本的に解決するには 無誤差演算を用いた完全4次元処理(完全同次座標処理)が最善の方法であると考える. そこで 本論文では 超3角形処理に この無誤差完全4次元処理を導入した形状演算アルゴリズムを提案する. このアルゴリズムでは ゼロ3角形を用いることにより 数値の桁数がある上限以上に増大しないことが特徴である. この新しいアルゴリズムと 従来の高速形状演算アルゴリズムとを計算機実験により比較評価した. 新しいアルゴリズムの計算速度の低下は 従来のアルゴリズムに比べて数100倍程度に収まることを確認した.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 increases dramatically when set 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 triangle, whose three vertices are collinear. As compared with the polygon-based BRep, the triangle-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 computation. 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.AN00116647情報処理学会論文誌409347134821999-09-151882-77642009-06-29