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 algorithm for computing CV(S,P) in $O(m^2n^2 \α(n))$ time and $O(mn^2)$ space. Furthermore, we prove that $CV(S,P)$ consists of $O(mn^2)$ surface elements including vertices, edges, and faces.
To generate more realistic images, it is natural that the light sources are modeled as curved shapes such as ellipses, spheres, and ellipsoids. We first propose algorithms for computing CV(S, P) and WV(S, P) from curved light sources S with respect to a single polygon P with n vertices in O(n) time and in O(n log n) time, respectively. For a set P of non-intersecting polygons with a total of n vertices, we propose a divide-and-conquer algorithm for computing CV(S,P) in O(n^2 α(n) log n)$ time and $O(n^2 2^α(n))$ space.
By applying complete and weak visibility in the three dimensional space to shadowing and discontinuity meshing for rendering, we show that shadow boundaries can be effectively provided, and discontinuities of light intensity function are explicitly represented in a mesh.
