Триангуляция point cloud на С++?

Question

[Vitaliy]

Посмотрел CGAL, PCL, они хорошо справляются с задачей генерации мешей из облака точек, но большой их минус - они объемные и имеют несколько зависимостей, из-за этого их использование в клиентском приложении из-за одной фичи будет неоправданным. Ладно там Desktop, но необходимо под Web портировать, где размер файла важен. А с одной из этих библиотек боюсь представить, на сколько увеличится размер .js (на 2 мб, или все 5?)

Из легковесных библиотек (или даже исходника в пару файлов) ничего не удалось найти. Надеюсь, кто-то сможет подсказать рабочие реализации, так как разбираться в нюансах и писать самому по времени затратно

Answer 1

[Vitaliy]

Все что удалось найти, без зависимостей:
https://github.com/mkazhdan/PoissonRecon
https://github.com/hhoppe/Mesh-processing-library

Первый работает хорошо, документация неплохая, вроде бы заточить под определенные проекты не должно возникнуть проблем,
По второму не удалось найти документации, есть только сайт автора

Answer 2

[exaw]

Можно попробовать аккуратно выпилить и собрать из CGAL или VTK только то, что нужно, если там лицензии позволяют таким заниматься.

Comments

[Vitaliy]

Рассматривал такой вариант, пока не рассмотрел код - если не утонуть в нем, то на выпиливание все равно уйдет много времени

[exaw]

Алгоритмы специализированные, само наличие открытых эффективных и надежных реализаций - уже большое достижение, думаю, что нелегко будет найти что-то другое. На серверной стороне сложными штуками заниматься не вариант?

[Vitaliy]

exaw: на серверной не вариант, могло бы послужить временным решением, но все же некоторые вещи лучше на клиент перенести

Answer 3

[tsarevfs]

https://github.com/greenm01/poly2tri
www.cs.cmu.edu/~quake/triangle.html
Ну и можно искать дальше по запросу delaunay triangulation c++ library

Comments

[Vitaliy]

дело в том, что по Делоне либо в 2.5D триангулирует, либо в 3D тетраэдрами, таким образом заполняя внутреннее пространство, чего быть не должно.

[Vitaliy]

На данный момент нашел подходящие алгоритмы и пару реализаций к ним, но толком не опробовал. Позже отпишусь

[tsarevfs]

Виталий Столяров: А может вам выпуклая оболочка нужна? quickhull алгоритм. Кстати, забавный факт: на шаре выпуклая оболочка == триангуляции делоне.

[Vitaliy]

tsarevfs: нет, невыпуклая

[tsarevfs]

Виталий Столяров: Если хочется восстановить невыпуклую фигуру, я бы попробовал триангуляцию тетраедрами -> выкинуть длинные ребра -> выкинуть внутренние ребра.

[Vitaliy]

tsarevfs: боюсь представить на сколько это будет ресурсоемкая задача дополнительно выкидывать внутренние части

[tsarevfs]

https://en.wikipedia.org/wiki/Alpha_shape еще такие штуки есть.

[tsarevfs]

Виталий Столяров: В 3d сканировании, есть подход, когда работают с поверхностями (картами глубин). данные с разных "кадров" склеивают, не переходя от поверхностей к облаку точек.