Как узнать, является ли треугольная сетка вогнутой или нет?
Учитывая трехмерную сетку треугольника, как я могу узнать, является ли она выпуклой или вогнутой? Есть ли алгоритм, чтобы проверить это? Если это так, было бы полезно определить диапазон допуска, чтобы игнорировать небольшие вогнутости.
Источник изображения: http://www.rustycode.com/tutorials/convex.html
Решение
Выпуклый многогранник может быть определено как пересечение конечного числа полупространств. Эти полупространства фактически являются полупространством, определяющим грани.
РЕДАКТИРОВАТЬ: Предполагая, что ваша сетка на самом деле определяет многогранник (то есть есть «внутри» и «снаружи»)
Вы можете сделать что-то вроде этого (псевдокод):
for each triangle
p = triangle plane
n = normal of p (pointing outside)
d = distance from the origin of p
//Note: '*' is the dot product.
//so that X*N + d = 0 is the plane equation
//if you write a plane equation like (X-P)*n = 0 (where P is any point which lays in the plane), then d = -P*n (it's a scalar).
for each vertex v in the mesh
h = v*N + d
if (h > Tolerance) return NOT CONVEX
//Notice that when v is a vertex of the triangle from which n and d come from,
//h is always zero, so the tolerance is required (or you can avoid testing those vertices)
end
end
return CONVEX
Другие решения
Для простого многоугольника, как вы его описали, вы можете проверить каждый внутренний угол в каждой вершине и проверить, находится ли угол ниже 180 градусов. Если это так, то нет никакой вогнутости. Если одна вершина превышает 180 °, она вогнутая.
Редактировать: для трехмерных сеток применима та же идея, но вы должны проверять каждую вершину каждого треугольника друг относительно друга, является ли угол между треугольниками выше или ниже 180 °