Experimental code to generate a simple polygon based terrain in the Camera view. Code uses AndEngine and the Box2D AndEngine extension.

terrainAttempt.java

/** 
 * Creates a top layer to the cave.. for now simply camera wide and height.
 * It is built from trapezoids, so there will be no issue with convexity.
 */
private void createTerrain(final PhysicsWorld pPhysicsWorld, 
					IEntity attachTo, final Random rand) {
	
	// we'll use this multiple times so let's save a reference here
	VertexBufferObjectManager vboMan = this.getVertexBufferObjectManager();
	
	// some setup
	final float stepSize = 50;
	float dYTop = 0;
	float dYBot = 0;
	
	final int numPoints = (int) Math.ceil(CAMERA_WIDTH / stepSize) + 1;
	
	// generating the sequence of y values that defines the top and bottom terrains
	float[] topTerrain = new float[numPoints];
	float[] botTerrain = new float[numPoints];
	topTerrain[0] = 50;
	botTerrain[0] = CAMERA_HEIGHT - 100;
	for (int i = 1; i < numPoints; ++i) {
		dYTop += (rand.nextFloat()-0.5)*30;
		topTerrain[i] = topTerrain[i-1]+dYTop;
		if (topTerrain[i] < 5) {
			topTerrain[i] = 5.0f;
			dYTop = 0;
		}
		
		dYBot += (rand.nextFloat()-0.5)*30;
		botTerrain[i] = botTerrain[i-1]+dYBot;
		if (botTerrain[i] > CAMERA_HEIGHT - 5) {
			botTerrain[i] = CAMERA_HEIGHT - 5.0f;
			dYBot = 0;
		}
	}
	
	// create the graphics for the top and the bottom
	float colGreen = Color.GREEN_ABGR_PACKED_FLOAT;
	/* we use a trianglestrip with this ordering
		1	3	5
			4
		2
				6
	(the example is for the top)
	*/
	// each point has x,y,color, there are numPoints * 2 points
	float[] topPointData = new float[numPoints * 2 * 3]; 
	float[] botPointData = new float[numPoints * 2 * 3];
	for (int i = 0; i < numPoints; ++i) {
		// top point
		topPointData[i*6] = i*stepSize;
		topPointData[i*6+1] = 0;
		topPointData[i*6+2] = colGreen;
		// bottom point
		topPointData[i*6+3] = i*stepSize;
		topPointData[i*6+4] = topTerrain[i];
		topPointData[i*6+5] = colGreen;
		
		// bottom point
		botPointData[i*6] = i*stepSize;
		botPointData[i*6+1] = CAMERA_HEIGHT;
		botPointData[i*6+2] = colGreen;
		// top point
		botPointData[i*6+3] = i*stepSize;
		botPointData[i*6+4] = botTerrain[i];
		botPointData[i*6+5] = colGreen;
		
	}
	final Mesh topGround = new Mesh(0, 0, topPointData, numPoints * 2, 
			DrawMode.TRIANGLE_STRIP, vboMan, DrawType.STATIC);
	final Mesh botGround = new Mesh(0, 0, botPointData, numPoints * 2, 
			DrawMode.TRIANGLE_STRIP, vboMan, DrawType.STATIC);
	attachTo.attachChild(topGround);
	attachTo.attachChild(botGround);
	
	
	// now we create the needed trapezoids (it would be more efficient to do 
	// this in the previous step, but this way it's separated spatially)
	for (int i = 1; i < numPoints; ++i) {
		// a bounding box so that we have something to pass to Box2D
		// the only solution I've seen used this..
		final float topHeight = Math.max(topTerrain[i-1], topTerrain[i]);
		final float botHeight = CAMERA_HEIGHT - 
					Math.min(botTerrain[i-1], botTerrain[i]);
		
		final float halfWidth = stepSize / 2 / PIXEL_TO_METER_RATIO_DEFAULT;
		final float tHalfHeight = topHeight / 2 / PIXEL_TO_METER_RATIO_DEFAULT;
		final float bHalfHeight = botHeight / 2 / PIXEL_TO_METER_RATIO_DEFAULT;
		final Rectangle topPolyBoundingBox = new Rectangle(
				(i-1)*stepSize, 1, stepSize, topHeight, vboMan);
		final Retangle botPolyBoundingBox = new Rectangle(
			(i-1)*stepSize, CAMERA_HEIGHT-botHeight-1, stepSize, botHeight, 
			vboMan);
		
		// needs to be relative to the center, in meters
		final Vector2[] topVertices = {
			new Vector2(-halfWidth, -tHalfHeight),
			new Vector2(halfWidth, -tHalfHeight),
			new Vector2(halfWidth, 
				(topTerrain[i] / PIXEL_TO_METER_RATIO_DEFAULT) - tHalfHeight),
			new Vector2(-halfWidth, 
				(topTerrain[i-1] /  PIXEL_TO_METER_RATIO_DEFAULT) - tHalfHeight),
		};
		final Vector2[] botVertices = {
			new Vector2(-halfWidth, bHalfHeight),
			new Vector2(-halfWidth, bHalfHeight +
				((-CAMERA_HEIGHT+botTerrain[i-1]) /  PIXEL_TO_METER_RATIO_DEFAULT)),
			new Vector2(halfWidth, bHalfHeight +
				((-CAMERA_HEIGHT+botTerrain[i]) /  PIXEL_TO_METER_RATIO_DEFAULT)),
			new Vector2(halfWidth, bHalfHeight),
		};
		
//		System.out.println("BotTrapezoid:");
//		for (Vector2 vec : botVertices) { System.out.println(vec); }
		
		PhysicsFactory.createPolygonBody(pPhysicsWorld, topPolyBoundingBox, 
				topVertices, BodyType.StaticBody, 
				PhysicsFactory.createFixtureDef(0, 0.5f, 0.5f));
		PhysicsFactory.createPolygonBody(pPhysicsWorld, botPolyBoundingBox, 
				botVertices, BodyType.StaticBody, 
				PhysicsFactory.createFixtureDef(0, 0.5f, 0.5f));
	}	
}