Matematica a Programmazione Video Games

Question

Ho appena finito secondo anno di Uni facendo un gioco Naturalmente, questo è sempre stato bugging me come la matematica e la programmazione del gioco sono correlate. Fino ad ora ho usato Vectors, Matrices, e Quaternions nei giochi, non posso stare sotto come questi in forma in giochi.

Questa è una General Question sul rapporto tra matematica e di programmazione per tempo reale grafica, sono curioso di come la matematica dinamica è. Si tratta di un caso in cui sono predefiniti tutte le formule e derivati ??(semi definito)?

E 'anche fattibile per calcolare derivati ??/ integrali in tempo reale?

Queste sono alcune delle cose che non vedo come si inseriscono all'interno di programmazione / matematica A titolo di esempio.

1. MacLaurin/Talor Series posso vedere questo è utile, ma è il caso che si deve passare la vostra funzione e dei suoi derivati, o si può passare una singola funzione e lo hanno funzionato i derivati ??per te?

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

2. Derivatives /Integrals Questo è legato al primo punto. Calcolo del y' di una funzione di fatto in modo dinamico in fase di esecuzione o è questo qualcosa che viene fatto in modo statico, forse con le variabili all'interno di una funzione set.

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

3. Bilnear Patches Abbiamo imparato questo come un modo per generare possibile paesaggi in piccoli pezzi che potrebbero essere 'Sewen' insieme, è questo qualcosa che accade nei giochi? Non ho mai sentito parlare di questo (concessi miei knowlages è molto limitata) essere utilizzato con modalità procedurali o altro. Quello che ho fatto finora coinvolge le matrici per le informazioni vertex essere processesed.

Scusate se questo è fuori tema, ma la comunità qui sembra a posto, in questo genere di cose.

Grazie.

Answer 1

La risposta di Skizz è vero quando preso alla lettera, ma solo una piccola modifica è necessaria per permettere di calcolare la derivata di una funzione C ++. Modifichiamo la funzione di 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
}

È ora possibile scrivere una funzione C ++ per calcolare la derivata di f rispetto a x. Ecco un programma completo autonomo per calcolare la derivata di f. E 'esatto (per precisione della macchina), in quanto non sta utilizzando un metodo impreciso come differenze finite. Mi spiego come funziona in un href="http://homepage.mac.com/sigfpe/paper.pdf" rel="nofollow noreferrer"> carta ho scritto. Si generalizza a derivati ??superiori. Si noti che la maggior parte del lavoro è fatto in modo statico dal compilatore. Se si alza l'ottimizzazione, e le tue inline del compilatore decentemente, dovrebbe essere veloce come tutto ciò che si potrebbe scrivere a mano per le funzioni semplici. (A volte più veloce! In particolare, è abbastanza bravo a ammortamento del costo di calcolo F e F 'contemporaneamente perché rende eliminazione sottoespressione comune più facile per il compilatore da individuare che se si scrivono le funzioni separate per F e 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;
}

Si stampa il risultato 6 e 4 come si dovrebbe aspettare. Prova altre funzioni f. Un bel esercizio è quello di provare a lavorare fuori le regole per consentire la sottrazione, divisione, funzioni ecc Trig.

Answer 2

2) Derivati ??ed integrali di solito non sono calcolati su grandi insiemi di dati in tempo reale, la sua troppo costoso. Invece sono precalcolate. Per esempio (in cima alla mia testa) per rendere un singolo supporto dispersione Bo Sun et al. utilizzare il loro "modello Airlight", che consiste in un sacco di scorciatoie algebriche per ottenere una tabella di ricerca precalcolate.

3) Streaming grandi insiemi di dati è un grande argomento, soprattutto in terreni.

Un sacco di matematica si incontrano nei giochi è quello di risolvere problemi molto specifici, e di solito è mantenuto semplice. L'algebra lineare è usata molto più di qualsiasi calcolo. In Graphics (I come questo la maggior parte) un sacco di algoritmi provengono da ricerche svolte in ambito accademico, e poi si sono modificati per la velocità da parte dei programmatori del gioco:., Anche se fa della ricerca, anche accademici accelerare il loro obiettivo in questi giorni

vi consiglio il due libri rilevamento delle collisioni in tempo reale e il rendering in tempo reale, che contengono le viscere della maggior parte dei matematica e concetti utilizzati nella programmazione motore di gioco.

Answer 3

penso che ci sia un problema fondamentale con la vostra comprensione del linguaggio C ++ per sé. Funzioni in C ++ non sono le stesse funzioni mathmatical. Così, in C ++, è possibile definire una funzione (che io ora chiamare i metodi per evitare confusione) per implementare una funzione mathmatical:

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

In C ++, non c'è modo di fare qualsiasi cosa con il metodo f diverso per ottenere il valore di f (x) per un dato x. La funzione f mathmatical (x) può essere trasformato facilmente, f '(x), ad esempio, che nell'esempio sopra è f' (x) = 2x + 4. Per fare questo in C ++ avresti bisogno di definire un metodo df (x):

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

Non si può fare questo:

get_derivative (f(x));

e hanno il metodo get_derivative trasformare il metodo f (x) per voi.

Inoltre, si dovrebbe fare in modo che, quando si voleva la derivata di f che si chiama il metodo df. Se hai chiamato il metodo per la derivata di g per caso, i risultati sarebbe sbagliato.

Possiamo, tuttavia, approssimare la derivata di f (x) per un dato 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;
}

, ma questo è molto instabile e piuttosto impreciso.

Ora, in C ++ è possibile creare una classe di aiuto qui:

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

e creare la nostra specifica funzione mathmatical:

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

e passare un'istanza di questa classe ad una routine sviluppo in serie:

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

, ma, siamo ancora dover creare un metodo per la funzione derivata di noi stessi, ma almeno non stiamo andando a chiamare accidentalmente quella sbagliata.

Ora, come altri hanno detto, i giochi tendono a favorire la velocità, così un sacco della matematica è semplificata:. Interpolazione, tabelle pre-calcolate, etc

Answer 4

La maggior parte dei giochi di matematica in è stato progettato per come a buon mercato per calcolare il più possibile, la velocità di negoziazione nel corso precisione. Per esempio, la maggior parte del numero di sgranocchiare utilizza numeri interi o in singola precisione galleggia piuttosto che doppie.

Non è sicuro circa i vostri esempi specifici, ma se si può definire un buon mercato (per il calcolo) formula per un anticipo derivato, allora è preferibile calcolare le cose al volo.

Answer 5

Nei giochi, le prestazioni è di primaria importanza. Non troverete tutto ciò che è fatto in modo dinamico quando potrebbe essere fatto in modo statico, a meno che non porta ad un notevole incremento della fedeltà visiva.

Answer 6

Si potrebbe essere interessato a tempo di compilazione differenziazione simbolica. Questo può (in linea di principio) essere fatto con C ++ modelli. Nessuna idea sul fatto che i giochi fanno in pratica (differenziazione simbolica potrebbe essere troppo costoso per programma giusto e tale uso estensivo modello potrebbe essere troppo costoso in fase di compilazione, non ho idea).

Tuttavia, ho pensato che si potrebbe trovare la discussione di questo argomento interessante. Googling "C ++ modello derivato simbolico" dà un paio di articoli.

Answer 7

Ci sono molti grandi risposte se siete interessati nel calcolo simbolico e il calcolo dei derivati.

Tuttavia, proprio come un controllo di integrità, questo tipo di calcolo simbolico (analitica) non è pratico di fare in tempo reale nel contesto di giochi.

Nella mia esperienza (che è più 3D geometria in computer vision di giochi), la maggior parte del calcolo e la matematica in geometria 3D è disponibile in modo da di calcolare le cose non in linea in anticipo e poi codifica per implementare questo matematica. E 'molto raro che avrete bisogno di cose simbolicamente calcolo al volo e quindi ottenere on-the-fly formule analitiche in questo modo.

Possono dei programmatori del gioco verificare?

Answer 8

1), 2)

serie MacLaurin / Taylor (1) sono costruiti derivati ??(2) in ogni caso.

Si, e 'difficile trovare necessità di calcolare simbolicamente uno di questi a run-time - ma di sicuro user207442 ' s risposta è grande se ne avete bisogno.

Cosa si fa trovare è che è necessario eseguire un calcolo matematico e che è necessario farlo in un tempo ragionevole, o, talvolta, molto veloce. Per fare questo, anche se si ri-uso di altre soluzioni, è necessario comprendere analisi di base.

Se si ha a risolvere il problema da soli, il vantaggio è che spesso solo bisogno di una risposta approssimativa. Questo significa che, per esempio, un tipo di espansione serie potrebbe consentire di ridurre una funzione complessa di una semplice lineare o quadratica, che sarà molto veloce.

Per integrali, la si può spesso calcolare il risultato numericamente, ma sarà sempre essere molto più lento di una soluzione analitica. La differenza può essere la differenza tra l'essere pratico o meno.

In breve: Sì, avete bisogno di imparare la matematica, ma per scrivere il programma, piuttosto che avere il programma di farlo per voi

.