Ray Casting Visual Search (RCVS). Простой и быстрый алгоритм поиска схожих по геометрии 3D моделей

PHYGITALISM
Mar 3, 2020 · 5 min read

Для меня эти две модели очень похожи, однако у них нет очевидных характеристик, по которым можно было бы измерить их сходство. У этих моделей разное количество вершин, рёбер и полигонов, они разного размера, к тому же по-разному повёрнуты в пространстве, и у обеих одинаковые трансформации (Положение = [0,0,0], Вращение в радианах = [0,0,0], Масштаб = [1,1,1]). Как определить их подобие?

Если бы эти модели были одинаково ориентированы в пространстве, их можно было бы свести к общему размеру Bounding Box, переместить начало локальных координат в его центр, привести к воксельному виду, и сравнить списки вокселей.

Обезьянки и их воксели

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

Рендеры кривизны поверхности

Для того, чтобы добиться инвариантности поворота, я решил обратиться к сферической системе координат.

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

Краткое описание RCVS

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

80 лучей
1280 лучей

Результаты сравнения моделей обезьянки Сюзанны в разных вариантах:

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):

  1. Начало локальных координат компонентов объекта устанавливается в центр массы объёма.

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):

  1. Задаётся пороговое значение допустимой ошибки. В тестах наилучшим было определено значение 0.01, ошибка в пределах 1%.
  2. Создаётся счётчик соответствия.
  3. Для каждой строки в первом списке ищется строка из второго, каждое значение которой отличается от соответствующего значения из первого списка в пределах допустимой ошибки. Если такая строка находится, она не участвует в дальнейшем поиске. Вычисляется попарная абсолютная разница значений из двух списков и вычитается из единицы, среднее арифметическое этих значений прибавляется к счётчику.
  4. Когда пройдены все строки первого списка значение счётчика делится на количество строк. Полученное значение является результатом сравнения.
  5. Если объекты идентичны по форме (независимо от их размера и поворота) результат близок к единице.

Бананы, Витрувианский человек и ограничения RCVS

Алгоритм отлично работает для поиска близких по геометрии объектов, например высоко- и низко-полигональных вариантов одной и той же модели. И иногда неплохо справляется с похожими по смыслу объектами, например с чайниками или гитарами разных форм. Однако, поскольку количество моделей, которым будет соответствовать один и тот же список путей лучей примерно можно оценить в n! / (n/2)!, есть существенная вероятность, что визуально непохожие по геометрии объекты будут иметь счёт совпадения в диапазоне (0.5–0.9). В ходе тестов так вышло с бананами, которые на 0.7 совпадают с самолётами и людьми в разных позах, которые в свою очередь на “внушительные” 0.85 совпадают с тиграми и собаками.

Для более точного поиска стоит учитывать размер и/или поворот объектов.

Исходники

Ссылка на GitHub.

Автор

Роман Чумак

Инженер-исследователь

p4@phygitalism.com

PHYGITALISM

Создаем проекты на стыке XR, ML и других интерактивных…

PHYGITALISM

Создаем проекты на стыке XR, ML и других интерактивных технологий

PHYGITALISM

Written by

Мы - команда PHYGITALISM, реализуем фиджитал-проекты и много экспериментируем с XR, интерактивными технологиями и машинным обучением.

PHYGITALISM

Создаем проекты на стыке XR, ML и других интерактивных технологий