講演抄録/キーワード |
講演名 |
2014-03-10 16:05
対角変形を用いた三角形メッシュのReebグラフ計算法 ○森口昌樹・今井桂子(中大) COMP2013-72 |
抄録 |
(和) |
Reebグラフとは,三角形メッシュ上に定義された関数のレベルセット(等値線や等高線とも呼ばれる)の位相の変化を表したもので,$3$次元形状の解析に広く応用されている.本研究では,2多様体と同相な三角形メッシュに対する,対角変形を用いたReebグラフの計算法を提案する.この手法は,ドロネー対角変形を用いたドロネー三角形分割の計算法と同様に,局所的な目的関数を改善させる対角変形のみを適用してReebグラフを計算する.頂点数$n$,辺数$m$の三角形メッシュのReebグラフを計算するとき,最短の対角変形列では$mathrm{O}(m log n)$回の対角変形が行われる.また,最長の対角変形列では$mathrm{O}(m n)$回の対角変形が行われるが,提案するアルゴリズムは実用的には高速で実装も簡単である. |
(英) |
The Reeb graph of a function defined over a triangular mesh encodes the topological evolution of the level-sets of the function. This high-level shape descriptor is widely used in computer graphics. In this paper, we present a flip-based algorithm for computing Reeb graphs on triangular meshes. Similar to Delaunay flips for computing Delaunay triangulations, the flips for computing Reeb graphs are driven by some local objective function. The shortest flip sequence that computes the Reeb graph has $mathrm{O}(m log n)$ flips, where $n$ is the number of vertices in the input mesh and $m$ is the number of edges. Though the longest flip sequence has $mathrm{O}(m n)$ flips, our algorithm runs fast in practice and easy to implement. |
キーワード |
(和) |
Reebグラフ / 対角変形 / 閉曲面 / 三角形分割 / 擬三角形分割 / / / |
(英) |
Reeb graphs / diagonal flips / closed surfaces / triangulations / pseudo-triangulations / / / |
文献情報 |
信学技報, vol. 113, no. 488, COMP2013-72, pp. 83-89, 2014年3月. |
資料番号 |
COMP2013-72 |
発行日 |
2014-03-03 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-72 |