ROAM算法的一段翻译

4.2 动态连续三角网 数据挖掘论坛

世界空间中的格网是通过对每一个二叉树顶点赋一个世界空间位置w(v)确定的。当任意两个三角形在公用点或者公用边上不重合时，三角形二叉树就形成了连续的格网，这种连续的格网叫做二叉树三角网。

图4显示了二叉树三角网中具有典型相邻关系的三角形T，我们把T_B称作共享基边(V₀,V₁)的基邻居，把T_L称作共享左边(V_a,V₀)的左邻居，把T_R称作共享右边(V₁,V_a)的右邻居。

二叉树三角网的一个重要性质为：邻居既可能来自与T相同的二叉树l层，也可能是较精细的l+1层的左邻居或右邻居，或者是比T更粗糙的l-1层的基邻居。

数据挖掘交友

当T和T_B属于同一层l时，我们把对(T,T_B)称为一个方块，图4显示了包含方块的三角网的分割和合并过程。分割以后孩子 (T₀,T₁) 代替了T，而 (T_B0,T_B1) 则代替了T_B。分割操作在方块的中心产生了一个新的结点V_C。如果三角形T没有基邻居T_B，则只有T进行分割。当T和T_B（如果存在T_B）的孩子都在同一三角网中时，方块(T,T_B)就能够合并。我们把这样的情况称作三角网中可合并的方块。 数据挖掘研究院

分割和合并操作的一个重要特征时，三角网可能可以由经过一系列分割和合并操作后产生的三角网确定。 数据挖掘交友

通常使用提供简单的临时邻接形式的顶点来激活分割和合并操作。当时间间隔 时，考虑图4中 (T,T_B) 的分割情况。我们可以先不直接把V_C移动到新的位置W_c=W(V_c)上，而是根据时间从未分割的基边中点W_m=(W(V₀)+W(V₁))/2线性的移动，其移动函数为W_a(t)=(1-t)W_m+tW_c。合并也可以用同样的方法激活。

数据挖掘工具

当三角形T的基邻居T_B来自更粗糙的层次时，它不能直接分割。为了使T强制分割，必须首先使T_B强制分割，可以看出，这样将会引起更深层次的递归分割。图5 显示了一个4次分割的情况。 数据挖掘论坛

大于一个三角形的基本网格就可以用于表示带有边界的任意类型的曲面。

数据挖掘工具