CPU+FPGA实现边标志填充算法（一）

发表于 2013/11/18 22:10:00 阅读（4628）

一、概述

该算法属于边标志填充算法的改进算法，利用软件写标记，利用硬件读取标记，配合像素颜色值，实现规则图形的填充。本笔记，是整个算法的实现思路，从简单的填充开始，对算法进行分析和改善，如不能进一步改善，则分析算法的应用需要哪些前提条件。

二、笔记

第1步：矩形色块填充，色块内部无其他图形。

较简单，略过不述。

第2步：矩形色块填充，色块内部可以有图形。

时序图为：

效果图为：

将中间部分放大：

应用限制：

1）一般来说，填充的色块内部有图形时，最好能保证图形完全位于色块内部，如同上图中的“ChinaAET”，在这种情况下不会有任何问题；

2）相对不理想一点的情况是图形与色块有交点，但是不影响填充标记（开始和结束标记），上图中也出现了这种情况，有部分线段，与色块有交集，但是并没有覆盖标记位；

3）更加糟糕的情形是图形与色块有交集，且有可能将标记位覆盖。这种情况处理起来比较费劲，标记位的描绘是由CPU完成的，当先绘制标记位，后绘制图形的时候，标记会被覆盖。该情况，如下图所示。

参照时序图，可以看出，当标记被覆盖，FPGA无法检测到结束标记，就会出现一直填充，直到检测到下一个结束标记为止。挽救的办法是，先绘制图形，绘制标记时，先读取原像素点的颜色，然后在原颜色的基础上加上标记。由于读显存耗时较大，这个解决方法是以牺牲效率为前提的。解决后的效果图如下图所示。

4）最糟糕的情况：开始标记出现问题。

当开始标记被覆盖时，这种填充机制就出现了问题：当后绘制图形时，开始标记被覆盖，无法检测到开始标记；当先绘制图形时，交点处的颜色被覆盖成填充的颜色，出现小的瑕疵。我现在是将标记位和像素颜色组合成32bits的数据，写入显存的，所以存在覆盖的现象。要解决这个问题，需要将像素的颜色信息和标记位分离开来，不能将flag+RGB整体写入显存。但是，这样一来，对于32位CPU而言，操作效率就会降低，头大啊……

第3步，嵌套填充

如下图所示，在绿色色块内部，需要进行蓝色色块的填充，姑且将这种情况成为“嵌套填充”。