Information available in this document :

• Brief information
• Photos
• Programme committee
• Invited speakers
• Official sponsors
• Programme
• Abstracts of the papers
• Contacts on us

Nadia Magnenat-Thälmann, MIRALab-CUI, Univ. of Geneva, Switzerland, Co-Chair
Vaclav Skala, Univ. of West Bohemia, Czech Republic, Co-Chair


          Brian Barsky (USA)                       Ken Brodlie (UK)
          Gulio Casciola (I)                       Alan Chalmers (UK)
          Gordon Clapworthy (UK)                   Steve Cunningham (USA)
          John Day (AU)                            Dieter Fellner (D)
          Andrej Ferko (SK)                        Martin Göbel (D)
          Eduard Gröller (A)                       Wolfgang Herzner (A)
          Roger Hubbold (UK)                       Lars Kjelldahl (S)
          Annie Luciani (F)                        Alan Middleditch (UK)
          Vojtech Mockrzycki (PL)                  G.Scott Owen (USA)
          Derek Paddon (UK)                        Hans-Peter Seidel (D)
          Francois Sillion (F)                     Wolfgang Stürzlinger (A)
          Danielle Tost (ES)                       Philip J.Willis (UK)
          Peter Wisskirchen (D)

Prof. Dr. Dieter Fellner : Design of a Graphics Architecture Bridging the Gap between Modeling and Rendering , Univ. of Bonn, Germany

Prof. Nadia Magnenat Thälmann : 3D Clothes Animation and Fashion Show Simulation, MIRALab, Univ.of Geneve, Switzerland

Prof. Dr. Franz-Erich Wolter : Differencial Geometric Concepts and Methods in CAGD, Univ.of Hannover, Germany

I B M s.r.o. , Hewlett Packard s.r.o.

Intergraph s.r.o. , Silicon Graphics s.r.o., Microsoft s.r.o.

Wolfram Research Inc. , DTP Studio s.r.o.

D.Arques, S.Michelin

IMPROVING THE ZONAL METHOD THROUGH THE USE OF SERIES DEVELOPMENTS TO APPROXIMATE VOLUME/VOLUME FORM FACTORS

Institute G.Monge, Universite de Marne-la-Vallee

Noisy-le-Grand Cedex, France

{arques,michelin}@iniv-mlv.fr

This paper introduces a new acceleration technique for the zonal method. We present mathematical developments which improve, in a considerable way, the time due to the form factor calculus. More precisly, we show that, under the assumption of classical modeling conditions, we can :

- simplify the mathematical expression of the volume/volume form factor,

- approximate this simplification by a series development of orthogonal polynomials with a complete error control. Analog results can be obtained for the other types of form factors.

NEW HEURISTICS FOR MINIMUM WEIGHT TRIANGULATION

M.Bartánus, A.Ferko, R.Mag, L.Niepel, T.Plachetka, E.Sikudova

Comenius University, Bratislava

Slovakia

kpgso@fmph.uniba.sk

In rendering it is sometimes desirable to compute minimum total light energy mesh. This requires finding the solution for mimimum weight triangulation (MWT). We have introduced several new heuristics for MWT, based on original observations. All new algorithms are tested on a set of randomly generated examples. For each example we compute the optimum (for small data sets) using backtrack technique or a reference suboptimum using simulated annealing technique. We compare the new heuristics.

LANGUAGE SUPPORT FOR DISTRIBUTED VIRTUAL REALITY

B.Benes, A.Holecek, J.Zára

Czech Technical University, Prague

Czech Republic

{benes|holecek|zara}@sgi.felk.cvut.cz

One of the main issues in the research on Multi-user Distributed Virtual Reality Systems is the virtual environment description language. A number of different languages with various level of description formalism already exist. In this paper we provide a quick overview of the existing systems. We look more into details of Virtual Reality Modeling Language based on SGI's Open Inventor format. The problems of multi-user reality systems are farther examined from the point of view of keeping the world database consistent. We present methods reducing the communication demands based on using more complex specification of the environment behaviour and distribution of the world database. Finally, the paper provides an explanation of our research. We attempt to design an algorithm for direct global visibility preprocesing, which is an important issue related to the world database subdivision.

STRAIGHT LINES : A STEP BY STEP METHOD

F.-P.Chalopin, J.-J.Bourdin

Universite Paris 8

France

[jj-chalopin]@ai.univ-paris8.fr

Drawing straight lines is a major field in computer graphics. Most methods are improvements of the DDA method first presented by Bresenham. Combinatory analysis method, as presented by Castle or Dulucq or Berstel are not commonly used; they imply multiple string copies and are therefore slow. A new approach, combining combinatory analysis and DDA is presented. The DDA does not apply to each point but to a step computed by combinatory method. This algorithm is tested and proves to be more than four times faster than Bresenham's algorithm.

IMAGE SPACE ALGORITHMS FOR LINE CLIPPING

J.D.Day

Queensland University of Technology

Australia

j.day@qut.edu.au

Algorithms for clipping lines against rectangular windows are normally implemented in object space using floating point arithmetic, and the resulting clipped lines are then scan converted to obtain their representation as a list of pixels in image space. Some algorithms avoid the use of floating point arithmetic. They use integer arithmetic to obtain the end points of the clipped line. The line is than scan converted as before. In both cases there is a side effect. This is described and discussed. An alternative approach is to scan convert the lines, then clip against the viewport. The algorithm would then use a description of the line as a list of pixel locations in image space, rather than a pair of end points in object space. The feasibility of this method, in terms of side effects and efficiency, is discussed.

PRE-PROCESSING OF THE FINGERPRINT IMAGE

M.Dobes

Palacky University, Olomouc

Czech Republic

dobes@risc.upol.cz

This article introduces a special way of the fingerprint image pre-processing - direct segmentation of the grayscale image. For the purpose of the following recognition there is one crucial point in the pre-processing of the scanned fingerprint image. It is the best separation of ridges from valleys. The proposed algorithm is designed to satisfy two contradictory aims : good quality of the segmentation and fastness.

It is typical for the fingerprint image that the finger is usually not printed uniformly a part of it is extremaly light and other part dark so methods based on global thresholding finding fail.

The proposed algorithm is based on a probabilistic approach and comes from the idea of the local histogram equalization method, but only from the idea - the algorithm is completely rebuilt. Instead of filtering the image first and segmenting it later all this is done in one step. To achieve a good separation the adequate area of each "interesting" pixel in the image is explored. The exploration mask is only updated and when another interesting pixel is reached to achieve greater speed of the algorithm.

Experimantal results show that this method is fairly effective from both points of view : good separation of ridges from valleys and the speed.

GRAPHICAL USER INTERFACES : MESS THEM UP !

E.Dubuis

Institute für Informatik und angewandte Mathematik

Bern, Switzerland

dubuis@tech.ascom.ch

Today's GUIs simulate a perfect world. Windows have always the same look and buttons have identical shapes and colors and are aligned to regular grids. The only distinction between graphical elements is their label. The current visual design of user interfaces ignores the capabilities of modern displays for an effective visual coding and the resulting uniformness makes it very difficult for the user to recognize graphical elements at first sight.

This paper presents some ideas and propositions for the visual design and the 'look & feel'- concept of next generation user interfaces. New concepts for the layout and the visual coding of graphical elements are proposed. The suggested new layout and coding rules should help the user to recognize and remember graphical elements easily and to distinguish them from other elements of the same type.

SCIENTIFIC VISUALIZATION ABILITY DEVELOPMENT

-Factor Analysis of Student Difficulties in Figure Transformation Problems using Computer Graphics Function

T.Ezaki, D.R.Short

Fukuoka University, Japan/P>

Purdue University, U.S.A.

ezaki@dgsun.tm.fukuoka-u.ac.jp, drshort@tech.purdue.edu

As a method for improving the scientific visual ability of students, the authors have used computer graphics based systems for student practice and the analysis of student responses. The final goal is to develop an effective instructional system by analyzing the underlying knowledge mechanism and reconstructing it for visualization problems. This paper describes the results of the comparison of student performance for 2D-3D figure transformation problems under different conditions. The results were used to investigate the sources and causes of projection or solid construction errors for multiview problems. Comparative data for RAR (Right Answer Rate) and TOT (Time on Task) and KOT (Key Operation Times) for student solutions were examined for selected, difficult problems. The errors and the suspected causes of the student's difficulty in solving these problems were related to the student prior knowledge of descriptive geometry.

RAY SHOOTING IN LOGARITHMIC TIME

T.Fóris, G.Márton, L.Szirmay-Kalos

Technical University of Budapest

Hungary

foris@fsz.bme.hu, marton@fsz.bme.hu

A new technique for ray tracing acceleration is presented. The objects of the scene are preprocessed to form a data structure that makes possible to find the first intersection with an arbitrary ray at the speed of binary search, that is in time logarithmically proportional to the number of objects. The idea is based on a peculiar representation of rays, while the underlying data structures are spherical and planar subdivisions, balanced binary trees.

INTERACTIVE DESIGN OF NONLINEAR FUNCTIONS FOR ITERATED FUNCTION SYSTEMS

E.Gröller, R.Wegenkittl

Technical University Vienna

Austria

groeller@eigvs4.una.ac.at, wegenkittl@cg.tuwien.ac.at

The basic requirement for the functions of an IFS is contractivity. Nevertheless the majority of recent scientific investigations is concentrating on IFSs defined through a set of contractive linear functions. Simpler handling of this kind of functions and a more predictable result is the main reason for this approach. In this work we use distorted grids (representing nonlinear functions) to specify an IFS with a higher degree of flexibility and a higher modeling capability. A program for modeling these grids with so-called high-level operations is presented. Attention is directed to the interactivity of designing the IFS and rendering its limit set. Therefore a z-buffer for displaying the result of a stochastic algorithm is included. Example images designed with the implemented software system are presented.

EFFICIENT DATA STRUCTURES FOR VOLUME RENDERING OF WAVELET-COMPRESSED DATA

R.Grosso, T.Ertl, J.Aschoff

Universität Erlangen-Nürnberg

Germany

{grosso,ertl}@informatik.uni-erlangen.de

Volume rendering is compute intensive and require huge amounts of memory. Many methods were proposed to improve performence, but the problems of dealing with large data sets still remain. Muraki was the first to propose the decomposition of the volume density function into a pyramidal representation by means of the 3D discrete wavelet transform with orthonormal bases, and then render the corresponding basis functions weighted by the wavelet coefficients. Depending on the approximation properties of the basis functions used a large number of coefficients can be neglected while still achieving a good representation of the volume data, which results in very high compression rates. However, due to the pyramidal character of the discrete wavelet transform, a very large number of basis functions have to be evaluated in order to approximate the underlying volume density function at any point. This fact increases the rendering time drastically. Furthemore, the access rate to a data value is very slow for typical data structures for compressed data, which combined with an efficient traversal of the pyramidal structures leads to even larger rendering times. In this paper we propose a data structure for sparse data representation, which does not exploit the full compression potential but combined with an intelligent pyramid traversal allows for a significant acceleration of the rendering time. All other known acceleration techniques to solve the volume integral can be used additionally, such as adptive integration step, space leaping, early ray termination, etc.

A PHYSICALLY-BASED MODEL FOR THE SIMULATION OF REACTIVE TURBULENT OBJECTS

A.Habibi, A.Luciani, A.Vapillon

Acroe & Clips-imag

France

Arash.Habibi@imag.fr, Annie.Luciani@imag.fr

The challenging issue that is addressed here is the modelling of turbulent phenomena, physically consistant, and reactive at the same time. The aim is, first, to understand these phenomena in order to elaborate a particle-based dynamic model, capable of accounting for a certain number of experimentally observed recognizable turbulent phenomena (consistency). Next, the aim is to achieve not only beautiful shapes, not only the fine dynamics slow and fleeting, of turbulent objects left to themselves, but the still richer movements that result from the interaction with man (reactivity).

This work presents a consistant connection with fundamental physics. However, it falls clearly in the field of computer graphics. We regard reactivity as a means to control a physically-based simulation of turbulent phenomena. Thanks to particles, we have simulated the interaction (action and reaction) between several fluids as well as between fluids and solid objects (fixed or mobile, rigid or deformable). When moved by an operator, these objects enable him to wave a hand in the fluid, to guide it, or to manipulate a thurible.

Eventually this course particle model is refined by a high-resolution dynamic model that adds the small-scale phenomena in the final animation.

VISIBILITY THROUGH INACCURACY : GEOMETRIC DISTORTIONS TO REDUCE THE CLUTTERING IN ROUTE MAPS

J.Hamel, R.Michel, T.Strothotte

Otto-von-Guericke University of Magdeburg

Germany

{hamel|rainer|tsr}@isg.cs.uni-magdeburg.de

We present the concept of the FOCUS LINE, a new geometric distortion method designed to solve the problem of symbol cluttering in maps. FOCUS LINE's utilise significant differences in the symbol density across the original map and distorts the layout to create the presentation area required. When focussed on dense areas, the distortion guarantees a continuous and smooth integration of the enlarged area in the map as a whole. Unlike related approaches, the FOCUS LINE distortion consideres the properties of the street network as found in city maps.

The FOCUS LINE polyfocal distortion is characterized by a new shape of distortion reducing unnecessary distortions to the overall layout. The distortion is designed such that the amount is easily adjustable by parameters that have a geometric correspondence. Applying this method to tactile route maps, we discuss the results of an automatic approach and present interactive tools based on the FOCUS LINE distortion. These tools have been included in a prototypical implementation of a map editor for a systematical modification of the map layout.

CHANNEL - A GENERALIZED PIPE

P.Hejda, J.Zára

Czech Technical University, Prague

Czech Republic

{hejda|zara}@sgi.felk.cvut.cz

Abstract is not available.

A MODEL FOR A USER-ADAPTIVE RESPONSE TO INTERACTIONS IN VIRTUAL WORLDS

L.Herve, T.Patrice, D.Yves, C.Rene

IRIT

France

{luga|torguet}@irit.fr

Nowadays, Human/Computers interaction moves from passive 2D desktops to active 3D environments. Such environments must take users'difference into account. To provide a simple user dependent system, we need new knowledge-based algorithms which automatically learns user's differences.

Evolutionary programming are nature based algorithms for problem solving. In this paper we are introducing the application of this searching techniques to Human Computer interaction. We present our software architecture and two examples of automatic adaption of computer responses to human inputs.

HIDDEN LINE PROBLEM FORMULATED AS A SET UNION PROBLEM

T.Hruz, I.Povazan, R.Gosiorovsky

Slovak Technical University, Slavak Academy of Sciences, Bratislava

Slovak Republic

{hruz|gosiorov}@vm.stuba.sk, utrrpova@savba.savba.cs

The paper describes an alternative approach to the hidden line problem in computer graphics. It is assumed that a 3D visible scene consisting of convex planar polygons with known visibility order is given. An abstract data structure together with a set of operations for efiicient solving of hidden line problem in the image space is defined. The main operation UNION is then implemented on the segment tree data structure. The solution of the visibility problem relies mainly on a two-way scan conversion process and the hidden line problem is formulated as a set union problem. The worst case complexity of the presented algorithm is O(sn log s) where n is the number of polygons and s is a resolution. The algorithm is output sensitive in the image space sence. In certain situations priority order is given or easily computable and resolution of raster space is very high. In these situations the algorithm presented can be faster than Z-buffer.

GENERALIZED CLIPPING OF A POLYGON AGAINST A 2D ARBITRARY WINDOW AND A 3D NON-CONVEX VOLUME

S.Hua, A.Tokuta

Computer Mangement & Development Services, Harrisonsburg

James Madison University, Harrisonsburg

U.S.A.

tokutaao@vax1.acs.jmu.edu

Several clipping algorithms are in wide use. These are separated into broad classes. They include subdivision algorithms of which the best known is the midpoint subdivision algorithm; the Cohen-Sutherland algorithm which uses outcodes generators and line window intersection calculations to determine what portion(s) of line segments may be contained in the window. Outcode determination /redetermination for the stages of the algorithm can dominate the clipping process. There are algorithms which are based on parametric expressions for lines and which are comparatively more efficient than the simple Cohen-Sutherland algorithm. The Skala 2D line clipping algorithm use a parameter value to determine the intersection of a line segment with a convex or non-convex polygon window. The Rappoport algorithm clips any subject polygon against a convex polygonal window. The work of Weiler and Atherton algorithm allows the clipping of any subject polygon against any clip polygon. However, it is based on some assumptions. This work presents an efficient method for clipping a polygon against an arbitrary two-dimensional polygonal windows and a modification of the algorithm can be also applied to clip a polygon against a non-convex volume on 3D. The basic idea based on geometry and parametric representation of the lines, determines if an edge of the subject polygon should be totally rejected, or is totally visible. On the other hand, if an edge of a polygon has intersections with the boundary of a simple polygon window, it is easy to decide which parts of the edge are visible after sorting these intersections.

GRAPHIC ENVIRONMENT FOR INDUSTRIAL COMPUTERIZED TOMOGRAPHY

M.Iovea, A.Marinscu, P.Chitescu, T.Sava, C.Rizescu, Ch.Georgescu

ICPE-BUCHAREST/P>

Romania

Abstract is not available.

USING IMAGES TO ESTIMATE REFLECTANCE FUNCTIONS

K.F.Karner

Technical University Graz

Austria

karner@icg.tu-graz.ac.at

A new method for the evaluation of the bidirectional reflectance distribution function (BRDF) is presented. The proposed procedure foregoes the usage of special equipment like photogoniometers or imaging reflectometers but rather uses of-the-shelf hardware like CCD cameras.

The BRDF is determined from the image data, thus capturing several incident angles at each measurement. Using a diffuse reflectance standard the effects of ambient and stray light can be reduced. The presented method offers an easy and cost efficient way to measure material properties needed for physically based rendering algorithms.

LOSSLESS WAVELET BASED IMAGE COMPRESSION WITH ADAPTIVE 2D DECOMPOSITION

M.Kopp

Technical University of Vienna

Austria

m.kopp@ieee.org

2D wavelets are usually generated from 1D wavelets through the rectangular or through the square decomposition scheme. In this paper a new adaptive 2D decomposition scheme for compression related applications is presented. The adaptive 2D decomposition selects 2D wavelet functions based on the compression of the coefficients, but needs only the same number of 1D filter operations as the rectangular decomposition for the compression and even less for the decompression. Results for lossless image compression have shown improvements in the compression rate between 1% and 10% compared to the square decomposition. Only in the case of very small images (below 50x50) the adaptive decomposition was outperformed by the square decomposition because of the overhead to store the selection, which 2D wavelets should be used.

SIMPLE, EFFICIENT AND FLEXIBLE CAD SYSTEM FOR TEXTILE PATTERNING

M.Kosek

Technical University of Liberec

Czech Republic

miloslav.kosek@vslib.cz

Textile patterning is one of very efficient areas for application of computer graphics in textile industry. The key procedure of textile patterning consists of regular placement of the atomic part, the motif, into the pattern area. Several big specialized commercial systems exist, their common disadvantage is high cost and special equipment they require. A simple and flexible CAD system for textile patterning developed at the Technical University in Liberec has all basic features of big systems and in advance it can run on each PC with a standard equipment. The system performs all basic operations of textile patterning : scanning of drawn motif, creation of pattern and preparation of the pattern printing on fabrics. Therefore the system is very suitable for textile student training but it can be also used in small textile companies.

MOLECULAR MODELS SUPERPOSITION AND VISUALIZATION

A.Krenek

Masaryk University

Czech Republic

ljocha@fi.muni.cz

A visualization system of molecular behaviour is presented in this paper. The system was designed for very large input data sets. An essential problem of visualization is finding the best natch of two structures. A solution (the superposition transformation) is discussed in detail.

TOWARDS AUTOMATED ANIMATION OF ALGORITHMS

S.P.Lahtinen, T.Lamminjoki, E.Sutinen, J.Tarhio, A.-P.Tuovien

University of Helsinki

Finland

tarhio@cs.Helsinki.FI

An interactive animation environment called Elliot is introduced. Eliot animates an algorithm written in a slightly modified version of the C programming language, giving the user immediate feedback of the algorithm's behaviour. Eliot visualizes data structures of the algorithm as moving graphical objects. Each data type has a selection of ready-made visual representations from which the user picks one for each data object. Based on these selected representations Eliot builds a full animation of the algorithm. As an animation generator, Eliot has several applications : algorithm design, visual debugging and learning to program.

COLOR DITHERING WITH N_BEST ALGORITHM

K.Lemström, J.Tarhio, T.Takala

University of Helsinki

Finland

{klemstro,tarhio}@cs.helsinki.fi

One of the most interesting problems of digital image processing is how much the color table can be reduced without any detectable difference in the quality of an image. The process of reducing the color information is known as quantizing. Usually a quantized image contains some visible errors, such as false contouring. Digital halftoning or spatial dithering is a process which tries to minimize visible quantization errors. A new method, called n-best, is presented for dithering color images. This method adds noise that is proportional to the quantization error. The n-best algorithm turns out to be a good compromise between the efficiency and the quality of the produced image.

ICONS FOR THE VISUALIZATION OF TENSOR FIELDS

A.De Liberato, L.Moltedo

Instituto per le Applicazioni del Calcolo, Rome

Italy

moltedo@cnriac.iac.rm.cnr.it

Multidimensional data coming from numerical simulations represent, usually, tensor fields. This paper deals with glyph icons we implemented for discrete visualization of second order tensor fields, in order to extent the mapping operations of MUDI3 system we have developed at IAC. Iconic representations of tensor fields we used to study a molecular dynamics problem are discussed too.

LOCAL ANALYSIS OF DYNAMICAL SYSTEMS _ CONCEPTS AND INTERPRETATION

H.Löffelmann, Z.Szalavári, E.Gröller

Institute of Computer Graphics, Vienna

Austria

{helwig,zsolt,groeller}@cg.tuwien.ac.at

We present several terms and definitions related to the local analysis of dynamical systems. Multiple terms for one and the same thing that were found in literature are put together to provide a "dictionary" of terms and to avoid potential confusion due to misleading definitions. Additionally, some important concepts which are necessary to analyze a dynamical system' are briefly discussed and a new procedure to locally analyze a dynamical system's behaviour near trajectory points is proposed. The paper should give computer graphics specialists, who work on the visualization of anlytically defined dynamical systems - but are not experts on the field of dynamical systems - a set of mathematical tools for a thorough investigation of the local behavior of such systems.

MESHING FOR DISCONTINUITY DRIVEN HIERARCHICAL RADIOSITY

A.A.Maierhofer, M.Gervautz, K.F.Karner

Graz University of Technology

Austria

{ali|gervautz|karner}@icg.tu-graz.ac.at

A discontinuity driven meshing algorithm is presented which keeps polygons well shaped and avoids the generation of T-vertices. The concept of split-hints is introduced enabling us to store splitting information for later use rather than immediately anchoring T-vertices. The concept allows to easily combine hierarchical subdivision of a scene and introduction of discontinuity edges representing shadow boundaries. The complete splitting algorithm using split-hints is given in pseudo-code producing a triangle mesh which can be used for fast Gouraud shaded rendering.

A NEW METHOD FOR FORMAL DESCRIPTION OF 3D SCENES

V.Manda, P.Slavík

Technical University, Prague

Czech Republic

xmanda@sun.felk.cvut.cz, slavik@cs.felk.cvut.cz

In this paper we deal with the problem of representation of 3D scenes. As far as the scene structure is concerned, it contains both objects and their relations. To capture this we propose to use a special graph grammar language. This language allows us to describe the objects in the scene and their properties, as well as the relations. Moreover, we can describe the constraints that can be imposed upon the scene. This particular paper introduces the idea and shows how to represent the objects in a simple eay using proposed concepts.

RADIOSITY TECHNIQUES FOR VIRTUAL REALITY - FASTER RECONSTRUCTION AND SUPPORT FOR LEVELS OF DETAIL

T.Möller

Clarus AB

Hungary

tompa@clarus.se

We present a method, aimed at VR applications with illumination calculated by radiosity, that provides faster reconstruction of the radiosity function of non-uniform rational B-splines (NURBS) and ultimate support for levels of detail, LODs. For each NURBS, an image, called an illumination map, which contains its illumination, is computed. Since many target machines for VR-rendering has support for real-time texture mapping, the illumination map is texture-mapped, using bilinear interpolation, onto the surface in order to rconstruct the radiosity function. We show that the polygon count, used when rendering, can be considerably reduced using our method. Also, by decoupling shading from geometry, our method supports LODs for VR in an ultimate way, since only one radiosity calculation is needed for every conceivable LOD. This also implies that the triangulation of surfaces could be altered, without recomputing the illumination, in order to trade-off real time rendering performance by surface NURBS. We have also implemented the method in a real world application with excellent results.

GENETIC ALGORITHMS AND IMAGE SEARCH

P.Mrázek

Czech Technical University, Prague

Czech Republic

xmrazek@sun.felk.cvut.cz

This article is intended to provide an introduction to Genetic Algorithms (GAs), concentrating on their abilities of function optimization. Basic features of GAs are presented in the first part. The second part describes one application : GAs are employed to search images for instances of known objects.

FORM FACTOR EVALUATION WITH REGIONAL BSP TREES

K.Nechvíle, J.Sochor

Masaryk University, Brno

Czech Republic

kodl@fi.muni.cz, sochor@fi.muni.cz

Form factor evaluation is an expensive and time consuming operation for radiosity applications. Visibility algorithms have to deal with a huge number of patches, rapidly increasing during an adptive subdivision. This paper presents one possible approach to visibility part of complex radiosity algorithm - dividing the scene to non-overlapping regions and creating hierarchical BSP tree with many regional BSP trees. The regional BSP approach offers possibility to solve radiosity in acceptable time without special HW.

AN EFFICIENT FRACTAL MODELLER (Modification of the Iterated Function Systems

S.S.Nikiel

Technical University of Zielona Gora

Poland

snikiel@irio.wsi.zgora.pl

Research and Development of fractal techniques for modelling and control over intricate artificial and natural phenomena fall in the scope of this paper. The principal objective is for close to real-time display of fractal structures. Iterated Function Systems rendering algorithms can be easily adapted to parallel processing. Modification of the IFS representation allows great speedup of the rendering process. Since the method relies on classical geometrical transformations, intricate structures such as clouds, plants etc. can be plugged in already existing graphical editors and virtual environments. Possible applications of the method include : travel & flight simulation, architectural design (CAD systems), art and home entertainment.

FULL_FRAME MERGING FOR SORT_LAST POLYGON RENDERING COMPUTER

J.M.Pereira, C.A.Wüthrich, M.R.Gomes

INESC, IST, Lisboa, Portugal

School of Architecture and Civil Engineering, Weimar, Germany

We propose a refinement of the Sort-Last algorithms' classification based on the scheduling of the rendering and merging steps.

Two algorithms whose rendering and merging steps run consecutively are described. Two different approaches were taken to implement the merging step : the Distributed Framebuffer approach and the Pipeline Composition approach. The load balancing problem is also discussed : a dynamic request-based mechanism is implemented at the end of the rendering phase.

Another solution, the ScanlineFlow Rasterization algorithm, is described. Its main characteristic resides on the fact that both steps, rendering and merging, run concurrently. This solution has provided good results and is a viable alternative to implement sort-last algorithms on a multicomputer.

The three algorithms made use of full-frame merging techniques because merging a full frame from each node is very regular and easy to implement.

Our developing platform consisted of a Parsytec MultiCluster machine with sixteen processors running the Helios Operating System and using the CDL (Component Distribution Language) parallel programming language.

CONSTRUCTING A HIGHLY IMMERSIVE VIRTUAL ENVIRONMENT : A CASE STUDY

D.Schmalstieg, Ch.Faisstnauer, T.Mazuryk

Institute of Computer Graphics, Vienna University of Technology

Austria

schmalstieg|faisstnauer|mazuryk@cg.tuwien.ac.at

Virtual reality (VR) applications raise enormous interest inside and outside computer science. Unfortunatelly, VR systems are rather complex, involving many software and hardware modules being integrated. Theoretical papers are not always of much aid in the actual implementation of VR applications. We try to fill this gap with a case study on a simple example VR system, that is used to demonstrate the most important aspects of a VR implementation, including application design, implementation strategy, selection of hardware and software, rendering, tracking and display technology. Special attention is paid to practical issues that are usually only learned by experience, and on the discussion of devices and methods that are inexpensive and readily available.

CONSTRAINT SATISFACTION PROBLEM SOLVED BY MINIMAL CHANGES METHOD

P.Simek, P.Slavík

Czech Technical University, Prague

Czech Republic

simekp@cslab.felk.cvut.cz, slavik@cs.felk.cvut.cz

Direct manipulation has become a very popular interaction technique in GUI's in the last few years. It allows the user to manipulate graphical objects in natural way. However, in complicated cases the user must perform complex manipulations that burden the user with many details. Therefore it is necessary to develop new techniques that are more user-friendly. One of many possible approaches is the use of constraints. By means of constraints it is possible to reduce the extent of interaction from the user as the constraints introduced express relations among objects that can be manipulated.

This paper describes a new technique that allows for interacting with graphical objects in an effective way. Moreover the implemented system contains features that visualize constraints. This supports the user during interaction as he/she can clearly see the mutual links between objects.

PARALLEL RADIOSITY ON A CLUSTER OF WORKSTATIONS

L.Sindlar, J.Pelikán

Faculty of Mathematics and Physics, Charles University

Czech Republic

{sindlar|pepca}@sun1.ms.mff.cuni.cz

A parallel version of progressive refinement radiosity with radiosity overshooting and adaptive surface subdivision is presented. A cluster of workstations under the operating system Unix was chosen as a parallel hardware. The whole system was organized according to the master - worker paradigm. We investigated how to adjust algorithms for run-time adptive surface subdivision and overshooting for such parallel hardware, especially if we use a relatively slow computer network or, moreover, a network with highly varying throughput. Variation in computer perfoemance (including the possibility that some workstations might crash) was also considered.

INTERACTIVE DESCRIPTION OF CONSTRAINED FORM-FEATURES

S.Strah, B.Zalik

Glass Production and Glazing Enterprise & University of Maribor

Slovenia

zalik@uni-mb.si

To increse a designer productivity, a reusibility of already designed geometrical objects is becoming one of the key techniques of actual geometric modelling systems. The use of geometric constraints and form-features seems to be a promising methodology to achieve this aim. In the paper, a 2D constraint-based geometric modelling system is considered. The aim of the system is to support interactive design and to automate the constraint definition. Constraints are applied on auxiliary geometry, while the desired visible geometry is built onto auxiliary geometrical data. A good property of the system is its ability to handle (and to constrain) free-form shapes (cubic Bezier curves). The main part of the paper highlights the work with the system using an example from the world of fonts.

OPTIMIZED LOCAL PASS USING IMPORTANCE SAMPLING

W.Stürzlinger

Johannes Kepler University Linz

Austria

stuerzlinger@gup.uni-linz.ac.at

Recent approaches to realistic image synthesis split the rendering process into two passes. The first pass calculates an approximate global illumination solution, the second produces an image of high quality (from a user selected view point) using the solution obtained in the first pass by applying the local illumination model to each surface point visible through each pixel.

This paper presents two new methods to compute the local illumination quickly. Instead of recalculating form factors and visibilities the information computed by a hierarchical radiosity solution algorithm is reused. The image generation time is reduced significantly by using stochastic methods.

APPLICATION OF OBJECT ORIENTED METHODS IN PROCESS VISUALIZATION

L.Szirmay-Kalos, G.Márton, T.Fóris, J.Fábián

Technical University of Budapest

Hungary

szirmay@fsz.bme.hu

This paper presents an approach to building process visualization systems. A visualization system must update a model of the visualized process from the measurements and provide its graphics presentation to the user. The proposed method defines both the model and its graphics presentation simultaneously and using graphics techniques. The only step which requires programming is the desription of the behaviour of component types. Using object-oriented approach, the behaviour is described by rules determining how an object reacts to messages from the process, other objects and from the user. From this definition and from the structure derived from the graphics schemes, the global system bahaviour is generated automatically. This allows for fast visualization system generation and requires only graphics editing if the underlying system structure changes.

BABEL : A GENERIC DATA STRUCTURE FOR GEOMETRIC MODELING

R.F.Tobler, H.Löffelman, T.Galla, W.Purgathofer

Technical University of Vienna

Austria

We present a basic data structure for geometric data which can be adapted to represent common geometry representations like CSG, BSP aso. The new data structure has been designed to be easy to use, and easy to extend. Due to the representation of geometric data using a directed acyclic graph, a number of the standard rendering algorithms can be used on the data structure in a very straightforward way. The new data structure has been implemented as a C++ library and can therefore serve as high-level tool for developing graphics applications, or as an extension for using C++ as a modeling language. As an additional benefit this new basic data structure captures the similarities of the indicated geometry representations, and thus leads to significant code reuse.

USING GENETIC ALGORITHMS TO IMPROVE THE VISUAL QUALITY OF FRACTAL PLANTS GENERATED WITH CSG_PL SYSTEMS

Ch.Traxler, M.Gervautz

Vienna University of Technology

Austria

{traxler|gervautz}@cg.tuwien.ac.at

PL-systems are a powerful and flexible technique for plant modeling. Unfortunately it is a hard task to specify a PL-system that generates a desired plant. Especially the tuning of the parameter values is time consuming and demands a lot of experience from the user. In this paper we describe how to apply genetic algorithms to CSG-PL-systems, which are a special class of PL-systems. A decomposition of CSG-PL-systems is introduced to extract those parts which can serve as genotype. Mutation and mating, the two major operations of evolution techniques, are applied to this data set. With the described method it is possible to find easily natural looking individuals out of a species that is described in an abstract way by the underlying CSG-PL-system.

EXPLOITING DEGREES OF FREEDOM ANALYSIS FOR INTERACTIVE CONSTRAINT-BASED DESIGN

Y.T.Tsai, T.Fernando, P.M.Dew

University of Leeds

U.K.

{tsai|ltpf|dew}@scs.leeds.ac.uk

This paper presents an interactive constraint solver which exploits the degrees of freedom (DOFs) of under-constrained models to satisfy constraints and to support direct manipulation. The evolving constraints are maintained in a directed graph referred to as the Relationship Graph. A DOF technique referred to as allowable motion has been integrated with graph based algorithms to enable the constraint satisfaction, incrementally. Four basic constraint satisfaction methods (basic allowable motion, locus analysis, inverse operation and hybrid method) have been implemented which traverse the relationship graph to exploit the DOF of the under-constrained models to satisfy a given constraint. The direct manipulation of the under-constrained models is supported by combining the constraint satisfaction methods and graph re-writing techniques. These techniques handle constraint loops efficiently without resorting to time consuming numerical approaches.

CHECKING BOUNDARY NON-MANIFOLDNESS OF SOLID OBJECTS FOR STEEL CONSTRUCTION

E.Tsegaye, F.Werner, C.A.Wüthrich

School of Architecture and Civil Engineering, Weimar

Germany

{tsegaye,werner}@bauing.hab-weimar.de, caw@informatik.hab-weimar.de

One of the major limitations of most of the currently available commercial CAD systems is the fact that they lack the possibility of representing non-manifold solids. This leads to the consequence that big limitations are imposed on the types of solids representable in a system : for example, neither dangling faces are allowed, nor are solids obtained through one-dimensional soldering of steel profiles. This paper presents an algorithm directly derived from the definition of 2-manifoldness which performs local checks on the manifoldness of a solid around one of its vertices. The algorithm builds the face-vertex incidence matrix around a vertex of the solid, and deducts the number of angles topologically equivalent to the open disk incident into the vertex. The algorithm is based on the face-vertex representation of a solid but can be easily extended to work on traditional edge-based or wing-edge data structures. The method has been developed for GT4Steel, a new CAD system for steel construction which allows to represent and manipulate non-manifold objects.

AUTOMATED TEXTURE EXTRACTION FROM MULTIPLE IMAGES TO SUPPORT SITE MODEL REFINEMENT AND VISUALIZATION

X.Wang, J.Lim, R.T.Collins, A.R.Hanson

University of Massachusetts

U.S.A.

xwang@cs.umass.edu

Texture mapping has wide and important applications in visualization and virtual reality. Surface texture extraction from a single image suffers from perspective distortion, data deficiency, and corruption caused by shadows and occlusions. In this paper, a system is developed for automated acquisition of complete and consistent texture maps from multiple images in order to support subsequent detailed surface analysis and scene rendering. Given camera and light source parameters for each image, and a geometric model of the scene, the textures of objects surfaces are systematically collected into an organized orthographic library. Occlusions and shadows caused by objects in the scene are computed and associated with each retrieved surface. A "Best Piece Representation" algorithm is designed to combine intensities from multiple views, resulting in a unique surface intensity representation. Detailed surface structures, such as windows and doors, are extracted from the uniquely represented surface images to refine the geometric model. Experiments show successful applications of this approach to model refinement and scene visualization.

PROJECTION IN BARYCENTRIC COORDINATES

S.Zachariás

University of West Bohemia, Pilsen

Czech Republic

At the beginning of this paper some elementary properties of the simplices, barycentric coordinates, convex polyhedra, affine ratio of three points and Euler's theorem are mentioned. The reader who wishes to know more about the geometrical background is referred to [1]. A central projection in n-dimensional Euclidean space is modelled with the help of barycentric coordinates, the center of the projection is a vertex of the simplex, the opposite hyper-side is the hyperplane of the projection (hyper-scereen). The direction of the parallel projection is chosen as the direction of one edge of the simplex.

OPTIMISATION OF SUBSPACE EVALUATION IN RAY_TRACING

P.Zemcík

Technical University of Brno

Czech Republic

zemcik@dcse.fee.vutbr.cz

Various space subdivision techniques are being used to speed-up rendering of graphics scenes when using ray tracing and particle tracing. How successful these techniques are depends on how closely the space subdivision algorithms can adapt to shape of the objects in graphics scene and how fast the subspace traversing is. This contribution presents a modified approach to space subdivision and representation of the data that can further save time and increase speed.

Invited Lecturers

Hosted by Graphics & Media Lab. http://graphics.cs.msu.su

mailto: Webmaster