

Learn to program or die trying 

Author 
Message 
albinopapa

Posted: December 14th, 2017, 7:31 am 

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

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: A = {10, 10}; B = { 0, 20}; C = {15, 30};
// Calculate where the split happens AB = BA; AC = CA; 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

Posted: December 14th, 2017, 2:35 pm 






goldengamesTM

Posted: December 14th, 2017, 2:56 pm 


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





albinopapa

Posted: December 14th, 2017, 7:39 pm 

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

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

Posted: December 14th, 2017, 9:47 pm 

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

There is another way of rendering triangles that has less steps using barycentric or aerial coordinates. This page will show you the math involved: barycentriccoordinates
_________________ 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

Posted: December 14th, 2017, 10:09 pm 

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

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: 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
_________________ 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

Posted: December 14th, 2017, 11:02 pm 


Attachment:
Engine.zip [4.23 MiB]
Downloaded 3 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

Posted: 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 That's A Triangle If I've Ever Seen One!





goldengamesTM

Posted: December 15th, 2017, 5:09 pm 


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





albinopapa

Posted: December 16th, 2017, 2:36 am 

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

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








You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot post attachments in this forum


