訪問三角形點以隨機的順序

Question

對於由方程AX +對整數

我想在三角形繪製每個像素（*）一次且僅一次指定由< = C直角三角形，以僞隨機順序，並且不存儲先前生命值的列表。

我知道如何與線段做到這一點0和x

選擇一個隨機point'o之間」沿線，
挑‘P’是相對素爲x
重複達x倍：o _下 =（O _CUR + P）MOD X

要爲三角形，我會
要這樣做1.需要計數的三角形SANS像素數列出
2.地圖的整數0..points成斧，y對即三角形

希望任何解決方案可以推廣內的有效象素金字塔和更高維的形狀。 （*）我使用一對整數點X，Y的CG術語像素，以便滿足方程式。

Answer 1

既然你想保證只訪問一次像素一次，最好是用像素而不是實際三角形來思考。 您可以水平切割三角形並獲得一堆水平的scan lines。將掃描線連接在一起，並將您的「三角形」轉換爲長線。將您的點訪問算法應用於您的長鏈掃描線。

順便說一句，這個映射只需要在紙上發生，你所需要的只是一個函數，它可以沿虛擬掃描線返回（x，y）給定（t）。

編輯： 要將兩點轉換爲線段，可以查找Bresenham's scan conversion。一旦將3條線段轉換爲一系列點，您可以將所有點放入一個存儲桶中，並將所有點按y分組。在相同的y值內，按x排序點。 y值內的最小x是掃描線的起始點，而y值內的最大x是掃描線的終點。這被稱爲「掃描轉換三角形」。如果你是Google，你可以找到更多信息。

Answer 2

一種方法是將所有像素放入數組中，然後對數組進行混洗（這是O（n）），然後按照混洗陣列中的順序訪問像素。這可能需要相當多的內存。

Answer 3

這是一種浪費一些CPU時間的方法，但可能不會像更復雜的方法那樣浪費。

計算外接三角形的矩形。很容易將這個矩形「線性化」，每條掃描線跟着下一個。使用您已知的算法來遍歷矩形的像素。當你擊中每個像素時，檢查像素是否在三角形中，如果不是，則跳過它。

Answer 4

以下是Triangle Point Picking的解決方案。

你需要做的是選擇你的三角形的兩個向量（邊），每個乘以[0,1]中的一個隨機數並加起來。這將在由矢量定義的四邊形中提供均勻的分佈。您必須檢查結果是否位於原始三角形內;如果它不能將其轉換回來，或者只是丟棄它並重試。

Answer 5

我會將三角形的線看作單線，將其切割成線段。這些段將存儲在一個數組中，其中也存儲了段的長度以及行總長度的偏移量。然後根據O的值，可以根據這些信息選擇哪個數組元素包含您想要繪製的像素，並根據元素中的值繪製像素。