CGAL users discussion list

[Michael Balzer <>]

Apparently, the paper uses a distribution of points that is some kind of 
a Poisson disc distribution, which means that all points have a minimum 
distance to each other. Then simply the Voronoi tessellation of these 
points is generated, where CGAL can definitely help you -- check chapter 
25 or 33 of the manual for details.

The question that is left is how to generate such a distribution, and 
there are many different ways to do that, e.g. dart throwing, inserting 
points at the center of the largest empty circle, etc. Another very 
excellent (but slow) method, that generates high quality uniform 
distributions of points, are so-called centroidal Voronoi tessellations 
(CVT). These CVTs can be computerd iteratively by first computing a 
Voronoi tessellation of a random point set (using CGAL, for example), 
then moving each generator point in the center of the according Voronoi 
region, and repeat this procedure until the distance between generator 
and centroid is below a chosen threshold.


I hope this helped.
Kind regards,
Michael



ZhouBo schrieb:
> Greetings,
>    Thanks for your reply. The paper named "Incremental Instant Radiosity 
> for Real-Time Indirect Illumination", it showed some a example, sampled 
> some points on circle and sphere. I thought maybe it's a question 
> about Monte Carlo sampling, quasi or uniform. I do not know how to do 
> this with the help from CGAL.
>    Thanks again.
>
>
>
>
> ------------------------------------------------------------------------
>
>  > Date: Wed, 22 Aug 2007 10:00:08 +0200
>  > From: 
>
>  > To: 
>
>  > Subject: Re: [cgal-discuss] How to generate a random Voronoi Polygon 
> map ?
>  >
>  > Hi,
>  >
>  > what do you mean by "subdivide these polygons equally"? That there
>  > exists a uniform distribution of the points, or even that the sizes of
>  > the polygons are equal?
>  >
>  >
>  > Michael
>
> ------------------------------------------------------------------------
> ÖйúÊ®´óÈÈÃÅÂÃÓξ°µã Á˽â¸ü¶àÐÅÏ¢£¡ 
> <http://search.msn.com/results.aspx?q=%E4%B8%AD%E5%9B%BD%E5%8D%81%E5%A4%A7%E9%A3%8E%E6%99%AF&mkt=zh-CN&form=QBRE>