P.-L Manteaux

C Wojtan
email: wojtan@ist.ac.at§narain@umn.edu

R Narain

S Redon

F Faure

M.-P Cani

Adaptive Physically-Based Models in Computer Graphics

Keywords: (according to ACM CCS): I, 3, 7 [Computer Graphics]: Computer Graphics-Three-Dimensional Graphics and Realism-Animation adaptivity, physically-based animation

One of the major challenges in physically-based modeling is making simulations efficient. Adaptive models provide an essential solution to these efficiency goals. These models are able to self-adapt in space and time, attempting to provide the best possible compromise between accuracy and speed. This survey reviews the adaptive solutions proposed so far in computer graphics. Models are classified according to the strategy they use for adaptation, from time-stepping and freezing techniques to geometric adaptivity in the form of structured grids, meshes, and particles. Applications range from fluids, through deformable bodies, to articulated solids.

Introduction

The ability of physically-based animation to generate highly complex and realistic motion, as well as react to unpredictable input, has made it increasingly indispensable in movies, video games and simulators since its introduction in 1987 by Terzopoulos et al. [START_REF] Terzopoulos | Elastically deformable models[END_REF]. Complex real-world behaviors exhibit multiscale phenomena in space and time. Sophisticated physical models involving a tremendous number of degrees of freedom are required to accurately reproduce these phenomena. This comes at a high memory and computational price, thus practitioners and researchers have been striving to achieve good trade-offs between accuracy and computational resources. This is especially relevant in computer graphics, where visual plausibility is the main quality criterion, and high-resolution results with rich details are sought. Trade-offs are typically obtained by carefully choosing the constitutive laws of the modeled objects, while Figure 1: Taxonomy of adaptive physically-based models in Computer Graphics. In this report, we discuss in detail the two most widely used adaptive techniques: Temporal adaptivity in Section 2 and geometric adaptivity in Section 3. We also discuss less common spatial adaptive techniques that proved to be very promising: Basis refinement in Section 4.1, moving grids in Section 4.2 and mixed models in Section 4.3.

21

In general, the CFL condition typically takes the form

C ≡ c∆t ∆x ≤ Cmax, (1)
where c is the speed of information propagation, and Cmax In smoothed particle hydrodynamics (SPH), each particle is affected by other particles within its smoothing radius h, analogous to the grid separation ∆x in finite-difference methods. Consequently, time step selection criteria based on the CFL condition can be applied. For pressure waves in compressible SPH, we continue to have

∆t ≤ Cmax h c , (2)
and values of Cmax between 0.25 and 0.4 have been used [START_REF] Monaghan | Smoothed particle hydrodynamics[END_REF]DC99]. Fast relative motion of particles, which occurs especially during fluid-fluid or fluid-solid collisions, can also produce artifacts due to interactions not considered in (2). Therefore, one can introduce additional time step constraints based on the instantaneous acceleration a and divergence of velocity ∇ • v [Mon92, DC99]:

∆t ≤ Λ h a , (3)
∆t ≤ Γ |∇ • v| . (4)
Λ and Γ are dimensionless constants which Desbrun et al.

41

[DC99] set to 0.5 and 0.005 respectively. Equation (3) can 42 in fact be interpreted as a CFL-type condition comparing the 43 size of the spatial neighborhood, h, to a particle's relative 44 displacement 1 2 a ∆t 2 due to acceleration over time ∆t. Fi-45 nally, we also point out that these criteria (2)-(4) may either 46 be applied globally by taking the minimum of all particles' 47 allowed time steps, or locally on a per-particle basis (as we 48 discuss below).

49

When adapting the time step based on higher-order deriva-50 tives such as acceleration (3), care must be taken because 51 such quantities can be much noisier than the system vari- which can be seen as a freezing technique and is discussed in Section 2.2. Bargteil et al. [BWHT07] simulate plastic flow using a finite element mesh, where excessive deformation of elements can be problematic. They reject a time step if any edge changes significantly in length, or a sudden acceleration takes place. Both methods discussed here use α = 2, that is, time steps are halved or doubled as needed.

The main drawback of this a posteriori strategy is that the whole system must be globally rolled back to its previous safe state, even if it was caused by a localized event. In rigid bodies simulation, this challenge was adressed by Mir- gorithm to asynchronously handle collision events. Here, the integration of a rigid body is interupted only when resolving an event that concerns it. This technique can be seen as a local time stepping technique, and inspired works on asynchronous variational integrators (AVIs) which we discuss later in this section.

Global time stepping

The simplest way to perform adaptive time stepping is to choose the time step that is safe for the entire simulation domain, and perform integration for the entire system using that time step. That is to say, given a time step criterion (or criteria) such as (2)-(4) that can be evaluated locally, one evaluates the permissible time step ∆t i at all simulation points i, and steps the entire system forward by a time step of length ∆t = min i ∆t i . For methods that use implicit integration or other globally coupled schemes, such as grid-based fluids with a global pressure solve, this is typically the only possible approach. For this reason as well as for its conceptual and practical simplicity, global time stepping is probably the most widely used form of temporal adaptivity in practice.

It is worth pointing out here that adaptive time stepping is not a free lunch for all time integration schemes. The Verlet, or leapfrog, scheme is second-order accurate, and has excellent energy conservation properties thanks to its symplectic nature, but both these features rely on the time step being fixed. To maintain second-order accuracy with a variable time step, Bridson et al. [BMF03] proposed a time integration scheme that combines a leapfrog scheme for position with an implicit trapezoidal rule for velocity:

1: ṽn+1/2 = v n + ∆t 2 a(t n , x n , ṽn+1/2 ) ⊲ implicit 2: x n+1 = x n + ∆t ṽn+1/2 ⊲ explicit 3: v n+1/2 = v n + ∆t 2 a(t n , x n , v n ) ⊲ explicit 4: v n+1 = v n+1/2 + ∆t 2 a(t n+1 , x n+1 , v n+1 ) ⊲ implicit
Maintaining symplecticity is much more challenging, as

71

Explicit integration schemes can readily incorporate local time stepping. We illustrate this with a generic twodimensional system,

q ′ 1 (t) = f 1 t, q 1 (t), q 2 (t) , (5)
q ′ 2 (t) = f 2 t, q 1 (t), q 2 (t) . (6)
If at time t, q 2 requires a very small time step ∆t 2 , one can 72 still integrate q 1 with its own time step ∆t 1 , giving

73 q 1 (t + ∆t 1 ) = q 1 (t) + ∆t 1 f 1 t, q 1 (t), q 2 (t) . (7)
Meanwhile, as q 2 takes multiple steps to cover the same time 74 interval, it will require values of q 1 at intermediate times 75 t + ∆t 2 , t + 2∆t 2 , and so on; these can be linearly interpo-76 lated from q 1 (t) and q 1 (t + ∆t 1 ). Equivalently, to simplify 77 bookkeeping, one can take the same small time steps ∆t 2 for 78 both q 1 and q 2 , but only evaluate q ′ 1 at the first step and hold 79 it fixed until a time ∆t 1 has been covered. This approach has

∆t ≤ h ρ λ + 2µ ( 8
)
where h is a measure of the size of the element, such as its in- doing so adaptively, one can continue to use an inexpensive 56 explicit integration scheme for the remainder of the system.

57

In the finite element method, ill-shaped elements impose 58 severe restrictions on the allowed time step for explicit inte- propose an element-wise implicit-explicit (IMEX) scheme.

65

Here the same time step ∆t is used for the entire system, but 66 ill-shaped elements that would be unstable if explicitly inte- ), important computational resources are dedicated to solving contacts between the different objects of a scene. This process becomes unnecessarily expensive when stacking occurs and nothing moves. In these cases, freezing techniques prove to be useful for saving computational time without compromising the plausibility of the simulation.

Schmidl [START_REF] Schmidl | Optimization-based animation[END_REF] uses a heuristic based on kinetic energy to determine whether to freeze a body or not:

1 2 mv 2 + 1 2 ω T Iω < p 2 g 2m (9)
where v and ω respectively denote the linear and angular velocity of the rigid body of mass m and inertia tensor I, and pg = mg∆t is the momentum that the body accumulates during a time step ∆t from gravity. If condition (9) is fullfilled by the body during a user-defined number of consecutive time steps, then it is frozen. Note that a single frozen body by itself does not save computation time. Time is saved when multiple neighboring objects become frozen, as their contact forces no longer need to be computed. The only way for a frozen rigid body to be reactivated is when it receives a large impulse during a collision. Once it is reactivated, the information is propagated to all its direct neighbors and a

given number of indirect neighbors, potentially awakening them (see Figure 2a).

Freezing ticle with p as momentum, q as position, V (q) as potential 66 energy, m as mass and ρ a restraining function:

67 ṗ = - ∂V (q) ∂q q = m -1 [1 -ρ(p)]p - 1 2 p T m -1 ∂ρ(p) ∂p p (10)
The restraining function ρ(p) ∈ [0, 1] is a twice differen-

ṗ = - ∂V (q) ∂q q = m -1 p (11)
Whereas if ρ = 1 then the particle will still accumulate momentum but will remain still:

ṗ = - ∂V (q) ∂q q = 0 (12)
In this case, even if particles' momentum are still correctly computed, forces do not need to be recomputed as positions are held fixed. Therefore substantial computational time can be saved. Moreover, by using an incremental algorithm to update interaction forces, inactive particles with active neighbors can be efficiently updated while staying aware of their neighborhood. Finally, if 0 < ρ < 1 then the particle follows the interpolated dynamics of equation ( 10). The particle is then called transitive. Manteaux et al. [START_REF] Faure | Exploring the Use of Adaptively Restrained Particles for Graphics Simulations[END_REF] extend their work to SPH (see Figure 4) and to deformable model simulation, in order to better match computer graphics needs.

Geometric adaptivity

Geometric adaptivity describes various techniques that adapt the spatial resolution of a model by refining and coarsening its discretization. These techniques are also refered in the literature as adaptive spatial refinement. However, as they include coarsening as well, we adopted a more general term.

Geometric adaptive techniques have two major compo-

nents: a refinement criterion that determines where higher resolution is needed, and a refinement/coarsening scheme that modifies the discretization to match the desired resolution. Both physical and visual criteria have been employed in existing work, and we discuss them in more detail below. The refinement scheme itself essentially depends on the type of spatial discretization. In the following subsections, 29 we will deal with the three major kinds of discretization sep-

e = A j (x j -P j x j+1 ) , (13)
and perform refinement if e exceeds a predefined threshold.

32 33 ωmax ≈ 2(n + 1) f mL , ( 14
)
where f is the tension in the wire and m and L are its mass where ℓ min is a user-specified refinement limit. This ap-

76 Df = (u • ∇)u ν∇ 2 u , ( 16
)
where u is the fluid's velocity field and ν is its viscosity. highly plastic materials while efficiently remeshing whenever element quality degrades (See Figure 6). Batty et al. their method on the evaluation of each particle neighbor's density. This evaluation is performed using a weighted covariance matrix computed in rest space for each particle i, where u i j denotes the vector between particle i and particle j, its neighbor.

39

B i = ∑ j u i j u T i j u i j 4 (18)
If the maximum eigenvalue of B i is too small, then there

Miscellaneous techniques for spatial adaptivity

By far the most popular approach to spatial adaptivity in computer graphics is to add more computational elements where more accuracy or detail is desired, as surveyed in Section 3. This type of spatial adaptivity is often called h-refinement, because the length of an edge in a mesh is typically indicated by the letter h. In addition to this triedand-true strategy, there are other fundamentally different approaches for achieving spatial adaptivity. In the next sections, we will discuss strategies that refine the basis within a single element (a superset of p-refinement, which refers specifically to the order of a polynomial basis) and during a subspace simulation, strategies that use multiple grids that move and overlap to track locations where more detail is desired, and strategies that mix different reference frames in order to use the computational degrees of freedom optimally.

Basis refinement

If we wish to achieve spatial adaptivity without explicitly remeshing (perhaps because it is difficult to control element quality when re-meshing, or because a particular application requires that we preserve the original mesh), then we can perform basis refinement instead. The concept of basis refinement can be a difficult one to grasp for newcomers to the field. One of the best ways to understand basis refinement is in the context of finite element methods (FEM). In In fact, it is quite surprising that this method was not more studied or extended in the last decade. A possible explanation is the fact that, in the last few years, adaptivity proved to be essential for large and complex deformations such as visco-elastic, visco-plastic flows. In those cases, hierarchical refinement is not sufficient anymore to ensure wellconditioning of the system matrices.

Polynomial basis refinement Polynomial basis refinement methods, also called p-adaptivity, increase or decrease the order of the basis functions. For a given spatial resolution, this allows to improve the quality of the deformation without remeshing. In computer graphics, using high order approximation to resolve fine details is not new. However mixing dif- re-meshing by inserting a fracture directly into the basis it-

1 self.

  domains makes it difficult to sort. Rather than iterating on 1 the different subdomains of physically based computer ani-2 mation (rigid bodies, deformable solids, liquids, smoke, etc.) 3 to present their adaptive approaches, we have chosen to re-4 view the different families of adaptive methods, and present 5 the way they have been applied in the different domains. We 6 hope that this organization will give the reader a broader 7 picture of adaptivity, by showing how variations of each ap-8 proach have been developed in different domains. 9 In Section 2, we present time adaptive techniques such as 10 dynamic time stepping and freezing techniques. Then, we fo-11 cus on spatially adaptive techniques. Section 3 discusses the 12 most popular approach of spatial adaptivity: geometric adap-13 tivity(h-adaptivity where h classically refers to the size of el-14 ements in the finite element method), which refers to varying grid cells (separated by ∆x), the CFL condition requires that 20 c∆t ≤ ∆x.

22

  is a method-dependent constant which depends on the size 23 of the finite-difference stencils. The dimensionless ratio C 24 is known as the CFL number or the Courant number. Note 25 that implicit methods are not restricted by the CFL condi-26 tion because the solution at any point at the end of the time 27 step depends on the values at all the points at the beginning 28 of the time step, so the numerical domain of dependence is 29 effectively infinite. 30 The CFL condition can be a useful heuristic even in situ-31 ations where it does not directly apply. In computer graph-32 ics, semi-Lagrangian advection [Sta99] has been a popu-33 lar scheme for solving the advection equation, as it is un-34 conditionally stable and not restricted by the CFL condi-35 tion [Bri08]. Nevertheless, excessively large time steps can 36 lead to undesirable artifacts such as numerical dissipation 37 and volume loss. Foster and Fedkiw [FF01] advocate limiting the time step size using (1) with c being the maximum 39 of the flow speed u ∞ over the domain, and Cmax = 5.

52

  ables themselves, causing large fluctuations in ∆t. Ihmsen 53 et al. [IAGT10] have observed that in incompressible SPH 54 simulations, these time step fluctuations can lead to spurious 55 density shocks that destroy the convergence of the simula-56 tion. A solution is to change ∆t gradually rather than instan-57 taneously: if the system violates any of the desired time step 58 criteria, ∆t is decreased by a small amount ( [IAGT10] use 59 0.2%), otherwise, if it is well within all the criteria, ∆t is 60 increased by the same amount. This strategy causes the time 61 step to change smoothly towards the ideal step length. On the 62 other hand, it may also prevent the time step from changing 63 quickly enough to resolve sudden shocks, such as those from 64 high-velocity impacts. Therefore, Ihmsen et al. introduce an 65 additional procedure that detects shocks if the density error 66 increases suddenly; if so, the simulation is rewound two time 67 steps and resumed with a sufficiently small ∆t. 68 Shock detection can be considered an example of an a 69 posteriori time step adaptation strategy, where undesirably 70 large time steps are detected and rewound. This kind of ap-71 proach is useful whenever it is costly or difficult to estimate 72 the right time step length in advance. Instead, we simply per-73 form a time step with the current estimate of ∆t, and then 74 test whether it adequately resolves the motion of the system. 75 If not, we reject the step, decrease the time step by setting 76 ∆t ← ∆t/α for some factor α > 1, and try again. When sev-77 eral time steps in a row are successful, we increase the time 78 step, ∆t ← α∆t. 79 Bridson et al. [BFA02] use this approach for efficient col-80 lision handling in cloth simulation, using a combination of 81 inelastic repulsion forces and a robust collision resolution 82 algorithm. Inelastic repulsions are much more inexpensive 83 than full collision resolution, but as they only check proximity at discrete points in time, they can easily fail to prevent interpenetrations if the cloth moves too far in a single time step. If this happens, the time step is rejected and ∆t is reduced; collision resolution is only triggered if after multiple failures the time step falls to a specified minimum size. The collision resolution step incorporates rigid impact zones [Pro97],

  tich [Mir00] to efficiently handle collisions. Inspired by the work of Jefferson et al. [Jef85], he proposed a time warp al-

  91 radius: skinnier elements or stiffer materials require smaller 92 time steps. To improve the parallelizability of local time step-93 ping for SPH fluids, Goswami and Batty [GB14] divide the 94 computational domain into blocks and choose time steps in-95 dependently per block.

  59 gration (8). When the object undergoes topological changes 60 such as cutting or fracture, it can be difficult to avoid in-61 troducing such elements. As an alternative to local time 62 stepping, where ill-shaped elements would have to be sim-63 ulated with extremely small time steps, Fierz et al. [FSH11] 64

67Figure 2 :

 2 Figure 2: Freezing techniques applied to rigid bodies stacking. At the stage of contact solving, those methods can save computational time while ensuring a plausible motion. In (a), quiescent rigid bodies are frozen (in hatched red) in a stacking configuration. A collision event then awakes one of the rigid bodies, and the active rigid body (in blue) propagates the information to its neighbors. In (b), a contact graph stores stack ordering. During shock propagation, a bottom-up traversal is performed and objects at each level are frozen by assigning an infinite mass. vation process of the frozen degrees of freedom that ensures plausible subsequent motion. In rigid objects simulation (see the survey of Bender et al. [BETC12]), important computational resources are dedi-

68Figure 4 :

 4 Figure 4: (a) shows a classic SPH simulation of a 2D scenario with inflow and outflow boundary conditions at the walls above a chasm. (b) shows at the same time the effect of the ARPS method from Manteaux et al. [MFRC13]. Blue particles are active, red particles are inactive, and green particles are transitive. Large regions quickly become inactive (c), allowing to save significant computational time as numerous particles' neighborhoods do not need to be updated anymore. sical equation of motion:

  30 arately: structured meshes and grids, unstructured meshes, 31 and meshless models. 32 Refinement criteria The choice of refinement criteria plays 33 a major role in the quality of the resulting simulation. Many 34 techniques use simple heuristics such as the distance to 35 boundaries, surface curvature, and the presence of contacts. 36 However, some authors have shown that employing criteria 37 that are more closely tied to the dynamics of the system can 38 be important in many contexts. 39 In elastic and plastic solids, the stress and strain in an el-40 ement characterize the amount of local deformation. There-41 fore, the values and gradients of these quantities are often 42 used to control refinement. Wu et al. [WDGT01] describe 43 several different error estimators of this type and discuss 44 their relative advantages, drawbacks, and performance. Go-45 ing beyond estimating a scalar error, Wicke et al. [WRK * 10] 46 define a metric tensor M that approximates the spatial vari-47 ation of strain by comparing deformation gradients of adja-48 cent elements. The matrix M is defined in such a way that 49 it has large eigenvalues in directions in which the deforma-50 tion changes most rapidly, and can thus be used to control 51 anisotropic refinement (see Figure 5). 52 If a multigrid algorithm is used, the difference between 53 the solution at the current level, x j , and the one prolonged 54 from the next coarser level, P j x j+1 , provides a natural mea-55 sure of the quality of x j+1 . Otaduy et al. [OGRG07] weigh 56 the error by the local system matrix A to reduce possible 57 popping in stiff scenarios, leading to the error metric 58

59Figure 5 :

 5 Figure 5: Elastoplastic simulation with dynamic local remeshing [WRK * 10]. By using the strain gradient as the refinement criterion, regions undergoing severe deformation are refined locally.

34

  and length. Requiring this frequency to be lower than 1/∆t 35 gives an upper bound on n for each wire.36In fracture simulation, the stress forms a singularity at 37 the crack tip, which must be resolved accurately with a fine 38 resolution mesh for realistic crack paths to be obtained. If 39 the crack origin is known a priori, one can track the crack 40 path as the fracture proceeds and refine the mesh based on 41 the distance from the crack [BDW13]. However, if fracture 42 is allowed to originate anywhere, it is necessary to refine 43 the mesh wherever stress is sufficiently high, i.e. close to 44 the material's strength τ, because such regions may generate 45 new cracks. Koschier et al. [KLB14] refine elements whose 46 tensile stress σ exceeds a specified fraction of τ. Pfaff et 47 al. [PNdJO14] choose the desired resolution of the mesh to 48 be proportional to tensile stress by requiring the length of 49 each edge e to satisfy 50 e ≤ max τ 2σ, 1 ℓ min(15)

  51proach allows the mesh to be coarsened again after the crack 52 tip has passed. 53 It is also possible to perform view-dependent adaptivity 54 by modulating the refinement criteria based on visibility and 55 distance from the camera. Such techniques have been ap-56 plied to the simulation of wires [SLN08] and cloth [KNO14]. 57 New issues arise in such contexts, such as preventing ar-58 tifacts when coarser regions come into the field of view 59 and must be refined: Koh et al. [KNO14] achieve this by 60 smoothly increasing the resolution in advance based on the 61 known camera path. 62 Many adaptive methods for simulation of liquids have re-63 lied on the distance to the free surface as the sole refinement 64 criterion. However, much greater adaptivity is possible by 65 observing that in regions where the surface is flat and does 66 not exhibit detailed motion, it can also be coarsened without 67 significantly affecting the flow. Adams et al. [APKG07] pro-68 pose a purely geometrical criterion based on an "extended 69 local feature size" which measures the distance to the sur-70 face and to the medial axis of the fluid volume. This criterion 71 assigns coarse resolution both far from the surface and near 72 thick, flat surfaces. However, it does not take the motion of 73 the fluid into account. To detect regions with significant flow 74 detail, Hong et al. [HHK08] use a "deformation factor" that 75 locally estimates the Reynolds number,

77

  Ando et al. [ATW13] use a flexible sizing function that com-78 bine multiple criteria to set the desired resolution. Among 79 them the depth of the liquid, the camera viewpoint, the fluid

65

  Figure 6: A high resolution surface mesh (blue) embedded into a deforming low resolution spatially-adaptive tetrahedral mesh based on a BCC lattice (gold). The bottom row shows the cross section of the tetrahedral mesh, illustrating the BCC structure. Image from Wojtan and Turk [WT08].

[Figure 7 :

 7 schemes are illustrated in Figure7a, 7b. In cloth simu-71

Figure 8 :Figure 9 :

 89 Figure 8: The anisotropic remeshing algorithm of Narain et al. [NSO12] allows detailed wrinkles in cloth to be resolved accurately with fine elements (red), while much coarser elements (blue/green) are used in flat regions. Long, narrow folds are best represented using anisotropic elements (yellow) aligned with the curvature direction.For manifold triangle meshes, high-quality remeshing can be accomplished using only the three simple operations of edge split, edge collapse, and edge flip (see Figure7d). Narain et al. [NSO12] use these operations in cloth simulation, generating an adaptive anisotropic mesh that resolves detailed wrinkles and folds (see Figure 8). First, all edges that are unacceptably long according to the refinement criterion are split, then edge collapses are attempted as long as they do not create new unacceptable edges. During both steps, edge flips are performed to maintain an approximately Delaunay mesh relative to the anisotropic metric. Local remeshing of tetrahedral meshes is significantly more involved, requiring several different local operations and a complex schedule for the order in which to apply them [KS07]. This technique was first applied to simulation by Wicke et al. [WRK * 10], who used it to minimize artificial diffusion in elastoplastic flow. Subsequent work has applied such remeshing techniques to simulation of incompressible liquids [MB12, MEB * 12, CWSO13]. Misztal et al. [MB12, MEB * 12] build a mesh over the entire simulation domain, with some elements belonging to the fluid and the rest to the exterior, while Clausen et al. [CWSO13] mesh only the fluid volume. The former approach allows topological changes like collisions to be handled automatically without special treatment, although at the cost of maintaining a mesh over a potentially much larger domain. Clausen et al. also describe techniques for guaranteeing incompressibility and momentum conservation that are applicable to both approaches. Two key advantages offered by these methods are that (i) the advection step causes no numerical diffusion, because physical quantities move with the mesh nodes, and that (ii) surface tension can be modeled accurately thanks to an explicit surface representation tied directly to the simulation mesh. Apart from simply adding or removing vertices, surface

40

  are too few particles in the neighborhood and the particle 41 is split in two. New particles are positioned along each side 42 of the eigenvector with the minimum eigenvalue. In order 43 to prevent from rendering artifacts, splittings which are not 44 tangent to the surface are rejected, and particles near the sur-45 face are split along the middle eigenvector whose direction 46 is tangent to the surface. Conversely, if the minimum eigen-47 value of B i is too large, then there are too many particles in 48 the neighborhood and the particle is merged with its closest 49 neighbor. The new particle is positioned halfway between 50 the two merged particles. 51 Multiscale methods In multiscale methods, several simu-52 lations with different resolutions are coupled in a hierarchi-53 cal way (see Figure 9b). At the coarsest simulation level L 0 , 54 the whole domain is discretized. Then, each finer simulation 55 level Lr discretizes a subset of L r-1 with a finer scale. This 56 finer subset is defined to match regions of interests that can 57 be physically or visually motivated. Transitions between two 58 scales are bilateral: the coarsest simulation level Lr is used to 59 build boundary conditions for the finer simulation level L r+1 60 and feedbacks from a finer simulation level L r+1 to a coarser 61 simulation level Lr are applied, in order to prevent dynam-62 ics of two different levels from diverging. Solenthaler and 63 Gross [SG11] and Horvath and Solenthaler [HS13] apply 64 this idea to SPH fluid simulation. Compared to merging and 65 splitting particles, the main advantage is that interactions be-66 tween different resolutions are not direct anymore. Thus, sta-67 bility can be more easily ensured and large differences in res-68 olution can be handled. In Solenthaler and Gross's approach, 69 a two-scale simulation is performed. High-resolution regions 70 are defined based on the distance to the surface and the view 71 frustum. In these regions, low-resolution particles emit finer 72 particles according to a cubic pattern which ensures a uni-73 form space sampling. Relaxation steps are performed when 74 particles enter the high-resolution region in order to avoid 75 large pressure forces. Horvath and Solenthaler extend the 76 two-scale simulation to multiscale simulation, and avoid pre-77 vious artifacts such as mass loss due to particle removal and 78 instabilities due to oversampling near boundaries. 79 Hierarchical refinement Dynamic resampling techniques 80 were also used in frame-based methods to simulate elastic 81 deformations, see [GBFP11] for a full description of the 82 method. Tournier et al. [TNFG14] use a hierarchical ap-83 proach to achieve simplifications during deformation with-84 out popping artifacts (see Figure 9c). The material is de-85 formed using physically-based control frames organized in 86 a generalized hierarchy. The model can be simplified by at-87 taching frames to their parents at any time in their current rel-88 ative positions. Activation and deactivation of nodes is performed based on relative velocity and user-specified metrics, while integration points are updated according to the hierarchy. These hierarchical techniques take advantage of their structure to improve efficiency, but may lack of flexibility, especially regarding topological changes.

Figure 11 :Figure 12 :

 1112 Figure 11: Refinement by element subdivision is attractive by its simplicity for 2D and 3D meshes, however it introduces T-junctions (in red) at interface between resolutions with different sizes. Bookkeeping or extra-remeshing operations are required to take care of these non-independant degrees of freedom. Hierarchical basis refinement In computer graphics, hier-51

Figure 13 .Figure 13 :

 1313 Figure 13. This type of basis replacement effectively avoids 77

63

  of these drawbacks by adaptively improving the reduced ba-64 sis. Common components to those strategies are the differ-65 ent processes to update the basis and the criteria used to de-66 cide when the basis should be adapted. Moreover, a com-67 mon challenge is to ensure temporal coherence while adapt-68 ing the basis. Kim and James [KJ09] combine a full nonlin-69 ear simulation with subspace simulation in order to exploit 70 coherence in the global motion of the model. They incre-71 mentally build a reduced-order nonlinear deformable model 72 as the full nonlinear simulation progresses. When possible, 73 full nonlinear steps are skipped with subspace steps result-74 ing in significantly cheaper steps. The challenge of this strat-75 egy is to provide efficient operators to update the reduced-76 basis and to robustly choose which steps can be reduced. 77 We briefly describe the two main operations that compose 78 the incremental construction of the basis: the updating op-79 eration and the downdating operation. The updating opera-80 tion adds a new vector to the basis only if it is significant. 81 To do so, a displacement vector received from a full simu-82 lation step is orthogonalized against the existing basis. If its 83 norm is above a given threshold then it is concatenated to 84 the basis. The downdating operator is applied when the ba-85 sis reached its maximal size r and a new significant vector 86 needs to be added. The basis is then modified so that the 87 r/2 most significant directions are preserved. Finally, as the 88 cubature (reduced integration) is dependent on the basis, it 89 also needs to be updated. The updating operation is triggered 90 through different criteria depending on the application. Kim 91 and James describe criteria for quasistatic and dynamic sim-92 ulations. The dynamic case is particularly challenging as the 93 error is history dependent, which means that taking full steps 94 after reduced steps do not correct errors from the subspace 95 simulation. This method presents impressive speed up for nonlinear simulations. However, the performance is highly dependent of the rate of expansion of the basis. As subspace simulation tends to reproduce the global motion of an object, it is particularly challenging to produce very local deformations in this framework. A direct consequence is a simplification of the dynamic behavior. Harmon and Zorin [HZ13] tackle this problem by including a priori knowledge in the building of the basis. More precisely, they augment a standard precomputed basis with a dynamic basis. This dynamic basis is built with custom functions derived from analytic solutions to static load. Unpredictable local deformations that arise due to collisions and contacts can then be handled. Moreover, as the change in the basis is very local, they can ensure temporal coherence by projecting the current subspace coordinate vector into the new basis whenever it changes. However, a limitation of the addition of local modes is a restriction on the time step size in order to properly represent the dynamics. Furthermore, the size of local displacements is limited. Pushing further the idea of using a priori knowledge in the building of a reduced basis, Hahn et al. [HTC * 14] perform adaptive subspace simulation of cloth. They start with a large amount of high-resolution simulation data from multiple training animations, and convert it into a database of lowdimensional bases associated with poses. Then at each time step, they adaptively choose a subset of low-dimensional bases in the data base depending on the pose of a clothed character. Highly nonlinear folds and wrinkles, which typically are very hard problems for subspace simulation, can then be reproduced. Dynamics is damped near tightly constrained regions such as sleeves, but this may be acceptable in practice for animating tight clothing. Recently, Teng et al. [TMDK15] propose the use of subspace condensation to locally switch between subspace and fullspace simulation at run time. When dealing with localized deformations, this allows the behavior not to be limited by a priori knowledge such as in [HZ13] and [HTC * 14].4.2. Moving gridsAs mentioned in Section (3.1), grids are an efficient and simple data structure compared to unstructured meshes. However, this simplicity is counterbalanced by a severe lack of flexibility. Firstly, simulating fluids on very large domains requires a prohibitive amount of memory. Secondly, focusing computational resources on regions of interest remains a challenge. While octrees and other adaptive structured meshes discussed in Section 3.1 address these challenges, they lose the cache-coherent structure that makes uniform grids so efficient. Moving grids methods, also called Chimera grids, allow more flexibility while keeping the advantages of Cartesian grids. The main idea is to use one or more computational grids and allow them to move at each time step to follow the region(s) of interest.

19

  Combining 2D & 3D Several techniques like discretizing the shallow water equations [LvdP02,HHL * 05] or linearized wave equations [KM90,[START_REF] Tessendorf | Interactive water surfaces[END_REF] KB14] are useful for reducing computational degrees of freedom, but we do not believe they are inherently adaptive by themselves, and we do not discuss them in detail in this document. However, several techniques utilize these 2D discretizations in ways that we would classify as an adaptive "mixed-model" approach.The work of Thürey et al. [TRS06] combines a 3D Lattice-Boltzmann simulation with a 2D simulation of the shallow water equations, allowing a local region that to adapt to 3D phenomena while distant motion remains a simple height field. Chentanez et al.[START_REF] Chentanez | Coupling 3D Eulerian, Heightfield and Particle Methods for Interactive Simulation of Large Scale Liquid Phenomena[END_REF] combine a 3D Eulerian solver with both a 2D shallow water solver and a particlebased fluid simulation. Mixing three models allows them to simulate extremely detailed water interactions at efficient frame rates. These methods fit our definition of adaptivity, because they both locally increase the computational degrees of freedom in interesting regions, and these decisions of where to place the new degrees of freedom are decided at run-time as the simulation progresses. As these papers suggest, adaptively switching simulation dimensions will clearly make animations more efficient, because the computational complexity plummets as the simulation transitions from 3D to 2D. The only reservations here are that there is a significant implementation expense to maintaining two or more solvers (one for each dimension), and the seamless coupling between dimensions is a sensitive process that is still being actively researched.5. DiscussionAdaptive physically-based models are becoming ubiquitous in computer graphics. In the last decade, various techniques for almost all types of deformable models have been proposed and extended. In this survey, we have classified adaptive techniques into five different categories: (1) temporal adaptivity, (2) geoemtric adaptivity, (3) basis refinement, (4) moving grids and (5) mixed models. For each category, we have described the variants that were developed for different applications and have discussed their strengths and weaknesses. Among those different categories, geometric adaptive techniques are the most studied, and are perhaps the most in-53 tuitive due to their geometrical nature. The many variations 54 in application contexts such as dimensionality and discretiza-55 tion have led to a proliferation of different innovative tech-56 niques. Yet, as we have tried to show, there are also many 57 commonalities between aspects of disparate techniques, for 58 example in terms of refinement criteria, and there is potential 59 for consolidation of the many approaches in this area. 60 In the opposite direction, mixed models represent an im-61 portant area of work. Unfortunately, as they rely on the spe-62 cific characteristics of each model, it is more difficult to ex-63 tract general patterns and strategies. Even so, they perfectly 64 represent the idea and the versatility of adaptive techniques 65 by combining the strengths of different approaches as the 66 simulation evolves. 67 For now, polynomial basis refinement represents only a 68 small fraction of the methods studied. In computer graphics, 69 this is a very recent topic, but which can build on strong foun-70 dations from engineering and applied mathematics where it 71 has been extensively studied. Results in solid and fluid sim-72 ulation show that polynomial basis refinement can indeed 73 produce impressive animations. One of the most exciting av-74 enues of future research is the combination of this technique 75 with geometric adaptivity. 76 In subspace simulation, adaptive reduced bases can 77 greatly extend the range of deformation that can be achieved 78 by introducing local and non-linear deformations such as 79 wrinkles. Nevertheless, there is still a large room for im-80 provement and innovation, especially regarding the possibil-81 ity to handle topological changes and couple different sub-82 space simulations such as deformable solids and fluids. 83 Even if there are only a few works that focus on temporal 84 adaptivity, these methods are widely used and play a crucial 85 role in ensuring stability and efficiency. Their importance is 86 due to two main reasons. First, spatial and temporal resolu-87 tion are often strongly related. Secondly, the necessary tem-88 poral resolution is inherently dependent on the events occur-89 ring during a simulation and cannot always be predicted in 90 advance, necessitating adaptive techniques. As we seek to 91 resolve details at increasingly finer time scales, further re-92 search will be required to capture them without paying an 93 exorbitant computational cost. 94 Adaptive methods are not without limitations, and we 95 briefly summarize the major ones. At present, setting up 96 a new adaptive method is quite difficult: adaptive methods 97 have often been application-specific so far, which makes the 98 study of existing solutions quite intricate. Adaptivity usu-99 ally makes the implementation of a model much more com-100 plex and may ruin the regularity of computations, causing 101 incompatibilities with GPU implementations. Evaluating the 102 future overhead due to the online adaptation process is of-103 ten difficult, which may make such techniques unusable in 104 performance-constrained contexts such as interactive appli-105 cations. There are also potential concerns relating to simula-tion fidelity. If not tackled with care, popping between differ-1 ent spatial and temporal resolutions may cause instabilities 2 and visual artifacts. Furthermore, the energy diffusion that 3 necessarily occurs when permanently adapting a model may 4 be an issue when an accurate simulation is required. 5 Nevertheless, the space of adaptive simulation techniques 6 is vast and fruitful, and many compelling benefits have been 7 uncovered so far. There is much room for future work in 8 developing new adaptive methods which are both easier to 9 implement and still generic enough to be used in different 10 applications. This challenge requires methods which, for ex-11 ample, minimize the overhead due to additional structures 12 while making it possible to integrate different adaptation cri-13 teria. Many other avenues of future research remain, includ-14 ing combinations of different forms of adaptivity and tech-15 niques that adapt between different dimensionalities, differ-16 ent formulations, and other characteristics that have tradi-This work was partly supported by the starting grants 20 ADAPT and BigSplash, as well as the advanced grant EX-21 PRESSIVE from the European Research Council (ERC-22 2012-StG_20111012, ERC-2014-StG_638176 , and ERC-23 2011-ADG_20110209).

  View-dependent dynamics of articulated bodies. Top: the algorithm proposed by Kim et al. [KRK08a] automatically simplifies the dynamics of a falling character as its distance to the viewer increases. Bottom: corresponding rigidification at this time step (one color per rigid group). weight matrices, and d Ji is the number of degrees of freedom of joint i in C. The weight matrices A i are required to depend at most on joint positions, and the simplest choice is the identity matrix. The key to the sub-linear complex-

	techniques have been used as a failsafe pro-Figure 3: ity is the demonstration that the acceleration metric of each sub-articulated body is a quadratic function of the forces applied to its handles (i.e. the free rigid bodies used to as-semble sub-articulated bodies in Featherstone's methodol-ogy [RGL05]). As a result, the acceleration metric may be computed before computing the joint accelerations them-selves. This is used during the top-down pass of Feather-stone's divide-and-conquer algorithm to determine which joint accelerations should be computed because they are suf-ficiently large [RGL05]. For example, if the acceleration metric of the complete articulated body is small, then all joint accelerations are small and joint velocities are constant for the current time step. A similar metric is built for joint velocities to determine which joint positions should remain constant, and thus which inter-body forces and inertial terms and cable route planning [KGL07]. sampling algorithm for highly articulated chains [GRS * 07] body method, which is used as the core of a physics-based perform contact handling with such an adaptive articulated-should be updated. Once all position-dependent terms are up to date, the motion metrics are available for the next time step, and a new set of active joints can be determined. It was shown that this approach could also help to speed up continuous collision detection for articulated bod-ies [KRK08a] and haptics rendering [MR07], as well as enable view-dependent articulated-body dynamics by com-bining motion metrics with visibility estimates [KRK08b] (see Figure 3). Gayle et al. [GLM06] demonstrate how to	34 35 40 41 42 43 44 36 45 37 46 38 47 39 48 40 41 42 43 44 45 46 47 48 49 49 50 51 52 53 54 55 56 57 50 51 52 53 54 55 56 57 58 63 62 61 60 59 58 59 60 61 62 63 64 65	ever, they also introduce loss of kinetic energy by treating contacts as fully inelastic, and are therefore only invoked as cles compute correct physical quantities. Computation time is saved for inactive particles that only have inactive neigh-bors. The main challenge in these methods is the definition of the process to transform a particle from the inactive set to the active one and vice versa. Indeed, as SPH is sensitive a last resort after multiple iterations of a physically correct to particle distribution, an inadequate transition of state can solver have failed to resolve the collisions. For rigid body directly lead to instabilities. Additionally, a judicious choice contact, Guendelman et al. [GBF03] propose a shock propa-of criterion to decide whether a particle should be active or gation strategy which freezes bodies progressively from the not is essential. ground up. They start by building a directed acyclic graph consisting of "levels" of objects that are resting on objects of lower levels (cyclic dependencies are grouped into the same level). A single bottom-up traversal of the graph re-solves contacts level by level, assigning infinite mass to lower-level objects for which contact is solved (see Figure 2b). Rigid impact zones, described by Provot [Pro97] and Bridson et al. [BFA02], are extensively used to resolve col-lisions in cloth. Nodes involved in multiple interfering colli-sions are collected into disjoint sets called "impact zones", Goswami and Pajarola [GP11] propose a simple method that evaluates the active status of particles at each time step. Particles are marked as active if they are close to the bound-ary or if their velocity exceeds a threshold. Inactive neigh-bors of such particles are also added to the active set, and continue with their last active velocity. All other particles are considered inactive. Unfortunately, the resulting method does not obey Newton's third law, resulting in some loss of momentum. constructed by merging zones if their nodes are involved in the same node-face or edge-edge collision. Each impact zone is rigidified by replacing the motion of its nodes with a rigid body motion while preserving the total linear and angu-lar momentum. This process eliminates collisions within the zone, but may introduce new collisions with nearby elements outside the zone. Therefore, one must perform collision de-tection again and grow the impact zones if new collisions are detected, iterating this process until no new collisions occur. Freezing techniques were also used for articulated rigid bodies, both for dynamics [RGL05] and quasi-statics [RL06]: joints are activated or deactivated based on user-defined error metrics, leading to a simplification of the whole model and a sub-linear computational complexity. In the context of molecular simulation, Artemova and Redon [AR12] propose a fundamentally different approach which ensures momentum conservation. This approach, called Adaptively Restrained Particle Simulation (ARPS), builds a modified equation of motion which adapts itself de-pending on the state of the particles. It continuously interpo-lates the behavior of a particle switching from one state to another. Here is the modified equation of motion for a par-
	cedure for resolving collisions and contact between rigid or deformable bodies. When many interacting contacts are present, iterative processes for collision response can require an excessively large number of iterations to converge, and early termination leaves the system in an interpenetrating state. Freezing procedures are attractive in this context as Recent work has sought to apply freezing techniques to accelerate SPH fluid simulation. In these methods, particles are divided into two sets: a set of active particles following a classical simulation step, and a set of inactive particles that are skipped in the simulation. As physical quantities in SPH are interpolated from neighbors, inactive neighbors of active	64 65 66	Denoting by qC = ( q1 , . . ., qNC ) T the composite acceler-ation of an articulated body C, where N C is the number of joints in C, the acceleration metric value of C is defined as qT i A i qi , A(C) = ∑ i∈C
	they can guarantee elimination of interpenetrations. How-particles also need to be updated to ensure that active parti-		where A i , i ∈ C, are symmetric, positive definite d Ji × d Ji

  Note that in this case, we opted to enrich the basis with

			43	The drawbacks are that the creation of the basis requires
			44	heavy precomputation, and that the motion of the model is
			45	constrained to lie in this basis. Furthermore, while the full
			46	finite element simulations often have local compact basis
			47	functions and sparse system matrices (because each degree
			48	of freedom is a vertex that only influences its neighbors lo-
			49	cally), reduced simulations tend to have global basis func-
			50	tions and dense system matrices (because each degree of
			51	freedom impacts all points in space simultaneously). Small
			52	dense systems are often more efficient than large sparse
			53	ones, but the increased storage requirement limits how many
			54	modes can be feasibly included in model-reduced simula-
			55	tions, and it limits the use of model reduction in settings
	2		56	where large numbers of modes are essential for visually-
	3 4 5 6 7 8	these particular "step" functions which drop to zero after a certain point, instead of trying to fit some polynomial that might overshoot or otherwise imperfectly capture the desired physics. Such basis enrichment techniques have been termed the "general finite element method" (GFEM) or "extended fi-nite element method" (XFEM) [BGV09].	57 58 59 60 61	plausible behavior (like cloth and fluids). Therefore model reduction is only truly efficient for smooth global deforma-tions and predictable scenarios where it is possible to build a basis that remains constant over time. It is also only useful in situations where a limited number of modes can adequately describe the system.
	9	Adaptive basis enrichment methods have been recently ap-
	10	plied in many computer graphics contexts. The virtual node
	11	algorithm uses basis enrichment to stabilize fracture and cut-
	12	ting simulations [MBF05, HJST13]. Instead of re-meshing
	13	and potentially inserting poorly-conditioned elements, the
	14	virtual node algorithm essentially copies the entire element
	15	and adapts its basis functions to the fracture site. The vir-
	16	tual node algorithm has recently been improved to robustly
	17	allow multiple cuts in a single element [SDF07, WJST14].
	18	One drawback to adaptive basis enrichment is that compli-
	19	cated cuts can require arbitrarily complicated basis func-
	20	tions that may not be simple to compute. In the case of cut-
	21	ting thin shells, Kaufmann and colleagues [KMB * 09] note
	22	that the most physically-appropriate enrichment functions re-
	23	quire the solution of a Laplace equation with time-varying
	24	boundary conditions. Similar basis enrichment techniques
	25	may not be computationally feasible for the adaptive sim-
	26	ulation of more complicated volumetric phenomena.
	27	Adaptive reduced bases As pointed out by Bargteil and
	28	Cohen [BC14], volumetric elastic effects are usually low-
	29	resolution in space, because we often care about longer
	30	time scales in computer graphics. Model reduction methods,
	31	also called subspace simulation, exploit this fact to turn ex-
	32	tremely costly nonlinear finite element simulations into inter-
	33	active ones. The idea is to solve equations of motion in a re-
	34	duced basis that is usually computed using modal analysis or
	35	from a database using principal component analysis (PCA).
	36	Thus, instead of having a complexity dependent on the simu-
	37	lation mesh resolution, it only depends on the size of the re-
	38	duced basis (the number of deformation modes) which is typ-
	39	ically much smaller. A cubature scheme is used to perform
	40	integration on only a reduced sets of well-chosen samples.
	41	In the end, this allows simulation of nonlinear deformable
	42	models with orders of magnitude speed-up.

62

Several strategies have been proposed to overcome some

  Shah et al. [SCP * 04] propose a simple approach in which 53 a single grid is used whose location and size changes to en-Eulerian simulation & SPH Eulerian methods can also be 102 combined with Lagrangian particles in other ways beyond 103 droplets and bubbles. Losasso et al. [LTKF08] combine SPH with a FLIP simulation, Wang et al. [WZKQ13] combine SPH with a Lattice-Boltzmann simulation and Chentanez et al. [CMK14] combine SPH with 3D Eulerian grid. This idea of adaptively switching between Eulerian simulations and SPH is still an active research topic. Using SPH instead of simple passive or ballistic particles is clearly more realistic, but it comes with the expense of additional neighborhood operations and more delicate numerical calculations in general. It is not clear yet whether the realism gained by augmenting an Eulerian simulation with SPH particles is worth the computational expense.

	1	4.3. Mixed models	52	complicated trajectories. However, Eulerian methods are of-
	2 3 4 5 6 7 8 9 10 11 12 13	Another important strategy for adaptively focusing compu-tation in computer animation is to selectively apply a mix-ture of different computational models. The motivation is that every model has its own strengths and weaknesses, and some are better suited to some situations than others. In par-ticular, many methods combine Eulerian reference frames (which describe motions relative to a fixed point in space) with Lagrangian reference frames (which describe motions relative to a physically important moving trajectory). The driving goal is to judiciously combine techniques in a way that leverages the strengths of each model and suffers none of the drawbacks.	54 55 56 57 58 59 60 61 62 63 64 65 53 54 55 56 57 58 59 60 61 62 63 64	close the region containing significant flow. This strategy is useful when there is only a single region of interest in the fluid, such as when simulating explosions. A more versatile approach is to use multiple indepen-dently moving grids, typically centered at each moving ob-ject in the scene. The grids may undergo pure translation [CTG10], or may also rotate with the object [DMYN08, EQYF13]; in the latter case, centrifugal and Coriolis forces may also need to be taken into account. A coarser back-ground grid can also be used to represent the global flow in the remainder of the domain not covered by any local grid. ten inferior to their Lagrangian counterparts when sampling fine individual features like droplets and bubbles, or for ex-plicitly tracking many individual vortices. This section describes many techniques that adaptively combine 2D/3D and Eulerian/Lagrangian techniques in or-der to get the most out of a fluid simulation. We first sur-vey various methods that combine Eulerian techniques with Lagrangian particles (droplets, bubbles, vortices, etc.). Next, we discuss how some Eulerian models also use Lagrangian particles to couple directly with SPH solvers. After that, we review some methods which combine 3D solvers with 2D techniques or with surface physics.
	14 15 16 17	While most of these mixed models represent a clever com-bination of techniques whose whole is greater than the sum of its parts, the mixed models which could not be classified as "adaptive" have been omitted from this paper. This section only discusses mixed models that adaptively change from	66 67 68 69 70 71 65 66 67 68	The major question that arises in these approaches is how to couple the degrees of freedom in regions where two or more grids overlap. For interactive smoke simulation, Cohen et al. [CTG10] omit the coupling step entirely. Instead, smoke particles that lie within multiple overlapping grids are simply advected Eulerian simulation & Lagrangian particles Several early methods combined Eulerian fluid simulations with La-grangian particles to animate splashing droplets. O'Brien and Hodgins [OH95] combine a 2D pipe-based fluid model with particle-based droplets. Holmberg and Wün-
			72	with a weighted average of the flow velocities indicated by
				different grids. The resulting motion is not physically valid,
	41
	42	the strands as normal. These models are "adaptive" under
	43	our definition, because the Eulerian nodes add local detail
	44	and their location is decided during run-time.	97 98	ulary, they belong to dynamic domain decomposition meth-
	45	4.3.2. Fluids	99 100 99	ods. These methods tackle with success the challenge of in-creasing the local accuracy of Cartesian grids methods while
	46 47 48	The large memory and computation requirements of 3D fluid discretizations are undesirable, so 2D simplifications are of-ten preferred when applicable. In addition, an Eulerian ref-	101 102 103 100	keeping their natural efficiency. However, while such meth-ods are extremely efficient for environments where regions of interests are known or easy to compute, they are not well cause the small expense of adding additional point geometry with simple physics pays off with enhanced visual realism.
	49	erence frame is popular for guaranteeing a uniform mesh-	104	suited for interactive scenarios where any number of new re-
	50	spacing, maintaining cache-coherence, avoiding remeshing,	105	gions of interest may pop up at any location and time, and
	51	and describing swirling flows without explicitly sampling		where adaptive particle simulation remain more appropriate.

73

but works well for interactive applications. 74 To perform correct coupling for globally incompressible 75 flow, there are two possible strategies: solve for incompress-76 ibility as usual in each grid and transfer data between them 77 in an outer loop, or build a single discretization that cou-78 ples all the grids together. Dobashi et al. [DMYN08] use 79 the former approach to efficiently simulate interaction be-80 tween smoke and rigid objects. Pressure is solved using a 81 modified Gauss-Seidel solver where each iteration follows 82 three steps. First, data from coarser grids is copied to the 83 boundary cells of finer grids for use as boundary conditions. 84 Then, pressure is computed independently on each grid. Fi-85 nally, data from the interior cells of finer grids is copied 86 to overlapping coarser grids. This process is repeated until 87 it converges; unfortunately, convergence can be slow. More 88 recently, English et al. [EQYF13] developed a full moving 89 Cartesian grids model. Instead of solving for pressure on 90 each grid separately, they combine all grids in a single dis-91 cretization. Coarse grid cells that contain the cell center of a 92 finer cell are removed, and a Voronoi mesh is built using the 93 remaining cell centers. An monolithic Poisson solver then 94 computes the pressure over the entire mesh. 95 In summary, moving grids are a good solution for accel-96 erating Eulerian fluid simulation. In the applied math vocab-18 one model to another when the situation calls for it. This sec-19 tion is separated into methods used to simulate solid objects 20 and methods used to simulate fluids. 21 We note that numerous other techniques use two-way cou-22 pling between different phenomena ([CMT04, RMSG * 08, 23 SSF08, RK13], to name a few). However, while these ap-24 proaches are adaptive in the sense that they modify com-25 putation depending on the phenomena being simulated, we 26 feel these two-way coupling methods are outside of the 27 scope of this report. Instead of surveying all possible combi-28 nations of different phenomena-specific discretizations, we 29 only discuss here methods that combine different discretiza-30 tions of the same phenomena in order to gain a computa-31 tional speedup.

32 4.3.1. Solids 33 While most mixed models for simulating solid dynamics 34 do not quite adapt their models to their environment, both 35 Sueda et al. [SJLP11] and Servin et al. [SLNB11] success-36 fully address the challenging problem of simulating stiff elas-37 tic strands in a collision-heavy scenario. They accomplished 38 this by introducing Eulerian nodes into a largely Lagrangian 39 strand simulation. The Eulerian nodes sit still at important 40 contact points, while the standard Lagrangian nodes sample 69 sche [HW04] create an Eulerian waterfall model and used 70 Lagrangian particles to animate spray, and Kim et al. 71 [KCC * 06] used particles from a 3D surface tracker to fill in 72 missing splash details. Chentanez and Müller [CM10] com-73 bine an Eulerian discretization of the shallow water equa-74 tions with a Lagrangian simulation of spray, splash, and 75 foam particles. The particles add important missing details 76 to the simulations and are allocated dynamically at run-time. 77 Researchers also use Lagrangian particles to capture bub-78 ble behavior in Eulerian simulations. Mould and Yang 79 [MY97] augment a height-field model with Lagrangian par-80 ticles for droplets and bubbles. Many simulation methods 81 [GH04,HLYK08,PAKF13] compute a 3D Eulerian fluid sim-82 ulation, and they represent bubbles that are too small to be 83 resolved on the grid with Lagrangian particles. The differ-84 ences in these methods lie in the varying bubble dynamics 85 and the subtleties of how to transition between the Eulerian 86 grid bubbles and the Lagrangian particle bubbles. 87 The main concept for these methods is to use an Eulerian 88 representation for the bulk of the flow, but to adaptively turn 89 to a Lagrangian particle representation whenever the Eule-90 rian model is insufficient. This switching point is often easy 91 to detect, because it occurs exactly when the diameter of a 92 water droplet or bubble falls below the Eulerian grid resolu-93 tion. Not only does this strategy conserve mass and momen-94 tum better than simply deleting small features, but it fills in 95 visually important information by animating sprays as a col-96 lection of small Lagrangian droplets and foams as a collec-97 tion of Lagrangian bubbles. Lagrangian droplets and bubbles 98 are practically indispensable in a production workflow, be-101


Daniel Barlet

Note on the quasi-proper direct image with value in a Banach analytic set

Keywords: AMS Classification, 32 H 02 -32 Quasi-proper map, Quasi-proper direct image, Banach analytic set

We give a rather simple proof of the generalization of Kuhlmann's quasi-proper direct image theorem to the case of a map with values in a Banach analytic set. The proof uses a generalization of the Remmert-Stein's theorem to this context.

Introduction

The aim of the present Note is to give a rather simple proof for the generalization of Kuhlmann's quasi-proper direct image theorem to the case of a map with values in Banach analytic set. N. Kuhlmann (and D. Mathieu in the Banach case, see [K.64], [K.66] and [M.00]) proved this direct image result for a "semi-proper" holomorphic map; this is a weaker hypothesis than quasi-proper, so their result is better than the one presented here. But the quasi-proper case fits well with the situation we are mainly interested in the study of f-analytic family of cycles (see [B.08], [B.13] and [B.15]1 ). Our simpler argument via the generalization of the Remmert-Stein's theorem does not work for a semi-proper map (see the remark following proposition 2.0.2). In the appendix we give an easy proof of the Remmert's direct image theorem in the proper finite case (with values in an open set of a Banach space) which is used in our proof to make this Note self-contained modulo the theorem III 7.4.1. in [B-M 1].

A simple proof of Kuhlmann's quasi-proper direct image theorem

In order to show the strategy of proof for the generalization of Kuhlmann's theorem with values in an open set of a Banach space, we shall begin by a simple proof of the finite dimensional case using the "usual" Remmert-Stein's theorem.

Theorem 1.0.1 Let f : M → N a quasi-proper holomorphic map between irreducible complex spaces. Then f (M) is a closed analytic subset of N.

Proof. The first point is to prove that f (M) is closed in N. Let y n = f (x n ) be a sequence in f (M) and suppose that y n converges to a point y ∈ N. Let V be a neighbourhood of y in N and K a compact subset in M such that for any z ∈ V each irreducible component of f -1 (z) meets K. Then we may assume that for n large enough y n lies in V and so that x n is chosen in K.

So, up to pass to a sub-sequence we may assume that the sequence (x n ) converges to x ∈ K. Then the continuity of f implies hat y = f (x). So f (M) is closed. Consider now the integer p := max{dim x f -1 (y), y ∈ N} and define the set

Z := {y ∈ N / dim(f -1 (y)) = p}.
We want to show that Z is a closed analytic subset in N. To show that Z is closed consider a sequence (y n ) in Z converging to a point y in N. Let V be a neighbourhood of y in N and K a compact subset in M such that for any z ∈ V each irreducible component of f -1 (z) meets K. Then for each n large enough in order that y n lies in V , we may find a point x n ∈ K such that f (x n ) = y n and with dim xn f -1 (y n ) = p. So, up to pass to a subsequence we may assume that the sequence x n converges to x ∈ K. We have f (x) = y ; consider now a p-scale E := (U, B, j) around x adapted to f -1 (f (x)). Then the map

g := f × (p U • j) : j -1 (U × B) → W × U is proper and finite if W ⊂ V is an open neighbourhood of
x which is small enough. For each x n ∈ W the image of g contains {x n } × U. So it contains also {x} × U and the fibre f -1 (y) has dimension p in W . So y is in Z and Z is closed.

To prove the analyticity of Z we argue as above and we remark that for any holomorphic function h : U × B → C m with zero set j(W ) ∩ (U × B) we have h(y, t) ≡ 0 for t ∈ U when y is in Z. This will give (infinitely many) holomorphic equations for Z in W using a Taylor expansion in t of the holomorphic function h. This proves the analyticity of Z. Remark that Z has dimension ≤ mp where m := dim M.

Now we shall prove the theorem by induction on the integer p ≥ 0. Note that, for p = 0 the result is already proved. So let assume that the result is proved for p = q -1 and we shall prove it for p = q. If the closed analytic set Z introduced above is equal to N, the result is clear because

f (M) = N. If not N \Z is an open dense set in N because N is irreducible and also M \f -1 (Z) is also an open dense set in M. Moreover the map f : M \f -1 (Z) → N \Z induced by f is again quasi- proper. The induction hypothesis gives that f (M \ f -1 (Z)) is a closed analytic subset in N \ Z and it has dimension bigger or equal to m -(p -1) = m -p + 1.
As Z has dimension ≤ mp we may apply Remmert-Stein theorem to obtain that the closure of f (M \ f -1 (Z)) in N is again an analytic set. This conclude the proof as we have

f (M) = f (M \ f -1 (Z)) ∪ Z, because we know that f (M) is closed.
Remarks.

1. The semi-properness of f would be enough to get the fact that f (M) is closed.

2. The restriction of a quasi-proper map to a closed saturated analytic subset X in M2 is again quasi-proper. This is also true for a semi-proper map.

3. When f is quasi-proper to have quasi-properness for f restricted to closed analytic subset X ⊂ M it is enough for X to be an union of some irreducible components of f -1 (y) for y ∈ f (X).

4. This property of X is not enough, in general, in the case of a semi-proper map f . This is precisely what happen for the subset Z introduced below or in the proposition 2.0.2.

2 The case with values in a Banach analytic set Definition 2.0.1 Let f : M → S be a holomorphic map from a reduced complex space M to a Banach analytic set S. We say that f is quasi-proper when for each point s ∈ S there exists a neighbourhood V of s in S and a compact set

K in M such that, for each σ ∈ V , each irreducible component of f -1 (σ) meets K.
Note that f quasi-proper implies semi-proper3 as the definition above implies that

f (K) ∩ V = f (M) ∩ V .
In particular this condition implies that f (M) is closed in S. So our result is local on S and it is enough to prove the Kulmann's theorem with value in an open set of a Banach space.

Proposition 2.0.2 Let f : M → S be a holomorphic map from a reduced and irreducible complex space M to a Banach analytic set S. We assume that f is quasi-proper. Let p := max{dim f -1 (s), s ∈ S}, and define

Z := {s ∈ S / dim f -1 (s) = p}.
Then Z is a closed analytic subset in S which is finite dimensional (so Z is a reduced complex space embedded in S; see the theorem III 7.4

.1 de [B-M 1]).

remark. This result is not true in general for a semi-proper holomorphic map: Let π : M → N be an infinite connected cover of a complex manifold N of dimension n ≥ 2. Let y ∈ N and let V be a relatively compact open set containing y such that π admit a continuous section σ : V → W where W is a relatively compact open set in M. Let (y ν ) be a sequence of points in V \ {y} with limit y and let (x ν ) be a discrete sequence in M \ W such that π(x ν ) = y ν for each ν ∈ N. Let τ : M → M be the blow-up of M at each point x ν and put π := τ • π. Then π is semi-proper and the subset Z of M where the fibre of π has dimension n -1 is exactely the subset {y ν , ν ∈ N} which is not closed in N.

First step of the proof: Z is closed in S. Let (s ν ) ν≥0 be a sequence in Z which converges to a point s in S. Let V be an open neighbourhood of s and K a compact subset of M such that for any

σ ∈ V each irreducible component of f -1 (σ) meets K. For ν ≫ 1 we have s ν ∈ V , and if Γ ν is a p-dimensional irreducible component of f -1 (s ν ), the intersection Γ ν ∩ K is not
empty, and we may choose some x ν ∈ Γ ν ∩ K. Up to pass to a sub-sequence, we may also assume that the sequence (x ν ) converges to a point x ∈ K. Of course we shall have x ∈ f -1 (s). Choose now a p-scale E := (U, B, j) such that x is in j -1 (U × B) and such that j -1 ( Ū × ∂B) ∩ f -1 (s) = ∅. This is possible because we know that dim f -1 (s) ≤ p. Then, up to shrink V around s, we may assume that for any σ ∈ V we have f -1 (σ) ∩ j -1 ( Ū × ∂B) = ∅. This means that for ν ≫ 1 the scale E is adapted to Γ ν and with deg

E (Γ ν ) = k ν ≥ 1. Define on the open set j -1 (U × B) ∩ f -1 (V ) ⊂ M the holomorphc map g := (p U • j) × f : j -1 (U × B) ∩ f -1 (V ) → U × V
where p U : U × B → U is the projection and where V is the open set in S defined by the condition s ∈ f (j -1 ( Ū × ∂B)).

Second step: g is a closed map with finite fibres. The finiteness of fibres is obvious because for σ ∈ V the intersection f -1 (σ) ∩ j -1 ( Ū × ∂B) is empty, so j(g -1 (t, σ)) ⊂ {t} × B is a compact analytic subset in a polydisc, so a finite set.

To show the closeness of g, choose a closed set F in f -1 (V ) ∩ j -1 (U × B) and a sequence (t ν , σ ν ) in g(F ) ∩ (U × V ) converging to a point (t, σ) ∈ U × V , and let (x ν ) be a sequence in F such that g(x ν ) = (t ν , σ ν ). As j -1 ( Ū × B) is compact, we may assume, up to pass to a sub-sequence, that the sequence (x ν ) converges to some

x ∈ j -1 ( Ū × B) ⊂ M. But the limit of g(x ν ) = (t ν , σ ν ) is in U × V by assumption and this implies that x is in j -1 (U × B). As it cannot be in j -1 (U × ∂B) because f (x) is in V , x lies in f -1 (V ) ∩ j -1 (U × B)
and so x is in F . This proves the closeness of g. Now the Remmert's theorem in the proper finite case, but with values in a Banach analytic set4 , applies and shows that the image of g is a reduced complex space.

In this case it is clear that the cardinal of the fibres is locally bounded, so k ν is bounded up to shrink U and V . So, up to pass to a subsequence, we may assume that k ν is constant equal to k ≥ 1.

Then it is easy to see, again up to pass to a sub-sequence and to shrink U, that the sequence j(Γ ν ) converges to a multiform graph. This implies that f -1 (s) has dimension p, so s is in Z.

We shall denote Ξ ⊂ (U × V ) the image of g.

Third step. We shall prove now that, assuming that we choose V small enough around the given point s in Z, the set

Z ′ := {σ ∈ V / {σ} × U ⊂ Ξ} is a closed analytic subset in V .
Remark that Z ′ is contained in Z but it may be smaller that Z because the fibre of a point s ∈ V \ Z ′ may be of dimension p via a component of f -1 (s) which does not meet j -1 (U × B).

Up to shrink V and U we may assume that V is a closed analytic subset of an open set U in some Banach space, and that we have a holomorphic map

Φ : U → Hol( Ū, F )
where F is a Banach space, such that the associated holomorphic map

Φ : U × U → F satisfies Φ-1 (0) ∩ (V × U) = Ξ.
Then it is clear that we have Z ′ = Φ -1 (0). Now remark that Z ′ ×U is a closed analytic subset of Ξ which is finite dimensional. So this implies that Z ′ is also finite dimensional and we have dim

Z ′ ≤ dim M -p.
If we cover the compact set f -1 (s) ∩ K by finitely many p-scales as above, we obtain that Z is locally a finite union of such Z ′ as above and then Z is a finite dimensional analytic set of dimension ≤ dim Mp near the point s; and, as we already know that Z is closed, it is a closed finite dimensional analytic set of dimension ≤ dim Mp in S.

Theorem 2.0.3 Let f : M → N a quasi-proper holomorphic map between an irreducible complex space M and a Banach analytic set S. Then f(M) is a closed analytic subset in S which is locally finite dimensional .

Proof. We shall prove the theorem by induction on the integer p defined in the previous proposition. Note that for a given M, we have always p ≤ dim M < +∞ as we assume M irreducible.

The case p = 0 is clear because in this case we have Z = f (M). Assume the theorem proved when p ≤ q -1 for some q ≥ 1 and we shall prove it for p = q.

From the previous steps we know that Z is a closed analytic subset in S and that it has finite dimension ≤ dim Mp. Let us consider now the map

f : M \ f -1 (Z) → S \ Z
induced by f . It is clearly quasi-proper and for this map we have p ≤ q -1. So, by the induction hypothesis, the image of f is a closed analytic subset in

S \ Z which is irreducible of finite dimension dim Im( f ) ≥ dim M -p ≥ dim M -q + 1 ≥ dim Z + 1.
Now we want to apply the Remmert-Stein theorem to conclude. This is clear in the case where S is a finite dimensional complex space because the dimensions satisfy the desired inequality, but we want now to treat the case where S is a Banach analytic set. As the problem is local, we may replace S by a open set in a Banach space, and we apply the generalization of Remmert-Stein theorem obtained in the next section to conclude.

3 The Remmert-Stein' theorem in a Banach space Theorem 3.0.1 Let U an open set in a Banach space and let A ⊂ U be a closed analytic susbset of dimension d.

Let X ⊂ U \ A a closed irreducible analytic subset in U \ Z of finite dimension ≥ d + 1. Then X is a closed irreducible analytic subset in U of finite dimension equal to dim X.
Here is a first step of the proof of this theorem.

Lemma 3.0.2 Let X ⊂ U be a closed analytic subset in an open set U in a Banach space E. Assume that X has finite pure dimension ≤ n and that X is countable at infinity. Let a ∈ U \ X and x ∈ X. Assume also that a n-dimensional linear subspace L containing a is given. Then there exists a linear closed codimension n subspace P in E containing a and x, such P is transversal to L at a and that the set X ∩ P is discrete and countable.

Proof. We shall make an induction on n ≥ 0. The case n = 0 is trivial. So let assume that the case n -1 is proved and consider X of pure dimension d ≤ n.

Choose for each irreducible component X ν of X a point x ν ∈ X ν which is not equal to x 5 . Now choose an hyperplane H containing a and x and such that x ν is not in H for each ν, and that H is transversal to L at a. Such a hyperplane exists thanks to Baire's theorem. Then X ∩ H is purely (d -1)-dimensional and contains x. The induction hypothesis gives us a co-dimension n -1 subspace Π containing a and x, transversal at a to L ∩ H, such that Π ∩ (X ∩ H) is discrete and countable. Now the co-dimension of P := Π ∩ H is exactly equal to n and is transversal to L at a. This completes the proof.

Proof of the theorem 3.0.1. We follow the proof of the proposition II 4.8.3 case (i) given in [B-M 1] but with an ambiant infinite dimensional complex Banach space. The theorem 3.0.1 follows from this result as in the finite dimensional case.

First, the following point is not completely obvious : the local compactness of X ∪A.

Of course A and X are locally compact by assumption. So it is enough to show that this union is locally compact near a point a ∈ A. Remark first that we have

∂X ⊂ ∂U ∪ A.
and X ∪A is closed in U. So if we consider ε > 0 small enough, we have B(a, 2ε) ⊂ U and B(a, ε) ∩ A is a compact set. Now we want to show that B(a, ε) ∩ (X ∪ A) is compact. So it is enough to show that any sequence (x ν ) in B(a, ε) ∩ X admits a converging sub-sequence to a point in B(a, ε). Let

δ ν := d(x ν , A ∩ B(a, ε)).
5 As n ≥ 1 an irreducible component is not equal to {x}.

If δ ν goes to 0 for some sub-sequence, then there is a Cauchy sub-sequence converging to some a ′ ∈ B(a, ε) ∩ (X ∪ A). If δ ν ≥ α > 0 for all large enough ν, then the sequence is contained in the subset

B(a, ε) \ {x / d(x, A ∩ B(a, ε)) ≥ α)} ∩ X.
This subset of X is compact, because it is closed and a sequence in it cannot approach neither ∂U (as B(a, 2ε) ⊂ U, any point z ∈ B(a, ε) satisfies d(z, ∂U) ≥ ε) nor A, and X is locally compact (so any discrete sequence has to approach the boundary of X).

Assume that X has dimension d + k with k ≥ 1. For a ∈ A a fixed smooth point, let V be a d + k sub-manifold through a containing A (we use here the theorem III 7.4.1 in [B-M 1]) and choose a co-dimension d + k plane P transversal to V at a meeting some point in X ∩ B(a, ε) and such that P ∩ X is discrete. Up to shrink V and taking a small ball B 0 with center a in P , we may assume that an open neighbourhood of a in B(a, ε) is isomorphic to the product V × B 0 . And from our construction we have X ∩ ({a} × B 0 ) which is discrete.

Claim. We can choose two small balls B ′ ⊂ B in P with center a contained in B 0 ⊂ B(a, ε) ∩ P such that (B \ B ′ ) ∩ X = ∅ and then we may find an open neighbourhood U of a in V in order that the projection on U of the set X ∩ (U × B ′ ) = (X ∪ A) ∩ (U × B) is proper (this means closed with compact fibres) and that its restriction to X ∩ ((U \ A) × B) has finite fibres.

proof. The choice of two arbitrary small balls B ′ ⊂ B with the first condition (B \ B ′ ) ∩ X = ∅ is easy because we know that X ∩ ({a} × B 0 ) is discrete : the distances to a of the points in X ∩ ({a} × B 0 ) are in a discrete subset in ]0, ε[ and we can choose r ′ < r with r arbitrary small such that ]r ′ , r[ avoids these values. But the subset (X ∪ A) ∩ B(a, ε) is compact and then, as A ∩ ( B \ B ′ ) is empty, the subset X ∩ ({a} × B) is compact. Then there exists an open neighbourhood U of a in V such that the projection of X ∩ (U × B) on U is proper : Let K be a compact neighbourhood in X ∩ (V × B) of the compact set X ∩ ({a} × B) (remember that we proved that X = X ∪ A is locally compact). Then for K small enough the distance of a point in K to the closed set {a} × ( B \ B ′ ) is bounded below by a positive number, and so there exists an open neighbourhood U of a in V such that U × ( B \ B ′ ) does not meet K. This is enough to prove the claim thanks to the following simple remark, as X ∩

((U \ A) × B) = X ∩ ((U \ A) × B) because A ≃ A × {a} ⊂ U × B ′ .
Remark. Any compact analytic subset in X ∩ B(a, ε) is finite: assume that Z is a connected component of such a compact analytic subset. As compactness implies that there are at most finitely many Z, it is enough to prove that Z has at most one point.

Assume that z 1 = z 2 are two points in Z. Choose a continuous linear form on E such that l(z 1 ) = l(z 2 ). As the map l |Z : Z → C is holomorphic, it has to be constant (maximum principle and connectness). Conclusion : Z has at most one point.

The end of the proof of the theorem 3.0.1 is now analogous to the end of the proof in the finite dimensional setting (we are in the "easy" case where the dimension of X is strictly bigger than d the dimension of A ; see the remark before the lemma 4.8.7 in [B-M 1] ch.III).

Remarks.

1. Along the same line, it is not difficult to prove the analog of the Remmert-Stein's theorem with equality of dimensions, assuming there exists an open set in U meeting each irreducible component of A and in which X ∪ A is an analytic subset.

2. In our proof we use in a crucial way the metric in the ambient Banach space.

If the extension of this proof to an open set in a Frechet space may be easy, the case of a non metrizable e.l.c. 4 Appendix: the direct image theorem in the proper finite case

Notation. An e.l.c.s.s. is a locally convex topological vector space which is separated and sequentially complete. For the definition we shall use of a holomorphic map on a reduced complex space M with values in a e.l.c.s.s. see [B-M 1] ch. III definition 7.1.1. Note that the general proper case of this result is given in loc. cit. th. III 7.4.3 but the proof of the proper finite case is much more simple.

To have a simple and self-contained proof (modulo the theorem III 7.4.1. in [B-M 1]) of the quasi-proper direct image theorem discussed in this Note, we shall give a easy proof of the direct image theorem in the proper finite case with values in an e.l.c.s.s.(this result has been used in the Banach case in our proof). This allows to use the proof of the previous section also in the proper case, thanks to the following lemma.

Lemma 4.0.1 Let f : M → S a holomorphic map from a reduced complex space to an open set of an e.l.c.s.s. Assume that f is closed with compact fibres (so f is proper). Then f is quasi-proper.

  s.s. (for instance a dual of Frechet space ) does not seem clear. Note that the proper case is proved with values in an open set of any e.l.c.s.s. in [B-M 1] ch.III.

Nevertheless we prove the semi-proper case of the direct image theorem with values in C f n (M ), the space of finite type n-dimensional cycles in the complex space M in [B.15] th.

2.3.2.

A subset X of M is saturated for f if x ∈ X implies f -1 (x) ⊂ X.

Recall that a continuous map f : M → S between Hausdorff topological spaces is semi-proper if for any s ∈ S there exists a neighbourhood V of s in S and a compact set K in M such that for any σ ∈ V the fibre f -1 (σ) meets K. This is a topological notion contrary to the quasi-properness which asks that M is a complex space and that the fibres of f are (closed) analytic subsets in M (but no complex structure in needed on S).

So we have to use the proper case with finite fibres of the Remmert' theorem with values in an open set of a complex Banach space to prove this proposition. To make this Note self-contained (modulo the theorem III 7.4.1. in [B-M 1]) we give a simple proof of this case in the appendix (section 4). See also [B-M 1] chapter III for the general case.

proof. If f is not quasi-proper at s ∈ S there exists, for each open neighbourhood V ν of s and for each compact K in M a point σ ν,K ∈ V ν and an irreducible component Γ ν,K of f -1 (σ ν,K ) which does not meet K. Now, for a fixed K we may choose the points σ ν,K to be distinct. Let W be a relatively compact open set in M containing the compact fibre f -1 (s) and let K := W . Then for each ν we can find a point

x ∈ F \ F , the point x is limit of an ultra-filter of points in F , and so f (x) is equal to s, because the intersection of the V ν for any ultra-filter is reduced to {s}. But as x ∈ M \ W and f -1 (s) ⊂ W , this is a contradiction. So the map f is quasi-proper at any point s ∈ S.

Proposition 4.0.2 Let f : M → S be a holomorphic map of a complex reduced space M to an open set S in a e.l.c.s.s. Assume that f is closed with finite fibres (so proper and finite). Then f (M) is a closed analytic subset which is locally of finite dimension in S.

proof. As f (M) is the locally finite union of the sets f (M i ), i ∈ I, where M i , i ∈ I is the set of irreducible components of M because f is quasi-proper and finite thanks to the previous lemma, we may assume that

Let G be the ambiant vector space of S. Choose a finite co-dimensional closed affine subspace H containing s in the e.l.c.s.s. G such that the point s is isolated in H ∩ f (M) which is maximal for this property. Such a H exists because it is easy to construct a sequence (H q ) of closed co-dimension q affine subspaces in G containing s such that the germ of f -1 (H q ) at f -1 (s) gives a strictly decreasing sequence of analytic germs as long as f -1 (H q ) is strictly bigger than the finite set f -1 (s). Then at the last step q 0 we have the equality of germs f -1 (H q 0 ) = f -1 (s) in M. If H q 0 is not maximal with this property, replace H q 0 by a maximal closed affine subspace containing s and containing H q 0 with this property. Write G = C n ⊕ H 0 where H 0 is the closed co-dimension vector subspace in G directing H and let p : G → C n and p H : G → H be the projections. Then the germ of analytic map g : (M, f -1 (s)) → (C n , p(s)) is finite by construction. So its image is an analytic germ. If it is not equal to (C n , p(s)) we can find a line ∆ through p(s) in C n such that g -1 (p(s)) = f -1 (s). Then the affine space p -1 (∆) contradicts the maximality of H. So the germ g is surjective and we can find an open polydisc U with center p(s) in C n such that g : M ′ := g -1 (U) → U is a k-sheeted branch covering. So we have a holomorphic map ϕ : U → Sym k (M ′ ) classifying the fibres of g. Composed with the holomorphic map induced by Sym k (p H •f ) we obtain that f (M ′ ) is a multiform graph of U contained in U × H (see [B-M 1] chapter III section 7.2). As we have f (M ′ ) = p -1 (U) ∩ M in a neighbourhood of s, we conclude that f (M) is a finite dimensional analytic subset in G in a neighbourhood of s.