Хабрахабр: Коллективные / Блоги / Захабренные Голосов: 10 Адрес блога: http://habrahabr.ru/blog/ Добавлен: 2007-10-24 18:05:40 блограйдером Robin_Bad

Алгоритмы / Быстрое вычисление точной 3D карты расстояний с использованием технологии CUDA

2011-05-19 15:41:52 (читать в оригинале)

Карта расстояний (Distance Map) — это объект, позволяющий быстро получить расстояние от заданной точки до определенной поверхности. Обычно представляет собой матрицу значений расстояний для узлов с фиксированным шагом. Часто используется в играх для определения «попадания» в игрока или предмет, и для оптимизационных задач по совмещению объектов: расположить объекты максимально близко друг к другу, но так, чтобы они не пересекались. В первом случае качество карты расстояний (то есть точность значений в узлах) не играет большой роли. Во втором — от нее могут зависеть жизни (в ряде приложений, связанных с нейрохирургией). В этой статье я расскажу как можно достаточно точно обсчитать карту расстояний за разумное время.