Can I use a list sorted by Morton Code for broad phase collision detection?

Question

Until now I used a list of objects sorted by a single axis for limiting the amount of objects that collisions are checked against.

The idea is simple: if the x coordinate of two objects differs by more than their width it is plain impossible that they collide. So if I want to know all possible objects inside a specific rectangle I just need to check those that are inside the indices of the smallest possible and the biggest possible x value.

Now recently I have learned about Morton Code as a way of reducing multiple axes into a single value that preserves locality. However the implications for it aren't 100% clear to me.

Can I determine something like "all objects with a morton code smaller than varA or bigger than varB can't possibly be inside rectangle A"? If so how do I determine these values?

Answer 1

Overview

The morton encoding technique, or z-order curve, essentially generates a grid index for a given coordinate if the grid is stored in a 1 dimensional array in z-order. This can therefore be used as a spatial hashing technique that can generate something similar to an octree/quadtree within a single dimensional array.

So, for a given arbitrary collision shape, if you can determine the set of morton codes that shape encompasses, then you can index the grid with these codes to see if there is any other geometry stored there, just like with an oct/quad tree.

As with other spatial partitioning, finding a hit at one of these indexes may directly imply that a collision has occurred, but it may simply act as a culling method to reduce tests as further collision checks are needed to prove a collision occurred.

Answer

Sadly, due to the nature of the storage you can't simply state "an object spans the indices i to j". The morton codes that an arbitrary shape spans will likely group into ranges, but there is likely to be more than 1 range;

See this image (I can't link it as it's an unsupported format).

A box; top left (2.5, 2.5) top right (3.5, 2.5) bottom left (2.5, 4.5) bottom right (3.5, 4.5) - would contain the Morton codes; 001111 and 100101 which aren't consecutive.

Typically objects are indexed by translating double/single precision positions into an int (sometimes scaling is applied to the values depending on the scene) which is then used to create the morton code. So if you want to find the codes an object encompasses you should calculate the set of integer points within that shape and generate the codes for those positions.

Given an axially aligned bounding box of an arbitrary size and position you can see how this might be fairly straight forward. In 2d translate the corners to the nearest int position, then starting from the top left increment x by 1 till you hit the right hand side x, then increment y and repeat. Keep looping till y = bottom y (assuming the y value is positive down the screen);

  for (int y = ceiling(top); u <= floor(bottom); ++y
  {
    for (int x = ceiling(left); x <= floor(right); ++x
    {
      Geometry* geometry;
      int mortonCode = generateMortonCode(x, y);
      if ((geometry = geometryArray[mortonCode]) != NULL)
      {
        collisionCheck(rectangle, geometry);
      }  
    }
  }

Note: For C/C++ users, rounding using a cast to int will sometimes give a number outside of the box, so use ceiling and floor; for top and left use ceiling, for bottom and right use floor. Again, this assumes y is positive down, so bottom > top.

Note: For collision detection you may want to allow the generation of codes surrounding the shape (swap ceiling and floor in the code above) to provide a slightly larger set of points which definitely will cover an area bigger than the shape you're checking.