-
Notifications
You must be signed in to change notification settings - Fork 0
/
3dmath.cpp
591 lines (467 loc) · 40 KB
/
3dmath.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
#include "3dmath.h"
#include <math.h>
// * Нахождение нормали полигона * \\
// Чтобы найти нормаль полигона, нам нужно найти результат cross-a от двух
// векторов этого полигона. В общем, это всё, что нам нужно для получения направлений
// двух сторон треугольника. В конце концов, вектор - это только направление и длинна.
// Длинна вектора в нашем случае не важна. Нам нужно только узнать направление.
// Итак, имея 2 вектора треугольника, мы можем найти вектор, стоящий перпендикулярно
// к полигону.
// Теперь, в зависимости от порядка следования вершин, нормаль будет расположена с
// какой-то из сторон полигона. Вам остаётся только решить, в каком порядке отрисовывать
// вершины - ВСЕГДА запоминайте это.
// Обычно полигоны отрисовываются только с одной стороны. Никому не нужно второй раз
// отрисовывать сторону, которую не видно. Задумайтесь, если у вас есть какая-нибуть 3д
// модель, нужно ли вам отрисовывать внутренние стороны её полигонов? Конечно нет,
// это безсмысленно.
//
/////////////////////////////////////// CROSS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
///// Возвращает вектор, перпендикулярный 2м переданным.
/////
/////////////////////////////////////// CROSS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
CVector3 Cross(CVector3 vVector1, CVector3 vVector2)
{
CVector3 vNormal; // результирующий вектор
// Еще раз, если у нас есть 2 вектора (2 стороны полигона), у нас есть плоскость.
// cross находит вектор, перпендикулярный плоскости, составляемой 2мя векторами.
// Формула в принципе проста, но сложна для запоминания:
// The X value for the vector is: (V1.y * V2.z) - (V1.z * V2.y)
vNormal.x = ((vVector1.y * vVector2.z) - (vVector1.z * vVector2.y));
// The Y value for the vector is: (V1.z * V2.x) - (V1.x * V2.z)
vNormal.y = ((vVector1.z * vVector2.x) - (vVector1.x * vVector2.z));
// The Z value for the vector is: (V1.x * V2.y) - (V1.y * V2.x)
vNormal.z = ((vVector1.x * vVector2.y) - (vVector1.y * vVector2.x));
return vNormal; // Возвращаем результат (направление, куда направлен полигон - нормаль)
}
/////////////////////////////////////// MAGNITUDE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
///// возвращает величину нормали
/////
/////////////////////////////////////// MAGNITUDE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
float Magnitude(CVector3 vNormal)
{
return (float)sqrt( (vNormal.x * vNormal.x) +
(vNormal.y * vNormal.y) +
(vNormal.z * vNormal.z) );
}
/////////////////////////////////////// NORMALIZE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
///// возвращает нормализованный вектор (с длинной 1)
/////
/////////////////////////////////////// NORMALIZE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
CVector3 Normalize(CVector3 vNormal)
{
float magnitude = Magnitude(vNormal);
vNormal.x /= magnitude;
vNormal.y /= magnitude;
vNormal.z /= magnitude;
return vNormal;
}
/////////////////////////////////////// NORMAL \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
///// Возвращает нормаль полигона
/////
/////////////////////////////////////// NORMAL \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
CVector3 Normal(CVector3 vTriangle[])
{
CVector3 vVector1 = vTriangle[2] - vTriangle[0];
CVector3 vVector2 = vTriangle[1] - vTriangle[0];
// В функцию передаются три вектора - треугольник. Мы получаем vVector1 и vVector2 - его
// стороны. Теперь, имея 2 стороны треугольника, мы можем получить из них cross().
// (*ЗАМЕЧАНИЕ*) Важно: первым вектором мы передаём низ треугольника, а вторым - левую
// сторону. Если мы поменяем их местами, нормаль будет повернута в противоположную
// сторону. В нашем случае мы приняли решение всегда работать против часовой.
CVector3 vNormal = Cross(vVector1, vVector2);
// Теперь, имея направление нормали, осталось сделать последнюю вещь. Сейчас её
// длинна неизвестна, она может быть очень длинной. Мы сделаем её равной 1, это
// называется нормализация. Чтобы сделать это, мы делим нормаль на её длинну.
// Ну а как найти длинну? Мы используем эту формулу: magnitude = sqrt(x^2 + y^2 + z^2)
vNormal = Normalize(vNormal);
// Теперь вернём "нормализованную нормаль" =)
// (*ПРИМЕЧАНИЕ*) если вы хотите увидеть, как работает нормализация, закомментируйте
// предидущую линию. Вы увидите, как длинна нормаль до нормалицации. Я стого рекомендую
// всегда использовать эту функцию. И запомните, неважно, какова длинна нормали
// (конечно, кроме (0,0,0)), если мы её нормализуем, она всегда будет равна 1.
return vNormal;
}
float PlaneDistance(CVector3 Normal, CVector3 Point)
{
float distance = 0; // Переменная хранит дистанцию плоскости от начала координат
// Используем уравнение плоскости для нахождения дистанции (Ax + By + Cz + D = 0).
// Нам нужно найти D. Больше информации об уравнении плоскости будет ниже (в IntersectedPlane()).
// Основное: A B C - это значения X Y Z нашей нормали, а x y z - это x y z нашей точки.
// D - дистанция от начала координат. Итак, нам нужно воспользоваться этим уравнением, чтобы найти D.
distance = - ((Normal.x * Point.x) + (Normal.y * Point.y) + (Normal.z * Point.z));
return distance; // Возвратим дистанцию
}
// С прошлого урока мы добавим ещё 2 параметра для нормали и дистанции в функцию IntersectedPlane().
// Это делается, чтобы не пересчитывать всё три раза в IntersectionPoint() и IntersectedPolygon().
// Может быть потом мы даже сделаем разные функции, чтобы выбирать, хотим ли мы рассчитать заодно
// нормаль и дистанцию. Я также заменил vTriangle на "vPoly", так как это не обязательно должен быть
// треугольник.
// Итак, изменяем функцию IntersectedPlane():
bool IntersectedPlane(CVector3 vPoly[], CVector3 vLine[], CVector3 &vNormal, float &originDistance)
{
float distance1=0, distance2=0; // Дистанция 2х точек линии
vNormal = Normal(vPoly); // Рассчитываем нормаль плоскости
// Найдем дистанцию плоскости от начала координат:
originDistance = PlaneDistance(vNormal, vPoly[0]);
// Получим дистанции от первой и второй точек:
distance1 = ((vNormal.x * vLine[0].x) + // Ax +
(vNormal.y * vLine[0].y) + // Bx +
(vNormal.z * vLine[0].z)) + originDistance; // Cz + D
distance2 = ((vNormal.x * vLine[1].x) + // Ax +
(vNormal.y * vLine[1].y) + // Bx +
(vNormal.z * vLine[1].z)) + originDistance; // Cz + D
// Проверим на пересечение
if(distance1 * distance2 >= 0)
return false;
return true;
}
// Следующая функция производит "рассчет оператора точки" (Dot product):
float Dot(CVector3 vVector1, CVector3 vVector2)
{
// Вот формула Dot product: V1.V2 = (V1.x * V2.x + V1.y * V2.y + V1.z * V2.z)
// В математическом представлении она выглядит так: V1.V2 = ||V1|| ||V2|| cos(theta)
// '.' называется DOT. || || - величина, она всегда положительна. То есть величина V1
// умножить на величину V2 умножить на косинус угла. Выглядит устрашающе, но позже станет
// яснее. Эта функция используются во множестве ситуаций, которые будут описаны в других
// уроках. В этом уроке с её помощью мы будем получать угол между двумя векторами.
// Если векторы нормализованы, dot product вернет косинус угла между 2мя векторами.
// Что это значит? Это значит, что на самом деле возвращается не сам угол, а cos(angle).
// Ну а что если мы хотим получить сам угол? Тогда мы используем аркосинус.
// Больше об этом будет написано в функции AngleBetweenVectors(). Давайте рассмотрим
// пример использования dot product. Как вычислить угол между перпендикулярными векторами?
// Если мы нормализуем вектор, мы можем получить результат ||V1|| * ||V2||, останется только
// найти cos(theta). Если вектор нормализован, его величина - 1, так что получится 1*1*cos(theta),
// что бессмысленно, так что мы отбрасываем эту часть формулы. Итак, что такое косинус 90?
// Если вы возьмете калькулятор, то узнает, что это 0. И получается, что если результат Dot()
// равен нулю, векторы перпендикулярны. Всё что мы делали - получили аркосинус нуля, который
// равен 90.
// (V1.x * V2.x + V1.y * V2.y + V1.z * V2.z)
return ( (vVector1.x * vVector2.x) + (vVector1.y * vVector2.y) + (vVector1.z * vVector2.z) );
}
////////////////////////////////////////////////////////////////////////////////
//
// Следуюшая функция возвращает угол между векторами
//
////////////////////////////////////////////////////////////////////////////////
double AngleBetweenVectors(CVector3 Vector1, CVector3 Vector2)
{
// Помните, выше мы говорили, что Dot product возвращает косинус угла между
// двумя векторами? Подразумевается, что векторы нормализованы. И, если у нас нет
// нормализованного вектора, то просто делаем arcCos(DotProduct(A, B))
// Нам нужно разделить dot product на величину двух умноженных друг на друга
// векторов. Вот формула: arc cosine of (V . W / || V || * || W || )
// ||V|| - это величина V. Это "отменит" величины dot product.
// Но если вы уже нормализовали векторы, вы можете забыть о величинах.
// Получаем Dot от обоих векторов
float dotProduct = Dot(Vector1, Vector2);
// Получаем умножение величин обоих векторов
float vectorsMagnitude = Magnitude(Vector1) * Magnitude(Vector2) ;
// Получаем аркосинус от (dotProduct / vectorsMagnitude), что есть угол в градусах.
double angle = acos( dotProduct / vectorsMagnitude );
// Теперь убедимся, что угол не -1.#IND0000000, что означает "недостижим". acos() видимо
// считает прикольным возвращать -1.#IND0000000. Если мы не сделаем этой проверки, результат
// проверки пересечения будет иногда показывать true, когда на самом деле пересечения нет.
// я выяснил эту фичу тяжким трудом после МНОГИХ часов и уже написанных неверных уроков ;)
// Обычно это значение возвращается, когда dot product и величина имеют одинаковое значение.
// Мы вернём 0 если это случается.
if(_isnan(angle))
return 0;
// Вернем угол в градусах
return( angle );
}
/////////////////////////////////// INSIDE POLYGON \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
///// Проверяет, находится ли точка внутри полигона
/////
/////////////////////////////////// INSIDE POLYGON \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
bool InsidePolygon(CVector3 vIntersection, CVector3 Poly[], long verticeCount)
{
const double MATCH_FACTOR = 0.9999; // Исп. для покрытия ошибки плавающей точки
double Angle = 0.0; // Инициализируем угол
CVector3 vA, vB; // Временные векторы
// Одно то, что линия пересекает плоскость, ещё не значит, что она пересекает полигон в
// этой плоскости. Эта функция проверяет точку пересечения на предмет того, находится ли
// она внутри полигона.
// На самом деле мы используем замечательный метод. Он создает треугольники внутри
// полигона от точки пересечения, проводя линии к каждой вершине полигона. Потом все углы
// созданных треугольников складываются. И если сумма углов равна 360, то мы внутри!
// Если же значение меньше 360, мы снаружи полигона.
// Чтобы лучше понять, как это работает, возьмите карандаш и нарисуйте
// равносторонний треугольник. Нарисуйте точку в его центре. Теперь от этой точки проведите линии
// к каждой вершине треугольника. Таким образом у нас получилось 3 треугольника внутри главного, верно?
// Теперь. Мы знаем, что если сложим все углы треугольника, то получим 180, верно?
// Почти в точности это мы и делаем.
for (int i = 0; i < verticeCount; i++) // Проходим циклом по каждой вершине и складываем их углы
{
vA = Poly[i] - vIntersection; // Вычитаем точку пересечения из текущей вершины
// Вычитаем точку пересечения из следующей вершины:
vB = Poly[(i + 1) % verticeCount] - vIntersection;
// Находим угол между 2мя векторами и складываем их все
Angle += AngleBetweenVectors(vA, vB);
}
// Теперь имея сумму углов, нам нужно проверить, равны ли они 360. Так как мы используем
// Dot product, мы работаем в радианах, так что проверим, равны ли углы 2*PI. PI мы обьявили в 3dmath.h.
// Вы заметите, что мы используем MATH_FACTOR. Мы используем его из-за неточности в рассчетах
// с плавающей точкой. Обычно результат не будет ровно 2*PI, так что нужно учесть маленькую
// погрешность. Я использовал .9999, но вы можете изменить это на ту погрешность, которая вас
// устроит.
if(Angle >= (MATCH_FACTOR * (2.0 * PI)) ) // Если угол >= 2PI (360 градусов)
return true; // Точка находится внутри полигона
return false; // Иначе - снаружи
}
/////////////////////////////////////// ABSOLUTE """"""""""""""\*
/////
///// Новая функция: возвращает модуль переданного числа
/////
/////////////////////////////////////// ABSOLUTE """"""""""""""\*
float Absolute(float num)
{
// Если число меньше нуля, возвращаем его модуль.
// Это просто. Можно или умножить число на -1, или вычесть его из нуля.
if(num < 0)
return (0 - num);
// Вернём оригинальное число, т.к. оно итак полоэительно.
return num;
}
////////////////////////////// SPHERE POLYGON COLLISION """""""""\\*
/////
///// Новая функция: возвращает true если сфера пересекает переданный полигон.
/////
////////////////////////////// SPHERE POLYGON COLLISION """""""""\\*
bool SpherePolygonCollision(CVector3 vPolygon[],CVector3 &vCenter, int vertexCount, float radius)
{
// Для проверки пересечения мы будем вызывать только эту функцию. Остальные - только
// вспомогательные функции, вызываемые из неё. Теория немного сложна, но
// я постараюсь обьяснить всё как можно более доступно. Поехали!
// Мы пройдем следующие шаги:
//
// 1) Сначала нужно проверить, пересекается ли сфера с плоскостью, на которой находится
// полигон. Помните, что плоскости бесконечны, и сфера может быть хоть в пятистах
// единицах от полигона, если сфера пересекает его плоскость - триггер сработает.
// Нам нужно написать функцию, возвращающую положение сферы: либо она полностью
// с одной стороны плоскости, либо с другой, либо пересекает плоскость.
// Для этого мы создали функцию ClassifySphere(), которая возвращает BEHIND, FRONT
// или INTERSECTS. Если она вернёт INTERSECTS, переходим ко второму шагу, иначе - мы
// не пересекаем плоскость полигона.
//
// 2) Второй шаг - получить точку пересечения. Это одна из хитрых частей. Мы знаем,
// что имея точку пересечения с плоскостью, нужно просто вызвать функцию InsidePolygon(),
// чтобы увидеть, находится ли эта точка внутри полигона, точно так же, как мы делали
// в уроке "Коллизия линии и полигона". Итак, как получить точку пересечения? Это
// не так просто, как кажется. Поскольку на сфере может распологатся бесконечное
// число точек, могут быть миллионы точек пересечения. Мы попробуем немного другой путь.
// Мы знаем, что можем найти нормаль полигона, что скажет нам направление, куда
// он "смотрит". ClassifyPoly() кроме всего прочего вернёт дистанцию от центра сферы до
// плоскости. И если мы умножим нормаль на эту дистанцию, то получим некое смещение.
// Это смещение может затем быть вычтено из центра сферы. Хотите верьте, хотите нет,
// но теперь у нас есть точка на плоскости в направлении плоскости. Обычно эта точка
// пересечения работает хорошо, но если мы пересечем ребра полигона, она не сработает.
// То, что мы только что сделали, называется "проекция центра сферы на плоскость".
// Другой путь - "выстрелить" луч от центра сферы в направлении, противоположном
// нормали плоскости, тогда мы найдем точку пересечения линии (этого луча) и плоскости.
// Мой способ занимает 3 умножения и одно вычитание. Выбирайте сами.
//
// 3) Имея нашу псевдо-точку пересечения, просто передаём её в InsidePolygon(),
// вместе с вершинами полигона и их числом. Функция вернёт true, если точка
// пересечения находится внутри полигона. Запомните, одно то, что функция
// вернёт false, не значит, что мы на этом остановимся! Если мы ещё не "пересеклись",
// переходим к шагу 4.
//
// 4) Если мы дошли досюда, значит, мы нашли точку пересечения, и она находится
// вне периметра полигона. Как так? Легко. Подумайте, если центр сферы находится
// вне треугольника, но есть пересечение - остаётся ещё её радиус. Последняя
// проверка нуждается в нахождении точка на каждом ребре полигона, которая
// ближе всего к центру сферы. У нас есть урок "ближайшая точка на линии", так что
// убедитесь, что вы его поняли, прежде, чем идти дальше. Если мы имеем дело
// с треугольником, нужно пройти три ребра и найти на них ближайшие точки к центру
// сферы. После этого рассчитываем дистанцию от этих точек до центра сферы. Если
// дистанция меньше, чем радиус, есть пересечение. Этот способ очень быстр.
// Вым не нужно рассчитывать всегда все три ребра, так как первая или вторая
// дистанция может быть меньше радиуса, и остальные рассчеты можно будет не производить.
//
// Это было вступление, *уфф!*. Надеюсь, вам ещё не хочется плакать от такого обилия
// теории, так как код на самом деле будет не слишком большим.
// 1) ШАГ ОДИН - Найдем положение сферы
// Сначала найдем нормаль полигона
CVector3 vNormal = Normal(vPolygon);
// Переменная для хранения дистанции от сферы
float distance = 0.0f;
// Здесь мы определяем, находится ли сфера спереди, сзади плоскости, или пересекает её.
// Передаём центр сферы, нормаль полигона, точку на плоскости (любую вершину), радиус
// сферы и пустой float для сохранения дистанции.
int classification = ClassifySphere(vCenter, vNormal, vPolygon[0], radius, distance);
// Если сфера пересекает плоскость полигона, нам нужно проверить, пересекает ли
// она сам полигон.
if(classification == INTERSECTS)
{
// 2) ШАГ ДВА - Находим псевдо точку пересечения.
// Теперь нужно спроецировать центр сфера на плоскость полигона, в направлении
// его номали. Это делается умножением нормали на расстояние от центра сферы
// до плоскости. Расстояние мы получили из ClassifySphere() только что.
// Если вы не понимаете суть проекции, представьте её примерно так:
// "я стартую из центра сферы и двигаюсь в направлении плоскости вдоль её нормали
// Когда я должен остановится? Тогда, когда моя дистанция от центра сферы станет
// равной дистанции от центра сферы до плоскости."
CVector3 vOffset = vNormal * distance;
// Получив смещение "offset", просто вычитаем его из центра сферы. "vPosition"
// теперь точка, лежащая на плоскости полигона. Внутри ли она полигона - это
// другой вопрос.
CVector3 vPosition = vCenter - vOffset;
// 3) ШАГ ТРИ - Проверим, находится ли точка пересечения внутри полигона
// Эта функция использовалась и в нашем предыдущем уроке. Если точка пересечения внутри
// полигона, ф-я вернёт true, иначе false.
if(InsidePolygon(vPosition, vPolygon, vertexCount))
return true; // Есть пересечение!
else // Иначе
{
// 4) ШАГ ЧЕТЫРЕ - Проверим, пересекает ли сфера рёбра треугольника
// Если мы дошли досюда, центр сферы находится вне треугольника.
// Если хоть одна часть сферы пересекает полигон, у нас есть пересечение.
// Нам нужно проверить расстояние от центра сферы до ближайшей точки на полигоне.
if(EdgeSphereCollision(vCenter, vPolygon, vertexCount, radius))
{
return true; // We collided! "And you doubted me..." - Sphere
}
}
}
// Если мы здесь, пересечения нет
return false;
}
/////////////////////////////////// DISTANCE """"""""""""\\*
/////
///// Возвращает дистанцию между двумя 3D точками
/////
/////////////////////////////////// DISTANCE """"""""""""\\*
float Distance(CVector3 vPoint1, CVector3 vPoint2)
{
// Это классическая формула из начального курса алгебры, возвращающая
// дистанцию между двумя точками. Так как это не 2D, а 3D, мы просто добавляем
// Z-измерение.
//
// Distance = sqrt( (P2.x - P1.x)^2 + (P2.y - P1.y)^2 + (P2.z - P1.z)^2 )
double distance = sqrt( (vPoint2.x - vPoint1.x) * (vPoint2.x - vPoint1.x) +
(vPoint2.y - vPoint1.y) * (vPoint2.y - vPoint1.y) +
(vPoint2.z - vPoint1.z) * (vPoint2.z - vPoint1.z) );
// Вернём дистанцию между двумя точками
return (float)distance;
}
////////////////////////////// CLOSET POINT ON LINE """""""""""\*
/////
///// Возвращает точку на линии vA_vB, которая ближе всего к точке vPoint
/////
////////////////////////////// CLOSET POINT ON LINE """""""""""\*
CVector3 ClosestPointOnLine(CVector3 vA, CVector3 vB, CVector3 vPoint)
{
// Эта функция принимает сегмент линии, от vA до vB, затем точку в пространстве,
// vPoint. Мы хотим найти ближайшую точку отрезка vA_vB к точке в пространстве.
// Или это будет одна из двух крайних точек линии, или точка где-то между
// vA и vB. В отношении определения пересечений это очень важная функция.
// Вот как это работает. Сначала это всё кажется немного запутанным, так что постарайтесь
// сосредоточится. Сначала нам нужно найти вектор от "vA" к точке в пространстве.
// Затем нужно нормализовать вектор от "vA" к "vB", так как нам не нужна его полная длинна,
// только направление. Запомните это, так как позже мы будем использовать скалярное
// произведение (dot product) при рассчетах. Итак, сейчас у нас есть 2 вектора, образующие
// угол воображаемого треугольника на плоскости (2 точки линии и точка пространства).
// Далее нам нужно найти величину (magnitude) сегмента линии. Это делается простой
// формулой дистанции. Затем вычисляем dot между "vVector2" и "vVector1". Используя
// это скалярное произведение, мы можем по существу спроэцировать vVector1 на нормализованный
// вектор сегмента линии, "vVector2". Если результат скалярного произведения равен нулю,
// это значит, что векторы были перпендикулярны и имели между собой угол в 90 градусов.
// 0 - это дистанция нового спроэцированного вектора от vVector2. Если результат -
// отрицательный, значит угол между двумя векторами более 90 градусов, что в свою очередь
// означает, что ближайшая точка - "vA", так как этот спроэцированный вектор находится
// снаружи линии. Если же результат - положительное число, спроэцированный вектор будет
// находится с правой стороны "vA", но возможно и справа от "vB". Чтобы это проверить,
// мы убедимся, что результат скалярного произведения НЕ больше дистанции "d". Если
// он больше, то ближайшая точка - "vB".
// Итак, мы можем найти ближайшую точку довольно просто, если это одна из крайних точек линии.
// Но как мы найдём точку между двумя краями линии? Это просто. Посколько у нас есть
// дистанция "t" от точки "vA" (полученная из скалярного произведения двух векторов),
// мы просто используем наш вектор направления сегмента линии, "vVector2", и умножим его
// на дистанцию "t". Это создаст вектор, идущий в направлении сегмента линии, с величиной
// (magnitude) спроецированного вектора, "vVector1", от точки "vA". Затем прибавляем
// этот вектор к "vA", что даст нам точку на линии, которая ближе всего к нашей точке
// пространства, "vPoint".
// Наверно, это всё очень сложно представить на основе комментариев, пока у вас
// нет хорошего понимания линейной алгебры.
// Создаём вектор от точки vA к точке пространства vPoint.
CVector3 vVector1 = vPoint - vA;
// Создаём нормализированный вектор направления от точки vA до vB.
CVector3 vVector2 = Normalize(vB - vA);
// Используем формулу дистанции, чтобы найти величину (magnitude) сегмента линии.
float d = Distance(vA, vB);
// Используя скалярное произведение, проэцируем vVector1 на vVector2.
// Это, по существу, даст нам расстояние от нашего спроецированного вектора до vA.
float t = Dot(vVector2, vVector1);
// Если наша спроецированная дистанция от vA, "t", меньше или равна нулю, ближайшая
// точка к vPoint - vA. Возвращаем эту точку.
if (t <= 0)
return vA;
// Если спроецированная дистанция от vA, "t", Больше или равна длинне сегмента линии,
// ближайшая точка на линии - vB. Вернём её.
if (t >= d)
return vB;
// Здесь мы создаём вектор с длинной t и направлением vVector2.
CVector3 vVector3 = vVector2 * t;
// Чтобы найти ближайшую точку на отрезке линии, просто прибавляем vVector3 к точке vA.
CVector3 vClosestPoint = vA + vVector3;
// Вернём ближайшую точку на линии
return vClosestPoint;
}
///////////////////////////////// CLASSIFY SPHERE """"""""""\\*
/////
///// Новая функция: вычисляет положение сферы относительно плоскости, а так же расстояние
/////
///////////////////////////////// CLASSIFY SPHERE """"""""""\\*
int ClassifySphere(CVector3 &vCenter,
CVector3 &vNormal, CVector3 &vPoint, float radius, float &distance)
{
// Сначала нужно найти расстояние плоскости от начала координат.
// Это нужно в дальнейшем для формулы дистанции.
float d = (float)PlaneDistance(vNormal, vPoint);
// Здесь мы используем знаменитую формулу дистанции, чтобы найти расстояние
// центра сферы от плоскости полигона.
// Напоминаю саму формулу: Ax + By + Cz + d = 0 with ABC = Normal, XYZ = Point
distance = (vNormal.x * vCenter.x + vNormal.y * vCenter.y + vNormal.z * vCenter.z + d);
// Теперь используем только что найденную информацию. Вот как работает коллизия
// сферы и плоскости. Если расстояние от центра до плоскости меньше, чем радиус
// сферы, мы знаем, что пересекли сферу. Берём модуль дистанции, так как если
// сфера находится за плоскостью, дистанция получится отрицательной.
// Если модуль дистанции меньше радиуса, сфера пересекает плоскость.
if(Absolute(distance) < radius)
return INTERSECTS;
// Если дистанция больше или равна радиусу, сфера находится перед плоскостью.
else if(distance >= radius)
return FRONT;
// Если и не спереди, и не пересекает - то сзади
return BEHIND;
}
///////////////////////////////// EDGE SPHERE COLLSIION """"""""""\\*
/////
///// Новая ф-я: определяет, пересекает ли сфера какое-либо ребро треугольника
/////
///////////////////////////////// EDGE SPHERE COLLSIION """"""""""\\*
bool EdgeSphereCollision(CVector3 &vCenter,
CVector3 vPolygon[], int vertexCount, float radius)
{
CVector3 vPoint;
// Эта ф-я принимает центр сферы, вершины полигона, их чичло и радиус сферы. Мы вернём
// true, если сфера пересекается с каким-либо ребром.
// Проходим по всем вершинам
for(int i = 0; i < vertexCount; i++)
{
// Это вернёт ближайшую к центру сферы точку текущего ребра.
vPoint = ClosestPointOnLine(vPolygon[i], vPolygon[(i + 1) % vertexCount], vCenter);
// Теперь нужно вычислить расстояние между ближайшей точкой и центром сферы
float distance = Distance(vPoint, vCenter);
// Если расстояние меньше радиуса, должно быть пересечение
if(distance < radius)
return true;
}
// Иначе пересечения не было
return false;
}