Разделение коробки на выпуклые тела вокруг вписанного тела (т.е. вырезание)

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

Я хотел бы «вырезать» тело из коробки и при этом разделить коробку на несколько выпуклых сегментов вокруг граней тела (надеюсь, если у тела n граней, то n сегментов). В основном, сделайте твердое отверстие в коробке. Вот картинка того, что я имею в виду:

введите здесь описание изображения

Однако это также должно работать для таких фигур:

введите здесь описание изображения

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


algorithm 3d geometry convex aabb
person Konstantin    schedule 02.03.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

В исходной постановке вопроса с произвольными внутренними формами, если вы хотите, чтобы число отрезков было конечным, вам в общем случае не повезло. В частности, если замкнутая форма является сферой, любая конечная часть поверхности сферы, хотя и выпуклая по отношению к сфере, обязательно вогнута по отношению к любому другому сегменту вне сферы, частью которого она является; таким образом, такой внешний сегмент не будет выпуклым и не будет соответствовать вашему требованию.

person Warren Dew    schedule 03.03.2014
comment
Все возможные формы действительно имеют конечное число плоских сторон. Дополню описание еще парой фото. - person Konstantin; 03.03.2014
comment
Я переместил свой второй абзац, который относится к отредактированному вопросу, в верхнюю часть моего ответа. - person Warren Dew; 03.03.2014

arrow_upward
1
arrow_downward

Построим список граней выпуклого тела, не лежащих на границе AABB, назовем его F, а список пирамид, изначально пустых, назовем P. Потом:

while F is not empty {
  for each vertex v of the AABB {
    for each face f in F {
      If v has line-of-sight to f (cross product test with face normal) {
        Build a pyramid p with base f and apex v
        Add p to P
        Remove f from F
        Add the other faces of p to F unless they lie on the AABB boundary
      }
    }
  }
}

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

person ryanm    schedule 04.03.2014