p4ymak 3 мар 2020 в 00:13

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

8 мин

5.2K

CGI (графика)*Алгоритмы*Поисковая оптимизация*Поисковые технологии*Работа с 3D-графикой*

Технотекст 2020

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

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

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

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

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

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

$r = \sqrt{x^2+y^2+z^2}$

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

Краткое описание 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):

Начало локальных координат компонентов объекта устанавливается в центр массы объёма.
Объект вписывается в сферу единичного радиуса с центром в начале локальных координат компонентов объекта.
Применяются трансформации размера.
Вокруг объекта строится икосаэдральный сферический многогранник (далее икосфера) единичного радиуса с нормалями, направленными внутрь. Количество полигонов икосферы, на которых проводились тесты: 80, 320, 1280, 5120, 22480. Оптимальным количеством полигонов икосферы по времени и точности в тестах было определено 1280.
Из каждого полигона икосферы по нормали отправляется луч и сохраняется его путь до столкновения с поверхностью объекта, нормаль которой направлена в сторону луча.
Нормали объекта переворачиваются в противоположном направлении.
Из каждого полигона икосферы ещё раз отправляются лучи и сохраняется их путь до встречи с поверхностью объекта, нормали которой направлены внутрь объекта. (Это фиксирует внутреннюю геометрию и/или заполняет слепые зоны предыдущих лучей)
Пути лучей, отправленных с противоположных полигонов компонуются в списки, где первые два пути из пункта 5 и вторые два из пункта 7. Каждый список сортируется по наименьшему значению пути из пункта 5 так, что пути из пунктов 5 и 7 попарно соответствуют друг другу.
Список списков всех путей сортируется по первому значению. Этот список имеет 4 столбца и количество строк, равное половине количества полигонов икосферы.
Список путей лучей записывается в файл.

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

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

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

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

Исходники.

Код на Python для создания словаря противоположных полигонов икосферы в Blender

import bpy
import os

name = bpy.context.active_object.data.name

polys = bpy.data.meshes[name].polygons
print("-----")
length = len(polys)

x = 0
p = 0
dict = []
for i in range(0, length):
    print(i, "/", length)
    for l in range(i, length):
        norm1 = polys[i].normal
        norm2 = polys[l].normal
        if norm1 == -norm2:
            dict.append(str(i)+", "+str(l)) 
            p += 1  


print("Polys", p)
basedir = os.path.dirname(bpy.data.filepath) + "/ico_dicts/"  
if not os.path.exists(basedir):
    os.makedirs(basedir)
file = open(basedir + "/" + str(length) + ".csv","w")
for poly in dict:      
    file.write(poly + "\n")
file.close()
print("----ok----")

Код на Python для подготовки объектов и создания списка путей лучей в Blender.

import bpy
import os
from math import sqrt
import csv


#Icosphere properties
#icosubd:
#5 -> 5120 X 2 rays
#4 -> 1280 X 2 rays
#3 ->  320 X 2 rays
#2 ->   80 X 2 rays
icosubd = 4
size = 1280 #name of directory
radius = 1




def icoRC(icosubd, rad, raydist, normals, target):
    icorad = rad
    bpy.ops.mesh.primitive_ico_sphere_add(radius=icorad, subdivisions=icosubd, enter_editmode=True, location=(0, 0, 0))
    bpy.ops.mesh.normals_make_consistent(inside=normals)
    bpy.ops.object.editmode_toggle()
    

    ico = bpy.context.active_object
    mesh = bpy.data.meshes[ico.data.name]
    rays = []
    size = len(mesh.polygons)
    for poly in mesh.polygons:
        normal = poly.normal
        start = poly.center
        
        ray = target.ray_cast(start, normal, distance=raydist)
      
        if ray[0] == True:
            length = sqrt((start[0]-ray[1][0]) ** 2 + (start[1]-ray[1][1]) ** 2 + (start[2]-ray[1][2]) ** 2)
            rays.append(length / (radius *2))
        else:
            rays.append(-1)
            
        
    result = []
    #Combine opposite rays using CSV dicts
    dictdir = os.path.dirname(bpy.data.filepath) + "/ico_dicts/"
    with open(dictdir+str(size)+'.csv', newline='') as csvfile:
        ico_dict_file = csv.reader(csvfile, delimiter=',')
        for row in ico_dict_file:
            result.append([rays[int(row[0])], rays[int(row[1])]])
            
            
    bpy.ops.object.select_all(action='DESELECT')
    bpy.data.objects[ico.name].select_set(True) 
    bpy.ops.object.delete() 
    
    return result
   
   
    
    
#Batch preparation of objects by scale and origin 
def batch_prepare():   
    for obj in bpy.context.selected_objects:
        bpy.ops.object.origin_set(type='ORIGIN_CENTER_OF_VOLUME', center='MEDIAN')
        max_dist = 0
        bb = bpy.data.objects[obj.name].bound_box
        
        for vert in obj.data.vertices:
            dist = vert.co[0]**2 + vert.co[1]**2 + vert.co[2]**2
            if dist > max_dist:
                max_dist = dist
        
        obj.scale *= (1 / sqrt(max_dist))



def write_rays(dir):  
    for obj in bpy.context.selected_objects:
        bpy.ops.object.transform_apply(location=False, rotation=False, scale=True)
        
        #Cast rays on object with normals turned inside   
        bpy.context.view_layer.objects.active  = obj
        bpy.ops.object.editmode_toggle()
        bpy.ops.mesh.normals_make_consistent(inside=True)
        bpy.ops.object.editmode_toggle()
        result1 = icoRC(icosubd, radius, radius*2, True, obj)
        
        #Cast rays on object with normals turned outside 
        bpy.context.view_layer.objects.active  = obj
        bpy.ops.object.editmode_toggle()
        bpy.ops.mesh.normals_make_consistent(inside=False)
        bpy.ops.object.editmode_toggle()
        result2 = icoRC(icosubd, radius, radius*2, True, obj)
        
        final = []
        #Sort sub-lists and append them to main list
        for i in range(0, len(result1)):
            if result2[i][0] < result2[i][1]:
                final.append([result2[i][0], result2[i][1], result1[i][0], result1[i][1]])
            else:
                final.append([result2[i][1], result2[i][0], result1[i][1], result1[i][0]])
        
        
        
     
        basedir = os.path.dirname(bpy.data.filepath) + "/rays/" + str(size) + "/" 
        if not os.path.exists(basedir):
            os.makedirs(basedir)
        file = open(basedir + "/" + obj.name,"w")
        
        final.sort(key=lambda x: x[0]) #Sort list by first values in sub-lists
     
        #Writing to file   
        for ray in final:
            ray_str = ""
            for dist in ray:   
                ray_str += str(dist) + " "
            file.write(ray_str + "\n")

        file.close()
        
    
    
batch_prepare()
write_rays(size)

Код на Rust для сравнения списков.

use rayon::prelude::*;
use std::collections::HashSet;
use std::fs;
use std::io::{BufRead, BufReader, Error, Read};

//Creates Vector from file
fn read<R: Read>(io: R) -> Result<Vec<Vec<f64>>, Error> {
    let br = BufReader::new(io);
    br.lines()
        .map(|line| {
            line.and_then(|v| {
                Ok(v.split_whitespace()
                    .map(|x| match x.trim().parse::<f64>() {
                        Ok(value) => value,
                        Err(_) => -1.0,
                    })
                    .collect::<Vec<f64>>())
            })
        })
        .collect()
}

//Compares two objects
fn compare(one: &Vec<Vec<f64>>, two: &Vec<Vec<f64>>, error: f64) -> f64 {
    let length = one.len();
    let mut count: f64 = 0.0;
    let mut seen: HashSet<usize> = HashSet::new();

    for orig in one {
        let size = orig.len();

        for i in 0..length {
            if seen.contains(&i) {
                continue;
            } else {
                let targ = &two[i];

                if (0..size).map(|x| (orig[x] - targ[x]).abs()).sum::<f64>() > error * size as f64 {
                    continue;
                }

                let err_sum = (0..size)
                    .map(|x| 1.0 - (orig[x] - targ[x]).abs())
                    .sum::<f64>();

                count += err_sum / size as f64;
                seen.insert(i);
                break;
            }
        }
    }
    count / length as f64
}

//Compares one object with others on different threads
fn one_with_others(
    obj: &(String, Vec<Vec<f64>>),
    dict: &Vec<(String, Vec<Vec<f64>>)>,
) -> Vec<(usize, f64)> {
    let length = dict.len();

    (0..length)
        .into_par_iter()
        .map(|x| {
            println!("Puny human is instructed to wait.. {:}/{:}", x + 1, length);
            (x, compare(&obj.1, &dict[x].1, 0.01))
        })
        .collect()
}

fn main() {
    let ray = 1280; //name of directory
    let obj_cur = "Suzanne_lo"; //name of object

    let mut objects = Vec::<(String, Vec<Vec<f64>>)>::new();
    let path_rays = format!("./rays/{:}/", ray);
    let paths = fs::read_dir(path_rays).unwrap();

    let obj_path = format!("./rays/{:}/{:}", ray, obj_cur);
    let obj = (
        obj_cur.to_string(),
        read(fs::File::open(obj_path).unwrap()).unwrap(),
    );

    for path in paths {
        let dir = &path.unwrap().path();
        let name = dir.to_str().unwrap().split("/").last().unwrap();

        objects.push((
            name.to_string(),
            read(fs::File::open(dir).unwrap()).unwrap(),
        ));
    }

    let mut result = one_with_others(&obj, &objects);
    result.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
    print!("{}\n", "_".repeat(150));
    println!("{:}", obj.0);
    for line in result {
        println!(
            "{:>36} |{:<100}| {:<14}",
            objects[line.0].0,
            "▮".repeat((line.1 * 100.0).round() as usize),
            line.1
        );
    }
}

Теги:

Хабы:

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

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

Подробное описание RCVS

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

Исходники.

Публикации

Истории

Ближайшие события