РАЗНОЕ
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 возможных расположений, так что таблица не такая уж и большая. Индекс в таблице тоже генерируется совсем просто: если вершина находится над поверхностью, устанавливаем соответствующий этой вершине бит индекса, иначе - сбрасываем.

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

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

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

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

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

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

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

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

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