Page principale | Projets | Publications | Thèses | Présentations | Membres | Cours | Gallerie | Intérêt local
Home | Projects | Publications | Theses | Presentations | People | Courses | Gallery | Local interest

 Echantillonnage basé sur les tuiles de Penrose et
applications en infographie


Sampling is a process that is omnipresent in computer graphics. Specifically, it plays an important role in the estimation of integrals used in digital image synthesis. It is also used in digital halftoning, image processing, as well as geometric modelling. There is no definitive sampling strategy that can ensure the best results in all cases ; regular sampling proves to be inefficient and often detrimental to the quality of the results, because it can introduce a bias that can manifest itself as aliasing. Pure stochastic sampling also has its problems, notably due to the variance in the results. Many researchers have thus studied this problem, and there are many sampling strategies used in computer graphics.

Our research focuses on using the Penrose tiles to address the sampling problem. It so happens that this set of tiles harbors certain properties that can be exploited in this context. This thesis presents two contributions that stem from this research.

The first article presented, Fast Hierarchical Importance Sampling with Blue Noise Properties, proposes a sampling system based on Penrose tiles. Given an importance density function in two dimensions, the system can generate a discrete sample distribution, in which the local point density is proportional to the given function, with a local blue noise distribution. Our technique is amongst the fastest, yet it is also amongst the best in terms of quality.

The second article presented, Fast Triangulated Importance Sampled Point Sets, proposes a system that can not only generate point sets as in the prior system, but can also build a Delaunay triangulation of these points. Our method exploits certain properties of sampling with Penrose tiles in order to obtain an efficiency greater than all known Delaunay triangulation algorithms.


Echantillonnage, bruit bleu, tuiles de Penrose, numérotation de Fibonacci, rendu, cartes d'environnement, triangulation de Delaunay


Online version

Available here (mostly in English) in Adobe PDF format (2.3 MB).


  author =       "Charles Donohue",
  title =        "Echantillonnage basé sur les tuiles de Penrose et applications en infographie",
  month =        sep,
  year =         2004,
  type =         "M.Sc. Thesis",
  school =       "D{\'e}partement d'Informatique et Recherche 
                  Op{\'e}rationnelle, Universit{\'e} de Montr{\'e}al",