datasheet
超过460,000+ 应用技术资源下载
pdf

三维图形几何管线的算法

  • 1星
  • 日期: 2014-03-05
  • 大小: 10.78MB
  • 所需积分:1分
  • 下载次数:0
  • favicon收藏
  • rep举报
  • 分享
  • free评论
标签: 三维图形几何管线的算法

近年来,计算机图形学应用越来越广泛,尤其是三维(3D)绘图。3D绘图使用3D模型和各种影像处理产生具有三维空间真实感的影像,应用于虚拟真实情况以及多媒体的产品上,且多半是使用低成本的实时3D计算机绘图技术为基础。在初期3D图形学刚起步时,由于图形简单,因此可以利用CPU来运算,但随着图形学技术的发展,所要绘制的图形越来越复杂,这时如果单纯依赖CPU来处理,不能达到实时的要求,因此需要专门的硬件来加速图形处理,GPU(图形处理单元)因此出现了。不过由于3D图形加速硬件的复杂性和短寿命,这极大地提高了对硬件开发环境的需要。为了更好的对设计进行更改和测试,不能仅仅用专门定制的方法来设计,需要其他的方:硬件描述语言(HDL)和FPGA。 随着计算机绘图规模的需要,借助辅助硬件资源,来提高图形处理单元(GPU)处理速度的需求越来越普遍。自从15年前现场可编程门阵列(FPGA)开始出现以来,其在可编程硬件领域所起的作用越来越大。它们在速度、体积和速度方面都有了很大的提高。这意味着FPGA在以前只能使用专用硬件的场合越来越重要。其中一个应用领域就是3D图形渲染,在这个研究领域里人们正在利用具有可编程性能的FPGA来帮助改进图形处理单元(GPU)的性能。 能够在廉价、可动态重新配置的FPGA上实现复杂算法来辅助硬件设计。本文的设计就是通过在FPGA上实现3维图形几何处理管线部分功能来提高图形处理速度。具体实现中使用硬件描述语言(Verilog HDL)进行逻辑设计,并发现问题解决问题。 本文主要特色如下: 1.针对几何变换换子系统,提出一种硬件实现方案,该方案能对基本的几何变换如:平移、缩放、旋转和投影进行操作。首先构造出总体变换矩阵,随后进行矩阵乘法运算,再进行投影变换,最后输出变换座标。提出一种脉动阵列结构,用于两个矩阵的乘法运算。找到一种快捷的方法来实现矩阵相乘,将能大大提高系统的效率。 2.对于3D图形裁剪,文中描述了一种裁剪引擎,它能够处理3D图形中的裁剪、透视除法以及视口映射的功能。硬件实现的难度取决于裁剪算法的复杂程度。我们在Sutherland-Hodgman裁剪算法的基础上提出一种新的裁剪算法,该算法通过去除冗余顶点以提高处理速度,同时利用编码来判断线段可见性的方法使得硬件实现变得很容易。 3.最后,我们在FPGA上实现了几何变换以及三维裁剪,并与C语言的模拟结果对比发现结果正确,且三维裁剪能够以3M个三角形/s的速度运行,满足了图形流水中的实时性要求。

中国科学技术大学 硕士学位论文 基于FPGA的三维图形几何管线的算法及其实现技术研究 姓名:吴思 申请学位级别:硕士 专业:电路与系统 指导教师:郭立 20080401 摘要 摘要 近年来,计算机图形学应用越来越广泛,尤其是三维(3D)绘图。3D绘图使用3D 模型和各种影像处理产生具有三维空间真实感的影像,应用于虚拟真实情况以及多 媒体的产品上,且多半是使用低成本的实时3D计算机绘图技术为基础。在初期3D 图形学刚起步时,由于图形简单,因此可以利用CPU来运算,但随着图形学技术的 发展,所要绘制的图形越来越复杂,这时如果单纯依赖CPU来处理,不能达到实时 的要求,因此需要专门的硬件来加速图形处理,GPU(图形处理单元)因此出现了。 不过由于3D图形加速硬件的复杂性和短寿命,这极大地提高了对硬件开发环境的 需要。为了更好的对设计进行更改和测试,不能仅仅用专门定制的方法来设计,需 要其他的方:硬件描述语言(HDL)和FPGA。 随着计算机绘图规模的需要,借助辅助硬件资源,来提高图形处理单元(GPU) 处理速度的需求越来越普遍。自从15年前现场可编程门阵列(FPGA)开始出现以来, 其在可编程硬件领域所起的作用越来越大。它们在速度、体积和速度方面都有了很 大的提高。这意味着FPGA在以前只能使用专用硬件的场合越来越重要。其中一个 应用领域就是3D图形渲染,在这个研究领域里人们正在利用具有可编程性能的 FPGA来帮助改进图形处理单元(GPU)的性能。 能够在廉价、可动态重新配置的FPGA上实现复杂算法来辅助硬件设计。本文 的设计就是通过在FPGA上实现3维图形几何处理管线部分功能来提高图形处理速 度。具体实现中使用硬件描述语言(Vemog HDL)进行逻辑设计,并发现问题解决问 题。 本文主要特色如下: 1.针对几何变换换子系统,提出一种硬件实现方案,该方案能对基本的几何变 换如:平移、缩放、旋转和投影进行操作。首先构造出总体变换矩阵,随后进行矩 阵乘法运算,再进行投影变换,最后输出变换座标。提出一种脉动阵列结构,用于 两个矩阵的乘法运算。找到一种快捷的方法来实现矩阵相乘,将能大大提高系统的 效率。 2.对于3D图形裁剪,文中描述了一种裁剪引擎,它能够处理3D图形中的裁剪、 透视除法以及视口映射的功能。硬件实现的难度取决于裁剪算法的复杂程度。我们 在Sutherland.Hodgman裁剪算法的基础上提出一种新的裁剪算法,该算法通过去除 冗余顶点以提高处理速度,同时利用编码来判断线段可见性的方法使得硬件实现变 得很容易。 摘要 3.最后,我们在FPGA上实现了几何变换以及三维裁剪,并与c语言。的模拟结 果对比发现结果iF确,甩三维裁剪能够以3M个三角形/s的速度运行,满足了图形 流水中的实时性要求。 关键词:计算机图形学几何变换脉动阵列3维裁剪可编程逻辑门阵列 A bstract clipping,perspectiVe diVision,and View-port mapping of 3D graphics.The di6cultity of hardware implementation depends on the complexity of the clipping algorithm.On the basis of Hodgman·Sutherland algorithm.we propose a new cIipping algorithm,which improVes processing speed by eliminating redundant Vertex,while using endpoint coding to judge the line whether Visible makes hardware design become very easy 3. Finally,we implement the engine in FPGA, including geometry transfIonnation and 3D clipping.We check the result with the C model and find out that the hardware desi gn can meet the requirements.And the 3M·triangle/s,meeting the real—time requirements. clipping engine can process Key words:Computer Graphics,Geometric transfo肌ations,Systolic Array, 3 D C1ipping,FieId Programmable Gate Array(FPGA) .IV. 论文原创性和授权使用声明 本人声明所呈交的学位论文,是本人在导师指导下进行研究工作 所取得的成果。除己特别加以标注和致谢的地方外,论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权,即:学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版,允许论文被查阅和借阅,可以将学位论文编入有关数据库进行检 索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名:吴忍 v耐年r月I岁日 第1章绪论 第1章 绪 论 1.1计算机图形学发展概述fll 计算机图形学12l f31已经成为一门成熟的学科。目前作为商品的图形软件和硬 件已能方便地产生各种线画图形和真实感图像。今天,对许多人来说,计算机和 计算机图形学已经成为日常生活中不可缺少的一部分。计算机图形学在科学、工 程、医学、娱乐、广告、图形艺术、精细艺术、商业、教育和培训等众多领域得 到了普遍的应用。如何在计算机中表示图形、以及利用计算机进行图形的计算、 处理和显示的相关原理与算法,构成了其主要研究内容。 1950年,第一台图形显示器作为美国麻省理工学院(MIT)旋风I号(Whirl诵nd I)计算机的附件诞生了。该显示器用一个类似于示波器的阴极射线管(CRT) 来显示一些简单的图形。1958年美国Calcomp公司由联机的数字记录仪发展成滚 筒式绘图仪,GerBer公司把数控机床发展成为平板式绘图仪。在整个50年代,只 有电子管计算机,用机器语言编程,主要应用于科学计算,为这些计算机配置的 图形设备仅具有输出功能。计算机图形学处于准备和酝酿时期,并称之为:“被 动式”图形学。到50年代末期,MIT的林肯实验室在“旋风”计算机上开发SAGE空 中防御体系,第一次使用了具有指挥和控制功能的CRT显示器,操作者可以用笔 在屏幕上指出被确定的目标。与此同时,类似的技术在设计和生产过程中也陆续 得到了应用,它预示着交互式计算机图形学的诞生。 1962年,MIT林肯实验室的Ivan E.Sutherland发表了一篇题为“Sketchpad: 一个人机交互通信的图形系统”的博士论文,他在论文中首次使用了计算机图形 学“Computer Graphics”这个术语,证明了交互计算机图形学是一个可行的、有用 的研究领域,从而确定了计算机图形学作为一个崭新的科学分支的独立地位。他 在论文中所提出的一些基本概念和技术,如交互技术、分层存储符号的数据结构 等至今还在广为应用。1964年MIT的教授Ste、『en A.Coons提出了被后人称为超限 插值的新思想,通过插值四条任意的边界曲线来构造曲面。同在60年代早期,法 国雷诺汽车公司的工程师Pierre B6zier发展了一套被后人称为B6zier曲线、曲面的 理论,成功地用于几何外形设计,并开发了用于汽车外形设计的UNISUIU系统。 Coons方法和B∈zier方法是CAGD最早的开创性工作。值得一提的是,计算机图形 学的晟高奖是以C00ns的名字命名的,而获得第一届(1983)和第二届(1 985) Steven A.Coons奖的,恰好是Ivan E.Sutherland和Pierre B邑zier,这也算是计算机 图形学的~段佳话。 70年代是计算机图形学发展过程中一个重要的历史时期。由于光栅显示器的 第1章绪论 产生,在60年代就已萌芽的光栅图形学算法,迅速发展起来,区域填充、裁剪、 消隐等基本图形概念、及其相应算法纷纷诞生,图形学进入了第一个兴盛的时期, 并丌始出现实用的CAD图形系统。又因为通用、与设备无关的图形软件的发展, 图形软件功能的标准化问题被提了出来。1974年,美国国家标准化局(ANSI) 在ACM SIGGRAPH的一个与“与机器无关的图形技术”的工作会议上,提出了制 定有关标准的基本规则。此后ACM专门成立了一个图形标准化委员会,开始制 定有关标准。该委员会于1977、l 979年先后制定和修改了“核心图形系统”(Core Gr即hics System)。ISO随后又发布了计算机图形接口CGI(Computer Graphics Interface)、计算机图形元文件标准CGM(Computer Graphics Metafile)、计算机 图形核心系统GKS(Graphics Kemel system)、面向程序员的层次交互图形标准 PHIGS(Programmer。s HierarchicalInteractive Graphics Standard)等。这些标准的 制定,为计算机图形学的推广、应用、资源信息共享,起到了重要作用。 70年代,计算机图形学另外两个重要进展是真实感图形学和实体造型技术的 产生。1970年Boukni曲t提出了第一个光反射模型,1971年Gourand提出“漫反射 模型+插值”的思想,被称为Gourand明暗处理。1975年Phong提出了著名的简单 光照模型.Phong模型。这些可以算是真实感图形学最早的开创性工作。另外,从 1973年开始,相继出现了英国剑桥大学CAD小组的Build系统、美国罗彻斯特大 学的PADL.1系统等实体造型系统。 1980年Whitted提出了一个光透视模型.Whitted模型,并第一次给出光线跟踪 算法的范例,实现Whitted模型;1984年,美国Comell大学和日本广岛大学的学 者分别将热辐射工程中的辐射度方法引入到计算机图形学中,用辐射度方法成功 地模拟了理想漫反射表面问的多重漫反射效果;光线跟踪算法和辐射度算法的提 出,标志着真实感图形的显示算法已逐渐成熟。从80年代中期以来,超大规模集 成电路的发展,为图形学的飞速发展奠定了物质基础。计算机的运算能力的提高, 图形处理速度的加快,使得图形学的各个研究方向得到充分发展,图形学己广泛 应用于动画、科学计算可视化、CAD/CAM、影视娱乐等各个领域。 计算机图形学之所以能在它短短的30多年历史中获得飞速发展,其根本原因 是图形为传递信息的最主要媒体之一。人们要利用计算机进行工作,必须有任何 计算机之间传递信息的手段——人机界面。人机界面从早期的读卡机及控制板上 的丌关、指示灯发展到键盘和字符中断,再发展到基于键盘、鼠标、光笔等输入 设备和光栅显示器的图形用户界面,而最终必然过渡到带给用户身临其境感觉的 三维用户界面——虚拟环境(虚拟现实)。人机界面的发展过程正好对应着计算 机技术从初级到高级的发展过程。计算机图形学来源于生活、科学、工程技术、 艺术、音乐、舞蹈、电影制作等,反过来,它又大大促进了这些领域的发展。 2 第1章绪论 1.2本文使用开发工具介绍 1.2.1开发语言及其开发环境 (i)C语言‘…51和硬件描述语言。Verilog HDL语言【6】【7】【8】【9J 硬件描述语言(HDL)是一种用形式化方法来描述数字电路和设计数字逻辑 系统的语言。它可以使数字逻辑电路设计者利用这种语言来描述自己的设计思 想,然后利用电子设计自动化(在下面简称为EDA)工具进行仿真,再自动综合到 门级电路,再用ASIC或FPGA实现其功能。目前,这种称之为高层次设计 (Hi曲.Level.Design)的方法已被广泛采用。据统计,在美国硅谷目前约有90%以 上的ASIC和FPGA已采用硬件描述语言方法进行设计。 算法的描述和验证常用C语言来完成。比如,要设计Reed.Solomen编码/解码 器,必须深入了解Reed.Solomen编码/解码算法,再编写C语言的程序来验证算法 的正确性。运行描述编码器的C语言程序,把这数据文件中的多组待编码的数据 转换为相应的编码后数据存入文件。再编写一个加干扰用的C语言程序,用于模 拟信道。它能产生随机误码位(并把误码位个数控制在纠错能力范围内)将其加 入编码后的数据文件中。运行该加扰程序,产生带误码位的编码后的数据文件。 然后再编写一个解码器的C语言程序,运行该程序把带误码位的编码文件解码为 另一个数据文件。只要比较原始数据文件和生成的文件便可知道编码和解码的程 序是否『F确(能否自动纠正纠错能力范围内的错码位)。用这种方法我们就可以 来验证算法的币确性。但这样的数据处理其运行速度只与程序的大小和计算机的 运行速度有关,也不能独立于计算机而存在。如果要设计一个专门的电路来进行 这种对速度有要求的实时数据处理,除了以上介绍的C程序外,还须编写硬件描 述语言(如Verilog HDL或VHDLll011111)的程序,进行仿真以便从电路结构上保 证算法能在规定的时l、日J内完成,并能与前端和后端的设备或器件正确无误地交换 数据。 在算法硬件电路的研制过程中,计算电路的结构和芯片的工艺对运行速度有 很大的影响。所以在电路结构确定之前,必须经过多次仿真: (1)C语言的功能仿真。 f2)C语占的并行结构仿真。 (3)Verilog HDL的行为仿真。 (4)Verilog HDL RTL级仿真。 (5)综合后门级结构仿真。 f6)布局布线后仿真。 (7)电路实现验证。 3 第1章绪论 应用Verilog HDL设计复杂数字电路的优点: (1)传统设计方法一电路原理图输入法。几十年前,当时所做的复杂数 字逻辑电路及系统的设计规模比较小也比较简单,其中所用到的FPGA或 ASIC设计工作往往只能采用厂家提供的专用电路图输入工具来进行。为了满 足漫计性能指标,工程师往往需要花好几天或更长的时间进行艰苦的手工布 线。工程师还得非常熟悉所选器件的内部结构和外部引线特点,才能达到设 计要求。这种低水平的设计方法大大延长了设计周期。 近年来,FPGA和ASIC的设计在规模和复杂度方面不断取得进展,而对 逻辑电路及系统的设计的时间要求却越来越短。这些因素促使设计人员采用 高水准的设计工具,如:硬件描述语言(Verilog HDL或VHDLf’o川)来进行设 计。 (2)Verilog HDL设计方法与传统电路原理图输入法比较。电路原理图输入 法最大问题是自动化程度低、工作量大、效率低,严重限制设计的规模。另一个 缺点是可移植性差,严重依赖于工具和库,如果工具和库发生变化,原理图的更 新可能需要很大的工作量。原理图的可读性很差,不利于维护以及项目成员之间 沟通。Verilog HDL语言克服了原理图输入的缺点,它有统一的标准,通过工具 自动综合产生网表,自动化程度高,工作效率高,可以用于大规模设计:语言描 述基本与工艺和库无关,也独立于综合工具,因此可移植性好;描述简洁,可读 性高,易于维护。 (ii)Modelsim仿真工具 Modelsim是Model Technology(MemorG raphics的子公司)的HDL硬件描述语 言‘仿真软件,可以实现VHDL,Verilog以及VHDL和Verilog混合设计的仿真,是 HDL仿真业界中应用最为广泛的产品。 ModelSim是业界最优秀的HDL语言仿真器,它提供最友好的调试环境,是 唯一的单内核支持VHDL和Verilog混合仿真的仿真器。是作FPGA/ASIC设计的 RTL级和门级电路仿真的首选,它采用直接优化的编译技术、Tcl厂rk技术、和单 一内核仿真技术,编译仿真速度快,编译的代码与平台无关,便于保护IP核,个 性化的图形界面和用户接口,为用户加快调错提供强有力的手段。全面支持 VHDL口和Verilog语言的IEEE标准,支持C/C++功能调用和调试。 ModelSim具有强大的交互DEBUG功能、衰减测试支持和高内存利用效率功 能,为仿真设计提供了广阔的范围。除此之外,Modelsim还能够与C语言一起对 HDL设计文件实现协同仿真。同时,相对于大多数的HDL仿真软件来说.Modelsim 在仿真速度以及稳定性上也有明显优势。这些特点使Modelsim越来越受到EDA 设计者、优尤其是FPGA设计者的青睐。 第l章绪论 1.2.2硬件载体 FPGA【101…1【12】 FPGA是英文Field Pro斟ammable GateAmy的缩写,即现场可编程门阵列, 它是在PAL、GAL、EPLD等可编程器件的基础上进一步发展的产物。与半定制 专用集成电路(ASIC)相比,随着技术的进步,FPGA的集成度、复杂度和面积 优势使其同益成为一种吸引力的高性价比ASIC替代方案。由于新产品成功的困 难越来越大,基于程序语言的AsIC设计方法也已成为基于FPGA设计大规模电 路的根本环节。FPGA采用了逻辑单元阵列LCA(Logic Cell A盯ay)这样一个新 概念,内部包括可配置逻辑模块CLB(Conngurable Logic Block)、输出输入模 块IOB(Input Output Block)、内部连线(IntercoImect)和块RAM(Blocl(I认M) 等部分。 FPGA的基本特点主要有: 1)采用FPGA设计ASIC电路,用户不需要投片生产,就能得到合用的芯片。 2)FPGA可做其它全定制或半定制ASIC电路的中试样片。 3)FPGA内部有丰富的触发器和I/o引脚。 4)FPGA是ASIC电路中设计周期最短、开发费用最低、风险最小的器件之 一O 5)FPGA采用高速CHMOS工艺,功耗低,可以与CMOS、TTL电平兼容。 可以说,FPGA芯片是小批量系统提高系统集成度、可靠性的最佳选择之一。 FPGA的设计开发流程【9】【lol【11】【14】主要包括四个步骤:设计输入 (Design Entry)、仿真(Simulat ion)、综合(Synthesis)及布局布线 (Place&Route)。 1.设计输入(Design Entry)一RTL代码编写 Summit公司的VisualHDL、Mentor公司的Renoir、Aldec公司的ActiveHDL。 均支持图文混合的层次化设计。三者都提供PC版本,VisualHDL还有工作站版 本。 图形输入包括状态图、真值表、流程图、方框图等。其中流程图输入方法是 Renoir独有的。文本输入包括VHDL和verilog,上述工具都而且同时支持两种 语言。 Renoir支持HDL2GRAPH,即从VHDL胱mog语言模块转换到图形。这一 特性有助于分析已有HDL的语言结构。 ActiveHDL提供HDL语法高亮显示、自动产生文本结构、自动格式化文本 等非常有益的文本编辑浏览特性。Renoir和VisualHDL甚至不提供最基本的 HDL语法高亮显示。 第1章绪论 2.仿真(Simulation)一编写Testbench 仿真包括功能仿真和时序仿真。其中,功能仿真在布局邪线之前;时序仿 真在布局布线之后。仿真工具有Mentor公司的Modelsim和Aldec公司的 ActiveHDL,二者同时支持VH DL和Verilog的仿真。Cadence公司也提供仿真 工具,似乎对Verilog的支持更强,没有评估过。Modelsim同时提供PC和工作 站版本,ActiveHDL只有PC版本。 其中Modelsim是工业界应用最广的仿真工具,已经成为事实上的标准。界 面简洁,仿真速度快,功能强大而稳定。 ActiveHDL提供图示化仿真激励输入,而且有testbench的自动生成模板, 这些特性都是独有的。而且语言的在线帮助系统非常好。 3.综合(Synthesis) 综合工具实现从HDL语言到FPGA或ASIC网表的生成。目前有Synopsys 公司的FPGAComp ilerII、Mentor公司的Ex锄plar和Synplify公司的Synplicity。 三者都有PC和工作站版本。 其中FPGA Compiler II是应用最广的,只支持FPGA的综合。Synopsys公 司另外有ASIC的综合工具。 Examplar同时支持FPGA和ASIC。 Synplicity界面简洁,据说综合速度比其他二者更快。 4.布局布线(Place&Route) 布局布线采用FPGA厂商提供的工具。Xilinx有Foundation Series和 Alliance Series两个系列,分别支持凡十门级以下和以上的FPGA。Altera的两个 系歹0是MaxPlusII币口Quartus。 这一整个设计流程都会有各类EDA软件的参与。通常是以某一主要EDA 软件(由器件厂商提供)为核心,再辅以若干个第三方软件来进行的。Xilinx公司 的FPGA开发流程如图: 第l章绪论 图卜1 FPGA开发流程 1.3课题背景及意义 1.3.1真实感图形绘制【151【16】117】 图形绘制技术是计算机图形学的一个重要领域,它研究的是如何将几何定义 的模型变成可视的图像。真实感图形绘制技术是图形学绘制技术发展的结果,它 的目标是根据几何场景的造型、材质和光源分布,将其转变成跟真实场景在视觉 效果上非常相似的图像,可以与实拍照相相媲美。在近三十年的时间里,随着硬 件技术和计算机图形学的高速发展,真实感图形绘制技术取得了举世瞩目的成 就,并且已广泛应用于CAD/CAM、计算机动画、虚拟现实、科学计算可视化 等众多领域,为社会的发展与进步做出了重大贡献。 几十年来,CAD/CAM技术的飞速发展,对许多行业的设计和生产过程产 生了巨大影响,使其自动化程度达到了前所未有的高度。在机械设计方面,传统 的产品设计通常需制作实物模型来检查设计效果,尤其是那些对外形美感要求较 高的产品,一般要先按图纸制作样品,再根据样品反映的问题进行多次修改,耗 费大量人力、物力和时间。若采用真实感图形显示技术,则可方便地在屏幕上显 示产品在各种视角下的逼真图形,并且可直接在计算机上对设计参数进行交互修 改和绘制,直到满意为止。既可大大减少反复生产样品的时间,缩短设计周期, 也节约了生产样品的资金和人力;在建筑方面,建筑师往往要花费很大的精力绘 制效果图,如果采用真实感图形绘制技术,不但可以把这方面的工作交给计算机 处理,还可以结合虚拟现实技术进行建筑物体的虚拟漫游,这样,建筑师和用户 在建筑物还处于设计阶段就可以非常直观地了解建成后的外观和内部空间的布 置及采光效果等,做到胸有成竹。 第1章绪论 计算机动画是真实感图形绘制技术的又一重大应用领域。在电影和电视广告 中,要达到某些特定的效果,往往需要进行许多次的试验和拍摄。那些危险场面、 破坏场面和需要动物配合的场面不但令电影工作者们非常为难,而且提高了电影 的制作费用,还可能对人员造成伤害。另外,有些事物和景象更是现实世界无法 找到的,比如科幻片或者灾难片,无法实景拍摄。通过计算机绘制出高度真实感 的虚拟场景,这些困难都可以方便地解决。可以说,真实感图形绘制技术给影视 工作者和艺术家提供了一个尽情发挥想象力的舞台。 虚拟现实是当前的一个热门研究课题,它在飞行训练、战斗模拟、计算机游 戏等许多领域具有十分广阔的应用前景。真实感图形绘制技术是基于图形的虚拟 现实的核心技术之一,直接关系到人机交互速度和图像输出质量。 科学计算可视化是当前的另一热门课题,它己在医学、地球科学、天文物理、 化学、机械工程等许多方面取得了巨大成就,将大批工程技术人员和医务人员从 大量繁琐的数据中解放出来。真实感图形是科学计算可视化的输出手段之一,绘 制质量将直接关系到工程技术人员对原始数据的理解和医务人员对病人病情和 病因的判断,具有突出的现实意义。 真实感图形绘制技术的应用领域非常广阔,它的影响正迅速地向工业生产和 社会生活的各个领域渗透。可以预料,在未来社会里它必将发挥更为重要的作用。 1.3.2研究意义 在计算机图形学中,引人注目的研究方向之一是图形的真实感问题。所谓图 形的真实感是指计算机所生成的图形反映客观世界的程度。长期以来,图形真实 感问题一直是计算机图形学研究的一个主要课题。这是由于计算机技术的飞速发 展,其应用越来越广泛,某些应用领域(计算机艺术造型、计算机制作、三维游 戏、计算机娱乐和广告动画设计等)已把高度真实感的图形作为其发展的目标, 要求我们能逼真地在计算机屏幕上再现真实世界。真实感图形绘制是计算机图形 学的重要组成部分。它综合利用数学、物理学、计算机科学和其它科学知识在计 算机图形设备上生成像彩色照片那样的真实感图形。随着多色彩高分辨率光栅图 形设备的普及,真实感图形绘制技术在各个领域中得到广泛应用,日益受到人们 的重视,发展速度极快。利用计算机绘制真实感图形具有很大的实用价值。面对 己经取得的巨大成就,计算机图形的生成仍面临着很多挑战。在图形绘制中常常 要根据现实世界中的真实情况来进行图形绘制,希望得到的绘制结果尽可能真 实。在电影中用计算机模拟的许多暴风雨、火灾、地震和其它的自然灾难就是这 样,为了获得具有真实效果的灾难场面,根据相应自然现象的物理性质进行绘制。 但是由于物理现实的复杂性,会在取得足够质量绘制结果的基础上进行一些简化 第1章绪论 以加速计算处理。 总的来说,绘制作为计算机图形学中的重要领域,其是一个复杂、耗时的过 程。如绘制一个只有几个物体和光源的场景,需要计算每个光源在物体上每个点 产生的影响。因此要在计算机图形生成的高质量和生成所需要时间之间进行平 衡,即在生成高质量图形效果的同时保持绘制的高速度。为了和使用者能够进行 交互,绘制系统在生成具有真实的图像效果的同时,还需要达到比较高的绘制速 度,最好高于30帧/秒,至少15帧/秒(FPS),否则系统就会出现停顿,不能形成流 畅的画面。 在一些绘制中,实时性也许不是很重要。只是需要等待一段时间才能得到绘 制的最终结果。此时可以通过软件来进行绘制处理,而不要特别去关心绘制速度。 但在实时绘制中,利用软件实现的绘制系统常常不能满足要求,只有借助于图形 硬件来加速处理。图形硬件在结构因为针对图形处理的需要,因此可以极大地提 高绘制处理速度。 1.4本文的工作和结构安排 本文在认真研究了3D图形学原理的基础上,尝试采用自顶向下(Top.Down)的 方法对GPU几何处理部分(包括几何变换和三维裁剪)进行FPGA设计实现,作为 GPU的辅助功能模块,减轻GPU的运算负担,以达到加速的目的。主要研究内容 有:3D图形学技术的发展状况;3D绘图管线介绍;几何处理技术研究;几何处 理功能单元的FPGA实现等。 文文包括五个章节,其结构安排如下:第一章为绪论部分,主要介绍3D图 形学技术的发展状况,以及本文所用到的软件和硬件;第二章介绍3D图形的实 时绘制管线,介绍绘制管线的各个处理阶段:第三章介绍了几何变换和三维裁剪 技术;第四章对3D图形的集成电路设计进行了相关研究:第五章为几何处理在 FPGA上的实现,包括几何变换系统和三维裁剪单元的设计;第六章总结与展望。 9 第2章3D图形的实时绘制管线 第2章3D图形的实时绘制管线 2.1引言 在现实世界中,管线概念的表现方式非常之多,如输油管道、工厂的装配线、 滑雪缆车等等,对于图形绘制来说,同样也采用了管线的概念。 根据OpenGL ES 1.1标准141)在实时计算机图形学中,同样存在着如图2.1所示 的管线结构,在概念上可以粗略地分为3个阶段:应用程序、几何以及光栅¨5】。 这种结构是绘制管线的核心机制,在实时计算机图形学中也应用广泛。在绘制管 线中,每个阶段也有可能就是一条管线,这就意味着它可以包含几个子阶段。一 个管线阶段应该与其他管线阶段同时执行,但是为了满足高性能的要求,也可以 对它们进行并行化处理。 图2.1 实时绘制管线的基本结构 最慢的管线阶段决定绘制速度,即图像更新速度,这种速度一般用如s来表 示,也就是每秒绘制的图像数量,或者用Hz来表示。由于涉及到管线,因此不 能将想绘制的所有数据通过整个管线的时间进行简单相加,这就是管线的特点, 它允许某些阶段做并行处理。如果能够确定其中的瓶颈位置,也就是管线中最慢 的阶段,同时知道所有数据通过该阶段需要花费的时间,就可以计算出绘制速度。 2.2绘制管线f151 2.2.1应用程序阶段 由于应用程序阶段是通过软件方式实现的,因此开发者能够对该阶段发生的 情况进行完全控制,可以通过改变实现方法来改变实际性能。而其他阶段,由于 它们全部或部分建立在硬件基础上,因此要改变实现过程非常困难。即便如此, 仍然有可能改变几何和光栅阶段所消耗的时间。例如,可以在应用程序阶段通过 减少三角形数量来达到此目的。 在应用程序的末端,将需要绘制的几何体输入到绘制管线的下一个阶段。这 些几何体都是绘制图元(如点、线、矩形等),最终需要在荧幕上(具体取决于 10 第2章3D图形的实时绘制管线 3.投影 在光照处理以后,绘制系统将开始进行投影。目的是将视体变换为一个单位 立方体。这个立方体的顶点是(.1,.1,.1)和(1,1,1)。单位立方体也称为规范视 体(Canonical View Volume)。投影主要有两种方式:正投影(平行投影)和透视投影。 J下投影的可视体通常是一个矩形盒子,正投影可以把这个视体变换为单位立 方体。工F投影的主要特点是平行线在投影变换以后依然平行,这种变换是平移和 缩放的组合。 透视投影比正投影复杂,这种投影方式下,物体距离相机位置越远,投影之 后就变得更小。平行线在投影之后可以相交。透视投影变换与人类感觉物体大小 的过程非常相似。从几何说,视体也称为锥体,即一个以矩形为底面的被截金字 塔,同样也可以将这个锥平截投体变换为单位立方体。 正投影和透视投影都可以通过4X4的矩阵来实现,在任何一种变换以后,都 可以认为模型位于归一化处理之后的设备坐标系中。投影变换后产生的图象的z 坐标系将不存在,投影以后模型从三维变成二维。 4.裁剪 只有当图元完全或部分位于视体内部的时候,才需要将其发送至光栅阶段, 在光栅阶段把这些图元在屏幕上绘制出来。当一个图元完全位于视体内部的时候 那么它可以直接进入下一阶段。完全在视体外部的图元,将不会进入下一阶段, 没有必要对它们进行绘制。需要对那些部分位于视体内的图元进行剪裁处理。投 影变换后的图元只针对单位立方体进行剪裁,在剪裁之前进行视点变换和投影的 优势在于可以使剪裁问题变得比较一致,而且图元可以根据单位立方体进行剪 裁。 5.屏幕映射 只有在视体内部经过裁剪的图元,才可以进入屏幕映射阶段,进入这个阶段 的时候,坐标仍然是三维的。每个图元的x和y坐标变换到屏幕坐标系中,屏幕坐 标系连同z坐标一起称为窗口坐标系。屏幕映射首先进行平移,所后进行缩放, 在映射过程中z坐标不受影响,新的、和y坐标称为屏幕坐标系,与z坐标系一起 进入光栅阶段。 2.2.3光栅阶段 给定经过变换和投影的顶点、颜色以及纹理坐标,光栅阶段的目的就是给每 个象素正确着色,以便正确绘制整幅图像,这个过程称为光栅化,也就是把屏幕 空间的二位顶点转化为屏幕上的像素。屏幕空间有一个z值(深度值)、一种或多 种颜色,以及一组或多组纹理坐标,其中纹理坐标会与顶点或者屏幕上 第2章3D图形的实时绘制管线 的z缓冲器内容进行比较。如果新得到的z值小于z缓冲器中的z值,那么说明即将 绘制的图元与视点的距离比原来距离视点最近的图元还要近。这样,像素的z值 和颜色就由当前图元对应的z值和颜色进行更新。如果计算出来的z值大于z缓冲 器中的z值,那么颜色缓冲器和z缓冲器中的内容就不变。z缓冲器算法非常简单, 具有O(n)的复杂度(n为需要绘制的像素的数量),知要对每个图元计算出对应像素 的z值,就可以使用该方法.z缓冲器算法中,像素绘制的顺序是任意的,这也是 它得到广泛应用的主要原因【2】。 为了提高绘制的真实感,纹理影射是一种有效的技术。值得注意的是,在使 用对顶点的法向量进行插值的Phong【331明暗处理方法绘制多边形时,光照的计算 将在光栅阶段进行,而不同于Gouraudl321明暗处理方法那样在几何阶段进行。 2.3小结 本章详细介绍了3D实时绘制管线的相关技术。在绘制管线中,点、线和三 角形都是绘制图元,它们共同构成了模型或者物体。在管线中,软件部分和硬件 加速部分之间存在经常性的交叠,而且存在一种将软件算法硬件化的趋势。此外, 价格、速度和质量上的权衡是非常重要的。从历史上看,图形硬件加速通常位于 管线的最后阶段,首先执行执行三角形光栅扫描处理。硬件的不断更新换代有力 地支持了管线这种概念,同时,随着显示图形复杂程度越来越高,比较高级的应 用程序阶段和几何阶段算法都尽可能利用硬件来实现。硬件比软件的唯一优势就 在于速度,而对于实时绘制来说速度则是至关重要的。 第3章3D图形绘制中的几何处理技术研究 第3章3D图形绘制中的几何处理技术研究 3.1引言 在前面第二章中提到,在3D图形绘制的几何管线部分包括几何变换和裁剪两 个部分,这两个部分真正进行的是几何处理功能。 在计算机图形学中,图形变换非常重要。通过变换,可以对实体、光源和相 机进行定向、变形,以及动画处理等等。此外还可以保证所有的计算操作在同一 个坐标系中进行,然后将物体以各种不同方式投影到给定平面上。虽然只有一小 部分操作需要运用图形变换来实现,但是却能充分说明变换在实时计算机图形学 甚至其他任何种类的计算机图形学中具有非常重要的作用。 裁剪是为了适合屏幕尺寸,减少后续图形处理工作量,提高3D图形加速效 率所必需的一个步骤。经裁剪后,只保留了视窗内我们可以看到的图元,后续的 其他图形处理步骤均只对这一部分图元进行。裁剪的要点是针对一个任意图元的 裁剪算法,这是提高裁剪速度的瓶颈所在。按空间分,裁剪可分为二维裁剪和三 维裁剪;按裁剪体分,裁剪分为平行投影视见体下的裁剪和透视投影视见体下的 裁剪:按裁剪对象分,裁剪分为线裁剪,三角面裁剪和多边形裁剪。本章重点分 析三维情况下三角面在透视投影视见体下的裁剪。 3.2几何变换技术 在计算机图形学中最通常的表示物体的方法是多边形网孔模型。一个物体由 ~系列多边形连接而成,而每个多边形又由一系列顶点(x,y,z)连接而成。如下图 3一l所示: 第3章3D图形绘制中的几何处理技术研究 vertices 图3.1 物体模型的数据结构 3D图形变换【2】f31【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 i y,z=Z f W 在计算机图形学中一般w取为1,则顶点的矩阵表示为Ix,y,z,117 用奇次坐标表示的平移变换这时可以表示为矩阵相乘的形式: 洲 0 1 0 0 O 1 t L r =丁× 00 1 因此,在奇次坐标系下任何变换的矩阵表示为: 17 第3章3D图形绘制中的几何处理技术研究 ● 石 ● y ● Z 1 『&口li刀g&m刎渤 l讹柙幽踟稽] l忍心够胁hom。影月窖。“s l I。 lI—,—j—z矽—‘,—曾。5—学—刀——f口——fj’。—刀———。—————————j—’_—————1——————一ll 缩放矩阵: 矿‘=S×矿 S: O OO Q S= 0 S。 0 0 O S: 0 O O O1 旋转矩阵: 对物体的旋转必须选定旋转轴,虽然旋转轴的位置可以任意,不过都可以转化 为平行坐标轴的形式,绕X,YZ坐标轴的旋转变换矩阵为: 1 O 0 O cos口 O 一sin口 O cos秒 sin 9 O 疋= O —sin目 cos臼 O O l R。= sin秽 O O cos毋 O O 0 1 0 0 0 cos口 一sinp R.= 0 O sin矽 cos口 O 0 O0 OO 10 01 投影矩阵: 目的是将视体变换为一个单位立方体。这个立方体的顶点是(.1,.1,.1) 和(1,1,1)。单位立方体也称为规范视体。投影主要有两种方式:J下投影(平 行投影)和透视投影。 正投影的可视体通常是一个矩形盒子,正投影可以把这个视体变换为单位立 方体。正投影的主要特点是平行线在投影变换以后依然平行,这种变换是平移和 缩放的组合。 透视投影比正投影复杂,这种投影方式下,物体距离相机位置越远,投影之 第3章3D图形绘制中的几何处理技术研究 后就变得更小。平行线在投影之后可以相交。透视投影变换与人类感觉物体大小 的过程非常相似。从几何说,视体也称为锥体,即一个以矩形为底面的被截金字 塔,同样也可以将这个锥平截投体变换为单位立方体。 币投影和透视投影都可以通过4X4的矩阵来实现,在任何一种变换以后,都 可以认为模型位于归一化处理之后的设备坐标系中。投影变换后产生的图象的z 坐标系将不存在,投影以后模型从三维变成二维,这罩以透视投影为例,如图3.2: ● j’ ,’%如弓.) · P(n,Jtr) ·。i。:二二二.?rqitxti。n p。i11l 、、(J 一 :/,。 7、’-■j r 、,. ’ ̄ ̄、、 、 、?1 X J j ‘Pr‘巧ection plane f image plane) Planc distance::一d 图3—2透视投影变换 该阶段也相当于一个矩阵变换过程: 1O 0 O x p 0l 0 O yp OO 1 O Z,, 0 O 1/d O 1 x。 O 0 0 0 y。 0 0 OO z— O 0 0 z p|d Q Xp yp Zp Z p|d 为了使w为l,进行一下除法即可得到投影变换后的坐标(寺《p。 3.3三维裁剪技术 3.3.1 2维裁剪算法 Sutherland.Hodgman算法I伸】将多边形边界作为一个整体,并根据窗口的每 一条边进行裁剪,可以得到J下确裁剪结果。通过依次按照裁剪边界的各边界来处 理所有多边形的顶点,可以实现这种操作。如图3.3所示,在对多边形的顶点集 进行初始化以后,首先用矩形左边界裁剪多边形,从而产生新的顶点序列。这些 新的顶点序列集可以依次传给右边界、下边界和上边界进行处理。在每一步产生 的新的输出顶点序列,将传递到下一个窗口边界的裁剪程序。 19 第3章3D图形绘制中的几何处理技术研究 /。 目口 原始彩边形 裁剪左边 裁剪右边 裁剪底边 图3.3逐次多边形裁剪示意图 裁剪顶边 沿着多边形依次处理顶点会遇到四种情况。在将相邻的一对多边形顶点传到 窗口的边界裁剪程序时,可以进行如下测试:(1)如果第一点在窗口边界外而第 二点在窗口边界内,则将多边形的这条边与窗口边界的交点和第二点加入到输出 顶点表中。(2)如果两顶点都在窗口边界内,则只有第二点加到输出顶点表中。(3) 如果第一点在窗口边界内而第二点在窗口外,则只有与窗口边界的交点加到输出 顶点表中。(4)如果两个顶点都在窗口边界外,那么输出顶点表中不增加任何点。 3.3.1.1区域编码 对一条线段的端点,要判断其在可见区域还是不可见区域,可用端点编码法 来确定。如下图所示,延长裁剪窗口的边界,将平面分成9个区域,每个区域用4 位二进制代码表示,称为区域码。约定4位码中最右边一位为第1位,如图3.4所 示,编码规则如下: 第一位置1:如果线段端点位于窗口左侧 第二位置l:如果线段端点位于窗口右侧 第三位置1:如果线段端点位于窗口下面 第四位置1:如果线段端点位于窗口上面 因此,根据端点编码相应位的值即可判定该点是否位于可见区域。 100l 1nor lOlO 0001 0010 010l O100 0110 第3章3D图形绘制中的几何处理技术研究 3.3.1.2线段裁剪算法 a)Cohen.Sutherland线段裁剪算法【181 这是一个最早流行的线段裁剪算法。该算法通过初始检测来减少要计算的交 点数目,从而加快线段裁剪算法的计算速度。 该算法的关键在于总是要得知位 于窗口之外的一个端点。这样位于此端点至交点之间的区段必为不可见,故可抛 弃。然后此算法继续处理线段被裁剪后的剩余部分,此时取交点来代替裁剪线段 的一个端点。Cohen.Sutherland算法可简述如下: 对于每条窗口边界: 检查线段片只是否为完全可见线段或可以抛弃的显然不可见线段。 若只在窗口外,继续执行算法;否则交换只和只。 用弓只和窗口边界的交点取代异。 为了说明Cohen.Sutherland线段裁剪算法的实现过程,下面以图3.5来进行详 细说明。 P4 图3—5 Cohen—Sutherland线段裁剪算法 对于线段只只由下端点只开始,依次按左、右、上、下边界对暑进行检查, 发现端点位于裁剪窗口下。然后我们找出线段#只与底边界的交点异’,并舍弃只 到只’之间的线段。线段现在缩短到从只’到只之间。因为最在裁剪窗口之外,所 以使用各个边界检查只,发现只位于窗口的左边。然后计算出交点只‘,但该点 在窗口的上方。因此,再做一次求交计算得到交点只”,并且储存眉’到只”的线 段。该线段的裁剪就处理完毕了。下面继续下一条线段的裁剪。下一条线段只只 的端点只在裁剪矩形的左边,所以求出交点只’,并且舍弃从只到只’的线段。检 查只’到只线段的端点编码,发现剩下的线段在裁剪窗口下方,也应该舍弃。 b)中点分割算法120l 中点分割方法是Cohen.Sutherland算法的特例,Cohen.Sutherland算法需要 求线段与窗口边界的交点,而中点分割算法将上述直接求交点的过程用折半查找 (即求中点)的方法来代替。中点分割算法也采用对线段端点进行编码的方式来 判断完全可见的线段,对于既不是完全可见也不是显然完全不可见的线段,中点 第3章3D图形绘制中的几何处理技术研究 分割算法分别求离两个端点最近的可见点,这两个最近的可见点(如果存在的话) 之|’ElJ的线段就是原线段的可见部分。中点分割算法的思想: (1)中点公式 x石:=—苎L±—兰二 2 11,,=:二_些L—±二丝三 ’ 2 (2) 中点分割求交点的规则 如图3—6中所示,当线段只最求出重点P(羔寺量,丛专丝)后,舍弃线段的 哪部分,由下面规则决定: 图3—6中点分割算法 (i)如果只与尸同侧,移动鼻点;(即可能的交点只能出现在职段) (ii)如果只与JP不同侧,移动只点;(即可能的交点只能出现在暑尸) (2)算法步骤 对线段的每一个端点: 若该端点可见,则它为离另一个端点最远的可见点,处理结束。否则继续。 若线段为显然不可见,则无输出,处理结束。否则继续。 在中点只处将线段片只一分为二,并以乞作为最远可见点的初始估计,对 所得的子线段只e,和匕e分别做上述检查。若匕£为显然不可见段,则抛弃, 这时中点e,为最远可见点的过估计点,继续处理#乞。否则,中点己为最远可 见点的欠估计点,继续处理只只如果线段非常短以至于它的中点已达到机器表示 端点的精度,则计算此点的可见性,处理结束。 中点分割算法比较适合硬件实现。 3.3.1.3逐次多边形裁剪算法实现过程 下面说明如何根据上述算法来对下图3.7的三角形进行裁剪。首先是左边界 的裁剪。V1v2与左边界有交点,且v1在窗口边界内,则在顶点存交点v1’:V2v3 与穿过左边界,且v2在边界外面,则在顶点表中保留交点v2’和v3;v3v1在窗口 边界内,则保留v1于顶点表中。接着,将顶点表送入右边界裁剪程序,由于都在 右边界内,所以都存于顶点表。以此类推,得到裁剪后得结果为多边形 点都要4个坐标(xyz,w)来确定。在w不等于0的情况每一点的三个位 (x,y,z).>(x/W’y/w'z/w,1).>(X,Y,Z)一般情况下,没有特别要通常w取l。但在 可以取 y=z=如图 3.3. 3维裁剪算法研究 特定的变换下,w不等于1。这时可以认为物体是一个4间上。 置向量分别除以w,从而得到一个仍用3个坐标描点(X,YZ); 下却无法描述出来。而齐次坐标的方法恰好可以解决这个。这个方法中每一 某些点(特别是无限远处的点)和确定的变换(包括平行和透影)在这个坐标系 的矩阵来描述。位置向量乘以这个矩阵可以产生一个变换新的位置向量。但 定一个点在三维空间中的具体位置。如旋转变换和比例缩可以用一个3木3 三维物体的描述和变换通常是在笛卡儿坐标系下完成。(x,z)可以完全的确 3齐次坐标 图3-8逐次形裁剪流水实现 vl———◆{v2r’.Y,l————◆:竹’.v2I vl——~’ 图3.8是一个流水线面三角形的操作。 v, v2……一净~Z………一’vl‘…'帕t3 、3 …~—≯ ……~2’.v v2’ …—啼 '. —————呻 ¨ ,一 i . V1 图7逐次多边形裁剪 一 j 。..,‘| 、?,;一一一 。 第3章3D图形绘制中的儿何处理技术研究 ,、 W p(xJ弘z,w) / / , / / W:l /7\p,(x/w,y旭z/w,1) / \ x=(x,y,z,1 图3·9并次裁剪 所有的描述真实的点(X,YZ)的齐次坐标系下的点(x,y,z,1)都位于从原点到 (X,YZ)的直线上。 将透视投影视见体变换为平行投影视见体后,可以使用为平行投影视见体优 化的单裁剪过程,但这个过程必须在齐次下才能有正确的结果,当出现负的w 时,这样的点可以在齐次坐标而不是三维中被正确裁剪。三维平行投影规范视见 体由一1≤x≤1,一1≤J,≤1,一1≤z≤0定义。通过用X/W代替x,Y/W代替y,Z/W 代替z,代入可求出齐次坐标中对应的不等式,对应的平面方程是: X=一∥,Ⅳ=∥,J,=一形,y=∥,Z=一∥,Z=0 需要分别考虑W>0和W<O的情况,结果可以表示为: ∥>0:一∥≤X≤肜,一∥S】厂≤∥,一形≤Z≤O ∥<0:一∥2Ⅳ≥∥,一∥≥y≥∥,一∥≥Z≥O 故当可能出现w<0的时候,需要在这两个区域进行裁剪。对于两个端点具有 相反符号的线段,常用的解决方法是先在一个区域内进行裁剪,再将两个端点反 号,再在同一个区域裁剪,即可完成一次裁剪过程。 我们研究的算法都是基于透视投影视见体下的裁剪,视见体示意图如图3.10: 第3章3D图形绘制中的儿何处理技术研究 y, /左一 / √\ I \ \\\ 右平面 \ 下平面、\ 图3-lO透视投影视见体 (一)基于编码和二次求交的三维裁剪算法实现原理 算法一主要是在透视视见体下的裁剪,在进行具体的裁剪工作前,我们直接 变换到45度透视裁剪体,不作归一化处理,全部裁剪完成后缩放并错切转换到 二维视平面再做后续的光栅化工作;裁剪采用中点分割法即可,裁剪可以按照前 面的编码分别裁剪方法来进行,只需要传裁剪面的参数进去。也可以考虑六个面 采用六个裁剪程序分别裁剪,可以实现裁剪的并行化处理。除了坐标外,每个新 的顶点的法向量,颜色,光照都要进行线性插值,可以在求交算法中同时确定下 来。 裁剪的主要流程是:先作求交运算求出所有交点,并进行正常的排序操作, 排序完成后,在合并OUT点时,仍按照正常的流程(程序相同)进行OUT点 求交运算(调用前面的中点分割算法即可),求交后,在输出顶点顺序数组前, 再进行一次OUT点判断,对于情况三,发现求交结果仍为OUT点,则将二次 求交得到的OUT点去除,其他烈点按原来的顺序输出,并分割成三角形。目 前编写的程序的算法简单框图如图3.11所示: 第3章3D幽形绘制中的儿何处理技术研究 _二次求交 图3.1 l算法框幽 详细流程图如图3一12所示: 26 第3章3D幽形绘制中的儿何处理技术研究 豳 囱 。一 .……………J…………. r 下面逐一说明: (i)顶点编码,图3.13。 图3.12算法详细流稃图 27 第3章3D图形绘制中的儿何处理技术研究 前裁剪平 z5z(】1lin 幽3—13透视投影视见体侧视图 首先将裁剪视见体(单位立方体)分成27个立方区域(6个面区域,8个顶点 区域,12个边区域,1个体内区域),并对27个区域行编码。使用6位的编码,约 定6位码中最右边一位为第1位,当满足条件时,其对应位为真: 第1位….点在视见体的前面…一z<z(min) 第2位….点在视见体的后面…一z<z(max) 第3位….点在视见体的左面…一x<一z 第4位….点在视见体的右面…一x>z 第5位….点在视见体的下面…一y<.z 第6位….点在视见体的上面…一v>z (ii)简单去除,如图3.13所示。 对于近远2个平面,简单去除依据三个顶点的z坐标来判定。对于4个侧面, 以y=z面为例,只要满足三个顶点的y.z>=0即可判断三角形可以简单去除。若 部分顶点不满足,则与y=z平面相交,再判断x=z和x=.z两个侧面,若其中任 何一个满足可以简单去除(对于x=z,x.z>=0;对于x=一z,x+z<=0)的条件,则同样去 除即可。 第3章3D图形绘制中的几何处理技术研究 y J\ A ℃ ≥c/ \ y =z/ / B / / / / \ Z 霄龄 \V:—z 、 图3.13简单去除图 / y / K ~||,< \. 、 夕B 一≤ 2— >< 3 i \ 图3.14顶点排序图 (iv)裁剪结果顶点的排序 对于裁剪结果得到的顶点排序问题:如如3.14所示,已知三角形ABC,已 求出所有交点(包括OUT点),若以A顶点为出发点,按AB,BC,CA的顺序, 对于AB,按AB上的交点离A点距离的近远排序(若A在视见体内则A点也参 加排序,以下同),对于BC,按BC上的交点离B的近远排序,CA按交点距C 点的近远排序,得到上图所示的顶点顺序。排序方法:取顶点与A点x,y,z的坐 标中均不相同的一组数值,如x均不相等,则按|x-x(A)I绝对值大小排序即可。若 有交点在面外,则依据OUT点的求交算法找出边上的点作为交点,顺序不变。 最终求得所有有序的顶点。 交点数目最少为2,最多为6。交点求出后要保留所在的区域编码,方便后 面运算。 (v)OUT点处理的边界条件 对于近平面:y(or x)>z(near)或<一z(near) 对于远平面:y(or x)>z(f打)或<一z(far) 对于侧平面:疹z(far)或z<z(near)或y>z或y<.z或x>z或x<.z 注:最后一个条件要根据具体的侧面选用相应的条件。针对每一个点所处的位置 选用上面的部分条件,并且有一条满足即为OUT点,边界上面内的交点视为IN 点。 (vi)求交运算 求交算法采用了典型的Sproull—Sutherland中点分割算法: 算法原理: 第3章3D图形绘制中的几何处理技术研究 对线段的每一端点: (1)符P2存窗口内,则P2就是离P1最远的可见点,处理结束,否则继续: (2)若P1P2完全不可见,则无输出,处理结束。否则继续: 取P1 P2的中点Pfn,若Pm点在窗口内部,则处理PmP2线段来寻找P1的最远可见点,即 用Pm代替Pl,执行步骤(2):否则P2用Pm代替,执行步骤(2).直到Pm与线段端点的 距离达到分辨率精度为止. (vi i)线性捅值 在求出交点的屏幕坐标后,新顶点的位置,法向量,颜色,光照等要进行线 性插值。在求交算法中,每计算出一个交点,都要插值出所有的顶点数据。插值 尼^一一=,导~.,一咎肿锌,斟期导i爪螂柏n的鳓佴I。酊一蝴个目州r|口阮I 方法:先根据已知2个顶点和新交点的屏幕坐标得出插值系数: 艾2一戈1 y2一夕1 z2一z1 然后利用插值公式: C=A+k(B-A) 计算出所需参数。 (二)降维裁剪算法原理 降维裁剪的思想,具体来说就是对于所有要进行裁剪的图元,先在一个裁剪 面上全部裁剪完毕,所有裁剪出来的图元再在另一个裁剪面进行裁剪,就这样一 个面一个面的裁,所有裁剪面都裁完后再进行分割并输出即可。具体在每个面上, 均采用的是二维裁剪的方法。裁剪流程如图3.15所示,而图3.16为对一个面进行 裁剪的算法流程图。 (注:为减少计算量,去掉了后平面裁剪,这基本上不影响裁剪效果) 第3章3D图形绘制中的JL何处理技术研究 预处理后的三角形 顶点数据 / 前平面 左平面 右平面 下平面 上平面 输出后再分割成 三角形 图3-15整体架构流程图 (1)降维裁剪 之所以说是降维裁剪的思想,是因为在任何一个裁剪面上,都是只进行二维 裁剪操作。比如在上平面裁剪,可以认为是只在Y—Z平面上进行裁剪。如图3.17 所示。 三角形的一条边P1P2与透视视见体的上平面y=z相交于P点。可以看作是 x=0二维平面上的两点(yl,z1),(y2,z2)构成的线段与直线y=z的交点。联 立方程组: 少一少1=2兰丛(z—z1) (1) Z2一Zl 少=z (2) 这样可以用线与线求交的公式法计算出交点P的二维坐标(y,z),再根据 比例关系: y—yl—x一五 儿一yl x2一葺 求出交点P的x坐标即可。 第3章3D幽形绘制中的几何处理技术研究 /\|| ≮乡。 广J’——1 { 卜9 印④ 口 a、 b1 图3.16一个面的裁剪流程图(图a适刖丁每一个顶点,而图b只适心丁最后一个顶点) 了十 \、前辛面 主 N 、 \ \ \ 下平面\ 、 图3.17上平面裁剪 32 第3章3D图形绘制中的几何处理技术研究 每个面都可以按照以上思想计算交点坐标。 前平面更简单,由于前平面z 值已知,直接根据比例关系就可以求出交点的三维坐标。 (111数据预处理 三角形顶点的数据格式是: typedef stmct J[1lyVertType{ Vector3 D Position: //位置xyz Vector3D Nonnal; //归一化法向量xyz Vector4D ScreenSpacePosition;//屏幕坐标xyzw FloatColor Color; //漫反射颜色唱ba FloatColor speColor; ,/镜面反射颜色唱ba UV2 uv: //纹理坐标u,v noat VercSize: //顶点精灵大小 BOOL IsLighted; BOOL IsNew: uint8 ClipFlags: uint8 Flags: //已经计算过光照和纹理坐标 ∥这个顶点是裁剪后新增的 //裁剪用标志 //一些其它有用标志 )myVen]陟pe; 裁剪用到的输入数据是屏幕坐标Vcctor4D ScreenSpacePosition,首先用它和 裁剪边界确定位置编码uint8 ClipFlags。编码采用6位编码即可。由低位到高位, 裁剪边界如下: 第1位….点在视见体的后面…一z>1(省略后平面裁剪) 第2位….点在视见体的前面…~z<z(min) 第3位….点在视见体的上面…一y>z 第4位….点在视见体的下面…~y<.z 第5位….点在视见体的右面…~x>z 第6位….点在视见体的左面…一x<.z (三)数据结构及顶点排序 由于裁剪面较多,为减少内存消耗,采用Pingpong结构来存储中问数据。所 有顶点数据存放在一个二维数组里面,对于任一个三角形,这种方法裁出来的顶 点数目最多为8个,所以数组大小为myVercType fV[2][8]。以后所有的数据处理 操作都在这个数组罩进行。下面举例介绍裁剪及排序过程。 第3常3D图形绘制【{J的儿f口』处理技术研究 剀3·1 8:;!f』0试平台 (II)测试方法 曰日if实现的3D场景卜-的裁剪采用透视投影下的裁剪方法,分透视视见体和 平行视见体两种j二要方法。其主要裁剪流程是首先是把传递过来的三角形通过第 ‘个裁剪嘶,得到一个多边形,然后在把该多边形传递到下一个裁剪面进行裁剪, 以此类推,直剑通过最后一个裁剪面,就完成了对一个三角形的裁剪。 针对裁剪算法的特点,我们可以从以下方面入手来进行测试: a、运行速度的评价 测试。个特殊场景一~具有固定裁剪三角形数目的场景,统计其裁剪时 问,评估算法效率。 b、运行效果的评价 测试一些简单场景,主要观察一F是否正确地对不同位置的三角形进行了 裁剪。 c、特殊情况分析与处理 构造一些特殊三角形,指出同前算法中存在的部分问题和解决方法的建 议。 fIII)测试步骤 分别有针埘性的选用4iI问的场景来测试单一测试点。给出相关测试数据,进 行分析评仙。 (IV)测试场景 场景:运行速度评估场景 选用件f叫’位置放置1000个二角形的方式,所有三角形大小一致即可,方 使实现副j芷戡剪=_i角7髟数目的裁剪叫问统计。 鹚3 7≯3D蚓形绘制中的儿{口f处理技术研歹‘ 测试过程中,首先尽可能的去掉光栅处理部分,包括最后的屏幕划线功能。 测试时可以分别测试进行裁剪的时问(裁剪1个面一3个面)和不进行裁剪的时 |'|1 J, :者相减即为裁剪耗时。然后,我们加上光栅化步骤,再测试1个时间,进 行比较。 rV)特殊场景 主要i寸论狭长三角形的问题产生和解决方法。 (VI)测试结果及分析 在去除光栅化部分的测试中,我们得到以下结果,如图3.19所示: , 驯}一/、≯, }t ,j川}—一;, /一r… i 无光栅一裁2个【可 I到3.19无光栅下的裁剪 无光栅一裁3个面 在加上光栅化处理的情形下的测试结果如下,如图3—20所示: 第3章3D图形绘制中的,L何处理技术研究 有光栅一裁2个面 幽3—20有光栅的裁剪结果 有光栅一裁3个面 fVII)测试结果的对比和分析 分析:对于裁剪1000个三角形,无光栅情况下的每帧运算时间计算如下(单 位:毫秒) 表3—3无光栅时的裁剪时间 状况 不裁 戗1_咖(2000) 裁2面(3000) 裁3面f4000) 总时间 2. 89 3. 35 3.67 4. 16 从帧速上看,对于裁剪1000个三角形,每多裁一个平面,速度降低约30 帧。裁剪一个面平均耗时为O.42ms。当裁3个面时,约占几何阶段总耗时的30 %。对所有顶,点的处理占用了大部分时|’自J。 而对于裁剪1000个一t角形,在有光栅阶段下的每帧运算时间计算如下(单 位:毫秒): 状况 小战 表3.4有光栅时的裁剪时间 战1血f2000) 找2面(3000) 战3面f4000 J 总时问 404. 86 454. 75 500. 03 768. 66 由于填充时填充面积对速度影响比较大,在测试中不同角度卜‘帧速有较大的 波动。但很明显,光栅化处理对速度的影响非常大。对_J二1 00(J个三角形,在不 哉的情况F的速度为4()4.86nls。是无光栅处理的140倍。是裁剪一个面耗时的 第4章3D图形集成电路设计相关研究 第4章3D图形集成电路设计相关研究 4.1引言 近■十年来,电脑绘图已成为人机介面中,最重要的资料显示方法,并广泛的 运用在各种应用之中。例如计算机辅助设计(CAD),医疗方面的影像处理,以 及电脑游戏等等。尤其是3D电脑绘图,到了90年代初期,很快的从高深的技 术领域,扩展到非技术领域上的运用。而多媒体(multimedia)以及虚拟现实 (virrtual reality)产品现在越来越普及。不但是人机介面上的重大突破,更在娱 乐有用中扮演着重要的角色。而这些的应用,多半是以低成本的即时3D电脑绘 图技术为基础。2D电脑绘图是一种常用以将资料和内容表现出来的普遍技术, 特别是在互动应用。另一方面,3D绘图是电脑绘图中一股越来越大的分支,它 使用3D模型和各种影像处理来产生具有三维空间真实感的影像。使用者一直要 求3D绘图系统有更好的效率和更低的价格,而半导体技术的进步使它成为可能。 VLSI技术使个人电脑能够做到工作站级的绘图处理器的效果。VLSI技术的长足 进步之下,因为量产所带来的价格优势,使得3D电脑绘图的加速硬件越来越普 及,甚至成为电脑中人机介面的标准配置。 4.2 3D绘图硬件的设计目标【2l】【22】 (i)即时着色(realtime Rendering) 我们可以把需要快速反应时间的3D应用分成以下三大类: 1.即时应用(Real Time Application):每秒必需输出数十张画面,通常为24到 30张。 2.交谈应用(Interactive Application):一张画面的产生时间需少于一或数秒。 3.批次应用(Batch Application):一张画面的产生时间大于数十秒。 由于多媒体和虚拟现实的盛行,电脑绘图也被要求要拥有即时着色的能力。 然而巨大的计算负荷,资料的存取及记忆体频宽的问题,使得大多数的CPU难 以负荷3D绘图的要求。因此为了速度的要求,使用特定的硬件来解决使最自然 的方式。 (ii)影像品质(Image Quality) 3D绘图被广泛地使用在许多领域,上至CAD,下至电脑游戏都可以见到它 的应用。随着电脑效能的增进,对影像的品质要求也越来越高。故可以预见的是 每个框架(frame)的复杂度会越来越高,同时使用一些新的算法,如texture 第4章3D图形集成电路设计相关研究 mapping,也可以有效地增加影像的真实度。综合以上所述,计算复杂度,资料 储存,和资料的负荷也会随之增加。 (iii)系统整合(System Integration) 现在的消费性电子产品中,多媒体扮演了越来越重要的角色。一个多媒体系 统整合了文字,绘图,影像,和声音。为了使这么多的资料同步,多媒体系统必 须在短时l、白J内处理相当大量的运算操作。因此需要不同的处理器,来加强一个多 媒体系统中,不同部分的处理能力。3D处理器是其中的一员,它需要和其它的 处理器协同工作。在这样的考虑之下,许多设计使用了最常见的f.r锄e bu虢r系 统来加快3D绘图的速度。虽然有记忆体频宽的瓶颈但比起重新设计一个与目前 架构不同的新架构,沿用旧架构可以很简单地将3D绘图处理器整合进现有PC 的多媒体显示系统中。另一方面,为了达成相容性和系统整合,设计师不只要考 虑硬件的设计,同时也要顾忌软件的开发。一些已经成熟的软件API可以用来 当做设计硬件时的参考,因为这些API正是使这些3D绘图处理器得以推广的动 力。 4.3标准3D绘图着色管线【15】【21l【22】 为了加快3D绘图的速度,标准3D绘图着色管线使用一种最常见被使用到 的方式。接下来介绍目前最常见的3D绘图管线。 在图2.1中,可以看到整体着色的管线根据不同的座标系统而分割成数个部 分。物体定义(0bject definition)里的物体是一些3D模型的描述定义,所使用 的座标系统参考其本身的参考点,故称之为本地座标(Local C00rdinate Space)。 要合成一张3D影像时,各个不同的物体从资料库中被读取,并转换至一个统一 的世界座标(wbrld Coordinate)。其次,就像真实世界中的照相机一般,我们需 要定义观测点(View Point)的位置。由于绘图系统硬件解析度的限制,必须将 连续的座标转换至含有X及Y座标,硬件深度值(常称为Z座标)的3D荧幕 空间。在做完隐藏面的消除(hidden surface removal)以及将物体以像素的方式 描绘出来后,frame bu仃er会保留结果的图像并且将其输出至荧幕上。通常将处 理这类标准管线的各单元分成两大部分: 1.几何转换子系统(Geometry Subsvstem) 2.着色子系统(Raster Subsvstem) 43 第4章3D图形集成电路没计相关研究 units将部分在观测空间中的primitives做适当的切割,lighting stage利用 如Phone illumination model对primitives做处理。在这儿所需要的运算有加, 乘,向量内积等。通常1ighting stage是整个系统加速时会遇到的最大障碍。 摩◆图~争圊一恩,网 4t3。l 3D几何管线 ’{黼鬻H僦H勰H:薰H淼煞l \。。。。。。。.,.,『 、 。I/ \ 。./ \二£g曼鎏i望;/ 、......../ 图4—3 3D几俐管线 由图4—3可以发现几何转换子系统一共有两个座标变换,这是几何转换子系 统最重要的运算所在,多数为4x4的矩阵运算。在本地座标,世界座标以及观察 坐标中,其座标值均为三维且连续的。在这部分最重要的工作就是座标的变换, 因此提供这些座标转换运算功能的单元通常被称之为几何转换子系统。而在3D 绘图处理中,这部分的加速硬件通常被称之为“几何引擎”(Geometric Engine)。 另外,在前级有primitive的选取动作,可以决定primitive是否在可视空间中, 减少不必要的运算。而那些仅有部分在可视范围内的primitive,则会在clipping 中被削切乘符合观测空间的形状。由Ⅵew space转成Screen space时由一个 Perspective divide的动作,将观测空间座标除以一个常数w,并且利用3D Screen M印ping将座标转换至x.y荧幕座标(Screen Coordinate)。以备接下来的着色子 系统使用。当使用Gouraud Shading时,li曲ting module仅存在于几何转换子系 统中。 4.4 3D图形硬件【23 J 4.4.1图形处理单元 在大多数现代计算机系统中,3D图形管线处理过程中所需的复杂计算是通 过专用图形卡来完成的。在过去,这些计算是和其他通用计算一起在CPU上实 现的。随着3D图形学的进步,这些复杂的计算将会越来越占用CPU的时间而 导致其他应用程序必须去忍受性能上的恶化。因此,图形卡被引进到现代计算机 系统中来和CPU一起协同工作以缓解3D图形中需要大量的矩阵和向量运算的 紧张程度。每个图形卡中都有一个称为图形处理单元(GPU)的微处理器用来包括 坐标系统中的几何和映射等计算。图形卡通过高速总线接收和传递处理结果到 RAM和CPU。这些高速总线之间的GPU和RAM是必要的,因为虽然显卡有一 些板载内存,但通常不是足够大能够存储以每秒百万计速度进行计算产生的结果 并作了回应给CPU,所以计算机RAM也要被使用到。 45 第4章3D图形集成电路设计相关研究 GPU处理矩阵和向量运算的速度是如此的快,以至于人们开始将GPU用于 其他非图形学的用途,如生成立体图象。与此同时,人们开始寻求老一代GPU 所基于的ASIC的替代品。许多产商开始以应用程序专用的处理器(Application Specinc Processors’ASPs)的形式向GPU中引进有限的可编程性,在其中运行专 门的应用程序来提高处理器的性能。尽管对GPU来蜕是一个前进,但由于其可 编程的有限性以及不能提供完全的可配置性能,因此,由于FPGA具有高度的可 配置性能,人们更加青睐于用FPGA来实现GPU。 4.4.2 FPGA作为替代 如日玎面所说,FPGA是一种完全可配置的硬件器件,能够简单地进行编程并 且价格便宜。它们的配置性能很通用以至于能够模仿任何类型的硬件,包括复杂 的GPU。这一特性使得任何人当有对图形处理有新的想法和算法时可以用硬件 电路来实现。FPGA的可动态配置特性使得设计具有更多的并行性能。也就是说, 不同的位模式可以从片上RAM下载到FPGA来完全更改芯片的配置以适用于当 6U的应用,而这一切都发生芯片已经被编程但却一直工作在计算机中。 尽管FPGA适用于小批量生产,而ASIC则在大批量生产上具有优势,但由 于两者相似,FPGA设计能被移植到ASIC上。这使得FPGA是一种完美的硬件, 当人们的设计有错误时可以修改设计并重新载入直到设计能通过ASIC产商大量 生产。FPGA甚至产生了一种新的“软”硬件,这些硬件的代码用硬件描述语言 来实现并在丌放许可证的条件下共享,比如opencores.o唱,在这里我找到了一些 对我设计有用的模块。现在有一个小组成员开始了开放图形项目(0pen Gr印hics Proiect【341),他们的目标是在许多较少使用的操作系统上利用开源驱动在FPGA 上实现开源GPU。 如前所述,FPGA具有可能替代GPU的一些优点,同时也有一些不利因素 限制着。一个障碍是速度。目前FPGA的速度比不上ASIC,当在图形管线中速 度是一个必要因素时这将是一个大大的障碍。ASIC的另外一个优势是比FPGA 具有更低的功耗,而这在移动设备中是相当重要的。FPGA的另外一个缺点是需 要使用宝贵的存储空间来存储配置信息。但是应该看到,FPGA在速度和面积上 的改进速度现在正超过GUP和ASIC的速度,所以按照摩尔定律口,FPGA在不 久的将来一定会得到很大的改进。 4.4.3 FPGA作为辅助 J下是由于这个原因,虽然FPGA可能永远不能完全代替专用的图形处理单 元,但是我觉得它可以很好地与GPU和CPU结合,提供更加可靠的并行性运算 第4章3D图形集成电路设计相关研究 服务,或者节省更多的时隙。FPGA可以提供的其他优点就是能很好地修正BUG, 使得功能趋向正确。 4.4.4 Xilinx FPGA结构简介(Virtex II系列)‘241 自1985年Xilinx公司推出第一片现场可编程逻辑器件(FPGA)至今,FPGA已 经历了二十年的发展历史。在这二十年的发展过程中,以FPGA为代表的数字系 统现场集成技术取得了惊人的发展:现场可编程逻辑器件从最初的1200个可利用 门,发展到90年代的25万个可利用门,乃至现在,国际上现场可编程逻辑 器件的著名厂商A1tera公司、Xilillx公司又陆续推出了数百万门的单片FPGA芯 片,将现场可编程器件的集成度提高到一个新的水平。 FPGA简化的结构如图4.4口所示。FPGA内部最主要的、设计过程中最需要 关注的部件是CLB(ConfigurabIe Logic Block,可配置逻辑块)、Inp州Output Block(输入/输出块)和BlockRAM(块RAM)。 图4.4 Xilill)(FPGA结构 (i)可配置逻辑块CLB 每个Virrcex.II CLB包含四个slice,如图4.5所示。Slice内部包括2个LUT(查 找表)、2个触发器、多路开关及进位链等。CLB内部的4个Slice是互相独立的, 各自分别连接开关矩阵(Switch Ma缸x)以便与通用布线阵列(General routing Matrix)相连。 47 第4章3D图形集成电路设计相关研究 Swifch Matrix 莎TBuF xDYl eouT 型竺岖盘 ■■■●■■●■■●■●_■■●■■■■.| 一 一’L‘ —d可氰园‘ SIice XOYl ClN SIice XOY0 Fa3t COnnects lo neighbOrs GiN 图4.5可配置逻辑块CLB (ii)输入输出块(Input/0utput Block) Input/Output Block是FPGA对主要组成部分之一,作用是为FPGA提供内 部资源与外围电路之间的接口,提供输入缓冲、输出驱动、接口电平转换、阻抗 匹配、延迟控制等功能。Input/0utput Block以Tile为单位,10 Tile的概念和CLB 有相似之处,同样是一个较大的组成单元,内部包括多个相同单元,如图4.6所 示。每个输入通路有两个DDR寄存器,而输出通路有两个DDR寄存器和两个 三态使能寄存器。同时,输入和输出的时钟以及时钟使能信号是独立的,只为和 复位信号是共享的。 D}fferemiaI Pa.r D计ferentiaI Pair 1●,};J、●■, 图4-6 Input/Output B10ck TiIe (iii)块RAM(Block RAM) Xilinx FPGA内部成块的RAM资源称为BlockRAM,对于Virtex.II系列其内部 BlockRAM资源为18Kbit。BlockRAM是真正的双口RAM结构,有两套读写数据、 地址和控制总线。两套总线的操作完全是独立的,共享同一组存储单元。 BlockRAM的双口RAM对于逻辑设计至关重要,它有两套独立的接口,可以方便 地连接两个其他设计单元,允许一个端口写入数据的同时,另一个端口读出数据, 第4章3D图形集成电路设计相关研究 提高数据吞吐率。图4.7显示了双口RAM的接口。 1 8 KbiI B{ock Se{ectRAM DlA DIPA ADDRA WEA ENA SSRA >CLKA DOA DOPA ■■●■●■■■—● DIB DIPB ADORB WEB ENB SSR8 >CLKB DOB DOPB 图4-7双口模式的Blocl姒M 除了CLB、Input/0utput Block和BlocI承AM外,FPGA还有很多其他的功能单 元。例如布线资源、DCM(D蟛tal C10ck Manager,数字时钟管理)和Multiplier(乘 法器)等。布线资源站FPGA中占用的硅片面积很大,为FPGA提供灵活可配的连 接;DCM模块提供各种时钟资源,包括多种分频、移相后的时钟;Mllltiplier为 18bit×18bit硬件乘法器,是高性能的乘法单元,可以在一个时钟周期内完成乘 法运算,对需要大量的DSP处理的应用至关重要。 4.5小结 随着计算机图形学的发展,所要绘制的图形场景越来越复杂,所消耗的时间 也越来越多,单单利用CPU来完成3D图形管线绘制中的运算已不能满足实时性 能的要求,同时,随着超大规模集成电路设计技术的飞速发展,使得利用硬件来 实现3D图形绘制成为可能,出现了以ASIC技术为基础的专门用来处理3D绘制的 GPU。不过由于ASIC适用于大规模生产,而在一个硬件设计真正实现成ASIC前 需要验证,而由于FPGA具有性能好、规模大、可重复编程、开发投资小等特点, 使得FPGA成为GPU设计中替代和辅助品。现代虽然EDA工具发展很快,但综合 工具不一定能保证充分利用芯片结构特点以达到最优目的,在这种情况下我们必 须了解我们的器件结构以达到设计的最优利用器件的目的。为了更好的利用 FPGA来设计电路,需要理解FPGA的内部结构,因此本章还介绍了Xilinx Vinex.玎 系列的结构。 49 第5章几何处理住FPGA上的实现技术 第5章几何处理在FPGA上的实现技术 5.1引言 随着现代计算机绘图规模越来越大,场景越来越复杂,为了满足这一需要, 需要借助辅助硬件资源,来提高图形处理单元(GPU)处理速度的需求越来越普 遍。几何处理是图形处理单元(GPu)算法实现中的第一阶段,其重要性不言而喻, 因此其运算速度直接关系到GPU的运算效率。根据前面第四章对FPGA与ASIC 的优缺点比较,我们选择FPGA作为硬件加速载体。结合计算机绘图及FPGA 的特点,本章采用Top.Down的方法对GPU的几何处理单元部分进行了FPGA 设计实现。所有结构模块均实现了R1乙级建模,并对其中几何变换中较复杂的 矩阵构造单元和矩阵乘法器模块以及3维裁剪模块给出了详细的描述。最后借助 电子设计自动化工具(EDA)对整个模块进行了验证综合,结果表明符合设计需 求,该方案能很好地完成处理功能,资源耗费低,并且能达到实时的要求。 本章组织结构:第一部分引言,第二部分为实现方案部分,第三部分为验证 综合结果,结论在第四部分给出。 5.2几何变换系统设计 5.2.1几何变换系统的硬件架构 将一座标做几何转换,计算方式为矩阵一向量相乘121】【221,会得到一新座标: f,义一却 ‰%l %‰ y一卸 l z一呻 L∥一印 嘲。嘲l 铂2 码3 ‰%1 %% %o鸭1 %2鸭3 其中 moo 删01 %o 朋1l 朋20 朋2l 称为转换矩阵。 m30 研3l 一般的几何转换处理器共有三种基本功能: 1.缩放(scaling):对一物体上的顶点做scaling,就是将这物体放大或缩小, 50 第5章儿何处理在FPGA上的实现技术 其转换矩阵如下: s Q 00 x 0 Sy O 0 0 0 S一 0 ● O O 0l 其中Sx代表x轴方向的放大或缩小,Sy代表y轴方向的放大或缩小, Sz代表z轴方向的放大或缩小。 2.平移(translation):其转换矩阵如下: l 0 Q d。 0 1 0 dy 0 01 t 0 00 l dx,dy,dz分别为x轴,y轴与z轴方向的位移量。 3.旋转(rotation):在三维坐标上可分为以x轴,y轴或z轴为中心的旋转, 转换矩阵分别为: 1 O 0 0 O cos9 sin目 0 B= 0 一sin目 cos臼 0 cos乡 O —sin乡 O 0 1 O 0 Ry= sin秒O cos护 0 O O O 1 0 0 0 1 cos臼 sin曰 O 0 一sin臼 cos伊 O 0 尺一= O 0 10 O O 0l 在3D管线的几何处理单元中,基本的处理元素为三角形的顶点(vertex), 其座标表示法为V=[x J,z w】。,分别对这些顶点做如上所述的一些转换得到 新的座标: vV’=f=fl(VvI) 每个几何转换r都可表示成矩阵M¨所以 v=M,.v 对于旋转、平移以及缩放等变换,一般会组合起来做多于一个的变换,例如: _=鸠o·%,吃=M7’l。H 或者可以先将两个矩阵相乘: V2=(M7’l·M7’o)‘% 第5章几何处理在FPGA上的实现技术 很显然这种方法耗时少且占用资源少。 对矩阵构造模块的实现,我们可以选用一个模式选择信号RVST(RVST即 Rotation Version Scale Translate的缩写)来决定组合的变换矩阵到底是什么样子 的。代码书写中,我使用case语句来判断输出矩阵的每个元素是多少,在具体硬 件实现上可以用4:1的Mux来实现该功能。 例如,如果RVST为0011,这表示没有旋转变换操作,只有缩放和平移变换, 那么Sx,Sy,Sz和Tx,Ty,Tz就会被发送到矩阵构造单元的输出响应位置。 旋转模式RV用2位bit数表示,表示4种模式:oo表示无旋转,01表示绕X轴旋转,10 表示绕Y轴旋转,11表示绕Z轴旋转。选择任何一种模式,输出端就有相应的矩 阵输出。 如果同时具有旋转和平移(如RVST=1X01,X为任意值),输出矩阵就是 在相应的旋转矩阵上,将偏移量加到最后一列上。 一共有四种形式的变换矩阵,如图5—2所示: S 0 0 o cos口水母 一sin口 0 sin口 cos口木墨 O 0 0 乙弓互● cos口奉母 0 sin口 疋 o S o 弓 一sin口 0 cos口囊墨 互 0 0 0 1 绕X轴旋转+缩放+平移 绕Y轴旋转+缩放+平移 cosd靠墨 一sin口 0 sin口 cos口窜母 o 0 0 墨 0 0 0 霉零互, S, 0 0 丁, 0 S, 0 丁, 0 0 S, 丁- 0 0 0 1 绕Z轴旋转+缩放+平移 基本矩阵 图5—2 四种输出矩阵组合样式 从上图可知,当我们要将旋转和缩放合而为一的时候(如RVST=1X1X), 问题就出现了,最终变换矩阵的一些元素会公用相同的位置。为了解决该问题, 需要引入三个乘法器,用于计算cos口和Sx,Sy,Sz的乘积,最后将乘积放入矩阵 的正确位置。 5.2.3三角函数查找表 运算中,需要用到三角函数值。为了使得设计简单,需要一个计算三角函数 cos臼和sin秒的模块。鉴于查找表方法的简单性,我们建立2个查找表来存储算好 的cos护和sin护的值。 鉴于三角函数的周期性特点,我们可以只存储一个周期内的值,另外考虑 到在一个周期内还可以化简,我们只需要存储1/4周期内的值。 靖5童IL。一j处理住FPGA上的。丈现技术 为n式验方便,这骋将l/4周期内的值分成128份。整个查找表结构如图5—3 njj: j惠;譬;载出 图5—3奁找表结构图 I)ecoder为地址映射单元,用于将超出1/4周期的角度变换到1/4周期内。 rom存储了1/4周期的函数值,Rom数据由Matlab程序产生。 minus用于产生负数的补码形式。 Mux多路选择其单元根据Decoder产生的符号判断位选择输出。 图5.4是cos臼≤和i謦si荔n臼雾模萄块}画的画R回TL●时哑序瑚仿硼真I匝图两:圃_固西固——-嗵TⅢ回■—I匝Ⅲ卿一 一“搿荔鬻I哑Ⅲ田——-哑面回—■I圊衄—●l■■■——I■■■■—阻——一 。巍o鬻j攀攀瑟雾匦≯蕊匝强l阿哑咀蕊殂—■I■哑哑画殛啊嘎匝■■囹哑曩砸匝圈圃■■糖■■—————■■圃■蕊圆疆 图5—4 cOs∥荆I sm∥模块的RTL时序仿具图 5.2.4矩阵乘法器 矩阵相乘在3D变换中是被频繁用到的一种计算,但在矩阵相乘过程中用到 了大量的矩阵运算,而乘法运算又需要大量的时l、刚,因此运算荦.元对于乘法的效 率是比较低的,远低于加法运算, 所以,需要从矩阵乘法的结构中挖掘出其可 并行计算的特性以达到减少运算时间的目的。 (i)矩阵乘法的算法分析 仟意两个矩阵的乘积定义如下: T c‰=a≯;k。 第5章儿何处理在FPGA上的实现技术 al 1 口12 口l 3 口14 6ll 61 2 6l 3 Cll C12 CI 3 C14 口21 口” 日23 日24 62 l 622 623 C2l C22 C23 C24 (1 31 口32 日3 3 日34 63 1 632 63 3 C3l C32 C33 C34 日4】 口42 口4 3 日44 64 I 642 643 C4I C42 C43 C44 c印=吼l包P+%2如p+….%朋% 因而,为了矩阵乘法能够被执行,矩阵的维数必须满足 (圪×聊)(聊×p)=(所×p) 以4x4的矩阵乘为例,完成结果的输出需要进行64次乘法运算,48次加法 运算。运行效率可想而知。 为提高矩阵乘法的运算速度,可采用并行处理结构及其对应的并行算法。脉 动阵列简单重复的PE(Processing Elements)构成和PE局部连接性质使它特别适 合于具有局部相关关系的线性递推运算的实现,矩阵乘法就是其中一种。在执行 矩阵相乘时,数据间相关关系具有局部性、一致性,映射到阵列结构上时,仅需局 部、规则的PE间的通讯,特别适合于用脉动阵列实现。 (ii)脉动阵列结构 (一)脉动阵列介绍 脉动阵列定义125】: 从1978年丌始,美国卡内基一梅隆大学(CMU)的H.T.Kung等人在研究算法计 算与专用芯片的体系结构的关系时,将计算任务按照通信与计算的比重不同分为 受计算限制(computation.bound)的和受输入、输出限制(I/O.bound)的两大类。脉 动阵列主要针对受计算限制的问题而提出的。 脉动阵列由一组简单的、重复的PE构成,每个PE能够执行固定的、简单的 操作。每个PE只与相邻的PE有规则地连接。除了极少数边界上的PE外,所有内 部的PE的内部构造都是一样的。进入、输出阵列的数据必须在边界上的PE进行 输入、输出。脉动阵列中通过有规则的、局部的PE间相互连接得到,这种特性 使之特别适合用VLSI技术来实现。 关于脉动阵列的定义有很多,S.Y.Kung给出的定义为: 脉动阵列是一个具有如下特性的计算机网络: (1)同步性:通过网络的数据是有节奏性地被计算(由一个全局时钟定时)和传递。 (2)模块化与规则化:阵列是由带有均匀互连拓扑的模块化处理单元组成,计算 网络可以无限扩展。 (3)空间局部性与时间局部性:阵列内部的变量以局部通信的形式互连接成某种 结构,即空间局部性。信号从一个节点传送到下一个节点中,至少具有一个单位 第5章儿何处理在FPGA上的实现技术 PE的利用率,使整个阵列的系统性能得到充分的发挥。因此,这种结构得到了普 warp,Saxpy公司设计的Matrix.1,ES 输入,必须在它们到达阵列之前采用一定数量的延迟对其进行调整。可以看出:B 个延迟,因此它是一个局部化的网络。对来自B的每一个列和来自A的每一个行的 对于简单矩阵乘法SFG运用准则2,所得的脉动化SFG的每一条边上都具有一 (四)矩阵乘法脉动阵列结构: L公司设计的脉动阵列机。其中,C删的协印 遍的重视。国外设计完成的脉动阵列处理机有:美国C删的可编程脉动阵列机 唯蓁鹩竖越竖诹逸鋈驰由i多鼷 个高性能誊的处理机裹构成,崩整个阵列同机的平均悸处理能团力达到l萋亿次/秒自,它可应,挲睡酆型旺趔基妻』一i鳊新i 萋 用于数字图像处理与识别、数字信号处理、人工智能等方面。 男i§餐毒 奏荔 簦!£妻薹 羹: 列爹萱 蓁童 冀; 耋i 霎}≤ 霉 囊l 萎;: 薹 雾 的第一列不需要调整,第二;妻硝褛托孤逸霉烂?矗巍裂羹; 捌捌吲霪i 萎霉萎j享i蓁;冀 善垂差蓦蓦二;委辇i霎攀 荔手~雾冀薹蓁冀望羹葡醑掣鬻吲薹 据从存储器中有规则地压入阵列,经过许多连成流水 羔!诱。耋誊鹱篱溪瓣韵羹型争磊吲暖些粪 线的PE,沿途得到一 系列连续的处理,所以它的数据运动是局部的,即在这个PE 中的符运待算督导茬致付的笤数藓据磁改希变冀不捌会萎影羹响季后擀续常的鞔P鲫E运剖算篙。j舔所型以市对|于薹数巧据穰运臻动。具有全局性 的算法,很难找到一种 合适的脉动阵列结构。 以傅罩叶变换为例,离 散傅立叶变换(DFT)的表示是线性的,它的数据运动 具有局部性,所以很容 易找到脉动阵列的结构来实现。但是在快速傅立叶变换中 (FFT),它的数据运 动具有全局性,则找不到一种脉动阵列结构来实现。相关的 研究表明,用脉动阵列 实现的DEF的运算速度接近FFT的运算速度,这从另一个方 第5章儿何处理在FPGA上的实现技术 处理器中。下一个clk开始输入矩阵B元素,并在clk下降沿作用下,进行内积步 运算。因为矩阵运算是元素乘积的累加和,所以B矩阵第i行元素的输入要比第i.1 行元素延迟一个clk。 53 3D裁剪器设计 本节描述了一种裁剪引擎,它能够处理3D图形中的裁剪、透视除法以及视口 映射的功能。硬件实现的难度取决于裁剪算法的复杂程度。我们在 Sutherland—Hodgman裁剪算法的基础上提出一种新的裁剪算法,该算法通过去除 冗余顶点以提高处理速度,同时利用编码来判断线段可见性的方法使得硬件实现 变得很容易。最后,我们在FPGA上实现了这个裁剪引擎并且能够以3M个三角形 /s的速度运行,满足了图形管线中的实时性要求。 5.3.1裁剪处理器的体系结构 根据前面第三章中对3维裁剪算法的研究,我们给出了裁剪处理器的整体结 构图,如图5.9【301所示。顶点寄存器单元Vertex Register Files(VIU)用来存放三 角形的顶点数据和中间的处理结果。编码器OutcodeUnit(OU)用来对三角形的顶 点进行编码。PVPDVM单元实现两个功能:计算出插值参数以及透视除法和视 口映射。插值器Interpolation Unit(IU)用插值参数来对三角形的各种属性进行插 值得到新的顶点。最后一个是控制器Control Unit(CU),用其他四个模块的输入 信号来负责控制其他各个功能模块协同合作。 l顶点寄存器单元l …~.1 VRF I 一一- 编码器I ou I I l ▲ ▲ I I ==:二{肾l - { ■ 1r ’● lPVP。VM单元卜j l插怎器卜 ? ? I I 一数据信号 …+控制信号 ……’进入控制器的信号 图5.9裁剪处理器架构 59 第5章儿何处理在FPGA上的实现技术 (a) O Position X 1 Position Y 2 Position Z 3 Position W 4 Norma l X 5 ’Normal Y 6 Norma I Z 7 -『exture U 8 Texture V Q CoI or R 10 CoI or 0 11 CoI or B 12 Col or A 13 SDeCoI or R 14 SDeCoIor G 1 5 SDeCoIor B 1 6 SDeCoIor A 17 Fog 一······。··‘, 入 C;ip pIa门e fAj 18) (C) 【O) l 1 2 ,3 4 5 入 ≯~ |1 2 3 31 I 4 5 p : 。“。:纠 (1)case—A 1 234 5 JJ |1 2 3。 4’ 5 (¨)∞∞一B 11 2 ” p、 345 , ● \/ |1 2 3 5 ’、 :#,一f (|lI)case-C (IⅥcase.D (c) 图5-10(a)VRF结构和I顶点属性 (c)裁剪中遇到的4中情况 (c)VRF 4种操作 第5章儿何处理在FPGA上的实现技术 5.3.3编码器0U的设计 编码器0U用来对三角形顶点进行编码,并回写到VRF中。透视投影后裁剪 体(四棱锥)的边界方程为: 一w≤Z≤w —w≤v≤w —W≤X≤W 因此对于六个边界,使用六位端点编码,第一位对应最右端位,其编码规则为: 第一位置1一一当z>w时; 第二位置1一一当z<一w时: 第三位置l一一当y>w时; 第四位置1一一当y<一w时; 第五位置l一一当x>w时; 第六位置1一一当x<一w时; 否则,相应位置为O,如图5一ll所示,给出了各个区域的编码情况。当一个三 角形能被完全接受时,就直接进行透视除法和视口映射操作。否则,需要对该三 角形进行裁剪处理。对一个顶点进行编码运算可以简单地使用6个比较器就能实 现。首先,对新来的三角形,需要对三个顶点进行编码,然后回写到VRF中。如 果在接下来的裁剪过程中产生了新的顶点,要立即对该顶点进行编码然后保存于 VRF中。 00l lO 0001lO 010l IO 100100 000100 OlOl00 ●^●。●●-。’’●-… 100101 000lOl O1010 IOOOlO 叫OO m 0100Io 101010 ∞ ● Om Oll们O 100000:000000 olo000 L……j i…——一一一————I 10looO 001000 0ll000 10000l;000001{olo001 ..i.......一1…... 10100l 00100l 01lool 阶℃丌 n Middle 图5.1l 3维裁剪区域编码 Back 5.3.4 PVPDVM单元的设计 PVPDVM单元主要完成两个功能:第一是计算出一条边与一个裁剪平面相 交的交点的插值参数值;第二是把已经对6个平面进行裁剪后所得的多边形进 行透视除法和视口映射。首先需要对传递进来的相应的两个端点的编码进行判 断以确定是否需要进行求交计算,如需要,则要进行插值参数计算,否则对下 一条边进行如上操作,直到对裁剪体的6个平面都裁剪完,然后进行透视除法 和视口映射。图5.1 2给出了PVPDVM单元的主要结构图。左边部分是PVP功 62 第5章几何处理在FPGA上的实现技术 能单元,用来计算插值参数,右边部分是DVM单元,是计算透视除法和视口 映射。考虑到除法器需要占用较大的资源,我们把PVP和DVM两个功能单元 共用一个除法器。我们设计的除法器【311是一个倒数单元rcp和一个乘法单元的 组合,其中倒数单元使用牛顿迭代算法来设计。PVP的输入是三角形一条边的 两个端点的坐标,由于不同的面的边界方程不同,所以使用多路选择器来对顶 点坐标进行耿舍,例如,对于后平面来说,所选的输入数是z和.w,所以其插 ,=一o 值系数为 z1一w1 (zl—w1)一(z2一w2) 当对三角形进行裁剪完后,接下来需要做的工作就是进行透视除法和屏幕映射 了。DVM单元中的32’ho0010000是定点数1的表示(我们采用15.16的顶点表示方 法),先用除法器求出w的倒数二,然后进行乘法操作即可完成透视除法,接下 W 来再把屏幕宽和长的一半兰每坐和竺每丝与前面的透视除法所得结果相乘,就 二 二 得到最后的屏幕映射。 图5.12 PVPDVM的主要结构 第5章儿何处理在FPGA上的实现技术 5.3.5插值器IU 插值器用从PvPDVM单元产生的参数值柬计算新交点的属性值。其在硬件 的实现上只需要加法器和乘法器。只和只是一条三角形边的两个端点,f是交点 在这两个端点I’日J的插值参数,则新交点尸为: P=只+(芝一只)木,. 由于每次有新的交点都需要进行乘法运算进行查找,因此乘法运算速度将是 该IU单元的瓶颈,下面详细介绍设计用到的布斯乘法器。 布斯算法就像所有的乘法系统一样需要检查乘数位元和部分乘积的移位元, 布斯算法对一个乘法器中的正数和负数看作是一样的,而且对于一个2进制补码 有符号数的乘法器来说是通用的。布斯观察到一个可执行加法和减法运算的 ALU,其运算方式不只一种。 比如:假设我们要进行2ten×6ten或0010two×01lOtwo: 00 1 0two MultipIicand × Ol 10two MultiDlier 0000 shiR(乘数位元为0) + 0010 add(乘数位元为1) + 0010 add(乘数位元为1) ± QQQQ 墨bi鱼(丞麴焦丞左Q) 00001 100two 但是注意到6ten=.2ten+8ten或0110two=.0010two+1000two。当计算中 第一次遇到1时,可以把乘数中一连串的l换成减法运算,当遇到最后一个1 后面的O时再加上被乘数。如: 00 1 Otwo Multiplicand × 01 1 0two MultiDlier 0000 一 0010 shiR(乘数位元为0) sub(乘数位元中第一个为1者) + 0010 add(乘数位元中的l字串) ±QQ!Q 墨hi鱼(煎二垄壁直量卮=仝!) 00001100two 御斯算法的核心是对数字中间部分的l字串进行头、中、后三段的分段动作, 因为0字串本身无须进行运算所以不必理会。根据现行位元及其右方位元,分别 执行如下动作: 00:此为。字串的中间部分,不执行运算: 01:此为l字串的结尾,所以将被乘数加到乘积的左半部: 第5章几何处理在FPGA上的实现技术 10:此为l字串的丌头,所以将乘积的左半部减去被乘数; ll:此为1字串的中间部分,所以不执行运算。 每执行上述步骤一次就要把乘积向右移一位。 如表5.1所示的操作,第一步是视最低有效元的右边一个“虚构"的位元其 值为0。 表5—1运算步骤举例 重复次数 被乘数 步骤 乘积 O 0010 初始值 OO00011 OO 1 0010 】a:00=>无运算 00000l】00 0010 2:乘积右移 OOOO001 lO 2 0010 1 c:1 0=>乘积=乘积.被乘数 1l10001 10 0010 2:乘积右移 11 ll 000 11 3 0010 1d:11_>无运算 11 11 000 ll 0010 2:乘积右移 1111 100 01 4 00lO 1b:01=>乘积=乘积+被乘数 0001 lOO 0l 0010 2:乘积右移 0000 11000 需要注意的是我们所处理的是有符号数,所以将乘积暂存器往右移位的过程 中必须保留中间结果的符号,而实际解决方法就是算术右移,即符号也跟着又延 伸。 既然已经了解了布斯算法的原理,接下来就要看为什么它也可以应用到2 进制补码的有符号数乘法运算。令a为乘数,b为被乘数,而ai代表a的第i 位元,再以乘数的位元重新定义布斯算法如表5—2所示。除了表格之外,我们还 可以用(ai一卜ai)来表示它,其值各代表如下的动作:0表示无运算,+l表示加 b,一l表示减b。 表5—2布斯算法定义 ● al ai.1 运算 O O 无运算 O 1 加b l 0 减b 1 1 无运算 由于我们知道将被乘数相对于乘积寄存器左移的运算可以想象成它乘上一 个2的幂次,所以布斯算法可以写为 (a.1一a0)×b×2 40 65 第5章儿何处理任FPGA卜的实现技术 +(a0一a1)×b×2‘1 +(a1一a2)×b×2‘2 +(a29一a301×b×2‘30 +(a30一a31)×b×2‘3l 我们可以利用下是柬简化以上的组合: (~ai×2“i)+(ai×2‘(i+1))=ai x 2‘i,另外,a—l=0,并把b提 出式子外面: b×(一a31×2 6 3 1)+(a30×2“30)+…+(a0×2‘0) 上式右边括号内的式子就是二进制补码的表示法。所以可以迸一步简化为: b×a 因此,伽斯算法事实上是执行a和b的相乘运算的。 图5一13是算法流程图。 第5章儿何处理在FPGA匕的实现技术 太,起 B:坎意{ Q:。,簦 算 图5一13布斯算法流样 最后,根据上述流程用verilog对该算法进行仿真,得到如图5.14所示的仿 真波形: 飘 霉巨!曼曼=’堂蔓!喧=苎曼曼墅鼍曼=曼曼,匡掌曼曼!曼■曼丝,笪!曼墼,曼!童曼!,塑曼曼曼曼!!曼壁!'堕!蔓曼!—堡蔓_曼-·!_曼!_皇—堕—·■ii_—:i簟i匦i一i;■i—i画;i;iii匠iiiii;藤ii;五ii;i面;ii蘑i;萱i;而ii 霸一 _一-———一·_lI_-__·__一__——_--__·—-iiiiiii;iii;ii;;二;■● 图5.14 booth乘法器波形 5.3.6综合与分析 本设计中所有模块,包括顶点存储单元、编码器、PVPDVM单元、插值器 和控制单元均使用Verilog语言完成了RTL级的编码,使用Mentor公司的 67 第 I 5S章l儿i何 c处 es 理6住3r1P9G/A 1f3.的6实9现6披4/6%{:1 MS1ci,cedFe1㈦ip1F1106p.328f刈9再5个/』2/7J能3模92块进1行4了%RT L.功能仿氧,嗣时,我们用Xilinx公¨?的 ISL9.1.(J2∽J’謦个横块进行了综合,选川器f,1.,乃:xc2\6()fJ(J一6b何57,?暮台后∥J器 件资源他川如袭5—1所,r÷: 农5.1裁剪器综台后使川的FPGA资溅 Slices 6319/1 3696 46% S1ice F1ip F10p 4输入LuTs 3895/27392 l 2078/27392 1 4% 44% !MULTl8X1 8 44/136 32%, GCI。K 1/1 6 6% 从表5.1可以看出本殴计资源消耗较人,分析发现,…于顶li寄存器瞥元 VRF需要进行移位、删除等操作,而且每个存储单元需要保存’个顼点的所有 属性,所以这个功能单元消耗了FPGA的大部分资源,I司时,在插值器IU巾使 用厂较多的乘法器。可以采用1些改进办法,比如:可以考虑对将加法器和乘法 器进行优化,选用更有效率的方法来实现,如采用Carry Look.ahead加法器和 Bau2h.Woolev乘法器米进行季夺换。 综合后用Modelsim进行仿真,仿真波形如图5一14所示:仿真结果和软件模拟 。充全一致。 l几几『1几几几几r] 趣匮囊e二二= 卿Qi唑1 1 I 一.玉』二立. 图5.14对一个三角面进行裁剪的波形图 5.4小结 本章阿先根据几何变换的特点给出了儿何变换的硬件实现结构。由于在进行 疑转操作叫.{嗅需要二-角函数sin和cos的值,因此根据j角函数的对称性设计了三 角函数套找表来提供所需要的数值。而 第5章儿何处理在FPGA上的实现技术 阵运算的速度,需要利用硬件的并行和流水特点束加速,因此利用脉动阵列来实 现矩阵的乘法运算。对于3维裁剪,在Sutherland.Hodgman裁剪算法的基础上对 其做了改进,用端点编码的方法来对线段是否可见进行判断,并利用去除多余顶 点的方法来提高裁剪在FPGA上的处理速度。另外,由于插值需要多次乘法运算, 因此利用佰斯算法来实现了32bit x32bit的乘法器。这些改进使得我们设计的裁 剪器在工作频率为47.618MHz时平均每秒能处理3M个三角形,达到了嵌入式3D 图形渲染的实时性要求。 第6章总结与展望 第6章总结与展望 6.1总结 本文探讨了计算机图形学中几何处理(包括几何变换和3维裁剪)的FPGA实 现技术,该部分是用FPGA实现GPU部分功能的尝试,希望借此推广到整个GPU 的实现,同时,对于现在ASIC设计,FPGA的前期验证不可缺少。本文首先概述 了3D图形学技术的发展状况,然后对3D图形的实时绘制管线进行了详细的表述, 接着对几何变换和3维裁剪技术进行研究,最后详细介绍了几何处理单元在FPGA 上的实现方案。几何变换采用了预先产生变换矩阵、多个变换矩阵合并为一个矩 阵以及脉动阵列矩阵乘法的实现技术,而3维裁剪则是采用预先编码轮流对裁剪 空|’日J的各个裁剪面进行裁剪得到最后的结果。 本文主要工作总结如下: 1、对几何变换与3维裁剪技术进行研究,确定算法。几何变换包括平移、 缩放、旋转和投影等操作,主要是进行矩阵乘法的运算,通过把多次变换所要进 行的矩阵合为一个矩阵以减少乘法时间。3维裁剪通过把3维空间转化了2维空 问分别对裁剪体各个面进行裁剪以实现对物体的取舍。 2、在确定算法的基础下用C程序模拟。算术运算包括定点和浮点两种运算。 首先是在浮点运算的基础上对算法进行模拟,实验结果表明算法的正确性。然后 把该浮点运算转换成定点运算,发现转换后的结果有些瑕疵,对定点进行调整以 确定最佳的定点格式。 3、在论述矩阵运算并行算法的基础上,提出了基于二维正方形心动阵列结 构的矩阵乘法器,并研究了二维方阵结构的矩阵乘法器的FPGA硬件实现方法。实 验结果表明采用二维正方形心动阵列实现的矩阵乘法器,具有高度并行性和流水 线性特点,能在保证运算速度的同时,节约硬件资源。 4、在3维裁剪算法的基础上,提出裁剪器的体系结构,合理划分各个功能模 块的协调合作,并利用并行处理技术以提高数据处理速度。实验结果发现该模块 能满足实时运行要求,同时发现顶点寄存器VRF占用资源较多,需要着手改进。 到本文完成,几何变换与三维裁剪的FPGA设计都已经完成,但随着学习的深 入,发现还有许多工作需要做: (1)脉动阵列矩阵乘法器的研究实现还很简单,没有进行优化和进一步的研 究。 (2)查找表结构过于简单,需要进行优化,在提高速度、精度的同时将ROM 表的数据量减少。 70 参考文献 参考文献 [1】b!!卫;丛型妻奏:;萋薹主二l辱囊:掣耋|萋≥;鋈薹i喜耋!耋委丝薹量蓥誊;攀囊一錾翥翼!一薹薹彝:簦;霉 i誊i?i妻i囊一萋i 霪警i刍|?囊矍耋萋耋笋÷主蚕妻鼍鱼耄≥;毳事l}量主孽!耋;到善i毳童量霉主i!蚕尊。羹霎喜霪誉纛兰二_=i要薯j喜琶 i宇j薹冀荔羔墓饕羹霆鼍毒蕃;囊:;j囊刍囊ij萋≠圭i真善嚣p≥≥§i 来对我的关心与 指导。 感谢实 验室的杨毅、史鸿声和我的同学钟伟、郭安泰、王炳勤等同学,你们 的钻研 精神和学习工作态度永远是我学习的榜样,同你们的讨论和交流,扩展了 我的知 识面,感谢孙大成师兄对我毕业设计的帮助,感谢大家在我的三年的学习 中所给 予的热情帮助。 最后向 一直关心支持我的家人、朋友和老师们表示由衷的感谢,是你们的关 心与鼓 励,我爿‘能顺利地完成这篇论文。 吴思 2 吴思 2 —— 叁耋室燮 . 2004 [38】Gunther Geriner.Kai Hormann,“E娟cient Clipping ofArbitra叮Polygons”,ACM,pp71.83, Apr订1998 【39】You。Dong Liang,Brian A.barsky'‘。A New Concept And Method for Line Clipping”,ACM, ppl—22.Jan 1984 [40】Cyrus,M.and J.Buck,”Generalized two-and three dimensional clipping,’’ACM Transactions on Graphjcs,VoI.1 1,pp.276—290,Janua∥1 984. [4 l】DaVid Bfylhe,AaRab Munshi,Joe Leech.0penGL哪ES Common/Common.Lite Pronle Specincation Version 1.1.1 0 (Full Specincation) 【EB/OL】. http://www.khronos.or∥regist叫儋Ies/specs/1.1/eS_full—spec.1.1,10.pdf [42]Gunther Geriner,Kai Homann,‘‘E币cient Clipping of Arbitra哆Polygons”,ACM,pp71.83, A prill998 【43】Frank DeVai,‘‘An Ana Jysis Technjque and an A Jgorjthm for Ljne Clipping” 【44】Patrick-G川es Mal Iot,”A Ne w’FaSt Method For 2D Polygon Clipping”,ACM,pp276.290, JuI y,1992 [45]James F.BIinn,Manin E.NeweII,‘‘Clipping Using Homogeneous Coordinaces,, 【46]Min百un Zhang,Chaman L.SabharwaI,‘‘An E衔cient Implementation Of Parametric Line And Polygon Clipping Algorithm’’ [47]You。Dong Liang,B rian A.barSky,“A New Concept And Method for Line Clipping’,ACM, ppl-22,Jan 1984 [48]薛之昕,“二维空间的NicholJs-Lee-Nichofl裁减算法“,计算机:[程与应用,pp66.68,ApriI 2004 【49】彭艳莹,陆国栋等,“基丁‘包围盒编码的三维线段裁减新算法”,计算机辅助设计与图 形学学报,ppl370—1 374,Nov 2003 74 附录 附录攻读硕士学位期间发表的论文及参加科研情况 发表论文: 1.吴思,郭立,郭安泰,“3D图形的裁剪算法及硬件实现技术研究”,《电 子技术》2008年2月刊已发表。 2.郭安泰,郭立,杨毅,吴思,“一种图形光栅的硬件实现算法”,《中国图 像图形学报》发表时间待定。 3.孙大成,郭立,吴思,“几何变换单元的设计及其FPGA实现”,已被《电 子测量技术》录用。 4.徐华结,郭立,李琳,吴思,“基于AC~3数字音频解码的递归IMDCT 的FPGA实现”,已被《微电子学与计算机》录用。 科研项目: [1】深圳市海思半导体有限公司:嵌入式3D图形加速硬件实现方案设计。 [2]微软公司:全景视频处理算法研究。 基于FPGA的三维图形几何管线的算法及其实现技术研究 作者: 学位授予单位: 吴思 中国科学技术大学 相似文献(10条) 1.学位论文 刘伟 三维图形处理系统中碰撞检测算法的研究和应用 2005 三维图形系统中要处理大量环境物体和运动物体,碰撞检测用来检测运动物体之间或运动物体与环境物体之间是否有碰撞,从而能决定运动物体的 下一步动向,以提高系统的真实感和用户的沉浸感,这在计算机图形学相关研究和应用中占有重要地位。   本文研究了已有的一些碰撞检测算法,分析了其中典型算法:如四维空间交集测试,八叉树空间分割,BVH(boundingvolumeshierarchies层次包围 盒),分析各自优劣及适用条件。针对BVH算法中选择单一的包围盒(BoundingVolumeBV)所导致的性能保持的问题,即如何在简单性和紧密型之间取得折 衷,本文提出了一种复合式的BVH算法,充分利用了三种BV的特点,按层次选择不同的BV,实验表明该算法能有效提高检测性能,增强算法稳健性,同时 该算法具有BV层次范围可调节性的特点;进一步加入了IAABB方法,实验表明能减少需要检测的可能碰撞的面对(pairsofsurfaces)和多边形对 (pairsofpolygons),从而在一定程度上提高检测性能。最后把复合BVH算法应用于一个具体的三维图形处理系统即野战三维态势系统中,针对态势系统 中碰撞的特点,做了碰撞检测的预处理和后处理。 2.期刊论文 李步升.Li Busheng MATLAB在三维图形构造中的应用 -电脑开发与应用2009,22(9) 计算机图形学中三维图形是较难的知识点,将MATLAB工具引入计算机图形学三维图形构造中,进行辅助教学并设置试验,能简化学生学习计算机图形学 的难度,激发学生的兴趣,提高教学效率. 3.学位论文 时新伟 实时视景中三维图形与视频背景融合技术的研究 2000 实时视景生成技术是虚拟现实技术中的重要组成部分.实时地生成具有真实感的三维视景是虚拟现实技术研究者长期以来追求的目标,它广泛的应用 于飞行模拟器、游戏娱乐、辅助教学、影视制作等领域中.该文的目标是研究应用随视点位置变化而变化的视频图像作为背景实时地生成具有真实感的三 维视景,解决视频与三维图形融合的关键技术,并探索视频图像在实时视景生成中的其它应用.基于以上目标,该文基于图像的生成技术和现有的视频与图 形融合技术的研究成果,提出了视频选播的概念和实现方法,解决了实现与视点位置相关的视频图像和三维图形场景之间融合的关键技术,并在Windows平 台上实现了此技术的演示系统,对视频图像作为不规则自然对象和运动体在实时视景生成中的应用技术进行了初步探索. 4.学位论文 屈磊 3D引擎中多层地形实时渲染及场景调度算法研究与实现 2009 随着计算机软硬件技术的不断发展,三维图形引擎也慢慢成为了计算机图形学研究的主要内容。三维图形引擎在虚拟现实、数字城市、影视广告、 计算机辅助设计和科学计算可视化等各个方面起着十分重要的作用。通过三维图形引擎我们可以逼真地模拟人在自然环境中视觉、听觉及运动等。一个 完整功能强大的三维图形引擎融合了计算机图形学、多媒体技术、人工智能、人机接口技术、数字图像处理、网络技术、传感器技术以及高度并行的实 时计算技术等多个信息技术分支。 对此,本文从国内外的研究现状出发。对地形的几何建模和光学建模进行深入研究,并且在大规模场景的数据调度进行改进。从而给出大规模地形 实时渲染的步骤和大规模场景数据调度的优化算法。 在大规模地形的渲染处理中,使用了基于组件式的多层地形算法。通过组件式的地形,我们可以将地形表现的更加的丰富。此外,组件式地形也是 本文提出的多层地形渲染算法和LRU数据加载算法很重要的基础。组件式地形算法的效率将会直接影响到后面两个核心算法的效率。在组件式地形算法的 基础上,通过多层地形算法,实现地形的多种精细程度,从而更加真实的模拟现实世界。同时避免了LOD算法消耗很高的问题,在保证真实性的情况下 ,减少各种消耗。 多层地形算法虽然降低了开销,但是却增加了内存消耗。简单说来就是通过空间来换取效率,为了减少空间消耗的影响,因此本文的第二个核心算 法是LRU的数据加载。通过LRU算法可以尽最大可能的减少空间消耗的弊端。 在大规模场景的数据调度中,使用了基于LRU算法原理的数据调度算法。通过本文的算法,可以实现大规模场景的数据调度,同时还不需要担心由于 内存大小对场景的限制,从而保证大规模场景中数据处理的流畅性。 此外,通过原创的三维图形引擎来实现本文的算法,从而证实算法的可行性。根据实验的结果说明算法能够很好的满足三维漫游的需求。 最后,在本文算法的基础上提出改进意见和进一步的展望。 5.学位论文 林谋广 移动三维图形几何压缩 2005 本文围绕在移动手持设备上进行三维图形的显示,根据移动手持设备的特点,对模型的压缩策略和模型的特征点进行了研究,目标是提出一个在保 持模型外观的基础上对几何模型进行压缩、简化,并且压缩后的模型可以适应在移动手持设备上进行显示的完整算法。 本文提出了一个基于顶点相邻三角形单位法向量变化的边折叠几何压缩算法;本文通过计算顶点相邻三角形单位法向量差值得出顶点的起伏程度 ,识别出模型的特征点,提出了一个特征保留的策略;完整的基于单位法向量变化和特征保留的边折叠几何压缩算法可以在保持模型外观的同时有效的 降低模型的规模,从而为在移动手持设备上显示几何模型提供了基础。文章最后给出了在移动手持设备上的应用情况。 6.会议论文 杨扬.马建明.张茹.周秋实 基于OpenGL的三维图形的开发 2008 本文介绍了OpenGL及OpenGL绘图与Windows编程的联系,阐述了实现VC++6.0和OpenGL图形接口机制,在VC++6.0下通过创建工程并加入支持OpenGL的 连接库和头文件、设置OpenGL支持的Windows窗口,从而实现与OpenGL在Windows操作系统下的图形接口,构建了三维图形的开发环境。 7.学位论文 任义 基于DirectX的3D图形引擎的设计和实现 2008 随着计算机图形学在CAD/CAM/CAE、虚拟现实、三维模拟等领域中得到越来越广泛的应用,如何快速开发高效三维应用程序受到了越来越多的重视。 3D图形引擎是解决三维图形应用程序开发效率的有效途径。DirectX是微软公司专门为游戏开发的API,目前Windows中大多数游戏引擎都以DirectX为 API。将DirectX应用于专业图形领域是一个新的尝试。 本文阐述了运用计算机图形学理论和面向对象程序设计方法,基于DirectX设计并实现针对CAD/CAM/CAE软件开发的3D图形引擎的全过程。主要内容 如下: 1.对3D图形引擎开发中常用的技术和功能划分进行了研究和总结,并对国内外3D图形引擎的现状和发展作了比较深入的探讨; 2.分析并比较了OpenGL和DirectX的相关技术特点。结合三维图形的一般显示流程研究了Direct3D的渲染流程和基于Direct3D的图形程序开发技术 ,设计了图形引擎的功能模块、接口和运行流程; 3.研究了3D图形引擎中的设备选取、窗口创建及消息处理、相机设置及其交互控制、灯光和材质、基于Direct3D的即时绘制模式等关键技术。 采用DirectX9.0设计并实现了3D图形引擎GE3D,并将该引擎应用到图形程序CAXBASE和可视化插件开发中,实践表明,该图形引擎基本能够符合3D图 形应用程序开发需求。 8.学位论文 楼啸波 曲线曲面造型方法与应用技术 2006 曲线曲面造型是计算机辅助几何设计(CAGD)与计算机图形学(CG)的重要内容。由Coons、Bezier等大师于六十年代奠定理论基础。经过几十多年发展 ,现在它已经形成了以Bezier方法、B样条方法以及NURBS方法为主体,以插值、拟合、逼近这三种手段为骨架的几何理论体系。 OpenGL是一个功能强大的图形库,它集成了所有曲线曲面造型、图形变换、光照等等复杂的计算机图形学算法,用户可以很方便地利用它开发出有 多种特殊视觉效果的三维图形。现在,OpenGL已经成为应用最为广泛的二维和三维图形编程接口。 本文首先介绍了曲线曲面的数学表示的相关知识,然后介绍了Bezier、B样条以及NURBS这几种典型的曲线曲面构造的方法的理论基础。在这些理论 的基础上,结合MicrosoftVisualC++IDE和OpenGL图形开发库所提供的绘制曲线曲面的接口函数,按照不同的曲线曲面构造方法实现了自由曲线曲面的绘 制。 9.学位论文 陈哲锋 基于OpenGL的地形三维可视化研究与应用 2008 在计算机图形学领域,三维可视化是一个重要的研究方向,许多研究人员己经进行了大量卓有成效的研究,并有许多成熟的技术已应用于游戏、电 影动画、工业设计等领域,但是与地理信息系统联系较少。地形三维可视化技术是三维地理信息系统重要研究内容,其使地理信息更直观、更形象地展 现在人们面前,在“数字地球”大背景的衬托下,具有广阔的发展和应用前景。因此,研究如何实现具有真实感的地形三维可视化就有非常重要的意义 。 本文运用作为三维图形技术标准的OpenGL技术在Windows XP系统和Visual C++6.0平台上实现了不同模式的地形三维可视化,主要工作如下: (1) 系统论述了OpenGL基本概念以及工作原理,着重研究了三维图形变换、可见面识别、光照模型、纹理贴图等OpenGL技术; (2) 归纳数字地形模型、分形分维技术、数据拟合模型等三维地形可视化建模方法,详细介绍了数字地形模型以及不同构建方式的优缺点; (3) 通过OpenGL基础库、像素格式、绘制描述表与设备描述表以及OpenGL风格设置等一系列步骤来建立基于Visual C++的OpenGL程序基本框架; (4) 总结反距离权重法、克里格法、邻域法、样条函数法等离散数据网格化方法以及它们适用的具体情况,着重研究反距离权重法数学模型以及实 现其算法的流程图; (5) 基于上述理论和成果,运用规则格网数字高程模型,采用反距离权重法进行离散数据网格化,实现了基于OpenGL技术的不同着色、纹理贴图、 天幕等不同模式显示的三维地形可视化。在深入研究了OpenGL高级纹理技术的基础上,运用纹理坐标生成、多重纹理、纹理绑定等相关技术,实现了对 等高线、土石方工程、植被等模拟应用,而且扩展了对简单层状地质模拟。 文章最后对全文内容进行了总结,并提出了值得进一步研究的问题。 10.期刊论文 朱齐丹.栗蓬.张伟明 用OpenGL实现三维图形的半可视化建模方法 -自动化技术与应用2000,19(1) 本文介绍了一种三维图形制作的实用半可视化建模方法,在可视环境中对三维物体的组件进行缩放、移动、旋转等,从而简化三维图形的制作过程. 本文链接:http://d.g.wanfangdata.com.cn/Thesis_Y1270088.aspx 授权使用:北京理工大学(北京理工大学),授权号:c7911945-800e-4a25-b0e5-9e2e001b9441 下载时间:2010年11月14日
更多简介内容

评论


个人中心

意见反馈

求资源

回顶部

下载专区


TI 参考设计资源库

工业电子 汽车电子 个人电子
$(function(){ var appid = $(".select li a").data("channel"); $(".select li a").click(function(){ var appid = $(this).data("channel"); $('.select dt').html($(this).html()); $('#channel').val(appid); }) })