Technical Reports

The ICICS/CS Reading Room

1995 UBC CS Technical Report Abstracts

TR-95-01 Buffer Sharing Schemes for Continuous-Media Systems, January 1995 Dwight J. Makaroff and Raymond T. Ng, 28 pages

Buffer management in continuous-media systems is a frequently studied topic. One of the most interesting recent proposals is the idea of buffer sharing for concurrent streams. As analyzed in~\cite{ny94}, by taking advantage of the temporal behaviour of concurrent streams, buffer sharing can lead to a 50\% savings in total buffer space. In this paper, we study how to actually implement buffer sharing. To this end, we develop the CES Buffer Sharing scheme that is very efficient to implement, and that permits savings asymptotically very close to the ideal savings predicted by the analysis in~\cite{ny94}. We show that the CES scheme can operate effectively under varying degrees of disk utilizations, and during transition periods when the number of concurrent streams changes. We also demonstrate how the scheme can be further improved, particularly for situations when the number of concurrent streams is small. In ongoing work, we will integrate the proposed scheme into a distributed continuous-media file system which is under development at the University of British Columbia.

TR-95-02 Geometric and Computational Aspects of Manufacturing Processes, January 1995 Prosenjit K. Bose, 103 pages

Two of the fundamental questions that arise in the manufacturing industry concerning every type of manufacturing process are:

1) Given an object, can it be built using a particular process? 2) Given that an object can be built using a particular process, what is the best way to construct the object?

The latter question gives rise to many different problems depending on how best is qualified. We address these problems for two complimentary categories of manufacturing processes: rapid prototyping systems and casting processes. The method we use to address these problems is to first define a geometric model of the process in question and then answer the questions on that model.

In the category of rapid prototyping systems, we concentrate on stereolithography, which is emerging as one of the most popular rapid prototyping systems. We model stereolithography geometrically and then study the class of objects that admit a construction in this model. For the objects that admit a construction, we find the orientations that allow a construction of the object.

In the category of casting processes, we concentrate on gravity casting and injection molding. We first model the process and its components geometrically. We then characterize and recognize the objects that can be formed using a re-usable two-part cast. Given that a cast of an object can be formed, we determine a suitable location for the pin gate, the point from which liquid is poured or injected into a mold. Finally, we compute an orientation of a mold that ensures a complete fill and minimizes the number of venting holes for molds used in gravity casting processes.

TR-95-03 No Quadrangulation is Extremely Odd, January 1995 Prosenjit Bose and Godfried Toussaint, 17 pages

Given a set S of n points in the plane, a quadrangulation of S is a planar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the subdivision (except possibly the outer face) is a quadrilateral. We show that S admits a quadrangulation if and only if S does not have an odd number of extreme points. If S admits a quadrangulation, we present an algorithm that computes a quadrangulation of S in O(n log n) time even in the presence of collinear points. If S does not admit a quadrangulation, then our algorithm can quadrangulate S with the addition of one extra point, which is optimal. We also provide an \Omega(n \log n) time lower bound for the problem. Finally, our results imply that a k-angulation of a set of points can be achieved with the addition of at most k-3 extra points within the same time bound.

TR-95-04 Performance Measures for Constrained Systems, February 1995 Kees van den Doel and Dinesh K. Pai, 27 pages

We present a geometric theory of the performance of robot manipulators, applicable to systems with constraints, which may be non-holonomic. The performance is quantified by a geometrical object, the induced metric tensor, from which scalars may be constructed by invariant tensor operations to give performance measures. The measures thus defined depend on the metric structure of configuration and work space, which should be chosen appropriately for the problem at hand. The generality of this approach allows us to specify a system of joint connected rigid bodies with a large class of metrics. We describe how the induced metric can be computed for such a system of joint connected rigid bodies and describe a MATLAB program that allows the automatic computation of the performance measures for such systems. We illustrate these ideas with some computations of measures for the SARCOS dextrous arm, and the Platonic Beast, a multi-legged walking machine.

TR-95-05 Rigidity Checking of 3D Point Correspondences Under Perspective Projection, March 1995 Daniel P. McReynolds and David G. Lowe, 39 pages

An algorithm is described which rapidly verifies the potential rigidity of three dimensional point correspondences from a pair of two dimensional views under perspective projection. The output of the algorithm is a simple yes or no answer to the question ``Could these corresponding points from two views be the projection of a rigid configuration?'' Potential applications include 3D object recognition from a single previous view and correspondence matching for stereo or motion over widely separated views. Our analysis begins with the observation that it is often the case that two views cannot provide an accurate structure-from-motion estimate because of ambiguity and ill- conditioning. However, it is argued that an accurate yes/no answer to the rigidity question is possible and experimental results support this assertion with as few as six pairs of corresponding points over a wide range of scene structures and viewing geometries. Rigidity checking verifies point correspondences by using 3D recovery equations as a matching condition. The proposed algorithm improves upon other methods that fall under this approach because it works with as few as six corresponding points under full perspective projection, handles correspondences from widely separated views, makes full use of the disparity of the correspondences, and is integrated with a linear algorithm for 3D recovery due to Kontsevich. The rigidity decision is based on the residual error of an integrated pair of linear and nonlinear structure-from-motion estimators. Results are given for experiments with synthetic and real image data. A complete implementation of this algorithm is being made publicly available.

TR-95-06 The UBC Distributed Continuous Media File System: Internal Design of Server, March 1995 Dwight J., Hutchinson, Norman C. Makaroff and Gerald W. Neufeld, 21 pages

This report describes the internal design of the UBC Distributed Continuous Media File Server as of April 1995. The most significant unique characteristic of this system is its approach to admission control which utilizes the time-varying requirements of the variable bit-rate data streams currently admitted into the system to properly allocate disk resources. The structure of the processes which implement the file server are described in detail as well as the communication between client processes and server processes. Each major client interface interaction is covered, as well as the detailed operation of the server in response to client requests. Buffer management considerations are introduced as they affect the admission control and disk operations. We conclude with the status of the implementation and plans for completion of the design and implementation. This document provides a snapshot of our design which has not yet been fully implemented and we expect to see significant evolution of the design as the implementation proceeds.

TR-95-07 Real Time Threads Interface, March 1995 David Finkelstein, Norman C. Hutchinson and Dwight J. Makaroff, 22 pages

The Real Time Threads package (abbreviated RT Threads) provides a user-level, preemptive kernel running inside a single address space (e.g., within a UNIX process). RT Threads implements thread management, synchronization, and communication functions, including communication between RT Threads environments (i.e., with different address spaces, possibly on different machines and different architectures). Threads are scheduled using a real-time, multi-priority, preemptive scheduling algorithm. Each thread is scheduled on the basis of its modifiable scheduling attributes: starting time, priority and deadline. No thread is scheduled before its starting time. Schedulable threads (i.e., threads whose starting time has passed) are scheduled on a highest priority first basis. Schedulable threads of equal priority use an earliest deadline first (EDF) scheduling policy. An RT Threads environment is cooperative in the sense that memory is shared among all threads, and each thread runs to completion unless preempted on the basis of priorities and deadlines. Alternate scheduling policies, such as time slicing, can be implemented at the application level using the scheduling mechanisms provided by RT Threads. This report describes the interface to the RT Threads package.

TR-95-09 Reflectance and Shape from a Rotating Object, April 1995 Jiping Lu and Jim Little, 26 pages

In this paper we show that the reflectance function of a rotating object illuminated under a collinear light source (where the light source lies on or near the optical axis) can be estimated from the image sequence of the object and applied to surface recovery. We first calculate the 3D locations of some singular points from the image sequence, and extract the brightness values of these singular points during the object rotation to estimate the surface reflectance function. Then we use the estimated reflectance function for surface recovery from the images of the rotating object. Two subprocedures are used in surface recovery. The first subprocedure computes the depth around a point of known depth and surface orientation by using first-order Taylor series approximation. The other computes the surface orientation of a surface point from its image brightness values in the two different images by applying the estimated reflectance function. Starting from surface points of known depth values and surface orientations and iteratively applying the two subprocedures, the surface depth and orientation are recovered simultaneously over the whole object surface. The experimental results on real image sequences of both matte and specular surfaces show that the technique is feasible and robust.

TR-95-11 Numerical Simulations of Semiconductor Devices by Streamline-Diffusion Methods, April 1995 Xunlei Jiang, 153 pages

Theoretical and practical aspects of the design and implementation of the streamline-diffusion (SD) method for semiconductor device models are explored systematically. Emphasis is placed on the hydrodynamic (HD) model, which is computationally more challenging than the drift-diffusion (DD) model, but provides some important physical information missing in the DD model.

We devise a non-symmetric SD method for device simulations. This numerical method is uniformly used for the HD model (including a proposed simplification (SHD)) and the DD model. An appropriate SD operator is derived for the general non-symmetric convection-diffusion system. Linear stability analysis shows that our proposed numerical method is stable if the system can be symmetrized. Stability arguments and numerical experiments also suggest that the combination of the method of lines and the semi-discrete SD method may not be appropriate for the transient problem, a fact which often has been ignored in the literature.

An efficient method, consistent with the SD method used for conservation laws, is developed for the potential equation. The method produces a more accurate electric field than the conventional Galerkin method. Moreover, it solves for the potential and electric field in a decoupled manner.

We apply our numerical method to the diode and MESFET devices. Shocks for the diode in one and two space dimensions and the electron depletion near the gate for the MESFET in two space dimensions are simulated. Model comparisons are implemented. We observe that the difference in solutions between the HD and DD models is significant. The solution discrepancy between the full HD and SHD models is almost negligible in MESFET simulation, as in many other engineering applications. However, an exceptional case is found in our experiments.

TR-95-12 Forward Dynamics, Elimination Methods, and Formulation Stiffness in Robot Simulation, April 1995 Dinesh Pai Uri Ascher and Benoit Cloutier, 15 pages

The numerical simulation problem of tree-structured multibody systems, such as robot manipulators, is usually treated as two separate problems: (i) the forward dynamics problem for computing system accelerations, and (ii) the numerical integration problem for advancing the state in time. The interaction of these two problems can be important and has led to new conclusions about the overall efficiency of multibody simulation algorithms [ClPaAs95]. In particular, the fastest forward dynamics methods are not necessarily the most numerically stable, and in ill-conditioned cases may slow down popular adaptive step-size integration methods. This phenomenon is called "formulation stiffness".

In this paper, we first unify the derivation of both the composite rigid body method [WalkerOrin82] and the articulated-body method [Featherstone83,Featherstone87] as two elimination methods to solve the same linear system, with the articulated body method taking advantage of sparsity. Then the numerical instability phenomenon for the composite rigid body method is explained as a cancellation error that can be avoided, or at least minimized, when using an appropriate version of the articulated body method. Specifically, we show that the articulated-body method is better suited to deal with certain types of ill-conditioning than the composite rigid body method. The unified derivation also clarifies the underlying linear algebra of forward dynamics algorithms and is therefore of interest in its own accord.

TR-95-13 A Simple Proof Checker for Real-Time Systems, June 1995 Catherine Leung, 193 pages

This thesis presents a practical approach to verifying real-time properties of VLSI designs. A simple proof checker with built-in decision procedures for linear programming and predicate calculus offers a pragmatic approach to verifying real-time systems in return for a slight loss of formal rigor when compared with traditional theorem provers. In this approach, an abstract data type represents the hypotheses, claim, and pending proof obligations at each step. A complete proof is a program that generates a proof state with the derived claim and no pending obligations. The user provides replacements for obligations and relies on the proof checker to validate the soundness of each operation. This design decision distinguishes the proof checker from traditional theorem provers, and enhances the view of ``proofs as programs''. This approach makes proofs robust to incremental changes, and there are few ``surprises'' when applying rewrite rules or decision procedures to proof obligations. A hand-written proof constructed to verify the timing correctness of a high bandwidth communication protocol was verified using this checker.

TR-95-14 Sequential Regularization Methods for Nonlinear Higher Index DAE's, July 1995 Uri M. Ascher and Ping Lin, 25 pages

Sequential regularization methods relate to a combination of stabilization methods and the usual penalty method for differential equations with algebraic equality constraints. The present paper extends an earlier work \cite{al} to nonlinear problems and to DAEs with index higher than 2. Rather than having one ``winning'' method, this is a class of methods from which a number of variants are singled out as being particularly effective methods in certain circumstances.

We propose sequential regularization methods for index-2 and index-3 DAEs, both with and without constraint singularities. In the case of no constraint singularity we prove convergence results. Numerical experiments confirm our theoretical predictions and demonstrate the viability of the proposed methods. The examples include constrained multibody systems.

TR-95-15 The Creation, Presentation and Implications of Selected Auditory Illusions, July 1995 Scott Flinn and Kellogg S. Booth, 43 pages

This report describes the initial phase of a project whose goal is to produce a rich acoustic environment in which the behaviour of multiple independent activities is communicated through perceptually distinguishable auditory streams. While much is known about the perception of isolated auditory phenomena, there are few general guidelines for the selection of auditory elements that can be composed to achieve a display that is effective in situations where the ambient acoustic conditions are uncontrolled. Several auditory illusions and effects are described in the areas of relative pitch discrimination, perception of auditory streams, and the natural association of visual and auditory stimuli. The effects have been evaluated informally through a set of demonstration programs that have been presented to a large and varied audience. Each auditory effect is introduced, suggestions for an effective demonstration are given, and our experience with the demonstration program is summarized. Implementation issues relevant to the reproduction of these effects on other platforms are also discussed. We conclude by describing several experiments aimed at resolving issues raised by our experience with these effects.

TR-95-16 Coordinating Heterogeneous Time-Based Media Between Independent Applications, July 1995 Scott Flinn, 42 pages

This report discusses the requirements and design of an event scheduler that facilitates the synchronization of independent, heterogeneous media streams. The work is motivated by the synchronization requirements of multiple, periodic, logically independent auditory streams, but extends naturally to include time-based media of arbitrary type. The scheduler design creates a framework within which existing synchronization techniques are composed to coordinate the presentation activities of cooperating or independent application programs. The scheduler is especially effective for the presentation of repetitive sequences, and guarantees long term synchronization with a hardware clock, even when scheduler capacity is temporarily exceeded on platforms lacking real time system support. The implementations of the scheduler and of several application programs, class libraries and other tools designed to use or support it are described in detail.

TR-95-17 XTP Application Programming Interface, July 1995 Rol Mechler, and Gerald W. Neufeld, 24 pages

The Xpress Transport Protocol (XTP) is a lightweight transport protocol intended for high-speed networks. High-speed networks provide bandwidths of 100 Mbps and beyond, enabling a new class of applications (e.g., multimedia). So as not to be a bottleneck in the delivery of data, a transport protocol must provide high performance. Features of XTP which enhance performance include implicit connection setup, sender driven acknowledgement, selective retransmission, fixed format word aligned packet structures and suitability for parallel implementation. Since the new generation of applications may require a variety of services from the transport layer, a transport protocol designed for high-speed networks should also be flexible enough to provide these services. XTP provides the mechanisms to allow applications to tailor the functionality of the protocol to their individual needs. In particular, XTP provides flow control, rate control and error control, the use of each being optional and orthogonal to the others. This report describes an Application Programming Interface designedfor a multi-threaded implementation of XTP. The API allows all XTP parameters to be set from the application level, and addresses the issue of performance by providing a mechanism for zero copy transmission and reception of data.

TR-95-18 Model Checking Partially Ordered State Spaces, July 1995 Scott Hazelhurst and Carl J. H. Seger, 31 pages

The state explosion problem is the fundamental limitation of verification through model checking. In many cases, representing the state space of a system as a lattice is an effective way of ameliorating this problem. The partial order of the state space lattice represents an information ordering. The paper shows why using a lattice structure is desirable, and why a quaternary temporal logic rather than a traditional binary temporal logic is suitable for describing properties in systems represented this way. The quaternary logic not only has necessary technical properties, it also expresses degrees of truth. This is useful to do when dealing with a state space with an information ordering defined on it, where in some states there may be insufficient or contradictory information available. The paper presents the syntax and semantics of a quaternary valued temporal logic.

Symbolic trajectory evaluation (STE) has been used to model check partially ordered state spaces with some success. The limitation of STE so far has been that the temporal logic used (a two-valued logic) has been restricted, whereas a more expressive temporal logic is often useful. This paper generalises the theory of symbolic trajectory evaluation to the quaternary temporal logic, which potentially provides an effective method of model checking an important class of formulas of the logic. Some practical model checking algorithms are briefly described and their use illustrated. This shows that not only can STE be used to check more expressive logics in principle, but that it is feasible to do so.

TR-95-19 A Shared 4-D Workspace, August 1995 Mir Ko, a and Peter Cahoon, 18 pages

A Shared four-dimensional workspace is a shared animation of three-dimensional databases. Since shared animated workspaces are important to many different types of users, a pilot project was undertaken to implement a shared, time varying workspace. This software permitted the give and take of control by users running the same application across an ATM fiber link running at 100 mbits/sec.

The project was divided into two parts. In the first phase, animation of three-dimensional databases in stereo was implemented. In the second phase, sharing of the animation across the ATM network was added.

This paper dicusses the interfaces to the program and presents outlines of implementations of the features in each of the project's two phases.

TR-95-20 On the Maximum Tolerable Noise for Reliable Computation by Formulas, September 1995 William Evans and Nicholas Pippenger, 16 pages

It is shown that if a formula is constructed from noisy 2-input NAND gates, with each gate failing independently with probability e, then reliable computation can or cannot take place according as e is less than or greater than e_0 = (3-sqrt(7))/4 = 0.08856....

TR-95-21 Verification of Benchmarks 17 and 22 of the IFIP WG10.5 Benchmark Circuit Suite, October 1995 Scott Hazelhurst and Carl J. H. Seger, 32 pages

This paper reports on the verification of two of the IFIP WG10.5 benchmarks --- the multiplier and systolic matrix multiplier. The circuit implementations are timed, detailed gate-level descriptions, and the specification is given using the temporal logic TLn, a quaternary-valued temporal logic. A practical, integrated theorem-proving/model checking system based on the compositional theory for TLn and symbolic trajectory evaluation is used to verify the circuits. A 64-bit version of multiplier circuit (Benchmark 17) containing approximately 28~000 gates takes about 18 minutes of computation time to verify. A 4 by 4, 32-bit version of the matrix multiplier (Benchmark 22) containing over 110~000 gates take about 170 minutes of computation time to verify. A significant timing error was discovered in this benchmark.

Keywords: symbolic trajectory evaluation, benchmarks, compositional verification, temporal logic, theorem proving.

TR-95-22 Optimal Algorithms to Embed Trees in a Point Set, October 1995 Prosenjit Bose, Michael McAllister and Jack Snoeyink, 11 pages

We present optimal Theta(n log n) time algorithms to solve two tree embedding problems whose solution previously took quadratic time or more: rooted-tree embeddings and degree-constrained embeddings. In the rooted-tree embedding problem we are given a rooted-tree T with n nodes and a set of n points P with one designated point p and are asked to find a straight-line embedding of T into P with the root at point p. In the degree-constrained embedding problem we are given a set of n points P where each point is assigned a positive degree and the degrees sum to 2n-2 and are asked to embed a tree in P using straight lines that respects the degrees assigned to each point of P. In both problems, the points of P must be in general position and the embeddings have no crossing edges.

TR-95-23 Pure versus Impure Lisp, October 1995 Nicholas Pippernger, 11 pages

The aspect of purity versus impurity that we address involves the absence versus presence of mutation: the use of primitives (RPLACA and RPLACD in Lisp, set-car! and set-cdr! in Scheme) that change the state of pairs without creating new pairs. It is well known that cyclic list structures can be created by impure programs, but not by pure ones. In this sense, impure Lisp is ``more powerful'' than pure Lisp. If the inputs and outputs of programs are restricted to be sequences of atomic symbols, however, this difference in computability disappears. We shall show that if the temporal sequence of input and output operations must be maintained (that is, if computations must be ``on-line''), then a difference in complexity remains: for a pure program to do what an impure program does in n steps, O(n log n) steps are sufficient, and in some cases Omega(n log n) steps are necessary.

TR-95-24 Three-Dimensional Analysis of Scoliosis Surgery Using Stereo Photogrammetry, December 1995 Kellogg S. Booth, Stanley B. Jang, Chris W. Reily and Bonita J. Sawatzky

Scoliosis is a deformity characterized by coronal, sagittal and axial rotation of the spine. Surgical instrumentation (metal pins and rods) and eventual fusion of the spine are required in severe cases. Assessment of the deformity requires enough accuracy to allow proactive planning of individual interventions or implant designs. Conventional 2-D radiography and even 3-D CT scanning do not provide this, but our new stereophotogrammetric analysis and 3-D visualization tools do. Stereophoto pairs taken at each stage of the operation and robust statistical techniques can be used to determine rotation, translation, goodness of fit, and overall spinal contour before, during and after the surgical instrumentation.

Novel features of our software include 3-D digitizing software that improves existing stereophotogrammetry methods, robust statistical methods for measuring 3-D deformity and estimating errors, full 3-D visualization of spinal deformities with optional head-coupled stereo ("fish tank virtual reality"), full integration with commercial animation software, use of consumer PhotoCD technology that significantly lowers costs for data collection and storage while increasing accuracy, and simultaneous 3-D viewing and control at remote locations over high-speed ATM networks.

TR-95-25 Separating Reflection Functions for Linear Radiosity, December 1995 Alain Fournier

Classic radiosity assumes diffuse reflectors in order to consider only pair-wise exchanges of light between elements. It has been previously shown that one can use the same system of equations with separable bi-directional reflection distrubution functions (BRDFs), that is BRDFs that can be put in the form of a product of two functions, one of the incident direction and one of the reflected direction.

We show here that this can be easily extended to BRDFs that can be approximated by sums of such terms. The classic technique of Singular Value Decomposition (SVD) can be used to compute those terms given an analytical or experimental BRDF. We use the example of the traditional Phong model for specular-like reflection to extract a separable model, and show the results in terms of closeness to ordinary Phong shading. We also show an example with experimental BRDF data. Further work will indicate whether the quality of linear radiosity images will be improved by this modification.

TR-95-26 From Local to Global Illumination and Back, December 1995 Alain Fournier

The following being musings about illumination problems and illumination answers, more particularly about the evolution and the interplay between local and global illumination concerns.

TR-95-27 Vide Hoc: A Visualization for Homogenous Coordination, December 1995 Robert R. Lewis

VideHoc is an interactive graphical program that visualizes two-dimensional homogeneous coordinates. Users manipulate data in one of four views and all views are dynamically updated to reflect the change.

TR-95-28 Light-Driven Global Illumination with a Wavelet Representation of Light Transport, December 1995 Robert R. Lewis and Alain Fournier

We describe the basis of the work he have currently under way to implement a new rendering algorithm called "light-driven global illumination". This algorithm is a departure from conventional raytracing and radiosity renderers which addresses a number of deficiencies intrinsic to those approaches.

TR-95-29 Union of Spheres Model for Volumetric Data, December 1995 Vishwa Ranjan and Alain Fournier

A stable representation of an object means that the representation is unique, is independent of the sampling geometry, resolution, noise, and other small distortions in the data, and is instead linked to the shape of the object. Stable representations help characterize shapes for comparison or recognition; skeletal (or medial axis) and volumetric primitive models have been popular in vision for the same reason. Piecewise polyhedral representations, e.g., tetrahedra, and voxel representations, e.g., octrees, generally tend to be unstable. We propose a representation for 3D objects based on the set union of overlapping sphere primitives. This union of spheres (UoS) model has some attractive properties for computer graphics, computational vision, and scientific visualization.

TR-95-30 Shape Transformations Using Union of Spheres, December 1995 Vishwa Ranjan and Alain Fournier

Shape interpolation is the process of transforming continuously one object into another. This is useful in applications such as object recognition, object registration and computer animation. Unfortunately, "good" shape interpolation is as ill-defined as "shape" itself. To be able to control the process in a useful way, we need a representation for the objects using primitives which capture at least some aspects of their shape, with methods to convert other representations to this one. We present here a method to interpolate between two objects represented as a union of spheres. We briefly describe the representation and its properties, and show how to use it to interpolate. Once a distance metric between the spheres is defined (we show different metric producing controlled effects), the algorithm optimally matches the spheres in the two models using a bipartite graph. The transformation then consists in interpolating between the matched spheres. If the union of spheres has been simplified, the other spheres are matched as a function of their positions within their representative cluster. Examples are shown and discussed with two- and three-dimensional objects. The results show that the union of spheres helps capture some notion of shape, and helps to automatically match and interpolate shapes.

TR-95-31 Multiresolution Surface Approximation, December 1995 David R. Forsey and David Wong

This paper presents a method for automatically generating a hierarchical B-spline surface from an initial set of control points. Given an existing mesh of control points a mesh with half the resolution is constructed by simultaneously approximating the finer mesh while minimizing a smoothness constraint using weighted least squares. Curvature measures are used to identify features that need only be represented in the finer mesh. The resulting hierarchical surface accurately and economically reproduces the original mesh, is free from excessive undulations in the intermediate levels and produces a multiresolution representation suitable for animation and interactive modelling.

TR-95-32 Pasting Spline Surfaces, December 1995 C. Banghiel, Richard H. Bartels and David R. Forsey

Details can be added to spline surfaces by applying displacement maps. However, the computational intensity of displacement mapping prevents its useful for interactive design. In this paper we explore a form of simulated displacement that can be used for interactive design by providing a preview of true displacements at low computational cost.

TR-95-33 Surface Fitting with Hierarchical Splines, December 1995 David R. Forsey and Richard H. Bartels

We consider the fitting of tensor product parametric spline surfaces to gridded data. The continuity of the surface is provided by the basis chosen. When tensor product splines are used with gridded data, the surface fitting problem decomposes into a sequence of curve fitting processes, making the computations particularly efficient. The use of a hierarchical representation for the surface adds further efficiency by adaptively decomposing the fitting process into subproblems involving only a portion of the data. Hierarchy also provides a means of storing the resulting surface in a compressed format. Our approach is compared to multiresolution analysis and the use of wavelets.

TR-95-34 Regularization Methods for Differential Equations and Their Numerical Solution, December 1995 Ping Lin, 168 pages

The objectives of the thesis are to propose and to investigate approximate methods for various differential equations with or without constraints. Most attention is paid to ordinary and partial differential equations with constraints (where the solution is know to lie in an explicitly defined invariant manifold). We propose and analyze a regularization method called sequential regularization method (SRM) and its numerical approximation. A very important improvement of the SRM over usual regularization methods is that the problem after regularization need not be stiff. Hence explicit difference schemes can be used to avoid solving nonlinear systems. This makes the computation much simpler. The method is applied in several application fields such as mechanical constrained multi-body systems, nonstationary incompressible Navier-Stokes equations which is an example of partial differential equations with constraints (PDAE), and miscible displacement in porous media in reservoir simulation. Improvements over stabilization methods that stabilize the invariant manifold over long time intervals and extra benefits for these applied problems are also achieved.

We finally discuss the numerical solution of several singular perturbation problems which come from many applied areas and regularized problems. Uniformly convergent schemes with respect to the perturbation parameter are constructed and proved. A spurious solution phenomenon for an upwinding scheme is analyzed.

TR-95-35 Illumination Problems in Computer Augmented Reality, January 31, 1994 Alain Fournier, 22 pages

The ability to merge a real video image (RVI) with a computer-generated image (CGI) enhances the usefulness of both. To go beyond "cut and paste" and chroma-keying, and merge the two images successfully, one must solve the problems of common viewing parameters. common visibility and common illumination. The result can be dubbed Computer Augmented Reality (CAR). The solution needs contributions from both computer graphics and computer vision. The problems of common illumination are especially challenging, because they test our understanding and practice of shadow and global illumination computation. In this paper we will describe and illustrate work in our laboratory where the emphasis is on extracting illumination information from real images and computing the common illumination between the real and the computer generated scene.

If you have any questions or comments regarding this page please send mail to