Реализация триангуляции

[Schrodinger's cat]

Всем доброго здоровья и хорошего настроения.
Изучаю методы триангуляции, хочу сам запрограммировать одно, два...
Прочитал книгу Скворцова "Триангуляция Делоне и ее применение", прочитал/посмотрел наверное большую часть того что доступно по запросам поисковика "триангуляция".
Скажите/разъясните пожалуйста:
1) Поисковик все запросы на тему триангуляции заваливает в сторону "триангуляция Делоне" и того же Скворцова.
Посоветуйте пожалуйста источники описывающие триангуляции НЕ Делоне.
В частности интересует вопрос а как сделать абы какую триангуляцию, но максимально быстро.
2) В книге, да и источники инета, описывают структуры данных, они понятны, но я не обнаружил никаких рекомендаций по поводу реализации операций, таких как флип и получение четвертой вершины в системе из двух треугольников для теста Делоне.
Что тут смущает. То, что в структурах данных треугольника например есть ссылки на смежные треугольники, но как эффективно понять а какой гранью они соприкасаются? Наивный алгоритм понятен - прямой перебор вершин и выяснение таки какими ребрами они соприкасаются и дальше я уже могу получить четвертую точку.
Тоже самое чтобы сделать флип нужна куча переборов.
Это кажется вычислительно сложным. Есть ли способы это сделать эффективно? Сам придумать пока не смог.
Возможно это очевидные для всех вещи, но я пока не въехал.
3) Вопрос около темы.
Есть такая игра empyrion galactic survival, возможно кто то играл...
Там реализована система бурения ландшафта и астероидов.
Интересно как они это сделали. Работает быстро, сетка нерегулярная, треугольники если присматриваться примерно одинакового размера плюс минус.
Возможно у кого то есть догадки?

Заранее благодарю за ответы.
Да, задача пока что построение плоской триангуляции.

[John Maller]

Если надо быстро - делим область на треугольники как угодно. Получившиеся треугольники рекурсивно делим на 4 части. Можно и 2 и 3, но если 4 стороны равнее. Если область равносторонний треугольник все полученные стороны будут в точности равны.

Если область не треугольник, окружаем её треугольником, триангулируем треугольник, убираем лишнее.

Или проводим триангуляцию полигона (это другой алгоритм), а дальше также делим треугольники. Это хуже, стороны будут не равны. Но убирать лишнее не придётся, что может быть преимуществом.

-- 06.06.2024, 15:28 --

Schrodinger's cat в сообщении #1639312 писал(а):

Есть такая игра empyrion galactic survival, возможно кто то играл...
Там реализована система бурения ландшафта и астероидов.
Интересно как они это сделали. Работает быстро, сетка нерегулярная, треугольники если присматриваться примерно одинакового размера плюс минус.
Возможно у кого то есть догадки?

Современные видеокарты сами считают триангуляцию. Это для них хорошая задача - параллелится легко.

[Schrodinger's cat]

Триангуляцию Делоне разобрался, реализовал, работает.

Структура данных у меня Треугольник содержащий 3 ребра. В каждом ребре ссылка на конечную точку ребра, ссылка на следующее ребро треугольника, и ссылка на ребро смежного треугольника.

John Maller в сообщении #1641654 писал(а):

Получившиеся треугольники рекурсивно делим на 4 части. Можно и 2 и 3, но если 4 стороны равнее.

Извините не понял. Я сперва сделал триангуляцию "абы как". Сперва сделал "супер квадрат" из двух треугольников в которые я уже добавлял все точки. Для добавления точки ищу треугольник в который попадает точка и делю его на 3 треугольника. Триангуляция при этом получается весьма плохая, все треугольники тонкие.
Потом зачем мне делить на 4 части? И что делить не понимаю?

John Maller в сообщении #1641654 писал(а):

Современные видеокарты сами считают триангуляцию. Это для них хорошая задача - параллелится легко.

Тут я не понимаю следующее.
Допустим у нас есть некий меш. Допустим формы метеорита, сфероид. Этот меш соткан из примерно одинаковых треугольников.
Я начинаю его "бурить лазером" при этом в нем образуется дыра.
Вот начало этого процесса еще можно понять.
Вычисляю рейкаст луча с объектом, нахожу точку пересечения и треугольник пересекшийся с лучом.
Теперь я могу например вычитать небольшую сферу из объекта. Вдавливаю ее в объект и образую в нем новые треугольники, тем самым образую дыру от бура. Способ примерный, понятно что это еще не конечный алгоритм.
Непонятно дальше. Вот когда мы пробурили уже насквозь, как узнать точку на тыльной стороне объекта? Ясно что тот же рейкаст даст ее. Если объект небольшой все сработает.
Но я не понимаю каким образом они находят ее на таком объекте как ландшафт. Там дофига треугольников и этот рейкас просто не в состоянии будет работать в реалтайме.

Посоветуйте пожалуйста что то почитать как реализуют такую задачу. Хочу типа лазером дырявить меши.

[worm2]

Schrodinger's cat в сообщении #1643174 писал(а):

Там дофига треугольников и этот рейкас просто не в состоянии будет работать в реалтайме.

Насколько дофига? Если до миллиона — по моим прикидкам, CPU в один поток должен справиться. Если больше — то не знаю.

[Schrodinger's cat]

Точно не знаю, но думаю что ДО.
Хм... спасибо за ответ.