Учитывая трехмерное поле расстояния, которое содержит расстояние до точек в сетке (например, ESDF или TSDF ), я хочу эффективно проверить, содержит ли куб в произвольной ориентации точку.
Простой подход - выполнить трассировку лучей, чтобы определить, какие ячейки содержатся внутри куба, и проверить, имеет ли какая-либо из этих ячеек расстояние 0. Это решение неудовлетворительно, поскольку оно отбрасывает информацию о расстоянии и тесно связано с базовым ESDF посредством трассировки лучей. Кажется, что мы должны быть в состоянии решить эту проблему более широко, используя информацию о расстоянии и параметр разрешения.
Можно представить более сложный подход, который сначала проверяет расстояние от центра куба до точки - если значение достаточно велико, мы знаем, что куб пуст, или, если оно достаточно мало, мы знаем, что внутри куба есть точка. Если значение находится где-то посередине, мы можем рекурсивно проверить неоднозначные области. Поскольку функция расстояния дискретизирована, этот алгоритм должен в конечном итоге завершиться, если ведение бухгалтерии ведется правильно во время поиска.
Конечно, дьявол кроется в деталях, и поэтому я задаю этот вопрос. Какой самый эффективный способ определить, есть ли точка внутри куба? Если это классическая проблема, как она называется?