How to Increase the Degree of Accuracy when using Time-Critical Collision Detection Algorithms

Most modern computer games need some kind of collision detection. It could be a car bumper grinding against a road barrier or a thousand pieces of debris interacting with each other during an explosion.

The traditional method of checking for collision and probably the simplest is to draw a bounding sphere around the object and then run checks against every object to see if they intersect. Where there’s an intersection a collision has occurred and the application can carry out the appropriate action.

This is simple enough for a few dozen objects but it is very costly in terms of processor cycles and when the number of objects increases to the hundreds and more likely thousands it can really noticeably slow down the game and make it appear “jumpy” or even stop altogether.

There are currently quite a few different methods of collision detection out there and all have their strengths and weaknesses. In this paper I will review a few of the more popular concepts and methodologies and expand on those and include some of my own.

I have decided to only include published academic papers recognised by the scientific literature digital library and search engine (CiteSeerx). Papers from external sources have been excluded from my research because they cannot be credible to me. Only papers written in English with scientific findings have been included.


In “Approximating Polyhedra with Spheres for Time-Critical Collision Detection” by Philip M. Hubbard a method for approximating polyhedral objects to support a time-critical collision-detection algorithm is presented.

The algorithm approximates objects by a hierarchy of spheres that allow the algorithm to progressively fine tune the accuracy of its detection based upon the time available, stopping as necessary to preserve the frame rate of the application and eliminating “jerkiness” in the picture. This is designed to achieve a smooth animation.

Hubbard speaks of a pre-process that uses medial-axis surfaces which are skeletal representation of objects. These skeletons guide the optimization technique in creating the hierarchies of appropriate accuracy for the later detection of collisions. Hubbard claims that this method of detecting collisions used in a sample application is consistently 10 – 100 times better than previous collision detection algorithms, maintaining low latency and a nearly-constant frame-rate of 10 frames per second.

This time-critical algorithm maintains its real-time performance even as objects become more complicated.

In “Real-Time Collision Detection and Response Using Sphere-Trees” by O’Sullivan, C. Dingliana, J. The problem of collision detection and response in real time is discussed in great detail. They describe a process of detection that approximates the objects using sphere-trees and an interruptible detection algorithm that tests for collisions faster but with less accuracy.

Only collisions perceivable to the human eye are allocated more time than those that aren’t as visually important, for example dust and dirt being disturbed on a floor compared to a rocket missile being fired at a target. Using the time available a degree of accuracy is decided to reduce inaccuracies in collisions. Using a new algorithm and sphere-trees an appropriate response for colliding objects can be decided.

When dealing with a large number of objects in a virtual space, the outcome cannot be pre-determined and therefore must be calculated in real time. This means that all of the collisions occurring within a given time frame must be calculated and the appropriate response taken. With a large number of objects the idea is to decide how important any given collision is in terms of what the user will see as accurate and inaccurate. The collisions marked as important will be given more of the processing time for that frame and therefore can calculate a more accurate collision than a non important collision which will inevitably be estimated using rough collision detection.

With a frame-rate of 60 per second there are 100 milliseconds available to determine any collisions, act on a response and render the new frame. In “Real-Time Collision Detection and Response Using Sphere-Trees” an example is given describing many rocks falling down a cliff-side. The rocks collide off each other and bounce away or break up into smaller pieces.

There are many bottlenecks in any given system that emulates reality, depending on the level of realism required. Computing such realism puts a heavy tax on the processor and increasing computation power alone is not enough and not a viable option for many users. So sometimes trading accuracy for speed is necessary in the aim to achieve the highest level of realism in any given time frame.

Traditional collision detection methods involve a lot of geometrical intersection tests to see if any polygons from one object intersect with a polygon from another. Improving on this foundation method calls for the world to be divided into hierarchical volumes to localise the areas where the collision occurred. These include sphere-trees [Palmer and Grimsdale 1995] [Hubbard 1995, 1996] [Quinlan 1994].
Most attempts at realistic collision detection are made up from two or more phases of detection. The broad phase is where approximate intersections are detected this eliminates entities that are far away from each other that cannot possible be intersecting. This allows the narrow phase to begin calculating more accurate collision detection.

Speed and accuracy has been the focus for many papers on realistic collision detection, the issues of a consistent frame rate also needs to be considered. For example a room with many balls bouncing equally spaced apart will have a manageable number of collisions. However it is safe to assume that occasionally two or more balls will collide, eventually sending all the balls into a corner of the room. There are now a large amount of possible collisions that need to be checked every few milliseconds and so the frame rate will reduce dramatically. This will ultimately result in a “jerky” or unrealistic animation.


The standard and demand for time-critical collision detection is constantly increasing. As there is a higher demand for realism in games the need to be able to accurately detect significant collisions increases. There are more and more applications that’s goal is to emulate realistic scenarios and with ever more powerful hardware collision detection algorithms are constantly being upgraded and becoming more efficient.

A detection algorithm is expected to maintain real-time performance as applications geographical content changes. Be it a flock of birds being disturbed in a city landscape simulation or an earthquake simulation designed to test buildings structural properties.

A time-critical detection algorithm can cope with any number of geometrical changes because it approximates object surfaces. This means that performance does not degrade as geometric intricacy increases. Traditional collision detection algorithms however process the real surfaces of objects so their processing times must necessarily increase with geometrical intricacy. This is unacceptable for interactive simulation applications. Increase in the complexity of objects does not make users care less about speed and responsiveness.

However, because a time-critical detection algorithm uses approximation accuracy will inevitably decrease. The easiest way to measure this inaccuracy is the measure the distance between two objects that it considers to be colliding. Collision response when the distance between colliding objects is less than zero will alter the orientation of objects will change the path of said objects in future frames. These inaccuracies will accumulate and can sometimes cause unacceptable qualitative changes, but these are often acceptable.

Even with said inaccuracies the overall accuracy level is high and inaccuracies would disappear very quickly. Even for objects controller by users, the inaccuracies would quickly disappear as humans are skilled at correcting subtle changes unconsciously.

I’m very interested in increasing the degree of accuracy when using time-critical collision detection algorithms. If a system maintains a steady frame-rate and can deal with any number of objects without taking a hit on performance the only real thing left to improve is accuracy and this is what I would like to investigate.
Within my academic area of discipline time-critical collision detection is a major player. The goal of computer games is increasingly to recreate a realistic scenario. This means realistic collisions produced in real-time without any delays. Should any delays occur then the sense of realism is ruined, this depends heavily on what is happening on the screen though, in a screen where there are fast moving objects a higher frame rate is needed to “fool” the eye. But in a slow moving scene, with slow moving fog for instance, there really isn’t much difference between 10fps and 1000 because the distance the fog has moved frame to frame is tiny.

Perhaps then time-critical collision detection should be based on what the frame rate needs to be in order to create a realistic fluid animation that the eye will believe.


References

[1]Philip M. Hubbard. Approximating Polyhedra with Spheres for Time-Critical Collision Detection. ACM Transactions on Graphics, Vol. 15, No. 3, July 1996, pp. 179-210. Online at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.2687 (as of 3/7/1996).
[2] O’Sullivan, C. Dingliana, J. Real-Time Collision Detection and Response Using Sphere-Trees. Online at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1282

iPlay

Thomas Hulversthorn came to give us a presentation on mobile gaming from iPlay. He mentioned that he started in business as a tester and then he moved on to iPlay.
He showed us few games that iPlay developed for mobile phones and he tried to explain the limitations on mobile gaming as there are few things to consider when developing a mobile game such as the screen size, the control of the game and mainly the memory available on the device.
At iPlay they have to consider about all the handsets are available in the market as they all run on different software and they all have different memory sizes, so they have to develop a game that will run on most of the handsets.
He gave us an example how they run a production at iPlay;

Mobile Game
Consider all the advantages.
Consider all the limitations.

Mobile Coverage
They have to try and cover most handsets available on the market.
Project Workflow
Create a first playable game.
Choose high end/low end.
Start testing the game.

Testing
Test status reporting.
Create the test strategy.
Create the test plan.
Perform test analysis.
Design test.
Schedule execution of test.

He also mentioned that mobile developing is not one of the first choices for the graduates but he recommends that it should be the first step in the industry to gain skills and experience to step up in the industry.

Sony Evolution

We had David Bramhall and Vicky Rowley from Sony Evolution. David worked there as a producer and Vicky was on the HR department.

David gone through how he started in the industry as a QA first and then he also explained all the different departments at Sony Evolution.

Departments at Sony Evolution

Coders – Test dev/Game/Rendering/Tools/Audio/Physics/Ai

Art – Art Direct/Environment/Texture/Technical/Caharacter/Vehicle/VFX/Concept/Graphical Eq

Animation – Director/In Game Animator/Cut Scene/

Design – Director/Lead Designers/Designers/Al Riggers/Level Scripters/Interface Desginers/Level Designers

QA – External Publisher/Internal developer/Embedded/Localisation

Game Dev Sectors – Console/Handheld/Mobile/PC/Publishers/Outsources/Console Manufacturers

Vicky explained what HR does at the company and gave us tips on how to apply jobs. There are some points below that she wanted us apply to all.

Ways To Apply

· Direct Application

· Agency

· Contacts

CV & Covering Letter

· Be clear on what you want to do

· Know What is expected in the role

· Sell Yourself

o -Covering letter (1 page max, Reference CV)

o -CV (3 sides max, don’t lie)

CV Sections

· Personal Profile

· Key Skills

· Work Experience

· Education

· Other Information

o -Volunteer Work

o -Memberships

o -Awards

· Interests

The Portfolio

· Code

o Language Samples/Working Demo/Technical Test

· Art&Animation

o Range of Specific Skills/Techniques/Software

· Design

o Level Design/Game Design Proposal

· Production

o Project Plans/ Scheduale

· Website

The Interview

· Expect technical and searching questions

· Expect competency/Situation Based questions

· Be Passionate and enthusiastic

· Do your homework

· Why you??

· Be yourself!!

Summary

· Stand Out

· Be enthusiastic and passionate about video games

· Intimate knowledge of your subject matter

· First role difficult to get

· Learn how the development process works

· Learn about the company and its place in the industry

Benefits

· Pension Scheme

· Private Health Insurance

· Income Protection /Life assurance

· Discount Sony hardware

· Free Sony games allowance

· Bonus scheme & profit share

Heinz - Health & Safety

Heinz came to present the Health and Safety issues at a workplace. They wanted to make sure what an accident is in a workplace and they explained that an accident is unplanned and unwanted event. They have to make sure in Health and Safety department that they have to prevent and put barriers to avoid accidents happening at work.

They also mentioned that Health & Safety splits into three areas; triggers, behaviour and consequences.