Raytracing - Tutorials?

Hey guys.
I don’t know much about raytracing other than that it’s a fairly complex technique though essential in modern game engines for advanced lighting and collision checking.
I would like to read up on raytracing in general but all the materials I found on the subject seems to be fairly advanced and I have a hard time studying them.
I would need rather simple, step-by-step explanation on the hows and whys because I hate to use something without understanding what’s going on under the hood. ::slight_smile:

If somebody can point me to a tutorial or a book where raytracing is well explained I would be very grateful. :smiley:

This gives you a fairly mathematical approach to ray-object intersections

Thank you, and sorry for the late response.
I’ll look into your link. :smiley:

There is an example of a very basic raytracer here
http://www.typescriptlang.org/Samples/#Raytracer
You could try and translate the code to Java.

I wrote a nifty little collision checking class for my java projects.

public class CollisionHelper {
	public static final float SMALL_NUM = 1.0E-008F;
	public static final int LARGE_NUM = 10000000;
	private static float[] lastTriangleData = { 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F };
	
	//p3dc_split();
	//Written by Andrew Hamilton (orange451)
	public static SplitModel model_split(D3DModel model1, int xStart, int yStart, int width, int height, int amount_cellsX, int amount_cellsY, int overlapX, int overlapY) {
		return new SplitModel(model1, xStart, yStart, width, height, amount_cellsX, amount_cellsY, overlapX, overlapY);
	}

	//p3dc_check()
	//Written by Andrew Hamilton (orange451)
	public static boolean collision_check(D3DModel model1, float x1, float y1, float z1, D3DModel model2, float x2, float y2, float z2) {
		int amtVertices = model1.getAmountVertices();
		for (int i = 0; i < amtVertices; i += 3) {
			float[] v1 = model1.getVertexAtId(i);
			float[] v2 = model1.getVertexAtId(i+1);
			float[] v3 = model1.getVertexAtId(i+2);
			v1[0] += x1;
			v1[1] += y1;
			v1[2] += z1;

			v2[0] += x1;
			v2[1] += y1;
			v2[2] += z1;

			v3[0] += x1;
			v3[1] += y1;
			v3[2] += z1;

			int amtVertices2 = model2.getAmountVertices();
			for (int ii = 0; ii < amtVertices2; ii += 3) {
				float[] v1_2 = model2.getVertexAtId(ii);
				float[] v2_2 = model2.getVertexAtId(ii+1);
				float[] v3_2 = model2.getVertexAtId(ii+2);

				v1_2[0] += x2;
				v1_2[1] += y2;
				v1_2[2] += z2;

				v2_2[0] += x2;
				v2_2[1] += y2;
				v2_2[2] += z2;

				v3_2[0] += x2;
				v3_2[1] += y2;
				v3_2[2] += z2;

				if (checkTriangleCollision(v1, v2, v3, v1_2, v2_2, v3_2)) {
					return true;
				}
			}
		}
		return false;
	}

	/*
	 Retrun all triangles hit by a ray,
	 By Andrew Hamilton (orange451)
	 
	 xRot, yRoy, zRot   = rotation of model being checked
	 x1, y1, z1         = position of model being checked
	 x2, y2, z2         = vertex of the ray
	 nx, ny, nz         = direction of the ray
	*/
	public static ArrayList<HitTriangle> collision_check_all(D3DModel model1, float xRot, float yRot, float zRot, float x1, float y1, float z1, float x2, float y2, float z2, float nx, float ny, float nz) {
		ArrayList<HitTriangle> ret = new ArrayList<HitTriangle>();
		float[] vec = { x2, y2, z2 };
		float[] dir = { nx, ny, nz };

		int amtVertices = model1.getAmountVertices();
		for (int i = 0; i < amtVertices; i += 3) {
			float[] v1 = model1.getVertexAtId(i);
			float[] v2 = model1.getVertexAtId(i + 1);
			float[] v3 = model1.getVertexAtId(i + 2);

			v1 = applyRotations(v1, xRot, yRot, zRot);
			v2 = applyRotations(v2, xRot, yRot, zRot);
			v3 = applyRotations(v3, xRot, yRot, zRot);

			v1[0] += x1;
			v1[1] += y1;
			v1[2] += z1;

			v2[0] += x1;
			v2[1] += y1;
			v2[2] += z1;

			v3[0] += x1;
			v3[1] += y1;
			v3[2] += z1;

			float dist = intersectRayTriangle(v1, v2, v3, vec, dir);
			if ((dist > 0.0D) && (dist < 10000000.0D)) {
				float[] normal = getTriangleNormal(v1[0], v1[1], v1[2], v2[0], v2[1], v2[2], v3[0], v3[1], v3[2]);
				lastTriangleData = new float[] { v1[0], v1[1], v1[2], v2[0], v2[1], v2[2], v3[0], v3[1], v3[2], normal[0], normal[1], normal[2], i / 3 };
				ret.add(new HitTriangle(dist, lastTriangleData));
			}
		}

		Collections.sort(ret, new Comparator<HitTriangle>() {
			@Override
			public int compare(HitTriangle arg0, HitTriangle arg1) {
				return (int)(arg0.distanceHitFrom - arg1.distanceHitFrom);
			}
		});
		return ret;
	}

	//p3dc_check()
	//Written by Andrew Hamilton (orange451)
	public static float collision_ray(D3DModel model1, float xRot, float yRot, float zRot, float x1, float y1, float z1, float x2, float y2, float z2, float nx, float ny, float nz) {
		float[] vec = {x2, y2, z2};
		float[] dir = {nx, ny, nz};
		float retdist = LARGE_NUM;
		int amtVertices = model1.getAmountVertices();
		for (int i = 0; i < amtVertices; i += 3) {
			float[] v1 = model1.getVertexAtId(i);
			float[] v2 = model1.getVertexAtId(i+1);
			float[] v3 = model1.getVertexAtId(i+2);

			v1 = applyRotations(v1, xRot, yRot, zRot);
			v2 = applyRotations(v2, xRot, yRot, zRot);
			v3 = applyRotations(v3, xRot, yRot, zRot);
			
			v1[0] += x1;
			v1[1] += y1;
			v1[2] += z1;

			v2[0] += x1;
			v2[1] += y1;
			v2[2] += z1;

			v3[0] += x1;
			v3[1] += y1;
			v3[2] += z1;
			
			float dist = CollisionHelper.intersectRayTriangle(v1, v2, v3, vec, dir);
			if (dist < retdist && dist >= 0) {
				retdist = dist;
				float[] normal = CollisionHelper.getTriangleNormal(v1[0], v1[1], v1[2], v2[0], v2[1], v2[2], v3[0], v3[1], v3[2]);
				lastTriangleData = new float[] { v1[0], v1[1], v1[2], v2[0], v2[1], v2[2], v3[0], v3[1], v3[2], normal[0], normal[1], normal[2], i/3 };
			}
		}
		return retdist;
	}
	
	public ArrayList<HitTriangle> trimTriangleList(ArrayList<HitTriangle> triangles) {
		for (int i = triangles.size() - 1; i >= 0; i--) {
			if (i >= triangles.size())
				continue;
			HitTriangle tri = triangles.get(i);
			float num = tri.triangleData[12];
			for (int ii = triangles.size() - 2; ii >= 0; ii--) {
				if (triangles.get(ii).triangleData[12] == num) {
					triangles.remove(ii);
				}
			}
		}
		return triangles;
	}
	
	private static float degtorad(float degrees) {
		return degrees*3.14159f/180f;
	}
	private static float radtodeg(float rad) {
		return rad*180f/3.14159f;
	}
	
	public static float lengthdir_x(float length, float angle){
		return (float) (Math.cos(degtorad(angle))*length);
	}
	public static float lengthdir_y(float length, float angle){
		return (float) (-Math.sin(degtorad(angle))*length);
	}
	public static float point_distance(float x1,float y1,float x2,float y2){
		return (float) Math.sqrt(((x1-x2)*(x1-x2)) + ((y1-y2)*(y1-y2)));
	}
	public static float point_distance_3d(float x1,float y1, float z1,float x2,float y2, float z2){
		return (float) Math.sqrt(((x1-x2)*(x1-x2)) + ((y1-y2)*(y1-y2)) + ((z1-z2)*(z1-z2)));
	}
	public static float point_direction(float x1,float y1,float x2,float y2){
		return radtodeg((float) (Math.atan2(( y1 - y2),-(x1 - x2))));
	}

	/*
	Apply a rotation to a vertex,
	By Andrew Hamilton (orange451)
	*/
	private static float[] applyRotations(float[] vertex, float xa, float ya, float za) {
		float x1 = vertex[0];
		float y1 = vertex[1];
		float z1 = vertex[2];
		if (xa!=0){
		    float pd = point_distance_3d(x1, y1, z1, x1, 0, 0);
		    float pa = point_direction(0, 0, z1, y1);
		    z1=0+lengthdir_x(pd,pa-xa);
		    y1=0+lengthdir_y(pd,pa-xa);
		}
		if (ya!=0){
			float pd = point_distance_3d(x1, y1, z1, 0, y1, 0);
			float pa = point_direction(0, 0, z1, x1);
		    z1=0+lengthdir_x(pd,pa+ya);
		    x1=0+lengthdir_y(pd,pa+ya);
		}
		if (za!=0){
			float pd = point_distance(x1,y1,0,0);
			float pa = point_direction(0, 0, x1,y1);
		    x1=0+lengthdir_x(pd,pa+za);
		    y1=0+lengthdir_y(pd,pa+za);
		}
		
		return new float[] {x1, y1, z1};
	}

	/*
	Triangle/triangle intersection test routine,
	by Tomas Moller, 1997.
	Ported to Java by by Andrew Hamilton (orange451)
	*/
	protected static boolean checkTriangleCollision(float[] V0, float[] V1, float[] V2, float[] U0, float[] U1, float[] U2) {
		float[] E1, E2, N1 = {0, 0, 0};
		float d1, du0, du1, du2, du0du1, du0du2 = 0;

		E1 = SUB(V1, V0);
		E2 = SUB(V2, V0);
		N1 = CROSS(E1, E2);
		d1 = -DOT(N1, V0);
		du0 = DOT(N1, U0) + d1;
		du1 = DOT(N1, U1) + d1;
		du2 = DOT(N1, U2) + d1;
		du0du1 = du0 * du1;
		du0du2 = du0 * du2;

		if(du0du1>0.0f && du0du2>0.0f)
			return false;
		
		float[] N2 = {0,0,0};
		E1 = SUB(U1,U0);
		E2 = SUB(U2,U0);
		N2 = CROSS(E1,E2);
		float d2=-DOT(N2,U0);
		float dv0=DOT(N2,V0)+d2;
		float dv1=DOT(N2,V1)+d2;
		float dv2=DOT(N2,V2)+d2;
		float dv0dv1=dv0*dv1;
		float dv0dv2=dv0*dv2;

		if(dv0dv1>0.0f && dv0dv2>0.0f)
			return false;
		
		float[] D = CROSS(N1,N2); // {a, b, c}
		float max=Math.abs(D[0]);
		float bb=Math.abs(D[1]);
		float cc=Math.abs(D[2]);
		short index=0;
		
		if(bb>max) {
			max=bb;
			index=1;
		}else if(cc>max) {
			max=cc;
			index=2;
		}

		float vp0=V0[index], vp1=V1[index], vp2=V2[index], up0=U0[index], up1=U1[index], up2=U2[index], a = 0, b = 0, c = 0, x0 = 0, x1 = 0, d = 0, e = 0, f = 0, y0 = 0, y1 = 0;
		
		if(dv0dv1 > 0.0f){
			a=vp2;
			b=(vp0-vp2)*dv2;
			c=(vp1-vp2)*dv2;
			x0=dv2-dv0;
			x1=dv2-dv1;
		}else if(dv0dv2 > 0.0f){                                          
			a=vp1;
			b=(vp0-vp1)*dv1;
			c=(vp2-vp1)*dv1;
			x0=dv1-dv0;
			x1=dv1-dv2;
		}else if(dv1 * dv2 > 0.0f || dv0 != 0.0f){                             
			a=vp0;
			b=(vp1-vp0)*dv0;
			c=(vp2-vp0)*dv0;
			x0=dv0-dv1;
			x1=dv0-dv2;
		}else if(dv1 != 0.0f){                                           
			a=vp1;
			b=(vp0-vp1)*dv1;
			c=(vp2-vp1)*dv1;
			x0=dv1-dv0;
			x1=dv1-dv2;
		}else if(dv2 != 0.0f){                                           
			a=vp2;
			b=(vp0-vp2)*dv2;
			c=(vp1-vp2)*dv2;
			x0=dv2-dv0;
			x1=dv2-dv1;
		}else{
			return false;
		}
		
		if(du0du1 > 0.0f){
			d=up2;
			e=(up0-up2)*du2;
			f=(up1-up2)*du2;
			y0=du2-du0;
			y1=du2-du1;
		}else if(du0du2 > 0.0f){                                          
			d=up1;
			e=(up0-up1)*du1;
			f=(up2-up1)*du1;
			y0=du1-du0;
			y1=du1-du2;
		}else if(du1 * du2 > 0.0f || du0 != 0.0f){                             
			d=up0;
			e=(up1-up0)*du0;
			f=(up2-up0)*du0;
			y0=du0-du1;
			y1=du0-du2;
		}else if(du1 != 0.0f){                                           
			d=up1;
			e=(up0-up1)*du1;
			f=(up2-up1)*du1;
			y0=du1-du0;
			y1=du1-du2;
		}else if(du2 != 0.0f){                                           
			d=up2;
			e=(up0-up2)*du2;
			f=(up1-up2)*du2;
			y0=du2-du0;
			y1=du2-du1;
		}else{
			return false;
		}
		
		float[] isect1 = {0,0};
		float[] isect2 = {0,0};
		
		float xx=x0*x1,
		yy=y0*y1,
		xxyy=xx*yy,
		tmp=a*xxyy;
		isect1[0]=tmp+b*x1*yy;
		isect1[1]=tmp+c*x0*yy;
		tmp=d*xxyy;
		isect2[0]=tmp+e*xx*y1;
		isect2[1]=tmp+f*xx*y0;

	    if(isect1[0] > isect1[1]){
	        float c1=isect1[0];
	        isect1[0]=isect1[1];
	        isect1[1]=c1;
	    }
	        
	    if(isect2[0] > isect2[1]){
	        float c1=isect2[0];
	        isect2[0]=isect2[1];
	        isect2[1]=c1;
	    }
	    
		if(isect1[1] < isect2[0] || isect2[1] < isect1[0])
			return false;
		
		return true;
	}

	/*
	Ray/triangle intersection test routine,
	By Thomas Moller,
	Ported to Java by Andrew Hamilton (orange451)
	*/
	private static float intersectRayTriangle(float vert0[], float vert1[], float vert2[], float[] orig, float dir[]){
		/*
	    Arguments:
	        0 vertex 1 (float array, length 3)
	        1 vertex 2 (float array, length 3)
	        2 vertex 3 (float array, length 3)
	        3 ray vertex
	        4 ray normal

	    Returns:
	        Returns the distance to the *closest* triangle that was hit. Returns 10000000 if no triangle was hit.
		 */
		float[] edge1, edge2, tvec, pvec, qvec = {0, 0, 0};
		float det,u,v,invDet;
		float EPSILON = 0.000001f;
		edge1 = SUB(vert1, vert0);
		edge2 = SUB(vert2, vert0);
		pvec = CROSS(dir, edge2);
		det = DOT(edge1, pvec);
		if (det > -EPSILON && det < EPSILON)
			return LARGE_NUM;
		invDet = (float) (1d/det);
		tvec = SUB(orig, vert0);
		u = DOT(tvec, pvec) * invDet;
		if (u < 0.0f || u > 1.0f)
			return LARGE_NUM;
		qvec = CROSS(tvec, edge1);
		v = DOT(dir, qvec) * invDet;
		if (v < 0.0f || (u + v) > 1.0f)
			return LARGE_NUM;
		float dist = DOT(edge2, qvec) * invDet;
		if (dist < 0)
			return LARGE_NUM;
		
		return dist;
	}


	/*
	private static float intersectRayTriangle(float vert0[], float vert1[], float vert2[], float[] orig, float dir[]){
		float[] edge1, edge2, tvec, pvec, qvec = {0, 0, 0};
		float det,u,v;

		edge1 = SUB(vert1, vert0);
		edge2 = SUB(vert2, vert0);
		pvec = CROSS(dir, edge2);
		det = DOT(edge1, pvec);
		tvec = SUB(orig, vert0);
		u = DOT(tvec, pvec);

		if (det > 0.0001){
			if (u < 0.0 || u > det)
				return LARGE_NUM;
			qvec = CROSS(tvec, edge1);
			v = DOT(dir, qvec);
			if (v < 0.0 || u + v > det)
					return LARGE_NUM;
		}else if(det < -0.0001){
			if (u > 0.0 || u < det)
					return LARGE_NUM;
			qvec = CROSS(tvec, edge1);
			v = DOT(dir, qvec);
			if (v > 0.0 || u + v < det)
				return LARGE_NUM;
		}else{
			return LARGE_NUM;
		}
		float dist = DOT(edge2, qvec) * (1.0 / det);
		return dist;
	}
	 */
	
	//Add two vectors together
	@SuppressWarnings("unused")
	private static float[] ADD(float[] v1, float[] v2) {
		float[] ret = new float[3];
		ret[0] = v1[0]+v2[0];
		ret[1] = v1[1]+v2[1];
		ret[2] = v1[2]+v2[2];
		return ret;
	}

	//Subtract two vectors
	private static float[] SUB(float[] v1, float[] v2) {
		float[] ret = new float[3];
		ret[0] = v1[0]-v2[0];
		ret[1] = v1[1]-v2[1];
		ret[2] = v1[2]-v2[2];
		return ret;
	}

	//Get dot product of two vectors
	private static float DOT(float[] v1, float[] v2) {
		return (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2]);
	}

	
	private static float[] CROSS(float[] v1, float[] v2) {
		float[] ret = new float[3];
		ret[0] = v1[1]*v2[2]-v1[2]*v2[1];
		ret[1] = v1[2]*v2[0]-v1[0]*v2[2];
		ret[2] = v1[0]*v2[1]-v1[1]*v2[0];
		return ret;
	}
	
	public static float[] getLastTriangleData() {
		return CollisionHelper.lastTriangleData;
	}

	/*
	 Calculate normal of a triangle,
	 By Andrew Hamilton (orange451).
	 */
	public static float[] getTriangleNormal(float argument0, float argument1, float argument2, float argument3, float argument4, float argument5, float argument6, float argument7, float argument8) {
		/*
	    Arguments:
	        0 x point0
	        1 y
	        2 z
	        3 x point1
	        4 y
	        5 z
	        6 x point2
	        7 y
	        8 z

	    Returns:
	        vector3f of the triangles' normal
		 */

		float ax,ay,az,bx,by,bz,m,rx,ry,rz;

		//point0 -> point1
		ax = argument3-argument0;
		ay = argument4-argument1;
		az = argument5-argument2;

		//point0 -> point2
		bx = argument6-argument0;
		by = argument7-argument1;
		bz = argument8-argument2;

		//cross product
		rx = ay*bz-by*az;
		ry = az*bx-bz*ax;
		rz = ax*by-bx*ay;

		//magnitude
		m = (float) Math.sqrt(rx*rx+ry*ry+rz*rz);

		//normalize
		rx /= m;
		ry /= m;
		rz /= m;

		return new float[] {rx, ry, rz};
	}

	/*
	 Check for collision between two vertices,
	 By Andrew Hamilton (orange451).
	 */
	public static int collision_line_3d(float x1, float y1, float z1, float x2, float y2, float z2, D3DModel d3dModel) {
		Vector temp = Vector.getDirection(new Location(null, x1, y1, z1), new Location(null, x2, y2, z2));
		float mag = temp.getMagnitude();
		float nx = temp.getX() / mag;
		float ny = temp.getY() / mag;
		float nz = temp.getZ() / mag;
		float raydis = collision_ray(d3dModel, 0, 0, 0, 0, 0, 0, x1, y1, z1, nx, ny, nz);
		if (raydis <= mag) {
		    return 1;
		}
		return 0;
	}
}

It wont work without my other classes, but all the math you’ll need is all there :wink: