Volume 14 (1995)

Permanent URI for this community

https://diglib7.eg.org/handle/10.2312/65

Browse

Now showing 1 - 20 of 59

Interactive Ray Tracing on a Virtual Shared-Memory Parallel Computer
(Blackwell Science Ltd and the Eurographics Association, 1995) Keates, M.J.; Hubbold, R.J.
This paper describes the results of experiments with accelerated ray tracing on a virtual shared-memory parallel computer and attempts to determine whether this kind of architecture would be suitable for an interactive ray tracing system. The machine used, the Kendall Square Research KSR1, is described in sufficient detail for its novel features to be appreciated. The paper describes a new ray tracer written specifically to capitalise on the KSR1 s features. Models used in the experiments include well-known test cases from the Haines database, permitting comparison with previously reported results. The results show that the program scales well up to 230 processors, and that with progressive rendering initial rendering times can be reduced to as little as 0.2 second on 32 processors.
Three Architectures for Volume Rendering
(Blackwell Science Ltd and the Eurographics Association, 1995) Hesser, Jurgen; Manner, Reinhard; Knittel, Gunter; Strasser, Wolfgang; Pfister, Hanspeter; Kaufman, Arie
Volume rendering is a key technique in scientific visualization that lends itself to significant exploitable parallelism. The high computational demands of real-time volume rendering and continued technological advances in the area of VLSl give impetus to the development of special-purpose volume rendering architectures. This paper presents and characterizes three recently developed volume rendering engines which are based on the ray-casting method. A taxonomy of the algorithmic variants of ray-casting and details of each ray-casting architecture are discussed. The paper then compares the machinefeatures and provides an outlook onfuture developments in the area of volume rendering hardware.
Bresenham's Line Generation Algorithm with Built-in Clipping
(Blackwell Science Ltd and the Eurographics Association, 1995) Kuzmin, Yevgeny P.
One of the most important operations in many graphical systems is the generation of a line segment. This process consists of two stages: clipping and drawing. These two stages are separated in current graphical applications. In this paper a new approach to line generation is proposed, which unifies these stages. The proposed algorithm is based on Bresenham s line generation algorithm to include necessary line clipping. The line clipping stage is an operation-reduced, integer arithmetic only algorithm. The notion of correctness of line clipping is introduced and correctness of the proposed algorithm is shown. Complete C-notation of the algorithm is included.
Efficient Parallel Gouraud Shading and Linear Interpolation over Triangles
(Blackwell Science Ltd and the Eurographics Association, 1995) Narayanaswami, Chandrasekhar
A parallel raster algorithm to draw Gouraud shaded triangles is presented. At the heart of the algorithm is a new constrained parallel edge-traversal technique. This parallel traversal represents an increased level of parallelism compared to the existing solutions. Next, traditional algorithms take different amounts of time to advance from one horizontal span to another for the left edge and the right edge of the triangle when the slope of one of the edges is more than one and that of the other edge is less than one. This causes one processor to wait for another processor. The parallel constrained edge traversal technique removes this problem by directly jumping from one span to the next. It also ensures that adjacent triangles that share an edge do not share any pixels. Moreover, no cracks occur between adjacent polygons. Unlike some existing algorithms whose complexity depends on the size of the bounding box of the triangle, the complexity of our algorithm is solely dependenton the perimeter and area of the triangle.Due to the above features, the algorithm presented here exposes a greater degree of parallelism at considerably lesser cost and achieves better processor utilization, compared to existing algorithms for this problem1, 2, 3, 4, 5, 6. The algorithm is well suited for hardware implementation.
Multiresolution B-spline Radiosity
(Blackwell Science Ltd and the Eurographics Association, 1995) Yu, Yizhou; Peng, Qunsheng
This paper introduces a kind of new wavelet radiosity method called multiresolution B-spline radiosity, which uses B-splines of different scales to represent radiosity distribution functions. A set of techniques and algorithms, such as function extrapolation, adaptive quadrature, scale adjustment and octree, are proposed to implement it. This method sets up hierarchical structures on surfaces, keeps radiosity distribution continuous at element boundaries, does not need postprocessing, and does not prevent the use of any surface whose parameter domain is rectilinear.
Visibility and Dead-Zones in Digital Terrain Maps
(Blackwell Science Ltd and the Eurographics Association, 1995) Or, Daniel Cohen; Shaked, Amit
The problem of detecting the visible and hidden areas of a topographic surface from a given viewpoint is well known, and has applications in GIS and other fields. The computational geometry literature is rich with solutions based on a polygonal representation of the surface. This work confronts the problem by working directly on the Digital Elevation Map which represents the terrain surface. We present an algorithm that processes discrete lines of sight from the viewpoint to the surface perimeter, and tests the unit-sized terrain elements along the discrete cross-sections defined by these lines. The algorithm is very efficient, performing O(n) testing operations, consisting of a few additions and no more than one multiplication each, where n is the number of the terrain elements in the map.
Colouration Issues in Computer Generated Facial Animation
(Blackwell Science Ltd and the Eurographics Association, 1995) Patel, M.
In everyday interactions with one another we use the face for recognising people and for communicating with them. Despite the considerable amount of research into computer generated facial animation, one particular aspect, that of the colouration of the face appears to have been neglected. In this paper we address issues pertinent to the use of colour for both modelling the appearance of the face and for enhancing communication during facial expression and animation. Colouration is an integral part of the face, which helps in the recognition of faces as well as in the interpretation of the often subtle signals emitted by the human face.
Fast Wavelet Based Volume Rendering by Accumulation of Transparent Texture Maps
(Blackwell Science Ltd and the Eurographics Association, 1995) Lippert, L.; Gross, M. H.
In the following paper, a new method for fast and accurate volume intensity and color integration is elaborated, which employs wavelet decompositions and texture mapping. At this point, it comprises and unifies the advantages of recently introduced Fourier domain volume rendering techniques and wavelet based volume rendering. Specifically, the method computes analytic solutions of the ray intensity integral through a single wavelet by slicing its Fourier transform and by backprojecting it into the spatial domain. The resulting slices can be considered as RGB textures where R, G and B account for the decomposed volume color function. Due to the similarity of the basis functions, the computation of the texture map has to be figured out only once for each 3D mother wavelet. Hence, the final volume rendering procedure turns out to be a superposition of self-similar, transparent and colored textures, which is supported by modern hardware accumulation buffers. Linear shading and attenuation can be introduced by modifications of the wavelet s Fourier transform.The main advantages of this method are the provision of accurate solutions and quantification of error bounds, the absence of any expensive prefiltering and the independence of the computational costs from the image resolution. Furthermore, any required discretization, such as the resolution of the basis textures is defined within the computational framework of the wavelet transform. The method is not restricted to a specific type of wavelet unless is provides an analytic Fourier description, such as any B-spline wavelets do.
Morphological Operations for Color-Coded Images
(Blackwell Science Ltd and the Eurographics Association, 1995) Busch, Christoph and Eberle, Michael
The subject of this paper is the semantically based postprocessing of color-coded images such as classification results. We outline why the classical definition of mathematical morphology suffers if it is used for processing of coded image data. Therefore we provide an extension for morphological operations such as dilation, erosion, opening, and closing. With a new understanding of morphology we introduce bridging and tunneling as further combinations of dilation and erosion. The extensions are applied to medical image data, where the semantic rules stem from basic anatomical knowledge.
The HUMANOID Environment for Interactive Animation of Multiple Deformable Human Characters
(Blackwell Science Ltd and the Eurographics Association, 1995) Boulic, R.; Capin, T.; Huang, Z.; Kalra, P.; Lintermann, B.; Magnenat-Thalmann, N.; Moccozet, L. and Molet, T. and Pandzic, I. and Saar, K. and Schmitt, A. and Shen, J. and Thalmann, D.
We describe the HUMANOID environment dedicated to human modeling and animation for general multimedia, VR, and CAD applications integrating virtual humans. We present the design of the system and the integration of the various features: generic modeling of a large class of entities with the BODY data structure, realistic skin deformation for body and hands, facial animation, collision detection, integrated motion control and parallelization of computation intensive tasks.
Discrete Ray-Tracing of Huge Voxel Spaces
(Blackwell Science Ltd and the Eurographics Association, 1995) Stolte, Nilo; Caubet, Rene
The quality of images produced by Discrete Ray-Tracing voxel spaces is highly dependent on 3d grid resolution. The huge amount of memory needed to store such grids often discards discrete Ray-Tracing as a practical visualization algorithm. The use of an octree can drastically change this when most of space is empty, as such is the case in most scenes.Although the memory problem can be bypassed using the octree, the performance problem still remains. A known fact is that the performance of discrete traversal is optimal for quite low resolutions. This problem can be easily solved by dividing the task in two steps, working in two low resolutions instead of just one high resolution, thus taking advantage of optimal times in both steps. This is possible thanks to the octree property of representing the same scene in several different resolutions. This article presents a two step Discrete Ray-Tracing method using an octree and shows, by comparing it with the single step version, that a substantial gain in performance is achieved.
An Adaptive Spatial Subdivision of the Object Space for Fast Collision Detection of Animated Rigid Bodies
(Blackwell Science Ltd and the Eurographics Association, 1995) Bandi, Srikanth; Thalmann, Daniel
Collision detection tests between objects dominate run time simulation of rigid body animation. Traditionally, hierarchical bounding box tests are used to minimize collision detection time. But the bounding boxes do not take shapes of the objects into account which results in a large number of collision detection tests. We propose an adaptive spatial subdivision of the object space based on octree structure to rectify this problem. We also present a technique for efficiently updating this structure periodically during the simulation.
Isometric Piecewise Polynomial Curves
(Blackwell Science Ltd and the Eurographics Association, 1995) Fiume, Eugene
The main preoccupations of research in computer-aided geometric design have been on shape-specification techniques for polynomial curves and surfaces, and on the continuity between segments or patches. When modelling with such techniques, curves and surfaces can be compressed or expanded arbitrarily. There has been relatively little work on interacting with direct spatial properties of curves and surfaces, such as their arc length or surface area. As a first step, we derive families of parametric piecewise polynomial curves that satisfy various positional and tangential constraints together with arc-length constraints. We call these curves isometric curves. A space curve is defined as a sequence of polynomial curve segments, each of which is defined by the familiar Hermite or Bezier constraints for cubic polynomials- as well, each segment is constrained to have a specified arc length. We demonstrate that this class of curves is attractive and stable. We also describe the numerical techniques used that are sufficient for achieving real time interaction with these curves on low-end workstations.
Automatic Reconstruction of Unstructured 3D Data: Combining a Medial Axis and Implicit Surfaces
(Blackwell Science Ltd and the Eurographics Association, 1995) Bittar, Eric; Tsingos, Nicolas; Gascuel, Marie-Paule
This paper presents a new method that combines a medial axis and implicit surfaces in order to reconstruct a 3D solid from an unstructured set of points scattered on the object s surface. The representation produced is based on iso-surfaces generated by skeletons, and is a particularly compact way of defining a smooth free-form solid. The method is based on the minimisation of an energy representing a"distance" between the set of data points and the iso-surface, resembling previous reserach19. Initialisation, however, is more robust and efficient since there is computation of the medial axis of the set of points. Instead of subdividing existing skeletons in order to refine the object s surface, a new reconstruction algorithm progressively selects skeleton-points from the pre- computed medial axis using an heuristic principle based on a"local energy" criterion. This drastically speeds up the reconstruction process. Moreover, using the medial axis allows reconstruction of objects with complex topology and geometry, like objects that have holes and branches or that are composed of several connected components. This process is fully automatic. The method has been successfully applied to both synthetic and real data.
Algorithms for Extracting Correct Critical Points and Constructing Topological Graphs from Discrete Geographical Elevation Data
(Blackwell Science Ltd and the Eurographics Association, 1995) Takahashi, Shigeo; Ikeda, Tetsuya; Shinagawa, Yoshihisa; Kunii, Tosiyasu L.; Ueda, Minoru
Researchers in the fields of computer graphics and geographical information systems (GISs) have extensively studied the methods of extracting terrain features such as peaks, pits, passes, ridges, and ravines from discrete elevation data. The existing techniques, however, do not guarantee the topological integrity of the extracted features because of their heuristic operations, which results in spurious features. Furthermore, there have been no algorithms for constructing topological graphs such as the surface network and the Reeb graph from the extracted peaks, pits, and passes. This paper presents new algorithms for extracting features and constructing the topological graphs using the features. Our algorithms enable us to extract correct terrain features; i.e., our method extracts the critical points that satisfy the Euler formula, which represents the topological invariant of smooth surfaces. This paper also provides an algorithm that converts the surface network to the Reeb graph for representing contour changes with respect to the height. The discrete elevation data used in this paper is a set of sample points on a terrain surface. Examples are presented to show that the algorithms also appeal to our visual cognition.
Realizing 3D Visual Programming Environments within a Virtual Environment
(Blackwell Science Ltd and the Eurographics Association, 1995) Van Reeth, F.; Coninx, K.; De Backer, S.; Flerackers, E.
In the visual programming community, many interesting graphical metaphors have been reported upon for representing computer programs graphically. Most of them have a 2D or 2.5D appearance on the screen in order to reflect the inherent multi-dimensionality of the programming constructs being represented. By going into a three-dimensional representation, this reflection can go a stepfurther. With ever increasing3D graphics rendering capabilities on todays computers, it moreover becomes feasible to extend the dimensionality of the program (and data structure) depiction. We follow this approach by realizing 3D graphical programming techniques within CAEL, our interactive Computer Animation Environment Language. The paper elucidates how several concepts, traditionally found within the Virtual Environments area, can be utilized in the realization of three-dimensional Programming Environments.
Synthesizing Feather Textures in Galliformes
(Blackwell Science Ltd and the Eurographics Association, 1995) Dai, Wen-Kai; Shih, Zen-Chung; Chang, Ruei-Chuan
The texture of feather is one of the most fascinating, complicated, and beautiful texture patterns in nature. In this paper, we propose a new and effective texture generation approach that uses the traits of iteration behavior to synthesize the textures of Galliformes feathers realistically. We also propose an interactive feather modeling approach which provides a close connection between the user s intuition and the resulting branching pattern. In texturing the feather structure, we use an object-space mapping technique. Experimental results are presented to show the effectiveness of our method.
A Multimedia Constraint System1
(Blackwell Science Ltd and the Eurographics Association, 1995) van Hintum, J.E.A.; Reynolds, G.J.
The MADE constraint system provides excellent opportunities to introduce constraints in a multimedia application. Multimedia applications are not only a good place to experiment with constraint systems- constraints in a multimedia environment are almost indispensable. Due to the overwhelming amount of data and the number of relations between several parts of this data, multimedia applications almost demand the support of a constraint management system.The MADE constraint system combines the object oriented programming paradigm, inherited from the mC++ language, the declarative constraint programming paradigm and the special requirements imposed upon the constraint system by the multimedia environment. Among other things, the MADE constraint system provides parallel satisfaction techniques- several constraints may be solved simultaneously and this satisfaction process is performed in parallel with the application. This not only reduces the time needed to solve the constraints, it also allows the multimedia application to proceed with its presentation while (beneath the surface) the constraints are maintained. This not only holds for the parts of the presentation that are not constrained at all, but also for those parts that are. Furthermore, the constraint system is transparent to the multimedia application- no special coding or preparation of the objects in the application is necessary. Constraints can be added later to the application without much work. Besides that, it is also possible to add and remove constraints at runtime- objects may be constrained for only a period of the time the application is running.
Inverse Displacement Mapping in the General Case
(Blackwell Science Ltd and the Eurographics Association, 1995) Logie, J. R.; Patterson, J. W.
Inverse Displacement Mapping is a form of displacement mapping which allows the ray tracing of displacement mapped surfaces. The technique performs all calculations in the inverse (parametric) space of the surface thus avoiding the need to explicitly model the complex three dimensional geometry. This produces a compact and general algorithm, Only when the solution, in parametric space, has been determined is it transformed back to 3D space. The algorithm works by projecting the ray into the parametric space of the surface. This ray is then split into a series of segments, each of which can be efficiently handled to calculate the intersection points. The algorithm presented here has been used to ray trace displacement mapped objects from a variety of underlying surface types.
A Quick Rendering Method Using Basis Functions for Interactive Lighting Design
(Blackwell Science Ltd and the Eurographics Association, 1995) Dobashi, Yoshinori; Kaneda, Kazufumi; Nakatani, Hideki; Yamashita, Hideo; Nishita, Tomoyuki
When designing interior lighting effects, it is desirable to compare a variety of lighting designs involving different lighting devices and directions of light. It is, however, time-consuming to generate images with many different lighting parameters, taking interreflection into account, because all luminances must be calculated and recalculated. This makes it difficult to design lighting effects interactively. To address this problem, this paper proposes a method of quickly generating images of a given scene illustrating an interreflective environment illuminated by sources with arbitrary luminous intensity distributions. In the proposed method, the luminous intensity ditribution is expressed with basis functions. The proposed method uses a series of spherical harmonic functions as basis functions, and calculates in advance each intensity on surfaces lit by the light sources whose luminous intensity distribution are the same as the spherical harmonic functions. The proposed method makes it possible to generate images so quickly that we can change the luminous intensity distribution interactively. Combining the proposed method with an interactive walk-through that employs intensity mapping, an interactive system for lighting design is implemented. The usefulness of the proposed method is demonstrated by its application to interactive lighting design, where many images are generated by altering lighting devices and/or direction of light.

Browse

Browsing Volume 14 (1995) by Issue Date

Results Per Page

Sort Options