Нарисуйте сферу с использованием 3D пикселей (вокселей)

Question

Можете ли вы предложить алгоритм, который может нарисовать сферу в трехмерном пространстве, используя только основные plot(x,y,z) примитив (что бы нарисовать один воксель)?

Я надеялся на что-то похожее на алгоритм круга Брезенхэма, но на 3D вместо 2D.

К вашему сведению, я работаю над аппаратным проектом, который представляет собой 3D-дисплей с низким разрешением, использующий 3-мерную матрицу светодиодов, поэтому мне нужно на самом деле нарисовать сферу, а не просто 2D-проекцию (т.е. круг).

Проект очень похож на этот:

... или увидеть это в действии здесь.

Я имею в виду одну возможность:

• рассчитать координаты Y полюсов (с учетом радиуса) (для сферы с центром в начале координат, они будут -r а также +r)
• разрезать сферу: для каждой горизонтальной плоскости p_i между этими координатами вычислите радиус окружности, полученный пересечением указанной плоскости со сферой => r_я
• нарисовать фактический круг радиуса r_я в самолете p_Я использовал алгоритм Брезенхэма.

Кстати, я использую микропроцессор.NET, поэтому программирование на C#, но мне не нужны ответы на C#.

Answer 1

Простой метод грубой силы состоит в том, чтобы перебрать каждый воксел в сетке и вычислить его расстояние от центра сферы. Затем раскрасьте воксель, если его расстояние меньше радиуса сферы. Вы можете сохранить много инструкций, убрав квадратный корень и сравнив произведение точек с квадратом радиуса.

Довольно далеко от оптимального, конечно. Но на сетке 8x8x8, как показано, вам нужно будет выполнить эту операцию 512 раз на сферу. Если центр сферы находится на сетке, а его радиус является целым числом, вам нужна только целочисленная математика. Точечный продукт - 3 умножения и 2 сложения. Умножения медленные; скажем, они принимают 4 инструкции каждый. Плюс тебе нужно сравнение. Добавьте в загрузки и магазины, скажем, это стоит 20 инструкций за воксель. Это 10240 инструкций на сферу.

Arduino, работающий на частоте 16 МГц, может выдавать 1562 шара в секунду. Если вы не выполняете кучу других математических операций и операций ввода-вывода, этот алгоритм должен быть достаточно хорошим.

Answer 2

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

Я думаю, что на основе комментария и ответа @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 будет иметь согласованное время независимо от радиуса, в то время как этот метод будет замедляться при рисовании сфер большого радиуса, где будет только часть отображается. Однако по мере увеличения разрешающей способности дисплейного куба время выполнения этого алгоритма будет оставаться неизменным, в то время как грубая сила будет увеличиваться.

Answer 3

Предполагая, что у вас уже есть функция сюжета, как вы сказали:

    public static void DrawSphere(double r, int lats, int longs)
    {
        int i, j;
        for (i = 0; i <= lats; i++)
        {
            double lat0 = Math.PI * (-0.5 + (double)(i - 1) / lats);
            double z0 = Math.Sin(lat0) * r;
            double zr0 = Math.Cos(lat0) * r;

            double lat1 = Math.PI * (-0.5 + (double)i / lats);
            double z1 = Math.Sin(lat1) * r;
            double zr1 = Math.Cos(lat1) * r;

            for (j = 0; j <= longs; j++)
            {
                double lng = 2 * Math.PI * (double)(j - 1) / longs;
                double x = Math.Cos(lng);
                double y = Math.Sin(lng);

                plot(x * zr0, y * zr0, z0);
                plot(x * zr1, y * zr1, z1);
            }
        }
    }

Эта функция должна построить сферу в начале координат с указанным разрешением по широте и долготе (судя по вашему кубу, вы, вероятно, захотите что-то около 40 или 50 в качестве приблизительного предположения). Этот алгоритм не "заполняет" сферу, хотя, поэтому он будет обеспечивать только контур, но игра с радиусом должна позволить вам заполнить внутреннюю часть, вероятно, с уменьшением разрешения по широтам и долготе на этом пути.

Answer 4

Только что нашел старые вопросы о генерации Sphere Mesh, но верхний ответ на самом деле дает вам небольшой кусок псевдокода для генерации ваших X, Y и Z:

(x, y, z) = (sin(Pi * m/M) cos(2Pi * n/N), sin(Pi * m/M) sin(2Pi * n/N), cos(Pi * m/M))

Проверьте это Q&A для деталей:) процедурно сгенерируйте сферу меш

Answer 5

Мое решение использует математику с плавающей запятой вместо целочисленной математики, что не идеально, но работает.

      private static void DrawSphere(float radius, int posX, int poxY, int posZ)
{
    // determines how far apart the pixels are
    float density = 1;

    for (float i = 0; i < 90; i += density)
    {
        float x1 = radius * Math.Cos(i * Math.PI / 180);
        float y1 = radius * Math.Sin(i * Math.PI / 180);

        for (float j = 0; j < 45; j += density)
        {
            float x2 = x1 * Math.Cos(j * Math.PI / 180);
            float y2 = x1 * Math.Sin(j * Math.PI / 180);
            
            int x = (int)Math.Round(x2) + posX;
            int y = (int)Math.Round(y1) + posY;
            int z = (int)Math.Round(y2) + posZ;

            DrawPixel(x, y, z);
            DrawPixel(x, y, -z);
            DrawPixel(-x, y, z);
            DrawPixel(-x, y, -z);

            DrawPixel(z, y, x);
            DrawPixel(z, y, -x);
            DrawPixel(-z, y, x);
            DrawPixel(-z, y, -x);

            DrawPixel(x, -y, z);
            DrawPixel(x, -y, -z);
            DrawPixel(-x, -y, z);
            DrawPixel(-x, -y, -z);

            DrawPixel(z, -y, x);
            DrawPixel(z, -y, -x);
            DrawPixel(-z, -y, x);
            DrawPixel(-z, -y, -x);
        }
    }
}