Smooth Gem Trail in Kuiper

Posted on July 11th, 2014

In Kuiper the player’s ship has a trail of gems following it as it flies about. To achieve this effect we need two things. First, the position information of the player has to be collected every frame. Second, we need to be able to place objects evenly along an arbitrary path.

Collecting Position History

This part is pretty straight forward because all we need to do is store the player’s position in some sort of array or list. In Kuiper there is a queue that stores the historical position data. This works well as new positions are added to the back of the queue and old positions are popped off the front.

If the ship flew around on a plane or didn’t require interpolation, a list of positions would be sufficient. In Kuiper the ship flies around on the surface of a torus which is simulated by wrapping the player to the opposite side of the world when they fly out of bounds. Additionally the position of all the objects is smoothed for display in between physics updates.  This can cause a problem during the frame that the player jumps to the opposite side of the world because the interpolation will make the ship appear to fly right across the screen! To remedy this we will also store the ship’s velocity at each frame and use it to calculate what the next, unwrapped, position should be for interpolation.

Player position and velocity history (debug mode)

Here is the structure that goes into the queue:

struct HistoryPoint
{
	glm::vec2	Position;
	glm::vec2	Velocity;

	HistoryPoint() { }
	HistoryPoint( const glm::vec2 &position, const glm::vec2 &velocity )
		: Position( position )
		, Velocity( velocity ) { }
};

The math library I use is called GLM.

Placing Objects

Given a history of positions and velocities we can figure out how to place objects along the player’s path. The idea is that we start from the beginning of the position history and take little steps until we get to the end. We keep track of the distance covered by the steps and every time it reaches a certain threshold we place an object there. Here is some code:

// The spacing parameter that will determine how far to walk until placing
// the first object in the history.
float spacing = parameters_.CrystalSpacing + parameters_.ShipSize;

// Start from the most recent history sample.
HistoryList::iterator i = positionHistory_.begin();

// Loop over all crystals that have been picked up.
for( Entity &crystal : crystals_ )
{
	while( i != positionHistory_.end() )
	{
		const glm::vec2 &p( i->Position );
		const glm::vec2 &v( i->Velocity );

		// This is the distance that that is traversed during the
		// frame of the history sample.
		float d = glm::length( v ) * dt;

		// If the spacing drops below 0 that means it's time to place
		// another object.
		if( spacing - d <= 0.f )
		{
			// Entities are interpolated so we set the current position and the
			// position it will be at the next frame.
			crystal.Position = p;
			crystal.NextPosition = p + v * dt;

			// Reset the spacing and break to move on to the next crystal.
			spacing = 2.f * parameters_.CrystalSpacing - d;
			break;
		}

		// Take another step along the historical path.
		spacing -= d;
		++i;
	}
}
Share

Point in Polygon Test

Posted on May 26th, 2014

Given a polygon and a point, how do you tell if the point is inside or outside the polygon?

Idea

In 2D let’s think of the polygon as dividing the whole space into two regions. The finite region inside the polygon and the infinite region outside. Imagine yourself standing at the point which we wish to classify as being inside or outside. Next, pick a direction and start walking in a straight line. As you walk, keep track of the number of times you cross an edge of the polygon. After a long while when you are certain you have left the polygon behind, maybe at infinity, take a break and consider the number of times you crossed its edges.

Every edge crossing implies that you have either left or entered the polygon so it toggles your current state of being inside or outside. An odd number of crossings means that your current state is opposite of what it was when you started while an even number of crossings means it is the same. So as you take your break at infinity far outside of the polygon you know that if the number of crossings was odd you started on the inside and if it was even you started outside.

Implementation

Now let’s convert the idea into some code. Here is what a polygon looks like:

struct Polygon
{
    vec2 *Vertices;
    int   NumVertices;
};

A polygon is a list of vertices. The edges are implied by the order of the vertices with each pair of consecutive vertices forming an edge. In this case the algorithm translates to code fairly naturally:

// This function returns true if the ray with origin o and direction d intersects a line segment
// with endpoints a and b.
bool RayLineSegmentIntersection( const vec2 &o, const vec2 &d, const vec2 &a, const vec2 &b );

bool IsInside( const vec2 &point, const Polygon &polygon )
{
    int numCrossings = 0;

    // Loop over all edges in the polygon.
    for( int i = 0; i &lt; polygon.NumVertices; ++i )
    {
        int j = ( i + 1 ) % polygon.NumVertices;

        // Check if a ray in the positive x direction crosses the current edge.
        if( RayLineSegmentIntersection( point, vec2( 1, 0 ), polygon.Vertices[ i ], polygon.Vertices[ j ] ) )
            ++numCrossings;
    }

    // If the number of crossings is odd, the point was inside the polygon.
    return ( numCrossings % 2 ) == 1;
}

The implementation above does exactly what we described. It shoots a ray from the point in question down the x axis(the direction doesn’t matter since a polygon will completely surround us if we’re inside) and counts how many edges it intersects. Then depending on the count the point is classified.

Ray-Line Segment Intersection Test

Here is a way to test a ray against a line segment. To get this result just set the ray \mathbf{x_1}(t_1)=\mathbf{o}+\mathbf{d}t_1 equal to the line segment \mathbf{x_2}(t_2)=\mathbf{a} + (\mathbf{b} - \mathbf{a})t_2 and solve for t_1, t_2. The ray will hit the line segment if t_1 \geq 0(line segment is in front of the ray) and 0 \leq t_2 \leq 1(the ray crosses the line segment between \mathbf{a} and \mathbf{b}).

bool RayLineSegmentIntersection( const vec2 &o, const vec2 &d, const vec2 &a, const vec2 &b )
{
    vec2 ortho( -d.y, d.x );
    vec2 aToO( o - a );
    vec2 aToB( b - a );

    float denom = dot( aToB, ortho );

    // Here would be a good time to see if denom is zero in which case the line segment and
    // the ray are parallel.

    // The length of this cross product can also be written as abs( aToB.x * aToO.y - aToO.x * aToB.y ).
    float t1 = length( cross( aToB, aToO ) ) / denom;
    float t2 = dot( aToO, ortho ) / denom;

    return t2 >= 0 && t2 <= 1 && t1 >= 0;
}

That is all there is to it. In a future post we’re going to revisit and solve this problem using some tricks!

Share