Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!

1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Member Since 16 Jul 2001
Offline Last Active Oct 19 2009 12:09 PM

#295870 How long should a KD tree take to get built

Posted by Caesar on 21 January 2005 - 05:13 AM

Hi, I'm dealing with some issues in my kd-tree code. I'm using space median as of now and I want it working before I go to RSA. What I'm quite worried about is the time it takes for the tree to get built. I have 256 faces (it's the classic teapot) and the termination cirteria are 1 node/primitive or depth > 15. This works fine, but once I try depth > 18 or even higher, the time required to build the tree grow exponentially (I'd say this should't really happen, since there have to be lots of leaf voxels already by depth = 3-6 or so (i get 41 seconds for depth = 20). 1) does it make sence to have trees of such depth? 2) my code in NOT optimalised, it takes the initial BB, iterates all primitives and checks (BB vs BB) if they're inside, then splits (cycles thru x,y,z) in two halves, checks all parent primitives and assigns them to the respecitve halves etc. No cache optimalizations or SSE or scheduling or whatsoever. Are those reasonable times (what are your times for comparable scenes) that I'm getting? Or shall I look for some ugly bugs in my code? thanks you all