M.S./Ph.D. Abstracts Compendium: 1988 Jeffrey J. McConnell SIGGRAPH Education Committee Canisius College Computer Science Department 2001 Main Street Buffalo, NY 14208 mcconnel@canisius Worcester Polytechnic Institute Computer Science Department 100 Institute Road Worcester, MA 01609 jmcconn@wpi.BITNET (1987-1988 Academic Year) This paper is the first of a yearly compendium of abstracts from Masters and Doctoral Theses in computer graphics. This compendium is being provided as a guide to the work being done in computer graphics by graduate students, and any requests for further information should be directed at the institution involved. This year's compendium has 58 entries from 23 institutions. This list is by no means complete, as there are a few prominent graduate schools missing. It is hoped that future participation will be more wide-spread. The deadline for the 1989 compendium will be September 1, 1988. Submissions should follow the format below, and can be sent (e-mail preferred) to either of the addresses above. I would like to thank Canisius College and WPI for their support of this project. Specifically, I would like to thank Veronica Serwacki, Kim Smith, and Ken Downey, all of Canisius College, for entering those abstracts arriving in paper form. I, however, take full responsibility and apologize for all errors. ------------------------------------------------------------------------ Title: Models for Stochastic Texture Generation Author: Norman Angerhofer Level: M.S. Institution: Department of Computer Science University of Utah Salt Lake City, UT Date: December 1985 Advisor: Spencer W. Thomas Ordering Information: Sue Lloyd 3419 MEB University of Utah Salt Lake City, UT 84112 (Send $5.40 plus postage) Abstract: This work explores current models of textures for image synthesis and analysis, with an emphasis on generation of stochastic textures. Digital signal processing techniques are applied to create a general and robust model for the generation of stochastic textures: - Martingale sequences are analyzed, and it is determined that the best way to develop martingale sequences is through the use of convolution. - Methods of convolution with white noises are discussed. - A number of ways to obtain the point spread function or texture filter for a target texture are developed. Important ways include (1) the use of preexisting texture samples and (2) the construction of ensemble averages. - The theoretical framework behind the robustness of these methods is developed. - Stochastic textures which have been generated with these methods are then used in the rendering process to give greater realism to objects in computer-generated images. ------------------------------------------------------------------------ Title: A New Approach to the Hidden Surface Removal Problem for a Contour Defined Environment Author: R.P. Balasubramanian Level: M.S. Institution: The School of Computer Science P.O. Box 4400 University of New Brunswick Fredericton, N.B. E3B 5A3 CANADA Date: August 1984 Advisor: Uday G. Gujar Ordering Information: none Abstract: Determination of the visible portions of a modelled three dimensional environment has been a topic in computer graphics of longstanding interest and critical investigation. It is needless to emphasize the significant role hidden surface removal algorithms have played, that three dimensional computer graphics cannot afford to do without it. A critical analysis of the previous algorithms is made and a classification scheme is developed. The algorithms are classified into two major categories: those that operate at object resolution and those that work at image resolution. The object resolution algorithms are further classified into three different classes based on the different forms of output, types of computations performed and the form of coherence capitalized: (1) object space algorithms (2) object image space algorithms (3) polygon algorithms The methodologies and modes of operation of the various algorithms as well as the operations and tests common to them are studied and summarized. A new approach to the hidden surface removal problem for a contour defined environment is presented. The structure used to define the environment is quite different from the conventional object description methods. A simple input data structure which does not demand any topological connectivity relationships from the user has been designed. The user is also not constrained upon ordering the points on a contour in accordance with any sign conventions. The output from the algorithms is a set of polygons guaranteed not to overlap in X-Y. This form of output has several advantages over its counterparts. This algorithm relies on object coherence as well as on polygon area coherence. Several polygon grouping techniques, which drastically reduce the computation time per polygon, have been introduced. The key to the new hidden surface removal algorithms is the polygon clipper. A detailed analysis of Weiler and Atherton's polygon clipper has been made. The singularities in the clipping algorithms have been identified and classified. Solutions to the above problems have been derived and the algorithm is extended to handle a class of degenerate polygons. The new hidden surface algorithm has been implemented as a FORTRAN callable subroutine HIDE on IBM 3081. A perspective transformation routine PERTRN has also been written. These two routines enable the user to model a three dimensional environment. ------------------------------------------------------------------------ Title: A Graphics Authoring System for Teacher Produced CAI Author: Tom Barstow Level: M.S. Institution: Worcester Polytechnic Institute 100 Institute Road Worcester, MA 01609 Date: 1983 Advisor: Mark R. Ohlson Ordering Information: none Abstract: On of the major impediments to progress in computer aided instruction is the lack of courseware (CAI lessons). One solution to the courseware problem would be for teachers to prepare their own materials using appropriate tools. In this thesis, a graphics authoring system was designed that would allow a teacher to create diagrams specially suited for CAI lessons. The four design goals were to make the proposed system easy to use, act like an intelligent sketchpad, be capable of producing interactive diagrams, and be capable of creating flexible diagrams. The design, conceived as a modified CAD system, includes features to meet these goals. A prototype system was implemented and observations on the effectiveness of both the implementation and the design were made. ------------------------------------------------------------------------ Title: Computer-Based Keyframe Animation of Shape Distortion Author: Edward Wesley Bethal Level: M.S. (Computer Science) Institution: The University Of Tulsa Department Of Computer Science 600 South College Avenue Tulsa, Oklahoma 74104-3189 (918) 592-6000 Date: Summer 1986 Advisor: Samuel P. Uselton Ordering Information: University of Tulsa McFarlin Library Duplicating Services (also available through interlibrary loan) Abstract: This paper presents a method enabling the "in-betweening" of two topologically different objects. Previous animation systems have emphasized motion and its control, while shape animation has not extended beyond limited variations of shape. The goal is to allow one object of arbitrary shape to be 'changed' into another object, also of arbitrary shape. In this approach, the source and target objects are described geometrically as a collection of polygons. An outline for an extension to objects built from parametric patches is presented as well. The two objects from the start and finish keyframes are compared in a face by face manner in a search for topological differences. While an exhaustive comparison of the objects is occurring, the original objects represented as duals in an ordered, rooted tree format, are subject to a reconstruction process. The objects resulting from reconstruction are identical in topological properties, differing only in geometric attributes. ------------------------------------------------------------------------ Title: Approximate Image Generalization with Realistic Effects Author: Martin Joseph Biernat Level: Ph.D. Institution: Illinois Institute of Technology Department of Computer Science Chicago, Illinois 60616 (312) 567-5150 Date: August 1986 Adviser: Dr. Thom Grace Ordering Information: University Microfilms 300 North Zeeb Road Ann Arbor, Michigan 48106 (800) 521-0600 Abstract: Natural phenomena by the human visual system are extremely difficult to render in a computer generated image. Shadows and the reflection and refraction of light are the most common examples. One modeling method is to perform many time consuming calculations to precisely model the effect of light as described by the laws of physics. This can be too costly to be practical. This thesis describes a new method for approximating umbrae and penumbrae using ray tracing without significantly increasing the computation time or storage space requirements. The same theory is then applied to the direct reflection of light to improve the overall realistic quality of the computer generated image. ------------------------------------------------------------------------ Title: Utilization of a ComputerVision Designer IV Interactive Graphics Systems to Off-line Program a PUMA 560 Robot Author: Roland Brooks Level: M.S. Institution: Worcester Polytechnic Institute 100 Institute Road Worcester, MA 01609 Date: 1984 Advisor: Mark R. Ohlson Ordering Information: none Abstract: A software package called ROBOPATH was developed so that a ComputerVision Designer IV Interactive Graphics System can be used in off-line programming a PUMA 560 robot. ROBOPATH allows the user to do the following: (1) locate the robot within the manufacturing environment, (2) change individual joint angles, (3) specify the orientation of the tool flange and a path for it to follow, (4) select the gripper position and speed of the robot, (5) display the robot moving along its path, and (6) postprocess the path into a VAL program and set of locations. VAL programs and locations were successfully defined and down-loaded into the controller of the PUMA. ROBOPATH does not compensate for robot inaccuracies. ------------------------------------------------------------------------ Title: Algorithm Animation Author: Marc H. Brown (mhb@src.dec.com) Level: Ph.D. Institution: Brown University Date: May 1987 Advisor: Robert Sedgewick Committee: Paris Kanellakis, Andries van Dam Ordering Information: UMI (OR) Dept. of Computer Science Brown University Providence, Rhode Island 02912 Technical Report No. CS--87--05 Abstract: An algorithm animation environment is a means for exploring the dynamic behavior of algorithms that makes possible a fundamental improvement in the way we understand and think about them. It presents multiple graphical views of an algorithm in action, exposing properties that might otherwise be difficult to understand or even remain unnoticed. All views are updated simultaneously in real time as the algorithm executes, and each view is displayed in a separate window on the screen, whose location, size, and level of detail is interactively set by the end-user. A specialized interpreter controls execution in units that are specific to the algorithm, and allows multiple algorithms to be run simultaneously for comparisons. Programmers can implement new algorithms, graphical displays, and input generators and run them with existing libraries of such components. An important aspect of an algorithm animation environment, and one we believe is useful in any interactive environment, is the concept of a script: a record of an end-user's session that can be replayed. Scripts can be used both passively, as virtual videotapes, and actively, as an innovative communication medium: the viewer of a script can customize the videotape interactively, and can readily switch between passively viewing it and actively exploring its contents. Scripts are typically used as high-level macros, system tutors, and electronic textbooks and research notes. End-users can create scripts easily by instructing the system to ``watch what I do;'' scripts are stored as readable and editable Pascal programs. The potential of such algorithm animation environments is great, but can be fully realized only if they are sufficiently easy and enjoyable to use. This dissertation is step towards achieving these goals. In it, we develop a model for creating real-time animations, as well as a framework for interacting with these animations. We also describe a prototype system, BALSA--II, and its feasibility study system, BALSA-I, that realize the conceptual model. ------------------------------------------------------------------------ Title: Plane decomposition for digital representations of images Author: Mark Christopher Level: M.S. Institution: University of Regina Department of Computer Science Regina, Saskatchewan S4S OA2 CANADA Date: August 25, 1986 Advisor: Przemyslaw Prusinkiewicz Ordering Information: Same as Institution Limited copies available Abstract: The thesis is devoted to image representations involving nonstandard area samples. They are of particular interest for low resolution representation of images. The two types of sampling areas given particular attention are non-overlapping non-square areas and overlapping square areas. The study of non-overlapping non-square areas associates image processing with the theory of tiles. The motivation is that, at low resolution, non-square sampling areas may lead to more pleasant images, compared to square tiles. This portion of the thesis consists of a general discussion of tilings, presentation of the applications of tilings to sampling, and a survey of the perception of various types of sampling by human beings. Overlapping square sampling areas are studied for a different reason. They lead to a representation of pictures with the "hologram-like" property. This property is defined as follows: Given a string of data Z representing a picture with full resolution, various (not necessarily initial) substrings of Z represent the same picture with a lower resolution. An important application of the hologram-like representation is for image transmission with progressive resolution. A practical program developed for this purpose is described. ------------------------------------------------------------------------ Title: A Hybrid Ray Tracing Algorithm for Realistic Computer Imaging Author: Patricia Craig Level: M.S. Institution: Worcester Polytechnic Institute 100 Institute Road Worcester, MA 01609 Date: 1984 Advisor: Mark R. Ohlson Ordering Information: none Abstract: Two key issues in realistic image generation are investigated: object intersection and object shading. A ray tracing algorithm for image creation is designed and verified. Intersection is performed by a strategy incorporating Catmull subdivision and Newton-Raphson iteration. For shading, the Cook and Torrance model is applied in a recursive environment which simulates inter-object reflections as well as direct illumination. The effectiveness of the design is demonstrated through a series of images of a scene. ------------------------------------------------------------------------ Title: Computer Encoding, Storage and Transposition of Musical Scores Author: C.A. Crawford Level: Master of Science in Computer Science Institution: The School of Computer Science P.O. Box 4400 University of New Brunswick Fredericton, N.B. E3B 5A3 CANADA Date: May 1982 Advisor: Uday G. Gujar and Thomas A. Austin Ordering Information: none Abstract: This thesis proposes an encoding scheme for printed music. Based on this scheme, a computerized system is designed and implemented to read music as human-encoded symbols, to decode and store it within the computer, and to print it out either in its original key or in another key specified by the user. The graphics output is obtained by translating musical symbols into positional information and plotting it on a high resolution digital incremental plotter. The rules for transposition, including those for transposing accidentals, are formalized and included in the thesis. These have been programmed and appear to work correctly. The graphic output obtained is of high quality and should be acceptable for several purposes. The usefulness of the system would be increased immensely by providing a graphical input phase. The design of such a phase is discussed. ------------------------------------------------------------------------ Title: Generation and Rendering of Three Dimensional Objects Author: N.N. Datar Level: M.S. Institution: The School of Computer Science P.O. Box 4400 University of New Brunswick Fredericton, N.B. E3B 5A3 CANADA Date: May 1986 Advisor: Uday G. Gujar and Virendra C. Bhavsar Ordering Information: none Abstract: Two methods for generating three dimensional objects, namely, sweep and interpolation, are presented in this thesis, followed by a ray tracing algorithm. In the sweep method, a given contour is swept along a given trajectory using three basic techniques, namely, translation, rotation and scaling; these techniques can be combined in any manner to generate required objects. A detailed and homogeneous mathematical treatment of sweep method using a parametric form of the equations of the contours is offered. The scaling can be linear or nonlinear. Two types of nonlinearities are discussed which offer a versatile approach for generating objects with desired shapes. The interpolation method generates an object from two given contours which may be similar or dissimilar in nature. A generalized and unified theory of interpolation and its mathematical formulation for the object generation is presented. A generalization of the standard concept of interpolation is defined and discussed. Linear and nonlinear interpolation constitute the two fundamental cases. These two contours are merged by means of the weighting functions which may be linear or nonlinear functions of the interpolation variable. Various factors which influence the shape of the object generated are identified; they are the number of points, choice of points, and the intra-contour connectivity technique, connectivity selection and the inter-contour connectivity technique. The concept of a modifying function to change the basic weighting functions is introduced. It is demonstrated that one can synthesize an object of a desired shape using the nonlinear interpolation method with the help of the Fourier Series. Several illustrative examples are included. A ray tracing algorithm for rendering realistic three dimensional objects, described in a generalized contour defined environment and using multiple light sources, is presented. Illustrative examples of the shaded images produced by the algorithm are exhibited. ------------------------------------------------------------------------ Title: Drawing Wide Lines on Raster Devices Author: Peter Davis Degree: M.S. Institution: New York University Courant Institute of Mathematical Sciences New York University 251 Mercer Street New York, NY 10012 Date: not given Advisor: Dr. David Lowe Ordering Information: none Abstract: Many texts present detailed algorithms for drawing single pixel wide lines in raster displays, and then proceed to tackle more advanced computer graphics issues without addressing the problem of drawing lines wider than one pixel. However, recent developments in printer technology, and the advent of page description languages such as Adobe's PostScript, have heightened the awareness of wide lines as graphical entities. In this paper, we begin by surveying some of the single pixel wide line drawing algorithms, and the evolution of schemes for representing lines. We then show how some simple alterations can be made to a basic incremental line drawing algorithm to produce wide lines, albeit with some displeasing artifacts. To circumvent these artifacts, we present a more abstract model of line drawing than the incremental algorithm: the brush-trajectory model. The features and drawbacks of the brush-trajectory model are discussed, and some notes on possible implementation schemes and problems are given. We then develop the geometry for producing mitered line joins, such as might be obtained from the PostScript model. The mitered line model is contrasted with the brush trajectory model, and some discussion on implementation is given. Finally, we look briefly at some additional requirements for line drawing, and how they might impact the choice of line drawing technique. Specifically, we discuss joining lines of different widths, arbitrary curves, patterned lines, lines drawn by XORing pixels, and the problem of recovering line trajectory information from the wide rendition. ------------------------------------------------------------------------ Title: Geometric Continuity: A Parametrization Independent Measure of Continuity for Computer Aided Geometric Design Author: Anthony D. DeRose Level: Ph.D. Institution: Berkeley Computer Graphics Laboratory Computer Science Division University of California Berkeley, California 94720 Date: August 1985 Advisor: Brian A. Barsky Ordering Information: none Abstract: Parametric spline curves and surfaces are typically constructed so that some number of derivatives match where the curve segments or surface patches abut. If derivatives up to order n are continuous, the segments or patches are said to meet with C^n, or n th order parametric continuity. It has been shown previously that parametric continuity is sufficient, but not necessary, for geometric smoothness. The geometric measures of unit tangent and curvature vectors for curves (objects of parametric dimension one), and tangent plane and Dupin indicatrix for surfaces (objects of parametric dimension two), have been used to define first and second order geometric continuity. These measures are intrinsic in that they are independent of the parametrizations used to describe the curve or surface. In this work, the notion of geometric continuity as a parametrization independent measure is extended for arbitrary order n (G^n), and for objects of arbitrary parametric dimension p. Two equivalent characterizations of geometric continuity are developed: one based on the notion of reparametrization, and one based on the theory of differential manifolds. From the basic definitions, a set of necessary and sufficient constraint equations is developed. The constraints (known as the Beta constraints) result from a direct application of the univariate chain rule for curves and the bivariate chain rule for surfaces. In the spline construction process the Beta constraints provide for the introduction of freely selectable quantities known as shape parameters. For polynomial splines, the use of the Beta constraints allows greater design flexibility through the shape parameters without raising the polynomial degree. The approach taken is important for several reasons. First, it generalizes geometric continuity to arbitrary order for both curves and surfaces. Second, it shows the fundamental connection between geometric continuity of curves and that of surfaces. Third, due to the chain rule derivation, constraints of any order can be determined more easily than using derivations based exclusively on geometric measures. Finally, a firm connection is established between the theory of differentiable manifolds and the use of parametric splines in computer aided geometric design. ------------------------------------------------------------------------ Title: Antialiasing in Computer Graphics Author: Mark Earnest Dippe Level: Ph.D. Institution: Berkeley Computer Graphics Laboratory Computer Science Division University of California Berkeley, California 94720 Date: May 1985 Advisor: Brian A. Barsky Ordering Information: none Abstract: The problem of aliasing in computer graphics is considered. Attention is paid to the role of reconstruction in aliasing. Previous antialiasing techniques are analyzed and new approaches are presented. The generation of accurate tetrahedral representations of time-varying images is developed. Tetrahedral image descriptions are then antialiased using functional prefiltering. Antialiasing through stochastic sampling is also presented. A Fourier model of image synthesis is developed that incorporates the spatiotemporal and spectral nature of digital image generation. Due to imperfect reconstruction, it is possible for frequencies below the frequency cutoff of regular sampling to cause aliasing. The width of the reconstruction filter and the sample/scene phase relationship are important aspects of reconstruction. The tetrahedral representation of a time-varying image is a linear approximation of the true image created using flatness tests. The volume of a tetrahedron corresponds to a region in x, y, and t of the time-varying image. The values at the vertices of a tetrahedron are the colors at those points in the image. Spatiotemporal hidden surface removal is applied to all the tetrahedra to create the final tetrahedral image description. Functional prefiltering smooths a time-varying image by bounding the magnitude of the image function and its derivatives. This bounding process attenuates high frequencies so that the image can be sampled without aliasing defects. Tetrahedral Bezier patches are defined over each tetrahedron of the image. The derivative magnitudes of the patches are bounded by feature interpolation. ------------------------------------------------------------------------ Title: A Graphics Server for Local Area Networks Author: John Ekberg Level: M.S. Institution: Worcester Polytechnic Institute 100 Institute Road Worcester, MA 01609 Date: 1984 Advisor: Mark R. Ohlson Ordering Information: none Abstract: Within a Local Area Network, the transmission of graphical images between users (a picture analogy of electronic mail) can potentially overwhelm the major resource: the bandwidth of the common data link. Furthermore, no facility currently exists to transfer graphical data easily. This thesis models and analyzes a hardware and software solution to these problems. The hardware consists of a general purpose computer system plus graphics and communications subsystems. The software consists of a user interface and bandwidth reduction reduction software. The user interface is the vehicle for manipulation of the image and provides for optimized utilization of common graphics device types. The bandwidth reduction software is used to compress the data so that resources are less likely to be overwhelmed. The graphics server can be built from currently available hardware, providing function at minimal cost. ------------------------------------------------------------------------ Title: Practical Considerations for Triangular Patch Surfaces Author: Daniel J. Filip Level: M.S. Institution: Berkeley Computer Graphics Laboratory Computer Science Division University of California Berkeley, California 94720 Date: December 1985 Advisor: Brian A. Barsky Ordering Information: none Abstract: Piecewise polynomial surfaces have been shown to be useful for representing objects in interactive modeling systems. Most such systems rely strictly on rectangular surface formulations. However, triangular surface formulations can be shown to be simpler topologically and analytically. The mathematics for triangular surfaces are quite new and many associated mathematical and algorithmic questions have not as yet been answered. This thesis addresses and provides practical solutions to a number of these questions. We first consider a single triangular surface patch called a Bezier triangle. Many important aspects of this surface type are discussed including representation, conversion from rectangular surfaces, and approximation by piecewise linear polynomials. We then consider the triangular B-spline surface. This surface is a simple topological network of triangular surface patches with inherent continuity between adjacent patches. Representation and boundary curve control are among the issues that are analyzed. We conclude with a discussion of further generalizations to triangular B-spline surfaces. ------------------------------------------------------------------------ Title: Applying Color Science to Computer Graphics Author: Kenneth Paul Fishkin Level: M.S. Institution: Berkeley Computer Graphics Laboratory Computer Science Division University of California Berkeley, California 94720 Date: December 1983 Advisor: Brian A. Barsky Ordering Information: none Abstract: Computer graphics is largely concerned with the creation and display of images on a display device. Color display devices support images with very high resolution and dynamic range. As the power of the display devices increases, and the color capacities become more sophisticated, attention to the principles of color science becomes increasingly important. These principles can be applied to many aspects of computer graphics to improve the appearance and correctness of displayed images. This thesis presents a number of new algorithms in computer graphics; algorithms concerned with display or manipulation of color images. New algorithms are presented which optimally approximate the display of colors which the technology cannot recreate, which quickly translate between one color system and another, which simulate the subtractive mixture of filters and dyes, and which simulate the pigmentary mixture of paints. ------------------------------------------------------------------------ Title: Hierarchical Reasoning: Simulating Complex Processes over Multiple Levels of Abstraction Author: Paul A. Fishwick Level: Ph.D. May 1986 Institution: Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 Date: May 1986 Advisor: Norman I. Badler Ordering Information: Report Secretary Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 MS-CIS-85-21 GRAPHICS LAB 07 $13.38 Abstract: This thesis describes a method for simulating processes over multiple levels of abstraction. There has been recent work with respect to data, object, and problem-solving abstraction, however, abstraction in simulation has not been adequately explored. We define a process as a hierarchy of distinct production rule sets that interface to each other so that abstraction levels may be bridged where desired. In this way, the process may be studied at abstraction levels that are appropriate for the specific task: notions of qualitative and quantitative reasoning are integrated to form a complete process description. The advantages to such a description are increased control, computational efficiency and selective reporting of simulation results. Within the framework of hierarchical reasoning, we will concentrate on presenting the primary concept of process abstraction. A Common Lisp implementation of the hierarchical reasoning theory called HIRES is presented. HIRES allows the user to reason in a hierarchical fashion by relating certain facets of the simulation to levels of abstraction specified in terms of actions, objects, reports, and time. The user is free to reason about a process over multiple levels by weaving through the levels either manually or via automatically controlled specifications. Capabilities exist in HIRES to facilitate the creation of graph-based abstraction levels. For instance, the analyst can create continuous system models (CSMP), petri net models, scripts, or generic graph models that define the process model at a given level. We present a four-level elevator system and a two-level "dining philosophers" simulation to demonstrate the efficacy of process abstraction. ------------------------------------------------------------------------ Title: Ray Tracing Surfaces of Revolution Author: Steve Fontes Level: M.S. Institution: Worcester Polytechnic Institute 100 Institute Road Worcester, MA 01609 Date: 1984 Advisor: Mark R. Ohlson Ordering Information: none Abstract: An algorithm for ray tracing surfaces of revolution is developed. surfaces are defined by planar cubic curves. The curves are hierarchically subdivided to approximate the cubic by straight line segments. The intersection problem is initially simplified by using a series of transformations to map the surface and ray to a standard orientation. The final intersection calculations are based on simple techniques from solid geometry. An implementation of the algorithm is presented. The shading model incorporates shadowing, reflections, and transmission of light through objects. Additional features of the implementation include anti-aliasing and the ability to represent multicolored objects. ------------------------------------------------------------------------ Title: A User Interface Management System Generator Author: Tamar Ezekiel Granor Level: Ph.D. Institution: Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 Date: May 1986 Advisor: Norman I. Badler Ordering Information: Report Secretary Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 MS-CIS-86-42 GRAPHICS LAB 12 $12.33 Abstract: Much recent research has been focused on user interfaces. A major advance in interface design is the User Interface Management System (UIMS), which mediates between the application and the user. Our research has resulted in a conceptual framework for interaction which permits the design and implementation of a UIMS generator system. This system, called Graphical User Interface Development Environment or GUIDE, allows an interface designer to specify interactively the user interface for an application. The major issues addressed by this methodology are making interfaces implementable, modifiable and flexible, allowing for user variability, making interfaces consistent and allowing for application diversity within a user community. ------------------------------------------------------------------------ Title: User Interface Management Systems: a Survey and a Proposed Design. Author: Philip D. Gray Level: M.S. Institution: University of Glasgow. Date: February 1987 Advisor: A.C. Kilgour Ordering Information: Computing Science Department University of Glasgow Glasgow, G12 8QQ, Scotland, U.K. (Price: $10 including postage) Abstract: The growth of interface computing has resulted in increasingly more complex styles of interaction between user and computer. To facilitate the creation of highly interactive systems, the concept of the User Interface Management System (UIMS) has been developed. Following the definition of the term 'UIMS' and a consideration of the putative advantages of the UIMS approach, a number of User Interface Management Systems are examined. This examination focuses in turn on the run-time execution system, the specification notation and the design environment, with a view to establishing the features which an "ideal" UIMS should possess. On the basis of this examination, a proposal for the design of a new UIMS is presented, and progress reported towards the implementation of a prototype based on this design. ------------------------------------------------------------------------ Title: Software Tools for Computer Graphics Research and Development Author: Jonathan Robert Gross Level: M.S. Institution: Berkeley Computer Graphics Laboratory Computer Science Division University of California Berkeley, California 94720 Date: May 1984 Advisor: Brian A. Barsky Ordering Information: none Abstract: We describe two projects undertaken to provide software support for continuing research and development in the Berkeley Computer Graphics Laboratory. The first project, Ned, is a graphical editor for creating and modifying data flow networks for the Evans and Sutherland PS300. It provides network abstraction and graphical interaction to help overcome the problems of network definition. The second project described is Asterisk*, a system for spline development and evaluation. Asterisk* integrates the capabilities of Vaxima (used to manipulate spline functions) with facilities to specify and compare a variety of splines interactively. ------------------------------------------------------------------------ Title: Stochastic texture generation Author: Shinichiro Haruyama Level: M.S. Institution: Berkeley Computer Graphics Laboratory Computer Science Division University of California Berkeley, California 94720 Date: June, 1983 Advisor: Brian A. Barsky Ordering Information: none Abstract: This paper presents a new computer graphics method of generating highly realistic random textures. Smoothly shaded images in computer graphics have almost reached the goal of realism. However, smooth shading makes objects look artificial so that we easily realize they are computer-generated. Painting a texture on a surface is one of the best ways to make images more natural. The new method presented here generates textures by perturbing normal vectors of the surface using a recursion technique which is similar to the algorithm developed by Fournier, Fussell, and Carpenter to generate stochastic curves and surfaces. By this method, complicated random textures can be depicted using a small amount of data and no original texture pattern. The properties of the texture can be changed by altering the few parameters that control them. ------------------------------------------------------------------------ Title: Visual Programming of Functional Transformations in a Dynamic Process Visualization System Author: Branka Jovanovic Level: M.S. Institution: George Washington University Department of E.E. and C.S. Washington D.C. 20052 Advisor: James D. Foley Ordering Information: Institute for Information Science and Technology George Washington University Department of E.E. and C.S. Washington D.C. 20052 Request IIST-86-22. Abstract: In this work we design and partially implement a simple visual programming system intended for application-oriented users in dynamic process visualization systems. The goal of our design is to enable easy on-line specification of simple functional transformations involving existing process variables to produce new, derivable information and subsequently view it. We design an extended structured-flowchart-like visual programming language, which also exploits the notion of data flow in complex expression construction. Program modules are constructed using a custom interactive editor designed to "engineer-out" most semantic and some syntactic errors. The editor also provides on-line module compilation and exercising facilities. The latter enables the user to test the created module by invoking it, assigning values to its input variables and checking the calculated output variable values. ------------------------------------------------------------------------ Title: Enhancement and Implementation of the A-buffer Rendering Algorithm Author: Atul Kedar Level: M.S. Institution: University of Regina Department of Computer Science Regina, Saskatchewan S4S OA2 CANADA Date: February 20, 1987 Advisor: Przemyslaw Prusinkiewicz Ordering Information: Same as Institution Limited copies available Abstract: A-buffer is an antialiasing rendering algorithm introduced in 1984 by L. Carpenter. It provides an attractive compromise between image quality and the rendering time. The thesis describes details of the A-buffer, proposes improvements to the original version, and presents a software implementation to the algorithm designed for the SUN workstations. The modifications of the original algorithm result in a major reduction of the memory requirements and in the correct rendering of surfaces intersecting under arbitrary angles in space. The saving in memory requirements results from the scanline operation of the modified algorithm. In order to handle intersecting surfaces correctly their depth at the four corners of each pixel is considered. Discussion of the A-buffer is preceded by a survey of other rendering techniques. ------------------------------------------------------------------------ Title: Hardware enhancement of a Hidden Line Algorithm Author: David Kirschen Level: M.S. Institution: Worcester Polytechnic Institute 100 Institute Road Worcester, MA 01609 Date: 1983 Advisor: Mark R. Ohlson Ordering Information: none Abstract: A hidden line removal algorithm and its implementation as part of a software test bed are described. Using the test bed, the performance of the original algorithm and a software optimization were measured. The results were applied to an investigation of ways in which hardware could be used to enhance the algorithm's performance. ------------------------------------------------------------------------ Title: SCORE: An Interactive, Graphic Interface to the GOALTENDER Language Author: Lisa Katz Koelewyn Level: M.S. Institution: Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 Date: August 1987 Advisor: Norman I. Badler Ordering Information: Report Secretary Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 MS-CIS-87-70 GRAPHICS LAB 17 $4.56 Abstract: The animation of articulated figures, particularly humans, performing natural actions and tasks is a tedious and complicated process whether done by key-position techniques or dynamics models. One way to achieve succinct expression of desired activities is through constraints on the position and orientation of a figure and its sub-parts. The requirements for a constraint- based animation system and a language, GOALTENDER, are briefly described; they are the motivation for SCORE, an interactive graphic interface for GOALTENDER. GOALTENDER'S constraints include spatial regions, orientation zones, and time expressions. Within a constraint, "preferences" are described by weighted potential functions indicating the desirability of reaching various points, regions, or volumes of space. The relative importance assigned to multiple constraints is their "strength". SCORE is an interactive, graphic front end to GOALTENDER. It allows an animator to visualize the objects and people in a scene, their spatial relationships, and draws the regions and zones as they are used or defined for specific goals. ------------------------------------------------------------------------ Title: Development of a Ray Tracing Model for Realistic Image Synthesis Author: Mark Edward Lee Level: M.S. Institution: The University Of Tulsa Department Of Computer Science 600 South College Avenue Tulsa, Oklahoma 74104-3189 (918) 592-6000 Date: Spring 1986 Advisor: Samuel P. Uselton Ordering Information: University of Tulsa McFarlin Library Duplicating Services (also available through interlibrary loan) Abstract: The ray tracing model generates images that are, generally, the most realistic to date. The model works well because it is based on the physical laws of nature. First, a simple ray tracing model is developed that includes effects such as reflections, refractions, and shadows. A shading model is presented that more accurately models the interaction between light and surfaces. An important issue is the use of material factors and the wavelength dependency of the light-surface interaction. A consistent method for the inclusion of a variety of object primitives for scene modeling is presented. A sampling technique based on statistics is presented to extend the ray tracing model for not only sampling the pixel area, but also sampling lens area, light source area, surface reflection direction, and surface refraction direction. Finally, an execution time analysis is presented to determine the efficiency of the ray tracing model and to locate bottlenecks and possible areas for improvement. ------------------------------------------------------------------------ Title: Digitisation Functions in Computer Graphics Author: Marloes van Lierop Level: Ph.D Institution: Eindhoven University of Technology P.O. Box 513 5600 MB Eindhoven The Netherlands Date: July 1987 Advisors: F.J. Peters and M. Rem Ordering Information: none Abstract: (in troff-mode) .EQ delim $$ .EN .LP For the generation of digital images from continuous objects, a digitisation mapping from $bold R sup 2$ (or $bold R sup 3$) to $bold Z sup 2$ is required. Thus far, in Computer Graphics literature, digitisation is dealt with by presenting algorithms; formal specifications of these algorithms are seldom presented. In this thesis we abstract from algorithms: a framework is presented in which desirable properties of digitisation functions are formulated formally. .LP One of these properties is \f2closeness\f1, which expresses that the digitisation of an object should correspond as good as possible to the original object. Other properties are \f2translation invariance\f1 and \f2convexity\f1. Thus far, closeness has been considered to be a necessary requirement for digitisation functions. In this thesis, however, digitisation functions that are not close are also dealt with. A measure is introduced to express the quality of these functions with regard to closeness; this measure is called the \f2vicinity function\f1. .LP To show the implications of this new view on digitisation, we concentrate on digitisation functions for line segments, shortly called line functions. Apart from the properties mentioned above, other properties for line functions are considered, namely \f2minimality\f1 and \f2recursiveness\f1. Several examples of line functions are discussed. .LP It will be proven that translation invariant, minimal, close line functions are not convex. (A line function $f$ is convex if for all pixels $p,^q,^r$ and $s,$ where $r,^s \(mo f(p,^q),$ holds that $f(r,s)^\(ib^f(p,^q).$) Special attention is paid to convexity: it will be shown that on a restricted domain $D,$ a convex line function can be constructed from any translation invariant, minimal line function that satisfies certain conditions. Furthermore, it will be proven that there is a one-to-one correspondence between line functions satisfying these conditions, and permutations. ------------------------------------------------------------------------ Title: Articulated Figure Positioning By Multiple Constraints and 6-Axis Input Author: Kamran H. Manoochehri Level: M.S. Institution: Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 Date: August 1986 Advisor: Norman I. Badler Ordering Information: Report Secretary Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 MS-CIS-86-69 GRAPHICS LAB 15 $5.83 Abstract: A common method of animating articulated figures is by key positioning and interpolation. Positioning a three-dimensional input device is a difficult and often a tedious task. In order to simplify this task for animators, a system called POSIT was designed and implemented. POSIT creates a highly interactively by using a six-axis input device to establish joint angles and locate multiple constraints between joints and goal positions. The combination of these two methods seems to provide a faster and easier way to position objects and articulated figures in three dimensional scenes. ------------------------------------------------------------------------ Title: An Implementation of the Raster Extensions to the CORE System Author: Sally Marlino Level: M.S. Institution: Worcester Polytechnic Institute 100 Institute Road Worcester, MA 01609 Date: 1982 Advisor: Mark R. Ohlson Ordering Information: none Abstract: A 3-dimensional, device independent, raster graphics system was designed and implemented. The graphics package is modeled after the CORE System proposed by SIGGRAPH Graphics Standard Planning Committee. The raster converter incorporates existing raster scan techniques to transform the user's description of a picture to pixel data. This paper reviews the Core Graphics System and discusses the raster scan concepts employed in the creation of the system. ------------------------------------------------------------------------ Title: Principal patches for computational geometry Author: R.R. Martin Level: Ph.D. Institution: Cambridge University Engineering Department Trumpington St. Cambridge, United Kingdom Date: 1982 Advisor: A.W. Nutbourne Ordering Information: Dr. R. Martin Dept of Computing Mathematics Mathematics Institute University College Cardiff, CF2 4AG United Kingdom (Price: 25 pounds sterling) Abstract: This thesis presents a new class of surface patches for the creation of sculptured surfaces in mechanical engineering applications of computer aided design. Ideas from differential geometry are used to create principal patches whose edges are lines of curvature. This is done by ensuring that the sides obey two equations called the frame matching and position matching conditions. It is shown that these conditions are both sufficient and necessary to create a patch based on lines of curvature. A solution to the frame matching equation is given for all cases where the patch boundaries are plane curves. Continuity between principal patches is examined. The method is illustrated by means of two well understood surface types which are of engineering importance: generalised cylinders and surfaces of revolution. The method is then used to create patches whose lines of curvature are circular arcs. Such patches come from surfaces known as Dupin's cyclides. These patches are demonstrated to have one degree of freedom, assuming two sides of the patch are known, and a discussion of how to use this choice is given. It is shown that cyclide patches are a subset of rational biquadratic surfaces, and that the sphere, cone cylinder, torus and plane are special cases. Another useful property is that the offset surface to a cyclide is another cyclide. The need for non-four-sided regions of surface is examined. These occur at umbilics when using principal patches. The behaviour of surfaces near umbilics is reviewed, and suggestions are made for dealing with such regions using principal patches. ------------------------------------------------------------------------ Title: A Realistic Model of Refraction for Computer Graphics Author: Forest Kenton Musgrave Level: M.S. Institution: Computer and Information Sciences University of California, Santa Cruz Date: September 1987 Advisor: Lew Hitchner Ordering Information: none Abstract: A model which takes into account the relationship of the frequency of light to the index of refraction in transparent media, is developed as an extension of the distributed ray tracing model. A model of atmospheric rainbows is presented. The problem of representing an approximation of the spectrum of monochromatic colors on a color graphics monitor is discussed, within the context of modelling dispersion. ------------------------------------------------------------------------ Title: Three Dimensional Solids from Orthographic Views Author: I.V. Nagendra Level: M.S. Institution: The School of Computer Science P.O. Box 4400 University of New Brunswick Fredericton, N.B. E3B 5A3 CANADA Date: May 1986 Advisor: Uday G. Gujar Ordering Information: none Abstract: A comprehensive comparative study of the earlier algorithms to generate 3D solids from the given orthographic views has been carried out. The capabilities and limitations of each of these algorithms have been listed in the form of a table. A categorization tree is drawn. An algorithm to generate 3D solid objects, made up of planar surfaces, from the three given orthographic views is designed and presented. The algorithm has been implemented on the IRIS 1400 Graphics System using the C language. Whenever more than one interpretation can be given for the user input orthographic views, the algorithm generates all the possible solutions. Several examples, both simple and complex, giving unique and multiple solutions are included. The infinite space has been divided into finite subspaces (called probable 3D subobjects) by making use of the surface normals and direction of travel of the edges that connect the faces. The certain and uncertain probable 3D objects are discussed. The algorithm has been interfaced to a ray tracing algorithm to obtain realistic rendering of the 3D solids. ------------------------------------------------------------------------ Title: High-Quality Text for Raster Displays Author: Avi C. Naiman Level: M.S. Institution: University of Toronto Department of Computer Science Sandford Fleming Building 10 King's College Road Toronto, Ontario M5S 1A4 CANADA (416) 978-8762 Advisor: Alain Fournier Ordering Information: Paper copies may be ordered from: University of Toronto Science & Medicine Library Interlibrary Loans Office 7 King's College Circle Toronto, Ontario M5S 1A5 CANADA (416) 978-3327 Microfiche copies may be ordered from: University of Toronto University Archives Fisher Rare Book Library 120 St. George Street Toronto, Ontario M5S 1A5 CANADA (416) 978-5343 Abstract: Much attention has recently been focused on Digital Typography, in particular for producing text on bi-level hard-copy devices. In this thesis, we develop algorithmic procedures for the interactive display of text on color, raster-scanned display devices. To this end, we review established methodologies in Computer Graphics for the design, representation, storage, and composition of characters, introduce relevant concepts from vision and typography, and develop new techniques for the storage and display of digital text, including: an improved version of the standard run-length encoding algorithm which achieves a compaction rate twice that obtained by the standard method; a heuristic for the display of grayscale characters at sub- pixel resolution without the need to precompute several versions of the characters; a method for the use of kerning techniques in an automated environment; and an algorithm for automatic color selection for foreground objects in order to guarantee visibility against colored backgrounds. ------------------------------------------------------------------------ Title: A Structural Model of The Human Face Author: Stephen Michael Platt Level: Ph.D. Institution: Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 Date: 1985 Advisor: Norman I. Badler Ordering Information: Report Secretary Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 MS-CIS-86-11 GRAPHICS LAB 11 $15.93 Abstract: This dissertation examines the problems of representing and animating complex, highly connected objects. Systems such as these are difficult to describe and animate due to the richness of actions and physical interconnections. A strategy of partitioning the objects, actions, and application algorithm is proposed which allows complete independence of definition of these three classes. A simple animator has been implemented for a gear-and-axle universe which is capable of detecting inconsistent cyclic systems while correctly animating consistent ones. An object of proven interest, the human face, is then examined. The face itself consists of a moderately large number of definable regions of expression and a predefined set of performable actions. An action in one of these regions may or may not cause other changes, both in the state of the region and in other adjacent regions. OASIS/F, using the object/action paradigm, was implemented. This representation of the face is capable of animating the face in a realistic manner, preserving the structural properties and idiosyncrasies of the face. ------------------------------------------------------------------------ Title: Interpolation and Display of Scattered Data Over a Sphere Author: Ramamani Ramaraj Level: M.S. Institution: Computer Science Department Arizona State University Tempe, AZ 85287 Date: none given Advisor: Gregory M. Nielson Ordering Information: Ramamani Ramaraj Computer Science Department Arizona State University Tempe, AZ 85287 Abstract: In this thesis we present a new method for solving the spherical interpolation problem: Given n distinct points Vi, i = 1,2...n, on the surface of the unit sphere R, construct a smooth function F, defined over R such that F(Vi) = fi, i = 1,2...n. The method is based on a planar method known as minimum norm network method. This method is extended to a spherical domain. This involves triangulation of the entire sphere based on the given data points as vertices. The triangulation scheme used is described. A curve network consisting of an approximation S and first partial derivatives is constructed. Then an appropriate blending scheme is described to extend the definition of S to the entire sphere R. Different graphical representations of the function over a sphere are discussed. Algorithms for generating the graphical representations are outlined. ------------------------------------------------------------------------ Title: Interactive Graphics System for Application to Geology (IGSAG) Author: A. Saxena Level: M.S. Institution: The School of Computer Science P.O. Box 4400 University of New Brunswick Fredericton, N.B., E3B 5A3, Canada Date: February 1987 Advisor: Uday G. Gujar Ordering Information: none Abstract: This thesis presents the design and implementation of an Interactive Graphics System for Application to Geology (IGSAG). Developed for geologists to use in the study of mines, this system automated the current practice of generating the mine sections manually. The input to the system is the data collected from the field survey of mines. The output of the system is a mine section of specified location, orientation and size that presents the profiles of various rocks. The input data files are preprocessed using one of the two schemes suggested in this thesis. A section is mathematically represented and an algorithm to generate a section from the input data is presented. A 3-D clipping algorithm, needed to generate a section, is also implemented. Use of natural cubic splines is incorporated in the system. A menu driven user interface has been developed to provide the user with a flexible, user friendly and easy to understand system. The user may choose a section using various parameters available to him as menu items. He may generate and edit the splines using the menu options. He may closely examine certain portions of the display by zooming in that portion. Once the user has created a desired section, he may save it as a file or get a hardcopy on various plotters. The details of design and implementation are also presented in this thesis. ------------------------------------------------------------------------ Title: The Slicing Extent Technique for Fast Ray Tracing Author: Sudhanshu Kumar Semwal Level: Ph.D. Institution: Department of Computer Science The University of Central Florida Orlando, Florida Date: July 1987 Advisor: J. Michael Moshell Ordering Information: none Abstract: A new technique for image generation using ray tracing is introduced. The "Slicing Extent Technique" (SET) partitions object space with slicing planes perpendicular to all three axes. Planes are divided into two dimensional rectangular cells, which contain pointers to nearby objects. Cell size and the space between slices varies, and is determined by the objects' locations and orientations. Unlike oct-tree and other space-partitioning methods, SET is not primarily concerned with dividing space into mutually exclusive volume elements ('voxels') and identifying objects within each voxel. Instead, SET is based on analysis of projections of objects onto slicing planes. In comparison to the space subdivision existing methods for ray tracing, SET avoids tree traversal and exhibit no anomalous behavior. There is no reorganization when new objects arrive. Preprocessing to create slices is inexpensive and produces a finely tuned filter mechanism which supports rapid ray tracing. SET resembles other efforts to speed up ray tracing inasmuch as a two step process is used. First an approximate filter technique eliminates most possible ray-object collisions. Then an accurate computation evaluates the remaining possible collisions and provide information for the generation of subsequent rays. A filter method is a technique which eliminates most possible ray-object collision from consideration, and subjects only the likely collisions to a complete collision computation. ------------------------------------------------------------------------ Title: An ETHERNET Based Graphics Server Author: Sassan Shahriary Level: M.S. Institution: Worcester Polytechnic Institute 100 Institute Road Worcester, MA 01609 Date: 1987 Advisor: Mark R. Ohlson Ordering Information: none Abstract: The design and implementation of an Ethernet Based Graphics Server is presented. The system enables users of graphic terminals to enhance their scope of operation by transferring graphic images to other systems on a local area network, Ethernet. The system provides a menu driven package for graphic users for processing, storage, and retrieval of graphic images on a system with mass storage and computational power. The network allows communication with advanced raster graphic devices residing on the communication subnet. ------------------------------------------------------------------------ Title: Modeling Branching Plants Using Attribute L-Systems Author: Melinda Shebell Level: M.S. Institution: Worcester Polytechnic Institute 100 Institute Road Worcester, MA 01609 Date: 1986 Advisor: Mark R. Ohlson Ordering Information: none Abstract: L-systems have been used in the past to model and render the growth behavior of branching plants. Attribute grammars have been used extensively in compiler and language studies, but have not been applied to L-systems. An expanded L-system that has attributes associated with symbols in the string can be used to model idealized plant growth governed by a set of deterministic rules, or random non-deterministic natural events such as branch death or damage, or complex environmental influences such as the effect of wind or sunlight on growth. Since the modeling problem is different from the rendering problem, a two step process is described. The first step is to generate a "skeletal" model of the plant which can contain a minimum amount of geometric data to describe the branching system of the plant. The second step uses the skeletal representation to generate sufficient information to render the plant. This thesis describes the grammar and attributes used to create a skeletal representation of a morphological model of a plant and a method to generate the state of the plant at some stage of its development given a previous state, or an initial state. Thus, continuity of the plant is maintained as the plant matures in discrete time periods. Because the skeletal representation is separate from the rendering representation, it is possible to have many different methods for rendering the plant depending on the degree of realism desired. Some of these methods are briefly described in the last chapter. ------------------------------------------------------------------------ Title: Presentation Component for the University of Alberta UIMS Author: Gurminder Singh Level: M.S. Institution: Department of Computing Science University of Alberta Edmonton, Alberta T6G 2H1 CANADA (403)432-5198 Date: 1985 Advisor: Dr. Mark Green Ordering Information: Department of Computing Science University of Alberta Edmonton, Alberta T6G 2H1 CANADA (also available through inter-library loan) Abstract: This thesis is concerned with the design and implementation of the presentation component of the University of Alberta User Interface Management System. The Seeheim Model of user interfaces is considered as the basis of this work. It is shown that all device dependencies can be limited to the presentation component of the user interface. This increases the portability of the system. In the design proposed in this thesis user interfaces can easily be adapted to individual users. The selection of interaction techniques and display formats can also be easily changed to the actual user's liking. It is observed that the existence of a separate presentation component encourages the use of standard libraries of interaction techniques and display procedures. This speeds up the process of generating user interfaces to a great extent and reduces the cost of programming considerably. A catalogue of interaction techniques is proposed. This catalogue defines the contents of the library of interaction techniques. The proposed classification scheme is based on the interaction task performed by the interaction technique. ------------------------------------------------------------------------ Title: (missing) Author: Yahya Slimani Institut d'Informatique Universite d'Es-Senia Oran Algerie Level: Ph.D. Institution: Fundamental Computing Science Laboratory of Lille 1 (French) UA 369 BAT. M3 USTL 1 59655 Villeneuve d'Ascq Cedex. FRANCE Date: February 1986 Advisor: Vincent Cordonnier and Michel Meriaux Ordering Information: none Abstract: Computer generation of images belong to computer applications for which we implement architectures and softwares that satisfy, as far as possible, with memory space and time constraints. From an analysis of graphic systems about data structures and algorithmic, we propose the use of applicative languages (like LISP) under two aspects. i) data structures where list structures is an interesting model for representation and manipulation of graphic objects. ii) algorithmic where fundamental concept of applicative languages (recursivity) go far to natural expression of graphic algorithms. ------------------------------------------------------------------------ Title: CADETS - A Computer Aided Design Tutorial System Author: L.B. Slipp Level: M.S. Institution: The School of Computer Science P.O. Box 4400 University of New Brunswick Fredericton, N.B. E3B 5A3 Canada Date: September 1985 Advisor: Uday G. Gujar Ordering Information: none Abstract: CADETS is a two-dimensional computer-aided drafting/design system modeled after the Unigraphics I software developed by McDonnell Douglas Automation (McAuto). The advantage of using CADETS lies in its series of automated tools which are used to develop and refine the geometric model of an object. For example, the user may create a line tangent to two arcs by selecting two existing arcs from the graphics display. A fillet may be created by specifying the two lines it will be tangent to. Within CADETS, there are currently eleven ways to create a point, thirteen ways to create a line segment, and ten ways to specify a circular arc. In addition, CADETS provides functions to generate common geometric objects such as triangles and rectangles, as well as arbitrary polygons with relatively little user action. Once created, the user may edit the model by deleting geometric entities, either individually or in a group. Line segments may be extended or trimmed to one of two boundary lines, constrained to intersect at a corner, etc. Arcs in turn may be bounded by angles or points or lines which intersect them. The visual attributes of any entity (i.e. colour, style and width) may also be changed by the user. The user also controls the view area and scale of the model. Small details may be examined by enlarging that particular area, or the user may select an option which automatically rescales the image to fit within the graphics display area. Once the model is fully developed, the user can generate a hardcopy of the model on a variety of output devices. The details of user interface and system design and internals are included. Several examples illustrating the capabilities of the system are given. The system is modular and easy to maintain and extend. Presently, CADETS works on an IBM 3279 type colour graphics terminal - terminal dependent functions are kept to a minimum and identified. ------------------------------------------------------------------------ Title: Light Models for Realistic Image Generation Author: Christianna Smith Level: M.S. Institution: Worcester Polytechnic Institute 100 Institute Road Worcester, MA 01609 Date: 1987 Advisor: Mark R. Ohlson Ordering Information: none Abstract: A light source model including the properties of geometry, spatial intensity distribution, and spectral intensity distribution was developed. This representation allows light sources to take on any shape desired by defining the sources with Bezier surfaces. The intensity and directional emission of the light energy can also be varied over the surface of the source. Additionally, the representation used allows for the generation of these sources within a scene using the same rendering algorithm with only minor variations in the pixel color computation. An algorithm for ray tracing scenes illuminated by these light sources was implemented. The objects of a scene are initially defined with Bezier surfaces. To simplify the intersection problem, the objects and light sources were reduced to polygons before the scene was ray traced. Modifications were made to a standard shading algorithm to enable it to handle the new definition of the light sources. Most of the modifications were done in the area of shadow computation which resulted in a more realistic image. ------------------------------------------------------------------------ Title: A Flexible Software Character Generator Author: F.W.L. So Level: M.S. Institution: The School of Computer Science P.O. Box 4400 University of New Brunswick Fredericton, N.B. E3B 5A3 CANADA Date: October 1982 Advisor: Uday G. Gujar Ordering Information: none Abstract: In computer graphics, generation of characters of different styles is required for several purposes. This report describes the design and implementation of a flexible software character generator which enables a novice FORTRAN user to display characters in different styles with desired heights, widths and various transformations. The character generator described is composed of the following three components: 1. A data structure to define characters; 2. Code to generate characters; 3. A set of routines to define the data structure. These three components are kept as separate units, thus providing a very powerful and generalized facility. Eight different character fonts have been generated to demonstrate the flexibility of the system. Additional fonts can be easily added without modifying any of the existing routines. Various transformations such as Rotation, Revolve, Skew, Fall and Stretch can be applied to each of these fonts. Rotation transformation enables the user to display a character string with different inclinations; Revolve transformation enables the user to rotate each individual character in the string separately; Skew and Fall transformation allows the user to obtain continuously changing heights for the characters. These transformations can be combined to form a composite complex transformation to obtain interesting and fascinating results. Shapes of the existing characters in any of the predefined character sets can be changed dynamically. Since each font is a different and independent module, new character fonts can be easily generated by supplying data in a new module; all the transformations will work on this new font without any reprogramming. Special control characters are provided for writing upper and lower case letters, subscripts, superscripts, etc. Effects of these control characters could be changed dynamically as well as statically. Several examples illustrating the capabilities of this generator are included. ------------------------------------------------------------------------ Title: Enhancements to the Computer Aided Design Tutorial System Author: J.W.P. So Level: M.S. Institution: The School of Computer Science P.O. Box 4400 University of New Brunswick Fredericton, N.B., E3B 5A3, CANADA Date: June 1986 Advisor: Uday G. Gujar Ordering Information: none Abstract: A Computer Aided Design Tutorial System (CADETS) has been developed and implemented at the University of New Brunswick in 1985 aiming at acquainting students with CAD experiences in an institutional environment. Several enhancements to CADETS were essential in order to achieve the completeness of a CAD software. This Thesis describes the design and implementation of the next version of CADETS - version 2.0. Enhancements include not only the addition of new features to CADETS 1.0 but also the consideration of transporting CADETS to other computer systems and display devices. With respect to the creation of geometric entities, CADETS 2.0 allows the user to create polygons, conics, and labels in various ways. Once created, the user may pick the geometric entities in the current model of inquiry, transformation or deletion through a series of selection methods. Manipulation of geometric entities is facilitated by the introduction of new transformation functions such as translation, scaling, rotation, and mirroring. Options to move, copy or duplicate the transformed entities are available to the user. Geometric models created by the user may be stored as either TSIO or VSPC data sets. The user may retrieve, inquire or change the data set names of the models at will. The drawing power of CADETS is further magnified by the introduction of layers. The facility enables the user to view and draw each individual layer independently or to view selected layers simultaneously. the process of converting CADETS to other computer systems and display devices is studied. Conversion to the IBM PC microcomputer is achieved successfully, but the conversion to the Keynote Designs terminal KD404 has failed. The problems involved in the conversion process are studied. It is concluded that CADETS runs on any computer system or display device provided that its device driver for GRAPHPAK has been properly implemented. ------------------------------------------------------------------------ Title: Constraint-based modeling of three-dimensional shapes Author: Dale Streibel Level: M.S. Insitution: University of Regina Department of Computer Science Regina, Saskatchewan S4S OA2 CANADA Date: August 24, 1987 Advisor: Przemyslaw Prusinkiewicz Ordering Information: Same as University Limited copies available Abstract: The thesis shows that constraint-based modeling provides a viable method for specifying complex surfaces. The thesis starts with an overview of the commonly used techniques for specifying polygon meshes, known as "explicit polygons", "explicit edges" and "explicit vertices". All these techniques assume that the coordinates of the vertices are given. The idea of constraint based modeling is to specify polygon meshes using relations between between mesh elements rather than their coordinates. The primary constraint type considered is the distance between vertices which is naturally expressed by a quadratic equation relating vertex coordinates. In order to satisfy these constraints, a system of nonlinear equations must be solved. To this end, Newton's method is used. Unfortunately, as objects become more complex, several problems arise with regards to convergence. One solution is to structure the system of constraints so that at each step of constraint satisfaction the corresponding system of equations is small. A notation for describing three-dimensional objects using constraints in either non-structured or structured way is specified in the thesis. Example of modeled objects are presented. ------------------------------------------------------------------------ Title: Graphical Simulation of Hydrodynamics: Modeling and Rendering Waves Author: Pauline Yue Jun Ts'o Level: M.S. Institution: Berkeley Computer Graphics Laboratory Computer Science Division University of California Berkeley, California 94720 Date: October 1985 Advisor: Brian A. Barsky Ordering Information: none Abstract: The graphical simulation of a certain subset of hydrodynamics phenomena is examined. New algorithms for both modeling and rendering these complex phenomenon are presented. The modeling algorithms deal with wave refraction in an ocean and turbulent flow in a river. Waves refract in much the same way that light does. In both cases, the equation that controls the change in direction is Snell's law. Ocean waves are continuous but can be directly decomposed into wave rays or wave orthogonals. These wave orthogonals can be traced in a manner similar to the rendering algorithm of ray-tracing. The refracted wave orthogonals can later be traversed and their height contribution to the final surface can be calculated using a sinusoidal approximation of a wave's shape and the principle of wave superposition. The models for turbulent water are based on using a combination of stochastics and simple heuristics derived from physical principles. Here, the physical principles of interest are conservation of mass and momentum. The rendering algorithms are based on the use of texture maps and Fresnel's law of reflection. In each algorithm, two texture maps are used to provide reflected color information and refracted color information. Based on surface normal orientation, viewer position, and Fresnel's law, a weighting is calculated that determines what fraction of reflected color and refracted color are assigned to a point. These algorithms are more efficient, though less accurate, alternatives to standard ray-tracing techniques. ------------------------------------------------------------------------ Title: Scattered Data Approximation Based on Delaunay Tessellation Author: Kyoya Tsutsui Level: M.S. Institution: Computer and Information Sciences University of California, Santa Cruz Date: September 1986 Advisor: Lew Hitchner Ordering Information: none Abstract: A solution for the problem of approximating a data distribution based on time varying data measured at scattered points in three-dimensional space is presented. The solution method tessellates the whole space with Delaunay tetrahedra using only recent data points. Reliability and efficiency of the solution method are analyzed. A stochastic, Poisson model is presented to describe the distribution of data points in space and time. An error bound analysis of the Delaunay tessellation approximation scheme is presented. Two algorithms, for incremental addition and incremental deletion of a data node, are described. Experimental results are illustrated by exhibits of contour surfaces computed upon a space that has been tessellated from pseudo-random data. ------------------------------------------------------------------------ Title: Tolerances in Computer-Aided Geometric Design Author: Joshua Urbain Turner Level: Ph.D. Institution: Rensselaer Polytechnic Institute Date: May 1987 Advisor: Michael J. Wozny Ordering Information: Center for Interactive Computer Graphics Rensselaer Polytechnic Institute Troy, New York 12180-3590 Abstract: In the design of discrete part shapes, the specification of tolerance constraints can have major consequences for product quality and cost. Traditional methods for tolerance analysis and synthesis are time-consuming and have limited applicability. The thesis of this work is that geometric design systems based on solid modeling technology can be used to automate the solution of these problems. First, a mathematical theory of tolerances is developed. It is shown that a tolerance specification may be as an "in-tolerance" region of a normed vector space over the reals. A representative selection of both dimensional (plus-minus) and geometric tolerance types is investigated. Using this theoretical framework, methods are developed for the solution of tolerance analysis and synthesis problems. Three methods for tolerance analysis are presented: a linear programming method, a Monte Carlo method, and a least squares fitting method. These methods differ as to linearity assumptions and computational costs. The linear programming method supports a worst-case solution basis. The other two methods also support the solution of tolerance analysis problems on a statistical basis. Next, models are developed for worst-case and statistical tolerance synthesis. It is shown that at least in some cases convex programming methods may be applicable. For both the analysis and the synthesis methods, all necessary geometric relationships are automatically derived from the geometric model. To provide a computational framework, a general strategy for constructive variational geometry is developed. This includes a general scheme for the relative positioning of parts and part features. Three relative positioning operators are described. Methods are given for the modeling of size, orientation, and position variations. Feasibility is demonstrated using an experimental geometric system named GEOTOL. The linear programming and Monte Carlo methods are used in solving tolerance analysis problems for several simple assemblies, as well as for a larger bus bar assembly drawn from an actual product. It is shown that three-dimensional tolerancing problems can be solved by these methods. ------------------------------------------------------------------------ Title: The Realistic Presentation of Synthetic Images: Image Processing in Computer Graphics Author: Steven D. Upstill Level: Ph.D. Institution: Berkeley Computer Graphics Laboratory Computer Science Division University of California Berkeley, California 94720 Date: August 1985 Advisor: Brian A. Barsky Ordering Information: none Abstract: The problem of viewing synthetic images on cathode-ray tube monitors is considered. Due to the enormous dynamic range of naturally occurring scenes, synthetic images using these devices cannot fully model physical reality. However, by attending to the nature of human visual response, it is possible to more closely replicate the visual response that would be produced by an ideal display device. In particular, the changes in visual response with scaler changes in image intensity should be reflected in the displayed image. Three categories of these changes are considered: * shifts in perceived color * changes in sensitivity to intensity modulation across the image (contrast sensitivity) * changes in the useful dynamic range of visual sensitivity Techniques for postprocessing synthetic images for improved display are derived, justified and embedded in a computer program, VINCE, for interactivity controlling a number of image quality variables. Physically correct synthetic images are processed by this program, and the results of this processing are presented and discussed. ------------------------------------------------------------------------ Title: Computer Aided Injection Molding Author: Robert Weiss Level: M.S. Institution: Worcester Polytechnic Institute 100 Institute Road Worcester, MA 01609 Date: 1986 Advisor: Mark R. Ohlson Ordering Information: none Abstract: Bezier patches are investigated as a unified data type for use in a CAD system intended for injection molding. The project implements algorithms for dividing a Bezier patch into two at a cut plane and tests the quality of the result. Calculating intersection curves and new patches is achieved by Least Squares Analysis. Error resulting from this method of calculation is comparable to the tolerance used for approximations, and is therefore too small to measure. Error also becomes smaller as the number of points used to fit curves is decreased. ------------------------------------------------------------------------ Title: Formalization of Computer Graphics on a Discretized Plane (Italian) Author: Charles Wuethrich (wuethri@ifi.unizh.ch seismo!mcvax!cernvax!unizh!wuethri) Level: "laurea" thesis - fulfills the requirements for a degree in Mathematics after a four year study course Institution: Universita` degli Studi di Milano Dipartimento di Matematica via Saldini 50 20100 Milano I T A L Y Date: February 1987 Advisor: M. Lunelli and A. Giorgilli Ordering Information: none Abstract: The great development of computer graphics in the latest years has not been supported by an adequate development of its mathematical fundaments. The lack of mathematical studies on the discrete world and therefore of good discrete geometries has constrained computer graphics researchers to use the continuous plane as a model for a graphic terminal's screen. In fact, everybody who deals with computer graphics knows that the screen is a finite set of points, and that the first generalization of a finite set is a discrete set, not a continuous one; this gap between the screen itself and its logical representation means that each object has to be re-discretized each time it is rotated or translated, which is a quite expensive thing in means of time. The thesis is a first attempt to solve this problem. Part 1 investigates former results presenting a work of R. Klette (Computer vision, graphics and Image Processing, Vol.30 (1985)) and intergrating it with the introduction of the Freeman chain code of a curve. A lot of work is then done in investigating the relations between the Freeman chain code of a straight line and its slope. Klette's work seems to be inappropriate because of its use of Hilbert space techniques which again are made for the description of the continuous world rather than of the discrete world. The Freeman chain code of a curve shows to be a very attractive and simple way of representing curves in the discrete world. The mathematical space where Freeman chain codes are introduced is the Cartesian product Z*Z of the set Z of integer numbers, where the relation of adjacency is somewhat forced in an unnatural way. There was indeed a mathematical structure that combined both the features of being discrete and of expressing easily adjacency: a GRAPH. This is Part 2's starting point. At first the regular coverings of the real plane are studied i.e. the coverings of the real plane with regular, adjacent and equal polygons. Every regular covering of the plane is then transformed in an infinite graph where straight lines and curves are directly defined through Freeman chain codes, gaining therefore independence from the real world. To each couple of points of a graph a "slope" is then associated and the canonical straight line passing through two points is then defined. Finally an equivalent of the quadrant of the real plane is then introduced on the class of infinite graphs outlined by regular coverings of the real plane. This work is a first attempt to introduce a "discrete" geometry which in the case of square grids coincides with the actual representation of discretized straight lines. Besides of this, it shows that, as long as the fulfillment of all Euclid's axioms is not required, a "reasonable- looking" discrete geometry is possible. Moreover, the geometry introduced is suitable to all types of regular coverings of the plane, including hexagonal ones.