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:
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:
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.