Как проверить столкновение полигона и сферы?

← →
c4 (2003-06-24 12:26) [0]

Не могу найти ничего конкретного.

← →
pasha676 (2003-06-24 13:28) [1]

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

← →
Kelegorm (2003-06-24 19:25) [2]

Знать надо МАТЕМАТИКУ: Линейную алгебру и Аналетическую геометрию. Мне 17, пиши мне, если нужны формулы. Для сферы просто возми растояние от центра, потом растояния до точек полигона, выбери из них минимальное и если оно меньше диаметра, то есть пересечение. Это для случая, когда полигон много меньше сферы.
ЕСЛИ Полигон больше сферы или любой могет быть
узнать растояние от центра сферы до плоскости
найти координаты этой точки
ЕСЛИ эта точка принадлежит треугольнику, то ЕСТЬ, или НЕТ пересечения.
Вот так всё просто работает. О том, принадлежит ли точка треугольнику, я могу тебе прислать *.pas файл с функцией.

← →
Aldor (2003-06-24 21:38) [3]

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

← →
pasha676 (2003-06-25 09:27) [4]

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

← →
Kelegorm (2003-06-25 11:24) [5]

Алдору:
Ты НЕПОНЯЛ. Или не дочитал до конца. Я пишу если треугольник большой, то НАЙТИ РАСТОЯНИЕ ОТ ЦЕНТРА ОКРУЖНОСТИ ДО ПЛОСКОСТИ ТРЕУГОЛЬНИКА. То есть опустить перпендикуляр. Потом посмотреть, длинну перпендикуляра. Здесь всё хитрей. Ничего делить не надо.
Кстати, другой метод.
узнать растояние до плоскости треугольника.
если меньше радиуса(то есть есть пересечение плоскости) и не внутри треугольника:
узнать коор. точки
узнать радиус сечения сферы плоскостью
сравнить с бижайшими точками треугольника.
ВСЁ! И просто и понятно.

← →
Aldor (2003-06-25 21:30) [6]

2 Kelegorm
Согласен. Не дочитал. Метод проверки принадлежности треугольнику проекции центра сферы на плоскость трегольника работает отично.

← →
Kelegorm (2003-06-28 21:40) [7]

НормальКПлоскости
Заданно - (X Y Z) координаты трех любых точек, принадлежащих(лежащих на) плоскости.
Результат - (X Y Z) координаты вектора нормали.
Описание.

// Это тип трехмерной точки. Так как я исп. DirectX, то тип обзывается TD3D. Название, конесно, роли // не играет.
// Это указатель на тип. Если не знал, то его можно объявить на неописанный до этой строчки тип. // Главное, чтобы тип был описан позднее.
PD3DVector = ^TD3DVector;
//Чесно говоря, я незнаю смысла следующей точки. Почему Packet
TD3DVector = packed record
x : Single;
y : Single;
z : Single;
end;

Function NormalFor3Points(P0, P1, P2 : TD3DVector):TD3DVector;
var x0,x1,x2,y0,y1,y2,z0,z1,z2:single;
wrkVector:TD3DVector;
wrkLength:Single;
begin
x0 := P0.x; y0 := P0.y; z0 := P0.z;
x1 := P1.x; y1 := P1.y; z1 := P1.z;
x2 := P2.x; y2 := P2.y; z2 := P2.z;
// D3DVector - Встроенная функция Директа, как и тип. Будет описанна ниже.
wrkVector := D3DVector( (y1-y0)*(z2-z0)-(y2-y0)*(z1-z0), (x2-x0)*(z1-z0)-(x1-x0)*(z2-z0), (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0));
//Затем мы нормализуем вектор, то есть, делаем его единичной длинны. От длинны нормали зависит,
//например, уровень освещенности.
wrkLength := sqrt( sqr(wrkVector.x) + sqr(wrkVector.y) + sqr(wrkVector.z));
// Это тоже встроенная функция. Делит вектор на длинну.
Result := VectorDivS(wrkVector, wrkLength);
end;

function D3DVector(x, y, z: Single): TD3DVector;
begin
Result.x := x;
Result.y := y;
Result.z := z;
end;

Сначала мы записываем в СВОЙ тип данных входные(на случай, если я "незнаю" или не объявлял опр. модулей). Затем используем математическую формулу для нахождения нормали. Есть одна особенность. Есть у трёх точек такая фишка. Если внутри треугольника поместить ось вращения, то точки по порядку, следуют по часовой стрелке, или против. Взависимости от этого, нормаль будет смотреть вверх или вниз. Эи две нормали отличаются только знаками всех трёх координат.
Потом мы нормализуем вектор. Сначала найдем его длинну, а затем каждую координату поделим на эту длинну.

Длинна := Корень квадратный(квадрат(X2-X1) + квадрат(Y2-Y1) + квадрат(Z2-Z1))
ИЛИ
Длинна := Корень квадратный(квадрат(dX) + квадрат(dY) + квадрат(dZ))

function VectorDivS(const v: TD3DVector; s: Single) : TD3DVector;
begin
result.x := v.x/s;
result.y := v.y/s;
result.z := v.z/s;
end;

Точка в треугольнике.
Эту идею предложили мне мои друзья, а я её доказал для выпуклых многоугольников и осуществил.
Принцип работы.(Данная функция предназначена для двух-мерного пространства, но этого достаточно)
по порядку следует N точек. Сторон тоже N. Это такие : точка[0]-точка[1]; точка[1]-точка[2]; .... точка[N-2]-точка[N-1]; точка[N-1]-точка[0]. Думаю, понятно.
Возмем на проверку точку O.
Затем по очереди проверяются все отрезки и посчитаем, если точка находится правее всех сторон, то она внутри, иначе снаружи. Значит, сначала мы берём первые две координаты и проверяем, лежит ли точка правее её, если да, то повторяем тоже самое с остальными сторонами.

TFreePoint = record
X, Y : Single;
end;

Function PointInAr(X, Y : Single; var Points : array of TFreePoint):Boolean;
var i : integer;
begin
For i := 0 to High(Points)-1 do
if PointRelatLine(X, Y, Points[i].X, Points[i].Y,Points[i+1].X, Points[i+1].Y) >= 0 then
begin
Result := True;
end
else
begin
Result := False;
Exit;
end;
end;

Это цикл. А вот функция, которая указывает, лежит ли точка правее, и возвращает a<0 - слева(справа), a=0 - на прямой, a>0 - справа(слева).

function PointRelatLine( X, Y : Single; X1, Y1, X2, Y2 : Single):Single;
begin
Result := (Y2 - Y1)*(X - X1) - (X2 - X1)*(Y - Y1);
end;

Как ни странно, на наших процессорах это работает очень даже быстро.

Понятно, что теперь следует сделать следующие шаги:
Определить как-нибудь плоскость по трем точкам.
Проверить, касается ли сфера этой плоскости, то есть надо нормаль к плоскости помножить на радиус сферы, отнять этот вектор от координат центра сферы, и найти точку пересечения с плоскостью. ( X, Y, Z) [7] НормальКПлоскости
Заданно - (X Y Z) координаты трех любых точек, принадлежащих(лежащих на) плоскости.
Результат - (X Y Z) координаты вектора нормали.
Описание.

// Это тип трехмерной точки. Так как я исп. DirectX, то тип обзывается TD3D. Название, конесно, роли // не играет.
// Это указатель на тип. Если не знал, то его можно объявить на неописанный до этой строчки тип. // Главное, чтобы тип был описан позднее.
PD3DVector = ^TD3DVector;
//Чесно говоря, я незнаю смысла следующей точки. Почему Packet
TD3DVector = packed record
x : Single;
y : Single;
z : Single;
end;

Function NormalFor3Points(P0, P1, P2 : TD3DVector):TD3DVector;
var x0,x1,x2,y0,y1,y2,z0,z1,z2:single;
wrkVector:TD3DVector;
wrkLength:Single;
begin
x0 := P0.x; y0 := P0.y; z0 := P0.z;
x1 := P1.x; y1 := P1.y; z1 := P1.z;
x2 := P2.x; y2 := P2.y; z2 := P2.z;
// D3DVector - Встроенная функция Директа, как и тип. Будет описанна ниже.
wrkVector := D3DVector( (y1-y0)*(z2-z0)-(y2-y0)*(z1-z0), (x2-x0)*(z1-z0)-(x1-x0)*(z2-z0), (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0));
//Затем мы нормализуем вектор, то есть, делаем его единичной длинны. От длинны нормали зависит,
//например, уровень освещенности.
wrkLength := sqrt( sqr(wrkVector.x) + sqr(wrkVector.y) + sqr(wrkVector.z));
// Это тоже встроенная функция. Делит вектор на длинну.
Result := VectorDivS(wrkVector, wrkLength);
end;

function D3DVector(x, y, z: Single): TD3DVector;
begin
Result.x := x;
Result.y := y;
Result.z := z;
end;

Сначала мы записываем в СВОЙ тип данных входные(на случай, если я "незнаю" или не объявлял опр. модулей). Затем используем математическую формулу для нахождения нормали. Есть одна особенность. Есть у трёх точек такая фишка. Если внутри треугольника поместить ось вращения, то точки по порядку, следуют по часовой стрелке, или против. Взависимости от этого, нормаль будет смотреть вверх или вниз. Эи две нормали отличаются только знаками всех трёх координат.
Потом мы нормализуем вектор. Сначала найдем его длинну, а затем каждую координату поделим на эту длинну.

Длинна := Корень квадратный(квадрат(X2-X1) + квадрат(Y2-Y1) + квадрат(Z2-Z1))
ИЛИ
Длинна := Корень квадратный(квадрат(dX) + квадрат(dY) + квадрат(dZ))

function VectorDivS(const v: TD3DVector; s: Single) : TD3DVector;
begin
result.x := v.x/s;
result.y := v.y/s;
result.z := v.z/s;
end;

Точка в треугольнике.
Эту идею предложили мне мои друзья, а я её доказал для выпуклых многоугольников и осуществил.
Принцип работы.(Данная функция предназначена для двух-мерного пространства, но этого достаточно)
по порядку следует N точек. Сторон тоже N. Это такие : точка[0]-точка[1]; точка[1]-точка[2]; .... точка[N-2]-точка[N-1]; точка[N-1]-точка[0]. Думаю, понятно.
Возмем на проверку точку O.
Затем по очереди проверяются все отрезки и посчитаем, если точка находится правее всех сторон, то она внутри, иначе снаружи. Значит, сначала мы берём первые две координаты и проверяем, лежит ли точка правее её, если да, то повторяем тоже самое с остальными сторонами.

TFreePoint = record
X, Y : Single;
end;

Function PointInAr(X, Y : Single; var Points : array of TFreePoint):Boolean;
var i : integer;
begin
For i := 0 to High(Points)-1 do
if PointRelatLine(X, Y, Points[i].X, Points[i].Y,Points[i+1].X, Points[i+1].Y) >= 0 then
begin
Result := True;
end
else
begin
Result := False;
Exit;
end;
end;

Это цикл. А вот функция, которая указывает, лежит ли точка правее, и возвращает a<0 - слева(справа), a=0 - на прямой, a>0 - справа(слева).

function PointRelatLine( X, Y : Single; X1, Y1, X2, Y2 : Single):Single;
begin
Result := (Y2 - Y1)*(X - X1) - (X2 - X1)*(Y - Y1);
end;

Как ни странно, на наших процессорах это работает очень даже быстро.

Понятно, что теперь следует сделать следующие шаги:
Определить как-нибудь плоскость по трем точкам.
Проверить, касается ли сфера этой плоскости, то есть надо нормаль к плоскости помножить на радиус сферы, отнять этот вектор от координат центра сферы, и найти точку пересечения с плоскостью. Врезультате возможно три варианта ответа: Пересекает(X, Y, Z), лежит(X, Y, Z), не перескает().
Если Пересекает, то нужно найти растояние от центра сферы до полученной точки, через тригонометрию определить радиус окружности - пересечение сферы и плоскости - и ВСЁ!

У нас следующие данные: Координаты точек треугольника, координаты и радиус окружности. Теперь НЕ-помню-что сделать с координатами и нормалью к плоскостью и получить трёхмерные координаты, в которых Z практически ноль, то есть координаты двумерные. Далее надо только найти общие точки окружности и треугольника, что просто, тем более координаты теперь двухмерны.

← →
с4 (2003-06-29 13:01) [8]

ОГРОМЕННОЕ СПАСИБО!

← →
с4 (2003-07-02 01:05) [9]

to Kelegorm
Чего-то не очень работает твоя функция NormalFor3Points

Вершины треугольника:
vertex[1].X:= 0.0;
vertex[1].Y:= 0.0;
vertex[1].Z:= 0.0;
vertex[2].X:= 0.0;
vertex[2].Y:= 3.0;
vertex[2].Z:= 0.0;
vertex[3].X:= 0.0;
vertex[3].Y:= 0.0;
vertex[3].Z:= 3.0;

Координаты нормаля выдает такие - 1 ;0 ;0
А должны быть 0;0;0

← →
K.o.Z (2003-07-04 01:11) [10]

2 Kelegorm
Хотелось бы спросить не обладаете ли вы эл. вариантом Аналитической геометрии, т.к. она сейчас необходима, а нет возможности найти.
Благодорю.

← →
Kelegorm (2003-07-04 12:44) [11]

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

← →
voland (2003-07-05 10:12) [12]

Kelegorm- ботанический программист.

← →
Kelegorm (2003-07-06 16:03) [13]

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

← →
voland (2003-07-06 16:16) [14]

:-(

Как проверить столкновение полигона и сферы? Найти похожие ветки