Page 3 of 5 [ 46 posts ] Go to page Previous  1, 2, 3, 4, 5  Next

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

 Print view Previous topic | Next topic

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

Author Message
 Post subject: Re: I Don't Watch 3D Fund, But....  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 = B-A;
AC = C-A;
mAC = ACx / ACy;
height = By - Ay;
AD = {Ax + ( mAC * height ), By}

// Calculate AB and AD slope
mAB = ABx / ABy;

// 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

 Post subject: Re: I Don't Watch 3D Fund, But....  Posted: December 14th, 2017, 2:35 pm
Ok, Thank You!

 Post subject: Re: I Don't Watch 3D Fund, But....  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)

 Post subject: Re: I Don't Watch 3D Fund, But....  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

 Post subject: Re: I Don't Watch 3D Fund, But....  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.

_________________
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 subject: Re: I Don't Watch 3D Fund, But....  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

 Post subject: Re: I Don't Watch 3D Fund, But....  Posted: December 14th, 2017, 11:02 pm
Attachment:
Engine.zip [4.23 MiB]
Ok, Here's A Solution For You People To Mess With. ( I Would Put This In The Main Post, But I Can't )

 Post subject: Re: I Don't Watch 3D Fund, But....  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!

 Post subject: Re: I Don't Watch 3D Fund, But....  Posted: December 15th, 2017, 5:09 pm
@albinopapa, Could You Please Upload A Zipped Solution That You Used That In?

 Post subject: Re: I Don't Watch 3D Fund, But....  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

Display posts from previous:  Sort by

 Page 3 of 5 [ 46 posts ] Go to page Previous  1, 2, 3, 4, 5  Next

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

 Search for: