491 lines
28 KiB
Markdown
491 lines
28 KiB
Markdown
# Лабораторная работа 3
|
||
## Векторный редактор `Zivro`
|
||
|
||
## 1. Цель работы
|
||
|
||
### 1.1. Дидактическая цель
|
||
|
||
Овладеть навыками разработки программных модулей, реализующих алгоритмы растровой развёртки (растеризации) контуров фигур и сплошных областей на плоскости, а также получить опыт эмпирического анализа вычислительной трудоёмкости и точности алгоритмов растеризации.
|
||
|
||
### 1.2. Практическая цель
|
||
|
||
Разработать и исследовать программный модуль, выполняющий:
|
||
|
||
- растеризацию контура фигуры;
|
||
- растеризацию (закраску) сплошной области;
|
||
- формирование и отображение растрового изображения;
|
||
- сбор эмпирических данных по времени выполнения и различию результатов алгоритмов.
|
||
|
||
В рамках данной работы в качестве программной базы используется проект `Zivro`, разработанный автором специально для выполнения лабораторной работы, в который интегрированы и исследуются соответствующие алгоритмы.
|
||
|
||
## 2. Постановка задачи
|
||
|
||
В рамках лабораторной работы требуется реализовать и проверить функционал, соответствующий методическим указаниям ЛР №3:
|
||
|
||
1. Реализовать программный модуль растеризации контура и внутренней области фигуры на растровом изображении.
|
||
2. Обеспечить вывод результата в окне/холсте приложения с попиксельной визуализацией.
|
||
3. Реализовать не менее двух алгоритмов построения контура и не менее двух алгоритмов закраски (в соответствии с вариантом).
|
||
4. Добавить эталонный контурный алгоритм (например, Брезенхейм) для сравнения.
|
||
5. Реализовать сбор эмпирических данных:
|
||
- время выполнения алгоритмов;
|
||
- различие получаемых растровых развёрток (по отличающимся пикселям).
|
||
6. Подготовить и оформить отчёт по выполненной работе.
|
||
7. Сформировать приложение с исходными текстами автоматически в отдельный `.md` без изменения исходного файла отчёта.
|
||
|
||
## 3. Краткое описание проекта
|
||
|
||
Для выполнения ЛР в качестве основы используется проект `Zivro` - настольное графическое приложение для работы с векторными объектами (линия, эллипс, ломаная), с собственной моделью документа, иерархией объектов и CPU-рендерингом.
|
||
|
||
В контексте ЛР проект используется не как объект абстрактного обзора, а как программная платформа, где реализуются и исследуются алгоритмы растеризации контура и закраски.
|
||
|
||
Приложение использует:
|
||
|
||
- язык `Zig`;
|
||
- UI-библиотеку `dvui` с SDL3-бэкендом;
|
||
- модульную архитектуру (UI, модель данных, рендер, сериализация, инструменты).
|
||
|
||
Точка входа находится в `src/main.zig`: создаётся окно, инициализируется `WindowContext`, далее выполняется event/render loop и отрисовка растрового результата алгоритмов.
|
||
|
||
## 4. Структура проекта
|
||
|
||
Основные каталоги и файлы:
|
||
|
||
- `build.zig` - сценарий сборки и шагов `run`/`test`;
|
||
- `src/main.zig` - запуск приложения и главный цикл;
|
||
- `src/WindowContext.zig` - управление открытыми документами и активным документом;
|
||
- `src/Canvas.zig` - логика холста, масштабирование, вычисление видимой области, запуск рендера;
|
||
- `src/models/*` - модель документа, объектов и их свойств;
|
||
- `src/render/*` - CPU-рендер и конвейер отрисовки;
|
||
- `src/persistence/json_io.zig` - сохранение/загрузка документов в JSON;
|
||
- `src/ui/*` - интерфейсные панели и компоновка экрана;
|
||
- `src/tests.zig` - entry-point тестов.
|
||
|
||
## 5. Архитектура приложения
|
||
|
||
### 5.1. Высокоуровневая схема
|
||
|
||
Архитектурно проект разделён на три уровня:
|
||
|
||
1. **UI-уровень** (`src/ui`, `src/Canvas.zig`)
|
||
Обрабатывает пользовательские события, отображает панели и холст, передаёт действия в модель и рендер.
|
||
|
||
2. **Модель данных** (`src/models`)
|
||
Хранит документ, дерево объектов и свойства (позиция, угол, масштаб, цвет, точки, радиусы и др.).
|
||
|
||
3. **Рендер-уровень** (`src/render`)
|
||
Преобразует модель объектов в набор пикселей видимой области и формирует текстуру.
|
||
|
||
### 5.2. Управление документами
|
||
|
||
`WindowContext` хранит массив открытых документов (`OpenDocument`) и индекс активного документа.
|
||
Каждый `OpenDocument` содержит:
|
||
|
||
- `Document`;
|
||
- экземпляр `CpuRenderEngine`;
|
||
- `Canvas`;
|
||
- идентификатор выбранного объекта.
|
||
|
||
Это позволяет одновременно работать с несколькими документами во вкладках.
|
||
|
||
### 5.3. Рендер-конвейер
|
||
|
||
Ключевой путь рендера:
|
||
|
||
1. `Canvas.redraw()` вычисляет масштаб качества и видимую часть документа;
|
||
2. вызывается `RenderEngine.render(...)` (в текущей конфигурации CPU-вариант);
|
||
3. `CpuRenderEngine.renderDocument(...)` подготавливает пиксельный буфер;
|
||
4. `cpu/draw.zig` рекурсивно обходит объекты документа;
|
||
5. для каждого объекта применяется `Transform.compose(parent, local)`;
|
||
6. shape-специфичные модули рисуют примитивы в буфер;
|
||
7. буфер превращается в текстуру UI.
|
||
|
||
## 6. Математические алгоритмы проекта (подробное текстовое описание)
|
||
|
||
В данном разделе подробно рассмотрены алгоритмы, которые формируют геометрию и цвет в CPU-рендере.
|
||
|
||
### 6.1. Иерархические трансформации объектов
|
||
|
||
В основе рендера лежит сцена-дерево: каждый объект может иметь дочерние элементы.
|
||
Следовательно, координаты дочернего объекта заданы не в мировой системе, а в системе координат родителя.
|
||
|
||
В `Transform` хранятся:
|
||
|
||
- `position = (tx, ty)` - перенос;
|
||
- `angle = a` - поворот;
|
||
- `scale = (sx, sy)` - независимый масштаб по осям;
|
||
- `opacity = o` - накопленная непрозрачность.
|
||
|
||
Для перехода из локальных координат объекта к мировым используется аффинное преобразование:
|
||
|
||
$$
|
||
\begin{aligned}
|
||
x_w &= t_x + (x_l \cdot s_x)\cos a - (y_l \cdot s_y)\sin a, \\
|
||
y_w &= t_y + (x_l \cdot s_x)\sin a + (y_l \cdot s_y)\cos a.
|
||
\end{aligned}
|
||
$$
|
||
|
||
Обозначения:
|
||
|
||
- `x_l, y_l` - локальные координаты точки объекта;
|
||
- `x_w, y_w` - мировые координаты точки в документе;
|
||
- `t_x, t_y` - перенос (`position`) текущего transform;
|
||
- `s_x, s_y` - масштаб по осям (`scale_x`, `scale_y`);
|
||
- `a` - угол поворота объекта (в радианах).
|
||
|
||
При композиции `parent * local` (в `Transform.compose`) выполняются шаги:
|
||
|
||
1. локальная позиция сначала масштабируется масштабом родителя;
|
||
2. результат поворачивается на угол родителя;
|
||
3. добавляется перенос родителя;
|
||
4. углы складываются: `a_world = a_parent + a_local`;
|
||
5. масштабы перемножаются покомпонентно: `sx_world = sx_parent * sx_local`, `sy_world = sy_parent * sy_local`;
|
||
6. прозрачности перемножаются: `o_world = o_parent * o_local`.
|
||
|
||
Почему это важно: такой порядок гарантирует, что при повороте/масштабе группы объектов дочерние элементы ведут себя как единая связанная конструкция.
|
||
|
||
### 6.2. Цепочка преобразований координат в рендере
|
||
|
||
Рендер использует 4 системы координат:
|
||
|
||
1. **локальная** (внутри shape);
|
||
2. **мировая** (внутри документа);
|
||
3. **координаты канвы** (после масштабирования документа под текущий размер);
|
||
4. **координаты буфера viewport** (видимая часть, начинающаяся с `(0,0)`).
|
||
|
||
Основные формулы:
|
||
|
||
- `canvas_x = world_x * scale_x`, `canvas_y = world_y * scale_y`;
|
||
- `buffer_x = canvas_x - visible_rect.x`, `buffer_y = canvas_y - visible_rect.y`.
|
||
|
||
Обратное преобразование также используется (например, в эллипсе):
|
||
|
||
- `canvas_x = buffer_x + visible_rect.x`, `canvas_y = buffer_y + visible_rect.y`;
|
||
- `world_x = canvas_x / scale_x`, `world_y = canvas_y / scale_y`.
|
||
|
||
Для вычисления локальных координат из мировых применяется обратный поворот и обратный масштаб:
|
||
|
||
$$
|
||
\begin{aligned}
|
||
dx &= x_w - t_x,\quad dy = y_w - t_y, \\
|
||
x_l &= \frac{dx\cos(-a)-dy\sin(-a)}{s_x}, \\
|
||
y_l &= \frac{dx\sin(-a)+dy\cos(-a)}{s_y}.
|
||
\end{aligned}
|
||
$$
|
||
|
||
Обозначения:
|
||
|
||
- `x_w, y_w` - мировые координаты точки;
|
||
- `x_l, y_l` - локальные координаты точки после обратного преобразования;
|
||
- `t_x, t_y` - перенос transform;
|
||
- `a` - угол поворота transform;
|
||
- `s_x, s_y` - масштаб transform;
|
||
- `dx, dy` - координаты точки после вычитания переноса.
|
||
|
||
Практический смысл: shape можно тестировать аналитически (по формулам) в "своей" удобной локальной системе, независимо от того, как он повернут и где расположен в документе.
|
||
|
||
### 6.3. Рисование линии: отсечение + дискретизация + толщина
|
||
|
||
Алгоритм в `line.zig` состоит из трёх частей.
|
||
|
||
#### 6.3.1. Отсечение Liang-Barsky
|
||
|
||
Перед рисованием линия отсекается расширенным прямоугольником буфера.
|
||
Параметрическая форма отрезка:
|
||
|
||
$$
|
||
P(t)=P_0+t(P_1-P_0),\quad t\in[0,1].
|
||
$$
|
||
|
||
Обозначения:
|
||
|
||
- `P_0, P_1` - начальная и конечная точки исходного отрезка;
|
||
- `P(t)` - точка на отрезке при параметре `t`;
|
||
- `t` - параметр интерполяции (`0` - начало, `1` - конец);
|
||
- `[t0, t1]` - допустимый интервал параметра после отсечения.
|
||
|
||
Для каждого ограничения (`x >= left`, `x <= right`, `y >= top`, `y <= bottom`) обновляется допустимый интервал `[t0, t1]`.
|
||
Если после обработки ограничений `t0 > t1`, отрезок полностью вне экрана и пропускается.
|
||
|
||
Преимущество: вместо "шагать по пикселям и каждый проверять границы" рендер сразу работает только с видимым отрезком.
|
||
|
||
#### 6.3.2. Дискретизация линии (Bresenham-подобный проход)
|
||
|
||
После отсечения используются целочисленные приращения:
|
||
|
||
- `dx = abs(x1 - x0)`, `dy = -abs(y1 - y0)`;
|
||
- `sx = sign(x1 - x0)`, `sy = sign(y1 - y0)`;
|
||
- ошибка `err = dx + dy`.
|
||
|
||
На каждом шаге:
|
||
|
||
- вычисляется `e2 = 2*err`;
|
||
- если `e2 >= dy`, двигаемся по `x`;
|
||
- если `e2 <= dx`, двигаемся по `y`.
|
||
|
||
Это классическая идея целочисленного интегрирования ошибки для аппроксимации идеального непрерывного отрезка на пиксельной сетке.
|
||
|
||
#### 6.3.3. Толщина и коррекция по углу
|
||
|
||
Если просто расширять линию равномерно, визуальная толщина может "плыть" при разных углах.
|
||
В проекте вычисляется поправка по длине проекций:
|
||
|
||
- `cos(theta) = |dx| / len`;
|
||
- `sin(theta) = |dy| / len`;
|
||
- выбирается базис (по X или Y), где ошибка толщины минимальна;
|
||
- итоговая толщина пересчитывается через деление на `max(sin, eps)` или `max(cos, eps)`.
|
||
|
||
Далее вокруг центрального пикселя проводится полоса ширины `thickness_corrected`.
|
||
|
||
Дополнительно есть режим `draw_when_outside`:
|
||
|
||
- внутри viewport рисуется полная толщина;
|
||
- за пределами viewport — только 1px, чтобы контур не "взрывался" по ширине за экраном.
|
||
|
||
### 6.4. Растрирование эллипса и дуги
|
||
|
||
Алгоритм `ellipse.zig` не использует инкрементальные midpoint-формулы, а работает через аналитическую проверку каждого пикселя в ограничивающем прямоугольнике.
|
||
|
||
#### 6.4.1. Нормализация координат
|
||
|
||
Для пикселя вычисляются локальные координаты `loc = (x_l, y_l)` и нормализуются:
|
||
|
||
$$
|
||
n_x = \frac{x_l}{r_x},\quad n_y = \frac{y_l}{r_y},\quad d=n_x^2+n_y^2.
|
||
$$
|
||
|
||
Обозначения:
|
||
|
||
- `x_l, y_l` - локальные координаты текущего пикселя (центра пикселя после обратного преобразования);
|
||
- `r_x, r_y` - полуоси эллипса по `x` и `y`;
|
||
- `n_x, n_y` - нормализованные координаты в системе эллипса;
|
||
- `d` - значение функции эллипса в нормализованной форме.
|
||
|
||
- `d = 1` соответствует идеальному контуру эллипса;
|
||
- `d < 1` внутри;
|
||
- `d > 1` снаружи.
|
||
|
||
#### 6.4.2. Полоса обводки заданной толщины
|
||
|
||
Толщина `thickness` переводится в нормированное пространство через меньшую полуось:
|
||
|
||
- `half_norm = thickness / (2*min(rx, ry))`;
|
||
- внутренний радиус: `inner = max(0, 1 - half_norm)`;
|
||
- внешний радиус: `outer = 1 + half_norm`.
|
||
|
||
Пиксель принадлежит обводке, если:
|
||
|
||
$$
|
||
inner^2 \le d \le outer^2.
|
||
$$
|
||
|
||
Обозначения:
|
||
|
||
- `d` - нормализованная квадратичная дистанция из предыдущей формулы;
|
||
- `inner` - внутренний радиус полосы обводки в нормализованном пространстве;
|
||
- `outer` - внешний радиус полосы обводки в нормализованном пространстве.
|
||
|
||
Это даёт геометрически корректную полосу вокруг эллипса при произвольном повороте/масштабе объекта.
|
||
|
||
#### 6.4.3. Дуга через угловой фильтр
|
||
|
||
Если `arc_percent < 100`, из полного эллипса берётся только часть:
|
||
|
||
- вычисляется длина дуги в радианах: `arc_len = 2*pi*arc_percent/100`;
|
||
- для пикселя находится угол через `atan2(ny, nx)` (с поправкой на экранную систему);
|
||
- точка принимается только если её угловая позиция не превышает `arc_len`.
|
||
|
||
Если `closed = true`, концы дуги соединяются с центром двумя радиальными отрезками (используется общий алгоритм линии).
|
||
|
||
### 6.5. Ломаная, выделение границы и заливка
|
||
|
||
В `broken.zig` ломаная строится как цепочка сегментов `P0->P1->...->Pn`, а при `closed` добавляется `Pn->P0`.
|
||
|
||
Для корректной заливки применяется трёхфазный алгоритм.
|
||
|
||
#### 6.5.1. Фаза 1: сбор пикселей границы
|
||
|
||
Во временном `FillCanvas` при каждом `blendPixelAtBuffer` сохраняется координата пикселя как граничная точка (`border_set`).
|
||
|
||
Смысл: сначала зафиксировать "жёсткий" контур, затем независимо заполнить внутренность.
|
||
|
||
#### 6.5.2. Фаза 2: поиск внутренних сегментов по строкам
|
||
|
||
Граничные пиксели сортируются по `(y, x)`. Для каждой строки:
|
||
|
||
1. выделяются последовательности рёбер;
|
||
2. строятся интервалы между соседними рёбрами;
|
||
3. из подходящих интервалов выбираются seed-точки (середина интервала).
|
||
|
||
Это снижает риск старта flood fill с внешней стороны фигуры.
|
||
|
||
#### 6.5.3. Фаза 3: flood fill (4-связность)
|
||
|
||
От каждого seed выполняется стековый обход соседей:
|
||
|
||
- влево, вправо, вверх, вниз;
|
||
- граничные пиксели не пересекаются;
|
||
- уже посещённые пиксели пропускаются.
|
||
|
||
Каждый найденный внутренний пиксель окрашивается в `fill_color`.
|
||
|
||
Почему используется отдельный буфер: при полупрозрачности иначе одна и та же область может смешаться несколько раз из-за пересечения сегментов.
|
||
|
||
### 6.6. Альфа-смешивание в Premultiplied Alpha (PMA)
|
||
|
||
Для каждого канала цвета применяется модель:
|
||
|
||
$$
|
||
C_{out} = C_{src} + (1-\alpha_{src})C_{dst},
|
||
\quad
|
||
\alpha_{out} = \alpha_{src} + (1-\alpha_{src})\alpha_{dst}.
|
||
$$
|
||
|
||
Обозначения:
|
||
|
||
- `C_src` - цвет источника в PMA (`r,g,b` уже домножены на альфу);
|
||
- `C_dst` - текущий цвет пикселя в буфере до смешивания;
|
||
- `C_out` - результат смешивания;
|
||
- `\alpha_src` - альфа источника (с учётом `transform.opacity`);
|
||
- `\alpha_dst` - альфа пикселя назначения;
|
||
- `\alpha_out` - итоговая альфа после композиции.
|
||
|
||
В коде `C_src` уже premultiplied (или домножается на opacity трансформа в момент смешивания).
|
||
|
||
Пошагово:
|
||
|
||
1. берётся альфа источника `a = src_a/255 * transform.opacity`;
|
||
2. вычисляется `inv_a = 1 - a`;
|
||
3. каналы `r,g,b` источника масштабируются на `transform.opacity`;
|
||
4. формируется новый `dst` по PMA-формуле.
|
||
|
||
`replace_mode = true` отключает смешивание и просто заменяет пиксель.
|
||
Этот режим используется во временных буферах shape-рендера, а затем результат один раз композится в целевой буфер.
|
||
|
||
### 6.7. Численная устойчивость и ограничения
|
||
|
||
В алгоритмах предусмотрены защиты от деградации вычислений:
|
||
|
||
- защита от деления на ноль в обратных преобразованиях (`scale == 0 -> 1.0`);
|
||
- использование `eps` в коррекции толщины линий;
|
||
- ограничение минимальных размеров рендер-буфера (`>= 1 px`);
|
||
- отсечение слишком больших выходов за viewport до начала растрирования;
|
||
- явное округление float->int в точках, где нужна стабильная пиксельная привязка.
|
||
|
||
Это снижает число визуальных артефактов при малых масштабах, сильных поворотах и частичной видимости объектов.
|
||
|
||
## 7. Работа с данными и сериализация
|
||
|
||
Модуль `src/persistence/json_io.zig` поддерживает:
|
||
|
||
- `saveToFile(...)` - сериализация в JSON (pretty-print);
|
||
- `loadFromFile(...)` - чтение JSON и восстановление структуры.
|
||
|
||
Для `Document` после парсинга выполняется клонирование, чтобы избежать проблем владения памятью (парсер выделяет память из арены).
|
||
|
||
## 8. Сборка, запуск и тестирование
|
||
|
||
### 8.1. Сборка и запуск
|
||
|
||
```bash
|
||
zig build
|
||
zig build run
|
||
```
|
||
|
||
### 8.2. Запуск тестов
|
||
|
||
```bash
|
||
zig build test
|
||
```
|
||
|
||
Файл `src/tests.zig` подключает модули с `test`-блоками, чтобы они выполнялись в составе общего тестового шага.
|
||
|
||
## 9. Автоматическое формирование приложения с исходным кодом
|
||
|
||
Чтобы не вставлять исходники вручную в конец отчёта, используется скрипт `Report/append_sources_to_report.py`.
|
||
|
||
Скрипт:
|
||
|
||
- читает исходный `.md` отчёт;
|
||
- добавляет раздел с кодом файлов проекта;
|
||
- перед каждым листингом вставляет путь файла;
|
||
- сохраняет результат в новый `.md` файл;
|
||
- исходный отчёт не изменяет.
|
||
|
||
Пример запуска:
|
||
|
||
```bash
|
||
python3 Report/append_sources_to_report.py \
|
||
--input Report/zivro-open-project-report.md \
|
||
--output Report/zivro-open-project-report-with-code.md \
|
||
--base .
|
||
```
|
||
|
||
## 10. PlantUML-диаграммы
|
||
|
||
Для отчёта подготовлены диаграммы в формате PlantUML (`.puml`) и сгенерированы их PNG-версии для прямой вставки в документ.
|
||
|
||
### 10.1. Архитектура проекта
|
||
|
||
`Report/uml/zivro-architecture-components.puml` - компонентная архитектура приложения.
|
||
|
||
|
||
|
||
`Report/uml/zivro-render-sequence.puml` - последовательность рендера кадра.
|
||
|
||
|
||
|
||
### 10.2. Управление холстом и viewport
|
||
|
||
`Report/uml/canvas-viewport-algorithm.puml` - вычисление видимой области, масштабирование по качеству, условия редроу.
|
||
|
||
|
||
|
||
### 10.3. Алгоритмы обработки данных и растризации
|
||
|
||
`Report/uml/transform-compose-algorithm.puml` - композиция трансформаций в иерархии объектов.
|
||
|
||
|
||
|
||
`Report/uml/coordinate-pipeline.puml` - конвейер преобразований координат.
|
||
|
||
|
||
|
||
`Report/uml/line-rasterization-flow.puml` - полный алгоритм отрисовки линии.
|
||
|
||
|
||
|
||
`Report/uml/liang-barsky-clip.puml` - шаги отсечения отрезка методом Liang-Barsky.
|
||
|
||
|
||
|
||
`Report/uml/ellipse-arc-rasterization.puml` - растрирование эллипса/дуги.
|
||
|
||
|
||
|
||
`Report/uml/polyline-fill-algorithm.puml` - построение и заливка замкнутой ломаной.
|
||
|
||
|
||
|
||
`Report/uml/pma-alpha-blending.puml` - PMA alpha-композиция пикселей.
|
||
|
||
|
||
|
||
### 10.4. Скрипт генерации PNG-диаграмм
|
||
|
||
Для повторной генерации PNG сохранён отдельный скрипт:
|
||
|
||
- `Report/render_uml_png.py`
|
||
|
||
Пример запуска в высоком качестве:
|
||
|
||
```bash
|
||
python3 Report/render_uml_png.py --input-dir Report/uml --dpi 360
|
||
```
|
||
|
||
## 11. Выводы
|
||
|
||
В ходе работы разработан и исследован проект `Zivro`, подготовлено структурированное описание его архитектуры. Проект реализует модульный подход: модель документа, иерархию объектов, CPU-рендер с преобразованиями координат и отдельные алгоритмы растеризации геометрии.
|
||
|
||
Ключевые математические части - композиция трансформаций, отсечение и растеризация линий, рендер эллипсов/дуг, а также алгоритм заливки замкнутых контуров.
|
||
Текстовый отчёт подготовлен без встроенных листингов кода; для генерации версии с приложением исходников создан отдельный автоматизированный скрипт.
|