In computer graphics, there have been developed various kinds of rendering methods for the last three decades, to generate more realistic images faster. An important issue in rendering is to develop a data structure which provides efficient visibility oprerations, because the most of the rendering time is spent for performing them.
Kwon et. al[8] present a new ray classification scheme, called directed line classification, that considerably reduces memory consumption while preserving the time efficiency of Arvo and Kirk[1]'s scheme. In that scheme, they use two kinds of cell division scheme such as uniform subdivision, hierarchical subdivision. In the hierarchical subdivision scheme, they subdivide the boundary faces of both origin and destination at the same time.
In this thesis, we present a new cell subdivision scheme, called origin first hierarchical subdivision, which gives an adaptive structure reducing memory requirement and an improvement for more applicability. Our scheme subdivides the origin faces first, and then subdivides destination faces. By using this scheme, each cell has a more adaptive shape to the spartial distribution of objects to have different sizes of origin and destination faces. This subdividing scheme is effective for point-to-region or region-to-region visibility operations. We can further reduce memory requirements by using candidate elevation and cell merging which take a good advantage of the coherency between the objects saved in each cells which appeared near location in data structure.
Our experiments indicate that the origin first hierarchical subdivision scheme improves the efficiency of the rendering process for various types of visibility operations in the advanced rendering applications such as ray tracing and radiosity.
