Объединить перекрывающиеся треугольники в многоугольник

Question

У меня есть куча перекрывающихся треугольников из 3D-модели, спроецированной в 2D-плоскость. Мне нужно объединить каждый остров трогательных треугольников в замкнутый невыпуклый многоугольник.

В результирующих многоугольниках не должно быть дыр (так как исходных данных нет).

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

Какой самый простой способ сделать это? Производительность не особенно важна, так как это будет сделано во время разработки.

Answer 1

Представьте проекцию на плоскость как «вид» модели (то есть направление проекции - это линия визирования, а проекция - это то, что вы видите). В этом случае границы полигонов, которые вы хотите вычислить, соответствуют силуэту модели.

Силуэт, в свою очередь, представляет собой набор ребер в модели. Для каждого ребра в силуэте смежные грани будут иметь нормали, которые либо направлены от плоскости, либо к плоскости. Вы можете проверить это, взяв точечное произведение нормали грани к плоскости нормали - найдите ребра, у смежных нормалей грани есть точечные произведения противоположных знаков с направлением проекции.

Как только вы нашли все ребра силуэта, вы можете соединить их вместе в границы нужных полигонов.

Как правило, вы можете узнать больше об обнаружении и извлечении силуэтов, прибегая к помощи таких терминов, как mesh silouette finding detection. Может быть, хорошее место для начала это здесь .

Answer 2

Попробуйте gpc или Общую библиотеку Clipper для полигонов.

Answer 3

Я также нашел этот [1] подход, который я попробую позже.

[1] 2d алгоритм контура для проецируемой трехмерной сетки