Simple yet robust triangulation for polygons containing multiple holes for real-time 3D industrial applications

Abstract

In industrial applications such as CAD modeling, manufacture or automated systems, it is common to work with data models that are represented by polygonal shapes, or models that produce polygonal shapes out of complex geometry defined by lines and curves. However, this data has to be converted to a triangular mesh before it can be processed and/or rendered by the GPU. Existing solutions that generate triangular mesh out of polygonal shapes either do not support holes or have limitations on how many holes can be present at the same time. Most modern advanced solutions need considerable effort to implement, debug and maintain, which involves significant development costs. In this work, an alternative solution is proposed, which is relatively simple to implement yet is sufficiently robust to handle all possible input scenarios handling any number of holes, or inner polygons in an outer polygon, assuming that polygons do not intersect each other or themselves, and makes no assumptions about the winding order of polygon vertices. The proposed solution involves initial pre-processing work, merging inner polygons into an outer polygon, and then performing polygon triangulation using one of the two proposed variations of an Ear Clipping algorithm. The proposed solution is shown to handle practically an unlimited number of holes in polygon independently of its shape. Quality and performance comparison between two techniques is also provided and discussed, along with the images of a real life CAD application, which implements the proposed solution.