（水利水电工程专业论文）嵌入式图形系统若干快速算法研究.pdf

华中科技大学硕士学位论文 摘要 在电力故障抢修车车载g i s 设备开发中，要求快速地描画地理图形信息，提出了 快速图形生成算法的研究需要。 本文研究了计算机图形学基础图形生成的快速算法。针对嵌入式图形系统硬件配 置低，图形用途的非专业性的特点，本文提出和研究了小计算量的快速图形生成算法。 主要有：直线的“两点- 对称”b r e s e i l h 锄生成算法、l i a i l g b a r ：出y 裁剪的整数化方法、 粗直线的快速生成算法，还提出了道路轮廓的描画方法。用于嵌入式g i s 软件描画地 理图形信息。并对实现的算法进行了对比测试，得到了比较满意的结果。 “两点对称”b r c s e n h 锄生成算法采用两点原理和对称原理相结合，可以通过一 次计算生成2 到4 个点，与单点b r e s e i l l l 锄算法相比加速比为2 4 6 8 。 直线的矩形裁剪算法采用l i 锄g b 趴汰y 的参数化裁剪算法，对其做了整数化实现。 这不仅降低了对硬件的要求，还使裁剪速度加速比提高到2 2 5 6 。 本文的粗线快速生成算法在“两点对称”直线段生成算法的基础上采用“点转化 扫描线法”，通过查宽度增量表的方法来确定不同斜率和线宽时的扫描线长，从而运 算量非常小。针对该算法特点，提出了“等腰直角三角形”粗线端头画法，粗折线的 拐角连接效果比较好。算法速度可以达到微软g d i 算法的4 1 8 倍左右。 上述算法作为图形用户界面( g u i ) 的基本图形引擎，是嵌入图形系统开发的重 要部分，本文还简单涉及了g u i 的开发。 关键词：嵌入式系统；计算机图形学；算法；直线生成；直线裁剪：粗线生成 一 i 华中科技大学硕士学位论文 一= # = = = = = ；= i 目= ；= = 目= = 2 = i e ； = 。= = ；t = j e ； i m p o n a n tf o rt h ee m b e d d e dg m 蛳cs y s t e md c v e l o p m e n t t h c 恤s i ss i m p l yr e f e r r i n gt o 也e g u id e v e l o p m e n ti nt l 坞e n d k e yw o r d s ：e m b e d d e ds y s t c m ；c o m p u t l 琵伊印h i c s ；a i g o r i t h r n s ；l i n eg c n e 矾o n ；l i n e c l i p p i n g ；t h i c k - l i n eg e n e r a t i o n ； 华中科技大学硕士学位论文 1 1 应用背景及研究意义 1绪论 本文的课题来源于“l b s ( l o c a t i o nb a s e ds e r v i c e ) 软件平台开发”项目，主 要用于电力抢修车车载移动g i s 设备，在抢修车的高速行进中需要快速地进行地理位 置导航。为了满足实时性和快速性要求，在导航过程中需要频繁调用基础图形生成函 数来快速的描画地理图形，因此高效的基础图形生成算法，即计算机图形学基础算法 的软件加速研究是该软件平台研究的关键之一。该软件平台还可用于其它移动导航、 移动地理信息定位设备。还可以用于基于g i s 技术和定位技术的能源综合利用、数字 流域监控、水利工程建设、灾害防治监控及抗洪救灾指挥决策系统。 1 1 1 电力抢修与电力g i s 随着电力用户的逐年增加，保障用户的正常服务是提供优质服务的基础。由此， 电力故障抢修工作成了能否提供优质服务的关键因素。对于客户的报修申告，抢修车 辆及人员能否在承诺的时限内以最快的速度到达现场直接关系到客户对电业部门的 满意度。为了加强电力抢修车辆管理，提高车辆运行效率，加强运行作业调度，在市 级电业局建立电力抢修车辆g p s 监控调度系统很重要。 结合g p s 、g s m 、g i s 等技术，利用装在各受控电力抢修车辆上的移动车载设备， 将电力客户的报修信息、车辆调度信息、卫星定位信息等通过g s m 网络的短信息平台 在电力抢修车辆和电力系统控制总台之间双向传递，实现对抢修车的状态监视、有效 调度、信息查询等功能，并有效提高客户报修的响应速度，降低车辆到达现场的时间， 加强了对车辆的管理。 电力g i s 是将电力企业的电力设备、变电站、输配电网络、电力用户与电力负荷 和生产及管理等核心业务连接形成电力信息化的生产管理的综合信息系统。它提供的 电力设备设施信息、电网运行状态信息、电力技术信息、生产管理信息、电力市场信 息与山川、河流、地势、城镇、公路街道、楼群，以及气象、水文、地质、资源等自 华中科技大学硕士学位论文 然环境信息集中于统一系统中。通过g i s 可查询有关数据、图片、图象、地图、技术 资料、管理知识等。 电力故障抢修车辆为了能够及时到达故障现场，通常以很高的速度运行，其车载 导航仪要求实时地显示导航地图信息，这时需要频繁调用基础图形生成函数来进行地 理图形描画，因此研究快速的图形生成算法很重要。 1 1 2 基于位置的服务( l b s ) l b s 技术是一种整合了互联网、无线移动定位和地理信息系统( g i s ) 技术的基于 空间位置的信息服务，顾名思义，可以理解为与地理位置相关的信息服务。在各种管 理和决策行为所需要的信息中，大约有8 0 左右的信息属于具有空间位置特性的地理 信息。无线定位技术和g i s 技术相结合就可以回答这方面的问题，一般是通过嵌入式 用户终端的图形显示系统来告诉用户所需的地理位置信息。 随着计算机技术、无线通讯技术、定位技术( p o s i t i o n i n g ) ，i n t e r n e t 技术及移 动计算( i o b i l ec o m p u t i n g ) 技术的飞速发展，由移动通信和互联网的融合而形成的移 动环球网( m o b i l ew e b ) 使用户在任何地点、任何时间都能通过移动终端中获取各种 信息服务，其中包括与移动终端用户所在地理位置相关的服务。搜索移动设备的地理 位置，并可以提供随时随地传送基于此空间位置相关的信息服务，移动定位技术是无 线定位技术和移动通信技术的结合。这就是l b s 技术，它提供了未来空间信息服务和 移动定位服务的蓝图，即当用户与现实世界的一个模型交互时，在不同时间、不同地 点，这个模型会动态的向不同用户提供不同的信息服务【l 】。 l b s 系统，例如，美国的e 9 1 1 ( 紧急求援) 服务，它能够定位呼叫者以提供用户及 时救援，日本n t td o c o m o 的卜a r e a 服务，提供诸如天气预报、地图、交通、当地指 南等服务，基于p h s 网络的p d o c o 寻人服务，包括地图功能、通信服务、交通信息、 天气预报、紧急信息等。在韩国s k t 和k t f 均推出了基于a g p s 的位置服务，提供诸 如位置导航、找朋友、附近医院、餐厅等。在新加坡在2 0 0 1 年3 月推出了c e l l 一i d 的位置服务，包括：公共设施菜单、银行服务、休闲娱乐、商店、房产、交通等。由 于位置的服务在全球范围内的使用，将使无线用户更愿意使用无线手机来接受移动通 华中科技大学硕士学位论文 信服务。这种需要既是移动通讯增长的要求又是数字化城市建设的要求，蕴含着极有 潜力的增长空间。 因此，进行l b s 相关技术开发是非常迫切和必要的，本课题中l b s 软件开发平台 的目的在于，开发一套运行于客户端移动设备的设备无关软件，来支持人机交互的数 字地图服务。l b s 软件平台开发的一项重要内容就是在用户终端进行图形显示，特别 是地理图形信息显示。市场上的嵌入g i s 设备几乎都存在地理图形描画速度慢的问题， 快速高效的g d i 图形库无疑会极大的改善l b s 软件的系统性能和效率，提高用户满意 度和产品竞争力。本文就是致力于嵌入式l b s 设备快速g d i 图形库的基础算法研究。 本文着重研究了计算机图形学的若干基础算 x 华中科技大学藕誓蚕褥潞躐 麦蘑引筻嚣珏爱。融爵扎曼驯甄型8 博一嘲7 亭丑 雨委嚣；阱醵习“j ；冀：塞琶雾嚣雾鬟肚蟪研；曩导兰 群藕赫| i _ ；蟛彬楮霎赢盏胃像罢! 雒矗鹊羁麓辫嚣鲚廿，萏翳；液装巍割蓄丰卡东 辑j 1 p 街碇同戴醑所示塑磊黍西蠹。酽未i 鬯慌博赢岩 38x 华中科技大学硕士学位论文 2 图形显示系统 计算机图形系统由硬设备及相应的软件两部分组成，从功能上来说，有计算、存 储、输入、输出、对话五方面的基本功能，图形显示系统可以兼具部分或所有的这些 基本功能。其软件的开发依赖于硬件并遵循相关图形标准。本课题所作的工作属于图 形系统显示输出的计算功能软件部分，本节论述了与基础图形生成算法密切相关的硬 件、软件环境。 2 1 硬件 2 1 1 光栅扫描显示器 目前普遍使用的显示器是光栅扫描显示器。在7 0 年代出现的光栅扫描显示器极大 地推动了计算机图形学的发展，由于光栅扫描显示的许多优点，至今仍然是图形显示 的主要方式，图形工作站、微型计算机、嵌入式系统都采用这种光栅扫描显示器，如 c r t 、等离子板、l c d 、电予发光板等。嵌入式显示系统一般采用l c d 显示器。这种基 于栅格扫描方式的显示器对应了一类图形算法( r a s t c rg r a p h i c s ) ，即像素级的图形绘 制算法( 或称点式生成算法) 。这类算法生成的曲线是很细致的并且误差小，可以说这 类算法充分利用了光栅显示器的特点。本课题所研究的算法就是基于光栅扫描显示器 的。 光栅扫描显示器的显示屏是由许多 x 华中科技大学硕士学位论文 2 1 2 图形处理器 图2 1 光栅扫描显示器上的直线显示 因为计算机图形生成需要相当的计算量，从而对硬件配置的要求也相当高，并且 计算机图形学的发展很大程度上取决于计算机硬件的发展。然而嵌入系统的硬件配置 一般是比较低的，所以有必要存在基于硬件的图形生成方法，即图形芯片，有2 d 、3 d 的，它们主要面对专业的图形市场，价格比较昂贵。对于非专业图形处理的移动终 端来说，为了降低成本，用软件加速来实现快速的图形生成仍然是非常必要的。 还有一些图形处理硬件是图形加速卡、显卡等，这些诸多的技术都是希望在成本 与性能、软件和硬件之间取得一个最佳平衡。对于一个在低端的嵌入系统上运行的软 件平台来说，要考虑到最为低端的硬件配置情况，即开发不依赖于硬件加速的软件快 速图形生成算法，并且这对计算机图形学的基础算法研究会有一定的贡献。 2 2 软件 计算机图形系统的软件可以自顶向下分为三个层次，图形用户界面( g u i ) 、基 本图形引擎( g d i ) 、图形硬件设备驱动，各个层次的开发要遵循一定的软件标准，以 提高软件的可移植性和兼容性。 2 2 1 图形系统软件标准 随着计算机图形显示器从专用的图形输出设备发展为标准化的“人一机，通信接 口，就给图形显示软件提出了一个要求，要求它由低层次的与设备有关的软件包转变 为高层次的与设备无关的软件包。这样可以使图形软件包在不同的计算机和图形设备 之间进行移植a 如果能够将图形软件包的使用方法标准化，则应用软件的移植将更方 8 华中科技大学硕士学位论文 z 缓冲技术：是在每个象素上附加一个2 4 位或4 8 位的表示z 值的缓冲存储器，这对 曲线曲面的消隐，亮度随度变化的处理，提高图形处理效率等都具有重要作用。( 4 ) 光源：光源的强度、颜色、物体的反方向、镜面反射系数、漫反射系数等都影响到一 定光源照射下物体最终的显示效果。g l 提供了充分的光源处理能力，使用户能得到 非常生动的图象。( 5 ) g l 和x w i n d o w ：g l 既可单独运行，也可在x - w i n d o w 环 境下运行，进而可支持网络上的用户。 2 2 2 嵌入式图形显示的驱动方式 帧缓冲( f r a i i l e b u 虢r ) 是嵌入式图形系统普遍使用的图形显示驱动方式。它允许 用户直接向显存描画，是一种简单、高效的显示方式。以l i n u x 操作系统为例来说明 它的应用，在l i n u x 2 2 x 以后加入了f r a m e b u f f e r 图形显示驱动模式，在l i n u x 系统中 f r 锄e b u f f e r 是一个抽象的图形设备，设备节点是d e v f b + 。它可以使应用程序不通过 x - w i n d o w 系统而直接访问图形显示硬件设备，这意昧着可以不使用庞大的x w i n d o w 系统而进 x 华中科技大学硕士学位论文 p t i + l t n 1， 一 s m ，一1 rr 名i + 一i = t q ) s i 图3 1b r e s e n h a m 单点画线 b r e s e i l l 锄方法假设被描画的直线段在二维坐标平面中从始点( x l ，y 1 ) 到终点 ( x 2 ，y 2 ) ，假设x 1 0 ，可以用d x ( s t ) 的正、负来知道s 、t 的大小关系，从而作为选择下一 个像素点s j 和t i 的标准。事实上，由( 3 2 ) 式我们还知道，d x ( s t ) 必然是一个整 数值，因为整数乘、加、减的结果还是整数，这就可以免去对浮点运算的要求。若令 d x ( s t ) = d i ，则d j 就是第i 步的误差因子，当d i = 0 时，s = t ，要选择t l 点，否则 选择s i 点。可得： d i = 2 ( r + d y q d x ) + 2 d y d x 将r = x i i ，q = y i 1 代入上式，得： t3 华中科技大学硕士学位论文 incrl=2+d e = i n c r l 一f i n c r 2 = e 一( + d i 1 一d i + x = x l j y = y 1 ； w h i l e( p r i o s e t p i x e l ( i ff esec l e l s e # * s e c c j + d i + 1 = d 1 + 2 d y ， s e c s i g n( p r i s i g nd # # p r i c ) s e c s i g n( p r i s i g nd # # p r i c ) 2 ( d y d x ) ，i n c r 2 = 2 ( d y p r i c o n dp r i c # * 2 ) c o l o r ，x ，y ) ； c o n do ) = 2 d y + v o i dd o l i n ec c d c + p d c ，i n tx 1 ，i n ty 1 ， i n tx 2 ，i n ty 2 ，c o l o r r e fc 。l o r i n td x = x 2 一x l j i n td y = y 2 一y l j i n ti n c r l ，i n c r 27 i n t 。，y ； i n te j i f ( d x = o ) i f ( d y ；0 ) i f ( d x = d y ) +( x 1 = x 2 ) ( y l = d y )+ d 钆l i n e ( + ，x ， = ) ； e l s ef + ( x 1 = x 2 ) 5 & ( y 1 。y 2 ) ( d x 。一d y ) ( + ( x l ；) ； 、 e l s ef i f ( d y = 0 ) i f ( 一d x = d y )f + x l x 2 ) 5 y 1 = d y ) + d o - l i n e ( 一， x ， 2 ，+ ，y ， 2 ) j ) e l s ef + c x l x 2 ) ( y 1 = y 2 ) ( d x d y ) + d o l i n e ( + ，y ， x 2 ) ( y 1 y 2 ) ( d x = d y ) + d o _ l i n e ( 一，x ， 一。，y ， x 2 ) ( y 1 y 2 ) ( d x = ，一，x ， 1 、 p l 1 2h 0 t i “ t， t ，一1 s i + l = 融q ) s i 侧p 靠持l h l l 各，h 幡啪2( h 嫩r 鹇 ( d p l t k m 图3 5 两点法在斜率区间 0 ，1 中点的选择 我们知道b r e s e i l l l 锄算法设计的核心工作是计算误差因子的初始值和迭代公式， 下面我们将导出两点b r e s e n h 锄生成法的误差迭代公式，也就是点的生成判据问题。 3 4 1 在斜率区间 0 ，1 2 】中的两点算法 由图3 3 可知，在斜率区间 o ，1 2 中点的排列模式仅有图3 5 中的d 、c 、b 三 种情形，图3 5 中的( c ) pa _ 吮m 3 表示出了在斜率区间 0 ，1 2 中点的选择情况，设 p i 1 是已选定的离直线最近的像素，我们要先计算其后第二个像素是s i + l 还是t i + l ，然 后再判断其后第一个像素是s i 还是t j 。因为若选择了s i + l ，那么不用计算一定要选择 s j ，若选择了t + 1 ，那么在下面我们还要构造一个误差因子c 来对s i 还是t i 进行选择。 用3 3 节中的方法，不难得出对点s i + i 和t i + l 的进行选择的误差因子d i ，及d i + 2 和d i 的差值迭代公式。设k i 的坐标为( r ，q ) ，s i + l 的坐标为( r + 2 ，q ) ，t i + i 的坐标 为( r + 2 ，q + 1 ) ，把即将生成的直线( x o ，y o ) 一( x l ，y 1 ) 简化为( o ，o ) 一( d x ， 2 0 华中科技大学硕士学位论文 然而在第i + 2 个像素选择s i + l 时，第i + 1 个像素还是需要判断一下的，我们不妨考虑 ( 3 6 ) 式减去3 2 节中的( 3 - 2 ) 式得到下式： ( m n ) d ) 【一( s t ) d x = 2 d y = c ( 3 - 1 0 ) ( m n ) d x 一2 d y = ( s t ) d x ( 3 - 1 1 ) 因为d x 0 ，当( s t ) d x 2 ，迭代循环计算一次可画出4 个点，除4 取整； 中间接点个数：c x t r a s = ( d x 1 ) & 3 ，除4 取余： 当前点后续第一个点的判据值： 华中科技大学硕士学位论文 c = 2 d y( m 2 1 2 ) 当前点后续第二个点的判据d i 迭代公式： d + l =d i + 4 d y 2 d x = d i + i r l c r 2 ， ( d i = o ，m 1 2 ) d i + l =d i + 4 d y = d i + i n c r l ， ( d i = 1 2 ) d + 1 =d i + 4 d y 4 d x =d i + i n c r l ，( d l = l 2 ) d i 的初值d l ： d l = 4 d y d x( m = 1 2 ) 在斜率大于l 时只要把上面迭代变量中d x 与d y 对换即可，而对应的画点模式则相应 的按照图3 3 所示的情况调整，分别是m o d e l 对应m o d e 7 、m o d e 2 对应m o d e 5 、m o d e 3 对应m o d e 6 、m o d e 4 不变，替换一下即可。 直线的中间接点绘制：在主循环结束后，直线的中间可能有e x n 部个接头点需要 单独计算，计算方法仍然是根据主循环结束时的误差因子d l 。m l 与0 和c 的关系来判 断后续两个点的坐标位置。当e x n 邪= 1 时，根据d l 。叭l 大于o 与否来判断这个点的位 置。当e x t r a s - 2 时，根据d l e 唱h 1 与0 的关系判断后续第一个点的位置，根据d l c n g 与c 的大小关系来判断后续第二个点的位置。当e x n 邪= 3 ，与e x t m s - 2 时方法同样画 两个点然后再对称的画1 个对称位置点就可以了。 3 5 2 算法实现的伪代码 2 5 华中科技大学硕士学位论文 表3 1 算法功能接口描述 功能描述利用两点和对称原理来画一条直线 接口与属性入口参数：指定的绘图区指针p g c 、起点( x o ，y o ) ，终点( x 1 ，y i ) ， 颜色d ix 返川值：_ 尢 v ( ，ldt w o s t e p l lne ( g c + p g c ，i n tx 0 ，i n ty 0 ，ln lx 1 n y i ，c o l ( ) r r e fp i x ) 数据结构把坐标空间的叫个象限按照斜率2 ( 1 2 ) 划分为16 个卦限时，n - 某卦 与算法限内，直线的点阵分布仅有三种情况，叫以通过模式判断( 比较) 米一 次生成两个点。在汁算出直线始端当前点的两个后趋点后，按照州趋规 则画出终端附近对称的两个后趋点。 补充说明伪代码中的变量参考35l 节，l 画点模式m o d e l m o d e 7 参考蹦33 v 0 1 a l 。w o s t e p l l n e ( g c p 6 c ，i n tx u i n ty u ，i n tx l ，i n ty l ，c o l o r r e fp i x 【 i n tdy=y1一yo f i n td x = x 1 一x o ； i n ts t e p x ， 8 t e p y ； i f( d y o ) d y = 一d y ；s t e p y = 一1 ；) e l s es t e p y = 1 ， ) i f( d x d y ) l e n g t h ；( d x - extras= cd x i n c r 2 一 ( d y i f( i n c r 2 o ) c ；d y 2 j + l e n g t h = d x 4 + 3 ；+ e x tr a s = d x 4+ 一 ( d x 1 ) ； + i n c r 2 = 4 d y 一2 d x + + s l o p e =【0 ，1 2 】 + + c = 2 d y + i n c r l 。c ( ( 1 j +i n cr l = 4 d y + 2 6 d ： i n cr 1 一d x + d l24 d y d x f 。r(i = o ； i ( 1 e n q t h fi + + ) x o + ；s t e p x ； + e a c hl 。pd 。o n es t e pb y 。+ x ls t e p x ； +s y m m e tr i cs t e p + i f(d(o)t d r a wm o d e l ； d r a wm 0 d e ls y m m e tr i c l y ； d + = i n c r l i ) e l s e i ffd 2 )s e t p i x e l ( p i x ， x 1一= s t e p x ，y 1 ) 7 e lse i f(d 1 ) s e t p i x e l ( p i x tx 0 + = s t e p x ty o + 。s t e p y ) ； i f( e x t r a s2 )s e t p i x e l ( p i x ， x l一=s 七e p x ， y 1 ) ； ) e l s et s e t p i x e l ( p i x ， x o+ = s t e p x ， y 0 + 。 s t e p y ) j i f( e x t r a s1 )s e t p i x e l ( p i x ， x o+ = s t e p 。，y 0 ) ； i f( e x tr a s 2 ) s e t p i x e l ( p i x ，x l 一= s t e p x ， y 1 5 s t e p y ) ； ) ) e lse+ l i n es l o p e ；【1 2 ，1 】 + c=fd y d x ) ( 1 ； +c = 2 ( d y d x )+ 2 7 i n crl；c0)( + d r a we x t r ap o i n t so fm 。d e4 + s e tp i x e l ( p i x x o 十=s t e p x ， y 0 +2 s t e p y ) j i f( e x t r a s1 )s e t p i x e l ( p i x ， x o+ = s t e p x ， y o +2 s t e p y ) j i f( e x t r a s2 )s e t p i x e lc p i x ， x 1 一； s t e p x ，y 1 2 s t e p y ) ； ) e l s e i i d 1 )s e t p i x e l ( p i x ， x 0 + = s t e p x ，y 0 + ；s t e p y l ； i f ( e x t r a s2 )s e t p i x e l ( p i x ， x l 一=s t e p x ， y 1 ) j l e ls e +d r a we x t r ap o i n t s。fm o d e 3 + s e t p i x e lc p i x ，x o+=s t e p x ， y 0 + ；8 t e p y ) ； i f( e x t r a s1 )s e t p i x e l ( p i x ，x o + ；s t e p “，y 0 ) ， i f( e x tras 2 )( i f(dc) s e t p i x e l ( p i x ， x 1 一= s t e p x ，y 1 一= s t e p y ) j e l s e s e t p i x e l ( p i x ， x 1 一；s t e p x ， y 1 ) ， + i fd ct h ep o i n ts h o u l db ec o n s i s t e n t l ya c c o r d i n gt h ed r a wo f ”i f ( e x t ras 1 )s e t p i x e l ( p i x ，x o + = s t e p x ，y 0 ) ”s l o p e = l 2 d 2c + 2 8 华中科技大学硕士学位论文 4 裁剪算法研究 当需要显示地图的某一部分时，要设定一个裁剪窗口，使用裁剪算法，窗口内的 图形得以显示，而窗外的图形部分则被裁剪掉。图形裁剪是计算机图形学的最基本内 容之一，它在消除隐藏线、隐藏面及真实感显示等算法中也是有用的工具。在显示地 图窗口时，矩形窗口的直线裁剪用的最为频繁，因此，矩形窗口直线裁剪算法的效率 是嵌入式地理图形系统性能的关键。 4 1 绪论 矩形窗口的直线裁剪算法是研究最为深入的一类算法，其中经典的算法有： s u m e r l a n d c o h e n 算法、中点分割算法、l i a n 乎b a r s k y 算法【”j 及n i c h o l l l e e n i c h o n 算 法f 1 4 等，这些算法几乎都用到了浮点运算。m d o 玎【1 5 】对现有的一些直线裁剪算法进行 了整数化实现，这样可以不用浮点运算，从而提高了算法的执行速度。由于 l i a i l g - b a r s k y 的算法比较快速，还可以方便的扩展到三维、四维裁剪。但该算法对我 们的应用来说存在两个问题，首先，在低档的嵌入系统中浮点运算会使裁剪速度变慢， 另外浮点运算求出的直线端点坐标在取整时有误差，该误差可能会使被裁剪线段端点 的某个像素画到裁剪窗口之外，本文在对l i a n g 。b a r s k y 算法整数化改造的同时亦提出 了出界误差的解决办法，可以在裁剪后图块拼接时体现出无缝连续性。本文提出了一 种非常简单实用的l i 觚g b 卸蚂，算法的整数化方法。 4 2 l i a n g b a r s k y 参数化裁剪算法 直线矩形裁剪的过程主要是判断被裁剪线段与裁剪窗口的位置关系，如果被裁剪 线段在裁剪窗口内有可视部分，那么截取这一部分。主要是计算可视部分及与窗口边 界的交点。在l i a i l g - b a r s k y 裁剪算法中，被裁剪的线段以参数化的形式表示，这样， 可以推导出一组表示剪切区域内外的条件表达式。这些表达式有相同的形式，可以重 写它们，把裁剪问题简化为最大最小问题。该算法的一个优点是可以快速的舍弃可 视区域之外的线段。 3 0 华中科技大学硕士学位论文 图4 卜a 可以简单的说明l i a i l g b a r s k y 算法的基本思想，其中，被裁剪的线段为 p 卜 p 2 ，裁剪矩形边界延长线为左边x - x l 、右边为x = ) ( r 、上边为y ；y t 、下边y = y b ， 线段p 1 p 2 与四条边界延长线的交点为a 、b 、c 、d 。从a 、b 和p l 三点中求出最 靠近p 2 的点( p 1 ) ，从c 、d 和p 2 三点中求出最靠近p l 的点( c ) ，则p 卜 c 就p 卜 p 2 线段上的可见部分。 详细的说，如果p 1 和p 2 的坐标分别为( x l ，y 1 ) 、( x 2 ，y 2 ) 。 线段p 卜 p 2 的参数 方程形式为： x = x 1 + u x ，其中x = x 2 一x 1 ，u o ，1 y = y 1 + u y ，其中y = y 2 一y 1 ，u o ，1 】 ( 4 1 ) 当上式中的参数u 1 时，参数方程确定的点( x ，y ) 在该直线段的延长线上。 如果按参数化形式写出线段p 卜 p 2 在图4 1 - a 情况下的裁剪条件，那么参数u 需 要同时满足： x l 工l + “缸x r ，y b y 1 + “缸y t( 4 2 ) ( 4 2 ) 还可以表示为： a l n v l s 1 b 图4 1l i a n g b a r s k y 算法原理 v i s a b l es i d e i m r i s a b l e s i d e u p k q k( 4 3 ) 其中，k