Перейти на главную   
  helloworld.ru - документация и книги по программированию  
helloworld.ru - документация и книги по программированию
    главная     хостинг    
Поиск по сайту:  
Смотрите также
Языки программирования
C#
MS Visual C++
Borland C++
C++ Builder
Visual Basic
Quick Basic
Turbo Pascal
Delphi
JavaScript
Java
PHP
Perl
Assembler
AutoLisp
Fortran
Python
1C

Интернет-технологии
HTML
VRML
HTTP
CGI
FTP
Proxy
DNS
протоколы TCP/IP
Apache

Web-дизайн
HTML
Дизайн
VRML
PhotoShop
Cookie
CGI
SSI
CSS
ASP
PHP
Perl

Программирование игр
DirectDraw
DirectSound
Direct3D
OpenGL
3D-графика
Графика под DOS

Алгоритмы
Численные методы
Обработка данных

Сис. программирование
Драйверы

Базы данных
MySQL
SQL

Другое

Хостинг


Друзья
demaker.ru
Реклама

Лучший хостинг. Аренда серверов




helloworld.ru





 в самое начало


demo.design
3D programming FAQ



РАЗНОЕ
7.4. Алгоритм "бегущих кубиков" для полигонизации изоповерхностей

Сооветствующий английский термин - marching cubes algorithm; приведен здесь, так сказать, just to avoid any confusion. Алгоритм предназначен для быстрого построения полигональной модели изоповерхности трехмерного скалярного поля, заданного значениями на равномерной сетке. Выражаясь менее академичным и, надеюсь, более понятным языком, этот алгоритм нужен для быстрого построения набора треугольных граней, достаточно хорошо приближающего изоповерхность, то есть такую поверхность, на которой определенная функция равна какой-то константе - изоуровню. Например, сфера радиуса 1 с центром в нуле - это изоповерхность функции f=1/(x*x+y*y+z*z) для изоуровня 1. Т.н. "3D капли", столь любимые ныне, тоже являются изоповерхностью, правда, немного более сложной функции (да, функция задана в трехмерном пространстве):

     n
f = sum c[i]/((x[i]-x)*(x[i]-x)+(y[i]-y)*(y[i]-y)+(z[i]-z)*(z[i]-z)),
    i=1

где

n

количество источников поля (капелек)

c[i]

интенсивность каждого источника (радиус капельки)

x[i], y[i], z[i]

координаты каждого источника (центра капельки)

Работает алгоритм следующим образом.

Рассматриваем какой-то параллелипипед, внутри которого заведомо находится изоповерхность (или та ее часть, которую мы хотим нарисовать). Разбиваем его сеткой, ну, как бы разрезаем его на несколько меньших параллелипипедов, и считаем значения функции (поля) в узлах сетки, то есть вершинах этих самых маленьких параллелипипедов. Для большей ясности можно заменить длинное слово "параллелипипед" на слово "куб" и представить себе кубик Рубика. Теперь проходим по всем кубикам (дальше я буду везде использовать слово "кубик", надоело "параллелипипед" писать). Смотрим на значения функции в вершинах кубика. Если все они больше (или меньше) изоуровня - значит, кубик находится целиком над (или под) изоповерхностью, внутри этого кубика поверхности нет и мы его просто отбрасываем. Если же часть больше, а часть меньше, то некоторые ребра кубика пересекаются с изоповерхностью. Линейной интерполяцией приближаем эти точки пересечения и в зависимости от того, какие вершины находятся над изоповерхностью, а какие под, генерируем несколько треугольных граней. Все вершины этих граней - это как раз точки пересечения поверхности с ребрами. Как генерировать грани и пересечения каких ребер с поверхностью считать, смотрим по таблице, это зависит лишь от того, какие вершины находятся над поверхностью, а какие - под. Вершин восемь, состояний два - над и под. Это дает нам 256 возможных расположений, так что таблица не такая уж и большая. Индекс в таблице тоже генерируется совсем просто: если вершина находится над поверхностью, устанавливаем соответствующий этой вершине бит индекса, иначе - сбрасываем.

Вот простенький пример.

рисунок (illu/illu74a.gif)

Пусть точка 6 находится под поверхностью, остальные - над. Тогда поверхность проходит через точки (*), приближаем их линейной интерполяцией и проводим через них треугольную грань. Какие ребра пересекаются с поверхностью, какие точки пересечния и как соединять - узнаем из таблиц по индексу; в данном случае индекс равен 11011111b=0DFh (установлены все биты, кроме 6го).

Алгоритм по шагам:

  • посчитать значения функции в узлах сетки (вершинах кубиков)

  • для каждого кубика:

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

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

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

Неоднократно упоминавшиеся магические таблицы приведены в примерчике, там же приведен кусок кода, который довольно легко переделть под свой engine. Пример взят с http://www.mhri.edu.au/~pdb/modelling/polygonise, сам по себе он компилироваться НЕ будет, но все там написано правильно и никаких ошибок в таблицах нет (так что ищите ошибку в своем коде).



 в самое начало


demo.design
3D programming FAQ














helloworld.ru © 2001-2021
Все права защищены
Rambler's Top100