As was previously stated, you need to do research on the Adaptive Binary Tree.
It's a derivation of the classic kD-tree algorithm. It has a well defined heuristic for calculating the optimal splitting plane.
A simple forum search and an hours worth of reading and you'll be an expert. Good luck.
k-d tree compiler, need thoughts
ABT is generally best used in datasets involving many thousands of polygons. I'm not sure that it'd be best for a GBA, perhaps a quake-style BSP might be better.
Note that the people suggesting the use of ABT's have never in their lives implemented such a thing and are really not in a position to comment on their use for this particular problem.
People, throwing buzzwords around doesn't benefit anyone.
People, throwing buzzwords around doesn't benefit anyone.
Quote:Original post by Anonymous Poster
Note that the people suggesting the use of ABT's have never in their lives implemented such a thing and are really not in a position to comment on their use for this particular problem.
Alot of people here (including me) have sucesfuly implemented ABTs, BSPs and alot of other scene-structures. So stop posting as AP and give some usefull anwsers.
The OP didn't mention he was working on GBA engine until the last post so that may change things a bit.
Author
It changes absolutely nothing if it is for the GBA or not, the engine will be software but I still need a structure for partitionning.
BSP are great for some levels, especially the ones where you have a geometry that can help choosing a good splitting plane. That is why in indoor games it is used, because there are many "vertical" polygones representing walls, and by testing all of them in each node you can find the best(linear method) one.
Unlike indoor games, outdoors games are more problematic, you cannot benefit from the geometry for finding spliiting planes. That is why you use quadtree(or octrees). But balancing cannot be achieved especially in levels where the polygones are not equally distributed int he space.
That is why I begun thinking of a more intelligent way of positioning the plane and I found on the net about kd trees. I don't see what is the problem of using them on the GBA, if you are referring to the number of polygones usually contained in the leaves(1000 to 2000 from what I read), you are using these numbers because of the GPU's and to take benefits of vertex buffers(lesser polygones wouldn't be worth).
I'll definitely go to like 200 polygones or less, and a small BSP tree will be in each non convex leaf for Z-sorting.
By the way, couldn't find docs about detecting convex areas so please someone help, at least give me a hint :) (I've searched the forums and posted in the math section).
Cheers, Jeff.
BSP are great for some levels, especially the ones where you have a geometry that can help choosing a good splitting plane. That is why in indoor games it is used, because there are many "vertical" polygones representing walls, and by testing all of them in each node you can find the best(linear method) one.
Unlike indoor games, outdoors games are more problematic, you cannot benefit from the geometry for finding spliiting planes. That is why you use quadtree(or octrees). But balancing cannot be achieved especially in levels where the polygones are not equally distributed int he space.
That is why I begun thinking of a more intelligent way of positioning the plane and I found on the net about kd trees. I don't see what is the problem of using them on the GBA, if you are referring to the number of polygones usually contained in the leaves(1000 to 2000 from what I read), you are using these numbers because of the GPU's and to take benefits of vertex buffers(lesser polygones wouldn't be worth).
I'll definitely go to like 200 polygones or less, and a small BSP tree will be in each non convex leaf for Z-sorting.
By the way, couldn't find docs about detecting convex areas so please someone help, at least give me a hint :) (I've searched the forums and posted in the math section).
Cheers, Jeff.
Quote:Original post by funkeejeffounet
I don't see what is the problem of using them on the GBA, if you are referring to the number of polygones usually contained in the leaves(1000 to 2000 from what I read), you are using these numbers because of the GPU's and to take benefits of vertex buffers(lesser polygones wouldn't be worth).
I'll definitely go to like 200 polygones or less, and a small BSP tree will be in each non convex leaf for Z-sorting.
Yes, I was mainly refering to this. I don't know how many polys GBA/your engine can handle. I'm also not sure how number of triangles versus size of triangles works in your case.
Quote:Original post by funkeejeffounet
By the way, couldn't find docs about detecting convex areas so please someone help, at least give me a hint :) (I've searched the forums and posted in the math section).
Here is one of top of my head for connected meshes, so I don't know if it works. For each edge, calculate angle between triangles that share it (counting winding, so you get angle in range 0-360). If angle is more than 180 degrees then it's not convex. I have no idea how to do it with "loose" triangles.
Quote:Original post by Anonymous Poster
Note that the people suggesting the use of ABT's have never in their lives implemented such a thing and are really not in a position to comment on their use for this particular problem.
People, throwing buzzwords around doesn't benefit anyone.
Well, I'd like to say that I've implemented both ABT and BSP, with quite good results, but that my experience shows ABT to be suboptimal when not being used to accelerate the rendering of large batches (2000+ polygons). BSP is better suited to a renderer based on a c-buffer, as it can give you absolute front-to-back visiblity of all polygons in the scene.
Quote:Original post by AssassinQuote:Original post by Anonymous Poster
Note that the people suggesting the use of ABT's have never in their lives implemented such a thing and are really not in a position to comment on their use for this particular problem.
People, throwing buzzwords around doesn't benefit anyone.
Author
I'm gonna use bsp for the polygon inside the leaves.
But I cannot BSP the whole map, I said why earlier.
If someone has another idea for sorting polys inside the leaves I'm curious about it cause splitting is scaring me here.
Maybe can I stop recursing when only a poly is left in the leaf?
But then what about the depth of the tree?(levels will have approximatively 5000 polygones cause it is a GBA).
Cheers, Jeff.
But I cannot BSP the whole map, I said why earlier.
If someone has another idea for sorting polys inside the leaves I'm curious about it cause splitting is scaring me here.
Maybe can I stop recursing when only a poly is left in the leaf?
But then what about the depth of the tree?(levels will have approximatively 5000 polygones cause it is a GBA).
Cheers, Jeff.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
