Optimizing my triangle drawing routine?

I've written a small software 3D renderer in Java, with the purpose of using it in a game, and I'm at the point where I'm thinking of calling it done and starting the actual game programming. However, I still think my draw triangle routine is kind of slow, especially for textured triangles. (Although it is at least 10 times faster than Graphics.fillPolygon for flat triangles, because Java uses GDI internally!). Here is the relevant part, that draws a textured, Gouraud-shaded triangle. (The real method is quite a bit longer and handles special cases like flat shading and untextured triangles). Do you have any suggestions as to how to make it faster, or should I stick with this? I realize that I'm using arrays to store parameter values on each side of the triangle, which is slightly slower than walking down the sides with some kind of dx/dy step, but this should be practically inperceptible with caching and pipelining, and it happens an order of magnitude less than the inner loop code; I saw this technique in some 10-year-old articles, and if it worked then, it should work now. I'm also sure that this method really is the main bottleneck for the program; I timed the T&L part of the code and the rendering part, and rendering takes much more time. Also, rendering with flat shading is 1.5 to 2 times faster than using Gouraud shading.

/**
 * Draws a triangle given x,y screen coordinates, a w (1/z) coordinate, texture
 * coordinates (u, v multiplied by w), and material colors at each vertex.
 * The pixels and wBuffer are such that the pixel at (x,y) is in pixels[y*displayWidth + x].
 */
private void rasterizeTriangle(ProcessedTriangle p) {
	// get y's as ints

	int y0 = (int) p.y[0];
	int y1 = (int) p.y[1];
	int y2 = (int) p.y[2];
	
	// find min and max y values

	int yMin = y0, yMax = y0;
	if(y1 < yMin) yMin = y1;
	else if(y1 > yMax) yMax = y1;
	if(y2 < yMin) yMin = y2;
	else if(y2 > yMax) yMax = y2;
	
	// interpolate parameters accross the edges, assuming the points are clockwise

	// "w" is 1/z, and "u","v" are premultiplied by w, for perspective-correct texturing

	
	interpolateInt(p.x[0], y0, p.x[1], y1, (y0 > y1 ? leftX : rightX));
	interpolateInt(p.x[1], y1, p.x[2], y2, (y1 > y2 ? leftX : rightX));
	interpolateInt(p.x[0], y0, p.x[2], y2, (y2 > y0 ? leftX : rightX));

	interpolateFloat(p.w[0], y0, p.w[1], y1, (y0 > y1 ? leftW : rightW));
	interpolateFloat(p.w[1], y1, p.w[2], y2, (y1 > y2 ? leftW : rightW));
	interpolateFloat(p.w[0], y0, p.w[2], y2, (y2 > y0 ? leftW : rightW));
	
	interpolateColor(p.color[0], y0, p.color[1], y1, (y0 > y1 ? leftCol : rightCol));
	interpolateColor(p.color[1], y1, p.color[2], y2, (y1 > y2 ? leftCol : rightCol));
	interpolateColor(p.color[0], y0, p.color[2], y2, (y2 > y0 ? leftCol : rightCol));
	
	interpolateFloat(p.u[0], y0, p.u[1], y1, (y0 > y1 ? leftU : rightU));
	interpolateFloat(p.u[1], y1, p.u[2], y2, (y1 > y2 ? leftU : rightU));
	interpolateFloat(p.u[0], y0, p.u[2], y2, (y2 > y0 ? leftU : rightU));
	
	interpolateFloat(p.v[0], y0, p.v[1], y1, (y0 > y1 ? leftV : rightV));
	interpolateFloat(p.v[1], y1, p.v[2], y2, (y1 > y2 ? leftV : rightV));
	interpolateFloat(p.v[0], y0, p.v[2], y2, (y2 > y0 ? leftV : rightV));

	int texWidth = p.texture.width;
	int texHeight = p.texture.height;
	int maxU = texWidth-1, maxV = texHeight-1;
	
	int yPos = yMin * displayWidth;

	// loop through the scanlines, and do some poor man's clipping

	for(int y = yMin; y < yMax; y++, yPos+=displayWidth) if(y>=0) {
		if(y>=displayHeight) break;
		
		int x1 = leftX[y];
		int x2 = rightX[y];
		if(x2 - x1 < 0) continue;

		// get values of parameters at each edge of the scanline

		float w1 = leftW[y], w2 = rightW[y];
		float u1 = leftU[y], u2 = rightU[y];
		float v1 = leftV[y], v2 = rightV[y];
		float r1=leftCol[y][0], r2=rightCol[y][0];
		float g1=leftCol[y][1], g2=rightCol[y][1];
		float b1=leftCol[y][2], b2=rightCol[y][2];
		float a1=leftCol[y][3], a2=rightCol[y][3];
		
		// get gradients (slopes) accross the scanline

		float s = 1.0f/(x2-x1);
		float gw = (w2-w1)*s;
		float gu = (u2-u1)*s, gv = (v2-v1)*s;
		float gr = (r2-r1)*s, gg=(g2-g1)*s, gb=(b2-b1)*s, ga=(a2-a1)*s;
		
		// use fixed-point math for the colors; convert r,g,b, and their gradients to ints

		// first multiply by 255 since they are from 0 to 1, then by 256 for 8 "binary places"

		int ir = (int)(r1*(255*256)), igr = (int)(gr*(255*256));
		int ig = (int)(g1*(255*256)), igg = (int)(gg*(255*256));
		int ib = (int)(b1*(255*256)), igb = (int)(gb*(255*256));
		int ia = (int)(a1*(255*256)), iga = (int)(ga*(255*256));
		
		// for each point on the scanline; again, some poor man's clipping is occuring

		for(int i=yPos+x1; i<yPos+x2; i++) {
			if(i>=yPos+displayWidth) break;
			if(i>=yPos) {
				if(wTest(w1, i)) {
					// perspective correct texture mapping

					float z = 1.0f/w1;
					int u = (int) (texWidth*u1*z);
					int v = (int) (texHeight*v1*z);
					if(u<0) u=0; else if(u>maxU) u=maxU;
					if(v<0) v=0; else if(v>maxV) v=maxV;
					
					// get the texture color

					int col = p.texture.pixels[v*texWidth+u];
					
					// get the real color, by blending material with texture

					int r = (((col&0x00ff0000)>>16)*ir) >> 16;
					int g = (((col&0x0000ff00)>>8)*ig) >> 16;
					int b = ((col&0x000000ff)*ib) >> 16;
					int a = (((col&0xff000000)>>>24)*ia) >> 16;
					if(r<0) r=0; else if(r>255) r=255;
					if(g<0) g=0; else if(g>255) g=255;
					if(b<0) b=0; else if(b>255) b=255;
					if(a<0) a=0; else if(a>255) a=255;
					
					// set the pixel color and the w buffer element

					pixels[i] = alphaBlend(pixels[i], r, g, b, a);
					wBuffer[i] = w1;
				}
			}
			ir+=igr; ig+=igg; ib+=igb; ia+=iga;
			u1+=gu; v1+=gv;
			w1+=gw;
		}
	}
}

/**
 * Puts the v value for each index from i1 to i2 into a float[] dest,
 * linearly interpolating between the values v1 and v2.
 * The functions interpolateInt and interpolateColor are similar.
 */
private void interpolateFloat(float v1, int i1, float v2, int i2, float[] dest) {
	if(i1 > i2) {
		float td = v1; v1 = v2; v2 = td;
		int ti = i1; i1 = i2; i2 = ti;
	}
	else if(i1 == i2) { return; }
	float gradient = (v2-v1)/(float)(i2-i1);
	float v = v1;
	for(int i = i1; i <= i2; i++) {
		if(i>=0 && i<dest.length)
			dest[i] = v;
		v += gradient;
	}
}


/** The w buffer test; should be inlined by the compiler. */
private final boolean wTest(float w, int pos) {
	return w <= wBuffer[pos];
}

/** Alpha blending; again, should be inlined by the compiler. */
private final int alphaBlend(int color, int r, int g, int b, int a) {
	if(a==0) return color;
	else if(a==255) return ((r<<16) | (g<<8) | b);
	int cb = color & 0x000000ff;
	int cg = (color>>8) & 0x000000ff;
	int cr = (color>>16) & 0x000000ff;
	cr = ((cr<<8) + (r-cr) * a) >> 8;
	cg = ((cg<<8) + (g-cg) * a) >> 8;
	cb = ((cb<<8) + (b-cb) * a) >> 8;
	return (cr << 16) | (cg << 8) | cb;
}


/************
Just for reference, this is how I draw the backbuffer;
This gets about 70 FPS with a blank scene, so it shouldn't be *too* big a problem. I think it's the fastest way available in Java to use a writable surface.
************/

/** Creates the pixels and w buffers (whenever component is resized) */
private void createBuffers() {
	backBuffer = new BufferedImage(displayWidth, displayHeight, BufferedImage.TYPE_INT_RGB);
	DataBufferInt dataBuffer = (DataBufferInt) backBuffer.getRaster().getDataBuffer();
	pixels = dataBuffer.getData();
	wBuffer = new float[pixels.length];
}

/** Paints the scene. */
private void paint3dScene(Graphics g) {
	// [clear buffers]

	// [do some math]

	// [call rasterizeTriangle a few thousand times]

	g.drawImage(backBuffer, 0, 0, null);	
}

 

[edited by - Matei on May 16, 2004 9:04:41 PM] [edited by - Matei on May 16, 2004 9:06:54 PM]