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

One method is to put all of the pixels into an array and then shuffle the array (this is O(n)), then visit the pixels in the order in the shuffled array. This could require quite a lot of memory though.

Answer 3

Here's a method which wastes some CPU time but probably doesn't waste as much as a more complicated method would do.

Compute a rectangle that circumscribes the triangle. It will be easy to "linearize" that rectangle, each scan line followed by the next. Use the algorithm that you already know in order to traverse the pixels of the rectangle. When you hit each pixel, check if the pixel is in the triangle, and if not then skip it.

Answer 4

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.

Answer 5

I would consider the lines of the triangle as single line, which is cut into segments. The segments would be stored in an array where the length of the segment also stored as well as the offset in the total length of the lines. Then depending on the value of O, you can select which array element contains the pixel you want to draw at that moment based on this information and paint the pixel based on the values in the element.