Nano-X图形引擎分析及其优化

Nano-X图形引擎分析及其优化
刘峥嵘  
MicroWindows是一个开放源码的嵌入式GUI软件，目的是把图形视窗环境引入到运行Linux的小型设备和平台上。作为X Window系统的替代品，MicroWindows可以用更少的RAM和文件存储空间（100KB～600KB）提供相似的功能，允许设计者轻松加入各种显示设备、鼠标、触摸屏和键盘等；可移植性非常好，可用C语言实现；支持Intel 16位/32位CPU、MIPS R4000以及基于ARM内核的处理器芯片。由于和微软的windows注册商标存在冲突，从2005年月起，MicroWindows改名为Nano-X。
     作为一个嵌入式的GUI，Nano-X因其体积小，定制性好的优点而在嵌入式领域得到了广泛的应用。但同时，一些专业开发者和竞争对手也对它的图形引擎提出了诸多批评，认为它过于原始，算法过于低效。下面就对Nano-X的图形引擎进行分析，并试图对之进行优化。
     Nano-X采用分层次的设计方法，在底层提供对屏幕、鼠标、触摸屏和键盘的驱动，在程序能访问实际的硬件设备和其它用户定制设备。在中间层 有一个可移植图形引擎，提供绘制线程、区域填充、绘制多边形、裁减和使用颜色模式的方法。在顶层实现多种API以适应不同的应用环境。目前， MicroWindows中使用两种流行的图形编程接口：Microsoft Windows Win32/WinCE图形显示接口（GDI）和Xlib接口。前者应用于所有的Windows CE和Win32应用程序；后者就像Nano-X，应用于所有Linux X插件集的最底层，这样可让Linux图形程序员X接口开发图形应用程序。
     显然Nano-X窗口刷新速度取决于两个因素，一个是准备显示的时间，也就是生成要显示的数据的时间，GUI要运算出窗口的哪部分需要刷新重画，它们的位置是什么，这就是属于中间层的图形引擎层的工作。另一个是显示的时间，也就是把放在缓冲区（内存）的显示数据搬移到显存中的时间，这部分的时间与硬件设备的外部总线访问时间有关，如果在显存中是连续的，还可以使用DMA的方式，这属于驱动层的内容。
     对于Nano-X的图形引擎层，它被API层调用（GrXXX()），提供绘制线程、区域填充、绘制多边形、裁减和使用颜色模式的方法。由于驱动程只提供画点、画横线、画竖线和填充矩形的方法，所以它首先要把API层一些比较复杂的绘图调用进行分化，以便能够调用驱动层的一些比较原始的方法去实现，比如把画矩形的函数分解为四次画边的调用。而另一方面，驱动层还不能直接在窗口上画，它必须判断要画的图形是否已经超过窗口的大小，还有，要画的窗口是否已经被别的窗口覆盖，如果被覆盖，就要把被覆盖的部分从本窗口中剪切出去，这就牵涉到窗口的剪切问题了，如果有窗口的多重覆盖，就要对每一个可能覆盖的窗口进行检查，这也是图形引擎层比较复杂的原因了。
     首先要说明，所有的API调用函数中，都是必须要指明要画的窗口的（另外也可以指明在pixelmap上画），也就是要提供窗口的ID。下面看看MicroWindows中记录窗口信息的数据结构：
typedef struct {
GR_WINDOW_ID wid;            /* window id (or 0 if no such window) */
GR_WINDOW_ID parent;            /* parent window id */
GR_WINDOW_ID child;            /* first child window id (or 0) */
GR_WINDOW_ID sibling;            /* next sibling window id (or 0) */
GR_BOOL inputonly;            /* TRUE if window is input only */
GR_BOOL mapped;            /* TRUE if window is mapped */
GR_COUNT unmapcount;            /* reasons why window is unmapped */
GR_COORD x;                  /* absolute x position of window */
GR_COORD y;                  /* absolute y position of window */
GR_SIZE width;            /* width of window */
GR_SIZE height;            /* height of window */
GR_SIZE bordersize;            /* size of border */
GR_COLOR bordercolor;            /* color of border */
GR_COLOR background;            /* background color */
GR_EVENT_MASK eventmask;      /* current event mask for this client */
GR_WM_PROPS props;            /* window properties */
GR_CURSOR_ID cursor;            /* cursor id*/
unsigned long processid;      /* process id of owner*/
} GR_WINDOW_INFO;
其中x,y,width,height分别是左上角的绝对坐标和宽度、高度
parent是这个窗口的父窗口，除了根窗口，每一个窗口都有且只有父窗口。
Child是这个窗口的第一个子窗口，一个窗口可以有多个子窗口。
Sibling是这个窗口的兄弟窗口，他们同一个父窗口。
Inputonly表明这个这个窗口只是用于输入。
Mapped表明这个窗口是否已经被显示出来。
Unmapcount记录窗口被隐藏的次数。
Bordercolor，bordercolor窗口边的宽度和边的颜色
Background窗口的背景色
Eventmask是一堆事件宏定义的或，表明这个窗口可以处理这些事件。
Props窗口的属性，里面有些内容和前面的重叠
Cursor这个窗口所用鼠标的ID号，各个窗口可以自己定义自己的鼠标形状
Processed运行这个窗口的进程ID

对于窗口的覆盖关系，MicroWindows是这样规定的：
1）      子窗口可以覆盖父窗口，而父窗口不能覆盖子窗口
2）      在兄弟窗口之间，他们的父窗口的child指针指向的窗口优先级最高，也就是说，它覆盖它的任意兄弟窗口，然后它的sibling指向的窗口优先级其次，通过sibling指针依次递减。
3）      子窗口的显示区域不能超出它的父窗口的显示区域。
下面是一个各个窗口的关系图：

根据我们前面说的窗口覆盖的优先级关系，它们优先级的次序与左子树优先的中序遍历顺序是一样的。
对于任何一个API级的函数GrXXX()，它里面的参数都要指定要画的窗口ID，以及所用图形上下文GC的ID。在这些API函数里面，在调用图形引擎层的GdXXX()真正的画之前，都要先调用GsPrepareDrawing(id, gc, &dp)作准备。其实这个函数就是对要画的窗口作剪切。它首先根据ID找到窗口，如果找不到再看是否ID为pixelmap的ID，如果都不是则报错。对于在pixelmap上画图形，用得很少，原理也差不多，这里不作讨论。
对于窗口，首先看窗口是否是当前的窗口，也就是看窗口是否是上一次已经做过剪切算法的窗口并且gc也没有改变，如果是，直接返回记录窗口的数据结构即可，否则就要作剪切了。作剪切的函数是在GsSetClipWindow()中实现的。对于用户区的偏移量不是（0，0）的特殊情况（一般是（0，0）），在调用GsSetClipWindow()之前还要作偏移运算。
在GsSetClipWindow()（新版本这个函数调用的是在srvclip2.c里）中，实现对一个窗口的剪切。由于一个窗口被覆盖的情况相当的复杂，所以这个算法也是比较复杂的。
首先，一个子窗口的显示区域不能超出父窗口的显示区域，这就要把这个窗口与它的各级父窗口进行比较，得到经过父窗口剪切后的可显示区域，这是通过以下代码实现的：
     x = wp->x;
     y = wp->y;
     width = wp->width;
     height = wp->height;
     /*
      * First walk upwards through all parent windows,
      * and restrict the visible part of this window to the part
      * that shows through all of those parent windows.
      */
     pwp = wp;
     while (pwp != rootwp) {
           pwp = pwp->parent;

           diff = pwp->x - x;
           if (diff > 0) {
                 width -= diff;
                 x = pwp->x;
           }

           diff = (pwp->x + pwp->width) - (x + width);
           if (diff < 0)
                 width += diff;

           diff = pwp->y - y;
           if (diff > 0) {
                 height -= diff;
                 y = pwp->y;
           }

           diff = (pwp->y + pwp->height) - (y + height);
           if (diff < 0)
                 height += diff;
     }
这个显示区域肯定是一个矩形，或者由于整个窗口超出父窗口的显示区域而为NULL。如果显示区域为NULL，则调用      GdSetClipRegion(clipwp->psd, NULL);然后直接返回。GdSetClipRegion（）对第二个参数为NULL的处理是调用GdAllocRegion()重新分配一个区域（这样clipregion->numRects 肯定等于 0，clipresult = FALSE，表明不可显示）。
如果显示区域不为NULL，就要进入下一步的剪切，根据前面的分析可以知道，一个窗口可以被比它优先级高的各个窗口覆盖，覆盖它的窗口有两种：一种是它自己的各级子窗口，另一种是排在它前面的兄弟窗口以及它各级父窗口的优先级高的兄弟窗口，至于它父窗口的兄弟窗口的子窗口，由于不会超出它父窗口的兄弟窗口的范围，所以虽然优先级比它高，但是不用考虑。
如何记录被剪切过后的区域呢，剪切过后是一个不规则的形状，但是由于都是一个被矩形被另一个矩形剪切，可以把剪切过后的形状划分为多个矩形，并且用一个全局变量来记录划分过后的各个矩形，这个全局变量就是clipregion，它的数据结构为：
typedef struct {
     int      size;            /* malloc'd # of rectangles*/
     int      numRects;      /* # rectangles in use*/
     int      type;            /* region type*/
     MWRECT *rects;            /* rectangle array*/
     MWRECT      extents;      /* bounding box of region*/
} MWCLIPREGION;
它的numRects记录分解过后的矩形个数，而各个矩形的信息记录在rects指向的数组中。
在剪切过程中，它依次检查优先级比它高的各个窗口，如果与它有相交的则调用GdSubtractRegion（）函数进行剪切，并把剪切过后的的形状分解为一个个的矩形保存在clipregion中。
需要注意的是，在GdSubtractRegion（）的剪切中，是横向优先的，比如如下图所示：

窗口W1被W2覆盖，覆盖过后的绿色区域会被分解为图2 的R1和R2矩形

这样，在整个剪切完成后，就可以得到一个矩形数组，这里面保存着当前窗口可以画的矩形区域的信息。
在当前窗口剪切完成后，就可以调用图形引擎里面的对应函数GdXXX（）进行绘图操作了。
由于窗口被剪切，所要画的图形可能有一部分被剪切掉，不能画出来，另外没有被剪切掉的部分则可以画出来。在MicroWindows中，对一个图形的显示是逐点判断显示的，也就是把一个图形分解为一个个的象素点，对每一个象素点，调用GdClipPoint(psd, x, y)进行判断，如果这个点在前面clipregion记录的任意一个矩形内，则表明是可以显示的，就可以调用驱动层的psd->drawpixel()函数进行写屏操作。另外，如果clipregion-> numRects小于或者等于0，表明这个窗口没有被剪切，那么只要象素点落在屏幕范围内，就是可以显示的。否则，这一点就是被剪切掉了，直接返回。
在GdClipPoint（）中，用全局变量clipresult 来记录是否可显示，若clipresult等于TRUE;则可以显示，否则不能显示。如果能显示，则clipminx，clipminy ，clipmaxx ，clipmaxy 来记录包含这个象素点的矩形的位置，否则用来记录去掉这一点的半边的的矩形。这样可以缓存当前矩形。
在MicroWindows中，还提供了一个判断一个矩形区域是否包含在剪切后的矩形数组内的函数GdClipArea（），如果参数定义的矩形完全包含在矩形数组中的任意一个矩形内，就返回CLIP_VISIBLE，如果不与任何一个矩形有重叠的区域，那么就返回CLIP_INVISIBLE，如果与矩形数组中的矩形有重叠区域，但是不能包含在里面，就返回CLIP_PARTIAL。
这个函数在窗口剪切中的作用是，如果返回CLIP_VISIBLE，表明要画的部分完全暴露的，可以直接画，不用再利用GdClipPoint（）逐点判断的画。如果是CLIP_INVISIBLE，表明要画的部分被完全覆盖，可以不用再画，直接返回即可。如果是CLIP_PARTIAL，那么就要调用GdClipPoint()函数，逐点的画了。
优化
在实际的应用中发现，只要编程时稍加注意，真正的需要剪切的情况比较少，可是，在MicroWindows中不加区别的为所有的画图函数都进行逐点的剪切运算，所以在窗口切换和背景刷新时，如果CPU的运算能力比较低（低于50mips时），就会看见明显的刷屏现象。从以上分析可以看出，MicroWindows的窗口剪切算法效率是比较低的，有可以改进的地方。
首先是MicroWindows虽然提供了GdClipArea（）函数，但是在图形引擎层的画线、画图像等GdXXX()函数中都没有用。
所以优化的第一步是在GdXXX()函数中使用GdClipArea（）进行判断，如果返回CLIP_VISIBLE，可以调用驱动层的psd->drawXXX()直接画，可以大大的提高画线、画图像和填充窗口背景的速度。而且对于在VRAM中连续写值的情况，还可以使用DMA传送显示数据，可以进一步减小显示时间。
但是使用上面的方法取得的优化效果是有限的，它只能在窗口没有被其他窗口覆盖的情况下才能进行优化。而对于如下的情况：

窗口W1被W2（蓝色）覆盖，如果要在黄色区域进行绘图操作，由于被剪切后的矩形数组是横向的，结果没有一个矩形能够完全包含它，如果调用GdClipArea（），结果会返回CLIP_PARTIAL，这样即使黄色区域没有被别的窗口覆盖，也要调用GdCliipPoint（）进行逐点的画。而以上这种情况是经常碰到的，特别是在使用控件的时候（控件就是一个窗口）。
对它优化的办法是，在GsSetClipWindow()进行剪切时，另外定义一个矩形数组，记录所有覆盖当前窗口的窗口的位置和尺寸，再用要画的区域分别与它们相比较，看是否有重叠的，如果没有，表明即使当前窗口被其他窗口覆盖，但是要画的区域没有被覆盖，可以如CLIP_VISIBLE一样直接画。如果要画的区域与任意一个记录的矩形区域有重叠的话，就只能进行逐点的画了。
根据我的研究发现，事实上，可以对需要剪切的的情况进行进一步的优化。我们用一个矩形把要画的图形包含起来，用来表示要画的区域。前面说过，在窗口剪切后的可画区域会用一个矩形数组表示。可以用这个矩形数组再对要画的矩形区域进行剪切，把要画的矩形区域剪切成一个个的小的矩形的集合，其中每个矩形都包含在前面说到的可画的矩形数组中。这样，每个小矩形中的图形都是可以直接画的，不用逐点判断，就可以完全不用GdCliipPoint（）。
比如，如下图所示：

窗口W1被W2覆盖，我们想在W1中的W3区域大小的范围画图。W1被W2剪切后生成的矩形数组为R1，R2，R3，R4。如下图所示：

我们可以用这个数组对要画的区域W3进行再剪切，R1和R2会与要画的区域重叠，对要画区域进行剪切后的图形为下图所示：

图中的T1和T2就是剪切后的可以直接画的图形，不用再判断，这样可以进一步提高显示速度。
由于在窗口显示的大多数情况下，都是属于前两可以优化的情况，经过实验证明，通过优化后，MicroWindows的显示速度有较为明显的提高，在我们的EPSON C33L05平台上（约为50mips）显示速度效果良好。

参考文献：
1．《The Nano-X Window System Architecture》Greg Haerr，
2《嵌入式Linux系统下Microwindows的应用》吴升艳 岳春生 胡 冰，单片机及嵌入式系统应用