Advertisement Jump to content


This topic is now archived and is closed to further replies.



This topic is 6857 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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[i]); case right: Count_Right++; realloc(List_Right,Count_Right*sizeof(poly)); List_Right.Add(polys[i]); case coincident: Count_On++; realloc(node->List,Count_On*sizeof(poly)); node->List.Add(polys[i]); case split: polys[i].split(node->Partition); realloc(....); AddSplitPolys to the correct Lists; if(List_Left){ node->children[left]; BuildTree(List_Left,node->children[left]; } free(List_Left); if(List_Right){ node->children[right]; 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.... ) How to avoid this problem. Sorry for the long Post!! Thanks in advance,XBTC!

Share this post

Link to post
Share on other sites
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:


Share this post

Link to post
Share on other sites
Guest Anonymous Poster
Use linked lists

Share this post

Link to post
Share on other sites
Guest Anonymous Poster
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;

Share this post

Link to post
Share on other sites
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 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

Share this post

Link to post
Share on other sites
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;


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

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!