présentation.tex (38884B)
1 \documentclass[hyperref={pdfpagelabels=false}]{beamer} 2 % ATTENTION 3 % modifier dans /usr/share/texmf/web2c/texmf.cnf : 4 % hash_extra = 500000 5 % pool_size = 12500000 6 % Puis~: fmtutil --all && sudo fmtutil-sys --all 7 % 8 % ATTENTION 9 % Nécessite pgf 2.10. Sous ubuntu, installer~: 10 % http://launchpadlibrarian.net/70800349/pgf_2.10-1_all.deb 11 % De la page https://launchpad.net/ubuntu/precise/i386/pgf/2.10-1 12 \usepackage{lmodern} 13 \usepackage{textcomp}% Babel says we should include this when using \textdegree. 14 \usefonttheme{professionalfonts} 15 \usepackage[T1]{fontenc} 16 \usepackage[frenchb]{babel} 17 \usepackage{hyperref} 18 \usepackage{tikz} 19 \usetikzlibrary{positioning,calc,chains,intersections} 20 \usetheme{Frankfurt} 21 \usepackage{graphicx} 22 23 \title{FMIN313 Moteurs de jeux\\ Génération de terrains} 24 \author{DUPÉRON Georges \and\texorpdfstring{\\}{} BONAVERO Yoann} 25 \institute{Université Montpellier II,\\Département informatique,\\Master 2 IFPRU\\Encadrants~: F. Koriche et M. Moulis} 26 \date{Lundi 14 novembre 2011} 27 28 \defbeamertemplate*{footline}{shadow theme} 29 {% 30 \leavevmode% 31 \hbox{\begin{beamercolorbox}[wd=.5\paperwidth,ht=2.5ex,dp=1.125ex,leftskip=.3cm plus1fil,rightskip=.3cm]{author in head/foot}% 32 \usebeamerfont{author in head/foot}\insertframenumber\,/\,\inserttotalframenumber%\hfill\url{http://www.pticlic.fr/} 33 \end{beamercolorbox}% 34 \begin{beamercolorbox}[wd=.5\paperwidth,ht=2.5ex,dp=1.125ex,leftskip=.3cm,rightskip=.3cm plus1fil]{title in head/foot}% 35 \usebeamerfont{title in head/foot}\insertshorttitle% 36 \end{beamercolorbox}}% 37 \vskip0pt% 38 } 39 40 \AtBeginSection[] { 41 \begin{frame} 42 \frametitle{Plan} 43 \tableofcontents[currentsection] 44 \end{frame} 45 \addtocounter{framenumber}{-1} 46 } 47 48 \begin{document} 49 \makeatletter\renewcommand*{\figurename}{\@gobble}\makeatother 50 51 \begin{frame} 52 \titlepage 53 \end{frame} 54 55 % \section{Introduction} 56 57 \section{Génération} 58 59 % \pgfmathrnd 60 % \xdef\noiseseed{\pgfmathresult} 61 \xdef\noiseseed{0.99661} 62 63 \makeatletter 64 \def\getcache#1{\csname cache,#1\endcsname} 65 \def\setcache#1#2{\expandafter\xdef\csname cache,#1\endcsname{#2}} 66 \def\clearcache#1{\expandafter\global\expandafter\let\csname cache,#1\endcsname\@undefined} 67 \def\setintmacro#1#2{\pgfmathparse{int(#2)}\edef#1{\pgfmathresult}} 68 % 69 \pgfmathdeclarefunction{lazyifthenelse}{3}{% 70 \ifx 1#1% 71 \pgfmathparse{#2}% 72 \else% 73 \pgfmathparse{#3}% 74 \fi% 75 } 76 \makeatother 77 78 \shorthandoff{;?:} 79 \tikzset{ 80 declare function={ 81 hash_3(\a,\b)=Mod(\a*\a+\b,1); 82 hash_2(\a,\b)=hash_3(mod(\a*\b,1.783)+77.123,mod(\a+\b,1.843)*-0.179); 83 hash(\a,\b)=hash_2(mod(\a+\b,1.783)*0.417,mod(\a*\b,1.843)+42.56); 84 noise1D(\x,\octave)=hash(\x,hash(\octave,\noiseseed)); 85 sampleLeft(\x,\periode,\octave)=noise1D(floor(\x/\periode), \octave); 86 sampleLeftLeft(\x,\periode,\octave)=noise1D(floor(\x/\periode)-1, \octave); 87 sampleRight(\x,\periode,\octave)=noise1D(floor(\x/\periode)+1, \octave); 88 sampleRightRight(\x,\periode,\octave)=noise1D(floor(\x/\periode)+2, \octave); 89 sampleDelta(\x,\periode)=frac(\x/\periode); 90 linearInterpolation(\x,\a,\b)=\x*(\b-\a) + \a; 91 cosineInterpolation(\x,\a,\b)=(1-cos(\x*180))*0.5*(\b-\a) + \a; 92 cubicInterpolation_(\x,\p,\q,\r,\s)=((\p*\x + \q)*\x + \r)*\x + \s; 93 cubicInterpolation(\x,\a,\b,\c,\d)=cubicInterpolation_(\x, (\d-\c)-(\a-\b), ((\a-\b)*2)-(\d-\c), \c-\a, \b); 94 % Using linear interpolation 95 octave1DLinear(\x,\octave,\periode,\amplitude)=\amplitude*linearInterpolation(sampleDelta(\x,\periode), sampleLeft(\x,\periode,\octave), sampleRight(\x,\periode,\octave)); 96 perlin1DLinear_(\x,\octave,\periode,\octaves,\persistance,\amplitude)=lazyifthenelse(\octave >= \octaves, 0, "octave1DLinear(\x,\octave,\periode,\amplitude) + perlin1DLinear_(\x,\octave+1,\periode*0.5,\octaves,\persistance,\amplitude*\persistance)"); 97 perlin1DLinear(\x,\periode,\octaves,\persistance,\amplitude)=perlin1DLinear_(\x,0,\periode,\octaves,\persistance,\amplitude); 98 % Using cosine interpolation 99 octave1DCosine(\x,\octave,\periode,\amplitude)=\amplitude*cosineInterpolation(sampleDelta(\x,\periode), sampleLeft(\x,\periode,\octave), sampleRight(\x,\periode,\octave)); 100 perlin1DCosine_(\x,\octave,\periode,\octaves,\persistance,\amplitude)=lazyifthenelse(\octave >= \octaves, 0, "octave1DCosine(\x,\octave,\periode,\amplitude) + perlin1DCosine_(\x,\octave+1,\periode*0.5,\octaves,\persistance,\amplitude*\persistance)"); 101 perlin1DCosine(\x,\periode,\octaves,\persistance,\amplitude)=perlin1DCosine_(\x,0,\periode,\octaves,\persistance,\amplitude); 102 % Using cubic interpolation 103 octave1DCubic(\x,\octave,\periode,\amplitude)=\amplitude*cubicInterpolation(sampleDelta(\x,\periode), sampleLeftLeft(\x,\periode,\octave), sampleLeft(\x,\periode,\octave), sampleRight(\x,\periode,\octave), sampleRightRight(\x,\periode,\octave)); 104 % Craters 105 sqdistance_(\dx,\dy)=\dx*\dx+\dy*\dy; 106 sqdistance(\x,\y,\cx,\cy)=sqdistance_(\x-\cx,\y-\cy); 107 % 2D Perlin 108 noise2D(\x,\y,\octave)=hash(\x,hash(\y,hash(\octave,\noiseseed))); 109 sampleLeftAbove2D(\x,\y,\periode,\octave)=noise2D(floor(\x/\periode), floor(\y/\periode) + 1, \octave); 110 sampleLeftBelow2D(\x,\y,\periode,\octave)=noise2D(floor(\x/\periode), floor(\y/\periode), \octave); 111 sampleRightAbove2D(\x,\y,\periode,\octave)=noise2D(floor(\x/\periode)+1, floor(\y/\periode) + 1, \octave); 112 sampleRightBelow2D(\x,\y,\periode,\octave)=noise2D(floor(\x/\periode)+1, floor(\y/\periode), \octave); 113 octave2DCosine(\x,\y,\octave,\periode,\amplitude)=\amplitude*cosineInterpolation(sampleDelta(\y,\periode), 114 cosineInterpolation(sampleDelta(\x,\periode), sampleLeftBelow2D(\x,\y,\periode,\octave), sampleRightBelow2D(\x,\y,\periode,\octave)), 115 cosineInterpolation(sampleDelta(\x,\periode), sampleLeftAbove2D(\x,\y,\periode,\octave), sampleRightAbove2D(\x,\y,\periode,\octave)) 116 ); 117 perlin2DCosine_(\x,\y,\octave,\periode,\octaves,\persistance,\amplitude)=lazyifthenelse(\octave >= \octaves, 0, "octave2DCosine(\x,\y,\octave,\periode,\amplitude) + perlin2DCosine_(\x,\y,\octave+1,\periode*0.5,\octaves,\persistance,\amplitude*\persistance)"); 118 perlin2DCosine(\x,\y,\periode,\octaves,\persistance,\amplitude)=perlin2DCosine_(\x,\y,0,\periode,\octaves,\persistance,\amplitude); 119 xpointoncircle(\t,\circler,\maxdiam)=1 + \maxdiam/2 + cos(\t)*\circler; 120 ypointoncircle(\t,\circler,\maxdiam)=1 + \maxdiam/2 + sin(\t)*\circler; 121 courbepoly(\x)=(((-12.5*\x + 26.25) * \x -16) * \x + 3.25)*\x; 122 } 123 } 124 \shorthandon{;?:} 125 126 \subsection{Perlin noise} 127 \begin{frame} 128 \frametitle{Perlin noise} 129 \begin{figure}[h] 130 \centering 131 \begin{tikzpicture}[ 132 scale=0.09, 133 pcurve/.style={samples at={0,1,...,64}, smooth}, 134 mcurve/.style={pcurve, mark=ball, mark size=18}, 135 mgray/.style={mcurve,gray!50!white}] 136 % Prendre de la place lorsqu'on n'affiche pas les courbes supérieures. 137 \path (0,-5) -- (0,40); 138 \only<1-14>{ 139 \path (-5,0) -- (70,0); 140 \node[anchor=east] at (-2,0) {\hphantom{\small $1+2+3$}}; 141 \node[anchor=west] at (64+2,0) {\hphantom{\small $1+2+3$}}; 142 } 143 144 % Lignes horizontales 145 \only<1-14>{ \draw[->,gray] (0,0) -- (70,0); } 146 \only<2-3,7-14>{ \draw[->,gray] (0,20) -- (70,20); } 147 \only<3-4,7-14>{ \draw[->,gray] (0,30) -- (70,30); } 148 149 % Amplitude 150 \only<11>{ \draw[<->, thick, red] (-2,1) -- (-2,19); } 151 % Octaves 152 \only<12>{ \node[anchor=east, text=red] at (-2,10) {1}; } 153 \only<12>{ \node[anchor=east, text=red] at (-2,25) {2}; } 154 \only<12>{ \node[anchor=east, text=red] at (-2,32.5) {3}; } 155 % Fréquence 156 \only<13>{ \draw[<->, thick, red] (0,-2) -- (16,-2); } 157 \only<13>{ \draw[dashed, red] (0,-2) -- (0,{octave1DCosine(0,0,16,20)}); } 158 \only<13>{ \draw[dashed, red] (16,-2) -- (16,{octave1DCosine(16,0,16,20)}); } 159 % Persistance 160 \only<14>{ \draw[<->, dashed, red] (-2,1) -- (-2,19); } 161 \only<14>{ \draw[<->, dashed, red] (-2,21) -- (-2,29); } 162 \only<14>{ \draw[thick, red] (-2,10) edge[->,bend left=70] node[left] {\small $\times 0.5$} (-2,25); } 163 164 % Étiquette à gauche 165 \only<4>{ \node[anchor=east] at (-2,{perlin1DCosine(0,16,2,0.5,20)}) {\small $1+2$}; } 166 \only<5>{ \node[anchor=east] at (-2,{perlin1DCosine(0,16,3,0.5,20)}) {\small $1+2+3$}; } 167 168 % Octave 0 169 \only<1-3>{ \draw[mcurve, mark repeat=16] plot (\x,{octave1DCosine(\x,0,16,20)}); } 170 \only<4>{ \draw[pcurve, gray] plot (\x,{octave1DCosine(\x,0,16,20)}); } 171 \only<5>{ \draw[pcurve, gray!50!white] plot (\x,{octave1DCosine(\x,0,16,20)}); } 172 \only<7>{ \draw[mgray, mark repeat=16] plot (\x,{octave1DLinear(\x,0,16,20)}); } 173 \only<8>{ \draw[mcurve, mark repeat=16] plot (\x,{octave1DLinear(\x,0,16,20)}); } 174 \only<9>{ \draw[mcurve, mark repeat=16] plot (\x,{octave1DCubic(\x,0,16,20)}); } 175 \only<10-14>{ \draw[mcurve, mark repeat=16] plot (\x,{octave1DCosine(\x,0,16,20)}); } 176 177 % Octave 1 178 \only<2-3>{ \draw[mcurve, mark repeat=8] plot (\x,{octave1DCosine(\x,1,8,10) + 20}); } 179 \only<7>{ \draw[mgray, mark repeat=8] plot (\x,{octave1DLinear(\x,1,8,10) + 20}); } 180 \only<8>{ \draw[mcurve, mark repeat=8] plot (\x,{octave1DLinear(\x,1,8,10) + 20}); } 181 \only<9>{ \draw[mcurve, mark repeat=8] plot (\x,{octave1DCubic(\x,1,8,10) + 20}); } 182 \only<10-14>{ \draw[mcurve, mark repeat=8] plot (\x,{octave1DCosine(\x,1,8,10) + 20}); } 183 184 % Octave 2 185 \only<3-4>{ \draw[mcurve, mark repeat=4] plot (\x,{octave1DCosine(\x,2,4,5) + 30}); } 186 \only<7>{ \draw[mgray, mark repeat=4] plot (\x,{octave1DLinear(\x,2,4,5) + 30}); } 187 \only<8>{ \draw[mcurve, mark repeat=4] plot (\x,{octave1DLinear(\x,2,4,5) + 30}); } 188 \only<9>{ \draw[mcurve, mark repeat=4] plot (\x,{octave1DCubic(\x,2,4,5) + 30}); } 189 \only<10-14>{\draw[mcurve, mark repeat=4] plot (\x,{octave1DCosine(\x,2,4,5) + 30}); } 190 191 % Octave 0+1 192 \only<4>{ \draw[mcurve, mark repeat=8] plot (\x,{perlin1DCosine(\x,16,2,0.5,20)}); } 193 \only<5>{ \draw[pcurve, gray] plot (\x,{perlin1DCosine(\x,16,2,0.5,20)}); } 194 195 % Octave 0+1+2 196 \only<5>{ \draw[mcurve, mark repeat=4] plot (\x,{perlin1DCosine(\x,16,3,0.5,20)}); } 197 \only<6>{ \draw[pcurve] plot (\x,{perlin1DCosine(\x,16,3,0.5,20)}); } 198 \end{tikzpicture} 199 % Hash de coordonnées 200 \begin{tikzpicture}[ 201 node distance=0.5cm, 202 every node/.style={rectangle,minimum size=6mm,rounded corners=3mm,very thick,draw=black!50} 203 ] 204 \only<15>{ 205 \path (0,-5*0.09) -- (0,40*0.09); % This and the 17.5*0.09 below are for vertical alignment with the other figure. 206 \node[draw] (hash1) at (0,17.5*0.09) {hash}; 207 \node[draw,above left=of hash1, draw=blue!50] (x) {$x$}; 208 \node[draw,below left=of hash1] (noctave) {n\textdegree octave}; 209 \draw[->] (x) -- (hash1); 210 \draw[->] (noctave) -- (hash1); 211 \node[draw, right=of hash1] (hash2) {hash}; 212 \node[draw,below left=of hash2] (seed) {graine}; 213 \draw[->] (hash1) -- (hash2); 214 \draw[->] (seed) -- (hash2); 215 \node[right=of hash2, draw=green!50] (valeur) {$valeur$}; 216 \draw[->] (hash2) -- (valeur); 217 } 218 \end{tikzpicture} 219 % \caption{Perlin noise} 220 \end{figure} 221 \begin{itemize} 222 \item<1-> Superposition d'octaves de bruit. 223 \item<7-> Interpolation\only<8->{ linéaire}\only<9->{, cubique}\only<10->{ ou cosinusoidale.} 224 \item<11-> Amplitude\only<12->{, octaves}\only<13->{, fréquence}\only<14->{, persistance.} 225 \item<15-> Hash de coordonnées. 226 \end{itemize} 227 \end{frame} 228 229 % Macro pour la génération de dégradés. 230 \def\gengradient#1{ 231 \xdef\pointa{0} 232 \xdef\pointb{1} 233 \pgfmathsetmacro{\posa}{\csname positions#1\endcsname[\pointa]}\xdef\posa{\posa} 234 \pgfmathsetmacro{\posb}{\csname positions#1\endcsname[\pointb]}\xdef\posb{\posb} 235 \foreach \x in {0,...,512}{ 236 \pgfmathsetmacro{\v}{max(0,min(1,\x/512))} 237 238 \pgfmathparse{\v > \posb} 239 \ifnum 1=\pgfmathresult 240 \xdef\pointa{\pointb} 241 \xdef\posa{\posb} 242 \setintmacro{\pointb}{\pointb+1}\xdef\pointb{\pointb} 243 \pgfmathsetmacro{\posb}{\csname positions#1\endcsname[\pointb]}\xdef\posb{\posb} 244 \fi 245 246 \pgfmathsetmacro{\mix}{100 - 100 * (\v-\posa) / (\posb-\posa)} 247 \setcache{gradient,#1,\x}{gradient#1\pointa!\mix!gradient#1\pointb} 248 } 249 } 250 251 % Génération du dégradé "terrain" 252 \definecolor{gradientterrain0}{rgb}{0,0,0.5} 253 \definecolor{gradientterrain1}{rgb}{0.2,0.2,1} 254 \definecolor{gradientterrain2}{rgb}{0.9,0.6,0.1} 255 \definecolor{gradientterrain3}{rgb}{0.1,0.6,0.2} 256 \definecolor{gradientterrain4}{rgb}{0.6,0.3,0.05} 257 \definecolor{gradientterrain5}{rgb}{1,1,1} 258 \def\positionsterrain{{0,0.3,0.4,0.88,0.94,1}} 259 \gengradient{terrain} 260 261 \definecolor{gradientnuage0}{rgb}{0,0,1} 262 \definecolor{gradientnuage1}{rgb}{0,0.3,1} 263 \definecolor{gradientnuage2}{rgb}{0.7,0.7,1} 264 \definecolor{gradientnuage3}{rgb}{1,1,1} 265 \def\positionsnuage{{0,0.1,0.9,1}} 266 \gengradient{nuage} 267 268 \definecolor{gradientmarbre0}{rgb}{1,1,1} 269 \definecolor{gradientmarbre1}{rgb}{0.6,0.3,0.05} % rose 270 \definecolor{gradientmarbre2}{rgb}{1,0.95,0.8} % beige/gris 271 \definecolor{gradientmarbre3}{rgb}{0.8,0.7,0.4} % beige/gris 272 \definecolor{gradientmarbre4}{rgb}{0.5,0.5,0.5} % gris 273 \definecolor{gradientmarbre5}{rgb}{0,0,0} % noir 274 \def\positionsmarbre{{0,0.4,0.6,0.88,0.96,1}} 275 \gengradient{marbre} 276 277 278 % Génération du perlin 2D 279 \xdef\twodperlinsize{128} 280 \xdef\maxvtwodperlin{0} 281 \xdef\minvtwodperlin{0} 282 \def\maxradius{32} 283 \def\ncircles{10} 284 \foreach \y in {1,2,...,\twodperlinsize}{ 285 \message{Perlin 2D line \y/\twodperlinsize.} 286 \foreach \x in {1,2,...,\twodperlinsize}{ 287 \pgfmathsetmacro{\v}{-perlin2DCosine(\x,\y,16,3,0.5,50)} 288 \setcache{vtwodperlin,\x,\y}{\v} 289 \pgfmathparse{max(\maxvtwodperlin,\v)} 290 \xdef\maxvtwodperlin{\pgfmathresult} 291 \pgfmathparse{min(\minvtwodperlin,\v)} 292 \xdef\minvtwodperlin{\pgfmathresult} 293 } 294 } 295 296 % Génération du craters 297 \xdef\craterssize{128} 298 \xdef\maxvcraters{0} 299 \xdef\minvcraters{0} 300 \def\maxradius{32} 301 \def\ncircles{100} 302 \foreach \y in {1,2,...,\craterssize}{ 303 \foreach \x in {1,2,...,\craterssize}{ 304 \setcache{vcraters,\x,\y}{0} 305 } 306 } 307 \foreach \c in {1,...,\ncircles}{ 308 \setintmacro{\circlex}{noise1D(\c,0)*\craterssize} 309 \setintmacro{\circley}{noise1D(\c,1)*\craterssize} 310 \setintmacro{\circler}{1+noise1D(\c,2)*\maxradius} 311 \message{Circle number \c/\ncircles, center (\circlex, \circley), radius \circler} 312 \foreach \dy in {-\circler,...,\circler}{ 313 \setintmacro{\y}{\circley+\dy} 314 \pgfmathparse{(\y > 0) && (\y <= \craterssize)} 315 \ifnum 1=\pgfmathresult 316 \foreach \dx in {-\circler,...,\circler}{ 317 \setintmacro{\x}{\circlex+\dx} 318 \pgfmathparse{(\x > 0) && (\x <= \craterssize)} 319 \ifnum 1=\pgfmathresult 320 \xdef\oldv{\getcache{vcraters,\x,\y}} 321 \pgfmathsetmacro{\v}{\oldv - max(0,\circler - ((\dx*\dx + \dy*\dy)/\circler))} 322 \setcache{vcraters,\x,\y}{\v} 323 \pgfmathparse{max(\maxvcraters,\v)} 324 \xdef\maxvcraters{\pgfmathresult} 325 \pgfmathparse{min(\minvcraters,\v)} 326 \xdef\minvcraters{\pgfmathresult} 327 \fi 328 } 329 \fi 330 } 331 } 332 333 % Génération du perlin + craters 334 \xdef\cratersperlinsize{\twodperlinsize} 335 \xdef\maxvcratersperlin{\maxvtwodperlin} 336 \xdef\minvcratersperlin{\minvtwodperlin} 337 \def\maxradius{32} 338 \def\ncircles{20} 339 \foreach \y in {1,2,...,\cratersperlinsize}{ 340 \foreach \x in {1,2,...,\cratersperlinsize}{ 341 \setcache{vcratersperlin,\x,\y}{\getcache{vtwodperlin,\x,\y}} 342 } 343 } 344 \foreach \c in {1,...,\ncircles}{ 345 \setintmacro{\circlex}{noise1D(\c,0)*\cratersperlinsize} 346 \setintmacro{\circley}{noise1D(\c,1)*\cratersperlinsize} 347 \setintmacro{\circler}{1+noise1D(\c,2)*\maxradius} 348 \message{Circle number \c/\ncircles, center (\circlex, \circley), radius \circler} 349 \foreach \dy in {-\circler,...,\circler}{ 350 \setintmacro{\y}{\circley+\dy} 351 \pgfmathparse{(\y > 0) && (\y <= \cratersperlinsize)} 352 \ifnum 1=\pgfmathresult 353 \foreach \dx in {-\circler,...,\circler}{ 354 \setintmacro{\x}{\circlex+\dx} 355 \pgfmathparse{(\x > 0) && (\x <= \cratersperlinsize)} 356 \ifnum 1=\pgfmathresult 357 \xdef\oldv{\getcache{vcratersperlin,\x,\y}} 358 \pgfmathparse{\oldv - max(0,\circler - ((\dx*\dx + \dy*\dy)/\circler))} 359 \setcache{vcratersperlin,\x,\y}{\pgfmathresult} 360 \pgfmathparse{max(\maxvcratersperlin,\pgfmathresult)} 361 \xdef\maxvcratersperlin{\pgfmathresult} 362 \pgfmathparse{min(\minvcratersperlin,\pgfmathresult)} 363 \xdef\minvcratersperlin{\pgfmathresult} 364 \fi 365 } 366 \fi 367 } 368 } 369 370 \begin{frame} 371 \frametitle{Perlin noise (Variations)} 372 \begin{figure}[h] 373 \centering 374 \begin{tikzpicture}[scale=0.025] 375 \path (300,0) ++(128,128) ++(1.5,1.5) rectangle (0,0); 376 \only<1-5>{ 377 \foreach \y in {1,2,...,\twodperlinsize}{ 378 \message{Gradient line \y/\twodperlinsize...} 379 \foreach \x in {1,2,...,\twodperlinsize}{ 380 \pgfmathsetmacro{\v}{(\getcache{vtwodperlin,\x,\y}-\minvtwodperlin)/max(1,\maxvtwodperlin-\minvtwodperlin)} 381 \only<5>{ \pgfmathsetmacro{\v}{1-2*abs(\v-0.5)} } 382 \setintmacro{\v}{max(0,min(512,int(\v*512)))} 383 \only<2-5>{ \path[fill=\getcache{gradient,nuage,\v}] (\x,\y) rectangle ++(1.5,1.5); } 384 \only<3-5>{ \path[fill=\getcache{gradient,marbre,\v}] (150+\x,\y) rectangle ++(1.5,1.5); } 385 \only<4-5>{ \path[fill=\getcache{gradient,terrain,\v}] (300+\x,\y) rectangle ++(1.5,1.5); } 386 } 387 } 388 } 389 \only<6-8>{ 390 \node[coordinate] (p0) at (150,64) {}; 391 \node[coordinate] (p8) at (150+128,64) {}; 392 393 \node[coordinate] (m4) at ($ .5*(p0) + .5*(p8) $) {}; 394 \node[coordinate] (p4) at ($ (m4) + (0,{noise1D(64,0)*64-32}) $) {}; 395 396 \node[coordinate] (m2) at ($ .5*(p0) + .5*(p4) $) {}; 397 \node[coordinate] (p2) at ($ (m2) + (0,{noise1D(32,0)*32-16}) $) {}; 398 \node[coordinate] (m6) at ($ .5*(p4) + .5*(p8) $) {}; 399 \node[coordinate] (p6) at ($ (m6) + (0,{noise1D(96,0)*32-16}) $) {}; 400 401 \node[coordinate] (m1) at ($ .5*(p0) + .5*(p2) $) {}; 402 \node[coordinate] (p1) at ($ (m1) + (0,{noise1D(16,0)*16-8}) $) {}; 403 \node[coordinate] (m3) at ($ .5*(p2) + .5*(p4) $) {}; 404 \node[coordinate] (p3) at ($ (m3) + (0,{noise1D(48,0)*16-8}) $) {}; 405 \node[coordinate] (m5) at ($ .5*(p4) + .5*(p6) $) {}; 406 \node[coordinate] (p5) at ($ (m5) + (0,{noise1D(80,0)*16-8}) $) {}; 407 \node[coordinate] (m7) at ($ .5*(p6) + .5*(p8) $) {}; 408 \node[coordinate] (p7) at ($ (m7) + (0,{noise1D(112,0)*16-8}) $) {}; 409 } 410 \tikzset{shortdash/.style={dash pattern=on 1pt off 1pt}} 411 \only<6>{ 412 \draw[gray!50] (p0) -- (p8); 413 \draw[shortdash,gray] (p4) -- (m4); 414 \draw (p0) -- (p4) -- (p8); 415 } 416 \only<7>{ 417 \draw[gray!25] (p0) -- (p8); 418 \draw[gray!50] (p0) -- (p4) -- (p8); 419 \draw[shortdash,gray] (p2) -- (m2); 420 \draw[shortdash,gray] (p6) -- (m6); 421 \draw (p0) -- (p2) -- (p4) -- (p6) -- (p8); 422 } 423 \only<8>{ 424 \draw[gray!12.5] (p0) -- (p8); 425 \draw[gray!25] (p0) -- (p4) -- (p8); 426 \draw[gray!50] (p0) -- (p2) -- (p4) -- (p6) -- (p8); 427 \draw[shortdash,gray] (p1) -- (m1); 428 \draw[shortdash,gray] (p3) -- (m3); 429 \draw[shortdash,gray] (p5) -- (m5); 430 \draw[shortdash,gray] (p7) -- (m7); 431 \draw (p0) -- (p1) -- (p2) -- (p3) -- (p4) -- (p5) -- (p6) -- (p7) -- (p8); 432 } 433 \end{tikzpicture} 434 \end{figure} 435 \begin{itemize} 436 \item<1-> Bruit $n$D et voxels~: cavernes\only<2->{, nuages}\only<3->{, textures}\only<4->{, terrains.} 437 \item<5-> Ridged Perlin Noise. 438 \item<6-> Midpoint displacement. 439 \end{itemize} 440 \end{frame} 441 442 \begin{frame} 443 \frametitle{Perlin noise (Variations)} 444 \begin{figure}[h] 445 \centering 446 \begin{tikzpicture}[scale=0.025] 447 \path (0,0) -- (0,129.5); 448 \only<1>{ 449 \node[coordinate] (a) at (60:64) {}; 450 \node[coordinate] (b) at (0,0) {}; 451 \node[coordinate] (c) at (64,0) {}; 452 \shade[shading=axis,bottom color=white,top color=gray!50,shading angle=60] (a) -- (b) -- (c) -- cycle; 453 \draw (a) -- (b) -- (c) -- cycle; 454 \node[fill=black,circle,inner sep=1pt] (p) at (20,15) {}; 455 \draw[gray, densely dotted] (p) -- (a); 456 \draw[gray, densely dotted] (p) -- (b); 457 \draw[gray, densely dotted] (p) -- (c); 458 % Tétraèdre 459 \node[coordinate] (3a) at (132,{23+64*sqrt(24)/6},{64*sqrt(3)/6}) {}; 460 \node[coordinate] (3b) at (100,23,0) {}; 461 \node[coordinate] (3c) at (164,23,0) {}; 462 \node[coordinate] (3d) at (132,23,{64*sqrt(3)/2}) {}; 463 \draw (3a) -- (3b); 464 \draw (3b) -- (3d); 465 \draw (3d) -- (3a); 466 \draw (3a) -- (3c); 467 \draw (3c) -- (3d); 468 \draw[dashed] (3b) -- (3c); 469 \node[fill=black,circle,inner sep=1pt] (3p) at (135,30,30) {}; 470 \draw[gray, densely dotted] (3p) -- (3a); 471 \draw[gray, densely dotted] (3p) -- (3b); 472 \draw[gray, densely dotted] (3p) -- (3c); 473 \draw[gray, densely dotted] (3p) -- (3d); 474 } 475 \only<2->{ 476 \pgfmathsetmacro{\xalign}{164/2-128/2} 477 \pgfmathsetmacro{\circler}{\twodperlinsize*0.35} 478 \pgfmathsetmacro{\maxdiam}{\twodperlinsize} 479 \foreach \y in {1,2,...,\twodperlinsize}{ 480 \message{Gradient line \y/\twodperlinsize...} 481 \foreach \x in {1,2,...,\twodperlinsize}{ 482 \pgfmathsetmacro{\v}{(\getcache{vtwodperlin,\x,\y}-\minvtwodperlin)/max(1,\maxvtwodperlin-\minvtwodperlin)} 483 \setintmacro{\v}{max(0,min(512,int(\v*512)))} 484 \path[fill=\getcache{gradient,terrain,\v}] (\xalign+\x,\y) rectangle ++(1.5,1.5); 485 } 486 } 487 % TODO : couleur de la map sur la ligne. 488 \draw[->,gray] (\xalign+150,0) -- (\xalign+150+140,0); 489 \only<2>{ 490 \draw[red,samples at={0,5,...,80}, smooth, mark=*, mark indices={1,12}, mark size=72] plot ({\xalign+xpointoncircle(\x,\circler,\maxdiam)},{ypointoncircle(\x,\circler,\maxdiam)}); 491 \draw[red,samples at={0,5,...,80}, smooth, mark=*, mark indices={1,12}, mark size=72] plot ({\xalign+150+\x/360*70},{105-perlin2DCosine(xpointoncircle(\x,\circler,\maxdiam),ypointoncircle(\x,\circler,\maxdiam),16,3,0.5,60)}); 492 } 493 \only<3>{ 494 \draw[red,samples at={0,5,...,140}, smooth, mark=*, mark indices={1,12,24}, mark size=72] plot ({\xalign+xpointoncircle(\x,\circler,\maxdiam)},{ypointoncircle(\x,\circler,\maxdiam)}); 495 \draw[red,samples at={0,5,...,140}, smooth, mark=*, mark indices={1,12,24}, mark size=72] plot ({\xalign+150+\x/360*70},{105-perlin2DCosine(xpointoncircle(\x,\circler,\maxdiam),ypointoncircle(\x,\circler,\maxdiam),16,3,0.5,60)}); 496 } 497 \only<4>{ 498 \draw[red,samples at={0,5,...,360}, smooth, mark=*, mark indices={1,12,24}, mark size=72] plot ({\xalign+xpointoncircle(\x,\circler,\maxdiam)},{ypointoncircle(\x,\circler,\maxdiam)}); 499 \draw[red,samples at={0,5,...,360}, smooth, mark=*, mark indices={1,12,24}, mark size=72] plot ({\xalign+150+\x/360*70},{105-perlin2DCosine(xpointoncircle(\x,\circler,\maxdiam),ypointoncircle(\x,\circler,\maxdiam),16,3,0.5,60)}); 500 } 501 \only<5>{ 502 \draw[red,samples at={0,5,...,360}, smooth, mark=*, mark indices={1,12,24}, mark size=72] plot ({\xalign+xpointoncircle(\x,\circler,\maxdiam)},{ypointoncircle(\x,\circler,\maxdiam)}); 503 \draw[red,samples at={0,5,...,720}, smooth, mark=*, mark indices={1,12,24,72,84,96}, mark size=72] plot ({\xalign+150+\x/360*70},{105-perlin2DCosine(xpointoncircle(\x,\circler,\maxdiam),ypointoncircle(\x,\circler,\maxdiam),16,3,0.5,60)}); 504 } 505 } 506 \end{tikzpicture} 507 \end{figure} 508 \begin{itemize} 509 \item<1-> Simplex noise. $O(d^2)$ au lieu de $O(2^d)$. 510 \item<2-> Bruit répétable 1D : Cercle dans un espace 2D.\\Bruit répétable $n$D : hypercercle dans un espace $2n$D. 511 {\tiny\url{http://www.gamedev.net/blog/33/entry-2138456-seamless-noise/}} 512 \end{itemize} 513 \end{frame} 514 515 \subsection{Craters et Hills Algorithm} 516 \begin{frame} 517 \frametitle{Craters et Hills Algorithm} 518 \begin{figure}[h] 519 \centering 520 \begin{tikzpicture}[scale=0.025] 521 \path (300,0) ++(128,128) ++(1.5,1.5) rectangle (0,0); 522 \only<2->{ 523 \foreach \y in {1,2,...,\craterssize}{ 524 \message{Gradient line \y/\craterssize...} 525 \foreach \x in {1,2,...,\craterssize}{ 526 \pgfmathsetmacro{\v}{(\getcache{vcraters,\x,\y}-\minvcraters)/max(1,\maxvcraters-\minvcraters)} 527 \setintmacro{\v}{max(0,min(512,int(\v*512)))} 528 \path[fill=\getcache{gradient,terrain,\v}] (\x,\y) rectangle ++(1.5,1.5); 529 } 530 } 531 } 532 \only<3->{ 533 \foreach \y in {1,2,...,\cratersperlinsize}{ 534 \message{Gradient line \y/\cratersperlinsize...} 535 \foreach \x in {1,2,...,\cratersperlinsize}{ 536 \pgfmathsetmacro{\v}{(\getcache{vcratersperlin,\x,\y}-\minvcratersperlin)/max(1,\maxvcratersperlin-\minvcratersperlin)} 537 \setintmacro{\v}{max(0,min(512,int(\v*512)))} 538 \path[fill=\getcache{gradient,terrain,\v}] (150+\x,\y) rectangle ++(1.5,1.5); 539 } 540 } 541 } 542 \only<4->{ 543 \foreach \y in {1,2,...,\craterssize}{ 544 \message{Gradient line \y/\craterssize...} 545 \foreach \x in {1,2,...,\craterssize}{ 546 \pgfmathsetmacro{\v}{(\getcache{vcraters,\x,\y}-\minvcraters)/max(1,\maxvcraters-\minvcraters)} 547 \setintmacro{\v}{max(0,min(512,int(\v*512)))} 548 \setintmacro{\v}{512-\v} 549 \path[fill=\getcache{gradient,terrain,\v}] (300+\x,\y) rectangle ++(1.5,1.5); 550 } 551 } 552 } 553 \end{tikzpicture} 554 \end{figure} 555 \begin{itemize} 556 \item<1-> Craters 557 \begin{itemize} 558 \item<1-> Soustraire des cercles au terrain. {\small ($z = z - f(\text{distance au centre})$)} 559 \item<2-> Sur un terrain nu. 560 \item<3-> Sur un terrain existant. 561 \end{itemize} 562 \item<4-> Hills Algorithm~: ajouter des cercles. 563 \item<5-> Stockage des cercles dans un arbre {\small (BSP, Quadtree, LOD, \dots{})}. 564 \end{itemize} 565 \end{frame} 566 567 \subsection{Érosion} 568 569 \begin{frame} 570 \frametitle{Érosion} 571 \begin{itemize} 572 \item<1-> Déplacement de sédiments. 573 \item<2-> Taux en fonction de la pente, dureté de la roche, végétation. 574 \item<3-> Carte de circulation des eaux. 575 \item<4-> Pas temps-réel. 576 \item<5-6> Approximation : modification de la distribution des hauteurs. 577 \begin{figure}[h] 578 \centering 579 \begin{tikzpicture}[scale=0.025] 580 \path (300,0) ++(128,128) ++(1.5,1.5) rectangle (0,-2); 581 \foreach \y in {1,2,...,\twodperlinsize}{ 582 \message{Gradient line \y/\twodperlinsize...} 583 \foreach \x in {1,2,...,\twodperlinsize}{ 584 \pgfmathsetmacro{\v}{(\getcache{vtwodperlin,\x,\y}-\minvtwodperlin)/max(1,\maxvtwodperlin-\minvtwodperlin)} 585 \pgfmathsetmacro{\vv}{\v}% 586 \only<6>{% 587 \pgfmathsetmacro{\vv}{courbepoly(\v)}% 588 } 589 \setintmacro{\v}{max(0,min(512,int(\v*512)))} 590 \setintmacro{\vv}{max(0,min(512,int(\vv*512)))} 591 \path[fill=\getcache{gradient,terrain,\v}] (\x,\y) rectangle ++(1.5,1.5); 592 \path[fill=\getcache{gradient,terrain,\vv}] (300+\x,\y) rectangle ++(1.5,1.5); 593 } 594 } 595 \only<6>{ \draw[gray!50] (150,0) -- (150+128,128); } 596 \only<5>{ \draw[red, samples at={0,...,128}, smooth] plot (150+\x,\x); } 597 \only<6>{ \draw[red, samples at={0,...,128}, smooth] plot (150+\x,{courbepoly(\x/128) * 128}); } 598 \draw[gray!50] (150,128) -- (150+128,128); 599 \draw[gray!50] (150+128,0) -- (150+128,128); 600 \draw[->] (150,0) -- (150,128); 601 \draw[->] (150,0) -- (150+128,0); 602 \end{tikzpicture} 603 \end{figure} 604 \end{itemize} 605 \end{frame} 606 607 \subsection{Autres} 608 \begin{frame} 609 \frametitle{Autres méthodes} 610 \begin{itemize} 611 \item<1-> Chaînage d'algorithmes de bruit~: 612 \begin{itemize} 613 \item Ajout de couleurs, climats, végétation, relief\dots{} 614 \item Altération du comportement d'un algo. 615 \item[] {\tiny\url{http://www.gamedev.net/blog/33/entry-2249260-procedural-islands-redux/}} 616 \end{itemize} 617 \item<2-> Cartes polygonales. {\tiny\url{http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/}} 618 % TODO : ne sera probablement pas fait faute de temps. 619 % TODO : images 620 % - découpage du plan en polygones 621 % - positionnement de la mer et des lacs 622 % - hauteur fonction de la distance à la mer. 623 % - tracé de rivières en descendant le long des segments des polygones. 624 % - climats et biotopes en fonction de l'élévation et de la distance à l'humidité. 625 % - bruitage supplémentaire. 626 \item<3-> Intégration de formes dans le terrain. 627 \end{itemize} 628 \end{frame} 629 630 \subsection{Rivières} 631 632 \begin{frame} 633 \frametitle{Rivières} 634 \begin{itemize} 635 \item<1-> Pathfinding. {\tiny\url{http://www.umbrarumregnum.net/articles/creating-rivers}} 636 % TODO : Image (ne sera pas fait, manque de temps). 637 \item<2-> Affinage du tracé en fonction du LOD. 638 % TODO : Schéma sur 3 niveaux d'affinage en 3 étapes. 639 \item<3-> Tracé arbitraire. 640 \item<4-> Intégration dans le terrain. 641 \end{itemize} 642 \end{frame} 643 % Si on utilise une méthode de coût qui favorise de passer par un petit 644 % bout de bruit plutôt que de le contourner, mais favorise le 645 % contournement pour une grosse accumulation de bruit, on pourra même 646 % simuler l'érosion qui efface les méandres trop petits. 647 648 \subsection{Démonstration} 649 \begin{frame} 650 \frametitle{Démonstration} 651 \begin{center} 652 {\Huge World machine} 653 654 \vspace{1em} 655 \url{http://www.world-machine.com/} 656 \end{center} 657 \end{frame} 658 659 \section{Rendu} 660 661 \subsection{Isosurfaces} 662 \begin{frame} 663 \frametitle{Isosurfaces} 664 \begin{itemize} 665 \item Metaballs. {\tiny\texttt{/usr/lib/xscreensaver/metaballs}} 666 \item Surface 2D d'un bruit 3D. 667 \item Simplification de nuages. 668 \item Surface de l'eau. 669 \end{itemize} 670 \end{frame} 671 672 \subsection{Ray casting} 673 674 \begin{frame} 675 \frametitle{Ray casting} 676 \begin{figure}[h] 677 \centering 678 \begin{tikzpicture}[scale=0.5] 679 \node[circle,fill=black,inner sep=2pt] (eye) at (0,0) {}; 680 \node[coordinate] (a) at (4,-3) {}; 681 \node[coordinate] (b) at (5,-1) {}; 682 \node[coordinate] (c) at (6,-2) {}; 683 \node[coordinate] (d) at (7,1) {}; 684 \node[coordinate] (e) at (8,-3) {}; 685 \draw (2,3) -- (2,-3); 686 \draw (a) -- (b) -- (c) -- (d) -- (e); 687 688 \only<2>{ \draw[dashed] (eye) -- (e); } 689 \only<2->{ 690 \path[name path=eyee] (eye) -- (e); \path[name path=verte] (2.5,3) -- (2.5,-3); 691 \draw[red!50,thick,name intersections={of=eyee and verte}] (intersection-1) -- (2.5,-3); 692 } 693 694 \only<3>{ \draw[dashed] (eye) -- (d); } 695 \only<3->{ 696 \path[name path=eyed] (eye) -- (d); \path[name path=vertd] (2.4,3) -- (2.4,-3); 697 \draw[red!50,thick,name intersections={of=eyed and vertd}] (intersection-1) -- (2.4,-3); 698 } 699 700 \only<4>{ \draw[dashed] (eye) -- (c); } 701 \only<4->{ 702 \path[name path=eyed] (eye) -- (c); \path[name path=vertd] (2.3,3) -- (2.3,-3); 703 \draw[red!50,thick,name intersections={of=eyed and vertd}] (intersection-1) -- (2.3,-3); 704 } 705 706 \only<5>{ \draw[dashed] (eye) -- (b); } 707 \only<5->{ 708 \path[name path=eyed] (eye) -- (b); \path[name path=vertd] (2.2,3) -- (2.2,-3); 709 \draw[red!50,thick,name intersections={of=eyed and vertd}] (intersection-1) -- (2.2,-3); 710 } 711 712 \only<6>{ \draw[dashed] (eye) -- (a); } 713 \only<6->{ 714 \path[name path=eyed] (eye) -- (a); \path[name path=vertd] (2.1,3) -- (2.1,-3); 715 \draw[red!50,thick,name intersections={of=eyed and vertd}] (intersection-1) -- (2.1,-3); 716 } 717 \end{tikzpicture} 718 \end{figure} 719 \begin{itemize} 720 \item<1-> Très simple, très petit code. 721 \item<8-> Sampling. 722 \item<9-> Très lent. 723 \item<10-> Démonstration. {\small\url{http://forum.osdev.org/viewtopic.php?p=170625\#p170625}} 724 \item<11-> Monte Carlo. 725 \end{itemize} 726 \end{frame} 727 728 \section[LOD]{Niveau de détail} 729 730 \subsection{ROAM} 731 \begin{frame} 732 \frametitle{ROAM} 733 \begin{figure}[h] 734 \centering 735 \begin{tikzpicture}[scale=0.2] 736 \path (-4,0) -- (16,8); 737 \only<2-5> { \fill[red!20] (0,0) -- (-4,0) -- (-4,4) -- cycle; } 738 \only<7> { \fill[red!20] (0,0) -- (-4,0) -- (-4,4) -- (0,4) -- cycle; } 739 \only<1->{ 740 \draw (0,0) -- (16,0) -- (8,8) -- cycle; 741 \draw (8,0) -- (8,8); 742 } 743 \only<2-> { 744 \draw (0,0) -- (0,8) -- (8,8); 745 \draw (0,0) -- (-4,4) -- (0,8); 746 \draw (0,0) -- (-4,0) -- (-4,4); 747 } 748 \only<3-5> { \draw[dashed] (-4,0) -- (0,4); } 749 \only<4-5> { \draw[dashed] (-4,4) -- (4,4); } 750 \only<5-5> { \draw[dashed] (0,8) -- (8,0); } 751 752 \only<6-7> { 753 \draw (-4,0) -- (0,4); 754 \draw (-4,4) -- (4,4); 755 \draw (0,8) -- (8,0); 756 } 757 \end{tikzpicture} 758 \end{figure} 759 \begin{itemize} 760 \item<1-> Triangle bintree. 761 \item<2-> Split et merge. CLOD. 762 \item<8-> Défaut maximal visible à l'écran. 763 % TODO : Figure : Dessin projection pavé triangle erreur à l'écran. 764 \item<9-> Split queue et Merge queue. 765 % TODO : queues l'une au-dessus de l'autre, montrer qu'on va +- les priorités pour éviter le chevauchement. 766 \item<10-> Frustum culling : utilisation de drapaux. 767 \item<11-> Améliorations~: 768 \begin{itemize} 769 \item Triangle stripping. 770 \item Geomorphing. 771 \item Calcul différé des priorités dans les queues. 772 \item Temps réel. 773 \end{itemize} 774 \item<12-> $\tilde O(\text{Nb triangles mis à jour})$ 775 \end{itemize} 776 \end{frame} 777 778 \subsection{Geometry clipmaps} 779 \begin{frame} 780 \frametitle{Geometry clipmaps} 781 \begin{itemize} 782 \item Carrés concentriques avec des LOD différents. 783 \item Comme le mipmapping de textures. 784 \item Utilisation forte du GPU. 785 \item Displacement shader. 786 \item Remplissage à la jointure des LOD. 787 \end{itemize} 788 \end{frame} 789 790 \subsection{Notre algo} 791 \begin{frame} 792 \frametitle{Notre algorithme} 793 \begin{figure}[h] 794 \centering 795 \begin{tikzpicture}[scale=0.2] 796 \only<5->{ 797 \draw[red] (4,4) -- (0,0); 798 \draw[red] (4,4) -- (8,0); 799 \draw[red] (4,4) -- (8,8); 800 \draw[red] (4,4) -- (4,8); 801 \draw[red] (4,4) -- (2,8); 802 \draw[red] (4,4) -- (0,8); 803 } 804 \only<1->{ 805 \node[circle,fill=black,inner sep=1pt] at (0,0) {}; 806 \node[circle,fill=black,inner sep=1pt] at (16,0) {}; 807 \node[circle,fill=black,inner sep=1pt] at (16,16) {}; 808 \node[circle,fill=black,inner sep=1pt] at (0,16) {}; 809 \node[circle,fill=black,inner sep=1pt] at (8,8) {}; 810 \draw (0,0) -- (16,0) -- (16,16) -- (0,16) -- cycle; 811 } 812 \only<2->{ 813 \node[circle,fill=black,inner sep=1pt] at (8,0) {}; 814 \node[circle,fill=black,inner sep=1pt] at (8,16) {}; 815 \node[circle,fill=black,inner sep=1pt] at (0,8) {}; 816 \node[circle,fill=black,inner sep=1pt] at (16,8) {}; 817 818 \node[circle,fill=black,inner sep=1pt] at (4,4) {}; 819 \node[circle,fill=black,inner sep=1pt] at (4,12) {}; 820 \node[circle,fill=black,inner sep=1pt] at (12,4) {}; 821 \node[circle,fill=black,inner sep=1pt] at (12,12) {}; 822 \draw (8,0) -- (8,16); \draw (0,8) -- (16,8); 823 } 824 \only<3->{ 825 \node[circle,fill=black,inner sep=1pt] at (0,12) {}; 826 \node[circle,fill=black,inner sep=1pt] at (8,12) {}; 827 \node[circle,fill=black,inner sep=1pt] at (4,8) {}; 828 \node[circle,fill=black,inner sep=1pt] at (4,16) {}; 829 830 \node[circle,fill=black,inner sep=1pt] at (2,10) {}; 831 \node[circle,fill=black,inner sep=1pt] at (2,14) {}; 832 \node[circle,fill=black,inner sep=1pt] at (6,10) {}; 833 \node[circle,fill=black,inner sep=1pt] at (6,14) {}; 834 \draw (0,12) -- (8,12); \draw (4,8) -- (4,16); 835 } 836 \only<4->{ 837 \node[circle,fill=black,inner sep=1pt] at (0,10) {}; 838 \node[circle,fill=black,inner sep=1pt] at (4,10) {}; 839 \node[circle,fill=black,inner sep=1pt] at (2,12) {}; 840 841 \node[circle,fill=black,inner sep=1pt] at (1,9) {}; 842 \node[circle,fill=black,inner sep=1pt] at (3,11) {}; 843 \node[circle,fill=black,inner sep=1pt] at (1,11) {}; 844 \node[circle,fill=black,inner sep=1pt] at (3,9) {}; 845 \draw (0,10) -- (4,10); \draw (2,8) -- (2,12); 846 847 \node[circle,fill=red,inner sep=1pt] at (2,8) {}; 848 } 849 \end{tikzpicture} 850 \end{figure} 851 \begin{itemize} 852 \item Quadtree de carrés. 853 \item Triangle fans. 854 \item LOD en fonction de la distance. 855 \item Mise à jour de quelques branches seulement. 856 \item Temps réel. 857 \item $\tilde O(\text{Nb carrés mis à jour})$ 858 \end{itemize} 859 \end{frame} 860 861 \subsection{Streaming de scène} 862 \begin{frame} 863 \frametitle{Streaming de scène} 864 \begin{itemize} 865 \item Modèle client/serveur. 866 \item Tiles avec LOD maximal. 867 \item Qualité progressive des tiles. 868 \item Geometry clipmaps. 869 \item Démonstration. {\tiny\texttt{/usr/lib/xscreensaver/crackberg}} 870 \end{itemize} 871 \end{frame} 872 873 % \section{Conclusion} 874 875 % \begin{frame} 876 % \frametitle{Conclusion} 877 % \end{frame} 878 879 \begin{frame} 880 \frametitle{Sources} 881 % Génération 882 % * [Différents algos]() : Ridged Perlin Noise, Hills Algorithm, Craters, Erosion. 883 % * [Plein d'algos](http://planetgenesis.sourceforge.net/docs15/noise/noise.html#tileworley) dont plusieurs basés sur une sorte de voronoi donc à priori trop lents. 884 % * Affichage avec Ogre : [forum](http://www.ogre3d.org/forums/viewtopic.php?f=5&t=67177&p=442222), [doc](http://www.ogre3d.org/docs/api/html/classOgre_1_1BillboardSet.html) 885 \begin{itemize} 886 \item Perlin noise. {\tiny\url{http://freespace.virgin.net/hugo.elias/models/m_perlin.htm}} 887 \item {\tiny\url{http://www.gamasutra.com}} 888 \item {\tiny\url{http://vterrain.org}} 889 % \item Mojoworld generator (mojoworld.org) 890 \item {\tiny\url{http://world-machine.com}} 891 \item Algorithmes de bruit. {\tiny\url{http://www.sluniverse.com/php/vb/project-development/34994-automatically-generated-terrain-map.html}} 892 \item Composition d'algorithmes de bruit. {\tiny\url{http://www.gamedev.net/blog/33/entry-2249260-procedural-islands-redux/}} 893 \item Création de cartes polygonales. {\tiny\url{http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/}} 894 \item Pathfinding pour créer des rivières. {\tiny\url{http://www.umbrarumregnum.net/articles/creating-rivers}} 895 \end{itemize} 896 \end{frame} 897 898 \begin{frame} 899 \frametitle{À propos} 900 \begin{itemize} 901 \item Utilise pgf/tikz 2.10~.% TODO : url. 902 \item Graine aléatoire~: \noiseseed~. 903 \end{itemize} 904 \end{frame} 905 906 \end{document}