Skip to main content
gamedev.net
🔒 Locked

BPS Tree's

Started by outRider 6 replies 300+ views
Original Post
outRider
outRider
I''ve tried to look up some stuff on BSP''s but I must admit I''m having some trouble understanding them... particularly how to handle textures and such. This is the basic data structure I have so far... (listed backwards just to make it easier to understand) typedef struct tagBSPobject { BSPNODE *Root; short VertexCount; VERTEX *Vertex; short NormalCount; NORMAL *Normal; BYTE MaterialCount; MATERIAL *Material; } BSPobject; // The vertex, normal, and material stuff are the actual vertices, materials, and normals. The triangle type is where the faces are and they have indices that point to the vertices, materials, and normals here typedef struct tagBSPNODE { TRIANGLE *Divider; TRIANGLE *List; BSPNODE *Front; BSPNODE *Back; } BSPNODE; typedef struct tagCOLORMATERIAL { float r, b, g, a; } COLORMATERIAL; typedef struct tagMATERIAL { COLORMATERIAL Ambient, Diffuse, Emissive, Specular; float Shininess; float Transparancy; unsigned int TextureID; unsigned int LightmapID; } MATERIAL; typedef struct tagVERTEX { float x, y, z; float u , v; } VERTEX; typedef struct tagNORMAL { float x, y, z; } NORMAL; typedef struct tagTRIANLGE { short v1, v2, v3; short n1, n2, n3; } TRIANGLE; Now, the way I understand it is that the BSP nodes have the face information, and each node only has the face whose plane is used to divide the other faces, and therefore it would also be drawn. where a node doesn''t have a divider it becomes a leaf and it has more than one face in the list and all those are drawn. But how would I handle textures? My models all have seperate meshes, each mesh has a material assigned to it, each material having a texture and a lightmap... It doesn''t make sense to have a different tree for each mesh, but then I have no idea what to do with textures if everything is thrown together in one tree... I''d appreciate any suggestions anyone might have. ------------ - outRider -
andy maddison
andy maddison
The basic idea of a bsp tree is to subdivide space using planes which are stored in the nodes. Each node contains a plane which divides the space defined by nodes above it. So the root node contains a plane which divides R3 space into 2 half-spaces. The nodes below the root divide their particular half-spaces into 2 half-spaces. And so on. The planes used to carve up the space are usually taken from the triangles in the scene. To find the plane for a node, you might use some kind of heuristic, such as choosing a plane which will cause the least splits, or maybe giving the most balanced tree.

Starting at the root, you would test all your triangles against the root''s plane. Any triangles which lie on the plane can be stored in a list in the root. Triangles which do not span the plane can be sent down to the left or right child node depending on which side of the plane they lie. Triangles which span the plane can be split into multiple triangles which do not span the plane. These can be sent to the relevant child. Each child will have a list of triangles with which to recurse the process.

When a node cannot send any triangles further down the tree, it is known as a leaf node and the recursion stops.

Perhaps you can just store indices into some big triangle list in the nodes, instead of triangles?

Just so you know, there is also another method for bsp trees in which all triangles are stored at the leaf nodes, but the splitting planes are still stored in the other nodes.
XBTC
XBTC
Some hints:
Never store concrete Faces in the tree or make your faces\mesh-structures dependant on the tree structures.Just seperate it completely.Code a back end that can simply render your face-structures in the most efficient way.In the leafs just store indices to the faces.When you traverse the tree mark the faces which are visible as visible and if you have traversed the whole tree, render those faces which were marked as visible.Now your tree has nothing todo with texturing, ....anymore.How you render your faces + with texture is no question of the tree now.

HTH, XBTC!

Edited by - XBTC on November 26, 2000 7:47:03 AM
andy maddison
andy maddison
If you take XBTC''s advice and mark visible faces I would suggest that you don''t use a simple visible/invisible flag, but instead use some kind of counter.

Using a flag means that you''ve got to reset every flag on every frame. If you keep some kind of counter, e.g. the current frame number, then you can just mark visible faces with this number. At render time, you ignore any faces with an older frame number. This removes the need to reset every flag.
XBTC
XBTC
>If you take XBTC''s advice and mark visible faces I would suggest that you don''t use a simple visible/invisible flag, but instead use some kind of counter.<

Isn´t that obvious?

Greets, XBTC!

andy maddison
andy maddison
Hey XBTC, maybe it''s obvious to you, but that doesn''t mean it''s not helpful for someone. Just remember, everyone is not as smart, knowledgeable and experienced as you, and these sorts of little tips are useful to some people. It wasn''t obvious to me either, until I read about it a couple of years ago. But hey, I guess I''m not as smart as you either. If what I wrote helps only 1 person then that''s better than none at all.

These forums are here to help people of all abilities, not just the boffins like you. So please refrain from writing such comments in the future.
mitchw
mitchw
Dude, chill out.
XBTC
XBTC
>Hey XBTC, maybe it''s obvious to you, but that doesn''t mean it''s not helpful for someone. Just remember, everyone is not as smart, knowledgeable and experienced as you, and these sorts of little tips are useful to some people. It wasn''t obvious to me either, until I read about it a couple of years ago. But hey, I guess I''m not as smart as you either. If what I wrote helps only 1 person then that''s better than none at all.

These forums are here to help people of all abilities, not just the boffins like you. So please refrain from writing such comments in the future.<

Hey!It was just a stupid joke....Don´t you now what this: means?

Sorry if somebody got it wrong....

Greets, XBTC!

P.s.:I know how annoying those people you described are but I myself surely don´t count to those....Read some other answers from me and you´ll see that this was just a mistake....


Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.