Визуализация в научных исследованиях. Ечкина Е.Ю - 15 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

Е. Ю. Ечкина, С. Б. Базаров, И. Н. Иновенков «Визуализация в научных исследованиях»
Кафедра АНИ факультета ВМК МГУ имени М. В. Ломоносова http://ani.cs.msu.su
15
в любой точке среды проходит только одна линия тока. Поэтому нужно определить
правила, по которым можно быстро интерполировать векторное поле внутри ячейки,
то есть интерполировать две координатные компоненты.
Для нахождения линий тока векторного поля предлагается применить двумерный
аналог метода Фонга. Алгоритм нахождение линий тока базируется на билинейной
интерполяции вдоль отрезков прямой.
Описание алгоритма
Первый этап. Сначала происходит инициализация базовой точки на области
определения векторного поля, которая будет определять одну линию тока. Механизм
инициализации базовой точки может быть разный. Итак, пусть задана базовая точка
( , )
b b
x y
.
Второй этап. Нужно определить, какой ячейке сетки принадлежит базовая точка. На
этом этапе работают алгоритмы локализации точки. Время локализации точки зависит
от типа разностной сетки. Можно предложить два метода:
1. Последовательный полный перебор ячеек. Рассмотрим текущую
четырехугольную ячейку с индексами: (i, j), (i+1, j), (i+1, j+1), (i, j+1).
Вычисляется габаритный прямоугольник, описывающий ячейку. Если
базовая точка не принадлежит описывающему прямоугольнику, то базовая
точка не принадлежит ячейке, в противном случае, применяем следующий
способ. Поскольку узлы ячеек легко ориентировать по часовой стрелке или
против нее, то ребра можно рассматривать в виде векторов, относительно
которых можно определить положение базовой точки. Если для каждого
вектора базовая точка будет, в зависимости от ориентации, слева или
справа, то она принадлежит ячейке.
Рис 8. Текущая четырехугольная ячейка и габаритный описывающий прямоугольник.
2. В этом случае возможен полный перебор, только в худшем случае.
Рассматриваются горизонтальная
( )
b
y y
и вертикальная
b
x x
прямые,
которые пересекаются в базовой точке. Рассмотрим текущую четырехугольную
ячейку с индексами: (i, j), (i+1, j), (i+1, j+1), (i, j+1). Сначала рассматриваются
координаты абсцисс узлов ячейки. Если существуют узлы с координатами
1 2
,
x x
:
1 2
b
x x x
или
1 2
b
x x x
, то необходимо проверить факт
пересечения с вертикальной прямой. Если пересечения нет, то переходим к
следующей ячейке. Проверка факта пересечения с вертикальной прямой
аналогична проверке факта пересечения с горизонтальной, если ячейка же не
пересекает вертикальную прямую, то переходим к следующей ячейке. Если
b
y y
min
Y
( , )
b b
x y
( , )
i j
i j
( 1, 1)
i j
max
Y
min
X
b
x x
max
X
i j
Е. Ю. Ечкина, С. Б. Базаров, И. Н. Иновенков «Визуализация в научных исследованиях»


в любой точке среды проходит только одна линия тока. Поэтому нужно определить
правила, по которым можно быстро интерполировать векторное поле внутри ячейки,
то есть интерполировать две координатные компоненты.
Для нахождения линий тока векторного поля предлагается применить двумерный
аналог метода Фонга. Алгоритм нахождение линий тока базируется на билинейной
интерполяции вдоль отрезков прямой.

Описание алгоритма
Первый этап. Сначала происходит инициализация базовой точки на области
определения векторного поля, которая будет определять одну линию тока. Механизм
инициализации базовой точки может быть разный. Итак, пусть задана базовая точка
( xb , y b ) .
Второй этап. Нужно определить, какой ячейке сетки принадлежит базовая точка. На
этом этапе работают алгоритмы локализации точки. Время локализации точки зависит
от типа разностной сетки. Можно предложить два метода:
           1. Последовательный полный перебор ячеек. Рассмотрим текущую
               четырехугольную ячейку с индексами: (i, j), (i+1, j), (i+1, j+1), (i, j+1).
               Вычисляется габаритный прямоугольник, описывающий ячейку. Если
               базовая точка не принадлежит описывающему прямоугольнику, то базовая
               точка не принадлежит ячейке, в противном случае, применяем следующий
               способ. Поскольку узлы ячеек легко ориентировать по часовой стрелке или
               против нее, то ребра можно рассматривать в виде векторов, относительно
               которых можно определить положение базовой точки. Если для каждого
               вектора базовая точка будет, в зависимости от ориентации, слева или
               справа, то она принадлежит ячейке.

                                    (i, j  1)
      Ymax
                                                   (i  1, j  1)
                                    ( xb , y b )
   y  yb      (i , j )                              (i  1, j )
     Ymin

                          X min     x  xb         X max

Рис 8. Текущая четырехугольная ячейка и габаритный описывающий прямоугольник.

        2. В этом случае возможен полный перебор, только в худшем случае.
      Рассматриваются горизонтальная ( y  yb ) и вертикальная ( x  xb ) прямые,
      которые пересекаются в базовой точке. Рассмотрим текущую четырехугольную
      ячейку с индексами: (i, j), (i+1, j), (i+1, j+1), (i, j+1). Сначала рассматриваются
      координаты абсцисс узлов ячейки. Если существуют узлы с координатами
      x1 , x2 : x1  xb  x2 или x1  xb  x2 , то необходимо проверить факт
      пересечения с вертикальной прямой. Если пересечения нет, то переходим к
      следующей ячейке. Проверка факта пересечения с вертикальной прямой
      аналогична проверке факта пересечения с горизонтальной, если ячейка же не
      пересекает вертикальную прямую, то переходим к следующей ячейке. Если
Кафедра АНИ факультета ВМК МГУ имени М. В. Ломоносова http://ani.cs.msu.su             15

Страницы