upd: см. по тэгу gjk, там есть ещё немного объяснений.
также смотри великолепную презентацию от Erin Catto на GDC 2010. я, конечно, о ней вспомнил только тогда, когда уже и без неё разобрался — а зря. потому что там как раз для идиотов нормальных существ расписано всё.
— это просто. то есть, если применять его в полной форме, то чуть сложнее, а для случая «проверить, столкнулись ли два выпуклых полигона» — просто.
статья на педии, как обычно, упускает самое интересное: волшебную функцию `NearestSimplex()`, в которой и заключена основная магия. и ещё мелочи.
во-первых: «симплекс», о котором там постоянно пишут — это просто массив с точками. для 2д случая их три, для 3д — четыре. ну, вы поняли: на единицу больше, чем измерений. это не зависит от фигур, это константа. уже круто.
во-вторых: операция «добавление точки в симплекс» — просто обычная операция заталкивания точки в стек. самая старая точка при этом тупо выкидывается, потому что она слабое звено, и больше не нужна. ну ок, не всегда самая старая: на самом деле точку надо выбирать ненужную, а не старую. об этом позже.
`Support(dir)` — это ещё проще. примерно вот так для polytope (полигона, в случае 2д):
// dumb O(n) support function, just brute force check all points
vec2 support() (in auto ref vec2 dir) const {
vec2 furthestPoint = vertices[0];
auto maxDot = furthestPoint.dot(dir);
foreach (const ref v; vertives[1..$]) {
auto d = v.dot(dir);
if (d > maxDot) {
maxDot = d;
furthestPoint = v;
}
}
return furthestPoint;
}
всё. в принципе, для мелких полигонов это даже нет смысла как-то оптимизировать.
если кому не ясно, то это просто нихрена не оптимизированый код для: «если двигаться по лучу (0,0)-dir, то какая вершина будет дальше всего?» важное замечание: здесь подразумевается, что вершины полигона хранятся в world coordinates, а не в object coordinates. не наебнитесь, а то нихера не заработает.
`D` (направление «расширения» симплекса) надо усердно менять (иначе алгоритм не будет работать). как? да хоть случайно. но лучше более-менее осмысленно. и тут мы приходим, наконец, к `NearestSimplex()`.
итак. что же такое, на самом деле, наш «симплекс»? рассмотрим 2д случай, он проще. наш «симплекс» — это ничто иное, как часть выпуклого полигона, находящегося в районе (0,0) aka origin. треугольник. весь алгоритм, по сути, делает вот что: использует один из вариантов minkowski sum (это всего лишь каждая точка одного полигона, приплюсованая к каждой точке другого; полная minkowski sum, соответственно, содержит n*m точек, и иногда вообще несохраняема; но нам полная и не нужна) двух выпуклых фигур, чтобы определить, содержит ли полученый после сложения многоугольник (он тоже выпуклый, это фича minkowski sum) origin. если содержит — то есть пересечение.
так вот. на каждом шаге мы рассматриваем только треугольный кусочек «суммарного многоугольника». если алгоритм будет постоянно выбирать разные точки, то рано или поздно он переберёт их все, и получит искомое. да, это тупой перебор.
когда перебор заканчивать? два варианта: 1. если наш треугольник содержит (0,0), то всё, есть пересечение, больше делать нечего. 2. если перебрали всё, а origin так и не попал внутрь.
второй вариант тесно связан с выбором куска для рассмотрения. как же выбрать этот кусок? а очень просто! помните наш `D`, который ничто иное, как «направление, в котором мы ищем границу суммарного полигона»? то есть, это направление от origin, в котором надо выбирать новые точки для симплекса.
теперь вспомним, что наш «симплекс» — это просто треугольник. каждое из рёбер треугольника — линия, которая делит пространство на два полупространства. то полупространство, которое содержит внутреннюю часть треугольника, нас нафиг не интересует (очевидно: мы уже убедились, что наш треугольник не содержит origin — иначе алгоритм бы завершился). так что рассматриваем другое полупространство. если оно содержит origin, то мы нашли новое направление: это перперндикуляр к нашей линии в направлении origin. выкидываем из симплекса ту точку, которая не принимает в нашей линии участия, и запускаем новую итерацию в выбраном направлении.
вот тут может случиться так, что ни одно полупространство не содержит (0,0). и это есть наша удача! на этом месте можно смело говорить, что фигуры не пересекаются, и завершать перебор. очевидно, что если ни одно полупространство из трёх возможных origin не содержит, то совершенно неважно, какое из них выбирать, так что в этом случае берите первое попавшееся.
маленький нюанс: на первой итерации у нас есть только две точки, а не три. ну и пофигу: всё то же самое, только рассматриваем оба возможных полупространства, и никакие точки из «симплекса» не выкидываем (потому что в нём есть свободное место).
3д особо ничем не отличается, только там не треугольники, а эти, как их, чертей… tetrahedrons.
а теперь небольшое дополнение: за что любят gjk. представим, что в нашем мире кроме фигур, заданых набором вершин, есть ещё и фигуры, заданые параметрически. например, окружность, которая задана центром и радиусом. очевидно, что «вершин» у окружности бесконечно много, одна ничем не лучше другой, и пересечение многоугольника с окружностью надо тоже решать формулами, которые выводить из параметрического представления. и так для каждой новой параметрической фигуры, и для их комбинаций. мазафака какая-то.
а вот с gjk это всё похеру: надо только уметь получать «самую дальнюю точку в направлении dir», и всё. для окружности, например, так: `dir.normalized*radius+center`. и никаких сложных формул взаимного пересечения! и вершины не надо генерировать. очевидно, что эллипсы, капсулы и прочие выпуклые интересные вещи будут не сильно сложнее.
ах, да: полная форма GJK позволяет определить минимальное расстояние между непересекающимися фигурами, и найти их ближайшие точки. тоже очень полезная вещь. а EPA (aka expanding polytope algorithm, ещё одна итеративная фигня) позволяет для случая пересечения найти минимальный вектор, на который надо отодвинуть одну из фигур, чтобы они перестали пересекаться. тоже полезно (и тоже очень просто, но об этом в другой раз как-нибудь).
спасибо, что были с нами всё это время, и прочитали эту простыню. не думаю, что вам стало сильно понятней, чем было в начале, но зато понятней стало мне.
p.s.: ах, да. теория без практики говно, конечно. поэтому вот вам практика: GJK+EPA для 2D.
>статья на педии, как обычно, упускает самое интересное
раз уже на простыню потратил время, то чему бы не потратить ещё ~n времени на перевод и викификацию? давай, не ленись, можно по 15 минут в день, а через неделю дополнить статью
![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small}