   BSP tree - its huge, memory help?
  Hi guys,To get right down to it, I have a very large scene that uses BSP tree for rendering and culling.Im having a problem, which has been recurrent but untill now I have been able to work around. The recursive building of my BSP tree (which seems to be a perfectly suitable structure to continue to use for my collision detection, as well as for rendering and culling) eventually takes up too much memory, I believe I am right in saying I am over-running the maximum allocation for the heap? or perhaps im not - but I do know what if I ctrl+alt+delete and watch the "Mem Usage" for my process when its building the BSP tree, if it goes over approximately 1.25-1.5GB then I will see a crash.This hasn't been a big deal up until now - my BSP tree stops being built when there are hundreds or perhaps low thousands of triangles in a node - its then set to a leaf.So this means my tree is only so deep for now - but I am trying to extend this same tree down to a very fine level, perhaps anywhere from 1-10 polygons in a "collisionLeafNode". You can imagine that this will result in perhaps millions of nodes when I am working with such a large set of triangles. I will have 2 sets of leaves really, one marked as a standard leaf, which is as far as the tree is used for rendering and culling purposes, and then a whole new set of leaves that mark the end of the tree that will be used by collision detection only, so that I can be much more accurate.The problem is, when I try to create a tree that is this massive, I am over-running this 1.5GB mysterious limit and I crash. I thought I had overcome it briefly by splitting up the writing of the file into 2 - write it to a certain level of the tree, save the file, then append more of the tree to this file next time round. This still left me with the problem of reading all the info in, where I am still overunning this memory limit.I thought I might post you some rough code of how my tree is built with hopes you might be able to see some ways of making it more memory effecient - the code is still far from optimised and Im sure there are ways of overcoming my little problem here.All the below code I have cut quite alot out of to make it more readable.First I will quickly show you the BSP class, or just its data members to give you an idea of what is being created with each new node in the tree. The bulk of it is just vectors holding the vertices, texture coord, normal and material information for the triangles in the node.[Source]class BSP_Tree{public:   BSP_Tree *front, *back;   int displayListNum;    static int displayListIncrement;    double coincidentPrecision;    double boundSphereRadius;    Vector3f boundSphereCentre;    double boundBox_minX, boundBox_maxX;    double boundBox_minY, boundBox_maxY;    double boundBox_minZ, boundBox_maxZ;    vector<Vector3f> box_points;    bool leafNode, collisionLeafNode, collisionOnly;    int visibleResultVFC, visibleResultOC;    vector<Vector3f> coincident_list;    vector<Vector3f> leaf_contents;    vector<Vector3f> collision_leaf_contents;    vector<Vector3f> coincident_list_TEX;    vector<Vector3f> leaf_contents_TEX;    vector<Vector3f> coincident_list_NORM;    vector<Vector3f> leaf_contents_NORM;    vector<int> coincident_list_MAT;    vector<int> leaf_contents_MAT;   BSP_Tree();    ~BSP_Tree();    //////////FUNCTIONS}[/Source][/source]Here is the recursive function that builds the tree. It chooses a suitable root polygon from the set passed and uses that polygon to classify all other polygons against a plane formed from the root polygon. We push the proper data to the front, back or coincident list and pass the proper information down to new front or back children, or else we set up a leaf node.After the tree is fuly built, i write all the data to a .dat file, which can then be read in much more quickly to populate the tree at runtime. Basically when I read in, everything in the above class is filled with data, with the exception that in the "collision" part of the tree, on the deeper level than what is used for rendering only, I dont fill any info about texture coords, normals, etc, since it wont be used.The below is much simplified and does not show any dealings with the texture coordinates, normals or material IDs but its all just much the same as dealing with the front_list and back_list.[Source]    void BSP_Tree::Build_BSP_Tree (vector<Vector3f>& totalPolys)    {   int maxPolys = 3000; //gives leaf nodes max of 1k triangles   vector<Vector3f> front_list;   vector<Vector3f> back_list;   int chosenRoot = chooseRoot(totalPolys);   //coincident_list is our root & root coincident polys   coincident_list.push_back(totalPolys[chosenRoot]);   coincident_list.push_back(totalPolys[chosenRoot+1]);   coincident_list.push_back(totalPolys[chosenRoot+2]);  for(int j=0; j< totalPolys.size(); j+=3)//loop for all polys  { if(j!=chosenRoot) //now we wont deal with the chosen root {int result = Classify_Polygon(totalPolys, j, coincident_list, 0); //classify polygon as front, back, coincident or spanning the root-plane switch (result){    case 0://COINCIDENT:   coincident_list.push_back(totalPolys[j]);   coincident_list.push_back(totalPolys[j+1]);   coincident_list.push_back(totalPolys[j+2]);   break;    case 1:// IN_FRONT_OF:   front_list.push_back(totalPolys[j]);   front_list.push_back(totalPolys[j+1]);   front_list.push_back(totalPolys[j+2]);   break;    case 2: // IN_BACK_OF:   back_list.push_back(totalPolys[j]);   back_list.push_back(totalPolys[j+1]);   back_list.push_back(totalPolys[j+2]);   break;    case 3: // SPANNING:   vector<Vector3f>  front_piece, back_piece;   //this splits polygons that are spanning the root-plane, and creates a front and back list of these new split polys.   Split_Polygon (totalPolys, j, front_piece, back_piece,  coincident_list, texCoords, vertNormals);for(int i=0; i< front_piece.size(); i++)  front_list.push_back(front_piece);   for(int i=0; i< back_piece.size(); i++)  back_list.push_back(back_piece);   break;} }  }  if(front_list.size() ==0 && back_list.size() ==0)  { leafNode = true; leaf_contents= coincident_list;  }  if(front_list.size() <= maxPolys  &&  front_list.size() !=0)  { front = new BSP_Tree(); front->leafNode = true; front->leaf_contents= front_list;  }  else if(front_list.size() > maxPolys)  { front = new BSP_Tree(); front->Build_BSP_Tree (front_list);  }  if(back_list.size() <= maxPolys  &&  back_list.size() !=0)  { back = new BSP_Tree(); back->leafNode = true; back->leaf_contents= back_list;  } else if(back_list.size() > maxPolys)  { back = new BSP_Tree(); back->Build_BSP_Tree (back_list);}    }[/Source][/source]Anyway, just thought id ask if anything struck you that was immediately not memory efficient about this that you could spot. Once I can create the tree that is able to split things down until I have a nice small amount of polygons in the collision_leaf_nodes I should have proper accurate collision detection and response up and running shortly, this is just holding me back somewhat.I appreciate I am not making use of pointers at all, which could well help alot, but I was struggling to see how to make proper use of them - I could potentially "pointer things up" alot in the building of the tree, but then when I come to read from the file, I have to read all the information in and store the proper info in each node anyway, so don't see that I can have any of this info as pointers, since its all coming from a .dat file. There might be an obvious solution or maybe not, but thought I would ask in case you had any gems of wisdom!CheersJohn   
Quote:Original post by jswill100Anyway, just thought id ask if anything struck you that was immediately not memory efficient about this that you could spot.The first thing that stands out is that your node class is absolutely huge!  You're using integers and double precision all over the place.  You might want to reconsider what information is absolutely necessary to store at each node and whether or not you could survive with single-precision.  Plus it looks like you might suffer from data duplication issues, since each node stores raw vertices.  If two nodes store the same vertex, then it makes more sense to store the vertex once in a common location and have each node simply index that vertex (similar to how vertex and index buffers work in graphics APIs).   ;  I think i've mentioned this to you before (maybe someone else), don't use spatial partitioning structures (like BSP trees) to try and accelerate collision detection of large static triangle meshes, there generally is no point, typically you don't need a spatial ordering of elements for CD.Instead of using the same BSP-tree for your CD trees at BSP leaves use object partitioning structures i.e bounding volume hierarchies (BVH) they do not suffer from splitting primitives, primitives do not get split with these structures. If use a binary AABB tree your code doesn't even change that much except the partitioning plane must be axis-aligned. Furthermore if you wanted you could make your BVH leaf nodes not contain AABBs around the primitive if intersection tests directly with the primitive isn't expensive.Also you will get better formed trees if you make them seperate for rendering and CD, just using indices to refer to data. I wouldn't bother putting vertex level data in leaves i'd do it on the face level (referencing them either by pointers or indices into face list). If you're wondering where you would then store the vertex data if you where loading in a file then just load up vertex data into plain arrays in your mesh type, builing  up face/index lists and then build your trees.As Zipster mentioned some of those data members could be derived values as opposed to being stored in each leaf.Quote:Original post by Zipster... Plus it looks like you might suffer from data duplication issues, since each node stores raw vertices.  If two nodes store the same vertex, then it makes more sense to store the vertex once in a common location and have each node simply index that vertex (similar to how vertex and index buffers work in graphics APIs).Usually does not happens with a strict spatial partitioning structure, only when you're bending the rules for some good reason.   ;  Thanks, I have indeed set up a AABB bvh for the scene and the memory problem is fixed. cheers!   ;Quote:Original post by snk_kidQuote:Original post by Zipster... Plus it looks like you might suffer from data duplication issues, since each node stores raw vertices.  If two nodes store the same vertex, then it makes more sense to store the vertex once in a common location and have each node simply index that vertex (similar to how vertex and index buffers work in graphics APIs).Usually does not happens with a strict spatial partitioning structure, only when you're bending the rules for some good reason.With BSP trees is usually does happen - as a matter of fact you can't avoid it.  The leafs are simply a collection of tightly packed convex polyhedra.  From that alone we know that every vertex is going to be shared by at least three faces/portals, otherwise you couldn't form a closed leaf.  That number goes up for vertices that are shared by faces/portals across multiple leafs.  It simply isn't possible for a vertex to be referenced just once.   ;Quote:Original post by ZipsterWith BSP trees is usually does happen - as a matter of fact you can't avoid it.  The leafs are simply a collection of tightly packed convex polyhedra.Doesn't necessary have to be closed manifolds, each node represent a decomposition of space into convex regions, each of which are distinct and do not overlap. How could a vertex possibly be referenced by more than one leaf node unless that vertex lies on the partition plane? in which case depending on what you do for this special case depends on whether or not you have duplicates.I'm not saying you're wrong but that is how i understand it.Quote:Original post by Zipster  From that alone we know that every vertex is going to be shared by at least three faces/portals, otherwise you couldn't form a closed leaf.  That number goes up for vertices that are shared by faces/portals across multiple leafs.  You have to be more clear what your saying here because i'm not exactly sure what you're trying to say, if you mean faces straddling partition plane in this case you have divide those faces up. If you can, draw me a picture to help me visualize what you're saying.[Edited by - snk_kid on September 13, 2007 4:37:58 AM]