编程视频游戏中的数学

Question

我刚刚完成了大学的第二年，修了一个游戏课程，一直困扰我的问题是数学和游戏编程的关系。到目前为止，我在游戏中一直在使用向量、矩阵和四元数，我可以理解它们如何适用于游戏。

这是关于实时图形数学与编程之间关系的一般问题，我对其中的数学动态性很好奇。所有的公式和导数是否都是预定义的（半定义的）？

在实时计算中计算导数/积分是否可行？

这些都是我不明白如何将它们融入编程/数学的一些事物的例子。

1.

MacLaurin/Taylor Series我可以看出这很有用，但是是必须传入函数及其导数，还是可以只传入一个函数然后让它自动计算导数呢？

MacLaurin(sin(X)); 或者 MacLaurin(sin(x), cos(x), -sin(x));

导数/积分这与第一个问题相关。计算函数的y'是在运行时动态完成的，还是静态地通过函数内部的变量完成的呢？

f = derive(x); 或者 f = derivedX;

双线性补丁我们学到了这种方法可以将小块生成的地形拼接在一起，这在游戏中会发生吗？我从未听说过（尽管我的知识非常有限）它与程序化方法或其他方法一起使用。到目前为止，我所做的涉及对顶点信息进行数组处理。

抱歉如果这个话题有些偏离，但是这里的社区似乎对这种事情很在行。

谢谢。

- user245019

---

有一个游戏开发堆栈交换网站，涵盖了像这样的问题：http://gamedev.stackexchange.com/ - 一二三

@一二三 是的。有点讽刺的是，我在gamedev上发布了一个关于游戏编程的问题，然后建议我去stackoverflow上发布:) 赢不了啊。 - user245019

Answer 1

Skizz的回答在字面上是正确的，但只需要进行小的更改就可以计算C++函数的导数。我们修改skizz的函数f为：

template<class Float> f (Float x)
{
  return x * x + Float(4.0f) * x + Float(6.0f); // f(x) = x^2 + 4x + 6
}

现在可以编写一个C++函数来计算f对x的导数。下面是一个完整的自包含程序来计算f的导数。它是精确的（达到机器精度），因为它不使用像有限差分这样的不准确方法。我在我写的论文中解释了它的工作原理。它推广到更高阶导数。请注意，编译器静态地完成了大部分工作。如果你打开优化，并且你的编译器能够很好地内联，对于简单函数，它应该和你手写的任何东西一样快。 （有时更快！特别是，它非常擅长分摊同时计算f和f'的成本，因为它使得编译器更容易发现公共子表达式消除，而不是如果你为f和f'编写单独的函数。）

using namespace std;

template<class Float>
Float f(Float x)
{
  return x * x + Float(4.0f) * x + Float(6.0f);
}

struct D
{
  D(float x0, float dx0 = 0) : x(x0), dx(dx0) { }
  float x, dx;
};

D operator+(const D &a, const D &b)
{
  // The rule for the sum of two functions.
  return D(a.x+b.x, a.dx+b.dx);
}

D operator*(const D &a, const D &b)
{
  // The usual Leibniz product rule.
  return D(a.x*b.x, a.x*b.dx+a.dx*b.x);
}

// Here's the function skizz said you couldn't write.
float d(D (*f)(D), float x) {
  return f(D(x, 1.0f)).dx;
}

int main()
{
  cout << f(0) << endl;
  // We can't just take the address of f. We need to say which instance of the
  // template we need. In this case, f<D>.
  cout << d(&f<D>, 0.0f) << endl;
}

它会打印出结果 6 和 4，正如你所期望的。尝试其他函数 f。一个不错的练习是尝试推导出允许减法、除法、三角函数等规则。

- sigfpe

---

哇！这真的很有趣！感谢分享你的论文。 - epaik

我印象深刻。它做了比只实现f'（x）函数更多的计算，我不确定二阶及更高阶微分是如何工作的（即f''（x * x * x）=> 6 * x）。我猜你可以有一个模板化的pow函数来计算每个微分。现在已经午夜了，我的大脑正在缓慢融化... - Skizz

它同时计算f和f'，这就是“额外的工作”。通常情况下，您希望同时计算两者，但并非总是如此。计算更高阶导数的代码在我的论文中。实际上很简单 - 您只需将此方法应用于自身即可。但是，您还需要将“D”作为模板。 - sigfpe

@sigfpe：你的论文链接已经失效。 - legends2k

@legends2k 谢谢你告诉我。请尝试使用 https://dl.dropboxusercontent.com/u/828035/paper.pdf - sigfpe

Answer 2

我认为你对C++语言本身的理解存在根本性问题。在C++中，函数并不等同于数学函数。因此，在C++中，你可以定义一个函数（我现在称其为方法以避免混淆）来实现一个数学函数：

float f (float x)
{
  return x * x + 4.0f * x + 6.0f; // f(x) = x^2 + 4x + 6
}

在C++中，除了获取给定x的f(x)值之外，没有其他方法可以处理方法f。数学函数f(x)可以很容易地转换为f'(x)，例如，在上面的示例中，f'(x) = 2x + 4。要在C++中实现这一点，您需要定义一个名为df(x)的方法：

float df (float x)
{
  return 2.0f * x + 4.0f; //  f'(x) = 2x + 4
}

您不能这样做：

get_derivative (f(x));

并且有一个方法get_derivative可以为您转换f(x)的方法。

另外，您需要确保当您需要f的导数时，调用df方法。如果您错误地调用了g的导数方法，则结果将不正确。

但是，我们可以近似计算给定x的f(x)的导数：

float d (float (*f) (float x), x) // pass a pointer to the method f and the value x
{
  const float epsilon = a small value;
  float dy = f(x+epsilon/2.0f) - f(x-epsilon/2.0f);
  return epsilon / dy;
}

但是这种方法非常不稳定且不太准确。

现在，在C++中，您可以创建一个类来帮助解决这个问题：

class Function
{
public:
  virtual float f (float x) = 0; // f(x)
  virtual float df (float x) = 0; // f'(x)
  virtual float ddf (float x) = 0; // f''(x)
  // if you wanted further transformations you'd need to add methods for them
};

并创建我们特定的数学函数：

class ExampleFunction : Function
{
  float f (float x) { return x * x + 4.0f * x + 6.0f; } // f(x) = x^2 + 4x + 6 
  float df (float x) { return 2.0f * x + 4.0f; } //  f'(x) = 2x + 4
  float ddf (float x) { return 2.0f; } //  f''(x) = 2
};

并将该类的实例传递给级数展开程序：

float Series (Function &f, float x)
{
   return f.f (x) + f.df (x) + f.ddf (x); // series = f(x) + f'(x) + f''(x)
}

不过，我们仍然需要自己创建函数导数的方法，但至少我们不会意外调用错误的方法。

现在，正如其他人所说，游戏往往更注重速度，因此许多数学问题都被简化了：插值、预先计算的表格等等。

- Skizz

---

与您的说法相反，C++编译器完全可以为您精确地区分函数。无需手工完成所有工作，也不需要采用有限差分这样可怕的方法。请参见我的答案。 - sigfpe

Answer 3

2) 在实时处理大数据集时，通常不会计算导数和积分，因为这太昂贵了。相反，它们是预先计算的。例如（在我脑海中）为了呈现单个散射介质，Bo Sun等人使用他们的“空气光模型”，其中包含很多代数快捷方式来获取预先计算的查找表。

3) 流式传输大数据集是一个重要的话题，特别是在地形方面。

在游戏中遇到的大部分数学问题都是解决非常具体的问题，并且通常保持简单。线性代数比微积分更常用。在图形方面（我最喜欢的领域），许多算法来自于学术研究，然后由游戏程序员进行速度修改：即使学术研究如今也将速度作为目标。

我推荐两本书《实时碰撞检测》和《实时渲染》，它们包含了游戏引擎编程中使用的大部分数学和概念的精华。

- user515136

Answer 4

游戏中的大部分数学计算都是为了尽可能地降低计算成本，以速度换取准确性。例如，许多数字计算使用整数或单精度浮点数而不是双精度浮点数。

关于您的具体示例不确定，但如果您可以预先定义一个便宜（易于计算）的导数公式，那么这比即时计算更可取。

- Richie Cotton

Answer 5

在游戏中，性能至关重要。除非它能显著提高视觉保真度，否则不会找到任何可以动态完成的事情，而不是静态完成。

- Puppy

Answer 6

你可能会对编译时符号微分感兴趣。理论上，这可以使用c++模板完成。不知道游戏实际上是否这样做（符号微分可能太昂贵而无法正确编程，如此广泛的模板使用可能在编译时太昂贵，我不知道）。

然而，我认为你可能会发现这个话题的讨论很有趣。在谷歌上搜索“c++模板符号导数”会得到一些文章。

- Tom

---

它被称为“自动微分”，这就是我在我的答案中使用的方法。 - sigfpe

Answer 7

如果您对符号计算和导数计算感兴趣，那么有很多好的答案。

然而，就像一个理智的检查一样，在游戏的实时环境中进行这种符号（分析）微积分并不实用。

根据我的经验（更多是在计算机视觉的三维几何方面而不是游戏），大部分的三维几何计算和数学都是离线计算，然后编码实现这些数学。很少需要在运行时符号计算，然后以此获得即时的解析公式。

有没有游戏程序员可以验证一下？

- Chris A.

Answer 8

1) 2)

Maclaurin/Taylor公式(1)是从导数(2)构建的。

是的，你很少需要在运行时对它们进行符号计算，但如果你需要的话，user207442的答案非常好。

你会发现自己需要进行数学计算，并且需要在合理的时间内完成，有时甚至需要非常快。为了做到这一点，即使你重用别人的解决方案，你也需要了解基本分析知识。

如果你确实需要自己解决问题，好处是你通常只需要一个近似的答案。这意味着，例如，一个级数类型的展开可以将复杂的函数简化为简单的线性或二次函数，这样会非常快。

对于积分，你通常可以通过数值计算来计算结果，但它总是比解析解慢得多。这个差异可能会决定是否可行。

简而言之: 是的，你需要学习数学，但是为了编写程序而不是让程序替你完成。

- Keith