Abdelhamid Zemirline
email: abdelhamid.zemirline@enst-bretagne.fr

Laurent Lecornu
email: laurent.lecornu@enst-bretagne.fr

Basel Solaiman
email: basel.solaiman@enst-bretagne.fr

Ahmed Ech-Cherif

An efficient association rule mining algorithm for classification

published or not. The documents may come

Introduction

Association Rule Mining [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] is the most popular data mining task due to its numerous applications and the efficiency of the APRIORI algorithm which produces interesting relationships among items of large databases. Associative classification [START_REF] Liu | Integrating classification and association rule mining[END_REF], [START_REF] Li | Cmar: Accurate and efficient classification based on multiple class-association rules[END_REF] attempts to solve classical classification problems using association rule mining. Successful algorithms in this category including the well known C4.5 predict the class label for novel (unseen) examples .

In this paper, we propose a new Association Rule Mining algorithm for Classification (ARMC) based on the extraction of both common and exception rules, specific to each class. ARMC uses a fuzzy method to automatically select the items that generate the rules and does not require the user to provide thresholds.

ARMC proceeds by combining on one hand, the weighted voting and the decision list algorithms. On the other hand, a fuzzy method is used in order to distinguish the important rules from the less important ones for each class.

The remainder of this paper is structured as follows. In the next section the basic terminology used throughout the paper is introduced. Related research on associative classification is surveyed in section 3. The ARMC algorithm is presented in section 4. Experimental results are given in section 5. We conclude the study in section 6.

Preliminaries

Association Rule Mining

Let B be a database consisting of one table over n items I = {a 1 , a 2 • • • , a n } whose values are nominal and containing k instances.

A database instance d is said to satisfy an item set

X ⊆ {a 1 , a 2 , • • • a n } if X ⊆ d.
An association rule is an implication X ⇒ Y where X, Y ⊆ I, Y = ∅ and X ∩ Y = ∅.

The support of an item set X is the number of database instances d which satisfy X: sup(X) = |{t∈B| X⊆t}| |B| . The confidence of an association rule is a percentage value that shows how frequently the consequent part occurs among all the groups containing the rule antecedent part : conf (X → Y ) = |{t∈B|X∪Y ⊆t}| |{t∈B|X⊆t}| .

Association Rules for Classification

Given a relational table B containing N cases (training examples) belonging to C classes, each one is described by an itemset and let I be the set of all items of B. Classical classification methods seek a rule or a hypothesis that predicts the label of an unseen example. The class association rule is an implementation of the form X → c, where X ⊆ I, and c ∈ C.

The objectives are to generate the complete set of class association rules that satisfy the minimum support as well as the minimum confidence (minConf ) constraints and to build a classifier from the class association rule set.

The classifier is applied to classify examples. To this aim, one combines the prediction of all rules which satify the exemple: if there is only one rule, the consequent of this rule is taken to be the predicted class for the example; if there is no rule satisfying the example, then a default class is taken to be the predicted class; and if there are multiple rules satisfying the example, then their predictions must be combined. Various strategies for realizing this are discussed in section §3.3.

Methodology

The associative classification algorithm can be divided into two fundamental parts: association rule mining and classification. The mining of association rules is a typical data mining task that works in an unsupervised manner. A major advantage of association rules is that they are theoretically capable of revealing all interesting relationships in a database.

Current Approaches for Discovering Frequent Items and Rule Generation

Many approaches for frequent items discovery and rule generation have been proposed. In this section, we present some paradigms used in the most important association rules and associative classification methods: type algorithms Apriori Agrawal et al. [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] discover large frequent itemsets, by making multiple passes over the dataset. In the first pass, the support of individual are counted and then the frequent ones are selected. In each subsequent pass, the algorithm starts with a seed set of frequent items found in the previous pass. This process continues until no new frequent items are found. This algorithm needs to scan several times the dataset in order to produce the frequent itemsets. The CMAR algorithm [START_REF] Li | Cmar: Accurate and efficient classification based on multiple class-association rules[END_REF] adopts some properties of the FP-growth method [START_REF] Han | Freespan: frequent pattern-projected sequential pattern mining[END_REF]. FP-growth is a frequent pattern mining algorithm which is faster than conventional Apriori method. Whose advantages are: it constructs a highly compact Frequent-Pattern-Tree, which is smaller than dataset and that avoids to scan the dataset in the subsequent mining process. Also, in contrary to FOIL and CPAR methods, it avoids costly candidate generation.

The MMAC [START_REF] Thabtah | Mmac: A new multi-class, multi-label associative classification approach[END_REF], [START_REF] Thabtah | Multiple labels associative classification[END_REF] algorithms use the technique based on intersection methods [START_REF] Zaki | New algorithms for fast discovery of association rules[END_REF]. They scan the dataset once to count the support of individual items and determine those having minimum support. They store items along with their location (rowIds) inside arrays. Then, by intersecting the rowIds of the frequent items discovered so far, can easily obtained the remaining frequent items that involve more than one attribute.

Current Approaches for Extracting Exception Rules

After performing data mining tasks as using association rule methods [START_REF] Hussain | Exception rule mining with a relative interestingness measure[END_REF], which usually terminate with a large set of rules, there is a need to find some interesting rules that can be used by the decision maker. In [START_REF] Hussain | Exception rule mining with a relative interestingness measure[END_REF], [START_REF] Liu | Efficient search of reliable exceptions[END_REF], exception rules are defined as the rules that contradict the common belief. They play an important role in making critical decision. The exception rules usually have a small cardinality as a set, and they are not known or omitted.

There are some intuitive ways [START_REF] Hussain | Exception rule mining with a relative interestingness measure[END_REF], [START_REF] Liu | Efficient search of reliable exceptions[END_REF] such as multi-support or generate-andremove. For discovering exception rules which generate the weak patterns using the traditional data mining techniques. For example, in order to find exception rules, we can introduce two support thresholds [s 1 , s 2 ] as delimiter and we search the itemsets whose support values fall into the range [s 1 , s 2 ].

Generate-and-remove is straightforward method where the rules are generated from the training data T by an induction algorithm as follows: remove T from T that is covered by R; then generate rules R on T -T ; repeat the process until no data are left. This procedure can find many weak patterns.

Current Approaches to Classification

In most associative classification methods such as CBA, MMAC, ... we use the classification approach which is called decision list algorithm. This approach takes into account just one rule in order to classify an instance. Therefore the set of class association rules is stored in a list data structure whose first rule covering the instance to be classified is used for prediction.

In CBA [START_REF] Liu | Integrating classification and association rule mining[END_REF], the class association rules are stored as follows: given the rules, r a and r b , r a precedes r b if the confidence of r a is greater than that of r b , or if their confidences are identical, but the support of r a is greater than that of r b , or both the confidences and support of r a and r b are the same but r a is generated earlier than r b .

Any associative classification using this approach, has approximately these same definition rules. The resulting classifier has the form: < r 1 , r 2 , ..., r n , def ault class > where r i precedes r i+1 . For classifying a new case, the first rule that satisfies the case classifies it. If no rule applies to the case, it takes the default class.

Another approach called the weighted vote algorithm. Uses a set of the best rules of each class for prediction, according to the following procedure: (1) select all the rules whose bodies are satisfied by the instance; (2) from the rules selected in step (1), select the best rules for each class; and (3) compare the measure of the combined effect of selected rules of each class and choose the class with the highest measure.

There are many possible ways to measure the combined effect of a group of rules [START_REF] Yin | CPAR: Classification based on predictive association rules[END_REF], [START_REF] Li | Cmar: Accurate and efficient classification based on multiple class-association rules[END_REF]. For example, one can compute the average of the confidence values of a group of rules or expected accuracy [START_REF] Yin | CPAR: Classification based on predictive association rules[END_REF] as the predicted class. Another alternative is to use the strongest rule as a representative of the predicted class [START_REF] Li | Cmar: Accurate and efficient classification based on multiple class-association rules[END_REF]. In other words, the rule with highest χ 2 value is selected. However, this method is based on a single rule for making predictions.

ARMC Algorithm

We present a new algorithm for associative classification, based on multi-rule classification. Our algorithm extracts rules from data subset instead of the whole dataset. Each class of the dataset has its instance subset which consists of the cases of the same class. In this approach, exception rules are discovered by all.

Item Discovery and Rule Generation

Our approach generates local rules (i.e., the rules are generated from a subset of dataset that is composed of the instances of the same class label for freqent items discovery and rule generation tasks, and employs a technique).

Based on the intersection method [START_REF] Zaki | New algorithms for fast discovery of association rules[END_REF] in order to scan the dataset once and to compute confidence value of rules from confidence value of frequent single items.

It clusters the training data set T into several subsets. Each subset holds the instances of the same class. We scan each subset once in order to count the occurrence of single items. Each single item has a number of occurences for each class. For a given class, the whole number of items is used in order to build a memberships function to the given class. These memberships sort the single items in two subsets: one rare items subset and another frequent items one. We use fuzzy sets [START_REF] Zadeh | The concept of a linguistic variable and its application to approximate reasoning -ii[END_REF] subsets in order to extract the frequent items inherent in a given class.

The support threshold value for some methods is pre-fixed, in order to select the items iteration numbers exceeding this support threshold. Although this procedure is widely used by most methods it has some disadvantages as:

-If the whole number of item iterations are higher or equal than the threshold, then no frequent items are selected. -Some interesting items are not selected as frequent items though their iteration numbers are close to the threshold.

In order to build membership functions for determination of the frequent items, we use the method introduced in [START_REF] Zadeh | The concept of a linguistic variable and its application to approximate reasoning -ii[END_REF]. This method enables the interpretation of the linguistic variable frequency for the term set {rare, f requent}. Each term is characterized by a fuzzy sets in a universe of frequency values of items for a specific class label.

Before presenting how to build these membership functions for class c i , some notations have to be specified: use of subsets of a database instead of the entire dataset requires the adaptation of certain functions such as the support function which calculates the frequency of appearances of an itemset in the whole data base. The support function is adapted to calculate the support of an itemset in a subset of data and named supportLocal :

suppLocal ci (X → c i ) = |{t ∈ B ci | X ⊆ t}| |B ci |
where : B ci is a set of instances of the class c i .

To define these membership functions, we denote the linguistic variable which is characterized by [START_REF] Zadeh | The concept of a linguistic variable and its application to approximate reasoning -ii[END_REF]: (x, T (x), U) where x is the linguistic variable. In our application x is equal to the linguistic variable frequency. -T (x) is the set of terms associated with the linguistic value, in which the frequency is represented according to the following set {Never, Rare, Frequent, Always}. -U is the universe of discourse and U = {s ∈ I| suppLocal ci (s → c i )}.

The terms of T (x) are characterized by fuzzy subsets defined by the following membership functions [START_REF] Zadeh | The concept of a linguistic variable and its application to approximate reasoning -ii[END_REF]: -K: is the set of centroids obtained by the K-means algorithm which is applied to U for K = {0, s rare , s freq , 1} (freq = frequent). -μ ci,rare : corresponds to the membership function in the linguistic term rare.

It is built from a set of instance frequencies which belong to the class c i .

μ ci,rare (s) = ⎧ ⎨ ⎩ 1 i f s ≤ s rare 1 -s-srare
s freq -srare if s rare < s ≤ s freq 0 o t h e r w i s e .

μ ci,f req : corresponds to the membership function in the linguistic term f requent. It is built from a set of frequency values of instances which belong to label class c i .

μ ci,f req (s) = ⎧ ⎨ ⎩ 0 i f s ≤ s rare 1 - s-s freq s freq -srare if s rare < s ≤ s freq 1
o t h e r w i s e .

where : s = suppLocal ci (X → c i ) such as X ∈ I

These membership functions are able to define fuzzy subset of single items. The frequent single items are all the items in which the frequency value of membership degree of the term frequent is higher than that of term rare, i.e. {s ∈ I| μ ci,f req (suppLocal ci (s → ci)) > μ ci,rare (suppLocal ci (s → c i ))}. Therefore two subjective thresholds (first support t ci 1 and second support t ci 2 ) can be computed (Figre 1). The first support t ci 1 is the value that corresponds to the intersection of μ ci,f req and μ ci,rare . The second support t ci 2 is the centroid s rare (t ci 2 = s rare ).

1 According to this method, we define subjective thresholds for a specific class by selecting. All the single items whose local support value exceeds the first threshold. We call these items frequent single items. Then, to produce the rules from these items, the local support value is calculated, and the rules whose local support is greater than the first threshold t ci 1 are considered as common rules. The others are considered as exception rules if their local support exceeds the second threshold t ci 2 and they are stored respectively in common rule set and exception set of this class.

1 µ c i ,f req µ c i ,rare SppLocal ci s rare = t c i 2 t c i
In order to illustrate the advantages of the combination of these approaches to find the exception rules, we present an example: the training dataset of Table 2, represents a set of the instances whose label class is A or B. From this table, we apply our method to produce the rules. In table 3 and 3, there are the rules extracted from the instances whose class label is A and B respectively. In these tables, the rules are grouped by the way either by the first or by the second threshold or by the generate-and-remove.

Double local support thresholds are computed by the method defined above. For the instances whose class label is A, the results obtained are t A 1 = 0.29 and to t A 2 = 0.17. Using the first threshold t A 1 , we select the set of the single frequent item {x 1 , x 4 }, with which, our method produces three rules: x 1 → A, x 1 x 4 → A and x 4 → A. The last rule is pruned because its included in the second rule and the both of them cover the same instances. Using the second threshold t A 2 , the items x 2 and x 11 are added to the set of the frequent single item, which are combined to generate many rules, but only rules x 1 x 11 → A and x 2 → A are saved. The other rules are pruned as: x 2 x 4 → A, x 2 x 11 → A because they do not cover any instances. The rule x 3 x 8 x 13 → A is found by the generate-and-remove approach.

For class B, results of threshold computing gives t B 1 = 0.307 and t B 2 = 0.23 respectively. The items x 1 , x 2 , x 6 , and x 12 are the frequent single items. The rules generated from these items are those having the Id 1, 2, 3, and 4 of Table 4. Other rules are generated but they are pruned because, either they do not cover any instances or they are included in other rules. the second set of frequent single items are {x 10 , x 4 } and the rules generated by adding these new frequent This approach is quite effective in terms of runtime and storage because it does not rely on the traditional Apriori approach [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF] of discovering frequent items requiring multiple scans. Moreover, it generates more rules than the traditional method and therefore avoids missing important ones.

Classification

Our approache builds a global model for classification by combining the two approaches presented above (3.3): the weighted vote algorithm and the decision list algorithm. Firstly, for each class c i , we store a set of rules R ci in two sets: the set of the common rules to class c i and the set of the exception rules to the class c i .

Given R a rule set containing the rules for each class, R is composed of common and exception rules, and given also the instance, we use the best rules of each class for prediction, with the following procedure:

(1) Select all the rules from R whose bodies are satisfied by the instance;

(2) Compare the average local support value of the common rules of each class and choose the class with the highest average as the predicted class. If there are no the common rules for a specific class, the local suport of the best rule from the specific class is selected.

The following function is used for selecting and combining rules as discussed above:

(c) Generation of exception rules :

For each In phase 1 of our algorithm, double local support threshold is applied, then the generate-and-remove is applied to discover the remaining rules in order to cover all the training instance by rules. This combination enables us to find more rules than the traditional methods and also to find some rules that can be to be generated by either generate-and-remove approach alone or by double support threshold approach alone.

X 1 ⊂ S f and X 2 ⊂ S r R ci ← < X 1 ∪ X 2 → c i > if suppLocal ci (X 1 ∪ X 2 → c i ) ≥ t ci 2 For each X 1 ⊂ S r and X 2 ⊂ S r R ci ← < X 1 ∪ X 2 → c i > and suppLocal ci (X 1 ∪ X 2 → c i ) ≥ t ci 2 (d) Purning R ci : Remove X → c i if B ci (X → c i ) ⊆ B ci (X → c i ) and X ⊆ X (e) B ci ← B ci -B ci (R ci ) (f) Repeat

Evaluation

We have evaluated the accuracy, efficiency and scalability of our algorithm. In this section, we report on our experimental results by comparing our algorithm with three popular classification techniques namely RIPPER [START_REF] Cohen | Fast effective rule induction[END_REF], PART [START_REF] Frank | Generating accurate rule sets without global optimisation[END_REF] and CBA [START_REF] Liu | Integrating classification and association rule mining[END_REF] in order to evaluate the predictive power of the proposed method. As in [START_REF] Thabtah | Mmac: A new multi-class, multi-label associative classification approach[END_REF], datasets from UCI Machine Learning Repository [START_REF] Merz | UCI repository of machine learning databases[END_REF] are used. 10-fold cross validation is used for every dataset. In our experiments, confidence threshold was set to 3, the datasets selected from [START_REF] Merz | UCI repository of machine learning databases[END_REF] were reduced by ignoring their integer and/or real attributes. The accuracy of our algorithm has been computed using the top label evaluation measure. We obtain better results with ARMC.

Table 5 shows the classification average accuracy of the classifiers extracted by RIPPER, PART, CBA, and ARMC on the 26 benchmark problems. Our algorithm outperforms the rule-learning methods in terms of accuracy rate, and the won loss tied records of ARMC against RIPPER, PART and CBA are 16 10 0, 15 10 1 and 18 8 0, respectively. Table 6 compares the number of classification rules discovred by RIPPER, PART, CBA and ARMC algorithms. We can see that on average, ARMC finds many more rules than RIPPER, PART and CBA. The reason why ARMC finds more rules is that it mines rules which cover all the instances of a dataset by the generate and remove procedure.

Table 7 shows the classification average accuracy of the different classifiers approach on the 26 benchmark problems. The ARMC-1 denotes the result of the weighted vote algorithm when sed by our method. The ARMC-Multi denotes the result of the decision list algorithm when used by our method.

We conclude that the combination of two approaches ( the weighted vote algorithm and the decision list algorithm) outperforms the weighted vote algorithm and the decision list algorithm.

Conclusion

A new approach for classification rules has been proposed having different features: (1) Covering all training instances and leaving no unclassified instances (2) requiring only one pass to discover rules (3) using a novel approach for building a classification model. All these features are not offered by the traditional associative classification methods. The first series of experiments on databases in UCI machine learning repository showed that ARMC is robust and highly effective for various classification tasks.

Fig. 1 .

 1 Fig. 1. Membership functions (μ c i ,f req , μc i ,rare) and the thresholds (t1, t2)

  (a), (c), (d) and (e) until B ci = ∅ 2. Build the classifier.

Table 1 .

 1 An example of training dataset

	Id Set of items Class	Id Set of items Class
	1 x1, x4, x9	A	8 x1, x4, x9	B
	2 x1, x4, x10	A	9 x1, x4, x9	B
	3 x1, x4, x11	A	10 x1, x5, x11	B
	4 x1, x5, x11	A	11 x2, x6, x12	B
	5 x2, x6, x12	A	12 x2, x6, x10	B
	6 x2, x7, x13	A	13 x2, x6, x12	B
	7 x3, x8, x14	A	14 x2, x7, x12	B
			15 x3, x8, x13	B

Table 2 .

 2 SupportLocals calculated from training dataset of Table2

	Item Support suppLocalA suppLocalB
	x1 7/15	4/7	3/8
	x2 6/15	2/7	4/8
	x3 2/15	1/7	1/8
	x4 5/15	3/7	2/8
	x5 3/15	1/7	2/8
	x6 3/15	1/7	2/8
	x7 2/15	1/7	1/8
	x8 2/15	1/7	1/8
	x9 2/15	1/7	1/8
	x10 3/15	1/7	2/8
	x11 3/15	2/7	1/8
	x12 4/15	1/7	3/8
	x13 2/15	1/7	1/8
	x14 1/15	1/7	0

Table 3 .

 3 Rules found in training subset instances of class A

	Approach	Id Rule	Sup SupL
	1 st threshold	1 x1 → A	2/7 4/7
	t A 1 2 nd threshold	2 x1x4 → A 3 x2 → A	3/14 3/7 1/7 2/7
	t B 2	4 x1x11 → A 1/7 2/7
	gen-and-rem 5 x3x8x14 → A 1/14 1/7

Table 4 .

 4 Rules found in training subset instances of class Bitems are the rules with Id 5, 7, 8 of Table4. The rule x 3 x 8 x 13 → B is found by the generate-and-remove approach.

	Approach	Id Rule	Sup SupL
		1 x2 → B	4/15 1/2
	1 st threshold	2 x1 → B	3/15 3/8
	t B 1	3 x2x6 → B	3/15 3/8
		4 x2x7 → B	3/8
	2 nd threshold t B 2	5 x1x4 → B 6 x2x6x12 → B 2/15 1/4 1/3 1/4 7 x10 → B 2/15 1/4
	gen-and-rem 8 x3x8x13 → B 1/15 1/8

Table 5 .

 5 Classification accuracy average of PART, RIPPER and ARMC Algorithm RIPPER PART CBA ARMC Average 83.519 83.923 83.242 85.367

Table 6 .

 6 Rule number Average of PART, RIPPER and ARMC

	Algorithm RIPPER PART CBA ARMC
	Average	6.29	18.58 44.71 47.79

Table 7 .

 7 Classification average accuracy of ARMC-1, ARMC-Multi, ARMC

	Approach ARMC-1 ARMC-Multi ARMC
	Average	84.91	82.1	85.36

where:

-R ci,com (e) : set of common rules which cover the instance e from class c i .

-R ci,¬com (e) : set of exception rules which cover the instance e from class c i .

We use multiple rules in prediction for the following reasons: the accurate rules cannot be precisely estimated and we cannot expect that any single rule can perfectly predict the class label of every example satisfying its body. Moreover, we use the best rule instead of using all of them because there are different number of rules for different classes and we do not want to use low rank rules in prediction when there are already enough rules to make a prediction.

ARMC Algorithm

Our algorithm proceeds in two phases: The first phase generates the common and exception rules. The last one builds the classifier.

Before presenting this algorithm, some notations have to be specified:

-B ci is the set of instances of the class c i .

-R ci is the set of rules extracted from B ci .

-S f is the frequent item set.

-S r is the rare item set.

-B ci (r) is set of istances covered by the rule r.

-B ci (R ci ) : is the set of instances covered by the set of rules R ci .

ARMC Algorithm

Input: Database B. Output: The rule set for each class (R ci ).

1. Scan the database B to group the instances according to class labels.

For each set B ci : (a) Generation of S f and S r from B ci (b) Generation of common rules : For each X 1 ⊂ S f and


Thomas Buffet

Damien Rohmer

Marie-Paule Cani

Untangling Layered Garments: An Implicit Approach

The efficient animation of layers of garments is a challenging task, as it requires handling collisions and contacts between multiple thin surfaces, which may be difficult to untangle once inter-penetrations have occurred. We propose a novel geometric approach, based on implicit surfaces, to robustly handle such situations. At each animation step, our method converts the possibly intersecting garment surfaces to an implicit representation. They are then combined using a new binary operator that guarantees, as output, collision free states of the surfaces. In addition to a precise modeling of contact situations, our method enables to model the relative influence of each cloth layer, based on their relative stiffnesses and thicknesses.

Introduction

Figure 1: Our untangling system based on implicit surface modeling is able to avoid intersections of the garment layers on these static frames of a walking sequence animation (left part: input; right part: our output).

Efficient clothes animation has been a prevalent domain in graphics and has received a lot of attention for many years due to its wide use, for instance, in animation movies, or in video-games. While wearing multiple layers of cloths is common is the real world, 3D virtual characters from industrial production are often limited to a single layer of cloth on top of their skin. Indeed, handling mutual contact between several thin layers of cloth surfaces is a complex problem. In addition of collision avoidance between garments, the relative thickness of the different layers have an impact on the resulting geometry and behavior of the most visible one. We propose in this work a robust approach, based on implicit modeling, to handle contact between cloth in a static step. More precisely, we consider as input a set of cloth layers exhibiting arbitrary intersections, and compute as output the corresponding garment layers free of intersections. Our approach not only avoid intersection between the resulting surfaces, but also guarantees that garment parts previously in intersections are in precise contact, while taking into account the relative stiffness of each layer in the resulting shape.

Most models of cloth animation separate the detection of collisions from their responses. Early works ( [BFA02]) were principally focus on surface/volume collision, in order to handle collision between a garment and a body, but cannot be used for cloth layers. Handling collision between surfaces, also known as "Untangling" in the case of garment, has been tackled in several articles such as [SSIF09] where the history of the clothes throughout the simulation is used, or as [START_REF] Volino | Resolving surface collisions through intersection contour minimization[END_REF] and [YNX15] where the intersections contour is considered. [LGA15] used ray tracing heavily paralelized on GPU. [START_REF] Müller | Air meshes for robust collision handling[END_REF] unifies the detection and the handling of collision during the simulation in a very efficient way, but require as input a legal collision-free state. All these methods are very well suited to avoid collision between surfaces, but do not intrinsically take into account the mutual interaction between cloth layers. Our approach relies on the use of implicit surfaces to model the layers of cloth, and bring a robust solution to avoid intersection between different layers. As explained in [BW97], implicit surface, defined as the iso-value of a field function, intrinsically convey a well defined interior and exterior domain in space associated with the surface. Therefore modeling surface with volumetric field enable a robust and precise handling of collision and modeling of the contact ( [Can] , [VGB * 14]).

Method

Let us consider an input provided as a set of two 3D meshes representing two layers of cloth supposed to be in a static equilibrium. This input can typically be computed using a physically-based simulation, or a geometrical skinning. Each mesh is converted into an In both cases the profile curve is simply a straight segment, orange colored. The equivalent of the blue and yellow zone also have been colored. Right : our result with the corresponding operators, zoomed in the rectangle. In the yellow zone, no visible change. In the blue zone, the layers have been untangled. The relative influence of each layer depend on θ: top-right, the red layer is dominating. Bottom-right, the green layer has a greater influence and impose its form on the red one.

implicit surface as the 0-isovalue of a Hermite Radial Basis Function (HRBF) ( f 1 , f 2 ) as proposed by Wendland et al. [Wen04] . Next, two new fields ( f 1 , f 2 ) are computed as the result of some new operators (O 1 , O 2 ) applied on the original fields such that

f 1 = O 1 ( f 1 , f 2 ) and f 2 = O 2 ( f 1 , f 2 ).
The associated iso-surfaces shall be collision-free while ensuring contact where collisions occurred in the input.

We develop in the following our definition of our new operators (O 1 , O 2 ). For simplicity, we only describe O 1 , and O 2 has a symmetric expression with respect to the fields. We separate two cases. First, when the surfaces are far from any collision, the geometry of the surfaces shouldn't be altered. This means that the 0-isovalue of the field f 1 should be the same as the one from f 1 , and leads to the following relation

f 1 = 0 & f 2 < 0 ⇒ O 1 ( f 1 , f 2 ) = 0.
Second, in region where collisions occur, the 0-isovalue of f 1 is modified. In order to control shape of the resulting geometry after application of the operator, we introduce a Profile Curve C defined as the subset

{( f 1 , f 2 ) ∈ C ⇒ O 1 ( f 1 , f 2 ) = 0}.
C is a curve passing by the point (0, 0), and going toward the border. We chose C to be a straight line, and its angle θ ∈ [0, π/2] parameterizes the influence of one layer onto the other one as illustrated in Fig. 2. The actual operator is generated numerically from the boundary conditions and the constraint defined by C in solving a diffusion equation as described by Vaillant et al. [VGB * 14].

Considering a common 0-isovalue for f 1 and f 2 can model contact for surface, however, real cloths have non null thickness that may be visible (ex. leather clothes), and this can deepen penetration, or even create new collision. We handle in a unified way such thickness in our method in modeling a shift operator S to generate a new field f 1 such that f 1 = f 1 + S( f 1 , f 2 ). We compute S similarly to the previous operators using the two following constraints. First, the final position of the 0-isosurface of the field should be offsetted with respect to the thickness of the clothes. Second, the fields ( f 1 , f 2 ) should remain monotonous when following a trajectory normal to the cloth in order to avoid local minimum that would perturb the projection algorithm described next. This condition is met by imposing boundary conditions so that |d f 1 S( f 1 , f 2 )| < 1. Intuitively, the operator shouldn't shift the field more than it is varying. As a last step, the vertices of the initial meshes are projected onto their new respective implicit surfaces f 1/2 = 0 in integrating the vertex positions along the direction of the field gradient, leading to untangled meshes.

Results and conclusion

As seen in Fig. 1 and2, our method based on implicit model successfully untangle surface layers in collision, while letting the user parameterize the relative stiffness of each layer graphically. Our approach has the advantage of controlling the varying behavior in a unified way using an operator acting on field function. So far, we defined a binary operator suitable for two layers, but extending it to n-ary operator could allow us to handle multiple layers in a single step while handling their mutual influences. We also plan to handle, within the definition of the operator, the possibility to generate wrinkles in order to avoid surface compression when deforming the cloth surface.

Figure 2 :

 2 Figure 2: Left : Penetration between a red and a green layer.Colored in blue is a collision zone, in yellow a zone "far" from collision. Middle: two Operators O 1 with a varying profile-curve. In both cases the profile curve is simply a straight segment, orange colored. The equivalent of the blue and yellow zone also have been colored. Right : our result with the corresponding operators, zoomed in the rectangle. In the yellow zone, no visible change. In the blue zone, the layers have been untangled. The relative influence of each layer depend on θ: top-right, the red layer is dominating. Bottom-right, the green layer has a greater influence and impose its form on the red one.

c 2018 The Author(s) Eurographics Proceedings c 2018 The Eurographics Association.