Mathematical Model of Multi-Type Marching Squares and Algorithm for Their Implementation

Abstract

The classical Marching Squares algorithm is limited to binary vertex states of a cell and does not allow direct processing of heterogeneous voxel data with multiple material types. This paper proposes an extension of this approach – the Multi-Type Marching Squares (MTMS) model, which expands the topological configuration space of a cell from the classical 16 to 512 states by supporting four material types. To map global material identifiers to the local space of the configuration table, a normalization method based on modular arithmetic is developed. To resolve diagonal ambiguity, a binary flag is introduced, computed by comparing weighted density sums on opposite cell diagonals. It is proved that the proposed encoding via case index ensures a one-to-one correspondence between cell states and configuration table entries. The developed model enables extraction of polygonal boundaries in a single pass over the grid without global synchronization, which is critical for parallel GPU implementations.