Sylvain Lazard
email: lazard@loria.fr

Christophe Weibel
email: weibel@math.mcgill.ca

Sue Whitesides

Linqiao Zhang
email: lzhang15@cs.mcgill.ca

On the Computation of the 3D Visibility Skeleton

The 3D visibility skeleton is a data structure that encodes the global visibility information of a set of 3D objects. While it is useful in answering global visibility queries, its large size often limits its practical use. In this paper, we address this issue by proposing a subset of the visibility skeleton, which is about 25% to 50% of the whole set. We show that the rest of the data structure can be recovered from the subset as needed, partially or completely. Our recovery method is efficient in the sense that it is output-dependent. We also prove that this subset is minimal for the complexity of our recovery method.

Introduction

Problems of 3D visibility arise commonly in areas such as computer graphics, computer vision, and robotics. Typical problems include determining the objects in a scene that are visible from a given view point, computing pairwise visibility information among objects, and computing the boundaries of umbra and penumbra cast by objects under various lighting conditions. 1 These visibility problems can roughly be classsified into point-based or surface-based, depending on the nature of the view points or light source.

Point-based visibility problems have been well studied and understood. On the other hand, little is known about surface-based visibility problems. A common approach in practice is to discretize such problems, transforming them into a set of point-based problems, so as to obtain approximate solutions, which is often unsatisfying and time consuming. A method for providing analytical solutions to surface-based visibility problems would be desirable.

The visibility complex is a data structure that is designed to encode global visibility information. This data structure partitions the space of line segments into sets of components, where each component consists of a set of maximal free line segments that share the same occluders, are tangent to the same objects in the scene, and form one connected component. This data structure was initially proposed in 2D by Pocchiola and Vegter [START_REF] Pocchiola | The visibility complex[END_REF]. Durand et al. extended the visibility complex data structure to 3D and furthermore introduced the 3D visibility skeleton, which essentially consists of the 0D and 1D cells of the visibility complex [START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF][START_REF] Durand | The 3D visibility complex[END_REF], together with their adjacencies. Thus the 3D visibility skeleton is a simpler, smaller data structure than the full visibility complex. It has the structure of a graph, where vertices represent 0D cells and arcs represent 1D cells. The visibility skeleton has been applied to global illumination computation [START_REF] Duguet | Robust epsilon visibility[END_REF][START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF][START_REF] Durand | Fast and accurate hierarchical radiosity using global visibility[END_REF], and has resulted in images with high quality shadow boundaries. On the other hand, the applications of [START_REF] Duguet | Robust epsilon visibility[END_REF][START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF][START_REF] Durand | Fast and accurate hierarchical radiosity using global visibility[END_REF]] also show that this data structure, although simplified, can still be enormous and thus has limited practical use.

Various other definitions have been proposed for the 3D visibility skeleton [START_REF] Demouth | Topological changes in the apparent contour of convex sets[END_REF][START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF][START_REF] Koenderink | The singularities of the visual mapping[END_REF], depending on the notion of visual events, which are based on the context (e.g. smooth manifolds, polyhedral scenes) and the intended use of the data structure (e.g. shadow boundary computation). In this article, we refer to a visibility skeleton based on visual events surfaces for a polytope scene, as defined in Demouth et al [START_REF] Demouth | Événements visuels et limites d'ombres[END_REF][START_REF] Demouth | Computing direct shadows cast by convex polyhedra[END_REF].

A visibility skeleton thus defined, when considering input consisting of a set of convex disjoint polytopes, consists of arcs of so-called type EEE, and a subset of arcs of so-called type VE, and vertices of so-called types EEEE, VEE, FEE, and a subset of vertices of so-called type VV (see Figures 1 and2). For instance, a vertex of type EEEE represents a maximal free line segment that is tangent to four polytopes along four of their edges, and similarly for the other types. Here, the lines supporting the maximal free line segments are required to be tangent to their associated polytopes. Moreover, we only consider among the VV vertices those that correspond to maximal free line segments that lie in some plane tangent to both associated polytopes. This data structure is only a subset of the 3D visibility skeleton defined by Durand et al. [START_REF] Durand | Visibilité tridimensionnelle : étude analytique et applications[END_REF][START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF], which consists of arcs Figure 3. Scene representing a box in a room with a rectangular light source on the ceiling. The black and white regions represent the umbra and unshaded regions. The union of the light and dark grey regions corresponds to the penumbra. The dark gray shape represents a portion of the penumbra limited by the trace of FE arcs. In this region, the visible portion of the light source does not exceed about 40%. The schema on the right represents a section through the middle of the scene. The points a are at the boundary of umbra, and the points c are at the boundary of the unshaded region. The points b are on the maximal free line segments corresponding to an arc FE involving a face of the blocker. From a to b, the percentage of the light source that is visible increases linearly from 0% to about 40%, and from b to c, it increases linearly from about 40% to 100%. Since the light grey region can be made arbitrarily large by moving the light source closer to the blocker, the trace of the FE arcs on the floor corresponds to a discontinuity of the derivative in the percentage of visible area of the light source.

of type EEE, VE and FE, and vertices of types EEEE, VEE, FEE, VV, FvE, FF, FE and FVV. 2For convenience, in this paper, we refer to the former definition as a succinct 3D visibility skeleton, and to the latter one as a full 3D visibility skeleton. Moreover, we define the vertices contained in the succinct skeleton to be primary vertices, and the remaining vertices of the full skeleton to be secondary vertices.

From the study of Demouth et al., the size of the succinct 3D visibility skeleton is only about 25% to 50% of the full one [START_REF] Demouth | Événements visuels et limites d'ombres[END_REF][START_REF] Demouth | Computing direct shadows cast by convex polyhedra[END_REF]. However, the skeleton vertices and arcs it contains are sufficient to compute the direct shadow boundaries cast by polytopes. While compact and useful on its own, the succinct 3D visibility skeleton does not always contain the necessary visibility information for answering global visibility queries. For example, when generating high quality shadows, the typical approach of linearly interpolating light intensity within the penumbrae [START_REF] Akenine-Möller | Approximate soft shadows on arbitrary surfaces using penumbra wedges[END_REF][START_REF] Hasenfratz | A survey of real-time soft shadows algorithms[END_REF][START_REF] Parker | Single sample soft shadows[END_REF] is not always sufficient to express the subtlety of penumbrae cast by polytope features, as shown in Figure 3; in particular, arcs FE may be needed even though they do not correspond to visual events. Apart from global illumination, other problems such as visibility culling [START_REF] Wonka | Visibility preprocessing with occluder fusion for urban walkthroughs[END_REF], architectural acoustics [START_REF] Funkhouser | A beam tracing method for interactive architectural acoustics[END_REF], or endoscopy [START_REF] He | Reliable path for virtual endoscopy: ensuring complete examination of human organs[END_REF] also need global visibility information.

The full visibility skeleton, on the other hand, contains all the necessary information for most visibility queries. However its large size has been seen as an impediment for its practical use [START_REF] Durand | Visibilité tridimensionnelle : étude analytique et applications[END_REF][START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF]. In this paper, we study in detail the 3D visibility skeletons computed from a set of convex disjoint polytopes in general position (defined in Section 2). We prove that knowing the succinct 3D visibility skeleton is sufficient to compute efficiently the secondary vertices; in particular, these computations can be local, that is, only the vertices and arcs of interest need to be computed. Furthermore, the full skeleton can be computed if necessary.

In terms of computing the full skeleton, we prove that, given k disjoint convex polytopes 3satisfying general position assumptions, with n edges in total, the full visibility skeleton can be computed from the succinct one in O(p log p + s log s) time, where p is the number of the primary vertices minus the EEEE vertices, and s is the number of secondary vertices. The worst-case size complexity of the primary vertices of interest to us, EEEE vertices excluded, is Θ(n 2 k), and the worst-case size complexity of the secondary vertices is Θ(n 2 ) [START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF]. Thus, in the worst case,

O(p log p + s log s) is equivalent to O(n 2 k log n).
There exist various algorithms for computing the secondary vertices. For instance one can use the sweep algorithm described in [START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF][START_REF] Goaoc | Structures de visibilité globales : tailles, calculs et dégénérescences[END_REF], or one can also compute, in a brute force way, the possibly occluded candidate secondary vertices and perform ray shooting to check for occlusion [START_REF] Agarwal | Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions[END_REF][START_REF] Dobkin | Determining the separation of preprocessed polyhedra: a unified approach[END_REF][START_REF] Pellegrini | Ray shooting on triangles in 3-space[END_REF]. To our knowledge, the best worst-case running time is O(n 2 k log n), obtained by computing O(n 2 ) candidate secondary vertices in a brute force way and checking for occlusion using the Dobkin-Kirkpatrick hierarchical representation [START_REF] Dobkin | Determining the separation of preprocessed polyhedra: a unified approach[END_REF][START_REF] O'rourke | Computational Geometry in C[END_REF], which leads to performing O(n 2 ) ray shooting queries on each of the k polytopes in O(log n) time each. Comparatively, the method we propose has the same complexity in the worst case. However, our method is output-dependent, and thus, it can be much more efficient than previously existing algorithms. In addition, our method takes as input the primary vertices, whose observed size is, in a random setting, Ck √ nk for a small constant C (see [START_REF] Zhang | On the size of the 3D visibility skeleton: experimental results[END_REF]), which is much smaller than the worst-case size, that is Θ(n 2 k).

The rest of this paper is organized as follows. We provide necessary definitions in the next section. We then introduce the computational relations among the types of visibility skeleton vertices in Section 3. We prove that we can recover the full skeleton from the succinct one in O(p log p + s log s) time in Section 4. By a series of examples, we show in Section 5 that none of the primary vertex types can be omitted while maintaining the validity of this result. We finally conclude in Section 6.

Preliminaries

We introduce the basic definitions we need in this section. We start with some preliminary definitions in order to explain the types of vertices and arcs of the 3D visibility skeleton of a set of k convex disjoint polytopes in general position. By general position, we mean that no edges of different polytopes are parallel, no four points on more than one polytope are coplanar, no line is tangent to more than four polytopes, and no four edges are on a hyperboloid quadratic surface [START_REF] Brönnimann | Transversals to line segments in three-dimensional space[END_REF].

A support vertex of a line is a polytope vertex that lies on the line. A support edge of a line is a polytope edge that intersects the line but has no endpoint on it (a support edge intersects the line at only one point of its relative interior). A support of a line is one of its support vertices or support edges. A maximal free line segment is a maximal subset of a line that does not intersect the interior of any polytope. The supports of a segment are defined to be the supports of the relative interior of the segment; thus if a maximal free line segment ends at a vertex of a polytope, this vertex is not a support. A support polytope of a line is a polytope that a support of the line lies on.

Full 3D visibility skeleton. We introduce this data structure based on the work of Durand et al. [START_REF] Durand | Visibilité tridimensionnelle : étude analytique et applications[END_REF][START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF], and often refer it as the full skeleton. The 3D visibility skeleton is a graph that consists of vertices and arcs. A skeleton vertex is a point in the space of maximal free line segments, and a skeleton arc is a connected sequence of points in the same space, with a skeleton vertex at each extremity. (See Figure 1 and 2 for graphical illustrations, and [START_REF] Durand | Visibilité tridimensionnelle : étude analytique et applications[END_REF][START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF] for more details).

Full 3D visibility skeleton vertices. There are eight types of skeleton vertices, shown in Figure 1. Note that unless stated otherwise, no two supports come from the same polytope. A skeleton vertex has type EEEE if its set of supports consists of four edges; VEE if its set of supports consists of a vertex and two edges; FEE if its set of supports consists of two edges on one face, and two additional edges; VV if its set of supports consists of two vertices; FF if its set of supports consists of two edges on one face, and two edges on another face; FvE if its set of supports consists of a vertex and an edge on one face, and an edge; FE if its set of supports consists of two adjacent vertices of the same polytope; and FVV if its set of supports consists of two non-adjacent vertices on the same face of a polytope. We also consider a special case of FvE vertex called an extremal FvE vertex, as shown in Figure 4. An extremal FvE vertex is also in the plane containing a face incident to the polytope vertex, but does not intersect that face except on the vertex. Note that our definition is consistent with the discussion in [16, § 5.2.1], which shows that without the extremal FvE vertex, some arcs are missing end vertices. The set of supports of extremal FvE vertex consists of a vertex and only one additional edge on a different polytope, in contrast, a non-extremal FvE vertex has one more support edge.

We note that with these definitions, all skeleton arcs have a skeleton vertex at both ends.

It should be stressed that the maximal free line segment corresponding to a skeleton vertex is tangent to all its support polytopes.

Full 3D visibility skeleton arcs. There are four types of skeleton arcs. We define them, based on [START_REF] Durand | Visibilité tridimensionnelle : étude analytique et applications[END_REF][START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF], as follows, and show graphical illustrations in Figure 2. Note that unless stated otherwise, no two supports will come from the same polytope. An arc has type: EEE if its set of supports consists of three edges; VE if its set of supports consists of a vertex and an edge; FE if its set of supports consists of two edges on one face, and one additional edge; FVE if its set of supports consists of one vertex and one edge on the same face which is not incident to the vertex.

Again, we emphasize that the maximal free line segments corresponding to a skeleton arc are tangent to all their support polytopes. Succinct 3D visibility skeleton, primary and secondary vertices. We define the primary vertices to be the skeleton vertices of types EEEE, VEE, FEE, together with the vertices of type VV whose corresponding maximal free line segment lies in a plane tangent to both polytopes; and the secondary vertices to be the remaining vertices of type VV, and the vertices of types FF, FvE, FE, and FVV.

The succinct 3D visiblity skeleton is the subgraph of the full 3D visibility skeleton that contains only primary vertices, and skeleton arcs connecting two primary vertices.

Constraints. Recall that for any skeleton vertex, a support vertex is a polytope vertex that lies on the relative interior of the maximal free line segment, and a support edge is a polytope edge that intersects the maximal free line segment in both their relative interiors. For any skeleton vertex, we define its constraints to be the polytope edges that intersect the maximal free line segment corresponding to the skeleton vertex, and such that the plane containing the edge and the maximal free line segment is tangent to the polytope containing the edge. In other words, the maximal free line segment corresponding to the skeleton vertex can be perturbed so that it intersects the interior of the poytope edge, while remaining tangent to the polytope. We define constraints similarly for arcs. We note that any support edge is a contraint, and that any support vertex is incident to at least two constraints that are not support edges (in the case of extremal FvE vertices, there are at least three constraints, and possibly four). A constraint edge which is not a support edge is called a salient edge. We note that any skeleton vertex has, under our general position assumption, at least four constraints, and up to seven in some cases. Any skeleton arc has three.

Remark 1. By continuity, the constraints of an arc are all constraints of its end vertices.

Computational Relations among the Visibility Skeleton Vertices

Recall from Section 2 that a 3D visibility skeleton vertex corresponds to a maximal free line segment that has 0-degrees of freedom, subject to the condition that the maximal free line segment keeps the same constraints.

Remark 2. We specify that the knowledge of a skeleton vertex includes its corresponding maximal free line segment and its constraint edges, that is, any support polytope edges, any support polytope vertices with incident salient edges, and all support polytopes. The knowledge of a polytope includes cyclic orderings of edges around vertices and faces. Computing a skeleton vertex includes computing the maximal free line segment and all these constraint edges, and similarly for skeleton arcs.

Furthermore, we create during preprocessing a binary search data structure on the cyclic orderings of edges around each polytope vertex and face. This is done in O(n log n), where n is the number of polytope edges in the scene.

Note that, by Remark 1, and since a skeleton vertex includes the knowledge of its constraint edges, we can determine all skeleton arcs that are incident to a skeleton vertex by removing, in turn, each edge from the list of its constraints. Moreover, the computation time is constant.

Given a skeleton arc, which includes the knowledge of its constraints and support polytopes, any incident skeleton vertex can be computed without additional knowledge, provided that the skeleton vertex has the same set of support polytopes as the skeleton arc. The computation involves searching edges incident to a polytope vertex to find salient edges, or edges on a polytope face to find the support edges of the incident skeleton vertex. Thanks to the binary search data structure of Remark 2, this requires only O(log δ) time computation, where δ is the maximum degree of a polytope vertex or number of edges on a polytope face. For example, given an EEE arc, one can compute the vertices of types VEE and FEE that are incident to the EEE arc in O(log δ) time. But, if an EEE arc is incident to an EEEE vertex, then this EEEE vertex can not be computed directly from the EEE arc, since the EEEE vertex has an additional, unknown support polytope.

The possible computational relations among skeleton vertex types are summarized in the diagram in Figure 5. The edges in this diagram give all possible pairs of vertex types that can be connected by an arc of the full visibility skeleton. Furthermore, an arrow oriented from one vertex type to another indicates that the set of support polytopes of a vertex of the former type contains that of a vertex of the latter type. This means that vertices of the latter type can be computed from adjacent vertices of the former type in O(log δ) time. Note that skeleton vertices of types appearing in rows 1 through 4 of the diagram in Figure 5 are supported by 1, . . . , 4 polytopes, respectively.

We prove the correctness of the computational relations illustrated in the diagram of Figure 5 in Lemmas 3 and 4 below. Lemma 3. Let X and Y denote vertex types in the full skeleton graph, such that in Figure 5, X has more support polytopes than Y (so X appears in a higher row than Y), and there is an edge directed from X to Y. Then we cannot, from a skeleton vertex of type Y, determine an adjacent skeleton vertex of type X in time independent of the number of input polytopes, without more knowledge than specified in Remark 2. Proof. Since any vertex of type X has more support polytopes than any vertex of type Y, when computing an incident vertex from the arc that is created by a vertex of type Y, the additional support polytope, and furthermore the additional support edge (or support vertex) on the additional support polytope, is unknown. This requires a search for the additional polytope and the additional support edge (or support vertex) on the polytope. In general, this search cannot be done directly from a vertex of type Y, given only the knowledge of its supports. Lemma 4. If a scene is in general position, then from any skeleton vertex, it is possible to compute each adjacent skeleton vertex in O(log δ) time, where δ is the maximum degree of a polytope vertex or number of edges on a polytope face, provided that all support polytopes of the adjacent skeleton vertex are also support polytopes of the given skeleton vertex and of the connecting skeleton arc.

This lemma simply states that from a skeleton vertex, we can find incident skeleton arcs, and then skeleton vertices at the other extremity of the arcs. The O(log δ) factor is required to find adjacency relations. Note that the support polytopes of the adjacent vertices should also be suport polytopes of the connection arc in order to allow us to use the adjacency information of the supports. The details of the proof are in Appendix A.

In summary, for any directed edge in Figure 5 from type X to type Y, Lemma 4 shows that it is possible to compute a vertex of type Y from an adjacent vertex of type X ; Lemma 3 shows that it is impossible to compute a vertex of type X from a vertex of type Y efficiently, that is, in time independent of the number of polytopes.

Recovery of the Full Skeleton

We show in this Section that the full visibility skeleton can be recovered from the succinct one in O(p log p + s log s) time, where p is the number of primary vertices minus the EEEE vertices, and s is the number of secondary vertices.

Recall that the five types of secondary vertices are FF, FvE, FVV, FE, and a subset of VV. The vertices of type FVV and FE are easy to find on their own, and can be computed separately (see Remark 10). In this section, we show how to compute vertices of type FvE, FF, and the subset of VV that belongs to the secondary vertices. For this, we explore the subgraph of the full visibility skeleton consisting of VE and FE arcs and their incident vertices, that is, the VEE, FEE, VV, FvE and FF vertices. We call this subgraph the partial graph.

We first prove that all connected components of the partial graph contain at least a primary vertex of type VV, VEE or FEE. This allows us to find all FvE, FF and the remaining VV vertices by simple graph exploration, examining vertices adjacent to those we have already computed.

To prove that all connected components contain a primary vertex of type VV, VEE or FEE, we proceed as follows. If a pair P i , P j of polytopes supports a skeleton vertex, we define G ij to be the subgraph consisting of all skeleton vertices and arcs that have P i and P j as supports. The following theorem shows that each connected component of each subgraph G ij contains a primary vertex of the specified types. This allows us to enumerate each subgraph separately starting from these primary vertices. Theorem 5. Let P i and P j be a pair of polytopes that supports a skeleton vertex. Then each connected component of the subgraph G ij defined as above contains a primary vertex.

Proof sketch. The proof uses an optimization concept. For each subgraph G ij , we define an objective function on maximum free line segments corresponding to vertices and arcs of the subgraph. We then prove that each local minimum of each connected component of the subgraph is a primary vertex of type VV, VEE, or FEE. As the subgraph is finite, it must contain such a primary vertex. The details are deferred to Appendix B.

We now show how to explore the partial graph, in order to compute the secondary vertices of types VV, FvE and FF from primary vertices of types VEE, FEE and VV. To explore the partial graph efficiently, we compute the secondary vertices of type VV, FvE or FF that occur in a certain sequence of VE or FE arcs. In what follows, we will show that this can be done in time O(p ′ log p + s ′ ), where p ′ and s ′ are the number, in the considered sequence, of primary and secondary vertices respectively, and p is the total number of primary vertices that are not EEEE in the succinct visibility skeleton.

We consider VE arcs and FE arcs separately. We define a sequence of VE arcs to be a maximal path of VE arcs that all share the same support edge and support vertex. We define a sequence of FE arcs to be a maximal path of FE arcs that share the same support polytope face, and that are tangent to the same other polytope. Note that our definition does not require a sequence of FE arcs to be supported by the same edge of the other polytope. The position in these sequences of skeleton vertices of different types is explained in the two following lemmas. The proofs are a simple application of the properties of skeleton vertices, and are deferred to Appendix C. The next two lemmas state that any sequence of arcs can be completely explored starting from its primary vertices. (Recall that p ′ and s ′ are defined for the considered sequences). Lemma 8. Any sequence of VE arcs can be computed in O(p ′ log p + s ′ + log δ) time if we know all the primary vertices, or, when the sequence contains no primary vertex, if we know one secondary vertex.

Lemma 9. Any sequence of FE arcs can be computed in O(p ′ log p + s ′ + log δ) if we know all the primary vertices, or, when the sequence contains no primary vertex, if we know one secondary vertex. Sketch of proofs. First, if the list of primary vertices in the succinct visibility skeleton is sorted by their supports, we can find the primary vertices in the considered sequence in O(p ′ log p). We then show that secondary vertices can be computed in linear time in their number. This is mostly done by enumerating edges incident to a polytope vertex or face in a proper way, as illustrated in Figure 6. The details of the proof, which mostly consists of case analysis, are deferred to Appendix C.

If an extremity of a sequence is a secondary vertex, we need to find the constraints of that vertex among the edges incident to a polytope vertex or to a face, and this can be done in O(log δ) time for each sequence, using the binary search data structure from Remark 2.

We describe now our exploration procedure in detail. We compute the secondary vertices by exploring the (unknown) partial graph. That is, we first examine each primary vertex of type VV, VEE or FEE, and find all secondary vertices of type VV, FvE and FF on adjacent sequences of arcs. We keep a list of discovered secondary vertices, and check before adding any new one whether it is already there. We then examine recursively each vertex in that list, looking again for secondary vertices on adjacent sequences of arcs, which are added to the end of the list on the condition that they are not yet there. In this sense, we are treating the list like a queue. To search the list efficiently, we order it (lexicographically for example), and keep track of the queuing order by adding to each vertex a pointer to the next one to be examined. Checking whether a vertex is already in the list is then done in logarithmic time.

Since any vertex is adjacent to a constant number of arcs, the search for secondary vertices can be done in O(p log p + s ′ (log s ′ + log δ)) time. Each of the s ′ secondary vertices found during the search is computed in O(log δ) time and added to the list of secondary vertices in O(log s ′ ) time.

Remark 10. The FE vertices correspond to edges of polytopes and can be computed by simple enumeration. Furthermore, FVV vertices correspond to diagonals of faces of polytopes, and can also be found by simple enumeration.

Theorem 5 and Lemmas 8 and 9 yield the following result: Theorem 11. Given the succinct visibility skeleton, one can compute the full visibility skeleton from the succinct one. This computation can be done in O(p log p + s log s) time, where p is the number of primary vertices of type VV, VEE and FEE, and s is the number of secondary vertices (which are of type VV, FvE, FF, FE, and FVV).

The details of the proof are deferred to Appendix C. Note that the complexity of the computation also covers the preprocessing of binary search data structures defined in Remark 2.

We finally note that, if desired, the graph exploration method presented above can be applied to a subset of the input polytopes. In this case, we first find all the primary vertices that are related to the polytopes of the subset, and then apply the graph exploration to these primary vertices only.

Tightness of the Succinct Skeleton

In this section, we show, mostly by examples, that Theorem 11 is tight in the sense that if any one of the primary vertex types EEEE, VEE, FEE, or VV, is regarded instead as a secondary vertex type, and thus excluded from the succinct skeleton, then Theorem 11 no longer holds.

Type EEEE. Any vertex of type EEEE requires four support polytopes, and there are no skeleton arcs that have four support polytopes, by the general position assumption. Hence, by Lemma 3, vertices of type EEEE must be regarded as primary.

Types VEE and FEE. When three input polytopes are not the support polytopes of any EEEE vertex, then the vertices of types VEE and FEE that have supports on the three polytopes cannot be computed from any EEEE vertex.

Moreover, some scenes may generate vertices of type VEE but no vertices of type FEE, or vertices of type FEE but no vertices of type VEE. Examples are given in Appendix D. Hence, by Lemma 3, vertices of type VEE and FEE cannot be dropped.

Type VV. When two input polytopes are not the support polytopes of any EEEE, VEE or FEE vertex, then the vertices of type VV that have supports on the two polytopes cannot be computed from any EEEE, VEE or FEE vertex. Moreover, when two polytopes resemble two nearly flat tetrahedra and face each other, then the only primary vertices they admit are of type VV. Therefore, the primary vertices of type VV must be regarded as primary.

Conclusion

We have presented a method to recover a full visibility skeleton, either partial or complete, from a succinct one. The full visibility skeleton is the 0D and 1D cells of the 3D visibility complex of polytopes, whereas the succinct one is defined by visual event surfaces, and is a subset of the full one. Recovering the full skeleton mainly consists of computing the secondary vertices of type FvE, FF, and VV (whose supports do not lie on a plane that is tangent to both support polytopes), from the primary vertices of type VEE, FEE, and VV (whose supports lie on a plane that is tangent to both support polytopes).

Given k polytopes with n edges in total, the running time of our method is, in the worst case, O(p log p+s log s), where p is the number of primary vertices except type EEEE, and s is the number of secondary vertices. In the worst case, p and s are of size O(n 2 k) and O(n 2 ) respectively, which gives a worst-case total complexity of O(n 2 k log n). This worst-case complexity is the same as the best previously known algorithm, which consists in computing O(n 2 ) candidate secondary vertices in a brute-force way and checking the occlusion with each of the k polytopes in O(log n) time each (using the Dobkin-Kirkpatrick hierarchical representation [START_REF] Dobkin | Determining the separation of preprocessed polyhedra: a unified approach[END_REF][START_REF] O'rourke | Computational Geometry in C[END_REF]). However, we can expect our method to be much more efficient on many instances since its running time is output sensitive.

An interesting subject for future research is to generalize our results to other types of input, such as intersecting polytopes and non-convex polyhedra, and to consider objects in, possibly degenerate, arbitrary positions. Furthermore, the objective function that we use to prove the presence of a primary vertex in each subgraph of the visibility skeleton graph could be used to find a better order of complexity, with the help of reverse search [START_REF] Avis | Reverse search for enumeration[END_REF].

A Computing adjacent vertices

We prove in this section Lemma 4. Let us recall the statement: Lemma 4 If a scene is in general position, then from any skeleton vertex, it is possible to compute each adjacent skeleton vertex in O(log δ) time, where δ is the maximum degree of a polytope vertex or number of edges on a polytope face, provided that all support polytopes of the adjacent skeleton vertex are also support polytopes of the given skeleton vertex and of the connecting skeleton arc.

Proof. By the assumption of the Lemma, we already know that the support polytopes of the adjacent skeleton vertex are a subset of the given skeleton vertex.

From the starting skeleton vertex, we need to find the incident skeleton arcs. Since we know the constraint edges of the skeleton vertex, and there are at most a constant number of them by Remark 1, we can find its incident skeleton arcs in constant time by removing in turn each of these constraints. As the polytopes are in general position, the number of constraints is bounded; there may however be as many as seven of these constraints and it is sometimes necessary to remove more than one of these at the same time.

We now consider how to deal with each type of arc incident to a given vertex. From an EEE arc, it is possible to find unknown incident skeleton vertices of type VEE or FEE by checking all polytope faces and vertices incident to the polytope edges, and computing the corresponding candidates. Since their number is constant, we can find the incident vertices in constant time by enumeration. Similarly, from a VE arc, we find unknown incident VV vertices by checking polytope vertices incident to the polytope edge. From an FE arc, we find unknown FF vertices by checking polytope faces incident to the polytope edge.

Moreover, from a VE arc, we find unknown incident FvE vertices by checking the four polytope faces that are incident to the two salient edges incident to the polytope vertex. From an FE arc, we find unknown FvE vertices by checking the four polytope vertices that are incident to the two polytope edges lying on the polytope face.

Thus we can find the maximal free line segment that corresponds to an adjacent skeleton vertex in constant time, along with its support vertices or faces.

According to Remark 2, we also need to compute the constraint edges. For a VEE or VV vertex, these are salient edges, which can be computed by searching through the polytope edges incident to the support polytope vertices. This can be done in O(log δ) time. For an FEE or FF vertex, these are support edges, which can be computed by searching through the polytope edges on the support polytope faces. Again, this can be done in O(log δ) time. These times are obtained thanks to the binary search data structure discussed in Remark 2.

Similarly, one can prove the computational relations shown in Figure 5 for skeleton vertices of type FE and FVV.

B Proof of Theorem 5

In this Section, we provide the details of the proof of Theorem 5. Here is a general outline. For each pair of polytopes P i , P j that support at least one skeleton vertex, we define an objective function, which associates a value to each maximal free line segment tangent to both polytopes. Recall that the graph G ij is defined to be the subgraph consisting of all skeleton vertices and arcs that have P i and P j as supports. We prove that each local minimum of the objective function on each connected component of the G ij graph is a primary vertex.

For each pair of polytopes P i and P j that support at least one skeleton vertex, we define the following objective function. Let H be a plane separating P i and P j , and let u be a vector that is in generic direction (explained below). For any maximal free line segment l tangent to P i and P j that corresponds to a skeleton vertex or a point of a skeleton arc, we define the value of l to be f (l) = u • x, where x is a vector representing the intersection of H with the supporting line of l. 4 Note that l always intersects H, being tangent to P 1 and P 2 , which are separated by H (See Figure 7). Lemma 12. Any vertex v of the visibility skeleton of type FF or FvE that is supported by P i and P j has an adjacent vertex v ′ , connected by a VE or FE arc, such that the value of f along the arc continuously decreases from v to v ′ .

Proof. If maximal free line segments are all tangent to the same edge and all intersect at a common single point off the edge, their intersections with plane H lie on a straight line, the intersection of H with the plane containing the tangent edge and the common point. We can parametrize these free line segments by l(t), t ∈ [0, 1], such that l(0) and l(1) correspond to the maximal free line segments tangent to the extremities of the edge, and f (l(t)) is an affine function, which is not constant since u is in generic position, so f (l(t)) has a minimum at 0 or 1. In particular, the set of maximal free line segments corresponding to a VE or FE arc of the visibility skeleton share a 3D point and are tangent to a common polytope edge e, and so the value of a maximal free line segment increases or decreases monotonically between two skeleton vertices connected arcs of these types.

Recall that extremal FvE vertices correspond to maximal free line segments l tangent to a polytope edge and a vertex of a different polytope, and are in the supporting plane Π of a face incident to the vertex, without intersecting that face except at the vertex (Figure 8). An extremal FvE vertex always has two incident VE arcs corresponding to the same polytope vertex and polytope edge, rotating about the polytope vertex from l in opposite directions. Therefore, the maximal free line segment corresponding to an extremal FvE vertex is in the middle of a set of free line segments defined by a vertex and an edge, which corresponds to two incident skeleton arcs. Since it is in the middle, its value is not minimum, so the value is decreasing along one of the arcs.

Non-extremal FvE vertices correspond to maximal free line segments tangent to a polytope face and a polytope vertex of that face, and to an edge of a different polytope (Figure 9). If a non-extremal FvE vertex is defined by an edge e of polytope P , a vertex v and a face f of polytope P ′ , then it has two incident FE arcs corresponding to the same intersection point on e and polytope edge (incident to f , but not v), whose corresponding maximal free line segments rotate about e in opposite directions. Again, the corresponding maximal free line segment is in the middle of a set of free line segments defined by a vertex and an edge, which corresponds to two incident skeleton arcs, and the value is decreasing along one of the arcs.

Vertices of type FF have four incident FE arcs. Let p and p ′ denote the intersection points of the maximal free line segment corresponding to an FF vertex with the two support edges on one of the two polytopes. Then the two FE arcs, obtained by rotating the maximal free line segment corresponding to the FF vertex around p and p ′ , will move in opposite directions on a line in H. Therefore, one of them is decreasing. Lemma 13. Let v be a vertex of the visibility skeleton of type VV. If all adjacent vertices of v have a higher value than v, then v lies in a plane tangent to both polytopes, i.e., v is a primary vertex.

Proof. Let v be a VV vertex supported by the polytope vertices v and v ′ in the polytopes P and P ′ , respectively, such that all adjacent skeleton vertices have a higher value. Let x be the intersection of v with H. Without loss of generality, we assume x to be the origin. Since H contains the origin, its equation is H = {x : a • x = 0} for some vector a. We modify u into u ′ , such that u ′ is perpendicular to v, but the value function does not change. This can be done by setting

u ′ = u - u • d a • d a, e 1 P e 2 v H v x v ′ u ′ K Figure 10
. The silhouette of the polytope P from v projected on H is inside the cone of the projected salient edges.

If the salient edges are in the half-plane u ′ • x 0, so is the polytope.

where d is a vector from v to v ′ . It is easy to check that u ′ • d = 0 and u • x = u ′ • x for any x in H. Let K denote the plane through x perpendicular to u ′ . Vertices of type VV have four incident VE arcs, two supported by each polytope vertex. Let e 1 and e 2 be the two salient edges of v incident to v ′ ; then v and e 1 generate a VE arc incident to v, as well as v and e 2 . Viewed from v, the silhouette of P projected on H is contained in the cone between e 1 and e 2 (see Figure 10). By assumption, the value of maximal free line segments is increasing along the four incident VE arcs, so P is in the half-space u ′ • x 0.

Similarly, P ′ is in the half-space u ′ • x 0, and so v lies in the plane K defined by u ′ • x = 0 which is tangent to P and P ′ .

We are now ready to prove Theorem 5. Let us recall the statement:

Theorem 5 Let P i and P j be a pair of polytopes that supposrts a skeleton vertex. Then each connected component of the subgraph G ij defined as above contains a primary vertex.

Proof. Since any non-empty subgraph G ij is finite, it has a minimum. From Lemma 12, we know that vertices of type FF or FvE cannot be local minima. From Lemma 13, we know that any vertex of type VV that is a local minimum is a primary vertex. It follows that the minimum of G ij is a primary vertex.

C Exploration of the 3D visibility skeleton graph

In this section, we present the proof of Lemmas 6 to 9 and of Theorem 11. Proof. Any extremal FvE vertex has a single incident FE arc. It is therefore an extremity of a sequence of FE arcs. Any non-extremal FvE vertex has two incident FE arcs supported by the same polytope face and polytope edge. It is in the middle of a sequence. And any FF vertex has four incident FE arcs, each polytope face supporting two of them, which are tangent to different edges on the other polytope. They are therefore in the middle of a sequence. An FEE vertex has three or four incident FE arcs, which are supported by two different polytope edges. When two arcs are supported by the same edge, the vertex is in the middle of the sequence; when only one arc is supported by an edge, the vertex is an extremity of the sequence.

For the following, recall that p is the total number of primary vertices in the succinct visibility skeleton minus the EEEE vertices, and p ′ and s ′ are the number of primary, respectively secondary vertices in a sequence of arcs.

Lemma 8 Any sequence of VE arcs can be computed in O(p ′ log p + s ′ + log δ) time if we know all the primary vertices, or, when the sequence contains no primary vertex, if we know one secondary vertex.

Proof. First, we find the primary vertices in the sequence from the total list of primary vertices in the succinct visibility skeleton. If the list is sorted by supports, this can be done in O(p ′ log p). We then show that secondary vertices can be computed in linear time in their number.

All skeleton vertices in a sequence of VE arcs are supported by a vertex v on polytope P and an edge e. Suppose x is a point moving on e, and let us consider the maximal free line segment l containing x and v. The constraints of l are e and two salient edges incident to v, denoted e 1 and e 2 . Let p 1 , p 2 be the two planes containing x and e 1 , e 2 respectively. Then plane p 1 (respectively p 2 ) is tangent to P and contains x, v and e 1 (respectively e 2 ). As x moves along e, planes p 1 and p 2 roll around the faces and edges incident to v. Let C be the polyhedral cone created by faces incident to v, and let C ′ be the centrally symmetric cone also having its apex at v. If the supporting line of e does not intersect C or C ′ , the two planes roll in the same direction around v (Figure 6). Otherwise, they roll in opposite directions (Figures 11 and12).

Suppose we know one of the extremities of the sequence of VE arcs, which can be either a VV, a VEE or a non-extremal FvE vertex. We examine each of the cases in turn as follows.

Case i): The extremity is of type VV (supported by v and v ′ ): Then the planes tangent to P contain its salient edges, e 1 and e 2 ; the supporting planes of the polytope faces incident to e 1 or e 2 intersect the supporting line of the polytope edge e on either side of v ′ (see Figures 6 and11). From those two edges (e 1 and e 2 ), circling around the polytope vertex v, we enumerate the two sequences of faces incident to v. Their supporting planes intersect the polytope edge e, and each of the intersections corresponds to an extremal FvE vertex.

If there is a VEE vertex in the sequence of arcs, then we already know the vertex, as well as the point where the maximal free line segment corresponding to the VEE vertex intersects the edge e. Thus we can insert it in the sequence when the intersections reach that point. The VEE vertex can end the sequence; otherwise we keep enumerating the faces incident to v.

If the sequence of arcs ends with a VV vertex, we stop when the intersections reach the other end of edge e.

In case the two sequences of faces are turning in opposite directions, and they turn until they meet (see Figure 11), this indicates a non-extremal FvE vertex at the end of the sequence of arcs.

Case ii): The extremity of the sequence of VE arcs formed by vertex v and edge e is a VEE vertex (supported by v, e and e ′ ): then let e 1 and e 2 denote the salient edges of the VEE vertex, incident to v, and we continue as in the case that the extremity is of type VV.

Case iii): The extremity of the sequence of VE arcs formed by vertex v and edge e is a non-extremal FvE vertex (supported by f , v and e): Then we enumerate from f the two sequences of faces incident to v and proceed as above. In case we do not know an extremity of the sequence of arcs, but we do know a vertex in the middle, we can explore the sequence in each direction using the same method, since we know the constraints of the vertex. If it is of type VEE, then let e 1 and e 2 denote its salient edges incident to v, and continue as above. If it is of type extremal FvE (supported by f , v and e), then let e 1 , e ′

1 and e 2 be three salient edges incident to v, with e 1 and e ′ 1 incident to f . We then enumerate faces incident to v in one direction starting with e 1 and e 2 , and in the other starting with e ′ 1 and e 2 . Note that if the sequence does not have a VV or VEE vertex at either extremity, then the supporting planes of all faces incident to the vertex v intersect with edge e (see Figure 12). All of these intersections correspond to FvE vertices.

Finally, if an extremity of a sequence is a non-extremal FvE vertex, we need to find its constraints among the edges incident to the support polytope face, and this can be done in O(log δ) time.

Lemma 9 Any sequence of FE arcs can be computed in O(p ′ log p + s ′ + log δ) if we know all the primary vertices, or, when the sequence contains no primary vertex, if we know one secondary vertex.

Proof. As in Lemma 8, we first find the primary vertices in the sequence from the complete list of primary vertices in the succinct visibility skeleton in O(p ′ log p) time. We then show that secondary vertices can be computed in linear time in their number.

If the extremity of the sequence of FE arcs formed by face f and polytope P is an FEE vertex (supported by face f , edge e on P and e ′ on some other polytope), then let e f and e ′ f denote its two support edges on face f . From e f or e ′ f , circling around the face f , the two sequences of polytope vertices (on face f ) will create a sequence of arcs joined by non-extremal FvE vertices with e.

If there is an FEE in the sequence of arcs, then we know the vertex, as well as its support edges on f . If the sequence of arcs reaches an FEE vertex, we insert the vertex into the sequence of arcs. The FEE vertex can end the sequence; otherwise we keep enumerating the vertices of f .

If the sequence of arcs contains an FF vertex, it corresponds to face f and a face f ′ that is incident to edge e. These are inserted in the sequence of arcs when the sequences of vertices cross the supporting plane of f ′ .

In case we do not know an extremity of the sequence of arcs, then they are the type of extremal FvE. In this case, all vertices of face f create an extremal or non-extremal FvE vertex with the other polytope. So starting from any skeleton vertex we know, we can enumerate polytope vertices on face f , adding vertices of type FF and FEE along the way as above.

Finally, if an extremity of a sequence is an extremal FvE vertex, we need to find its constraints among the edges incident to its support vertex, and this can be done in O(log δ) time.

Theorem 11 Given the succinct visibility skeleton, one can compute the full visibility skeleton from the succinct one. This computation can be done in O(p log p + s log s) time, where p is the number of primary vertices of type VV, VEE and FEE, and s is the number of secondary vertices of type VV, FvE, FF, FE, and FVV.

Proof. We start with the knowledge of all the primary vertices, and find the secondary vertices. In order to do that, we explore the partial subgraph of the visibility skeleton containing all VE and FE skeleton arcs and the skeleton vertices at their extremities. We find in this way all vertices of type VV, FvE and FF.

By Theorem 5, we know at least one vertex in each connected component of this partial subgraph. Lemmas 8 and 9 show that from any vertex in a sequence of VE or FE arcs, we can find all the secondary vertices in the sequence in time linear in their number. As any unknown vertex is connected to a known vertex through a series of sequences of arcs, we can find all vertices.

We have seen that using our special exploration procedure, a graph of p known vertices and s ′ unknown vertices can be explored in O(p log p + s ′ (log s ′ + log δ)) time. Vertices of type FE and FVV are computed separately in linear time in their number s ′′ . Thus the complete enumeration is done in O(p log p + s ′ (log s ′ + log δ)+s ′′ ) time, where s ′ +s ′′ = s. Note that δ is in O(s ′′ ), since s ′′ is the number of edges and face diagonals in the whole scene (see Remark 10). Therefore, O(p + s ′ (log s ′ + log δ) + s ′′ ) is in O(p log p + s log s), and the theorem follows.

D Examples showing tightness of the succinct visibility skeleton

We present in this section examples of instances where a particular type of skeleton vertices is necessary to compute the whole skeleton, showing that each of these types must be defined as a primary vertex.

First, we give an example in Figure 13 (a) of a scene which contains vertices of type VEE, but no vertices of type FEE.

Then, we present a construction generating vertices of type FEE, but no vertices of type VEE, as shown in Figure 13 (b) and explained below.

The scene in Figure 13 (b) consists of a prism that approximates a cylinder, positioned between two truncated pyramids that approximate truncated cones, where the full cones would barely intersect.

A supporting plane of a face of the prism intersects the two truncated pyramids in two polygonal arcs that approximate hyperbolas (Figure 13 (c)). These two polygonal arcs admit two bitangents that lie in the supporting plane of the face of the prism and that cross the face, generating two FEE vertices.

As the supporting plane rolls around the prism, either one of the two bitangents will cross a pyramid face, or both bitangents will cross a face of the prism. Thus for this scene, each arc of type EEE is incident to two FEE vertices, and there are no vertices of type VEE.

Figure 1 .

 1 Figure 1. The eight types of vertices of the 3D visibility skeleton.

Figure 2 .

 2 Figure 2. The four types of arcs of the 3D visibility skeleton.

Figure 4 .

 4 Figure 4. The extremal case of type FvE vertex.

Figure 5 .

 5 Figure 5. The possible computational relations among the types of 3D visibility skeleton vertices.

Lemma 6 .

 6 Any sequence of VE arcs has a VV vertex, a VEE vertex, or a non-extremal FvE vertex at each extremity, and arcs in the sequence are separated by extremal FvE vertices or VEE vertices. Lemma 7. Any sequence of FE arcs has an extremal FvE vertex or FEE vertex at each extremity, and arcs in the sequence are separated by non-extremal FvE vertices, FEE vertices or FF vertices.

Figure 6 .

 6 Figure 6. (a) Bird's eye view and (b) 3D view of extremal FvE vertices whose supports are polytope edge e and two sequences of faces incident to v, starting from e1 and e2, which create VE arcs with v ′ .

Figure 7 .

 7 Figure 7. The figure on plane H represents the intersections with H of the maximal free line segments corresponding to the skeleton arcs and vertices supported by Pi and Pj. The value of each of the maximal free line segments is defined by a linear function of its intersection with the plane H.

Figure 8 .Figure 9 .

 89 Figure 8. The intersections with H of maximal free line segments on the two VE arcs on each side of an extremal FvE vertex move in opposite directions.

Lemma 6 Lemma 7

 67 Any sequence of VE arcs has a VV vertex, a VEE vertex, or a non-extremal FvE vertex at each extremity, and arcs in the sequence are separated by extremal FvE vertices or VEE vertices.Proof. Any non-extremal FvE vertex has a single incident VE arc. Any VV vertex has four of them, but no two of them are supported by the same polytope vertex and edge. Thus, any non-extremal FvE or VV vertex is an extremity of a sequence of VE arcs. Any extremal FvE vertex has two incident VE arcs supported by the same polytope vertex and edge, so it is in the middle of a sequence. A VEE vertex has three or four incident VE arcs, which are supported by two different polytope edges. When two arcs are supported by the same edge, the skeleton vertex is in the middle of the sequence; when only one arc is supported by an edge, the vertex is an extremity of the sequence. Any sequence of FE arcs has an extremal FvE vertex or FEE vertex at each extremity, and arcs in the sequence are separated by non-extremal FvE vertices, FEE vertices or FF vertices.

Figure 11 .FvEFigure 12 .

 1112 Figure 11. When the polytope edge e intersects with the polyhedral cone of the faces incident to v, the two sequences of faces that are supports of extremal FvE vertices turn in opposite directions until they meet, which indicates a non-extremal FvE vertex.

Figure 13 .

 13 Figure 13. (a) Three polytopes admit vertices of type VEE but not vertices of FEE. (b) Three polytopes admit vertices of type FEE but not vertices of type VEE. (c) A cross section of (b) as indicated by the red line segment.

In[START_REF] Durand | Visibilité tridimensionnelle : étude analytique et applications[END_REF][START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF], Durand et al. do not assume any structure in the triangles composing a scene. The lines supporting maximal free line segments are always tangent to their associated triangles, but not necessarily to the polyhedra they are part of. In this paper, we consider the triangles to be structured in polytopes and we require tangency between these lines and their associated polytopes.

Note that polytopes are bounded polyhedra.

We can define the generic direction of u to be u = (1, ε, ε 2 ), so that when ε goes to 0, f (l1) = f (l2), for any maximal free line segments l1 and l2 corresponding to adjacent skeleton vertices.


D A Silva

C Sinfort

B Bonicelli

M Voltz

S Huberson

International Advances in Pesticide Application Spray penetration within vine canopies at different growth stages

Keywords: Vine, spraying, model, deposit, simulation, Leaf Area Density, absorption coefficient, resistance

This paper deals with adaptation and improvement of a previous model developed to predict amount of pesticide deposit within vine canopies. Tasks described here were aimed at analysing the effect of variation in the leaf area density (LAD) on both model predictions and deposits measured in the field. Tests were conducted in a vineyard during spring-summer 2001. Deposits on leaves and LAD were measured at several growth stages. After a description of the field tests, the outline of the model is briefly described and the influence of LAD on the results obtained with both methods discussed.

Introduction

Vines, particularly those in Mediterranean countries are infested by various pests and diseases that are controlled by frequent pesticide treatments, usually by means of air-assisted sprayers. It is now necessary to reduce pesticide losses to preserve the environment (i.e. to reduce run-off and drift problems). It is also necessary to spray more accurately in order to decrease the amounts of pesticides in plants as well as to limit possible residues in grapes and/or in wine. These improvements depend on a better knowledge of spraying processes. To understand phenomena that occur during spraying, many experiments have been conducted but they are time-consuming and expensive and, moreover, not reproducible. Operating conditions vary substantially since an exact description of the vine foliage would be obviously impossible and of no use. As a result, averaged conditions had to be defined. They provided a basis for numerical simulations. Within that context, this work aimed at predicting which part of pesticide sprayed within the canopy is retained by leaves, depending on the canopy density.

In a previous paper (Da [START_REF] Silva | Simulation of sprayed pesticide deposit within a vineyard[END_REF] a model was described that represented air penetration of air-assisted spray within vine canopies. The model was constructed according to principles developed by Walklate (1996) and measurements of air velocities performed in the laboratory on artificial plants. The steady, incompressible and isothermal flow could be described by the time-averaged Navier-Stokes equations [START_REF] Zhi | Flow structure and spray transport from a moving orchard sprayer[END_REF]. Product concentration within the canopy had been predicted by means of an additionnal advectiondiffusion equation. The different physical parameters which were used in this equation had been identified in order to reproduce the results obtained on vine leaves during a one-spray test with a fluorescent dye, where all leaves from a vine were picked to measure deposits.

In this paper, the aim is to analyse the effect of LAD on deposits at different growth stages, by two different approaches; field tests and model simulations.

Materials and Methods

Field Experiments

Tests were organised on a Merlot grape vineyard of 3.3 hectares area. The test period extended from May 15 th to July 15 th 2001. During this period, this vineyard was sprayed 3 times with copper using a pneumatic sprayer at a dose of 1.5 kg ha -1 . Calibration was done in laboratory to obtain a flow rate of 3 litres min -1 from each side of the sprayer. The forward speed was 5 km h -1 (Fig. 1).

Figure 1. Field experiments: photograph of spraying and frame for leaf sampling

That sprayer was equipped with an embedded device to record meteorological data, right and left flow-rates and ground velocity and with a GPS device to record sprayer position. Set-up of the sprayer was the same for all three tests except those examining the effects of direction of the spray jets. Leaves were collected from 3 trees before each spray application and from 9 trees after each application. For each tree, canopy sections of 10 cm width (travel direction) were selected. These sections were then divided into 25cm x 25cm x 10cm cells (Fig. 1).

For each tree, leaf areas were measured using a camera and an image analysis procedure developed with Matlab. The leaf area density (LAD) was then computed for each cell. The amount of copper was obtained by digesting the organic matter with acid followed by flame atomic absorption spectrometry. Results were given for the entire mass and that mass was related to surface area (efficiency) for each harvested cell. The model, developed with CFX solver was described in Da [START_REF] Silva | Simulation of sprayed pesticide deposit within a vineyard[END_REF]. Contrary to this last paper, the vine was now considered to be non-homogeneous. Its geometry has been divided in 5 vertical blocks in which leaf area density was defined (Fig. 2). The numbers of cells in the vertical, longitudinal and transversal directions are respectively 40, 35 and 24 for the all domain and 20, 20 and 24, for the vine. Air velocity at the inlet of the domain was set to 11.5 m s -1 corresponding to the averaged experimental conditions described in the previous section. On the other faces, Dirichlet boundary conditions for pressure were used. Total pressure was specified and set to 0.0 bar.

As previously mentionned, the physical phenomena has been described by means of two different equations. Firstly, the Navier Stokes equation was used with the additional resistance tensor R ij causing a momentum loss due to foliage proportional to the LAD, as shown by Walklate (1996). Secondly, regarding the product transport, an advection-diffusion equation described the concentration decrease across the canopy by introduction of a sink term S c equal to S p .Y a where Y a is the product mass fraction (Da [START_REF] Silva | Simulation of sprayed pesticide deposit within a vineyard[END_REF]. There was only one carrying phase, air, which was regarded as a continuum and solved in an Eulerian frame. R ij and S p were specified in each block and Y a , the initial mass fraction of the product, was set at the inlet.

In order to compute the deposit within a non-homogeneous vine canopy, i.e. with a nonuniform LAD, it was then necessary to estimate the product concentration in the five vertical blocks used in field measurements. In the numerical simulation, the sprayer was static so that the air jet only occupied a limited part of the computational domain. Therefore, a reduced section of the cross flow plane was selected, extending vertically from lines 1 to 22 and rows 7 to 18 (Fig. 2). In order to perform a computation, each block had been sub-divided into four brackets extending 0.0625 m in the flow direction and corresponding to a convenient discretisation for the numerical simulation. For each block, constant values for the resistance and absorption coefficient had to be specified (Fig. 3).

Figure 3. Sampling of the vine

On this basis, block values for Sp were selected in order to fit the experimental data as well as possible. This was performed by means of a set of runs which actually constituted the different steps of a rough optimisation procedure. The main assumption at this stage was that the optimisation could be parabolised according to the flow direction. This is a realistic requirement since the concentration had no effect on the flow in our model. The different sections are coupled within the concentration transport equation only, which could be considered as a weak coupling in view of the respective values of the transport velocity and dispersion coefficient. Therefore, the following sequence had been performed:

We assumed that all the Sp values for block 1 to n-1 had been computed. A first run with these values for the upstream blocks and Sp = 0 for the downstream blocks including block n was then performed. A first estimate for Sp(n) was computed from the local concentration in block n. This value could be used as a first guess in an iterative procedure in which the upstream and downstream values were those previously used and only the block n value was adjusted. Local iterations were stopped once the desired deposit value had been conveniently approximated. It was important to notice that the concentration fraction corresponding to the deposit had to be renormalised since the experimental deposit fraction was based on the initial concentration whereas the computed one was based on local concentration.

The procedure was stopped when coefficient Sp had been estimated for all blocks.

Results

Field results

Analysis of results was done in three steps. The first was to compute an average tree for each test (May, June and July), the second was to analyse the balance of copper for each growth stage and the third was to analyse influence of LAD and of growth stage on distribution of product within the plant.

To define an average tree at the three periods, it was first necessary to have each tree centred around its baricentre. This baricentre was obtained by using LAD as a mass parameter. Then, LAD and the mass of copper were re-computed with a linear interpolation so that all trees of the same test had the same baricentre. Then, the average tree was defined to have in each of its cells the average values of LAD and of copper mass of each cell in the same position for any tree at the same period. Table 1 gives the mean LAD obtained for each average tree as well as the total amount of copper sprayed on it. This last value was computed by subtraction of the amount of copper measured just before spraying and it is given relative to one hectare (with rank space of 2.50 m). Figure 4 shows the amount of copper measured on leaves relative to LAD for the three different growth stages. The values are for the total amount obtained in each collect cell (25cm x 25 cm x 10 cm). The scheme was drawn on a log-log scale because samples with low LAD (and low mass of Copper) were more numerous.

Figure 4. Amount of copper measured in each cell of the averages trees for the three growth stages (May, June and July) -mCu (mg) -relative to the LAD. "Correl" stands for the linear regression curve Simulation

The model had been calibrated in former trials made in a vineyard with an air-assisted sprayer [START_REF] Silva | Simulation of sprayed pesticide deposit within a vineyard[END_REF]. Improvement of model consisted of dividing the vegetation into 5 blocks of 4 brackets each one, with a different resistance force and an absorption coefficient for each block, in order to have LAD varying with depth. In CFX solver, the resistance called R f is equal to R ij / (U i U i ) successive simulations, as described above, values of S p were calibrated to fit the experience (Fig. 5). Values of S p (S1 to S5) and R f (R1 to R5) are recapitulated in Table 2. While resistance R f increases with LAD, absorption coefficient decreases linearly together with LAD, except for the first block, where the LAD can be overlooked. As far as concentration Co at the input of each block is concerned, i.e. concentration before deposit as explained in simulation principles, it decreases exponentially from second to last block. Between the first and the second block, one can see an accumulation of product, Co passing from 17.88 g.m -3 to 22.52 g.m -3 . Apart from the first block, deposits decrease with depth while increasing with LAD.

Deposit in each block

Discussion

Field experiments

The main fact that can be underlined about field results is a poor proportion of copper reaching the plant, particularly at the first growth stages. The reason is that the dose of product was not adaptated to the plant size. Only the direction of the spray jets was modified. These results show clearly -if necessary -that this is not good practice. In fact, product was lost mainly to the ground and the atmosphere.

Evolution of geometry and density of canopy is important during the first month. Later on, it becomes less important but one should notice that some operations as pre-pruning or stems training were conducted during the second month.

When observing the influence of LAD on the amount of copper retained on leaves, one can observe that the growth stage does not seem to influence behaviour. The linear regression gives a correlation coefficient of 0.90. This regression fits the equation : m Cu/cell [mg] = 0.31 x LAD [m 2 /m 3 ] Such a result seems to demonstrate that collecting from canopy sections of 10 cm width at several points in the vineyard in order to define an average sample is a good methodological approach as it allows a generalisation of some phenomena. This point is very interesting when justifying use of simulations as there were done. The linear correlation that was observed could be due to the spraying technology used (pneumatic). It is not obvious that another sprayer would have given the same result. Nevertheless, such kinds of results should be confirmed under different conditions (sprayer and dose) as it could allow easy prediction of amounts of deposits.

Simulation

The first effect of LAD is decreasing the air speed. With the second block, when LAD abruptly changes, there was an accumulation of product because of foliage shear stress. It is illustrated by R f , depending only on LAD.

In order to modelise the fraction of product retained by the leaves, the absorption coefficient Sp has been introduced in the folowing advection-diffusion equation :

∂ρY a ∂t + ∇.(ρUY a ) -∇.(Γ a ∇Y a ) = S p Y a where : ρ = ρ(air+ product) = Y a ρ a + (1 -Y a ) ρ air Y a = C a ρ
, with C a the concentration of pesticide U is the air speed and Γ a is the molecular diffusivity added to the turbulent diffusivity.

Although an identification procedure based on experimental measurements had been used, it was not possible to obtain satisfactory results with one uniform value for Sp. This was only achieved when a linearly varying Sp was used. However, such a law can not be considered anymore because it is based on one single experiment.

Several simulations calibrated after many experimental data (with other vine and machine configurations) could possibly confirm it. If S p could be deduced from LAD, final deposit could be predicted from known LAD using the advection-diffusion equation model.

Influence of LAD

The experimental results shows a linear correlation between LAD and deposit, meaning that the deposit per leaf surface unit should be constant for an average tree representing the entire vineyard. The goal of the numerical simulation was to describe what happened on a given tree knowing its internal LAD variation. The representation used here, with an advection-diffusion equation using a sink term S p allowed representation of experimental deposits but calibrations for simulations resulted in a cumbersome procedure. Moreover, the clear dependance of Sp on the LAD can not be considered as defined due to limitation of the present work to one single experimental case. Further work will be required to derive an automatic identification procedure which can be used to analyse many more experiments so that the resulting Sp (LAD) law could have a better basis.

A Lagrangian model would allow analysis of the dependency of the phenomena on droplet speed and diameter. With such an approach, a droplet mass fraction could be defined instead of the product mass fraction used with the Eulerian model. It shoud be then possible to analyse a collection efficiency of spray droplets as defined by [START_REF] Zhu | Collection efficiency of spray droplets on vertical targets[END_REF] on vertical targets.

Figure 2 .

 2 Figure 2. Geometry. Top left, global geometry. Top right, grid from top view. Bottom right, grid from right view. Bottom left, simulation air flow.

Figure 5 .

 5 Figure 5. Comparison between experimental and simulated deposit.

Table 1 .

 1 Mean

		LAD and mass at of copper obtained at the three different growth stages
	(amount of sprayed copper: 1500 g/ha)
		Height Depth Mean LAD	Mass of Copper	Percentage
	Test	(m)	(m)	m 2 /m 3	g/ha of sprayed Cu
	May	0.75	0.75	0.76	95	6%
	June	1.25	1.50	2.34	574	38%
	July	1.25	1.50	3.30	1141	76%

  1/2 where U i is the i-component of the air speed. It is proportional to LAD. With

				Cu = f(LAD)
		10.000
		1.000
	m Cu(mg)	0.100
		0.010
		0.001
		0.01	0.10		1.00	10.00	100.00
					LAD (m2/m3)
			July	June	May	Correl

Table 2 .

 2 Simulation results relatively to LAD : values of R f and S p coefficients and evolution of the initial concentration Co at the input of each block.

		Block 1 Block 2 Block 3 Block 4 Block 5
	LAD (m -1 )	0.09	3.34	3.06	1.93	0.32
	R f (kg.m -4 )	0.03	1.22	1.12	0.7	0.12
	S p (kg.m -3 .s -1 ) -0.2	-15	-18	-30	-100
	Co (g.m -3 )	17.88 22.52 10.32 1.06	0.02
	Deposit (g.m -3 ) 0.04	4.08	2.40	0.36	0.01

Acknowledgements

This work was completed within concerted research program of INRA and Cemagref institutes (program AQUAE). The authors wish to acknowledge Sandrine Negro for all her chemical analyses. The authors also wish to thank AFCRST (French Chinese association for Scientific and Technical Research) which provided funds to the work of Hexing Zhang whose work for his masters degree could be completed within this program. Finally, the authors thank all the people who participated in field experiments and especially Vincent De Rudnicki for his work on the sprayer.