図面 (/)

技術 ポリゴンメッシュの作成方法と作成装置並びにポリゴンメッシュの形状特徴提示方法と形状特徴提示装置及びポリゴンメッシュの作成プログラムと形状特徴提示プログラムを格納した記憶媒体

出願人 株式会社リコー
発明者 植田健治早野勝之
出願日 1998年11月5日 (21年3ヶ月経過) 出願番号 1998-314903
公開日 2000年5月30日 (19年8ヶ月経過) 公開番号 2000-149060
状態 未査定
技術分野 CAD イメージ処理・作成 イメージ生成
主要キーワード 境界稜線 特徴属性 各立方体 曲面モデル 特徴要素 ガウス曲率 射影点 シェーディング表示
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2000年5月30日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (12)

課題

すべての点を頂点とした単一の3角形ポリゴンメッシュを自動的に生成する。

解決手段

点集合が与えられ表示されると、凸包多面体列生成部12は与えられた点集合に対して、その凸包多面体を生成し、点の集まりを3次元空間内で入れ子状階層化してから点の集まりを処理する。初期3角形ポリゴンメッシュ生成部13は生成された凸包多面体列の最も外側の多面体を3角形ポリゴンメッシュの初期形状とし、この最も外側の多面体を凸包多面体列から除く。ポリゴンメッシュ変形部14はポリゴンメッシュの初期形状に対して凸包多面体列の最も外側の凸包多面体の頂点からなる点集合をポリゴンメッシュを凹ませながらポリゴンメッシュに取り込み最終形状を作成する。

概要

背景

次元測定機などから得られる形状の表面をプロットした3次元座標値群をもとに生成した3次元ポリゴンメッシュの利用が進んでいる。このポリゴンメッシュの作成方法の代表的なものとして、例えば下記文献に記載された方法がある。
文献1;W.E.Lorensen
「Marching cubes:a high resolution
3D surface construction algorithm 」
Computer Graphics,Vol.21,No.4,1987,pp.163-169.
文献2;H.Edelsbrunner and E.P.Mucke
「Three-dimensional alpha shapes」
ACMToransactions on Graphics,Vol.13,No.1,(1994)pp.43-72.

第1の文献に記載された方法は、空間を格子状の立方体に分割し、点の存在の仕方にしたがって、各立方体で占められる領域をいくつかの3角形組み合わせパターンに変換し空間を3角形のポリゴンで分割することを各立方体で行うことにより3角形のポリゴンメッシュを構築する方法であり、格子の幅に依存したポリゴンメッシュが作成され、点の座標は直接ポリゴンメッシュに反映されない。

また、第2の文献に記載された方法は、点集合に与えられた点をつなぐような数学的に定義された形状を作成するが、点集合中の点の分布と与えられたある距離(1/a)に依存した形状が定義されるため、必ずしも実際に存在するような形状が得られるとは限らない。

また、作成したポリゴンメッシュの精度やデータ量は、3次元座標値群の密度やポリゴンメッシュの作成方法に依存するため、ユーザの目的に応じた精度やデータ量を持っているとは限らない。そこで、何らかの手段でポリゴンメッシュを編集し、利用目的に適したメッシュを作成することが必要になる。しかし3角形の集合で表されるポリゴンメッシュをCRT等の表示装置において表示しても、どの部分が形状の特徴を表しているのか感覚的にわかりにくい。

このような計算機内の形状モデル修正の難しさを軽減する方法として、例えば特開平5−346957号公報に示されているように、機械系CADなどの設計支援システムで自由曲面モデル形状修正を行う際に、自由曲面モデルの指定した位置における曲率などの形状特徴量表示画面上にグラフ等で表示することにより、詳細な形状特徴量を表示する方法がある。

概要

すべての点を頂点とした単一の3角形のポリゴンメッシュを自動的に生成する。

点集合が与えられ表示されると、凸包多面体列生成部12は与えられた点集合に対して、その凸包多面体を生成し、点の集まりを3次元空間内で入れ子状階層化してから点の集まりを処理する。初期3角形ポリゴンメッシュ生成部13は生成された凸包多面体列の最も外側の多面体を3角形ポリゴンメッシュの初期形状とし、この最も外側の多面体を凸包多面体列から除く。ポリゴンメッシュ変形部14はポリゴンメッシュの初期形状に対して凸包多面体列の最も外側の凸包多面体の頂点からなる点集合をポリゴンメッシュを凹ませながらポリゴンメッシュに取り込み最終形状を作成する。

目的

この発明はポリゴンメッシュを作成するときの前記問題を解消し、与えられた点集合中の点を階層的な凸包列の頂点に分割することで階層化し、できるだけ表面積の小さい3角形のポリゴンメッシュに徐々に変換することで、すべての点を頂点とした単一の3角形のポリゴンメッシュを自動的に生成することができるポリゴンメッシュの作成方法と作成装置を提供することを目的とする。

また、作成したポリゴンメッシュの形状特徴を表す要素を検出し、それ以外の要素とは異なる方法で表示することによって、ポリゴンメッシュを編集し、目的に応じたメッシュを得るために必要な作業量を軽減することができるポリゴンメッシュの形状特徴提示方法と形状特徴提示装置を提供することを目的とする。

効果

実績

技術文献被引用数
0件
牽制数
1件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

次元の点の集まりから定義される形状を作成するとき、点の集まりで定義される凸包列を生成し、点の集まりを3次元空間内で入れ子状階層化してから点の集まりを処理することを特徴とするポリゴンメッシュ作成方法

請求項2

上記点の集まりで定義される凸包列を生成するときに、最外殻凸包を初期外殻ポリゴンメッシュとしたあと、外殻ポリゴンメッシュの面を一つ内側へ凸包の頂点へ凹ませることを繰り返して、点の集まり中のすべて点を頂点とするポリゴンメッシュを生成する請求項1記載のポリゴンメッシュの作成方法。

請求項3

上記外殻の面を凹ませるとき、変形された外殻ポリゴンメッシュの表面積が最小となるように面を凹ませる請求項2記載のポリゴンメッシュの作成方法。

請求項4

上記面を凹ませるときに、一つの頂点へ面を凹ませるたときに凹んだ面の周辺に対して局所的なポリゴンメッシュの面積が小さくなるようにして、変形された外殻ポリゴンメッシュの表面積が最小となるようにする請求項3記載のポリゴンメッシュの作成方法。

請求項5

凸包多面体列生成部と初期3角形ポリゴンメッシュ生成部及びポリゴンメッシュ変形部を有し、凸包多面体列生成部は与えられた点集合に対してその凸包多面体を生成することを複数回行い凸包多面体列を生成し、初期3角形ポリゴンメッシュ生成部は生成された凸包多面体列の最も外側の多面体を3角形ポリゴンメッシュの初期形状とし、この最も外側の多面体を凸包多面体列から除き、ポリゴンメッシュ変形部はポリゴンメッシュの初期形状に対して凸包多面体列の最も外側の凸包多面体の頂点からなる点集合をポリゴンメッシュを凹ませながらポリゴンメッシュに取り込むことを特徴とするポリゴンメッシュの作成装置

請求項6

3次元形状を近似した3角形ポリゴンメッシュを構築し、3角形ポリゴンメッシュから形状特徴を表す要素を検出し、検出された形状特徴を表す要素の特定の属性を与え、特定の属性を持つ要素を他の要素と区別して構築した3角形ポリゴンメッシュとともに表示することを特徴とするポリゴンメッシュの形状特徴提示方法

請求項7

上記検出された形状特徴を表す要素は、形状特徴を表すポリゴン稜線ポリゴン頂点である請求項6記載のポリゴンメッシュの形状特徴提示方法。

請求項8

上記特定の属性を持つ要素を他の要素と異なる色で表示する請求項7記載のポリゴンメッシュの形状特徴提示方法。

請求項9

特徴要素検出部と特定属性付与部と形状特徴出力部を有し、特徴要素検出部は3角形ポリゴンメッシュデータに基づいて形状特徴を表す要素を検出し、特定属性付与部は検出された形状特徴を表す要素に特定の属性を与え、形状特徴出力部は特定の属性を付与された要素を他の要素と区別して構築した3角形ポリゴンメッシュとともに表示装置に表示することを特徴とするポリゴンメッシュの形状特徴提示装置

請求項10

与えられた点集合に対してその凸包多面体を生成することを複数回行い凸包多面体列を生成し、生成された凸包多面体列の最も外側の多面体を3角形ポリゴンメッシュの初期形状とし、この最も外側の多面体を凸包多面体列から除き、ポリゴンメッシュの初期形状に対して凸包多面体列の最も外側の凸包多面体の頂点からなる点集合をポリゴンメッシュを凹ませながらポリゴンメッシュに取り込むポリゴンメッシュの作成プログラムと、3角形ポリゴンメッシュデータに基づいて形状特徴を表す要素を検出し、検出された形状特徴を表す要素に特定の属性を与え、特定の属性を付与された要素を他の要素と区別して構築した3角形ポリゴンメッシュとともに表示装置に表示するポリゴンメッシュの形状特徴提示プログラムを記録し、コンピュータにより読み取り可能なことを特徴とする記録媒体

技術分野

0001

この発明は、計算機を用いた3次元データ処理におけるポリゴンメッシュ作成方法作成装置並びにポリゴンメッシュの形状特徴提示方法と形状特徴提示装置及びポリゴンメッシュの作成プログラムと形状特徴提示プログラムを格納した記憶媒体に関するものである。

背景技術

0002

次元測定機などから得られる形状の表面をプロットした3次元座標値群をもとに生成した3次元ポリゴンメッシュの利用が進んでいる。このポリゴンメッシュの作成方法の代表的なものとして、例えば下記文献に記載された方法がある。
文献1;W.E.Lorensen
「Marching cubes:a high resolution
3D surface construction algorithm 」
Computer Graphics,Vol.21,No.4,1987,pp.163-169.
文献2;H.Edelsbrunner and E.P.Mucke
「Three-dimensional alpha shapes」
ACMToransactions on Graphics,Vol.13,No.1,(1994)pp.43-72.

0003

第1の文献に記載された方法は、空間を格子状の立方体に分割し、点の存在の仕方にしたがって、各立方体で占められる領域をいくつかの3角形組み合わせパターンに変換し空間を3角形のポリゴンで分割することを各立方体で行うことにより3角形のポリゴンメッシュを構築する方法であり、格子の幅に依存したポリゴンメッシュが作成され、点の座標は直接ポリゴンメッシュに反映されない。

0004

また、第2の文献に記載された方法は、点集合に与えられた点をつなぐような数学的に定義された形状を作成するが、点集合中の点の分布と与えられたある距離(1/a)に依存した形状が定義されるため、必ずしも実際に存在するような形状が得られるとは限らない。

0005

また、作成したポリゴンメッシュの精度やデータ量は、3次元座標値群の密度やポリゴンメッシュの作成方法に依存するため、ユーザの目的に応じた精度やデータ量を持っているとは限らない。そこで、何らかの手段でポリゴンメッシュを編集し、利用目的に適したメッシュを作成することが必要になる。しかし3角形の集合で表されるポリゴンメッシュをCRT等の表示装置において表示しても、どの部分が形状の特徴を表しているのか感覚的にわかりにくい。

0006

このような計算機内の形状モデル修正の難しさを軽減する方法として、例えば特開平5−346957号公報に示されているように、機械系CADなどの設計支援システムで自由曲面モデル形状修正を行う際に、自由曲面モデルの指定した位置における曲率などの形状特徴量表示画面上にグラフ等で表示することにより、詳細な形状特徴量を表示する方法がある。

発明が解決しようとする課題

0007

上記文献1に記載されたポリゴンメッシュの作成方法は、格子間隔の大きさで3角形メッシュの大きさが決定され、点集合中の点の密度には関係なくメッシュが生成されため、点集合中の点の位置を正確に反映したようなメッシュを生成するためにはメッシュの最適化操作を必要とする。また、文献2に記載されたポリゴンメッシュの作成方法は、点集合に与えられた点の位置には必ず頂点が存在するような形状が作成されているが、与えられた距離以上で頂点間を結ぶような形状は作成されない。さらに、文献1と文献2に記載された方法は、いずれも与えられた点集合の概形を作成する手段として利用されているが、最適な格子間隔または距離を自動的に決定することは困難であり、例えそれが決定できたとしても得られる形状には制限がある。

0008

また特開平5−346957号公報に示されている形状特徴量の表示方法は、自由曲面によって表現される形状モデルを対象にしており、3角形ポリゴンメッシュによって表現される形状モデルの特徴を表示するものではない。

0009

この発明はポリゴンメッシュを作成するときの前記問題を解消し、与えられた点集合中の点を階層的な凸包列の頂点に分割することで階層化し、できるだけ表面積の小さい3角形のポリゴンメッシュに徐々に変換することで、すべての点を頂点とした単一の3角形のポリゴンメッシュを自動的に生成することができるポリゴンメッシュの作成方法と作成装置を提供することを目的とする。

0010

また、作成したポリゴンメッシュの形状特徴を表す要素を検出し、それ以外の要素とは異なる方法で表示することによって、ポリゴンメッシュを編集し、目的に応じたメッシュを得るために必要な作業量を軽減することができるポリゴンメッシュの形状特徴提示方法と形状特徴提示装置を提供することを目的とする。

課題を解決するための手段

0011

この発明に係るポリゴンメッシュの作成方法は、3次元の点の集まりから定義される形状を作成するとき、点の集まりで定義される凸包列を生成し、点の集まりを3次元空間内で入れ子状に階層化してから点の集まりを処理することを特徴とする。

0012

上記点の集まりで定義される凸包列を生成するときに、最外殻凸包を初期外殻ポリゴンメッシュとしたあと、外殻ポリゴンメッシュの面を一つ内側へ凸包の頂点へ凹ませることを繰り返して、点の集まり中のすべて点を頂点とするポリゴンメッシュを生成すると良い。

0013

また、上記外殻の面を凹ませるとき、変形された外殻ポリゴンメッシュの表面積が最小となるように面を凹ませることが望ましい。

0014

さらに、上記面を凹ませるときに、一つの頂点へ面を凹ませるたときに凹んだ面の周辺に対して局所的なポリゴンメッシュの面積が小さくなるようにして、変形された外殻ポリゴンメッシュの表面積が最小となるようにすると良い。

0015

この発明に係るポリゴンメッシュの作成装置は、凸包多面体列生成部と初期3角形ポリゴンメッシュ生成部及びポリゴンメッシュ変形部を有し、凸包多面体列生成部は与えられた点集合に対してその凸包多面体を生成することを複数回行い凸包多面体列を生成し、初期3角形ポリゴンメッシュ生成部は生成された凸包多面体列の最も外側の多面体を3角形ポリゴンメッシュの初期形状とし、この最も外側の多面体を凸包多面体列から除き、ポリゴンメッシュ変形部はポリゴンメッシュの初期形状に対して凸包多面体列の最も外側の凸包多面体の頂点からなる点集合をポリゴンメッシュを凹ませながらポリゴンメッシュに取り込むことを特徴とする

0016

この発明に係るポリゴンメッシュの形状特徴提示方法は、3次元形状を近似した3角形ポリゴンメッシュを構築し、3角形ポリゴンメッシュから形状特徴を表す要素を検出し、検出された形状特徴を表す要素の特定の属性を与え、特定の属性を持つ要素を他の要素と区別して構築した3角形ポリゴンメッシュとともに表示することを特徴とする。

0017

上記検出された形状特徴を表す要素は、形状特徴を表すポリゴン稜線ポリゴン頂点である。

0018

また、上記特定の属性を持つ要素を他の要素と異なる色で表示すると良い。

0019

この発明に係るポリゴンメッシュの形状特徴提示装置は、特徴要素検出部と特定属性付与部と形状特徴出力部を有し、特徴要素検出部は3角形ポリゴンメッシュデータに基づいて形状特徴を表す要素を検出し、特定属性付与部は検出された形状特徴を表す要素に特定の属性を与え、形状特徴出力部は特定の属性を付与された要素を他の要素と区別して構築した3角形ポリゴンメッシュとともに表示装置に表示することを特徴とする。

0020

また、この発明に係る記録媒体は、与えられた点集合に対してその凸包多面体を生成することを複数回行い凸包多面体列を生成し、生成された凸包多面体列の最も外側の多面体を3角形ポリゴンメッシュの初期形状とし、この最も外側の多面体を凸包多面体列から除き、ポリゴンメッシュの初期形状に対して凸包多面体列の最も外側の凸包多面体の頂点からなる点集合をポリゴンメッシュを凹ませながらポリゴンメッシュに取り込むポリゴンメッシュの作成プログラムと、3角形ポリゴンメッシュデータに基づいて形状特徴を表す要素を検出し、検出された形状特徴を表す要素に特定の属性を与え、特定の属性を付与された要素を他の要素と区別して構築した3角形ポリゴンメッシュとともに表示装置に表示するポリゴンメッシュの形状特徴提示プログラムを記録し、コンピュータにより読み取り可能とする。

発明を実施するための最良の形態

0021

この発明のポリゴンメッシュの作成装置は、与えられた点集合の各点を頂点に持つようなポリゴンメッシュデータを生成するものであり、凸包多面体列生成部と初期3角形ポリゴンメッシュ生成部及びポリゴンメッシュ変形部を有する。

0022

点集合が与えられ表示されると、凸包多面体列生成部は与えられた点集合に対して、その凸包多面体を生成し、点の集まりを3次元空間内で入れ子状に階層化してから点の集まりを処理する。初期3角形ポリゴンメッシュ生成部は生成された凸包多面体列の最も外側の多面体を3角形ポリゴンメッシュの初期形状とし、この最も外側の多面体を凸包多面体列から除く。ポリゴンメッシュ変形部はポリゴンメッシュの初期形状に対して凸包多面体列の最も外側の凸包多面体の頂点からなる点集合をポリゴンメッシュを凹ませながらポリゴンメッシュに取り込み最終形状を作成する。

0023

また、この発明のポリゴンメッシュの形状特徴提示装置は、特徴要素検出部と特定属性付与部と形状特徴出力部を有する。3角形ポリゴンメッシュが構築されると、特徴要素検出部は構築された3角形ポリゴンメッシュデータに基づいて形状特徴を表す要素を検出する。特定属性付与部は検出された形状特徴を表す要素に特定の属性を与え、特定の属性を付与された要素を形状特徴出力部は他の要素と区別して構築した3角形ポリゴンメッシュとともに表示装置に表示して、形状特徴の把握を容易にする。

0024

図1はこの発明の一実施例の構成を示すブロック図である。図に示すように、形状データの認識処理装置は、制御部1と入力装置2と表示装置3とプロッタ4及び記憶媒体5を有する。制御部1は装置全体の動作を管理するCPU6と、基本ソフトグラフィックライブラリアプリケーションプログラム等を記憶したROM7と、CPU6のワークメモリ等に使用するRAM8と、外部の記憶媒体5に対して読み込みや書き込みを行う外部メモリインタフェース9と、ポリゴンメッシュ生成部10及び形状特徴提示部11を有する。

0025

ポリゴンメッシュ生成部10は、与えられた点集合の各点を頂点に持つようなポリゴンメッシュデータを生成するものであり、凸包多面体列生成部12と初期3角形ポリゴンメッシュ生成部13及びポリゴンメッシュ変形部14を有する。凸包多面体列生成部12は、与えられた点集合に対してその凸包多面体を生成することを複数回行い凸包多面体列を生成する。初期3角形ポリゴンメッシュ生成部13は、生成された凸包多面体列の最も外側の多面体を三角形ポリゴンメッシュの初期形状とし、この最も外側の多面体を凸包多面体列から除く。ポリゴンメッシュ変形部14はポリゴンメッシュの変形を行うものであり、ポリゴンメッシュに対して凸包多面体列の最も外側の凸包多面体の頂点からなる点集合をポリゴンメッシュを凹ませながらポリゴンメッシュに取り込む。この点集合のすべての点がポリゴンメッシュに取り込まれたなら、外側の多面体は凸包多面体列から除く。

0026

形状特徴提示部11は、ポリゴンメッシュ生成部10で生成した3角形ポリゴンメッシュによって表現される形状モデルのの特徴を検出して表示するものであり、特徴要素検出部15と特定属性付与部16と形状特徴出力部17を有する。特徴要素検出部15は3角形ポリゴンメッシュデータに基づいて形状特徴を表す要素を検出する。特定属性付与部16は検出された形状特徴を表す要素に特定の属性を与える。形状特徴出力部17は特定の属性を付与された要素を他の要素と異なる方法で構築した3角形ポリゴンメッシュとともに検出した形状特徴を出力して表示装置3の表示画面上に表示する。

0027

上記のように構成された形状データの認識処理装置により点集合の形状を近似した3角形ポリゴンメッシュを作成するときの処理を図2フローチャートを参照して説明する。

0028

例えば図3に示すような点集合21が与えられ表示装置3に表示されると、ポリゴンメッシュ生成部10の凸包多面体列生成部12は与えられた点集合21に対して、図4に示す、その凸包多面体22を生成する。この点集合21に対する凸包多面体とは点集合21中のすべての点をその中に含む最小の多面体である。点集合21中のいくつかの点はその多面体の頂点となるが、それ以外の点は多面体の内部に含まれる点となる。この凸包多面体22の頂点となる点の集合を最外殻の点集合とし、この最も外側の多面体を凸包多面体列から除く。図5(a)に示す凸包多面体23は、図3の点集合21から図4に示す凸包多面体22の頂点となるような点を除いた点集合によって定義される凸包多面体である。この凸包多面体の内部の点からなる集合に対して再び凸包多面体を求め、2番目の凸包多面体の頂点からなる点の集合を外から2番目の点集合とする操作を繰り返すことで、最初に与えられた点集合のすべての点を、何かの凸包多面体の頂点になるように入れ子状の凸包多面体列を構成し、各凸包多面体の頂点の集合に与えられた点集合を分割する(ステップS1)。図5(b),(c),(d)に示す凸包多面体24,25,26は、このような処理を、与えられた点集合の各点が入れ子状に階層化した凸包多面体のいずれかに属するまで行って得られた凸包多面体列である。このように分割された各点集合に対する凸包多面体は、空間中で入れ子状に階層化されることになるので、その後の処理にとって都合がよくなる。

0029

初期3角形ポリゴンメッシュ生成部13は、生成された凸包多面体列の最も外側の多面体、すなわち図4に示す多面体を三角形ポリゴンメッシュの初期形状とする(ステップS2)。その後、ポリゴンメッシュ変形部14は初期ポリゴンメッシュの内部に含まれる凸包多面体列の外側の凸包多面体から順番に、その凸包多面体の頂点を利用してポリゴンメッシュを凹ませるポリゴンメッシュの変形処理に入る(ステップS3)。このポリゴンメッシュを凹ませるポリゴンメッシュの変形処理においては、凹ませ方の基準として、ポリゴンメッシュの表面積ができるだけ小さくなるように凹ませる。これは初期ポリゴンメッシュとして採用した最外殻凸包多面体は、もともとその頂点からなる多面体で表面積が最小なものであることからも妥当なものである。

0030

この表面積が最小なポリゴンメッシュを得る処理として、まず、距離計算処理を行う(ステップS4)。距離計算処理は、点集合中の各点υiについて、ポリゴンメッシュの面の裏側がすべて可視である面を含む平面にυiを正射影する。このとき点υiが面内に射影されるなら、点と面の距離として点と射影点との距離を採用する。もし点υiの射影点が面の外であれば、点υiに最も近い面の頂点と点υiの距離を点と面の距離とする。このような距離のうち最短な距離とそのときの面を点υiに対応付けて最短裏面情報とする。次ぎに、角錐生成処理に入る(ステップS5)。角錐生成処理では、点集合中の各点に対応付けられた距離に中から最短距離を持つ点を選び、最短距離にある面をポリゴンメッシュから削除し、その削除された部分に残った境界から選択された点を頂点とする三角錐でポリゴンメッシュに面を張る。この選択された点は、ポリゴンメッシュの内部にあったので、ポリゴンメッシュの一つの面がある頂点に向かって凹むことになる。このとき、選択された点から凹まされる面の裏面はすべて見渡せるので、凹ませることで生成される三角錐でポリゴンメッシュがポリゴンメッシュの他の面と干渉することはない。引き続いて稜線交換処理に入る(ステップS6)。稜線交換処理では、図6(a)に示すように、新たに生成された面の境界稜線のうちから稜線交換によって、図6(b)に示すように、表面積の減少量が最も大きい稜線を選び、その稜線に対して稜線交換を行う。この処理を表面積が減少する稜線交換が実行できなくなるまで繰り返す。このとき、ポリゴンと自己干渉しないかどうか、また、より内側の凸包多面体と干渉しないかを確認しながら稜線交換処理を行う。そしてポリゴンに組みこまれていない点に対し、新たに生成された角錐の面に対して、最も近くに面のすべてが見えるポリゴンになっていないかを調べ、より近い面が存在すれば、距離計算処理で最短裏面情報を修正し、上記処理を繰り返す(ステップS7,S4〜S6)。この処理によりポリゴンに組み込まれていない頂点が存在しない場合は処理を終了する(ステップS7,S8)。また、ポリゴンに組みこまれていない頂点が存在する場合には、上記処理を繰り返す(ステップS8,S4〜S7)。図7(a)は、このポリゴンメッシュの変形処理により、図5(a)に示す多面体23に含まれるポリゴンメッシュを凹ませた形状27を示し、図7(b)は、図5(b)に示す多面体24に含まれる点でポリゴンメッシュを凹ませた形状28を示し、図7(c),(d)に示す形状29,30は、図5(b),(d)に示す多面体25,26に含まれる点でポリゴンメッシュを凹ませた形状を示し、図7(d)に示す形状30がポリゴンメッシュを凹ませた最終形状である。

0031

このようにして、初期ポリゴンメッシュが容易に生成できるとともに、空間中に散在している点が階層的に分割されることにより、ポリゴンメッシュを得る操作の対象が限定され、ポリゴンメッシュの生成を効率的に行うことができる。

0032

次ぎに、上記のように生成したポリゴンメッシュの形状特徴を形状特徴提示部11で抽出して表示装置3に表示するときの処理を図8のフローチャートを参照して説明する。

0033

ポリゴンメッシュが生成されると(ステップS11)、形状特徴提示部11の特徴要素検出部15は、ポリゴンメッシュを構成する各要素、すなわちポリゴンとポリゴン稜線及びポリゴン頂点を抽出して、抽出した各要素を隣接関係が辿れるように格納する。この各要素を検出した後、特徴要素の検出処理に入る。特徴要素の検出処理では、まず、形状特徴を表すポリゴン稜線の検出処理を行う(ステップS12)。形状特徴を表すポリゴン稜線の検出は、例えば、下記文献に記載された既存の方法を適用することにより検出することができる。
文献;Maria-Elena Alogorri and Francis Schmitt
「Mesh Simplification」
EUROGRAPHICS'96,15,3,C:79-86,1996.

0034

この方法は、図9に示すように,稜線を共有する2つのポリゴンから定義される2面角βを算出し(ステップS13)、算出した2面角αが指定した値よりも小さな角度を持つ稜線を形状特徴を表すポリゴン稜線と判定する(ステップS14)。特定属性付与部16は、この形状特徴を表すと判定されたポリゴン稜線には特徴属性を設定し、それ以外のポリゴン稜線には属性は設定しないでおく(ステップS15)。ポリゴン稜線の全てを確認したのち形状特徴を表すポリゴン頂点の検出処理に入る(ステップS12,S16)。ポリゴン頂点の検出処理では多面体の頂点における曲率を表す近似ガウス曲率を算出し、形状特徴を表すポリゴン頂点の検出する(ステップS17)。近似ガウス曲率は、そのポリゴン頂点における形状の具合を表す値であり、ポリゴン頂点の周りに集まる全てのポリゴンの形状から決まる。この近似ガウス曲率が大きいほど、形状はその頂点において尖っているか、あるいは凹んでいるといえる。したがって近似ガウス曲率の絶対値が指定した値よりも大きい頂点を形状特徴を表すポリゴン頂点であると判定する(ステップS18)。この近似ガウス曲率の算出は、例えば下記文献に記載された既存の方法を用いて行うことができる。
文献;Calladine,CR,
「Gaussian curvature and shell structures」
The Mathematics of Surfases,ed.
JA Gregory, Oxford University Press,pp.197-196,1986.

0035

この方法によると、近似ガウス曲率は曲面を近似した多面体の頂点における曲率の近似値と定義されている。図10(a)に示すように、頂点Vに集まる面を3次元空間で表すと、頂点Vにおける近似ガウス曲率Kは式K=β/Sにより求めることができる。ここで、βは、β=〔2π−(Vに集まる面の隅の角度の総和)〕と定義され、Sは、S=1/3(Vに集まる面の面積の総和)と定義される。図10(b)は図10(a)に示す頂点Vに集まる面を、面F1とF5の間で切り分けて2次元空間に置き換えて表したものである。そして形状特徴を表すと判定されたポリゴン頂点には特徴属性を設定し、それ以外のポリゴン頂点には属性は設定しないでおく。ポリゴン頂点の全てを確認すると、形状特徴出力部17はポリゴンメッシュデータの表示処理に入る(ステップS16,S20)。ポリゴンメッシュデータの表示処理では特徴属性の設定されているポリゴン稜線はそれ以外のポリゴン稜線とは異なる色で表示し、特徴属性の設定されているポリゴン頂点はそれ以外のポリゴン頂点とは異なる色で表示する。図11は表示の例を示し、(a)は対象となるポリゴンメッシュのワイヤーフレーム表示を示し、(b)は対象となるポリゴンメッシュのシェーディング表示、(c)は対象となるポリゴンメッシュの形状特徴を表示したものである。図11(c)において、太い線で表示されている稜線は特徴属性の設定されたポリゴン稜線であり、黒丸で表示されている頂点は特徴属性の設定されたポリゴン頂点である。

0036

このようにしてポリゴンメッシュによる形状モデルの形状特徴をそれ以外の部分と判別できるように表示装置3に表示するから、形状特徴の把握を容易に行うことができ、ポリゴンメッシュ編集の作業量が軽減できる。

0037

また、上記実施例はポリゴンメッシュ生成部10と形状特徴提示部11でポリゴンメッシュの作成とポリゴンメッシュの形状特徴提示を行った場合について説明したが、ポリゴンメッシュの作成プログラムとポリゴンメッシュの形状特徴提示プログラムを外部の記録媒体5に記憶しておき、CPU6で記録媒体5に記憶したポリゴンメッシュの作成プログラムとポリゴンメッシュの形状特徴提示プログラムによりポリゴンメッシュの作成とポリゴンメッシュの形状特徴提示を行っても良い。

発明の効果

0038

この発明は以上説明したように、3次元の点の集まりから定義される形状を作成するとき、点の集まりで定義される凸包列を生成し、点の集まりを3次元空間内で入れ子状に階層化してから点の集まりを処理するから、初期ポリゴンメッシュを容易に生成できるとともに、空間中に散在している点が階層的に分割されることによりポリゴンメッシュを得る処理の対象を限定してポリゴンメッシュの生成を効率的に行うことができる。

0039

また、点の集まりで定義される凸包列を生成するときに、最外殻凸包を初期外殻ポリゴンメッシュとしたあと、外殻ポリゴンメッシュの面を一つ内側へ凸包の頂点へ凹ませることを繰り返して、点の集まり中のすべて点を頂点とするポリゴンメッシュを生成するから、初期ポリゴンメッシュから与えられたすべての点を頂点とするポリゴンメッシュへの変形がを行うことができる。

0040

さらに、外殻の面を凹ませるとき、変形された外殻ポリゴンメッシュの表面積が最小となるように面を凹ませるから、初期ポリゴンメッシュから目的のポリゴンメッシュへの変形に於ける処理を明確に行うことができる。

0041

また、面を凹ませるときに、一つの頂点へ面を凹ませるたときに凹んだ面の周辺に対して局所的なポリゴンメッシュの面積が小さくなるようにして、変形された外殻ポリゴンメッシュの表面積が最小となるようにするから、初期ポリゴンメッシュから目的のポリゴンメッシュへの変形を限定的な範囲で行うことができ、ポリゴンメッシュデータの生成を効率的に行うことができる。

0042

さらに、3角形ポリゴンメッシュから形状特徴を表す要素を検出し、検出された形状特徴を表す要素の特定の属性を与え、特定の属性を持つ要素を他の要素と区別して3角形ポリゴンメッシュとともに表示するから、形状特徴の把握を容易に行うことができ、ポリゴンメッシュ編集の作業量を軽減できる。

0043

また、検出された形状特徴を表す要素を形状特徴を表すポリゴン稜線とポリゴン頂点とすることにより形状特徴の把握を容易に行うことができる。

0044

さらに、特定の属性を持つ要素を他の要素と異なる色で表示することにより、形状特徴の把握をより容易に行うことができる。

0045

また、記録媒体にポリゴンメッシュの作成プログラムとポリゴンメッシュの形状特徴提示プログラムを記録し、コンピュータにより読み取り可能とすることにより、ポリゴンメッシュの作成とポリゴンメッシュの形状特徴提示を容易に行うことができる。

図面の簡単な説明

0046

図1この発明の実施例の構成を示すブロック図である。
図2ポリゴンメッシュの作成処理を示すフローチャートである。
図3画像の点集合を示す表示図である。
図4点集合に対する凸包多面体を示す表示図である。
図5凸包多面体列を示す表示図である。
図6稜線交換処理を示す説明図である。
図7ポリゴンメッシュの変形処理を示す表示図である。
図8ポリゴンメッシュの形状特徴提示処理を示すフローチャートである。
図9ポリゴン稜線の検出処理を示す説明図である。
図10ポリゴン頂点の検出処理を示す説明図である。
図11ポリゴンメッシュを示す表示図である。

--

0047

1 制御部
2入力装置
3表示装置
4プロッタ
5記憶媒体
6 CPU
7 ROM
8 RAM
9外部メモリインタフェース
10ポリゴンメッシュ生成部
11形状特徴提示部
12凸包多面体列生成部
13初期3角形ポリゴンメッシュ生成部
14 ポリゴンメッシュ変形部
15特徴要素検出部
16特定属性付与部
17 形状特徴出力部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ