Volume 13 (1994)
Permanent URI for this community
Browse
Browsing Volume 13 (1994) by Issue Date
Now showing 1 - 20 of 69
Results Per Page
Sort Options
Item 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.Item 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.Item Parallel ray tracing based upon a multilevel topological knowledge acquisition of the scene(Blackwell Science Ltd and the Eurographics Association, 1994) RIS, Philippe; ARQUES, DidierIncluding 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.Item 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.Item A New Real Time Geometric Transformation Matrix and its Efficient VLSI Implementation(Blackwell Science Ltd and the Eurographics Association, 1994) Ng, C. M.; Bustard, D. W.The geometric transformation of an image with irregular shapes from a source space to a target space requires a huge number of multiplications and additions for each pixel. Such a through put is impossible to deliver by any processor in real-time. This paper presents a new transformation matrix which can be used toper form real-time 2-D geometric transformations economically. The implementation of the transformation engine that is used to execute the transformation matrix is also presented. Experimental results indicate that real-time geometric transformations based on a 4 ? 4 transformation mesh can be achieved with the use of the transformation engine. This real-time transformation function is useful in warping and blending of images, and can be easily extended to perform irregular shape transformations with a large number of control points in the transformation mesh.Item Classification of Ray-Generators in Uniform Subdivisions and Octrees for Ray Tracing(Blackwell Science Ltd and the Eurographics Association, 1994) Endl, Robert; Sommer, ManfredSpatial subdivisions cause an enormous acceleration of ray tracing due to the reduction of ray-object intersections. For this purpose it is necessary to generate the sequence of ray-cells (all cells met consecutively by a given ray). A method generating this sequence will be called a ray-generator. First this paper analyses the common properties of ray-generators in order to establish a classification. Then some well-known ray- generators are described and classified, as well as some new ones. In the sequel nine different ray-generators are implemented in one single program allowing direct comparisons with the same scene. Finally, global time measurements for two scenes are given, as well as time measurements for random rays enabling the calculation of mean values for the time of initialization and determination of ray-cells.Item 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 MagnenatWe 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.Item Strands, Gravity and Botanical Tree Imagery(Blackwell Science Ltd and the Eurographics Association, 1994) Holton, MatthewThis paper presents a technique for the modelling and rendering of realistic botanical tree images. A strand model is used that is analogous to the internal vascular structure of a tree. The model is"grown" under the simulated influence of gravity and light. The strand densities at each branching point are used to determine branching angles, branch lengths and branch thicknesses, taking into account stored, user definable parameters that characterize the species of tree being modelled. These parameters address such factors as gravimorphism, phototropism, orthotropism, plagiotropism, planartropism and phyllotaxis, and are distributed according to a branch ordering system.Branch segments and joints are modelled by Bezier splines, with an assumed circular cross-section. Leaves are made up from numbers of sample ranges from vector plane equations. The trees are rendered using a surface sampling algorithm with a light Z buffer for shadows and autoregression textures for tree bark and grass.Item Fast Wavelet Radiosity Method(Blackwell Science Ltd and the Eurographics Association, 1994) Pattanaik, Sumanta N.; Bouatouch, KadiWavelet 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.Item Chebyshev Polynomials for Boxing and Intersections of Parametric Curves and Surfaces(Blackwell Science Ltd and the Eurographics Association, 1994) Fournier, Alain; Buchanan, JohnParametric 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.Item Adaptive mesh generation for progressive radiosity: A ray-tracing based algorithm.(Blackwell Science Ltd and the Eurographics Association, 1994) PAULIN, Mathias; JESSEL, Jean-PierreThe 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.Item Contextual Animation of Gestural Commands(Blackwell Science Ltd and the Eurographics Association, 1994) Kurtenbach, G.; Moran, T. P.; Buxton, W.Drawing a mark can be an efficient command input technique when using a pen-based computer. However, marks are not intrinsically self-explanatory as are other interactive techniques such as buttons and menus. We present design principles for interaction mechanisms which make marks self explanatory for novices but still allow experts to use efficient command marks. The key notion is that use of the explanation mechanism physically trains a novice to use the efficient command marks. Two novel interaction mechanisms we have developed using these principles are presented.Item The Design and Specification of a Visual Language: An Example for Customising Geographic Information Systems Functionalities(Blackwell Science Ltd and the Eurographics Association, 1994) Paterna , F.; Campari, I.; Scopigno, R.In this paper the design of a visual program editor and its specification using formal grammars are discussed. We consider an environment to specify, analyse and execute visual programs for a Geographical Information System (GIS). The lack of sophisticated user interfaces is one of the major drawbacks to Geographical Information Systems, particularly for people without a sound background in computer science. The use of a visual language approach is useful in order to hide the plethora of basic GIS functions, while providing ready- to-use tools to solve users tasks. The visual environment provides users with higher level interfaces- it is based on the module concept, which is conceived as a software building block that implements a solution to a general basic task and is presented to the user through an interactive frame. Complex GIS queries can be carried out by interconnecting modules into flow networks, using a direct manipulation approach.Item 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.Item 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, TetsuoThis 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.Item 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.Item Implementing RenderMan - Practice, Problems and Enhancements(Blackwell Science Ltd and the Eurographics Association, 1994) Slusallek, Philipp; Pflaum, Thomas; Seidel, Hans-PeterThe 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.Item Experiments in the Parallel Computation of 3D Convex Hulls(Blackwell Science Ltd and the Eurographics Association, 1994) Claret, A.R.; Day, A.M.Two parallel implementations of a 3D convex hull algorithm are reported. The paper considers a MIMD distributed memory architecture and the implementations are carried out on the Meiko Computing Surface using T800 transputers and the programming languages Occam and C. The first method uses a simple parallel geometric decomposition strategy and produces encouraging results. With the second approach a parallel generic Divide-and-Conquer kernel is incorporated. This is an example of the algorithmic skeleton approach to parallel programming and involves run-time, dynamic allocation of work to processors. The resulting performances for both methods are measured and compared.Item 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, KastumiIt 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.Item Constant-Time Filtering by Singular Value Decomposition?(Blackwell Science Ltd and the Eurographics Association, 1994) Gotsman, CraigWe present a technique implementing space-variant filtering of an image, with kernels belonging to a given family, in time independent of the size and shape of the filter kernel support. The essence of our method is efficient approximation of these kernels, belonging to an infinite family governed by a small number of parameters, as a linear combination of a small number k of"basis" kernels. The accuracy of this approximation increases with k, and requires O(k) storage space. Any kernel in the family may be applied to the image in O(k) time using precomputed results of the application of the basis kernels. Performing linear combinations of these values with appropriate coefficients yields the desired result. A trade off between algorithm efficiency and approximation quality is obtained by adjusting k.The basis kernels are computed using singular value decomposition, distinguishing this from previous techniques designed to achieve a similar effect. We illustrate by applying our methods to the family of elliptic Gaussian kernels, a popular choice for filtering warped images.