<figure><img src="image_1.png" /></figure>

HAL
open science

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

Léo Valque, Sylvain Lazard

► To cite this version:

Léo Valque, Sylvain Lazard. Resolving self-intersections in 3D meshes while preserving floating-point coordinates. Computer Graphics Forum, 2025, 44 (5), pp.e70197. 10.1111/cgf.70197. hal-05242294

HAL Id: hal-05242294

https://hal.science/hal-05242294v1

Submitted on 5 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Resolving self-intersections in 3D meshes while preserving floating-point coordinates

Leo Valque, Sylvain Lazard

SUBMISSION ID FP2-1012

<figure><img src="image_3.png" /><figcaption>Figure 1: We present a new method for robustly resolving the mesh intersection problem, focusing on the conversion of the vertices coordinates from their exact mathematical values to doubles. We can process all the 4524 models in Thingi10K [ZJ16] that contain self-intersections; the figure shows the famously difficult model referenced as number 996816, which contains about 76k vertices, 171k triangles, 25 million pairs and triplets of intersecting triangles (shown in red), and whose mathematically exact intersection-free representation contains about 30 million vertices and 240 million faces. We resolve the intersections in 38 seconds on this model. The output model contains about 100k vertices and 245k faces, with all coordinates in doubles with a relative error of at most 3·10⁻⁵.</figcaption></figure>

## Abstract

We present a straightforward and robust method for resolving the mesh intersection problem. We focus specifically on the challenge caused by the intersections resulting from the conversion of the vertices coordinates from their exact mathematical values to a fixed-precision floating-point format. Our method takes as input a soup of triangles and outputs intersection-free models whose vertices coordinates are all represented with double-precision floating-point format. We evaluated our approach thoroughly, considering a large collection of meshes. In particular, we can process all the 4524 models in Thingi10K [ZJ16] that contain self-intersections. This outperforms previous state-of-the-art approaches: On the 527 models of Thingi10K for which naive rounding fails, Zhou et al.'s approach [ZGZJ16] is capable of handling 91% of them, and Valque's 94% [Val24]. In terms of time efficiency, our approach handles about 50k vertices per second on average, which is faster to that of Zhou et al. by a factor 1.4 on these non-trivial models and is faster than that of Valque by several order of magnitude. (see https://www.acm.org/publications/class-2012)

## CCS Concepts

* *Computing methodologies* → *Model development and analysis; Mesh models; Theory of computation* → *Computational geometry*;
# 1. Introduction

In computer science, many software pipelines rely on clean, well-structured 3D meshes and, in particular, meshes without self-intersections. However, 3D meshes are very often not clean: for instance, about half of the 10 000 “real-world” meshes from the popular Thingi10K repository [ZJ16] contain self-intersections. A standard and natural approach to solving that issue is to compute the mathematically exact self-intersections and subdivide the faces accordingly. However, most software dealing with polygonal objects requires input vertices whose coordinates have single- or double-precision floating-point format (referred to as float or double). The coordinates of the vertices resulting from the intersections thus need to be rounded from their exact mathematical values to fixed-precision floating-point representations. We refer to this approach as naive rounding.

Surprisingly, naive rounding often fails in the sense that the rounding of the coordinates induces new self-intersections between the faces. For instance, out of the 4 524 models in Thingi10K that contain self-intersections, naive rounding fails on 527 models, that is in about 12% of these models. It should be stressed that, in theory, it is unknown whether iterating the naive rounding scheme always terminates and, in practice, iterating for at most one hour fails fairly often, namely, on about half (273) of these 527 models.

When addressing the long-lasting challenge of robustly handling mesh intersections, a common weakness in all robust methods that compute mathematically exact intersection vertices is the conversion, or rounding, of their exact coordinates to fixed-precision floating-point format; see e.g. [Att14, ZGZJ16, CLSA20, Att20, DA21, CPAL22, TNWK22, Liv24, Lév24, GF24]. As mentioned by Cherchi et al. [CPAL22]: “Solving the snap rounding problem is the ultimate solution for all these issues, but this is a remarkably difficult problem”.

To the best of our knowledge, only two (non-trivial) practical approaches have been proposed for handling this challenge. Zhou et al. [ZGZJ16] proposed a simple heuristic which is capable of handling 91% of the 527 non-trivial models of Thingi10K, i.e., those for which the naive rounding fails. Very recently, Valque [Val24] proposed a practical algorithm, which handles 94% of these non-trivial models. This algorithm also provides some topological guarantees but its implementation is difficult and it is several order of magnitude slower than that of Zhou et al. [ZGZJ16].

Building on the work of Zhou et al. [ZGZJ16], we propose a remarkably simple heuristic for resolving self-intersections in a soup of triangles, which we extensively tested and found to produce near-perfect results: our method handles successfully all Thingi10K models, although on the one famous instance shown in Fig. 1, we had to use a coarser-than-default rounding. We also successfully tested our approach on an ad-hoc challenging instance consisting of the Boolean intersection of randomly rotated unit cubes (see Fig. 2). In terms of time efficiency, our approach handles about 50k vertices per second on average in a serial implementation, achieving a relative precision on the coordinates of the vertices of at least $2 \cdot 10^{-7}$ for all Thingi10K models, except the one in Fig. 1.

The strength of our method lies in its impressive effectiveness

<figure><img src="image_4.png" /><figcaption>Figure 2: Boolean intersections of 1000 randomly rotated unit cubes, all centered at the origin. The resulting model approximates the sphere inscribed in the cubes, with complex shapes on its surface.</figcaption></figure>

achieved with a remarkably simple approach. However, we emphasize that it is carefully crafted and all the minor variations we have experimented with do not perform as well.

We first review the state of the art in Section 2. We then present our heuristic in Section 3, our experiments in Section 4 and give some insight into its effectiveness in Section 5, before concluding in Section 6.

# 2. State of the art

Many approaches have been proposed in the literature for computing intersections between meshes, particularly in applications such as Boolean operations, mesh arrangements, and mesh repair. As mentioned earlier, most robust methods rely on computing exact rational coordinates at some stage, which can introduce new intersections when rounded to fixed-precision floating-point format.

A solution for computing an intersection-free mesh is close to the input while preserving floating-point coordinates is remeshing. However, remeshing completely alters the mesh, which is not always desirable. Additionally, these techniques typically achieve only moderate relative precision, around $10^{-3}$. The remeshing literature is vast and we refer to the following works and references therein [Ju04, HZG*18, HSW*20, WSH*20, ZGP*24, CPLW19].

We focus here on the problem of resolving the self-intersections in triangle meshes while preserving floating-point coordinates, without fully remeshing the models.

With the notable exception of the work by Zhou et al. [ZGZJ16] described below, all previous approaches start by computing the mathematically exact self-intersections in the 3D mesh and subdividing the faces accordingly, before approximating the coordinates of the vertices. Furthermore, most solutions round the coordinates onto a fixed uniform grid, usually considered to be the integer grid up to a change of scale. This problem is often referred to as *snap rounding* in the computational geometry community.

In the nineties, Milenkovic [Mil90] and Goodrich et al.
<figure><img src="image_5.png" /><figcaption>Figure 3: Counter-example to Goodrich et al.’s scheme [GGHT97]: $A = (1, \epsilon, 1)$, $B = (6+\epsilon, 6+\epsilon, 4)$, $C = (\epsilon, 1, 0.8)$, $D = (6+\epsilon, 6+3\epsilon, 4+\epsilon)$ with $0 < \epsilon \ll 1$.</figcaption></figure>

[GGHT97] proposed two schemes that were later proved to be flawed by Fortune [For99]. We present in Fig. 3 a counter-example to Goodrich et al.’s scheme, which highlights some difficulties of the problem: it shows two segments whose distance is realized by their endpoints (B and D) and whose projections on each of the three axis-parallel planes do not intersect, while they intersect after rounding their vertices to the centers of their grid cells; by construction, it does not help to subdivide the segments in the grid cells that realize their distance, or at the points where they intersect in projection on the axis-parallel planes.

Fortune [For99] later proposed a rounding algorithm whose grid precision depends on the number of input triangles and which is thus not usable for rounding the coordinates on a grid of fixed precision.

Zhou et al. [ZGZJ16] were the first to propose an efficient practical scheme that goes beyond naive rounding. Their approach consists in (i) identifying all pairs of properly intersecting triangles (without explicitly computing their intersections), (ii) rounding the coordinates of their vertices to floats, (iii) computing all the intersections between the triangles and subdividing them accordingly, (iv) rounding all new vertices to doubles, and (v) iterating at most 20 times or until no proper intersections remain.

Zhou et al. designed their scheme for computing Boolean operations and they only considered models that consist of possibly (self-)overlapping components that bound solids. However, their approach can be applied to any model when replacing the Boolean operations with a computation of mesh self-intersections. Zhou et al. [ZGZJ16] successfully computed intersection-free Boolean self-unions for all but five of the 3413 self-intersecting models from Thingi10K that met their criteria. For computing mesh self-intersections, our experiments show that on the 527 non-trivial models of Thingi10K [ZJ16] mentioned above, their approach fails on about 9% of them (48 instances), stopping each trial after 10 hours of computation.

Milenkovic and Sacks [MS19] proposed an algorithm involving iterative linear programming to increase the minimum distance between features (vertex/face and edge/edge pairs) and a post-processing using gradient descent to minimize vertex drift while maintaining feature separation. While no intersection can occur during rounding, the drawback of their approach is that vertices can be rounded arbitrarily far. They show that the vertex drift remains

small in practice but their tests were mainly conducted on custom examples and not on a large data base including difficult models, making comparisons with other methods difficult.

Devillers et al. [DLL20] presented the first 3D snap rounding algorithm, which outputs a set of triangles with integer coordinates such that the Hausdorff distance between the input and the output is at most $\frac{3}{2}$ and the topology is preserved “up to collapse”. However, the complexity of their algorithm is, in practice, too large to be usable on “real-life” models [Val19].

Building on this work, Valque [Val24] proposed a practical algorithm that offers the same guarantees. Their implementation fails relatively often, that is on about 35% (187 instances) of the non-trivial models of Thingi10K. However, by relaxing some topological guarantees, their failure rate drops to about 6% (33 instances), slightly outperforming the heuristic of Zhou et al. [ZGZJ16]. Nevertheless, Valque’s algorithm is much more challenging to implement and slower by two orders of magnitude than Zhou et al.’s heuristic.

### 3. Our approach

Our heuristic for resolving self-intersections in a soup of triangles while preserving coordinates in floating-point format is, in essence, as follows.

(i) Identify all pairs of properly intersecting triangles (without explicitly computing their intersections),

(ii) round their vertices to the centers of their respective cells in a uniform grid of suitable coarseness (see below),

(iii) also round all vertices that are located in these cells.

(iv) Compute all the intersections between the triangles, using exact arithmetics, and subdivide them accordingly.

(v) Round all new vertices to doubles.

(vi) Iterate at most 5 times or until no proper intersections remain.

When the input coordinates are given as doubles, the default uniform grid we use in Steps (ii) and (iii) is essentially the finest possible uniform grid on which the rounded coordinates of all the vertices are exactly representable as floats. Precisely, for each axis, we consider a scaling by a power of two such that the largest absolute value of all the vertices coordinates lies within $[2^{23}, 2^{24})$, which is the largest scaling so that the integral part of every possible coordinate is representable as float; the rounding of a coordinate then amounts to applying this scaling, rounding to the closest integer and applying the reverse scaling.

Thus, in more details, our heuristic is as follows:

(i') Compute (tight) upper bounds $2^{m_x}, 2^{m_y}, 2^{m_z}$ on the absolute values of the x-, y- and z-coordinates, respectively, of all vertices. Let $\mathcal{G}$ be the grid, centered at the origin, with spacing $2^{-24+m_x}, 2^{-24+m_y}$, and $2^{-24+m_z}$ along the x-, y-, and z-axes, respectively, and bounded by $\pm 2^{m_x}, \pm 2^{m_y}$, and $\pm 2^{m_z}$ on each axis.

(ii') Identify all pairs of properly intersecting triangles (without explicitly computing their intersections). Let $\mathcal{V}$ be the set of their vertices.

(iii') Add to $\mathcal{V}$ all vertices lying in the cells of $\mathcal{G}$ that contain at least one vertex from $\mathcal{V}$.

(iv') Round every vertex $v$ of $\mathcal{V}$ to the center of its cell in $\mathcal{G}$. In other words, multiply the x-, y- and z-coordinates of $v$ by
$2^{24-m_x}, 2^{24-m_y}, 2^{24-m_z}$, respectively. Round the resulting values to the nearest integers, and scale them back by multiplying them by $2^{-24+m_x}, 2^{-24+m_y}$ and $2^{-24+m_z}$.

(v') Compute the intersections between all triangles, using exact arithmetics, and subdivide them accordingly.

(vi') Round the coordinates of the new vertices to doubles.

(vii') Iterate at most 5 times Steps (ii') to (vi') or until no proper intersections remain.

The rounding in Step (iv') induces a relative error of at most
half of $2^{-24}$ ($\approx 3 \cdot 10^{-8}$), which induces a Hausdorff distance be-
tween the input and output of at most this relative error times the
maximum absolute value of the coordinates times the number of
iterations in our scheme.

It is worth emphasizing that our default choice of the constant 24 in Steps (i') and (iv') is entirely arbitrary. As mentioned above, it corresponds the finest uniform grid for which all rounded coordinates are exactly representable as floats. However, some other constant can be used. Choosing a smaller constant results in a coarser grid $G$ for rounding the vertices in Step (iv'). This may naturally increase the Hausdorff distance between the input and output. It may also collapse very small triangles into points and, ultimately, very small constants will generate very approximated meshes. For example, the instance shown in Fig. 1 consists of approximately 171 thousand input triangles, but the exact arrangement resulting from self-intersections contains about 240 million faces. To make our scheme work in this case, we used a constant 14 instead of 24, which reduced the number of faces to only 245 thousand in the rounded output, while keeping the Hausdorff distance between the input and output below $3.1 \cdot 10^{-3}$ (see Section 4.5 for details). As mentioned previously, this instance is the only one in Thingi10k that requires a constant smaller than the default.

We provide, in Section 5, insights into the effectiveness and dif-
ferences between the heuristics of Zhou et al. [ZGZJ16] and ours.
However, we begin by presenting our experiments in Section 4.

4. Experiments

In this section, we present experiments on our heuristic and, for
comparison, on naive rounding, iterative naive rounding, and Zhou
et al.'s heuristic [ZGZJ16]. We do not provide a detailed compari-
son between our heuristic and Valque's algorithm [Val24] because
the latter is challenging to implement and its reported running time
(processing about 100 vertices per second on average) is about two
orders of magnitude slower than ours, with a lower success rate.

Most of our experiments are conducted on the Thingi10K dataset [ZJ16] of 10 000 meshes, which were created using objects from the model-sharing website for 3D printing called Thingiverse (https://www.thingiverse.com). This dataset reflects the variety, complexity, and quality (or lack thereof) of 3D models. Three models in Thingi10K are unreadable and were excluded from our tests (these models are referenced as 49 911, 81 313, and 77 942). Of the remaining models, 4 524 exhibit self-intersections and were the primary focus of our experiments. We present in Figure 4 and Table 1 results on 10 pertinent models of various sizes from Thingi10K.

We present our experimental setup in Section 4.1. We analyze the

success rates of the considered heuristics on the Thingi10K models
in Section 4.2, their running times in Section 4.3, and their output
sizes in Section 4.4.

The famously difficult model of Thingi10K shown in Fig. 1 is discussed separately, in Section 4.5, because it requires a coarser-than-default grid and because the size of the arrangement obtained by computing all self-intersections in the input model is off the charts, with its approximately 240 million faces. In Section 4.6, we consider a challenging ad hoc experiment involving the Boolean intersections of many randomly rotated cubes. We finally give a summary of these experiments in Section 4.7.

**4.1. Experimental setup**

Our experiments were performed on a cluster using CPUs Intel
Xeon CPU E5-1650 v4 @3.60GHz with 6 cores.

We consider an experiment failed or unfinished for a model if
the last rounded version still presents self-intersections, or if the
implementation does not terminate in less than the time limit.

In all experiments, we resolve self-intersections using CGAL li-
brary [CGA]. We use exact arithmetic for the predicates to ensure
correct results in the intersection tests; this ensures that when the
heuristics terminate within the bound on the number of iterations
and the time limit, the output is certified to be intersection free.
We also use exact arithmetic for the construction of intersection-
induced vertices to control the maximum distance between the in-
put and the output. This is achieved using the CGAL EPECK kernel
(Exact Predicates Exact Construction Kernel) [CGA]. (Note that
one can also use the exact predicates but inexact constructions ker-
nel -EPICK- to achieve a certified output with faster runtime but
less control on the input-output distance.)

For fair comparisons, we did our own implementation of all
schemes. In particular, we use the same implementation for com-
puting self-intersections, which is the most time-consuming step
in all heuristics. These intersections are computed using the au-
torefine function of the Polygon Mesh Processing CGAL pack-
age [CLK*24].

4.2. Success rates

**Naive rounding and iterative naive rounding.** Recall that the naive rounding consists in computing self-intersections and rounding the newly created vertices to doubles. As already mentioned in the introduction, out of the 4 524 models in Thingi10K that contain self-intersections, the naive rounding fails on 527 models ($\approx 12\%$). We focus most of the following experiments on these models, which we refer to as the *non-trivial models* of Thingi10K.

Iterating the naive rounding improves the success rate but about
half (273 of the 527 models) still exhibit self-intersections after one
hour of computation (each). Interestingly, 237 of these models had
more intersections in the last iteration than initially.

**Zhou et al.'s heuristic.** Recall that Zhou et al. [ZGZJ16] applied their heuristic only to models that bound solids (PWN models) for computing Boolean operations. In our experiments, we tested
<figure><img src="image_6.png" /><figcaption>Figure 4: Ten pertinent meshes from Thingi10K [ZJ16], we considered for the experiments in Table 1.</figcaption></figure>

<table><caption>Table 1: Experiments on 10 pertinent examples of various sizes from Thingi10K: two for which the iterative naive rounding terminates, three more on which Zhou et al.'s approach [ZGZJ16] terminates, and five for which they do not. Input V., Out. V and Arr. V refer, respectively, to the input and output number of vertices and to the number of vertices in the arrangement obtained by computing all self-intersections in the input model. 'It.' stands for iteration.</caption><thead><tr><th colspan="4">Input model</th><th colspan="3">It. naive</th><th colspan="3">Zhou et al.</th><th colspan="3">Ours</th></tr><tr><th>Name</th><th>Id</th><th>Input V</th><th>Arr. V</th><th>It.</th><th>Out. V</th><th>Time</th><th>It.</th><th>Out. V</th><th>Time</th><th>It.</th><th>Out. V</th><th>Time</th></tr></thead><tbody><tr><td>Bird feeder</td><td>622327</td><td>125k</td><td>157k</td><td>17</td><td>138k</td><td>1min20</td><td>1</td><td>138k</td><td>9s</td><td>1</td><td>138k</td><td>9s</td></tr><tr><td>Dragonfly wings</td><td>498460</td><td>95k</td><td>412k</td><td>5</td><td>412k</td><td>43s</td><td>2</td><td>412k</td><td>31s</td><td>1</td><td>412k</td><td>18s</td></tr><tr><td>Chess set</td><td>113906</td><td>24k</td><td>93k</td><td>&gt;6</td><td>-</td><td>&gt;1h</td><td>5</td><td>92k</td><td>13s</td><td>1</td><td>91k</td><td>6s</td></tr><tr><td>Three men</td><td>199665</td><td>506k</td><td>507k</td><td>&gt;8</td><td>-</td><td>&gt;1h</td><td>1</td><td>507k</td><td>6s</td><td>1</td><td>507k</td><td>6s</td></tr><tr><td>Medieval castle</td><td>1368052</td><td>1.2M</td><td>2.1M</td><td>&gt;5</td><td>-</td><td>&gt;1h</td><td>6</td><td>2.1M</td><td>7min08</td><td>3</td><td>2.5M</td><td>5min12</td></tr><tr><td>Turbo Entabulator</td><td>217027</td><td>528</td><td>553</td><td>&gt;19</td><td>-</td><td>&gt;1h</td><td>&gt;15</td><td>-</td><td>&gt;1h</td><td>1</td><td>524</td><td>&lt;0.01s</td></tr><tr><td>Spiral Sphere</td><td>356074</td><td>14k</td><td>14k</td><td>&gt;6</td><td>-</td><td>&gt;1h</td><td>&gt;19</td><td>-</td><td>&gt;1h</td><td>1</td><td>14k</td><td>&lt;0.2s</td></tr><tr><td>Bottle Carrier</td><td>247516</td><td>90k</td><td>197k</td><td>&gt;4</td><td>-</td><td>&gt;1h</td><td>&gt;6</td><td>-</td><td>&gt;1h</td><td>1</td><td>196k</td><td>8s</td></tr><tr><td>Thing-O-Hoist</td><td>71377</td><td>502k</td><td>506k</td><td>&gt;12</td><td>-</td><td>&gt;1h</td><td>&gt;19</td><td>-</td><td>&gt;1h</td><td>1</td><td>506k</td><td>7s</td></tr><tr><td>Spider cube</td><td>252786</td><td>355k</td><td>2.2M</td><td>&gt;3</td><td>-</td><td>&gt;1h</td><td>&gt;2</td><td>-</td><td>&gt;1h</td><td>1</td><td>2.1M</td><td>2min26</td></tr></tbody></table>
their heuristic on all Thingi10K models for computing mesh self-intersections.

Unsurprisingly, their scheme works on all 3997 trivial Thingi10K models. Among the 527 non-trivial models, 48 did not terminate after 20 iterations or 10 hours, which is about 9% of the 527 models.

It should be stressed that the bound on the number of iterations is not a significant limitation. Indeed, among these 48 models, only five models terminates (within 10 hours each) if we remove this bound. (These models are referenced as 113 422, 521 600, 86 324, 128 001, 496 388 and they terminate in 21, 22, 32, 36, and 53 iterations, respectively.) For the others, the number of intersections increases with each iteration in 37 models, and six models get stuck in a loop with a cyclic number of intersections after more than 100 iterations.

**Our heuristic.** Except the famously difficult model of Thingi10K shown in Fig. 1, which we discuss in Section 4.5, all Thingi10K models were successfully resolved. Only 26 models required two iterations, and only 3 required three iterations. One of these three models is the Medieval castle presented in Fig. 4 and Table 1, and the other two are referenced as 106 838 and 78 227.

## 4.3. Running time

Computing self-intersections is the most time-consuming step in all heuristics and it is output sensitive. We thus present running times in terms of the size of input arrangements, specifically, the number of vertices in the models after computing all self-intersections.

We present in Fig. 5 the running times for the 3997 Thingi10K models for which the naive rounding works, and in Fig. 6 the running times for the other 527 non-trivial Thingi10K models (with the exception of the model shown in Fig. 1 and discussed in Section 4.5).

Data points are included only when heuristics succeed within the time bound; recall that the iterative naive rounding terminates on only 52% of the non-trivial models, and Zhou et al.'s heuristic on 91%.

For both data subsets and all schemes, the running times are well captured by linear approximations. The least-square interpolations of the running time shown in Figs. 5 and 6 are the following, in milliseconds per thousand of input arrangement vertices: for trivial models, 7.1x for the naive rounding, 7.3x for Zhou et al. and 7.5x for ours; for non-trivial models, 34x for the iterative naive rounding, 26x for Zhou et al. and 19x for ours. Table 2 gives the corresponding average numbers of vertices processed per second. The averages are quite similar for trivial models but for non-trivial models, the gap is larger and our scheme is on average faster than Zhou et al.'s by a factor 1.4 and faster than the iterative naive rounding by a factor 1.8.

## 4.4. Size of output

We present in Fig. 7(a) the ratio of the output size of our heuristic over the size of the input, and the ratio of the size of the input arrangement (i.e., after having computed self-intersections) over the

<table><caption>Table 2: Average number of input arrangement vertices handled per second.</caption><thead><tr><th></th><th>It. Naive</th><th>Zhou et al.</th><th>Ours</th></tr></thead><tbody><tr><th>Trivial models</th><td>140 k/s</td><td>136 k/s</td><td>133 k/s</td></tr><tr><th>Non-Trivial models</th><td>29 k/s</td><td>38 k/s</td><td>53 k/s</td></tr></tbody></table>

size of the input, for the 527 non-trivial Thingi10K models (except the one of Fig. 1 discussed in Section 4.5).

This shows that the size of the input arrangement is a good predictor of the size of the output, especially when the input model contains many self-intersections (i.e., when the input arrangement is larger than the input size). However, we can also observe that, occasionally, our output is much smaller than the input arrangement, the converse being very rare.

Fig. 7(b) shows the ratio of Zhou et al. output size over the input size, compared to ours and similarly for Fig. 7(c) with the iterative naive rounding scheme. These figures show that these heuristics fail more often when the input arrangement is large compared to the input size. However, when they succeed, the output size tend to be similar to ours, although occasionally larger.

## 4.5. The model of Fig. 1

The model shown in Fig. 1, referenced as number 996 816 in Thingi10K, is notoriously difficult due to its incredibly high number of intersections and has caused failures in many various implementations. It contains about 76k vertices and 171k triangles. Its input size is thus quite reasonable, but about 86k of its triangles are involved in about 5M pairs of intersecting triangles and 20M of triplets of intersecting triangles. Computing all self-intersections is thus already a tremendous work and the resulting exact arrangement is huge with about 30M vertices and 240M faces.

Our heuristic fails to resolve this model with our default grid size for rounding the vertices of the triangles involved in self-intersections. Recall that our default grid is obtained by scaling the uniform integer grid, where the reverse scaling (by a power of two) maps the largest absolute value of all vertex coordinates to the range $[2^{23}, 2^{24})$.

However, we successfully resolve this model in 38s (serial) by rounding the vertices on a coarser grid, namely by scaling the largest absolute value of the coordinates to the interval $[2^{13}, 2^{14})$ instead of $[2^{23}, 2^{24})$. With this coarser grid, the rounding induces a relative error of at most half of $2^{-14}$ ($\approx 3 \cdot 10^{-5}$) in the coordinates and the $L^\infty$ Hausdorff distance between the input and output models does not exceed $3.1 \cdot 10^{-3}$ (because rounded coordinates do not exceed 100 in absolute value and the heuristic resolves this instance in only one iteration).

Furthermore, the output model contains approximately 100k vertices and 245k faces, which is satisfactory, as it is of the same order of magnitude as the input model.

It should be noted that, by increasing the precision of the rounding by a factor 2, the heuristic still resolves this model in 1min26
<figure><img src="image_7.png" /><figcaption>Figure 5: Running time in seconds for the 3997 trivial models of Thingi10K in terms of the input arrangement size, and their interpolations.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 6: Running time in seconds for the 527 non-trivial models of Thingi10K (except the one of Fig. 1) in terms of the input arrangement size, and their interpolations.</figcaption></figure>

with about 280k vertices in the output. Increasing again the precision by a factor two, the heuristic still works but in 19min and a huge output with 4.8M vertices. Increasing again the precision by a factor two, the heuristic does not terminate in the one hour time limit.

## 4.6. Rotated cubes

We tested the heuristics on an ad hoc challenging model that consists of the Boolean intersection of many randomly rotated unit cubes, all centered at the origin and added one by one. After many iterations, the model approximates a sphere with complex shapes on its surface (see Fig. 2).

We conducted these experiments using the same initial seeds for each heuristic to ensure reproducibility, performing 16 distinct trials per heuristic with seeds ranging from 1 to 16. We computed Boolean intersections using the CGAL core-fine_and_compute_intersection function [CLK*24].

Each trial run was stopped at a certain iteration either if (i) the heuristic failed to remove self-intersections, or (ii) the result of the Boolean intersection was not 2-manifold (a requirement of the CGAL Boolean operator).

Understanding why Boolean intersections of such cubes might not result in a 2-manifold is not immediately clear. A typical example, depicted in Fig. 8(c), is when the rounding scheme creates new intersections, then the resulting model of the current iteration is not 2-manifold and its Boolean intersection with a cube in the following iteration is possibly not 2-manifold either.

The iterative naive rounding trials stopped after an average of 150 cubes with a standard deviation (SD) of 96, while Zhou et al.'s [ZGZJ16] trials stopped after an average of 288 cubes

(SD = 163). In contrast, our heuristic reached an average of 1090 cubes (SD = 457) over the 16 trials after 40 hours of computation. However, 7 of the 16 trials were still in progress after 40 hours: these 7 trials reached an average of 1476 intersected cubes (SD = 109), each with about 750k vertices, and each Boolean intersection with a new cube took about four minutes.

## 4.7. Summary of experiments

In terms of success rate, naive rounding fails quite often, that is on 527 (≈12%) of the self-intersecting models of Thingi10K, which are referred to as the non-trivial models of Thingi10K. The iterative naive rounding solves only about half of these non-trivial models. Zhou et al.'s heuristic [ZGZJ16] is generally effective but shows limitations, as it fails on about 9% of the non-trivial models. Our heuristic successfully resolves all Thingi10K models, although its famously difficult model shown in Fig. 1 needs to be handled with a coarser-than-default grid.

In terms of efficiency, the output size is fairly well approximated by the size of the input arrangement (i.e., the input model after having computed self-intersections) and the running time of all heuristics are well approximated by linear interpolations. Our scheme handles on average at least 50k vertices of the input arrangement per second. The averages are quite similar for all heuristics on trivial models but on non-trivial models, our scheme is on average faster than Zhou et al.'s by a factor 1.4.

In the challenging ad hoc experiment of Boolean intersections of randomly rotated unit cubes, all centered at the origin, previous heuristics fail with less than 300 cubes, averaged over 16 trials. In contrast, our heuristic reached an average of 1090 cubes with 7 out of the 16 trials that were still in progress after 40 hours of
<figure><img src="image_9.png" /><figcaption>Figure 7: Output sizes versus input sizes. (a-c) In blue: ratio of the output size of our heuristic over the input size, for each of the 527 Thingi10K non-trivial models (except the one of Fig. 1) ordered increasingly. (a) In purple: ratio of the input arrangement size over the input size. (b) In green: ratio of Zhou et al. [ZGZJ16] output size over the input size. (c) In red: ratio of the iterative naive output size over the input size. (b-c) Missing data corresponds to instances on which heuristics fails.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 8: A typical intersection induced by rounding. (a) Edge-face intersection. (b) Subsequent face triangulation. (c) Edge-face intersection *N* induced by the rounding of *M* and the “flip” of a triangle.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 9: Another typical intersection induced by rounding. (a) In-put. (b) Intersection induced by the rounding of Step (ii). (c) Re-moval of the intersection induced by the rounding of Step (iii).</figcaption></figure>

computation and in which each Boolean intersection with a new
rotated cubes took about 4 minutes.

**5. Insights on our scheme and Zhou et al.'s**

The effectiveness of our scheme and Zhou et al.'s [ZGZJ16] are not
obvious. We present here our understanding, although supporting
evidence remains elusive. (Note that Zhou et al. did not address
this aspect in their paper.)

**Merging vertices.** First, coarsely rounding coordinates tends to merge nearby vertices, eliminating triangles with tiny edges. This effect can be observed in the size of the output (see Fig. 7), which is occasionally much smaller than the size of the input after computing self-intersections. However, this alone does not explain the schemes effectiveness because it solves fewer problems than it causes (see e.g. Fig. 8). Experiments show that rounding *all* coordinates to floats (after computing self-intersections) performs very poorly and is even worse than naive rounding: this approach fails to remove self-intersections on about 42% of the 4524 Thingi10K models that contain self-intersections (instead of 12% for naive rounding) and iterating with a one-hour limit only reduces the failure ratio to about 24%. (Results are similar if we round coordinates on a uniform grid instead of the grid of floats.)

Nevertheless, rounding all vertices that are located in a grid cell where a vertex has already been rounded (as in Step (iii) of our scheme) is quite natural, since it prevents additional intersections, as depicted in Fig. 9, with no apparent drawbacks. Without Step (iii), our scheme fails on one Thingi10K model other than the

famous one of Fig. 1; this model (referenced as 105 867) is relatively small, containing 15k vertices and 75 pairs of intersecting triangles, however the number of intersections increases significantly with each iteration. Furthermore, without Step (iii), many models (46 in total) require more iterations, which results in slower running times.

**Reducing triangle flips.** Consider now a (proper) intersection of a segment with a triangle (see Fig. 8). A simple calculation shows that each coordinate of the intersection point is a rational whose numerator and denominator are polynomials of degree 4 and 3, respectively, in the coordinates of the triangle and segment vertices. Further straightforward computations show that, in projection on any of the three axis-parallel planes, the distance between the intersection point and the triangle boundary is an expression whose numerator is the sum of 144 monomials, each of degree 5 in the coordinates of these vertices and whose coefficient is $\pm 1$; the denominator is the sum of 36 monomials, each of degree 3 in the same variables and also with coefficient $\pm 1$, times a square root of the form $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ where the $x_i$ and $y_i$ are coordinates of the vertices. If all these coordinates are bounded by $\pm 2^m$ and lie on a uniform grid of fineness $2^{-k}$, the denominator is at most $2^{4m+7}$ since $36 \cdot \sqrt{8} < 2^7$ and the numerator is either 0 or at least $2^{-5k}$ because after multiplying the numerator by $2^{5k}$, each monomial is an integer. Hence, the above distance is either 0 or at least $\Delta = 2^{-5k-4m-7}$.

It follows that, if the intersection (between the triangle and seg-
ment) is rounded on a grid with a minimum spacing smaller than $\Delta$,
the subdivided triangles (see Fig. 8) do not flip during rounding, in
projection onto axis-parallel planes. (In what follows, triangle flips
refer to flips occurring in these 2D projections.)

In our scheme, if the input vertices have their coordinates
bounded by ±2<sup>m</sup>, we round the vertices of the triangles that in-
tersect (in Step (iv')) on a uniform grid of fineness 2<sup>-k</sup> with
k = 24 - m. Hence Δ = 2<sup>-((103-m))</sup>. We then round (in Step (vi'))
the coordinates of the intersections points on doubles, which spac-
ing is at most 2<sup>-((53-m))</sup> in the range ±2<sup>m</sup>.

The rounding in Step (vi') can thus move coordinates by half of
2⁻(53⁻m), which is larger than the distance bound Δ = 2⁻((103⁻m)).
Hence, the rounding we consider in Step (iv') is not coarse enough
to ensure that the triangles never flip. However, the discrepancy be-
tween the fine and coarse grids (in Steps (i') and (vi')) makes it
unlikely for them to often flip in practice. It follows that if trian-
gles are unlikely to flip during rounding, the typical propagation
of edge-face intersections depicted in Fig. 8 is also unlikely. We
identify this as the key insight underlying the remarkable behav-
ior of our scheme. This understanding is further supported by our
following analysis of Zhou et al.'s scheme.

It should be emphasized that this insight is far from yielding a
guaranteed practical algorithm. Indeed, first, ensuring that triangles
never flip in the above analysis would require that the rounding
in Step (iv') uses an extremely coarse rounding with significand
precision of only 9 bits (8 explicitly stored); indeed, a significand
of *p* bits yields a grid of fineness 2⁻ᵏ with *k* = *p* − *m* in Step (iv'),
then half of 2⁻((5³⁻m)) is smaller than Δ = 2⁻((5*p*+7⁻m)) only if *p* ≤
9. Second, the propagation of edge-face intersection depicted in
Fig. 8 is, in theory, far from being the only cause for propagation
of intersections when rounding vertices.

**Limitations of Zhou et al.'s scheme.** While we consider a uni-
form grid in our scheme, Zhou et al. round the coordinates directly
on floats. This implies that, in their scheme, the minimum dis-
tance between coordinates is much smaller when the coordinates
are close to zero than when they are away from zero. As a conse-
quence, the above argument, claiming that triangles rarely flip, does
not hold anymore. Experimental evidence supporting this analysis
is that 44 out of the 48 Thingi10K models on which Zhou et al.'s
scheme fails are successfully resolved by their scheme after trans-
lating the models so that all coordinates are larger than one.

This observation also supports our earlier insight into the under-
lying behavior of our scheme. However, it should be emphasized
that the approach that consists in translating the model, applying
Zhou et al.'s scheme and translating the rounded model back does
not work well in practice. Indeed, the final translation, which re-
quires rounding the coordinates again, appears to often create new
intersections in difficult instances. Our experiments show that this
approach fails on 34 of the 48 Thingi10K models on which Zhou
et al.'s scheme fails: their scheme fails on 4 translated models and
the reverse translation introduces new intersections in 30 additional
models.

6. Conclusion

We have introduced a new scheme to address the mesh intersec-
tion problem, with a particular focus on the intersections resulting

from the conversion of the vertices coordinates from their exact
mathematical values to a fixed-precision floating-point format. The
method is very lightweight and minimally invasive, and it can be
applied regularly if further geometric operations reintroduce inter-
sections. Our evaluations on the Thingi10K dataset, where we suc-
cessfully resolve all models, and on a challenging ad hoc experi-
ment, demonstrate that our method is highly effective, even on ex-
tremely difficult instances, and significantly outperforms previous
approaches. Our implementation will be included in the Polygon
Mesh Processing package of the upcoming CGAL release 6.1.

**References**

[Att14] ATTENE M.: Direct repair of self-intersecting meshes. *Graphical Models* **76**, 6 (2014), 658–668. URL: https://www.sciencedirect.com/science/article/pii/S1524070314000496, doi:https://doi.org/10.1016/j.gmod.2014.09.002.2

[Att20] ATTENE M.: Indirect predicates for geometric constructions. *Computer-Aided Design* **126** (2020), 102856. URL: https://www.sciencedirect.com/science/article/pii/S001044852030049X.2

[CGA] CGAL PROJECT: *CGAL User and Reference Manual*. CGAL Editorial Board. URL: https://doc.cgal.org/latest/Manual/packages.html. 4

[CLK*24] COEURJOLLY D., LACHAUD J.-O., KATRIOPLAS K., LO-RIOT S., PADEN I., ROUXEL-LABBÉ M., SAEED H., TOURNOIS J., YAZ I. O.: Polygon mesh processing. In *CGAL User and Reference Manual*, 6.0.1 ed. CGAL Editorial Board, 2024. URL: https://doc.cgal.org/latest/Manual/packages.html#PkgPolygonMeshProcessing. 4, 7

[CLSA20] CHERCHI G., LIVESU M., SCATENI R., ATTENE M.: Fast and robust mesh arrangements using floating-point arithmetic. *ACM Transactions on Graphics* **39**, 6 (2020), 1–16. 2

[CPAL22] CHERCHI G., PELLACINI F., ATTENE M., LIVESU M.: In-
teractive and robust mesh booleans. *ACM Transactions on Graphics (TOG)* **41**, 6 (Nov. 2022). URL: https://doi.org/10.1145/3550454.3555460, doi:10.1145/3550454.3555460.2

[CPLW19] CHU L., PAN H., LIU Y., WANG W.: Repairing man-
made meshes via visual driven global optimization with minimum intru-
sion. *ACM Trans. Graph.* **38**, 6 (Nov. 2019). URL: https://doi.
org/10.1145/3355089.3356507, doi:10.1145/3355089.
3356507.2

[DA21] DIAZZI L., ATTENE M.: Convex polyhedral meshing for robust solid modeling. *ACM Transactions on Graphics (TOG)* **40**, 6 (2021), 1–16. URL: https://dl.acm.org/doi/10.1145/3478513.3480564.2

[DLL20] DEVILLERS O., LAZARD S., LENHART W.: Rounding meshes in 3D. *Discrete and Computational Geometry* **64**, 1 (Apr. 2020), 32–67. URL: https://inria.hal.science/hal-02549290, doi:10.1007/s00454-020-00202-2.3

[For99] FORTUNE S.: Vertex-rounding a three-dimensional polyhedral subdivision. *Discrete & Computational Geometry* **22**, 4 (1999), 593–618. doi:10.1007/PL00009480.3

[GF24] GUO J.-P., FU X.-M.: Exact and efficient intersection resolution for mesh arrangements. *ACM Trans. Graph.* **43**, 6 (Nov. 2024). URL: https://doi.org/10.1145/3687925, doi:10.1145/3687925.2

[GGHT97] GOODRICH M. T., GUIBAS L. J., HERSHBERGER J., TANENBAUM P. J.: Snap rounding line segments efficiently in two and three dimensions. In *Proceedings of the thirteenth annual symposium on Computational geometry* (1997), ACM, pp. 284–293. doi: 10.1145/262839.262985.3
[HSW*20] HU Y., SCHNEIDER T., WANG B., ZORIN D., PANOZZO D.: Fast tetrahedral meshing in the wild. *ACM Trans. Graph.* **39**, 4 (Aug. 2020). URL: https://doi.org/10.1145/3386569.3392385, doi:10.1145/3386569.3392385.2

[HZG*18] HU Y., ZHOU Q., GAO X., JACOBSON A., ZORIN D., PANOZZO D.: Tetrahedral meshing in the wild. *ACM Trans. Graph.* **37**, 4 (July 2018). URL: https://doi.org/10.1145/3197517.3201353, doi:10.1145/3197517.3201353.2

[Ju04] JU T.: Robust repair of polygonal models. *ACM Trans. Graph.* **23**, 3 (Aug. 2004), 888–895. URL: https://doi.org/10.1145/1015706.1015815, doi:10.1145/1015706.1015815.2

[Lév24] LÉVY B.: Exact predicates, exact constructions and combinatorics for mesh csg, 2024. URL: https://arxiv.org/abs/2405.12949, arXiv:2405.12949.2

[Liv24] LIVESU M.: Advancing Front Surface Mapping. *Computer Graphics Forum* **43**, 2 (2024), e15026. doi:10.1111/cgf.15026.2

[Mil90] MILENKOVIC V.: Rounding face lattices in $d$ dimensions. In *Proceedings of the 2nd Canadian Conference on Computational geometry* (1990), pp. 40–45. URL: https://cccg.ca/proceedings/1990/Paper10.pdf. 2

[MS19] MILENKOVIC V., SACKS E.: Geometric rounding and feature separation in meshes. *Computer-Aided Design* **108** (2019), 12–18. URL: https://www.sciencedirect.com/science/article/pii/S0010448518302896, doi:https://doi.org/10.1016/j.cad.2018.10.003.3

[TNWK22] TRETTNER P., NEHRING-WIRXEL J., KOBBELT L.: Ember: exact mesh booleans via efficient & robust local arrangements. *ACM Trans. Graph.* **41**, 4 (July 2022). URL: https://doi.org/10.1145/3528223.3530181, doi:10.1145/3528223.3530181.2

[Val19] VALQUE L.: 3D Snap Rounding. Master's thesis, Université de Lyon, June 2019. URL: https://hal.inria.fr/hal-02393625.3

[Val24] VALQUE L.: 3D Snap Rounding. PhD thesis, Université de Lorraine, Décember 2024. URL: https://hal.inria.fr/tel-05016163.1, 2, 3, 4

[WSH*20] WANG B., SCHNEIDER T., HU Y., ATTENE M., PANOZZO D.: Exact and efficient polyhedral envelope containment check. *ACM Trans. Graph.* **39**, 4 (Aug. 2020). URL: https://doi.org/10.1145/3386569.3392426, doi:10.1145/3386569.3392426.2

[ZGP*24] ZHENG Z., GAO X., PAN Z., LI W., WANG P.-S., WANG G., WU K.: Visual-preserving mesh repair. *IEEE Transactions on Visualization and Computer Graphics* **30**, 9 (2024), 6586–6597. doi: 10.1109/TVCG.2023.3348829.2

[ZGZJ16] ZHOU Q., GRINSPUN E., ZORIN D., JACOBSON A.: Mesh arrangements for solid geometry. *ACM Transactions on Graphics (TOG)* **35**, 4 (2016), 1–15. URL: https://dl.acm.org/doi/abs/10.1145/2897824.2925901?preflayout= tabs. 1, 2, 3, 4, 5, 7, 8

[ZJ16] ZHOU Q., JACOBSON A.: Thingi10k: A dataset of 10,000 3d-printing models, 2016. URL: https://arxiv.org/abs/1605.04797, arXiv:1605.04797.1, 2, 3, 4, 5