EG1994

Permanent URI for this community

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

Browse

Now showing 1 - 20 of 44

Triangulating multiply-connected polygons: A simple, yet efficient algorithm.
(Blackwell Science Ltd and the Eurographics Association, 1994) Ronfard, Remi P.; Rossignac, Jarek R.
We present a new, simple, yet efficient algorithm for triangulating multiply-connected polygons. The algorithm requires sorting only local concave minima (sags). The order in which triangles are created mimics a flooding process of the interior of the polygon. At each stage, the algorithm analyses the positions and neighborhoods of two vertices only, and possibly checks for active sags, so as to determine which of five possible actions to take. Actions are based on a local decomposition of the polygon into monotonic regions, or gorges (raise the water level in the current gorge, spill into an adjacent gorge, jump to the other bank of a filled gorge, divide a gorge into two, and fill a gorge to its top). The implementation is extremely simple and numerically robust for a large class of polygons. It has been tested on millions of cases as a preprocessing step of a walkthrough and inspection program for complex mechanical and architectural scenes. Extensive experimental results indicate that the observed complexity in terms of the number of vertices, remains under in all cases.
An Integrated Line Tracking and Vectorization Algorithm
(Blackwell Science Ltd and the Eurographics Association, 1994) van Nieuwenhuizen, Peter R.; Kiewiet, Olaf; Bronsvoort, Willem F.
A method is presented to compute a vector representation of an arbitrary line in a bi-level raster image The line may have varying line width and irregular borders. Furthermore, at line crossings and branches the user is offered the opportunity to choose from the directions in which line tracking may he continued The method avoids thinning and vectorization of chain codes. Instead, a contour follower is used at both sides of the line, and median line calculation is integrated with contour following. This leads to an efficient algorithm, in particular when individual lines have to be interactively extracted from a raster image.
Parallel ray tracing based upon a multilevel topological knowledge acquisition of the scene
(Blackwell Science Ltd and the Eurographics Association, 1994) RIS, Philippe; ARQUES, Didier
Including the standard parallelization by grouping primary rays, this paper presents a new parallel ray-timing method based upon a topological knowledge acquisition of the scene. This topological knowledge focuses on relative positions between objects and processes and uses a new type of message. Indeed, instead of exchanging database pages or rays, processes exchange topological information. This information is used by each process to decrease its own list of objects to test against rays The acquisition of information about relative positions between objects and processes is obtained by a careful ordering of he pixel calculation. The processes are dispatched on a computer network including a parallel computer The organization of the processes on this network is a multilevel one leading to different levels of topological message exchanges This method is characterized by topological messages describing the scene, dynamic optimization of the database, easy parallelization on any network (no deadlock, fault tolerance, easily expandable and simple routing), and gives interesting results with true or simulated parallelism.
A Paradigm for the Robust Design of Algorithms for Geometric Modeling
(Blackwell Science Ltd and the Eurographics Association, 1994) Agrawal, Amitabh; Requicha, Aristides A. G.
Geometric modelers are becoming faster and more powerful, but they still suffer from reliability problems because of floating point errors. Previous work in the field of robust geometric modeling tends to be problem specific and has proven hard to generalize. The approach described here is a general paradigm for handling the accuracy problem for a large set of geometric algorithms. This approach brings together ideas and techniques from interval arithmetic, constraint management, randomization, and algebraic geometry. It acknowledges that input values have tolerances, that objects within tolerance are equivalent, and that certain geometric singularities must be maintained because they reflect design intent or the laws of geometry. Our approach is systematic, and can be applied almost mechanically to the large domain of problems that can be solved by algorithms using the operations +, ?, * and /. The required theory and algorithms have been developed, and the viability of the concepts has been demonstrated by an experimental implementation involving linear half-spaces in Euclidean 2-dimensional space. The implementation focuses on algorithms for computing the boundaries of objects defined by Constructive Solid Geometry (CSG) trees.
Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity
(Blackwell Science Ltd and the Eurographics Association, 1994) VOLINO, Pascal; THALMANN, Nadia Magnenat
We present a new algorithm for detecting self-collisionson highly discretized moving polygonal surfaces. If is based on geometrical shape regularity properties that permit avoiding many useless collision tests. We use an improved hierarchical representation of our surface that, besides the optimizations inherent to hierarchisation, allows us to fake adjacency information to our advantage for applying efficiently our geometrical optimizations. We reduce the computation time between each frame by building automatically the hierarchical structure once as a preprocessing task. We describe the main principles of our algorithm, followed by some performance tests.
Fast Wavelet Radiosity Method
(Blackwell Science Ltd and the Eurographics Association, 1994) Pattanaik, Sumanta N.; Bouatouch, Kadi
Wavelet analysis has been found [1] to be very useful for functional representation and accurate global solution of radiosity. In radiosity we deal with functions in 2D and 4D spaces. Under such conditions, the biggest bottleneck in applying this wavelet analysis seems to be the large number of multidimensional inner products. In this paper, we propose (i) the use of interpolating wavelets for fast inner product computation and consequently for faster wavelet radiosity solution (ii) the use of hierarchical decomposition technique for determining the smoothness of the radiosity function for optimal adaptive subdivision.
Chebyshev Polynomials for Boxing and Intersections of Parametric Curves and Surfaces
(Blackwell Science Ltd and the Eurographics Association, 1994) Fournier, Alain; Buchanan, John
Parametric curves and surfaces are powerful and popular modelling tools in Computer Graphics and Computer Aided Design. Ray-tracing is a versatile and popular rendering technique. There is therefore a strong incentive in developing fast, accurate and reliable algorithms to intersect rays and parametric curves and surfaces.We propose and demonstrate the use of Chebyshev basis functions to speed up the computation of the intersections between rays and parametric curves or surfaces. The properties of Chebyshev polynomials result in the computation of better and tighter enclosing boxes. For surfaces they provide a better termination criterion to decide on the limits of subdivision, and allow the use of bilinear surfaces for the computation of the intersection when needed.The efficiency of the techniques used depends on the relative magnitude of the coefficients of the Chebyshev basis functions. We show from a statistical analysis of the characteristics of several thousands surfaces of different origin that these techniques will result most of the time in significant improvement in speed and accuracy over other other boxing and subdivision techniques.
Adaptive mesh generation for progressive radiosity: A ray-tracing based algorithm.
(Blackwell Science Ltd and the Eurographics Association, 1994) PAULIN, Mathias; JESSEL, Jean-Pierre
The radiosity method is one of the most popular rendering algorithms. It allows to simulate interreflections of light accurately between surfaces as energy transfers are well designed. However, this algorithm and its derivatives need to break scenes into a relatively large number of small elements to approximate the illumination function. Even with a very large number of elements, not all the illumination effects can be simulated. In fact, there are always artefacts when modelling sharp shadows, besides shadows falling between mesh vertices can be missed entirely. To reduce the computational cost of such methods and to increase the accuracy of the radiosity solution, adaptive mesh generation is well suited. In this paper, we present a ray-tracing based algorithm for adaptive mesh generation which resolves all the illumination problems without lengthening computation time too much. This method allows a small number of initial elements and increases element density in critical locations while solving the illumination problem.
How to Render Frames and Influence People
(Blackwell Science Ltd and the Eurographics Association, 1994) Strothotte, Thomas; Preim, Bernhard; Raab, Andreas; Schumann, Jutta; Forsey, David R.
Rendering systems generally treat the production of images as an objective process governed by the laws of physics. However, perception and understanding on the part of viewers are subjective processes influenced by a variety offactors. For example, in the presentation of architectural drawings, the apparent precision with which the drawings are made will affect whether the viewer considers the design as part of a preliminary design or as part of a final polished project, and to some extent the level of confidence the viewer has in the encoded information.In this paper we develop techniques for rendering images in a way that differs from the usual photorealistic or wire-frame output of renderers. In particular, our techniques allow a user to adjust the rendering of a scene to produce images using primitives with variable degrees of precision, from approximations that resemble vague"five-minute-sketches" to more mature but still hand-drawn images. We provide a theoretical framework for analysing the information flow from the computer to the user via such images. Finally, we describe the design and implementation of a prototypical renderer and show examples of its output.
Computer Graphics System for Reproducing Three- Dimensional Shape from Idea Sketch
(Blackwell Science Ltd and the Eurographics Association, 1994) Akeo, Makoto; Hashimoto, Hiroshi; Kobayashi, Taisuke; Shibusawa, Tetsuo
This paper describes the technical features and method of implementation of our designer support system which enables reproducing a three-dimensional shape from an idea sketch speedily and modifying the reproduced shape easily, thereby facilitating the consistency of the shape to be checked from a design viewpoint.The designer support system was developed as a tool to cut the time and labor designers have to spend in the design process and help designers to fully display their creativity-the essential attribute of designers.This system uses cross-section lines of an idea sketch of an object drawn by an industrial designer as input data to reproduce automatically a three-dimensional wireframe model of the object by a newly developed three-dimensional graphic algorithm including graphic constraints. In addition, it automatically creates planes by scanning the area enclosed by reproduced curved lines and subjects them to shading. In this process, the dimensions of the object need not be input to the system. The designer can operate the system simply by using the mouse to input appropriate data.Thus, the system permits the designer to easily express his idea in the form of a three-dimensional shape and study idea variations on the display screen without creating a mockup.
COMPUTER GRAPHICS AND REMOTE SENSING - A SYNTHESIS FOR ENVIRONMENTAL PLANNING AND CIVIL ENGINEERING
(Blackwell Science Ltd and the Eurographics Association, 1994) Graf, K.Ch.; Suter, M.; Hagger, J.; Nuesch, D.
This paper presents efforts undertaken in the field of photo-realistic visualization of natural landscapes using digital elevation models (DEM) and images generated by remote sensing techniques. The remote sensing systems used in this work include Landsat Thematic Mapper, SPOT HRV and aerial photographs. After an appropriate preprocessing, including radiometric corrections and image enhancement procedures, a precise geometric correction is performed in order to achieve a very high co-registration of the images with the elevation model. A mosaic of several images at various resolutions is stored together with the DEM in a data set covering an extensive area. These data are then input to an efficient hardware-independent terrain rendering algorithm based on a forward projection. Atmospheric effects can be simulated. The concept of a virtual scene allows an automated embedding of raytraced 3D objects. The results show that these methods can be used in the field of environmental planning, civil engineering and other applications where terrain visualization is required.
Implementing RenderMan - Practice, Problems and Enhancements
(Blackwell Science Ltd and the Eurographics Association, 1994) Slusallek, Philipp; Pflaum, Thomas; Seidel, Hans-Peter
The RenderMan interface has been proposed as a general interface to rendering systems, yet only a few implementations of the interface exist. In this paper we describe the implementation of the RenderMan interface on a general rendering architecture that supports various rendering algorithms. Specifically we discuss the implementation of the RenderMan Shading Language and its integration into our rendering architecture. Special attention is focused on the problems that we have encountered and how they can be solved. Additionally, we suggest extensions and enhancements to the current interface definition, which would make RenderMan easier to implement and more flexible to use.
Skylight for Interior Lighting Design
(Blackwell Science Ltd and the Eurographics Association, 1994) Dobashi, Yoshinori; Kaneda, Kazufumi; Nakashima, Takanobu; Yamashita, Hideo; Nishita, Tomoyuki and Tadamura, Kastumi
It is inevitable for indoor lighting design to render a room lit by natural light, especially for an atelier or an indoor pool where there are many windows. This paper proposes a method for calculating the illuminance due to natural light, i.e. direct sunlight and skylight, passing through transparent planes such as window glass. The proposed method makes it possible to efficiently calculate such illuminance accurately, because it takes into account both non-uniform luminous intensity distribution of skylight and the distribution of transparency of glass according to incident angles of light. Several examples including the lighting design in an indoor pool, are shown to demonstrate the usefulness of the proposed method.
Visualization of Regular Polytopes in Three and Four Dimensions
(Blackwell Science Ltd and the Eurographics Association, 1994) Hausmann, Barbara; Seidel, Hans-Peter
Nontrivial regular polytopes only exist in three and four dimensions. This paper describes a software package that allows to interactively visualize and analyze these regular polytopes. The following four tools are available: Display of the Schlegel diagrams, perspective projections with the possibility of interactively rotating the polytope in three-/four-dimensional space before projection, interactive slicing along various directions, cut-throughs and fold-downs. Various examples illustrate the approach.
A Hand Control and Automatic Grasping System for Synthetic Actors
(Blackwell Science Ltd and the Eurographics Association, 1994) Sanso, Ramon Mas; Thalmann, Daniel
In the computer animation field, the interest for grasping has appeared with the development of synthetic actors. Based on a grasp taxonomy, we propose a completely automatic grasping system for synthetic actors. In particular, the system can decide to use a pinch when the object is too small to be grasped by more than two fingers or to use a two-handed grasp when the object is too large. The system also offers both direct and inverse kinematics to control the articulations. In order to ensure realistic looking closing of the hand, several of the joints are constrained. A brief description of the system and results are also presented.
3D Visualization for 2D GIS: an Analysis of the Users Needs and a Review of Techniques*
(Blackwell Science Ltd and the Eurographics Association, 1994) Giertsen, Christopher; Lucas, Anne
Most of the existing geographical information systems (GIS) make limited use of algorithms for advanced computer graphics and visualization. One explanation is that few attempts are made to identify the visualization needs for different uses of GIS, and to couple such needs to the available algorithms. Another explanation is that most GIS are designed to handle two-dimensional (20) data with few obvious relationships to three-dimensional (30) visualization.In an attempt to provide a better understanding of the application of visualization in GIS, we propose a conceptual framework linking several aspects of the two fields. At the user-level, we link different uses of GIS to different categories of audience and presentation styles. At the level of implementation, we first propose different ways to create 3D data for visualization from 2D GIS data, and then we review algorithms and techniques for 3D visualization with respect to support of different presentation styles.
A Formal Approach to the Specification of Graphic Object Functions
(Blackwell Science Ltd and the Eurographics Association, 1994) Torres, J.C.; Clares, B.
Graphic objects are an abstract mathematical model for graphic systems. The model is an algebraic approach to represent graphic information, which include modelling operations. This formalism require some method to describe normal graphic procedures, such as changing the object colour or texture mapping, as these procedures are essential to represent graphic processes.This paper extends the theory by introducing the concept of graphic object functions. A graphic object function transforms one graphic object into another, changing its visual appearance or its geometric properties. A formal definition of graphic functions is given, with a characterization of two special kinds of graphic object functions: filters and object transference functions. These two kinds of functions can be used to perform normal graphic operations, such as changing colours, texture mapping or clipping.Equivalence relationships between graphic objects induced by functions are also studied. These relationships establish an hierarchical structure on the graphic object set.
Solid Modeling Based on a New Paradigm
(Blackwell Science Ltd and the Eurographics Association, 1994) Yoshida, Norimasa; Shiokawa, Masato; Yamaguchi, Fujio
The technique of solid modeling is essential in CAD/CAM applications, and is currently well established. However, problems remain, such as the lack of uniformity in geometric computations and the lack of stability of Boolean operations of two solids. In this paper, we introduce a theoretical solid modeling system that operates on boundary representations of polyhedral objects and is based on a new paradigm. The characteristics of the system are the following: (I) in Boolean Operations and modeling transformations, all geometric computations are performed by the 4 ? 4 determinant method or the 4 ? 4 matrix method in homogeneous space, which allows the system to avoid division operations, (2) all geometric computations are performed by the exact integer arithmetic, which makes the geometric algorithms stable and simple, and (3) primitive solids are constructed consistently in the integer domain, and the consistency is assured throughout Boolean operations and transformations.
Selective Visualization of Vector Fields
(Blackwell Science Ltd and the Eurographics Association, 1994) van Walsum, Theo; Post, Frits H.
In this paper, we present an approach to selective vector field visualization. This selective visualization approach consists of three stages: selectdon creation, selection processing and selective visualization mapping. It is described how selected regions, called selections, can be represented and created, how selections can be processed and how they can be used in the visualization mapping. Combination of these techniques with a standard visualization pipeline improves the visualization process and offers new facilities for visualization. Examples of selective visualization of fluid flow datasets are provided.
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.

Browse

Browsing EG1994 by Issue Date

Results Per Page

Sort Options