Skip to main content
gamedev.net
🔒 Locked

Quadtree Question

Started by Christopher Harris 3 replies 500+ views
Original Post
Christopher Harris
Christopher Harris
Hello, everyone. I will be using a quadtree to store my level (triangle-based) and objects in. I was wondering if I should keep a list of what triangles (and/or objects) should be rendered inside each smallest leaf node, or if I should try and fit that triangle, or object, inside the smallest branch node possible. In otherwords, should there be more than one node with a pointer to any given object, or should only one node contain (the smallest possible container) be the only node with a pointer to that object? If none of this makes sense, any quadtree information site related to entity storage would be helpful...
hplus0603
hplus0603
If you just push objects upwards until they fit, any object that sits across a boundary of cells will draw in a much higher level that it has to -- in fact, it may draw at the top layer!

If you say that each node must contain pointers to all objects contained within them, and then put in objects based on object centers, then more than one node needs a pointer to the object.

Instead, Google "loose octrees" and then re-target that theory for quadtrees. The short theory is that, in an octree level where node size is X, you store objects of size (X >= size > X/2), based on center, in a single node. Then, when you query, you actually query an inflated volume for each octree node, where the dimensions for each node (for intersection testing only) are expanded by X/2 in each direction.
enum Bool { True, False, FileNotFound };
Christopher Harris
Christopher Harris
Well, I am glad you mentioned that rendering using a quadtree makes the objects closer to the root get rendered last, and thus on top of everything else. But a simple depth management system should deal with that problem, or perhaps some ZBuffering...

I'm not sure I understood your last statement, but I will do the google.

I think I should now change my question, as I had a new thought.

Should you store dynamic objects in a quadtree? I realize you would need to iterate through the tree and place the object every time it moves, so it might take longer than just testing each object against every other object.
newera
newera
Quote:
Original post by Christopher Harris

Should you store dynamic objects in a quadtree? I realize you would need to iterate through the tree and place the object every time it moves, so it might take longer than just testing each object against every other object.


I have the same question, if someone could possibly help!

Thanks,
Tony
hplus0603
hplus0603
In general, it's reasonable to store dynamic objects in your quad- or octree. The reason is that testing against neighbors is much cheaper (O ln N) which means you avoid the N-squared performance problem.

However, if the number of dynamic objects is small, you can get away with just a simple linked list.
enum Bool { True, False, FileNotFound };

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.