Girijanandan Nucha

Georges-Pierre Bonneau

Stefanie Hahmann

Vijay Natarajan

Computing Contour Trees for 2D Piecewise Polynomial Functions

Keywords: (according to ACM CCS): I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling-Geometric algorithms, languages, and systems

Contour trees are extensively used in scalar field analysis. The contour tree is a data structure that tracks the evolution of level set topology in a scalar field. Scalar fields are typically available as samples at vertices of a mesh and are linearly interpolated within each cell of the mesh. A more suitable way of representing scalar fields, especially when a smoother function needs to be modeled, is via higher order interpolants. We propose an algorithm to compute the contour tree for such functions. The algorithm computes a local structure by connecting critical points using a numerically stable monotone path tracing procedure. Such structures are computed for each cell and are stitched together to obtain the contour tree of the function. The algorithm is scalable to higher degree interpolants whereas previous methods were restricted to quadratic or linear interpolants. The algorithm is intrinsically parallelizable and has potential applications to isosurface extraction.

Introduction

Scientists and engineers are increasingly using higher order FEM simulations. Consider, as an example, the hp-adaptive variant [START_REF] Babuška | The h, p and h-p version of the finite element method: Basis theory and applications[END_REF] of finite element methods for which Nektar++ [CMC * 15], Concepts [Sch], and Hermes [Sol] are three among many existing open source software packages and libraries. These methods rely on piecewise polynomial approximations, using elements (possibly curvilinear) of variable size h and polynomials of order p within an element. Higher order elements are suitable for efficient parallel implementations and allow for higher numerical accuracy and convergence than linear basis functions by either adaptively reducing the element's size h, by increasing the polynomial order p, or by combining both approaches. For an equivalent number of degrees of freedom, one can obtain the same level of accuracy with fewer elements. In this paper, we study piecewise higher order real-valued functions defined on planar or curvilinear elements representing 2-manifold geometries.

Motivation and related work. Whereas higher order discretizations have become a widely accepted tool for many applications, visualization techniques have to adapt and better exploit the nonlinear and often polynomial nature of the data sets. Standard visualization techniques such as contouring, volume rendering, and topology-based methods assume the basis functions to be linear. These methods first create compatible linear approximations of the geometry as well as of the higher order data generally through adaptive tessellation [KT03,RCMG07] in order to increase numerical accuracy and topological fidelity. Since the basis functions used to represent geometry and the attribute field functions are not neces- sarily the same nor of same polynomial order, accurate tessellation is a challenging task [SBM * 06]. Further, the use of high sampling density increases memory usage and may still introduce additional error.

Many visualization techniques for higher order scalar fields have begun to emerge in recent years [CSP01,WCG * 03,NK06,SBM * 06, MNKW07, POS * 11, NLKH12]. Whereas these contouring, particle tracking, and rendering techniques for higher order data seek for improving numerical accuracy of the visualization, topological fidelity is equally important. Indeed, topology-based methods are important for analysis and visualization of scalar data, since they provide abstract representations of key features in the data.

Our focus is on the computation of contour trees. The contour tree captures significant topological features of a data set by computing the nested relationships between the connected components of level sets in a scalar field, as illustrated in Figure 1. Contour trees are widely applied in the context of volume visualization -for efficient computation of isosurfaces [vKvOB * 97], transfer function design [FTAT00, TTF04, WDC * 07, ZT09, DN12], and for effective and flexible exploration of isosurfaces [CSvdP10]. The application of contour trees to volume data analysis such as feature extraction and tracking [BWT * 11, WBD * 11, DNN13], symmetry and similarity detection [TN11, SSW14] is also clearly demonstrated.

Many efficient algorithms have been proposed for computing the contour tree for two-and three-dimensional scalar fields [dBvK97, vKvOB * 97, TV98, CSA03, CLLR05] and considerable efforts have been undertaken to develop parallel implementations [PCM04, MDN12, LPG * 14, AN15, CWSA16, GFJT16]. However, these methods typically suppose the data being sampled at the mesh/grid vertices and varying linearly along the edges. In this paper, we tackle the problem of computing contour trees specifically dedicated to higher order interpolants without falling back to linear approximations of the data. * 09] described a method to compute the contour tree for quadratic interpolants. They proceed by first tessellating a triangle in the input mesh into monotone triangles and then apply classical methods for contour tree computation. This method does however not scale to higher order elements because it requires a case analysis for computing the tessellation. This case analysis is cumbersome already for quadratic interpolants. Pascucci and Cole-McLaughlin [PCM04] and Acharya and Natarajan [START_REF] Acharya | A parallel and memory efficient algorithm for constructing the contour tree[END_REF] describe parallel algorithms to compute the contour tree for piecewise trilinear interpolants over a 3D grid. Minima and maxima are restricted to vertices of the grid and there are only four possible join/split tree configurations. Both methods compute the join and split trees for a single grid cell by looking up a case table and stitch them together. Carr and Snoeyink [START_REF] Carr | Representing interpolant topology for contour tree computation[END_REF] propose an abstract framework for handling interpolants of arbitrary order and design a finite state automaton for computing the contour tree. This framework was employed either explicitly or implicitly for computing the contour tree in parallel for both trilinear interpolants [PCM04, AN15] and for piecewise linear interpolants [MDN12,LPG * 14]. These algorithms used combinatorial routines to compute the tree corresponding to an individual cell. Such an approach is not feasible for higher order interpolants. Our method may be considered as the first concrete realization of this abstract framework for higher order interpolants. Summary of results. Our algorithm has two phases: local and global. The local phase computes the contour tree restricted to a single triangle by exploiting the monotone connectivity of critical points within an element. Inspired by the approach from Chiang et al. [CLLR05], we compute monotone paths on the polynomial function to connect the critical points inside an element. This leads to an advantageous dimension reduction of all involved subproblems because the restriction of a bivariate polynomial function to a specific direction reduces to a univariate polynomial. The global phase stitches together the local trees. This algorithm may be considered as a hybrid approach between the monotone path tracing algorithm of Chiang et al. [CLLR05] and the two-pass union-find based algorithm of Carr et al. [CSA03]. Both algorithms have to be suitably extended to be made applicable to higher order polynomials. Our algorithm combines the advantages of both approaches. The algorithm of Chiang et al. is output sensitive and does not require processing all sample points. It is appropriate for our local tree computation because we enjoy the benefit of sampling the polynomial only along the monotone paths as opposed to sampling uniformly over all triangles. The global stitching procedure is a combinatorial and computationally efficient algorithm.

Dillard et al. [DNW

Our algorithm is designed to work for any higher order interpolant. We demonstrate the effectiveness of our approach with an implementation for piecewise quadratic and piecewise cubic polynomials. We also performed experiments on real-world scientific data obtained using COMSOL [Com11]. Figure 2: Join tree (a) and split tree (b) of the function described in Figure 1. The contour tree is the union of the join and split trees.

Background

Let M be a d-manifold with or without boundary. Let A level set is the preimage f -1 (c) of a real value c, which is called an isovalue. The connected components in a level set are called contours. The quotient space of M by the equivalence relation "a relates to b if a and b lie within the same contour" is a graph called the Reeb graph [Ree46]. If the domain M is simply connected (genus 0) then the Reeb graph is acyclic and called the contour tree. Nodes in a contour tree correspond to critical points of f . Maxima and minima are leaves of the tree, while saddles are interior nodes of degree 3. In order to explain the structure of the contour tree, it is convenient to use the metaphor of contours 'appearing', 'disappearing' or 'merging'. A contour appears when the isovalue increases past the critical value of a minimum. A contour disappears when the isovalue increases past the critical value of a maximum. When the isovalue increases past the critical value of a saddle, either one contour splits into two or two contours merge into one. Figure 1 shows a 2D function and the corresponding contour tree. Nodes colored red, blue, and green correspond to maxima, minima, and saddles, respectively. The contour tree provides the user with direct insight into the topology of all level sets and reduces the time required to understand the topological structure of the data. The join tree and split tree are defined in a manner analogous to the contour tree, by tracking connected components of the sub-level sets (preimage of f -1 (-∞, c]) and the super-level sets (preimage of f -1 [c, +∞)), respectively. Figure 2 shows the join and split tree of the scalar function shown in Figure 1. They are useful intermediate structures for computing the contour tree as explained in Section 3.2 and Section 3.6.

f : M -→ R be a smooth (C ∞ differentiable) real function. A point p ∈ M is called a critical point if ∇ f (p) = 0. A critical

Algorithm

We now describe an algorithm for computing the contour tree of a 2D piecewise polynomial function.

Input

The domain is represented by a triangle mesh of genus 0. We require the input data to be continuous across the domain so that the level sets are also continuous, see Figure 3. The polynomial interpolant is specified by a set of samples in each triangle. We use the word patch to refer to a triangle together with the polynomial interpolant as specified by the set of samples. A sample is specified by two parameter values for the location and one function value. The number of samples depends on the degree of the polynomial function. For example, a polynomial of maximal degree 2 is defined by 6 samples, whereas a maximal degree-3 polynomial requires 10 samples. If required, the monomial coefficients of the polynomial may be computed from the samples by solving a linear system. Typically, three samples are located at vertices of the triangle. The location of the remaining samples depends on the particular finite element implementation. Figure 3b shows a quadratic polynomial defined by six sample points (black). For comparison, the piecewise linear interpolant defined by the same set of six sample points is shown in Figure 3a. Figure 3d shows two quadratic patches defined by 6 sample points each. The functions are continuous across the common boundary as the continuous isolines indicate. The geometry of the element may also be modeled as a polynomial function, possibly of different order than the attribute data. In this case, a second set of samples is required, consisting of two parameter values and a 3D position per sample.

Overview

The algorithm proceeds by building the local join and split tree of a patch independent of other patches. A local join tree captures the connectivity of sub-level sets of a patch, where topology change events are associated with local minima and join saddles. Similarly, the local split tree captures the connectivity of super-level sets of a patch. Topology change events here are associated with local maxima and split saddles. The local join trees of adjacent patches are stitched together to obtain the global join tree of the input scalar field. Similarly, the local split trees are stitched together into the global split tree. Finally, the global join and split trees are merged using an efficient tree merge procedure to obtain the desired contour tree of the input scalar field. Essentially, the algorithm consists of four steps:

1. Compute critical points for each patch. 2. Construct local join tree and split tree for each patch.

3. Stitch local join trees together to obtain the global join tree. Stitch local split trees to obtain the global split tree. 4. Merge the global split and join trees together to obtain the contour tree.

Prior to processing a patch, we apply a rigid body transformation that moves the triangle to the XY-plane. This transformation simplifies future numerical computations without affecting the topology of the level sets and hence the local join and split trees.

Critical points of a patch

The critical points of a 2D polynomial are computed by solving for the roots of a polynomial system given by the two partial derivatives. Analytic methods are not available to compute roots of such a polynomial system, particularly for higher degrees. We use PHCpack [Ver11] for computing the roots of the polynomial system. PHCpack uses homotopy continuation methods and provides exact roots whenever they are computable and numerically approximate solutions when the root finding is intractable. The critical points lie on the XY-plane. The method reports points lying in the interior of the triangle. Line-critical points, defined as critical points

Local join and split trees

The critical points computed in the previous step together with the triangle vertices constitute the potential nodes of the local join and split tree of a patch. We next compute the arcs of these local trees. Below, we describe the algorithm for computing the local join tree (Algorithm 1). The local split tree is computed using a similar procedure. The algorithm assumes that the polynomial f defined on a triangle together with the set of its critical points is available as input.

Most methods to compute the join tree for piecewise linear functions explicitly track the connected components of sub-level sets during a sweep over the domain and process all vertices of the input mesh [CSA03, DNN13]. This approach does not extend well to higher order interpolants due to two reasons. First, the critical points of a piecewise linear function are necessarily located at vertices of the input mesh and hence it is sufficient to process vertices of the mesh. However, the critical points of a higher order polynomial interpolant may lie in the interior of the triangle. Second, computing the level sets for higher order interpolants is challenging both in terms of the computational cost and numerical accuracy. We instead employ an approach that directly computes the downward arcs incident on a join tree node. The potential nodes of the join tree are processed in increasing order of function value and the downward arcs incident on it are identified by following monotone descending paths from the corresponding critical point / triangle vertex. A monotone descending path (MDP) is a path in the patch along which the value of f decreases monotonically. The path originates at a critical point / triangle vertex and terminates at a different critical point / triangle vertex or merges into another descending path. The MDP terminates in the sub-level set component that contains its origin. Hence, the MDP helps determine the downward arcs from the corresponding join tree node.

The critical points and triangle vertices are processed in increasing order of value of f . We maintain a forest of join trees containing all critical points and vertices processed so far. When the next critical point or vertex c is processed, the forest is updated to include c. The local neighborhood of c is classified into regions where f assumes values lower or higher than f (c). This classification determines the number of MDPs traces from c. If an MDP terminates at a critical point c then we insert an arc from c to the root of the tree containing c . Alternatively, if the MDP intersects a previously computed MDP, say originating at c , then we insert an arc from c to the root of the tree containing c . The forest of trees is stored as a union find data structure [START_REF] Cormen | Introduction to Algorithms[END_REF]. After all critical points and vertices are processed, the forest consists of a single tree rooted at the global maximum of the patch. This tree is the local join tree of the patch.

Monotone path tracing. Computing the exact geometry of a monotone path is computationally challenging. However, it is sufficient for our purposes to compute sample points on the path. We represent an MDP as a piecewise linear curve and store it as a finite collection of points [x 0 , x 1 , . . . , x k ]. Here, x 0 is the source critical point, x k is the terminal point, and f (x i+1 ) < f (x i ). We now describe how an MDP is traced. Ensuring numerical accuracy while reducing computational costs makes this a challenging problem. In particular, (a) appropriate number of MDPs needs to be traced from a critical point / triangle vertex, (b) the tracing procedure should ensure the monotone property, and (c) the terminal point should be recognized correctly.

We reduce all numerical computations to root finding on univariate polynomials, thereby simplifying the computation. We use GNU Scientific Library for processing the univariate polynomials [Gal09]. To facilitate the identification of the number of MDPs originating at a critical point or vertex, we first compute disjoint axis-aligned bounding boxes for all of them. Chattopadhyay et al. [START_REF] Chattopadhyay | Certified computation of planar morse-smale complexes[END_REF] show that these boxes always exist. In practice, we compute boxes with diagonal length smaller than d min , the minimum distance between critical points / triangle vertices. Assuming that f is a Morse function, the local neighborhood may be partitioned into sectors with values of f alternating between higher and lower than f (c). We compute the restriction of f to the boundary of the bounding box R c . This restriction is a univariate piecewise polynomial function f R c . Roots of f R cf (c) partition the boundary of R c into segments. If there are more than four roots then we compute a smaller bounding box by halving the diagonal length. Choose a point s within each segment and initialize an MDP negative gradient direction at s. This restriction is also a univariate polynomial, say f s . The minimum of f s closest to s is inserted as the next point x 2 of the MDP. This process is repeated to compute subsequent points x i on the MDP. This iterative procedure terminates either when x i lies in the interior of the bounding box of a critical point / triangle vertex c or when x i-1 x i intersects a previously computed MDP.

[x 0 = c, x 1 = s] if f (s) < f (c). Next,
Example. The steepest descent direction on the boundary is computed at x 2 , shown using an arrow glyph in Figure 4(c). Next, the univariate polynomial along the blue ray is computed followed by locating the closest minimum r, see Figure 4(d). The tracing stops because r lies within the bounding box of c 2 . The resulting path is p =

[x 0 = c 1 , x 1 = s, x 2 , x 3 = c 2 ].

Global join and split trees

The local join trees are stitched together resulting in the global join tree. Similarly the global split tree is computed by stitching the local split trees. The stitching procedure is similar to the one proposed by Acharya and Natarajan [START_REF] Acharya | A parallel and memory efficient algorithm for constructing the contour tree[END_REF]. We describe it here for completeness, see also Algorithm STITCHJOINTREES. The sorted list of nodes of two input join trees are merged into a single sorted list. Duplicate nodes from the boundary of the two corresponding sub-domains lie adjacent to each other in the sorted list. An edge is inserted between every pair of duplicate nodes, resulting in a single connected graph that may contain cycles. The stitched join tree is computed by sweeping the graph in increasing order of function values and tracking connected components of subgraphs using a union-find data structure. Repeated application of the stitching process on all local join trees and on intermediate stitched trees results in the global join tree.

Contour tree

The global join and split trees are merged resulting in the global contour tree [CSA03]. This merge step is also described in previous work. For completeness, the merging procedure is described in Algorithm MERGEJOINANDSPLITTREE. The algorithm maintains a set L of leaf nodes in the join and split trees and processes them in sequence. If the current leaf node under consideration, say l, is an unprocessed non-root node then the edge between l and its parent from the appropriate tree is added to the resulting contour tree. After processing, l is deleted both from the list L and the join/split tree that contained it. If this deletion results in the parent of l to become a leaf node , then that node is inserted into L.

Degeneracies

A patch that contains at least one non-isolated critical point is said to be degenerate. Figure 5(a) shows a degenerate function defined on a triangle. All points on the line c 1 c 2 are local maxima. The function in this case is not Morse and hence the above algorithm does not apply. In particular, individual critical points cannot be isolated and the MDP tracing fails due to the presence of zero gradient regions. We compute the local join and split tree for the degenerate patch by subdividing it into smaller triangles and assuming linear interpolation within each smaller triangle. The degenerate patch is processed as follows. First, compute the line-critical points of the patch and insert them as vertices. Next, compute a triangulation of the set of triangle vertices and the newly inserted vertices. This triangulation subdivides the interior of the degenerate patch into smaller triangles. For example, Figure 5

Correctness

We claim that the tree computed by the above algorithm is the contour tree of the piecewise polynomial input. If the MDPs are computed accurately from all critical points of a patch then Algorithm 1 indeed computes the local join tree. This follows from the result of Chiang et al. [CLLR05]. The algorithm traces all required MDPs from a critical point / triangle vertex as shown in Lemma 3 in the appendix. Degenerate patches are also processed correctly.

If a patch contains a non-isolated critical point then the degenerate region extends to the boundary as shown in the appendix, see Lemma 1 and 2. If the degenerate region is a curve then the corresponding line-critical points are included, else the entire patch is flat. In either case, all critical points are included into the join tree and the degenerate patch is processed correctly. c n 2 p ). Let n t denote the number of triangles in the input. Stitching the lo-cal join trees requiresO(n t n c ) Find and Union calls, which takes O(n t n c α(n t n c )) time. Computing the global split tree also takes the same time. The global join and split tree can be merged in linear time on the total number critical points, which is O(n t n c ). For a degree d polynomial, n c ≤ d -1. So, the total time to compute the contour tree is dominated by the MDP tracing, which is O(n t d 2 n 2 p ). Input: Join trees JT 1 and JT 2 for two sub-domains that have a common boundary Input: List of nodes of the two trees N 1 and N 2 sorted in ascending order of function value Output:

Analysis

Stitched join tree JT 1 Initialize JT ←-JT 1 ∪ JT 2 2 UF ←-/ 0 3 N ←-Merge(N 1 , N 2 ) for (i ←-1to|N| -1) do 4 if v i and v i+1 are redundant nodes on the common boundary then 5 NewSet(v i ,UF) 6 NewSet(v i+1 ,UF) 7 Union(v i , v i+1 ,UF) making v i+1 as the head 8 JT.v i .Parent ←-v i+1 9 Add v i to JT.v i+1 .ChildrenList

Experimental Results

We now present results of computational experiments on 2D quadratic and cubic polynomials. The algorithm is implemented in C++. The open source C++ library Eigen [GJ * 10] is used for finding the solution of a system of linear equations, the GNU Scientific Library [Gal09] for finding the roots of a univariate polynomial, and PHCpack [Ver11] for finding roots of a polynomial system. The contour tree computed by the algorithm contains all vertices of the input mesh as nodes. Hence, the output is the so-called augmented contour tree. In our implementation, the degree-2 nodes are pruned away. They may be retained if required.

Piecewise quadratic input. The thermal conductor dataset represents the temperature distribution at the surface of an electronic component computed by solving a multi-physics simulation using COMSOL [Com11]. The temperature field is a polynomial of maximal degree 2 within each triangle. The six samples are located at the triangle vertices and at the mid-point of the edges, as shown in Figure 3b. For this dataset, the geometry of the elements is also modeled as a quadratic polynomial that accurately fits the curved surface. Figure 6a-6c shows the temperature field, its critical points The contour tree contains 530 nodes, several of them corresponding to small-sized topological features. Given a persistence threshold the contour tree may be simplified by iteratively removing arcs incident on leaf nodes [CSvdP10]. Figure 6d shows the contour tree simplified using a persistence threshold of 0.1%. The temperature field contains multiple degeneracies, particularly on the top plate as shown in Figure 7. Our algorithm handles all degenerate patches gracefully and computes the contour tree. The simplified tree shows the two significant maxima located at the center of the two legs surrounded by a few low persistence maxima. Note that the tree contains two similar subtrees as expected. The subtrees correspond to the symmetric legs of the conductor. It took approximately 15 minutes to compute the contour tree for this data set (8598 vertices, 4298 triangles). Algorithmic and code optimizations may result in significant reduction in running times. For example, several steps of the algorithm can be parallelized. We plan to do this in future.

Figure 8 compares the contour tree of a piecewise quadratic function with the contour tree of piecewise linear (PL) approximations. The PL approximations are computed by applying a uniform refinement on the input triangulation and by linearly interpolating the polynomials on the refined triangles. There are large differences between the contours of the original data and those of the PL approximations even after a high level of refinement. A close-up view shows how the topology of the contours, and thus the contour trees, differ. The visual comparison indicates that a higher order interpolant can capture all topological features even if the surface is discretized using fewer number of triangles. The PL approximation is not able to accurately capture the level set topology even with a 15-fold increase in number of triangles. The section of the contour tree shown in Figure 8(i) contains more number of maxima than Figure 8(j). However, these additional maxima are introduced due to flat regions and have zero persistence.

Piecewise cubic input. The heater dataset is a sum of Gaussian function sampled on the surface of a heater. Each triangle in the mesh representing the heater surface contains ten sample points. Three samples are located at the vertices, two within each edge subdividing it into equal sized segments and one at the barycenter. A polynomial of maximal degree 3 interpolates the ten samples. Figure 6e-6h shows the cubic function, its critical points together with a set of contours, the contour tree computed using our algorithm, and the contour tree simplified using a persistence threshold of 0.5%. Gradient computation and root finding are costlier for the cubic interpolant. However, the use of univariate polynomials to trace monotone paths and the use of bounding boxes helps resolve several numerical issues. This data again contains multiple degenerate patches. All degeneracies are gracefully handled.

Figure 9 compares the contour tree of the piecewise cubic function defined on the heater dataset with the contour tree of its PL approximations. The contours of the PL approximation is significantly different from that of the piecewise cubic function defined on an equal number of triangles. A 10-fold increase in number of triangles seems to be necessary to obtain similar contours.

Conclusions

We have described a simple algorithm for computing the contour tree of a 2D piecewise polynomial scalar field that is defined over a triangle mesh. The algorithm employs efficient numerical computations to trace monotone paths within each triangle. All other steps are combinatorial in nature. Experimental results show how the algorithm can efficiently capture topological features that are not easily identified using a linear approximation. With the increasing use of higher order element data in simulations, it is essential that the analysis and visualization techniques are also directly applied on the higher order elements. This is particularly true for topologybased visualization techniques, which aim to capture and represent key features in the data.

Appendix

We prove three lemmas that are required to show the correctness of the algorithm.

Lemma 1 If a bivariate polynomial function f is constant over a non-empty open subset Ω of R 2 , then f is constant over R 2 .

Proof Let x 0 ∈ Ω. The Taylor expansion of the polynomial function f at x 0 is

f (x) = f (x 0 ) + k=N ∑ |k|>0 ∂ k f (x 0 ) (x -x 0 ) k k! ,
where we use the multi-index notation, and N = (N 1 , N 2 ) is the degree of f . Since f is constant within a neighborhood of x 0 , we must have ∂ k f (x 0 ) = 0, ∀k. From the Taylor expansion of f , we conclude that f is constant over R 2 .

Lemma 2 If a bivariate polynomial function f is constant over a non-empty line segment I in R 2 , then f is constant over its supporting line l(I).

Proof Let x 0 and x 1 be two distinct points in I. Define a univariate polynomial g such that g(s) = f (x 0 + s(x 1 -x 0 )) for s ∈ R. The polynomial g is constant over a non-empty open interval. An analogous argument as in the proof of the previous lemma implies that g is constant over R. Therefore, f is constant over the line l(I).

Lemma 3 Let f be a bivariate polynomial Morse function and let c be a critical point of f . Algorithm 1 traces at least one monotone descending path from each connected component of the lower neighborhood N - c of c. Proof The bounding box is chosen such that no other critical point lies within it. First, assume that the bounding box R c is small enough that the level set f -1 (c) intersects the boundary of R c exactly zero times (for minima and maxima) or four times (for saddle critical points). In this case, Algorithm 1 clearly traces 0, 1, and 2 MDPs for minima, maxima, and saddle critical points, respectively. Further, the path is indeed an MDP because there exists a descending path from c to the point s on the boundary, namely the gradient descent path (see Figure 10

Figure 1 :

 1 Figure 1: (a) A 2D scalar field with two maxima (red) in the interior, two maxima on the boundary, one minimum (blue) in the interior, and three minima on the boundary. (b) Contour tree of the scalar field, whose nodes are exactly the critical points of the scalar field.

  c 2017 The Author(s) Computer Graphics Forum c 2017 The Eurographics Association and John Wiley & Sons Ltd. A u t h o r p r e p r i n t Nucha et al. / Computing Contour Trees for 2D Piecewise Polynomial Functions

Figure 3 :

 3 Figure 3: Linear and higher order interpolation over a triangle for a function sampled at multiple points (black). (a) Linear interpolation within each of the four triangles obtained by subdividing the input triangle. (b) Quadratic polynomial function interpolating the sample points. (c) Cubic polynomial function interpolating 10 sampling points. (d) Piecewise continuous quadratic polynomial sampled at 6 points each over two triangles. (e) Piecewise continuous cubic polynomial sampled at 10 points within each triangle. Isolines are continuous across common boundary.

  c 2017 The Author(s) Computer Graphics Forum c 2017 The Eurographics Association and John Wiley & Sons Ltd.

Figure 4 :

 4 Figure 4: Tracing a monotone descending path from c 1 . The steepest descent direction (blue) helps locate monotonic segments. If a path reaches the boundary, it is restricted to the boundary.

  compute the restriction of f to the ray along the c 2017 The Author(s) Computer Graphics Forum c 2017 The Eurographics Association and John Wiley & Sons Ltd.

  A u t h o r p r e p r i n t Nucha et al. / Computing Contour Trees for 2D Piecewise Polynomial Functions

  Figure 4 illustrates the tracing of an MDP p from a critical point c 1 in a triangle. All the critical points of the patch are shown in red. The bounding box is shown only for critical points c 1 and c 2 to reduce clutter. The direction of steepest descent is shown using the arrow glyph. The polynomial f defined on the triangle is restricted to a ray along the steepest descent (Figure 4(b), shown in blue). Let r be the closest minimum of the resulting univariate polynomial. In this case, the point r lies outside the boundary of the patch. The univariate polynomial decreases monotonically until r. So, the point of intersection of the ray with the triangle boundary is chosen as the next point, x 2 on the MDP. When an MDP reaches the triangle boundary, it is restricted to the boundary for simplicity.

  (b) shows the decomposition of the patch into three triangles. Assume linear interpolation within each triangle and compute the local join tree and local split tree of the patch using the sweep algorithm [CSA03]. Inserting the line-critical points ensures that the subsequent stitching step applies to all patches, degenerate or otherwise, without modification.

Figure 5 :

 5 Figure 5: (a) A degenerate patch. (b) Subdividing the patch into triangles after inserting all line-critical points. The local join tree and local split tree is computed by assuming piecewise linear interpolation within each smaller triangle.

5

  We now analyze the run time of the contour tree algorithm beginning with Algorithm 1. Let n c denote the number of critical points in the patch. Sorting the critical points takes O(n c log n c ) time. Assuming that the function is Morse, a constant number of MDPs are c 2017 The Author(s) Computer Graphics Forum c 2017 The Eurographics Association and John Wiley & Sons Ltd. A u t h o r p r e p r i n t Nucha et al. / Computing Contour Trees for 2D Piecewise Polynomial Functions Algorithm 1: BUILDLOCALJOINTREE Input: Polynomial function f defined on a triangle that lies on the XY plane Input: Set C of critical points and triangle vertices. Minimum distance, d min , between points in C. Output: Local join tree JT / * Let P denote the set of monotone descending paths(MDP). Each p ∈ P is of the form [x 0 , x 1 , . . . , x k ], where x i ∈ C. * / / * Let R c denote the bounding box of a point c ∈ C. * / / * Let S denote the set of starting points of monotone descending paths. These are points x 1 that lie on the bounding box of a point in C. * / / * Let UF denote a union-find data structure to store collection of points in C. Each set in UF is represented by the critical point with highest function value. * / 1 Initialize the node set of JT to C 2 Initialize UF ←-/ 0, P ←-/ 0 3 for each c ∈ C in ascending order of function value do 4 NewSet({c},UF) Compute an axis parallel bounding box, R c with c as center and diagonal length d min 6 Compute roots of f restricted to the boundary of R c 7 Compute the collection S of points s between pairs of adjacent roots on the boundary of R c that satisfy the condition f (s) < f (c) 8 for each s ∈ S do 9 Start a monotone descending path p, initialize it to [c] 10 Set x 1 ←s, i ←-0 11 repeat 12 Set i ←i + 1 13 Append x i to p 14 Compute f i , the restriction of f to the ray along the negative gradient of f at x i 15 Set x i+1 as the minimum of f i that is closest to x i 16 until x i+1 lies within R c for some c ∈ C Or the line segment x i x i+1 intersects a path p ∈ P; 17 if x i+1 lies within R c then 18 Append c to p 19 Add p to P 20 Add edge cc to JT 21 Union(c, c ,UF) 22 end 23 if x i x i+1 intersects a path p ∈ P at a point x then 24 Append x to p 25 if x is not a point in the representation of p then 26 Insert x into p at the appropriate location 27 end 28 Add p to P 29 Let c denote the source critical point for p 30 if c = Find(c ,UF) then 31 Add edge (c, Find(c ,UF)) to JT 32 Union(c, c ,UF) traced for each critical point resulting in O(n c ) Find and Union calls. This takes O(n c α(n c )) time. Let n p denote the maximum number of segments in an MDP. Checking for intersection with previously computed MDPs takes O(n 2 c n 2 p ) time and is the costliest step in the MDP tracing procedure. So, Algorithm 1 takes O(n 2

c

  2017 The Author(s) Computer Graphics Forum c 2017 The Eurographics Association and John Wiley & Sons Ltd. A u t h o r p r e p r i n t Nucha et al. / Computing Contour Trees for 2D Piecewise Polynomial Functions Algorithm 2: STITCHJOINTREES [AN15]

  child c j of v i ) do 12 if c j is present in UF then 13 if v i is present in UF then 14 NewSet(v i ,UF)15 end 16 Delete c j from JT.v i .ChildrenList 17 c ←-FIND(c j ,UF) 18 if v i = c then 19 JT.c .Parent ←v i 20 Add c to JT.v i .ChildrenList 21 Union(c , v i ,UF) ensuring v i as the head Stitched join tree JT

Algorithm 3 :

 3 MERGEJOINANDSPLITTREE [AN15] Input: Global join tree JT and split tree ST Output: Contour tree CT 1 L ←-Set of leaves in JT and ST 2 while L = φ do 3 if l is a leaf in JT or ST then 4 Process l and remove it from L 5 T = tree in which l is a leaf 6 while l = T.root and l is not processed do 7 n = l 8 l = parent vertex of l in T 9 end 10 Remove n from T and L 11 Add arc(n, l) to CT 12 if l is either a leaf in JT or ST then 13Add l to L with a set of contours, and the contour tree computed using the proposed algorithm. A topological feature is represented by a min-saddle or max-saddle arc / path in the contour tree. The size of a topological feature is measured using the notion of topological persistence [EH10], which is equal to the difference in function value at the pair of critical points.

Figure 7 :

 7 Figure 7: Top of the conductor contains multiple degeneracies. The algorithm identifies all the critical points and handles the degenerate patches gracefully.

Figure 6 :

 6 Figure 6: Contour trees for piecewise quadratic and cubic polynomials (a) Temperature distribution on the surface of a thermal conductor as a piecewise quadratic function. (b) Critical points and contour lines. (c) Contour tree consisting of 530 nodes. (d) Contour tree after simplification using a persistence threshold of 0.1% contains 67 nodes. (e) A cubic function defined on a heater geometry. (f) Critical points and contour lines. (g) Contour tree consisting of 268 nodes. (h) Contour tree with 178 nodes obtained after simplifying using a persistence threshold of 0.5%.

  c 2017 The Author(s) Computer Graphics Forum c 2017 The Eurographics Association and John Wiley & Sons Ltd.

  A u t h o r p r e p r i n t Nucha et al. / Computing Contour Trees for 2D Piecewise Polynomial Functions

Figure 10 :

 10 Figure 10: (a) Bounding box R c for a critical point c showing its neighborhood N c . (b) A box containing c, which is larger than the required bounding box.

  (a)).Let us now consider the case when the above assumption is not true. If c is a minimum or maximum and f -1 (c) intersects the boundary of R c then there exists another critical point within R c , a contradiction.If c is a saddle point, then a configuration as shown in Figure10(b) may arise. In this case, f R cf (c) will have more than four roots and the algorithm finds a smaller bounding box. [WBD * 11] WEBER G. H., BREMER P.-T., DAY M. S., BELL J. B., PASCUCCI V.: Feature tracking using reeb graphs. In Topological Methods in Data Analysis and Visualization: Theory, Algorithms, and Applications (2011), Pascucci V., Tricoche X., Hagen H., Tierny J., (Eds.), Springer Verlag, pp. 241-253. LBNL-4226E. 2 [WCG * 03] WILEY D. F., CHILDS H. R., GREGORSKI B. F., HAMANN B., JOY K. I.: Contouring curved quadratic elements. In VisSym (2003). 1 [WDC * 07] WEBER G. H., DILLARD S. E., CARR H., PASCUCCI V., HAMANN B.: Topology-controlled volume rendering. IEEE Transactions on Visualization and Computer Graphics 13, 2 (Mar. 2007), 330-341. 2 [ZT09] ZHOU J., TAKATSUKA M.: Automatic transfer function generation using contour tree controlled residue flow model and color harmonics. IEEE Transactions on Visualization and Computer Graphics 15, 6 (Nov. 2009), 1481-1488. 2 c 2017 The Author(s) Computer Graphics Forum c 2017 The Eurographics Association and John Wiley & Sons Ltd.

A

  u t h o r p r e p r i n t Nucha et al. / Computing Contour Trees for 2D Piecewise Polynomial Functions

Figure 8 :

 8 Figure 8: Visual comparison with piecewise linear (PL) approximations. (a) A PL approximation of the temperature field over the conductor. (f) Contour tree for the PL approximation. (b-d) Close up of region of thermal conductor showing critical points and contours for successive PL subdivisions of conductor containing 4298, 17192, and 68768 triangles, respectively. (g-i) Corresponding nodes and arcs in the contour tree. (e) Critical points and contour lines for piecewise quadratic function with 4298 triangles. (j) Nodes and arcs from contour tree of the piecewise quadratic function.

Figure 9 :

 9 Figure 9: Visual comparison with PL approximations. (a) Close up view of heater dataset. Critical points computed using a PL approximation on a mesh with 12438 triangles.(d) Corresponding contour tree containing 210 nodes. (b) PL approximation with 111942 triangles. (e) Corresponding contour tree with 208 critical points. (c) Close up of heater showing critical points computed using a piecewise cubic function with 12438 triangles. (f) Corresponding contour tree containing 212 critical points.

c 2017 The Author(s) Computer Graphics Forum c 2017 The Eurographics Association and John Wiley & Sons Ltd.

Acknowledgements

This research was partially funded by a grant from the Indo-French Centre for Applied Mathematics. The first author thanks Talha Bin Masood for active discussions and help with dataset preparation.


Patrick Cormier
email: cormier@sb-roscoff.fr

Cell Cycle New and Views Translation regulator ballet in meiotic spindle

Keywords: 4E-BP1, CDK1, mTOR, meiotic and mitotic spindle, mammalian oocyte

est destinée au dépôt

The fine spatial and temporal resolution of translation control can have a rapid and subtle effect on the microenvironment of the cell in comparison with transcriptional regulation. Mammalian oocyte represents a relevant model that allows addressing the spatial control of translation during meiotic maturation. The fully-grown mammalian oocyte is transcriptionally quiescent and stored maternal RNAs are used for the completion of meiosis and early embryo development. It was shown three decades ago that during resumption of meiosis, protein synthesis is not necessary for the nuclear envelope breakdown (NEBD) but active protein synthesis is required for the correct formation of the meiotic spindle and progression to metaphase II [START_REF] Hashimoto | Regulation of meiotic metaphase by a cytoplasmic maturation-promoting factor during mouse oocyte maturation[END_REF]. Therefore mammalian oocyte represents a suited system to address translation control in relation with the cell cycle in general and with the spindle formation in particular. In this issue of the Cell Cycle the study by Jansova et al. gains new insight into the role of the eukaryotic initiation factor 4E-Binding Protein 1 (4E-BP1) in the meiotic spindle formation in mouse oocyte (2). 4E-BP1 has been shown to undergo a dynamic and fine spatially regulated pattern of phosphorylation at sites that control its binding to eIF4E and consequently its efficiency to inhibit translation [START_REF] Romasko | Association of maternal mRNA and phosphorylated EIF4EBP1 variants with the spindle in mouse oocytes: localized translational control supporting female meiosis in mammals[END_REF][START_REF] Shang | 4E-BP1 participates in maintaining spindle integrity and genomic stability via interacting with PLK1[END_REF]. Then, it has been proposed that the localization of specific phosphorylated 4E-BP1 isoforms at the spindle pole or on the spindle represents a novel mechanism supporting localized protein synthesis related to mRNA localized at the spindle. The study by Jansova et al. goes further in demonstrating the implication of the 4E-BP1-phosphorylation status in forming a well-structured meiotic spindle. Microinjection of mRNA encoding for a dominant negative 4E-BP1 mutant (replacement of key serine/threonine residues by non-phosphorylatable alanine residues) affects translation activity and promotes aberrant spindle formation. Their data demonstrate that 4E-BP1-phosphorylation is essential to ensure correct meiotic progression. In this regard, the identification of the kinases, which are involved in the phosphorylation of 4E-BP1, represents a major challenge. Kubelka's group previously showed that chromosomal translational hotspots are controlled by the activity of the mTOR-signalling pathway during the first meiotic division in maturing mouse oocytes [START_REF] Susor | Temporal and spatial regulation of translation in the mammalian oocyte via the mTOR-eIF4F pathway[END_REF]. The current study adds new information by investigating the role of CDK1 on the phosphorylation of 4E-BP1 in mouse oocytes [START_REF] Jansova | Regulation of 4E-BP1 activity in the mammalian oocyte[END_REF]. Using specific kinase inhibitors, they showed that CDK1 and mTOR kinases are the main positive regulators of 4E-BP1 phosphorylation following NEBD (Fig. 1). The Western blot data shown by Jansova et al., indicate that CDK1 influences the activity of mTOR in mouse oocytes suggesting that CDK1 acts indirectly on 4E-BP1 phosphorylation via mTOR activation. Interestingly, both CDK1 and mTOR co-localize with specific 4E-BP1-phosphorylation isoform on the spindle at the onset of meiotic resumption. The fact that CDK1 is a positive regulator of the 4E-BP1-phosphorylation during mouse oocyte maturation will add fuel to the complicated debate of the link between the translational activity and the stages of the cell cycle. Indeed, many discrepancies that have been reported when observing translation mechanisms linked with the cell cycle might be related to direct effect of the different pharmacological agents used to synchronize cells rather than cell cycle status [START_REF] Coldwell | Phosphorylation of eIF4GII and 4E-BP1 in response to nocodazole treatment: a reappraisal of translation initiation during mitosis[END_REF]. Therefore, oocyte meiotic maturation, where the synchronism of cell divisions occurs physiologically, represents a pertinent model for the analysis of the control of the phosphorylation of 4E-BP1 by CDK1. The work by Jansova et al., revealing CDK1 activity towards 4E-BP1 phosphorylation via unexpected phosphorylation and activation of mTOR, adds more to the complexity of the signalling pathway acting upstream 4E-BP1 and may initiate further research. In view of these works, it now appears that fine control of translation activity within the spindle can play an important role in maintaining genomic stability. However, many points remain to be clarified. Among others, one can still wonder how the phosphorylations are controlled spatially on specific sites of 4E-BP1 and what their consequences on specific translation activity are. Which mRNAs are actively translated in this spatial and temporal context? The integration of 4E-BP1-phosphorylation knowledge at different levels of scales (molecular / structural [START_REF] Bah | Folding of an intrinsically disordered protein by phosphorylation as a regulatory switch[END_REF] and intracellular compartments (2-6)) opens up a promising field of investigation for systemic approaches that focus on spatio-temporal control of the mRNA translation. It is almost sure that the mammalian oocyte meiotic maturation system, by its characteristics: size and round shape, synchronism and asymmetry of meiotic divisions, its links with translation, represents an interesting future model in this context.

Figure 1

 1 Figure 1 legends: CDK1 phosphorylates and activates mTOR, which phosphorylates 4E-BP1 on different sites (after (2)). Depending on the phosphorylated sites, 4E-BP is localized in the vicinity of the chromosomes and at the spindle poles (brown dashed arrows) or is distributed along the whole spindle (red dashed arrows).


H Farhat
email: hannafarhat@hotmail.com

Y Lostanlen
email: yves.lostanlen@ieee.org

T Tenoux

G Grunfelder

G El Zein

Indoor MIMO Channel Sounding at 3.5 GHz

Keywords: radiowave propagation, MIMO channel sounding, indoor environment

This paper presents a measurement campaign carried out at 3.5 GHz. The objective is to characterize the electromagnetic waves propagation in indoor environment. A double directional channel sounder was used to perform these measurements. The collected data were then processed with a high resolution algorithm to extract the multipath parameters. A comparison between measurement results and a ray tracing tool is done to interpret the propagation mechanisms in this environment. The aim of these measurement campaigns is to obtain realistic MIMO channel models.

I. INTRODUCTION

The MIMO (Multiple-Input Multiple-Output) technique, using multiple antennas at emission and reception, is a good solution for wireless communication systems to improve data rates and the quality of service. This technique was adopted in the latest wireless systems standards (4G, WLAN, WiMAX). It exploit the spatial degree of freedom of wireless communications and thus see multipath as an opportunity [START_REF] Steinbauer | The double-directional radio channel[END_REF]. However, the performance of MIMO systems is very dependent on the propagation channel. In fact, MIMO systems perform better when deployed in rich scattering environments like indoor. Thus, the study of the transmission channel is required in this context.

In this paper, wideband double directional channel [START_REF] Steinbauer | The double-directional radio channel[END_REF] measurements were performed at 3.5 GHz in indoor environment. This frequency band is licensed for the WiMAX system in Europe but could be used also for the 5G mobile systems. A large number of MIMO measurement are found in the literature, but there is always a need for more measurement data to obtain realistic MIMO channel models [START_REF] Bonek | MIMO propagation channel modeling[END_REF]. These channel models will help wireless system designers to evaluate precisely the performances of MIMO systems for future wireless communication standards [START_REF] Patane | Basic and advanced MIMO OTA testing of wireless devices using reverberation chamber[END_REF]. This paper is organized as follows. In Section II, we present the measurement setup. Then, in Section III, the measurement campaign, the ray tracing tool and the measurement results are described. Finally, Section IV concludes this paper and draws some perspectives of this work.

II. MEASUREMENT SYSTEM DESCRIPTION

Our channel sounder [START_REF] Farhat | A dual band MIMO channel sounder at 2.2 and 3.5 GHz[END_REF] uses a periodic PN coded transmit signal based on the spread spectrum technique. It offers an 11.9 ns temporal resolution for 100 MHz sounding bandwidth. Different impulse response lengths can be recorded from 1.27 to 81.84 μs, depending on the sounding bandwidth and code length. As an example, for 100 MHz sounding bandwidth and 1023 code length, the recorded impulse response duration is 10.23 μs. The measurement dynamics is 50 dB for the 1023 code length. The synchronization between the transmitter and the receiver is achieved with highly stable 10 MHz rubidium oscillators. Such systems capture the wideband MIMO channel features of real propagation environments.

Two UCAs (Uniform Circular Array) were developed at 3.5 GHz (Fig. 1) to characterize 360° azimuthal double directional channel at both link sides. The arrays used contain 4 active elements at the transmitter (Tx) and 16 at the receiver (Rx). At the transmitter we integrated power amplifiers to increase transmitted power, and at the receiver we added LNAs (Low Noise Amplifier) behind the antennas to improve the dynamic of our measurement system. Fig. 2 shows a horizontal cut of the measured beam patterns for the two UCAs.

The collected channel data are stored on a laptop for postprocessing. Fig. 3 presents the MIMO channel sounder transmitter and receiver.

III. CHANNEL MEASUREMENTS SETUP AND RESULTS

This indoor measurement campaign was conducted in the CLE (Centre de Loisirs Educatifs) building at the INSA of Rennes campus. The transmitter was placed in two positions Tx1 and Tx2 for one fixed position of the receiver Rx. The two measurement configurations were in NLOS (Non Line-Of-Sight) conditions. Fig. 4 presents the layout of the CLE building with the positions of the transmitter and receiver in the building. Fig. 5 shows the transmitter in the position Tx1 where the transmitter antenna height is 2 m. Fig. 6 presents the receiver position in the CLE where the receiving antenna height is 1.3 m.

We assume a quasi-stationary channel during the measurements. Attention was paid that no people were moving in the building during the measurements. For each position, several measurements were taken in order to check stationarity and to average the measurements to reduce the noise floor.

The multipath parameters are obtained by using the high resolution SAGE algorithm [START_REF] Fleury | Channel parameter estimation in mobile radio environments using the SAGE algorithm[END_REF]. To interpret the measurement results, a ray tracing tool developed by SIRADEL is used [START_REF] Lostanlen | A deterministic indoor UWB space-variant multipath radio channel modelling[END_REF], [START_REF] Lostanlen | A solution to predict the 3d indoor propagation for future wireless mobile communication systems[END_REF]. The ray tracing method calculates the possible propagation paths between a transmitter and a receiver. It requires an accurate geometrical description of the considered measurement configuration scene containing the building structure and the position of the partition walls, the floors, the ceilings, the windows and the doors.

We gave a special attention to the AoD (Angles of Departure) and AoA (Angles of Arrival) which are the most important parameters to evaluate the MIMO systems performance. Fig. 7 shows the angular response (AoD) in the horizontal plane at the transmitter for the position Tx1. The measurement results are presented with red points and simulation results in blue. In this configuration, we observe a large number of multipath in all the directions with an important angular dispersion. We notice also some main propagation directions highlighted with the green arrows. Fig. 8 shows the angular response (AoA) in the horizontal plane at the receiver Rx for the position Tx1. The measurement results are presented with red points and simulation results in blue. We also observe a large number of multipath in all the directions, and also some main propagation directions are highlighted with the green arrows. Fig. 9 presents a comparison between simulation and measurement results where the main directions of departure and arrival are highlighted with green arrows. Fig. 10 shows the angular response (AoD) in the horizontal plane at the transmitter for the position Tx2. The measurement results are presented with red points and simulation results in blue. Fig. 11 shows the angular response (AoA) in the horizontal plane at the receiver Rx for the position Tx2. The measurement results are presented with red points and simulation results in blue. Fig. 12 presents a comparison between simulation and measurement results. In this configuration, we also observe a large number of multipath in all the directions with a larger angular dispersion then the position Tx1.

The ray tracing permits the interpretation of the measurement results and shows the possible origins of the multipath in this harsh indoor environment. Some discrepancy between the measured and simulated results is observed. As an example, in Fig. 8, the main propagation direction at -120° is not obtained in the simulation. This can be explained by the reflection and diffraction on the near surrounding buildings, and the furniture in the CLE building that is not considered in the ray tracing simulations.

IV. CONCLUSION

This paper reports double directional channel measurement campaign conducted in an indoor environment. Multipath parameters are obtained using a high resolution algorithm. A comparison between measurement and simulation results from a ray tracing tool is achieved. The results show a rich scattering environment with a large number of multipath and an important angular dispersion. The future work is to obtain a realistic channel model from these measurement results. Different steps are needed to obtain this channel model. First, since we have a rich indoor scattering environment, we will use a clustering algorithm to model the multiple paths in clusters. Then, statistical values for the multipath parameters like delays, AoDs and AoAs can be deduced from the measurements.

Fig. 1 .

 1 Fig. 1. UCA 4-elements transmitter (left) and 16-elements receiver (right).

Fig. 2 .

 2 Fig. 2. Antenna measured beam patterns: 4-elements Tx (top) and 16 elements Rx (bottom) .

Fig. 3 .

 3 Fig. 3. MIMO channel sounder: Transmitter (left) and receiver (right).

Fig. 4 .

 4 Fig. 4. Layout of the CLE building.

Fig. 5 .

 5 Fig. 5. Tx1 location in the CLE building.

Fig. 6 .Fig. 7 .

 67 Fig. 6. Rx location in the CLE building.

Fig. 9 .

 9 Fig. 9. Ray tracing and measurement results for Tx1 and Rx.

Fig. 12 .

 12 Fig. 12. Ray tracing and measurement results for Tx2 and Rx.


From self-organization to self-assembly

Introduction

Over the past decades, self-assembly has revived the fascination for spontaneous activities in matter. How molecular units assemble to form an organized structure or pattern without intervention of an outside source is a puzzling process that chemists and physical-chemists intensively scrutinize. To what extent did this new research field transform the relation between physics, chemistry and biology? Is it a new episode of the longstanding fight between reductionism and vitalism? Since self-organization has long been considered as a distinctive feature of living organisms, one could think that the shift of attention from self-organization toward self-assembly is one of the outcomes of the molecularisation of life, due to decades of intense research in molecular genetics and genomics. Given the technological connotation of the term assembly (which connotes an assembly line) one could presume that the focus on self-assembly marks the triumph of the mechanistic view of life over the anti-reductionnist traditions. Is it the symptom that the enigmatic spontaneity attributed to living cells has been reduced to the mechanical assembly of molecular building blocks? It would not be the first time that chemists challenge the mystery of vital organization. Since early-modern alchemy, many chemists have claimed that they could reproduce life in a testtube. A major episode in this long tradition was Friedrich Wölher's synthesis of urea in 1828, which allegedly destroyed the metaphysical belief in the existence of a vital force. It is a legend forged by nineteenth-century chemists who cared to demonstrate that life was merely a set of physico-chemical phenomena [START_REF] Brooke | Wöhler's Urea and its Vital Force -A Verdict from the Chemists[END_REF][START_REF] Ramberg | The Death of Vitalism and the Birth of Organic Chemistry: Wölher's Urea Synthesis and the Disciplinary Identity of Chemistry[END_REF]. The metaphysical challenge was part of Marcellin Berthelot's grandiose dream of synthesizing all the compounds made by living organisms, using only elements and the range of molecular forces [START_REF] Berthelot | La chimie organique fondée sur la synthèse[END_REF]. Berthelot boasted that starting with the four basic elements-carbon, hydrogen, oxygen, and nitrogen-and proceeding systematically from the most simple to the most complex compounds, chemists would dissipate the mystery of life. It was not too difficult for physiologists such as Claude Bernard, to retort to arrogant chemists that synthesizing a product from its elementary principles did not mean getting the properties of Bernadette Bensaude Vincent living beings [START_REF] Bernard | Introduction à l'étude de la méthode expérimentale en médecine[END_REF]. He also emphasized that the synthetic process used by chemists in their laboratories was very different from those created by organisms. (Bernard 1866) It is thus tempting to adopt the master narrative of the gradual triumph of science over metaphysics featuring the nineteenth-century reduction of biological products to chemical elements as a first conquest followed by the emulation of biological processes such as selforganization and self-assembly in the twentieth century. One can still find this sort of claims in recent publications. For instance an editorial in the journal Nature was headlined: "Synthetic biology provides a welcome antidote to chronic vitalism" (Nature, June 28, 2007) Synthetic biology is said to demonstrate that "life is a molecular process lacking moral threshold at the level of the cell." It thus challenges religious dogma about life and the "popular belief" that "life is something that appears when a clear threshold is crossed."

This essay discourages such positivistic claims. Considering the context of research on selfassembly I argue that the shift of attention from self-organization to self-assembly has no antivitalistic implications. Self-assembly was first and foremost investigated in an engineering context as a strategy for manufacturing without human intervention and did not raise new perspectives on the emergence of vital organization itself. However the emergence of selfassembly as a field of research has metaphysical implications.

The paper first describes the emergence of self-assembly as a research field in the context of materials sciences and nanotechnology. The second section outlines the metaphysical implications and will emphasize a sharp contrast between the ontology underlying the chemists' practices of self-assembly and the practices developed by synthetic biologists. Finally, the third section ventures some reflections on the kind of design involved in selfassembly practices.

How self-assembly became a booming research field

The term 'self-assembly' has been coined in an academic context, which significantly differed from the milieu where self-organization became a fashionable research topic in the twentieth century. To make a long story short, self-organization became a central concept in three different research communities [START_REF] Stengers | Les généalogies de l'auto-organisation[END_REF]. First, in the 1940s embryologists promoted self-organization in response to failed attempts at identifying a specific chemical substance that would induce the process of organization in early embryos [START_REF] Feltz | Self-Organization and Emergence in Life Sciences[END_REF]. Second, in the 1950s cybernetics prompted a redefinition of self-organization in the terms of Claude Shannon's theory of information. For John von Foester, self-organization meant order from noise with a decrease of relative entropy, and an increase of redundancy within the system (von [START_REF] Foerster | On self-organizing systems and their environments[END_REF]. The French biologist and philosopher Henri [START_REF] Atlan | L'organisation biologique et la théorie de l'information[END_REF] retained this definition while suggesting that it was complexity from noise, a process requiring a hierarchical multilevel system and initial redundancy. Third, Belgian physical-chemist Ilia Prigogine redefined the concept in thermodynamic terms on the basis of his investigation of dissipative structures [START_REF] Nicolis | Self-organization in nonequilibrium systems: From dissipative structures to order through fluctuations[END_REF]. Self-organization then referred to the evolution of an open system toward steady-states and this dynamic notion of self-organization concept has been extensively applied to a variety of domains ranging from biology to psychology and neurosciences, to economy.

In stark contrast, the phrase 'self-assembly' appeared in a more specific domain related to materials engineering. It was first used in the 1960s by materials scientists who were struggling to design high-performance materials with unprecedented combinations of properties for space and military applications. This goal was achieved through the design of composite multifunctional structures. Ironically this new approach, known as "materials by design" because materials are not extracted from nature but individually built up for a specific set of functions, drew the attention of materials scientists to nature. They came to realize that biological structures -wood, skin, bones… -offered many examples of multifunctional composite materials. Stephen Mann -a natural scientist who entered the field of materials science -wrote: "We can be encouraged by the knowledge that a set of solutions have been worked out in the biological domain". (Mann et al. 1989, p. 35).

Materials scientists were especially interested in biomineralization where complex structures are assembled thanks to templates which bring together the components in the right position. In marine shells the inorganic component -calcium carbonate -nucleates and grows under the control of an organic matrix. While chemists and marine biologists joined their effort to explore mineralization processes, they realized that self-assembly is ubiquitous in the natural world and can be achieved through various methods [START_REF] Ball | Natural strategies for the molecular engineer[END_REF]. One of the most elegant method is inspired by the phospholipids with hydrophobic and hydrophilic ends which form a stable structure when placed in aqueous solution. This method inspired by cell membranes relies on a process leading to equilibrium state through minimization of free energy. This arrangement has been literally mimicked to make synthetic liposomes employed as vehicles for drug delivery. The key to perform such structures is to control the kinetics of reactions. Performing chemical reactions under quasi-physiological conditions, with biodegradable and renewable by-products and with an economy similar to that of nature, is the agenda of a new style of chemistry, named "chimie douce" (soft chemistry) by Jacques Livage in 1977. In order to obtain materials whose structures and textures are determined by local energy minima rather than one global energy minimum, soft chemistry works in open reactor at ambient temperature and makes extensive uses of sol-gel route and molecular precursors. . Achieving molecular recognition is another favourite method. Emil Fisher's idea of the 'lock and key mechanism' which allows enzymes to click on a substrate has been extended to other molecules in supra molecular chemistry. This new branch of chemistry created by Jean-Marie Lehn in 1978 is clearly aimed at designing chemical processes that mimic the coding of biological processes. Its objective is to reproduce the selectivity of the interaction between receptors and substrates in biology, with the help of hydrogen bonds and stereochemistry. Thanks to molecular recognition the building blocks self-assemble to form supramolecular structures, and even materials. Selective and efficient assembly can be obtained not only with the help of hydrogen-bonding, but also with donor-acceptor interactions, or metal-ion coordination. According to Lehn, "it is one of the major chemist's motivation to see that biology successfully made highly complex properties on a molecular basis." [START_REF] Lehn | Une chimie supramoléculaire foisonnante[END_REF] As important as molecular recognition is the role of catalysts in the environment, which trigger or alter the reactivity of the binding sites.

While developing a wide spectrum of biomimetic strategies chemists have gradually outlined the conditions for designing structure bottom-up, through self-assembly (Whitesides Boncheva 2005). First, the components must be able to move and interact ; second, their interactions should be reversible in order for the components to explore a wide range of potentials for assembly; third, nevertheless in order to prevent the formation of defects the number of possible assemblies must be limited by the use of compartments or templates generating geometrical constraints. Harvard chemist George Whitesides insisted that selfassembly operates at all length-scales and opened up a fascinating perspective of design without human intervention:

Our world is populated with machines, non living entities assembled by human beings from components that humankind has made…. In the 21 st century, scientists will introduce a manufacturing strategy based on machines and materials that virtually make themselves [START_REF] Whitesides | Self-Assembling Materials[END_REF].

The perspective of self-made machines becomes crucial for engineering at the molecular scale, where human hands and tools cannot operate. Therefore self-assembly became the holy grail of nanotechnology. In the 1990s and 2000s ten percent of all nanotechnology publications were dealing with self-assembly (Maassen 2006). In his best-seller Engines of Creation (1986) Eric Drexler claimed to replace the conventional top-down design methods (such as microlithography for instance) developed in the miniaturization of computer technologies by bottom-up methods with 'molecular assemblers" that would pick and place individual molecules to assemble them in functional modules or molecular machines. Drexler's perspective of a molecular manufacture inspired by Lego sets raised sarcasms from chemists. In particular, Richard [START_REF] Smalley | Of chemistry, love and nanobots[END_REF] argued that at the nanometre scale atoms are all interconnected and sensitive to the placement of other atoms in the vicinity. The only way to deal with this 'intricate dance of atoms' is to let them self-assemble.

To sum-up, unlike self-organization self-assembly became a booming field of research in an engineering context as a technique for making artefacts bottom-up at the molecular level. In their exploration of the potentials of molecular self-assembly chemists and materials scientists certainly came closer to biologists but most of them were not interested in addressing the issue of emergence or reducing the complexity life to physics or chemistry. On the contrary Whitesides (2004) claimed that chemistry so far blindly reductionist was becoming complex because of its investigation of biological phenomena.

Where does the "genius" lie?

There is no self-assembly without the assumption of a spontaneous activity of matter, an intrinsic dunamis that can be observed at the molecular level. It enables atoms and molecules to construct a variety of geometrical shapes: helix, spiral, hollow sphere, ellipsoid, tube….. Smalley, who was awarded the Nobel Prize for his contribution to the discovery of fullerenes, elegantly referred to the 'genius' of carbon:

The discovery that garnered the Nobel Prize was the realization that the carbon makes the truncated icosahedral molecule, and larger geodesic cages, all by itself. Carbon has wired within it, as part of its birthright ever since the beginning of this universe, the genius for spontaneously assembling into fullerenes [START_REF] Smalley | Discovering the Fullerenes[END_REF].

What can be the "genius" of a chemical element like carbon? It is certainly not an obscure and mysterious vital force, a kind of animus that would come from the outside and infuse life into inanimate matter. The term "genius" referring to a natural ability and at the same time connoting an ingenuous, skilful invention definitely blurs the boundary between the natural and the artificial, between what results from a material process and what is man-made.

It challenges the Kantian theory of objective knowledge, which relies on a dichotomy between nature, defined by the stability of structures and operations that connote instability, becoming and process. For Kant, only living beings challenge the divide between structure and operation because they are self-organized. Therefore there is no objective knowledge of living organisms, which are dealt with in the Critique of Judgement rather than in the Critique of Pure Reason. According to French philosopher Gilbert [START_REF] Simondon | Epistémologie de la cybernétique[END_REF] Kant's dichotomy between structure and operation also implied that technology is a kind of corruption of nature, a denaturation [START_REF] Guchet | Nature and artefact in nanotechnology[END_REF].

Blurring the boundary between the grand divides that organize our modern culture -such as nature/artefact, nature/culture, or humans/non humans -has become a commonplace in the current post-modernist literature since Bruno Latour's famous essay We Have Never Been Modern (1993). Not only the entanglement of matter and humans is a major feature of postmodernism but American feminist theorist Karen Barad promoted the performativity of matter as an icon of a feminist metaphysics labelled "agential realism" [START_REF] Barad | Posthumanist performativity : toward an understanding of how matter comes to matter[END_REF].

However there is no need of any commitment to postmodernist or posthumanist discourses to realize that nanotechnologists no longer consider matter as a static and passive entity awaiting information from scientists and designers. In granting "genius" and performativity to molecules, in using their performances to make smart artefacts, materials chemists and nanoscientists give up the Cartesian view of nature and create a new metaphysical landscape.

Nature is no longer viewed as a static given: the natura naturata gives way to a natura naturans, a continuous process of formation (Bensaude [START_REF] Vincent | Les Vertiges de la technoscience[END_REF][START_REF] Nordmann | Enhancing Material Nature in Kamilla Lein Kjølberg and Fern Wickson[END_REF][START_REF] Vincent | Matters of Interest: The Objects of Research in Science and Technoscience[END_REF]). Kant's clear metaphysical divide between nature's immutable structures and operations, which delineated the boundary between the domains of objective science and technological action, becomes obsolete. Technosciences such as nanotechnology and biotechnology invite us to assume Simondon's claim that operativity is an objective natural phenomenon [START_REF] Guchet | Nature and artefact in nanotechnology[END_REF].

Although technoscientists never openly discuss ontological questions they all recruit material agencies to enhance the potentials of nature. However they differ about what kind of agency is embedded in matter and at what level. Where does the "genius" lie in matter and how does it operate? It is possible to delineate at least two radically different views in current practices of self-assembly.

Genetic engineering and synthetic biology rely on the assumption that the agency of matter lies in the genetic code. Accordingly, one major objective is to modify the code, or to rewrite it. Genome-driven cell engineering is one of the methods developed in synthetic biology. It consists in the modification or the synthesis of a whole genome which is transplanted into cells with a view to reprogram them. This strategy is instantiated in Craig Venter's team successful synthesis of Mycoplasma Laboratorium in 2010. Reprogramming the machinery of a cell is supposed to be sufficient to change and control its performances because the genome is viewed as the causal engine of the cell. In their effort to "redesign life" synthetic biologists revive the standard hylomorphic model since the complex behaviour of a cell results from the information of matter, or the imposition of a plan on a substrate. Indeed the instructions that command the structure and behaviour lie within the molecules of DNA and RNA, they are no longer impressed from the outside. However the metaphor of the program suggests a clear distinction and independence of the software (the genetic code) from the hardware (the molecular machinery of the cell). The genome is analogous to a designer informing matter and controlling its behaviour. As anthropologists Tim Ingold notices the genetic code is reminiscent of the clockmaker argument developed by natural theologians. "The attribution of ultimate responsibility for the design to natural selection rather than God does not affect the logic of the argument, namely that there can be no functional complexity without prior design" (Ingold 2013: 67). The agentivity of matter is located in the central instructions encoded in DNA.

By contrast, in biomimetic approaches there is no identifiable set of instructions acting as a designer. The organization and performances of molecules result from the interactions between molecules and with their environment. Although modern chemists share with biologists the conviction that living organisms are controlled by the DNA-RNA system, which contains the instructions for the machine to operate, they do not try to access and modify the code. Their challenge is to dispense with the information of the genetic code in order to self-assemble the components and to control morphogenesis. For this purpose, they play with intermolecular bonds rather than making and breaking covalent bonds between atoms as organic chemists used to do. They use reversible reactions and let molecules explore the range of possible combinations. They are looking for what interactions of molecules can afford while they resort on tricks to obtain complex systems. All the resources of physics and chemistry are put at work: chemical transformations in spatially restricted reaction fields, external solicitations like gravity, electric or magnetic fields, mechanical stress, gradients and flux of reagents during the synthesis.

Biomimetic processes are based on a combination of affordances and contrivances. The resources displayed by the interrelations and interactions between molecular entities interplay with astute tricks to monitor the spontaneous dynamics of molecules. When a substrate binds to an enzyme or a drug to its target, when signals propagate between cells, highly selective interactions occur between the partners and control the process. Supramolecular chemists investigate and implement these interactions in specially designed non-natural systems. They deal with populations of molecules and take advantage of their selectivity, their ability to recognize each other, their tendency to assemble or separate themselves. In other terms, the biomimetic approach is based on a morphogenetic model, where complex functional structures result from the collective behaviour of molecules. An order emerges out of the confluence of atoms or molecules. In order to stress that something emerges from the molecules 'being together', Lehn often claims that a glass full of water is different from a single water molecule because isolated molecules do not behave like interacting ones. The collective behaviour results from coupling processes rather than being just the expression of the information contained in each individual component. Lehn's program of Constitutional Dynamical Chemistry is a sort of molecular sociology relying on the group dynamics of an ensemble of individuals and their interactions with the milieu. Because in biomimetic practices molecules are viewed as relational and dynamic entities, they are better defined as affordances rather than as agencies. The concept of affordance revisited by Rom [START_REF] Harré | The materiality of instruments in a metaphysics for experiments[END_REF] refers to both the dispositions of atoms and the world/apparatus complex. It is a hybrid of nature and artefact, of objective properties and human purposes.

A design without designer

We have seen that the biomimetic approach developed by chemists presupposes that intrinsic contrivances in chemical molecules generate spontaneous order, whereas the synthetic biology approach relies on the assumption that the order is generated by central instructions embedded in the genome. As they still assume that a master plan is responsible for the performances of a cell, synthetic biologists are entitled to use the phrase "designing" or "redesigning life" and to present themselves as rational designers. In the Biobricks agenda, which dominates synthetic biology, their practice of is based on the model of scientific reason, which prescribes to proceed from the simple to the complex aim is to assemble bricks like Lego blocks into modules that will be in turn assembled into systems. By contrast self-assembly is a blind process of interactions through combinations and selection without rational designer. Although chemists occasionally use such phrases as "selforganization by design" (Lehn 2004) or "we self-assemble molecules", the process is going on without human involvement. The subject "we" just initiates the process of self-assembly by securing the necessary agencies and appropriate conditions.

The attractive power of self-assembly techniques is precisely that they open the way to a design without designer and more broadly to machines working without humans as Whitesides emphasizes:

A self assembling process is one in which humans are not actively involved, in which atoms, molecules, aggregates of molecules and components arrange themselves into ordered, functioning entities without human intervention… People may design the process, and they may launch it, but once under way it proceeds according to its own internal plan, either toward an energetically stable form or toward some system whose form and function are encoded in its parts [START_REF] Whitesides | Self-Assembling Materials[END_REF].

Self-assembly opens the fascinating perspective of a world of self-made machines capable of regulating their operation rather than working on the basis of a program. Such machines are not necessarily confined to the biological realm or to biomimetic processes. The archetype of self-operating devices could be the gnomon -the stick or the tree, which shows the time by the position of its shadow [START_REF] Serres | Gnomon, les débuts de la géométrie grecque[END_REF]). This prototype of a sundial is both natural and technological. There is no need of a thinking subject to design it. Similarly self-asssembly is not a "human fabrication " in the sense that the assembly process is not operated by human hands or tools. In this respect, self-operating machines are different from a robot performing human tasks because the robot has been programmed. Despite the frequency of bugs, the designer can feel that the machine is under control because the program is her creation.

What kind of control of the spontaneous process of self-assembly is involved in biomimetic strategies? Biomimetic chemists are inducing a process that delegates the task of building up to a "society" of interacting molecules. They delegate the operations they want to perform to molecules, radicals, ions…, which are not their own creation. The result of their design is not entirely the product of their hands and brain. It is mainly the offspring of a spontaneous process. In this respect, chemist and material scientists who design self-assembled structures do not have the same responsibility as the clockmaker.

Does it mean that self-assembly could work without humans? Simondon claimed that selfregulating machines such as cybernetic machines, do not dispense with human interventions. Rather they change the nature of human intervention: while conventional machines depend on humans as designers and organizers, self-regulating machines require humans as technicians, i.e. as "associates" (Simondon 1958: 174). Similarly, biomimetic chemists are the associates of nature or pilots of spontaneous material processes. Pilots rely both on natural elements and instruments to guide their sea boat. They work with nature. More precisely they negotiate with nature rather than imposing their norms and standards on nature. They know that all journeys are risky, that the success of their enterprise involves a good deal of uncertainties.

Conclusion

Material scientists and engineers who develop biomimetic practices of self-assembly do not try to reproduce life. Unlike nineteenth-century chemists they take inspiration from the processes of synthesis developed during the course of the evolution of life on earth for developing their own 'biomimetic' synthetic strategies. It is no longer a question of proving that life can be reduced to the interplay of chemical forces view a view to defeat claims that life is something essentially different from inanimate nature. The goal is to and design smart devices from bottom-up, from atoms and molecules to machines and systems. If the old debate vitalism versus mechanicism has lost salience, it is not because technosciences such as nanotechnology or biotechnology would be ontology-free. Rather it is because an alternative ontology is underlying the practices of making from bottom up. In this ontology material entities are essentially active. The view that agency is essential to matter is by no means novel. It can be seen as the continuation of a century-long tradition opposed to the Cartesian view of nature as passive matter and developed by Diderot or La Mettrie [START_REF] Riskin | The Restless Clock. A history of century-long argument over what make living things tick[END_REF]. In this materialistic perspective there is no need of a divine clockmaker since material entities are endowed with an intrinsic power to self-assemble into more complex structures.

However there are two different ways of naturalizing the divine designer. Either the designer is embodied in specific molecules such as DNA and RNA that contain the instructions for other molecules to operate. Or the designer gives way to a process of design that is performed by a crowd of interacting molecules co-operating with their environment, albeit triggered by humans. In the former case, the agency of matter is concentrated in a code or program informing matter. In the latter case, the material arrangement of molecules affords performances. In both cases, the practices of self-assembly are based on strict materialistic assumptions. But chemistry reconfigured by biomimetic practices is much less reductionist than biology reconfigured by technological ambitions.