THESIS
2000
ix, 38 leaves : ill. ; 30 cm
Abstract
In computer graphics, most polygonal surfaces are rendered as a collection of triangles. Rendering a triangle requires the coordinates of its three vertices. Since the speed of rendering is bounded by the data rate, reducing the amount of data will make rendering faster. This can be attained by decomposing a surface patch into triangle strip(s) where a triangle strip is an ordered list of triangles such that two consecutive ones share an edge. To display a triangle strip, we can set up a pipeline with two vertices of the first triangle (one being the unshared vertex), and then we only need to transmit one additional vertex to render each subsequent triangle. The ideal case is that one strip suffices....[
Read more ]
In computer graphics, most polygonal surfaces are rendered as a collection of triangles. Rendering a triangle requires the coordinates of its three vertices. Since the speed of rendering is bounded by the data rate, reducing the amount of data will make rendering faster. This can be attained by decomposing a surface patch into triangle strip(s) where a triangle strip is an ordered list of triangles such that two consecutive ones share an edge. To display a triangle strip, we can set up a pipeline with two vertices of the first triangle (one being the unshared vertex), and then we only need to transmit one additional vertex to render each subsequent triangle. The ideal case is that one strip suffices.
We obtain two algorithms for triangulating a polygon to produce the minimum number of strips among all possible triangulations. The first algorithm works for simple polygons and runs in O(n
3) time, where n is the number of polygon vertices. The second algorithm works for polygons with holes and runs in O(n
2h+3) time, where h is the number of holes. These two algorithms are based on dynamic programming paradigm. Next, we study the problem of computing the minimum number of strips for a triangulated polygon possibly with holes. This problem is equivalent to partitioning the dual graph of the triangulated polygon into a minimum number of paths. When the dual graph is a tree, the minimum number of paths can be computed in O(n) time. For the dual graph that contains cycles, we study the special cases of deciding if the dual graph contains a Hamiltonian cycle or a Hamiltonian path. Under a special condition, we can decide in O(n) time the existence of a Hamiltonian cycle, and in O(n
3) time the existence of a Hamiltonian path. The cycle or path, if it exists, can be constructed in the same time bound.
Post a Comment