Растеризация на отсечка

Често се налага да се изчертават на екрана основни геометрични обекти като отсечки, части от окръжност/елипса. Както знаете обаче мониторът е правоъгълна таблица от пиксели, като всеки пиксел свети в определен цвят. Естествено възниква проблемът за изчертаване на отсечка/окръжност със зададени координати1 върху тази правоъгълна таблица. Т.е трябва да определим кои точно пиксели трябва да светят и евентуално колко силно. Проблемът не е сложен за решаване, но бързодействието е от изключително голяма важност. В тази глава ще разгледаме основните алгоритми за растеризация на отсечка, окръжност и елипса.

Отсечка

Най-често се налага изобразяването на отсечки върху растера. Ще разгледаме алгоритъма на Брезенхам (на английски Bresenham). Като за начало да видим какво точно ще правим:

Ако си представим отсечката като безкрайно тънка линия, която минава през 2 точки от екрана, то трябва да `светнем` квадратчетата (пикселите) през които тази отсечка минава. За удобство ще приемем, че отсечката върви от югозапад (долу-ляво) до североизток (горе-дясно) и ъгъла който тя сключва с хоризонталата e по-малък от 45 градуса (т.е отсечката е по-"легнала"). Всички останали случай са еквивалентни на този с подходящо ротиране на координатната система. С тези ограничения задачата ни става наистина много лесна - ако си представим, че в момента сме в даден пиксел и се чудим в кой следващ пиксел да отидем имаме само 2 възможности - надясно или по диагонал нагоре и надясно:

На всяка стъпка от алгоритъма, трябва да знаем текущото квадратче, което сме светнали както и грешката, която показва колко далеч е минала линията от квадратчето. За център на квадратчето ще приемем долния му ляв ъгъл. Ще разглеждаме също пресечните точки на линията (отсечката) с вертикалните линии на решетката. Спрямо тези точно пресечни точки (отбелязани с червено на фигурата) избираме най-близката точка от решетката по тази вертикална линия (т.е най близкия долен ляв ъгъл на квадрат със същия x) - на фигурата е отбелязано с лилаво мерниче. След като изберем долните леви ъгли просто светваме съответните им квадратчета (т.е квадратчето, което стои горе вдясно спрямо точката).

Имаме дадени 2та края на отсечката - нека това са (X1, Y1), (X2, Y2). Тогава  ΔX = X1 - X2, ΔY = Y1 - Y2. Нека за улеснение приемем че ΔX > ΔY т.е линията има по-малък наклон от π/4. Ако си отбележим наклона с α, то tgα = ΔX/ΔY = m. Това е първата много важна характеристика на линията (за единица дължина по X колко пиксела нагоре (по Y) се изкачва линията.

Алгоритъм на Брезенхам:

  • Във всеки момент се знае кой е текущият пиксел, в който се намираме - Xc,Yc както и стойността на текущата грешка - E, т.е колко далече минава истинската линия от квадратчето. Ще приемем, че координатите на квадратчето са координатите на долния му десен ъгъл и ще се интересуваме повече от самото ъгълче, отколкото от целия квадрат.
  • От всеки пиксел можем да се движим или надясно (т.е увеличаваме X ) или по диагонал (т.е увеличаваме X и Y). Това зависи от грешката - тя се изчислява като към старата грешка прибавим m. Т.е Enew = Eold + m. Тъй като грешката е разстоянието от долния десен ъгъл на пиксела до пресечната точка на истинската отсечка с вертикалната права, минаваща над този долен десен ъгъл (на картинката отбелязано със синьо), то за да получим следващата грешка прибавяме точно разстоянието, което отсечката ще "изкачи" за един пиксел. Тъй като искаме точката (долния десен ъгъл) да бъде най-близо до пресечната точка на отсечката с вертикалната права, то ако грешката е повече от 1/2, избираме горната точка, иначе - долната.

Тази лекция е лицензирана под Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License .