我在教科書中遇到的問題之一是：
In Computer Graphics transformations are applied on many vertices on the screen. Translation, Rotations
and Scaling.
Assume you’re operating on a vertex with 3 values (X, Y, 1). X, Y being the X Y coordinates and 1 is always
constant
A Translation is done on X as X = X X’ and on Y as Y = Y Y’
X’ and Y’ being the values to translate by
A scaling is done on X as X = aX and on Y as Y = bY
a and b being the scaling factors
Propose the best way to store these linear equations and an optimal way to calculate them on each vertex
暗示它涉及矩陣乘法和施特拉森。但是，我不確定從哪里開始？它不涉及復雜的代碼，它宣告提出一些簡單的東西來展示我的想法，但我遇到的所有 Strassen 實作絕對足夠大，不能稱之為復雜。我的思維程序應該是什么？
我的矩陣會像這樣嗎？每個方程 3x3 還是我將它們全部組合在一起？
[ X X X']
[ Y Y Y']
[ 1 1 1 ]
uj5u.com熱心網友回復：
您試圖找到的是一個轉換矩陣，然后您可以使用它來將某個當前 (x, y) 點轉換為下一個 (nx, ny) 點。換句話說，我們想要
start = Vec([x, y, 1])
matrix = Matrix(...)
next = start * matrix // * is matrix multiplication
現在，如果您next應該看起來像Vec([a * x x', b * y y', 1])，我們可以向后作業以找出矩陣。首先，只看x組件。我們將有效地start取向量和矩陣最頂行的點積，產生a * x x'.
如果我們更明確地寫出來，我們想要a * x 0 * y x' * 1. 希望這能讓我們更容易看到我們想要點的向量start是Vec([a, 0, x'])。我們可以對矩陣的其余兩行重復此操作，并獲得以下矩陣：
matrix = Matrix(
[[a, 0, x'],
[0, b, y'],
[0, 0, 1]])
仔細檢查這是否有意義并且對您來說似乎合理。如果我們將我們的start向量與這個矩陣相乘，我們將得到轉換后的向量next為Vec([a * x x', b * y y', 1])。
現在為了真正的美麗 - 矩陣本身根本不關心我們的輸入是什么，它完全獨立。因此，我們可以一遍又一遍地重復應用這個矩陣，以通過更多的縮放和平移向前邁進。
next_next_next = start * matrix * matrix * matrix
知道了這一點，我們實際上可以使用一些數學技巧非常快速地提前計算許多步驟。乘法但matrix n時間是一樣乘以matrix提升到n次方。幸運的是，我們有一種有效的方法來計算矩陣的冪——它被稱為平方取冪（實際上也適用于常規數，但這里我們關心的是矩陣相乘，邏輯仍然適用）。簡而言之，我們不是一次又一次地將數字或矩陣相乘，而是將其n平方并在正確的時間將中間值乘以原始數字/矩陣，以非常快速地接近所需的冪（在 log(n) 乘法中） .
這幾乎肯定是你的教授希望你意識到的。您可以及時模擬n平移/縮放/旋轉（是的，也有旋轉矩陣）log(n)。
額外里程
更酷的是，使用一些更高級的線性代數，您實際上可以做得更快。您可以將矩陣對角化（意味著您將矩陣重寫為P * D * P^-1，即某個矩陣P與矩陣的乘積，D其中唯一的非零元素沿著主對角線，乘以 的倒數P）。然后，您可以非常快速地將這個對角矩陣提升到冪，因為(P * D * P^-1) * (P * D * P^-1)簡化為P * D * D * P^-1，并且這推廣為：
M^N = (P * D * P^-1)^N = (P * D^N * P^-1)
由于D沿其對角線只有非零元素，因此您可以通過將每個單獨的元素提升到該冪來將其提升到任何冪，這只是整數乘法的正常成本，跨越與矩陣寬/高一樣多的元素。這是非常快的，然后您只需在任一側進行單個矩陣乘法即可到達M^N，然后將您的start向量與此相乘，以獲得最終結果。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/395984.html