本站原创本文是一篇计算机图形学论文范文,计算机图形学类本科毕业论文,关于基于计算机图形学的多类型算法设计相关毕业论文参考文献格式范文。适合计算机图形学及计算机图形及数据库方面的的大学硕士和本科毕业论文以及计算机图形学相关开题报告范文和职称论文写作参考文献资料下载。
摘 要：本文通过结合基于计算机图形学的多类型算法相关内容进行讨论,并结合在计算机图形学下的平面扩展简单多边形面积计算以及高维空间中欧式距离计算,进行多类型算法设计研究.
关 键 词：计算机图形学；算法；分析和探究
中图分类号：TP391.4
1计算机图形学的基本算法介绍
在计算机图形学的基本算法中,通常包括了裁剪算法、多边形布尔运算、复杂多边形面积计算以及高维空间中点距离计算等几种.其中,裁剪算法作为计算机图形学中最为基本的内容,是图形合成的基础及必要的操作,主要作用在于可以有选择地对图形数据进行摘取.多边形的布尔运算通常被用于几何以及实体造型等领域当中,由于其可以用于计算交点,并避免了对其他几何元素的计算,使得布尔运算在几何与实体造型等领域中具有较高的应用价值.
2基于计算机图形学的平面扩展简单多边形面积计算设计
在假定多边形曲线边为圆锥曲线边或是三次Bezier曲线边的基础上,对原点到曲线边端点直线段,以及其与曲线边构成的三角范围进行考察,在此过程中出现的不合理情形包括了以下四种,即从原点到圆锥曲线边端点的直线段与边相交、三次Bezier曲线边有自交点、原点到Bezier曲线边端点直线段与边相交,以及连接Bezier曲线边两端点上的直线段与边相交等情况.需要对曲线边加以分割,行圆锥曲线边求分割点与切点算法、三次Bezier曲线边求可能的自交点算法、三次Bezier曲线边求不同形式分割点与切点算法等.
2.1圆锥曲线边的分割算法
根据圆锥曲线方程f等于a11x+2a12xy+a22y+2a1x+2a2y+a3.其中,V0等于（x0,y0）,V0与V1均为曲线两端点,s为1（或-1）,用于表示曲线段的走向选择.若是从原点O到圆锥曲线边端点V0的直线和曲线边存在除V0之外的交点,则将其确定为分割点,并得到直线方程为：y等于kx.综合得出（a11+2a12k+a22k）x+2（a1+ka2）x+a3等于0.根据伟大定理,推断出方程的另一个根X1为：a3/[x0（a11+2a12k+a22k）].输入a11、a12、a22、a1、a2、a3、V0、V1和s,根据A等于a2-a3a22,B等于2（a1a2-a12a3）,C等于a1-a11a3,求出AK+BK+C等于0的根k1、k2,再判断是否有切点,若无根则说明没有切点,否则进行以下步骤：
Xq1等于-（a1+k1a2）/（a11+2a12k1+a22k12）；yq1等于k1*Xq1
Xq2等于-（a1+k2a2）/（a11+2a12k2+a22k22）；yq2等于k2*Xq2
若sign（V0Q1V1）等于s,或是sign（V0Q2V1）等于s,那么Q1或Q2为圆锥曲线边的切点,否则说明交点在圆锥曲线段外部.
2.2三次Bezier曲线的自交点
若是多边形曲线边均为三次Bezier曲线,此时可以借助曲线边起点及终点P0和P3、以及P1和P2点来确定.将P0、P1、P2和P3各点的坐标设定为（x0,y0）,（x1,y1）（x2,y2）和（x3,y3）,并将自交点先后两次对应的参数值设定为t1和t2,其中,t1、t2均在0到1之间,那么：
（1-t1）3x0+3（1-t1）2t1x1+3（1-t1）t12x2+t13x3等于（1-t2）3x0+3（1-t2）2t2x1+3（1-t2）t22x2+t23x3（t1-t2）（（-3+3（t1+t2）-（t1+t2）2+t1t2）x0+3（1-2（t1+t2）+（t1+t2）2-t1t2）x1+3（（t1+t2）-（t1+t2）2+t1t2）x2+（（t1+t2）2-t1t2）x3）等于0
2.3三次Bezier曲线边的分割
若是从原点向三次Bezier曲线边某端点连接的直线段和曲线边存在交点（分割点）,那么,在对该直线段和曲线边的交点进行考查时,可以根据上述记号,表达为：
由P0点在公式y等于kx上,可知P0等于（x0,y0）,由此可推断出y0等于kx0,代入上式得出方程At+Bt+C等于0.通过求解,判断其根是否在0到1之间,若是,则说明直线和三次Bezier曲线边有交点,可求出该交点的参数值.若是连接三次Bezier曲线边两端点的直线和曲线边相交,此时其交点也相当于分割点.通过假定过曲线边两端点的坐标分别为（x0,y0）和（x3,y3）,且其直线方程为：y等于kx+b,将（1）式代入,推算出：
3基于计算机图形学的高维空间中欧式距离计算的设计
在高维空间中,各种对象所具备的特征组成均可看成一个点,例如在人脸识别方面,可通过提取更多的人脸特征,并将其存入相应的人脸特征向量数据库,当需要查找某个人时,只需输入相应的人脸特征向量,便可完成对输入人脸的识别.在此计算设计中,可假定一个n维向量空间,x为其特征向量,xi表示第i个人脸特征数值,c为一个高维数据点,R表示一个固定的半径长度,c与R之间的所有点组合成一个n维的集合——超球C.
在n维空间中,x到y之间的欧式距离L2、以及街区距离L1和棋盘距离L∞分别为：
由此可见,计算其街区距离或是棋盘距离相对较为简单.根据简单验证L∞≤L2≤L1,计算L∞和L1的线性组合来取代对L2的计算.具体如下.
假定n维超球C的球心为坐标系原点O,再根据半径R,可推断出方程：
根据超球C的球心为坐标系原点,了解到L1和L∞中的yi均为0,那么L1和L∞的简单形式：a（L1+L∞）为：
取绝大值和最大值,得出共有n·2n个超平面,围成一个n维超多面体.假设在xi≥0的卦限,在第n个坐标轴附近,L∞等于xn,则其相应表面所在的超平面方程为：此时分几种情况考虑,一是超多面体刚好在超球内部,令第n个坐标轴上的点P（0,0,等,0,R）落在超球表面以及超多面体的表面上,则a（0+0+等+R+R）等于R,得出a的值为0.5.由此可了解到,n个坐标数值中,存在i-1个0,或是n-i-1的值相等,为：
此时可以完成对某顶点到原点的距离平方的计算,得出.其中,R的系数不大于1.即所有点均在超球内部,或者说超多面体刚好落在超球内部,数值偏小.a等于0.5,n等于2,八边形在圆的内部；a等于0.5,n等于3,多面体在球的内部.
二是超多面体刚好落在超球外部,用公式表示为：
假定一个数值A,代入上述公式以确保所选择的a值使其xi有唯一解.首先,应经过平移公式xi等于xi’+A（1≤i≤n）,得出：
将其中的（x’1+x’2+等+xn+1’）的系数,以及最后一项设定为0,联立得到的两个方程求得：
并对（x’1+x’2+等+xn+1’）的系数,以及最后一项设定为0后的方程的前两项进行验证,可知方程前两项可成为正定二次型.假设方程有唯一解,那么x’1等于x’2等于等等于xn+1’等于0,由此可知满足要求的是：
为了验证超球是否与超多面体外切,可将a值代入（3）式,完成后将其代入方程：x12+x22+等+xn2等于R2.计算得到各顶点到原点距离的平方为：
在1≤i≤n的条件下,验证得出R的系数≥1,判断超多面体落在超球外部,说明数值偏大.a等于1/,n等于2,八边形和圆外切；a等于a等于1/,n等于3,24面体和球外切.此外,在超多面体与超球体积相等时,还可求出八边形与圆,或24面体与球存在相交情况.
4结束语
可以看出,基于计算机图形学的多类型算法能够提高算法效率、缩短计算时间,同时,通过分析曲线多边形的面积计算方式,还可以为基于计算机图形学的多类型算法在三维空间曲面多面体体积的计算提供参考依据.