14.1.3. Представление рельефа с мультиразрешением.

 

Мультиразрешение – представление с различной степенью детализации.

 

Основная задача:

Сортировка тачек по степени важности.

 

Данное представление можно использовать при изображении рельефа:

Разбиваем область на несколько зон. В ближних зонах используются триангуля- ция всех точек нулевого ранга(т.е. полное разрешение), далее используем триангуляцию точек за вычетом нулевого ранга, а на самом дольнем плане используем только самые важные точки. Причём, при приближении объекта точки добавляются, а при удалении объекта удаляется так же и часть точек(ненужных).

 

Наблюдатель в точке.

 

Показана триангуляция 0-го ранга

 

 

                                                                                              

 

 

Существует и такое понятие, как переменное мультиразрешение – один объект(рельеф), но представляется с различным разрешением в разных частях этого объекта.

 

Теперь рассмотрим такую задачу, как удаление точки из триангуляции. Это сделать достаточно сложно, но можно.

 

 

Допустим, хотим удалить следующую точку(на рис. помечена красным):

Для этого нужно:

“вырезать” эту точку,а образовавшуюся пустоту стриангулировать произвольным образом. Оставшиеся после удаления точки рёбра поместить в стек флипов, а затем профлиповать после чего пустота затянется.

Безусловно, сеществует несколько способов удаления точек, но самый эффективный это

Ранжирование точек.

 

Принцип по которому строится этот способ состоит в следующем:

В первую очередь удаляются точки, которые лежат в одной плоскости.

 

Наша задача – оценить важность точки, а значит наити ценность для каждой точки.

 

-нормированная нормаль для j-ой вершины;

 - соседние вершины (число соседних вершин m);

 - сама точка.

Функция нормировки:

 

Алгоритм ранжирования точек:

 

1) Построить триангуляцию полного разрешения, т.е. всех вершин. Присвоить   

     всем вершинам максимальный ранг;

2) Для каждой вершины посчитать среднюю нормаль(она считается один раз

    и является постоянной характеристикой вершины);

3) Для всех вершин рассчитать стоимость;

4) Установить текущий ранг = 0;

5) Удалить из триангуляции часть вершин, имеющих наименьшую стоимость.

     Пересчитать стоимость соседних вершин по отношению к удалённой.

     Присваиваем им текущий ранг;

6) Посчитать ошибку с данным рангом триангуляции, т.е. для каждой вершины

    (удалённой) посчитать расстояние по её триангуляции;

7) Увеличиваем текущий ранг на единицу;

8) Проверка текущего ранга(если текущий ранг не равен максимальному рангу,

    то возвращаемся к 5-му пункту.

 

Этот алгоритм можно усложнить. Например:

Оценивать ошибки удалённых вершин, а если, вершина была удалена неудачно,

то её возвращаем обратно.