We implemented two-phase collision detection with triangle meshes, or polyhedrons with only triangular faces, with an emphasis on the broad-phase portion. Our algorithm relies on placing objects in a fixed grid subdivision of space based on their size, and improves beyond the naive O(n^2) by only checking for bounding ball intersections between objects of adjacent grid cells. In order to permit parallelism, our narrow phase checks are performed entirely after the broad-phase; these are also parallelized. We then analyzed the speedup gained from these parallel versions, and evaluate the effectiveness of different OpenMP schedulers and various re-orderings of steps of the algorithm.