next »

[mucaho]

Hi

This is advanced stuff. If you are new to lighting and shadows chances are you wont understand much. Dont be discouraged. There are plenty of good tutorials out there.
For starters: http://forums.tigsource.com/index.php?topic=8803.0 (thats a shadow volume technique)

Im going to introduce a method for creating shadows on TileMaps walls without shadowing the walls themselves. I will be using OpenGL ES 2.0 GLSL extensively. The tiles are from opengameart.org. Additonal content is from libGDX.

Test the shadows here https://www.box.com/s/m6wu6lhmxel8fgzjz0ei. Run the .jar file in the root directory.



There are 2 main techniques of creating shadows: shadow maps and shadow volumes.
ShadowMaps:
+ GPU does the work
- precision problems (more / less)
Shadow Volumes:
- CPU does some work
+ no precision problems

So lets do it with GPU and having no precision problems.
In the above linked tutorial the CPU has to calculate the shadow volume in every render step. Lets do it on the GPU instead! In addition to supplying the standard vertex attributes of the tiles, you can supply additional information which will be stored on the GPU in a static vertex buffer.
Using the complete information stored on the GPU you can draw the walls once with the shadow volume generating shader enabled (supplying the dynamically changed light source(s) each frame) and once with the shader disabled.
First you render everything else.



Then you render the shadows (data from vertex buffer + shader enabled).



Finally you render the walls (data from vertex buffer + shader disabled).



Now to implementation details.
Static geometry (like tilemaps) is loaded on the GPU in the preprocessing phase (in OpenGL you could use a static VertexBuffer): The position of every tile is calculated in world space and the correct u-v (texture) coordinates are assigned to every tile. In the  framework of my choice (libGdx) every tile is split up into two triangles:



Each triangle consists of 3 vertices of the primitive type GL_Triangles (6 vertices in total!! the vertices on the border of the triangles are duplicated!!) Texture Coordinates are supplied by my framework.
Additional attribute center:
I calculate the center of the tile and supply it with each vertex for both triangles.
Additional attribute "triangle normal":
For every triangle i supply the vector from the corner of the tile to the center. The top triangle's (BLACK) triangle normal will point from the top left corner to the center. The bottom triangle's (RED) triangle normal will point from the bottom right corner to the center.
Additional uniform(s) light source(s)
One or more (omni directional) lights ofc

In the vertex shader we can "simulate" a geometry shader now. (remember we are on OpenglES2.0). From every vertex we can calculate every other vertex using the supplied vertex attributes. We can also calculate the position relative to the quad of our current vertex (which corner the current vertex is). We can also calculate which triangle the vertex belongs to (remember the 2 vertices at the edge between RED and BLACK are duplicated).

Now that we have the location of all vertices we can calculate the edges of the tile and their normals. Following the great, linked tutorial we now know which edges we need to extrude. (only the ones facing away from the light)



The gray part represents the shadow volume. But wait, that are 2 quads. We would need 4 triangles to correctly represent 2 quads. We have only 2. What do we do?



Now thats more like it. We sacrifice a bit of precision at the back end of the shadow (which is negligible if you extrude the shadow volume out of the viewing spectrum). The shadow also overlaps half of the original geometry, so we have to render the original geometry above the shadow.
Ok, so how do we achieve that with our 2 available triangles?



Cool. But how is it done?
Every vertex does the same calculations and at the end of the calculations he is going to a predefined position. Lets say the current vertex is the top left corner (black) in our inital triangle. After all calculations TOP_LEFT BLACK goes to lets say the RIGHT SHADOW-PROJECTED CORNER. Thats it actually


Extras:
Ok that was considering one light. What do we do if we have more?
I just need visibility for my 2d game so i didnt test it with multiple lights. I think:
You draw the geometry for every light. You use the stencil buffer in order to count the amount of overlapping shadow volumes. If the count == amount of shadow volumes you are indeed in shadow. If its less, the point is in light.
What about uni-directional and/or spotlights?
Well if you mean sun light, you can precalculate the shadow volume up front - photoshop- (if the sun position doesnt change). Spotlights have a direction and cone so you should find out at each quad if its affected.
Why do you have 100fps only in the screenshots?
Im on netbook with graphic chip and virtual video memory on power savings mode
Well i did not test the performance per se. Should have good performance as far as my theory checks out.
What about other tiles (like hexagonal)? What about other 2D geometry? But this surely wont work in 3D, or would it?
Remember we just need the necessary information to compute all points of the geometry from one point. The more complex the geometry gets, the harder it gets to compute and the more additional information you have to supply.
In addition to your complex geometry, you can have a simpler version of the geometry (simple one for rendering shadows and complex one for rendering the geometry the usual way).
Lets consider hexagonal tiles. Chances are they will be composed of 6 triangles. You supply the center of the hexagon for all triangles. You supply one of the 6 possible hexagonal possitions for each triangle. You supply the distance from the center to a corner. There you go, now you can compute all points and you can determine which point you are exactly.

Well thats all daisies and roses, i want to see code
here you go. vert shader. no if/else. not even tenary operator. only static for-loops (unrolled by compiler).

Code:

#define ARRAY_LENGTH 4
#define TRIANGLE_AMOUNT 2

attribute vec2 a_position;
attribute vec2 a_center;
attribute vec2 a_normal;

uniform mat4 u_projectionViewMatrix;
uniform vec2 u_lightPosition;

varying vec4 v_color;


const mat2 perpendicularMatrix = mat2(	0.0,	-1.0,
										1.0,	0.0);

const vec2 VEC2_ZERO = vec2 (-1000.0, -1000.0);
										
const uint TOP_LEFT = 0u;
const uint BOTTOM_LEFT = 1u;
const uint BOTTOM_RIGHT = 2u;
const uint TOP_RIGHT = 3u;

const uint TRIANGLE_TOP = 0u;
const uint TRIANGLE_BOTTOM = 1u;

const float POSITIVE = 1.0;
const float NEGATIVE = -1.0;

struct Data {
	mat4 matrix;
	vec2 center;
	vec2 light;
	vec2 normal;
	vec2 position;
};

struct TriangleMeta {
	uint oppositeID;
	uint aID;
	uint bID;
	uint cID;
};

struct Point {
	uint ID;
	vec2 value;
};

struct EdgeMeta {
	uint startID;
	uint endID;
	bool castsShadow;
};

struct Distance {
	uint ID;
	float value;
};


vec2 projectionAxis (in vec2 center, in vec2 light) {
	//center-to-light
	vec2 tmp = light - center;
	
	//perpendicular to center-to-light
	tmp = perpendicularMatrix * tmp;
	
	//normalize & return
	return normalize (tmp);
}

//true for max, false for min
Distance computeMaxMin (in Distance[ARRAY_LENGTH] distances, bool findMax) {
	Distance result;
	
	float maxD = distances[0].value;
	for (int i=1; i<ARRAY_LENGTH; ++i) {
		maxD = maxD - float(findMax) * maxD
					+ float(findMax) * max(maxD, distances[i].value);
		maxD = maxD - float(!findMax) * maxD
					+ float(!findMax) * min(maxD, distances[i].value);
	}
	result.value = maxD;
	
	//find the index of max value, when found set max to a negative value 
	uint index = uint(0);
	for (int i=0; i<ARRAY_LENGTH; ++i) {
		index += distances[i].ID * uint(maxD == distances[i].value);
		maxD = maxD - maxD * float(maxD == distances[i].value)
					- float(maxD == distances[i].value);
	}
	result.ID = index;

	return result;
}



uint determineID (in vec2 point, in Point[ARRAY_LENGTH] points) {
	uint ID = 0u;
	for (int i=0; i<ARRAY_LENGTH; ++i) {
		ID += points[i].ID * uint(all(equal(point, points[i].value)));
	}
	
	return ID;
}

//sign: 1.0 for normal normal, -1.0 for reverse
uint determineOppositeID(in Data data, in Point[ARRAY_LENGTH] points, in float sign) {
	//calculate opposite (not a vertex of this triangle)
	vec2 opposite = vec2 (data.center + sign * data.normal);
	uint ID = determineID(opposite, points);
	return ID;
}

uint determineTriangleID(in Data data) {	
	//calculate if we are TOP or BOTTOM triangle
	vec2 axisDirect = normalize (data.light - data.center);
	vec2 axisPerp  = projectionAxis(data.center, data.light);
	vec2 normal = normalize (data.normal);
	
	float directAngle = dot(axisDirect, normal);
	float perpAngle = dot(axisPerp, normal);
	
	uint ID = 0u;
	//top is top half
	ID += TRIANGLE_TOP * uint(sign(directAngle) > 0.0);
	//bottom is bottom half
	ID += TRIANGLE_BOTTOM * uint(sign(directAngle) < 0.0);
	//top is left half
	ID += TRIANGLE_TOP * uint(sign(directAngle) == 0.0) * uint(sign(perpAngle) < 0.0);
	//bottom is right half
	ID += TRIANGLE_BOTTOM * uint(sign(directAngle) == 0.0) * uint(sign(perpAngle) > 0.0);

	return ID;
}

uint determineTrianglePointID(in Point[ARRAY_LENGTH] points) {
	uint ID = 0u;
	
	for (int i=0; i<ARRAY_LENGTH; ++i) {
		ID = ID
			- ID 			* uint(any(notEqual(points[i].value, VEC2_ZERO)))
			+ points[i].ID 	* uint(any(notEqual(points[i].value, VEC2_ZERO)));
	}
	
	return ID;
}


TriangleMeta computeTriangle(in Data data, in Point[ARRAY_LENGTH] points, in float oppositeSign) {
	TriangleMeta meta;
	
	//determine opposite ID
	meta.oppositeID = determineOppositeID(data, points, oppositeSign);
	points[meta.oppositeID].value = VEC2_ZERO;
	
	//determine rest IDs
	meta.aID = determineTrianglePointID (points);
	points[meta.aID].value = VEC2_ZERO;
	meta.bID = determineTrianglePointID (points);
	points[meta.bID].value = VEC2_ZERO;
	meta.cID = determineTrianglePointID (points);
	points[meta.cID].value = VEC2_ZERO;
	
	return meta;
}


Distance[ARRAY_LENGTH] computeDistances (in vec2 light, in Point[ARRAY_LENGTH] points) {
	//compute distances
	Distance[ARRAY_LENGTH] distances;
	for (int i=0; i<ARRAY_LENGTH; ++i) {
		distances[i].value = distance( points[i].value, light );
		distances[i].ID = points[i].ID;
	}

	return distances;
}

Point[ARRAY_LENGTH] computeEdgePoints(in Point[ARRAY_LENGTH] points, in EdgeMeta[ARRAY_LENGTH] edges) {
	Point[ARRAY_LENGTH] validPoints;
	for (int i=0; i<ARRAY_LENGTH; ++i) {
		validPoints[i].ID = points[i].ID;
		validPoints[i].value = VEC2_ZERO;
	}
	for (int i=0; i<ARRAY_LENGTH; ++i) {
		validPoints[edges[i].startID].value = validPoints[edges[i].startID].value
												- validPoints[edges[i].startID].value * float(edges[i].castsShadow)
												+ points[edges[i].startID].value * float(edges[i].castsShadow);
												
		validPoints[edges[i].endID].value = validPoints[edges[i].endID].value
												- validPoints[edges[i].endID].value * float(edges[i].castsShadow)
												+ points[edges[i].endID].value * float(edges[i].castsShadow);
	}
	
	return validPoints;
}



Point[ARRAY_LENGTH] computeShadowVolume(in Data data, in Point[ARRAY_LENGTH] points, in EdgeMeta[ARRAY_LENGTH] edges) {
	Point[ARRAY_LENGTH] validPoints = computeEdgePoints(points, edges);
	Distance[ARRAY_LENGTH] distances = computeDistances(data.light, validPoints);

	uint aProjectionID = 0u;
	uint bProjectionID = 0u;
	Distance minDistance;
	
	minDistance = computeMaxMin(distances, false);
	aProjectionID = minDistance.ID;
		distances[minDistance.ID].value = length(VEC2_ZERO);
	
	minDistance = computeMaxMin(distances, false);
	bProjectionID = minDistance.ID;
	
	Point[ARRAY_LENGTH] outs;
	outs[BOTTOM_LEFT].ID = BOTTOM_LEFT;
	outs[BOTTOM_LEFT].value = points[aProjectionID].value;
	outs[BOTTOM_RIGHT].ID = BOTTOM_RIGHT;
	outs[BOTTOM_RIGHT].value = points[bProjectionID].value;
	outs[TOP_LEFT].ID = TOP_LEFT;
	outs[TOP_LEFT].value = outs[BOTTOM_LEFT].value + (outs[BOTTOM_LEFT].value - data.light) * 100.0;
	outs[TOP_RIGHT].ID = TOP_RIGHT;
	outs[TOP_RIGHT].value = outs[BOTTOM_RIGHT].value + (outs[BOTTOM_RIGHT].value - data.light) * 100.0;
	
	return outs;
}

EdgeMeta[ARRAY_LENGTH] computeEdges(in Point[ARRAY_LENGTH] points, in Data data) {
	EdgeMeta[ARRAY_LENGTH] edges;
	
	vec2 startToEnd;
	vec2 startToNormal;
	vec2 startToLight;
	for (int i=0; i<ARRAY_LENGTH; ++i) {
		edges[i].startID = points[i].ID;
		edges[i].endID = points[i+1].ID * uint(i+1 < ARRAY_LENGTH)
						+ points[0].ID 	* uint(i+1 == ARRAY_LENGTH);
		
		startToEnd = normalize(points[edges[i].endID].value - points[edges[i].startID].value);
		startToNormal = normalize(perpendicularMatrix * startToEnd);
		startToLight = normalize(data.light - points[edges[i].startID].value);
		
		edges[i].castsShadow = dot(startToNormal, startToLight) < 0.0;
	}
	
	return edges;
}

Point[ARRAY_LENGTH] computePoints(in Data data) {
	//translate to object space (to origin)
	data.position -= data.center;

	Point[ARRAY_LENGTH] points;
	//points of a quad in object space
	points[TOP_LEFT].ID = TOP_LEFT;
	points[TOP_LEFT].value = vec2(	-abs(data.position.x),	abs(data.position.y) );	
	points[TOP_RIGHT].ID = TOP_RIGHT;
	points[TOP_RIGHT].value = vec2(	abs(data.position.x),	abs(data.position.y) );
	points[BOTTOM_LEFT].ID = BOTTOM_LEFT;
	points[BOTTOM_LEFT].value = vec2(	-abs(data.position.x),	-abs(data.position.y) );
	points[BOTTOM_RIGHT].ID = BOTTOM_RIGHT;
	points[BOTTOM_RIGHT].value = vec2(	abs(data.position.x),	-abs(data.position.y) );
	
	//translate back to world space (from origin)
	//data.position += data.center;
	for (int i=0; i<ARRAY_LENGTH; i++) {
		points[i].value += data.center;
	}
	
	return points;
}

vec2 projectPosition(vec2 position, Point[ARRAY_LENGTH] shadowPoints, 
					uint ownID, uint triangleID, TriangleMeta[TRIANGLE_AMOUNT] meta) {
	 
	 position = 	shadowPoints[BOTTOM_LEFT].value * float(ownID == meta[TRIANGLE_TOP].aID) * float(triangleID == TRIANGLE_TOP)
					+ shadowPoints[BOTTOM_RIGHT].value * float(ownID == meta[TRIANGLE_TOP].bID) * float(triangleID == TRIANGLE_TOP)
					+ shadowPoints[TOP_RIGHT].value *  float(ownID == meta[TRIANGLE_TOP].cID) * float(triangleID == TRIANGLE_TOP)
					
					+ shadowPoints[BOTTOM_LEFT].value *  float(ownID == meta[TRIANGLE_BOTTOM].aID) * float(triangleID == TRIANGLE_BOTTOM)
					+ shadowPoints[TOP_LEFT].value * float(ownID == meta[TRIANGLE_BOTTOM].bID) * float(triangleID == TRIANGLE_BOTTOM)
					+ shadowPoints[TOP_RIGHT].value * float(ownID == meta[TRIANGLE_BOTTOM].cID) * float(triangleID == TRIANGLE_BOTTOM);
					
	return position;
}

void main() {
	v_color = vec4(0.0, 0.0, 0.0, 1.0);
	
	//init
	Data data;
	data.matrix = u_projectionViewMatrix;
	data.center = a_center;
	data.light = u_lightPosition;
	data.normal = a_normal;
	data.position = a_position;
	
	//compute Points
	Point[ARRAY_LENGTH] points = computePoints(data);
	
	//compute Edges
	EdgeMeta[ARRAY_LENGTH] edges = computeEdges(points, data);
	
	//compute Shadow Points
	Point[ARRAY_LENGTH] shadowPoints = computeShadowVolume(data, points, edges);
		
	//determine own ID
	uint ownID = determineID(data.position, points);
	
	//determine triangle ID
	uint triangleID = determineTriangleID(data);
	
	//compute triangles
	TriangleMeta[TRIANGLE_AMOUNT] meta;
	float sign;
		sign = float(triangleID == TRIANGLE_TOP)
			- float(triangleID != TRIANGLE_TOP);
	meta[TRIANGLE_TOP] = computeTriangle(data, points, sign);
		sign = float(triangleID == TRIANGLE_BOTTOM)
			- float(triangleID != TRIANGLE_BOTTOM);
	meta[TRIANGLE_BOTTOM] = computeTriangle(data, points, sign);
				
				
	//apply shadow projections
	data.position = projectPosition(data.position, shadowPoints, ownID, triangleID, meta);
	
	
	gl_Position =  data.matrix * vec4(data.position, 0.0, 1.0);
	//gl_Position.z += 0.0625;
}

frag

Code:

#ifdef GL_ES
precision mediump float;
#endif

varying vec4 v_color;


void main() {
	gl_FragColor = v_color;
}

[kamac]

That's really cool. Althrough, I couldn't find easy shadow mapping tutorial for 3D stuff... Maybe you could try creating one, too? (In all such tutorials that I've found, people speak only theoritically, without giving proper, full examples - aka. no details)

Anyhow, good stuff

[mucaho]

Tbh my tutorial isnt that detailed either, and also much theoretical. I thought about making it comprehensive, but i would need to write a book about that I can link you any resources i used to teach myself though and/or answer questions to what i know.

I also noticed many "tutorials" are theoretical and dont walk you through the code. I found two excellent ones for Shadow Mapping (with pictures and code explanation):
http://www.opengl-tutorial.org/intermediate-tutorials/tutorial-16-shadow-mapping/
http://www.fabiensanglard.net/shadowmapping/index.php

These are basic ones, if you are interested check up on the additional stuff besides basic shadow mapping (partly linked in the tutorials above). First of all know what version of OpenGL you will be using, as there is a BIG difference what you can achieve which each version.

[mucaho]

I added a simple test jar to test the shadows.

https://www.box.com/s/m6wu6lhmxel8fgzjz0ei