Quadtree Visualization

I’ve been doing some work lately with the physics engine that is in the Flare data visualization library. This is a very simple little engine that just deals with particles, forces, and springs. The Flare physics package does not include any rigid body mechanics or collision detection, since it was built as a tool for data visualization as opposed to simulation. For the purpose of things like tag clouds and force-directed layouts, this is just the trick. I can’t speak much for the rest of the Flare library, as so far, it really hasn’t met any of my needs. But, definitely check it out. There is great code here.

One nice piece of this code base is the NBodyForce class. This is a force that simulates “an N-Body force of charged particles with pairwise interaction, such as gravity or electrical charge.” To aggregate these charge values and optimize computation, a quad-tree structure is used to subdivide the 2D space in such a way that each node of the tree contains exactly one particle. Branches of the tree then represent clusters of particles, and the center of gravity and mass is collected for each branch. Then, instead of comparing each particle to all the other particles in the system, calculations of things such as gravity can be approximated by using these clusters.

Visualization of Quadtree used in N-Body force calculations
(requires Flash Player 10+)

I’m currently working on porting this to three dimensions using an octree, and to better understand all this, I felt the need for a little visualization. Of course, the rendering of the quadtree entirely undermines the efficiency of the n-body force calculations, but I think this is just fun to watch.

For this example, all particles are attached to the center by a spring with a rest length that is a factor of it’s mass. This brings bigger particles toward the center which is something you might use for instance in a tag cloud. The N-Body force here is the repulsion, technically a negative attraction, that pushes all the particles away from one another. Mouse clicks add more particles, and resizing the browser will move the center point to which the springs are all attached.

I just found a nice explanation and visualization of quadtrees in relation to collision detection over on the polygonal labs site. I’ll have to see if the motor2 physics implementation could be borrowed for this.

Also, I’ve got this working with an octree in 3D now.
Demo: N-Body forces in 3D (requires Flash player 10)

Tags: , , , ,

4 Responses to “Quadtree Visualization”

  1. Thorin Nielson Says:

    What a great visualization, fun to play with… fun to look at. I’m not a coder myself, but the idea of designing with physics in flash is really exciting and scary…in a good way. Thanks for sharing.

  2. Zach Says:

    Nice work! The 3D version is lovely too.

    I wish I had a project that could make use of Flare, the demos are impressive.

  3. andy Says:

    I was just taking a look at your Flare demos. Were you able to compile the library with Flash or did you use FDT or Flex. Looks like it has some Flex dependencies. True?

  4. david Says:

    I assume you’re talking about the Flare library as a whole. There may be some flex dependencies there. I’m not sure. The only pieces I’ve used in production are from the physics package, and that is self-contained with no external dependencies. It is this physics package that I ported to 3d. For my experiments, I was developing in FDT and compiling with the flex compiler, but there are no flex framework dependencies.