1 Introduction↩︎

Recent years have witnessed impressive progress in native 3D mesh generation. Unlike traditional pipelines that extract meshes from implicit shapes via Marching Cubes [1], native generation directly predicts vertex coordinates and topological connections. This paradigm yields lightweight meshes with high-quality topology, significantly facilitating downstream applications such as gaming and cinematic production.

Currently, the dominant paradigm for native mesh generation relies on autoregressive (AR) models [2], [3] rather than diffusion models [4], [5]. This discrepancy stems from the underlying data structures: AR models naturally handle variable-length, discrete data (such as mesh graphs), whereas diffusion models typically require fixed-length, continuous representations. Despite their tremendous success, AR-based methods suffer from inherent limitations dictated by the paradigm itself: (1) Restricted scalability: The inherent upper bound on token sequence length strictly limits the maximum number of generated faces, while vocabulary size constraints inherently restrict the quantization resolution of vertices within the normalized coordinate space. (2) Lack of attribute support: Incorporating other 3D attributes, such as color, UV mapping, or physically based rendering (PBR) materials, into the AR generation process remains an open challenge. (3) Fragile robustness: Unlike natural language, meshes are highly sensitive to erroneous tokens. A single mispredicted token can cause severe geometric artifacts, such as surface holes or flying faces, a vulnerability that is particularly exacerbated during long-sequence generation. Furthermore, AR models face practical bottlenecks, including slow inference speeds and high training costs. These challenges compel us to rethink the feasibility of adapting the highly successful diffusion paradigm for native mesh generation.

The crux of resolving this lies in establishing an equivalent continuous field representation for discrete triangular meshes. Such a representation would allow us to leverage the strong capability of neural networks in fitting continuous signals [6], thereby seamlessly integrating native mesh generation into mature and powerful 3D diffusion frameworks.

To this end, we propose Barycentric Dominance Field (BDF), a novel scalar field defined on the surface of triangular meshes. Formally, it is constructed simply by extracting the maximum barycentric coordinate of points on the triangle surface. As an intrinsic property of the mesh, BDF exhibits excellent mathematical properties, including \(C^0\) continuity and Lipschitz continuity. These properties establish a solid foundation for successful neural network fitting.

From a 3D generation perspective, BDF is highly analogous to a texture map. As shown in Fig. 1, this crucial insight allows us to process BDF using similar texture techniques, seamlessly incorporating it into existing VAE and diffusion frameworks. Conceptualizing BDF as a texture map elegantly decouples the geometry (shape) and topology of the mesh. The former can be obtained by leveraging powerful priors from existing 3D shape generation [7], allowing the generative network to focus exclusively on the latter—namely, the precise positioning of vertices on the high-resolution surface and their local connectivity.

In summary, our main contributions are as follows:

• We propose BDF, a novel scalar field defined on the triangular mesh surface, and formally prove its mathematical properties. This representation bridges the gap between discrete native mesh generation and the continuous diffusion paradigm.

• By conceptualizing BDF as a texture map, we seamlessly integrate BDF into the powerful 3D VAE and Diffusion generative paradigm without requiring modifications to the underlying model architecture.

• Extensive experiments demonstrate the effectiveness of this novel mesh representation, showcasing superior generation quality, scalability, and robustness compared to state-of-the-art autoregressive methods.

2 Related Works↩︎

2.1 Non-Native Mesh Generation↩︎

To fit the continuous nature of diffusion models, most 3D generation methods encode meshes into implicit fields like Signed Distance Fields (SDFs) [8]–[14]. While preserving overall geometry, this process entirely discards original vertex positions and topological connectivity. Extracting explicit surfaces from these fields requires algorithms like Marching Cubes (MC). Although recent high-fidelity methods predict shapes directly on MC or Dual Contouring (DC) grids [7], [15]–[18], they inevitably yield excessively dense and irregular triangulations (i.e., messy wireframes).

2.2 Native Mesh Generation↩︎

Inspired by NLP, autoregressive (AR) paradigms have been widely adapted for native 3D mesh generation [2], [3]. To scale face counts or enhance topology, existing works explore novel tokenization strategies [19]–[22], architectural modifications [23], or post-training techniques [24], [25]. However, diffusion-based native mesh generation remains sparse due to the discrete nature of meshes. Pioneering works like PolyDiff [26] and PartDiffuser [27] adapt continuous diffusion into discrete modes, while MeshCraft [28] designs a specialized VAE tailored for flow models. Notably, concurrent work LATO [29] proposes an engineered mesh-to-voxel codec to enable the use of mature 3D VAEs and flow models.

Unlike LATO’s heuristically designed codec, our proposed BDF leverages an intrinsic mathematical property of triangular surfaces. It establishes a natural equivalence between discrete meshes and continuous scalar fields, seamlessly integrating with the Dual Contouring algorithm. This provides a mathematically grounded, elegant, and highly generalizable solution for native mesh generation.

3 Barycentric Dominance Field↩︎

We introduce the Barycentric Dominance Field (BDF), a novel scalar field defined directly on the triangle mesh surface.

3.1 Formulation↩︎

For a given triangle \(T\) with vertices \(V_1, V_2, V_3\), any point \(p \in T\) can be uniquely expressed using its barycentric coordinates \((w_1, w_2, w_3)\) as follows: \[\begin{gather} p = w_1 V_1 + w_2 V_2 + w_3 V_3 \\ \text{where}\quad w_1+w_2+w_3 = 1, \quad w_i \ge 0 \quad \text{for} \quad i \in \{1,2,3\} \end{gather}\] We define the Barycentric Dominance Field (BDF) value at point \(p\), denoted as \(B(p)\), as the maximum of its barycentric coordinates: \[B(p) = \max(w_1, w_2, w_3)\] This definition naturally extends to a complete 3D mesh surface \(\mathcal{M} = \{T_k\}\). For any point on the mesh, its BDF value is evaluated based on the specific triangle it resides in, as shown in Fig. 1.

3.2 Theoretical Properties↩︎

The proposed BDF has several simple yet useful properties for neural surface representation:

\(C^0\) continuity. The BDF is continuous over the mesh surface. Intuitively, within each triangle, the barycentric coordinates change smoothly as the point moves on the triangle, and thus their maximum also changes continuously. Moreover, when a point moves across a shared edge between two adjacent triangles, the barycentric coordinate corresponding to the opposite vertex becomes zero on both sides. Therefore, the BDF value computed from either triangle is consistent on the shared edge, which avoids abrupt jumps across triangle boundaries.

Lipschitz continuity. The BDF is also Lipschitz continuous on a finite non-degenerate triangular mesh. In simple terms, this means that the BDF value cannot change arbitrarily fast when the point moves along the surface. This property comes from the fact that barycentric coordinates are affine functions within each triangle, and the maximum operation does not amplify the variation of its inputs. As a result, the BDF has bounded local variation over the mesh surface.

These properties make BDF a well-behaved supervision signal for neural field learning. Its continuity avoids artificial discontinuities on the mesh, while its Lipschitz continuity provides a bounded and stable target for function approximation. Therefore, BDF can be effectively fitted by standard neural networks. We provide detailed proofs of these properties in Appendix 7.

4 Method↩︎

To realize native mesh generation based on BDF, we adopt Trellis.2 [7]—a powerful 3D generation pipeline based on sparse voxels and flow models—as our backbone. We first introduce the algorithm design for mesh-to-voxel encoding and decoding, followed by the generation pipeline.

4.1 Algorithms of BDF Encoding and Decoding↩︎

Dual Contouring. To efficiently compress complex mesh geometries into sparse voxels, Trellis.2 utilizes a training-free, explicit mesh-to-sparse-voxel compression scheme based on the Dual Contouring (DC) algorithm. Specifically, given an input mesh and a high-resolution voxel grid, the DC algorithm first determines whether the voxel edges along the \(x\), \(y\), and \(z\) axes intersect with the mesh triangles, yielding three bool intersection flags \(\in \text{B}^3\). For each intersected edge, it assigns a small quad whose vertices are the centers of the four surrounding voxels (termed Dual Vertices \(\in \text{R}^3\)). A Quadratic Error Function (QEF) is then minimized to fit these four vertices to the underlying surface, with a regularization term restricting them within their respective voxels. To compute the QEF, Hermite data (i.e., intersection points and surface normals) are temporarily cached on each intersected edge. Additionally, following the design of FlexiCubes [30], each dual vertex stores an extra splitting scalar (\(\in \text{R}^1\)) to indicate the subdivision pattern of the quad.

Voxel Encoding. We retain the original DC algorithm entirely and introduce an incremental extension: during the computation of Hermite data, we additionally calculate the barycentric coordinates of the intersection points and store the corresponding BDF values on the voxel edges. As illustrated in Fig. 2, given the sufficiently high resolution of the voxel grid (typically \(512^3\) or \(1024^3\)), this encoding process can be viewed as a dense sampling of the surface BDF. To explicitly encourage the network to learn vertex positions, we further match the original mesh vertices with the intersection points in the Hermite data, assigning a peak BDF value of \(1.0\) to the corresponding edges.

Surface Decoding. Given the voxel data where each edge encodes a BDF value, we first decode the surface quads directly using dual vertices and intersection flags. Since each quad corresponds to an intersected edge, it naturally inherits a BDF value. To facilitate subsequent algorithmic processing, we transform these BDF-augmented quads into a dual graph structure: each quad center acts as a graph node endowed with its BDF value, and edges are formed by connecting adjacent quads.

Mesh Reconstruction. We first apply Non-Maximum Suppression (NMS) on the dual graph to identify the mesh vertices. Inspired by the concept of dual meshes, we design a BDF-guided flood-fill algorithm to construct an equivalent Voronoi-style representation for mesh reconstruction. The "flood" initiates simultaneously from all identified mesh vertices and propagates along the BDF contours. When floodfronts from different vertices meet, an edge is instantiated between the corresponding vertices. Upon completion, this process yields a wireframe structure composed of vertices and edges. Since this wireframe inherently adheres to the mesh surface, we simply traverse it to find simple cycles of length 3 or 4 to reconstruct the final, complete mesh faces. As shown in Fig. 2, we provide a 2D toy example of this flood-fill algorithm, where each pixel denotes a DC quad. Intuitively, during the flood-fill process, fronts meet at BDF saddle points (where BDF value is \(1/2\)) to recover the original mesh edges, and the process terminates at the local minima (where BDF value is \(1/3\)). The pseudocode for this algorithm is provided in the Appendix 8.

4.2 Generation Pipeline↩︎

VAE. As shown in Fig. 3, since the BDF encoding aligns closely with how Trellis.2 encodes dual vertices and textures, it only incurs a marginal cost of 3 additional float values per sparse voxel, representing the BDF values on the \(x\), \(y\), and \(z\) edges. Considering that the Shape and Material (Texture) modules in Trellis.2 utilize identical U-Net-style [31] VAEs with input/output dimensions of 7 and 6 respectively, we directly repurpose this architecture to construct the BDF VAE, setting the input/output dimensions to 3. Notably, the intersection flags can be directly retrieved from the Shape VAE, eliminating the need for redundant encoding of BDF VAE.

Our VAE design ensures complete decoupling from the original Shape and Material VAEs, sharing only essential structural information (e.g., intersections and subdivision patterns during voxel upsampling). This design elegantly leverages the powerful shape priors from the Shape VAE to construct the underlying surface, allowing the BDF VAE to focus exclusively on learning the precise locations of mesh vertices on this high-fidelity surface and their local connectivity.

During training, to eliminate background noise and focus the network’s capacity on the actual surface, the reconstruction loss is exclusively computed on the valid intersected edges, denoted as the set \(E_{int}\). Furthermore, to encourage the network to predict sharp and accurate vertices, we introduce a spatially varying weight \(w_i\). The training loss for the BDF VAE is formulated as:

\[\mathcal{L}_{VAE} = \lambda_{field} \mathcal{L}_{field} + \lambda_{KL} \mathcal{D}_{KL}\]

where \(\mathcal{D}_{KL}\) regularizes the latent space, and the field reconstruction loss \(\mathcal{L}_{field}\) is defined as a weighted Binary Cross-Entropy (BCE) loss over the intersected edges:

\[\mathcal{L}_{field} = - \frac{1}{\sum_{i \in E_{int}} w_i} \sum_{i \in E_{int}} w_i \left[ x_i \log(\hat{x}_i) + (1 - x_i) \log(1 - \hat{x}_i) \right]\]

Here, \(x_i\) and \(\hat{x}_i\) represent the normalized ground truth and predicted BDF values, respectively. The weight \(w_i\) is defined as:

\[w_i = \begin{cases} \lambda_{point}, & \text{if } x_i > 0.999 \\ 1, & \text{otherwise} \end{cases}\]

By assigning a significantly larger weight (\(\lambda_{point} \gg 1\)) to the actual mesh vertices (\(x_i > 0.999\)), we effectively penalize vertex blurring.

Flow Model. Following the training and inference paradigm of the Material Flow Model in Trellis.2, we first employ the Shape Flow Model to predict the shape latents \(z^{\text{shape}}\) conditioned on the input image. Subsequently, a sparse Diffusion Transformer (DiT) [32] predicts the BDF latents \(z^{\text{BDF}}\), conditioned jointly on the input image and the generated shape latents \(z^{\text{shape}}\). As illustrated in Fig. 3, similar to the VAE stage, we completely freeze the Shape and Material Flow Models, decoupling them from the BDF Flow. This strategy fully preserves the robust shape and texture generation capabilities of the pre-trained models.

5 Experiments↩︎

5.1 Datasets and Implementation Details↩︎

Due to storage constraints, we utilize the Texverse [33] dataset and filter a high-quality subset of approximately 180k 3D assets to train the VAE and flow models. The BDF VAE is trained on 8 \(\times\) H200 GPUs with a batch size of 8, taking roughly 16 hours. Similarly, the BDF Flow model is trained on 8 \(\times\) H200 GPUs with a batch size of 8, requiring about 24 hours. Following the training protocol of Trellis.2, all models are optimized using AdamW [34] (learning rate \(1 \times 10^{-4}\), weight decay \(0.01\)) and employ classifier-free guidance with a drop rate of \(0.1\).

5.2 Evaluation Setting↩︎

Datasets and Metrics. We select the Toys4k [35] dataset to compare our method against state-of-the-art baselines. To rigorously evaluate the robustness of our approach on high-poly, artist-created meshes (typically \(>10\text{k}\) faces), we construct two evaluation splits: a standard set of 200 meshes with \(0 \sim 10\text{k}\) faces, and a complex set of 100 meshes with \(0 \sim 40\text{k}\) faces. We employ three standard geometric metrics: Chamfer Distance (CD), Hausdorff Distance (HD), and Normal Consistency (\(|\text{NC}|\)), calculated using \(30,000\) sampled surface points.

Baselines and Condition Alignment. We select three representative autoregressive (AR) native mesh generation models as our baselines: MeshSilksong [22], DeepMesh [24], and MeshRipple [36]. Since these AR models require point clouds as input conditions, we design a fair alignment pipeline: we first feed the rendered images of artist-created meshes into Trellis.2 to generate dense meshes, and then sample point clouds from these surfaces to serve as the condition for the AR baselines.

5.3 Results and Comparisons↩︎

Quantitative Results. As shown in Table 1, while AR baselines perform well on low-poly meshes (\(0 \sim 10\text{k}\)), their geometric metrics degrade significantly on more complex samples (\(0 \sim 40\text{k}\)). In contrast, our method outperforms them across all metrics and exhibits exceptional robustness as data complexity scales, particularly in CD scores.

Qualitative Results. Fig. 4 illustrates that AR methods struggle with complex shapes, often failing due to token limits or producing fragmented faces. This stems from error accumulation in long sequences, to which discrete meshes are notoriously sensitive. Our method elegantly bypasses these token limits, with its resolution bounded only by the Dual Contouring grid.

Furthermore, we compare our approach against ultra-high-poly generation (Trellis.2) followed by naive decimation (Fig. 5). While Trellis.2 yields intricate meshes, their massive face counts (\(>1\)M) necessitate decimation for practical downstream deployment, which inevitably causes severe geometric degradation and chaotic topology. Conversely, our method directly outputs production-ready meshes with moderate face counts, preserving uncorrupted geometry and excellent topology.

Finally, Fig. 1 demonstrates the joint generation of mesh topology and PBR textures. To our knowledge, we are the first to achieve this unified generation within a single framework, highlighting the remarkable scalability of BDF.

5.4 Ablation Studies↩︎

VAE Loss: BCE vs. MSE. While BDF resembles a texture map (suggesting MSE loss), its sharp nature (peaking at \(1.0\) at vertices) requires precise localization. BCE loss provides stronger gradient signals to restore these sharp peaks. As shown in Table 2, we evaluate vertex reconstruction using CD, HD, and F-score (under strict tolerances of \(0.5, 1, 2, 3\) voxel units). Although MSE yields comparable CD and HD, it falls significantly short under the stricter F-score, proving BCE is crucial for accurate vertex localization.

Decoupled vs. Jointed VAE. Since BDF correlates with surface geometry (e.g., peaks at sharp features), integrating it into the Shape VAE (expanding channels from 7 to 10) and fine-tuning via ControlNet-style zero-convolutions [37] might seemingly facilitate learning. However, Table 2 shows this Jointed VAE unexpectedly entangles the latent space, severely degrading vertex accuracy. Visually (Fig. 6), flow models trained on this joint latent space generate "muddy" BDF fields with chaotic peak distributions, confirming the necessity of our decoupled architecture.

6 Conclusion↩︎

In this paper, we introduced the Barycentric Dominance Field (BDF), a continuous scalar field that elegantly bridges discrete native mesh generation and the continuous diffusion paradigm. By conceptualizing BDF as an intrinsic surface texture, we seamlessly integrated it into existing 3D VAE and diffusion frameworks without architectural modifications. This design bypasses the token-length and robustness bottlenecks of autoregressive models, enabling the first unified generation of native meshes and PBR textures. Experiments demonstrate our method’s state-of-the-art geometric quality and scalability, particularly on complex, high-poly assets.

Limitations and Future Work. While effective, BDF’s current codec need not be strictly confined to Dual Contouring (DC). During encoding, the DC grid resolution imposes a physical limit: topological information of extremely small faces missing grid intersections is inevitably lost. During decoding, because our flood-fill algorithm operates on the DC-recovered surface, self-intersecting triangles in the original mesh can mislead propagation, yielding erroneous connections. Future work will explore resolution-independent codecs to fully unleash BDF’s potential for intricate, ultra-fine 3D structures.

Technical appendices and supplementary material↩︎

7 Proof of BDF Continuity and Lipschitz Continuity↩︎

In this section, we provide the detailed proof for the continuity properties of the proposed Barycentric Dominance Field (BDF).

7.1 \(C^0\) Continuity↩︎

Proposition 1. Let \(\mathcal{M}\) be a triangular mesh surface, and let \(B(p)\) be the BDF value defined as the maximum barycentric coordinate of point \(p\). Then \(B(p)\) is \(C^0\) continuous on \(\mathcal{M}\).

Proof. We first consider a single triangle \(T\) with vertices \(V_1,V_2,V_3\). For any point \(p \in T\), its barycentric coordinates \((w_1,w_2,w_3)\) satisfy \[p = w_1 V_1 + w_2 V_2 + w_3 V_3, \quad w_1+w_2+w_3 = 1.\] Inside a non-degenerate triangle, each barycentric coordinate \(w_i\) is an affine function of \(p\). Therefore, \(w_1,w_2,w_3\) are continuous functions on \(T\). Since the maximum of finitely many continuous functions is still continuous, we have \[B(p) = \max(w_1,w_2,w_3)\] continuous inside each triangle.

It remains to verify continuity across triangle boundaries. Consider two adjacent triangles \(T_a\) and \(T_b\) sharing an edge with endpoints \(V_1\) and \(V_2\). Let their third vertices be \(V_3\) and \(V_4\), respectively. For any point \(p\) on the shared edge, \(p\) can be represented as \[p = w_1 V_1 + w_2 V_2, \quad w_1 + w_2 = 1, \quad w_1,w_2 \ge 0.\] When \(p\) is viewed as a point in triangle \(T_a\), its barycentric coordinate associated with \(V_3\) is zero. Thus, its barycentric coordinates in \(T_a\) are \((w_1,w_2,0)\). Similarly, when \(p\) is viewed as a point in triangle \(T_b\), its barycentric coordinate associated with \(V_4\) is zero, and the coordinates are also \((w_1,w_2,0)\) with respect to the shared edge.

Therefore, the BDF value computed from either side is \[B(p) = \max(w_1,w_2,0) = \max(w_1,w_2).\] Hence, the BDF values agree on shared edges. The same argument naturally holds at shared vertices, where one barycentric coordinate is one and the others are zero. Consequently, \(B(p)\) is continuous across all triangle boundaries, and thus is \(C^0\) continuous on the whole mesh surface \(\mathcal{M}\). \(\square\)

7.2 Lipschitz Continuity↩︎

Proposition 2. Let \(\mathcal{M}\) be a finite triangular mesh composed of non-degenerate triangles. Then the BDF \(B(p)\) is Lipschitz continuous on \(\mathcal{M}\) with respect to the intrinsic surface distance.

Proof. We first prove the Lipschitz continuity on a single triangle \(T\). Let \(T\) have vertices \(V_1,V_2,V_3\). Any point \(p \in T\) can be written as \[p = V_1 + u_1 (V_2 - V_1) + u_2 (V_3 - V_1),\] where \(u_1 = w_2\) and \(u_2 = w_3\). The remaining barycentric coordinate is \[w_1 = 1 - u_1 - u_2.\] Since \(T\) is non-degenerate, the mapping from \(p\) to \((u_1,u_2)\) is affine on the triangle plane. Therefore, there exists a finite constant \(L_T > 0\) such that for any \(p,q \in T\), \[\|w(p)-w(q)\|_2 \le L_T \|p-q\|_2,\] where \(w(p)=(w_1(p),w_2(p),w_3(p))\) denotes the barycentric coordinate vector of \(p\).

Next, we use the fact that the maximum function is \(1\)-Lipschitz with respect to the \(\ell_\infty\) norm. For any two vectors \(x,y \in \mathbb{R}^3\), we have \[|\max_i x_i - \max_i y_i| \le \max_i |x_i-y_i| = \|x-y\|_\infty \le \|x-y\|_2.\] Applying this inequality to the barycentric coordinate vectors of \(p\) and \(q\), we obtain \[\begin{align} |B(p)-B(q)| &= |\max_i w_i(p) - \max_i w_i(q)| \\ &\le \|w(p)-w(q)\|_2 \\ &\le L_T \|p-q\|_2. \end{align}\] Thus, \(B(p)\) is Lipschitz continuous within each triangle.

Now consider the whole mesh \(\mathcal{M}=\{T_k\}_{k=1}^{N}\). Since the mesh contains a finite number of non-degenerate triangles, each triangle has a finite Lipschitz constant \(L_{T_k}\). Define \[L = \max_{k=1,\dots,N} L_{T_k}.\] Then \(L\) is finite.

For any two points \(p,q \in \mathcal{M}\), consider a surface path \(\gamma\) connecting them. This path can be decomposed into finitely many segments, where each segment lies inside a single triangle. Applying the per-triangle Lipschitz bound to each segment and summing over all segments gives \[|B(p)-B(q)| \le L \, \mathrm{Length}(\gamma).\] Taking the infimum over all surface paths \(\gamma\) connecting \(p\) and \(q\), we obtain \[|B(p)-B(q)| \le L \, d_{\mathcal{M}}(p,q),\] where \(d_{\mathcal{M}}(p,q)\) denotes the intrinsic surface distance on \(\mathcal{M}\). Therefore, the BDF is globally Lipschitz continuous on the mesh surface. \(\square\)

8 Details of the BDF-Guided Flood-Fill Algorithm↩︎

In this section, we provide the detailed implementation of the BDF-guided flood-fill algorithm used for mesh reconstruction, as introduced in Section 4.

The core objective of this algorithm is to robustly extract topological connections (i.e., mesh edges) between the identified mesh vertices (seeds) on the dual graph. To achieve high efficiency and parallelism, we formulate this flood-fill process as a multi-source shortest path problem.

Specifically, given the dual graph \(\mathcal{G} = (\mathcal{V}, \mathcal{E})\) where nodes represent dual contouring quads and edges represent their adjacency, each node \(v \in \mathcal{V}\) is associated with a predicted BDF value \(f(v)\). Let \(\mathcal{S} \subset \mathcal{V}\) denote the set of identified mesh vertices (seeds). We define the directed traversal weight (or "flow resistance") from node \(u\) to an adjacent node \(v\) as:

\[w(u, v) = \exp(\alpha \cdot (f(v) - f(u)))\]

where \(\alpha\) is a scaling hyperparameter. Since BDF values peak at mesh vertices (\(1.0\)) and monotonically decrease towards the face centers (\(1/3\)), a negative difference (\(f(v) - f(u) < 0\)) indicates "flowing downhill" along the BDF gradient, resulting in a minimal traversal cost. Conversely, flowing uphill incurs an exponentially large penalty. This design strictly constrains the flood to propagate along the BDF contours.

To solve this efficiently, we introduce a virtual Super Source node \(v_{super}\) connected to all seed nodes in \(\mathcal{S}\) with zero-weight edges. This elegantly converts the multi-source propagation into a standard single-source Dijkstra’s algorithm, allowing simultaneous flooding from all seeds. After computing the shortest paths, each node is assigned an "owner" corresponding to its closest seed via predecessor tracking. Finally, the original mesh edges are recovered by identifying the meeting frontiers—that is, the edges \((u, v) \in \mathcal{E}\) where the adjacent nodes belong to different owners. The complete procedure is summarized in Algorithm 1.

References↩︎