Quadtrees

This is today’s three things.

Quadtree is a data structure. It is a tree with each nodes having zero (leaves) or four children (internal nodes). Naturally it can be used to divide a 2D space into four quadrants recursively. In this way each internal node represents one square area, and its four children occupies the four quadrants of that area. Its operations consist of insertion, deletion and split. Split is performed when one leave is containing too many objects. It creates four children under the overloaded leave, put its objects of the four quadrants into their respective nodes.

One important use of quadtree is to check for potential particle/object collisions. Suppose there is one object out of many objects in a 2D scene that we are interested in, and we want to see what it is colliding into at a particular moment- say a bullet in a shooting game. First we arrange all the objects into a quadtree, and see one node that contains the object of interest. In that square occupied by the node, this object will only possibly collide into objects in the quadrant it resides in. If we work out the path from the root to the leave containing the object, we have a set of objects possibly colliding with it. This enables us fast detection of collision.

Will this technique be possible to apply a similar scenario, say 3D space with “Octree” (8 children per internal node)? I can imagine it being not so helpful, as we can have more complicated shape with 3D or higher dimensions. Sizes also matters. If the object of interest is huge and surrounded by small particles, quadtree or octree will not help as we always end up checking most of the particles.

Source: http://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space–gamedev-374

Other small things:

  1. I am excited about Wayland. I am eager to see NVidia proprietary driver working with Wayland. However, while Wayland does not require Kernel mode setting (KMS), its compositors (which window manager will depend on, like kwin) need it. NVidia drivers support EGL, but not KMS. KMS is an improvement for controlling graphic card configurations, including screen resolution.
  2. Pressing Ctrl+a or Ctrl+x in Vim to increment/decrement numbers at the cursor position. Wow.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s