 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第四节 三维几何模型 | ||||
 设己采取了上述两项措施,已知形体变换前的八叉树表示T1,己计算出 要做的复合变换R,要确定变换后形体的八叉树表示T2,可以写出如下的算法框架： 1. 遍历形体原来的八叉树T1,对遇到的每个黑结点,做下述步2。 2. 对遇到黑结点对应的正立方体做相应变换,得它新的一般来说是斜置的新位置。若这位置已超出定义八叉树的充分大正立方体C之外,报告出错;否则执行下述的步3。 3. 从要计算求出的目标树T2的根开始,检查2中确定的处于新位置立方体与T2中结点对应的直立的正立方体是否相交,分以下三种情况进行处理: (1) 不相交,说明正考查直立正立方体未被占据,可保持为白结点,不做处理。 (2) 直立的正立方体整个被占据,即它在变换后"斜置"立方体内,置对应结点为黑结点。 (3) 在上述两条均不成立时,生成当前结点的八个子结点,对八个子结点对应的八个直立子立方体,依次再递归执行步3。如果最终这八个结点被标上同样特性,比方为黑结点,则应再删掉这八个子结点而把它们的共同父结点置为黑。 算法中,主要工作是检查某个直立的正立方体与一个斜置的正立方体是否相交,。对所有黑结点对应正立方体处理相同,使得操作可以并行进行。  线性八叉树
在对立方体做八等分时,按一致的方式, 对分出的子立方体进行编号。若再分共进行n层，则每个结点可以用n位的八进制数的数串来表示,数串从左至右,第一位对应第一次划分，第二位对应第二位划分，依此类推。据此整个八叉树就可以根据对其做深度第一遍历而依次列出的黑结点的编号序列来表示 。 前图所示三维形体,其线性八叉树表示是: {0x,10,12,13,14,2x,4x,6x,7x} |
||||
 第一节
图形的分段表示第二节
二维形体的表示第三节
四叉树第四节
三维几何模型第五节
分形 |
