Top > Search of Japanese Patents > NON-CONFLICTING METHOD AND SYSTEM FOR THREE-DIMENSIONAL GEOMETRIC DATA

# NON-CONFLICTING METHOD AND SYSTEM FOR THREE-DIMENSIONAL GEOMETRIC DATA

Patent code P140010729 03-143 Jul 7, 2014 P2004-004690 P2005-196684A P3950976 Jan 9, 2004 Jul 21, 2005 May 11, 2007 (In Japanese)荒川 佳樹 (In Japanese)国立研究開発法人情報通信研究機構 NON-CONFLICTING METHOD AND SYSTEM FOR THREE-DIMENSIONAL GEOMETRIC DATA PROBLEM TO BE SOLVED: To provide a method of detecting and eliminating geometric conflict (self-interference and the like) in three-dimensional geometric data, in particular, a geometric non-conflict processing method of the three-dimensional geometric data free from failure in operation even when the shape operation is repeatedly executed in the shape operation of three-dimensional geometric data. SOLUTION: This method of detecting and eliminating geometric conflict in a processed three-dimensional geometric data in a three-dimensional geometric data processing system SS performing the operation processing to the three-dimensional geometric data, and storing the geometric data created and processed in the operation processing process, comprises a step for constituting and processing the boundary face data as a surface data of a three-dimensional geometric figure by triangle face data or zero triangle data where three apexes of triangle are located on the same straight line, a coordinate value data step for arbitrarily truncating a numerical value of the three-dimensional geometric data in accordance with necessary accuracy, and a geometric conflict detecting and eliminating step for detecting and eliminating the geometric conflict generated in the numerical value data truncating step. (In Japanese) 従来技術では、幾何演算は浮動小数点演算を用いて行うのが一般的である。浮動小数点演算では数値の丸め（切り捨て）が行われるために演算誤差が発生する。そして、このような浮動小数点演算が繰り返されると、誤差が蓄積していく。 このような演算誤差のために、浮動小数点演算をベースとした幾何演算処理（図形処理）では、処理が破綻し処理系に暴走（バグ）が生じるという問題点があった。このような処理系の暴走へのこれまでの対処方法は、それぞれの破綻に対応した例外処理ルーチン（アドホック的）を作成することにより対応していた。そして、このような例外処理ルーチンはかなりの量となり、また次第に増加していく。すなわち、根本的に処理系の破綻を回避することが出来なかった。 この幾何処理の破綻の問題を解決する1つの方法を提案した。この提案では、以下に示す3つの特徴を有し、これにより無誤差形状演算を実現している。そして、計算誤差をまったくなくすことにより、計算誤差から生じる幾何演算の破綻を回避している（例えば特許文献1参照）。（1）超3角形（ゼロ3角形）幾何データ処理（2）4次元同次座標系幾何処理（3）可変長ビットの整数演算【特許文献1】 特許第3151710号 (In Japanese) 本発明は、3次元幾何データの演算処理方法及びそのシステムに関する。 (In Japanese)【請求項1】  3次元幾何データに対して演算処理を行い、前記演算処理過程で生成及び処理された幾何データを記憶する3次元幾何データ処理システムにおいて、処理される3次元幾何データにおける幾何矛盾を検出しかつ除去する方法であって、 3次元幾何図形の表面データである境界面データを、3角形面データまたは3角形の3つの頂点が同一直線上となるゼロ3角形データにより構成し処理する3角形／ゼロ3角形データ処理ステップと、 前記3角形／ゼロ3角形データ処理ステップで処理された3次元幾何データの数値を必要精度に応じて任意に切り捨てる数値データ切り捨て処理ステップと、 前記数値データ切り捨て処理ステップにより、発生する幾何矛盾を検出し除去する幾何無矛盾化処理ステップと、を有し、 前記幾何無矛盾化処理ステップが、縮退3角形面を検出し除去する縮退3角形面の検出除去処理ステップ、重なり3角形面を検出し除去する面の重なり検出除去処理ステップ、および矛盾立体を検出し除去する矛盾立体の検出除去処理ステップを含むものであることを特徴とする3次元幾何データの無矛盾化方法。【請求項2】  縮退3角形面の検出除去処理ステップが、2頂点が同一点となるいびつな3角形、3頂点が同一点となるいびつな3角形、および3頂点が同一直線上となるいびつな3角形を検出し除去するものであることを特徴とする請求項1記載の3次元幾何データの無矛盾化方法。【請求項3】  面の重なり検出除去処理ステップが、組にした3角形面データの同一平面判定および面の向き判定の判定結果に基づき、3角形面が重なっていると判定された3角形面に対してその重なりを除去するようにした処理であることを特徴とする請求項1または2記載の3次元幾何データの無矛盾化方法。【請求項4】  矛盾立体の検出除去処理ステップが、 同じ立体を構成する面同士が交差している立体を検出し除去するものであることを特徴とする請求項1乃至3いずれか記載の3次元幾何データの無矛盾化方法。【請求項5】  矛盾立体の検出除去処理ステップが、 自己干渉立体の分離処理を行うステップ、立体の最上位3角形面の探索処理を行うステップ、立体の最近傍上位立体の探索処理を行うステップ、最近傍上位立体順に立体データのソーティングを行うステップ、面の向きによる立体の消去処理を行うステップからなることを特徴とする請求項1乃至4いずれか記載の3次元幾何データの無矛盾化方法。【請求項6】  前記各ステップにおいて、4次元同次座標系処理と可変長ビットの演算を用いて無誤差演算を行うことを特徴とする請求項1乃至5いすれか記載の3次元幾何データの無矛盾化方法。【請求項7】  3次元幾何データに対して演算処理を行い、前記演算処理過程で生成及び処理された幾何データを記憶する3次元幾何データ処理システムであって、 3次元幾何図形の表面データである境界面データを、3角形面データまたは3角形の3つの頂点が同一直線上となるゼロ3角形データにより構成し処理する3角形／ゼロ3角形データ処理部と、 前記3角形／ゼロ3角形データ処理部で処理された3次元幾何データの数値を必要精度に応じて任意に切り捨てる数値データ切り捨て処理部と、 前記数値データ切り捨て処理部により、発生する幾何矛盾を検出し除去する幾何無矛盾化処理部と、を有し、 前記幾何無矛盾化処理部が、縮退3角形面を検出し除去する縮退3角形処理部、重なり3角形面を検出し除去する重なり3角形処理部、および矛盾立体を検出し除去する矛盾立体処理部を含むものであることを特徴とする3次元幾何データの無矛盾化システム。【請求項8】  縮退3角形処理部が、2頂点が同一点となるいびつな3角形、3頂点が同一点となるいびつな3角形、および3頂点が同一直線上となるいびつな3角形を検出し除去するものであることを特徴とする請求項7記載の3次元幾何データの無矛盾化システム。【請求項9】  重なり3角形処理部が、組にした3角形面データの同一平面判定および面の向き判定の判定結果に基づき、3角形面が重なっていると判定された3角形面に対してその重なりを除去する処理をすることを特徴とする請求項7または8記載の3次元幾何データの無矛盾化システム。【請求項10】  矛盾立体処理部が、 同じ立体を構成する面同士が交差している立体を検出し除去する処理を行うことを特徴とする請求項7乃至9いずれか記載の3次元幾何データの無矛盾化システム。【請求項11】  矛盾立体処理部が、 自己干渉立体の分離処理と、立体の最上位3角形面の探索処理と、立体の最近傍上位立体の探索処理と、最近傍上位立体順に立体データのソーティングを行う処理と、面の向きによる立体の消去処理とを行うように構成していることを特徴とする請求項7乃至10いずれか記載の3次元幾何データの無矛盾化システム。【請求項12】  前記各処理部において、4次元同次座標系処理と可変長ビットの演算を用いて無誤差演算を行うことを特徴とする請求項7乃至11いすれか記載の3次元幾何データの無矛盾化システム。 G06F  17/50      Computer-aided design 5B046DA08 Diagrams indicating three-dimensional shape 5B046FA07 Detecting intersection or overlapping (i.e., interference) 5B046FA18 Descriptions and creation of curved surfaces or shape modeling 5B046JA02 Geometrical checking Registered