（电路与系统专业论文）基于FPGA的三维图形几何管线的算法及其实现技术研究[电路与系统专业优秀论文].pdf

摘要 摘要 近年来，计算机图形学应用越来越广泛，尤其是三维( 3 d ) 绘图。3 d 绘图使用3 d 模型和各种影像处理产生具有三维空间真实感的影像，应用于虚拟真实情况以及多 媒体的产品上，且多半是使用低成本的实时3 d 计算机绘图技术为基础。在初期3 d 图形学刚起步时，由于图形简单，因此可以利用c p u 来运算，但随着图形学技术的 发展，所要绘制的图形越来越复杂，这时如果单纯依赖c p u 来处理，不能达到实时 的要求，因此需要专门的硬件来加速图形处理，g p u ( 图形处理单元) 因此出现了。 不过由于3 d 图形加速硬件的复杂性和短寿命，这极大地提高了对硬件开发环境的 需要。为了更好的对设计进行更改和测试，不能仅仅用专门定制的方法来设计，需 要其他的方：硬件描述语言( h d l ) 和f p g a 。 随着计算机绘图规模的需要，借助辅助硬件资源，来提高图形处理单元( g p u ) 处理速度的需求越来越普遍。自从1 5 年前现场可编程门阵列( f p g a ) 开始出现以来， 其在可编程硬件领域所起的作用越来越大。它们在速度、体积和速度方面都有了很 大的提高。这意味着f p g a 在以前只能使用专用硬件的场合越来越重要。其中一个 应用领域就是3 d 图形渲染，在这个研究领域里人们正在利用具有可编程性能的 f p g a 来帮助改进图形处理单元( g p u ) 的性能。 能够在廉价、可动态重新配置的f p g a 上实现复杂算法来辅助硬件设计。本文 的设计就是通过在f p g a 上实现3 维图形几何处理管线部分功能来提高图形处理速 度。具体实现中使用硬件描述语言( v e m o gh d l ) 进行逻辑设计，并发现问题解决问 题。 本文主要特色如下： 1 针对几何变换换子系统，提出一种硬件实现方案，该方案能对基本的几何变 换如：平移、缩放、旋转和投影进行操作。首先构造出总体变换矩阵，随后进行矩 阵乘法运算，再进行投影变换，最后输出变换座标。提出一种脉动阵列结构，用于 两个矩阵的乘法运算。找到一种快捷的方法来实现矩阵相乘，将能大大提高系统的 效率。 2 对于3 d 图形裁剪，文中描述了一种裁剪引擎，它能够处理3 d 图形中的裁剪、 透视除法以及视口映射的功能。硬件实现的难度取决于裁剪算法的复杂程度。我们 在s u t h e r l a n d h o d g m a n 裁剪算法的基础上提出一种新的裁剪算法，该算法通过去除 冗余顶点以提高处理速度，同时利用编码来判断线段可见性的方法使得硬件实现变 得很容易。 摘要 3 最后，我们在f p g a 上实现了几何变换以及三维裁剪，并与c 语言。的模拟结 果对比发现结果i f 确，甩三维裁剪能够以3 m 个三角形s 的速度运行，满足了图形 流水中的实时性要求。 关键词：计算机图形学几何变换脉动阵列3 维裁剪可编程逻辑门阵列 ab s t r a c t c l i p p i n g ，p e r s p e c t i v ed i v i s i o n ，a n dv i e w - p o r tm a p p i n go f3 dg r a p h i c s t h ed i 6 c u l t i t yo f h a r d w a r ei m p l e m e n t a t i o nd e p e n d so nt h ec o m p l e x i t yo ft h ec l i p p i n ga l g o r i t h m o nt h e b a s i so fh o d g m a n s u t h e r l a n da l g o r i t h m w ep r o p o s ean e wc i i p p i n g a l g o r i t h m ，w h i c h i m p r o v e sp r o c e s s i n gs p e e db ye l i m i n a t i n gr e d u n d a n tv e r t e x ，w h i l eu s i n ge n d p o i n tc o d i n g t oj u d g et h el i n ew h e t h e rv i s i b l em a k e sh a r d w a r ed e s i g nb e c o m ev e r ye a s y 3 f i n a l l y ，w ei m p l e m e n tt h ee n g i n ei nf p g a ， i n c l u d i n gg e o m e t r yt r a n s f i o n n a t i o n a n d3 dc l i p p i n g w ec h e c kt h er e s u l tw i t ht h ecm o d e la n df i n do u tt h a tt h eh a r d w a r e d e s ig nc a nm e e t t h e r e q u i r e m e n t s a n d t h e c l i p p i n g e n g i n e c a n p r o c e s s 3 m t r i a n g l e s ，m e e t i n gt h er e a l t i m er e q u i r e m e n t s k e yw o r d s ：c o m p u t e rg r a p h i c s ，g e o m e t r i ct r a n s f o 肌a t i o n s ，s y s t o l i ca r r a y ， 3dc 1 i p p i n g ，f i e i dp r o g r a m m a b l eg a t ea r r a y ( f p g a ) i v 论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除己特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：吴忍 v 耐年r 月i 岁日 第1 章绪论 第1 章绪论 1 1 计算机图形学发展概述f l l 计算机图形学1 2 lf 3 1 已经成为一门成熟的学科。目前作为商品的图形软件和硬 件已能方便地产生各种线画图形和真实感图像。今天，对许多人来说，计算机和 计算机图形学已经成为日常生活中不可缺少的一部分。计算机图形学在科学、工 程、医学、娱乐、广告、图形艺术、精细艺术、商业、教育和培训等众多领域得 到了普遍的应用。如何在计算机中表示图形、以及利用计算机进行图形的计算、 处理和显示的相关原理与算法，构成了其主要研究内容。 1 9 5 0 年，第一台图形显示器作为美国麻省理工学院( m i t ) 旋风i 号( w h i r l 诵n d i ) 计算机的附件诞生了。该显示器用一个类似于示波器的阴极射线管( c r t ) 来显示一些简单的图形。1 9 5 8 年美国c a l c o m p 公司由联机的数字记录仪发展成滚 筒式绘图仪，g e r b e r 公司把数控机床发展成为平板式绘图仪。在整个5 0 年代，只 有电子管计算机，用机器语言编程，主要应用于科学计算，为这些计算机配置的 图形设备仅具有输出功能。计算机图形学处于准备和酝酿时期，并称之为：“被 动式”图形学。到5 0 年代末期，m i t 的林肯实验室在“旋风”计算机上开发s a g e 空 中防御体系，第一次使用了具有指挥和控制功能的c r t 显示器，操作者可以用笔 在屏幕上指出被确定的目标。与此同时，类似的技术在设计和生产过程中也陆续 得到了应用，它预示着交互式计算机图形学的诞生。 1 9 6 2 年，m i t 林肯实验室的i v a ne s u t h e r l a n d 发表了一篇题为“s k e t c h p a d ： 一个人机交互通信的图形系统”的博士论文，他在论文中首次使用了计算机图形 学“c o m p u t e rg r a p h i c s ”这个术语，证明了交互计算机图形学是一个可行的、有用 的研究领域，从而确定了计算机图形学作为一个崭新的科学分支的独立地位。他 在论文中所提出的一些基本概念和技术，如交互技术、分层存储符号的数据结构 等至今还在广为应用。1 9 6 4 年m i t 的教授s t e 、e na c o o n s 提出了被后人称为超限 插值的新思想，通过插值四条任意的边界曲线来构造曲面。同在6 0 年代早期，法 国雷诺汽车公司的工程师p i e r r eb 6 z i e r 发展了一套被后人称为b 6 z i e r 曲线、曲面的 理论，成功地用于几何外形设计，并开发了用于汽车外形设计的u n i s u i u 系统。 c o o n s 方法和b z i e r 方法是c a g d 最早的开创性工作。值得一提的是，计算机图形 学的晟高奖是以c 0 0 n s 的名字命名的，而获得第一届( 1 9 8 3 ) 和第二届( 19 8 5 ) s t e v e na c o o n s 奖的，恰好是i v a ne s u t h e r l a n d 和p i e r r eb 邑z i e r ，这也算是计算机 图形学的段佳话。 7 0 年代是计算机图形学发展过程中一个重要的历史时期。由于光栅显示器的 第1 章绪论 产生，在6 0 年代就已萌芽的光栅图形学算法，迅速发展起来，区域填充、裁剪、 消隐等基本图形概念、及其相应算法纷纷诞生，图形学进入了第一个兴盛的时期， 并丌始出现实用的c a d 图形系统。又因为通用、与设备无关的图形软件的发展， 图形软件功能的标准化问题被提了出来。1 9 7 4 年，美国国家标准化局( a n s i ) 在a c ms i g g r a p h 的一个与“与机器无关的图形技术”的工作会议上，提出了制 定有关标准的基本规则。此后a c m 专门成立了一个图形标准化委员会，开始制 定有关标准。该委员会于1 9 7 7 、l9 7 9 年先后制定和修改了“核心图形系统”( c o r e g r 即h i c ss y s t e m ) 。i s o 随后又发布了计算机图形接口c g i ( c o m p u t e rg r a p h i c s i n t e r f a c e ) 、计算机图形元文件标准c g m ( c o m p u t e rg r a p h i c sm e t a f i l e ) 、计算机 图形核心系统g k s ( g r a p h i c sk e m e ls y s t e m ) 、面向程序员的层次交互图形标准 p h i g s ( p r o g r a m m e r 。sh i e r a r c h i c a l i n t e r a c t i v eg r a p h i c ss t a n d a r d ) 等。这些标准的 制定，为计算机图形学的推广、应用、资源信息共享，起到了重要作用。 7 0 年代，计算机图形学另外两个重要进展是真实感图形学和实体造型技术的 产生。1 9 7 0 年b o u k n i 曲t 提出了第一个光反射模型，1 9 7 1 年g o u r a n d 提出“漫反射 模型+ 插值”的思想，被称为g o u r a n d 明暗处理。1 9 7 5 年p h o n g 提出了著名的简单 光照模型p h o n g 模型。这些可以算是真实感图形学最早的开创性工作。另外，从 1 9 7 3 年开始，相继出现了英国剑桥大学c a d 小组的b u i l d 系统、美国罗彻斯特大 学的p a dl 1 系统等实体造型系统。 1 9 8 0 年w h i t t e d 提出了一个光透视模型w h i t t e d 模型，并第一次给出光线跟踪 算法的范例，实现w h i t t e d 模型；1 9 8 4 年，美国c o m e l l 大学和日本广岛大学的学 者分别将热辐射工程中的辐射度方法引入到计算机图形学中，用辐射度方法成功 地模拟了理想漫反射表面问的多重漫反射效果；光线跟踪算法和辐射度算法的提 出，标志着真实感图形的显示算法已逐渐成熟。从8 0 年代中期以来，超大规模集 成电路的发展，为图形学的飞速发展奠定了物质基础。计算机的运算能力的提高， 图形处理速度的加快，使得图形学的各个研究方向得到充分发展，图形学己广泛 应用于动画、科学计算可视化、c a d c a m 、影视娱乐等各个领域。 计算机图形学之所以能在它短短的3 0 多年历史中获得飞速发展，其根本原因 是图形为传递信息的最主要媒体之一。人们要利用计算机进行工作，必须有任何 计算机之间传递信息的手段人机界面。人机界面从早期的读卡机及控制板上 的丌关、指示灯发展到键盘和字符中断，再发展到基于键盘、鼠标、光笔等输入 设备和光栅显示器的图形用户界面，而最终必然过渡到带给用户身临其境感觉的 三维用户界面虚拟环境( 虚拟现实) 。人机界面的发展过程正好对应着计算 机技术从初级到高级的发展过程。计算机图形学来源于生活、科学、工程技术、 艺术、音乐、舞蹈、电影制作等，反过来，它又大大促进了这些领域的发展。 2 第1 章绪论 1 2 本文使用开发工具介绍 1 2 1 开发语言及其开发环境 ( i ) c 语言5 1 和硬件描述语言。v e r i l o gh d l 语言【6 】【7 】【8 】【9 j 硬件描述语言( h d l ) 是一种用形式化方法来描述数字电路和设计数字逻辑 系统的语言。它可以使数字逻辑电路设计者利用这种语言来描述自己的设计思 想，然后利用电子设计自动化( 在下面简称为e d a ) 工具进行仿真，再自动综合到 门级电路，再用a s i c 或f p g a 实现其功能。目前，这种称之为高层次设计 ( h i 曲l e v e l d e s i g n ) 的方法已被广泛采用。据统计，在美国硅谷目前约有9 0 以 上的a s i c 和f p g a 已采用硬件描述语言方法进行设计。 算法的描述和验证常用c 语言来完成。比如，要设计r e e d s o l o m e n 编码解码 器，必须深入了解r e e d s o l o m e n 编码解码算法，再编写c 语言的程序来验证算法 的正确性。运行描述编码器的c 语言程序，把这数据文件中的多组待编码的数据 转换为相应的编码后数据存入文件。再编写一个加干扰用的c 语言程序，用于模 拟信道。它能产生随机误码位( 并把误码位个数控制在纠错能力范围内) 将其加 入编码后的数据文件中。运行该加扰程序，产生带误码位的编码后的数据文件。 然后再编写一个解码器的c 语言程序，运行该程序把带误码位的编码文件解码为 另一个数据文件。只要比较原始数据文件和生成的文件便可知道编码和解码的程 序是否f 确( 能否自动纠正纠错能力范围内的错码位) 。用这种方法我们就可以 来验证算法的币确性。但这样的数据处理其运行速度只与程序的大小和计算机的 运行速度有关，也不能独立于计算机而存在。如果要设计一个专门的电路来进行 这种对速度有要求的实时数据处理，除了以上介绍的c 程序外，还须编写硬件描 述语言( 如v e r i l o gh d l 或v h d l l l 0 1 1 1 1 1 ) 的程序，进行仿真以便从电路结构上保 证算法能在规定的时l 、日j 内完成，并能与前端和后端的设备或器件正确无误地交换 数据。 在算法硬件电路的研制过程中，计算电路的结构和芯片的工艺对运行速度有 很大的影响。所以在电路结构确定之前，必须经过多次仿真： ( 1 ) c 语言的功能仿真。 f 2 ) c 语占的并行结构仿真。 ( 3 ) v e r i l o gh d l 的行为仿真。 ( 4 ) v e r i l o gh d lr t l 级仿真。 ( 5 ) 综合后门级结构仿真。 f 6 ) 布局布线后仿真。 ( 7 ) 电路实现验证。 3 第1 章绪论 应用v e r i l o gh d l 设计复杂数字电路的优点： ( 1 ) 传统设计方法一电路原理图输入法。几十年前，当时所做的复杂数 字逻辑电路及系统的设计规模比较小也比较简单，其中所用到的f p g a 或 a s i c 设计工作往往只能采用厂家提供的专用电路图输入工具来进行。为了满 足漫计性能指标，工程师往往需要花好几天或更长的时间进行艰苦的手工布 线。工程师还得非常熟悉所选器件的内部结构和外部引线特点，才能达到设 计要求。这种低水平的设计方法大大延长了设计周期。 近年来，f p g a 和a s i c 的设计在规模和复杂度方面不断取得进展，而对 逻辑电路及系统的设计的时间要求却越来越短。这些因素促使设计人员采用 高水准的设计工具，如：硬件描述语言( v e r i l o gh d l 或v h d l f o 川) 来进行设 计。 ( 2 ) v e r i l o gh d l 设计方法与传统电路原理图输入法比较。电路原理图输入 法最大问题是自动化程度低、工作量大、效率低，严重限制设计的规模。另一个 缺点是可移植性差，严重依赖于工具和库，如果工具和库发生变化，原理图的更 新可能需要很大的工作量。原理图的可读性很差，不利于维护以及项目成员之间 沟通。v e r i l o gh d l 语言克服了原理图输入的缺点，它有统一的标准，通过工具 自动综合产生网表，自动化程度高，工作效率高，可以用于大规模设计：语言描 述基本与工艺和库无关，也独立于综合工具，因此可移植性好；描述简洁，可读 性高，易于维护。 ( i i ) m o d e l s i m 仿真工具 m o d e l s i m 是m o d e lt e c h n o l o g y ( m e m o r gr a p h i c s 的子公司) 的h d l 硬件描述语 言仿真软件，可以实现v h d l ，v e r i l o g 以及v h d l 和v e r i l o g 混合设计的仿真，是 h d l 仿真业界中应用最为广泛的产品。 m o d e l s i m 是业界最优秀的h d l 语言仿真器，它提供最友好的调试环境，是 唯一的单内核支持v h d l 和v e r i l o g 混合仿真的仿真器。是作f p g a a s i c 设计的 r t l 级和门级电路仿真的首选，它采用直接优化的编译技术、t c l 厂r k 技术、和单 一内核仿真技术，编译仿真速度快，编译的代码与平台无关，便于保护i p 核，个 性化的图形界面和用户接口，为用户加快调错提供强有力的手段。全面支持 v h d l 口和v e r i l o g 语言的i e e e 标准，支持c c + + 功能调用和调试。 m o d e l s i m 具有强大的交互d e b u g 功能、衰减测试支持和高内存利用效率功 能，为仿真设计提供了广阔的范围。除此之外，m o d e l s i m 还能够与c 语言一起对 h d l 设计文件实现协同仿真。同时，相对于大多数的h d l 仿真软件来说m o d e l s i m 在仿真速度以及稳定性上也有明显优势。这些特点使m o d e l s i m 越来越受到e d a 设计者、优尤其是f p g a 设计者的青睐。 第l 章绪论 1 2 2 硬件载体 f p g a 【1 0 1 1 【1 2 】 f p g a 是英文f i e l dp r o 斟a m m a b l eg a t e a m y 的缩写，即现场可编程门阵列， 它是在p a l 、g a l 、e p l d 等可编程器件的基础上进一步发展的产物。与半定制 专用集成电路( a s i c ) 相比，随着技术的进步，f p g a 的集成度、复杂度和面积 优势使其同益成为一种吸引力的高性价比a s i c 替代方案。由于新产品成功的困 难越来越大，基于程序语言的a s i c 设计方法也已成为基于f p g a 设计大规模电 路的根本环节。f p g a 采用了逻辑单元阵列l c a ( l o g i cc e l la 盯a y ) 这样一个新 概念，内部包括可配置逻辑模块c l b ( c o n n g u r a b l el o g i cb l o c k ) 、输出输入模 块i o b ( i n p u to u t p u tb l o c k ) 、内部连线( i n t e r c o i m e c t ) 和块r a m ( b l o c l ( i 认m ) 等部分。 f p g a 的基本特点主要有： 1 ) 采用f p g a 设计a s i c 电路，用户不需要投片生产，就能得到合用的芯片。 2 ) f p g a 可做其它全定制或半定制a s i c 电路的中试样片。 3 ) f p g a 内部有丰富的触发器和i o 引脚。 4 ) f p g a 是a s i c 电路中设计周期最短、开发费用最低、风险最小的器件之 一o 5 ) f p g a 采用高速c h m o s 工艺，功耗低，可以与c m o s 、t t l 电平兼容。 可以说，f p g a 芯片是小批量系统提高系统集成度、可靠性的最佳选择之一。 f p g a 的设计开发流程【9 】【l o l 【1 1 】【1 4 】主要包括四个步骤：设计输入 ( d e s i g ne n t r y ) 、仿真( s i m u l a ti o n ) 、综合( s y n t h e s i s ) 及布局布线 ( p l a c e & r o u t e ) 。 1 设计输入( d e s i g ne n t r y ) 一r t l 代码编写 s u m m i t 公司的v i s u a l h d l 、m e n t o r 公司的r e n o i r 、a l d e c 公司的a c t i v e h d l 。 均支持图文混合的层次化设计。三者都提供p c 版本，v i s u a l h d l 还有工作站版 本。 图形输入包括状态图、真值表、流程图、方框图等。其中流程图输入方法是 r e n o i r 独有的。文本输入包括v h d l 和v e r i l o g ，上述工具都而且同时支持两种 语言。 r e n o i r 支持h d l 2 g r a p h ，即从v h d l 胱m o g 语言模块转换到图形。这一 特性有助于分析已有h d l 的语言结构。 a c t i v e h d l 提供h d l 语法高亮显示、自动产生文本结构、自动格式化文本 等非常有益的文本编辑浏览特性。r e n o i r 和v i s u a l h d l 甚至不提供最基本的 h d l 语法高亮显示。 第1 章绪论 2 仿真( s i m u l a t i o n ) 一编写t e s t b e n c h 仿真包括功能仿真和时序仿真。其中，功能仿真在布局邪线之前；时序仿 真在布局布线之后。仿真工具有m e n t o r 公司的m o d e l s i m 和a l d e c 公司的 a c t i v e h d l ，二者同时支持v hd l 和v e r i l o g 的仿真。c a d e n c e 公司也提供仿真 工具，似乎对v e r i l o g 的支持更强，没有评估过。m o d e l s i m 同时提供p c 和工作 站版本，a c t i v e h d l 只有p c 版本。 其中m o d e l s i m 是工业界应用最广的仿真工具，已经成为事实上的标准。界 面简洁，仿真速度快，功能强大而稳定。 a c t i v e h d l 提供图示化仿真激励输入，而且有t e s t b e n c h 的自动生成模板， 这些特性都是独有的。而且语言的在线帮助系统非常好。 3 综合( s y n t h e s i s ) 综合工具实现从h d l 语言到f p g a 或a s i c 网表的生成。目前有s y n o p s y s 公司的f p g a c o m pi l e r i i 、m e n t o r 公司的e x 锄p l a r 和s y n p l i f y 公司的s y n p l i c i t y 。 三者都有p c 和工作站版本。 其中f p g ac o m p i l e ri i 是应用最广的，只支持f p g a 的综合。s y n o p s y s 公 司另外有a s i c 的综合工具。 e x a m p l a r 同时支持f p g a 和a s i c 。 s y n p l i c i t y 界面简洁，据说综合速度比其他二者更快。 4 布局布线( p l a c e & r o u t e ) 布局布线采用f p g a 厂商提供的工具。x i l i n x 有f o u n d a t i o ns e r i e s 和 a l l i a n c es e r i e s 两个系列，分别支持凡十门级以下和以上的f p g a 。a l t e r a 的两个 系歹0 是m a x p l u s i i 币口q u a r t u s 。 这一整个设计流程都会有各类e d a 软件的参与。通常是以某一主要e d a 软件( 由器件厂商提供) 为核心，再辅以若干个第三方软件来进行的。x i l i n x 公司 的f p g a 开发流程如图： 第l 章绪论 1 3 课题背景及意义 图卜1f p g a 开发流程 1 3 1 真实感图形绘制【1 5 1 【1 6 】1 1 7 】 图形绘制技术是计算机图形学的一个重要领域，它研究的是如何将几何定义 的模型变成可视的图像。真实感图形绘制技术是图形学绘制技术发展的结果，它 的目标是根据几何场景的造型、材质和光源分布，将其转变成跟真实场景在视觉 效果上非常相似的图像，可以与实拍照相相媲美。在近三十年的时间里，随着硬 件技术和计算机图形学的高速发展，真实感图形绘制技术取得了举世瞩目的成 就，并且已广泛应用于c a d c a m 、计算机动画、虚拟现实、科学计算可视化 等众多领域，为社会的发展与进步做出了重大贡献。 几十年来，c a d c a m 技术的飞速发展，对许多行业的设计和生产过程产 生了巨大影响，使其自动化程度达到了前所未有的高度。在机械设计方面，传统 的产品设计通常需制作实物模型来检查设计效果，尤其是那些对外形美感要求较 高的产品，一般要先按图纸制作样品，再根据样品反映的问题进行多次修改，耗 费大量人力、物力和时间。若采用真实感图形显示技术，则可方便地在屏幕上显 示产品在各种视角下的逼真图形，并且可直接在计算机上对设计参数进行交互修 改和绘制，直到满意为止。既可大大减少反复生产样品的时间，缩短设计周期， 也节约了生产样品的资金和人力；在建筑方面，建筑师往往要花费很大的精力绘 制效果图，如果采用真实感图形绘制技术，不但可以把这方面的工作交给计算机 处理，还可以结合虚拟现实技术进行建筑物体的虚拟漫游，这样，建筑师和用户 在建筑物还处于设计阶段就可以非常直观地了解建成后的外观和内部空间的布 置及采光效果等，做到胸有成竹。 第1 章绪论 计算机动画是真实感图形绘制技术的又一重大应用领域。在电影和电视广告 中，要达到某些特定的效果，往往需要进行许多次的试验和拍摄。那些危险场面、 破坏场面和需要动物配合的场面不但令电影工作者们非常为难，而且提高了电影 的制作费用，还可能对人员造成伤害。另外，有些事物和景象更是现实世界无法 找到的，比如科幻片或者灾难片，无法实景拍摄。通过计算机绘制出高度真实感 的虚拟场景，这些困难都可以方便地解决。可以说，真实感图形绘制技术给影视 工作者和艺术家提供了一个尽情发挥想象力的舞台。 虚拟现实是当前的一个热门研究课题，它在飞行训练、战斗模拟、计算机游 戏等许多领域具有十分广阔的应用前景。真实感图形绘制技术是基于图形的虚拟 现实的核心技术之一，直接关系到人机交互速度和图像输出质量。 科学计算可视化是当前的另一热门课题，它己在医学、地球科学、天文物理、 化学、机械工程等许多方面取得了巨大成就，将大批工程技术人员和医务人员从 大量繁琐的数据中解放出来。真实感图形是科学计算可视化的输出手段之一，绘 制质量将直接关系到工程技术人员对原始数据的理解和医务人员对病人病情和 病因的判断，具有突出的现实意义。 真实感图形绘制技术的应用领域非常广阔，它的影响正迅速地向工业生产和 社会生活的各个领域渗透。可以预料，在未来社会里它必将发挥更为重要的作用。 1 3 2 研究意义 在计算机图形学中，引人注目的研究方向之一是图形的真实感问题。所谓图 形的真实感是指计算机所生成的图形反映客观世界的程度。长期以来，图形真实 感问题一直是计算机图形学研究的一个主要课题。这是由于计算机技术的飞速发 展，其应用越来越广泛，某些应用领域( 计算机艺术造型、计算机制作、三维游 戏、计算机娱乐和广告动画设计等) 已把高度真实感的图形作为其发展的目标， 要求我们能逼真地在计算机屏幕上再现真实世界。真实感图形绘制是计算机图形 学的重要组成部分。它综合利用数学、物理学、计算机科学和其它科学知识在计 算机图形设备上生成像彩色照片那样的真实感图形。随着多色彩高分辨率光栅图 形设备的普及，真实感图形绘制技术在各个领域中得到广泛应用，日益受到人们 的重视，发展速度极快。利用计算机绘制真实感图形具有很大的实用价值。面对 己经取得的巨大成就，计算机图形的生成仍面临着很多挑战。在图形绘制中常常 要根据现实世界中的真实情况来进行图形绘制，希望得到的绘制结果尽可能真 实。在电影中用计算机模拟的许多暴风雨、火灾、地震和其它的自然灾难就是这 样，为了获得具有真实效果的灾难场面，根据相应自然现象的物理性质进行绘制。 但是由于物理现实的复杂性，会在取得足够质量绘制结果的基础上进行一些简化 第1 章绪论 以加速计算处理。 总的来说，绘制作为计算机图形学中的重要领域，其是一个复杂、耗时的过 程。如绘制一个只有几个物体和光源的场景，需要计算每个光源在物体上每个点 产生的影响。因此要在计算机图形生成的高质量和生成所需要时间之间进行平 衡，即在生成高质量图形效果的同时保持绘制的高速度。为了和使用者能够进行 交互，绘制系统在生成具有真实的图像效果的同时，还需要达到比较高的绘制速 度，最好高于3 0 帧秒，至少1 5 帧秒( f p s ) ，否则系统就会出现停顿，不能形成流 畅的画面。 在一些绘制中，实时性也许不是很重要。只是需要等待一段时间才能得到绘 制的最终结果。此时可以通过软件来进行绘制处理，而不要特别去关心绘制速度。 但在实时绘制中，利用软件实现的绘制系统常常不能满足要求，只有借助于图形 硬件来加速处理。图形硬件在结构因为针对图形处理的需要，因此可以极大地提 高绘制处理速度。 1 4 本文的工作和结构安排 本文在认真研究了3 d 图形学原理的基础上，尝试采用自顶向下( t o p d o w n ) 的 方法对g p u 几何处理部分( 包括几何变换和三维裁剪) 进行f p g a 设计实现，作为 g p u 的辅助功能模块，减轻g p u 的运算负担，以达到加速的目的。主要研究内容 有：3 d 图形学技术的发展状况；3 d 绘图管线介绍；几何处理技术研究；几何处 理功能单元的f p g a 实现等。 文文包括五个章节，其结构安排如下：第一章为绪论部分，主要介绍3 d 图 形学技术的发展状况，以及本文所用到的软件和硬件；第二章介绍3 d 图形的实 时绘制管线，介绍绘制管线的各个处理阶段：第三章介绍了几何变换和三维裁剪 技术；第四章对3 d 图形的集成电路设计进行了相关研究：第五章为几何处理在 f p g a 上的实现，包括几何变换系统和三维裁剪单元的设计；第六章总结与展望。 9 第2 章3 d 图形的实时绘制管线 第2 章3 d 图形的实时绘制管线 2 1 引言 在现实世界中，管线概念的表现方式非常之多，如输油管道、工厂的装配线、 滑雪缆车等等，对于图形绘制来说，同样也采用了管线的概念。 根据o p e n g le s1 1 标准1 4 1 ) 在实时计算机图形学中，同样存在着如图2 1 所示 的管线结构，在概念上可以粗略地分为3 个阶段：应用程序、几何以及光栅5 】。 这种结构是绘制管线的核心机制，在实时计算机图形学中也应用广泛。在绘制管 线中，每个阶段也有可能就是一条管线，这就意味着它可以包含几个子阶段。一 个管线阶段应该与其他管线阶段同时执行，但是为了满足高性能的要求，也可以 对它们进行并行化处理。 图2 1实时绘制管线的基本结构 最慢的管线阶段决定绘制速度，即图像更新速度，这种速度一般用如s 来表 示，也就是每秒绘制的图像数量，或者用h z 来表示。由于涉及到管线，因此不 能将想绘制的所有数据通过整个管线的时间进行简单相加，这就是管线的特点， 它允许某些阶段做并行处理。如果能够确定其中的瓶颈位置，也就是管线中最慢 的阶段，同时知道所有数据通过该阶段需要花费的时间，就可以计算出绘制速度。 2 2 绘制管线f 1 5 1 2 2 1 应用程序阶段 由于应用程序阶段是通过软件方式实现的，因此开发者能够对该阶段发生的 情况进行完全控制，可以通过改变实现方法来改变实际性能。而其他阶段，由于 它们全部或部分建立在硬件基础上，因此要改变实现过程非常困难。即便如此， 仍然有可能改变几何和光栅阶段所消耗的时间。例如，可以在应用程序阶段通过 减少三角形数量来达到此目的。 在应用程序的末端，将需要绘制的几何体输入到绘制管线的下一个阶段。这 些几何体都是绘制图元( 如点、线、矩形等) ，最终需要在荧幕上( 具体取决于 1 0 第2 章3 d 图形的实时绘制管线 3 投影 在光照处理以后，绘制系统将开始进行投影。目的是将视体变换为一个单位 立方体。这个立方体的顶点是( 1 ，1 ，1 ) 和( 1 ，1 ，1 ) 。单位立方体也称为规范视 体( c a n o n i c a lv i e wv o l u m e ) 。投影主要有两种方式：正投影( 平行投影) 和透视投影。 j 下投影的可视体通常是一个矩形盒子，正投影可以把这个视体变换为单位立 方体。工f 投影的主要特点是平行线在投影变换以后依然平行，这种变换是平移和 缩放的组合。 透视投影比正投影复杂，这种投影方式下，物体距离相机位置越远，投影之 后就变得更小。平行线在投影之后可以相交。透视投影变换与人类感觉物体大小 的过程非常相似。从几何说，视体也称为锥体，即一个以矩形为底面的被截金字 塔，同样也可以将这个锥平截投体变换为单位立方体。 正投影和透视投影都可以通过4 x 4 的矩阵来实现，在任何一种变换以后，都 可以认为模型位于归一化处理之后的设备坐标系中。投影变换后产生的图象的z 坐标系将不存在，投影以后模型从三维变成二维。 4 裁剪 只有当图元完全或部分位于视体内部的时候，才需要将其发送至光栅阶段， 在光栅阶段把这些图元在屏幕上绘制出来。当一个图元完全位于视体内部的时候 那么它可以直接进入下一阶段。完全在视体外部的图元，将不会进入下一阶段， 没有必要对它们进行绘制。需要对那些部分位于视体内的图元进行剪裁处理。投 影变换后的图元只针对单位立方体进行剪裁，在剪裁之前进行视点变换和投影的 优势在于可以使剪裁问题变得比较一致，而且图元可以根据单位立方体进行剪 裁。 5 屏幕映射 只有在视体内部经过裁剪的图元，才可以进入屏幕映射阶段，进入这个阶段 的时候，坐标仍然是三维的。每个图元的x 和y 坐标变换到屏幕坐标系中，屏幕坐 标系连同z 坐标一起称为窗口坐标系。屏幕映射首先进行平移，所后进行缩放， 在映射过程中z 坐标不受影响，新的、和y 坐标称为屏幕坐标系，与z 坐标系一起 进入光栅阶段。 2 2 3 光栅阶段 给定经过变换和投影的顶点、颜色以及纹理坐标，光栅阶段的目的就是给每 个象素正确着色，以便正确绘制整幅图像，这个过程称为光栅化，也就是把屏幕 空间的二位顶点转化为屏幕上的像素。屏幕空间有一个z 值( 深度值) 、一种或多 种颜色，以及一组或多组纹理坐标，其中纹理坐标会与顶点或者屏幕上 第2 章3 d 图形的实时绘制管线 的z 缓冲器内容进行比较。如果新得到的z 值小于z 缓冲器中的z 值，那么说明即将 绘制的图元与视点的距离比原来距离视点最近的图元还要近。这样，像素的z 值 和颜色就由当前图元对应的z 值和颜色进行更新。如果计算出来的z 值大于z 缓冲 器中的z 值，那么颜色缓冲器和z 缓冲器中的内容就不变。z 缓冲器算法非常简单， 具有o ( n ) 的复杂度( n 为需要绘制的像素的数量) ，知要对每个图元计算出对应像素 的z 值，就可以使用该方法z 缓冲器算法中，像素绘制的顺序是任意的，这也是 它得到广泛应用的主要原因【2 】。 为了提高绘制的真实感，纹理影射是一种有效的技术。值得注意的是，在使 用对顶点的法向量进行插值的p h o n g 【3 3 1 明暗处理方法绘制多边形时，光照的计算 将在光栅阶段进行，而不同于g o u r a u d l 3 2 1 明暗处理方法那样在几何阶段进行。 2 3 小结 本章详细介绍了3 d 实时绘制管线的相关技术。在绘制管线中，点、线和三 角形都是绘制图元，它们共同构成了模型或者物体。在管线中，软件部分和硬件 加速部分之间存在经常性的交叠，而且存在一种将软件算法硬件化的趋势。此外， 价格、速度和质量上的权衡是非常重要的。从历史上看，图形硬件加速通常位于 管线的最后阶段，首先执行执行三角形光栅扫描处理。硬件的不断更新换代有力 地支持了管线这种概念，同时，随着显示图形复杂程度越来越高，比较高级的应 用程序阶段和几何阶段算法都尽可能利用硬件来实现。硬件比软件的唯一优势就 在于速度，而对于实时绘制来说速度则是至关重要的。 第3 章3 d 图形绘制中的几何处理技术研究 第3 章3 d 图形绘制中的几何处理技术研究 3 1 引言 在前面第二章中提到，在3 d 图形绘制的几何管线部分包括几何变换和裁剪两 个部分，这两个部分真正进行的是几何处理功能。 在计算机图形学中，图形变换非常重要。通过变换，可以对实体、光源和相 机进行定向、变形，以及动画处理等等。此外还可以保证所有的计算操作在同一 个坐标系中进行，然后将物体以各种不同方式投影到给定平面上。虽然只有一小 部分操作需要运用图形变换来实现，但是却能充分说明变换在实时计算机图形学 甚至其他任何种类的计算机图形学中具有非常重要的作用。 裁剪是为了适合屏幕尺寸，减少后续图形处理工作量，提高3 d 图形加速效 率所必需的一个步骤。经裁剪后，只保留了视窗内我们可以看到的图元，后续的 其他图形处理步骤均只对这一部分图元进行。裁剪的要点是针对一个任意图元的 裁剪算法，这是提高裁剪速度的瓶颈所在。按空间分，裁剪可分为二维裁剪和三 维裁剪；按裁剪体分，裁剪分为平行投影视见体下的裁剪和透视投影视见体下的 裁剪：按裁剪对象分，裁剪分为线裁剪，三角面裁剪和多边形裁剪。本章重点分 析三维情况下三角面在透视投影视见体下的裁剪。 3 2 几何变换技术 在计算机图形学中最通常的表示物体的方法是多边形网孔模型。一个物体由 系列多边形连接而成，而每个多边形又由一系列顶点( x ，y ，z ) 连接而成。如下图 3 一l 所示： 第3 章3 d 图形绘制中的几何处理技术研究 v e r t i c e s 图3 1物体模型的数据结构 3 d 图形变换【2 】f 3 1 【4 】【”1 【协】i j 包括旋转，缩放，错切和平移等几个部分。一系列图 形变换可以合成为一个变换式。一个物体的3 维顶点集合可以通过线性变换为另 外一组点的集合。在图形学中通常用矩阵来表示各种变换。利用矩阵表示时，若 顶点v 要进行平移，缩放，旋转变换，可以用如下表示： 矿= d + 矿，矿= s y ，y = r 矿 其中d 为平移矩阵，s 和r 分别为缩放和旋转矩阵。 如果要将所有变换都能在硬件结构上实现，对于所有变换运用规范化的表示 是必须的。由于在笛卡儿坐标系下不能将平移变换和其他变换结合起来，因而引 入了齐次坐标系。笛卡儿坐标系和齐次坐标系之间的转换也很容易。在齐次坐标 系中，顶点数据y ( x ，y ，z ) 表示为y ( x ，y ，z ，w ) ( w 不等于o ) ，两坐标之间的关系为： x = x ? w ，y = y iy ，z = zfw 在计算机图形学中一般w 取为1 ，则顶点的矩阵表示为i x ，y ，z ，1 1 7 用奇次坐标表示的平移变换这时可以表示为矩阵相乘的形式： 洲 00 t 1o l 01r 001 因此，在奇次坐标系下任何变换的矩阵表示为： = 丁 1 7 第3 章3 d 图形绘制中的几何处理技术研究 石 y z 1 & 口l i 刀g m 刎渤l 讹柙幽踟稽 l 忍心够胁h o m 。影月窖。“sli 。 l ，j z 矽，曾5 学刀f 口f j 。刀 j 1 l i 。_ 一l 缩放矩阵： 矿= s 矿 s = s ： o q s 。 0o oo oo 00 s ： 0 o1 旋转矩阵： 对物体的旋转必须选定旋转轴，虽然旋转轴的位置可以任意，不过都可以转化 为平行坐标轴的形式，绕x ，y z 坐标轴的旋转变换矩阵为： 疋= 1o0oc o s 口o oc o s 秒 os i n 目 oo s i n9o c o s 臼o 01 r = c o s 口 一s i n p 0 o r 。= s i n 矽 c o s 口 o 0 ol s i n 秽o 00 o 0 o o 10 01 一s i n 口 o