Collision Detection: Go Stone vs. Go Board

Hello, I’m Glenn Fiedler and welcome to Virtual Go, my project to simulate a Go board and stones.

We have already mathematically defined the shape of a go stone, tessellated it so it can be rendered using 3D graphics hardware and discussed how the go stone moves, both linear and angular motion, and how it is accelerated by gravity.

This is all great but right now the go stone falls right through the go board!

Our next goal, obviously, is to get the go stone to bounce and come to rest on the go board.

corner with slate and shell stones

Understandably this is quite complicated! So, in this article I’ll focus on the first step: detecting collision between the stone and the board.

Voronoi Regions and The Minkowski Difference

First, lets assume that the go board is axis aligned and does not move.

Because go stones are small relative to the go board, we can break down the collision detection into regions which are treated differently.

The common case is with the primary surface, the actual playing surface of the go board, so lets start by looking top-down at the go board and breaking it up into 2D voronoi regions.

voronoi regions

Each voronoi region corresponds to a subspace where all points (x,z) in that region map to the same nearest feature on the go board. This gives us one region that maps points to the top surface of the go board, four regions that map to the sides and four corner regions.

If we were testing an infinitely small point against the go board, this would be sufficient but we are colliding a go stone of a certain width and height.

One simple way to incorporate the dimensions of the go stone is to offset the regions from the edge of the go board by the the go stone’s bounding sphere radius. Note that we’re not attempting to calculate exact collision yet, we’re just trying to break down into a number of cases so we can simplify the actual collision detection part later on.

This creates something like a poor man’s version of a minkowski difference:

minkowski difference

We can now quickly test the center of the go stone against the region boundaries to categorize the type of potential collision.

enum BoardEdges
{
    BOARD_EDGE_None = 0,
    BOARD_EDGE_Left = 1,
    BOARD_EDGE_Top = 2,
    BOARD_EDGE_Right = 4,
    BOARD_EDGE_Bottom = 8
};

enum StoneBoardRegion
{
    STONE_BOARD_REGION_Primary = 
        BOARD_EDGE_None,

    STONE_BOARD_REGION_LeftSide = 
        BOARD_EDGE_Left,

    STONE_BOARD_REGION_TopSide = 
        BOARD_EDGE_Top,

    STONE_BOARD_REGION_RightSide = 
        BOARD_EDGE_Right,

    STONE_BOARD_REGION_BottomSide = 
        BOARD_EDGE_Bottom,

    STONE_BOARD_REGION_TopLeftCorner =
        BOARD_EDGE_Top | BOARD_EDGE_Left,

    STONE_BOARD_REGION_TopRightCorner = 
        BOARD_EDGE_Top | BOARD_EDGE_Right,

    STONE_BOARD_REGION_BottomRightCorner =
        BOARD_EDGE_Bottom | BOARD_EDGE_Right,

    STONE_BOARD_REGION_BottomLeftCorner = 
        BOARD_EDGE_Bottom | BOARD_EDGE_Left
};

StoneBoardRegion 
DetermineStoneBoardRegion( const Board & board, 
                           vec3f position, 
                           float radius )
{
    const float thickness = board.GetThickness();
    
    const float x = position.x();
    const float y = position.y();
    const float z = position.z();

    const float w = board.GetHalfWidth();
    const float h = board.GetHalfHeight();
    const float r = radius;

    uint32_t edges = BOARD_EDGE_None;

    if ( x <= -w + r )
        edges |= BOARD_EDGE_Left;
    else if ( x >= w - r )
        edges |= BOARD_EDGE_Right;

    if ( z >= h - r )
        edges |= BOARD_EDGE_Top;
    else if ( z <= -h + r )
        edges |= BOARD_EDGE_Bottom;

    return (StoneBoardRegion) edges;
}

Go Board Cases

Although the go board has nine different regions there only three unique types:

  1. Primary surface
  2. Edge
  3. Corner

Primary surface is the common case.

board primary case

The only possible collision in this case is between the stone and the playing surface of the go board.

Since the go board rests on the floor and cannot move we do not need to worry about collisions with the bottom surface. This means that we can consider the go board to be infinitely thick. This is extremely useful because it removes the possibility of fast moving go stones tunneling vertically through the board.

Next is the edge case. This is more complicated because there is more than one way to collide in edge regions. Tests must be done between the go stone and the top plane, the side plane and the side edge.

board side case

The corner case is more complicated still. Potential collisions include the top plane, the two side planes, the side edges adjacent to the corner, the vertical corner edge, and the corner point.

board corner case

Go Stone Cases

When a go stone collides with another object there are three collision types to consider.

The first is a collision on the top surface of the biconvex. This corresponds to a collision with a portion of the bottom sphere that generated the go stone.

biconvex collision top

Next is the bottom surface of the biconvex. This corresponds to the top sphere.

biconvex collision bottom

Finally, the collision point can be on the circle ring at the intersection of the two sphere surfaces.

biconvex collision circle ring

Separating Axis Test (SAT)

So we have 3 ways a stone can collide with any convex object, and we have 9 different regions that must be treated differently when testing vs. the go board. Within each region we have up to 7 different features on the go board that must be tested against 3 different features on the go stone.

This is all rather complicated. How can we simplify it?

The solution is to use the separating axis test.

Basically the idea is that if we can find a plane that separates the stone and the board then they must not be colliding. This is a robust way of thinking about collision which makes the actual testing of collision detection between objects easy, and more importantly, more generic and less prone to combinatorial explosion.

Calculating The Support

In order to use the separating axis test we must first write a function that determines the support of the go stone.

The support is the projection of an object on to an axis. This can be difficult to think about in 3D, but for me at least it is easiest to think of the axis not as a line, but as the normal of a plane.

What we are really asking is: given this plane normal, what two planes from either side tightly bound the object like book-ends on a shelf?

To calculate the support of a go stone we need to consider two cases.

The first is when the go stone is vertical relative to the axis. Here it is reasonably easy. To calculate the support you simply calculate the intersection of the supports of the spheres used to generate the go stone. This makes a nice sort of intuitive sense seeing as the go stone is itself the intersection of two spheres.

biconvex support intersection of sphere support

To calculate a sphere support just take the projection of the sphere center and +/- the radius along the axis.

Unfortunately, this technique breaks down when the stone is horizontal relative to the axis because it fails to exclude the portion of the spheres that don't contribute to the biconvex solid.

biconvex support wrong

What you need to do in this case instead is to calculate the support of the circle edge.

biconvex support correct

This can be done relatively easily by finding the projection of the circle along the axis. Unlike a sphere this depends on the relative orientation of the go stone and the axis. Once you have this projection just +/- to the projection of the center of the go stone on the axis to find the support.

The tricky part is detecting when the transition between these two cases occur. Here is a diagram I created a while back when I first tried to work this out. If you look closely you can see the exact point where my head exploded:

biconvex support head explode

Here is a visualization of the result:

Primary Case

Now that we have the support we can use a one-sided variant of the SAT to detect collision with the primary surface. We're doing the one-sided variant because we already decided to treat the go board as 'infinitely thick' to avoid tunneling in the common case.

First, we take the normal of the primary surface which is up (0,1,0) and find the support for the go stone along this axis: s1 and s2.

Next, we calculate the projection of the board surface along the normal: t

If s1 <= t then the go stone is colliding with the go board:

Unfortunately we detect the collision after the go stone has already penetrated the go board. There are many solutions for this problem: continuous collision detection, and speculative contacts being very interesting avenues I may explore later on.

But for now I just do the simplest, most pragmatic thing I can think of.

I just push the stone out of the board along the axis.

After I push the stone out, I recalculate the nearest point between the stone and board and use this as the contact point.

Edge and Corner Cases

The primary surface case is easy because only one axis needs to be tested, but in corner and edge regions multiple axes must be tested for collision.

multiple axes SAT

When you are considering multiple axes, apply the separating axis test as follows:

  • Test all features in the region and determine if there is any separating axis
  • If a separating axis exists then the go stone is not colliding with the board
  • Otherwise the stone must be colliding with the board

If the stone is colliding we must now work out what direction to push the stone out.

I thought about this for some while and tried to come up with a simple pattern that worked.

First, I tried pushing the stone out along the axis with the greatest amount of penetration, but that breaks down pretty severely in the case where a go stone approaches the go board from the side:

multiple axes push out most penetration

Next I thought that perhaps I could use the previous position of the go stone and try to determine the direction that the stone is approaching from. But then I thought about go stones that were rotating rapidly and how this wouldn't always be correct. Then I started thinking about corner and edge cases and the longer I thought the more this approach seemed too complicated, like I was trying to invent my own half-assed continuous collision detection method that would only work half the time and be almost impossible to test.

In the end I settled on the simplest solution I could come up with: push the go stone out along the axis with the least amount of penetration.

You can see that this passes the test that previously failed:

multiple axes SAT push out least penetration

Now this seems counter-intuitive at first, but it has some nice parallels with other physical laws.

Nature is lazy and always takes the shortest path.

Your physics simulation should probably do the same :)

Next: Rotation and Inertia Tensors




If you enjoyed this article please donate. Donations encourage me to write more articles!

15 comments on “Collision Detection: Go Stone vs. Go Board
  1. Hi Glenn, great series so far.

    Just wanted to let you know this article seems to be missing the last two diagrams.

    Are you going to be covering collisions between Go-stones as well? I’d be very interested to read your take on sequential vs. simultaneous physics (handling each body’s movement in turn, or all simultaneously) and discrete vs. continuous collision-detection.

    Sequential + discrete is obviously the simplest, and in this case where only one object is moving at a time I guess adding continuous collision-detection is rather easy as well (just use a swept-volume)? It’s obviously not physically accurate (can collide with object that would move out of the way but hasn’t been handled yet), but it seems like a fair trade-off given a reasonably small timestep.

    Could you say anything about what is actually used in most games?

    Cheers.

    • Thanks. I was not happy with the last section but got tired while I was in the middle of reworking it. Diagrams are such a pain in the ass :) I’ll have it sorted out shortly.

      Yes, I’ll be covering stone vs. stone collision later on after collision response and friction. I really want to get to basic collision response and friction first, and save the simultaneous contacts until later on when I have my iterative solver working.

      Anyway, for the collision part of stone vs. stone it’s all just SAT and the only tricky part is working out the complete set of axes to test against

      cheers

        • I remember reading and trying that at some point. It seems pretty clever, but I didn’t like the ghost collisions it generates. Specifically (for my purposes), if you’re at the bottom of a ledge in a 2D game and jump straight up you’ll land on the top of the ledge instead of falling back down to where you were. (You can try this on the platformer on his site.) A really minor issue, but it destroys that pixel-perfect feel I’d like. It’s possible it’s actually just a off-by-one error in the code somewhere (though I don’t think so), but I didn’t feel like digging through it just to make sure and some random tweaking didn’t get me anywhere.

          For your purposes I’d guess the bigger problem would be the seeming lack of support for non-zero coefficients of restitution however — so the stones wouldn’t bounce off each other? I don’t know if you’ve tried, but he seemed to have some trouble implementing it.

          I don’t want to take up too much of your time as I’m sure you’re busy, especially with GDC coming up, but I’d really appreciate it if you could help clear this (hopefully not too off-topic issue) up for me:

          In the first demo on the page you linked one can choose between “discrete” and “discrete sequential”. From Ericson’s RTCD-book (page 15 / section 2.4.2 if you happen to have it handy) I gathered “sequential” (as opposed to simultaneous) in this context to mean “fully handle the movement of each body in turn during the frame”, i.e. you basically loop over each object and move it accordingly (resolving collisions as you go, making it easy to avoid tunnelig as everything aside from the current object is static).

          However, in the demo there is only one moving object so it seems the two choices should be identical — but clearly they are not, especially with added iterations.

          Is “sequentially” here actually referring to how a list of generated contacts are handled after objects are (here discretely) moved, or something similar? This seems likely as you’re also referring to “contacts” and “solver” in your reply. I feel like Ericson’s notion of “Sequential vs Simultaneous Motion” and “Discrete vs Continuous Motion” from the book makes sense, but it’s really tripping me up when trying to understand other resources so it seems like there is a mismatch in terminology?

          I think maybe I get confused because I’ve mainly been concerned with getting tunnel-free and non-penetrative movement, so I haven’t really considered how e.g. a distance-constraint could be maintained and how similar issues factors in. I guess that would complicate things highly, and is why seemingly nobody simply moves each object in turn (continuously) — while it’s great for avoiding tunneling and interpenetration (i.e. what I’ve been focusing on), it’s probably not a sufficient solution for physics engines in general?

          Does it sound like I’m on the right track here? Thanks in advance for any hints in regards to where my understanding breaks down. :)

          • Hi Christian I actually don’t have any real experience with continuous collision detection (yet).

            My plan was to move all objects then do interative impulses to resolve multiple contacts and penetration.

            In my experience working on Christer’s team I can say that most (all?) practical instances of continuous collision I’ve seen boil down to:

            1. Hold every object fixed except the one that is moving now

            2. Minkowski sum

            3. Do a raycast :)

            This works great for linear character movement in a static world but breaks down for rotating bodies, multiple simultaneous contacts, stacking and so on

            Cheers

  2. Glenn, i want to say – you already did a great job!! Its really pleasure to read all this material and understand technical details of this things. I don’t have words to describe my feelings right now, but you are semigod to me cause you not just do, but also greatly describe what are you doing. This details can help not only in this particular project, but can be used in similar tasks, and thats why can be used in teaching of new programmers.

  3. Didn’t even see this article. I want to learn GO, so I am trying to make an interface in Python/Tk. I plan on connecting it later to blender. I have used your networking articles so far, but I *am* a beginner. In there you mention an article on multi-client UDP.

    Should I use TCP, or UDP, and single-client or multi-client? For now, this whole UDP thing seems a bit overwhelming.

    Cheers

    • TCP should be fine for what you want to do. UDP is only neccessary when what you are networking is time critical and you have both latency and packet loss. cheers

Leave a Reply