University of West Bohemia, Pilsen, Czech Republic

January 19 - 20, 1994

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

Dept. of Computing Science

Katholieke Universiteit Leuven

Celestijnenlaan 200A, 3001 Leuven, Belgium

philippe@cs.kuleuven.ac.be

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

e-mail benes@cslab.felk.cvut.cz

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}@cs.kuleuven.ac.be

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

e-mail elias@delta.dcs.fmph.uniba.sk

Institute of Computer Graphics

Technical University of Vienna

Karlsplatz 13/186 A-1040 Vienna, Austria

e-mail elias@eigvs4.una.ac.at

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

ferko@fmph.uniba.sk

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

e-mail filip@delta.dcs.fmph.uniba.sk

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

e-mail groeller@eigvs4.tuwien.ac.at

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

Prague

e-mail hudec@cs.felk.cvut.cz

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

e-mail imriskov@cvt.stuba.sk

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

e-mail kolinger@kiv.zcu.cz

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

e-mail derek@compsci.bristol.ac.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

e-mail limpouch@cs.felk.cvut.cz

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

e-mail jozef.martinka@st.fmph.uniba.sk

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

e-mail skala@kiv.zcu.cz

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

tr.17.listopadu

708 00 Ostrava-Poruba

|e-mail eduard.sojka@vsb.cz

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

e-mail wrzl@gup.uni-linz.ac.at

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

SR

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 **(zara@cs.felk.cvut.cz)

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

Plzen

Last update: *23.07.2001*