Метод грубой силы заключается в проверке каждого куба на вашей линии. Там какая-то нетривиальная геометрия задействована IIRC.
Ах. Погуглив «столкновение куба линии», оказалось немало хитов. Это выглядит довольно многообещающе.
http://www.devmaster.net/forums/archive/index.php/t-371.html
По сути, это выглядит так (я должен ошибиться):
Возьмите 8 вершин, которые составляют углы куба. Мы будем работать в четырехугольниках для его обработки.
Первая задача - отработать все 6 нормалей лица и сохранить их где-нибудь в массиве. Чтобы выработать нормальное, вы должны использовать перекрестное произведение двух векторов parralel на лицо. Исходя из этой нормы, вы можете использовать уравнение плоскости, чтобы убедиться, что конечная точка луча находится вне (результат> 0) всех плоскостей.
Хорошо, немного математики:
Четыре вершины (x, y, z), составляющие грань ABCD, используются для создания двух векторов.
Чтобы получить эти два вектора, достаточно просто указать B-A и C-A (что означает B.x - A.x, B.y - A.y и т. Д.)
У нас есть два параллельных вектора, A и B, я назову их для ясности
...
Это продолжается в том же духе и для еще нескольких абзацев.
Единственное, что вы можете сделать, чтобы немного ускорить процесс, - это определить, насколько близко куб находится к рассматриваемой линии. Еще математика, чтобы найти ближайшую точку на линии от заданной точки (центр куба).
http://www.gamedev.net/community/forums/topic.asp?topic_id=185204
Вам не нужно проходить все испытания поверхности, пока вы не узнаете, будут ли столкновения вообще.
Уловка быстрого обнаружения столкновений:
Расстояние между двумя точками в 2d: sqrt (x ^ 2 + y ^ 2). Основные.
Но если вы просто хотите узнать относительное расстояние между двумя вещами, вы можете пропустить SQRT.
if ((x1 ^ 2 + y1 ^ 2)> (x2 ^ 2 + y2 ^ 2)) {
// x1, y1 длиннее x2, y2.
}
Квадратные корни дороги, и их стоит избегать, особенно во внутренних циклах, таких как обнаружение столкновений.
Эй, вот мысль. Постройте плоскость, которая является продолжением вашей линии (скажем, прямой вертикали, у вас никогда не изменится ... что угодно). Возьмите скалярное произведение всех точек куба. Если все они находятся на одной или другой стороне (все положительные или все отрицательные), куб не «разрезается» плоскостью и поэтому не может пересекать линию.
Точечные продукты дешевы.
Теперь постройте другую плоскость, перпендикулярную первой, и снова получите ваши точечные произведения. Если ваш куб тоже разрезан этой второй плоскостью ... сырой, в этом случае все равно можно разрезать дважды и не быть на линии.
Первая и единственная плоскость должны быть перпендикулярны линии между центром куба и ближайшей точкой на линии (время перекрестного произведения). Если плоскость ТА разрезает куб (точечные произведения, которые являются положительными и отрицательными для вершин вашего куба), то куб пересекает линию.