Приналежність точки грані
Потрібно перевірити колізію в об'ємному просторі. Грань (площина) задана чотирма точками. Як визначити, чи належить точка цієї межі?
Порада №1: площина задається трьома точками (перша аксіома стереометрії).
І що? Гілка про плаский багатокутник, до того ж рішення навряд чи там є.
Напевно, це так, але якби я це знав, якби я знав вектори, то легко б упорався з питанням сам.
Якби там не було алгоритму рішення, я б тобі посилання не давав. а потім перевіряй належність точки кожному трикутнику.
У тебе випадок взагалі простий.
Порада №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 Якщо дорівнює нулю, то точка лежить на площині.
Якщо не знаєте, що таке "визначник" і як його обчислювати, то в інтернеті на цю тему інформації неміряно, чи може на форумі допоможуть. Успіхів!
Оце вже справа. Займусь!
Мабуть коректніше - порахувати відстань від площини до точки. У певному околиці нуля - вважати, що завгодно.
Але питання я б уточнив. Йдеться про колізію з гранню – а грань – частина площини (грань куба, піраміди). І про що? Про влучення точки на грань чи площину грані? Інакше мені незрозуміло виникнення, саме 4-х крапок.
Так саме відстань, томуяк рахуючи наведений визначник ми лише знаходимо обсяг певного паралеліпіпеда. І можна навести приклад (близько розташовані точки основи) - обсяг буде дуже маленький (умовний 0), проте четверта точка буде далеко від площини.
> І можна навести приклад (близько розташовані точки основи) – обсяг буде дуже маленький (умовний 0). точка буде далеко від площини
По-перше, не можна. Пам'ятайте, щоплощинанескінченна. Для кращого розуміння цей визначник краще інтерпретувати не як 1/6 обсягу паралелепіпеда, бо як рівняння площини (якщо взяти (x, y, z) як поточну точку). Так ось ми просто підставляємо координати точки, що перевіряється в це рівняння і дивимося, задовольняє точка цьому рівнянню чи ні, якщо задовольняє, значить точка лежить в площині.
Однак починаю підозрювати, що чотири точки вводяться саме для позначення грані. Щойно побачив назву гілки. Тоді розв'язання задачі розбивається на два етапи: 1. Перевірка належності точки площини грані (див. [5]) 2. Перевірка в "місцевих" координатах площини приналежності точки чотирикутнику як у звичайній двовимірній системі координат (див. сусідню гілку "Алгоритм попадання точки.", в одному з постів докладно розповідається як це зробити, тим більше що випадок спрощений - чотирикутник завжди випулий).
Вибачаюсь за помилку - змішаний твір дорівнює повному об'єму паралелепіпеда, а не 1/6, як було написано.
Плюс доповнення: у гілці "Алгоритм попадання крапки" пост [12]
>Але питання я б уточнив. Йдеться про колізію з гранню – а грань – частина площини (грань куба, піраміди). І про що? Про влучення точки на грань чи площину грані? Інакше мені незрозуміло виникнення, саме 4-х точок.
Мені справді потрібна колізія з гранню.
>2. Перевірка в "місцевих" координатах площини належності точки чотирикутнику як у звичайній двовимірній системі координат (див. сусідню гілку "Алгоритм влучення точки. ", в одному з постів докладно розповідається як це зробити, тим більше що випадок спрощений - чотирикутник завжди випулий). 6>
Як перевести до "місцевих координат"?
> тим більше що випадок спрощений - чотирикутник завжди випулий. Це в тій гілці? Або як?
Але можна 2 пункт і так: Треба розбити чотирикутник на 2 трикутники, що повністю лежать у чотирикутнику (на випадок невипуклості останнього). Потім вже дивитися колізії з цими трикутниками. Нам у зв'язку з 1-м, достатньо перевірити, куди потрапить проекція. Для цього можна чинити по-різному: 1. Як описано вище. 2. Постаріть на сторонах площини і подивитися в які напівплощини потрапить крапка - тут треба дуже акуратно розібратися зі знаками. 3. З нашої точки провести відрізки до вершин – вийде пірамідка, порахувати площі граней. Якщо площа основи "мало відрізняється" від суми площ бічних граней - то все пучком. До речі, цей спосіб можна застосовувати без обчислення відстані.
Напишу потім, що вийде.
Ви маєте рацію, перевірка рівнянням з [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]: чотирикутник може бути невипуклим.
функція 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);
if Angle >= PI * 2 - 0.1 then begin Result := True; Exit; end;
> Yar-Com (22.04.04 9:21) [18]Для опуклих багатокутників вірно. У загальному випадку, для неопуклих неправильно. Для випуклих принцип той же як і в мене з площами, але простіше. Кут - мається на увазі абсолютне значення?
Result := (Angle >= PI * 2 - 0.1)
так так, так дійсно краще) на рахунок опуклості, я думаю це не проблема потрібно тріангулювати.
функція AngleBetweenVectors(Vector1, Vector2: TVector): Single; begin Result := ArcCos(VectorDotProduct(VectorNormalize(Vector1),VectorNormalize(Vector2))); if IsNan(Result) then Result := 0; end;
це правда досить повільно все, але якщо використовувати ббокси і попередньо перевіряти їх на колізію, а вже потім знаходити більш точне місце зіткнення.