A combinatorial marching hypercubes algorithm

Antonio Castelo, Lucas Moutinho Bueno, Marcio Gameiro

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We propose a Combinatorial Marching Hypercubes (CMH) algorithm to approximate manifolds of any dimension by a collection of cells. Our algorithm is a generalization of the renowned Marching Cubes Algorithm, which approximates surfaces by a set of polygons. The size and complexity of the manifolds, as well as their approximations, grow exponentially with their dimensions. In order to make our algorithm feasible in higher dimensions, we use a set of efficient techniques that rely on topology and enumeration concepts, which do not require the use of lookup tables. We also propose an extension to CMH, the Combinatorial Continuation Hypercubes (CCH), that uses a continuation method to avoid processing empty spaces. We implemented and compared our algorithm with a similar algorithm based on hypertetrahedra. We present empirical results for manifolds of up to five dimensions.

Original languageEnglish (US)
Pages (from-to)67-77
Number of pages11
JournalComputers and Graphics (Pergamon)
Volume102
DOIs
StatePublished - Feb 2022
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Engineering(all)
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Graphics and Computer-Aided Design

Keywords

  • Combinatorial skeleton
  • High-dimensional manifolds
  • Manifold approximation
  • Marching hypercubes

Fingerprint

Dive into the research topics of 'A combinatorial marching hypercubes algorithm'. Together they form a unique fingerprint.

Cite this