Коллизии полигона с... не знаю, как назвать.

[Mikle]

В 3D пространстве имеется полигон, заданный массивом вертексов. Вертексы лежат в одной плоскости, которая в общем случае не параллельна плоскости XoZ, но плоскость не вертикальна, её проекция на XoZ имеет ненулевую площадь. Лицевой считается верхняя часть полигона, её нормаль заранее вычислена.
Сверху вниз вдоль строго вертикальной оси с известными координатами X и Z опускается сфера с радиусом R.
Необходимо узнать, коснётся ли сфера полигона. В случае касания нужно найти Y координаты центра сферы в момент касания и нормаль в точке касания. Под нормалью подразумевается вектор, направленный из точки касания к центру сферы.
Это всё желательно сделать оптимально с точки зрения быстродействия.

Я разделил задачу на три части:

1. Проверка касания с внутренней областью полигона.
Это проверяется просто. Умножаем нормаль полигона на -R, X и Z полученного вектора V прибавляем к X и Z оси сферы - если точка лежит внутри проекции полигона на XoZ, то соответствующая точка сферы - это и есть место касания, из координаты Y этой точки вычитает Y вектора V - получаем Y сферы в момент касания, нормаль равна нормали полигона.

2. Проверка касания с рёбрами полигона поочерёдно.
Тут основная загвоздка. Будь полигон параллелен XoZ, было бы просто - если проекция оси на XoZ (точка) проецируется на проекцию ребра на эту же плоскость, попадая между вершинами этого отрезка, и длина линии W последней проекции меньше R, то получили касание. Считаем W одним катетом, достраиваем второй вдоль Y ток, чтобы гипотенуза была равна R, получаем нормаль в точке проекции, высота тоже вычисляется не сложно, не буду останавливаться.
Но, когда полигон не параллелен XoZ, проекция на XoZ уже не помогает, радиус сферы не будет перпендикулярен проекции ребра на XoZ. Он будет перпендикулярен при проекции сферы на плоскость полигона, но в этом случае мы получаем невертикальную ось, её проекция уже не точка, а линия. Всё как-то сильно усложняется.

3. Проверка касания с вершинами полигона поочерёдно.
В случае выпуклых углов проекции оси могут не попасть на рёбра, но сфера касается вершины между ними. Поэтому проверяем касания с вершинамы, это просто - считаем отрезок, соединяющий проекцию оси сферы с проекцией вершины на XoZ отрезком W из предыдущего пункта, дальше так же.

Просьба поделиться мыслями по второму пункту, либо, возможно, вообще по альтернативному варианту решения задачи.

[Sam777e]

Я плохо понял; беру модельный пример и изучаю пункт 2:

сфера радиуса R = 10 спускается по оси Y, полигон лежит в плоскости XoZ и его вершины (0;-1 / 0;2 / 3;2 / 3;-1). Где здесь W и какова ее роль ? Сама точка касания и нужная нормаль сферы ясны . На всякий случай - речь именно о касании, не пересечении ? Короче, растолкуй, пожалуйста, приведенный пример.

[Mikle]

Где здесь W и какова ее роль ?

Если рассматривать 2D вариант в XoZ, то ось (точка) проецируется на прямую, содержащую ребро, получаем точку M. Если точка попала в отрезок (ребро), то линию, соединяющую точку M с осью я и назвал W.

[Sam777e]

Мои нечеткие мысли.

Прямая, по которой движется центр сферы и прямая ребра полигона - скрещивающиеся прямые.
1. Если расстояние между ними больше R то нет касания.
2. Иначе это как раз величина "горизонтального" катета.

http://mathprofi.ru/zadachi_s_pryamoi_v_prostranstve.html

Здесь подробно, в частности, о нахождении точки на прямой ребра, из которой торчит общий перпендикуляр. Зная эту точку, легко определяем лежит ли она внутри отрезка-ребра или нет.
Мне кажется, что в случае "нет" надо изучать пункт 3.

[Debugger]

Если

Вертексы лежат в одной плоскости

и

Будь полигон параллелен XoZ, было бы просто

- что мешает трансформировать координаты в X, Y, Z в X', Y', Z' так, чтобы полигон стал параллелен X'oZ'? Сфера при этом просто переместится.

[Mikle]

что мешает трансформировать координаты в X, Y, Z в X', Y', Z' так, чтобы полигон стал параллелен X'oZ'? Сфера при этом просто переместится.

При таком повороте вертикаль оси сферы перестанет быть вертикалью.
Если использовать трансформацию "сдвиг", можно сохранить вертикальную ось, но сфера станет эллипсоидом, причём наклоненным.

[Debugger]

что мешает трансформировать координаты в X, Y, Z в X', Y', Z' так, чтобы полигон стал параллелен X'oZ'? Сфера при этом просто переместится.

При таком повороте вертикаль оси сферы перестанет быть вертикалью.
Если использовать трансформацию "сдвиг", можно сохранить вертикальную ось, но сфера станет эллипсоидом, причём наклоненным.

Да, ты прав. Задетектить пересечение это поможет, так как это своеобразный вариант нахождения "тени" полигона и сферы на XZ. Но про то, что сфера станет эллипсоидом, и нахождение центра сферы в момент соприкосновения не станет проще - я забыл.

[Mikle]

Мне на другом форуме предложили:

Строим в вершинах полигона виртуальные сферы радиусом R, соединяем их виртуальными цилиндрами радиусом R, сверху и снизу накрываем эту конструкцию виртуальными копиями исходного полигона, отстоящими от него на R. Исходная сфера пересекается с исходным полигоном тогда и только тогда, когда центр сферы находится внутри выпуклой оболочки этой виртуальной конструкции. Строим траекторию центра сферы и проверяем, есть ли пересечение этой оболочки.

Мы усложнили неподвижный объект, зато упростили подвижный до точки, её траектория - луч, ищем первое пересечение.
Это то, что надо.