World querying

Box2D C++ tutorials - World querying

Last edited: July 14 2013

Chinese version -> 中文

Often you will want to know what entities are in a given part of the scene. For example if a bomb goes off, everything in the vicinity should take some damage, or in an RTS type game you might want to let the user select units by dragging a rectangle around them. The method of quickly checking what objects are in that part of the world to use for further detailed processing is known as 'world querying'.

Box2D provides two tools for this - ray casting and AABB testing. Ray casting... didn't we just do that? Yes, we did it the manual way, by looping through every fixture in the world and checking the ray against them all to find out which one was the closest. This can be very inefficient when you have a large number of fixtures in the scene. A better way is to use the RayCast function of the world itself. This allows the engine to focus on fixtures which it knows are near the ray's path.

Ray casting, the efficient way

Since we have already looked at ray casting in some detail, we'll just take a quick look at the world's RayCast function without making a demonstration. The function looks like this:

1	void RayCast(b2RayCastCallback* callback, const b2Vec2& point1, const b2Vec2& point2);

The last two parameters are pretty simple, they are the beginning and end point of the ray, and we use them as we would for a ray cast against a single fixture. The 'callback' parameter is new, but by now we are familiar with how callbacks in Box2D usually work, so it's no surprise that we would implement this by making a subclass of b2RayCastCallback, and passing an instance of it to this function as the callback. The b2RayCastCallback class has only one function to override, and it is:

1 2	//in b2RayCastCallback class float32 ReportFixture(b2Fixture* fixture, const b2Vec2& point, const b2Vec2& normal, float32 fraction);

During the ray cast calculation, each time a fixture is found that the ray hits, this callback function will be called. For each intersection we can get the fixture which was hit, the point at which it was hit, the normal to the fixture 'surface' and the fraction of the distance from point1 to point2 that the intersection point is at. The diagrams in the ray casting topic may help to explain the fraction parameter.

The final point to cover is the return value that you should give for this callback function. Remember that if your ray is long enough there could be many fixtures that it intersects with, and your callback could be called many times during one RayCast. Very importantly, this raycast does not detect fixtures in order of nearest to furthest, it just gives them to you in any old order - this helps it to be efficient for very large scenes. The engine lets you decide how you want to deal with each fixture as it is encountered. This is where the the return value of the callback comes in. You will return a floating point value, which you can think of as adjusting the length of the ray while the raycast is in progress. This can be a little confusing so take it slow...

return -1 to completely ignore the current intersection
return a value from 0 - 1 to adjust the length of the ray, for example:
- returning 0 says there is now no ray at all
- returning 1 says that the ray length does not change
- returning the fraction value makes the ray just long enough to hit the intersected fixture

Here the fraction value refers to the 'fraction' parameter that is passed to the callback. If I can be bothered I might make a diagram for this later, but if the above description is not clear just remember the common cases:

To find only the closest intersection:
- return the fraction value from the callback
- use the most recent intersection as the result
To find all intersections along the ray:
- return 1 from the callback
- store the intersections in a list
To simply find if the ray hits anything:
- if you get a callback, something was hit (but it may not be the closest)
- return 0 from the callback for efficiency

Area querying (aka AABB querying)

The Box2D world has another function for finding fixtures overlapping a given area, the AABB query. This one allows us to define a rectangular region, and the engine will then find all fixtures in that region and call a callback function for each of them. Typically the callback is used to fill a list of fixtures in preparation for some other processing to follow, but this method allows you to implement other kinds of processsing efficiently too. For example, if there are a large number of fixtures in the given area but all you want to do is find out if their total mass is more than a certain amount, you could add their masses as the query progressed, and as soon as you find the necessary mass, the query can finish.

The function for this is called QueryAABB and it gets the name because the area must be specified as an 'axis-aligned bounding box'. This just means that the area is rectangular and can't be rotated at an odd angle. It also means that instead of testing whether fixtures are within the area, it tests if the AABBs of fixtures are within the area. You can turn on rendering of the AABBs for fixtures in the testbed with one of the checkboxes on the right. Here is an example of the AABBs (purple) of some fixtures. World querying

The function looks like this:

1	void QueryAABB(b2QueryCallback* callback, const b2AABB& aabb);

Do you like these callback functions? I hope so because here is another one. As usual, you need to make a subclass of the b2QueryCallback class and implement a function. The single function in this class is:

1	bool ReportFixture(b2Fixture* fixture);

Awesome, only one parameter. Since the AABB query just finds out whether a fixture is inside the area or not, there is no need for any trickiness like the ray cast query above. When you call QueryAABB, your ReportFixture callback will just be called for each fixture in the area, passing that fixture as the parameter. Let's try an example of using this feature.

We will set up a test where we define a rectangular area, and then draw marker on each fixture which is currently overlapping the area. We'll use the same scene as at the beginning of the last topic, so go copy the code from there. World querying

First let's get the area displaying on the screen. We can override the MouseUp and MouseDown functions of the Test class to store the corners of the rectangle as member variables of our FooTest class. Then in the Step() function, draw a rectangle using those points:

  //FooTest class member variable
  b2Vec2 mouseDownPos, mouseUpPos;
  
  //FooTest class functions
  void MouseDown(const b2Vec2& p) { mouseDownPos = mouseUpPos = p; Test::MouseDown(p); }
  void MouseUp(const b2Vec2& p) { mouseUpPos = p; Test::MouseUp(p); }
  
  //in Step() function, draw the rectangle
  b2Vec2 lower( min(mouseDownPos.x,mouseUpPos.x), min(mouseDownPos.y,mouseUpPos.y) );
  b2Vec2 upper( max(mouseDownPos.x,mouseUpPos.x), max(mouseDownPos.y,mouseUpPos.y) );
  
  glColor3f(1,1,1);//white
  glBegin(GL_LINE_LOOP);
  glVertex2f(lower.x, lower.y);
  glVertex2f(upper.x, lower.y);
  glVertex2f(upper.x, upper.y);
  glVertex2f(lower.x, upper.y);
  glEnd();

Unfortunately this version (v2.1.2) of Box2D's testbed doesn't allow us to override the MouseMove function, so we can't actually see the box as we drag the mouse to draw it.
World querying

With a query area in place, we now get on with the actual AABB query itself. First we'll need to make a subclass of the b2QueryCallback class to hold the callback function, and a list to hold the fixtures that were found inside the query region. You could put the list in global or class scope, but as world query results tend to be very temporal in nature, it can be more intuitive to keep the results list in the callback class itself and use a new instance of it each time.

  //subclass b2QueryCallback
  class MyQueryCallback : public b2QueryCallback {
  public:
      std::vector<b2Body*> foundBodies;
      
      bool ReportFixture(b2Fixture* fixture) {
          foundBodies.push_back( fixture->GetBody() ); 
          return true;//keep going to find all fixtures in the query area
      }
  };
  
  //in Step() function
  MyQueryCallback queryCallback;
  b2AABB aabb;
  aabb.lowerBound = lower;
  aabb.upperBound = upper;
  m_world->QueryAABB( &queryCallback, aabb );
  
  
  //draw a point on each body in the query area
  glPointSize(6);
  glBegin(GL_POINTS);
  for (int i = 0; i < queryCallback.foundBodies.size(); i++) {
      b2Vec2 pos = queryCallback.foundBodies[i]->GetPosition();
      glVertex2f( pos.x, pos.y );
  }
  glEnd();

Note that we need to return true from the callback function to make sure the query keeps going until all of the overlapping fixtures have been put into the list. You should see a white spot on each fixture which has an AABB overlapping the region. In the screenshot above, you can see in the bottom left an example of how the AABB can overlap the region while the fixture itself does not.

Next: Removing bodies safely