Introduction to Geometric Queries

Just about every game, whether simple or complex, will require making geometric queries. It’s a fundamental part of building a game, so I wanted to cover it before we go further. Geometric queries also act as building blocks for many more things that we’ll talk about in upcoming posts.

So what is a geometric query, anyway? It’s a generic term that covers all questions involving shapes, positions, orientations, and anything else geometry related. Here are some common examples from various parts of a game engine:

1. Collision – Did the player collide with anything this frame?
2. Graphics – Is a particular object visible to the camera?
3. Audio – Can the player hear a particular sound? How loud, and in what direction?
4. Input – Does the touch point or mouse click location “select” an object?
5. AI – Is an enemy soldier’s path to the room unobstructed?

It’s possible to build more complex geometric queries by combining simpler ones. For that reason, I think it’s important to build a set of basic primitive tests that you can use to solve all kinds of problems with. These primitive queries are so fundamental, that I view them as an extension of the core math library.

Geometric queries come in a variety of forms. Some ask a Boolean question, others ask for specific details such as distance or angles. There are countless queries we can come up with, but we’ll focus on a few key types of basic queries. They are:

• Boolean overlap query – Do two shapes overlap in any fashion? No additional data is returned, only that they overlap or that they don’t. Overlap is defined as sharing any region of space with each other, so even if one is completely contained in the other, they’re considered overlapping.
• Overlap query – This is similar to the Boolean overlap query, except that it also returns information about the overlapping region.
• Intersection query – This is a class of queries that can return more detailed intersection data.
• Ray cast query – If you shoot a ray out from a point in a direction, does it hit anything? Where? How far?

Shapes can range from very simple (points, lines, triangles) to very complex (arbitrary polyhedra, smooth curvy surfaces, etc…). For the purposes of this blog, we’ll start with some simple shapes as our building blocks, and in later posts will cover a few complex ones. However, we’ll generally always stick with convex shapes. This is because queries involving convex shapes generally have simpler solutions (both mathematically so we can understand them, and computationally so they are efficient). Most non-convex shapes can be described in terms of multiple convex ones, so we can usually use a combination of smaller queries to answer the non-convex question.

This post was just an introduction to the concept of geometric queries, giving a reason for why we care about them. In the coming posts, we’ll explore some basic shapes and common queries involving them. I’ll do my best to come up with real-world examples to use for the motivation of each test. I’m currently planning on covering points, lines, triangles, spheres, and axis aligned boxes as the simple shapes. Then, the plan is to talk about using a change of basis and the separating axis test as a way to solve more complicated problems, using the non-axis aligned box (also called oriented bounding box) as an example. Once shapes are covered, we’ll talk about higher level algorithms for visibility culling, collision detection, space partitioning, etc…

Also, if you have specific shapes or queries you’re interested in, please let me know and I’ll try to include them.