注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一路

To find the final symmetry & beauty

 
 
 

日志

 
 
 
 

Computer Graphics note1: Rasterization of Simple Shapes  

2011-06-13 21:11:24|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

    Today, most displaying devices are raster display device. The display panel is formed by rectangle display unit configured in matrix shape. But, things in real word are not formed in matrix points, real things are accurate and continuous. In order to show things of real world on raster display devices, rasterization of shapes should be done and this comes rasterization algorithm. In this short article, I would like to show some basic rasterization algorithm on simple geometric shapes.

  1. Line rasterization algorithms

     

  1. DDA algorithm

DDA represents digital differential analyzer, it is the simplest algorithm for rasterization of lines, this algorithm requires computation of floating point numbers. The idea of this algorithm is simple, considering a line in first quadrant of Cartesian coordinate system from () to () shown in the following figure.

Compute and , make the larger to be variable length.

Let

Each time increase x by and increase y by , then round x and y to nearest integer and set the pixel. When reached the end point, algorithm terminates.

As the pixel (0,0) covers points (0,0) and (1,1), the center of pixel (0,0) is (0.5,0.5). There is a 0.5 shift on each pixel's real center. So, the first pixel is not (round(),round()), it is shifted by 0.5 to be (round(+0.5),round(+0.5)). This algorithm is simple, but on some devices, there is no floating point instructions and should use integer instructions to simulate floating point arithmetic. This DDA algorithm hurts performances on these devices and rasterization algorithms are called so often. Bresenham algorithm is tricky designed to be both effective and eliminate using floating point computation.

    (2)Bresenham algorithm

    The lines' increasing rate on x and y direction depends on . Bresenham uses this value to make prediction if line should step one step in y direction if line steps in x direction in one step.

Assuming , if this is not the case, just inverse the direction to run the algorithm.

First, set value e=.

Each time x increases by one, add to e, if e>0, y increase one and subtract e by one, else y and e don't change.

Just using sign of e to indicate whether y should increase by one. Multiply the above value by to scale all values, then all values are now become integer. This algorithm is very efficient and elegant.

  评论这张
 
阅读(648)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017