В SO, нашел следующий простой алгоритм для рисования заполненных кругов:
for(int y=-radius; y<=radius; y++)
for(int x=-radius; x<=radius; x++)
if(x*x+y*y <= radius*radius)
setpixel(origin.x+x, origin.y+y);
Есть ли одинаковый простой алгоритм для рисования заполненных эллипсов?
Упрощен, без double и без деления (но будьте осторожны с переполнением целых чисел):
for(int y=-height; y<=height; y++) {
for(int x=-width; x<=width; x++) {
if(x*x*height*height+y*y*width*width <= height*height*width*width)
setpixel(origin.x+x, origin.y+y);
}
}
Мы можем воспользоваться двумя фактами, чтобы оптимизировать это значительно:
Первый факт экономит три четверти работы (почти); второй факт значительно уменьшает количество тестов (мы проверяем только по краю эллипса, и даже там нам не нужно проверять каждую точку).
int hh = height * height;
int ww = width * width;
int hhww = hh * ww;
int x0 = width;
int dx = 0;
// do the horizontal diameter
for (int x = -width; x <= width; x++)
setpixel(origin.x + x, origin.y);
// now do both halves at the same time, away from the diameter
for (int y = 1; y <= height; y++)
{
int x1 = x0 - (dx - 1); // try slopes of dx - 1 or more
for ( ; x1 > 0; x1--)
if (x1*x1*hh + y*y*ww <= hhww)
break;
dx = x0 - x1; // current approximation of the slope
x0 = x1;
for (int x = -x0; x <= x0; x++)
{
setpixel(origin.x + x, origin.y - y);
setpixel(origin.x + x, origin.y + y);
}
}
Это работает, потому что каждая строка сканирования короче предыдущей, по крайней мере, столько же поскольку этот был короче, чем тот, который был до него. Из-за округления до целочисленных координат пикселей, что не совсем точно - линия может быть короче на один пиксель меньше этого.
Другими словами, начиная с самой длинной линии сканирования (горизонтальный диаметр), количество, на которое каждая строка короче предыдущей, обозначается dx в коде, уменьшается не более чем на один, остается неизменным, или увеличивается. Первый внутренний for находит точное количество, на которое текущая линия сканирования короче предыдущей, начиная с dx - 1 и вверх, пока мы не приземлимся внутри эллипса.
| x1 dx x0
|###### |<-->|
current scan line --> |########### |<>|previous dx
previous scan line --> |################ |
two scan lines ago --> |###################
|#####################
|######################
|######################
+------------------------
Чтобы сравнить количество тестов внутри эллипса, каждая звездочка - это одна пара координат, проверенная в наивной версии:
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
... и в улучшенной версии:
*
**
****
***
***
***
**
**
Заменить
x*x+y*y <= radius*radius
с
Axx*x*x + 2*Axy*x*y + Ayy*y*y < radius*radius
где у вас есть три константы: Axx, Axy, Ayy. Когда Axy = 0, эллипс будет иметь свои оси горизонтально и вертикально. Axx = Ayy = 1 создает круг. Чем больше Axx, тем меньше ширина. Похоже для Айи и высоты. Для произвольного эллипса, наклоненного под любым заданным углом, для определения констант требуется бит алгебры.
Математически Axx, Axy, Ayy - это "тензор", но, возможно, вы не хотите вникать в этот материал.
ОБНОВЛЕНИЕ - подробная математика. Я не думаю, что С.О. может сделать хорошую математику, как математика С.Е. так что это будет выглядеть грубо.
Вы хотите рисовать (или делать что угодно) с эллипсом по координатам x, y. Эллипс наклонен. Мы создаем альтернативную систему координат x ', y', совмещенную с эллипсом. Ясно, что точки на эллипсе удовлетворяют условию
(x'/a)^2 + (y'/b)^2 = 1
Рассматривая некоторые хорошо отобранные случайные точки, мы видим, что
x' = C*x + S*y
y' = -S*x + C*y
где S, C - sin (& theta;) и cos (& theta;), & theta; являющийся углом оси х 'w.r.t. ось х. Мы можем сократить это с помощью обозначений x= (x, y) и аналогичных для primed, а R a 2x2-матрица с C и S:
x '= R x
Эллипсовое уравнение можно записать
T (x ') A' ' x'= 1
где 'T' указывает на транспонирование и, понижая '^', чтобы не совать всех в глаза, так что "a2" действительно означает a ^ 2,
A '' =
1/a2 0
0 1/b2
Используя x '= R x, находим
T (R x) A '' R x= 1
T (x) T (R) A '' R x= 1
T (x) A x= 1
где A, то, что вам нужно знать, чтобы сделать ваш алгоритм линии развертки наклонного чертежа,
A = T (R) A '' R =
C2/a2+S2/b2 SC(1/a2-1/b2)
SC/(1/a2-1/b2) S2/a2 + C2/b2
Умножьте их на x и y в соответствии с T (x) A x, и у вас это получилось.
Эллипс (около начала координат) представляет собой круг, линейно растянутый вдоль осей x или y. Поэтому вы можете изменить свой цикл следующим образом:
for(int y=-height; y<=height; y++) {
for(int x=-width; x<=width; x++) {
double dx = (double)x / (double)width;
double dy = (double)y / (double)height;
if(dx*dx+dy*dy <= 1)
setpixel(origin.x+x, origin.y+y);
}
}
Вы можете видеть, что если width == height == radius, то это эквивалентно вашему коду для рисования круга.
Быстрый алгоритм типа Bresenham, предложенный этой , работает очень хорошо. Здесь реализация OpenGL, которую я написал для нее.
Основная предпосылка заключается в том, что вы строите кривую на одном квадранте, который мы можем отразить на остальных трех квадрантах. Эти вершины вычисляются с использованием функции ошибки, аналогичной тому, что вы используете в алгоритме окружности окружности для кругов. Документ, который я связал выше, имеет довольно отличное доказательство для уравнения, и алгоритм отходит до того, чтобы просто проверить, находится ли заданная вершина внутри эллипса или нет, просто подставив его значения в функцию ошибки. Алгоритм также отслеживает наклон касательной линии кривой, которую мы рисуем в первом квадранте, и увеличивает x или y в зависимости от значения наклона, что вносит дополнительный вклад в работу алгоритма. Вот изображение, которое показывает, что происходит:
Как для заполнения эллипса, как только мы знаем вершины в каждом квадранте (который по существу является зеркальным отражением по осям x и y), мы получаем 4 вершины для каждой вершины, которую мы вычисляем, - что достаточно для рисования квадранта (в OpenGL в любом случае). Как только мы рисуем квадратики для всех таких вершин, получаем заполненный эллипс. Реализация, которую я дал, использует VBO по соображениям производительности, но вам это не нужно.
Реализация также показывает вам, как достичь заполненного эллипса, используя треугольники и линии вместо рисования квадрациклов - четверо лучше всего, поскольку это примитив, и мы делаем только один квад для 4 вершин, а не один треугольник за вершину в реализации треугольника.