Сайт Информационных Технологий

АППРОКСИМАЦИЯ ПОВЕРХНОСТИ РЕЛЬЕФА

В.С. Иким

Санкт-Петербургский государственный электротехнический университет “ЛЭТИ” им. В.И.Ульянова (Ленина)

Abstract - The objective of this paper is the development and estimation of effectiveness recursive triangulating method of approximating terrain surface based on ranking of vertices, which allows to view surfaces of the terrain with discrete multiresolution.

Proposed method of terrain surface ranking vertex, permit classification of vertices and definition of their ranks in relation to other vertices. The rank of vertex corresponds to the degree of its influence on construction of approximating surfaces. The construction level-of-details by using ranking vertices come out to a step-by-step contraction of the least significant vertices.

He specific of our method is that there was developed a new criterion for estimating rank of vertices which use a linear regression and a new algorithm of dynamic removing vertices from a triangulation Делоне.

1. Ранжирование существенных ординат поверхности рельефа

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

Поверхность рельефа может быть задана в виде непрерывной функции высоты y=f(x, z) или в виде множества дискретных элементов аппроксимации. Определить точно функцию высот достаточно трудно, поэтому отдают предпочтение дискретным представлениям. Дискретно заданную поверхность рельефа для обеспечения ее эффективной обработки можно сохранять и обрабатывать как множество уровней разрешения, представляющее собой аппроксимирующие поверхности полного разрешения с определенной погрешностью. Под полным разрешением понимается поверхность рельефа с максимальным уровнем детализации, в которой присутствуют все исходные вершины, описывающие поверхность рельефа.

Ранжирование вершин поверхности рельефа должно обеспечивать определение их рангов по отношению к другим вершинам. Ранг вершины соответствует степени ее влияния на построение аппроксимирующей поверхности. Построение уровней разрешения путем ранжирования вершин сводится к постепенной отбраковке наименее важных вершин.

Чтобы ранжировать вершины поверхности рельефа, необходимо определить критерий сравнения, с помощью которого можно бы было вычислить приоритет любой вершины по отношению к другим оставшимся вершинам.

1.1 Разработка метода ранжирования вершин триангулированной поверхности

Особенность предлагаемого метода состоит в том, что используется собственный критерий оценки ранга вершин с помощью линейной регрессии и алгоритм динамического удаления вершин из триангуляции Делоне (ТД) [8].

C помощью линейной регрессии предлагается определить аппроксимирующую плоскость, соответствующую каждой вершине, путем минимизации суммы квадратов отклонений соседних вершин. Приближенно, аппроксимирующую плоскость можно определить через усреднение векторов нормалей всех прилегающих к вершине треугольников. В качестве критерия сравнения вершин предлагается использовать квадрат расстояния от вершины до соответствующей аппроксимирующей плоскости.

Значение критерия каждой вершины позволяет оценить погрешность аппроксимации в случае ее удаления. На рис.1 представлена блок-схема алгоритма ранжирования вершин, где - сортированный список вершин по критерию, которым еще не присвоен ранг.

Рис.1. Блок-схема метода ранжирования вершин.

На первом этапе необходимо определить критерий для всех вершин поверхности рельефа. Далее, пока список не пуст, извлекается вершина v с минимальным критерием, присваивается текущий ранг, удаляется вершина v из ТД и переопределяются критерии, соответствующие вершинам, которые участвовали в текущем изменении аппроксимации при удалении вершины. Для ограничения удаления граничных вершин предлагается определить критерий как расстояние от вершины до прямой, проходящей через соседние граничные вершины. Чем дольше вершина находится в списке , тем выше ее ранг.

1.2 Оценка погрешности аппроксимации

В качестве исходных данных для испытания и качественной и количественной оценки предложенного метода ранжирования взяты два типовых рельефа (гладкий - относительно менее сложная модель и волнистый - относительно более сложная модель).

Можно оценить визуально результат аппроксимации представленный на рис.2. Однако, чтобы получить более точное представление качества аппроксимаций, необходимо оценить погрешность аппроксимации. Для этого определяется погрешность аппроксимации по среднеквадратическому отклонению (СКО). Результаты аппроксимации разных рельефов необходимо нормировать.

В таблице 1.1 и на рис.3 представлена зависимость нормированного среднеквадратического отклонения по диапазону высот от нормированного количества вершин по количеству вершин аппроксимируемой поверхности. Критерий граничных вершин определяется расстоянием до прямой, проходящей через соседние вершины по контуру границы. Контур границы представляет собой ломаную линию, которая охватывает все оставшиеся вершины поверхности рельефа.

 

Рис.2 Результаты аппроксимации методом рекурсивного удаления вершин из триангуляции.

Таб. 1.1

Рельеф

10%

20%

30%

40%

50%

60%

70%

80%

90%

Гладкий

4,70%

2,70%

1,60%

1,20%

1,00%

0,80%

0,70%

0,50%

0,40%

Волнистый

9,20%

6,10%

4,10%

3,30%

2,80%

2,20%

1,80%

1,40%

0,90%

Рис.3 СКО от количества вершин

        1. 2. Заключение

Предложенный рекурсивный триангуляционный метод ранжирования практически решает проблему аппроксимации поверхности рельефа с минимальным количеством вершин с учетом заданной погрешности. Самостоятельное значение имеют предложения по аппроксимации границ рельефа.

Считаем, что данный подход и соответствуюшие методы ранжирования сущесвенны, когда производительность систем играет решающее значение.

Экспериментальное исследование и визуальное представление аппроксимированных рельефов дает возможность получения конкретных оценок, которые не противоречат полученным в работе результатам.

Литература

  1. Hoppe H. Progressive meshes. Computer Graphics (SIG-GRAPH ’96 Proceedings) (1996), 99–108.
  2. M. Soucy and D. Laurendeau. Multiresolution surface modeling based on hierarchical triangulation. Computer Vision and Image Understanding, 63(1):1-14,1996.
  3. C. L. Bajaj and D.R. Schikore. Error bounded reduction of tri
  4. angle meshes with multivariate data. SPIE, 2656:34-45, 1996.

  5. J. Cohen, A. Varshney, D. Manocha, G. Turk, H. Weber, P. Agarwal, F. Brooks, and W. Wright. Simplification envelopes. In Computer Graphics Proc., Annual Conf. Series (SIGGRAPH '96), ACM Press, pages 119-128, Aug. 6-8 1996.
  6. W.J. Schroeder. A topology modifying progressive decimation algorithm. In R. Yagel and H. Hagen, editors, Proceedings IEEE Visualization'97, pages 205-212, 1997.
  7. De Floriani L., Puppo E., Magillo P. Geometric structures and algorithms for geographic information systems //Technical Report DISI-TR-97-08.-Department of Computer and Information Sciences, University of Genova.-1997.
  8. M. Garland and P.S. Heckbert. Simplifying surfaces with color and normals with quadric error metrics. In Proceedings IEEE Visualization'98, pages263-269, Research Triangle Park, NC, 1998.
  9. L.P. Chew. Constrained Delaunay triangulations. Algorithmica, 4:97-108, 1989.

Site of Information Technologies
Designed by  inftech@webservis.ru.