Comments 15
Ещё можно SDF использовать:
https://en.wikipedia.org/wiki/Signed_distance_function#Applications
https://iquilezles.org/articles/distfunctions2d/
https://iquilezles.org/articles/interiordistance/
SDF как приближенное решение - да. А все описанное в статье - логично. Но не решает задачу на практике. Для начала нужно написать алгоритм, который сможет корректно отработать просто два треугольника. Решение для 95% случаев пишется за день. Для остальных 5% случаев за время, которое сложно оценить 😂 Может занят годы. Из-за неточностей и округлений. Когда надоест, можно посмотреть на библиотеку Manifold. Единственную из тех, что мне попадались, где все это корректно продумано. Да, она 3D, но это не меняет сути вопроса. И обязательно почитать диссертацию, на которую они ссылаются. Если в итоге получится рабочее собственное решение, нужно сделать много-много текстов на всякие пограничные случаи.
Не надо тратить годы, уже всё потрачено другими людьми. Тут достаточно одного предиката orient2d. Там же Джонатан Шевчук и сишный код выложил, причём в public domain.
Не работал с orient_2d. Быстрый поиск сказал, что это это при ориентацию треугольника. Если в ней больше ничего нет, то это самая наименьшая проблема в задаче булевых операций между двуми треугольниками. Так другие проблемы с точностями и округлениям возникают в части согласованности трактовок разных кейсов. У меня была продакшн задача, где требовалось гарантированное робастное решение. Ух, сколько проблем вылезло. CGAL, libIGL многие другие известные библиотеки не справлялись пр разному. CGAL просто крашился на сложныз случаях. libIGL не справлялся нормально, когда из одного треугольника нужно было вычесть десять и т.д. Задача кажется простой, но...
Да, ориентация треугольника, оно же определить, лежит ли точка на данной прямой, заданной двумя другими точками, и есть самое сложное в этой задаче. Ну, есть ещё нюансы из разряда того, что не все точки являются непосредственно данными вашей задачи, многие из них получаются, например, пересечением двух отрезков, а их нельзя просто так представлять с плавающей точкой, зачастую нужна будет точная арифметика. Но в двумерном случае это всё уже давно решено, годы тратить не надо.
Да вы правы, задача имеет не мало подводных камней, в основном связанных с точностью вычислений. Например, такая казалось бы тривиальная проблема, как определение принадлежности точки прямой, становится не однозначной при работе с числами с плавающей точкой. В случае целочисленных вычислений возникают свои трудности, например, в вопросе: определения точки пересечения отрезков (0, 0)-(4, 0) и (1, -2)-(2, 2)? Это (1, 0) или (2, 0)? Оба этих решения не лежат на обоих отрезках, что приводит к искажению изначальной картины.
Однако, несмотря на сложности, эти проблемы можно решить, если принять ряд условностей. В этой статье я сознательно опустил ряд сложных деталий, чтобы сфокусироваться на основной концепции. Но, судя по вашему интересу и комментариям, тема действительно заслуживает продолжения.
решал сам задачу нахождения контура объединения большого количества полигонов на Delphi, несколько лет назад, потратил недели 2, действительно застрял на большом количестве исключительных случаев и неоднозначностях при округлении, до уровня продакшн не дошел, пользовался алгоритмом Вейлера-Азертона, наиболее толковое описание было на сайте cyberpedia.su, к сожалению сейчас эта ссылка не работает, на всякий случай оставляю https://cyberpedia.su/12xe1f0.html может кто найдет в архивах. В этой же статье (текущей) концептуально сложный алгоритм обхода и составления составного контура фактически пропущен.
Вот нашел работающую ссылку https://stydopedia.ru/2xbba8.html?ysclid=m0tpogrb9d367647596
Я пробовал данный алгоритм лет 5 назад, в нем гораздо сложнее победить дегенеративные случаи: общие вершины, ребра, элеменирующие ребра. Нет четкого подхода как их обрабатывать, остаешься с этим один на один. Мне так и не удалось довести результат до того, что бы он был корректен при любых входных данных. Из единственного плюса могу отметить его кажущуюся простоту.
У меня та же история. Верю что есть лучший, только вы его не расписали. По вашему тексту описан этот же алгоритм, только на пальцах, без формализации.
С вырожденными случаями не надо бороться вручную. Для этого придумали SOS.
Была клевая игрушка, предок червяков - scorched earth, https://ru.m.wikipedia.org/wiki/Scorched_Earth
Как раз с векторной графикой
Вообще, что лучше для подобных 2D игр - растр или вектор, - зависит от требуемой детализации разрушений ландшафта. У растра вычислительная сложность постоянна в течение всей игры и пропорциональна size^2, а у вектора растёт в процессе разрушения ландшафта, в связи с чем нужна процедура упрощения контура (очистки от мелких деталей).
В случае 3D, воксели (сложность ~ size^3) лишь недавно, с появлением мощных GPU, смогли составить конкуренцию полигонам из-за огромного потребления памяти и вычислительных ресурсов. В то же время игры с полигональным разрушаемым ландшафтом могут быть очень лёгкими и нетребовательными (пример экстремальной оптимизации - игра-демо Sumotori dreams в 96 кб). Но есть также ряд игр, использующих промежуточный подход, в котором мир состоит из блоков более или менее одинаковой формы (в серии Worms это Worms 3D).
У растра вычислительная сложность постоянна в течение всей игры и пропорциональна size^2
Такие игры не делал, но из здравого смысла никак не могу понять, для чего там такая сложность. При движении достаточно проверить пиксели под игроком (не провалится ли) и пиксели перед игроком (может ли ползти дальше) - это никак не зависит от размера карты, т.е. сложность O(1). То же самое при обработке взрыва - достаточно занулить пиксели в окружности данного радуса, центр которой известен. Опять O(1). Результат не меняется и при переходе в 3Д.
Если же у нас ландшафт задан набором фигур - это, конечно, кошмар. Проблемы начинаются везде, начиная от определеня точки пересечения снаряда с землей. И я не верю вышеидущему комментарию, что scorched earth сделан на векторной графике, особенно вспоминая как там разливается напалм.
Если бы я делал подобные игры, то конечно остановился бы на варианте с дискретной сеткой (для 2Д), в пределе - размером с пиксель, но можно и больше
Отличная статья.
Ещё Perimeter у K-D Labs векторный и ландшафт модифицирующий.
Он и в opensource выложен... https://github.com/KD-lab-Open-Source/Perimeter
Булевы операции двумерных тел