Transcript game s sin
CSCE 552 Spring 2011 Math By Jijun Tang Languages C/C++ Java Script: Flash, Python, LISP, etc. C# XNA for PC and Xbox Data Structures: Array Elements are adjacent in memory (great cache consistency) They never grow or get reallocated Use dynamic incremental array concept GCC has a remalloc function In C++ there's no check for going out of bounds Requires continuous memory space Use vector if possible Keep in mind of checking boundaries Inserting and deleting elements in the middle is expensive Lists Hash Table Stack/Queue/Priority Queue Bits Inheritance Models “is-a” relationship Extends behavior of existing classes by making minor changes Do not overuse, if possible, use component systerm UML diagram representing inheritance Enemy Boss SuperDuperBoss Component Systems Component system organization GameEntity Name = sword RenderComp CollisionComp DamageComp PickupComp WieldComp Object Factory Creates objects by name Pluggable factory allows for new object types to be registered at runtime Extremely useful in game development for passing messages, creating new objects, loading games, or instantiating new content after game ships Singleton Implements a single instance of a class with global point of creation and access For example, GUI Don't overuse it!!! Singleton static Singleton & GetInstance(); // Regular member functions... static Singleton uniqueInstance; Adapter Convert the interface of a class into another interface clients expect. Adapter lets classes work together that couldn't otherwise because of incompatible interfaces Real interface Observer Allows objects to be notified of specific events with minimal coupling to the source of the event Two parts subject and observer Ad-hoc Modular DAG Layered Overview: Initialization/Shutdown The initialization step prepares everything that is necessary to start a part of the game The shutdown step undoes everything the initialization step did, but in reverse order Initialization/Shutdown Resource Acquisition Is Initialization A useful rule to minimalize mismatch errors in the initialization and shutdown steps Means that creating an object acquires and initializes all the necessary resources, and destroying it destroys and shuts down all those resources Optimizations Fast shutdown Warm reboot Overview: Main Game Loop Games are driven by a game loop that performs a series of tasks every frame Some games have separate loops for the front and the game itself Other games have a unified main loop Must finish a loop within 0.017 second Tasks of Main Game Loop Handling time Gathering player input Networking Simulation Collision detection and response Object updates Rendering Other miscellaneous tasks Sample Game Loop Main Game Loop Structure Hard-coded loops Multiple game loops: for each major game state Consider steps as tasks to be iterated through Coupling Can decouple the rendering step from simulation and update steps Results in higher frame rate, smoother animation, and greater responsiveness Implementation is tricky and can be error-prone Execution Order of Main Loop Most of the time it doesn't matter In some situations, execution order is important Can help keep player interaction seamless Can maximize parallelism Exact ordering depends on hardware Example (Open Source Rail Simulator) Simulator = new Simulator(settings, args[0]); if (args.Length == 1) Simulator.SetActivity(args[0]); else Simulator.SetExplore(args[0], args[1], args[2], args[3], args[4]); Simulator.Start(); Viewer = new Viewer3D(Simulator); Viewer.Initialize(); Viewer.Run(); //Frame Updates Here Simulator.Stop(); //Check if exit condition met Math Applied Trigonometry Trigonometric functions Defined using right triangle y sin a h h y a x x cos a h y sin a tan a x cos a Applied Trigonometry Angles measured in radians radians degrees p 180 180 p degrees radians Full circle contains 2p radians Applied Trigonometry Sine and cosine used to decompose a point into horizontal and vertical components y r r sin a a r cos a x Trigonometry Trigonometric identities sin a sin a cos a sin a p 2 cos a cos a tan a tan a sin a cos a p 2 cos a sin a p 2 sin 2 a cos 2 a 1 sin a cos a p 2 sin a sin a p sin a p cos a cos a p cos a p Inverse trigonometric functions Return angle for which sin, cos, or tan function produces a particular value If sin a = z, then a = sin-1 z If cos a = z, then a = cos-1 z If tan a = z, then a = tan-1 z arcs Applied Trigonometry Law of sines a b c sin a sin sin g a c Law of cosines c 2 a 2 b2 2ab cos g b g a Reduces to Pythagorean theorem when g = 90 degrees Vectors and Scalars Scalars represent quantities that can be described fully using one value Mass Time Distance Vectors describe a magnitude and direction together using multiple values Examples of vectors Difference between two points Velocity of a projectile Magnitude is the distance between the points Direction points from one point to the other Magnitude is the speed of the projectile Direction is the direction in which it’s traveling A force is applied along a direction Visualize Vectors The length represents the magnitude The arrowhead indicates the direction Multiplying a vector by a scalar changes the arrow’s length 2V V –V Vectors Add and Subtraction Two vectors V and W are added by placing the beginning of W at the end of V Subtraction reverses the second vector V W V+W W V–W V V –W High-Dimension Vectors An n-dimensional vector V is represented by n components In three dimensions, the components are named x, y, and z Individual components are expressed using the name as a subscript: V 1, 2,3 Vx 1 Vy 2 Vz 3 Add/Subtract Componentwise V W V1 W1 ,V2 W2 , ,Vn Wn V W V1 W1 ,V2 W2 , ,Vn Wn Vector Magnitude The magnitude of an n-dimensional vector V is given by V n 2 V i i 1 In three dimensions, this is V Vx2 Vy2 Vz2 Vector Normalization A vector having a magnitude of 1 is called a unit vector Any vector V can be resized to unit length by dividing it by its magnitude: V ˆ V V This process is called normalization Matrices A matrix is a rectangular array of numbers arranged as rows and columns A matrix having n rows and m columns is an n m matrix 1 2 3 M 4 5 6 At the right, M is a 2 3 matrix If n = m, the matrix is a square matrix Matrix Representation The entry of a matrix M in the i-th row and j-th column is denoted Mij For example, 1 2 3 M 4 5 6 M 11 1 M 21 4 M 12 2 M 22 5 M 13 3 M 23 6 Matrix Transpose The transpose of a matrix M is denoted MT and has its rows and columns exchanged: 1 2 3 M 4 5 6 1 4 T M 2 5 3 6 Vectors and Matrices An n-dimensional vector V can be thought of as an n 1 column matrix: V V1 , V2 , V1 V2 , Vn Vn Or a 1 n row matrix: V T V1 V2 Vn Vectors and Matrices Product of two matrices A and B Number of columns of A must equal number of rows of B Entries of the product are given by m AB ij Aik Bkj k 1 If A is a n m matrix, and B is an m p matrix, then AB is an n p matrix Vectors and Matrices Example matrix product 2 3 2 1 8 13 M 1 1 4 5 6 6 M 11 2 2 3 4 M 12 2 1 3 5 13 8 M 21 1 2 1 4 6 M 22 1 1 1 5 6 Vectors and Matrices Matrices are used to transform vectors from one coordinate system to another In three dimensions, the product of a matrix and a column vector looks like: M 11 M 21 M 31 M 12 M 22 M 32 M 13 Vx M 11Vx M 12Vy M 13Vz M 23 Vy M 21Vx M 22Vy M 23Vz M 33 Vz M 31Vx M 32Vy M 33Vz Identity Matrix In For any n n matrix M, the product with the identity matrix is M itself I nM = M MIn = M Invertible An n n matrix M is invertible if there exists another matrix G such that 1 0 0 1 MG GM I n 0 0 0 0 1 The inverse of M is denoted M-1 Properties of Inverse Not every matrix has an inverse A noninvertible matrix is called singular Whether a matrix is invertible can be determined by calculating a scalar quantity called the determinant Determinant The determinant of a square matrix M is denoted det M or |M| A matrix is invertible if its determinant is not zero For a 2 2 matrix, a b a b det ad bc c d c d Determinant The determinant of a 3 3 matrix is m11 m12 m13 m21 m22 m23 m11 m31 m32 m33 m22 m23 m32 m33 m12 m21 m23 m31 m33 m13 m21 m22 m31 m32 m11 m22 m33 m23 m32 m12 m21m33 m23m31 m13 m21m32 m22 m31 Inverse Explicit formulas exist for matrix inverses These are good for small matrices, but other methods are generally used for larger matrices In computer graphics, we are usually dealing with 2 2, 3 3, and a special form of 4 4 matrices Inverse of 2x2 and 3x3 The inverse of a 2 2 matrix M is 1 M 22 M 12 M det M M 21 M11 1 The inverse of a 3 3 matrix M is M 22 M 33 M 23 M 32 1 1 M M 23 M 31 M 21M 33 det M M 21M 32 M 22 M 31 M13 M 32 M12 M 33 M11M 33 M13 M 31 M 12 M 31 M11M 32 M12 M 23 M13 M 22 M13 M 21 M11M 23 M11M 22 M12 M 21 4x4 A special type of 4 4 matrix used in computer graphics looks like R11 R21 M R31 0 R12 R13 R22 R23 R32 R33 0 0 Tx Ty Tz 1 R is a 3 3 rotation matrix, and T is a translation vector Inverse of 4x4 M 1 R 1 0 R111 1 R T R211 R311 1 0 R121 R131 R221 R231 R321 R331 0 0 R 1T x 1 R T y R 1T z 1 General Matrix Inverse (AB) -1 = B-1A-1 A general nxn matrix can be inverted using methods such as Gauss-Jordan elimination Gaussian elimination LU decomposition Gauss-Jordan Elimination Gaussian Elimination The Dot Product The dot product is a product between two vectors that produces a scalar The dot product between two n-dimensional vectors V and W is n given by V W VW i i i 1 In three dimensions, V W VxWx VyWy VzWz Dot Product Usage The dot product can be used to project one vector onto another V a V cos a VW W W Dot Product Properties The dot product satisfies the formula V W V W cos a a is the angle between the two vectors Dot product is always 0 between perpendicular vectors If V and W are unit vectors, the dot product is 1 for parallel vectors pointing in the same direction, -1 for opposite Self Dot Product The dot product of a vector with itself produces the squared magnitude VV V V V 2 Often, the notation V 2 is used as shorthand for V V The Cross Product The cross product is a product between two vectors the produces a vector The cross product only applies in three dimensions The cross product is perpendicular to both vectors being multiplied together The cross product between two parallel vectors is the zero vector (0, 0, 0) Illustration The cross product satisfies the trigonometric relationship V W V W sin a This is the area of the parallelogram formed by V V and W ||V|| sin a a W Area and Cross Product The area A of a triangle with vertices P1, P2, and P3 is thus given by 1 A P2 P1 P3 P1 2 Rules Cross products obey the right hand rule If first vector points along right thumb, and second vector points along right fingers, Then cross product points out of right palm W V V W Reversing order of vectors negates the cross product: Rules in Figure Formular The cross product between V and W is V W VyWz VzWy , VzWx VxWz , VxWy VyWx A helpful tool for remembering this formula is the pseudodeterminant (x, y, z) are unit vectors Alternative The cross product can also be expressed as the matrix-vector product 0 V W Vz Vy Vz 0 Vx Vy Wx Vx Wy 0 Wz The perpendicularity property means V W V 0 V W W 0