Cubical Marching Squares (CMS)
Adaptive Feature Preserving Surface Extraction from Volume Data

Chien-Chang Ho*, Fu-Che Wu, Bing-Yu Chen, Yung-Yu Chuang, and Ming Ouhyoung
National Taiwan University

* I'm back.

Abstract [Chinese version]
In this paper, we present a new method for surface extraction from volume data which preserves sharp features, maintains consistent topology and generates surface adaptively without crack patching. Our approach is based on the marching cubes algorithm, a popular method to convert volumetric data to polygonal meshes. The original marching cubes algorithm suffers from problems of topological inconsistency, cracks in adaptive techniques and inability to preserve sharp features. Most of marching cubes variants only focus on one or some of these problems. Although these techniques could be combined to solve these problems altogether, such a combination might not be straightforward. Moreover, some feature-preserving variants introduce an additional problem, inter-cell dependency. Our method provides a relatively simple and easy-to-implement solution to all these problems by converting 3D marching cubes into 2D cubical marching squares and resolving topology ambiguity with sharp features. We compare our algorithm with other marching cubes variants and demonstrate its effectiveness on various applications.

Chien-Chang Ho, Fu-Che Wu, Bing-Yu Chen, Yung-Yu Chuang and Ming Ouhyoung. Cubical Marching Squares: Adaptive Feature Preserving Surface Extraction from Volume Data, In Computer Graphics Forum (Proceedings of EUROGRAPHICS 2005), volume 24, number 3, pp 537-545, Dublin, Ireland, August 2005.


Eurographics 2005 paper (2.3MB PDF)

Video for the conference

360x240 wmv (8.7MB) 720x480 wmv (25.9MB)


Simulation results.

CSG/LOD operations using CMS.

Remesh operation using CMS.

Additional Infomation

3D Configurations generated by CMS.

CMS implementation using HLSL.

Screenshots of the CMS program.

Seeing CMS in action

Click images to download videos

The following videos are compressed using Windows Media Encoder.
You may need WMP10 or VLC to playback these videos.

Video: A static scene (2,537KB)

Video: A time verying scene (3,318KB)

Video: Cell Independency - EG (4,553KB)

Video: Cell Independency - fandisk (7,568KB)

Video: illustration of 3D to 2D (1,006KB)

Video: Level of detail (1,021KB)

Video: 3D configurations (11,763KB)

Video: New configurations (1,927KB)