|
|
Опубликовано Дмитрий Литвинов в Вс, 04/03/2011 - 21:15
|
Задача : создание приложения, реализующего основные алгоритмы растеризации линии и окружности
Использованный API : .NET Framework 3.5
Язык : Visual C#
Среда разработки : MS Visual Studio 2008
Представленное приложение реализует некоторые растровые алгоритмы. Среди них алгоритмы Брезенхема и Ву. Также для сравнения представлены аналогичные графические примитивы, встроенные в платформу .NET. В программе ведется работа с двумя классами : класс Form1, наследующий класс Form и выводящий изображения на форму, и статический класс RasterAlgorithms, содержащий реализации алгоритмов в статических методах. Далее описаны реализованные алгоритмы.
1. Алгоритм Брезенхема для 4-связной линии.
public static void Bresenham4Line(Graphics g, Color clr, int x0, int y0, int x1, int y1)
Алгоритм основан на том, что для каждой точки растра существует ровно 4 соседних точки. Это означает, что две соседние точки могут отличаться друг от друга только по одной координате и только на 1 единицу. Т. е. для точки (x, y) соседними являются точки (x+1, y), (x-1, y), (x, y+1), (x, y-1). Точка (x+1, y+1) может оказаться закрашенной только если закрашена точка (x+1, y) или (x, y+1). Алгоритм Брезенхема модифицированный по такому закону реализован в данной программе.
2. Алгоритм Брезенхема для 8-связной линии.
static public void Bresenham8Line(Graphics g, Color clr, int x0, int y0, int x1, int y1)
Данный алгоритм предполагает, что у каждой точки растра существует ровно 8 соседних точек. Т. е. приращение абсциссы и ординаты может одновременно составлять +/- 1. Таким образом у точки (x, y) появляется 4 новых соседки : (x+1, y+1), (x-1, y+1), (x-1, y-1), (x+1, y-1).
3. Алгоритм Ву Сяолиня растеризации линии с антиалиасингом.
public static void DrawWuLine(Graphics g, Color clr, int x0, int y0, int x1, int y1)
Алгоритм использует механизмы сглаживания при растеризации линии. При этом ступенчатые выступы на линии становятся менее заметны. Этот эффект достигается следующим образом. На первом шаге для точки, лежащей на линии, вычисляются две ближайшие точки растра. Далее между этими двумя точками распределяется прозрачность(альфа-канал) цвета пиксела пропорционально близости пиксела к линии таким образом, чтобы суммарная яркость была равна единице. При таком распределении человеческий глаз воспринимает последовательность нескольких пикселов с взаимодополняющими значениями прозрачности как непрерывную линию, причем достаточно гладкую. В программе реализован упрощенный алгоритм, в котором некоторые вычисления производятся в вещественном формате, а также учитываются особенности платформы разработки, что замедляет работу алгоритма.
4. Алгоритм Брезенхема для окружности.
public static void BresenhamCircle(Graphics g, Color clr, int _x, int _y, int radius)
Реализация алгоритма Брезенхема для окружности. Вычисляется ближайший к окружности пиксел с учетом правила Брезенхема. Этот алгоритм дает возможность достаточно быстро растеризовать окружность в виде 8-связной линии.
5. Алгоритм Ву Сяолиня растеризации окружности с антиалисингом.
public static void DrawWuCircle(Graphics g, Color clr, int _x, int _y, int radius)
Представляет собой измененный алгоритм растеризации линии. Для точки окружности выбираются два ближайших пиксела. между ними пропорционально распределяется прозрачность цвета. При оптимизации данного алгоритма можно учитывать, что более яркие пикселы, лежащие на внутренней части линии, придают вогнутость линии, а лежащие на внешней стороне - выпуклость.
//file Form1.cs
using System;
using System.Drawing;
using System.Windows.Forms;
namespace RasterAlgorithms
{
public partial class Form1 : Form
{
//Метод Main() - точка входа в программу
public static void Main()
{
using (Form1 frm = new Form1())
{
Application.Run(frm);
}
}
//Конструктор пользовательского класса, наследующего класс Form
public Form1()
{
InitializeComponent();
ResizeRedraw = true;
}
//Обработчик события OnPaint. Отрисовывает на форме её содержимое
protected override void OnPaint(PaintEventArgs e)
{
//Устранение ошибки смещения на 1 пиксел
e.Graphics.PixelOffsetMode = System.Drawing.Drawing2D.PixelOffsetMode.HighQuality;
//Отрисовка 4-связной линии, построенной по алгоритму Брезенхема
RasterAlgorithms.Bresenham4Line(
e.Graphics,
Color.Black,
50, 34, ClientSize.Width - 10, ClientSize.Height - 50);
//Отрисовка 8-связной линии, построенной по алгоритму Брезенхема
RasterAlgorithms.Bresenham8Line(
e.Graphics,
Color.Black,
30, 34, ClientSize.Width - 10, ClientSize.Height - 30);
//Отрисовка линии, построенной по алгоритму Ву
RasterAlgorithms.DrawWuLine(
e.Graphics,
Color.Black,
10, 34, ClientSize.Width - 10, ClientSize.Height - 10);
//Обычная линия
e.Graphics.DrawLine(new Pen(Color.Black),
10, 54, ClientSize.Width - 30, ClientSize.Height - 10);
//Настройки сглаживания
e.Graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
//Линия с установленными параметрами сглаживания
e.Graphics.DrawLine(new Pen(Color.Black),
10, 74, ClientSize.Width - 50, ClientSize.Height - 10);
//Отрисовка окружности, построенной по алгоритму Брезенхема
RasterAlgorithms.BresenhamCircle(
e.Graphics,
Color.Black,
400, 150, 75);
//Отрисовка окружности, построенной по модифицированному алгоритму Ву
RasterAlgorithms.DrawWuCircle(
e.Graphics,
Color.Black,
600, 150, 75);
//Окружность
e.Graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.None;
e.Graphics.DrawEllipse(new Pen(Color.Black), 100, 350, 150, 150);
//Окружность с установленными параметрами сглаживания
e.Graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
e.Graphics.DrawEllipse(new Pen(Color.Black), 300, 350, 150, 150);
}
//Описание элементов меню
private void toolStripMenuItem2_Click(object sender, EventArgs e)
{
Application.Exit();
}
private void toolStripMenuItem4_Click(object sender, EventArgs e)
{
MessageBox.Show(
"Линии (сверху вниз) : \n" +
"1. 4-связная линия, построенная по алгоритму Брезенхема\n" +
"2. 8-связная линия, построенная по алгоритму Брезенхема\n" +
"3. Линия, построенная по алгоритму Ву\n" +
"4. Линия, встроенная в платформу\n" +
"5. Линия с эффектом сглаживания, встроенная в платформу\n\n" +
"Окружности (слева направо сверху вниз) : \n" +
"1. Окружность, построенная по алгоритму Брезенхема\n" +
"2. Окружность, построенная по алгоритму Ву\n" +
"3. Окружность, встроенная в платформу\n" +
"4. Окружность с эффектом сглаживания, встроенная в платформу\n",
"Help");
}
}
//Статический класс, содержащий реализацию растровых алгоритмов
static class RasterAlgorithms
{
//Статический метод, реализующий отрисовку линии по алгоритму Ву
public static void DrawWuLine(Graphics g, Color clr, int x0, int y0, int x1, int y1)
{
//Вычисление изменения координат
int dx = (x1 > x0) ? (x1 - x0) : (x0 - x1);
int dy = (y1 > y0) ? (y1 - y0) : (y0 - y1);
//Если линия параллельна одной из осей, рисуем обычную линию - заполняем все пикселы в ряд
if (dx == 0 || dy == 0)
{
g.DrawLine(new Pen(clr), x0, y0, x1, y1);
return;
}
//Для Х-линии (коэффициент наклона < 1)
if (dy < dx)
{
//Первая точка должна иметь меньшую координату Х
if (x1 < x0)
{
x1 += x0; x0 = x1 - x0; x1 -= x0;
y1 += y0; y0 = y1 - y0; y1 -= y0;
}
//Относительное изменение координаты Y
float grad = (float)dy / dx;
//Промежуточная переменная для Y
float intery = y0 + grad;
//Первая точка
PutPixel(g, clr, x0, y0, 255);
for (int x = x0 + 1; x < x1; x++)
{
//Верхняя точка
PutPixel(g, clr, x, IPart(intery), (int)(255 - FPart(intery) * 255));
//Нижняя точка
PutPixel(g, clr, x, IPart(intery) + 1, (int)(FPart(intery) * 255));
//Изменение координаты Y
intery += grad;
}
//Последняя точка
PutPixel(g, clr, x1, y1, 255);
}
//Для Y-линии (коэффициент наклона > 1)
else
{
//Первая точка должна иметь меньшую координату Y
if (y1 < y0)
{
x1 += x0; x0 = x1 - x0; x1 -= x0;
y1 += y0; y0 = y1 - y0; y1 -= y0;
}
//Относительное изменение координаты X
float grad = (float)dx / dy;
//Промежуточная переменная для X
float interx = x0 + grad;
//Первая точка
PutPixel(g, clr, x0, y0, 255);
for (int y = y0 + 1; y < y1; y++)
{
//Верхняя точка
PutPixel(g, clr, IPart(interx), y, 255 - (int)(FPart(interx) * 255));
//Нижняя точка
PutPixel(g, clr, IPart(interx) + 1, y, (int)(FPart(interx) * 255));
//Изменение координаты X
interx += grad;
}
//Последняя точка
PutPixel(g, clr, x1, y1, 255);
}
}
//Статический метод, реализующий отрисовку окружности по алгоритму Ву
public static void DrawWuCircle(Graphics g, Color clr, int _x, int _y, int radius)
{
//Установка пикселов, лежащих на осях системы координат с началом в центре
PutPixel(g, clr, _x + radius, _y, 255);
PutPixel(g, clr, _x, _y + radius, 255);
PutPixel(g, clr, _x - radius + 1, _y, 255);
PutPixel(g, clr, _x, _y - radius + 1, 255);
float iy = 0;
for (int x = 0; x <= radius * Math.Cos(Math.PI / 4); x++)
{
//Вычисление точного значения координаты Y
iy = (float)Math.Sqrt(radius * radius - x * x);
//IV квадрант, Y
PutPixel(g, clr, _x - x, _y + IPart(iy), 255 - (int)(FPart(iy) * 255));
PutPixel(g, clr, _x - x, _y + IPart(iy) + 1, (int)(FPart(iy) * 255));
//I квадрант, Y
PutPixel(g, clr, _x + x, _y + IPart(iy), 255 - (int)(FPart(iy) * 255));
PutPixel(g, clr, _x + x, _y + IPart(iy) + 1, (int)(FPart(iy) * 255));
//I квадрант, X
PutPixel(g, clr, _x + IPart(iy), _y + x, 255 - (int)(FPart(iy) * 255));
PutPixel(g, clr, _x + IPart(iy) + 1, _y + x, (int)(FPart(iy) * 255));
//II квадрант, X
PutPixel(g, clr, _x + IPart(iy), _y - x, 255 - (int)(FPart(iy) * 255));
PutPixel(g, clr, _x + IPart(iy) + 1, _y - x, (int)(FPart(iy) * 255));
//С помощью инкремента устраняется ошибка смещения на 1 пиксел
x++;
//II квадрант, Y
PutPixel(g, clr, _x + x, _y - IPart(iy), (int)(FPart(iy) * 255));
PutPixel(g, clr, _x + x, _y - IPart(iy) + 1, 255 - (int)(FPart(iy) * 255));
//III квадрант, Y
PutPixel(g, clr, _x - x, _y - IPart(iy), (int)(FPart(iy) * 255));
PutPixel(g, clr, _x - x, _y - IPart(iy) + 1, 255 - (int)(FPart(iy) * 255));
//III квадрант, X
PutPixel(g, clr, _x - IPart(iy), _y - x, (int)(FPart(iy) * 255));
PutPixel(g, clr, _x - IPart(iy) + 1, _y - x, 255 - (int)(FPart(iy) * 255));
//IV квадрант, X
PutPixel(g, clr, _x - IPart(iy), _y + x, (int)(FPart(iy) * 255));
PutPixel(g, clr, _x - IPart(iy) + 1, _y + x, 255 - (int)(FPart(iy) * 255));
//Возврат значения
x--;
}
}
//Статический метод, реализующий отрисовку 8-связной линии по алгоритму Брезенхема
static public void Bresenham8Line(Graphics g, Color clr, int x0, int y0, int x1, int y1)
{
//Изменения координат
int dx = (x1 > x0) ? (x1 - x0) : (x0 - x1);
int dy = (y1 > y0) ? (y1 - y0) : (y0 - y1);
//Направление приращения
int sx = (x1 >= x0) ? (1) : (-1);
int sy = (y1 >= y0) ? (1) : (-1);
if (dy < dx)
{
int d = (dy << 1) - dx;
int d1 = dy << 1;
int d2 = (dy - dx) << 1;
PutPixel(g, clr, x0, y0, 255);
int x = x0 + sx;
int y = y0;
for (int i = 1; i <= dx; i++)
{
if (d > 0)
{
d += d2;
y += sy;
}
else
d += d1;
PutPixel(g, clr, x, y, 255);
x++;
}
}
else
{
int d = (dx << 1) - dy;
int d1 = dx << 1;
int d2 = (dx - dy) << 1;
PutPixel(g, clr, x0, y0, 255);
int x = x0;
int y = y0 + sy;
for (int i = 1; i <= dy; i++)
{
if (d > 0)
{
d += d2;
x += sx;
}
else
d += d1;
PutPixel(g, clr, x, y, 255);
y++;
}
}
}
//Статический метод, реализующий отрисовку 4-связной линии по алгоритму Брезенхема
public static void Bresenham4Line(Graphics g, Color clr, int x0, int y0, int x1, int y1)
{
int dx = x1 - x0;
int dy = y1 - y0;
int d = 0;
int d1 = dy << 1;
int d2 = -(dx << 1);
PutPixel(g, clr, x0, y0, 255);
int x = x0;
int y = y0;
for (int i = 1; i <= dx + dy; i++)
{
if (d > 0)
{
d += d2;
y++;
}
else
{
d += d1;
x++;
}
PutPixel(g, clr, x, y, 255);
}
}
//Статический метод, реализующий отрисовку окружности по алгоритму Брезенхема
public static void BresenhamCircle(Graphics g, Color clr, int _x, int _y, int radius)
{
int x = 0, y = radius, gap = 0, delta = (2 - 2 * radius);
while (y >= 0)
{
PutPixel(g, clr, _x + x, _y + y, 255);
PutPixel(g, clr, _x + x, _y - y, 255);
PutPixel(g, clr, _x - x, _y - y, 255);
PutPixel(g, clr, _x - x, _y + y, 255);
gap = 2 * (delta + y) - 1;
if (delta < 0 && gap <= 0)
{
x++;
delta += 2 * x + 1;
continue;
}
if (delta > 0 && gap > 0)
{
y--;
delta -= 2 * y + 1;
continue;
}
x++;
delta += 2 * (x - y);
y--;
}
}
//Метод, устанавливающий пиксел на форме с заданными цветом и прозрачностью
private static void PutPixel(Graphics g, Color col, int x, int y, int alpha)
{
g.FillRectangle(new SolidBrush(Color.FromArgb(alpha, col)), x, y, 1, 1);
}
//Целая часть числа
private static int IPart(float x)
{
return (int)x;
}
//дробная часть числа
private static float FPart(float x)
{
while (x >= 0)
x--;
x++;
return x;
}
}
}
//file Form1.Designer.cs
namespace RasterAlgorithms
{
partial class Form1
{
/// <summary>
/// Required designer variable.
/// </summary>
private System.ComponentModel.IContainer components = null;
/// <summary>
/// Clean up any resources being used.
/// </summary>
/// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
protected override void Dispose(bool disposing)
{
if (disposing && (components != null))
{
components.Dispose();
}
base.Dispose(disposing);
}
#region Windows Form Designer generated code
/// <summary>
/// Required method for Designer support - do not modify
/// the contents of this method with the code editor.
/// </summary>
private void InitializeComponent()
{
this.menuStrip1 = new System.Windows.Forms.MenuStrip();
this.toolStripMenuItem1 = new System.Windows.Forms.ToolStripMenuItem();
this.toolStripMenuItem2 = new System.Windows.Forms.ToolStripMenuItem();
this.toolStripMenuItem3 = new System.Windows.Forms.ToolStripMenuItem();
this.toolStripMenuItem4 = new System.Windows.Forms.ToolStripMenuItem();
this.menuStrip1.SuspendLayout();
this.SuspendLayout();
//
// menuStrip1
//
this.menuStrip1.Items.AddRange(new System.Windows.Forms.ToolStripItem[] {
this.toolStripMenuItem1,
this.toolStripMenuItem3});
this.menuStrip1.Location = new System.Drawing.Point(0, 0);
this.menuStrip1.Name = "menuStrip1";
this.menuStrip1.Size = new System.Drawing.Size(784, 24);
this.menuStrip1.TabIndex = 1;
this.menuStrip1.Text = "menuStrip1";
//
// toolStripMenuItem1
//
this.toolStripMenuItem1.DropDownItems.AddRange(new System.Windows.Forms.ToolStripItem[] {
this.toolStripMenuItem2});
this.toolStripMenuItem1.Name = "toolStripMenuItem1";
this.toolStripMenuItem1.Size = new System.Drawing.Size(37, 20);
this.toolStripMenuItem1.Text = "File";
//
// toolStripMenuItem2
//
this.toolStripMenuItem2.Name = "toolStripMenuItem2";
this.toolStripMenuItem2.Size = new System.Drawing.Size(152, 22);
this.toolStripMenuItem2.Text = "Exit";
this.toolStripMenuItem2.Click += new System.EventHandler(this.toolStripMenuItem2_Click);
//
// toolStripMenuItem3
//
this.toolStripMenuItem3.DropDownItems.AddRange(new System.Windows.Forms.ToolStripItem[] {
this.toolStripMenuItem4});
this.toolStripMenuItem3.Name = "toolStripMenuItem3";
this.toolStripMenuItem3.Size = new System.Drawing.Size(44, 20);
this.toolStripMenuItem3.Text = "Help";
//
// toolStripMenuItem4
//
this.toolStripMenuItem4.Name = "toolStripMenuItem4";
this.toolStripMenuItem4.Size = new System.Drawing.Size(152, 22);
this.toolStripMenuItem4.Text = "Help";
this.toolStripMenuItem4.Click += new System.EventHandler(this.toolStripMenuItem4_Click);
//
// Form1
//
this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
this.ClientSize = new System.Drawing.Size(784, 562);
this.Controls.Add(this.menuStrip1);
this.MainMenuStrip = this.menuStrip1;
this.Name = "Form1";
this.Text = "Form1";
this.menuStrip1.ResumeLayout(false);
this.menuStrip1.PerformLayout();
this.ResumeLayout(false);
this.PerformLayout();
}
#endregion
private System.Windows.Forms.MenuStrip menuStrip1;
private System.Windows.Forms.ToolStripMenuItem toolStripMenuItem1;
private System.Windows.Forms.ToolStripMenuItem toolStripMenuItem2;
private System.Windows.Forms.ToolStripMenuItem toolStripMenuItem3;
private System.Windows.Forms.ToolStripMenuItem toolStripMenuItem4;
}
}
Ключевые слова:
алгоритм растр брезенхем сглаживание
|
|
