CGAL users discussion list

[Monique Teillaud <>]

Hi,

I would say that computing the 3D convex hull of the points is the 
simplest way to get their Delaunay triangulation on the sphere.
You will get a Polyhedron_3 (see the CGAL 3D convex hull chapter).

Each edge (line segment) of the convex hull projects to a circular arc 
on the sphere, that is an edge of the triangulation on the sphere.
The circumcenter of a facet of the 3D convex hull projects on the 
Voronoi center of the facet vertices, on the sphere.

The 3D spherical kernel, which will be released in CGAL 3.4, might help 
you playing further with your arcs. It will offer some functionality on 
circles and circular arcs in 3D.

Best,
        Monique Teillaud


 wrote:
> Hi,
>  
> I am a first time CGAL user and I am implementing an algorithm that 
> requires me to do the Delaunay tetrahedralization of a set of points in 
> 3D space. I also need the corresponding Voronoi diagram.
>  
> A little background information might clarify what I am trying to 
> accomplish: the algorithm is part of a global illumination simulation.
>  
> In the first stage, from the center of an omnidirectional point light, 
> several directions of light paths are traced. The vectors of these 
> directions are then mapped to the unit sphere (with its center at the 
> point light). These points on the unit sphere are the input points 
> (vertices) of the Delaunay triangulation. With this triangulation, I can 
> use the distance between the vertices (length of the edges) to calculate 
> the densest region. This allows the algorithm to remove points from a 
> dense region (which is oversampled) and add points to a sparse region 
> (which is undersampled).
>  
> In a second stage, I need to calculate the Voronoi diagram of these 
> points on the unit sphere. The surface area of the Voronoi regions or 
> cells, tells me how much "light" is beamed in a particular direction, 
> proportional to the total power of the point light source.
>  
> My first question would be: can I accomplish these two things using 
> CGAL? I am sure the first step is possible, but I don't know about the 
> second step.
>  
> The steps for stage 1 are as follows:
>  
> 1. I am generating points on the unit sphere (using a Halton 
> sequence). That is, I generate a set of points in 2D which are mapped to 
> the unit sphere.
> 2. These points (on the unit sphere), need to be triangulated in 3D, 
> that is, they are the input for the Delaunay algorithm.
> 3. I then need only the convex hull of the triangulation, the "inner" 
> edges must be discarded.
> 4. Finally, I need to be able to calculate lengths of the remaining edges.
>  
> Q1: I have successfully triangulated a set of points using 
> <Delaunay_triangulation_3>, however this yields a triangulation with 
> edges inside the convex hull (as opposed to only those "on" the convex 
> hull). I presume these edges cannot be "deleted" as it were from a 
> <Delaunay_triangulation_3>. I suppose it is possible to disregard these 
> edges during step 4 (length calculation of edges), but I feel that this 
> would be extremely cumbersome to do.
>  
> I therefore tried to use <Delaunay_d> to triangulate the 3D points. From 
> what I understand, the "furthest site" Delaunay triangulation is what I 
> need. That is a 3D triangulation with no interior edges. I am hoping 
> "std::list<Simplex_handle>  DT.all_simplices ( Delaunay_voronoi_kind k = 
> FURTHEST)" will yield the correct triangulation. I was in the process of 
> coding this, but I before I continue, I was hoping to find out for sure 
> whether this will get me anywhere.
>  
> Q2: Is it possible to use Cartesian coordinates with <Delaunay_d>? The 
> example uses Homogeneous coordinates. I have tried to use Cartesian 
> coordinates, but I haven't been successful as yet.
>  
> The steps for stage 2 are as follows:
>  
> 1. The points on the unit sphere (computed in stage 1, step 1) are reused.
> 2. From these points, a Voronoi diagram needs to be computed. That is, a 
> Voronoi diagram in 2D, but on the surface of the unit sphere.
>  
> Q3: Is this possible using CGAL? If not, does anyone know of a library 
> that is capable of doing this?
>  
>  
> Any and all help is greatly appreciated.
>
> ------------------------------------------------------------------------
> De nieuwe Hotmail maakt je leven nog makkelijker Wees er als eerste bij. 
> <http://www.windowslive-hotmail.com/comingsoon/nl/default.htm>