Citation
Von Herzen, Brian (1989) Applications of surface networks to sampling problems in computer graphics. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd03132007083552
Abstract
This thesis develops the theory, algorithms and data structures for adaptive sampling of parametric functions, which can represent the shapes and motions of physical objects. For the first time, ensured methods are derived for determining collisions and other interactions for a broad class of parametric functions. A new data structure, called a surface network, is developed for the collision algorithm and for other sampling problems in computer graphics. A surface network organizes a set of parametric samples into a hierarchy. Surface networks are shown to be good for rendering images, for approximating surfaces, and for modeling physical environments. The basic notion of a surface network is generalized to higherdimensional problems such as collision detection. We may think of a twodimensional network covering a threedimensional solid, or an ndimensional network embedded in a higherdimensional space. Surface networks are applied to the problems of adaptive sampling of static parametric surfaces, to adaptive sampling of timedependent parametric surfaces, and to a variety of applications in computer graphics, robotics, and aviation.
First we develop the theory for adaptive sampling of static surfaces. We explore bounding volumes that enclose static surfaces, subdivision mechanisms that adjust the sampling density, and subdivision criteria that determine where samples should be placed.
A new method is developed for creating bounding ellipsoids of parametric surfaces using a Lipschitz condition to place bounds on the derivatives of parametric functions. The bounding volumes are arranged in a hierarchy based on the hierarchy of the surface network. The method ensures that the bounding volume hierarchy contains the parametric surface completely. The bounding volumes are useful for computing surface intersections. They are potentially useful for ray tracing of parametric surfaces.
We develop and examine a variety of subdivision mechanisms to control the sampling process for parametric functions. Some of the methods are shown to improve the robustness of adaptive sampling. Algorithms for one mechanism, using bintrees of right parametric triangles, are particularly simple and robust.
A set of empirical subdivision criteria determine where to sample a surface, when we have no additional information about the surface. Parametric samples are concentrated in regions of high curvature, and along intersection boundaries.
Once the foundations of adaptive sampling for static surfaces are described, we examine timedependent surfaces. Based on results with the empirical subdivision criteria for static surfaces, we derive ensured criteria for collision determination. We develop a new set of rectangular bounding volumes, apply a standard kdimensional subdivision mechanism called kd trees, and develop criteria for ensuring that we detect collisions between parametric surfaces.
We produce rectangular bounding boxes using a "Jacobian"style matrix of Lipschitz conditions on the parametric function. The rectangular method produces even tighter bounds on the surface than the ellipsoidal method, and is effective for computing collisions between parametric surfaces.
A new collision determination technique is developed that can detect collisions of parametric functions, based on surface network hierarchies. The technique guarantees that the first collision is found, to within the temporal accuracy of the computation, for surfaces with bounded parametric derivatives. Alternatively, it is possible to guarantee that no collisions occur for the same class of surfaces. When a collision is found, the technique reports the location and parameters of the collision as well as the time of first collision.
Finally, we examine several applications of the sampling methods. Surface networks are applied to the problem of converting a twodimensional image, or texture map, into a set of triangles that tile the plane. Many polygonrendering systems do not provide the capability of rendering surfaces with textures. The technique converts textures to triangles that can be rendered directly by a polygon system. In addition, potential applications of the collision determination techniques are discussed, including robotics and airtraffic control problems
Item Type:  Thesis (Dissertation (Ph.D.)) 

Subject Keywords:  adaptive sampling; collision; computer graphics; intersection; Lipschitz condition; parametric surfaces; recursive sampling; restricted quadtrees 
Degree Grantor:  California Institute of Technology 
Division:  Engineering and Applied Science 
Major Option:  Computer Science 
Thesis Availability:  Public (worldwide access) 
Research Advisor(s): 

Thesis Committee: 

Defense Date:  20 July 1988 
Author Email:  BrianVon (AT) fpga.com 
Record Number:  CaltechETD:etd03132007083552 
Persistent URL:  http://resolver.caltech.edu/CaltechETD:etd03132007083552 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  943 
Collection:  CaltechTHESIS 
Deposited By:  Imported from ETDdb 
Deposited On:  23 Mar 2007 
Last Modified:  26 Dec 2012 02:33 
Thesis Files

PDF (VonHerzen_b_1989.pdf)
 Final Version
See Usage Policy. 6Mb 
Repository Staff Only: item control page