Водонепроницаемый алгоритм восстановления поверхности для организованного точечного облака

Question

У меня есть 3D-декартовый куб. Для каждой точки этого куба имеется соответствующее значение плотности. Когда плотность меняется внезапно, это означает, что есть полость. Теперь, чтобы найти полость, я вычисляю градиент в каждой точке куба. Это дает мне облако точек на поверхности полости. Теперь я хотел бы сшить поверхность полости, учитывая облако точек.

К сожалению, у меня нет опыта в реконструкции поверхности, и мне было интересно, может ли кто-нибудь порекомендовать подходящий алгоритм, который создаст закрытую поверхность полости?

Куб довольно большой, так что облако точек поверхности полости может легко составлять 500 000 точек или более. Я прочитал этот пост: robust algorithm for surface reconstruction from 3D point cloud?, который я считаю полезным. Однако, кажется, что проблема я столкнулся проще, учитывая, что:

1. координаты точек всегда целое число
2. Распределение Дело даже
3. расстояние от одной точки до ее ближайшего соседа либо 1, sqrt (2) или sqrt (3)

Answer 1

Возможно, вам нужен алгоритм marching cubes.

Answer 2

Алгоритм Marching Cubes будет выполнять именно то, что вы хотите. Для рабочей реализации (с использованием three.js для рендеринга графики), проверьте:

http://stemkoski.github.com/Three.js/Marching-Cubes.html

Для получения более подробной информации по теории, я думаю, что лучшая статья на сайте:

http://paulbourke.net/geometry/polygonise/