1

我在教科书中遇到的问题之一是：

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。但是，我不确定从哪里开始？它不涉及复杂的代码，它声明想出一些简单的东西来展示我的想法，但我遇到的所有 Strassen 实现绝对足够大，不会称之为复杂。我的思考过程应该是什么？

我的矩阵会像这样吗？每个方程 3x3 还是我将它们组合在一起？

[ X X X']
[ Y Y Y']
[ 1 1 1 ]
4

1 回答 1

2

您要查找的是一个转换矩阵，然后您可以使用该矩阵将某个当前 (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向量的点积和矩阵的最上面一行，yield 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次数与乘以matrixthn次方相同。幸运的是，我们有一种有效的方法来计算矩阵的幂 - 它称为平方取幂（实际上也适用于常规数字，但这里我们关注的是乘法矩阵，并且逻辑仍然适用）。简而言之，我们不是一次又一次地将数字或矩阵相乘，而是将其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向量与此相乘，以获得最终结果。

于 2021-12-25T02:37:57.027 回答