Алгоритм поиска «одинаковых» геометрий

Привет! Меня зовут Мацкевич Евгений, я бекэнд-разработчик 3D-движка компании «Бимейстер». Хоть это и не очевидно на первый взгляд, но элементы загружаемых пользователями 3D-моделей зачастую повторяются, имея при этом различные положение в пространстве, масштабирование и вращение. Я расскажу о том, как мы научили нашу систему распознавать такие элементы как «одинаковые», выделять из них уникальный, а для остальных – вычислять матрицы трансформации. Это дало возможность однократно загружать уникальный элемент, а вместо прочих одинаковых – их матрицы, что сократило трафик и объем занимаемой оперативной памяти.

В рамках форматов 3D-моделей, создаваемых с использованием тех или иных САПРов, элементы могут быть заданы разными способами (набором вершин и нормалей, B-rep, или, в общем случае, параметрически). Поэтому сперва, на этапе парсинга, все элементы 3D-моделей приводятся к единому виду – набору вершин и нормалей (далее геометрия). Это дает возможность применять алгоритм поиска одинаковых геометрий.

Итак, геометрия задается набором вершин и нормалей. Но нормалями в данном случае будем пренебрегать. Каждые три вершины образуют треугольник. Эти треугольники, соединяясь вместе, образуют поверхность геометрической фигуры. Для того, чтобы задать куб, нужно двадцать четыре вершины, а не восемь, поскольку куб состоит из шести граней, а каждая грань – из двух треугольников (Рисунок 1).

Рисунок 1. Изображение куба

Условия, при которых мы будем считать две геометрии одинаковыми:

1. Одинаковые дескрипторы;

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

Дескрипторы

В общем виде дескриптором является некоторая характеристика, описывающая геометрию (прочитать подробно можно на medium.com). Мы будем пользоваться дескриптором, инвариантным к вращению, перемещению и масштабированию по трем осям пропорционально.

Метод расчета дескриптора:  

1. Найдем центр масс геометрии. Это среднее арифметическое всех вершин. 

2. Получим геометрию в локальной системе координат. Вычтем из каждой вершины центр масс. 

3. Получим нормализованную геометрию. Впишем геометрию в сферу единичного радиуса с центром в начале координат. 

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

5. Округлим числа до заданной точности (в нашем случае это 4 знака после запятой) и рассчитаем хэш-значение от полученных чисел (алгоритм хэширования MD5). Полученная величина и будет дескриптором. 

Таким образом, приведение к локальной системе координат нивелирует компоненту перемещения, нормализация – масштабирования, а сортировка массива длин – вращения.

Расчет дескрипторов относительно «дешев» и позволяет сгруппировать потенциально одинаковые геометрии, сокращая размер выборки для последующего вычисления матрицы трансформации.

Равенство дескрипторов является необходимым, но
недостаточным условием, при котором геометрии будут считаться одинаковыми.

Вычисление матрицы трансформации

Матрица трансформации состоит из трех компонентов: 

1. Перемещение; 

2. Масштабирование; 

3. Вращение. 

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

Алгоритм вычисления вращения по двум парам векторов

Представим все вершины геометрии как вектора с основанием в начале координат. Для того, чтобы найти вращение от первой геометрии ко второй, нужно найти вращение любой пары векторов из первой геометрии к точно такой же паре из второй. Для этого выберем две произвольные вершины из первой геометрии (Анимация 1).

Анимация 1. Две произвольные вершины u0 и v0 из первой геометрии

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

Пусть (Рисунок 2):    

• u₀ и v₀ - два вектора первой пары;

• u₂ и v₂ - два вектора второй пары.

Рисунок 2. Две пары векторов

Тогда мы ищем вращение q, которое преобразует u₀ в u₂, а v₀ в v₂ (Анимация 2):

Анимация 2. Вращение q

Для этого разложим q на два последовательных вращения q1 и q2:

• q₁ = u₀ → u₁;

• q₁ = v₀ → v₁;

• q₂ = u₁ → u₂;

• q₂ = v₁ → v₂.

Таких комбинаций из двух вращений может быть бесконечное множество.

Выберем такое множество вращений q₁, при котором u₀ = u₁, т.е. это вращения вокруг оси u₀ (Анимация 3).

Анимация 3. Множество вращений вокруг оси u0

Тогда вращение q₂ преобразует u₀ в u₂:

• q₂ = u₀ → u₂.

Для вычисления кватерниона q₂ нам достаточно вычислить угол между u₀ и u₂, а в качестве оси вращения выберем N_u – нормаль к плоскости, в которой лежат векторы u₀ и u₂ (Анимация 4).

Анимация 4. Вращение q2 вокруг оси Nu

Осталось определить q_1.

Известно, что q₂ преобразует v₁ в v_2, тогда обратное вращение q₂^* (конъюгат кватерниона) преобразует v₂ в v₁ (Анимация 5)_. Отсюда мы можем найти v_1.

Анимация 5. Вращение q2* вокруг оси Nu

О q₁ верно следующее:

q₁ - вращение вокруг оси u₀.
q₁ = v₀ → v₁;

Мы могли бы найти вращение q₁, аналогично q₂ по углу между v₀ в v_1, и оси u_0, но ось u₀ не обязательно будет являться нормалью к плоскости, в которой лежат v₀ и v_1. Поэтому найдем проекции v₀ и v₁ на плоскость, ортогональную оси u₀. Назовем их v'₀ и v'₁ (Рисунок 3).

Рисунок 3. Проекции v'0 и v'1

Вращение q₁ вокруг оси u₀, которое преобразует v₀ в v₁, также преобразует и v'₀ в v'₁.

Найдем q₁, используя угол между v'₀ и v'₁ и ось u₀ (Анимация 6).

Анимация 6. Вращение q1 вокруг оси u0

Конечное вращение получим, перемножив кватернионы q = q_{2 *} q_1.  Выглядеть оно будет как на анимации 2.

Итак, повернем первую геометрию, используя вычисленное вращение, и сравним ее повершинно со второй геометрией. Если обнаружится хоть одна пара неравных вершин, то, несмотря на рассчитанное вращение, одинаковыми такие геометрии являться не будут. Это означает, что пары векторов были выбраны неверно, и требуется повторить поиск вращения со следующей парой.

Далее, имея вычисленные значения перемещения, масштабирования и вращения, мы можем найти итоговую матрицу трансформации.

Назначение и нюансы применения алгоритма

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

В дополнение хотелось бы отметить некоторые нюансы алгоритма поиска одинаковых геометрий:

1. От метода вычисления дескриптора зависит качество работы алгоритма в целом.

   Алгоритм расчета дескриптора может давать как ложноположительный, так и ложноотрицательный результат. Если результат ложноположительный, т.е. две геометрии имеют одинаковое значение дескриптора, но «одинаковыми» при этом не являются, то, получается, что мы зря ищем вращение. Однако, в случае ложноотрицательного результата и вовсе упускается возможность применения алгоритма поиска вращения для заведомо одинаковых геометрий.

2. Сравнение вершин, как и вычисление дескриптора, должны выполняться с некоторой заданной точностью, т.к. мы имеем дело с числами с плавающей запятой.