CGAL users discussion list

[Tauheed Farhan <>]

________________________________________
From: Sylvain Pion 
[]
Sent: 07 January 2010 17:52
To: 

Subject: Re: [cgal-discuss] Scalable Delaunay Triangulation 3D

Tauheed Farhan wrote:
>   I have a problem I have 173 million data points and I want to do 3d 
> delaunay triangulation

Interesting.

>   I run out of memory after doing 6million because the incremental 
> algorithm adds "auxiliary" vertices which i dont use.

I'm puzzled by your sentence.  Which vertices don't you use ?
The only vertices added by the Delaunay triangulation are the points that
you pass to it.  Are there some of them that you would like to get rid of
to avoid building the full Delaunay triangulation ?


I meant the algorithm adds additional vertices while computing the delaunay 
triangulation . they call them infinite vertices which are far more than the 
actual vertices,
http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/TriangulationDS_3/Chapter_main.html
I dont care about these infinite vertices which the algorithm adds, my 
concern is only with the actual vertices I gave as input.
The algorithm fills up my 2GB memory after inserting 6 million points. I'm 
using triangulation_hierarchy_3 class which builds the delaunay incrementaly
I have a 32bit windows machine and cannot access more than 2GB of main memory 
per application 


>   Can any one help me out to implement a disk based "external memory" 
> implementation?

I never went as far as 173M.  I think the largest I tried was 50M (random) 
points,
it went smoothly on a 16GB machine, using normal swap and doing nothing 
special
(due to the local swap-friendly order which is used).
This technique is simplistic, but might work.

I have not seen more involved schemes implemented with CGAL so far, although
there is related out-of-core non-CGAL work (e.g. by Martin Isenburg et al).

I'm interesting in helping on this.


I'm checking Martin Isenburg work on streaming delaunay thanks a lot for the 
link
If i understood you correctly you are suggesting I do the delaunay 
triangulation on partitions of data that can fit in memory and swap the 
result of delaunay 
in and out of memory. how would I stitch the results of delaunay 
triangulation of different partitions together if I follow this path?.
 I'm not sure if i fully understood when u mentioned the local swap friendly 
order

many thanks again mate
Farhan



--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss