Jump to content
  • Advertisement
Sign in to follow this  

Scanline triangle rasterization To retrieve 2D grid cells

This topic is 1264 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey all.


I'm tyring to retrieve 2D grid  cells based on a scanline triangle raster. I have it working for pixels but when it comes to add a cell offset of 1024 width of cell, it returns squares or bits of the triangle. I also have a working Bresenham's line algorithm with the cell off setand this works fine.

I used this to test my triangle points and they all check out. But I don't use the line function in the triangle no need for it there.

But for some reason I just cant apply the offset in the triangle raster. any tips or whats wrong. I've been at this for 25 hour hehe I'm ashamed.

I wrote the line algo from less info about 2 years ago in less time.


This is the info I'm following. It works perfect but I cant add an offset for pixels(cells in this case) being larger then 1

Share this post

Link to post
Share on other sites

Well there you go. All I needed was to post a post, reread the article, Look at my lineofsight function again and there.


It was a combination of using the wrong width for delta left and right needs to be half cell hight and the Y set needs to be cell size as I was using sell half size.

That and the fact that the triangles are from the cameras frustum and it over hangs the boundary and was being clipped and not looking like a triangle.


So in the above post's linked article if you add.


//step size's need to be half cell size

//and y step is cell size

int stepleft = 512;

int stepright = 512;

int stepY = 1024;

//then use the cell's half size to get the deltas 

//delta gets computed by the half cell size

dx_left  = (x2-x1)/stepleft;

dx_right = (x3-x1)/stepright;

//adjust the steps sign

if(dx_left < 0)

    stepleft *= -1;

if(dx_right < 0)

  stepright *= -1;
//then cell retreival

 // draw the triangle

    for (temp_y=y1; temp_y<=y3; temp_y+= stepY)


                 GetAllCellsInScanLine((unsigned int)xs, (unsigned int)(xe+1024), temp_y, celllist);

                    // adjust starting point and ending point

                    xs+=dx_left + stepleft;

                  xe+=dx_right + stepright;

        } // end for

Share this post

Link to post
Share on other sites

Nope Turns out you need the height to create the deltas or when you set it back to a 1 to 1 pixel it does not draw a triangle.


// compute delta's

height = y3-y1;


dx_left  = ((x3-x1)/height);


dx_right = ((x3-x2)/height);



With that all being said it works the best when the off sets are small gives a perffect triangle at 1, but a bit sad on a larger cell.

Share this post

Link to post
Share on other sites

Oh Jumping the gun again in calling some thing wright.


Just when you think its save to enter the water /| /| /| along comes the next part rotation. Failed big time on the in between ranges like 55° bla.


I was thinking about it all wrong, Thinking offsets bad path to go down.

Getting to the point the damn this is vector based, Therefore the cell size's can be looked at as a speed and multiplied with the deltas and there you have it perfect triangles.


Tested completely rotated over time. Yaywub.png

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!