I'm trying to create a quad tree for my 3D environment (all elements are on a flat terrain, so they can be represented with 2D data), but I'm a little lost on the implementation of the finer parts of it.
I will first begin by describing my current quad tree, than move on to its flaws, and than ask the questions.
What I currently have is a quad tree that takes in a very specific rectangle in which I define the x,z,width, and forward. Here is an overview of my operations.
Insert an object into the quadtree:
Check if the current node has any child. If it does, check if the object is able to completely fit into any of the four nodes. If Possible, recurse and repeat. If the object does not completely fit into the four nodes or there are no nodes at all, it will add it to a std vector, than check if it should split. If it splits, split it and split the current objects into their respective nodes.
Delete an object from the quadtree:
Check if the object is inside the current node. Than move onto children. If found, pop the object out of the vector.
Update the quadtree:
Moving and static objects are stored in different quad trees. Moving quad tree will always delete whatever has moved and reinsert. Static quad tree just chills.
Retrieving an object
First find which of the four nodes it belongs to, than move recursively, taking all of the node's current objects and adding it to a vector that is returned at the end.
So here are my flaws: Not all of my rects are located in the leaf. I have no idea what I should do with those that intersect between the nodes. This also makes collision detection checking kinda stupid in a quad tree; why do I need to put rects inside parent nodes? I am thoroughly unhappy about the Retrieve object function.
My second flaw is that I can only take a rect in. While this was useful in making the quad tree and debugging it, I would like to move on and be able to directly put my Objects in my game inside.
So here are my questions I've read Quadtree for 2D collision detection. Everything seems good enough, until "Objects can belong to several collections inside the quadtree. You're going to need an extra linear collection outside the quadtree to enumerate every object without duplicates."
I have no idea what that means, or how to do that. The operations for collision detection also seems much better than what I currently have. I want to know what he means and how its done.
My second question is regarding the insertion of objects into the tree. All my objects in the game would be part of a base class. Should I just make them add the base class directly? Or should I cast the objects into rects and than add a pointer to the object? I am loading some models for my game as well, and they are stretched around and played with by glScalef(). Thus it seems really hard (but possible) to get the scaling of and the position of the models after scaling.
On a side note, the main reason I am scaling the models is because I am basically making walls for a maze game. So I need them to fit perfectly around, and I can't mathematics on maya.
