Математика в программировании видеоигр - PullRequest
5 голосов
/ 28 апреля 2011

Я только что закончил второй год в 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 Мы узнали это как способ создания ландшафта небольшими порциями, которые можно «сшить» вместе, это происходит в играх? Я никогда не слышал об этом (при условии, что мои знания очень ограничены), который используется с процедурными методами или иным образом. То, что я сделал до сих пор, включает массивы для обработки информации о вершинах.

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

Спасибо.

Ответы [ 8 ]

5 голосов
/ 28 апреля 2011

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

2 голосов
/ 28 апреля 2011

Я думаю, что есть фундаментальная проблема с вашим пониманием самого языка 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)
}

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

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

2 голосов
/ 28 апреля 2011

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

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

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

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

1 голос
/ 28 апреля 2011

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

1 голос
/ 28 апреля 2011

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

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

0 голосов
/ 29 апреля 2011

1), 2)

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

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

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

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

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

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

0 голосов
/ 28 апреля 2011

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

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

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

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

0 голосов
/ 28 апреля 2011

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

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

...