I Don't Watch 3D Fund, But....

The Partridge Family were neither partridges nor a family. Discuss.
albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: I Don't Watch 3D Fund, But....

Post by albinopapa » December 14th, 2017, 7:31 am

Regarding #1, I don't think this would give you good results, try and see, you'll probably end up with empty pixels in places. Not to mention, drawing horizontal lines would be faster since you are moving in the direction memory is laid out anyway.

Regarding #2, this approach is called line rasterization. This is what chili covers in his 3D fundamentals tutorials. You arrange the points in ascending order based on their Y coordinate.

Let's name these 3 points as vertex A, B, C.
Let's name the edges that connect the vertices as AB, AC, BC, where the first letter means the edge starts there and ends on the second letter. AB would be the edge connecting A to B, BA would be the same edge, but going from B to A.
Let's also say, A is the top most vertex, B is the second highest and C is the lowest.

Once you have arranged the points, you need to get the slope of AC and multiply it by the height of AB. What this does is finds a point along AC that is at the same height as vertex B. It will break the triangle into two sections, one with a flat bottom and one with a flat top. It creates a new vertex, we'll call it D.

Once you have your flat top and flat bottom triangles, you can calculate the slope of AB ( X / Y instead of Y / X because you will be iterating one row at a time, so you really only need to calculate the X for each row ). Then, calculate the slope ( X / Y ) of AD. This will help calculate the X for each row to end your line.

Now that you have your left and right slope, start from the coordinates of vertex A and iterate down, from Ay to Dy. Use the distance from Ay ( y - Ay ) and multiply that by the slope of each edge to get your X positions for start and finish.

Code: Select all

A = {10, 10};
B = {  0, 20};
C = {15, 30};

// Calculate where the split happens
AB = B-A;
AC = C-A;
mAC = ACx / ACy;
height = By - Ay;
AD = {Ax + ( mAC * height ), By}

// Calculate AB and AD slope
mAB = ABx / ABy;
mAD = ADx / ADy;

// Iterate from Ay to Dy or Ay to By, the height should be the same
for y = Ay to Dy
    xstart = (y - Ay) * mAB
    xend   = (y - Ay) * mAD
    gfx.DrawLine( xstart, y, xend, y, color )

The process is pretty much the same for the flat top triangle, but you have two vertices at the top of the triangle, so the left edge is BC and the right edge is DC. It's been awhile since I've looked through that code, so some info may be a bit off, but this is what I can remember when I attempted what you are attempting.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

goldengamesTM

Re: I Don't Watch 3D Fund, But....

Post by goldengamesTM » December 14th, 2017, 2:35 pm

Ok, Thank You!

goldengamesTM

Re: I Don't Watch 3D Fund, But....

Post by goldengamesTM » December 14th, 2017, 2:56 pm

Hey, You Lied... My Triangle Idea Worked Like A Charm!
Capture.png
Capture.png (1.58 KiB) Viewed 2408 times
(In Case You Didn't Get The Memo, I Was Joking)

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: I Don't Watch 3D Fund, But....

Post by albinopapa » December 14th, 2017, 7:39 pm

Hehe, I kind of figured that would happen. Ran into similar problems trying to make thicker slanted lines. Thought I could just use the line drawing algorithm over and over for the thickness, but it didn't work, got a bunch of holes.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: I Don't Watch 3D Fund, But....

Post by albinopapa » December 14th, 2017, 9:47 pm

There is another way of rendering triangles that has less steps using barycentric or aerial coordinates.

This page will show you the math involved: barycentric-coordinates
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: I Don't Watch 3D Fund, But....

Post by albinopapa » December 14th, 2017, 10:09 pm

Here are the steps:
1) Get the area of the triangle to render
2) Create a bounding box around the triangle
3) Iterate through the bounding box from left top to right bottom
4) Using X and Y from each point in the bounding box, split up the triangle into smaller triangles, using this point as one of the vertices.
5) Get the area of each of the three smaller triangles
6) divide each smaller area by the total area
7) if any of the areas is >= 0 AND <= 1 then the point is in the triangle

The nice thing about this method is the three values you get after step 6 can be used to interpolate any value you need within the triangle. For instance, if you have texture coordinate you can use sum the products ( I hate math lingo ) of the three values and the texture coordinates.

*tc = texture coordinate
*bc = barycentric coordinate

tc.u = ( tc0.u * bc.u ) + ( tc1.u * bc.v ) + ( tc2.u * bc.w );
tc.v = ( tc0.v * bc.u ) + ( tc1.v * bc.v ) + ( tc2.v * bc.w );

same would go for any other property of the triangle that needs to be interpolated.

Here's my implementation

Code: Select all

struct Coordinates
{
	Coordinates(
		const Vec2f A,
		const Vec2f B,
		const Vec2f C,
		const Vec2f CA,
		const Vec2f AB,
		const Vec2f BC,
		const float TotalArea
	)
		:
		a( A ), b( B ), c( C ),
		ca( CA ), ab( AB ), bc( BC ),
		total_area( TotalArea )
	{}

	void Calculate( const Vec2f& P )
	{
		const auto ap = P - a;
		const auto bp = P - b;
		const auto cp = P - c;

		const float areaA = ( ca.y * cp.x - ca.x * cp.y ) * .5f;
		const float areaB = ( ab.y * ap.x - ab.x * ap.y ) * .5f;
		const float areaC = ( bc.y * bp.x - bc.x * bp.y ) * .5f;

		u = areaA / total_area;
		v = areaB / total_area;
		w = areaC / total_area;
	}

	bool IsInTriangle()const
	{
		return
			( u >= 0.f && u <= 1.f ) &&
			( v >= 0.f && v <= 1.f ) &&
			( w >= 0.f && w <= 1.f );
	}

	template<class T>
	T Interpolate( const T& Value0, const T& Value1, const T& Value2 )
	{
		return ( Value0 * u ) + ( Value1 * v ) + ( Value2 * w );
	}
	template<>
	Color Interpolate( const Color& Value0, const Color& Value1, const Color& Value2 )
	{
		const unsigned char cu = static_cast< unsigned char >( u * 255.f );
		const unsigned char cv = static_cast< unsigned char >( v * 255.f );
		const unsigned char cw = static_cast< unsigned char >( w * 255.f );

		return ( Value0 * cu ) + ( Value1 * cv ) + ( Value2 * cw );
	}

	Vec2f a, b, c;
	Vec2f ca, ab, bc;
	float total_area;
	float u, v, w;
};

void Graphics::DrawTriangle( const Vec2f & A, const Vec2f & B, const Vec2f & C, Color C0, Color C1, Color C2 )
{
	// Calculate the total area of the trinagle
	const auto AB = B - A;
	const auto AC = C - A;
	const auto BC = C - B;
	const auto CA = A - C;

	const float total_area = AB.y * AC.x - AB.x * AC.y * .5f;
	
	// Calculate the bounding box around the triangle
	const int xStart = std::min( A.x, std::min( B.x, C.x ) );
	const int yStart = std::min( A.y, std::min( B.y, C.y ) );
	const int xEnd =   std::max( A.x, std::max( B.x, C.x ) );
	const int yEnd =   std::max( A.y, std::max( B.y, C.y ) );

	Coordinates coords( A, B, C, CA, AB, BC, total_area );

	// Iterate through the bounding box and calculate the barycentric coordinates
	for( int y = yStart; y < yEnd; ++y )
	{
		for( int x = xStart; x < xEnd; ++x )
		{
			coords.Calculate( {
				static_cast< float >( x ),
				static_cast< float >( y )
				} );

			// Only show pixels that are in the triangle
			if( coords.IsInTriangle() )
			{
				Color color = coords.Interpolate( C0, C1, C2 );
				PutPixel( x, y, color );
			}
		}
	}
}
Edit: I modified a few things to add color interpolation. My Color::operator* function doesn't handle floats, instead it accepts unsigned char, so I had to make a template specialization in the Coordinates struct for interpolate to convert the floats ( 0 to 1 ) to unsigned char ( 0 to 255 ) before interpolating.

Screenshot
Image
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

goldengamesTM

Re: I Don't Watch 3D Fund, But....

Post by goldengamesTM » December 14th, 2017, 11:02 pm

Engine.zip
(4.23 MiB) Downloaded 161 times
Ok, Here's A Solution For You People To Mess With. ( I Would Put This In The Main Post, But I Can't )

goldengamesTM

Re: I Don't Watch 3D Fund, But....

Post by goldengamesTM » December 14th, 2017, 11:03 pm

albinopapa wrote: Edit: I modified a few things to add color interpolation. My Color::operator* function doesn't handle floats, instead it accepts unsigned char, so I had to make a template specialization in the Coordinates struct for interpolate to convert the floats ( 0 to 1 ) to unsigned char ( 0 to 255 ) before interpolating.

Screenshot
Image
That's A Triangle If I've Ever Seen One!

goldengamesTM

Re: I Don't Watch 3D Fund, But....

Post by goldengamesTM » December 15th, 2017, 5:09 pm

@albinopapa, Could You Please Upload A Zipped Solution That You Used That In?

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: I Don't Watch 3D Fund, But....

Post by albinopapa » December 16th, 2017, 2:36 am

Here is the GitHub link for the repository: Triangle Rasterizer
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Post Reply