TOP > 国内特許検索 > 3次元幾何データの無矛盾化方法及びそのシステム

3次元幾何データの無矛盾化方法及びそのシステム コモンズ

国内特許コード P140010729
整理番号 03-143
掲載日 2014年7月7日
出願番号 特願2004-004690
公開番号 特開2005-196684
登録番号 特許第3950976号
出願日 平成16年1月9日(2004.1.9)
公開日 平成17年7月21日(2005.7.21)
登録日 平成19年5月11日(2007.5.11)
発明者
  • 荒川 佳樹
出願人
  • 国立研究開発法人情報通信研究機構
発明の名称 3次元幾何データの無矛盾化方法及びそのシステム コモンズ
発明の概要 【課題】3次元幾何データにおける幾何矛盾(自己干渉等)を検出しかつ除去する方法を提供する。特に、3次元幾何データの形状演算において、形状演算を何回も実行しても、演算に破綻が生じない3次元幾何データの幾何無矛盾化処理方法を提供する。
【解決手段】3次元幾何データに対して演算処理を行い、前記演算処理過程で生成及び処理された幾何データを記憶する3次元幾何データ処理システムSSにおいて、処理される3次元幾何データにおける幾何矛盾を検出しかつ除去する方法であって、3次元幾何図形の表面データである境界面データを、3角形面データまたは3角形の3つの頂点が同一直線上となるゼロ3角形データにより構成し処理するステップと、前記3次元幾何データの数値を必要精度に応じて任意に切り捨てる座標値データステップと、前記数値データ切り捨てステップにより、発生する幾何矛盾を検出し除去する幾何矛盾検出除去ステップとを有するようにした。
【選択図】図1
従来技術、競合技術の概要


従来技術では、幾何演算は浮動小数点演算を用いて行うのが一般的である。浮動小数点演算では数値の丸め(切り捨て)が行われるために演算誤差が発生する。そして、このような浮動小数点演算が繰り返されると、誤差が蓄積していく。



このような演算誤差のために、浮動小数点演算をベースとした幾何演算処理(図形処理)では、処理が破綻し処理系に暴走(バグ)が生じるという問題点があった。このような処理系の暴走へのこれまでの対処方法は、それぞれの破綻に対応した例外処理ルーチン(アドホック的)を作成することにより対応していた。そして、このような例外処理ルーチンはかなりの量となり、また次第に増加していく。すなわち、根本的に処理系の破綻を回避することが出来なかった。



この幾何処理の破綻の問題を解決する1つの方法を提案した。この提案では、以下に示す3つの特徴を有し、これにより無誤差形状演算を実現している。そして、計算誤差をまったくなくすことにより、計算誤差から生じる幾何演算の破綻を回避している(例えば特許文献1参照)。
(1)超3角形(ゼロ3角形)幾何データ処理
(2)4次元同次座標系幾何処理
(3)可変長ビットの整数演算
【特許文献1】
特許第3151710号

産業上の利用分野



本発明は、3次元幾何データの演算処理方法及びそのシステムに関する。

特許請求の範囲 【請求項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次元幾何データの無矛盾化システム。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2004004690thum.jpg
出願権利状態 登録
※ 詳細内容の開示にあたっては、別途、JSTと秘密保持契約を締結していただくことが必要となります。


PAGE TOP

close
close
close
close
close
close
close