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.

In most layered additive manufacturing processes, a tool solidifies or deposits material while following pre-planned trajectories to form solid beads. Many interesting problems arise in this context, among which one concerns the planning of trajectories for filling a planar shape as densely as possible. This is the problem we tackle in the present paper. Recent works have shown that allowing the bead width to vary along the trajectories helps increase the filling density. We present a novel technique that, given a deposition width range, constructs a set of closed beads whose width varies within the prescribed range and fill the input shape. The technique outperforms the state of the art in important metrics: filling density (while still guaranteeing the absence of bead overlap) and trajectories smoothness. We give a detailed geometric description of our algorithm, explore its behavior on example inputs and provide a statistical comparison with the state of the art. We show that it is possible to obtain high quality fabricated layers on commodity FDM printers.

Let P be a set of n polygons in R^3, each of constant complexity and with pairwise disjoint interiors. We propose a rounding algorithm that maps P to a simplicial complex Q whose vertices have integer coordinates. Every face of P is mapped to a set of faces (or edges or vertices) of Q and the mapping from P to Q can be done through a continuous motion of the faces such that (i) the L_infty Hausdorff distance between a face and its image during the motion is at most 3/2 and (ii) if two points become equal during the motion, they remain equal through the rest of the motion. In the worst case, the size of Q is O(n^{15}) and the time complexity of the algorithm is O(n^{19}) but, under reasonable hypotheses, these complexities decrease to O(n^{5}) and O(n^{6}sqrt{n}).

We address the problem of computing a linear separating form of a system of two bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at the distinct solutions of the system. The computation of such linear forms is at the core of most algorithms that solve algebraic systems by computing rational parameterizations of the solutions and this is the bottleneck of these algorithms in terms of worst-case bit complexity. We present for this problem a new algorithm of worst-case bit complexity ÕB(d7 + d6τ) where d and τ denote respectively the maximum degree and bitsize of the input (and where Õ refers to the complexity where polylogarithmic factors are omitted and OB refers to the bit complexity). This algorithm simplifies and decreases by a factor d the worst-case bit complexity presented for this problem by Bouzidi et al. [5]. This algorithm also yields, for this problem, a probabilistic Las-Vegas algorithm of expected bit complexity ÕB(d5 + d4τ).

We address the problem of solving systems of two bivariate polynomials of total degree at most d with integer coefficients of maximum bitsize τ We suppose known a linear separating form (that is a linear combination of the variables that takes different values at distinct solutions of the system) and focus on the computation of a Rational Univariate Representation (RUR).

We present an algorithm for computing a separating linear form of a system of bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at distinct (complex) solutions of the system. In other words, a separating linear form defines a shear of the coordinate system that sends the algebraic system in generic position, in the sense that no two distinct solutions are vertically aligned. The computation of such linear forms is at the core of most algorithms that solve algebraic systems by computing rational parameterizations of the solutions and, moreover, the computation of a separating linear form is the bottleneck of these algorithms, in terms of worst-case bit complexity.

We consider the problem of computing shortest paths having curvature at most one almost everywhere and visiting a sequence of $n$ points in the plane in a given order. This problem is a subproblem of the Dubins traveling salesman problem and also arises naturally in path planning for point car-like robots in the presence of polygonal obstacles. We show that when consecutive waypoints are a distance of at least four apart, this question reduces to a family of convex optimization problems over polyhedra in $\mathbb{R}^n$.

We present two new fundamental lower bounds on the worst-case combinatorial complexity of sets of free lines and sets of maximal free line segments in the presence of balls in three dimensions.

We revisit the problem of computing the topology and geometry of a real algebraic plane curve. The topology is of prime interest but geometric information, such as the position of singular and critical points, is also relevant. A challenge is to compute efficiently this information for the given coordinate system even if the curve is not in generic position.

The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without backtracking. We propose a natural extension of Fréchet distance to more general metric spaces, which requires the leash itself to move continuously over time. For example, for curves in the punctured plane, the leash cannot pass through or jump over the obstacles ("trees"). We describe a polynomial-time algorithm to compute the homotopic Fréchet distance between two given polygonal curves in the plane minus a given set of obstacles, which are either points or polygons.

When an observer is in a 3D scene, a topological change in the view arises when the line of sight is tangent to four objects. If we consider polyhedral scenes, the relevant lines of sight are transversals to some edges of the polyhedra. In this paper we investigate predicates about visibility events arising in this context. Namely, we consider the predicates for counting the number of line transversals to lines and segments in 3D and the predicate for determining whether a line of sight is intersected by a triangle. We also consider a predicate that order these visibility events in the rotating plane-sweep algorithm of Brönnimann et al. (2007)

Computing shadow boundaries is a difficult problem in the case of non-pointlight sources. A point is in the umbra if it does not see any part of anylight source; it is in full light if it sees entirely all the light sources;otherwise, it is in the penumbra. While the common boundary of the penumbraand the full light is well understood, less is known about the boundary of theumbra. In this paper we prove various bounds on the complexity of the umbra andthe penumbra cast by a segment or polygonal light source on a plane in the presence ofpolygon or polytope obstacles. In particular, we show that a single segment light source may cast on a plane, in thepresence of two triangles, four connected components of umbra and that two fatconvex obstacles of total complexity n can engender Ω(n) connectedcomponents of umbra. In a scene consisting of a segment light source and kdisjoint polytopes of total complexity n, we prove an Ω(nk2+k4)lower bound on the maximum number of connected components of the umbra and a O(nk3) upper bound on its complexity. We also prove that, in the presence of kdisjoint polytopes of total complexity n, some of which being light sources,the umbra cast on a plane may have Ω(n2k3 +nk5) connected components and has complexity O(n3k3).These are the first bounds on the size of the umbra in terms of both k and n. These results prove that the umbra, which is bounded by arcs of conics,is intrinsically much more intricate than the full light/penumbra boundary whichis bounded by linesegments and whose worst-case complexity is in Ω(nα(k) +km +k2) and O(nα(k) + kmα(k) +k2), where m is the complexity of the polygonallight source.

We give a complete description of the Voronoi diagram of three lines in R3. In particular, we show that the topology of the Voronoi diagram is invariant for three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. The trisector consists of four unbounded branches of either a non-singular quartic or of a cubic and line that do not intersect in real space. Each cell of dimension two consists of two connected components on a hyperbolic paraboloid that are bounded, respectively, by three and one of the branches of the trisector. The proof technique, which relies heavily upon modern tools of computer algebra, is of interest in its own right. This characterization yields some fundamental properties of the Voronoi diagram of three lines. In particular, we present linear semi-algebraic tests for separating the two connected components of each two-dimensional Voronoi cell and for separating the four connected components of the trisector. This enables us to answer queries of the form, given a point, determine in which connected component of which cell it lies. We also show that the arcs of the trisector are monotonic in some direction. These properties imply that points on the trisector of three lines can be sorted along each branch using only linear semi-algebraic tests.

In this note we describe the contents of a video illustrating analgorithm for computing the 3D visibility skeleton ofa set of disjoint convex polytopes. The video can be foundat http://www.cs.mcgill.ca/~lzhang15/video/ with file name socg07visidemo.mov.

Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in $\mathbb{R}^3$ with a total of n edges consists of $\Theta(n^2)$ connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrarily degenerate scenes. More generally, we show that a set of k possibly intersecting convex polyhedra with a total of n edges admits, in the worst case, $\Theta(n^2k^2)$ connected components of maximal free line segments tangent to at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments. Finally, we present an $O(n^2 k^2 \log n)$ time and $O(nk^2)$ space algorithm that, given a scene of k possibly intersecting convex polyhedra, computes all the minimal free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.

We prove that the lines tangent to four possibly intersecting convex polyhedra in ℝ3 with n edges in total form Θ(n2) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. More generally, we show that a set of kconvex polyhedra with a total of n edges admits, in the worst case, Θ(n2k2)connected components of (possibly occluded) lines tangent to any four of these polyhedra. We also show a lower bound of Ω(n2k2) on the number of non-occluded maximal line segments tangent to any four of these k convex polyhedra.

We present the first complete, exact and efficient C++ implementation of a method for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the near-optimal algorithm recently introduced by Dupont et al., [2]. Unlike existing implementations, it correctly identifies and parameterizes all the connected components of the intersection in all cases, returning parameterizations with rational functions whenever such parameterizations exist. In addition, the coefficient fields of the parameterizations are either minimal or involve one possibly unneeded square root. We prove upper bounds on the size of the coefficients of the output parameterization and compare these bounds to observed values. We give other experimental results and present some examples.

In this paper, we present the first exact, robust and practical method for computing an explicit representation of the intersection of two arbitrary quadrics whose coefficients are rational. Combining results from the theory of quadratic forms, linear algebra and number theory, we show how to obtain parametric intersection curves that are near-optimal in the number and depth of radicals involved.

In this paper, we show that, amongst n uniformly distributed unit balls in $\mathbb{R}^3$, the expected number of maximal nonoccluded line segments tangent to four balls is linear. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding the visibility information of a scene, providing evidence that the storage requirement for this data structure is not necessarily prohibitive. These results significantly improve the best previously known bounds of $O(n^{8/3})$ [F. Durand, G. Drettakis, and C. Puech, {ACM Transactions on Graphics}, 21 (2002), pp. 176-206]. Our results generalize in various directions. We show that the linear bound on the expected number of maximal nonoccluded line segments that are not too close to the boundary of the scene and tangent to four unit balls extends to balls of various but bounded radii, to polyhedra of bounded aspect ratio, and even to nonfat three-dimensional objects such as polygons of bounded aspect ratio. We also prove that our results extend to other distributions such as the Poisson distribution. Finally, we indicate how our probabilistic analysis provides new insight on the expected size of other global visibility data structures, notably the aspect graph.

Let B be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let $\poly$ be a convex polygon with n vertices. We study the collision-free, optimal path-planning problem for B moving between two configurations inside $\poly$. (A configuration specifies both a location and a direction of travel.) We present an O(n 2 log n) time algorithm for determining whether a collision-free path exists for B between two given configurations. If such a path exists, the algorithm returns a shortest one. We provide a detailed classification of curvature-constrained shortest paths inside a convex polygon and prove several properties of them, which are interesting in their own right. For example, we prove that any such shortest path is comprised of at most eight segments, each of which is a circular arc of unit radius or a straight-line segment. Some of the properties are quite general and shed some light on curvature-constrained shortest paths amid obstacles.

In this article, we introduce a general-purpose method for computing radiosity on scenes made of parametric surfaces with arbitrary trimming curves. In contrast with past approaches that require a tessellation of the input surfaces (be it made up of triangles or patches with simple trimming curves) or some form of geometric approximation, our method takes full advantage of the rich and compact mathematical representation of objects. At its core lies the virtual mesh , an abstraction of the input geometry that allows complex shapes to be illuminated as if they were simple primitives. The virtual mesh is a collection of normalized square domains to which the input surfaces are mapped while preserving their energy properties. Radiosity values are then computed on these supports before being lifted back to the original surfaces. To demonstrate the power of our method, we describe a high-order wavelet radiosity implementation that uses the virtual mesh. Examples of objects and environments, designed for interactive applications or virtual reality, are presented. They prove that, by exactly integrating curved surfaces in the resolution process, the virtual mesh allows complex scenes to be rendered more quickly, more accurately, and much more naturally than with previously known methods.

We study the problem of computing the free space ${\cal F}$ of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is subject to two constraints: each leg has a maximal extension R (accessibility constraint) and the body of the robot must lie above the convex hull of its feet (stability constraint). Moreover, the robot can only put its feet on some regions, called the foothold regions. The free space ${\mathcal{F}}$ is the set of positions of the body of the robot such that there exists a set of accessible footholds for which the robot is stable. We present an efficient algorithm that computes ${\cal F}$ in $O(n^2\log n)$ time using $O(n^2\alpha(n))$ space for n discrete point footholds where $\alpha(n)$ is an extremely slowly growing function ($\alpha(n)\leq 3$ for any practical value of n). We also present an algorithm for computing ${\cal F}$ when the foothold regions are pairwise disjoint polygons with n edges in total. This algorithm computes ${\cal F}$ in $O(n^2\alpha_8(n)\log n)$ time using $O(n^2\alpha_8(n))$ space. ($\alpha_8(n)$ is also an extremely slowly growing function.) These results are close to optimal since $\Omega(n^2)$ is a lower bound for the size of ${\cal F}$.

International audience

In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane. More precisely, given prescribed initial and nal congurations (i.e. positions and orientations) and a set of obstacles in the plane, we want to compute a shortest C 1 path joining those two congurations, avoiding the obstacles, and with the further constraint that, on each C 2 piece, the radius of curvature is at least 1. In this paper, we consider the case of moderate obstacles (as introduced by Agarwal et al. [1]) and present a polynomial-time exact algorithm to solve this problem. 1 Introduction In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane, SBC path for short. More precisely, given prescribed initial and nal congurations (i.e. positions and orientations) and a set of obstacles in the plane, we want to compute a shortest C 1 path joining those two congurations, avoiding the obstacles,...

Studies the problem of computing the set F of accessible and stable placements of a spider robot. The body of this robot is a single point and the legs are line segments attached to the body. The robot can only put its feet on some regions, called the foothold regions. Moreover, the robot is subject to two constraints: each leg has a maximal extension R (accessibility constraint) and the body of the robot must lie above the convex hull of its feet (stability constraint). The authors present an efficient algorithm to compute F. If the foothold regions are polygons with n edges in total, the authors' algorithm computes F in O(n/sup 2/ log n) time and O(n/sup 2//spl alpha/(n)) space where /spl alpha/ is the inverse of Ackerman's function. /spl Omega/(n/sup 2/) is a lower bound for the size of F.>