{"id":"f86dd93a-9206-4f07-8719-d6791f90f660","arxiv_id":"2412.16776","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"DMesh++ speeds up differentiable mesh generation by using a Minimum-Ball condition instead of weighted Delaunay triangulation, enabling faster reconstruction of complex shapes.","lead":"This paper presents DMesh++, a differentiable mesh representation that replaces the slow weighted Delaunay triangulation step of an earlier method with a Minimum-Ball condition. The result is a faster pipeline for reconstructing complex 2D and 3D shapes from point clouds or multi-view images, with a claimed asymptotic speedup.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(log N) claim in Sec. 3.2 is not realized by the implementation: PyTorch3D's knn_points is a linear scan, and with |F|=N in the benchmarks the total tessellation work is O(N^2); the periodic full-Delaunay refresh (Algorithm 2, line 9) is an unaccounted cost.","rationale":"We agree with the reader that the paper's headline complexity claim is the key assumption. The Minimum-Ball condition itself is a valid characterization of Delaunay faces (Lemma 3.2), and the reconstruction results are state-of-the-art on several metrics; the code is released and the empirical speedups are reproducible in the reported range. However, the asymptotic claim is not backed by the shown implementation. The paper states O(|F| * log |P|) and then reduces it to O(log |P|) by assuming GPU parallelization and |F| bounded, but the experiment fixes |F| = N, and the actual kNN is PyTorch3D's brute-force linear scan. Thus the total work is quadratic in N, and the observed sub-linear scaling up to 50K is a parallelism artifact, not an algorithmic improvement. The periodic full-Delaunay refresh adds further unsupported cost. Without a real spatial index or a corrected complexity statement, the central 'O(N) to O(log N)' claim should not be taken at face value. This does not invalidate the method's practical value, so a conditional acceptance with a request to fix the complexity analysis or implement a true O(log N) index remains appropriate.","tokens_in":24250,"tokens_out":6380,"duration_ms":52006,"concrete_test":"Use the released code to time only the knn_points call in Algorithm 1 for N = 10K, 20K, 40K, 80K, 160K with |F| = N, as in Sec. 5.1, and fit T(N) = c * N^p. If p is approximately 2, the per-face NN is linear and the O(log N) claim fails for the implemented method. Additionally, profile the Update-Query-Faces DT in Algorithm 2 over one full epoch (n0=2000, n1=50) and report its fraction of total tessellation time; if substantial, the claimed complexity omits a dominant step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim, repeated in the abstract and Sec. 3.2, is that the Minimum-Ball algorithm evaluates face existence in O(log N) time, replacing DMesh's O(N) WDT. This rests on implausible or unmet conditions. First, the paper assumes each nearest-neighbor query can be answered in O(log N) time via a spatial index, but the implementation (footnote 2) uses PyTorch3D's knn_points, which is a brute-force linear scan: per-face cost is O(N), not O(log N). Second, the complexity expression O(|F| * log |P|) only becomes O(log |P|) if |F| is constant, yet the tessellation benchmark (Sec. 5.1) sets |F| = N (randomly selecting N query faces), so the total work is O(N^2) even with a logarithmic index. Third, Algorithm 2's Update-Query-Faces runs a full Delaunay triangulation of all points (line 9, Appendix 8.2.2) every n1 steps; this cost is excluded from the O(log N) claim but is part of the tessellation pipeline. The measured speedups are real but reflect GPU parallelism over brute-force distance computations, not an asymptotic improvement; the experiment's 'sharper increase beyond 50K' is consistent with quadratic scaling. Since the scalability claim is the paper's headline contribution, it must be corrected or supported with an actual spatial index.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces DMesh++, a differentiable mesh representation that replaces DMesh's Weighted Delaunay Triangulation (WDT) with a Minimum-Ball condition for face existence. The Minimum-Ball condition (Definition 3.1) declares a face present when its minimum bounding ball contains no other point, and Lemma 3.2 shows these faces are a subset of Delaunay faces. The paper claims an O(log N) tessellation complexity, lower memory use, and demonstrates 2D and 3D point-cloud reconstruction plus 3D multi-view reconstruction, comparing against PSR, VoroMesh, PoNQ, DMTet, FlexiCubes, GShell, and DMesh. The supplementary material adds implementation details, nearest-neighbor caching, a periodic query-face refresh that runs a full Delaunay triangulation, and an experimental Reinforce-Ball algorithm.","tokens_in":24643,"tokens_out":5284,"duration_ms":49512,"significance":"If the efficiency and reconstruction claims hold, the Minimum-Ball formulation is a useful step toward scalable differentiable meshes: the geometric lemma is correct, the method is benchmarked against external methods rather than only the authors' prior DMesh, the code and project page are promised, and the reported reconstruction metrics are often better than the baselines, especially on open surfaces. The measured wall-clock speedups over DMesh are plausible and the paper is transparent about remaining limitations such as non-manifoldness and real-image reconstruction. However, the central asymptotic claim in the abstract and Section 3.2 is not supported by the paper's own analysis or its implementation, and the actual pipeline still invokes full Delaunay triangulations. The practical contribution therefore needs to be separated from the unsupported O(log N) claim.","major_comments":[{"comment":"The O(log N) complexity claim is not supported. Section 3.2 derives only O(|F| log |P|), and the reduction to O(log |P|) rests on parallelization and on the parenthetical assumption that |F| does not grow with |P|. Footnote 2 states that the implementation uses PyTorch3D's knn_points, which is a brute-force linear scan over all points for each query, so the per-face nearest-neighbor cost is O(|P|), not O(log |P|). Section 5.1 then chooses |F| = N query faces, making the total tessellation work O(N^2) even with an idealized logarithmic index. Parallelizing a fixed total amount of work changes wall-clock time on a given GPU but does not change the asymptotic complexity. The measured 'sub-linear' behavior up to 50K points and the sharper increase beyond that are consistent with brute-force GPU scans, not with O(log N) scaling. This claim must be removed or supported with an actual spatial-index implementation and an explicit accounting of |F|.","section":"Abstract and Sec. 3.2"},{"comment":"The statement that DMesh++ 'eliminates WDT' is contradicted by the reconstruction pipeline. Algorithm 2's Update-Query-Faces function performs a full Delaunay triangulation of the entire point set every n1 steps, and Step 3 (Appendix 8.2.3) explicitly computes the DT of the points and then checks which DT faces satisfy the Minimum-Ball condition. These operations have essentially the same cost class as the WDT that the paper claims to remove, and their cost is excluded from the O(log N) claim in Section 3.2. The paper should include these Delaunay computations in the complexity analysis, or reframe the contribution as reducing the cost of per-face probability evaluation given an externally supplied candidate-face set.","section":"Algorithm 2, line 9 and Appendix 8.2.2"},{"comment":"The theoretical tessellation function is not shown to be a complete tessellation. The paper concedes in Section 3.2 that Fmin is only a subset of Delaunay faces and may omit faces such as AB in Figure 5, so Fmin alone does not tessellate the convex domain. The actual reconstruction relies on candidate faces extracted from a full Delaunay triangulation (Appendix 8.2.2), not on Fmin alone. The relationship between the theoretical Minimum-Ball tessellation and the mesh generated in the experiments should be clarified, because the claim that DMesh++ retains DMesh's core advantage of a self-contained tessellation function depends on this point.","section":"Definition 3.1 and Appendix 8.2.2"}],"minor_comments":[{"comment":"Figure 7 reports averages over 5 trials without error bars or per-trial values; given the small number of trials and the large speedup claims, the variability should be reported.","section":"Sec. 5.1, Fig. 7"},{"comment":"The memory comparison is partly explained by the note that the 2D DMesh implementation is not CUDA-optimized; the '96% less GPU memory' claim should be stated with this caveat in the main text.","section":"Footnote 4 and Sec. 5.1"},{"comment":"The assumption that |F| does not grow exponentially with |P| is essential to the complexity claim but appears only in a footnote; it should be moved to the main text and justified with the actual query-face generation procedure.","section":"Sec. 3.2, footnote 3"},{"comment":"The captions state that the best results for closed and open surfaces are highlighted in red and blue, but the printed tables do not show these colors unambiguously; a legend or explicit formatting marker would help.","section":"Tables 3 and 5"},{"comment":"The nearest-neighbor caching introduces hyperparameters n0, n1, and K, but no ablation is provided for their effect on reconstruction quality or speed; a brief sensitivity study would strengthen the practical claims.","section":"Appendix 7.4"}],"recommendation":"major_revision","confidential_remarks":"The paper has a solid empirical core: the Minimum-Ball lemma is correct, the reconstruction results are competitive, and the authors are transparent about the remaining limitations. The main problem is the unsupported asymptotic claim, which appears in the abstract and Section 3.2 and is not realized by the implementation. I believe the manuscript can be made suitable through a major revision that either implements a real logarithmic nearest-neighbor structure and accounts for the full pipeline, or honestly reframes the contribution as a practical GPU-accelerated approximation with measured speedups rather than an asymptotic improvement. The heavy reliance on the authors' own DMesh baseline is acceptable as a comparison, but the novelty relative to DMesh should be stated more precisely after the complexity discussion is corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First the punchline: the Minimum-Ball condition is a real improvement over DMesh's WDT, and the reconstruction experiments are strong, but the paper's central complexity claim—O(log N) instead of O(N)—does not hold up as stated. The implementation uses PyTorch3D's knn_points, which is a brute-force linear scan, and the benchmark sets |F| = N, so the total tessellation work is O(N^2), not O(log N). The periodic Delaunay refresh in Algorithm 2 adds another unaccounted cost. The speedups are real, but they come from GPU parallelism on brute-force distance computations, not from an asymptotic improvement.\n\nWhat is genuinely new: the Minimum-Ball tessellation condition (a face is kept if its minimum bounding ball is empty) and the Reinforce-Ball stochastic pruning idea in the appendix. Lemma 3.2 is correct and simple. The method stays free of self-intersections, which matters for downstream use, and the paper demonstrates this experimentally. The experiments are the strong part: large-scale point cloud and multi-view reconstruction against PSR, VoroMesh, PoNQ, DMTet, FlexiCubes, GShell, and DMesh, with particular success on open surfaces. The authors also ship code and a detailed appendix. That is real evidence.\n\nSoft spots, in proportion: the complexity claim is the big one. The abstract says 'O(N) to O(log N)' but Sec. 3.2 only establishes O(|F|·log|P|), which reduces to O(log|P|) only if |F| is constant. In the benchmark |F| = N, so with a spatial index the total is O(N log N). With the actual PyTorch3D kNN, it is O(N^2). The paper's own figure shows a sharper increase beyond 50K points, consistent with quadratic scaling. This needs to be corrected, either by implementing a real spatial index or by restating the claim as practical speedup. Minor: reconstruction tables have no error bars, and some models are manually selected. Standard for the area, not fatal.\n\nWho this is for: anyone working on differentiable meshes, or mesh reconstruction from point clouds or multi-view images. It deserves a serious referee; the technique is novel and the empirical work is solid, but the author should be required to fix the complexity accounting before publication. I would take it to our reading group.","headline":"A genuinely faster differentiable mesh tessellation, but the O(log N) headline is not what the implementation delivers.","tokens_in":25138,"tokens_out":4164,"would_cite":true,"duration_ms":34322,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that replacing weighted Delaunay triangulation with a Minimum-Ball condition cuts differentiable mesh tessellation from linear to logarithmic time, enabling reconstruction of complex 2D and 3D shapes.","keywords":["differentiable mesh","Minimum-Ball condition","Delaunay triangulation","nearest neighbor search","point cloud reconstruction","multi-view reconstruction","mesh topology","probabilistic mesh"],"falsifier":"Measure the wall-clock time of a single tessellation step on random point sets of size $N = 10^3$ through $10^6$, with the brute-force neighbor scan replaced by an exact accelerated search; if per-face query time does not stay near $O(\\log N)$, or if total time scales as $O(N^2)$, the complexity claim fails. Separately, count the candidate faces $|F|$ during a running reconstruction: if $|F|$ grows linearly with $N$, the effective tessellation cost is $O(N \\log N)$, not $O(\\log N)$.","tokens_in":24083,"feed_emoji":"🔺","tokens_out":13929,"duration_ms":96998,"temperature":0.7,"pith_summary":"DMesh++ sets out to remove the computational bottleneck that kept differentiable meshes—surfaces whose connectivity is learned by gradient descent rather than fixed in advance—from representing highly detailed shapes. The earlier DMesh formulation decided which faces exist by computing a weighted Delaunay triangulation, a sequential construction whose practical cost grows linearly with the number of points. DMesh++ replaces that global construction with a Minimum-Ball condition: a candidate face survives only if the smallest ball through its vertices contains no other point, which is decided by a single nearest-neighbor query per face. The paper argues this brings tessellation cost to $O(\\log N)$ under GPU parallelization, and demonstrates the payoff on intricate 2D drawings, dense 3D point clouds, and multi-view images, with better reconstruction accuracy than prior differentiable mesh methods and a fraction of the time.","feed_headline":"One ball test makes differentiable meshes 32x faster","feed_subtitle":"A nearest-neighbor query per face replaces costly triangulation, letting mesh learning capture intricate shapes.","key_machinery":"The Minimum-Ball algorithm is the paper's central object. For each query face $F$, it computes the smallest ball whose circumference or surface passes through the face's vertices—via closed-form center formulas in 2D and 3D—and then finds the nearest point of the point set to the ball's center. The signed distance $d(B_F,P)$ between that point and the ball's boundary decides whether $F$ qualifies, and is passed through a scaled sigmoid $\\sigma(d \\cdot \\alpha_{\\min})$ to produce a face-existence probability. This single nearest-neighbor query replaces the whole weighted Delaunay triangulation of DMesh, converting a sequential $O(N)$ global construction into per-face queries that can be parallelized across the GPU; between optimization steps the algorithm caches nearest neighbors and periodically refreshes the candidate face list, so gradients flow through positions and real values without rebuilding the full structure each step.","core_discovery":"DMesh++ claims that mesh connectivity can be made differentiable and scalable at the same time by substituting the Minimum-Ball condition for weighted Delaunay triangulation. For a candidate face $F$ with $d$ vertices in $d$-dimensional space, it computes the unique minimum bounding ball $B_F$ whose boundary passes through those vertices, then measures the signed distance from the ball's surface to the nearest other point. The face is real when that distance is positive (no other point lies strictly inside the ball) and every vertex carries a real value $\\psi > 0.5$; the signed distance is mapped through a sigmoid to give a differentiable existence probability $\\Lambda_{\\min}(F)$. Because every face passing the Minimum-Ball condition also belongs to the ordinary Delaunay triangulation (Lemma 3.2), the resulting mesh inherits Delaunay's guarantees of no self-intersections and few thin triangles. Points carry only position, a real value, and optional extra features such as color, so optimizing these continuous quantities alone drives the discrete topology changes observed during reconstruction.","pith_inferences":["The Minimum-Ball condition is a local version of Delaunay's empty-circumsphere property, so the expressible meshes form a subset of ordinary Delaunay meshes; shapes that demand strongly anisotropic or non-Delaunay connectivity may be under-represented no matter how the points are arranged.","The $O(\\log N)$ asymptotics presuppose a true spatial-index query and a bounded candidate count; the paper's timings use a brute-force neighbor scan and a periodically rebuilt triangulation, so the measured speedups and the stated complexity class describe different quantities until the implementation changes.","The Reinforce-Ball procedure in the appendix—stochastic optimization of per-point existence probabilities with a log-derivative gradient—looks like a general template for differentiable mesh simplification that could extend to 3D and to learning connectivity priors.","The reported failure on real-world multi-view images is diagnosed as a rendering-model limitation, so joining the Minimum-Ball tessellation with a photorealistic renderer is the most direct route to practical use."],"forward_implications":["Reconstruction of complex shapes becomes practical at high resolution: DMesh++ reports handling 2D drawings with nearly a million edges and 3D point clouds with hundreds of thousands of points, where DMesh exhausts memory or time.","Tessellation is up to 32 times faster than DMesh in 3D while using up to 75% less GPU memory, so finer meshes fit in the same computational budget.","Because the Minimum-Ball condition selects a subset of Delaunay faces, reconstructed meshes avoid self-intersections and thin triangles without a separate post-processing pass.","Multi-view reconstruction recovers open and closed surfaces, including colored meshes, that can be used directly for downstream applications such as physics simulation.","Discrete topology changes emerge from optimizing continuous per-point features alone, so no explicit connectivity prediction or remeshing operator is needed inside the optimization loop."],"supporting_citations":[{"why":"The DMesh formulation this work extends; its weighted Delaunay tessellation is the baseline whose cost and memory use motivate the Minimum-Ball replacement.","marker":"[42]"},{"why":"Provides the triangulation implementation whose practical linear runtime for weighted Delaunay triangulation is the bottleneck being eliminated.","marker":"[14]"},{"why":"Supplies the Delaunay characterization used in Lemma 3.2 to prove that Minimum-Ball faces are a subset of Delaunay faces.","marker":"[8]"},{"why":"Supplies the nearest-neighbor search routine that the Minimum-Ball algorithm calls for every query face.","marker":"[37]"},{"why":"Compared against in 3D point cloud reconstruction; represents the classical implicit-surface approach the paper's open-surface results are set against.","marker":"[17]"},{"why":"Compared against in 3D point cloud reconstruction; a neural mesh-based approach that serves as the strongest watertight-surface baseline.","marker":"[27]"},{"why":"Compared against in multi-view reconstruction; its closed-surface assumption is the contrast to DMesh++'s open-surface support.","marker":"[39]"},{"why":"Compared against in multi-view reconstruction; its representation of open surfaces via sub-surface extraction is the nearest capability to DMesh++'s.","marker":"[23]"}],"fun_headline_variants":["One ball test makes differentiable meshes 32x faster","DMesh++: ball queries slash mesh learning cost","Minimum-ball rule speeds up complex shape meshing","Faster differentiable meshes with a single distance check","From O(N) to O(log N): DMesh++ complexity win"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claimed logarithmic speedup rests on two premises: that the nearest point to a face's ball center can be found in logarithmic time by an accelerated search structure, and that the number of candidate faces does not grow as the point count grows—yet the reported implementation uses a brute-force neighbor scan and periodically rebuilds candidate faces with a full Delaunay triangulation.","fun_headline_variants_meta":{"raw":{"variants":["One ball test makes differentiable meshes 32x faster","DMesh++: ball queries slash mesh learning cost","Minimum-ball rule speeds up complex shape meshing","Faster differentiable meshes with a single distance check","From O(N) to O(log N): DMesh++ complexity win"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000708,"raw_usage":{"total_tokens":3142,"prompt_tokens":853,"completion_tokens":2289,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":469,"completion_tokens_details":{"reasoning_tokens":2209}},"tokens_in":469,"tokens_out":2289,"duration_ms":16149,"temperature":1.0,"reasoning_tokens":2209,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T10:15:13.878799+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure the wall-clock time of a single tessellation step on random point sets of size $N = 10^3$ through $10^6$, with the brute-force neighbor scan replaced by an exact accelerated search; if per-face query time does not stay near $O(\\log N)$, or if total time scales as $O(N^2)$, the complexity claim fails. Separately, count the candidate faces $|F|$ during a running reconstruction: if $|F|$ grows linearly with $N$, the effective tessellation cost is $O(N \\log N)$, not $O(\\log N)$.","supporting_citations":[{"cited_title":"3D triangulations","cited_arxiv_id":null,"evidence_quote":"Provides the triangulation implementation whose practical linear runtime for weighted Delaunay triangulation is the bottleneck being eliminated."},{"cited_title":"Delaunay mesh generation","cited_arxiv_id":null,"evidence_quote":"Supplies the Delaunay characterization used in Lemma 3.2 to prove that Minimum-Ball faces are a subset of Delaunay faces."},{"cited_title":"Screened poisson sur- face reconstruction","cited_arxiv_id":null,"evidence_quote":"Compared against in 3D point cloud reconstruction; represents the classical implicit-surface approach the paper's open-surface results are set against."},{"cited_title":"Ponq: a neural qem-based mesh representation","cited_arxiv_id":null,"evidence_quote":"Compared against in 3D point cloud reconstruction; a neural mesh-based approach that serves as the strongest watertight-surface baseline."},{"cited_title":"Flexible isosurface extraction for gradient-based mesh optimization","cited_arxiv_id":null,"evidence_quote":"Compared against in multi-view reconstruction; its closed-surface assumption is the contrast to DMesh++'s open-surface support."},{"cited_title":"Ghost on the Shell: An Expressive Representation of General 3D Shapes","cited_arxiv_id":"2310.15168","evidence_quote":"Compared against in multi-view reconstruction; its representation of open surfaces via sub-surface extraction is the nearest capability to DMesh++'s."}],"review_version":1}