Department of Science and Technology Institutionen för teknik och naturvetenskap Linköping University Linköpings universitet

gnipökrroN 47 106 nedewS ,gnipökrroN 47 106-ES

LiU-ITN-TEK-A--17/032--SE

Concepts of Hybrid DataRendering

Torsten Gustafsson

2017-06-21

LiU-ITN-TEK-A--17/032--SE

Concepts of Hybrid DataRendering

Examensarbete utfört i Medieteknikvid Tekniska högskolan vid

Linköpings universitet

Torsten Gustafsson

Handledare Rickard EnglundExaminator Ingrid Hotz

Norrköping 2017-06-21

Upphovsrätt

Detta dokument hålls tillgängligt på Internet – eller dess framtida ersättare –under en längre tid från publiceringsdatum under förutsättning att inga extra-ordinära omständigheter uppstår.

Tillgång till dokumentet innebär tillstånd för var och en att läsa, ladda ner,skriva ut enstaka kopior för enskilt bruk och att använda det oförändrat förickekommersiell forskning och för undervisning. Överföring av upphovsrättenvid en senare tidpunkt kan inte upphäva detta tillstånd. All annan användning avdokumentet kräver upphovsmannens medgivande. För att garantera äktheten,säkerheten och tillgängligheten finns det lösningar av teknisk och administrativart.

Upphovsmannens ideella rätt innefattar rätt att bli nämnd som upphovsman iden omfattning som god sed kräver vid användning av dokumentet på ovanbeskrivna sätt samt skydd mot att dokumentet ändras eller presenteras i sådanform eller i sådant sammanhang som är kränkande för upphovsmannens litteräraeller konstnärliga anseende eller egenart.

För ytterligare information om Linköping University Electronic Press seförlagets hemsida http://www.ep.liu.se/

Copyright

The publishers will keep this document online on the Internet - or its possiblereplacement - for a considerable time from the date of publication barringexceptional circumstances.

The online availability of the document implies a permanent permission foranyone to read, to download, to print out single copies for your own use and touse it unchanged for any non-commercial research and educational purpose.Subsequent transfers of copyright cannot revoke this permission. All other usesof the document are conditional on the consent of the copyright owner. Thepublisher has taken technical and administrative measures to assure authenticity,security and accessibility.

According to intellectual property law the author has the right to bementioned when his/her work is accessed as described above and to be protectedagainst infringement.

For additional information about the Linköping University Electronic Pressand its procedures for publication and for assurance of document integrity,please refer to its WWW home page: http://www.ep.liu.se/

© Torsten Gustafsson

Concepts of Hybrid Data

Rendering

A thesis performed in Media Technologyat Linkoping University.

Torsten Gustafsson

Examiner

Ingrid Hotz

Supervisor

Rickard Englund

Norrkoping. June 25, 2017

Department of Science and TechnologyLinkoping University

Sweden

Abstract

This thesis describes methods for advanced visualization of 3D data. Order-independent transparent data between multiple datasets of varying typescan be combined using an A-buffer. In this thesis, an implementation ofsuch a buffer is presented. An optimisation of the A-buffer, based on thediscarding of unnecessary fragments will be presented. A line integral con-volution method for 3D volumes will also be presented, where noise input,and resolution of the input- compared to output volumes will be discussed.The resulting method is able to visualize multiple types of data with order-independent transparency. The rendering speed is generally fast enough foran interactive user-experience.

Contents

1 Introduction 3

1.1 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Report Structure . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Background 5

2.1 Visualization of Data . . . . . . . . . . . . . . . . . . . . . . . 52.2 Mesh Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Volume Rendering . . . . . . . . . . . . . . . . . . . . . . . . 62.4 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.5 Inviwo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.6 Rendering of Volumes and Meshes . . . . . . . . . . . . . . . . 7

2.6.1 Differences of Volume and Mesh Data . . . . . . . . . . 72.6.2 Order-Independent Transparency . . . . . . . . . . . . 82.6.3 Hybrid Data Rendering . . . . . . . . . . . . . . . . . . 92.6.4 Line Integral Convolution For Volumes . . . . . . . . . 10

2.7 A-Buffer Rendering Methods . . . . . . . . . . . . . . . . . . . 122.7.1 Using 3D Textures . . . . . . . . . . . . . . . . . . . . 122.7.2 Per-Pixel Linked Lists . . . . . . . . . . . . . . . . . . 132.7.3 Using Fragment Pages for Improved

Cache-Coherency . . . . . . . . . . . . . . . . . . . . . 142.7.4 Early Fragment Discarding . . . . . . . . . . . . . . . . 15

3 Method 17

3.1 Rendering Hybrid Data . . . . . . . . . . . . . . . . . . . . . . 173.2 A-buffer and Meshes . . . . . . . . . . . . . . . . . . . . . . . 173.3 3D Line Integral Convolution . . . . . . . . . . . . . . . . . . 18

3.3.1 Random Noise-Volume Generation . . . . . . . . . . . 19

4 Results and Evaluation 20

4.1 A-buffer method . . . . . . . . . . . . . . . . . . . . . . . . . 204.1.1 Customizable Properties . . . . . . . . . . . . . . . . . 214.1.2 Problems and Solutions . . . . . . . . . . . . . . . . . 22

1

4.2 3D-LIC method . . . . . . . . . . . . . . . . . . . . . . . . . . 224.3 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.3.1 Memory Utilization . . . . . . . . . . . . . . . . . . . . 244.3.2 Rendering Speed . . . . . . . . . . . . . . . . . . . . . 25

4.4 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5 Case Study 28

5.1 Visualization of a Heart Dataset . . . . . . . . . . . . . . . . . 285.1.1 A-buffer Methods . . . . . . . . . . . . . . . . . . . . . 285.1.2 3D-LIC . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.2 Visualization of Protein Molecules . . . . . . . . . . . . . . . . 335.2.1 Using the A-buffer . . . . . . . . . . . . . . . . . . . . 33

2

1 Introduction

In visualization we try to develop the concepts and tools necessary for theunderstanding of data. This data can look very differently depending on thecontext. Some examples of data sets may consist of scalar, vector, volumetricor geometric data, to name a few. In many applications it is a combinationof these different data types that make for an intuitive visualization.

When performing advanced volume rendering it is sometimes necessaryto render geometric data on top of volumetric data sets. To achieve this, ahybrid data visualization method needs to be used. A problem with renderinghybrid data sets is how to render the different data sets in a correctly depth-sorted, per-pixel order.

There exist many different methods that render volumetric data. Someof the methods will be discussed here. Most prominently, volume raycastingin combination with mesh rendering, as well as 3D line integral convolutionare the methods this thesis focuses on.

1.1 Purpose

This thesis aims to discuss and present some interesting hybrid data visual-ization methods, which may be useful when the more traditional renderingmethods are not enough.

Much of the focus has been on implementing an efficient A-buffer rendererto store fragments before rendering them to screen. This allows us to renderany kind of data together in the same view. This type of rendering allows usto render transparency of volumes and geometry without extra work, sincethe rendering is done in two passes, and the alpha value is easily storedtogether with the colour values.

Many of the visualizations used in this paper are based on a dataset of ahuman heart. This dataset will be discussed in detail in chapter 6.

A method for reducing the amount of data that have to be passed tothe A-buffer will be presented. Here we choose to call this method ”EarlyFragment Discarding”, because of its similarities with the commonly usedmethod called ”Early Ray Termination” that is used in volume raycasting.

3

The actual implementations was made in Inviwo [Inv]. The main reasonfor this was that Inviwo is developed by the people at the InfoVis depart-ment, which made it easy to work around unexpected problems with theimplementations. It is also a powerful tool for performing visualization suchas the ones presented in this thesis.

The thesis aim to answer the following research questions:

• Can a hybrid data visualization method be implemented in Inviwo?

• How can we render such a visualization in real-time?

• Which problems will be the most important to solve in terms of per-formance?

1.2 Report Structure

The structure of this thesis report is as follows:

• The second chapter, Background, will discuss why we want to visu-alize data, and present some of the methods used for it, as well assome related work in the field. As the work focuses a lot on A-buffermethods, theory on such methods will be presented, as well as a prefor-mance improvement to these, based on early discarding of unnecessaryfragments.

• The third chapter, Method, will present the development process, anddiscuss the problems that arose, and which solutions that was used.

• The fourth chapter, Results and Evaluation, will discuss the results ofthis work, and some ideas for possible future work in this area.

• The fifth chapter, Case Study, will discuss some of the application areasthis work was tested on.

4

2 Background

This section will discuss some general visualization methods used, and presentthe platform used for the specific implementations that took place.

2.1 Visualization of Data

Good visualization of data is important to understand the information dif-ferent datasets may contain. There exist many techniques and methods tovisualize data. Some of them are specialized for a specific type of data. Forexample, some datasets consists of points in space, which are meant to berendered by making triangles from them, and then rendered as simple ge-ometry. On the other hand, volume data can be rendered in a wide rangeof different techniques [Eng+06], and while one technique may fit well forsome problems, other volume rendering techniques may be better suited tovisualize the data when other information needs to be highlighted.

In many cases the data needs to be visualized using multiple methods toextract all of the interesting data. A visualization method can be consideredbetter than another if it is able to show more information in a way that iseasy to understand to the user. Who is using the visualization method isalso important to know, since an experienced user may be more interested inthe details of the data, while others may want to see a bigger picture of it,to understand what they are looking at.

2.2 Mesh Rendering

Based on points in 3D space. It is often rendered by grouping these pointsin groups of three, and rendering them as triangles, with each triangle con-taining colour information.

5

2.3 Volume Rendering

Often based on some kind of grid in 3D space, where each element is calleda voxel (derived from the name pixel, which is the name of an element in2D space). These elements contain information such as colour or intensity.Volumes are often visualized using ’volume raycasting’.

2.4 Related work

There exist many methods that achieves specialized rendering of data. Inmany cases the rendering of multiple, separate objects are necessary. Foropaque objects, this is easily achieved using a depth buffer that only allownew fragments that are closer than the currently stored fragment to overwriteit. In the OpenGL pipeline [KSS17] this method is built in and can be easilyimplemented in code.

Problems occur when these fragments can be transparent, since there isno way of knowing if the object currently being rendered is behind or infront of another object, before we start rendering that object. To solve thisproblem, multiple techniques have been proposed. One of these are basedon performing multiple depth tests using two depth buffers. This method iscalled ’Depth Peeling’ [Eve01]. A problem with this method is that it maybecome slow if the scene has got a high depth complexity.

There exists another method that is based on using a buffer to store a listof fragments per screen pixel. This method is called the A-buffer [Car84], andis a widely used method that have been the base for many improvements inthe years since it first was proposed. An example of such an improvement isCrassins method [Cra10] of using dynamically sized lists of fragments usinga fragment list. A problem with the A-buffer method is how to optimisethe local memory for each pixels’ fragment list. Because of the way GPUshaders work, dynamic array sizes is impossible to implement in a shaderprogram. A solution to this is proposed by Lindholm et al. [Lin+14]. Theirmethod is called ”per-pixel array optimization” and is based on using multipleshaders which uses different array sizes, and sending pixels of certain depthcomplexities to a shader using a similar array size. Lindholm also proposesanother improvement called ”per-pixel depth-peeling”, which removes theproblem of having to allocate too large array sizes completely.

Another method that achieves order-independent transparency is the k-

6

buffer [Bav+07]. It works similar to the traditional Z-buffer, which storesonly the frontmost fragment for each pixel, but it can store up to k fragments,sorted and blended in a single pass. A possible advantage of this comparedto the A-buffer is that it does not have to define a maximum scene depth itwill be able to handle.

When rendering data sets containing vector fields, a popular method touse is ’Line Integral Convolution’ (LIC). This area is well-defined in the 2Dcase, but when it comes to 3D-LIC, the works are not as numerous. Falk et al.[FW08] presents a specialized method of 3D-LIC that is largely independentof the input size when it comes to the rendering speed. Interrante [Int97]discusses the rendering of multiple overlapping volume surfaces using 3D-LIC, by using the volumes isovalue surfaces to render textures to.

2.5 Inviwo

Inviwo is a visualization toolkit developed at Linkoping University [Inv]. Itis written in C++, and uses OpenGL and GLSL to render graphics output.The methods presented in this thesis have been implemented as parts of theinviwo pipeline.

2.6 Rendering of Volumes and Meshes

In this section we will discuss specialized rendering methods for differenttypes of data, mainly volume data and mesh data. We will briefly explainthe classic approach for rendering these data types, and then discuss howthese different methods can be combined.

2.6.1 Differences of Volume and Mesh Data

Mesh data is based on vertex points in 3D space. These points are oftenrelated to each other, in that we can make triangles out of their relation toeach other. These triangles are then rendered to the screen. This renderingmethod is very common and almost all forms of 3D graphics uses it. Volumerendering on the other hand, can be performed in many different ways. Thevolume data is often represented by a cubic grid, where each element is calleda voxel. These voxels may either contain a single value each (scalar data)

7

or multiple values (vector data). The most common method of renderingvolume data is volume raycasting, which is based on sending a ray from thecamera (eye) coordinates through the volume, and sampling each voxel itpasses through.

Because of the way these data types differ, it is difficult to render themsimultaneously. We need a unified method that handles both data types atthe same time in order to make it possible.

2.6.2 Order-Independent Transparency

A problem of rendering meshes occurs when multiple triangles intersect eachother, or some triangles are behind others. To correctly render this infor-mation, we need to know the depth of each fragment rendered. Using adepth-buffer, we can check the depth of each new fragment, and compare itto the current depth value stored in that screen coordinate. If its value islower, we overwrite it, otherwise we throw it away. This is all well and good,but what if we want to see the triangles that are behind the front ones?

C.a = 1− (1− fg.a) ∗ (2− bg.a)

C.rgb =fg.rgb ∗ fg.a+ bg.rgb ∗ bg.a ∗ (1− fg.a)

C.a

(2.1)

This is where the classic RGB (Red, Green, Blue) colour space got re-placed with RGBA (Red, Green, Blue, Alpha) in order to get the alpha value,or opacity, of the fragment as well. The fragments that occupy each screencoordinate can then be sorted and blended together using the alpha blendingequation, shown in eq. 2.1.

In this equation, ’C’ represents the resulting colour value from blendingthe foreground colour ’fg’, with the background colour ’bg’. The blendedRGB values depend on the blended alpha value, which means it will need tobe calculated first.

A problem with this approach is when multiple, separate objects (datasets), are to be rendered one at a time. Because they are rendered sepa-rately, we have no way of sorting their fragments together using conventionalmethods (for example, OpenGL:s build-in alpha blending only handles oneobject at a time), and we will thus have problems when they intersect witheach other. There are several methods that solve this problem. One of themis using a buffer which first stores all the fragments, and then renders them

8

(a) Simple geometries (b) A raycasted volume (c) Combined scene withadded transparency

Figure 2.1: The A-buffer is able to combine mesh data and volume data bystoring the mesh fragments, and then rendering them together with a volume.

to the screen in a second pass. This method is called the A-buffer. Anothermethod, called depth peeling, utilizes the built in depth buffer to perform arendering technique commonly called ’ping-ponging’, that is based on per-forming a rendering pass on the scene, storing the resulting texture to abuffer, and then rendering again, using the stored texture data. This may beperformed as many times as needed, and in the case of depth-peeling, everysuch rendering pass takes us one fragment deeper in the scene. This meansthat if we have a scene with a highest depth-complexity of 30 fragments, itwould need 30 rendering passes for the depth-peeling algorithm to renderthe whole scene. On the other hand, it is rarely necessary to blend over thatmany fragments, as the accumulated alpha value often reaches values closeto one after relatively few fragments.

2.6.3 Hybrid Data Rendering

Using an A-buffer, we can render almost anything, as long as we can convertthe data points coordinate systems into a unified one. For instance, we canrun multiple meshes (standard rendering) and volumes (volume raycasting)where we store the fragment data in our A-buffer instead of rendering themdirectly to screen. Then we sort the fragments and render them in a secondpass. Figure 2.1 shows how this can look.

In order to render fragments with an A-buffer, for each fragment, wemust be able to retrieve its screen coordinates, its depth value, and its colour

9

(a) A streamline visual-ization

(b) A LIC visualizationof the same dataset

(c) 2.2b taken from an-other angle

Figure 2.2: Visualizations of a vector field dataset

value. In order to render fragments of varying transparency, an alpha valuemust also be stored.

Converting the coordinate systems between a volume and a mesh canbe done using entry- and exit points of the volume to convert it to worldcoordinates, while the mesh’s coordinates is converted to world coordinatesusing its transformation matrix. The important thing with having a correctcoordinate system in the case of using an A-buffer, is to get the correctdepth value for each fragment. If a volume and a mesh uses their own depthcoordinates, either the volume or the mesh will most likely render completelyin front of the other. Their own fragments will still be correctly depth-sortedsince they are based on the same coordinate system.

2.6.4 Line Integral Convolution For Volumes

Line Integral Convolution (hereafter referred to as ’LIC’) is useful for in-tuitive rendering of vector fields. When performing LIC on volumes, themethod must be able to handle three dimensions, compared to the two thatis necessary for images.

LIC is based on calculating output values from noise data, and a vectorfield. Thus, in order to perform LIC on volumes, a 3D noise volume must beavailable, as well as a volume containing vector data. For each voxel in theoutput volume, points are sampled along its streamline in the vector fieldusing a discrete integration method. Traversal of the streamline is eitherforwards, backwards or in both directions. Typically using a fixed step size,

10

the streamline is traversed for a limited number of steps, until enough pointshave been sampled. The mean value of these points is then used as the voxelsfinal colour value.

Figure 2.2a shows a visualization of the streamlines of a vector field.Figure 2.2b and 2.2c shows how a 3D-LIC of the same vector field mightlook.

Discrete Integration Methods

There exist many discrete integration methods, but only the two most preva-lent methods will be discussed here. These are Euler integration and fourth-order Runge-Kutta integration. Both methods are based on using fixed stepsizes, and Runge-Kutta’s method can be seen as an extension of Euler inte-gration, since first-order Runge-Kutta integration works exactly the same asEuler’s method.

yn+1 = y

n+ h ∗ f(p

n) Euler integration (2.2)

Euler integration first takes the vector field value of its starting point,and moves in its direction with the length of the step size. Then it takesthe new point it landed on, and does the same, until all steps are complete.This method is often inaccurate as the vector field typically turns faster thanthe length of the step size. Using a smaller step size reduces the error, butincreases computation time as more steps are needed. eq. 2.2 shows hownew points are calculated. Here y

n+1 is the new value to be calculated (in

vector form), ynis its previous value, h is the step length and f(p

n) is the

(normalized) direction of the vector field in point pn. the variable n starts

of at 0 and iteratively increases for a fixed number of steps.

k1 = f(pn)

k2 = f(pn+

h

2k1)

k3 = f(pn+

h

2k2)

k4 = f(pn+ hk3)

yn+1 = y

n+ h ∗

k1 + 2k2 + 2k3 + k4

6

Runge-Kutta 4 integration (2.3)

11

Another method is the fourth-order Runge-Kutta integration. Instead ofmoving directly in the direction of the vector field in the current point, ittakes the direction of the sampled point, and, from the same starting point,moves in that direction by half the step size. Then it samples the directionof the vector field in that point, moves again from the start point using halfthe step size. Then in the last step it samples a fourth point using the fullstep size. When all points are sampled, it calculates in which direction tomove based on these four sampled directions. This method is generally muchmore accurate than Euler integration. Eq. 2.3 shows how it calculates thenew direction. In this equation, the different k values are used to calculatethe resulting new value (for each step) y

n+1. f(x) is the vector field value atpoint x. p

nis the current position (point) for each step.

2.7 A-Buffer Rendering Methods

The concept of a-buffer is open to different implementation methods. Thissection explains two of the most common ones, which are based on 3D-textures and linked lists of fragments.

An A-buffer that is able to handle varying transparency and colour offragments, need to be able to store A-data (red, green, blue and alpha) aswell as depth information. This amount to five separate values, which isoften not easily stored in a single data container, because since more thanfour values is used so rarely, OpenGL’s build-in data containers do not includeany such built-in container. Instead, we need to define two buffers to storethe data, for example one that holds RGBA-data, and a separate one thatholds the depth value.

2.7.1 Using 3D Textures

This is most likely the most intuitive method when writing an A-buffer im-plementation. It is based on defining a 3D-texture to store A-buffer elements,which is used as an array of 2D textures. For each coordinate in the image,an array of fragments is stored to later be used for rendering the final image.Figure 2.3 shows an illustration of how such a texture may look. Here it isclear that many elements will often remain unused, and is thus taking up

12

y

x

z

Figure 2.3: Illustration of a 3D texture storing fragments. The z-dimensionholds the depth-complexity of each final screen pixel, while the x-y dimen-sions hold the screen pixel coordinates. Here we see an example of a scene ofnon-uniform depth. Out of 3x3x3=27 possible fragments, only 9 are used. Inreal applications, the number of unused slots is often a lot higher than this.

unnecessary space in the global GPU memory.The process goes like this: Geometry is first rendered as usual, using a

shader that stores the fragments into the 3D-texture in its next availableslot. This means that rendering multiple meshes means that every fragmentof each mesh will be stored, but there is no way of knowing in which orderthey were rendered. This is solved in the next step, where a new shader isused. This shader renders the whole screen space as a rectangle. By using thefragment coordinates, it takes the list of fragments that have been stored foreach screen coordinate, and sorts that list based on the stored depth values.Alpha blending is then performed on each fragment in the list to generatethe final pixel value.

2.7.2 Per-Pixel Linked Lists

Another method that can be used is to define a buffer to store fragments,with an accompanying buffer that stores pointers between these elements.By having the first fragment of each coordinate point to the zero index,and having the remaining ones point back to its previous fragment, a lot ofmemory can be saved compared to using the 3D-texture method, since thebuffer can be defined to be just as large as is necessary. This is advantageousespecially for scenes with high variation of depth complexity. Figure 2.4

13

Screen texture

p points to its

last fragment

fragmentfragmentfragmentend pointer

Indexed RGBA+depth

container

Global counter(next fragment available)

Figure 2.4: A screen texture is used to store pointers to the last storedfragment, which in turn points to its previous fragment. By using thesepointers, we are able to access the RGBA+depth values of each fragment.

shows the concept of using linked lists of fragments with an A-buffer.A problem with using this method is that it will generally be slower than

a texture based method, due to bad cache coherency between the fragments,since every fragment is stored separately in the buffer. The L1 and L2 cachememory is generally the fastest layers of a graphics card, that is used asan intermediary between the GPU and the global graphics memory. It isgenerally very limited in size, and this means that modern graphics cardstend to fetch chunks of memory at a time to improve speed. But if thecoherency between elements (in our case fragments) is bad (they are storedin far away locations in memory), it means that the cache will not manage tofetch multiple elements in a single fetch, and will thus require more fetches.

2.7.3 Using Fragment Pages for Improved

Cache-Coherency

A way to improve the coherency in memory is to utilize pages of fragments,instead of using single fragments as elements of the linked list. This is doneby defining a fixed ”page size” to be used by the linked list. A pointer in thelist will then point to a page of fragments instead of a single fragment.

This method should theoretically remove (or at least minimize) the prob-lem of bad cache coherency when using a linked list of fragments. Figure 2.5shows how the pages would be stored in the linked list.

14

Screen texture

ppoints to its last page

end pointer

Global counter(next page available)

page page

The pixel's last page

may contain empy fields

Figure 2.5: Here the screen texture points to a page of fragments. In thisillustration the page size is three fragments, but it can essentially be anynumber. By storing the fragments in pages, we get better performance onthe GPU.

2.7.4 Early Fragment Discarding

In many scenes, there is a lot of fragments that are stored unnecessarily.When the alpha values of the closest fragments are high enough to completelyocclude the fragments behind them, we would optimally want to have a wayof knowing beforehand which fragments those would be, since that wouldallow us to skip the occluded fragments completely in the first pass.

Here we present a method we call ”Early Fragment Discarding”, whichpartially solves this problem. It is based on using a buffer that stores theprevious frame’s highest depth that was used to store a fragment. In thefirst rendering pass, for every fragment passed into the shader, it checks ifthe depth is higher than this value. If it is, the fragment is probably notgoing to be visible in the final image and is thus discarded.

By storing fewer fragments, the performance increases for multiple rea-sons. One is that the storing of a fragment in itself takes time, and also thatby having fewer fragments, sorting them will become faster.

Information loss using the highest stored value as the threshold for dis-carding fragment is a bit high, especially during rotation, which is somethingwe want to avoid. By only using this method while the user is dragging thescene (rotation, translation etc.) and then performing a full rendering oncethe user stops interacting, a good compromise between performance and cor-rectness can be achieved. Since the fragment depth is stored in the valuespace of 0-1, we can easily add a margin to the threshold as well, which will

15

allow us to keep some of the fragments that could potentially be incorrectlydiscarded on interaction of the scene. A good value for this margin wasfound at 5%, in which most of the correct fragments were kept, while stillsignificantly improving performance, compared to not using the method atall.

16

3 Method

This chapter discusses the methods that were used in implementing the actualmodules and processors in Inviwo. It presents the data types that can bevisualized, as well as the options users have for how to visualize the data.

3.1 Rendering Hybrid Data

One of the goals of the work was to research methods of rendering differentdata types together. Specifically, mesh data and volume data was the focusof the work. These data types are well managed in Inviwo, so the implemen-tation mostly consisted of adding the functionality of the A-buffer to renderthese data types together.

Inviwo is built around processors, which are connected through inports,outports and connectors. It has got the data types for meshes as well asvolumes, so a processor that is supposed to handle any amount of these datatypes should take a list of meshes, and a list of volumes. Volume raycastingin Inviwo is generally optimised by finding the optimal entry- and exit pointsfor any given volume. This means that these should first be calculated inseparate processors, and then sent to the rendering processor. If multiplevolumes are to be allowed, multiple entry- and exit points must also becalculated. Mainly for this reason, it was decided that the rendering processorshould only be able to handle one volume. Another reasoning for this wasthat rendering multiple volumes together is rarely necessary, and that thereexist other methods of doing so in Inviwo without using an A-buffer.

3.2 A-buffer and Meshes

Because the method only needs to handle one volume, the A-buffer can besimplified to only handle the mesh fragments. By first sending these to the A-buffer shader, the fragments get stored (unsorted) in a list, which is then sentto the second rendering pass, where the fragments are sorted. After havingsorted the mesh fragments, standard volume raycasting can be performed on

17

(a) 3D-LIC using purely randomnoise

(b) 3D-LIC with Poisson disks asnoise input

Figure 3.1: Two LIC visualizations of the same volume vector field, withdifferent noise inputs. Here we can see that while random noise give a goodresult, Poisson disks will often give more distinct lines.

a volume, where we compare the foremost fragment in the A-buffer list withthe current raycasted depth, with each volume fragment, and if the depthis lower, we insert the mesh fragment first, and remove it from the mehsfragment list. By doing this until all fragments have been rendered, a scenewith OIT of multiple data types is gained. This method can be likened toperforming a merge sort of two sorted lists.

3.3 3D Line Integral Convolution

A 3D-LIC method was implemented using Euler integration, as well as Runge-Kutta order 4 integration. For every voxel in a vector field volume, a gener-ated noise volume is traversed with a certain amount of steps, in the vectorfield’s forward- and backward directions. For every step traversed the noisetexture is sampled. When all the points are sampled, their mean value isused as the final colour of the voxel.

18

3.3.1 Random Noise-Volume Generation

In order to get good results from any LIC, it is important to use a goodrandom generation model for the noise used. In this case, using a 3D volumeas the noise input, two types of noise was tested. These were purely randomnoise, where each voxel get a random value between zero and one, as well asnoise generation using Poisson disks in three dimensions.

Out of these two algorithms, the Poisson disk method was generally betterat reducing residual noise in the output volume. The method is based ongenerating points in space, based on a randomly generated starting point.

19

4 Results and Evaluation

This chapter will discuss the results of the work, as well as the conclusionsdrawn from them.

4.1 A-buffer method

Two A-buffer rendering methods have been presented. One using 3D-texturesand one using linked lists of fragment pages.

The 3D-texture method have been fully implemented, and a user may setparameters such as the maximum depth that the A-buffer will handle (thisrepresents the size of the z-dimension in the 3D-textures), and to perform aspecial rendering that highlights the areas with high depth complexity in thescene.

The other method that is based on linked list, have been fully imple-mented, but have got some unexplained bugs, shown in figure 4.1. In figure4.1a it is apparent that some artefacts appear when rendering basic geome-tries. This problem is less apparent when using more complex meshes. Seefigure 4.1b. Why these artefacts appear is still unknown, but since they onlyappear when using certain page sizes, it is most likely due to how the GPUhandles multithreading. There may be something wrong with the write-lockcurrently in place, allowing multiple fragments to write to the same memoryslot before the global counter is increased.

The memory allocated for this method is dynamic, in the sense that itstarts with a low allocation value, and upon rendering, if the buffer is filledup, it stops, expands the memory buffers, and restarts the procedure. Thisgoes on until the whole scene is filled without exceeding the limits. Thisgives in many cases much better memory utilization than the method thatis based on 3D-textures.

This answers the first research question ”Can a hybrid data visualizationmethod be implemented in Inviwo?”. The simple answer is that it can. In-viwo has full support for modern Open-GL which allows us to use an A-bufferto render fragmetns in two separate passes. The current implementation only

20

(a) Artefacts appearing on basic ge-ometries.

(b) On smaller meshes, it is muchmore subtle.

Figure 4.1: An issue when using certain page sizes on the linked list methodis that visible artefacts may appear. This is most likely due to how the GPUhandles multiple threads, overwriting values before the counter (which pointsto the next available memory slot) is increased.

have support for Nvidia graphics cards however. If it is possible to add sup-port for AMD cards is still not certain, as it has not been tested.

4.1.1 Customizable Properties

Both methods have helper processors for performing special rendering oftransparent meshes. A ”mesh properties” processor takes a mesh as inputand outputs the mesh data in a format that the A-buffer processor can handle.This processor allows the user to set a transparency value of the input mesh,as well as giving the option for special rendering of it. Only one specialrendering option have been implemented, which renders the mesh using linerendering instead of the more standard triangle rendering. These lines takeson the same transparency values as the other method, and is meant as anexample of the possible rendering methods that can be implemented using aseparate mesh properties processor.

The A-buffer compositor processor allows the user to set the size of the3D-texture, to allocate more memory, which allows scenes with higher depth-complexity to be rendered. The user may also choose to render the scenein a way that the depth complexity is visualized. This is done by countingthe number of fragments for each screen pixel and finding the one with thehighest number of fragments. The scene is then rendered in red with intensityvalues based on this value. Fragments with low depth-complexity will thenbe get colours closer to black, while high complexity fragments will get more

21

saturated shades of red.

4.1.2 Problems and Solutions

When implementing an A-buffer renderer, some problems that we had notthought of appeared that we had to find a solution for. The most prominentof these was the linked lists artefacts on geometries, that is explained at thetop of this section. We have still not found the solution for these, but whenrendering lots of small meshes, such as with the heart dataset (see chapter6), the artefacts were much too small to be visible, and the method can stillbe considered viable in certain situations.

When handling scenes with very large depth-complexity, the A-buffermay sometimes go out of bounds of the memory that is allocated. In suchsituations, instead of experiencing runtime errors or undefined behaviour, weset the screen pixels with too many fragments to black. Even if we in somesituations may have most of the information, we do not want to present it.It was considered better to show clearly to the user that more memory needsto be allocated to get a correct visualization.

4.2 3D-LIC method

The line integral convolution method presented in this paper is a basic variantof performing 3D-LIC. It allows the user to choose between two different noiseinputs, namely pure random noise, and noise using Poisson disks. It worksby integrating both forwards and backwards for each output voxel. Twoalternatives for integration methods is available: The Euler method as wellas the Runge-Kutta order 4 method.

The results vary greatly based on which random noise generation methodis used, as well as the size of the noise volume dimensions. Having a largenoise volume generally gives better results, as more fine-grained details can beextracted, but the disadvanatage of using too large sizes is that performancesuffers. Using random noise works well, as it is a fast method since each voxeldoes not depend on anything else than its own value in the generation of thevolume. This means that a large noise volume can be achieved without bigperformance hits. The Poisson disks method however, is quite a bit slower,as each new voxel to be calculated depends on all its nearby voxels duringthe volume generation. As the actual implementation was done on the GPU,

22

the noise generation often failed when attempting to generate very largevolumes using Poisson disks. This is probably because of Open-GL havinga limit on how long a shader may run a single frame (anything that takeslonger than a couple of seconds automatically fails). The reason for this willneed to be studied in more detail for a solution to be reached. Because ofthis problem, only small input volumes could be tested using Poisson disks,which is prevalent in fig. 5.4b, where large points are visible, due to the noisevolume having smaller dimensions than the vector field volume.

4.3 Performance

All performance tests presented here have been made on a computer using aNvidia GTX 580 GPU, with 4552 MB of graphics memory, and an Intel XeonW3550 CPU, with four cores and clock speed of 3.07 GHz, unless otherwisespecified.

The A-buffer methods presented in this paper are based on performingtwo rendering passes. The first writes the fragments to a fragment container(which may be different depending on the method used), then it renders themto screen in the second pass. When measuring the performance of the A-buffer methods, it is therefore relevant to measure the performance of thesepasses separately.

Table 4.1: Performance of the two A-buffer methods. The average depth-complexity was ∼12 fragments for the scene these tests were made on.

Method Max Depth Page Size Avg. FPS

3D Texture 64 - ∼223D Texture 128 - ∼18Linked Lists 64 8 ∼18Linked Lists 128 8 ∼16Linked Lists 128 2 ∼15Linked Lists 128 1 ∼14

In order to get a good time measure of each pass, timestamps were takenbefore the first pass, after the first pass, and after the second pass. Bycalculating the differences between these we could measure the time takenfor them. When running the tests using different options meant to speed

23

up one of the rendering passes, it was discovered that both time differenceschanged drastically, in contrast to just one, which would have been expected.This is probably due to some hardware optimisations performed on the CPUand/or the GPU, and thus these tests may not be 100% correct.

Still, the biggest bottleneck for the first pass is definitely the writing totextures/buffers. We can not affect this without changing the base methodsince it is necessary to write all the data in order to use it later. For thesecond pass, the depth-sorting could be considered as the biggest bottleneck.A simple insertion sort is used to sort all the fragments for each screen pixel.This was estimated to be ”good enough” since most pixels should not have adepth-complexity of more than 10 fragments for most scenes. Performancecould possibly be improved by changing the sorting method into a betterone. A reason this was not tested was because GLSL does not allow re-cursive functions, which most of the O(Nlog(N)) sorting methods are basedon. Other workarounds for implementing one of these sorting methods onthe GPU was skipped due to time-constraints. Disabling depth-sorting com-pletely currently improves overall performance by around 20-30%, but willof course give incorrect results.

4.3.1 Memory Utilization

The method of using a 3D-texture should be faster than the linked list ver-sion, since a texture pre-allocates the memory it needs, which means that itselements will be stored aligned in memory, which is good when fetching datato the L1- and L2 cache memory. By using pages of fragments, this speeddifference should theoretically be removed. One clear advantage of using thelinked list version, however, is the memory utilization on the GPU.

Table 4.2: Results from a test performed by Crassin [Cra10], that comparedthe difference in memory utilization using the 3D-textures and the linkedlists methods, when rendering transparent objects.

Dimensions (px) 3D Textures Linked Lists

512x512 64MB 6.5MB768x708 132.7MB 11.7MB1680x988 405MB 27.42MB

A problem with the 3D-texture method is that it must predefine a maxi-

24

mum depth that it will be able to handle. The linked lists method should the-oretically be able to handle any depth-complexity, but since GLSL does notallow dynamically sized arrays, a fixed value was used even for this method.This limits the performance of the method drastically. The advantage withusing this method though, is that we will have the option to allocate lessmemory and still get correct results, compared to a 3D-texture, where thedepth of the texture must be at least as big as the depth of the pixel with thehighest depth complexity. According to Crassin [Cra10], the advantage inmemory utilization of the method using linked lists can be huge when objectsof high depth-complexity is rendered in parts of the full screen space, whileother parts are either empty or very simple (which is often the case in realrendering situations). Table 4.2 shows Crassins results when comparing thetwo methods in some typical rendering situations.

4.3.2 Rendering Speed

The method that uses linked lists of fragments is mostly redundant at themoment, because of how the second rendering pass is implemented. GPUshaders does not allow local arrays of dynamic size, which is a problem forthis method, as its main advantage is that it is able to handle dynamic sizesof fragment lists. This means that performance-wise the linked lists methodcould theoretically be a lot faster than it currently is. Its current advantageover the 3D-texture method is that it does not allocate more global memorythan necessary, which allows it to handle complex scenes, even when using agraphics card with low global memory.

Table 4.1 compares the two A-buffer methods. The rendering windowthese tests were made in was 800 by 800 pixels, . Note that the EarlyFragment Discarding method was not used here.

The early fragment discarding method was tested with scenes of varyingdepth complexity, object transparency and resolutions. The results are shownin table 4.3. Here it is clear that the method is able to improve performanceof the A-buffer significantly, under the right circumstances. An unexpectedresult was that for low resolutions, removing the margin yielded worse resultscompared to using a 5% margin.

While removing the margin generally increases performance, the visualimpact of doing so is considered too big. A margin of around 5% was con-sidered good enough, while using 10% often removed the visual artefacts al-together. The performance gain of removing the margin is also small enough

25

Table 4.3: Performance of the Early Fragment Discarding method using dif-ferent parameters. All tests were performed on the same dataset. The aver-age depth-complexity of the scenes were ∼10 fragments for the 400x400 pxscene and ∼7 for the 800x800 px one.

Dimensions (px) Alpha Value Method Margin Avg. FPS

400x400 0.2 not EFD - ∼30400x400 0.2 EFD 5% ∼35400x400 1.0 EFD 0% ∼44400x400 1.0 EFD 5% ∼46400x400 1.0 EFD 10% ∼43800x800 0.2 not EFD - ∼24800x800 0.2 EFD 5% ∼32800x800 1.0 EFD 0% ∼41800x800 1.0 EFD 5% ∼40800x800 1.0 EFD 10% ∼39

that using it is easily justifiable.Since the research questions focused heavily on the resulting rendering

speed of the algorithms used, these result can be used to answer the questions.First, the question of ”How can we render such a visualization in real-time?”(referring to the hybrid data visualization method), is answered with themethod used, namely the A-buffer. Because of the way the A-buffer works,and the improvements that have been made to the implemented version ofit, a real-time visualization is achieved.

The other research question related to the rendering speed is ”Whichproblems will be the most important to solve in terms of performance?”. TheA-buffer which is based on two rendering passes, has its main bottleneck inthe storing of the fragments. This problem was solved to a large extent whenintroducing the EFD method. Another performance bottleneck (while notquite as big) is the sorting of the fragments. A faster sorting method thanthe one currently implemented would most likely improve performance evenmore.

26

4.4 Future Work

Our hybrid data rendering method using an A-buffer is fully working and isready to be used in multiple types of scenes. Something that may definitelybe improved though, is the performance. Both A-buffer methods used havea big performance problem when it comes to the second rendering pass. Thisis due to the local array sizes for each pixel being fixed to a predefined value.This problem may be reduced or even removed, using either the per-pixelarray optimization, or per-pixel depth-peeling method proposed by Lindholmet al. [Lin+14]. The performance gain of using these methods could be upto 50%, based on tests using limited sizes of the local arrays, and comparingwith the static size necessary for a full rendering of the same scene.

As discussed in the Results section, a better sorting algorithm could po-tentially be implemented to improve performance for scenes with high depthcomplexity.

An improvement to the 3D-LIC method includes better noise generation.The Poisson disks method is generally good, but it is very slow at generatinghigh resolution noise in 3D space. The optimal resolution of the noise input,in comparison to the output resolution could be studied in more detail, inorder to improve performance while still keeping a good visual representation.

27

5 Case Study

Case studies were performed on a couple of datasets. This chapter will discusshow these studies were performed and the results gained from them.

5.1 Visualization of a Heart Dataset

The implemented methods was tested a dataset of a human heart [Bus+15].The dataset was acquired using MRI scans of a healthy volunteer, and itrepresents the 4D blood flow of the heart, with the fourth dimension repre-senting the blood flow over time. Figure 5.1 shows a volume and a streamlinevisualization of one of the dataset. The volume visualization was made usingvolume-raycasting of the heart’s scalar values (not the blood flow).

In many cases, a pathline visualization is more intuitive than a streamlineone, since pathlines follow a particle along its path over time. A pathlinegenerator for the heart dataset was already available. A visualization of thepathlines of the heart can be seen in figure 5.2.

5.1.1 A-buffer Methods

A goal of this thesis was to render the blood flow together with the ”shell”of the heart. A blood flow visualization already existed, but because of themethod used in visualizing it, it was difficult to see where the ’edges’, or theshell of the heart was. Volume raycasting would help to make this clear, bydefining a transfer function that highlights the edges of the actual heart.

These methods could easily be combined using the A-buffer method de-scribed in this paper. By generating meshes from the blood flow visual-ization, and using volume raycasting, we could combine these two using anA-buffer-compositor processor. Figure 5.3 shows the results of some of thesevisualizations. Comparing figures 5.2 and 5.3b it is apparent that some ofthe shading is lost when using the A-buffer. This is simply a feature that hasnot been implemented yet and could most likely be added without problem.

28

(a) Streamline visualiza-tion of the bloodflow ofa heart.

(b) The heart datasetrendered using volume-raycasting

Figure 5.1: The heart dataset contains both vector and scalar values, al-lowing visualization methods like streamlines, and volume-raycasting to beperformed on it.

5.1.2 3D-LIC

A 3D-LIC representation of the heart was made in order to visualize thestreamlines of the heart at specific time intervals. Optimally a LIC of thepathlines of the blood flow would have been implemented, but due to timeconstraints this was not done. Visualizations of the hearts streamlines isconsidered more difficult to interpret as the user only sees the blood flow at aspecific time-step. Thus, to get a true understanding of the data, all timestepsmust be visualized one by one. In figure 5.4 two different visualizations ofthe 3D-LIC was generated using random noise, as well as Poisson disks asnoise input.

29

Figure 5.2: Pathline visualization of the heart dataset. The magnitude ofthe velocities is shown using a colour-scale from blue to yellow to red. Thered area is in the middle and is mostly hidden in this image.

30

(a) Combined pathlines and volume raycasting visualizations

(b) Pathline visual-ization using the A-buffer

(c) Same as 5.3b,but with 80% trans-parency

Figure 5.3: A-buffer visualizations of the heart. Figure 5.3a shows the volume’shell’ together with a pathlines visualization. Figures 5.3b and 5.3c showsthe A-buffer rendering of only the pathlines. Compared to figure 5.2, some ofthe shading is lost here, but on the other hand, transparency can now easilybe added, as seen in 5.3c. With the added transparency, the red areas of thepathlines are now more visible.

31

(a) LIC representation using randomnoise

(b) LIC representation using Poissondisks as noise input

Figure 5.4: The 3D-LIC was generated using two different noise inputs. Withrandom noise (5.4a), and using Poisson disks (5.4b). Here the random noisegives clearer lines, which is probably due to the poisson disks method havinggenerated too few points.

32

5.2 Visualization of Protein Molecules

Datasets of two different protein molecules was used for testing the A-buffer.The datasets were taken from the Protein Data Bank. The data representsproteins of Scheffersomyces stipitis [PDB17] and yeast protein [PDB16]. TheScheffersomyces stipitis is a much larger protein than the yeast variant.

Using this data, several different mesh representations have been made forthe purposes of this case study. These are: a surface visualization, a cartoonvisualization, a licorice visualization, and a Van der Waals-force visualization.The purpose of the cartoon visualization is to draw the protein ’backbone’.The licorice visualization highlights the important protein side chains. TheVan der Waals force is one of the weak chemical forces, and represents adistance-dependent interaction between atoms.

5.2.1 Using the A-buffer

Using the A-buffer presented in this paper, combined visualizations of thesedata representations can be made. In figure 5.6, different combinations ofthese representations have been visualized together, using the yeast proteindataset. By showing multiple representations of the same dataset togetherlike this, a user is able to get an easier understanding of the relation of theserepresentations.

Combinations of the large protein dataset is presented in figures 5.7, 5.8and 5.9. By combining representations two at a time, a user may be ableto derive additional information. Showing more than two at once will oftenresult in cluttering of the data, and the user may not be able to separate whatis what. A solution to that while still allowing the user to interact with allrepresentations at once is to make the transparency values of each individualrepresentation adjustable. This allows the user to effectively hide data thatis not relevant at the moment, allowing better focus on the important parts,while still being able to interact with every data representation at once.

33

(a) Surface visualization (b) Cartoon visualization

(c) Licorice visualization(d) Van der Waals-force visual-ization

Figure 5.5: Different mesh visualizations of the large protein dataset[PDB17]. In 5.5a, we see a surface visualization. 5.5b shows the backboneof the protein (cartoon). 5.5c visualizes the important protein side chains(licorice). In 5.5d, the Van der Waals-force between the atoms is visualizedas spheres.

34

(a) Surface and licorice visualization

(b) The Van der Waals-force and licorice visual-izations.

(c) Cartoon and licoricevisualization

(d) All four representa-tions combined.

Figure 5.6: Combined representations of a yeast protein. 5.6a highlights thesurface of the protein together with a licorice representation. The Van derWaals-force rendered together with the licorice representation in 5.6b showshow two different forces connects the atoms. 5.6c shows the relation of theprotein backbone and its side chains. Finally in 5.6d all representations arecombined as one.

35

(a) Surface and licorice visualization

(b) Surface and cartoon visualization

Figure 5.7: Surface visualizations of the licorice and cartoon representationsin 5.7a and 5.7b give a clear understanding of the size of the protein, whenvisualizing specific data.

36

Figure 5.8: Cartoon and licorice visualizations combined, for the large pro-tein. Here we can see how the protein backbone relates to the side chains.The side chains will for the most part closely follow the backbone, but willsometimes stretch out from it.

37

Figure 5.9: All four representations of the large protein combined together.While this may not be all too useful to visualize at once, as we get a lot ofcluttering, it serves to show what is possible using this kind of visualization.An argument for using it is that the user may set the transparency for eachrepresentation separately, making it possible to show all the relations in onewindow, while still keeping control of the interesting parts of the data.

38

Bibliography

[Bav+07] Louis Bavoil et al. “Multi-Fragment Effects on the GPU usingthe k-Buffer”. In: I3D ’07 Proceedings of the 2007 symposium onInteractive 3D graphics and games. Pages 97-104 (2007).

[Bus+15] M. Bustamante et al. “Atlas-based analysis of 4D flow CMR: Au-tomated vessel segmentation and flow quantification”. In: Journalof Cardiovascular Magnetic Resonance (2015).

[Car84] L. Carpenter. “The A -buffer, an antialiased hidden surface method”.In: SIGGRAPH ’84 Proceedings of the 11th annual conferenceon Computer graphics and interactive techniques. Pages 103-108(1984).

[Cra10] C. Crassin. OpenGL 4.0+ ABuffer V2.0: Linked lists of fragmentpages. July 2010. url: http://blog.icare3d.org/2010/07/.

[Eng+06] K. Engel et al. Real-Time Volume Graphics. Wellesley, Massachusetts:A K Peters, Ltd., 2006.

[Eve01] C. Everitt. “Interactive order-independent transparency”. In: NVIDIAOpenGL Applications Engineering (2001).

[FW08] M. Falk and D. Weiskopf. “Output-Sensitive 3D Line IntegralConvolution”. In: IEEE Computer Society (2008).

[Int97] V. Interrante. “Illustrating surface shape in volume data via prin-cipal direction-driven 3D line integral convolution”. In: SIGGRAPH’97 Proceedings of the 24th annual conference on Computer graph-ics and interactive techniques. Pages 109-116 (1997).

[Inv] Inviwo. Inviwo - Interactive Visualization Workshop. url: https://www.inviwo.org/.

[KSS17] J Kessenich, G. Sellers, and D. Shreiner. OpenGL ProgrammingGuide: The Official Guide to Learning OpenGL, Version 4.5.Boston, Massachusetts: Addison-Wesley, 2017.

[Lin+14] S. Lindholm et al. “Hybrid Data Visualization Based on DepthComplexity Histogram Analysis”. In: Computer Graphics Forum(2014).

39

[PDB16] PDB. Crystal structure of yeast Cdt1 C-terminal domain. Nov.2016. url: http://www.rcsb.org/pdb/explore/explore.do?structureId=5meb.

[PDB17] PDB. Crystal structure of Scheffersomyces stipitis Rai1 in com-plex with (3’-NADP)+ and calcium ion. Jan. 2017. url: http://www.rcsb.org/pdb/explore/explore.do?structureId=5ulj.

40