Yves Caniou
email: yves.caniou@ens-lyon.fr

Ronan Guivarch
email: ronan.guivarch@enseeiht.fr

Gaël Le

Evaluation of the OGF GridRPC Data Management library, and study of its integration into an International Sparse Linear Algebra Expert System

The Data Management API for the GridRPC describes an optional API that extends the GridRPC standard. It provides a minimal subset of functions to handle a large set of data operations, among which movement, replication, migration and stickyness. We already showed that its use leads to 1) reduced time to completion of application, since useless transfers are avoided; 2) improved feasibility of some computations, depending on the availability of services and/or storage space constraints; 3) complete code portability between two GridRPC middleware; and 4) seamless interoperability, in our example between the French GridRPC middleware DIET and the Japanese middleware Ninf, distributed on French and Japanese administrative domains respectively, leading to both of them contributing to the same calculus, their respective servers sharing only data through our implementation of the GridRPC DM API. We have extended the implementation of the library and a further integration has been made available into DIET as a back-end of its data manager Dagda. We thus present how the library is used in the International Sparse Linear Algebra Expert System GridTLSE which manages entire expertises for the user, including data transfers, tasks executions, and graphical charts, to help analysing the overall execution. GridTLSE relies on DIET to distribute computations and thus can benefit from the persistency functionalities to provide scientists with faster results when their expertises require the same input matrices. In addition, with the possibility for two middleware to interact in a seamless way as long as they're using an implementation of the GridRPC Data Management API, new architecture of different domains can easily be integrated to the expert system and thus helps the linear algebra community.

Introduction

The GridRPC API [START_REF] Nakada | A GridRPC model and API for end-user applications[END_REF] was designed to define Remote Procedure Call over the Grid. It has been widely and successfully used in middleware like DIET [START_REF] Caron | DIET: A scalable toolbox to build network enabled servers on the grid[END_REF], NetSolve/GridSolve [START_REF] Yarkhan | GridSolve: The evolution of network enabled solver[END_REF], Ninf [START_REF] Tanaka | Ninf-G: A reference implementation of RPC-based programming middleware for grid computing[END_REF], OmniRPC [START_REF] Sato | OmniRPC: a GridRPC facility for cluster and global computing in OpenMP[END_REF] and SmartGridSolve [START_REF] Brady | Experiments with SmartGridSolve: Achieving higher performance by improving the GridRPC model[END_REF]. The API concentrated on remote service executions: It standardized synchronous and asynchronous calls and computing tasks management. In June 2011, the Open Grid Forum standardized the document "Data Management API within the GridRPC" [START_REF] Caniou | Data management API within the GridRPC[END_REF] which describes an API that extends the GridRPC standard [START_REF] Nakada | A GridRPC model and API for end-user applications[END_REF] (GridRPC DM API). Used in a GridRPC middleware, it provides a minimal set of structure definitions and functions to handle a large set of data operations, among which movement, replication, migration, and persistence.

A first prototype of the API containing the basic functions offering data management through the library has been developed, in addition to a GridRPC layer making possible to write a single GridRPC client able to invoke DIET and Ninf services transparently. With several experiments relying on these early developments, we showed in [START_REF] Caniou | Transparent Collaboration of GridRPC Middleware using the OGF Standardized GridRPC Data Management API[END_REF] that the GridRPC DM API already answers most of the needs presented in [START_REF] Camillo | Improvement of the data management in gridtlse, a sparse linear algebra expert system[END_REF], namely code portability (the exact GridRPC code written with the GridRPC DM API to manage data can be used with any GridRPC middleware), computational feasibility (because of the transparent use of remote data, a GridRPC client is not required to have data on its own system to respect the GridRPC paradigm, hence leading to the use of light client machines), performance (useless transfers can be avoided with the use of persistence). Moreover, we showed that it is even possible for two Grid middleware, managing resources across different administrative domains and using the API, to collaborate in a completely transparent manner.

Although the implementation is still in progress, we show in this paper how a sparse linear algebra expert system, GridTLSE1 , can benefit from the use of the data management provided by the API: we first study the possible performance improvements that can be achieved since expertises may use several times the same matrices; then we study how using stickyness for temporary results can lead to spare already work made in a factorization process to perform several remote solves.

In sections 2 and 3, we first recall the need for such an API for the GridRPC and summarize its properties. Then we present the different middleware, context of the use of the library, in Section 4. The different experiments, experimental protocols and results, are detailed in Section 5 and we conclude in Section 6.

State of the Art

In the GridRPC paradigm, input and output data are arguments of grpc_call() and grpc_ call_async() and are transferred between clients and servers during steps (4) and ( 5) of Figure 1. Thus, each Grid middleware managing its own built-in data, code portability is impossible, and performance can only be managed bypassing the GridRPC model, even for request sequencing [START_REF] Arnold | Request sequencing: Optimizing communication for the Grid[END_REF]. Many other issues arise [START_REF] Caniou | Standardized data management in GridRPC environments[END_REF], but they can only be addressed separately: one can store data on distributed file system like GlusterFS2 or GFarm [START_REF] Tatebe | Gfarm grid file system[END_REF] to deal with automatic replication; Om-niRPC introduced omniStorage [START_REF] Nakajima | Performance evaluation of data management layer by data sharing patterns for GridRPC applications[END_REF]

(3) (4) [START_REF] Caniou | Standardized data management in GridRPC environments[END_REF] Figure 1: GridRPC paradigm such as GFarm and Bittorrent. It aims to provide data sharing patterns (worker to worker, broadcast and all-exchange) to optimize communications between a set of resources, but needs knowledge on the topology and middleware deployment to be useful; DIET also introduced its own data managers (JuxMEM, DTM, and DAGDA [START_REF] Antoniu | GDS: An architecture proposal for a grid data-sharing service[END_REF][START_REF] Del-Fabbro | DTM: a service for managing data persistency and data replication in network-enabled server environments[END_REF][START_REF] Desprez | DAGDA: Data Arrangement for the Grid and Distributed Applications[END_REF]), which focus on both user data management and persistence of data across the resources, with transparent migrations and replications.

Overall, in addition to only fulfilling complementary services, the lack of standard makes their implementation and usage not interoperable nor portable through different middleware, thus the need for the GridRPC DM API standard.

GridRPC Data Management API

The GridRPC Data Management standard relies on the definition of 12 functions and of the GridRPC data, which represents a Grid data, i.e., several copies of the same data stored in different locations, and which may store a data in addition to meta-information. Among these, one can cite the dimension of the data (vector, matrix or more complicated structures), the data type to be able to make the relation with the language type (double, integer, etc). A new and special type, CONTAINER_OF_GRPC_DATA, has been introduced as a set where the user can put or get GridRPC data, and can be used with services producing a number of parameters unknown before execution. There is also a management mode for each data: strictly volatile (the system must erase the data from the storage resource once it has been used or transfered), volatile (the default behavior of the GridRPC standard), sticky (a copy of the data must be maintained on the given location), unique sticky (in addition to being maintained on the given location, that data must stay the unique copy in the system: some systems may indeed implement some fault tolerance mechanisms and would otherwise replicate the data, a behavior that some users do not want), or persistent (the user relies on the GridRPC middleware and its data manager to handle in a seamless and best possible way data management, with possible inner coupling with scheduling decisions). Finally, URI being a description of both the location and the protocol that must be used to access a data registered in the system, one can thus find two lists of URIs, describing where each data can be transfered from or has to be transfered to, and a list of management modes, each of which being applied to the corresponding data whose URI is given in the output URI list.

The API is driven by 12 functions: grpc_data_init() initializes a GridRPC data with information describing the previously mentioned characteristics. GridRPC data referencing input parame-ters must be initialized with identified data before being used in a grpc_call(). grpc_data_getinfo() lets the user access information like transfer status, location, etc. grpc_data _transfer() writes data to output locations (additional ones, with their corresponding management mode, can be given) from input locations (a list of additional input URIs can also be provided). Consequently, some broadcast/multicast mechanisms can then be implemented in the GridRPC data middleware in order to improve performance. grpc_unbind_data() may be used when a client does not need the handle on the GridRPC data anymore, but to explicitly erase a data on storage resources and free the GridRPC data, a call to grpc_free_data() must be performed. In order to communicate a Grid data between grid users, the GridRPC data management API proposes two functions, grpc_data_load() and grpc_data_save(). The last functions of the API are related to inner management, to be able to address in-memory data from an URI, and to get and put GridRPC data in a container of GridRPC data, as mentioned previously.

This work relies on the implementation of the GridRPC standard, and evaluates its integration, and its performance both in terms of possibilities and measurements. The library is freely available to download at https://forge.mis.u-picardie.fr/projects/gridrpcdm/. Note that studies to integrate popular data protocols like iRods 3 and OwnCloud4 are in progress.

Integrating GridRPC Data Management into GridTLSE 4.1 GridTLSE

The expert site GridTLSE5 for linear algebra aims at providing tools and softwares for sparse matrices (matrices with a higher ratio of zero components versus nonzero ones). The site provides user assistance to evaluate and choose the best solver for given problems and helps to set the appropriate values of the input parameters that control the efficiency of the selected solver (Sparse Direct Solvers currently available in GridTLSE are MA48, MA49, MUMPS, SuperLU, UMFPack).

The GridTLSE project uses a high level component semantic description to manipulate sparse linear algebra services (factorization, orderings, linear solves, etc.). Figure 2 presents the different layers of the GridTLSE platform: to provide an easy access to these services, GridTLSE uses the scenario concept which is a graphical description of the task workflow to perform (Geos). This description relies on a semantic description of sparse linear algebra services and tools (Prune). The expertise engine (Weaver) takes into account the user requirements, the internal expertise scenarios, the constraints on the solvers to build a dynamic experience workflow that we call expertise. Finally, each experience of this workflow corresponds to an execution of a computation service, which is made through calls to the DIET middleware (with the help of the GridCOM grid adaptor).

DIET, a GridRPC framework

DIET [START_REF] Caron | DIET: A scalable toolbox to build network enabled servers on the grid[END_REF] (Distributed Interactive Engineering Toolbox) is a lightweight GridRPC middleware, designed for high performance. It is highly scalable, a deployment on thousands of nodes requering only a few minutes. It integrates many features, like customizable distributed scheduling, and can rely on dynamic workflow management, as well as LRMS and Cloud seamless management. It is implemented in CORBA and thus benefits from the many standardized, stable services provided by freely-available and high performance CORBA implementations. It comprises several components: A Client uses the DIET infrastructure to solve problems using a RPC approach. A SED (server daemon) acts as the service provider, exporting functionalities via a standardized computational service interface; a single SED can offer any number of computational services. A SED can also serve as the interface and execution mechanism for either a stand-alone interactive machine or a parallel supercomputer, by directly and independently dealing with its batch scheduling facility. The third component of the DIET architecture, the agent, facilitates the service location and invocation interactions of clients and SEDs. The DIET deployment is structured hierarchically for improved scalability, the hierarchy of agents being composed of a single Master Agent (MA) (the entry point) and several Local Agents (LA), providing higher-level services such as scheduling and data management. Figure 3 shows an example of a multi-hierarchy DIET architecture.

DIET relies on DAGDA [START_REF] Desprez | DAGDA: Data Arrangement for the Grid and Distributed Applications[END_REF] to perform its data management. DAGDA can make implicit and explicit replication, can optimize transfers by selection the most convenient source. For this work, we implemented a "glue" for DAGDA to use the GridRPC data management library.

Experimentations and results

Platform of experimentation

Depicted in Figure 4, the testbed is composed of the machine running the GridTLSE web site (and its matrix collection) in Toulouse, and a cluster in Lyon, with the MA and the client launched on the frontal, and two SEDs running on two of its computing resources.

Validation of the integration of data management in GridTLSE

Methodology

Each expertise uses one of the 5 matrices given in Table 1, with their respective raw and compressed sizes. For each expertise, we consider 3 test cases, each containing two calls to a solver requesting the use of the same matrix. In the following, we give the overall duration of the transfers of each test case, using M and Mc to name the same raw and compressed matrix, T M the duration of the transfer of matrix M, d the duration of the decompression process, B 1 bandwidth between the machines in Lyon and the GridTLSE website, B 2 between the machines in the cluster.

Test case 0 Do not use DAGDA. Transfers are explicitly made: when a service is executed on a SED, it downloads the gzipped matrix from the GridTLSE website. Hence, two transfers occur and

D 0 = (T Mc /B 1 + d) * 2
Test case 1 Use DAGDA. The client downloads the gzipped matrix from the GridTLSE site, uncompresses and registers it into DAGDA by sending the uncompressed matrix to the MA. Then the SED downloads the matrix from the MA. When the second call is performed on the same SED, there is still a copy of the matrix on the SED, so the data is immediately available and

D 1 = (T Mc /B 1 + d) + T M /B 2
Test case 2 Use DAGDA. The expertise is the same than for Test cases 0 and 1, but the second execution is conducted on a different computing resource, thus an additional transfer from the MA (but more generally DAGDA is able to choose the best location from where to download data depending on internal statistics and monitoring). Hence we have

D 2 = (T Mc /B 1 + d) + 2 * T M /B 2

Results

Apart from Aster_feti009a_2.1 whose timings are too small to be really meaningful, results depicted in Figure 5 are really interesting. Similar experiments were conducted in [START_REF] Camillo | Design of an international sparse linear algebra expert system relying on an OGF GridRPC Data Management GridRPC system[END_REF], but results are slightly different here, because of a network bandwidth whose performance has increased and DAGDA which relies on the GridRPC data management library. Indeed, apart from the expertise using FLUX-2M, for which DAGDA shows a real improvement as long as a matrix is used at least twice in an expertise, we can see that the cost to register a matrix in the data management layer is higher than expected: for Aster_perf001a and NICE20MC the expertise (2 GridRPC calls) finishes in the same range of time for TC0, TC1 and TC2, but actually the two calls for TC1 finish nearly at the same time. Of course, TC2 involving an additional local transfer, it conducts to a slightly worse time to complete the expertise. For QIMONDA07, as long as fewer expertises use a matrix less than 3 times, direct download from the GridTLSE website gives a smaller expertise duration.

Remarks

Overall the results presented in the previous section can be considered as the minimum gain that can be achieved for an expertise. Indeed 1) our cases do not consider the fact that several expertises can be performed in parallel, and thus transfers are made in parallel, sharing the network resource and taking more time; 2) if expertises are executed on the same parallel machine, and use the same matrix (or matrices), there is only one transfer using DAGDA, improving by far the time to completion of the study; 3) DAGDA smartly manages storage memory (in a Least Recently Used -LRU -or Least Frequently Used manner -LFU -), so that matrices are still available locally as long as the platform is deployed and there is still memory available; 4) in this study, a matrix is only used twice: in a complex expertise analysis, where a scientist wants to study the effect of some scheduling parameters, gains are cumulative. Hence negative results such as for the expertise using QIMONDA07 would rarely happen and could be easily avoided, by storing both compressed and non-compressed data; 5) finally, the issue for QIMONDA07 being known, we will improve the solution with additional work in order to avoid the transfers from and to the MA. Moreover, as shown in [START_REF] Caniou | Transparent Collaboration of GridRPC Middleware using the OGF Standardized GridRPC Data Management API[END_REF], more GridRPC-driven architectures may be available in a seamless way with all the benefits of the implemented solution. This leads to good expectations on a wider platform (French-Japanese for example) since using DAGDA leads to automatic, yet transparent of use, replicates on components of the DAGDA hierarchy.

Improving GridTLSE expertises with the use of factor files

We consider now a second example that manipulates another kind of data: the factor files resulting from the factorization of a matrix.

Methodology

Numerical context

A typical direct solver for solving sparse linear system Ax = b consists of 3 different steps:

1. a symbolic factorization that determines the nonzeros structures of the factors L and U 2. a numerical factorization that computes the factors L and U such that L.U = A

a solve step

One can see that it is interesting to separate steps 1 and 2 from step 3: for an unique factorization, we can perform multiple solves with different values of the right hand side (RHS) b.

This situation arises in many scientific fields when there are multiple systems to solve with the same matrix either in a simultaneous (parallel) or sequential way. For instance, different systems are solved to evaluated a solution field, function of a wave frequency: for each selected frequency, there is a different RHS. Alternatively, in an evolution problem where, at each time step k, there is a system Ax k = b k to solve.

Therefore if we are able to save the factors after the factorization steps, we can have two separate pieces of software: one that performs the factorization and dumps the factor on disk; one that loads the factor and performs a solve. Not all direct solvers offer the dump/load functionalities that are able to manage big matrices. The forthcoming version 5.0 of MUMPS [START_REF] Amestoy | A fully asynchronous multifrontal solver using distributed dynamic scheduling[END_REF] enables us to write such pieces of software.

Implementation in GridTLSE

We can describe the computation to perform a complete direct solve as a workflow. Figure 6 shows the workflow implemented in GridTLSE. In the previous version (called http version), the factor files are uploaded to the GridTLSE website by the DIET SeD that performs the factorization. The SeD that computes the solution downloads these files at the beginning of its work. The new version (called dagda version) uses DAGDA. The factor files are registered into DAGDA at the end of the factorization step with no upload to the website. If the solve is performed on the same cluster or even better, on the same machine, it can rapidly retrieve the factor files.

Results

We perform different experiments with the selection of matrices detailed in Table 2; the size of the resulting factors is the main parameter to show the gain of time when we avoid the communication of the factor files between the cluster and the GridTLSE website. Table 3 presents the obtained results with or without compression and with or without advanced data management features. For these experiments, we used the test cases TC0, TC1 and TC2 of Section 5.2.1. We can clearly notice the benefit of using the GridRPC Data Management library through DAGDA when we look at the total time 6 .

Concerning the different compressions, when we are using the http version, we can say that gzip compression gives the best results: the smaller time in transfer due the reduced size with lzma does not compensate the larger time spent in the compression and decompression steps.

Figure 2 Figure 3 :

 23 Figure 2: GridTLSE platform

Figure 4 :

 4 Figure 4: A geographically distributed platform of experimentation

Figure 5 :

 5 Figure 5: Results for each expertise on all the test cases

Figure 6 :

 6 Figure 6: A direct solve as a workflow in GridTLSE

  as a Data Management layer relying on several Data Managers

		Registry
	Handle		Register
			(1)
		Lookup
	Client	Call	Service
		Results

Table 1 :

 1 Matrices characteristics and time to decompress (sizes in KBytes, and times in seconds)

		Aster_ f eti009a_2.1 Aster_per f 001a	NICE20MC	QIMONDA07	FLUX -2M
		Size	Time	Size	Time	Size	Time	Size	Time	Size	Time
	raw 1 563	-	534 224	-	895 087	-	2 195 699	-	16 007 994	-
	gziped	353	0	131 813	13	205 756	20	214 549	34	3 000 860	325

Table 2 :

 2 Matrices characteristics and time to decompress (sizes in KBytes, and times in seconds)

http://gridtlse.org

http://www.gluster.org/

https://www.irods.org/

https://owncloud.org/

http://gridtlse.org

* Speaker. † This work is partially founded by the Technological Development Department (D2T) at INRIA, the ANR-JST FP3C (Framework and Programming for Post Petascale Computing) and the ANR-09-COSI-001, COOP (Multi Level Cooperative Resource Management)

Table 3: Experiments results for three matrices, three test cases and two compression algorithms

Conclusion and future work

We have presented the first evaluation of the benefits obtained by the extension of the GridRPC API OGF standard concerning data management, i.e., the GridRPC Data Management GFD-R-P.186 OGF standard, in the context of real computations required for a sparse linear algebra expert system, GridTLSE.

We have conducted several experiments. The experiments for validation showed us that the proposed solution is interesting if the same matrix is used more than a couple of times in an expertise. Of course, in a production environment, some gains would rapidly be obtained since different expertises are generated by GridTLSE, and they may use the same input matrices. But some additional work on the architecture of the solution, i.e., the integration of GridTLSE and DIET, together with the use of the data management, can improve the solution by overlapping given operations and thus reducing the time spent to register a new data in the system.

We also studied the possibility of using the factor files produced by direct solver MUMPS, in order to split the factorization step and the solve step. The experiments clearly demonstrated that the new pieces of software developed for this study perform much better than the basic approach. They should be integrated in the production expert site soon.

Future work will go towards the development of the full API (some functions are still missing), also taking into account other protocols such as GridFTP, iRods and OwnCloud if possible. We will continue our work in the Open Grid Forum GridRPC working group: recommendations and possible extensions to the API are possible, but it will depend on the final users'/developers' remarks. We are eager to get different use-cases and users' feedback.

On the numerical side, future work will focus on the two following directions: 1) When a full direct solve expertise is launched, there may be no need to perform the factorization step if it has already been processed before, for the need of another expertise for example. Mechanisms have thus to be deployed inside the expertise engine to detect this situation. For instance, we could verify if the factor files corresponding to the matrix are already registered in the data manager (to avoid the factorization step). This could actually be done at the middleware level or in Weaver, the expertise engine of GridTLSE in connection with the DAGDA data manager. 2) Extend our work to the parallel version of the direct solvers. That will induce a more complicated data management than with the sequential version, in addition to automatic job management with regard to LRMS systems.


Hugo Loi

Thomas Hurtut

Romain Vergne

Joëlle Thollot

A Programmable Model for Designing Stationary 2D Arrangements

Keywords: Programmable approach, element texture, spatial arrangement, texture design, texture synthesis Approche programmable, texture à base d'éléments, arrangement spatial, conception de textures, synthèse de textures

This paper introduces a programmable method for designing stationary 2D arrangements for element textures, namely textures made of small geometric elements. These textures are ubiquitous in numerous applications of computer-aided illustration. Previous methods, whether they be example-based or layout-based, lack control and can produce a limited range of possible arrangements. Our approach targets technical artists who will design an arrangement by writing a script. These scripts are using three types of operators: partitioning operators for dening the broad-scale organization of the arrangement, mapping operators for controlling the local organization of elements, and merging operators for mixing dierent arrangements. These operators are designed so as to guarantee a stationary result meaning that the produced arrangements will always be repetitive. We show that this simple set of operators is sucient to reach a much broader variety of arrangements than previous methods. Editing the script leads to predictable changes in the synthesized arrangement, which allows an easy iterative design of complex structures. Finally, our operator set is extensible and can be adapted to application-dependent needs.

This paper introduces a programmable method for designing repetitive arrangements of geometric elements. Such repetitive arrangements are good candidates for element texture design (Figure 1). Throughout this paper, we distinguish arrangements from textures in that textures can be stylized, using for instance colors and varying stroke widths. Element textures are a fundamental aspect of illustration. They add complexity to a drawing and support many artistic eects. They also depict important information such as materials in architectural plans, fabric in clothes, terrain type in topographic maps, biological materials in medical illustrations, etc.

Producing element textures is therefore mandatory for many illustration systems and application elds, such as 2D animation, cartography, and other computer-assisted design tasks like pattern creation for textile or wallpaper industry. These applications often need to synthesize a large amount of each element texture either because the target image is very large (geographic map, wallpaper) or because the same texture is used in many images (comics, 2D animation). In

RR n°8713

this context, manual authoring is tedious which motivates the need for a completely automated production pipeline. Several problems need to be solved to achieve this goal: the synthesis of various geometric elements, their arrangement on the plane, the choice of style attributes for each element and the rendering of the nal element texture. Each of these topics is a research problem in itself. Existing works address extensively the tasks of creating elements [START_REF] Baxter | Latent doodle space[END_REF][START_REF] Hurtut | Synthesizing structured doodle hybrids[END_REF][START_REF] Neill | Learning a manifold of fonts[END_REF] as well as stylizing and rendering geometrical data [START_REF] Hertzmann | Fast paint texture[END_REF][START_REF] Eisemann | Stylized vector art from 3d models with region support[END_REF][START_REF] Grabli | Programmable rendering of line drawing from 3d scenes[END_REF][START_REF] Diverdi | A brush stroke synthesis toolbox[END_REF]. In this article we address the problem of spatially arranging existing elements into a texture so as to ll a given region.

Targeted Properties. A computer-aided design tool for the production of texture arrangements should meet several requirements which we formalize in the following targeted properties:

Predictability. Iterations between clients and technical artists involve numerous edits of the produced arrangements, which is feasible only through a controllable synthesis engine with predictable results.

Expressiveness. The design tool must be expressive enough to allow the creation of classic layouts used by technical artists (see Figure 1 for an overview). When looking at manually drawn patterns, we observe that artists use regular and non-regular elements distributions and control elements adjacency such as contact or overlap. Complex arrangements are obtained by composing multiple distributions, the composition rule being generally a nonoverlap superposition of these distributions. Some arrangements are also structured into clusters of elements and can be thought as being based on multi-scale arrangements.

Stationarity. The main property of a texture is to be repetitive, enforcing its perception as a whole [START_REF] Treisman | A feature-integration theory of attention[END_REF]. This characteristic can be formalized as the result of a stationary process.

It means that the spatial statistics of the arrangement should not depend on the spatial location. Since this property is required for every texture, the design tool has to guarantee that all produced arrangements are stationary.

Extensibility. Some specic projects might need arrangements that cannot be initially produced by the design tool, despite its native expressiveness. It must then provide a way to add new components for synthesizing these arrangements, while still guaranteeing stationary results.

Our Approach. We propose a programming-based method where each arrangement is represented by a user-written script. Programmable approaches have been proven useful for many designing tasks in computer graphics, including shading [START_REF] Robert | Shade trees. Computer Graphics[END_REF], modeling [START_REF] Müller | Procedural modeling of buildings[END_REF], stylized rendering of 3D scenes [START_REF] Grabli | Programmable rendering of line drawing from 3d scenes[END_REF][START_REF] Eisemann | Stylized vector art from 3d models with region support[END_REF] and motion eects [START_REF] Schmid | Programmable motion eects[END_REF]. As in these works, we target artists having programming abilities such as technical directors. Our contribution is therefore to provide the rst programmable design tool dedicated to arrangements creation while simultaneously satisfying the four properties dened above.

Technical Contribution. To build our programmable method, we dene a set of predictable operators that allow to produce a wide variety of arrangements while ensuring their stationarity.

For that we take inspiration from programmable raster textures design 1 . In these methods, the design process (1) starts with an initialization such as Perlin's noise, (2) involves a number of lters such as color mapping, and (3) uses combining operations such as blending to mix multiple textures. Instead of a pixel grid, we store our arrangements in a high-level structure that stores adjacency and geometric information. Then, similarly to raster texture, we introduce three types of operations for the design process: (1) the structure is initialized with stationary partitions 1 www.allegorithmic.com Inria such as a grid; (2) instead of lters, local geometric transformations are next applied to rene the partitions; (3) merging operators nally allow to combine multiple arrangements into complex ones. These three categories of operators are sucient to achieve expressiveness, while creating a modeling scheme where stationarity is guaranteed at all stages. The synthesis is controlled step-by-step, which allows to edit the script with predictable eects. Finally, our method can easily be extended by adding new operators as long as they satisfy locality conditions in order to preserve stationarity.

Related Work

We focus our study on object-based texture representations, such as vector graphics representations, rather than their raster counterpart. Indeed, even if some ecient methods have been devised in the context of raster textures design [START_REF] Ebert | Texturing and Modeling: A Procedural Approach[END_REF], pixel-based textures loose geometric and connectivity information of the elements at stake, preventing further stylization or editing. In the context of object-based texture representation, existing computer-aided solutions for element placement fall into two main categories: example-based approaches which have seen a recent increased interest, and layout-based solutions usually proposed in commercial software. After reviewing these two classes of approaches that allow to produce stationary arrangements, we will review other procedural modeling approaches that are more expressive or predictable but loose stationarity.

Example-based Element Texture Synthesis

Most methods in the literature of element textures synthesis are dedicated to example-based approaches. They propose an artist-friendly interface where a small user-drawn exemplar is analyzed and synthesized over a larger domain. These approaches produce stationary arrangements and are easy to use for casual users. However they have a limited use in industrial contexts due to their lack of predictability and expressiveness.

Predictability. Describing the texture through a single examplar brings an ambiguity between desired invariants (such as all elements must touch each other at their ends) and variable properties (such as elements can have random orientations). Furthermore, small modications in the examplar may produce large unpredictable changes in the output. Besides, the exemplar needs to be stationary. So any modication has to be spread all over the exemplar meaning that the user has to rearrange the entire exemplar at each design iteration.

Expressiveness. None of the existing example-based methods succeeds to cover all classic layouts presented in Figure 1. We tested three recent methods [START_REF] Ijiri | An example-based procedural system for element arrangement[END_REF][START_REF] Hurtut | Appearance-guided synthesis of element arrangements by example[END_REF][START_REF] Ma | Discrete element textures[END_REF] and we observed limitations controlling contact or overlap (Figure 2(a)), regularities such as alignments (Figures 2(b) and 2(c)) and multi-level arrangements (Figure 2(d)). These limitations come from two fundamental issues. First, approximate representations limit the types of elements and adjacencies that can be handled. For example, a centroidal element model [START_REF] Ijiri | An example-based procedural system for element arrangement[END_REF] is not adapted to strongly anisotropic elements. Similarly bounding boxes [START_REF] Hurtut | Appearance-guided synthesis of element arrangements by example[END_REF] or sampling [START_REF] Ma | Discrete element textures[END_REF] reduce control on adjacency (Figure 2(a)). The proxy geometries introduced in [START_REF] Landes | A shape-aware model for discrete texture synthesis[END_REF] help to control more precisely elements adjacency. However, it does not solve overlapping cases due to an inaccurate similarity measure of overlapping relations. Second, the lack of high-level information makes it hard to detect geometrical constraints at variable scales such as alignments and clusters. It has been done for specic applications, like in [START_REF] Yeh | Synthesis of tiled patterns using factor graphs[END_REF] for arrangements of tiles, but we are looking for a more general approach.

RR n°8713 Synthesized results from previous methods [START_REF] Ijiri | An example-based procedural system for element arrangement[END_REF][START_REF] Hurtut | Appearance-guided synthesis of element arrangements by example[END_REF][START_REF] Ma | Discrete element textures[END_REF][START_REF] Landes | A shape-aware model for discrete texture synthesis[END_REF] are shown on the four right columns.

(a) A bimodal hatching, explicitly cited as one of the last limitations in [START_REF] Hurtut | Appearance-guided synthesis of element arrangements by example[END_REF]. While each interior hatch drawn in the exemplar crosses exactly three other hatches, no method preserves this property. In the case of the Expectation-Maximization algorithm of [START_REF] Ma | Discrete element textures[END_REF], possibly unwanted overlaps created during the patch-based initialization tend to be corrected during the optimization step thanks to the deformations handled. However, desired overlaps are still not ensured. (b,c) Regular structures with respect to three and one axis of alignment. The growing Delaunay-based approach of [START_REF] Ijiri | An example-based procedural system for element arrangement[END_REF] achieves to reproduce these regularities in some ways. Yet the heuristics used to preserve the local graph structure also tend to create some gaps. Dense packing is challenging for Monte-Carlo statistical approaches such as [START_REF] Hurtut | Appearance-guided synthesis of element arrangements by example[END_REF][START_REF] Landes | A shape-aware model for discrete texture synthesis[END_REF]. Indeed, although running 10 8 iterations, the (b) example outputs for these two methods still have some density variations. (d) A simple case of element clusters that no method succeeds to reproduce faithfully.

Predened Layouts

Vector graphics software such as Adobe Illustrator or Inkscape propose predened layouts to arrange user-drawn elements. The most common example of such layouts is the grid. With the same approach, recent online tools 2 propose methods for tiling small user-drawn arrangements.

More complex stand-alone algorithms can synthesize uniform distributions eciently [START_REF] Hiller | Beyond Stippling Methods for Distributing Objects on the Plane[END_REF][START_REF] Lagae | A procedural object distribution function[END_REF]. All these methods produce stationary results and are straightforward to use for obtaining a single particular layout. Their eect is predictable but their expressiveness is limited to a single kind of arrangement and they usually are not easily extendable. Typically Figure 2(d) would be hard to do with such approaches because it mixes regular and random distributions.

2 www.colourlovers.com/seamless Inria

Procedural Modeling

In this section, we present several inspiring procedural methods, coming from other elds than texture synthesis. We share some properties with these approaches, but none of them is well suited to element texture production because they have not been designed to ensure stationary outputs.

Historically, L-Systems [START_REF] Lindenmayer | Mathematical models for cellular interaction in development: Parts i and ii[END_REF] were used early in computer graphics to model plants [START_REF] Prusinkiewicz | The Algorithmic Beauty of Plants[END_REF]. Being originally dedicated to the generation of one-dimensional patterns, they cannot enforce a stationarity property in a two-dimensional domain. This is also the case for their extensions: parametric, timed and open L-Systems.

Shape grammars are another renowned procedural modeling approach [START_REF] Stiny | Shape grammars and the generative specication of painting and sculpture[END_REF][START_REF] Wonka | Instant architecture[END_REF][START_REF] Müller | Procedural modeling of buildings[END_REF]. Like more general context-dependent growth systems [START_REF] Michael | Computer-generated oral ornament[END_REF][START_REF] M¥ch | The Deco framework for interactive procedural modeling[END_REF], they use an axiom that is either a single element or the domain boundary. User-programmed growth rules must handle the propagation (or the subdivision) into the entire domain. Consequently, users would have to make a careful, non-intuitive use of each rule to obtain stationary arrangements.

Other arrangement transformations have been studied such as parquet deformations [START_REF] Kaplan | Curve evolution schemes for parquet deformations[END_REF] and Escher construction operators [START_REF] Henderson | Functional geometry[END_REF]. These models are very specic to their respective application elds, which limits their expressiveness. However they are similar to our approach in the sense that they locally apply geometric transformations to an initial partition. Our approach targets general stationary arrangements.

3 Overview Design principles. In a programmable approach, the task of the user is to build the algorithm that will produce his envisioned result. For that we provide the user with three types of operators, each of them responsible of a specic task: partitioning operators initialize an arrangement, mapping operators rene it and merging operators create combinations of arrangements. All of these operators have to guarantee the stationarity of the resulting arrangement. The texton theory [START_REF] Julesz | Textons, the elements of texture perception, and their interactions[END_REF] states that the appearance of an arrangement emerges from the broad-scale organization of micro-patterns called local texture elements. Therefore stationarity occurs at broad-scale whereas local texture elements do not need to be constrained. Following this theory each type of operator will guarantee stationarity at its own scale:

Partitioning operators. The design of an arrangement starts with a stationary partition.

It ensures stationarity at broad-scale while letting the user choose between a regular or non-regular global arrangement structure.

Mappers. The initial partition is locally rened using mappers. Mappers are user-programmed functors and control both local geometry and adjacency, by for instance placing an imported element and transforming it depending on its neighbors. A mapper is always applied everywhere on the arrangement via a mapping operator. Whereas no specic property has to be satised by elements, this is the locality and the homogeneous application of the mapper all over the arrangement that will ensure stationarity. Note that mappers can also call a partitioning operator in order to create a subscale arrangement. This can be useful to create texture elements made of a stationary arrangements (see for instance the subscale stripe arrangements in Figure 1(g)).

Merging operators. Finally, complex arrangements are sometimes more easily designed when seen as the merge of simple arrangements such as the overlap of two textures. Merg- Functional programming. Our approach is entirely functional. We dene an arrangement as a function that takes as input a region and returns a collection of curves. All our operators, regardless of their category (partitioning, mapping, merging), output an arrangement. On the input side, partitioning operators take in a region whereas merging operators take in two arrangements to be combined. Mapping operators take in both a mapper and an arrangement to be mapped. We use Python as the programming user interface, its syntax being simple and intuitive to most programmers and well designed for functional programming.

Data representation. The collection of curves returned by an arrangement function is embedded into a planar map: A structure containing vertices (intersection points), edges (pieces of curves linking vertices) and faces (2D domains enclosed by edges) [START_REF] Baudelaire | Planar maps: An interaction paradigm for graphic design[END_REF]. Spatial adjacency between these three types of component can be precisely handled by the user with mappers, allowing contact or overlap control.

Overview example. Figure 3 gives an example of the synthesis of a two-scale arrangement.

Three mappers are rst designed in this script. The rst two ones map an SVG element on a face (L.9) and an edge (L. [START_REF] Hurtut | Appearance-guided synthesis of element arrangements by example[END_REF]). The last one creates a regular partition (L.29) and calls the second mapper (L.32) to map a curve on each of its edges. Once these mappers are dened, a uniform partition is created (L.37). A blob shape is mapped on each of its faces using the rst mapper Denition. The planar map induced from a collection of curves C is dened as a set of cells partitioning the plane (Figure 4). Cells are of three types: edges, vertices and faces. Edges are the set of maximal pairwise disjoint subcurves of C. Vertices are the set of limit end points of edges. Faces are the set of maximal parts of R 2 ´C. An incidence graph completes the representation allowing access to all types of adjacencies in the planar map.

Cell labels. On top of the planar map, we add a set of labels to each cell, accessible to mapping operators. They will typically be used to select a subset of cells when needed. We let the user dene the (nite) set of possible labels by either giving labels to partitions' cells or adding labels to imported SVG curves.

Face labels reconstruction. When modifying or combining planar maps, labelling has to be conserved. We adopt the same solution as [START_REF] Asente | Dynamic planar map illustration[END_REF]. Since planar maps are induced by curves, labels should be stored only on curves. Faces labels are thus stored on their adjacent edges and reconstructed each time a new planar map is induced.

RR n°8713

Implementation. Practically, in our implementation, planar maps are based on the CGAL arrangement structure [START_REF] Fogel | CGAL arrangements and their applications[END_REF] and use exact arithmetic and geometry with rational coordinates to avoid any topological artifacts due to numerical imprecisions. Edges are oriented accordingly to their originating curves. For example, e 1 's source vertex is v 2 and its target vertex is v 3 . Right: The incidence graph of the planar map denotes the relationships between vertices, edges and faces. We did not include arcs between vertices and faces for clarity, they can be deduced by transitivity.

Three oriented curves Induced planar map Incidence graph

Partitioning Operators

The rst step in the design of an arrangement is to choose a partition to determine its global structure. Such partitions must be stationary and should hold a regular or non-regular global structure. These partitions will be extensively rened by dening local transformations using mappers, as presented in Section 6. If required, more operators could be easily added to adapt to specic needs. Our goal in this section is therefore to provide operators that ensure a stationary partition, simple enough to begin the design, but subsequently exible enough to allow all possible renements.

Regular Vs Non-regular Partitions

We propose four partitioning operators that allow to design regular and non-regular partitions of the input region. These operators, in addition to a a few others that let specify partition labels and properties, are recalled in the Table 1 of the appendix.

Regular partitions. The StripesPartition operator partitions the domain with a distribution of parallel lines. This operator is dened with the stripe angle and the width between two successive lines. Optionally, the user may dene a cycle of widths that will be repeated periodically until all lines are placed. For instance in Figure 5(a) the top image shows a cycle with two alternating width values (20 units and 10 units), while the bottom image uses only one width value (15 units). These parameters are set by the "StripesProperties" function that takes a variable number of arguments. Labels might also be associated to faces and/or edges using the same cycle process. In that case, all partition's faces/edges are labelled by successively picking the corresponding value in the label list (Figure 5(a)). GridPartition partitions the domain with two distributions of parallel lines and is thus obtained by specifying two stripes partitions.

Inria

Note that when faces are labelled for both stripes, each single face receives a total of two labels.

For instance in the top image of Figure 5(b), the green color denotes the presence of both labels yellow and blue.

Non-regular partitions. UniformPartition and RandomPartition operators are computed using Voronoi diagrams, respectively based on Poisson-Disk and Poisson distributions. In both cases, the user needs to specify a density value that denes the number of samples per unit area via the "IrregularProperties" function. Labels might also be attached to faces and edges of these partitions. In that case, the user denes a list of labels and apparition probabilities used to randomly assign each face and/or edge (Figure 5(c,d)). Labels may also randomly be assigned according to user-dened probabilities. Faces and edges may contain multiple (cycling) labels to precisely control the nal arrangement.

Border management

When partitioning a face, the user may want various behaviors at its boundary. We provide four border management options that cover all the cases we encountered (Figure 6).

Mappers

Mappers are a central feature of our approach. As previously mentioned, a texture is a large-scale stationary arrangement of small-scale elements. Contrary to partitioning operators that create the broad-scale structure of the arrangement, mappers are targeting small-scale elements. In practice, a mapper is a function that takes as input a single cell of a planar map. It applies (almost) arbitrary code written by the user so as to create, combine, transform and place curves on a particular location according to the cell's information (position, incident vertices, edges, faces, etc.). The mapper nally outputs a collection of curves.

In order to preserve stationarity, mappers must be executed homogeneously on all the cells of a planar map. Since the initial planar map comes from a stationary partition, this property is preserved, formalizing the large-scale repetitive aspect of textures. This homogeneous execution is handled by mapping operators. We provide one mapping operator per cell's type: "MapToVertices", "MapToEdges" and "MapToFaces" (Table 2 A grid is rst initialized using the "GridPartition" operator (left). Each edge is labelled using user-dened value cycles (shown with colors in this example). Based on the "HasLabel" operator, a mapper that keeps edges in staggered rows is applied on each edge of the grid (middle). The nal puzzle pattern is obtained by a mapper using the "MatchPoints" operator that places a simple curved line on each edge (Right). Middle: The planar map is initialized with a uniform partition (left). Four lines are matched to the centroid of each face of the partition to build a new set of construction lines (middle). Overlapping circles are mapped on the resulting vertices to create rosette owers (right). Bottom: Starting from a random initial partition (left), the induced faces are slightly scaled down (middle). Some curves, picked from a limited example set are nally mapped on each induced edge using the "MatchPoints" operator (right).

used as input to another mapping operator in order to generate more complex patterns.

Mapper denition

Formally, a mapper is a user-programmed functor m that maps a single cell c of a planar map P to a new collection of curves C. The key idea of our model is that the programmed functor m will automatically be executed on each cell c P P by a mapping operator. To ensure that the mapping of m on P preserves stationarity, the following conditions must be respected:

m is local and depends only on cells of P inside a given bounded neighborhood. Only a bounded number of incidence queries should then be called inside a given functor.

m does not depend on a particular execution order. It means that global variables are read-only and should not be overwritten.

m does not depend on global coordinates to avoid specic mappings to be applied at RR n°8713 particular locations in the plane. Consequently, only relative cell's coordinates are available from the user point of view.

These conditions ensure that a functor will have the same behavior everywhere in the input planar map.

Programming Mappers

We provide a set of low-level built-in operators specically designed to program mappers, given in Table 3 Incidence operators are dedicated to access all the information stored is the incidence graph of the planar map.

Adjacency operators are used to place elements while controlling their adjacency either to one or two vertices, or in a face.

Geometry operators retrieve information of the input cell such as its location, contour, centroid, etc.

Labels operators are dedicated to the management of labels.

Random values operators allow to easily vary the properties of the mapping inside each cell.

We also provide a set of useful utility functions that yield simple geometric ane transformations, bounding box information as well as the loading of an SVG element. These functions are accessible from everywhere in user-scripts (see Table 5 of the appendix).

Using mappers

A typical use of mapping operators is to modify an original partition, for instance by removing of modifying some cells, then placing some imported elements possibly controlling their adjacency.

One can stop here or continue to map elements until reaching the desired arrangement. We show three examples in Figure 7 to illustrate the variety of eects a mapper allows to create on the partitions. The top example leverages labels and the precise matching of curve endpoints to create a puzzle-like brick wall arrangement. The middle example uses single point matching and location operators to create a uniform distribution of rosette shapes. In the third example, the faces of a uniform partition are rst rescaled before replacing each of their edge by a new smooth curve. More complex arrangements can be created by calling partitions operators into mappers as shown in the overview (Figure 3).

Merging Operators

Merging operators take two arrangements as inputs, and return one arrangement (Figure 8).

They provide a simple way to mix simple arrangements to obtain complex patterns. We propose three dierent merging operators (Table 4):

Union computes a new arrangement that results from the collection of all the edges produced by the two inputs arrangements. It is used to group multiple distributions (Figure 8(d)). proposed as for partitions (see Figure 6). (g,h) The Outside operator also behaves like a mask, keeping only the edges from a rst arrangement that fall outside the faces of a second one. Same border management options are available.

Inria

Inside and Outside are masking operators. They keep only the edges produced by a rst arrangement that are falling inside and outside the bounded faces, respectively, of a second arrangement. A border management option is mandatory for these operators. It allows to precisely dene if cells have to be kept-in, kept-out or cropped along the rst arrangement boundaries (Figure 8(e-h)).

Results

Along the paper we have shown that our method guarantees stationary outputs by construction.

We also have highlighted how it is extensible at all stages. Here we present practical modeling sessions that demonstrate its predictability and expressiveness. Designing an arrangement is an iterative process. The user progressively nds the set of successive rules that leads to the result he has in mind. As shown along the paper, the basic strategy is to design simple arrangements to be combined. A general structure is chosen for each one, and further rened. All the scripts and execution times used to produce the images of this paper are included in the supplemental RR n°8713 Script Editing. In terms of interaction, our modeling approach is very similar to nodebased material shaders commonly used in the 3D pipeline: (1) partitioning operators correspond to initialization nodes, (2) mapping operators correspond to ltering nodes, and (3) merging operators correspond to the 2 Ñ 1 combination nodes. This interaction scheme has been used

during the last 30 years since the seminal work on Shade Trees [START_REF] Robert | Shade trees. Computer Graphics[END_REF]. It is commonly acknowledged to be ecient. In particular, it favors iterative design processes as well as the exploration of various combinations at the artist's whim.

Figure 9 shows the kind of variations that are produced during such an exploratory usage of our tool. Each image shows the result obtained by a slight modication of the script presented in the overview (Figure 3). These variations are predictable because the script is composed of small understandable chunks of code (partitions and mappers) linked together by simple merging operators. A regular user of our tool should be able to foresee how these edits in the script will inuence the execution of the other chunks left unchanged.

In Figures 11 and12 we show iterative design sessions where the user envisions a particular arrangement and edits the result towards this objective. Our method allows to proceed step by step and to display the arrangements produced at each step. This helps making sure that the edits converge towards the envisioned result. These two gures display the temporary steps of the design sessions as well as the results nally obtained. They showcase how this script-editing scheme is helpful for quickly designing complex arrangements. 55 human-readable lines and they use only the operators given in appendix. Our method is therefore able to achieve the target level of expressiveness. It is the rst approach that completes this objective since it overcomes the limitations of the existing techniques as shown in Figure 10.

Expressiveness. The examples shown in

Let's note that our feasible set of arrangements does not strictly include those of the previous methods. In particular, our proposed operators may not be able to reproduce all the subtle Inria The evaluation protocol developed in [START_REF] Almeraj | Towards eective evaluation of geo-Inria metric texture synthesis algorithms[END_REF] showed that even expert designers do not usually agree on what should be the output arrangement based on one examplar.

We show here that we can reproduce the four dierent expert manual arrangements gathered in the second gure from AlMeraj's study, which all subtly vary from the given input examplar.

variations synthesized by example-based methods. However our solution is able to span a variety of arrangements that was not feasible before, which was the goal of this article.

These results demonstrate that expressiveness is achievable with a restrained set of operators.

It also validates our insight of separating the design tasks between a very small set of partitioning operators and an unlimited set of possible renements. It is particularly visible in Figure 11 where a variety of arrangements are designed based on simplistic regular partitions. These results validate as well our choice of manipulating all kinds of primitives (vertices, edges and faces), whereas alternative strategies based only on dot anchors or edge distributions would limit the possible spectrum of edits.

Figure 13 shows a complete vector drawing, textured with seven scripts using our approach.

These seven textures cover a variety of eects. Rough natural materials are depicted using various hatching (wood) and stippling (teapot) techniques. The man-made parquetry arrangement is based on specic adjacency relations. Finally, the tapestry uses the two-scale texture from generate a very ne StripesPartition, and then to ll the faces obtained with constant densities that would make a piecewise-constant approximation of the sine function. This limitation is due to our choice of generating the arrangement's properties from discrete predicates only, for example the value of a label. As discussed in future works, continuous control maps would be helpful in such cases.

Implicit control. In our approach the user explicitly controls all spatial relations in the arrangement. Unlike most by-example approaches where targeted properties are given as input of the synthesis algorithm, our input is the construction script. As a consequence our approach allows to precisely control element adjacencies but does not help producing arrangements that exhibit implicit behaviors such as the ones resulting of physical simulation or other global optimization processes. A typical example is a zebra texture that is hard to design with our approach.

Operators. We designed our operator set in order to allow a wide variety of arrangements. More operators could be added for specic needs. As an example, we currently control adjacency based on one or two contact points. It may be interesting to increase the number of constraint points to create more constrained arrangements. This requires non-rigid transformations and interpolation, which is left for future work.

Inria

Planar maps. Since our internal representation is a planar map, we inherit all the limitations of this model. In particular, there is no simple way to determine which faces of the planar map are intended to be the interior of the elements. For instance, the drawing of a ring is constituted of two concentric circles. This induces two faces considered at the same level by our operators, whereas the user might want to process them separately. Labels can be used to resolve some ambiguities but not all of them. Other representations could be investigated to solve this problem such as Vector Graphics Complexes [START_REF] Dalstein | Vector Graphics Complexes[END_REF].

RR n°8713

Figure 13: Texture-based illustration. (top) A simple SVG drawing. (bottom) The drawing is textured using seven scripts. The created paths can be grouped and imported in any vector drawing software. They can then be processed as any other SVG element. For example here, a single action was needed for lling all the parquetry slats with a horizontal linear gradient.

User interface

We have shown that our programmable approach yields predictable and controllable results.

However the interaction scheme oered by a programming language is not suitable for nonprogrammers. A way to broaden the audience of our method is to oer more intuitive user interfaces. This should be possible thanks to the combination scheme of our operators which is natively nodal. Formally, operations are organized as a Directed Acyclic Graph where nodes are operations and pointers are planar maps (we call them nodes and pointers to avoid confusion with planar map cell types). It means that a straightforward node-based graphical interface such as in [START_REF] Abram | Building block shaders[END_REF] would be sucient to wrap our operator combination scheme. However the (almost) arbitrary code in our mappers is much more dicult to represent graphically. A simple solution could be to abstract these mappers as operation nodes. Users with programming skills would then create such nodes using a regular text editor and share these nodes to the non-programming community.

An interesting issue to pursue could be to propose inverse procedural modeling such as in [START_REF] Galerne | Gabor noise by example[END_REF]. A full inverse programmable approach is probably too dicult since it would boil down to go back to the limitations of by-example approaches. Yet one could target just a few operators' parameters such as density and cycles, or more global characteristics such as the type of partition.

These could be learned from simple examples or user given sketches.

Inria

Towards a complete programmable illustration pipeline

Our programmable approach addresses the problem of placing elements in a texture. This problem is part of a complete texture synthesis pipeline. We discuss here how the remaining parts could be combined with our approach.

Elements synthesis. Our current system in able to import existing elements. A straightforward extension could be to add an import operator that pick random elements produced by existing algorithms of element synthesis such as [START_REF] Baxter | Latent doodle space[END_REF]. However if one may want to stay in a programmable pipeline, operators may be devised to increase the control on each element shape.

Procedural modelling already oers numerous methods for context-dependent element synthesis that we could use to extend our model [START_REF] M¥ch | The Deco framework for interactive procedural modeling[END_REF].

Control maps. It is sometimes suitable to add control maps to guide the global behavior of the arrangement by locally varying its density or orientation. We plan to extend our approach in that direction by devising new operators that would give mappers the ability to query external data.

These data could locally deform partitions or impact elements spatial properties. Starting from our stationary distributions and depending on the control map, the resulting element textures would exhibit a repetitive aspect even if not strictly stationary.

Stylization. The stylization step can be done manually by loading SVG exported by our system in commercial vector graphics software. However, it would make sense to stay in a programmable approach for this step because style attributes could be linked with placement data via specic operators. A similar approach has been applied to the stylisation of line-drawn 3D models [START_REF] Grabli | Programmable rendering of line drawing from 3d scenes[END_REF][START_REF] Eisemann | Stylized vector art from 3d models with region support[END_REF]. This method would be a good candidate to extend our approach to stylization.

Rendering. Currently, we produce simple SVG outputs containing only polylines. As our internal representation is a planar map, the resulting SVG le does not contains stacked polygons.

In order to extend the vector formats handled by our approach, new operators should be dened.

For example, stacked polygons would need ordering operators on top of the planar map. We could also produce other types of vector formats such as diusion curves [START_REF] Orzan | Diusion curves: a vector representation for smooth-shaded images[END_REF] by adding color points mappers.

We give here the list of our operators in respective tables: partition operators (Table 1), mapping operators (Table 2), mappers' built-in operators (Table 3), merging operators (Table 4), and other useful functions available anywhere in user scripts (Table 5).

Figure 1 :

 1 Figure 1: Element textures commonly used. These textures can be found in professional art (d,g,h), casual art (a,e,f ), technical productions such as Computer-Assisted Design illustration tools (c), and textile industry (b). For each example, we show a hand-drawn image (left), and our synthesized reproduction of its geometric arrangement (right). (a,b,c) Classic regular distributions with contact, overlap and no adjacency between elements respectively. (d) Overlap of two textures creating cross hatching. (e) Non overlapping combination of two textures. (f,g,h) Complex element textures with clusters of elements. Image credit: (d,g,h) [15]; (a,e) Profusion Art [profusionart.blogspot.com]; (f ) Hayes' Art Classes [hayesartclasses.blogspot.com]; (c) CompugraphX [www.compugraphx.com]; (b) 123Stitch [www.123stitch.com].

[Figure 2 :

 2 Figure 2: Example-based methods' limitations. Input examplars are shown on the left.

Figure 3 :

 3 Figure 3: An example of a script and its output. Left: A script based on two imported SVG elements (a blob-like shape and a small stroke) and three user-dened local mappers to control local features. Right: The output is a two-scale arrangement. We show here two intermediary results and the nal output.

  (L.40). The third mapper then maps a regular arrangement on the resulting faces which are now blobs (L.43). Induced edges and faces are exported respectively as open and closed SVG polylines (L.46).4 Planar MapsPlanar maps are a topological modeling tool introduced in[START_REF] Baudelaire | Planar maps: An interaction paradigm for graphic design[END_REF] for representing drawings. All the curves manipulated by a user (imported SVG elements, operators outputs) are automatically converted into planar maps. Each of them internally represents an arrangement and provides easy accesses to precise topological relations between cells such as intersections, contacts, and inclusions.

Figure 4 :

 4 Figure 4: Planar map representation. Left: Three oriented curves. Middle: Induced planar map composed of nine vertices, nine edges and two faces. The face f 0 is unbounded.Edges are oriented accordingly to their originating curves. For example, e 1 's source vertex is v 2 and its target vertex is v 3 . Right: The incidence graph of the planar map denotes the

Figure 5 :

 5 Figure 5: Available types of partition. When designing an arrangement, the rst step is to choose a type of partition among four possible ones, whether it is a regular (a,b) or a non-regular partition(c,d). Colors denote assigned labels to faces (top) or edges (bottom). We vary the width between lines of regular partitions using periodic cycles of values. The same process is used to assign labels. The density of irregular partitions is controlled by a single parameter.

Figure 6 :

 6 Figure 6: Border behaviors. The user can choose between four partition behaviors at the domain's border. In these illustrations, a uniform partition is created on a light blue domain. One can rst simply crop the partition along the border (a), with possibly adding the domain's outline curve (b). The cells of the partition that overlap the border can also be discarded (c) or kept (d).

Figure 7 :

 7 Figure 7: Using mappers. Three examples of mappers eect on initialized partitions. Top:

Figure 8 :

 8 Figure 8: Merging multiple distributions. (a,b,c) Three simple arrangements obtained via partitioning and mapping operators. (d) The Union operator overlaps its two input arrangements. (e,f ) The Inside operator behaves like a mask, keeping only the edges from a rst arrangement that fall inside the faces of a second one. The same border management options are

Figure 9 :

 9 Figure 9: Script edition. A design strategy can be to edit iteratively a starting arrangement. (a) Original two-scale arrangement from Figure 3. (b) The grid partition previously applied to the lower scale is exchanged with the uniform partition from the blob distribution. (c) Another inversion: blobs are now regularly distributed inside the uniformly distributed cells. (d) A twig is mapped to the smooth stroke of (c), and owers or leafs with varying scales are now mapped to the blob shape.

Figures 10 ,

 10 11 and 12 illustrate how the properties usually required by artists can be obtained (see Section 1): regular and non-regular arrangements, various elements adjacency relations such as contact or overlap, compositions of several arrangements and clusters of elements. All the scripts producing these examples have less than

Figure 10 :

 10 Figure 10: Comparison with examplar-based approaches. Top: we go beyond by-example methods' limitations from Figure 2 by faithfully reproducing the target arrangements with our set of operators. Bottom:The evaluation protocol developed in[START_REF] Almeraj | Towards eective evaluation of geo-Inria metric texture synthesis algorithms[END_REF] showed that even expert

Figure 9

 9 Figure 9(d).

Figure 10 (Figure 11 :

 1011 Figure 11: Creating complex structures starting from regular partitions. Each row shows some iterative design steps, starting from an initial regular partition. (a,b,c) Two-scale examples where the initial partition is rened in dierent ways, and the resulting regions lled with various stripe patterns to produce hatching eects. (d) A mosaic-like partition is made using a grid and mapped circles. A kind of aging eect is nally obtained by deleting some faces randomly.

Figure 12 :

 12 Figure 12: Creating complex structures starting from non regular partitions. (a) First row shows two examples starting from a uniform partition, yet with radically dierent nal arrangements. (b) A random partition, after having mapped its edges with a curve, is recursively applied to its own regions, achieving a two-scale cracks eect. (c) Another two-scale arrangement, based on an inside merging operator, leading to a turtle shell eect. (d) The arrangements can quickly depart from the initial partition, even with simple renements: the edges of a random partition are directly scaled then rotated to produce various random lines distributions.

  of the appendix. All the examples shown in this paper have been created with this simple operator set:

Table 1 :

 1 Partition operators. Regular partitions StripesProperties(Scalar a,Scalar w1[,Scalar w2,...]) Sets stripes properties SetEdgeLabels(Properties p, String l1[, String l2,...]) Adds edges labels to p SetFaceLabels(Properties p, String l1[, String l2,...]) Adds faces labels to p StripesPartition(Properties p) Creates a stripes partition GridPartition(Stripes S1, Stripes S2, Border b) Creates a grid partition Irregular partitions IrregularProperties(Scalar d) Sets the partition density SetWeightedVertexLabels(Properties p, Adds vertices labels to p String l1, Scalar w1[, String l2, Scalar w2...]) SetWeightedEdgeLabels(Properties p, Adds edges labels to p String l1, Scalar w1[, String l2, Scalar w2...]) SetWeightedFaceLabels(Properties p, Adds faces labels to p String l1, Scalar w1[, String l2, Scalar w2...]) UniformPartition(Properties p, Border b) Creates a uniform partition RandomPartition(Properties p, Border b)

	Creates a random partition

RR n°8713

Applies m to all edges of A MapToFaces(Mapper m, Arrangement A)

Applies m to all edges of A