На этот вопрос нет единого ответа, но большие миры часто разбиваются на пространства, используя что-то вроде quadtree или kd-tree , что приводит к поиску ближайших соседей. ниже линейного времени (дробная мощность или в худшем случае O (N ^ (2/3)) для 3D-игры). Эти методы часто называют BSP для разделения двоичного пространства.
Что касается обнаружения столкновений, то с каждым объектом обычно связан ограничивающий объем сетка (набор многоугольников, образующих выпуклый корпус), связанный с ним. Эти очень упрощенные сетки (иногда просто куб) не рисуются, а используются для обнаружения столкновений. Самый элементарный метод - создать плоскость, перпендикулярную линии, соединяющей средние точки каждого объекта с плоскостью, пересекающей линию в средней точке линии. Если ограничивающий объем объекта имеет точки по обе стороны от этой плоскости, это столкновение (вам нужно проверить только один из двух ограничивающих объемов относительно плоскости). Другой метод - улучшенный алгоритм расстояния GJK . Если вы хотите, чтобы учебное пособие прошло, ознакомьтесь с уроком NeHe Productions 'OpenGL # 30 .
Кстати, ограничивающие тома могут также использоваться для других оптимизаций, таких как так называемые окклюзионные запросы . Это процесс определения того, какие объекты находятся за другими объектами (окклюдерами) и, следовательно, не требуют обработки / визуализации. Ограничивающие объемы также можно использовать для отбраковки усеченного конуса , который представляет собой процесс определения того, какие объекты находятся за пределами объема перспективного обзора (слишком близко, слишком далеко или за пределами угла вашего поля зрения) и поэтому не нужно отображать.
Как отметил Килотан, использование ограничивающего объема может генерировать ложные срабатывания при обнаружении окклюзии и просто не работает вообще для некоторых типов объектов, таких как тороиды (например, глядя через отверстие в пончике). Правильно закрывать объекты, подобные этим, - совсем другая нить на портале-отбраковке .