著者

藤本 敬介 守屋 俊夫 中山 泰一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.49, no.2, pp.1031-1040, 2008-02-15

参考文献数

10

被引用文献数

1

---

陰関数表現から三角形メッシュを生成する手法としてMarching Cubes 法(MC 法)がよく知られているが,本論文ではその改良手法について述べる.従来のMC 法は,等間隔にグリッドを設定し,格子点に対して境界面との内外判定を行うことでメッシュを生成するため,(1) 格子に対して細い物体が存在するときにそれが欠損してしまう可能性がある,(2) 物体の鋭角部が鈍った形状に変換されてしまう,といった問題が発生していた.本論文では,これらの問題に対し各格子点の位置を物体の形状に対して適応的に移動させ各格子の形状を変形させるDeformed Marching Cubes 法(DMC法)を提案する.DMC 法では,各格子点の周辺を探索して重心点を求め,また格子と等値面の関係から鋭角の頂点座標を求め,それぞれ求めた座標に最も近い格子点を移動させる.これにより,少なくとも格子内に物体が1 つしか存在しない場合においては,(1) 探索精度以上の細い物体の非欠損性の保証,および(2) 鋭角部の再現,を同時に実現した.実験により,MC 法における格子の1 辺の長さに対し1/5 以上の幅を持つ物体の非欠損性を保証する場合でも,従来に対し約25%の計算時間増だけで処理されることを確認した.We describe an algorithm that improves the ability of detailed expression of the Marching-Cubes (MC) method. The MC method is a technique for generating triangular meshes from implicit function. It sets the uniform grid, and generates mesh with the judgment whether the lattice point is on the inside to the boundary. Therefore, it has two problems. First, there is a possibility that the thin part of the object is lost. Second, the sharp part is converted into the smooth shape. In this paper we present a Deformed-Marching-Cubes (DMC) method that changes the shape of the grid form by moving lattice points. The steps of the DMC method are: 1) detecting a thin part by searching for surroundings of each lattice point, 2) calculating coordinates of the sharp part, 3) moving a lattice point that is nearest from each calculated point. As a result, when only one object exists for the grid interval, this method realized guaranteeing the non-loss of an object that is bigger than the search accuracy, and reproducting the sharp part. Consequently, we proved that the method guarantee non-loss of the object of the width of 1/5 compared with the grid size only by the overhead of only about 25%.