Sign in to follow this  
Jiia

Drawing a Triangle

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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Jiia
The 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 this post


Link to post
Share on other sites
Quote:
Original post by SpaceDude
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.

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 this post


Link to post
Share on other sites
Quote:
Original post by ernow
A *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 this post


Link to post
Share on other sites
Quote:
Original post by Jiia
Quote:
Original post by ernow
A *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 this post


Link to post
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this