Bsp-Questions!
Author
I have little question on the building process of a node based Bsp which looks like the following(maybe there are some errors in it,but that doesn´t matter,it just a example):
BuildTree(Polygons *polys,node *node){
node->Partition=GetBestSplitter(polys);
for(int i=0;i<=Max_polys;i++){
result=polys.Classify(node->Partition);
switch(result){
case left:
Count_Left++;
realloc(List_Left,Count_Left*sizeof(poly));
List_Left.Add(polys);
case right:
Count_Right++;
realloc(List_Right,Count_Right*sizeof(poly));
List_Right.Add(polys);
case coincident:
Count_On++;
realloc(node->List,Count_On*sizeof(poly));
node->List.Add(polys);
case split:
polys.split(node->Partition);
realloc(….);
AddSplitPolys to the correct Lists;
if(List_Left){
node->children[left]=node.new();
BuildTree(List_Left,node->children[left];
}
free(List_Left);
if(List_Right){
node->children[right]=node.new();
BuildTree(List_Right,node->children[right];
}
free(List_Right);
}
This is the pseudo code of my actual Bsp-Builder,BUT I have a problem with it:
It wastes tons of memory:
Example:
If I put 1000 Polys into the builder,it allocates memory(for the Left and Right Lists) for 1000 Polys(PLUS the ones which
result from the splitting process).
The next step:If all polys are left of the Part.-Plane again memory for about 1000 Polys would be allocated.
->Because the function is recursive,a huge amount of memory is allocated until the programm comes back to the points
where the program frees the memory.
The Result:The Building Process of a 2000Poly Scene needs a Maximum of about 250MB!! of Memory,but the
resulting tree has a size of about 10MB.
Is this need of memory common for a Bsp-Builder??(I don´t think so….<img src="smile.gif" width=15 height=15 align=middle> )
How to avoid this problem.
Sorry for the long Post!!
Thanks in advance,XBTC!
</i>
Why do you allocate memory for the whole polygons??
If you store only the indices in the lists the problem should become much smaller. With 2000 polygons you have max. 2000 lists and you have to list max. 2001000 polygons. With unsigned int indices you need ca. 4M.
Visit our homepage: www.rarebyte.de.st
GA
If you store only the indices in the lists the problem should become much smaller. With 2000 polygons you have max. 2000 lists and you have to list max. 2001000 polygons. With unsigned int indices you need ca. 4M.
Visit our homepage: www.rarebyte.de.st
GA
You usually have a link list of all of the polygons in the world. Then you just put the pointers to those polygons in each node. You can make a bsp list with no allocations needed at the time of building.
struct node
{
struct node left, right;
polylist* list;
};
struct node
{
struct node left, right;
polylist* list;
};
Author
Thanx!
But:
Do you mean I should throw all my polygons in a linked list,and have an array of pointers to ALL polygons?
Or do you mean I should have a linked list at each node ,which consists of ALL polys?
Or do you mean I should have a pointer list at every node which only consists of the polys which are coplanar with the node´s splitter?(Thats what i´m doing now)
But all these ideas don´t work,´cause at building I have to sort the polys into a left and into a right list,these lists have to be allocated every time BuildTree....is called or the app crashes,even if I use linked lists for the left and right lists the need the same amount of memory.
Or am I wrong?
Please help!!
Edited by - XBTC on 4/14/00 10:12:22 AM
But:
Do you mean I should throw all my polygons in a linked list,and have an array of pointers to ALL polygons?
Or do you mean I should have a linked list at each node ,which consists of ALL polys?
Or do you mean I should have a pointer list at every node which only consists of the polys which are coplanar with the node´s splitter?(Thats what i´m doing now)
But all these ideas don´t work,´cause at building I have to sort the polys into a left and into a right list,these lists have to be allocated every time BuildTree....is called or the app crashes,even if I use linked lists for the left and right lists the need the same amount of memory.
Or am I wrong?
Please help!!
Edited by - XBTC on 4/14/00 10:12:22 AM
I usually organise my data like this (for BSP)
CPolygon Polygons[2000];
struct Node {
Node left;
Node right;
int *PolyPointer;
} SomeNode;
this might not be right, I''m adapting my bone and skinning source code for this.
All you have to do is create an array of polygons, and then use their index (Polygons[INDEX]) to access their data. Remember to use Polygon[SomeNode.PolyPointer] to access the information of the polygon.
if you want to optimise your data even futher, have the polygon structure like this:
struct CVertex {
float X, Y, Z;
};
struct CPolygon {
int Vert1, Vert2, Vert3;
};
then....
CVertex Vertex[3];
CPolygon Polygon;
Polygon.X = 0;
Polygon.Y = 1;
Polygon.Z = 2;
0, 1, 2 are the number of the verticies in the array. this means more than 1 triangle can share the same vertex
CPolygon Polygons[2000];
struct Node {
Node left;
Node right;
int *PolyPointer;
} SomeNode;
this might not be right, I''m adapting my bone and skinning source code for this.
All you have to do is create an array of polygons, and then use their index (Polygons[INDEX]) to access their data. Remember to use Polygon[SomeNode.PolyPointer] to access the information of the polygon.
if you want to optimise your data even futher, have the polygon structure like this:
struct CVertex {
float X, Y, Z;
};
struct CPolygon {
int Vert1, Vert2, Vert3;
};
then....
CVertex Vertex[3];
CPolygon Polygon;
Polygon.X = 0;
Polygon.Y = 1;
Polygon.Z = 2;
0, 1, 2 are the number of the verticies in the array. this means more than 1 triangle can share the same vertex
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
