EG1987

Permanent URI for this community

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

Browse

Now showing 1 - 20 of 43

An Algorithm for 3D Scan-Conversion of Polygons
(Eurographics Association, 1987) Kaufman, Arie
A 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.
Efficient and Consistent Algorithms for Determining the Containment of Points in Polygons and Polyhedra
(Eurographics Association, 1987) Chen, Min; Townsend, Teeter
Algorithms are presented for the determination of whether a given point E² in is interior to, exterior to or on an arbitrary polygonal boundary and for the determination of whether a point in E ³ 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.
Extended Octtrees, between CSG Trees and Boundary Representations
(Eurographics Association, 1987) Navazo, Isabel; Fontdecaba, Josep; Brunet, Pere
Besides 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.
An Automatic Interpolation Method of Grayvalued Images Utilizing Density Contour Lines
(Eurographics Association, 1987) Agui, Takeshi; Saito, Minoru; Nakajima, Masayuki; Arai, Yukihiro
This 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.
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.
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.
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.
A Fast Antialiasing Method with a Z-Buffer
(Eurographics Association, 1987) Ghazanfarpour, Djamchid; Peroche, Bernard
This 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.
A Means to Improve the GKS-3D/PHIGS Output Pipeline Implementation
(Eurographics Association, 1987) Herman, Ivan; Reviczky, Janos
The 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.
A New Algorithm of Space Tracing Using a CSG Model
(Eurographics Association, 1987) Bouatouch, Kadi; Madani, M.O.; Priol, Thierry; Arnaldi, Bruno
This 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.
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.
A Fast Ray Tracing Algorithm Using Space Indexing Techniques
(Eurographics Association, 1987) Qunsheng, Peng; Zhu, Yining; Liang, Youdong
A 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.
Dynamic Management of 3D Scenes
(Eurographics Association, 1987) Hegron, Gerard
When 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.
COLOUR SECTION
(Eurographics Association, 1987) -
Extraction and Organization of Form Features into a Structured Boundary Model
(Eurographics Association, 1987) Falcidieno, Bianca; Giannini, Franca
A 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].
A Fast Voxel Traversal Algorithm for Ray Tracing
(Eurographics Association, 1987) Amanatides, John; Woo, Andrew
A 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.
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.
A Window Managment System on Top of GKS
(Eurographics Association, 1987) Hartelt, Helga I.M.; Magalhaes, Leo Pini; Daltrini, Beatriz Mascia
This 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.
Active-Ray Tracing for 3D Medical Imaging
(Eurographics Association, 1987) Trousset, Yves; Schmitt, Francis
Large 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.
Unifying Vector and Polygon Algorithms for Scan Conversion and Clipping
(Eurographics Association, 1987) Kilgour, AIistair
In 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.

Browse

Browsing EG1987 by Issue Date

Results Per Page

Sort Options