
GameDev.Net Discussion Forums Frequently Asked Questions (for individual forums)  Back to the Forums 
Current Server Time 
1:06:38 AM 

FAQ  Math and Physics  
Body  
FAQ for Math and Physics Forum Last Updated 13 August 2009 NOTE: Answers/references for many COMMON questions are located at the bottom half of this FAQ, under the section titled "Technical FAQ". If you have a common question, go there! ******************************************************* Forum Purpose and Policies ******************************************************* 1. What is the purpose of this forum? To discuss solutions and algorithms for math and physics AS RELATED TO game development. This is not a forum to discuss the specifics of a particular graphics API, but it is appropriate to discuss 3D transformations and the like as it applies to math and physics. 2. How do I......(pointinpolygon, collision detection, rotate to align with vector, etc.)? There are several math/physics related problems in game development that are extremely common. In order to minimize the creation of new threads to discuss the same old topic again and again at great length, some of these problems are addressed below, in the "Technical FAQ"s" section of this list. Please do not start a new thread to discuss topics that are covered below, as these topics have already been discussed to the point of exhaustion. 3a. How should I ask for help on homework problems? Since gamedev.net exists to support the game development community, and is not a homework site, please visit another website that is specifically dedicated to math education and homework specifically. Here are a few nice sites: Math Goodies: Free Interactive Math Lessons, Homework Help, ... That one is very nice, and has a dedicated homework forum. Math.com  World of Math Online Nice site, but I didn't see a forum Algebra Homework Help at Algebra.com AAA Math Mathforum Discussion Groups  active, ongoing discussions on many topics related to math 3b. Is it acceptable to post school homework questions? It is NOT appropriate to simply ask for answers to homework questions. Especially those where the answer involves mathematical or physics derivations. Do the work for yourself. The purpose of homework is to teach you to solve problems for yourself, and you"re cheating yourself out of an education if you choose to take the answer from someone else"s hard work and thinking. Think about it. Will you be able to pass a comprehensive inclass examination if you don"t actually learn the material by practicing to solve problems given in homework assignments? I think not. That said, properly stated homework questions are welcome. Here are some rules. (A) Ask your peersother students at your schooland teacher first before posting questions here. (B) This is a forum for game development, and the questions should be related somehow to math and physics in game development. Be prepared to say how your question relates to game development. (C) When asking technical questions, show your own work in detail before asking any question. (D) Never ask for the answer. Ask for a hint or suggestion on how to proceed with finding the answer for yourself. If you are a student, then you are bound by an honor system not to cheat. Its an unwritten contract between you and your teacher and school. YOU are the loser if you break the contract. Many times, it is obvious that a question is purely and simply a homework question. But other times it is less obvious. Do the right thing for YOURSELF and don"t cheat. 3c. What about a school/college/university/studyrelated question that is not homework? In general, if you are not taking a game development class in school, all schoolrelated questions are off topic. Go visit a school related website and save gamedev bandwidth! Technical questions, ones that provide a problem and ask for solutions, are off topic if they are school related. It does not matter if they are not specifically homework. For example, people occasionally ask for help solving problems that appear on college entrance exams. Off topic! There are websites that do cater to this sort of thing. Go visit those sites! So, what is acceptable? It is perfectly acceptable to ask for advicenot about technical problems, but about courses that your should pursue, reference material that you should read, subjects that you should know, AS LONG AS your question is related to math/physics AND you are wanting to pursue game development as a career or hobby! 4. If someone else asks for the answer to a question that is obviously a homework/schoolwork/schoolrelated question, should I answer it? It depends. If the question is posted properly, following the "rules" stated in question (2), then by all means yes, answer the question. If the question is simply asking for an answer, please do not answer. Instead, encourage the poster to solve the problem for him/herself, or to restate the question, referring him/her to this FAQ. 5. What happens when the moderator discovers a post that asks for help on homework? If the post does not follow the rules above (state how the homework relates to a game development project, show your own work, never simply ask for an answer, etc.), then the moderator will close the thread. 6. What if I have a game development question that could be interpreted as a homework question? Describe your game development project, the task you are working on that requires you solve the problem, and show your work. 7. How do I create superscripts and subscripts, for the purpose of formatting equations (example: y = x^{2})? Surround the text to be super or subscripted with the HTML tags "< sup>" and "< /sup>" for superscript, or "< sub>" and < /sub> for subscript. (Take the extra space out, after the < sign.) ******************************************************* Technical FAQ ******************************************************* This section contains brief discussions of a number of VERY common math/physics problems that arise in game development applications. These discussions are not comprehensive. Past threads in the gamedev.net forums, as well as the gamedev.net articles & resources list, can provide sources of much more detailed answers/solutions/discussions of these problems. 8. Is there a good general source of information on mathematics for game development? I"m glad you asked. Yes, there are many, and I"ll suggest a few here: comp.graphics.algorithms FAQ This one discuss quite a long list of very common graphics math problems. Highly recommended. www.gamasutra.com The website companion to Game Developer"s Magazine. This link puts you in the Features/Programming section of the site. You have to register, but its free. And eventually most articles published in the print magazine show up here where you can access them for no cost. Lots of great, practical articles on just about every game programming subject under the sun. Here"s a very good math site that presents a wide variety of topics in a fairly simple way. www.sosmath.com Another classic site, comprehensive but less straightforward and helpful for the novice, in my opinion: Mathworld A bit more difficult to navigate, and more focused on theory than algorithms, but nontheless quite useful. http://mathforum.org/dr.math/ Great help for those of you who are in school and looking for online help doing your homework. A few others: http://www.geocities.com/SiliconValley/2151/math2d.html http://www.faqs.org/faqs/graphics/algorithmsfaq/ 9. How can I determine if a point lies within the interior of a 3D polygon? Since the most common graphics geometry primitive is a triangle, lets talk about finding a point in a 3D triangle. A triangle, 3D or 2D, is planar. Any point contained in the interior of the triangle must lie in the same plane as the triangle. So, the first thing to do is to find out if the point lies in the same plane as the triangle. If the point does lie in the same plane, the problem really becomes a 2D problem. See the next question for more details on this. The following link does discuss the 3Dto2D mapping. http://erich.realtimerendering.com/ptinpoly/ As for general polygons, the answer is the same as long as the polygon is planar. If the polygon is nonplanar (in which case its not technically a polygon anymore, but this occurs quite frequently in 3D graphics modeling), then the problem becomes the problem of finding out if the point lies on a curved surface. This problem can be approximated by tesselating the polygon into triangles, which are of course planar, then testing the point against all of the triangles. This is probably very uncommon in game development, since triangles are used more often than not. 10. How can I determine if a point lies within the interior of a 2D polygon? Refer to the following web page, which has a comprehensive discussion of the subject: http://erich.realtimerendering.com/ptinpoly/ This topic has been discussed since the math & physics forum began on gamedev.net, but I am not including links to any of the threads since I believe the linked website provides a nice summary of a variety of appropriate algorithms. 11. What is a vector/matrix/quaternion, and how do I get started working with them? A very good question for the novice or beginning game programmer! Here are a couple of web resources that can help you learn about matrices, vectors, and quaternions. Good introductory article here on gamedev.net: Vectors and Matrices: A Primer A couple of others: The Matrix and Quaternion FAQ Vector Math Tutorial for 3D Computer Graphics 12. Are there any realtime physics SDK"s available, free or otherwise? Sure. Please see the following sticky thread in this forum: List of physics engines and reference material 13. How do I clip a 2D line against the viewport or another rectangle? Google says... A good description of the classic Cohen Sutherland algorithm is here: http://www.cs.brown.edu/courses/cs123/lectures/Clipping.pdf A Java demonstration of the Cohen Sutherland algorithm: http://graphics.lcs.mit.edu/classes/6.837/F99/assignment2/CohenSutherland.html Documentation of 3 different algorithms: http://www.cis.ohiostate.edu/~hwshen/681/0118.pdf 14. How do I begin writing my own physics engine? Ask this question of a dozen game developers and you will get a dozen different answers. Here is my take: a) Go to the sticky thread listed below and look for the essential math tutorials link: List of physics engines and reference material b) Read a few articles. Do not start out with David Baraff's paper or presentations (at least not the ones on constrained dynamics)they're too advanced to begin with. Chris Hecker's articles are a better starting point: http://www.d6.com/users/checker/dynamics.htm There is also a helpful series of articles over at Pixar's site (including Baraff's famous papers/presentations, which I already suggested are not for the novice): http://www.pixar.com/companyinfo/research/pbm2001/ c) Start with free moving particles, rather than objects with shapes (such as cubes). 2D vs. 3D to start is your choice. I feel that if you start with particles, you can probably start out in 3Das long as you have a grasp of 3D coordinate systems. Even a fundamental grasp, e.g., what does (x, y, z) mean in terms of location (coordinate) vs. direction (vector). d) Go find yourself a simple particle system to play with. try developer.nvidia.com or perhaps nehe.gamedev.net. The idea is to get a prebuilt toolbox for some of the following. e) Start with particles that just move with constant velocity in space. Figure out how to deal with a variable frame rate. Actually go and write some code to render particles and let you look at the particle system from different angles. Work out how to get the particles moving at the same speed (e.g., same number of meters per second) when you have a frame rate of 20 vs. a frame rate of 100. You can cause your frame rate to vary by just increasing the number of particles. My suggestion would be to place several static blocks in your scene, say along the x axis every 5 feet or so. Then, have your particles all start moving along the x axis at 5 feet per second. This way, you can visually inspect the particles and make sure they all are moving at 5 feet per second even when you frame rate is not constant. HINT: you will want to look into framerateindependent methods to avoid some physics stability issues that you'll eventually discover. Its probably best to figure out the framerateindependent issue early on, rather than try and retrofit your system later. HINT 2: To determine the motion, you will want to be using "Verlet" integration. You pretty much NEVER should use Euler integration (even though many folks do and even though many folks say it works finebelieve me, it is evil. And I have the Ph.D courses and work experience in numerical physics to prove it.) f) Once you've got particles moving consistently at different frame rates, start throwing in some interesting things. Start with gravity and watch the particles follow a parabolic path. You can look at the very simple equations for projectile motion if you want. These equations you will be learning later in high school. But they won't get you too far in realtime physics. You need to look into the Verlet integration I mentioned above. But, those high school equations *are* *very* good to use to generate exactly correct results that you can compare your Verlet results against. Use them as a benchmark for accuracy and to help track/minimize numerical error/drift. g) After gravity, work on collision with a simple ground plane located at z = 0.0. h) Then, maybe add springs with damping to connect the particles together. Here is where Verlet integration will first save you from the perils of Euler integration. NOTE: There is a kind of Euler integration, called implicit Euler, which is very good. But it is very difficult to code and you will not be trying that soon! i) Then, try particletoparticle collision. Give each particle a radius and a mass, and use conservation of momentum to figure out the collision response. These conservation of momentum equations you will also learn in high school probably, and in this case you *should* use those equations. You'll also want to review the following article over at gamasutraits actually going to be far more useful than your high school lessons: http://www.gamasutra.com/features/20020118/vandenhuevel_01.htm j) You can always expand this. Add in some simple air drag effects (search the gamedev forum archives as there are threads in this forum over the past 23 years that describe very simple ways to calculate drag), or electromatic field forces. k) Do all that and you will basically have perfected particle physics (which you definitely should do before trying your hand at complex shapes or true rigid body joints). It shouldn't take you too long to get there, and you should be very pleased with the results. l) Now you can perhaps start working with interesting shapes, *or* true rigidbody constraints. If you continue with interesting shapes, then you're going to get into more complex collision detection problems + the issue of rotational/spin/gyroscopic effects. Which are all nontrivial. If you continue with true rigidbody constraints, you're going to get into some nontrivial things there too. If you develop a good rigidbody system, which effectively can rigidly link particles together, then you can continue to use the code you developed in steps 19, and effectively build complex rigid shapes by just putting a particle at each node/vertex of a shape and rigid bar links between them. In this way you can simulate complex shapes while still just dealing with particles. This is far from ideal, but it is a simple way to get into complex shapes. This is where you might at least want to try to read some of David Baraff's papers or presentations. But you are starting to get into some stuff that may be beyond your grasp right now. m) into the future... realtime softbody dynamics and fracture using modal analysis, combined with sound effects synthesized in software from the physics calcs anyone? P.S. Definitely do springs before trying to do joints or complex shapes. 15. What are some good resources for collision detection? For research and theory, as well as some packages that may be practical to use, try these: UNC Collide Research Group Stanford University page on Collision Detection There are some articles around, one good beginners article, related to spherical objects (such as pool/billiard balls), is here: http://www.gamasutra.com/features/20020118/vandenhuevel_01.htm Also, these packages may be helpful: Pierre Terdiman's OPCODE Note that for the link below, there is also now a very nice book from Morgan Kauffman Publishers, called "Collision Detection in Interactive 3D Environments"  ISBN 155860801X Gino van den Bergen's SOLID 16. Are there any websites that give a concise summary of different numerical integration methods? Here is one nice web page that describes a few common integrators, along with examples that show the benefits and weaknesses: Numerical Integration 
All times are ET (US)
Moderators/Admin: Edit FAQ 