Search code examples
data-structuresmeshcgalopenmesh

How to use CGAL to model a set of points moving on a sphere?

I am trying to learn using CGAL. I have questions about which data structures and triangulation schemes to use for my problem.

Problem description:

I have a small number ( < 1000) of particles moving on a sphere. I need to make a triangular Delaunay mesh out of this point cloud. At every time step, I need to:

  1. Remesh the point cloud, only if required, so that the Delaunay criterion still holds. Store the mesh connectivity independently of the point coordinates.
  2. Keeping the topology fixed, do some optimization using an iterative solver to calculate new particle positions. The number of solver iterations can be 100 or more with the same connectivity. At each iteration, the calculations require area of each triangle and some calculations on vertices connected by an edge (i.e. each vertex interacts with first ring of nearest neighbors).

Questions:

  1. How can I change the coordinates of the points associated with mesh (triangulation data structure, surface mesh, polyhedra etc.) vertices without invalidating the iterators or circulators of the triangulation?
  2. How to check when remeshing is required?
  3. Which data structure gives fastest access to all edges and faces in a single pass over the full mesh? Every edge is shared between two triangles. The calculations on the edges are the most expensive. Hence, I want to calculate for each edge only once. Iterating once over all faces and separately over all edges may be less efficient.

Please let me know if any more information is required.

Solution

  • Giving part answers to your questions :

    3/ You can use openmesh library to mesh your points. It allows one to reach the first ring of neighbours very fast as explained here, and also all edges and faces. I can't be sure if it is the data structure that gives the fastest access to these informations. To give you a hint of what speed to expect, In my work I use openmesh : running 30 'for' loops, each loop going over the first ring neighbours of the 500 000 vertices of my mesh and computing some arithmetics (typically center of gravity), takes in total less than 100ms.

    1/ With openmesh, at any time you can reset a point position without changing its connectivity (it won't delete already defined edges and faces).

    2/ To check if remeshing is needed, you have to check wether Delaunay condition is still satisfied at every point of your mesh. If it is not, remesh the whole or swap suitable edges.

    Hope this helps!