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

一根本原理

八叉树三维数据构造用八叉树来表示三维形体,并争论在这种表示下的各种操作及应用是在进入80后才比较全面地开展起来的;这种方法,既可以看成是四叉树方法在三维空间的推广,也可以认为是用三维体素阵列表示形体方法的一种改进;八叉树的规律构造如下：假设要表示的形体V可以放在一个充分大的正方体C内,C的边长为2 n,形体VC,它的八叉树可以用以下的递归方法来定义：八叉树的每个节点与C的一个子立方体对应,树根与C本身相对应,假设V＝C,那么V的八叉树仅有树根,假设V≠C,则将C等分为八个子立方体,每个子立方体与树根的一个子节点相对应;只要某个子立方体不是完全空白或完全为V2-5-1,从而对应的节点也就有了八个子节点;这样的递归推断、分割始终要进展到节点所对应的立方体或是完全空白,或是完全为VV交作肯定的“舍入”,使体素或认为是空白的,或认为是V如此所生成的八叉树上的节点可分为三类：灰节点,它对应的立方体局部地为V所占据；白节点,它所对应的立方体中无V的内容；黑节点,它所对应的立方体全为V后两类又称为叶结点;形体V关于C其上的节点要么是叶节点,要么就是有八个子节点的灰节点;根节点与C相对应,其它节点与C由于八叉树的构造与四叉树的构造是如此的相像,所以八叉树的存贮构造方式可以完全沿用四叉树的有关方法;因而,依据不同的存贮方式,八叉树也可以分别称为常规的、线性的、一对八的八叉树等等;另外,由于这种方法充分利用了形体在空上的相关性,因此,一般来说,它所占用的存贮空间要比三维体素阵列的少;但是实际上它还是使用了相当多的存贮,这并不是八叉树的主要优点;这一方法的主要优点在于可以格外便利地实现有广泛用途的集合运算例如可以求两个物体的并、交、差等运算,而这些恰是其它表示方法比较难以处理或者需要消耗很多计算资源的地方;不仅如此,由于这种方法的有序性及分层性,因而对显示精度和速度的平衡、隐线和隐面的消退等,带来了很大的便利,特别有用;二八叉树的存贮构造八叉树也分别称为规章八叉树、线性八叉树以及一对八式八叉树;不同的存贮构造的空间利用率及运算操作的便利性是不同的;分析说明,一对八式八叉树优点更多一些;1、规章八叉树规章八叉树的存贮构造用一个有九个字段的记录来表示树中的每个结点;其中一个其余的八个字段用来作为存放指向其八个子结点的指针;这是最普遍使用的表示树形数据的存贮构造方式;规章八叉树缺陷较多,最大的问题是指针占用了大量的空间;假定每个指针要用两个字节表示,而结点的描述用一个字节,那么存放指针要占总的存贮量的94％;因此,这种方法虽然格外自然,简洁把握,但在存贮空间的使用率方面不很抱负;2、线性八叉树线性八叉树留意考虑如何提高空间利用率;用某一预先确定的次序遍历八叉树例如2-5-2,表的每个元素与一个结点相对应;对于结点的描述可以丰富一点,例如用适当的方式来说明它是否为叶结点,假设不是叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等;这样,可以在内存中以紧凑的方式来表示线性表,可以不用指针或者仅用一个指针表示即可;线性八叉树不仅节约存贮空间,对某些运算也较为便利;但是为此付出的代价是丧失了肯定的敏捷性;例如为了存取属于原图形右下角的子图形对应的结点,那么必需先遍历了其余七个子图形对应的全部结点后才能进展存取,导致了很多与此相关的运算效率变低;因此尽管不少文章争论了这种八叉树的应用,但是仍很难令人满足;3、一对八式的八叉树一个非叶结点有八个子结点,为了确定起见,将它们分别标记为0,1,2,3,4,5,6,7;从上面的介绍可以看到,假设一个记录与一个结点相对应,那么在这个记录中描述的是这个结点的八个子结点的特性值;而指针给出的则是该八个子结点所对应记录的存放处,而且还隐含地假定了这些子结点记录存放的次序;也就是说,即使某个记录是不必要的例如,该结点已是叶结点,那么相应的存贮位置也必需空闲在那里图2-5-3,以保证不会错误地存取到其它同辈结点的记录;这样固然会有肯定的铺张,除非它是完全的八叉树,即全部的叶结点均在同一层次消灭,而在该层次之上的全部层中的结点均为非叶结点;为了抑制这种缺陷,有两条途径可以承受;一是增加计算量,在记录中增加肯定的信息,使计算工作适当削减或者更便利;栅格数据压缩存储方式之四叉树、八叉树编码四叉树编码quad-treecode四又树构造的根本思想是将一幅栅格地图或图像等分为四局部;逐块检查其格网属性值或灰度;假设某个子区的全部格网值都具有一样的值;则这个子区就不再连续分割,否则还要把这个子区再分割成四个子区;这样依次地分割,直到每个子块都只含有一样的属性值或灰度为止;的区分率是可变的,边界简单局部四叉树较高即分级多,区分率也高,而不需表示很多细节便利;四叉树编码的最大缺点是转换的不定性,用同一外形和大小的多边形可能得出多种不同的四叉树构造,故不利于外形分析和模式识别;但因它允很多边形中嵌套多边形即所谓“洞”这种构造存在,使越来越多的地理信息系统工作者都对四叉树构造很感兴趣;上述这些压缩数据的方法应视图形的简单状况合理选用,同时应在系统中备有相应的程序;另外,用户的分析目的和分析方法也打算着压缩方法的选取;四叉树构造按其编码的方法不同又分为常规四叉树和线性四叉树;常规四叉树除了记录叶结点之外,还要记录中间结点;结点之间借助指针联系,每个结点需要用六个量表达：四个叶结点指针,一个父结点指针和一个结点的属性或灰度值;这些指针不仅增加了数据贮存量,而且增加了操作的简单性;常规四叉树主要在数据索引和图幅索引等方面应用;线性四叉树则只存贮最终叶结点的信息;包括叶结点的位置、深度和本结点的属性或灰度值;所谓深度是指处于四叉树的第几层上;由深度可推知子区的大小;线性四叉树叶结点的编号需要遵循肯定的规章,这种编号称为地址码,它隐含了叶结点的位置和深度信息;最常用的地址码是四进制或十进制的Morton————————————————————————————————————————————八叉树构造就是将空间区域不断地分解为八个同样大小的子区域马上一个六面的立方体再分解为八个一样大小的小立方体,分解的次数越多,子区域就越小,始终到同—区域的属性单一为止;按从下而上合并的方式来说,就是将争论区空间先按—定的区分率将三维空间3合并,否则就记盘;依次递归运算,直到每个子区域均为单值为止;八叉树同样可分为常规八叉树和线性八叉树;常规八叉树的结点要记录十个位,即八个指向子结点的指针,—个指向父结点的指针和一个属性值或标识号;而线性八叉树则只需要记录叶结点的地址码和属性值;因此,它的主要优点是,其一节约存储空间,由于只需对叶结点编码,节约了大量中间结点的存储;每个结点的指针也免除了,而从根到某一特定结点的方向和路径的信息隐含在定位码之中,定位码数字的个位数显示区分率的凹凸或分解程度；其次,线性八叉树可直接寻址,通过其坐标值则能计算出任何输入结点的定位码称编码,而不必实际建立八叉树,并且定位码本身就是坐标的另—种形式,不必有意去存储坐标值;假设需要的话还能从定位码中猎取其坐标值称解码简洁实现象集合、相加等组合操作;八叉树主要用来解决地理信息系统中的三维问题;include““include<>include<>include<>include<>include<>include““/ // /Vec3makeVec3doublex,doubley,doublez{Vec3v3=Vec3malloc3 sizeofdouble;v30=x;v31=y;v32=z;returnv3;}Vec3copyVec3Vec3src{Vec3v3=Vec3malloc3 sizeofdouble;v30=src0;v31=src1;v32=src2;returnv3;}/ /Octreemake_octreeVec3min,Vec3max{lf,%.3lf,%.3lf...%.3lf,%.3lf,%.3lf\n“,o->min2,o->min1,o->min0,o->max2,o->max1,o->max0;/returno;}voidsubpointOctreeo,intoc,Vec3min,Vec3max{pvex_norm_p1,m_p2;POSITIONpos1,pos2;forpos1=o->,pos2=o->;pos1=NULL;{etHeadPosition;pos=NULL;{m_p=pvex_norvexoc.GetNextpos;newpvex_norm_p->x,m_p->y,m_p->z;}/5 pos0+.25+pos1+.5 pos1+.5+pos2 pos2;doubledist_sq_b=pos0+.8 pos0+.8+pos1 pos1+pos2 pos2;ifdist_sq_a<=.0625return;ifdist_sq_b<=.25return;return;}doubledemo3Vec3pos{/demo3:thesurfaceistinysphere,radius centeredat,.5,0functionreturns ifpointinsidesphereA, otherwise/doubledist_sq=pos0+.5 pos0+.5+pos1 pos1+pos2 pos2;return dist_sq<:;}doubledemo4Vec3pos{/demo4:waveysurfacefunctionreturns ifpoint”near”surface, otherwise/doublesurface_height=sinpos0 cos pos1 ;doubledistance_sq=pos2-surface_height pos2-surface_height;return distance_sq<:;}doubledemo5Vec3pos{/demo5:hemisphere,center0,0,0radius,cutbyplaneatz=0/doubleabs_dist_sq=pos0 pos0+pos1 pos1+pos2 pos2;doublesurf_dist_sq=abs_dist_sq-;ifsurf_dist_sq <0surf_dist_sq=-surf_dist_sq;ifpos2>0&&surf_dist_sq<return;elsereturn.0;}doubledemo6Vec3pos{/demo6:anotherwaveysurfacefunctionreturns ifpoint”near”surface, otherwise/doublesurface_height=sinpos0 +sin pos1 ;doubledistance_sq=pos2-surface_height pos2-surface_height;return distance_sq<:;}doubledemo7Vec3pos{/demo7:acylinderfunctionreturns ifpoint”near”surface, otherwise/doubledisc_dist_sq=pos1 pos1+pos2 pos2;doublesurf_dist_sq= disc_dist_sq-;ifsurf_dist_sq <0surf_dist_sq=-surf_dist_sq;if pos0> && pos0<{if surf_dist_sq<return;}return;}doubledemo8Vec3pos{/demo8:mandlebrot/intmax_iters=500;intit_count=0;doublecr,ci,zr,zi,new_zr,new_zi;intinside=1;/onlyexistsneartheplanez=0/ifpos2> ||pos2<return.0;zr=cr=pos0 zi=ci=pos1 ;whileit_count<max_iters&&inside{/z=z^2+c/it_count++;new_zr=zrzr-zizi+cr;new_zi=2zrzi+ci;zr=new_zr;zi=new_zi;inside=zr zr+zi zi< 20;}returnit_count==max_iters :;}doubledemo9Vec3pos,Octreeo{pvex_norm_p1,m_p2;POSITIONpo;doubledis;doublezx,zy,zz,tempx,tempy,tempz,temp;forinti=0;i<o->;i++{po=o->i;m_p1=pvex_noro->po;m_p2=pvex_noro->po;tempx=pos0-m_p1->x;tempy=pos1-m_p1->y;tempz=pos2-m_p1->z;temp=tempxm_p2->x+tempym_p2->y+tempzm_p2->z;zx=m_p1->x-tempm_p2->x;zy=m_p1->y-tempm_p2->y;zz=m_p1->z-tempm_p2->z;dis=sqrtpos0-zxpos0-zx+pos1-zypos1-zy+pos2-zzpos2-zz;7isdifferenttocorner0thenthefunctionreturns1/intoctree_needs_to_be_splitOctreeo{/inti;doublev=o->value0;fori=1;i<8;i++ifo->valuei=vreturn1;/ifwegothere,thenallcornershavethesamevalue/Returnthenumberoftriangularfacets,thearray“triangles“willbeloadedupwiththeverticesatmost5triangularfacets.0willbereturnedifthegridcelliseithertotallyaboveoftotallybelowtheisolevel./intPolygoniseGRIDCELLgrid,doubleisolevel,TRIANGLEtriangles{inti,ntriang;intcubeindex;Vec3vertlist12;intedgeTable256={0x0 ,0x109,0x203,0x30a,0x406,0x50f,0x605,0x70c,0x80c,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,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,0xaf0,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,0x3c6,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,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,0xc93,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 };inttriTable25616={{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{0,8,3,-1,-1,-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,-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,-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,-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,-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,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,-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},{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,11,10,1,3,9,5,4,-1,-1,-1,-1,-1,-1,-1},{4,9,5,0,8,1,8,10,1,8,11,10,-1,-1,-1,-1},{5,4,0,5,0,11,5,11,10,11,0,3,-1,-1,-1,-1},{5,4,8,5,8,10,10,8,11,-1,-1,-1,-1,-1,-1,-1},{9,7,8,5,7,9,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{9,3,0,9,5,3,5,7,3,-1,-1,-1,-1,-1,-1,-1},{0,7,8,0,1,7,1,5,7,-1,-1,-1,-1,-1,-1,-1},{1,5,3,3,5,7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{9,7,8,9,5,7,10,1,2,-1,-1,-1,-1,-1,-1,-1},{10,1,2,9,5,0,5,3,0,5,7,3,-1,-1,-1,-1},{8,0,2,8,2,5,8,5,7,10,5,2,-1,-1,-1,-1},{2,10,5,2,5,3,3,5,7,-1,-1,-1,-1,-1,-1,-1},{7,9,5,7,8,9,3,11,2,-1,-1,-1,-1,-1,-1,-1},{9,5,7,9,7,2,9,2,0,2,7,11,-1,-1,-1,-1},{2,3,11,0,1,8,1,7,8,1,5,7,-1,-1,-1,-1},{11,2,1,11,1,7,7,1,5,-1,-1,-1,-1,-1,-1,-1},{9,5,8,8,5,7,10,1,3,10,3,11,-1,-1,-1,-1},{5,7,0,5,0,9,7,11,0,1,0,10,11,10,0,-1},{11,10,0,11,0,3,10,5,0,8,0,7,5,7,0,-1},{11,10,5,7,11,5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{10,6,5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{0,8,3,5,10,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{9,0,1,5,10,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{1,8,3,1,9,8,5,10,6,-1,-1,-1,-1,-1,-1,-1},{1,6,5,2,6,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{1,6,5,1,2,6,3,0,8,-1,-1,-1,-1,-1,-1,-1},{9,6,5,9,0,6,0,2,6,-1,-1,-1,-1,-1,-1,-1},{5,9,8,5,8,2,5,2,6,3,2,8,-1,-1,-1,-1},{2,3,11,10,6,5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{11,0,8,11,2,0,10,6,5,-1,-1,-1,-1,-1,-1,-1},{0,1,9,2,3,11,5,10,6,-1,-1,-1,-1,-1,-1,-1},{5,10,6,1,9,2,9,11,2,9,8,11,-1,-1,-1,-1},{6,3,11,6,5,3,5,1,3,-1,-1,-1,-1,-1,-1,-1},{0,8,11,0,11,5,0,5,1,5,11,6,-1,-1,-1,-1},{3,11,6,0,3,6,0,6,5,0,5,9,-1,-1,-1,-1},{6,5,9,6,9,11,11,9,8,-1,-1,-1,-1,-1,-1,-1},{5,10,6,4,7,8,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{4,3,0,4,7,3,6,5,10,-1,-1,-1,-1,-1,-1,-1},{1,9,0,5,10,6,8,4,7,-1,-1,-1,-1,-1,-1,-1},{10,6,5,1,9,7,1,7,3,7,9,4,-1,-1,-1,-1},{6,1,2,6,5,1,4,7,8,-1,-1,-1,-1,-1,-1,-1},{1,2,5,5,2,6,3,0,4,3,4,7,-1,-1,-1,-1},{8,4,7,9,0,5,0,6,5,0,2,6,-1,-1,-1,-1},{7,3,9,7,9,4,3,2,9,5,9,6,2,6,9,-1},{3,11,2,7,8,4,10,6,5,-1,-1,-1,-1,-1,-1,-1},{5,10,6,4,7,2,4,2,0,2,7,11,-1,-1,-1,-1},{0,1,9,4,7,8,2,3,11,5,10,6,-1,-1,-1,-1},{9,2,1,9,11,2,9,4,11,7,11,4,5,10,6,-1},{8,4,7,3,11,5,3,5,1,5,11,6,-1,-1,-1,-1},{5,1,11,5,11,6,1,0,11,7,11,4,0,4,11,-1},{0,5,9,0,6,5,0,3,6,11,6,3,8,4,7,-1},{6,5,9,6,9,11,4,7,9,7,11,9,-1,-1,-1,-1},{10,4,9,6,4,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{4,10,6,4,9,10,0,8,3,-1,-1,-1,-1,-1,-1,-1},{10,0,1,10,6,0,6,4,0,-1,-1,-1,-1,-1,-1,-1},{8,3,1,8,1,6,8,6,4,6,1,10,-1,-1,-1,-1},{1,4,9,1,2,4,2,6,4,-1,-1,-1,-1,-1,-1,-1},{3,0,8,1,2,9,2,4,9,2,6,4,-1,-1,-1,-1},{0,2,4,4,2,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{8,3,2,8,2,4,4,2,6,-1,-1,-1,-1,-1,-1,-1},{10,4,9,10,6,4,11,2,3,-1,-1,-1,-1,-1,-1,-1},{0,8,2,2,8,11,4,9,10,4,10,6,-1,-1,-1,-1},{3,11,2,0,1,6,0,6,4,6,1,10,-1,-1,-1,-1},{6,4,1,6,1,10,4,8,1,2,1,11,8,11,1,-1},{9,6,4,9,3,6,9,1,3,11,6,3,-1,-1,-1,-1},{8,11,1,8,1,0,11,6,1,9,1,4,6,4,1,-1},{3,11,6,3,6,0,0,6,4,-1,-1,-1,-1,-1,-1,-1},{6,4,8,11,6,8,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{7,10,6,7,8,10,8,9,10,-1,-1,-1,-1,-1,-1,-1},{0,7,3,0,10,7,0,9,10,6,7,10,-1,-1,-1,-1},{10,6,7,1,10,7,1,7,8,1,8,0,-1,-1,-1,-1},{10,6,7,10,7,1,1,7,3,-1,-1,-1,-1,-1,-1,-1},{1,2,6,1,6,8,1,8,9,8,6,7,-1,-1,-1,-1},{2,6,9,2,9,1,6,7,9,0,9,3,7,3,9,-1},{7,8,0,7,0,6,6,0,2,-1,-1,-1,-1,-1,-1,-1},{7,3,2,6,7,2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{2,3,11,10,6,8,10,8,9,8,6,7,-1,-1,-1,-1},{2,0,7,2,7,11,0,9,7,6,7,10,9,10,7,-1},{1,8,0,1,7,8,1,10,7,6,7,10,2,3,11,-1},{11,2,1,11,1,7,10,6,1,6,7,1,-1,-1,-1,-1},{8,9,6,8,6,7,9,1,6,11,6,3,1,3,6,-1},{0,9,1,11,6,7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{7,8,0,7,0,6,3,11,0,11,6,0,-1,-1,-1,-1},{7,11,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{7,6,11,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{3,0,8,11,7,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{0,1,9,11,7,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{8,1,9,8,3,1,11,7,6,-1,-1,-1,-1,-1,-1,-1},{10,1,2,6,11,7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{1,2,10,3,0,8,6,11,7,-1,-1,-1,-1,-1,-1,-1},{2,9,0,2,10,9,6,11,7,-1,-1,-1,-1,-1,-1,-1},{6,11,7,2,10,3,10,8,3,10,9,8,-1,-1,-1,-1},{7,2,3,6,2,7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{7,0,8,7,6,0,6,2,0,-1,-1,-1,-1,-1,-1,-1},{2,7,6,2,3,7,0,1,9,-1,-1,-1,-1,-1,-1,-1},{1,6,2,1,8,6,1,9,8,8,7,6,-1,-1,-1,-1},{10,7,6,10,1,7,1,3,7,-1,-1,-1,-1,-1,-1,-1},{10,7,6,1,7,10,1,8,7,1,0,8,-1,-1,-1,-1},{0,3,7,0,7,10,0,10,9,6,10,7,-1,-1,-1,-1},{7,6,10,7,10,8,8,10,9,-1,-1,-1,-1,-1,-1,-1},{6,8,4,11,8,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{3,6,11,3,0,6,0,4,6,-1,-1,-1,-1,-1,-1,-1},{8,6,11,8,4,6,9,0,1,-1,-1,-1,-1,-1,-1,-1},{9,4,6,9,6,3,9,3,1,11,3,6,-1,-1,-1,-1},{6,8,4,6,11,8,2,10,1,-1,-1,-1,-1,-1,-1,-1},{1,2,10,3,0,11,0,6,11,0,4,6,-1,-1,-1,-1},{4,11,8,4,6,11,0,2,9,2,10,9,-1,-1,-1,-1},{10,9,3,10,3,2,9,4,3,11,3,6,4,6,3,-1},{8,2,3,8,4,2,4,6,2,-1,-1,-1,-1,-1,-1,-1},{0,4,2,4,6,2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{1,9,0,2,3,4,2,4,6,4,3,8,-1,-1,-1,-1},{1,9,4,1,4,2,2,4,6,-1,-1,-1,-1,-1,-1,-1},{8,1,3,8,6,1,8,4,6,6,10,1,-1,-1,-1,-1},{10,1,0,10,0,6,6,0,4,-1,-1,-1,-1,-1,-1,-1},{4,6,3,4,3,8,6,10,3,0,3,9,10,9,3,-1},{10,9,4,6,10,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{4,9,5,7,6,11,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{0,8,3,4,9,5,11,7,6,-1,-1,-1,-1,-1,-1,-1},{5,0,1,5,4,0,7,6,11,-1,-1,-1,-1,-1,-1,-1},{11,7,6,8,3,4,3,5,4,3,1,5,-1,-1,-1,-1},{9,5,4,10,1,2,7,6,11,-1,-1,-1,-1,-1,-1,-1},{6,11,7,1,2,10,0,8,3,4,9,5,-1,-1,-1,-1},{7,6,11,5,4,10,4,2,10,4,0,2,-1,-1,-1,-1},{3,4,8,3,5,4,3,2,5,10,5,2,11,7,6,-1},{7,2,3,7,6,2,5,4,9,-1,-1,-1,-1,-1,-1,-1},{9,5,4,0,8,6,0,6,2,6,8,7,-1,-1,-1,-1},{3,6,2,3,7,6,1,5,0,5,4,0,-1,-1,-1,-1},{6,2,8,6,8,7,2,1,8,4,8,5,1,5,8,-1},{9,5,4,10,1,6,1,7,6,1,3,7,-1,-1,-1,-1},{1,6,10,1,7,6,1,0,7,8,7,0,9,5,4,-1},{4,0,10,4,10,5,0,3,10,6,10,7,3,7,10,-1},{7,6,10,7,10,8,5,4,10,4,8,10,-1,-1,-1,-1},{6,9,5,6,11,9,11,8,9,-1,-1,-1,-1,-1,-1,-1},{3,6,11,0,6,3,0,5,6,0,9,5,-1,-1,-1,-1},{0,11,8,0,5,11,0,1,5,5,6,11,-1,-1,-1,-1},{6,11,3,6,3,5,5,3,1,-1,-1,-1,-1,-1,-1,-1},{1,2,10,9,5,11,9,11,8,11,5,6,-1,-1,-1,-1},{0,11,3,0,6,11,0,9,6,5,6,9,1,2,10,-1},{11,8,5,11,5,6,8,0,5,10,5,2,0,2,5,-1},{6,11,3,6,3,5,2,10,3,10,5,3,-1,-1,-1,-1},{5,8,9,5,2,8,5,6,2,3,8,2,-1,-1,-1,-1},{9,5,6,9,6,0,0,6,2,-1,-1,-1,-1,-1,-1,-1},{1,5,8,1,8,0,5,6,8,3,8,2,6,2,8,-1},{1,5,6,2,1,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{1,3,6,1,6,10,3,8,6,5,6,9,8,9,6,-1},{10,1,0,10,0,6,9,5,0,5,6,0,-1,-1,-1,-1},{0,3,8,5,6,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{10,5,6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{11,5,10,7,5,11,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{11,5,10,11,7,5,8,3,0,-1,-1,-1,-1,-1,-1,-1},{5,11,7,5,10,11,1,9,0,-1,-1,-1,-1,-1,-1,-1},{10,7,5,10,11,7,9,8,1,8,3,1,-1,-1,-1,-1},{11,1,2,11,7,1,7,5,1,-1,-1,-1,-1,-1,-1,-1},{0,8,3,1,2,7,1,7,5,7,2,11,-1,-1,-1,-1},{9,7,5,9,2,7,9,0,2,2,11,7,-1,-1,-1,-1},{7,5,2,7,2,11,5,9,2,3,2,8,9,8,2,-1},{2,5,10,2,3,5,3,7,5,-1,-1,-1,-1,-1,-1,-1},{8,2,0,8,5,2,8,7,5,10,2,5,-1,-1,-1,-1},{9,0,1,5,10,3,5,3,7,3,10,2,-1,-1,-1,-1},{9,8,2,9,2,1,8,7,2,10,2,5,7,5,2,-1},{1,3,5,3,7,5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{0,8,7,0,7,1,1,7,5,-1,-1,-1,-1,-1,-1,-1},{9,0,3,9,3,5,5,3,7,-1,-1,-1,-1,-1,-1,-1},{9,8,7,5,9,7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{5,8,4,5,10,8,10,11,8,-1,-1,-1,-1,-1,-1,-1},{5,0,4,5,11,0,5,10,11,11,3,0,-1,-1,-1,-1},{0,1,9,8,4,10,8,10,11,10,4,5,-1,-1,-1,-1},{10,11,4,10,4,5,11,3,4,9,4,1,3,1,4,-1},{2,5,1,2,8,5,2,11,8,4,5,8,-1,-1,-1,-1},{0,4,11,0,11,3,4,5,11,2,11,1,5,1,11,-1},{0,2,5,0,5,9,2,11,5,4,5,8,11,8,5,-1},{9,4,5,2,11,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{2,5,10,3,5,2,3,4,5,3,8,4,-1,-1,-1,-1},{5,10,2,5,2,4,4,2,0,-1,-1,-1,-1,-1,-1,-1},{3,10,2,3,5,10,3,8,5,4,5,8,0,1,9,-1},{5,10,2,5,2,4,1,9,2,9,4,2,-1,-1,-1,-1},{8,4,5,8,5,3,3,5,1,-1,-1,-1,-1,-1,-1,-1},{0,4,5,1,0,5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{8,4,5,8,5,3,9,0,5,0,3,5,-1,-1,-1,-1},{9,4,5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{4,11,7,4,9,11,9,10,11,-1,-1,-1,-1,-1,-1,-1},{0,8,3,4,9,7,9,11,7,9,10,11,-1,-1,-1,-1},{1,10,11,1,11,4,1,4,0,7,4,11,-1,-1,-1,-1},{3,1,4,3,4,8,1,10,4,7,4,11,10,11,4,-1},{4,11,7,9,11,4,9,2,11,9,1,2,-1,-1,-1,-1},{9,7,4,9,11,7,9,1,11,2,11,1,0,8,3,-1},{11,7,4,11,4,2,2,4,0,-1,-1,-1,-1,-1,-1,-1},{11,7,4,11,4,2,8,3,4,3,2,4,-1,-1,-1,-1},{2,9,10,2,7,9,2,3,7,7,4,9,-1,-1,-1,-1},{9,10,7,9,7,4,10,2,7,8,7,0,2,0,7,-1},{3,7,10,3,10,2,7,4,10,1,10,0,4,0,10,-1},{1,10,2,8,7,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{4,9,1,4,1,7,7,1,3,-1,-1,-1,-1,-1,-1,-1},{4,9,1,4,1,7,0,8,1,8,7,1,-1,-1,-1,-1},{4,0,3,7,4,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{4,8,7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{9,10,8,10,11,8,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{3,0,9,3,9,11,11,9,10,-1,-1,-1,-1,-1,-1,-1},{0,1,10,0,10,8,8,10,11,-1,-1,-1,-1,-1,-1,-1},{3,1,10,11,3,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{1,2,11,1,11,9,9,11,8,-1,-1,-1,-1,-1,-1,-1},{3,0,9,3,9,11,1,2,9,2,11,9,-1,-1,-1,-1},{0,2,11,8,0,11,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{3,2,11,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{2,3,8,2,8,10,10,8,9,-1,-1,-1,-1,-1,-1,-1},{9,10,2,0,9,2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{2,3,8,2,8,10,0,1,8,1,10,8,-1,-1,-1,-1},{1,10,2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{1,3,8,9,1,8,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{0,9,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{0,3,8,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}};/Determinetheindexintotheedgetablewhichtellsuswhichverticesareinsideofthesurface/cubeindex=0;if0<isolevelcubeindex|=1;if1<isolevelcubeindex|=2;if2<isolevelcubeindex|=4;if3<isolevelcubeindex|=8;if4<isolevelcubeindex|=16;if5<isolevelcubeindex|=32;if6<isolevelcubein