Dissertation Abstracts

Title: PIPELINE RENDERING: INTERACTION AND REALISM THROUGH
HARDWARE-BASED MULTI-PASS RENDERING (RAY TRACING,
RADIOSITY)
Author: DIEFENBACH, PAUL JOSEPH
School: UNIVERSITY OF PENNSYLVANIA (0175) Degree: PHD Date: 1996
pp: 152
Advisor: BADLER, NORMAN I.
Source: DAI-B 57/04, p. 2663, Oct 1996
Subject: COMPUTER SCIENCE (0984)

Abstract: While large investments are made in sophisticated graphics
hardware, most realistic rendering is still performed off-line using
ray trace or radiosity systems. A coordinated use of
hardware-provided bitplanes and rendering pipelines can, however,
approximate ray trace quality illumination effects in a
user-interactive environment, as well as provide the tools necessary
for a user to declutter such a complex scene. A variety of common ray
trace and radiosity illumination effects are presented using
multi-pass rendering in a pipeline architecture. We provide recursive
reflections through the use of secondary viewpoints, and present a
method for using a homogeneous 2-D projective image mapping to extend
this method for refractive transparent surfaces. This paper then
introduces the Dual Z-buffer, or DZ-buffer, an evolutionary hardware
extension which, along with current frame-buffer functions such as
stencil planes and accumulation buffers, provides the hardware
platform to render non-refractive transparent surfaces in a
back-to-front or front-to-back order. We extend the traditional use
of shadow volumes to provide reflected and refracted shadows as well
as specular light reclassification. The shadow and lighting effects
are then incorporated into our recursive viewpoint paradigm. Global
direct illumination is provided through a shadow blending technique.
Hardware surface illumination is fit to a physically-based BRDF to
provide a better local direct model, and the framework permits
incorporation of a radiosity solution for indirect illumination as
well. Additionally, we incorporate material properties including
translucency, light scattering, and non-uniform transmittance to
provide a general framework for creating realistic renderings. The
DZ-buffer also provides decluttering facilities such as transparency
and clipping. This permits selective scene viewing through arbitrary
view-dependent and non-planar clipping and transparency surfaces in
real-time. The combination of these techniques provide for
understandable, realistic scene rendering at typical rates 5-50 times
that of a comparable ray trace images. In addition, the
pixel-parallel nature of these methods leads to exploration of
further hardware rendering engine extensions which can exploit this
coherence.



Title: AUTOMATIC MESH GENERATION FOR RADIOSITY METHOD IN
REALISTIC IMAGE SYNTHESIS
Author: YI, XIN
School: STEVENS INSTITUTE OF TECHNOLOGY (0733) Degree: PHD
Date: 1996 pp: 131
Advisor: IMIELINSKA, CELINA
Source: DAI-B 57/06, p. 3860, Dec 1996
Subject: COMPUTER SCIENCE (0984)

Abstract: Radiosity method, based on thermal engineering theory, has
become the most effective technique used in global illumination of
diffuse environments in realistic image synthesis. This thesis
presents a new mesh refinement algorithm based on shadow edge
detection for the radiosity method. Refining mesh along shadow
boundaries can yield radiosity solutions that are more accurate both
visually and numerically. Instead of determining the shadow boundary
by pure geometric refinement of a mesh, this new algorithm resolves
shadow details by using a modified hierarchical meshing strategy and
edge detection image processing techniques. In the algorithm, shadow
boundaries on a surface are approximated by a link of shadow edges
that are detected on the mesh of elements of this surface. No
sophisticated shadow boundary representation method is needed to keep
mesh elements conformed. Another advantage of this approach comes
from a possibility of implementation in hardware parts of the
algorithm. Successful experimental work has been conducted using the
new method, and the results are encouraging.



Title: SCENE VERIFICATION USING AN IMAGING MODEL IN
THREE-DIMENSIONAL COMPUTER VISION (MACHINE VISION)
Author: HANAJI' K, MILAN
School: TECHNISCHE UNIVERSITEIT EINDHOVEN (THE NETHERLANDS) (0426)
Degree: PHD Date: 1995
Source: DAI-C 57/04, p. 1344, Winter 1996
Subject: COMPUTER SCIENCE (0984); ARTIFICIAL INTELLIGENCE (0800)
ISBN: 90-386-0110-7

Abstract: A technique for the verification of scene descriptions is
presented which employs an imaging model, i.e. a model describing the
scene illumination and the image formation processes. It is assumed
that the scene description to be verified has been created by a
computer vision system. This verification problem involves the
estimation of unknown scene parameters, and a decision-making problem
based on the original acquired image and the synthetic image created
with the imaging model.
The image of a scene projected onto an image plane is the result
of an interaction of light with objects in the scene and a camera
image plane. Discussed are surface reflectance models, a camera
model, and three techniques for the computation of the global
illumination, ray tracing, radiosity and stochastic ray tracing. An
imaging model consisting of stochastic ray-tracing and the
Torrance-Sparrow surface reflectance model is considered.
When using the imaging model, knowledge of surface reflectance
parameters and parameters of the light sources is essential. A
maximum-likelihood technique for the estimation of the unknown
parameters is proposed and elaborated on.
For the verification of a scene description, a decision procedure
consisting of the difference between the camera image and the
synthetic image (an image created using the imaging model), the
linear filtering of the result of the difference by a North filter,
and the subsequent thresholding of the filtered image is proposed.
For the special case of a simple hypothesis and a simple alternative
this procedure is a most powerful test in the Neyman-Pearson sense.
The verification of the scene description is a decision problem with
a simple hypothesis and a composite alternative. A method for the
determination of suitable filter coefficients in the decision
procedure is given.
Finally, some methods for the improvement of the scene
description are discussed. The application of the technique is
demonstrated in a number of experiments reported throughout the
thesis, showing the feasibility of the proposed verification method.



Title: WAVELET METHODS FOR COMPUTER GRAPHICS
Author: GORTLER, STEVEN J.
School: PRINCETON UNIVERSITY (0181) Degree: PHD Date: 1995
pp: 195
Source: DAI-B 56/02, p. 918, Aug 1995
Subject: COMPUTER SCIENCE (0984)

Abstract: This thesis discusses how a wavelet basis can be used in
the context of two computer graphics applications, realistic
rendering and geometric modeling, to produce more efficient and
flexible algorithms.
The goal of realistic rendering is to simulate the
interreflection of light in some geometric environment to produce
realistic images. Radiosity is a commonly used solution method for
this problem. Recently Hanrahan et al. have introduced a hierarchical
method that can solve radiosity problems in $O(n)$ time instead of
$O(n/sp2)$. This thesis explores how the hierarchical radiosity
algorithm can be formally understood from the context of wavelet
theory. When the radiosity problem is expressed with respect to a
wavelet basis, the resulting linear system is sparse, with only
$O(n)$ significant terms. By casting the hierarchical method in this
framework, a variety of wavelet basis functions can be used,
resulting in more efficient radiosity methods.
This thesis also discusses how wavelets can be used in the
context of geometric modeling. Geometric modeling is the study of how
geometric shapes can be represented and manipulated by a designer.
This thesis explores the use of wavelets to represent parametric
curves and surfaces within the context of geometric modeling
interfaces.
One intuitive modeling interface commonly used in geometric
modeling allows the user to directly manipulate curves and surfaces.
This manipulation defines some set of constraints that the curve or
surface must satisfy (such as interpolation and tangent constraints).
Direct manipulation, however, usually leads to an underconstrained
problem since there are, in general, many possible surfaces meeting
some set of constraints. Therefore an optimization problem must be
solved.
This thesis discusses how geometric modeling optimization
problems can be solved more efficiently by using a wavelet basis.
Because the wavelet basis is hierarchical, iterative optimization
methods converge rapidly. And because the wavelet coefficients
indicate the degree of detail in the solution, they can be used to
determine the number of basis functions needed to express the
variational minimum, thus avoiding unnecessary computation. An
implementation is discussed and experimental results are reported.



Title: THE USE OF INVERSE RENDERING IN LIGHTING DESIGN
Author: KAWAI, JOHN KOJI
School: THE UNIVERSITY OF UTAH (0240) Degree: PHD Date: 1995
pp: 100
Source: DAI-B 56/05, p. 2722, Nov 1995
Subject: COMPUTER SCIENCE (0984); ARCHITECTURE (0729)

Abstract: Traditionally in a rendering environment an image is
generated given the surface attributes, lighting parameters, and
geometry of the environment. In an inverse rendering system the user
characterizes the final image in order to determine the surface
attributes, lighting parameters, and/or geometry. This dissertation
presents an inverse rendering approach for designing the illumination
in an environment using optimization techniques applied to a
radiosity based image synthesis system. An optimization of lighting
parameters is performed based on user specified constraints and
objectives for the illumination of the environment. The
Radioptimization system solves for the 'best' possible settings for
element reflectivities, and spotlight directionality, emissitivity,
and beam width so that the design goals, such as to minimize energy
or to give the room an impression of privacy, are met. The system
absorbs much of the burden for searching the design space allowing
the user to focus on the goals of the illumination design rather than
the intricate details of a complete lighting specification.
The system employs an object space perceptual model based on work
by Tumblin and Rushmeier to account for psychophysical effects such
as subjective brightness and the visual adaptation level of a viewer.
This provides a higher fidelity when comparing the illumination in a
computer simulated environment against what would be viewed in the
'real' world. Optimization criteria are based on subjective
impressions of illumination with qualities such as pleasantness and
privateness. The qualities were selected based on Flynn's work in
illuminating engineering. These criteria were applied to the
radiosity context through an experiment conducted with subjects
viewing rendered images, and the respondents evaluated with a
multidimensional scaling analysis.



Title: HIERARCHICAL TECHNIQUES FOR GLOSSY GLOBAL ILLUMINATION
(IMAGE PROCESSING)
Author: CHRISTENSEN, PER HENRIK
School: UNIVERSITY OF WASHINGTON (0250) Degree: PHD Date: 1995
pp: 170
Advisor: SALESIN, DAVID H.; DEROSE, ANTHONY D.
Source: DAI-B 56/12, p. 6856, Jun 1996
Subject: COMPUTER SCIENCE (0984)

Abstract: This dissertation concerns efficient computation of
realistic images. To compute realistic synthetic images, the effect
of global illumination is essential. Ray tracing algorithms solve the
global illumination problem for specular interreflections, and
radiosity algorithms solve it for diffuse interreflections. But
computing a solution is more complicated when the surfaces are
glossy. This dissertation describes hierarchical techniques for
efficient solution of the glossy global illumination problem. Two
types of hierarchy are utilized: wavelets to accurately represent
radiance distributions on surface patches, and clusters to
approximately represent radiant intensity from groups of surface
patches. Without hierarchical techniques, the solution time would be
quadratic in the number of patches and $O(n/sbsp[b][1.5])$ in the
number of basis functions $n/sb[b].$ The hierarchical techniques make
solution time linear in both the number of patches and the number of
basis functions. This reduction is significant since the numbers of
patches and basis functions are large for accurate solutions in
realistic environments. Furthermore, directional importance is used
to focus refinement of the solution on parts that contribute
significantly to a particular view of the scene. Our method is the
first finite-element method capable of handling complex glossy
scenes.



Title: ACCURATE AND RELIABLE ALGORITHMS FOR GLOBAL ILLUMINATION
(RADIOSITY, PHOTOREALISM)
Author: LISCHINSKI, DANIEL
School: CORNELL UNIVERSITY (0058) Degree: PHD Date: 1994
pp: 129
Advisor: GREENBERG, DONALD P.
Source: DAI-B 55/11, p. 4944, May 1995
Subject: COMPUTER SCIENCE (0984)

Abstract: The simulation of global illumination is one of the most
fundamental problems in computer graphics, with applications in a
wide variety of areas, such as architecture and lighting design,
computer-aided design, and virtual reality. This problem concerns the
transport of light energy between reflective surfaces in an
environment. During the past decade, radiosity has become the method
of choice for simulating global illumination in diffuse environments.
Despite much recent progress in efficiency and applicability of
radiosity methods, there are several very important open issues
remaining: (1) Radiosity images suffer from many visual artifacts,
resulting from lack of reliable automatic discretization algorithms;
and (2) Current radiosity algorithms do not provide the user with
guaranteed bounds or reliable estimates of the approximation errors.
As a result, current radiosity systems require very careful and
time-consuming user intervention in the discretization process, and
the accuracy of the resulting solutions can only be assessed by
visual appearance.
This thesis presents new radiosity algorithms for diffuse
polyhedral environments that address the open problems mentioned
above. First, we have improved and combined together two recently
developed radiosity approaches: hierarchical radiosity and
discontinuity meshing. An improved hierarchical radiosity algorithm
that is based on a discontinuity-driven subdivision strategy to
achieve better numerical accuracy and faster convergence is used to
compute the global distribution of light energy in an environment.
Then, a new algorithm based on discontinuity meshing uses the
hierarchical solution to reconstruct a visually accurate
approximation to the radiance function. Thus, results of high visual
quality can be obtained even from coarse global illumination
simulations. The solution is performed entirely in object-space,
which enables users to 'walk' through high-fidelity shaded virtual
environments in real time, using appropriate display hardware.
Second, we have developed algorithms that compute a posteriori
error bounds and estimates for local and total errors in hierarchical
radiosity solutions. A conservative algorithm computes guaranteed
upper bounds on the errors. A non-conservative algorithm is capable
of computing more realistic error estimates more efficiently. These
error estimates are used in a new error-driven refinement strategy
for hierarchical radiosity, resulting in faster convergence.



Title: EFFICIENT HIERARCHICAL RADIOSITY IN COMPLEX ENVIRONMENTS
(RADIOSITY)
Author: SMITS, BRIAN EDWARD
School: CORNELL UNIVERSITY (0058) Degree: PHD Date: 1994
pp: 120
Advisor: GREENBERG, DONALD
Source: DAI-B 55/12, p. 5436, Jun 1995
Subject: COMPUTER SCIENCE (0984)

Abstract: This thesis presents methods for speeding up the global
illumination computations by using bounds on error to eliminate work
that is not needed for a solution of a given accuracy. This work
makes the hierarchical radiosity approach feasible for complex
environments.
First, a new radiosity algorithm for efficiently computing global
solutions with respect to a constrained set of views is presented.
Radiosities of directly visible surfaces are computed to high
accuracy, while those of surfaces having only an indirect effect are
computed to an accuracy commensurate with their contribution. The
algorithm uses an adaptive subdivision scheme that is guided by the
interplay between two closely related transport processes: one
propagating power from the light sources, and the other propagating
importance from the visible surfaces. By simultaneously refining
approximate solutions to the dual transport equations, computation is
significantly reduced in areas that contribute little to the region
of interest. This approach is very effective for complex environments
in which only a small fraction is visible at any time. Our statistics
show dramatic speedups over the fastest previous radiosity algorithms
for diffuse environments with details at a wide range of scales.
A new approach for accelerating hierarchical radiosity by
clustering objects is also presented. Previous approaches constructed
effective hierarchies by sub-dividing surfaces, but could not exploit
a hierarchical grouping on existing surfaces. This limitation
resulted in an excessive number of initial links in complex
environments. Initial linking is potentially the most expensive
portion of hierarchical radiosity algorithms, and constrains the
complexity of the environments that can be simulated. The clustering
algorithm presented here operates by estimating energy transfers
between collections of objects while maintaining reliable error
bounds on each transfer. Two methods of bounding the transfers are
employed with different tradeoffs between accuracy and time. In
contrast with the $O(s/sp2)$ time and space complexity of the initial
linking in previous hierarchical radiosity algorithms, the new
methods have complexities of O(s log s) and O(s) for both time and
space. Using these methods we have obtained speedups of two orders of
magnitude for environments of moderate complexity while maintaining
comparable accuracy.
Finally, the thesis describes a method for reconstructing the
radiance functions across the visible surfaces given a global
solution to the energy balance equations. This approach greatly
reduces artifacts resulting from the choice of constant basis
functions used for the global solution.



Title: RAY TRACING AND RADIOSITY ALGORITHMS FOR PHOTOREALISTIC
IMAGE SYNTHESIS
Author: KOK, ADRIANUS JOHANNES FRANCISCUS
School: TECHNISCHE UNIVERSITEIT TE DELFT (THE NETHERLANDS) (0951)
Degree: DR Date: 1994 pp: 140
Source: DAI-C 55/04, p. 1267, Winter 1994
Subject: COMPUTER SCIENCE (0984)
ISBN: 90-6275-981-5
Publisher: DELFT UNIVERSITY PRESS, STEVINWEG 1, 2628 CN
DELFT, THE NETHERLANDS

Abstract: Realistic image synthesis strives to generate images that
not only look realistic, but that are also physically correct. All
kinds of optical effects must be computed to reach this goal.
A combination of radiosity and ray tracing methods is able to
compute all these effects. The radiosity process computes the
illumination of the surfaces in a scene, and the ray tracing process
renders the scene using the illumination values computed in the
radiosity process. A disadvantage of this hybrid method is that the
quality of the resulting images strongly depends on the number of
points (meshing) for which illumination values are computed.
To avoid inaccurate shadows an alternative method has been
developed. The radiosity pass computes only the illumination that is
responsible for minor shading gradients. The illumination that is
responsible for important shading gradients (perceptible shading
contrast) is added during rendering by recomputing the illumination
of the important sources for all visible points. A source selection
mechanism determines which sources are responsible for important
shading gradients. This new method can generate very accurate images,
and is very flexible. Depending on how strict source selection
criteria are applied, most known hybrid radiosity and ray tracing
methods can be simulated.
Radiosity and ray tracing are both expensive processes. The
radiosity method can be improved by using a hierarchical meshing of
the scene. This meshing should not only include an adaptive
subdivision of surfaces, but also the grouping of several surfaces
into groups. Interaction of light between two objects is then
computed at the most appropriate level in the hierarchy, considering
accuracy and efficiency. The rendering pass can be improved by
reducing the number of shadow rays. This is achieved by exploiting
shadow coherence, because shadows tend to be very coherent and
homogeneous. Also, when sampling large area light sources, an
adaptive stochastic sampling method may reduce the number of shadow
rays compared to other sampling methods.



Title: DISTRIBUTION-INDEPENDENT HIERARCHICAL N-BODY METHODS
(GREENGARD METHOD)
Author: ALURU, SRINIVAS
School: IOWA STATE UNIVERSITY (0097) Degree: PHD Date: 1994
pp: 88
Advisor: PRABHU, G. M.; GUSTAFSON, JOHN
Source: DAI-B 55/09, p. 3968, Mar 1995
Subject: COMPUTER SCIENCE (0984)

Abstract: The N-body problem is to simulate the motion of N
particles under the influence of mutual force fields based on an
inverse square law. The problem has applications in several domains
including astrophysics, molecular dynamics, fluid dynamics,
radiosity methods in computer graphics and numerical complex
analysis. Research efforts have focused on reducing the $O(N/sp2)$
time per iteration required by the naive algorithm of computing each
pairwise interaction. Widely respected among these are the Barnes-Hut
and Greengard methods. Greengard claims his algorithm reduces the
complexity to O(N) time per iteration.
Throughout this thesis, we concentrate on rigorous,
distribution-independent, worst-case analysis of the N-body methods.
We show that Greengard's algorithm is not O(N), as claimed. Both
Barnes-Hut and Greengard's methods depend on the same data structure,
which we show is distribution-dependent. For the distribution that
results in the smallest running time, we show that Greengard's
algorithm is $/Omega(N log/sp2N)$ in two dimensions and $/Omega(N
log/sp4N)$ in three dimensions. Both algorithms are unbounded for
arbitrary distributions.
We have designed a hierarchical data structure whose size depends
entirely upon the number of particles and is independent of the
distribution of the particles. We show that both Greengard's and
Barnes-Hut algorithms can be used in conjunction with this data
structure to reduce their complexity. Apart from reducing the
complexity of the Barnes-Hut algorithm, the data structure also
permits more accurate error estimation. We present two- and
three-dimensional algorithms for creating the data structure. The
multipole method designed using this data structure has a complexity
of O(N log N) in two dimensions and O(N log$/sp2$ N) in three
dimensions.



Title: GLOBAL ILLUMINATION MODELS FOR VOLUME RENDERING
(RENDERING)
Author: SOBIERAJSKI, LISA MARIE
School: STATE UNIVERSITY OF NEW YORK AT STONY BROOK (0771)
Degree: PHD Date: 1994 pp: 220
Advisor: KAUFMAN, ARIE E.
Source: DAI-B 55/11, p. 4950, May 1995
Subject: COMPUTER SCIENCE (0984)

Abstract: The increasing demand for realistic images has led to the
development of several global illumination models and rendering
techniques. Great effort has been taken to extend these illumination
models and optimize the rendering techniques to produce more
realistic images in less time. Despite this effort, most of these
methods are designed for scenes consisting of geometric surface
descriptions, and cannot directly render volumetric data. Volumetric
data sets can be rendered using volume rendering techniques that, in
order to decrease rendering times and therefore increase
interactivity, typically employ only a local illumination model.
The development of global illumination models and rendering
techniques for volumetric data is the focus of this work. These
illumination methods can be used to generate realistic images of
scenes containing volumetric as well as geometric data. The
volumetric global illumination methods can be employed by a
visualization system in order to add intuitive cues to an image for a
greater three-dimensional understanding of a scene. Also, these
methods allow for amorphous effects that can not be captured using
geometric illumination models, including clouds, fog, and smoke.
A volumetric ray tracing method is presented that encompasses
classical ray tracing while allowing for volume rendering effects.
The definition of an intersection is extended to include intersection
points for surface contributions to the intensity equation, and
intersection segments for volumetric contributions. A method for
accelerating primary and shadow rays is developed.
A volumetric radiosity method is presented that encompasses
classical radiosity while also including isotropic and diffuse
volumetric interactions. Geometric surfaces and volumetric
isosurfaces are approximated using standard surface patches, and
voxels are used to approximate participating volumes. Diffuse
volumetric interactions make it possible to give the appearance of
shaded surfaces to scenes consisting of only volumetric data.
Hierarchical techniques are applied to decrease the number of
interactions required for a solution.
Multipass methods are developed to increase realism by combining
illumination methods. A multipass method that combines volumetric ray
tracing and volumetric radiosity is presented. Also, a multipass
method that extends volumetric ray tracing to account for indirect
specular lighting is presented.



Title: WAVELET ALGORITHMS FOR ILLUMINATION COMPUTATIONS
(GRAPHICS, RADIOSITY)
Author: SCHRODER, PETER
School: PRINCETON UNIVERSITY (0181) Degree: PHD Date: 1994
pp: 141
Source: DAI-B 55/12, p. 5434, Jun 1995
Subject: COMPUTER SCIENCE (0984); MATHEMATICS (0405); PHYSICS,
RADIATION (0756)

Abstract: One of the core problems of computer graphics is the
computation of the equilibrium distribution of light in a scene. This
distribution is given as the solution to a Fredholm integral equation
of the second kind involving an integral over all surfaces in the
scene. In the general case such solutions can only be numerically
approximated, and are generally costly to compute, due to the
geometric complexity of typical computer graphics scenes. For this
computation both Monte Carlo and finite element techniques (or hybrid
approaches) are typically used.
A simplified version of the illumination problem is known as
radiosity, which assumes that all surfaces are diffuse reflectors.
For this case hierarchical techniques, first introduced by Hanrahan
et al. (32), have recently gained prominence. The hierarchical
approaches lead to an asymptotic improvement when only finite
precision is required. The resulting algorithms have cost
proportional to $O(k/sp2 + n)$ versus the usual $O(n/sp2)$ (k is the
number of input surfaces, n the number of finite elements into which
the input surfaces are meshed). Similarly a hierarchical technique
has been introduced for the more general radiance problem (which
allows glossy reflectors) by Aupperle et al. (6).
In this dissertation we show the equivalence of these
hierarchical techniques to the use of a Haar wavelet basis in a
general Galerkin framework. By so doing, we come to a deeper
understanding of the properties of the numerical approximations used
and are able to extend the hierarchical techniques to higher orders.
In particular, we show the correspondence of the geometric arguments
underlying hierarchical methods to the theory of Calderon-Zygmund
operators and their sparse realization in wavelet bases. The
resulting wavelet algorithms for radiosity and radiance are analyzed
and numerical results achieved with our implementation are reported.
We find that the resulting algorithms achieve smaller and smoother
errors at equivalent work.



Title: LINEAR MODELS OF REFLECTIVE COLOUR (MACHINE VISION, SOLID
SURFACES)
Author: PAETH, ALAN WILLIAM
School: UNIVERSITY OF WATERLOO (CANADA) (1141) Degree: PHD
Date: 1994 pp: 382
Advisor: COWAN, WILLIAM B.
Source: DAI-B 56/02, p. 926, Aug 1995
Subject: COMPUTER SCIENCE (0984)
ISBN: 0-315-94773-X

Abstract: Colour is an artifact of the continuous, interacting
physical processes of light and matter. In theory, colour models
using linear systems require a high dimension. In practice, the
perception of light rays is well-modeled using an 3-space whose
construction is based upon the trichromatic nature of human vision.
Linear systems may also model the reflectance functions of surfaces
(Yilmaz, 1962). A larger n-space is required to minimize perceivable
colour error of a surface under unspecified illumination. Bounds as
low as n $/approx$ 6 have been demonstrated by using a Fourier basis
(Buchsbaum and Gottshalk, 1984). Contemporary research in perceptual
models for human and machine vision apply regression techniques, such
as the singular value decomposition, to create orthogonal bases
(Maloney, 1986), often derived from widely available reflectance data
on natural surfaces (Krinov, 1947).
This thesis extends methods of low-dimensional reflectance
modeling, thereby providing a framework suitable to computer graphics
with direct application to radiosity-based rendering and digital
printing. The framework systematizes both the sequential production
of orthogonal bases and methods of dimensional change. Each basis
spans a reflectance space, by analogy to the additive colour spaces
of light. A reflectance space contains a unique reflectance solid: a
convex polytope whose volume describes merely valid colours (e.g.,
excludes surfaces of 'negative' reflectivity). The SVD methods are
constrained so that white reflectances $/rho(/lambda)$ = 1 are always
representable. This concedes little in accuracy yet is both necessary
and sufficient to guarantee that all reflectance solids exhibit a
useful symmetry of inversion. Solids are derived from
spectroradiometric data produced in-house and studied using both
formal and empirical methods. Digital production of colour facsimile
whose reflectances form an equivalence class with an original's
engenders an illumination-independent means of colour correction,
named reflectance matching.



Title: SHADING COMPUTATIONS ON THE RADIATION MANIFOLD (COMPUTER
VISION, IMAGE PROCESSING)
Author: LANGER, IRA MICHAEL SAMUEL
School: MCGILL UNIVERSITY (CANADA) (0781) Degree: PHD Date: 1994
pp: 123
Advisor: ZUCKER, S. W.
Source: DAI-B 56/10, p. 5678, Apr 1996
Subject: ENGINEERING, ELECTRONICS AND ELECTRICAL (0544); COMPUTER
SCIENCE (0984)
ISBN: 0-612-00108-3

Abstract: How may the shape of a smooth surface be inferred from an
image? Traditional methods in computer vision for inferring
shape-from-shading assume that surface shading depends entirely on
surface orientation. In many illumination scenarios, however, shading
may occur independently of surface orientation. For example, when an
extended light source such as the sky casts a continuous shadow on a
flat ground, the resulting shading is due to illumination variations
only.
In this thesis, a new approach to shape-from-shading is taken in
which shading variations are attributed entirely to spatially varying
illumination. This leads to a new analysis of the shape-from-shading
problem, and to a new algorithm for solving it. In particular, a
model of spatially varying illumination is developed which is in
terms of the set of light rays in free space. This set is shown to be
a four dimensional smooth manifold, called the radiation manifold.
Local transformations between coordinate systems on this manifold are
derived, and provide the basic mechanism of a new, parallel algorithm
for inferring shape-from-shading.
The scope of the thesis reaches beyond shape-from-shading,
however. The radiation manifold is used to solve two other shading
problems in which illumination varies across space, namely the
radiosity equation in computer graphics and the shape-from-darkness
problem in computer vision. The thesis thus provides a unifying
framework in which a variety of shading problems may be understood
and solved.



Title: ANALYSIS AND MODELLING OF LUMINOUS REFLECTION APPLIED TO
LIGHTING SIMULATIONS
[ETUDE ET MODELISATION DE LA REFLEXION LUMINEUSE DANS LE
CADRE DE L'ECLAIRAGE PREVISIONNEL]
Author: EMBRECHTS, JEAN JACQUES
School: UNIVERSITE DE L'ETAT A LIEGE (BELGIUM) (0422) Degree: PHD
Date: 1994 pp: 191
Source: DAI-C 56/03, p. 746, Fall 1995
Language: FRENCH
Subject: PHYSICS, OPTICS (0752); ARCHITECTURE (0729)
Location: UNIVERSITE DE LIEGE, BIBLIOTHEQUE GENERALE,
PLACE COCKERILL, 1, B-4000 LIEGE, BELGIUM

Abstract: This work is intended to propose a mathematical model to
describe the scattering indices of light reflected by a sample of
material.
There are two contributions in light reflection: surface
reflection and volume or bulk reflection. The mathematical model set
up in this work is greatly inspired by this duality.
The modelized parameter is the luminance factor. An apparatus has
been conceived to measure this factor in the plane of incidence, as a
function of the angle of incidence and the viewing angle. Several
materials have been measured: among them are glass, wood, and
concrete samples.
Modelization begins with the theoretical development of a plane
electromagnetic wave scattered by a rough surface, a theory first
developed by Beckmann. This theory has been reformulated and
corrected, for example to take into account the shadowing effects of
each surface element on its neighbours. Two terms represent surface
reflection: the first is the coherent (and specular) reflection which
is only significant for plane surfaces, and the second is the
incoherent reflection which depends on a statistical parameter
describing the roughness of the surface.
Bulk reflection is represented by an experimental model issued
from a study of light reflected by an opaline glass sample. This term
is added to both surface reflection terms and, together, they form
what is called the general model for light reflection. This is a
five-parameter model which expresses the angular variation of the
luminance factor. It has been tested for several materials and
compared with other models.
Finally, this general model has been applied to an interior
lighting program (LUXCALC) based on the radiosity technique.



Title: COMPUTER GRAPHICS TECHNIQUES FOR OPERA LIGHTING DESIGN AND
SIMULATION
Author: DORSEY, JULIE O'BRIEN
School: CORNELL UNIVERSITY (0058) Degree: PHD Date: 1993
pp: 159
Advisor: GREENBERG, DONALD P.
Source: DAI-B 54/02, p. 931, Aug 1993
Subject: COMPUTER SCIENCE (0984); THEATER (0465); ARCHITECTURE
(0729)

Abstract: A major problem challenging opera designers is the
inability to coordinate lighting, projection systems, and set designs
in the preliminary planning phase. This thesis presents a suite of
new computer graphics techniques that provide set and lighting
designers the opportunity to evaluate, test, and control opera
designs prior to the construction of full-scale sets and installation
of the lighting apparatus. There are four novel parts: light source
input and attribute assignment, simulation of directional lighting,
modeling of scenic projection systems, and an approach for the design
and preview of time-dependent intensity variations. When integrated,
these components demonstrate the potential for the use of computer
graphics in lighting design.
First, the light source input component consists of a program for
assigning light source attributes by using a set of theater lighting
icons. This module allows a designer to specify light source
characteristics in a way familiar to the discipline and to make
preliminary evaluations of the lighting conditions. Second, an
extended progressive radiosity method is introduced to simulate the
directional lighting characteristics that are specified by the input
program. Third, a projection approach is presented to simulate the
optical effects of scenic projectors. In addition, a solution to the
distortion problem produced by angular projections is described.
Fourth, a system for designing and previewing complex,
time-dependent, lighting intensity variations by rapid image
compositing is given. After minimal pre-processing, real-time
playback is achieved regardless of scene and lighting complexity. To
accelerate the pre-processing, the algorithm uses a minimal basis set
of global solutions to construct the entire time sequence. The
sequence is progressively refined by computing basis solutions in
order of increasing overall contribution, producing useful
approximations very quickly. A design methodology is presented that
shows how the algorithm can be used for interactive design. The
techniques are demonstrated with several complex models based on
actual stage sets.



Title: DISCONTINUITY MESHING FOR RADIOSITY IMAGE SYNTHESIS
(SHADOW ALGORITHMS)
Author: TAMPIERI, FILIPPO
School: CORNELL UNIVERSITY (0058) Degree: PHD Date: 1993
pp: 202
Source: DAI-B 54/07, p. 3716, Jan 1994
Subject: COMPUTER SCIENCE (0984)

Abstract: The simulation of global illumination is one of the most
fundamental problems in computer graphics, with applications in a
wide variety of areas. This problem studies the light energy transfer
between reflective surfaces in an environment. Initially derived from
the field of thermal engineering, radiosity has emerged over the past
several years as one of the most promising solution methods.
Despite having produced some of the most realistic-looking
computer generated images to date, radiosity methods have not yet met
with widespread acceptance. The main obstacle has been their need for
very careful and time consuming user intervention, without which,
current techniques are prone to generating a wide range of annoying
visual artifacts. These artifacts are generally due to poor surface
meshing, resulting in insufficient sampling density and ineffective
sample placement.
This thesis investigates the roots of this problem by taking a
step back from the traditional finite element formulation of
radiosity and examining the more general integral equation
formulation. An analysis of the radiance functions described by this
equation shows how umbra and penumbra boundaries as well as other
sharp changes in illumination actually correspond to discontinuities
in the radiance function and its derivatives. The results of this
analysis have led to the concept of discontinuity meshing, whereby
accurate approximations to the radiance functions are computed by
explicitly representing their discontinuities as boundaries in the
mesh.
This concept has been applied to the design of a discontinuity
meshing algorithm for polyhedral environments. The algorithm is
embedded in a progressive refinement radiosity system and uses
piecewise quadratic interpolation to reconstruct a smooth radiance
function while preserving discontinuities where appropriate.
The radiosity solutions produced by the new algorithm are
compared against a photograph of a physical environment, an
analytical solution, and a conventional, yet state-of-the-art,
radiosity system, and its performance on architectural models of
medium complexity is measured. The results are remarkably accurate
both numerically and visually. The new discontinuity meshing
algorithm drastically reduces, and in many cases eliminates, many of
the annoying artifacts typical of conventional radiosity meshes,
producing images of previously unattained quality. Moreover, the
meshing is completely automatic and produces solutions that are
highly view-independent.



Title: A PARALLEL IMAGE RENDERING ALGORITHM AND ARCHITECTURE
BASED ON RAY TRACING AND RADIOSITY SHADING
Author: SHEN, LI-SHENG
School: TECHNISCHE UNIVERSITEIT TE DELFT (THE NETHERLANDS) (0951)
Degree: DR Date: 1993 pp: 206
Source: DAI-C 55/02, p. 627, Summer 1994
Subject: COMPUTER SCIENCE (0984)
ISBN: 90-5326-012-9
Publisher: DELFT UNIVERSITY, DELFT, THE NETHERLANDS

Abstract: This dissertation is about the parallelization of an
algorithm that has become known as the two-pass approach, for
rendering artificial scenes with photo realism on the screen of a
workstation. The two-pass approach demands orders-of-magnitude more
processing power for a single processor if we wish to make a
state-of-art image in real-time or even interactive time. An obvious
answer to this dilemma lies in parallel processing, and the following
algorithm/architecture issues will turn up: (1) Combined algorithmic
and architectural design; (2) Latency and synchronization problems;
and (3) Resource management problem. Those issues will be the main
theme of this dissertation.
We aim to develop a very efficient and effective parallel machine
that can serve as a rendering accelerator attached to various
standard workstations, in particular for ray-casting based
applications. The radiosity engine has been completely modelled in
BONeS$/sp/circler$, and we have evaluated its performance for a set
of practical scenes. Promising results have been observed, including
the following: (1) The performance of the shelling technique is a
weak function of the scene complexity. The computational complexity
of the shelling technique is k $/times$ R (k is about 2-5) as
compared to N $/times$ R (N is the total number of patches) of the
naive algorithm, where R is the total number of
intersection-computation rays. (2) A reasonable speedup has been
observed up to 8 clusters. The limiting factors in speedup are
workload imbalancing, the long latencies for global memory requests
and the limited bandwidths supported by the system and local buses.
To achieve a higher scalability of the system, further improvement in
the front-end system together with the use of a dynamic workload
balancing scheme would be necessary. (3) The performance of software
intersection computation on HP720 is about 0.2M/sec. The radiosity
engine provides two-orders-of-magnitude more processing power than
this software approach per cluster.



Title: PHOTOREALISTIC VOLUME RENDERING (RADIOSITY)
Author: BHATE, NEETA VASANT
School: UNIVERSITY OF SOUTH FLORIDA (0206) Degree: PHD
Date: 1993 pp: 148
Advisor: PIEGL, L. A.
Source: DAI-B 54/09, p. 4769, Mar 1994
Subject: COMPUTER SCIENCE (0984)

Abstract: In a typical room, (such as the one you may be reading
this abstract in) the air is invisible since the particles that
constitute air do not have significant interactions with the visible
light that is bouncing around. However, when there is smoke, fog or
dust, the particles that constitute matter have significant
interactions with light energy and, as a result, the medium becomes
visible to human observers. Such media are termed as participating.
In this dissertation two problems have been addressed. The first is
the photorealistic rendering of 3-dimensional scenes containing
participating media that scatter light anisotropically. The second is
the speedup that can be achieved through the application of the
hierarchical radiosity concept to (isotropic) volume radiosity
algorithms.
The pursuit of visual realism entails a simulation of various
physical phenomena exhibited by heat and light. A physically accurate
model for participating media that exhibit anisotropic scattering has
been investigated. The model takes into account all possible
transport chains in an environment consisting of diffuse surfaces and
directional scattering by media. Important information about the
scattering behaviour of a medium is contained in the phase function.
For directional scattering, the phase function can be very complex
and its accurate modeling is of utmost importance in any attempts at
capturing anisotropic effects. The approach used here exploits
various properties of spherical harmonics to achieve the desired
goal.
Most algorithms for the inclusion of participating media in
3-dimensional scenes are extremely cumbersome (space and time
expensive) and this is the main obstacle standing in the way of their
widespread use. A technique to speedup volume rendering radiosity
algorithms is presented. The method is an application of the
hierarchical radiosity concept to volume rendering. Substantial
speedups can be achieved thus paving the way for interactive volume
rendering. The limitations for real time use have thus been partially
lifted.



Title: HIERARCHICAL ALGORITHMS FOR ILLUMINATION
Author: AUPPERLE, LARRY
School: PRINCETON UNIVERSITY (0181) Degree: PHD Date: 1993
pp: 145
Source: DAI-B 54/10, p. 5252, Apr 1994
Subject: COMPUTER SCIENCE (0984)

Abstract: This dissertation is a discussion and development of
hierarchical algorithms for illumination. These algorithms operate
through recursive, adaptive refinement of the environment into
hierarchical meshes--rather than computing light transport only
between elements at the finest level of refinement, the algorithms
allow computation of transport between higher level subpatches, as
controlled by user specified error bounds. As discussed in this
dissertation, employment of hierarchical methods yields significant
savings in computation.
The initial work in hierarchical methods was that of Hanrahan and
Salzman for the computation of radiosity over unoccluded
environments. In this dissertation, we discuss extension of the
algorithm to occluded environments, incorporating visibility
heuristics and acceleration via radiosity weighting. Given an
environment consisting of k polygonal patches and n elements at the
finest level of refinement, the algorithm requires at most
$O(n+k/sp2)$ transport interactions; traditional methods require
$O(n/sp2).$
Application of hierarchical transport to nondiffuse reflection is
developed through the derivation of a radiance formulation for
discrete three point transport, incorporating a new measure and
description of reflectance: area reflectance. This formulation and
associated reflectance allow an estimate of error in the computation
of radiance across triples of surface elements, and lead directly to
a hierarchical refinement algorithm for global illumination.
We have implemented and analyzed this algorithm over surfaces
exhibiting glossy and diffuse reflection. Theoretical growth in
transport computation is shown to be $O(n+k/sp3)$--this growth is
exhibited in experimental trials. Naive application of three point
transport would require computation over $O(n/sp3)$ element triples.
Global illumination within nondiffuse environments is ideally
suited for computation under importance and radiance driven
refinement: a transport interaction is of significance only if it
lies within paths of directional reflection of both radiance
originating at a light source, and importance originating at the eye.
We have thus derived the adjoint to the radiance transport
formulation, and present preliminary results of application of this
adjoint in the form of an importance driven version of our
implementation. These results show significant reduction in
computation, and indicate that importance and radiance driven
hierarchical techniques possess great potential for efficient
evaluation of global illumination over general reflection.



Title: PARALLEL HIERARCHICAL N-BODY METHODS AND THEIR
IMPLICATIONS FOR MULTIPROCESSORS
Author: SINGH, JASWINDER PAL
School: STANFORD UNIVERSITY (0212) Degree: PHD Date: 1993
pp: 186
Advisor: HENNESSY, JOHN L.
Source: DAI-B 54/02, p. 945, Aug 1993
Subject: COMPUTER SCIENCE (0984); ENGINEERING, ELECTRONICS AND
ELECTRICAL (0544)

Abstract: To make significant advances in the design of large-scale
multiprocessing systems, designers need to understand the
characteristics of the applications that will run on these systems.
This thesis studies the parallelization and system implications of
one important class of scientific applications: N-body applications
that use hierarchical solution methods. We focus primarily on the
Barnes-Hut and Fast Multipole methods, the two most prominent
hierarchical methods for classical N-body problems. In addition, we
study a radiosity application from computer graphics, which is an
application of the hierarchical N-body approach to a very different
problem domain.
We first address the problem of obtaining effective parallel
performance on these applications, which is challenging owing to
their nonuniform, dynamically changing nature and their need for
long-range communication. For the classical applications, we show
that simple yet effective partitioning techniques can be developed by
exploiting key insights into the problems and solution methods. Using
a novel partitioning technique which we propose, 45-fold speedups are
obtained on a 48-processor Stanford DASH machine (a cache-coherent,
shared address space multiprocessor) and 118-fold speedups are
obtained on a 128-processor simulated architecture, even for
relatively small problems. The radiosity application also yields good
parallel performance (27-fold speedup on a 32-processor DASH), but
only by resorting to dynamic task stealing.
We then study the implications of this class of applications for
multiprocessor architecture. We show that both a shared address space
and caching are important architectural properties for achieving high
performance. Finally, we examine the architectural implications of
scaling the applications to run on machines with more processors. We
find that using a scaling methodology which reflects the concerns of
the application scientist leads to different conclusions than do more
naive methods of scaling typically found in the literature. In
particular, both the communication to computation ratio that a
machine must support, as well as the size of a processor's working
set (and hence the per-processor cache size required for effective
performance) grow slowly as larger problems are run on larger
machines.



Title: CONSTRAINT-BASED RENDERING FOR SCENES WITH HIGH DYNAMIC
RANGES
Author: FANG, LIJIANG
School: UNIVERSITY OF WATERLOO (CANADA) (1141) Degree: MMATH
Date: 1993 pp: 152
Advisor: COWAN, WILLIAM B.
Source: MAI 32/03, p. 985, Jun 1994
Subject: COMPUTER SCIENCE (0984)
ISBN: 0-315-84561-9

Abstract: Many researchers have examined rendering techniques with a
focus on realistic image synthesis. Ray tracing and radiosity, which
are the most successful current methodologies, are based on the
physics of light and surfaces. Neither considers display device
limitations or properties of human visual perception. Furthermore,
the synthetic camera model has shown its deficiency in rendering
images with high dynamic ranges onto display devices with lower
dynamic ranges.
A new rendering framework is proposed. Human visual properties
are incorporated into the framework to increase the effective visual
contrast. It is known in visual perception that brightness is not a
monotonic function of intensity. The perceived brightness is affected
by the intensities of the surrounding area. It is also known that
human vision is insensitive to low frequency spatial intensity
variation. In the proposed framework, to preserve the visual contrast
in one image, the contrasts across edges are maintained while the
intensities in large areas are slowly varied.
Based on the proposed framework, a modified rendering pipeline is
presented and a prototype system is implemented. The system generates
the contrast constraints by invoking a modified visible surface
algorithm. Then, the problem of satisfying the constraint hierarchy
is transformed into a bounded linear least squares (BLLS) problem.
Numerical algorithms are employed to solve the BLLS problem.



Title: MAPPING RADIOSITY COMPUTATIONS TO PARALLEL PROCESSORS
Author: SINGH, GAUTAM BIR
School: WAYNE STATE UNIVERSITY (0254) Degree: PHD Date: 1993
pp: 142
Advisor: SIY, PEPE
Source: DAI-B 54/03, p. 1503, Sep 1993
Subject: COMPUTER SCIENCE (0984); ENGINEERING, ELECTRONICS AND
ELECTRICAL (0544); PHYSICS, OPTICS (0752)

Abstract: The radiosity method for rendering scenes is gaining
popularity because of its ability to accurately model the energy
distribution in an environment. As this photonic energy distribution
is independent of the viewer's position, generating scenes for
different viewpoints only requires hidden surface removal and can be
performed in real-time. This makes it more attractive than ray
tracing as a technique for modeling illumination. It is quite
conceivable that radiosity method will be used for applications in
scientific visualization, lighting simulations, CAD/CAM, virtual
reality, and medical imaging.
Computing radiosity of a scene with moderate to high complexity
is tantamount to solving a system of tens of thousands of linear
equations. Iterative linear system solvers, such as Gauss-Seidel,
Jacobi, or conjugate descent, are quite demanding for a system of
equations this large. An alternate approach, known as progressive
refinement, offers some computational tractability and delivers an
approximate solution relatively quickly.
This dissertation presents the results of partitioning the
radiosity computation to suitably map on a variety of multiprocessor
classes. The effect of problem decomposition on computation and
communication components is studied for the shared memory, the
message passing and the loosely coupled distributed memory
multiprocessors. Kendall Square Research's KSR1 and Intel hypercube
iPSC/860 were used for experimenting with the shared memory and
message-passing algorithms respectively. A network of IBM RS/6000 was
used for understanding coarse grain parallelization techniques. These
experiments demonstrated that optimality of parallel algorithms must
be considered as a $/langle machine, algorithm/rangle$ pair. Thus the
notion of program portability must also take machine architecture in
consideration beside allowing for software compatibility.
As the number of polygons for processing complex scenes continues
to grow, the subdivision in the object space become increasingly
important. An adaptive technique for binary subdivision of the object
space is outlined and used in all the experiments. The resulting tree
has a better balance as compared to the conventional techniques. A
multiprocessor architecture that utilizes the object space
subdivision and uses the token driven dataflow computation model is
proposed as a hardware solution for radiosity. The proposed
architecture is targeted toward the high end workstations which can
benefit from the proposed design in performing radiosity computation
and other similar tasks.



Title: PARALLEL HIERARCHICAL RADIOSITY RENDERING (RADIOSITY)
Author: CARTER, MICHAEL BRANNON
School: IOWA STATE UNIVERSITY (0097) Degree: PHD Date: 1993
pp: 173
Advisor: WRIGHT, CHARLES W.
Source: DAI-B 54/03, p. 1563, Sep 1993
Subject: ENGINEERING, ELECTRONICS AND ELECTRICAL (0544); COMPUTER
SCIENCE (0984); ENGINEERING, HEAT AND THERMODYNAMICS
(0348)

Abstract: The radiosity equation is examined, and is found to
contain a previously unexploited symmetry. This symmetry is
formalized, and a solution method previously unusable in the field of
computer graphics (conjugate gradients) is shown to be superior to
all methods currently in use. A detailed analysis of all solution
techniques previously applied to the radiosity problem is conducted,
and results presented.
So-called 'hierarchical methods' have reduced the operational
complexity of the N-body problem from $O(N/sp2)$ to O(N log N)
assuming a pre-set error tolerance. An algorithm following the same
basic tenets has been applied to radiosity rendering by other
researchers, and has reduced the operational complexity from
$O(N/sp2)$ to (arguably) O(N).
Shortcomings in the state-of-the-art hierarchical radiosity
method are pointed out, and enhancements are offered. A consistent
treatment of various types of error is found to be absent from
present methods. Catastrophic error is possible in the visibility
assessment between two polygons. A self-consistency check is possible
during the solution process, but never exploited.
Until now, supercomputer-class computers have not been used to
solve radiosity problems at a production-quality level even though
realistic image synthesis has always been a prodigious consumer of
computer time. A state-of-the-art hierarchical radiosity code is
implemented on an nCUBE-2 parallel computer, and discussed in detail.
The algorithm is found to have ample sources of parallelism, in both
data- and operational modes. Its performance is analyzed in detail.
The hierarchical method has only been applied to realistic image
synthesis since 1991. Not surprisingly, many avenues of further
research are open. Some are pointed out, and include: analytic
determination of coupling factors, quantifying discretization error,
incorporating specular light reflection modes into the hierarchical
treatment, and exploring what other important physical problems might
benefit from the hierarchical approach.



Title: ANALYSIS OF ENERGY TRANSFER IN INDUSTRIAL GAS-FIRED
RADIANT TUBE FURNACES
Author: HARIHARAN, RAMAMURTHY
School: PURDUE UNIVERSITY (0183) Degree: PHD Date: 1993 pp: 319
Advisor: VISKANTA, RAYMOND; RAMADHYANI, SATISH
Source: DAI-B 55/04, p. 1624, Oct 1994
Subject: ENGINEERING, MECHANICAL (0548); ENGINEERING, HEAT AND
THERMODYNAMICS (0348)

Abstract: A thermal system mathematical model has been developed to
predict heat transfer from the products of combustion in the radiant
tubes to the ultimate load in the furnace. The three-dimensional
thermal model for the furnace involved the integration of various
submodels for the radiant tube and the furnace enclosure.
For the radiant tube, mathematical models were developed to
describe turbulent interdiffusion of fuel and air, combustion, flame
radiation and NO$/sb[x]$ emissions from the system by solving the
conservation equations of mass, momentum, chemical species and
energy. The turbulent transport was modeled using a low Reynolds
number k-$/epsilon$ turbulence model, and a modified
weighted-sum-of-gray-gases model was employed for spectral radiative
transfer calculations using the discrete ordinates approach. The
reaction between fuel and air was assumed to be a single step,
infinitely fast process, and the mean concentration of the species
were obtained using an appropriate probability density function for
the mixture fraction. The two-dimensional radiant tube model
predictions were verified using available experimental data.
The temperature distribution in the refractory walls and the load
were obtained by calculating the incident heat fluxes from the
radiant tubes via the radiosity method. The thermal models for batch
and continuous furnaces were verified using experimental data
obtained from industrial furnaces. Heat transfer enhancement methods
were identified by performing parametric calculations using the
furnace thermal models.
The thermal system model revealed that radiation is the dominant
mode of heat transfer from the radiant tubes to the load in the
furnace. The parametric studies revealed that increasing load
emissivities increased net heat transfer to the load and thereby the
overall furnace efficiency. Highly reflective refractories helped
reduce the temperature of the refractories with no adverse effect on
the furnace efficiency. Although increasing the fuel firing rate in
the radiant tubes increased the net heat transfer rate to the load,
the furnace efficiency decreased due to increased loss of energy at
the radiant tube exhaust. The analysis using different stock
materials in the furnace indicated that different optimum firing
strategies exist for different stock materials.



Title: IMAGE SYNTHESIS USING FRONT-TO-BACK BASED RADIOSITY
METHODS
Author: WANG, YIGONG
School: UNIVERSITY OF ALBERTA (CANADA) (0351) Degree: PHD
Date: 1992 pp: 169
Source: DAI-B 53/12, p. 6405, Jun 1993
Subject: COMPUTER SCIENCE (0984)
ISBN: 0-315-73087-0

Abstract: This thesis is concerned with a new radiosity method for
image synthesis. In general, a radiosity method includes four steps:
polygon subdivision, form-factor calculation, radiosity solution, and
image display. The most expensive part is the form-factor
calculation. This new radiosity method, termed FBRM, uses a
front-to-back approach rather than the traditional z-buffer method to
calculate form-factors.
In order to determine the depth order of patches efficiently, the
subdivision step not only subdivides polygons into patches, but also
yields a set of octants by using a linear octree technique. An octant
priority list with respect to the given viewpoint is obtained by
traversing the linear octree. With the octant priority list, the
front-to-back based hemi-cube method can speed up form-factor
calculation significantly since some of patches that are hidden by
other patches can normally be detected and discarded at an earlier
stage before they are actually processed.
This thesis also deals with the aliasing problem occurring in
calculating form-factors, and the parallel implementation of the
FBRM. These two aspects are of importance to image quality and
efficiency. Another important part of this thesis is the
implementation of the FBRM. Most of features in the FBRM were
realized mainly on a Sun 3/60 workstation.



Title: AN ADAPTIVE DISCRETIZATION METHOD FOR PROGRESSIVE
RADIOSITY
Author: LALONDE, PAUL
School: QUEEN'S UNIVERSITY AT KINGSTON (CANADA) (0283)
Degree: MSC Date: 1992 pp: 83
Source: MAI 31/04, p. 1836, Winter 1993
Subject: COMPUTER SCIENCE (0984)
ISBN: 0-315-76516-X

Abstract: The problem of global illumination is to accurately
simulate lighting effects in a scene being rendered by computer.
Early efforts made shading of surfaces independent of other surfaces.
Developments in the last ten years have shown methods for accounting
for indirect lighting in scenes. One method developed is known as the
radiosity method, in which an environment is discretized and energy
transfers are calculated over the discretization by solving a large
system of linear equations.
The solutions of the radiosity method are highly dependent on the
discretization used. All methods used to generate these
discretizations have to date depended upon the scene being formed of
polygonal faces. However, these are often not the most efficient
representations of the objects. The meshing process usually only
takes geometry into account, making shadow edges awkward to deal
with.
The method presented here allows non-polygonal objects to be used
as input to a progressive radiosity method, without having to provide
a polygonal representation. The method automatically generates a
discretization that is sensitive to lighting changes, not to
geometric constraints. One effect of this is that higher order
discontinuities in surface lighting are detected and rendered without
user intervention.



Title: PHOTO-REALISTIC IMAGE GENERATION TECHNIQUES
Author: SHAH, BINA CHUNILAL
School: UNIVERSITY OF SUSSEX (UNITED KINGDOM) (0545)
Degree: DPHIL Date: 1992 pp: 140
Source: DAI-C 55/01, p. 236, Spring 1994
Subject: COMPUTER SCIENCE (0984)
Location: LIBRARIAN, UNIVERSITY OF SUSSEX, BRIGHTON, BN1
9QT, UNITED KINGDOM

Abstract: As technology improves, vast demands are made in producing
photo-realistic images in computer graphics. However, the
algorithms--ray tracing and radiosity--used to produce these images
require large computational power which would take many hours to
execute in a uniprocessor system. Thus, algorithms need to be
developed which can be executed efficiently in multiprocessor systems
to achieve interactive rendering. This thesis presents some novel
algorithmic approaches to improve the performance of ray tracing
algorithms.
Adaptive antialiasing algorithms based on object space edge
detection and voxel antialiasing techniques have been presented. The
former method improves the overall rendering performance by more than
65% of the image rendered using traditional super sampling method,
whereas the latter method was found unsuitable for octrees due to the
non-uniformity of the voxels. Unlike the previous adaptive
antialiasing algorithms, in the methods presented, the choice on
whether to subdivide a pixel is made independently of the
neighbouring pixel's intensity information. This pixel independence
nature of the algorithm makes it well suited for implementation in
multiprocessing environment.
Multiprocessing systems come with a limited local memory size.
Often it is not possible to fit the whole database and data structure
in a single processor memory. It is also known that to render a
pixel, only a small fraction of the database is accessed and these
data accesses are mainly in the upper level of the octree. Hence, a
dynamic octree building algorithm has been proposed which builds only
the upper level of the octree at start-up and the lower levels are
built during the rendering process when required. Also a hierarchical
grid-octree structure has been introduced, which further reduces the
storage costs and also improves the management of data structure and
data structure construction costs, when rendering dynamic scenes.
A diffuse ray tracing algorithm, based on radiosity methods, has
been discussed to improve the scene realism by adding diffuse effects
to the ray tracing algorithm, without losing the view independence
nature of the radiosity algorithm. Ray tracing methods are used to
determine the visible pairs of surfaces as ray tracing provides the
flexibility of modelling scenes with a range of geometric primitives
and it also provides a number of optical effects.



Title: ANALYSIS OF RADIOSITY TECHNIQUES IN COMPUTER GRAPHICS
Author: KWOK, BERNARD
School: YORK UNIVERSITY (CANADA) (0267) Degree: MSC Date: 1992
pp: 147
Source: MAI 31/03, p. 1269, Fall 1993
Subject: COMPUTER SCIENCE (0984)
ISBN: 0-315-72845-0

Abstract: The radiosity technique currently produces some of the
most realistic images in computer graphics. We will discuss the
basics behind this technique and analyze some of the major
algorithmic approaches taken to tackle problems in modeling,
simulation, rendering, and animation of scenes, with the emphasis on
form factor and energy transfer algorithms. Some important ideas have
been incorporated to produce a hybrid radiosity-ray casting
progressive refinement program, a scene modeling preprocessing
program, and a scene walk-through / rendering program. The result has
been a package which takes a polygonally meshed input scene, and
produces a scene with physically based illumination, which may be
'walked through'. Some experimental results for the implementation
will be presented for comparative analysis of techniques presented.



Title: RADAR CROSS SECTION OF COMPLEX RADAR TARGETS IN REAL TIME
[SECCION RECTA DE BLANCOS RADAR COMPLEJOS EN TIEMPO REAL]
Author: RIUS CASALS, JUAN MANUEL
School: UNIVERSITAT POLITECNICA DE CATALUNYA (SPAIN) (5874)
Degree: DRING Date: 1991 pp: 355
Source: DAI-C 54/01, p. 322, Spring 1993
Language: SPANISH
Subject: ENGINEERING, ELECTRONICS AND ELECTRICAL (0544)
ISBN: 84-7653-182-6
Publisher: EDICIONS DE LA UNIVERSITAT POLITECNICA DE
CATALUNYA, AVDA. DR. GREGORIO MARANON, S/N
E-08028 BARCELONA, SPAIN

Abstract: Numerical computation of RCS of large and complex radar
targets is based on high-frequency approximations: the target is
usually modelled in terms of facets and wedges, so that physical
optics and physical theory of diffraction can be respectively applied
to each facet and wedge. These classical techniques require very long
CPU run time on powerful computers.
This Thesis presents a new and original approach to compute RCS
in real-time with a graphic workstation using the hardware
capabilities of a 3-D graphics accelerator. Real-time computation is
achieved through graphical processing of an image of the target
present at the workstation screen. First-order reflections are
obtained by rendering of the target with a local illumination
algorithm, and multiple scattering with a global illumination one.
A computer aided design package for geometric modeling of solids
I-DEAS has been used for modeling target geometry. The target is
described as a collection of parametric surfaces, defined with
two-dimensional NURBS (non-uniform rational B-splines).
The following high-frequency scattering phenomena are considered
by the real-time graphical processing approach: (1) Reflection at
perfectly conducting surfaces by physical optics approximation. (2)
Reflection at coated surfaces by physical optics and IBC
approximations. (3) Diffraction at edges by method of equivalent
currents using PTD diffraction coefficients. (4) Multiple reflections
between surfaces by radiosity global illumination method.
Graphical processing has the following advantages over classical
techniques: (1) Hardware graphics accelerator removes hidden surfaces
and edges so that they do not contribute to surface or line
integrals. (2) Evaluation of surface and line integrals (PO and MEC)
independent of target complexity. (3) CPU time and RAM requirements
independent of target electrical size and complexity. (4) Real-time
computation if hardware graphics accelerator is used. (5) Target can
be modelled by parametric NURB surfaces, requiring less mass storage
memory that the faceting approach, and adjusting more accurately to
the real target surface. (6) Real-time RCS computing software can be
integrated with CAD geometric modeling package, thus providing an
efficient tool for interactive modeling, design and analysis of
aircraft with RCS specifications.
High-frequency RCS prediction by graphical processing techniques
has been fully validated for simple objects and complex radar
targets.