bluuebunny/crossref_metadata_2025 huggingface dataset:
Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes
Authors: Kaufman Arie
Published: November 2005

Three-dimensional (3D) scan-conversion algorithms
, that scan-convert 3D parametric objects into their discrete voxelmap representation within a Cubic Frame Buffer (CFB), are presented. The parametric objects that are studied include Bezier form of cubic parametric curves, bicubic parametric surface patches, and tricubic parametric volumes. The converted objects in discrete 3D space maintain pre-defined application-dependent connectivity and fidelity requirements.The algorithms introduced here emply third-order forward difference techniques. Efficient versions of the algorithms based on first-order decision mechanisms, which employ only integer arithmetic, are also discussed. All algorithms are incremental and use only simple operations inside the inner algorithm loops. They perform scan-conversion with computational complexity which is linear in the number of voxels written to the CFB. All the algorithms have been implemented as part of the
CUBE Architecture
, which is a voxel-based system for 3D graphics.
Real-time manipulation of texture-mapped surfaces
Authors: Oka Masaaki , Tsutsui Kyoya , Ohba Akio , Kurauchi Yoshitaka , Tago Takashi
Published: November 2005

A system for real-time texture mapping was constructed, Here, "real-time" means that the system reacts to changes in parameter values which define the shape of surfaces and the viewing point that are given by its operator 30 times per second. This real-time processing enables interactive manipulation of texture-mapped free-form surfaces and various application software has been developed taking advantage of this ability. The system owes its performance to a new algorithm for texture mapping which is based on a newly proposed approximation scheme of mapping functions. In this scheme, a mapping function from the texture plane into the output screen is approximated by a linear function on each of the small regions which form the texture plane altogether. The algorithm is very simple and applicable to any smooth surface. It is especially efficient when implemented by a special-purpose hardware.
Elastically deformable models
Authors: Terzopoulos Demetri , Platt John , Barr Alan , Fleischer Kurt
Published: November 2005

The theory of elasticity describes deformable materials such as rubber, cloth, paper, and flexible metals. We employ elasticity theory to construct differential equations that model the behavior of non-rigid curves, surfaces, and solids as a function of time. Elastically deformable models are active: they respond in a natural way to applied forces, constraints, ambient media, and impenetrable obstacles. The models are fundamentally dynamic and realistic animation is created by numerically solving their underlying differential equations. Thus, the description of shape and the description of motion are unified.
Rendering antialiased shadows with depth maps
Authors: Reeves William T. , Salesin David H. , Cook Robert L.
Published: November 2005

We present a solution to the aliasing problem for shadow algorithms that use depth maps. The solution is based on a new filtering technique called percentage closer filtering. In addition to antialiasing, the improved algorithm provides soft shadow boundaries that resemble penumbrae. We describe the new algorithm in detail, demonstrate the effects of its parameters, and analyze its performance.
The history of versaCAD
Authors: Machover Carl
Published: November 2005

For this issue's column, I'm delighted to bring you some reminiscences courtesy of Tom Lazear, President of Archway Systems. Tom wrote one of the first (Gwen Bell of the Computer Museum cautioned me never to claim anything as the first!) PC-CAD (computer-aided design) systems. T-Square, for the Terak PC, was subsequently adapted as CADapple for the ApplellE, and preceded AutoCAD (which was written for the IBM PC).Before presenting Tom's article, I want to remind you of ongoing Pioneer opportunities. Pioneer membership requires at least 20 years in the field, which means that if you were involved in computer graphics by 1981, you're now eligible for membership! Let's hear from you.
A parallel algorithm for polygon rasterization
Authors: Pineda Juan
Published: November 2005

A parallel algorithm for the rasterization of polygons is presented that is particularly well suited for 3D Z-buffered graphics implementations. The algorithm represents each edge of a polygon by a linear
edge function
that has a value greater than zero on one side of the edge and less than zero on the opposite side. The value of the function can be interpolated with hardware similar to hardware required to interpolate color and Z pixel values. In addition, the edge function of adjacent pixels may be easily computed in parallel.
The
coefficients of the "Edge function" can be computed from floating point endpoints in such a way that sub-pixel precision of the endpoints can be retained in an elegant way.
The triangle processor and normal vector shader
Authors: Deering Michael , Winner Stephanie , Schediwy Bic , Duffy Chris , Hunt Neil
Published: November 2005

Current affordable architectures for high-speed display of shaded 3D objects operate orders of magnitude too slowly. Recent advances in floating point chip technology have outpaced polygon fill time, making the memory access bottleneck between the drawing processor and the frame buffer the most significant factor to be accelerated. Massively parallel VLSI system have the potential to bypass this bottleneck, but to date only at very high cost. We describe a new more affordable VLSI solution. A pipeline of
triangle processors
rasterizes the geometry, then a further pipeline of
shading processors
applies Phong shading with multiple light sources. The triangle processor pipeline performs 100 billion additions per second, and the shading pipeline performs two billion multiplies per second. This allows 3D graphics systems to be built capable of displaying more than one million triangles per second. We show the results of an anti-aliasing technique, and discuss extensions to texture mapping, shadows, and environment maps.
Subanosecond pixel rendering with million transistor chips
Authors: Gharachorloo Nader , Gupta Satish , Hokenek Erden , Balasubramanian Peruvemba , Bogholtz Bill , Mathieu Christian , Zoulas Christos
Published: November 2005

The desire for higher performance and higher resolution continuously increases the pixel update rates needed in high performance graphics systems. The increasing density of memory chips on the other hand reduces the pixel update rate that can be provided by the frame buffer. We present the design of a VLSI chip and a graphics system that can sustain sub-nanosecond pixel rendering rates for three-dimensional polygons and can be used to render about a million Z-Buffered and Gourard shaded polygons per second. The chip has been designed at the IBM Research Division's Thomas J. Watson Research Center.
V-buffer
Authors: Upson Craig , Keeler Michael
Published: November 2005

This paper presents rendering techniques that use volumes as the basic geometric primitives. It defines data structures composed of numerous subvolumes, in excess of 100,000. Over each subvolume, a scalar field describes the variation of some physical quantity. The two rendering methods described herein assume a trilinear variation of this scalar field within each volume element, unlike voxel-based techniques that assume a constant value for each subvolume. The result is a higher order approximation of the structures within the volume. In addition, solid texture mapping, atmospheric attenuation, and transfer functions relating the dynamic range of the scalar field to color and opacity are used to isolate important data features. The result is a new method for the visualization of three-dimensional data resulting from numerical simulations and observations of natural phenomena. This method continuously covers the gap between surface-based and voxel-based techniques.
Volume rendering
Authors: Drebin Robert A. , Carpenter Loren , Hanrahan Pat
Published: November 2005

A technique for rendering images of volumes containing mixtures of materials is presented. The shading model allows both the interior of a material and the boundary between materials to be colored. Image projection is performed by simulating the absorption of light along the ray path to the eye. The algorithms used are designed to avoid artifacts caused by aliasing and quantization and can be efficiently implemented on an image computer. Images from a variety of applications are shown.
A progressive refinement approach to fast radiosity image generation
Authors: Cohen Michael F. , Chen Shenchang Eric , Wallace John R. , Greenberg Donald P.
Published: November 2005

A reformulated radiosity algorithm is presented that produces initial images in time linear to the number of patches. The enormous memory costs of the radiosity algorithm are also eliminated by computing form-factors on-the-fly. The technique is based on the approach of rendering by progressive refinement. The algorithm provides a useful solution almost immediately which progresses gracefully and continuously to the complete radiosity solution. In this way the competing demands of realism and interactivity are accommodated. The technique brings the use of radiosity for interactive rendering within reach and has implications for the use and development of current and future graphics workstations.
A study in interactive 3-D rotation using 2-D control devices
Authors: Chen Michael , Mountford S. Joy , Sellen Abigail
Published: November 2005

This paper describes and evaluates the design of four virtual controllers for use in rotating three-dimensional objects using the mouse. Three of four of these controllers are "new" in that they extend traditional direct manipulation techniques to a 3-D environment. User performance is compared during simple and complex rotation tasks. The results indicate faster performance for complex rotations using the new continuous axes controllers compared to more traditional slider approaches. No significant differences in accuracy for complex rotations were found across the virtual controllers.A second study compared the best of these four virtual controllers (the Virtual Sphere) to a control device by Evans, Tanner and Wein. No significant differences either in time to complete rotation task or accuracy of performance were found. All but one subject indicated they preferred the Virtual Sphere because it seemed more "natural".
Harnessing chaos for image synthesis
Authors: Barnsley Michael F. , Jacquin Arnaud , Malassenet Francois , Reuter Laurie , Sloan Alan D.
Published: November 2005

Chaotic dynamics can be used to model shapes and render textures in digital images. This paper addresses the problem of how to model geometrically shapes and textures of two dimensional images using iterated function systems. The successful solution to this problem is demonstrated by the production and processing of synthetic images encoded from color photographs. The solution is achieved using two algorithms: (1) an interactive geometric modeling algorithm for finding iterated function system codes; and (2) a random iteration algorithm for computing the geometry and texture of images defined by iterated function system codes. Also, the underlying mathematical framework, where these two algorithms have their roots, is outlined. The algorithms are illustrated by showing how they can be used to produce images of clouds, mist and surf, seascapes and landscapes and even faces, all modeled from original photographs. The reasons for developing iterated function systems algorithms include their ability to produce complicated images and textures from small databases, and their potential for highly parallel implementation.
Plant models faithful to botanical structure and development
Authors: de Reffye Phillippe , Edelin Claude , Françon Jean , Jaeger Marc , Puech Claude
Published: November 2005

Some very impressive results have been obtained in the past few years in plants and trees image synthesis. Some algorithms are largely based on the irregularity and fuzziness of the objects, and use fractals, graftals or particle systems. Others focus on the branching pattern of the trees with emphasis on morphology. Our concern here is the faithfulness of the models to the botanical nature of trees and plants. We present a model which integrates botanical knowledge of the architecture of the trees: how they grow, how they occupy space, where and how leaves, flowers or fruits are located, etc. The very first interest of the model we propose is its great richness: the same procedural methods can produce "plants" as different as weeping willows, fir trees, cedar trees, frangipani trees, poplars, pine trees, wild cherry trees, herbs, etc. Another very important benefit one can derive from the model is the integration of time which enables viewing the aging of a tree (possibility to get different pictures of the same tree at different ages, accurate simulation of the death of leaves and branches for example). The ease to integrate physical parameters such as wind, the incidence of factors such as insects attacks, use of fertilizers, plantation density, and so on makes it a useful tool for agronomy or botany.
Spacetime constraints
Authors: Witkin Andrew , Kass Michael
Published: November 2005

Spacetime constraints are a new method for creating character animation. The animator specifies
what
the character has to do, for instance, "jump from here to there, clearing a hurdle in between;"
how
the motion should be performed, for instance "don't waste energy," or "come down hard enough to splatter whatever you land on;" the character's
physical structure
---the geometry, mass, connectivity, etc. of the parts; and the physical
resources'
available to the character to accomplish the motion, for instance the character's muscles, a floor to push off from, etc. The requirements contained in this description, together with Newton's laws, comprise a problem of constrained optimization. The solution to this problem is a
physically valid
motion satisfying the "what" constraints and optimizing the "how" criteria. We present as examples a Luxo lamp performing a variety of coordinated motions. These realistic motions conform to such principles of traditional animation as anticipation, squash-and-stretch, follow-through, and timing.
Rendering trimmed NURBS with adaptive forward differencing
Authors: Shantz Micheal , Chang Sheue-Ling
Published: November 2005

Trimmed non-uniform rational B-splines have become a very useful surface representation form in the mechanical CAD industry. Previous rendering methods use the de Boor algorithm to evaluate the surface at equal increments in parameter space. This yields polygons which are then rendered. Alternatively the Oslo algorithm and Boehm's knot insertion algorithms are used in a subdivision approach. In this paper a new method is presented for rendering trimmed NURB surfaces of arbitrary order using the adaptive forward differencing (AFD) technique. This method extends the AFD technique to higher order, efficiently computes the basis matrix for each span, calculates the shading approximation functions for rational surfaces, and trims and image maps NURB surfaces. Trimming is accomplished by using AFD to scan convert the trimming curves in parameter space, thus producing the intersection points between the trim curves and an isoparametric curve across the surface. A winding rule is used to determine the regions bounded by the curve which are then rendered with AFD. The method is suitable for both hardware and software implementations, however, higher order surfaces require very high precision due to the forward difference nature of the algorithm.
Reconstruction filters in computer-graphics
Authors: Mitchell Don P. , Netravali Arun N.
Published: November 2005

Problems of signal processing arise in image synthesis because of transformations between continuous and discrete representations of 2D images. Aliasing introduced by sampling has received much attention in graphics, but reconstruction of samples into a continuous representation can also cause aliasing as well as other defects in image quality. The problem of designing a filter for use on images is discussed, and a new family of piecewise cubic filters are investigated as a practical demonstration. Two interesting cubic filters are found, one having good antialiasing properties and the other having good image-quality properties. It is also shown that reconstruction using derivative as well as amplitude values can greatly reduce aliasing.
High-performance polygon rendering
Authors: Akeley Kurt , Jermoluk Tom
Published: November 2005

This paper describes a system architecture for realtime display of shaded polygons. Performance of 100,000 lighted, 4-sided polygons per second is achieved. Vectors and points draw at the rate of 400,000 per second. High-speed pan and zoom, alpha blending, realtime video input, and antialiased lines are supported. The architecture heavily leverages parallelism in several forms: pipeline, vector, and array processing. It is unique in providing efficient and balanced graphics that support interactive design and manipulation of solid models. After an overview of algorithms and computational requirements, we describe the details of the implementation. Finally, the unique features enabled by the architecture are highlighted.
Collision Detection and Response for Computer Animation
Authors: Moore Matthew , Wilhelms Jane
Published: November 2005

When several objects are moved about by computer animation, there is the chance that they will interpenetrate. This is often an undesired state, particularly if the animation is seeking to model a realistic world. Two issues are involved:
detecting
that a collision has occurred, and
responding
to it. The former is fundamentally a kinematic problem, involving the positional relationship of objects in the world. The latter is a dynamic problem, in that it involves predicting behavior according to physical laws. This paper discusses collision detection and response in general, presents two collision detection algorithms, describes modeling collisions of arbitrary bodies using springs, and presents an analytical collision response algorithm for articulated rigid bodies that conserves linear and angular momentum.
Realistic animation of rigid bodies
Authors: Hahn James K.
Published: November 2005

The theoretical background and implementation for a computer animation system to model a general class of three dimensional dynamic processes for arbitrary rigid bodies is presented. The simulation of the dynamic interaction among rigid bodies takes into account various physical characteristics such as elasticity, friction, mass, and moment of inertia to produce rolling and sliding contacts. If a set of bodies is statically unstable, the system dynamically drives it toward a stable configuration while obeying the geometric constraints of the system including general
non-holonomic
constraints. The system also provides a physical environment with which objects animated using more traditional techniques can interact. The degree of interaction is easily controlled by the animator. A computationally efficient method to merge kinematics and dynamics for articulated rigid bodies to produce realistic motion is presented.
Applications of computer graphics to the visualization of meteorological data
Authors: Papathomas T. V. , Schiavone J. A. , Julesz B.
Published: November 2005

The need to visualize huge amounts of numerical data is exemplified in the field of meteorology, where measurements of many atmospheric parameters are routinely taken over large geographical areas for the purpose of monitoring and predicting weather. Computer graphics has provided and will continue to offer powerful tools to meet this visualization challenge, principally in three areas: first, efficient graphics algorithms for displaying the data; second, novel special-purpose graphics hardware; and third, interactive techniques for graphically manipulating the data at close to video rates. This paper reviews past and current uses of computer graphics for gaining insight from measured or modelled meterological data.
A hand biomechanics workstation
Authors: Thompson David E. , Buford William L. , Myers Loyd M. , Giurintano David J. , Brewer John A.
Published: November 2005

Interactive graphics for hand surgery was used to apply mathematical modeling and describe the kinematics of the hand and its resultant effect on hand function. Dynamic high resolution displays and three-dimensional images were tailored for use with a specific patients' hand and a new and powerful design and analysis tool produced. Methods were developed to portray kinematic information such as muscle excursion and effective moment arm and extended to yield dynamic information such as torque and work. This prototype workstation has been developed in concert with leading orthopedic surgeons and therapists.
PHIGS+ functional description revision
Authors: van Dam Andries
Published: November 2005

This is a set of proposed extensions to the proposed PHIGS graphics standard (dpANS X3.144-198x. DIS 9592) to cover the areas of lighting, shading and advanced primitives which have thus far not been addressed by that standard. This document is organized to promote its eventual integration with the existing PHIGS documentation and is therefore not tutorial in nature. It assumes that the reader is familiar with PHIGS. with rendering and with curves and surfaces. This specification has been made available to standards bodies for their consideration.
The standards pipeline
Authors: Meads John , Puk Dick
Published: November 2005

The news this issue consists entirely of Dick Puk's report on the ISO/IEC JTCI/SC24/WG4 computer graphics language bindings meeting held in Tokyo, Japan. April 12--20. 1988. We were hoping that we would be able to report on the X3H3 meeting, but, unfortunately, deadlines for this issue would not provide us with sufficient time to get that report in. We'll have that news in the next issue. This material is excerpted from a longer report prepared for SIGAda which funded Puk's attendance at this meeting.
Computer graphics around the world
Authors: Mudur S. P. , Gopalsamy S. , Shikhare Dinesh , Dixit D. S. , Patwardhan B. S. , Nayak N. S. , Shanbhag S. V.
Published: November 2005

The National Centre for Software Technology is an autonomous research and development institution of the government of India. It is a centre for excellence in software technology and related computer science areas. It carries out research in a number of disciplines such as databases and knowledge engineering, artificial intelligence, computer networking and Internet, software engineering and graphics and CAD.The graphics and CAD division of the centre has been active in this field since the early seventies and is one of the oldest and well-established research groups in this area in India. The current group numbers more than 20 graphics researchers with about 10 interdisciplinary associates in areas like visual design and communication, digital architecture, calligraphy, animation and linguistics.In the very early years, the focus was on graphics and CAD for electronic design, (PCBs, IC Mask layouts, etc.) By the mid seventies, the emphasis shifted to core graphics systems with 3D support. A number of commercially viable packages, such as IndoGKS and IndoPHIGS, based on international standards, were developed collaboratively with the industrial partners and sold worldwide. Over the past 15 years the group has been very active in 3D graphics and computer aided geometric design. A parallel track right from the mid seventies has been electronic publishing with particular emphasis on software architectures for dealing with the complexity of multiple scripts and languages in the country. In each of these subfields the group has undertaken high end implementation projects for end use and distribution, and also carried out substantive fundamental research that has found its way in the form of research publications in prestigious international journals and conferences.For the remainder of this article, we provide a brief overview of some recent research work. For more details on the division's activities and publications, the interested reader is referred to the following Web site:
http:://www.ncst.ernet.in/~graphics.
Education
Authors: Wolfe Rosalee
Published: November 2005

This column is the second in a series revisiting the introductory computer graphics course for undergraduate computer science majors. It has been 10 years since the last formal discussions resulted in a list of topics for
Curriculum 91
[1]. Given the great changes that have occurred in computer graphics during that time, the SIGGRAPH Education Committee is reexamining this issue.At SIGGRAPH 98, several computer graphics educators met to compare syllabi and as a result of the discussion that ensued, decided to solicit syllabi from educators at a variety of institutions across the country. Scott Grissom, Lew Hitchner, Bill Jones, Susan Reiser and I collected syllabi from 23 educators. For a list of the instructors who contributed syllabi, please see the Education column in the last issue of
Computer Graphics
[2]. Of the 23 collected, two were strictly for graduate students and one was primarily an image-processing course. This column examines the remaining 20 syllabi.
Intentional non-photorealistic rendering
Authors: Goldstein Dan
Published: November 2005

Non-photorealistic rendering (NPR) is a subject that has been generating quite a bit of interest in the computer graphics community lately. This is partly because any advance in the area is so rapidly picked up by authors who create actual content. The term NPR covers any computer-generated imagery explicitly rendered using techniques designed not to mimic physical reality. Most frequently, NPR rendering is performed by a program that takes images or three-dimensional geometry as input and creates a new output image within the bounds of a given artistic style.
Vis files
Authors: Hibbard Bill
Published: November 2005

Supercomputers produce data sets that are too large to visualize on workstations, which is a real problem. So I have asked Dr. Shun Doi to describe the work of his team at NEC, directly visualizing data sets on their supercomputers.
Computer graphics around the world
Authors: Shi Jiaoying , Pan Zhigeng
Published: November 2005

Computer graphics has become an important discipline in both academia and industry, and an enabling technology for a broad variety of applications such as engineering (CAD, CAE and CAM), geographic information systems (GIS), publishing, office applications, games and the filmmaking industry. Graphics is also integrated to Internet application systems, and graphics and image techniques are combined together in some special applications. Computer graphics can no longer be regarded as a confined discipline devoted solely to graphics standards or traditional techniques of 3D representations and rendering. The influence of computer graphics and its related techniques can be felt in almost all of today's key industrial areas, wherever computers are employed.Computer graphics has been a subject of interest in China for many years. Primary overviews of computer graphics activities in China were presented in [9] (on research and industry) and [8] (on education). In addition, there was also a special journal issue on computer graphics in China [10]. However, computer graphics activities in Hong Kong [7] and Macao were not included in these materials. Furthermore some new achievements were achieved in the past years. For example, in the State Key Lab of CAD&CG, Zhejiang University, a four-sided CAVE was installed in 1999. In addition, nowadays virtual reality (VR) is a hot research topic. In China researchers have attained many achievements in various VR fields. We will emphasize this aspect as we introduce computer graphics activities in China.This article gives an overview of the research and development of computer graphics in China, including the mainland of China, Hong Kong and Macao. The article is organized as follows. The next section introduces computer graphics research in some major universities and institutes in China. The section following that presents some industrial activities in computer graphics in China. The next section presents some other activities related to computer graphics. The final section gives closing comments.
Vis files
Authors: Hibbard Bill
Published: November 2005

Today, scientists, engineers and medical researchers routinely use computers to simulate complex physical phenomena. Such simulations present new challenges for computational scientists, including the need to effectively analyze and visualize complex three-dimensional data. As simulations become more complex and produce larger amounts of data, the effectiveness of utilizing such high resolution data will hinge upon the ability of human experts to interact with their data and extract useful information. Here we describe recent work at the SCI Institute in large-scale scalar, vector and censor visualization techniques. We end with a discussion of ideas for the integration techniques for creating computational multifield visualizations.
Computer graphics around the world
Authors: Pan Zhigeng , Heng Pheng-ann , Lau Rynson W. H.
Published: November 2005

Computer graphics has evolved to become an important discipline in both academia and industry, and an enabling technology for a broad variety of applications such as engineering (CAD, CAE and CAM), GIS, publishing and office applications. It can no longer be regarded as a confined discipline devoted solely to graphics standards or traditional techniques of 3D representations and rendering. The influence of computer graphics can be felt in almost all of today's key industrial areas, wherever computers are employed.Computer graphics has been a subject of interest in Hong Kong in recent years. Overviews of activities in China were presented in [18, 19] and in a special journal on computer graphics [20]. However, computer graphics activities in Hong Kong were not included in these materials, since all the papers mentioned above were published before July 1, 1997, when Hong Kong returned to China. Therefore, we present this article as a supplementary part to the two overviews, and try to give people an overall picture of computer graphics activities in China.
3D visualization development at NOAA forecast systems laboratory
Authors: McCaslin Paula T. , McDonald Philip A. , Szoke Edward J.
Published: November 2005

Visualization transforms numeric data into a visual form that enables users to conceptualize and understand the information. Three-dimensional (3D) visualization is the ability to display, analyze, manipulate and interact with 3D data in 3 space. New visualization tools, 3D in nature, are being designed to display meteorological datasets for use in operational forecasting.Forecast Systems Laboratory (FSL) has been supporting the development of 3D visualization software and applications since 1990. Until recently, the emphasis has been on research application. Using commercial visualization software called the Application Visualization System (AVS5), both analysis and forecast 3D data were displayed and investigated. The software was used for visual analysis and scanning of data for the presence of desired features. For example, plotting of the station observations with forecast-generated data allows visual comparison of the two. Figure 1 shows 3D images of weather parameters from the Local Analysis and Prediction System (LAPS) analysis output, which is created automatically on an hourly basis for the World Wide Web.Operational meteorologists who issue forecasts and warnings for the nation from the various Weather Forecast Offices (WFOs; see
http://www.wrh.noaa.gov/wrhq/nwspage.html
for a display of WFOs across the nation) currently utilize two-dimensional displays of analyses and numerical model output, combined with images from satellites and radar. They do this on a system developed at FSL call the Advanced Weather Interactive Processing System (AWIPS). Visualization has been used successfully in the research context for some time. The next logical step was to determine if 3D visualization can offer added value in an operational setting. This required developing a 3D visualization workstation application, conducting a forecast exercise using the system and evaluating feedback from the exercise. An experimental workstation application, Display 3D (D3D), was developed at FSL to investigate the complexities and 3D structure of atmospheric parameters, and potential value added of 3D displays in an operational forecast setting. The D3D system was designed to be used with the two-dimensional AWIPS operational system known as D2D.The scope of this article covers the development of the D3D application, plus a brief description of the D3D real-time exercise (RT98).
Two stepping information technology with visualization
Authors: Rhyne Theresa-Marie
Published: November 2005

Interactive visualization techniques facilitate the examination of unknown data sets. At the United States Environmental Protection Agency's (U.S. EPA) Scientific Visualization Center, we are exploring the combination of 3D visual displays with emerging information technologies. The following discussion highlights prototype efforts in three arenas: (1) Integrating Visualization into Data Mining Techniques; (2) Exploring Policy Analysis Visualization and (3) Combining Object-Relational Databases, Visualization and Web Technologies. The three prototypes are still in embryotic form. We anticipate it will take three to five years for actualization of these concepts and precise implementation details will change over time.The U.S. EPA is currently designing and implementing a new high profile Office of Environmental Information that will advocate the use and management of information as a strategic resource to enhance public health and environmental protection. New information technologies will be applied to facilitate the collection and dissemination of environmental data. We are hopeful that interactive visualization tools will be successfully used across the entire range of users, computing platforms and World Wide Web (Web) technologies that support the information life cycle.
Combinatorial analysis of ramified patterns and computer imagery of trees
Authors: Viennot X. , Eyrolles G. , Janey N. , Arqués D.
Published: November 2005

Herein is presented a new procedural method for generating images of trees. Many other algorithms have already been proposed in the last few years focusing on particle systems, fractals, graftals and L-systems or realistic botanical models. Usually the final visual aspect of the tree depends on the development process leading to this form. Our approach differs from all the previous ones. We begin by defining a certain "measure" of the form of a tree or a branching pattern. This is done by introducing the new concept of ramification matrix of a tree. Then we give an algorithm for generating a random tree having as ramification matrix a given arbitrary stochastic triangular matrix. The geometry of the tree is defined from the combinatorial parameters implied in the analysis of the forms of trees. We obtain a method with powerful control of the final form, simple enough to produce quick designs of trees without loosing in the variety and rendering of the images. We also introduce a new rapid drawing of the leaves. The underlying combinatorics constitute a refinment of some work introduced in hydrogeology in the morphological study of river networks. The concept of ramification matrix has been used very recently in physics in the study of fractal ramified patterns.
Curve-to-curve associations in spline-based inbetweening and sweeping
Authors: Bartel R. H. , Hardock R. T.
Published: November 2005

We are concerned in this paper with associations between spline curves that will hold at all inbetween positions when the control points of these curves are used as key points for animation or sweeping. It is established that any association between two spline curves that can be expressed as the equality of two linear mappings will hold throughout an inbetweening process provided the inbetweening trajectories are coordinated splines that uniquely interpolate the control-point key positions. Multiple associations are possible, so long as the basic requirements of linearity and coordination are observed.
Voxel space automata: modeling with stochastic growth processes in voxel space
Authors: Greene N.
Published: November 2005

A novel stochastic modeling technique is described which operates on a voxel data base in which objects are represented as collections of voxel records. Models are "grown" from predefined geometric elements according to rules based on simple relationships like intersection, proximity, and occlusion which can be evaluated more quickly and easily in voxel space than with analytic geometry. Growth is probabilistic: multiple trials are attempted in which an element's position and orientation are randomly perturbed, and the trial which best fits a set of rules is selected. The term
voxel space automata
is introduced to describe growth processes that sense and react to a voxel environment.Applications include simulation of plant growth, for which voxel representation facilitates sensing the environment. Illumination can be efficiently estimated at each plant "node" at each growth iteration by casting rays into the voxel environment, allowing accurate simulation of reaction to light including heliotropism.
Analytical methods for dynamic simulation of non-penetrating rigid bodies
Authors: Baraff D.
Published: November 2005

A method for analytically calculating the forces between systems of rigid bodies in resting (non-colliding) contact is presented. The systems of bodies may either be in motion or static equilibrium and adjacent bodies may touch at multiple points. The analytic formulation of the forces between bodies in non-colliding contact can be modified to deal with colliding bodies. Accordingly, an improved method for analytically calculating the forces between systems of rigid bodies in colliding contact is also presented. Both methods can be applied to systems with arbitrary holonomic geometric constraints, such as linked figures. The analytical formulations used treat both holonomic and non-holonomic constraints in a consistent manner.
Layered construction for deformable animated characters
Authors: Chadwick J. E. , Haumann D. R. , Parent R. E.
Published: November 2005

A methodology is proposed for creating and animating computer generated characters which combines recent research advances in robotics, physically based modeling and geometric modeling. The control points of geometric modeling deformations are constrained by an underlying articulated robotics skeleton. These deformations are tailored by the animator and act as a muscle layer to provide automatic squash and stretch behavior of the surface geometry. A hierarchy of composite deformations provides the animator with a multi-layered approach to defining both local and global transition of the character's shape. The muscle deformations determine the resulting geometric surface of the character. This approach provides independent representation of articulation from surface geometry, supports higher level motion control based on various computational models, as well as a consistent, uniform character representation which can be tuned and tweaked by the animator to meet very precise expressive qualities. A prototype system (Critter) currently under development demonstrates research results towards layered construction of deformable animated characters.
Algorithms for solid noise synthesis
Authors: Lewis J. P.
Published: November 2005

A solid noise is a function that defines a random value at each point in space. Solid noises have immediate and powerful applications in surface texturing, stochastic modeling, and the animation of natural phenomena.Existing solid noise synthesis algorithms are surveyed and two new algorithms are presented. The first uses Wiener interpolation to interpolate random values on a discrete lattice. The second is an efficient sparse convolution algorithm. Both algorithms are developed for
model-directed synthesis
, in which sampling and construction of the noise occur only at points where the noise value is required, rather than over a regularly sampled region of space. The paper attempts to present the rationale for the selection of these particular algorithms.The new algorithms have advantages of efficiency, improved control over the noise power spectrum, and the absence of artifacts. The convolution algorithm additionally allows quality to be traded for efficiency without introducing obvious deterministic effects. The algorithms are particularly suitable for applications where high-quality solid noises are required. Several sample applications in stochastic modeling and solid texturing are shown.
Antialiased ray tracing by adaptive progressive refinement
Authors: Painter J. , Sloan K.
Published: November 2005

We describe an antialiasing system for ray tracing based on adaptive progressive refinement. The goals of the system are to produce high quality antialiased images at a modest average sample rate, and to refine the image progressively so that the image is available in a usable form early and is refined gradually toward the final result.The method proceeds by adaptive stochastic sampling of the image plane, evaluation of the samples by ray tracing, and image reconstruction from the samples. Adaptive control of the sample generation process is driven by three basic goals: coverage of the image, location of features, and confidence in the values at a distinguished "pixel level" of resolution.A three-stage process of interpolation, filtering, and resampling is used to reconstruct a regular grid of display pixels. This reconstruction can be either batch or incremental.
Ray tracing deterministic 3-D fractals
Authors: Hart J. C. , Sandin D. J. , Kauffman L. H.
Published: November 2005

As shown in 1982, Julia sets of quadratic functions as well as many other deterministic fractals exist in spaces of higher dimensionality than the complex plane. Originally a boundary-tracking algorithm was used to view these structures but required a large amount of storage space to operate. By ray tracing these objects, the storage facilities of a graphics workstation frame buffer are sufficient. A short discussion of a specific set of 3-D deterministic fractals precedes a full description of a ray-tracing algorithm applied to these objects. A comparison with the boundary-tracking method and applications to other 3-D deterministic fractals are also included.
Parameterized Ray-tracing
Authors: Séquin C. H. , Smyrl E. K.
Published: November 2005

The construction and refinement of a computer graphics scene is unacceptably slow when using ray tracing. We introduce a new technique to speed up the generation of successive ray traced images when the geometry of the scene remains constant and only the light source intensities and the surface properties need to be adjusted. When the scene is first ray traced, an expression parameterized in the color of all lights and the surface property coefficients of all objects is calculated and stored for each pixel. Redisplaying a scene with a new set of lights and colors then consists of substituting values for the corresponding parameters and re-evaluating the expressions for the pixels. This parameter updating and redisplay takes only a few seconds, as compared to the many minutes or hours required to ray trace the entire scene again, but it uses much more memory and disk space. With suitable expression sharing, however, these storage needs can be reduced to an acceptable level.
Improving radiosity solutions through the use of analytically determined form-factors
Authors: Baum D. R. , Rushmeier H. E. , Winget J. M.
Published: November 2005

Current radiosity methods rely on the calculation of geometric factors, known as form-factors, which describe energy exchange between pairs of surfaces in the environment. The most computationally efficient method for form-factor generation is a numerical technique known as the hemi-cube algorithm. Use of the hemi-cube is based on assumptions about the geometry of the surfaces involved. First, this paper examines the types of errors and visual artifacts that result when these assumptions are violated. Second, the paper shows that these errors occur more frequently in progressive refinement radiosity than in the originally proposed full matrix radiosity solution. Next, a new analytical technique for determining form-factors that is immune to the errors of the hemi-cube algorithm is introduced. Finally, a hybrid progressive refinement method that invokes the new technique to correctly compute form-factors when hemi-cube assumptions are violated is presented.
Incremental computation of planar maps
Authors: Gangnet M. , Hervé J.-C. , Pudet T. , van Thong J.-M.
Published: November 2005

A
planar map
is a figure formed by a set of intersecting lines and curves. Such an object captures both the geometrical and the topological information implicitly defined by the data. In the context of 2D drawing it provides a new interaction paradigm,
map sketching
, for editing graphic shapes.To build a planar map, one must compute curve intersections and deduce from them the map they define. The computed topology must be consistent with the underlying geometry. Robustness of geometric computations is a key issue in this process. We present a robust solution to Bézier curve intersection that uses exact forward differencing and bounded rational arithmetic. Then, we describe data structure and algorithms to support incremental insertion of Bézier curves in a planar map. A prototype illustration tool using this method is also discussed.
An efficient algorithm for hidden surface removal
Authors: Mulmuley K.
Published: November 2005

We give an efficient, randomized hidden surface removal algorithm, with the best time complexity so far. A distinguishing feature of this algorithm is that the expected time spent by this algorithm on junctions which are at the "obstruction level"
l
, with respect to the viewer, is inversely proportional to
l
. This provably holds for any input, regardless of the way in which faces are located in the scene, because the expectation is with respect to randomization in the algorithm, and does not depend on the input. In practice, this means that the time complexity is roughly proportional to the size of the
actually visible
output times logarithm of the average depth complexity of the scene (this logarithm is very small generally).
Retrospectives I: the early years in computer graphics at MIT, Lincoln Lab, and Harvard
Authors: Hurst J. , Mhoney M. S. , Taylor N. H. , Ross D. T. , Fano R. M.
Published: November 2005

I am Jan Hurst; welcome to Retrospectives. In early 1988, SIGGRAPH funded a project which was called Milestones, the History of Computer Graphics. We believed it was important to capture the early history since the graphics of tomorrow continues to build upon its past. We established goals, and one result was to begin a series of retrospectives which focus on specific aspects of the industry. Boston seemed like the perfect opportunity to focus on MIT, Lincoln Lab, and Harvard.I hope that you will get a sense from the pioneers as to what graphics was like in its infancy in Boston. I hope that you will enjoy hearing about their experiences as I have. They have been absolutely charming and inspirational to work with, and I'd like to thank all of them at this time.The speakers have many things to share with you, so I will be brief. I want to thank SIGGRAPH for supporting and encouraging this project and I want to thank the Pioneers for their willingness to share their experiences and their knowledge with all of us.I want to introduce you to Michael S. Mahoney, who will act as the moderator for the retrospectives. Mike is a professor at Princeton, he is in the program in the History of Science, he is editor of the ACM History Series, and he is a distinguished member of the Milestone Advisory Committee. Mike.