Точка внутри 3d замкнутого объема

Question

У меня есть 3-й замкнутый объем, определенный 6 поверхностями, каждая поверхность имеет 4 вершины.

Итак, я хочу проверить, находится ли данная точка внутри тома или вне его. Решение, которое я подумал было:

1. Нарисуйте случайную строку из заданной точки и проверить, где она пересекает поверхность, которые ограждают объем. Поскольку я использую векторную алгебру для вычисления пересечения прямой и поверхности, точка пересечения может находиться где угодно на трехмерной бесконечной поверхности.

2. Теперь я проверяю, находится ли эта точка пересечения на этой грани, которая лежит на бесконечной плоскости и охватывает громкость.

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

But I don't know how to check this feature of locating if it is on the surface 
or not. Can someone please suggest how can I do it. 



P.S. One way of doing this was extending ray casting to 3d but that involves 
comparison of slopes to check the orientation. So how can I check orientation 
of 3 points in 3d space. I have 4 vertices which make up that face, I know the 
point under consideration. How can I check if this point lies clockwise or 
counter clockwise to the surface. 

Answer 1

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

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

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

Первое, что вам нужно, чтобы адекватно определить ваши твердое тело, ограничивающее лицо с ребрами и несколько устанавливая ребра и вершину, которые ограничивают одно лицо, как лица соединяются, чтобы сформировать ваше тело.

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

Я попытаюсь проиллюстрировать ту же проблему в 2D, но по сути это то же самое в 3D:

Во-первых, у нас есть начальное Полигон, давайте предположим, что оно выпукло (это важное свойство для этого я укажем ниже):

Предположим, что это 3D-астероид, и вы - кто-то, кто идет по его поверхности. Если вы начнете ходить, вы пройдете все линии, выраженные желтым цветом. Это нормали, и для этого вам нужно знать с каждого лица, с которыми сталкиваются лица, и построить на этих поверхностях карту нормалей, как я сделал. Когда вы ходите по астероиду, вы отмечаете нормали, чтобы знать, где находится внутренняя часть астероида, и вы это ограничиваете. Теперь у нас есть карта нашего астероида со всеми нормалями. Давайте проведем полупространство под нами (одна сторона поверхности, которая ниже нас). В геометрии это может быть представлено плоскостью (плоскость обладает тем свойством, что все ее точки ортогональны вектору, поэтому X*V=0 где * представляет точку Если мы возьмем центр нашего полигона и нормальный вектор в качестве желтого вектора на нашем рисунке, мы получим (X - P)*N = 0, где X - это положение точки в плоскости, P - это наше положение (центр лица) и N вектор нормали к плоскости, указывая вверх (на внешней стороне астероида)

Ну, это уравнение обладает свойством, что если мы подставим X любым положением в пространстве, все точки X ниже самолет значение (X - P)*N < 0 и все значения неба имеют его > 0.

Если бы я сделать то же самое для четырех нормалей, я получаю это: ... дело в и точкой в ​​вопросе X будет похоронен в астероид, только если четыре самолета дайте (X - X_face)*(N_face) < 0, где сейчас X_face - это центр лица, а N_face - лицо, нормальное, указывающее наружу от нашего астероида. Точка будет находиться внутри астероида только, если применяются четыре условия.

Но что произойдет, если астероид не выпуклый?

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

проблема состоит в том, что многоугольник (или многогранник) не является выпуклой, и мы не можем применить алгоритм там Итак, сначала мы должны решить эту проблему. что он выпуклый.

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

Когда все ребра являются нормальными, нет проблем, так как наш астероид будет выпуклым, но когда какой-либо из них является аномальным, мы должны продолжать в этой плоскости (копать в астероиде на всей плоскости), пока не доберемся до другой поверхности (мы продлили плоскость до разделения наш полигон) как таковой:

как мы имеем конечное число ребер, и только некоторые из них были отмечены как аномальное, этот процесс является оправданным, чтобы закончить (помните, что вы можете получить другая сторона пытается найти лицо (сторона) вашего многогранника (многоугольника) с вершинами вверх и вершины вниз (в том смысле, который мы объясняли ранее))

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

Answer 2

Вы можете создать логическое условие для каждой поверхности, которое определяет, находится ли данная точка внутри или снаружи поверхности. Это может потребовать добавления информации о нормалях каждой поверхности (т. Е. Какая сторона поверхности «наружу»). Если это условие выполняется для каждой из шести поверхностей, то точка находится внутри объема.

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

Answer 3

Взгляните на этот вопрос: signed distance between plane and point

Теперь вам просто нужно проверить, если ваша точка находится на правой стороне (правильный знак) каждого из ваших поверхностей объема. Что-то вроде этого:

bool isInside(const std::vector<Planes>& planes, const Point& point){ 

    for(const auto& plane : planes){ 
    const auto dist = 
     dotProduct(plane.normal, vectorSubtract(point, plane.point)); 
    if(dist>0) return false; 
    } 

    return true; 
}; 

Answer 4

Таким образом, один из способов я думаю, что я могу сделать это:

Продлить луч литья на 3d поверхности, но которая включает в себя, как, возможно, раз луч от рассматриваемой точки пересекла объем. Это связано с нахождением точки пересечения линий и граней объема.

So what I can do is for a single face (and I will extend it to all the faces) 
is, I check for the point of intersection of 3d line and plane by doing simple 
algebra and then check if the point lies inside the cuboid formed by 
extremities of the vertices forming the face. i.e check if P(x.y,z) which is 
the point of intersection of line and plane lies inside the region defined by 
extremities of the surface. 
i.e. 

x > xlow and x < xhigh and y > ylow and y < yhigh and z > zlow and z < zhigh. 

These two conditions i.e. ray intersects the 3d plane and the intersection 
lies in this region proves that the intersection of ray and plane lies on the 
surface which encloses the volume. 


I can count the number of such intersections if it is odd, the point 
lies inside the volume if it is even the point lies outside the volume. 


Does anyone see a problem with this algorithm?