Project Topics
Get Complete Project Material File(s) Now! »
The 3D Visibility Complex
We introduce the 3D visibility complex based on the work of Durand et al. [34, 38] as it was initially presented.
The 3D visibility complex is an extension of the concept of the 2D visibility com-plex. However the 3D visibility complex is not a cell complex since some of the cells are not contractible to a point. Moreover a line in 3D has four degrees of freedom, and therefore the cells that partition the 3D line space can have higher dimension than the cells in the 2D case.
In what follows, we deÞne the cells of the 3D visibility complex. We note that the concept of each cell is based on smooth objects that are in general position. We say 3D objects are in general position when free line segments tangent to any n of them have 4 n degrees of freedom with respect to that property, for 0 n 4.
¥ a vertex corresponds to a maximal free line segment that is tangent to three or four objects that are in general position (Figure 2.5). In the case of three objects, the maximal free line segment lies on a plane that is tangent to two objects. Such line segment has 0-degrees of freedom. A vertex is a 0D cell.
¥ an edge corresponds to a set of maximal free line segments that are tangent to two or three objects that are in general position, and form one connected component (Figure 2.6). In the case of two objects, the set of maximal free line segments lie on a set of planes that are tangent to the two objects. In such a set, each line segment has 1 degree of freedom. An edge is a 1D cell.
¥ a bitangency (respectively tangency) face corresponds to a set of maximal free line segments that are tangent to two (respectively one) objects that are in general position, and form one connected component. In such a set, each line segment has 2 (respectively 3) degree(s) of freedom. A bitangency (respectively tangency) face is a 2D (respectively 3D) cell.
¥ a face corresponds to a set of line segments that are being occluded by the same two objects, form one connected component. Each of the line segments in such a set has 4-degrees of freedom. A face is a 4D cell.
The Visibility Skeleton
The visibility skeleton data structure is a simpliÞed version of the visibility com-plex that consists of only the 0D and 1D cells of the visibility complex. This data structure was Þrst introduced in 3D by Durand et al. [34, 36] and used in shadow boundary computation [32, 34, 36]. The application of this data structure was suc-cessful but limited to only small input scenes, since the practical running time complexity of the algorithm that is used to compute it is relatively high (O(n2.5)), and the worst-case size complexity of this data structure is large (O(n4)). These apparent limitations have motivated researchers to study its average size and to design efficient algorithms to compute it. The ongoing research of others in this area will be intro-duced later in this chapter, as indeed, the main part of this thesis also studies the 3D visibility skeleton.
The 2D visibility skeleton data structure was later introduced by Goaoc [50] when designing a sweep algorithm to compute the 3D visibility skeleton.
In the visibility skeleton data structure, a 0D cell is called a vertex and a 1D cell is called an arc. Recall that, in the visibility complex data structure, the 0D cell corresponds to a maximal free line segment that has 0-degrees of freedom; and the 1D cell corresponds to a connected set of maximal free line segments that have 1-degree of freedom. This concept holds in the visibility skeleton data structure as well. Moreover, the incidence relation of vertices and arcs is encoded into a graph, namely, the visibility skeleton graph. We will introduce this data structure in 2D and 3D in detail in the next two sections.
The 2D Visibility Skeleton
We introduce this data structure based on the work of Goaoc [50], but limit ourselves to the case where objects are in general position. By general position, we mean that no three vertices are collinear.
Figure 2.8. (a) The 2D visibility skeleton vertices and arcs, computed from objects A and B. Four vertices, labeled 1, 2, 3, 4, are shown as four blue line segments, and an arc, incident to vertices 1 and 2, is shown as a set of dashed lines. (b) The corresponding 2D visibility skeleton graph of (a); the circular cycle corresponds to the vertices whose corresponding maximal free line segments are tangent to object A in clockwise order; and the other cycle is similarly deÞned, based on object B.
2D Visibility Skeleton Vertices and Arcs
In 2D, there is only one type of vertex and one type of arc. Each vertex corresponds to a maximal free bitangent that is tangent to two objects. Each arc corresponds to a set of connected maximal free line segments that are tangent to one given object, and possibly blocked by 0, 1, or 2 other objects. A graphical illustration of the 2D visibility skeleton vertices and arcs is shown in Figure 2.8 (a).
The 2D Visibility Skeleton Graph
In the 2D visibility skeleton graph, each vertex is incident to four arcs, and each arc is incident to two vertices. In particular, the corresponding maximal free line segments of each arc, and its two incident vertices, are tangent to a common object. An example graph is shown in Figure 2.8 (b), which is computed from the two polygons A and B, as shown in Figure 2.8 (a).
The 2D visibility skeleton graph is a directed graph whose arcs are oriented as follows. Two adjacent vertices of the graph correspond to two maximal free line segments tangent to a common object. The free line segments are ordered clockwise, and the arc incident to both vertices is oriented accordingly. As in Figure 2.8, the circular cycle of directed arcs gives the ordering of the 4 bitangents around polygon A; the cycle of the remaining directed arcs gives the ordering of the 4 bitangents around polygon B.
The 3D Visibility Skeleton of a Set of Polytopes
We Þrst make some preliminary deÞnitions in order to explain the types of vertices and arcs of the 3D visibility skeleton of a set of polytopes.
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. The supports of a segment are deÞned to be the supports of the interior of the segment; thus if a maximal free segment ends at a vertex of a polytope, this vertex is not a support. A support polytope of a line is the polytope that the support of the line lies on.
3D Visibility Skeleton Vertices. There are eight types of skeleton vertices. We deÞne them based on [34, 36], and show graphical illustrations in Figure 2.9. Note that unless stated otherwise, no two supports will 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 note a degenerate case of the type FvE vertex, as shown in Figure 2.10. Its set of supports consists of a vertex, a face that the vertex lies on, and an additional edge. Note that in contrast to a non-degenerate FvE vertex, a degenerate FvE vertex has only one edge support. Note also that our deÞnition differs from the discussion in [48], in which this degenerate case of an FvE vertex is not considered to generate a skeleton vertex.
Table of contents :
1 Introduction
2 Background and Related Work
2.1 The Visibility Complex
2.1.1 The 2D Visibility Complex
2.1.2 The 3D Visibility Complex
2.2 The Visibility Skeleton
2.2.1 The 2D Visibility Skeleton
2.2.2 The 3D Visibility Skeleton
2.2.3 The Size Complexity of the Visibility Skeleton
2.3 Overview of the Sweep Algorithm
3 Experimental Study of the Size of the 2D Visibility Complex
3.1 Models
3.2 Experiments
3.2.1 Software
3.2.2 Setting
3.2.3 Experimental Results and Interpretation
3.3 Summary and Bibliographic Notes
4 An Implementation of the Sweep Algorithm
4.1 The Input
4.2 The Output
4.3 Description of the Implementation
4.3.1 Preliminaries: The CGAL Library and Number Types
4.3.2 The 2D Visibility Skeleton
4.3.3 Computing Events
4.3.4 The Event List
4.3.5 Updating the 2D Visibility Skeleton and the Event List
4.3.6 Computing the Ordering of Bitangents
4.3.7 Computing the 3D Visibility Skeleton Vertices
4.4 Complexity of the Implementation
4.5 Software Validation
4.5.1 Visualization
4.5.2 Experimental Verification
4.6 Performance
4.6.1 Running Time in Terms of n and k
4.6.2 Running Time in Terms of the Number of Polygons
4.6.3 Running Time in Terms of Number Types
4.7 Conclusion and Bibliographic Notes
5 The Algebraic Degree of the Predicates
5.1 Computing Lines through Four Lines
5.2 Predicates
5.2.1 Preliminaries
5.2.2 Transversals to Four Lines
5.2.3 Transversals to Four Segments
5.2.4 Ordering Planes through Two Fixed Points, Each Containing a Third (Rational) Point or a Line Transversal
5.3 Experiments
5.4 Discussion
5.5 Bibliographic Notes
6 Experimental Study of the Size of the 3D Visibility Skeleton
6.1 The Visibility Skeleton of a Set of Polytopes
6.2 Setting of the Experiments
6.2.1 The Model
6.2.2 The Experiments
6.2.3 Number Type and Machine Characteristics
6.3 Experimental Results and Analysis
6.3.1 Number of Skeleton Vertices in Terms of n
6.3.2 Number of Skeleton Vertices in Terms of n and k
6.4 Double versus Filtered_exact
6.5 Summary and Bibliographic Notes
7 Computing the 3D Visibility Skeleton
7.1 Preliminaries
7.2 Computational Relations among the Visibility Skeleton Vertices
7.3 Recovery of the Full Skeleton
7.4 Tightness of the Succinct Skeleton
7.5 Discussion
8 Conclusion and Future Work
Bibliography
