Обнаружение отверстий / отверстий в замкнутой треугольной сетке?

Question

Я хочу обнаружить (и закрыть) отверстия и отверстия / выдолбленные части замкнутой сетки. Я знаю, что для открытой сетки это можно сделать, найдя граничные ребра (ребра, принадлежащие только одному треугольнику), как описано здесь .

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

Answer 1

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

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