miércoles, 31 de diciembre de 2008
martes, 23 de diciembre de 2008
martes, 16 de diciembre de 2008
Time Critical Collision Detection
One of the bottlenecks to obtain real-time physical based simulations is the collision detection process and much research has been done on this. In the past, I proposed a method to fit the collision process to any given budget of time. See the paper here. This method works for rigid and deformable bodies.
The idea is to interrupt the collision process when our budget of time has expired and use the available information to compute the collision response (it this happened). The computed response is an approximation of the real one: Yes, we trade time for accuracy, but in general the results are quite satisfactory.
The method is based on sphere representations of the object. Each of these representations goes from a coarse representation (a) to a high quality representation (d). If we have little time, we compute the collision detection process using (a) or (b) representations as in the figure above. If we have lots of time, we use more detailed representations (c) or (d). The coarser the representation the less accurate is the response (or even the detection).
The complexity of the problem comes to compute good responses even with little information.
The question is: do you prefer high accurate responses even if your application goes slow or do you prefer to keep your simulation rates and obtaining some non-accurate responses ??
Well, here at Atari we have decided to go for high accurate responses... so, that means that I will have to find other ways to keep good simulation rates... good challenge !
So, if anybody have some good ideas, please let me know.
The idea is to interrupt the collision process when our budget of time has expired and use the available information to compute the collision response (it this happened). The computed response is an approximation of the real one: Yes, we trade time for accuracy, but in general the results are quite satisfactory.
The method is based on sphere representations of the object. Each of these representations goes from a coarse representation (a) to a high quality representation (d). If we have little time, we compute the collision detection process using (a) or (b) representations as in the figure above. If we have lots of time, we use more detailed representations (c) or (d). The coarser the representation the less accurate is the response (or even the detection).
The complexity of the problem comes to compute good responses even with little information.
The question is: do you prefer high accurate responses even if your application goes slow or do you prefer to keep your simulation rates and obtaining some non-accurate responses ??
Well, here at Atari we have decided to go for high accurate responses... so, that means that I will have to find other ways to keep good simulation rates... good challenge !
So, if anybody have some good ideas, please let me know.
miércoles, 10 de diciembre de 2008
Atari is ramping up
Yeah, this is happening...
Atari, the company I have joined this year, was death at the end of the last century and it was converted in a company publishing games from other game developers.
In 2003, it has been started to be acquired by Infogrammes Inc., a French corporate and in 2008, Atari was fully acquired and then EdenGames (about 150 people) became an internal developer of Atari. Actually, the only one.
Then, things are happening very rapidly, at the end of the summer, Atari created a second studio in London bringing Paulina Bozek (the pretty girl producer previously head of SingStar) to Atari (Read article here). Now, Atari fully acquire massively multiplayer online (MMO) game developer Cryptic Studios. Read the article here. So, another 150 people are now employees of Atari. Cryptic Studios has been awarded in all this online stuff.
This are going fast ! 3 studios in less than a semester !!
Atari, the company I have joined this year, was death at the end of the last century and it was converted in a company publishing games from other game developers.
In 2003, it has been started to be acquired by Infogrammes Inc., a French corporate and in 2008, Atari was fully acquired and then EdenGames (about 150 people) became an internal developer of Atari. Actually, the only one.
Then, things are happening very rapidly, at the end of the summer, Atari created a second studio in London bringing Paulina Bozek (the pretty girl producer previously head of SingStar) to Atari (Read article here). Now, Atari fully acquire massively multiplayer online (MMO) game developer Cryptic Studios. Read the article here. So, another 150 people are now employees of Atari. Cryptic Studios has been awarded in all this online stuff.
This are going fast ! 3 studios in less than a semester !!
domingo, 7 de diciembre de 2008
Evaluating Physics Engines For Games - PAL -
Physics engines are a high-tech aspect within a next-gen game. They are in charge of simulating all the physics as realistic as possible. Many times the accuracy of the physics is reduced to meet the real-time requirements of the game. Many companies prefer to buy the physics engine as a middleware and apply their effors in others parts of the game. Nowadays there well established companies offering this middleware, like for example Havok, Nvidia-AGEIA. There are of course new comers and open-source engines such as Pixelux, Bullet, ODE, Tokamak, etc.
The big question is: which physics engine is the best ?
The answer is straighforward: None of them is in overall the best and it is very case dependent. However, there is still a way to make some comparisons. So, I came across this paper:
Evaluation of Real Time Physics Simulation Systems,
A. Boeing, T. Braunl
Procc. Computer graphics and interactive techniques in Australasia and South East Asia, 2007
The work on the paper compares different physics engines: AGEIA-Nvidia, Bullet, JigLib (from my friend Danny Chapman), Newton Physics, ODE, Tokamak, True Axis. The authors implemented a physics abstraction layer (PAL) to carry out the comparison. You can even download PAL. I suppose that it has been an amazing work to wrap all the physics engine in only one application. Unfortunately, HAVOK is not compared nor PIXELUX.
The comparison was based on five tests:
The main conclusion that the authors made is that Bullet engine provided the best results overall.
Although this result is the conclusion of a huge work, it should be taken with a lot of care, since many aspects were not included in the comparison and that the PAL system does not support correctly some engines (for example AGEIA-Nvidia for collision detection), Pixelux and Havok were not included in the comparison, support from the physics engine provider, other aspects such as fluid simulation, soft body simulation and some specific optimisations of the engines were not included. Which ones are optimised for PS3 or Xbox360 ? Results are evidently tested on a PC. Finally, some tests are not suitable in many cases, for instance the integrator performance may vary for each engine and for each object being simulated.
Still, PAL is a good starting tool to start testing physics engines.
Anyway, my favorites are AGEIA-Nvidia, Havok and Bullet and the one we are developping :)
The big question is: which physics engine is the best ?
The answer is straighforward: None of them is in overall the best and it is very case dependent. However, there is still a way to make some comparisons. So, I came across this paper:
Evaluation of Real Time Physics Simulation Systems,
A. Boeing, T. Braunl
Procc. Computer graphics and interactive techniques in Australasia and South East Asia, 2007
The work on the paper compares different physics engines: AGEIA-Nvidia, Bullet, JigLib (from my friend Danny Chapman), Newton Physics, ODE, Tokamak, True Axis. The authors implemented a physics abstraction layer (PAL) to carry out the comparison. You can even download PAL. I suppose that it has been an amazing work to wrap all the physics engine in only one application. Unfortunately, HAVOK is not compared nor PIXELUX.
The comparison was based on five tests:
- Integrator performance (i.e. solution of ODE's)
- Material properties (i.e. frictions, restitution)
- Constraint stability
- Collision detection
- Stacking test
The main conclusion that the authors made is that Bullet engine provided the best results overall.
Although this result is the conclusion of a huge work, it should be taken with a lot of care, since many aspects were not included in the comparison and that the PAL system does not support correctly some engines (for example AGEIA-Nvidia for collision detection), Pixelux and Havok were not included in the comparison, support from the physics engine provider, other aspects such as fluid simulation, soft body simulation and some specific optimisations of the engines were not included. Which ones are optimised for PS3 or Xbox360 ? Results are evidently tested on a PC. Finally, some tests are not suitable in many cases, for instance the integrator performance may vary for each engine and for each object being simulated.
Still, PAL is a good starting tool to start testing physics engines.
Anyway, my favorites are AGEIA-Nvidia, Havok and Bullet and the one we are developping :)
miércoles, 3 de diciembre de 2008
Loving 2D games.
Following previous post on 2D physics engines, see my post on Box2D, I have found the World of Goo game. It is just fantastic !
Besides the originality, the tenderness, the best wii game, or any other good reviews received by this game, what impacts me is that it has been created by only two guys (Kyle Gabler and Ron Carmel). There have been other "external" people involved in the development of the game, but everything goes to only two persons. This is a bit of hope for those developing their own games in the corner of their rooms and spending nights on it. Check out the interview of this guys here.
Just check the video or go to their website.
Besides the originality, the tenderness, the best wii game, or any other good reviews received by this game, what impacts me is that it has been created by only two guys (Kyle Gabler and Ron Carmel). There have been other "external" people involved in the development of the game, but everything goes to only two persons. This is a bit of hope for those developing their own games in the corner of their rooms and spending nights on it. Check out the interview of this guys here.
Just check the video or go to their website.
lunes, 1 de diciembre de 2008
Optimized Spatial Hashing for Collision Detection: Implementation
A couple of weeks ago, I implemented a method to detect collisions between any kind of body -rigid or deformable-. The method is based on the following paper:
M. Teschner, B. Heidelberger, M. Mueller, D. Pomeranets, M. Gross, "Optimized Spatial Hashing for Collision Detection of Deformable Objects," Proc. Vision, Modeling, Visualization VMV'03, Munich, Germany, pp. 47-54, Nov. 19-21, 2003.
Click here to get the paper.
Short conclusion and review after the implementation:
The collision detection method is based on an optimised spatial hashing of the object. I have implemented it for rigid bodies and soft bodies (2D and 3D) so you can use it for both. The method assumes that you can provide the surface vertices of the object and that you can also provide a collision primitive representation of the object. The collision primitives in case of soft bodies can be the surface tetrahedrons, for fluids you can inflate the particles, for cloths you can give a thickness to the triangles or even bounding spheres for triangles.
The method follows two main steps:
STEP 1:
Discretization and hashing of the surface vertices of the object. Each vertex is discretized with respect to a cell (an axis aligned box). The coordinates of the vertex (x,y,z) are divided by the given cell size and rounded down to the next integer. As in the paper the discretized vertex is: (i,j,k) where i = x/l, j = y/l and k = z/l. Then, a hash function maps the discretized vertex to a 1D index h. I used the following code:
inline unsigned int hash(int xi, int yi, int zi) {
unsigned int h = (xi * 73856093)^(yi * 19349663)^(zi * 83492791) ; //same as in paper
return h % sizeOfHashTable} //sizeOfHashTable=big value
}
STEP 2:
Discretization and hashing of the collision primitives as in step 1. For example, for each surface tetrahedron of the object, I compute the AABB and discretize the minimum and maximum values as we did for the vertices. Hash values are computed for all cells affected by the AABB of the tetrahedron. This is a tricky part and I can explain a bit further if you want. Then, all the vertices found at the according hash table index are tested for intersection. The intersection test can be: vertices inside sphere, tetrahedron or box, or if continuous collision detection, you can use segments versus sphere, tetrahedron or box.
The rest of the paper determines an optimal size of the hash table and optimal hash function.
CONCLUSION:
Good stuff: The method handles collision detection for deformable objects (cloths and volumetric objects) and rigid bodies. The method handles self-collisions since it hashes all collision primitives and all vertices of all objects in the same table.
Bad stuff: It is not edge sensitive which means that it does not detect collision with edges. Object penetration happens when edges are not detected. The method detects if vertices are inside the object but not edges. Authors of the paper claim that this is not a problem.. well, not really, if the objects uses a low resolution with big triangles (like the case of triangles in videogames) the penetrations are really evident and things are very unrealistic.
Besides, it is difficult to compute a proper collision response. If a vertex is inside the object, which is the direction of the repulsion normal ? To solve this, I use previous vertex positions to compute segments and handle this problem.
I am not quite sure about the optimization at the end of section 4.2. It is not clear explained so I am not sure if I got it right (well, it works fine, so I think it is correct). But, is there a big signifcance for this optimization for small hash tables ?
M. Teschner, B. Heidelberger, M. Mueller, D. Pomeranets, M. Gross, "Optimized Spatial Hashing for Collision Detection of Deformable Objects," Proc. Vision, Modeling, Visualization VMV'03, Munich, Germany, pp. 47-54, Nov. 19-21, 2003.
Click here to get the paper.
Short conclusion and review after the implementation:
The collision detection method is based on an optimised spatial hashing of the object. I have implemented it for rigid bodies and soft bodies (2D and 3D) so you can use it for both. The method assumes that you can provide the surface vertices of the object and that you can also provide a collision primitive representation of the object. The collision primitives in case of soft bodies can be the surface tetrahedrons, for fluids you can inflate the particles, for cloths you can give a thickness to the triangles or even bounding spheres for triangles.
The method follows two main steps:
STEP 1:
Discretization and hashing of the surface vertices of the object. Each vertex is discretized with respect to a cell (an axis aligned box). The coordinates of the vertex (x,y,z) are divided by the given cell size and rounded down to the next integer. As in the paper the discretized vertex is: (i,j,k) where i = x/l, j = y/l and k = z/l. Then, a hash function maps the discretized vertex to a 1D index h. I used the following code:
inline unsigned int hash(int xi, int yi, int zi) {
unsigned int h = (xi * 73856093)^(yi * 19349663)^(zi * 83492791) ; //same as in paper
return h % sizeOfHashTable} //sizeOfHashTable=big value
}
STEP 2:
Discretization and hashing of the collision primitives as in step 1. For example, for each surface tetrahedron of the object, I compute the AABB and discretize the minimum and maximum values as we did for the vertices. Hash values are computed for all cells affected by the AABB of the tetrahedron. This is a tricky part and I can explain a bit further if you want. Then, all the vertices found at the according hash table index are tested for intersection. The intersection test can be: vertices inside sphere, tetrahedron or box, or if continuous collision detection, you can use segments versus sphere, tetrahedron or box.
The rest of the paper determines an optimal size of the hash table and optimal hash function.
CONCLUSION:
Good stuff: The method handles collision detection for deformable objects (cloths and volumetric objects) and rigid bodies. The method handles self-collisions since it hashes all collision primitives and all vertices of all objects in the same table.
Bad stuff: It is not edge sensitive which means that it does not detect collision with edges. Object penetration happens when edges are not detected. The method detects if vertices are inside the object but not edges. Authors of the paper claim that this is not a problem.. well, not really, if the objects uses a low resolution with big triangles (like the case of triangles in videogames) the penetrations are really evident and things are very unrealistic.
Besides, it is difficult to compute a proper collision response. If a vertex is inside the object, which is the direction of the repulsion normal ? To solve this, I use previous vertex positions to compute segments and handle this problem.
I am not quite sure about the optimization at the end of section 4.2. It is not clear explained so I am not sure if I got it right (well, it works fine, so I think it is correct). But, is there a big signifcance for this optimization for small hash tables ?
Suscribirse a:
Entradas (Atom)
Entradas
