Расстояние между двумя полигонами

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

Прежде чем начинать выравнивать и передвигать, нужно определить, какие именно грани надо выравнивать относительно каких. Пытаюсь делать так:

1. Нахожу у объектов пару полигонов/граней с минимальным расстоянием, и чтобы угол между ними не превышал максимальное допустимое значение (например, 30°).
2. Потом нахожу вторую такую же пару, исключая выбранные на предыдущем шаге полигоны из пространства поиска.

Вместо честного расчёта расстояния между полигонами беру минимальное расстояние между вершинами первого полигона и плоскостью второго и наоборот. Обычно получается вполне логично, но иногда выходит фигня (первая пара полигонов зелёная, вторая розовая):

К зелёным полигонам вопросов нет, они вообще лежат в одной плоскости, даже выравнивать не надо. А вот плоскость от розового полигона Деревяшки проходит вблизи вершин розового полигона Стены, и поэтому «расстояние» между этими полигонами (как я его считаю) получается минимальным. Но хотелось бы, независимо от того кто относительно кого выравнивается, чтобы всегда получалось так:

--
Теперь пытаюсь сообразить:
1. Если считать расстояние честно, поможет ли это при любом взаимном расположении объектов?
2. Честное расстояние между двумя полигонами в пространстве - это что такое вообще? Какое дать ему формальное определение, чтобы понять, что конкретно надо посчитать?
3. Нет ли другого способа подбора пары граней у двух объектов, который давал бы логичный результат?

1. Ответ на первый вопрос, скорее всего, получится узнать только практическим путём.

2. Расстояние между двумя полигонами в пространстве - это длина минимального отрезка, соединяющего две точки, принадлежащие разным полигонам. Такими точками могут быть и вершины полигонов, и точки на их рёбрах, и просто точки на плоскости внутри полигонов.

Самый тупой способ найти расстояние между полигонами А и Б получается такой:

- найти расстояния между каждой вершиной полигона А и каждой вершиной полигона Б;
- найти расстояния между каждой вершиной полигона А и каждым ребром полигона Б;
- то же самое наоборот;
- найти расстояния между каждым ребром полигона А и каждым ребром полигона Б;
- найти расстояния между каждой вершиной полигона А и её проекцией на плоскость полигона Б при условии, что проекция попадает внутрь полигона Б;
- то же самое наоборот;
- а потом взять из этих расстояний минимальное.

Способа умнее пока не нашёл. Например, что-нибудь типа "спроецировать все вершины обоих полигонов одну прямую и найти пару точек с минимальным расстоянием между ними" (как узнать ту прямую, на которую проецировать?).

Учитывая, что мне не просто надо найти расстояние между двумя полигонами, а из двух множеств полигонов выбрать пару с минимальным расстоянием, то вычислений получится прилично.

Для пары 4-угольников получится 16 расстояний между вершинами, 32 расстояния между вершиной и ребром, 16 расстояний между рёбрами, 8 расстояний от точки до плоскости и 8 проверок на попадание точки внутрь полигона. Если сравнивать два объекта-шестигранника, то для поиска пары ближайших граней повторить всё это 36 раз. И я ещё не учитываю, что объект может быть состоять не из одной детали, а множества деталей (одна-две сотни легко). Понятно, что многое можно будет оптимизировать и не считать, но всё равно выходит неслабо.

3. Третий вопрос пока открыт и актуален.

По моему какая-то наркоманская задача....

В Autodesk Inventor сделан выбор 2х плоскостей и по ним совмещение, может так будет правильнее?

Т.е. дать юзеру

А если объект овальный? или случай, когда вершина куба направлена в сторону плоскости, причём каждая из его ближайших плоскостей - имеет равный угол с прицельной плоскостью.... Тут слишком много всяких Но :)

FireFenix
> Т.е. дать юзеру
> выбрать плоскость 1
> выбрать плоскость 2
> кнопка совместить

Это само собой, но только когда автоматика не справилась. Одно дело когда ставишь предмет на сцену и он сразу ровненько пристыковывается к ближайшему, а другое, когда надо потратить полминуты на его ручную подгонку. Не люблю, когда программы заставляют пользователя выполнять операции, которые они сами могли бы сделать намного быстрее автоматически, но программисту было сложно или лень делать этот функционал.

> А если объект овальный?

Овальных быть не могёт. Могут быть такие:

Двух пар полигонов хватит для задания правильной ориентации. Потом надо будет рассчитать ещё и сдвиг, но это должно быть проще.

--

Сейчас сделал поиск расстояния между полигонами описанным тупым способом, но всё равно попадаются случаи, когда пары полигонов выбираются явно нелогичные. Или где-то ошибся, или всё в порядке, но формально правильный ответ не всегда лучший. Что тоже бывает.

PS
Ошибся. Вместо расстояний между рёбрами-отрезками взял расстояния между прямыми. Не надо было.

alexzzzz
> Делаю функцию автоматического выравнивания одного объекта относительно другого.
> Тыкаешь в объект, потом в образец, и первый объект как-нибудь поворачивается
> параллельно второму и передвигается к нему впритык, чтобы получилось красиво,
> ровно и аккуратно. При отсутствии дополнительных подсказок со стороны
> пользователя выравнивание должно работать по принципу наименьшего удивления. На
> скриншотах ниже Деревяшка, имхо, должна прижаться к Стене, и чтобы не осталось
> никаких щелей.
Плохая задача.
Опиши её так, чтобы можно было найти точное и однозначное решение. Например, "нужно взять пару треугольников с двух объектов, и переместить объект Б так, чтобы эти треугольники оказались в одной плоскости".

Задача вращения и перемещения объектов не вызывает затруднения. Я запнулся на автоматическом поиске ориентиров для задания ориентации - какую именно «пару треугольников» взять. (Треугольников в чистом виде у меня, кстати, нет. Забыл как страшный сон. Форма задаётся выпуклыми полигонами.)

Пробовал делать привязку вершин объекта к ближайшим вершинам соседних объектов. Не прокатило. В зависимости от допустимого расстояния оказывается или мало подходящих вершин, или много, но они давали непредсказуемые сочетания (когда тестовые объекты состояли не из одной детали, а из десятка более мелких).

Начал было делать привязку по рёбрам, но потом подумал, что логичнее будет по граням. Встала задача поиска на объектах одной-двух пар граней, по которым надо выравнивать. По каким метрикам можно отбирать такие пары? Имхо, только два варианта: углы между нормалями граней и расстояния между полигонами граней. Одних углов мало, нужно считать или честное расстояние или придумать оценочную функцию для нахождения примерного расстояния.

alexzzzz
Если грани плоские - то можно так. Для каждой получаешь общее уравнение плоскости Ax+By+Cz+D=0. Если вектор (A, B, C) нормализованный, то по разнице коэффициента D можно "оценить расстояние" между плоскостями. Но делать это само собой надо между плоскостями у которых dot(vec3(A1,B1,C1), vec3(A2,B2,C2)) больше некоторого treshold.

Есть такой момент, что даже когда две плоскости совпадают, но их нормали смотрят в противоположные стороны, значения D тоже противоположны.

alexzzzz
> Есть такой момент, что даже когда две плоскости совпадают, но их нормали
> смотрят в противоположные стороны, значения D тоже противоположны.
Умножить уравнение плоскости на -1 ?

Надо попробовать.

Попробовал. В половине случаев D из уравнения прямой (в мировых координатах) работает:

в половине нет:

Чем более неровно стоят объекты, тем страннее получаемый результат.

alexzzzz
> Чем более неровно стоят объекты, тем страннее получаемый результат.
Тебе сначала нужно отсеять по углу между плоскостями:
treshold = 0.85;
abs(dot(vec3(A1, B1, C1), vec3(A2, B2, C2))) > treshold
и только плоскости, прошедшие этот тест должны попадать в сравнение по D (не забываем что нормали плоскостей должны быть нормализованными). Если и по D сравнение прошло - то нужно найти трансофрмацию, переводящую одну плоскость в другую (поворот + перенос).
Вот тут поворот от одной нормали плоскости к другой: http://www.gamedev.ru/code/articles/?id=4215&page=3#preobrazo… vuh_napravlen
После этого перенос вдоль вектора на расстояние delta D.

MrShoor
> Тебе сначала нужно отсеять по углу между плоскостями:
> treshold = 0.85;

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

Для изучения эффекта сделал в Geometry Expressions двумерную модель (Planes), где вместо плоскостей две прямые. Нарисовал два почти совпадающих отрезка под углом 10° друг к другу (dot между векторами ~0.985) и попробовал вращать и двигать в разные стороны. deltaD пляшет очень существенно и от смещений, и от вращения:

С математикой проблемы нет. Как посчитать, я разберусь, тем более, что почти всё что нужно уже написано. Больше волнует вопрос, что именно считать. Сегодня поправил честный расчёт расстояния между полигонами. Пока вроде пары подбираются логично. Поэкспериментирую ещё и, если более шустрого метода подбора пар не придумается, займусь оптимизацией для больших объектов из кучи деталей, иначе можно повеситься от количества ненужных расчётов.

alexzzzz
> от смещений
Да, действительно будет плясать от смещений. Тогда можно предварительно смещать фейсы например чтобы их геометрический центр оказалвался в нуле. Поидее должно помочь.

Не получится ли тогда ситуации, что красный отрезок будет более подходящей парой чёрному?