DISSERTATION ABSTRACTS IN COMPUTER GRAPHICS
Clifford A. Shaffer
Department of Computer Science
Virginia Tech
Blacksburg VA 24061
(shaffer@siggraph.org; shaffer@vtopus.cs.vt.edu)
Welcome to the fourth compendium of dissertation abstracts in computer
graphics. Due to the overwhelming number of submissions received, we
expect to publish two lists this year. The deadline for the next
compendium is May 15, 1992. All submissions should be of the same
form as those in this list, and should be sent to the address listed
above (electronic submission preferred).
I would like to make one change in the format for future lists. In
the past, the author's address could either be where the work was
performed, or where the author is currently. Ordering information
is sometimes also the author's current address. In such cases, the
degree granting institution may never be listed. In the future,
please include the advisor's department and institution with all
abstract submissions in order to clarify the situation.
Note that most of the abstracts appearing this time come from
Rensselaer Polytechnic Institute. To save space, I will list the
ordering information once as:
Ms. Ilene Fretto
Rensselaer Design Research Center
CII 7015
Rensselaer Polytechnic Institute
Troy, NY 12180-3590
ilene@rdrc.rpi.edu
Cost for these reports is $20 for University requests and $30 for
Industrial requests, payable to RDRC. When ordering from RPI, please
note the TR number, included with the abstract below. Special thanks
go to David Breen of RPI for supplying these abstracts.
-----------------------
The Graphical Processing of NURBS in a Highly Dynamic Environment
Salim S. Abi-Ezzi
Rensselaer Polytechnic Institute
(TR-89001)
Level: Ph.D. Thesis
Date: May 1989
Advisor: M. Wozny
We address the problem of direct graphical processing of B-spline
based models in a graphics system. We focus on graphics systems
intended for interactive design and engineering applications,
primarily architectural and mechanical CAD. It is desirable that
the systems: 1) retain the graphical data in order to support the
concept of graphical data editing, and 2) perform basic rendering
techniques on continually (dynamic) data in order to achieve
maximum interactivity.
We present a solution that emphasizes formality by ensuring the
generation of accurate images, and completeness by ensuring the
proper processing of general graphical data. There are cases of
mathematically well-defined data that were not addressed in the
past because they were judged as impractical. We suggest that
there are important, practical applications for these cases and we
demonstrate how they are handled within the framework of our
solution. This drive for formality and completeness is an
important step towards ensuring the robustness and credibility of
graphics systems.
The emphasis on formality and completeness has a potentially
negative impact on efficiency. We successfully counter this
concern by developing the general concept of graphical data
compilation. This concept facilitates and speeds traversal by
identifying components of the graphical data that can be computed
at creation time and that remain usable after data edit
operations. We systematically apply this concept to reduce the
mathematical form of the graphical data into a simpler but still
complete form.
Furthermore, we develop and provide algorithms for the factoring
and classification of homogeneous transformations that lead to
efficient forms of the conceptual pipeline. We compare and
contrast adaptive and uniform tessellation techniques, whereby we
conclude that uniform techniques are more favorable for solving
the problem at hand. Uniform techniques meet the approximation
criteria based on a priori differential analysis of the
primitives. We absorb the majority of the complexity of trimmed
surfaces at compilation time, and we incorporate support for the
simplified form of trimming with the tessellation process. We
give the results of extensive experimentation with different
approximation schemes on geometric reflectance parameters, and we
treat such approximations more formally than they have been
treated in the past.
--------------------------------
A Z8001 Based Host Computer Interface for the Octree Processor
Ramon D. Acosta
Rensselaer Polytechnic Institute
(TR-82017)
Level: M.S. Thesis
Date: August 1982
Advisor: M. Wozny
This report describes the hardware and software design of a host
computer interface for an Octree Processor work station. Octree
encoding is a solid modeling scheme employed in the
representation, manipulation, and display of geometric objects.
octrees consist of hierarchical tree structures used for the
digital representation of these three-dimensional objects. The
Octree Processor is a special purpose hardware system which
operates on Octrees. It is composed of four subsystems: tree
processors, node memory, a display processor, and a host
interface. This system uses hardware to take advantage of the
fact that the manipulation of Octrees involves performing many
simple integer calculations and accessing a large memory.
The main purpose of the host interface is to establish
communication between the Octree Processor and a host computer.
Its activities are directed by a Z8001 16-bit microprocessor with
its associated memory. Communication with the host computer is
done by means of an IEEE-488 standard parallel I/O port. The host
interface can also communicate with a user using two RS-232C
serial I/O ports. Another function of this subsystem is to
monitor the activity of the tree and display processors. User
commands are executed by managing these processors in their
performance of Octree algorithms on data obtained from the node
memory.
--------------
A Flexible Shading System for Interactive Image Synthesis
Anthony A. Apodaca
Rensselaer Polytechnic Institute
(TR-86034)
Level: M.Eng. Project
Date: December 1986
Advisors: P. Getto, M. Wozny
Image synthesis is a specialized subdiscipline of color raster
computer graphics which deals with calculating the colors that
would be present in a real photograph of an imaginary scene
represented mathematically in a computer. Because physically
accurate algorithms for light reflection in a scene are very
expensive to compute, most image synthesis programs run for long
periods of time to generate a single image. This means that there
is no interactive loop for the design of subtle but vitally
important nuances of color and material properties of the surfaces
of the objects in the scene.
The project describes an experimental shading system which is
integrated into the image synthesis environment at the Center for
Interactive Computer Graphics at Rensselaer Polytechnic Institute.
The shading system attacks the interactivity problem by providing
a flexible, interactive environment in which to design materials,
lighting conditions and shading algorithms, and select the
appropriate ones to use to shade the objects in a synthetic image.
The system presents the user an environment in which he can make
modifications to these parameters and see the resulting new
synthetic image with a minimum of recalculation, and thus a
minimum of time. This project also implements a new paradigm for
the description of material properties and textures of objects.
---------------------
Interactive Computer Design of the Banbury Mixer on the Gerber
IDS-80 System
Lee A. Appelbaum
Rensselaer Polytechnic Institute
(TR-83010)
Level: M.S. Project
Date: May 1983
Advisors: H. McLaughlin, M. Wozny
This project provides the software necessary to model a four-wing
Banbury rotor on the Gerber IDS-80 turnkey system. The mixer
blade contains as its 'mid-section' a transition from one twisting
ellipse to another. Attempts to model this region with bicubic
patches had proved insufficient, hence a new approach was devised.
Rather than trying to describe the surface as a patchwork of
points, a set of curves lying on the surface is designed. Slicing
these curves with a plane passing through the z-axis, we can
define points on these curves with the same theta (the model is in
cylindrical coordinates). There are generally not enough points
to model the odd shape, thus the designer is also allowed to
define the slopes of the splines at these points. By proper slope
specification, the desired shape of the surface can be modeled.
-------------
A Scan-Line Display Approach to Interactive Constructive Solid Modeling
Peter R. Atherton
Rensselaer Polytechnic Institute
(TR-83026)
Level: Ph.D. Thesis
Date: August 1983
Advisor: M. Wozny
A new methodology for resolving visible surface images of solid
models derived from Boolean combinations of volumetric building
blocks is the major contribution of this dissertation. The
algorithm introduced here is an extension of polygon-based
scan-line hidden-surface removal procedures, and it integrates
knowledge of a Boolean construction tree in the surface resolution
process. Initial implementation tests indicate that substantial
performance improvements over previous methods can be achieved
with this new display algorithm, and that computational growth is
less than linear with increases in model complexity.
The application of volumetric Boolean set operations to solid
objects in order to define more complex solid objects is commonly
referred to as constructive solid geometry (CSG). In order to
derive the criteria for CSG part display, a dual solid modeling
system approach is introduced. This dual solid modeling
philosophy suggests that two solid modelers are necessary to
successfully satisfy both analytical precision requirements and
user interactive visualization requirements. The portion of the
visual solid modeling task addressed in this thesis provides
greatly improved response capabilities, as compared to other
systems, by striving to optimize the CSG modeling computations,
specifically for display purposes.
Based on the high-speed and low-resolution criteria for the visual
solid modeler, polygon approximations of analytic boundary surface
models are recommended for display applications. In order to
quantify the effectiveness of imagery generated from polygon
approximated models, sphere model imagery derived from several
polygon-density and shading procedures was evaluated by thirty
people for form faithfulness and aesthetic appeal. Results of
this study support the notion that polygons can be used
effectively to produce smooth shaded imagery of curved surface
models.
-----------------
A Study of an Extensible Architecture for Three-Dimensional
Computer Graphics
David Avraamides
Rensselaer Polytechnic Institute
(TR-91014)
Level: M.S. Thesis
Date: May 1991
Advisors: R. O'Bara, M. Wozny
Existing computer workstations employ a high-performance hardware
rendering pipeline subsystem. Often, an application exercises only a
small fraction of the capabilities of the pipeline and may use only one
or two types of geometric primitives. Yet, the graphics subsystem must
be designed with the ability to service a wide variety of requests and
types of geometry. A flexible pipeline architecture, that could be
configured to best match the demands of the application could outperform
traditional architectures.
Building such a system is not a practical approach to evaluating the
architecture. An alternative is to create such an architecture using
software components. These components model the behavior of the
equivalent hardware modules allowing an architecture to be built,
simulated, evaluated, modified and reevaluated.
In this manuscript, the design, development and use of a system for
simulating a flexible and extensible computer graphics rendering
architecture is discussed. The system is flexible in that the stages
comprising the architecture can be place in an arbitrary order, and
their configuration is established at run-time. It is extensible in
that new stages, or enhancements to existing stages, can be easily
incorporated into the simulator. The tool can be used in the design and
analysis of new and existing graphics architectures and algorithms by
providing accurate timing information about the system's performance.
The tool can be used to prototype, test and evaluate new processing
stages, algorithms and architectures for solving problems in computer
graphics. The simulator is unique in that it does not model a specific
architecture, rather it provides a toolkit from which to build
simulators.
Results of this work show that the simulator provides accurate timing
information when compared to performance specifications for an existing
architecture. It is shown to be flexible by reordering the stages to
realize display features that were not explicitly designed into the
system. Finally, the extensibility of the system is demonstrated by
adding a new stage to the class and producing an image with it.
-------------------------
Geometric Modeling and Fluid Dynamic Analysis of Swimming Spermatozoa
Alan H. Barr
Rensselaer Polytechnic Institute
(TR-83023)
Level: Ph.D. Thesis
Date: October 1983
Advisor: G. Odell
In this thesis, supporting evidence is provided for the hypothesis
that new forward speed is an important selection criterion
governing the external morphology of freely swimming spermatozoa.
Geometric and fluid-dynamic tools and techniques are developed to
model realistic time-varying shapes of micro-organisms, and to
calculate the three-dimensional trajectories along which the
organisms swim. In the process of achieving this, a set of new
solid primitives, called superquadrics, and a class of deformation
operators were created to model the head shapes and the tail
waveforms. These new geometric techniques have many potential
applications in the context of computer-aided design, and in the
analysis and display of time-varying three-dimensional shapes. In
particular, a transformation rule for normal vectors analogous to
the chain-rule of multidimensional calculus is developed, and a
methodology for performing inextensible curvilinear
transformations is presented. The solution to the arbitrary body
problem of Stokes flow is obtained, in which the swimming velocity
of an arbitrarily deforming body is derived in closed form, in
terms of the linear Thrust-Velocity operator, L. This
arbitrary-body solution can calculate trajectories of swimming
micro-organisms utilizing any fluid-dynamic paradigm which
calculates the net force and moment exerted by a Stokes fluid on a
moving body. The method is also used to derive approximate
solutions to the swimming velocity of a conglomerate body, in
which interactions between parts of the body are neglected.
Parameterizations of realistic tail-beat waveforms are developed,
consistent with frame-by-frame cine film analysis of live swimming
spermatozoa. Figures of merit for the swimming efficiency are
calculated for a family of head shapes and tail waveforms, to
determine the relative effect of each of several configurational
parameters. Optimal headshapes and motions are shown to exist in
this parameter space, and qualitative properties of the shapes are
obtained. The correlation between the optimal high-speed
(theoretical) head-shapes in this family and the natural (live)
head shapes indicate that speed is an important evolutionary
selection criterion governing the evolution of spermatozoa.
-----------
Computing the Unit Normal for Non-Uniform Rational B-Spline Surfaces
Jan Helge Bohn
Rensselaer Polytechnic Institute
(TR-89061)
Level: M.S. Thesis
Date: December 1989
Advisors: S. Abi-Ezzi, R. O'Bara, M. Wozny
A modern graphics system, such as one based on PHIGS+, gives an
application the ability of lighting and shading objects, including
primitives such as non-uniform rational B-spline (NURBS) surfaces.
The problem is that exact calculation of the parameters that go
into the lighting calculation of NURBS surfaces, are prohibitively
expensive on all but simple models.
In addressing this problem, we investigate approximations of the
lighting parameters, in particular the surface normal. Starting
out with the standard industry approach of using a single bicubic
approximation patch per surface patch, we extend the approach by
using a single biquintic approximation patch, and as an
alternative, we also used a grid of bicubic approximation patches
per surface patch. Neither of these approaches proved
satisfactory.
The solution came through the development of the scaled surface
normal, a polynomial expression for the unnormalized normal for
rational and polynomial surfaces. By increasing the startup cost,
we reduced the per point evaluation costs. The problem of startup
costs is significantly reduced by retaining and reusing previously
computed intermediate results during subsequent traversals of the
rendering pipe-line.
We also show how one can realize a 10-20% computational saving at
evaluation time by using a lookup-table for normalization, and by
performing the lighting calculations in lighting coordinates.
Lighting coordinates are angle-preserving with respect to world
coordinates, yet they are computationally close to device
coordinates.
----------------------
Creation and Smooth-Shading of Steiner Patch Tessellations
David E. Breen
Rensselaer Polytechnic Institute
(TR-85016)
Level: M.S. Thesis
Date: August 1985
Advisor: M. Wozny
Motivated by recent work with Steiner patches, a method has been
developed to create C0 tessellations of Steiner patches which
approximate high order biparametric surfaces. An accompanying
technique has also been created to smooth-shade the tessellation
in order to produce high quality color raster images. The whole
process is an extension of the tessellation and rendering process
using polygons. The Steiner patch method provides a better
approximation with fewer geometric elements and non-jagged
silhouettes.
The tessellation algorithm utilizes the properties of the
Bernstein-Bezier representation of Steiner patches. The algorithm
fits Steiner patches to ordered surface point and normal data.
The resulting tessellation is C0 everywhere and C1 at the data
points. The unique normal vectors at the data points are
interpolated over the tessellation during rendering in order to
produce a smooth looking surface.
------------------
A Prototype PHIGS Archival Mechanism
Mogens Brolin
Rensselaer Polytechnic Institute
(TR-86041)
Level: M.S. Project
Date: June 1985
Advisors: S. Abi-Ezzi, D. Spooner
The Programmers Hierarchical Interactive Graphics Standard (PHIGS)
is a graphics standard under development by the American National
Standards Institute (ANSI). An experimental environment to
evaluate and study PHIGS concepts has been developed at the Center
for Interactive Computer Graphics at Rensselaer Polytechnic
Institute (RPI). The goal of this work has been to evaluate the
feasibility of PHIGS concepts from an implementation viewpoint and
the utility of a PHIGS system supporting complex graphics
applications.
In this paper I present a subset of this PHIGS implementation.
The subset constitutes a complete archival mechanism as described
in the PHIGS document. The routines provide methods for archiving
PHIGS structures in files, retrieving structures from files and
deleting structures from files. In addition there are routines
for inquiring file contents and archival, retrieval and deletion
of workstation view entries.
-----------------
Direct display algorithms for solid modelling
Willem F. Bronsvoort
Faculty of Technical Mathematics and Informatics
Julianalaan 132
2628 BL Delft
The Netherlands
Level: PhD Thesis
Date: June 1990
Advisor: Denis J. McConalogue
Ordering Information:
Willem F. Bronsvoort
Faculty of Technical Mathematics and Informatics
Julianalaan 132
2628 BL Delft
The Netherlands
In this thesis algorithms are discussed for displaying geometric models
of three-dimensional objects. An important use of such algorithms is
in CAD/CAM-systems to give the designer insight in the shape of a
design.
Of particular concern here are direct display algorithms for
constructive solid geometry models and generalized cylinders. 'Direct'
in this context means that a solid object is displayed without the need
to convert its model into a boundary representation providing the
information about faces, edges and vertices required by the standard
display algorithms.
For constructive solid geometry models, the starting point is a
collection of primitive objects, such as cubes, spheres and cylinders,
that can be combined into more complex objects with set operations.
The two alternatives for displaying such models, namely conversion
into a boundary representation followed by display with a standard
algorithm, and direct display with an adapted algorithm, are weighed.
An overview of direct display algorithms for constructive solid
geometry models is also given.
An efficient standard algorithm for display of models approximated
with planar faces is the scanline algorithm. This algorithm can be
extended to a direct display algorithm for constructive solid geometry
models in a rather straightforward way. A detailed description is
given of such an algorithm.
Next, several methods are described to further increase the
efficiency of such scanline algorithms for constructive solid
geometry models. First, a number of techniques are discussed that
reduce the extra time required for processing constructive solid
geometry models. Second, an algorithm is discussed that, when possible,
performs the visibility computations for larger areas of the screen per
step than a scanline algorithm does; a version of this algorithm for
producing line drawings is also given. Third, local updating of an
image, in which only those parts are redisplayed that may have changed
since the previous display, is discussed. For all methods, results are
given in the form of images and computing times.
Generalized cylinders are objects defined by an arbitrary two-dimensional
contour, or cross-section, and an arbitrary three-dimensional trajectory
along which to sweep the contour. With profiled generalized cylinders,
the contour can be scaled along the trajectory in two perpendicular
directions according to two profile curves. An exact definition of such
objects is given. Here also the alternatives for display, namely
conversion into a boundary representation followed by display with a
standard algorithm, and direct display with a special algorithm, are
compared.
Next, two direct display algorithms for generalized cylinders are
described. The first is a ray tracing algorithm with which high-quality
images with various optical effects can be produced, but that requires
much computing time. The second is an algorithm that scans the surface
of the object in a way that generates enough points to produce a smooth
image without gaps; this algorithm is simpler and much more efficient
than the ray tracing algorithm, but the image quality obtainable is
lower.
Finally, some conclusions are drawn, and directions for further
research on direct display algorithms for solid models are identified.
------------------
Graphical Cross-Referencer
Albert J. Bunshaft
Rensselaer Polytechnic Institute
(TR-82009)
Level: M.S. Thesis
Date: May 1982
Advisor: M. Wozny
Interactive computer graphics has yet to reach its potential in
the program development environment. In many cases, information
can be assimilated more readily when presented graphically. This
study demonstrates the power of graphics in one specific
application, presenting program organization via automated
hierarchical structure diagrams.
A cross-referencer is a tool which determines the logical
interactions present in software. The cross-referencer parses
compiler output (object code) from which is obtains information
about the software. The utility typically outputs a text listing
which describes the interactions found. A Graphical
Cross-Referencer communicates the same information through
hierarchical structure diagrams. In this manner, information
previously obtained from text is now presented in a graphical
form. This paper demonstrates the power of graphical
cross-referencing in helping programmers visualize program
structure and in providing software developers with a useful form
of documentation. Graphical Cross-Referencer is a software
utility which effectively integrates the use of graphics into a
tool commonly used by programmers.
The Graphical Cross-Referencer developed has been designed to be
very flexible, allowing it to be placed in a variety of
environments with a minimum of effort. The program is written in
FORTRAN 66 using a device independent Siggraph core compatible
graphics system. It is user configurable and easily adapted to
new compilers.
---------------
Methods for the Fast Computation of Illumination and Shading Algorithms
(in German)
Ute Claussen
c/o AITEC
Am Hartweg 106
D-4600 Dortmund
Germany
Level: Ph. D. Thesis
Date: December 1990
Advisor: Wolfgang Straber
Ordering Info: Send requests to the author.
In the last years, computer graphics has been heavily influenced
by the aim to increase the realism of the generated images. Especially,
illumination and shading plays an increasingly important role beside
modeling and hidden surface calculation methods. By the use of
application specific integrated circuits, rendering time is getting into
the range of real-time. In particular, this feature is interesting for
computer animated sequences.
In the work presented here, a concept for the real time rendering
of scenes with a Phong shading algorithm is developed in several steps.
Firstly, aspects of realistic rendering are investigated. By looking at
the physical basis, the importance of illumination computations for
realistic computer image generation is emphasized.
Afterwards, two main aspects of illumination computations, namely
shading algorithms and illumination models, are presented in an
overview. Classification schemes for both of them have been developed.
These schemes turn out to be completely covering all known methods.
This part of the presentation is closed with an overview about coming
standards which will include illumination and shading.
A judgement of the real time capability of each of the algorithms
leads to a restriction of the further investigations to linearly
interpolating algorithms. Linearly interpolating algorithms and their
properties are presented. By judging the quality of the generated
images and the hardware costs, a hierarchy of these algorithms can be
evaluated. It is shown that an increase in quality is coupled with an
increase in cost.
For the shading algorithm that is judged the most favourable, a
hardware implementation has been developed. The shading processor
presented will support next generation standards and real-time
rendering. A discussion of properties of the method as well as the
hardware close the thesis.
--------------------
Computer Modeling of an Archaeoastronomical Calendar
Laura G. Conway
Rensselaer Polytechnic Institute
(TR-84016)
Level: M.S. Thesis
Date: August 1984
Advisors: H. Mclaughlin, P. Getto, M. Wozny
A preliminary computer model of an archaeoastronomical calendar
known as the "Sun Dagger" was developed for the purposes of
researching its function, archiving its geometric properties, and
creating a basis for an interactive computer graphics display.
The calendar consists of three sandstone slabs leaning against a
southeast facing wall of a butte in New Mexico. Patterns of light
shine on two spiral shaped petroglyphs on the butte wall during
the passage of the midday Sun.
The model is based on existing data taken at the site, the most
significant of which are three-dimensional digitized coordinates
for points on the surfaces of the rocks. This data is tied to the
geographic coordinates of the site. Ultimately, the objective is
to make an accurate computer simulation of the shadows and light
patterns resulting from the orientation of the slabs, cliff, and
light source.
This initial modeling effort is comprised of three primary tasks;
the computation of geometric representations of the three slabs
using the scattered data; the calculation of the positions of the
Sun and the Moon; and the generation of shadows based on results
of the first two tasks.
A procedure for the geometric modeling of the slabs was developed
in which triangulation is performed on the scattered data and a
surface represented by planar facets is produced. These
intermediate results can be displayed as color-shaded raster
images or as wire frame images. Solar and lunar positions are
determined for any time of observation relative to the geographic
position of the site. Corrections are applied for effects of
atmospheric refraction and parallax. These computations result in
a direction vector for the light source which is used in
conjunction with the planar facets to compute shadows by ray
tracing. The resulting shadows are imposed on a pre-computed
image of the cliff wall.
The visual results of triangulation and shadow casting have been
favorable. Further testing must be done to determine if the
triangular facets represent a close enough approximation to the
original surface of the sandstone slabs. It is not yet known how
accurately shadows are generated because the complete set of data
is not currently available.
--------------------
A High Performance Packet Bus for Parallel Processing
Damian Deneault
Rensselaer Polytechnic Institute
(TR-86031)
Level: M.Eng. Project
Date: August 1986
Advisor: M. Wozny
A packet bus protocol with support for multiprocessing, and a VLSI
implementation of the protocol have been designed and simulated.
The Graphics Bus is intended to provide the interprocessor
communication for a high performance Graphics Display Controller
currently under development at Raster Technologies. The Graphics
Bus bandwidth approaches 40Mbytes/sec with inherent distribution
of commands among multiple processors. The VLSI design allows
different types of processors to access the Graphics Bus through a
single-chip interface. This interface isolates the processors
from the bus and simplifies the processor design.
In this report the design of the bus protocol and VLSI interface
are discussed. Simulation results are presented which verify the
function and performance of the bus and interface.
---------------------
Two Dimensional Shape Approximation With the Delaunay Triangulation
Diane Desenberg
Rensselaer Polytechnic Institute
(TR-86051)
Level: M.S. Thesis
Date: December 1986
Advisors: H. McLaughlin, M. Wozny
An appropriate polygonal approximation to a curve can be
constructed from a discretization of that curve. This thesis
seeks a method to obtain the appropriate ordering of a set of
points taken from a curve. The convex hull and the Delaunay
triangulation of the point set are used as a base for the method.
Points from the data set are added to the convex hull by removing
triangles from the Delaunay triangulation, until all the points in
the data set lie on the boundary. Seven different criteria are
used to determine the order in which triangles are removed. Each
criterion is applied to seven sets of curves at various density
refinements. Subsequent analysis reveals two surprising results.
The first is that the behavior of some criteria deteriorate as the
curves are sampled more densely. The second is the degree to
which a criterion might show outstanding performance on one data
set and produce disastrous results on another. Although no
criterion performed better than the rest on all data sets, a
criterion combining various properties of the other criteria shows
the best results to date. Polyhedral surfaces may also be derived
using a straightforward application of this method to three dimensions.
-------------------
Graphical Decomposition and Retraction: An Approach to Collision-Free
Path Planning
Kurt Dittenberger
Rensselaer Polytechnic Institute
(TR-90005)
Level: Ph.D. Thesis
Date: January 1990
Advisor: H. McLaughlin
This thesis treats the collision-free path planning problem using a
configuration space approach. A collision detection algorithm is used
to determine the parts of a grid in the configuration space which
correspond to collision-free positions. The collision-free path
planning problem is thus transformed into a search problem on a paired
directed graph whose nodes are the grid points. There are arcs between
two neighboring grid points if and only if all points on the line
segment between them correspond to collision-free positions.
This thesis shows how to obtain for a given tolerance, d, the
discretization steps that guarantee the existence of a path on the grid
whenever there is a path for which, at all its positions, the distance
between the robot and the obstacles is larger than d. The
discretization steps of a grid can be twice as large as the
discretization steps of a voxel approximation that would also contain a
path. Grids, therefore, yield graphs whose order in 2**n times smaller
than the order of graphs that result from voxel approximations, where n
is the dimension of the configuration space.
A new method to preprocess these graphs is developed so that the
resulting structure allows efficient searching. The graph is decomposed
into two subgraphs. One graph is a paired directed graph. The second
graph is a loop-free directed graph whose leaves are nodes of the first
graph. The second graph guarantees that, for all nodes not in the first
graph, we find a path to a node in the first graph without a search.
The first graph preserves the connectivity of the original graph in the
sense that if there is a path in the original graph between two of the
first graph's nodes, then the first graph also contains a path.
The additional properties which these decompositions must have in order
to provide good paths are investigated, and algorithms to produce these
decompositions are developed. To successfully treat the questions and
problems that emerge from this graph decomposition method, topological
concepts for paired directed graphs are defined.
-----------------------
Implementation of a Ray-Tracing Algorithm for Rendering
Superquadric Solids
Bruce E. Edwards
Rensselaer Polytechnic Institute
(TR-82018)
Level: M.Eng. Project
Date: December 1982
Advisor: M. Wozny
An important goal of the Computer Graphics industry is the
rendering of realistic images from computer defined data bases.
This report describes parts of a technique, called "Ray-Tracing",
for computing two dimensional raster scan images of three
dimensional solids composed of superquadric primitives. The goal
of this work is to produce the most realistic images possible for
such three dimensional structures.
Ray-tracing algorithms allow the user to render highly complex
surface properties of solids. Such properties include specular
reflection, pure reflection, refraction and textures.
The work described in this report does render specular and pure
reflection, and refraction. This ray-tracing algorithm can
accommodate, but does not currently handle, surface textures.
The final images produced are of a very high quality and realism.
The trade-off quality is large amounts of processor time.
-----------------
Node Memory Sub-System Design of the Tre0 Solid Modeling Processor
Donald B. Faatz
Rensselaer Polytechnic Institute
(TR-82020)
Level: M.Eng. Project
Date: December 1982
Advisor: M. Wozny
Octree encoding is a technique for representing models of solid
objects in a digital computer. Manipulation of models represented
in this way can be decomposed into parallel tasks executed in
independent parallel processors. To do this, requires a special
purpose processing system. Tre0 is a processor/workstation
designed to perform exactly this task. This work details the
physical packaging of this system and the detailed design of its
octree node memory. The node memory is a data memory structured
as a linked list. All list management is performed by the
hardware of the node memory subsystem. The system provides, as
primitive operations to processors, the capability of reading a
node at a particular address, writing a node into the list
structure, deleting a given node from the structure, and
reinitializing the list.
-----------------
NC Tape Verification Using Octree Encoding
Lawrence D. Finkel
Rensselaer Polytechnic Institute
(TR-81007)
Level: M.S. Thesis
Date: May 1981
Advisor: M. Wozny
A computer graphics software system has been created whereby
machine control data for numerically controlled machines can be
used to graphically simulate NC processes. This system generates
solid modeling commands which can execute and display the tool
paths specified by the NC tape. A geometric data base is used to
model the tools, clamps, and raw stock needed for the simulation.
Full color raster graphics technology is used for the display.
Creation of any 3-axis machined part can be achieved using
point-to-point positioning, straight line paths, or circular arcs.
Further flexibility is achieved by allowing for absolute or
incremental files, and tool changes during execution.
----------------------
Extraction and Tessellation of Trimmed Surfaces
Joseph W. Fisher
Rensselaer Polytechnic Institute
(TR-85021)
Level: M.S. Project
Date: December 1985
Advisors: M. Wozny, D. Spooner
A project recently completed at the RPI Center for Interactive
Computer Graphics dealt with the tessellation of geometric models
extracted from the CATIA CAD/CAM system. The purpose of this
original project was to transform the geometric surface
representation stored in the CATIA database to one more suitable
for high quality rendering.
This report describes the implementation of an algorithm which
extends the capability of the above software to include the
tessellation of faces. A face is a sub-surface defined by a
closed boundary curve lying on a base surface. This project
includes the modifications of the original software necessary to
extract and represent the original face definition, and to
generate the polygonal approximation of the face.
The primary purpose of this project is to facilitate the rendering
process for a designer utilizing the CATIA geometric modeler. The
software produced accomplishes the extraction and tessellation of
surface, face and polyhedral geometries from the CATIA database.
The input to the program is a model contained in the database, and
the output is a file containing a polygonal approximation of that
model which is suitable for rendering in a variety of different
ways. The enhancement of the tessellation capabilities of the
program has broadened the domain of applicable models, and has
increased the usefulness of the program to the designer.
-------------------
Interactive Design of Steel Framed Buildings
Michael J. Fusco
Rensselaer Polytechnic Institute
(TR-84004)
Level: M.Arch. Thesis
Date: December 1983
Advisor: M. Ackroyd, G. Droste
This thesis documents the development of an interactive modeling
and analysis program on a PRIME-750 computer, with IMLAC graphics.
In documenting this development the author is concerned with the
concepts, the applications, and the directions which may be
suggested by this program.
The program allows an Architect/Engineer to interactively model
the three-dimensional superstructure of a building on a graphics
terminal. The data resulting from this process, may serve a dual
purpose. First, it may be used to produce perspective views of
the building. These views may have hidden lines removed and
surface patterns applied. Secondly, this data may be used for
indeterminate analysis of the building structure, and design of
its structural members, subject to AISC building code requirements.
This development began with two goals. The first goal was to make
all interaction, between the user and the program, user friendly.
In order for this program to become an acceptable tool in the
architectural profession, accomplishing this goal was essential.
The second goal was to utilize current analytic and programming
techniques. In the same fashion, accomplishing this goal was
essential to making the program effective.
The products of this development are four-fold: (1) the program
may be used to facilitate the quick and easy modeling of a
building's structure; (2) the program has merged graphic input and
graphic output with hard-numbered analysis and design; (3) the
program has utilized coding techniques which allow for its
continued growth; and (4) the program has provided hooks in its
data which will facilitate this growth.
---------------
An Extensible CAD System Applied to the Study of Swept and Lofted Surfaces
Phillip H. Getto
Rensselaer Polytechnic Institute
(TR-83022)
Level: M.Eng. Project
Date: December 1983
Advisor: M. Wozny
This report describes a CAD "test-bed" software system and the
geometry it has been used to study. The project is partitioned
into two major areas; the first area has been a study of several
types of geometry, both mathematically and practically, via a CAD
test-bed software system. The second area has been the design and
implementation of CAD test-bed software.
The types of geometry which have been studied are cubic splines,
translationally swept surfaces, and generalized lofted surfaces.
A swept surface is defined as the sum of two independently
parameterized curves. A lofted surface can be thought of as a
continuum of polynomials that blends between two boundary curves.
Software to implement the geometry, mentioned above, has been
written and integrated into the CAD test-bed environment. This
has provided the opportunity to evaluate both the geometry of
interest and the test-bed's effectiveness.
The CAD test-bed software provides a highly modular environment,
which easily accommodates new components for testing, analysis,
and evaluation. To include a new component, be it a geometric
element or a user interface, the old routine or set of routines
are removed, and the new ones "plugged in" in their place. The
rest of the system need not be changed because it is isolated from
the section being changed. For example, the addition of a new
type of curve would not involve changes to the intersection
routine, because the intersection routine uses the evaluator
routine to evaluate a curve. The concept of an evaluator routine
has proven very helpful when designing and building highly modular
software. It is a "smart database retrieval" routine, that is to
say, it reads an entity from a database and evaluates it at a
specified parameter space point. Contrast this with a typical
retrieval which would just return the coefficients of an entity
and the user's software would then be responsible for the
evaluation of the entity.
--------------
Reparameterization of Surfaces by Lines of Curvature
Jeffrey Goldsmith
Rensselaer Polytechnic Institute
(TR-83014)
Level: M.S. Project
Date: October 1983
Advisor: D. Isaacson
This project entails the interactive design of and the display of
surfaces via curves on the surface that are the geometric lines of
curvature of the surface. It takes as input a parametric
definition of a surface and computes curves on the surface that
follow the directions of minimum and maximum curvature at each
point along their lengths. That is, the tangent vector to a line
of curvature points in the direction of least curvature at that
point, for all points of the curve, or its points in the direction
of highest curvature at all points. The project computes
coordinate transformations that reparameterize the surface so that
the new parameter curves are these lines of curvature. The
surface will be displayed by a mesh of curves on the surface.
This mesh is orthogonal at each crossing because the lines of
curvature through any point are always orthogonal, unless that
point has very special properties that allow more than two lines
of curvature through it. These points are very important to the
shape of the surface. This technique will emphasize their
position and thus describe the surface better than most arbitrary
parameterizations.
-------------
Hardware Design for the PHIGS Transformation Processor
Michael H. Greenberg
Rensselaer Polytechnic Institute
(TR-86035)
Level: M.Eng. Thesis
Date: September 1986
Advisors: S. Abi-Ezzi, M. Wozny
Hardware has been built for a transformation processor as part of
the development of a microcomputer based PHIGS subsystem. This
project was motivated by the need for real time interactive three
dimensional graphics to aid the engineering and scientific design
capabilities of microcomputers. The emerging three dimensional
graphics standard PHIGS was chosen to be implemented and the
architecture of a PHIGS subsystem was developed. The
transformation processor will be used to provide the floating
point computational capability for the rest of the PHIGS
subsystem. In order to perform real time three dimensional
computer graphics, the transformation processor needs to perform
floating point operations at a rate of two megaflops.
The transformation processor was designed using the WTL 1032/1033
32 bit floating point multiplier and ALU processors which can
perform floating point operations at a rate of eight megaflops. A
WTL 1066 32 word by 32 bit 5 port register file is used in the
system along with two kilobytes by 32 bits of local data storage
which can be accessed by a bit slice address generator based on
three Am2901 4 bit ALU slices. The transformation processor is
responsible for performing the multiplication of a 1 x 4
coordinate vector by a 4 x 4 transformation matrix at a rate of
60,000 times per second. Other operations such as clipping,
normalization, matrix inversion, and PHIGS utility functions
requiring operations such as sine and cosine are also to be
performed by the transformation processor. The final design of
the transformation processor operates at six megaflops and
preliminary tests show that a figure with 1000 vectors can be
transformed in real time.
----------------------
An Interactive Graphics Editor for Printed Circuit Design
Andrew J. Haber
Rensselaer Polytechnic Institute
(TR-81013)
Level: M.Eng. Project
Date: August 1981
Advisor: M. Wozny
The design and implementation of a program for computer aided
printed circuit board design is described here. The goal is to
use computer graphics to reduce design time and minimize errors in
the design of printed circuit boards. The program includes
functions for describing the board, describing the connections to
be made, a rat's nest placement aid, and a highly interactive
editor for manual layout of printed circuit traces. This document
describes the major steps in designing a printed circuit board and
the facilities provided for accomplishing these steps. Since the
routing of traces consumes the major part of the designer's time,
the trace editor plays a central role in the design process. The
features and aids incorporated in the editor are carefully
outlined and explained. Finally, a few of the issues involved in
the implementation on the computer are also discussed.
---------------
Primitive Generation, Perspective Transformation, and
Semi-Transparent Display of Octree Encoded Objects
Franz H. Herbert
Rensselaer Polytechnic Institute
(TR-81008)
Level: M.Eng. Thesis
Date: May 1981
Advisors: L. Doctor, J. Torborg, M. Wozny
This work describes several key enhancements to the solid modeling
package currently in use at the Center for Interactive Computer
Graphics. This package is based on Octree encoding, an efficient
tree representation of maximal suboctants of a 3D object embedded
in a cube universe. The set of encoded 3D primitives has been
extended to include the entire family of superquadrics and certain
surface patches. Algorithms for perspective transformation and
semi-transparent display have also been developed. An assessment
of computer requirements to process Octree encoded solid models is
given.
------------
Tools for Particle Based Geometric Modeling
Jay S. Hersh
Rensselaer Polytechnic Institute
(TR-88050)
Level: M.Eng. Project
Date: December 1988
Advisors: D. Breen, D. House, M. Wozny
Computer Based Geometric Modelers utilize a variety of
representations to model geometry. Most of these representations
are well suited to the modeling of rigid solids with well defined
surfaces. This project describes the implementation of a
representation suited to the modeling of non-rigid solids whose
surfaces may deform. The representation scheme, known as particle
based modeling, presents a capability for the interactive design
of irregularly shaped geometry. This scheme also allows the
dynamic perturbation of the geometry.
The implementation was incorporated within The Clockworks, an
object oriented modeling and visualization package. This geometry
can be dynamically deformed by relocation of control points which
define the geometry. The control points specify the center of
volume defining functions which sum to yield the geometry. They
can be manipulated via scripting mechanisms available from within
The Clockworks.
The project also implements an algorithm for converting geometry
modeled in other representations to the particle based modeling
scheme. This allows models defined with other geometry to access
current and future capabilities of the particle based
representation described herein. The algorithm utilizes a ray
firing technique by which it identifies intervals of the geometry
which exist along the ray. These intervals are subsequently
populated with particles.
-------------------
Hardware Design for the GIN Display Controller
Joseph P. Higham
Rensselaer Polytechnic Institute
(TR-85005)
Level: M.Eng. Project
Date: May 1985
Advisor: M. Wozny
A single-board, IBM Personal Computer-resident, very high
resolution color raster display controller has been designed and
built. The GIN Graphics Display Controller is part of a
microcomputer-based graphics workstation which will serve as a
test vehicle for an implementation of device-independent computer
graphics software concepts. GIN provides a display capability of
up to 1024 by 1024 pixels, 4 bits per pixel. Based on the NEC
uPD7220 Graphics Display Controller, GIN can support 1024 by 1024
pixel display in interlaced format and lower resolutions in
non-interlaced format. GIN pixel rates can be as high as 40 MHz.
The GIN Graphics Display Controller is designed as an I/O device
for the IBM Personal Computer. When installed as a stand-alone
graphics display controller, GIN relies on the IBM Personal
Computer to provide host-level graphics processing. A companion
card, the TONIC Graphics Command Coprocessor, may also be
installed with GIN in the IBM Personal Computer. Here, TONIC
provides host-level graphics-processing, off-loading often
repetitive graphics display tasks from the IBM Personal Computer.
------------------------------
An Object-oriented Interaction Model for Specification of Graphic
Dialogues
Wolfgang Hubner
Zentrum fur Graphische Datenverarbeitung e.V. (ZGDV)
Wilhelminenstr.7
D-6151 Darmstadt
Germany
Level: PhD Thesis
Date: May 1990
Advisors: Prof. J.L. Encarnacao, Prof. H. -J. Hoffmann
Ordering information:
Book Publications:
Hubner, Wolfgang: Entwurf graphischer Benutzerschnittstellen:
ein objektorientiertes Interaktionsmodell zur Spezifikation
graphischer Dialoge
Springer-Verlag
ISBN 3-540-53438-5
ISBN 0-387-53438-5
In this work, an object-oriented interaction model for the isolation and
specification of functional and descriptive components of graphics
interactions as well as their interdependencies within graphics user
interfaces is developed and, hence, user interface tools derived.
Proceeding from the outstanding position of graphics input in
interactive systems and from the increasing import of graphical,
directly manipulating forms of interaction for ergonomic user
interfaces, the model is tailored to the specific requirements of
graphics dialogue techniques. In a dialogue study first the
characteristics of graphics interactions are analyzed. More than 60
graphic-interactive application systems are examined by means of an
inquiry. The results thereof form the reference background for the
interaction model and for the evaluation of the user interface tools.
The object-oriented interaction model provides a complete frame for the
technical specification of all components relevant to the development of
graphics user interfaces.
Interaction techniques are described as classes within an extendable and
configurable hierarchy, Graphics user interfaces are presented by
directed, acyclic graphs of interaction objects. User input is modelled
by messages, the system's behaviour by methods.
Each interaction is composed of the individually designed components
Prompt (graphics output to prepare input), Trigger (input operation(s)
for event firing), Feedback (graphics output as an input result),
Semantics (application-dependent processing instructions for an
interaction), and Dynamics (control of dynamically changeable dialogue
sequences).
For the description of complex, continous interactions and for the
specification of dialogue sequences, the dialogue designer may, beside
elementary basic interactions with undivisible Trigger, create
hierarchically structured interactions. This is done by connecting the
input events of completely specified interaction objects with
predicate-logical or algorithmic trigger operators resulting in a
composite trigger and in the design of the remaining components.
The macrocosmos of global layer models (e.g. lexical, syntactic,
semantic level) and the separation into input, output, and application
is replaced by a microcosmos within each interaction object, containing
all components of a graphics interaction independently from its
abstraction level.
The applicability of the model is proved by two user interface tools:
IAMBUS converts the model into an object-oriented User Interface
Management System including an interactive design interface. Moreover,
the model forms the basis for the interaction component of the User
Interface Toolkit THESEUS. The evaluation shows that the development
efforts for graphics user interfaces could markedly be reduced and the
flexibility in designing graphics dialogues could be increased in
comparison to other tools.
-----------------
Interactive Inspection of Volume Data
Hans Jense
Department of Mathematics and Computer Science
University of Leiden
Leiden, The Netherlands
Level: PhD Thesis
Date: June 1991
Advisors: Jan van den Bos, Nies Huijsmans
Ordering Information:
Hans Jense
TNO Institute of Applied Computer Science
P.O. Box 6032
2600 JA Delft
The Netherlands
+31 15 69 7093
Research in volume visualization has thus far concentrated on finding
individual solutions to particular problems. One of the things that has
been lacking so far is a look at the generic aspects of different volume
visualization techniques. In addition to this, the emphasis has been on
the rendering of highly detailed images, requiring long display times
of sometimes up to an hour. The usefulness of the interactive display
of approximate renderings has not yet been studied extensively. Thirdly,
Spatial editing methods, i.e., methods to perform spatial selections on
objects and manipulate the selected part separately from the rest of the
object, are rarely mentioned in the literature. Finally, the processing
--- such as filtering --- of volume data sets is mostly done ''slice-
by-slice'', using conventional 2D image processing methods.
The purpose of the research described in this thesis is to assess the
feasibility of interactive inspection of general scalar volume data.
To this aim, several display algorithms have been implemented and their
performances compared. Motivated by the close correspondence of volume
data sets to digital images, it will be shown that a number of image
processing techniques can be extended to 3D. Furthermore, a method for
spatial editing of volume data sets, based on binary space partitioning,
is presented. Several different hardware architectures are compared
with respect to their suitability to support interactive volume
visualization. Finally, a prototype of an interactive volume visualiza-
tion system has been built and experiments with various interaction
techniques have been carried out. Results of proposed solutions have
been evaluated both qualitatively and quantitatively.
---------------
Interactive Computer Modeling of Airframe Structures
Bruce P. Johnston
Rensselaer Polytechnic Institute
(TR-84010)
Level: M.S. Thesis
Date: April 1984
Advisor: M. Shephard
A method for the interactive computer modeling of airframe
structures is presented. The technique allows the designer to
interactively develop a three-dimensional model of both the
geometry and the structural components that make up an airframe.
The method combines the input and definition of outer contour
surfaces, the definition of section cuts and structural locations,
and the detailing of structural components in a single process.
The result is a model containing all the data necessary for later
analysis in an easily accessible and revisable form. With such a
computer model as a base, the time required for the generation of
finite element analysis models can be drastically reduced.
Computer graphics allows for interactive and visual definition of
the model and provides continuous feedback to the designer.
A prototype package was developed to demonstrate this method of
interactive definition of airframe structures. Models used as
figures and examples were created using this package.
----------------
A PHIGS-Based Interactive Tutorial for Advanced 3D Graphics
Steven Kader
Rensselaer Polytechnic Institute
(TR-88047)
Level: M.Eng. Project
Date: December 1988
Advisors: S. Abi-Ezzi, M. Wozny
Advanced 3D graphics systems are becoming more powerful and more
complicated. These systems are opening new doors in application
development, however, the ability to use these systems is a
problem. Training aids for these systems are becoming critical.
Manuals, short courses, and even videos are used to help in the
training process. The problem is the nature of the material that
must be presented, which is highly interactive, 3D graphics.
The purpose of this project is to develop a PHIGS-based
interactive tutorial for advanced 3D graphics. The tutorial is
designed to teach the major PHIGS (Programmer's Hierarchical
Interactive Graphics System) concepts, such as the hierarchical
grouping of graphical data, 3D viewing, and the name set
mechanism. The tutorial is a tool for both beginners, for
self-teaching, and experienced users, for teaching others or
verifying a specific detail.
Each of ten selected and important concepts is addressed by a
separate lesson. A lesson is then divided into two parts, an auto
sequenced explanation of the concept, and then a session where the
student can interact with the tutorial to test out what he/she has
learned. The auto sequence is nothing but a faked interactive
session, and hence it is a good introduction to the interactive
part.
The tutorial itself is a perfect application of PHIGS, that draws
heavily upon all PHIGS concepts. This fact makes it a good
teaching tool both directly, by explaining the PHIGS concepts, and
indirectly, by being an illustration of these concepts. Hence, an
alert user will get an insight on how PHIGS can be applied in
solving difficult graphics problems, which in this case is
teaching 3D graphics.
The uniqueness of the tutorial is the high interactivity of the
user interface and the ability to visually represent geometric
relationships, an event queue, a hierarchy of structures, or the
behavior of transformations. The tutorial has been evaluated by
IBM and is currently being distributed as an IBM product.
--------------------
Optimizing Ray Tracing Performance With Object and Spatial Coherence
Elaine V. Korngold
Rensselaer Polytechnic Institute
(TR-87047)
Level: M.S. Thesis
Date: August 1987
Advisor: M. Wozny
Ray tracing is a method for producing images with realistic
lighting, shading and texturing. In naive ray tracing rays are
shot from the viewer through the image screen into the geometric
model. Every ray is intersected with every object in the model
until the intersection point closest to the ray's origin is found
and shaded. Naive ray tracing is incredibly time consuming.
The performance of a ray tracer was optimized using object and
spatial coherence techniques. The object coherence technique
bounded objects in the model with parallelepipeds aligned with
world coordinate axes. The hierarchy of bounding extents was
built and traversed for each ray. The ray was intersected with a
given node in the hierarchy only if it had pierced the bounding
extent of its parent node.
The spatial coherence technique for complex polyhedra was
implemented to decrease ray tracing time for polyhedra with
hundreds of faces. A cellular grid was placed over the bounding
extent of each complex polyhedron. Octree subdivision and an
efficient polygon-box intersection algorithm were used to
determine for each grid cell which polygonal faces intersected it.
The grid was traversed for each ray that intersected the bounding
extent of a polyhedron using a fast integer stepping algorithm.
The ray that pierced the bounding extent of the polyhedron was
intersected only with polygonal faces in grid cells along its
path.
The ray tracing performance was improved by one order of magnitude
with the object coherence method and by another order of magnitude
with the spatial coherence method for complex polyhedra.
-------------------
Interactive CAD Software for Parameter Space Region Modeling and Display
Edmund Lau
Rensselaer Polytechnic Institute
(TR-85014)
Level: M.Eng. Project
Date: August 1985
Advisors: P. Putz, M. Wozny
Using the computer to help in control system design is drawing
more and more attention from system designers. Currently, there
is an algorithm which utilizes the parameter space concept for
computer-aided control system design. The major work of this
thesis is to implement and refine this algorithm using interactive
computer graphics. Basically, three modules have been written;
namely: REGION MODELING, REGION DISPLAY, and FEEDBACK DESIGN which
when combined with other modules (written by other students) forms
a complete stand-alone package.
In this report, the three modules mentioned above are described in
detail: their structures, functionalities, usage, and problems
encountered during the implementation process. Moreover, many
resulting parameter space regions corresponding to different
system order, system characteristics and design requirements are
presented. These illustrate the significance and the correctness
of the algorithm. Also, future possible enhancements are discussed.
-------------------
The Intersection of Parametric Surfaces
Randy B. Lee
Rensselaer Polytechnic Institute
(TR-84030)
Level: M.S. Thesis
Date: December 1984
Advisor: H. McLaughlin
The intersection curve between parametrically defined surfaces is
required in a variety of computer graphics applications. CAD/CAM
systems need to find accurate intersection curves as a basic
utility in design, analysis, and manufacturing. Image processing
also has a need for the intersection between surfaces if realistic
representation is desired.
The goal of this thesis was to produce an intersection algorithm
that is totally independent of the surface types being
interrogated while at the same time being fast, accurate, and
stable. This has been accomplished by developing an algorithm
that performs in the parameter space of the surfaces rather than
taking advantage of the 3D geometry of the particular surface
types. This thesis presents an original algorithm for finding all
intersection curves between to parametric surface patches.
Possible improvements and future research projects are also
explored. The speed, accuracy, and stability of the algorithm are
used as parameters for comparison to other existing intersection
algorithms.
An implementation of this algorithm was incorporated by the author
into a production CAD/CAM software system for CADAM, Inc., a
subsidiary of Lockheed Corporation. The entire package is
scheduled for public release in the summer of 1985.
--------------
Tree Processor Subsystem Design for the Tre0 Solid Modeling Processor
Mitchell D. Levinn
Rensselaer Polytechnic Institute
(TR-83007)
Level: M.Eng. Project
Date: May 1983
Advisor: M. Wozny
Tre0 is a system designed to manipulate octree encoded solids.
This report describes the design details of the hardware tree
processor subsystem in Tre0. The tree processor is a microcoded
processor with an instruction set and the data paths appropriate
to octree functions. It is designed to provide the flexibility
necessary for continued research into new octree algorithms while
providing a viable design station for the practical use of
existing algorithms. It is estimated that a Tre0 system employing
the tree processors presented here will provide up to three orders
of magnitude of speed improvement when executing octree algorithms
as compared to an implementation on a general purpose computer.
The tree processor hardware consists of a bit slice ALU and
controller with several special purpose stacks to allow fast
manipulations of octrees. Also included in the tree processor are
interfaces to other subsystems in the Tre0 system. The Node
Memory Interface allows fast compression and expansion of data
locally, where appropriate, and provides an efficient path to data
in the Node Memory subsystem when needed. The Host Interface Bus
Interface allows the Host Interface to control and monitor the
status of the tree processor.
---------------
Vector List Processing Firmware for a High Resolution Raster
Display System
Carleton G. Lorig
Rensselaer Polytechnic Institute
(TR-83013)
Level: M.Eng. Project
Date: August 1983
Advisor: M. Wozny
The purpose of this project was to design and implement VLIST, a
2D vector list processing system which would provide, within a
display system, a flexible yet powerful environment for the
performing of graphics related tasks. Using this system, 2D
graphical structures can be defined, drawn using a viewing
transformation, picked, highlighted, deleted, or read. Conceptual
simplicity without sacrifice to either performance or capability
was stressed in the design. The result is a firmware package
resident within a graphics display system, capable of providing a
user with an interactive environment, yet requiring only a minimal
amount of host intervention.
VLIST was written exclusively in Z8002 assembler and represents
two thousand lines of executeable code. The firmware was cross
assembled on a Prime 500 computer and the resultant object code
burned into PROM. The complete firmware package requires 8k bytes
of ROM.
-------------
Manufacturing Routings Using Computer Graphics
Susan E. Markowski
Rensselaer Polytechnic Institute
(TR-82015)
Level: M.Eng. Project
Date: August 1982
Advisor: M. Wozny
This project deals with human/computer communications relating to
the implementation of a "paperless" manufacturing environment.
Specifically, this project deals with the construction and
interpretation of instruction sets used to manufacture and
manually assemble special purpose integrated circuit boards. The
creation of the instruction sets using CADAM software for
altering, manipulating and storing symbols is investigated. It is
proposed that drawing time rather than subjective ranking of
drawing detail be used as a criterion for locating old drawings.
A workplace layout of the instruction sets is proposed, using the
relevant literature and an experiment by the author. The
workplace layout should include textual instructions, a full board
picture and an enlarged frame showing explicit instructions in
pictorial form. A new symbol set for use in this workplace layout
was developed using prototypes. Preliminary testing implies that
the new symbols and workplace layout will be cost-effective. An
experiment is proposed that will determine a method for evaluating
the cost-effectiveness of a retrieval program for old drawings.
----------------
CORY: An Animation Scripting System
Daniel R. McLachlan
Rensselaer Polytechnic Institute
(TR-85006)
Level: M.S. Thesis
Date: May 1985
Advisor: M. Wozny
This thesis describes an animation scripting system, CORY. It was
developed as a tool to facilitate the specification and execution
of computer generated motion sequences. This work can be divided
into two major thrusts: (1) the examination of scripting
principles and the determination of what constitutes a complete
workable set of scripting primitives; and (2) the actual
implementation of these primitives and evaluation of their
usefulness within the structure of the animation system being
developed at RPI.
One of the major requirements for CORY has been for the system to
be flexible enough to allow the animator to change any parameter
within the scene environment as a function of time. This allows
him/her to do not only rigid body motions but also to perform
shape deformation, color transformations and even dynamically
create and destroy objects.
The emphasis has been on examination of the basic building blocks
necessary for script design and execution. This is not intended
as an end unto itself but rather a set of primitives that can be
incorporated into a larger user-friendly interactive system. As a
means of creating a highly modular system, an object oriented
approach was used in the implementation.
The core of the scripting system has been implemented and used to
animate several sequences, including an animation of Frosty the
snowman, and a robot inserting bolts into an assembly. The latter
sequence, which resulted in a 45 second video tape, took a week to
design and four weeks to render and film. The scripting system
has worked well and been relatively easy to learn.
-------------------
Design and Implementation of a Programmable Function Key Box
Gregory J. McPhee
Rensselaer Polytechnic Institute
(TR-84011)
Level: M.Eng. Thesis
Date: May 1984
Advisors: D. Faatz, M. Levinn, M. Wozny
Many present day graphics workstations for CAD/CAM use external
function key boxes (FKB's) to expand upon the capabilities of the
standard keyboard. The FKB's are designed such that they cannot
easily be attached to any other host device. This report
describes an alternate design and implementation of an intelligent
FKB using a standard RS-232-C serial interface making it easier to
communicate with and attach to different host devices. This
design was motivated by the needs of the RPI uCADAM project, an
IBM Personal Computer based CADAM training workstation. The
design incorporates a microprocessor based circuit which allows
the FKB to interpret a small set of commands and understand a
particular communications protocol.
Although the microprocessor based FKB design is somewhat more
complex than the commercial FKB's, this alternative approach
yields a higher performance vs. cost ratio. Not only is this FKB
a more flexible device because of the standard interface, but also
the program running within the FKB detects and responds to FKB
hardware and protocol errors.
----------------
Interactive Computer-Aided Design and Analysis of Large Space Structures
Andrew F. Miller
Rensselaer Polytechnic Institute
(TR-84002)
Level: M.S. Thesis
Date: February 1984
Advisors: M. Ackroyd, M. Shephard
Continuum modeling of large space structures is a new approach to
structural analysis. Although several continuum modeling
techniques have been developed, the Load Correction Method (LCM)
presented by Taft H. Broome at Howard University, lends itself
quite readily to computer implementation. The goal of the work
presented in this paper has been to create a structural
preprocessor to prepare the appropriate data for an analysis using
the Load Correction Method. Since the immediate use of this
program is to aid in the development and testing of potential LCM
analysis formulations, the preprocessor is designed to create an
extensive data base which can be linked to many different analysis
programs.
--------------------
On GDM's: Geometrically Deformed Models for the Extraction of
Closed Shapes from Volume Data
James V. Miller
Rensselaer Polytechnic Institute
(TR-90051)
Level: M.S. Thesis
Date: December 1990
Advisors: D. Breen, R. O'Bara, M. Wozny
The advent of nondestructive sensing equipment (CT, MRI) has created an
entirely new field of research for image engineers. The equipment
generates a point sampling of a true three-dimensional object.
Typically, this point sampling is presented as a series of slices
through the 3D object. It has become apparent, however, that displaying
individual slices does not lend itself to conveying the true
three-dimensional structure of the scanned object. Research, therefore,
has focused on alternative methods of presenting volume data.
This thesis proposes an approach that will generate a topologically
closed simple geometric model of an object with a scalar field.
A Geometrically Deformed Model, GDM, is created by placing and initial
simple model in the data set which is then deformed by minimizing a set
of constraints. The constraint functions evaluated at each vertex in
the model control the local deformation, the interaction between the
model and the data set, and maintain the shape and topology of the
model. Once generated, a GDM can be used for visualization, shape
recognition, geometric measurements or subjected to a series of
geometric operations.
---------------
Scan-Conversion and Shading of Arbitrary Polygons
Mark D. Miller
Rensselaer Polytechnic Institute
(TR-84012)
Level: M.S. Project
Date: May 1984
Advisors: M. Wozny, D. Spooner
An increasingly important tool in Computer Aided Design is a
facility which allows the user to examine a realistic rendition of
the object being designed. This renderer must be reasonably fast
so that the designer does not waste time while waiting for his
image, but it must also produce images which are sufficiently
realistic. This report discusses the implementation of such a
renderer.
The renderer takes as its input the descriptions of planar
arbitrary polygons in 3-space. An arbitrary polygon has any
number of sides and can have holes or multiple components; all
vertices of the polygon must, however, be in a common plane.
Hidden surfaces are removed from the scene using a modified
scan-line hidden-surface removal algorithm, and edges are
anti-aliased. The anti-aliasing is performed by a fast,
mask-based algorithm which computes the edges to a higher
resolution than is displayed. The remaining surfaces are
smooth-shaded using Phong shading, and the final image is
run-length encoded and written in a file. This file can then be
down-loaded to a raster graphics display to view the results.
Optionally, an intermediate file is produced. This file contains
enough information to re-shade the scene using different colors
and light sources. The re-shading process requires a fraction of
the time needed to compute the original image.
The actual time required to render a model depends on the size of
the model. Small models, under 400 polygons, can be rendered in
under two minutes of CPU time on an IBM 4341 mod II and re-shaded
in about one minute. Larger models of about 10,000 polygons
require about six minutes of CPU time. Re-shading a large model
can take as little as two minutes.
The renderer is intended to be used with models generated on
CATIA; it is, however, more general-purpose than that. This
implementation can be used by anyone who can produce arbitrary
polygons which approximate the desired geometry. The origin of
these polygons is irrelevant; they can come from mathematically
modeled objects, as from CATIA, or from digitized points from real
objects.
-----------------
Use of a Specialized System Architecture to Implement PHIGS
Jorge F. Molina
Rensselaer Polytechnic Institute
(TR-87017)
Level: M.S. Thesis
Date: August 1987
Advisors: S. Abi-Ezzi, M. Wozny
This thesis illustrates how the harmonious cooperation between
multiprocessor hardware organized in a special architecture and
carefully designed software, constitute an ideal foundation for
implementing the Programmers Hierarchical Interactive Graphics
System (PHIGS). A detailed presentation of the software aspects
of the system is given.
The report details the tradeoffs evaluated when considering the
distribution of the tasks across the system and when selecting the
algorithms to be used. An analysis of the possible bottlenecks
and the strategies used to improve the performance of the system
is presented, identifying core operations and searching for their
optimal implementation. The discussion frequently addresses
issues between PHIGS implementation problems and the design
decisions taken to solve them. This interrelationship between
requirements and design was a key to the success of the project.
A complete description of the programming characteristics of the
Geometry Pipeline Processors (GPPs) used in the system is
presented. Timing constraints are identified and programming
examples are included. Finally, an analysis of the performance of
the system is made, in light of a realistic, medium-sized problem,
showing that the proposed system is capable of handling it in a
clean and efficient manner.
----------------------
Title: The Use of Grayscale for Improved Character Presentation
Avi C. Naiman
Center for Visual Science
University of Rochester
274 Meliora Hall
Rochester, NY 14627-0270
USA
(716) 275-0682
avi@cvs.rochester.edu
Level: Ph. D. Thesis
Date: March 1991
Advisor: Alain Fournier
Ordering Information:
Computer Systems Research Institute Technical Report CSRI-253
Cost: $16, payable to the University of Toronto
Attn: Technical Reports
Computer Systems Research Institute
University of Toronto
6 King's College Road
Toronto, Ontario M5S 1A1
Canada
(416) 978-8751
With the advent of inexpensive, CRT-based display systems, an
increasing amount of what we read is available on soft-copy monitors.
Until recently, most text on raster displays used mono-spaced
characters represented as binary matrices, the ones and zeros
corresponding to the black and white dots to be displayed. "Grayscale"
display technology allows the incorporation of gray pixels into font
representations, particularly along character boundaries. Under
appropriate conditions, the use of grayscale can improve character
image quality and/or increase a display's effective addressing
resolution.
We introduce "rectangular convolution", a fast filtering technique
specially adapted to grayscale character production. The masters are
decomposed into rectangles, and a summed-area representation of the
filter is convolved efficiently with each individual rectangle to
construct the grayscale characters. For a given filter, the number of
operations is linear in the size of the grayscale character, which is
optimal.
To investigate the image quality of screen fonts, a modeling system is
developed in which the generation, display, and perception stages are
clearly separated. This framework provides the basic platform needed
to develop and test metrics for judging the perceived quality of a
grayscale character generated with a particular filter, displayed on a
characterized device, and viewed under specified conditions.
To quantify the tradeoff between grayscale and spatial resolution for
edge localization, a sub-pixel edge alignment experiment is conducted,
determining the visual conditions under which it is possible to use
pixel luminance to position a perceived edge at sub-pixel precision, as
well as the relationship between luminance and perceived position under
those conditions. Our results suggest that, for the purposes of using
grayscale to position edges at sub-pixel resolution, spatial resolution
should be increased until pixels subtend no more than about 1.4 minutes
of visual angle; for a viewing distance of 18 inches, this corresponds
to 140 pixels per inch. Furthermore, even at this relatively small
visual angle, the relationship between luminance and perceived edge
position is still non-linear, and can be explained with a vision
model. Under these conditions, no more than about three bits of
grayscale can be used reliably to localize edge position.
-----------------
Polygon Clipping and Star Decomposition for Rendering Solid Models
Bruce N. Navsky
Rensselaer Polytechnic Institute
(TR-85007)
Level: M.S. Thesis
Date: May 1985
Advisors: M. Ackroyd, M. Wozny
Computer Aided Geometric Design systems have the capability to
answer a growing need for creating large solid models. The
quantity of information contained in such models is enough
information to make them difficult to comprehend without the help
of color shaded images. However, known software algorithms for
producing color shaded images of 3D models have inherent
difficulty with large models. Some algorithms may require that
entire model be in storage. Others may have a time complexity
which has a higher than linear order dependence on model size.
Some algorithms require input to be of restricted geometric type,
and lack the robustness to handle the multitude of geometric
special cases which may be created with a CAGD system.
To enable very large models to be displayed in reasonable time,
special display hardware has been developed which can off-load
some of the rendering tasks from the host computer. These display
devices use a depth buffer hidden surface method to remove hidden
surfaces. Storage requirements with this method depends on image
resolution only, not model size. Also, the rendering time with
this special hardware has a linear dependence on model size.
However, these devices may require data of a specific geometric
type, which may or may not be directly available from the CAGD system.
This thesis describes rendering algorithms for interfacing a CAGD
system to a display device capable of performing color shading and
hidden surface elimination in hardware. The CAGD system contains
solid models which have boundary representations in the form of
planar polygonal faces which may consist of one or more connected
areas with holes. The display device requires that input be
clipped to integer display-space limits, and be of a special
polygonal format called star polygons (also known as a polygon
visible from a vertex).
This interfacing process involves two key algorithms. The first
algorithm, a view-space clipper, clips faces from the CAGD system
to the limits of the display space. The second algorithm converts
the clipped faces to one or more non-overlapping star polygons
which cover the face.
This rendering system, and its associated hardware and software
allows the designer to view solid models of greater complexity
with increased comprehension and faster interactive response time.
-------------------
Interactive Computer-Aided Design of 3-D Steel Structures
Bruce C. Nelson
Rensselaer Polytechnic Institute
(TR-85018)
Level: M.S. Thesis
Date: May 1985
Advisors: M. Ackroyd, M. Shephard
The design of constructed facilities is a data intensive process
which lends itself readily to the utilization of computers. The
use of interactive computer graphics allows the designer to be
creative as well as efficient in his design approach since he is
not bound to any specific design or analysis format.
Several separate design and analysis programs have already been
developed. An integrated program that links a design layout and
member properties preprocessor to the existing analysis programs
and completes the design process with a postprocessor that allows
for an iterative optimum design is the goal of the research
concluded in this thesis.
------------------
An Analysis of Modeling Clip
Robert M. O'Bara
Rensselaer Polytechnic Institute
(TR-88011)
Level: M.Eng. Project
Date: May 1988
Advisors: S. Abi-Ezzi, M. Wozny
Modeling clip is a functionality supported by the Programmer's
Hierarchical Interactive Graphics System (PHIGS), and gives an
application the ability of removing sections of an object in order
to view internal detail. The clipping volume defined by modeling
clip can be concave and disjoint, and is composed of a set of
volumes that are specified in modeling coordinates. No known
previous work has been done on modeling clip concerning its
applications, implementation, or impact on the rest of the PHIGS
conceptual model.
Some interesting peculiarities arise from the fact that the PHIGS
pipeline is algebraically based and that modeling clip regions are
specified in modeling coordinates. One such peculiarity occurs
when the transformation relating the coordinate system of the clip
region to world coordinates is singular. An in-depth study on the
algorithmic and architectural issues of implementing modeling clip
is presented, along with a few applications of the new functionality.
The resulting algorithm to implement the modeling clip mechanism
represents the clip volume as a pipeline of filters with each
filter representing one of the sub-volumes. The method handles
all of the sixteen possible set combinations between two regions
in space. The effects of transformations on modeling clip have
been examined, and has resulted in identifying when modeling clip
can be efficiently performed in device coordinates as well as the
cases when it can not. When handling singular modeling
transformations, it is shown that it is necessary to deviate from
the PHIGS conceptual model.
--------------------------
An Interactive Tool to Illustrate the Basic Principles of Bezier and
B-Spline Curves and Surfaces
Natasha Oza
Rensselaer Polytechnic Institute
(TR-90037)
Level: M.S. Thesis
Date: August 1990
Advisor: M. Wozny
Parametric curves and surfaces play an important role in Computer Aided
Geometric Design. Of these, a particular subset known as Bezier and
B-Spline curves and surfaces form the basis for most currently available
commercial CAD systems.
The importance of Bezier curves in particular lies in their fundamental
representation of piecewise polynomial curves. Understanding the theory
of these curves is essential for a grasp of many CAGD phenomena. It may
also be used to derive the theory of B-spline and rational curves.
The purpose of this work is to develop a computer-based tool that would
allow students to understand parametric curves and surfaces by
displaying and manipulating new or previously calculated data. This
tool illustrates many of the mathematical properties of Bezier and
B-Spline curves and surfaces by exploiting the visual and interactive
capabilities of present day graphics systems. The emphasis is on
interactivity rather than precise numerical evaluation of complex curves
and surfaces. A framework is developed that allows extensibility to new
curve and surface design methods.
---------------------
Hardware Design for the TONIC Graphics Command Coprocessor
Jason J. Perreault
Rensselaer Polytechnic Institute
(TR-84022)
Level: M.S. Thesis
Date: December 1984
Advisor: M. Wozny
Hardware for the TONIC Graphics Command Coprocessor has been
designed and built to support the development of a
microcomputer-based graphics workstation which will serve as a
test vehicle for an implementation of device-independent computer
graphics software concepts. The motivations for this
graphics-processing companion to the IBM Personal Computer are to
reduce the complexity of PC-level software and to improve the
response of the system. TONIC's primary responsibilities are to
provide additional graphical processing, storage, and input
support for the workstation; to offload from the PC repetitive or
routine tasks, such as crosshair management; and to serve as a
communication intermediary between the PC and the GIN Graphics
Display Controller. TONIC composes appropriate low-level
control/data parameter sequences for GIN based on high-level
graphical information received from the PC.
Raw performance characteristics indicate that TONIC can improve
system performance in two ways. First, it allows a degree of
processing overlap between application execution and display
update. Second, its hardware floating-point capability provides
an order of magnitude improvement over software implementation of
this capability.
-------------------
An Algorithm for Disc Cutter Path Generation
Ogen Perry
Rensselaer Polytechnic Institute
(TR-83015)
Level: M.Eng. Project
Date: December 1983
Advisors: H. McLaughlin, A. Bunshaft, M. Wozny
This project involves the machining phase of a software package
which allows a designer to create a BANBURY rotor on a Gerber
Systems Technology IDS-80 CAD/CAM system and then to use the same
system to generate a tool path for a custom made tilted disc
cutter. This paper describes the algorithm used for the
generation of the tool path for the NC machinery.
A method has been developed which uses the coordinates and surface
normals of the rotor at sampled points on the rotor surface in
order to generate an accurate tool path, and a computer program
has been written. The output of the program is submitted to a
post-processor in the form of blocks of data consisting of GSTCL
commands. In addition to this hard output, the user is allowed to
check the progress of the program and its accuracy using a
two-dimensional graphic representation of the cutting process.
The unique geometry of both the BANBURY rotor and the cutter being
used introduce complex problems into the tool path generation process.
----------------
SMBLD: An Interactive Raster Graphics Display Builder
Steven H. Philipson
Rensselaer Polytechnic Institute
(TR-82016)
Level: M.S. Project
Date: August 1982
Advisors: M. Wozny, E. Rogers
A working display building program named SMBLD has been produced
that includes the following characteristics: 1) Program control
is based on a user-friendly, hierarchically oriented, menu driven
system of interaction. 2) A data structure and related software
has been implemented to facilitate graphical manipulation,
specifically entity selection (picks) and "gravity" operations
(connections). 3) Graphics techniques have been developed
pertaining to the use of vector oriented color raster display
devices. An extensive design has been outlined, and several major
sections of it have been implemented. The basic system has been
exercised through the creation of several displays and has
demonstrated the efficacy of the interactive techniques, data
structure design, and graphical manipulation methods. These three
segments of the project have been closely intertwined in the
production of the working program.
---------------
PHASE: A Computer Program for Generating Three Dimensional Phase
Space Diagrams of Ordinary Differential Equations
Mark B. Phillips
Rensselaer Polytechnic Institute
(TR-83030)
Level: M.S. Project
Date: February 1984
Advisor: G. Odell
PHASE is a program, written in reasonably standard FORTRAN, for
interactively creating three dimensional phase space diagrams
showing trajectories of autonomous Ordinary Differential Equations
(ODEs). In general, the ODE being investigated can be written in
the form: (x',y',z') = F(x,y,z), where ' denotes the derivative
with respect to time, and F is a vector valued function. the user
specifies a particular ODE by writing FORTRAN subroutines for
evaluating the function F and its Jacobian matrix, and linking
these routines with the package. Once this has been done and
execution of the program begins, several options are available for
generating a diagram showing the behavior of solutions to the ODE.
These include interactive positioning of a 3D cursor to indicate
initial points of trajectories, numerical integration and plotting
of these trajectories, analysis routines for determining critical
points of the system and eigenvalues and eigenvectors at these
points, and the drawing of 'flow' arrows at regularly spaced
intervals throughout a region of space to show the direction field
of the ODE. In addition to these analysis functions, PHASE
provides an 'edit picture' option, in which explanatory text
labels, arrows, and lines can be added to the diagram.
PHASE also incorporates an algorithm for using ODEs to compute
surface intersections. If two surfaces are given by the equations
f(x,y,z)=0, g(x,y,z)=0, and if these surfaces intersect in a
smooth one-dimensional manifold, then it is possible to construct
an ODE which has this intersection as its stable invariant
manifold. This ODE can then be used to plot the intersection by
following a trajectory, actually plotting only after the
trajectory falls within some very small tolerance of f=g=0. PHASE
includes facilities for doing much of this work automatically,
such as only drawing a trajectory after it has come close to the
intersection, and detecting when a trajectory has made a closed
loop. The user specifies the two surface functions f and g by
writing FORTRAN subroutines to evaluate them and their gradients,
and linking them with this package, just as with the ODE function
F above. Once this has been done, the process of plotting their
intersection is essentially the same as generating a phase
portrait, since in both cases what is actually being computed and
drawn is the solution to an ODE. For this reason, these two tasks
are (almost) equivalent from the user's point of view.
Thus there are two 'types' of ODEs which PHASE can analyze. Both
are three dimensional systems of first order autonomous ODEs, but
they differ in the way in which they are computed. The first type
is computed from a direct specification (in the form of a user
written subroutine) of the function F(x,y,z) given above. The
second type is computed by using the two 'inside-outside'
functions f(x,y,z) and g(x,y,z) mentioned above (also in the form
of user written subroutines) to construct an ODE which tracks the
intersection curve f=g=0. The result of this construction is
another function of the type F(x,y,z) which actually defines the
ODE, but the user never sees this function, and need not worry
about the details of its construction. The user specifies which
type of ODE she/he wants to work with by setting a switch in the
program.
-------------------
Color Display Support for the Geometric Design Processor
Philip Puccio
Rensselaer Polytechnic Institute
(TR-81020)
Level: M.S. Project
Date: August 1981
Advisor: M. Wozny
The "Color Display Support for the Geometric Design Processor"
project was undertaken to provide the users of the Geometric
Design Processor (GDP) with a means of composing color images
based upon the contents of the world model database.
The final color support system gives the user much flexibility in
the composition of such images. The user can define anywhere from
one to sixteen hues to be assigned to faces or entire objects in
the world model. Moreover, all assignments and defined hues can
be stored with the world model and later retrieved for display in
color.
Throughout the design of the software, device dependencies were
kept to a minimum. At the same time, device-dependent software
was designed to ease the conversion from one display system to
another.
A user's manual is provided for those who will be using the Color
Display Support software at their GDP installation. Also included
is a technical report which includes detailed descriptions of all
software used in this project. The user's manual can stand alone
as a design aid for users of an installation with Color Display
Support. The technical report, however, will be of greater value
when the reader has already become familiar with the system
through actual experience with the software and knowledge of all
options described in the user's manual.
-------------
Interactive Computer-Aided Design of Control Systems in Parameter Space
Peter Putz
Rensselaer Polytechnic Institute
(TR-85002)
Level: Ph.D. Thesis
Date: April 1985
Advisor: M. Wozny
A novel integration of interactive computer graphics into
computer-aided control system design is developed by applying the
parameter space design approach to continuous-time or sampled-data
linear multivariable systems.
Primary design requirements are formulated as closed-loop
eigenvalue regions and mapped into the state feedback gain design
parameter space. Interactive computer graphics allows viewing the
complete solution space in an intuitive geometric fashion and
resolving additional criteria like robustness, integrity to sensor
failures, or actuator constraints by direct geometric
interpretations.
A methodology for mathematical modeling of n-dimensional
admissible parameter space regions for single-input systems is
developed first. An algebraic approach combines conformal mapping
of the permissible pole regions and Routh-Hurwitz stability
criteria to establish an implicit inequality description by an
automated procedure. An alternative recursive parametric boundary
representation is established which is superior for fully
automated graphical display of 2D or 3D slices.
Conceptual strategies are devised to systematically access
n-dimensional parameter spaces by judicious selection of sequences
of such slices. An automated heuristic search procedure finds
subspaces of a prescribed structure with maximum admissible
hypervolume to yield optimal subsequent design latitude. A
sequential decomposition technique computes slices for full
parameter space design of sub-systems such that the remaining
eigenvalues are invariant.
Several methods are given for designing multi-input systems by
suitable application of the above techniques. The modeling of 2D
and 3D slices and unity rank feedback allow direct reductions to
equivalent single-input problems, while systematic sequential
design of full-rank feedback is achieved as a sum of dyadic stages
incorporating the invariant subspace strategy.
Dynamic output feedback can be reformulated and designed in the
parameter space framework, too. As a special case, the complete
solution space for SISO PID compensator design is readily
available in graphical form.
Practical realization of these concepts in a comprehensive
software package with immediate analysis and simulation
capabilities offers unprecedented flexibility to study complex
design tradeoffs by real-time graphical interaction with 3D
admissible regions on vector or color raster devices. Case
studies of real-world design applications prove the potential of
this methodology as a unique and powerful analysis and design
environment.
---------------
A Ray Tracing Renderer for a Geometric Solid Modeler
Linda A. Roy
Rensselaer Polytechnic Institute
(TR-86053)
Level: M.Eng. Project
Date: September 1986
Advisors: M. Wozny
Industrial designers working with CAD tools have need for high
quality computer graphics renderings to interpret the visual and
aesthetic qualities of their models. This thesis extends a
specific solid modeling package, GDP, to include a computer
generated image synthesis capability using a ray tracing
technique. The focus of the work has been the quality of the
images produced by the ray tracer. No major attempts were made to
reduce computation time.
A ray tracing algorithm has been developed and successfully
implemented in an industrial design facility. It produces
realistic images of the models. The ray tracer renders the GDP
primitives as precisely as possible, including performing Boolean
operations which allow the user to union, difference or intersect
objects. The user can control the lighting of the model to
achieve better definition of the objects. The ray tracer provides
antialiasing through a supersampling technique. Preliminary
feedback indicates good acceptance of the computer generated
images.
-----------------------
Resource Sharing for a Dual Work-Station Graphics System
Paolo Sabella
Rensselaer Polytechnic Institute
(TR-81004)
Level: M.S. Thesis
Date: May 1981
Advisor: M. Wozny
Graphics processors often possess local intelligence to unload
from the host the task of display list building. In particular,
the IMLAC 6220 refresh vector processor is capable of dynamically
building display lists, independently for two users.
Unfortunately, there are more than one program supplied by IMLAC
for the 6220. Each of these interpret commands from the host in a
different format and only one of them, DYNAGRAPHICS, supports more
than one user. Therefore, in an installation where a user is
likely to use any of several host formats, added flexibility is
needed whereby the 6220 can execute every program for two users as
well as allow each user to execute a different program.
In this study a non-disk operating system, ANDOS, was written for
the 6220 to provide this capability. It provides the facilities
of resource management, time-sharing, sharing of code and a
dynamic memory management scheme.
Furthermore, the IMLAC supplied programs DYNAGRAPHICS and DINO
have been re-written to run under ANDOS. This will provide users
on a dual-user 6220 with the option of configuring their 6220 to
be either a DYNAGRAPHICS terminal or a DINO terminal or both.
---------------
A User Interface for Interactive Computer Animation Scripting
Brion D. Sarachan
Rensselaer Polytechnic Institute
(TR-86050)
Level: M.Eng. Project
Date: December 1986
Advisors: D. Breen, P. Getto, M. Wozny
An interactive user interface is developed for creating computer
animation scripts. Scripting a computer animation is difficult
using traditional programming techniques. The system developed
provides the user with an interactive environment for scripting
the synchronization between actions in a script and for scripting
the parameter transformations which create the actions themselves.
The overall goal has been to identify the necessary features of an
interactive computer scripting system that allow an animator to
deal only with those choices that relate to the animation which he
or she is creating. Tedious and mechanical tasks have been
identified and automated.
A timeline-editing facility is implemented for scripting the
synchronization between actions. Automatic action-writing and
curve-editing tools are designed to allow the user to
interactively script the component actions of an animation in a
process much like geometric modeling.
The Clockworks animation system is used as the foundation for this
project. Once the requirements for the interactive scripting
system were identified, additions were made to The Clockworks
system which transcend from the Clockworks parser at the lowest
level, up to the high-level interactive user interface.
-----------------------
An Architecture for Floating-Point Intensive Geometric Algorithms
Stephen A. Schlapp
Rensselaer Polytechnic Institute
(TR-90036)
Level: M.Eng. Thesis
Date: August 1990
Advisors: S. Abi-Ezzi, R. O'Bara, M. Wozny
Interactive, three dimensional graphics systems require enormous amounts
of floating-point processing power. For example, point transformations,
requiring 16 multiplications and 12 additions each, must be performed
millions of times a second in current graphics systems. Currently, this
need cannot be satisfied by individual floating-point chips so some form
of parallel processing is needed. Current parallel processing schemes
for performing geometric operations have inherent inefficiencies.
A new architecture is proposed that operates on the four elements of a
vector in parallel. Since it accelerates processing of the basic data
type used by geometric algorithms, it is capable of executing them
efficiently.
A simulation model of the architecture has been implemented with
microcoded programs executing on it. The performance of several key
geometric operations have been evaluated.
------------------------------
VIRA, A Visibility Resolving Algorithm for Constructive Solid Geometry
Using A-Buffer Techniques
Daniel G. Schmidt
Rensselaer Polytechnic Institute
(TR-86023)
Level: M.Eng. Project
Date: August 1986
Advisors: P. Getto, M. Wozny
This thesis discusses VIRA, a visibility resolving algorithm, with
the application of a scan-line AVID (anti-aliased visibility data)
buffer to synthesize images for Constructive Solid Geometry (CSG).
CSG graphs have been rendered in previous scan-line systems, but
the use of A-buffer concepts adds flexibility to this system.
VIRA, together with an interactive shading program, make up a
renderer capable of generating quality images of complex geometries.
VIRA may be considered an extension of the polygon-based scan-line
hidden-surface removal procedures used to resolve a Boolean set
operations on geometry graphs because it produces an AVID buffer
that is used for a variety of shading computations. Like the
A-buffer, the AVID buffer is stored as a frame-buffer-sized matrix
of element lists. Each list defines the visible surface for one
picture element (pixel). Unlike the A-buffer, however, the
elements do not contain shading intensities; they contain surface
information derived from a particular view. Thus, VIRA resolves
visibility among a set of opaque, transparent and intersecting
volumes in preparation for an interactive shading session.
A scan-line-oriented polyhedron clipping algorithm is presented.
This clipper is capable of clipping volume-enclosing polyhedra for
rendering solids, like those found in CSG systems. Also, a
polygonal approximation method (PAM) for approximating
superquadrics into polygonal models is discussed.
The implementation of this combination of algorithms was developed
in conjunction with an interactive shader at the RPI Center for
Interactive Computer Graphics as a means of producing realistic
images in the Center's object-oriented animation system called The
Clockworks.
-------------------------
SOLID: A Command Language for Solid Modeling Using Octree Encoding
Peter Segal
Rensselaer Polytechnic Institute
(TR-82005)
Level: M.S. Thesis
Date: May 1982
Advisor: M. Wozny
The purpose of this project is to design and implement a solid
modeling design language, SOLID (Solid modeling Language for
Interactive Design), with which one can either interactively, or
via a SOLID program executed in batch mode, design and utilize
solid models easily, conveniently and effectively. Applications
of SOLID include designing three-dimensional solid models,
performing N/C verification, and identifying three-dimensional
interference problems.
SOLID is designed to be easy to use, yet powerful. With SOLID,
the user can define objects from a class of solid primitives
called SUPERQUADRICS. He can also transform and combine objects,
save and load them to and from disk, and display them in
orthogonal or perspective projections.
The ability to execute blocks of SOLID commands (referred to as
Command Blocks, or "programs"), as well as save and load them to
and from disk is also provided. The user may define a
three-dimensional path along which a command block may be executed
at each step. This allows further flexibility in using SOLID as a
design tool, as objects may be formed by unioning or subtracting
objects along a path, to generate more complex objects. This
feature is especially useful for simulating manufacturing
operations, such as cutting, routing, and drilling.
-----------------
The Programmer's Hierarchical Interactive Graphics Standard in an
Object-Oriented Environment
Craig A. Shelly
Rensselaer Polytechnic Institute
(TR-87031)
Level: M.S. Project
Date: May 1987
Advisor: M. Wozny
There are outward structural similarities between the Programmer's
Hierarchical Interactive Graphics Standard (PHIGS) and certain
object oriented concepts. The organizational pattern of PHIGS is
a hierarchy of structures, where inheritance through the hierarchy
is used for attribute determination. It is certainly tempting to
suggest that since an object oriented system possesses the ideas
of hierarchy and inheritance, an object oriented implementation of
PHIGS would be natural and straight forward.
This project is a study of the questions of 'to what extent is
PHIGS well-suited for implementation under an object oriented
environment' and 'what could be done to either concept to
facilitate their union'. In the course of exploring the first
issue, an implementation of an unmodified subset of PHIGS was
built using the C Object Oriented Language Extension (COOLE), an
experimental software package. The second question is addressed
by a proposed PHIGS variant implementable in COOLE and some
discussion of what COOLE was lacking in regards to PHIGS.
The implementation runs on a VAXstation II, using the UIS graphics
support routines from a C Language based object oriented system.
-------------------------
Interactive 3-D Surface Design - BBSRF
Moh-Fung Shen
Rensselaer Polytechnic Institute
(TR-86009)
Level: M.S. Project
Date: May 1986
Advisors: D. Breen, D. Spooner
The purpose of this project is to implement software which creates
bicubic spline surfaces.
A bicubic spline surface can pass through a given set of
rectangular points while maintaining continuous first and second
derivatives. The surface consists of tensor-product patches, thus
it is easy to modify and extend.
Both the mathematics and the geometric meaning of the algorithm
for fitting bicubic spline surfaces are addressed. The
interactive method for constructing surfaces is demonstrated.
---------------------
A Color Raster Addition to the GDP System With Full Hidden Surface
Removal
Derek D. Snyder
Rensselaer Polytechnic Institute
(TR-81019)
Level: M.S. Project
Date: August 1981
Advisor: M. Wozny
GDP is a Geometric Design Processor program which is a
computer-based system for modeling three-dimensional solid objects
designed by the Automation Research Group at the IBM Watson
Research Center in Yorktown Heights. The system generates a data
base where objects and assemblies are represented by nodes in a
graph structure. Among the information stored in each node are
the positional relationships between objects and other physical
and geometrical properties about the objects. All objects are
represented internally as polyhedra and all rounded portions are
faceted. This paper discusses an extension to the GDP/GRIN
package which will take a previously constructed three-dimensional
scene and perform a conversion of the information into a form
displayable on a color raster graphics terminal with full hidden
surface removal. A scanline hidden surface algorithm which takes
advantage of scanline coherence is used to perform the
rasterization and hidden surface removal.
-------------
Non-Uniform Rational B-Spline Curves in the
Programmer's Hierarchical Interactive Graphics System
Brian M. Stevens
Rensselaer Polytechnic Institute
(TR-88034)
Level: M.S. Thesis
Date: September 1988
Advisors: S. Abi-Ezzi, M. Wozny
The Non-Uniform Rational B-spline (NURB) form supports both
quadratic and free-form curves and surfaces. This paper studies
NURB curves, examining ways to exploit their properties for
efficient processing in a PHIGS+ context.
We observe that we can transform the control points prior to
tessellation, saving the expensive transformation of every
approximating line segment. This allows us to tessellate in
device coordinates, which is really the only coordinate system
where approximation criteria makes sense. The projection of the
control points from 4D to 3D is not possible before tessellation,
thus, tessellation must be done in 4D.
Homogeneous coordinates provide a tool for achieving both
perspective transformations and rational splines in a unified
fashion. This observation combined with tessellating after the
transformation step, combines the rational divide and the
perspective divide into a single divide per point.
The basis polynomials for the NURB spans are independent of the
control points, and thus can be precomputed before the control
points are transformed. The blending of these polynomials into a
single polynomial is done once the control points are transformed,
allowing for the evaluation of a single polynomial when sampling.
Efficient algorithms for the handling of NURBs in a PHIGS+
environment depend on the approximation criterion being used.
Forward differencing proves to be the most efficient algorithm
when sampling at equal increments in parameter space. Recursive
subdivision is most efficient when we need to adapt based on the
shape of the curve.
A problem arising from the use of homogeneous coordinates is that
a line segment may penetrate the w = 0 plane. This situation may
arise when using certain values of w with the original control
points or by using certain classes of transformations. This
causes a problem when the line segment is to be projected to 3D.
A solution to this problem is to clip out a region close to the w
= 0 plane, via an operation called w-clip, before projecting to
3D.
-------------
Design and Implementation of a Virtual Device Interface
Paul R. Stutsrim
Rensselaer Polytechnic Institute
(TR-84014)
Level: M.Eng. Project
Date: July 1984
Advisors: D. Faatz, M. Wozny
This project involved the design, implementation and test of a
core portion of a Virtual Device Interface based on the ANSI
Graphics Kernel System (GKS) draft standard and the ANSI Virtual
Device Interface (VDI) draft standard. GKS consists of a set of
graphics subroutines which define a device independent graphics
language. The VDI facilitates device independence by specifying
the functionality of the standard interface between the physical
device and a graphics language like GKS. The VDI compensates for
differences in physical hardware by using software routines to
implement the standard interface.
The purpose of the project was to explore the methodology of VDI
design and to provide the VDI foundation for a PC based GKS
workstation. The VDI was implemented on an IBM Personal Computer
XT/Vectrix VX384 intelligent graphics display system using IBM
Pascal for coding. Results indicate that a VDI for the PC
environment is feasible but may require tradeoffs between
functionality and limited memory size. This VDI design will be
implemented in ROM on the GIN & TONIC Graphics Display Subsystem
currently under development for the PC GKS workstation project at
the Center for Interactive Computer Graphics.
---------------------
Parallel Processor Architectures for Image Processing
David C. Tannenbaum
Rensselaer Polytechnic Institute
(TR-87046)
Level: M.Eng. Thesis
Date: August 1987
Advisor: M. Wozny
A hardware system with a parallel architecture was designed and
built to speed the computation of complex, numerically intensive
mathematical operations. Specifically, it was designed for
graphic image applications, to explore experimentally different
parallel architectures for performing the convolution operation
for use as a digital image filter.
A digital filter utilizing a discrete convolution was written.
The specific filter operations performed include: 1) High-pass
filtering, 2) Low-pass filtering, 3) Band-pass filtering
(primarily for noise removal), 4) High-boost filtering (gives a
degree of edge enhancement), 5) Edge detection (only the outlines
of features remain), and 6) Directional feature filtering
(A set of figures showing the experimental results are included in
the appendixes.)
Convolution was chosen because the algorithm to perform
convolutions lends itself readily to parallel implementation.
Also, the single operation of convolution can be used to perform a
number of useful image operations just by changing the parameters
in the algorithm. Thus convolution is at the same time a valuable
image processing operation and a good operation for testing the
merits of different parallel architectures.
Other operations investigated were dithering, so the images could
be rendered on devices with small spectral resolution, and
bi-linear interpolation for scaling images to different sizes.
Mapping was examined but was not implemented on the parallel array
because it was not fully compatible with the current architecture.
Prior to running on the parallel array, each of the different
algorithms was first run on a mainframe to determine what its
results would be. This was performed strictly as an intermediate
step. The results generated on the mainframe were later compared
with those from the parallel array. Any discrepancies were used
as an indication of an error. Running on the mainframe prior to
on the parallel array also provided an easy means by which to
evaluate the relative merits of the different algorithms because,
on the mainframe, a high-level language could be used, thus making
it easy to change the code.
It was shown that by using a sufficiently parallel architecture,
complex operations can be performed at or near to real-time.
Moreover, with the same hardware, both wireframe graphics and
image processing can be performed, potentially leading to large
savings in hardware costs.
------------------------
Design of a Specialized Hardware System for PHIGS
Michael A. Toelle
Rensselaer Polytechnic Institute
(TR-87016)
Level: M.Eng. Thesis
Date: May 1987
Advisors: S. Abi-Ezzi, M. Wozny
PHIGS specifies a conceptual model for a high level device
independent graphics system designed to support highly interactive
manipulation of hierarchically related graphical objects.
Supporting PHIGS at interactive speeds requires very high
performance software execution and/or specialized graphics
hardware. This thesis deals with the design, implementation, and
evaluation of such a system.
The system hardware designed is an extensible, homogeneous
pipelined architecture, which accommodates the current PHIGS
geometry pipeline and allows for future experimentation and the
support of PHIGS extensions. The system hardware is based on high
performance floating point processors, with specialized microcode
providing support for homogeneous coordinate transformation and
clipping, local handling of the PHIGS hierarchical data grouping
mechanism, and floating point intensive PHIGS utility functions.
The implementation of the system has been evaluated, showing that
the system is capable of interactively manipulating a reasonably
complex three dimensional wire frame model. The current system
limitation is in the rendering phase, and is the result of
component limitations in this particular implementation, rather
than any design problems.
------------------------
A Window Based Object-Oriented User Interface for THE CLOCKWORKS
David Tonnesen
Rensselaer Polytechnic Institute
(TR-89024)
Level: M.S. Thesis
Date: May 1989
Advisors: D. Breen, P. Getto, M. Wozny
This paper discusses the design and implementation of a
window-based user interface for an object-oriented application
program called The Clockworks. Objects send messages to a "window
interface" object describing the user-computer interactions for
that object. In return, the window interface object sends
messages back to the objects notifying them of user interaction.
Each object in the system is associated with a window on the
screen. The object's attributes are displayed on the window.
Standard window techniques (such as clicking buttons, editing text
strings, dialog boxes, and pulldown menus) are mapped to messages.
Input from a user will cause the corresponding message to be
generated and sent to the appropriate object.
The window interface object is defined independently of the other
objects in The Clockworks. This independence allows the
application to grow and to be modified without the need to update
the user interface. The implementation uses the X Window System.
However, since the window system dependencies are encapsulated in
a single object, it would be easy to modify the user interface to
use another window system. The concepts and the design of this
user interface can be directly applied to other object-oriented
applications.
-----------------
Shape Preserving Spline Based on Conic Sections
Hansel H. Wan
Rensselaer Polytechnic Institute
(TR-83005)
Level: M.S. Thesis
Date: May 1983
Advisors: H. McLaughlin, M. Wozny
In using the computer for design, there is frequently a need to
construct shape preserving curves. This paper presents an
algorithm which can be used to draw curves by using conic sections
which interpolate fixed planar data points, or knots. The notion
of regularity introduced by McLaughlin is used to preserve the
shape of the data. The algorithm is strictly local and it does
not require the solution of systems of equations. The resulting
curves will have slope continuity, except where there are cusp
points in the data.
---------
Topological Structures for Geometric Modeling
Kevin J. Weiler
Rensselaer Polytechnic Institute
(TR-86032)
Level: Ph.D. Thesis
Date: August 1986
Advisor: M. Wozny
Geometric modeling technology for representing three-dimensional
objects has progressed from early wireframe representations,
through surface representations, to the most recent
representation, solid modeling. Each of these forms has many
possible representations.
The boundary representation technique, where the surfaces, edges,
and vertices of objects are represented explicitly, has found
particularly wide application. Many of the more sophisticated
versions of boundary representations explicitly store topological
information about the positional relationships among surfaces,
edges, and vertices.
This thesis places emphasis on the use of topological information
about the shape being modeled to provide a framework for geometric
modeling boundary representations and their implementations, while
placing little constraint on the actual geometric surface
representations used.
The major thrusts of the thesis fall into two areas of geometric
modeling.
First, a theoretical basis for two-manifold solid modeling
boundary topology representation is developed. The minimum
theoretical and minimum practical topological adjacency
information required for the unambiguous topological
representation of manifold solid objects is determined. This
provides a basis for checking the correctness of existing and
proposed representations. The correctness of the winged edge
structure is also explored, and several new representations which
have advantages over existing techniques are described and their
sufficiency verified.
Second, a non-two-manifold boundary geometric modeling topology
representation is developed which allows the unified and
simultaneous representation of wireframe, surface, and solid
modeling forms, while featuring a representable range beyond what
is achievable in any of the previous modeling forms. In addition
to exterior surface features, interior features can be modeled,
and non-manifold features can be represented directly. A new data
structure, the Radial Edge structure, which provides access to all
topological adjacencies in a non-manifold boundary representation,
is described and its completeness is verified. A general set of
non-manifold topology manipulation operators is also described
which is independent of a specific data structure and is useful
for insulating higher levels of geometric modeling functionality
from the specifics and complexities of underlying data structures.
The coordination of geometric and topological information in a
geometric modeling system is also discussed.
---------------
Interactive Design of Plate Girders
Rolf Wentorf
Rensselaer Polytechnic Institute
(TR-85012)
Level: M.Eng. Project
Date: May 1985
Advisors: M. Ackroyd, M. Shephard
Design of plate girders necessitates iterative calculation
procedures: the designer selects trial plate component
dimensions, properties and locations; checks the adequacy of the
proposed girder design based on strength and stiffness
requirements; and revises these components until a safe and
economical design is achieved. In this project, software has been
developed which utilizes a natural language processor to define a
proposed design for a plate girder along with the loads and
reactions acting on it, performs design adequacy checks according
to current building codes, and graphically displays the adequacy
and efficiency of the proposed design. Design revisions can be
made through interactive natural language and graphic procedures,
rather than the more customary iterative calculation methods. The
program would be useful for complex design problems and as an
education tool for the understanding of plate girder behavior.
--------------
Tessellation of Variable Order Polynomial Surface and Polyhedral
Geometries
Edward E. Wong
Rensselaer Polytechnic Institute
(TR-84005)
Level: M.Eng. Project
Date: March 1984
Advisor: M. Wozny
This project concerns the tessellation of variable order
polynomial surface and polyhedral geometries generated by the 3D
CAD system, CATIA. Before a surface can be color-shaded, it has
to be tessellated or approximated with planar polygons. The
resultant polygons are then scan converted or "filled in" with the
proper color and shading (determined by illuminating light sources).
The ensuing report describes how the geometries are extracted from
the CATIA database and subsequently tessellated. The
Lane-Carpenter algorithm is used to subdivide surface patches of
variable degree. However, the algorithm has been extended to
avoid the extraneous cracks which occur when adjacent patches are
subdivided to different extents. This extension consists of
generating a surface node network during the subdivision process
and extracting the polygons which comprise the nodes, after the
process has converged. The tessellation algorithm extends
directly to CATIA polyhedrons. Also presented is a proposed
method for handling CATIA FACEs.
-----------------
Efficient Methods for Volumetric Graphics
Roni Yagel
The Ohio State University
Department of Computer and Information Science
2036 Neil Av. Columbus, Ohio 43210-1277
Tel: (614) 292-0060, Fax: (614) 292-9021
yagel@cis.ohio-state.edu
Level: PhD
Date: August 1991
Advisor: Prof. Arie Kaufman
Department of Computer Science
The State University of New York at Stony Brook
Ordering Info: Contact University Microfilm International
Driven by the prospect of three dimensional rasters as a primary
vehicle for future 3D graphics and volumetric imaging, we aim at
devising software and hardware tools needed to make this foresight
a reality. The major contributions of this work are the design of
the Flipping Cube architecture, the development of the template-based
approach to volume viewing, and the combination of both into a
special-purpose system for real-time high-resolution volume visualization.
In the Flipping Cube Architecture, N^3 volume elements (voxels) are
distributed among N slice-oriented memory modules in a scheme that allows
real-time viewing from one third of the possible viewing directions.
The aggregate of voxels comprising a viewing ray is fetched in parallel,
one voxel from each memory module, and fed into a special purpose mechanism
for ray projection. In order to achieve real-time viewing from arbitrary
direction the system employs a shift mechanism that accomplishes real-time
re-orientation (flipping) of the data inside the modular memory by utilizing
either a special purpose Flip Buffer or a 3D shearing method.
These two flipping methods are compared in terms of performance, memory
requirement, and hardware realization. We analyze the expected performance
of our system and conclude that it has the potential to support, for the
first time, real-time high-resolution volume viewing from an arbitrary
direction.
We present a template-based volume viewing algorithm that exploits
ray-coherency in parallel viewing in order to expedite rendering.
The algorithm generates a single ray and uses it as a template for all
other rays, saving the need for repeated ray generation. We demonstrate
its superior performance and describe how it can be extended to support
screen supersampling, continuous rays, and adaptive traversal.
Our three-phased approach guarantees uniform space sampling with discrete
rays by carefully placing the ray origin and by employing discrete space
arithmetic for ray-volume intersection calculation.
Next, we show how the template-based parallel viewing algorithm finds
a surprisingly efficient realization as part of the Flipping Cube
Architecture while maintaining real-time throughput.
-----------------
A Histogram-Based System Utility for Evaluating CAD/CAM Software Performance
John C. Zawada
Rensselaer Polytechnic Institute
(TR-83016)
Level: M.Eng. Project
Date: December 1983
Advisor: M. Wozny
Computer costs have shifted from hardware (the actual computer,
terminals, printer, etc.) to software (operating systems, CAD/CAM
application programs, etc.) in the last few years. All
indications favor that this trend will continue. Computer
programming is a creative art in the respect that a given task or
application can be programmed a number of different ways. It is
generally desired that the application program perform as
efficiently as possible on a given system.
Software performance can be evaluated through dynamic or static
techniques. The most accepted dynamic technique for evaluating
software is the use of histogramming. Histogramming involves the
use of a supervisor that samples the "where abouts" of a monitored
program periodically. The problem, however, is that the
information gathered is not accurate because the sampling rates
cannot be set too high.
A new technique which assigns the monitored program the active
role in the monitoring process is discussed in this paper. This
new technique is called the "WATCH" algorithm. The monitored
program is modified to report to the supervisor whenever it enters
or exits a routine. The modified application program is linked
together with the supervisor to make up the "WATCH" system. Since
the reported events are occasionally produced at a rate faster
than the resolution of the system clock, an approximation is made
of how much time is spent in a given routine.
This technique has been implemented and compared with existing
histogram techniques. The results are encouraging. Output data
is displayed in real time instead of waiting hours as in the case
of using a histogrammer. However, transportability of WATCH is
difficult for operating systems that do not support multi-tasking.
Future work is proposed that would eliminate the approximation in
the WATCH algorithm and provide perhaps the most accurate
evaluator of software yet.
-----------------
Color Minimization for Computer Image Display Using Color Look-Up Tables
Alan N. Zucker
Rensselaer Polytechnic Institute
(TR-83004)
Level: M.Eng. Thesis
Date: May 1983
Advisor: M. Wozny
Color look-up tables reduce the number of bits necessary to
specify a given color on a raster graphics terminal. This
approach requires that a given color be chosen from a fixed size
palette of colors. Although the actual hues and intensities in
the palette are chosen, as desired, from an even larger selection,
the number of colors (hues and intensities) remain fixed.
It is desired that when an image which contains many colors is
displayed on a terminal having a color look-up table, it appears
as an acceptable replica of the image with no color limitations.
When a color anti-aliased image is generated, many colors are
present. If the generation technique is limited to the number of
colors available in a look-up table, the quality is generally
degraded. Special techniques are therefore employed to reduce the
number of colors after generating the image.
A number of algorithms are reviewed which accomplish this task.
They are compared, and one is chosen for implementation based on
ease of implementation and prior results. This method is
described in detail, implemented, and experimentally evaluated for
performance. It is found that the limited range of colors chosen
by this algorithm appears, to a human observer, to provide
acceptable quality images for engineering applications.