Olivier Devillers
email: olivier.devillers@sophia.inria.fr

Marc Glisse
email: marc.glisse@normalesup.org

Sylvain Lazard
email: sylvain.lazard@loria.fr

Predicates for line transversals to lines and line segments in three-dimensional space *

].

Introduction

The computation of visibility between objects in three-dimensional space is one of the main problems of computer graphics, useful for hidden parts elimination, umbra and penumbra computations, radiosity methods. . . [START_REF] Durand | A multidisciplinary survey of visibility[END_REF]. The visibility skeleton of a set of polyhedra can be computed by sweeping the space by a plane rotating around each edge of the scene in O(n 2 k 2 log n) time for a scene of k convex polyhedra of total complexity n [START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF]. In this sweeping algorithm an event corresponds to a line stabbing four edges of the scene. As any geometric algorithm, visibility computation relies on basic geometric tests called predicates involving a small number of input objects; the answer of a predicate is discrete, typically it is a sign +/ -/0 that can be interpreted by something like inside/outside/on boundary or above/below/same height. Going from the geometric formulation of a predicate (is an object above another?) to an actual implementation consists in finding one (or several) polynomial(s) in the parameters describing the objects such that the sign (or a combination of the signs) of the polynomial(s) gives the answer to the geometric question.

For a given geometric problem, what a good design is for a predicate remains a difficult question. Between several polynomial formulations, the set of polynomials with lowest maximal degree is often preferred since the degree of a polynomial is closely related to the precision of the computation needed to evaluate exactly this polynomial, and such exact evaluation may be needed to solve robustness issues using the exact computation paradigm [START_REF] Yap | Towards exact geometric computation[END_REF]. Notice that this study is restricted to predicates implemented by computing the sign of polynomials; divisions, modular operations, factorizations are not considered here.

For our visibility problems, the predicates needed include: -the existence of a stabbing line to four edges (or more edges to take degeneracies into account), -the fact that a triangle occludes or not a stabbing line and -the comparison of such stabbing lines in the sweep order.

Contribution

In this paper, we propose a direct formulation for line intersection problems which gives better results than the standard naive approach using Plücker coordinates. In particular, it is easier in this setting to take into account line segments rather than entire lines. Based on this formulation we design several predicates.

We propose a predicate for counting the transversals to four lines using a polynomial of degree 12 while the naive approach of Plücker coordinates gives degree 24 [START_REF] Everett | Accepted in Computational Geometry: Theory and Applications[END_REF] and a more advanced use of Plücker coordinates gives the same degree 12 polynomial but was only interpreted for parameters in the field of complex numbers [START_REF] Mourrain | [END_REF]. Designing the counting predicates for transversals to line segments instead of lines, our approach still gives a polynomial of degree 12 while [START_REF] Everett | Accepted in Computational Geometry: Theory and Applications[END_REF] increases to 36.

We solve the occlusion predicate with degree 15 and the ordering of stabbing lines predicate with degree 36 while [START_REF] Everett | Accepted in Computational Geometry: Theory and Applications[END_REF] uses polynomials of respective degrees 78 and 144.

If the involved polynomial of highest degree is irreducible and its roots correspond to a change in the answer of the predicate, we can argue that we reach a kind of optimality. This is indeed the case for the counting and occlusion predicates while for the ordering of stabbing lines predicate we believe that the polynomial is reducible and the degree of the predicate could be lowered to 24.

Notation and preliminaries

We work in a projective setting so that two parallel lines intersect (at infinity). Let P n denote the real projective space of dimension n. Lines in 3D are defined by two points in P 3 . More formally, a line A through the points a = (a x : a y :

a z : a ω ) T and a ′ = (a ′ x : a ′ y : a ′ z : a ′ ω ) T in P 3 is the set {αa + α ′ a ′ ; (α, α ′ ) ∈ P 1 }; a point on A is thus parameterized by (α, α ′ ) in P 1 .
The line A can be split in two parts cutting it at points a and a ′ . Since the projective space cannot be oriented, to precise these two sets we need to restrict the representative coordinates of a and a ′ ; namely we will assume in the sequel that all fourth coordinates ω of segment's endpoints are non negative. The two parts of A will be denoted by A = {αa + α ′ a ′ ; αα ′ ≥ 0} and à = {αa + α ′ a ′ ; αα ′ ≤ 0}; if neither a nor a ′ is at infinity (i.e. a ω and a ′ ω are non-zero), A is the finite segment and à the "segment" going through infinity. If the points a and a ′ are finite we also like to orient the line A from a to a ′ that is, inside A, we consider decreasing α α ′ . Given two oriented lines A and B we say that the orientation of B is positive with respect to A if the determinant |a b a ′ b ′ | > 0 (with the hypotheses that the fourth homogeneous coordinates are non negative).

Intuitively, this means that, if the orientation of B is positive with respect to A, a screwdriver oriented along A and turning according to B will turn in the positive direction along A, that is it will screw (see figure above).

Lines can be represented using two of their points, but they can also be represented using Plücker coordinates (see [START_REF] Shoemake | Plücker coordinate tutorial[END_REF] for a review of Plücker coordinates). We represent a line by a point of P 5 ℓ = (ℓ 0 : ... : ℓ 5 ). If the line passes through points a and a ′ as before, the Plücker coordinates can be computed as the 2x2 determinants of the coordinates of a and a ′ . In the affine case (a ω = a ′ ω = 1), (ℓ 0 , ℓ 1 , ℓ 2 ) is the external product of a and a ′ and (ℓ 3 , ℓ 4 , ℓ 5 ) is a ′a. A useful operator on these lines is the side operator, which takes two vectors of R 6 ℓ and ℓ ′ , exchanges the first and last three coordinates of ℓ ′ and returns the scalar product of this modified vector with ℓ. It has two particularly interesting properties: a point of P 5 represents a line if and only if the side operator of this point with itself is 0, and two lines intersect if and only if their side operator is 0. Notice that when line ℓ is defined by points a and a ′ and line ℓ ′ is defined by points b and b ′ , the side operator of ℓ and ℓ ′ is |a b a ′ b ′ |, so the respective orientation of lines ℓ and ℓ ′ is the sign of their side operator.

3 A direct approach to transversals to lines and line segments

Algebraic formulation

For any pair of parameters (α, α ′ ) and (β, β ′ ) in P 1 , there is a line through αa+α ′ a ′ and βb+β ′ b ′ that also intersects a line C if and only if the four points αa + α ′ a ′ , βb + β ′ b ′ , c and c ′ are coplanar (note that such a line transversal is not unique if αa + α ′ a ′ = βb + β ′ b ′ ). This condition can be expressed as:

˛αax + α ′ a ′ x βbx + β ′ b ′ x cx c ′ x αay + α ′ a ′ y βby + β ′ b ′ y cy c ′ y αaz + α ′ a ′ z βbz + β ′ b ′ z cz c ′ z αaω + α ′ a ′ ω βbω + β ′ b ′ ω cω c ′ ω ˛= 0
This can be rewritten with a suitable notation as

0 = ˛αa + α ′ a ′ βb + β ′ b ′ c c ′ ˛= (1)
αβ ˛a b c c ′ ˛+ αβ ′ ˛a b ′ c c ′ ˛+ α ′ β ˛a′ b c c ′ ˛+ α ′ β ′ ˛a′ b ′ c c ′ ˛. (2)
Similarly, we obtain that there exists a line through αa + α ′ a ′ and βb + β ′ b ′ that stabs D if and only if:

αβ ˛a b d d ′ ˛+ αβ ′ ˛a b ′ d d ′ ˛+ α ′ β ˛a′ b d d ′ ˛+ α ′ β ′ ˛a′ b ′ d d ′ ˛(3) = 0. (4)
We have the following lemma.

Lemma 1 There exists a line through αa + α ′ a ′ and βb + β ′ b ′ that intersects lines C and D if and only if ((α, α ′ ), (β, β ′ )) is solution of Equations ( 1) and [START_REF] Devillers | Algebraic methods and arithmetic filtering for exact predicates on circle arcs[END_REF]. Furthermore, such a solution corresponds to a unique line transversal unless αa + α ′ a ′ = βb + β ′ b ′ and that point is either coplanar with lines C and D or on C or D.

Proof: If a line through αa + α ′ a ′ and βb + β ′ b ′ intersects lines C and D, the above discussion implies that ((α, α ′ ), (β, β ′ )) is solution of Equations (1-4). Conversely, suppose that (α, β) is solution of Equations [START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF][START_REF] Brönnimann | Transversals to line segments in three-dimensional space[END_REF][START_REF] Cox | Ideals, Varieties and Algorithms[END_REF][START_REF] Devillers | Algebraic methods and arithmetic filtering for exact predicates on circle arcs[END_REF]. If the two points αa + α ′ a ′ and βb + β ′ b ′ are distinct, then the line through them is unique and Equations (1-4) imply that it intersects C and D. On the other hand, if αa+α ′ a ′ = βb+β ′ b ′ , Equations (1-4) imply that there exists a line through this point and line C and a line through this point and line D, but these two lines may be distinct; it is however straightforward that there exists a line through αa + α ′ a ′ = βb + β ′ b ′ that intersects lines C and D because a point and two lines always admit a line transversal in P 3 . Indeed, if the point is on line C, any line through this point and D is a transversal and there are infinitely many transversals. Otherwise, the point and C define a plane. If D is in that plane or contains the point, any transversal to the point and C also intersects D and there are infinitely many transversals. Otherwise D intersects the plane in a single point which, together with αa + α ′ a ′ , defines a unique transversal.

Lemma 1 directly implies the following corollary.

Corollary 2 There exists a line that intersects segments A and B and lines C and D if and only if Equations ( 1)-( 4) admit a solution ((α, α ′ ), (β, β ′ )) such that αα ′ and ββ ′ are non-negative.

We now show how Equations ( 1) and ( 4) can be transformed into degree-2 equations in (α, α ′ ) or (β, β ′ ) and into the equation of a line.

By considering Equations ( 1) and ( 4) as linear equations in variable (β, β ′ ) with parameter (α, α ′ ) the system admits at least one solution only if this determinant is 0:

˛α |a b c c ′ | + α ′ |a ′ b c c ′ | α |a b d d ′ | + α ′ |a ′ b d d ′ | α |a b ′ c c ′ | + α ′ |a ′ b ′ c c ′ | α |a b ′ d d ′ | + α ′ |a ′ b ′ d d ′ | ˛.
(

) 5
This can be rewritten as

Fαα 2 + Gααα ′ + Hαα ′2 = 0 (6)
where

Fα = ˛|a b c c ′ | |a b d d ′ | |a b ′ c c ′ | |a b ′ d d ′ | ˛(7) Gα = ˛|a b c c ′ | |a ′ b d d ′ | |a b ′ c c ′ | |a ′ b ′ d d ′ | ˛+ ˛|a ′ b c c ′ | |a b d d ′ | |a ′ b ′ c c ′ | |a b ′ d d ′ | ˛(8) Hα = ˛|a ′ b c c ′ | |a ′ b d d ′ | |a ′ b ′ c c ′ | |a ′ b ′ d d ′ | ˛. (9)
Similarly considering (α, α ′ ) as the variable, we get

F β β 2 + G β ββ ′ + H β β ′2 = 0 (10)
where

F β = ˛|a b c c ′ | |a b d d ′ | |a ′ b c c ′ | |a ′ b d d ′ | ˛(11) G β = ˛|a b c c ′ | |a b ′ d d ′ | |a ′ b c c ′ | |a ′ b ′ d d ′ | ˛+ ˛|a b ′ c c ′ | |a b d d ′ | |a ′ b ′ c c ′ | |a ′ b d d ′ | ˛(12) H β = ˛|a b ′ c c ′ | |a b ′ d d ′ | |a ′ b ′ c c ′ | |a ′ b ′ d d ′ | ˛. ( 13
)
Finally by eliminating αβ between Equations ( 1) and ( 4) we get

Fααβ ′ + F β α ′ β + H αβ α ′ β ′ = 0 (14)
where

H αβ = ˛|a b c c ′ | |a b d d ′ | |a ′ b ′ c c ′ | |a ′ b ′ d d ′ | ˛. ( 15
)
Note that the coefficients F α and F β in Equation ( 14) are the same as in Equations ( 6) and [START_REF] Yap | Towards exact geometric computation[END_REF]. Note also that, if one of these coefficients is nonzero, Equation ( 14) is the equation of a line whose equation in affine space is

F α α α ′ +F β β β ′ +H αβ = 0. Finally, note that H αβ = Gα+G β 2
; indeed, by exchanging the diagonals in the two determinants defining G α , we get that 6). Note that one can easily prove that ∆ is also the discriminant G 2 β -4F β H β of Equation ( 10) by developing the two expressions.

G α = H αβ + H ′ where H ′ = |a ′ b c c ′ | |a ′ b d d ′ | |a b ′ c c ′ | |a b ′ d d ′ | and similarly that G β = H αβ -H ′ . Let ∆ = G 2 α -4F α H α be the discriminant of Equation (

Remark 3

The discriminant ∆ also appears naturally as the determinant of the matrix whose coefficients are the pairwise side operators of the lines A, B, C and D:

˛0 |a a ′ b b ′ | |a a ′ c c ′ | |a a ′ d d ′ | |a a ′ b b ′ | 0 |b b ′ c c ′ | |b b ′ d d ′ | |a a ′ c c ′ | |b b ′ c c ′ | 0 |c c ′ d d ′ | |a a ′ d d ′ | |b b ′ d d ′ | |c c ′ d d ′ | 0 ˛= ∆.
With ∆ written this way, it is easy to see that exchanging the role of any two lines among A, B, C, D does not change ∆. We can also notice that ∆ = 0 if and only if there exists a linear combination of the Plücker coordinates of A, B, C and D that has a null side operator with all four lines (and thus with itself ); this vector is either null (the four lines are linearly dependent) or represents the Plücker coordinates of a common transversal.

We now prove the following lemmas stating some equivalences between these equations.

Lemma 4 If F α F β = 0 then Systems ( 1)-( 4), ( 6)-( 14), and ( 10)-( 14) are equivalent.

Proof:

We have already seen that Equations ( 1) and ( 4) imply Equations ( 6), [START_REF] Yap | Towards exact geometric computation[END_REF], and (14). Assume now that F α F β = 0 and Equations ( 6) and ( 14) are satisfied. Since F α = 0, any solution of Equation ( 6) is such that α ′ = 0. One can easily verify that equations ( 1), ( 6) and ( 14) satisfy the relation

α ′ F β .(1) + β ′ |a b c c ′ | .(6) = (α |a b c c ′ | + α ′ |a ′ b c c ′ |).(14).
Since α ′ F β = 0, Equation ( 1) must be satisfied. The proof that Equation ( 4) is satisfied is similar, as well as the equivalence between Systems (1)-( 4) and ( 10)-(14).

Remark 5 Note that exchanging the roles of a and a ′ , which is equivalent to exchanging α and α ′ , yields very similar equations; precisely, it exchanges F α and H α , leaves G α and ∆ unchanged, changes the sign of F β , G β and H β (which means that Eq. ( 10) is unchanged), and H αβ takes the new value of Remark 6 The above remark implies that, if F α or H α is non-zero and F β or H β is non-zero, then after exchanging the role of a and a ′ if F α = 0 and exchanging the role of b and b ′ if F β = 0, the new equations are such that F α F β = 0 and Lemma 4 applies. 6) identically vanishes then System ( 1)-( 4) has infinitely many solutions. If F α = H α = 0 and G α = 0, then System ( 1)-( 4) has two solutions.

Lemma 7 If Equation (

Proof: If Eq. ( 6) identically vanishes then System (1)-( 4) admits infinitely many solutions since for any solution of Eq. ( 6), that is for any (α, α ′ ), there exists a (β, β ′ ) such that ((α, α ′ ), (β, β ′ )) is solution of the system or (α, α ′ ) cancel the coefficients of β in Equations ( 1) and ( 4); in the latter case, ((α, α ′ ), (1, 0)) is solution of the system (see [START_REF] Cox | Ideals, Varieties and Algorithms[END_REF]Th. 3,Ch. 3,[START_REF] Everett | Accepted in Computational Geometry: Theory and Applications[END_REF] for a reference on resultants).

If F α = H α = 0 and G α = 0, then the solutions of Eq. ( 6) are (1, 0) and (0, 1). Substituting these solutions in Eq. ( 1)-( 4) gives the solutions. When (α, α ′ ) = (1, 0), if Equation (1) does not identically vanish, it yields (β,

β ′ ) = (|a b ′ c c ′ | , -|a b c c ′ |) and otherwise Equation (4) yields (β, β ′ ) = (|a b ′ d d ′ | , -|a b d d ′ |) (which is necessarily well defined in P 1 since, if all four deter- minants are zero, then G α = 0). Similarly, for (α, α ′ ) = (0, 1), (β, β ′ ) = (|a ′ b ′ c c ′ | , -|a ′ b c c ′ |) or (|a b ′ c c ′ | , -|a b c c ′ |).
We get the following lemma by exchanging the role of lines A and B in Lemma 7. [START_REF] Yap | Towards exact geometric computation[END_REF] identically vanishes then System (1)-( 4) has infinitely many solutions. If F β = H β = 0 and G β = 0, then System (1)-( 4) has two solutions.

Lemma 8 If Equation

Geometric interpretation

We give here a geometric interpretation of the above algebraic formulationwhich will be useful in the proofs of later lemmas. We give this interpretation in the affine parameter space, that is in the αβ-plane with α ′ = β ′ = 1. We assume that the four lines or segments are defined by Euclidean points given in homogeneous form with their fourth coordinates equal to one. Recall that a point αa + a ′ on line A is on segment A for α ∈ [0, +∞] and similarly for points on B. We first consider the case of four lines or segments and then the case where a fifth line or segment is added.

Four lines or line segments

Refer to Figure 1. A point in the αβ-space corresponds to the 3D line going through points αa+a ′ and βb+b ′ (if these two points are distinct). Equation [START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF] defines in the αβ-space the conic corresponding to the lines passing through A, B, and C. Similarly, Equation (4) defines the conic corresponding to the lines passing through A, B, and D. These two conics and the line defined in αβspace by Equation ( 14) are in the same pencil and intersect in the same set

α β 0 Equation (2)
Equation ( 1) Equation ( 5)

α 1 α 2 β 2 β 1

Adding a fifth line

If we add a fifth line E, then we get another conic in αβ-space: (

) 17
This conic can belong to the same pencil as Equations ( 1), ( 4) and ( 14). Then the two stabbing lines of A, B, C and D stab also E. Otherwise locating points (α i , β i ) with respect to this conic allows to determine if E stabs or turn positively or negatively around the stabbing lines.

The three Equations ( 1), ( 4) and ( 17) define three planes in αβζ-space whose intersection is a point M if the planes are affinely independent.

The five lines admit a common stabbing line if the point M lies on the quadric ζ = αβ which can be verified by solving the system of Equations ( 1), ( 4) and ( 17) and substituting in the quadric.

Number of transversals to lines and segments 4.1 Number of transversals to four lines

Lemma 9 Given four lines, there is a predicate of degree 12 in the Cartesian coordinates of their defining points to determine whether they admit 0, 1, 2, or infinitely many transversals.

Proof:

We first consider the number of solutions to the system of Equations ( 1) and ( 4); let S denote that system. By Lemmas 7 and 8, if Equation ( 6) or [START_REF] Yap | Towards exact geometric computation[END_REF] identically vanishes then S has infinitely many solutions; otherwise, if F α = H α = 0 or F β = H β = 0, then S has two solutions. Otherwise, at least one of F α or H α is non-zero and at least one of F β or H β is non-zero. By Remark 6, we can then apply Lemma 4 after exchanging, if needed, the roles of α and α ′ and of β and β ′ . The number, zero, one, or two, of solutions to S is then given by the sign (negative, null, or positive) of the discriminant ∆ of Equation [START_REF] Everett | Accepted in Computational Geometry: Theory and Applications[END_REF]. Moreover, by Remark 5, this discriminant is not modified by the exchange of α and α ′ and of β and β ′ , thus the number of transversals is given by the sign of the discriminant of Equation ( 6) without any exchange. Now, by Lemma 1, the number of solutions of S is the number of transversals to the four lines except if lines A and B intersect in x and either x, C and D are coplanar or x ∈ C or x ∈ D in which cases there are infinitely many line transversals. We notice that in these cases, ∆ = 0; indeed, we first note that the discriminant ∆ does not change if we exchange the role of any two lines among A, B, C and D, as shown in Remark 3. If the four lines have infinitely many common transversals, there must be at least one of these four lines, say A without loss of generality, such that every points on A belongs to common transversals. This implies that Equation ( 6) has infinitely many solutions and thus that its discriminant ∆ is 0.

To sum things up, if ∆ > 0, there are two transversals, if ∆ < 0, there is no transversal and if ∆ = 0, there may be either a unique transversal or infinitely many transversals. Precisely, if ∆ = 0, there are infinitely many transversals if and only if lines A and B intersect at a point that is coplanar with lines C and D or at a point that lies on C or D.

The discriminant ∆ is a degree 16 irreducible polynomial in the homogeneous coordinates of the points defining the lines. If the points are given with affine coordinates, this degree drops to 12 (and this degree 12 polynomial is irreducible as well). Finally, if ∆ = 0 deciding if there is one or infinitely many transversals is done with an additional predicate of degree lower than 12, and the maximal degree remains 12.

Number of transversals to four line segments

We study here the degree of predicates for determining the number of transversals to segments. We study first the case of 1 segment and 3 lines and the case of 2 segments and two lines; the case of four segments will follow.

Lemma 10 Given a line segment and three lines, there is a predicate of degree 12 in the Cartesian coordinates of their defining points to determine whether they admit 0, 1, 2, or infinitely many transversals.

Proof: If the predicate defined by Lemma 9 concludes to the existence of no or an infinity of stabbing lines, then the result applies also for line segment A except in very degenerate cases.

In the case of one or two line transversals to A, B, C, and D, it remains to determine whether they intersect the line segment A. This is equivalent to determine the sign of the solutions of Equation ( 6).

In fact it is more efficient to first attempt to locate the roots of Equation ( 6), and then only resolve Lemma 9 (i.e., evaluate the discriminant ∆) when the root location is not complete [START_REF] Devillers | Algebraic methods and arithmetic filtering for exact predicates on circle arcs[END_REF][START_REF] Karavelas | Root comparison techniques applied to computing the additively weighted Voronoi diagram[END_REF]. Precisely, as we show below, we need to evaluate ∆ only to distinguish between some cases where Equation ( 6) has no real roots and the case where it has two positive real roots, other cases e.g. with one or two negative real roots can be identified with lower degree evaluations. If F α = 0 or H α = 0, the signs of the roots of Equation ( 6) are obvious, so we can restrict ourselves to the case where F α = 0 and H α = 0. We further assume that F α > 0 (the case F α < 0 is similar). We define f (x) = F α x 2 + G α x + H α . Figure 2 shows possible graphs of f . If f (0) = H α < 0, f has two real roots, one is positive and the other one is negative (case (a) on the figure). Otherwise, if f ′ (0) = G α ≥ 0 (case (b)), the minimum of f happens for a non-positive value of x and f has no non-negative root (it has either two negative roots or Proof: We first write the Plücker coordinates of the five lines in a 6x5 matrix. Two lines intersect if and only if their side operator is 0. This means that a line T is a common transversal to all five lines if and only if the vector of its Plücker coordinates (properly reordered) is in the kernel of this matrix. The five lines might have linearly dependent Plücker coordinates, in which case we can forget about one of them, because intersecting the other four implies intersecting this one as well. If the lines are linearly independent (which is the generic case, even for five lines that admit a common transversal), the 5x5 minors of the matrix define a generator of the dimension 1 kernel of the matrix. All that remains to be seen is whether this vector corresponds to a line, that is whether its self side operator is 0. This gives a degree 15 irreducible polynomial in the Cartesian coordinates, or a degree 20 irreducible polynomial in the homogeneous coordinates.

Remark 14 This polynomial also appears naturally (up to a factor 2) as the determinant of the matrix whose coefficients are the pairwise side operators of the lines A, B, C, D and E:

˛0 |a a ′ b b ′ | |a a ′ c c ′ | |a a ′ d d ′ | |a a ′ e e ′ | |a a ′ b b ′ | 0 |b b ′ c c ′ | |b b ′ d d ′ | |b b ′ e e ′ | |a a ′ c c ′ | |b b ′ c c ′ | 0 |c c ′ d d ′ | |c c ′ e e ′ | |a a ′ d d ′ | |b b ′ d d ′ | |c c ′ d d ′ | 0 |d d ′ e e ′ | |a a ′ e e ′ | |b b ′ e e ′ | |c c ′ e e ′ | |d d ′ e e ′ | 0
˛.
It is easy to see that this polynomial is 0 if and only if there exists a linear combination of A, B, C, D and E that has a null side operator with all five lines (and thus with itself ) [START_REF] Mourrain | [END_REF]; this vector is either null (and the five lines are linearly dependent) or represents the Plücker coordinates of a common transversal.

Notice that in the case where the five lines have linearly independent Plücker coordinates and they have a common transversal, we managed to compute the Plücker coordinates of this transversal as a rational fraction in the input. So if all the input has rational coordinates and we can determine that 4 given lines have 2 transversals and they have irrational coordinates, then the only way a fifth line can intersect one of these transversals is if its Plücker coordinates are a linear combination of the Plücker coordinates of the 4 initial lines, and then it intersects both transversals.

Lemma 15 Given five line segments, there is a predicate of degree 15 in the Cartesian coordinates of their endpoints to determine whether they admit 0, 1, 2, 3, 4, 5, or infinitely many transversals.

Proof: We start by presenting an alternative approach to the previous lemma.

If Equation ( 17) is a linear combination of Equations ( 1) and (4), that is all 4 of the 3 × 3 determinants constructed with the coefficients are zero, then one of the lines, say E, is such that any line stabbing A, B, C, D also stabs E. Thus the answer is obtained by applying Lemma 9 to lines A, B, C and D.

In αβζ-space, the above three equations can be solved to compute the coordinates of the intersection point M as a quotient of 3 × 3 determinants built on the coefficients of these equations. Then, we substitute the coordinates of M in the quadric equation ζ = αβ, if the equation is verified , there is one stabbing line, otherwise there is no stabbing line.

Using Cartesian coordinates, the degree of this predicate is 18. However, there is only one polynomial of degree 18 involved in this predicate (the next polynomial of highest degree has degree 15) and it is reducible. We first notice that the side operator of lines A and B is an irreducible factor of degree 3 of this polynomial. This is quite natural because, if lines A and B intersect, choosing (α, α ′ ) and (β, β ′ ) so that the two parametric points are the same solves all equations like 1, 4 and 17 whereas there may not be any common transversal. The remaining degree 15 factor is exactly the polynomial computed in the previous approach. Notice that proving that the degree 18 polynomial is really the product of the degree 15 and the degree 3 polynomials is not trivial. Indeed, their developed forms have too many terms for a software like Maple running on a real computer to compute all of them. However, one can notice that the functions they define are invariant under any transformation that preserves the determinants of 4-tuples of points. Applying a rigid motion to send a to the origin and a ′ on one of the axes, we obtain polynomials in fewer variables, that Maple is able to identify. This is enough to prove that the polynomials define the same function and thus are identical.

Coming back to the proof of Lemma 15, we first note that by proceeding as before, and by verifying that the coordinate (α, α ′ ) of M satisfies αα ′ ≥ 0, we can determine, with a predicate of degree 15, the number of line transversals to one segment and four lines.

Assuming we are in the case where the 5 lines supporting the segments have a single common transversal, we now evaluate this predicate for (A, B, C, D, E), (A, B, C, D, E), (A, B, C, D, E), (A, B, C, D, E) and(A, B, C, D, E).

If we find one stabbing line in all cases then there is exactly one stabbing line for (A, B, C, D, E). If we find no stabbing line in at least one case, then there is no stabbing line for (A, B, C, D, E). As in Lemma 13 the predicate has degree 15 if we never compute the degree 18 polynomial and only deduce its sign from the signs of the degree 3 and 15 polynomials.

Degenerate cases need a more complicated handling. When one line is "useless", meaning that intersecting it is a mere consequence of intersecting the others, we cannot simply ignore the segment as we were ignoring the line. Instead, we use an equation like Equation 1where B is the "useless" line in order to translate the restriction on the values of (β, β ′ ) in terms of (α, α ′ ). We can then ignore this segment and only remember that the possible values of (α, α ′ ) are less than the initial set with αα ′ ≥ 0.

Lemma 16 Given six or more lines or line segments, there is a predicate of degree 15 in the Cartesian coordinates of their defining points to determine how many transversals they admit.

Proof: If the input only includes lines, we can write all their Plücker coordinates in a matrix. If the rank is at most 3 then there are infinitely many common transversals. Otherwise we keep four independent lines and check that they have two transversals (not zero). For each other line we check which of the two transversals it intersects using Lemma 13. The solution is then composed of those of the 2 transversals that were intersected by all the lines.

For segments, there are two cases. If the lines have finitely many transversals, combining the previous technique with Lemma 15 solves the problem. Otherwise the lines have infinitely many common tangents. This case is mostly handled in [START_REF] Brönnimann | Transversals to line segments in three-dimensional space[END_REF].

Transversals to four segments and a triangle

Lemma 17 Let ℓ be a line transversal to four lines that admit finitely many transversals and let T be a triangle. There is a predicate of degree 15 in the Cartesian coordinates of the points defining the lines and the triangle to determine whether ℓ intersects (properly or not) T .

Proof:

We work in αβζ space in a manner similar to Lemma 15. We need to know if a point S i = α i , β i , α i β i , (i = 1, 2) corresponding to a stabbing line is above or below the planes of Equations (17 k ) (where E k for k = 1 . . . 3 are the edges of the triangle) to locate the stabbing lines with respect to the triangle, but we cannot eventually compute the coordinates of this point which involve square roots. Equivalently, we can compute M k the intersection of the plane defined by Equations ( 1), ( 4) and (17 k ) and M + ∞ the direction of the line defined by Equations ( 1) and [START_REF] Devillers | Algebraic methods and arithmetic filtering for exact predicates on circle arcs[END_REF]. Notice that all points S 1 , S 2 , M 1 , M 2 and M 3 are on the same line in αβζ space whose direction is M + ∞ . Since it is possible to determine if a "point at infinity" on that line is above/below the planes of Equations (17 k ) and the quadric ζ = αβ, then locating M 1 , M 2 and M 3 with respect to the quadric allows to deduce the position of S 1 and S 2 with respect to the planes (17 k ). As in Lemma 15 the predicate has degree 15.

Given a line transversal ℓ to a set S of segments, a triangle T occludes ℓ if ℓ intersects T and if there exist two segments in S whose intersections with ℓ lie on opposite sides of T .

Lemma 18 Let ℓ be a line transversal to four line segments that admit finitely many transversals and let T be a triangle. There is a predicate of degree 15 in the coordinates of the points defining the segments and the triangle to determine whether T occludes ℓ.

Proof: This test is performed in two steps. First we check whether the transversal intersects the triangle as in Lemma 17. Then, assuming the transversal does intersect the triangle, for each of the four supporting lines we check where its intersection point with the transversal is with respect to the plane supporting the triangle. If all four intersection points are on the same side of the plane, the transversal is not occluded. If there are points on both sides of the plane, the transversal is occluded.

In order to check on which side of the plane supporting T the point of intersection of A and ℓ is, we compute the sign of the determinant |T 1 T 2 T 3 αa+ α ′ a ′ | where T i are the 3 vertices of T . This can be rewritten as:

α|T 1 T 2 T 3 a| + α ′ |T 1 T 2 T 3 a ′ |
The two coefficients of this polynomial in (α, α ′ ) are degree 3 polynomials in the input. Remember that (α, α ′ ) is a solution of Equation 6. Evaluating the sign of a polynomial at a root of an other polynomial amounts to sorting their respective roots, which means computing their resultant, that is a degree 12 polynomial in the input. The computation is exactly the same for the intersection points of ℓ with B, C and D. 1 and β * 2 as solutions of a degree 2 equation with degree 12 coefficients that we have to compare with β * 3 and β * 4 which are solutions of a degree 2 equation with degree 6 coefficients. This yields a degree 36 predicate (degree 48 with homogeneous coordinates).

Sorting transversals around a line

The degree 36 in the above predicate is likely not optimal. Indeed, after replacing the coordinates of the points by values of the type xt + y where x and y are pseudo-random integer values, the resulting polynomial in t can be factored in Q[t] into one irreducible factor of degree 24 and two squared factors of degree three (which are the side operator of A with B and B * , respectively). This implies that with high probability, the polynomial of degree 36 is reducible. Note that the polynomial of degree 36 cannot successfully be factored in Maple because it is too large.

Note also that if lines B and B * coincide then it is straightforward to show that the degree of the predicate drops to 24 (which can be presumably factored, as above, into two polynomials with degrees 21 and 3).

Figure 1 :

 1 Figure 1: Geometric interpretation in αβ-space.

  αβ ˛a b e e ′ ˛+ α ˛a b ′ e e ′ ˛+ β ˛a′ b e e ′ ˛+ ˛a′ b ′ e e ′ ˛= 0.

Figure 2 :

 2 Figure 2: Graph of f depending on the signs of f (0), f ′ (0), and ∆.

Lemma 19

 19 Given seven lines A, B, C, D, B * , C * , D * with two stabbing lines S 1 and S 2 to A, B, C, D, and two stabbing lines S 3 and S 4 to A, B * , C * , D * , there is a predicate of degree 36 in the Cartesian coordinates of the points defining the lines for ordering S 1 , S 2 , S 3 and S 4 around A. Proof: Writing that |a a ′ βb + β ′ b ′ β * b * + β * ′ b * ′ | = 0 describes how β and β * corresponding to the same sweeping plane correspond together. This equation is similar to Equation (1). Writing β in terms of β * and substituting in Equation (10) we get β *

  This work has been partially supported by INRIA-ARC Visi3d and the 3rd McGill -INRIA Workshop on Computational Geometry in Computer Graphics. int CountingPredicate2Segments2Lines (Point a,a',b,b',c,c',d,d') If sign(Fα) = sign(Hα) If sign(Gα) = sign(Fα) there is no stabbing line: return 0; ∆α = G 2 α -4FαHα If ∆α < 0 there is no stabbing line: return 0; there are 2 lines stabbing A, B, C, D: Na = 2; else there is 1 line stabbing A, B, C, D: Na = 1; If sign(F β ) = sign(H β ) If sign(G β ) = sign(F β ) there is no stabbing line: return 0; else there are 2 lines stabbing A, B, C, D: N b = 2, return Na; else there is 1 line stabbing A, B, C, D: N b = 1; If Na = 2: return 1; If sign(Fα) = sign(F β ) there is 1 line stabbing A, B, C, D: return 1; else there is no stabbing line: return 0; }

Acknowledgments Authors thank for fruitful discussions in past years Hervé Brönnimann, Olaf Hall-Holt, Bernard Mourrain, Sylvain Petitjean and Fabrice Rouillier.

* This work was partially supported by INRIA ISA-McGill Équipe associée

no root). Otherwise we need to evaluate the sign of ∆ to distinguish between case (c) where f has two positive real roots and case (d) where it has none.

Lemma 11 Given two line segments and two lines, there is a predicate of degree 12 in the Cartesian coordinates of their defining points to determine whether they admit 0, 1, 2, or infinitely many transversals.

Proof: Applying Lemma 10 once for A, B, C and D and once for A, B, C and D gives the solution in most cases. One case where this does not give the answer is when A, B, C and D have infinitely many transversals. Then A, B, C and D may have 0, 1, 2 or infinitely many transversals, see [START_REF] Brönnimann | Transversals to line segments in three-dimensional space[END_REF] for details.

The other case that remains is when A, B, C and D have two common transversals, one intersects A and one intersects B. Indeed, we need to check whether the transversal that intersects A is the one that intersects B or the one that intersects B. For the sake of simplicity, we omit the case where a transversal goes through the endpoint of one of the segments. The values of (α, α ′ ) that correspond to the two transversals are (α 1 , 1) and (α 2 , 1) with α 1 < 0 < α 2 . Similarly the values of (β, β ′ ) are (β 1 , 1) and (β 2 , 1) with β 1 < 0 < β 2 . The two transversals then either match α 1 with β 1 and α 2 with β 2 or α 1 with β 2 and α 2 with β 1 . Equation 14 enables us to distinguish the two cases. Indeed, it describes a line that contains the two points (α i , β j ) that are solution. If its slope is positive, we are in the first case, and otherwise we must be in the second case.

Lemma 12 Given four line segments, there is a predicate of degree 12 in the Cartesian coordinates of their endpoints to determine whether they admit 0, 1, 2, 3, 4, or infinitely many transversals.

Proof: Similarly to Lemma 11, the case where the four lines admit infinitely many transversals can lead to 0, 1, 2, 3, 4, or infinitely many transversals to the line segments (see [START_REF] Brönnimann | Transversals to line segments in three-dimensional space[END_REF] for details) and is handled separately.

When A, B, C and D have a finite number of common tangents, we evaluate Lemma 10 for (A, B, C, D), (A, B, C, D), (A, B, C, D) and(A, B, C, D). If we find two stabbing lines in all cases then there are two stabbing lines for (A,B,C,D). If we find no stabbing line in at least one case, then there is no stabbing line for (A, B, C, D). Otherwise assume without loss of generality that (A, B, C, D) has only one stabbing line, then we will use Lemma 11 for (A, B, C, D), (A, B, C, D) and(A, B, C, D) and the final answer is the minimum of the three answers. As in Lemma 9 the predicate has degree 12 (16 with homogeneous coordinates).

More lines and segments

Lemma 13 Given five lines, there is a predicate of degree 15 in the Cartesian coordinates of their defining points to determine whether they admit 0, 1, 2, or infinitely many transversals.

Appendix: towards an actual implementation

We give here a pseudo code version of the counting predicate for two line segments and two lines in general position based on strategies described in Section 4.

The aim of this pseudo-code is to show that the amount of computation remains quite reasonable. We choose this particular predicate, since other counting predicates reduce to several calls to this one (with less lines and more segments) or are simpler (with less segments and more lines).