Visiting the points in a triangle in a random order

Question

For a right triangle specified by an equation aX + bY <= c on integers

I want to plot each pixel(*) in the triangle once and only once, in a pseudo-random order, and without storing a list of previously hit points.

I know how to do this with a line segment between 0 and x

pick a random point'o' along the line,
pick 'p' that is relatively prime to x
repeat for up to x times: O_next = (O_cur + P) MOD x

To do this for a triangle, I would
1. Need to count the number of pixels in the triangle sans lists
2. Map an integer 0..points into a x,y pair that is a valid pixel inside the triangle

I hope any solution could be generalized to pyramids and higher dimensional shapes.

(*) I use the CG term pixel for the pair of integer points X,Y such that the equation is satisfied.

Answer 1

Since you want to guarantee visiting each pixel once and only once, it's probably better to think in terms of pixels rather than the real triangles. You can slice the triangles horizontally and get bunch of horizontal scan lines. Connect the scan lines together and you have converted your "triangle" into a long line. Apply your point visiting algorithm to your long chain of scan lines.

By the way, this mapping only needs to happen on paper, all you need is a function that can return (x, y) given (t) along the virtual scan line.

Edit: To convert two points to a line segment, you can look for Bresenham's scan conversion. Once you get the 3 line segments converted into series of points, you can put all points into a bucket and group all points by y. Within the same y-value, sort points by x. The smallest x within a y-value is the begin point of the scan line and the largest x within the y-value is the end point of the scan line. This is called "scan converting triangle". You can find more info if you Google.

Answer 2

Here's a solution for Triangle Point Picking.

What you have to do is choose two vectors (sides) of your triangle, multiply each with a random number in [0,1] and add them up. This will provide a uniform distribution in the quadrilateral defined by the vectors. You'll have to check whether the result lies inside the original triangle; if it doesn't either transform it back in or simply discard it and try again.