合并纹理图像技术

!""#$!% 计算机工程与应用 & 引言 预研基金项目中为了达到更好的真实性场景，提出了基于 合并纹理图像的纹理映射概念并且实现。 纹理映射是提高计算机三维图形真实感的有力手段，现在 市面上流行的 #’ 加速卡均支持纹理映射。纹理映射的一般过 程是对一组面指定一幅纹理图像，根据纹理映射方式生成面上 各顶点的纹理坐标；#’ 加速卡根据面顶点的纹理坐标和指定 的纹理图像完成纹理映射过程。 从这个过程可以看出纹理映射是以一个面，一个纹理图像 为单位，那么每个面都指定一幅纹理图像将是一种费力、费时 的工作。如果在实时生成图像系统中，不加改变地使用这种方 法，那么将加大建模的复杂度以及大大影响处理速度。 ’()*+,#’ 和 -.*/01 的绘制引擎均以状态机的方式工作， 在指定一幅纹理图像后，随后处理的各个面的顶点纹理坐标都 是相对于该纹理图像的。在面数一定的情况下，减少纹理图像 指定的次数可以提高绘制速度。从这个意义上来讲，纹理图像 越大，关联的面数越多越好。纹理图像的大小受 #’ 加速卡硬 件结构和卡上存储器的制约，其合理大小有一定的限度，’(2 )*+,#’3$" 推荐的纹理图像的大小为 !"435!"43。一般情况下用 于纹理映射的一幅纹理图像的尺寸在 #!5#! 到 !675!67 之 间，一个 !"435!"43 的大纹理图像可以包含几十幅乃至几百幅 小纹理图像，因此将小的纹理图像合并为大的纹理图像与硬件 系统是相容的。 从建模角度来讲，使用包含很多内容的大纹理图像也是非 常方便的。例如，对一个由很多面组成的几何形状映射几种不 同的纹理时，将纹理图像合并可以避免将面从结构上分开的复 杂性，同时也避免了将面分组导致的冗余计算，潜在地提高绘 制速度。使用大的纹理图像甚至可以实现一个面一个面地贴纹 理，“古墓丽影”的场景制作就采用了这种贴纹理的方式。 合并纹理图像包含两个方面的技术：自动纹理图像合并技 术及基于合并纹理图像的纹理映射工具。自动纹理图像合并技 术对整个场景进行遍历，对相关和邻近的景物进行纹理图像合 并工作。纹理映射工具根据应用目标可以有各种不同的设计， 其基本功能包括将小的纹理图像合并成大的纹理图像，在大的 纹理图像中指定一个图像区域作为当前纹理图像，另外还要包 括常规纹理映射的基本功能。 该文在“890!"""”的数据结构基础上研究自动纹理图像 合并技术及基于合并纹理图像的纹理映射工具设计技术。 ! 自动纹理图像合并技术 自动纹理图像合并处理施加于一个已经制作完成的场景， 其唯一目的是提高场景绘制速度。 “890!"""”中的场景使用层次结构组织，场景由若干个景 物组成，使用树结构将景物组织在一起，场景本身是一个景物。 当一个景物调用一个几何形状时，可以施加纹理映射。施加纹 理映射时，要指定一幅纹理图像，纹理坐标包含在几何形状内 部。由于早期的“:;0 三维图形开发工具包”没有提供使用合 并纹理图像进行纹理映射的工具，当一个几何形状要使用几个 纹理图像时，将残忍地将几何形状分解为几部分，使每部分对 应一个纹理图像。 合并纹理图像技术 李晗静 郭恒业 赵 辉 陈 爽 （哈尔滨工业大学计算机科学与技术学院，哈尔滨 &6"""&） <=>?(@：@(A?/B(/C@DEA?CF/CG?$+F> 摘 要 该文在“890!"""”基础上，提出了基于合并纹理图像的纹理映射技术。使用该技术可以解决为多个几何体制定 同一幅纹理图像，以及一个几何体的不同面映射不同的纹理图像。因此提高了工作效率，大大影响处理速度。 关键词 纹理映射 合并纹理图像 结点 数据结构 文章编号 &""!=3##&=（!""#）!%=""%"="! 文献标识码 H 中图分类号 ;I#%&$4& !"# !#$"%&’(# )* +"# ,)-.&%#/ !#0+(1# 2-34# 5& 63%7&%4 8() 6#%49# :"3) 6(& ,"#% ;"(3%4 （8F>.J,*) K+(*/+* ?/G ;*+A/F@FCL K+AFF@，M?)N(/ 9/D,(,J,* FO ;*+A/F@FCL，M?)N(/ &6"""&） <.=+13$+：9/ ,A(D .?.*)，P* DJN>(, ,A* ,*+A/F@FCL FO ,*Q,J)* >?..(/C N?D*G F/ ,A* +(C!"""，? ,FF@ OF) G*R*@F.(/C )*?@= ,(>* #’ C)?.A(+D ?..@(+?,(F/$S(,A ,A(D，P* +?/ DF@R* ,A*D* TJ*D,(F/D：O()D,，>?..(/C DF>* FNB*+,D NL F/* (>?C* FO ,*Q,J)*；D*+F/G，>?..(/C ,A* G(OO*)*/, *GC* FO F/* FNB*+, P(,A G(OO*)*/, (>?C*$;A*)*NL，,A* *OO(+(*/+L (D C)*?,@L (>.)FR*G ?/G D.**G FO .)F+*DD(/C ,A* (>?C* (D (/+)*?D*G$ >#9?)1/=：,*Q,J)* >?..(/C，,A* 8F>N(/*G 9>?C* FO ;*Q,J)*，UFG*，D,)J+,J)* FO G?,? 基金项目：国家部委预研基金项目 作者简介：李晗静，助研，主要研究方向为计算机图形学、虚拟现实技术。郭恒业，研究员，主要研究方向为计算机图形学、虚拟现实软硬技术、计算 机仿真。赵辉，副教授，主要研究方向为计算机图形学、虚拟现实软硬技术。陈爽，研究员，主要研究方向为计算机图形学、虚拟现实软硬 技术、计算机仿真、计算机通讯。 %" 计算机工程与应用 !""#$!% 合并纹理图像时要考虑同时合并几何形状，这样才能使合 并后的场景绘制效率更高。合并两个几何形状时只要将两个几 何形状的顶点合并在一起，同时将两个几何形状的面表合并 在一起即可。两个几何形状合并时可能存在重合的顶点和内 边，归并重合的顶点、剔除内边将提高绘制速度；通常情况下， 位置重合的顶点其纹理坐标不一定相同，根据 &’()*+#& 规范， 不能合并这类重合的顶点。顶点的纹理坐标取决于对应的纹理 图像在合并后的大纹理图像中的摆放位置，可以考虑纹理图像 合并时合理安排各纹理图像的位置，使重合的顶点可以归并， 内边可以剔除，如图 , 所示，面 -，. 的纹理图像若按（/）摆放， 则面 -，. 可以合并为一个面 0，重合的顶点被归并，内边被剔 除；若按（1）或（*）摆放，则面 -，. 不能合并。如果进行这种优 化处理则制约了纹理图像在合并纹理图像中的位置，处理过程 相当复杂，在自动合并处理时暂不考虑这类优化技术，仅将纹 理坐标碰巧相同的重合顶点归并为一点。 图 , 纹理图像位置和顶点合并的关系 合并纹理图像时要考虑纹理图像在合并后的大纹理图像 中的位置，合理的布局算法可以使缝隙和孔洞尽可能地少。这 是一类复杂的布局规划问题，该文不作进一步讨论。 合并纹理图像时要对顶点的原纹理坐标进行变换，得到顶 点在合并后的纹理图像中的纹理坐标。设顶点的原纹理坐标为 2、3，原纹理图像的宽和高为 4、5；合并后的纹理图像宽和高为 6、7，原纹理图像在合并后的纹理图像中的原点位置为 8、9， 顶点在合并后的纹理图像中的纹理坐标为 :、;，则：:<8= 2>4 ?6，;<9=3>5 ? 7。 # 基于合并纹理图像的纹理映射工具 在 @AB 三维图形开发工具包中，用一个纹理映射窗口实 现加载几何体、加载纹理图像、合并纹理图像和纹理映射的功 能。纹理映射窗口由两部分组成，左边显示几何体，右边是纹理 图像窗口。纹理映射类型选择放在工具栏上。 #$, 纹理图像窗口 纹理图像窗口对应一个合并的纹理图像。标准的合并纹理 图像大小为 !"CDE!"CD 象素点，用户可以定义更大或更小的合 并纹理图像。用户可以使用“新建（F)4）”功能创建一个空的合 并纹理图像，使用“打开（GH)I）”功能加载一个合并纹理图像， 使用“保存（J/3)）”功能将一个合并纹理图像保存到磁盘上。 在合并纹理图像上提供“插入（KIL)(+）”、“删除（&)M)+)）”、 “复制（0NH9）”等操作。插入操作将一幅图像加入到合并纹理图 像中，删除操作将选定的一幅图像从合并纹理图像中删除，复 制操作将合并纹理图像中一幅图像复制到另外的位置。在执行 插入和复制操作时，用户可以自由移动图像放置到合并纹理图 像中的任意位置。 主要的功能是加载一个纹理图像文件或把多个纹理图像 文件经编辑合并为一个纹理图像文件。以及在纹理映射过程 中，可以定义当前的纹理图像其中的一个图像块作为当前要映 射的纹理图像。并且，窗口中的纹理图像可以根据用户的需求 保存为相应的格式以备以后使用。 合并纹理图像与它内部各纹理图像的关系记录在一个链 表中，该链表中的数据将作为合并纹理图像的工程文件保存在 磁盘上，在打开合并纹理图像时使用。 合并后的纹理图像以 !C 位 .OP 格式保存在磁盘上，插入 的纹理图像文件可以是各种格式，在插入时转换为 .OP格式。 使用合并纹理图像对几何体进行纹理映射时，要在合并纹 理图像上选择一幅纹理图像或使用框选功能选择一个矩形纹 理图像区域。当用户在合并纹理图像中单击鼠标左键时，将自 动将选择捕捉到纹理图像上。 使用合并纹理图像进行纹理映射时不支持 :、; 方向纹理 重复和透明纹理，可以在纹理图像窗口中选择打开单个纹理图 像来使用这些功能。 #$! 纹理映射过程 在对一个几何体施加纹理映射时，激活一个纹理映射窗 口。在几何体窗口中可以选择全部面，部分面和单个面，在纹理 图像窗口中通过矩形选择框选择纹理图像，选择框的大小及在 合并纹理图像中的位置是计算纹理坐标的参数。 在“0KB!"""”原有的平面、球面、柱面、盒子等纹理映射类 型基础上添加逐个面进行纹理映射的功能，用户可以将合并纹 理图像中不同的纹理图像映射到不同的面上，也可以将同一纹 理图像映射到不同的面上，如图 ! 所示。逐面纹理映射时可以 通过图像拖拽面上的纹理图像施加平移、比例、旋转变换。 图 ! 纹理映射不同方式 #$# 使用合并纹理图像的策略 使用合并纹理图像的目的之一是在绘制过程中减少指定 纹理图像的次数。由于在绘制过程中是按景物的层次结构来绘 制景物，这就要求在使用合并纹理图像时，尽量将一个景物的 纹理图像放置在一个合并纹理图像中，避免邻近的几何体使用 不同的合并纹理图像；否则除了不能减少指定纹理图像的次 数，若发生从系统内存加载纹理图像到显示卡上的情况，那么 因为纹理图像比较大，不但不会提高绘制速度，相反会降低绘 制速度。 C 结论 自动纹理图像合并和基于自动纹理图像合并的纹理映射 技术已经在“0KB!"""”内部测试版本中实现，初步试用表明经 自动纹理图像合并处理过的场景绘制速度略有提高。合并纹理 图像的纹理映射工具是方便，实用的纹理映射制作工具，尤其 是提供了逐个面设置纹理映射的功能，弥补了“0KB!"""”的不 足。（收稿日期：!""# 年 , 月） 参考文献 ,$赵辉等$模拟训练视景系统、三维游戏开发工具 @B.B/Q).2’MR)( 的 （下转 ,!C 页） %, !""#$!% 计算机工程与应用 &’() *+,-+./+0 12 3 4564+* 7*5’/5/2 /*38.3(/5’8 9+30 :*5/+ ;+*/5<2 9+30 =*38/+0 &>?1’*/+0 ;388’/ ’((-* :*5/+ =*38/+0 =*38/+0 =*38/+0 ;+*/5<2 ;’8@+*.5’8 =*38/+0 ;’8@+*.5’8 &’A+* 7*5’/5/2 4’B0 （上接 %C 页） 设计DEF$计算机图形图像学报，C%%C；"C !$丛等$基于曲线的纹理映射DEF$计算机研究与发展，##（C） #$G*-(+ H32B’*，E’48 ?I383/50+.，:5BB53I J4513-B/$K+*6586 GLMJ*++. N5+B0. M’B24+0*3B L+/ O7+*3/5’8.DEF$;’I7-/+* =*3745(.，C%%"；!P（P）： CCQRC!P P$L3/238 ;’’*6，L+/4J+BB+*$9+3B>J5I+ O((B-.5’8 ;-BB586 <’* K’0+B. A5/4 &3*6+ O((B-0+*.D;F$S8：M*’( C%%T?;K L2I7’.5-I’8 S8/+*3(/5@+ #U> =*3745(.，C%%T：V#R%" &’() *+,-+./+0 12 3 B’A+* 7*5’/5/2 /*38.3(/5’8 9+30 :*5/+ ;+*/5<2 9+30 =*38/+0 =*38/+0 GB’()+0 :*5/+ GB’()+0 =*38/+0 GB’()+0 ;+*/5<2 GB’()+0 =*38/+0 GB’()+0 W564+* 7*5’/5/2 4’B0 表 ! 消除优先级反转的多版本 &>?1’*/+0X&’A+* 7*5’*5/2 /*38.3(/5’8 5. 31’*/+0 ;’8@+*.5’8X&’A+* 7*5’*5/2 /*38.3(/5’8 B’() (’8@+*/+0 /’ :*5/+ #$Q 基于优先级的时标排序协议（MJO） 在基本时标排序协议中，冲突操作的调度决定是基于事务 启动时赋予的时标。在基于优先级的执行环境中，如果低优先 级事务 JY 的时标大于高优先级事务 J 的时标，高优先级事务 J 可能在访问一个被低优先级事务 JY 先前访问过的数据项时 被夭折。这就是时标排序协议中的优先级反转。 解决以上问题的是在给事务赋予时标时考虑优先级。 首先将事务分组，分组时将时间按长度!分段，在同一分段内 到达的事务属于同一组，称为时标组，然后对同一时标组内的 事务按它们的实时优先级调度。每一事务被赋予两级时标：组 时标和实时时标。同一时标组中的事务其组时标相同，等于组 中第一个事务的到达时间。同一组中事务的实时时标由事务的 优先级决定，优先级越高，实时时标越大，因此，发生数据访问 冲突时，高优先级事务不会被同组中的低优先级事务夭折。实 时时标用于对同组中的事务访问请求排序，组时标用于对不同 组中的事务访问请求排序。对每一个数据项，系统记载了最近 访问过该数据项的事务的组时标与实时时标。MJO 协议算法 如下： 5<（6*’-7Z/5I+./3I7（J）[6*’-7Z/5I+./3I7（U）） J 3((+..+. U； 6*’-7Z/5I+./3I7（U）X6*’-7Z/5I+./3I7（J）； *+3B>/5I+Z/5I+./3I7（U）X*+3B>/5I+Z/5I+. /3I7（J）； +B.+ 5<（6*’-7Z/5I+./3I7（J）X6*’-7Z/5I+./3I7 （U）380 *+3B>/5I+Z/5I+./3I7（J）[ *+3B>/5I+Z/5I+./3I7（U）） J 3((+..+. U； *+3B>/5I+Z/5I+./3I7（U）X*+3B>/5I+Z/5I+. /3I7（J）； +B.+ J 5. 31’*/+0； P 实时嵌套事务优先级反转的解决方法 嵌套事务的可串行化可以通过锁式协议保证。这里采用文 献DPF中的嵌套事务模型，读者可参考文献DPF获得详细的上锁规 则。基于锁的并发控制协议在实时嵌套事务模型环境下会产生 优先级反转问题。与平淡事务一样也可以采用优先级继承协议 和优先级夭折协议解决实时嵌套事务中的优先级反转。 P$C 优先级继承协议 当一个父事务等待其子事务提交并且父事务有更高的优 先级，则提高所有子事务的优先级且保持子事务的相对优先级 不变。 当由于数据访问冲突而导致低优先级事务阻塞高优先级 事务，则低优先级事务继承高优先级事务的优先级并且立即将 高优先级传播给其家族。整个家族将以高优先级运行。 P$! 优先级夭折 在嵌套事务模型中夭折一个子事务可能导致其它子事务 夭折。这些夭折事务可能包括其后代，祖先及兄弟。如果一个中 等优先级的事务夭折一个低优先级的事务可能导致高优先级 的事务串联夭折，这显然违反了优先级夭折协议的原意。以下 是解决方法： 对每一个事务可以有两个优先级与之关联。一个为分派优 先级，由优先级分派过程赋值，另一个为虚拟优先级，由其家族 上下文导出。事务的虚拟优先级是其后代的最大分派优先级， 当一个子事务从其上级继承一个锁，它也继承了上级的虚拟优 先级。;M\ 的调度基于分派优先级，冲突解决基于虚拟优先级。 当两个事务冲突时，如果低虚拟优先级事务持有需要的数据， 高虚拟优先级的事务将夭折低虚拟优先级的事务。否则，低虚 拟优先级事务将等待。以上方法仍然会导致优先级反转，此时 可将优先级继承协议结合起来使用。 Q 结束语 该文对实时平淡事务和实时嵌套事务并发控制协议中出 现的优先级反转问题进行了分析并给出了一些解决办法，优先 级反转广泛存在于基于优先级的调度策略中，特定的应用环境 使用何种解决方法还需要作进一步的比较和研究。 （收稿日期：!""! 年 C" 月） 参考文献 C$刘云生$现代数据库技术DKF$北京：国防工业出版社，!""C !$; K ]*5.483，]386 = L458$9+3B>/5I+ L2./+IDKF$H+A N’*)：K(=*3A> W5BB ;’I7385+.，S8(，C%%T #$N->:+5 ;4+8，&+ =*-+8A3B0$9+.+3*(4 S..-+. <’* 3 H+./+0 J*38.3(/5’8 K’0+BDKF$S^^^，">VCV_>_#TQ>V ‘ %P，C%%P P$J W3*0+*，] 9’/4+*I+B$;’8(-**+8(2 ;’8/*’B S..-+. 58 H+./+0 J*38.> 3(/5’8.DEF$a&UG E’-*83B，C%%#；!（C）：#%RTP C!P