A short Viking adventure filled with myth, magic and a little bit of pillaging.
(more…)

A big welcome to everyone visiting the brand spanking new site! Here you will find information about our games as well as be able to read about their development. We are looking forward to learning, having fun, and most importantly making great games. Check back soon for more!

Say you want to draw a full screen quad in clip space.  The straight forward way to do it is to draw two triangles to cover the viewport.  But why waste two triangles when you can do the very same thing with just one?

Using one triangle to draw a full screen quad

Drawing a triangle with vertices a, b and c covers the entire screen.  To interpolate a parameter across the quad so that it has values u₀,v₀ and u₁,v₁ at the opposite corners of the quad, set the parameter values on the three vertices as in the diagram above and in the table below.

Up until recently I’ve been very good about using std::string for strings in all of my projects.  In Kuiper 2 I decided that I wanted to try something different.  String interning is a method of allocating strings such that there is only one instance of a particular string.  For example:

// If all strings were interned then writing:
const char *a = "Hello, world!";
const char *b = "Hello, world!";

// Then this would be true:
if( a == b )
    std::cout << "The strings are the same!" << std::endl;

The code segment above is meant as an illustration and won’t necessarily work as expected. It is possible to have the compiler combine all copies of identical string literals via “string pooling” using the /GF option in MSVC(I think GCC pools strings by default.) With pooling, the code above will work as expected but it only takes care of string literals. What about dynamically allocated strings?

String Pool

To handle dynamic strings we will need to create our own string pool that will keep a unique copy of every string. Let’s keep the interface very simple:

// A wrapper around a const char *.  This helps distinguish interned strings
// from any other kind of string.
class InternedString
{
    const char *string_;

public:
    InternedString() : string_( nullptr ) { }
    explicit InternedString( const char *string ) : string_( string ) { }

    const char *Data() const { return string_; }
    operator const char *() const { return string_; }

    bool operator ==( const InternedString &rhs ) const { return string_ == rhs.string_; }
    bool operator !=( const InternedString &rhs ) const { return string_ != rhs.string_; }
};

// The string pool that will hold instances of interned strings.
class Strings
{
    class Impl;
    Impl *impl_;

public:
    Strings();
    ~Strings();

    InternedString Internalize( const char *str );
};

Using this abstraction we will be able to write things like this:

Strings strings;
InternedString a = strings.Internalize( "Hello, world!" );
InternedString b = strings.Internalize( "Hello, world!" );

// And this would be true.
if( a == b )
    std::cout << "The strings are the same!" << std::endl;

This is all neat and nice, but why would we want to do this?

Why?

Depending on your use-case there may be some benefits for interning strings. Here are some reasons why I decided to use interning in Kuiper 2:

• Only one copy of each unique string – Kuiper 2 uses a data driven approach for all of the in game assets. All scenes, textures, shaders, sound effects, pieces of text and everything else has an internal name that can be referenced by the engine. Interning the names means only one copy of each name is around.
• Fast string comparisons – This is related to the previous point. Since there is only one copy of each name, finding named objects and comparing names can be done very quickly! It’s as fast as comparing pointers and games are supposed to be fast.
• Warm and fuzzy feelings – It feels great knowing that all your strings are in one place.

Now for the dirty bit!

Implementation

Essentially the string pool is nothing more than a set of strings where equality is determined by string equality. Internalizing a string involves a check to see if a copy of it is already in the set. If it’s in there we can just return a pointer to that string. If the string is not found then we have to make a copy, insert it into a set and return a pointer to the new copy. So let’s just write exactly that:

#include <cstring>
#include <unordered_set>;

// Hash for C strings.  I think I got this from boost.
class SimpleStringHash
{
public:
    size_t operator() ( const char *str ) const
    {
        size_t hash = 0;

        int c;
        while( c = *str++ )
            hash = c + ( hash << 6 ) + ( hash << 16 ) - hash;

        return hash;
    }
};

// Predicate for comparing strings by value.
class StringPredicate
{
public:
    bool operator() ( const char *a, const char *b ) const
    {
        return a == b || strcmp( a, b ) == 0;
    }
};

class Strings::Impl
{
    // A customized unordered_set that compares and hashes elements as if
    // they were strings and not pointers.
    typedef std::unordered_set< const char *, SimpleStringHash, StringPredicate > StringSet;

    StringSet internalizedStrings_;

public:
    ~Impl()
    {
        for( const char *str : internalizedStrings_ )
            delete[] str;
    }

    InternedString Internalize( const char *str )
    {
        if( str == nullptr )
            return InternedString( nullptr );

        StringSet::iterator i = internalizedStrings_.find( str );
        if( i == internalizedStrings_.end() )
        {
            // String not found so place it into the set.
            size_t length = strlen( str );
            char *internalized = new char[ length + 1 ];

            memcpy( internalized, str, length );
            internalized[ length ] = '\0';

            internalizedStrings_.insert( internalized );
            return InternedString( internalized );
        }

        return InternedString( *i );
    }
};

// Forward all calls to the PIMPL.
Strings::Strings() : impl_( new Impl() ) { }
Strings::~Strings() { delete impl_; }

InternedString Strings::Internalize( const char *str ) { return impl_->Internalize( str ); }

That’s all there is to internalizing strings. In a future post I will talk about how to use a memory pool to keep all strings allocated in the same memory area.

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;
	}
}

In the Point in Polygon Test post we used a Ray-Line Segment intersection test in order to figure out how many sides of the polygon intersected a test ray. This post will explain how that test was derived.

Problem

Find out if a ray with origin and direction intersects a line segment with end points and .

Will it intersect?

This problem can be converted into a Ray-Ray intersection problem if you turn the line segment into a ray with origin and direction but we are not going to do that. Well we are, but not explicitly.

Solution

Checking if two things intersect involves finding out if they share at least one common point. The first step is to express the ray and the line segment as sets of points.

Points on lines

In parametric form, the ray becomes

for .

The line segment on the other hand is

for .

Next we can set the two equations to be equal and find the values of and . Since there are two dimensions the equality can be split into the and counterparts and give us two equations to solve for the two unknowns. Once and are calculated the ray and the segment intersect if and . Under these conditions the point of intersection is on both the ray and the line segment.

After Some Algebra

The solution simplifies very neatly if you make some substitutions. Let , and . Intuitively, is just the direction perpendicular to . The result:

The symmetry is pretty cool!

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 < 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 equal to the line segment and solve for . The ray will hit the line segment if (line segment is in front of the ray) and (the ray crosses the line segment between and ).

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!