Artur P Sampaio

Raphaëlle Chaine

Creto A Vidal

Joaquim B Cavalcante-Neto

Temporally Coherent Sculpture of Composite Objects

Keywords: Sculpting, Interactive techniques, Agglomerates

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Modeling virtual objects is essential in the entertainment industry. Far from computer-aided design (CAD) and tedious static parameterisation systems, artists expect to use abilities developed from real life sculpting in digital environments. Many systems now allow users to sculpt objects as they would do with virtual clay, but little effort has been made in the direction of materials composed of smaller entities that are glued together or that roll around each other. Artists should feel free to deform such global composites, as the elements change position, and appear or disappear automatically around each other. Likewise, we would like to give artists the opportunity to sculpt a cloud of little objects that are not joined to each other or to deform such composites through other means, such as scripted deformations.

In this paper, we consider the sculpting and rendering of surfaces represented as agglomerates of smaller, composing 3D elements. These agglomerate materials are common in nature: rock piles, armies of ants, castles of sand, beautiful works of tiled art -basically any group of similar, randomly oriented elements that, when viewed together, form a larger scale shape (see Figure 2). The 3D elements we use, henceforth denoted CompEls, can be seen as 3D models anchored at the faces of a support mesh. Representing and updating those kinds of assem-blies efficiently remains an open problem. The sheer quantity of elements on a surface and the polygons required to represent them can cripple even powerful GPUs.

As stated in [START_REF] Ma | Dynamic element textures[END_REF], the biggest challenge in creating an agglomerate is controlling the position of individual objects. Traditionally, agglomerates were created by placing each composing element in its final position, one by one. This can be cumbersome due to sheer object count. The other common approach is to design an intermediate representation and to populate it afterwards with smaller elements, using for example systems of particles in the case of a regular distribution or samplebased distributions [START_REF] Emilien | Worldbrush: Interactive example-based synthesis of procedural virtual worlds[END_REF]. This a posteriori element sampling can either be limited to the object's surface or encompass the entire volume [START_REF] Peytavie | Procedural Generation of Rock Piles Using Aperiodic Tiling[END_REF]. Extensive research has been done on how to generate and render such models correctly. The representation of the proxy object generally does not need to be exact or high quality. It can result from the rough meshing of an implicit surface, or from any other meshing design that does not involve constraints on the quality of the facets. The final rendered composite will display very high quality results and sampling properties. Those optimisation techniques are clearly not intended for real-time applications or for dynamic surfaces. The corollary is that the user cannot see the desired agglomerate pattern before the end of the design process of the proxy shape. This can be a problem for the design of object clouds, where it becomes very difficult to have an idea of the final shape's outer silhouette without the presence of the actual objects. The problem is compounded on the representation of animations, where temporal continuity or coherence is also of concern. Merely resampling elements on updated regions of an animated surface can cause significant visual artifacts, due to sudden changes associated with rapid object insertion and removal, as described in [START_REF] Schwarz | On predicting visual popping in dynamic scenes[END_REF]. The temporal continuity that we aim to obtain is similar to the one defined by Medeiros et al [START_REF] Medeiros | Fast adaptive blue noise on polygonal surfaces[END_REF], which means that objects should be inserted, displaced and removed without popping effects or loss of visual continuity between frames.

Another approach to minimize the cost of positioning the elements over the surface is to delay their involvement until the rendering pipeline, using works on spatial adaptive sampling of density function and projections. A number of publications focus on the process of rendering images using dots, called stipples. A stipple can later be transformed into the anchor of an orientable texture unit. For that reason, a good stippling can be the basis for agglomerate generation. One usually aims at obtaining blue noise samplings [START_REF] Vanderhaeghe | Dynamic point distribution for stroke-based rendering[END_REF]. Hierarchical tiles with different levels of resolution [START_REF] Ostromoukhov | Fast hierarchical importance sampling with blue noise properties[END_REF], [START_REF] Wachtel | Fast tile-based adaptive sampling with userspecified fourier spectra[END_REF] can be used to generate adaptive samplings with fast timings (except for preprocessing costs). More focused on meshed surfaces to be sampled, Pastor et al [START_REF] Pastor | Real-time animated stippling[END_REF] use a dynamic stippling generation system that performs directly on a mesh and that relies on adaptive subdivision meshes. However, although they use a hierarchical framework and the mesh could be edited for nearly isometric deformation, their work relies on fixed topology and overall connectivity. Finally, there is a tight coupling between vertices and stipples. For the same kind of applications, a hierarchical Poisson disk sampling was precomputed on the surface [START_REF] Medeiros | Fast adaptive blue noise on polygonal surfaces[END_REF]. It can be later evaluated and rendered according to an importance function. Their system, however, uses fixed connectivity meshes. Singh et al [START_REF] Abdrashitov | Mosaic: Sketch-based interface for creating digital decorative mosaics[END_REF] employ a sketch-based interface to interactively create 2D mosaics. More recently, research has been done on detailpreserving deformation [START_REF] Rohmer | Real-Time Continuous Self Replicating Details for Shape Deformation[END_REF] that does not drastically affect the overall aspect of a shape, like the stretching of one part. The method is capable of maintaining temporally coherent details on meshed surface stretch with local updates performed on the geometry and connectivity. The number of details evolve on an enlarging area. Though capable of decoupling mesh and detail resolutions, those methods are not intended for agglomerate material representation. Details are represented as high frequency changes applied on top of objects' surfaces.

Textures are also a fast and reliable way of adding information to meshed surfaces without requiring any additional geometry description. For that reason, they are natural candidates for representing composites. Tiled composite textures can be mapped to large surfaces by reusing texture cells. A composite could be created by aperiodic tile packing and good surface parameterization. This precludes the need for generating individual compositing elements on the surface. The resulting textured surface can also be made non-periodic, and retains most of the attributes of the tile packing. Most of the related research follows this strategy [START_REF] Wei | Tile-based texture mapping on graphics hardware[END_REF], [START_REF] Li | Anisotropic blue noise sampling[END_REF], [START_REF] Vanhoey | On-the-fly multi-scale infinite texturing from example[END_REF]. The tile packing is usually created from methods such as Wang Tiles and Corner tiles, which have an expensive preprocessing step: the construction of a good distribution, such as Poisson Disk Distribution, of the initial tile packing, and surface parameterization. The resulting tiled texture can be mapped on the fly to the mesh by means of Direct Stochastic algorithms implemented by hashing functions, as discussed in [START_REF] Lagae | Tilebased methods for interactive applications[END_REF]. In order to generate the most photorealistic agglomerate materials, recent research has given attention to 3D texture mapping to represent complex surface detail on parameterised surfaces [START_REF] Koniaris | Texture mapping techniques for volumetric mesostructure[END_REF], [START_REF] Meng | Multi-scale modeling and rendering of granular materials[END_REF]. The main restriction to this kind of strategy to our intended application on dynamic meshes is that reparameterization after deformation can be time consuming or non-temporal preserving. Surface tracking methods can ensure consistent parameterization [START_REF] Bojsen-Hansen | Tracking surfaces with evolving topology[END_REF] and insertion of details [START_REF] Mercier | Surface turbulence for particle-based liquid simulations[END_REF] through animations even on large-scale surface deformations, but so far have not been able to do it in real-time.

A more direct approach, called texture bombing, involves sampling texture or mesh elements directly on the target surface [START_REF] Dischler | Texture particles[END_REF]. Sampling variation and rendering efficiency can be (a) An ant bridge reveals nature sculpting through agglomerates [START_REF] Land | Bridging environmental conservation and animal rights[END_REF].

(b) An ant bridge sculpted in our framework.

(c) Deus Ex Machina [START_REF] Robertson | The matrix resolution[END_REF]. The swarm of bugs forming the god's face illustrates an industry inspiration for our work. improved by adding noise and by precomputing levels-of-detail [START_REF] Wang | Just-in-time texture synthesis[END_REF]. A common limitation is the requirement of static connectivity and geometry. Changing the underlying mesh connectivity would require recalculating all texture and element particle maps. [START_REF] De Groot | Implicit decals: Interactive editing of repetitive patterns on surfaces[END_REF] uses 2D texture decals placed on the surface and performs local parameterization only, which allows for small deformations on the surface with consistent texturing and realtime rendering. It is not, however, targeted at accumulating or large scale deformations.

In the domain of surface sculpting and deformation, many techniques have been proposed. As discussed in [START_REF] Aghdaii | 5-6-7 Meshes[END_REF], a number of sculpting frameworks use volumetric models with adaptive topology. These systems operate by locally carving and merging materials under the action of the user. Though they are straightforward to implement, they usually have large storage requirements, as well as sampling and continuation issues, as the surface needs to be constantly re-extracted.

Concerning boundary representations, a number of works deal with the editing of point-based surfaces [START_REF] Zwicker | Pointshop 3d: An interactive system for point-based surface editing[END_REF], while others deal with meshes. First spatial warping techniques [START_REF] Gain | Warp sculpting[END_REF] that were developed to determine displacement vectors in adaptive meshes, mainly depended on the use of haptic interfaces in order to become intuitive. Since then, several applications managed to deform and refine a mesh in real time, by embedding it into a deformation field [START_REF] Stanculescu | Sculpting multidimensional nested structures[END_REF]. A deformation field assigns a displacement to each point of the evolving surface to produce local perturbations [START_REF] Gain | Warp sculpting[END_REF]. Those deformation fields may be defined in the ambient space, while still holding properties such as volume preservation [START_REF] Angelidis | Swirling-sweepers: Constant volume modeling[END_REF], [START_REF] Von Funck | Vector field based shape deformations[END_REF] or detail preservation [START_REF] Sumner | Embedded deformation for shape manipulation[END_REF] of the shape being deformed. They can also depend on differential properties of the surface or even on features to be preserved [START_REF] Stanculescu | Freestyle: Sculpting meshes with self-adaptive topology[END_REF]. Finally, Laplacian editing [START_REF] Sorkine | Laplacian surface editing[END_REF] can be used to extend the deformation field between a fixed part of the shape being deformed and a handle. An extension of Laplacian editing can be used to preserve details when stretching adaptive meshes [START_REF] Dekkers | Geometry seam carving[END_REF]. Although such systems can convey a wider range of operations, the performance cost related to updating and solving sparse linear systems usually restricts their use, in the context of solid sculpting, to mesh posing and detail-preserving deformations. Furthermore, the fast intersection detection and prevention between multiple rigid objects has been vastly studied, but solutions tend to be too slow for real-time [START_REF] Tang | Fast continuous collision detection using deforming non-penetration filters[END_REF].

Overview

In this research, we address the problem of sculpting shapes composed of small volumetric elements. For now, we exclude the use of shapes considered "too elongated", such as hair fibers, since they can be seen as lower dimensional objects. Furthermore, we are interested in shapes whose component elements can be distant or loosely glued to each other. Under the action of a deformation field, two touching elements should be able to separate, if so required. In Section 3, we will suggest how these shapes can be empirically described by a system of elements referred to as CompEls. This system relies on a uniform sampling of the evolving shape to describe the relative positions of Com-pEls to one another, without implementing interaction forces, but only by identifying local area variations on the shapes envelope. Section 4 then describes how to initialise the CompEls coverage of the shape, and how to update it under the action of a deformation field that controls surface vertices' and Com-pEls' positions alike, even when it does not correspond to an isometric deformation. Intuitively, CompEls undergo the same deformation of the faces of the support mesh, whose vertices present uniform sampling, except when a triangle disappears or is split. We suggest fast redistribution schemes aiming at little to no CompEls displacement in Section 4.2. While splitting a triangle is quite natural, the transfer of CompEls from a destroyed triangle imposes to make room in neighboring triangles by stretching sub-regions. The heuristics proposed only use simple barycentric coordinates tests and computation of pairs of closest points between two edges. Finally, we discuss in Section 5 how to use the graphic card to perform CompEl variation, visual intersection prevention and to speed up the CompEl-made shapes' display, before presenting numerical results in Section 6 and concluding in Section 7.

A new system for empirical description of composite shapes

Avoiding management of interactions between components?

Whenever a composite shape is deformed, its elements are displaced under the action of the deformation. The nature of the interactions between components that collide can be very complex to model, leading to numerical systems that are difficult to solve in real time. Even if not physically accurate, we decided to make a compromise by basing our approach on empirical descriptions instead. We stress that our goal is to offer the user a magnified experience of sculpture, still in real time, and we do not necessarily adhere faithfully to the physics of the real world. The observations we have decided to focus on are the followings:

• Elements that move toward and touch each other are clamped in their movements, they cannot get closer. This implies a change in their position at this time step, compared to the expected position that would have been reached in absence of collision (position induced by the local deformation of the shape exclusively). Among the elements visible from the outside, some only undergo tangential additional movement on the surface, while others are pushed inside the shape and disappear behind other elements.

• Conversely, when the deformation field separates elements that were previously in contact, new elements appear between the distanced CompEls, emerging from the interior of the shape.

Maintaining a uniform set of anchors on the shape

Since we are interested in empirically simplifying the deformation of a compound shape, it may be worthwhile to get rid of internal components, and to focus on visible elements only. These are the elements of the outer layers of the evolving shape. We also need descriptors in order to locally identify the effects of deformation on the surface of the shape. Indeed, we aim to know wherever the surface is contracting and wherever it expands. This will be useful to avoid computing exact collisions between components. To this end, we propose to maintain a uniform sampling of a rough envelope of the shape with a set of anchors. Wherever the shape is deformed isometrically, the sampling should remain stable. In contrast, the emergence of new samples is an indicator of the areas of expansion, where new components should become visible. Finally, the disappearance of samples will identify areas where the shape locally contracts.

It is important, therefore, to locate the components that we track with respect to the uniform sampling. We do not aim to couple each component with a sample, since we do not want the elements to be distributed regularly over the surface. Furthermore, we want the number of samples to be significantly smaller than the number of components. We suggest connecting the samples into a triangulated mesh to anchor the components therein. For that aim, we focused on the quasi-uniform meshes proposed by [START_REF] Stanculescu | Freestyle: Sculpting meshes with self-adaptive topology[END_REF] to maintain a nearly uniform sampling of a shape that is sculpted under the action of deformation fields but other systems are also possible. Quasi-uniform meshes are characterised by a level of detail d, which technically corresponds to the maximum distance between two adjacent samples, as well as a minimum thickness t, below which the shape breaks locally, as described in [START_REF] Stanculescu | Freestyle: Sculpting meshes with self-adaptive topology[END_REF]. Unlike similar systems [START_REF] Lachaud | Deformable meshes with automated topology changes for coarse-to-fine three-dimensional surface[END_REF] previously proposed in image processing, quasi-uniform meshes do not guarantee a minimum length for the edges but still promote the elimination of edges that are too short. Whenever the surface is deformed, edges that have become too long are broken by a sequence of flips or splits. This means that samples becoming distant are not connected anymore, and that new samples are inserted in between whenever a split is performed. That sequence of long edges destruction is followed by a sequence of merging short edge extremities (those with length smaller than d/2). When this step is over, all the edges that once again grew larger than d are flipped or split. The proposed algorithm optimises the uniformity of the edges, and does not require any additional step. It also does not require a relaxation loop. The resulting mesh is only consistent with the constraint regarding the level of detail d. The uniformity obtained in practice turns out to be sufficient for our purpose. Finally, as described in [START_REF] Stanculescu | Freestyle: Sculpting meshes with self-adaptive topology[END_REF], in order to ensure an accurate tracking of the deformation (at the precision d) and of the changes in topological genus, we recall that deformations have to be subdivided into smaller steps d move such that 4d 2 move ≤ t 2d 2 /3.

3.3.

Description of outer layers of a shape by a system of Com-pEls.

We suggest to use quasi-uniform meshes as an anchor for the component elements of the shape. Given a quasi-uniform mesh of the input shape, we propose to populate it with a set of elements that we shall refer to individually as CompEl (Composing Element) hereafter. Each CompEl is anchored into a triangle and is characterised by its barycentric coordinates within that triangle, by its depth level with respect to the envelope of the object and by its orientation (rotation) relative to its support triangle.

Generation and update of CompEls under deformation

Initialisation

The initial distribution of CompEls is obtained using an accelerated dart throwing technique on an input quasi-uniform mesh (it is easy to transform any triangular manifold mesh into a quasi-uniform mesh using a sequence of edge flips, edge splits and edge collapses). The user should only provide the target density e corresponding to the number of CompEls that are visible or partially visible per area unit and the number of layers n over which the CompEls are distributed. CompEls are then inserted in the faces by randomly picking their barycentric coordinates, their orientation and their level of deepness. The method is fully parallelizable, as it only requires information from the given face.

Considering that the faces may not exactly have the same area, each face receives a number of CompEls proportional to its area. The depth level is just an artificial information to be used by the graphic card during the rendering step, as described in section 5. If one wishes to sculpt a shape with the appearance of a plain object, it is important to choose e sufficiently large such that e*(projected area of a CompEl) is greater than the area of an equilateral triangle with edge length d. In order to ensure small area triangles to contain CompEls, we also set a minimum threshold on the number of CompEls. This naive initialisation is simple and powerful enough to create a good jittered gridlike distribution, provided that the triangles are approximately regular, with a controlled area.

Temporal coherence and continuity under freestyle sculpting

Whenever the shape is changing under the action of a deformation field, the vertices of the quasi-uniform mesh move accordingly and the triangles are deformed. As described above, the outgrown triangles are automatically cut into smaller triangles and small triangles collapse in turn. It is important to set rules for internal evolution and transfer of the CompEls between those triangles. Wherever the shape undergoes a rigid transformation locally, the triangles keep their initial dimension, and the CompEls do not change their position with respect to their support faces. Anywhere else, we suggest the evolution of the CompEls to be directly coupled with the elementary operations performed on the triangles: flip, split and collapse of the edges. The following rules should be interpreted as CompEls migration rules, from the triangles being destroyed towards the triangles being created and towards the neighboring triangles whose dimensions are impacted by the operation. Those rules remain local and simple, while still ensuring temporal continuity of CompEls. Thus, the evolution of the resulting system does not relate any more to some force equalizing system as is the case with a physical system. The update can be performed in real-time, possibly involving parallelism.

After each operation, the proportion of CompEls per unit of area is maintained by creating new CompEls in any triangle with a shortage in the number of CompEls. These are created in deeper layers. When a layer of depth is not sufficiently represented in a triangle, the update also picks a few CompEls randomly from deeper layers and promotes them to upper layers. Similarly, CompEls can be destroyed in deeper layers whenever a triangle is too crowded. With this maintenance strategy, visual artifacts related to the sudden insertion or removal of CompEls are minimised or overcome entirely, as those operations are performed behind the elements on the surface.

Edge split

Splitting an edge that has grown beyond d after applying a deformation results into replacing its two incident triangles by four triangles. We first address the case where the edge is cut in the middle. We suggest a very simple CompEls coordinate update within these triangles that ensures that CompEls remain where they were positioned before the division step. Figure 3 illustrates the technique on a face f affected by an edge split.

V 4 V 2 V 3 V 1 V 4 V 2 V 3 V 1 f f 1 f 2
Figure 3: Splitting an edge at its center. Left: CompEls in f before split. Right: Distribution of CompEls between f 1 and f 2 after V 4 splits the edge V 1 V 2 at its center.

Split update. Let (α, β, γ) be the barycentric coordinates of a CompEl C with respect to the vertices V 1 , V 2 and V 3 of a face f to be split on V 1 V 2 (C = αV 1 + βV 2 + γV 3 ), a straightforward implementation to the CompEls distribution between each of the two resulting faces f 1 and f 2 is simply to transmit to f 1 the CompEls whose barycentric coordinate with respect to V 1 is bigger than that to V 2 , and the remaining to f 2 . The barycentric coordinates of the CompEls attached to

f 1 (α > β) thus evolve into (α -β, 2β, γ) with respect to V 1 , V 4 and V 3 .
Proof. As we know that the triangle is split in half with the insertion of a vertex

V 4 in V 1 V 2 (V 1 + V 2 = 2V 4 )
, we can update the barycentric coordinates straight away.

C = αV 1 + β(2V 4 -V 1 ) + γV 3 = (α -β)V 1 + 2βV 4 + γV 3
The barycentric coordinates of the CompEls attached to f 1 (α > β) thus evolve into (α -β, 2β, γ) with respect to V 1 , V 4 and V 3 .

In the case where a deformation is decomposed into steps that are sufficiently small with respect to d and the minimum thickness t, the split of an edge using its middle is sufficient to track the deformation with precision d [START_REF] Stanculescu | Freestyle: Sculpting meshes with self-adaptive topology[END_REF]. However, if we want to improve the quality of the resulting anchor mesh, we propose choosing another position for the added vertex that better corresponds to the sampling strategy proposed by [START_REF] Von Funck | Vector field based shape deformations[END_REF]. Whenever an edge is split, the new vertex is positioned at the location corresponding to the deformation of the middle of the initial edge (the one before deformation) (see left Figure 4). This position may not be equidistant from the two extremities of the deformed edge. We adapt the update of the CompEls so as to take these relative distances into account, while still providing a fast scheme. We calculate the ratio between the distances r 1 = ||V 1 V 4 || and r 2 = ||V 2 V 4 ||, and use that ratio r = r 2 /r 1 as the new threshold for CompEls placement in f 1 or f 2 . An illustration of the modified procedure is shown in Figure 4. We therefore avoid overly sparse regions in f 1 and overly crowded regions in f 2 .

V 2 V 3 V 1 f 1 f 2 V 4 V 2 V 3 V 1 f 1 V 4 f 2 V 4 V 2 V 3 V 1 f Figure 4: Modified edge split algorithm. Left: f before split of V 1 V 2 ,
and before shifting the initial midpoint V 4 to its deformed position. Center: naive approach, that distributes the CompEls with respect to the initial midpoint of V 1 and V 2 and that does not adapt to the difference between the areas being deformed. Right: modified approach, taking into account the area difference.

Edge collapse

The collapse of an edge VV affects all the triangles that are incident to V or V : the two triangles that are incident to the edge VV disappear and the remaining are distorted. In the case where the surface is nearly planar, the migration of CompEls could be obtained by superposing the configurations of the triangles before and after the edge collapse, with the initial Com-pEls being projected on the remaining triangles. This amounts to not moving CompEls during redistribution (see top Figure 5). This strategy has already been proposed by [START_REF] Hale | Texture re-mapping for decimated polygonal meshes[END_REF] for traditional texture update on edge collapse algorithms. The overlay of the original and modified projected connectivities results in a set of convex polygonal cells, whose determination imposes the calculation a number of points that, in the worst case, is proportional to the square of the number of neighbouring edges [START_REF] Cohen | Simplifying polygonal models using successive mappings[END_REF]. Time requirement to correctly place CompEls during the edge collapses at a given frame can therefore increase. Furthermore, if the surface is not flat, the extension of this approach to the general case requires the determination of a projection plane that is suitable for all the participant triangles, before and after deformation. Especially, it is necessary to avoid the folding of the projected surface. The choice of such a plane is not always obvious or legitimate. We propose a simple heuristic that is an order of complexity faster and that does not require explicit projection calculations (see bottom Figure 5).

Among the faces that are affected by the collapse of an edge VW, the two faces VWX and WVY are destroyed. The other affected faces are maintained, but their vertex incident to the collapsed edge (V or W) is moved to the midpoint V of VW. We suggest only redistributing CompEls on destroyed faces to the remaining ones. In our heuristic, the surviving faces also keep their own original CompEls, but those are redistributed over a sub-region (of triangular or quadrangular shape), in order to make room for the CompEls of the triangles being destroyed.

Collapse update. Let V 1 , .., V n denote the vertices incident to the new vertex V that are located counterclockwise between X and Y, and W 1 , .., W m the vertices that are located counterclockwise between Y and X. We execute our Compel distribution by visiting the faces around V in a specified order.

In order to determine the CompEls that migrate from VWX to V XV 1 , our approach computes the pair of closest points and P 1 that are located on the straight lines (V X) and (V V 1 ) respectively (as illustrated in Figure 6). If P 1 and P 1 are located within the interior of the segments V X and V V 1 respectively, these two points can be used to define a kind of local projection of the CompEls (see illustration in Figure 5 and6):

P 1 V W X V 1 V 2 V 3 V 4 = V n Y W 1 = W m V X V 1 V 2 V 3 V 4 = V n Y W 1 = W m W
• CompEls initially located in V XV 1 are pushed above segment XP 1 on the resulting face V XV 1 . Everything happens as if the point V were pushed towards P 1 , which means that the barycentric coordinates (α, β, γ) of a Com-pEl C expressed in P 1 XV 1 are the same as its original coordinates in V XV 1 . We say that the triangle V XV 1 is lifted to P 1 XV 1 . Since we know the barycentric coordinates (µ 1 , ν 1 ) of P 1 with respect to V 1 and V , the new coordinates of C in the triangle V XV 1 are (αν 1 , β, αµ 1 + γ).

• CompEls of VWX that are initially located within V XP 1 are lifted to the triangle V XP 1 by keeping their barycen-

X V 1 V' V W P 1 P' 1
V 1 V X (in light-red) are lifted to the subregion V 1 P 1 X (darker red) of triangle V 1 V X.
The dotted line reveals the shortest segment between edges (V X) and and (V V 1 ). tric coordinates unchanged within those two triangles. Therefore, their new coordinates within V XV 1 can be updated using the coordinates (µ 1 , ν 1 ) of P 1 and the coordinates (µ 1 , ν 1 ) of P 1 within V X.

We iteratively carry a similar treatment with CompEls contained in the triangles VV i V i+1 for increasing values of i ranging from 1 to a stop condition defined below. In order to determine which of the triangle VWX's CompEls are reassigned to the triangle VV i V i+1 , we compute the pair of closest points P i+1 and P i+1 that are located on the straight lines (V X) and (V V i+1 ) respectively. If P i+1 and P i+1 are located in the interior of the segments V X and V V i+1 , the following migrations are performed:

• CompEls initially located in VV i V i+1 are lifted above the segment P i P i+1 on the resulting face V V i V i+1 . This amounts to lifting the initial triangle VV i V i+1 into the quadrangle P i V i V i+1 P i+1 . Let C be a CompEl (α, β, γ) in VV i V i+1 and let C be the position corresponding to the same coordinates (α, β, γ) within V V i V i+1 . The target position C" of the CompEl C will be placed along the line (V C ): one determines the intersection P (i,C) (resp. V (i,C) ) of this line with P i P i+1 (resp. with V i V i+1 ) and we consider the linear mapping of V P (i,C) into V V (i,C) . C" is obtained as the image of C by this linear mapping. This defines the lifting of C into C" (see illustration in Figure 5 for i = 1).

• CompEls of VWX that are initially located within V P i P i+1 are lifted to the triangle V P i P i+1 by keeping their barycentric coordinates unchanged within these two triangles.

Stop condition.

The index i is incremented until we reach the value I such that P I+1 and P I+1 are not located in the interior of the segments V X and V V I+1 (stop condition). In that case, V is projected onto P within the triangle VV I V I+1 (this is illustrated in triangle VV 2 V 3 of Figure 5). The CompEls of VWX initially included in V P I V are lifted to the triangle V P I P. It is also necessary to compute P" as the intersection of V P with V I V I+1 . CompEls located inside the triangle VV I P", are lifted within the quadrangle P P I V I P". When the stop condition is met, we do not move to the next triangle and the index i is not incremented.

In the same way, if P 1 and P 1 do not belong to the segments V X and V V 1 respectively, we project V on the triangle V XV 1 at point P (and compute P" as described above). The subtriangle V XV (within VWX) is then lifted to V XP (within V XV 1 ). CompEls located inside the triangle V XP" are lifted to the triangle P XP", and no iteration is performed on i.

The same process is performed starting from the edge VY in the direction of V n , from WX in the direction of W m and from the edge WY in the direction of W 1 . If any triangle incident to vertex V is not reached by these four iterations, it keeps its CompEls unchanged. Figure 5 illustrates the strategy's results and the CompEls' barycentric coordinates update.

Edge flip

In nearly planar areas, edge flip is a preferred alternative to edge split and edge collapse, whenever it is sufficient to restore the level of detail d or the quality of a triangle. This favours a better stability of the quasi-uniform sampling since it prevents creation and destruction of vertices.

Whenever an edge V 1 V 2 is replaced by its flipped counterpart V 3 V 4 , one first calculates the pair of points P and P on the edges V 1 V 2 and V 3 V 4 that minimize the distance between the lines supported by these edges. Compel barycentric coordinates are first updated as if V 1 V 2 was to be split in P. CompEls of the triangle

PV 3 V 1 (resp. PV 1 V 4 ) are then lifted to P V 3 V 1 (resp. P V 1 V 4 ). Since P is on V 3 V 4 we then proceed the in- verse of a split barycentric coordinate update to merge P V 3 V 1 and P V 1 V 4 into V 4 V 3 V 1 . The same thing is done on the other side of V 4 V 3 . V 1 V 2 V 3 V 4 X Y W 2 W 3 W 1 (a)
The original neighborhoods of two vertices before ring join.

V 1 V 2 V 3 V 4 W 2 W 3 W 1 (b)
The two vertices are removed and the two neighborhoods are stitched together.

V 1 V 2 V 3 V 4 W 2 W 3 W 1 V 3 W 3 (c)
Resulting connectivity unwind at the edge V 3 W 3 (shown in green, duplicated)

Change in topological genus

Whenever the distance between two vertices located in different sides of the quasi-uniform mesh becomes smaller than the minimum thickness t, the shape locally flattens and breaks. This amounts anticipating intersections and changes in topological genus. This change is performed through vertex ring join of the two vertices [START_REF] Stanculescu | Freestyle: Sculpting meshes with self-adaptive topology[END_REF]. It can cause major topological and visual changes in the mesh. In order to maintain a minimum temporal continuity, we propose to reuse destroyed facets to join the vertices. The faces and their corresponding CompEls are maintained by merely replacing the joining vertex with the selected one in the other ring. This effectively stitches both 1-rings together, as depicted in Figure 7.

Rendering

Storing and rendering, in real time, a large number of Com-pEls can be a considerable technical challenge. A single model can have tens of thousands of CompEl instances, which can hinder performances due to a sheer triangle count. Using the capabilities of the graphic card can be useful for that challenge. We also use the programable rendering pipeline to lower visual problems related to CompEls intersecting one another, which is a problem not commonly present in traditional 2D texture bombing. Finally, we will explain how our system is compatible with the introduction of variability in the models of Com-pEls being used without loosing the benefits of instancing. In this section, we outline the algorithms employed to improve the geometric quality, variability and rendering time of a large number of CompEls.

Variability

CompEl models are displayed using traditional instancebased rendering. This means that we use a single CompEl model, and that the graphic card performs the numerous mesh instantiations of this model. This alleviates memory requirements in the graphic card and allows us to render a large number of objects in real time. Variability can be introduced directly during instancing. Given a very small number of input models, we are able to synthesize a possibly large number of different CompEls. We control variations between CompEls originated from the same model by means of a randomisation seed, assigned to each element, that is used by shader operations.

The first source of diversification are textures. Increasing the number of different textures applied to CompEls can increase variability without increasing connectivity complexity. Different textures are stored and made available in an array. The one used can be picked on the fly using the randomisation seed. Figure 8 illustrates the concept.

We compound differentiation by adding low frequency noise to the positions of CompEl vertices. A low frequency noise can be efficiently generated in the graphic card by a number of algorithms. We opted for a Perlin Noise-like function, as defined in [START_REF] Gustavson | Simplex noise demystified[END_REF]. Noise intensity is evaluated using vertex normals offset by the randomisation seed. The resulting noise strength is applied as a vertex displacement along its normal direction (Figure 9).

"Back CompEl" Culling

Backface culling and clipping algorithms are common place in modern graphic cards. CompEl meshes, after vertex processing in the rendering pipeline, can already be automatically clipped out. If they are not, however, there will usually be triangles on their surface facing the camera (always, if they are closed manifold inside the viewing frustum). In crowded composite objects, this may result in several hidden CompEls being passed on to primitive assembly and fragment processing.

We can alleviate the problem by discarding all the CompEls that face away from the camera. At the level of each vertex (in Normalized Device Coordinates (NDC)), we compare the quasi-uniform mesh normal closest to the CompEl's barycentre and the eye vector. If the CompEl is deemed backfacing, we displace the vertex outside the viewing frustum, resulting in the entirety of the CompEl being clipped. Figure 10 illustrates this technique.

Visual intersection prevention

Intersections in a scene are a constant concern in computer graphics [START_REF] Gain | Preventing self-intersection under free-form deformation[END_REF]. Applications that work with 3D objects clumped together usually solve this problem by making use of physical simulations, polygonal collision tests or other indirect methods, such as bounding boxes, to prevent pairs of rigid objects from intersecting each other. Collisions can not only be costly to identify, but also troublesome to solve when more than two objects are involved. Our framework aims at being fully local in order to better support interactive sculpting times, so we cannot resort to costly collision detection calculations.

To tackle the issue, we propose a CompEl squish in the rendering pipeline. After transformation to the Normalized Device Coordinates, we add a displacement to CompEl vertices perpendicular to the canvas. We move the vertex so that its depth approaches the same depth as its CompEl's projected center of mass. As per [START_REF] Gain | Preventing self-intersection under free-form deformation[END_REF], this deformation can be represented as a simple linear scale in a cubic set of hyperpatches around the CompEl. This squish operator cannot cause any new selfintersections in a mesh, as long as the scale factor s is less than 100%. Also, since the displacement is perpendicular to the canvas, only the intersection of objects with different centers of mass is altered. The rendering of individual CompEls is not affected. In the limit case, when s = 100%-, all CompEls become equivalent to parallel 2D images, which cannot intersect (Figure 11). Though arguably ideal for static viewports, applying the squish operator with s = 100%-may generate animation artifacts. As the camera rotates, CompEls that were behind other CompEls may suddenly pop to the front. This is a direct consequence of CompEls whose centers of mass become closer to the canvas than the other CompEls' center of mass. It is also theoretically possible, though not observed in our tests, to experience z-fighting between squished CompEls. Both of these problems can be minimized by allowing some small intersection, through the reduction of s. This dilutes the popping effect for several frames. Notice also that it is possible for the squish to change the rendering of a CompEl that is only partly contained by the volume.

Results

Our CompEl redistribution algorithm greatly limits the number of CompEl insertions and deletions on all basic topological operations performed on the anchor mesh, as can be seen in Table 1 with respect to Figure 12. In our tests, the number of CompEls created and removed on deformation was reduced by more than 70% when compared to simple populating of newly The framework is capable of conveying several different types of composite materials. Figure 13 shows the resulting sculpture of dissociated elements. We also show that it can create significant element variation from a limited initial set.

The system allows for very smooth and intuitive sculpture at interactive rates, being suitable for the use of digital artists of all backgrounds, as shown in Figure 14.

Our frames per second are on par or more efficient than the Visual continuity is ensured by the seamless creation and destruction of CompEls on surface stretch and by their redistribution between faces affected by changes in connectivity.

Newly inserted elements sprout seamlessly from inside the sculpted object, giving the impression they were always there to begin with. Similarly, excess elements are first pushed from sight towards inside the shape before disappearing.

Conclusion

Interactive virtual sculpting of composite shapes remains a challenge in Computer Graphics. We proposed an empirical approach that helps deforming an agglomeration of component elements in real time. We believe that a real-time approximate solution for these problems, such as ours, is of interest to the virtual creation of shapes. Sculpting is a creating process rather than a mere reproduction of a preconceived model. Therefore, the artist needs to assess the tentative result of his work on the fly, even if at an approximative scale, before the final quality rendering is performed. For this to be possible, we concentrate on the elements that are present on the most superficial layers of the shape being sculpted. Secondly, rather than modeling the interactions between the component elements, we only maintain the properties of their relative placement. This can be performed by setting and tracking a dynamic uniform sampling of the shape that is useful to characterize the local evolution of the surface. A CompEl results from the coupling between a com-ponent element and a triangulation of the uniform sampling. Of course, such a system does not completely cover the problems of intersection between CompEls since we do not focus on those interactions. We do, however, employ visual "tricks" into the graphics pipeline to display elements as if they were entirely separate and non-overlapping. The results obtained so far are very satisfying and allow the user to create and deform composite shapes fluently. Future research could focus on the efficient use of CompEls with high-density meshes. Research could also be done to allow for the simultaneous sculpting of regions with different densities and other, non-uniform, CompEl distribution. Our perspective is now to extend this approach to more complex components, such as hair, to better use surface curvature information and to further exploit the possibilities offered by the graphics card.

Figure 1 :

 1 Figure 1: Carnival mask sculpted using our framework. Left: input CompEls and accompanying textures. Center: initial sphere mesh and intermediate steps of the sculpting process, with and without CompEls on the outer surface. Right: final rendering.

Figure 2 :

 2 Figure 2: Agglomerates.

Figure 5 :

 5 Figure 5: CompEls redistribution on edge collapse performed on a planar surface. In both images, the original (in grey) and modified (black) connectivities are shown overlaid. CompEls are colored according to their originating faces. Top: CompEls are shown in their initial positions (that also correspond to their projections on the new faces, without moving: in that case, the determination of the resulting barycentric coordinates would requires search for the adequate face). Bottom: Compel distribution on edge collapse by using the proposed heuristic. CompEls are shown in their final position: they are pushed within their originating faces being deformed to make room for the CompEls of the faces being destroyed (colored areas illustrate the reassignment).

Figure 6 :

 6 Figure 6: 3D illustration of region lifting, in the general case of non-planar surfaces. CompEls belonging to the triangleV 1 V X (in light-red) are lifted to the subregion V 1 P 1 X (darker red) of triangle V 1 V X.The dotted line reveals the shortest segment between edges (V X) and and (V V 1 ).

Figure 7 :

 7 Figure 7: CompEl redistribution on ring join operations.

Figure 8 :

 8 Figure 8: The same rock mesh can be used with different textures to generate different CompEls.

Figure 9 :

 9 Figure 9: Adding noise to a rock mesh can generate different pebbles.

  (a) CompEls distributed along a surface in NDC. The screen and the viewing vector are shown on the left. CompEls placed where the surface normal forms an angle smaller than 90 • with the viewing vector, shown dotted in red, are sent outside the NDC to be clipped. (b) Model rendered without culling. (c) Model rendered with culling.

Figure 10 :

 10 Figure 10: Back CompEl culling.

  View from the camera before (left) and after (right) squish.

  A hypothetical side view before (left) and after (right) squish reveals that the two intersecting CompEls had their vertices moved towards the depth of their respective centers of mass in the NDC.

Figure 11 :

 11 Figure 11: Particle Squish.

Figure 12 :

 12 Figure 12: Example sculpture created from a sphere. Left: pills used as Com-pEls show their relative frequency and texture distribution. Right: the final result. Time taken: 10-15 min.

Figure 13 :

 13 Figure 13: "Flight of the hummingbirds". CompEls sampled from simple quasi-uniform cloud meshes.

Figure 14 :

 14 Figure 14: "My World". Example sculpture by a 6-year-old from candy meshes reveal how simple it is to sculpt with the framework. A zoomed view shows individual CompEls. The artist is shown on the left, looking at his creation.

Table 1 :

 1 CompEl creation and destruction for the sculpture in Figure 12. The number of CompEls is shown as a function of the required density e.

	Variable # Initial # Created # Removed # Final
	Edge Splits			41263
	Edge Flips				13573
	Edge Collapses			30122
	Vertices Ring join			22
	Area	12.52	N/A	N/A	8.78
	Vertices 1026	41270	30197	12099
	Faces	2048	82526	60384	24190
	CompEls
	e =3986 48882	27469	41844	34507
	e =797	8911	66	3855	5122
	e =341	3328	14	1128	2214

rendering of a equivalent number of polygons due to our back CompEl culling algorithm. The performance, however, can be significantly diminished if CompEl meshes are dense.

Acknowledgements

Artur P. Sampaio acknowledges CAPES for the fellowship (PDSE Proc. 14495/13-9). This work was also funded by the Programme Avenir Lyon Saint-Etienne (PALSE) at the Université Claude Bernard Lyon 1.


Jabier Martinez

Tewfik Ziadi
email: tewfik.ziadi@lip6.fr

Tegawendé F Bissyandé

Jacques Klein

Yves Le Traon

Automating the Extraction of Model-based Software Product Lines from Model Variants

We address the problem of automating 1) the analysis of existing similar model variants and 2) migrating them into a software product line. Our approach, named MoVa2PL, considers the identification of variability and commonality in model variants, as well as the extraction of a CVL-compliant Model-based Software Product Line (MSPL) from the features identified on these variants. MoVa2PL builds on a generic representation of models making it suitable to any MOF-based models. We apply our approach on variants of the open source ArgoUML UML modeling tool as well as on variants of an Inflight Entertainment System. Evaluation with these large and complex case studies contributed to show how our feature identification with structural constraints discovery and the MSPL generation process are implemented to make the approach valid (i.e., the extracted software product line can be used to regenerate all variants considered) and sound (i.e., derived variants which did not exist are at least structurally valid).

I. INTRODUCTION

In the realm of software engineering, models, which are high-level specifications of systems, have progressively taken importance for researchers and practitioners as the primary artefacts of development projects. Traditionally, modeling has been used in a descriptive way to represent systems by abstracting away some aspects of the systems and emphasizing others [START_REF] Voelter | DSL Engineering -Designing, Implementing and Using Domain-Specific Languages[END_REF]. Nonetheless, prescriptive modeling is now trending and is relied upon to automate the generation of products as well as their validations [START_REF] Schmidt | Model-driven engineering[END_REF]. In this context, models are often extended, customized or simply reconfigured for use in particular system settings. Thus, an important challenge in Model-Driven Engineering (MDE) is to develop and maintain multiple variants, i.e. similar models, by exploiting the features that the models share (commonalities) and managing the features that vary among them (variabilities) [START_REF] Apel | An overview of feature-oriented software development[END_REF]. To address this problem, which is relevant to many kinds of software artefacts, Software Product Line (SPL) engineering [START_REF] Northrop | A Framework for Software Product Line Practice, Version 5.0[END_REF] has matured as an approach for 1) managing the commonalities and variabilities of a product family and 2) managing the derivation of tailored products by combining reusable assets.

Unfortunately, SPL adoption is still a major challenge in industry [START_REF] Kästner | Variability mining: Consistent semi-automatic detection of product-line features[END_REF], [START_REF] Dubinsky | An exploratory study of cloning in industrial software product lines[END_REF]. Instead, practitioners use to rely on adhoc mechanisms, such as copy-paste-modify, to perform reuse when creating similar products. It has even been reported that more than 50% of industrial practitioners formally implement an SPL only after the instantiation of several similar variants using ad-hoc reuse techniques [START_REF] Dubinsky | An exploratory study of cloning in industrial software product lines[END_REF]. Figure 1, that will be discussed later, illustrates ad-hoc reuse for variants creation and the circumstances to consider the adoption of more advanced variability management approaches. However, migrating product variants into an SPL is a known challenge in SPL engineering [START_REF] Lopez-Herrejon | Second international workshop on reverse variability engineering (REVE 2014)[END_REF], [START_REF] Rubin | Cloned product variants: From ad-hoc to well-managed software reuse[END_REF]. Several approaches, referred to as extractive or bottom-up approaches, have been proposed for source code artefacts. In this work, we focus on models, and propose an end-to-end solution for dealing with the two requirements for building a bottom-up approach to the adoption of Model-based Software Product Lines (MSPL):

• Feature identification. Analysing and comparing the existing model variants (i.e., models that are used using ad-hoc reuse techniques) to identify commonality and variability in terms of features. A feature is a prominent or distinctive characteristic, quality or uservisible aspect of a software system or systems [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF]. • Reengineering. Once features are identified, and the constraints among them are detected, extractive approaches should propose a transformation phase where the model variants are actually refactored to conform to an SPL approach.

With MoVa2PL (Model Variants to Product Line) we address simultaneously in a single framework both requirements for extracting an MSPL from model variants. In the realization of our approach, we used the Common Variability Language (CVL) [START_REF] Haugen | CVL: common variability language[END_REF] to implement the MSPL. The benefits of this work for easing the adoption of SPL engineering for models are numerous. Indeed, first, adopting an MSPL, as for any other kind of SPL, will allow practitioners to easily and efficiently propagate changes done in one feature to all existing variants by simply re-deriving them automatically. Second, the extracted MSPL can be relied upon to derive efficiently new products by combining features. This work does not focus on the challenging problem of model similarity analysis in the sense that we assume that the variants are not independently generated out of the same family of systems.

The contributions of this work are: 1) We provide an approach for commonality and variability analysis that includes the automatic detection of constraints between identified features. 2) We propose a method for MSPL reengineering to automatically extract a CVL-compliant MSPL. 3) We assess the approach with two case studies.

The remainder of this paper is structured as follows: Section II summarizes our previous work on feature identification in models and presents the motivation to MSPL adoption. Section III presents our approach. Section IV presents experiments based on case studies with large real-world systems. Section V discusses the approach and its limitations. Section VI presents related work. Finally, Section VII concludes this work and outlines future directions. In previous work we introduced MoVaC [START_REF] Martinez | Identifying and visualising commonality and variability in model variants[END_REF] as a metamodel independent approach for comparing simultaneously a set of model variants in order to identify commonality and variability. The approach was flexible to apply or integrate different matching techniques. Figure 2 shows the proposed process whose objective was to help domain experts in feature identification. The approach was designed to support concepts from the Meta-Object Facility (MOF) [START_REF] Omg | Meta-Object Facility (MOF) Core Specification[END_REF] which is a wellknown standard in MDE.

Each model variant is decomposed into Atomic Model Elements (AMEs) since models are artefacts that can be expressed as a sequence of elementary construction operations [START_REF] Blanc | Detecting model inconsistency through operation-based model construction[END_REF]. The computed AMEs are either of type Class (not to be confused with UML classes), Attribute or Reference. Then, we proposed an algorithm, called Interdependent AMEs, which automatically identify sets of AMEs that correspond to the distinguishable features from the model variants. We named Blocks to these sets of AMEs. Unfortunately, MoVaC has two main limitations: although it helps in feature identification, (1) it does not manage to identify the constraints that exist among the features and (2) it only focuses on one part of Fig. 2: Model Variants Comparison (MoVaC) approach to identify and analyse commonality and variability the problem for MSPL extraction since it does not propose a method to extract an SPL from the identified commonalities and variabilities.

We present in Figure 1 our running example illustrating a scenario of building UML model variants for different banking systems [START_REF] Ziadi | Feature identification from the source code of product variants[END_REF], [START_REF] Ziadi | Software product line engineering with the UML: deriving products[END_REF], [START_REF] Atkinson | Component-based Product Line Engineering with UML[END_REF]. In this scenario we have created three models through ad-hoc reuse processes with variations on the limit of bank withdrawal, the consortium entity and currency conversion. Thus, the first created variant, Bank 1 UML model, is implemented with information related to currency conversion and consortium. The Bank 2 UML model includes a new requested feature that is the support of a limit in the withdrawal. This new banking system does not however need consortium. Thus, in order to create it, we consider a copy of Bank 1 where we added one UML property, two UML operations, we modified the name attribute of a UML operation and we removed the UML class Consortium and all its related UML elements (one UML class and two UML operations). The needs of Bank 3 on the other hand include limit in the withdraw and consortium, but no currency conversion. To create this variant, we build from a copy of Bank 2 where we removed all UML elements related to currency conversion (one UML property, four UML operations and one UML class). However, we also selected and copied UML elements from Bank 1 variant to complete the implementation of this Bank 3 variant.

The building of variants for such a basic running example aims to illustrate how time-consuming and error-prone the manual creation of variants can be in real-world complex scenarios. This manual process quickly ceases to be sustainable if we consider the possibility that continuously creating new variants will require even more effort in finding, selecting and reusing elements from other variants. Furthermore, because of a lack of an explicit formalization of feature relationships, potential inconsistencies in the requested features for a new variant will be found during/after the variant creation.

To extract an MSPL from the variants of our running example, feature identification would consist in analysing the three UML variants of Figure 1 to identify the core elements of a banking system and the different features related to currency converter, consortium and limit support, as well as the constraints among them. Reengineering will then exploit the identified features and the existing variants to build the necessary assets for the MSPL.

In MDE, CVL [START_REF] Haugen | CVL: common variability language[END_REF] is a modeling approach that is specialized for implementing MSPL in a non-invasive, language independent way. CVL further provides the necessary expressiveness to support systematic reuse for the derivation of models [START_REF] Czarnecki | Cool features and tough decisions: A comparison of variability modeling approaches[END_REF]. CVL was thus designed to simplify a topdown approach to the adoption of MSPL, where practitioners directly write the assets for defining the MSPL. In a bottomup approach, the challenge is to leverage existing variants to extract these assets. CVL consists of two layers:

• Variability definition layer: This layer defines the variability of the domain in a very similar fashion as feature modeling. Feature modeling is the most widely used formalism in SPL engineering to represent the features of a product family and the relationships between them [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF]. • Product realization layer: The replacement actions in a Base Model must be defined according to the variability specification.

In this work we are concerned with the following research questions: RQ1: Based on existing model variants, can we derive automatically a Variability definition layer that ensures the validity of the configuration space? RQ2: Can we automatically infer a Product realization layer for variants of complex systems?

III. EXTRACTION OF MODEL-BASED PRODUCT LINES WITH MOVA2PL

The overall process of MoVa2PL is illustrated in Figure 3. In the first step, we leverage MoVaC [START_REF] Martinez | Identifying and visualising commonality and variability in model variants[END_REF] to decompose the model variants into AMEs (the Decomposition in Atomic Elements including dependencies step of Figure 3) and we perform Block and Feature identification. Block identification is performed by computing the interdependence among AMEs. As defined in our previous work [START_REF] Martinez | Identifying and visualising commonality and variability in model variants[END_REF], given a set of model variants MV s, two AMEs ame 1 and ame 2 (of models from MV s) are interdependent if the two following conditions are fulfilled:

1

) 9M 2 M V s ame 1 2 M ^ame 2 2 M 2) 8M 2 M V s ame 1 2 M , ame 2 2 M
A Block is thus a set of interdependent AMEs that are distinguishable in the model variants. Feature identification is a semi-automatic process where domain experts manually review the elements from the identified blocks to map them with the functionalities (i.e., features) of the system.

However, we augment the information of AMEs with the computation of all dependencies among AMEs in all variants. Thus, once the features are already identified, we can implement a Constraints discovery step which will allow a more reliable definition of the variability model for the MSPL.

Also we modify the decomposition process. In MoVaC we considered only the attributes and references which have not the property of being derived, volatile or transient. For example, if an attribute has the derived flag in a given metamodel, it means that its value is automatically calculated from other attributes or by some function, thus MoVaC does not add this as attribute AME during decomposition of the model in AMEs. In MoVa2PL, apart from these conditions, we also add the condition that their values must have been set before (e.g. non null values or empty lists of referenced elements).

As presented in Figure 3, MoVa2PL has a Visualisation layer that covers its different steps. Indeed, as we will show above, real-world case studies yield model variants that can be large and complex with a high number of model elements and constraints. Apart from automating the process of extracting MSPL, MoVa2PL uses visualisation techniques [START_REF]Readings in Information Visualization: Using Vision to Think[END_REF] to help domain experts to visually analyse, not only the results of this automation, but also the intermediary results in order to provide a better understanding of the automatic underlying process. The generation of feature constraints' graphs is thus automated in MoVa2PL.

The tool-support of MoVa2PL is implemented and integrated in the Bottom-Up Technologies for Reuse framework [START_REF] Martinez | Bottom-up adoption of software product lines: a generic and extensible approach[END_REF]. In the following subsections we provide details of the constraints discovery strategy and the MSPL extraction.

Fig. 3: MoVa2PL Process

A. Structural constraints discovery

Variability modeling in product line engineering is known as an efficient paradigm to describe at once several variants of a system. Precisely specifying a variability model is essential to guarantee that any derived model is valid. A structurally valid model is a model that does not violate any constraint defined in the meta-model such as cardinality of the model references or the non existence of dangling elements (i.e. an element that does not have a parent). Semantic validity of model variants, which is checked by domain experts, is out of the scope of this paper. In this section, we focus on how we compute the dependencies between AMEs and how, by reasoning on these dependencies, we infer constraints between features to ensure that the models that will be derived from the extracted MSPL are structurally valid.

1) Dependencies between Atomic Model Elements:

A dependency involves a pair of AMEs and it has an ID which corresponds to the dependency type. Each dependency type has an upper bound representing the maximum number of times an AME can be referenced with its dependent counterpart.

The AME dependencies are calculated as following:

• Class: A class AME depends on its parent class AME. By parent we mean the container relation (not to be confused with inheritance in a UML sense). The dependency ID is the ID of the containment reference as it was given in the meta-model. The upper bound is the containment reference upper bound. For instance, from the running example, the class AME UML Operation deposit depends on the class AME UML Class Account, its dependency ID is ownedOperation and, in this case, there is no upper bound given that a UML Class can have unlimited owned operations.

• Attribute: An attribute AME depends on the class AME that hosts the attribute. The dependency ID is the ID of the attribute. The upper bound is 1 in the sense that a class cannot have the same attribute twice. As an example of such dependency we note that any UML Operation has an attribute AME name.

In UML Operation deposit, the attribute AME name depends on UML Operation deposit and there can only be one attribute name.

• Reference: A reference AME depends on the class AME that hosts the reference and on each of the class AMEs that are referenced. The dependency ID is the ID of the reference in the case of the host class, and the hard-coded value referenced is used as ID for the dependencies to the referenced class AMEs. The upper bound in a dependency with the host is 1 as it happened for the attribute AME. However the upper bound in a dependency with referenced classes is unlimited given that a class AME can be referenced as many times as desired. From the running example we note that the reference AME Type of UML Parameter amount depends on UML Parameter amount and also depends on the class AME UML Primitive Type double.

Figure 4 shows the AMEs of Bank 1, Bank 2 and Bank 3 and their corresponding dependencies using a directed graph visualisation. All the graphs shown in this paper are automatically generated by MoVa2PL. The direction of the edges are clockwise. We can see how the class AMEs (in black) are surrounded by the attribute AMEs (light color) and reference AMEs (dark color) that depend on each class AME. We can also see, as black edges, how some class AMEs depend on other class AMEs through a containment relation (given that a class depends on its parent class AME). The graph shows how attribute AMEs only depend on their corresponding host class AME. On the contrary, we can see the reference AMEs that, besides their host class AME, also depend on the referenced class AMEs.

2) Requires constraints discovery: For the discovery of structural constraints between features we reason on the dependencies of the AMEs. In order to avoid dangling elements in derived models after MSPL construction, we identify the requires constraints that will assure that all the model classes (except the root) will have a parent. We also identify the requires constraints between any pair of features where one feature needs the other in order to be successfully integrated in a system variant.

In Figure 5 we show the blocks that were identified by computing the interdependence between AMEs. The BankCore Feature, which corresponds to the first block (Block 0), comprises most of the AMEs. Specifically, it comprises those that are common for all model variants. On the contrary, We can see how most of these dependencies are intra-feature structural dependencies given that they exist between AMEs corresponding to the same feature. However, we can see inter-feature structural dependencies that in this case are all in the direction to the Block 0 (i.e., BankCore feature). We identify the requires constraint between two features when at least one AME from one feature has a structural dependency to an AME of the other feature. Figure 6 thus shows the discovered requires constraints in the running example.

3) Mutual exclusion constraints discovery: Cardinality in model references plays an important role in defining a domain specific language. These cardinalities define constraints in the domain that must not be violated to obtain valid models. To avoid violation of upper bound cardinalities we identify in which cases two features cannot coexist in the same model (mutual exclusion constraint).

To illustrate upper bound cardinalities in real scenarios, and following with the context of the running example, we discuss the cardinalities of the widely used UML meta-model. In the case of the UML meta-model, as implemented in Eclipse UML2 ecore, we have 242 classes with a total of 3113 nonvolatile, non-transient, non-derived references. 67.7% of these references have no upper bound. 32.2% of them have an upper bound of 1 maximum referenced model classes. The remaining 0.1% corresponds to the DurationObservation meta class which allows to model execution durations in UML. This class has the event reference with an upper bound of 2 UML NamedElements. If the upper bound of a containment reference is 1, that means that it is structurally invalid to try to reference 2 different containments at the same time. Figure 7 illustrates an example where a structural invalid model is created by combining two features. In the UML meta-model, the TimeEvent class has the when containment reference with an upper bound of 1 to a TimeExpression class. Therefore, it is not valid to reference two TimeExpression classes using this reference. Suppose we have a class AME TimeEvent that is part of the common feature and then two different class AME TimeExpressions belonging to two different features. Both class AME TimeExpressions will have a dependency to the same TimeEvent class AME. The dependency type of both dependencies correspond to the when dependency ID that has an upper bound of 1. Given such information we can identify mutual exclusion constraints between two features when the sum of the dependencies of a given dependency type that points to a given AME from one feature and the dependencies which points to the same AME with the same dependency type from the other feature, exceeds the defined upper bound of this dependency type. This is applicable also for the reference AME and for the attribute AME. In our running example, we have two attribute AMEs that depend on the same UML Operation class AME with the name dependency ID. In one of them the value is withdrawWithLimit and in the other is withdrawWithoutLimit. These attribute AMEs correspond to two different features and only 1 can be used in a derived model. This discovered constraint is made visible in Figure 6 by an "excludes" link between the two features.

B. CVL models generation

Different strategies can be selected for implementing an MSPL ranging from additive, subtractive or hybrid approaches [START_REF] Zhang | Developing model-driven software product lines[END_REF], [START_REF] Perrouin | Reconciling automation and flexibility in product derivation[END_REF]. The additive approach relies on a Minimum Base Model composed only by the Core of the family of models, i.e. the model elements that are common to all model variants. Then the approach requires Library Models which will contain the model fragments to be added to the Base Model. On the contrary, the subtractive strategy consists in constructing the Maximum Base Model (also known as 150% model) and then removing the model elements related to each of the non selected features. Hybrid approaches use a mix between subtractive and additive strategies by providing to some extent Library models and still leaving the possibility to subtract from the Base Model. In MoVa2PL, we rely on a subtractive strategy. Notice that it is possible to construct a Maximum Base Model even if the resulting Base Model violates reference upper bounds. It will be the responsibility of the resolution model to operate in the Base model to bring it to a valid state. The following paragraphs explain how the CVL layers, described in Section II, are created. Using these layers, CVL implementations provide an engine to automatically transform the Base model in a resolved model.

Variability model: The variability model is created using information from the identified features and the discovered constraints. Figure 8 shows the CVL variability model created from the three model variants of the running example. The steps for its creation are as follows:

1) Identified features are added as well as their negations. Feature negations are needed to differentiate the actions of the resolution layer given that the negation will be the responsible to remove the model elements in this subtractive strategy. 2) Discovered structural constraints, as presented in Section III-A, are added as propositional logic formulas. 3) Mutual exclusion constraints are added to avoid selecting a feature and its own negation. 4) Configurations, in terms of features in the existing model variants, are added. These configurations are called resolution elements. The resolution elements will trigger the actions on the Base Model to regenerate the existing model variants.

In this example, three resolution elements are created in step 4 correspond to existing variants. However, with the features and constraints shown in Figure 8 as result of the steps 1, 2 and 3, there are eight possible valid resolution elements. Therefore five additional models can be derived using different combinations of feature selections.

Base model: The Base model creation is a realization of an n-way model merge, a technique that has proven to produce better results than pairwise merging [START_REF] Rubin | N-way model merging[END_REF]. We leverage the feature identification approach with its computation of Interdependent AMEs where the model matching is performed. Figure 5 already showed the hyper-set of all the AMEs from the Model variants. These AMEs are the result of an n-way matching. In order to create the Base Model, we start from the class AME that is marked as the initial resource (i.e. the root) and we automatically construct the Base Model from scratch with the information contained in each AME using: 1) an in-depth tree traversal of the containment dependencies creating the MOF classes and setting their attributes; and 2) a second phase where the references are set to the corresponding classes in the Base Model. In this process, there is neither need to consider if upper bound cardinalities are being violated, nor that there are attributes in the Base Model that are already set. In these cases, as discussed before, the resolution model is responsible for providing information to adjust it at resolution time. Figure 9 shows the Base Model obtained from the variants of our running example. Resolution model: Given that we are following a subtractive strategy, each feature negation will be resolved by removing the feature's corresponding classes. For this, we create three CVL elements for each feature negation: A placement fragment, a replacement fragment and a fragment substitution element. The placement fragment defines the model elements from the Base Model that will be replaced with the replacement fragment. This replacement fragment consists actually of an empty fragment. The fragment substitution element just relates the placement and replacement fragments. Figure 10 shows the overall process to obtain a resolved model.

Figure 11 shows an excerpt of the resolution model for our running example. Notice that in the CVL implementation that we are using [START_REF]CVL Tool[END_REF], the resolution layer is defined inside the variability model itself so the resolution information is contained in each of the features presented before in the variability layer. In the case of No CurrencyConverter we can see a Placement fragment that encompasses all the classes related to CurrencyConverter. In Figure 9, the classes that are inside the placement fragment of No CurrencyConverter are highlighted in dark color. The placement also includes the FromPlacement. In the FromPlacement we specify all the classes that are referenced from any class of the placement classes and from any class in the contents of the placement classes. These classes are highlighted in light color in Figure 9. This placement information will allow, at resolution time, the removal of the CurrencyConverter feature by its substitution with the empty replacement. Regarding attribute and reference AMEs, if the class AME that hosts this AME is not in the same feature, we need to add a placement, replacement and substitution elements to the resolution information of the feature associated to the attribute or reference AME. For example, in the WithdrawWithoutLimit feature we add a Placement value in the name attribute of the corresponding Operation class and we add a replacement value with the String of the value of the attribute AME. At resolution time, if WithdrawWithoutLimit is selected, this attribute value will be assigned. For reference AMEs it is the same approach but Object placement, replacement and substitution are used.

IV. EXPERIMENTAL ASSESSMENT

In this section we discuss the assessment of MoVa2PL. First, we describe the case studies of real-world systems that we rely on to evaluate our approach. We then present characteristics of the extracted MSPL for the case studies. Finally, we summarize the evaluation of the MoVa2PL where we checked its efficiency to extract an MSPL for large models, and its effectiveness to derive back the existing models and new valid model variants.

A. Case Studies

ArgoUML Case Study: ArgoUML is an open source tool for UML modeling. Variants from this tool were created from its Java codebase by removing specific features [START_REF] Couto | Extracting software product lines: A case study using conditional compilation[END_REF]. These features are mainly related to the tool support for the edition of different kind of UML diagrams (i.e. Activity, Collaboration, Deployment, Sequence, State and UseCase diagrams). We reverse engineered the source-code of the original ArgoUML and the 6 variants related to diagram edition support as UML models in order to apply MoVa2PL. Concretely, the first column of Table I enumerates these variants. As example, the first one, ActivityDisabled, means that this model variant contains all the features related to UML diagrams' edition except Activity diagram. These models contain more than 50K classes. Table I shows the AMEs obtained after MoVa2PL decomposition of the models.

The decomposition in AMEs for the 7 model variants, including the dependencies, took an average of 15 seconds (i.e. around 2 seconds per variant) using a lap-top Dell Latitute E6330 with a processor Inter(R) Core(TM) i73540M CPU @3.00GHz 3.00GHz, 8GB RAM, with Windows 7 and 64bit Operating System. The Interdependent AMEs identified 41 Blocks and took an average of 7 minutes. Table II shows the result of the identified blocks and their size in terms of AMEs.

We manually analysed the blocks in order to identify the features. The meaning of the blocks from 0 to 6 were easily recognisable by looking at the textual description of its associated AMEs. Block 0 corresponds to the Core of ArgoUML, Block 1 to UseCase diagrams edition, Block 2 to Sequence, Block 3 to Collaboration, Block 4 to State, Block 5 to Deployment and Block 6 to Activity diagrams. These blocks were the bigger ones in terms of number of AMEs because the rest of the Blocks only contain very few of them. We manually checked these small blocks and we realized that most of them contain reference AMEs that, in the UML meta-model, are defined as ordered (i.e. the order of the referenced elements is important). The applied matching method takes into consideration the ordering of the referenced elements and therefore considered them as different. This issue, probably introduced by the Java to UML reverse engineering tool, makes more difficult the work of the domain expert that needs to manipulate and analyse these blocks. However, in terms of size of model elements, the main part of the features were successfully identified by MoVa2PL.

Figure 12 shows the graph visualisation of the discovered structural constraints. Concretely, for the ArgoUML case study 45 requires constraints and 13 mutual exclusion constraints were discovered. These discovered constraints reduce considerably the configuration space of the possible feature combinations. Figure 12 shows that the 6 identified features related to the diagrams depend on the Core feature. The other nodes of the graph correspond to the blocks that the domain expert will need to analyse. These automatically calculated relations between the blocks can also help during this manual process. For example, those blocks that exclude each other should be related and the scope of analysis is narrowed for those blocks that requires another block that is not the Core feature.

Once the constraints are discovered, the CVL MSPL extraction step generates the Variability model, the Base Model and the Realization layer. Figure 13 shows an excerpt of the realization layer related to the UseCase and Sequence features. We can see the Placement fragment containing the ToPlacement relations. The BaseModel was created as the Maximum model from the model variants. The time for the BaseModel creation took an average of 8 minutes and the Variability and Realization layer took 3 seconds.

While in the beginning we had model variants that only considered disabling one type of diagram each, with the extracted MSPL, we can generate ArgoUML UML model variants with any combination of diagrams. For example, we can derive a UML model that only considers ArgoUML Sequence diagrams edition. The mentioned problem identified with the ordering of the references highlight the importance of the matching method during MoVa2PL. MoVa2PL is flexible to apply different matching methods. By providing a matching method that ignores the ordering of the references, 18 blocks were identified in the ArgoUML case study from which the first 7 blocks also correspond to the Core and diagrams' features. The trade-off is that, by ignoring the order, we will be assuming that the order was not important and this design decision on the matching policy requires a manual analysis by the domain expert on the models.

In-Flight Entertainment Systems Case Study: We consider the case study of an In-Flight Entertainment (IFE) System. The IFE system is responsible for providing entertainment services for the passengers, including movies, music, internet connection or games during a flight. The IFE system needs also to adjust its behavior in special circumstances (e.g. when the crew wants to communicate with the passengers or during take-off or landing).

For our experiments we consider an IFE system from the Thales Group. Their IFE system was modelled in Capella. Capella is a systems engineering modeling tool which implements the Arcadia method for system, software and hardware architectural design [START_REF] Polarsys | Capella[END_REF]. A system modelled with Capella consists of 5 layers. The Operational analysis layer captures the stakeholders, their needs, as well as general information of the system's domain. The System analysis layer formalizes the system requirements. The Logical architecture layer defines how the system will fulfil its requirements. The Physical architecture layer defines how the system will technically be developed and built. Finally, the End-Product Breakdown Structure layer formalizes the component requirements definition to facilitate components' integration, validation, verification and qualification. The domain of Arcadia method is realized and tool-supported in Capella by defining a domain specific language consisting of 17 meta-models. These 17 meta-models are highly linked among themselves and they have a total of 411 meta-classes.

We consider in our study 3 model variants of the IFE system. The first one is the Original one and the other two are manually created independently. The second one, called LowCost1 is a variant that does not include the feature for Wi-Fi access for passengers. Figure 14 shows an operational analysis diagram that contains some model elements related to Wi-Fi access. We can see how the Aircraft provides connectivity and the Personal device will allow the Passenger to Browse the internet during the flight. The capability of Wi-Fi access for passengers is propagated to the rest of the model layers such as the System Analysis and the Logical and Physical architecture. The third one, LowCost2, does not contain support for ExteriorVideo allows the passengers to watch, in their personal screens, the exterior of the plane at any time during the flight. This variant is intended for aircrafts that may not have cameras outside the plane.

Following the MoVa2PL process as defined in Figure 3, first the IFE model variants were decomposed in AMEs and the dependencies between AMEs inside each variant were calculated. Figure 15 shows the decomposition of the Original IFE System variant. Table III shows the obtained number of AMEs for each variant.

Our Interdependent AMEs method lead to the identification of 3 blocks. The identified blocks where manually analysed and mapped to the features. Table IV summarizes the number of AMEs for the corresponding features.

In the end of this step MoVa2PL automatically discovers the structural constraints among the different features. Thus, we discovered that both Wi-Fi and ExteriorVideo

B. Summary evaluation of MoVa2PL

For evaluating MoVa2PL, based on the case studies outlined above, we focused on checking that, in each case, the extracted MSPL is able not only to 1) re-generate the previously existing variants using our systematic reuse approach but also to 2) generate previously non-existing variants which are structurally valid. By realizing the experiments on different modeling meta-models, namely UML models and the Capella domain specific language, we demonstrated the flexibility and genericity of MoVa2PL as it worked for the two meta-models. We obtained an exact match of the re-generated models and we generated possible non-existing variants (RQ1 and RQ2). We also checked the structural validity manually and we found that we prevent invalid models (RQ1).

V. LIMITATIONS AND THREATS TO VALIDITY

Currently, our work presents a number of limitations and includes hypotheses which are threats to validity. We now summarize them before discussing related work.

Feature identification is a challenging task and can be complex for domain experts. Automatically identifying features using heuristics may lead to an output where a given marked feature is actually a set of different features. This situation is likely when a set of features came always together in all the variants considered. In this case, the Interdependent AMEs approach cannot distinguish among them. Dealing with this kind of issue is out of the scope of the work presented in this paper. We, however, recommend the MoVa2PL approach to be used when in presence of a wide range of variants, increasing the probability that the minimum number of combinations were available to allow distinguishing all features.

In this work we have also eluded the question of semantic validity of the derived model variants. A semantically valid model is a structurally valid model which also makes sense in the domain (i.e. a combination of features that does not violate any semantic rule of the domain). In our work, the extracted MSPL will allow the creation of new models based on combinations of identified features. These new models may be semantically invalid. The challenging issue of assuring some notion of semantic validity has been addressed in other works such as Czarnecky et al. [START_REF] Czarnecki | Verifying feature-based model templates against well-formedness OCL constraints[END_REF] or in our previous work proposing visualisation schemes [START_REF] Martinez | Feature relations graphs: A visualisation paradigm for feature constraints in software product lines[END_REF].

Finally, MoVa2PL presents some limitation in ensuring the structural validity of models. Indeed, we are not considering constraints that could be defined using the Object Constraints Language (OCL) [START_REF] Czarnecki | Verifying feature-based model templates against well-formedness OCL constraints[END_REF], [START_REF] Omg | Object Constraint Language[END_REF], [START_REF] Warmer | The Object Constraint Language: Getting Your Models Ready for MDA[END_REF]. Also, the constraints discovery only check requires excludes constraints between pair of features. More complex structural constraints involving more than two features are not considered.

VI. RELATED WORK MSPL Reengineering from variants:

There are other extractive approaches that study reengineering of MSPLs from model variants. Zhang et al. [START_REF] Zhang | Model comparison to synthesize a model-driven software product line[END_REF] propose the CVL Compare process that combines EMF compare and the CVL framework to analyse a set of model variants and create a preliminary MSPL model. This approach is similar to our MoVa2PL, however, there are three differences: 1) while we automatically calculate the Base Model, CVL Compare relies on the SPL developer to choose it. 2) CVL Compare is based on EMF Compare two-way comparison mechanism. i.e.; model variants are only compared with each other but not simultaneously. 3) CVL Compare do not consider the identification of constraints. As mentioned below, the structural constraints represent the core aspect in our approach to construct valid MSPL.

Rubin [START_REF] Rubin | Cloned product variants: From ad-hoc to well-managed software reuse[END_REF] and Rubin et al. [START_REF] Rubin | Combining related products into product lines[END_REF] propose the mergerefactoring framework. merge-refactoring is a formal framework to compare UML model variants using what is referred as n-way Model merging [START_REF] Rubin | N-way model merging[END_REF]. Rubin et al. also propose to refactor the input model variants and create an MSPL using the compose operator. While our approach is generic and can be applied to any MOF-based models, the mergerefactoring is only applied to UML models. In addition to the reengineering of the MSPL model, the merge-refactoring framework propose what is referred to as quality-based metrics that guide the refactoring process to ensure that all refactoring produced by the framework are semantically correct. As we presented in this paper, our approach is based on the structural constraints to generate coherent and correct CVL-compliant MSPLs. Koschke et al. [START_REF] Koschke | Extending the reflexion method for consolidating software variants into product lines[END_REF] propose an automated approach for comparing specific model variants that only concern the static architectural view.

Feature identification: Some existing works only consider feature identification without any support for the reengineering step. Assunc ¸ão et al. present a recent survey on these works [START_REF] Assunc | Feature location for software product line migration: A mapping study[END_REF]. For instance, Ryssel et al [START_REF] Ryssel | Automatic variation-point identification in function-block-based models[END_REF] compare model variants that are represented as function-blocks. Ziadi et al. [START_REF] Ziadi | Feature identification from the source code of product variants[END_REF] propose an approach to analyse the source code through the use of UML class diagrams of a set of software variants and identify commonality and variability between them. Apart from not covering the reengineering step, these approaches are not generic to any MOF-based scenario. The tool Fea-tureMapper [START_REF] Heidenreich | Featuremapper: mapping features to models[END_REF] enables manual and automatic mapping of model elements to features. However, their automatic mapping is based on monitoring the developer while is modeling the realisation of a feature.

Feature constraints discovery: Bosco et al. [START_REF] Ferreira Filho | Generating Counterexamples of Model-based Software Product Lines[END_REF] targeted the challenge of generating invalid models from MSPL to be used as counterexamples to refine variability models. Their assumption is that the MSPL exists while we focus on extracting them from variants. The work of Blanc et al. [START_REF] Blanc | Detecting model inconsistency through operation-based model construction[END_REF] also propose an approach for validating sub-models of a monolithic model. In Section V we already discussed Czarnecky et al. work regarding OCL constraints [START_REF] Czarnecki | Verifying feature-based model templates against well-formedness OCL constraints[END_REF] as well as our approach to target constraints discovery through a semi-automatic approach using visualisation techniques [START_REF] Martinez | Feature relations graphs: A visualisation paradigm for feature constraints in software product lines[END_REF]. These works can be complementary to MoVa2PL structural constraints discovery.

Model comparison and splitting: Model comparison have received a lot attention in the MDE community. However, this is often limited to a comparison between two versions of a model. Stephan et al. [START_REF] Stephan | A survey of model comparison approaches and applications[END_REF] and Kolovos et al. [START_REF] Kolovos | Different models for model matching: An analysis of approaches to support model differencing[END_REF] analysed model comparison approaches and provided a classification of them. Model splitting [START_REF] Struber | Splitting models using information retrieval and model crawling techniques[END_REF] is used to reduce the complexity of monolithic models for human comprehension and team collaboration by hiding part of it. These approaches provide heuristics to modularize the model before splitting. However, these approaches focus in single models, not model variants. We consider that model splitting can be complementary in the feature identification process.

VII. CONCLUSION

We have presented MoVa2PL as a solution to MSPL adoption from existing model variants. First, the feature identification process considers structural constraints discovery in order to extract a variability model that ensures the validity of the MSPL configuration space. Secondly, a product realization layer is extracted with the information of the AMEs related to each of the features. This realization layer will operate on a base model extracted by an n-way model merge of the variants. We assessed MoVa2PL in two case studies that consider bigmedium sized model variants with different meta-models. As further work we want to provide a better support for the semiautomatic step of MoVa2PL that is the analysis and naming of the identified features by using advanced information retrieval techniques.

Fig. 1 :

 1 Fig. 1: Three UML model variants fulfilling different bank systems' needs and the manual actions for their creation

Fig. 4 :Fig. 5 :Fig. 6 :

 456 Fig. 4: Visualisation of the decomposition of three model variants into Atomic Model Elements

Fig. 7 :

 7 Fig. 7: Illustrative example of structurally invalid model as result of composing two features

Fig. 8 :

 8 Fig. 8: CVL variability model for the Banking systems

Fig. 10 :

 10 Fig. 10: Subtractive MSPL resolution process with CVL

Fig. 12 :Fig. 13 :

 1213 Fig. 12: Structural constraints discovered for the ArgoUML case study

1

 1

Fig. 14 :

 14 Fig. 14: Operational analysis diagram of the In-Flight Entertainment system variant showing some model elements related to Wi-Fi access for passengers

Fig. 15 :

 15 Fig. 15: In-Flight Entertainment system variant decomposition in Atomic Model Elements

TABLE I :

 I Number of Atomic Model Elements of ArgoUML UML model variants and number dependencies between them

	ActivityDisabled CollabDisabled DeployDisabled Original SequenceDisabled StateDisabled UsecaseDisabled	AMEs 157896 158535 157314 159771 155231 156193 157504	Class 51235 51418 51033 51820 50349 50699 51056	Attr 77707 78046 77450 78667 76417 76805 77547	Ref 28954 29071 28831 29284 28465 28689 28901	Depend 180623 181338 179949 182738 177646 178785 180184

TABLE II :

 II Number of Atomic Model Elements of the blocks identified in the ArgoUML case study

	Block 0 -Core Block 1 -UseCase Block 2 -Sequence Block 3 -Collaboration Block 4 -State Block 5 -Deployment Block 6 -Activity Block 7 Block 8	AMEs 143894 2260 4509 1204 3499 2457 1796 0 0	Class 46724 760 1461 392 1095 787 559 0 0	Attribute 70696 1117 2233 604 1818 1217 916 0 0	Reference 26474 383 815 208 586 453 321 1 1
	. . . Block 40	. . . 4	. . . 2	. . . 2	. . . 0

TABLE III :

 III Number of Atomic Model Elements of IFE system model variants and number dependencies between them

	Original LowCost1 LowCost2	AMEs 16624 16551 16594	Class 5345 5321 5335	Attr 4081 4066 4075	Ref 7198 7164 7184	Depend 24205 24098 24161

TABLE IV :

 IV Number of Atomic Model Elements of the Features identified from the In-Flight Entertainment model variants

	Block0 -Core Block1 -Wi-Fi Block2 -ExteriorVideo	Total AMEs 16521 73 30	Class 5311 24 10	Attribute 4060 15 6	Reference 7150 34 14
	requires the Core feature. With the gathered information
	the CVL models were automatically generated obtaining a
	MSPL for the IFE models. From this MSPL we are able
	to generate a new variant that does not contain Wi-Fi nor
	ExteriorVideo.

Capella and IFE system model example available at http://polarsys.org/capella/download.html

ACKNOWLEDGMENT

Funded by FNR Luxembourg under the AFR grant agreement 7898764. The work of Tewfik Ziadi was also supported by the University of Luxembourg as a visiting researcher.