# Drawing a Triangle

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

## Recommended Posts

I tried hard to Google for this, but lack of good search keywords lead me to everything except what I wanted. I'm trying to find all of the dark cells in this grid. The grid is infinite, so I cannot scan them or use a quad tree. The routine is to cull world and terrain objects within a uniform grid. I plan to eliminate camera-tilting in order for this to work properly. I could find the outlining cells by casting rays, but I'm not sure how to find what is inside. Or I could also resort to using an AABB for the frustum, which would make it ridiculously simple to locate the cells, but it could introduce a lot of invisible cells (only 6 in example). If anyone has any useful links, that's almost as good as advice [smile] Thanks

##### Share on other sites
I had the same problem, and solved it by using a polygon-fill-routine.
Just look for a routine, that would do line fills.

Basically you insert the points in a list, sort them by y and scan the edges line per line. Every line simply adds the tiles/boxes of a specific y value.

A minor modification will be necessary though, most fill routines leave out the right-most tile/pixel and the bottom edge.

##### Share on other sites
Isn't this covered in Tricks of the Windows Game Programming Gurus?

##### Share on other sites
Quote:
 Original post by JiiaThe grid is infinite, so I cannot scan them or use a quad tree.

Well you could very easily obtain a finite grid by building a bounding box around the triangle, then find the grid squares which interesect with this bounding box. Then you could scan through all the grid squares you obtained and check if each one of them interesect with the triangle or not. This is not trivial though, and could be rather in-effecient for a large number of grid cells.

##### Share on other sites
Quote:
 Original post by SpaceDudeWell you could very easily obtain a finite grid by building a bounding box around the triangle, then find the grid squares which interesect with this bounding box. Then you could scan through all the grid squares you obtained and check if each one of them interesect with the triangle or not. This is not trivial though, and could be rather in-effecient for a large number of grid cells.

It is probably the most suitable for my situation. The number of cells that will fall in the triangle is not far off from the example image I posted. Actually, it may be a bit less. Probably around 10 to 16 or so cells. I'm thinking that matching axis-aligned cells against the frustum probably wouldn't be too bad, but I haven't given much thought as to how to optimize for them yet.

One of the coolest aspects is that using this idea doesn't require the triangle to even be a triangle, which means I wouldn't need to eliminate tilting. I may even use the frustum AABB to do some quick box cull-rejections on movable world objects.

I appreciate all of the advice

##### Share on other sites
A *completely* different approach would be to draw the triangle using
Bresenham's algorithm and interpolate the pixels in between.

Cheers

##### Share on other sites
Quote:
 Original post by ernowA *completely* different approach would be to draw the triangle using Bresenham's algorithm and interpolate the pixels in between.

That's what I was referring to when I mentioned "casting rays". But as I said, I'm not sure how I would be sure to find all of the inside cells. Any clue?

Thanks for the suggestion, though.

##### Share on other sites
Here's a good article about rasterising a 2D triangle

##### Share on other sites
Quote:
Original post by Jiia
Quote:
 Original post by ernowA *completely* different approach would be to draw the triangle using Bresenham's algorithm and interpolate the pixels in between.

That's what I was referring to when I mentioned "casting rays". But as I said, I'm not sure how I would be sure to find all of the inside cells. Any clue?

Thanks for the suggestion, though.

Quick (maybe dirty) way:
The Bresenham algo give you exact pixels. So when you use the algo to 'virtually' draw the edges you just store the cells in an array that uses the y-coordinate of the cells as an index and stores (possibly) two x-coordinates.

Then loop through the array:
- no x-coordinates: outside of the triangle
- 1 x-coordinate: top (or bottom corner)
- 2 x-coordinates: loop from the smallest x to the biggest x -> all these cells are inside the triangle.

Cheers

[Edited by - ernow on June 1, 2005 3:58:15 AM]

##### Share on other sites
This method looks pretty dang simple. I'll look into it as soon as I get my head out of yet another problem.

Thanks for the detail and link, I really appreciate it.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634090
• Total Posts
3015432
×