Как эффективно нарисовать поверхность сферы в вокселях?

Question

У меня есть большая трехмерная сетка (с минимальным размером прямоугольника сетки 1x1x1 для простоты), и я хочу нарисовать только поверхность большого количества сфер с переменным радиусом в этой сетке.Однако я хочу устранить типичные проблемы растеризации отверстий и насыпей.

Я также не хочу использовать метод грубой силы (найти все пиксели в радиусе центра сферы, удалить неограниченные пиксели), так как яЯ создам миллионы этих сфер, и некоторые из них могут иметь очень большие радиусы. алгоритм Брезенхэма для кругов похож на то, что я хочу, но мне интересно, как я мог бы адаптировать это к форме сферы.

Кто-нибудь может помочь?

Answer 1

Хорошо, я думаю, у меня все получилось.Не уверен, что это самая эффективная версия.

По существу, поверхность сферы состоит из бесконечного набора окружностей с радиусом r, который увеличивается, а затем уменьшается при перемещении через ось, перпендикулярную плоскости, пересекающей эту плоскость.круг.Увеличение и уменьшение радиуса можно описать с помощью полукруга.

В дискретном пространстве мы можем эффективно моделировать поверхность сферы, рисуя набор окружностей с использованием алгоритма Брезенхема, где рассчитывается радиусиспользуя дополнительный круг Брезенхэма, радиус которого равен радиусу сфер.Этот радиус рассматривается как торчащий «из» круга в третьем измерении.

Другие круги строятся вокруг него, как если бы основной круг являлся рамкой для построения.

IЯ не совсем уверен, что все это так легко понять, поэтому, надеюсь, алгоритм может пролить немного больше света:

public static void bresenhamSphere(Vector3 centre, int radius)
    {
        List<Vector3> points = new List<Vector3>();
        foreach (Point coord in bresenhemCircle(new Point(0,0), radius)) //get the set of points for an initial bresenham circle centred at the origin (we'll add the coordinates later)
        {
            int z = coord.Y; //I think you should be able to pick which coord matches to Z and which matches to radius arbitrarily, but this was more intuitive
            int r = coord.X; //the radius for the new circles
            foreach(Point point in bresenhemCircle(new Point((int)(centre.X),(int)(centre.Y)), r)) //get the circle spans around the original circle, this will make the surface of the sphere - this time create them at the x and y coordinates of the centre point supplied in the parameters
            {
                points.Add(new Vector3(point.X, point.Y, (int)(centre.Z) + z)); //convert the 2D results into 3D points by adding in the z value and add to the list.
            }
        }
    }

Где BresenhamCircle (center, radius) возвращает координаты всех пикселей на окружностиокружности, образованной из предоставленного центра и радиуса.

Где BresenhamSemiCircle (center, radius) возвращает координаты всех пикселей на окружности полукруга, образованного из предоставленного центра и радиуса.

Еще одним улучшением было бы не добавлять начальные точки на новых кругах, поскольку мы уже получили их от первоначального пробега круга, но я не уверен, сколько бонуса в этом есть.