UNISYS TECHNOLOGY REVIEW

第 129 号，SEP. 2016

ポリゴンモデルの精度保証簡略化
Accuracy Guaranteed Algorithm for Polygonal Mesh Simpliﬁcation

田 中 修 平要 約

ポリゴンモデルの簡略化とは，縮約を繰り返してポリゴンモデルのポリゴン数を削減する処理のことである．簡略化による元形状からの離れの問題に対応する為，精度保証簡略化の手法を開発した．精度保証とは「元形状から簡略化後形状への距離の離れが指示した範囲内に収まること」である．精度保証を実現するために，縮約前後の紐付け処理や位相不正の感知，縮約対象リスト管理を採り入れた．その結果，本手法は従来のものよりも優れた精度を実現した．
Abstract Polygonal mesh simplification is a process to reduce the triangles of mesh. To solve the problemof distance between the original and the simplified mesh, we have developed geometric accuracy guaranteed simplification. Guaranteeing geometric accuracy means to keep the maximal distance between original
mesh vertices and simplified mesh in the user defined tolerance. In order to realize the geometric accuracy, we introduced a checklist which manages the target vertices to check. As a result, we achieved
better geometric accuracy than a conventional method.

1.

はじめに
［1］

ポリゴンモデル は，ポリゴンを敷き詰めて物体の表面形状を表現したデータのことである．
ポリゴンは，三角形や四角形など多角形のことである．ポリゴンを構成する面をフェイス，辺をエッジと呼ぶ．ポリゴンモデルの簡略化とは，ポリゴンモデル全体の形をできるだけ変えずに，ポリゴンモデルのポリゴン数（以降フェイス数）を減らすことである．
簡略化後のポリゴンモデルは，簡略化前のポリゴンモデルよりも少ないフェイス数で形を表現する為，ポリゴンモデルに離れが生じる．この離れを少なくすることが簡略化の処理を実行する上での課題である．この課題はポリゴンモデルの利用用途に応じて重要性が異なる．例えば，CG（Computer Graphics）や AR（Augmented Reality）ではテクスチャを貼ることによってある程度離れを目立たなくすることができる為，大きな問題とはならない．しかし，厳密な精度が求められる製造業では，簡略化前後の距離の離れを許容値以内にする必要がある．
課題への対応として，特に製造業分野での適用を目指し，処理前後での差異を許容値以内に抑える簡略化（精度保証簡略化）を開発した．本稿では，そのアルゴリズムと工夫した箇所および課題について述べる．2 章と 3 章で一般的なポリゴンモデルの簡略化と課題，4 章で精度保証簡略化の実現方法，5 章でその具体策と課題，6 章で評価結果を述べる．
2.

簡略化の仕組み
簡略化によってフェイス数を減らしていく仕組みは，三角形の辺（エッジ）の縮約（2 頂点を 1 頂点に置き換える処理）を繰り返すことによって実現している．エッジを一つ縮約すると，（47）1

2（48）

フェイス数を 2，エッジ数を 3，頂点数を 1 減らすことができる．図 1 に示した具体例では，エッジ ab を縮約すると三角形（以降△）abc と△ abd がなくなり，フェイス数は 10 から 8 となる．
頂点 a と頂点 b が頂点 a’ となり，頂点数は 10 から 9 となる．エッジ ad，エッジ bd がエッジ a’dに，エッジ ac，エッジ bc がエッジ a’c になり，エッジ数が 19 から 16 となる．エッジを縮約して，一つにする頂点の座標値を決める方法として，一般的に Quadric Error Metrics（以降［2］QEM） がよく使われている．今回開発した精度保証簡略化でも QEM の考え方を採用している．

図13.

エッジ縮約のイメージ図

ポリゴンモデル簡略化の課題
ポリゴンモデルの簡略化を行うと，少ないポリゴンで同様の形を表す為，簡略化前後のポリゴンモデルに距離の離れが生じる．本章で詳しく述べる．
簡略化の QEM は縮約するエッジの両端頂点周りの 1 近傍フェイス群（図 2）の無限平面との距離の二乗和が最小になる位置を計算して，縮約後の頂点の位置にする．距離の二乗和最小値を QEM 値とする．図 3 に示すように，エッジ ab を縮約すると，QEM で求まる頂点は a’となる．縮約前のエッジの両端点 ab と縮約後のエッジとの離れは図 3 の右側において赤矢印で示した箇所となる．

図2

1 近傍フェイス群のイメージ図（表面形状を上から見たイメージ）

ポリゴンモデルの精度保証簡略化

左：縮約前

中：QEM の頂点例

（49）3

右：縮約後

図 3 エッジ ab の縮約

QEM 値に応じた評価値を計算して頂点ごとに保持し，全エッジについて，両端点が保持している評価値から縮約に要するコストという数値を計算し，コストの小さなものから縮約の対象エッジとなるように縮約対象エッジのリストを作成した．平らな部分では，無限平面との離れが少ないので，コストが小さくなり，曲がっている部分ではコストが大きくなる．コストの小さなエッジから縮約することは，平らな部分から縮約することを意味している．
このリストの順番に従って，エッジを縮約していく為，元の形状からの離れを少なくすることはできる．しかしながら，QEM から決定された頂点をそのまま使っても元形状からの離れを一定の閾値以内にすることはできない．具体的に QEM で簡略化を行った例を図 4 に示す．
図 4 の右側の QEM の手法で簡略化したポリゴンモデルを見ると，左側の簡略化前のポリゴンモデルから離れがある為，角張っている．

左：簡略化前右：一般的な QEM でフェイス数を 1/100 にした結果

図4QEM での簡略化例

4. 精度保証簡略化の実現方法
元形状からの離れを許容値以内にするということを次のように定義する．
『簡略化前のすべての頂点（以降オリジナル頂点）から，簡略化後のポリゴンモデルに最近点を求め，その値が許容値以内であること』
この定義を満たす為，エッジ縮約時に縮約後のポリゴンモデルがオリジナル頂点から離れないことを確認して処理を進める．縮約によってなくなるオリジナル頂点と，縮約後の 1 近傍フェイス群中の最近フェイスとの関連付けを行う．この関連付けの処理を紐付け処理と呼ぶ．簡略4（50）化が進んでフェイスの形が変わる時に，そのフェイスに紐付いているオリジナル頂点を離れの距離検査に使用する．エッジを縮約するたびに，全てのオリジナル頂点から縮約後のポリゴンモデルへの距離を計算すると膨大な計算時間がかかる．あるエッジを縮約して形が変わるフェイスは，1 近傍フェイス群となる為，すべてのオリジナル頂点を離れ検査の対象にしなくとも，1 近傍フェイス群に紐付いているオリジナル頂点のみを距離検査の対象とすればよい．
簡略化が進むにつれて，一つのフェイスに対して紐付く頂点は増加するため，距離検査に要する処理時間は増加していく．
5.

考慮した点と課題
精度保証簡略化で取り入れた考慮と課題に関して述べる．
5. 1 不正形状を作らない工夫
対象エッジの縮約により，裏返りフェイスや，面積が 0 に近い微小フェイス，極端に扁平なフェイスといった不正形状が作られるという課題がある．不正な形状が残っていると簡略化後の別の編集作業でエラーが発生する原因となる可能性がある為，こうした不正形状については，精度保証に限らず，簡略化する際に考慮しなければならない．対象エッジの両端点のそれぞれの 1 近傍で重複する頂点が 3 点以上存在する場合には，位相不正として検査不合格とした．
図 5 に示すように，共有頂点が 3 点以上存在するエッジ ab を縮約すると，△ a’（a）dc と△ a’（b）dc が重なる位相不正の状態となる．

図 5 エッジを縮約して不正な形状を作る場合の例

1 近傍フェイス群について，縮約前のフェイス法線と縮約後の表向き法線ベクトルのなす角度を調べ，閾値以上の角度で折れる場合，裏返ったとみなし，検査不合格とした．検査する対象フェイスは，図 6 に示すように，△ abc，△ abd は縮約してなくなる為，△ efa と△ efa’ といった組み合わせで検査する．

図 6 裏返り検査を行う対象フェイスのイメージ図

ポリゴンモデルの精度保証簡略化（51）5

実際の裏返りは，図 7 に示すようなケースで発生する．図 7 ではエッジ ab を縮約した際に，頂点 a’ の求まる位置によって裏返りが発生する．図 7 の中央の上側の図で示すように，頂点 aの近くに頂点 a’ が求まった場合には，裏返りは発生しない．しかし，頂点 b の近くに頂点 a’が求まった，中央の下側の図のような場合，△ a’dc のエッジ a’d が頂点 c を追い越すような動きになる．このため法線の向きが逆になり，裏返りとなる．また，縮約後の面積が 0 に近い場合も，簡略化後のポリゴンモデルに更に編集処理を行う場合にエラーが発生する可能性がある為，検査不合格とした．

図75. 2

裏返りの例

削減率をあげる工夫

不正形状の検査や離れの検査において，不合格であったエッジでも，周辺の他のエッジが縮約されると，1 近傍フェイスの形が変わり，縮約できる可能性がある．この為，縮約できなかったエッジはコストを大きくして，縮約対象エッジリストの後ろに入れなおし，再度縮約対象となるようにした．この工夫により，削減率を上げることはできるが，縮約対象エッジリストが減りにくくなる為，簡略化処理全体が終了するまでの時間は増加する．データ量を減らすことが重視されるならば，この工夫には意味がある．しかし，効率が優先されるような用途では，この工夫を外すことで簡略化処理時間を削減することができる．簡略化処理は，この縮約対象エッジリストの全てのエッジが検査 NG となる状況が連続した場合には強制的に終了するようにした．
5. 3 貫通穴や外周が維持されない問題とその対応
1 近傍フェイス群と元形状のオリジナル頂点との離れ検査を行い，離れが許容値以内になるように縮約を進めるが，この検査方法では，オリジナル頂点と簡略化後のフェイスとの離れは許容値以内となるが，穴や外周の形が変わるという問題が発生した．
この問題の原因は，図 8 を例とすると，エッジ ab を縮約した場合，縮約後の 1 近傍フェイス群と頂点 a，頂点 b の各頂点との距離は許容値以内である為，エッジ ab は検査合格となり，縮約されてしまう．しかし，頂点 a，頂点 b と簡略化後の形状の外周エッジの距離を計算すると，許容値よりも離れてしまうということであった．
縮約により作られるエッジが元のポリゴンモデルと離れないか検査する為，次のような離れの検査を新たに追加した．

6（52）

図 8 穴や外周が元形状から離れる問題のイメージ縮約してできる頂点に接続するエッジの中点と，縮約前の 1 近傍フェイス群との離れが許容値以内となるかどうかを検査する．全ての中点において検査合格であれば，対象エッジを縮約しても外周や穴は維持される．検査不合格になる中点があれば，対象エッジは縮約しない．図9 の例では，中点 a，中点 g が元形状の外周から離れてしまっている為，検査不合格となりエッジ v1v2 は縮約できない．

図9

穴や外周が元形状から離れてしまう問題への対応

この距離検査を追加することにより，外周や貫通穴，シャープエッジ箇所での元形状からの離れが許容値以内となった．図 10 の中央の QEM を用いた手法では，穴部分のシャープエッジの形状が維持できないことがわかる．比較して右の提案手法の結果では穴部分のシャープエッジ形状が維持されていることがわかる．

左：オリジナル

図 10

中：QEM の結果

右：提案手法穴部分のシャープエッジの形状

ポリゴンモデルの精度保証簡略化

（53）7

6. 評価
ポリゴンモデルの簡略化の精度と効率について，他社市販ソフトウェア，QEM を使った手法，提案手法を比較評価した．結果は図 11 および表 1 のとおりである．
■実行条件
元データのフェイス数：304,134
条件：離れ許容値 0.01
■結果

左：市販ソフトウェア

中：QEM を使った手法

右：提案手法図 11 簡略化実行後のイメージ

表 1 比較結果

フェイス数

処理時間

表面形状

最大離れ市販ソフトウェア

ソフトウェア58,7713秒

不正3.25QEM（オープンソース）

26,6923秒

不正0.05

提案手法

26,69215 秒

正常0.01QEM の実行は，離れを指定しての実行ではなく，本手法の結果と同じフェイス数となるよ
うにフェイス数を目標に実行した結果，どれだけ離れが出るのかという観点での比較として実施した．結果，フェイス数，最大離れの両比較項目において，提案手法は市販ソフトウェアに対して優れた結果を示している．処理時間では，市販ソフトウェアの 5 倍の時間がかかっており，提案手法の課題となっている．
7.

おわりにデータ量は減らしたいが，形状の崩れはできる限り抑えたいという要望に対して，本手法は有用な解決策を提供できるものである．特に精度が厳密に求められることが多い製造業分野において顕著な効果が期待できる．まだ処理時間，フェイスの歪みの抑止，更なる削減率の向上等を課題として，今後継続して改善していく．
─────────
参考文献 ［ 1 ］ 谷本茂樹，「3D プリンタ造形に必要なポリゴン編集機能」，ユニシス技報，日本ユニ8（54）

シス，Vol. 36 No. 2，通巻 129 号，pp51-68，2016 年 9 月．
［ 2 ］ Michael Garland and Paul S. Heckbert, “Surface Simpliﬁcation Using Quadric Error Metrics”, SIGGRAPH 97

執筆者紹介

田 中 修 平（Shuhei Tanaka）
2002 年日本ユニシス・エクセリューションズ（株）
入社．2012 年
より CAD・CAM 分野に取り組み，同年より理化学研究所計測情報処理研究チーム客員研究員．POLYGON EDITOR，POLYGONALmeister，CADmeister の開発に従事．