Keywords:

  L'archive ouverte pluridisciplinaire

Introduction

Paris, invisible city: The plasma

Everything in the city remains invisible, everything and, over and above everything, the city taken as a whole.

One might say that we now have satellite maps enabling us to zoom in on every level, so conveniently that in a few clicks we can switch from the entire Ile-de-France to the roof of our building. We do therefore have the right, for once, with regard to Google Earth or the National Geographic Institute's site, to talk of a panopticon, since we ''embrace the entire city'' and are able, at the same time, to keep delving down into its minutest detail.

Well no, we do not actually ''embrace'' anything, we do not see anything, we do not ''keep going down''! The illusion is strong, I admit; it is such fun roller-coastering up and down from the whole to the parts until your stomach turns, but if you think you are omniscient, you are kidding yourself. It is like confusing a video game with actually playing a rugby match. Moreover, satellite photos date; they are not in ''real time''. What you see is the city, your neighbourhood, your building, as they were a few months or years back, and in any case in another season, from a different light, and from the most improbable point of viewand the least informative. What does it matter to you to see the roof of your building? Are you an installer of antennae or a chimney sweep? The images are refreshed at intervals that are far too long for you to be faced with anything other than an illusion of seeing everything live -not to mention pixels that instantly mute into big brownish squares as soon as you go off the beaten track.

What would the view of Paris be if it could be refreshed so swiftly that you found yourself in real time and, above all, real space?

To refresh a space and make it a little more realistic, it is not a map that we need, irrespective of the number of pixels, but oligopticons. By this neologism I mean narrow windows through which, via numerous narrow channels, we can link up with only some aspects of beings (human and non-human) which together comprise the city. An official at the police prefecture watches the videos installed at Paris' main intersections. What does he see? A lot, from very close up; hence, the word ''oligo-ptic''. But videos film only certain aspects of what happens at intersections, and only that which serves to alert their colleagues on siteif they are able to reach them by radio and if these colleagues are willing to obey. Another example: you open the yellow pages of the Paris telephone directory to find a plumber, and you find one. But you have seen virtually nothing, apart from pages and adverts, even though in your hands you do have ''all'' the artisans and trades in Paris. The map is no different to the directory: it simply sets out lists of sites, by longitudes and latitudes, whereas the directory does so by alphabetical order, with trades and names. No one would consider the big volume of Yellow Pages to be Paris, so why consider the map of Paris to be the territory?

The illusion of the zoom is so deceptive because of the impression of continuity. Because computers can so easily adjust pixels to all scales and link up data (ultimately, they are never more than zeros and ones saved as electric potential on sheets of silicon), they enable us to believe that between all these points of view there is a passage with no solution of continuity. And yet there is no straightforward relationship, no bridges, between what the police officer sees on the monitors at the Paris prefecture and what you see in the pages of the directory when you point to the name of your favourite plumber. We have really got to avoid connecting these two oligopticons in the same space, as if they were two points of view of the same whole. They are not joined. They are incommensurable -even if Google, cleverly using the new property of all this data that can now be arranged in digital files, manages to superpose your plumber's address with the little bunch of pixels that marks the location of his workshop, seen from the sky. Yes, it is true, digitization does enable us to throw some bridges between oligopticons that were separate until now, but that still doesnot make a panopticon. Finding your plumber's name and the photo of his street superposed on a screen still doesnot put you in the position of the Divine Eyeespecially since all you have done is to pay your attention and some money for the extension of a new network, that of the firm Google, which makes the plumber's business pay hard cash for your little mouse clicks. The most complete panopticon, the most integrated software, is never more than a peep show.

One might say that it is absurd to seek real space on a map, on a screen, in a directory, and that Paris can be seen via the only channel that is realistic and experienced firsthand: strolling, walking, wandering around. No one but the pedestrian, doing window-shopping, drinking a coffee at a pavement café, rummaging about the flea market, handing out flyers at the entrance to the metro, or chatting up the girls or boys on the Grands Boulevards, really grasps the space of the City of Light. Thus, ultimately, only the subjective, personalized, individualized view is objective. From this point of view, that of maps, control rooms, lists and directories can offer no more than an abstraction of space and life in the city. There is no lack of writers, sociologists, psychologists, even town planners, who maintain that the city can be apprehended in concreto only by an individual who moves around in the framework that it offers.

Yet there is nothing more abstract than this point of view, nothing less realistic -apart from the illusory zoom sliding, without the slightest tremor, from the European continent to the Beaubourg square in Paris, continuously changing scale. Ultimately, a city cannot be the framework within which an individual moves, simply because this framework itself is made of nothing more than traces left by other individuals who have moved about or are still there, in place. Favouring the point of view of the paedestrian, the person strolling, wondering around, prevents us from understanding what is so particular about living in the city; it cuts us off from those channels that precisely enable us not to distinguish the frame from the person moving about within it. A space can become more real only if we are able to follow these channels.

One might say that a tourist, for example, is only passing through Paris, and this clearly reflects the separation between the individual who is visiting and the framework that is being visited: he or she passes through, Paris remains. The stroller is set against a background. And yet this is merely a very superficial point of view -as superficial as the zoom. First because tourists are generally in groups, and are therefore a fraction of a touristic infrastructure encompassing the Bateaux-Mouches, the Tourist Bureau of Paris, the offices of officially approved translators, the drivers of coaches and the problems they have parking their iron beasts. Do not forget, moreover, just how much infrastructure is needed to be able to walk around Paris. From this point of view, we all have ''reduced mobility''.

This touristic infrastructure has shaped the city in so many ways that the visitor is no longer outside a set frame on which he or she will have no influence. ''Frame'' and ''visitor'': two perfectly reversible ways of talking. In the final balance the tourist may be worth no more than a few dollars, but without this infrastructure there would be no tourists at all and Paris would be sleepy and provincial, somewhere ''outside of the touristic circuits''. And that is without counting all the renovations of buildings that had no aim other than pleasing the passers-by, the campaigns (always to no avail) to attempt to make taxi drivers ''friendly to foreign visitors'', and the countless clichés in films which make all the shots by these same tourists, from the Place du Tertre or Notre-Dame, as inevitable as they are accessible.

Clearly, whoever claims to do justice to the visitors' subjective and individual points of view without taking into account the infrastructure in which they move about, would give a version of the city that is even more illusory than someone who believed the map of Paris was the city itself. Between the visitor and the visited framework, there is only the difference between the nth + 1 participant in the continuous elaboration of Paris, and all those who have preceded him or her on the paths he or she effortlessly follows. Hence there is a path -tenuous, I admit -enabling us to make equivalent the ''frame'' and the individual situated ''within'' it. The frame is they, since the survival of the infrastructure partially depends on the money that visitors will leave behind and the good impression that they will have of their visit. On the other hand, the visitors are to some extent this frame, since from now on their biography, in a part of their trajectory, will include the fact that they have ''done Paris'', whereas Paris ''has been done'' (admittedly, to a very small degree) by such-and-such particular visitors, who went through this turnstyle at the Pompidou Centre, added their coffee to the list of drinks served at the Café Flore, etc. All that is needed is a bit of astuteness to morph from one into the other.

But this infrastructure is society, one might say, in which, ''of course'', one must always ''situate'' tourists, so as not to believe that they are ''really'' detachable individuals. By following their desire to visit Paris, they merely responded to the tour operators' advertising campaigns and, going even further back (or deeper down), to the interests of the firms whose business is globalizing tourism. Just as there is a zoom in geography, enabling us continuously to slide from the scale of the planet to the Place Beaubourg, there seems to be a zoom in sociology, from Capitalism to the poor Chinese tourist having his portrait done by a dauber on the corner of the Place du Tertre. From this point of view, Paris is situated ''in'' Europe and ''in'' Capitalism, each place being pinpointed by its longitude and latitude, and each individual by a certain overlapping of interests and passions.

And yet, while the geographic zoom has the appearance of likelihood, the same cannot be said for the sociological zoom. The former is merely a procedure of displaying the same digital file that distributes pixels according to the requested image size, a simple matter of DPI; the latter does not even have that resource. As soon as I leave the individual tourists to go towards ''that in which'' they are situated, I start no longer knowing what I am talking about. I settle for a vague gesture, saying ''All that is no coincidence, there are big interests behind it''. At the bar counter where I pronounce this definitive sentence, as my stooges' nod their heads in agreement, I think I have said enough. . . Images of the social bear too much of a resemblance to those T-shaped maps in medieval geography: surrounding them lies an Ocean about which nothing is known, except that it is vast and dangerous, due to the monsters inhabiting it. About ''society as a whole'' nothing is known, except that it forms a circle encompassing everything, which enables one to close the conversation peremptorily.

If we really had to study what is ''social'' in Paris, we would have to go about it very differently. We would have to be able to do for totalizing enterprises what we have just done for maps: tilt them over from the illusion of panopticons onto the paths of oligopticons.

''Paris has become unbearable'', ''the municipality's doing crazy things'', ''they have got to consult with the municipalities of neighbouring suburbs'', ''the police would do better to patrol the suburbs'', ''dog owners should pay heavier fines'', ''there are no halls for amateur music'': all statements circulating from mouth to media, media to concierges, concierges to co-tenants, co-tenants to petitions, petitions to offices, offices to decrees, decrees to administrative courts. . . Can we study these myriads of statements? To some extent: on blogs, in newspapers, cafés, dinner parties, squares, SMS. I suppose that the mayor has informers, like the police prefecture has videos and the intelligence services have big ears. A mass of rumours and detached statements whose circulation, from point to point, compose Paris as surely as do cars travelling on the ring road or the millions of users transported daily in the metro. There are often public transport strikes, but this transportation of statements (what I call ''collecting statements'') are never on strike. . . Fortunately. . . or Paris would disappear for good. Some of these words ''totalize'' Paris, which has become the subject of ready-made phrases like ''Paris wants to breathe'', ''Paris welcomes you'', ''Paris refuses''. But these totalizing phrases do not circulate differently to individualizing ones, like that of the little girl who murmurs from the sandpit: ''Mummy I am bored. . .''. Recording the circulation of a statement is very different to deciding whether that statement totalizes or individualizes. While the allegorical statue of Paris does indeed represent ''all of Paris'', it is simply situated at an intersection and does not occupy ''any more place'' than that of Balzac on the Boulevard Raspail or that of the Republic on the square with the same name. Just as the map is not the territory but is situated inside the territory, of which it accelerates or facilitates certain movements, and just as the directory is not ''all of Paris'', of which it is nevertheless part and parcel by rapidly pinpointing addresses, so too the totalizing statements that consider Paris ''as a whole'' also circulate in Paris, to which they add, one might say, their fragments of totalization. The most global panoramas also have an address, and even if they present a scholarly and quantifying version, if one does see ''everything'' in them, it is always ''in'' a dark hall.

Why is it so important to ''locate'' with such obstinacy the totalizing views of Paris? It is a matter of atmosphere and breath, and thus, Peter Sloterdijk would say, a serious matter of politics. The illusion of the zoom, in geography and sociology alike, has the drawback of making life in the city completely suffocating. There are no more loci, since everything is filled by the apparently smooth transition from the whole to the parts and from the parts to the whole, as if there were not a single gap, not a single breathing space. The filling up has been done. We are suffocating. This -to use a scholarly word -is a question of mereology: the relationship of the parts to the whole, which is the privilege of politics. It is not up to geography or sociology to simplify it too quickly, assuming the problem has been solved and the totality is already known, as if Paris were merely an image, sliced up, waiting to be reassembled. This relationship of the parts to the whole, like a jigsaw puzzle, is the very negation of politics.

For politics to be reborn, for Paris to be breathable again, the city has to remain invisible, in the sense of neither the parts nor the different wholes into which they fit, being determined in advance.

From this point of view, there is nothing more suffocating than Google Earth with its pretention of zooming in seamlessly; nothing more reactionary than the conventional discourses on the continuous passage of global Capitalism to the market stalls of Maubrt, through the (recently computerized) waste paper basket of the Palais Brongiart. As Sloterdijk put it, politics is not the revolution but the explication, that is, the unfolding of the artificial elements that, until now, we didnot know we depended on to exist. In other words, politics is a question of air conditioning, the gradual realization that we live together in enclosures which are as unnatural as greenhouses, and the intricate mechanisms of which are gradually appearing to us. Whosoever believes that politics stands to reason because it deals with a Public Good whose form and bounty they will know in advance, commits more than a crime: they commit political misconduct.

I use the term plasma for this space -but it is not a space -in which lie -but there is no rest -the various circulations of totalizations and participations waiting for explication and composition. The term seems abstract, but it is because all the usual metaphors are defined by the zoom, which forces us to believe that we know what they are talking about when they say that there is a continuous path between the parts and the whole. Suspend the zoom, multiply the connections between the different views of Paris, without making them commensurable too quickly; measure the fundamental invisibility of all the oligopticons (each of them sees well but very little), relocate the sites where they talk of Paris ''as a whole'' (the mayor's office, the headquarters of the Paris prefecture, the control room of the water utility, the building in the Boulevard Morland, etc.), and ask yourself in what you could situate these membra disjecta, without immediately relating them to a ''natural context'', a ''society'' or, of course, ''discourses''. Well, this background, it is the plasma. This is what makes it possible to measure the extent of our ignorance concerning Paris. Above all, it enables us to give its chances back to politics, by reserving for it the task of composition, and by not naturalizing or socializing it, or turning it into a simple question of words.

For the past ten years or so, we have been giving in to the temptation to replace politics by management, and the exercise of democracy by the awful word ''governance''. We now see why: good management, like good governance, are used to regulate the relationship of the parts to the whole as harmoniously and effectively as possible. They like the zoom. They see things first from on high, then from the middle, and finally around the bottom. All that is a sequence linked up and fitted together perfectly. Each Russian doll is set without any debate in a bigger one and contains other smaller ones, always without force. E-mail address: bruno.latour@sciences-po.fr URL: www.bruno-latour.fr

  That is the visible Paris. It is the managed Paris. Now open all the dolls and plunge them into the plasma, leaving each of them to define what is bigger and what is smaller than it, without ranking them in advance and by opening all the controversies on the challenged relations of the parts to the whole. That is the invisible Paris. It is the political Paris. It is the Paris that has to be composed. Bruno Latour ⇑ Sciences Po, 27 rue St Guillaume, 75007 Paris, France * Tel.: +33 (0)14 549 5093; fax: +33 (0)14 549 7217.

q Translated from French by Liz Carey-Libbrecht


Samuel Hornus

Detecting the intersection of two convex shapes by searching on the 2-sphere

Keywords: intersection detection, GJK, numerical robustness, collision detection, Minkowski sum, Gauss map 1 Except, briefly, in Section 6.4

We take a look at the problem of deciding whether two convex shapes intersect or not. We do so through the well known lens of Minkowski sums and with a bias towards applications in computer graphics and robotics. We describe a new technique that works explicitly on the unit sphere, interpreted as the sphere of directions. In extensive benchmarks against various well-known techniques, ours is found to be slightly more efficient, much more robust and comparatively easy to implement. In particular, our technique is compared favourably to the ubiquitous algorithm of Gilbert, Johnson and Keerthi (GJK), and its decision variant by Gilbert and Foo. We provide an in-depth geometrical understanding of the differences between GJK and our technique and conclude that our technique is probably a good drop-in replacement when one is not interested in the actual distance between two non-intersecting shapes.

Introduction

This paper is concerned with the problem of detecting the intersection of two convex objects. Given two convex objects A and B in R 3 , we ask whether A and B have a point in common or not. When that is the case we say that "they intersect" or "they touch each other." The intersection detection problem is a component of collision detection for more general shapes, which plays a major role in robotics [START_REF] Gilbert | Computing the distance between general convex objects in three-dimensional space[END_REF], computer animation [START_REF] Gottschalk | OBBTree: A hierarchical structure for rapid interference detection[END_REF] and mechanical simulation for example.

Intersection detection also plays a role in computer graphics in general as an ingredient in acceleration data structures, such as bounding volume hierarchies or Kdtrees. In the latter case, an object of interest (eg a ray, a view frustum, or another hierarchy) is tested for intersection against the geometric shapes that bound each node in the hierarchy. These bounding shapes are simple shapes (boxes, spheres) for which fast intersection detection techniques exist. For an in-depth exposition to intersection and collision detection, we refer the reader to the book of Ericson [START_REF] Ericson | Real-Time Collision Detection[END_REF] and the survey of Jiménez et al. [START_REF] Jiménez | 3D collision detection: A survey[END_REF].

In robotics or computer graphics, we often limit ourselves to constant-size or small convex objects, and techniques that do not use pre-processing, but the intersection detection problem has several variants and have been studied by theoreticians as well. Computational geometers have recently developed an optimal solution for general convex polyhedra: Given any collection of convex polyhedra in R 3 , one can pre-process them in linear time, inde- * samuel.hornus@inria.fr pendently of each other, so that the intersection of any two polyhedra P and Q from the collection can be tested in optimal time O(log |P | + log |Q|) (see [START_REF] Barba | Optimal detection of intersections between convex polyhedra[END_REF] and the other references within). This essentially closes the (theoretical) problem for the case of convex polyhedra. It is not clear if their technique is amenable to an efficient implementation since the data-structures used are not simple and it requires knowledge of the connectivity between the polyhedron neighboring facets.

In this paper however, we only consider techniques that do not use excessive or complex pre-processing 1 and are asymptotically slower, but very fast in practice.

Of particular interest is the beautiful algorithm developed by Gilbert, Johnson and Keerthi (GJK) for computing the distance d(A, B) between two convex polyhedra A and B [START_REF] Gilbert | A fast procedure for computing the distance between complex objects in three-dimensional space[END_REF]. It only needs access to the vertices of the polyhedra and typically uses just a few iterations over them to compute the distance d(A, B). It was later generalized and adapted to the decision version of the problem by Gilbert and Foo [START_REF] Gilbert | Computing the distance between general convex objects in three-dimensional space[END_REF] to handle a broader class of convex objects. We describe these algorithms in Section 3.

In this paper we view the decision problem as that of finding an oriented plane that sets A on its negative and B on its positive side. Writing S -for the set of normals to the planes achieving separation, we design, in Section 4, an algorithm to find a direction in S -or decide that S - is empty (when A and B do touch each other). Our algorithm iteratively prunes parts of the unit sphere S so that the remaining part, a convex spherical polygon, provides

A B -B C A B A ⊕ B A C A ⊕ C A ⊕ C A B A ⊕ B A C
Figure 1: Three convex shapes A, B and C lie in the Euclidean plane whose origin is marked. Some Minkowski sums and differences are drawn. Note how the origin lies in the Minkowski difference of A and C, proving that these two shapes intersect.

an increasingly tight superset of S -. We call it Decision Sphere Search, or DSS for short. Section 5 gives a theoretical analysis of DSS and an extensive comparison of DSS with GJK. In particular, we show that DSS optimally aggregates the information gathered about the Minkowski difference A B during the successive iterations.

In Section 6, we benchmark our implementations of a "naive", quadratic algorithm, of DSS and of GJK. Each benchmark considers a specific type of objects and measures the performance of the algorithm with respect to the "collision density," ie the ratio of the number of tested pairs of convex objects that actually intersect to the total number of tested pairs. Our DSS technique appears to be faster than GJK in general, numerically more robust and easier to implement. We have taken care to analyse a large variety of situations including very uneven ones, such as frustum-culling where one object (the frustum) is much larger than the other. In that case, we show that a hybrid technique combining DSS and GJK gives the overall best results and we explain why.

Preliminaries

It is simpler to work with an alternative view of the geometry of the intersection detection problem, thereby reducing it to deciding whether a closed convex set contains the origin or not. The rest of the present section describes this well known alternative view.

The Minkowski sum and Minkowski difference of two subsets A and B of R 3 are (see Figure 1):

A ⊕ B = {a + b | a ∈ A, b ∈ B} and
(1)

A B = {a -b | a ∈ A, b ∈ B}. (2)
Using this definition, A and B have non-empty intersection if and only if A B contains the origin o:

A ∩ B = ∅ ⇔ o ∈ A B. ( 3
) h A (n) -h B (-n) h A B (n) o 0 -h B (-n) A B A B n A B A B n h A B (n) o Σ A B (n)
Figure 2: Two illustrations of equation ( 8) with opposite normal vectors n. In each case, the blue vectors are identical. On the left,

max x∈A B n • x = h A B (n) is positive.
On the right, it is negative, which certifies that A B does not contain the origin.

We write d(A, B) for the distance between the two subsets A and B:

d(A, B) = min a∈A,b∈B |a -b|. (4)
When A and B are closed convex sets, their Minkowski difference is a closed convex set as well. In equation ( 3), we have thus reduced our question on the existence of an intersection between A and B to a question regarding a single convex object P = A B and the origin. In the rest of the paper we most often consider this single closed convex set P and its relation with the origin o, instead of considering A and B separately.

We now define three functions that play an important role in the algorithms discussed in this paper. For a closed convex subset P of R 3 , we define the support function h P that maps a unit vector n of the unit sphere S to a real number defined as

h P (n) = max p∈P (n • p). (5)
The support function is closely tied to the study of convex shapes and serves as a tool to represent and manipulate them. The usefulness of the support function for shape modeling operations was recognized by Sabin who showed how offset and convolution are easily expressed with it [START_REF] Sabin | Surfaces closed under five important geometric operations[END_REF].

A more technical overview with an application to the computation of Minkowski sums is given, eg by Šír et al. [START_REF] Šír | Computing convolutions and minkowski sums via support functions[END_REF].

We also define the extremal function Σ P as

Σ P (n) = arg max p∈P (n • p), (6)
ie, h P (n) = n • Σ P (n). For a given direction n, several points on P might realize the largest dot-product with n.

In this case we choose a point arbitrarily. When the convex set P is not bounded, we implicitly restrict the functions h P and Σ P to the portion of S where they are well defined. The closest-point function ν maps P to the unique point in P that realizes the distance from P to the origin, ie ν(P ) ∈ P and |ν(P )| = d(P, {o}).

The case P = A B is of particular importance for us.

Algorithm 1 The GJK algorithm.

1: function GJK(P , V) If we test A and B, then

P = A B |V| ≤ 4 2: v ← ν(H(V)) v is the point of H(V) closest to the origin 3: if v = o then d(P, {o}) = 0 since o ∈ H(V) ⊂ P 4:
return 0 (for the distance problem) 5:

or return Intersection (for intersection detection) 6:

p

← Σ P -v |v| 7: if v • p = |v| 2 then 8:
return |v| or Disjoint o ∈ P and d(P, {o}) = |v| 9:

V ← the smallest subset of V such that v ∈ H( V) | V| ≤ 3 10:

return GJK(P , V ∪ {p})

In this case, the functions h P and Σ P are computed as: 2). ( 9)

h A B (n) = max a∈A (n • a) -min b∈B (n • b) (7) = h A (n) + h B (-n) and (8)
Σ A B (n) = Σ A (n) -Σ B (-n) (see Figure
The convex shape P = A B contains the origin if and only if its support function h P , takes a non-negative value over the whole unit sphere:

A ∩ B = ∅ ⇔ o ∈ P ⇔ ∀n ∈ S, h P (n) ≥ 0, or (10) A ∩ B = ∅ ⇔ o ∈ P ⇔ ∃n ∈ S, h P (n) < 0. ( 11
)

Related work

Research on practical intersection detection techniques for static convex shapes has not been very active in recent years, so we can refer the reader to the survey of Jiménez et al. [START_REF] Jiménez | 3D collision detection: A survey[END_REF] and the excellent book of Ericson [START_REF] Ericson | Real-Time Collision Detection[END_REF]. We also refer the reader to our technical report [START_REF] Hornus | Intersection detection via gauss maps; a review and new techniques[END_REF], where we propose a review of previous work on intersection detection problem for small convex polyhedra with or without specific symmetries, through the unifying lens of Minkowski sums and the Gauss map, which both play a central role as soon as the relation between two convex objects is sought after; see for example the references [START_REF] Kim | Incremental penetration depth estimation between convex polytopes using dualspace expansion[END_REF][START_REF] Choi | Determining the directional contact range of two convex polyhedra[END_REF].

Among the various existing techniques, that of Gilbert, Johnson and Keerthi stands out as a very general and typically very fast method to compute the distance between two convex polyhedra. As such it is an indispensable tool in software that deals with interacting shapes (see Section 5.4). We devolve this section to describing the GJK technique [START_REF] Gilbert | A fast procedure for computing the distance between complex objects in three-dimensional space[END_REF] and its cousin, developed by Gilbert and Foo [START_REF] Gilbert | Computing the distance between general convex objects in three-dimensional space[END_REF] that generalizes it to a more general class of convex shapes and adapt it to the decision version of the problem.

The GJK algorithm

The technique of Gilbert, Johnson and Keerthi (called GJK hereafter) incrementally evolves a set V of d vertices of P (d ∈ [START_REF] Barba | Optimal detection of intersections between convex polyhedra[END_REF][START_REF] Cameron | Enhancing GJK: Computing minimum and penetration distances between convex polyhedra[END_REF]) whose convex hull H(V) forms increasingly accurate approximation of A B closer and closer to the origin [START_REF] Gilbert | A fast procedure for computing the distance between complex objects in three-dimensional space[END_REF]. See Algorithm 1. The first call to GJK is passed the parameters P = A B and V = {x} where x is any point in P . In each iteration, H(V) serves as a low complexity proxy to the full convex P . The iteration of the GJK algorithm proceeds as follows. The closest point of H(V) to the origin is computed and stored in variable v. If v = o then o ∈ P because H(V) ⊂ P and this proves that P contains the origin (or that A and B do intersect); the iteration terminates. Otherwise the support point on P along the direction of -v is computed and stored in variable p. The authors show (and it is easy to see) that if v • p = |v| 2 then we have found ν(P ) = v so the iteration terminates (d(A, B) = |ν(P )|). Finally, a new simplex V ∪ {p} is formed which is a better approximation of P closer to the origin and the iteration continues. The authors provide a proof that the algorithm does indeed terminate after a finite number of iterations when P is a polyhedron.

For the decision version of GJK, we can return Disjoint as soon as we find a plane separating P from o. To do so, we replace lines 7 and 8 by if v • p > 0 then return Disjoint

The main difficulty with GJK is the computation of ν(H(V)) when V is a tetrahedra, starting at the beginning of the fourth iteration. First, this computation is time consuming and not easy to implement correctly. Second, the chain of floating point computations starting at the input point coordinates are long, which increases the numerical inaccuracies. The later are exacerbated by the geometry of the tetrahedra itself which tends to be close to degenerate, being almost as flat as a triangle. This behavior forces an implementation to monitor the number of iterations and decide that P contains the origin when that number exceeds a fixed threshold. (A large number of iterations is usually due to a configuration where P and the origin are difficult to separate.) Another minor defect of GJK is its inability to take advantage of all the information gathered along the iterations. In particular, after the fourth iteration, each iteration loses one of the vertices of P computed in line 6 of Algorithm 1. This loss is on purpose, so that H(V) never get more complex than a tetrahedron.

In contrast, our new technique DSS keeps all the relevant information of previous iterations compactly in the form of a convex spherical polygon. Long chains of floating point computations are not required, thereby greatly decreasing numerical inaccuracies. This makes the technique much less prone to reaching the maximum number of iterations and taking, then, an arbitrary decision, as demonstrated in our benchmarks. In addition our DSS technique has a more stable way to pick a new candidate test direction v, which leads to a smaller number of iterations than GJK on average. Finally, DSS is also easier to implement since its most complex subroutine is the clipping of a 2D convex polygon against a half-plane.

The GJK technique was then generalized by Gilbert and Foo [START_REF] Gilbert | Computing the distance between general convex objects in three-dimensional space[END_REF] to arbitrary convex shapes X as long as the corresponding extremal function Σ X can be computed on them. In the same reference, the decision version of the algorithm is also presented, as described above.

More recent work has focused on computing the penetration depth of intersecting objects [START_REF] Kim | Incremental penetration depth estimation between convex polytopes using dualspace expansion[END_REF][START_REF] Van Der Bergen | A fast and robust GJK implementation for collision detection of convex objects[END_REF][START_REF] Van Der Bergen | Proximity queries and penetration depth computation on 3D game objects[END_REF] or bringing time into the problem: maintaining the intersection status as the objects move or deform and doing so over complex hierarchies of shapes, see eg [START_REF] Guibas | A hierarchical method for real-time distance computation among moving convex bodies[END_REF] and the huge body of work at the Gamma research group at UNC. We discuss some of these aspects in Section 5.4.

Projection onto Convex Sets

While DSS and GJK are closely related, there is another, much more general family of techniques for computing a point in the intersection of two or more convex shapes by alternate projection of a point on the shapes until convergence. These Projection onto Convex Sets (POCS) techniques are typically used in the case of many convex shapes in higher dimensional spaces. Their basic operation is the projection operator, while DSS and GJK use the extremal function Σ. Using POCS for deciding if two three-dimensional convex shapes have an intersection point seems less efficient than using GJK or DSS. The interested reader may consult the survey by Bauschke and Borwin [START_REF] Bauschke | On projection algorithms for solving convex feasibility problems[END_REF].

Our Decision Sphere Search algorithm

Our algorithm is similar in spirit to the GJK/GF algorithm: A sequence of candidate directions are generated in which the convex P and the origin o are tested for separation using equations ( 11) and ( 8) until a final decision can be taken. Our algorithm differs from theirs in the way a new test direction is generated (they search a point closest to the origin on a simplex inside P , whereas we pick a point in a convex spherical polygon) and in that we do not seek the actual distance between the two convex objects but only whether they touch or not (as also studied in [START_REF] Gilbert | Computing the distance between general convex objects in three-dimensional space[END_REF]). Note that equation [START_REF] Ericson | Real-Time Collision Detection[END_REF], as well as our technique, described below, applies to any pair of closed convex objects, not necessarily polyhedra.

Let us define the separating set S -(P ) of convex P as

S -(P ) = {n ∈ S | h P (n) < 0}, (see Figure 3). ( 12
)
It is the set of normals of the oriented planes tangent to P with P on their non-positive side and o on their positive side. Then

A ∩ B = ∅ ⇔ S -(A B) = ∅, or (13)
o ∈ P ⇔ S -(P ) = ∅. (14)
Our algorithm follows this idea and searches over the unit sphere for a direction n in which h A B (n) is negative, or decides that h A B is everywhere non-negative. When v is a vector in R 3 , let v ↑ denote the north-hemisphere of Algorithm 2 Our DecisionSphereSearch algorithm.

1: function DecisionSphereSearch(P , S) 2: n ← a center point of S It holds that n ∈ S 3: p ← Σ P (n) h P (n) = n • p 4: if h P (n) < 0 then return Disjoint o ∈ P 5: S ← S ∩ p ↓ Now, n ∈ S since n • p ≥ 0 6:
if S is empty then return Intersection o ∈ P 7:

return DecisionSphereSearch(P , S ) S whose north pole is in the direction of v:

A B S -(A B) A B P o S -(P )
v ↑ = {w ∈ S | v • w ≥ 0} and v ↓ denote its complement: v ↓ = S \ v ↑ . (As an exception, o ↑ is equal to S;
it is not a hemisphere.) To design our search procedure, we use the following Lemma 1. Let p be a point in P \ {o}. Then h P ( p |p| ) > 0 and, for all n ∈ p ↑ , h P (n) ≥ 0.

Proof. Clearly, p • p is positive, which proves that h P ( p |p| ) is positive as well. If n is a vector in p ↑ , then n • p ≥ 0. Therefore h P (n) ≥ 0.

The lemma above states that the support function h P takes a non-negative value on any direction n ∈ p ↑ . We use this property to prune parts of the unit sphere in which we can not find a direction n making h P negative. Our search procedure (Algorithm 2) takes as parameters a search polygon S: a convex spherical polygon whose interior, S, is guaranteed to contain S -(P ), and a direction n ∈ S:

To test if A and B intersect, we first pick some points a ∈ A and b ∈ B (the respective centers of A and B might be good candidates). If a = b then we are done. Otherwise, we compute p ← ab and n ← -p |p| and call DecisionSphereSearch(A B, n, n ↑ ).

Initially, the spherical polygon S is set to a hemisphere, and the first test direction is the center n (or pole) of that hemisphere. If h P (n) ≥ 0, then direction n fails to separate B from A and a new direction must be tested. The extremal point p ∈ P (p = ab, a ∈ A and b ∈ B) that was computed in line 3 is put to use to prune a part of the search polygon: since we know, by Lemma 1, that h P takes a non-negative value over p ↑ the search polygon can be reduced to S ∩ p ↓ .

For the search to be as quick as possible, we should prune as much of S as possible. We should ideally choose the test direction n ∈ S in such a way that any hemisphere that contains n (in particular, the hemisphere p ↓ , see line 5) contains at least a constant fraction of the area of S. The solution for a discrete version of this problem is known as the centerpoint [START_REF] Clarkson | Approximating center points with iterated radon points[END_REF]. For our convex spherical problem, we don't know how to find such an "area centerpoint." Our implementation approximates it by the re-normalized average of the vertices of S, which behaves well in practice.

The DSS algorithm shares several interesting properties with that of Gilbert and Foo [START_REF] Gilbert | Computing the distance between general convex objects in three-dimensional space[END_REF]:

• The only operation needed on the convex object is the computation of the extremal function Σ in a given direction. Therefore, it works on any kind of convex objects for which the extremal point can be effectively computed, not just polyhedra. For example, take A as a sphere and B as a view-frustum and DSS becomes an exact frustum culling algorithm for spheres. Algorithms to compute Σ X for various classes of shapes X, including ellipsoids, are given in [START_REF] Gilbert | Computing the distance between general convex objects in three-dimensional space[END_REF][START_REF] Eberly | Intersection of ellipsoids[END_REF]. Zonotopes (which include oriented bounding boxes) are tightfitting bounding volumes for which the extremal function is easy to compute; see [START_REF] Guibas | Zonotopes as bounding volumes[END_REF][START_REF] Hornus | Intersection detection via gauss maps; a review and new techniques[END_REF].

• DSS works just as well on unbounded convex objects such as lines, rays or view-pyramid. In the case of unbounded polyhedra, we avoid treating infinitely far extremal points as a special case by simply initializing the spherical polygon S to the intersection of the supports of the Gauss maps of A and B. 2 This limits the extrema to finite points only without any restriction since extrema at infinity always lead to a positive infinite value of support function h.

Compared to the GJK algorithm, our algorithm

• can not compute the distance between A and B, but only gives a yes/no answer; this lets it conclude that A and B do not intersect using less test directions since the actual distance between A and B is not needed.

• is able to use more of the information computed in previous stages of the algorithm. This lowers the average number of directions to be tested. See Section 5.

• Importantly, DSS has a much lower failure rate than GJK, where a failure means entering in an infinite loop because of numerical inaccuracy. See Section 5.3.

The last detail of our algorithm is the computation of S ∩ p ↓ . This intersection is simple to compute since any algorithm for clipping a convex polygon with a half-plane can be adapted to clip a convex spherical polygon with a hemisphere, with a tiny extension to account for lunes: spherical polygons with two sides only.

Remark on the complexity of DSS

In this section, we assume that we are able to find a centerpoint n of a convex spherical polygon S efficiently. Thus, there exists a constant µ > 1 such that n • v ≥ 0 ⇒ area(S ∩ v ↓ ) ≤ area(S)/µ. Note that our implementation of DSS does not satisfy this assumption: it computes the average of the vertices of the polygon, which is not guaranteed to produce a centerpoint.

After the k-th iteration, if a decision has not yet been reached, the search polygon S must still contain

S -(A B). Thus, area(S -(A B)) ≤ area(S) ≤ 2πµ -k . This implies k ≤ log µ 2π area(S -(A B)) . ( 15
)
Under the above assumption, the number of iterations of DSS is bounded by the logarithm of the inverse of the area of the separating set of A B. When A and B are far away from each other, this area is large (close to 2π, Figure 3 top) and thus the number of iterations is small. When A and B are close to tangent to each other, the area of the separating set is very small (Figure 3 bottom-right) and the maximal number of iterations is correspondingly larger.

Understanding DSS v.s. GJK

A characterisation of the separating planes

This section derives a characterisation of the planes separating two convex objects that we use in Section 5.2 to understand the differences between our algorithm and GJK. This characterization, embodied in definition [START_REF] Gottschalk | OBBTree: A hierarchical structure for rapid interference detection[END_REF] and Lemma 2 below.

First, recall that testing that A and B touch each other is equivalent to testing that the origin o lies in the Minkowski difference A B. In this section, in order to simplify the exposition, we therefore consider the geometrically (but not computationally) equivalent problem of testing that an object P contains the origin o. We assume that P is convex, which is the case when P = A B and both A and B are convex.

Let us define the silhouette of P , sil(P ), as the set of points p ∈ ∂P such that P admits a tangent plane in p with (outward) normal n so that h P (n) = 0.

When P is a polyhedron, its silhouette sil(P ) is a subset of its faces (vertices, edges and facets). The separating set of P depends only on its silhouette vertices: Algorithm 3 An abstract view of GJK and DSS.

1: function ConvexContainsOrigin(P , Pi ) 2:
Pi is a convex polyhedron that approximates P : Pi ⊂ P .

3:

P is a convex object. It is assumed that o ∈ Pi . 4:

n ← a vector in S -( Pi ), the separating set of Pi 5:

S

-( Pi ) = ∅ because o ∈ Pi 6: v i+1 ← Σ P (n) h P (n) = n • v i+1 7: if h P (n) < 0 then return Disjoint o ∈ P 8:
Pi+1 ← better approximation of P using Pi and v i+1 9:

if o ∈ Pi+1 then return Intersection o ∈ Pi+1 ⊂ P 10:

return ConvexContainsOrigin(P , Pi+1 ) o ∈ Pi+1

Lemma 2. When P is a convex polyhedron not containing the origin, S -(P ) is a non-empty convex spherical polygon on S:

S -(P ) = v, vertex of sil(P ) v ↓ = v, vertex of P v ↓ . ( 16
)
We use Lemma 2, whose proof is given in Appendix A, in the following in order to compare the DSS and GJK algorithms.

Comparing DSS and GJK

In order to compare the GJK algorithm with ours, it is convenient to see both under the same light. To do so, we can describe both algorithms abstractly as follows (Algorithm 3):

Both algorithms are called initially using P0 = {v 0 }, v 0 ∈ P . We will also consider the set of all known constructed points of P : V i = {v 0 , v 1 , v 2 , • • • , v i } ⊂ P generated in line 6 of Algorithm 3. The algorithms differ in the polyhedron Pi used to approximate P and in lines 4, 8 and 9 of Algorithm 3. We now examine these differences in turn.

The polyhedron Pi

In DSS (Algorithm 2 page 4), Pi is simply the convex hull of all the known points of P : Pi = H(V i ). Note however that the algorithm does not store Pi explicitly but stores a spherical polygon S that is guaranteed to contain S -(P ). Lemma 2 proves that indeed S is the separating set of H(V i ): S = S -(H(V i )). Importantly, H(V i ) is the best approximation of P that we can have knowing only the subset V i of P , and therefore S is the tightest approximation of S -(P ) that one can construct with the knowledge that we have at this stage.

In GJK, Pi is stored explicitly and is either a vertex, a line segment, a triangle or a tetrahedron. It is the convex hull of at most four points taken in V i and including v i . As such, PGJK ⊂ PDSS , ie GJK considers approximations of P of lesser quality (they are smaller, so their separating sets are larger than those of DSS). Also, there is no guarantee that the sequence of considered approximations is increasing, while DSS does guarantee that Pi ⊂ Pi+1 . Dually, our algorithm guarantees that S -( Pi+1 ) is a better approximation of S -(P ) than S -( Pi ), while GJK offers no such guarantee.

In our implementation, we regularly find separating sets S with 5 or 6 vertices while GJK can only produce spherical polygons S -( PGJK ) having at most 4 vertices (because PGJK has at most 4 silhouette vertices and Lemma 2). This is a direct evidence that our algorithm is able, in practice as well as in theory, to use more information during its execution.

Line 9: testing for intersection

This line tests whether the origin lies in the approximation Pi+1 of P . In GJK, this geometric test is performed when Pi+1 is a tetrahedron as part of the picking of a new test direction (see below). In our algorithm DSS, we know, by Lemma 2, that the origin lies in Pi+1 simply when its separating set, S, is empty, which is trivial to check.

Line 4: picking a new test direction

In DSS, we pick a vector n as a (approximate) centerpoint of S -( Pi ). As we have seen earlier in the description of the algorithm, this ensures that a large part of S is pruned if n fails to produce a separating plane (ie n ∈ S -(P )) thereby heuristically accelerating the search for the separating set of P .

In contrast, GJK was originally designed to actually compute the closest point of P to the origin, To ensure that it is eventually found and that Pi stays tractable (with 4 or fewer vertices), the vector n is chosen as the opposite of the closest point of Pi to the origin: n = -ν( Pi ). The vector n is indeed a direction in the separating set of Pi , but it is not necessarily centrally located in it. It is however locally optimal in the sense that is minimizes n → h P i (n).

Line 8: updating the approximation Pi

In both algorithms we know that the silhouette of Pi+1 is different from that of Pi and the vector n ∈ S -( Pi ) picked in line 4 disappears from S -( Pi+1 ) (by Lemma 1), but only DSS guarantees that Pi ⊂ Pi+1 , or equivalently, S -( Pi+1 ) ⊂ S -( Pi ). In particular in GJK the vector n might appear again in a subsequent approximation Pj , j > i + 1.

In DSS, the separating set of Pi+1 is computed as the intersection of the separating set of Pi (a spherical convex polygon) with the half-sphere v ↓ i+1 . This is algorithmically akin to polygon clipping in the plane.

In GJK, assuming that o ∈ Pi , let f be the unique facet of Pi that contains ν( Pi ) in its interior. Then Pi+1 is set to H(f ∪ {v i+1 }) which is the convex hull of at most 4 affinely independent points.

Which algorithm is faster is not an easy question to answer to. GJK is very fast at first when Pi has less than four vertices, but slower when Pi is a tetrahedron. However the tetrahedron stage is seldom reached as a decision is often taken in less than four iterations. The iterations of DSS all cost roughly the same. We then expect to see GJK perform best in easy cases, when the object P is close to being a polyhedron with very few facets and far from being "round". In that case, few iterations are required to reach a decision (typically less than four) and GJK is faster on average (see the frustum culling test in Section 6.5). In our experiments, the polyhedron P = A B is often more complex and DSS is slightly faster. Furthermore, DSS is less prone to numerical inaccuracies caused by floating-point computation, thanks in part to its less complicated implementation. Section 5.3 describes this phenomenon and Section 6 shows experimentally the robustness of DSS.

Numerical issues in GJK and DSS

GJK and DSS are iterative techniques. A typical implementation uses non-exact floating point numbers, so that it is possible that the implementations of GJK or DSS enter an infinite loop. To remedy this problem, we force the implementation to exit when a maximal number of iterations, Θ, has been reached. 3 When this happens, we consider the intersection test to have failed and, conservatively, decide that the pair of convex objects at hand do intersect. Note that a failure may happen also when the objects do not actually intersect, in which case a wrong answer is reported.

In our statistics over a large number of tested pairs of objects, the second largest number of iterations is strictly smaller than Θ -1 (the largest one being Θ). This makes us confident that Θ is large enough to almost surely detect that the routine has entered an actual infinite loop.

In this context, we will see in Section 6 that DSS is more stable than GJK, in the sense that our DSS implementation fails less often than our GJK implementation. In fact, while the failure rate of both implementation is rather small, the failure rate of DSS is more than a thousand times smaller than that of GJK. DSS is also almost never slower than GJK. This let us argue that DSS might be a good candidate to replace GJK in several applications.

Our DSS algorithm also has the advantage, over GJK, to be more easily amenable to a fast and exact implementation. Indeed, the only operation that is required is the computation of the signs of the determinant of 3 by 3 matrices, a predicate for which several very efficient exact implementations exist [START_REF] Pion | A generic lazy evaluation scheme for exact geometric computations[END_REF].

DSS in physics simulation

The decision version of GJK (that returns a yes/no answer) is often used in software library for physics simulation (eg the Bullet Physics Library [START_REF] Bullet | The Bullet physics library[END_REF]) since it applies equally well to all kinds of convex shapes, a large variety of which are typically used in such software (from Bullet's class hierarchy: spheres, convex hulls, convex polyhedra, cones, capsules, Minkowski sums, cylinders, triangles, tetrahedra and boxes).

Our DSS algorithm is simpler to implement (see accompanying code). The benchmarks in Section 6 indicate that DSS is also about 10 % faster and fails much less often (see Section 5.3 and Section 6). Thus we believe that DSS can provide a useful replacement for the decision version of GJK (but not for computing the distance between two non-intersecting convex objects, see Section 7).

In a physics simulator, after A and B are found to intersect, the penetration depth (the shortest translation required to separate A from B) is computed, if desired, using the so-called Expanding Polytope Algorithm (EPA) [START_REF] Van Der Bergen | Proximity queries and penetration depth computation on 3D game objects[END_REF]. The EPA technique starts from the simplex σ ⊂ A B containing the origin o, as computed by GJK. It then iteratively expands it away from the closest point on the boundary of σ to o until an approximation of A B is reached that does contain the closest point to o on the boundary of A B, giving the penetration depth. (The EPA technique is used only when A and B are known to intersect because it is costly, since it basically amounts to an incremental convex hull construction that can lead to a polytope with a large number of faces.)

As described, DSS can not be used to compute the penetration depth. However, just like GJK, the spherical polygon S maintained by DSS can be used to compute a starting polytope for EPA. (A similar idea is used in Section 6.5.1.) Indeed the edges of the spherical polygon S do correspond to 3D vertices of A B. Let V be the set of 3D vertices thus representing the edges of S just prior to S becoming empty; S = ( p∈V p ↓ ) = ∅. And let v be the vertex of A B such that S ∩ v ↓ = ∅. Then the convex hull H(V ∪ {v}) is a polytope that can be used as a starting point for EPA:

o ∈ H(V ∪ {v}) ⊂ A B.
There are other efficient techniques for computing the penetration depth, such as that of Kim et al. [START_REF] Kim | Incremental penetration depth estimation between convex polytopes using dualspace expansion[END_REF], which can similarly be efficiently initialized using the vertex of A B found at the last iteration of the DSS run.

Benchmarks

We have compared our implementations of DSS, GJK and other algorithms, over a few kinds of randomly generated data sets: random pairs of tetrahedra, oriented boxes and polytopes, and frustum culling of random spheres and axis-aligned boxes.

In the figures below, Generic is an implementation of a "naive" technique4 that we described in [16, §3], Tetra is an implementation of Generic specialized to pairs of tetrahdra [16, §4] and DSS is an implementation of our DSS algorithm. Our implementation of GJK (called GJK) follows reference [START_REF] Van Der Bergen | A fast and robust GJK implementation for collision detection of convex objects[END_REF]. The literature describes various algorithmic optimizations of the computation of Σ P (n) (eg "hill-climbing" along the edges of P when P is a polyhedron [START_REF] Cameron | Enhancing GJK: Computing minimum and penetration distances between convex polyhedra[END_REF], or starting the search from the previous extremal position when P is moving [START_REF] Guibas | A hierarchical method for real-time distance computation among moving convex bodies[END_REF]).

We have not used these optimizations since they apply equally well to GJK and DSS and only when P is a polyhedron. SAT is an implementation of the Separating Axis Test that has been taken directly from Gottschalk's PhD manuscript [START_REF] Gottschalk | Collision queries using oriented bounded boxes[END_REF]. The abscissa axis is always logarithmic. The ordinate axis is linear or logarithmic as indicated above each diagram.

All the implementations use 32-bits floating-point arithmetic. We have carefully optimized all our tested implementation, but have refrained from using SIMD instructions, which would however clearly help in optimizing further. In particular, the subroutines that find the extremal point on A B in a given direction are shared by the GJK and DSS implementations, so that their optimization with SIMD instructions would benefit both equally. Regarding the non-shared parts of these implementations, that of DSS (2D polygon clipping) is probably the one that would benefit the most from a "SIMD treatment" (computing the position of points relative to a clipping line, four points at a time). The specifics of GJK seem much harder to optimize with SIMD instructions, so that we believe SIMD instruction would mostly be in favor of our new technique, DSS.

The benchmarks are run on a desktop computer with an Intel Core i7-4770K CPU clocking at 3.5 GHz, with 16 GB of RAM clocking at 1.6 GHz. The software is compiled using g++ 4.9 (c++ -O3 -DNDEBUG). The OS is Debian Linux.

Some of the statistics below report the average number of plane tests evaluated per pair of objects tested for intersection. This number is independent of the implementation and is therefore valuable for comparing the various techniques.

The C++ code and Python scripts that were used to generate all the benchmark plots are available as companion files to this paper.

Random tetrahedra

In this test, N tetrahedra are generated as the convex hull of four uniformly random point on the unit sphere. Each tetrahedron is translated along the x axis by a random distance in [0, σ] where σ represents the "spread" of the set of tetrahedra. Then all N 2 pairs of tetrahedra are tested for intersection using different techniques. The collision density is the fraction of intersecting pairs. A fixed σ implies a fixed average collision density, and the larger the spread is, the lower the collision density. We ensure that all tetrahedra contain the origin when σ = 0, so as to guarantee a collision density of 100 % in that case. This diagram shows the number of pairs of tetrahedra tested per second against the collision density, for a variety of algorithms. The general trend of the graphs shows, as expected, that the performance of all the different techniques lowers as the collision density increases.

The Tetra and SAT techniques both test a predetermined set of separating planes in a predetermined order. This explains their similar performance in the low-density regime, where one or two plane tests are sufficient on average. For pairs of tetrahedra, the SAT algorithm performs more arithmetic operations and thus is predictably slower than Tetra in the high-density regime.

DSS and GJK have a very similar behavior but DSS is consistently faster when density is in the range [1 %, 100 %]. Note that the minimum of the graphs for DSS and GJK is not at 100 % density, but between 80 % and 90 %. This is the density that maximizes the number of pairs of almost-tangent tetrahedra. These pairs require more work from the algorithm to distinguish between intersecting or non-intersecting tetrahedra (because the origin is close to the boundary of A B). In contrast, and contrary to Tetra and SAT, frank intersections at density 100 % are easier to detect for GJK and DSS. The maximal possible number of tests for SAT (44) and Tetra (32) is always achieved at any collision density since all the tests are required to confirm that two tetrahedra touch each other. Our DSS implementation never performed more than 10 plane tests in this benchmark. At the lowest density, Tetra and SAT require a bit less than two plane tests on average while GJK and DSS require just one, since the heuristic chooses a initial plane which is separating when tetrahedra are far away from each other. At density 100 %, SAT computes 44 interval overlap tests; Tetra performs a bit less that 32 plane tests since only pairs of edges that are silhouette of each other incur a plane test. (The silhouette condition is tested for the 36 pairs of edges, but this is much faster than the plane test.) GJK and DSS perform 3 plane tests only, on average (see the bottom diagram), which are sufficient to conclude that the tetrahedra touch each other. This rate is the probability that the testing of a pair will reach the maximum number of iterations allowed, Θ. This limit, Θ, is required because limited floating-point precision may give wrong results in configurations that are close to degenerate. This is the case when the two tetrahedra barely touch each other, and explains the peak failure rate at density ≈ 72 % for GJK. In DSS, the construction of a new test direction does not depend much on the actual geometry of the problem and our DSS implementation enjoys a much lower failure rate. For example, at density 72 %, GJK failed 24923 times while testing 1.999 × 10 8 pairs of tetrahedra while DSS failed 14 times (at density 56 %). The GJK technique needs to find a closest point on a simplex to the origin. This is numerically more sensitive and our implementation of GJK can reach a failure rate of more than one per ten thousand pairs.

Random oriented boxes

In this test, N oriented boxes are generated randomly. The three edge half-lengths are uniformly random in [0, 1], the center of each box is uniformly random in a zerocentered cube of side length σ and the box is randomly oriented. Then all N 2 pairs of boxes are tested for intersection using different techniques. Figure 5 plots the statistics of this test, run against a varying value of σ. Each sample point is the average of 100 runs with N = 2000. As expected, the specialized SAT implementation is faster than GJK or DSS when the collision density becomes non-negligible. Indeed, while the GJK and DSS implementations also take advantage of the symmetrical nature of the boxes to accelerate the computation of h A B (n), they can not exploit the algebraic simplifications stemming from the specific choice of test normal vectors that SAT uses. The largest speed ratio of SAT to DSS is 2.04. The largest speed ratio of SAT to GJK is 2.46. In this benchmark, DSS is faster than GJK in the density range [1 %, 100 %] by as much as 25 %.

Figure 5-bottom diagram. As for tetrahedra, the most striking observation is how our DSS technique is able to use fewer test planes than GJK, although these numbers are already very close to optimal. Here again, while relatively small, the failure rate of GJK is still about a thousand times larger than that of DSS.

Random polytopes with 16 vertices

We now move to somewhat larger convex polytopes generated as the convex hull of 16 random points on the unit sphere and translated by a random amount in [0, σ] along the x axis. Figure 6 plots the statistics of this test, run against a varying value of σ. Each sample point is the average of 100 runs with N = 1600 for GJK and DSS and N = 300 for Generic.

Each plane test in the first phase of the Generic implementation (see [16, §3]) requires to loop over the vertices of a single polytope, instead of looping over the vertices of both in order to compute h A B (n) in GJK and DSS. This explains why Generic is faster at very low collision density. The performance of Generic falls dramatically at higher density because of its quadratic time complexity.

Comparing DSS and GJK, we see a trend very similar to the oriented boxes benchmark. DSS is again faster and more robust than GJK in the density range [1 %, 100 %] and up to 14 % faster. In the next benchmark, we fix the collision density at 50 % and vary the number of vertices of the polytopes.

Varying the number of vertices at 50 % density

In this benchmark, we generate random polytopes in the same way as in Section 6.3, but set the spread σ so that the collision density is always approximately 50 %. We then vary the number of vertices of the polytopes and test the same three techniques. Figure 7 plots the statistics of this benchmark.

Unsurprisingly, as shown in the top diagram, the Generic technique exhibits an inverse quadratic dependency on the number v of vertices. The DSS and GJK techniques shows a performance only inversely proportional to v, and a bit better than that for v ≤ 100, perhaps thanks to cache memory.

Regarding GJK and DSS, when the number of vertices increases, the cost of a single plane test becomes dominant compared to the cost of updating the respective data-structure maintained by these two techniques from one iteration to the next. Therefore, the time to perform one test increasingly depends only on the average number of plane tests, which is lower, at this collision density, for our DSS technique. This explains the constant ratio, of about 1.12, between DSS and GJK. (The corresponding parallel curves are more easily seen in the zoomed-in bottom diagram.)

When the number of vertices is large, it might become interesting to add a hierarchy on top of the vertices of a polytope in order to accelerate the maximization of a linear function over the polytope. We have experimented with such an acceleration scheme and show the result in the bottom diagram of Figure 7. As expected, the scheme is effective for both DSS and GJK and more effective with an increasing number of vertices.

Frustum culling: influence of the relative size

We haven't yet looked at a case of convex objects that are relatively simple but show a strong size discrepancy. To analyse this case, we look at frustum culling. The frustum is a six-sided truncated pyramid. Against a frustum, we cull either axis-aligned boxes (Figure 8) or spheres (Figure 9), since these shapes are typically used as bounding shapes of more complex geometric data.

All frustums are generated with a constant horizontal field-of-view of 80 • and a 16 : 9 aspect ratio. The near plane is 0.1 units away from the frustum apex and the far plane 100 units away. We compute the center C and radius ρ of the largest inscribed sphere of a frustum and translate the frustum so that the center C coincide with the world origin. Each frustum is then randomly rotated.

The radii of the spheres and the edge-lengths of the boxes are uniformly random in [0, 1]. Their centers are uniformly random in the ball of center C and radius σρ where the spread parameter σ is never smaller than 1. We generate N frustums and N boxes or spheres and test all N 2 pairs for intersection. N is set to 1000 and the statistics are averaged over 100 runs (10 8 tested pairs for each sample point). We decrease the collision density by increasing the parameter σ.

At the bottom of Figure 8 we have added a comparison with an implementation of the technique of Greene. The ratio of Greene's technique to the DSS technique ranges from 4.13 at low collision density to 2.73 at high density. This ratio is easily explained because Greene's technique is specialized to testing the intersection of an axis-aligned box and a polyhedron. It also pre-computes three sets of silhouette edges on the polyhedra [START_REF] Greene | Detecting intersection of a rectangular solid and a convex polyhedron[END_REF]. On the other hand, the DSS and GJK techniques are fully general and do not pre-process the input convex shapes. When we look at the top diagrams of Figures 8 and9, the situation is different from the previous benchmarks. For frustum culling small objects (w.r.t. the frustum), the DSS technique is slower than GJK on almost the whole density range. However, the diagram below indicates that GJK still fails far more often than DSS.

We need to make two observations in order to understand why DSS is slower in that case. Let A be the frustum and B a box or a sphere.

1. Since B is much smaller than A, A B is approximately equal to A, that is, A B is very close to the shape of a frustum, which is a quite simple geometric shape.

The GJK algorithm builds local approximations of

A B closer and closer to the origin [START_REF] Gilbert | A fast procedure for computing the distance between complex objects in three-dimensional space[END_REF].

Since A B is a simple shape, the first triangle that GJK builds in A B is highly likely to approximate the face of A B closest to the origin very well, say within Hausdorff distance 1, the size of B. This approximation is often largely enough for the subsequent plane test to succeed or for the generated tetrahedron to include the origin, letting the algorithm decide that A and B intersect. This behavior explains the smaller standard deviation of GJK (bottom diagrams) and why it is faster: because it can more often avoid the distance minimization step over a tetrahedron.

In contrast, DSS works on the unit sphere of directions, and generates a new test direction as an approximate center n of the current spherical polygon S . Now consider the plane with normal vector n and tangent to A B, with A B on its negative side. Any small variation of n makes this tangent plane rotate around some point of A B. During this rotation, at the other end of A B, far from the rotation center, the local distance of the plane to A B varies widely, with respect to the size of B. This will often put the origin in the negative side of the plane, preventing DSS to conclude quickly that A and B are disjoint (equivalently o ∈ A B); DSS will require more iterations to align its test plane with a face of A B.

In other words, in the case of frustum culling, the separating set S -(A B) is small and the support function h A B has a large gradient. This is especially pronounced when A and B are very close to a tangential configuration. In this context, DSS needs more iterations to find S -(A B); its dichotomic search works better with a smoother support function.

A hybrid technique

As evidenced in the bottom diagrams of Figures 8 and9, despite being the faster contender for frustum culling small objects, GJK shows again a rate of failure much larger than that of DSS.

It turns out that we can combine GJK and DSS into a technique, called Hybrid in the two figures, that is just as fast as GJK and fails just as seldom as DSS. To do so, we start with GJK for the first four iterations. Just after the first tetrahedron τ has been built, we build the spherical polygon S = p,p is a vertex of τ p ↓ [START_REF] Jiménez | 3D collision detection: A survey[END_REF] and switch to DSS iterations. The statistics for our Hybrid implementation are shown in Figures 8 and9.

This hybrid technique is only useful when two objects of very different size are tested for intersection. When we enlarge the spheres or boxes to roughly the size of the frustum, 5 we obtain again the same behavior as, eg, in the oriented-boxes benchmark in Section 6.2, where DSS is faster than GJK in almost the whole collision density range. In this case as well, Hybrid performs just like GJK and is therefore slower that DSS. Remarkably, Hybrid fails (in the sense given in Section 5.3) even less often that DSS, typically once or twice per benchmark, which involves 10 8 tested pairs. We set as future work the task of understanding this interesting behavior.

Concluding remarks

We have developed a new algorithm, DSS, to decide the disjointness of two convex shapes, by searching on the 2sphere. Just as for GJK, DSS simply assumes that the extremal function Σ (page 2) is computable on the shapes at hand. Compared to GJK, DSS is i) easier to implement, ii) numerically more robust, iii) typically a little bit faster and never much slower.

We have however considered only the disjointness decision problem. But GJK can compute the actual distance between the two shapes. It is possible to use DSS in a binary search process that converges to the distance d(P, o), since the signed distance from o to the boundary of P ⊕ B(r) (for r ≥ 0) is decreasing (as a function of r), is zero precisely at r = d(P, o) and it is possible to decide if P ⊕ B(r) contains the origin using Σ P ⊕B(r) (n) = Σ P (n) + rn. While our implementation of this idea works well, we found it difficult to make it competitive with GJK.

Figure 3 :

 3 Figure 3: In 2D, the separating set of A B or P , drawn red, is a circular arc on the unit circle.

4 Figure 4 :

 44 Figure 4: Statistics for the 'random tetrahedra' test.

  Figure 4 plots the statistics of this test, run against a varying value of σ. Each sample point is the average of 100 runs with N = 2000.

Figure 4 -

 4 Figure 4-top diagram.This diagram shows the number of pairs of tetrahedra tested per second against the collision density, for a variety of algorithms. The general trend of the graphs shows, as expected, that the performance of all the different techniques lowers as the collision density increases.The Tetra and SAT techniques both test a predetermined set of separating planes in a predetermined order. This explains their similar performance in the low-density regime, where one or two plane tests are sufficient on average. For pairs of tetrahedra, the SAT algorithm performs more arithmetic operations and thus is predictably slower than Tetra in the high-density regime.DSS and GJK have a very similar behavior but DSS is consistently faster when density is in the range [1 %, 100 %]. Note that the minimum of the graphs for DSS and GJK is not at 100 % density, but between 80 % and 90 %. This is the density that maximizes the number of pairs of almost-tangent tetrahedra. These pairs require more work from the algorithm to distinguish between intersecting or non-intersecting tetrahedra (because the origin is close to the boundary of A B). In contrast, and contrary to Tetra and SAT, frank intersections at density 100 % are easier to detect for GJK and DSS.

Figure 4 -

 4 Figure 4-middle diagram. This diagram shows the average number of plane tests (or interval overlap tests for SAT) per pair of tetrahedra (solid lines with shaded standard deviation) as well as the overall maximal number of plane tests reached during the benchmark operation (dashed lines, excluding the pairs for which the intersection detection failed by reaching Θ iterations).The maximal possible number of tests for SAT (44) and Tetra (32) is always achieved at any collision density since all the tests are required to confirm that two tetrahedra touch each other. Our DSS implementation never performed more than 10 plane tests in this benchmark. At the lowest density, Tetra and SAT require a bit less than two plane tests on average while GJK and DSS require just one, since the heuristic chooses a initial plane which is separating when tetrahedra are far away from each other. At density 100 %, SAT computes 44 interval overlap tests; Tetra performs a bit less that 32 plane tests since only pairs of edges that are silhouette of each other incur a plane test. (The silhouette condition is tested for the 36 pairs of edges, but this is much faster than the plane test.) GJK and DSS perform 3 plane tests only, on average (see the bottom diagram), which are sufficient to conclude that the tetrahedra touch each other.

Figure 4 -

 4 Figure 4-bottom diagram. For comparing GJK and DSS, the most important diagram is the bottom one. It shows the same average number of plane tests as in the middle diagram and also shows the rate of failure of each technique.This rate is the probability that the testing of a pair will reach the maximum number of iterations allowed, Θ. This limit, Θ, is required because limited floating-point precision may give wrong results in configurations that are close to degenerate. This is the case when the two tetrahedra barely touch each other, and explains the peak failure rate at density ≈ 72 % for GJK. In DSS, the construction of a new test direction does not depend much on the actual geometry of the problem and our DSS implementation enjoys a much lower failure rate. For example, at density 72 %, GJK failed 24923 times while testing 1.999 × 10 8 pairs of tetrahedra while DSS failed 14 times (at density 56 %). The GJK technique needs to find a closest point on a simplex to the origin. This is numerically more sensitive and our implementation of GJK can reach a failure rate of more than one per ten thousand pairs.

4 Figure 5 :

 45 Figure 5: Statistics for the 'random oriented boxes' test.

Figure 5 -

 5 Figure5-top diagram. As expected, the specialized SAT implementation is faster than GJK or DSS when the collision density becomes non-negligible. Indeed, while the GJK and DSS implementations also take advantage of the symmetrical nature of the boxes to accelerate the computation of h A B (n), they can not exploit the algebraic simplifications stemming from the specific choice of test normal vectors that SAT uses. The largest speed ratio of SAT to DSS is 2.04. The largest speed ratio of SAT to GJK is 2.46.In this benchmark, DSS is faster than GJK in the density range [1 %, 100 %] by as much as 25 %.

4 Figure 6 :

 46 Figure 6: Statistics for the 'random polytopes with 16 vertices' test.

Figure 7 :

 7 Figure 7: Statistics for the 'random polytopes at 50 % collision density' test.

  of plane tests per pair Testing pairs of frustum/AAB, LOG-LIN diagram

Figure 8 :

 8 Figure 8: Statistics for frustum culling of axis-aligned boxes. Bottom. Comparison with the specialized technique of Greene.

4 Figure 9 :

 49 Figure 9: Statistics for frustum culling of spheres.

The support, or domain, of the Gauss map of a convex shape is the union of the unit normal vectors of its tangent planes. For example, the Gauss map of a ray with direction n is the hemisphere (-n) ↑ ; the Gauss map of a line is reduced to a single great-circle whose north pole is in the direction of the line, and the Gauss map of a view-pyramid is a convex quadrilateral (on the unit sphere).

Our implementations limit the number of iterations to Θ = 20 for DSS and GJK.

The naive technique tests all facets as potential separating plane, then all pairs of edges,one in A and one in B, that are silhouette edges with respect to each other.

We have benchmarked this case but do not include the diagrams, which are similar to earlier diagrams on boxes or small polytopes.

Acknowledgment. This work was partially supported by ERC grant ShapeForge (StG-2012-307877).

Proof. n ∈ S -(P ) ⇔ h P (n) < 0 ⇔ ∀p ∈ P, n

Define the silhouette of P , sil(P ) as the set of points p ∈ ∂P such that P admits a tangent plane in p with (outward) normal n that satisfies h P (n) = 0. Lemma 4 below shows that the separating set of P depends only on the silhouette of P . When P is a polyhedron, its silhouette sil(P ) is a subset of its faces (vertices, edges and facets). The separating set of P depends only on its silhouette vertices: Lemma 2. When P is a convex polyhedron not containing the origin, S -(P ) is a non-empty convex spherical polygon on S:

Proof. The left equality is obtained from Lemma 4 by considering and simplifying the contribution of each silhouette edge. The right equality follows directly from Lemma 3.