Что такое коллизия и как проверять столкновения объектов?

[Segaman]

Народ, разъясните пож., что такое коллизия и как вообще можно проверять столкновеня обьектов?

[r57shell]

омг, нуб детектед.
Коллизия есть пересечение.
Обычно пересечение и есть столкновение.
Термин коллизия используют в:
1) Играх когда говорят о столкновениях
2) В криптографии когда например говорят о хэшах.
3) В интернете коллизии возникают когда одновременно пытаются в обоих направлениях передать данные...
4) другое...
А теперь: "как вообще можно проверять столкновения объектов?"
Collision Detection тебе поможет (спасиба кэп)
Задача найти пересечение двух объектов сводится к примитивным задачам, типа
1) пересечь прямую с прямой/отрезком
2) пересечь треугольник с прямой/отрезком
3) пересечь треугольник с точкой (ужасно сложно  )
4) пересечь треугольник с треугольником.
Используемые при потребности максимальных точностей
5) прямая с окружностью
6) окружность с окружностью
7) окружность с треугольником
8) чего в голову взбредёт.
короче другими словами, считаешь какие есть у тебя объекты, а потом уже эти фишки реализовываешь.
После чего остаётся заюзать какое-нибудь пространственное дерево, чтобы ускорить нахождение пересечений, и всё.
Ито они не всегда нужны.

[Mr2]

А как быть с 3D объектами? Каждый полигон сканировать на пересечение с чем либо?

[r57shell]

нуб 2 детектед.
А треугольники бывают только 2D?) А полигон, не объединение треугольников?)
Ответ: да сканировать, не все конечно... но именно пересечение с треугольниками. Если конечно у тебя объект из треугольников.
"не все конечно" - для этого и есть "пространственное дерево". За такое название не пинать, просто их дофига, BSP, AABB... а как их вместе называют не знаю.
Поидее BSP = Binary Space Partitioning - бинарное разделение пространства. Может "деревья разделения пространства"?))) слишком много букаф.

Добавлено позже:
Вместо "BSP-подобных текник", если очень лень, можно использовать только Bound-Box'ы.

[Mr2]

Ответ: да сканировать, не все конечно...

А какие сканировать. Допустим катится у меня шарик и надо зафиксировать столкновение со стеной?Придётся сканировать все полигоны шарика?

[r57shell]

Ну вопервых раз у тебя шарик, то умные люди сразу проверяют пересечение шарика с чем-то.
А так, да... если у тебя отвёртка катится, то какие-то её треугольники проверять...
Яже вроде уже писал. фигли снова спрашивать. Если не укладывается в твои представления, то это не означает, что делают не так. Погугли Collision Detection и BSP-tree, AABB.
Я не собираюсь подробно описывать то, что уже всеми подробно описано .

Добавлено позже:
например:
http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%B0
http://www.gamedev.ru/articles/?id=30128

[Mr2]

фигли снова спрашивать.

Не удержался.

Мне ещё до колизий далеко, я так и непонял как линии рисовать. Там какие то формулы(Алгоритм Брезенхэма) ядрёные.... Рисовать то рисует, а как и почему не понял .Вобщем спасибо за внимание.

[AjaxVS]

да никто никогда треугольники не сравнивает. это нереально по производительности.
сравниваются ограничивающие объемы. обычно рассчитывают прямоугольный параллелепипед, в который помещается вся модель, проверяется пересечение такого кубика со всеми остальными, которые рядом находятся. потом, если надо, проверяется пересечение с другими, более мелкими кубиками, в которые помещаются части моделей (рука, голова, etc). алгоритмы легко ищутся, как подсказал r57shell.

Там какие то формулы(Алгоритм Брезенхэма) ядрёные

а ты думал, мы тут пестики в тычинки пихаем? копай, учись.. если хочешь.

[Mr2]

да никто никогда треугольники не сравнивает. это нереально по производительности.

То то я и думаю:"Где то тут подвох". 
Пока весь шар просканируешь, стены рухнут.

а ты думал, мы тут пестики в тычинки пихаем? копай, учись.. если хочешь.

Низнаю что вы там втыкаете, я точно не втыкаю.

копай, учись.. если хочешь.

"Пилите, пилите Шура - они золотые"...

[r57shell]

да никто никогда треугольники не сравнивает. это нереально по производительности.

Нуб 3 детектед.
Не вешай людям на уши...
Примеры:
1) попадание пуль в Counter Strike/Call of Duty .... короче в FPS играх. (заметь, точки от пуль остаются в точном их попадании...)
2) Выделения объектов тоже бывают такими, пример сходу не скажу.
3) В нормальной физике типа Half-Life 2 без этого не обойтись (например гравипушкой когда играешься, предмет может зацепится любой вершиной...)
4) ходьба по поверхностям. в FPS играх.
5) если подумать можно ещё тонны перечислить.
Не спорю что бывает прибигают к апроксимации моделей для физики. (строится дополнительный мэш, представляющий упрошенную модель, для физики).
На счёт скорости - достигается логарифмичная сложность.
На примере логарифм от 1000000 = 20.

[Mr2]

1) попадание пуль в Counter Strike/Call of Duty .... короче в FPS играх. (заметь, точки от пуль остаются в точном их попадании...)

Ты видел исходники Counter Strike/Call of Duty/Half-Life 2?

[pedro]

Ты видел исходники Counter Strike/Call of Duty/Half-Life 2?

со стима скачать можно-)

[r57shell]

Mr2, нет. Ещё туда добавь Quake3.

[AjaxVS]

1) ... точки от пуль остаются в точном их попадании

пересечение луча с OOBB.
вот у меня даже функция есть:

DWORD CajGamePhys::CheckCrossLine(DWORD wOI, bool isBullet, D3DXVECTOR3 * vRayStart,D3DXVECTOR3 * vRayEnd, D3DXVECTOR3 * vHit = NULL, DWORD iIgnoreET = 0, DWORD iIgnoreWOI = 0, DWORD iStart = 0) {
...
}

угадай, что возвращает вектор vHit.
пересечение с треугольниками не используется.

2) Выделения объектов тоже бывают такими, пример сходу не скажу.

получение проекции и выборка из дерева.
пересечение с треугольниками не используется.

3) В нормальной физике типа Half-Life 2 без этого не обойтись (например гравипушкой когда играешься, предмет может зацепится любой вершиной...)

про Half-Life2 ничего не знаю, догадываться не буду.

4) ходьба по поверхностям. в FPS играх.

хейтмапы.
пересечение с треугольниками не используется.

Не спорю что бывает прибигают к апроксимации моделей для физики. (строится дополнительный мэш, представляющий упрошенную модель, для физики).

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

продолжай троллить нас дальше, дорогой товарищ
я, правда, в топик заходить больше не буду - мне с вами все ясно.

зы. чтобы не быть голословным - пример с ландшафтом:

никаких пересечений с треугольниками.

[Mr2]

Mr2, нет.

NOOB №1 детектед!
Ты слышал какое Г играет биталз? 

[r57shell]

пересечение луча с OOBB.

Видимо у вас объекты box-овидного вида. в сферу стрельни таким методом.

получение проекции и выборка из дерева.

Тут нет конкретики, так-что не могу спорить.

хейтмапы.

Как давно ты видел игры в которых всего один этаж?

причем здесь прогрессивные меши?

Да так, за красивое название.

продолжай троллить нас дальше, дорогой товарищ

продолжай оставаться нубом.

я, правда, в топик заходить больше не буду - мне с вами все ясно.

Это твой выбор.

зы. чтобы не быть голословным - пример с ландшафтом:

Одноэтажный ландшафт.
Как ты припухнешь на картах типа Half-Life где этажи
1) не на одном уровне.
2) их дофига.
а ещё круче пример Painkiller

никаких пересечений с треугольниками.

"Полностью с вами согласен."

Добавлено позже:
http://www.devmaster.net/articles/bsp-trees-physics/
картинки Figure 10, 11 и прочие, так, для извращенцев просто да?)
И код написан тоже just for lulz.

[Segaman]

Мне над самое простое. Это проверять столкновения объектов перед их движением. т.е. перед тем как переместится, проверять столкновение с одним или там другим обьектом. Тупо квадраты проверять разных размеров. Так вот объясните на пальцах все мои действия. Буду крайне благодарен. Ато доки панимать не выходит. Слишком нудно. И я не нуб. Сам такой. Я б не стал спрашивать, не будь такой нужды. А я игру начал писать, а таких встроеных, как в гм, функций в сеге нед. Просто обьясни, если знаешь, понятным языком. Ато чот моск мой не хочет додумывать.

[r57shell]

Ато чот моск мой не хочет додумывать.

Не хочет значит не надо.

[Segaman]

Спасибо, большое. Очень помог, сам бы долго моск бы ломал. Ато в армии не всегда моск пашет на всю катушку. Не знаю даж. Как отблагодарить.