   Offscreen objects, how to know when to draw them...
  So I have a basic quadtree setup, but ive run into a problem with visibility along the edges. The quadtree simplifies things to a level I can work with (60x60 meters), from there I do a 'is this sphere inside the frustum' to rule out individual objects (I recycle objects every frame, starting at 0, and placing them one at a time until the frustum is full, this keeps my object count as low as possible).The problem is, if an object is in a sector that the quadtree considers to be 'out of view', but part of the object (maybe the branches of a tree) are dangling into a sector that IS in view, the object will never make it to the point where it gets a 'sphere check', thus will not be drawn.It seems there are two solutions (maybe more)1.) Redundant placement - ie when writing your 'object position data files', make sure that any objects which overlap from one sector to another are declared in BOTH sectors. This is most efficient as it allows you to keep the frustum nice and tight, but requires you to check every object you place to make sure there isnt a duplicate already there.2.) Use bigger volumes when calculating your quadtree - ie make sure the bounding volumes for your quadtree are big enough to contain all possible objects. This would require you to either add a universal 'worst case scenario' size to all your volumes, OR calculate the 'extra size' needed each sector individually.Either solution doesnt seem elegant enough to me. Both require a lot of extra work/attention, I wish there was another way...Any insight greatly appreciated!   
Quote:Original post by ZealousEngine1.) Redundant placement - ie when writing your 'object position data files', make sure that any objects which overlap from one sector to another are declared in BOTH sectors. This is most efficient as it allows you to keep the frustum nice and tight, but requires you to check every object you place to make sure there isnt a duplicate already there.2.) Use bigger volumes when calculating your quadtree - ie make sure the bounding volumes for your quadtree are big enough to contain all possible objects. This would require you to either add a universal 'worst case scenario' size to all your volumes, OR calculate the 'extra size' needed each sector individually.From what I've seen, each of these methods is fairly common (if you want a term to google for, the latter is often called a 'loose' quadtree or octree). For the former, the duplicate object checking can be done quite easily by keeping track of the current frame number and giving each object a 'frame last drawn' variable (you may have already thought of this).As for which method is better or more efficient, I don't know - I'm guessing it's somewhat context dependent. Intuitively though I'd go for the former. (Note that this is only for static objects; dynamic objects are a different story.)   ;  The key property with any spatial tree is that every child is *completely* contained within it's parent node. If you break that assumption (like you have) then the whole structure becomes basically useless as you can never be sure if you've got everything in a given sections.If you're dealing with static geometry the usual solution is to split it at the boundary, and add the two halves into the appropriate tree nodes. Obviously this isn't practical for moving objects. Other solutions:1. As you've suggested, "redundant placement", or having the objects in both nodes. IMHO while this sounds like a good idea it's a pain to implement - the code to move and maintain the structure becomes considerably more complicated, and if you're not careful you'll end up with objects being left in nodes that they walked away from ages ago!2. A more practical method is to allow objects to be inserted into all nodes, not just the leaf nodes. Then if you can't fit an object into a leaf node (such as when it's too big or straddles a boundary) then you keep pushing it up the tree until you find a node which can completely contain it. This works well and is much easier and cleaner to implement, and you only ever have one reference in the tree to each object.The problem with 2 is that occasionally you can end up with an object right at the top of the tree - if it was dead center of your tree bounds for example. This isn't terrible (everything will still work) but if you're not careful then you can get lots of objects which are actually far away from each other being at the same node.As a counter to this you can use a loose tree (expanding the nodes so they overlap somewhat, making it less likely to push objects up the tree) and by choosing the leaf size such that most objects can fit within them easily.   ;  Although redundant placement is certainly a pain for dynamic objects, it sounds to me as though the OP is talking about static objects (the term "data files" is suspicious). You could place objects without bothering about duplicates already present (I'm slightly at a loss as to why there would be any though), and then prune any excessive duplicates from the tree (a post-op, if you will) before saving to file.   ;  Well after a lot of thought Ive decided to go with a 'loose quad tree' solution. So ill just have to make sure all my nodes are x units bigger than they really are (x will be based on the worst case scenario largest object).And when I say data files, i just mean object placement data (where trees are, ect). They start out as files on disk, and are loaded into memory for faster access as you move to different areas.   ;  double post   