Yu Chai

Thomas Salez

James A Forrest
email: jforrest@uwaterloo.ca

Using M w dependence of surface dynamics of glassy polymers to probe the length scale of free surface mobility

Using Mw dependence of surface dynamics of glassy

polymers to probe the length scale of free surface mobility

1

Introduction

The structure and dynamics of polymers in the near surface region close to the glass transition temperature (T g ) have attracted much attention over the past decade because they have significant implications for polymer thin film fabrication, coating, and the lubrication industry. 2 In addition, from a fundamental science perspective, understanding how and why polymers behave differently at the surface, near T g , from those in the bulk is an important ongoing question. 3,4 With more than 20 years of continuous research, accumulated evidence shows that the free surface of glassy polymers is not glassy and exhibits enhanced mobility compared to the same material in the bulk. [5][6][7][8][9][10][11][12] This enhanced mobility in the near surface region of glassy polymers is often attributed qualitatively and even quantitatively 1,6,13 to the existence of a liquid-like layer near the surface. It has been widely (though not universally) accepted that this liquid-like layer is the boundary condition that leads to the decreases in the measured T g observed in ultrathin polymer films. 14,15 While theoretical and experimental 7,[16][17][18] efforts have been made to characterize this liquid-like layer, the nature of enhanced surface dynamics of glassy polymers is far from being fully understood. Direct measurements of depth dependent local relaxation rates with nanometer precision in depth have been preformed using β-NMR, 19 but it is not clear how much these studies can be used to shed light on the α-relaxation dynamics that is responsible for bulk flow. Experimental studies of the surface relaxation of glassy films have been performed to provide a more quantitative picture, 20,21 but none of those have yet been able to quantitatively provide the size of the liquid-like layer, h * . However, we note that experiments 1 and numerical simulations 22 on the surface levelling of glassy films provide a quantitative determination of the surface mobility h * 3η , where η is the viscosity of the liquid-like layer. A key step in improving our understanding of the surface properties of glassy polymers is to find a way to independently determine h * and η.

One possibility to isolate the size of the liquid-like layer, h * , is to utilize the natural and tunable size of polymer molecules. This was done at a semi-quantitative level by Qi et al., 9 where nanoparticle embedding onto glassy PS surfaces as a function of the M w of PS was studied. In that study, there was a distinct difference in the embedding behaviour between the large M w values (87 kg/mol to 1200 kg/mol) and the low M w values (3 kg/mol to 22 kg/mol). For the lowest M w = 3 kg/mol (the one also used by Chai et al. 1 ), a surface flow was observed and is reminiscent of surface diffusion of organic glasses. 23,24 This suggests that performing quantitative surface flow experiments on polymers with varying M w , and hence the size of the polymer molecules, may provide an independent estimate for h * . Indeed, as the molecular size exceeds h * , there may be quantitative changes in surface flow that allow for the determination of h * . According to the previous study of Qi et al., there seems to be differences between the flow at the lowest value of M w = 3 kg/mol, and that at larger M w values, suggesting that the range from 3 kg/mol to 22 kg/mol should provide the transition in flow dynamics. This range also limits M w to values less than the critical molecular weight (32 kg/mol for PS) as the entanglement of polymer chains can potentially affect surface properties. 25

Results and discussion

In this article, we describe a quantitative study of the levelling of PS stepped films (with varying M w ) at temperatures above and below T g . By measuring the levelling profiles and fitting them to solutions of two different thin-film equations, we are able to distinguish without ambiguity whether the levelling is attributed to bulk or surface flow.

When the surface of a liquid film is not flat (and gravity can be neglected), surface tension drives a flow to minimize the surface area according to the equations of fluid dynamics.

Recently a number of studies have applied this idea to polymer stepped films, such as those shown in Fig. 1a. If the polymer is at a temperature T >> T g then the flow is simply that of a thin liquid film. Such systems have been studied extensively and are well understood. [26][27][28][29] In the case of glassy polymer films, bulk flow is not possible. However, experimentally, it has been shown that the levelling of stepped films still occurs for glassy polymers. In such cases, the levelling has been quantitatively described by a lubrication model involving the capillary-driven flow of a viscous layer localized at the free surface of the glassy film. 1 Mathematically, flows in both cases are described by two 2D 4 th order partial differential equations. For the case where T > T g , the equation is well studied, and we will refer to it as the Thin Film Equation (TFE)

∂h ∂t = γ 3η ∂ ∂x h 3 ∂h ∂x (1)
where h(x, t) is the sample height profile at lateral position x and time t, γ is surface tension, and η is bulk viscosity. This equation is non-linear, and is solved numerically for comparison with experiments. 30 For T < T g , flow occurs only through the liquid-like layer of thickness h * . Because the latter is much smaller than the thickness of the film (h * << h 1 , h 2 ), the equation is linear and can be solved analytically. 1,27 This equation will be referred to as the Glassy Thin Film Equation (GTFE)

∂h ∂t = γh * 3 3η ∂ 4 h ∂x 4 (2)
where now η refers to the viscosity of the liquid-like layer.

The premise of using polymer chains to probe h * derives from the natural length scale of polymer molecules. In polymer melts, chains of a sufficient number of monomers can be described as random coils following configurations of an ideal random walk. While random chains do not have definitive configurations, we can define the statistical distribution of configurations for all polymer chains, which leads to ensemble averages of variables such as the end-to-end distance (R EE ) and the radius of gyration (R g ). The value of the ratio between h * and R g (or R EE ) can be expected to control the flow behaviour. For example in Fig. 1b where 2R g < h * , the entire chain is in the liquid-like layer and thus surface flow is uninhibited. In contrast, in Fig. 1c where 2R g > h * , while there are some polymer segments in the mobile region, the fact that many parts of the chain are in the glassy immobile region means that surface flow should be inhibited, and this may lead to differences in flow behaviour.

Polystyrene (from Polymer Source Inc., PDI < 1.1) with M w = 3.0 kg/mol (T g = 343 K), 11.9 kg/mol (T g = 366 K), and 22.2 kg/mol (T g = 369 K) were used in this study, where 2R g are ∼ 3 nm, 6 nm, and 8 nm respectively. Although there is yet no consistent answer to how thick the liquid-like layer is, it has been reported by several groups that h * is only a few nanometers. Here we use the value reported by Paeng and co-workers 31 as an estimation.

In their study, a temperature dependent h * of glassy PS was measured. Corresponding to our experimental temperatures, h * is 4 nm (T = T g -6 K) to 6 nm (T = T g -3 K). Given these estimations of h * and 2R g for PS, and the study of Qi et al., 9 our range of M w should enable us to probe the transition from uninhibited to inhibited flow.

Stepped PS films were made in a two-step process. First, polymer solutions in toluene were spin-coated onto two substrates, Si wafers with a size of 1 cm × 1 cm (University Wafer), and mica plates with a size of 2 cm × 2 cm. These spin-coated films were then annealed in a home-made oven flushed with dry nitrogen above T g for more than 12 hours to remove internal stresses and residual solvents. The films were then slowly cooled back to room temperature. The thickness of the supported films on Si was measured by nulling ellipsometry, and that of mica supported films was measured by atomic force microscopy (AFM, JPK NanoWizard 3). Mica supported films were then transferred onto the surface of a clean water bath (Milli-Q). Typically, low M w PS samples on water broke up into small pieces that remained on the water surface. These film pieces were picked up by Si supported films. For the M w = 22 kg/mol films, an initial cut with a razor blade was done on the mica supported films before floating as these films did not break by themselves during the transfer process. Finally, stepped films with many sharp steps (h 1 = h 2 = 90 nm, Fig. 1a)

were dried for later study.

All experiments were conducted on a JPK AFM with a heating stage, where the annealing 1)) and GTFE (Eq. ( 2)) profiles.

Fig. 2 shows typical evolutions of PS stepped films of M w = 11.9 kg/mol at temperatures below and above T g . In particular Fig. 2a shows the evolution at T = T g -6 K, and Fig. 2b shows the evolution at T = T g + 9 K. There are two things revealed by these plots. First, M w = 11.9 kg/mol PS at T = T g -6 K exhibits some type of levelling below T g . Second, and less obviously, the shapes of the levelling profiles at two different annealing temperatures are not the same. This is analogous to our previous levelling study of M w = 3.0 kg/mol PS, where we showed that above T g the profile evolution proceeds by way of bulk film flow, while below T g it proceeds by way of surface flow.

In order to properly characterize the type of flow at play, we need to consider the detailed shapes of the levelling profiles. While it may not be clear from a casual inspection of the profiles in Fig. 2, we have previously developed a direct quantitative method to identify the flow mechanism. As long as the profiles have evolved sufficiently that the capillary surface stress can be approximated as -γ ∂ 2 h ∂x 2 , and that the early-time residual and viscoelastic stresses have vanished, and if Eq. (1) (TFE) or Eq. ( 2) (GTFE) is the governing equation, the profile h(x, t) is in fact a function of the self-similar variable xt -1/4 only. Furthermore, we can compare the experimental profile to both the TFE numerical solution, 30 and the GTFE analytical solution. 27 This comparison is done quantitatively through our previously defined correlation functions:

χ GTFE = dx(h EXP -h TFE ) 2 dx(h GTFE -h TFE ) 2 (3)
χ TFE = dx(h EXP -h GTFE ) 2 dx(h TFE -h GTFE ) 2 (4)
where h EXP , h TFE , h GTFE are the experimental, TFE, and GTFE profiles respectively. Given an experimental profile, if χ TFE is equal to 1 and χ GTFE is equal to 0, the levelling process can be precisely described by the TFE (Eq. 1). In other words, the entire film flows. In contrast, if χ TFE is equal to 0 and χ GTFE is equal to 1, the levelling process can be precisely described by the GTFE (Eq. ( 2)) implying a surface flow.

Fig. 3 shows the previous time-dependent correlation functions for PS stepped films with three M w , annealed below or above T g . For M w = 3 kg/mol PS (Fig. 3a), it is evident that both correlation functions, whether the sample is annealed above or below T g , reach their steady state values rapidly. Furthermore, it is clear that for T > T g , χ TFE 1 and χ GTFE 0; while, for T < T g , χ TFE 0 and χ GTFE 1. These results clearly indicate (as 3) and ( 4)) χ for PS with M w = 3.0 (a, d), 11.9 (b, e), 22.2 (c, f) kg/mol, where the blue squares stand for χ GTFE , and the red triangles stand for χ TFE . The annealing temperatures are (a) T g -5 K, (b, c) T g -6 K, (d) T g + 10 K, (e, f) T g + 9 K. described previously 1 ) that for 3.0 kg/mol PS, the levelling process occurs through bulk flow for T > T g and through surface flow for T < T g .

t (h) t (h) t (h)
For M w = 11.9 (Fig. 3b and3e) and 22.2 kg/mol PS (Fig. 3c and3f), the behaviours of the correlation functions are novel and insightful. Perhaps the first thing to notice is that the values of all correlation functions are, at least initially, quite different from 0 or 1. This is an indication that the profiles are not fit well by neither the GTFE nor the TFE models. While in Figs. 3e and3f, where T > T g , the correlation functions do eventually converge to their expected values, in Figs. 3b and3c where T < T g this is not the case and the results remain transient. Note that in this case the profiles are still close to their sharp initial conditions, and the linear approximation of the curvature assumed in the derivations of Eqs. ( 1) and ( 2) is certainly not valid. Specifically, for M w = 11.9 kg/mol and T > T g , after about 5-10 hours of annealing, we have χ TFE 1 and χ GTFE 0 as expected for bulk flow. For T < T g , after 90 hours of annealing, we have χ GTFE 1, but χ TFE 0.5. While this is a fairly strong indication of surface flow, it does indicate that the 90 hour experimental time window was probably too short. For this reason, the total annealing time for the 22.2 kg/mol PS at T < T g was increased to 650 hours (27 days). However, in this case again, χ GTFE 1, but χ TFE 0.5. While χ TFE does not reach its saturation value of 0 below T g in the experimental time window for M w = 11.9 kg/mol and M w = 22.2 kg/mol PS, it is safe to conclude from Fig. 3 that all PS samples show a bulk flow above T g , and surface flow or the onset of surface flow below T g . In addition, the levelling experiments for M w = 11.9 kg/mol PS stepped films at a temperature close to T g show that the saturation of both correlation functions can be achieved in a reasonable annealing time at elevated temperatures (Fig. S1) or with thinner stepped films (Fig. S2), although how the interactions between thin polymer films and substrates affect the dynamics of the liquid-like layer still remains unclear.

Similar to the conclusions by Qi et al., 9 that samples with M w less than 22 kg/mol exhibit evidence for flow at temperatures below T g , all samples in the current study exhibit levelling, and thus flow, at T = T g -6 K or T = T g -5 K. As noted previously, 1 as long as the system has evolved to the point where the evolution is self-similar, with h(x, t) being a function only of the variable xt -1/4 , then the only adjustable parameter is the mobility H 3 3η when fitting the solution of the TFE (Eq. ( 1)) or the GTFE (Eq. ( 2)) to the experimental profile. Above T g , H is equal to h 1 + h 2 /2 and η is the bulk viscosity; while, below T g , H is equal to h * and η is the viscosity of the surface liquid-like layer. Note that, although for M w = 11.9 and 22.2 kg/mol PS the correlation functions have not converged yet to their final values below T g , due to the extremely slow evolution and the fine profile details (bump, dip, etc.), the mobility values obtained from the fits are robust global features (essentially related to the evolution of the profile widths), and thus have saturated (see Fig. S1). Therefore, it is possible to extract PS mobility values for all our studied M w and T , as shown in Fig. 4a. Since PS samples with different M w values have different T g values, the temperatures are normalized by using T g /T .

As a comparison, the mobility values for M w =1.1, 1.7, and 3.7 kg/mol PS are calculated based on diffusion coefficients or viscosity values obtained in grating relaxation experiments by Zhang et al. 13 Due to the use of different temperatures, the diffusion coefficients or viscosity values for M w =1.1, 1.7, and 3.7 kg/mol PS at two temperatures (T g /T = 0.976 and 1.016) used here are extrapolated based on the fits presented in the same study by Zhang et al. Also shown as guides to the eye are power-law fits to the M w dependence.

Note that over this range we do not expect a single power law to be valid. Instead these fits are provided to demonstrate that the PS mobility below T g shows a much stronger M w dependence compared to that above T g . This implies that, for PS, surface mobility is more sensitive to the macromolecular size compared to bulk mobility. Fig. 4b further shows the ratio between the mobilities below T g and above T g as a function of M w . It is evident that the mobility ratio decreases significantly with M w , indicating a strong confinement effect due to the increase of the macromolecular size of the polymer chains. It is also noticeable that the mobility ratio shows a relatively weak M w dependence for M w > 11.9 kg/mol. This supports the idea of an intrinsic length scale less than the macromolecular size of M w = 11.9 kg/mol PS.

a b

Figure 4: (a) Mobility of PS films as a function of molecular weight, for two rescaled temperatures (orange for T g /T = 0.976 ± 0.001, and blue for T g /T = 1.016 ± 0.001). Above T g , H = h 1 + h 2 /2 and the bulk mobility is obtained by fitting the experimental profiles to the numerical solution of the TFE (Eq.( 1)), while below T g , H = h * and the surface mobility is obtained by fitting the experimental profiles to the analytical solution of the GTFE (Eq.( 2)). Our current results are represented by squares. Also shown are the results for 1.1 kg/mol PS, 1.7 kg/mol PS, and 3.7 kg/mol PS from Zhang et al. for each value of M w , the fraction of free polymer chains in the liquid-like layer is calculated as

ϕ = n f n f + n g . (5)
Fig. 5 shows the M w dependent ϕ. Taking M w = 3.0 kg/mol PS as an example, it gives ϕ equal to 0.9 meaning that 90% of the polymer chains in the liquid-like layer can flow. For M w = 11.9 and 22.2 kg/mol PS, one get ϕ values of 66% and 46% respectively. Based on these fractions, it is evident that there are many polymer chains mobile in the liquid-like layer, even when 2R g h * , but also a lot of grafted immobile chains. Although this structural picture of the liquid-like layer as a mixture of completely free and grafted chains can provide a simple explanation of the observed surface flow below T g for the samples with 2R g h * , it is still not clear how to relate quantitatively the fractions obtained in Fig. 5 to the surface mobility in Fig. 4. Nevertheless, given the different molecular-weight dependencies in PS mobility above and below T g , it is possible to conclude that long-enough polymer chains in the liquid-like layer experience some confinement effect below T g . Thus, it is reasonable to deduce that the size of the liquid-like layer (assumed to be independent of M w ) is comprised between 2 nm (2R g of M w = 1.1 kg/mol PS) and 6 nm (2R g of M w = 11.9 kg/mol PS).

Conclusion

We have measured by AFM the levelling process of PS stepped films with different M w , and found a tendency to surface flow below T g in all samples. However, the different M w dependencies in mobility observed above and below T g , and ideal-random-walk simulations, indicate that long-enough polymer chains in the liquid-like layer can experience a confinement effect. Thus, from our detailed analysis, we conclude that the size of the liquid-like layer should be comprised between 2 nm and 6 nm, and that surface flow for glassy PS films thicker than that might be inhibited for very large M w values.

The authors would like to acknowledge several helpful discussions with K. Dalnoki-Veress.

Figure 1 :

 1 Figure 1: (a) Schematic diagram of a stepped polymer film, where the thickness of the top layer is denoted as h 2 and that of the bottom layer is denoted as h 1 . (b,c) Some representative polymer chains near the surface: (b) 2R g < h * : in this case, the entire polymer chain is in the liquid-like layer and surface flow is uninhibited; (c) 2R g > h * : while there are some polymer segments in the liquid-like layer, many parts of the chain are still in the glassy immobile region meaning surface flow is inhibited.

Figure 2 :

 2 Figure 2: Temporal evolution of the stepped fronts for M w = 11.9 kg/mol PS samples annealed at two temperatures: (a) T = T g -6 K, (b) T = T g + 9 K. The insets show the experimental profiles (after 90 hours in (a), and 25 hours in (b)) compared with both the calculated TFE (Eq. (1)) and GTFE (Eq. (2)) profiles.

Figure 3 :

 3 Figure 3: Temporal evolutions of the correlation functions (see Eqs. (3) and (4)) χ for PS with M w = 3.0 (a, d), 11.9 (b, e), 22.2 (c, f) kg/mol, where the blue squares stand for χ GTFE , and the red triangles stand for χ TFE . The annealing temperatures are (a) T g -5 K, (b, c) T g -6 K, (d) T g + 10 K, (e, f) T g + 9 K.

  Figure4: (a) Mobility of PS films as a function of molecular weight, for two rescaled temperatures (orange for T g /T = 0.976 ± 0.001, and blue for T g /T = 1.016 ± 0.001). Above T g , H = h 1 + h 2 /2 and the bulk mobility is obtained by fitting the experimental profiles to the numerical solution of the TFE (Eq.(1)), while below T g , H = h * and the surface mobility is obtained by fitting the experimental profiles to the analytical solution of the GTFE (Eq.(2)). Our current results are represented by squares. Also shown are the results for 1.1 kg/mol PS, 1.7 kg/mol PS, and 3.7 kg/mol PS from Zhang et al.13 (triangles). The solid lines represent power-law fits, as guides to the eye. (b) Ratio of the mobility values shown in (a) as a function of M w , where M b represents the mobility at T g /T = 1.016 ± 0.001, and M a represents the mobility at T g /T = 0.976 ± 0.001. The solid curve is a guide to the eye.

  mol) M w (g/mol)

Figure 5 :

 5 Figure 5: Ideal-random-walk simulated fraction of free polymers in the liquid-like layer as a function of PS M w . The inset shows three typical cases: (a) a free polymer chain, (b) a partially grafted polymer chain, (c) an embedded polymer chain.

Financial support from Natural Sciences and Research Council of Canada is gratefully acknowledged. Research at Perimeter Institute is supported by the Government of Canada through Industry Canada and by the Province of Ontario through the Ministry of Economic development and Innovation. JAF would like to thank ESPCI Paris for funding through the Paris Sciences Chair.

Before linking the different M w dependences in PS mobility below T g and above T g to the ratio between h * and 2R g , it is worthwhile examining the distribution of polymer conformations near a flat surface. For that purpose, we invoke a simple ideal random-walk based simulation. In order to map the ideal random walks to real molecular conformations, we consider that for PS, one Kuhn monomer has a molar mass M 0 = 720 g/mol and one Kuhn length is b = 1.8 nm. [START_REF] Rubinstein | Polymer Phyics[END_REF] We use the Kuhn length as the elementary spatial step size to ensure no correlation between two successive steps. h * is set to be three Kuhn lengths (h * = 3b = 5.4 nm). 31 For each value of M w , and thus total chain length, we simulate ideal random walks that can possibly have a segment in the surface region. In order to accomplish this, each random-walk realization among a set of 10,000 attempts is started with one end at a distance z = z 0 from the free surface, and arrested after N = M w /M 0 (in fact the integer part of it) steps. The value z 0 is then varied from 0 (the free surface) to (N + 3)b, since no chain starting at any z 0 greater than this last value can possibly have a segment in the liquid-like layer. While this ignores effects such as chain-end enrichment, [START_REF] Jalbert | [END_REF][34][35][36] and any enthalpic effects on chain conformations, it is a good starting point for our discussion.

During the simulation, two variables are defined. These variables are n f , the number of free chains, and n g , the number of grafted chains in the liquid-like layer. We are interested in knowing what fraction of polymer molecules in the liquid-like layer can be considered as freely flowing. This can be alternatively rephrased as: "What fraction of polymers that have at least one segment in the liquid-like layer have all segments in this layer?". We illustrate this by an example in the inset of Fig. 5. In the case (a), the entire polymer chain is in the liquid-like layer, i.e. this is a free polymer chain. For this realization, n f is increased by 1.

In the case (b), only 60% of the polymer chain is in the liquid-like layer, i.e. this is a grafted polymer chain. Thus, n g is increased by 0.6. In the case (c), no part of the polymer chain is in the liquid-like layer, i.e. this is an embedded polymer chain. Therefore, both n f and n g remain unchanged.

After generating 10, 000 ideal random walks for each value of z 0 (among N +3 values), and


Gabriel V Markov
email: gabriel.markov@sb-roscoff.fr

Jean Girard

Vincent Laudet

Catherine Leblanc

Hormonally active phytochemicals from macroalgae: a largely untapped source of ligands to deorphanize nuclear receptors in emerging marine animal models

Keywords: hormonally active phytochemicals, macroalgae, ligands, nuclear receptors

Hormonally active phytochemicals (HAPs) are signaling molecules produced by plants that alter hormonal signaling in animals, due to consumption or environmental exposure. To date, HAPs have been investigated mainly in terrestrial ecosystems. To gain a full understanding of the origin and evolution of plant-animal interactions, it is necessary also to study these interactions in the marine environment, where the major photosynthetic lineages are very distant from the terrestrial plants.

Here we focus on chemicals from red and brown macroalgae and point out their potential role as modulators of the endocrine system of aquatic animals through nuclear hormone receptors. We show that, regarding steroids and oxylipins, there are already some candidates available for further functional investigations of ligand-receptor interactions. Furthermore, several carotenoids, produced by cyanobacteria provide candidates that could be investigated with respect to their presence in macroalgae. Finally, regarding halogenated compounds, it is not clear yet which molecules could bridge the gap to explain the transition from lipid sensing to thyroid hormone high affinity binding among nuclear receptors.

Introduction: what are HAPs and why do we need a systematic look at them to understand the endocrinology of emerging marine model organisms

Hormonally active phytochemicals (HAPs) are molecules that are endogenously synthesized by plants and have a modulatory effect, either positive or negative, on the endocrine physiology of animals [START_REF] Lambert | Hormonally active phytochemicals and vertebrate evolution[END_REF]. The best-studied examples are estrogenic compounds from land plants, which were first described in a pioneer study on red clover effect on fertility of ewes (Bennets, 1944). These compounds, mainly coumestans and flavonoids, compete with endogenous estrogens to bind to nuclear estrogen receptors (ERs) in vertebrates resulting in disruption of reproduction. This phenomenon has already been brought into an evolutionary perspective, stressing that flavonoids involved in root-microbe interactions were recruited for their estrogenic effects on vertebrates [START_REF] Baker | Endocrine activity of plant-derived compounds: an evolutionary perspective[END_REF]McLachan et al., 2001;[START_REF] Fox | Phytoestrogen signaling and symbiotic gene activation are disrupted by endocrine-disrupting chemicals[END_REF][START_REF] Lambert | Hormonally active phytochemicals and vertebrate evolution[END_REF], and lead to practical results in conservation biology [START_REF] Tubbs | Advances in conservation endocrinology: The application of molecular approaches to the conservation of endangered species[END_REF]. In parallel, marine chemical ecology has matured into a very ample research field, including algal-herbivore interactions, but with a strong focus on chemicals that either mediate repellent effects, or contribute to the recruitment of predators [START_REF] Hay | Marine chemical ecology: chemical signals and cues structure marine populations, communities, and ecosystems[END_REF]. With the exception of the so-called « insidious » effects of diatom grazing on copepod reproduction in laboratory experiments [START_REF] Miralto | The insidious effect of diatoms on copepod reproduction[END_REF], for which the ecological relevance is still under active investigation (Paul et al., 2012, Ianora et al.,

Perspective: towards a connection between environmental cues and physiological processes

To date, the evidence of a physiologically relevant connection between macroalgal signaling molecules and animal endocrine systems through nuclear receptors is not substantiated to the same level in the four main chemical classes of potential ligands. The connections are quite strong for steroids and oxylipins, providing precise candidates for follow-up investigations. Concerning carotenoids, molecules isolated from cyanobacteria also provide candidates to search for in macroalgal metabolomes. Regarding halogenated compounds, more exploratory work will be necessary. The tremendous chemodiversity of biological molecules makes it quasi-impossible to systematically test all possible ligand-receptor interactions in an unbiased way, especially when studying emerging model organisms. It is always necessary to find compromises between exploratory searches including a wide variety of compounds, and detailed physiologically meaningful investigations of a reduced part of the chemical space. Furthermore, we focused here on nuclear receptors, but exactly the same reasoning could be applied to membrane receptors, biosynthetic enzymes, and all kinds of proteins that undergo allosteric modulation by small molecules. Regarding membrane receptors, there is already solid evidence that phytochemicals have strong interactions with the estrogen membrane receptor, GPER [START_REF] Thomas | Binding and activation of the seven-transmembrane estrogen receptor GPR30 by environmental estrogens: a potential novel mechanism of endocrine disruption[END_REF]. Endocrinology and natural products chemistry have diverged long time ago, but the increasing availability of genomic data is now changing this situation, making it possible to put metabolic diversity into an evolutionary context in a more and more comprehensive way [START_REF] Edison | The Time Is Right to Focus on Model Organism Metabolomes[END_REF]. The chemical identification of new hormones is still a challenging task, requiring long-term collaboration between chemists and biologists, but could benefit from the technical improvements in the field of natural product-based drug discovery [START_REF] Harvey | The re-emergence of natural products for drug discovery in the genomics era[END_REF]. Indeed, herbal compounds from traditional Chinese medicine have already brought important information about the synergistic effects of multiple molecules [START_REF] Li | Botanical compounds and their regulation of nuclear receptor action: the case of traditional Chinese medicine[END_REF]. We anticipate that functional assays using available molecules from other, and ecologically-relevant organisms will constitue another promising alternative for this research field. Our hope is that incorporation of molecules that are present in the food of the studied model animals in those assays will accelerate the mechanistic understanding of the connection between environmental cues and physiological processes.

Acknowledgments

This paper was stimulated by presentations and discussions during the 18th International Congress of Comparative Endocrinology. We also thank Simon Dittami for comments on the manuscript. This work benefited from the support of the French Government via the National Research Agency investment expenditure program IDEALG (ANR-10-BTBR-04) to GVM and JG and from Région Bretagne via the grant « SAD 2016 -METALG (9673) » to GVM.


Master Valque Léo

Sylvain Lazard
email: sylvain.lazard@inria.fr

Introduction

The problem of snap rounding consists in rounding the vertex coordinates with a certain guarantee on topology and geometry. We will first explain why snap rounding is necessary. Then, we will describe a solution to this problem in 2D and why it cannot be generalized in 3D. Then, we will describe the only existing solution in 3D for fixed grid. The goal of the internship was to implement, evaluate and improve this solution. We will present our implementation of this algorithm and then how to improve the algorithm and the implementation in the future.

Need for 3D Snap Rounding

Rounding 3D polygonal structures is a fundamental problem in computational geometry. Indeed, many implementations dealing with 3D polygonal objects, in academia and industry, require as input whose vertices have coordinates given with fixed-precision representations (usually with 32 or 64 bits). On the other hand, many algorithms and implementations dealing with 3D polygonal objects in computational geometry output polygons whose vertices have coordinates that have arbitrary-precision representations.

For instance, when computing boolean operations on polyhedra, some new vertices are defined as the intersection of three faces and their exact coordinates are rational numbers whose numerators and denominators are defined with roughly three times the number of bits used for representing each input coordinate (Fig. 1). This discrepancy between the precision of the input and output of many geometric algorithms is an issue, especially in industry, because it often prevents the output of one algorithm from being directly used as the input to a subsequent algorithm. [START_REF] Zhou | Mesh arrangements for solid geometry[END_REF].

In practice, coordinates are often rounded without guarding against changes in topology and there is no guarantee that the rounded faces do not properly intersect one another. This naive rounding can make improper data that cannot be use after. In 3D, There are 2 possible types of intersection: a vertex that traverses a face or an edge that traverses an other edge.

For example, on a dataset of 10K meshes from thingiverse called thini10K, about half of the meshes have self-intersections. During mesh repair on this dataset , the naive snap rounding fails on 2.2% of cases [START_REF] Zhou | Mesh arrangements for solid geometry[END_REF].

Formal Statement

Given a set of disjoint-interior faces in 3D, the problem is to subdivide the faces and round the vertices so that no two disjoint faces map to faces that properly intersect during motion. For clarity, all schemes consider that vertices are rounded on the integer grid.

In such schemes, disjoint faces may collapse but this is inevitable if the rounding precision is fixed and if we bound the Hausdorff distance between one of each of them and their rounded images (Fig. 2). Furthermore, it is NP-hard even in 2D to determine whether it is possible to round simple polygons with fixed precision and bounded Hausdorff distance, and without changing the topological structure [START_REF] Milenkovic | Finding compact coordinate representations for polygons and polyhedra[END_REF]. So subdivisions may be needed.

The partical problem is to round the coordinates with a fine precision such as float or double.

2D Snap Rounding

The same problem in 2D for segments, referred to as snap rounding, has been widely studied and admits practical and efficient solutions [2, 5-8, 10-12, 15]. We describe one solution for 2D snap rounding. Let L the list of the input segments (Fig. 3), for each intersection or boundaries of segments, we create a "hot" pixel (Fig. 4) (a pixel is a unit square centered on the integer grid). If a segment goes through a hot pixel, we split it in 2 (Fig. 5). Then we can move old and new vertices to the center of their pixels without intersection (Fig. 6). Figure 4: We label hot all pixels that contain an endpoint of a segment or an intersection.

Figure 5: We split all edges that intersect go through a hot pixel.

3D Snap Rounding

In this context, there exist only 2 algorithms for rounding the coordinates of 3D polygons with the constraint that their rounded images do not properly intersect and that every input polygon and its rounded image remain close to each other (in Hausdorff distance). The first one was presented by Fortune [START_REF] Fortune | Vertex-rounding a three-dimensional polyhedral subdivision[END_REF]. But this algorithm is very complicated and only works on a grid whose size depends on the number of vertices by 1/n. The second algorithm works with a fixed grid size independant of the input and will be described in the next section [START_REF] Devillers | 3D Snap Rounding[END_REF].

To understand why 3D snap rounding is difficult, note first that it is reasonable to round every vertex to the center of the voxel containing it (a voxel is a unit cube centered on the integer grid). But, by doing so, a vertex may traverse a face and to avoid that, it might be necessary to add beforehand a vertex on the face, which requires triangulating it (Fig. 7). Newly formed edges may cross other edges when snapping. To avoid this, new vertices maybe added to these edges, in turn requiring further triangulating of the faces. It is not known whether, there exist such schemes that always terminate. During mesh repair on Thingi10K, after 20 recursions of this scheme, 0.05% of the meshes have always self-intersections [START_REF] Zhou | Mesh arrangements for solid geometry[END_REF]. Further difficulties of snap rounding faces in 3D is described by Fortune [START_REF] Fortune | Vertex-rounding a three-dimensional polyhedral subdivision[END_REF].

3D Snap Rounding Algorithm 2.1 Introduction

We describe the algorithm presented by Devillers, Lazard and Lenhart for solving the snap rounding problem [START_REF] Devillers | 3D Snap Rounding[END_REF]. Recall that this is the first and only algorithm that solves the problem with a grid size that is independant combinatorial size of the input. This algorithm is divided in 4 steps:

•

Step 1: Collapse the faces that are close to one another

For each face F i , we project it on faces F 1 to F i-1 in this order. The projection of F i to F j such that for each point p of F i , we project p on F j onto p on F j if and only if p is at distance at most 1 from p. To keep the faces connected, we create walls between parts of the original face and the projected parts (Fig. 8)-(Fig. 9). This step gives the property that for each face F , there are no faces at distance less than 1 along y except for the connecting walls that we created.

Step 2: Partition the space into xy-parallel slabs

We project all faces obtained by Step 1 on the floor, we obtain a 2D arrangement. An arrangement of segments is the partition of the plane formed by these segments. For each facet of this arrangement, we lift it on all faces above it (Fig. 10). So after this step, for all pair of faces, their projection on the floor are equal or interior disjoint. Then we partition the space into slabs (Fig. 11). There are 2 types of slabs. A Thin Slab is a closed region bounded by two side walls x = c ± 1 2 f orc ∈ Z. So a thin slab will be rounded onto his middle plane. A Thick Slab is a closed region bounded by two consecutive thin slabs (it can have 0 width). We create a thin slab for each vertex of the 2D arrangement on the floor. A thin slab may contain several of such vertices. With this, there are no vertex in thick slabs. Then, we project the faces on the backwall and we create a thin slab for each vertex of the induced arrangement. Then we cut the faces by the slab boundaries (Fig. 12). With this, no two edges in a thick slab intersect each other on the backwall projection.

Step 3a: 2D snap in thin slab to prepare triangulation

In a thin slab, faces will be rounded on a single plane, so the problem become 2D and we can solve it with a 2D snap rounding (Fig. 13a). First, we project the edges on the middle plane and then we snap them in 2D (Fig. 13b). Then we do a L1 projection of the created vertices by the 2D snap on their original edges (Fig. 13c). This step can create vertices in the side walls shared with the adjacent thick slabs.

Step 3b: Triangulation of the faces in thick slabs

After treating all thin slabs, we can continue with thick slabs (Fig. 14). In a thick slab, faces are trapezes. To keep planar faces after rounding, we need to triangulate them. Thanks to Step 2, all faces have identical or interior disjoint floor projections. To ensure that triangulation edges do not intersect after snapping, we define them so that their floor projections are identical or interior disjoint. So we add edges that link the "top-left" vertex of each trapeze with its "bottom-right" vertex (Fig. 15) (viewed in projection on the floor). During Step 3a, we could have created new vertices on the walls of the slab, so we need to triangulate these points as well (Fig. 16). After these steps, vertices can be rounded without creating intersections (Fig. 17). Figure 17: We can round safely.

Correctness and complexity

The proof of correctness of this algorithm is complicated and described in the original paper [START_REF] Devillers | 3D Snap Rounding[END_REF]. To compute the complexity, we count the number of lines supporting edges instead of the number of edges.

• •

Step 2 : we project lines on the floor and then lift them back. Lifting on the O(n 2 ) connected walls created by Step 1 is not necessary [START_REF] Devillers | 3D Snap Rounding[END_REF]. We have at most O(n 2 ) lines on the floor and each one can be lifted onto the n faces. So we have at most O(n 3 ) lines in the scene after the lifting.

we project these lines on the back to compute thin slabs. An arrangement of O(N ) lines has at most O(N 2 ) intersection points so with N = n 3 we have at most O(n 6 ) intersection points so at most O(n 6 ) slabs.

we cut the O(n 3 ) faces of the scene by these O(n 6 ) slabs so we have at most O(n 9 ) faces, O(n 3 ) per slab.

• Step 3a : 2D snap rounding can create O(N 3 ) vertices for an input of size O(N ) so we can have O(n 9 ) vertices per thin slab. O(n 15 ) vertices in all slabs.

• Step 3b : in a thick slab, we create an edge for each face and for each vertex created by adjacent slabs. There are at most O(n 3 ) edges inside the slab and at most O(n 9 ) vertices created by adjacent slabs. So we have at most O(n 9 ) edges in the slab.

So with all steps, we have at the end a space complexity of O(n 15 ). The time complexity is O(n 16,5 ) [START_REF] Devillers | 3D Snap Rounding[END_REF]. This algorithm is polynomial but has a very high complexity in worst case.

With some assumptions, the complexity decreases to O(n 5 ) in space and O(n 6,5 ) in time [START_REF] Devillers | 3D Snap Rounding[END_REF]. But if edges are "small" and vertices are "well distributed", intersection will be "rare" and we can expect O(n) slabs in practice. In a "distributed" setting too, cutting a scene by a plan hits O( √ n) faces so we can expect O(n √ n) in practice. One of the goals is to evaluate if these assumptions are correct.

Algorithm implementation

The goal of the internship was to implement, evaluate and improve this algorithm using the CGAL library [START_REF]CGAL User and Reference Manual[END_REF]. CGAL provides us some usefull package :

• A representation of 3D scenes named halfedge data structure (see next paragraph).

• An implementation of 2D arrangement as input a set of 2D segments and output an halfedge data structure on the 2D plane.

• An implementation of 2D snap rounding.

To implement this algorithm, we use the halfedge data structure (Fig. 18) [START_REF] Kettner | Halfedge data structures[END_REF]. Each halfedge h goes from a source vertex s to a target vertex t (also called incident vertices). h has a pointer on his adjacent face f . Its opposite halfedge has for source t and target s and a different adjacent face. The next halfedge of h is the halfedge with source t and the same adjacent face f . The previous halfedge has target s and the same adjacent face too. The halfedge data structure implements some operations on structure like split a facet or an edge (Annexe B).

The big advantage of the halfedge data structure is that if we modify a face of the scene, all adjacent faces will automatically be modified. With it we can easily manage the creation of vertices. The disadvantage of the halfedge structure is it does not really manage the edges adjacent to more than 2 faces (we have to duplicate edges and vertices in this case).

We describe in the next section the implementation of Step 1 and Step 2. The implementations of Step 3 and Step 4 are really simple and we will not describe it.

2D Snap Rounding Implementation

When we used the 2D snap rounding of CGAL, this one was surprisingly slow. After some research, we discover that this package of CGAL was old and not optimized and so we reimplemented it.

We implemented the algorithm describes in Section 1 1.3 [START_REF] Guibas | Rounding arrangements dynamically[END_REF]. To find pixels that need to be "hot, we compute the intersection points with the 2D Arrangement package of CGAL. Then, for each "hot" pixels (x, y), we add the segments [(x + 0.5, y + 0.5), (x -0.5, y -0.5)] and [(x -0.5, y + 0.5), (x + 0.5, y -0.5)] to the arrangement, these segments form a cross in this pixel. For each segment of the input, if it goes through a hot pixel, it necessarily intersect this cross and this segment is cutted. Then we can round the points. The majority of operations are done by the arrangement package of CGAL and not by us. We compared our implementation and the implementation of CGAL on random inputs of different size (Fig. 19). Inputs was segments of length O( √ n), on average, we have O(n) intersections of segments. For all input, the 2 implementations give the same output. For running times, the 2 implementations seem to have not the same complexity. Our implementation take 6 less times for the largest tested input. Test with segments of length O(n) gives the same result, on average, we have O(n 2 ) intersections of segments. Our implementation is 2 times slower for segments of length O(1), on average, we have O(1) intersections of segments (Fig. 20).

Step 1 Implementation

Difficulties

In Step 1, we need to project faces that are close to one another. When a face F is projected, possibly only a part of F is projected. So we need to continue with the projections of the rest of F onto the other faces. Problem, the difference of 2 convex polygons can be non-convex non-connected polygons with holes (Fig. 21). Managing side walls with these non-convex non-connected polygons with holes is a nightmare to implement. To avoid this problem, we have modified Step 1.

Figure 21: Example of projection of Step 1 (the connected walls are not drawn). We can see a hole in the middle triangle and a quite complicated form of the top triangle (there is a tooth inside the red circle).

Step 1 in a Thick Slab

We present a modification of the algorithm in Section 2. We split Step 1 into two parts. We do the first part at the beginning of the algorithm and the second just after the cutting by the walls (between Step 2 and

Step 3).

In the first part, for each pair of faces A and B, we calculate the intersection lines between plane A with plane B ±  and plane A ±  with plane B and then we cut the faces A and B by these 2 lines (Fig. 22). So after this cutting, if a part of a face A is at distance less than 1 along y of a face B , then all A is at distance less than 1 of B (Fig. 23).

In the second part, so righ after Step 2, we perform the projection described in Step 1 in all thick slabs. In thick slabs, the faces are trapezoids without intersection between the edges in the back-wall projection. The difference of such trapezes can only be same kind of trapezes, so we avoid holes and non-convexity (Fig. 24). The projections and building of the walls are really simplified.

With this projection, we create new edges and faces such that the equal or disjoint floor projection property can be lost. To avoid this, during the first part of the modified Step 1, we add the projection of the face A on the plane B and the projection of the face B on the plane A . Does this is brutal and unefficient and was only done to have a complete algorithm before the end of the internship. A proper modification is simply to repeat Step 2 in the thick slab. However, degeneracies are produced by projections and need to be managed (see (Annexe C)). We have modified the algorithm so that we have to justify the correction of this change. Lemma 2 of Devillers, Lazard and Lenhart's article states that during the projection of Step 1, Hausdorff's distance before and after the rounding never exceeds 1 and the topology is preserved up to collaspe [START_REF] Devillers | 3D Snap Rounding[END_REF]. Lemma 3 of the same paper states that after Step 1, the distance along y between 2 points of different faces is at least 1. The modification of Step 1 described below respects the assumptions of these lemmas. So the proof of correctness inside thick slabs is unchanged. Inside thin slabs, these lemmas are not used and the proof is also unchanged.

Segment Tree

The projection of Step 1 must project all faces on all others, rigorously, it is a O(n 2 ) but we project only over a distance less than 1. We optimize it with segment trees [START_REF] Louis | An optimal worst case algorithm for reporting intersections of rectangles[END_REF]. We can approximate faces by its bounding box and project them only if their bounding boxes are at distance of less than 1. With segment trees, recovering the intersections of n boxes has for complexity O(nlog(n) + k) where k is the number of intersections.

Step 2 implementation

Arrangement on the floor

After computing the floor arrangement, for each facet of this arrangement, we must find all 3D faces that are above. Arrangement package of CGAL takes segments as input and it does not give us this. To do this, we color all input segments with the indexes of its adjacent faces and store one oriented segment for each 3D face (Fig. 25). An edge can have many adjacent faces so can have as much colors.

Then for each 3D face, we make the following algorithm (Fig. 25). We color the adjacent 2D facet of the stored segment with the index of the 3D face. Then, for each boundary edge of this facet, if the segment of this edge does not have the color of this 3D face, we color the facet on the other side of this edge and we repeat this process for this facet. Repeating this process for each face implies that facets may have several colors. Now, we have the 3D faces above 2D facets, we can lift them.

Lift the arrangement

To lift the facets, we simply project them onto all planes of the 3D faces above. The floor facets can have complex shapes and we therefore prefer to completely rebuild the scene instead of trying to modify it. But we have to keep connectivity between faces so if 2 faces share a vertex, it must be lifted to a single vertex.

To do this, for each vertex of the 2D arrangement, we store all 3D vertices already lifted from this 2D vertex. Each time we lift a facet F on a plane A, for each 2D vertex of that facet, we check if we have already created a 3D vertex on that plane, if that is true we take that point, otherwise we create a new vertex.

Efficient cut of Faces

Cutting a scene by a plane has complexity O(n) where n is the number of edges. Unless the grid is rough, we have at least O(n) slabs (we create one slab per vertex). If we make a naive cut, we have a complexity of O(n * s) = O(f * l * s) where s is the number of slabs, f the number of faces and l the mean size of a face. We will present an efficient way to cut a face by slabs (Fig. 26).

First, find the left vertex of the face and we target the wall to the right of this vertex. We were going to go through the edges clockwise. If an edge goes from left to right, if it crosses the target wall, we split the edge , stack the created vertex and target the next wall. If one edge goes from right to left, we target the previous wall. If it crosses the target wall, we split the edge, target the previous wall and link the created vertex with the top of the stack (Fig. 26).

With this small algorithm, cutting a face F by s slabs is O(log(s)

+ k + l)
where k is the number of slabs that truly cutting F and l the size of the face. So we have a general complexity of O(f * (log(s

) + k + l)) = O(n + f * (log(s) + k))
which is really smaller than the naive algorithm.

(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) (n) (o)

Result of the implementation

We tested our implementation (without Step 1) on a polyhedron of a aircraft of around 70.000 faces with a rough grid size (Fig. 27). The output has a voxelated appearance that is not the desired behaviour. This algorithm makes no sense in the context of a rough grid. The problem is that the algorithm becomes very slow and has a very large output when we take a very fine grid. The cause is the number of thin slabs. with a very fine grid, we can expect as many thin slabs as the number of vertices in the bottom arrangement (5.000.000 vertices in the backwall arrangement for the aircraft).

The running time is dominated by the 2D snap in the thin slabs and so adds thin slabs taking more time. With this, it is impossible to run the algorithm on very fine grid except for very small input.

To evalutate the complexity, we compute the size of the backwall arrangement on 250 elements of the Thingi10k Dataset [START_REF] Zhou | Thingi10k: A dataset of 10, 000 3d-printing models[END_REF]. On a log-log scale, we obtain a scatter plot that is concentrated around a line (Fig. 28). A linear interpolation gives us a size of the backwall arrangement of 141n 1.13 where n is the number of vertices in the input. We can interpret these results as the backwall arrangement being linear or almost-linear but with a significant prefactor and a significant variance. Therefore, the assumption that the backwall arrangement is linear was correct such that the algorithm has the expected space complexity of O(n * sqrt(n)) in practice. But with a significant prefactor, this complexity is actually too large to use in practice.

So the algorithm is unusable in this form, for very fine grids. But the trivial rounding works on the majority of vertices so we can design a lazy algorithm that makes trivial rounding where are possible and do the heavy algorithm where are needed. 5 Improvement of the algorithm and the implementation

We have described the implemented version of the algorithm but improvements are needed to have a usable version. In this section, we present different ways to improve the algorithm in the future.

Lazy algorithm

The standard algorithm is slow and returns an output that is too large for fine grids. We know that the trivial rounding works most of the time [START_REF] Zhou | Mesh arrangements for solid geometry[END_REF]. The idea is therefore to run the heavy algorithm only where it is needed. First, we have to detect problematic elements. For each vertex-face or edge-edge pair, we check if the 2 elements risk to intersect when continuousy snap rounding the vertices (Fig. 5.2). If they intersect, the concerned vertices, edges or faces are "frozen".

We isolate the frozen elements in work slabs (Fig. 29). For each problematic intersection, we create a work slab that starts from the largest x ∈ Z smaller than the x-coordinate of the vertices of the frozen elements and ends at the smallest x ∈ Z larger than the x-coordinate of the vertices of the frozen elements.

These slabs are bounded by walls and we cut the edges that traversing these walls. By cutting the edges, we create new vertices and faces need to be triangulated.

We have to check if the edges of the triangulation don't create new problems. If the new edges create a new intersection, we go back before cutting by the walls of the work slabs. Now, we double the width of the work slabs and try again.

After finding correct work slabs, we run the heavy algorithm inside them and trivial rounding outside.

Test of proper intersection

For the vertex-face intersection, if the motions are linear to the voxel centers, computing the intersection amounts to compute a determinant of degree 6 amounts to solve a polynomial of degree 3 (defined by a 4x4 determinant). Then for these roots, it should be determined whether the corresponding plane-line intersection points lie in the moving face. To avoid these complicated computations, we propose the following scheme in which instead of moving each vertex in a straight line to its voxel center, we first round in x, then y then z.

In what follows, orientation is the sign of the determinant of 4 points in homogeneous coordinates. First, we round the x-coordinate. Thus, the projection on the yz-plane doesn't change with the snap. To check if a vertex traverses a face, the orientation of the 4 points before and after the rounding is calculated. If the orientation has changed, it is possible that the vertex and the face intersect each other. Next, we check if the projection of the vertex in yz-plane is in the face, if that is the case then they intersect each other, otherwise they do not.

Then we do the same thing on y and z. If there is an intersection on at least one of the 3 coordinates, the 2 elements properly intersect.

We do something very similar for edge-edge intersection. First we move on x. As for the vertex-face intersection, we check if the orientation of the 4 points has changed. If the orientation has changed and the projection of edges in yz-plane intersects, they intersect each other in 3D. Then we round on y and z.

This checker was implemented during the internship. As accelerator, we used the Segment tree described in Section 3 3.2.3. With this accelerator, we check if 2 elements intersect each other only if they are closed.

Lifting only in thick slabs

We observed in our experiments that most of the time is spent in thin slabs. So, to improve the running time it may be useful to reduce the number of vertices and edges in the thin slabs. Lifting the faces from the floor is only necessary in thick slabs so the goal is to lift only in thick slabs [START_REF] Devillers | 3D Snap Rounding[END_REF].

To do this, we modify the algorithm described in "Step 1 in thick slab section" (Fig. 3.2.2). First, in Step 2, we compute the floor arrangement, lift the segments in 3D then compute the backwall arrangement to have the position of the thin slabs. But we forget the lifted segments for what follows, we don't modify the scene, we have only compute the position of the thin slabs.

Then, in thick slabs, we do Step 1' normally as described. This Step 1' adds segments, we add them to the floor arrangement and we add new slabs if needed.

And now, we lift the segments of the floor arrangement in the the thick slabs. We only lift on trapezes and the segments of the floor can cut the trapezes only on the slab walls. As a result, lifting must be easy.

With this, we can lift floor arrangement only in thick slab and reduce the number of elements in the thin slabs. Its should reduce the size of the output and the running time of the algorithm.

Avoid exact calculations

The compute of the arrangements need to be done with exact coordinates. In CGAL, a lazy exact representation is used [START_REF] Hemmer | Number types. In CGAL User and Reference Manual[END_REF]. A number x is represented by a couple (I, G) where I is a float interval that contains x and G is the acyclic graph (DAG) of the operation done to obtain x. The goal is to do as much as possible computation with the intervals and when intervals arithmetic fails CGAL uses the DAG to recalculate the value of x with an exact representation (often rational).

For example, when we compare 2 numbers x = ([x 1 , x 2 ], G x ) and y = ([y 1 , y 2 ], G y ), if x 2 < y 1 we know without exact computation that x < y. Exact computation is only done when is needed.

But if we lift as explained in Section 5.3 a segment on a face, such segment will end exactly on the face boundary (without subdividing it) and thus exact computations will be triggered generically when computing the arrangement of the back wall projection (Fig. 30). A possible improvement is to extend a little segments to avoid exact computations (Fig. 31). With an "enough small" extension, we expect a constant number of unwanted intersections.

Summary of the work performed

We give a small summary of all the work performed during the internship:

• Implementation of 2D snap rounding.

• Completion and implementation of all steps of the 3D snap rounding algorithm.

• Design and implementation of a checker that verifies if a naive rounding works and detect problematic edges.

• Design of improvements of the actual algorithm.

Conclusions and Perspectives

3D Snap Rounding is a fondamental issue in computational geometry. There is only one algorithm that solved this problem on an arbitrary fixed grid. The internship provided proof that this algorithm is implementable. It's currently the only implementation of 3D snap rounding. But it is too slow and the size of the output is too large to be usable on fine grids, which is the pratical problem since we want to round the coordinates with a fine precision such as floats or double. To have a usable algorithm, we designed and began to implement a lazy algorithm that makes trivial rounds where possible and runs the fancy algorithm only where necessary.

The perspectives are to test all improvements present in the section 5 5.

Figure 1 :

 1 Figure 1: Example of intersection of four icosahedra. Image from Zhou et al. 2016 [17].

Figure 2 :

 2 Figure 2: Example of necessary collapsing if the Hausdorff distance is bounded.

Figure 3 :

 3 Figure 3: Input of segments for 2D snap.Figure4: We label hot all pixels that contain an endpoint of a segment or an intersection.

Figure 6 :

 6 Figure 6: We can round safely.

Figure 7 :

 7 Figure 7: Subdividing faces to avoid vertex-face traversing requires creating new edges that can induce new intersections.

Step 1 :

 1 Collapse the faces that are close to one another • Step 2: Partition the space into yz-parallel slabs • Step 3: Triangulate the faces • Step 4: Round all vertices to their voxels centers We detail each of them below. In what follows , the xy-plane is named the floor and the xz-plane is named the backwall.

Figure 8 :

 8 Figure 8: Projection of Step 1, the red part is the projected part, the orange parts are walls created to keep the projection of F i connected.

Figure 9 :

 9 Figure 9: Example of step 1 projection in 3D.

Figure 10 :

 10 Figure 10: Floor projection of the 3D faces and lift of the facets of the floor arrangement on the 3D faces.

Figure 11 :

 11 Figure 11: Representation of thick and thin slabs.Figure 12: Cut faces by the walls between slabs.

Figure 12 :

 12 Figure 11: Representation of thick and thin slabs.Figure 12: Cut faces by the walls between slabs.

  (a) Faces in a thin slab. (b) Some vertices are created by the projection and 2D snap in the middle plane.(c) We lift these vertices on their original edges.

Figure 13 :

 13 Figure 13: Step 3a.

Figure 14 :

 14 Figure 14: Faces in a thick slab.Figure 15: We triangulate faces by top-left to bottom-right diagonals.

Figure 15 :

 15 Figure 14: Faces in a thick slab.Figure 15: We triangulate faces by top-left to bottom-right diagonals.

Figure 16 :

 16 Figure 16: Trapeze triangulations with vertices induced by adjacent thin slabs.Figure17: We can round safely.

Step 1 :

 1 we can do Step 1 by considering the arrangement on the backwall and lift it back. If we have O(n) supporting lines in the input, we have O(n) lines on the backwall and each line can be lifted onto O(n) faces so we have after this step at most O(n 2 ) lines in the scene.

Figure 18 :

 18 Figure 18: Representation of the halfedge Data Structure. Image from CGAL Documentation [16].

Figure 19 :

 19 Figure 19: Factor acceleration of our implementation compared to CGAL implementation. The input is n random segments of length O( √ n).

Figure 20 :

 20 Figure 20: Factor acceleration of our implementation compared to CGAL implementation. The input is n random segments of length O(1).

Figure 22 :

 22 Figure 22: We calculate the intersections of plane A with plane B ±  and of plane A ±  with plane B . Then we cut A and B by these 2 lines.

Figure 23 :

 23 Figure 23: After Step 2, we project the faces in thick slab.

Figure 24 :

 24 Figure 24: The only 2 possible cases of faces projection on the back wall inside a thick slab.

Figure 25 :

 25 Figure 25: (a) We color segments by the indexes of the adjacent faces (here segments have only one adjacent triangle). (b) (c) For the blue triangle, we color the facet adjacent to the remember segment. (d) (e) (f) If an edge of the boundary doesn't have the same color as the facet considered, we color the facet on the other side and repeat for this facet.

Figure 26 :

 26 Figure 26: (a) We want to cut a face by walls of slabs. (b) We start from the left vertex, and we target the wall on right of this vertex.(c) (d) (g) We were going to go through the edges clockwise.(e) (f) (h) If the edge goes from left to right, and if it crosses the target wall, we split the edge, stack the created vertex and target the next wall.(i) (m) If the edge goes from right to left, we target the previous wall.(j) (l) (n) If it crosses the target wall, we split the edge, target the previous wall and (k) (l) (o) we link the created vertex with the top of the stack.

Figure 27 :

 27 Figure 27: Test of the algorithm on a plane. The output has a voxelated appearance.

Figure 28 :

 28 Figure 28: Number of vertices of the Backwall Arrangement function of number of vertices of the input in log-log scale. The points are noisy but we interpolate a line with slipe of 1.13 and value on 0 of 2.15 so we have y = 10 b * x a = 141n 1.13.

Figure 29 :

 29 Figure 29: (a) For a scene. (b) We find some problematic elements. (c) They are isolated in work slabs. (d) We cut through the slab walls and triangulate the faces. (e) (f) If there is a problem with the new edges, go back, double the width of work slabs and try again. (g) (h) If there are no problems, we make the heavy algorithm in work slabs and trivial rounding on the outside.

Figure 30 :

 30 Figure 30: Example where exact computations is always needed.

Figure 31 :

 31 Figure 31: A way to avoid exact computation.

C Manage degeneration created by Step 1

This algo works well but does not support some degenerated cases. However, Step 1 can create this kind of degenerate case.

The first degenerate case is that of projected faces where we have 2 faces geometrically identical but combinatorically disjoint. To avoid problems, we make a symbolic pertubation on z of projected faces. The coordinates are always carried by vertices, so to make the symbolic perturbation, we simply add an integer attribute to the vertices that represent the symbolic pertubation on z (this pertubation is only used during the lifting step).

The second degenerate case is that of vertical faces created on walls between slabs. These faces are projected onto segments. To do this, for all segments of the 2D arrangement that have the colors of these faces, we cut the faces by the vertical lines that start from the end of these segments.

With this, we have a good implementation of Step 2 that support the degenerations produce by Step 1.