Как использовать CGAL для моделирования набора точек, движущихся по сфере?

Question

Я пытаюсь научиться использовать CGAL.У меня есть вопросы о том, какие структуры данных и схемы триангуляции использовать для моей задачи.

Описание проблемы:

У меня есть небольшое количество (<1000) частиц, движущихся посфера.Мне нужно сделать из этого облака точек треугольную сетку <em>Делоне .На каждом временном шаге мне нужно:

1. Перемешать облако точек, только если требуется, чтобы критерий Делоне все еще выполнялся.Сохраняйте связность сетки независимо от координат точек.
2. Сохраняя топологию фиксированной, проведите некоторую оптимизацию, используя итеративный решатель для вычисления новых положений частиц.Количество решающих итераций может составлять 100 или более при одинаковом соединении.На каждой итерации для вычислений требуется площадь каждого треугольника и некоторые вычисления для вершин, соединенных ребром (то есть каждая вершина взаимодействует с первым кольцом ближайших соседей).

Вопросы:

1. Как изменить координаты точек, связанных с вершинами сетки (структура данных триангуляции, сетка поверхности, многогранники и т. Д.), Не отменяя итераторы или циркуляторы триангуляции?
2. Как проверить, когда требуется пересчет?
3. Какая структура данных дает самый быстрый доступ ко всем ребрам и граням за один проход по всей сетке?Каждое ребро разделено между двумя треугольниками.Расчеты по краям самые дорогие.Следовательно, я хочу рассчитать для каждого ребра только один раз.Итерации по всем граням и отдельно по всем ребрам могут быть менее эффективными.

Пожалуйста, дайте мне знать, если требуется дополнительная информация.

Answer 1

Частично отвечая на ваши вопросы:

3 / Вы можете использовать библиотеку openmesh для построения сетки ваших очков.Это позволяет очень быстро достичь первого кольца соседей, как объяснено здесь , а также всех ребер и граней.Я не могу быть уверен, что именно структура данных обеспечивает самый быстрый доступ к этой информации.Чтобы дать вам подсказку о том, какую скорость ожидать, в своей работе я использую openmesh: выполнение 30 циклов for, каждый цикл проходит по первому кольцу соседей 500 000 вершин моей сетки и вычисляет некоторую арифметику (обычно центр тяжести).), в общей сложности занимает менее 100 мс.

1 / С помощью openmesh вы можете в любое время сбросить позицию точки без изменения ее связности (она не удалит уже определенные ребра и грани).

2 / Чтобы проверить, нужно ли повторное смешивание, вы должны проверить, выполняется ли условие Делоне в каждой точке вашей сетки.Если это не так, снимите целые или поменяйте местами подходящие края.

Надеюсь, это поможет!