A novel broad-phase continuous-time collision detection algorithm

Abstract

Geçmişe kıyasla günümüzde oyun geliştirme araçları gerçekçi fizik simülasyonuna çok daha fazla önem vermektedir. Fizik simülasyonu, kavraması zor ve çok farklı açılardan yaklaşılabilen bir konudur, çünkü mükemmel fizik simülasyonu imkansızdır. Mükemmel fizik simülasyonun imkansızlığının nedeni, sonsuz çözünürlük, kesinlik ve dolayısıyla sonsuz bilgisayar gücü gereksinimidir. Bu yüzden oyun fiziği simülasyonunun amacı, bilgisayar gücünün mümkün kıldığı kadarıyla oyun dünyasını gerçekçi göstermeye çalışmaktır. Fizik simülasyonunun kesinliğini ve doğruluk oranını azaltarak daha hızlı bir simülasyon elde etmek ve tersi her zaman mümkündür. Bu yüzden simülasyon verimliliği büyük önem taşır. Biz işbu çalışmamızda sürekli-zaman çarpışma tespiti algoritmasına kendi geniş-aşama algoritmamızı ekleyerek fizik simülasyonunun verimliliğini arttırdık. Bunu algoritma çıktısını hiç değiştirmeden, yani gerçekçilikten ödün vermeden başardık.

Today's game development tools rely on realistic physics simulation more than ever. Physics simulation is a highly sophisticated subject, which can be approached from various angles, because of the impossibility of exact simulation. The impossibility of exact simulation for real world physics comes from the requirements of infinite precision, resolution and therefore infinite computational power. Hence the main aim of game physics simulations is making the game-world seem as physically realistic as feasible within the computational power limitations. One can always increment the physical precision and the number of active physical objects at the cost of performance and vice versa. This makes performance a critical issue. In our work we optimize the continuous-time collision detection algorithm by adding a novel broad-phase step to improve performance without any loss of realism, i.e., the output of our optimized method is exactly the same as the old method.