Matemáticas en la programación de videojuegos

https://stackoverflow.com/questions/5817491

26-10-2019
|

Pregunta

Acabo de terminar el segundo año en UNI haciendo un curso de juegos, esto siempre me ha estado molestando cómo están relacionadas las matemáticas y la programación de juegos. Hasta ahora he estado usando Vectors, Matrices, y Quaternions En los juegos, puedo poner en pie cómo se ajustan a los juegos.

Esto es un General Question Sobre la relación entre las matemáticas y la programación para gráficos en tiempo real, tengo curiosidad sobre cuán dinámicas son las matemáticas. ¿Es un caso en el que todas las fórmulas y derivadas están predefinidas (semi definidas)?

¿Es incluso factible calcular derivadas/integrales en tiempo real?

Estas son algunas de las cosas que no veo cómo encajan dentro de la programación/matemáticas como ejemplo.

MacLaurin/Talor Series Puedo ver que esto es útil, pero ¿es el caso que deba aprobar su función y sus derivadas, o puede pasarla una sola función y hacer que resuelva las derivadas para usted?
```
MacLaurin(sin(X)); or MacLaurin(sin(x), cos(x), -sin(x));
```
Derivatives /Integrals Esto está relacionado con el primer punto. Calculando el y' de una función realizada dinámicamente en el tiempo de ejecución o es algo que se hace estáticamente quizás con variables dentro de una función establecida.
```
f = derive(x); or f = derivedX;
```
Bilnear Patches Aprendimos esto como una forma de generar paisajes en pequeños trozos que podrían ser 'coser' juntos, ¿es esto algo que sucede en los juegos? Nunca he oído hablar de esto (concedido mis conocimientos es muy limitado) que se utiliza con métodos de procedimiento o de otra manera. Lo que he hecho hasta ahora implica matrices para la información del vértice que se está procesando.

Lo siento si esto está fuera de tema, pero la comunidad aquí parece acertada, en este tipo.

Gracias.

Solución

La respuesta de Skizz es cierta cuando se toma literalmente, pero solo se requiere un pequeño cambio para que sea posible calcular la derivada de una función C ++. Modificamos la función de Skizz f a

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

Ahora es posible escribir una función C ++ para calcular la derivada de F con respecto a x. Aquí hay un programa independiente completo para calcular la derivada de f. Es exacto (a la precisión de la máquina) ya que no está utilizando un método inexacto como las diferencias finitas. Explico cómo funciona en un papel Escribí. Se generaliza a derivadas más altas. Tenga en cuenta que gran parte del trabajo es realizado estáticamente por el compilador. Si aumenta la optimización y su compilador ingresa decentemente, debe ser tan rápido como cualquier cosa que pueda escribir a mano para funciones simples. (¡A veces más rápido! En particular, es bastante bueno para amortizar el costo de calcular F y F 'simultáneamente porque hace que la eliminación de la subexpresión común sea más fácil para el compilador que detecte que si escribe funciones separadas para F y 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;
}

Imprime los resultados 6 y 4 Como deberías esperar. Prueba otras funciones f. Un buen ejercicio es tratar de resolver las reglas para permitir la resta, la división, las funciones Trig, etc.

Otros consejos

2) Los derivados e integrales generalmente no se calculan en grandes conjuntos de datos en tiempo real, es demasiado costoso. En cambio son precomputados. Por ejemplo (en la parte superior de mi cabeza) para representar un solo medio de dispersión Bo Sun et al. Use su "modelo de luz de aire" que consiste en muchos atajos algebraicos para obtener una mesa de búsqueda precomputada.

3) La transmisión de grandes conjuntos de datos es un gran tema, especialmente en terreno.

Muchas de las matemáticas que encontrarás en los juegos es resolver problemas muy específicos, y generalmente se mantiene simple. El álgebra lineal se usa mucho más que cualquier cálculo. En los gráficos (me gusta más), muchos de los algoritmos provienen de la investigación realizada en la academia, y luego los programadores de juegos modifican para la velocidad: aunque incluso la investigación académica hace que la velocidad sea su objetivo en estos días.

Recomiendo los dos libros de detección de colisiones en tiempo real y representación en tiempo real, que contienen las entrañas de la mayoría de las matemáticas y conceptos utilizados en la programación de motores de juegos.

Creo que hay un problema fundamental con su comprensión del lenguaje C ++ en sí. Las funciones en C ++ no son las mismas que las funciones matemáticas. Entonces, en C ++, podría definir una función (que ahora llamaré métodos para evitar confusiones) para implementar una función matemática:

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

En C ++, no hay forma de hacer nada con el método F que no sea obtener el valor de f (x) para una x dada. La función matemática f (x) se puede transformar con bastante facilidad, f '(x), por ejemplo, que en el ejemplo anterior es f' (x) = 2x+ 4. Para hacer esto en C ++ necesitaría definir un método DF (x):

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

No puedes hacer esto:

get_derivative (f(x));

y tener el método get_derivative Transforme el método f (x) para usted.

Además, tendría que asegurarse de que cuando quisiera la derivada de F que llame el método DF. Si llamó al método para la derivada de G por accidente, sus resultados serían incorrectos.

Sin embargo, podemos aproximar la derivada de F (x) para una x dada:

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;
}

Pero esto es muy inestable y bastante inexacto.

Ahora, en C ++ puedes crear una clase para ayudar aquí:

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
};

y crear nuestra función matemática específica:

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
};

y pase una instancia de esta clase a una rutina de expansión en serie:

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

Pero todavía tenemos que crear un método para la derivada de la función nosotros mismos, pero al menos no vamos a llamar accidentalmente al incorrecto.

Ahora, como otros han declarado, los juegos tienden a favorecer la velocidad, por lo que se simplifican muchas de las matemáticas: interpolación, tablas precomputadas, etc.

La mayoría de las matemáticas en los juegos están diseñadas para calcular lo más barato posible, la velocidad del comercio sobre precisión. Por ejemplo, gran parte de los números que cruje usa enteros o flotadores de precisión única en lugar de dobles.

No estoy seguro de sus ejemplos específicos, pero si puede definir una fórmula barata (para calcular) para un derivado de antemano, entonces eso es preferible calcular las cosas sobre la marcha.

En los juegos, el rendimiento es primordial. No encontrará nada que se haga dinámicamente cuando se pueda hacer estáticamente, a menos que conduzca a un aumento notable de la fidelidad visual.

Es posible que esté interesado en compilar la diferenciación simbólica. Esto se puede hacer (en principio) con plantillas C ++. No tengo idea de si los juegos hacen esto en la práctica (la diferenciación simbólica podría ser demasiado costosa para programar bien y un uso tan extenso de la plantilla podría ser demasiado costoso en el tiempo de compilación, no tengo idea).

Sin embargo, pensé que podría encontrar la discusión de este tema interesante. Google "Derivado simbólico de plantilla C ++" da algunos artículos.

Hay muchas respuestas excelentes si está interesado en el cálculo simbólico y el cálculo de derivados.

Sin embargo, solo como una verificación de cordura, este tipo de cálculo simbólico (analítico) no es práctico en tiempo real en el contexto de los juegos.

En mi experiencia (que es más geometría 3D en la visión por computadora que los juegos), la mayor parte del cálculo y las matemáticas en la geometría 3D se adentra con calcular las cosas fuera de línea y luego codificar para implementar estas matemáticas. Raramente, rara vez necesitará calcular las cosas simbólicamente sobre la marcha y luego obtener fórmulas analíticas sobre la marcha de esta manera.

¿Pueden verificar algún programador de juegos?

1), 2)

La serie Maclaurin/Taylor (1) se construye a partir de derivados (2) en cualquier caso.

Sí, es poco probable que necesite calcular simbólicamente cualquiera de estos en tiempo de ejecución, pero seguro user207442La respuesta es genial si la necesitas.

Lo que encuentra es que necesita realizar un cálculo matemático y que debe hacerlo en un tiempo razonable, o a veces muy rápido. Para hacer esto, incluso si reutiliza las soluciones de otros, deberá comprender el análisis básico.

Si tiene que resolver el problema usted mismo, el alza es que a menudo solo necesita una respuesta aproximada. Esto significa que, por ejemplo, una expansión de tipo en serie puede permitirle reducir una función compleja a un simple lineal o cuadrático, que será muy rápido.

Para integrales, a menudo puede calcular el resultado numéricamente, pero siempre será mucho más lento que una solución analítica. La diferencia puede ser la diferencia entre ser práctico o no.

En resumen: sí, debe aprender las matemáticas, pero para escribir el programa en lugar de que el programa lo haga por usted.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow