Фактически, этот пост - продолжение этого.
Остановились мы на том, что построили тетраэдальную сетку из кубической. Следующая стадия - построить разбиение границы. Главная проблема в том, что разбиение границы должно быть согласованно с разбиением самой области - то есть, если у нас есть треугольник на границе, то этот треугольник полностью принадлежит одному из тетраэдров. Естественно есть множество способов сделать это. Простейший - берём прямоугольник разбиваем его на 4 треугольника (по 3 вершины разными способами), далее пробегаем по всем тетраэдрам и проверяем каждый тетраэдр на наличие этого треугольника. Проблема очевидна - на больших сетках это будет занимать гигантское количество времени.
Теперь если подумать о более рациональных способах, то можно сделать так: хранить отдельно параллелепипеды, находящиеся у границы сетки. Тогда сначала можно будет сделать разбиение внутренних, а затем внешних вместе с границей - тогда пробегать по тетраэдрам не придётся вообще(ну даже если придётся, то для каждого всего по 6 тетраэдрам, а не по всем, что есть - уже существенный плюс). Ну либо наоборот, порядок не важен.
Приведённые мой алгоритмы удобны в плане построения сеток для тестовых задач, либо для задач где надо сравнить решения на кубической и тетраэдальной сетки, однако построение "чисто" тераэдальной сетки даёт бóльшие возможности. С другой стороны это создаёт проблемы. Одна из главной проблема - это нормали. В вычислении нормалей проблем нет - векторное произведение сторон треугольника даст нам эту нормаль, главная проблема в определении ориентации нормали - её направления. Если с параллелепипедами всё просто - нормали для каждого параллелепипеда одинаковые(например, совпадают с координатными ортами), то для тетраэдров они могут быть направлены как угодно. И, если требуется ориентация нормали(что обычно так и есть), то надо для каждого тетраэдра разворачивать все нормали как надо, например, по направлению из тетраэдра, либо как-то хитро нумеровать сетку чтобы нормали расположились как надо. И то и другое требуют каких-никаких затрат.
Ещё один минус связан с размером тетраэдров в том или ином направлении(а возможно во всех сразу). Заключается в том, что при автоматическом построении сетки могут получаться очень маленькие тетраэдры. В зависимости от целей построения сетки это может не играть роли, а может быть минусом. Для графики, например, при аппроксимации некоторой модели тетраэдрами для отрисовки если маленький тетраэдр получается где-то внутри области, то это может не играть роли вообще. Для вычислительных задач это более важный критерий и может влиять на качество всего решения в целом.
Вещи, написанные мной в этих двух постах, в какой-то мере могут быть применены и к треугольным сеткам, для них алгоритмы будут формулироваться даже проще. Например, при построении из прямоугольной сетки треугольной разбиение границы остаётся тем же - перестраивать его не надо, да и само разбиение делается проще - по диагонали прямоугольника.
Остановились мы на том, что построили тетраэдальную сетку из кубической. Следующая стадия - построить разбиение границы. Главная проблема в том, что разбиение границы должно быть согласованно с разбиением самой области - то есть, если у нас есть треугольник на границе, то этот треугольник полностью принадлежит одному из тетраэдров. Естественно есть множество способов сделать это. Простейший - берём прямоугольник разбиваем его на 4 треугольника (по 3 вершины разными способами), далее пробегаем по всем тетраэдрам и проверяем каждый тетраэдр на наличие этого треугольника. Проблема очевидна - на больших сетках это будет занимать гигантское количество времени.
Теперь если подумать о более рациональных способах, то можно сделать так: хранить отдельно параллелепипеды, находящиеся у границы сетки. Тогда сначала можно будет сделать разбиение внутренних, а затем внешних вместе с границей - тогда пробегать по тетраэдрам не придётся вообще(ну даже если придётся, то для каждого всего по 6 тетраэдрам, а не по всем, что есть - уже существенный плюс). Ну либо наоборот, порядок не важен.
Приведённые мой алгоритмы удобны в плане построения сеток для тестовых задач, либо для задач где надо сравнить решения на кубической и тетраэдальной сетки, однако построение "чисто" тераэдальной сетки даёт бóльшие возможности. С другой стороны это создаёт проблемы. Одна из главной проблема - это нормали. В вычислении нормалей проблем нет - векторное произведение сторон треугольника даст нам эту нормаль, главная проблема в определении ориентации нормали - её направления. Если с параллелепипедами всё просто - нормали для каждого параллелепипеда одинаковые(например, совпадают с координатными ортами), то для тетраэдров они могут быть направлены как угодно. И, если требуется ориентация нормали(что обычно так и есть), то надо для каждого тетраэдра разворачивать все нормали как надо, например, по направлению из тетраэдра, либо как-то хитро нумеровать сетку чтобы нормали расположились как надо. И то и другое требуют каких-никаких затрат.
Ещё один минус связан с размером тетраэдров в том или ином направлении(а возможно во всех сразу). Заключается в том, что при автоматическом построении сетки могут получаться очень маленькие тетраэдры. В зависимости от целей построения сетки это может не играть роли, а может быть минусом. Для графики, например, при аппроксимации некоторой модели тетраэдрами для отрисовки если маленький тетраэдр получается где-то внутри области, то это может не играть роли вообще. Для вычислительных задач это более важный критерий и может влиять на качество всего решения в целом.
Вещи, написанные мной в этих двух постах, в какой-то мере могут быть применены и к треугольным сеткам, для них алгоритмы будут формулироваться даже проще. Например, при построении из прямоугольной сетки треугольной разбиение границы остаётся тем же - перестраивать его не надо, да и само разбиение делается проще - по диагонали прямоугольника.
