Christian Bessiere
email: bessiere@lirmm.fr

Hélène Fargier
email: fargier@irit.fr

Christophe Lecoutre
email: lecoutre@cril.fr

Global Inverse Consistency for Interactive Constraint Satisfaction ⋆

Some applications require the interactive resolution of a constraint problem by a human user. In such cases, it is highly desirable that the person who interactively solves the problem is not given the choice to select values that do not lead to solutions. We call this property global inverse consistency. Existing systems simulate this either by maintaining arc consistency after each assignment performed by the user or by compiling offline the problem as a multi-valued decision diagram. In this paper, we define several questions related to global inverse consistency and analyse their complexity. Despite their theoretical intractability, we propose several algorithms for enforcing global inverse consistency and we show that the best version is efficient enough to be used in an interactive setting on several configuration and design problems. We finally extend our contribution to the inverse consistency of tuples.

Introduction

Constraint Programming (CP) is widely used to express and solve combinatorial problems. Once the problem is modelled as a constraint network, efficient solving techniques generate a solution satisfying the constraints, if such a solution exists. However, there are situations where the user has strong opinions about the way to build good solutions to the problem but some of the desirable/undesirable combinations will become clear only once some of the variables are assigned. In this case, the constraint solver should be there to assist the user in the solution design and to ensure her choices remain in the feasible space, removing the combinatorial complexity from her shoulders. See the Synthia system for protein design as an early example of using CP to interactively solve a problem [START_REF] Janssen | SYNTHIA: Assisted design of peptide synthesis plans[END_REF]. Another well known example of such an interactive solving of constraint-based models is product configuration [START_REF] Gelle | Interactive configuration using constraint satisfaction techniques[END_REF][START_REF] Amilhastre | Consistency restoration and explanations in dynamic CSPs -application to configuration[END_REF]. The person modelling the product as a constraint network for the company knows its technical and marketing requirements. She models the feasibility, availability and/or marketing constraints about the product. This constraint network captures the catalog of possible products, which may contain billions of solutions, but in an intentional and compact way. Nevertheless, the modeller does not know the constraints or preferences of the customer(s). Now, this is the customer who will look for solutions, with her own constraints and preferences on the price, the colour, or any other configurable feature.

These applications refer to an interactive solving process where the user selects values for variables according to her own preferences and the system checks the constraints of the network, until all variables are assigned and satisfy all constraints of the network. This solving policy raises an important issue: the person who interactively solves the problem should not be led to a dead-end where satisfying all constraints of the network is impossible. Existing interactive solving systems address this issue either by compiling the constraint network into a multivalued decision diagram (MDD) at the modelling phase [START_REF] Amilhastre | Consistency restoration and explanations in dynamic CSPs -application to configuration[END_REF][START_REF] Hadzic | Interactive reconfiguration in power supply restoration[END_REF][START_REF] Hadzic | Layer compression in decision diagrams[END_REF] or by enforcing arc consistency on the network after each assignment performed by the user [START_REF] Janssen | SYNTHIA: Assisted design of peptide synthesis plans[END_REF]. Compiling the constraint network as a MDD can require a significant amount of time and space. That is why compilation is performed offline (before the solving session). As a consequence, configurators based on a MDD compilation are restricted to static constraint networks: non-unary constraints can neither be added nor removed once the network compiled. It is thus not possible for the user to perform complex requirements, e.g., she is interested in travelling to Venezia only during the carnival period. Arc and dynamic arc consistencies require a lighter computational effort but the user can be trapped in dead-ends, which is very risky from a commercial point of view. It has been shown in [START_REF] Debruyne | Domain filtering consistencies[END_REF] that arc consistency (and even higher levels of local consistency) can be very bad approximations of the ideal state where all values remaining in the network can be extended to solutions.

The message of our paper is that for many of the problems that require interactive solving of the problem, and especially for real problems, it is computationally feasible to maintain the domains of the variables in a state where they only contain those values which belong to a complete solution extending the current choices of the user. Inspired by the nomenclature used in [START_REF] Freuder | Neighborhood inverse consistency preprocessing[END_REF] and [START_REF] Martinez | Résolution interactive de problemes de satisfaction de contraintes[END_REF], we call this level of consistency global inverse consistency (GIC).

Our contribution addresses several aspects. First, we formally characterise the questions that underlie the interactive constraint solving loop and we show that they are all NP-hard. Second, we provide several algorithms with increasing sophistication to address those tasks and we experimentally show that the most efficient one is efficient enough to be used in an interactive constraint solving loop of several non trivial configuration and design problems. Third, we finally extend all these contributions to the positive consistency of constraints, which is a problem closely related to GIC that appears in configuration.

Background

A (discrete) constraint network (CN) N is composed of a finite set of n variables, denoted by vars(N ), and a finite set of e constraints, denoted by cons(N ). Each variable x has a domain which is the finite set of values that can be assigned to x. The initial domain of a variable x is denoted by dom init (x) whereas the current domain of x is denoted by dom(x); we always have dom(x) ⊆ dom init (x). The maximum domain size for a given CN will be denoted by d. To simplify, a variable-value pair (x, a) such that x ∈ vars(N ) and a ∈ dom(x) is called a value of N . Each constraint c involves an ordered set of variables, called the scope of c and denoted by scp(c), and is semantically defined by a relation, denoted by rel(c), which contains the set of tuples allowed for the variables involved in c. The arity of a constraint c is the size of scp(c), and will usually be denoted by r.

An instantiation I of a set X = {x 1 , . . . , x k } of variables is a set {(x 1 , a 1 ), . . ., (x k , a k )} such that ∀i ∈ 1..k, a i ∈ dom init (x i ); X is denoted by vars(I) and each a i is denoted by An instantiation I on a CN N is locally consistent iff (i) I is valid on N and (ii) every constraint of N covered by I is satisfied by I. A solution of N is a complete locally consistent instantiation on N ; sols(N ) denotes the set of solutions of N . A CN N is satisfiable iff sols(N ) = ∅.

I[x i ]. An instantiation I on a CN N is an instantiation of a set X ⊆ vars(N ) ; it is complete if vars(I) = vars(N ). I is valid on N iff ∀(x,
The ubiquitous example of constraint propagation is enforcement of generalised arc consistency (GAC) which removes values from domains without reducing the set of solutions of the constraint network. A value (x, a) of a CN N is GAC on N iff for every constraint c of N involving x, there exists a valid instantiation I of scp(c) such that I satisfies c and I[x] = a. N is GAC iff every value of N is GAC. Enforcing GAC means removing GAC-inconsistent values from domains until the constraint network is GAC. In this paper, we shall refer to MAC which is an algorithm considered to be among the most efficient generic approaches for the solution of CNs. MAC [START_REF] Sabin | Contradicting conventional wisdom in constraint satisfaction[END_REF] explores the search space depth-first and enforces (generalised) arc consistency after each decision taken (variable assignment or value refutation) during search. A past variable is a variable explicitly assigned by the search algorithm whereas a future variable is a variable not (explicitly) assigned. The set of future variables of a CN N is denoted by vars f ut (N ).

Problems Raised by Interactive Constraint Solving

In this section we formally characterise the questions that underlie the interactive constraint solving loop and we study their theoretical complexity.

Formalization

We first need to define global inverse consistency.

Definition 1 (Global Inverse Consistency

). A value (x, a) of a CN N is globally in- verse consistent (GIC) iff ∃I ∈ sols(N ) | I[x] = a. A CN N is GIC iff every value of N is GIC.
The GIC closure of N is the CN obtained from N by removing all the values that do not belong to a solution of N . The obvious problems that follow are to check whether a constraint network is GIC or not, and to enforce GIC.

Problem 1 (Deciding GIC) Given a CN N , is N GIC? Problem 2 (Computing GIC) Given a CN N , compute the GIC closure of N .

As we are interested in interactive solving, we define the problem of restoring (maintaining) GIC after the user has performed a variable assignment.

Problem 3 (Restoring GIC) Given a CN N that is GIC, and a value (x, a) of N , restore GIC after the assignment x = a has been performed.

In a configuration setting, as soon as some mandatory variables have been set, the user can ask for an automatic completion of the remaining variables. Hence the definition of following problem: Problem 4 (Solving a GIC network) Given a CN N that is GIC, find a solution to N .

Complexity Results

Not surprisingly, the basic questions related to GIC (Problems 1 and 2) are intractable.

Theorem 1 (Problem 1). Deciding whether a constraint network N is GIC is NPcomplete, even if N is satisfiable.

Proof. We first prove membership to NP. For each value (x, a) of N , it is sufficient to provide a solution I of N such that the projection I[x] of I on variable x is equal to a. This certificate has size n • n • d and can be checked in polynomial time.

Completeness for NP is proved by reducing 3COL to the problem of deciding whether a satisfiable CN is GIC. Take any instance of the 3COL problem, that is, a graph G = (V, E). Consider the CN N where vars(N

) = {x i | i ∈ V }, dom(x i ) = {0, 1, 2, 3}, ∀i ∈ V , and cons(N ) = {(x i = x j ) ∨ (x i = 0 ∧ x j = 0) | (i, j) ∈ E}.
Clearly [0, . . . , 0] is a solution of N , and by construction, N has other solutions iff G is 3-colourable. Now, if G is 3-colourable, N is GIC because colours are completely interchangeable. Therefore, N is GIC iff G is 3-colourable. ⊓ ⊔ Our proof shows that hardness for deciding GIC holds for binary CNs (i.e., CNs only involving binary constraints). We have another proof, inspired from that used in Theorem 3 in [START_REF] Astesana | Constraint-based vehicle configuration: A case study[END_REF], that shows that deciding GIC is still hard for Boolean domains and quaternary constraints.

Theorem 2 (Problem 2). Computing the GIC closure of a constraint network N is NP-hard and NP-easy, even if N is satisfiable.

Proof. We prove NP-easiness by showing that a polynomial number of calls to a NP oracle are sufficient to build the GIC closure of N . For each value (x, a) of N , we ask the NP oracle whether N with the extra constraint x = a is satisfiable (we call this an inverse check). Once all values have been tested, we build the GIC closure of N by removing from each dom(x) all values a for which the oracle test returned 'no'. Hardness is a direct corollary of Theorem 1.

⊓ ⊔ Notice that the two previous intractability results are still valid when the CN is satisfiable, as is the case at the beginning of an interactive resolution session.

We finally show that Problems 3 and 4 are unfortunately not easier than checking GIC or enforcing GIC from scratch. But they are not harder.

Theorem 3 (Problem 3). Given a CN N that is GIC, and a value (y, b) of N , computing the GIC closure of the CN N ′ , where vars(N ′ ) = vars(N ) and cons(N ′ ) = cons(N ) ∪ {y = b} is NP-hard and NP-easy.

Proof. NP-easiness is proved as in the proof of Theorem 2 by showing that a polynomial number of calls to a NP oracle are sufficient to build the GIC closure of N ′ . For each value (x, a) of N (except values (y, a) with a = b), we ask the NP oracle whether N ′ with the extra constraint x = a is satisfiable. Once all values have been tested, we build the closure of N ′ by removing from dom(y) all values a = b and removing from each dom(x) all values a for which the oracle test returned 'no'. Hardness is a direct corollary of Theorem 7 in [START_REF] Astesana | Constraint-based vehicle configuration: A case study[END_REF].

⊓ ⊔ Theorem 4 (Problem 4). Generating a solution to a GIC constraint network cannot be done in polynomial time, unless P = N P .

Proof. The following proof is derived from [START_REF] Papadimitriou | [END_REF]. But it is also a corollary of the recent and more complex Theorem 3.1 in [START_REF] Gottlob | On minimal constraint networks[END_REF]. Suppose we have an algorithm A that generates a solution to a GIC constraint network N in time bounded by a polynom p(|N |). Take any instance of the 3COL problem, that is, a graph G = (V, E). Consider the CN N where vars

(N ) = {x i | i ∈ V }, dom(x i ) = {0, 1, 2}, ∀i ∈ V , and cons(N ) = {x i = x j | (i, j) ∈ E}. N has a solu- tion iff G is 3-colourable. Now, if G is 3-colourable, N is GIC because colours are com- pletely interchangeable. Thus, it is sufficient to run A during p(|N |) steps.
If it returns a solution to N , then the 3COL instance is satisfiable. Otherwise, the 3COL instance is unsatisfiable. Therefore, as 3COL is NP-complete, there cannot exist a polynomial algorithm for generating a solution to a GIC constraint network, unless P = N P . ⊓ ⊔

GIC Algorithms

In this section, we introduce four algorithms to enforce global inverse consistency. These GIC algorithms use increasingly sophisticated data structures and techniques that have recently proved their worth in filtering algorithms proposed in the literature; e.g., see [START_REF] Lecoutre | A study of residual supports in arc consistency[END_REF][START_REF] Ullmann | Partition search for non-binary constraint satisfaction[END_REF]. To simplify our presentation, we assume that the CNs are satisfiable, which is the case in interactive resolution, allowing us to avoid handling domain wipe-outs in the GIC procedures. Note that these algorithms can be used to enforce GIC, but also to maintain it during a user-driven search. This is why we refer to the set vars f ut (N ) of future variables in some instructions. The first algorithm, GIC1, described in Algorithm 1, is really basic: it will be used as our baseline during our experiments. For each value a in the domain of a future variable x, a solution for the CN N where x is assigned the value a, denoted by N | x=a , is sought using a complete search algorithm. This search algorithm, called here search-SolutionFor, either returns the first solution that can be found, or the special value nil. Our implementation choice will be the algorithm MAC that maintains (G)AC during a backtrack search [START_REF] Sabin | Contradicting conventional wisdom in constraint satisfaction[END_REF]. Hence, in Algorithm 1, when it is proved with searchSolutionFor that no solution exists, i.e., I = nil, the value a can be deleted. Note that, in contrary to Algorithm 1: GIC1(N : CN)

1 foreach variable x ∈ vars f ut (N ) do 2 foreach value a ∈ dom(x) do 3 I ← searchSolutionFor(N |x=a) 4 if I = nil then 5 remove a from dom(x)
Algorithm 2: handleSolution2/3(x: variable, I: instantiation) Data: GIC3 is obtained by considering light grey coloured instructions between lines 5 and 6, and after line 10

1 foreach variable y ∈ vars f ut (N ) | y is revised after x do 2 if stamp[y][I[y]] = time then 3 stamp[y][I[y]] ← time 4 nbGic[y] + + Algorithm 3: isValid(X : set of variables, I : instantiation): Boolean 1 foreach variable x ∈ X do 2 if I[x] / ∈ dom(x) then
1 time + + 2 foreach variable x ∈ vars f ut (N ) do 3 nbGic[x] ← 0 4 foreach variable x ∈ vars f ut (N ) | nbGic[x] < |dom(x)| do 5 foreach value a ∈ dom(x) | stamp[x][a] < time do if isValid(vars(N ),residue[x][a]) then handleSolution2/3(x,residue[x][a]) continue 6 I ← searchSolutionFor(N |x=a) 7 if I = nil then 8 remove a from dom(x) 9 else 10 handleSolution2/3(x,I) residue[x][a] ← I
weaker forms of consistency, when a value is pruned there is no need for GIC to repeat the process of iterating over the values remaining in the CN.

The second algorithm, GIC2 described in Algorithm 4 (ignoring light grey lines), uses timestamping. This is useful when GIC is maintained during a user-driven search. We use an integer variable time for counting time, and we introduce a two-dimensional array stamp that associates with each value (x, a) of the CN the last time (value of stamp[x][a]) a solution was found for that value. We also assume that variables are implicitly totally ordered (for example, in lexicographic order). Then, the idea is to increment the value of the variable time whenever a new call to GIC2 is performed (see line 1) and to test time against each value (x, a) of the CN (see line 5) to determine whether it is necessary or not to search for a solution for (x, a). When a solution I is found, function handleSolution2/3 is called at line 10 in order to update stamps. Actually, we only update the stamps of values in I corresponding to variables that are processed after x in the loop of revisions (line 4) in Algorithm 4. These are the variables that have not been processed yet by the loop at line 4 of Algorithm 4. Finally, by further introducing a one-dimensional array nbGic that associates with each variable x of the CN the number of values in dom(x) that have been proved to be GIC, it is possible to avoid some iterations of loop 5; see initialization at lines 2-3, testing at line 4 and update at line 4 of Algorithm 2.

The third algorithm, GIC3, described in Algorithm 4 when considering light grey lines, can be seen as a refinement of GIC2 obtained by exploiting residues, which correspond to solutions that have been previously found. Here, we introduce a twodimensional array residue that associates with each value (x, a) of the CN the last solution found for this value (potentially, during another call to GIC3). Because residual solutions may not be valid anymore, for each value (x, a) we need to test the validity of residue[x][a] by calling the function isValid; see instructions between lines 5 and 6. If the residue is valid, we call handleSolution2/3 to update the other data structures, and we continue with the next value in the domain of x. A validity test, Algorithm 3, only checks that all values in a given complete instantiation are still present in the current domains. Of course, when a new solution is found, we record it as a residue; see instruction after line 10.

Our last algorithm, GIC4 described in Algorithm 6, is based on an original use of simple tabular reduction [START_REF] Ullmann | Partition search for non-binary constraint satisfaction[END_REF]. The principle is to record all solutions found during the enforcement of GIC in a table, so that an (adaptation of an) algorithm such as STR2 [START_REF] Lecoutre | STR2: Optimized simple tabular reduction for table constraints[END_REF] can be applied. The current table is given by all elements of an array solutions at indices ranging from 1 to nbSolutions. As for STR2, we introduce two sets of variables called S val and S sup . The former allows us to limit validity control of solutions to the variables whose domains have changed recently (i.e., since the last execution of GIC4). This is made possible by reasoning from domain cardinalities, as performed at lines 3 and 26-27 with the array lastSize. The latter (S sup ) contains any future variable x for which at least one value is not in the array gicValues[x], meaning that it has still to be proved GIC. Related details can be found in [START_REF] Lecoutre | STR2: Optimized simple tabular reduction for table constraints[END_REF]. After the initialization of S val and S sup (lines 1-8), each instantiation solutions[i] of the current table is processed (lines 11-16). If it remains valid (hence, a solution), we update structures gicValues and S sup by calling the function handleSolution4. Otherwise, this instanti-Algorithm 5: handleSolution4(I : instantiation) ation is deleted by swapping it with the last one. The rest of the algorithm (lines 17-25) just tries to find a solution support for each value not present in gicValues. When a new solution is found, it is recorded in the current table (lines 23-24) and handleSolu-tion4 is called (line 25).

1 foreach variable x ∈ S sup do 2 if I[x] / ∈ gicValues[x] then 3 gicValues[x] ← gicValues[x] ∪ {I[x]} 4 if |gicValues[x]| = |dom(x)| then 5 S sup ← S sup \ {x} Algorithm 6: GIC4(N : CN) // Initialization of structures 1 S val ← ∅ 2 foreach variable x ∈ vars(N ) do 3 if |dom(x)| = lastSize[x] then 4 S val ← S val ∪ {x} 5 S sup ← ∅ 6 foreach variable x ∈ vars f ut (N ) do 7 gicValues[x] ← ∅ 8 S sup ← S sup ∪ {x} // The
Theorem 5. Algorithms GIC1, GIC2, GIC3 and GIC4 enforce GIC.

Proof. (sketch) This is immediate for GIC1. For GIC2 and GIC3, the use of timestamps and residues permits us to avoid useless inverse checks. For GIC4, the same arguments as those used for proving that STR2 enforces GAC hold. Simply, additional inverse checks are performed for values not collected (in gicValues) during the traversal of the current table. ⊓ ⊔ The worst-case space complexity (for the specific data structures) of GIC1 is O(1). For GIC2 and GIC3, this is O(nd) because nbGic is O(n), stamp and residue are O(nd). For GIC4, S val , S sup and lastSize are O(n), gicValues is O(nd), and the structure solutions is O(n 2 d). The time complexity of the GIC algorithms can be expressed in term of the number of calls to the (oracle) searchSolutionFor. For GIC1, this is O(nd). For GIC2, in the best-case, only d calls are necessary, one call permitting to prove (through timestamping) that n values are GIC. For GIC3 and GIC4, still in the best-case and assuming the case of maintaining GIC (i.e., after the assignment of a variable by the user), no call to the oracle is necessary (residues and the current table permit alone to prove that all values are GIC). This rough analysis of time complexity suggests that GIC3 and GIC4 might be the best options.

Tuple Inverse Consistency

Up to this point, we have based our analysis on the last part of the interactive resolution process, i.e., the specification of a solution of the constraint network by the user. This allowed us to make the simplifying assumptions that the user is only looking at the domains of the variables. After each variable assignment, she just wants to know which values remain feasible for non assigned variables.

The situation is different at the modelling phase, e.g., the engineers of the company dynamically build the set of constraints that define the configurable product. At this point, GIC is also a crucial functionality, not for deriving a solution (a end product), but to ensure that each of the options proposed in the catalog (each of the values in the domains of the constraint network) is present in at least one end product. It is meaningless to propose (and advertise on) a sophisticated air bag system when it cannot equip any car in practice.

In that modelling phase, the need for information on the extensibility to solutions is not restricted to domains, but extends to (some of) the constraints of the model. Many constraints have actually a double meaning. Following the standard semantics of constraints, the first one is negative: technical constraints forbid combinations of variables. The second one is positive: the possibilities that are left by some (generally, table) constraints have to be effective. Let us assume, for instance, that a constraint means 'The level of equipment of vehicles with type M3 engine can be middle level or luxurious'.

If some other constraint excludes the vehicles M3 engine for luxurious level of equipment, the specification of the product is considered as inconsistent. This property has been called positive consistency in [START_REF] Astesana | Constraint-based vehicle configuration: A case study[END_REF] and actually refers to the extensibility to a solution of each of the tuples allowed by the constraint of interest: Definition 2 (Tuple Inverse Consistency). Given a CN N , a tuple τ on a set of variable X is said to be inverse consistent (TIC) in N iff there exists a solution

I of N such that ∀x ∈ X, I[x] = τ [x].

Definition 3 (Positive Consistency).

A constraint c is positively consistent in N iff for any valid tuple τ ∈ rel(c), τ is TIC.

The positive closure of a constraint c is the constraint obtained from c by removing from rel(c) all the valid tuples that are not TIC in N . The obvious problem that follows is to check whether a constraint is positively consistent or not.

Problem 5 (Deciding Positive Consistency) Given a CN N and a constraint c of N , is c positively consistent in N ?

Deciding positive consistency has been shown to be NP-hard, even when the constraint network is known to be satisfiable ( [START_REF] Astesana | Constraint-based vehicle configuration: A case study[END_REF]). The other problem of interest is to restore positive consistency on a constraint after the user has refined her model by adding a constraint to the network.

Experiments

In order to show the practical interest of our approach, we have performed several experiments mainly using a computer with processors Intel(R) Core(TM) i7-2820QM CPU 2.30GHz; for random instances, we used a cluster of Xeon 3.0GHz with 13GB of RAM. Our main purpose was to determine whether maintaining GIC is a viable option for configuration-like problem instances and for interactive puzzle creation, as well as to compare the relative efficiency of the four GIC algorithms described in Section 4. In Table 1, we show relevant features of car configuration instances, generated with the help of our industrial partner Renault. For each of the six instances currently available, 4 we indicate the number of variables (n), the size of the greatest domain (d), the number of constraints (e), the greatest constraint arity (r), the size of the greatest table (t), the total number of values (D = x∈vars(N ) |dom(x)|), and the total number of tuples (T = c∈cons(N ) |rel(c)|).

The left part of Table 2 presents the CPU time required to establish GIC on the six Renault configuration instances. Clearly GIC1 is outperformed by the three other algorithms, which have here rather similar efficiency. The right part of Table 2 aims at simulating the behaviour of a configuration software user who makes the variable choices and value selections. It presents the CPU time required to maintain GIC along a single branch built by performing random variable assignments (random variable assignment simulates the user, who chooses the variables and the values according to her preference). Specifically, variables and values are randomly selected in turn, and after each assignment, GIC is systematically enforced to maintain this property. Of course, no conflict (dead-end) can occur along the branch due to the strength of GIC, which is why we use the term of greedy executions. CPU times are given on average for 100 executions (different random orderings). For all instances, GIC3 and GIC4 are maintained very fast, whereas on the biggest instances, GIC2 requires a few seconds and GIC1 around ten seconds.

Establishing GIC with

Maintaining GIC with GIC1 GIC2 GIC3 GIC4 GIC1 GIC2 GIC3 GIC4 One great advantage of GIC is that it guarantees that a conflict can never occur during a configuration session. However, one may wonder whether the risk of failure(s) is really important in user-driven searches that use a weaker consistency such as GAC or a partial form of it (Forward Checking). Table 3 shows the number of conflicts (sum over 100 executions using random orderings) encountered when following a MAC or a nFC2 [START_REF] Bessiere | On Forward Checking for non-binary constraint satisfaction[END_REF] strategy. The number of conflict situations can be very large with nFC2 (for two instances, we even report the impossibility of finding a solution within 10 minutes with some random orderings). For MAC, the number of failures is rather small but the risk is not null (for example, the risk is equal to 5% for megane). The encouraging results obtained on Renault configuration instances led us to test other problems, in particular to get a better picture of the relative efficiency of the various GIC algorithms. For example, on classical Crossword instances (see Table 4), GIC1 is once again clearly outperformed while the three other algorithms are quite close, where there is still a a small benefit of using GIC4.

Establishing GIC with

Maintaining GIC with GIC1 GIC2 GIC3 GIC4 GIC1 GIC2 GIC3 GIC4 It is worthwhile to note that GIC is a nice property that can be useful when puzzles, where hints are specified, have to be conceived. Typically, one looks for puzzles where only one solution exists. One way of building such puzzles is to add hints in sequence, while maintaining GIC, until all domains become singleton. For example, this is a possible approach for constructing Sudoku and Magic Square grids, with the advantage that the user can choose freely the position of the hints. 5 On the left part of Table 5, we report the time to enforce GIC on empty Sudoku grids of size 9x9 and 16x16, and on empty Magic square of size 4x4 and 5x5, and on the right part, the average time required to maintain GIC until a fixed point is reached, meaning that after several hints have been randomly selected and propagated, we have the guarantee of having a onesolution puzzle. GIC4 is a clear winner, with for example, a 30% speedup over GIC2 and GIC3 on sudoku-16x16, and more than one order of magnitude over GIC1. Overall, the results we obtain show that MIC, i.e., maintaining GIC, is a practicable solution (at least for some problems) as the average time between each decision of the user is small with GIC4.

The efficiency of MIC on structured under-constrained instances piqued our curiosity. So we decided to compare MIC (embedding GIC4) and MAC on series of binary random instances generated from Model RB [START_REF] Xu | Exact phase transitions in random constraint satisfaction problems[END_REF]. For the class RB(2, 30, 0.8, 3, t), see [START_REF] Xu | Random constraint satisfaction: easy generation of hard (satisfiable) instances[END_REF], we obtain instances with 30 variables, 15 values per domain and 306 binary constraints of tightness t, and for the class RB(2, 40, 0.8, 3, t), instances with 40 variables, 19 values per domain and 443 binary constraints of tightness t. For each value of t ranging from 0.01 to 0.50 (step of 0.01), a series of 100 instances was generated so as to observe the behaviour of MIC on both under-constrained instances and over-constrained instances; the theoretical threshold is around 0.23. Figure 1 shows the average CPU time of MIC and MAC on series of class RB(2, 30, 0.8, 3, t). On the left, Figure 1(a), the ordering of variables and values is random (simulating a free user-driven search). MIC outperforms MAC when the ordering is random and the tightness is greater than or equal to 0.23. That means that the strong inference capability of MIC do pay off for the unsatisfiable instances. On the right, Figure 1(b), the variable ordering heuristic is dom/wdeg [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF] and the value ordering heuristic is lexico. Obviously, MAC with dom/wdeg is clearly faster than MIC. However, if used in a context of interactive resolution, the dom/wdeg ranking of the variables drives the user, who is not free anymore in the choices of its variables. It may ask her to assign first variables that are meaningless to her, restricting her future choices on important variables. The outcome will be a solution which is very bad with respect to the preferences of the user. All of this suggests that MIC can be efficient enough to be used in practice, except for a (small) region of satisfiable instances lying at the left of the threshold point. Figure 2 shows similar results with respect to series of class RB(2, 40, 0.8, 3, t).

One other practical issue we are interested in is the effectiveness of positive consistency. Hence, we tested to establish positive consistency on existing constraints of the Renault configuration instances, see Table 6. The algorithm we used here is a simple adaptation of GIC1 to tuples (so, certainly, several optimizations are possible). A few hundreds of seconds are necessary to ensure the positive consistency of all existing constraints of the biggest instances. Finally, in our last experiment, for each constraint network, we randomly select a constraint of interest c i for which positive consistency must be ensured (as if the modeller were asking for the positive consistency of this constraint), and we randomly select a set C containing 10% of the set of constraints. We initially consider the CN without the constraints in C, and we enforce positive consistency on c i . Then we simulate a session of product modelling: we post each constraint in C in turn and maintain positive consistency on c i . In our implementation (not detailed here due to lack of space), we use residues, i.e., a solution stored for each tuple of c i . The first line of Table 7 shows the average CPU time to maintain positive consistency on the constraint of interest. For the second line, the constraint of interest is not randomly chosen but set to the constraint with the largest table. The obtained results are rather promising (except for the instance megane).

Conclusion

We have analysed the problems that arise in applications that require the interactive resolution of a constraint problem by a human user. The central notion is global inverse consistency of the network because it ensures that the person who interactively solves the problem is not given the choice to select values that do not lead to solutions. We have shown that deciding, computing, or restoring global inverse consistency, and other related problems are all NP-hard. We have proposed several algorithms for enforcing global inverse consistency and we have shown that the best version is efficient enough to be used in an interactive setting on several configuration and design problems. This is a great advantage compared to existing techniques usually used in configurators. As opposed to techniques maintaining arc consistency, our algorithms give an exact picture of the values remaining feasible. As opposed to compiling offline the problem as a multi-valued decision diagram, our algorithms can deal with constraint networks that change over time (e.g., an extra non-unary constraint posted by a customer who does not want to buy a car with more than 100,000 miles except if it is a Volvo). We have finally extended our contribution to the inverse consistency of tuples, which is useful at the modelling phase of configuration problems. One direct perspective of this work is to try computing diverse solutions when enforcing GIC. This should permit, on average, to reduce the number of search runs. Some techniques developed in [START_REF] Hebrard | Finding diverse and similar solutions in constraint programming[END_REF] might be useful.

  a) ∈ I, a ∈ dom(x). I covers a constraint c iff scp(c) ⊆ vars(I), and I satisfies a constraint c with scp(c) = {x 1 , . . . , x r } iff (i) I covers c and (ii) the tuple (I[x 1 ], . . . , I[x r ]) ∈ rel(c).

Algorithm 4 :

 4 GIC2/3(N : CN)

  variable x ∈ vars f ut (N ) do lastSize[x] ← |dom(x)|

Problem 6 (

 6 Restoring Positive Consistency) Given a CN N , given a positive consistent constraint c in N , given any extra constraint c ′ not in cons(N ), compute the new positive closure of c in the network obtained from N by adding c ′ to cons(N ).

Fig. 1 .Fig. 2 .

 12 Fig. 1. Mean search cost (100 instances) of solving instances in class RB(2, 30, 0.8, 3, t) with MAC and MIC.

  table of current solutions is traversed

	9 i ← 1
	10 while i ≤ nbSolutions do
	11	if isValid(S val ,solutions[i]) then
	12	handleSolution4(solutions[i])
	13	i + +
	14	else
	15	solutions[i] ← solutions[nbSolutions]
	16	nbSolutions --
		// Search for values not currently supported is performed
	17 foreach variable x ∈ S sup do

18 foreach value a ∈ dom(x) \ gicValues[x] do 19 I ← searchSolutionFor(N |x=a)

Table 1 .

 1 Features of six Renault configuration instances.

		n	d	e	r	t	D	T
	souffleuse	32	12	35	3	55	145	350
	megane	99	42	113	10	48,721	396	194,838
	master	158	324	195	12	26,911	732	183,701
	small	139	16	147	8	222	340	3,044
	medium	148	20	174	10	2,718	424	9,532
	big	268	324	332	12	26,881	1,273	225,989

Table 2 .

 2 CPU time (in seconds) to establish GIC on Renault configuration instances, and to maintain it (average over 100 random greedy executions).

	souffleuse	0.02	0.01	0.01	0.01	0.13	0.07	0.02	0.02
	megane	2.94	0.71	0.72	0.71	4.26	1.18	0.05	0.04
	master	2.45	1.35	1.33	1.33	9.81	3.57	0.07	0.06
	small	0.14	0.02	0.03	0.03	0.32	0.05	0.01	0.01
	medium	0.26	0.04	0.05	0.04	0.35	0.04	0.01	0.01
	big	4.19	1.16	1.10	1.10	12.6	2.60	0.05	0.05

Table 3 .

 3 Number of conflicts encountered when running nFC2 and MAC (sum over 100 random executions).

		souffleuse	megane	master	small	medium	big
	nFC2	252,605	313,910	time-out	3,728	7,824	time-out
	MAC	0	7	5	0	3	3

Table 4 .

 4 CPU time (in seconds) to establish GIC on some Crosswords instances, and to maintain it on average over 100 random greedy executions.

	ogd-vg5-5	2.25	0.67	0.67	0.67	2.34	0.79	0.73	0.70
	ogd-vg5-6	6.40	2.18	2.19	2.19	7.42	2.82	2.58	2.48
	ogd-vg5-7	25.8	9.91	9.87	9.84	33.4	15.2	14.3	13.8
		Establishing GIC with	Maintaining GIC with
		GIC1 GIC2 GIC3 GIC4	GIC1 GIC2 GIC3 GIC4
	sudoku-9x9	1.58	0.32	0.32	0.31	15.3	2.71	2.10	1.74
	sudoku-16x16	6.04	0.51	0.50	0.50	246	25.5	26.5	18.9
	magicSquare-4x4	0.96	0.26	0.28	0.28	1.63	0.69	0.71	0.71
	magicSquare-5x5	14.7	3.01	3.10	2.99	55.1	15.9	15.6	13.7

Table 5 .

 5 CPU time (in seconds) to establish GIC on Puzzle instances, and to maintain it on average over 100 random greedy executions until a unique solution is found.

Table 6 .

 6 CPU time (in seconds) and filtering in term of the number of tuples deleted when establishing positive consistency on Renault configuration instances.

		souffleuse	megane	master	small	medium	big
	CPU	0.68	352	368	2.6	4.2	613
	# tuples removed	0	138,493	90,874	240	5,425	105,020

Table 7 .

 7 Dynamic positive consistency filtering on Renault configuration instances (average CPU time over 100 executions).

		megane	master	big
	random	9.97	10.1	36.4
	largest	106.6	11.4	20.6

see http://www.irit.fr/ Helene.Fargier/BR4CP/benches.html

However, we are not claiming that maintaining GIC is the unique answer to this problem.

⋆ This work has been funded by the ANR ("Agence Nationale de la Recherche") project BR4CP

(ANR-11-BS02-008).


Y Mecheri

M Nedjar

A Lamure

M Aufray

C Drouet

Influence of Moisture on the Electrical Properties of XLPE Insulation

Keywords: XLPE, cables, aging, Moisture, Characterization techniques, Electrical properties

During their operating service, insulated power cables can be exposed to wet environment. The presence of moisture in cables surroundings may affect the properties of the used insulation material for instance, XLPE widely employed in MV and HV power cables insulation and therefore the reliability of the insulated cables. In order to examine the influence of wet aging conditions on the performances of XLPE insulated cables, samples (plates moulded from granules HFDE 4201-EC) of the same insulation material were exposed during 5600 hours to wet environment inside a cell simulating moisture. The XLPE material used in the present investigation is employed as insulation for medium voltage (MV) cables (18 / 30 kV). This work presents the results of the effect of aging under wet conditions on the electrical properties of XLPE. The goal of this paper was to investigate the eventual degradation of XLPE insulation under humidity effect by characterization techniques. For this purpose, measurements of dielectric losses factor, relative permittivity, volume resistivity and dielectric strength were performed.

I. INTRODUCTION

ross-Linked Polyethylene (XLPE) is widely used as power cable insulation because of its excellent performances [START_REF] Acedo | Dielectric characterization and conduction modelling of a water tree degraded LDPE[END_REF][START_REF] Celina | Characterisation and degradation studied of peroxide and silane crosslinked polyethylene[END_REF]. However, it is now well known that regardless of its good properties, XLPE can degrade when exposed to stress conditions. During their operating service, XLPE insulated power cables are expected to work under wet environments. In fact, Submarine insulated cables are immersed in water and underground ones are located in humid places [START_REF] Hirose | Lifetime assessment by intermitted inspection under the mixture weibull law model with application to XLPE cables[END_REF][START_REF] Eish | Effect of temperature rise and water contamination on leakage current in underwater used XLPE insulated power cables[END_REF]. Although their high safety designs, a physical damage caused by mishandling of the cables can allow water penetration into the insulation and may lead to water treeing [START_REF] Farkas | Water Treeing Retardant XLPE Insulation Grade with Improved Electrical Endurance[END_REF][START_REF] Acedo | Relations between the Water Tree Degradation of Polyethylene and Electrical Properties of the Material. Application to the Insulation Diagnostics of Power Cables[END_REF]. Numerous studies have reported the possible mechanisms of moisture permeation and water absorption of insulating materials from the environment [START_REF] Hirose | Lifetime assessment by intermitted inspection under the mixture weibull law model with application to XLPE cables[END_REF][START_REF] Nikolajevic | Investigation of water effects on degradation of Crosslinked polyethylene (XLPE) insulation[END_REF]. From many hypotheses, the water condenses at defects such as contamination, voids or interfacial cavities by the effect of electrical stress [START_REF] Lawson | Investigation of insulating deterioration in 15 kV and 22 kV polyethylene cables removed from service[END_REF][START_REF] Matsuba | Water tree mechanism in electrical insulation[END_REF]. The absorption of water within a solid dielectric (XLPE) depends on the body structure and on the distribution of electrical charges within the body-water or water vapour absorbed in the insulation of solid [START_REF] Nikolajevic | Investigation of water effects on degradation of Crosslinked polyethylene (XLPE) insulation[END_REF]. The water can be put in cable conductors during cable manufacture, transportation, stocking, laying, service, etc. [START_REF] Nikolajevic | The behaviour of water in XLPE and EPR cables and its influence on the electric characteristics of insulation[END_REF]. The existence of moisture in cables surroundings may affect the basic characteristics of the insulating material and therefore the reliability of XLPE insulated cables. Several experimental and theorical studies [START_REF] Pélissou | Water content of XLPE cable components[END_REF] have been performed to understand and to describe the phenomena in a cable context. In order to investigate the influence of wet aging conditions on the performances of XLPE insulated cables, press moulded XLPE samples of plates were exposed to wet environment inside a cell simulating moisture. The samples were exposed to moisture during 5600 hours. Periodically, about two plates were removed from the aging cell and cut into samples having a circular shape to subject destructives and non destructives tests accordingly to IEC 540 publication [START_REF]IEC Standard 540, Tests for insulations and sheaths of electric cables and cords (Elastomeric and Thermoplastic Compounds)[END_REF]. The aim of this paper was to characterize the degradation of XLPE insulation subjected to wet aging conditions. Evolution of dielectric losses factor (tan δ), permittivity (ε r ), volume resistivity (ρ) and dielectric strength (E b ) versus aging time were investigated. Temperature dependence of tan δ and ε r before and after aging were also studied.

II. EXPERIMENTAL PROCEDURE

A. Samples and wet aging conditions

Square plates of 300 mm x 300 mm with 2 mm thickness of XLPE were aged under wet environment inside a cell simulating moisture. The plates of XLPE were moulded and cross-linked at 180°C under a pressure of 300 bars from granules of Union Carbide Low Density Polyethylene Compound HFDE 4201-EC using pressurized heat press. The cross-linkable material contains 2% dicumyl peroxide (DCP) to generate cross-links and 0.2 wt. % of a hindered phenol (HP) as antioxidant. The studied material is used as insulation for medium voltage cables (18 / 30 kV). The samples were vertically suspended and exposed to 100% RH-relative humidity during 5600 hours inside an oven generating moisture using water heated by electrical resistance. After each 240 hours, about two plates were removed from the oven and cut into samples having a circular shape of 7.5 cm diameter to subject electrical tests. The destructives and non destructives tests investigated in the current work were performed accordingly to IEC 540 publication [START_REF] May | Contribution à l'étude des propriétés électriques de certains types de polymères à l'état solide[END_REF].

C B. Electrical properties measurements

The electrical properties tests were performed on five circular shaped samples. The dielectric losses factor and the relative permittivity were measured under the tolerated service temperature (90°C) of XLPE at the same time using TETEX AG Schering bridge with an applied voltage of 2 kV, 50 Hz. The measurements of the volume resistivity were carried out by a megohmmeter with a DC voltage of 500 V during 10 minutes application. Test temperatures were varied by means of a regulator. The Alternating Current (AC) Breakdown Voltage (BDV) tests were carried out with a BAUR OLPRUFGERAT PGO 90 A, Automatic apparatus using a microprobe cell immersed in insulating oil of BORAK 22 to avoid flashover. Uniform AC voltage at 50 Hz was increased linearly at 2 kV / s until breakdown. The dielectric strength (breakdown field) is evaluated from the breakdown voltage and the thickness of the sample.

III. RESULTS AND DISSCUSSION

In this section, we present results showing the evolution of the electrical properties of XLPE as a function of aging time under wet conditions. Some dielectric properties (tan δ, ε r ) with respect to test temperature are also investigated.

A. Dielectric losses factor

The measurement of dielectric losses factor (tan δ) is an important non-destructive method for testing HV insulated systems. It can serve as a representative indicator of other insulating material properties relevant to the aging phenomena. Figure 1 displays the XLPE dielectric losses factor variations with respect to aging time. The measurements were made at the temperature of 90°C with an applied voltage of 2 kV, 50Hz. The curve of tan δ presents variations characterized by the presence of some peaks having the following values: 1.7x10 -4 , 1.2x10 -4 , 0.4x10 -4 and 3x10 -4 obtained after 1350 h, 2800 h, 3500 h and 5000 h, respectively. Theses peaks could be explained by movements of XLPE macromolecular chains segments [START_REF] May | Contribution à l'étude des propriétés électriques de certains types de polymères à l'état solide[END_REF]. The dissipation factor (loss angle tangent) was also performed on the temperature range of 30°C to 140°C using a Schering bridge coupled with a temperature regulator. The measurements were carried out before and after aging under wet conditions (Fig. 2). The curves for tan δ are seen to increase rapidly with increasing temperature particularly over 100°C which is slightly superior than the acceptable operating temperature (90°C) of XLPE insulated cable. We mention that the values of tan δ after humidity exposure are higher than those obtained in virgin samples.

B. Dielectric constant

Measured simultaneously at the same conditions as the dissipation factor, the dielectric constant varies around the value of 2.0 with the time of moisture exposure (Fig. 3). As can be seen in the figure 3, the peaks appeared practically at the same aging time observed on tan δ curve. The temperature dependence of the relative dielectric constant was investigated too. The obtained results indicate that the relative permittivity curves present the same variation law (slight temperature dependence) before and after wet aging conditions (Fig. 4). The relative permittivity ε r decreases slightly as the test temperature progresses and its values after aging are relatively superior to those obtained prior to aging. In fact, at the XLPE maximum operating temperature ε r increases from 1.91 to 2.0 representing a rise of 6.8 %. In unaged samples, the dielectric constant versus test temperature drops from the value of 2.35 to 1.83 corresponding to a reduction of 22.12%. After moisture exposure, ε r diminishes from 2.0 to 1.8 representing a decline of 10 % of the property measured. The reduction in the dielectric constant values as a function of the temperature is believed to be caused by the diminution of the material density [START_REF] St-Onge | Research to Determine the Acceptable Emergency Operating Temperatures for Extruded Dielectric Cables[END_REF].

C. Volume resistivity

Volume resistivity is one property representing average deterioration of dielectric material. It constitutes a diagnostic tool for aging characterization. Performed under DC voltage of 500 V and at 90°C, the changes in the XLPE volume resistivity versus duration of moisture exposure are depicted in figure 5.

Qualitatively, we remark that the volume resistivity of the studied material shows variations with respect to the time of humidity exposure. Theses variations are categorized by the existence of some peaks. Indeed at the beginning, the property increases from about 10 13 Ω•cm to 10 14 Ω•cm value, then slopes down but not monotonously to reach a value of 10 12 Ω•cm after 5600 hours of aging under moisture.

D. Dielectric strength

The dielectric strength measurement is a destructive test used to diagnosis insulating materials dielectric state. The experiments were conducted by BDV equipment using a microprobe cell arrangement. The changes of dielectric strength as a function of aging time is presented in figure 6. It is seen in the curve that the breakdown field (E b ) exhibits variations versus moisture exposure time. In unaged XLPE samples, the dielectric strength value was 42.5 kV/mm. After a long aging time (5600 hours), a decline in the breakdown field is clearly apparent. In fact, E b has decreased to a value of 24 kV/mm corresponding to a change of 43.3% of the dielectric property measured on virgin samples. It can be noticed that a long exposure under moisture seems to have significant effect on the dielectric strength of the XLPE.

IV. CONCLUSION

In this work, we investigated the effects of wet aging conditions on the electrical properties of XLPE, insulating material of MV cables (18/30 kV). For this purpose, square plates of the same material were aged under moisture environment inside a cell simulating moisture. Based on the obtained results, the moisture influences slightly the dielectric constant. However, we observed a significant degradation of the used material (XLPE) under the aging conditions abovementioned. This degradation is characterized by the dissipation factor increase and the decrease of volume resistivity and dielectric strength. For a better knowledge of the XLPE degradation under wet conditions, DMA, FTIR, TGA-DTA and DSC analysis would be performed.

Fig. 1 .

 1 Fig. 1. Dielectric losses factor variations with respect to aging time.

Fig. 2 .

 2 Fig. 2. Temperature dependence of dielectric losses factor before and after wet aging.

Fig. 3 .

 3 Fig. 3. Changes in the dielectric constant as a function of aging time.

Fig. 4 .

 4 Fig. 4. Temperature dependence of dielectric constant before and after moisture exposure.

Fig . 5 .

 5 Fig .5. Volume resistivity evolution versus aging time.

Fig. 6 .

 6 Fig. 6. Dielectric strength changes versus aging time.


Dorian Gomez

Mathias Paulin

David Vanderhaeghe

Pierre Poulin
email: poulin@iro.umontreal.ca

Time and Space Coherent Occlusion Culling for Tileable Extended 3D Worlds

Keywords: occlusion culling, visibility, procedural modeling, tiling, PVS, CHC++, BVH

In order to interactively render large virtual worlds, the amount of 3D geometry passed to the graphics hardware must be kept to a minimum. Typical solutions to this problem include the use of potentially visible sets and occlusion culling, however, these solutions do not scale well, in time nor in memory, with the size of a virtual world. We propose a fast and inexpensive variant of occlusion culling tailored to a simple tiling scheme that improves scalability while maintaining very high performance. Tile visibilities are evaluated with hardwareaccelerated occlusion queries, and in-tile rendering is rapidly computed using BVH instantiation and any visibility method; we use the CHC++ occlusion culling method for its good general performance. Tiles are instantiated only when tested locally for visibility, thus avoiding the need for a preconstructed global structure for the complete world. Our approach can render large-scale, diversified virtual worlds with complex geometry, such as cities or forests, all at high performance and with a modest memory footprint.

I. INTRODUCTION

Many of today's interactive media outlets, such as video games, immerse users in large virtual worlds. These worlds tend to be diversified, complex, and very extensive. Procedural modeling and tiling sets can be used to create such large virtual worlds at reasonable costs, alleviating the tedious task of modeling them by hand (Figure 2).

Procedural modeling encompasses several kinds of automatic generation methods in order to model synthetic scenes. Some of these methods allow designers to create procedural geometry or textures. Tiling methods can serve as an alternative or supplemental solution to this design, where well-designed portions of a world (enclosed in 3D tiling volumes, as illustrated in Figure 1) are randomly, deterministically, or a combination of both, laid out to give the impression of variations and near-infinite extent.

Procedural generation of such extended scenes is often used as a preprocess with respect to the rendering or interactive walkthrough. By integrating rendering constraints, such as visibility computation, in a tiling-based scene generation process, we can ensure that the generation of only the information necessary for rendering the scene is provided, given a fixed performance budget. nor even generated. Moreover, no precomputed global data structures for the entire scene are necessary, thus avoiding extreme memory and processing requirements. Visibility computation, procedural generation of scenes, and tiling methods are well-studied topics in computer graphics (Section II). Building on these, our tiling creation process first computes a per-tile local visibility information using a fast instantiation of a bounding volume hierarchy (BVH; Section III-A) to bootstrap to the CHC++ algorithm. Global visibility computation relies on per-neighbor tile queries using view-frustum culling and GPU occlusion queries, effectively reducing some limitations of CHC++ and adding frame-to-frame temporal coherence to speed up the entire process (Section III-B). Popping artifacts resulting from variation over time and space of the occlusion queries, are efficiently avoided by our method (Section III-C). We analyze our performance on a set of typical procedurally generated scenes (Section IV) and discuss the benefits and limitations of our approach (Section V). Finally, we conclude and offer future perspectives (Section VI).

II. RELATED WORK

A. Visibility

Visibility determination remains one of the most challenging problems in computer graphics, particularly with respect to efficient rendering. For this reason, the literature on this topic is very extensive and we refer readers to surveys [START_REF] Cohen-Or | A Survey of Visibility for Walkthrough Applications[END_REF], [START_REF] Bittner | Visibility in Computer Graphics[END_REF] for a comprehensive review. We instead restrict ourselves to discussions on visibility (pre)computation methods for interactive rendering.

The two general families of methods used to efficiently display large and complex scenes are PVS and occlusion culling. By neglecting completely occluded objects, these methods can reduce the rendering load on both CPU and GPU.

The concept of PVS, introduced by Airey et al. [START_REF] Airey | Towards Image Realism with Interactive Update Rates in Complex Virtual Building Environments[END_REF], consists of determining all the polygons that can be potentially visible from a given convex region, called a view cell.

In order to increase PVS construction efficiency, an important step consists of computing the fusion of occluders and the aggregation of regions farther away from a view cell. Schaufler et al. [START_REF] Schaufler | Conservative Volumetric Visibility with Occluder Fusion[END_REF] use an octree to store opaque volumetric interiors (of city buildings in their application). By conservatively projecting the occluded regions through the octree, they efficiently classify regions as occluded for given view cells. Durand et al. [START_REF] Durand | Conservative Visibility Preprocessing Using Extended Projections[END_REF] also use the concept of occluder fusion and region aggregation in general 3D scenes, but reproject occluders on successive parallel planes instead. Both methods compute conservative PVS, but their respective preprocessing remains very compute-intensive, and their resulting PVS require large amounts of storage.

Several outdoor 3D worlds can be represented by heightfields. By limiting the maximal displacement speed of an observer in a 2.5D heightfield scene, Koltun et al. [START_REF] Koltun | Virtual Occluders: An Efficient Intermediate PVS Representation[END_REF] achieve interactive rendering with a PVS computed on the fly. Wonka et al. [START_REF] Wonka | Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs[END_REF] propose a conservative approach also limited to 2.5D, but instead supported by raycasting. Their method is very efficient compared to other geometrical approaches because of the discretization of the scene. It can compute a PVS in only a few seconds. Bittner et al. [START_REF] Bittner | Adaptive Global Visibility Sampling[END_REF] use sample rays across the scene to simultaneously compute the PVS for an entire set of view cells. Unfortunately this method requires large amounts of storage and cannot be used in a traditional rendering engine.

Occlusion culling consists of quickly testing if an object is occluded by another one, visible from the viewpoint. Occlusion queries and early-z rejection are commonly used for real-time occlusion culling methods.

Greene et al. [START_REF] Greene | Hierarchical Z-Buffer Visibility[END_REF] traverse an octree in a hierarchical Z-buffer software rasterizer for fast polygon visibility determination with both spatial and temporal coherence. Zhang et al. [START_REF] Zhang | Visibility Culling Using Hierarchical Occlusion Maps[END_REF] introduce a similar approach for visibility culling but instead with hierarchical occlusion maps, thus allowing image occluder fusion resulting in significant speedups for interactive walkthroughs.

Staneker et al. [START_REF] Staneker | Efficient Multiple Occlusion Queries for Scene Graph Systems[END_REF] use occupancy maps to allow scene graph rendering systems to perform efficient occlusion culling. They organize multiple occlusion queries by priority, even though a scene graph hierarchy is not as efficient as BVHs to perform front-to-back node traversal. They also use temporal coherence to fix a budget on the number of individual occupancy maps tests before GPU occlusion multi-queries. This allows for good spatial and temporal culling coherence if the scene graph remains unmodified.

Because of our use of CHC++, we describe it in more details here. Mattausch et al. [START_REF] Mattausch | CHC++: Coherent Hierarchical Culling Revisited[END_REF] present CHC++ using occlusion multi-queries on a BVH representation of the scene. Their algorithm handles millions of polygons while maintaining very high rendering framerates. The CHC++ algorithm recursively queries the BVH nodes to determine whether they are visible from the viewpoint. If a node is visible, CHC++ either displays its geometry if it is a leaf, or recursively traverses its children. If the node is not visible, the node and its subtree are culled. According to the node's polygon count and its spatial extent, it is sometimes preferable to render the entire subtree geometry rather than to determine which children nodes are visible or not. Moreover, the traversal cost, also related to the depth of a subtree, must be limited in order to get CHC++ to work efficiently without too much overhead. CHC++ efficiently exploits temporal coherence, and a node might be marked as visible for a bounded random number of frames. This alleviates the GPU load: the occlusion queries on the BVH nodes are thus spread out across several frames. Nevertheless, as in previous approaches, the scene must remain unmodified to benefit from temporal coherence. In this paper, we name CHC++ context the set of resources (query queues, BVH, etc.) used by CHC++ to compute occlusion culling.

Both PVS and occlusion culling methods significantly improve performance. However, for very large worlds, the preprocessing time for building the required data structures is often too long, and the scene must remain static. Moreover, the memory requirements for storing the PVS or the BVH become a limiting factor in real-world rendering engines. Finally, when dealing with interactively and procedurally generated very extended worlds, neither method is convenient due to their precomputation times and memory costs.

B. Procedural Modeling and Tiling

Tiling is often used in procedural modeling to ensure a virtual world's variability over large distances and scales [START_REF] Lagae | Tile-Based Methods for Interactive Applications[END_REF]. One compelling example was provided by Peytavie et al. [START_REF] Peytavie | Procedural Generation of Rock Piles Using Aperiodic Tiling[END_REF] with their aperiodic tiling set of corner cubes to generate piles of rocks structures for landscapes, stone huts, walls, etc.

Despite many existing procedural methods for objects and landscape generation, only a few consider positioning constraints on objects in the scene, and none consider guiding the scene generation with visibility, except for two methods. The first method, from Greuter et al. [START_REF] Greuter | Real-time Procedural Generation of 'Pseudo Infinite' Cities[END_REF], uses the view frustum to generate a procedural city, but without any other form of culling. The second, from Gomez et al. [START_REF] Gomez | Occlusion Tiling[END_REF], uses 2.5D visibility to precompute occluding tiles, ensuring a fixed PVS size. However this latter method is limited as scene designers cannot authorize long avenues, where visibility extends far away. In addition, the algorithmic complexity of the method does not scale well to fully 3D scenes.

III. VISIBILITY TILING

Tiling can efficiently generate large 3D worlds based on a set of predefined tiles. However, building a BVH for efficient occlusion culling on such an entire generated scene is impractical as the scene's size increases. Indeed, Figure 3 shows time and memory consumptions for BVH construction using all the objects of a tile-based world. Our method improves the performance of such world generation independently from the tile placement procedure. As such, we do not require the location of each tile to be explicitly stored, e.g., in a tile-instantiation map or by storing neighborhood information.

Our tiling scheme takes a predesigned set of tiles as input (Figure 1 top). These tiles are considered as axis-aligned boxes for simplicity, without loss of generality. In fact, these tiles have no restrictions on their shape. The geometry associated with each tile is defined inside a local scene graph of 3D objects instances freely arranged in the tile. To generate the 3D world, the tiles are instantiated in 3D space, on a 2D surface for our test scenes, to form the final world geometry (Figure 1 bottom), depending on whether they may be visible from the viewpoint according to a two-level occlusion culling algorithm. The first level applies hardware occlusion queries on the tiles' common bounding box, i.e., the union of each individual tile's bounding box (Figure 4) to allow for long-range visibility determination. The second level uses Mattausch et al.'s CHC++ algorithm [START_REF] Mattausch | CHC++: Coherent Hierarchical Culling Revisited[END_REF] to determine the local occlusion within each visible tile.

When the extent of the scene is very large, for instance for an entire virtual world, even with instantiated BVHs, the time and memory necessary to build a hierarchical structure, as well as the increased cost of traversing this hierarchy for occlusion queries, can become major bottlenecks. Our grid-based front-to-back tile visibility algorithm avoids such difficulties by expanding locally the number of queried tiles without the need to store them in any hierarchical structure.

We first construct a per-tile bounding box and a BVH from the local scene graph associated with the distribution of objects in the tile. The bounding boxes of all tiles in a tiling set are then combined to define the common bounding box of the tiling set (Section III-A). This common bounding box is used to avoid popping artifacts (Section III-C). Using this information, the tiling is generated on the fly, by propagating the visibility from the viewpoint over the tiling until each line of sight is blocked, using our two-level occlusion culling algorithm (Section III-B).

A. Tiling Set Representation

In order to limit memory usage for a large 3D world our method employs object instantiation, represented efficiently with a scene graph. Each tile has its own scene graph and may share objects with other tiles. From this per-tile scene graph (Figure 5 order to compute efficient occlusion queries. Each BVH node contains references to the corresponding scene graph instantiation nodes, but not to the geometry itself. Each BVH is built using the binned SAH heuristic [START_REF] Macdonald | Heuristics for Ray Tracing Using Space Subdivision[END_REF], [START_REF] Havran | Heuristic Ray Shooting Algorithms[END_REF]. The recursive BVH construction stops when there is only one object referenced in a leaf node, or when either a maximum depth or a minimum number of triangles per leaf is reached (Figure 5 right). Having a BVH for each tile is important for interactivity and computational efficiency. If a tile contains animated geometries, only its tile's BVH must be recomputed at each frame, which can be done quickly. Animated geometries could also be handled in a separate per-tile BVH, or in a global BVH for the entire world as in traditional implementations.

The BVH's root node defines the tile's bounding box. From each tile bounding box, we compute the tiling set common bounding box, which is unique for the entire tiling set. This bounding box, computed as the union of every tile's bounding box as shown in Figure 4, allows for conservative occlusion determination, independently of the tile, during the tiling process.

B. Visibility Propagation with Tile Queries

For each frame, visibility is computed from the viewpoint and the tiling process propagates visibility from the nearest visible tile to adjacent tiles, and so on, in front-to-back order. The nearest visible tile is found with a search in the tiling domain. The tiling process uses the tiling common bounding box to determine if a tile instance must be rendered or if visibility propagation should stop (Figure 6). We call this step the "tile query". If the tile has to be instantiated, the tiling process selects the associated tile from the set of predesigned tiles. For this selection, we use a function that returns the selected tile from its world position, thus avoiding explicit storage of every instantiated tile position; this is particularly important for scalability to large worlds. • current tile T • pending query queue Q Output:

• pending query queue Q // query neighbor tiles of T

1 foreach neighbor n of T do 2 if ¬ queriedForThisFrame(n) then 3 if intersectsViewFrustum(n) then // asynchronous query launch 4 q ← query(commonBboxAtOffset(n)) 5 append(Q,(q,n)) 6 end 7 setQueriedForThisFrame(n) 8 end 9 end
Algorithm 2: queryNeighbors(T ,Q)

In the remainder of this section, we describe the algorithms used by our visibility propagation algorithm. The instructions written in blue are related to temporal visibility prediction. They could be neglected if temporal coherence is not exploited.

The main rendering steps are detailed in Algorithm 1. Starting from the nearest visible tile, the corresponding BVH is instantiated if it has not yet been. The BVH instance is created such that each node can determine its own visibility status (like with CHC++) when rendered with local occlusion culling. When a BVH node is marked as visible, we add the corresponding scene graph nodes instances to the rendering, if they were not already added for the current frame (Figure 5). When the current tile geometry has been rendered with local occlusion culling using CHC++, farther neighboring tiles are queried for visibility (Algorithm 2) using the same common bounding box that is offset at the queried tile position. To benefit from the front-to-back generation of the world and increase the efficiency of our occlusion culling method, tile queries are stored in a queue Q because hardware query specifications guarantee that occlusion queries results are returned in order.

In Algorithm 3, we send visible tiles to the renderer and predict their visibility for the next frame. If the result of a query is not readily available, we use temporal coherence (line 3): if it was visible in the previous frame, we postpone the query result processing until the end of the current frame (postponed query queue P) and send the tile for rendering. As most of these query results will be available at the end of the frame, the correct visibility status will be determined before the next frame.

Input:

• pending query queue Q • postponed query queue P Output:

• pending query queue Q • postponed query queue P • neighbor to render n // retrieve first available AND positive query result Input:

1 while ¬ empty(Q) do 2 (q,n) ← pop(Q) 3 if ¬ isResultAvailable(q) ∧ wasVisibleAtPreviousFrame(n) then //
• postponed query queue P 1 // get visibility result for next frame 2 while ¬ empty(P) do 3 (q,n) ← pop(P) // next frame visibility prediction Due to our front-to-back tiling traversal, the first queries in the query queue Q, that correspond to tiles close to the viewer, are more likely to be predicted as visible, and thus, have their result postponed. Most of the following query results from the query queue will then be available, as queries are launched according to increasing distance from the viewer using a neighborhood relationship. Line 7 of Algorithm 3 is executed when a tile becomes newly visible. This affects the framerate when the number of such tiles is large but the time spent to wait could be used to preinstantiate the remaining tiles in the pending query queue.

4 if isResultAvailable(q) ∧ isResultPositive(q)
At the end of the main algorithm, we check if the results of all the postponed queries have become available, and update prediction for the next frame (Algorithm 4). At line 4 of Algorithm 4, tile query results that are not available at this moment are those from tiles that are far away from the viewpoint. Predicting these tiles as not visible will force Algorithm 3 to wait at line 7 for the query result retrieval but, as they are far and have a small footprint on screenspace, this cost should be small. We also noticed that the number of such tiles is small: as shown experimentally in our test scenes, the number of queries failing in temporal prediction are only 0.02% (City), 0.04% (Hybrid scene), and 0.14% (Forest) of the total number of queries. Figure 7: The common bounding box, rather than the tile's bounding box, ensures the correctness during visibility propagation. The query of Tile 2 will return visible, and therefore Tile 3 will be queried for visibility and will not suddenly appear when passing through Tile 1 or when the observer's height increases.

Temporal coherence results in a significant speed-up in terms of framerate. Since queries are performed in a front-toback order, most of the queries for which results are not yet available are those from tiles that are closer to the viewpoint. As such, most of these tiles were already visible in the previous frame and were therefore predicted to be visible at the current frame.

When a tile instance is marked as visible for the first time, the corresponding BVH instance is kept in a cache to manage its own CHC++ context. Tile query temporal coherence is independent and complementary to CHC++'s own temporal coherence. We keep instantiated tiles in the cache for the subsequent frames, so that we preserve the CHC++ temporal coherence and avoid instantiation overheads from one frame to another. When a tile is not visible for a specified duration, we remove it from the cache, reducing memory usage.

C. Avoiding Popping Artifacts

Using simply tiles' bounding boxes and direct neighborhood to propagate visibility across the tiling is not sufficient to ensure that a closer tile completely occludes a farther one. Figure 7 shows an example in which such a simple algorithm would fail in determining potentially visible geometry located farther away from the maximal extent of the instantiated tiling. Using the common bounding box for the tile queries overcomes this problem. As every queried bounding box has the same size, as soon as a query result is negative, we know that farther tiles will not be visible from any viewpoint, i.e., inside or outside of the tiling. Therefore, querying farther neighbor tiles for occlusion will not be necessary and visibility propagation can stop.

IV. RESULTS AND PERFORMANCE ANALYSIS

We tested our algorithm on different tiling sets composed of houses and trees, as shown in Figure 2. The geometries come from turbosquid [START_REF]3D Models, Textures and Plugins at TurboSquid[END_REF]. Each tile holds between 16K and 2.5M polygons divided among all the 3D objects in the tile. No levels of detail (LODs) are used on these objects, such that the entire geometries are rendered when declared visible. Computations are performed on an Intel Core i7 with a GeForce GTX 680. The BVH of each tile is constructed with the embree parallel implementation of BVH builder [START_REF] Woop | Embree -Photo-Realistic Ray Tracing Kernels[END_REF], using a spatial split heuristic. The BVH construction times, depths, and memory for the tiling sets precomputations are given in Table I.

In the accompanying video, we show three walkthroughs within three tilings, each one set up with a different tiling set. We compare four culling algorithms: tile query + CHC++, tile query alone, per-tile CHC++, and view frustum only. The tile query algorithm alone systematically renders the entire geometry of each visible tile instead of rendering it with CHC++. A direct comparison between our method and the CHC++ algorithm cannot be done since, as said in Section III, building the entire BVH of our very extended scenes is impractical. But in order to show the benefits of our method in a fairer way, we compare it with a per-tile CHC++ algorithm in which we consider, for each frame, each tile BVH within the conservative bounding box of the tiles instantiated using the tile query propagation method (preserving CHC++ temporal coherence). We use the same a priori information for the view frustum culling algorithm alone. In fact, per-tile CHC++ and view frustum culling alone are favored in our implementation in regard to a possible naive implementation. Figures 8 and9 show the framerates and the numbers of rendered triangles for these walkthroughs.

As we previously mentioned, it is sometimes preferable to render the entire geometry contained in a tile rather than determining its occlusion status. As well, we can see that using the tile query algorithm alone performs sometimes slightly better than using it in conjunction with CHC++ in the City and the Hybrid scenes, where the scenes are not very complex and produce much occlusion (Figures 8a and8b). Occasionally, the tile query algorithm even performs twice as better, as shown between frames 2100 and 2200 of the City. But tile query alone induces more variance in the framerate.

We can see that for most viewpoints, our algorithm in conjunction with CHC++ keeps better framerates than pertile CHC++ (Figure 8). This is easily explained by the fact that CHC++ does not handle visibility information or temporal coherence on neighboring tiles, and thus more tiles are instantiated in the tiling, and more time is spent to resolve individual tile queries. The Forest walkthrough is the one for which our hybrid algorithm performs the best in aggregating the occlusion of several tiles (Figure 8c). In each of the three scene walkthroughs, the framerates decrease a lot when the observer's location is high above the ground, looking at the tiling at grazing angles, resulting in many visible tiles thus being instantiated. This slowdown could be reduced using coarser geometry for distant instantiated tiles (LODs), but we decided to leave this for future investigations.

In terms of rendered triangles (Figure 9), our algorithm performs as well as per-tile CHC++, i.e., tile query associ-ated with CHC++ is as much conservative as per-tile CHC++ is in terms of occlusion.

V. DISCUSSION

As explained in Section III-C, using a common bounding box ensures that no popping artifacts occur. But this can affect the framerate in the cases of an overestimation of the visibility of a tile. If the bounding box of a particular tile is small with respect to the common bounding box, this tile will be often marked as visible even if it is not the case. Then, the instantiation and the rendering of the tile using CHC++ will introduce unnecessary computational costs.

As with every occlusion culling method, the efficiency of our algorithm greatly depends on the occlusion in the scene. In our case, as occlusion culling is performed on the tiles, the efficiency depends on the occlusion of each tile. If the tiles do not contain enough occluding geometry, the tiling process will propagate the visibility to many tiles.

As with CHC++, temporal coherence can be increased so that when a tile is marked as visible, we can set it as visible for a random number of subsequent frames, resulting in fewer queries spread over time. We can also use the front-toback order to decrease the frequency of closer tiles' queries. In our test scenes this did not result in significant speed-up, because our tiles generate enough occlusion.

In our algorithm, the geometry of an instantiated object is completely rendered once determined visible. If this geometry is complex, an efficient LOD system would allow to decrease the number of rendered polygons for farther tiles and improve overall performance.

VI. CONCLUSION AND FUTURE WORK

In this paper, we associate visibility and tiling. Within this context, we propose a solution for occlusion culling in 3D worlds generated on the fly. This allows for real-time occlusion culling and low memory BVH instantiation for extended worlds. In our method, tiles are instantiated on a 2D surface but could also be instantiated in 3D. Simply put, only the neighborhood relationship would have to be extended to 3D.

Although BVH computation might not always be achieved on the fly, it is still feasible for reasonable numbers of polygons per tile and depths of the computed BVH. In a multithreaded implementation, a tile BVH could be prefetched in a separate thread, when a neighboring tile is queried, so that such a tiling process could even create the geometry in the tile itself, while instantiating it. Thus, the tiling set would not need to contain predesigned tiles if they do not exceed a given number of polygons, depending of the rendering performance.

Repositioning of procedural geometry according to visibility analysis could also emerge from our structures in order to limit visibility propagation. As a result, level designers could exploit such tools for the fast creation of huge worlds. Moreover, using this method could alleviate the whole PVS construction cost induced by the number of polygons, by dividing it into small computation steps. Finally, we decided to use the CHC++ algorithm, but in fact, this local occlusion culling step could be replaced by any other conservative, exact, or sampling visibility determination method.

For even better occlusion culling, and therefore better rendering framerates, our method can be used in conjunction with hierarchical Z-buffer [START_REF] Greene | Hierarchical Z-Buffer Visibility[END_REF] or occupancy maps [START_REF] Staneker | Efficient Multiple Occlusion Queries for Scene Graph Systems[END_REF]. The latter one would use directly the BVH nodes instead of the scene graph nodes to test and update the occupancy map.

We also would like to develop a hierarchical version of this method : visibility would be propagated very quickly over large distances at the top level of the hierarchy.

Figure 2 :

 2 Figure 2: Three tiled scenes generated from three different tiling sets. Our tiling creation process integrates visibility propagation in the construction of tileable 3D worlds allowing for much more interactive rendering. Mountains in the background come from the skybox.

Figure 3 :

 3 Figure 3: Time and memory measured for the naive building of the BVH of a tiled world. Our method avoids these costs with a low preconstruction time on each tile BVH.

Figure 4 :

 4 Figure 4: A 2D tiling set consisting of three tiles: their bounding boxes (green, red, orange) are computed with respect to all the tile's objects. Their union, the common bounding box (purple), is the one used for tile occlusion queries.

Figure 5 :

 5 Figure 5: Left : The structure of a scene graph used for instantiation. The numbered nodes correspond to scene graph instances. Right : The BVH structure built for a tile (in red). Each node keeps references to the corresponding instantiation scene graph nodes it belongs to.

Figure 6 :

 6 Figure 6: 2D tiling process within the view frustum. Visibility is propagated from the nearest visible tile (yellow). Tiles are shown in light blue if query result is positive, in dark blue if it is negative.

Figure 8 :

 8 Figure 8: The FPS for the three different walkthroughs in the three different scenes (higher is better).

Figure 9 :

 9 Figure 9: The rendered triangles for the three different walkthroughs (lower is better). Blue and yellow curves overlap.

  postpone query result retrieval

	4	append(P,(q,n))
	5	return n // send to rendering
	6	else
	7	waitQueryResult(q)
	8	// next frame visibility prediction
	9	if isResultPositive(q) then
	10	setVisible(n)
	11	return n // send to rendering
	12	else
	13	setNotVisible(n)
	14	end
	15	end
	16 end
	17 return ∅ // no neighbor to render
	Algorithm 3: getNextPositiveQuery(Q,P)

Table I :

 I BVH construction statistics for the tiles of the three test scenes.

	Tile ID	time (ms)	City depth size (MB)	# polys	time (ms)	Hybrid scene depth size (MB)	# polys	Forest time (ms) depth size (MB)	# polys
	Tile 0	184	16	24.6	0.768M	251	16	46.6	1.100M	453	16	61.2	2.41M
	Tile 1	132	16	27.1	0.728M	181	16	35.9	0.934M	484	16	67.8	2.31M
	Tile 2	103	16	20.9	0.580M	391	16	54.9	2.129M	472	16	66.6	2.48M
	Tile 3	85	16	16.7	0.474M	184	16	34.0	0.967M	431	16	59.8	1.98M
	Tile 4	85	16	16.1	0.674M	114	16	26.8	0.543M	215	16	47.1	1.03M
	Tile 5	117	16	21.2	0.363M	125	16	30.3	0.607M	217	16	44.2	1.06M
	Tile 6	67	16	15.8	0.276M	45	16	11.2	0.174M	278	16	55.5	1.42M
	Tile 7	61	16	14.9	0.580M	96	16	23.8	0.445M	283	16	54.5	1.41M
	Tile 8	104	16	19.9	0.050M	192	16	42.2	0.908M	121	16	30.3	0.47M
	Tile 9	81	16	15.6	0.459M	111	16	27.6	0.528M	99	16	25.3	0.42M
	Tile 10	106	16	27.8	0.562M	10	13	1.3	0.024M
	Tile 11	72	16	18.3	0.365M	164	16	32.8	0.838M
	Tile 12	58	16	12.0	0.313M	74	16	19.9	0.316M
	Tile 13	90	16	18.0	0.494M	184	16	37.7	0.935M
	Tile 14	70	16	14.8	0.369M	94	16	22.5	0.462M
	Tile 15	84	16	18.6	0.472M
	Tile 16	102	16	22.4	0.565M
	Tile 17	57	16	14.9	0.275M
	Tile 18	86	16	19.2	0.472M
	Tile 19	58	16	17.0	0.275M

ACKNOWLEDGEMENTS

The authors thank the anonymous reviewers for their constructive comments. They acknowledge financial support in Canada from GRAND.