Jump to content
  • Advertisement
Sign in to follow this  

Sorting Texture in a BSP tree

This topic is 4722 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

Just curious, how do you know which texture to use for which node in a bsp tree? For example a simple skybox have 6 different texture from 6 different file. After creating the bsp tree, how do i know which node/polygon correspond to which texture? How do i know which texture load when i render each node? My method now is to use a editor (photoshop) to combine the 6 different texture into a single file. But it will not work for scene which many texture as the combine file will be bigger than 2000x2000 pixel A small question: Are BSP still the way to go for scene management or are the other methods like scenegraph, octree becoming the more popular?

Share this post


Link to post
Share on other sites
Advertisement
a node will only contain a plane that cuts the world into 2 halves. The leafs of a BSP tree will store the actual polygon data(although BSP tree's are imho nowadays only helpful for collision detection). If you store for each face it's textureID you can quick sort that out. as for sky boxes if a leaf contains a 'sky face' just render a skybox first and then the actual geometry.

But what is your question excactly?

Share this post


Link to post
Share on other sites
what i mean is for example at the start i have 30 polygon with 6 texture

(polygon 1-5 -> 1st texture, polygon 6-10 -> 2nd texture and so on).

After creating the tree, the polgons get seperated from the textureing order.

(For exampe, polygon 1-3 in a leaf and 4-5 in another leaf, some polygon may be splt like poly 6-7a in a leaf and 7b-10 in another)

My problem is how to keep track of which texture to load for a leaf when i draw the bsp, since some leaf may need to load more than 1 texture

(e.g. poly 1-3 and poly 6-8 may end up in a same leaf which means i need to load and change 2 texture when i draw)

However when i draw i don't know which texture to load as i completely lost track of which texture is for which polygon.

(The bsp is sorted using the indices as i thought using vertex would create to many duplicates is it the correct method?)

Share this post


Link to post
Share on other sites
BSPs arn't just for colision detection, think about alpha blending, you have a complex alpha blended object, you need to sort it's polygons back to front. also, drawing front to back makes non-alpha blended stuff faster.

and to answere the question, just make some sort of reference/handle/other-identifier into the polygon structure/class you are useing for the texture that should be used. but it's much better if each BSP tree uses only one texture.

scene management diferes a lot based on what you plan on doing. BSPs are a great way to store geometry of submodels (if they are all useing the same matrix set (i.e. no skelital deformation)) but I generaly would avoid it in situations were the nodes are apt to change a lot, like scene management.

[edit]you posted while I did, makeing relivent post now[/edit]

Share this post


Link to post
Share on other sites
figure out how many textures may be used for a single BSP rendering (or easier and faster, but less elequent solution make up some max number and just make a static array) then make that many index buffers and when you add a polygon from your BSP just send it to the index buffer coresponding to the texture, then after sorting the index buffers with the BSP you draw them one at a time with the texture assigned to the index buffer.

understanding better how you have things organised might help a little, how are you useing the BSP tree right now? is it sorting whole objects or just the geometry of an object? how are you manageing texture in this opperation?
the way I have things set up in my BSPs is generaly any BSP tree can have no more than some hard coded number of textures (well materials actualy, but it's the same concept), and I have that many index buffers, each polygon in the BPS references the texture on a per instance basis (they don't reference a global texture but the Nth one loaded with the model). so the setup goes

render_object{
sort index_buffers()
set vertex buffer()
draw with resorted index buffers()
}

if you make the index buffers persistant on a per object basis (but all objects of a type shareing the same vertex buffers) then you can sort every few seconds rather than every frame, giveing you all the benifits of a BSP sorted geometry while drasticly reduceing the cost of locking one or more index buffers over and over again.

Share this post


Link to post
Share on other sites
I have no way of rendering a texture now with my current bsp

Here is how i bulid my bsp

For example i have a bsp tree:

#### N1
# - / # \ +
## / ## 7
# N2 ## 8
#/ \ ## 9
/ # \
1 # 2
3 # 5
4 # 6
[Thoes # are just to make the bsp have a shape because it cannot display multiple spaces]

Then i will tranverse down the tree from the head check the plane in N1 see if the eye is behind or infront the plane, if infront then down the positive branch first. Store 7,8,9 in to a index buffer, then tranverse down the other branch to N2 check the eye and the plane of N2 then push back the index at the leaf into the index buffer.

Therefore
Go N1 -> check eye and plane -> + branch -> push 7,8,9 into IndexBuffer
Go N2 -> check eye and plane -> + branch -> push 2,5,6 into IndexBuffer
Go -> - branch -> push 1,3,4 into IndexBuffer

So the Indexbuffer will be 7,8,9,2,5,6,1,3,4 after tranversing the tree and then I will draw using this index buffer.

BSP_NODE
{
D3DXPLANE dividing_plane
bool IsLeaf //true if this is a leaf
vector<WORD> index //store the list of index at the leaf
BSP_NODE* Front, Back
}

Pre Game Loop Build BSP
{
1. Sort the object into a bsp tree using the index of the mesh
2. Create the vertex buffer, Create the index buffer base on the max number of index needed
using DYNAMIC_USAGE
}
Game Loop
{
1. Tranverse the bsp and push into a (Global)vector<WORD>index_list.
2. IndexBuffer->Lock(), memcopy from the vector<WORD> index_list, Unlock().
3. Render
}

Where do i store the texture info? Should i change my BSP bulid or is this good enough?

Share this post


Link to post
Share on other sites
allright, BSP_NODE is were all your geometry is stored, you need to store some sort of reference to a texture in this. are you useing some sort of texture management or are you just useing raw ID3DTexture pointers everyware? (BTW I'd recomend not useing stl vector<> in this application, it's slow at everything but this is irrelevent to this topic)

assumeing that the scope of your BSP is the geometry of one object, and you know ahead of time how many textures the object is going to have. you need to change
(Global)vector<WORD>index_list
to
(Global)vector<WORD>index_list[MAX_OBJECT_TEXTURES]

and have a paralel array (or make single array of a structure to hold both data) of what ever you are useing to identify textures. then in your BSP_NODE add an int identifying wich texture of the model that node uses, then you simply go
index_list[BSP_NODE.texture_id].pushback(BSP_NODE.index)

then after you get done running through the BSP tree you go

set_v_buffer()
for(i; number of textures){
set_texture(texture)//an array of what ever you are useing to identify textures parralel with index_list
set_index_buffer(index_list)//locking and all that
draw()
}

I could probly make a better answer if I knew how you were handeling textures overall, when you load a model, what do you do with the textures? how do you ever know what textures are suposed to go with wich poly?

but basicly, all you need to do is to have your BSP interpeter act on multable index lists at the same time, rather than just one.

Share this post


Link to post
Share on other sites
Quote:
Original post by Bobboau
(BTW I'd recomend not useing stl vector<> in this application, it's slow at everything but this is irrelevent to this topic)


Just wondering what do you suggest i use instead of vectors<> ? Do i write my own stack or link list?

Share this post


Link to post
Share on other sites
std::list is the stl-equalence of a linked list. if you do insertion-heavy stuff, i'd prefer a std::list.

Share this post


Link to post
Share on other sites
Quote:
Original post by littlekid
what i mean is for example at the start i have 30 polygon with 6 texture

(polygon 1-5 -> 1st texture, polygon 6-10 -> 2nd texture and so on).

After creating the tree, the polgons get seperated from the textureing order.

(For exampe, polygon 1-3 in a leaf and 4-5 in another leaf, some polygon may be splt like poly 6-7a in a leaf and 7b-10 in another)

My problem is how to keep track of which texture to load for a leaf when i draw the bsp, since some leaf may need to load more than 1 texture

(e.g. poly 1-3 and poly 6-8 may end up in a same leaf which means i need to load and change 2 texture when i draw)

However when i draw i don't know which texture to load as i completely lost track of which texture is for which polygon.

(The bsp is sorted using the indices as i thought using vertex would create to many duplicates is it the correct method?)



if you have found out your leafs, you can determine what leafs are connected to eachother, and thus sorting out whenever a texture change state occurs( if you pre-sort them in the compile progress ) and store indices whenever a texture change occured. this way you won't have to bind textures again, coz they are still bound. (but if you're going to have lightmaps also a check should be made if the lightmap texture is changed )

My old renderFace function was as follows

void renderFace(int faceIndex)
{
BSPFace face = faces[faceIndex];
//face.texID is an index to a global texture array
if( face.texID != oldTexID )
{
//bind new texture
oldTexID = face.texID;
}
//
render face along with it's properties

}









@ Bobboau i know BSP tree's aren't only used for Collisions, but my findings are they are usefull for testing the potential polygons( in case of a bsp tree not a lot of them ). The rendering should! be seperated from the BSP tree, unless it is software based.



Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!