There you are developing a 2D game, everything’s going great – sprites everywhere and they look super good. Here’s an awesome sprite for demonstration purposes.

TexturedQuad

What could possibly go wrong?

Someone (Designer Dave?) decides that it would be a good idea to texture a trapezoid or some other irregular quad. You specify your texture coordinates, fire them at the graphics card and OMG! WHAT THE HELL IS THAT MESS?

DistortedTexture

Distorted textures, eh? We’ve all encountered the problem at some point (haven’t we?)

That’s linear interpolation at work that is and the issue is caused because the triangles that make up the quad are different sizes / shapes.

No problem, you say, the graphics card is a clever chap and knows how to perform perspective correct texture mapping – I’ve seen it in those 3D games and they look great (PS1 not withstanding). All I need to do is modify XY and use one of those extra properties of the texture coordinate like ‘Z’ (or ‘q’ I believe it might be called in OpenGL / GLSL) and fix up the shader to use it. Easy this graphics coding.

Here’s some code that fixes up the texture coordinates
(converted from Java from: http://www.bitlush.com/posts/arbitrary-quadrilaterals-in-opengl-es-2-0)

var texCoords = new[]
{
	new Vector4(0, 1, 1, 1),
	new Vector4(0, 0, 1, 1),
	new Vector4(1, 1, 1, 1),
	new Vector4(1, 0, 1, 1)
}

//Modify the texture coordinates
for (var i = 0; i < points.Length; i += 4) { 
	var a = points[i + 3] - points[i]; 
	var b = points[i + 2] - points[i + 1];
	var cross = a.X*b.Y - a.Y*b.X; 
	
	if (!(cross > 0) && !(cross < 0)) 
		continue; 
		
	var c = points[i] - points[i + 1]; 
	var s = (a.X*c.Y - a.Y*c.X)/cross; 
	if (!(s > 0) || !(s < 1)) 
		continue; 

	var t = (b.X*c.Y - b.Y*c.X)/cross; 
	if (!(t > 0) || !(t < 1))
		continue;

	texCoords[i] *= 1/(1 - t);
	texCoords[i + 1] *= 1/(1 - s);
	texCoords[i + 2] *= 1/s;
	texCoords[i + 3] *= 1/t;
}

…and a typical perspective correct pixel shader…

float4 PixelShaderFunction(VertexShaderOutput input) : COLOR0
{
    return tex2D(TextureSampler, input.TexCoord.xy / input.TexCoord.z);
}

PerspectiveTexture

Awesome – now the textures are mapped without distortion – sure they look 3D even though the quad is strictly on a 2D plane but *I* can live with that.

“Hmmm”, says Designer Dave, “wouldn’t it be great if our game had some sort of trail or lightning effect – we could texture it and have everything all line up nice and neat now and it would look excellent!”

OR MOST DEFINITELY NOT EXCELLENT!

Look!

DistortedTrail

We started to build the trail – added a second quad (I’ve left a little gap so it’s easier to see the individual segments), applied the perspective correction to it that helped us so much previously, but it’s still broken!
HOW IS THIS HAPPENING?

Well, each quad in the trail gets a different perspective projection applied to it – so the textures will not line up at the seams.

We can either sack Dave for coming up with all these difficult to implement ideas or we could use BILINEAR INTERPOLATION. This is not to be confused with BILINEAR FILTERING used for those super fuzzy textures that were all the rage during the N64 days. No, this is the answer to all our prayers (if we’ve been praying for correctly texture mapped 2D trail effects that is).

See this article for the details (starts at page 14)
http://www.cs.cmu.edu/~ph/texfund/texfund.pdf

…that explains what we need to do – just got to do the actual doing now!

My naive, cheap as chips, first attempt implementation in XNA is as follows. There’s probably loads of optimization that could be done.
Create a new vertex declaration…

public struct VertexBilinearInterpolation : IVertexType
{
	public Vector3 Position;
	public Vector2 P00;
	public Vector2 P01;
	public Vector2 P10;
	public Vector2 P11;

	static readonly VertexDeclaration VertexDeclaration = new VertexDeclaration
			(
			new VertexElement(0, VertexElementFormat.Vector3, VertexElementUsage.Position, 0),
			new VertexElement(12, VertexElementFormat.Vector2, VertexElementUsage.TextureCoordinate, 0),
			new VertexElement(20, VertexElementFormat.Vector2, VertexElementUsage.TextureCoordinate, 1),
			new VertexElement(28, VertexElementFormat.Vector2, VertexElementUsage.TextureCoordinate, 2),
			new VertexElement(36, VertexElementFormat.Vector2, VertexElementUsage.TextureCoordinate, 3)
			);
			
			//rest of code
}

For every quad segment of the trail…

For every vertex in the quad…

Pass the vertex along with the 4 vertices of the quad.

var quadId = 0;
for (var i = 0; i < points.Length; i++)
{
		_vertexList.Add(new VertexBilinearInterpolation(
			new Vector3(points[i], 0.0f), 
			points[quadId], 
			points[quadId + 1], 
			points[quadId + 2], 
			points[quadId + 3]));

		if ((i + 1) % 4 == 0)
			quadId += 4;
}

Create a new shader to do the bilinear interolation

float4x4 World;
float4x4 View;
float4x4 Projection;

sampler TextureSampler : register(s0) = sampler_state
{
	AddressU = CLAMP;
	AddressV = CLAMP;
};

struct VertexShaderInput
{
    float4 Position : POSITION0;
    float2 P00 : TEXCOORD0;
    float2 P01 : TEXCOORD1;
    float2 P10 : TEXCOORD2;
    float2 P11 : TEXCOORD3;
};

struct VertexShaderOutput
{
    float4 Position : POSITION0;
    float2 Pos : TEXCOORD0;
    float2 P00 : TEXCOORD1;
    float2 P01 : TEXCOORD2;
    float2 P10 : TEXCOORD3;
    float2 P11 : TEXCOORD4;
};

VertexShaderOutput VertexShaderFunction(VertexShaderInput input)
{
    VertexShaderOutput output;

    float4 worldPosition = mul(input.Position, World);
    float4 viewPosition = mul(worldPosition, View);

	output.Position = mul(viewPosition, Projection);
	
    output.Pos = input.Position;
    output.P00 = input.P00;
    output.P01 = input.P01;
    output.P10 = input.P10;
    output.P11 = input.P11;

    return output;
}

float cross(float2 a, float2 b)
{
    return a.x * b.y - a.y * b.x;
}

// given a point p and a quad defined by four points {a,b,c,d}, return the bilinear
// coordinates of p in the quad. Returns (-1,-1) if the point is outside of the quad.
float2 invBilinear(float2 p, float2 a, float2 b, float2 c, float2 d)
{
    float2 e = b - a;
    float2 f = d - a;
    float2 g = a - b + c - d;
    float2 h = p - a;
        
    float k2 = cross(g, f);
    float k1 = cross(e, f) + cross(h, g);
    float k0 = cross(h, e);
    
    float w = k1 * k1 - 4.0 * k0 * k2;
    
    if (w < 0.0) 
        return float2(-1.0, -1.0); 

    w = sqrt(w); 

    float v1 = (-k1 - w) / (2.0 * k2); float v2 = (-k1 + w) / (2.0 * k2); float u1 = (h.x - f.x * v1) / (e.x + g.x * v1); float u2 = (h.x - f.x * v2) / (e.x + g.x * v2);
    bool b1 = v1 > 0.0 && v1 < 1.0 && u1 > 0.0 && u1 < 1.0; 
    bool b2 = v2 > 0.0 && v2 < 1.0 && u2 > 0.0 && u2 < 1.0;
    
    float2 res = float2(-1.0, -1.0);

    if (b1 && !b2)
        res = float2(u1, v1);

    if (!b1 && b2)
        res = float2(u2, v2);
    
    return res;
}

float4 PixelShaderFunction(VertexShaderOutput input) : COLOR0
{
    float2 uv = invBilinear(input.Pos, input.P00, input.P10, input.P11, input.P01);
    return tex2D(TextureSampler, uv);
}

technique Technique1
{
    pass Pass1
    {
        VertexShader = compile vs_2_0 VertexShaderFunction();
        PixelShader = compile ps_2_0 PixelShaderFunction();
    }
}

BilinearTrail

Viola! Textures line up along the seams. Now imagine there’s lots of those quads and map a nice texture to it for lovely trail effects.

I hope this post saves someone all the grief I’ve gone through recently 🙂

References
http://www.bitlush.com/posts/arbitrary-quadrilaterals-in-opengl-es-2-0
http://www.cs.cmu.edu/~ph/texfund/texfund.pdf
https://www.shadertoy.com/view/lsBSDm#
http://www.iquilezles.org/www/articles/ibilinear/ibilinear.htm

Leave a Reply