Я не верю, что выполнение алгоритма окружности средней точки на каждом слое даст желаемые результаты, как только вы достигнете полюсов, поскольку у вас будут зазоры на поверхности, где светодиоды не горят. Это может дать желаемый результат, так что это будет зависеть от эстетики. Этот пост основан на использовании алгоритма круга средней точки для определения радиуса слоев через два средних вертикальных октанта, а затем при рисовании каждого из этих кругов также устанавливаются точки для полярных октантов.
Я думаю, что на основании комментария и ответа @Nick Udall здесь использование алгоритма окружности для определения радиуса вашего горизонтального среза будет работать с модификацией, которую я предложил в комментарии к его ответу. Алгоритм окружности должен быть модифицирован, чтобы принимать в качестве входных данных начальную ошибку, а также рисовать дополнительные точки для полярных октантов.
- Нарисуйте стандартные точки алгоритма окружности в
y0 + y1 и y0 - y1: x0 +/- x, z0 +/- z, y0 +/- y1, x0 +/- z, z0 +/- x, y0 +/- y1, всего 16 баллов. Это составляет основную часть вертикали сферы.
- Дополнительно нарисуйте точки
x0 +/- y1, z0 +/- x, y0 +/- z и x0 +/- x, z0 +/- y1, y0 +/- z, всего 16 точек, которые сформируют полярные шапки для сферы.
Путем передачи ошибки внешнего алгоритма в алгоритм окружности, это позволит под-воксельной настройке круга каждого слоя. Не передавая ошибку во внутренний алгоритм, экватор круга будет приближен к цилиндру, и каждая приближенная грань сферы по осям x, y и z будет образовывать квадрат. С учетом ошибки каждая грань с достаточно большим радиусом будет аппроксимирована в виде закрашенного круга.
Следующий код изменен из алгоритма окружности средней точки Википедии . Алгоритм DrawCircle имеет измененную номенклатуру для работы в плоскости xz, добавления третьей начальной точки y0, смещения по y y1 и начальной ошибки error0. DrawSphere был изменен из той же функции, чтобы взять третью начальную точку y0 и вызывает DrawCircle вместо DrawPixel
public static void DrawCircle(int x0, int y0, int z0, int y1, int radius, int error0)
{
int x = radius, z = 0;
int radiusError = error0; // Initial error state passed in, NOT 1-x
while(x >= z)
{
// draw the 32 points here.
z++;
if(radiusError<0)
{
radiusError+=2*z+1;
}
else
{
x--;
radiusError+=2*(z-x+1);
}
}
}
public static void DrawSphere(int x0, int y0, int z0, int radius)
{
int x = radius, y = 0;
int radiusError = 1-x;
while(x >= y)
{
// pass in base point (x0,y0,z0), this algorithm's y as y1,
// this algorithm's x as the radius, and pass along radius error.
DrawCircle(x0, y0, z0, y, x, radiusError);
y++;
if(radiusError<0)
{
radiusError+=2*y+1;
}
else
{
x--;
radiusError+=2*(y-x+1);
}
}
}
Для сферы радиуса 4 (которая на самом деле требует 9x9x9), это будет запускать три итерации процедуры DrawCircle, при этом первый рисует типичный круг радиуса 4 (три шага), а второй рисует круг радиуса 4 с начальная ошибка 0 (также три шага), а затем третий рисунок окружности радиуса 3 с начальной ошибкой 0 (также три шага). В итоге получается девять вычисленных точек, каждая из которых рисует 32 пикселя.
Это составляет 32 (точки на окружность) x 3 (операции сложения или вычитания на точку) + 6 (операции сложения, вычитания, сдвига на одну итерацию) = 102 операции сложения, вычитания или смещения на вычисленную точку. В этом примере это 3 балла за каждый круг = 306 операций на слой. Алгоритм радиуса также добавляет 6 операций на слой и повторяет 3 раза, поэтому 306 + 6 * 3 = 936 базовые арифметические операции для примера радиуса 4.
Здесь стоит заплатить несколько пикселей без дополнительных проверок условий (т. Е. X = 0, y = 0 или z = 0), поэтому, если ваш ввод / вывод медленный, вам лучше добавить проверки условий. Предполагая, что все светодиоды были очищены при запуске, пример круга установит 288 светодиодов, тогда как на самом деле будет гораздо меньше светодиодов, которые фактически загорятся из-за повторяющихся наборов.
Похоже, что это будет работать лучше, чем метод bruteforce для всех сфер, которые будут помещаться в сетку 8x8x8, но метод bruteforce будет иметь согласованное время независимо от радиуса, в то время как этот метод будет замедляться при рисовании сфер большого радиуса, где только часть будет отображаться. Однако при увеличении разрешения у экрана дисплея время выполнения алгоритма будет оставаться неизменным, в то время как перебор будет увеличиваться.