Structured Bitmap-to-Mesh Triangulation for Geometry-Aware Discretization of Image-Derived Domains

Wei Feng; Haiyong Zheng

cs.CGFeb 23, 2026

Structured Bitmap-to-Mesh Triangulation for Geometry-Aware Discretization of Image-Derived Domains

Authors: Wei Feng, Haiyong Zheng

Abstract

We propose a template-driven triangulation framework that embeds raster- or segmentation-derived boundaries into a regular triangular grid for stable PDE discretization on image-derived domains. Unlike constrained Delaunay triangulation (CDT), which may trigger global connectivity updates, our method retriangulates only triangles intersected by the boundary, preserves the base mesh, and supports synchronization-free parallel execution. To ensure determinism and scalability, we classify all local boundary-intersection configurations up to discrete equivalence and triangle symmetries, yielding a finite symbolic lookup table that maps each case to a conflict-free retriangulation template. We prove that the resulting mesh is closed, has bounded angles, and is compatible with cotangent-based discretizations and standard finite element methods. Experiments on elliptic and parabolic PDEs, signal interpolation, and structural metrics show fewer sliver elements, more regular triangles, and improved geometric fidelity near complex boundaries. The framework is well suited for real-time geometric analysis and physically based simulation over image-derived domains.

Figures & tables

Panel of Figure 1 — Figure 1: Overview of the SBMT execution pipeline. The process begins with a regular triangular grid, followed by boundary embedding, threshold-based preprocessing, discrete classification of boundary–triangle intersections, and local retriangulation via symbolic lookup templates. Each stage is deterministic, parallelizable, and free of global mesh coupling.

Figure 2: Structured equilateral mesh over a bitmap-derived domain. Green squares indicate unit pixels; blue lines denote the triangular grid; red polylines represent boundary segments intersecting the mesh. This configuration satisfies the geometric protocol of Section 3.2 and supports lookup-based local retriangulation while preserving topological and numerical consistency. The grid shown uses parameters $a=0.2$ , $b=0.08$ , $c=0$ (as defined in Section 3.3.4 ), with triangle edge length $\sqrt{0.7}$ .

Panel of Figure 3 — Figure 3: Exhaustive enumeration of canonical intersection patterns induced by a single boundary segment intersecting a triangular cell. Each configuration is treated as an atomic unit, abstracted independently of any additional segments that may also intersect the same cell. Subfigures are labeled by the number of intersection points (e.g., 1 intersection , 2 intersections , etc.), omitting edge identities. These localized, template-based configurations form the basis of our lookup-driven remeshing framework, enabling robust and scalable subdivision of structured triangular domains with embedded polygonal boundaries.

Panel of Figure 4 — Figure 4: Geometric classification of all local configurations in which a single boundary segment intersects a triangle cell. The four cases include vertex intersection (a), edge piercing (b), single-edge contact (c), and edge-aligned overlap (d). This classification forms the base of the local retriangulation lookup table.

Panel of Figure 5 — Figure 5: Geometric configurations of type (1,1) , where two boundary segments intersect a triangle at one point each. These cases are grouped by intersection count rather than edge location, forming a unified retriangulation pattern applicable to all edge combinations.

\pi_{K,\tau}(\bar{A},\bar{B},\bar{C})=(A,B,C),\qquad\pi_{K,\tau}(\bar{q}_{j})=q_{j},\qquad\pi_{K,\tau}(\bar{p}_{i})=p_{i},

Algorithm 2 Template-driven retriangulation of a single triangle

Panel of Figure 6 — Figure 6: Structure-aware interpolation on an SBMT mesh via a holomorphic chart. (a) Original bitmap MR image. (b) Interpolation on a globally uniform equilateral mesh that ignores anatomical boundaries. (c) Gu–Yau holomorphic chart computed on the SBMT mesh: the harmonic potentials $(u,v)$ induce two orthogonal foliations, where red curves visualize equipotential lines ( $u=\mathrm{const}$ ) and blue curves visualize trajectory/field lines ( $v=\mathrm{const}$ , integral curves aligned with $\nabla u$ ). This panel visualizes the PDE-derived coordinate field (analogous to a 2D electrostatic potential/stream function), not a mesh-quality plot; curve crowding reflects conformal scaling in thin or high-curvature regions rather than remeshing artifacts. All meshes use a fixed edge length $e=\sqrt{0.7}$ for a fair comparison. Rendering uses OpenGL; brightness variations are due to lighting.

Panel of Figure 7 — Figure 7: Illustration of the threshold- $b$ retriangulation rule. (a) Two triangles share an edge $(A,B)$ . (b) A boundary point $p_{j}$ lies within distance $b$ of the shared edge and triggers edge deletion. (c) The local region is retriangulated using $p_{j}$ as an internal vertex, resulting in four sub-triangles.

Panel of Figure 8 — Figure 8: Execution dependency of the three preprocessing steps in Proposition 3.9 .

Panel of Figure 9 — Figure 9: Structure-aware processing of a stomach cross-section. (a) Original binary image. (b) Interpolation on a uniform mesh without respecting anatomical boundaries. (c) Holomorphic chart on the SBMT mesh (Gu–Yau pipeline; Section 3.4 ): we solve a discrete Poisson/Hodge system to obtain a holomorphic $1$ -form and integrate it to produce harmonic conjugate potentials $(u,v)$ . Red curves show equipotential lines ( $u=\mathrm{const}$ ) and blue curves show trajectory/field lines ( $v=\mathrm{const}$ ), analogous to a 2D electrostatic potential and its orthogonal field lines. This visualization reflects the conformal coordinate field; apparent bending/crowding near the distal thin regions is an expected conformal scale effect under the chosen boundary conditions, and should not be interpreted as remeshing error. Mesh edges are omitted for clarity.

Panel of Figure 10 — Figure 10: SBMT lookup table coverage on a complex anatomical boundary. Dominant cases such as single-edge and $(1,1)$ types are highlighted, confirming the sufficiency of lookup table coverage in practice. The clean triangulation and absence of conflicts illustrate the spatial coherence of the local retriangulation strategy.

Panel of Figure 11 — Figure 11: Structure-aware representation of a synthetic star-shaped domain. (a) Original binary image with sharp nonconvex boundaries. (b) Bilinear interpolation on a uniform triangular mesh, which smears the star tips and narrow lobes. (c) Holomorphic $1$ -form foliation computed on the SBMT mesh using the Gu–Yau algorithm [ 13 ] : the conjugate harmonic potentials $(u,v)$ define an orthogonal chart whose level sets (blue curves) align with the geometry and serve as structure-aware coordinates for subsequent reconstruction (Section 3.4 ).

Panel of Figure 12 — Figure 12: Structure-aware remeshing of a synthetic star-shaped domain. (a) Global view of the remeshed binary image. The red rectangle marks a high-curvature region near a sharp inward corner. (b) Zoomed-in visualization of the selected region. Triangle elements remain well-shaped and align precisely with embedded boundaries. Color coding indicates the local intersection type of each triangle, consistent with the legend in Figure 10 . Black squares represent the underlying pixel grid, each of unit size and centered at the pixel coordinate. Blue lines indicate the initial regular triangular mesh, and red polylines denote embedded boundary segments. Only $(1,1)$ , $(2,2)$ , and single-edge intersection types appear in this zoomed region; rarer types did not occur here.

Panel of Figure 13 — Figure 13: Smoothed histograms of minimum triangle angles for the stomach and star meshes. Bin centers are spaced at $2^{\circ}$ intervals, and the vertical axis uses a logarithmic scale to reveal the low-probability tail. In both cases, the distributions are sharply peaked near $60^{\circ}$ , reflecting the dominance of equilateral elements. The low-angle tail remains well above the sliver threshold, with observed minima of $11.4^{\circ}$ for the stomach and $10.32^{\circ}$ for the star, in agreement with the analytic lower bound in Theorem 3.6 .

Domain	Min angle	Min area	Slivers	Equilateral ratio
Stomach	$11.4^{\circ}$	$0.0134$	$0$	$183{,}063/188{,}239\approx 97.25\%$
Star	$10.32^{\circ}$	$0.0133$	$0$	$66{,}540/70{,}292\approx 94.66\%$

Table 1: Geometric quality of SBMT meshes on two domains. Slivers are triangles with minimum angle

<5^{\circ}

. Equilateral ratio is the fraction of triangles classified as equilateral by the edge-length test.

	Stomach			Star
Config	Min angle	Min area	Slivers	Min angle	Min area	Slivers
E1 – Full	11.42	0.01338	0	10.32	0.0133	0
E2 – No snapping	2.52	0.00636	1	2.19	0.00104	4
E3 – No repulsion	0.0272	$2\times 10^{-8}$	215	0.05	$1\times 10^{-7}$	190
E4 – No deletion	0.0331	$4\times 10^{-5}$	87	0.16	$1.6\times 10^{-4}$	50
E5 – All off	0.0199	$2\times 10^{-8}$	609	0.001	$1\times 10^{-7}$	508

Table 2: Ablation of geometric preprocessing rules. E1 (full pipeline) consistently yields the highest mesh quality.

Domain	Method	Min Angle	Min Area	Area Var.	Count	Slivers	Equilateral
Star	SBMT	$10.32^{\circ}$	$0.0133$	$0.000645$	$70{,}292$	$0$	$66{,}540$
	Triangle	$20.07^{\circ}$	$0.0615$	$0.00084$	$107{,}097$	$0$	$3{,}438$
	Gmsh	$31.29^{\circ}$	$0.0590$	$0.00153$	$82{,}315$	$0$	$0$
Droplet	SBMT	$11.63^{\circ}$	$0.0131$	$0.00039$	$84{,}271$	$0$	$81{,}553$
	Triangle	$20.12^{\circ}$	$0.0583$	$0.00084$	$129{,}581$	$0$	$4{,}249$
	Gmsh	$32.08^{\circ}$	$0.0621$	$0.00147$	$96{,}613$	$0$	$0$

Table 3: Comparison between SBMT, Triangle (CDT), and Gmsh on three domains. Sliver: triangle with minimum angle

<5^{\circ}

. Equilateral: triangles classified as equilateral by the edge-length test.

Domain	Method	$\mathbf{AR_{\mathrm{med}}}$	$\mathbf{AR_{95}}$	$\mathbf{AR_{\mathrm{max}}}$
Star	SBMT	$1.1547$	$1.2434$	$7.7902$
	Triangle	$1.6449$	$2.4672$	$5.4555$
	Gmsh	$1.2586$	$1.4980$	$1.8879$
Droplet	SBMT	$1.1547$	$1.1547$	$7.7916$
	Triangle	$1.6469$	$2.4693$	$5.4595$
	Gmsh	$1.2570$	$1.4947$	$1.8802$

Table 4: Aspect-ratio statistics (

\mathrm{AR}=\text{longest edge}/\text{shortest altitude}

) for three domains and three meshing methods.

\mathrm{AR}_{\mathrm{med}}

: median;

\mathrm{AR}_{95}

: 95th percentile;

\mathrm{AR}_{\mathrm{max}}

: maximum.

Panel of Figure 14 — Figure 14: Holomorphic 1-form reconstructions on SBMT meshes for the three benchmark domains. The embedded boundary curves are faithfully aligned with the triangulated grid, and the induced scalar fields remain smooth up to the boundary, illustrating the suitability of SBMT for PDE-based image analysis.

Figure 15: Local triangulation near high-curvature boundary tips on two canonical shapes. Top row: star-shaped domain; bottom row: Y-shaped domain. In each row, the left panel shows the binary boundary (black) and a region of interest (blue box). The three panels to the right display zoomed-in triangulations produced by SBMT, Triangle (constrained Delaunay), and Gmsh, respectively, with the raster boundary overlaid in red. SBMT preserves an almost equilateral pattern up to the boundary band, while Triangle and Gmsh introduce more irregular elements in order to satisfy their global angle and size objectives.

Panel of Figure 16 — Figure 16: Smoothed histograms of minimum triangle angles for the three benchmark domains: (a) star, (b) droplet, and (c) Y-shaped region. In each panel, the horizontal axis is the minimum interior angle (degrees) and the vertical axis is the triangle count (log scale). Curves correspond to SBMT, Triangle, and Gmsh, as indicated in the legend. SBMT exhibits a sharp peak near the equilateral angle ( $60^{\circ}$ ), reflecting its nearly uniform grid, whereas Triangle and Gmsh produce broader distributions with larger guaranteed minima but more variation across the mesh.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 17 — Figure 17: Worst-case angle configurations used to derive lower bounds for triangle angles. (a) Angle $\theta_{1}=\angle QAP_{2}$ is bounded below by $\arctan\left(\frac{b}{e+a-\sqrt{a^{2}-b^{2}}}\right)$ , where $b$ is the edge threshold. (b) Angle $\theta_{2}=\angle Q_{1}AB$ is bounded below by $\arctan\left(\frac{c}{e+a}\right)$ , where $c$ is the projection threshold from a vertex to a boundary segment.

Panel of Figure 18 — Figure 18: A worst-case triangle $\triangle AQP_{2}$ is formed when vertex $A$ is projected orthogonally onto the boundary segment $P_{2}P_{3}$ , producing foot $L$ . Meanwhile, the point $P_{2}$ is projected onto edge $AC$ to form foot $M$ . If $|AL|>c$ and $|P_{2}M|>b$ , then the resulting triangle satisfies $\text{Area}(AQP_{2})>\frac{1}{2}b\cdot c$ , guaranteeing a lower bound for sub-triangle area during retriangulation.

Signal Condition	Cutoff Frequency $\Omega$	Recommended $h$
Sharp transitions (e.g., checkerboard, alias-prone)	$\pi$	$h\lesssim 0.59$
Natural images (antialiased or smoothed)	$\pi/2$	$h\lesssim 1.18$
Conservative safety margin	N/A	$h\leq 0.5$

Appendix

Table 5: Recommended edge-length bounds

h

for SBMT triangulation under typical signal conditions.

Panel of Figure 19 — Figure 19: Configurations of type (1,2) , where two boundary segments intersect a triangle with one and two points respectively. These patterns feature three embedded intersection points and support unified retriangulation rules across different edge locations.

Panel of Figure 20 — Figure 20: Typical (2,3) intersection patterns involving two boundary segments and their interaction with a single triangle. Classification is based on geometry to support complete, template-driven retriangulation.

Panel of Figure 21 — Figure 21: Representative configurations from the $(2,2)$ interaction class, where two consecutive boundary segments intersect a triangle with two intersection points each. These high-complexity cases demonstrate key subtypes including double edge crossings, vertex piercing, and corner-touching patterns. The illustrated cases are sampled from the complete lookup set, and each corresponds to a unique template-driven retriangulation rule. Full tabulation and rule assignments are provided in Appendix F of the Supplementary Material.

Panel of Figure 22 — Figure 22: Representative configuration of type (1,3) , involving one and three intersections from two adjacent boundary segments. This case has a unique retriangulation and requires no special handling.

Panel of Figure 23 — Figure 23: Illustrative (3,3) cases, where two segments intersect a triangle at three points each. Though excluded by SBMT’s $90^{\circ}$ angle constraint, these edge cases are shown for theoretical completeness. They verify that remeshing remains valid under sharp junctions, as long as no triangle is intersected by more than two segments.

Panel of Figure 24 — Figure 24: Heat diffusion using SBMT mesh and its deviation from analytic reference.

Panel of Figure 25 — Figure 25: Transient heat fields at $t=0.1$ , $0.3$ , and $0.5$ s (left to right) on the same bitmap-derived domain. Rows (top to bottom) show solutions on SBMT, Triangle (constrained Delaunay), and Gmsh meshes, respectively. SBMT yields boundary-aligned isotherms and sharper localization near thin lobes; Triangle and Gmsh produce smoother, slightly faster-spreading fronts.

Domain	$(a,b,c)$	$\theta_{\min}$ ( ∘ )	$A_{\min}$	Eq. (%)	$\mathrm{Var}(A)$	$\mathrm{AR}_{95}$	$\mathrm{AR}_{\max}$	#Tris
Star	$(0.22,0.10,0.15)$	$9.140$	$0.00867$	$94.46$	$0.000781$	$1.29476$	$9.20532$	$70650$
	$(0.24,0.115,0.17)$	$9.847$	$0.01162867$	$94.52$	$0.000712$	$1.2793$	$8.2771$	$70475$
	$(0.26,0.125,0.183)$	$10.32$	$0.01330030$	$94.66$	$0.000645$	$1.24342$	$7.79015$	$70292$
	$(0.27,0.125,0.185)$	$10.383$	$0.01347564$	$94.72$	$0.000623$	$1.22759$	$7.72205$	$70222$
	$(0.30,0.145,0.205)$	$12.53$	$0.01716856$	$94.86$	$0.000547$	$1.19911$	$7.11804$	$69995$
Droplet	$(0.22,0.10,0.15)$	$10.079$	$0.009722$	$96.61$	$0.000479$	$1.1547$	$9.20598$	$84550$

Appendix

Table 6: Sensitivity of SBMT mesh statistics over an expanded admissible range of threshold triplets

(a,b,c)

A Method for Exact Enforcement of Boundary Conditions on General Curved Triangular Domains: Algorithm and Application to Scientific Machine Learning
Oct 12, 2026Suchuan Dong, Yuchuan ZhangPDE Solving Neural PDE Solvers
Center for Computational and Applied Mathematics Department of Mathematics Purdue University, USA
Intrinsic and Triangulation-Agnostic Attention: A Simple and Powerful Approach for Learning on Meshes
Jul 27, 2026Ashwath Shetty, Zihan Zhu, Soeren Pirk +13D ViTs Geometric Representation Learning
Université de Montréal & Mila, Canada · Kiel University, Germany
Matérn Noise for Triangulation-Agnostic Flow Matching on Meshes
May 19, 2026Tianshu Kuai, Arman Maesumi, Daniel Ritchie +1Flow Matching 3D Mesh Generation
Université de Montréal & Mila, Canada · Brown University, USA

Oct 12, 2026J/K move · Enter open · S save

A Method for Exact Enforcement of Boundary Conditions on General Curved Triangular Domains: Algorithm and Application to Scientific Machine Learning

Suchuan Dong, Yuchuan Zhang

Center for Computational and Applied Mathematics Department of Mathematics Purdue University, USA

PDE Solving Neural PDE Solvers

Open paper AskPDF arXiv

We present a method for enforcing exactly Dirichlet, Neumann, and Robin conditions on general triangular domains with arbitrarily curved boundaries. The algorithmic constructions developed here complements those in a previous work for general quadrilateral domains. Our method combines (i) the exact mapping between a general curved triangular domain and the standard triangle, (ii) TFC constrained expressions, and (iii) Barnhill transfinite interpolations, to provide explicit closed-form trial ansatze that mathematically satisfy the imposed boundary conditions exactly. Corner compatibility induced by the boundary conditions is pivotal, and enforcing exactly the imposed boundary conditions hinges on the exact enforcement of the induced compatibility constraints. The corner compatibility associated with the acute vertices of the standard triangle and the coupling between gradient components when the hypotenuse corresponds to a Neumann/Robin boundary pose particular challenges. Two strategies are critical to resolving these issues, by reformulating conditional corner constraints into equivalent unconditional forms and by introducing a separate TFC-style auxiliary edge construction together with an associated linear solve on the hypotenuse. We analyze the corner compatibility constraints and present formulations for the general form of functions that exactly satisfy the imposed Dirichlet, Neumann, or Robin conditions on curved triangular domains. The proposed method has been implemented using extreme learning machine type randomized neural networks for solving PDE problems. We present ample numerical experiments with linear/nonlinear PDE problems on a variety of domains with complex boundary geometries. Numerical results show that the current method has enforced the Dirichlet, Neumann, and Robin conditions on curved domain boundaries to the machine precision.

Abstract

Explore similar work

A Method for Exact Enforcement of Boundary Conditions on General Curved Triangular Domains: Algorithm and Application to Scientific Machine Learning

Intrinsic and Triangulation-Agnostic Attention: A Simple and Powerful Approach for Learning on Meshes

Matérn Noise for Triangulation-Agnostic Flow Matching on Meshes