Определите, находится ли точка внутри треугольника в 3D

Я ищу подтверждение для своего восприятия метода определения того, находится ли точка внутри треугольника или нет в 3D.Определите, находится ли точка внутри треугольника в 3D

Для луча в виде R (t) = e + td и набора из трех точек T = {V0, V1, V2}, который образует треугольник в трех измерениях, я знаю, как найти параметрическое уравнение для плоскость, которую образуют три точки, и как определить, пересекает ли луч эту плоскость или нет. Наконец, если он пересекается, я хочу знать, действительно ли точка пересечения находится в пределах границ треугольников.

См. Мою фотографию ниже.

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

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

источник

2016-05-31 Great Cubicuboctahedron

Я построил пример, чтобы проверить метод, и кажется, что он работает .. по крайней мере, в этом случае. Я все еще ищу окончательный ответ. Треугольник I составлен из вершин {P0, P1, P2} = {(0,0,0), (5,0,5), (5,0,0)} и точек, которые я обозначаю w = (3, -5, 0) och u = (5, 5, 5), чтобы сформировать линию, которая, как я знал, пересекала бы треугольник в какой-то точке. –

это неверно; проверка точечного продукта работает только в том случае, если граница является прямым углом –

@willywonka_dailyblah. Если я позволяю векторам идти против часовой стрелки, точно так, как я описал в своем тексте и на изображении выше, я не понимаю, почему это должно быть проблема? Не могли бы вы объяснить, что вы имеете в виду? –

В графике люди обычно используют барицентрические координаты. В вашем случае P можно описать как P = aV0 + bV1 + cV2, где a + b + c = 1. P находится внутри, если и только если 0 < = a, b, c < = 1. Если треугольники, образованные v1, P, v2, имеют площадь S1, треугольник от P, v0, v2 имеет площадь S2, а P, V0, V1 имеет площадь S3. Тогда a = S1/S, b = S2/S и c = S3/S, где S - площадь треугольника V0, V1, V2. Найти область S = 1/2 || (V0-V1) creosspdoruct (V0-V2) ||. Вы можете проверить учебник, который я наношу на моем сайте здесь: http://pages.cpsc.ucalgary.ca/~amahdavi/pmwiki-2.2.8/uploads/Site/RayTracing3.ppt

источник

2016-05-31 17:46:28

Спасибо за ваш ответ, я обязательно проведу ваш учебник! Не могли бы вы взглянуть на третий метод на этой странице? Http://totologic.blogspot.se/2014/01/accurate-point-in-triangle-test.html Что отличает этот метод и тот, который я предложил? ? –

Также я нашел это: http://www.scratchapixel.com/lessons/3d-basic-rendering/ray-tracing-rendering-a-triangle/ray-triangle-intersection-geometric-solution Цитата: "найти если P находится внутри треугольника, мы можем проверить, является ли точечное произведение вектора вдоль ребра и вектора, определяемого первой вершиной испытанного ребра, и P положительно (это означает, что P находится в левой части края). P находится слева от всех трех ребер, тогда P находится внутри треугольника ». –

Вы уверены, что у вас одинаковые настройки? В третьем методе вы не должны найти точечный продукт v0v1 и v0p. Кажется, вам нужно найти точечный продукт лево-ортогонального к v0v1, как описано в учебнике: для этого сначала нам нужно рассмотреть 3 вектора v1, v2 и v3, которые соответственно лево-ортогональны [p1, p2], [p2, p3] и [p3, p1]: v1 = v2 = v3 = –

Вы хотите решить

E + t.D = a.V0 + b.V1 + c.V2

где

t, a, b, c >= 0, a + b + c = 1

Используя c = 1 - a - b, вы получите 3x3 линейную систему (разлагаются для x, y, z)

a.(V0 - V2) + b.(V1 - V2) - t.D = E - V2

что вы можете решить для t, a, b, затем c и проверить положительность.

источник

2016-05-31 22:33:07

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

Для треугольника a, b, c и точек p вычислительных m и s для каждого ребра. m - это точка, где p проектов на краю ab.

m = (p - a) • (b - a)/|b - a|² * (b - a) + a 
s = (p - m) • (c - m)

Если s положительна, то p и c находятся на одной и той же стороне ab. Повторите это испытание для каждого края.Если p и противоположная вершина находятся на одной стороне каждого края, то p находится в треугольнике.

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

Для |b - a|² вы можете использовать (b - a) • (b - a), если длина квадрата недоступна.

источник

2018-01-27 13:02:17 drawnonward

Определите, находится ли точка внутри треугольника в 3D

ответ

Смежные вопросы