Category Archives: Math

Position Reconstruction

28 Replies

There are many occasions when the fragment position in world space needs to be reconstructed from a texture holding the scene depth (depth texture). One example of use is in deferred rendering when trying to decrease memory usage by not saving the position but instead only the depth. This will result in one channel of data, instead of three channels needed when saving the whole position.

 

Viewspace scene depth

There are different ways to save the depth. The most popular are view space depth and screen space depth. Saving depth in view space instead of screen space gives two advantages. It’s faster, and it gives better precision because it’s linear in view space.

This is how screen space depth can be rendered in HLSL:

struct VS_OUTPUT
{
   float4 Pos: POSITION;
   float4 posInProjectedSpace: TEXCOORD0;
};
 
// vertex shader
VS_OUTPUT vs_main( float4 Pos: POSITION )
{
   VS_OUTPUT Out = (VS_OUTPUT) 0;
   Out.Pos = mul(Pos,matWorldViewProjection);
   Out.posInProjectedSpace = Out.Pos;
   return Out;
}
 
// pixel shader
float4 ps_main( VS_OUTPUT Input ) : COLOR
{
   float depth = Input.posInProjectedSpace.z / Input.posInProjectedSpace.w;
   return depth;
}

The HLSL pixel shader below shows how the position can be reconstructed from the depth map stored with the code above. Although this is one of the slowest ways of doing position reconstruction since it requires a matrix multiplication.

float4 ps_main(float2 vPos : VPOS;) : COLOR0
{
   float depth = tex2D(depthTexture,vPos*fInverseViewportDimensions + fInverseViewportDimensions*0.5).r;
 
   // scale it to -1..1 (screen coordinates)
   float2 projectedXY = vPos*fInverseViewportDimensions*2-1;
   projectedXY.y = -projectedXY.y;
 
   // create the position in screen space
   float4 pos = float4(projectedXY,depth,1);
 
   // transform position into world space by multiplication with the inverse view projection matrix
   pos = mul(pos,matViewProjectionInverse); 
 
   // make it homogeneous
   pos /= pos.w; // result will be (x,y,z,1) in world space
 
   return pos; // for now, just render it out
}

To reconstruct depth from view space, a ray from the camera position to the frustum far plane is needed. For a full screen quad, this ray can be precalculated for the four corners and passed to the shader. This is how the computer game Crysis did it [1] . But for arbitrary geometry, as needed in deferred rendering, the ray must be calculated in the shaders [2] .

[1] “Finding next gen: CryEngine 2″
http://ati.amd.com/developer/gdc/2007/mittring-finding_nextgen_cryengine2(siggraph07).pdf

[2] “Reconstructing Position From Depth, Continued”
http://mynameismjp.wordpress.com/2009/05/05/reconstructing-position-from-depth-continued/

Please share:
  • Print this article!
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • Current
  • LinkedIn
  • Live
  • MySpace
  • Netvibes
  • StumbleUpon
  • Twitter
  • Reddit
  • Technorati
  • Yahoo! Bookmarks

Grid Traversal

4 Replies

Probably the best and most famous grid traversal algorithm uses a simple loop that for each iteration takes one more step in the grid. It works in both 2D and 3D.

Java code:

   public boolean isFreePath(float startX, float startZ, float endX, float endZ)
   {
      // calculate the direction of the ray (linear algebra)
      dirX = (endX - startX);
      dirY = (endZ - startZ);
      float length = (float) Math.sqrt(dirX * dirX + dirY * dirY);
      dirX /= length; // normalize the direction vector
      dirY /= length;
 
      tDeltaX = MAP_RESOLUTION / Math.abs(dirX); // how far we must move in the ray direction before we encounter a new voxel in x-direction
      tDeltaY = MAP_RESOLUTION / Math.abs(dirY); // same but y-direction
 
      // start voxel coordinates
      x = (int) (worldCoordToMapCoord(startX));  // use your transformer function here
      y = (int) (worldCoordToMapCoord(startZ));
 
      // end voxel coordinates
      endX1 = (int) (worldCoordToMapCoord(endX));
      endY1 = (int) (worldCoordToMapCoord(endZ));
 
      // decide which direction to start walking in
      stepX = (int) Math.signum(dirX);
      stepY = (int) Math.signum(dirY);
 
      float tMaxX, tMaxY;
      // calculate distance to first intersection in the voxel we start from
      if(dirX < 0)
      {
         tMaxX = (mapToWorld(x)-startX) / dirX;
      }else
      {
         tMaxX = (mapToWorld(x+1)-startX) / dirX;
      }
 
      if(dirY < 0)
      {
         tMaxY = (mapToWorld(y)-startY) / dirY;
      }else
      {
         tMaxY = (mapToWorld(y+1)-startY) / dirY;
      }
 
      // check if first is occupied
      if (isMapPositionOccupied(x, y)) // use your function here
         return false;
 
      boolean reachedX = false, reachedY = false;
 
      while (true)
      {
         if (tMaxX < tMaxY)
         {
            tMaxX += tDeltaX;
            x += stepX;
         } else
         {
            tMaxY += tDeltaY;
            y += stepY;
         }
 
         if (stepX > 0.0f)
         {
            if (x >= endX1)
            {
               reachedX = true;
            }
         } else if (x <= endX1)
         {
            reachedX = true;
         }
 
         if (stepY > 0.0f)
         {
            if (y >= endY1)
            {
               reachedY = true;
            }
         } else if (y <= endY1)
         {
            reachedY = true;
         }
 
         if (isMapPositionOccupied(x, y))
         {
            return false;
         }
 
         if (reachedX && reachedY)
         {
            break;
         }
      }
 
      return true;
   }

Here’s an applet showing it in action.
The white tiles are free, the gray tiles are blocking. The ray starts at the green dot and ends at the red dot. The gray spheres are the visited grid sections. Use leftclick to position the green dot and the right button to position the red dot.
 


Hi There


Link to paper:
http://www.flipcode.com/archives/A%20faster%20voxel%20traversal%20algorithm%20for%20ray%20tracing.pdf

Some discussion on GameDev:
http://www.gamedev.net/community/forums/topic.asp?topic_id=385303

Implementations:
http://www.clockworkcoders.com/oglsl/rt/gpurt3.htm
http://www.devmaster.net/articles/raytracing_series/part4.php

Full source of the applet:

import java.awt.*;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.event.MouseMotionListener;
import java.applet.*;
 
public class GTApplet extends Applet implements MouseListener,
		MouseMotionListener
{
	enum mapNotations
	{
		FREE, OCCUPIED, BOOKED, RESERVED
	};
 
	private static final int GRID_PAINT_SIZE = 50;
 
	private static final int MAP_RESOLUTION = GRID_PAINT_SIZE;
 
	private static final int MAP_SIZE = 4 * 2;
 
	private final mapNotations[][] map = new mapNotations[MAP_SIZE][MAP_SIZE];
 
	private final int[][] markedMap = new int[MAP_SIZE][MAP_SIZE];
 
	// Specify variables that will be needed everywhere, anytime here
	// The font variable
	Font bigFont, smallFont, smallestFont;
 
	Color bgColor;
	Color gridLineColor;
	Color gridOccupiedColor;
	Color startColor;
	Color endColor;
	Color helperLineColor;
	Color markerColor;
	Color textColor;
 
	int startX = 50, startY = 50, endX = 50, endY = 50;
 
	int markerDiameter = 6;
	int mapMarkerDiameter = 26;
 
	boolean isFreePath = false;
 
	public void init()
	{
		// init the map
		for (int x = 0; x < MAP_SIZE; x++)
		{
			for (int y = 0; y < MAP_SIZE; y++) 			{ 				if (Math.random() > 0.2f)
				{
					map[x][y] = mapNotations.FREE;
				} else
				{
					map[x][y] = mapNotations.OCCUPIED;
				}
			}
		}
 
		bigFont = new Font("Arial", Font.BOLD, 16);
		bigFont = new Font("Arial", Font.BOLD, 12);
		smallestFont = new Font("Calibri", Font.PLAIN, 10);
 
		gridLineColor = Color.DARK_GRAY;
		gridOccupiedColor = Color.LIGHT_GRAY;
		startColor = Color.green;
		endColor = Color.red;
		helperLineColor = Color.black;
		markerColor = Color.gray;
		textColor = Color.DARK_GRAY;
 
		bgColor = new Color(230, 231, 232);
 
		setBackground(bgColor);
 
		addMouseListener(this);
		addMouseMotionListener(this);
 
	}
 
	public void mouseEntered(MouseEvent e)
	{
		// called when the pointer enters the applet's rectangular area
	}
 
	public void mouseExited(MouseEvent e)
	{
		// called when the pointer leaves the applet's rectangular area
	}
 
	public void mouseClicked(MouseEvent e)
	{
		// called after a press and release of a mouse button
		// with no motion in between
		// (If the user presses, drags, and then releases, there will be
		// no click event generated.)
	}
 
	public void mousePressed(MouseEvent e)
	{ // called after a button is pressed down
		if (e.getButton() == MouseEvent.BUTTON1)
		{
			startX = e.getX();
			startY = e.getY();
		} else
		{
			endX = e.getX();
			endY = e.getY();
		}
 
		resetMarkedMap();
		isFreePath = isFreePath(startX, startY, endX, endY);
 
		repaint();
		// "Consume" the event so it won't be processed in the
		// default manner by the source which generated it.
		e.consume();
	}
 
	public void mouseReleased(MouseEvent e)
	{ // called after a button is released
	//        repaint();
		e.consume();
	}
 
	public void mouseMoved(MouseEvent e)
	{ // called during motion when no buttons are down
	//        repaint();
		e.consume();
	}
 
	public void mouseDragged(MouseEvent e)
	{ // called during motion with buttons down
	//        repaint();
		e.consume();
	}
 
	public void stop()
	{
	}
 
	// just some simple and rude drawing
	public void paint(Graphics g)
	{
		g.setColor(gridLineColor);
		for (int x = 0; x < MAP_SIZE + 1; x++)
			g.drawLine(x * GRID_PAINT_SIZE, 0, x * GRID_PAINT_SIZE, MAP_SIZE
					* GRID_PAINT_SIZE);
 
		for (int y = 0; y < MAP_SIZE + 1; y++)
			g.drawLine(0, y * GRID_PAINT_SIZE, MAP_SIZE * GRID_PAINT_SIZE, y
					* GRID_PAINT_SIZE);
 
		g.setColor(gridOccupiedColor);
		for (int x = 0; x < MAP_SIZE; x++)
		{
			for (int y = 0; y < MAP_SIZE; y++)
			{
				if (map[x][y] == mapNotations.OCCUPIED)
				{
					g.fillRect(x * GRID_PAINT_SIZE + 1,
							y * GRID_PAINT_SIZE + 1, GRID_PAINT_SIZE - 1,
							GRID_PAINT_SIZE - 1);
				}
			}
		}
 
		g.setColor(textColor);
 
		g.setFont(smallestFont);
 
		for (int x = 0; x < MAP_SIZE; x++)
		{
			for (int y = 0; y < MAP_SIZE; y++)
			{
				g.drawString("(" + x + "," + y + ")", x * GRID_PAINT_SIZE + 2,
						y * GRID_PAINT_SIZE + 10);
			}
		}
 
		g.setFont(bigFont);
		g.drawString("Start: (" + startX + "," + startY + ")", 16, MAP_SIZE
				* GRID_PAINT_SIZE + 30 + 10);
		g.drawString("End: (" + endX + "," + endY + ")", 16, MAP_SIZE
				* GRID_PAINT_SIZE + 48 + 10);
		g.drawString("Is free path: " + isFreePath, 16, MAP_SIZE
				* GRID_PAINT_SIZE + 48 + 18 + 10);
		g.setFont(smallFont);
		g.drawString("Start (map coords): (" + sx + "," + sy + ")", 16,
				MAP_SIZE * GRID_PAINT_SIZE + 10 + 48 + 18 + 18 + 0 * 14);
		g.drawString("End (map coords): (" + endX1 + "," + endY1 + ")", 16,
				MAP_SIZE * GRID_PAINT_SIZE + 10 + 48 + 18 + 18 + 1 * 14);
		g.drawString("Step (map coords): (" + stepX + "," + stepY + ")", 16,
				MAP_SIZE * GRID_PAINT_SIZE + 10 + 48 + 18 + 18 + 2 * 14);
		g.drawString("Dir: (" + dirX + "," + dirY + ")", 16, MAP_SIZE
				* GRID_PAINT_SIZE + 10 + 48 + 18 + 18 + 3 * 14);
		g.drawString("tDelta: (" + tDeltaX + "," + tDeltaY + ")", 16, MAP_SIZE
				* GRID_PAINT_SIZE + 10 + 48 + 18 + 18 + 4 * 14);
		g.drawString("sTMax: (" + sTMaxX + "," + sTMaxY + ")", 16, MAP_SIZE
				* GRID_PAINT_SIZE + 10 + 48 + 18 + 18 + 5 * 14);
 
		g.setColor(markerColor);
 
		for (int x = 0; x < MAP_SIZE; x++)
		{
			for (int y = 0; y < MAP_SIZE; y++)
			{
				if (markedMap[x][y] == 1)
				{
					g.fillOval(x * GRID_PAINT_SIZE - mapMarkerDiameter / 2
							+ GRID_PAINT_SIZE / 2, y * GRID_PAINT_SIZE
							- mapMarkerDiameter / 2 + GRID_PAINT_SIZE / 2,
							mapMarkerDiameter, mapMarkerDiameter);
				}
			}
		}
 
		g.setColor(startColor);
		// draw start and end markers
		g.drawOval(startX - markerDiameter / 2, startY - markerDiameter / 2,
				markerDiameter, markerDiameter);
 
		g.setColor(endColor);
		// draw start and end markers
		g.drawOval(endX - markerDiameter / 2, endY - markerDiameter / 2,
				markerDiameter, markerDiameter);
 
		g.setColor(helperLineColor);
		g.drawLine(startX, startY, endX, endY);
	}
 
	public void resetMarkedMap()
	{
		for (int x = 0; x < MAP_SIZE; x++)
		{
			for (int y = 0; y < MAP_SIZE; y++)
			{
				markedMap[x][y] = 0;
			}
		}
	}
 
	int sx, sy, x, y, endX1, endY1, stepX, stepY;
	float tDeltaX, tDeltaY;
	float dirX, dirY;
	float sTMaxX, sTMaxY;
 
	public boolean isFreePath(float startX, float startZ, float endX, float endZ)
	{
		// calculate the direction of the ray (linear algebra)
		dirX = (endX - startX);
		dirY = (endZ - startZ);
		float length = (float) Math.sqrt(dirX * dirX + dirY * dirY);
		dirX /= length; // normalize the direction vector
		dirY /= length;
 
		tDeltaX = MAP_RESOLUTION / Math.abs(dirX); // how far we must move in the ray direction before we encounter a new voxel in x-direction
		tDeltaY = MAP_RESOLUTION / Math.abs(dirY); // same but y-direction
 
		// start voxel coordinates
		sx = (int) (worldCoordToMapCoord(startX));  // use your transformer function here
		sy = (int) (worldCoordToMapCoord(startZ));
 
		// end voxel coordinates
		endX1 = (int) (worldCoordToMapCoord(endX));
		endY1 = (int) (worldCoordToMapCoord(endZ));
 
		x = sx;
		y = sy;
 
		// decide which direction to start walking in
		stepX = (int) Math.signum(dirX);
		stepY = (int) Math.signum(dirY);
 
		float tMaxX, tMaxY;
		// calculate distance to first intersection in the voxel we start from
		if(dirX < 0)
		{
			tMaxX = (mapToWorld(x)-startX) / dirX;
		}else
		{
			tMaxX = (mapToWorld(x+1)-startX) / dirX;
		}
 
		if(dirY < 0)
		{
			tMaxY = (mapToWorld(y)-startY) / dirY;
		}else
		{
			tMaxY = (mapToWorld(y+1)-startY) / dirY;
		}
 
		sTMaxX = tMaxX;
		sTMaxY = tMaxY;
 
		// check if first is occupied
		if (isMapPositionOccupied(x, y)) // use your function here
			return false;
 
		boolean reachedX = false, reachedY = false;
 
		while (true)
		{
			if (tMaxX < tMaxY) 			{ 				tMaxX += tDeltaX; 				x += stepX; 			} else 			{ 				tMaxY += tDeltaY; 				y += stepY; 			} 			if (stepX > 0.0f)
			{
				if (x >= endX1)
				{
					reachedX = true;
				}
			} else if (x <= endX1) 			{ 				reachedX = true; 			} 			if (stepY > 0.0f)
			{
				if (y >= endY1)
				{
					reachedY = true;
				}
			} else if (y <= endY1)
			{
				reachedY = true;
			}
 
			if (isMapPositionOccupied(x, y))
			{
				return false;
			}
 
			if (reachedX && reachedY)
			{
				break;
			}
		}
 
		return true;
	}
 
	private float mapToWorld(int coord)
	{
		return coord*MAP_RESOLUTION;
	}
 
	private float worldCoordToMapCoord(float coord)
	{
		return coord / MAP_RESOLUTION;
	}
 
	private boolean isMapPositionOccupied(int x, int y)
	{
		if(x < 0 || y < 0)
			return true; 
 
		// save this for debug use
		markedMap[x][y] = 1;
 
		return map[x][y] == mapNotations.OCCUPIED;
	}
}
Please share:
  • Print this article!
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • Current
  • LinkedIn
  • Live
  • MySpace
  • Netvibes
  • StumbleUpon
  • Twitter
  • Reddit
  • Technorati
  • Yahoo! Bookmarks

Random point in circle

7 Replies

The best algorithm to generate a point in a circle is to generate a point in a square with the same width as the circle diameter and then rerun the algorithm until this random point is inside the circle. This algorithm might need to run a couple of times before finding a suitable point but will be faster than a more algorithmic solutions.

Pseudo code:

  1. Randomize a point in the square
  2. If this point is outside the circle then jump to 1
  3. Done
Please share:
  • Print this article!
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • Current
  • LinkedIn
  • Live
  • MySpace
  • Netvibes
  • StumbleUpon
  • Twitter
  • Reddit
  • Technorati
  • Yahoo! Bookmarks

Tangent Space

Leave a reply

Tangent space is (when speaking of rendering) the space built up by the vertex normal and the vertex texture coordinates often called  (u,v). This space is useful when dealing with textures with information in tangent space, for example a normal map.

The tangent space matrix can be separated in three vectors:

- The normal vector

- The tangent vector

- The bitangent vector

A detailed description of how to create the tangent vector from the u,v coordinates. (including source code)
http://www.terathon.com/code/tangent.html

More information about tangent Space (and an OpenGL implementation):
http://jerome.jouvie.free.fr/OpenGl/Lessons/Lesson8.php

Please share:
  • Print this article!
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • Current
  • LinkedIn
  • Live
  • MySpace
  • Netvibes
  • StumbleUpon
  • Twitter
  • Reddit
  • Technorati
  • Yahoo! Bookmarks