Experiences in 3D

New website

2011-06-19T16:16:00.000-07:00

I don't work at Eden Games (the internal studio of Atari) any more. So, I have radically modified my website so many links might be broken (all paper publications for example, although you can google them and you will find them). I will update them gradually.

Soon, I will also give some more news on my new projects. Stay focus !

Nanoenvironment Interactions based on virtual reality including force feedback

2010-10-08T14:56:00.000-07:00

After reading the title of this post, you might be thinking that you are not in the website of Cesar Mendoza. "eh, he works in video games, what is this nano.. stuff about ?"

In fact, in the past I did some research in nano technology. Under the support of two research teams, the ICA-ACROE lab of the Grenoble Institute of Technology (INPG) and the PicoGroup of the LEPES lab of the Néel Institute of the CNRS I proposed a research project for making investigations in the nanoworld.

These two groups are leading teams in mechanics, robotics and moreover in nano physics.

The idea of the project was to develop nanogrippers (say, a gripper tool but incredibly small) that we could use to execute 3D tasks, for example, assembly manipulations. Imagine manipulating atoms with your own hands.

The design of these nanogrippers included virtual reality to enable the user to "actually see" the nano manipulations and force feedback to provide the sensation of "feeling" the manipulated objects, i.e. "touching the atoms". This design was strongly based on the Atomic Force Microscope (AFM). Just to mention, at the time I wrote this document, it was possible to use Atomic Force Microscope as a tool tip to touch nano objects.

The project was really ambitious and exciting and we submitted to the CNRS, Unfortunately, the project was rejected and of course, I was not assigned to follow this project.

Just as a anecdote, when I presented this project in Paris, at 9:30 am, in 2006, one person of the jury was sleeping (I couldn't believe it !) and the other spent his time watching at his PC without taking care about what I said. I wish I could know the name of the guy who was sleeping... Under these circumstances, I was not really in the mood to show the great potential of the project.. the project, as I said, was rejected.

Anyway, the thing is that I still believe in the future of this and if you have a AFM, I can send you all the details of the project (in French). For now, you can get the English summary here.

Use it !

Siggraph 2010 mug

2010-08-17T03:58:00.000-07:00

Being a reviewer for the last Siggraph 2010 has been a pleasure. If you work in the Academia being a reviewer is a normal part of your daily activities, since although you are not paid, the payment is implicitly included in your Academia salary besides giving you a plus in your CV for further scientific evaluations.

However, if you are working in the industry, it has a different meaning. You don't get paid either, it is not really worthy for your work since in your CV does not mean much for recruiters, your wife is upset for loosing time in something without any payment. From my point of view, it is done by the pleasure of reading and reviewing highly technical works. It gives you some sort of self-confidence.

I don't thing my boss cares if I am a SIGGRAPH reviewer or not, unlike the boss of normal academia researchers. But, still, you get a free and pretty mug as shown in the picture.

The book: Game Physics Pearls

2010-08-06T04:52:00.000-07:00

I have written a chapter on this book about how to set-up soft bodies in games. Within the chapter you will find sample code on how to implement the most difficult features of the model. It has been tested in one prototype using the Alone in the Dark framework for PC.

Within the book there are other very interesting topics related to physics in games. All of them give incredible hints in how to optimize the algorithms for games.

So, it would be a good idea if you buy the book. You can get it from Amazon.

VRIPHYS : Virtual Reality Interactions and Physical Simulations : http://www.vriphys.org

2010-06-30T05:00:00.000-07:00

You might be surprised that the website of the VRIPHYS workshop has disappeared. At the moment, this link: http://www.vriphys.org does not work any more.

The main reason of this is because it has been decided to change to a different host provider for the website. Hence, the previous Italian provider (aruba) does not host the vriphys website and has therefore removed the information.

Vriphys will be now hosted and managed by INRIA, France. Find the latest 2010 vriphys (the 7th) workshop in this link.

As a partner event of Eurographics, you can find the papers and scientific committees of the previous workshops in the Eurographics Digital Library. HERE

Note that papers of the years 2004 and 2005 are not available in the Eurographics website since, although partnership with EG was obtained in 2005, it was until 2006 that they started to store the papers and related information.

In any case, if you need the vriphys papers or other information related to 2004 and 2005, feel free to contact me.

Paris Master Class

2010-06-08T04:44:00.000-07:00

Next June 23th, 2010 I have been invited to give a "master class" in Paris. The training is a one-day set of lectures, all related to video games. In fact, it is a review of several math fundamentals for game programming. The course is accompanied with user-cases and sample code.

The lectures focuses game professionals who want to develop and improve their skills in a concrete way. Although it is designed for intermediate level, I will be starting at some basic levels but I will also touch some interesting and practical advance topics.

I am posting this a bit late but you can still register in their website.

Voila mes amis !

Test drive unlimited 2

2010-05-26T03:53:00.000-07:00

The studio I am working in, EdenGames, is about to release the next edition of the well-known game test drive.

It is a car's game with a lot of "social and on-line" stuff. So, if you want me to keep my job, buy this game.

You can see some trailers of the game on its website. Click here

If interested, you can also check more details on Nour's interview. Here is that interview:

Fast update

2010-05-08T12:00:00.000-07:00

Yes, I have not been very ofter writting posts here... well, I will try to arrange that. I have been very busy lately, extremely.. for those becoming dads will know the short nights. Anyway, some bits of updates

I finished my reviews for SIGGRAPH 2010. In fact, you don't get paid for do it but it is always good the review high quality papers (mostly) and it is also good for your self esteem. Here is the link for the SIGGRAPH of this year.
I have just finished a book chapter which will be published this year. The editor is Gino Van den Bergen and the publisher is AK Peters. That took me much time of my nights. I will give you more details as soon as I know.
I have been fixing my GJK + EPA collision detection algorithm. In fact, I have wrote a post on that, but much tuning is required to make it work fine. I will give details on this in a different post.
I have started working with Kd-trees for occlusion, visibility and other related problems. I will let you know more about this in other post as well.

Vriphys 09

2009-08-20T03:42:00.000-07:00

Oh, ahh, I always do it at the last minute... but I do it right. I finished reviewing some papers for this conference.

VRIPHYS 09

It is a conference for professionals, researchers, students interested in virtual reality interactions and physics simulations. I think it is a great forum where people can meet in a friendly manner.

It is not the huge show of Siggraph, not even EG or SCA. It is more focused in real-time and interactions and it has the support of Eurgraphics. I hope this year it will have excellent papers as previous years.

Convex decomposition

2009-08-19T13:42:00.000-07:00

I have recently wrap the extraordinary convex decomposition library of John Ratcliff. I did it with the 2007 version. I have added some functions (from John's as well) to find the best fitting capsules, spheres and oriented boxes of convex hulls.

The 2007 version has some bugs that I am currently fixing but it works fine. If you want a more robust version you can get that one of 2004 which is the one that the guys from Bullet have wrapped. I wrapped it as well and it works just perfect. The disadvantage is that it does not include best fitting features and that the splitting plane of concave objects is not always the best. Besides, it is implemented using floats instead of doubles.

John did a great job. At the beginning I tried to implement the convex decomposition myself, but I had some troubles trying to find the best fitting plane. It worked in some cases but in others it failed terrible. So, I decided to wrap John's convex library. It is a bit slower (since it computes the decomposition in a "brute force manner" but it is worthy to wait 30 seconds for decomposing a concave object of 700 triangles into a set of convex hulls.

I will use this together with my GJK implementation :)

Click here for the link of John's convex decomposition library. If you use it, feel free to donate something to John's son association.

Implementation of GJK

2009-07-17T04:09:00.000-07:00

Wow, quite a lot without posting here... I will try to be better on this.

After some relaxing weeks implementing intersection tests for basic primitives (triangles, box, spheres, etc) I have decided to go further and implement a generic algorithm to detect collisions: I decided to implement the well known GJK algorithm (also known as Gilbert-Johnson-Keerthi algorithm).

Here, I will just describe my general thoughts and experience while implementing this (time of implementation, bibliography) but I will not give details on the theory, which might take lots and lots of lines.

Actually, the GJK algorithm is only a part of a whole collision detection architecture. It only gives you the distance between two convex objects but it is possible to adapt it to a clever architecture to provide you with contact points a penetration depths.

So, I did a fast "state-of-the-art" just to realize that it was not an easy task. Even worst, my dear boss was asking me for details on the time that it can be implemented and just looking all the maths, I was just scared !

Unless you have a good experience working with convex theory, Minkowski sums, affine transformations, you will do the implementation very fast or, if you are like me, not a real expert on this, it will take about "1 month" working 8 hrs a day to implemented the whole thing. I should say that you can get it much faster from Bullet or Solid libraries, but here in the company, due to license constraints, we have to implement everything from nothing.

I should accept that I had good inspiration from these books:

Collision Detection in Interactive 3D Environments, Gino Van der Vergen
Real-Time Collision Detection, Christer Ericson

In the first book, the one from Gino, there are a lot of maths (quite a lot, I would say), but you can get the Solid library where GJK is implemented. The book explains everything in the code, mainly the numerical problems, and provides you of a hybrid method to get penetration depths using GJK. I compiled the library and it runs very nice. It was a huge source of inspiration. However, there is no way it will make it for our PS3 compilation standards and many many problems arise while integrating SIMD operations.

The second book gives you a better introduction to the GJK problem but it will no go farther into the details. So, I think both books complement each other very well.

I also took some inspiration from Bullet. It computes distance to simplexes in a more direct way but still, it remains quite complex.

So, I implemented GJK + EPA as explained in Gino's book and so far it compiles perfectly in within our SIMD standards and PS3 compilation constraints.

The main idea is to add an extra convex radius to each convex shape (as Havok does) . Then

GJK is used when inter-penetrations are small. Using EPA when penetration are larger is quite unstable. To use GJK we surround the objects with a little margin (the convex radius in Havok terms) When the inter-penetration is within this margin, we compute the closest distance between the original objects. The witness points of the distance are projected to the boundaries of the enlarged objects in order to return the penetration depth.

If the original objects penetrate as well, we use EPA (Expanding Polytope Algorithm). EPA is fully explained in Gino's book. It is really worthy to take a look on it. Be sure on reading page 162 which is very helpful to get rid of many numerical errors. The general idea is to expand a 3D politope which is further used to extract the penetration depth. You can have a better idea if you have a look on Solid 3D.

To avoid jittering you should better allowed some little penetration and create a persistent manifold as Bullet does. The little penetration is easy to allow since we have already implemented a convex radius. At the beginning I "snobbed" the persistent manifold and only catched contact points (the deepest). But it turns out that this is very important and an optimal persistent manifold should be implemented. GJK retunrs always one contact point, so imagine for a capsule/box collision: it will give you a jittering due to only one contact at a time. You have to keep one contact point. The most clever, I have found, to do this, is to do it as bullet. Keeping the contact points that covers the maximum area of the manifold. Although, if you go further into Bullet's code, you will notice a risk for slippering.

Anyway, no more time to write, now..

take care !

PS3 compilation hints

2009-03-25T05:26:00.000-07:00

Templates are not transparent all the time when compiling with PS3. I have been compiling a set of hints from my short experience. I will put a list of them shortly.

THE SHORTEST COLLISION DETECTION SUMMARY EVER

2009-02-16T04:28:00.000-08:00

I. INTRODUCTION

Collision detection between virtual objects is one of the bottlenecks in real-time applications.

Unfortunately, after more than 20 years of research, there is not a generic method that can be used in all applications.

The main reason of this is that the objects involved in the collision detection process become more and more complex. Hence, we have passed from using only rigid bodies to use more complex objects such as volumetric deformable bodies, cloths, fluids, etc.

Refer to [1][2][3] as a good starting point. Although most of the available techniques used to detect collision between rigid bodies need to be modified for deformable objects, most of these techniques share a basic approach. This approach divides the collision detection process into 3 steps:

1. Broadphase
2. Middle phase
3. Narrow phase

Next, I will briefly describe this steps. Note that we only consider static collision detection.

II. THE BROADPHASE.

In this stage, bodies are encapsulated in simpler volumes (spheres, boxes) for fast intersections.

This way, non intersecting pairs of complex objects are rapidly culled out from the collision process.

These simpler objects may be spheres, axis aligned bounding boxes (AABB), oriented bounding boxes (OBB) just to mention the most typical ones. They add little extra memory to the simulation but highly increase the performance of our collision detection process.

There is not a best choice between these bounding volumes, and some tests should be done to pick the best for a particular situation.

Decomposing the space into uniform grids and checking the interference between the cells and the simpler volume can additionally be added to this stage to speed up the collision process.

III. THE MIDDLE PHASE

The broadphase identifies the pair of bodies that should be tested for possible collision detection. Instead of directly test the primitives of the bodies (triangles, points) we may add an additional stage that can accelerate the collision detection process.

This additional stage is the middle phase. The main idea is to construct a bounding volume hierarchy of the object: the simpler volume used in the broadphase is subdivided into inner sub-volumes and each sub-volume into inner sub-volumes and so on, until we reach the primitives of the body.

Once the pair of objects are identified in the broadphase, the middle phase uses the bounding volume hierarchy to identify “regions” of the bodies for additional collision detection queries.

As an example, in a bottom-up construction approach of the bounding volume hierarchy, we select a small set of primitives of the object ( say 2 or 3 triangles for example) and we enclose them within a bounding volume. This is a leaf node. We do the same for all the primitives of the object. We end up by enclosing all the primitives of the object with small bounding volumes.

Next, we select a set of these small bounding volumes (2 or more and normally neighbors of each other) and enclosed them within a larger bounding volume. We repeat this for all the small volumes. As a result, we will have a smaller set of larger (middle) bounding volumes. We repeat the process until we have only one bounding volume, which represents our root node. Each level of the hierarchy represents a tighter fit than its parent. The number of level of the hierarchy is usually known as the depth of the tree.

Note that these hierarchies are constructed in an offline process.

The middle phase starts by testing the root bounding volume of bodyA (rootBVA) with the children bounding volumes of the root bounding volume of bodyB (rootBVB). If an interference exists between rootBVA and only one of the children of rootBVB we will know that the collision does not happen with the other children of rootBVB. In the next iteration we will not include them in the intersection tests. We will only test the colliding children with the children of the rootBVB and so on.

Alternatively, there exists a top-bottom approach in which we start by using the simpler bounding volume of the object and subdivide this volume into inner subvolumes in a recursively manner until we reach the primitives of the object.

For rigid bodies, there is not a clear advantage between OBB, AABB or bounding spheres trees. Their efficiency, memory consumption and accuracy depend on the application and on the enclosing body.

The main difference comes out when they are applied to deformable bodies (volumetric, 2D cloths) since these hierarchies need to be updated at each time step to adapt to the new deformed shape of the body.

Van der Bergen compared AABB's and OBB's hierarchies for deformable objects and determined that AABB's are the best option [4]. He also showed that, although hierarchies can also be rebuilt, updating them is almost ten times faster than rebuilding them. Larson et al. [5] compared different methods for the hierarchy updating process based on bottom-up and top-down strategies. They found that these methods depend on the depth of the tree and proposed a method that uses both strategies.

There has not been a comparison between sphere hierarchies and AABB's hierarchies since sphere trees were for long time rejected for its poor tightness to the body. However, latest results have shown that sphere trees can be as tight as AABB's trees and then can be an excellent option for deformable bodies. Their only problem is that their construction is not as simple as AABB's trees but the update can be much faster (note: last sentence is only an empirical personal assumption).

Advance issues concern the update of the trees when the encapsulating body suffers a topology modification, i.e. when the object is broken or cut. If it is a partial fracture or rupture, the tree most probably will need a rebuilt, which is computationally costly. If the object is broken in hundreds of sub-bodies, then the tree hierarchy might result to be obsolete.

Additionally, as an advance issue, auto-collisions might occur, (e.g. cloth self-collisions) and this is a subject in which volume hierarchies haven't present an effective solution.

To handle these two last issues, alternative approaches can be used. Instead of using bounding trees, we can used an optimized spatial hashing for collision detection of deformable objects [6].

IV THE NARROW PHASE

The result of the middle phase is either no collision (i.e. no leaves of body A are colliding with any leaves of body B) or "leaves collision" (i.e. at least one bounding volume leaf of body A is overlapping at least one bounding volume leaf of body B).

We focus here in polygonal models.

The leaves of the bounding volume tree (the smaller boxes and spheres in the hierarchy) are associated to a small set of primitives of the object. Hence, a little sphere will point to 2 or 3 triangles. Associating triangles to little bounding volumes is not a simple task since some aliasing problems may arise (e.g. a triangle may be associated to different bounding volumes under different circumstances).

Therefore, the narrow phase consists on finding the intersection of the primitives (e.g. triangles) enclosed by the bounding volume leaves of body A and B. Finally, we need to find the separation normal and the penetration distance as the minimum information for the collision response. Additional information can be included such as the intersecting triangles or edges. This additional information can be useful to build the Id of the contact.

Alternatively, instead of finding the primitives associated to the each leaf bounding volume, we can use the little leaf bounding volume as a "coarse primitive" of the body and compute the separation normal and penetration distance. We lose accuracy by doing this, however, if the approximation of the object by the deepest level of the hierarchy is good enough (i.e. the leaves were extraordinary calculated) then we can have an acceptable response and we can earn lots of time computations and memory consumption is highly reduced.

Finding contact information for triangles or other primitives is not an easy task. Methods such as the Lin-Canny Closest Feature algorithm may not be well suited since it does not provide penetration information and the well known and complicated to implement GJK seems to be the best option to best measure interpenetration.

BIBLIOGRAPHY

[1] Collision Detection for Deformable Bodies, Teschner. M et al., Proc. of the Star Reports, EG 04, pp 119-140

[2] 3D Collision Detection: A Survey, Jimenez P. et al, Computer And Graphics, 2001 pp 269-285

[3] Real-Time Collision Detection, C Ericson, Elsevier 2005

[4] Efficient Collision Detection Of Complex Deformable Models Using AABB trees, Van den Bergen, G. J Graph Tools, 2,4 (1997)

[5] Collision Detection for continuously deforming bodies, Larsson T. et al, EG Short Presentations 2001, pp. 325-333

[6] Optimized Spatial Hashing for Collision Detection of Deformable Objects, M. Teschner et al. Proc. VMV 2003

Happy New Year 2009

2008-12-31T00:58:00.000-08:00

To all and everyone.

Merry Christmas 2008 !

2008-12-23T13:38:00.000-08:00

Yes, Merry Christmas to anyone hitting my blog and/or my website.

Time Critical Collision Detection

2008-12-16T03:37:00.000-08:00

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.

Atari is ramping up

2008-12-10T03:48:00.000-08:00

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 !!

Evaluating Physics Engines For Games - PAL -

2008-12-07T10:54:00.000-08:00

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:

Integrator performance (i.e. solution of ODE's)
Material properties (i.e. frictions, restitution)
Constraint stability
Collision detection
Stacking test

The authors had these results: AGEIA-Nvidia has the best integrator performance. True Axis gave the best results for restitutions followed by Bullet and AGEIA-Nvidia. Static friction was best simulated by Newton followed by AGEIA-Nvidia. With respecto to constraints, Tokamak provides the best results solving constraints in the least time, ODE provided the most accurate results but requires a lot of time to solve the constraints. In this aspect, among the worst you can find AGEIA-Nvidia. This is very surprising since I've been using AGEIA-Nvidia and it has been quite accurate when solving the constraints. Collision detection was best carried out by Tokamak and Bullet, however, it should be noted that other engines failed this test because the test was not properly adapted to the engine. For box stacking the author only provided a visual test claiming that all the engines pass the test with the best performance for Tokamak.

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 :)

Loving 2D games.

2008-12-03T23:42:00.000-08:00

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.

Optimized Spatial Hashing for Collision Detection: Implementation

2008-12-01T11:39:00.000-08:00

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 ?

Box2D -Part II-

2008-11-28T04:35:00.000-08:00

As I told you previously Box2D has been used in some games. A good example is the Crayon Physics Deluxe that won the first prize in the Independent Game Festival.

I really like this game. It is very original and simple. When my baby will grow, I will probably get this game. Hopefully, it will be available in a little toy-set instead of using the screen and computer.

Check it out the website of the game by clicking here. You can also check the little video below:

Box2D -Part I-

2008-11-25T14:22:00.000-08:00

Most of my previous research dealed with soft bodies, collision detection, real-time optimisation, biped robotics for virtual humans, but very recently I have started to investigate rigid body constraints (rigid body contacts, distance constraints, etc.) for real-time simulations.

I must confess that I am quite new in this. i.e. I have never implemented a contact ball constraint... now, this is about to change. Rigid body research is not new at all, there are more than 20 years that people has spent on that and now there are really good commercial software out there (e.g. Havok, Ageia, etc.) and also open source, like Bullet.

This is great, but still, if you want to implemented from nothing, you might need some documentation. Papers are the best choice, but if you have simple code available is just fantastic. So, I have found Box2D . It is an open source software where rigid body dynamics is implemented in 2D in a very friendly manner. It has been coded with an incredible videogame taste. It has already been used in some 2D videogames.

And the best thing for me is that it has the implementation of constraints in 2D. This implementation is actually 2D version of the constraints implemented in Bullet !

I have compiled some tests and surfed throughout the code and it is really good... so, as a first look, Box2D seems a very didactical starting point for rigid body simulation for games.

Cesar's reasons to get the XBox360

2008-11-23T12:29:00.000-08:00

Yeah, yeah, yeah !!! just look at the picture on the left !! it is my new little toy !

Yes, it is almost one month that I've got an XBOX 360. After quite a while of time thinking what to choose between an XBOX 360 and and a PlayStation 3, I have finally decided to choose an XBOX360.

I have only two games: Assasins's creed and GTA IV -special edition - great games !!

These are my reasons:

1) XBox is cheaper than a PS3.
2) Performance is almost equal between the XBox360 and PS3.
3) I don't care about BlueRay's PS3. BlueRay discs are more expensive than normal DVD's.
4) I am happy with the 60GB of the XBox 360. I am not a crazy film-game demo downloader. I don't need all the memory that the PS3 has.
5) When I was working at NaturalMotion, I've got GTA IV -special edition -for XBox360 for free, since I was part of the Euphoria team developper... So actually, I had already an XBox360 game.
6) Most of the people I know (except from my nephews that got the PS3) have a XBox 360, so I can share the videogames with them.

Eden Games in the heart of Atari

2008-11-19T12:48:00.000-08:00

As you probably know, Eden Games is the only internal studio of Atari.

Well, last November 7th, Eden Games has moved and now it is located in the heart of Atari in Lyon, France. It is just besides Electronics Arts.

So now, we are in the middle of a beautiful complex where the buildings seem to be boats parked in a port (just look at the picture).

Offices are now open-space style which I think is a good thing since it is easier to share ideas... however, we have lost the intimity of the 3person offices... But that is not all that we have lost, now I have to walk for 1 hour to get there and we don't have free drinks in the building anymore :(

VRIPHYS 08

2008-11-16T14:49:00.000-08:00

Last week I attended VRIPHYS 08 in Grenoble, France. VRIPHYS 08 is a workshop related to scientific research in the domain of interactive virtual reality and physical simulations.

The conference was organized by Francois Faure and Matthias Teschner. Click HERE to check the website of the conference.

The conference level was acceptable with some papers showing good research and some others with on going research. Most of the papers are related to real-time interactive 3D simulations.

I had also the opportunity to have dinner with some colleagues in the domain such as Matthias Muller, Matthias Teschner, Thomas Stumpp, Markus Becker, Francois Faure and others.

Brief, I enjoyed the workshop. Hopefully there will be another vriphys next year.

And if you look carefully, you will find me in both pictures !