На конференции в Вене автор статьи обнаружил, что другие исследователи — Чинг Чен и Цунг-Тай Йе — решили задачу, над которой он бился два года назад. Он разработал структуру CAPT для быстрой проверки коллизий между сферами робота и облаками точек, но у неё была серьёзная проблема: долгая сборка. Плотные облака точек требовали дублирования данных, и конструкция структуры разрасталась. Чен и Йе придумали MVT — multilevel voxel table. Вместо дерева пространственного разбиения они режут пространство на воксели и хранят только занятые ячейки в разреженном трёхуровневом дереве. Точки не дублируются, поиск соседних вокселей тривиален, а запросы можно параллелить через SIMD. Автор переписал их идею на Rust и упростил структуру: вместо паутины указателей из оригинального C++ — плоские буферы Box<[]> и простой поиск по таблицам. Он также сделал мутируемую версию MutableMvt, где каждый Voxel хранит свои точки. Это добавляет примерно 2x к размеру и 1.5x к времени сборки, зато удобно для изменяемых сцен.
Главный вопрос — размер вокселя. Оригинальная статья советовала брать радиус самой большой сферы робота, но автор прогнал замеры на роботах Fetch, Panda, UR5 и Baxter. Для Baxter такой выбор оказался в двадцать раз медленнее оптимума. Оптимальный размер для всех роботов — примерно 10–20 см.
Бенчмарки показали, что MVT значительно быстрее CAPT при построении: память линейна, конструкция почти не требует книг учёта. По скорости запросов MVT тоже обошёл CAPT, который выдавал около десяти наносекунд. Неожиданно мутируемая версия показала чуть лучшую производительность запросов, возможно из-за особенностей кэша. В реальных задачах motion planning планирование с MVT почти всегда быстрее, чем с CAPT, а иногда даже быстрее, чем с настоящей геометрией примитивов.
Но большая проблема осталась. Облака точек с камер видят объект только с одной стороны, а для реальных роботов нужно учитывать, что невидимое пространство тоже может быть занято. Октокарты с этим справляются, но они медленные. Автор пожертвовал обработкой окклюзий ради скорости в CAPT, и MVT её тоже не добавляет. Классический подход к планированию, где мир выглядит как идеальный натюрморт, не работает: робот всегда планирует по приблизительной модели мира. Так что, как и немытая посуда, эта задача ещё ждёт своего решения.