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.
*