Ray Casting Visual Search (RCVS). Простой и быстрый алгоритм поиска схожих по геометрии 3D моделей
Для меня эти две модели очень похожи, однако у них нет очевидных характеристик, по которым можно было бы измерить их сходство. У этих моделей разное количество вершин, рёбер и полигонов, они разного размера, к тому же по-разному повёрнуты в пространстве, и у обеих одинаковые трансформации (Положение = [0,0,0], Вращение в радианах = [0,0,0], Масштаб = [1,1,1]). Как определить их подобие?
Если бы эти модели были одинаково ориентированы в пространстве, их можно было бы свести к общему размеру Bounding Box, переместить начало локальных координат в его центр, привести к воксельному виду, и сравнить списки вокселей.
Если бы эти модели были произвольно ориентированы вдоль осей координат, их можно было бы свести к общему размеру Bounding Box, переместить начало локальных координат в его центр, порендерить их с шести сторон и сравнивать наборы изображений между собой.
Для того, чтобы добиться инвариантности поворота, я решил обратиться к сферической системе координат.
Сначала я считал расстояния до вокселей от начала координат, собирал расстояния в упорядоченные списки и сравнивал эти списки. Это дало неплохие результаты, но требовало много времени для приведения к воксельному виду достаточного разрешения и сравнения больших списков.
Краткое описание RCVS
Вместо вокселизации и рендеров, мой метод основан на бросании лучей (Ray Casting). Модель помещается внутрь икосаэдрального сферического многогранника, из полигонов которого бросаются лучи и записывается их длина (далее путь) до поверхности модели. Списки этих путей сортируются и сравниваются друг с другом. Сортировка нивелирует повороты, так как у одинаковых или близких по геометрии моделей пути лучей будут совпадать в пределах погрешности, но отличаться по порядку.
Результаты сравнения моделей обезьянки Сюзанны в разных вариантах:
Suzanne_lo
Suzanne_lo | 1
Suzanne_lo_rot_rand | 0.9878376875939173
Suzanne_lo_rot_90 | 0.9800766750109137
Suzanne_hi_rot_rand | 0.9761078629585936
Suzanne_hi | 0.9730722945028376
Suzanne_hi_rot_90 | 0.9680325422930756
Skull | 0.7697333228143514
Ceramic_Teapot_rot_rand | 0.6634783235048608
Ceramic_Teapot | 0.6496529954470333
Grenade_MK2 | 0.5275616759076022Подробное описание RCVS
Перед сравнением 3D моделей (далее объектов), каждая проходит этап подготовки (эту часть я реализовал на Python в Blender):
- Начало локальных координат компонентов объекта устанавливается в центр массы объёма.
2. Объект вписывается в сферу единичного радиуса с центром в начале локальных координат компонентов объекта.
3. Применяются трансформации размера.
4. Вокруг объекта строится икосаэдральный сферический многогранник (далее икосфера) единичного радиуса с нормалями, направленными внутрь. Количество полигонов икосферы, на которых проводились тесты: 80, 320, 1280, 5120, 22480. Оптимальным количеством полигонов икосферы по времени и точности в тестах было определено 1280.
5. Из каждого полигона икосферы по нормали отправляется луч и сохраняется его путь до столкновения с поверхностью объекта, нормаль которой направлена в сторону луча.
6. Нормали объекта переворачиваются в противоположном направлении.
7. Из каждого полигона икосферы ещё раз отправляются лучи и сохраняется их путь до встречи с поверхностью объекта, нормали которой направлены внутрь объекта. (Это фиксирует внутреннюю геометрию и/или заполняет слепые зоны предыдущих лучей)
8. Пути лучей, отправленных с противоположных полигонов компонуются в списки, где первые два пути из пункта 5 и вторые два из пункта 7. Каждый список сортируется по наименьшему значению пути из пункта 5 так, что пути из пунктов 5 и 7 попарно соответствуют друг другу.
9. Список списков всех путей сортируется по первому значению. Этот список имеет 4 столбца и количество строк, равное половине количества полигонов икосферы.
10. Список путей лучей записывается в файл.
Список путей лучей выглядит примерно так:
0.00271218840585662 0.2112752957162676 0.00271218840585662 0.2112752957162676
0.004740002405006037 0.210980921765861 0.004740002405006037 0.2109809188911709
0.00660892842734402 0.2066613370130234 0.00660892842734402 0.2066613370130234
…
0.2692299271137439 0.2725085782639611 0.2692299271137439 0.2725085782639611
0.2705489991382905 0.2707842753523402 0.270548999138295 0.2707843056356914
0.2709498404192674 0.271036677664217 0.2709498404192674 0.271036642944409Когда все объекты получили готовые списки путей лучей их можно сравнивать (эту часть я написал на Rust):
- Задаётся пороговое значение допустимой ошибки. В тестах наилучшим было определено значение 0.01, ошибка в пределах 1%.
- Создаётся счётчик соответствия.
- Для каждой строки в первом списке ищется строка из второго, каждое значение которой отличается от соответствующего значения из первого списка в пределах допустимой ошибки. Если такая строка находится, она не участвует в дальнейшем поиске. Вычисляется попарная абсолютная разница значений из двух списков и вычитается из единицы, среднее арифметическое этих значений прибавляется к счётчику.
- Когда пройдены все строки первого списка значение счётчика делится на количество строк. Полученное значение является результатом сравнения.
- Если объекты идентичны по форме (независимо от их размера и поворота) результат близок к единице.
Бананы, Витрувианский человек и ограничения RCVS
Алгоритм отлично работает для поиска близких по геометрии объектов, например высоко- и низко-полигональных вариантов одной и той же модели. И иногда неплохо справляется с похожими по смыслу объектами, например с чайниками или гитарами разных форм. Однако, поскольку количество моделей, которым будет соответствовать один и тот же список путей лучей примерно можно оценить в n! / (n/2)!, есть существенная вероятность, что визуально непохожие по геометрии объекты будут иметь счёт совпадения в диапазоне (0.5–0.9). В ходе тестов так вышло с бананами, которые на 0.7 совпадают с самолётами и людьми в разных позах, которые в свою очередь на “внушительные” 0.85 совпадают с тиграми и собаками.
Для более точного поиска стоит учитывать размер и/или поворот объектов.
