быстрое пересечение сферы и сетки

Question

учитывая трехмерную сетку, 3d точку в качестве центра сферы и радиус, я хотел бы быстро вычислить все ячейки, содержащиеся или пересекаемые сферой.

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

было бы замечательно, если бы было что-то более эффективное

спасибо!

Answer 1

Существует версия алгоритма Брезенхема для рисования кругов. Рассмотрим двумерное место в точке z = 0 (предположим, что сфера сейчас находится на уровне 0,0,0), и рассмотрим только плоскость x-y точек сетки. Начиная с x = R, y = 0, следуйте алгоритму Брезенхема до y = y_R, x = 0, за исключением того, что вместо рисования вы просто используете результат, чтобы знать, что все точки сетки с нижними координатами x находятся внутри круга, вниз в х = х_центр. Поместите их в список, сосчитайте их или запишите. Когда закончите с двумерной задачей, повторите с изменением z и используя уменьшенный радиус R (z) = sqrt (R ^ 2-z ^ 2) вместо R, пока z = R.

Если центр сферы действительно расположен в точке сетки, вы знаете, что каждая точка сетки внутри или снаружи правой половины сферы имеет зеркального партнера с левой стороны, а также сверху / снизу, так что вы можете сделать половину подсчет / листинг по измерению. Вы также можете сэкономить время, выполняя Bresenham только до линии 45 градусов, потому что любая точка x, y относительно центра имеет партнера y, x. Если сфера может быть где-либо, вам придется вычислять результаты для каждого октанта.

Answer 2

Независимо от того, насколько эффективно вы рассчитываете отдельную ячейку, находящуюся внутри или вне сферы, ваш алгоритм всегда будет иметь значение O (радиус ^ 3), потому что вы должны отметить это количество ячеек. Предложение DarenW относительно алгоритма окружности в средней точке (он же Брезенхем) может дать постоянное ускорение коэффициента, так же как и простая проверка пересечения с использованием квадрата радиуса, чтобы избежать вызова sqrt ().

Если вы хотите получить производительность лучше, чем O (r ^ 3), тогда вы можете использовать octree вместо плоской сетки. Каждый узел дерева может быть помечен как полностью внутри, полностью снаружи или частично внутри сферы. Для частично внутри узлов вы перемещаетесь вниз по дереву, пока не доберетесь до мелкозернистых клеток. Это по-прежнему требует пометки O (r ^ 2 log r) узлов [O (r ^ 2) узлов на границе, O (log r) проходит по дереву, чтобы добраться до каждого из них], поэтому это может не стоить проблема в вашем приложении.