论文部分内容阅读
裁剪算法是计算机图形学中的基本算法,也是其它诸多重要问题的基础。经过了近半个世纪的讨论和探索,一些线裁剪算法越来越完善,尤以矩形窗口的线裁剪方法最为突出,但一般多边形窗口的线裁剪算法并不是十分理想,而多边形窗口的多边形裁剪算法还没有受到广泛的关注。但后两者在图形学以及工程实际的应用中具有更为重大的现实意义。尤其是目前还没有文献提到带圆弧边的多边形的多边形裁剪问题。而这类问题又是土建工程三维可视化预算软件开发中最为基础的问题。 因此,本文首先基于Visual C++6.0语言、采用OpenGL图形库,开发了一个小型矢量图形系统,为后续算法的设计、调试和应用提供了图形平台。 接着,设计了一个任意多边形窗口的多边形裁剪算法。该算法不仅适用于一般意义上的凸多边形和凹多边形,而且还适用于带圆弧边的组合多边形以及有空洞的多边形(本文称之为广义多边形)。其次,在算法的设计中采用了包围盒技术、计算几何的跨立法、射线法等技术,大大简化了计算过程。再者,Visual C++支持的CArray类,以及CObList类的数据结构(单链表)的采用,大幅度地减少了内存开销,节约了存储空间。符号函数的引入,有效地控制了误差传递,确保了计算精度。最后,针对MFC(Microsoft Foundation Class Library)提供的库函数的不足,编写了一个判断点与广义多边形位置关系的新函数,有效地消除了由此产生的致命性错误。最终实现了一个几何适应性强,时间和空间复杂度低的算法。 最后,将新算法应用于土建工程三维可视化预算软件中,成功地实现了三维动态交互绘制中墙与墙、墙与梁、墙与柱,以及墙与板的实时扣减。