Complete visibility in the 3D space and its related problems

Abstract

Suppose that a set P of non-intersecting polygons and a light source are given in the three dimensional space. With the light source shining past P, the polygons cast shadows, and in general attenuate or eliminate the light reaching various regions of the three dimensional space. A point s in the light source and a point p in the three dimensional space are said to be visible from s with respect to P if the light shooting from s to p does not intersect any polygon in P. A point is said to be completely weakly visible from the light source S if the point is visible from every point (resp. a point) in S. The completely visible region CV(S,P) weakly visible region WV(S,P)) from S with respect to P is defined as the set of all points in the three dimensional space that are completely (resp. weakly) visible from S. To render a scene environment, we have to compute shading information about the light intensity which is the amount of light source reaching a point in the three dimensional space. The light intensity of a point in CV(S,P) and the complement of WV(S,P) for a single polygon P can be directly calculated. Therefore, identifying of the visible regions from S is helpful to efficiently obtain realistic images. This thesis is concerned with the notion of visibility in the three dimensional space. Most light sources S are approximated as polyhedral shapes such as line segments, polygons, and polyhedrons. In this environment, we propose algorithms for computing CV(S,P) and WV(S,P) from polyhedral light sources S with m vertices with respect to a single polygon P with n vertices in O(m+n) time and O(m+n log n) time, respectively. For a set cal P of non-intersecting polygons with a total of n vertices, we present algorithms for computing CV(S,P). The first results are two divide-and-conquer algorithms which run in $O(m^2n^2α(mn))$ time and $O(mn^2 log mn)$ time, respectively. Here, α(mn) is the inverse of Ackermann``s function. Second, we propose an incremental alg...