光子束聚焦无掩模光刻机是纳米量级器件和极大规模集成电路制造关键装备,图形发生器是该装备的核心部件,它的主要功能模块包括:窗口裁减,尺寸修正,场切割,黑白翻转,轮廓化以及多边形自分割等。目前国内已有的图形发生器仅仅只是用工程方法来实现各个功能,没有一套完整的几何图形理论体系,而图形发生器的软件架构和算法对直写系统的整机性能起着至关重要的作用,所以必须为掩模图形中的图形数据设计良好的数据结构以及高效的算法。　　 为实现直写光刻机中图形发生器的软件功能模块,本文以计算机图形学中的光栅图形学部分和计算数学理论中的计算几何为理论基础,较为系统地给出了一种多边形的双向链接边表的表示方法及高效的平面子区域划分的叠合算法。该算法以计算几何中常用的平面扫描算法为基础,针对多边形中出现空洞的情况,提出了一种新的判别准则和基于图的重构的遍历搜索方法。该算法的时间复杂度相对传统的二次项复杂度提高了一个数量级,并且具有线性的空间复杂度。　　 在直写技术控制算法上,本文以Bresenham锄算法为理论基础,推导了掩模图形中最基本的单元图形如直线,圆的坐标生成递归式,它消除了除法和浮点运算,从而完全消除了因计算机字长限制而产生的误差,并为后续工程实现节约了硬件资源和成本。对由单元图形组成的复合图形和封闭图形,本文也给出了各种曝光策略与填充策略。最后在Windows程序中对算法进行了模拟实现和实验验证。