Jump to content
  • Advertisement

Archived

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

mitchw

Building a BSP Tree - Stack Overflow and Recursion

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

Howdy, I''ve got my Leaf based bsp building and rendering. Problem is on large maps, I am running into stack overflow because of recursion issues, I am recursing too deep with the nodes. Pseudo code is pretty vanilla for bsps, I believe: buildnode ( CNode* pNode ) { findsplitter() // which does convex polygon set test if ( !splitter ) leaf else sort polys to front and back buildnode( pNode->front ) buildnode( pNode->back ) } Any general tips on how to work around this limitation? I am passing pointers or references for any complex data types. Thx.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
I''ve built a bsp engine from the ground up including a bsp compiler and ran into this a few times. Every time, however, it was just a mistake I made in my code so that the base case wasn''t being reached when it was supposed to. You have to do a LOT of recursions before you run out of stack space, expecially if your just passing 1 pointer to the function. Do you have a csg phase in your compiler? I ran into a problem were having 2 brushes (or whatever you call them) overlap and would cause infinite recursion when trying to split. Using csg to make sure that any point was contained in no more than 1 brush. You can check out my source at http://www.thepeel.com/void.
JS

Share this post


Link to post
Share on other sites
Thx for the tips, I''ll check out your compiler, see if I see anything glaring I am doing wrong. It looks like it is a bug (heh), probably not detecting a leaf when I should. I keep a static recurse count now, and when I am overflowing, the recurse count is 4500+, even on a small map. I am also trying to figure out what geometry is failing.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Ahh. Blame it on FP errors. My face splitter didn''t have a precise enough EPSILON, and I was getting some WACKY faces created. The face that would be created would have an extreme vertex somewhere, and then it would try to use that face as a splitter, with nothing to split

Seems fixed now

Thx!

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

GameDev.net 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!