Advertisement

Plotting line in 3D space

Started by December 04, 2022 02:34 AM
5 comments, last by JoeJ 2 years ago

Hi guys,

I am making a software 3D renderer, which is presently working great, but I am at the point where I am designing the depth handling side of things.

I am trying to create a routine that will plot a line in to 3D space. I can happily draw lines on the X & Y axes, but struggling to figure out how I would draw the Z component (which is being stored in a 2D array as a depth buffer).

I have tested my plot routines and they are working as intended (pixels deeper in the scene getting culled happily).

This is what I have made so far. I know that my z is locked in as z0 at the moment. But I've been working at this for so long that my brain has turned to mush.

Any advice would be greatly appreciated.

Many thanks!

function plotLine3D(x0, y0, x1, y1, z0, z1)
{
	dz = z1 - z0;
	dx = x1 - x0;
	dy = y1 - y0;

	yi = 1;

	if(dy < 0)
	{
		yi = -1;
		dy = -dy;
	}

	D = (2 * dy) - dx;

	y = y0;
	z = z0;


	for(x = x0; x <= x1; x++)
	{
		if(x >= 0 && x <= 319 && y >= 0 && y <= 199)
		{
			Plot3D(x, y, z);
		}

		if(D > 0)
		{
			y = y + yi;
			D = D + (2 * (dy - dx));
		}
		else
		{
			D = D + 2 * dy;
		}
	}
}

I am not sure what you're asking, I have a hard time understanding what a depth buffer has to do with plotting a line.

If you're asking for a routine to compute pixels for a line in 3D space between 2 points, I'd suggest you look into a 3D Bresenham algorithm, eg https://www.geeksforgeeks.org/bresenhams-algorithm-for-3-d-line-drawing/​ was my first hit. You may want to read the original 2D algorithm though to understand the idea behind it (wikipedia explains it).

Advertisement

Alberth said:

I am not sure what you're asking, I have a hard time understanding what a depth buffer has to do with plotting a line.

As I said “I am trying to create a routine that will plot a line in to 3D space”, that's why I'm writing the 3rd dimension to a depth buffer.

The line on screen is still 2D, so you can keep what you have. (Although you want subpixel accuracy for stable results under motion, but this becomes more meaningful once you start with triangles/polygons)

For depth the problem is that it isn't linear, so you can not interpolate it along the start and end points of the line without a divide.
The common solution is to interpolate 1/depth instead, which works.

Ofc. you also need to include depth value support to your projection math, which i do not remember much about.

Here is a function i used to draw a textured scanline for a polygon or triangle with depth test:

void rastScanlineHTexF (int y, rast_paramsF &rp0, rast_paramsF &rp1, // scanline params
						  unsigned int* scr, unsigned int* scr_z, int scr_w, // color buffer, bepth buffer, screen width
						  texture32 *texture) 
{

	int x = (int)rp0.s;
	int x2 = (int)rp1.s;


	unsigned int  *cbufL = scr + y*scr_w;
	unsigned int  *cbuf =		cbufL + x;
	unsigned int  *cbufEnd =	cbufL + x2;



	if (cbufEnd<=cbuf) return; // not sure what this is; probably some hack to deal with errors
			
	float inv = 1.0f / (rp1.s-rp0.s); 
	float sub = 1.0f-(rp0.s - (float)x); // sub pixel accuracy (adds complexity, but otherwise jitters like Playstation 1)
	
	
	float slopeZ = inv * (rp1.z-rp0.z);
	float z = rp0.z + slopeZ * sub;

	unsigned int *zbuf = cbuf + (scr_z-scr);
	
	float slopeU = (rp1.u-rp0.u) * inv;
	float slopeV = (rp1.v-rp0.v) * inv;
	float u = rp0.u + slopeU * sub;
	float v = rp0.v + slopeV * sub;

	while (cbuf < cbufEnd)
	{
		float real_z = 1.0f / z; // that's the division i have mentioned to turn interpolted 1/z back to z. Quake only did this once for 4 pixels, but i did not mind performance here. It gives us perspective correct textrue mapping.
		float real_u = u * real_z;
		float real_v = v * real_z;


		unsigned int zI = ((unsigned int)toFP (z))<<1;
		if (zI > *zbuf) // depth test
			rastPixelFTex32 (cbuf, zbuf, zI, real_u, real_v, texture);
		zbuf++; cbuf++; 
		
		z += slopeZ;
		u += slopeU;
		v += slopeV;
	}
}

That's already a port from older renderer where i had used fixed point integers instead floats. The Z buffer is still fixed point, and toFP() only handles the conversation.

Here comments to explain some params:

struct rast_paramsF
{
	float u; // u&v must be first, to allow swapped indexing
	float v; // 
	float s; // screen x 
	float z; // screen z

Nothing special about the pixel draw:

inline void rastPixelFTex32 (unsigned int* cbuf, unsigned int* zbuf, int z,
	float u, float v, texture32 *texture)
{
	*zbuf = z | 0x1; // set Z and Alpha
	int uindex = int (u);
	int vindex = int (v);
	int index = uindex + vindex * texture->width;
	int col32 = texture->bits[index];
	*cbuf = col32;
}

Not sure how much this really helps.
Triangle/polygon setup is way more complicated, and clipping as well.
Basic rasterization is harder than basic ray tracing. : )

Hi @joej , thanks for the hugely detailed reply. That is truly awesome.

My present line routines work well for triangles etc, and am even at the stage where flood fill is working great. The 3d matrix math is already complete also and am able to draw 3D geometry wherever I like. Flat shaded, looks fine (as a silouhette). Just that pesky depth element now now culling. :D

I'll have a solid read through what you have posted and try some things out. Will let you know how it goes.

Huge thanks so far!

DividedByZero said:
My present line routines work well for triangles etc

Nah. It jitters, because you snap vertices to pixels. So under motion it jumps around due to rounding quantization.
Initially many games were fine with this.
But Quake did much better. Maybe you remember the nice stairstep crawling of triangle edges after players death, when they move the camera very slowly at some tilted angle. They did this to show off their high quality subpixel accuracy.
At this point, Bresenham & co is amateur crap. That's also why fixed point integer math was used to handle accuracy beyond a single pixel.
But just to let you know. :D

DividedByZero said:
flood fill

Meh as well. Prohibitively slow.
Instead, you have clockwise order polygon edges, find the top most vertex, and then traverse left and right side down, generating horizontal scan lines. Then no searching is needed to fill it.

But again, just to brag with knowledge nowadays no longer needed. :D Although, UE5 Nanite brings this stuff back.

DividedByZero said:
I'll have a solid read through what you have posted and try some things out.

I have learned this stuff from Micheal Abrashs Graphics Programming Blackbook. Good resource, and it's free online somewhere. I also found some old projects with code belonging to the book back then.

This topic is closed to new replies.

Advertisement