Математика в программировании видеоигр

Question

Я только что закончил второй год в Uni, изучая игровой курс, меня всегда беспокоило, как связаны математика и игровое программирование. До сих пор я использую Vectors, Matrices, а также Quaternions в играх я могу понять, как они вписываются в игры.

Это General Question насчет отношений между математикой и программированием для графики в реальном времени, мне интересно, насколько динамична математика. Это тот случай, когда все формулы и производные предопределены (полуопределены)?

Можно ли рассчитать производные / интегралы в реальном времени?

Вот некоторые вещи, которые я не вижу, как они вписываются в программирование / математику. В качестве примера.

1. MacLaurin/Talor Series Я вижу, что это полезно, но так ли это, что вы должны передать свою функцию и ее производные, или вы можете передать ей одну функцию и заставить ее работать для вас?

   MacLaurin(sin(X)); or MacLaurin(sin(x), cos(x), -sin(x));
   

2. Derivatives /Integrals Это связано с первым пунктом. Расчет y' функции, выполняемой динамически во время выполнения, или это то, что статически выполняется, возможно, с переменными внутри заданной функции.

   f = derive(x); or f = derivedX;
   

3. Bilnear Patches Мы научились этому как способу создавать пейзажи небольшими порциями, которые можно "сшить" вместе, это то, что происходит в играх? Я никогда не слышал об этом (при условии, что мои знания очень ограничены), с использованием процедурных методов или иным образом. То, что я сделал до сих пор, включает в себя массивы для обработки информации о вершинах.

Извините, если это не по теме, но сообщество здесь, кажется, точно, в этом роде.

Благодарю.

Answer 1

Ответ Скиза верен, если понимать его буквально, но требуется лишь небольшое изменение, чтобы сделать возможным вычисление производной функции C++. Мы модифицируем функцию скиза 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, Хорошее упражнение - попытаться выработать правила, позволяющие выполнять вычитание, деление, триггерные функции и т. Д.

Answer 2

2) Производные и интегралы обычно не рассчитываются на больших наборах данных в режиме реального времени, это слишком дорого. Вместо этого они предварительно вычисляются. Например (вверху моей головы) для рендеринга одного рассеивающего носителя Bo Sun et al. используйте их "модель авиалайнера", которая состоит из множества алгебраических сочетаний клавиш, чтобы получить предварительно вычисленную таблицу поиска.

3) Потоковая передача больших массивов данных - большая тема, особенно на местности.

Большая часть математики, с которой вы столкнетесь в играх, предназначена для решения очень специфических задач, и обычно она проста. Линейная алгебра используется гораздо больше, чем любое исчисление. В графике (мне это нравится больше всего) многие алгоритмы основаны на исследованиях, проведенных в академических кругах, а затем они модифицируются для скорости программистами игр: хотя даже академические исследования делают скорость своей целью в наши дни.

Я рекомендую две книги "Обнаружение столкновений в реальном времени" и "Рендеринг в реальном времени", в которых содержатся основные сведения о математических понятиях и понятиях, используемых в программировании игрового движка.

Answer 3

Я думаю, что есть фундаментальная проблема с вашим пониманием самого языка C++. Функции в C++ - это не то же самое, что математические функции. Итак, в C++ вы можете определить функцию (которую я теперь буду называть методами, чтобы избежать путаницы) для реализации математической функции:

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

В C++ нет способа сделать что-либо с методом f, кроме как получить значение f(x) для данного x. Математическая функция f(x) может быть преобразована довольно легко, например, f'(x), которая в приведенном выше примере является f'(x) = 2x + 4. Чтобы сделать это в C++, вам нужно определить метод дф (х):

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, ваши результаты будут неверными.

Однако мы можем приблизить производную f(x) для данного 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)
}

но мы все еще должны создать метод для производной функции сами, но по крайней мере мы не собираемся случайно вызывать неправильный.

Теперь, как утверждают другие, игры, как правило, предпочитают скорость, поэтому многие математические операции упрощены: интерполяция, предварительно вычисленные таблицы и т. Д.

Answer 4

Большая часть математики в играх предназначена для того, чтобы как можно дешевле вычислить скорость торговли за точность. Например, большая часть обработки чисел использует целые числа или числа с одинарной точностью, а не удваивается.

Не уверен насчет ваших конкретных примеров, но если вы можете заранее определить дешевую (для расчета) формулу для производной, то это предпочтительнее, чем вычислять вещи на лету.

Answer 5

В играх производительность имеет первостепенное значение. Вы не найдете ничего, что будет сделано динамически, когда это может быть сделано статически, если только это не приведет к заметному увеличению визуальной точности.

Answer 6

1), 2)

Ряды Маклаурина / Тейлора (1) построены из производных (2) в любом случае.

Да, вам вряд ли понадобится символически вычислять любой из них во время выполнения - но наверняка sigfpe, если вам это нужно.

Вы обнаружите, что вам нужно выполнить математический расчет и сделать это за разумное время, а иногда и очень быстро. Чтобы сделать это, даже если вы повторно используете решения других, вам нужно будет понять базовый анализ.

Если вам нужно решить проблему самостоятельно, положительным моментом является то, что вам часто требуется только приблизительный ответ. Это означает, что, например, разложение по последовательному типу вполне может позволить вам уменьшить сложную функцию до простой линейной или квадратичной, что будет очень быстрым.

Для интегралов вы можете часто вычислять результат численно, но он всегда будет намного медленнее, чем аналитическое решение. Разница вполне может быть разницей между практичностью или нет.

Короче говоря: да, вам нужно изучать математику, но для того, чтобы написать программу, а не делать это за вас.

Answer 7

Есть много отличных ответов, если вы заинтересованы в символьных вычислениях и вычислениях производных.

Однако, так же, как проверка работоспособности, этот вид символического (аналитического) исчисления не практичен в реальном времени в контексте игр.

По моему опыту (который больше 3D-геометрии в компьютерном зрении, чем в играх), большая часть математических вычислений и математики в 3D-геометрии приходит путем заранее вычислений в автономном режиме и последующего кодирования для реализации этой математики. Очень редко вам нужно будет символически вычислять вещи на лету, а затем таким образом получать аналитические формулы на лету.

Может ли кто-нибудь из разработчиков игр проверить это?

Answer 8

Возможно, вас заинтересует символьная дифференциация времени компиляции. Это можно (в принципе) сделать с помощью шаблонов C++. Не знаю, делают ли игры это на практике (символическая дифференциация может быть слишком дорогой, чтобы правильно программировать, а такое широкое использование шаблонов может быть слишком дорогим во время компиляции, я понятия не имею).

Однако я подумал, что обсуждение этой темы может показаться вам интересным. Поиск в Google "символьная производная шаблона C++" дает несколько статей.