CGAL users discussion list

[Shuchu Han <>]

Dear Pedro

sorry for the late reply  and thanks for your reply. After I posted my last email, I did some test about these two operations ( not "exact" one )  and the results was the same as you said. 

I am going to read the paper you recommend. Thanks again!

regards

shuchu

2009/12/11 Pedro Machado Manhães de Castro <>

Hello,

As far as I understood, you are within a static setting since you know the next position of all the points, and all your points move.
Then, in general, your approach (2) is better (rebuilding). Allow me to show you a better way to do that.
Instead of maintaining 1 original and 1 copy of such a huge triangulation, and swapping them, you can do as follow:

Have a container (list, vector) with all the new positions (several Point_3) and simply do
tr.clear();
tr.insert(points.begin(), points.end());

Depending on your application there are two methods that have shown some quality in practice (improve on rebuilding for some data-sets) for Delaunay triangulations:

(static setting) Heuristics + Flipping:
Leonidas Guibas and Daniel Russel
An empirical comparison of techniques for updating Delaunay triangulations.
SCG '04: Proceedings of the twentieth annual symposium on Computational geometry, pages 170-179.

(dynamic setting) Filtering Relocations:
Pedro Machado Manhães de Castro, Jane Tournois, Pierre Alliez, and Olivier Devillers.
Filtering relocations on a Delaunay triangulation. Computer Graphics Forum, 28:1465-1474, 2009. Note: Special issue for EUROGRAPHICS Symposium on Geometry Processing.

Best regards,
Pedro Machado Manhaes de Castro

On Fri, Dec 11, 2009 at 6:41 AM, Shuchu Han <> wrote:

Hi, all

Currently, I'm doing some isotropic remeshing jobs. I try to remesh  a Delaunay triangluation_3 which has 1~5 million vertices.

At the end of each optimization step, the location of the vertices will be update to another place.  and as i know, there are two method to finish this update:

1)  using one triangulation object and use the   "Triangluation_3::move_point()"  operation;

2) using two copy triangulation objects.  and  use the "t.swap ( Triangulation_3 & tr)" operation to update the whole triangulation. 

Is there any one know the efficient between these two operations, which one is more fast?

Best regards

shuchu