Jump to content

  • Log In with Google      Sign In   
  • Create Account


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 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