| Revista: | Programación matemática y software |
| Base de datos: | |
| Número de sistema: | 000573324 |
| ISSN: | 2007-3283 |
| Autors: | , |
| Any: | 2024 |
| Volum: | 16 |
| Número: | 1 |
| Paginació: | 11-21 |
| País: | México |
| Idioma: | Español |
| Resumen en inglés | 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. |
| Resumen en español | En aplicaciones industriales tales como el modelado CAD, la industria de fabricación o los sistemas automatizados, es común trabajar con modelos de datos que representan contornos poligonales, o con los modelos que general polígonos a partir de una geometría compleja que se define mediante líneas y curvas. Sin embargo, para que estos datos pueden ser procesados y/o rendereados por GPU, los datos se tienen que convertir en una serie de triángulos. Las soluciones existentes que general triángulos a partir de contornos poligonales no son capaces de trabajar con orificios o se limiten a un cierto número de orificios que pueden estar presentes al mismo tiempo. La mayoría de las soluciones modernas avanzadas requieren de un esfuerzo considerable para su implementación, depuración y mantenimiento, lo que a su vez produce ciertas implicaciones importantes en cuestión de costos de desarrollo. En este trabajo, una solución alternativa se propone, siendo relativamente fácil de implementar y al mismo tiempo suficientemente robusta para manejar cualquier posible entrada de datos, incluyendo cualquier número de orificios e incluso cualquier número de polígonos internos, siempre y cuando los polígonos no se cruzan entre sí ni se auto-cruzan a sí mismos. La solución propuesta tampoco depende de un orden determinado de los vértices del polígono, solo necesita que este orden sea consistente. La solución propuesta involucra un pre-procesamiento inicial, donde los polígonos internos se integran a los polígonos externos. Una vez hecho esto, se hace una triangulación de polígonos utilizando una de las dos variaciones de técnicas propuestas que se basan en algoritmo de "Ear Clipping". En este trabajo se muestra que la solución propuesta puede trabajar con el número de orificios prácticamente ilimitados independientemente de su forma. Este trabajo también incluye una comparativa de evaluación de calidad y desempeño entre las dos técnicas propuestas, incluyendo unas imágenes de una aplicación CAD que utiliza estas soluciones de manera práctica. |
| Paraules clau: | Triangulación de polígonos, Algoritmo ear-clipping, Polígono con agujeros, Visualización en tiempo real |
| Keyword: | Polygon triangulation, Ear clipping algorithm, Polygon with holes, Real-Time visualization |
| Text complet: | Texto completo (Ver PDF) |
