Benoît Sagot
email: benoit.sagot@inria.fr

Extracting an Etymological Database from Wiktionary

Keywords: Lexical resource development, etymology, Wiktionary

Electronic lexical resources almost never contain etymological information. The availability of such information, if properly formalised, could open up the possibility of developing automatic tools targeted towards historical and comparative linguistics, as well as significantly improving the automatic processing of ancient languages. We describe here the process we implemented for extracting etymological data from the etymological notices found in Wiktionary. We have produced a multilingual database of nearly one million lexemes and a database of more than half a million etymological relations between lexemes.

Introduction

Electronic lexical resources used in the fields of natural language processing and computational linguistics are almost exclusively synchronic resources; they mostly include information about inflectional, derivational, syntactic, semantic or even pragmatic properties of their entries. Because this information is formalised, it can be used by automatic tools.

Conversely, diachronic information such as etymology is virtually absent from electronic resources, only being present in printed or online dictionaries. The few exceptions, such as The Tower of Babel database1 or the PIElexicon project,2 often rely on comparative and etymological principles that are, at best, obsolete or non-consensual,3 and, at worst, unanimously rejected by the scientific community. 4 Only EtymWordNet (de Melo, 2014), to which we shall come back below, is an outlier in this regard, although it has other severe limitations.

The availability of formalised, detailed and large-coverage etymological databases would make it possible to develop automatic tools targeted towards historical and comparative linguistics. Modelling language evolution and reconstructing proto-languages-ancestors of attested languages-rely on a very large amount of lexical information often covering dozens, if not hundreds of languages. For some language families, such as Indo-European or Semitic languages, almost two centuries of careful work has resulted in a fairly clear understanding of lexical diachrony. However, even for these two families, and a fortiori for all others, many grey areas remain.

The development of automatic means to explore possible formal and semantic correspondences between words from different languages and to model their diachronic evolution would therefore constitute an important step forward for the linguistic sub-fields involved, while raising difficult algorithmic challenges. It would also contribute to the development of resources and tools for the automatic processing of documents written in older forms of the languages, for which they already exist for their modern variant (for instance, documents in Old or Middle English, which cannot be properly processed by tools dedicated to contemporary English). This direction of research should take advantage of the outcome of previous etymological investigations, which should therefore be encoded in the form of formalised electronic lexical resources.

To achieve this goal, we need to find a large-scale source of etymological information, to automatically extract this information from it, and to represent it in a structured or even normalised form. In this paper, we describe a first attempt at carrying out such an enterprise. We rely on the (English) Wiktionary,5 an online collaborative dictionary, whose syntax is semi-structured and which includes relatively detailed and fairly reliable etymological information.

The remainder of this paper is structured as follows. After a brief overview of previous work related to ours (Section 2) and a brief sketch of the various types of etymological relations between lexemes (Section 3), we describe how etymological information is represented in Wiktionary articles and how we extracted and partially structured this information (Section 4). In Section 5, we explain how we transformed this information into a database of lexemes and a database of etymological relations between these lexemes. We provide in Section 6 quantitative information about these two databases, their export formats-including an etymology-oriented extension of the LMF standard6 currently under discussion-and a manual evaluation of their quality. We conclude this work in Section 7 by discussing possible follow-ups to this work, including possible direct use cases for our etymological databases.

Both databases are freely available under an LGPL-LR license.

Related work

Previous work related to ours is threefold: efforts towards the standardisation of etymological information, development of existing databases, and the above-mentioned EtymWordNet.

Since etymological information is only exceptionally taken into account in electronic lexical resources, their structured representation is not yet the subject of recommendations concerning their standardisation. In this regard, the working paper published by Bowers & Romary (2016) reflects the state of ongoing research. It builds on several previous initiatives, including the work by Salmon-Alt (2006). It proposes a set of general principles for the representation of etymological information in electronic dictionaries encoded in TEI. It is based on a relatively broad typology of the underlying phenomena, which covers standard inheritance (what etymologists refer to as recto itinere, "in direct line"), borrowing, metaphor, metonymy, composition and grammaticalisation. Some of these mechanisms are not etymological in nature, but are rather lexical creation mechanisms. We shall come back in Section 6 on several limitations of this proposal in its current state.

Few freely available electronic dictionaries make use of structured representations of etymological information. We have already mentioned The Tower of Babel and the PIElexicon. Another example is the Germanic Lexicon Project7 by S. Crist, whose representation format can also be considered as a predecessor of the propositions made by Bowers & Romary (2016). However, the various free dictionaries distributed in this framework are only weakly structured: the systematic extraction of etymological relations would be a non-trivial task. This is not the case for the World Loanword Database, which, for 1,460 carefully selected meanings, provides one or more lexemes in 41 languages, each associated with a probability level that it results from a borrowing, as well as its possible source lexeme. But the inventory of the 41 languages covered reflects the typological and non-etymological positioning of the project. In any case, it is far from a widely covered resource, and, of course, only borrowing mechanisms are covered, to the exclusion of any other etymological mechanism.

Closer to our work, de Melo (2014) has made available EtymWordNet, which, like in our work, was automatically extracted from the Wiktionary (although in a three-yearold version). However, and despite extensive coverage, the EtymWordNet can not be used as it is for the computerisation of comparative and historical linguistics because of two fundamental limitations. Firstly, the mechanisms at play are not distinguished (for example, no distinction between inheritance, borrowing and morphological derivation). Secondly, and even more importantly, its basic units are lemmas, not lexemes: senses are ignored.

We are not aware of previous works that resulted in a large-scale formalised etymological database at the lexeme level, as is necessary in etymological lexicology (see Section 3) and makes a distinction between etymological mechanisms. That is the purpose of our work.

Etymological and lexical creation mechanisms

The extraction and formalisation of etymological information requires a model of this type of information. The first question that arises is that of the basic unit. As recalled by Buchi (2016: 346), only the lexeme can play this role-in our case a lexeme is defined by a citation form, a language identifier and an English gloss.8 A relation between a lexeme and another lexeme can correspond to changes in the language (diachronic change in the case of inheritance, synchronic change in the case of a borrowing), the citation form (phonetic but also morphological changes) and the meaning (semantic shifts).

The second important question is the nature of the etymological relations between lexemes. Following again Buchi (2016: 346-347), an elementary etymological relation must concern directly related lexemes: there should not be any intermediate lexemes between those involved in the relation. In the case of a recto itinere inheritance, and given an inventory of language identifiers, an elementary relation must therefore involve a lexeme in a given language and another lexeme, or several lexemes, in the immediately preceding language or language state. 9 In the case of a borrowing, a direct relation simply involves the target lexeme and its source lexeme.10 Using direct relations whenever possible is necessary to be able to correctly specify the nature of the etymological relation involved. 11The third question to address for formalising etymological relations is that of the different types of etymological mechanisms. Although we do not cover all of them in this work, we make use of the following typology:

• Inheritance (with phonetic change in most cases, with or without semantic or morphological change); as is customary, we shall note this type of relation as follows: target lexeme < source lexeme; To this inventory we shall add a special cognation relation, which will allow us to relate two lexemes (within the same language or in two different languages) that have a common or partly common etymology (in general, at least a same "root"). It will be noted lexeme 1 // lexeme 2 .

Extraction and structuration of Wiktionary's etymological information 4.1 Etymological information in Wiktionary

Wiktionary is a collaborative multilingual dictionary. It is organised into articles, which each contain one or more homonymous lexical entries13 concerning lexemes from one or more languages.

We used the 01/01/2017 dump. It contains nearly 5.5 million articles, more than 40,000 of which are redirect pages. These entries contain a total of 894,453 etymological records. This dump is in a semi-structured format: the structuration into articles is encoded in XML and includes metadata for each article; the content of each article is coded using the so-called "wiki syntax", in which the plain text is supplemented by typographical markers (different levels of titles, lists, etc.) and templates allowing the coding of certain information in a systematic way. For example, the template link (or l) can be used to encode a form that is a link to the article it is the title of. Thus, {{link|fr|chaise||chair|g=f}} will be rendered on the Wiktionary site as chaise f ("chair"), where the feminine gender is indicated (g=f) and where the word chair is a hyperlink to the section of the Wiktionary article "chaise" concerning the French lexems (fr).14

Figure 1 shows part of the Wiktionary article "manger". The corresponding source code is shown in Figure 2.

Finally, "Descendants" sections are sometimes included. They list the descendants of the lexeme at hand, without any further precision on the nature of the etymological relation (inheritance, borrowing).

Extraction and structuration

We first converted the Wiktionary dump into an XML file using a series of regular expressions. 15 This XML file is a set of lexical entries that correspond approximately to lexemes. It contains only entries for which Wiktionary provides etymological information in a dedicated section. It contains is 831,988 entries. Each of them includes the content of this etymological section in an <etymology/> tag, in which all forms, especially but not only those mentioned using templates, are represented by an XML element <form/>. Whenever several <form/> are used together (affixed derivation, composition), their combination is harmonised using the symbol "+" (see above). Whenever several alternate forms are listed (variants, principal parts. . . ), they are separated using the symbol "∼". These apparently simple standardisation steps are made complex by the variety of situations, the richness of the available templates and the multiplicity of ways used by Wiktionary contributors to represent etymological information.

If a section listing descendants is available, they are all converted into <form/> elements and are included in a dedicated <descendants/> element within the <etymology/>.

All forms mentioned in the article but outside the etymological section or the descendant section are also extracted in a special section <forms/>. This is because these forms, especially those associated with a gloss, might prove useful in the next steps of the extraction process.

Whenever possible, the lexeme at hand is associated with a gloss. If it is an English lexeme, its citation form is considered as its own gloss. In all other cases, we try to extract one or several glosses based on the definitions provided in the article.

From the source code corresponding to the French verb manger, shown in Figure 2, our structuration process outputs the entry given in Figure 3.

<entry id="manger#French"> <header><form lang="Fr." l="fr" sense="to eat; food; foodstuff">manger</form></header> <etymology> From <form lang="MFr." l="frm" trgl="fr" trglang="Fr." type="inherited">manger</form>, from <form lang="OFr." l="fro" trgl="fr" trglang="Fr." type="inherited">mengier</form>, from <form lang="LL." l="la-lat" sense="to chew, devour" trgl="fr" trglang="Fr." type="inherited">manducāre</form>, present active infinitive of <form lang="Lat." l="la">manducō</form>, from <form lang="Lat." l="la" trgl="fr" trglang="Fr." type="inherited">mandō</form>. </etymology> <forms> <form lang="Fr." l="fr">gramen</form> <form lang="Fr." l="fr">magner</form> </forms> </entry>

Construction of the etymological database

The output of the structuration process described in the previous section is much easier to exploit than the original Wiktionary dump. However, several challenges remain. The main one is of course that the etymological information is given in plain English, apart from the <form/> elements. Another one is that, from one article to the other, a same lexeme can associated with different glosses, if any.

To address these challenges, we proceed in several steps. First, we defined a number of regular patterns for infering the gloss of a non-glossed form based on its context. 16 In such a case, the corresponding <form/> element is updated accordingly.

We then process all entries and the etymological information they contain, in order to create triples of the form (target lexeme, source lexeme or source lexeme sequence, type of the relation). We now have to merge synonymous lexemes as much as possible. For instance, if the triples we built involve lexemes such as Fr. bêtement 'stupidly, idiotically', Fr. bêtement '(no gloss)' and Fr. bêtement 'stupidly, foolishly', these three lexemes need to be merged into a lexeme Fr. bêtement 'stupidly, idiotically, foolishy'. To achieve this goal, we iterate the following steps until stability:

• If a gloss-less lexeme has the same language and the same citation form as exactly one (glossed) lexeme, then these lexemes are merged. • If two glossed lexemes have the same language, the same citation form, and at least one gloss in common (cf. 'stupidly, foolishly' vs. 'stupidly, idiotically'), then they are merged (in this example, it creates a lexeme with the gloss 'stupidly, foolishly, idiotically', as mentioned above); • All triples encoding etymological relations are then updated accordingly.

In order to restrict as much as possible our set of etymological relations to direct relations, we remove any relation between two lexemes lexeme 1 et lexeme 3 such that there exists a relation between lexeme 1 and an intermediate lexeme lexeme 2 and a relation between this lexeme 2 and lexeme 3 .17

Finaly, the type of certain relations is corrected, in order to indicate as precisely as possible cases of borrowing or morphological derivation rather than inheritance, this latter case still remaining the default one.

The outcome of this extraction process is twofold: a set of lexemes, only some of them being glossed, and a set of etymological relations involving a target lexeme, one or more source lexemes (two or more in case of composition or affixal derivations) and a relation type.

Results and evaluation

Quantitative information

The initial extraction process described at the beginning of Section 5 has produced almost 1.2 million lexemes, 62,056 lexeme sequences and 548,935 etymological relations between two lexemes or between a lexeme and a sequence of lexemes.18 A few dozen iterations of the lexeme merging algorithm merged 199,185 lexemes and 289 lexeme sequences, resulting in 975,473 distinct lexemes, 61,809 distinct lexeme sequences and 519,348 distinct relations. After discarding 5,149 non-diret relations, the final number of relations is 514,199.

The lexemes obtained belong to 2311 distinct languages, the best represented of which are, in decreasing order, English (257,978 lexemes), Latin (65,981), French (32,044), Italian (28,028), and Ancient Greek (21,077). Among these lexemes, 659,567 (68%) have a gloss.

Among the 514,199 relations, 452,041 relate two lexemes, whereas other relations relate a lexeme and a lexeme sequence. There are 90,511, cognation relations, all other 423,673 relations being direct relations. Finally, 318,883 relations involved glossed lexemes only.

Note that we could have easily created many more cognation relations by adding relations sharing a (direct or indirect) ancestor in our database.

Etymological chain inference and TEI export

We have developed an export module for our etymological relation database that encodes data in the TEI format proposed by Bowers & Romary (2016). In this format, direct relations wan be exported in the form of simple <etym/> elements, associated with the type of the relation at hand. For a given lexeme, it can also be interesting to have not only its direct etymon but also its etymological history in as exhaustive a way as possible. In fact, such an etymological chain is often provided in the etymological information included in Wiktionary articles, as exemplified in Figures 1 and2. In order to re-build these etymological chains (or derivations) from our relation database, one can simply recursively retrieve relations involving each etymon involved. For instance, from Fr. manger 'to eat' < MFr. manger 'to eat' and MFr. manger 'to eat' < OFr. mengier 'to eat', one can re-build the chain Fr. manger 'to eat' < MFr. manger 'to eat' < OFr. mengier. This is how we created etymological chains, before encoding them in TEI.

We had to extend the proposal by Bowers & Romary (2016) in four directions, which could serve as a source of inspiration for its further improvement:

• This proposition does not cover the cogation relation. We therefore introduce an additional relation type (type="cognate") to the element <etym/>. • It does not allow to refer to another lexical entry providing relevant etymological relation. We therefore introduce a new type (type="reference") to the <etym/> element, within which a direct reference to the relevant lexical entry can be included with an <xr/> (TEI element used for cross-references). • Bowers & Romary (2016) do not provide any way to encode etymological chains. We simply used a special <etym/> element, which, using a dedicated attribute, indicates that it contains a sequence of etymological relations, each of them being represented by a specific <etym/> element within the global <etym/> element. • In their document, Bowers & Romary (2016) do not allow for alternative etymological hypotheses, something which is frequent in our database. In this case, we also make use of a special <etym/> element, which indicates using a dedicated attribute that it contains alternative hypotheses, each of them represented by a distinct <etym/>.

In the two last cases, the recursivity of <etym/> elements allows for any possible combinations, such as an etymological chain starting with two "certain" steps followed by an alternative between two different etymological sub-chains.

Manual evaluation

The evaluation of our etymological relation database could be carried out with four different questions in mind:

1. What is the quality of the etymological information provided by the Wiktionary? 2. What are the errors caused by our extraction and structuration process? 3. What are the errors introduced by our gloss inference and lexeme merging algorithms?

Conversely, what is the coverage of these algorithms? 4. Which errors result from the fact that non-typed relations are interpreted by default as inheritance relations?

A detailed answer to the first question is not straightforward, and falls beyond the scope of this paper. An informal study of the etymological information found in a random set <entry xml:id="sla-pro:gostinȗ:guest" xml:lang="sla-pro"> <form type="lemma"> <orth>gostinȗ</orth> </form> <sense> <cit type="translation" xml:lang="en"> <oRef>guest<oRef> </cit> </sense> <etym type="suffixalDerivation"> <cit type="etymon"> <oRef xml:lang="sla-pro">gostȋ</oRef> <gloss>guest</gloss> <etym type="inheritance"> <cit type="etymon"> <oRef xml:lang="ine-pro">g h óstis</oRef> <gloss>stranger, guest, host, someone with whom one has reciprocal duties of hospitality</gloss> </cit> </etym> </cit> <cit type="etymon"> <oRef xml:lang="sla-pro">-inȗ</oRef> </cit> </etym> </entry> of articles showed that this information is usually reliable. Only Proto-Indo-European etyma sometimes reflect of a somewhat obsolete knowledge of the field. Nevertheless, it can be considered that etymological information in Wiktionary can generally be trusted, and often reflect the most recent and consensual scientific literature, which are often cited in the references.

The precision and recall of our gloss inference and lexeme merging algorithms are easier to evaluate. We first focused on the recall of the merging algorithm. We randomly selected 50 (language, citation form) pairs among the 124,775 ones (out of 941,757) that correspond to more than one entries. We then extracted all entries for these 50 pairs, and have manually annotated the relevance of their co-existence (as opposed to merging them). In almost all cases, additional merges would have been relevant, but our algorithm was not able to perform these merges. It is therefore an obvious direction for future improvements. Conversely, in order to evaluate the precision of our merging algorithm and that of our gloss inference algorithm, we randomly extracted 100 glossed forms and checked the quality and coherence of their glosses. Out of these 100, we identified two extraction errors (both caused by an unusual use of the "wiki" syntax by contributors), a partial error (some of the glosses are correct, one of them is an easily dismissable "wiki" code fragment), a transcription misinsterpreted as a gloss, and a (correct) definition misinterpreted as a gloss. All other glossed forms were fully correct. Therefore, there are only a few errors, which are almost never caused by our merging and glossing algorithms-yet the extraction and structuration algorithm could be slightly improved.

Finally, we evaluated the etymological relations themselves based on a random set of size 100. Among them, 78 are correct, 18 have type "inheritance" whereas they encode borrowings, three of them have other relation typing errors, and only one is errineous because of an error while extracting the article. The 18 errors of type "inheritance" instead of "borrowing" are the result of the fact that inheritance is the default relation type, used when the latter is not explicitely provided in the Wiktionary. A finer description of the relations between languages would make it possible to automatically correct these examples. This is something we will do in the near future.

Comparison with EtymWordnet

EtymWordNet de Melo (2014), freely available without an explicit license,19 is an etymological database extracted from Wiktionary, although from a dump dating back to 2013. In this resource, contrarily to the one we built, relations are not typed with a sufficient granularity (it only distinguishes between a cognacy relation and a generic etymological origin relation). 20 Moreover, it relates non-glossed citation forms (rather than lexemes). Nevertheless, it is the only resource that is comparable with ours. We therefore evaluated our etymological relation database with respect to this resource.

EtymWordNet contains 473,433 direct yet non-typed etymological relations as well as 538,558 cognacy relations. As mentioned above, many cognation relations can be added based on other relations. The most interesting etymological information is provided by these other relations, which are unfortunately not distinguished within EtymWordNet. Another issue with EtymWordNet is that derivation and composition relations are not modelled in a satisfying way. For instance, (American) English monophthongize is the source of two independent etymological relations, one with -ize and the other one with monophthong.

To make the comparison possible, we had to transform our relations (excluding cognation relations) so that they follow the same model as EtymWordNet. Unsurprisingly, this slightly lowers the number of relations to 559,614. Among them, 464,542 (83%) are not found in EtymWordNet. Conversely, 378,361 relations are only found in EtymWordNet. But among these 378,361 relations, 333,369 (88%) relate forms from the same language: they are derivation or composition relations, extracted from other parts of the Wiktionary articles than the etymological part we exploited (especially the "derived terms" sections). Such relations are less interesting from an etymological point of view. Among the other missing relations, a large (yet hard to quantify) number of them are almost identical to relations that are included in our database, differing only by diacricts added in Wiktionary since 2013. Overall, this comparison shows that our database is significantly richer than EtymWordNet-and recall that our database relates (mostly glossed) lexemes with typed relations correctly representing inheritance, borrowings, derivation and composition, whereas EtymWordNet relates (non-glossed) citation forms with non typed relations (apart from the notion of cognacy relation).

Future work: improvement and use of our etymological database

The work presented here shall be improved in two ways. Firstly, patterns used for information extraction from etymological sections in Wiktionary articles can be extended, improved, refined. Secondly, the lexeme merging algorithm can be enriched so as to merge lexemes which are not merged yet, mostly because variation of the following types:

• formal variations: differences in transcription or notation, form with or without stress information, 21 complete citation form vs. truncated citation form vs. principal parts; 22 • variation in glosses [START_REF] Fr | aise 'ease' and Fr. aise 'satisfaction, joy' are not merged yet, which prevents a further merging with Fr. aise '(pas de glose)' because of the resulting spurious ambiguity[END_REF] (for instance using WordNet or distributional similarity information).

The way we gloss lexemes that have no gloss in Wiktionary can also be improved, for instance by better taking advantage of their context of occurrences and by using external bilingual or multilingual resources.

A model of the phylogenetic relations between languages would also help replacing indirect relations with direct ones, either using simple heuristics or based on a (partial) model of phonetic (and maybe morphological) change. For instance, the relation Fr. chapitre 'chapter' < OFr. chapitre 'chapter' could be replaced by a relation MFr. chapitre 'chapter' < OFr. chapitre and a relation MFr. chapitre 'chapter' < OFr. chapitre, simply by knowing that, given our language inventory, the immediate ancestor of French is Middle French, whose immediate ancestor is Old French. It could help extending the lexicons for a number of intermediate languages with attested words, which could be validated using external lexical resources, or even unattested words.

Finally, it would be useful to extract the etymological information available in other Wiktionary editions, especially its French edition, the Wiktionnaire. Our databases are only affected by the language of the original information source at the level of glosses. We could automatically replace French glosses extracted from the Wiktionnaire by English glosses, for example by exploiting the English translations provided in the Wiktionnaire articles themselves.

In addition to lexicon extension for intermediate languages, as mentioned above, the resource presented in this article could be used as a starting point for research in computational historical linguistics, as suggested in the introduction. It may also be subjected to automated internal consistency checks, for example by automatically extracting phonetic laws and verifying their systematic applicability, modulo the analogical levelling phenomena. In the long term, this could also allows the construction or the automatic completion of large-coverage etymological dictionaries.

Figure 1 :

 1 Figure 1: Part of a Wiktionary entry

Figure 2 :

 2 Figure 2: Source code corresponding to the article part shown in Figure 1 (the pronunciation-related part is not shown)

Figure 3 :

 3 Figure3: Output of our structuration process for the input source code shown in Figure2

Figure 4 :

 4 Figure 4: Example of a TEI-formatted entry (cognation relations are not shown)

  • Borrowing; we shall note this type of relation as follows: target lexeme ← source lexeme; 12 • Lexical creation -Morphological derivation * Suffixal derivation; it will be noted as follows: target lexeme < s base + suffix;

* Prefixal derivation; it will be noted as follows: target lexeme < p prefix + base; * Other cases (including analogy-based derivation); they will be noted as follows: target lexeme < d element + . . . + element; -Morphological composition, noted as follows: target lexeme < c component + . . . + component; -Portmanteau word creation, not covered in this work; -Truncation and other phenomena, not covered in this work.

  Here are a few real examples concerning French lexemes: • Fr. gobelet 'goblet' < OFr. gobel 'goblet; cup; beaker; tumbler' • Fr. maudire 'to curse' < OFr. maudire ∼ maldire 'to curse' • Fr. éponger 'to sponge; to absorb' < s Fr. éponge 'sponge' + Fr. -er • Fr. idéologie 'ideology' < d Fr. idéo-+ Fr. -logie • Fr. acajou 'cashew' ← Port. acajú 'cashew' • Fr. car 'car; coach' ← E car

http://starling.rinet.ru/babel.php?lan=en

http://pielexicon.hum.helsinki.fi

The Indo-European database in The Tower of Babel is based on the Pokorny dictionary, which is now outdated. Moreover, the authors of this database defend non-consensual views on genetic relationships between traditional language families. These views are generally rejected by the scientific community yet still influence some of their etymological proposals.

This applies to the PIElexicon, although the justification of such a statement lies beyond the scope of this paper.

https://en.Wiktionary.org/

Lexical Markup Framework. See below for details.

http://lexicon.ff.cuni.cz/texts/pgmc_torp_about.html

This also covers the case of place names, person names, people/tribe names, and other proper names.

Fr. manger < Mid. Fr. manger is therefore a direct relation, contrarily to Fr. manger < Old Fr. mengier and Fr. manger < Late Lat. manducāre, which are indirect relations.

For instance, relations such asFr. abricot 'apricot' < Esp. albaricoque 'id.' and Fr. abricot < Port. albricoque 'id.' are possible direct relations (both are plausible). The Spanish and Portuguese words are borrowings from Ar. al-barqūq 'id.', itself a borrowing from Med. Gr. βερικόκκια 'apricot tree', derived from Ancient Gr. πραικόκιον 'apricot', itself a borrowing from Lat. praecoquum 'early (fruit)'. Therefore, a relation such as Fr. abricot < Lat. praecoquum would be correct but not direct.

11 Going back to the example introduced in the previous footnote, it would be difficult to assign a simple type to the etymological relation between Lat. praecoquum et Fr. abricot, as it covers several steps of different

natures.12 We include in this category all cases of learned loans such as Fr. oculaire 'ocular' ← Lat.

ocularis 'id.'. 13 Two lexical entries are homonymous if they share the same citation form, independently of the language or part-of-speech of the two underlying lexemes.

The language inventory used by Wiktionary is based on the ISO-639-1 to ISO-639-3 standards, with extensions when needed. For more details, cf. https://en.Wiktionary.org/wiki/Wiktionary:Languages. Based on the correspondence between language codes and language names, we also set up a system for the automatic abbreviation of language names as well as a system for the identification of language (codes) based on their usual names or abbreviations as used in the Wiktionary articles. Thus, "OFr.", "Old Fr." or "Old French" are correctly interpreted as reflecting the fro language code, which can then be transformed into its standard English abbreviation, " OFr. "

This XML format is a working format. It is not intended at this stage to be suitable for TEI compatibility. We shall return in Section 6.2 on how we exported etymological information to an extended TEI format.

Coming back to our French running example manger, the phrase "From Middle French manger, from Old French mengier. . . ", although it contains no glosses, makes it possible to associate the gloss of the head lexeme manger, namely 'to eat', to MFr. manger et OFr. mangier.

The same mechanism applies when lexeme 3 is not a unique lexeme but a sequence of lexemes.

In these figures and in all figures below, lexemes invovled in zero relations are not counted.

http://www1.icsi.berkeley.edu/~demelo/etymwn/

We ignore relations of the type "orthographic variant".

. Data structures for etymology: towards an etymological lexical network. BULAG, 31, pp. 1-12.

This work is licensed under the Creative Commons Attribution ShareAlike 4.0 International License. http://creativecommons.org/licenses/by-sa/4.0/


Weikai Chen

Sylvain Lefebvre

Jonàs Martínez

Fabricable Tile Decors

Keywords: Computing methodologies → Mesh geometry models; fabrication, tiles, packing, foldable

. Given a target surface and a set of user-specified tiles (top left), our method produces a dedicated packing of tiles that is optimized for fabrication (bottom left). The results are printed as independent flat patches (second column) with integrated hinges and snap-fit joints. The patches are folded and assembled into the final object (third column); in this case a functional handbag that can carry light objects.

Recent advances in 3D printing have made it easier to manufacture customized objects by ordinary users in an affordable manner, and therefore spurred high demand for more accessible methods for designing and fabricating 3D objects of various shapes and functionalities. In this paper we present a novel approach to model and fabricate surface-like objects composed of connected tiles, which can be used as objects in daily life, such as ornaments, covers, shades or handbags.

Our method is designed to maximize the efficiency and ease of fabrication. Given a base surface and a set of tile elements as user input, our method generates a tight packing of connected tiles on the surface. We apply an efficient and tailored optimization scheme to pack the tiles on the base surface with fabrication constraints. Then, to facilitate the fabrication process, we use a novel method based on minimal spanning tree to decompose the set of connected tiles into several connected patches. Each patch is articulated and can be developed into a plane. This allows printing with an inexpensive FDM printing process without requiring any supporting structures, which are often troublesome to remove. Finally, the separately printed patches are reassembled to form the final physical object, a shell surface composed of connected user-specified tiles that take the shape of the input base surface. We demonstrate the utility of our method by modeling and fabricating a variety of objects, from simple decorative spheres to moderately complex

INTRODUCTION

Additive manufacturing is paving the way to mass customization, enabling ordinary users to create their own version of a base product and customizing it in creative and beautiful ways. With the increasing availability of 3D printers in FabLabs and homes, users can fabricate their customized objects directly in a wide variety of colors and materials. However, design customization remains a difficult task for non-expert users. Hence, there has been significant research dedicated to providing computational support for customization of shapes, materials, and functionality of 3D objects. For instance, researchers have focused on shape optimization for balancing [START_REF] Prévost | Make it stand: balancing shapes for 3D fabrication[END_REF], creating spinnable objects [START_REF] Bächer | Spin-It: Optimizing Moment of Inertia for Spinnable Objects[END_REF], turning surfaces into physical filigrees [START_REF] Chen | Synthesis of Filigrees for Digital Fabrication[END_REF], designing wind instruments [START_REF] Li | Acoustic Voxels: Computational Optimization of Modular Acoustic Filters[END_REF][START_REF] Umetani | Printone: Interactive Resonance Simulation for Free-form Print-wind Instrument Design[END_REF], lampshades [START_REF] Zhao | Printed Perforated Lampshades for Continuous Projective Images[END_REF]] and helping users maintain fabricability during modifications [START_REF] Shugrina | Fab forms: customizable objects for fabrication with validity and geometry caching[END_REF].

In this paper we study the modeling and fabrication of customized decoration patterns obtained by packing together distinct decorative elements, or tiles. Such patterns are ubiquitous in fashion and design; hobbyists often create them by juxtaposing existing decorations, e.g. stickers or decals. Our goal is to enable non-expert users to digitally model such decoration on a base surface with a set of flat tiles. Taken together, these tiles are joined by hinges and connectors to form an articulated object that takes the shape of the input surface and can be fabricated using a home printer (see Figure 1). This is a challenging problem as the tiles must be closely packed and properly connected to each other in order to define a shelllike object. Furthermore, fabrication is made difficult by the hollow nature of the shape. Printing directly with a filament printer requires a large amount of support structures. Besides wasting time and material, the supports are particularly difficult to remove as they end up enclosed within the shape itself (see Figure 2). Even on a high-end powder-based system (e.g. SLS), the part occupies a large volume while using little material. It is thus not very efficient to print, as only few objects can be made in a single batch. Therefore, there is no easy option to efficiently print such objects on widely accessible printers.

Our approach directly takes fabrication constraints into account. The constituent tiles of the synthesized object are joined by hinges instead of rigid connectors. This allows neighboring tiles to rotate with respect to one another. Instead of producing a single final object for printing, we propose to decompose the synthesized shelllike object into a small number of connected tiles subsets, which we call patches. We carefully place the hinges to ensure that the patches are developable, and output each patch in its developed (flat) configuration. This has a major advantage: all the tiles of a patch as well as their connecting hinges can be printed flat on a low-cost filament printer, in a single print session. No support is required. After printing, all patches are folded and assembled back together, using snap-fit connectors printed along their boundaries. The result, locked in its final position, is the desired shell-like object.

The main contributions of this paper are: A large amount of support is required, and it is not easily accessible for removal.

• A new approach to fabricate shell-like flexible objects composed of user-specified tiles in an affordable and easy way, using a standard filament printer. Such objects can be used as objects in daily life, such as ornaments, covers, handbags, etc. (see Figures 1,19). • A novel packing algorithm on surfaces that is specifically tailored to take into account connectivity constraints and fabrication considerations. • A new segmentation method that decomposes the network of connected tiles into a small number of developable patches in order to facilitate the fabrication of these patches without supports on a standard filament printer.

PREVIOUS WORK

Art and design. As early adopters of additive manufacturing, artists are constantly pushing the boundaries of fashion and design. Among the many examples of this trend, Nervous System [Rosenkrantz and Louis-Rosenberg 2007] has produced beautiful flexible designs made of many interconnected triangles -the resulting objects are bracelets, necklaces or even full dresses. The flexibility is obtained by placing hinges in between the triangles of a densely tessellated initial flat surface. As a result, the designs can be printed flat, pre-assembled, on low-cost printers.

While this is a key inspiration for us -in particular showing the importance of taking into account printability concerns in the design itself -our goal is different. We seek to produce 3D structures made of packed, arbitrary shaped tiles. We do not have a base flat contour to work from, and we approximate a target 3D surface.

Pattern synthesis. Several recent works consider the problem of decorating surfaces to turn them into printable objects, with the same purpose of customization for 3D printing. [START_REF] Zhou | Topology-constrained synthesis of vector patterns[END_REF] synthesize connected patterns along curves, and use their approach to model fabricable 3D objects. [START_REF] Dumas | By-Example Synthesis of Structurally Sound Patterns[END_REF] modify texture synthesis to account for structure and rigidity, and synthesize printable 3D patterns that cover a base surface. [START_REF] Chen | Synthesis of Filigrees for Digital Fabrication[END_REF] synthesize filigree-like structures along surfaces. Their approach is close to ours since the input is a set of base elements and a target surface. However, they relax the packing problem by allowing appearance-preserving overlaps between elements. This produces appealing patterns, but cannot guarantee their base shape is preserved, and thus forbids the use of patterns with a semantic meaning (e.g. a fish, a heart, a letter). [START_REF] Zehnder | Designing structurally-sound ornamental curve networks[END_REF] explore the interactive design of curve networks onto surfaces. The user positions curve elements (visually similar to a bent wire) onto a surface. The curves are simulated as elastic rods, giving a very natural feel to their deformations, while intersections are disallowed to preserve their appearance. Tight packings are achieved thanks to deformations. This approach produces beautiful, airy curve networks that can be fabricated on high-end printers.

All the aforementioned techniques output complex yet hollow 3D geometries that are challenging to print. In contrast, our approach strives to produce an easy and efficient to print output.

Packing onto surfaces. The packing of shapes into the plane is an important topic of research with many industrial applications (e.g. textile). However, packing on surfaces has been less explored. [START_REF] Lai | Surface mosaics[END_REF] and Dos [START_REF] Passos | 3D virtual mosaics: Opus Palladium and mixed styles[END_REF][START_REF] Wang | A least-norm approach to flattenable mesh surface processing[END_REF] proposed methods for creating mosaics on surfaces using convex planar tiles. [START_REF] Hu | Surface Mosaic Synthesis With Irregular Tiles[END_REF] recently proposed an approach for surface mosaics that supports irregular planar tiles. It operates through iterated continuous and combinatorial steps. [START_REF] Ma | Discrete Element Textures[END_REF] and [START_REF] Roveri | Example based repetitive structure synthesis[END_REF] consider a data-driven synthesis of packings from exemplar elements. [START_REF] Schumacher | Stenciling: Designing Structurally-Sound Surfaces with Decorative Patterns[END_REF] present stenciling, a complementary work to ours, which brings together element packing and structural optimization in an elegant, joint optimization. Stenciling approximates each tile as a circle in a packing objective, making it solvable by a gradient-based method. That is however not ideal in our scenario as we seek for dense packing. The approximation would lead to difficulties for joint placement along concave tiles, as the actual tile boundary differs significantly from a circle. Other techniques consider pattern distributions by locally mapping 2D elements (i.e. decals) onto surfaces, e.g. [START_REF] Lefebvre | Texture Sprites: Texture Elements Splatted on Surfaces[END_REF][START_REF] Schmidt | Interactive Decal Compositing with Discrete Exponential Maps[END_REF]Wang et al. 2016a]. These are less suited to our needs as we seek to preserve the planarity of the packed elements.

In this work we use the approach of [START_REF] Hu | Surface Mosaic Synthesis With Irregular Tiles[END_REF] as a comparison baseline regarding packing quality; please refer to supplemental material. It is worth noting, however, that the problem settings are different. The aforementioned techniques are geared towards mosaicking, where large numbers of relatively small tiles are placed. We instead have to use fewer tiles, large with respect to object curvature, to accommodate for fabrication constraints.

Fabrication from sheets and wires. Several recent works focus on helping users fabricate shapes from simpler materials. [START_REF] Miguel | Computational Design of Stable Planar-Rod Structures[END_REF] optimize wire sculptures that approximate input surfaces. [START_REF] Iarussi | WrapIt: Computer-assisted Crafting of Wire Wrapped Jewelry[END_REF] present an approach for wire jewelry design. Other approaches consider fabrication from paper or similar planar sheets. The original surface is unfolded into charts [START_REF] Shatz | Paper craft models from meshes[END_REF] or strips [START_REF] Mitani | Making papercraft toys from meshes using strip-based approximate unfolding[END_REF][START_REF] Takezawa | Fabrication of freeform objects by principal strips[END_REF] which can be cut, folded and assembled to approximate the input. Fabrication from flat surfaces has also been studied for modeling large objects from laser cut wood pieces [START_REF] Cignoni | Field-aligned mesh joinery[END_REF], for modeling tight-fit cloths from 3D scanners by automatic flattening [START_REF] Zhang | Optimal fitting of strain-controlled flattenable mesh surfaces[END_REF], to fabricate surfaces that self-fold under the action of heat [START_REF] Kwok | Four-dimensional printing for freeform surfaces: design optimization of origami and kirigami structures[END_REF], to fabricate iris folding patterns [START_REF] Igarashi | Computational design of iris folding patterns[END_REF] and to fabricate wire mesh sheets [START_REF] Garg | Wire Mesh Design[END_REF]] and auxetic planar materials [START_REF] Konaković | Beyond developable: computational design and fabrication with auxetic materials[END_REF].

While our approach shares the idea of assembling from planar patches, our problem setting is very different as we consider networks of rigid planar tiles along the surface, and exploit 3D printed hinges to fold patches into shape.

3D printing large objects. Solutions have been proposed for printing large objects, which either do not fit the printer, or occupy a large volume compared to their material use. A first set of methods decompose a shape into smaller parts, for later assembly [START_REF] Luo | Chopper: Partitioning Models Into 3D-Printable Parts[END_REF]. Other methods additionally consider how to pack the parts together for printing [START_REF] Attene | Shapes in a Box: Disassembling 3D Objects for Efficient Packing and Fabrication[END_REF][START_REF] Chen | Dapper: decompose-and-pack for 3D printing[END_REF][START_REF] Vanek | PackMerger: A 3D Print Volume Optimizer[END_REF]. Wang et al. [2016b] decompose objects into smaller parts for maximizing print quality, changing the print direction of each subpart. Finally, [START_REF] Song | CofiFab: Coarse-To-Fine Fabrication of Large 3D Objects[END_REF] decompose large objects into small pieces that are 3D printed and then fixed to an internal, laser-cut structure.

The tile packings generated by our approach are not an ideal input for the aforementioned methods, as cross sections are thin everywhere. By proposing a method specifically tailored to our outputs, we are able to introduce rotational degrees of freedoms between tiles and can fully unfold large patches, maximizing print efficiency.

OVERVIEW

Our approach starts from a set of user-specified tiles, and a target surface represented by a triangular mesh S. The output is a set of foldable patches that (1) can be printed flat without support and (2) are made of tiles interconnected by hinges with a rotational degree of freedom. Each patch can be folded and assembled with other patches in order to approximate S (see Figure 1). We refer to the surface assembled from the synthesized tile patches as the tile network (see Figure 11a). The tile network is optimized to approximate the target surface. The user can optionally specify a varying tile scale and orientation field along the surface, as well as choose different tiles in different parts of the surface. Note that our objective is to provide an efficient approach for fabricating tile decors that can stand on their own (e.g. bag, vase, teddy bear), as well as form covers over objects (lampshade). We have incorporated a simple physical simulation that considers both gravity and common pinch forces (Section 5.3.1), but the tile decors in our case are indeed not appropriate to carry large loads. Nevertheless, our experiments have shown that the printed results maintain their shape in daily use (Fig. 19).

Fabrication Constraints. In order to connect adjacent tiles, parts of the tiles need to be carved out so as to insert joints (see Figure 3). However, the tiles may contain narrow features and concavities. As illustrated in Figure 4, we need to take care to position the tiles such that they face each others along sufficiently large areas, allowing for creating cavities to insert joints. In addition, a tile typically has multiple connectors and we have to avoid conflicts -overlapsbetween different cavities (see Figure 14). Our approach does not support tiles that are thin everywhere, e.g. thin wire-like structures, as they offer no space for connectors.

Pipeline overview

Our framework consists of two main steps: tile packing and patch extraction. During tile packing, tiles are densely packed over the base surface. The tiles are kept aligned with the tangent plane passing through their centroid so that the result covers the base surface, which is convenient to produce tile networks that cover a given object.

Unlike conventional packing methods which solely focus on maximizing surface coverage [START_REF] Hu | Surface Mosaic Synthesis With Irregular Tiles[END_REF], we seek to produce a dense packing of irregular tiles that 1) satisfies fabrication constraints and 2) follows the target surface as closely as possible. This results in a complex optimization problem, with both non smooth and combinatorial aspects (number of tiles, interlocking of concavities). We therefore propose a dedicated optimization that can jointly optimize the positions, scales and orientations of the tiles in order to enforce fabrication constraints and approximate the base surface. We detail the tile packing in Section 4. After packing, we divide the tile network into several flat, foldable patches. We resort on two types of joints for connecting the tiles: hinge joints (Figure 3a), which allow rotations between two connected tiles, keeping their inter-distance constant; and snap-fit hinge joints (Figure 3c), which are printed disconnected and later assembled to connect tiles within and across patches. For the sake of clarity, we refer to the later type of joints simply as snap-fits. After assembly, hinges and snap-fits impose distance constraints between the tiles, locking the assembled patches into a stable surface in most cases. The details of patch extraction are discussed in Section 5.

TILE PACKING

In this section, we detail our tailored optimization tile packing algorithm. Dense packings of irregular flat tiles (mosaicking) cannot be optimized via traditional gradient based approaches [START_REF] Hu | Surface Mosaic Synthesis With Irregular Tiles[END_REF]. Compared to mosaicking, we also face additional constraints: fabrication imposes the use of fewer tiles that are relatively large compared to surface curvature (this stems from limitations in minimal printable feature size and maximum object size). This makes packing even more difficult, especially as the tiles remain planar and rigid. We also have to ensure that the tiles are neighboring in a way that allows the insertion of connectors.

Our approach is based on a two-phase attract-and-repulse mechanism that iteratively refines an initial layout towards our goal. Figure 6 illustrates the idea behind the proposed mechanism. (1) We first initialize the distribution of tiles by enforcing that each newly placed tile has a limited overlap with existing ones. (2) During the attraction phase, tiles are attracting each other to form near-uniform overlaps. The fabrication constraints are considered during optimization. After tile attraction, empty spaces may appear providing room for adding new tiles. This progressively increases surface coverage (Figure 6c). The attraction phase iterates until no more tiles can be added. (3) The repulsion phase resolves remaining tile overlaps by encouraging tiles to repel their neighbors. This is achieved by adaptively scaling tile sizes and optimizing both tile placement and orientation. We stop the repulsion phase when a uniform inter-spacing among tiles is achieved.

Tile representation

We input tiles as 2D closed boundary polygons in the XY plane, with the origin at their centroid. During optimization, we only consider a sampling of the contours, as shown in Figure 5b. We use two different samplings for performance reasons: the finest is a sampling with a spacing of 2 mm and the coarsest is a sampling with a constant number of 20 samples per tile. The 3D geometry of the tiles is reconstructed during post-processing. The tiles may only be uniformly scaled during optimization, and are otherwise kept unmodified.

Initialization

We initialize the tile distribution following multi-class blue noise sampling [START_REF] Wei | Multi-class blue noise sampling[END_REF]]. We made this choice as it provides a reasonably good initialization while accommodating for simple controls regarding mixing different tiles and considering overlaps.

New tiles are placed around the boundary of existing tiles, following a dart-throwing procedure. We accept a new tile position if it satisfies both of the following criteria: (1) it slightly overlaps with existing tiles; and (2) the overlapping ratio with each existing tile is below a given threshold. This encourages a dense initialization - overlaps are resolved later. This process is repeated until a maximum number of trials has been reached (1500 in our implementation).

If no control field is provided, i.e. orientation is free, we optimize the orientation of the newly positioned tile so as to increase the possibility of placing hinges between neighbors, as will be detailed in Section 4.3.2. If, however, a control field is provided, the new tile is scaled and orientated as dictated by the control field at the tile insertion position. The tile position is then immediately optimized to maximize its hinge area, as detailed in Section 4.3.1. Immediately optimizing inserted tiles limits the creation of bad local cases for the following global optimization steps.

Using different tiles. When using different tiles, we found it necessary to explicitly encourage mixing. Specifically, for tiles belonging to different classes the overlap area should not exceed 20% of the area of the tiles, while the threshold is reduced to 5% for tiles of the same class. This encourages tiles from different classes to be neighbors while prohibiting tiles of a same class from staying too close, which is demonstrated in Figure 6a.

Attraction phase

The attraction phase distributes and optimizes the position of the tiles to bring them closer together. The optimization variables are the number of tiles, the positions of their centroids along the surface, their sizes (uniform scaling), and their orientations (angle around normal).

Objective function.

The objective function is a combination of three terms, designed to encourage the tiles to come closer together (neighborhood distance) while fitting the surface (local surface approximation) and allowing for hinge placement (hinge area).

Neighborhood distance. We define the set of direct neighbors N i of a tile T i as the set of tiles that are overlapping T i , e.g. {T j |T i ∩ T j ∅, j i}. The intersection is tested after projecting each tile to a common projection plane, which is orthogonal to the bisector plane of the support planes of T i and T j (dashed line in Figure 7).

N i =
We define the neighborhood distance between a tile T i and its neighborhood N i as:

dist(T i , N i ) = max p j ∈ P N i (dist(p j ,T i )) (1)
where P N i is the point set formed by the union of all the sample points of the tiles in N i that lie inside T i (green dots in Figure 8). dist(p j ,T i ) returns the shortest distance of point p j to the boundary of T i . Since T i and the tiles in N i are not coplanar, we project the points in P N i onto the plane of T i to perform all the distance computations. dist(T i , N i ) evaluates to a large value if N i = ∅ (i.e. T i has no overlaps). Intuitively, minimizing dist(T i , N i ) encourages T i to be attracted to adjacent tiles while preserving a minimum overlap with each neighbor when tiles come together.

Local surface approximation. The tiles are aligned with the tangent plane of the base surface S at their centroid. In high-curvature regions this quickly leads to large deviations from S. We penalize such configurations by defining the following approximation error for a tile T i :

approx(T i , S) = max p i ∈T i (dist(p i , S)) (2)
where dist(p i , S) returns the (Euclidean) distance from point p i to the closest point on S. Low values of approx(T i , S) indicate a better local approximation of S by T i .

Hinge area. The tile positions and orientations influence where hinges can be added between neighboring tiles. We measure the capacity of holding a hinge by using the local shape thickness -a notion similar to the shape diameter defined in [START_REF] Shapira | Consistent mesh partitioning and skeletonisation using the shape diameter function[END_REF]]. For a 2D shape, we define the shape thickness at a boundary point p as the diameter of the maximal ball centered at the medial axis and tangential to p (as shown in Figure 9a). Larger values indicate that it is more likely that an hinge can be placed at this location.

Whenever considering adjacent tiles (overlapped or not), we would like them to be translated or oriented such that the potential connection points have large local shape thicknesses. For the nonoverlapping tiles (Figure 9a), the connection points to place an hinge are the two nearest points between the tile contours. As tiles may be overlapping during optimization, we predict the connection points of such cases as the middle point of the curve segment contained in the other tile (Figure 9b). We denote the hinge area for a tile T i as Θ(T i , N i ): it is computed as the sum of the local shape thicknesses for all potential contact points between T i and its neighbors.

Objective function. We finally define the global attraction objective function E at t r act :

E at t r act = α i dist(T i , N i ) + β i approx(T i , S) -Θ(T i , N i ) (3)
E at t r act is a weighted sum of the neighboring distance, local approximation and hinge area terms, where α and β are controlling the tradeoff. We set α = 1.0 and β = 1.5 as we found this achieved a good tradeoff between packing performance and local approximation. β is set larger than α to penalize positions in high-curvature regions.

During the attraction phase, our goal is to find a tile configuration with the lowest value of E at t r act .

4.3.2

Minimization. E at t r act is a complex objective function with a mixture of continuous and combinatorial terms: it cannot be optimized directly by gradient-based methods. In addition, the solution space for E at t r act contains a vast number of possible configurations, which emerge from combinatorial aspects (number of tiles, interlocking of concavities), and its energy landscape is riddled with local minima. Fortunately, many of these local minima will produce configurations that are good enough to be used in practice, and our algorithm is designed to find them efficiently. We rely on a greedy strategy to locally optimize the configuration of each tile. The pseudo-code for minimization is detailed in Algorithm 1. It takes the following steps:

Position update. In algorithm PositionUpdate each tile is translated to a number of candidate positions (including the current position), searching for a displacement producing a lower value of E at t r act . The candidate positions are randomly sampled within the minimal circle centered on the centroid and fully enclosing the tile. We test 400 positions in our implementation. The position with lowest value is used to update the tile in the current iteration. Note that if the user provided a scale control field, the tile is resized before computing E at t r act at each tested position.

In regions of high-curvature it is likely that no good update can be found, as the tile plane misaligns with the surface. When all the candidate positions for a tile T i produce an approximation error approx(T i , S) greater than a threshold τ appr ox , the tile is shrunk at its current position. This favors smaller tiles in high curvature regions. A minimum size constraint prevents tiles from becoming too small. τ appr ox is determined before starting the attraction phase. The approximation errors of all tiles are computed and sorted. τ appr ox is the average error of the top 20%.

Angle update. Algorithm AngleUpdate optimizes the orientation of each tile. Each tile is tested with different orientations while its centroid remains fixed. If an orientation field is provided, we only consider ±5 degrees deviations from the prescribed orientation (10 candidate angles); otherwise, we test all rotations with 1 degree stepping (360 candidate angles). Among the candidate rotation angles, we consider the top n with the lowest value of E at t r act as the candidate orientations (n = 10 in our implementation). Among these, we select the one that provides the best opportunity to insert an hinge, that is the angle that maximizes the minimum of local shape thicknesses between the tile and its neighbors.

Updating sequence. We process tiles in parallel, updating the tile positions in independent sets similarly to the mechanism in [START_REF] Chen | Synthesis of Filigrees for Digital Fabrication[END_REF].

Increasing the surface coverage. The minimization of E at t r act leads to a compact packing of existing tiles, uncovering other parts of the surface. Therefore, after position and orientation optimization we add tiles to uncovered regions in AddMoreTiles. This is done similarly to the initialization. The attraction phase stops if no more tiles can be added.

Algorithm 1 Attraction Input:

Target Surface S; Initial placement of tile set T on S; Input scale field F on S.

Output:

Optimized tile configuration T O that follows F on S.

Repulsion phase

The second phase of the tile packing focuses on resolving overlaps that remain after the attraction phase. In particular, we adaptively scale each tile according to its distance to adjacent tiles, and encourage repulsion among neighboring tiles to evenly distribute tile inter-spacing. A target gutter size (the gap between the nearest two tiles) d is given as input to the algorithm. Our algorithm iterates until there is no overlap between any two tiles and the minimal gutter distance is larger than or equal to d (1 mm in our implementation).

Objective function.

The objective function is designed to push the tiles away from each others. We define a repulsion term between two tiles T i and T j : repulse(T i ,T j ) = min{ min

p i ∈T i sdist(p i ,T j ), min p j ∈T j sdist(p j ,T i )} (4)
where sdist(p i ,T j ) is the signed closest distance from point p i to the point set sampled from T j 's contour:

sdist(p i ,T j ) = -min p j ∈T j ∥Γ(p i ) -Γ(p j )∥ if p i inside T j min p j ∈T j ∥Γ(p i ) -Γ(p j )∥ otherwise (5)
where Γ(p) projects the point onto the common projection plane of T i and T j , as illustrated in Figure 7.

The sign of repulse(T i ,T j ) indicates whether T i and T j overlap with each other (negative values imply an overlap). The absolute value of repulse measures how deeply T i and T j penetrate each other if they overlap, or how far they are separated from each other if they do not.

During the repulsion phase we seek to maximize the value of repulse between each tile T i and its adjacent neighbors A i . These are the neighbors that are spatially close to the current tile and have to be pushed away. Note that this neighborhood is different from the one used during the attraction phase, denoted by N i (Section 4.3.1). A i is defined as A i = {T j |repulse(T i ,T j ) < σ , j i}, that is, the set of tiles closer to T i than a threshold distance σ . This is illustrated in Figure 10 (σ = 6 mm in our implementation).

We then define the final objective function as:

E r epulse = i min T j ∈A i repulse(T i ,T j ) (6)
Maximizing this objective increases the distance between each tile and its adjacent neighbors.

Fig. 10. The adjacent neighborhood (in red) of the black tile are all the tiles surrounding it while being closer than a threshold.

Maximization.

We resort on a similar strategy as described in Section 4.3.2 to maximize E r epulse . Algorithm 3 details the procedure, which executes the following steps: Scale update. To eliminate gaps and overlaps between tiles we adaptively scale them according to the distances to their adjacent neighbors. The pseudo code for ScaleUpdate is given in Algorithm 2. We measure the size of a tile as the diameter of the smallest enclosing circle centered on the centroid.

ComputeDistance returns d i , the smallest value of repulse (Equation 4) between a tile and its adjacent neighbors. Assuming that the current size of T i is s i , we compute in ComputeNewScale the expected size of T i in the next iteration as k i = s i + (d i -d)/2.0, where d is the target gutter distance. We divide (d i -d) by two as T i and its nearest neighbor change in size simultaneously. After the expected size is computed for all tiles, ScaleToExpectedSizes applies the actual scaling operations.

Position and orientation update. We follow a similar strategy as in Algorithm 1 to locally update the positions and orientations of the tiles. However, during each iteration, we seek to search for updates that maximize Equation 6.

Termination. At each iteration we track the minimum distance between closest neighbors d min . If this value is larger than or equal to the target gutter distance d the process terminates -all tiles are far enough from their neighbors. Otherwise, the iterations continue up to a maximum value. The overall process is illustrated in Figure 6e.

While there is no strict guarantee that the process converges, we never observed cases where the maximum number of iterations is reached: after initialization and attraction phase there is only a Algorithm 2 ScaleUpdate Input:

Input tile layout T on S, target interspacing distance d; Output:

Updated tile layout T O with size adaptively scaled. 1: K := ∅; // vector that stores expected size of each tile 2: for each tile T i ∈ T do 3:

A i ← FindAdjNeighbors(T i ); 4: d i ← ComputeDistance(T i , A i ); 5: k i ← ComputeNewScale(T i , d i ); 6: K ← K ∪ {k i };

PATCH EXTRACTION

We now consider the problem of connecting tiles with hinges and snap-fit joints, thus forming patches that can be fabricated flat, folded and assembled to form the final 3D shape. The set of potential hinges are the connections between a tile T i and its adjacent neighbors in A i (see Section 4.4.1 and Figure 10). For two neighboring tiles, the potential location of a hinge is in-between the two closest points along the contours. We use the neighborhood information to create a graph G that captures the tile network. Each tile T i is a node, and one edge is added for each adjacent neighbors T j in A i (see Figure 11b). This graph is very densely connected since the tiles are packed.

This section focuses on two questions: 1) how to segment the tile network into foldable patches (Sections 5.1 and 5.2) and 2) how to assign and optimize the hinge placement so that the final assembled printout is fabricable and possibly stable (Section 5.3).

What we mean by stable is that the tiles are all locked in place with respect to one another. This possibility stems from the fact that taken all together the joints create a dense set of distance constraints between the rigid tiles. These constraints hold the tiles into a stable configuration -a property which is expected for a closed convex polyhedron through Cauchy's rigidity theorem, but may not generally be true (e.g. a flat surface). Our algorithm attempts to preserve this property while trying to reduce the number of joints (Section 5.3.1). Note that if the shape is not stable even when inserting all joints, the final result can still be fabricated but will exhibit unconstrained degrees of freedom.

Extracting foldable patches

Decomposing a surface into developable/flattenable patches is a well-studied field [START_REF] Julius | D-Charts: Quasi-Developable Mesh Segmentation[END_REF][START_REF] Tang | Interactive design of developable surfaces[END_REF][START_REF] Wang | A least-norm approach to flattenable mesh surface processing[END_REF]]. However, conventional methods segment the surface into neardevelopable patches and then deform the patches into fully developable ones. This may introduce distortions and mismatches between the boundaries of adjacent patches. We propose a method better suited to our application, based on the extraction of spanning trees.

It finds a segmentation that does not produce distortions when flattening patches, and that maintains corresponding boundaries between adjacent patches.

In particular, let us consider a case where the tile graph G is a tree -it is easy to observe that it could be flattened/unfolded: each hinge separates the graph in two distinct parts which can rotate freely around the hinge axis with respect to one another. This notion is similar to the foldability of the triangulation dual, where triangles are nodes and edges are hinges [O'Rourke 1998], as illustrated in the inset. The flattening/unfolding might however produce overlaps in the plane.

We build upon this idea and formulate patch extraction as a graph partitioning problem: we seek to partition the graph G into a set of spanning trees such that each tree can be unfolded.

Graph partitioning

We now describe how to partition the graph G (Figure 11b) into a set of spanning trees. There are two fabrication requirements for the graph partitioning problem. First, the size of the unfolded geometry of each patch cannot exceed the extent of the printer bed; second, the unfolding should not produce overlaps between tiles. We propose a method to grow each patch in sequence while considering the properties of its unfolded geometry.

We decorate the graph with edge weights. Each edge weight indicates the capability c(i, j) to insert a hinge between T i and T j at two points p i and p j as described in Section 4.3.2 and Figure 9. c(i, j) is equal to the average local shape thickness. A larger c(i, j) indicates a larger space for inserting a joint.

In practice the hinges require smaller footprints than the snap-fits (see Figure 3). Therefore, we encourage edges with lower c(i, j) to become hinges. We thus seek to extract a minimal spanning tree from G such that the edges with lower c(i, j) belong to the tree.

In the following, whenever selecting an edge to become a hinge (or snap-fit) we first check whether the value of c(i, j) is large enough to host the joint, and ignore the edge otherwise. Note that most edges can host a joint: the packing algorithm specifically optimizes tile orientations to achieve this.

We grow patches with the following process. We start from a tile selected randomly. We then locally grow a subgraph by breadthfirst expansion. At each step of the growth, we extract a minimal spanning tree and verify whether the flattening/unfolding of tree is valid, in which case we continue growing the subgraph. The unfolding is valid as long as it does not produce an overlap between tiles and it fits the printer bed size. If the unfolding is not valid, we return the last valid spanning tree as the next patch, and start extracting a new patch. This is done until all tiles have been covered.

Algorithm 4 PatchGrow Input:

Undirect weighted graph G; Index of starting tile T k ; Size of printing bed: w -width; l -length Output:

A minimal spanning tree that is grown from tile T k . 1: M = ∅; M.add(k); // vector that stores the patch nodes 2: q.push(k); // queue that stores pending nodes 3: F out ; // output spanning tree 4: while !q.empty() do 5: t = q.pop(); q.push(j); F out = F ; end for 17: end while 18: return F out ;

Snap-fits optimization

After patch extraction the set of hinges is fully determined (edges of the spanning trees). However, the number and placement of snap-fit joints is not fixed yet. This affects both the model stability and its printability.

Ideally, we would like to minimize the number of snap-fits: they have to be manually assembled, and using too many is likely to result in non-printable configurations as they cannot be hosted in the tiles. However, each snap-fit introduces a new distance constraint in the final assembly, working towards locking the result in a stable configuration. We thus seek for a proper amount of snap-fit joints so that the final printout is both fabricable and stable.

Note that some tile networks simply cannot be made stable: this depends on the input surface properties (see discussion in the introduction of Section 5). In this section we assume that the tile network is stable if all possibly snap-fit joints are inserted -thus, our objective during the snap-fit joint selection process is to preserve this property. If a surface cannot be made stable, all possible snap-fit joints will be inserted.

Snap-fit edges selection.

A necessary condition for the assembled printout to lock in a stable configuration is to have loops in the connection graph -otherwise any leaf tile would be able to rotate freely along its hinge. In addition, smaller loops increase the set of constraints, further reducing the number of degrees of freedom in the assembly. Based on these simple observations, we optimize the selection of snap-fits to ensure each tile is captured inside constraint loops of small size.

During the algorithm we check the stability of the assembly by using a physics simulation (based on Bullet Physics [START_REF] Coumans | Bullet Physics[END_REF]), verifying whether the tiles remain fixed in space under the effect of gravity and common pinch forces. The lowest point of the object is fixed to the ground as we are not interested in checking for balance. If the largest displacement exceeds 5 mm we consider the model unstable.

Algorithm 5 details the process. The input consists of the graph G and the set of edges that are already selected as hinges. The remaining unselected edges become a pool for selecting snap-fits, see Figure 13a. We filter out any edge in which tiles could not host a snap-fit. We refer to edges that could become snap-fits as available.

The first step in Algorithm 5 is to construct initial loops so that each tile node is captured within a certain cycle. This is implemented in ConnectLeafNodes. We search all leaf nodes (degree 1) and add an additional available edge to them, favoring closest neighbors. As the graph is densely connected, and as the packing is optimized to maximize the possibility to place joints, there is a very high likelihood that such an edge exists. This is illustrated by the green dashed segments in Figure 13b.

After removing leaf nodes, all tiles belong to cycles. The next step is to achieve a denser connectivity. DetectMinimalCycles detects the minimal cycles {C i }. The value of k determines the maximal accepted length for the cycles. If a cycle C i is longer than k, more edges are added to it by searching for available edges connecting pairs of nodes in the cycle, favoring closest neighbors. Thanks to the high degree of connectivity in G many such choices exist. This process, performed by EnhanceLargeCycles, is illustrated in Figures 13c and13d. Finally, TestStability checks whether the model is stable with the current set of snap-fits. If not, the value of k is decreased and another iteration adds more snap-fits. At worst the algorithm terminates when all available snap-fits are added. Our algorithm is capable to adapt the number and placement of snap-fits according Algorithm 5 SelectSnapFits Input:

Graph G; A set of hinge edges E; Snap-fit hinge pool P; Output:

Result stability f stb ; A set of edges F in G that will be realized by snap-fits. 1: k ← 15; f stb ← true; 2: G ′ ← ConnectLeafNodes(E); 3: while true do end if 17: end while return (f stb , F );

to different input external forces. As shown in Figure 12, when larger external forces are imposed, our approach will automatically enhance the structure with more connections. A closeup shows how a flower tile is strengthened.

We provide in the supplemental material an experiment showing the effects of adding different numbers of snap-fit edges. 5.3.2 Final joint assignments. After selecting the hinges and snap-fit joints, there might exist overlaps between their geometries (see Figure 14a). Hinges require space only for one of their ends (the other simply protrudes out of the tile). Snap-fits require space on both ends, one being slightly larger as shown in Figure 3d. This results in a combinatorial problem where we attempt to resolve for all conflicts, while swapping the joint ends assignment.

We proceed in two steps described in Algorithm 6. First, the joint ends are evenly distributed by function EvenlyDistribute. We define the "load" of a tile as the ratio between the number of joint ends it hosts and its area. We distribute the joint ends while attempting to achieve an even load across all tiles. We process the tiles in a priority queue in order of decreasing load value. Each time a tile is visited, the neighboring tiles are checked to assign the joint ends such that the load is kept minimal.

This initial assignment might however create conflicts. To resolve these we process the tiles in a priority queue by decreasing order of number of conflicts. A conflict can be removed in two ways in function ResolveConflicts: the first attempted is to swap the ends of a joint; the second is to slightly move the joint attachment along the tile boundary. These changes can produce a conflict on a neighboring tile, and we therefore add any new conflict to the queue. In rare cases the conflicts cannot be resolved: this is detected whenever neither swapping nor moving the attachment works, or when a new conflict is produced on an already processed tile. In such a case we cancel the edge -a situation that occurred only on one edge in all our experiments (Lamp in Figure 19). Figure 14 shows the effect of joint assignment optimization.

IMPLEMENTATION AND FABRICATION

This section gives details regarding implementation and fabrication.

3D model generation

To generate model for fabrication, we first unfold each patch into a set of 2D contours. The 3D model is constructed via adding a thickness to the 2D pattern. Joints are embedded into the model via boolean operations [START_REF] Jacobson | libigl: A simple C++ geometry processing library[END_REF][START_REF] Wang | LDNI-based Solid Modeling[END_REF]. Snap-fits internal to a patch are printed vertically (Figure 3)which avoids having to consider potential collisions. Other snap-fits (across patches) are printed horizontally whenever possible, such that the part inserted into the tile is hidden from view (this can be seen on the printed patches in the second column of Figure 1).

Optimizations

We achieve better performance by using a coarser sampling. In particular, the attraction phase resorts on a coarse sampling of the tiles (20 samples per tile), followed by a first repulsion phase using a coarse sampling. After this point the packing is almost finalized, and we perform a final repulsion phase using the finest sampling (2 mm spacing). This second repulsion phase terminates quickly as only small overlaps -missed by the coarse pass -are resolved. We provide timings in Section 7.4.

RESULTS

In Section 7.1 we show several results produced with our method. In Section 7.2 we present UI controls provided to help users curstomize their designs. In Section 7.3 we compare our algorithm with different state-of-the-art optimization algorithms. We provide execution timings in Section 7.4. In supplemental material, we discuss convergence rate and surface packing quality.

Fabrication

We test our algorithm on a variety of models, from a simple sphere to a teddy bear with high curvatures. Figure 1 and Figure 15 show our fabrication results without control field and their corresponding simulations. Tiles of various shapes are used to decorate the base surfaces, including round convex shapes (e.g. sphere and egg) and concave contours with thin features (e.g. the bird and fish pattern). We fabricate all the results using a filament printer (Flash Forge Creator Pro) with ABS filament. All of the assembled models correspond to their simulation and approximate the target surface well. Some low amount of distortion can be seen, which is due to necessary tolerances when fabricating pre-assembled joints.

Our fabrication results have a variety of uses, for instance acting as lamp shades, vase decor (Figure 19) or even as a bag that can carry light objects (Figure 1). On the bag, two ring tiles are manually placed and fixed during optimization in order to attach the handles.

Table 1 summarizes the statistics for each fabricated result: size of assembled printout, number of tiles and the number of fabricated patches. The number of patches depends on both the model size and the surface complexity. Models with high curvatures require more patches (e.g. teddy bear). Note that Handbag1, Hangbag2, Lamp1 and Lamp2 refer respectively to the results in Figure 1, Figure 16e, Figure 19 and Figure 16f. Lamp1 is also visible in the supplemental material.

UI Control

We provide several controls to help users stylize their designs: orientation and scale as well as using different tiles in different regions. 7.2.1 Scale and orientation fields. Our method allows the user to edit both the size and orientation of the tiles. Figure 16 demonstrates results in which the tiles are adapted to an input control field, which consists of a scaling field and an orientation field, both specified by the user. In the figure the scale field is color coded, and ranges from 0.5 to 1.0. The streamlines in Figure 16a and 16b reveal the orientation fields used on the two results. The user edits the orientation field by sketching lines on the surface. A smooth orientation field is generated by treating the sketch lines as constraints, using the implementation provided by [START_REF] Diamanti | Designing N -PolyVector Fields with Complex Polynomials[END_REF]]. The user can paint desired scales directly onto the base surface using a brush tool.

As can be seen in the simulation and printed results, the tiles follow both the sizing and orientation fields while the result is a dense, fabricable packing. 7.2.2 Global tile class control. Our approach lets the user specify the ratios of different tile classes that appear in the result. Figure 17 shows a case where the ratio is changed to achieve different results. This control is mainly achieved during the initialization step, when the tile distribution is generated. We employ the strategy described in [START_REF] Wei | Multi-class blue noise sampling[END_REF]] for sampling from different classes.

7.2.3

Local tile class control. We let the user control the choice of tiles locally, as illustrated in Figure 18. A brush tool allows the user to paint the desired tile class id directly onto the surface. Tiles can only appear in a region with a same class id. This allows to customize the tile decors even further, as shown in Figure 18.

Comparison with gradient-free methods

We compare our approach to state of the art gradient-free optimization algorithms in Figure 20. In particular, we test two global optimization algorithms (ISRES [START_REF] Runarsson | Search biases in constrained evolutionary optimization[END_REF] and MLSL [Rinnooy Kan and Timmer 1987]) and two local optimization approaches (COBYLA [START_REF] Powell | A direct search optimization method that models the objective and constraint functions by linear interpolation[END_REF]] and SBPLX [START_REF] Rowan | Functional stability analysis of numerical algorithms[END_REF]). The results of these algorithms are produced using the implementations of the NLopt library [START_REF] Johnson | The NLopt nonlinear-optimization package[END_REF]]. We use the same initialization (Figure 20a) and the same objective functions for all tested algorithms.

As seen in Figure 20, these generic optimizers perform poorly in our case (Figure 20b and Figure 20c). As none of the optimizers reached termination (i.e. a packing where the spacing constraint is achieved), we stopped them after 2 hours of running time. The local optimization methods perform better than their global counterparts (see Figure 20d and Figure 20e) since the initial tile layout provides a good starting point. However, without an effective search strategy, it is hard for these methods to find valid solutions and there remain many unresolved tile overlaps as well as uncovered regions. Our algorithm achieves a much better result thanks to dedicated heuristics. We provide more details on the evolution of the objective functions during optimization in supplemental material.

Timings

Table 2 summarizes the timing of our results. All the results are produced on computer with an Intel i7-4770 CPU and 16GB RAM. The tile packing dominates the runtime. The timing is mostly influenced by the number of tiles and the complexity of the target surface. The printing time is mainly related to the surface area of target surface.

For instance, the vase took around 7 more hours to print than the bear due to its larger surface.

LIMITATIONS AND CONCLUSIONS

Our approach lets anyone fabricate visually interesting objects by decorating a surface with tiles. This mimics a popular way of improving a surface appearance by applying stickers and decals. 15 and Figure 16). Statistics (from top to bottom) include size of assembled printout, number of tiles packed and number of patches used for assembly. The size is represented as (l enдt h, widt h, heiдht ), all measured in centimeters. 37.5 37.8 36.9 t asm 9.9 10.6 10.1

Table 2. Timing of fabricated results (Figure 15 and Figure 16). For each result, we show the timing of tile packing t pac k , patch extraction t pat ch , printing t pr int and assembling t asm . All timings are listed in minutes expect t pr int which is in hours.

than synthesizing a complex 3D model difficult to print, our technique is designed to allow for efficient fabrication: the final surface is assembled from articulated patches that print flat, without support. This makes them fabricable on home filament printers, and easy to pack which maximizes utilization of powder-based printers, and reduces shipment costs. Due to the fabrication constraints, our method cannot handle tiles which are thin everywhere (as shown in the inset). These do not offer sufficient space for inserting joints. Our method tends to ignore small scale surface details, e.g. the scales of a dragon, as our tiles are relatively large to allow for fabrication.

While the assembly step is left to the user -and it does take some time -we find the assembly to be an enjoyable process, that gives the user a better sense of ownership on the part she customized. However, it would be interesting, as future work, to attempt to further simplify this stage. Also, the main structural fragilities are the articulated hinges. To obtain stronger objects it would be interesting to investigate whether we could print solid connectors and deform them with heat, as in [START_REF] Sageman-Furnas | Meltables: fabrication of complex 3d curves by melting[END_REF]. As the scale of input surface grows, the number of patches increases 175:14 • Weikai Chen, Yuexin Ma, Sylvain Lefebvre, Shiqing Xin, Jonàs Martínez, and Wenping Wang -since the printer bed size limits the maximal extent of a patch. Tolerance required in the fabrication of joints may accumulate and increasingly lead to larger distortion in the final assembly. We will also explore the optimization of joint length for reducing global deformation. Finally, it would be interesting to study whether a final assembly could be made stable by gluing or constraining the motion of a small subset of hinges. Using our technique, users without prior expertise can model objects that fully exploit advanced possibilities of 3D printing: embedding pre-assembled hinges and snap-fit joints in a model, as well as producing freeform, unusual geometries. We hope our approach will find a wide audience, and we will make the application available for everyone to enjoy.

Fig. 2 .

 2 Fig. 2. Directly printing tile decors on a filament printer requires support. (a) Tree support structure. Several tiles are incorrectly printed as highlighted within the red rectangles. (b) Standard, downward extrusion support structure. (c) Inner view of (b). A large amount of support is required, and it is not easily accessible for removal.

Fig. 4 .

 4 Fig. 3. (a,b) Hinge joint. Note that (b) is only for showing the inner structure of hinge joint as it is always printed attached.(c,d) Snap-fit joint. Note that for those snap-fit joints that are internal to a patch, their bar will be printed vertically but would be folded down to connect adjacent tile during assembly.

Fig. 5 .

 5 Fig. 5. The tiles are represented by samples along their contour.

Fig. 6 .

 6 Fig. 6. Tile packing algorithm. (a) Initialization. (b-d) Attraction Phase. During the attraction phase, we encourage each tile to stay close to neighbors while maintaining near-uniform overlaps (b). This strategy makes room for adding new tiles so as to increase surface coverage (c). In this case, four new tiles (highlighted with yellow) are added in now empty regions. (d) We iterate until no more tiles can be added. (d) Repulsion phase. We encourage each tile to repel its neighbors to resolve any remaining overlap. This is achieved via adaptively scaling the tile sizes and optimizing both the tile positions and orientations.

Fig. 7 .

 7 Fig. 7. Common projection plane of T i and T j (side view).

Fig. 8 .

 8 Fig. 8. Samples for the neighborhood distance (green dots).

Fig. 9 .

 9 Fig. 9. Potential joint positions. (a) Local shape thickness. The medial axis of each shape is outlined by a dashed line. The medial balls at p 1 and p 2 are drawn in blue. (b) In case of overlap p 1 and p 2 are the midpoints of the orange and green segment, respectively.

  stop 6: return T O = T ;

  7: end for T O ← ScaleToExpectedSizes(T , K); 8: return T O ; limited amount of overlap, and these can be resolved without having to apply excessive scaling to the tiles. Algorithm 3 Repulsion Input: Target Surface S; Input tile distribution T on S; Target interspacing distance d; Input magnitude field F on S. Output: Optimized tile configuration T O that follows F on S. until d min ≥ d or maximum iterations reached 7: return T O = T ;

  Fig. 11. Tile network and its corresponding graph. Note that (b) only shows the graph for the tiles that are visible in (a). The red edges in (b) form a spanning tree of the graph.

  G ′ ) ← EnhanceLargeCycles({C i }, k, P);

  Fig. 12. Results of inputting different external forces. 5N and 15N pinching forces are imposed in (a) and (b), respectively. The forces are imposed on both sides of bag symmetrically. The orange dot dictates the pressure point on the front side while the blue arrow shows the force direction. As the joints are designed to be embedded in an inconspicuous way, we highlight the additional joints resulted from larger forces in the red rectangles in (b). A closeup shows how a flower tile is strengthened.

  Fig. 13. Adding snap-fit joints. The left column illustrates the graph, the right column shows the physical simulation as more snap-fits are added.

Fig. 14 .

 14 Fig. 14. Effect of joint assignment optimization.

Fig. 15 .

 15 Fig. 15. From left to right: input tiles, target surfaces, simulated results with each patch color coded and fabricated results (two views).

Fig. 16 .

 16 Fig. 16. Results of control field editing. The user can edit both the size and orientation of tiles.

Fig. 17 .Fig. 18 .

 1718 Fig. 17. Result of varying the percentage of each tile class. (a) and (b) shows the input tile set (from top to bottom: leaf, flower and clover) and the underlying scaling field. (c) is a result where each class appears equally, while in (d) leaves appears with 70% probability and in (e) clovers appear with 70% probability.

Fig. 19 .

 19 Fig. 19. Fabrication results used for home decor.

Fig. 20 .

 20 Fig. 20. Comparisons with other generic derivative-free optimization algorithms. We use the same tile initialization (a) as the input. (b) ISRES and (c) MLSL are global-optimization algorithms while (d) COBYLA and (e) SBPLX are algorithms for local optimization.

Table 1 .

 1 Statistics of fabricated results (Figure

	Rather

ACM Transactions on Graphics, Vol. 36, No. 6, Article 175. Publication date: November 2017.

ACM Transactions Graphics, Vol. 36, No. 6, Article 175. Publication date: November 2017.

ACKNOWLEDGMENT

We would like to thank Lei Chu for photographing the printouts and anonymous reviewers for their insightful comments. This work is supported by Hong Kong RGC (GRF 17208214), ERC grant Shape-Forge (StG-2012-307877) and NSFC (61772016).