ИСТИНА

При численном моделировании физических процессов методами механики сплошной среды широко используются геометрические расчетные сетки. Вопрос их построения в трёхмерных областях сложной формы, заданных поверхностными триангуляциями, является, на сегодняшний день, одним из наиболее сложных и затратных, с вычислительной точки зрения. В настоящее время известно несколько подходов к построению тетраэдральных сеток, в том числе методы граничной коррекции, методы исчерпывания, а так же алгоритмы на основе критерия Делоне [1-3]. Однако, эти алгоритмы не позволяют добиться гарантированного построения сетки для произвольной области за априорно оцениваемое время. Рассматриваемый в работе алгоритм отличается от упомянутых выше. К особенностям рассматриваемого алгоритма относятся: зависимость числа операций только от сложности поверхности, что делает возможным априорную оценку времени работы с хорошей точностью, и гарантированность построения трёхмерной триангуляции на множестве вершин, координаты которых являются рациональными числами ограниченной разрядности. Алгоритм отличается высокой степенью внутреннего параллелизма. Основным недостатком рассматриваемого алгоритма является низкое с точки зрения дальнейших вычислений качество генерируемой сетки. В рамках работы рассматривается параллельная программная реализация алгоритма ортогонального проецирования относительно оси OZ, а так же используемые для реализации алгоритмы. Структурно алгоритм генерации сетки состоит из трёх частей: проецирования и формирования призм, согласования граней и рёбер призм, и построение триангуляций для граней призм. Задача согласования всех построенных призм сводиться к задаче построения наборов вершин и рёбер, попавших на каждую грань. Использование арифметики рациональных чисел создаёт дополнительные сложности при передаче данных между процессорами. Рассмотрено несколько вариантов алгоритма построения боковых стенок призм, реализован как последовательный, так и параллельный алгоритма. Изучен вопрос эффективности использования алгоритма раскраски графа для обеспечения построения согласованной триангуляции общих граней соприкасающихся призм. Альтернативой этому алгоритму является реализация полностью детерминированного алгоритма двумерной триангуляции. Использование такого подхода удваивает объём работ по построению двумерной триангуляции граней, но позволяет избавиться от передачи данных на этом этапе. В результате был выбран второй подход, позволяющий не использовать обмены между процессорами во время триангуляции боковых граней, до момента формирования конечного результата, что даёт дополнительный ресурс масштабируемости.