Continuous-Time Collision Detection for CGAL

# Continuous-Time Collision Detection for CGAL **Applicant**: Jeffrey Cochran **Affiliation**: The Oden Institute at UT Austin **Mentor**: Sébastien Loriot (possibly co-mentored by Etienne Vouga of UT Austin) ## Executive Summary Funded by GSoC this summer, I propose to add collision detection to CGAL in a way that naturally builds on and extends [CGAL's existing AABB-tree functionality](https://doc.cgal.org/latest/AABB_tree/index.html). The project will focus on implementing trusted collision-detection methods, which are attested to by their use in projects like the [Godot game engine](https://godotengine.org/) as well as their continued academic propagation through works like Ericson's "[Real-Time Collision Detection](https://realtimecollisiondetection.net/books/rtcd/)" and courses like UT Austin's "[CS395T: Physical Simulation](https://www.cs.utexas.edu/users/evouga/courses.html)". ## Project Outline I envision the project having the following deliverables: - Modifications to CGAL's existing AABB tree functionality where necessary, e.g. to handle moving bounding boxes and dynamic restructuring of the bounding volume hierarchy - Broad-phase collision detection routine that utilizes CGAL's AABB tree to quickly rule out unnecessary collision queries and identify potential collision pairs - Narrow-phase collision detection routine that performs fast collision tests on the pairs of primitives identified in the broad phase - Tests to cover all changes and new functionality - Documentation of the above If time permits, there are always extensions that could be pursued. For example: - Performance optimization (e.g. caching collision queries) - Debugging tools (e.g. collision visualization and logging) - Additional bounding volume hierarchy support (e.g. OBB or k-DOP trees) - Additional out-of-the-box primitive support ## Proposed Timeline - [May 4 - May 28] - Discuss expectations and desired outcomes with CGAL mentor - [May 29 - June 4] - Review CGAL's existing AABB tree functionality and determine best course of action - [June 5 - June 18] - Create a public interface for collision detection - Create a simple example simulation for testing and documentation - [June 19 - July 9] - Modify CGAL's AABB tree for continuous-time collision - Implement broad-phase collision detection using AABB trees - [July 10 - July 14] - Prepare for midterm evaluation - [July 15 - August 6] - Create collision pair data structure - Modify broad-phase to return relevant collision pairs - Implement narrow-phase collision detection, iterating over pairs - [August 7 - August 23] - Clean up and prepare a test suite - Confirm successful build for different platforms - Write documentation - [August 24 - August 28] - Prepare for final evaluation ## Personal Information I'm Jeff Cochran---a native of Cleveland, Ohio and a PhD student in the [Oden Institute's](https://oden.utexas.edu/) CSEM program at UT Austin in Texas. Before starting this PhD program, I was the Head of Research and Development at the [Equity Engineering Group](https://e2g.com/), where I spent most of my time developing commercial software to solve engineering problems. My culminating achievement at E2G was the development of a suite of online engineering tools that now earns hundreds of thousands of dollars each year. I have other relevant experience, including my time as a visiting researcher at [Coreform](https://coreform.com/), where I worked on computational methods for optimal quadrilateral layouts, and my time as a GSoC contributor to the physics backend of the Godot Engine, where I improved soft-body dynamics. Finally, it's worth mentioning that I've already implemented continous-time collision detection (in C++) as assignment for Etienne Vouga's course on physical simulation. Concomitant with my work experience, I have a good background in physical simulation, computational geometry, and numerical methods. I've taken more courses than I want to list here, but the most relevant are probably the several courses I've taken in finite element methods and physical simulation for computer graphics. I'm happy to provide an extensive list of relevant coursework upon request. As a developer, most of my experience is in Python, C++, and Fortran (in that order). I've developed software in both a commerical and academic setting, and in both cases I've found that I prefer to work in groups of five or fewer. That said, working on the Godot Engine did provide me with a nice experience contributing to a much larger, open-source project. I foresee no reason that I couldn't work on this project full-time during the program period. When the program ends, I may continue to contribute to CGAL, although my availability will largely depend on the demands of my thesis-writing. Most likely, any major future contributions will have to wait until after my thesis defense. After graduation, I intend to start my own company, most likely focused on simulation for manufacturing. My personal interest in CGAL is twofold. First, I am of course interested in computational geometry, and CGAL offers a great opportunity to immerse myself in a productive way. Second, I hope to use this opportunity to evaluate CGAL as a geometry library for my own simulations. In any case, I'm excited to work with you, and I hope to hear from you soon.