A Robust Approach to Detect Intersections between Triangles with Different Numerical Representations

Gianmarco Cherchi; Luca Garau

REVIEW 3 major objections 5 minor 24 references

A Robust Approach to Detect Intersections between Triangles with Different Numerical Representations

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A templated C++ library detects and classifies triangle-triangle intersections under floating-point, rational, and implicit coordinates, and matches a state-of-the-art pipeline in speed and robustness.

desk verdict A genuinely useful templated triangle-triangle intersection library with strong float-mode validation on Thingi10k, but the exhaustive and multi-representation claims are not yet fully supported. read the letter →

arxiv 2507.08478 v1 pith:4XDBSR5B submitted 2025-07-11 cs.CG

Luca Garau , Gianmarco Cherchi This is my paper · ORCID

classification cs.CG MSC 68U0565D18

keywords triangle-triangleintersectionrobustgeometryprocessingexactarithmeticimplicitpointsgeometricpredicatesmesharrangementstemplatedC++librarycollisiondetection

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper presents a header-only, templated C++ library for detecting and classifying intersections between two triangles. The tool works with three numerical representations for coordinates—floating-point, rational numbers, and implicit points—and is designed to be dropped into existing mesh processing pipelines. The authors claim the algorithm is exhaustive, covering the full range of intersection configurations including coplanar overlaps, and they demonstrate that its detection speed is essentially identical to a state-of-the-art mesh arrangement pipeline on the Thingi10k dataset. The value of the work is a reusable, representation-agnostic intersection module that removes the usual coupling between intersection detection and a specific numeric type or data structure.

What carries the argument

The central mechanism is the simplex-based enumeration of intersection types powered by Shewchuk's exact geometric predicates (Orient2D and Orient3D), which determine whether a query point lies on one side or on the line or plane defined by other points. The tool wraps these predicates in C++ templates, so any numerical representation that implements these predicates—including the built-in floating-point, CGAL rational numbers, and implicit points—can be used without changing the detection logic. The other load-bearing rule is the coplanar segment-linking rule, which connects any two detected intersection points that lie on the same input edge, producing the intersection segments and polygonal output that arrangement algorithms require.

What would settle it

Construct two coplanar triangles in a degenerate configuration such that the true intersection polygon cannot be recovered by pairing the recorded intersection points that share a single input edge, for example a case where two overlapping edges produce a segment whose endpoints do not both appear among the listed point intersections. If the tool outputs fewer or different segments than the actual polygonal overlap, the exhaustive claim fails.

Watch

Extended reading notes

Core claim

The central claim is that all triangle-triangle intersections can be identified and classified by decomposing each triangle into lower-dimensional simplexes (vertices, edges, and area) and applying the robust Orient2D and Orient3D geometric predicates to those simplexes, regardless of the coordinate representation. The algorithm enumerates five intersection types—coincident points, point in segment, point in triangle, segment crossing segment, and segment crossing triangle—and then forms intersection segments by linking any two intersection points that lie on a common input edge. For coplanar triangles this yields up to six intersection points and up to a six-sided intersection polygon, while non-coplanar triangles yield at most two points and one segment. The output is a list of point tuples (type, simplex ids) and edge-linked segments, which downstream code can turn into actual point coordinates in any chosen representation. The authors state that the tool has been demonstrated to be equally fast and robust as a state-of-the-art algorithm, while being far easier to integrate and extend.

Load-bearing premise

The algorithm assumes that the five listed intersection types plus the coplanar rule linking points on a common input edge cover every possible configuration of two triangles, including degenerate coplanar and collinear cases, with no proof of completeness provided.

Editorial extensions

If this is right

Mesh arrangement and boolean pipelines can replace their hard-coded detection modules with a single templated function that accepts any supported numeric type.
The representation-agnostic output lets downstream code construct intersection points exactly as floating-point approximations, exact rationals, or implicit points, without changing the detection flow.
Adding a new numerical representation requires only implementing Orient2D and Orient3D for that type, making the library extensible to arbitrary-precision or other exact arithmetic.
The Thingi10k validation, covering 9996 models with up to 1.8 million intersection points, indicates that the generic templated approach does not sacrifice runtime performance compared to a specialized implementation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The exhaustiveness claim is only as strong as the completeness of the five-type simplex enumeration; a formal proof or a fuzz test over degenerate configurations (identical triangles, overlapping edges, vertex-on-edge) would settle it beyond the floating-point tests reported.
Since the same detection logic runs on all three numeric representations, the library could be used as an experimental testbed to measure how reliably exact rational and implicit coordinate representations preserve arrangement topology compared to floats.
A direct stress test mixing degenerate configurations into the rational and implicit modes would exercise the exhaustive claim more thoroughly than the current all-floating-point validation, which never engages the alternative representations.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The useful thing here is the library design: a header-only C++ template that runs the same intersection classification logic over float, rational, and implicit-point representations by swapping the Orient2D/Orient3D predicates. That is genuinely new relative to the cited alternatives, which are single-representation and deeply coupled to their host pipelines. The empirical validation for the float path is also solid: 9,996 Thingi10k models, identical intersection lists and arrangement topology compared with CLSA20, and comparable timings. That is real evidence and the strongest part of the paper.

The soft spots are in proportion to the claims. First, Algorithm 1's 'exhaustive' classification has no completeness argument. The five-case simplex enumeration and the coplanar rule that links intersection points sharing an input edge are plausible, but the paper does not prove that every degenerate configuration (coincident vertices, overlapping edges, multiple points on one edge) is handled. A missed configuration would break the central claim. Second, the rational and implicit instantiations are never executed. The conclusion says the tool 'has been demonstrated to be equally fast and robust' for all three representations, but the experiments only exercise floating point. That is overreach as written. Third, the repository is a placeholder ('LINK'), so nobody can independently check the code right now.

None of these are fatal. The float-mode evidence is strong enough that the basic approach works. The missing pieces are a correctness argument for the enumeration (or at least a rigorous case analysis), actual benchmarks for rational and implicit modes, and a real repository link. The baseline comparison is a previous paper co-authored by Cherchi, but the results are transparent and the timings are close, so I do not see self-citation as a problem.

This paper deserves a serious referee. The engineering contribution is real and would be useful to people building mesh arrangements, booleans, or CSG tools. I would engage with it after those revisions; right now I would not cite it as a verified tool, but I would follow it.

Referee Report

3 major / 5 minor

Summary. The paper presents a header-only C++ templated library for detecting and classifying intersections between two triangles, intended to work with floating-point, rational, and implicit numerical representations. The core Algorithm 1 decomposes the problem into lower-dimensional simplex tests (vertices, edges, faces) using Orient2D and Orient3D predicates, and outputs lists of intersection points and segments. The validation replaces the detection module in the state-of-the-art mesh arrangement pipeline of [CLSA20] and reports that on 9,996 Thingi10k models the tool produces exactly the same intersection lists and final arrangement topology as the reference, with comparable execution times. The paper claims that the tool is versatile, exhaustive, easy to integrate, and open source, and it is positioned as a practical implementation of the authors' earlier workshop paper [GSC25].

Significance. If the central claims hold, the tool would be a useful, representation-agnostic drop-in module for mesh arrangement, Boolean, and repairing pipelines, and the templated predicate-based design is a sensible way to support multiple numerical representations. The empirical protocol for the floating-point mode is a strength: agreement with [CLSA20] on thousands of Thingi10k models is a strong sanity check, and the reported timings are comparable. However, the significance is currently limited because the central 'versatile and exhaustive' claim is not backed by evidence for the rational and implicit instantiations, which are never executed or benchmarked, and the exhaustiveness of the case enumeration in Algorithm 1 is not proven for degenerate configurations. The manuscript also does not provide a working repository link, so the main artifact cannot be independently verified.

major comments (3)

[Section 3, Algorithm 1 and Figure 3] The central claim of exhaustiveness is not supported by a completeness argument. The five intersection types and the vertex-edge-face enumeration in Algorithm 1 may cover generic transverse and coplanar configurations, but no proof or case analysis is given for degeneracies such as coincident vertices, overlapping edges, or more than two intersection points lying on a single input edge. In particular, the coplanar branch (Algorithm 1, lines 35-40) links any two intersection points on a common input edge, but it is not established that this rule recovers exactly the boundary of the overlap polygon in degenerate cases, nor that it avoids redundant or inconsistent segments. This is load-bearing because the abstract and conclusion explicitly claim an 'exhaustive' algorithm; please add a completeness proof or a systematic case analysis, or narrow the claim to non-degenerate configurations.
[Section 4, Validation] The experiments exercise only the floating-point instantiation of the tool. Although the templated design may in principle support rational and implicit representations, no tests, correctness checks, or benchmarks are provided for those modes, and the paper does not report whether the rational and implicit code paths are even compiled and executed in the validation. Consequently, the abstract's claim that the tool works with rational or implicit representations, and the conclusion's statement that the tool has been 'demonstrated to be equally fast and robust', are not supported by the evidence presented. Please add at least unit tests and representative benchmarks for the rational and implicit instantiations, or revise the claims to describe the floating-point mode only.
[Abstract and Section 5 (repository availability)] The paper's main deliverable is the open-source library, but the repository is referenced only as 'Repository LINK' and 'LINK', with no actual URL or version identifier. This makes the central artifact unverifiable and prevents an independent check of the claimed support for multiple numerical representations, the predicate interface, and the integration procedure. Please provide the actual public repository URL and, if possible, a commit hash or version number so that the results can be reproduced.

minor comments (5)

[Section 3, Algorithm 1] The pseudocode does not specify how duplicate intersection records are handled when a vertex is simultaneously a coincident vertex, lies on an edge, and lies on the area of the other triangle; please clarify whether each geometric point is reported once or once per generating simplex pair.
[Figure 4] The output labels such as '10EB_CROSS_TAP0' and '11EA_CROSS_EBP1' are not explained in the text; please define the naming convention used for the intersection type and simplex identifiers.
[Section 2 and Section 4] Typographical and formatting issues: 'Shewchuck' should be 'Shewchuk' in the introduction, the curly apostrophe in 'Ours’ time' in Table 1 is inconsistent, and the reference [LV25] is described as a preprint without a stable identifier; please correct these.
[Section 3] The sentence stating that coplanar triangles can have up to six intersection points 'excluding case (5)' is clear, but the relationship between the five cases in Figure 3 and the possible output tuples could be stated more explicitly, especially for case (5) in non-coplanar intersections.
[Section 5] The conclusion says the tool has no dependencies on data structures or algorithms specific to implementations, yet the code relies on cinolib and the Shewchuk predicate library; please clarify that the dependency is on generic predicate interfaces rather than on a particular pipeline.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: the central claim is supported by an explicit algorithm and external empirical comparison, though self-citations and an unproven enumeration limit the strength of the exhaustiveness claim.

full rationale

The paper's derivation chain is not circular. Algorithm 1 provides an explicit, implementable enumeration of vertex-edge-face simplex intersections, and the correctness of the geometric tests is delegated to Shewchuk's Orient2D and Orient3D predicates, which are external to the present contribution. The validation compares the tool's output against the public CLSA20 arrangement pipeline on Thingi10k meshes; while CLSA20 is co-authored by one of the present authors, and while the paper transparently states that 'This work represents a practical implementation of a problem discussed in [GSC25]', these self-citations are not the load-bearing justification for the results. No parameter is fitted, no quantity is defined in terms of the target claim, and no uniqueness theorem is imported from the authors' prior work. The main limitations are non-circular: the completeness of the five-case intersection enumeration and the coplanar segment-linking rule is asserted rather than proven, and the rational and implicit numerical instantiations are not empirically exercised in the reported experiments. These are correctness and validation gaps, not circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new geometric entity. The LPI (line-plane intersection) points used for implicit representation are from [Att20], not new to this work. No free parameters were fit to data; the method has no hand-tuned thresholds or fitted constants.

assumptions (4)

domain assumption Shewchuk's Orient2D and Orient3D predicates return the exact sign of the underlying determinant for all well-defined inputs.
The whole detection logic in Section 3 dispatches on the signs of these predicates; if they were inexact for some representation, the classification would fail. Predicates from [RS97] are external and widely tested.
domain assumption Attene's indirect predicates give correct orientation results for implicitly represented points.
The implicit-point mode (Section 3) relies on the indirect predicate framework [Att20]; no validation of this mode is included in the paper.
ad hoc to paper The five intersection types in Figure 3, together with the vertex-edge-face enumeration in Algorithm 1, exhaust all possible configurations of two triangles, including coplanar and degenerate ones.
Algorithm 1 loops over simplex pairs and then links coplanar points that share an input edge (lines 35-40); no proof of completeness is given, so this assumption is intrinsic to the paper's claim of being exhaustive.
domain assumption CGAL rational arithmetic provides exact coordinates in the rational mode.
The rational path (Section 3) depends on CGAL number types [The24] being exact, which is a standard property of the library.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Robust Approach to Detect Intersections between Triangles with Different Numerical Representations." pith.science (2026). https://pith.science/paper/4XDBSR5B

@misc{pith2026250708478,
  author       = {Pith},
  title        = {Pith review of: A Robust Approach to Detect Intersections between Triangles with Different Numerical Representations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4XDBSR5B}},
  note         = {Machine review of arXiv:2507.08478}
}

read the original abstract

The detection and classification of intersections between triangles are crucial tasks in a wide range of applications within Computer Graphics and Geometry Processing, including mesh Arrangements, mesh Booleans, and generic mesh processing and fixing tasks. Existing methods are hard-coded and deeply integrated into specific algorithms, and significant efforts are usually required to integrate them into new pipelines or to extend them to different numerical representations. This paper presents a versatile and exhaustive algorithm to identify and classify intersections between triangles with either floating points, rational numbers, or implicit representations. The proposed tool is implemented as a C++ templated and header-only code that is generic and easy to integrate into further algorithms requiring the triangle-triangle intersection detection step. The developed tool has been tested and compared with a state-of-the-art approach, and it is shared with the Geometry Processing community with an Open Source license.

Figures

Figures reproduced from arXiv: 2507.08478 by the authors.

**Figure 2.** Decomposition of an intersection between [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** All possible cases of intersections between two triangle sub-simplexes. Output Intersection Points P0 EB_CROSS_TA 0 -1 P1 EA_CROSS_EB 1 1 Intersection Edges P0 P1 V2 A B V0 V1 P0 V0 V1 V2 P1 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: An example of an intersection between two [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

**Figure 6.** Figure 6: In this bar chart, we can see the models taken [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages

[1]

Polygon mesh repairing: An application perspective

Marco Attene, Marcel Campen, and Leif Kobbelt. Polygon mesh repairing: An application perspective. ACM Comput. Surv. , 45(2), March 2013

work page 2013
[2]

Indirect predicates for geometric constructions

Marco Attene. Indirect predicates for geometric constructions. Computer-Aided Design , 126:102856, 2020

work page 2020
[3]

Cork boolean library, 2013

Gilbert Bernstein. Cork boolean library, 2013

work page 2013
[4]

Fast and robust mesh arrangements using floating-point arithmetic

Gianmarco Cherchi, Marco Livesu, Riccardo Scateni, and Marco Attene. Fast and robust mesh arrangements using floating-point arithmetic. ACM Trans. Graph. , 39(6):1--16, 2020

work page 2020
[5]

Interactive and robust mesh booleans

Gianmarco Cherchi, Fabio Pellacini, Marco Attene, and Marco Livesu. Interactive and robust mesh booleans. ACM Trans. Graph. , 41(6), 2022

work page 2022
[6]

A collision detection algorithm based on sphere and ebb mixed hierarchical bounding boxes

Lei Dong, Yikai Xiao, Yanfeng Li, and Ruimin Shi. A collision detection algorithm based on sphere and ebb mixed hierarchical bounding boxes. IEEE Access , 12:62719--62729, 2024

work page 2024
[7]

Real-time collision detection

Christer Ericson. Real-time collision detection . Crc Press, 2004

work page 2004
[8]

Fast and robust triangle-triangle overlap test using orientation predicates

Philippe Guigue and Olivier Devillers. Fast and robust triangle-triangle overlap test using orientation predicates. Journal of Graphics Tools , 8(1):25--32, 2003

work page 2003

Show all 24 references

[9]

Exact and efficient intersection resolution for mesh arrangements

Jia-Peng Guo and Xiao-Ming Fu. Exact and efficient intersection resolution for mesh arrangements. ACM Trans. Graph. , 43(6), November 2024

2024
[10]

Triangle-triangle intersections with different numerical representations

Luca Garau, Riccardo Scateni, and Gianmarco Cherchi. Triangle-triangle intersections with different numerical representations. In 2025 IEEE Conference on Virtual Reality and 3D User Interfaces Abstracts and Workshops (VRW) , pages 401--404, 2025

2025
[11]

Erit—a collection of efficient and reliable intersection tests

Martin Held. Erit—a collection of efficient and reliable intersection tests. Journal of Graphics Tools , 2(4):25--44, 1997

1997
[12]

Robust inside-outside segmentation using generalized winding numbers

Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung. Robust inside-outside segmentation using generalized winding numbers. ACM Trans. Graph. , 32:1 -- 12, 2013

2013
[13]

Livesu, G

M. Livesu, G. Cherchi, R. Scateni, and M. Attene. Deterministic Linear Time Constrained Triangulation using Simplified Earcutfig . IEEE Transactions on Visualization and Computer Graphics , 28(12):5172--5177, 2021

2021
[14]

cinolib: a generic programming header only c++ library for processing polygonal and polyhedral meshes

Marco Livesu. cinolib: a generic programming header only c++ library for processing polygonal and polyhedral meshes. Transactions on Computational Science XXXIV , 2019. https://github.com/mlivesu/cinolib/

2019
[15]

Removing self-intersections in 3D meshes while preserving floating-point coordinates

Sylvain Lazard and Leo Valque. Removing self-intersections in 3D meshes while preserving floating-point coordinates . working paper or preprint, January 2025

2025
[16]

A faster triangle-to-triangle intersection test algorithm

Wei Ling-yu. A faster triangle-to-triangle intersection test algorithm. Comput. Animat. Virtual Worlds , 25(5–6):553–559, September 2014

2014
[17]

Exact predicates, exact constructions and combinatorics for mesh csg

Bruno Lévy. Exact predicates, exact constructions and combinatorics for mesh csg. arXiv , 2024

2024
[18]

A fast triangle-triangle intersection test

Tomas M \"o ller. A fast triangle-triangle intersection test. Journal of Graphics Tools , 2(2):25--30, 1997

1997
[19]

Adaptive precision floating-point arithmetic and fast robust geometric predicates

Jonathan Richard Shewchuk. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry , 18:305--363, 1997

1997
[20]

A brief survey of clipping and intersection algorithms with a list of references (including triangle-triangle intersections)

Vaclav Skala. A brief survey of clipping and intersection algorithms with a list of references (including triangle-triangle intersections). Informatica , 34(1):169--198, 2023

2023
[21]

CGAL User and Reference Manual

The CGAL Project . CGAL User and Reference Manual . CGAL Editorial Board , 6.0.1 edition, 2024

2024
[22]

Ember: exact mesh booleans via efficient & robust local arrangements

Philip Trettner, Julius Nehring-Wirxel, and Leif Kobbelt. Ember: exact mesh booleans via efficient & robust local arrangements. ACM Trans. Graph. , 41(4), July 2022

2022
[23]

Mesh arrangements for solid geometry

Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. Mesh arrangements for solid geometry. ACM Trans. Graph. , 35(4):1--15, 2016

2016
[24]

Thingi10k: A dataset of 10,000 3d-printing models

Qingnan Zhou and Alec Jacobson. Thingi10k: A dataset of 10,000 3d-printing models. arXiv preprint arXiv:1605.04797 , 2016

2016 arXiv

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Polygon mesh repairing: An application perspective

Marco Attene, Marcel Campen, and Leif Kobbelt. Polygon mesh repairing: An application perspective. ACM Comput. Surv. , 45(2), March 2013

work page 2013

[2] [2]

Indirect predicates for geometric constructions

Marco Attene. Indirect predicates for geometric constructions. Computer-Aided Design , 126:102856, 2020

work page 2020

[3] [3]

Cork boolean library, 2013

Gilbert Bernstein. Cork boolean library, 2013

work page 2013

[4] [4]

Fast and robust mesh arrangements using floating-point arithmetic

Gianmarco Cherchi, Marco Livesu, Riccardo Scateni, and Marco Attene. Fast and robust mesh arrangements using floating-point arithmetic. ACM Trans. Graph. , 39(6):1--16, 2020

work page 2020

[5] [5]

Interactive and robust mesh booleans

Gianmarco Cherchi, Fabio Pellacini, Marco Attene, and Marco Livesu. Interactive and robust mesh booleans. ACM Trans. Graph. , 41(6), 2022

work page 2022

[6] [6]

A collision detection algorithm based on sphere and ebb mixed hierarchical bounding boxes

Lei Dong, Yikai Xiao, Yanfeng Li, and Ruimin Shi. A collision detection algorithm based on sphere and ebb mixed hierarchical bounding boxes. IEEE Access , 12:62719--62729, 2024

work page 2024

[7] [7]

Real-time collision detection

Christer Ericson. Real-time collision detection . Crc Press, 2004

work page 2004

[8] [8]

Fast and robust triangle-triangle overlap test using orientation predicates

Philippe Guigue and Olivier Devillers. Fast and robust triangle-triangle overlap test using orientation predicates. Journal of Graphics Tools , 8(1):25--32, 2003

work page 2003