Цей останній метод є гарним вибором між “трюком” з чистим OpenGL та реалізацією за допомогою зручного, повнофункціонального графічного рушія, від якого нам потрібен тільки raycast і вибір об’єктів.

Цей туторіал містить концепції і функції з туторіалу про Bullet, отже прочитайте спочатку його.

Базова ідея

Ми не будемо покладатись на те, що Bullet за нас знайте перетин променя і об’єкту, ми зробимо це самостійно.

Як ми бачили, є багато можливих об’єктів для “зіткнення”. Сфери дуже легкі для пошуку зіткнення, але для багатьох оригінальних мешей це зовсім не так. З іншої сторони, перевіряти перетин променю з кожним трикутником меша може бути дуже дуже дорого. Гарна середина - OBB (Oriented Bounding Boxes) - Орієнтований обмежувальний паралелепіпед (ящик, коробка). Вони досить точні (але багато чого залежить від Вашої геометрії) та дешеві в розрахунках.

OBB це паралелепіпед який вміщує меш і коли меш повертається чи переміщується, ці самі трансформації відбуваються і з ним:

Ray-OBB алгоритм

( Алгоритм і малюнки значною мірою натхненні книгою Real-Time Rendering 3. Купіть її!!! )

Розглянемо OBB, наведений нижче. По осі X він обмежений двома вертикальними площинами, забарвленими в червоне. Коли вони перетинаються з променем (дуже проста операція), це дає нам два перетини, один “близький”, один “далекий”:

Коли промінь перетинає дві інші площини, що обмежують вісь Y (виділено зеленим), це дає два додаткових перетини. Зверніть увагу, що перетини впорядковані - Ви входите через зелену область -> покидаєте зелену область -> входите в червону область -> покидаєте червону область. Це означає, що тут немає перетину.

Але якщо порядок інший (Ви ввійшли через зелену область -> Ви ввійшли через червону область), то Ви знаєте, що у Вас перетин!

Давайте попрактикуємося.

Реалізація алгоритму

(повний код доступний тут Misc05/misc05_picking_custom.cpp)

Наша функція, яка знаходить перетин променя(Ray) та OBB виглядає насупним чином:

bool TestRayOBBIntersection(
	glm::vec3 ray_origin,        // Початок променя, в світовому просторі
	glm::vec3 ray_direction,     // Напрям променя (не цільова позиція!) в світовому просторі. Має бути нормалізованою.
	glm::vec3 aabb_min,          // Мінімальні координати X,Y,Z меша, коли він повністю не трансформований.
	glm::vec3 aabb_max,          // Максимальні координати X,Y,Z. дуже часто це aabb_min*-1 якщо Ваш меш відцентровано, але це не завжди так.
	glm::mat4 ModelMatrix,       // Трансформації, які були накладені на меш. (і які повинні бути накладені на обмежувальний паралелепіпед)
	float& intersection_distance // Результат - відстань між ray_origin і перетином з OBB
){

Ми починаємо з ініціалізації декількох змінних. tMin є найбільшим ближчим перетином, що ми знайшли, tMax - найменший “далекий” перетин, який був знайдений. Delta використовується для пошуку перетину двох площин.

float tMin = 0.0f;
float tMax = 100000.0f;

glm::vec3 OBBposition_worldspace(ModelMatrix[3].x, ModelMatrix[3].y, ModelMatrix[3].z);

glm::vec3 delta = OBBposition_worldspace - ray_origin;

Тепер давайте обчислимо перетин з двома площинами, що обмежують OBB по осі X:

glm::vec3 xaxis(ModelMatrix[0].x, ModelMatrix[0].y, ModelMatrix[0].z);
float e = glm::dot(xaxis, delta);
float f = glm::dot(ray_direction, xaxis);

// Будьте обережні, не виконуйте ділення, якщо f близьке до нуля. Дивіться повний код для деталей.
float t1 = (e+aabb_min.x)/f; // Перетин з лівою площиною
float t2 = (e+aabb_max.x)/f; // Перетин з правою площиною

t1 та t2 тепер містять відстань між початком променя та перетином променя і площин, Але ми не знаємо в якому порядку, тому ми переконаємося, що t1 буде “ближчим” перетином, а t2 - “дальнім”:

if (t1>t2){ // якщо порядок невірний
	float w=t1;t1=t2;t2=w; // обміняємо t1 та t2
}

Можна оновити tMin та tMax :

// tMax є найближчим "дальнім" перетином (серед всіх X,Y і Z пар площин)
if ( t2 < tMax ) tMax = t2;
// tMin найдальшим "ближнім" перетином (серед всіх X,Y і Z пар площин)
if ( t1 > tMin ) tMin = t1;

Тут є одна особливість, якщо “найдальший” ближче ніж “найближчий”, то перетину немає.

if (tMax < tMin )
	return false;

Це все було для осі Х. Для всіх інших робимо те ж саме!

Використання алгоритму

Функція TestRayOBBIntersection() дозволяє нам перевіряти перетини лише з OBB, тому ми повинні перевірити їх всіх. В цьому туторіалі ми просто перевіримо всі паралелепіпеди по черзі, але якщо у Вас дуже багато об’єктів, то можливо Вам знадобиться додаткова структура для прискорення, наприклад, Binary Space Partitionning Tree (BSP-Tree) - (дерево бінарного розбиття простору, BSP-дерево) або Bounding Volume Hierarchy (BVH) - (Ієрархія обмежених об’ємів).

for(int i=0; i<100; i++){

	float intersection_distance; // результатf TestRayOBBIntersection()
	glm::vec3 aabb_min(-1.0f, -1.0f, -1.0f);
	glm::vec3 aabb_max( 1.0f,  1.0f,  1.0f);

	// Трансформація матриці моделі ModelMatrix:
	// - для меша, для отримання його позиції
	// - також для AABB (визначеного за допомогою aabb_min та aabb_max) в OBB
	glm::mat4 RotationMatrix = glm::toMat4(orientations[i]);
	glm::mat4 TranslationMatrix = translate(mat4(), positions[i]);
	glm::mat4 ModelMatrix = TranslationMatrix * RotationMatrix;

	if ( TestRayOBBIntersection(
		ray_origin, 
		ray_direction, 
		aabb_min, 
		aabb_max,
		ModelMatrix,
		intersection_distance)
	){
		std::ostringstream oss;
		oss << "mesh " << i;
		message = oss.str();
		break;
	}
}

Зверніть увагу, що алгоритм має певну ваду - він обирає перший OBB, який знайде. Але якщо потрібен OBB за ним, то це проблема. Отже Ви будете отримувати лише найближчий OBB!. Розв’язання цієї проблеми залишаємо читачу…

Переваги та недоліки

Переваги :

Просто
Невеликі витрати пам’яті (лише данні про OBB)
Не сповільнює OpenGL як інший метод

Недоліки :

Повільніше, ніж готова в рушію фізики, так як не використовує спеціальні структури для прискорення
Може бути не зовсім точною.

Висновки

Є ще багато інших способів розрахувати перетин, доступних для всіх видів фігур, що зіштовхуються, дивіться тут http://www.realtimerendering.com/intersections.html.

Якщо Вам потрібен точний перетин, потрібно використовувати перетин променя і трикутника. Знову, це не дуже гарна ідея перевіряти кожний трикутник в меші буквально. Потрібні різноманітні структури для прискорення.