A Data Structure for Manipulating Meshes with Regular Regions

Le-Jeng Shiue, Jorg Peters, "A Data Structure for Manipulating Meshes with Regular Regions", submitted to ACM Siggraph 2004.

http://www.cise.ufl.edu/~sle-jeng/Research/research.html

概要

自動的に生成されたり、レーザースキャンされたサーフェスは通常一様なパターンを持つ大きなクラスタが現れます。本論文では、クラスタ内の一様性の利点を利用かつ扱える ２レベルのデータ構造である Qreg を提案します。上部のレベルでは、 Qreg はエッジベースのデータ構造であるが T-コーナー(T-corners)を許すものに似たクラスタへのアクセスを提供します。各クラスタでは、スパイラル列挙法(spiral enumeration scheme)と修正可能選択ステンシル(modifiable selection stencil)が効率的な近傍アクセス、マルチサイドクラスタ(multi-sided clusters)、それらの結合(joining)と分割(splitting)、プライマル・デュアルおよび三重根(sqrt(3))構造、および適応的リファイメントをサポートします。

Automatically generated or laser-scanned surfaces often exhibit large clusters with a uniform pattern. This paper proposes a two-level data structure, Qreg, that supports and takes advantage of the regularity within clusters. At the upper level, Qreg provides access to the clusters similar to edge-based data structures but allowing for T-corners. Within each cluster, a spiral enumeration scheme and a modifiable selection stencil support efficient neighbor access, multi-sided clusters, their joining or splitting, primal, dual and sqrt(3) structures and adaptive refinement.