八叉树三维数据结构及示例程序

1、八叉树三维数据结构（一）基本原理    用八叉树来表示三维形体，并研究在这种表示下的各种操作及应用是在进入80年代后才比较全面地开展起来的。这种方法，既可以看成是四叉树方法在三维空间的推广，也可以认为是用三维体素阵列表示形体方法的一种改进。    八叉树的逻辑结构如下：    假设要表示的形体V可以放在一个充分大的正方体C内，C的边长为2 n，形体V C，它的八叉树可以用以下的递归方法来定义：    八叉树的每个节点与C的一个子立方体对

2、应，树根与C本身相对应，如果VC，那么V的八叉树仅有树根，如果VC，则将C等分为八个子立方体，每个子立方体与树根的一个子节点相对应。只要某个子立方体不是完全空白或完全为V所占据，就要被八等分（图2-5-1），从而对应的节点也就有了八个子节点。这样的递归判断、分割一直要进行到节点所对应的立方体或是完全空白，或是完全为V占据，或是其大小已是预先定义的体素大小，并且对它与V之交作一定的“舍入”，使体素或认为是空白的，或认为是V占据的。    如此所生成的八叉树上的节点可分为三类：    灰节点，它对应的立方体部分地为V所

3、占据；    白节点，它所对应的立方体中无V的内容；    黑节点，它所对应的立方体全为V所占据。    后两类又称为叶结点。形体V关于C的八叉树的逻辑结构是这样的：它是一颗树，其上的节点要么是叶节点，要么就是有八个子节点的灰节点。根节点与C相对应，其它节点与C的某个子立方体相对应。    因为八叉树的结构与四叉树的结构是如此的相似，所以八叉树的存贮结构方式可以完全沿用四叉树的有关方法。因而，根据不同的存贮方式，八叉树也可以分别称为常规

4、的、线性的、一对八的八叉树等等。    另外，由于这种方法充分利用了形体在空上的相关性，因此，一般来说，它所占用的存贮空间要比三维体素阵列的少。但是实际上它还是使用了相当多的存贮，这并不是八叉树的主要优点。这一方法的主要优点在于可以非常方便地实现有广泛用途的集合运算(例如可以求两个物体的并、交、差等运算，而这些恰是其它表示方法比较难以处理或者需要耗费许多计算资源的地方。不仅如此，由于这种方法的有序性及分层性，因而对显示精度和速度的平衡、隐线和隐面的消除等，带来了很大的方便，特别有用。（二）八叉树的存贮结构    八

5、叉树有三种不同的存贮结构，分别是规则方式、线性方式以及一对八方式。相应的八叉树也分别称为规则八叉树、线性八叉树以及一对八式八叉树。不同的存贮结构的空间利用率及运算操作的方便性是不同的。分析表明，一对八式八叉树优点更多一些。 1、规则八叉树    规则八叉树的存贮结构用一个有九个字段的记录来表示树中的每个结点。其中一个字段用来描述该结点的特性(在目前假定下，只要描述它是灰、白、黑三类结点中哪一类即可，其余的八个字段用来作为存放指向其八个子结点的指针。这是最普遍使用的表示树形数据的存贮结构方式。    规则八叉树缺陷较

6、多，最大的问题是指针占用了大量的空间。假定每个指针要用两个字节表示，而结点的描述用一个字节，那么存放指针要占总的存贮量的94。因此，这种方法虽然十分自然，容易掌握，但在存贮空间的使用率方面不很理想。2、线性八叉树    线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树(例如以深度第一的方式，将八叉树转换成一个线性表（图2-5-2），表的每个元素与一个结点相对应。对于结点的描述可以丰富一点，例如用适当的方式来说明它是否为叶结点，如果不是叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等。这样，可以在内存中以紧凑的方式来表示线性表，

7、可以不用指针或者仅用一个指针表示即可。    线性八叉树不仅节省存贮空间，对某些运算也较为方便。但是为此付出的代价是丧失了一定的灵活性。例如为了存取属于原图形右下角的子图形对应的结点，那么必须先遍历了其余七个子图形对应的所有结点后才能进行；不能方便地以其它遍历方式对树的结点进行存取，导致了许多与此相关的运算效率变低。因此尽管不少文章讨论了这种八叉树的应用，但是仍很难令人满意。3、一对八式的八叉树    一个非叶结点有八个子结点，为了确定起见，将它们分别标记为0，1，2，3，4，5，6，7。从上面的介绍可以看到，如果

8、一个记录与一个结点相对应，那么在这个记录中描述的是这个结点的八个子结点的特性值。而指针给出的则是该八个子结点所对应记录的存放处，而且还隐含地假定了这些子结点记录存放的次序。也就是说，即使某个记录是不必要的(例如，该结点已是叶结点，那么相应的存贮位置也必须空闲在那里（图2-5-3），以保证不会错误地存取到其它同辈结点的记录。这样当然会有一定的浪费，除非它是完全的八叉树，即所有的叶结点均在同一层次出现，而在该层次之上的所有层中的结点均为非叶结点。    为了克服这种缺陷，有两条途径可以采纳。一是增加计算量，在记录中增加一定的信息，使计算工作适当减少或者更方便

9、。栅格数据压缩存储方式之四叉树、八叉树编码四叉树编码(quad-tree code  四又树结构的基本思想是将一幅栅格地图或图像等分为四部分。逐块检查其格网属性值(或灰度。如果某个子区的所有格网值都具有相同的值。则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。 四叉树编码法有许多有趣的优点：容易而有效地计算多边形的数量特征；阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；栅格到四叉树及四叉树到简

10、单栅格结构的转换比其它压缩方法容易；多边形中嵌套异类小多边形的表示较方便。四叉树编码的最大缺点是转换的不定性，用同一形状和大小的多边形可能得出多种不同的四叉树结构，故不利于形状分析和模式识别。但因它允许多边形中嵌套多边形即所谓“洞”这种结构存在，使越来越多的地理信息系统工作者都对四叉树结构很感兴趣。上述这些压缩数据的方法应视图形的复杂情况合理选用，同时应在系统中备有相应的程序。另外，用户的分析目的和分析方法也决定着压缩方法的选取。四叉树结构按其编码的方法不同又分为常规四叉树和线性四叉树。常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指

11、针，一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。线性四叉树则只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值。所谓深度是指处于四叉树的第几层上。由深度可推知子区的大小。线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是四进制或十进制的Morton码。八叉树结构就是将空间区域不断地分解为八个同样大小的子区域(即将一个六面的立方体再分解为八个相同大小的小立方体，分解的次数越多，子区域就越小，一直到同区域的属性单一为止。按从下

12、而上合并的方式来说，就是将研究区空间先按定的分辨率将三维空间划分为三维栅格网，然后按规定的顺序每次比较3个相邻的栅格单元，如果其属性值相同则合并，否则就记盘。依次递归运算，直到每个子区域均为单值为止。八叉树同样可分为常规八叉树和线性八叉树。常规八叉树的结点要记录十个位，即八个指向子结点的指针，个指向父结点的指针和一个属性值(或标识号。而线性八叉树则只需要记录叶结点的地址码和属性值。因此，它的主要优点是，其一节省存储空间，因为只需对叶结点编码，节省了大量中间结点的存储。每个结点的指针也免除了，而从根到某一特定结点的方向和路径的信息隐含在定位码之中，定位码数字的个位数显示分辨率的高低或分解程度；其

13、次，线性八叉树可直接寻址，通过其坐标值则能计算出任何输入结点的定位码(称编码，而不必实际建立八叉树，并且定位码本身就是坐标的另种形式，不必有意去存储坐标值。若需要的话还能从定位码中获取其坐标值(称解码；其三，在操作方面，所产生的定位码容易存储和执行，容易实现象集合、相加等组合操作。八叉树主要用来解决地理信息系统中的三维问题。#include "stdafx.h"#include #include #include #include #include #include "octree.h"/* - */* - */Vec3 makeVec3( double

14、 x, double y, double zVec3 v3 = (Vec3 malloc(3 * sizeof(double;v30 = x; v31 = y; v32 = z;return v3;Vec3 copyVec3( Vec3 src Vec3 v3 = (Vec3 malloc(3 * sizeof(double;v30 = src0; v31 = src1; v32 = src2;return v3;/* - */Octree* make_octree( Vec3 min, Vec3 max /Octree* o = (Octree* malloc(sizeof(Octree;O

15、ctree* o = new Octree;o->min = copyVec3(min;o->max = copyVec3(max;o->children = 0;o->at_max_depth = 0;/*printf("creating octree %.3lf,%.3lf,%.3lf . %.3lf,%.3lf,%.3lfn", o->min2, o->min1, o->min0,o->max2, o->max1, o->max0 ;*/return o;void subpoint( Octree* o,in

16、t oc,Vec3 min, Vec3 maxpvex_nor *m_p1,*m_p2;POSITION pos1,pos2;for(pos1=o->vex.GetHeadPosition(,pos2=o->normal.GetHeadPosition(;pos1!=NULL;/pos1=o->vex.FindIndex(i;/pos2=o->normal.FindIndex(i;m_p1=(pvex_nor*o->vex.GetNext(pos1;m_p2=(pvex_nor*o->normal.GetNext(pos2;if(m_p1->x>

17、min0&&m_p1->x y>min1&&m_p1->y &&(m_p1->z>min2&&m_p1->z o->childrenoc->vex.AddHead(new pvex_nor(m_p1->x,m_p1->y,m_p1->z;o->childrenoc->normal.AddHead(new pvex_nor(m_p2->x,m_p2->y,m_p2->z;void split_octree( Octree* o doubl

18、e oc_min3;double oc_max3;Vec3 mid = makeVec3( (o->min0 + o->max0 * 0.5, (o->min1 + o->max1 * 0.5, (o->min2 + o->max2 * 0.5 ;int xp, yp, zp;int oc = 0;/o->children = (Octree* malloc( 8 * sizeof(Octree*;o->children = new Octree*;for(zp=0; zp < 2; zp+if(zp = 0 oc_min2 = o->

19、;min2;oc_max2 = mid2;elseoc_min2 = mid2;oc_max2 = o->max2;for(yp=0; yp < 2; yp+if(yp = 0 oc_min1 = o->min1;oc_max1 = mid1;elseoc_min1 = mid1;oc_max1 = o->max1;for(xp=0; xp < 2; xp+if(xp = 0 oc_min0 = o->min0;oc_max0 = mid0;elseoc_min0 = mid0;oc_max0 = o->max0;o->children (zp*

20、4 + (yp*2 + xp = make_octree( oc_min, oc_max ;subpoint( o,(zp*4 + (yp*2 + xp,oc_min,oc_max;/* - */int recursively_evaluate_octree( int min_depth, int max_depth, int current_depth, Octree* o int deepest_child = current_depth;/int xp, yp, zp;int oc;int cd;/pvex_nor *m_p;/POSITION pos;/*Vec3 point = ma

21、keVec3(0,0,0;int p = 0;for(zp=0; zp < 2; zp+point2 = (zp = 0 ? o->min2 : o->max2;for(yp=0; yp < 2; yp+ point1 = (yp = 0 ? o->min1 : o->max1;for(xp=0; xp < 2; xp+ point0 = (xp = 0 ? o->min0 : o->max0;o->value p+ = evaluate_point( point,o;*/o->density=evaluate1_point(o

22、;current_depth+;o->not_fully_divided = (char octree_needs_to_be_split( o ;if( current_depth <= max_depth if( current_depth <= min_depth | ( o->not_fully_divided /if(deepest_child=current_depth|deepest_child=0/split_octree( o ;/ for(oc = 0; oc < 8; oc+/*Vex.RemoveAll(;for( pos = vexoc.

23、GetHeadPosition(; pos != NULL; m_p=(pvex_nor*vexoc.GetNext( pos ;Vex.AddHead(new pvex_nor(m_p->x,m_p->y,m_p->z;*/if(deepest_child=current_depth|deepest_child=0/cd = recursively_evaluate_octree( min_depth, max_depth, current_depth, o->children oc ;/if(cd > deepest_childdeepest_child =

24、cd;elseo->at_max_depth = 1;return deepest_child;/* - */int subdivide_octree( int min_depth, int max_depth, Octree* o return recursively_evaluate_octree(min_depth, max_depth, 0, o ;double demo1( Vec3 pos /* demo 1: the surface is a sphere of radius 0.75 centered at 0,0,0 function returns 1.0 if po

25、int inside sphere, 0.0 otherwise */double dist_sq = (pos0 * pos0 + (pos1 * pos1 + (pos2 * pos2;return ( dist_sq < 0.5625 ? 1.0 : 0.0;double demo2( Vec3 pos /* demo 2: the surface is two spheres, A: radius 0.25 centered at -.25,-.5,0 and B: radius 0.5 centered at -0.5,0,0 function returns 1.0 if p

26、oint inside sphere A, 2.0 for sphere B, 0.0 for neither*/double dist_sq_a = (pos0+.25 * (pos0+.25 + (pos1+.5 * (pos1+.5 + (pos2 * pos2;double dist_sq_b = (pos0+.8 * (pos0+.8 + (pos1 * pos1 + (pos2 * pos2;if( dist_sq_a <= .0625 return 1.0;if( dist_sq_b <= .25 return 2.0;return 0.0;double demo3(

27、 Vec3 pos /* demo 3: the surface is tiny sphere, radius 0.1 centered at -.5,.5,0 function returns 1.0 if point inside sphere A, 0.0 otherwise*/double dist_sq = (pos0+.5 * (pos0+.5 + (pos1-.5 * (pos1-.5 + (pos2 * pos2;return ( dist_sq < 0.01 ? 1.0 : 0.0;double demo4( Vec3 pos /* demo 4: wavey surf

28、acefunction returns 1.0 if point 'near' surface , 0.0 otherwise*/double surface_height = sin( (pos0 * 3.0 * cos ( (pos1 * 3.0 ;double distance_sq = (pos2 - surface_height * (pos2 - surface_height;return ( distance_sq < 0.01 ? 1.0 : 0.0;double demo5( Vec3 pos /* demo 5: hemisphere, center

29、0,0,0 radius 0.5, cut by plane at z=0*/double abs_dist_sq = (pos0 * (pos0 + (pos1 * (pos1 + (pos2 * pos2;double surf_dist_sq = abs_dist_sq - 0.5625;if(surf_dist_sq < 0surf_dist_sq = -surf_dist_sq;if( (pos2 > 0 && (surf_dist_sq < 0.1 return 1.0;elsereturn .0;double demo6( Vec3 pos /*

30、 demo 6: another wavey surfacefunction returns 1.0 if point 'near' surface , 0.0 otherwise*/double surface_height = sin( (pos0 * 2.0 + sin ( (pos1 * 2.0 ;double distance_sq = (pos2 - surface_height * (pos2 - surface_height;return ( distance_sq < 0.01 ? 1.0 : 0.0;double demo7( Vec3 pos /*

31、demo 7: a cylinderfunction returns 1.0 if point 'near' surface , 0.0 otherwise*/double disc_dist_sq = (pos1 * (pos1 + (pos2 * pos2;double surf_dist_sq = disc_dist_sq - 0.5625;if(surf_dist_sq < 0surf_dist_sq = -surf_dist_sq;if( ( pos0 > -0.75 && ( pos0 < 0.75 if( surf_dist_sq

32、 < 0.1 return 1.0;return 0.0;double demo8( Vec3 pos /* demo8 : mandlebrot */int max_iters = 500;int it_count = 0;double cr, ci, zr, zi, new_zr, new_zi;int inside = 1;/* only exists near the plane z=0 */if(pos2 > 0.001 | (pos2 < -0.001return .0;zr = cr = (pos0 * 2.0;zi = ci = (pos1 * 2.0;whi

33、le(it_count < max_iters && (inside/* z = z2 + c */it_count+;new_zr = (zr*zr - (zi*zi + cr;new_zi = (2*zr*zi + ci;zr = new_zr;zi = new_zi;inside = (zr * zr + (zi * zi < (2.0 * 20;return (it_count = max_iters ? 1.0 : 0.0;double demo9( Vec3 pos, Octree *opvex_nor *m_p1,*m_p2;POSITION po;d

34、ouble dis;double zx,zy,zz,tempx,tempy,tempz,temp;for(int i=0;i vex.GetCount(;i+ po=o->vex.FindIndex(i;m_p1=(pvex_nor *o->vex.GetAt(po;m_p2=(pvex_nor *o->normal.GetAt(po;tempx=pos0-m_p1->x;tempy=pos1-m_p1->y;tempz=pos2-m_p1->z;temp=tempx*m_p2->x+tempy*m_p2->y+tempz*m_p2->z;

35、zx=m_p1->x-temp*m_p2->x;zy=m_p1->y-temp*m_p2->y;zz=m_p1->z-temp*m_p2->z;dis=sqrt(pos0-zx*(pos0-zx+(pos1-zy*(pos1-zy+(pos2-zz*(pos2-zz;/dis=sqrt(pos0-m_p1->x*(pos0-m_p1->x+(pos1-m_p1->y*(pos1-m_p1->y/+(pos2-m_p1->y*(pos2-m_p1->y;if(dis<0.1 goto loop;loop:return

36、(dis<0.1 ? 1.0 : 0.0;/* - */double evaluate_point( Vec3 pos,Octree *o return demo9( pos,o ;int evaluate1_point( Octree *o int tCnt=o->vex.GetCount(+1;return(tCnt;/* - */* returns 1 if the octree should be split, 0 otherwise */*this implementation checks whether all 8 corner values are the same

37、(if any corner 1.7 is different to corner 0 then the function returns 1*/int octree_needs_to_be_split( Octree* o /*int i;double v = o->value0;for(i=1; i < 8; i+if( o->valuei != vreturn 1;/* if we got here, then all corners have the same value */return 0;if(o->density>40 return 1;else

38、return 0;void isoface(Octree* o char bf2;/CPtrList vexlist,norlist;float v1,v2,v3;ifstream file("ww9.obj"if(!o->vex.IsEmpty(o->vex.RemoveAll(;if(!o->normal.IsEmpty(o->normal.RemoveAll(; if(!file.fail(while(!file.eof(file>>bf>>v1>>v2>>v3;if(bf0='v'

39、;&&bf1=0o->vex.AddTail(new pvex_nor(v1,v2,v3;if(bf0='v'&&bf1='n'o->normal.AddTail(new pvex_nor(v1,v2,v3;/o->vex=vexlist;file.close(;/*Linearly interpolate the position where an isosurface cutsan edge between two vertices, each with their own scalar value*/Vec

40、3 VertexInterp(double isolevel,Vec3 p1,Vec3 p2,double valp1,double valp2double mu;Vec3 p= makeVec3(0,0,0;if (fabs(isolevel-valp1 < 0.00001return(p1;if (fabs(isolevel-valp2 < 0.00001return(p2;if (fabs(valp1-valp2 < 0.00001return(p1;mu = (isolevel - valp1 / (valp2 - valp1;p0 = p10 + mu * (p20

41、 - p10;p1 = p11 + mu * (p21 - p11;p2 = p12 + mu * (p22 - p12;return(p;/*Given a grid cell and an isolevel, calculate the triangularfacets required to represent the isosurface through the cell.Return the number of triangular facets, the array "triangles"will be loaded up with the vertices a

42、t most 5 triangular facets.0 will be returned if the grid cell is either totally aboveof totally below the isolevel.*/int Polygonise(GRIDCELL grid,double isolevel,TRIANGLE *trianglesint i,ntriang;int cubeindex;Vec3 vertlist12;int edgeTable256=0x0 , 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,0x8

43、0c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,0x190, 0x99 , 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,0x230, 0x339, 0x33 , 0x13a, 0x636, 0x73f, 0x435, 0x53c,0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,0x3a0, 0x2a9, 0x1a3, 0xaa ,

44、0x7a6, 0x6af, 0x5a5, 0x4ac,0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,0x460, 0x569, 0x663, 0x76a, 0x66 , 0x16f, 0x265, 0x36c,0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff , 0x3f5, 0x2fc,0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf

45、0,0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55 , 0x15c,0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc ,0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc,0xcc , 0x1c5, 0x2cf, 0x

46、3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c,0x15c, 0x55 , 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,0x2fc, 0x3f5, 0xff , 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65,

47、 0xc6c,0x36c, 0x265, 0x16f, 0x66 , 0x76a, 0x663, 0x569, 0x460,0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa , 0x1a3, 0x2a9, 0x3a0,0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c,0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33 , 0x339, 0x230,0xe90, 0xf99, 0xc9

48、3, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c,0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99 , 0x190,0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c,0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0 ;int triTable25616 =-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,0, 8, 3, -1, -1,

49、-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,9, 2, 10, 0, 2, 9, -1

50、, -1, -1, -1, -1, -1, -1, -1, -1, -1,2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1,3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,1, 11, 2, 1, 9, 11, 9, 8, 11,

51、 -1, -1, -1, -1, -1, -1, -1,3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1,3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1,9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,4, 7, 8, -1, -1, -1, -1, -1, -1, -1,

52、-1, -1, -1, -1, -1, -1,4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1,1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1,

53、 -1,9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1,2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1,8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1,9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1,4, 7, 11, 9, 4, 11,

54、9, 11, 2, 9, 2, 1, -1, -1, -1, -1,3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1,1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1,4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1,4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1,9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1,

55、-1, -1, -1, -1, -1,9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1,1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1,

56、5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1,2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1,9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1,0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1,2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1,10, 3