Рисование 3D сферы в C/C++
Я ищу алгоритм, который может нарисовать красивую трехмерную сферу с небольшим разрешением. Я нашел алгоритм круга Брезенхэма, но он для 2D-рисования. Мне просто нужны границы сфер (мне это не нужно заполнять). Я тоже погуглил для решения проблемы, но ничего не нашел. Эта статья не помогает (что такое алгоритм перебора?). Я не могу использовать библиотеки OpenGL, мне нужно ванильное решение C/C++. Заранее спасибо.
4 ответа
Если я правильно понял, вы хотите визуализировать все поверхностные Voxels ofphere
Грубая сила O(R^3), Если вы просто проецируете лучи из плоскости и вычислите 3-ю координату, то вы получите O(R^2) но чтобы убедиться, что вокселей не хватает, вы должны выполнить эту проекцию со всех трех плоскостей, которая все еще O(R^2)
Это выглядит так:
на светодиодном кубе 16x16x16 моделирование. Теперь алгоритм:
вычислить видимую ограничивающую рамку
не нужно рендерить все пространство рендеринга, только сферу, поэтому центр +/- радиус...
возьмите одну плоскость (например, XY)
Отливать лучи от всех
x,yуказывает на ограничивающую рамку, которая составляет всего 2 для циклов и вычислитьzкоординаты, где луч попадает через сферное уравнение:(x-x0)^2 + (y-y0)^2 + (z-z0)^2 = R^2так
z=z0 +/- sqrt(R^2 - (x-x0)^2 - (y-y0)^2)и сделать два вокселя.
int sqrt(int x)для ограниченного размера (например, LED Cube/Screen или Voxel space) это можно сделать через таблицу поиска LUT, чтобы ускорить процесс.сделать шаг № 2 для всех самолетов (
xy,yz,xz)
Код на C++ выглядит так:
//---------------------------------------------------------------------------
//--- LED cube class ver: 1.00 ----------------------------------------------
//---------------------------------------------------------------------------
#ifndef _LED_cube_h
#define _LED_cube_h
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
const int _LED_cube_size=16;
//---------------------------------------------------------------------------
class LED_cube
{
public:
int n,map[_LED_cube_size][_LED_cube_size][_LED_cube_size];
LED_cube() { n=_LED_cube_size; }
LED_cube(LED_cube& a) { *this=a; }
~LED_cube() { }
LED_cube* operator = (const LED_cube *a) { *this=*a; return this; }
//LED_cube* operator = (const LED_cube &a) { /*...copy...*/ return this; }
void cls(int col); // clear cube with col 0x00BBGGRR
void sphere(int x0,int y0,int z0,int r,int col); // draws sphere surface with col 0x00BBGGRR
void glDraw(); // render cube by OpenGL as 1x1x1 cube at 0,0,0
};
//---------------------------------------------------------------------------
void LED_cube::cls(int col)
{
int x,y,z;
for (x=0;x<n;x++)
for (y=0;y<n;y++)
for (z=0;z<n;z++)
map[x][y][z]=col;
}
//---------------------------------------------------------------------------
void LED_cube::sphere(int x0,int y0,int z0,int r,int col)
{
int x,y,z,xa,ya,za,xb,yb,zb,xr,yr,zr,xx,yy,zz,rr=r*r;
// bounding box
xa=x0-r; if (xa<0) xa=0; xb=x0+r; if (xb>n) xb=n;
ya=y0-r; if (ya<0) ya=0; yb=y0+r; if (yb>n) yb=n;
za=z0-r; if (za<0) za=0; zb=z0+r; if (zb>n) zb=n;
// project xy plane
for (x=xa,xr=x-x0,xx=xr*xr;x<xb;x++,xr++,xx=xr*xr)
for (y=ya,yr=y-y0,yy=yr*yr;y<yb;y++,yr++,yy=yr*yr)
{
zz=rr-xx-yy; if (zz<0) continue; zr=sqrt(zz);
z=z0-zr; if ((z>0)&&(z<n)) map[x][y][z]=col;
z=z0+zr; if ((z>0)&&(z<n)) map[x][y][z]=col;
}
// project xz plane
for (x=xa,xr=x-x0,xx=xr*xr;x<xb;x++,xr++,xx=xr*xr)
for (z=za,zr=z-z0,zz=zr*zr;z<zb;z++,zr++,zz=zr*zr)
{
yy=rr-xx-zz; if (yy<0) continue; yr=sqrt(yy);
y=y0-yr; if ((y>0)&&(y<n)) map[x][y][z]=col;
y=y0+yr; if ((y>0)&&(y<n)) map[x][y][z]=col;
}
// project yz plane
for (y=ya,yr=y-y0,yy=yr*yr;y<yb;y++,yr++,yy=yr*yr)
for (z=za,zr=z-z0,zz=zr*zr;z<zb;z++,zr++,zz=zr*zr)
{
xx=rr-zz-yy; if (xx<0) continue; xr=sqrt(xx);
x=x0-xr; if ((x>0)&&(x<n)) map[x][y][z]=col;
x=x0+xr; if ((x>0)&&(x<n)) map[x][y][z]=col;
}
}
//---------------------------------------------------------------------------
void LED_cube::glDraw()
{
#ifdef __gl_h_
int x,y,z;
float p[3],dp=1.0/float(n-1);
glEnable(GL_BLEND);
glBlendFunc(GL_ONE,GL_ONE);
glPointSize(2.0);
glBegin(GL_POINTS);
for (p[0]=-0.5,x=0;x<n;x++,p[0]+=dp)
for (p[1]=-0.5,y=0;y<n;y++,p[1]+=dp)
for (p[2]=-0.5,z=0;z<n;z++,p[2]+=dp)
{
glColor4ubv((BYTE*)(&map[x][y][z]));
glVertex3fv(p);
}
glEnd();
glDisable(GL_BLEND);
glPointSize(1.0);
#endif
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
использование класса:
LED_cube cube;
cube.cls(0x00202020); // clear space to dark gray color
int a=cube.n>>1; // just place sphere to middle and size almost the whole space
int r=a-3;
cube.sphere(a,a,a,r,0x00FFFFFF);
cube.glDraw(); // just for mine visualization you have to rewrite it to your rendering system
Если вы хотите использовать только C, то разложите класс на глобальные функции и переменные и переведите операторы C++ x++,--,+=,-=,*=,... в стиле C x=x+1,...
Судя по ссылке, похоже, что вас больше интересуют алгоритмы вокселей для сфер, а не графика как таковая; сказать что-то вроде этой страницы помогает. Вы не хотите мяч, но только поверхность.
Алгоритм окружности средней точки может использоваться для рисования трехмерных сфер вокселей: рассматривайте сферу как стек срезов, и каждый срез содержит окружность.
На практике вы используете два вложенных круга средней точки, внешний определяет радиус для внутреннего. (Хотя простой алгоритм рисования окружностей друг над другом, скорее всего, оставит дыры в вокселях, алгоритм окружности средней точки использует симметрии, и при правильной реализации такие дыры не должны возникать.)
Вы строите шесть колпачков в тандеме, словно вырезаете куб в сферу. Поскольку уклоны поверхности на каждой крышке всегда меньше 1, выход наружу на крышке будет максимально изменять каждую координату на 1, поэтому отверстия не могут возникнуть.
Проблема этого подхода заключается в сложности: каждая вычисляемая вами точка может затронуть до 48 ячеек вокселей. (В каждой кепке каждая точка рассчитывается в пределах октанта и, следовательно, влияет на восемь ячеек. Есть шесть кепок, и 6*8=48.)
Я предлагаю другой подход.
Уравнение для поверхности сферы r- радиуса с центром в x 0, y 0, z 0, имеет вид
(x - x 0) 2 + (y - y 0) 2 + (z - z 0) 2 = r 2
С помощью целочисленного координатора точки сетки редко оказываются точно на поверхности сферы, допускают диапазон значений:
RR MIN ≤ (x - x 0) 2 + (y - y 0) 2 + (z - z 0) 2 ≤ RR MAX
где RR MIN и RR MAX являются константами; в частности, минимальное и максимальное квадраты расстояния до центра сферы.
Я рекомендую использовать двойные координаты для общих случаев. Это позволяет вам выбрать, будет ли центр сферы центрироваться по координате (подразумевается нечетный диаметр) или центрироваться между двумя соседними кординатами (подразумевается четный диаметр).
Если у тебя есть SIZE × SIZE × SIZE сетка вокселей (свет, строительные блоки, что угодно), затем
int sphere_surface(const char x, const char y, const char z,
const char size, const int rrmin, const int rrmax)
{
const int center = size - (size & 1); /* Size rounded down to even integer */
const int dx = center - x - x,
dy = center - y - y,
dz = center - z - z; /* Doubled coordinates */
const int rr = dx*dx + dy*dy + dz*dz; /* Distance squared */
return (rrmin <= rr) && (rr <= rrmax);
}
возвращает 1, если точка (x, y, z) находится в области поверхности сферы, центрированной в кубе. (Технически, он возвращается, если расстояние от этой точки до центра size куб находится внутри sqrt(rrmin)/2 а также sqrt(rrmax)/2 включительно.)
"Правильные" значения rrmin а также rrmax сильно зависят от контекста. rrmax как правило, где-то рядом size*size (помните, функция использует двойные координаты), с rrmin несколько меньше.
Например, если у вас есть сетка 3×3×3, вы хотите, чтобы только шесть центральных ячеек на каждой грани выполняли условие; Вы можете сделать это с size=3, rrmin=1, rrmax=4:
Если у вас есть сетка 4×4×4, вы хотите, чтобы четыре центральные ячейки на каждой грани выполняли условие (таким образом, считается, что в общей сложности 24 из 64 ячеек находятся на поверхности сферы); Вы можете сделать это с size=4, rrmin=11, rrmax=11:
С сеткой 5×5×5 мы получаем интересные побочные эффекты вышеупомянутого алгоритма.
size=5, rrmin=8, rrmax=16 дает очень "угловую" сферу, почти куб, стоящий на углу:
size=5, rrmin=12, rrmax=20 дает мою любимую приблизительную сферу:
size=5, rrmin=16, rrmax=24 дает округленный куб (каждая грань размером 3 × 3):
Очевидно, используя rrmin=0 также включает в себя все внутренние ячейки, дающие шар, а не только поверхность сферы.
Чем больше размер сетки, тем больше вариантов каждой сферы размера вы можете представить.
Вышеприведенная функция особенно полезна на микроконтроллерах, потому что вы можете просто перебрать свою решетку, обновляя состояние в каждой точке, как вы пожелаете. Кроме того, большинство микроконтроллеров имеют ограниченный объем памяти, но имеют очень быстрые (одночасовые) инструкции сложения, вычитания и умножения. (Хотя умножение 16×16-бит с 32-битным результатом обычно требует двух или более инструкций.)
Типичный микроконтроллер не имеет возможности ПЗУ / флэш-памяти для хранения достаточно интересных шаблонов вокселей, и лишь немногие имеют возможность DMA с SD-карты через SPI (так что вы можете просто загрузить "кадры" воксельных шаблонов с карты microSD), но Функции, подобные приведенным выше, могут создавать интересные формы с небольшим количеством входов - и особенно входов, которые можно интерполировать.
Вышеупомянутая функция также может быть адаптирована для аппроксимирующего сглаживания (путем сравнения rr в rrmin а также rrmax), в случае, если ваши воксели не просто двоичные, а, например, светодиоды с ШИМ-управлением.
Так как визуализация вышеупомянутого, как правило, немного сложна, вот небольшой быстрый взлом, который я использовал для генерации вышеупомянутых изображений. Он выводит изображение SVG на стандартный вывод, а срезы ASCII - на стандартную ошибку, если дано size, rrmin, а также rrmax в качестве параметров командной строки.
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define BORDER 2
#define XC(x,y,z) ((x)*16 + (y)*12)
#define YC(x,y,z) ((x)*6 - (y)*8 - (z)*17)
static int xt = 0;
static int yt = 0;
static void fcube(FILE *out, const int x, const int y, const int z, const int fill)
{
const int xc = xt + XC(x,y,z);
const int yc = yt + YC(x,y,z);
fprintf(out, "<path d=\"M%d,%dl16,6,12,-8,0,-17,-16,-6,-12,8z\" fill=\"#%06x\" stroke=\"#000\" />\n", xc, yc, fill & 0xFFFFFF);
fprintf(out, "<path d=\"M%d,%dl16,6,12,-8m-12,8l0,17\" fill=\"none\" stroke=\"#000\" />\n", xc, yc-17);
}
static unsigned long rrmin = 0UL;
static unsigned long rrmax = 0UL;
static int center = 0;
static int surface(const int x, const int y, const int z)
{
/* Doubled coordinates: */
const long dx = 2*x - center,
dy = 2*y - center,
dz = 2*z - center;
const unsigned long rr = dx*dx + dy*dy + dz*dz;
return (rrmin <= rr) && (rr <= rrmax);
}
int main(int argc, char *argv[])
{
int width, height;
int size, x, y, z;
char dummy;
if (argc != 4 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s SIZE RRMIN RRMAX\n", argv[0]);
fprintf(stderr, "Where\n");
fprintf(stderr, " SIZE is the size of the voxel cube\n");
fprintf(stderr, " RRMIN is the minimum distance squared, and\n");
fprintf(stderr, " RRMAX is the maximum distance squared,\n");
fprintf(stderr, " using doubled coordinates.\n");
fprintf(stderr, "\n");
fprintf(stderr, "Examples:\n");
fprintf(stderr, " %s 3 1 4\n", argv[0]);
fprintf(stderr, " %s 4 11 11\n", argv[0]);
fprintf(stderr, " %s 5 8 16\n", argv[0]);
fprintf(stderr, " %s 5 12 20\n", argv[0]);
fprintf(stderr, " %s 5 16 24\n", argv[0]);
fprintf(stderr, "\n");
return EXIT_FAILURE;
}
if (sscanf(argv[1], " %d %c", &size, &dummy) != 1 || size < 3) {
fprintf(stderr, "%s: Invalid size.\n", argv[1]);
return EXIT_FAILURE;
}
if (sscanf(argv[2], " %lu %c", &rrmin, &dummy) != 1) {
fprintf(stderr, "%s: Invalid rrmin.\n", argv[2]);
return EXIT_FAILURE;
}
if (sscanf(argv[3], " %lu %c", &rrmax, &dummy) != 1 || rrmax < rrmin) {
fprintf(stderr, "%s: Invalid rrmax.\n", argv[3]);
return EXIT_FAILURE;
}
/* Calculate coordinate range. */
{ int xmin = XC(0,0,0);
int ymin = YC(0,0,0);
int xmax = XC(0,0,0);
int ymax = YC(0,0,0);
for (z = 0; z <= size; z++)
for (y = 0; y <= size; y++)
for (x = 0; x <= size; x++) {
const int xc = XC(x,y,z);
const int yc = YC(x,y,z);
if (xc < xmin) xmin = xc;
if (xc > xmax) xmax = xc;
if (yc < ymin) ymin = yc;
if (yc > ymax) ymax = yc;
}
xt = BORDER - xmin;
width = xmax - xmin + 2*BORDER;
yt = BORDER - ymin;
height = ymax - ymin + 2*BORDER;
}
center = size - 1;
/* SVG preamble. */
printf("<?xml version=\"1.0\"?>\n");
printf("<svg xmlns=\"http://www.w3.org/2000/svg\" viewBox=\"0 0 %d %d\">\n", width, height);
printf("<path d=\"M%d,%dL%d,%d,%d,%d,%d,%d,%d,%d,%d,%dz\" fill=\"#f7f7f7\" stroke=\"#666666\"/>\n",
xt+XC( 0, 0, 0), yt+YC( 0, 0, 0),
xt+XC(size, 0, 0), yt+YC(size, 0, 0),
xt+XC(size,size, 0), yt+YC(size,size, 0),
xt+XC(size,size,size), yt+YC(size,size,size),
xt+XC(0, size,size), yt+YC( 0,size,size),
xt+XC(0, 0,size), yt+YC( 0, 0,size));
printf("<path d=\"M%d,%dL%d,%d,%d,%dM%d,%dL%d,%d\" fill=\"none\" stroke=\"#666666\"/>\n",
xt+XC( 0, 0, 0), yt+YC( 0, 0, 0),
xt+XC( 0,size, 0), yt+YC( 0,size, 0),
xt+XC(size,size, 0), yt+YC(size,size, 0),
xt+XC( 0,size, 0), yt+YC( 0,size, 0),
xt+XC( 0,size,size), yt+YC( 0,size,size));
for (z = 0; z < size; z++)
for (y = size - 1; y >= 0; y--)
for (x = 0; x < size; x++)
if (surface(x,y,z))
fcube(stdout, x, y, z, 0x00CCFF);
printf("</svg>\n");
for (z=0; z < size; z++) {
for (y = 0; y < size; y++) {
for (x = 0; x < size; x++)
fputc(surface(x,y,z) ? 'X' : '.', stderr);
fputs(" ", stderr);
for (x = 0; x < size; x++)
fputc(surface(x,z,y) ? 'X' : '.', stderr);
fputs(" ", stderr);
for (x = 0; x < size; x++)
fputc(surface(y,z,x) ? 'X' : '.', stderr);
fputc('\n', stderr);
}
fputc('\n', stderr);
}
return EXIT_SUCCESS;
}
Я не удосужился изобразить результат; Вы можете довольно легко, например, выбрать разные цвета для каждого лица, возможно, добавить тени на фоновые плоскости и так далее.
Вышеуказанные изображения были созданы с помощью этой программы, а затем преобразованы в PNG с использованием GIMP, но я рекомендую использовать ваш браузер для локального просмотра сгенерированных файлов.
Вопросы?
Я не могу использовать библиотеки OpenGL, мне нужно ванильное решение C/C++.
Значит ли это, что нет графических библиотек вообще? В этом случае очень простой ответ: вы не делаете. Ни C, ни C++ не имеют собственных возможностей визуализации графики. вам нужно использовать внешнюю библиотеку и драйвер только для связи с кадровым буфером ОС и / или видеокартой.
Однако, что касается моего решения, не связанного с графикой, это зависит от:
Я нашел алгоритм круга Брезенхэма, но он для 2D-рисования. Мне просто нужны сферы границ.
Значит ли это, что вам буквально нужны границы сферы? Потому что в этом случае вы должны просто использовать алгоритм 2d рисования, который у вас уже есть, поскольку он дает вам границы прямо здесь и сейчас.
Если это означает, что вам нужны отдельные воксели сферы, это немного сложнее, и потребуется немного больше математики, и, возможно, в той степени, в которой программный рендерер просто столкнется с проблемой производительности, в зависимости от того, сколько вокселей и отдельных вершин имеет ваша сфера.
Я думаю, что вы пытаетесь получить то, что разработчики игр и физических движков называют "ограничивающей рамкой" или "коллизионной рамкой", которую иногда называют просто "хитбоксом". Все, что требуется, это нарисовать куб (обычно каркасный), который охватывает всю сферу и ничего более (Другими словами, вы просто рисуете куб с такой же шириной, высотой и глубиной, что и сфера, предполагая, что мы работаем с измерение XYZ).
Наиболее распространенная библиотека, используемая в этом поле, - openGL, и на этом слайде показано, как настроить библиотеку в вашей среде IDE. Загрузите файлы отсюда http://www.xmission.com/~nate/glut.html затем поместите их в эти пути. glut32.dll -> C:\Windows\System32 glut32.lib -> C:\Program Files\Microsoft Visual Studio .NET\Vc7\PlatformSDK\lib glut.h -> C:\Program Files\Microsoft Visual Studio .NET\ vc7\PlatformSDK\Include\ Г.Л.
opengl-superbible-4th это учебник удивительный один начать с нуля до продвинутого уровня