Bounding Polygon Generation in 2D Games Through Contour Extraction

• Maria Laura Barboza Moroni UFERSA
• Paulo Henrique Almeida de Andrade UFERSA
• Judson Santos Santiago UFERSA

DOI: https://doi.org/10.5753/sbgames_estendido.2026.25609

Resumo

Introduction: Collision detection is essential for realistic interactions in 2D games, ranging from pixel-based methods to bounding objects. Objective: This research presents an automated tool for generating pixel-perfect bounding polygons from PNG images, aiming for higher precision than traditional AABB and less manual effort than polygon creation. Methodology or Steps: The system employs a Radial Sweep algorithm for external contour extraction, ignoring internal holes, and applies a collinearity filter based on Freeman Chain Codes to reduce vertex count, mapping directions between consecutive pixels and discarding intermediate points that maintain the same trajectory. Results: The developed tool, AutoBBox, successfully reduced geometric complexity while maintaining pixel-perfect accuracy. In a specific test case involving an irregular character sprite, the solution eliminated the 35% false positive collision area that resulted from standard AABB approximation, and minimized the geometric representation by 39% compared to the vertices typically required in a non-optimized trace.

Palavras-chave: Collision Detection, Contour Tracing, 2D Games, Digital Image Processing, Hitboxes

Referências

Alder, M. (1997). An introduction to pattern recognition: Statistical, neural net and syntactic methods of getting robots to see and hear. Course notes, Department of Mathematics, University of Western Australia.

Ericson, C. (2004). Real-Time Collision Detection. CRC Press, Boca Raton, FL, USA.

Freeman, H. (1961). On the encoding of arbitrary geometric configurations. IRE Transactions on Electronic Computers, EC-10(2):260–268.

Gonzalez, R. C. e Woods, R. E. (2018). Digital Image Processing. Pearson, 4th edition.

Lazaridis, L., Papatsimouli, M., Kollias, K.-F., Sarigiannidis, P., e Fragulis, G. F. (2021). Hitboxes: A survey about collision detection in video games. In Fang, X., editor, HCI in Games: Experience Design and Game Mechanics, pages 314–326, Cham. Springer International Publishing.

Linietsky, J., Manzur, A., e Godot Engine Community (2014). Godot engine documentation: BitMap class. [link]. Accessed on 21st March 2026.

Mandachescu, C. A. (2003). Path finding in 2D games. Master’s thesis, Concordia University, Montreal, Canada.

Mileff, P. (2023). Collision detection in 2D games. Production Systems and Information Engineering, 11(3):12–31.

Reddy, P. R., Amarnadh, V., e Bhaskar, M. (2012). Evaluation of stopping criterion in contour tracing algorithms. International Journal of Computer Science and Information Technologies, 3(3):3888–3894.

Santiago, J. S. (2022). Volt engine. [link]. GitHub repository.

Thompson, K. (2023). Generate pixel perfect colliders from sprites in Godot. [link]. Accessed on 21st March 2026.