"Информатика (углублённый уровень)", Калинин И.А., Самылкина Н.Н.
Растровое изображение состоит из пикселей, поэтому математически точную линию или область нужно превратить в набор экранных точек. Этот процесс называют растеризацией. Для отрезков применяют, например, алгоритм Брезенхэма: он выбирает подходящие пиксели по целочисленной оценке ошибки. Для заполнения замкнутых областей используют затравочную заливку, которая распространяется от выбранного пикселя, не пересекая контур.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Растровая графика — способ представления изображения в виде сетки отдельных пикселей. Разрешение показывает, сколько пикселей приходится на ширину и высоту изображения, например 800 × 600. Чем меньше растр, тем грубее могут передаваться мелкие детали; при увеличении отдельные пиксели становятся заметнее. Поэтому разрешение влияет на качество изображения, хотя само по себе не определяет его содержание.
Растеризация — преобразование геометрического объекта, заданного математически, в набор пикселей на экране. Например, в математике отрезок состоит из непрерывного множества точек, а на экране нужно выбрать конечное число пикселей. Растеризация нужна для того, чтобы графические объекты можно было показать на устройстве с дискретной сеткой.
Алгоритм Брезенхэма — способ построения отрезка на растре, при котором следующий пиксель выбирают по целочисленной оценке ошибки. Эта оценка показывает, по какую сторону от идеальной линии находится кандидатный пиксель. Метод нужен, чтобы строить линию близко к заданному отрезку и не тратить вычисления на точные вещественные координаты каждого шага.
Затравочная заливка — заполнение связной области изображения, начатое с выбранного пикселя-затравки. Алгоритм проверяет соседние пиксели и закрашивает те, которые принадлежат области, не проходя через её границу. Такой способ используют, например, чтобы заполнить внутреннюю часть замкнутого контура.
Геометрический отрезок нельзя вывести на экран как непрерывную линию: поверхность экрана разделена на отдельные пиксели. Поэтому программа должна решить, какие именно клетки сетки показать и в каком порядке. Если выбрать их неудачно, линия получится прерывистой или заметно отойдёт от заданного направления.
При простом построении отрезка сначала выбирают основную координату — ту, вдоль которой отрезок проходит больше пикселей. Затем движутся по этой оси шаг за шагом, а вторую координату меняют тогда, когда идеальная линия достаточно приблизилась к соседнему ряду пикселей. Такой выбор нужен, чтобы полученная цепочка оставалась связной и как можно точнее повторяла наклон отрезка.
Алгоритм Брезенхэма оценивает, какой из двух соседних пикселей ближе к идеальной линии. После выбора он обновляет ошибку: её знак показывает, пора ли перейти на соседний ряд или столбец. Поскольку изменение ошибки можно выразить целыми числами, алгоритм обходится преимущественно без вещественных вычислений. Это особенно удобно, когда нужно быстро построить много линий.
Наклоны отрезков различаются: иногда сильнее меняется x, а иногда — y. Поэтому перед построением сравнивают модули приращений координат и выбирают основную ось; вторую координату меняют по мере накопления ошибки. Кроме того, координата может возрастать или убывать, и это учитывают знаками шагов. Так обрабатываются отрезки во всех октантах — восьми направлениях на плоскости, разделённых осями и диагоналями.
Затравочная заливка начинает обход из заданного пикселя и рассматривает его соседей. Пиксель закрашивают, если он принадлежит нужной области и не является контуром; затем проверяют его соседние пиксели. Стек или очередь позволяет хранить точки, которые ещё предстоит проверить. Обход заканчивается, когда подходящих соседей больше нет, а проверка границ и уже обработанных пикселей не даёт выйти за контур или зациклиться.
| Свойство | Пошаговое округление координат | Алгоритм Брезенхэма |
|---|---|---|
| Как выбирается следующий пиксель | Используются приращения координат и округление | Используется знак целочисленной ошибки |
| Тип вычислений | Возможны вещественные вычисления | Преимущественно целочисленные вычисления |
| Учет наклона и направления | Нужно согласовать шаги по координатам с наклоном отрезка | Нужно выбрать основную координату и учитывать знак приращений |
| Основное преимущество | Простота описания | Экономичность вычислений при построении растра |
Сравнивайте методы по тому, как они выбирают пиксель и какие вычисления выполняют. Для короткого отрезка оба подхода позволяют понять общий принцип, а преимущество Брезенхэма особенно заметно при построении множества линий.
Нужно выписать пиксели для отрезка с небольшим положительным наклоном. По x он проходит 6 шагов, а по y — 3, поэтому основной координатой будет x. Приращение y на каждый шаг x равно 3/6 = ½, так что вертикальный шаг нужен через один шаг по горизонтали.
Ответ: пиксели отрезка — (1, 2), (2, 2), (3, 3), (4, 3), (5, 4), (6, 4), (7, 5). В варианте алгоритма Брезенхэма конкретный начальный порог ошибки зависит от выбранной договорённости о равенстве расстояний. Здесь приведена равномерная последовательность, которая точно передаёт заданные приращения.
Здесь x убывает, а y возрастает, поэтому нельзя бездумно увеличивать обе координаты. Изменение по y равно 7, а по x — −4; основным направлением будет ось y. Это даёт по одному шагу вверх на каждом этапе, а уменьшение x происходит по мере накопления ошибки.
Ответ: отрезок растеризуется с движением по y вверх и с уменьшением x по знаку приращения. Нельзя менять местами шаги или заставлять обе координаты только возрастать: тогда направление линии будет неверным. При равном расстоянии до двух пикселей алгоритм может выбрать один из них согласно принятому правилу.
Дана точка внутри замкнутой области, из которой нужно выполнить затравочную заливку. Предположим, что контур имеет отдельный цвет, а внутренние пиксели отличаются от него. Алгоритм должен заполнять связные пиксели области и остановиться, когда вокруг останутся только граница или уже обработанные точки.
Ответ: область будет заполнена, если контур замкнут, а принадлежность пикселя области проверяется верно. Обход закончится, когда не останется незаполненных допустимых соседей. Проверка уже закрашенных пикселей нужна, чтобы не обходить одну точку повторно.
Считать, что растеризация — это только округление координат концов отрезка. Такая мысль возникает потому, что концы задают положение линии, но промежуточные пиксели тоже требуется выбрать. Иначе между концами могут появиться пропуски или линия получится неправильной формы. Проверьте себя: выпишите весь путь пикселей, а не только две крайние точки.
Использовать один порядок изменения координат при любом наклоне — значит не учитывать, какая ось меняется сильнее. При крутом отрезке основным направлением становится y, и шагать удобнее именно по этой оси. Ошибку допускают, механически повторяя алгоритм для пологой линии. Проверьте модули Δx и Δy до начала построения.
Игнорировать отрицательные приращения координат — значит потерять направление отрезка. Тогда программа может построить зеркальную линию или сместиться не к той конечной точке. Это часто случается, если в алгоритме оставляют только положительные шаги. Проверьте знаки Δx и Δy и убедитесь, что последние координаты совпадают с концом отрезка.
Запускать заливку без проверки границ и уже обработанных пикселей опасно: она может выйти за контур или снова проходить по тем же точкам. Причина часто в предположении, что одного замкнутого контура достаточно для безопасного обхода. Проверьте, что контур действительно не имеет разрывов, соседние пиксели тестируются на принадлежность области, а закрашенная точка повторно не добавляется в очередь.
Для растеризации нужны координатная плоскость, целые числа, округление и представление изображения как двумерного массива пикселей. Геометрические преобразования меняют положение или форму объекта, а отсечение удаляет его часть за пределами области вывода; после этих операций линию всё равно приходится растеризовать. Поэтому методы построения графических объектов применяются в компьютерной графике, редакторах изображений и визуализации данных.
Почему прямой отрезок на экране выглядит ступенчатым?
Экран состоит из отдельных пикселей, а не из бесконечно малых точек. Поэтому непрерывную линию приходится приближать набором квадратных пикселей, и на наклонных участках их границы образуют ступеньки.
Зачем при растеризации отрезка нужно учитывать его наклон?
Наклон определяет, как быстро меняется одна координата относительно другой. Если двигаться только по неподходящей оси, линия получится с пропусками или заметно отойдёт от идеального отрезка.
Чем алгоритм Брезенхэма отличается от пошагового округления?
При пошаговом округлении вычисляют координаты линии и округляют их до пикселей, иногда используя вещественные числа. Брезенхэм принимает решение по знаку целочисленной ошибки, поэтому обычно требует меньше вычислений.
Как построить отрезок, если его координаты убывают?
Нужно учитывать знак изменения каждой координаты. Выбирают основное направление — ту ось, вдоль которой отрезок изменяется сильнее, — и на каждом шаге увеличивают или уменьшают координаты согласно их знакам.
Почему затравочная заливка может выйти за пределы области?
Так бывает, если контур разомкнут, выбран неверный цвет границы или алгоритм не проверяет, какие пиксели разрешено заполнять. Также нужно ограничивать обработку границами изображения и не обрабатывать один пиксель повторно.
§ 2. Некоторые алгоритмы и методы машинной графики
