M.V. Zagvozdkin, D.V. Filippov

The goal of the present work was to develop an algorithm of initial triangulation with specified forms of surfaces jointly describing material objects in the context of external and internal electrodynamic problems solving. Developed algorithm is based on decomposition of a complex object into a set of geometric primitives (parallelepipeds, spheres, pyramids, cylinders etc) which approximate an object form with certain precision. Each of primitives in its turn is represented by composition of base elements of one class. It was shown that it is practical to choose a base element type from convex polygons class. A special problem was stated in the context of decomposition problem: to substantiate a form of base element (it is called "simplex" in literature) which should represent peculiarity of space form of objects in most accurate way. Studying literature on numerical methods for solving electrodynamic problems as well as up-to-date graphics chipsets characteristics analysis has shown that it is most practical to use triangle for simplex. Thus, as a method for aggregative surface discretization, triangulation method was chosen by the authors. In a general case, triangulation problem is reduced to resolving of two particular problems: - generation of set of points (vertices) characterizing a space form of an object - initial decomposition of an object surface into triangles - improving of initial mesh quality (using Delaunay criteria for example) A variant of initial surface decomposition algorithm for given set of vertices was proposed by authors. This algorithm consists of three steps. At the first step a first rib is determined on a given set of boundary points. At the second step an adjacent point for a current rib is determined. At the third step an adjacent point, if it was found, a new triangle formed by it and also by two points of a current rib is added to a triangles list; also two new ribs formed by two points of a current rib and an adjacent point are added to a ribs list. Then a current rib is deleted and algorithm finishes its work if a ribs list is empty. Obtained results of the initial triangulation algorithm work may be used as a base data for a final triangulation accomplishment on a stage of initial mesh quality improvement.