This repository contains the implementation of a Triangle Boolean Subtraction algorithm developed to create holes in navigation mesh polygons. The algorithm is designed to handle cases where single precision floating point is required for performance reasons, making it suitable for use in game development.
The need for this algorithm arose from the necessity to subtract one triangle from another to create obstacles in navigation meshes. This process involves complex geometric calculations, and after extensive research and testing, this solution was developed.
- Triangle Subtraction: The algorithm performs boolean subtraction on triangles, simplifying the problem to 20 possible cases.
- Optimized for Performance: The implementation uses single precision floating point for faster performance, crucial in real-time applications like games.
- Reliable and Tested: The algorithm has been rigorously tested with billions of cases, ensuring stability and accuracy.
The algorithm is implemented in C/C++, and can be integrated into projects requiring navigation mesh manipulation or other geometric processing tasks.
The best way to use it is to integrate it within your application.
For a detailed explanation of the algorithm, please refer to this blog post.
The algorithm starts by checking for overlap between the triangles using SAT, reorients them if necessary, and proceeds with collinearity checks. Once the overlap is confirmed, an overlap polygon is created, cleaned up, and inserted into the subject triangle. Additional checks ensure that the points are correctly processed and handled to avoid stacking or precision errors.
The algorithm constructs tables to keep track of vertex information, including whether a vertex is outside, if it's a crossing point, and its relationship to other vertices. These tables are then used to generate the final resulting polygons.
- Documentation: The algorithm is based on concepts from this documentation.
- Sutherland-Hodgman Algorithm: For clipping operations, implementation of Sutherland-Hodgman algorithm can be found here.
- SAT: Separating Axis Theorem(SAT)
This project is licensed under the MIT License - see the LICENSE file for details.