102
Volume Modelling And Rendering Based On 3D Voxel Grids Diplomarbeit Jan Müller Institut für Computervisualistik Universität Koblenz-Landau erstellt am Fraunhofer-Institut für Angewandte Informationstechnik FIT vorgelegt von: Jan Müller Matrikel-Nr.: 200210323 12.08.2005 Prüfer: Prof. Dr. Stefan Müller, Universität Koblenz-Landau Betreuer: Dipl.-Inform. Jan Ohlenburg, Fraunhofer FIT

Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Volume Modelling And RenderingBased On 3D Voxel Grids

Diplomarbeit

Jan Müller

Institut für ComputervisualistikUniversität Koblenz-Landau

erstellt am Fraunhofer-Institutfür Angewandte Informationstechnik FIT

vorgelegt von:

Jan MüllerMatrikel-Nr.: 200210323

12.08.2005

Prüfer: Prof. Dr. Stefan Müller, Universität Koblenz-LandauBetreuer: Dipl.-Inform. Jan Ohlenburg, Fraunhofer FIT

Page 2: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-
Page 3: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Eidesstattliche Erklärung

Hiermit erkläre ich an Eides statt, dass die vorliegende Arbeit selbständig verfasstwurde und keine anderen, als die angegebenen Quellen und Hilfsmittel verwendetwurden. Die Arbeit wurde bisher in gleicher oder ähnlicher Form keiner anderenPrüfungsbehörde vorgelegt und auch nicht veröffentlicht.

—————————- —————————-Ort / Datum Unterschrift

i

Page 4: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

ii

Page 5: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Danksagung

Nur durch die Unterstützung und das Verständnis von vielen Seiten war es möglich,diese Diplomarbeit in wenigen Monaten zu erstellen.Insbesondere möchte ich Prof. Dr.-Ing. Stefan Müller danken für das Vertrauen, daser in mich gesetzt hat, aber auch für seine Hilfe in unseren zahlreichen Dialogenzu den verschiedensten Fragestellungen. Außerdem meinem Betreuer Dipl.-Inform.Jan Ohlenburg vom Fraunhofer-Institut für Angewandte Informationstechnik, der mirgleichermaßen viele Freiheiten und eine helfende Hand zur Verfügung gestellte hat.Durch ihn wurde es erst möglich, dass diese Diplomarbeit über sich hinaus wuchsund in der Evaluation auch aufwändigste Virtual Reality Hardware zum Einsatz kom-men konnte. Schließlich möchte ich meiner Familie, am meisten meiner FreundinMichelle Martin danken, die mich mit ihrem Beistand moralisch gestärkt hat und diedie vergangene Zeit deutlich weniger anstrengend werden ließ, als sie es ohne ihreHilfe gewesen wäre.

iii

Page 6: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Zusammenfassung

Ziel dieser Diplomarbeit ist es, die Vorzüge von dreidimensionalen Voxeln, alsoVolumen-Elementen, die in einer Gitterstruktur angeordnet sind, für die Model-lierung zu untersuchen. Die zugrunde liegende These besagt, dass solche Voxeleher für eine intuitive Skulpturierung geeignet sind, als zum Beispiel das üblicheModellierungsprimitiv Dreieck. Der Grund liegt darin, dass es keine ausdrücklicheVoxelnachbarschaft gibt, die wie bei Polygonen geometrisch verbunden ist; die Vox-elumgebung wird nur implizit durch die Position im Gitter bestimmt. So werdeneinfache Eingriffe, wie das Addieren und Subtrahieren von Voxel, aber auch dasMalen auf die Voxeloberfläche möglich, ohne komplexe Berechnungen durchführenzu müssen.Damit ist in diesem Fall das Modellieren auf Voxelgittern vorraussichtlich amehesten mit der Bildhauerei vergleichbar, im Gegensatz zu klassischen Dreiecks-Modellierungsumgebungen, in denen Modelle eher technisch konstruiert werden.Die Einarbeitungszeit in die Voxel-Modellierung sollte wesentlich kürzer ausfallen,als dies bei komplexen, polygonalen Profi-Werkzeugen wie Autodesk’s 3D StudioMax der Fall ist.Die Motivation für diese Arbeit liegt also zum einen in der Möglichkeit, eine ein-fache und leicht zugängliche Art der dreidimensionalen Modellierung zu erforschen.Zum anderen könnten sich in Zukunft holographische oder volumetrische Aufnah-men gegenüber zweidimensionalen Fotos durchsetzen und somit einen neuen Marktfür die unkomplizierte Nachbearbeitung solcher Abbildungen schaffen.Um die Bearbeitung von größeren Volumen zu ermöglichen, mussten allerdingszunächst Möglichkeiten untersucht werden, wie solche Volumengitter einer beispiel-haften Größe von 5123 Voxeln in Echtzeit dargestellt werden können. Dazu wurdenverschiedene Darstellungsansätze, unter anderem mit Hilfe moderner, programmier-barer Grafikkarten, implementiert und ihre Leistungsfähigkeit verglichen.Darüber hinaus wurden verschiedene Werkzeuge und Schnittstellen für die Interak-tion mit dem Volumen evaluiert. Insbesondere musste die Navigation im dreidimen-sionalen Raum benutzerfreundlich gestaltet werden. Neben verschiedenen software-seitigen Hilfsmitteln wurde auch der Einsatz von 3D Virtual Reality Hardware un-

iv

Page 7: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

v

terstützt, um einen möglichst plastischen und realitätsnahen Eindruck der Skulpturvermitteln zu können. Aber auch die Eingriffsmöglichkeiten auf das Volumen unddessen Oberfläche selbst mussten teilweise völlig neu entwickelt werden, da darübernur wenige Veröffentlichungen vorlagen. So wurde eine Sammlung von Werkzeugengeschaffen, die den Anwender befähigen, in Echtzeit das Voxelgitter zu modellieren.Unter anderem wurden boolesche Operationen mit mathematischen Primitiven, aberauch Ray-Tracing gestützte Sprühwerkzeuge zur Oberflächenbearbeitung implemen-tiert.Die Ergebnisse der Arbeit zeigen deutlich, dass selbst Probanten, die im dreidimen-sionalen Modellieren vollkommen ungeübt sind, nach wenigen Minuten Einarbeitungeffizient das Voxelvolumen skulpturieren können. Eine komplexe Szene die ein Haus,einen See, einen Baum und einen Hügel enthalten sollte, wurde mehrheitlich binnenweniger Minuten gestaltet. Durch den Einsatz von Virtual Reality Hardware wieeiner 3D Stereo Brille, Head Tracking und einem kabellosen Gamepad mit haptis-chem Feedback könnte die Bedienbarkeit gegenüber der klassischen Ein- und Aus-gabe mit Monitor und Tastatur/Maus nochmals klar verbessert werden. Auch dievorgeschlagenen Werkzeuge für boolesche Operationen und Oberflächengestaltungwurden positiv bewertet.Als effizienteste Darstellungsmethode hat sich eine hybride GPU/CPU Lösung er-wiesen, die die Volumenoberfläche mittels 3D Texturen in einem GLSL Shader ab-tastet und die Oberflächenvoxel in Software beleuchtet und gegebenenfalls filtert. Fürdie Implementierung kamen C++, OpenGL, GLSL Shader sowie die API Qt für dieBenutzeroberfläche zum Einsatz.

Page 8: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Abstract

In this diploma thesis voxels are evaluated as a primitive for a volume modelling envi-ronment. In order to implement a suit called "Virtual Sculpture", different renderingand modelling techniques are compared. Various approaches for volume renderinglike surface graphics, indirect volume rendering and direct voxel grid visualisationare presented. Hardware accelerated GPU texture slicing is chosen as the optimaltechnique for real time volume rendering. Furthermore a ray tracing system is imple-mented in parallel to sample the volume’s surface for tool-object interaction, but alsoto utilise this software-only visualisation technique as a basis of comparison. Bothapproaches are accelerated by a spacial subdivision structure.The render cores can be combined with different colouring and lighting modes: aGLSL shader, which computes the output image completely on the GPU, a softwareshader that draws the voxels based on an extracted index map in software and a pointcloud mode, which generates a 3D OpenGL point for every index on that map. TheGPU accelerated core outperforms the ray tracing system by a factor of 2 to 15 and isable to render a volume of 5123 voxels at about 10 frames per second. The GPU/CPUmixed modes are superior to the GPU only mode, since their GLSL shader is onlyused for surface sampling and thus smaller and faster.Previous publications in the field of volume modelling are presented, especially con-cerning input devices and sculpting tools for the voxel grid manipulation. Three kindsof tools are implemented to allow an intuitive way of 3D modelling: Boolean primi-tives are used to form basic shapes. Ray tracing based spray tools are most suitablefor surface sculpting and control functions like undo and marker based selection toolsare used for error correction. Utilising the Qt API, a graphical user interface withseparate windows for image output, global options, tool selection and tool optionsis created. Next to the standard mouse/keyboard combination, a wireless gamepadwith rumble feedback as well as head tracking are supported as input devices for anVR/AR scenario. Also quad buffered stereo rendering and a video background tex-ture are implemented to increase the number of possible fields of application.To improve the volume modelling using scalable 3D tools with six degrees of free-dom, various supporting systems are applied. The 3D navigation is being simplified

vi

Page 9: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

vii

for example by aligning the tools moving axis to the volumes orientation or by rotat-ing the tool with the volume. Finally "Virtual Sculpture" is tested in a user evalua-tion: After only 10 minutes of practice 16 out of 18 participants are able to sculpturea complex voxel scenery consisting of a house, a tree, a lake and a mountain/hillwithin only 15 minutes.

Page 10: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Contents

1 Introduction 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Layout of this Work . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Specification Analysis 52.1 Rendering Requirements . . . . . . . . . . . . . . . . . . . . . . . 52.2 Modelling Requirements . . . . . . . . . . . . . . . . . . . . . . . 6

3 Previous Work In Volume Rendering 73.1 Volume vs Surface Point Graphics . . . . . . . . . . . . . . . . . . 8

3.1.1 Surface Splatting . . . . . . . . . . . . . . . . . . . . . . .103.1.2 QSplat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.1.3 Pointshop 3D . . . . . . . . . . . . . . . . . . . . . . . . .11

3.2 Direct vs Indirect Rendering . . . . . . . . . . . . . . . . . . . . .123.2.1 Surface Construction . . . . . . . . . . . . . . . . . . . . .133.2.2 Implicit Surfaces . . . . . . . . . . . . . . . . . . . . . . . 14

3.3 Direct Volume Rendering Techniques . . . . . . . . . . . . . . . .143.3.1 Ray Casting . . . . . . . . . . . . . . . . . . . . . . . . . .153.3.2 Texture Slicing . . . . . . . . . . . . . . . . . . . . . . . . 163.3.3 Shear-Warp Rendering . . . . . . . . . . . . . . . . . . . .17

3.4 Acceleration Strategies for Volume Graphics . . . . . . . . . . . . .18

4 Previous Work In Volume Modelling 204.1 Volume Modelling Techniques . . . . . . . . . . . . . . . . . . . .20

4.1.1 Surface Modelling . . . . . . . . . . . . . . . . . . . . . . 214.1.2 Constructive Volume Geometry . . . . . . . . . . . . . . .224.1.3 Volume Sculpting on Voxel Grids . . . . . . . . . . . . . . 23

4.2 User-Sculpture Interaction . . . . . . . . . . . . . . . . . . . . . .254.2.1 Haptic Rendering and Deformations . . . . . . . . . . . . .254.2.2 Modelling Acceleration . . . . . . . . . . . . . . . . . . . 26

viii

Page 11: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

ix

5 Virtual Sculpture 295.1 Technical Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . .29

5.1.1 Program Structure . . . . . . . . . . . . . . . . . . . . . .295.1.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . 315.1.3 VR/AR Support . . . . . . . . . . . . . . . . . . . . . . . . 31

5.2 The Grid Object Class . . . . . . . . . . . . . . . . . . . . . . . .325.2.1 The Virtual Coordinate System . . . . . . . . . . . . . . . .325.2.2 Memory Costs And Grid Sizes . . . . . . . . . . . . . . . .325.2.3 Data Representation . . . . . . . . . . . . . . . . . . . . .34

5.3 The Rendering System . . . . . . . . . . . . . . . . . . . . . . . .345.3.1 The Texture Slicing Render Core . . . . . . . . . . . . . . .355.3.2 Acceleration Strategies for the Texture Slicing Core . . . . .385.3.3 The Ray Tracing Render Core . . . . . . . . . . . . . . . .395.3.4 The Render- and Shading- Modes . . . . . . . . . . . . . .425.3.5 Performance Comparison . . . . . . . . . . . . . . . . . . .44

5.4 The Modelling Tools of Virtual Sculpture . . . . . . . . . . . . . . 475.4.1 Construction Tools . . . . . . . . . . . . . . . . . . . . . .475.4.2 Spray Tools . . . . . . . . . . . . . . . . . . . . . . . . . . 495.4.3 Control Tools . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.5 The User Controls . . . . . . . . . . . . . . . . . . . . . . . . . . .515.5.1 Graphical User Interface . . . . . . . . . . . . . . . . . . .515.5.2 3D Navigation . . . . . . . . . . . . . . . . . . . . . . . . 51

6 User Evaluation 556.1 The User Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . .566.2 Results of the Evaluation . . . . . . . . . . . . . . . . . . . . . . .64

7 Last Words 717.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 717.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 727.3 Technology Review . . . . . . . . . . . . . . . . . . . . . . . . . .73

A Source Codes 75A.1 GPU Shader for Surface Sampling . . . . . . . . . . . . . . . . . .75A.2 GPU Shader for GPU only mode . . . . . . . . . . . . . . . . . . .77A.3 GPU Render Core Main Loop for Z-Axis . . . . . . . . . . . . . . 80

B Gallery 82

Page 12: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

List of Figures

1.1 3D Scan of St. Matthew . . . . . . . . . . . . . . . . . . . . . . . . 2

3.1 Volume Graphics Pipeline for 3D Voxel Grids . . . . . . . . . . . . 83.2 Comparison between vector graphics and raster graphics . . . . . .93.3 QSplat model "Lucy" (top half - front) . . . . . . . . . . . . . . . . 113.4 Pointshop 3D surfel model "gnome" . . . . . . . . . . . . . . . . .123.5 Marching Cubes Surface Generation . . . . . . . . . . . . . . . . .133.6 Marching Cubes: the 15 resulting cell state combinations . . . . . .143.7 Volume projection of direct rendering and surface splatting . . . . .153.8 Classical Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . .153.9 View aligned and object aligned texture slicing . . . . . . . . . . .173.10 The Shear-Warp Algorithm . . . . . . . . . . . . . . . . . . . . . .18

4.1 Point-based modelling and rendering using radial basis functions . .214.2 Virtual Clay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.3 Constructive Volume Geometry . . . . . . . . . . . . . . . . . . . .224.4 "Sculpting : An Interactive Volumetric Modeling Technique" . . . .234.5 Comparison between ordinary marching cubes (left) and EMC . . .244.6 The Spherical Display of the Virtual Sculptor System . . . . . . . .254.7 The 5DT Data Glove 14 Ultra . . . . . . . . . . . . . . . . . . . .264.8 The SensAble Phantom, 6 DOF haptic input device . . . . . . . . .274.9 Adaption of magnitude and direction of the drilling force . . . . . .28

5.1 The structure of Virtual Sculpture . . . . . . . . . . . . . . . . . .305.2 The coordinate systems of Virtual Sculpture. . . . . . . . . . . . . .335.3 Texture Slicing: The Nearest Side / The Uniform Sub Division . . .365.4 Texture Slicing Areas . . . . . . . . . . . . . . . . . . . . . . . . .365.5 A Voxel-Index Map . . . . . . . . . . . . . . . . . . . . . . . . . . 375.6 Computation of Texture Coordinates for Subdivision Areas . . . . .395.7 The Ray Generation . . . . . . . . . . . . . . . . . . . . . . . . . .395.8 3DDA vs. Quickstep Traversal . . . . . . . . . . . . . . . . . . . .40

x

Page 13: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

xi

5.9 The Different Render Modes of Virtual Sculpture . . . . . . . . . .425.10 GPU / CPU Software Shader Mode Image Quality Example . . . .435.11 Software Shader Mode with Activated Normal and Colour Filtering445.12 Benchmark of all 5 Render Modes . . . . . . . . . . . . . . . . . .455.13 A Complex Volume with 5123 Voxels . . . . . . . . . . . . . . . . 465.14 Benchmark of all 5 Render Modes Rendering a 5123 Voxel Grid . . 465.15 Boolean Operations Between the Volume and 3D Primitives . . . .475.16 The Selection Tool . . . . . . . . . . . . . . . . . . . . . . . . . .505.17 Virtual Sculpture’s Graphical User Interface . . . . . . . . . . . . .52

6.1 Age Chart of the Evaluators . . . . . . . . . . . . . . . . . . . . . .656.2 Experience of the Evaluators with PCs and Modelling . . . . . . . .656.3 Personal Appraisal of the Modelling Results . . . . . . . . . . . . .666.4 Acceptance of the Boolean Primitives . . . . . . . . . . . . . . . .666.5 Acceptance of the Spray Tools . . . . . . . . . . . . . . . . . . . .676.6 Acceptance of the Selection Tools . . . . . . . . . . . . . . . . . .676.7 Appraisal of the Supporting Systems for Tool Interaction . . . . . .686.8 General Questions About the Evaluation . . . . . . . . . . . . . . .696.9 Possible Fields of Application . . . . . . . . . . . . . . . . . . . .70

7.1 The Object Space of a Possible Multi-Grid Version of Virtual Sculpture73

B.1 Result Volumes of the Virtual Sculpture User Evaluation . . . . . .85B.2 A Virtual Sculpture Example Object . . . . . . . . . . . . . . . . .85

Page 14: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Chapter 1

Introduction

Triangles have prevailed as the smallest descriptive element for real time 3D graphics.Modern GPUs1 are designed to accelerate this specific primitive in common appli-cations, games and all kinds of virtual environments. Their increasing parallelismand programmability allow not only realistic shading, but also make GPGPU2 an in-teresting field for a wide variety of scientific researches. Other primitives like lines,points and voxels3, although better suited for various tasks like particle simulations orvolume visualisation, take little influence on the development of graphic processorsand drivers. Together with the rapidly growing computation power of modern GPUsthe complexity of triangle meshes increases. Moore’s Law [22], which states that thecomplexity, meaning the amount of transistors of integrated circuits increases by afactor of two per year. Also this rule applied for GPUs for a long time. The term"Moore’s Law cubed" has been introduced as soon as their performance has begun todouble every 6 months due to their parallelised architecture. Today rendering qualityoften depends equally on texturing and lighting as it does on the granularity of thegeometric models. Therefore the number of triangles of an average single entity in acomputer game did grow from some hundred in 1997 to sometimes ten thousands ofpolygons in 2005 and the overall performance has been increased by more than a fac-tor of ten [3]. If a higher level of detail cannot be reached by increasing the geometricresolution of a mesh, usually it will be textured with larger and multiple blended tex-ture maps. Due to the high polygon count it happens that multiple triangle verticescollapse into less than one on-screen pixel and cause a definite overhead: instead ofa single three dimensional point, three vertices have to be considered and instead ofone RGB(A) colour, interpolated texture look-ups have to be performed. In such ascenario a point or voxel based geometry representation can solve the overhead and

1GPU: graphic processing unit, the main processor of modern 3D acceleration hardware2GPGPU: general purpose computation using graphics hardware(GPUs)3voxel: volume element, an atomic part of a volume

1

Page 15: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 1. INTRODUCTION 2

prove itself beneficial even in classic rendering environments.The lack of connectivity between voxels is the advantage and disadvantage of volumegraphics at the same time: it makes real time animation very difficult, but allows ahigh flexibility and robustness concerning alterations. Furthermore volumes naturallyconsume much more memory than surface representations. Their strength lies in thesimulation of deformations, in the rendering of half-transparent data sets gained from3d scanners and medical applications, in the visualisation of huge objects with veryhigh geometric detail and the possibility to sculpture them in an intuitive way in realtime.

1.1 Motivation

Figure 1.1: 3D Scan of St. MatthewA 3D laser scan of Michelangelo’s unfinished statue of the apostle St. Matthew. The

surface is generated measuring the distance between each point and the laserscanning device.

While the efficient rendering of volume data using various acceleration structuresis a well covered area of research [21], only few publications are concerned in thesculpting process of these object representations [27]. Voxels arranged in 3D gridshave however a great potential as a modelling primitive; unlike triangle meshes sucha volume object can be altered without need of recomputation of the surface. The

Page 16: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 1. INTRODUCTION 3

sculpting can be performed in very natural ways like it is done by stone sculpting.My motivation is to evaluate voxel grids as a data structure for intuitive volume mod-elling. The metaphor of sculpting a block of sandstone is by far more comprehensiblefor common computer users than the classic idea of constructing polygonal meshes asit is done by modelling tools like Autodesks’s 3D Studio Max. The learning phase ofsuch environments is considered to be long and extensive. The official tutorial from3D Studio Max 5.0 for an apple for example is denoted with 25 minutes, whereasthe tutorial for a claw takes 45 minutes without an introduction to the required usercontrols [1]. A multitude of books and expensive classes accomodate this concernand train their readers in polygonal construction [2]. The sculpting of voxel gridson the other hand is presumably fairly intuitive and straight forward. The possibilityto form shapes of high detail using modern input devices could lead to a new kindof easy 3D-drafting or rapid prototyping applications. Virtual reality technology likehaptic joysticks and 3D stereo glasses could allow a 3D object handling very nearto the real-life archetype of sculpting and chiselling. But it is in need of a robustfundament consisting of interactive tools and real time volume visualisation.A possible future application of this technology is the post-processing of 3D photog-raphy. The possibility to take three dimensional images like it can be done with 3Dscanning devices, might be a killer application on the future consumer market (Fig-ure 1.1). These 3D images are usually represented as point clouds or voxel grids, asthey are already used in several point-based applications. When consumer 3D cam-eras will be available in future, an intuitive way to manipulate and alter such imagerywill be necessary.

1.2 Layout of this Work

After this introduction the guidelines of the work will be specified in the followingchapter. The aims of this thesis will be described and the requirements which arenecessary to reach the goals will be characterised. The main part of this thesis isdivided into three major chapters:in the Chapter 3 previous work in the field of volume rendering is pointed out andcompared in its context. Doing so the main focus is laid on direct volume visualisa-tion techniques, due to their capability for interactive frame rates.In the consecutive Chapter 4 various approaches to volume modelling and user-volume interaction will be presented. Besides former approaches to direct volumemodelling, input and output devices for 3D sculpting are pictured.In Chapter 5 the modelling application called Virtual Sculpture, which developedfrom this work will be introduced. Next to the different volume rendering approachesthat have been implemented and are compared using benchmarks, the requirements

Page 17: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 1. INTRODUCTION 4

for intuitive 3D modelling are discussed. The created toolset is described in detail.Chapter 6 outlines the results of the user evaluation in which the 3D sculpting possi-bilities have been tested by modelling a voxel landscape.Finally, chapter 7 resumes the achievements of this diploma thesis and gives an out-look on the possible use of volume sculpting in the future. The appendix presentsa gallery of sculptures which have been generation in the evaluation process of thevolume modelling system. Also a list of source codes has been delivered.

Page 18: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Chapter 2

Specification Analysis

The aim of this work is to examine possibilities to shape and render massive voxelbased volumes in real time. Beside an appropriate visualisation technique, differentsculpturing tools for interactive and intuitive modelling have to be implemented. Theusability of these tools and fitting control devices are to be evaluated. Working at thedeparture CVAE at Fraunhofer FIT1, functionalities necessary for virtual and aug-mented reality scenarios like 3D stereo output and head tracking are integrated intothe volume modeller to further improve the usability.

2.1 Rendering Requirements

Using volumes as a data representation in this work means the presence of a regulargrid of voxels, from which the visible surface has to be sampled. Each voxel canbe seen as a 3D point relative to the origin of the grid. Further each point can haveits own normal and material and has an expansion that covers the voxel area fromeach point of view. A massive amount of voxels is necessary to form a coherentand adequately covered modelling volume. As a guideline for this work up to5123 volume points have to be handled, which is regarded as a large voxel grid incorresponding literature [13]. Without reducing material information and by savingabsolute voxel positions, this would require over 3.5GB RAM, which exceeds theaverage memory size of current desktop PCs.

Voxeldata:position = float [x,y,z] = 96 bit Data;material = unsigned byte [R, G, B, (A)] = 32 bit Data;normal = float [dX, dY, dZ] = 96 bit Data;

1Fraunhofer Institute for Applied Information Technology, Collaborative Virtual and AugmentedEnvironments Department, St. Augustin, Germany

5

Page 19: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 2. SPECIFICATION ANALYSIS 6

voxel = [position, material, normal];Memory usage for5123 voxels:5123 * sizeof(voxel) = 134.217.728 * 28 byte = 3584 MB;

Therefore the data amount has to be limited and the memory requirementshave to be cut back by reducing the information saved in a single voxel. Findingan adequate data representation for the volume is significant for the success of thiswork.The requirement of real time rendering demands the adoption of efficient accelerationstrategies for the used sampling approach. Because the resulting system will be usedfor modelling purposes unlimited in their extent, exploiting geometric coherence byusing precomputed data structures is widely prohibited. Therefore different samplingand shading solutions should be evaluated that are capable to efficiently visualise thevolume without the need of precomputations.For interactive modelling I consider 10 frames per second as an absolute minimumrequirement. The average when rendering a non-optimal volume should be signifi-cantly higher to allow frequent updates of the user input. The image resolution onthe other hand is of inferior meaning as long as it does not drop below a standardoutput size like 640*480 pixels.

2.2 Modelling Requirements

For interactive sculpting of the volume data a set of tools has to be implementedwhich offers a wide variety of sculpting techniques. Next to straight-forward booleanmodelling like adding and subtracting of points, methods for easy surface manipula-tion have to be found. Artistic spray-tools and surface filters based on ray tracing willbe examined. The user interaction should allow to sculpture intuitively even organicobjects after only a short learning period.Furthermore, the use of stereo viewing devices like HMDs2 and shutter glasses haveto be considered and an appropriate input system for user interaction in virtual real-ity scenarios has to be found. The control of three dimensional sculpting tools with6 degrees of freedom and the interaction with a movable and rotatable volume is acomplex task, which has to be simplified to enhance the usability.

2Head Mounted Display

Page 20: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Chapter 3

Previous Work In VolumeRendering

Volumes are regarded to be data sets of atomic 3D points that contain scanned fea-tures like densities, gradients, pressures or any other kind of a sensorially acquiredattribute. Most real-life volumes originate from medical scans. Those volumes oftenconsist of hundreds of body slices with density information. A common resolutionwould be 512 slices of 512*512 pixel resolution containing 16 bit values. A volumeof that dimensions requires 256 MB memory without additional information likenormals [13]. To render such amounts of data in real time, adequate accelerationstrategies are necessary.Equilateral voxel grids simplify the use of acceleration structures and traversal, butthere are also visualisation methods for rectilinear grids of non-uniform cells. Themost important action is to apply a subdivision structure which exploits spacialcoherence. Empty space is defined by voxels with zero opacity or a value below aspecified threshold. Such voxels consume large amounts of memory as long as nomulti-resolutional volume representation is in use. A subdivision can also be used toaccelerate various rendering approaches drastically, but at expense of flexibility andmodifiability, because it has to be recomputed when the volume was changed.To render a volume means to blend the overlapping visible voxels - for the activeviewing perspective - depending on their material information onto the imageplane. Whether the voxels are blended from front to back or back to front dependsprimarily on the used projection method, the existence of half-transparancies andused acceleration technique. A transfer function defines the exact visible informationemerging from the volume data commonly gathered by MRI1, X-Ray or laser 3Dscanning devices. The volume classification maps distinct attributes of the scannedtissue to well-defined material features for the final image projection like RGB

1 MRI : Magnetic Resonance Imaging

7

Page 21: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 3. PREVIOUS WORK IN VOLUME RENDERING 8

colours and opacity. This function can be implemented as a simple texture look-upin a fragment shader2, but also as a complex non-linear transformation.

Figure 3.1: Volume Graphics Pipeline for 3D Voxel Grids

The volume graphics pipeline (3.1) for three-dimensional voxel grids comprisesthree domains: the volume domain, in which volume information is collected andstored in the grid representation, the surface domain, in which the volume is pro-jected and the visible surface is sampled, and finally the image domain, where colourinformation is generated and rendered to the screen. The computational most expen-sive process of this volume pipeline is the gathering of surface points from a volume.If transparencies exist, data inside the volume have to be regarded and interpolated.Therefore many voxels can blend into a single surfel3 which is projected and shadedto render the final image. Surface graphics circumvents this interpolation step toallow real time rendering.

3.1 Volume vs Surface Point Graphics

The comparison between volume and surface graphics, as that between points andpolygons as a primitive, has many parallels to that of raster and vector graphics (Fig-ure 3.2). When the detail level of a 2D picture stays below a certain threshold, vector

2fragment shader: program which runs on a programmable GPU and computes information for eachscreen pixel

3surfel : short for SURface ELement, the primitive of surface-point graphics

Page 22: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 3. PREVIOUS WORK IN VOLUME RENDERING 9

Figure 3.2: Comparison between vector graphics and raster graphicsThe comparison between vector graphics and raster graphics is equivalent to that

between surface graphics and volume graphics in the third dimension. This table canbe found in "Volume Visualization: Principles and Advances" [13].

graphics occupy much less memory than pixel-based image formats. Also the qual-ity is higher, because edges can be anti-aliased and scaled without loss of sharpness.Points and raster graphics are in advantage, when the granularity, which in 2D im-ages applies to the amount of different colours and thus the sizes of homogenousareas, becomes very high. Volumes surpass surfaces, when frequent deformationsand other alterations take place, because they hold interior data, which otherwise hasto be computed when a surface is deformed.Other than direct volume visualisation, surface rendering of volumes only considersthe border between the inside and outside of a defined object, not its interior. Eitherthis surfel cloud is converted from a triangle mesh or is directly generated by a 3Dlaser scanning device. The extracted volume surface can be saved as a point cloudencapsulated in a bounding hierarchy. As a result the memory cost of a surface repre-sentation falls drastically below that of a volume and the rendering performance canbe increased equally radical. While volumes are more resistant to artifacts originatingfrom sculpting and deformations, a surface has to be recomputed after a substantialalteration took place. A major problem is to avoid holes or at least to fill them upwhen the object is rendered. Therefore the modelling capabilities of applicationsconcentrating solely on surface points are usually very limited.

Page 23: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 3. PREVIOUS WORK IN VOLUME RENDERING 10

3.1.1 Surface Splatting

Surface splatting was introduced by Matthias Zwicker, who also published many ofthe fundamental techniques behind the later introduced PointShop 3D [43], as a pos-sible solution for accelerated and interpolated surfel rendering. Splatting can be seenas process to accumulate the contribution of all voxels to an image surfel using a 3Dreconstruction filter. The surfels are "splatted" against the image plane to generatethe output image, each surfel resulting in a blended colour area rather than a singlepixel. The interpolation kernels can be precomputed and saved as a look-up texture,which allows real time rendering. A splatting filter method with very high imagequality is the Elliptical Weighted Average(EWA) [44]. EWA consists of a 3D Gaussreconstruction kernel and a 2D low pass filter for artifact-less surface projection.The research of surfels as a rendering primitive is heading towards real time applica-tions and games. Facilities like the Mitsubishi Electronic Research Laboratories [41]have worked on real time rendering pipelines pre-processing textures and surface in-formation into a surfel representation. Great effort has also been spent in order to en-able GPU fragment and vertex shader acceleration of EWA based image filtering andsurface splatting. A hierarchical data structure called sequential point trees (SPT) [7]was introduced. It‘s sequential processing makes SPT well suited for a GPU shaderimplementation. The processing on the CPU4 can be limited to pre-culling, while theGPU efficiently computes a level of detail point selection, even regarding a point‘stexture and local curvature. The same paper furthermore dealt with approaches of hy-brid triangle/point based graphical environments: surfel clouds would only be usedwhere high geometrical detail was needed and triangles efficiently covered areas oflow detail.

3.1.2 QSplat

QSplat [38] is an efficient point model viewer. It takes advantage of a multireso-lutional bounding spheres hierarchy and is capable of rendering very large meshesin real time. QSplat most impressively demonstrates what surface rendering can dowith partialy hardware accelerated point sprites or even textured quads as primitives.Typically a pure polygonal model of very high detail consists of more triangles thanit would have root points in QSplat (Figure 3.3). The reason is the mediocre curveapproximation by many small triangles and the requirement of connectivity betweenthe vertices. Large plain areas of low-detail models on the other hand lead to a sig-nificant overhead of points to cover them.Using view frustum and backface culling as well as level-of-detail selection, QSplatis able to adopt to the system’s performance and keep a distinct frame rate. The

4CPU : central processing unit of a computer system

Page 24: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 3. PREVIOUS WORK IN VOLUME RENDERING 11

Figure 3.3: QSplat model "Lucy" (top half - front)Lucy was converted from 20 million triangles to now 10 million leaf points; 1.6

million points were rendered for this screenshot

bounding sphere hierarchy refines the drawn model to the maximum quality that canbe achieved. Likewise it will only refine as long as an image quality improvementis possible at the current distance to the model’s surface. In downtimes, when nointeraction like rotation, zoom or movement takes place, the maximum image qualityis computed and millions of surface elements are taken into account. Only a subsetof 100000 to 500000 points is usually regarded while the user is interacting with themodel.

3.1.3 Pointshop 3D

Pointshop 3D [43] is a surface editing toolkit based on surface splatting with theEWA algorithm (Section 3.1.1). It has been extended by various plug-ins to a surfelmanipulation suit. The system emphasises the need of high speed parametrisationand dynamic point resampling to facilitate artifact-less surface manipulation. To al-low real time interaction the sampling resolution is reduced while a surfel object ismoved. In their advanced work the team around Pointshop 3D published methods to

Page 25: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 3. PREVIOUS WORK IN VOLUME RENDERING 12

Figure 3.4: Pointshop 3D surfel model "gnome"

interact with their models not only by editing the material of surfels, but also by de-forming the surface geometrically (Figure 3.4). Pointshop 3D is meant to be a threedimensional image editor just like Adobe‘s Photoshop is for the two dimensionalcounterpart, but recent research deals also with sculpting of surfel objects. Whiletexturing, surface carving and displacement maps were already a part of the toolkit,methods for interactive point-based modelling and more complex manipulation us-ing implicit surfaces were examined lately [33]. The aim is to push the use of 3Dscanned surface data as a standard image format. Although more editing capabilitieshave been added by the mentioned plug-ins over time, allowing to create primitivesand perform CSG5 operations for example, so far Pointshop 3D is not usable to createcompletely new 3D content and was not designed as a 3D modelling solution.

3.2 Direct vs Indirect Rendering

When volumes are not rendered directly as it is introduced later in this chapter, theirsurface is computed by a sampling technique and either rendered as described inthe last section or by using another primitive, for example the triangle. While thecentre of a voxel is the reference point in direct volume rendering, indirect surfacesampling interpolates between the eight voxel-box vertices.

Page 26: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 3. PREVIOUS WORK IN VOLUME RENDERING 13

Figure 3.5: Marching Cubes Surface GenerationIn the Marching Cubes Algorithm the surface plane is determined by an

inside-outside test of the voxel’s vertices.

3.2.1 Surface Construction

Marching Cubes [17] is a surface construction algorithm, which regards the extrap-olated values at the vertices of each voxel cell: an inside-outside check computeswhose grid-vertices are part of the volume and whose are not (Figure 3.5). There are28 possible combinations for a surface plane within a voxel according to the mem-bership of the eight vertices to the volume. Regarding symmetry and complementsthe different surface set-ups in a cell are reduced to fifteen (Figure 3.6). Those fif-teen are ambiguous however, which leads to holes in the constructed iso-surfaces thathave to be capped. The surface plane is generated in between of the vertices insideand those outside of the volume. In order to allow correct surface construction, theoriginal mesh has to be well-defined. The detected edges of each two of the volumeslices are interpolated and triangulated. In a final step the triangle mesh is simplifiedby combining small triangles to bigger ones and the surface normal is computed forthe shading process. Clearly such a construction algorithm cannot be performed inreal time beyond a very limited grid size. Due to this vast amount of computationneeded, indirect volume rendering is in general considered insufficient for interactivemodelling solutions.

5Constructed Solid Geometry: final geometry is generated as the sum of its boolean primitives

Page 27: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 3. PREVIOUS WORK IN VOLUME RENDERING 14

Figure 3.6: Marching Cubes: the 15 resulting cell state combinations

3.2.2 Implicit Surfaces

Implicit surfaces are a special kind of volume representation and are only introducedshortly in this context. The basic idea is to represent the surface of a volume only bymathematical basis functions that define, whether a three dimensional point belongsto the object shell or not [42]. Mathematical primitives like spheres for example canbe represented accurately; the basis function F(P), which describes for every point Pwhether it’s a part of the unit sphere would be:

F(x,y,z) =√

x2 +y2 +z2−1

It is a complex problem though to describe arbitrary shapes using implicit surfaces.Commonly details are lost and real world objects are only approximated by such rep-resentations. In the further processing these functions can be manipulated by booleanoperations such as union, intersection and difference using CSG [?]. Implicit sur-faces can be visualised by ray-surface intersection tests using a ray tracing system,but also by first converting them into a polygonal representation with an algorithmlike marching cubes.

3.3 Direct Volume Rendering Techniques

For interactive volume sculpting it is recommendable to render the volume directly,without first converting it into a triangle mesh. Therefor the volume is traversed andsampled in well-defined steps (Figure 3.7). All direct visualisation techniques have incommon though to only become efficient, when adequate acceleration strategies are

Page 28: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 3. PREVIOUS WORK IN VOLUME RENDERING 15

Figure 3.7: Volume projection of direct rendering and surface splatting

applied. The surface of the volume has to be found without redundant traversing ofinvisible voxels. Whether a rendering solution is robust enough can only be evaluatedby rendering objects of arbitrary shape rather than geometric primitives. There areseveral approaches for direct volume visualisation from which the most importantones will be introduced:

3.3.1 Ray Casting

Figure 3.8: Classical Ray Tracingfrom the paper "Ray Casting" [11]

Ray tracing is known to be an accurate but slow projection and rendering tech-nique. Although ray tracing is still not generally hardware accelerated, it can be im-plemented on clusters or modern GPUs for parallel processing of the rays as shownby Timothy Purcell et al. [31]. Also there are ray tracing hardware prototypes like theso called "SaarCor" [39]. When using ray tracing for 3D rendering view rays are cast

Page 29: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 3. PREVIOUS WORK IN VOLUME RENDERING 16

through the image plane pixels into the scene (Figure 3.8. As soon as they hit an ob-ject, secondary rays like reflection rays are spawned from the hit point. Finally, lightrays originating from the light sources shade the hit surface point. If there is an ob-ject between a light and the fragment, it is shadowed. The sum of all consecutive raysdescending from one view ray blends into the image plane pixel the ray intersected.The possibility to trace rays through a regular grid with the "three-dimensional digi-tal analyser algorithm" [5] and acceleration techniques exploiting spacial coherencemake ray casting a useful method for direct voxel grid rendering. Volume ray castingis usually limited to surface sampling. The volume is traversed until the gatheredopacity is maximised. Secondary rays for reflections, refractions and shadows arenot traced through the scene.When a volume is rendered commonly sampling points in regular distances alongthe ray are scanned. At each point a gradient is computed and the proximate voxelsare interpolated. Most gradient computations are based on 2D edge detection filters.The gradients are used to compute the local shading according to a lighting modellike Phong or Blinn. Like normal ray tracing the image quality can be improved bycasting multiple rays through the area of a single pixel. Additional effects like sub-surface scattering and refraction effects can be simulated when very accurate surfacevisualisation becomes significant.

3.3.2 Texture Slicing

Exploiting textures is a very efficient because hardware-accelerated method to ren-der volumes directly. The most straight-forward approach is to use the 3D texturemapping capabilities of modern graphics hardware and workstations. The completevoxel information of a uniform, Cartesian voxel grid can be swapped into the videomemory. The access to this volume texture is performed using the interpolated tex-ture coordinates of its bounding box. Other implementations confine themselves to2D textures by cutting the volume into n textures of i*j voxels. The texture lookupsof 2D textures are definitely faster than those of its 3D counterpart. Also the 3D tex-turing support varies depending on the graphic board’s manufacturer and the API6.In both approaches texture slices are mapped on quadrilaterals which are usually ren-dered from back to front. This way semi-transparent voxels can be alpha-blended inhardware. Without compression, the size of a volume is strictly limited either by thememory of the GPU or by the bandwidth of the connecting bus. A grid of 5123 vox-els using a 32Bit RGBA 3D texture would require 512 Megabyte of video RAM. Sofar only very few consumer products dispose of that amount of memory. Even whenthe volume’s densities are post-processed in a fragment shader and only 16 bit val-

6API : application programming interface; OpenGL is an API for graphical output, DirectX is anAPI with additional libraries for multimedia (Microsoft Windows) applications

Page 30: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 3. PREVIOUS WORK IN VOLUME RENDERING 17

ues are transferred per voxel, this is still too much for frequent updates in real timeapplications due to bandwidth limitations. A 8x AGPort is limited to a theoreticalupload maximum of 2GB/s, its successor PCIe to a bandwidth of 4GB/s. Both failto meet their maximum performance and thus fast texture updates of that size are notpossible.The conventional 2D texturing approach is to decompose the volume into a set ofobject-aligned slices, meaning that the volume is cut into slices along the depth axis.Textures for all three possible drawing axes have to be generated and updated, occu-pying three times as much memory than one 3D texture. Also the resulting imagesoften contain visual artifacts caused by the lack of trilinear interpolation. Other thanwith 3D textures it is not possible to use view-aligned slices that intersect the volumeparallel to the image plane (Figure 3.9). Errors can occur when the volume is ro-tated, because the planes are not parallel to the viewport and thus the viewer can lookbetween two adjacent slices actually seeing previous or consecutive voxels insteadof a surface voxel. When 3D textures are used this can be avoided by computingviewport-aligned slices that intersect the bounding box of the 3D texture-volume.As soon as the viewing matrix changes, these viewport-aligned slices have to be re-computed, which makes them unattractive for real time applications. Additionallyview-aligned slicing complicates the use of acceleration techniques like empty spaceskipping. The image quality though can be easily improved with this approach byincreasing the number of sampling-slices that intersect the volume. Since the colourof a voxel is interpolated from its semi-transparent neighbourhood, the colour transi-tions become smoother. As in many fields of computer graphics the decision betweenaxis- and view-aligned slicing can be a real trade-off between quality, performanceand hardware capabilities.

Figure 3.9: View aligned and object aligned texture slicing

3.3.3 Shear-Warp Rendering

Shear-Warp rendering was introduced by Marc Levoy [16] and has been recognisedas one of the fastest software volume renderer to date. The Shear-Warp algorithm

Page 31: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 3. PREVIOUS WORK IN VOLUME RENDERING 18

is a hybrid between ray tracing, surface splatting and slicing (Section 3.1.1). In thepre-processing step voxel runs are encoded based on pre-classified opacities. Threeencoded volumes, one for each viewing axis, have to be generated. In the "shearing"step the slices of the volume are displaced such that the viewing rays are parallel tothe depth axis (Figure 3.10). In case of perspective projection the slices also have tobe scaled according to their distance to the image plane. As far-away objects appearsmaller, the slices at the far end of the volume have to be shrunk so that they areprojected on a smaller area of the screen. In the second step the contributing voxelsalong a ray collapse into a single pixel on the image plane using the ray tracingintegration. This step is referred to as "warping" the volume on the projection screen.The image quality of Shear-Warp approaches can be high, but interactive frame ratescan so far only be reached using specialised hardware.

Figure 3.10: The Shear-Warp Algorithm

3.4 Acceleration Strategies for Volume Graphics

All volume rendering approaches rely on appropriate acceleration strategies toachieve interactive frame rates. Texture slicing is an already hardware acceleratedmethod utilising the 3D texturing and interpolation abilities of modern graphics hard-ware. But even the fastest GPUs are currently not capable of rendering large, arbitraryvolumes in real time without further optimisations.When rendering volumes with semi-transparent voxels that have to be interpolated,classic texture slicing methods require to render the volume from back to front forvoxel blending. This prohibits early z-buffer termination, which is necessary for realtime rendering of millions of voxels. A possible solution is to render the volume fromfront to back and save, whether a screen pixel has reached an alpha value of 1.0 andis opaque. This can be done using a fragment shader that saves the current RGB andAlpha value of a pixel into a texture, which is reused in the next slicing step. Whenthe volume is rendered by ray tracing, it is even easier to terminate the ray, as soonas the pixel opacity has reached the maximum value or a specified threshold.Even more important is a multi-resolutional subdivision structure which allows empty

Page 32: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 3. PREVIOUS WORK IN VOLUME RENDERING 19

space skipping. By avoiding unnecessary texture accesses using texture slicing ormultiple voxel traversal through empty regions using ray tracing, much performancecan be saved. An optimal subdivision structure would be a binary space or kd- tree,which approximates the real shape of the volume’s surface as narrow as possible.Such a structure has to be recomputed after alterations took place though.For ray tracing there are several other acceleration strategies which constrain the im-age quality. Rays can be skipped in areas of low frequency or when a close up viewof the scene is rendered, which leads to a definite speed-up, but also to artifacts atobject edges. Finally, especially ray-tracing based approaches can be greatly acceler-ated by parallelisation. Next to GPU-implementations, the computation of view rayscan be distributed over a workstation cluster or multi-threaded PCs with multipleCPU cores. Also big volume data sets can be decomposed and processed on differentsystems before they are reintegrated and the final image is rendered.

Resume

In this chapter different approaches to volume rendering have been compared. Sur-face graphics represents a volume by its shell only. This leads to a surface point cloudthat occupies less memory than the volume and can be rendered in real time. The lackof inner-volume information complicates the modelling of such an object though andcan cause artifacts. Indirect volume rendering generates a surface representation ofa voxel grid before it is rendered in high quality. Because the surface generationprocess is computational expensive, this cannot be achieved when modelling a bigvolume at interactive frame rates. The surface has to be restored when the volumewas altered. A direct rendering approach on the other hand can be able to re-renderthe volume sufficiently fast when it is accelerated appropriately.Direct volume rendering is preferable for a volume modelling system, since it isable to render even big voxel grids in real time. The most important visualisationtechniques like ray tracing, texture slicing and the Shear-Warp method differ in theirvisual quality and rendering performance. While ray tracing is very accurate andflexible, it is also much slower than the hardware accelerated texture slicing. Alldirect rendering approaches have in common that they can only be efficient whendecent acceleration techniques like a spacial subdivision structure are implemented.Using modern GPUs the texture slicing approach outperforms all other approaches,but yields image artifacts due to the texture interpolation and alpha blending in hard-ware. Since speed is more important than image quality for a modelling system, thisstill seems to be the visualisation technique of choice for a sculpting environment.

Page 33: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Chapter 4

Previous Work In VolumeModelling

The central questions of volume modelling that have to be addressed are:

1. In which way is the volume modified?

2. What are applicable tools for user-volume interaction?

3. What is an appropriate input device?

4. How can the interaction itself and the computation of results be accelerated?

4.1 Volume Modelling Techniques

Contrary to the alteration of volumes, the most reasonable way to change the shapeof polygons is to alter the position of their control vertices, which is not immediatelypossible with volume or surfel data. When the volume is implicitly represented byits shell, it can be modified by changing the surface; especially on spline based facesboolean operations with primitives like a sphere can be computed easily. The basicshape can be defined by Bezier curves for example, which then can be deformed bymoving their control points. The results lack sharp features though and it’s not al-ways possible to form any arbitrary shape this way.For sharp edges either a reconstruction algorithm has to be used or the boolean oper-ations have to be computed directly on an explicit volume representation like a voxelgrid. As has been elaborated the lack of interconnectivity is the strength and weak-ness of voxel grids at the same time. Boolean operations however are very simpleto implement on regular grids and therefore a standard method for volume sculpt-ing. Even when the tool and the object have a differing granularity and voxels could

20

Page 34: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 4. PREVIOUS WORK IN VOLUME MODELLING 21

be missed, it is straight forward to adopt a higher sampling frequence. Still thereare various approaches to volume modelling, especially regarding the user-volumeinteraction and therefore question 2, that have to be discussed:

4.1.1 Surface Modelling

Figure 4.1: Point-based modelling and rendering using radial basis functionsThe figure shows the surface generation from 450 seed points (left) to a smoothC2

surface (right).

Many considerations have to be taken into account when a modelling interactionis performed directly on surfel objects. While changing material information is a verysimple operation, alterations of the position of surfels lead to recomputation of theobject’s surface. Also the performance of boolean operations has to be optimised toallow real time interaction. Since Bart Adams et al. published a technique to performboolean operations on surfel based objects using high speed inside-outside tests [4],a couple of researches were developed based upon their work.

Shingo Kinashi et al. [14] implemented a haptical modelling device with forcefeedback to interact with the geometry of a surfel cloud. The main focus was on im-proving the user input, because mouse and keyboard were regarded as inadequate forintuitive 3D volume modelling. Therefor a virtual reality system was implementedwhich supports the use of 6 DOF force feedback input devices. The haptic feedbackrenders the cutting resistance proportional to the amount of deleted surfels and the al-teration speed. For the modelling process an octree representation of the surfel data isprecomputed as an acceleration structure. The sculpting is performed by boolean op-erations between the tool and the object which are represented both as surfel clouds.An inside-outside check determines whether a surfel has to be removed or added,depending on its position.As mentioned before the achievement of Adam‘s work was a fast inside-outsidecheck for real time interaction with surfel objects. Reuter et al. [34] presented atechnique was presented to edit point based models generated by radial functions

Page 35: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 4. PREVIOUS WORK IN VOLUME MODELLING 22

Figure 4.2: Virtual Clay

(Figure 4.1). Due to their spline curve like nature surfaces from radial functionsare perfect to solve scattering problems and avoid aliasing and similar artifacts com-pletely.There are also several approaches to clay-like modelling on polygonal meshes, eitherby deforming the mesh [10] or using subdivision techniques. Other than with gridrepresentations of a volume, each point on the surface is linked with its neighbours.This way its position can be altered without breaking the surface and vertices can beadded by insertion into the mesh. A powerful, commercial software package usingthis concept is SensAble’s Freeform [40]. In Virtual Clay [20] a mass-preservingmodelling approach using haptic feedback and dynamic subdivision solids was pre-sented (Figure 4.2). Since this kind of solution does not rely on the use of a volumeor surfel representation, it will not be further discussed in this work.

4.1.2 Constructive Volume Geometry

Figure 4.3: Constructive Volume Geometry

Page 36: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 4. PREVIOUS WORK IN VOLUME MODELLING 23

Constructive Volume Geometry (CVG) is a generalisation of CSG1 [6]. WhileCSG is limited to the geometry of objects, CVG can also be utilised to manipu-late physical properties that are associated with the objects. CVG shares the sameoperators with CSG, like union, intersection and difference, but can apply them oninterior structures and material properties like the density of voxels. Therefore it’sextended by special blending functions for the merging of semi-transparent objects(Figure 4.3). Such objects are specified as a set of scalar fields that are generatedfrom volume data sets or mathematically definitions.

4.1.3 Volume Sculpting on Voxel Grids

Figure 4.4: "Sculpting : An Interactive Volumetric Modeling Technique"Hi-res models tree and teapot

Tinsley Galyean and John Hughes introduced a technique for direct volume mod-elling using indirect rendering [8]. They proposed to sculpture on a Cartesian voxelgrid of low resolution and triangulate the interpolated volume using the marchingcubes algorithm. The resulting triangle meshes of thousands of polygons can be ren-dered in real time using hardware acceleration. While their modelling technique isvery imprecise and lacks fine details due to the interpolation of volumes with lessthan 303 voxels, it is possible to sculpture directly on the grid data using simple ad-ditive and subtractive operations. (4.4) They suggested various useful sculpting toolslike cutting material, adding clay with the "toothpaste tube" or a "heat gun", whichmelts voxels away. Also a surface filtering tool called "sandpaper" was included. Thedirect sculpting technique by applying boolean operations and surface filters is opti-mal for the direct manipulation of a voxel grid. The fundamental metaphor was thatof clay modelling: supported by haptical input devices like a force feedback joystick,an intuitive way of volume sculpting was implemented. The lack of fine granularity

1Constructed Solid Geometry: final geometry is generated as the sum of its boolean primitives

Page 37: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 4. PREVIOUS WORK IN VOLUME MODELLING 24

and detail was merely a hardware restriction at that time, because their researchestook place in the early 90’s.In a follow-up paper [18] a team from the National Taiwan University improved theabove volume sculpting technique. Using the extended marching cube (EMC) [15]algorithm, sharp features could be preserved and the volume’s surface could be ren-dered as a triangle mesh with impressive 30 FPS on a NVidia TNT2 graphics proces-sor. As modelling primitives polygonal meshes were voxelised2 and boolean opera-

Figure 4.5: Comparison between ordinary marching cubes (left) and EMC

tions could be performed between the tool and the sculpture. The system was testedin a virtual reality scenario using a spherical display with stereoscopic rendering anda 6 DOF force feedback input device (Figure 4.6). Since the voxel grid resolutionhas been limited to 643 voxels, the surface of small objects could be generated in realtime. The main focus laid on image quality improvements that could be achievedby the EMC algorithm (Figure 4.5). They stated the sculpting of "3D models withimpressive feature preserving effects" would take a few minutes to half an hour withtheir system.

2Voxelisation: the process of converting data from one source into a 3D volume grid ([12])

Page 38: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 4. PREVIOUS WORK IN VOLUME MODELLING 25

Figure 4.6: The Spherical Display of the Virtual Sculptor System

4.2 User-Sculpture Interaction

The answer to the third question, regarding an appropriate input device, could be: thehuman hand. Many volume sculpting articles announce natural look-and-feel to bethe final goal. The aim is to simulate real-life sculpting like clay modelling, chisellingor even surgery as closely as possible. This constitutes the requirement of hapticalfeedback for the optimal user control. An operator enhanced with a tactile sense canreact faster and more naturally on tool-object penetration than it would be possibleby visual and acoustic feedback only (Figure 4.6).

4.2.1 Haptic Rendering and Deformations

Especially, for the simulation of organic tissues both sides of the interaction have tobe imitated as perfectly as possible. Therefore force feedback capable input deviceswith at least three degrees of freedom and a physically correct surface representationare recommended.Such volumes are often simulated by more complex approaches than regular grids

like chain reactions [9] or spring masses emulating physical links. This kind of rep-resentation can lead to complex equation systems that need to be solved at very high

Page 39: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 4. PREVIOUS WORK IN VOLUME MODELLING 26

Figure 4.7: The 5DT Data Glove 14 Ultra

computational cost for example using the finite elements method3.For the input system, devices like the SensAble Phantom(Figure 4.8) brand are actu-ally capable of gauging up to six degrees of freedom. A 6 DOF input device whichalso permits the use of haptical feedback can clearly improve the handling of 3Dobjects and is mentioned in various publications concerning volumes and volumesculpting. Next to such a tool-assisted gear there are wire tension devices that attachthreads to the fingers and react on finger bending. Some of the so called "cyber-gloves" can even react on contact, be it the encounter of two finger tips or touchingreal world dummies (Figure 4.7). Other devices make use of a spherical gripper;wires are stretched over a suspension and run through the centre of the sphere. Thetool’s position and orientation can be measured by the forces that act on the wires.At the same time an electrical engine can increase the tension to simulate gravity orcollisions.

4.2.2 Modelling Acceleration

This last question concerning the acceleration of volume modelling can only be an-swered within the limitations of a given system. It depends on the requirements ofthe haptical rendering. Factors like the desired accuracy, the existing of physical sim-ulations and the kind of modelling operation have to be regarded. For optimal userinteraction the update frequency of collision tests between rapidly moving tools andthe volume has to be very high. While smooth visual rendering is already achievedat 30 - 60 Hz, a typical frequency demanded for modelling intersection tests is 1000Hz. Computation time for tool - object intersections can be saved by reducing thegeometric sampling frequency. When only has to be decided whether an intersectiontook place or not, but not how many voxels overlapped, it can be sufficient to check

3finite elements, FEM : can be used to approximately solve partial differential equations

Page 40: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 4. PREVIOUS WORK IN VOLUME MODELLING 27

Figure 4.8: The SensAble Phantom, 6 DOF haptic input device

only a fraction of the volume for intersection. But in high quality modelling solutionsand medical applications the cross section often has to be computed exactly includingthe affected volume’s shape and resulting forces.As in many other cases using spacial coherence is a promising approach here; whenthe world space is divided into parts and the intersection tool can be allocated to apart which is not occupied by the volume, no intersection can take place. If onlyone volume and one tool exist at the same time, a simple bounding box collision testcan be efficient enough to avoid further intersection tests. In more complex scenariossubdivision structures like the octree or BSP can be used to exclude intersections be-tween different volumes and tools.Especially for ray tracing based sculpting systems the frame rate during modelling in-teraction can further be improved by updating only the necessary parts of the screen.While the volume is not moved, only those pixels can change, where sculpting oper-ations take place. The specific pixel areas can either be computed by a projection ofthe affected volume regions or, when ray tracing tools based on a spray can metaphorare used, are given from the tool’s position and rays.

Page 41: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 4. PREVIOUS WORK IN VOLUME MODELLING 28

Figure 4.9: Adaption of magnitude and direction of the drilling forceThe tool-volume interaction in a volume sculpting system [28].

Resume

The most important publications that dealt with volume modelling on voxel gridsutilised a surface generation technique to render the final object indirectly. Instead ofrendering a high resolution sculpture in real time, only modelling tools are applieddirectly on the voxel grid, which is afterwards converted and displayed as a trianglemodel. This approach could be obsolete though, because modern GPU’s seem tohave the performance to render much bigger volumes than the used 643 voxel gridsat interactive frame rates.Next to the adoption of haptical user input with six degrees of freedom and force feed-back, also a stereoscopic output device has been recommended for volume modelling.Several tools like boolean operators, the adding and subtracting of voxel chunks andsmoothing functions have been presented and could be a basis for new sculpting tech-niques. Boolean primitives are very useful to create simple shapes and objects, whilemore precise tools would have to be implemented to allow accurate and intuitivesurface modelling.

Page 42: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Chapter 5

Virtual Sculpture

Virtual Sculpture is the volume modelling toolkit that has been developed during thisresearch. It is capable of displaying a voxel grid of varying size in real time andenables the user to interact with the volume sculpture. A graphical user interfaceallows to control operators and adjust several options like different rendering modesand input devices intuitively. Also functions for saving and loading of voxel grids areavailable. A set of sculpting tools is provided that can be used to modify the shapeand colour of the objects’s appearance.

5.1 Technical Basis

Before the functionality of Virtual Sculpture is discussed in detail, an overview ofthe technical basis of its implementation will be given. Since a complete sculptingenvironment has emerged from this diploma thesis, various different technologieshave been used.

5.1.1 Program Structure

Virtual Sculpture is divided into four parts: the render core, the grid representation,the toolbox and the graphical user interface. All components of the system are man-aged and controlled by the VSInterface class, which also handles the user input (Fig-ure 5.1).The render core is divided into two sub cores: Next to a ray tracing system for sur-face sampling exists a texture slicing render core for hardware accelerated volumevisualisation. The main function of the ray tracing core is to form a link betweensurface manipulation tools and the volume grid. The second core is optimised forfast volume rendering and has no additional functionality. Both render cores will beexplained in detail in Section 5.3.

29

Page 43: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 30

Figure 5.1: The structure of Virtual Sculpture

The grid object maintains all voxel information. It also includes a rudimentary sub-division structure for acceleration purposes. Its importance for the sculpting systemwill be elaborated in Section 5.3, while other functions of the grid object are ad-dressed in Section 5.2.The toolbox contains a list of interaction tools. The different tool types and theirfunctionality are described in Section 5.4.The GUI (Section 5.5.1) is based on Qt1 and consists of separate windows for op-tions, tool selection and visual output (Figure 5.17).As shown in Figure 5.1, the interaction tools have access to the volume object, ei-ther directly or indirectly over the ray tracing system. Thus the tools themselves

1Qt is an application framework with various pre-defined GUI elements [32]

Page 44: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 31

can implement voxel grid operators and pass the resulting voxel changes to the classrepresenting the volume.

5.1.2 Implementation

The system is implemented in the C++ programming language and compiled underWindows XP using the Microsoft Visual Studio .NET 2003 development environ-ment. The OpenGL API provides hardware accelerated drawing of Virtual Sculpturescenes including the 3D tools and the volume, which also requires GLSL2 for GPUshader support. Parts of the voxel pipeline (Figure 3.1), namely the surface samplingprocess, have been implemented as a fragment shader program. This program runsdirectly on programmable graphic cards rather than on the CPUs and makes use oftheir high parallelism. A modern GPU with GLSL support and shader version 2.0 isnecessary to run the hardware accelerated rendering mode. Further information aboutGPU programming and shaders for OpenGL can be found in "The OpenGL ShadingLanguage" [36].As mentioned before, the Qt API has been used in version 3.3 to implement the GUIof Virtual Sculpture. Also Microsoft’s DirectX API is needed for the support of var-ious input devices.

5.1.3 VR/AR Support

Virtual Sculpture was not only designed for consumer hardware, but also for a vir-tual reality (VR) and an augmented reality (AR) scenario. For VR/AR scenarios avideo background texture has been implemented, which captures a webcam usingMicrosoft’s DirectShow3. Also quad buffered 3D stereo glasses are supported byrendering separate images for the left and the right eye in OpenGL’s stereo buffers.It has successfully been tested with a NVidia GeForce Quaddro FX 3400 GPU andSony Glasstron stereo glasses. Gamepads with rumble feedback are supported asinput devices over DirectInput4. Finally head tracking was implemented for the aug-mented reality scenario by integrating an interface to the Morgan framework5. Usingthe Morgan framework various input devices could additionally be connected to Vir-tual Sculpture. Head tracking enables the user to handle the volume more intuitively,since it allows a natural 3D navigation just by looking around.

2GLSL : OpenGL shader language, high level language for shader programs that run on a program-mable graphics processor (GPU)

3DirectShow is part of the DirectX API for Windows Applications4DirectInput is part of the DirectX API for Windows Applications5The Morgan abstraction framework for VR/AR systems integrates support for a multitude of input

and output devices and offers an efficient, platform independent rendering system

Page 45: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 32

5.2 The Grid Object Class

Within Virtual Sculpture a voxel grid is encapsulated in the grid object class, whichstores all voxel data. It provides an abstraction layer for voxel opacity and materialaccess and manages all relevant volume information. Also it saves voxel changes forthe undo function of Virtual Sculpture and serves as an interface between the volumeand other parts of the application.

5.2.1 The Virtual Coordinate System

The voxel grid exists in a separate coordinate system. Three dimensional objects likethe grid and some tools are not defined within a global coordinate system, but ratherhave a local mathematically representation as well as a global visualisation in theOpenGL object space (Figure 5.2). The voxel grid itself always begins at the originof its local coordinate system and grows with its amount of voxels along the threeaxes in positive direction. Its dimension can be determined by the amount of voxelsand their size only. It is never rotated or translated in the local coordinate system,only its OpenGL representation is. The visualisation of the volume is translated sothat the centre of the voxel grid is at the origin. It is rotated around its centre and thentranslated to the current position in OpenGL world coordinates.Each grid object includes its own ray tracing camera. This camera is computed byinverting OpenGL’s modelview matrix and initialising the camera accordingly. Thedecision not to move the OpenGL camera but to rotate the volume instead was madedue to integration considerations. This way it is easier to integrate Virtual Sculptureinto an existing rendering environment. It also leaves open the possibility to imple-ment the support for multiple voxel grids at once, if that is required.

5.2.2 Memory Costs And Grid Sizes

As referred to in Section 3.3.2 using 3D textures demands a lot of (video) memory.This seems to be prohibited in a modelling system, where the volume informationchanges with every second of user interaction, requiring to reload the texture fre-quently. It should be possible for example to erase the complete volume or at leasta big part of the voxel grid at once. Multi resolutional data representations limit thememory costs by allocating only the memory of opaque voxel areas. Empty spaceneither has to be represented on the heap or on the framebuffer, nor does it have to betraversed or projected. Multi-resolutional subdivision on the other hand is expensiveto compute and changes completely, when big-scaled sculpting is applied.But Virtual Sculpture was especially designed for volume modelling and does notsupport densities or half-transparencies. This fact is exploited to reduce the memory

Page 46: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 33

Figure 5.2: The coordinate systems of Virtual Sculpture.

cost of the volume texture. By restraining the GPU on the surface sampling processand ignoring material information, it is possible to consume only 1 bit per voxel invideo memory. Whether a voxel is fully opaque or fully transparent is enough data tosample the volume’s surface and render the voxel indices in an output texture. Trans-ferring only 1 bit per voxel to the GPU leads to a 3D grid texture consuming only16MB Ram for the previous example of 5123 voxels. This means the texture is smallenough to ignore the bandwidth limitations of the AGP and the PCIe bus.The maximum size of a single volume grid in Virtual Sculpture is only limited by themaximum size of a 3D texture, which commonly is 5123 pixels, multiplied with the32 bit of a RGBA colour value. The factor of 32 is multiplied with the X-Axis andleads to a theoretical maximum volume size of 16384*512*512 voxels right now.This type of 1 bit storage comes with the requirement to extract the voxels withina fragment shader as it is described in Section 5.3. The voxels cannot be mappedon a polygon directly like it is done with a 32 bit voxel in a RGBA texture. Sincea shader is already in use, it would make little difference to use bricking6 to alloweven bigger grid sizes. The volume could be sub-divided into eight equal parts thatcould be accessed without major modifications. In the absence of half-transparenciesthere even would be no need to interpolate the brick-borders. Eight textures of 5123

voxels, allowing an overall resolution of 10243 voxels, would occupy 128MB videomemory. Modern GPUs dispose of at least 256MB and using bricking would allowto update only the modified parts of a volume. Therefore this could be an efficient

6bricking: volume space is divided into overlapping sub-volumes which are rendered separately andinterpolated at their borders

Page 47: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 34

possibility to render huge volumes in real time in the future.Since 5123 was the maximum resolution that could be rendered at interactive framerates yet, this feature was not implemented to date though.

5.2.3 Data Representation

A grid object contains two separate textures. The first one holds the existence bits ofthe voxels, which define whether they are opaque or transparent, and is used as a 3Dtexture for surface sampling. The second texture saves additional colour informationand has a variable size of 0 to 24 bit per voxel. When a new grid is created, the userdecides how much memory should be spend for material data. For Virtual Sculpturethere is no difference between the possible resolutions, because an abstraction layeralways interprets them as 24 bit RGB colours. They are compressed and unpackedaccording to the given byte amount. The compression algorithm favours green beforeblue and blue before red according to the sensibility of the human eye [?]. When only8 bit are used, 4 bit hold the green channel and 2 bit are saved each for blue and red.In the 16 bit mode, 7 bit represent green, 5 bit blue and 4 bit the red channel.Virtual Sculpture has no proprietary file format so far and uses a third-party format,which saves only density information of voxel grids that has to be reinterpreted duringthe loading process. Stefan Röttger [37] published withV3 a volume viewer forsemi-transparent data sets from CT or MRI scans. It implements "pvm" as a volumedata format, which is also utilised in this work without any alterations.V3 displaysvolumes in real time by exploiting the 3D texturing capabilities of modern GPUs andusing a pre-integration technique.The pvm data format is easy to use, supports density resolutions from 8 bit to 24bit and comes with converters to and from "raw" and "dti" files. Virtual Sculptureinterprets the density values of a "pvm" file as colour values or optional loads a fileas native VS - RGB colour values packed in 8, 16 or 24 bit.

5.3 The Rendering System

As has been pointed out in Section 3.3, rendering large volumes brings about the ne-cessity of robust acceleration techniques. In this context the requirement of interpo-lating half-transparencies is a major obstacle. Thus Virtual Sculpture works on fullyopaque voxels only and considers everything else as empty space. This decision hasbeen made to allow a render core design, which concentrates on the real time mod-elling directive and allows interactive frame rates on consumer hardware. Also thebiggest problem of voxel representations, their extreme memory consumption, wasreduced to negligibility this way, since no material information has to be regarded forthe surface sampling process. Neither do half-transparencies have to be blended, nor

Page 48: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 35

are the colour information significant during this computation. The ability to blendtissues of different densities is irrelevant for the targeted modelling technique, whileinteractive frame rates are crucial. The feature is dispensable as there are alreadyvarious viewers for medical data sets available that are very capable of visualisingbones, skin and flesh or even gaseous substances.Virtual Sculpture uses two different rendering approaches simultaneously to displayand modify a volume in real time: texture slicing and ray tracing. Texture slicingis known to be the fastest volume rendering technique, because the computationalpower of modern GPUs can be exploited without any constraints. The texture slicingkernel of Virtual Sculpture makes use of a 3D grid texture. But instead of comput-ing view-aligned slices, it functions with object-aligned planes. Thus 3D texturing isonly used to avoid frequent swapping, to simplify the texture access and to reduce theoverall memory consumption. Object-aligned slicing was given the precedence sinceimage quality is less important for a modelling environment. Thereby the system canbe fully optimised for fast volume rendering using acceleration strategies like emptyspace skipping. Minor graphical glitches like the possibility to look between twoadjacent slices from different viewing angles were easily removed by utilising gradi-ent interpolation. Even if a voxel inside the volume is drawn, the rendering systemrecognises the error and computes a surface gradient for the affected voxel.

5.3.1 The Texture Slicing Render Core

The texture slicing render core uses OpenGL quadrilaterals to send texture coordi-nates to the GPU. These coordinates are used within a fragment shader to sample thecorresponding surface voxels. All voxels are saved in a 3D texture, which is accessedfrom front to back exploiting OpenGL’s depth culling. This is an efficient, hardwareaccelerated approach to volume surface sampling that allows interactive frame rates.Conventionally the bandwidth of the graphics bus has to be broad enough for fre-quent updates to allow modelling in real time. Since Virtual Sculpture uses only 1 bitper voxel on the GPU, the bandwidth is no bottleneck and has little influence on theoverall performance.The program sequence of the texture slicing render core goes as follows: First thevolume texture is updated, if it has been changed since the last frame. Also shadervariables like the camera position or colour values can be renewed. Most variablesare only necessary for a GPU-only mode though. After all values are up-to-date, thenearest side of the volume is to be computed. Depending on the position of the cam-era and the grid rotation that side of the voxel grid has to be found, which the user isfacing most (Figure 5.3). When head tracking is active in an AR scenario, also thehead position and orientation have to be regarded.The nearest side plane determines the depth axis as the axis intersecting it orthog-

Page 49: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 36

onally. Along this axis the texture slices are generated and rendered from front toback.The mentioned subdivision structure is used to find areas of homogenous empty orfull space. The grid is divided into several uniform subgrids of a typical size of 83

voxels. Each subgrid stores the number of opaque voxels it contains. Accordinglyempty subgrids within the acceleration structure can be disregarded while renderingthe volume (Section 5.3.2).

Figure 5.3: Texture Slicing: The Nearest Side / The Uniform Sub Division

Finally the computed areas of uniform space are rendered as OpenGL quads.Accordingly to its position in the voxel grid, the texture coordinates of each vertex areset (Section A.3). These coordinates are used to access the corresponding voxels inthe fragment shader, but also to compute the index of that voxel, which is covered bythe current fragment. Since OpenGL automatically interpolates texture coordinatesalong a polygon edge, only the vertex-coordinates have to be computed in software(Figure 5.4).

Figure 5.4: Texture Slicing Areas

Page 50: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 37

The handicap of the used technique is that the voxel information has to be ex-tracted from the 3D texture using a fragment shader program, because every singlebit of a RGBA value represents one voxel. This is done by first retrieving the 32bit value from the texture, then determining the correct 8 bit component, R, G, B orA, containing the desired bit representing the voxel and finally calculating the bit’sposition within that byte. The byte value is then shifted by this position to move thebit to the lower end. A modulo operator is used to determine whether the resultingvalue is an odd or even number and thus whether it is opaque or transparent. Becausethe shift function is not part of the GLSL, it has to be replaced by a division: the shiftof a single bit to position zero is equivalent to a division by 2position.Another problem is the shader program’s precision: the GLSL implementation of theused NVidia GeForce 6800 GT apparently becomes imprecise when additions andsubtractions are performed on integer values beyond the range of 24 bit values like itis done when voxel indices of a big grid are computed. An index is computed by thefollowing formula:

index i = x+y·dX+z·dX ·dYMy solution is to factor out larger numbers of the voxel index computation. The

shader’s source code can be found in the appendix (Listing A.1).If the sampled surface voxel is opaque, its index is rendered as a RGBA value intothe framebuffer. The result is an index map, in which each colour stands for a surfacevoxel that afterwards has to be shaded and lighted (Figure 5.5).

Figure 5.5: A Voxel-Index Map

Page 51: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 38

5.3.2 Acceleration Strategies for the Texture Slicing Core

A very naive approach to empty space skipping for texture-slicing would be to com-pute the first and last slice that contain opaque voxels for the current viewing directionand render only the slices between them. A little bit rendering time could be saved,but only when there are any object slices that are completely empty. A much betteridea is to subdivide the volume into 3D equilateral subgrids of a distinct size anddecide whether there are filled voxels within a subgrid or not. This way a real emptyspace skipping with the sub-division resolution can take place. Only those subgridsare rendered that posess more opaque voxels than a specified threshold.This approach still has its flaws: very many polygons have to be drawn; the number ofsub-areas dividing the grid in 2D - times the size of the grid in the current depth axis,to be specific. Certainly this solution can be further improved by multi-resolutionalrendering. In a more static environment than a modelling suit it would be best to con-struct a subdivision structure around the volume fitting the real outline of its opaquevoxels as tightly as possible. Such a structure, for example a BSP7 tree, would havelarge blocks of uniform regions that could be addressed as grouped regions to savepolygons and rendering time.In Virtual Sculpture this task is performed on basis of the mentioned uniform sub-grids: because a single sculpting operation can change the complete subdivision, areal time approach was implemented within the texture-slicing module, that can re-built the subdivision without interrupting the rendering process. The introduced uni-form acceleration structure saves whether a subgrid of the volume contains voxels ornot. This uniform cells are binary subdivided into regions of full or empty subgrids.Adjacent blocks are combined within a recursive mapping algorithm to areas andsaved in a vector ofk quadrilaterals, wherek is a well-defined number of slices alongthe depth axis, that have been grouped (Figure 5.4). Such coherent polygon packsare uniformly filled with voxels, since empty areas are discarded. The polygons arecompiled into a OpenGL display list and only recomputed, when the geometry of thevolume changes. The texture coordinates for the vertexA from the arean in slicesare computed as shown in Figure 5.6.Next to depth culling, which prevents that fragments are computed that are alreadycovered by a voxel with a smaller depth value, also hardware accelerated z-cullingis utilised. By rendering rather small voxel areas using adjacent polygons, OpenGLcan cull regions that are overlapped by other objects or positioned outside the viewfrustum.

7binary space partitioning: an efficient spacial subdivision technique; the object cell is divided intotwo sub-cells, which are divided into sub-cells and so on as long as they are non-empty

Page 52: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 39

Figure 5.6: Computation of Texture Coordinates for Subdivision Areas

5.3.3 The Ray Tracing Render Core

The main function of the ray tracing render core is to sample the volume’s surface.Spray tools use ray tracing to find their application points. The first non-empty voxelthat is hit by a ray will either be directly affected by an alteration like colouring ordeletion, or it will be the starting point of a larger function.Nevertheless the ray tracing core is also capable to render the complete volume.Therefore it is an appropriate CPU-only visualisation technique when no GPU shader

Figure 5.7: The Ray Generation

support is available. Also it can be a basis of comparison for the hardware acceler-ated benchmarks. The ray tracing camera generates a perspective view ray for eachscreen pixel. This computation is presented in Figure 5.7. The ray is traced throughthe scene and intersected with the volume object. Lightning and shading is computedfor each found intersection point according to its normal and the position of lightsources.The ray tracer uses the same uniform subdivision, which the empty space skipping

Page 53: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 40

algorithm of the GPU core is attached to. First a bounding box test is performed withthe volume and the entry point, if available, is computed. The 3DDA [5] algorithm isused to compute a 3D line through the voxel space as long as the traversed subgridsare empty. It compares the distances of the current subgrid borders in each direction

Figure 5.8: 3DDA vs. Quickstep Traversal

with the direction of the ray and performs the next traversal step over the first-crossedborder. When a non-empty subgrid is entered, a 3D voxel run algorithm follows anapproximated line between the centre of the first and last voxel that is intersectedwithin the region. The axis on which the most steps will be performed becomes thebasisdirection. The ratio between thebasisand the other two axes is computed andthe algorithm I named "Quickstep" is initialised. A for-loop performs a traversal stepthrough the gridbasis-times (Figure 5.8). In each step the basis axis is progressedonce. The other axes’ iterators are increased when their ratio threshold is reached.Be it that x is the basis axis, y is only half as often traversed and z only every fourthtime averaged. Then x will be traversed in every step of the for loop and a check isperformed, whether the hit voxel is opaque or empty. Y will be increased as well inevery second pass, z in every fourth and the voxel is tested after each increase.Since the 3D line is only approximated and the order in which the axes are traversedis not sorted in any kind of way, fully opaque voxels can be missed. Because a singlevoxel is usually smaller than a pixel in Virtual Sculpture, the error is minimal though.

Page 54: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 41

The pseudo-code of the Quickstep algorithm can be written as follows:

*****************************************************************

Raytracer::quickstep(Ray ray, Volume vol){...

hitPoint, exitPoint = vol.boundingBox.intersect(ray);

stepsThroughGridXYZ = exitPoint - hitPoint;

directionX, directionY, directionZ = getDirection(stepsThroughGridXYZ);

basis = findAbsoluteMaximum(stepsThroughGridXYZ);axisThresholdB = axisStepsB / basis;axisThresholdC = axisStepsC / basis;

for(basis steps){

traverse(basisAxis);vol.checkVoxel();if(voxelFound)

return voxel;

if(axisThresholdB == 0){

axisThresholdB = axisStepsB / basis;traverse(axisB);vol.checkVoxel();if(voxelFound)return voxel;

}

if(axisThresholdC == 0){

axisThresholdC = axisStepsB / basis;traverse(axisC);if(voxelFound)return voxel;

}

axisThresholdB --;axisThresholdC --;

}

...}

*****************************************************************

Page 55: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 42

5.3.4 The Render- and Shading- Modes

Subsequent to the surface sampling lighting and shading has to be computed. Thetwo render cores of Virtual Sculpture can be combined with multiple shading modes.There are two software shading implementations that can be used by both rendercores. The main core, which is based on hardware accelerated texture slicing, alsoimplements a third shading method for computing the lighting directly on the GPU.The three shading-modes (Figure 5.9), from which five different render-modesemerge, can be summarised as follows:

1. The GPU-only mode, which computes an output image (of single-colouredvoxels) completely in the GLSL shader. Thus this mode cannot be utilised bythe ray tracing core.

2. The software shader mode, which samples the volume’s surface in the GLSLshader or the ray tracer and computes colouring, lighting and interpolationafterwards in software (Figure 5.10). Since the shading operates on the vertex-index map created during the surface sampling, both render cores employ thismode. The indices are passed as a texture and replaced by their shaded voxelcolour values.

3. The OpenGL point mode, which also uses the index map and creates a 3DOpenGL point for every voxel index in the given texture. The points are ren-dered using OpenGL points and vertex normals and are thus shaded by theOpenGL standard pipeline. This means the OpenGL point mode generates asurfel cloud out of the sampled volume surface that represents the voxel gridfor the current perspective.

Figure 5.9: The Different Render Modes of Virtual Sculpture

The OpenGL point mode generates a point cloud out of the volume’s surface.Since only those surfels that can be seen from the current perspective are generated,

Page 56: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 43

this is no complete surface representation. Technically, it would be possible to gener-ate a complete surfel object of the volume by sampling multiple angles and distancesand combining these results. This surfel cloud could be inserted into any 3D environ-ment for real time rendering.Regardless whether the surface was sampled by the GPU or in the CPU-only raytracing mode, only the software shader mode, which computes shading in softwareon a voxel texture, has additionally integrated normal and colour interpolation filters(Figure 5.11). Such filters can improve the image quality especially when volumes of2563 or less voxels are computed, but at the expense of sharpness and accuracy. Theimage quality of ray tracing sampled modes differs only minimal from those of GPUaccelerated modes.

Figure 5.10: GPU / CPU Software Shader Mode Image Quality Example

Colouring is not computed in a GPU shader because every single voxel contains8-24 bit colour information, which would result in a 128-384 MB colour texture.Even more important than the required video memory, which has recently becomeavailable, is the limited AGP bandwidth that would be highly loaded by colour tex-ture updates. Those problems could be solved using compression algorithms, whichalso could reduce the requirements of system memory. But the most definite rea-son against a fully-fledged GPU-only shader, which computes gradients and shadingand retrieves the material for each voxel, is the performance of Virtual Sculpture’sGPU-only mode. The implemented shader computes an approximated normal by in-terpolating neighbouring voxels and shades all voxel with the same colour using onlythe first light source. Although it is completely hardware accelerated, it performs less

Page 57: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 44

Figure 5.11: Software Shader Mode with Activated Normal and Colour Filtering

well than the GPU/CPU software shader mode using a common CPU. Apparentlythe expensive 3D texture look-ups and high instruction counts slow down the render-ing pipeline significantly and prohibit the use of more complex hardware shaders. Abenchmark and comparison of all render modes can be found in the following section.

5.3.5 Performance Comparison

In Figure 5.12 a benchmark of all 5 render modes of Virtual Sculpture is shown. Twodifferent voxel grids, a full cube and the already presented engine model, are com-pared. The time measures were taken at a resolution of 640*480 pixels using an IntelPentium 4 CPU with 3 GHz, 1 GB of main memory and a NVidia GeForce 6800GPU with 256 MB Video Ram. As you can clearly see the hardware accelerated ren-der modes outperform ray tracing by a factor of 2 to 15. When a full voxel cube isdrawn, all GPU modes perform equally well at around 17 FPS, which is about twiceas fast as the ray tracing core.When an arbitrary volume shape is computed on the other hand, the picture changesdrastically: while the ray tracing core performs distinctly worse, because large partsof the volume have to be traversed before a pixel can be terminated, the GPU accel-erated modes behave completely different. The GPU/CPU mixed approach reachesmore than 30 FPS, regardless whether the fragments are shaded by the CPU or usingOpenGL point sprites, while the GPU only mode stagnates.All GPU modes benefit from the overall smaller fragment amount that has to be com-puted for the engine model. But while in the software shader mode also fewer voxels

Page 58: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 45

have to be shaded, the GPU only mode is slowed down excessively by unnecessarytexture look-ups. Even with empty space skipping there are always some voxels

Figure 5.12: Benchmark of all 5 Render Modes

in front of the volume surface, which have to be checked for existence. Becausethe GPU only shader is much more complex and therefore slower than the surfacesampling shader of the mixed modes, it takes accordingly more time rendering. Ad-ditionally the gradient computation for an opaque voxel, which uses at least six 3Dtexture look-ups, is a very expensive operation. This could only be overcome by up-loading pre-computed normal maps, which again would engage a lot video memoryand exceed the AGP bandwidth when large parts of the volume are changed at once.Furthermore it can be observed that the OpenGL point modes perform somewhat bet-ter than the software shaded versions in the 2563 voxel grid benchmark. Still thereare two drawbacks, which make them less attractive: the first one is artifacts that canoccur when the volume is far away and thus a single voxel has to become smallerthan a screen pixel. Similar artifacts like gaps and interferences can also be seenwhen a close-up is taken and single voxels become enlarged on the screen. Finallyit is more difficult to compute interpolation filters and find acceleration strategies forthe OpenGL point mode than it is for the software shaded versions.For the benchmarks of 5123 voxels volumes, which is eight times as big as 2563, acomplex model volume was created (Figure 5.13). The benchmarks shows a similarbehaviour as the 2563 voxel counterpart: the GPU modes outperform ray tracing evenmore drastically, since huge amounts of voxels have to be traversed. The used model

Page 59: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 46

Figure 5.13: A Complex Volume with 5123 VoxelsThis structure was used for the 5123 voxel benchmark.

can be regarded as a worst case, since the surface is larger and rather detailed andrequires a good deal of traversing. Still the GPU mixed mode is the fastest renderingsolution with about 10 frames per second (Figure 5.14).

Figure 5.14: Benchmark of all 5 Render Modes Rendering a 5123 Voxel Grid

Page 60: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 47

5.4 The Modelling Tools of Virtual Sculpture

Only a few publications could be used as a basis for the modelling capabilities ofVirtual Sculpture, since the modelling of voxel grids is a quite rarely addressedtopic. Tinsley Galyean et al. proposed a set of interesting tools including cuttingand smoothing together with an ergonomic graphical user interface (Section 4.1.3).Virtual Sculpture adopts some of their ideas and tries to amend them by additionalfeatures.There exist three groups of modelling tools in Virtual Sculpture: three-dimensionalprimitives for boolean operations on the volume, various ray tracing based spray toolsfor surface sculpting and finally selection tools like a working area assignment or acopy and paste operation. Other functionalities include undo, save, load and the cre-ation of new grids from the scratch.While many more tools, including more primitive shapes and filtering operators, areimaginable and could be added over time, the current toolbox has been chosen bypriority. The first necessity was to sculpture basic shapes. Boolean primitives thatcan be combined to more complex objects appeared appropriate. Their inability tomanipulate only the surface of an object in an intuitive way had to be compensatedby spray tools that work like a paint brush. Fine details on the surface can be gener-ated most easily by drawing on it. Finally a solution had to be found to prevent theuser from accidently deleting or altering parts of the volume which led to the thirdcategory, the control and selection tools.

5.4.1 Construction Tools

Figure 5.15: Boolean Operations Between the Volume and 3D Primitives

The construction tools are basic 3D shapes, which are drawn in OpenGL and havea mathematical representation that allows boolean operations with the volume. Theyare very useful for creating large, regular objects and forming the basic outlines ofan object. Since the mathematical representation of these tools exists in a local co-ordinate system only and is not rotated or translated as their OpenGL visualisation,first the overlapping voxels have to be found when a tool is activated. An intersection

Page 61: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 48

volume has to be computed and the overlapping voxels have to be transferred into thetool’s coordinate system. Subsequently an inside-outside test compares these coordi-nates with the scaled mathematical shape and decides whether a voxel is affected bythe tool’s operation or not (Figure 5.15).The pseudo-code of such a computation can be written as follows:

*****************************************************************

Tool::use(...){...

inverseProjMatrix = calculateInverseProjectionMatrix( volume.projMatrix,volume.headTracking, my_projMatrix );

interVol = computeIntersectingVolumeBoundingBox( volume.getBoundingBox() );

interVol = getVoxelCoordinates(interVol);alignedBox = computeAxisAlignedBoundingBox( interVol );

for( allVoxelsInAxisAlignedBoundingBox X,Y,Z ){

voxel = volume.getVoxel( X,Y,Z );voxel = transferVoxelCoordinatesToToolSpace( voxel, inverseProjMatrix );

if( voxelInsideToolShape(voxel) ){

volume.change( X,Y,Z );}

}

...

}

*****************************************************************

All construction tools are derived from the same class and therefore share func-tionality like adding or subtracting voxels and changing the colour of affected voxels.To simplify the navigation in 3D space the tool movement is aligned to the coordinatesystem of the volume and rotated together with the volume. Also they can accommo-date their orientation to the rotation of the grid. The important topic of controllingsuch primitives in a 3D modelling environment is further discussed in Section 5.5.2.The basic shapes that have been implemented in Virtual Sculpture are the sphere, thecuboid and the pyramid. All of these can be scaled independently in all three dimen-sions, which allows their application in manifold ways: the sphere also functions asan ellipsoid and the pyramid can be used as a spike. An ellipsoid is defined by threeradiansa,b,c. The surface description of the ellipsoid (in cartesian coordinates) re-sults in a simple test whether a pointpx, py, pz is inside the ellipsoid:

x2

a2 + y2

b2 + z2

c2 = 1⇒ p2x

a2 + p2y

b2 + p2z

c2 ≤ 1

Page 62: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 49

Although such tools have powerful modelling capabilities by cutting or adding voxelchunks, they lack the ability to manipulate seperately the volume’s surface in anintuitive way. This is compensated by a second category of sculpting instruments,the spray tools.

5.4.2 Spray Tools

All spray tools of Virtual Sculpture have in common that they are based on ray trac-ing. A lot of effort has been spent to create a ray tracing based surface sampling thathas congruent results with the GPU sampled volume. Since the OpenGL camera isnot moved, but rather the volume is translated and rotated around its own axis, theray tracing camera has to be computed by inverting the modelview matrix. The pos-sibility to ray-trace the voxel grid allows the implementation of various intuitive anduseful tools:

1. PaintbrushThe Paintbrush is a very simple drawing tool that changes the colour of hitvoxels. Rays are emitted from the mouse position and traversed through thevolume until they hit an opaque voxel. The colour of the voxel is set to thechosen sculpting material.

2. DevourerThe Devourer called tool only emphasises ray tracing to find the voxel of itsimpact. In a radial or quadratic area around this position all voxels are elimi-nated.

3. Erosion/DilationAn area filter for erosion and dilation has been implemented. It affects anarea around the hit voxel by applying a filter matrix on the neighbourhood. Athreshold defines the number of voxels that have to be adjacent to the hit voxelto trigger the filtering operation. Thus the erosion filter does not alter a plane,but smoothes sharp features and deletes single voxels. The threshold of thefilter can be set by the user.

4. Voxel GrowthThe Voxel Growth tool is able to smooth an object’s surface by inserting voxelsinto sharp corners. Since new voxels are generated adjacent to existing ones,a closed plane can be generated.

All spray tools share general parameters, but also have unique options each. Theuser is able to change the basic shape of the pixel area, from which rays are castinto the scene. A circle or a square of adjustable radius can be chosen for each tool.

Page 63: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 50

Additional options like the covering power of the Paintbrush or the reaction thresholdof the Erosion filter are available in the specific tool’s option window.

5.4.3 Control Tools

The most important control tool of Virtual Sculpture is the undo-function. It savesmillions of voxel changes as well as the beginning and the end of atomic operations.This way large-scale operations started by a single mouse click can be reversed inone step.The Selection tool is another important control mechanism. It uses a 3D markerthat can be moved within the voxel grid coordinates to define multiple voxel areasand limit the functionality of other tools on these selected parts of the volume (Fig-ure 5.16). The possibility to prevent the accidental alteration of parts of the volumeis crucial especially for spray tools. Without it, the use of such tools would requireextraordinary caution and patience. A stack allows to select multiple regions at onceand to delete them one by one. The most basic function of the Selection is to markthe complete volume or parts of it and delete them or fill them up with voxels.Finally, based on the Selection tool, a copy and paste function is available in VirtualSculpture. A selected area is copied to the current marker’s position including allcolour information.

Figure 5.16: The Selection Tool

Page 64: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 51

5.5 The User Controls

Virtual Sculpture can be controlled either by using a combination of a common mouseand keyboard or using a modern gamepad. As mentioned in Section 5.1.3 a wirelessforce-feedback gamepad is supported for a AR scenario, where the users is not sitting,but rather walking around freely using head tracking and a 3D stereo HMD. Thegamepad can either control the mouse movement or directly rotate and translate thevolume and the 3D tools. Therefor the control mode has to be switched between"ONLY MOUSE", "USE TOOL" and "MOVE ACTIVE GRID" by pressing "leftshift" on the keyboard or button 2 on the gamepad. In mouse-mode the gamepadbutton 1 is interpreted as a double click, button 4 as a single click and the left analoguestick controls the position of the mouse.In the other modes, the left stick controls the translation, the right one the rotationof the moving axes. The depth axis is controlled by the shoulder buttons 5 and 7(translation) as well as 6 and 8 (rotation). The first button of the gamepad is used toactivate the tool.The mouse on the other hand can only control either rotation or translation at a time.The object is translated while the first mouse button is pressed down; it is rotatedwhile the second mouse button is down. To switch from X/Y to X/Z movement, the"Ctrl" key has to be pressed. When both buttons are clicked, the tool’s function isexecuted, while it can be translated in meantime.

5.5.1 Graphical User Interface

The graphical user interface of Virtual Sculpture is implemented using the Qt API.The output window is derived from the QGLWidget class, which is the basis forOpenGL applications within the Qt framework and allows to use OpenGL and prede-fined Qt GUI elements simultaneously. Other windows include a global options bar,the tool box and an tool-options window, which adapts to the used tool (Figure 5.17).The main options grants access to the colour, save, load and new volume dialogues.Within the options pane above the main window the render mode can be set and stereorendering as well as a video background texture and rumble feedback for gamepadscan be activated.The tool box lists all available sculpting tools. They are ordered by tool classificationfrom top to bottom: boolean primitives, spray tools and selection tools. Their optionsappear in a separate window below the tool box.

5.5.2 3D Navigation

Three dimensional navigation on a two dimensional display is unintuitive and prob-lematic for most users. Computer games address this issue usually by restricting the

Page 65: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 52

Figure 5.17: Virtual Sculpture’s Graphical User Interface

player to more or less two dimensions of freedom. From real-world travelling we areused to move left, right, forward and backward but not up and down. Real six de-grees of freedom can cause disorientation especially in fast gameplay, since humansare just not trained in flying and rotating around their own axis. Even controllinganother object that can navigate in 6 DOF demands a high grade of concentration andbecomes even harder when the third dimension is rendered by perspective projectionon a two dimensional screen, rather than a real stereoscopic view.In early versions of Virtual Sculpture when the first 3D primitive modelling tool wasimplemented and the user was already able to interact with a voxel grid in real time,it was nearly impossible to achieve the intended result by moving the tool throughthe volume. The user failed to position the 3D tool correctly and regularly missed histarget in one dimension completely. It was obvious that 3D navigation and position-ing would become a major development issue.The first problem was that the tool’s position in depth had to be estimated without abasis point. 3D stereo view compensates the missing depth impression but at the ex-pense of rendering performance and thus update frequency. By using a stereo HMDthe accuracy of positioning a 3D primitive tool was slightly enhanced. Also 6 DOFforce feedback input devices like the mentioned SensAble Phantom should improvethe navigation.

Page 66: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 53

Though my intention was to make Virtual Sculpture applicable with standard hard-ware and without specialised controlling devices. All common input devices like themouse, joysticks or gamepads allow only a two dimensional navigation. Thereforhelpers had to be found, which supported the user with the tool handling.Moving the 3D tool in the coordinate system of the grid instead of the world coor-dinate system is a big improvement. This is done by rotating the tool’s moving-axiswith the grid and swapping the moving direction according to that rotation. When theuser presses the "up-button", he expects the tool to move to the top of the screen. Thisis not always given in three dimensional space, because the axis can be rotated. Evenif the tool moves in the anticipated direction, the user expects the movement to relateto the coordinate system of the volume he is working on. If the tool just moves "up"and not "to the top of the object", intuitive modelling without constant correctionsbecomes unreachable. Only by moving the tool in the volume’s coordinate systemthe user is enabled to cut a primitive out of one side of the object and move it to theother side to perform a symmetrical subtraction there.As trivial as it may seem, it has to be mentioned explicitly that a 3D primitive shouldbe semi-transparent. If the user cannot see the slicing plane, he is unable to positionthe tool correctly. Also it is unacceptable to look behind the tool after each use toverify, whether the subtraction worked as intended.Finally the tool has to be rotated with the volume. If its position and orientation staysfixed while moving the grid, the user cannot rotate around the scene and verify thetool’s exact position. It is not possible to change the perspective and continue work-ing afterwards, because only the volume rotates and the tool’s relative position to thegrid changes.Additionally in Virtual Sculpture the tool is connected with the centre of the voxelgrid by a straight, red line. This helps the user to recover the 3D tool, when hedragged it out of the view frustum accidently.If the navigation is done correctly, the operator does not recognise the built-in helpers.The application behaves just as expected.

Resume

With Virtual Sculpture an interactive volume sculpting environment for big voxelgrids was created. It uses GPU shaders together with a subdivision structure for realtime surface sampling, which can be combined with different lighting approaches:either the volume can be visualised completely within a GPU shader, or an indexmap can be extracted and shaded in software. As a third possibility for each voxelindex on that map a OpenGL point can be created, resulting in a surfel cloud that isshaded by the OpenGL standard pipeline.

Page 67: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 5. VIRTUAL SCULPTURE 54

A ray tracing system was implemented in parallel, which can also visualise the vol-ume completely in software, but is mainly used for tool-surface interaction. Thehardware accelerated render modes outperform this CPU-only approach by a factorof 2 to 15. The GPU/CPU mixed mode, which renders a complex model of 5123

voxel with averaged 10 frames per second, is superior to the GPU-only mode, sinceits shader is less complex and thus faster.Three different kinds of tools were integrated into Virtual Sculpture for volume mod-elling: boolean primitives for basic shaping, ray tracing based spray tools for surfacesculpting and control functions like undo as well as marker based selection tools forerror correction. Various supporting systems had to be applied to improve the 6 DOFnavigation and object handling. 3D tools rotate together with the volume and thusstay in the same place relative to the volume when it is moved. Such tools are trans-lated in the coordinate system of the volume rather than the global coordinate systemto allow symmetrical operations. Finally support for an virtual reality and an aug-mented reality scenario was implemented: quad buffered stereo HMDs can be usedas an 3D output device with a video background layer. A wireless gamepad withrumble feedback as well as head tracking are supported for user input.

Page 68: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Chapter 6

User Evaluation

Subsequent to the implementation of this work a user evaluation has been accom-plished. In two groups, one for the virtual environment scenario, the other usingcommon PC hardware, Virtual Sculpture has been surveyed as a modelling solution.The VR/AR hardware consisted of a Sony Glasstron 3D Stereo see-through HMDfor output and a Logitech wireless gamepad with rumble feedback as well as headtracking for user input. The visual results of the evaluation can be examined in thegallery at the end of this elaboration (Section B).The theses that were to be proved or disproved by the evaluation are:

1. The sculpting based on 3D voxel grids is intuitive and easy to learn.

2. The different kinds of tools like boolean primitives, spray tools and selectiontools, are considered handy and intuitively applicable.

3. After a short learning phase of less than 15 minutes most evaluators are ableto model a complex voxel landscape, consisting of a house, a tree, a lake and ahill or mountain.

4. The various necessary supporting systems for 3D tool-grid interaction arerecognised and appraised.

5. The voxel characteristic to have no neighbourhood connections is recognisedas a disadvantage. The majority of the evaluators would appreciate a compen-sation like operators, that compute deformations within an area of influence.

6. The user group working within the VR scenario achieved statistical better re-sults and they rate the tasks easier.

55

Page 69: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 56

6.1 The User Test

Apart from queries aiming at the above theses, the gender, age and PC experienceof the evaluators were enquired. The personal opinion about Virtual Sculpture andthe user interface as well as additional suggestions could be given to round up thequestionnaire. As all evaluators were native German speakers, the overall form wasin German and appeared like this:

Page 70: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 57

Page 71: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 58

Page 72: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 59

Page 73: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 60

Page 74: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 61

Page 75: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 62

Page 76: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 63

Page 77: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 64

The first page of the user evaluation was an introducing learning task. The usershould become familiar with various important tools of the volume sculpting envi-ronment as well as the overall controls. One half of the voxel grid should be deletedto form empty space. The limitation function of the recommended Selection tool wassupposed to be activated for the cleared area. Then a cuboid should be created byadding the box primitive to the centre of the volume. The Devourer tool and VoxelGrowth should be used to form a solid, harsh rock, which should finally be smoothedwith the Erosion filter. The rock was suggested to be painted with the Paintbrush;since the selection - limitation was active, the ground was not affected and could bedyed independently afterwards.Part 2 asked the user to sculpture a voxel scene consisting of a house, a tree, a lakeand a hill or mountain. This task had a time limit of 15 minutes. It was allowed tofall short of that time, but not to exceed it. Additionally after saving the resultingvolumes the evaluators were instructed to model freely for about 10 more minutes ifthey wanted to enhance the scenery. This was done to allow a creative dealing withthe sculptured volume.The main aim of the questionnaire was to clarify the enumerated theses by askingdirectly or collateral. Aside from personal data 15 questions about the user interface,the usability and the functionality of the whole framework as well as single toolswere posed. The results of this questionnaire will be introduced in the next section.

6.2 Results of the Evaluation

While screenshots of the designed voxel landscapes are shown in the appendix, thestatistical results of the user evaluation will now be presented within the context ofthe theses enumerated at the beginning of this chapter. Overall 18 people participatedin the evaluation, 9 of them male and 9 female. Only 5 of the users had never heardof voxels or volume graphics before. The remaining personal data that were gatheredare summarised in the following figures and show that the testers had good experi-ence with PCs but only little modelling knowledge (Figure 6.1 and Figure 6.2).The first thesis predicates that volume sculpting on voxel grids would be intuitive andeasy to learn. This is approved by the fact that 16 of 18 evaluators fulfilled the taskof modelling a complex voxel landscape within 15 minutes after only a short learningperiod satisfactorily. The users had about 10 minutes to practice with Virtual Sculp-ture before a voxel scene consisting a house, a tree, a lake and a hill or mountain hadto be designed. The success of this test backups thesis three and can be judged on thebasis of the screenshots in the appendix. Also the personal opinion of the evaluatorsabout their solution of the sculpting task could barely be more evident (Figure 6.3).For all three kinds of sculpting tools in Virtual Sculpture the participants were asked,

Page 78: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 65

Figure 6.1: Age Chart of the Evaluators

Figure 6.2: Experience of the Evaluators with PCs and Modelling

whether they found them intuitive, functional and whether the tools behaved as ex-pected or not. This works towards the second thesis, which can widely be affirmed.While the boolean primitives were fully accepted in every aspect by almost all evalu-

Page 79: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 66

Figure 6.3: Personal Appraisal of the Modelling Results

Figure 6.4: Acceptance of the Boolean Primitives

ators, the spray tools and selection tools have been rated more variably (Figure 6.6).Many helpers have been implemented to enhance the interaction between 3D toolsand the volume. Given the last charts, it has been worthwhile to take some extra time

Page 80: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 67

Figure 6.5: Acceptance of the Spray Tools

Figure 6.6: Acceptance of the Selection Tools

in developing the boolean primitives (Thesis 4). The users were asked, whether theyrecognised the helper systems and whether these supporters were reasonable (Fig-ure 6.7).

Page 81: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 68

For Thesis 5 a value between 1 and 10 should be given: lower values stood for "not soimportant", a high value for "necessary and missing". The evaluators missed a com-pensation for the lacking neighbourhood information only with an average of 3.88of 10 points within the Virtual Sculpture modelling system, although they would be

Figure 6.7: Appraisal of the Supporting Systems for Tool Interaction

necessary for deformations. Nevertheless I reckon a commercial volume sculptingsystem would include a powerful solution for soft deformations and shape modifica-tions.For the last thesis different measurements were compared between evaluators withand without VR hardware. The answer is more complex than the previous ones,since it depends on various factors and cannot be separated from influences like theuser’s experience. In the VR scenario the 3D stereo glasses mentioned above wereused for output and a wireless game-pad with rumble feedback as an input device.What can clearly be stated is that the VR testers needed an average of 12 minutesto fulfil the task to sculpture a complex voxel scene, while those without VR needed13.66 minutes. Furthermore all evaluators who failed to finish the scene in time werein that second group. But this could be more related to personal experience, becausenone of the testers with very low PC experience could be evaluated in the VR lab-oratory. Although the quality of the results seems not to be directly related to thisvalue, it should have an influence on the speed in which the tasks are accomplished.This was not the case though: the average sculpting time of those with less than 6experience points (Figure 6.2) was exactly 13 minutes, that of those with higher expe-

Page 82: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 69

rience 12.54 minutes, which inherits a difference near the accuracy of measurement.Therefore it seems that a coherence exists between the adoption of VR/AR hardwareand an improved object handling as well as simplified 3D navigation. The utilisa-tion of stereoscopic rendering and additional input devices led to an increase of themodelling speed.

Figure 6.8: General Questions About the Evaluation

Not all of the questionnaire flew into the above results; for example the userswere asked, whether they had fun with the evaluation. These answers shall also bementioned (Figure 6.8). Very interesting is also that only a minority of 6 evaluatorsfinds a Virtual Sculpture like system applicable for the postprocessing of 3D pho-tography, while a majority of 12 people determines the drafting of architectural blueprints as an interesting field of application (Figure 6.9). This might be affected by thefact that Virtual Sculpture emphasises objects modelling rather than on displayingmedical data sets.

Resume

Overall the user evaluation of Virtual Sculpture proved that the presented modellingconcept is usable for fast and intuitive 3D drafting, which the majority of the evalua-tors stated to be an appropriate area of application. Supported by a 3D stereo HMDand a rumble feedback gamepad, the sculpting control and navigation could furtherbe improved. In the sculpting test 16 of the 18 participants were able to create acomplex voxel model within minutes regardless of their previous knowledge and the

Page 83: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 6. USER EVALUATION 70

scenario. Although they have never used the tools and GUI before and many of thetesters had no experience with 3D modelling at all, the sculpting evaluation was a fullsuccess.

Figure 6.9: Possible Fields of Application

Page 84: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Chapter 7

Last Words

The utility which was implemented during this work was designed in terms of arendering performance comparison and a user evaluation. As next steps towards afull-featured modelling suit various additional functionalities would have to be added.Some of these features, like textured primitives that change a voxel colour accordingto the corresponding texel or a more powerful undo/redo capacity, have already beentested, but fell prey to time schedule. Also the user controls have to be simplified andunified. Still Virtual Sculpture is in the current form absolutely adequate to evaluatethe potentials of voxel grids for 3D modelling.

7.1 Conclusion

Real time rendering of volumes has been discussed many times before; nevertheless Iwas able to show that it is possible to render arbitrary, frequently changing volumes atinteractive frame rates using modern graphics hardware. With very limited expensesand without the need of greater alterations of the volume pipeline, the surface sam-pling process can be implemented as a GPU fragment shader. The voxel informationcan be reduced to the opacity value, which is only one bit in my case. The com-bination of hardware accelerated surface sampling and software shading has provensuperior to CPU-only ray tracing and even a GPU-only shader solution on presentconsumer hardware. Theoretically the system is capable of rendering huge volumeswith up to one billion voxels that way.The sculpting tools that were evaluated have been chosen by priority and in regardto previous publications [8]. Various support systems allow the intuitive use of 3Dprimitives and ray tracing based spray tools. It has been accentuated to be crucial toextensively help the user with the 3D navigation in a volume. Only when adequatesupporting systems are offered, this navigation becomes intuitive. 3D primitives havebeen flanked by greatly accepted ray tracing based spray tools. Other implements

71

Page 85: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 7. LAST WORDS 72

like the control tools, which are based on a selection marker at a 3D position of thegrid, have been functional in their purpose but were reviewed as less simple to han-dle. Nevertheless the evaluation showed that after a very short phase of learning andeven without any previous knowledge of 3D modelling, most reviewers are able tosculpture a complex voxel landscape satisfactory. The integrated support of virtualand augmented reality hardware like a pair of 3D stereo glasses or head trackers islikely to boost the usability. Especially a stereoscopic impression of tool and volumecan improve the handling. It also opens new application areas as augmented realitysolutions will probably become more commonly accepted in future.

7.2 Future Work

While the theoretical maximum grid size was higher by the factor of 32, the vol-ume resolution was limited to 5123 voxels during the evaluation of Virtual Sculpture.By utilising bricking1, the rendering solution would be able to handle much biggervolumes, for example 10243 voxels, as soon as the GPU performance increases ac-cordingly. Another possibility to allow the rendering of such big volumes would bethe support of larger cube textures by the hardware manufacturers. A higher resolu-tion inherits additional modelling possibilities and allows a finer surface granularity.With resolutions of less than 2563 voxels it is almost unavoidable that single pointscan be seen and aliasing artifacts occur. The used 2D filtering algorithms were onlypartly able to improve the image quality in that case. A most promising extension infuture work would be to render and manipulate multiple voxel grids at one simulta-neously (Figure 7.1). Since in Virtual Sculpture voxels only occupy one bit each, itwould be possible to upload multiple volume textures to the GPU and update themfrequently. It can be easily decided on basis of its position’s offset, to which grid avoxel belongs : the first voxel of the second grid begins with the last (plus one) indexof the first grid and so on. Multi-volume rendering would not only allow to draw acomplete voxel landscape of different, instantiated voxel entities, it would also ex-tend the sculpting system by a powerful tool: previous sculptured voxel grids couldbe used as a boolean tool themselves. It would be possible to model a tree and use itto add a forest to another volume. The possibility to craft a sculpting shape greatlyimproves any modelling solution that is based on boolean operations, which in fact isthe concept behind such man-made tools like an axe or a chisel. Many functions ofVirtual Sculpture already have been prepared for a multi-grid system, but the com-plexity of the render-cores and modelling tools would require heavy modifications tofully support it.

1bricking: the volume is divided into (for example) 8 parts, which can be uploaded to the GPU asseparate textures

Page 86: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 7. LAST WORDS 73

Figure 7.1: The Object Space of a Possible Multi-Grid Version of Virtual Sculpture

7.3 Technology Review

Drawing voxel geometry is less accurate but more intuitive than triangle mesh con-struction. It allows a very simple design of organic structures and landscapes, but isnot usable for high quality modelling in the shown form. It may be useful though forrapid prototyping of a template for a final CAD model for example.The strengths of volume sculpting lie in creative 3D painting, the creation of organicshapes and 3D drafting. Right now its most important application area is the simu-lation of tissue deformations in real time simulations of surgery and other medicalpurposes though.The possibility to triangulate volumes before they are used in real time environmentshas often been pointed out; but 3D artist often have no intention to sculpture voxelvolumes and triangulate them afterwards for interactive drawing. Instead they di-rectly work on polygonal meshes like they are used to and have a much broaderoffering of modelling and animation software to choose from.Currently in real time graphics hardware accelerated point sprites are mainly usedfor particle systems. Static objects and animated entities of non-arbitrary shape aremost efficiently visualised using triangles by modern graphics hardware. There is no

Page 87: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

CHAPTER 7. LAST WORDS 74

advantage in voxel representations as long as the user is not able to deform or destroygeometry at his own will. If he is able to blast a hole in every wall on the other hand,all polygonal systems will fail. Therefore deformations are still very limited and rarein real time applications like computer games. Compared to the overall very fewproducts that have such deformable objects in their 3D engines a superproportionalpart of them are rendered with voxel heightmaps. In the late nineties some gameshave even made use of voxel representations and abandoned hardware accelerationbecause it was not possible to render efficiently smooth hills and mountains usingtriangles in that time. And even nowadays a deformable terrain based on voxels canbe superior to a polygonal representation. If the hardware support of points as a ren-dering primitive will further improve, hybrid triangle/point based 3D engines may bethe standard of tomorrow.Voxels and surfels have both proven to be efficient primitives for intuitive sculpting.Be it as a 3D extension of the functionality of programs like Adobe’s Photoshop or aneasy 3D drafting and painting environment: for free-hand sculpting point primitivesare superior to polygons. The advantages of voxel based, three dimensional data setscompared with surfel clouds are a higher modelling flexibility and additional possi-bilities for scenery manipulation. Boolean operations are by far easier carried out onvolumes. Also sub-surface information is necessary for photorealistic rendering andalways available in volumes. Their success depends on the spreading of 3D scanningdevices as the consumer camera of the future. Holographic and three dimensionalphotography will be an important topic for following generations and today’s Photo-shops are not prepared for such an application.

Page 88: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Appendix A

Source Codes

A.1 GPU Shader for Surface Sampling

Listing : standard GLSL GPU Fragment Shader of Virtual SculptureDescription : Samples a volume’s surface by extracting 1 bit voxel data from a 3D texture and writing itsindex to the screen buffer.

//this is the texture coordinate for array accessvarying vec3 texCoord;

//this is the texture representation of the grid//each bit stands for one voxeluniform sampler3D pointGrid;

//grid size in pointsuniform int gridPointsX;uniform int gridPointsY;uniform int gridPointsZ;uniform int gridPointsXY;

//constantsconst float div255 = 1.0 / 255.0;const float div256 = 1.0 / 256.0;const float div65536 = 1.0 / 65536;const float div16777216 = 1.0 / 16777216;const float error = 0.01;

//global variablesivec3 gridPoint;

//this function computes the position of a grid voxel in the grid texture//and compares its value -> if the bit is set it computes the pointNrvoid testGridPoint(){

vec4 pointNeighbourhood = texture3D(pointGrid, texCoord);

int gX = texCoord.x * gridPointsX;

75

Page 89: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

APPENDIX A. SOURCE CODES 76

//now the exact 8Bit have to be foundint pos = gX % 32;int byteNr = pos / 8.0 + error;float byteValue;

if(byteNr == 0)byteValue = pointNeighbourhood.r * 255;

if(byteNr == 1)byteValue = pointNeighbourhood.g * 255;

if(byteNr == 2)byteValue = pointNeighbourhood.b * 255;

if(byteNr == 3)byteValue = pointNeighbourhood.a * 255;

byteValue += error; //add some rounding error

//the point is tested by shifting the interesting bit to pos 0 and computing % 2pos = pos % 8;pos = pow(2, (float)pos);byteValue = byteValue / pos;

//discard if point is emptyif((int)byteValue % 2 == 0){

discard;}

gridPoint = texCoord * ivec3(gridPointsX, gridPointsY, gridPointsZ);}

void main(void){

testGridPoint();

int result = gridPoint.x + gridPoint.y * gridPointsX + gridPoint.z * gridPointsXY;

int tempDiv = int(result * div16777216);gl_Fragcolour.x = (tempDiv) * div255;//factor out indices beyond 24Bit due to shader precisionresult = gridPoint.x + gridPoint.y * gridPointsX +( gridPointsXY * ( (gridPoint.z) - (tempDiv * (16777216/(float)gridPointsXY)) ) );tempDiv = int(result * div65536);gl_Fragcolour.y = tempDiv * div255;result -= tempDiv * (65536);tempDiv = int(result * div256);gl_Fragcolour.z = tempDiv * div255;result -= tempDiv * 256;gl_Fragcolour.a = result * div255;

}

Page 90: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

APPENDIX A. SOURCE CODES 77

A.2 GPU Shader for GPU only mode

Listing : GLSL GPU only Fragment Shader of Virtual SculptureDescription : Samples a volume’s surface by extracting 1 bit voxel data from a 3D texture. The colour ofthe voxels are set as a uniform, the shading is computed by a uniform light source and an approximatednormal extrapolated from the voxel-neighbourhood.

//this is the texture coordinate for array accessvarying vec3 texCoord;

//this is the texture representation of the grid//each bit stands for one voxeluniform sampler3D pointGrid;

//grid size in pointsuniform int gridPointsX;uniform int gridPointsY;uniform int gridPointsZ;uniform int gridPointsXY;

//voxel sizeuniform float pSize;

//LLF of griduniform vec3 LLF;

//position of camerauniform vec3 CamPos;

//position and color of lightSourceuniform vec3 LightPos;uniform vec3 LightColor;uniform vec3 LightAmbient;uniform vec3 MatColor;

//constantsconst float div256 = 1.0 / 256.0;const float error = 0.01;

//variablesivec3 gridPoint;vec3 N;

//this function computes the position of a grid voxel in the grid texture//and compares its value -> if the bit is set it computes the pointNrvoid testGridPoint(){

vec4 pointNeighbourhood = texture3D(pointGrid, texCoord);

int gX = texCoord.x * gridPointsX;

//now the exact 8Bit have to be foundint pos = gX % 32;int byteNr = pos / 8.0;float byteValue;

Page 91: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

APPENDIX A. SOURCE CODES 78

if(byteNr == 0)byteValue = pointNeighbourhood.r * 255;

if(byteNr == 1)byteValue = pointNeighbourhood.g * 255;

if(byteNr == 2)byteValue = pointNeighbourhood.b * 255;

if(byteNr == 3)byteValue = pointNeighbourhood.a * 255;

byteValue += error; //add some rounding error

//the point is tested by shifting the interesting bit to pos 0 and computing % 2pos = pos % 8;pos = pow(2, (float)pos);byteValue = byteValue / pos;

//discard if point is emptyif((int)byteValue % 2 == 0){

discard;}

gridPoint = texCoord * ivec3(gridPointsX, gridPointsY, gridPointsZ);}

bool getPoint(ivec3 point, vec3 coord){

bool returnValue = true;if(point.x >= gridPointsX || point.y >= gridPointsY || point.z >= gridPointsZ)

returnValue = false;else if(point.x < 0 || point.y < 0 || point.z < 0)

returnValue = false;

if(returnValue){

int pos = point.x % 32;int byteNr = pos / 8.0;float byteValue;

if(byteNr == 0)byteValue = pointNeighbourhood.r * 255;

if(byteNr == 1)byteValue = pointNeighbourhood.g * 255;

if(byteNr == 2)byteValue = pointNeighbourhood.b * 255;

if(byteNr == 3)byteValue = pointNeighbourhood.a * 255;

byteValue += error; //add some rounding error

//the point is tested by shifting the interesting bit to pos 0 and computing % 2

Page 92: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

APPENDIX A. SOURCE CODES 79

pos = pos % 8;pos = pow(2, (float)pos);byteValue = byteValue / pos;

//return -1 if point is emptyif((int)byteValue % 2 == 0){

returnValue = false;}

}

return returnValue;}

void computeNormal(){

bool xr, xl, yb, yt, zn, zf;

ivec3 tempGridPoint = gridPoint;vec3 tempCoord = texCoord;float xDiv = 1.0f / (float) gridPointsX;xl = getPoint(ivec3(gridPoint.x - 2, gridPoint.yz),

vec3(texCoord.x - 2 * xDiv, texCoord.yz));xr = getPoint(ivec3(gridPoint.x + 2, gridPoint.yz),

vec3(texCoord.x + 2 * xDiv, texCoord.yz));float yDiv = 1.0f / (float) gridPointsY;yb = getPoint(ivec3(gridPoint.x, gridPoint.y - 2, gridPoint.z),

vec3(texCoord.x, texCoord.y - 2 * yDiv, texCoord.z));yt = getPoint(ivec3(gridPoint.x, gridPoint.y + 2, gridPoint.z),

vec3(texCoord.x, texCoord.y + 2 * yDiv, texCoord.z));float zDiv = 1.0f / (float) gridPointsZ;zn = getPoint(ivec3(gridPoint.xy, gridPoint.z - 2),

vec3(texCoord.xy, texCoord.z - 2 * zDiv));zf = getPoint(ivec3(gridPoint.xy, gridPoint.z + 2),

vec3(texCoord.xy, texCoord.z + 2 * zDiv));

if(!zn)N.z = -1;

if(!zf)N.z += 1;

if(!yb)N.y = -1;

if(!yt)N.y += 1;

if(!xl)N.x = -1;

if(!xr)N.x += 1;

Page 93: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

APPENDIX A. SOURCE CODES 80

N = normalize(N);}

void main(void){

testGridPoint();

vec3 pos = gridPoint.xyz * pSize;

computeNormal();

vec3 L = pos - LightPos;L = normalize(L);

float colorMul = clamp(-dot(L, N), 0.0, 1.0);

gl_FragColor.xyz = MatColor.xyz * LightColor.xyz; // * 0.5;

gl_FragColor.xyz += LightAmbient.xyz;

gl_FragColor.xyz * = colorMul;}

A.3 GPU Render Core Main Loop for Z-Axis

Listing : GPU main loop of Virtual Sculpture for the z-axis as depthDescription : This loop renders a voxel grid volume as texture area packs (OpenGL quads) when z is thedepth axis (z == 0 or z == max is nearest side).

//if nearest side is front or back (+/-z)if(side == FRONT || side == BACK){//start at z = 0.5 * size(slice)

float zOffset = 0.5f * ZpInGridDiv;

//determine direction of traversalif(side == BACK){

endStep = p_VSGO->getSubGridPointCountZ();beginStep = 0;end = p_VSGO->getSubGridCountZ();

}else{

begin = p_VSGO->getSubGridCountZ()-1;end = -1;step = -1;beginStep = p_VSGO->getSubGridPointCountZ() - 1;endStep = -1;

}

//go through the grid in z-direction

Page 94: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

APPENDIX A. SOURCE CODES 81

for(int z = begin; z != end; z+=step){

//divide 2D (x,y) plane at z into uniform parts (areas)divideAndConquer(p_VSGO, 2, z);

//for all uniformly filled areasfor(unsigned int a = 0; a < areas.size(); a++){

unsigned int x, y;x = areas[a].m_beginA;y = areas[a].m_beginB;

tempBox = &(areas[a].m_bBox);sizeA = areas[a].m_endA - areas[a].m_beginA;sizeB = areas[a].m_endB - areas[a].m_beginB;

//now the slices of the melted subGrids (areas) are renderedfor(int slice = beginStep; slice != endStep; slice+=step){

glTexCoord3f(x * dX, y * dY, zOffset + z * dZ + slice * ZpInGridDiv);glVertex3f(tempBox->m_LLF.x, tempBox->m_LLF.y, tempBox->m_LLF.z + slice * pSize);glTexCoord3f(x * dX, (y+sizeB) * dY, zOffset + z * dZ + slice * ZpInGridDiv);glVertex3f(tempBox->m_LLF.x, tempBox->m_URB.y, tempBox->m_LLF.z + slice * pSize);glTexCoord3f((x+sizeA) * dX, (y+sizeB) * dY, zOffset + z * dZ + slice * ZpInGridDiv);glVertex3f(tempBox->m_URB.x, tempBox->m_URB.y, tempBox->m_LLF.z + slice * pSize);glTexCoord3f((x+sizeA) * dX, y * dY, zOffset + z * dZ + slice * ZpInGridDiv);glVertex3f(tempBox->m_URB.x, tempBox->m_LLF.y, tempBox->m_LLF.z + slice * pSize);

}}

}}

Page 95: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Appendix B

Gallery

The following screenshots were taken during the evaluation of Virtual Sculpture andrepresent the results of the sculpting test:

82

Page 96: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

APPENDIX B. GALLERY 83

Page 97: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

APPENDIX B. GALLERY 84

Page 98: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

APPENDIX B. GALLERY 85

Figure B.1: Result Volumes of the Virtual Sculpture User Evaluation

Figure B.2: A Virtual Sculpture Example Object

Page 99: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

Bibliography

[1] 3D Studio Max 5.0, Autodesk/Discreet, http://www.discreet.com, 10.08.2005

[2] 3D Studio Max Training Courses, Discreet, http://www4.discreet.com/training/,10.08.2005

[3] www.AnandTech.com GPU performance charts (page 5-7) :http://www.anandtech.com/video/showdoc.aspx?i=2195, 10.08.2005

[4] B. Adams, P. Dutre : Interactive Boolean Operation on Surfel-Bounded Solids,SIGGRAPH, San Diego, California, 2003

[5] J. Amanatides, A. Woo : A Fast Voxel Traversal Algorithm for Ray Tracing,Eurographics, Amsterdam, Netherlands, 1987

[6] M. Chen, J. Tucker : Constructive Volume Geometry, Computer Graphics Fo-rum, Volume 19, Issue 4, December 2000

[7] C. Dachsbacher, C. Vogelsang, M. Stamminger : Sequential point trees, SIG-GRAPH, San Diego, California, 2003

[8] T. Galyean and J. Hughes: Sculpting : An Interactive Volumetric ModelingTechnique, SIGGRAPH 1991, 1993

[9] S. Gibson : 3D ChainMail: a Fast Algorithm for Deforming Volumetric Objects,Symposium on Interactive 3D Graphics, Providence, USA, 1997

[10] K. Hui, H. Leung : Virtual Sculpting and Deformable Volume Modelling, IV2002

[11] G. Humphreys: Ray Casting, University of Virginia, 2005

[12] M. Jones, R. Satherley : Voxelisation: Modelling for Volume Graphics, VolumeGraphics, Springer, 2000

[13] A. E. Kaufman : Volume Visualization: Principles and Advances, SIGGRAPH,Hong Kong, 1998

86

Page 100: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

BIBLIOGRAPHY 87

[14] S. Kinashi, Y. Sugisaki, H. Kanao, M. Fujisawa, K. Miura, J. Sone : Develop-ment of a Geometric modelling Device with Force Feedback, The Journal ofThree Dimensional Images, Vol.18, No.4, 2004

[15] L. Kobbelt, M. Botsch, U. Schwanecke, H.P. Seidel : Feature-sensitive surfaceextraction from volume data, International Conference on Computer Graphicsand Interactive Techniques, 2001

[16] P. Lacroute, M. Levoy : Fast Volume rendering using a shear-warp factorizationof the viewing transformation, SIGGRAPH, 1994, pp. 451-458

[17] W. E. Lorensen, H. E. Cline : Marching Cubes: A High Resolution 3D Sur-face Construction Algorithm, ACM SIGGRAPH Computer Graphics archiveVolume 21, Issue 4 (July 1987), pp. 163 - 169

[18] Y. Lu, W. Wang, R. Liang, M. Ouhyoung : Virtual Sculptor: A Feature Preserv-ing Haptic Modeling System, ITP, 2002

[19] K. McDonnell, H. Qin : Dynamic sculpting and animation of free-form subdi-vision solids, Computer Animation, 2000

[20] K. McDonnell, H. Qin : Virtual Clay: A Real-time, Haptics-based SculptingSystem, Symposium on Interactive 3D Graphics, Research Triangle Park, USA,2001

[21] M. Meißner, J. Huang : A Practical Evaluation of Popular Volume RenderingAlgorithms, IEEE symposium on Volume visualisation, Salt Lake City, USA,2000

[22] G. E. Moore : Cramming more components onto integrated circuits (Moore’sLaw), Electronics Magazine 19. April 1965

[23] J. Müller : Entwicklung eines hybriden, GPU-unterstützten Ray Tracing Sys-tems, Studienarbeit, University Koblenz-Landau, 2003

[24] Prof. S. Müller : Computergrafik 2 - Visualisierung und Volumenrendering,University of Koblenz-Landau, 2003/2004

[25] Prof. S. Müller : Photorealistische Computergrafik, University of Koblenz-Landau, 2003/2004

[26] J. Neider, T. Davis : OpenGL Programming Guide: The Official Guide to Learn-ing OpenGL, Addison-Wesley, second edition, 1997

[27] G. M. Nielson : Volume Modelling, Volume Graphics, Springer, 2000

Page 101: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

BIBLIOGRAPHY 88

[28] A. Petersika, B. Pflesser, U. Tiede, K.H. Höhne, R. Leuwer : Realistic hap-tic volume interaction for petrous bone surgery simulation, Institute of Math-ematics and Computer Science in Medicine, ENT-Clinic, University HospitalHamburg-Eppendorf, 2002

[29] H. Pfister, J. Hardenbergh, J. Knittel, H. Lauer, and L. Seiler: The volumeproreal-time ray-casting system, International Conference on Computer Graphicsand Interactive Techniques, 1999

[30] H. Pfister: Moderne Volumenvisualisierung, Mitsubishi Electric Reseach Lab-oratories, 2004

[31] T. Purcell : Ray Tracing on a Stream Processor, University of Standford, 2004

[32] Qt toolkit, Trolltech, http://www.trolltech.com, 10.08.2005

[33] M. Reunanen : Point-Based Modeling, HUT - Telecommunications Softwareand Multimedia Laboratory

[34] P. Reuter, I. Tobor, C. Schlick, S. Dedieu : Point-based modelling and renderingusing radial basis functions, 1st international conference on Computer graphicsand interactive techniques, Melbourne, Australia, 2003

[35] C. Rezk-Salama, K. Engel, M. Bauer, G. Greiner, T. Ertl: Interactive VolumeRendering on Standard PC Graphics Hardware Using Multi-Textures and Multi-Stage Raserization, SIGGRAPH/EUROGRAPHICS Workshop On GraphicsHardware, Interlaken, Switzerland, 2000

[36] R. Rost, J. Kessenich, B. Lichtenbelt: The OpenGL Shading Language,Addison-Wesley, 2004

[37] S. Röttger : The Versatile Volume Viewer (GNU GPL), University of Erlangen:http://www9.cs.fau.de/Persons/Roettger

[38] S. Rusinkiewicz, M. Levoy: QSplat - A Multiresolution Point Rendering Sys-tem for Large Meshes, SIGGRAPH, New Orleans, USA, 2000

[39] J. Schmittler, P. Slusallek: SaarCor - Realtime Raytracing Architecture,http://www.saarcor.de

[40] SensAble Technologies, http://www.sensable.com, 10.08.2005

[41] Surface Elements as Rendering Primitives, Mitsubishi Electric Research Labo-ratory, http://www.merl.com/projects/surfels/

Page 102: Volume Modelling And Rendering Based On 3D Voxel Gridscg/Diplomarbeiten/VirtualSculpture.pdf · technique for real time volume rendering. Furthermore a ray tracing system is imple-

BIBLIOGRAPHY 89

[42] S. Yamazaki, K. Kase : Interactive Visualization of Non-manifold ImplicitSurfaces Using Pre-integrated Volume Rendering, 10th Pacific Conference onComputer Graphics and Applications, 2002

[43] M. Zwicker, M. Pauly, O. Knoll, M. Gross: Pointshop3D - A Interactive Systemfor Point-Based Surface Editing, SIGGRAPH, Zürich, Switzerland, 2002

[44] M. Zwicker, H. Pfister, J. Van Baar, and M. Gross: Ewa splatting, IEEE Trans.on Visualization and Computer Graphics, 2002