Блоґ одного кібера

Історія хвороби контуженого інформаційним вибухом

Перетин променя й трикутника

leave a comment »

Для тривимірного випадку.

Це досить часта задача в комп’ютерній графіці. Зокрема, визначити чи знаходиться точка всередині меша (якщо він замкнений), можна обчисливши кількість перетинів довільного променя що виходить з цієї точки з мешем. Якщо ця кількість непарна – точка всередині меша. Про обчислення зіткнень, та трасування променів взагалі мовчу.

Нам дано вектори \vec O – початок променя, \vec D – його напрям, \vec A,\ \vec B,\ \vec C – вершини трикутника. \vec X – перетин променя й трикутника.


Далі, ми записуємо два рівняння для знаходження точки перетину, зважаючи на два факти: вона лежить на промені і вона лежить в трикутнику:

\begin{cases} \vec X = \vec O + \vec D \cdot t \\   \vec X = \vec A + (\vec C - \vec A) \cdot v + (\vec B - \vec A) \cdot u \end{cases}

З першим рівнянням ясно – це параметричне рівняння променя. Точка \vec X – на промені, якщо t>0. Друге рівняння – параметричне рівняння трикутника в барицентричних координатах. Що вони таке краще пояснює ілюстрація:

Барицентричні координати

Або словами – це координати точки, в системі, в якій базисними векторами є сторони нашого трикутника. Точка лежить в трикутнику, якщо:

\begin{cases} u \geq 0\\ v \geq 0 \\ u+v \leq 1 \end{cases}

Щоб знайти ці параметри, перетворюємо першу систему в рівняння з трьома невідомими:

\vec D \cdot t + (\vec A - \vec C) \cdot v + (\vec A - \vec B) \cdot u = \vec A - \vec O

Яка насправді (щастить же нам), є системою, бо кожен вектор має три координати, і рівність має виконуватись для всіх трьох координат. Нам залишається лише цю систему розв’язати, і отримати потрібні нам t,u та v.

Можливий варіант, коли система вироджена, і не розв’язується. Це означає, що промінь паралельний площині трикутника.

Пишемо простеньку функцію:

import numpy 
 
def ray_triangle_intersect(O,D,A,B,C): 
        b = [A[0] - O[0],A[1] - O[1], A[2] - O[2]] 
        M = [[D[i],A[i]-C[i],A[i]-B[i]] for i in range(3)] 
        try: 
                t,v,u = numpy.linalg.solve(M,b) 
        except numpy.linalg.LinAlgError: 
                return False 
        if t<0 or v<0 or u<0: 
                return False 
        if v+u>1: 
                return False 
        return True

тести:

>>> print ray_triangle_intersect((0,0,0),(1,0,0),(1,-1,1),(1,-1,-1),(1,1,0)) 
True

проходять!

Питання того чому я це вчора написав неправильно, і чому я не зміг самостійно написати нормальне розв’язування СЛАР залишається відкритим. Але й numpy.linalg.solve працює чудово. Нащо ще щось своє писати? 🙂

Advertisements

Written by bunyk

Квітень 25, 2011 at 23:44

Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: