EG1987 Proceedings (Technical Papers)
Permanent URI for this collection
A Fast Ray Tracing Algorithm Using Space Indexing Techniques
[meta data] [files:
Qunsheng, Peng
;
Zhu, Yining
;
Liang, Youdong
Parallel Polygon Rendering with Precomputed Surface Patches
[meta data] [files:
Theoharis, Theoharis
;
Page, Ian
A New Algorithm of Space Tracing Using a CSG Model
[meta data] [files:
Bouatouch, Kadi
;
Madani, M.O.
;
Priol, Thierry
;
Arnaldi, Bruno
A Fast Voxel Traversal Algorithm for Ray Tracing
[meta data] [files:
Amanatides, John
;
Woo, Andrew
A Window Managment System on Top of GKS
[meta data] [files:
Hartelt, Helga I.M.
;
Magalhaes, Leo Pini
;
Daltrini, Beatriz Mascia
Extraction and Organization of Form Features into a Structured Boundary Model
[meta data] [files:
Falcidieno, Bianca
;
Giannini, Franca
An Interactive Graphic Simulator for the Teaching of Fibrendoscopic Techniques
[meta data] [files:
Gillies, Duncan
;
Williams, Christopher
Parallel Graphical Output from Dialogue Cells
[meta data] [files:
Ten Hagen, P.J.W.
;
Schouten, H.J.
A VLSI System Architecture for High-Speed Radiative Transfer 3D Image Synthesis
[meta data] [files:
Bu, Jichun
;
Deprettere, Ed F.
The Reconstruction of Neurone Morphology from Thin Optical Sections - Graphical Aspects
[meta data] [files:
Brown, A. D.
;
Wheal, H. V.
;
Stockley, E. W.
Extended Octtrees, between CSG Trees and Boundary Representations
[meta data] [files:
Navazo, Isabel
;
Fontdecaba, Josep
;
Brunet, Pere
Unifying Vector and Polygon Algorithms for Scan Conversion and Clipping
[meta data] [files:
Kilgour, AIistair
The Clockworks: An Object-Oriented Computer Animation System
[meta data] [files:
Breen, David E.
;
Getto, Phillip H.
;
Apodaca, Anthony A.
;
Schmidt, Daniel G.
;
Sarachan, Brion D.
Display of Solid Models with a Multi-Processor System
[meta data] [files:
Jansen, Frederik W.
;
Sutherland, Robert J.
Viz: A Production System Based User Interface Management System
[meta data] [files:
van Harmelen, Mark
;
Wilson, Stephanie M.
Designing a System to Provide Graphical User Interfaces: The THESEUS Approach
[meta data] [files:
Huebner, W.
;
Lux-Mulders, G.
;
Muth, M.
A Temporal Scripting Language for Object-Oriented Animation
[meta data] [files:
Fiume, E.
;
Tsichritzis, D.
;
Dami, L.
A Metric for Computing Adaptive Detail in Animated Scenes Using Object-Oriented Programming
[meta data] [files:
Blake, Edwin H.
3D Models in Computer-Assisted Chemistry
[meta data] [files:
Roch, Michel
;
Cretegny, Isabelle
;
Weber, Jacques
A New Scan Line Algorithm for the Rendering of CGS Trees
[meta data] [files:
Pueyo, Xavier
;
Mendoza, Joan Carles
A Means to Improve the GKS-3D/PHIGS Output Pipeline Implementation
[meta data] [files:
Herman, Ivan
;
Reviczky, Janos
Bezier Patches with Local Shape Control Parameters
[meta data] [files:
Schmitt, Francis J. M.
;
Du, Wen-Hui
Efficient and Consistent Algorithms for Determining the Containment of Points in Polygons and Polyhedra
[meta data] [files:
Chen, Min
;
Townsend, Teeter
An Automatic Interpolation Method of Grayvalued Images Utilizing Density Contour Lines
[meta data] [files:
Agui, Takeshi
;
Saito, Minoru
;
Nakajima, Masayuki
;
Arai, Yukihiro
An Approach to the Formal Specification of Configurable Models of Graphics Systems
[meta data] [files:
Arnold, D.B.
;
Duce, D.A.
;
Reynolds, G.J
HIRASP: A Hierarchical Interactive Rastergraphics System Based on Pattern Graphs and Pattern Expressions
[meta data] [files:
Teunissen, Wim J.M.
;
van den Bos, Jan
A Shareable Centralised Database of KRT3 - A Hierarchical Graphics System Based on PHIGS
[meta data] [files:
Howard, Toby
A Fast Antialiasing Method with a Z-Buffer
[meta data] [files:
Ghazanfarpour, Djamchid
;
Peroche, Bernard
Interaction Management in CAD Systems with History Mechanism
[meta data] [files:
Yamaguchi, Yasushi
;
Kimura, Fumihiko
;
Ten Hagen, Paul J. W.
Browse
Recent Submissions
Item COLOUR SECTION(Eurographics Association, 1987) -Item A Fast Ray Tracing Algorithm Using Space Indexing Techniques(Eurographics Association, 1987) Qunsheng, Peng; Zhu, Yining; Liang, YoudongA fast ray tracing algorithm is presented. Spatial coherency is exploited by adopting a linear octree data structure which corresponds to an adaptive partitioning of space. A ray strides over a number of empty regions aligning on its way and intersects the desired objects directly, Efficiency of the algorithm is achieved by decreasing the number of regions that the ray must be checked with, by reducing the computations involved in skipping an empty region and by performing a binary search to find the next region. An efficient algorithm based on linear programming for mapping the whole environment into a sorted linear octree is also described. Only the terminal nodes containing boundary surfaces of objects are explicitly represented, which not only shortens the searching process but also leads to a considerable saving on storage space.Item Parallel Polygon Rendering with Precomputed Surface Patches(Eurographics Association, 1987) Theoharis, Theoharis; Page, IanWe describe an algorithm for rendering a restricted class of trapeziums, and hence arbitrary polygons, in parallel on an NxN SIMD array processor. The algorithm achieves good performance by precomputing “surface patches” (finite portions of half -planes), thus trading storage for increased speed. The number of surface patches that are precomputed grows only linearly with the size of the array processor but as the square of the subpixel accuracy desired. NxN texture patterns can be added at very little extra cost additional to filling a trapezium with a particular colour.Item GOCS - The GKS-oriented Communication System(Eurographics Association, 1987) Egelhaaf, Chr.; Schuermann, G.We present a system which offers a distributed GKS in an open network. The GKS kernel and the workstations are located on different hosts. There is no restriction to the full level 2b functionality of GKS due to the distribution. The workstation interface WSI and the communication modules, which are based on the transport protocol T.70, are discussed.Item A New Algorithm of Space Tracing Using a CSG Model(Eurographics Association, 1987) Bouatouch, Kadi; Madani, M.O.; Priol, Thierry; Arnaldi, BrunoThis paper describes a new algorithm of space tracing. Scenes are modeled by a CSG tree. Space is subdivided regularly into 3D regions called boxes. With each box is associated a subtree which is the restriction of the whole scene CSG tree to primitives belonging to this box. A 3D grid is used to access boxes.Item A Fast Voxel Traversal Algorithm for Ray Tracing(Eurographics Association, 1987) Amanatides, John; Woo, AndrewA fast and simple voxel traversal algorithm through a 3D space partition is introduced. Going from one voxel to its neighbour requires only two floating point comparisons and one floating point addition. Also, multiple ray intersections with objects that are in more than one voxel are eliminated.Item Conformal Texture Mapping(Eurographics Association, 1987) Fiume, E.; Fournier, A.; Canale, V.A new class of geometric mappings is introduced to computer graphics, and the utility of this class is illustrated by applying it to texture mapping. When mapping a texture onto a surface such as a polygon, the entire texture can rarely be mapped without some clipping or non-linear transformation. Is it possible to map a texture bijectively to an arbitrary polygon such that the entire texture is mapped? This paper presents a solution to this problem. A new class of mapping techniques based on conformal mapping is proposed. The technique allows one to construct a continuous, bijective map from a polygonal texture space (e.g., a square) to an arbitrary convex polygon. The resulting map is texture-independent. The theory and .an implementation of conformal texture mapping is discussed, and several simple filtering techniques to support it are outlined. Conformal mapping extends the range of geometric mapping techniques, and is pertinent to many areas of computer graphics. Other examples of the potential utility of conformal mappings are also discussed.Item Experiences in Implementing Postscript(Eurographics Association, 1987) Goswell, Crispin A. A.This paper describes an implementation of POSTSCRIPT for previewing use on workstations with high resolution bitmapped displays. It discusses implementation of storage management, area fill and line drawing, imaging, fonts and font caching. Treatment of bezier curves and dashing is explained. Area fill involves both the even-odd and non-zero winding number rules, so implementation of both of these using trapezoid decomposition is described. There is also a discussion of an object-oriented implementation of polymorphism in POSTSCRIPT. This results in a flexible and user extensible system. Error handling is discussed, because its implementation has a considerable effect on the design of the virtual machine. Various hints are given on improving performance, including caching fonts on disk, treating thin lines specially and magnifying images. Most displays have only two intensities, so there is some discussion of half-toning for gray level simulation, and the extensive options that POSTSCRIPT supports for half-tone design. Finally there is a brief discussion of porting experiences with the interpreter. It is written in the C language and runs on the UNIX operating system, on Perqs, Suns and WhiteChapels.Item A Window Managment System on Top of GKS(Eurographics Association, 1987) Hartelt, Helga I.M.; Magalhaes, Leo Pini; Daltrini, Beatriz MasciaThis paper presents a Window Management System, GAV, which utilizes a GKS Graphics System as a supporting tool. GAV allows the definition, by the users (designers of application programs), of several areas of visualization in the same screen. Each of these areas is a workstation according to the concept of workstation established in GKS. GAV even allows different parts of application programs to be done by different users. These users can use the full set of GKS functions in each part, without worrying about the existence of the other parts, Finally, GAV allows the grouping of workstation in sets called screen configurations. Advantages and disadvantages of the adopted solution to the problem of constructing a Window Management System are discussed.Item Extraction and Organization of Form Features into a Structured Boundary Model(Eurographics Association, 1987) Falcidieno, Bianca; Giannini, FrancaA method is presented for the automatic identification and extraction of feature information from the solid model of an object. The procedure consists of recognizing shape features, extracting those features as solid volumes and arranging them in a hierarchical structure. In this hierarchical model the main shape of the object is represented at the highest levels of abstraction, while form features are described at lower levels of specification. The system is divided into three modules: feature recognition, feature extraction and feature organization. The recognition step works on a face-based representation of solid objects, called Face Adjacency Hypergraph [1] and it takes advantage of the Kyprianou's method [12]. In the extraction phase every recognized form feature is completed with dummy entities to form a feasible object and in the organization step the completed features are arranged in a hierarchical graph, called Structured Face Adjacency Hypergraph, which is a modification of a model defined in a previous work [1].Item An Algorithm for 3D Scan-Conversion of Polygons(Eurographics Association, 1987) Kaufman, ArieA three-dimensional (3D) scan-conversion algorithm, that scanconverts 3D planar polygons into their discrete voxel-map representation within a Cubic Frame Buffer (CFB), is presented. The algorithm, which is a variation of a 2D scan-line filling algorithm, is incremental and uses only simple operations like additions and testy inside the inner loops. The algorithm performs scan-conversion with computational complexity which is linear in the number of voxels written to the CFB. The paper also presents an algorithm that scan-converts polygons clipped to the CFB boundaries with no added time complexity. An all-integer decision mechanism which makes the inner-most loop of the algorithm more efficient is discussed too. All the algorithms guarantee lack of 6-connected "tunnels" in the converted polygons. The algorithms have been implemented as part of the 3D geometry processor of the CUBE Architecture, which is a voxel-based system for 3D graphics. These algorithms allow the' CUBE system to generate the essential primitive polygon within the CFB from a 3D geometric model.Item Real-Time Scan-Line In-Fill(Eurographics Association, 1987) Allerton, D. J.; Evemy, J. D.; Zaluska, E. J.A novel algorithm is described to perform in-fill of wire-frame polygons, typically for application in visual systems for flight simulation. Post-processing is performed on an image formed in a conventional raster-scan framestore using edge-detection in scan-line order. A prototype real-time implementation of this algorithm is operational and is also presented.Item Active-Ray Tracing for 3D Medical Imaging(Eurographics Association, 1987) Trousset, Yves; Schmitt, FrancisLarge quantities of three-dimensional (3D) information are produced by 3D medical imaging techniques such as CT and MRI, in the form of digital volumes (DV). We propose a new approach to help a human observer to visualize these volumes. This approach is based on the idea that, in order to achieve true user-interaction, segmentation and visualization should not be treated separately. This is achieved by introducing active ray tracing, a method inspired by ray tracing but working directely on unsegmented digital volumes. Segmentation takes place as the active rays penetrate through the volume.Item An Interactive Graphic Simulator for the Teaching of Fibrendoscopic Techniques(Eurographics Association, 1987) Gillies, Duncan; Williams, ChristopherA simulator has been designed and implemented for teaching the skills required for fibrendoscopic investigation of the colon. The student using the simulator manipulates a dummy endoscope control head in which the rotary and linear movements are converted to voltages and interfaced to the computer via analogue to digital converters. The simulator is based on a three dimensional computer model of the colon and endoscope. The program reads the endoscope controls, determines the position of the tip of the endoscope, and using this as viewpoint draws the appropriate view. In the worst case, the whole cycle takes 0.185 seconds on an ordinary IBM PC, giving a frame rate of just under 6/sec.Item Parallel Graphical Output from Dialogue Cells(Eurographics Association, 1987) Ten Hagen, P.J.W.; Schouten, H.J.A system that accepts and processes graphical output from parallel processes using a single workstation, and its use in a User Interface Management System called Dialogue Cells, is described. It allows for a programmer to easily, concisely and precisely describe pictures and operations on them in a highly interactive environment. Each parallel process can do output independently, but pictures can also be moved from one process to another. Each process has its own graphical output environment. The description and implementation of the system is based on GKS.Item A VLSI System Architecture for High-Speed Radiative Transfer 3D Image Synthesis(Eurographics Association, 1987) Bu, Jichun; Deprettere, Ed F.In this paper we present a VLSI system architecture for high-speed synthesis of 3D images composed of diffusely reflective surfaces. The system consists of two loosely coupled sub-systems. The first sub-system computes the form-factor matrix F. The form-factor computation is based on the hemi-cube approximation technique, where the patch-to-hemi-cube projections are computed by an efficient ray-tracing algorithm. The second sub-system, a multiprocessor Gauss-Seidel iterative system solver, solves the sparse system of radiosity equations (I-AF)b=e. The described system is suitable for VLSI implementation. Pipelined CORDIC processors are used in the first sub-system, and pipelined multiplier/accumulator processors are used in the second sub-system.Item Interactive Generation of Fractal Objects(Eurographics Association, 1987) Kaandorp, J. A.In this paper a description is given of the development of data structures by which a large class of fractal objects can be represented using production rules, together with an algorithm to generate these objects. These data structures and algorithm can be used to produce many of the classical, examples of self-similar sets, mentioned for example by Mandelbrot [13]. The algorithm and data structures are part of a fractal system by which production rules can be designed; production rules can be retrieved from and stored in a fractal library.Item Generative Scene Modelling(Eurographics Association, 1987) Beyer, Thomas; Friedell, MarkWe describe a new theory of scene modelling that includes generative processes as integral components of scene descriptions. A single, uniform treatment of generative processes replaces the variety of ad hoc mechanisms commonly in use. We discuss the implementation of the theory in an experimental modelling system and show that L-systems, fractals, and particle systems, as well as many specialized generative processes, become comparatively easy to define and use.Item Shape Approximation by a Fractal Model(Eurographics Association, 1987) Levy-Vehel, J.; Gagalowicz, A.The use of fractals to synthesize complex objects is of current interest in the computer graphics community. A powerful way to compute fractals is the use of IFS (iterated function system) which is a set of contractions with associated probabilities which characterize the fractal. This theory, developed by M. Barnsley and al., can produce very complicated objects. We present a method to solve the inverse problem for these globally constructed fractals : given a set A (attractor), find an IFS that will approximately generate A. We use an optimisation method to minimize a distance between A and the current set L. Several distances have been tested and an algorithm has been implemented which gives good results. A test image is presented.Item The Reconstruction of Neurone Morphology from Thin Optical Sections - Graphical Aspects(Eurographics Association, 1987) Brown, A. D.; Wheal, H. V.; Stockley, E. W.The aims of the project are two-fold: firstly, to create an accurate three-dimensional model of a neurone from the mammalian nervous system, which can be used to obtain quantitative geometric and topological data on the neurone, and secondly, to create a software simulation of an active neurone, that accurately mirrors the electrochemical responses of a real, living mammalian neurone to external excitations and to changes in its electrochemical ambient. The focus of this paper is the first of these two goals. Portions of brain tissue are prepared, containing stained neurones. Using an optical sectioning technique, these neurones can be photographed in two-dimensional slices, down to about 10um thick. These photographs are digitised, and input to a computer. The system reconstructs the three-dimensional structure of the neurone, and provides a number of ways of displaying the reconstruction.Item Extended Octtrees, between CSG Trees and Boundary Representations(Eurographics Association, 1987) Navazo, Isabel; Fontdecaba, Josep; Brunet, PereBesides the most widely used models in the Geometric Modeling Systems, Constructive Solid Geometry (CSG) and Boundary Representations (BR), Octtrees have appeared as an alternative representation scheme which is particularly well suited for the solid boolean operation algorithms. Extended Octtrees, which incorporates three additional node types containing part of the surface of the object, are much more compact and allow the exact representation of plane faced objects, while supporting also low complexity algorithms for boolean operations. Due to the limitations of the two main models, CSG and Boundary Representation , a number of Hybrid Systems have appeared, which support both schemes and perform every operation in the most suitable model. However, algorithms for the boundary evaluation of CSG trees are complex, and at the moment little is known on algorithms for the inverse conversion, from BR to CSG. In the present paper, the use of the Extended Octtree model as an intermediate tool in the conversions between. CSG trees and BR is studied. In the case of CSG trees build from primitives with plane faces, an algorithm for the conversion from the CSG model to the Extended Octtree representation is presented. Its complexity is linear with respect to the numbe of nodes in the Octtree. The use of this algorithm in model-to-model conversions is discussed, together with the BR to Extended Octtree and Extended Octtree to BR conversion algorithms, that present also linear complexity with respect to the total number of nodes.Item Unifying Vector and Polygon Algorithms for Scan Conversion and Clipping(Eurographics Association, 1987) Kilgour, AIistairIn both scan conversion and clipping, algorithm for dealing with polygons are generally presented independently of those for vectors, although many of the operations performed are similar. This paper shows how polygon algorithms for both problems can be developed from the corresponding vector algorithm. As well as yielding a unification at the conceptual level, this approach can lead to reduced code size in graphics system implementation, and produces polygon algorithms which are comparable in both robustness and efficiency with those previously presented.Item The Clockworks: An Object-Oriented Computer Animation System(Eurographics Association, 1987) Breen, David E.; Getto, Phillip H.; Apodaca, Anthony A.; Schmidt, Daniel G.; Sarachan, Brion D.The Clockworks is an object-oriented computer animation system developed at RPl's Center for Interactive Computer Graphics (CICG). The Clockworks has the ability to model and graphically simulate complex 3-D engineering processes, Its interactive capabilities also allow it be used as a design tool. Object-oriented concepts have been utilized in developing its high level architecture and its low level implementation. The Clockworks is defined as a collection of objects which communicate with the user and each other via messages. The actual implementation involved the creation of an object-oriented programming methodology using C and Unix. The complete system provides a rich research environment for exploring modelling, scripting and rendering. It also provides an interactive environment for design and a simulation environment for visual analysis of complex interacting structures.Item Display of Solid Models with a Multi-Processor System(Eurographics Association, 1987) Jansen, Frederik W.; Sutherland, Robert J.There is a growing need for fast high-quality display of solid objects. Recently-developed custom-VLSI hardware offers high-speed display but lacks the flexibility and processing power at the pixel level to sustain the calculations and filter operations needed for realistic reflection models, texture mapping and anti-aliasing. Multi-processor systems built with general-purpose components of relatively high capacity and moderate cost provide an alternative; they also offer higher performance than single processor systems but retain their flexibility. A CSG hidden-surface algorithm based on depth-buffering and image subdivision is presented which is suitable for use with such a multi-processor system.Item Viz: A Production System Based User Interface Management System(Eurographics Association, 1987) van Harmelen, Mark; Wilson, Stephanie M.A production system based User Interface Management System (UIMS) is discussed. The UIMS, called Viz, has been designed and implemented in a windowed workstation environment, and (a) capitalises on the graphical facilities of the workstation while (b) being designed for both textual and graphical applications. The paper considers interaction, the appearance of Viz generated interfaces, and dialogue descriptions which parameterise Viz.Item Designing a System to Provide Graphical User Interfaces: The THESEUS Approach(Eurographics Association, 1987) Huebner, W.; Lux-Mulders, G.; Muth, M.This paper presents the design of THESEUS, a system for programming graphical user interfaces especially targetted at the area of software engineering. Starting with the special needs and requirements that arise in this area, the design alternatives for such a system - abstraction level of the programming interface, division of control and dialogue specification - are discussed. The decisions that resulted in the layer model of THESEUS are substantiated. THESEUS offers an application-oriented programming interface supporting a user interface with multiple windowing, graphics and modem interaction techniques. The dialogue control mechanisms,' event driven input management and the definition of hierarchical object-oriented output are described in detail. Experience with a first implementation is also presented.Item A Temporal Scripting Language for Object-Oriented Animation(Eurographics Association, 1987) Fiume, E.; Tsichritzis, D.; Dami, L.Object orientation and concurrency are inherent to computer animation. Since the pieces of an animation can come from various media such as computer-generated imagery, video, and sound, the case for object orientation is all the stronger. However, languages for expressing the temporal co-ordination of animated objects have been slow in coming. We present such a language in this paper. Since the movements that an animated object can perform are also encapsulated as objects in our system, the scripting language can also be used to specify motion co-ordination. Such \u2018 motion objects\u201d can be applied to any animated object. The syntax, semantics, and implementation of this language will be described, and we shall show how to specify device-independent computer animation.Item A Metric for Computing Adaptive Detail in Animated Scenes Using Object-Oriented Programming(Eurographics Association, 1987) Blake, Edwin H.A spatial metric for adapting the level of detail in a modelled object to achieve a convincing degree of realism on a display is formulated and illustrated with a simple implementation. This spatial metric is designed to be of most benefit to animations of natural environments. The metric can operate with a wide range of different representations: the essential requirement being that an abstract data structure with hierarchical levels of detail is formulated. Such models are most easily implemented with procedural recursive representations, such as fractals. The actor/message passing approach to modelling animation is adopted as being most appropriate and intuitive when simulating the objects and events of the natural environment. This object-oriented programming method also gives a uniform abstract interface to differing data representations. A stick figure, which has a non-uniform hierarchical structure, was chosen for the first implementation. This prototype was implemented in Smalltalk which had to be extended to include a part-whole (assembly-subassembly) hierarchy. The need to extend the metric to include temporal (dynamic) trade-offs is discussed.Item 3D Models in Computer-Assisted Chemistry(Eurographics Association, 1987) Roch, Michel; Cretegny, Isabelle; Weber, JacquesNovel and efficient algorithms have been developed in order to display on a raster scan device some basic 3D models used in computer-assisted chemistry. They allow, among other things, the construction and manipulation of the geometrical structure, or shape, of chemical species containing several hundreds of atoms, both as simple skeleted and sophisticated 3D space filling models with Gouraud shading and hiddensurface treatment. In addition, the technique of image storing is used in order to simultaneously display the molecular model and both 2D (colorfilled contour levels) and 3D (solid model) representations of chemical properties of the compound. The images thus generated allow an immediate perception of the major features of the species under study, which provides the chemist with an invaluable tool in computer-assisted chemistry. Some simple examples, which illustrate the potential of these 3D models for discussing chemical reactivity, are presented. Finally, the algorithms and procedures used for constructing the 3D images are briefly described and discussed. *Correspondence address: Dr J. Weber, Laboratory of Computational Chemistry, University of Geneva, 30 quai Ernest Ansermet, 1211 Geneva 4, SwitzerlandItem A New Scan Line Algorithm for the Rendering of CGS Trees(Eurographics Association, 1987) Pueyo, Xavier; Mendoza, Joan CarlesA scan line algorithm is proposed to render CSG modelled solids. Scan planes intersections are obtained by means of a proposed generalisation of Porter’s algorithm. 2-D scan plane primitives are decomposed in a way that provides a more accurate disjointness information then 3-D inclosing boxes and a simple way to class spans. Furtheremore, this scan plane organisation allows the use of most of scan line hidden surface strategies that make use of different types of coherence to speed up the visibility process.Item A Means to Improve the GKS-3D/PHIGS Output Pipeline Implementation(Eurographics Association, 1987) Herman, Ivan; Reviczky, JanosThe output pipeline of GKS-3D/PHIGS isexamined to find some possible points where the implementation could be improved to raise efficiency while remaining strictly within the scope of the Standards. Some interesting results are presented in the paper which have led to a 25-30% improvement in speed when compared to a more conservative implementation.Item Bezier Patches with Local Shape Control Parameters(Eurographics Association, 1987) Schmitt, Francis J. M.; Du, Wen-HuiIn this paper, we introduce three types of shape control parmeters (tension, bias, and continuity) into the modelling of free-form surfaces composed of bicubic Bernstein-Bezier patches. This is an extension to surfaces of the three control parameters introduced in the local interpolatory spline curves by Kochanck and Bartels [12]. We first analyze the general conditions for guaranteeing the G' continuity of the surface at corners where three, four, or five patches meet. The analysis of the continuity constraints reveals the remaining degrees of freedom which can be exploited for the control of the surface shape. The shape control parameters arc then introduced. Experimental results are provided. They show the efficiency of these parameters for an easy and intuitive control of the surface shape.Item Efficient and Consistent Algorithms for Determining the Containment of Points in Polygons and Polyhedra(Eurographics Association, 1987) Chen, Min; Townsend, TeeterAlgorithms are presented for the determination of whether a given point E2 in is interior to, exterior to or on an arbitrary polygonal boundary and for the determination of whether a point in E 3 is interior to, exterior to or on a simple polyhedral boundary. The algorithms are based on the principle of using binary coded coordinate systems and parity counting of the number of intersections of the polygon or polyhedron boundary with an infinite vector. The amount of floating-point arithmetic, including arithmetical and comparative operations has been reduced to a minimum making the algorithms very suitable for implementation in either low-level language software or by hardware. Performance of the algorithms is compared with a number of others taken from the literature and a considerable increase in efficiency is apparent. The algorithms are also shown to be consistent.Item An Automatic Interpolation Method of Grayvalued Images Utilizing Density Contour Lines(Eurographics Association, 1987) Agui, Takeshi; Saito, Minoru; Nakajima, Masayuki; Arai, YukihiroThis paper presents an automatic method of interpolation or inbetweening for gray valued images, which have been difficult to be processed automatically. The method consists of three parts. The first i s the extraction of density contour lines from a pair of gray valued key frame images, the second i s the interpolation of the contour lines and the l a s t is the generation of in-between gray valued images. In the second part, the correlation of corresponding contour lines of the key frames i s carried out automatically utilizing some kinds of similarity functions. The method is applied to a pair of pictures of a plaster head photographed slightly different directions and generates a very smooth rotating animation picture of the p l a s t e r head. This method has much applicability to computer animation and motion picture analysis. Stereo pair images are available from key frame pictures of objects photographed from any direction. Interpolation of color images is also possible.Item An Approach to the Formal Specification of Configurable Models of Graphics Systems(Eurographics Association, 1987) Arnold, D.B.; Duce, D.A.; Reynolds, G.JThis paper describes a general framework for the formal specification of modular graphics systems. The approach is illustrated by an example taken from the Graphical Kernel System (GKS) and uses the Z specification notation.Item HIRASP: A Hierarchical Interactive Rastergraphics System Based on Pattern Graphs and Pattern Expressions(Eurographics Association, 1987) Teunissen, Wim J.M.; van den Bos, JanTo exploit the full capabilities of raster graphics, two and three dimensional drawing primitives should play a preponderant role in the specification of a graphics standard. In addition there should be facilities for modeling and hierarchy. HIRASP presents an integrated language system fulfilling these requirements. The pattern is used as the basic drawing primitive. It consists of a colour function defined over an arbitrary OD to 3D domain. There are a number of basic pattern primitives. Arbitrarily complex patterns may be composed from pattern expressions. But once an expression is assigned to a pattern, the constituent structure loses its existence. Patterns define the static structure of HIRASP. On top of this a dynamic structure is built to allow for interactive modification. This dynamic structure can be represented as a directed graph, the so-called pattern graph. Patterns are the leaves of this graph. Each node carries a set of alterable orthogonal attributes, controlling domain and colour transformations, highlighting, visibility, detectability, level, and transparency, for the subgraphs descending from the node. The interpretation (traversal) of the graph results in a 2 1/2D mapping, akin to the Painters algorithm, or a full 3D mapping, on a graphics screen.Item A Shareable Centralised Database of KRT3 - A Hierarchical Graphics System Based on PHIGS(Eurographics Association, 1987) Howard, TobyThe Programmer’s Hierarchical Interactive Graphics System (PHIGS), currently under development by ISO, is a specification of a set of functions for device-independent computer graphics programming, supporting dynamic interaction and hierarchically organised graphical data. A central aspect of an implementation of a system such as PHIGS is the provision of a compact and efficient representation for the graphical entities involved. This paper describes a centralised graphical database for KRT³, an experimental hierarchical graphics system based on PHIGS. It presents a discussion of the issues involved, and the experience gained, in the practical design and implementation of a database for hierarchical graphical data. A novel aspect of the design is that the database may be simultaneously shared by several application programs.Item An Intersection-Sensitive Hidden-Surface Algorithm(Eurographics Association, 1987) Devai, FerencGiven a set of pairwise disjoint planar polygonal faces with altogether N edges in the three-dimensional space. Let k be the number of intersection points of the projections of the edges in a projection plane, 0 < k < N(N-1)/2. An algorithm for the elimination of hidden surfaces in O((N+k)log N) time and O(N+k) space is proposed. If k is O(N), which is often the case in practice, the algorithm has O(N log N) expected time, regardless of the probability distribution of the input data. The constants of proportionality are low enough to make this algorithm of practical use. The method is a three-dimensional generalization of a two-dimensional scan-line algorithm, called the NlogN algorithm. A total order hide of faces is introduced. By determining the intersections of the projected edges, regions are designated within which visibility is unvaried. Then each region is visited, maintaining the total order hide, from which visible surfaces and rendering of partially transparent objects can be inferred.Item Splines for Engineers(Eurographics Association, 1987) Ohlin, S.C.This paper introduces the concept of interpolation consistency. It is claimed that this property is an essential one for splines that are intended for use in Computer Aided Design. Consistency is defined as the property of an interpolation algorithm that, if the given set of points is extended by any point on the interpolated curve, the algorithm applied to the extended set of points will yield exactly the same curve as before. A clear distinction is made between function interpolation, where y is a function of x, and curve interpolation, where x and y are Cartesian coordinates in the geometric plane. The class of consistent curve interpolating planear splines that corresponds to cubic function interpolation is discussed in some detail and includes the Cornu spiral, the lemniscate, and the tension-free mechanical spline. Next the class that corresponds to pentic function interpolation is considered, and an efficient algorithm is presented for the calculation of one such spline, a planar spline where the curvature is a cubic polynomial in the arclength. This algorithm produces curves where the curvature is, loosely speaking, as constant as possible. Some examples illustrating the desirable properties of this spline are given.Item A New Algorithm for Contour-plotting(Eurographics Association, 1987) Brinkkernper, Sjaak; Hendriks, HarrieA new algorithm for contour-plotting is introduced. The input function, tabulated or in a subroutine description, is approximated by an interpolation function. The contours of this approximating function are drawn piecewise on a subdivision of the given domain. The algorithm is based on the iterated solution of Initial Value Problems defined by applying the Implicit Function Theorem. Estimates on the dependence of the contourlines on the approximating function are presented using the method of gradient lines. Finally some examples are shown.Item A Fast Antialiasing Method with a Z-Buffer(Eurographics Association, 1987) Ghazanfarpour, Djamchid; Peroche, BernardThis paper describes a new antialiasing method when a z-buffer is used. Good quality antialiasing is achieved in spite of unavoidable approximations. Compared to an ordinary z-buffer, only a little extra memory space and processing time are required. In particular, this fast method can be beneficial when used on a raster graphics system equipped with a hardware-implemented z-buffer. Our approach, however, offers appropriate treatment for certain problems left unsolved by previous methods.Item Interaction Management in CAD Systems with History Mechanism(Eurographics Association, 1987) Yamaguchi, Yasushi; Kimura, Fumihiko; Ten Hagen, Paul J. W.User friendliness is one of the unresolved problems in CAD systems. There are many possible directions for improving user friendliness. Understanding of the modeling process is one of the most important directions. It is natural for a user to describe the model in terms of its evolution. We call this concept model derivation. To construct and use model derivation, we propose a history mechanism which keeps and manipulates the history of the modeling process. The history mechanism manages high level interactions by introducing powerful symbolic computation to manipulate the history. Since the history representation is based on the operation's syntax and separated from the internal model representation, it is easy to apply the history mechanism to any modeling system which uses established techniques. Thus the system designer can easily introduce model derivation without reducing efficiency of the implementation.Item Dynamic Management of 3D Scenes(Eurographics Association, 1987) Hegron, GerardWhen simulating a moving observer or sensor in a 3D scene which contains a large number of objects, only the objects lying in the field of view or of interaction, named the local data base, have to be taken into account in order to decrease, at each step, computation time necessary for either image generation or various processings. This paper presents an algorithm which achieves the dynamic management of the local data base, that is to say which manages the set of objects which enter or leave the field of view of an observer (camera, sensor) during its displacement. This method consists, broadly, of the following two steps: a binary space partitioning of the 3D space is performed off-line from the object bounding boxes by means of planes perpendicular to the X, Y and Z axes and a subregion adjacency graph is created; the dynamic management of the local data base is achieved on-line by modelling the bounded bearing volume of the sensor by a cube of R "radius" (half-edge), and by using the adjacency graph, and inclusion and intersection criteria in order to exploit spatial and temporal coherences between each displacement. When the scene data base is very large, the dynamic management of the RAM memory can be done simultaneously by using this method reasoning from the bounding boxes of disjoined sub - scenes.