Patent ID: 8269762
Filing Date: 2012-09-18
Classification: G06T

Abstract:
1. In a computing environment, a computer implemented method of triangulating quadrilaterals, the method comprising: accessing an irregular grid comprising a plurality of irregular quadrilaterals; determining that each of the irregular quadrilaterals in the irregular grid is a convex quadrilateral; on a grid basis and as a result of determining that each of the irregular quadrilaterals in the irregular grid is a convex quadrilateral, triangulating each of the irregular quadrilaterals in the irregular grid to create a triangular mesh by defining diagonals from at least one vertex point of each of the irregular quadrilaterals in the irregular grid to the diagonally opposed vertex point of the same irregular quadrilateral; storing the triangular mesh in a computer readable storage medium that can be accessed by an application for at least one of data visualization, computer graphics, or computational geometry; and wherein each of the irregular quadrilaterals in the irregular grid corresponds to a quadrilateral in a regular grid such that vertex points in a given irregular quadrilateral among the plurality of irregular quadrilaterals corresponds to vertex points of a given quadrilateral in the regular grid, the regular grid corresponding to the irregular grid, wherein at least some vertex points in the irregular grid are displaced some distance from corresponding vertex points in the regular grid, and wherein determining that each of the irregular quadrilaterals in the irregular grid is a convex quadrilateral comprises determining that each vertex point in the irregular grid is displaced from the corresponding vertex point of the corresponding quadrilateral in the regular grid by being placed within the boundaries of an ellipse centered about the corresponding vertex points in the regular grid.