Список работ

Алгоритм плавающих горизонтов: удаление невидимых линий

Содержание

Алгоритм плавающих горизонтов

В приводимой ниже программе алгоритм используется для вывода поверхности в виде линий пересечения поверхности с плоскостями X = const или Y = const. Сами же линии аппроксимируются точками (рис. 1).

Поверхность в виде линий

Рис. 1. График функции z = sin(sqrt(x2 + y2))

Алгоритм иллюстрирует рис. 2, на котором показана функция

z = ((1 – x)2 + 100 * (1 + y – x2)2) / 500 - 2.5

Иллюстрация алгоритма плавающих горизонтов

Рис. 2. Иллюстрация алгоритма плавающих горизонтов

Линии, отображающие поверхность, получаются в результате пересечения поверхности следующим плоскостями:

Y = -2; Y = -1.2; Y = -0.4; Y = 0.4; Y = 1.2 и Y =2.

В левой части рисунка выводятся и видимые, и невидимые части линий; в центральной – только видимые части линий; справа – линия на плоскости Y = 0.4.
Цифра у линии указывает на порядок ее вывода.
Линии 1 и 2 видны целиком. У линии 3 не видна небольшая нижняя часть (показана красным цветом на левом графике).
У линии 4 будет видна часть, лежащая выше линии 1, и часть, расположенная, ниже линии 3. Аналогично определяются видимые куски линий 5 и 6.
Такая логика обеспечивается следующим алгоритмом:

  1. Начало.
  2. Инициализировать массивы целочисленные horMax и horMin:
        horMax(1:width) = 0;
        horMin(1:width) = height,
        где width и height – соответственно ширина и высота видового порта, в который выводится график функции.
        Массивы представляют соответственно верхний и нижний горизонты.
  3. Задать начальную секущую плоскость Y = Ymin.
  4. X = Xmin.
  5. Найти в этой плоскости точку Z на поверхности, отвечающую текущим X и Y. (Координаты X, Y, Z являются мировыми).
  6. Найти в видовом порте проекцию (IX, IY) точки (X, Y, Z).
  7. Если IY > horMax(IX), то
        horMax(IX) = IY.
        Вывести пиксель (IX, IY) красным цветом.
  8. Если IY < horMin(IX), то
        horMin(IX) = IY.
        Вывести пиксель (IX, IY) зеленым цветом.
  9. X = X + dx.
  10. Если X <= Xmax, то перейти к п. 5.
  11. Y = Y + dy.
  12. Если Y <= Ymax, то перейти к п. 4.
  13. Останов.

Текущая точка (X, Y, Z), проецируемая в точку видового порта (IX, IY), будет выведена, если IY будет либо выше верхнего горизонта на вертикали IX, либо ниже нижнего горизонта на той же вертикали. При этом верхний или нижний горизонт, или оба горизонта будут скорректированы.
Алгоритм работает в картинной плоскости (видовом порте). Поэтому в нем присутствует п. 6, который реализуется следующей функцией:

        private int[] Project(ref Matrix4 proj, ref Matrix4 view, int gWidth, int gHeight, ref Vector4 vec)
        {
            int[] point = new int[2];
            int ix, iy;
            Vector4.Transform(ref vec, ref view, out vec);
            Vector4.Transform(ref vec, ref proj, out vec);
            // Переход от однородных к декартовым координатам
            if (Math.Abs(vec.W) > float.Epsilon)
            {
                vec.X /= vec.W;
                vec.Y /= vec.W;
                vec.Z /= vec.W;
            }
            ix = Convert.ToInt32(0.5f * gWidth * (vec.X + 1f));
            iy = Convert.ToInt32(0.5f * gHeight * (vec.Y + 1f));
            if (ix < 0) ix = 0;
            if (ix >= gWidth) ix = gWidth - 1;
            point[0] = ix;
            point[1] = iy;
            return point;
        }

Функция принимает следующие параметры:

Функция возвращает массив point, в котором point[0] = IX, а point[1] = IY, где (IX, IY) – координаты проекции текущей точки поверхности в видовом порте.

Реализация на C#

Интерфейс программы, реализующей алгоритм плавающих горизонтов, показан на рис. 3.

Интерфейс приложения

Рис. 3. Интерфейс приложения

C#-код:

using System;
using System.Drawing; // Color
using System.Windows.Forms;
using OpenTK; // WindowState , Exit() and so on
using OpenTK.Graphics.OpenGL;

namespace WindowsFormsApplicationOpenTK
{
    public partial class FormSphere : Form
    {
        float cx = 3f, cy = 3f, cz = 3f; // Параметры матрицы проецирования
        float x1 = -2, x2 = 2; // Диапазоны изменения X и Y-координат
        float y1 = -2, y2 = 2;
        float dx = 0.002f, dy = 0.4f; // Шаг по X и Y
        double rotX0 = -90, rotY0 = 0, rotZ0 = 0;
        double rotX, rotY, rotZ;
        double dRotX = 2, dRotY = 2;
        int gWidth, gHeight;
        int[] ps = new int[2];
        int[] horMin, horMax;
        Matrix4 projectionMatrix, modelViewMatrix;
        
        public FormSphere()
        {
            InitializeComponent();
            timer.Enabled = false;
            timer.Interval = 500;
        }
        void projMat()
        {
            GL.MatrixMode(MatrixMode.Projection); // Формируем матрицу проецирования
            GL.LoadIdentity();
            GL.Ortho(-cx, cx, -cy, cy, -cz, cz);
            GL.GetFloat(GetPName.ProjectionMatrix, out projectionMatrix);
        }
        private void glControlRoz_Load(object sender, EventArgs e)
        {
            gWidth = glControlRoz.Width;
            gHeight = glControlRoz.Height;
            GL.Viewport(0, 0, gWidth, gHeight);
            projMat();
            GL.MatrixMode(MatrixMode.Modelview);
            GL.LoadIdentity();
            radioButtonRoz.Checked = true;
        }
        private void initHor()
        {
            horMin = new int[gWidth];
            horMax = new int[gWidth];
            for (int k = 0; k < gWidth; k++)
            {
                horMin[k] = gHeight;
                horMax[k] = 0;
            }
        }
        void putPoint(float x, float y, float z)
        {
            if (checkBoxAllPoints.Checked)
            {
                GL.Color3(Color.Black);
                GL.Vertex3(x, y, z);
            }
            else
            {
                Vector4 vec = new Vector4(x, y, z, 1);
                ps = Project(ref projectionMatrix, ref modelViewMatrix, gWidth, gHeight, ref vec);
                bool dn = false;
                if (ps[1] > horMax[ps[0]])
                {
                    horMax[ps[0]] = ps[1];
                    GL.Color3(Color.Red);
                    GL.Vertex3(x, y, z);
                    dn = true;
                }
                if (ps[1] < horMin[ps[0]])
                {
                    horMin[ps[0]] = ps[1];
                    if (!dn)
                    {
                        GL.Color3(Color.Green);
                        GL.Vertex3(x, y, z);
                    }
                }
            }
        }
        void Roz()
        {
            float x, y;
            float t, t2, z;
            y = y1 - dy;
            while (y < y2)
            {
                y += dy;
                x = x1 - dx;
                while (x < x2)
                {
                    x += dx;
                    t = 1.0f - x;
                    t2 = (y + 1) - x * x;
                    z = (t * t + 100.0f * t2 * t2) / 500.0f - 2.5f;
                    putPoint(x, y, z);
                }
            }
        }
        void Sph()
        {
            double x, y, z;
            double r = 2;
            int nx = 64;
            int ny = 64;
            double pi = Math.PI;
            double pix = pi / nx;
            double piy = pi / ny;
            double pix2 = 2 * pix;
            double ay = -piy, ax, rsy;
            for (int iy = 0; iy < ny; iy++)
            {
                ay += piy;
                rsy = r * Math.Sin(ay);
                y = r * Math.Cos(ay);
                ax = -pix2;
                for (int ix = 0; ix <= nx; ix++)
                {
                    ax += pix2;
                    x = rsy * Math.Cos(ax);
                    z = rsy * Math.Sin(ax);
                    putPoint((float)x, (float)y, (float)z);
                }
            }
        }
        void Sqrt()
        {
            float x, y, z;
            y = y1 - dy;
            while (y < y2)
            {
                y += dy;
                x = x1 - dx;
                while (x < x2)
                {
                    x += dx;
                    z = (float)Math.Sin(Math.Sqrt(x * x + y * y));
                    z = 3 * z;
                    putPoint(x, y, z);
                }
            }
        }
        void Exp()
        {
            const float pi = (float)Math.PI;
            float x, y;
            float z, alph;
            y = y1 - dy;
            while (y < y2)
            {
                y += dy;
                x = x1 - dx;
                while (x < x2)
                {
                    x += dx;
                    alph = (x - pi) * (x - pi) + (y - pi) * (y - pi);
                    z = (float)(0.2 * Math.Sin(x) * Math.Cos(y) - 1.5 * Math.Cos(1.75 * alph) * Math.Exp(-alph));
                    z = 3 * z;
                    putPoint(x, y, z);
                }
            }
        }
        private void glControlRoz_Paint(object sender, PaintEventArgs e)
        {
            label1.Text = "Rot_X = " + rotX;
            label2.Text = "Rot_Y = " + rotY;
            if (!checkBoxAllPoints.Checked) initHor();
            GL.MatrixMode(MatrixMode.Modelview);
            GL.PushMatrix();
            GL.Rotate(rotX, new Vector3d(1, 0, 0));
            GL.Rotate(rotY, new Vector3d(0, 1, 0));
            GL.Rotate(rotZ, new Vector3d(0, 0, 1));
            GL.GetFloat(GetPName.ModelviewMatrix, out modelViewMatrix);
            // Заливка окна вывода
            GL.ClearColor(Color.Beige);
            GL.Clear(ClearBufferMask.ColorBufferBit);
            GL.PointSize(2f);
            GL.Begin(PrimitiveType.Points);
            if (radioButtonRoz.Checked)
                Roz();
            else if (radioButtonSph.Checked)
                Sph();
            else if (radioButtonSqrt.Checked)
                Sqrt();
            else
                Exp();
            GL.End();
            glControlRoz.SwapBuffers();
            GL.PopMatrix();
        }
        private int[] Project(ref Matrix4 proj, ref Matrix4 view, int gWidth, int gHeight, ref Vector4 vec)
        {
            int[] point = new int[2];
            int ix, iy;
            Vector4.Transform(ref vec, ref view, out vec);
            Vector4.Transform(ref vec, ref proj, out vec);
            // Переход от однородных к декартовым координатам
            if (Math.Abs(vec.W) > float.Epsilon)
            {
                vec.X /= vec.W;
                vec.Y /= vec.W;
                vec.Z /= vec.W;
            }
            ix = Convert.ToInt32(0.5f * gWidth * (vec.X + 1f));
            iy = Convert.ToInt32(0.5f * gHeight * (vec.Y + 1f));
            if (ix < 0) ix = 0;
            if (ix >= gWidth) ix = gWidth - 1;
            point[0] = ix;
            point[1] = iy;
            return point;
        }
        private void timer_Tick(object sender, EventArgs e)
        {
            initHor();
            rotX -= dRotX;
            rotY += dRotY;
            if (rotX > -75 || rotX < -135) dRotX = -dRotX;
            if (rotY > 360 || rotY < 0) dRotY = -dRotY;
            glControlRoz.Invalidate();
        }
        private void checkBoxAllPoints_CheckedChanged(object sender, EventArgs e)
        {
            timer.Enabled = false;
            buttonStop.Text = "Поехали";
            rotX = rotX0;
            rotY = rotY0;
            rotZ = rotZ0;
            glControlRoz.Invalidate();
        }
        void rbChange()
        {
            projMat();
            timer.Enabled = false;
            buttonStop.Text = "Поехали";
            rotX = rotX0;
            rotY = rotY0;
            rotZ = rotZ0;
            glControlRoz.Invalidate();
        }
        private void radioButtonRoz_CheckedChanged(object sender, EventArgs e)
        {
            if (radioButtonRoz.Checked)
            {
                cx = 3f; cy = 3f; cz = 3f; // Параметры матрицы проецирования
                x1 = -2; x2 = 2; // Диапазоны изменения X и Y-координат
                y1 = -2; y2 = 2;
                rbChange();
            }
        }
        private void radioButtonSph_CheckedChanged(object sender, EventArgs e)
        {
            cx = 2.5f; cy = 2.5f; cz = 2.5f; // Параметры матрицы проецирования
            x1 = -2; x2 = 2; // Диапазоны изменения X и Y-координат
            y1 = -2; y2 = 2;
            rbChange();
        }
        private void radioButtonSqrt_CheckedChanged(object sender, EventArgs e)
        {
            const float pi = (float) Math.PI;
            const float c = 4.5f;
            const float c2 = 4.5f;
            x1 = -c * pi; x2 = c * pi; // Диапазоны изменения X и Y-координат
            y1 = -c * pi; y2 = c * pi;
            cx = c2 * c; cy = c2 * c; cz = c2 * c; // Параметры матрицы проецирования
            rbChange();
        }
        private void radioButtonExp_CheckedChanged(object sender, EventArgs e)
        {
            const float pi = (float)Math.PI;
            const float c = 2.2f;
            const float c2 = 2.2f;
            x1 = -pi / c; x2 = c * pi; // Диапазоны изменения X и Y-координат
            y1 = -pi / c; y2 = c * pi;
            cx = c2 * c; cy = c2 * c; cz = c2 * c; // Параметры матрицы проецирования
            rbChange();
        }
        private void buttonStop_Click(object sender, EventArgs e)
        {
            timer.Enabled = !timer.Enabled;
            if (timer.Enabled)
                buttonStop.Text = "Стоп";
            else
                buttonStop.Text = "Поехали";
        }
        private void buttonClose_Click(object sender, EventArgs e)
        {
            this.Close();
        }
    }
}

Список работ

Рейтинг@Mail.ru