Volume 13 (1994)

Permanent URI for this community

https://diglib.eg.org/handle/10.2312/59

Browse

Now showing 1 - 20 of 69

A Median Cut Algorithm for Efficient Sampling of Radiosity Functions
(Blackwell Science Ltd and the Eurographics Association, 1994) Feda, Martin; Purgathofer, Werner
This paper presents an efficient method for sampling the illumination functions in higher order radiosity algorithms. In such algorithms, the illumination function is not assumed to be constant across each patch, but it is approximated by a function which is at least C1 continuous. Our median cut sampling algorithm is inspired by the observation that many form factors are computed at higher precision than is necessary. While a high sampling rate is necessary in regions of high illumination, dark areas can be sampled at a much lower rate to compute the received radiosity within a given precision. We adaptively subdivide the emitter into regions of approximately equal influence on the result. Form factors are evaluated by the disk approximation and a ray tracing based test for occlusion detection. The implementation of a higher order radiosity system using B-splines as radiosity function is described. The median cut algorithm can also be used for radiosity algorithms based on the constant radiosity assumption.
An All-integer Algorithm for Drawing Anti-aliased Straight Lines
(Blackwell Science Ltd and the Eurographics Association, 1994) Kui, Liu Yong
An algorithm for drawing anti-aliased straight lines based on Bresenharn sline algorithm is presented in this paper. Only integer calculations are required. Multiplications or divisions are not needed (only simple addition/subtraction and sign testing are used). The algorithm can be used to choose between 2n intermediate grey levels between black and white.
Fast Dynamic Tessellation of Trimmed NURBS Surfaced1
(Blackwell Science Ltd and the Eurographics Association, 1994) Abi-Ezzi, Salim S.; Subramaniam, Srikanth
Trimmed NURBS (non-uniform rational B-splines) surfaces are being increasingly used and standardized in geometric modeling applications. Fast graphical processing of trimmed NURBS at interactive speeds is absolutely essential to enable these applications. which poses some unique challenges in software, hardware, and algorithm design. This paper presents a technique that uses graphical compilation to enable fast dynamic tessellation of trimmed NURBS surfaces under highly varying transforms.We use the concept of graphical data compilation. through which we preprocess the NURBS surface into a compact, view-independent form amenable for fast per-frame extraction of triangles. Much of the complexity of processing is absorbed during compilation. Arbitrarily complex trimming regions are broken down into simple regions that are specially designed to facilitate tessellation before rendering. Potentially troublesome cases of degeneracies in the surface are detected and dealt with during compilation. Compilation enables a clean separation of algorithm-intensive and compute-intensive operations, and provides for parallel implementations of the latter. Also, we exercise a classification technique while processing trimming loops. which robustly takes care of geometric ambiguities and deals with special cases while keeping the compilation code simple and concise.
Recovering a Smooth Boundary Representation from an Edge Quadtree and from a Face Octree
(Blackwell Science Ltd and the Eurographics Association, 1994) Pla-Garcia, N.
The Face Octrees are a representation scheme which is very suitable to represent both smooth free form surfaces and solids with smooth boundary, as well as, to perform operations among them. However, the Face Octree representation is non continuous, thus an algorithm to convert this model to a boundary representation can be necessary. The conversion algorithm makes the advantages of this scheme really significant. The current paper is involved in the conversion from the Face Octrees model to a smooth boundary representation. However, first the planar case is treated.
Controllable Locality in C2 Interpolating Curves by B2-splines / S-splines
(Blackwell Science Ltd and the Eurographics Association, 1994) Kuroda, Mitsuru; Furukawa, Susumu; Kimura, Fumihiko
This paper presents a systematic scheme for controlling the local behaviour of C2 interpolating curves, based on the cubic B2-splines and the quartic S-splines. Both splines have an additional control point obtained by knot- insertion or degree-elevation in each span of the conventional uniform cubic interpolating B-splines. The shape designer can choose the desired range of locality for each span and get the corresponding additional control point as a barycentric combination of interpolation points within the range, without solving any variational problem and simultaneous equations. The scheme is consistent over the entire curve subject to some typical end conditions. The class of the curves derived includes the conventional cubic interpolating B-splines. Examples demonstrate the behaviour of the new interpolating curves and the capability of the scheme.
A Robust and Consistent Algorithm for Intersecting Convex Polyhedra
(Blackwell Science Ltd and the Eurographics Association, 1994) Sugihara, Kokichi
This paper presents a numerically robust and topologically consistent algorithm for intersecting convex polyhedra. This algorithm is new in the sense that the consistency issue is completely separated from the numerical error issue. The intersection operation is combinatorially abstracted as the operation of changing the vertex-edge graphs associated with the input polyhedra, and numerical computation is employed only for choosing the branch of processing which is most likely to lead to the correct solution of the problem. Hence, the resultant algorithm is completely free from topological inconsistency.
A Constraint-Based Reasoning Framework for Behavioural Animation
(Blackwell Science Ltd and the Eurographics Association, 1994) Mah, Sang; Calvert, Thomas W.; Havens, William
Behaviour is a reflection of a reasoning process that must deal with constraints imposed by an external environment, internal knowledge and physical structure. This paper proposes a framework for behavioural animation that is based on the next generation of object-oriented, constraint-based expert systems technology, and applies a control structure of knowledge agents and knowledge units to determine the behaviour of objects to be animated. Knowledge agents are responsible for planning, plan implementation and information extraction from the environment. The activity of an agent is dependent on the knowledge units ascribed to them by the animator. The interaction between agents and knowledge units is resolved by the reasoning engine, and thus, influences the eventual motion displayed. An example given is NSAIL, a pilot implementation using the model-based ECHIDNA constraint logic programming shell. With this approach, the motion for a sailing scenario and other behavioural domains can be specified at a high level through the characterization of the knowledge agents.
Real Time Fitting of Hand-Sketched Pressure Brushstrokes
(Blackwell Science Ltd and the Eurographics Association, 1994) Pudet, Thierry
A method is described for fitting the outline of hand-sketched pressure brushstrokes with Bezier curves. It combines the brush-trajectory model, in which a stroke is generated by dragging a brush along a given trajectory, with a fast curve fitting algorithm.The method has been implemented for a vector-based drawing program in which the user draws with a cordless pressure-sensitive stylus on a digitizing tablet. From the trajectory followed by the stylus, its associated pressure data, and a specified brush, a stroke of variable width is computed and displayed in real time.First, the digitized trajectory is fitted, thus removing noise. Then, from polygonal approximations of the fitted trajectory and the brush outline, a polygonal approximation of the stroke outline is computed. Working with polygonal approximations reduces computations to simple geometric operations and greatly simplifies the treatment of dynamic, pressure-controlled brushes. Last, the polygonal approximation of the stroke outline is fitted. The result is a closed piecewise Bezier curve approximating the brushstroke outline to within an arbitrary error tolerance.Several examples of hand-sketched drawings realized with this method are presented.
A New Approach to the Construction of Surfaces from Contour Data
(Blackwell Science Ltd and the Eurographics Association, 1994) Jones, Mark W.; Chen, Min
This paper presents a new approach to the construction of a surface from a stack of contour slices. Unlike most existing methods, this new approach handles ambiguous conditions consistently without employing an algorithm to establish a correspondence between vertices on one contour and those on the next. It is easy to implement and fast to compute, requiring only basic geometric properties, namely closedness and simplicity, to be available with contour data. The advantages of this new approach have also been demonstrated with solutions to a few classical problems from the literature and some practical problems in medical imaging. It can also be applied to geographical surveying and keyframe animations.
Cross Scan Buffer and its Applications
(Blackwell Science Ltd and the Eurographics Association, 1994) Tanaka, Toshimitsu; Takahashi, Tokiichiro
We propose the Cross Scanline Buffer which preserves the result of hidden surface removal as performed by the Cross Scanline Algorithm. The Cross Scan Buffer reduces image re-generation time and eliminates aliasing artifacts even if the image is arbitrarily scaled. Perfect anti-aliasing is achieved because the Cross Scanline Algorithm analytically determines visible polygonal surfaces and divides them into sets of triangles and trapezia. The Cross Scan Buffer supports the various applications that currently use the conventional buffering methods for anti-aliasing. This paper introduces and tests three applications: image scaling, shadow creation, and texture mapping. Experimental results verify that the Cross Scan Buffer is very powerful yet efficient.
Multiresolution Tiling
(Blackwell Science Ltd and the Eurographics Association, 1994) Meyers, David
This paper describes an efficient method for constructing a tiling between a pair of planar contours. The problem is of interest in a number of domains, including medical imaging, biological research and geological reconstructions. Our method, based on ideas from multiresolution analysis and wavelets, requires O(n) space and appears to require O(n log n) time for average inputs, compared to the O(n2) space and O(n2 log n) time required by the optimizing algorithm of Fuchs, Kedem and Uselton1. The results computed by our algorithm are in many cases nearly the same as those of the optimizing algorithm, but at a small fraction of the computational cost. The performance improvement makes the algorithm usable for large contours in an interactive system. The use of multiresolution analysis provides an efficient mechanism for data compression by discarding wavelet coefficients smaller than a threshold value during reconstruction. The amount of detail lost can be controlled by appropriate choice of the threshold value. The use of lower resolution approximations to the original contours yields significant savings in the time required to display a reconstructed object, and in the space required to store it.
Deriving Spectral, Reflectance Functions of Computer-Simulated Object Colours
(Blackwell Science Ltd and the Eurographics Association, 1994) Schettini, R.
A method is presented which, given the RGB values of a colour stimulus displayed on a given cathode ray tube (to which a CIE XYZ triple corresponds), makes it possible to find a spectral reflectance function characterizing an object colour. Such an object when"illuminated" by a given illuminant produces a metameric spectral power distribution, that is, one with the same XYZ tristimulus values. The method is useful in the colorimetric matching of colours on different media or supports.
An Inexpensive BRDF Model for Physically-based Rendering
(Blackwell Science Ltd and the Eurographics Association, 1994) Schlick, Christophe
A new BRDF model is presented which can be viewed as an kind of intermediary model between empirism and theory. Main results of physics are observed (energy conservation, reciprocity rule, microfacet theory) and numerous phenomena involved in light reflection are accounted for, in a physically plausible way (incoherent and coherent reflection, spectrum modifications, anisotropy, self-shadowing, multiple surface and subsurface reflection, differences between homogeneous and heterogeneous materials). The model has been especially intended for computer graphics applications and therefore includes two main features: simplicity (a small number of intuitively understandable parameters controls the model) and efficiency (the formulation provides adequation to Monte-Carlo rendering techniques and/or hardware implementations).
A Theoretical Framework for Physically Based Rendering
(Blackwell Science Ltd and the Eurographics Association, 1994) Lafortune, Eric P.; Willems, Yves D.
In this paper we introduce the concept of the global reflection distribution function which allows concise formulation of the global illumination problem. Unlike previous formulations it is not geared towards any specific algorithm. As an example of its versatility we derive a Monte Carlo rendering algorithm that seamlessly integrates the ideas of shooting and gathering power to create photorealistic images.
Reducing The Latency In Head-Mounted Displays By A Novel Prediction Method Using Grey System Theory
(Blackwell Science Ltd and the Eurographics Association, 1994) Wu, Jiann-Rong; Ouhyoung, Ming
In this paper we propose a novel prediction method for the head motion using Grey System theory, where a 6D tracker is attached to an HMD on a user s head in virtual reality applications. Our prediction method using Grey System Model can greatly reduce the latency by at least one half and reduce image jittering. A system latency below 100 ms or even 50 ins can be achieved, even though without prediction the latency is around 200 ms. Using 6 points in prediction with Grey System Model is currently the best in tracker prediction as we tried from 2 points to 10 points.In order to measure the latency, we also propose a way to measure it in an HMD system precisely and conveniently. During the process, we have implemented four different prototypes respectively on a PC486, a SUN SparcStation10, an SGI IndigoR4000, and a high performance computer image generator. The computation complexity of our prediction method is relatively low and therefore real time requirement is easily met.
Raycasting of Nonregularly Structured Volume Data
(Blackwell Science Ltd and the Eurographics Association, 1994) Fruhauf, Thomas
Raycasting is an efficient, but computation-intensive technique for the direct rendering of volumetric data. Nonregularly structured volume data is produced in a variety of applications, such as numerical simulation, ultrasonic inspection, or seismic measurement. Unfortunately, in raycasting nonregulary structured grids, sampling data along the rays is even more computation-intensive. One idea might be to resample the data onto a regular grid for further processing. It is shown, that resampling typical grids results either in extreme sub- sampling of the most interesting areas or in data sets too huge to handle. Additionally, no better hardware will overcome the fact that all topology and context information is lost through resampling. Therefore, dedicated algorithms for the raycasting of nonregularly structured volumes are required.We present a new approach for this task, which is based on sending rays through the computational space of a nonregular grid, instead of conventionally raycasting the physical space. This technique overcomes the difficulties in sampling data along the rays, since the computational space is regular by definition. The paper outlines the mathematical operations of this technique as well as its embedding in a rendering algorithm. We have implemented the new raycasting strategy as a module of our interactive visualization system, providing the users with an additional tool for the efficient exploration of their data.
Spectral Data Modeling for a Lighting Application
(Blackwell Science Ltd and the Eurographics Association, 1994) Deville, Pascal M.; Merzouk, Slimane; Cazier, Dorothee; Paul, Jean C.
In computer graphics, image generation uses the RGB colorimetric system. However, this system does not produce an accurate simulation of the spectral characteristics of both light and material, due to the fact that it is device dependent. Indeed, to get realistic images, the image calculation process must deal with spectral characteristics of lights and materials and with the problem of sampling the wavelength domain. Methods have been shown that are a good way to solve the two problems mentioned above, however, these approaches do not take into account complex spectrums (discontinuous). In this paper, we propose a method which removes the constraints imposed by the current methods. Our method is based upon an algorithm of spectrum analysis.
Five-dimensional Adaptive Subdivision for Ray Tracing
(Blackwell Science Ltd and the Eurographics Association, 1994) Simiakakis, G.; Day, A. M.
This paper presents a directional subdivision method for speeding up ray tracing. This method is easy to use, because it automatically adapts the subdivision to the scene relieving the user from having to set parameters for the subdivision. It also attempts a balance between 5D and spatial subdivision in order to benefit from both methods. A memory saving scheme is introduced and experimental results are presented.
Magicsphere: an insight tool for 3D data visualization
(Blackwell Science Ltd and the Eurographics Association, 1994) Cignoni, P.; Montani, C.; Scopigno, R.
How to render very complex datasets, and yet maintain interactive response times, is a hot topic in computer graphics. The MagicSphere idea originated as a solution to this problem, but its potential goes much further than this original scope. In fact, it has been designed as a very generical 3D widget: it defines a spherical volume of interest in the dataset modeling space. Then, several filters can be associated with the Magicsphere, which apply different visualization modalities to the data contained in the volume of interest. The visualization of multi-resolution datasets is selected here as a case study and an ad hoc filter has been designed, the MultiRes filter. Some results of a prototipal implementation are presented and discussed.
Volume Rendering on Non-regular Grids
(Blackwell Science Ltd and the Eurographics Association, 1994) Tabatabai, Behnam; Sessarego, Emanuela A.; Mayer, Harald F.
In this article we present the principle methods for volumerendering of non-regular grids as used in the Finite Element Method or the Method of Control Volumes. Besides linear element types, the methods discussed here also cover the handling of commonly used non-linear element types but little considered in the Computer Graphics community. The very basic operation in the whole rendering process, namely the interpolation of the geometry and function values is fully based on the element type specific shape functions, ensuring a consistent mathematical treatment of the object in the sense of the underlying numerical simulation. We discuss the implications of this approach and propose optimizations justified by general assumptions on the qualify of the simulation model.

Browse

Browsing Volume 13 (1994) by Issue Date

Results Per Page

Sort Options