Как я могу проверить столкновение между двумя точками? (С++)

По сути, программа, которую я делаю, позволит пользователю импортировать 3D-модель (как fbx или obj). Затем он будет отображаться в окне с помощью openGL, после чего пользователь сможет размещать точки на модели.

Итак, моя проблема в том, как я могу проверить коллизии между этими двумя точками. Поэтому, если прямая линия рисуется из одной точки в другую, если она вообще попадает в 3D-модель, она может, например, вернуть «истину». Если он вообще не проходит через модель, он возвращает false.

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


c++ points trace collision
person Wapted    schedule 04.07.2016    source источник
comment
О том, как лучше всего выполнять обнаружение столкновений между полигонами, написаны целые книги.   -  person Lightness Races in Orbit    schedule 04.07.2016
comment
Похоже, это больше похоже на математическую задачу, чем на программирование. ИМХО не по теме для stackoverflow. Попробовать другой обмен стеками?   -  person Ivan Rubinson    schedule 04.07.2016

Ответы (1)


arrow_upward
2
arrow_downward

Псевдокод:

function rayhitsmodel(model, pointA, pointB):

    max-distance <- distance-between(pointA, pointB)
    ray-source <- pointA
    ray-direction <- normalize-vector(pointB - pointA)

    for each triangle-index in model.triangle-indices:

        p1 <- model.points[triangle-index.point1]
        ... similarly for p2, p3

        triangle <- p1, p2, p3
        intersection <- intersect-with-triangle(ray-source, ray-direction, triangle)

        if intersection is not nothing
            and distance-between(intersection.point, ray-source) <= max-distance
                return true

    return false

Пересечение луч-треугольник: https://en.wikipedia.org/wiki/M%C3%B6ller%E2%80%93Trumbore_intersection_algorithm.

Может быть сильно оптимизирован, например. путем разделения модели на октодерево. Пересечение становится O (log n) вместо O (n). См. это для пересечений лучей и октодеревьев: алгоритмы пересечения лучей и октодеревьев.

person Community    schedule 04.07.2016