基于矩形或圆形窗口的若干线裁剪算法研究

摘要

随着信息技术和互联网技术的不断发展，图形图像技术得到了广泛的应用。作为图形图像技术基础学科，计算机图形学也显得越来越重要。自20世纪60年代计算机图形学作为一门新兴学科诞生以来，已经历了五十多年的发展历程。虽然计算机图形学的发展速度非常迅速，但是仍然不能满足人们高度沉浸感的需求。其不足之处主要表现在计算机图形学的算法效率低下仍然需要不断改善，不同学科之间的融合需要不断地加强。为了使图形显示满足更加逼真的视觉效果，需要改进计算机图形学中的某些经典算法或者不断提出新的算法以提高效率。随着计算机动画、人机交互以及虚拟现实等相关学科的飞速发展，人们对现有计算机图形学技术提出了更高的真实感要求。由于复杂图形是由简单图形构成的，因此重视计算机图形学中的基础算法仍然十分重要。裁剪作为计算机图形学的基础操作，其重要性也是不言而喻的。论文的工作是改进了计算机图形学的经典裁剪算法并提出了一种圆形窗口线段裁剪算法。
　　本文针对Cohen-Sutherland线段裁剪算法不能排除完全位于矩形窗口之外的线段而且可能计算无效交点的问题，提出了一种改进的Cohen-Sutherland线段裁剪算法。本文改进算法通过增加判断条件，可以快速的舍弃完全位于矩形窗口之外的线段，避免了无效的求交计算，并且对于与矩形窗口有交点的线段，可以快速的判断出线段与窗口的哪条边有交点，从而快速的计算出真实交点的坐标。实验表明，本文改进的算法确实改善了裁剪的效率。
　　由于圆形窗口对直线段裁剪在进行求交点计算时，需要对一元二次方程进行求解，计算比较费时。本文通过分析圆形窗口与被裁剪直线段之间的位置关系，提出了一种新的圆形窗口对线段的裁剪算法。该算法可以快速的排除完全位于圆形窗口之外的线段，避免了无效的求交计算，对于与圆形窗口有交点的线段在求交点计算时避免了对一元二次方程的求解，从而加快了裁剪的速度。

目录

声明

摘要

1 绪论

1．1 计算机图形学的发展史

1．2 裁剪操作

1．3 国内外裁剪研究综述

1．3．1 点的裁剪

1．3．2 矩形窗口线段裁剪

1．3．3 圆形窗口线段裁剪

1．3．4 多边形窗口线段裁剪

1．4 课题研究的意义

1．5 本文的组织结构

2 线段裁剪算法基础

2．1 有效交点与无效交点

2．2 Cohen-Sutherland裁剪算法

2．2．1 算法思想

2．2．2 算法基本步骤

2．3 中点分割算法

2．3．1 算法思想

2．3．2 求交方法

2．3．3 算法基本步骤

2．4 算法比较

2．5 本章小结

3 改进的Cohen-Sutherland裁剪算法

3．1 改进算法的思想

3．2 改进算法流程图

3．3 改进算法基本步骤

3．4 裁剪结果和效率分析

3．5 本章小结

4 圆形窗口的线裁剪算法

4．1 算法思想

4．1．1 圆形窗口与被裁剪直线段的位置关系

4．1．2 圆形窗口与被裁剪直线段位置关系的判定

4．2 圆与直线段交点计算

4．3 圆形窗口线裁剪算法描述

4．4 裁剪结果和效率分析

4．5 本章小结

5 总结与展望

5．1 论文工作总结

5．2 未来工作展望

参考文献

致谢

攻读学位期间参与的项目及发表的学术论文