光栅图形区域填充算法-外文翻译.rar

包括英文原文和中文翻译，其中中文翻译11000字；英文 含详细作者及出处信息

　
高效利用空间的光栅图形区域填充

Dominik Henrich
实时计算机系统和机器人技术学会
德国卡尔斯鲁厄大学，凯撒街12号，卡尔斯鲁厄D-76128



摘要
　　　本文提出了在光栅图形学中被定义边界的区域填充算法。此算法仅要求一个固定大小的工作内存。这种方法是基于所谓的使用内部连通区域内点的“种子算法”。本文中除了附加启发式加速算法，基本算法也被描述和验证。对于不同类别的区域，算法的时间复杂度将通过实验结果进行比较。
　　　关键字:种子填充,图形处理器,帧缓冲操作,算法显示,光栅图形学

1 简介
　　　计算机图形区域填充的问题主要发生在交互式系统。例如，绘图应用软件的用户用鼠标点击图画的区域时，应用软件立即被要求填充这个区域。由于这个领域对速度的高要求，越来越多的带有特殊图形处理的解决方案已被列入考虑范围。由于协处理器的芯片区域是有限的，算法不用或只用协处理器提供的局部工作内存有特殊要求。这里，我们描述并且验证以解决这种有限性的基本算法和附加启发式试探索法。
　　　填充的区域可以用不同的方式来描述。例如，多边形的几条边可以分隔出这个区域的边界部分(Little和Heuft 1979年, Brassel和Fegeas 1979年)。另一种情况是用一组连续的邻接象素来描述区域。如果定义区域的像素是着同一颜色，称之为内点表示。否则，边界像素着同一颜色时，这个区域采用的是边界表示。这两种情况的其它像素点的着色都是随意的。本文我们集中介绍边界表示区域，内点表示区域的工作原理是类似的。
　　　由于是运用像素来定义区域，大部分的填充算法都有一个种子点作为输入。种子点是区域内部的一个像素。所谓的种子填充算法就是从种子点出发并通过某个算法扩展到相邻近的像素。只有区域内部的像素才能够变成填充色。由于这些像素从种子出发能达到而又不穿过边界，因此，它们是 “连通”到种子的。
　　　考虑到内存的使用，填充算法可以细分为两个小组。在一个小组，附加的“工作面”除帧缓存器之外，都被用来填充。填充后，它被复制到帧缓存器。在中间可能会用到绘图模板（Ackland 和Weste 1981年, Dunlavey1983年, Tang和 Lien 1988年)。另一组使用了一个数据结构，大多数情况下，它是一个填充区域被划分时存放一些内在像素的堆栈。在之后的步骤中，这些像素中每一个都被用作新的种子点来填充一个分隔的区域（Newman和Sproull 1973年, Liebermann1978年,Smith 1979年,Shani 1980年,Pavlidis 1982年）。通常情况，这两组的方法都需要除帧缓存器外的工作内存。内存的使用数量根据区域的大小来决定（随区域复杂度而增长），且不是恒定不变的。