Следующим этапом после уплотнения облака точек в алгоритме построения трёхмерной сцены из видеопотока является получение меша. Меш - это набор полигонов (плоских многогранников) в пространстве. Часто в качестве полигонов используются треугольники как самые простые плоские фигуры, однозначно определяющие плоскость.
Чтобы получить меш из облака точек, можно каким-то алгоритмом выбирать тройки точек и создавать для них полигоны, однако для шумных и плотных облаков это даст очень шумный меш с множеством лишних деталей. Кроме того, в зависимости от алгоритма, можно получить неманифолдный (non-manifold) меш [1] - меш с самопересечениями, с отдельно стоящими рёбрами (незамкнутыми контурами), с отдельно стоящими точками. Алгоритмы, которые могут применяться в случае облака, полученного из SfM и MVS, включают в себя триангуляцию Делоне в трёхмерном пространстве, Ball Pivoting [2], различные оболочки: выпуклая (convex hull), невыпуклая с параметром невыпуклости (concave hull - alpha shape [3]).
Триангуляция Делоне в трёхмерном пространстве основывается на приведении всех полигонов к такому набору тетраэдров, что для любого тетраэдра описанная сфера содержит в себе только те вершины, которые составляют этот тетраэдр. Данный подход в первую очередь плох своей вычислительной эффективностью в случае большого количества точек. Кроме того, строится очень много "невидимых" полигонов внутри оболочки, что увеличивает дополнительно время работы и размер выходного файла.
Алгоритм Ball Pivoting основан на "прокатывании шарика" по всем тройкам точек в некоторой окрестности. Там, где радиус шарика больше радиуса вписанной окружности треугольника, полигон не создаётся. Этот алгоритм имеет несколько модификаций, позволяющих учитывать нормали вершин и не создавать лишних полигонов, однако это влечёт за собой необходимость дополнительно рассчитывать нормали точек в нашей задаче. Недостатки алгоритма такие же, как и у триангуляции Делоне, но применимость к трёхмерной реконструкции из видеопотока большая.
Из оболочек для нашей задачи интересна только невыпуклая оболочка: выпуклые оболочки для облака точек, представляющего асфальт и стены домов на улице, даст выпуклую фигуру, напоминающую параллелепипед, "заполняя" пространство между стенами домов на противоположных концах улицы. Для невыпуклых оболочек есть алгоритм alpha shape, работающий по принципу "вынимания" из твёрдой выпуклой оболочки сфер размера не меньше задаваемого радиуса. В статье, описывающей этот алгоритм, приводилась аналогия с мороженым в лотке и инструментом для доставания его шариками. Этот алгоритм гарантирует получение оболочки, то есть манифолдного меша, что делает его наиболее применимым для нашей задачи.
Кроме методов, работающих непосредственно с облаком, есть семейства алгоритмов, собирающих статистические данные из облака и берущих за основу пространство. Самый известный - Marching Cubes [4], который часто используется в игровой индустрии для создания разрушаемых объектов. Его идея заключается в разбиении пространства на трёхмерную битовую сетку (легко представляемую тензором) и сопоставлении каждого вокселя (8 вершин сетки, образующие куб) заранее заданному шаблону, гарантирующему связность получаемых полигонов и, соответственно, манифолдность меша. К сожалению, этот метод не может работать с адаптивным размером сетки, тогда как в нашей задаче занимаемое облаком пространство слишком велико и детализация слишком большая, чтобы эффективно применять Marching Cubes.
Потенциально перспективным выглядит совмещение алгоритмов, работающих с облаком, и алгоритмов, работающих с пространством: один из применяемых нами методов основывался на разбиение пространства на воксели, получения нового облака точек центроидов исходных точек в каждом вокселе, а затем создание меша на основе этого облака.
Источники:
https://pages.mtu.edu/~shene/COURSES/cs3621/SLIDES/Mesh.pdf
F. Bernardini, J. Mittleman, H. Rushmeier, C. Silva and G. Taubin, "The ball-pivoting algorithm for surface reconstruction," in IEEE Transactions on Visualization and Computer Graphics, vol. 5, no. 4, pp. 349-359, Oct.-Dec. 1999, doi: 10.1109/2945.817351.
H. Edelsbrunner and D. G. Kirkpatrick and R. Seidel: On the shape of a set of points in the plane, IEEE Transactions on Information Theory, 29 (4): 551–559, 1983
William E. Lorensen and Harvey E. Cline. 1987. Marching cubes: A high resolution 3D surface construction algorithm. SIGGRAPH Comput. Graph. 21, 4 (July 1987), 163–169. doi:https://doi.org/10.1145/37402.37422