Linqiao Zhang
email: lzhang15@cs.mcgill.ca

Hazel Everett

Sylvain Lazard

Christophe Weibel
email: weibel@math.mcgill.ca

Sue Whitesides

On the Size of the 3D Visibility Skeleton: Experimental Results

The 3D visibility skeleton is a data structure used to encode global visibility information about a set of objects. Previous theoretical results have shown that for k convex polytopes with n edges in total, the worst case size complexity of this data structure is Θ(n 2 k 2 ) [Brönnimann et al. 07]; whereas for k uniformly distributed unit spheres, the expected size is Θ(k) [Devillers et al. 03].

In this paper, we study the size of the visibility skeleton experimentally. Our results indicate that the size of the 3D visibility skeleton, in our setting, is C k √ n k, where C varies with the scene density but remains small. This is the first experimentally determined asymptotic estimate of the size of the 3D visibility skeleton for reasonably large n and expressed in terms of both n and k. We suggest theoretical explanations for the experimental results we obtained. Our experiments also indicate that the running time of our implementation is O(n 3/2 k log k), while its worst-case running time complexity is O(n 2 k 2 log k).

Introduction

Computing visibility information in a 3D environment is crucial to many applications such as computer graphics, vision and robotics. Typical visibility problems include computing the view from a given point, determining whether two objects partially see each other, and computing the umbra and penumbra cast by a light source.

In a given scene, two points are visible if the segment joining them does not properly intersect any obstacle in the scene. The study of visibility is thus intimately related to the study of the set of free line segments in a scene. The visibility complex, which is, roughly speaking, a partition of the space of maximal free line segments into connected components of segments that touch the same objects, was proposed by Pocchiola and Vegter as a data structure encoding visibility information of a scene in 2D [START_REF] Pocchiola | The visibility complex[END_REF]. Durand et al. [START_REF] Durand | The visibility skeleton: a powerful and efficient multipurpose global visibility tool[END_REF][START_REF] Durand | The 3D visibility complex[END_REF] initiated the study of the visibility complex in 3D, and furthermore, introduced the visibility skeleton, which is essentially the zero and one-dimensional cells of the visibility complex, arguing that this smaller and simpler structure suffices for solving interesting visibility queries related to shadow computation [START_REF] Durand | The visibility skeleton: a powerful and efficient multipurpose global visibility tool[END_REF][START_REF] Durand | Fast and accurate hierarchical radiosity using global visibility[END_REF]. Although smaller than the visibility complex, the visibility skeleton is, nevertheless, a potentially enormous structure; it has worst-case size complexity O(n 4 ). Note that the visibility skeleton is related to the aspect graph [START_REF] Plantinga | Visibility, occlusion, and the aspect graph[END_REF] as the embedding of the visibility skeleton in R 3 is almost the partition of R 3 whose dual is the aspect graph.

Durand et al. implemented the visibility skeleton for polygonal scenes and demonstrated that use of the skeleton indeed results in higher quality light simulation in rendered images with improved computation time compared to previous algorithms [START_REF] Durand | Fast and accurate hierarchical radiosity using global visibility[END_REF]. Despite these positive results their pioneering approach suffers a major drawback. Their algorithm is not efficient because it is based on a systematic enumeration of all possibilities and thus has worst-case time complexity Θ(n 5 ) although the use of heuristics gives an observed complexity Θ(n 2.4 ) [START_REF] Durand | The visibility skeleton: a powerful and efficient multipurpose global visibility tool[END_REF]. Two other implementations, one by Glaves [START_REF] Glaves | An exploration of the 3D visibility complex[END_REF] for random triangles and another by Schröder [START_REF] Schröder | Globale Sichtbarkeitsalgorithmend[END_REF] for polytopes, yielded similar results. Duguet et al. [START_REF] Duguet | Robust epsilon visibility[END_REF] report an implementation that computes elements of the visibility skeleton needed for light simulations in the restricted setting of point-light sources (possibly at infinity); their results can thus not be compared to those mentioned previously.

Worst-case examples are somewhat artificial and indeed Durand et al. [START_REF] Durand | The visibility skeleton: a powerful and efficient multipurpose global visibility tool[END_REF] provide empirical evidence indicating that the O(n 4 ) worst-case upper bound on the size of the visibility skeleton is largely pessimistic in practical situations; they observe a quadratic growth rate, albeit for the rather small scenes (at most 1,500 triangles) that they were able to test. Again, these results were experimentally confirmed by Glaves [START_REF] Glaves | An exploration of the 3D visibility complex[END_REF] and Schröder [START_REF] Schröder | Globale Sichtbarkeitsalgorithmend[END_REF]. Some recent theoretical results also support the observation that the O(n 4 ) is pessimistic. When the inputs are k polytopes with n edges in total, [START_REF] Goaoc | Structures de visibilité globales : tailles, calculs et dégénérescences[END_REF][START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF] show that the number of vertices of the visibility skeleton is Θ(n 2 k 2 ) in the worst case. If the polytopes are disjoint and their silhouettes have worst-case complexity O( n/k), then the size of the visibility skeleton is O(nk 2 √ nk) [START_REF] Glisse | Combinatoire des droites et segments pour la visibilité 3D[END_REF]. Moreover, when the inputs are randomly distributed unit balls, the expected size is linear [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF]. Nevertheless, the problem of estimating the size of the visibility skeleton in practice for reasonably large input scenes has remained open for years because of the absence of a sufficiently efficient implementation.

We address in this paper the problem of computing and estimating the size of the visibility skeleton of k disjoint polytopes of total complexity n in generic position. In fact, we measure the size of the skeleton as the number of its vertices (since vertices have constant degree under general position assumptions). A definition of the visibility skeleton is given in Section 2. We present a robust implementation based on a sweep-plane algorithm that was first presented in [START_REF] Goaoc | Structures de visibilité globales : tailles, calculs et dégénérescences[END_REF] for the case of pairwise disjoint polytopes and generalized to the case of possibly intersecting polytopes in [START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF]. We then present experiments on k disjoint polytopes of size n/k, with vertices on congruent spheres randomly distributed with fixed densities in a given (spherical) universe. These experiments show that the number of vertices of the visibility skeleton is roughly C k √ nk where the observed constant C varies with scene density but remains small (less than 5 in our setting). Our experiments also indicate that the average running time of our implementation is O(n 3/2 k log k). By contrast, the theoretical worst-case running time of the algorithm in our setting is O(n 2 k 2 log k).

These results are significant for three reasons. First, this is the first experimentally determined asymptotic estimate of the number of vertices of the 3D visibility skeleton that takes into account not only the total number n of edges, but also the number k of polytopes in the scene. The results show that the size of the visibility skeleton may be sub-quadratic; in particular, they show a sub-linear growth in n and a sub-quadratic growth in k. Second, assuming that the size of the silhouette of a polytope on n/k vertices is O( n/k), our results show that we may express the size of the visibility skeleton as a function that is linear in the size of the silhouette and quadratic in the number of polytopes; that is, the number of vertices in the scene impacts the size of the visibility skeleton only insofar as it increases the size of the silhouettes. Finally, our results indicate that there is no large constant hidden in the big-Oh notation.

Notice that if each polytope has constant complexity (i.e., n/k in Θ(1)), our experiments show a quadratic growth (in n or k). This latter observation is consistent with previous experiments [START_REF] Durand | The visibility skeleton: a powerful and efficient multipurpose global visibility tool[END_REF][START_REF] Glaves | An exploration of the 3D visibility complex[END_REF] in which the scenes consist of polygons of constant complexity. We recall, however, that for constant-size polytopes of bounded aspect ratio contained in randomly distributed disjoint congruent spheres, the expected number of visibility events (sufficiently inside the universe) is linear [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF]. It is thus possible that our experiments did not treat scenes large enough to demonstrate the asymptotic behavior of the complexity; however, in such a case, our bound would be an overestimate.

In the next section, we give a definition of the visibility skeleton. In Section 3, we review the algorithm and discuss technical details of our implementation. We present our experimental results in Section 4 and conclude in Section 5.

The Visibility Skeleton of a Set of Polytopes

We start with some preliminary definitions. A polytope is the convex hull of a point set.

Here, polytopes are assumed to have nonempty interior. A plane is tangent to a polytope if it intersects the polytope but not its interior. A line or segment is tangent to a polytope if it intersects the polytope and is contained in a tangent plane. A line or segment is free if it does not intersect the interior of any polytope. A free line segment is maximal if it is not properly contained in another free line segment.

A support vertex of a line is a polytope vertex that lies on the line. A support edge of a line is a polytope edge that intersects the line but has no endpoint on it (a support edge intersects the line at only one point of its relative interior). A support of a line is one of its support vertices or support edges. The supports of a segment are defined to be the supports of its relative interior; thus if a maximal free segment ends at a vertex of a polytope, this vertex is not a support.

The visibility complex of smooth disjoint objects is, roughly speaking, the partition of the space of maximal free line segments into connected components of segments that are tangent to the same objects [START_REF] Pocchiola | The visibility complex[END_REF]. For polytopes, each cell of the complex is further subdivided so that the corresponding maximal free line segments have the same set of supports. The visibility skeleton [START_REF] Durand | The visibility skeleton: a powerful and efficient multipurpose global visibility tool[END_REF] is then naturally defined as the one-skeleton (i.e. the set of vertices and arcs) of the visibility complex.

In this paper, we study not the full one-skeleton but rather the skeleton containing only those arcs that correspond to local changes in the view, i.e., arcs such that, when a viewpoint crosses the surface generated by the set of segments corresponding to the arc, a new polytope comes into view or a previously seen polytope disappears; in particular, we do not consider the appearance or disappearance of a polytope feature as a change in the view. For pairwise disjoint convex smooth algebraic surfaces, it well known that these arcs consist of one-dimensional sets of maximal free line segments that are tangent to three objects (triple tangent events) or that are tangent to two objects in planes tangent to the two objects (tangent crossing events) [START_REF] Platonova | Singularities of relative position of a surface and a line[END_REF]. This also holds for pairwise disjoint polytopes [START_REF] Demouth | Événements visuels et limites d'ombres[END_REF]. 1With this in mind, we classify the arcs and vertices of the skeleton, in the spirit of Durand et al. [START_REF] Durand | The visibility skeleton: a powerful and efficient multipurpose global visibility tool[END_REF], as follows. Unless stated otherwise, no two supports come from the same polytope. An arc is of type EEE if its set of supports consists of three edges; it is of type EV if its set of supports consists of an edge and a vertex that define a plane tangent to their respective polytopes. A vertex is of type EEEE if its set of supports consists of four edges; it is of type VEE if its set of supports consists of a vertex and two edges; it is of type FEE if its set of supports consists of two edges on one face, and two additional edges; it is of type VV if its set of supports consists of two vertices that lie on a plane that is tangent to their two respective polytopes. 2In this paper, we study the number of vertices of the visibility skeleton thus defined and refer to it, with abuse of notation, as the size of the visibility skeleton. Since, under our general position assumptions, the degree of each skeleton vertex is bounded by a constant, the actual size of the skeleton, including the arcs, will be a constant factor away from what we measure.

Algorithm and Implementation

In this section, we first give a brief overview of the sweep-plane algorithm for computing the vertices of the visibility skeleton and then give details about its implementation. Algorithm. We give here a brief overview of the O(n 2 k 2 log k) algorithm for computing the vertices of the visibility skeleton of k convex disjoint polytopes with n edges in total and in general position. (Discussion about the general position assumption can be found below.) This algorithm was presented in [START_REF] Goaoc | Structures de visibilité globales : tailles, calculs et dégénérescences[END_REF] for the case of pairwise disjoint polytopes 3and then generalized to possibly intersecting polytopes in [START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF].

Given k convex disjoint polytopes in general position, that have n edges in total, the algorithm sweeps a plane about each edge e of each polytope in turn. The sweep plane is initially coplanar with one face incident to edge e and rotates about edge e until it becomes coplanar with the other face incident to e.

Initially, the sweep plane intersects the input polytopes in a set of polygons and the 2D visibility skeleton of these polygons is computed. This involves computing all the bitangents, the maximal free line segments tangent to two polygons. Generically, a bitangent is tangent to two polygons in the sweep plane at two vertices. Each of these vertices lies on an edge of the input polytopes; we call these edges the support edges of the bitangent. We represent the 2D skeleton by storing, for each polygon, the list of bitangents supported by that polygon, in sorted order about the polygon.

During the sweep, we maintain the 2D visibility skeleton of the polygons intersected by the sweep plane. An event occurs whenever a bitangent appears or disappears, the support edges of a bitangent change, or when there is a change in the order of the bitangents around a polygon vertex. The EEEE, VEE, and FEE skeleton vertices arise from some of these events. (See [START_REF] Zhang | Towards an implementation of the 3D visibility skeleton[END_REF] for a video on the algorithm.)

The worst-case running time of this algorithm is O(nk 2 log k) per sweep, that is O(n 2 k 2 log k) in total. 4 Notice that the Θ(nk 2 log k) worst-case bound for one sweep can be quite pessimistic: the time complexity of each sweep is, modulo the logarithmic factor, proportional to the complexity of the 2D visibility skeleton over the whole sweep, that is, to the number of combinatorially distinct bitangents occurring during the sweep. In particular, the time complexity of one sweep can be sub-linear in n. Note that this differs from the algorithms presented in both [START_REF] Efrat | On incremental rendering of silhouette maps of a polyhedral scene[END_REF] and [START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF] which maintain all line segments tangent to two polygons in the sweep plane, even if they are not free. Implementation. While our ultimate objective is a robust implementation that correctly computes the visibility skeleton vertices on a set of polyhedra in arbitrary position in a reasonable amount of time, our current implementation takes as input any set of convex polyhedra and either outputs the skeleton vertices or reports that the polytopes are not in general position (see below). We implemented the algorithm in C++ using the CGAL library [START_REF]CGAL: Computational Geometry Algorithms Library[END_REF] with the 2D visibility skeleton package due to Angelier and Pocchiola [START_REF] Angelier | CGAL-based implementation of visibility complexes[END_REF]. Predicates. Several predicates are required by the algorithm including, for example, determining whether four segments admit a line transversal. As in all sweep algorithms, an essential predicate is one that compares two positions of the sweep plane. The algebraic degree of some of these predicates is quite high; in particular, comparing two positions of the sweep plane is implemented with a procedure of degree 168 in the Cartesian coordinates of the input vertices. See [START_REF] Everett | On the degree of standard geometric predicates for line transversals in 3[END_REF] for details. Number type. Our implementation follows the paradigm of exact computation; we have implemented all predicates using the Filtered_exact number type of CGAL (3.2.1) templated with CGAL interval arithmetic (based on double number type) and the CORE library [START_REF]The CORE library[END_REF]. This means that the predicates are first evaluated using interval arithmetic, and only when this fails are they evaluated using the CORE exact number type. Using filtered exact computation ensures that no predicate is ever incorrectly evaluated; however, this comes at a cost: on random inputs, the computation is no more than four times slower than when using the double number type. General position assumption. By polytopes in general position we mean that no predicate evaluates to zero. 5 In particular, this guarantees that each event corresponds to a unique position of the sweep plane. 6 It also implies more familiar assumptions such as that no two polytope faces are coplanar; see [START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF] for more details. To the best of our knowledge, there exists no implementation of the 3D visibility skeleton that handles degeneracies, including the implementation of Durand in which degeneracies were avoided by perturbing the input scenes by hand (Duguet [7] proposed a method for handling degeneracies but, as previously noted, only for computing a section of the visibility skeleton, that is a set of maximal free line segments that are supported by concurrent lines.) Our code represents an improvement in the sense that we systematically detect all degeneracies although the code to handle them remains unwritten.

Software validation.

We verified the correctness of our implementation by comparing its output with that of an implementation of the brute force algorithm, the latter being straightforward, having only about a thousand lines of code. We ran tests on twenty input scenes of up to 100 polytopes with up to 1 000 edges and obtained the same results for both implementations, that is, the same list of vertices.

Experiments

The model. The input scenes are generated in two phases. First, we generate a set of disjoint spheres and, in phase two, we generate one convex polytope in each sphere.

In phase one, for a given number of spheres k and scene density µ, we generate k unit spheres in a spherical universe of center O and radius R, where R = 3 k/µ (that is, µ = k 4 3 π/ 4 3 πR 3 ). The centers of the spheres are chosen, one by one, uniformly from the ball centered at O of radius R-1. When a newly generated sphere intersects any existing one, the new sphere is discarded. Note that the spheres are not uniformly distributed since the new sphere is not chosen independently of the previous ones.

In phase two, for each sphere, a set of vertices is generated uniformly on the surface of the sphere and their convex hull is computed. This defines one polytope for each sphere and guarantees that they are disjoint. Notice that the density of the polytopes in the scene is somewhat less than the density µ of the spheres of phase one.

We emphasize that our objective is not to study uniformly distributed disjoint polytopes approximating spheres. We have chosen this scene model because it provides a simple way to generate large scenes containing disjoint polytopes. Furthermore, it allows us to compare our results with the theoretical results of [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF].

The experiments. We consider scenes of polytopes, as defined above, depending on three parameters, the number k of polytopes, the total number n of polytope edges, and the scene density µ. We perform three suites of experiments in which we measure the number of visibility skeleton vertices.

In Suite I, we fix the scene density µ and the number n/k of edges per polytope. For different values of k, we generate scenes of k polytopes each having n/k edges.

It appears that, even in the random setting of our experiments, predicates are evaluated incorrectly about 0.1% of the times when using the double number type. 6 Actually, this guarantees that no two unrelated events correspond to the same position of the sweep plane. The situation where three bitangents become aligned induces three events corresponding to an alignment of any two of these bitangents; these three events are in the same sweep plane yet the situation is generic. We perform experiments for µ = 0.3, 0.05 and 0.01 and for n/k ≈ 6, 42 and 84. 7 In Suite II of our experiments, we also fix the scene density µ to 0.3 and vary the number n/k of edges per polytope for fixed numbers of polytopes. Namely, we consider k = 30, 60, and 90 and vary n/k from 6 to 102. As we will see, these experiments confirm that when n/k varies (in the given range), the complexity observed in the first set of experiments holds.

Note that a scene with density µ = 0.3 is very dense (see Fig. 1 and recall Kepler's Theorem that the density of any sphere packing in 3D space is at most π/3 √ 2 ≈ 0.74). Density µ = 0.3 is close to the highest density we can reach in a reasonable amount of time with our scene generation scheme. Machine characteristics. All the experiments were done on an i686 machine with a Pentium 2.80 GHz CPU running Linux, with 2 GB of main memory. Running time was measured with the getrusage() command and the ru_utime attribute.

Experimental Results and Analysis

Number of skeleton vertices in terms of n. We present, in terms of the total number n of edges in the scene, the results of Suite I for density µ = 0.3. For n/k ≈ 6, 42 and 84, respectively, Fig. 2(a) shows the total number of visibility skeleton vertices; Fig. 2(b) shows the running time of our implementation in seconds.

For a given value of n/k, the number of skeleton vertices appears to be quadratic in n (see Figs. 2(a) and 3(a)) and the running time appears to be in Θ(n 2.5 log n) (see Figs. 2(b) and 4(b)). Notice also that for a fixed n, both the running time and the size of the output drop drastically when the number k of polytopes decreases (see Fig. 2). These observations are consistent with the theoretical bounds; the worst-case time complexity of the algorithm is in O(n 2 k 2 log k) and the worst-case output size is in Θ(n 2 k 2 ) [START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF]. The rest of this section analyses the running time and output size in terms of n and k. Number of skeleton vertices in terms of n and k. Fig. 3 shows the number of skeleton vertices in terms of k √ nk = k 2 n/k. The number of these skeleton vertices appears to be linear in this parameter with a constant that depends on the scene density µ. For µ = 0.3, 0.05, and 0.01, the constant is roughly 5, 4, and 3. The constant appears to decrease in terms of µ which is consistent with the intuition that the constant goes to zero as the scene density goes to zero (since the probability that there exists a line transversal to three polytopes goes to zero as the density goes to zero and that the number of vertices of type VV is asymptotically negligible).

Note that, for any fixed density µ and any given value of k 2 n/k, the number of these skeleton vertices varies very little in terms of the polytope complexity n/k (Fig. 3(a)) and in terms of the number of polytopes (Fig. 3(b)). This suggests that C µ k 2 n/k is a good predictor of the number of these skeleton vertices regardless of the polytope complexity, at least for the scene density µ and the ranges of n/k used here.

Our experiments thus indicate that, in our setting, the number of skeleton vertices is roughly C µ k 2 n/k, where C µ is a constant that depends on the density µ of the scene. The experiments hint that this constant is small and is a decreasing function of µ.

This observed complexity is, as expected, much smaller than worst-case bounds. Recall that, for k polytopes with n edges in total, the worst-case number of skeleton vertices is Θ(n 2 k 2 ) [START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF]. Also, if the silhouettes of the polytopes have size n/k in the worst case, the worst-case number of skeleton vertices is O(nk 3 n/k) [15, §6.7]. These worst-case bounds are much larger than our observed size (by a factor n √ nk and nk). We analyze below the observed complexity of C µ k 2 n/k in terms of (i) k when the complexity of the polytopes is constant, and (ii) the silhouette size of the polytopes when the number k of polytopes is constant.

Analysis of the number of skeleton vertices in terms of k.

If each polytope has constant complexity (i.e., n/k in Θ(1)), our experiments exhibit a quadratic growth (in terms of k) of the number of skeleton vertices. This is consistent with previous experiments [START_REF] Durand | The visibility skeleton: a powerful and efficient multipurpose global visibility tool[END_REF][START_REF] Glaves | An exploration of the 3D visibility complex[END_REF] in which the scenes consist of polygons of constant complexity and is also consistent with the best known theoretical expected upper bound of O(k 2 ) [6] corresponding to our setting. However, this contradicts the intuitive linear bound of Θ(k) when n/k is constant; indeed, recall that for k randomly distributed congruent spheres, the expected number of visibility events is linear and, for constant-size polytopes of bounded aspect ratio inside such spheres, the expected number of visibility events is linear for events that occur sufficiently inside the universe but it is only upper bounded by O(k 2 ) for events near the boundary of the universe [START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF]. It is possible that the expected upper bound of O(k 2 ) is tight but it is also possible that our experiments did not reach the asymptotic behavior of the complexity. If this is the case, it is then reasonable to believe that our experimental estimate of the complexity is an overestimate.

Analysis of the number of skeleton vertices in terms of the silhouette size of the input polytopes. If we fix the number k of polytopes and vary the total number n of edges, our experiments show that the number of skeleton vertices depends linearly on n/k. We argue below that this means that, in our setting, when k is fixed, the number of skeleton vertices depends linearly on the silhouette size of the input polytopes and explain why.

Recall that, for any polyhedron of size Θ(m), the size of its silhouette viewed from a random point is O( √ m) under some reasonable hypotheses [START_REF] Glisse | An upper bound on the average size of silhouettes[END_REF] (see also [START_REF] Kettner | Contour edge analysis for polyhedron projections[END_REF] for the special case of polyhedra that approximate spheres). Since the vertices of the polytopes we consider are randomly distributed on a sphere, it is reasonable to assume that the size of the silhouette does not depend much on the choice of the viewpoint. In other words, for any polytope with n/k edges we consider, it is reasonable to assume that its silhouette has size O( n/k) from any viewpoint. Hence, when k is fixed, the number of skeleton vertices depends linearly on the silhouette size of the input polytopes.

We offer the following intuitive explanation of this observation. Consider the arcs of type EEE of the skeleton. The endpoints of these arcs are vertices of type VEE, FEE or EEEE. When the number k of polytopes is fixed and the number n of edges tends to infinity, the polytopes tend to spheres and the segments corresponding to vertices of type EEEE converge to segments that are tangent to four spheres; hence, in our setting, the number of EEEE vertices converges to a constant. Similarly, for those V EE vertices that correspond to intersections of two arcs of types VE and EEE (thus corresponding to segments tangent to three polytopes while lying in planes that are tangent to two of them). Moreover, in the successive refinements of polytopes as n increases, each EEE arc incident to an EEEE vertex or one of the above VEE vertices will become a sequence of EEE arcs joined at VEE vertices (that is, subdivision vertices such that the sets of supports are invariant along the subdivided arcs). For such a sequence of arcs, the number of these VEE vertices is the number of polytope vertices encountered by a maximal free line segment as it slides from the segment corresponding to one end of the sequence to the other, while remaining tangent to the three polytopes (nearly spheres) involved. The number of such polytope vertices is, intuitively, at most the worst-case size of the silhouette of each polytope, which we have assumed to be in O( n/k). As a polytope gets more complex and tends to a sphere, the subset of lines in the line space that are tangent to the polytope on its vertices tends towards the subset of lines that are tangent to the sphere. This is also the case for lines tangent to the polytope on its faces. For this reason, the number of FEE vertices is asymptotically the same as that of VEE vertices. Thus, intuitively, we can expect that, for fixed k, (i) the number of vertices of type EEEE converges to a constant as n goes to infinity, (ii) the number of vertices of type VEE or FEE is in O( n/k) times the number of EEEE vertices, and thus that (iii) the number of VEE and FEE vertices is in O( √ n) (for k fixed). In experiments not reported here, we have observed (ii) and (iii), but not (i). In Figure 4(a), the number of VEE vertices is much larger than the number of EEEE vertices, which is consistant with the previous discussion, while the convergence of EEEE is not seen in our experimental range.

Finally, the number of VV vertices is, intuitively, bounded by the product of the number of pairs of polytopes that are mutually visible (which is asymptotically linear in k for any given density) and the size of the polytope silhouettes. Hence the number of VV vertices is presumably in Θ(k n/k). Note that in our experiments (Fig. 4(a)) we observe a complexity of roughly Θ(k 2 n/k) because the number of visible pairs of polytopes is quadratic in k in our experimental range.

Running time in terms of n and k. We study the running time of our implementation in terms of n √ n k log k for experiments in Suite I, and show the results for scene density µ = 0.3 in Fig. 4(b) (our results for other densities are omitted here). We observe that for a fixed polytope complexity n/k, the running time seems linear in n √ n k log k. More precisely, we observe a running time of C ′ µ n √ n k log k seconds with C ′ µ no more than 3 • 10 -4 for the considered densities. Note, however, that for density 0.3, the data we obtained from groups n/k ≈ 42 and 84 fit the estimated time complexity well, whereas the data from the group n/k ≈ 6 is a constant factor away.

The observed running time can be intuitively explained as follows. Note first that n √ n k log k is equal to n n/k k √ k log k. We dissect this expression as follows. First, n is the number of sweeps performed by the algorithm. We observe that the factor k √ k is linearly related to the average over all sweeps of the maximal number of bitangents encountered in the sweep plane during a sweep (we omit here the presentation of these experiments). This is reasonable since the number of bitangents in the sweep plane varies from Θ(k 2 ), the trivial worst-case bound, to Θ(k), the expected bound in the right setting [START_REF] Everett | On the expected size of the 2D visibility complex[END_REF]. Furthermore, the factor n/k naturally relates to the number of updates caused by each bitangent during the sweep; indeed, following a bitangent during a sweep, the bitangent will encounter vertices on each of the two polytopes supporting it; the number of these vertices on each polytope is related and, intuitively, is less than the worst-case size of the silhouettes of the polytopes which, as we argued above, is in O( n/k) in our setting. Finally, log k is the complexity of each update of the event list.

Conclusion

We have presented here an implementation of the sweep-plane algorithm to compute the visibility skeleton. Our experiments suggest that, in our setting, the number of vertices of the 3D visibility skeleton is C µ k √ n k and is dominated by type VEE vertices. The constant C µ , which depends on the scene density, is no more than 5 for n and k in our experimental range, and for the various densities that we studied. This is the first prediction of the actual size of the 3D visibility skeleton for reasonably large n, and expressed in terms of both n and k. Assuming that the size of the silhouette of a polytope with n/k edges is O( n/k), our results show that the size of the visibility skeleton is linear in the size of the silhouette and quadratic in the number of polytopes. Surprisingly, the constant C µ is rather small; this indicates that there is no large constant hidden in the big-Oh notation.

The experiments also suggest that the expected running time of our implementation of the sweep plane algorithm is C ′ µ n √ n k log k seconds, where C ′ µ depends on the scene density but is, on our machine, no more than 3 • 10 -4 for the considered densities.

Our results indicate that the visibility skeleton is of reasonable size and can be computed exactly in a reasonable length of time. Further work includes completing the implementation for degenerate situations. A major challenge is to extend the sweep algorithm to handle general polyhedra.

Fig. 1 .

 1 Three sample scenes with scene density µ = 0.3 and k = 50 polytopes whose number of edges, n/k, is approximately equal to (a) 6, (b) 42, and (c) 84.

  (A sample scene with k = 50 is shown in Fig. 1.) For each value of n/k, we vary the number k of polytopes as follows: (a) when n/k ≈ 6, we vary k from 10 to 190 (giving n ∈ [75, 1 425]), (b) when n/k ≈ 42, we vary k from 10 to 130 (giving n ∈ [400, 5 200]), and (c) when n/k ≈ 84, k varies from 10 to 110 (giving n ∈ [850, 9 400]). As we will see, the number of visibility skeleton vertices appears to be roughly C µ k √ nk in these experiments where C µ is a constant that depends on the density.

Fig. 2 .

 2 Fig. 2. Suite I (µ = 0.3): (a) total number of skeleton vertices and (b) running time (in seconds; 2.88 × 10 4 seconds = 8 hours) in terms of n, the number of edges in the scene.

Fig. 3 .

 3 Fig. 3. Total number of skeleton vertices in terms of k 2 n/k when (a) the polytopes have a constant (n/k) number of edges (Suite I) and (b) the number k of polytopes is constant (Suite II).

Fig. 4 .

 4 Fig. 4. Suite I (k polytopes having a constant, n/k, number of edges; µ = 0.3): (a) proportion of number of vertices in terms of k 2 n/k and (b) running time (in seconds) in terms of n 1.5 k log k.

Note that the visibility skeleton for smooth objects does not contain the arcs that correspond to tangent crossing events. On the other hand, the one-skeleton of the visibility complex of polytopes contains all arcs corresponding to visual events (as they appear as sets of segments tangent to two objects); however, it also contains many arcs that do not correspond to a local changes in the view (but only to the the appearance or disappearance of a polytope feature).

This catalog is a subset of the one in[START_REF] Durand | The visibility skeleton: a powerful and efficient multipurpose global visibility tool[END_REF] because Durand et al. essentially consider the oneskeleton of the visibility complex. They consider, in particular, line segments supported by two vertices which do not lie on a plane tangent to the two polytopes. This has an impact on the asymptotic size of the structure since the number of such vertices is presumably linear in the total complexity of the polytopes (in our experimental setting).

[START_REF]CGAL: Computational Geometry Algorithms Library[END_REF] Efrat et al.[START_REF] Efrat | On incremental rendering of silhouette maps of a polyhedral scene[END_REF] presented a similar algorithm for computing not necessarily free isolated transversals in the same setting.

Note that both[START_REF] Goaoc | Structures de visibilité globales : tailles, calculs et dégénérescences[END_REF] and[START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF] report algorithms having time complexity O(n 2 k 2 log n) instead of O(n 2 k 2 log k); the reason for this is that, in[START_REF] Goaoc | Structures de visibilité globales : tailles, calculs et dégénérescences[END_REF], the skeleton is reconstructed which is not the case here and, in[START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF], the event queue may be of size Θ(n) because the polytopes may intersect.

Note that filtered-exact arithmetic is still needed under this general position assumption since predicates could still be evaluated incorrectly with a fixed-precision floating-point arithmetic.

fact, we generate polytopes whose numbers of vertices range in[START_REF]The CORE library[END_REF][START_REF] Devillers | The expected number of 3D visibility events is linear[END_REF],[START_REF] Glisse | Combinatoire des droites et segments pour la visibilité 3D[END_REF][START_REF] Goaoc | Structures de visibilité globales : tailles, calculs et dégénérescences[END_REF] and [30, 32], respectively. The number of edges per polytope is thus not actually fixed but varies slightly; the polytopes we generated have, on average,7.5, 40, and

edges, respectively.


domain: spi chim

text:
Tobias A Gmür

Joydeb Mandal

Juliette Cayer-Barrioz

Nicholas D Spencer
email: nspencer@ethz.ch

Towards a Polymer-Brush-Based Friction Modifier for Oil

Keywords: Lubricant additive, Friction reduction, RAFT polymerization, Block copolymer, Oil compatibility

To meet the need for oil-compatible friction modifier additives that can significantly reduce energy consumption in the boundary-lubrication regime, a macromolecular design approach has been taken. The aim was to produce a lubricious polymer film on the sliding surfaces. A series of readily functionalizable block copolymers carrying an oleophilic poly(dodecyl methacrylate) block and a functionalizable poly(pentafluorophenyl methacrylate) block of various lengths was synthesized by means of reversible addition-fragmentation chain-transfer (RAFT) polymerization. The poly(pentafluorophenyl methacrylate) block was used to attach surface-active nitrocatechol anchoring groups to the polymer. The friction-reduction properties of these polymers were assessed with 0.5 wt% solutions in hexadecane by means of rolling-sliding macroscopic tribological tests. Block copolymers with roughly equal block lengths and moderate molecular weights were significantly more effective at friction reduction than all other architectures investigated. They also displayed lower friction coefficients than glycerol monooleate-a commercially used additive. The film-formation ability of these polymers was examined using a quartz-crystal microbalance with dissipation (QCM-D), by monitoring their adsorption onto an iron oxide-coated QCM crystal. The polymer with highest lubrication efficiency formed a thin film of ~ 17 nm thickness on the crystal, indicating the formation of a polymer brush. Interferometric rolling-sliding experiments with the same polymer showed a separating film thickness of ~ 20 nm, which is consistent with the QCM-D value, bearing in mind the compression of the adsorbed layers on the two sliding surfaces during tribological testing.

Introduction

We are living in a world in which both the sources and uses of energy are rapidly changing, with significant impact on our needs for lubricants, and especially for additives that are active in boundary lubrication. The advent of electric vehicles means that thermally activated lubricant additives are less effective, and it also presents new requirements for lubricants, such as extremely low viscosity at speeds higher than 20,000 rpm [START_REF] Farfan-Cabrera | Tribology of electric vehicles: A review of critical components, current state and future improvement trends[END_REF], placing greater demands on the boundary-lubrication performance upon startup. Internal combustion and hybrid vehicles will be with us for decades yet, and among the measures proposed for energy saving [START_REF] Carpick | Tribology Opportunities or Enhancing America's Energy Efficiency[END_REF] have been self-healing ultrathin tribofilms that are active under boundary-lubrication conditions in reduced-viscosity lubricants [START_REF] Ishizaki | Reduction of CO 2 emissions and cost analysis of ultra-low viscosity engine oil[END_REF]. Wind turbines have rapidly ascended in importance, but their effective lubrication, including under boundary-lubrication conditions, remains a significant challenge [START_REF] Dhanola | Tribological challenges and advancements in wind turbine bearings: a review[END_REF]. In short, the development of lubricant additives for the boundary regime, i.e. friction modifiers, is more important than ever.

New approaches are needed to improve upon the current state of the art in friction modifiers, which include small organic molecules, organo-molybdenum compounds, and, the focus of this study, polymeric additives [START_REF] Spikes | Friction Modifier Additives[END_REF]. Polymers have been found to be beneficial for friction and wear properties of engine oils for many decades [START_REF] Okrent | The effect of lubricant viscosity and composition on engine friction and bearing wear[END_REF]. In general, however, their use has been motivated by their viscositymodification [START_REF] Martini | Review of viscosity modifier lubricant additives[END_REF] or dispersion [START_REF] Burrington | Challenges in Detergents and Dispersants for Engine Oils[END_REF] properties. The beneficial friction-reduction properties of polymeric friction modifiers (PFMs) in commercial engine oils were extensively investigated in the 1990s [START_REF] Cann | The behavior of polymer solutions in concentrated contacts: immobile surface layer formation[END_REF][START_REF] Smeeth | The formation of viscous surface films by polymer solutions: boundary or elastohydrodynamic lubrication?[END_REF][START_REF] Gunsel | Friction and wear reduction by boundary film-forming viscosity index improvers[END_REF], and were ascribed [START_REF] Guangteng | Measurement and modelling of boundary film properties of polymeric lubricant additives[END_REF] to a surface enrichment of the polymeric species, leading to a local increase in viscosity. Later investigations [START_REF] Tohyama | Friction reducing effect of multiply adsorptive organic polymer[END_REF][START_REF] Aoki | Verification of the advantages in friction-reducing performance of organic polymers having multiple adsorption sites[END_REF][START_REF] Hobday | Friction modifiers for next generation engine oils[END_REF][START_REF] Guegan | Friction modifier additives, synergies and antagonisms[END_REF] reiterated the potential of PFMs, but the precise chemical identity of the investigated additives was generally undisclosed. A notable exception to this trend was the work from the group of Spikes at Imperial College, [START_REF] Müller | The design of boundary film-forming pma viscosity modifiers[END_REF][START_REF] Fan | Reduction of friction by functionalised viscosity index improvers[END_REF], in which a broad range of poly(alkyl methacrylate)-based copolymers with a multitude of different polar groups, serving as surfaceactive moieties, were investigated. Polymer-architectural effects were highlighted by showing the superior frictionreduction properties of a block copolymer compared to a random copolymer.

The synthesis and friction/wear properties of novel viscosity modifiers have also been precisely described in recent years [START_REF] Cosimbescu | Low molecular weight polymethacrylates as multifunctional lubricant additives[END_REF][START_REF] Bapat | Lipophilic polymethacrylate ionic liquids as lubricant additives[END_REF][START_REF] Campbell | Multifunctional tunable polymethacrylates for enhanced shear stability and wear prevention[END_REF]. However, in general their effect on friction reduction under boundary-lubrication conditions is somewhat limited and requires relatively high polymer loadings.

The present study brings together two previous developments in polymer-brush lubrication. On the one hand oleophilic polymer brushes grown from a silicon surface were shown to display excellent lubricious properties in a range of common base oils [START_REF] Bielecki | Polymer-brush lubrication in oil: sliding beyond the stribeck curve[END_REF]. On the other hand, in aqueous environments it was found that a dilute solution of the graft copolymer poly(L-lysine)-graft-poly(ethylene glycol) (PLLg-PEG) could reduce friction dramatically, the -NH 2 groups on the PLL backbone acting as anchors to the surface, and statistically grafted PEG chains forming a lubricious polymer brush [START_REF] Lee | Self-healing behavior of a polyelectrolyte-based lubricant additive for aqueous lubrication of oxide materials[END_REF]. In light of this, an initial study focused on the use of newly synthesized graft copolymers as schematically illustrated in Fig. 1a to reduce friction in oil, this time using oleophobic chains to form brushes and statistically distributed anchors that would form covalent bonds with the surface. The effectiveness of such an approach appeared to be very limited, however (see Sect. 1 in the Supporting Information for details). Previous investigations on graft copolymers such as PLL-g-PEG have shown experimentally [START_REF] Serrano | Novel Polymer-Brush Based Coatings for Regulating Bioadhesion[END_REF] and through computational models [START_REF] Feuz | On the conformation of graft-copolymers with polyelectrolyte backbone in solution and adsorbed on surfaces[END_REF], that in aqueous solutions the long-range electrostatic force is crucial for the graft copolymers to attach to the surface in a brush-like configuration, overcoming the steric hindrance of the polymer chains (e.g. the conformational transition from Fig. 1a to c). In oil, the surfaces are not intrinsically charged, and so this mechanism is not an option. The use of alternative anchoring strategies, such as the formation of covalent bonds, requires a closer approach of the anchor to the surface than is feasible in the presence of lengthy co-grafted polymer side chains.

One of the ways in which such a steric effect of the oleophilic side chains can be minimized is by designing block copolymers carrying an oil-soluble, brush-forming block and a surface-active block as depicted in Fig. 1b. This allows free access of the anchoring groups to the surface without impediment from the brush-forming chains. Clearly there is a balance to be achieved between the length of the two kinds of blocks (i.e. polymer-architectural parameters), and there are many anchoring-group chemistries that could be explored. This paper describes the synthesis of novel block copolymer PFMs whose molecular structures have been designed to allow for facile exploration of both blockcopolymer architecture and anchoring chemistry. We focus here on the investigation of the architecture, the anchoring moieties being limited to nitrocatechol, which is designed to interact strongly and similarly with many non-noble, transition-metal surfaces (and the corresponding oxidized surfaces), such as steel, iron, or chromium, via a combination of coordination chemistry and hydrogen bonding [START_REF] Zürcher | Biomimetic surface modifications based on the cyanobacterial iron chelator anachelin[END_REF][START_REF] Amstad | Ultrastable iron oxide nanoparticle colloidal suspensions using dispersants with catechol-derived anchor groups[END_REF][START_REF] Saiz-Poseu | The chemistry behind catechol-based adhesion[END_REF], in contrast to the weaker, polar interactions that have been generally relied upon for PFMs to date. The influence of alternative anchoring chemistries will be reported in detail elsewhere. The PFMs were evaluated for their frictional performance in rolling-sliding macroscale contact in low-viscosity oils, on both steel and chromium, and their adsorption properties were studied with the quartz-crystal microbalance (QCM) [START_REF] Reviakine | Hearing what you cannot see and visualizing what you hear: interpreting quartz crystal microbalance data from solvated interfaces[END_REF][START_REF] Lundgren | Adsorption of fatty acids from alkane solution studied with quartz crystal microbalance[END_REF][START_REF] Lundgren | Unsaturated fatty acids in alkane solution: adsorption to steel surfaces[END_REF][START_REF] Nalam | Adsorption behavior and nanotribology of amine-based friction modifiers on steel surfaces[END_REF][START_REF] Zachariah | Correlation between the adsorption and the nanotribological performance of fatty acid-based organic friction modifiers on stainless steel[END_REF][START_REF] Fry | Adsorption of organic friction modifier additives[END_REF][START_REF] Van Ravensteijn | Triple function lubricant additives based on organicinorganic hybrid star polymers: friction reduction, wear protection, and viscosity modification[END_REF][START_REF] Murdoch | Sticky but slick: reducing friction using associative and nonassociative polymer lubricant additives[END_REF][START_REF] Dardin | Lubricating oil composition with good frictional properties[END_REF], using iron oxide-coated sensors.

Materials and Methods

Materials

The synthetic pathway is summarized in Fig. 2 (the details of raw materials used and synthesis conditions are given in Sect. 2 of the Supporting information). First, an oleophilic block is produced by RAFT polymerization of an oleophilic monomer to yield a polymer with an active chain end. This is used in a second polymerization as a macro chain-transfer agent (CTA). A block of functional units is added to the polymer, which is modified with nitrodopamine in a final step to yield a poly(dodecyl methacrylate)-block-poly(nitrodopamine acryl amide) (p12MA-b-pNDAcrAm).

Five different polymer structures are discussed here, with differing degrees of polymerization m and n (as derived from NMR conversion measurements) being presented in Table 1. The motivation for the choice of synthesized structures was to start off at what is reported to work in the literature: block copolymers with an overall molecular weight of roughly 25 kDa [START_REF] Dardin | Lubricating oil composition with good frictional properties[END_REF] and a functionalization percentage of 10 mol% [START_REF] Fan | Reduction of friction by functionalised viscosity index improvers[END_REF]. This was achieved with PFM A. The other structures were designed to investigate the effects of the different size parameters. While B contained a larger anchoring block, D and E were intended to take structure A to a higher molecular weight with constant relative and absolute anchoring block sizes, respectively. Polymer C is a larger version of B and was synthesized in light of the promising early results of the latter.

The additives were dissolved at 0.5 wt% in either hexadecane (Acros Organics), PAO2 or PAO6 (both kindly donated by Blaser Swisslube) at 80 °C under stirring overnight. All solutions were subsequently left to reach room temperature, centrifuged at 4000 rpm for 10 min, decanted and only the supernatant liquid used for further experiments.

Methods

Rheometry

Rheological measurements in an Anton Paar MCR302 Rheometer with double-wall accessory were used to quantify the effect of PFM-additive addition to the bulk dynamic viscosity of hexadecane. For PAO2 and PAO6, the measurements were carried out in a cone/plane rheometer with a 60 mm diameter cone and a shear rate of 10 s -1 and 0.1 s -1 , respectively, covering the range 15-60 °C.

QCM-D

Quartz-crystal-microbalance measurements were conducted on a QCM-D E4 (Biolin Scientific AB, Sweden) at 25 °C. To obtain reproducible results, the iron oxide (QSX 326, Fe 3 O 4 ) coated sensors were only used freshly out of the box. They were sonicated for 20 min in ethanol, rinsed with ultrapure water and blown dry with filtered nitrogen. The rest of the measurement setup was sonicated in isopropanol and hexane prior to assembly. Each of the four cells was connected in parallel to a peristaltic pump and rinsed with hexadecane for 4 h at a constant flow rate of 2.5 μL / s through each sensor to achieve a flat baseline. The subsequent measurement consisted of 20 min of further equilibration, after which the lubricant solution was flowed through the cells for 20 min, and finally the cells were purged with pure hexadecane again for 20 min.

The adsorbed masses of the polymers (including trapped solvent) were calculated using the Sauerbrey equation [START_REF] Sauerbrey | Verwendung von Schwingquarzen zur Wägung dünner Schichten und zur Mikrowägung[END_REF]. Measurements were carried out using four sensors simultaneously, although only for overtones 5, 7, and 9 was the signal-to-noise ratio deemed sufficient for further processing. The presented derived quantities are the averages of those 12 different values with standard deviations.

Tribology: MTM

The mini-traction-machine (MTM) measurements were performed on a MTM2 (PCS Instruments, UK) with the standard specimen pack (100Cr6 balls and disks, R a < 20 nm) as received and sonicated in isooctane. The temperature was set to 30 °C and the normal load maintained at 2 N if not mentioned otherwise, resulting in an average pressure of 256 MPa. Stribeck curves were obtained repeatedly with increasing and decreasing speed ramps from 1 to 2000 mm/s. The slide-to-roll ratio, as defined by SRR =

U sliding /U entrainment = 2*|U b -U d |/(U b + U d )
was maintained at 50% throughout, where U b and U d correspond to speeds of the ball and disk, respectively, with respect to the contact. Running-in effects made the first measurement incomparable to the rest of the set, which is why it was omitted. The data presented for the Stribeck-curve measurements are averages, together with their 95% confidence intervals from 4 repetitions. Comparative measurements were performed in pure hexadecane and with 0.5.wt% glycerol monooleate (GMO), which is a commercially used organic friction modifier.

Tribology: IRIS

The IRIS tribometer, developed in LTDS, Ecole centrale de Lyon, is described in detail elsewhere [START_REF] Ernesto | The combined role of soot aggregation and surface effect on the friction of a lubricated contact[END_REF]. In short, a 100Cr6 steel ball and a silica disk (sonicated in heptane and isopropanol, and then dried under nitrogen flow) are brought into contact and rotated independently under controlled kinematic conditions. The polished ball and the disk both had a rms roughness of 5 nm, measured with a Bruker Contour GT-K interferometer. The silica disk was coated with a 6-nm thick semi-transparent chromium layer that allowed for visualization of the tribocontact and simultaneous interferometric determination of the absolute distance between the two. The normal force was fixed at 5 N (resulting in an average pressure of 212 MPa) and continually monitored on the ball, while the torque on the disk assembly allowed for the direct calculation of friction forces. These conditions (metallic surfaces and contact pressures) were selected, in order to monitor film formation under similar conditions as in the MTM experiments. The actual measurement started with an initial pure rolling period at 10 mm/s. After this, the SRR was set to 50% and the entrainment velocity was decreased to 2 mm/s, increased to 200 mm/s and decreased to 10 mm/s again stepwise. The first pure rolling step was used to calculate the frictional force offset, later pure rolling steps served as a measure to check for instrumental drift. The traction coefficient reported at any given entrainment velocity is the average between positive and negative SRR ratios (i.e. only Couette friction is considered and the Poiseuille term is neglected), while the error bars represent the aggregated 95% confidence interval. The measurements were conducted under ambient conditions (i.e. 27.5 °C and 40 RH%).

The film thickness and its distribution in the high-pressure zone were measured using two independent methods: in situ during the experiment, using the color of the steel/chromium contact with an appropriate calibration, and post-experiment, using a spacer-layer-coated disk. The first method gave a comparative, order-of-magnitude estimate of the evolution of the film thickness with the entrainment velocity, averaged over 6 images with low resolution (about 10 nm) while the second method gave a more accurate and absolute value of the adsorbed film thickness on the steel ball after the experiment with a resolution of a few nanometers.

In parallel, these experimental values were compared to the calculated hexadecane film thickness. The pressure-viscosity coefficient of hexadecane was deduced from the data presented by Meng et al. [START_REF] Meng | Reference correlation of the viscosity of n-hexadecane from the triple point to 673 K and up to 425 MPa[END_REF] fitted with Roelands' equation [START_REF] Roelands | Correlational Aspects of the Viscosity-Temperature-Pressure Relationship of Lubricating Oils[END_REF] and a viscosity of 3 mPa.s. The resultant value, α = 10 GPa -1 , was low, leading to the use of Moes-Venner prediction [START_REF] Chevalier | Modélisation des Conditions d'Alimentation dans les Contacts Elastohydrodynamiques Ponctuels[END_REF] to calculate the hexadecane film thickness.

Results and Discussion

Effect of Additives on Viscosity

The addition of very small amounts of polymer to hexadecane did not have a significant influence on the measured viscosity as presented in Table 2. In fact, the maximum viscosity increase was < 10%. This was to be expected, since the concentration is also at the lower end of the range reported for previous PFM investigations.

Friction Behavior (MTM)

The efficacy of the developed PFMs was examined in MTM experiments by measuring their friction behavior and plotting the coefficient of traction (COT) against entrainment speed. A comparison of all synthesized PFMs as well as results for pure hexadecane and the GMO solution is shown in Fig. 3a. When the entrainment speed is higher than 1000 mms -1 , all the measurements overlap at very low friction values, corresponding to the onset of hydrodynamic lubrication. The results for the decreasing speed ramps are omitted for clarity, since no indication of hysteresis was observed.

In the mixed/boundary regime the results fall into three categories: (a) Pure hexadecane shows extremely high friction, reaching 0.3 with a large scatter, (b) most of the polymers appear to be as effective as GMO, with a maximum friction coefficient of about 0.17, and (c) PFM-B, which exhibits an exceptionally low friction coefficient (~ 0.06) throughout the measured speed range of 1 to 100 mm s -1 , resembling the previously observed friction behavior for "covalently grafted" poly(dodecyl methacrylate) brushes in oil [START_REF] Bielecki | Polymer-brush lubrication in oil: sliding beyond the stribeck curve[END_REF].

To gain a better understanding of the efficacy of PFM B, similar MTM experiments were performed in different base oils: hexadecane, PAO2 and PAO6. The results are plotted in Fig. 3b, where the viscosity of the base oil was factored into the x-axis. PFM-B consistently shows greater friction reduction, especially in the boundary regime, compared to GMO. Hardly any influence of the base oil viscosity was detected in the boundary regime, confirming that a surface effect was being measured. Finally, the low-friction behavior of PFM B can be further examined by examining Stribeck curves that were obtained upon increasing normal load, as shown in Fig. 3c. No significant differences are seen here, even though the maximum contact pressure reaches 960 MPa.

Existence of an Adsorbed Film Under Unperturbed Conditions (QCM-D)

Film formation by PFM B was examined using the quartzcrystal microbalance with dissipation (QCM-D). In Fig. 4 a set of exemplary raw-data graphs is depicted. The measurements are separated into three phases: the first approximately 25 min consists of a constant flow of hexadecane, to obtain a baseline, after which the lubricant solutions are added and reach the sensor cells. After an additional roughly 20 min, the cells are purged with pure hexadecane for an additional 20 min. Only the central three frequencies are shown and later analyzed, since the higher-and lower-order overtones displayed a poor signal-to-noise ratio. The rawdata graph for PFM E is barely distinguishable from that of PFM D shown in Fig. 4d, and can be found in the Supporting Information.

In Fig. 4e-depicting the reference friction modifier GMO -a constant instrumental drift for the ∆F n /n signal is clearly visible. This is observed in all measurements (with slightly different magnitudes and prefixes), but is best visible here because of the lower scale of the y-axis. Keeping this in mind one sees that the frequency-shift and dissipation signals do return to pre-adsorption values after rinsing, which indicates a dynamic equilibrium and thus complete detachment of the film upon rinsing. All polymer-containing lubricant formulations, on the other hand, show a residual change in ∆F n /n, i.e. the film is bound strongly enough to be irreversibly adsorbed.

For PFM A, significant mass is adsorbed irreversibly, i.e. remains upon rinsing. The decrease in dissipation upon rinsing indicates, however, that a rearrangement of the film occurred. PFM B has a visibly faster adsorption rate than the other polymers, and the thick film resulting after a few minutes shows little sign of rearrangement upon rinsing. Figure 4c highlights the extremely slow adsorption kinetics of PFM C, which can be attributed to its high molecular weight. No decrease in dissipation again indicates no film rearrangement. PFM D (as well as E shown in Figure S15) resembles PFM A in its trends, but the absolute values for frequency and dissipation shifts are approximately a factor of 2 higher. Finally, a reference measurement with the oleophilic chain only (the precursor molecule to PFMs A and B) shown in Fig. 4f provides additional insight. There is significant, but slow adsorption, and the adsorbed films show rearrangement upon rinsing. This can be rationalized by the fact that the methacrylate unit of the p12MA chain is inherently polar, and therefore there will be a tendency for the molecule to adsorb to the oxide surface when the alternative is the very non-polar hexadecane. The overall polarity of the molecule is also an explanation for the different behavior of PFMs B and C compared to the others: the percentage of functional, polar groups is, at > 30%, very high.

The irreversible-mass-adsorption results are quantified in Fig. 5. As expected from the tribological results, the lubricant containing PFM B exhibits significantly different behavior compared to the others. The irreversibly adsorbed masses (i.e. after rinsing) are shown on the left axis, with the Sauerbrey assumption of a rigid, laterally homogeneous film (see also Supporting Information).

The conversion into film thickness shown on the right axis assumes a density of 0.93 g cm -3 (p12MA in bulk) for the polymer and incorporated solvent. For PFM B in hexadecane, the resulting thickness is 16.4 ± 0.7 nm, the highest of all samples measured. Assuming an all-trans zigzag conformation of the backbone chain, one would expect between 10.5 nm (for the oleophilic block only) and 19.5 nm for the entire polymer.

Despite having the highest molecular weight and a high degree of anchor functionalization, PFM C adsorbs to a lesser extent than three of the other block copolymers. This is likely due to its large molecular size, which leads to a blocking of potential surface adsorption sites. GMO in hexadecane shows an equilibrium thickness of 1.3 nm (but a negligible irreversibly adsorbed amount), which corresponds to what has been reported using other techniques [START_REF] Crespo | Methodology to characterize rheology, surface forces and friction of confined liquids at the molecular scale using the ATLAS apparatus[END_REF], supporting the validity of our experimental conditions and modeling used for the determination of film thickness.

These estimated thicknesses here are mainly for comparison, and are to be considered as approximations, especially since the Sauerbrey equation assumes only a solid adsorbed slab of material. The layer whose thickness we are measuring also incorporates an unknown amount of hexadecane as solvent, some of which may be partially protruding from the polymer layer. Finally, the polydispersity of the polymer means that a fraction of longer chains is protruding from the surface, leading to an overestimation of the adsorbed Nevertheless we are within a thickness range consistent with the p12MA chains being upright in a brush-like configuration, the space between them being filled with solvent (hexadecane) molecules. Potentially, some of the adjacent anchoring groups are also constituting part of the brushforming chains.

The deduced thicknesses for all other PFMs are much lower, indicating unoriented, "mushroom" monolayer adsorption and neither brush nor multilayer formation. Additional ex situ ellipsometry measurements of the additives adsorbed on Cr surfaces from hexadecane yielded drythickness values corresponding to a packing density of ≈0.2 chains.nm -2 for PFMs A and B, which would be consistent with the formation of a polymer brush (see Supporting Information).

Correlation Between the Presence of an Adsorbed Film and Low Friction (IRIS)

In order to confirm the role of the adsorbed film on the low friction behavior in the mixed/boundary lubrication regimes, solutions of PFMs A, B and C in hexadecane were investigated with IRIS. The results of the measurements, in which film thickness and friction coefficient are measured simultaneously, are summarized in Fig. 6. For all polymers, the film thickness was large compared to that calculated for hexadecane, especially at low entrainment velocity, indicating that hydrodynamic effects alone could not explain the film-formation mechanisms. Contact visualization, during and after friction experiments, showed that a boundary film was adsorbed on the surfaces. This was also confirmed by the shape of the meniscus in the outlet zone at low entrainment velocity, a signature of a modification of surface properties. The thickness and heterogeneity of the adsorbed film and its capacity to withstand shear were dependent on the polymer architecture (see Figures S19, S20 andS21).

The friction measurement for PFM A shows significant hysteresis for entrainment velocities larger than 20 mm/s. This hysteresis was concomitant with that seen in the film evolution. The point of highest measured friction coincides with a visible onset of wear of the chromium coating of the disk (see also Figure S19). The measured film thickness is only approaching the regime expected for hexadecane at high entrainment speeds. In the lower-speed range, however, a speed-independent film in the range of 7 nm was visible, which again was consistent with both the post-friction adsorbed film measurement and the QCM results.

PFM B shows the lowest friction coefficient, consistent with the MTM measurements, despite the different surface roughness and substrate chemistry in the IRIS measurements. Negligible hysteresis was observed in friction and film thickness, highlighting the robustness of the adsorbed polymer film. The low friction coincided with the presence of a measured adsorbed film in the range of 20 nm. This corresponds reasonably well with that measured in QCM, keeping in mind that we expect an adsorbed film on each surface that is under significant compression (P av = 212 MPa). The film distribution was homogeneous, uniformly covering the surface, regardless of the entrainment velocity, confirming the strong anchoring of the polymers on metallic surfaces and the absence of contact bridging.

PFM C exhibited a continuous increase in measured film thickness during the IRIS experiment. At the end of the measurements, the film was patchy and thickness increased to 100 nm (Figure S21) compared to the thickness of 6 nm measured at the beginning of the experiment. The initially measured 6 nm thickness was consistent with the thickness derived from QCM-D experiments, while the 100 nm thickness measured at the end of the IRIS measurement is comparable with the large PFM C molecule in a brush configuration. This increase in film thickness was not observed during the initial pure rolling step at constant velocity, indicating that shear in the contact might be favoring the formation of the adsorbed film. A possible interpretation is that the shearing at the inlet zone of the contact and/or in the high-pressure contact zone allows for re-arrangements of the polymer molecules and a densification of the formed film. The formation of multilayers of polymer aggregates could also be a reason of the thick adsorbed film. The friction trends show a hysteresis, where the largest difference between decreasing and increasing speed is at 100 mm/sthe same speed at which the film-thickness measurements start to show large deviations. The absolute friction values in the final measurement stages are in a similar range to those measured with MTM. This seems to confirm the existence of a run-in phase in the film formation/friction evolution.

Conclusions

A series of polymeric friction modifiers (PFM) was synthesized with a range of precisely chosen structures and a specific chemistry. The chosen synthesis route allowed for the decoupling of effects due to polymer structure and anchoring chemistry (the latter being the topic of a subsequent study). Additionally, it opened the route for novel anchoring concepts to be explored in the field of oil-based polymeric friction modifiers.

A combination of a structure with an unusually large nitrodopamine anchoring block and moderate molecular weight (PFM B) showed unparalleled friction-reduction performance in rolling-sliding measurements, while other structures (some resembling the architecture of the published state-of-the-art, PFM A) showed a smaller effectcomparable to that of a reference organic friction modifier, glycerol monooleate.

In QCM-D measurements, all polymers adsorbed irreversibly onto the iron oxide surfaces, while glycerol monooleate was shown to adsorb reversibly. The film formed from the best-performing PFM (B) showed the highest adsorbed mass. The derived thickness of approximately 17 nm is comparable to the polymer size, implying a brush-like structure, firmly anchored to the surface by a substantial portion of the block of nitrodopamine groups.

IRIS measurements indicate various reasons for the less effective friction-reduction behavior of some of the PFMs. For PFM B, a uniformly adsorbed film was measured that was of comparable thickness to that measured by QCM-D, and it was stable under the applied contact pressure and shear conditions, resulting in a drastic friction reduction in the boundary regime.

Thus, it appears that the use of a block of nitrodopamine anchors is a very promising approach to anchoring blocks of brush-forming chains on ferrous surfaces in oil, and that the architecture of the polymer plays an important role in its effectiveness as a boundary lubricant. Overall molecular weight and relative sizes of anchoring and brush-forming blocks appear to be crucial parameters.

Fig. 1

 1 Fig. 1 Schematic depiction of the polymeric friction modifiers synthesized. a Graft copolymer and b block copolymer. c and d Hypothesized attachment configurations

Fig. 2

 2 Fig. 2 Synthesis route of the p12MA-b-pNDAcrAm PFMs investigated. a Polymerization of the oleophilic block. b Functionalizable blockcopolymer synthesis. c Post-polymerization modification reaction

Fig. 3 a

 3 Fig. 3 a MTM results for the investigated PFMs. b Performance assessment of PFM B in different base oils at 30 °C. c Load-dependent measurements with 0.5 wt% PFM B in hexadecane

Fig. 4 Fig. 5

 45 Fig. 4 Raw data from QCM-D measurements (a-d) PFMs A to D, respectively, e GMO, f p12MA

Fig. 6

 6 Fig. 6 IRIS measurement results. The first and last measurement steps are indicated with arrows, and the dotted lines indicate the chronological evolution. a-c PFM A-C, respectively. The straight dotted line is the expected hydrodynamic film thickness of pure hexadecane (Moes-Venner [41])

Table 1

 1 Detailed size descriptions of the investigated PFMsThe degrees of polymerization (DP) are derived from NMR-based conversion measurements, as described in the Supporting Information. Average molecular weight (Mn) and the ratio of 12MA to NDAcrAm units are derived from the DP directly

	Name	PFM A	PFM B	PFM C	PFM D	PFM E
	d.p. 12MA m	42	42	375	375	375
	d.p. NDAcrAm n	8	36	281	19	5
	Mn (kDa)	13	20	162	100	97
	Functionalization (%)	10	41	37	4	1
	Schematic representation

Table 2

 2 Measured kinetic viscosity in a 0.5 wt% solution in hexadecane

	Additive	PFM A	PFM B	PFM C	PFM D	PFM E	GMO	w/o
	Dynamic viscosity	2.993 ± 0.013 3.029 ± 0.011 3.025 ± 0.017 3.241 ± 0.013 3.063 ± 0.016 2.947 ± 0.014 2.951 ± 0.016
	(mPa s)

Supplementary Information

The online version contains supplementary material available at https:// doi. org/ 10. 1007/ s11249-021-01496-w.

Authors' Contributions All authors involved at all stages.

Funding Open Access funding provided by ETH Zurich. N/A.

Declarations

Conflict of interest Patent filed on similar topic.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http:// creat iveco mmons. org/ licen ses/ by/4. 0/.

Authors and Affiliations

Tobias A. Gmür 1 • Joydeb Mandal 1,2 • Juliette Cayer-Barrioz 3 • Nicholas D. Spencer 1