TY - JOUR
T1 - A combinatorial marching hypercubes algorithm
AU - Castelo, Antonio
AU - Moutinho Bueno, Lucas
AU - Gameiro, Marcio
N1 - Funding Information:
All authors thank the financial support from the São Paulo Research Foundation (FAPESP), Brazil grants 2013/07375-0 and 2019/07316-0 . A. Castelo also thanks the financial support from the National Council for Scientific and Technological Development (CNPq), Brazil grant 307483/2017-7 . L. M. Bueno also thanks the financial support from the São Paulo Research Foundation (FAPESP), Brazil grant 2017/25631-4 . M. Gameiro was partially supported by the National Science Foundation, USA under awards DMS-1839294 and HDR TRIPODS, USA award CCF-1934924 , DARPA, USA contract HR0011-16-2-0033 , National Institutes of Health, USA award R01 GM126555 , by FAPESP grant 2019/06249-7 , and by CNPq grant 309073/2019-7 , Brazil.
Publisher Copyright:
© 2021 Elsevier Ltd
PY - 2022/2
Y1 - 2022/2
N2 - 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.
AB - 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.
KW - Combinatorial skeleton
KW - High-dimensional manifolds
KW - Manifold approximation
KW - Marching hypercubes
UR - http://www.scopus.com/inward/record.url?scp=85120857441&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85120857441&partnerID=8YFLogxK
U2 - 10.1016/j.cag.2021.10.023
DO - 10.1016/j.cag.2021.10.023
M3 - Article
AN - SCOPUS:85120857441
VL - 102
SP - 67
EP - 77
JO - Computers and Graphics
JF - Computers and Graphics
SN - 0097-8493
ER -