|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Eugene Kilachkoff 2:5020/400 07 Oct 2001 16:28:46
To : Andrey Glazunov
Subject : Re: опознать пересечение треугольников
--------------------------------------------------------------------------------
> представь 2 очень вытянутых треугольника, лежащих "крест накрест" -
> ни одна вершина не лежит внутри другого, а общая область есть.
Да, уже сообразил.
> мож кто хоть напомнит как задается область, охватываемая треугольником
> на плоскости ? из всего что помнится со школы так это уравнение
Вот отсюда и надо плясать. Щас объясню. Треугольник это частный случай
симплекса. Те в двухмерном случае - это выпуклый многоугольник. Который
задается системой линейных функций ( уравнение прямой ). Пусть x - вектор на
плоскости, f(x) - уравнение прямой, фактически скалярное произведение нормали
к прямой на вектор x. Каждая такая фция делит плоскость на две части: f()>0 и
f()<0. Тогда треугольник задается тремя линейными ф-циями f1(x), f2(x) и
f3(x). Точки в области где все три ф-ци >= 0 - принадлежат треугольнику.
А метод такой. IMHO следующее утверждение справедливо всегда ( доказывать
влом). Треугольники A и B не пересекаются, только если треугольник B невидим
хотя бы из одного угла треугольника A. Треугольник считается видимым из угла,
если хотя бы одна точка лежит внутри этого угла.
Задаем треугольник A в виде набора ф-ций. И вычисляем знак Fi(Bj). Те
проверяем все точки треугольника B, относительно сторон A.
1. Если найдется такая точка, для которой все три Fi() будут положительны, то
задача решена, ответ положительный. Точка просто лежит внутри треугольника.
Дальше начинаем рассматривать углы, те все Fi попарно. Для простоты рассмотрим
F1 и F2. Как проверять видимость треугольника из угла:
2. Если для всех точек Bj хотя бы одна ф-ция (F1 или F2) меньше 0, то
треугольник из этого угла невидим.
3. Если какая либо точка лежит внутри угла, те F1(bj)>0 и F2(bj)>0, то ответ
однозначный: точка видима. И смотрим следующий угол (другую пару прямых).
4. Самый нехороший случай. Когда не подходят случаи 2 и 3. Здесь так просто не
отделаться, придется нудно считать. Возможно, самым простым способом будет
проверить пересечение не A с B, а B с A. Посмотри на алгоритм, это не одно и
то же.
Да, и еще одно. Если ты делаешь collision detection и при условии, что у тебя
треугольники двигаются со скоростями порядка средних линейных размеров самих
треугольников, то довольно маловероятно, что возникнет описанный тобой случай.
Чаще всего на одном кадре треугольники будут находиться близко друг от друга,
а на следующем уже одна из вершин будет находиться внутри.
Hужно всего лишь проверить вершины A на попадание внутрь B и если нет, то
проверить еще и B на попадание в A. Если и в этом случае пересечения нет, то
можно считать, что пересечения нет на самом деле. Этот алгоритм тоже не
отлавливает твой случай, однако он достаточно редкий, а кроме того для его
наступления нужно, чтобы треугольники "проткнули" друг друга, те в какой то
момент вершины одного находились внутри другого. Тогда алгоритм это отловит и
просто не допустит "плохого" случая.
Если же ты делаешь 3d-engine и тебе нужно проверить треугольник на попадание в
экран, то нужно применить _оценку_. Точнее оценку HЕпопадания. Hапример, если
у тебя все вершины лежат скажем в отрицательной области одной из ф-ций,
задающих экран, то треугольник точно не попадает в экран. В остальных случаях
просто отсекай.
Короче, куча идей :-)
--- ifmail v.2.15dev5
* Origin: home (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
