JP4480306B2 - Mesh simplification device, program and storage medium - Google Patents

Description

【００４７】
次に、メッシュを構成するすべての頂点についてＱ行列を計算する。頂点ｖのＱ行列Ｑ（ｖ）は、（２）式のように頂点のまわりの隣接する三角形面ｆ_ｉ（ここで、ｉ＝０，１，…，ｎ−１とする）のＱ行列Ｑ（ｆ_ｉ）の和になる。
【００４８】
Ｑ_ｆ（ｖ）＝Ｑ（ｆ_０）＋Ｑ（ｆ_１）＋…＋Ｑ（ｆ_ｎ−１） …… （２）
【００４９】
次に、頂点ペアをすべての稜線及び（３）式を満たす頂点の組（ｖ_１，ｖ_２）とする。
【００５０】
||ｖ_１−ｖ_２||＜δ …… （３）
但し、“|| ||”は絶対値を示す（以下同様）。
【００５１】
δは、頂点共有を行なう距離のしきい値で、大きければ大きいほど頂点の組が増える。そして、すべての頂点ペアについて、最適化頂点座標を計算する。最適化頂点座標ｖ_ｏｐｔは、頂点ペアに隣接するすべての面、すなわち始点ｖ_ｓ、終点ｖ_ｅに隣接するすべての面と最適化頂点座標ｖ_ｏｐｔとの距離の２乗和が最も小さくなる座標である。
【００５２】
【数２】

が最も小さくなる座標である。
【００５３】
ここでは、頂点ぺアの隣接面のＱ行列の和Ｑ（ｖ_ｐａｉｒ）を、始点頂点ｖ_ｓと終点頂点ｖ_ｅの隣接面のＱ行列の和Ｑ（ｖ_ｓ），Ｑ（ｖ_ｅ）を加えることにより（５）式のように求め、始点頂点、終点頂点に隣接するすべての面のＱ行列の和とする。
【００５４】
Ｑ_ｆ（ｖ_ｐａｉｒ）＝Ｑ_ｆ（ｖ_ｓ）＋Ｑ_ｆ（ｖ_ｅ） …… （５）
厳密には頂点ペアが稜線である場合、面を共有するため異なるが、計算を簡単にするため、そのようにする。
【００５５】
そうすると、最適化頂点ｖ_ｏｐｔと頂点ペアに隣接するすべての面との距離の２乗和は、
ｖ^Ｔ _ｏｐｔＱ_ｆ（ｖ_ｐａｉｒ）ｖ_ｏｐｔ …… （６）
となる。
【００５６】
この値が最小になるｖ_ｏｐｔは、この式をｘ，ｙ，ｚそれぞれについて微分することにより得られる連立方程式
【００５７】
【数３】

の解になる。
【００５８】
ここでＡは３行３列の行列、ｖ，ｂは次元数が３の列ベクトル、ｃはスカラとし、Ｑ（ｖ_ｐａｉｒ）をブロック分解した結果得られるものである。解を求めて、距離の２乗和の（６）式に代入し、頂点コストとする。
【００５９】
次に、図３以下のフローチャートを参照して、メッシュ簡単化装置１が行なうメッシュ簡単化の処理について説明する。
【００６０】
まず、かかる処理の概要について、図３を参照して説明する。図３に示すように、ＣＰＵ２は、まず、対象となる元メッシュのすべての面について（１）式を用いてＱ行列を計算する（ステップＳ１）。次いで、元メッシュのすべての頂点についてＱ行列、Ｑ_ｆ行列、面リスト、面数を計算する（詳細は後述）（ステップＳ２）。頂点についてＱ行列については（８）式を用いて計算する。
【００６１】
【数４】

【００６２】
そして、元メッシュのすべての頂点ペアについてＱ_ｆ行列、最適化頂点、頂点ペアコスト、最大又は平均の距離を、それぞれ計算し、メモリ３などに構築した頂点ペアキューに保存する（詳細は後述）（ステップＳ３）。ステップＳ３により推定手段、推定処理を実現している。
【００６３】
次いで、頂点ペアコストの低い順に頂点ペアキューをソートし（ステップＳ４）、ソート後の頂点ペアキューの先頭要素について検査・削除更新する（詳細は後述）（ステップＳ５）。ステップＳ５により判定手段、判定処理を実現している。そして、頂点ペアキューの先頭要素が存在しない場合、すなわち空の場合は（ステップＳ６のＹ）、処理を終了する。空でなければ（ステップＳ６のＮ）、ステップＳ７に進む。ステップＳ７では、頂点ペアキューの先頭の頂点ペアについて頂点共有化操作を行なう（詳細は後述）。ステップＳ７により頂点共有化手段、頂点共有化処理を実現している。そして、頂点ペアの始点頂点ｖ_ｓに隣接する頂点ペアについて、ステップＳ３と同様に、Ｑ_ｆ行列、最適化頂点、頂点ペアコスト、最大又は平均の距離を、それぞれ計算し、メモリ３などに構築した頂点ペアキューに保存して（ステップＳ８）、ステップＳ５に戻る。以上の処理により指定誤差の範囲内の簡単化メッシュを得ることができる。
【００６４】
次に、図４のフローチャートを参照して、前記ステップＳ２について詳細に説明する。すなわち、元メッシュのすべての頂点についてＱ行列、Ｑ_ｆ行列、面リスト、面数を計算するには、以下の操作を元メッシュのすべての頂点について行なう。まず、（８）式を用いて頂点のＱ行列を計算する（ステップＳ１１）。次いで、（２）式を用いて頂点のＱ_ｆ行列を計算する（ステップＳ１２）。
【００６５】
このメッシュ簡単化装置１では、元メッシュの面と簡単化メッシュの頂点の最大距離、あるいは、平均距離を求める。そして、これらの処理を行なうには、いくつかの距離算出方式が考えられる。これらの距離算出方式としては、最大距離を求めるものとして次の最大距離方式１〜２、平均距離を求めるものとして次の平均距離方式１〜４が考えられる。
【００６６】
最大距離方式1
元のメッシュの頂点と簡単化メッシュの面との間の距離の最大値を最大距離として計算する。
【００６７】
最大距離方式2
元のメッシュの頂点と簡単化メッシュの面との間の距離及び元のメッシュの面と簡単化メッシュの頂点との距離の最大値を最大距離として計算する。
【００６８】
平均距離方式１
元のメッシュの頂点と簡単化メッシュの面の間の距離の平均値を平均距離として計算する。
【００６９】
平均距離方式2
元のメッシュの頂点と簡単化メッシュの面との間の距離及び元のメッシュの面と簡単化メッシュの頂点との距離の平均値を平均距離として計算する。
【００７０】
平均距離方式３
簡単化メッシュの面コストを元メッシュの頂点数で割った値の平方根を平均距離とて計算する。
【００７１】
平均距離方式4
頂点ペアコスト及び簡単化メッシュの面コストの和を削除面数と削除頂点数の和により割った値の平方根を平均距離として計算する。
【００７２】
そして、これらのうち何れの方式を用いるかに応じて、所定の計算を行なう（ステップＳ１３）。すなわち、最大距離方式２又は平均距離方式２を用いる場合は、隣接する面の面リストの計算を行ない、平均距離方式３，４を用いる場合は、隣接する面の面数の計算を行なう。両リストの各要素は、元メッシュの面への参照が可能な情報（具体的には元メッシュの面のＩＤや名称、ポインタなど）が収められており、各面の幾何的な情報（面の頂点座標や面の法線ベクトル）への参照ができるものとする。
【００７３】
次に、図５のフローチャートを参照して、前記ステップＳ３について詳細に説明する。すなわち、（４）式を用いて、頂点ペアのＱ_ｆ行列を計算する（ステップＳ２１）。次いで、（６）式を用いて、頂点共有を行った場合の最適化頂点位置を計算し、頂点ペアキューに保存する（ステップＳ２２）。次いで、（５）式を用いて頂点ペアコストを計算し、頂点ペアキューに保存する（ステップＳ２３）。そして、（９）式を用いて、面コストを計算する（ステップＳ２４）。
【００７４】
【数５】

【００７５】
ここで、ｎは、最適化頂点位置で頂点共有化を行った場合の隣接面の平面の方程式を表わすベクトルである。Ｑ_ｖは頂点共有化を行ない失われた頂点のＱ行列の和を示しており、初期値はＱ（ｖ_ｓ）とＱ（ｖ_ｅ）の和になる。すなわち、（１０）式のとおり。
【００７６】
【数６】

【００７７】
次いで、前記の距離算出方式に応じた処理をおこなう（ステップＳ２５）。
【００７８】
すなわち、最大距離方式１の場合は、頂点共有化した際に失われる元メッシュの頂点の座標と、頂点共有化後の面との間の距離の中で最大のものを求め、頂点ペアキューに保存する。面と頂点座標との距離は、次の（１１）式を用いて計算する。
【００７９】
dist（ｖ，ｆ）＝||ａｘ＋ｂｙ＋ｃｚ＋ｄ||，ａ^２＋ｂ^２＋ｃ^２＝１……（１１）
但し、（ｘ，ｙ，ｚ）は頂点の座標、ａｘ＋ｂｙ＋ｃｚ＋ｄは面ｆを表わす平面の式とする。
【００８０】
最大距離方式２の場合は、ステップＳ１３の面コストから参照されるすべての面と最適化頂点との距離、及び、頂点共有化した際に失われる頂点と、頂点共有化した際の面との間の距離の中で最大のものを求め、頂点ペアキューに保存する。
【００８１】
平均距離方式１の場合は、頂点共有化した際に失われる元メッシュの頂点座標頂点共有化した際の面との間の距離の相加平均を求め、頂点ペアキューに保存する。
【００８２】
平均距離方式２の場合は、最適化頂点とステップＳ１３の面リストとの間の距離、及び、頂点共有化した際の面との間の距離の相加平均を求め、頂点ペアキューに保存する。
【００８３】
平均距離方式３の場合は、面コストを“削除頂点数×頂点共有後の隣接面数”で除算し、その平方根を計算することにより、平均距離を求め、頂点ペアキューに保存する。すなわち、（１２）式のとおり。
【００８４】
【数７】

【００８５】
ここで、♯ｖ_ｏｌｄは頂点共有化により失われた頂点の数であり、♯ｆ（ｖ_ｏｐｔ）は頂点共有化後の頂点に隣接する面の数である。
【００８６】
平均距離方式４の場合は、（１３）式に示す頂点ペアコストと面コストとの和を求め、始点及び終点の面数の和、さらに、“削除頂点数×頂点共有後の隣接面数”を加えた値で除算し、その平方根を計算することにより、平均距離を求め、頂点ペアキューに保存する。
【００８７】
【数８】

【００８８】
ここで、ｖ_ｓ，ｖ_ｅは頂点ペアｖ_ｐａｉｒそれぞれの始点頂点、終点頂点であり、♯ｆ（ｖ）は頂点ｖに隣接する数である。
【００８９】
図６のフローチャートを参照して、前記ステップＳ５について詳細に説明する。すなわち、頂点ペアキューの先頭の要素について検査・削除を行なうには、図６に示すように、まず、頂点ペアキューにおける先頭の要素の有無を調べ（ステップＳ３１）、あれば（ステップＳ３１のＹ）、ステップＳ３２に進み、なければ（ステップＳ３１のＮ）、処理を終了することで行なう。
【００９０】
ステップＳ３２では、その要素の推定誤差が指定誤差を上回っていないか調べ、上回っていなければ（ステップＳ３２のＮ）、処理を終了する。上回っていれば（ステップＳ３２のＹ）、その要素を頂点ペアキューから削除し（ステップＳ３３）、ステップＳ３１に戻る。すなわち、推定誤差は元メッシュの簡単化を行った場合の簡単化の程度を示すものであり、指定誤差は推定誤差の基準値として予め指定された値である。
【００９１】
図７のフローチャートを参照して、前記ステップＳ７について詳細に説明する。すなわち、項点ペアキューから先頭の頂点ペアを取り出し、頂点ペアキューから削除する（ステップＳ４１）。次いで、頂点ペアキューの先頭の要素に一致する頂点ペアについて、図２を参照して説明したような頂点共有化操作を行なう（ステップＳ４２）。そして、最適化頂点座標を、残った始点側の頂点ｖ_ｓの座標として設定する（ステップＳ４３）。
【００９２】
この操作で、頂点ペアｅ、頂点ペアeの両側の面、頂点ペアeの終点側の頂点ｖ_ｅが削除される。次いで、ｖ_ｓのＱ行列にｖ_ｅのＱ行列を加える（ステップＳ４４）。次いで、前記の距離算出方式に応じた処理を行なう（ステップＳ４５）。すなわち、最大距離算出方式１及び平均距離算出方式１では、ｖ_ｓの削除頂点リストにｖ_ｅを加える。最大距離算出方式２及び平均距離算出方式２では、ｖ_ｓの面リストにｖ_ｅの面リストを加えた後、ｖ_ｓの削除頂点リストにｖ_ｅを加える。平均距離算出方式３では、ｖ_ｓの削除頂点数を１増やす。平均距離算出方式４では、ｖ_ｓの面数にｖ_ｅの面数を加えた後、ｖ_ｓの削除頂点数を１増やす。
【００９４】
【発明の効果】
請求項１に記載の発明は、元メッシュの面と簡単化メッシュの頂点との最大距離を求めるために、元メッシュの面と簡単化メッシュの面との間の距離の最大値を求めることで、元メッシュと簡単化メッシュとの間の距離を正確に求めることができる。
【００９５】
請求項２に記載の発明は、元メッシュの面と簡単化メッシュの頂点との平均距離を求めるために、元メッシュの面と簡単化メッシュの面との間の距離の平均値を求めることで、元メッシュと簡単化メッシュとの間の距離を正確に求めることができる。
【００９６】
請求項３に記載の発明は、元メッシュの面と簡単化メッシュの頂点との平均距離を求めるために、元メッシュの面と簡単化メッシュの面との間の距離の平均値を求めることで、元メッシュと簡単化メッシュとの間の距離を正確に求めることができる。
【００９７】
請求項４に記載の発明は、元メッシュの面と簡単化メッシュの頂点との平均距離を求めるために、元メッシュの面と簡単化メッシュの面との間の距離の平均値を求めることで、元メッシュと簡単化メッシュとの間の距離を正確に求めることができる。
【００９８】
請求項５に記載の発明は、元メッシュの面と簡単化メッシュの頂点との平均距離を求めるために、元メッシュの面と簡単化メッシュの面との間の距離の平均値を求めることで、元メッシュと簡単化メッシュとの間の距離を正確に求めることができる。
【０１００】
請求項６に記載の発明は、元メッシュの面と簡単化メッシュの頂点との最大距離を求めるために、元メッシュの頂点と簡単化メッシュの面との間の距離の最大値を求めることで、元メッシュと簡単化メッシュとの間の距離を正確に求めることができる。
【０１０１】
請求項７に記載の発明は、元メッシュの面と簡単化メッシュの頂点との平均距離を求めるために、元メッシュの面と簡単化メッシュの面との間の距離の平均値を求めることで、元メッシュと簡単化メッシュとの間の距離を正確に求めることができる。
【０１０２】
請求項８に記載の発明は、元メッシュの面と簡単化メッシュの頂点との平均距離を求めるために、元メッシュの面と簡単化メッシュの面との間の距離の平均値を求めることで、元メッシュと簡単化メッシュとの間の距離を正確に求めることができる。
【０１０３】
請求項９に記載の発明は、元メッシュの面と簡単化メッシュの頂点との平均距離を求めるために、元メッシュの面と簡単化メッシュの面との間の距離の平均値を求めることで、元メッシュと簡単化メッシュとの間の距離を正確に求めることができる。
【０１０４】
請求項１０に記載の発明は、元メッシュの面と簡単化メッシュの頂点との平均距離を求めるために、元メッシュの面と簡単化メッシュの面との間の距離の平均値を求めることで、元メッシュと簡単化メッシュとの間の距離を正確に求めることができる。
【０１０５】
請求項１１に記載の発明は、請求項６〜１０のいずれかの一に記載の発明と同様の効果を奏する。
【図面の簡単な説明】
【図１】この発明の一実施の形態であるメッシュ簡単化装置の電気的な接続を示すブロック図である。
【図２】頂点共有化操作について説明する説明図である。
【図３】前記メッシュ簡単化装置が行なう処理について説明するフローチャートである。
【図４】同フローチャートである。
【図５】同フローチャートである。
【図６】同フローチャートである。
【図７】同フローチャートである。
【符号の説明】
１ メッシュ簡単化装置
３ 記憶装置[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a mesh simplification device, a program, and a storage medium that generate a simplified mesh simplified by reducing the number of elements of an original mesh.
[0002]
[Prior art]
In recent years, the use of three-dimensional representations has expanded with the spread of multimedia on the Internet, and the importance of three-dimensional shape display has increased. Recently, in order to display large-scale design data at a higher speed using an existing graphics display device, the shape of a triangular mesh (referred to as “mesh” in this specification) as shape data is not affected as much as possible. As described above, research on techniques for reducing and simplifying the number of elements has been actively conducted (in this specification, a mesh to be simplified is referred to as an “original mesh”, and a simplified mesh is referred to as a “simplified mesh”).
[0003]
In particular, vertex sharing and QEM represented by the technique disclosed in “Michael Garland and Paul S. Heckbert:“ Surface simplification using quadric error metrics ”, SIGGRAPH '97 Conference Proceedings, pp.209-216, Aug 1997” There are many studies using Quadric Error Metrics.
[0004]
[Problems to be solved by the invention]
However, although the above-described conventional technique can obtain a high-quality simplified mesh at high speed, the degree of simplification cannot be designated in advance. In other words, in the prior art, only the final number of faces can be specified, and simplification with an appropriate degree of simplification by trial and error such as actually specifying the number of faces and generating a simplified mesh for evaluation. I got a mesh. Therefore, there is a problem that it takes a very long time to obtain a simplified mesh having an appropriate degree of simplification.
[0005]
On the other hand, the applicant of the present application has proposed a technique for obtaining an average distance and a maximum distance between the surface of the mesh from the QEM and the simplified mesh (Japanese Patent Application No. 2001- filed on May 11, 2001). 141070 (unpublished at the time of filing this application)).
[0006]
However, we would like to determine the distance between the original mesh and the simplified mesh more accurately than the results obtained with this technique.
[0007]
An object of the present invention is to accurately obtain a distance between an original mesh and a simplified mesh so that a simplified mesh having an appropriate degree of simplification can be quickly created.
[0010]
[Means for Solving the Problems]
  Claim1In the mesh simplification device for generating a simplified mesh simplified by reducing the number of elements of the original mesh, the estimation error that is the degree of simplification when the vertex sharing operation of the mesh is performed Is calculated for each vertex pair, and the calculation of the estimation error is performed by storing a surface to be deleted by the vertex sharing operation in a storage device for each vertex remaining by the vertex sharing operation and remaining by the vertex sharing operation. The maximum value of the distance between the coordinates of the vertex and the stored surface is calculated, and the vertex deleted by the vertex sharing operation is stored in the storage device for each vertex, and the vertex sharing is performed. The maximum value of the distance between the surface adjacent to the remaining vertex by the operation and the stored coordinates of the vertex is calculated, and the larger of the two maximum values is calculated as the surface of the original mesh and the simplified mesh. As the maximum distance from the vertex of Estimation means for performing the estimation, determination means for determining whether the estimation error exceeds a specified error that is a value specified in advance as a reference value of the estimation error, and the estimation error based on the determination A mesh simplification apparatus comprising: vertex sharing operation means for sequentially executing the vertex sharing operation that does not exceed an error from the vertex pair with the smallest estimation error.
[0011]
Therefore, in order to find the maximum distance between the face of the original mesh and the vertex of the simplified mesh, the maximum value of the distance between the face of the original mesh and the face of the simplified mesh is obtained. The distance between the two can be accurately determined.
[0012]
  Claim2In the mesh simplification device for generating a simplified mesh simplified by reducing the number of elements of the original mesh, the estimation error that is the degree of simplification when the vertex sharing operation of the mesh is performed For each vertex pair, the calculation of this estimation error is to store the vertices deleted by the vertex sharing operation in a storage device for each vertex, and the surface adjacent to the remaining vertices by the vertex sharing operation and the By calculating the average distance between the stored coordinates of the vertices and calculating the average distance between the surface of the original mesh and the vertices of the simplified mesh, the estimation error includes: Determining means for determining whether or not a specified error that is a value specified in advance as a reference value for the estimated error is exceeded; and based on this determination, the vertex sharing operation in which the estimated error does not exceed the specified error. A mesh simplified apparatus characterized by comprising a vertex sharing operation means for executing sequentially from smaller the apex pairs of the estimation error a.
[0013]
Therefore, in order to find the average distance between the face of the original mesh and the vertex of the simplified mesh, the average value of the distance between the face of the original mesh and the face of the simplified mesh is obtained. The distance between the two can be accurately determined.
[0014]
  Claim3In the mesh simplification device for generating a simplified mesh simplified by reducing the number of elements of the original mesh, the estimation error that is the degree of simplification when the vertex sharing operation of the mesh is performed Is calculated for each vertex pair, and the calculation of the estimation error is performed by storing a surface to be deleted by the vertex sharing operation in a storage device for each vertex remaining by the vertex sharing operation and remaining by the vertex sharing operation. The average value of the distance between the coordinates of the vertex and the stored surface is calculated, and the vertex deleted by the vertex sharing operation is stored in the storage device for each vertex, and the vertex sharing is performed. Obtaining an average distance between the surface of the original mesh and the vertex of the simplified mesh by calculating the average value of the distance between the surface adjacent to the remaining vertex by the operation and the coordinates of the stored vertex; Estimating means performed in Determining means for determining whether or not the estimated error exceeds a specified error that is a value specified in advance as a reference value of the estimated error; and the vertex whose estimated error does not exceed the specified error based on this determination A mesh simplification apparatus comprising: a vertex sharing operation unit that sequentially executes a sharing operation from the vertex pair with a small estimation error.
[0015]
Therefore, in order to find the average distance between the face of the original mesh and the vertex of the simplified mesh, the average value of the distance between the face of the original mesh and the face of the simplified mesh is obtained. The distance between the two can be accurately determined.
[0016]
  Claim4In the mesh simplification device for generating a simplified mesh simplified by reducing the number of elements of the original mesh, the estimation error that is the degree of simplification when the vertex sharing operation of the mesh is performed Is calculated for each vertex pair, and the calculation of this estimation error is performed by storing the sum of squares of the coordinates of the vertices deleted by the vertex sharing operation and the number of vertices in the storage device as attributes of the remaining vertices by the vertex sharing operation. The square root of the value obtained by calculating the product of the vector of the plane formula coefficients of the surface adjacent to the remaining vertices and the sum of squares as the cost value of the surface and dividing the cost value by the number of vertices Is estimated as an average distance between the surface of the original mesh and the vertex of the simplified mesh, and the estimation error exceeds a specified error which is a value specified in advance as a reference value of the estimated error. Determining means for determining whether or not, and vertex sharing operation means for executing the vertex sharing operation in which the estimation error does not exceed the specified error based on the determination in order from the vertex pair with the small estimation error, It is the mesh simplification apparatus characterized by having.
[0017]
Therefore, in order to find the average distance between the face of the original mesh and the vertex of the simplified mesh, the average value of the distance between the face of the original mesh and the face of the simplified mesh is obtained. The distance between the two can be accurately determined.
[0018]
  Claim5In the mesh simplification device for generating a simplified mesh simplified by reducing the number of elements of the original mesh, the estimation error that is the degree of simplification when the vertex sharing operation of the mesh is performed Is calculated for each vertex pair, and the calculation of this estimation error is performed by storing the number of faces deleted by the vertex sharing operation in a storage device for each vertex remaining by the vertex sharing operation, and QEM (Quadric Error Metrics) The vertex pair cost value calculated by the method, the sum of squares of the coordinates of the vertices deleted by the vertex sharing operation, and the number of vertices are stored in the storage device as attributes of the vertices remaining by the vertex sharing operation. The sum of the cost values of the surface calculated as the product of the vector of the plane equation of the surface adjacent to the remaining vertex and the sum of squares is obtained, and this sum is calculated as the number of surfaces to be deleted. Vertex sharing Estimating means for obtaining the square root of the value divided by the sum of the number of vertices to be deleted by the operation as an average distance between the surface of the original mesh and the vertices of the simplified mesh, and the estimation error is the estimation error Determining means for determining whether or not a specified error that is a value specified in advance as a reference value of the reference value is determined, and based on this determination, the vertex sharing operation in which the estimated error does not exceed the specified error is performed. A mesh simplification apparatus comprising: a vertex sharing operation unit that executes in order from a small number of vertex pairs.
[0019]
Therefore, in order to find the average distance between the face of the original mesh and the vertex of the simplified mesh, the average value of the distance between the face of the original mesh and the face of the simplified mesh is obtained. The distance between the two can be accurately determined.
[0022]
  Claim6In the invention described in the above, the vertex sharing operation of the mesh is performed in a computer-readable program that causes a computer to execute a process for generating a simplified mesh by reducing the number of elements of the original mesh. An estimation error that is a degree of simplification in each case is obtained for each vertex pair, and the calculation of the estimation error is performed by storing a surface to be deleted by the vertex sharing operation in a storage device for each vertex remaining by the vertex sharing operation. The maximum value of the distance between the coordinates of the vertices remaining in the vertex sharing operation and the stored surface is calculated, and the vertices deleted by the vertex sharing operation are stored for each vertex. And calculating the maximum value of the distance between the surface adjacent to the remaining vertex by the vertex sharing operation and the stored coordinates of the vertex, and the larger of the two maximum values, The original mesh An estimation process performed by obtaining the maximum distance between the surface and the vertex of the simplified mesh, and a determination to determine whether the estimation error exceeds a specified error that is a value specified in advance as a reference value of the estimated error And causing the computer to execute a vertex sharing operation process in which, based on this determination, the vertex sharing operation in which the estimation error does not exceed the specified error is executed in order from the vertex pair with the small estimation error. It is a featured program.
[0023]
Therefore, in order to find the maximum distance between the face of the original mesh and the vertex of the simplified mesh, the maximum value of the distance between the vertex of the original mesh and the face of the simplified mesh is obtained. The distance between the two can be accurately determined.
[0024]
  Claim7In the invention described in the above, the vertex sharing operation of the mesh is performed in a computer-readable program that causes a computer to execute a process for generating a simplified mesh by reducing the number of elements of the original mesh. An estimation error that is a degree of simplification in each case is obtained for each vertex pair, and the calculation of the estimation error is performed by storing the vertex deleted by the vertex sharing operation in a storage device for each vertex, Obtaining an average distance between the surface of the original mesh and the vertex of the simplified mesh by calculating the average value of the distance between the surface adjacent to the remaining vertex by the operation and the coordinates of the stored vertex; And a determination process for determining whether or not the estimation error exceeds a specified error that is a value specified in advance as a reference value for the estimated error, and based on this determination, Estimation error is a program for causing to execute a vertex shared operation processing to be executed sequentially from smaller the apex pairs of the estimated error of the vertex sharing operation does not exceed the specified error into the computer.
[0025]
Therefore, in order to find the average distance between the face of the original mesh and the vertex of the simplified mesh, the average value of the distance between the face of the original mesh and the face of the simplified mesh is obtained. The distance between the two can be accurately determined.
[0026]
  Claim8In the invention described in the above, the vertex sharing operation of the mesh is performed in a computer-readable program that causes a computer to execute a process for generating a simplified mesh by reducing the number of elements of the original mesh. An estimation error that is a degree of simplification in each case is obtained for each vertex pair, and the calculation of the estimation error is performed by storing a surface to be deleted by the vertex sharing operation in a storage device for each vertex remaining by the vertex sharing operation. The average value of the distance between the coordinates of the vertices remaining in the vertex sharing operation and the stored surface is calculated, and the vertices deleted by the vertex sharing operation are stored for each vertex And storing the original mesh surface and the simplification by calculating an average value of the distance between the surface adjacent to the vertex remaining in the vertex sharing operation and the coordinates of the stored vertex. Me An estimation process that is performed by calculating an average distance from the top of the channel, a determination process that determines whether or not the estimation error exceeds a specified error that is a value that is specified in advance as a reference value of the estimated error, and this determination And a vertex sharing operation process for sequentially executing the vertex sharing operation in which the estimation error does not exceed the specified error from the vertex pair with the small estimation error. is there.
[0027]
Therefore, in order to find the average distance between the face of the original mesh and the vertex of the simplified mesh, the average value of the distance between the face of the original mesh and the face of the simplified mesh is obtained. The distance between the two can be accurately determined.
[0028]
  Claim9In the invention described in the above, the vertex sharing operation of the mesh is performed in a computer-readable program that causes a computer to execute a process for generating a simplified mesh by reducing the number of elements of the original mesh. An estimation error that is a degree of simplification in each case is obtained for each vertex pair, and this estimation error is calculated by calculating the sum of squares of the coordinates of the vertices to be deleted by the vertex sharing operation and the number of vertices. Is stored in the storage device as the attribute of the remaining vertex, and the product of the vector of the plane formula of the surface adjacent to the remaining vertex and the sum of squares is calculated as the cost value of the surface, and this cost value Is calculated by obtaining the square root of the value obtained by dividing the number of vertices by the average distance between the surface of the original mesh and the vertices of the simplified mesh, and the estimation error is the estimation error. A determination process for determining whether or not a specified error that is a value specified in advance as a reference value is exceeded, and the vertex sharing operation in which the estimated error does not exceed the specified error based on this determination is performed with a small estimated error A program for causing a computer to execute vertex sharing operation processing executed in order from the vertex pair.
[0029]
Therefore, in order to find the average distance between the face of the original mesh and the vertex of the simplified mesh, the average value of the distance between the face of the original mesh and the face of the simplified mesh is obtained. The distance between the two can be accurately determined.
[0030]
  Claim10In the invention described in the above, the vertex sharing operation of the mesh is performed in a computer-readable program that causes a computer to execute a process for generating a simplified mesh by reducing the number of elements of the original mesh. The estimation error, which is the degree of simplification of the case, is obtained for each vertex pair, and the calculation of this estimation error stores the number of faces deleted by the vertex sharing operation in the storage device for each vertex remaining by the vertex sharing operation. The vertex pair cost value calculated by the QEM (Quadric Error Metrics) method and the sum of squares of the coordinates of the vertexes deleted by the vertex sharing operation and the number of vertices are obtained by the vertex sharing operation. The sum of the cost values of the surface calculated as the product of the vector of the plane equation coefficients of the surface adjacent to the remaining vertex and the sum of squares is stored in the storage device as the attribute of the remaining vertex. The square root of the value obtained by dividing the sum by the sum of the number of faces to be deleted and the number of vertices to be deleted by the vertex sharing operation is an average distance between the face of the original mesh and the vertices of the simplified mesh. The estimation process performed by obtaining the estimation error, the determination process for determining whether or not the estimation error exceeds a specified error that is a value specified in advance as a reference value of the estimation error, and the estimation error based on this determination A program for causing a computer to execute a vertex sharing operation process in which the vertex sharing operation that does not exceed the specified error is executed in order from the vertex pair with the smallest estimation error.
[0031]
Therefore, in order to find the average distance between the face of the original mesh and the vertex of the simplified mesh, the average value of the distance between the face of the original mesh and the face of the simplified mesh is obtained. The distance between the two can be accurately determined.
[0032]
  Claim11The invention described in claim6~10A computer-readable storage medium storing the program according to any one of the above.
[0033]
Therefore, the claims6~10The same action and effect as the invention described in any one of the above are obtained.
[0034]
DETAILED DESCRIPTION OF THE INVENTION
An embodiment of the present invention will be described.
[0035]
FIG. 1 is a block diagram showing electrical connection of a mesh simplification apparatus 1 according to an embodiment of the present invention. As shown in FIG. 1, the mesh simplification apparatus 1 is a computer such as a PC, which performs various calculations and centrally controls each part of the mesh simplification apparatus 1, and a memory composed of various ROMs and RAMs. A memory 3 as a device is connected by a bus 4.
[0036]
The bus 4 is provided with a magnetic storage device 5 such as a hard disk, an input device 6 including a mouse and a keyboard, a display device 7, and a storage medium reading device such as an optical disk via a predetermined interface. A device 9 is connected, and a predetermined communication interface 11 for communicating with a network 10 such as the Internet is connected. As the storage medium 8, various media such as an optical disk such as a CD and a DVD, a magneto-optical disk, and a floppy disk can be used. As the storage medium reader 9, specifically, an optical disk device, a magneto-optical disk device, a floppy disk device, or the like is used according to the type of the storage medium 8.
[0037]
The magnetic storage device 5 stores a mesh simplification program. This mesh simplification program is installed in the magnetic storage device 5 by being read from the storage medium 8 by the storage medium reader 9 or downloaded from the network 10 such as the Internet. By this installation, the mesh simplification apparatus 1 becomes operable. This mesh simplification program may be a part of specific application software such as a dimensional shape viewer for browsing data designed by CAD. Further, it may operate on a predetermined OS.
[0038]
Below, the content of the process which the mesh simplification apparatus 1 performs based on a mesh simplification program is demonstrated.
[0039]
First, the concept that is the premise of the contents of such processing will be described.
[0040]
(1) Simplification of mesh
It is to generate a simplified mesh with fewer elements such as faces, vertices, and edges from the original mesh. A simplified mesh is obtained from the original mesh by performing the vertex sharing operation in ascending order of the edge pair cost calculated by the QEM described below.
[0041]
(2) Vertex pair queue
Each element of the vertex pair queue is information that can refer to the edge of the original mesh along with attribute information such as vertex pair cost, optimized vertex coordinates, and measurement distance (specifically, the ID, name, pointer, etc. of the edge of the original mesh) ) Are stored, and information on each ridge line (vertices forming both end points of the ridge line) can be referred to.
[0042]
(3) Vertex sharing operation
This operation reduces the number of mesh elements. In this operation, a vertex pair (v_s, V_e) At the vertex v_s, Vertex v_eIs deleted. v_s, V_eThere may or may not be a shared ridgeline.
[0043]
FIG. 2 shows an example of the vertex sharing operation. FIG. 2A shows a case where a ridge line shared by a vertex pair exists, and FIG. 2B shows a case where a ridge line shared by the vertex pair does not exist. In FIG. 2 (a), one vertex v is deleted at the same time as one edge E is deleted by the vertex sharing operation._e, Face f sharing a vertex pair_r, F_lIs deleted and one vertex v_sRemains. In FIG. 2B, the element deleted by the vertex sharing operation is v_eOnly. In either case, the surrounding faces and edges after the vertex sharing operation are the remaining vertices v_sTo share.
[0044]
(4) QEM (Quadric Error Metrics)
This is a vertex pair cost calculation method for determining the priority of which vertex pair should be used first for vertex sharing operation.
[0045]
In the method, first, a Q matrix is calculated for all triangular faces constituting the mesh. The Q matrix Q (f) of the surface f is an equation “ax + by + cz + d = 0” (where “a²+ B²+ C²= 1 ”and coordinates (x₀, Y₀, Z₀) And the plane is “ax₀+ By₀+ Cz₀It is defined as the equation (1) using the coefficients a, b, c and d (which are obtained by + d ″).
[0046]
[Expression 1]

[0047]
Next, the Q matrix is calculated for all the vertices constituting the mesh. The Q matrix Q (v) of the vertex v is an adjacent triangular surface f around the vertex as shown in equation (2)._iQ matrix Q (f) (where i = 0, 1,..., N−1)_i).
[0048]
Q_f(V) = Q (f₀) + Q (f₁) + ... + Q (f_n-1) (2)
[0049]
Next, the vertex pair is defined as a pair of vertices (v₁, V₂).
[0050]
|| v₁-V₂|| <δ (3)
However, “||||” indicates an absolute value (the same applies hereinafter).
[0051]
δ is a threshold value for the distance at which vertex sharing is performed. Then, optimized vertex coordinates are calculated for all vertex pairs. Optimized vertex coordinates v_optIs all faces adjacent to the vertex pair, ie the starting point v_s, End point v_eAll faces adjacent to and optimized vertex coordinates v_optThis is the coordinate where the sum of squares of the distance to is the smallest.
[0052]
[Expression 2]

Is the smallest coordinate.
[0053]
Here, the sum Q (v of the Q matrix of adjacent faces of the vertex pair_pair) For the starting vertex v_sAnd end vertex v_eSum of Q matrices of adjacent faces of Q (v_s), Q (v_e) To obtain the sum of the Q matrices of all the faces adjacent to the start point vertex and the end point vertex.
[0054]
Q_f(V_pair) = Q_f(V_s+ Q_f(V_e) (5)
Strictly speaking, if the vertex pair is a ridge line, it is different because it shares a face, but in order to simplify the calculation, it is so.
[0055]
Then, optimization vertex v_optAnd the sum of squares of the distances between all faces adjacent to a vertex pair is
v^T _optQ_f(V_pair) V_opt                    (6)
It becomes.
[0056]
V where this value is minimized_optIs a simultaneous equation obtained by differentiating this expression with respect to x, y, z.
[0057]
[Equation 3]

It becomes the solution of.
[0058]
Where A is a 3 × 3 matrix, v and b are 3 column vectors, c is a scalar, and Q (v_pair) Is obtained as a result of block decomposition. The solution is obtained and substituted into the formula (6) of the sum of squares of the distance to obtain the vertex cost.
[0059]
Next, the mesh simplification process performed by the mesh simplification apparatus 1 will be described with reference to the flowchart in FIG.
[0060]
First, an outline of such processing will be described with reference to FIG. As shown in FIG. 3, the CPU 2 first calculates a Q matrix using the equation (1) for all the faces of the target original mesh (step S1). Then the Q matrix for all vertices of the original mesh, Q_fA matrix, a surface list, and the number of surfaces are calculated (details will be described later) (step S2). For the vertices, the Q matrix is calculated using equation (8).
[0061]
[Expression 4]

[0062]
And Q for all vertex pairs of the original mesh_fThe matrix, the optimized vertex, the vertex pair cost, and the maximum or average distance are calculated and stored in the vertex pair queue built in the memory 3 or the like (details will be described later) (step S3). Step S3 realizes estimation means and estimation processing.
[0063]
Next, the vertex pair queue is sorted in ascending order of the vertex pair cost (step S4), and the first element of the sorted vertex pair queue is inspected / deleted (details will be described later) (step S5). Determination means and determination processing are realized by step S5. If the top element of the vertex pair queue does not exist, that is, if it is empty (Y in step S6), the process is terminated. If not empty (N in step S6), the process proceeds to step S7. In step S7, a vertex sharing operation is performed for the first vertex pair in the vertex pair queue (details will be described later). In step S7, vertex sharing means and vertex sharing processing are realized. And the starting vertex v of the vertex pair_sAs for the vertex pair adjacent to Q, as in step S3, Q_fThe matrix, the optimized vertex, the vertex pair cost, and the maximum or average distance are respectively calculated and stored in the vertex pair queue constructed in the memory 3 or the like (step S8), and the process returns to step S5. With the above processing, a simplified mesh within a specified error range can be obtained.
[0064]
Next, the step S2 will be described in detail with reference to the flowchart of FIG. That is, the Q matrix for all vertices of the original mesh, Q_fTo calculate the matrix, face list, and number of faces, perform the following operation on all vertices of the original mesh. First, the vertex Q matrix is calculated using equation (8) (step S11). Next, the vertex Q using equation (2)_fA matrix is calculated (step S12).
[0065]
In the mesh simplification device 1, the maximum distance or the average distance between the surface of the original mesh and the vertex of the simplified mesh is obtained. In order to perform these processes, several distance calculation methods can be considered. As these distance calculation methods, the following maximum distance methods 1 and 2 can be considered as methods for obtaining the maximum distance, and the following average distance methods 1 through 4 as methods for obtaining the average distance.
[0066]
Maximum distance method 1
The maximum distance between the original mesh vertex and the simplified mesh face is calculated as the maximum distance.
[0067]
Maximum distance method 2
The maximum distance is calculated as the maximum distance between the original mesh vertex and the simplified mesh face and the distance between the original mesh face and the simplified mesh vertex.
[0068]
Average distance method 1
The average distance between the original mesh vertex and the simplified mesh face is calculated as the average distance.
[0069]
Average distance method 2
The average value of the distance between the vertex of the original mesh and the face of the simplified mesh and the average of the distance between the face of the original mesh and the vertex of the simplified mesh are calculated.
[0070]
Average distance method 3
The square root of the value obtained by dividing the surface cost of the simplified mesh by the number of vertices of the original mesh is calculated as the average distance.
[0071]
Average distance method 4
The square root of the value obtained by dividing the sum of the vertex pair cost and the surface cost of the simplified mesh by the sum of the number of deleted faces and the number of deleted vertices is calculated as an average distance.
[0072]
Then, a predetermined calculation is performed according to which method is used (step S13). That is, when the maximum distance method 2 or the average distance method 2 is used, the surface list of the adjacent surfaces is calculated, and when the average distance methods 3 and 4 are used, the number of surfaces of the adjacent surfaces is calculated. Each element of both lists contains information that can refer to the face of the original mesh (specifically, the ID, name, pointer, etc. of the face of the original mesh). Can be referred to).
[0073]
Next, the step S3 will be described in detail with reference to the flowchart of FIG. That is, using equation (4), the vertex pair Q_fA matrix is calculated (step S21). Next, using the equation (6), the optimized vertex position when vertex sharing is performed is calculated and stored in the vertex pair queue (step S22). Next, the vertex pair cost is calculated using equation (5) and stored in the vertex pair queue (step S23). Then, the surface cost is calculated using equation (9) (step S24).
[0074]
[Equation 5]

[0075]
Here, n is a vector representing an equation of the plane of the adjacent surface when vertex sharing is performed at the optimized vertex position. Q_vIndicates the sum of the Q matrices of the lost vertices by sharing the vertices, and the initial value is Q (v_s) And Q (v_e). That is, as shown in equation (10).
[0076]
[Formula 6]

[0077]
Next, processing according to the distance calculation method is performed (step S25).
[0078]
That is, in the case of the maximum distance method 1, the maximum distance between the coordinates of the vertex of the original mesh lost when the vertex is shared and the face after the vertex sharing is obtained, and stored in the vertex pair queue. To do. The distance between the surface and the vertex coordinates is calculated using the following equation (11).
[0079]
dist (v, f) = || ax + by + cz + d ||, a²+ B²+ C²= 1 …… (11)
However, (x, y, z) is a vertex coordinate, and ax + by + cz + d is a plane expression representing the surface f.
[0080]
In the case of the maximum distance method 2, the distances between all the faces referenced from the face cost in step S13 and the optimized vertices, the vertices lost when the vertices are shared, and the faces when the vertices are shared Find the largest of the distances between them and save it in the vertex pair queue.
[0081]
In the case of the average distance method 1, the arithmetic average of the distance between the vertex coordinates of the original mesh that is lost when the vertex is shared and the face when the vertex is shared is obtained and stored in the vertex pair queue.
[0082]
In the case of the average distance method 2, the arithmetic average of the distance between the optimized vertex and the surface list in step S13 and the distance between the surfaces when the vertex is shared is obtained and stored in the vertex pair queue.
[0083]
In the case of the average distance method 3, the surface cost is divided by “the number of deleted vertices × the number of adjacent surfaces after vertex sharing” and the square root is calculated to obtain the average distance, which is stored in the vertex pair queue. That is, as shown in equation (12).
[0084]
[Expression 7]

[0085]
Where #v_oldIs the number of vertices lost due to vertex sharing, and #f (v_opt) Is the number of faces adjacent to the vertex after vertex sharing.
[0086]
In the case of the average distance method 4, the sum of the vertex pair cost and the surface cost shown in the equation (13) is obtained, the sum of the number of surfaces of the start point and the end point, and “the number of deleted vertices × the number of adjacent surfaces after sharing the vertex” The average distance is obtained by dividing by the value obtained by adding and calculating the square root, and stored in the vertex pair queue.
[0087]
[Equation 8]

[0088]
Where v_s, V_eIs the vertex pair v_pairEach is a start point vertex and an end point vertex, and #f (v) is a number adjacent to the vertex v.
[0089]
The step S5 will be described in detail with reference to the flowchart of FIG. That is, in order to inspect and delete the head element of the vertex pair queue, as shown in FIG. 6, first, the presence or absence of the head element in the vertex pair queue is checked (step S31), and if there is (Y in step S31), If it does not proceed to step S32 (N in step S31), the process is terminated.
[0090]
In step S32, it is checked whether the estimated error of the element exceeds the specified error. If it does not exceed the specified error (N in step S32), the process ends. If it exceeds (Y in step S32), the element is deleted from the vertex pair queue (step S33), and the process returns to step S31. That is, the estimation error indicates the degree of simplification when the original mesh is simplified, and the designation error is a value designated in advance as a reference value for the estimation error.
[0091]
The step S7 will be described in detail with reference to the flowchart of FIG. That is, the top vertex pair is extracted from the item pair queue and deleted from the vertex pair queue (step S41). Next, a vertex sharing operation as described with reference to FIG. 2 is performed on the vertex pair that matches the head element of the vertex pair queue (step S42). Then, the optimized vertex coordinates are set to the remaining starting point side vertex v._sAre set as the coordinates (step S43).
[0092]
By this operation, the vertex pair e, the faces on both sides of the vertex pair e, and the vertex v on the end point side of the vertex pair e_eIs deleted. Then v_sV in the Q matrix_eQ matrix is added (step S44). Next, processing according to the distance calculation method is performed (step S45). That is, in the maximum distance calculation method 1 and the average distance calculation method 1, v_sV in the deleted vertex list_eAdd In the maximum distance calculation method 2 and the average distance calculation method 2, v_sV in the face list_eAfter adding the face list of v_sV in the deleted vertex list_eAdd In the average distance calculation method 3, v_sIncrease the number of deleted vertices by 1. In the average distance calculation method 4, v_sV is the number of faces_eAfter adding the number of faces, v_sIncrease the number of deleted vertices by 1.
[0094]
【The invention's effect】
  Claim1In order to obtain the maximum distance between the face of the original mesh and the vertex of the simplified mesh, the invention described in (1) obtains the maximum value of the distance between the face of the original mesh and the face of the simplified mesh. And the distance between the simplified mesh and the simplified mesh can be determined accurately.
[0095]
  Claim2In order to obtain the average distance between the surface of the original mesh and the vertex of the simplified mesh, the invention described in the above item is obtained by calculating the average value of the distance between the surface of the original mesh and the surface of the simplified mesh. And the distance between the simplified mesh and the simplified mesh can be determined accurately.
[0096]
  Claim3In order to obtain the average distance between the surface of the original mesh and the vertex of the simplified mesh, the invention described in the above item is obtained by calculating the average value of the distance between the surface of the original mesh and the surface of the simplified mesh. And the distance between the simplified mesh and the simplified mesh can be determined accurately.
[0097]
  Claim4In order to obtain the average distance between the surface of the original mesh and the vertex of the simplified mesh, the invention described in the above item is obtained by calculating the average value of the distance between the surface of the original mesh and the surface of the simplified mesh. And the distance between the simplified mesh and the simplified mesh can be determined accurately.
[0098]
  Claim5In order to obtain the average distance between the surface of the original mesh and the vertex of the simplified mesh, the invention described in the above item is obtained by calculating the average value of the distance between the surface of the original mesh and the surface of the simplified mesh. And the distance between the simplified mesh and the simplified mesh can be determined accurately.
[0100]
  Claim6In order to obtain the maximum distance between the face of the original mesh and the vertices of the simplified mesh, the invention described in (1) obtains the maximum value of the distance between the vertex of the original mesh and the face of the simplified mesh. And the distance between the simplified mesh and the simplified mesh can be determined accurately.
[0101]
  Claim7In order to obtain the average distance between the surface of the original mesh and the vertex of the simplified mesh, the invention described in the above item is obtained by calculating the average value of the distance between the surface of the original mesh and the surface of the simplified mesh. And the distance between the simplified mesh and the simplified mesh can be determined accurately.
[0102]
  Claim8In order to obtain the average distance between the surface of the original mesh and the vertex of the simplified mesh, the invention described in the above item is obtained by calculating the average value of the distance between the surface of the original mesh and the surface of the simplified mesh. And the distance between the simplified mesh and the simplified mesh can be determined accurately.
[0103]
  Claim9In order to obtain the average distance between the surface of the original mesh and the vertex of the simplified mesh, the invention described in the above item is obtained by calculating the average value of the distance between the surface of the original mesh and the surface of the simplified mesh. And the distance between the simplified mesh and the simplified mesh can be determined accurately.
[0104]
  Claim10In order to obtain the average distance between the surface of the original mesh and the vertex of the simplified mesh, the invention described in the above item is obtained by calculating the average value of the distance between the surface of the original mesh and the surface of the simplified mesh. And the distance between the simplified mesh and the simplified mesh can be determined accurately.
[0105]
  Claim11The invention described in claim6~10There exists an effect similar to the invention as described in any one of these.
[Brief description of the drawings]
FIG. 1 is a block diagram showing electrical connection of a mesh simplification apparatus according to an embodiment of the present invention.
FIG. 2 is an explanatory diagram for explaining a vertex sharing operation.
FIG. 3 is a flowchart illustrating processing performed by the mesh simplification device.
FIG. 4 is a flowchart of the same.
FIG. 5 is a flowchart of the same.
FIG. 6 is a flowchart of the same.
FIG. 7 is a flowchart of the same.
[Explanation of symbols]
1 Mesh simplification device
3 Storage device

Claims (11)

  In a mesh simplification device that generates a simplified mesh that is simplified by reducing the number of elements of the original mesh, an estimation error that is a degree of simplification when the mesh vertex sharing operation is performed is obtained for each vertex pair. The calculation of the estimation error is performed by storing a surface to be deleted by the vertex sharing operation in a storage device for each vertex remaining by the vertex sharing operation, and storing the coordinates of the vertex remaining by the vertex sharing operation and the memory. The maximum value of the distance to the marked surface is calculated, and the vertices deleted by the vertex sharing operation are stored in the storage device for each vertex and adjacent to the remaining vertices by the vertex sharing operation. The maximum value of the distance between the surface to be stored and the coordinates of the stored vertex is calculated, and the larger of the two maximum values is determined as the maximum distance between the surface of the original mesh and the vertex of the simplified mesh. To do by asking Means for determining whether or not the estimated error exceeds a specified error which is a value specified in advance as a reference value of the estimated error, and based on this determination, the estimated error does not exceed the specified error A mesh simplification apparatus, comprising: vertex sharing operation means for sequentially executing the vertex sharing operation from the vertex pair with the least estimation error.   In a mesh simplification device that generates a simplified mesh that is simplified by reducing the number of elements of the original mesh, an estimation error that is a degree of simplification when the mesh vertex sharing operation is performed is obtained for each vertex pair. In this calculation of the estimation error, vertices to be deleted by the vertex sharing operation are stored in a storage device for each vertex, and the surfaces adjacent to the vertices remaining by the vertex sharing operation and the stored vertices are stored. An estimation means for calculating an average distance between the surface of the original mesh and a vertex of the simplified mesh by calculating an average value of the distance between the coordinates, and the estimation error is a reference value of the estimation error. Determining means for determining whether or not a specified error that is a value specified in advance is exceeded, and based on this determination, the vertex sharing operation in which the estimated error does not exceed the specified error Mesh simplification apparatus characterized by comprising a vertex sharing operation means for executing sequentially from smaller the vertex pairs.   In a mesh simplification device that generates a simplified mesh that is simplified by reducing the number of elements of the original mesh, an estimation error that is a degree of simplification when the mesh vertex sharing operation is performed is obtained for each vertex pair. The calculation of the estimation error is performed by storing a surface to be deleted by the vertex sharing operation in a storage device for each vertex remaining by the vertex sharing operation, and storing the coordinates of the vertex remaining by the vertex sharing operation and the memory. Calculate the average value of the distance to the marked surface, store the vertices deleted by the vertex sharing operation in a storage device for each vertex, and adjoin the remaining vertices by the vertex sharing operation Estimating means for calculating an average distance between the surface of the original mesh and the vertex of the simplified mesh by calculating an average value of the distance between the surface to be stored and the coordinates of the stored vertex; The estimation error A determination unit that determines whether or not a specified error that is a value specified in advance as a reference value for the estimation error is exceeded, and the vertex sharing operation in which the estimated error does not exceed the specified error based on the determination A mesh simplification device comprising: vertex sharing operation means that executes in order from the vertex pair with a small estimation error.   In a mesh simplification device that generates a simplified mesh that is simplified by reducing the number of elements of the original mesh, an estimation error that is a degree of simplification when the mesh vertex sharing operation is performed is obtained for each vertex pair. In this calculation of the estimation error, the sum of the squares of the coordinates of the vertices deleted by the vertex sharing operation and the number of vertices are stored in the storage device as attributes of the vertices remaining by the vertex sharing operation, and the remaining The product of the vector of the plane equation of the surface adjacent to the vertex and the sum of squares is calculated as the cost value of the surface, and the square root of the value obtained by dividing the cost value by the number of vertices is calculated as the original mesh. An estimation unit that is obtained by obtaining an average distance between a surface and a vertex of the simplified mesh, and whether or not the estimation error exceeds a specified error that is a value specified in advance as a reference value of the estimated error And a vertex sharing operation unit that sequentially executes the vertex sharing operation in which the estimation error does not exceed the specified error based on this determination, starting from the vertex pair with the least estimation error. Feature mesh simplification device.   In a mesh simplification device that generates a simplified mesh that is simplified by reducing the number of elements of the original mesh, an estimation error that is a degree of simplification when the mesh vertex sharing operation is performed is obtained for each vertex pair. In the calculation of the estimation error, the number of faces deleted by the vertex sharing operation is stored in a storage device for each vertex remaining in the vertex sharing operation, and the calculation is performed by the QEM (Quadric Error Metrics) method. The vertex pair cost value and the sum of squares of the coordinates of the vertices deleted by the vertex sharing operation and the number of vertices are stored in the storage device as attributes of the vertices remaining by the vertex sharing operation, and the remaining vertices are stored. The sum of the cost values of the surface calculated as the product of the vector of the plane equation of the surface adjacent to and the sum of squares is obtained, and this sum is calculated by the number of surfaces to be deleted and the vertex sharing operation. Deleted Estimating means for obtaining the square root of the value divided by the sum of the points as the average distance between the surface of the original mesh and the vertex of the simplified mesh; and the estimation error is designated in advance as a reference value for the estimation error Determination means for determining whether or not a specified error that is a determined value is exceeded, and based on this determination, the vertex sharing operation in which the estimated error does not exceed the specified error is sequentially performed from the vertex pair with the least estimated error A mesh simplification apparatus comprising: a vertex sharing operation means to be executed.   Degree of simplification when the vertex sharing operation of the mesh is performed in a computer-readable program that causes a computer to execute a process for generating a simplified mesh by reducing the number of elements of the original mesh The estimation error is obtained for each vertex pair, and the calculation of the estimation error is performed by storing a surface to be deleted by the vertex sharing operation in a storage device for each vertex remaining by the vertex sharing operation. Calculating the maximum value of the distance between the coordinates of the vertices remaining in the conversion operation and the stored surface, and storing the vertices deleted by the vertex sharing operation in a storage device for each vertex, The maximum value of the distance between the surface adjacent to the vertex remaining in the vertex sharing operation and the stored coordinates of the vertex is calculated, and the larger of the two maximum values is determined as the surface of the original mesh. Simplification An estimation process performed by obtaining the maximum distance from the top of the cache, a determination process for determining whether the estimation error exceeds a specified error that is a value specified in advance as a reference value of the estimation error, and this determination And a vertex sharing operation process in which the vertex sharing operation in which the estimation error does not exceed the specified error is executed in order from the vertex pair with the least estimation error.   Degree of simplification when the vertex sharing operation of the mesh is performed in a computer-readable program that causes a computer to execute a process for generating a simplified mesh by reducing the number of elements of the original mesh For each vertex pair, the estimation error is calculated by storing the vertices deleted by the vertex sharing operation in a storage device for each vertex and adjacent to the remaining vertices by the vertex sharing operation. An estimation process performed by obtaining an average distance between the surface of the original mesh and the vertex of the simplified mesh by calculating an average value of the distance between the surface to be stored and the coordinates of the stored vertex, A determination process for determining whether or not the estimated error exceeds a specified error that is a value specified in advance as a reference value of the estimated error, and based on this determination, the estimated error is A program characterized by executing the vertex sharing operation process executing said vertex sharing operation does not exceed a constant error from less the apex pairs of the estimated error in the order, to the computer.   Degree of simplification when the vertex sharing operation of the mesh is performed in a computer-readable program that causes a computer to execute a process for generating a simplified mesh by reducing the number of elements of the original mesh The estimation error is obtained for each vertex pair, and the calculation of the estimation error is performed by storing a surface to be deleted by the vertex sharing operation in a storage device for each vertex remaining by the vertex sharing operation. Calculating the average value of the distance between the coordinates of the vertices remaining in the conversion operation and the stored surface, and storing the vertices deleted in the vertex sharing operation in the storage device for each vertex, By calculating the average value of the distance between the surface adjacent to the remaining vertex by the vertex sharing operation and the coordinates of the stored vertex, the surface of the original mesh and the vertex of the simplified mesh are calculated. An estimation process performed by obtaining a uniform distance, a determination process for determining whether or not the estimation error exceeds a specified error that is a value specified in advance as a reference value of the estimation error, and the estimation based on this determination A program for causing a computer to execute a vertex sharing operation process in which the vertex sharing operation in which an error does not exceed the specified error is executed in order from the vertex pair with a small estimation error.   Degree of simplification when the vertex sharing operation of the mesh is performed in a computer-readable program that causes a computer to execute a process for generating a simplified mesh by reducing the number of elements of the original mesh For each vertex pair, the estimation error is calculated by calculating the sum of squares of the coordinates of the vertices to be deleted by the vertex sharing operation and the number of vertices as attributes of the remaining vertices by the vertex sharing operation. Stored in a storage device, calculate the product of the vector of the plane equation coefficients of the surface adjacent to the remaining vertices and the sum of squares as the cost value of the surface, and divide the cost value by the number of vertices An estimation process performed by obtaining a square root of the obtained value as an average distance between the surface of the original mesh and the vertex of the simplified mesh, and the estimation error is preliminarily used as a reference value of the estimation error. A determination process for determining whether or not a specified error that is a specified value is exceeded, and based on this determination, the vertex sharing operation in which the estimated error does not exceed the specified error is performed from the vertex pair with a small estimated error. A program that causes a computer to execute vertex sharing operation processing to be executed in order.   Degree of simplification when the vertex sharing operation of the mesh is performed in a computer-readable program that causes a computer to execute a process for generating a simplified mesh by reducing the number of elements of the original mesh For each vertex pair, the estimation error is calculated by storing the number of faces to be deleted in the vertex sharing operation in a storage device for each vertex remaining in the vertex sharing operation. Stores the vertex pair cost value calculated by the Quadric Error Metrics method, the sum of squares of the coordinates of the vertices deleted by the vertex sharing operation, and the number of vertices as attributes of the remaining vertices by the vertex sharing operation. The sum of the cost values of the surface calculated as a product of the vector of the plane formula of the surface adjacent to the remaining vertex and the sum of squares is stored in the apparatus, and this sum is obtained. The square root of the value divided by the sum of the number of deleted faces and the number of vertices deleted by the vertex sharing operation is obtained as an average distance between the face of the original mesh and the vertices of the simplified mesh. An estimation process; a determination process for determining whether or not the estimation error exceeds a specified error that is a value specified in advance as a reference value of the estimated error; and based on this determination, the estimated error exceeds the specified error. A program that causes a computer to execute a vertex sharing operation process in which the vertex sharing operation that does not exist is sequentially executed from the vertex pair with the least estimation error. A computer-readable storage medium storing the program according to any one of claims 6 to 10 .

Images