一种地质体线性八叉树快速动态生成的方法

摘要

该发明提供了一种地质体面模型快速动态生成其线性八叉树的方法，利用深度缓存判断体元在实体内外，通过栈结构来存储八叉树分解的情况，对栈的操作中输出编码，省去了结点的复杂排序和压缩过程，进一步利用深度缓存的信息，对地质体进行分块并按分块实时构造线性八叉树，从而实现地质体的快速构建和可视化，能很好的对隐伏矿体预测中的地质对象进行模拟与分析。

主权项

1.本发明涉及一种地质体线性八叉树快速动态生成的步骤包括：步骤一：基于深度缓存判断体素与地质体的内外关系采用深度缓存判断体素在地质体的内外，设置与X，Y，Z轴垂直时的大小为2ⁿ×2ⁿ的三对深度缓存，将三对深度缓存分别标记为[X₁，X₂]、[Y₁，Y₂]、[Z₁，Z₂]，其中每对中的第一项存储的最近深度值，另一项存储最远深度值，用这三对深度缓存建立等价于八叉树空间的立方体区域包围地质体，包围盒的三个对立面分别与X，Y和Z轴垂直，且对应于与其所垂直坐标轴上的那对深度缓存，设空间中有一坐标为(x，y，z)的体素(I，J，K)，对其做如下判断：IF((X₁(K，J)≤x≤X₂(K，J))AND(Y₁(I，K)≤y≤Y₂(I，K))AND(Z₁(I，J)≤z≤Z₂(I，J)))，如果返回真，则体素在地质体内，属性为黑，否则在地质体外，属性为白。对于一个八分体O，若划分次数为l(l＜n)，O可视为在2^l×2^l×2^l空间下的“体素”，则其属性可通过类似的方法判断，建立3对深度图像[X’₁，X’₂]、[Y’₁，Y’₂]、[Z’₁，Z’₂]，深度图像按一定规则从[X₁，X₂]、[Y₁，Y₂]、[Z₁，Z₂]中采样获得；设{X’_min 1，Y’_min 1，Z’_min 1}和{X’_max 1，Y’_max 1，Z’_max 1}，{X’_min 2，Y’_min 2，Z’_min 2}和{X’_max 2，Y’_max 2，Z’_max 2}分别以最小值和最大值采样规则从X’₂，Y’₂，Z’₂中获得，O中心点实际坐标为(x，y，z)，在2^l×2^l×2^l空间下行列层坐标为(I_O，J_O，K_O)，边长为a，单个体素的边长为δ，则O的属性可按如下规则判断：步骤二：对地质体进行八分体划分确定与地质体相关的八分体，即确定被地质体完全占据(黑)，部分占据(灰)还是不含地质体(白)的八分体，只有在属性为非白的八分体中才可能产生线性八叉树编码，而属性为白的八分体则无需考虑，对每个非白八分体进行处理并确定其中体素的属性，从而生成该八分体中所包含地质体对应的线性八叉树，当处理完所有非白八分体后，整个地质体的线性八叉树将构造完成，这一过程用自底向上构造八叉树的方法来进行，首先指定对空间划分的最大次数l并将空间划分为2^l×2^l×2^l个小八分体，用深度缓存判断各个小八分体的属性，在这些小八分体中，如果存在8个八分体属于同一个父八分体且属性都为黑，则将这8个八分体合并，从底向上一直合并上去，直到不能合并为止，从此，地质体被划分到各个属性为非白的八分体空间中，下一步确定剩下的部分，即确定不完全八叉树中非白叶结点的分解情况，从而生成地质体的线性八叉树。步骤三：生成地质体线性八叉树按先序遍历顺序处理不完全八叉树中的各非白叶结点，在遍历过程中按不同方法处理不完全八叉树中黑叶结点与灰叶结点，当遇到不完全八叉树中的每个黑结点时，可直接输出其线性八叉树编码，而对灰叶结点，则要扫描其所对应八分体，在扫描中判断其中各体素的属性，从而确定结点的分解情况。(1)扫描灰八分体每个灰叶结点所对应的灰八分体都可视为一个2^m×2^m×2^m大小的子空间，采用一个2×2×2大小的窗口按Morton码的Z序扫描该子空间，下文称该窗口所扫描的2×2×2八分体为窗八分体，扫描从子空间的首位置码处开始，每到一处比较深度缓存中的深度值来检查窗口内体素的属性，再比较窗口内体素间的属性返回窗八分体的属性：黑、白或灰，解码得到下个窗口坐标，一直循环扫描下去，执行又一次窗扫描，直到位置码到2^m×2^m×2^m结束，在每次检查中，将分解所得的黑叶结点编码动态输出，当窗扫描发现活动结点分解时，输出其分解所得的黑已知结点编码，并存储新活动结点与未知结点以记录下八叉树分解的情况。利用一个栈结构存储这些结点的局部位置码及在所在层，栈中的每个元素对应树的一个结点，结点按其窗扫描顺序与出栈顺序一致的原则存储在栈中，并保证栈顶存储的是活动结点，扫描过程中若发现活动结点分解，弹出栈顶，压入活动结点下的未知子结点和新的活动结点来更新树的分解情况，同时根据被弹出的旧活动结点得到新的已知结点，在栈操作中，动态输出子空间中地质体的线性八叉树编码。(2)结点分解的确定本发明称活动结点自上到下分解所截止的那一层为体素V的最底分解层，求V的最底分解层可通过检查V在其各层祖先结点中的位置来求得，检查从窗八分体所对应结点(第m层)开始，至此向上展开，一旦发现V不是其在第k(k＜m)层祖先结点的首位置体素，该结点为灰，第k层为最底分解层，检查停止。(3)栈操作先弹出栈顶，获得活动结点信息，然后从顶向下输出活动结点以下各层中的黑已知结点的线性八叉树编码，并压入活动结点以下各层中新的未知子结点，直到最底分解层为止，最后压入新的活动结点，完成栈更新，设活动结点为N_a，N_a分解所得的在第l层中的第k号结点为N_a(l，k)，栈更新过程如下：1)弹出栈顶，得到N_a信息：位置码M和所在层l₀，令当前分解层l＝l₀+1；2)判断第l层否高于或等于V的最底分解层l_d，如是则转3)，否则转7)；3)根据当前窗口位置码，求窗八分体在第l层的祖先结点N_a(l，p)；4)如果上一窗八分体属性为黑(说明V之前的体素为黑)，输出第l层中属性为黑的已知结点的线性八叉树编码：顺序产生从N_a(l，0)至N_a(l，p-1)在子空间下的局部编码，将其与对应于子空间的灰八分体全局位置码求和并输出；5)压入在第l层中的未知结点：将该层未知结点从N_a(l，7)至N_a(l，p+1)逆序压入栈中；6)令l＝l+1，转2)；7)压入新活动结点：在栈中压入窗八分体在最底分解层l_d上的祖先结点N_a(l_d，p)，返回。当活动结点扫描完成后，它转成已知结点，进行出栈操作，首先弹出栈顶，根据栈顶信息将对应于活动结点的线性八叉树编码输出，将窗八分体属性视为活动结点属性，若窗八分体属性为白，则一定不含黑体素，不产生编码，否则生成并输出对应于活动结点的编码。