Winter School of Computer Graphics 1994

University of West Bohemia, Pilsen, Czech Republic

January 19 - 20, 1994

Abstracts of papers with some on-line versions


Raytracing 3D Linear Graftals
Ph. Bekaert, Y. D. Willems

Dept. of Computing Science
Katholieke Universiteit Leuven
Celestijnenlaan 200A, 3001 Leuven, Belgium

Many objects in nature, like trees, mountains and seashells, have a property called selfsimilarity. Sometimes this property is very pronounced, other natural phenomena exhibit this property to a lesser degree. During the past years much attention has been paid to fractals, purely selfsimilar objects. We present a formalism, based on the well-known object-instancing graph, to represent objects which are not necessarily purely selfsimilar. We show that Iterated Function Systems and some famous variants can be described elegantly in this formalism. We also present an algorithm to raytrace such objects.

Keywords: rendering, fractals, formal languages, ray tracing

Generating Plants for Computer Graphics
Bedrich Benes

CTU, Fac. of Electrical Eng.
Dept. of Computer Science
Karlovo nam.13

121 35 Praha 2

Abstract is not available.

Keywords : Tree, L-system, Rendering, Computer Graphics

A Mathematical Framework for Global Illumination Algorithms
Ph.Dutre, E.Lafortune, Y.D.Willems

{philipd, ericl, ydw}
Department pf Computing Science
Katholieke Universiteit Leuven
Celestijnenlaan 200A
B-3001 Heverlee, Belgium

This paper describes a mathematical framework for rendering algorithms. Starting from the rendering equation and the potential equation, we will introduce the Global Reflection Distribution Function (GRDF). By using GRDF, we are able to compute the behaviour of light in an environment, independent of the initial lighting or viewpoint conditions. This framework is able to describe most existing rendering algorithms.

Cubic Monte Carlo Radiosity
Pavol Elias, Martin Feda, Peter Ferschin, Werner Purgathofer

Department of Applied Mathematics
Faculty of Mathematics and Physics, Comenius University,
842 15 Bratislava, Slovakia

Institute of Computer Graphics
Technical University of Vienna
Karlsplatz 13/186 A-1040 Vienna, Austria

A revised radiosity method for curved surfaces is proposed, based on the Monte Carlo approach. In order to improve the accuracy of the solution, a smoothly reconstructed illumination function with selected discontinuities is used during the radiosity computation. The reconstructed function is used as a random number distribution for position sampling to overcome the constant radiosity assumption syndrome. Illumination information stored at the surface control points is used to preserve continuity of the illumination across the boundary of adjacent surfaces and to avoid Mach band effects. Implementation in Flatland is discussed.

Prehlad normalizovanych grafickych systemov
Andrej Ferko

MFF UK, 842 15 Bratislava, SR

The paper deals with the survey of standardized graphics systems from the point of view of a course for computer graphics students. This Comenius University course is based on a new textbook [ErFe93] on this topic which seems to be a very useful notional and conceptual tool for systematic understanding to the functionality and architecture of any graphics system.

Fractal Based Procedural Modelling
Norbert Filip

Department of Geometry
Faculty of Mathematics and Physics
Comenius University
842 15 Bratislava, Slovakia

Two different methods for procedurally based modelling are presented as an alternative to the interactive modelling. Fractal and graftal techniques are shown to be the possibilities for modelling of natural phenomena as terrain shapes and trees. Different issues of consistency for fractal based terrain modelling are discussed. Second part of the paper shows several problems of graftal and L-systems trees modelling. Attention is focused on modeling of branches, the problem of "twisted" branches and branch connections are solved. The paper contains remarks towards the implementation of presented ideas.

Coherence in scan-line algorithms for CSG
Eduard Gröller, Peter Brunner

Technical University Vienna
Institute for Computergraphics
Karlsplatz 13/186/2
A-1040 Vienna, Austria

Scan-line algorithms for visibility calculation exploit various types of coherence properties. Several scan-line algorithms for Constructive Solid Geometry (CSG)are discussed. In one approach CSG primitives are represented by polygonal approximations. Another technique processes CSG primitives as general quadric surfaces. We investigate the handling of frequently occuring quadric surfaces (cube, cone, sphere, cylinder)as distinct cases. Thus the differing properties of such objects can be used more efficiently than a uniform approach would allow. A so called eBRep (extended Boundary Representation) is defined for the frequently occuring quadric surfaces. An eBRep is an exact representation of of a quadric object and contains curved edges and faces. For each of the above mentioned quadric surfaces a different, geometry dependent eBRep is specified. A comparison between the polygon-based scan-line algorithm for CSG and our eBRep based approach is done. eBRep is a storage efficient exact representation of quadric surfaces, well suited for scan-line visibility determination.

Keywords: CSG, quadrics, scan-line alghoritm, extended BRep, curved edges

Graphics Systems PHIGS and PHIGS+
Bohuslav Hudec
Dept. of computers
Electrotechnical Faculty of Czech Technical University

The PHIGS (Programmer's Hierarchical Interactive Graphics System) is an international ISO standard of a functional interface between an application program and a configuration of graphical input and output devices. This interface contains basic functions for dynamic interactive 2D and 3D graphics on wide variety of graphics equippment.

G2 Continuous Beta-spline Curves Defined on the Interval <0,1)
Maria Imriskova

Radlinskeho 11, 813 68 Bratislava, SR

In this paper, the general and special matrices forms of the cubic beta-spline curve defined on the interval <0,1) are described.

Visualisation of the Volume Datasets in Science
Juraj Jankovic
Faculty of Mathematics and Physics
Comenius University,
842 15 Bratislava, Slovakia

Volume visualisation is one of the fast-growing areas in scientific visualisation. It helps to look at scalar or vector datasets and understand them more easily. An overview of basic algorithms used for this purpose, some of enhancements and optimizations are described here.

Semiregular Grids in 2D and 3D
Alexej Kolcun

Institute of Geonics
Academy of Sciences of Czech Republic
Studentska 1768, 70200 Ostrava, Czech Republic

Advantages of grids used in finite element analysis ( FEM ), which are similar to regular, are described in [5]. We show posibilities of generation and transformation of such grids and we make comparison of them in 2D. We show dificulties arising in 3D.

Creating Convex Hulls in E2 Using Dual Representation
Ivana Kolingerova
Department of Computer Science
University of West Bohemia
Univerzitni 8, 306 14 Plzen
Czech Republic

The dual representation of points, lines and polygons introduced in [Gun88] can also be used for computing convex hulls of a set of points in E2. The main principles of the dual representation and a sketch of the algorithm for convex hull computation are given in this paper. Algorithm can be used both for statical and semi-dynamical case. More details can be seen in [Kol94].

Fractal Volumes
C. Kose, C.P.Willis and D.J.Paddon
Department of Computer Science,
University of Bristol,
Queens Building,

University Walk,
Bristol BS8 1TR, UK

A Mandelbrot set, in quaternion representation, is used as a test data set to research the necessary characteristics of a system that visualises large and complex data sets. An image space software solution is developed that uses dynamic data partitioning across a distributed system of processors. A system configuration is used that minimised the network diameter in order to reduce the communications overhead.

Simple Graphic CAM System Controlling the Cutting Machine
Miloslav Kosek

Department of Electrical Engineering
Fculty of Textile Engineering
Technical University of Liberec, Czech Republic

A CAM system using a personal computer for the control of a cutting machine is described. The key part of the system is a database of suits. It contains commands that areprocessed by a personal computer. The computer can control a drawing or cutting machine that draws or cuts contours of style parts. The attention is focused namely to the transform of standard instructions that are understood by a tailor to commands that drive the computer.

X Window System
Ales Limpouch

Department of Computers
Faculty of Electrical Engineering
Czech Technical University

The X Window System has, over the last few years, become increasingly important and it is now accepted as THE window system for workstations, mainframes and supercomputers. It has become the standard means of providing graphical facilities on UNIX systems. This paper gives a brief overview of fundamental principles, concepts and architecture of the X system and describes in detail essential characteristics of the X server.

Keywords : graphical user interface, window management system, X Window System, X server

Pouzitie octree struktury na urychlenie metody ray tracing
Jozef Martinka

Katedra aplikovanej matematiky
Matematicko fyzikalna fakulta Univerzity Komenskeho
842 15 Bratislava, Slovenska republika

Niektore sposoby urychlenia metody ray tracing vyuzivaju priestorove rozdelenie sceny a jej reprezentaciu pomocou octree struktury. Hlavne problemy spojene s pouzitim octree su: vhodna reprezentacia, efektivny sposob vytvorenia (rozdelenia sceny na kocky octree) a rychly "prechod" sledovaneho luca cez strukturu. V clanku su strucne popisane niektore pristupy k rieseniu tychto problemov.

Triangular Patches under Tension
F. Schindler

Dept. of Computer Science and Engineering
Slovak Technical University
SK-81219 Bratislava, Slovakia

Given a triangular surface scheme that only approximates the initial data the resulting surfaces do not reflect the shape of control vertices as much as the user would have liked. By supplying tension parameters, or what in this case might be called "shape" parameters, the user is able to force the triangular surface patch to follow the control vertices as close as desired without moving or introducing additional control point A revised radiosity method for curved surfaces is proposed, based on the Monte Carlo approach. In order to improve the accuracy of the solution, a smoothly reconstructed illumination function with selected discontinuities is used during the radiosity computation. The reconstructed function is used as a random number distribution for position sampling to overcome the constant radiosity assumption syndrome. Illumination information stored at the surface control points is used to preserve continuity of the illumination across the boundary of adjacent surfaces and to avoid Mach band effects. Implementation in Flatland is discussed.

O(lg N) Line Clipping Algorithm in E2
Vaclav Skala

Department of Informatics and Computer Science
University of West Bohemia
Americka 42, Box 314, 306 14 Plzen Czech Republic

A new O(lg N) line clipping algorithm in E2 against a convex window is presented. The main advantage of the presented algorithm is the principal acceleration of the line clipping problem solution. A comparison of the proposed algorithm with others shows a significant improvement in run-time. Experimental results for selected known algorithms are also shown.

Keywords : Line clipping, Convex polygon, Computer graphics, Algorithm complexity.

Graf potencialu viditelnosti
Eduard Sojka

Katedra informatiky FEL VSB Ostrava
708 00 Ostrava-Poruba


Clanek podava novy pohled na teorii potencialu viditelnosti. Tento pohled predpoklada, ze na mnozine obrazu dane sceny lze zavest relaci ekvivalence. Tato relace pak indukuje rozklad mnoziny obrazu, ktera je nekonecna, na konecny pocet trid. Take prostor obklopujici scenu je dekomponovan na tridy. Ze vsech bodu jedne tridy vnima pozorovatel ekvivalentni obrazy. Graf potencialu viditelnosti zachycuje informaci o techto tridach a vztazich mezi nimi. Predkladana teorie umoznuje zasadit publikovane pristupy do jednotneho ramce. Pouziti teorie je ilustrovano na nekolika prikladech. Graf potencialu viditelnosti muze byt puzit jako alternativni nebo doplnkovy model sceny a muze byt uzitecny pri reseni ruznych problemu jako je napriklad problem viditelnosti, problem navigace ve scene a problem rozpoznani trojrozmernych objektu.

Klicova slova: graf potencialu viditelnosti, graf aspektu, viditelnost.

Parallel Progresive Radiosity with Parallel Visibility Computations
W. Stürzlinger and C. Wild

Institute for Computer science,
Johannes Kepler University of Linz,
Department for graphical and parallel processing
Altenbergerstrasse 69, A-4040 Linz, Austria

The radiosity method models the interaction of light between diffuse reflecting surfaces, thereby accurately predicting global illumination effects. Due to the high computational effort to calculate the transfer of light between surfaces and the memory requirements for the scene description, a distributed, parallelized version of the algoritm is needed for scenes consisting of thousands of surfaces. We present a distributed, parallel radiosity algoritm, which can subdivide the surface adaptively. Aditionally we present a scheme for paralel visibility calculations. Adaptive load redistribution is also discussed.

Computer Graphics Hardware
Miroslav Snorek

Dept of Computers, Electrical faculty
Czech Technical University of Prague

Abstract is not available.

An Algorithm for Fast Voxel Scene Traversal
Milos Sramek

Institute of Measurement Science
Slovak Academy of Science
Dubravska cesta 9
842 19 Bratislava

Together with improvement of tomographic method of scanning 3D data, residing in an increase of distinguishing ability of the scanners, the quality of final 3D reconstruction of the data comes into foreground. An inevitable condition for visualization of small details, comparable with the voxel size is application of such algorithms, which enable to define a surface of the scanned object on subvoxel level. Comong out from paper published at previous year of Winter School on Computer Graphics and CAD Systems we present an algorithm for fast traversal of the voxel scene, which enables to find a nearest intersection of a ray with the object surface defined in such way. High speed of the algorithm utilizes object coherency of the scene, which means that voxels belonging to the object are usually grouped in connected regions.

The algorithm consists from two steps : preprocessing and scene traversal. In the preprocessing phase we assign to each background voxel of the segmented scene a value equal to its chessboard distance from the nearest object voxel, which defines a cubic macro region with no voxels inside. While generating a discrete ray, we can jump over this region, which results in up to 6-fold speed up of the traversal. The algorithm has no additional demands on memory, since the distance is stored in originally "empty" background voxels.

Demonstration Constructive du Theoreme de Pohlke-Schwarz
Svatopluk Zacharias

Katedra matematiky Zapadoceske Univerzity
Univerzitni 8
306 14 Plzen, CR

Abstract is not available.

Parallelisation of the Ray Tracing Algorithm
Jiri Zara
Ales Holecek (
Jan Prikryl (
CTU, Fac.of Electrical Eng.
Dept.of Computer Science
Karlovo nam.13
121 35 Praha 2

The two typical methods for distribution of ray tracing rendering algorithm are presented in this article. The implementation of a distributed ray-tracer on a network of UNIX workstations is described in details. The first results are discussed from the point of view of memory load, time of computation and cost of communication among processes.

Keywords: computer graphics, rendering, parallel algorithm, ray-tracing, PVM

Knowledge of Students
Petr Rezacek
University of West Bohemia



Last update: 23.07.2001