This is the final draft of my proposal minus the gantt chart as this has not changed:
---------------------------------------------------------------------
CS1004A Honours Project
Project Proposal
Realistic Modelling of Motion Involving Collisions with 3D Environments
Introduction
The games industry has developed significantly throughout the years and there will always be constant refinement and advancements made. Focus on new development will constantly be at the forefront of the evolution of the games industry. With technological advances initially driving the art, the focus turned to the realism of the game. The general goal in making any game is that it must give the player an all round believable world, in which they can become immersed. When it comes to physics in games, it is often said that its success is determined by how it looks rather than how accurate it is and so the game has to, at the very least, look realistic. However, with computational limitations on the CPU, the more advanced physics calculations need to be estimated.
In recent years, physics systems in games have advanced greatly and will continue to do so. As Hecker (2000, p.35) says: ‘as these skills [of game programmers] and CPU speeds improve, and as player expectations increase, game “physics simulators” have to keep pace by becoming increasingly realistic and advanced.’ Therefore it is an area which always needs to be developed repeatedly as CPU speeds improve, so that it is used to it highest potential. Physics is the key to any successful realistic game. If a character was to get stuck or completely walk though a closed door unexpectedly, it would not matter how good the character looked, the gamer's attention would be diverted completely from the task at hand. Of course, with certain limitations on what can be simulated and how realistically it can be simulated, the main focus of a programmer will be to make everything as consistent as possible. ‘Interference calculation of physically based models is computationally expensive and is usually the bottleneck in all applications that require a real-time response.’ (Geiger 2000). Previous studies into realistic simulations show that it cannot be done to any great detail without the need for approximating. Whether that is at the point of collision or the response at the moment after collision, the calculations become too computationally demanding for the processor and need to be estimated. Basic simulations may be possible and the need to estimate may be smaller with a simulation of only a small number of objects.
Baraff (1993, p.1) suggests that, ‘We have become somewhat proficient at creating high-quality images of complex models, but our skill at performing realistic physical simulations lags far behind our ability to visualize them.’ This is because the CPU’s in most modern computers do not have the capacity to perform high level computation of physics calculations. The acceleration of game physics is always a well talked about subject with the constant development of add-on hardware (such as GPU and physics processing unit – PPU) to speed physics calculations up that generally run on the CPU. However, until these become part of the standard computer package, developers must continue to work with physics calculations within the CPU. As mentioned before, physics is the key to how realistic a game will look. Going back to basic rigid body dynamics and how they collide with their environment seems to be a good place to start when studying how physics can be simulated with current constraints on processing power.
Research Topic
This project will consist of performing research into how mathematics and physics can be used to produce a simulation of highly realistic movement. Specifically, the investigation will look at how a number of different objects move and collide with a curved surface. By looking into the mathematics behind such collisions in real life, this project will hopefully provide a realistic template of the movements. With the simulation of rigid body dynamics, the Euler integration method can be used. However, Atencio et al. (2005) suggest using the Verlet integrator, which stores current position, previous position and the force or acceleration. Of course, all of these methods including others will be researched in more detail to ensure the correct and most accurate method of collision detection and response is used in relation to the problem.
The project will also look into ways of increasing the accuracy, and therefore the realism, of collisions on a curved surface while maintaining good frame rates. At some point there might be a need to simplify the calculations if the processing of the simulation becomes too demanding. If this happens, methods will be researched and integrated into the simulation to maintain the speed of the simulation, while hopefully preserving the realistic movement.
Research Question
Can the movements and collisions of objects on a curved surface be realistically simulated in real-time?
The aim of this project will be to investigate the use of simple realistic collisions on a curved surface in real-time. To achieve this, a graphical simulation will be made to replicate these movements realistically.
Project Execution
As the study will be on the simulation of realistic movement, background knowledge will be needed initially of the mathematical theory behind real-life movements and collisions. Having obtained this, the next stage would be to start implementation on the simulation itself. The implementation will be broken down into small manageable sections as shown below and implemented in OpenGL:
v Movements of a point mass bouncing on an angled surface.
Ø Start the point mass on a given path towards the surface.
Ø It will bounce off the surface at an angle.
Ø Calculate its resulting motion.
Ø The effect that friction has on the resulting motion will be taken into account.
v Movements of the point mass bouncing on a curved surface (represented by Bezier surface).
Ø Again the mass will be placed on a given path to collide with the surface at an angle.
Ø To find out the resulting motion, the tangent plane of the curve will be found at the point of collision and the calculations will be similar to the collision with the flat, angled plane.
v Movements of a sphere/ball bouncing on a flat, angled surface.
Ø With the substitution of a sphere or ball instead of a point mass, additional movements will have to be considered.
Ø To calculate the resulting motion of the sphere, the same calculations will be made as above however, it will then be followed by calculations on the rotation effect placed on the ball depending on the angle and velocity when the collision occurs.
v Movements of the sphere on the curved surface.
Ø The tangent of the plane at the point of collision will be calculated to find the given normal for the bounce.
Ø Calculations will proceed as above to find the resulting bounce, by first finding the tangent plane to the curve. The rotational effect on the sphere before and after bouncing will be simulated also.
v Extra study where time permits. Possible areas include:
Ø Differently shaped objects, such as a box character mesh, bringing additional movements into consideration.
Ø Rough terrain which will result in an increase of friction.
Ø Effects of wind.
Ø Multiple objects or surfaces that increases the computational effort of the scene.
Project Evaluation
To evaluate this project, there are a number of criteria to consider. Firstly, how the simulation would be conveyed to the viewer. Referring to an earlier statement, ‘if it looks right, then it is right’ (Conger 2004, p.3), a measurement of success, will be on its appearance. The project considers the realistic simulation of real life collisions and movements of objects and therefore, throughout the project, the need for visual ‘correctness’ at every stage is essential.
Another criterion to take into account is the frame rates as the simulation is run. Frame rates will be overseen throughout the execution of this project to make sure they are adhering to the research question that it is a simulation performed in real-time.
Issues
There are a number of issues which may arise throughout this project and its implementation.
As mentioned above, the criterion of ‘success’ is somewhat subjective to the viewer of the simulation.
Another issue may arise when the collision detection technique will be chosen. Lin (1993, p.1) states, ‘Since prompt recognition of possible impacts is a key to successful response to collisions in a timely fashion, a simple yet efficient algorithm for collision detection is important for fast and realistic animation and simulation of moving objects.’ As this project will be measuring the level of realism that can be simulated, the method of collision detection used will have to be as accurate as possible; obtaining minimal approximations while maintaining low frames rates and in turn lowering the computational power of the simulation. So far, some research has gone into the method for collision detection. Atencio et al. (2005) devised a technique for collision detection and response which can be used for a simple physics animation. This will be looked at in further detail as well as other methods, to ensure an appropriate technique is adopted.
Resource Requirements
The techniques which are researched will be executed into a computer simulation using the OpenGl API. At present, the resources essential for this project are easily accessible and no additional computer applications or software will be required. However, this will be frequently reviewed at each stage.
Conclusion
The completion of this project as a realistic simulation is feasible in the time given and the realistic requirement will be constantly evaluated at each stage of the project.
Bibliography
Bandi, S and Thalmann, D. 1995. An Adaptive Spatial Subdivision of the Object Space for Fast Collision Detection of Animated Rigid Bodies. 14(3): Blackwell Publishers.
Baraff, D. 1990. Curved Surfaces and Coherence for Non-penetrating Rigid Body Simulation. 24(4) pp. 19-28. [online] Available from:
http://wf2dnvr5.webfeat.org/qXgAL1179/url=http://delivery.acm.org/10.1145/100000/97881/p19-baraff.pdf?key1=97881&key2=2940009221&coll=ACM&dl=ACM&CFID=14222854&CFTOKEN=77279356 [Accessed on 1 December 2008]
Beadsworth, T and Jefferson, B. 2000. Introducing Mechanics. Oxford: Oxford University Press.
Blyth, D and McReynolds, T. 2005. Advanced Graphics Programming Using OpenGl. China: Elsevier Inc.
Chrysanthou, Y, Slater, M and Steed, A. 2002. Computer Graphics and Virtual Environments: From Realism to Real-time. USA: Pearson Education Ltd.
Mortenson, ME. 1999. Mathematics for Computer Graphics Applications. 2nd ed. USA: Industrial Press Inc.
References
Atencio, YP et al. 2005. A Collision Detection and Response Scheme for Simplified Physically Based Animation. pp. 291-298 [online] Available from: http://www2.computer.org/portal/web/csdl/doi/10.1109/SIBGRAPI.2005.3 [Accessed on 24 November 2008]
Baraff, D. 1993. Non-Penetrating Rigid Bodies Simulation. [online] Eurographics Association. Available from: http://www.cs.cmu.edu/afs/cs/user/baraff/www/papers/eg93.pdf [Accessed on 8 December 2008]
Conger, D. 2004. Physics In Games, Physics Modelling for Games Programmers. [online] US: Thompson Course Technology. Available from:
http://books.google.co.uk/books?id=TuceL0LMWSMC&printsec=frontcover&dq=physics+modelling+for+game#PPR12,M1 [Accessed on 23 October 2008]
Geiger, B. 2000. Computer Graphics International. Real-Time Collision Detection and Response for Complex Environments. pp. 105. [online] Available from:
http://doi.ieeecomputersociety.org/10.1109/CGI.2000.852326 [Accessed on 28 November 2008]
Hecker, C. 2000. Physics in Computer Games. Communications of the ACM, 43(7): pp. 34-39. [online] Available from: http://doi.acm.org/10.1145/341852.341861 [Accessed on 28 November 2008]
Lin, MC. 1993. Efficient Collision Detection for Animation and Robotics. [online] Available from: ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/thesis.pdf [Accessed on 6 December 2008]
Project Proposal
Realistic Modelling of Motion Involving Collisions with 3D Environments
Introduction
The games industry has developed significantly throughout the years and there will always be constant refinement and advancements made. Focus on new development will constantly be at the forefront of the evolution of the games industry. With technological advances initially driving the art, the focus turned to the realism of the game. The general goal in making any game is that it must give the player an all round believable world, in which they can become immersed. When it comes to physics in games, it is often said that its success is determined by how it looks rather than how accurate it is and so the game has to, at the very least, look realistic. However, with computational limitations on the CPU, the more advanced physics calculations need to be estimated.
In recent years, physics systems in games have advanced greatly and will continue to do so. As Hecker (2000, p.35) says: ‘as these skills [of game programmers] and CPU speeds improve, and as player expectations increase, game “physics simulators” have to keep pace by becoming increasingly realistic and advanced.’ Therefore it is an area which always needs to be developed repeatedly as CPU speeds improve, so that it is used to it highest potential. Physics is the key to any successful realistic game. If a character was to get stuck or completely walk though a closed door unexpectedly, it would not matter how good the character looked, the gamer's attention would be diverted completely from the task at hand. Of course, with certain limitations on what can be simulated and how realistically it can be simulated, the main focus of a programmer will be to make everything as consistent as possible. ‘Interference calculation of physically based models is computationally expensive and is usually the bottleneck in all applications that require a real-time response.’ (Geiger 2000). Previous studies into realistic simulations show that it cannot be done to any great detail without the need for approximating. Whether that is at the point of collision or the response at the moment after collision, the calculations become too computationally demanding for the processor and need to be estimated. Basic simulations may be possible and the need to estimate may be smaller with a simulation of only a small number of objects.
Baraff (1993, p.1) suggests that, ‘We have become somewhat proficient at creating high-quality images of complex models, but our skill at performing realistic physical simulations lags far behind our ability to visualize them.’ This is because the CPU’s in most modern computers do not have the capacity to perform high level computation of physics calculations. The acceleration of game physics is always a well talked about subject with the constant development of add-on hardware (such as GPU and physics processing unit – PPU) to speed physics calculations up that generally run on the CPU. However, until these become part of the standard computer package, developers must continue to work with physics calculations within the CPU. As mentioned before, physics is the key to how realistic a game will look. Going back to basic rigid body dynamics and how they collide with their environment seems to be a good place to start when studying how physics can be simulated with current constraints on processing power.
Research Topic
This project will consist of performing research into how mathematics and physics can be used to produce a simulation of highly realistic movement. Specifically, the investigation will look at how a number of different objects move and collide with a curved surface. By looking into the mathematics behind such collisions in real life, this project will hopefully provide a realistic template of the movements. With the simulation of rigid body dynamics, the Euler integration method can be used. However, Atencio et al. (2005) suggest using the Verlet integrator, which stores current position, previous position and the force or acceleration. Of course, all of these methods including others will be researched in more detail to ensure the correct and most accurate method of collision detection and response is used in relation to the problem.
The project will also look into ways of increasing the accuracy, and therefore the realism, of collisions on a curved surface while maintaining good frame rates. At some point there might be a need to simplify the calculations if the processing of the simulation becomes too demanding. If this happens, methods will be researched and integrated into the simulation to maintain the speed of the simulation, while hopefully preserving the realistic movement.
Research Question
Can the movements and collisions of objects on a curved surface be realistically simulated in real-time?
The aim of this project will be to investigate the use of simple realistic collisions on a curved surface in real-time. To achieve this, a graphical simulation will be made to replicate these movements realistically.
Project Execution
As the study will be on the simulation of realistic movement, background knowledge will be needed initially of the mathematical theory behind real-life movements and collisions. Having obtained this, the next stage would be to start implementation on the simulation itself. The implementation will be broken down into small manageable sections as shown below and implemented in OpenGL:
v Movements of a point mass bouncing on an angled surface.
Ø Start the point mass on a given path towards the surface.
Ø It will bounce off the surface at an angle.
Ø Calculate its resulting motion.
Ø The effect that friction has on the resulting motion will be taken into account.
v Movements of the point mass bouncing on a curved surface (represented by Bezier surface).
Ø Again the mass will be placed on a given path to collide with the surface at an angle.
Ø To find out the resulting motion, the tangent plane of the curve will be found at the point of collision and the calculations will be similar to the collision with the flat, angled plane.
v Movements of a sphere/ball bouncing on a flat, angled surface.
Ø With the substitution of a sphere or ball instead of a point mass, additional movements will have to be considered.
Ø To calculate the resulting motion of the sphere, the same calculations will be made as above however, it will then be followed by calculations on the rotation effect placed on the ball depending on the angle and velocity when the collision occurs.
v Movements of the sphere on the curved surface.
Ø The tangent of the plane at the point of collision will be calculated to find the given normal for the bounce.
Ø Calculations will proceed as above to find the resulting bounce, by first finding the tangent plane to the curve. The rotational effect on the sphere before and after bouncing will be simulated also.
v Extra study where time permits. Possible areas include:
Ø Differently shaped objects, such as a box character mesh, bringing additional movements into consideration.
Ø Rough terrain which will result in an increase of friction.
Ø Effects of wind.
Ø Multiple objects or surfaces that increases the computational effort of the scene.
Project Evaluation
To evaluate this project, there are a number of criteria to consider. Firstly, how the simulation would be conveyed to the viewer. Referring to an earlier statement, ‘if it looks right, then it is right’ (Conger 2004, p.3), a measurement of success, will be on its appearance. The project considers the realistic simulation of real life collisions and movements of objects and therefore, throughout the project, the need for visual ‘correctness’ at every stage is essential.
Another criterion to take into account is the frame rates as the simulation is run. Frame rates will be overseen throughout the execution of this project to make sure they are adhering to the research question that it is a simulation performed in real-time.
Issues
There are a number of issues which may arise throughout this project and its implementation.
As mentioned above, the criterion of ‘success’ is somewhat subjective to the viewer of the simulation.
Another issue may arise when the collision detection technique will be chosen. Lin (1993, p.1) states, ‘Since prompt recognition of possible impacts is a key to successful response to collisions in a timely fashion, a simple yet efficient algorithm for collision detection is important for fast and realistic animation and simulation of moving objects.’ As this project will be measuring the level of realism that can be simulated, the method of collision detection used will have to be as accurate as possible; obtaining minimal approximations while maintaining low frames rates and in turn lowering the computational power of the simulation. So far, some research has gone into the method for collision detection. Atencio et al. (2005) devised a technique for collision detection and response which can be used for a simple physics animation. This will be looked at in further detail as well as other methods, to ensure an appropriate technique is adopted.
Resource Requirements
The techniques which are researched will be executed into a computer simulation using the OpenGl API. At present, the resources essential for this project are easily accessible and no additional computer applications or software will be required. However, this will be frequently reviewed at each stage.
Conclusion
The completion of this project as a realistic simulation is feasible in the time given and the realistic requirement will be constantly evaluated at each stage of the project.
Bibliography
Bandi, S and Thalmann, D. 1995. An Adaptive Spatial Subdivision of the Object Space for Fast Collision Detection of Animated Rigid Bodies. 14(3): Blackwell Publishers.
Baraff, D. 1990. Curved Surfaces and Coherence for Non-penetrating Rigid Body Simulation. 24(4) pp. 19-28. [online] Available from:
http://wf2dnvr5.webfeat.org/qXgAL1179/url=http://delivery.acm.org/10.1145/100000/97881/p19-baraff.pdf?key1=97881&key2=2940009221&coll=ACM&dl=ACM&CFID=14222854&CFTOKEN=77279356 [Accessed on 1 December 2008]
Beadsworth, T and Jefferson, B. 2000. Introducing Mechanics. Oxford: Oxford University Press.
Blyth, D and McReynolds, T. 2005. Advanced Graphics Programming Using OpenGl. China: Elsevier Inc.
Chrysanthou, Y, Slater, M and Steed, A. 2002. Computer Graphics and Virtual Environments: From Realism to Real-time. USA: Pearson Education Ltd.
Mortenson, ME. 1999. Mathematics for Computer Graphics Applications. 2nd ed. USA: Industrial Press Inc.
References
Atencio, YP et al. 2005. A Collision Detection and Response Scheme for Simplified Physically Based Animation. pp. 291-298 [online] Available from: http://www2.computer.org/portal/web/csdl/doi/10.1109/SIBGRAPI.2005.3 [Accessed on 24 November 2008]
Baraff, D. 1993. Non-Penetrating Rigid Bodies Simulation. [online] Eurographics Association. Available from: http://www.cs.cmu.edu/afs/cs/user/baraff/www/papers/eg93.pdf [Accessed on 8 December 2008]
Conger, D. 2004. Physics In Games, Physics Modelling for Games Programmers. [online] US: Thompson Course Technology. Available from:
http://books.google.co.uk/books?id=TuceL0LMWSMC&printsec=frontcover&dq=physics+modelling+for+game#PPR12,M1 [Accessed on 23 October 2008]
Geiger, B. 2000. Computer Graphics International. Real-Time Collision Detection and Response for Complex Environments. pp. 105. [online] Available from:
http://doi.ieeecomputersociety.org/10.1109/CGI.2000.852326 [Accessed on 28 November 2008]
Hecker, C. 2000. Physics in Computer Games. Communications of the ACM, 43(7): pp. 34-39. [online] Available from: http://doi.acm.org/10.1145/341852.341861 [Accessed on 28 November 2008]
Lin, MC. 1993. Efficient Collision Detection for Animation and Robotics. [online] Available from: ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/thesis.pdf [Accessed on 6 December 2008]
No comments:
Post a Comment