Update: Wow..Thank God the new kdtree code works =)… happy with it also! Collision detection and response can be such a tough topic as it needs to relate to the whole engine also.. I love working on it but it really can be tough.. this time not so tough =)..I could still and need to still introduce some optimizing =) (Mainly just tree balancing) I will get to that later … first make game happen. Video of the current progress incoming =)
BTW Skyrim is THE BEST RPG EVER!… BY FAR….. Even better then system shock 2 =)… Wow..
————————————————————————–
Can’t sleep and was thinking about the oct-tree vs bvh vs kd-tree. I still love KD-Trees and their simplicity. I think I will stick with what I had with a minor alteration. What I was doing before was when I removed a node I would also trash all its children. I was also not laying in the children totally correctly with overlap issues. So what I will do, is when I place a node in I will follow this:
3 types of structures:
1.
KD_Tree_Node:
–Splitting axis
–Splitting point
–Collision node (can be null)
–Positive Child
–Negative Child
KD_Tree_ParentPtr_List
–KD_Tree_Node
–Link List Ptr Next
3.
Collision node:
–SceneGraphModelPtr used for world min max calculations
–pointer to models world min for speed
–pointer to models world max for speed
–pointer to models world center for speed
–Link List of KD_Tree_ParentPtr_List to all parents of this node.
_On_addition_:
1. Is this nodes collision model empty?
–Yes =
—-A. Place it here as the KD_Tree_Node Collision Node
—-B. The collision model adds a parent to its link list of parents.
—-C. Done traversing this recursion as any node passing by will have to test this collision.
–No =
—-A. If it is on the positive side pass it down to the next negative node
—— GOTO pass_down_code
—-B. If it is on the negative side pass it down to the next negative node
—— GOTO pass_down_code
—-C. If it is on both sides pass it down both sides of the axis
—— GOTO _pass_down_code_ for both positive and negative
_pass_down_code_:
–If this child is null
—-YES create a new KD_Tree_Node with the correct new rotated splitting axis and its point -bias from the minimum point axis. Then follow _On_addition_(1.Yes)
—-NO child is NOT node null go back to _On_Addition_ above and recurse
Anytime a Collision node moves or is deleted:
_On_Removal_:
–1. run through link list of parents and null out their KD_TreeNode->CollisionNode
–2. return all parents link list pointers to the parent pool of empty link list pointers.
–3. Goto _On_Addition_
There all out of my head now maybe I can sleep… =)…
This removes the issue I was having of the nodes really getting into some nasty loops as child after child had to be reprocessed on moving or deleting. This method might make a pretty large tree as nodes never go away but the level of recursion should only get so deep. Along with that I could and need to add a code block that in the future (When I am streaming a level and not just loading one) I can reprocess (balance) the tree. This would occur by gathering all the collision nodes in the tree. Then clearing the tree. Then reinserting them from a shuffled or spatially separated list. Anywho I should get some more sleep I was hoping on another workout this morning.. in a few hours..
