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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

Е. Ю. Ечкина, С. Б. Базаров, И. Н. Иновенков «Визуализация в научных исследованиях»
Кафедра АНИ факультета ВМК МГУ имени М. В. Ломоносова http://ani.cs.msu.su
11
проблемы, связанные с аппроксимацией искомой поверхности в ячейке. Если размер
ячейки будет очень большим, то возможна большая потеря точности.
Рис.2. На схеме квадрат обозначает ячейку, овал - некий изгиб искомой поверхности.
Как видно из рис.2, при большом размере ячейки некоторые части искомой
поверхности просто не будут видны. Однако выбирать ячейки очень маленького
размера не очень хорошо с точки зрения быстродействия метода. Поэтому размер
ячейки надо выбирать не меньше допустимой погрешности построения искомой
поверхности.
Форма ячейки в алгоритме «Марширующих кубов» - параллелепипед. Однако это не
единственно возможный вариант. Форма ячейки определяет дальнейшую
триангуляцию ячейки. Пусть форма ячейки - многогранник с N вершинами, тогда
сопоставим каждой ячейке N-битовый индекс, а каждой вершине - один бит в индексе.
Причем, если вершина ячейки находится вне объема ограниченного искомой
поверхностью, то значение этого бита <0>, иначе <1>. Тогда количество разных типов
триангуляции будет 2
N
. Отсюда видно, что использовать в качестве ячейки, например,
икосаэдр не оптимально. Многогранник с наименьшим количеством вершин -
треугольная пирамида. Именно она используется в качестве ячейки в алгоритмах
Канейро, Скалы.
Итак, допустим, что область G уже разбита на ячейки. Тогда главной проблемой
становится поиск ячеек пересекаемых искомой поверхностью. Пусть С - множество
ячеек, тогда C
v
- множество ячеек, пересекаемых поверхностью F(P)=v. Тогда можно
считать, что поверхность пересекает ячейку, если существуют такие P
1
и P
2
- вершины
ячейки, что
1 2
( ) ( )
F p F p
(*)
Это условие выполняется, если справедливо неравенство
( ) ( )
i j
i j
(**)
где p
i
и p
j
- вершины ячейки.
Таким образом, проблема свелась к следующему: из множества ячеек C выбрать
подмножество ячеек C
v
, удовлетворяющих условию (**).
Рассмотрим далее проблему аппроксимации поверхности в ячейке.
Второй этап
Как уже было сказано, пространство разбивается на ячейки, и отбираются только те
ячейки, в которых надо производить аппроксимацию. Таким образом, задачей второго
этапа является аппроксимация поверхности в одной ячейке. Наиболее оптимальный
способ аппроксимации - триангуляция. Посчитаем, сколько способов триангуляции
имеет параллелепипед. Пусть имеется 8-битовый индекс. Тогда сопоставим каждой
вершине один бит в индексе. Причем, если вершина ячейки находится вне объема
ограниченного искомой поверхностью, то значение этого бита <0>, иначе <1>. Тогда
количество разных типов триангуляции будет 2
8
=256. Однако из рис.3 видно, что 
Е. Ю. Ечкина, С. Б. Базаров, И. Н. Иновенков «Визуализация в научных исследованиях»


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




Рис.2. На схеме квадрат обозначает ячейку, овал - некий изгиб искомой поверхности.

Как видно из рис.2, при большом размере ячейки некоторые части искомой
поверхности просто не будут видны. Однако выбирать ячейки очень маленького
размера не очень хорошо с точки зрения быстродействия метода. Поэтому размер
ячейки надо выбирать не меньше допустимой погрешности построения искомой
поверхности.
Форма ячейки в алгоритме «Марширующих кубов» - параллелепипед. Однако это не
единственно возможный вариант. Форма ячейки определяет дальнейшую
триангуляцию ячейки. Пусть форма ячейки - многогранник с N вершинами, тогда
сопоставим каждой ячейке N-битовый индекс, а каждой вершине - один бит в индексе.
Причем, если вершина ячейки находится вне объема ограниченного искомой
поверхностью, то значение этого бита <0>, иначе <1>. Тогда количество разных типов
триангуляции будет 2N. Отсюда видно, что использовать в качестве ячейки, например,
икосаэдр не оптимально. Многогранник с наименьшим количеством вершин -
треугольная пирамида. Именно она используется в качестве ячейки в алгоритмах
Канейро, Скалы.
Итак, допустим, что область G уже разбита на ячейки. Тогда главной проблемой
становится поиск ячеек пересекаемых искомой поверхностью. Пусть С - множество
ячеек, тогда Cv - множество ячеек, пересекаемых поверхностью F(P)=v. Тогда можно
считать, что поверхность пересекает ячейку, если существуют такие P1 и P2 - вершины
ячейки, что
F ( p1 )    F ( p2 ) (*)
Это условие выполняется, если справедливо неравенство
MinF ( pi )    MaxF ( p j ) (**)
  i                    j

где pi и pj - вершины ячейки.
Таким образом, проблема свелась к следующему: из множества ячеек C выбрать
подмножество ячеек Cv, удовлетворяющих условию (**).
Рассмотрим далее проблему аппроксимации поверхности в ячейке.

Второй этап

Как уже было сказано, пространство разбивается на ячейки, и отбираются только те
ячейки, в которых надо производить аппроксимацию. Таким образом, задачей второго
этапа является аппроксимация поверхности в одной ячейке. Наиболее оптимальный
способ аппроксимации - триангуляция. Посчитаем, сколько способов триангуляции
имеет параллелепипед. Пусть имеется 8-битовый индекс. Тогда сопоставим каждой
вершине один бит в индексе. Причем, если вершина ячейки находится вне объема
ограниченного искомой поверхностью, то значение этого бита <0>, иначе <1>. Тогда
количество разных типов триангуляции будет 28=256. Однако из рис.3 видно, что

Кафедра АНИ факультета ВМК МГУ имени М. В. Ломоносова http://ani.cs.msu.su            11

Страницы