Dissertation Abstracts in Computer Graphics Jeffrey J. McConnell SIGGRAPH Education Committee Canisius College Computer Science Department 2001 Main Street Buffalo, NY 14208 (mcconnell.SIGGRAPH@Xerox.com) The response to the publication of abstracts from masters and doctoral theses in computer graphics has been overwhelmingly positive. Since there are limited opportunities to publish in computer graphics, this compendium provides a needed forum for widespread distribution of graduate student research. It is hoped that submission to this project will become part of the normal routine for completion of computer graphics theses. I have been coordinating this compendium since 1987, and though it has been enjoyable, I feel a new perspective is needed, and it is time for me to move onto other projects. This project is being taken over by Cliff Shaffer, Virginia Polytechnic Institute & State University (shaffer@vtopus.cs.vt.edu). I would like to thank Rick Beach, Judy Brown, Steve Cunningham, and Scott Owen for their support and encouragement of this project. I would also like to thank Canisius College and, specifically, the Computer Science Department Office Staff (Jan Dyer, Dan Bailey, and David Pietraszewski) for their help on this project. The deadline for the next compendium is November 15, 1991. All submissions should be of the same form as those in this list, and should be sent to (electronic submission preferred): Cliff Shaffer Department of Computer Science Virginia Tech Blacksburg, VA 24061 (shaffer@vtopus.cs.vt.edu) ------------------------------------------------------------------------ Filtros Espaciais: Estudo Comparativo e Aplicacao em Segmentacao e Classificacao de Imagens Arnaldo de Albuquerque Araujo Lab. de Sinais, Imagens e Comp. Grafica Departamento de Engenharia Eletrica Universidade Federal da Paraiba Campina Grande, PB - Brazil Level: PhD Thesis Date: July 1987 Advisors: Joao Marques de Carvalho / Walter Ameling Ordering Information: Universidade Federal de Minas Gerais Departamento de Ciencia da Computacao Caixa Postal 702 30161 Belo Horizonte, MG - Brazil ABSTRACT: This work is concerned with the problem of automatic discrimination of cardiac tissues by textural analysis of two- dimensional (2-D) echocardiograms, and how image enhancement techniques can be used to improve the results of this discrimination. Preliminary results indicated a success rate of up to 95%, when performing discrimination of tissues by textural anlysis and a stepwise discriminating technique. The results of this study refer to the training phase of an automatic classification system. In order to improve these results, the preprocessing of the images by enhancement techniques (spatial filters) was attempted. Filters were selected by a thorough examination of the existent techniques, followed by a performance analysis. Performance was measured in terms of the algorithms capacity for noise removal with edge preservation, step noise removal, ramp- edge sharpening, features and shape preservation, and computational efficiency. As a result of this investigation a new filtering algorithm, utilizing neighborhood smoothing, was developed. Compared to the other techniques analysed, this new method turned out to be a very efficient solution to the problem of noise removal with edge preservation. The preprocessing of 2-D echocardiograms by spatial filters resulted in a 100% success rate when performing automatic discrimination between normal and pathological tissues. The results of this experiment are presented. Two segmentation methods are considered: segmentation by edge detection and segmentation by region detection. For both cases, preprocessing of the images resulted in reduction of the numbers of parameters (edges or regions) detected and of the number of operations required. ------------------------------------------------------------------------ A Program for Reconstructing Traffic Accidents Alvin Theophilus Campbell, III Department of Computer Sciences University of Texas Austin, Texas 78712 Level: M.S. Date: December 1987 Advisors: Donald S. Fussell and Walter S. Reed Ordering Information: Department of Computer Sciences University of Texas Austin, Texas 78712 Abstract: The reconstruction of traffic accidents is a recent development in engineering. Starting from the evidence left after a collision, investigators attempt to determine exactly how the event happened. The process is accomplished through a combination of science and expert judgment. Experienced engineers sort through a set of possible scenarios to arrive at the one most likely. The engineer can be greatly aided by seeing each of these possibilities acted out in front of him. Restaging of the accident with real vehicles is difficult, expensive, and dangerous. The use of computer animation has none of these drawbacks. This paper describes a system where the engineer uses computer graphics to help visualize an accident. Various evidence is left after a collision. Physical evidence includes skid marks, damage to the environment, vehicle debris, and plastic deformation of the vehicles. Eyewitness accounts of the accident are useful as a guide in the reconstruction process, but only so long as they conform to the physical evidence. This information, along with the laws of physics and dynamics, must be used as the basis for the expert's judgment of what happened. After formulating an opinion based on this evidence, the investigator may use a computer system to help refine his initial opinion into the final verdict. In this thesis we document our experience in designing and implementing such a system on a moderately priced hardware platform. First we review existing systems and explain why none of them is completely appropriate for the task at hand. Next, our design considerations are discussed in some depth. The physically phenomena of interest are detailed, along with the algorithms used to model them. Afterward, we fully describe our user interface and file formats. Finally, we review our experience with the project and make recommendations for similar research efforts. ------------------------------------------------------------------------ Object-Oriented Rendering of Volumetric and Geometric Primitives Judith Challinger Computer and Information Sciences University of California Santa Cruz, California 95064 judy@cis.ucsc.edu Level: M.S. Date: June 1990 Advisor: Jane Wilhelms Ordering Information: Jean McKnight CIS Technical Library Applied Sciences Bldg. University of California Santa Cruz, CA 95064 $10 per copy payable to UC Regents Abstract: Computer graphics has, since its inception, been an invaluable tool for the understanding and analysis of datasets, both computed and acquired. The primary means for visualizing abstract datasets has been to extract two or three-dimensional geometric information from the data and display it using traditional computer graphics rendering techniques. However, this technique is not appropriate for many types of datasets and may result in loss of information in the visualization process. Volumetric datasets consist of a three-dimensional grid of scalar and/or vector values which may not be inherently representable using geometric methods. Recently, researchers have developed specialized techniques for directly rendering volumetric data, however, not many have addressed the need to incorporate these techniques into traditional rendering systems. The objective of this research is to investigate an object-oriented approach to the analysis, design, and implementation of a ray casting rendering system which handles volumetric and geometric primitives directly. Particular attention is paid to the requirement of extensibility of the rendering system. This feature is inherent in an object-oriented design and eases the addition of new types of renderable objects and experimentation with different methods. To demonstrate, the system is extended to include a new primitive for rendering the volumetric results of computational fluid dynamics simulations on three-dimensional curvilinear solution grids. ------------------------------------------------------------------------ Multi-Processor Considerations for Visual Array Analysis Sumit Das Electronic Visualization Laboratory University of Illinois at Chicago Chicago, Illinois, USA Level: M.S. Thesis Date: 1989 Advisor: Thomas A. DeFanti Ordering Information: Maxine D. Brown Electronic Visualization Laboratory University of Illinois at Chicago Box 4348 (M/C 154) Chicago, IL 60680 (312) 996-3002 $10.00 per copy Abstract: Today, computers produce huge amounts of data that can be difficult to analyze by non-graphical means. In addition to graphics, some degree of interactivity is necessary to quickly find trends in data. Software and hardware are available to analyze data graphically, but the hardware tends to be expensive, and software rarely satisfies the needs of every user. Therefore, some guidelines are needed so scientists can decide what equipment they need and how to combine various components to create a working system that will meet the requirements of the intended research. The software that will run on such a system can be developed by the scientist, or through the public domain. This latter is important, because it allows access to source code, so that each researcher can easily modify the system software to match the application. This thesis attempts to outline the options for creating the hardware system, and to show one possible approach to designing an easily modified software system for scientific visualization. Such a system has been implemented, and the design and implementation of a prototype application, a tool for the exploration of two-dimensional numerical data, is discussed. ------------------------------------------------------------------------ Parallelization of the Radiosity Model James G. Dugger, Jr. Computer Science Department Southern Illinois University Carbondale, IL 62901-4511 Level: M.S. Thesis Date: June, 1989 Advisor: Michael S. Wainer Ordering Information: Computer Science Department Southern Illinois University Carbondale, IL 62901-4511 (618) 536-2327 Abstract: Radiosity is an illumination model which accurately describes the diffuse reflection of light between surfaces in an "enclosed environment". The basis of the radiosity method is founded in radiation heat transfer. Calculation of intensities is found through the solution of a system of linear equations. The geometric relationship between each surface in the environment provides a matrix of form factors, which gives the fraction of light leaving each surface and arriving at another. Generation of the form factors is by far the most costly procedure with 0(n2) work and storage requirements. Specular reflections have been considered in the most recent work which offers an excellent shading model for realistic rendering. Progressive refinement of the image can reduce storage costs by calculating the subset of form factors which have an appreciable effect on the final image quality. This thesis presents parallel hemispheric and hemi- cubic algorithms which improve time cost in the form factor calculation. Additionally, the progressive refinement combined with one of the parallel algorithms reduces both time and storage costs. Results show nearly linear speedup on a shared memory, multi-processor machine. ------------------------------------------------------------------------ UIPEX: Design of the Application Programmer Interface Parris K. Egbert egbert@cs.uiuc.edu Department of Computer Science University of Illinois at Urbana-Champaign 1304 West Springfield Avenue Urbana, IL 61801 Level: M.S. Date: Spring 1990 Advisor: William J. Kubitz Ordering Info: Documentation Center Department of Computer Science University of Illinois at Urbana-Champaign 1304 West Springfield Avenue Urbana, IL 61801 Abstract: In an attempt to provide powerful 3D graphics in a windowing environment, PHIGS, PHIGS PLUS, and PEX have been developed. PHIGS and PHIGS PLUS provide an environment for producing complex 3D images. PEX incorporates this environment into the X Window system. This thesis discusses UIPEX, the University of Illinois implementation of PEX. The main focus of the thesis is on the application programmer interface (API) level. The manner in which PHIGS and PEX mesh is discussed. An overview of the PEX architecture is given, with an explanation of the responsibilities and functionality of the API level. In addition, various design options are presented, particularly in the areas of PHIGS/PEX structure mapping, multiple-server architecture, and PHIGS input devices. Possible design choices are presented. The design decisions we made in our implementation are then given, along with the rationale behind those decisions. Finally, a critique of PHIGS is presented. Although PHIGS, as a graphics standard, has many desirable characteristics, it also carries with it many shortcomings. The strengths and weaknesses of PHIGS are discussed, with possible solutions for overcoming the weaknesses. ------------------------------------------------------------------------ Spatial Query Languages Max J. Egenhofer Department of Surveying Engineering 107 Boardman Hall University of Maine Orono, ME 04469, USA Level: Ph.D. Thesis Date: Spring 1989 Advisor: Andrew U. Frank Ordering Information: National Center for Geographic Information and Analysis University of Maine Orono, ME 04469 (207) 581-2114 max@mecan1.bitnet Abstract: The purpose of this thesis is to investigate possible languages through which humans may request spatial information stored in computerized information systems, such as geographic information systems or systems for CAD/CAM. The investigations have been motivated by the recognition that traditional database query languages show severe shortcomings when they are applied to spatial data handling. In order to identify the specific concepts of a spatial query language, those concepts have been investigated that humans tend to use when they perceive or exchange spatial information, e.g., graphical representation of spatial data in which humans understand most naturally geometric concepts. The investigations identified a set of eight fundamental spatial concepts to be used as a methodology for the design of spatial query languages. A specific spatial query language has been designed by extending the structured query language SQL with the concepts identified. The new language, called Spatial SQL, is a superset of SQL, i.e., all traditional SQL concepts and commands apply for non-spatial data. Particular effort was put into the treatment of graphical representation with the development of a specific language to describe the graphical renderings of spatial data with colors, patterns, and cartographic symbols; to provide for dynamic graphical representation by adding, removing, or highlighting query results on existing screen drawings; and to establish a spatial context in which graphical results become understandable. Spatial relationships are necessary in spatial query languages to allow users to formulate queries with spatial conditions, such as neighbor, inside, intersect, etc., in combination with other selections on attributes. Particular emphasis was put on topological relationships. Investigations into the mathematical formalisms of concepts in algebraic topology led to a theory of topological relationships which supports the correct processing of such spatial queries. The major results of this study are a methodology for the design of spatial query languages; a demonstration of the extension of an SQL-like language for spatial data handling; the conceptual separation of retrieval and display in a spatial query language; and a formal approach according to which different topological relationships may be identified. ------------------------------------------------------------------------ Variations of Tilings and Choice of Color Spaces for Color Image Compression William Gale Electronic Visualization Laboratory University of Illinois at Chicago Chicago, Illinois, USA Level: M.S. Thesis Date: 1989 Advisor: Thomas A. DeFanti Ordering Information: Maxine D. Brown Electronic Visualization Laboratory University of Illinois at Chicago Box 4348 (M/C 154) Chicago, IL 60680 (312) 996-3002 $10.00 per copy Abstract: In 1979, Delp and Mitchell introduced Block Truncation Coding (BTC), a novel approach to data compression of grey scale images, which was distinguished by its relative simplicity during compression and reconstruction of images. In 1986, Campbell et al., introduced the Color Cell Compression Algorithm (CCC), which extended the Block Truncation Coding scheme to color images, while maintaining the relative simplicity of the compression process, and the speedy reconstruction of images. Unfortunately, visible aliasing artifacts are induced in compressed images that undergo block truncation-based compression -- a fact acknowledged, but not dealt with, by authors of the BTC and CCC approaches to compression. In this thesis, we examine the BTC and CCC approaches to compression in detail, paying special attention to the deficiencies inherent with the "block" approach used in block truncation-based compression. We introduce various non-block shaped cells and tilings which overcome the artifacts induced with block shaped cells and tilings, yet induce other visible aliasing artifacts in the process. We also introduce the YIQ Compression Algorithm, which explores the benefits of block truncation-based compression in a different color space, the YIQ color space, in contrast with the RGB color space commonly used for color images. This algorithm attains data rates of 2.63 bits/pixel for compressed images and preserves greater luminance information than CCC-based compression, yet preserves less chrominance information which produces stronger aliasing artifacts than CCC-based compression. From these explorations, we gain a new understanding of the nature of the aliasing artifacts present in block truncation-based forms of compression, and conclude with a new model for block truncation-based compression which calls for adaptive compression and allows for stepwise refinement of compressed image quality. ------------------------------------------------------------------------ Digital Representations of Karst: A Prospectus John H. Ganter Deasy GeoGraphics Laboratory Department of Geography The Pennsylvania State University University Park, Pennsylvania Level: M.S. Thesis Date: Spring 1989 Advisor: Alan M. MacEachren Ordering Information: John H. Ganter National Center for Geographic Information and Analysis SUNY at Buffalo Buffalo NY 14260 716-636-2545 ganter@cs.buffalo.edu $7.00 per photocopy Abstract: Karst is a landform characterized by water movement through caves rather than on the land surface. The scientist and engineer collect data at a multitude of scales from the microscopic (chemistry and mineralogy) to topographic mapping and satellite imagery. Integrating and visualizing the relations between this data, which lies both above and below the land surface is challenging. This thesis examines the expert knowledge of scientists and engineers, and presents a needs analysis for data structures, display techniques and analytical routines. It draws on the literatures of geology, geographic information systems (GIS), CAD and cognitive science. The costs and benefits of spatial composition approaches (CSG, B-reps) and spatial decomposition approaches (Voxels in various hybrid indexing schemes) are analyzed and discussed. The thesis is intended as a model for dialogue between earth scientists, software engineers and programmers. It includes numerous illustrations and a complete index. ------------------------------------------------------------------------ An Analysis and Modification of Shao's Radiosity Method for Computer Graphics Image Synthesis David E. Hall The George W. Woodruff School of Mechanical Engineering Georgia Institute of Technology Atlanta, GA 30332 Level: MS Date: March 1990 Advisor: Holly Rushmeier Ordering Information: Holly Rushmeier The George W. Woodruff School of Mechanical Engineering Georgia Institute of Technology Atlanta, GA 30332 Abstract: The radiosity method was introduced to computer graphics to accurately model illumination for the creation of realistic, synthetic, computer generated images of scenes. Two limitations of the original radiosity method were the restriction to diffusely reflecting surfaces, and the extended length of time required to generate an initial image. Shao et al. developed a radiosity method capable of determining the effect of non-diffuse surfaces on illumination. Cohen et al. presented the progressive refinement radiosity method to allow the rapid generation of initial images. In this thesis, Shao's method is analyzed, and corrections to the original formuation are presented. Shao's method is then combined with Cohen's progressive refinement approach. The adaptive discretization of specular surfaces is introduced in the progressive refinement to increase the accuracy of the radiosity solution. Finally, Shao's method is modified to efficiently model the effect of true bidirectional reflectance using the concept of a "reflectance hemisphere" to determine and store the outgoing directional characteristics of the energy leaving a bidirectional surface. Results and images for this bidirectional radiosity method are given. ------------------------------------------------------------------------ Image Space Algorithms for Visualizing Quaternion Julia Sets John C. Hart Electronic Visualization Laboratory University of Illinois at Chicago Chicago, Illinois, USA Level: M.S. Thesis Date: 1989 Advisor: Thomas A. DeFanti Ordering Information: Maxine D. Brown Electronic Visualization Laboratory University of Illinois at Chicago Box 4348 (M/C 154) Chicago, IL 60680 (312) 996-3002 $10.00 per copy Abstract: In 1982, Alan Norton discovered that certain Julia sets did not reside exclusively in the Complex Plane, but leaped into the four-dimensional spaces of the Quaternions as well. The Quaternion extensions were non-trivial and illustrated certain properties of Julia sets not visible in planar sections. Unfortunately, the only algorithm developed to visualize these objects in 3-D was object-space based. This required the efficient storage of millions of points, thus limiting the task to large mainframes. By using more efficient image-space algorithms, the same 3-D Julia sets may be generated and rendered with no more than standard graphics workstation resources. This document contains a full discourse on Analytical Dynamics and Quaternion Algebra, and a discussion of two image-space algorithms that generate and render 3-D Julia sets. ------------------------------------------------------------------------ On the Computational Geometry of Pocket Machining. Martin Held Institut fuer Computerwissenschaften und Systemanalyse Universitaet Salzburg, Austria Level: Ph.D. Date: May 1990 Advisors: Johann Linhart and Horst D. Clausen Ordering Information: Martin Held Institut fuer Computerwissenschaften und Systemanalyse Universitaet Salzburg A--5020 Salzburg Austria (Europe) phone: +662 8044 6752 e-mail: <1held@edvz.uni-salzburg.ada.at> $10 per Xerox copy. Abstract: Numerically controlled machining of mechanical parts requires various working processes such as 2D--2.5D milling of arbitrarily shaped planar areas (`pockets'). This thesis describes a computational geometry approach to handling geometrical and technological problems arising from pocket machining. Contour-parallel (`offset') as well as direction-parallel (`zigzag') machining are investigated. Topics dealt with comprise the selection of tool sizes, the generation of tool paths, and the optimization of tool paths with respect to practical machining objectives. Seen from a practical point of view, full details including implementational issues of the pocketing algorithms are given. This practice-minded approach is embedded into a thorough theoretical framework that enables to state concise definitions and to prove the correctness and the complexity of each presented algorithm mathematically. The part of the thesis dealing with contour-parallel milling centers around the concept of generalized Voronoi diagrams. An algorithm for computing Voronoi diagrams of multiply-connected planar areas bounded by straight lines and circular arcs is presented and its correctness is proved. Voronoi diagrams are used for efficiently carrying out the required offsetting tasks. Based on Voronoi diagrams, the concept of so-called `monotonous areas' is introduced. Monotonous areas serve as a high-level abstraction of the pocket geometry and are well-suited for performing path-planning tasks among sites of objects. In the particular application to pocket machining, Voronoi diagrams and monotonous areas are the key data structures that help to generate correct and (near) optimum tool paths. In the part on direction-parallel milling, the investigation focusses on avoiding unnecessary tool retractions. This goal is realized by using a mesh-like data structure and by designing an algorithm for determining (near) optimum inclinations of the zigzag reference line. ------------------------------------------------------------------------ Interaction with Spatial Information Systems: From Constructing towards Editing Geometric Models (in German) Werner Kuhn Institute of Geodesy and Photogrammetry Swiss Federal Institute of Technology ETH Hoenggerberg 8093 Zurich, Switzerland Level: Ph.D. Thesis Date: Spring 1989 Advisors: Alessandro Carosio and Hans-Peter Frei Ordering Information: Werner Kuhn National Center for Geographic Information and Analysis University of Maine Orono, ME 04469 (207) 581-2118 Bitnet: Kuhn@mecan1 Abstract: This thesis treats human-computer interaction for the acquisition of geometric data in spatial information systems. It proposes to design this interaction as constraint-based editing of geometric models, rather than as geometric constructing. After an analysis of practical tasks and solution methods, problem solving theory is applied to identify two possibilities for the allocation of subtasks and the degree of communication between user and system: (1) The user develops and describes solutions as sequences of construction steps which the system executes. Such a computer aided geometric construction reflects an automation of manual procedures. (2) The user describes tasks by geometric constraints which the system then tries to satisfy. Such descriptions of construction tasks represent geometric models which can subsequently be edited. The means for describing geometric models by constraints are developed in three steps: First, differential geometry is used to determine the elementary properties and relations sufficient to express general geometric constraints in the plane. Then, formal logic serves to define a high-level language for the specification of constraints in geometric terms. Finally, an interaction language is designed in which users can sketch geometric models and refine these by declaring constraints. A least squares adjustment is proposed to solve the systems of equations representing the geometric constraints. This allows for treating under- and over-constrained situations as well as uncertain constraints. The sketched geometric models provide the necessary approximate solutions and allow an incremental solution. The thesis has three main results: (1) A constructive and a declarative interaction model for geometric data acquisition are identified. The framework from the theory of problem solving can be used to analyze and design user interfaces in other areas as well. (2) The Geometric Constraint Calculus, a language for complete formal descriptions of plane geometric models, is defined. It provides the basis for a declarative interaction and can serve as a high-level language for geometric knowledge representation in other applications. (3) The practical implications of adopting the declarative interaction model are illustrated by a design of an editor for geometric models. The feasibility of the approach has been demonstrated by a prototype implementation. ------------------------------------------------------------------------ Contribution to the study of graphic systems, software and hardware architectures. (French). Patrick-Gilles Maillot. Sun Microsystems, inc. Graphics Products Division, 2550 Garcia ave. Mountain View, CA 94043 Level: Ph.D. Date: July 1986 Advisor: Denis Vandorpe Ordering information: University Claude Bernard, Lyon I 43 bd du 11 Novembre 1918, Laboratoire d'informatique graphique, bat 410. 69100 Villeurbanne, France. Abstract: This thesis presents a hardware and software study of graphic systems. It is divided in two parts. The first one is a general study of the basic concepts of computer graphics and their evolution. The second part is a more practical approach. It contains some elements of graphic software based on the realization of an intelligent graphic display terminal, and describes a collection of algorithms to perform geometrical 2D and 3D transformations, quaternion manipulations to code movements in a 3D space, 2D and homogeneous 3D line and polygon clippings, B splines and circle clippings, as well as a fast method to scan convert 2D and 3D polygons, while performing hidden lines removal, even when intersecting non-planar 3D polygons. The last series of algorithm describe some look-up tables manipulations. ------------------------------------------------------------------------ The Application of Fast Visualization Techniques for the Graphical Interactive Design Process Gert-Andreas Meissner Institut for Naval Architecture and Marine Engineering Technical University of Berlin Salzufer 17-19, Secr.SG 10 1000 Berlin 10 Germany Level: Ph.D. Date: April 1990 Advisor: Prof.Dr.-Ing. Horst Nowacki Ordering Information: Institut of Naval Architecture and Marine Engineering Technical University of Berlin Salzufer 17-29, Secr.SG 10 1000 Berlin 10 Germany Abstract: Constructing fast visualization techniques, as a means for computer-aided graphical interactive design, is nowadays becoming a research topic of increasing interest in the area of computer-aided design (CAD). This task however cannot be accomplished in the context of a conventional graphical system. This is due to the fact that integrating visualization-in-scientific-computing (ViSC) within an interactive design process is very demanding from the point of view of processing time of the representation algorithms as a prerequisite of user- friendliness and interactivity of the graphical interactive design system. The present thesis starts with a state of the art on the pertinent software and hardware techniques. A systematic process is then firstly developed for selecting alternative graphical-representation primitives and attributes for depicting physical or engineering-relevant calculation or measurement results. The associated data interface is also described in detail, involving scalar, vectorial, or tensorial data correlated to line-, surface-, or volume- oriented geometries. Within the context of the afore- mentioned systematic process, existing methods are further elaborated, from the acceleration point of view, and some new methods are developed. The obtained results are treated by an object-oriented graphical interactive design system in which the user interface is of special importance for the acceptance of the system and which is conceived on the basis of an open-system architecture. In this connection, fast picture generation and past picture updating are achieved by relying on advanced interaction methods. The efficiency of the systematic process and the programs installed therein are tested by constructing pictures for various practical examples arising in diverse application areas. ------------------------------------------------------------------------ Simulating Cloth using a Mixed Geometric--Physical Method Isaac Rudomin Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 Level: Ph.D. Date: August 1990 Advisor: Norman I. Badler Ordering Information: Available from University Microfilms Abstract: The objective of this dissertation is to model the shape of a piece of cloth draped over rigid bodies. The problem of cloth modeling has been studied by Feynman, Weil, Terzopoulos and Thingvold. They model pieces of cloth as a mesh of discrete points to which forces or constraints are applied, and are basically iterative relaxation methods. The methods of Feynman, Weil and Terzopoulos can yield pleasing results, but are relatively costly because they require the use of a fine mesh. Thingvold's method is a hierarchical B--spline based approach that starts with a coarse physical model and refines it where the geometry or physical constraints require it. Another approach entails finding some global information that may guide the process. This global information can be used to construct an approximation to the shape of the cloth. This approximation is helpful by itself and is the main focus of this dissertation. It can also be used to give a better starting point for the other physical methods, or to provide global information to these other methods. The main contribution of this dissertation is to describe a geometric method that yields this global information, as well as how to use it in combination with physical methods to yield a hybrid geometric--physical method. ------------------------------------------------------------------------ Parallel Adaptations of Stochastic Modeling Techniques for Computer Graphics Michael S. Wainer Department of Computer and Information Sciences University of Alabama at Birmingham Birmingham, Alabama Level: Ph.D.Dissertation Date: Fall 1987 Advisor: Michael A. McAnulty Order Information: Department of Computer and Information Sciences University of Alabama at Birmingham Birmingham, AL 35256 (205) 934-2213 Abstract: Realistic models of natural objects for use in computer graphics require an enormous amount of information. Traditional methods employ large data bases which are unwieldy to enter and manipulate. Stochastic procedural models greatly diminish these problems by performing data amplification on a small data base and, using a parameter constrained Stochastic process, mimic the richness found in nature. Time constraints on real time graphics applications are severe and even applications which are not real time (production of movie sequences) can benefit from a reduction of execution time. Speedups through uniprocessor architectures are almost exhausted leaving parallel architectures as the only hope for major hardware improvements. Many different forms of parallel architectures exist, each with its own balance of resources. Often the resource balance of sequential machines differs drastically from parallel machines. Since resource balance is a major determiner in the optimization of software, there are many dangers in blindly moving sequential software to parallel computers (especially optimized software). Of major concern is the coupling between modeling and rendering modules (special cases of numerical simulation and analysis modules). Special purpose architectures tend to suffer from an offloading problem since their processing resources outweigh their memory and communications resources. General purpose massively parallel processors are proposed as a solution since they can increase the processing load which effectively balances the system. The effectiveness of massively parallel architectures for Stochastic modeling is demonstrated using examples from Stochastic subdivision, iterated function systems and chaotic dynamical systems. A general method for mapping recursive generating procedures onto the array is developed. Massively parallel algorithms scale well to different size machines and compete well with special purpose architectures. Software development not constrained by sequential code often leads to powerful generalizations as adaptations to parallel machines are made. As computer graphics models become increasingly complex and other scientific modeling more dependent on graphics, the generality and computing power of massively parallel processors will become an increasingly attractive computing tool. ------------------------------------------------------------------------ Human Strength Database and Multidimensional Data Display Susanna Wei Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 Level: Ph.D. Date: August 1990 Advisor: Norman I. Badler Ordering Information: Available from University Microfilms Abstract: We study human figure modeling with strength capability to achieve more realistic and natural human motions in a task simulation. First, we develop a strength model and incorporate it in the computer graphics human figure definition. Strength information (maximum torques) is defined as muscle group strengths and is stored on a joint degree of freedom basis in the human figure model. Modeling strength in terms of muscle group strength allows different people to possess different capacities in different muscle groups. Each muscle group strength is modeled as a function of body position, anthropometry, gender, handedness, fatigue, and other strength parameters. In terms of body position, we choose a more generalized model that takes the effects of adjacent joint angles into consideration. To facilitate the use of strength information (data) in the human-task simulation environment, we have designed and implemented a relational strength database system. Because strength data are sparsely measured over the space of input parameters, we develop interpolation and scaling techniques for the system to estimate the strengths when they are not measured directly. To allow a user to have easy and effective access to the strength database, we have also designed and implemented an interface. To further enhance the effective use of the strength information, we develop graphical methods to display the multidimensional characteristics of the strength data. We use human figures together with two or three dimensional graphical symbols, colors, and other computer graphics techniques so that the user can visualize the effects of different parameters on strength. These displays give a dynamic changing view of the effects of parameters on strength, and illustrate safe and forbidden body postures (or regions) in terms of strength capability. ------------------------------------------------------------------------ Concepts and Experiments for Automating the Generalization of Digital Terrain Models (German) Robert Weibel University of Zurich GIS Laboratory Department of Geography Winterthurerstrasse 190 CH-8057 Zurich SWITZERLAND Level: Ph.D. Date: December 1989 Advisor: Kurt E. Brassel Ordering Information: Same as Institution Abstract: One of the most serious limitations to a meaningful use of geographic information systems (GIS) is the current lack of suitable generalization techniques. Procedures for automated generalization are needed for two major reasons: to ensure optimal readability of GIS display products (i.e. cartographic generalization), and to enable the building of multi-resolution, multi-purpose spatial databases (to reduce costs of data acquisition, increase data consistency, etc.). These problems apply equally well to digital terrain models (DTM), which are a vital component of GIS. The objective of this thesis was to develop techniques for structure- and purpose-dependent automated terrain generalization. "Structure-dependent" implies that the generalization approach be adaptive to the given terrain characteristics (i.e. the topographic structure); likewise, "purpose-dependent" means an adaption to the constraints of the generalization process (display scale, display purpose, etc.). To achieve these objectives three basic alternative methods with different characteristics were developed: "global filtering", "selective filtering", and "heuristic generalization". Selection of an appropriate generalization method depends on the complexity of the terrain (as determined by a terrain classification procedure), as well as the controls of generalization. Procedures for global filtering relate to position-invariant filtering techniques in image processing. Selective filtering involves an iterative procedure that identifies the subset of points of a DTM whose elevation difference from the original surface exceeds a user-defined tolerance. Thus, only the most significant points of the terrain surface are retained. Both global and selective filtering are mainly used for low and medium complexity terrain, as well as for minor scale reductions. However, selective filtering seems to be applicable to a wider range of purposes; it can also be used for controlled data reduction on DTM's. The method of heuristic generalization attempts to emulate principles of manual practice. As in traditional cartography, the structure lines (drainage channels, ridges, etc.) are used as a skeletal representation of topography and as a basis for generalization. These lines are extracted from the DTM and connected to form a tree-like network called the structure line model (SLM). The SLM can then be modified by a number of generalization operations - selection, simplification, combination, and displacement - yielding a reduced-scale SLM. The resulting generalized DTM is reconstructed through interpolation from the generalized SLM. Heuristic generalization offers the possibility of addressing landforms as individuals. It is intended for use on rough terrain. It is also the only approach that allows the fundamental transformations (i.e. combination and displacement) necessary to achieve major scale reductions. The major generalization functions of our design have been implemented as prototypes. Some of the heuristic processes have been simulated by interactive procedures. As a mid-term goal for future research we propose the development of a high-level interactive editor for terrain generalization based on the components of our strategy. ------------------------------------------------------------------------ Computer Reconstruction and Display of Three-Dimensional Scalar Data Kevin Wu Stanford University Electrical Engineering Department Stanford, CA 94305 Level: Engineer Date: May 1988 Advisor: Lambertus Hesselink Ordering Information: Lambertus Hesselink Stanford University Department of Aeronautics and Astronautics Durand Building, Room 359B Stanford, CA 94305-4035 Abstract: In the past two decades, the scientific and engineering communities have witnessed revolutionary breakthroughs in techniques that gather information about physical three-dimensional quantities. Medical scanners provide physicians with a noninvasive means of detecting internal lesions in patients by employing the modalities of computer-assisted X-ray tomography and magnetic-resonance imaging. In fluid-flow visualization, modern optical diagnostics probe the behavior of fluids in motion, and supercomputers numerically simulate the dynamics. These and many other high-volume generators of information contribute to an emerging new field known as Visualization in Scientific Computing. Its goal is to give scientists and engineers the ability to perceive and interpret complex data sets through computer-based visualization technology. This thesis specifically concentrates on computer methods for reconstructing and displaying the structures in three-dimensional scalar data, with emphasis on visualizing the interior structures. In the medical imaging and fluid-flow visualization examples given above, the sources of three-dimensional information often produce data in a common format: a sequence of digital images stacked parallel to each other along an axis, or equivalently, a three-dimensional rectangular lattice. From this starting point, we investigate a collection of reconstruction and display methods including translucent surface representations, interactively controlled motion of skeletal structures, cubic spline contour surfaces, and interactive surface peeling. Interactive peeling of smooth opaque contour surfaces is the best of these methods: it gives excellent perception cues.