Rank-1 lattices in computer graphics [Elektronische Ressource] / Sabrina Dammertz

Sujets

• Informatik
• Mathematics

Informations

• Publié par: universitat_ulm
• Publié le: 01 janvier 2009
• Nombre de lectures: 7
• Langue: English
• Poids de l'ouvrage: 47 Mo

Extrait

Rank 1LatticesinComputerGraphics
SabrinaDammertz,geb.inRavensburg
Institutfur¨ Medieninformatik,2009
DissertationzurErlangungdesDoktorgradesDr.rer.nat.derFakultat¨ fur¨
¨IngenieurwissenschaftenundInformatikderUniversitatUlmAmtierenderDekan: Prof.Dr.MichaelWeber
Gutachter: Dr.AlexanderKeller Prof.Dr.MichaelWeber
TagderPromotion: 14.07.2009Abstract
Sampling is fundamental to computer graphics, as samples are used both for representing
data and computing averages in the process of forming images. In this context rank 1 lat
tices are explored with respect to image and texture representation, simulation, and image
synthesis. We also contribute the necessary algorithmic and theoretical investigations to
find rank 1 lattices, which are suitable for specific requirements. Opposite to common be
lief, it turns out that rank 1 lattices improve graphics applications quite notably and result
inmoreefficientalgorithms,too.
iiiivAcknowledgements
Manythanksto
• Holgerforhislonglastingcollaboration,support,andpatience
• AlexanderKellerforhisguidance,encouragement,andsupportforthisPhD
• mentalimagesforthefinancialsupport
• theoldandnewcomputergraphicsgroup
• Johannes Hanika and Leonhard Grunschloss¨ for proof reading, and giving valuable
feedback
• Carsten Wachter¨ , Matthias Raab, Martin Bader, Leonhard Grunschloss,¨ Johannes
Hanika,ManuelFinckh,andStefanMenzformanyhelpfuldiscussions
• myfamily
vviContents
1 Introduction 1
1.1 LatticeStructureofPseudo RandomNumberGenerators . . . . . . . . . 2
1.2 Images,Displays,andSensorswithLatticeStructure . . . . . . . . . . . 5
1.3 MotivationandStructureoftheThesis . . . . . . . . . . . . . . . . . . . 7
2 Rank 1Lattices 9
2.1 Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.2 DualLattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.3 MinimumDistance . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.4 SamplingEfficiencyofRank 1Lattices . . . . . . . . . . . . . . 21
2.1.5 LocatingLatticePoints . . . . . . . . . . . . . . . . . . . . . . 21
2.1.6 ShiftedRank 1Lattices . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Rank 1LatticeSequences . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Quasi MonteCarloErrorBounds . . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 ClassicQuasi MonteCarloErrorBounds . . . . . . . . . . . . . 27
2.3.2 ErrorBoundforLipschitzContinuousFunctions . . . . . . . . . 30
2.3.3 RandomizedQuasi MonteCarloErrorBound . . . . . . . . . . . 32
3 ParametersforRank 1Lattices 35
3.1 Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.1 FibonacciLattice . . . . . . . . . . . . . . . . . . . . . . . . . . 35√
3.1.2 ConstructionbytheContinuedFractionEqualto 3 . . . . . . . 36
3.2 MaximizedMinimumDistanceRank 1Lattices . . . . . . . . . . . . . . 37
3.2.1 SearchingontheUnitSquare . . . . . . . . . . . . . . . . . . . 39
3.2.2 MMDRank 1LatticeSequences . . . . . . . . . . . . . . . . . . 48
3.3 SearchforAnisotropicRank 1Lattices . . . . . . . . . . . . . . . . . . 54
3.4 WeightedNorms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.5 (t,m,2) NetsfromShiftedRank 1Lattices . . . . . . . . . . . . . . . . 61
4 FourierTransformonRank 1Lattices 69
4.1 ChoosingtheWaveVectors . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2 SpectralSynthesisofOceanWaves . . . . . . . . . . . . . . . . . . . . . 73
4.3 StableSimulationofFluids . . . . . . . . . . . . . . . . . . . . . . . . . 75
viiContents
5 RasterizationonRank 1Lattices 79
5.1 Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.2 Circles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6 TexturesonRank 1Lattices 87
6.1 DataStructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.1.1 NearestNeighborLook Up . . . . . . . . . . . . . . . . . . . . . 87
6.1.2 LinearInterpolation . . . . . . . . . . . . . . . . . . . . . . . . 88
6.1.3 Rank 1LatticeB SplinesofDegree k . . . . . . . . . . . . . . . 89
6.1.4 TilingandMulti Resolution . . . . . . . . . . . . . . . . . . . . 91
6.1.5 Acquisition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.2.1 MaximizedMinimumDistanceRank 1Lattices . . . . . . . . . . 94
6.2.2 AnisotropicRank 1Lattices . . . . . . . . . . . . . . . . . . . . 95
7 Anti AliasingbyRank 1Lattices 99
7.1 SpectrallyAdaptiveSampling . . . . . . . . . . . . . . . . . . . . . . . 100
7.2 JitteringRank 1Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.2.1 MappinginanIsotropicWay . . . . . . . . . . . . . . . . . . . . 106
7.2.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
8 Summary 115
8.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8.2 FutureWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
A SourceCode 119
A.1 SearchAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
A.2 AuxiliaryFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
B LatticeParameterTables 129
B.1 MMDRank 1LatticesnotavailableinKorobovForm . . . . . . . . . . . 129
iB.2with n=2 Pointsfori=2,...,31 . . . . . . . . 130
B.3 (t,m,2) NetsfromShiftedRank 1LatticesinBase b . . . . . . . . . . . 132
viii1 Introduction
Lattices are well known structures in everyday life which often are only unconsciously
perceived: Ranging from cobbled pavement in pedestrian areas, mesh wire fences, mo
saics and decorations to the screen raster and camera sensors, they are for example also
used to partition the playing fields in strategy games. Moreover, they are applied in crys
tallography, in communication theory for modulation and quantization and in coding and
decoding[AEVZ02]andplayanimportantroleinspherepackingproblems[CSB87].The
most common two dimensional lattices are the rectangular, the square, and the hexagonal
lattice,thelasttwoofwhichareshowninFigure1.1.Thehexagonallatticeallowsthedens
est packing of circles in a plane, which means that the largest mutual minimum distance
betweentwolatticepointsintwodimensionsisfeaturedinthiskindoflattice[CSB87].
According to their applications in mathematics and computer science many numerical
algorithmsarebaseduponthem,suchasquadraturerulesinintegrationproblemsandfunc
tion approximation [Sch97]. Recently, lattices have quite actively been subject of research
in the field of quasi Monte Carlo with respect to high dimensional numerical integration
[KSW06,NC06,CKN06,CN08,SJ08].Incomputergraphicslatticesareusedassampling
patterns for pixel anti aliasing. The simplest example is placing a sampling point in the
center of each pixel. Additionally, in [Gla95] the rectangular, hexagonal, triangular and
diamond lattice are examined as sampling techniques. Current display technology incor-
porates the square lattice in the square pixel layout. Thus, all algorithms involved in pixel
processing, as for example rasterization or the accumulation buffer, work on this lattice.
Furthermore, sampling lattices are basic tools for the digitalization of continuous data.
Whereas the square lattice is mostly used in this context, [MS05] give a thorough survey
1 1
1 1
squarelattice hexagonallattice
Figure1.1:Exampleforrank 2lattices.
1Figure1.2:Two dimensional shifted lattice by all overlapping 2 tuples (X ,X ) for then n+1
linearcongruentialgenerator(LCG)X =(137·X +187) mod 256.n+1 n
ofthehexagonallatticeinthefieldofimageprocessing(seeSection1.2).
1.1 LatticeStructureofPseudo RandomNumberGenerators
Random numbers appear in a wide range of applications, as for example in numerical
analysis and cryptography. A sequence of random numbers has to fulfill the following
properties: the random numbers must be unpredictable, independent from each other, and
uniformlydistributedwithinagivendomain.However,realrandomnumbersareexpensive
anddifficulttogenerateonstandardcomputerhardware.Thereforeusuallypseudo random
generators are used, which try to mimic random behavior by deterministic algorithms. As
a consequence, the resulting pseudo random numbers are predictable and only approxi
matelyindependent.
A very common and popular principle for the generation of pseudo random numbers is
thelinearcongruentialgenerator(LCG)[Knu81,ES01]
X =(aX +c)modm, m>0,k≥0, (1.1)k+1 k
eachofwhichisdescribedbythetuple (a,c,m,X ),wherea∈{1,...,m−1}isthemulti 0
+plier, c∈{0,...,m−1} is the increment, m∈N is the modulus, and X ∈{0,...,m−1}0
is the initial value. Dividing each X by the modulus m yields numbers in the unit intervalk
[0,1).Duetothemodulusthesetofgeneratednumbersisfiniteandthereforemustexpose
aperiod.
This periodicity can be analyzed and visualized by an important property of LCGs,
whichisthatthesetofallmpoints
{(X ,X ,...,X )|0≤k<m}, (1.2)k k+1 k+s−1
which are called overlapping s tuples, conforms to the intersection of an s dimensional
sinteger lattice with the hypercube [0,m) [LC97]. This lattice structure is illustrated for
dimension s =2 in Figure 1.2 using a LCG with parameters a =137, c =187 , m =256
andX =0[Knu81].0