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. 希望这能让我们更容易看到我们想要点的向量startVec([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 回答