Принадлежность точки грани

← →
Шлац (2004-04-18 16:46) [0]

Нужно сделать проверку коллизии в обёъмном пространстве. Грань (плоскость) задана 4-мя точками. Как определить, принадлежит ли точка этой грани?

← →
Landgraph © (2004-04-18 17:18) [1]

http://delphimaster.net/view/9-1082207751/

← →
Aldor © (2004-04-18 18:22) [2]

Совет №1: плоскость задается тремя точками (первая аксиома стереометрии).

← →
Шлац (2004-04-18 18:46) [3]

>http://delphimaster.net/view/9-1082207751/

И что? Ветка про плоский многоугольнки, к тому же решение едва ли там есть.

2 Aldor:

Наверное, это так, но если бы я это знал, если бы я знал векторы, то без труда бы справился с вопросом сам.

← →
Landgraph © (2004-04-19 09:51) [4]

Если бы там не было алгоритма решения я бы тебе ссылку не давал.
Цитирую:
Viktor (17.04.04 17:47) [4]
Триангулируй свой полигон (разбей его на треугольники), а потом проверяй принадлежность точки каждому треугольнику.

У тебя случай вообще простой.

← →
Aldor © (2004-04-19 20:21) [5]

Совет №2 (он же ответ на вопрос):
Из Ваших четырех точек возьмите любые три, на лежащие на одной прямой (я все же настоятельно рекомендую Вам хранить только три точки). Пусть их координаты будут соответственно:
(x0, y0, z0)
(x1, y1, z1)
(x2, y2, z2)
а координаты проверяемой точки - (x, y, z).
Тогда Вам нужно всего-навсего вычислить определитель:
|x-x0 y-y0 z-z0 | |x1-x0 y1-y0 z1-z0| |x2-x0 y2-y0 z2-z0|
Если он равен нулю, то точка лежит на плоскости.

Если не знаете, что такое "определитель" и как его вычислять, то в интернете на эту тему информации немеряно, или, может, на форуме помогут. Удачи!

← →
Mihey © (2004-04-19 21:03) [6]

2 Aldor [5]:

Вот это уже дело. Займусь!

← →
Думкин © (2004-04-20 06:36) [7]

> Aldor © (19.04.04 20:21) [5]

Тут скорее, все-таки не о чистом 0 говорить надо будет, а о некоторой окрестности.

Видимо более корректно - посчитать расстояние от плоскости до точки. В определенной окрестности нуля - считать, что попало.

Но вопрос я бы уточнил. Речь идет о коллизии с гранью - а грань часть плоскости (грань куба, пирамиды). И речь о чем? О попадании точки на грань или на плоскость грани? Иначе мне непонятно возникновение, именно 4-х точек.

← →
Думкин © (2004-04-20 06:41) [8]

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

← →
Aldor © (2004-04-20 20:19) [9]

> И можно привести пример (близко расположенные точки основания) - объем будет очень маленький (условный 0)... точка будет далеко от плоскости

Во-первых, нельзя. Помните, что плоскость бесконечна. Для лучшего понимания этот определитель лучше интерпретировать не как 1/6 объема параллелепипеда, а как уравнение плоскости (если взять (x, y, z) как текущую точку). Так вот мы просто подставляем координаты проверяемой точки в это уравнение и смотрим, удовлетворяет точка этому уравнению или нет, если удовлетворяет, значит точка лежит в плоскости.

Однако начинаю подозревать, что четыре точки вводятся именно для обозначения грани. Только что увидел название ветки. Тогда решение задачи разбивается на два этапа:
1. Проверка принадлежности точки плоскости грани (см. [5])
2. Проверка в "местных" координатах плоскости принадлежности точки четырехугольнику как в обычной двумерной системе координат(см. соседнюю ветку "Алгоритм попадания точки...", в одном из постов подробно рассказывается как это сделать, тем более что случай упрощеный - четырехугольник всегда выпкулый).

← →
Aldor © (2004-04-20 20:36) [10]

Извиняюсь за ошибку - смешанное произведение равно полному объему параллелепипеда, а не 1/6, как было написано.

Плюс дополнение: в ветке "Алгоритм попадания точки" пост [12]

← →
Mihey © (2004-04-20 22:43) [11]

>Но вопрос я бы уточнил. Речь идет о коллизии с гранью - а грань часть плоскости (грань куба, пирамиды). И речь о чем? О попадании точки на грань или на плоскость грани? Иначе мне непонятно возникновение, именно 4-х точек.

Мне действительно нужна коллизия с гранью.

>2. Проверка в "местных" координатах плоскости принадлежности точки четырехугольнику как в обычной двумерной системе координат(см. соседнюю ветку "Алгоритм попадания точки...", в одном из постов подробно рассказывается как это сделать, тем более что случай упрощеный - четырехугольник всегда выпкулый).

Как перевести в "местные координаты"?

← →
Думкин © (2004-04-21 06:34) [12]

> Aldor © (20.04.04 20:19) [9]
> > И можно привести пример (близко расположенные точки основания)
> - объем будет очень маленький (условный 0)... точка будет
> далеко от плоскости
>
> Во-первых, нельзя. Помните, что плоскость бесконечна

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

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

Это в той ветке? Или как?

> Mihey © (20.04.04 22:43) [11]
> Мне действительно нужна коллизия с гранью.

Можно для начала посмотреть тут:
http://algolist.manual.ru/maths/geom/belong/poly2d.php
Я на вскидку делал бы так:
1. Определил бы расстояние до плоскости - если "удовлетворительно маленькое" идем дальше.
2. Затем т.к. при проекции взаиморасположения сохраняются, то спроецировал бы на одну из координатных плоскостей, если наша плоскость ей не параллельна. Для этого просто вычеркиваем одну из координат точек. Получаем плоскость и 2 координаты - далее по приведенной статье.

← →
Думкин © (2004-04-21 06:48) [13]

> Думкин © (21.04.04 06:34) [12]
> 2. Затем т.к. при проекции взаиморасположения сохраняются,
> то спроецировал бы на одну из координатных плоскостей, если
> наша плоскость ей не параллельна. Для этого просто вычеркиваем
> одну из координат точек. Получаем плоскость и 2 координаты
> - далее по приведенной статье.

Блин, абсолютно не верно - извиняюсь, дико. Поспешил.
Надо сделать преобразование переводящее нашу плоскость в одну из координатных. Потом уже с новыми координатами работаем как написано.

Но можно 2 пункт и так:
Надо разбить четырехуголник на 2 треугольника полностью лежащие в четырехуголнике (на случай невыпуклости последнего). Затем уже смотреть колизии с этими треугольниками. Нам в связи с 1-м, достаточно проверить куда попадет проекция. Для этого можно поступать по разному:
1. Как описано выше.
2. Посторить на сторонах плоскости и посмотреть в какие полуплоскости попадет точка - тут надо очень аккуратно разобраться со знаками.
3. Из нашей точки провести отрезки к вершинам - получится пирамидка, посчитать площади граней. Если площадь основания "мало отличается" от суммы площадей боковых граней - то все пучком. Кстати, этот способ можно применять и без вычисления расстояния.

Удачи.

← →
Думкин © (2004-04-21 06:48) [14]

Удалено модератором
Примечание: Дубль

← →
Mihey © (2004-04-21 20:50) [15]

Напишу потом, что получится.

[12]:

Вы правы, проверка уравнением из [5] может быть некорректна при слишком малой площади треугольника или если вершины близки к тому, чтобы лежать на одной прямой.
Действительно, лучше оценивать уклонение точки от плоскости:

Чтобы определить расстояние, нужно сначала определить уравнение плоскости:
Ax + By + Cz + D = 0

Как уже было сказано, распишите определитель из [5], сгруппируйте относительно x, y и z, считая их переменными и получите A, B, C и D.
Тогда расстояние от точки до плоскости можно будет вычислить по формуле:
Ax + By + Cz + D h = -------------------- (это значение взять по модулю) sqrt(A^2 + B^2 + C^2)
Внимание, здесь x, y, z это уже не переменные, а координаты Вашей проверяемой точки.

А на счет проверки принадлежности уже грани, когда принадлежность плоскости установлена, то там вполне работают методы, описанные в соседней ветке и в статье на algolist"е. К "местным" координатам в данном случае перейти очень просто - отбросить координату z. Для этих двух методов этого вполне достаточно. Только не забудьте разбить грань на треугольники - очень разумная идея.

P.S. Прошу прощения за ошибку в посте [9]: четырехугольник может быть невыпуклым.

> Aldor © (22.04.04 05:13) [16]
> в данном случае перейти очень просто - отбросить координату z. Для этих двух методов этого вполне достаточно. Только не забудьте разбить грань на треугольники - очень разумная идея.

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

← →
Yar-Com (2004-04-22 09:21) [18]

function PointInsidePolygon(Intersection: TVector; Polygon: array of TVector; VertexCount: Integer): Boolean; var i: Integer; Angle: Single; vA, vB: TVector; begin angle := 0; for i := 0 to VertexCount - 1 do begin vA := VectorSubtract(Polygon[i], Intersection); vB := VectorSubtract(Polygon[(i + 1) mod VertexCount], Intersection); Angle := Angle + AngleBetweenVectors(vA, vB); end; if Angle >= PI * 2 - 0.1 then begin Result := True; Exit; end; Result := False; end;

> Yar-Com (22.04.04 09:21) [18]

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

И еще:

Result := (Angle >= PI * 2 - 0.1)

так лучше.

← →
Yar-Com (2004-04-22 10:40) [20]

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

function AngleBetweenVectors(Vector1, Vector2: TVector): Single;
begin
Result := ArcCos(VectorDotProduct(VectorNormalize(Vector1), VectorNormalize(Vector2)));
if IsNan(Result) then Result := 0;
end;

← →
Yar-Com (2004-04-22 10:45) [21]

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

Принадлежность точки грани Найти похожие ветки