Находится ли точка внутри пространственного выпуклого многогранника?

Подскажите, правильно ли я понимаю алгоритм проверки нахождения точки внутри пространственного выпуклого многогранника? Речь идет о пространственных(типа куба, тетраэдра), а не о плоских многогранниках.

Точка находится внутри выпуклого многогранника, если при нахождении расстояния от точки до плоскости грани, вычисляемой по формуле: (A*x + B*y + C*z + D) / sqrt(A*A + B*B + C*C)/*где A, B, C- координаты нормали плоскости, x,y,z-координаты проверяемой точки*/ для каждой грани знак результата будет одинаков.

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

А также две одинаковые совпадающие плоскости, но с противоположно направленными нормалями дадут разный знак при нахождении расстояния от точки до них?

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

Если нормали всех граней согласованы (все внутрь или все наружу), то одинаковый знак всех (A*x + B*y + C*z + D) говорит, что точка внутри.

алгоритм математически верен, но практически так никто не делает. удобнее хранить ограничивающие плоскости не коэффициентами уравнения плоскости A, B, C, D, а, например, точкой и нормалью, или просто тремя точками, или нормалью и проекцией любой из точек плоскости на эту нормаль. если, например, плоскость задана тремя точками, то проверить, по какую сторону от неё лежит точка можно, например, так:

Ага, спасибо. Таким образом, скорость алгоритам пропорциональна числу граней. Для тетраэдра -4, пирамиды -5, для куба -6.

graveman > Таким образом, скорость алгоритам пропорциональна числу граней обратно пропорциональна.

Suslik И важен порядок множителей cross-оператора

Suslik > добнее хранить ограничивающие плоскости не коэффициентами уравнения плоскости > A, B, C, D, а, например, точкой и нормалью, ага. только это одно и тоже ;) нормаль к проскости это N= а точка - N * D

> или просто тремя точками, фэйл. дополнительный cross это что? особый шик? а если в сцене тысячи объектов? а если еще 20 источников света, и для каждого надо посчитать видно \ не видно \ что затеняет. всетаки веркторное произведение - это как несколько dot продуктов. зачем так бездарно их тратить впустую? да и нелогично хранить плоскость ввиде трех точке, когда она изначально задается нормалью и точкой (например тотже фрустум).

graveman хранить удобнее ввиде номали и значения D (т.е. ввиде тогоже уравнения, но нормализованного) попала не попала точка внутрь объема dot(N, V) + D < 0.f (ну или больше, в зависимости от того куда нормали направлены, наружу или внутрь).

зы. да и хранить 4 флоата - куда дершевле чем три вектора. конечно во многих случаях не опримизация, но код короче и проще читается

Kloun > ага. только это одно и тоже математическая эквивалентность далеко не всегда следует практическая

> фэйл. дополнительный cross это что? особый шик? а если в сцене тысячи объектов? > а если еще 20 источников света, и для каждого надо посчитать видно \ не видно \ > что затеняет. всетаки веркторное произведение - это как несколько dot > продуктов. зачем так бездарно их тратить впустую? да и нелогично хранить > плоскость ввиде трех точке, когда она изначально задается нормалью и точкой > (например тотже фрустум). угадай что делает кросс продакт? считает нормаль. реалии жизни в том, что вовсе не всегда позволительно хранить для каждого треугольника ещё и нормаль, тем более в случае выпуклой геометрии, которую можно задать просто как выпуклое облако точек, информация о полигонах избыточна.

> зы. да и хранить 4 флоата - куда дершевле чем три вектора Suslik >удобнее хранить ограничивающие плоскости не коэффициентами уравнения плоскости A, B, C, D, а, например, точкой и нормалью, или просто тремя точками, или ***нормалью и проекцией любой из точек плоскости на эту нормаль*** если есть такая возможность - ради бога.

Kloun > ага. только это одно и тоже математическая эквивалентность далеко не всегда следует практическая

Suslik > случае выпуклой геометрии, которую можно задать просто как выпуклое облако > точек, информация о полигонах избыточна. И кстати верно. И плюс еще одна точка внутри. Если знак для искомой точки и для внутренней точки совпадает по всем плоскостям, то искомая точка тоже внутри. Только если есть только точки, как понять, какие тройки (или группы) образуют грань, а какие нет? Это же целый сложный алгоритм обхода облака точек, а если бы хранить хотя бы полигоны граней (да просто положение проскостей) + 1 точку внутри. тогда все было бы очень просто! да и мало данных хранить! сколько чисел задают плоскость?

Мне кажется три числа задают плоскость, а не "4 - ABCD, нормаль и сдвиг по нормали D" (три степени свободы). Возьмем координаты точки на шаре (центр шара в начале координат) - их две: широта и долгота. В этой точке проведем касательную плоскость к шару; наша будет ей параллельна, и совпадет, если взять радиус шара равным 3-ему числу. Итак, 3 числа на грань (а там может быть куча точек) и 3 числа на все тело - координаты внутренней точки. Все!

graveman > является ли проверка попадания точки в пирамиду видимости лишь частным случаем > этого алгоритма. Проверка кем?

SeriousProgrammer > И кстати верно. И плюс еще одна точка внутри. Если знак для искомой точки и для внутренней точки совпадает по всем плоскостям, то искомая точка тоже внутри. лучше настроить обход вершин в правильном порядке при расчете коэффициентов, чем добавлять лишнее сравнение > Только если есть только точки, как понять, какие тройки (или группы) образуют грань, а какие нет? так хранить же нужно не точки, а уравнения плоскостей на каждую грань, список которых строится только один раз в начале, после вершины знать не обязательно > Возьмем координаты точки на шаре (центр шара в начале координат) - их две: широта и долгота. В этой точке проведем касательную плоскость к шару; > наша будет ей параллельна, и совпадет, если взять радиус шара равным 3-ему числу. шо? причем здесь шар? ты имеешь виду полярную систему координат? на*?

SeriousProgrammer > Мне кажется три числа задают плоскость, а не "4 - ABCD, нормаль и сдвиг > по нормали D" ты абсолютно прав. уравнение Ax+By+Cz+D=0 легко приводиться к виду Px+Qy+Rz + 1 = 0; нормализованный 3ех мерный векотор - это тоже два числа для хранения, так как третье легко восстанавливается из первых двух. но дело в том, что нормаль к поверхности может участвовать в других вычислениях и нормализовать вектор P Q R каждый раз - не разционально. использование нормали и значения D - это по-моему дефакто принятный стандарт для гафических приложений. (конечно в разных задачах могут разные формы представления плоскости быть удобнее, но лично мне встречаться не приходилось с ними)

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

Suslik > угадай что делает кросс продакт? считает нормаль. реалии жизни в том, что вовсе > не всегда позволительно хранить для каждого треугольника ещё и нормаль, тем > более в случае выпуклой геометрии, которую можно задать просто как выпуклое > облако точек, информация о полигонах избыточна. дело в том, что по облаку точек, довольно сложно определить находится ли дополнительная точка внутри данного облака или снаружи, так как произвольно взятые 3 точки из облака - не есть грань. а вот для грани хранить координаты ее точек - определенно лишнее, зачем они? если грань используется для определения границ и теста на вхождение точки в ограниченный плоскостями объем?

Suslik > угадай что делает кросс продакт? считает нормаль да ты что? серьезно? а попробуй угадать что делает нормаль в представлении плоскости как вектора и числа? ага правильно - она избавляет от необходимости при рассчетах проводить дополнительные вычисления.

Suslik > математическая эквивалентность далеко не всегда следует практическая ну если ты про то, что тройка ABC может быть ненормализованным вектором то да. но тогда смысла хранить ввиде произвольных ABCD, завсегда лучше либо избавиться от Д либо номализвать АБЦ

зы. и по поводу облака точек. хранить как правило лучше в том виде, в котором затем удобно использовать. для ограничивающего объема - очевидно удобнее (и даже! менее затратно по памяти! что не всега совпадает) хранить грани ввиде нормаль + скаляр. для проверки попадания точки в объем в таком случае нужно просто последовательно пробежаться по гранятм и сделать проверку (N dot P + D три умножения три сложения) в случае если хранить объем как облако точек - то для вычисления вхождения надо как минимум по этому облаку построить convex hull

SeriousProgrammer > Проверка кем? В каком смысле? Движком.

📎📎📎📎📎📎📎📎📎📎