Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Okay so i've spent a few days learning what a quadtree is and how to implement one. So far I have a quadtree that when I click inside a leaf it subdivides, I wondering how do I get the previous subdivisions to collapse back up, so that only one area is subdivided at a time?

This is what mine looks like: (1. initial mouse click) (2. another mouse click)

enter image description here

The aim to to eventually track the position of my mouse and subdivide the area it is in dynamically.

THE OVERALL aim it to use this to create a terrain mesh and subdivide based on the camera. But I've gone right back to basics to get an understanding of how this will work.

Any advice would be grand! - Caius

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Terminology first: I refer to quadtree quads as "nodes" within the quadtree structure, and I refer to flat array elements as "cells".

Every individual quad, at each subdivision depth, should have it's own wireframe view component. You should also have a flat 2D array that represents all of the quadtree leaf (i.e. deepest level) nodes in your entire root node. We'll call this a presence array. Basically this array shows us which cells have objects in them. You should have one such array for the last frame/update, and one for the new frame. At the start of every frame/update, determine deltas from the presence arrays by comparing their cells at each respective [x, y] location, and recording any differences into lists as follows:

  1. enteredInto holds corresponding leaf nodes for any cells that changed from not present in last array -> present in new array.
  2. departedFrom holds corresponding leaf nodes for any cells that changed from present in last array -> not present in new array.

I would keep each of these as List<T>.

These sets can each hold multiple entries because your object may be sitting over an intersection of four (or more) leaf cells, and because the object may be larger than a single cell.

Using these sets, you can flag each leaf node with a boolean to either render or not in the current frame/update. As soon as a leaf node is turned on for rendering, all of its ancestors must be automatically turned on for rendering, as well, right up to the root. I would implement this in a setter method, such that as soon as you set any lower level node, it walks up its ancestor list, setting flags all the way to the root. Be sure to switch off "just departed" cells before switching on "just entered" cells.

share|improve this answer
    
Just to clarify, the "leaf" nodes, are the same as "child" nodes? –  Caius Eugene Dec 6 '12 at 15:55
1  
@CaiusEugene "Child" nodes can mean child nodes at any depth down to the deepest, i.e. any node that is the child of some other node, at any depth. "Leaf" nodes mean something more specific: You have a maximum number of depths in your quadtree, correct? Well if you have n depths, and root is at depth 0, then leaf nodes are the nodes at depth n-1 -- the deepest depth possible. –  Nick Wiggill Dec 6 '12 at 15:57
1  
Perfect! Thank you for clearing that up, I've been reading so many papers and not understanding correctly. Also: "determining the delta" (in layman's terms, is that working out if the "mouse pointer", or point, is within the bounding box of that node)? –  Caius Eugene Dec 6 '12 at 16:01
    
@CaiusEugene Yes. You should separate your problem from the mouse, which is just an input method. What's important is what the mouse is moving. This is either a point, or a polygon. If it's a point, then your delta sets will be very simple: departed set will be the cell the mouse was in last update, and entered set will be the cell the mouse has entered this frame. However if you used more realistic physics with a polygon object, eg. a large car object moving and rotating by gradual velocities, each set would then contain multiple entries based on how the car overlaps the presence array. –  Nick Wiggill Dec 6 '12 at 16:05
1  
@CaiusEugene That depends very much on your terrain complexity and memory requirements, and cost of GC on your target devices. Start with a maximal quadtree, and take it from there, is my advice. –  Nick Wiggill Dec 6 '12 at 16:40

Implement the following methods: Add(point), Remove(point), Move(point) Move is not completeley necessary as it can be simulated by Remove and Add but that's less efficient.

Use the following mouse events: press -> Add, release -> Remove, drag -> Move

I assume you implemented your Remove and Move functions recursively. Return a boolean value from each Remove call in your Node, so you will know exactly which recursive path removed a point. If this value is true for a certain node, check if that node has any elements or child nodes inside. If it has neither, undo the subdivision.

Another approach may be to track the number of points inside each node (including children). This trades some computation time for memory and may actually be more efficient.

And a side-note: your example is not the best to demonstrate a quadtree. The idea behind quadtrees is that you only subdivide once a node has reached a certain number of points inside. If you only track one position (mouse pointer) you don't even have to subdivide at all. Instead, create a number of points that move around randomly.

share|improve this answer
    
Thanks, I've been looking at "ROAM Level Of Detail" quadtree system and it's based off a single camera (or so I thought), how does that work in regards to being a single point quadtree? –  Caius Eugene Dec 6 '12 at 10:49
    
My goal is this youtube.com/watch?feature=player_embedded&v=LxZhWrSmrOY#! but starting simple with a small grid. Isn't this just one point? –  Caius Eugene Dec 6 '12 at 11:23
    
The video shows tessalation and LOD management, the point of which is that the closer you get to the surface, the more detailed sphere it will display. It is not the same as what you're doing. As for the number of points, the sphere in the video actually has 0 points, because the subdivision they do is not done for the sake of tracking objects, but for the sake of smoothing the graphics. –  maul Dec 6 '12 at 11:35
    
that's what I'm trying to achieve. I'm trying to start by doing based off mouse distance. Apparently the technique featured in the video is quadtree based... I assumed the triangle data was being stored as a quadtree. –  Caius Eugene Dec 6 '12 at 11:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.