Volume 14 (1995)

Permanent URI for this community

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

Browse

Now showing 1 - 20 of 59

A Graph-Based Approach to Surface Reconstruction
(Blackwell Science Ltd and the Eurographics Association, 1995) Mencl, Robert
A new approach to the reconstruction of a surface from an unorganized set of points in space is presented. The point set may for example be obtained with a laser scanner or a manual digitizing tool, and is the only source of information about the shape of the acquired object. The basic idea is to calculate the Euclidean minimum spanning tree (EMST) of the given points. The EMST is then augmented to the so-called surface description graph (SDG). Finally the wire frame defined by the SDG are filled with triangles. The advantage of our approach is that also highly non-convex and even disconnected surfaces are reconstructed quite reliably. This is demonstrated for a variety of data sets.
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.
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.
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.
The MADE Help System
(Blackwell Science Ltd and the Eurographics Association, 1995) Haindl, Michal; de Ruiter, Behr
MADE is the acronym for the ESPRIT project 6307, whose aim is to develop an object oriented multimedia application development environment. As part of this project the MADE help system is designed to be a distributed hypermedia system with additional support for run-time object monitoring and contextual help.
A Real-time Continuous Alphabetic Sign Language to Speech Conversion VR System
(Blackwell Science Ltd and the Eurographics Association, 1995) Liang, Rung-Huei; Ouhyoung, Ming
Many ways of communications are used between human and computer, while using gesture is considered to be one of the most natural way in a virtual reality system. Because of its intuitiveness and its capability of helping the hearing impaired or speaking impaired, we develop a gesture recognition system. Considering the world-wide use of ASL (American Sign Language), this system focuses on the recognition of a continuous flow of alphabets in ASL to spell a word followed by the speech synthesis, and adopts a simple and efficient windowed template matching recognition strategy to achieve the goal of a real-time and continuous recognition. In addition to the abduction and the flex information in a gesture, we introduce a concept of contact-point into our system to solve the intrinsic ambiguities of some gestures in ASL. Five tact switches, served as contact-points and sensed by an analogue to digital board, are sewn on a glove cover to enhance the functions of a traditional data glove.
Using Procedural RenderMan Shaders for Global Illurnination
(Blackwell Science Ltd and the Eurographics Association, 1995) Slusallek, Philipp; Pflaum, Thomas; Seidel, Hans-Peter
Global illumination techniques like radiosity or Monte-Carlo ray-tracing are becoming standard features of rendering systems. However, there is currently no accepted interface format which supports an appropriate physically-based scene description. In this paper we present extensions to the well-known RenderMan interface, which allow for a physically based scene description and support advanced global illumination techniques. Special emphasis has been laid on the support for procedural descriptions of reflection and emission by RenderMan surface shaders. So far, they could not be used with most global illumination algorithms. The extensions have been implemented in a physically-based rendering system and are illustrated with examples.
A rational model of the surface swept by a curve*
(Blackwell Science Ltd and the Eurographics Association, 1995) Johnstone, John K.; Williams, James P.
This paper shows how to construct a rational Bezier model of a swept surface that interpolates N frames (i.e., N position/orientation pairs) of a fixed rational space curve c(s) and maintains the shape of the curve at all intermediate points of the sweep. Thus, the surface models an exact sweep of the curve, consistent with the given data. The primary novelty of the method is that this exact modeling of the sweep is achieved without sacrificing a rational representation for the surface. Through a simple extension, we also allow the sweeping curve to change its size through the sweep. The position, orientation, and size of the sweeping curve can change with arbitrary continuity (we use C2 continuity in this paper). Our interpolation between frames has the classical properties of Bezier interpolation, such as the convex hull property and linear precision.This swept surface is a useful primitive for geometric design. It encompasses the surface of revolution and extruded surface, but extends them to arbitrary sweeps. It is a useful modeling primitive for robotics and CAD/CAM, using frames generated automatically by a moving robot or tool.
An Incremental Alignment Algorithm for Parallel Volume Rendering
(Blackwell Science Ltd and the Eurographics Association, 1995) Or, Daniel Cohen; Fleishman, Shachar
This paper introduces a data distribution scheme and an alignment algorithm for parallel volume rendering. The algorithm performs a single wrap-around shear transformation which requires only a regular inter-processor communication pattern. The alignment can be implemented incrementally consisting of short distance shifts, thus significantly reducing the communication overhead. The alignment process is a non-destructive transformation, consisting of a single non-scaling shear operation. This is a unique feature which provides the basis for the incremental algorithm.
Image Warping Using Few Anchor Points and Radial Functions
(Blackwell Science Ltd and the Eurographics Association, 1995) Arad, Nur; Reisfeld, Daniel
Transformations based on radial basis junctions have proven to be a powerful tool in image warping. In the present work we decompose these transformations into linear and radial terms, and show examples where such a decomposition is advantageous. Locally supported basis functions are introduced. Several applications are demonstrated, and a comparison with other warping techniques is carried out. Finally, some fine points of image warping are discussed.
An Algorithm for Perspective Viewing of Objects Represented by Octrees
(Blackwell Science Ltd and the Eurographics Association, 1995) Aref, Walid G.; Samet, Hanan
A new algorithm is presented for viewing three-dimensional objects, represented by an octree, from an arbitrary location. The algorithm generates aperspective view of the objects while eliminating hidden surfaces. The viewer can be located anywhere inside or outside the objects. The algorithm presented in this short notefixes an artifact that is generated by a previously published algorithm due to Meagher when the viewer is located in certain regions in space. The new algorithm traverses the octree in a back-to-front order and recursively chooses correct orders for visiting the sons of non-leaf nodes.
Synthetic Vision and Audition for Digital Actors
(Blackwell Science Ltd and the Eurographics Association, 1995) NOSER, Hansrudi; THALMANN, Daniel
We present an overview of some principles of synthetic vision and audition for digital autonomous actors in virtual worlds. After a short review of the state-of-the-art we focus on some aspects of synthetic vision and virtual world constraints. Then, we present a simple real time structured sound renderer. This sound renderer is used as audition channel for synthetic and real actors and synchronized sound track generator for video film productions.
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.
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.
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.
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.
Sketching 3D Animations
(Blackwell Science Ltd and the Eurographics Association, 1995) Balaguer, Jean-Francis; Gobbetti, Enrico
We are interested in providing animators with a general-purpose tool allowing them to create animations using straight-ahead actions as well as pose-to-pose techniques. Our approach seeks to bring the expressiveness of real-time motion capture systems into a general-purpose multi-track system running on a graphics workstation. We emphasize the use of high-bandwidth interaction with 3D objects together with specific data reduction techniques for the automatic construction of editable representations of interactively sketched continuous parameter evolution. In this paper, we concentrate on providing a solution to the problem of applying data reduction techniques in an animation context. The requirements that must be fulfilled by the data reduction algorithm are analyzed. From the Lyche and Morken knot removal strategy, we derive an incremental algorithm that computes a B-spline approximation to the original curve by considering only a small piece of the total curve at any time. This algorithm allows the processing of the user s captured motion in parallel with its specification, and guarantees constant latency time and memory needs for input motions composed of any number of samples. After showing the results obtained by applying our incremental algorithm to 3D animation paths, we describe an integrated environment to visually construct 3D animations, where all interaction is done directly in three dimensions. By recording the effects of user s manipulations and taking into account the temporal aspect of the interaction, straight-ahead animations can be defined. Our algorithm is automatically applied to continuous parameter evolution in order to obtain editable representations. The paper concludes with a presentation offuture work.

Browse

Browsing Volume 14 (1995) by Issue Date

Results Per Page

Sort Options