kd-tree vs oct-tree

This is a discussion on kd-tree vs oct-tree within the Game Programming forums, part of the General Programming Boards category; does anyone know if there is an significant difference in using these structures for scene management? (so the objects stored ...

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    244

    kd-tree vs oct-tree

    does anyone know if there is an significant difference in using these structures for scene management? (so the objects stored in the nodes have bounding boxes, and the nodes of the trees have also boxes (cuboids)

    the thing is, when moving to a child in the oct-tree - it relates to moving to 3 children in the kd-tree.

    but in the kd-tree the nodes can be fitted better to the objects contained in them.

    edit: kd-tree is basically a dual-tree - simlar to quad-tree and oct-tree
    signature under construction

  2. #2
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    the thing is, when moving to a child in the oct-tree - it relates to moving to 3 children in the kd-tree.
    If you look at moving to a node in a kd-tree as if you're moving to that node and all its children, then moving to a node in an oct tree would be, at minium, like moving to 8 children, no?

    They are both solving the same problem, just handling the data in a different way. So with proper abstraction, you should be able to use both systems the same way.

  3. #3
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    >> like moving to 8 children,

    no, its 3 children.
    an octree-node has 8 children.
    a binary tree has, when moving from some node 3 steps down, a total of 2^3=8 children in that level (relative to the node started from).


    >> So with proper abstraction, you should be able to use both systems the same way.

    yes, thats what im doing anyway. i just don't want to have to implement the interface twice though
    (eventually ill do it i guess - but currently i want to continue with the project instead of getting stuck in trying to get like 5% more speed out of it)

    i just wondered if anyone has already messed around with that stuff.

    well, ive now decided to go along with the kd tree.
    (when i used it for my raytracer it worked out pretty well - it could render a 5000 poly object in less than a second (on a 3ghz comp, 512x512)
    signature under construction

  4. #4
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    when moving from some node 3 steps down, a total of 2^3=8 children in that level (relative to the node started from).
    I see what you mean now. With a kd-tree, you'll have more traversal steps. That's not that bad though.

    I hope you come up with a good interface so you can interchange the data structures. I've never actually tried to do that, but the API's I've written were easily adaptable. As long as you hide anything to do with the traversal, you should be ok.

    At times, I've needed to use the traversal path to my advantage. Createing a traversal object that lets you override callback methods works out pretty well, that way you can process the data in anyway you want, and the traversal still happens automagically.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 02:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 06:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21