FRIEDRICH-ALEXANDER-UNIVERSITÄT ERLANGEN-NÜRNBERGTECHNISCHE FAKULTÄT DEPARTMENT INFORMATIK

Lehrstuhl für Informatik 10 (Systemsimulation)

Volumetric method for calculating the ow around moving objects

in lattice-Boltzmann schemes

Benedikt Rauh

Bachelor Thesis

Volumetric method for calculating the ow around moving objects

in lattice-Boltzmann schemes

Benedikt RauhBachelor Thesis

Aufgabensteller: Prof. Dr. U. Rüde

Betreuer: Dipl.-Inf. Simon Bogner; Dipl.-Ing. (FH) Dominik Bartuschat, M.Sc.(hons)

Bearbeitungszeitraum: 15.5.2013 14.10.2013

Erklärung:

Ich versichere, dass ich die Arbeit ohne fremde Hilfe und ohne Benutzung anderer als der angege-benen Quellen angefertigt habe und dass die Arbeit in gleicher oder ähnlicher Form noch keineranderen Prüfungsbehörde vorgelegen hat und von dieser als Teil einer Prüfungsleistung angenom-men wurde. Alle Ausführungen, die wörtlich oder sinngemäÿ übernommen wurden, sind als solchegekennzeichnet.

Der Universität Erlangen-Nürnberg, vertreten durch den Lehrstuhl für Systemsimulation (Informa-tik 10), wird für Zwecke der Forschung und Lehre ein einfaches, kostenloses, zeitlich und örtlichunbeschränktes Nutzungsrecht an den Arbeitsergebnissen der Bachelor Thesis einschlieÿlich etwai-ger Schutzrechte und Urheberrechte eingeräumt.

Erlangen, den 14. Oktober 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Abstract

A simulation framework called waLBerla has been developed at the chair of System Simulation.The major purpose is, besides other purposes, to simulate uid ows. The ow calculations arebased on the lattice-Botzmann method. Fictitious uid particles are simulated to ow from onecell to the next. If the uid cell borders on an obstacle cell, such as at the border of the simulationdomain or an oating object, a boundary function has to be applied. It has to be assured thatthe particles are correctly reected and no mass is gained or lost. There are simple algorithms forcube aligned boundaries, but curved boundaries and arbitrarily shaped objects, such as spheresor tetrahedrons, have to be approximated by cubic cells. This approximation is called staircaseapproximation or stairs approximation because it looks like a sequence of steps. This method ismass conserving but leads to unwanted numerical errors. Another approach, which has also beenimplemented in waLBerla, is to increase the accuracy via interpolation. This method is fast andaccurate, but leads to uctuations in mass. Within this thesis, another, alternative method has beenimplemented, which works with objects approximated by triangulated meshes. The approximationcan be arbitrarily exact and interpolation is not necessary. This makes the method accurate andmass conserving. The forces acting on the facets, and therefore the drag force, can be calculatedeasily by using the existing data structures. The method can be extended to moving objects. Thiscould be an attractive approach, since the objects are independent of the grid. Unfortunately thismakes computations very slow. It is neither suited for simulations with many objects. A cubeand a sphere are simulated to prove the mass conservation and accuracy of the method and itsimplementation.

Zusammenfassung

Am Lehrstuhl für Systemsimulation gibt es das Simulations-Programmpaket waLBerla, welches vor-rangig für die Simulation von Strömungen eingesetzt wird. In der lattice-Botzmann-Methode, aufder die Strömungsberechnungen basieren, wird simuliert, dass ktive Fluidpartikel von einer Zellezur nächsten strömen. Wenn die Fluidzelle aber an eine Randzelle angrenzt, wie z.B. am Rand derSimulationsdomäne oder bei einem schwimmenden Körper, muss eine Randbehandlungsfunktionsicherstellen, dass die Fluidpartikel korrekt reektiert werden und keine Masse verloren geht. Fürdas Reektieren an geraden Flächen, welche keine Fluidzellen schneiden, gibt es sehr einfache Algo-rithmen. Doch gebogene Flächen und beliebig geformte Körper wie Kugeln oder Tetraeder müssenmit würfelförmigen Zellen approximiert werden. Diese Approximation wird Treppenapproximationgenannt und resultiert in ungewünschten Ungenauigkeiten. Ein weiterer ebenfalls in waLBerla im-plementierter Ansatz ist, die Genauigkeit durch Interpolation zu erhöhen. Diese Methode ist sehrgenau und schnell. Da sie aber nicht auf physikalischen Prinzipien basiert, ist sie nicht ganz korrektund es ergeben sich Schwankungen in der Masse. Im Zusammenhang mit dieser Arbeit wurde eineweitere, alternative Randbehandlungsfunktion implementiert, die mit Dreiecksgittern als beliebigexakte Approximation von Objekten arbeitet. Interpolation ist nicht nötig, sodass die Methodenicht nur sehr genau, sondern auch masseerhaltend ist. Die Kräfte, die auf den einzelnen Flächenwirken, und damit der Strömungswiderstand, lassen sich einfach mit den vorhandenen Datenstruk-turen berechnen. Die Methode lässt sich auch auf sich bewegende Objekte erweitern, was sich durchdie Unabhängigkeit vom Simulationsgitter anbietet; sie wird dadurch aber sehr langsam. Für Sim-ulationen mit vielen Objekten ist die Methode nicht geeignet. Es wird ein Würfel und eine Kugelsimuliert, um die Masseerhalung und die Richtigkeit der Methode zu belegen.

Contents

1 Introduction 5

1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Structure of this thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 The lattice-Boltzmann method 7

2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Lattice-Boltzmann in practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.3 Boundary Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3.1 Interpolation method for xed boundaries . . . . . . . . . . . . . . . . . . . . 10

3 The volumetric boundary handling method 13

3.1 Overview and data structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2 No-slip boundary condition for xed surfaces . . . . . . . . . . . . . . . . . . . . . . 14

3.3 Movement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.3.1 Modication of the propagation rule . . . . . . . . . . . . . . . . . . . . . . . 16

3.3.2 Treatment of changing cell sizes . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Implementation 18

4.1 Object representation using Nef Polyhedra . . . . . . . . . . . . . . . . . . . . . . . . 18

4.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.1.2 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4.2 Volume calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.2.1 Volume integral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.2.2 Reduction to surface integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.2.3 Reduction to projection integrals . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.2.4 Reduction to line integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.2.5 Computation of line integrals from vertex coordinates . . . . . . . . . . . . . 25

5 Simulation 27

5.1 Empty simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5.2 Simulation of a cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5.3 Simulation of a Sphere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

6 Conclusion 33

Bibliography 34

1

Contents

List of Figures 36

List of Tables 38

A Appendix A 39

B Appendix B 42

2

Nomenclature

∩ intersection

∪ set union

∆V (~x) volume of cell ~x

∆x = ∆y = ∆z grid cell dimensions

∆ symmetric dierence

Γin,αi∗ (t) total incoming mass of Sα in direction i∗

Γout,αi (t) reected mass of facet Sα in direction i

m exterior normal along the boundary

λ relaxation time

∇ del operator or nabla

ν kinematic shear viscosity

Ω(f) collision term of the Boltzmann equation

Ωi(~x, t) collision term of the discretised LBE

Φαi volume of parallelepiped of facet α in direction i

Π region in a plane bounded by the single curve ∂Π

ρ uid density

\ set dierence

τ lattice relaxation time

fi(~x, t) post-collision distribution function

M(~x, t∗) total cell mass after collision and propagation steps, without Bi(~x+ ~ci∆t, t)

ν region in space bounded by the surface ∂ν

~ξ microscopic uid velocity

~ci uid velocity in direction i

~Fα(t) net force on facet Sα

~nα normal of facet α

~ub object velocity

~x grid position

Aα area of facet Sα

Bnk (λ) Bernstein Polynomial

3

Contents

Bi(~x+ ~ci∆t, t) extra mass added or removed from boundary cells to establish the no-slip boundarycondition for moving objects

ci∗ reverse velocity of ci

cs = 1/√

3 speed of sound

f(~x, ~ξ) continuous velocity distribution function

f (0) local Maxwell distribution/equilibrium distribution

Fb body forces acting on the uid

fi(~x, t) particle distribution function in discrete velocity space

feqi (~x, t) equilibrium distribution function in discrete velocity space

M(~x, t∗) total mass of a uid cell before the movement of the surface

Ni(~x, t) mass distribution at cell ~x in direction i

N′

i (~x, t) normal lattice-Boltzmann equation

p pressure

P = p/p0 kinematic pressure

p0 constant mass density

Pαi (~x) fraction of mass in cell ~x hitting facet α

P disti (~x) fraction of mass that will hit the surface

Pundisti (~x) fraction of mass that does not hit the surface

Pyrp(x) local pyramid of P in x

Qi(~x+ ~ci∆t, t) reected mass in direction i arriving in cell ~x+ ~ci∆t

Sα facet α

t time

t+ moment after collision, but before propagation step

tp,i global, direction dependent equilibrium distribution weights

v ow velocity

V αi (~x)[= V αi∗ (~x)] intersection volume of parallelepiped of facet α in direction i and cell ~x

D3Q19 3-dimensional LBM model with 19 velocities

LBE lattice-Boltzmann equation

LBM lattice-Boltzmann method

4

1. Introduction

1.1. Motivation

Figure 1.1: Spheres in liquid Taken from http://2.bp.blogspot.com

There are many examples, where objects are moving in a uid such as particles moving insuspensions, corpuscles in blood or a rotor shaft of a wind turbine. The physics of the ow around amoving object is well understood, accurate and fast simulation, however, still presents a challenge.In this thesis for the simulation of uids the lattice-Botzmann method (LBM) is employed (seeChapter 2). The whole domain is divided into cubic grid cells and objects are placed in this domain.In the original method proposed by Ladd [1], the moving objects are approximated by setting theobstacle ag of the cells of which the midpoint (later referred to as uid node) is inside the objectto one. Thus, a zig-zag shape, also called staircase shape, results. Using the LBM, uid moleculesfor each time step either stay unchanged or move to their neighbouring cells. If this cell is markedas obstacle, a boundary handling function has to be applied. Usually a no-slip boundary conditionis implemented by using the bounce-back rule, which means that the velocity of uid molecules isinverted when they are about to hit an obstacle cell. That is to say, a particle hitting the surfaceis being reected to its originating position. Especially for curved surfaces, this leads, due to thestaircase approximation, to a signicant numerical error. To improve the accuracy, interpolation,such as proposed by Bouzidi, et al [2], could be used with the loss of mass conservation due tonumerical errors.Movement also provokes problems. Since the objects are approximated by cubic cells, whole cubeshave to be set to uid or obstacle when an object changes position. This leads to a changing shapeof the simulated objects and to numerical uctuations.The method, which is discussed in this thesis, was proposed by Rohde [3] and combines the merits ofthe two aforementioned ones - it promises to be accurate and mass conserving; additionally, movingobjects can be handled accurately. In Rohde's volumetric method a oating object is approximatedby a polygon mesh. The amount of uid particles hitting the surface is calculated by means ofparallelepipeds originating from the object's facets. This yields the advantages of accuracy, grid

5

Introduction

independence, mass conservation and the possibility of simulating arbitrarily shaped, moving objects[3][4][5].

Figure 1.2: Staircase approximation: Theboundary is set exactly between two nodes.Taken from [4]

Figure 1.3: Curved boundary without ap-proximation. Taken from [4]

1.2. Structure of this thesis

The thesis is structured in four main parts. In Chapter 2 a short introduction is given to the lattice-Boltzmann method in general and the Navier-Stokes equations. An introduction to boundaryconditions follows with the presentation of the interpolation method of Bouzidi, which is a fastalternative to the volumetric method. Chapter 3 explains Rohde's boundary condition in detail.The next chapter deals with two implementation details, which are the choice of the object anduid cell representation as well as the method for calculating volumes of arbitrarily shaped objects.The results of the application of the volumetric method are presented in the last chapter.

6

2. The lattice-Boltzmann method

A few basics of the LBM are necessary to understand the volumetric boundary method. In thischapter, only the fundamental ideas of the lattice-Boltzmann method are outlined for readers with-out background knowledge to enable the understanding of the following chapters. Reference is madeto the bibliography for further reading.

2.1. Background

The LBM is a method for simulating uids such as liquids or gases. The Navier-Stokes-Equation isthe physical description of a uid motion and shall be mentioned here as well. It is often used forexact simulations and to investigate the accuracy of faster methods. The Navier-Stokes-Equationfor an incompressible uid reads:

∂v

∂t+ (v · ∇)v = −∇P + ν∇2v, (2.1)

where v is the ow velocity, P = p/p0 the kinematic pressure, p the pressure, p0 the constantmass density, ν the kinematic shear viscosity and ∇ the del operator. Dierent uids such aswater or air have their specic values of mass density and viscosity by which they are characterized(νwater = 10−6m2/s, νair = 1.5 · 10−5m2/s). Even though their microscopic interactions are quitedierent (compare gases and liquids), incompressible ows of these uids obey the same form of(Navier-Stokes) equation. In conventional computational uid dynamics (CFD), methods are basedon numerical solutions of the Navier-Stokes-Equation. [6][4]

In contrast to conventional CFD, LBM solves the discrete Boltzmann equation, which is basedon the continuous Boltzmann equation, established by the Austrian scientist Ludwig Boltzmannin 1872. The Boltzmann equation describes the behaviour of uids on a microscopic scale. Fluidsconsist of particles, e.g. atoms or molecules, which are constantly moving, colliding, and inuencingeach other . In a simulation, the position ~x and velocity ~ξ of these particles have do be described.If we consider a three dimensional space, this can be done by a six dimensional vector compound ofposition and velocity (x, y, z, ξx, ξy, ξz) (from now on called the µ−space). Since air, as an exampleof a typical gas, contains around 2.7 · 1019 particles per cm³, neither performance nor memory ofcurrent computers are sucient to handle this amount. Instead, a volume d~xd~ξ in µ − space isdened to describe the density of the gas. If we dene dN as the number of particles in this volume,the molecular velocity distribution function reads as follows:

f(~x, ~ξ) =dN

d~xd~ξ(2.2)

f(~x, ~ξ) is a probability density function yielding a oating point value. That means, instead ofsimulating each single particle, the probability for a number of uid particles that move in direction~ξ to be in a certain very small region of space is calculated. The particles are assumed to be equallydistributed in these spaces. To derive the Boltzmann equation three assumptions have to be made:

1. In particle collisions, it is assumed that only two particles are involved.

2. The particles are structureless and point-like. Their velocities are not correlated before andafter the collision

7

The lattice-Boltzmann method

3. Lastly, it is assumed that the collision dynamics are instantaneous and not inuenced byexternal forces.

Now the Boltzmann equation can be formulated:

∂f

∂t+ ~ξ

∂f

∂~x= Ω(f) (2.3)

The left-hand side of the equation describes the overall motion of the particles with the microscopicvelocity ~ξ, whereas the right-hand side represents the interaction of the molecules via the collisionoperator Ω(f). The integral equation Ω(f) includes the dierential collision cross section σ for theparticles. σ can be calculated by approximating the molecules with rigid spheres for the collision.With the subscripts 1 and 2 for two particles, Ω(f) can be written as:

Ω(f) =

∫(f′

1f′

2 − f1f2)σ(|~v1 − ~v2|, ~ω)d~ωd~x2, (2.4)

where ~ω is the solid angle over which is integrate, or guratively, around which collisions areconsidered. Usually the collision term is modied according to the BGK-model (Bhatnagar-Gross-Krook) in order to replace the complex collision integral with a mathematically substantially easierformulation, which describes the relaxation of a distribution function to a Maxwell distribution.The Boltzmann equation with BGK-term reads:

∂f

∂t+ ~ξ

∂f

∂~x=

(f (0) − f)

λ(2.5)

where f (0) is a local Maxwell distribution (= equilibrium distribution) and λ the relaxation time,which depends on the uid viscosity. In the BGK-model, which was introduced in 1954 by Prabhu L.Bhatnagar, Eugene P. Gross, and Max Krook, the collision term is simplied, whereas fundamentalproperties of the Boltzmann equation are preserved such as the entropy condition of the second lawof thermodynamics (H-theorem) and the moments leading to the general conservation law. [5] [7]

2.2. Lattice-Boltzmann in practice

To solve the Boltzmann equation it has to be discretised in time, space and velocity. Discretisationin time is done by considering only constant time steps ∆t. The space is divided into cubic cells withedge length normalized to 1, which makes calculations more convenient. Sometimes the domainis also seen as a lattice with uid nodes where the particles are concentrated. For this thesis thenodes can be imagined to be located at the center of their cells. Using the D3Q19-model (threedimensions, 19 velocity directions. Other models would be D2Q9, D3Q15 and D3Q27.) the velocityspace is discretised into 19 vectors ci, whereas c0 denotes a velocity of 0 and therefore representsuid particles which stay motionless in the cell.

~cC = (0, 0, 0)~cW,E ,~cN,S ,~cT,B = (±1, 0, 0), (0,±1, 0), (0, 0,±1)

~cNW,NE,SW,SE ,~cTW,TE,BW,BE ,~cTN,TS,BN,BS = (±1,±1, 0), (±1, 0,±1), (0,±1,±1)

Each simulation step is divided into two sub-steps - the stream step and the collision step. The ideais that during the stream step, uid particles ow alongside their velocity vector to a neighbouringcell. What actually happens is, that during the stream step the velocity vectors are passed on to theneighbouring cells. In the collision step, collisions among the uid particles are simulated, whichcauses the particles to be drawn towards equilibrium state. To understand the equilibrium state,one could imagine a lake into which a stone has been thrown. On the surface, waves arise and thewater around the stone is in motion. It is in non-equilibrium state and could be simulated withthe LBM. After waiting a while, when the water is motionless again, it has reached equilibrium

8

The lattice-Boltzmann method

Figure 2.1: D3Q19-model Taken from [4]

state. All uids tend to reach this state of balance. The equilibrium distribution function can becalculated as follows:

feqi (~x, t) = tp,i · [ρ+3

d2ci · v +

9

2d4(ci · v)2 − 3

2d2v · v], (2.6)

where ρ stands for the lattice density, v is the lattice velocity, d = ∆~x/∆t, ∆~x is the cell size, and∆t is a time step. tp,i is a direction dependent weighting factor:

tp,i =

1/3, i = C1/18, i = N,S,W,E, T,B1/36, i = NW,NE,SW,SE, TN, TS, TW, TE,BN,BS,BW,BE

The global equilibrium distribution weights tp,i are also used for initial conditions; the sum overall the tp,i in a cell is 1. In the LBM, the following discretisation of the Botzmann equation is used:

fi(~x+ ~ci∆t, t+ ∆t) = fi(~x, t)−1

τ[fi(~x, t)− feqi (~x, t)], (2.7)

where feqi (~x, t) denotes the equilibrium distribution function and τ = λ/∆t is the lattice relaxationtime.

This discretised equation is divided according to the two sub-steps:

fi(~x, t) = fi(~x, t)−1

τ[fi(~x, t)− feqi (~x, t)] (collision step)

fi(~x+ ci∆t, t+ ∆t) = fi(~x, t), (stream step)

where fi(~x, t) represents the post-collision distribution function.[4]

9

The lattice-Boltzmann method

2.3. Boundary Condition

Figure 2.2: No-slip boundary condition be-fore and after stream step. Taken from [4]

Figure 2.3: Free-slip boundary condition be-fore and after stream step.Taken from [4]

For every time step of a simulation a sweep function is applied to each one of the uid cellsand performs collision and stream step. Cells (so called boundary cells) adjacent to boundaries orobstacle cells have to be treated dierently, though. The collision step can be carried out usually,but uid particles cannot be allowed to stream into an obstacle cell. Instead, they are reected,which can be implemented via a no-slip or free-slip boundary condition. In the no-slip boundarycondition, due to friction, a uid velocity of zero is assumed at the surface. Hence, all near-obstaclecells should have the same quantity of particles moving towards the boundary as of those, moving inthe opposite direction. Assuming approximated surfaces with staircase shape exactly between twonodes, this can be achieved through the bounce-back rule by setting the distribution functions indirection of the surface to the opposite direction (see Figure 2.2). The uid particles reach the wallafter half their way, are reected and arrive in their cell of origin with an opposite ow direction(see gure 2.4). With ci∗ being the reversed velocity of ci [ci∗ = −ci] the bounce-back rule can beformulated as

fi∗(~x, t+ 1) = fi(~x, t+), (2.8)

where t+ denotes the moment after the collision but before the propagation step. [2] The free-slip boundary condition simulates walls with no friction at all; distribution functions are reectedaccording to the law of reection: The angle of incidence equals the angle of reection (see Figure2.3). From now on, only the no-slip boundary condition will be considered. For the bounce-backrule a wall exactly in the middle between two nodes has been assumed. If we want to considercurved geometries or to increase the accuracy, also other distances have to be taken into account.Particles are partly reected to the opposite uid cell if the distance to the wall is less than 0.5(Figure 2.5). If the distance is greater than 0.5, uid particles ow partly undisturbed and arepartly reected (Figure 2.5). [4]

Figure 2.4: Wall distance 0.5Taken from [4]

Figure 2.5: Wall distance <0.5Taken from [4]

Figure 2.6: Wall distance >0.5Taken from [4]

2.3.1. Interpolation method for xed boundaries

Before the volumetric method will be discussed, another approach to handle curved boundariesshall be presented so that comparisons can be made. Bouzidi et al. [2] use an interpolation of thevelocity distribution functions of two or three nodes to increase the accuracy at curved boundaries.

10

The lattice-Boltzmann method

Figure 2.7: Interpolation with wall close to the boundary cell (a) and far from the boundary cell(b). Taken from [2]

The method is simple, robust, ecient and leads to a second-order accuracy. Yet the drawback ofthis method is that it is not mass conserving.

In this example, A denotes the last uid node next to the wall, which will be considered to beon the right. B is the rst solid node and the wall position is given by C. q = |AC|/|AB| denotesthe location of the wall with respect to A and B. After moving over a total distance of 1, a particleoriginating form A and being reected from the wall will not reach a uid node, unless q is equalto 0, 1/2, or 1. Therefore, after the collision step, it is unknown how many particles are located inA with velocity L (see Figure 2.7). Two cases are being distinguished:

(a) For q < 1/2, we compute the population of ctitious particles at location D that will ow to Aafter bouncing back on the wall at C.

(b) For q ≥ 1/2, particles leaving A and arriving in D are simulated. To compute the unknownquantities at A, uid nodes E (and F) will be considered as well.

In both cases, linear or quadratic interpolation formulas are used, involving values at two orthree nodes. At rst all links of the lattice that cross the boundary are considered. Supposing ~x isa uid node such that (~x+ ci∆t) is a solid node, the interpolations read:

fi∗(~x, t+ ∆t) = 2qfi(~x, t+) + (1− 2q)fi(~x− ci∆t, t+), q <1

2(2.9)

fi∗(~x, t+ ∆t) =1

2qfi(~x, t+) +

(2q − 1)

2qfi∗(~x, t+), q ≥ 1

2, (2.10)

The f(·, t+ 1) on the left-hand side will be used after propagation, i.e. after a complete LBM timestep. There are two dierent equations needed, depending on q, to avoid intolerable instabilities ifonly one equation is used.

Quadratic interpolation leads to the following formulae:

fi∗(~x, t+ ∆t) =q(2q + 1)fi(~x, t+) + (1 + 2q)(1− 2q)fi(~x− ci∆t, t+)−

q(1− 2q)fi(~x− 2ci∆t, t+), q <1

2

(2.11)

11

The lattice-Boltzmann method

fi∗(~x, t+ ∆t) =1

q(2q + 1)fi(~x, t+) +

(2q − 1)

qfi∗(~x, t+)+ (2.12)

Since the equations 2.9, 2.10, 2.11 and 2.12 only use interpolations, they are superior in terms ofstability to some other schemes using extrapolations[8][9]. The change in q is continuous and theequations are reduced to the bounce-back scheme when q = 1/2. For values of q 6= 1/2 small gainsand losses of mass can be observed. [2]

12

3. The volumetric boundary

handling method

The boundary handling function, which is discussed now, was proposed by M. Rohde, et. al in2002 [3]. It is an approach that abolishes the dependency on grid nodes. Since the objects aregiven in triangulated form as originally proposed by Chen [10], the surface is given in a much moredetailed representation and can be positioned in the computational domain more accurately. Therigid, triangulated objects can be arbitrarily shaped and their shape doesn't change during theirmovement. This avoids unwanted uctuations. The surface is considered to be closed, thereforeno internal uid is used. In contrast to Ladd's staircase method [1], mass conservation can beachieved without internal ow. Further advantages: The resolution of the surface can be increasedfor higher accuracy and the force (i.e. ux of momentum) can be calculated separately for eachfacet. Thus, it is possible to determine locally and accurately the tangential and normal forcesacting on the surfaces. First results suggested second-order accuracy. However, they were found ina later publication [11] to be only of rst-order accuracy in space for a plane Poiseuille ow. [3]

Figure 3.1: (a)Triangulated sphere. (b) Facet with normal ~nα. Taken from [3]

3.1. Overview and data structures

For this method, the grid is dened by cubic grid cells (rather than nodes). The triangulated objectsare set into the domain independently of the grid cells. Cells completely inside the object are markedas obstacle cells, cells that are cut by the object become noncubic uid cells. The volume of a cellresembles the volume of the cubic uncut cell (usually 1) reduced by the intersecting volume withthe objects. The surface of an object is dened by its facets Sα with area Aα and surface normal~nα. Grid nodes ~x are placed in the center of a cubic cell, which has size ∆x = ∆y = ∆z = 1. Themass, which is usually assumed to be located in the grid node, is now considered to be uniformlydistributed throughout the cell. ∆V (~x) is the cell's volume and contains a mass that is equal to∑i=1,...,bNi(~x, t) = ∆V (~x)

∑i=1,...b fi(~x, t), where Ni(~x, t) is an amount of mass owing in velocity

13

The volumetric boundary handling method

Figure 3.2: Two-dimensional representation of the volumes Φαi , Vαi , and ∆V (~x). α1,α2 and α3

denote facets of the surface, ~xi and ~x2 are boundary cells.Taken from [3]

direction i at position ~x and fi(~x, t) represents the density distribution of the lattice-Boltzmannscheme. b is equal to the number of velocity directions (19 in this thesis). How these quantitieswere calculated in this thesis will be presented in chapter 4.

The method can be divided into ve steps, which have to be carried out for each time step.Steps 3-5 are only needed if the objects are moving. [3]

(1) Calculation of the geometrical quantities ∆V (~x, t), Φαi (t), V αi (~x, t), and ~nα(t). If the objectsare not moving, these quantities only have to be computed once. Especially because of thecomputation of V αi (~x, t), this saves a considerable amount of time (see Chapter 5).

(2) Calculation of the ow eld for xed objects using equation 3.1.

(3) The term Bi(~x + ~ci∆t, t) is added to the mass distribution of the boundary cells to establishthe no-slip boundary condition for moving surfaces.

(4) The object is moved over a distance of ∆~x = ~ub(t)∆t.

(5) Calculation of the nal mass distribution Ni(~x, t + ∆t) in the boundary cells according to theequations (3.14), (3.15), and (3.16).

3.2. No-slip boundary condition for xed surfaces

In this section a method is presented to establish the no-slip boundary condition for xed objectsaccording to the denitions, which were given before. The idea of this method, as described byChen et al., is to enforce the no-slip boundary condition by applying a modied bounce-back rulebased on the denition of the surface. A proportion of mass is considered to be moving towardsa facet Sα. When this mass moves with velocity ~ci and hits the surface, it must move within aparallelepiped, emanating from the facet Sα in direction i∗ (with ~ci∗ ≡ −~ci). This is illustrated inFigure 3.2. The parallelepiped's volume Φαi is equal to |~ci∗ · ~nα|Aα∆t = |~ci · ~nα|Aα∆t. The massmoving within the parallelepiped may originate from dierent cells, since it may intersect several

14

The volumetric boundary handling method

grid cells. The volume of the intersection of a parallelepiped and a grid cell V αi (~x) [= V αi∗ (~x)] hasto be calculated for two reasons: Firstly, the proportion of V αi (~x) and the volume of a grid cell ~xdetermines the amount of mass originating from this cell and hitting the surface Sα in direction i.The rest is not reected and ows undisturbed into the next uid cell. Secondly, the proportionof V αi (~x) and the parallelepiped volume determines the amount of the reected mass that will owinto cell ~x. With the above denitions, an adjusted lattice-Boltzmann equation for boundary cellscan be derived:

Ni(~x+ ~ci∆t, t+ ∆t) = Pundisti (~x)N′

i (~x, t) +Qi(~x+ ~ci∆t, t). (3.1)

Pundisti (~x) denotes the fraction of mass that moves undisturbed without hitting the surface, N′

i (~x, t) ≡Ni(~x, t) + Ωi(~x, t) is the right-hand side of the original lattice-Boltzmann equation (compare withequation 2.7) and Qi(~x + ~ci∆t, t) represents the mass that is reected from the surface and ar-rives in cell ~x + ~ci∆t. The "normal" lattice-Boltzmann equation is recovered, when no mass hitsthe surface, that is to say when Pundisti (~x) = 1 and, since no mass is reected form the surface,Qi(~x+ ~ci∆t, t) = 0.

The undisturbed fraction of mass

Pundisti (~x) = 1− P disti (~x) (~ci · ~nα < 0) (3.2)

can be determined by calculating the disturbed fraction of mass

P disti (~x) =∑α

V αi∗ (~x)

∆V (~x)≡∑α

Pαi (~x) (~ci · ~nα < 0). (3.3)

P disti (~x) is the fraction of mass located in cell ~x that moves in direction i and hits any facet Sα ofthe object. Pαi (~x) denotes the proportion of mass originating from cell ~x, owing in direction i andhitting facet Sα.

To determine Qi(~x+ ~ci∆t, t), the reected mass Γout,αi (t) of all facets Sα in direction i owing

into cell ~x has to be added.V αi (~x+~ci∆t)

Φαirepresents the proportion of mass that is reected by facet

Sα in direction i and arriving in cell ~x. It is assumed that the reected mass is uniformly distributedin the parallelepiped with volume Φαi . The whole equation reads

Qi(~x+ ~ci∆t, t) =∑α

V αi (~x+ ~ci∆t)

ΦαiΓout,αi (t) (~ci · ~nα > 0). (3.4)

To calculate the reected mass, for the case of no-slip boundary condition at the surface, thebounce-back rule can be applied. Since the mass is reected back in the opposite direction i∗, wecan simply set

Γout,αi (t) = Γin,αi∗ (t). (3.5)

For the calculation of the total incoming mass per facet Sα, Pαi (~x) can be used:

Γin,αi∗ (t) =∑~x

Pαi∗(~x)N′

i∗(~x, t) (~ci∗ · ~nα < 0). (3.6)

All surrounding uid cells within the diameter of two cell sizes around the facet have to be consid-ered. [3]

3.3. Movement

To achieve the no-slip boundary condition for moving surfaces, extra work has to be done. Ladd[1, 12] used a technique in which he transferred an extra amount of mass proportional to theobstacle velocity ~ub across the surface. In order to conserve mass, this addition or subtractionof mass has to be balanced in some way. For staircase shaped objects internal uid was usedto establish mass conservation. In case of freely moving low-density objects, however, this maycause stability problems. By considering the surface to be closed, Aidun et al. [13] could exclude

15

The volumetric boundary handling method

the internal uid with no signicant global mass change in the computational domain. Aidun etal., have also proposed a technique to determine the mass distribution on appearing uid nodesthat were formerly covered by the object. Equation 3.1 has to be extended to cope with movingobjects. Other equations deal with the changing volume of boundary cells as well as appearingand disappearing cells. In these cells, mass must be properly adjusted in order to avoid unphysicaldensity uctuations around the object.

3.3.1. Modication of the propagation rule

Equation 3.1 is adjusted according to the method of Ladd [1] for moving staircase shaped surfaces,in order to establish the no-slip boundary condition. Firstly, the method of Ladd will be describedbriey.

The surface is placed exactly in between two grid nodes. During the propagation step, extra massis transferred across the surface of the object to or from a grid node inside the object, additionallyto the mass that is reected into the uid. On the macroscopic level, the no-slip boundary conditionis established at the surface when the transferred amount of mass is proportional to the surfacevelocity ~ub. By introducing uid grid nodes throughout the entire object and by applying thisprocedure also for the grid nodes inside the object, mass is conserved. Ladd's modied propagationrule for grid nodes adjacent to the suface inside and outside the object is given as

fi(~x+ ~ci∆t, t+ ∆t) = fi∗(~x+ ~ci∆t, t+) + 2tp,iρ(~x, t)(~ub · ~ci)/c2s (3.7)

fi∗(~x, t+ ∆t) = fi(~x, t+)− 2tp,iρ(~x, t)(~ub · ~ci∗)/c2s (3.8)

where cs = 1/√

3 denotes the lattice speed of sound (or rather information), a lattice dependentquantity. tp,i represents a direction dependent weight factor related to the equilibrium distributionand t+ indicates the moment after the collision and before the propagation step.

Equation 3.1 can be modied analogous to the method of Ladd so that the velocity ~ub at thesurface is recovered. A term Bi(~x+ ~ci∆t, t) is added in analogy to 2tp,iρ(~x, t)(~ub · ~ci)/c2s:

Ni(~x+ ~ci∆t, t∗) = Pundisti (~x)N

′

i (~x, t) +Qi(~x+ ~ci∆t, t) +Bi(~x+ ~ci∆t, t). (3.9)

The modied equation represents the collision and propagation steps during a time shift t → t∗,where t∗ denotes the moment before the surface is moved to a new position. An extra amount ofmass must be added to (or removed from) boundary cells in order to enforce a velocity ~ub(t) at afacet Sα. This extra mass, originating from all contributing facets to cell ~x+ ~ci∆t, is equal to

Bi(~x+ ~ci∆t, t) =∑α

∆Γout,αi (~x+ ~ci∆t, t) [~ci · ~nα(t) > 0]. (3.10)

∆Γout,αi (~x+ ~ci∆t, t) is an extra amount of mass added to cell ~x + ~ci∆t and originating from facetα in direction i. It is proportional to ~ub(t) and the volume fraction V αi (~x, t)/∆V (~x, t) and can becalculated as follows:

∆Γout,αi (~x, t) =2tp,i

V αi (~x,t)∆V (~x,t)M(~x, t∗)[~ub(t) · ~ci]

c2s[~ci · ~nα(t) > 0], (3.11)

with M(~x, t∗) =∑iNi(~x, t

∗).

According to Aidun et al. [13], in equation 3.11 the total mass M(~x, t∗) in cell ~x on t = t∗ isused and reads

M(~x, t∗) =M(~x, t∗)

1− 2∑α

∑i∈~ci·~nα(t)>0V αi (~x, t)/∆V (~x, t)tp,i[~ub(t) · ~ci]/c2s

, (3.12)

where M(~x, t∗) [=∑iNi(~x, t

∗)] represents the total mass in cell ~x after the collision and prop-agation steps but without the extra mass term Bi(~x+~ci∆t, t), the denominator corresponds to theextra mass term Bi(~x+ ~ci∆t, t).

16

The volumetric boundary handling method

The net ux of momentum and therefore the net forces on each facet Sα, needed for the calcu-lation of movement and torque, can be calculated from the mass distribution in the boundary cells,which follows

~Fα(t) =1

∆tAα

[ ∑i∈~ci·~nα(t)≤0

~ciΓin,αi (t)−

∑i∈~ci·~nα(t)>0

~ci[Γout,αi (t) + ∆Γout,αi (i)]

]. (3.13)

3.3.2. Treatment of changing cell sizes

On t = t∗, after the collision and propagation steps, the objects are moved over a nite distance∆~x = ~ub(t)∆t. Due to this shift, three issues have to be considered with respect to the mass balancein the boundary cells:

(i) The boundary cell volume may change.

(ii) Cells (and thus mass) may disappear, new cells may appear.

(iii) The addition of Bi(~x+~ci∆t, t) is, contrary to the method of Ladd, not balanced by a grid cellwithin the object.

At rst, we deal with cells of which the volume has changed due to the movement of the object. Inorder to avoid substantial unphysical density uctuations (and therefore pressure uctuations), themass of these cells has to be adjusted in such way that the density in the cells is not altered by thediscrete displacement of the objects. Therefore

Ni(~x, t+ ∆t) =∆V (~x, t+ ∆t)

∆V (~x, t)Ni(~x, t

∗). (3.14)

Furthermore, new cells may appear and old cells may disappear. Following Aidun et al. [13],new cells are lled with the equilibrium mass distribution, based on the averaged density of thesurrounding cells and the surface velocity ~ub(t). Hence

Ni(~xfluid, t+ ∆t) = Neqi (~xfluid, t+ ∆t). (3.15)

Since the physical state of the uid close to the surface is far from equilibrium, this could result insmall physical errors. Even so, Aidun et al. found that using the equilibrium distribution does notlead to signicant nonphysical uctuations, although staircase shaped surfaces were used. Theseuctuations are expected to be even smaller when using the volumetric method, as the volume ofnewly appearing cells is very small. This implies that the contribution to the volumetric bounce-back process of these cells is very small. The nonphysical eects should die away quickly after afew time steps. The mass of disappearing cells is set to zero,

Ni(~xobject, t+ ∆t) = 0. (3.16)

Lastly, cells inside the object are not taken into account, as they are in the method of Ladd (3.7,3.8). Mass in the computational domain is not a priori conserved globally, since mass is addedto (or removed from) boundary cells outside the surface according to equation 3.10, which is notbalanced by an inner grid cell. Mass is removed and added from boundary cells, depending on theposition of the boundary cells with respect to the orientation of the surface. Considering closedsurfaces, the global mass change is very small. The mass added to one side is almost equal to themass removed from the other side, as long as density dierences are small around the object. Testshave shown that applying equations (3.9), (3.14), (3.15), and (3.16) does not produce a signicantextra amount of mass. [3]

17

4. Implementation

In this chapter, two implementation details will be discussed. Firstly, a representation for theobjects and the uid cells has to be found. This data structure must be capable of Boolean setoperations such as dierence and intersection. Ideally, the intersections can be computed fastbecause ten-thousands are needed in each time step for every single sphere. The second problemis the volume calculation. After subtraction of the objects, uid cells can have arbitrary shape;they may not even have a triangular faceted shape. Therefore, a method capable of calculating thevolume of arbitrarily shaped objects is needed.

4.1. Object representation using Nef Polyhedra

For the representation of uid cells and parallelepipeds, the data type Nef_Polyhedron of the Com-putational Geometry Algorithms Library (CGAL, pronounce "seagull") was used. In this sectionthe structure and theoretical background of Nef Polyhedra, which were introduced by Walter Nefin 1978, will be explained.

4.1.1. Introduction

Two major representation schemes are used in solid modelling, boundary representations (B-rep)and constructive solid geometry (CSG).

A B-rep describes the geometric properties of all lower-dimensional features and the incidencestructure of the boundary of a solid body. To decide between the interior and exterior, surfaces areoriented.

In CSG, a solid is represented as a set of primitive objects, such as blocks, cylinders, prisms ortoruses. Instead of evaluating the Boolean operations, objects are represented implicitly by a treestructure. Primitive objects are represented by leaves. Boolean operations or rigid motions, e.g.translation or rotation, are represented by interior nodes. Algorithms on such a CSG-tree use theprimitive objects to evaluate properties and to propagate the result by means of the tree structure.

The types of representable objects in a CSG are normally restricted by the choice of the primitivesolids. A B-rep is usually limited both by the connectivity structure that is allowed and the choicefor the geometry of the supporting edge curves and the supporting surfaces for surface patches.Under set operations, a B-rep is not always closed. The class of orientable (compare Moebius strip)two-manifold objects (i.e. edges have at most two neighbouring facets) is a popular example ofsurfaces commonly used for B-reps. This class is not closed under Boolean set operations as can beseen in Figure 4.1. The object was generated by applying Boolean set operations on several cubes,which are orientable two-manifold objects. The edge connecting the "roof" with the cube and thevertices bounding the tunnel are non-manifold situations. Manifold solids have the property thata small sphere around any point on the boundary is divided into two pieces, one inside and oneoutside the object. Non-manifold objects violate this rule.

In the three dimensional Nef polyhedron implementation of CGAL, a B-rep data structure isused that is closed under Boolean operations and with all their generality. It can work with setintersection, set dierence and many others by starting from half-spaces (and also directly fromoriented 2-manifolds). That is to say, that a CSG-tree with half-spaces as primitives is evaluated,which can be converted into a B-rep representation.

18

Implementation

Figure 4.1: A Nef polyhedron with an unselected boundary in the tunnel, non-manifold edges, adangling facet and two isolated vertices. Taken from [14].

Two data structures are used: The rst represents the local neighbourhoods of vertices, whichalready is a full description of the geometry. The second connects these neighbourhoods up to aglobal data structure with volumes, facets and edges. Nef polyhedra can be read from and storedto les.

4.1.2. Theory

Denition 4.1.1. A Nef-polyhedron in dimension d is a point set P ⊆ Rd generated from a nitenumber of open half-spaces by set complement and set intersection operations.

Dierence (\), symmetric dierence (∆) and set union (∪) can be reduced to complement (!)and intersection (∩) as follows:

P1 ∪ P2 =!(!P1∩!P2) (4.1)

P1 \ P2 = P1∩!P2 (4.2)

P1∆P2 = (P1 \ P2) ∪ (P2 \ P1) =!(!(P1∩!P2)∩!(P2∩!P1)) (4.3)

Topological operations such as interior, exterior, boundary, closure, and regularization can alsobe modelled for Nef polyhedra, since set complement changes between open and closed half-spaces.Local pyramids are a characterization of the local space around a point and a face is dened as anequivalence class of it.

Denition 4.1.2. A point set K ⊆ Rd is called a cone with apex 0, if K = R+K (i.e., ∀p ∈K,∀λ > 0 : λp ∈ K) and it is called a cone with apex x, x ∈ Rd, if K = x+ R+(K − x). A cone Kis called a pyramid if K is a polyhedron.

Let x ∈ Rd, and P ∈ R+ be a polyhedron. "There is a neighbourhood U0(x) of x such that thepyramid Q := x+R+((P ∩U(x))−x) is the same for all neighbourhoods U(x) ⊆ U0(x). Q is calledthe local pyramid of P in x and denoted Pyrp(x)[15]."

Denition 4.1.3. Let P ∈ Rd be a polyhedron and x, y ∈ Rd be two points. We dene an equivalencerelation x ∼ y i pyrp(x) = Pyrp(y). The equivalence classes of ∼ are the faces of P. The dimensionof a face s is the dimension of its ane hull, dims := dim affs.

19

Implementation

That means, a face s of P is a maximal non-empty subset of Rd so that all of its points have thesame local pyramid Q dened as Pyrp(s).

Only two full-dimensional faces are possible, those with the total space Rd as its local pyramidand the one whose local pyramid is the empty set. All lower-dimensional faces, which don't haveto be connected, form a boundary of the polyhedron. Usually zero-dimensional faces are calledvertices, one-dimensional faces edges and in case of polyhedra in space, two-dimensional faces arecalled facets. Full-dimensional faces are then referred to as volumes. Faces are dened as relativeopen sets, i.e. an edge does not contain its end-vertices, for example. [15] (Denitions taken from [15].)

Figure 4.2: 2-dimensional example of a Nefpolyhderon. Thin edges and white nodes arenot part of the polyhedron. Taken from [14]

Figure 4.3: Sketches of the local pyramids ofexample Fig. 4.2. The shaded region in a smalldisc depicts the local pyramids in their relativeneighbourhood. Taken from [14]

Example 4.1.1. For illustration an example in the plane is illustrated. Following half-spaces aregiven:

h1 : y ≥ 0, h2 : x− y ≥ 0, h3 : x+ y ≤ 3, h4 : x− y ≥ 1, h5x+ y ≥ 2. (4.4)

The polyhedron is dened as P := (h1 ∩ h2 ∩ h3)− (h4 ∩ h5).

Figure 4.2 illustrates this polyhedron with its partially open boundary, vertices ν4, ν5, ν6, andedges e4, e5 are not part of P. Pyrp(f1) = ∅ and Pyrp(f2) = R2 are the local pyramids for thefaces. The closed half-space h2 for the edge e1, Pyrp(e1) = h2, and the open half-space that is thecomplement of h4 for the edge e5, Pyrp(e5) = (x, y)|x− y| < 1 are examples for the local pyramidsof edges. The two disconnected parts of e3 have the same local pyramid Pyrp(e3) = h1, eventhough, they will be represented separately. Figure 4.3 shows all local pyramids for this example.

Figure 4.4: 2-dimensional example of a Nef polyhderon. Thin edges and white nodes are not partof the polyhedron. Taken from [15]

By conceptually intersecting the local neighbourhood with a small ε-sphere, local pyramids ofvertices are represented. This forms, together with the set-selection mark for vertices, edges, loops

20

Implementation

(a circuit of edges bounding a face) and faces, a two dimensional Nef polyhedron embedded inthe sphere (see Fig. 4.4 and Fig. 4.5). After adding the set-selection mark for the vertex, theresulting structure is called the sphere map of the vertices. The prex s is used to distinguish theelements of the sphere map from the three-dimensional elements. Sphere maps for all vertices area full representation of the polyhedron, but since the sphere maps are not easily accessible, thedata structure is complemented with more explicit representations of all the faces and incidencesbetween them.

Figure 4.5: Sketches of the local pyramids of example Fig. 4.2. The shaded region in a small discdepicts the local pyramids in their relative neighbourhood. Taken from [15]

Finally, the dierent components of the CGAL Nef polyhedron shall be outlined as follows:

edges: Two oppositely oriented edges for each edge are stored; an additional pointer pointsfrom one oriented edge to its opposite edge. Such oriented edges can be dened using sverticesin a sphere map. One svertex is linked with the corresponding opposite svertex in the othersphere map

edge uses: In a non-manifold situation, an edge can have many incident facets. For each ofthe two orientations of a facet, one edge-use for each incident facet is introduced. An edge-usepoints to its oriented facet and its corresponding oriented edge. An edge-use can be identiedwith an oriented sedge in the sphere map.

facets: The oriented facets are stored as boundary cycles of oriented edge-uses. Holes inthe facet are represented by a distinguished outer boundary cycle and several inner boundarycycles. Boundary cycles are linked in one direction, the other traversal direction can beaccessed by switching to the oppositely oriented facet, or rather by using the opposite edge-use.

shells: The dierent connected components of the volume boundary are called shells. A shellconsists of a connected set of vertices, edges, and facets incident to this volume. The radialorder formed by the facets around an edge is captured in the radial order of sedges around ansvertex in the sphere map. A shell can be traced from one entry element with a graph searchusing this information. For this graph traversal, a visitor design pattern is provided.

volumes: A volume is dened by a set of shells. One outer shell contains the volume andseveral (or maybe none) inner shells separate voids, which are excluded from the volume.

4.2. Volume calculation

In the volumetric method, volumes of parallelepipeds, uid cells and the intersection of these twohave to be computed. To calculate these volumes, the method of Brian Mirtich [16] has been used.

21

Implementation

It computes the mass integrals of uniform density polyhedra, which can be converted into volumeintegrals under this assumption. The complex integrals are computed by successively reducing themto simpler integrals. It is ecient, since it has a linear complexity in the number of vertices, edges,or facets, and is designed to minimize the numerical errors. All theorems and proves in this sectionare cited from [16].

4.2.1. Volume integral

The volume of a polyhedron can be calculated via the following volume integral:

V =

∫ν

1dV, (4.5)

where ν is the domain of integration. The divergence theorem is used to reduce the volume integralto a sum of surface integrals over all the facets of the polyhedron. These surface integrals areevaluated as integrals over a planar projection of the surface. Green's theorem reduces the planarintegration to a sum of line integrals around the edges of the polygon for polygons in the plane.These line integrals can be evaluated directly from the coordinates of the projected vertices of theoriginal polyhedron. Image 4.6 illustrates the dierent steps of the method.

Figure 4.6: To compute volumes, complicated integrals are decomposed into successively simplerones. The values from the simplest integrals are combined and propagated back to compute thecomplex ones. Taken from [16]

4.2.2. Reduction to surface integrals

The divergence theorem helps to reduce a polyhedral volume integral to a sum of integrals over itstwo-dimensional facets [17]:

Theorem 4.2.1. (Divergence)Let ν be a region in space bounded by the surface ∂ν. Let n denotethe exterior normal of ν along its boundary ∂ν. Then∫

ν

∇ · FdV =

∫∂ν

F · n|dA (4.6)

for any vector eld F dened on ν.

The right-hand side of equation (4.6) can be broken up into a summation over facets of constantnormal for a polyhedral volume so that n can be taken out of the integral. The resulting integrals,e.g.

∫νxdV , do not immediately appear to be of the form in the theorem. However, there can be

found many vector elds whose divergence is the function x such as F (x, y, z) = (12x

2, 0, 0)T . Since

22

Implementation

two of its components are identically zero, the dot product on the right-hand side of Eq. (4.6)becomes a scalar multiplication. The new volume equation becomes:

V =∑F∈∂ν

n

∫FxdA (4.7)

4.2.3. Reduction to projection integrals

Starting with a region in the plane, Green's theorem reduces an integral over a planar region to anintegral around its one-dimensional boundary. Therefore the planar faces of the polyhedron haveto be projected onto one of the coordinate planes. The following theorem relates integrations overthe original face to integrations over the projection.

Figure 4.7: The size of the facet's projected shadow in the α − β plane is maximized by choosingthe α− β− γ axes, which are right-handed permutations of the x-y-z axes, accordingly. Taken from [16]

Theorem 4.2.2. Let F be a polygonal region in α− β − γ space, with surface normal n, and lyingin the plane

nαα+ nββ + nγγ + w = 0. (4.8)

Let Π be the projection of F into the α− β plane. Then∫Ff(α, β, γ)dA =

1

|nγ |

∫Π

f(α, β, h(α, β))dα dβ, (4.9)

where

h(α, β) = − 1

nγ(nαα+ nββ + w). (4.10)

Proof: The points (α, β, h(α, β)) lie in the plane of F , so F is the graph of h over Π. We use:

∫Ff(α, β, γ)dA =

∫Π

f(α, β, h(α, β))

√1 +

(∂h

∂α

)2

+

(∂h

∂β

)2

dα dβ. (4.11)

23

Implementation

For h, the square root in the integrand reduces to |nγ |−1; it follows the theorem.

With the help of this theorem we can reduce the integral of a polynomial in α, β, and γ overthe facet F to the integral of a polynomial in α and β over the projected region Π. The constantw can be computed from 4.8: w = −n · p, where p is any point on the facet F . The α − β − γcoordinates are always chosen as a right-handed permutation of the x-y-z coordinates such that |n|is maximized (see Figure 4.7). This maximizes the area of the projected shadow in the α− β plane

and therefore reduces numerical errors. There can always be found a choice such that |nγ | ≥√

3−1.

The volume integral can be found by computing the following three integrals:∫Fα dA (4.12)

∫Fβ dA (4.13)∫

Fγ dA (4.14)

These facet integrals can all be reduced to integrals over the projection region Π. With

πf =

∫Π

f dA (4.15)

the complete set of face integrals reads:∫F

α dA = |nγ |−1πα (4.16)

∫F

β dA = |nγ |−1πβ (4.17)∫F

γ dA = −|nγ |−1n−1γ (nαπα + nβπβ + wπ1) (4.18)

4.2.4. Reduction to line integrals

Figure 4.8: Notation for the computation of a projection integral as a sum of line integrals. Taken

from [16]

Lastly an integral over a polygonal projection region in the α − β plane is reduced to a sumof line integrals over the edges enclosing the region. The following notation is adopted (see also

24

Implementation

Figure 4.8): E1 through EK name the edges of Π. Edge Ee represents the directed line segment from(αe, βe) to (αe+1, βe+1), ∆αe = αe+1 − αe, and ∆βe = βe+1 − βe [here (αK+1, βK+1) = (α1, β1)].Edge Ee has the exterior unit normal me and length Le.

The nal integration reduction is provided by Green's theorem [17]:

Theorem 4.2.3. (Green's) Let Π be a region in the plane bounded by the single curve ∂Π. Let mdenote the exterior normal along the boundary. Then∫

Π

∇ ·H dA =

∮∂Π

H · m ds (4.19)

for any vector eld H dened on Π, where the line integral traverses the boundary counter-clockwise.

Green's theorem, a two dimensional version of the divergence theorem, again can be simpliedfor our case. The right hand side of equation 4.19 may be broken into a summation over edges ofconstant normals, because Π is polygonal, and the dot product becomes a scalar multiplication ifH is chosen so that one component is identically zero. The integrals of equation (4.16) and (4.17)are needed. By choosing H = ( 1

2α2, 0)T , and applying Green's theorem to the polygonal region Π,

the rst case reads: ∫Π

α dA =1

2

K∑e=1

meα

∫Eeα(s)2 ds. (4.20)

The integration variable s in the right hand integral is the length of the arc and runs from 0 tothe length of the edge Le. The α-coordinate of the point on the edge that is a distance s from thestarting point is called α(s). One can change integration variables by letting the variable λ be s/Le(ds = Ledλ) to get ∫

Π

α dA =1

2

K∑e=1

meαLe

∫ 1

0

α(Leλ)2 dλ. (4.21)

Let meαLe = ±∆βe, where plus or minus have to be used, depending on whether the vertices Πare indexed in counter-clockwise or clockwise order. By convention, it is assumed that the verticesof the original facet F are indexed in counter-clockwise order. That means, the vertices of Π haveto be indexed in counter-clockwise order exactly when the sign of nγ is positive (see Figure 4.7).Hence, meαLe = (sgn (nγ))∆βe, and∫

Π

α dA =sgn nγ

2

K∑e=1

∆βe

∫ 1

0

α(Leλ)2 dλ. (4.22)

Analogously one can derive ∫Π

β dA =sgnnγ

2

K∑e=1

∆αe

∫ 1

0

β(Leλ)2 dλ. (4.23)

4.2.5. Computation of line integrals from vertex coordinates

The volume integral has been successively reduced to face integrals, projection integrals, and nallyline integrals. With the help of the following theorem the latter can be directly evaluated in termsof vertex coordinates.

Theorem 4.2.4. Let Le be the length of the directed line segment from (αe, β3) to (αe+1, βb+1).Let α(s) and β(s) be the α− and β−coordinates of the point on this segment a distance s from thestarting point. Then for non-negative integers p and q,

∫ 1

0

α(Leλ)pβ(Leλ)qdλ =1

p+ q + 1

p∑i=0

q∑j=0

(pi

)(qj

)(p+qi+j

) αie+1αp−ie βje+1β

q−je . (4.24)

25

Implementation

Proof: Denoting the integral on the left hand side of (4.24) by I,

I =

∫ 1

0

[(1− λ)αe + λαe+1]p[(1− λ)βe + λβe+1]q dλ (4.25)

=

∫ 1

0

[p∑i=0

Bpi (λ)αie+1αp−ie

] q∑j=0

Bqj (λ)βje+1βq−je

dλ, (4.26)

where the B's are Bernstein Polynomials:

Bnk (λ) =

(n

k

)λk(1− λ)n−k. (4.27)

There are two important properties of these polynomials:

Bpi (λ)Bqj (λ) =

(pi

)(qj

)(p+qi+j

) Bp+qi+j (λ), (4.28)

∫ 1

0

Bnk (λ)dλ =1

n+ 1. (4.29)

Expanding the product in (4.26) and applying (4.28) gives

I =

p∑i=0

q∑j=0

(pi

)(qj

)(p+qi+j

) αie+1αp−ie βje+1β

p−je

∫ 1

0

Bp+qi+j (λ) dλ. (4.30)

Evaluating of the integrals using (4.29) proves the theorem.

The line integrals from the previous subsection represent special cases of Theorem (4.2.4), withp and q set to 0. That is to say ∫ 1

0

α dλ =1

2

1∑i=0

αie+1α1−ie (4.31)

∫ 1

0

β dλ =1

2

1∑j=0

βje+1β1−je (4.32)

The required projection integrals in terms of the coordinates of the projection vertices result afterthe substitution of (4.31) and (4.32) into (4.22) and (4.23):

π1 =

∫Π

1 dA = +sgn(nγ)

2

K∑e=1

∆βe(αe+1 + αe) (4.33)

πα =

∫Π

α dA = +sgn(nγ)

6

K∑e=1

∆βe(α2e+1 + αe+1αe + α2

e) (4.34)

πβ =

∫Π

β dA = −sgn(nγ)

6

K∑e=1

∆αe(β2e+1 + βe+1βe + β2

e ) (4.35)

In Appendix A a pseudo code is given for calculating all the volume integrals discussed by BrianMirtich.

26

5. Simulation

Figure 5.1: Velocity eld for a simulation without object after 10000 time steps and in-/outowvelocity (0.002, 0, 0).

Figure 5.2: Velocity at a horizontal line of Fig-ure 5.1 at position y = z = 32.

Figure 5.3: Velocity at a vertical line of Figure5.1 at position x = y = 32.

Rohde's method was implemented as a new boundary condition for the simulation frameworkwaLBerla (widely applicable Lattice Boltzmann solver from Erlangen). Its original purpose was

27

Simulation

the simulation of uid scenarios with the Lattice-Boltzmann method. By now it is not limited to theLBM, but also suitable for a wide range of applications based on structured grids. An example wouldbe an ecient multigrid solver for partial dierential equations. It aims at physical correctness andhigh performance, combined with easy adaptability and extensibility. [18] As mentioned before,for intersections and dierences of volumes the library CGAL was used (see section 4.1. Volumecalculations were carried out with in Section 4.2 discussed method proposed by Brian Mirtich. Thesimulations were done dimensionlessly. The domain had a size of 64× 64× 64 grid cells with length1. ρ was set to 1, τ was also 1. A xed object, cube or sphere, was placed in the middle of thedomain and mass conservation, grid dependence and the forces acting on the body were studied.

No simulations for moving objects were carried out because of speed issues. The method is veryslow compared with other boundary conditions. The volume calculation is very ecient and canbe done in linear time in the number of facets. CGAL, however, is known for its stability, butnot for its fast algorithms. The calculation of V αi is the most computationally extensive volumecalculation. Therefore, a short example of its calculation shall illustrate the problem:

For the calculation of V αi , all parallelepipeds with (~ci ·~nα > 0) have to be cut with all surroundinguid cells. A sphere with 80 facets was used. There are up to 13 valid parallelepipeds and, usinga radius of two and facets smaller than a cell, we can assume 43 = 64 cells. This amounts to80 · 13 · 64 = 66, 560 intersections. CGAL is capable of 3000-6000 intersections a minute. Inour example, this would lead to 11-22 minutes per time step for the calculation of V αi . In mysimulation, with a sphere of radius 5, the calculation of all intersections took 15 minutes. Since theparallelepiped and the surrounding uid cells do not change for a xed object, these calculationsonly have to be done once. The code was written in C++. The simulations were carried outsequentially on an Intel Core i7-2600 3.4 Ghz processor with 8 GB of memory capacity. All imagesand graphs in this chapter were made with Paraview, which is innately supported by waLBerla.

5.1. Empty simulation

For comparison reasons, one simulation was carried out without an object and therefore withoutany use of the volumetric boundary condition. To induce a velocity, an inow at the west walland an outow at the east wall was implemented. Two velocities (0.002, 0, 0) and (0.001, 0, 0)were tested. No-slip boundary condition was set at the top and bottom walls, the domain wasperiodic in y-direction. Figure 5.1 shows the velocity eld of a plane at position y = 32. Figures5.2 and 5.3 show the velocity distribution on a horizontal (green) and vertical (red) line. Due tothe no-slip boundary condition, the velocity at the bottom and the top is zero. In the middle, thevelocity increases to balance the zero velocity at the borders. The mass is equal in each column.As expected the mass stays constant at 643 = 262144 throughout the whole simulation.

5.2. Simulation of a cube

A cube with edge length 10 was set at dierent positions in the middle of the domain. At rstthe mass conservation was monitored. Three dierent positions have been tested to investigategrid dependence. At rst the cube was placed in the center of the domain with the position of itsmidpoint at (32, 32, 32) (position 1). The cube is aligned with the grid, i.e. grid cells are eitherlocated completely inside or completely outside of the cube. In the second simulation the cubewas placed at (31.5, 31.5, 31.5). The consequence is that all near obstacle cells are cut in halfexcept for the cells in the corners of the cube, they are one quarter solid and three quarters uid.Lastly, the cube was set randomly at (32.4, 31.7, 33.1), cutting cells with dierent ratios. Figure5.4 shows the mass distribution for the aligned cube. Dark red means mass of one, dark blue zeromass. It is equally distributed throughout the whole domain during all time steps. Inside the cubethe mass is set to 0. Only in the beginning of the simulation, when the velocity is induced, veryslight uctuations could be monitored. Figure 5.5 shows the mass distribution for case two. Themass is set to one half or three quarters for boundary cells according to their volume. It has tobe mentioned that neither waLBerla nor Paraview are capable of representing triangulated meshes.

28

Simulation

Figure 5.4: Mass distribution for an alignedcube.

Figure 5.5: Mass distribution for a cube cuttinguid cells in half.

Figure 5.6: Velocity eld for a simulation with a cube of edge length 10 positioned at (32, 32, 32)and induced velocity of (0.002, 0, 0).

That is why the objects seem to be approximated by cubes in the pictures. During the boundaryhandling function, however, their actual shape and volume are used.

For all positions the mass stays unchanged at 643 − 103 = 261144 throughout the simulation.The mass around the cube, measured in a bounding box with edge length 15, uctuates slightly byan amount of ±1 in total within the rst time steps and stays unchanged at 2374.95 for the alignedcase, 2375 for case two and 2374.97 for the last case. Figure 5.6 shows the velocity distributionfor a cube at position 1. Same as in the previous section, plots for the velocity at a horizontaland vertical line for case 1 are shown in Figure 5.7 and 5.8. Images for the other positions canbe found in Appendix B. Again the velocity at the top and the bottom is zero because the no-slipboundary condition is applied. At the west side of the cube, particles are hitting the surface andbeing reected in the opposite direction. This leads to a lower uid velocity the closer the distance

29

Simulation

Figure 5.7: Velocity at a horizontal of Figure5.6.

Figure 5.8: Velocity at a vertical line of Figure5.6.

is to the surface. The same happens at the top and at the bottom of the object, but since the uidows from west to east, fewer particles are hitting the surface so that the eect is weaker. AS theeast or rear facet of the cube is shaded by it, there is no ow at this facet. Between the boundariesthe ow again is fastest.

In addition to the mass, the force at each facet and the resulting drag force on the objects werecomputed. Table 5.1 compares the forces of a cube at all three positions with an inow velocityof (0.001, 0, 0). In contrast to Rohde's paper, the gross force was used instead of the net force.It can be observed that in the aligned case the opposing facets bottom-top and south-north havecompletely symmetric forces in the opposite direction of their surface normals with a tendencytowards the positive x-direction due to the ow direction. The force on the west wall is slightlyhigher than the force on the east wall, which results in a force in x-direction. The small componentsin y-direction result from round-o errors and can be approximated to 0. The values of the secondand third case dier slightly because the cube is set a little o the center of the domain. The y-and z-component dier from 0 because the cube is drawn towards a line at position y = z = 32.

Position (32, 32, 32) (31.5, 31.5, 31.5) (32.4, 31.7, 33.1)

Bottom (0.002795, 0, 16.667) (0.002871,−4.44 · 10−16, 16.667) (0.002864, 1.69 · 10−7, 16.666)

Top (0.002795, 0,−16.667) (0.002893, 4.44 · 10−16,−16.667) (0.002822, 1.58 · 10−7,−16.666)

South (0.002859, 16.666, 0) (0.002949, 16.666, 1.32 · 10−6) (0.002916, 16.666, 5.47 · 10−7)

North (0.002859,−16.666, 0) (0.002950,−16.666, 1.32 · 10−6) (0.002911,−16.666, 5.56 · 10−7)

East (−16.661,−1.33 · 10−15, 0) (−16.661,−4.00 · 10−15,−1.54 · 10−5) (−16.661,−3.02 · 10−6, 3.98 · 10−5)

West (16.672,−8.88 · 10−16, 0) (16.672, 8.88 · 10−16, 1.81 · 10−5) (16.672, 3.78 · 10−6,−3.84 · 10−5)

Total (0.022259,−2.22 · 10−15, 0) (0.022904,−3.11 · 10−15, 9.38 · 10−6) (0.022673,−4.04 · 10−7, 6.25 · 10−6)

Table 5.1: Forces on a cube with edge length 10 at dierent positions.

5.3. Simulation of a Sphere

A triangulated sphere with 80 facets and radius 5 was placed at (32, 32, 32). A sphere with radius 5has a volume of V = 4

3πr3 ≈ 523. The triangulated object has a volume of 457.337 ( = r ≈ 4.780).

Simulations again have shown no mass change with a constant mass of 643 − 457.337 ≈ 261686.6.The mass in a local bounding box uctuated by ±0.1 in total around 1270.65 during the rst timesteps. Figure 5.9 shows the mass distribution. The mass of the cells around the sphere is smaller

30

Simulation

Figure 5.9: Mass distribution for a sphere.

because their volume is smaller due to the intersection with the sphere. Cells completely insidethe sphere are obstacle cells and have no mass of the uid. Figure 5.10 shows the velocity eldand Figure 5.11 and 5.12 show the corresponding horizontal and vertical line. The velocity eldof the sphere is similar to the one around a cube. However, the uid can ow around the objectmore easily and therefore forms an elliptical shape. An interesting fact is that the velocity is slightlyincreasing before it reaches the object. It increases in the rst place because of the no-slip boundarycondition explained in Section 5.1. As the increase is not observed in the case of the cube, one canconclude that the uid ow is more obstructed by a cube than by a sphere. This is not unexpectedsince volume and surface of the cube are larger and the shape also contributes to this behaviour.The drag force of (0.0146035, 6.10 · 10−14,−3.38 · 10−06) is smaller than the drag force of a cube,which is (0.022259,−2.22 · 10−15, 0). This can be explained by the smaller surface and volume aswell as the aerodynamic shape. Encountering a z-component, however, is unexpected and may bedue to the not completely spherical approximation.

The drag force exerted on a spherical object can be calculated by Stokes' law if the Reynoldsnumber is smaller than 0.1. It reads:

Fd = 6πµrv, (5.1)

where Fd is the drag force, also called Stokes' drag, µ is the dynamic viscosity, r is the radius of thesphere and v is the relative velocity of sphere and uid. [19] Since the sphere is xed, the averagevelocity of the uid can be used. The Reynolds number can be calculated as follows:

Re =inertialforces

viscousforces=ρvL

µ, (5.2)

where ρ is the density of the uid and L the characteristic length of the object. [20] Setting ρ = 1and ν = 1

6 and using the diameter for L, the Reynolds number for this setup is Re = 1·0.001·101/6 =

0.06 < 0.1. With µ = ν · ρ = 16 · 1 = 1

6 , r = 4.780 and v = (0.001, 0, 0) the drag force according toStokes' law amounts to

Fd = 6π1

6· 4.780

0.00100

=

0.01501700

(5.3)

This value is close to the measured value (0.0146035, 6.10 · 10−14,−3.38 · 10−06) of the approxi-mated sphere. It is an error of 2.75% in the x-component and much smaller in the other components.With a higher number of facets the error may be even smaller, but this has yet to be tested.

31

Simulation

Figure 5.10: Velocity eld for a simulation with a sphere with radius 5 positioned at (32, 32, 32).

Figure 5.11: Velocity at a horizontal line of Fig-ure 5.10.

Figure 5.12: Velocity at a vertical line of Figure5.10.

32

6. Conclusion

A new boundary handling function, which uses volumes to compute the amount of reected particles,has been presented. It was successfully implemented in waLBerla and tested with a cube and asphere as xed objects in the ow. Mass conservation could be shown for both cases as well as gridindependence. The drag force on these objects was calculated and the drag force on the spherecompared with Stokes' law. It could be shown that the drag force calculation is correct with adeviation in the third valid digit. The method is suciently fast for xed objects. 10.000 timesteps of the simulation with a sphere took less than 20 minutes, after the initial 15 minutes for thecalculation of all intersections. The code can be easily extended to handle several objects. Whenthe PE physics engine is capable of handling triangulated objects, the volumetric method can becombined with it. At the moment, the objects are stored in a global data structure only neededfor the boundary handling function. Since the method is also made for moving objects, another,faster algorithm for the intersection computation could be implemented in order to use the alreadyexisting functions and extensions necessary for this case. So far waLBerla was only capable ofsimulating primitive objects like a sphere or a cuboid and those composed of these primitives. Thevolumetric method is a new alternative boundary handling function which can be used to simulatebodies with complex geometries and to increase the accuracy of simulations.

33

Bibliography

[1] Ladd, Anthony J. C.: Numerical simulations of particulate suspensions via a discretizedBoltzmann equation. Part1. Theoretical foundation. In: Journal of Fluid Mechanics 271 (1994),S. 285309. doi:10.1017/S0022112094001771

[2] Bouzidi, M'hamed ; Firdaouss, Mouaouia ; Lallemand, Pierre: Momentum transfer ofa Boltzmann-lattice uid with boundaries. In: American Institute of Physics 13 (November2001)

[3] Rohde, M. ; Derksen, J. J. ; Akker, H. E. A. V.: Volumetric method for calculating theow around moving objects in lattice-Boltzmann schemes. In: PHYSICAL REVIEW E 65 (23April 2002)

[4] Iglberger, Klaus: Lattice Boltzmann Simulation of Flow around moving Particles. 3June 2005. Chair of computer science 10, university of Erlangen-Nuremberg, Germany:www10.informatik.uni-erlangen.de

[5] Thuerey, Nils: A Single-phase free-surface Lattice Boltzmann Method. 2 June2003. Chair of computer science 10, university of Erlangen-Nuremberg, Germany:www10.informatik.uni-erlangen.de

[6] Wolf-Gladrow, Dieter A.: Lattice-Gas Cellular Automata and Lattice Boltzmann Models -An Introduction. Berlin Heidelberg : Springer-Verlag, 2000

[7] Haenel, D.: Molekulare Gasdynamik. Berlin Heidelberg : Springer-Verlag, 2004

[8] Chen, S. ; Martinez, D. ; Mei, R.: On boundary conditions in lattice-Boltzmann method.In: Phys. Fluids 8, 2527 (1996)

[9] Filippova, O. ; Haenel, D.: Grid renement for lattice BGK models. In: J. Comput. Phys.147, 219 (1998)

[10] Chen, H. ; Teixeira, C. ; Molvig, K.: Realization of uid boundary conditions via discreteBoltzmann dynamics. In: International Journal of Modern Physics C 9 8, 1281-92 (1998)

[11] Rohde, M. ; Derksen, J. J. ; Akker, H. E. A. V.: Improved bounce-back methods for no-slipwalls in lattice-Boltzmann schemes: Theory and simulations. In: PHYSICAL REVIEW E 67(10 June 2003)

[12] Ladd, Anthony J. C.: in Dynamics: Models and Kinetic Methods for Nonequilibrium ManyBody Systems. Dorbrecht : Kluwer Academic Publishers, 2000

[13] Aidun, C. K. ; Lu, Y. ; Ding, E. J.: Direct analysis of particulate suspensions with inertiausing the discrete Boltzmann equation. In: Journal of Fluid Mechanics 373 (1998), S. 287311

[14] Hachenberger, Peter: Boolean Operations on 3D Selective Nef Complexes: Data Structure,Algorithms, Optimized Implementation, Experiments, and Applications. 2006. Saarbruecken

[15] Hachenberger, Peter ; Kettner, Lutz: Chapter 29: 3D Boolean Operations on NefPolyhedra. http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Nef_3/Chapter_main.html. Version: 9 April 2013

[16] Mirtich, Brian: Fast and Accurate Computation of Polyhedral Mass Properties. In: journalof graphics tools 1, no. 2 (1996)

34

BIBLIOGRAPHY

[17] Stein, Sherman K.: Calculus and Analytic Geometry. New York : McGraw-Hill, Inc., 1982

[18] waLBerla - Short description. http://www.fz-juelich.de/ias/jsc/EN/Expertise/High-Q-Club/waLBerla/_node.html. Version: 2 August 2013

[19] Stokes' law. http://en.wikipedia.org/wiki/Stokes%27_law. Version: 2 June 2013

[20] Reynolds number. http://en.wikipedia.org/wiki/Reynolds_number. Version: 11October 2013 2013

35

List of Figures

1.1 Spheres in liquid Taken from http://2.bp.blogspot.com . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Staircase approximation: The boundary is set exactly between two nodes. Taken from [4] 6

1.3 Curved boundary without approximation. Taken from [4] . . . . . . . . . . . . . . . . . . 6

2.1 D3Q19-model Taken from [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 No-slip boundary condition before and after stream step. Taken from [4] . . . . . . . . . 10

2.3 Free-slip boundary condition before and after stream step.Taken from [4] . . . . . . . . . 10

2.4 Wall distance 0.5 Taken from [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.5 Wall distance <0.5 Taken from [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.6 Wall distance >0.5 Taken from [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.7 Interpolation with wall close to the boundary cell (a) and far from the boundary cell(b). Taken from [2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.1 (a)Triangulated sphere. (b) Facet with normal ~nα. Taken from [3] . . . . . . . . . . . . . 13

3.2 Two-dimensional representation of the volumes Φαi , Vαi , and ∆V (~x). α1,α2 and α3

denote facets of the surface, ~xi and ~x2 are boundary cells.Taken from [3] . . . . . . . . . 14

4.1 A Nef polyhedron with an unselected boundary in the tunnel, non-manifold edges, adangling facet and two isolated vertices. Taken from [14]. . . . . . . . . . . . . . . . . . . 19

4.2 2-dimensional example of a Nef polyhderon. Thin edges and white nodes are notpart of the polyhedron. Taken from [14] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.3 Sketches of the local pyramids of example Fig. 4.2. The shaded region in a smalldisc depicts the local pyramids in their relative neighbourhood. Taken from [14] . . . . . 20

4.4 2-dimensional example of a Nef polyhderon. Thin edges and white nodes are notpart of the polyhedron. Taken from [15] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.5 Sketches of the local pyramids of example Fig. 4.2. The shaded region in a smalldisc depicts the local pyramids in their relative neighbourhood. Taken from [15] . . . . . 21

4.6 To compute volumes, complicated integrals are decomposed into successively simplerones. The values from the simplest integrals are combined and propagated back tocompute the complex ones. Taken from [16] . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.7 The size of the facet's projected shadow in the α−β plane is maximized by choosingthe α−β−γ axes, which are right-handed permutations of the x-y-z axes, accordingly.Taken from [16] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.8 Notation for the computation of a projection integral as a sum of line integrals. Taken

from [16] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.1 Velocity eld for a simulation without object after 10000 time steps and in-/outowvelocity (0.002, 0, 0). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.2 Velocity at a horizontal line of Figure 5.1 at position y = z = 32. . . . . . . . . . . . 27

36

LIST OF FIGURES

5.3 Velocity at a vertical line of Figure 5.1 at position x = y = 32. . . . . . . . . . . . . 27

5.4 Mass distribution for an aligned cube. . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.5 Mass distribution for a cube cutting uid cells in half. . . . . . . . . . . . . . . . . . 29

5.6 Velocity eld for a simulation with a cube of edge length 10 positioned at (32, 32,32) and induced velocity of (0.002, 0, 0). . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.7 Velocity at a horizontal of Figure 5.6. . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.8 Velocity at a vertical line of Figure 5.6. . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.9 Mass distribution for a sphere. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5.10 Velocity eld for a simulation with a sphere with radius 5 positioned at (32, 32, 32). 32

5.11 Velocity at a horizontal line of Figure 5.10. . . . . . . . . . . . . . . . . . . . . . . . 32

5.12 Velocity at a vertical line of Figure 5.10. . . . . . . . . . . . . . . . . . . . . . . . . . 32

A.1 Computes volume integrals for a polyhedron. See section 4.2.1. Taken from [16]. . . . . . 39

A.2 Computes the required surface integrals over a polzhedral face. See section 4.2.2 Taken

from [16]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

A.3 Compute the integrals over a facet projection. See section 4.2.3.Taken from [16]. . . . . . 41

B.1 Velocity eld for a simulation with a cube of edge length 10 positioned at (31.5, 31.5, 31.5). 42

B.2 Velocity eld for a simulation with a cube of edge length 10 positioned at (32.4, 31.7, 33.1). 42

B.3 Velocity at a horizontal line of Figure B.1. . . . . . . . . . . . . . . . . . . . . . . . . 43

B.4 Velocity at a vertical line of Figure B.1. . . . . . . . . . . . . . . . . . . . . . . . . . 44

B.5 Velocity at a horizontal line of Figure B.2. . . . . . . . . . . . . . . . . . . . . . . . . 45

B.6 Velocity at a vertical line of Figure B.2. . . . . . . . . . . . . . . . . . . . . . . . . . 46

37

List of Tables

5.1 Forces on a cube with edge length 10 at dierent positions. . . . . . . . . . . . . . . 30

38

A. Appendix A

Figure A.1: Computes volume integrals for a polyhedron. See section 4.2.1. Taken from [16].

39

Appendix A

Figure A.2: Computes the required surface integrals over a polzhedral face. See section 4.2.2 Taken

from [16].

40

Appendix A

Figure A.3: Compute the integrals over a facet projection. See section 4.2.3.Taken from [16].

41

B. Appendix B

Figure B.1: Velocity eld for a simulation with a cube of edge length 10 positioned at(31.5, 31.5, 31.5).

Figure B.2: Velocity eld for a simulation with a cube of edge length 10 positioned at(32.4, 31.7, 33.1).

42

Appendix B

Figure B.3: Velocity at a horizontal line of Figure B.1.

43

Appendix B

Figure B.4: Velocity at a vertical line of Figure B.1.

44

Appendix B

Figure B.5: Velocity at a horizontal line of Figure B.2.

45

Appendix B

Figure B.6: Velocity at a vertical line of Figure B.2.

46