一种三维动画模型的自适应简化方法

摘要

本发明针对不同的三维动画模型和终端显示屏幕的分辨率，提出一种基于边折叠的移动图形简化算法，通过定义不同的模型精度感知因子，改进QEM误差度量，获得基于目标屏幕分辨率的感知度量，把不能被用户所感知的冗余数据进行简化，得到面片规模与屏幕显示精度匹配的简化模型。本发明中基于边折叠的简化方法可以在保证显示质量的前提下最大限度的降低三维动画模型的面片规模，因此它可以用在计算和显示能力比较低的三维动画终端显示应用中。

主权项

1.一种三维动画模型的自适应简化方法，其特征在于该简化方法基于边折叠简化算法，对网格图形的几何元素进行删除，以实现简化目的，并采用Garland的二次误差(QEM)来对简化进行误差控制，具体包括以下步骤：(1)检索动画模型中的空间三维动画前景模型和背景模型；(2)对前景模型进行自适应简化；(3)对背景模型进行自适应简化；其中，在步骤(1)中，所述动画模型定义为：在三维动画生成过程中使用的三维网格模型，具体可定义为空间中一个三角形的集合，这些三角形之间有公共点和公共边，把这样的三角形集合定义为动画模型M，M可由顶点集V＝(v₁，v₂，...，v_n)和三角形集合T＝(T₁，T₂，...，T_m)所组成的二元组(V，T)来表示；所述前景模型定义为：前景模型是指在动画中具有重要意义，参与动画动作的动画模型；具体来说就是在动画过程中位置角度发生变化，参与动画运动的动画模型；通常由动画作者在制作动画时设定；所述背景模型定义为：背景模型是指在动画中主要作为背景存在的，在动画过程中不发生位置移动和旋转的动画模型；通常由动画作者在制作动画时设定；其中，对前景模型进行自适应简化，具体包括如下步骤：1)获得精度控制系数n、图形视窗参数H_window和W_window、显示屏幕分辨率参数h_screen和w_screen参数；其中，所述精度控制系数n定义为：精度控制系数n表示在简化过程中使用的单位长度为n个屏幕像素所对应的空间长度；所述精度控制系数n由用户设定；所述图形视窗参数H_window和W_window定义为：H_window是图形空间中视窗的高度，W_window是图形空间中视窗的宽度；所述图形视窗参数H_window和W_window由系统获取；所述显示屏幕分辨率参数h_screen和w_screen定义为：h_screen是显示屏幕上一列所包含的像素数目，w_screen是显示屏幕上一行所包含的像素数目；2)对原始网格中的每个顶点V，计算其误差矩阵Q；其中，一个顶点移动到新顶点的误差表示为：$\Delta \left(v\right)=\Delta \left({\left[\begin{array}{cccc}{v}_x& v_y& v_z& 1\end{array}\right]}^T\right)=\underset{p\in \mathrm{planes}\left(v\right)}{\Sigma }{\left(p^{T}v\right)}^2=\underset{p\in \mathrm{planes}\left(v\right)}{\Sigma }{v}^T\left({\mathrm{pp}}^T\right)v$$=v^T\left(\underset{p\in \mathrm{planes}\left(v\right)}{\Sigma }\left(K_p\right)\right)v=v^{T}Q\left(v_i\right)v.$其中，K_P为4×4对称矩阵，即3)对原始网格中的每条边E(u，v)，计算精度感知因子M_edge，把边的两个端点代入边误差计算，取使误差值较小的一点作为新顶点，并把折叠误差值进行排序；其中，所述边E(u，v)的精度感知因子M_edge定义为：$M_{\mathrm{edge}}=\left\{\begin{array}{cc}1& (\frac{\left|\right|u-v\left|\right|}{n·ϵ}\ge 1)\\ \frac{\left|\right|u-v\left|\right|}{n·ϵ}& (\frac{\left|\right|u-v\left|\right|}{n·ϵ}<1)\end{array}\right.$其中||u-v||为点u与点v之间的空间距离；所述边E(u，v)的误差的计算公式定义为：Error′(uv)＝v^T(Q_u+Q_v)v·(M_edge)ⁿ；4)选出误差最小的边进行折叠；5)更新相关信息；6)如果没有达到简化目标，转到4)，否则结束；其中：所述简化目标为min(E)≥nε，其中min(E)为最短边长；步骤3)和步骤6)中n为精度控制系数，ε为一个屏幕像素在图形空间中所对应的长度；其中，对背景模型进行自适应简化，具体包括如下步骤：a)获得精度控制系数n、图形视窗参数H_window和W_window、显示屏幕分辨率参数h_screen和w_screen参数，其中：所述精度控制系数n定义为：精度控制系数n表示在简化过程中使用的单位长度为n个屏幕像素所对应的空间长度；所述图形视窗参数H_window和W_window定义为：H_window是图形空间中视窗的高度，W_window是图形空间中视窗的宽度；所述显示屏幕分辨率参数h_screen和w_screen定义为：h_screen是显示屏幕上一列所包含的像素数目，w_screen是显示屏幕上一行所包含的像素数目；b)对原始网格中的每个顶点V，计算其误差矩阵Q，其中：误差矩阵Q采用Garland的二次误差来计算获取，具体计算方法如下：一个顶点移动到新顶点的误差表示为：$\Delta \left(v\right)=\Delta \left({\left[\begin{array}{cccc}{v}_x& v_y& v_z& 1\end{array}\right]}^T\right)=\underset{p\in \mathrm{planes}\left(v\right)}{\Sigma }{\left(p^{T}v\right)}^2=\underset{p\in \mathrm{planes}\left(v\right)}{\Sigma }{v}^T\left({\mathrm{pp}}^T\right)v$$=v^T\left(\underset{p\in \mathrm{planes}\left(v\right)}{\Sigma }\left(K_p\right)\right)v=v^{T}Q\left(v_i\right)v.$其中，K_P为4×4对称矩阵，即c)对原始网格中的每条边E(u，v)，计算精度感知因子M_edge，把边的两个端点代入边误差计算，取使误差值较小的一点作为新顶点，并把折叠误差值进行排序；其中，所述边E(u，v)，u(a₁，a₂，a₃)，v(b₁，b₂，b₃)的精度感知因子M_edge定义为：$M_{\mathrm{edge}}=\left\{\begin{array}{cc}1& (\frac{\sqrt{{(a_1-b_1)}^2+{(a_2-b_2)}^2}}{n·ϵ}\ge 1)\\ \frac{\sqrt{{(a_1-b_1)}^2+{(a_2-b_2)}^2}}{n·ϵ}& (\frac{\sqrt{{(a_1-b_1)}^2+{(a_2-b_2)}^2}}{n}<1)\end{array}\right.;$所述边E(u，v)的误差的计算公式定义为：Error′(uv)＝v^T(Q_u+Q_v)v·(M_edge)ⁿ；d)选出误差最小的边进行折叠；e)更新相关信息；f)如果没有达到简化目标，转到d)，否则转到g)；其中：所述简化目标为min(E)≥nε，其中min(E)为最短边长；g)根据三维动画的视点P_view(x₀，y₀，z₀)，对简化后的背景模型进行背向面剔除；所述背向面的定义：动画模型中背向视点P_view(x₀，y₀，z₀)的三角面片；所述背向面剔除的具体方法为：对视点P_view(x₀，y₀，z₀)和三角面片F(u，v，w)，u(a₁，a₂，a₃)，v(b₁，b₂，b₃)，w(c₁，c₂，c₃)，该三角面片所在平面方程为：Ax+By+Cz+D＝0其中A＝a₂×(b₃-c₃)+b₂×(c₃-a₃)+c₂×(a₃-b₃)B＝a₃×(b₁-c₁)+b₃×(c₁-a₁)+c₃×(a₁-b₁)C＝a₁×(b₂-c₂)+b₁×(c₂-a₂)+c₁×(a₂-b₂)D＝-a₁×(b₂×c₃-c₂×b₃)-b₁×(c₂×a₃-a₂×c₃)-c₁×(a₂×b₃-b₂×a₃)当Ax₀+By₀+Cz₀+D≤0成立时，三角面片F(u，v，w)为无法在屏幕上显示，也无法被视点感知的背向面片，可以直接剔除；当Ax₀+By₀+Cz₀+D＞0成立时，三角面片F(u，v，w)为可以显示的正向面片，需要保留；如果有一个点v，包含v的所有面片都是背向面片，当所有背向面片都被剔除后，从点列表中将v剔除。