Having read up on all varying types of bsp trees used in games, and tried to implement a couple in different ways, I keep coming across the same sort of problem, that never seems to even get mentioned in the articles. The problem is that when building the tree, I often get stack overflows due to the (recursive) process not terminating. The trees I''m trying to make are to subdivide an individual object/model, and so it is polygons/triangles that I''m sorting. With the sort of tree where the splitting plane is chosen as one of the polygon planes, and polygons are only ever stored at nodes where they lie in the splitting plane, the problem arises from creating more new polygons from splitting than I''m storing at the nodes, so the build process never finishes. I''ve gotten round this somewhat by testing various splitting planes based on balance/no. of polys split, but it seems that this isn''t robust enough - I''ll always be able to find an object that building a tree for still causes stack overflow - so I''m wondering if theres a better way to deal with this. I''ve also tried trees where the splitting planes are in line with the x,y,z axes, and polys are stored at leaf nodes once the number of polys falls below some threshold. Here, if a poly spanned a plane, I just added it to both child nodes without splitting, since this is for ray-tracing and I read that there is no need to split polys in this case. This causes the same problem as before though. I have to set the threshold much higher than I''d like, and still some models give overflow/non-termination. One final thing, just a thought really, is that maybe bsp trees, at least the first kind I mentioned, aren''t any good for subdividing models anyway. I thought this because one model I was using for testing was a triangulated sphere. I realised that no matter what triangle I chose as a splitting plane, it would always result in a totally unbalanced tree, since all other triangles would be on one side of the plane only. Obviously the sphere is the worst case, but I think lots of models are similar in that the polygons are all on the surface of the model, which is often quite concave (does that make any sense?), and so you would generally get fairly unbalanced trees. I dont know. Anyway, any help or thoughts would be cool. cheers, Cameron

if i understand what you wrote..
try having a threshold value or percentage
that the triangle has to meet in addition
to the crossing of the plane before you
split it. if all you are checking is the crossing
of the plane then you could possibly be splitting
a triangle forever due to floating point
inprecision, cause youll lose a bit or two with
every divide or multiply.

on the side...
what are you trying to accomplish by using the tree?

thanks for the reply.

if by a threshold value you mean some sort of epsilon to make sure that the triangle definitely crosses the plane, then I already am doing that.

as for the use of the tree. that particular tree is to subdivide a very complex model to try to accelerate the intersection of a ray with the model. so far, it''s resulted in an average of about a 5x speed up of the process over just doing a ray-triangle intersection test of every triangle in the model. I dont know if this is as good as I could expect, but I''d think not since I''ve not been able to generate a well balanced tree without the stack overflow problem.

I might have thought that this was an inherent problem with bsp trees but for the fact that no article seems to mention it as a problem. To me it makes sense that, since each subsequent node represents a smaller region of space, that if your tree construction doesn''t stop after relatively few recursions then you''re inevitably going to create more new triangles from splitting than you''re going to use up in nodes, and so the process goes on forever. It also seems that using very detailed models (15 - 50 000 triangles) would make this more likely. Maybe i''m just talking rubbish though.

cheers
Cameron

ok, using the tree makes sense to me now..it didnt before.
is this for a ray tracer by chance or a collision system?

what about not spliting the triangles at all?
if a triangle crosses your plane place a reference
to that particular triangle on both sides
of the tree. bingo problem solved.

have a flag associated with triangle telling you
whether or not its been drawn or is currently being
drawn (if this is for a collision system then you
dont need a flag..then again you may depending on what you do
with them once youve collided with it). so if
your using references if you need to check the other
side of the grid as well than you can skip the flagged
polys.

ok, thanks

yeh, it is for a sort of ray-tracing, basically I need to do nothing more than find the first intersection point between a ray and the object. I''ll try what you said.

cheers
Cameron