Hierarchical structuring of scenes with MKtrees

Hierarchical structuring of scenes with MKtrees Omar Rodr´ıguez Gonz´alez Marta Franquesa Niub´o Facultad de Ingenier´ıa Departament de Llenguatges Universidad Aut´onoma i Sistemes Inform`atics de San Luis Potos´ı Universitat Polit`ecnica de Catalunya San Luis Potos´ı, M´exico Barcelona, Espa˜na [email protected] [email protected]c.edu 13th January 2005 Abstract The location of an object or parts of an object in huge environments is of fundamental importance in several research areas. The problem to locate an object or parts of an object in very complex systems (environments with large number of objects) has been studied by several authors, contributing with a large number of solutions based on different hierarchical representations of the scenes. In this research report, an implementation of a Multiresolution K dimensional tree (Multiresolution Kdtree, MKtree) and its results are presented. A MKtree represents a hierarchical subdivision of the scene objects, that guarantees a minimum space overlap between node regions in large environments. The implementation is related to ship design applications where the number and distribution of objects are considered complex. This will serve for later inclusion of methods to better approximate objects with tighter bounding volumes. 1 Introduction The realism needed in several areas such as robotics, computer animation and any application where large environments (also called complex systems) are used has stimulated the need to research for efficient techniques in model simplification, mesh compression, real-time rendering, and collision detection tests. Referring to the collision detection problem, the term hybrid collision detection, introduced by Kitamura et al. in [KTAK94], arises when more than two objects are moving in the same space. The hybrid collision detection refers to any collision detection method which first performs one or more iterations of approximate test to study whether objects interfere in the workspace and 1 BROAD PHASE                    DELIMITATION LEVELS      INPUT: N-BODIES USE OF HIERARCHICAL STRUCTURES OUTPUT: n-BODIES (SUBSET OF N-BODIES) ACCURATE BROAD LEVEL      INPUT: n-BODIES USE OF SIMPLE BOUNDING REPRESENTATIONS OUTPUT: 2-CANDIDATE BODIES LIST NARROW PHASE                    REFINEMENT LEVELS      INPUT: 2-BODIES USE OF HIERARCHICAL STRUCTURES OUTPUT: CANDIDATE PARTS OF THE 2-BODIES EXACT LEVEL      INPUT: 2-BODIES OR CANDIDATE PARTS OF 2-BODIES USE THE GEOMETRY OF OBJECTS OUTPUT: COLLIDING FEATURES Figure 1: Phases of the global collision detection problem then, performs a more accurate tests to identify the objects parts causing the interference. Hubbard [Hub95] reports two collision tests encompassing two phases: the broad phase, where approximate interferences are detected, and the narrow phase where exact collision detection is performed. O’Sullivan and Dingliana [O’S99, OD99] extended the hybrid collision detection classification phases pointing out that the narrow phase itself consists of several levels of intersection testing between two objects at increasing level of accuracy, where the last one may be exact. They referred the most accurate level as narrow phase: exact level and the phase of testing for collision using increasing levels of accuracy as narrow phase: progressive refinement levels. Franquesa and Brunet [FNB03] extended the broad phase pointing that it may consist of two subphases too. In the first one, tests are performed to find subsets of objects of the entire workspace where collisions can occur, rejecting, at the same time, all the space regions where interference is not possible. In the second subphase, the collision test determines the candidate objects that can cause collision. They refer the first subphase as broad phase: progressive delimitation levels and, the second subphase as broad phase: accurate broad level. Figure 1 summarizes the main features of each phase. The broad phase is well suited not only for the collision detection problem, but also can be applied to other techniques as, real-time rendering, viewdependent rendering, etc. This research report is based on the work of Franquesa in [FN04], in which the broad phase is covered with the proposal of the MKtrees, a data structure 2 useful when performing simultaneously space and scene subdivision. The narrow phase is approached using a collision prediction solution based on the work of Kim and Rossignac [KR03], in which the time and location of collisions are computed directly from the relative motion of pairs of objects. A software system for MKtrees construction is implemented and is presented as the foundation for future research (see section 5). One of the main methods for MKtrees construction and its results are evaluated and visual output results are obtained from several samples. This software implementation creates a complete MKtree structure of a complex scene (in this case an oil tanker), and writes a new file with the results of the first subdivision in the hierarchical structure, whose visualization gives an overall idea about the results of the algorithms. 1.1 Previous related work We give a brief overview on the related work applied to different application contexts. 1.1.1 Spatial partition hierarchies This methods decomposes the space in a hierarchical way. The Regular Grids of Boxes model is based on a grid of equal sizes boxes over the space (also called voxels), which can be unit cubes [HKM95, MPT99], or parallelepipeds [GASF94]. Thus, objects are presented by a 3D matrix of voxels. The octrees [Sam90] is a tree of degree eight (octants) which represents the space occupied by objects contained in a space defined by cubes. But not only cubes are used in octrees, [Hub93, PG95] used spheres trees. A Bintree [ST85] is a recursive dimension-independent subdivision of the space, whose cuts are exactly half of the original space and orthogonal to the coordinate axis. A Binary Space Partition tree (BSPtree) [TN87] recursively divides the space into two subspaces, each separated by a plane of arbitrary orientation and position. A Kdtree [Ben75], is a binary space partition tree whose cuts are orthogonal to the coordinate axis. A Multiresolution Kdtree (or MKtree) [FNB03] represents a hierarchical subdivision of a scene, that guarantees a minimum space overlap between node regions in large environments. 1.1.2 Bounding volume hierarchies The bounding volume hierarchies approximate a representation of an object as representation hierarchy, known as Bounding Volume tree (BVtree). The SphereTrees [Hub93] represents objects by sets of spheres. Two methods are commonly used for the construction of the SphereTree, medial-axis surface [Qui94, Hub95, Hub96, OD99, BO03], and fitting spheres to a polyhedron 3 and shrinking them until they just fit [RB79]. The Axis-Aligned Bounding Box trees (AABBtrees) [BKSS90] are based in boxes with axis-aligned faces. An Oriented Bounding Box tree (OBBtree) [GLM96] represents an object by an enclosed oriented box. The kDOP trees [KHM+98] are a set of discrete oriented polytopes bounding the volume. In [YSLM04], a clustered hierarchy of progressive meshes is used as a dual hierarchy, a BV hierarchy with clusters bounded by OBB, and a multiresolution hierarchy of the object. [LAM03] proposed a bounding-volume tree over morphing objects for collision detection, updating the tree with the same morphing function used for the vertices of the object. [JP04] create a Bounded Deformation Tree (BD-Tree) with spheres as BV for fast collision detection with generic deformable models. 1.2 The problem to be solved Create a suitable framework to continue testing and researching with MK- trees is the primary goal of this research report. This will allow us to explore new methods applied over objects in complex systems. The problem is directed to rigid polyhedra in fixed localizations in space. The main interest is related to create a hierarchical structure of a complex environment in ship design applications that will serve to incorporate new approximative representations of scenes and objects as sphere-trees or kDOP trees. This structure, combined with the approximative representations, will help us to speed up different tests (point classification, collision detection, . . . ). This implementation develops one of the three MKtrees construction algorithms presented in the section 4.2 of [FN04], the Splitting Overlap Algorithm (SOA). This algorithm distributes objects of the scene minimizing the number of objects that intersect the overlapping space between node regions, and creates another structure (SplitTree) inside the overlapping space. 2 MKtrees structure This class of tree represents a hierarchical subdivision of the scene objects that guarantees a minimum space overlap between subtree regions. This structure is useful for collision detection queries and objects classification. 2.1 Description The MKtrees has the following features: •The MKtree represents a hierarchical subdivision of the objects in the scene that minimizes the number of objects in the overlap regions. 4 •The algorithms for MKtree simultaneously partition the space and the scene objects. •Bounding approximations of objects can be used. •The method has been conceived to manage memory efficiently. The MKtrees are useful to treat objects inside a ship design environment, where most objects are pipes (mainly, 1D), walls (mainly, 2D) and some equip-elements (3D). Objects usually are oriented to coordinate axis, as pipes, or oriented to coordinate planes, as walls. The objects in the scene are rigid and static solids. Before describing the MKtrees, some related definitions are presented: Definition 2.1.1 The environment, S, is defined as a collection of 3D objects, usually polyhedra. Thus, S={o1, ..., oN} Definition 2.1.2 R(S)is the axis-aligned bounding box, AABB, of the set S.R(Sn)is the AABB of a subset Sn, with Sn⊂S Assumption: There exists a function InP age(Sn) that returns true if all the geometry of Snfits in the space reserved for one tree leaf - ddisk blocks (and can be retrieved to the core memory in ddisk access operations): function InP age(Sn)return bool return (GeometrySize(Sn)≤MemP age) end function Where MemP age is a global constant that indicates the size of one leaf. MemP age =d∗OneBlockSize We can describe a MKtree as follows: A MKtree is a tree, MKT (S), that specifies a hierarchy on S, where Sis a set of objects. Each node, n, of the MKT (S) corresponds to a subset Sn⊂S, where the root is associated with the full set S. Each internal node nhas two children. The union of the object subsets associated to the children of nis equal to Sn. Each node nis associated to the AABB box of Sn:R(Sn). Sn1and Sn2are the subsets associated with the children of n. Assume that exists a wDivideList procedure that divides the collection of objects belonging to Snin two subsets Sn1, and Sn2minimizing the overlap between R(Sn1) and R(Sn2) (where wcan be x,yor z). The performance of a MKtree is related to the selection of the splitting rules to build the hierarchy. The main goal is that during the tree construction 5 subsets Sn1and Sn2of objects can be assigned to each child of a node, n, in such a way that they can be spatially separated. A node of a MKtree can be defined as: •If InP age(Sn), then nis a leaf node and stores the geometry of objects in Sn •If no InP age(Sn), then nis a leaf node with information on the overlap region and two pointers to n1and n2, respectively. Sn1and Sn2are obtained by the wDivideList minimum overlap value where wcan be x,yor z. Given a node n, the procedure wDivideList splits the set of objects Sninto subsets Sn1and Sn2taking into account the direction in which the minimum overlap has been found, SplitDir. Thus the SplitDir is a unit vector being (1,0,0), (0,1,0) or (0,0,1). Definition 2.1.3 π0and π1are two oriented half-spaces that bound the overlap region: •π0is the half-space of the first face of R(Sn2)in the SplitDir direction •π1is the half-space of the last face of R(Sn1)in the SplitDir direction •Every object of R(Sn2)is in π1 •Every object of R(Sn1)is in π0 •The overlap region is the intersection of R(Sn),π0and π1 •The overlap size is the distance between the planes π0and π1 In this way the tree construction procedure generates a subdivision and a hierarchy of all objects of Swith a minimum number of objects intersecting the overlap space. The method to implement performs a spatial splitting of the overlap region using a compact KdTree, the SplitTree (SpTree). Each node nof the MKtree, corresponding to a subset Sn, is defined as: •If InP age(Sn), then nis a leaf node and stores a pointer to the geometry of objects in Sn •If no InP age(Sn), then nis an internal node and it is represented by: –The splitting direction SplitDir –The bounding box R(Sn) –The planes defining the overlap region: π0and π1 6 –Two pointers to the son nodes n1and n2(associated to the object sets Sn1and Sn2 –The corresponding SpT ree (hierarchical set of half spaces). The internal nodes of the MKtree (including the SpTrees of the nodes) are stored in main memory. Leaf nodes storing the geometry of the objects use out-of-core storage. 3 MKtrees construction The Splitting Overlap Algorithm (SOA) distributes objects over the children minimizing the number of objects that intersect the overlapping space between node regions. Then, the algorithm computes an SpTree with the objects that belong to the overlapping spaces. The wDivideList for the SOA algorithm is based on the following concepts: 1. Objects that belong to Snare sorted in increasing order of wcoordinate (w=x,yor z). 2. The wmaximum coordinate value of objects that belong to Sn1(Sn1= o1..oft,ft = first to be treat) of the objects set Sn, determines the half-space π0. 3. The wminimum coordinate value of objects that belong to Sn2(Sn2= oN−lt..oN,lt = last to be treat and N= number of objects in Sn) of the objects set Sn, determines the half-space π1. 4. The space between π0and π1is the overlapping space between the regions of the subtrees. 5. Objects in Snare classified in several groups depending on their positions with respect to half-spaces π0and π1, as follows: •W W Objects: Group of objects that fall on the left of π0. In other words, W W Objects = Set of objects oisuch that oi∈Sn1 and Classif(oi, π0) = out. This group of objects will be included to the subset Sn1. •BBObjects: Group of objects that fall on the right of π1. In other words, BBObjects = Set of objects oisuch that oi∈Sn2 and Classif(oi, π1) = out. This group of objects will be included to the subset Sn2. •OverObjects: Subset of objects, say Sm, that intersects the overspace limited by π0and π1. This group of objects will be used to compute the SpTree. Then, Smwill be distributed over Sn1and 7 Sn2, before building the subtree for Sn.Smis made out of three subsets Sw,SBand SIn such that: –SIn (or InObjects): Objects that fall between π0and π1, this means that are totally inside the overspace. In other words, SIn = Set of objects oisuch that Classif(oi, π0) = in and Classif(oi, π1) = in. –SW(or W Objects): Objects that only intersects the π0plane. In other words, SW= Set of objects oisuch that oi∈Sn1 and oiis neither a W W Object nor an InObject. –SB(or BObjects): Objects that only intersects the π1plane. In other words, SB= Set of objects oisuch that oi∈Sn2 and oiis neither a BBObject nor an InObject. W Objects are intersected by the plane of π0, whereas BObjects are intersected by the plane of the the half-space π1. Note that the way π0and π1 planes are selected, does not allow objects to intersect the two planes at the same time. 3.1 Algorithms description The construction of the software was made using the P3D library used in the Alice 1software to read the p3d file containing the oil tanker of the complex scene. While reading the geometric information from the file, an AABB for each element in the scene is constructed and stored in main memory. Better bounding volumes with the MKtrees can be used, instead of AABB, but this remains as future research (see section 5). With the AABB of each object (or level of detail = 1, LOD = 1), the elements are processed to build the MKtree by the SOA algorithm. Colors are assigned to the elements after the first subdivision occurs in the algorithm. At the end, the AABB representation of each object in the MKtree is written with the P3D library into an output p3d file which can be visualized using the Alice software. The procedure BuildMKtree is the implementation of the SOA algorithm (see algorithm 1). It has six arguments, the actual MKtree node mkt, the list of objects Snstarting from geomini to geomend, the number of objects N, the limit, ratio, of the sublist of objects that will be examined r(with 0≤r≤1), and the level tree in which the nodes will be colorized. The parameter rhelps the tree to be more or less balanced depending on its value. When splitting a set of objects Snwith Nobjects, Sn={o1, . . . , oN}, the sublist of objects to be examined is defined by the following rank of object indices: {ok}with k∈[r∗N..(1.0−r)∗N]. 1http://www.lsi.upc.es/dept/crv/webcrv/investigacion ing archivos/alice.htm 8 procedure BuildMKtree(mkt, geomini, geomend, N, r, level) if no InP age(geomini, geomend)then {Initialize mkt} fT =F irst(geomini, N, r) fT =Last(geomend, N, r) {ft = firstTreat, lT = lastTreat} for SpDir in [x, y, z]do SortGeom(geomini, N, SpDir, min) MinObjOver(geomini, geomend, fT, lT, SpDir, min, minOb) SortGeom(geomini, N, SpDir, max) MinObjOver(geomini, geomend, fT, lT, SpDir, max, minOb) end for SubSetOverlapObj(minOb, geomini, Sn1, Sn2, Sm) Sp =gnSplitT ree(Sm, mkt) if level == 1 then AssignColors(Sm, Sn1, Sn2) end if DivideSets(mkt, Sm, Sn1, Sn2) BuildMKtree(mktleftchild, Sn1ini, Sn1end, N, r, (level −1)) BuildMKtree(mktrightchild, Sn2ini, Sn2end, N, r, (level −1)) else {MkTree node is a terminal node and points to geometry} return end if end procedure Algorithm 1: Build a MKtree The algorithm 1 works as follows: when the total size of the geometry of Snis bigger than the user defined block size (InP age(geomini, geomend) is false), the best dimension and location is computed for SpDir, sorting six times the actual objects list (SortGeom procedure) and finding the minimum object overlap region (MinObjOver procedure). The resulting region is stored in the structure minOb. The actual list of objects is then distributed over three subsets: Sn1,Sn2and Sm, taking into account the half-spaces π0and π1(SubSetOverlapObj procedure). The third subset, Sm, corresponds to the minimum set of objects that intersect the overlapping space, and used to compute and create a SpTree Sp (gnSplitT ree function). If the MKtree level is 1, colors are assigned to all the elements in the three subsets Sn1,Sn2 and Sm(AssignColors procedure). Objects in Smare then distributed in the subsets Sn1and Sn2, which are recursively called in the BuildMKtree procedure. 9 [PG95] I.J. Palmer and R.L. Grimsdale. Collision detection for animation using sphere-trees. Computer Graphics Forum, 1995. [Qui94] S. Quinlan. Efficient distance computation between non–convex objects. In Proceedings of the IEEE Int. Conf. on Robotics and Automation, pages 3324–3329, 1994. San Diego, CA. [RB79] J.O. Rourke and N. Badler. Decomposition of three–dimensional objects into spheres. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI–1(3):295–305, July 1979. [Sam90] H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1990. ISBN 0-201-50255-0. [ST85] H. Samet and M. Tamminen. Bintrees, CSG trees, and time. In ACM SIGGRAPH Conf. Proc., pages 121–130, July 1985. Computer Graphics vol. 19 num. 3. [TN87] W.C. Thibault and B.F. Naylor. Set operations on polyhedra using binary space partitioning trees. In ACM Computer Graphics, volume 21, pages 153–162, July 1987. [YSLM04] Sung-Eui Yoon, Brian Salomon, Ming Lin, and Dinesh Manocha. Fast Collision Detection between Massive Models using Dynamic Simplification. In Proceedings of the Eurographics Symposium on Geometry Processing, 2004. 16 Appendix A Source code // Splitting Overlap Algorithm (SOA) void BuildMKTree(mktree *mkt, AABB *inigeom, AABB *endgeom, UInt32 nobjs, Float32 r, UInt8 level) { splittree *Sp; AABB *Sn1 = NULL, *Sn2 = NULL, *Sm = NULL;; UInt8 SpDir; tminOb minOb; if (!InPage(inigeom, endgeom)) { mkt->iniobjects = NULL; mkt->endobjects = NULL; AABB *newbox = (AABB*) malloc(sizeof(AABB)); newbox->leftAABB = newbox->rightAABB = NULL; newbox->xmin = newbox->ymin = newbox->zmin = 999999.99; newbox->xmax = newbox->ymax = newbox->zmax = -999999.99; newbox->numvertices = 0; AABB *run = inigeom; while (run != NULL) { if (run->xmin < newbox->xmin) newbox->xmin = run->xmin; if (run->ymin < newbox->ymin) newbox->ymin = run->ymin; if (run->zmin < newbox->zmin) newbox->zmin = run->zmin; if (run->xmax > newbox->xmax) newbox->xmax = run->xmax; if (run->ymax > newbox->ymax) newbox->ymax = run->ymax; if (run->zmax > newbox->zmax) newbox->zmax = run->zmax; run = run->rightAABB; } mkt->boundbox = newbox; for (SpDir = XDIR; SpDir <= ZDIR; SpDir++) { SortGeom(inigeom, 1, nobjs, SpDir, MIN); MinObjOver(inigeom, endgeom, First(inigeom, nobjs, r), Last(endgeom, nobjs, r), SpDir, MIN, &minOb); SortGeom(inigeom, 1, nobjs, SpDir, MAX); MinObjOver(inigeom, endgeom, First(inigeom, nobjs, r), Last(endgeom, nobjs, r), SpDir, MAX, &minOb); } SubSetOverlapObj(&minOb, &inigeom, &Sn1, &Sn2, &Sm); mkt->overobjects = minOb.nobjs; mkt->pi0 = minOb.pi0; 17 mkt->pi1 = minOb.pi1; mkt->SpDir = minOb.SpDir; Sp = gnSplitTree(Sm, mkt); mkt->sptree = Sp; if (level == 1) AssignColors(Sm, Sn1, Sn2); DivideSets(mkt, &Sm, &Sn1, &Sn2); mktree *leftmkt = (mktree*) malloc(sizeof(mktree)); mkt->leftchild = leftmkt; mktree *rightmkt = (mktree*) malloc(sizeof(mktree)); mkt->rightchild = rightmkt; run = Sn1; UInt32 nobjs = 0; UInt8 band = 0; while (run != NULL && !band) { nobjs++; if (run->rightAABB != NULL) run = run->rightAABB; else band = 1; } BuildMKTree(leftmkt, Sn1, run , nobjs , r, (level - 1)); run = Sn2; nobjs = 0; band = 0; while (run != NULL && !band) { nobjs++; if (run->rightAABB != NULL) run = run->rightAABB; else band = 1; } BuildMKTree(rightmkt, Sn2, run , nobjs , r, (level - 1)); } else { // mktree points to geometry nodes mkt->iniobjects = inigeom; mkt->endobjects = endgeom; mkt->overobjects = 0; mkt->pi0 = 0; 18 mkt->pi1 = 0; mkt->SpDir = -1; mkt->sptree = NULL; mkt->leftchild = NULL; mkt->rightchild = NULL; } } void MinObjOver(AABB *inigeom, AABB *endgeom, AABB *ft, AABB *lt, UInt8 SpDir, UInt8 order, tminOb *minOb) { AABB *run = inigeom; Float32 pi0, pi1; UInt32 nobjs; pi0 = retval(ft, SpDir, MIN); pi1 = retval(lt, SpDir, MAX); run = inigeom; UInt8 alt = 0; while (run != NULL) { if (retval(run, SpDir, MIN) < pi0) if (retval(run, SpDir, MAX) > pi1) { if (alt == 0) { ft = ft->leftAABB; pi0 = retval(ft, SpDir, MIN); alt = 1; } if (alt == 1) { lt = lt->rightAABB; pi1 = retval(lt, SpDir, MAX); alt = 0; } run = inigeom; } else run = run->rightAABB; else run = run->rightAABB; } nobjs = 1; run = ft; while (run != lt) { nobjs++; 19 run = run->rightAABB; } minOb->overobjs[SpDir][order] = nobjs; run = inigeom; nobjs = 0; while (run != ft) { nobjs++; run = run->rightAABB; } minOb->ft[SpDir][order] = nobjs; while (run != lt) { nobjs++; run = run->rightAABB; } minOb->lt[SpDir][order] = nobjs; } splittree *gnSplitTree(AABB *Sm, mktree *mkt) { splittree *s; mktree *spl, *spl_comp; if (intersection(mkt, Sm)) { s = (splittree*) malloc(sizeof(splittree)); spl = (mktree*) malloc(sizeof(mktree)); spl_comp = (mktree*) malloc(sizeof(mktree)); FindBestSplittingOrientedPlane(Sm, mkt, &spl, &spl_comp); s->spdir = spl->SpDir; s->splitval = spl->pi0; s->leftchild = gnSplitTree(Sm, spl); s->rightchild = gnSplitTree(Sm, spl_comp); free(spl->boundbox); free(spl); free(spl_comp->boundbox); free(spl_comp); return s; } return NULL; } 20 B Further examples Figure 5: Ship detail. Top left: scene with r= 0.3, MemP age = 12kb, MKtree level 1 and LOD = 1. Top right: scene with r= 0.2, MemP age = 4.8kb, MKtree level 1 and LOD = 1. Bottom: original scene Figure 6: Texaco oil tanker. Left: scene with r= 0.3, MemP age = 12kb, MKtree level 1 and LOD = 1. Right: scene with r= 0.2, MemP age = 4.8kb, MKtree level 1 and LOD = 1. 21