免费下载
网站简介

找论文变得更简单!

帮找论文

当前位置:

重点论文网    理科论文    信息与计算科学论文    隐式曲线的几种绘制方法及分析
创建时间:11-13

隐式曲线的几种绘制方法及分析


摘要
本文主要介绍两种隐式曲线的绘制算法,角点判断算法和区间判断算法,并在两者之间作一些优劣性的对比。角点判断算法作为曲线绘制的一种经典算法,对比传统的象素遍历发,具有运算量小、复杂度低等优点。并且运用角点判断算法在VC++程序上编程,画出椭圆、三叶线等方程的曲线图形。区间算法主要讨论其创新的区间定义来判断曲线是否经过像素点来绘制出曲线。以及对比角点判断算法在绘制闭合曲线上具有的一些优势,同时对区间算法的一些不足之处进行改进,进一步优化算法。在此基础上运用区间算法编写程序,实现一些曲线的图形。
关键词  区间运算画法 角点判断画法 隐式曲线绘制
 
Several implicit curve mapping methods and analysis
 


Abstract
In this paper, two implicit curve mapping algorithm, corner algorithm and interval algorithm   are introduced. and it also compares two of them. As a classical method of drawing algorithm , Corner judgement is little amount of computing and the advantage of low complexity. In the paper ellipse and trefoil are programmed in VC++. Interval algorithm mainly uses that whether the curve passes the pixels innovatory. And compared with corner judgement , interval algorithm has some advantage and shortage. The article will also improve on the shortage of the interval algorithm .On the base of this interval algorithm the paper used to write programs, and carry out some of the graphics. 
Keywords: Interval Algorithm; ur corners judgment Algorithm; plicit curves


目录
中文摘要  ………………………………………………………………………………………………i
英文摘要 ………………………………………………………………………………………………ii
目录……………………………………………………………………………………………………iii
第一章    绪论………………………………………………………………………………………1
1.1    计算机图形学背景………………………………………………………………………1
1.2    隐式曲线绘制的研究意义………………………………………………………………2
1.3    角点判断画法大致思想…………………………………………………………………2
1.4    区间运算画法大致思想…………………………………………………………………3
第二章    角点判断画法……………………………………………………………………………5
2.1    角点判断画法的实现……………………………………………………………………5
2.2    角点判断画法的不足……………………………………………………………………8
2.3    角点判断画法的改进……………………………………………………………………9
第三章    区间判断画法……………………………………………………………………………11
3.1    区间类的基本定义………………………………………………………………………11
3.2    区间运算在曲线上应用…………………………………………………………………12
3.3    区间运算画法的实现……………………………………………………………………13
3.4    用区间运算画法绘制的一些实例展示…………………………………………………14
3.5    区间运算画法的不足……………………………………………………………………21
第四章    结论………………………………………………………………………………………24
致谢 ……………………………………………………………………………………………………25
参考文献 ………………………………………………………………………………………………26
附录A     程序源代码 ………………………………………………………………………………27

 

 
第一章     绪论
1.1    计算机图形学的背景
图形图像是人类相互交流和认识的主要媒体,而图像图形科学是一门理论与实际相结合,交叉性,综合性很强的学科,随着计算机技术的发展,图像图形技术已经迅速地渗透到人类生活和社会发展的各个方面,比如:动画制作,虚拟现实,高空遥感,航空航天,科学可视化等方面都迅速发展,随着计算机的进一步的发展,人们对图形图像的可视化要求越来越高,于是计算机图形绘制的研究就显得十分必要了。
在计算机辅助几何设计(CAGD)中,主要研究的对象是平面或空间的曲线和曲面,自然要考虑用合适的方法表示平面或空间中的点与点的轨迹,常用的表示方法有很多种,主要可以分为参数表示和隐式表示两类。
在CAGD的发展史上,人们最先探索的是采用参数多项式的数学形式来表示曲线和曲面,这主要是在参数表示形式上的应用。常用的两种参数表示形式是插值法和函数逼近法。在用参数多项式构造插值时,可以采用不同的多项式基函数,但这导致插值曲线的不同基表示形式,他们具有不同的优缺点。与插值的方法不同,逼近方法给出了在某种意义上最贴近数据点的逼近表示。现在在参数表示绘制中流行采用的方法有Bézier曲线\曲面与B样条曲线\曲面等形式。而隐式表示形式中的代数表示是另一种有效的表示方法。一般常用的方法有:象素遍历法,六角网格画法,角点判断画法,区间运算画法,点遍历画法等。
参数表示和隐式表示各有各的优点和缺点。先举个简单的例子,设曲线是到一固定点距离等于 的平面上的点轨迹,可选择这固定点为坐标原点,建立平面直角坐标系,设动点为 ,这个轨迹可以由以下两种表示:
  或 [5]
左边的是隐式表示方式,而右边的就是参数的表现形式。对于参数表示的方法,可以很容易由一个 的值得出一对 的值,随着 值的不断连续变化,得出一系列连续的点集 ,连成一条曲线,这样只要把得出来的点列集逐一画出来,就可得到一个完整的曲线或曲面。所以参数形式的曲线或曲面是很容易画出来的。当是,用参数形式表示一个曲线或曲面的时候。可以发现虽然曲线或曲面容易得出,但是很多性质不容易判断,比如当要判断一个点是否在于这个曲线或曲面上的时候,就不容易实现。例如判断点 是不是在上面的圆的曲线方程的时候,要先解出方程组 的值,如果方程组有解,则说明这个点在这个曲线或曲面上,简单的函数可以很容易解出反函数,但是对于很多的函数(可以说绝大部分函数)来说解出反函数的几乎是不可能的,更不用说是用计算机去解出并判断了。而且判断两点是否在曲线或曲面的同一侧也同样很难实现。这时候就需要运用隐式曲线或曲面来解决上面的问题。一条隐式代数曲线可以由一个多项式方程 定义,类似的,一个隐式代数曲面也可由多项式方程 定义。这时要判断一个点是否在一个曲线或曲面上,只要把点的值代入方程,使等式成立的就一定是在曲线或曲面上。而且隐式表示也易于表示封闭的形体,在几何操作(如求交,求并等)下运算封闭。但是隐式表示也有一些缺陷。比如,通常会出现多分支,形状不容易控制,绘制算法复杂等。
1.2隐式曲线研究意义
不过,鉴于隐式表示的优越性,隐式曲线和曲面的绘制是值得去研究的。近年来人们在隐式表示上的探索一直没有停止过,在隐式曲面绘制方面,存在的算法也是层出不穷,目前流行的主要算法有:光线跟踪算法,等高线画法,多边形化画法等。但是很多曲面绘制的方法的原始思想是来自隐式曲线的绘制,或者有些根本就是二维隐式曲线算法在三维中的直接推广。比如等高线画法,就是二维隐式曲线算法在三维中的应用。一般隐式曲面的表示形式是 ,按需求定义不同的等高线,不妨设 方向等高线为 ,接着计算一系列不同 的值的时候,由于 中的 是常数,就可以简化为 ,而 正是前面所描述隐式曲线的表示方法,把他在平面上绘制出来,然后再把一系列的绘制出来的曲线结合在一张图上,就形成了等高线画法。很显然,在这里,把隐式曲面的绘制完全转化为了隐式曲线的绘制,而多边形化画法的最根本的思维和隐式曲线的绘制的想法也多多少少有着异曲同工之处。
隐式曲线的绘制在计算机图形学中有着极其重要的地位,人们对此的研究也是比较深入的。从最初的象素遍历法,到角点判断画法,区间运算画法等。象素遍历法指的是对每个象素点进行判断,从而确定曲线是否经过这个点,如果通过就把它画出来。但是这样的算法是不可行的,因为他的计算量太大了,而且不实用。角点判断画法和区间运算画法是原来方法的改进。角点判断画法是比较经典的画法,而区间运算画法是近十年提出来的,有着很好的发展前景。在本文中将详细的讨论他。本文的重点将是区间运算画法的讨论,而角点判断法由于和区间运算画法的思想有着相似的地方。所以也将给于一定的篇幅去叙述他。
1.3    角点判断画法大致思想
角点判断画法是隐式曲线绘制中一个很经典的算法。下面先描述一下该算法的的大致思想。
在曲线的绘制中,一条曲线是由无穷多的点组合而成的,而且一个点几乎是无法绘制的,由于当正方形小到一定程度,就可以用小正方形来代替点。当曲线经过这个小正方形的时候,可以把这个小正方形绘制出来。这样,一条曲线可以由有穷多的小正方形连合而成,而且绘制的时候,绘制曲线的粗细也变得容易控制。
由上面的思想,很容易想到把绘制的区域平面分成 个小正方,但是鉴于象素遍历法要把每一个正方体都判断过去,但是曲线只经过一小部分的正方形,这样造成绘制的计算量庞大,而且不实用,还有一个缺点就是当把绘制的线条加细一半的时候,需要对每个正方体再次平分成等分的四个小正方形,这样就有了 个正方形需要判断,而产生的效果只是图形绘制的曲线细一半。但是在角点判断画法和区间运算画法的中,可以大量的减少运算量。
角点判断画法的大致思想很简单,就是取定一个绘制区域 ,先判断曲线是否在这个区域里面。如果不在,那么曲线不绘制,如果在,下一步要做的就是,把区域分成以下四个部分
     
     
,然后对这四个区域进行逐次的判断,对曲线经过的区域可以进行再一次的细分,对于曲线不经过的区域就舍去。有了这样的处理思想,就能很好的解决象素遍历法的一些缺陷,而且只是对曲线经过的区域进行判断,而对不经过的区域直接舍去。而且再细分到下一级的时候,由于对于不经过的区域舍去,计算量也会随之大量减少。
这就是角点判断画法的大致的思想,将在下一章中具体的描述实现的过程,和对一些不足的改进。
1.4    区间运算画法大致思想
把区间运算运用到隐式曲线的绘制上是近十年提出来的全新思想,它和角点判断的算法在处理的方式上有些相似,但是又有其自身的特点。区间运算最初的提出是围绕在关于几何造型上如何进行稳定的几何表示和计算而提出的。
由于在几何实体(点,线,面)的边界表示中,只有很少一部分数学式子能在计算机中精确表示,大部分的几何物体在计算机中都只能以浮点数来近似表示,而且在几何计算上,由于计算机采用的是浮点运算,所以由浮点算法得到的数也只能是近似的。因此,即使对于精确表示的几何实体,各种几何操作的结果也是近似的,所以无论数据是多么的准确,解的过程也会产生误差。几何造型的稳定性问题自80年代就已经广泛被提及并且一直是很活跃的研究课题,为了解决这个问题以保证算法的稳定性,出现了大量的研究成果,区间运算画法便是其中引人注目的一类方法。近几年,区间运算画法被Hu等引入几何造型领域,取得不少有效的结果。而后区间运算又被应用于曲线和曲面求交及几何形体的表示[6]。本文所讨论的区间运算画法在曲线绘制中的应用就是其中的一部分。
区间运算在隐式曲线绘制上运用和角点判断画法在处理的方式上有些相似,通过判断曲线是否经过区域,对区间进行不断细分处理,对曲线经过的区域再次细分处理,不断重复处理,直到达到所要的精度。如果精度相同,由于处理方式相同,他的运算的次数和和角点判断的算法的次数应该是一样的。但是由于算法不同,实际上他们的次数是不一样的,这将会在后面提到。
区间运算和角点判断区别在于对函数 的计算。角点判断判断一个曲线是否在区域 上时候,计算 , , , 四个角点的值,如果存在两个角点的值相乘小于零,那么可知这两点之间有一个点的值使 等于零,即曲线经过这个区域。而对于区间运算画法,这里 的值 不是确定的值而是区间 ,即进行的运算是 ,而且运算出来的结果是同样也是区间,当算出来的区间的范围在负数到正数之间时候。可以知道曲线经过这个区域。
区间运算有很多好处,不过也有一些缺陷,这些都将在第三章给出具体例子,详细讨论。
 

最新论文

网站导航

热门论文