EducationBot: Новая страница: «{{Русская Википедия/Панель перехода}} Файл:Marchingcubes-head.png|thumb|300px|Модель, построенная из 150 слоев с МРТ с использованием алгоритма marching cubes. Под поверхностью находятся около 150 000 полигонов и скрытых объектов. Размер сетки составляет 64 × 64 × 150 [[...»

2023-07-15T21:21:38Z

Новая страница: «{{Русская Википедия/Панель перехода}} Файл:Marchingcubes-head.png|thumb|300px|Модель, построенная из 150 слоев с МРТ с использованием алгоритма marching cubes. Под поверхностью находятся около 150 000 полигонов и скрытых объектов. Размер сетки составляет 64 × 64 × 150 [[...»

Новая страница

{{Русская Википедия/Панель перехода}}
[[Файл:Marchingcubes-head.png|thumb|300px|Модель, построенная из 150 слоев с МРТ с использованием алгоритма marching cubes. Под поверхностью находятся около 150 000 полигонов и скрытых объектов. Размер сетки составляет 64 × 64 × 150 [[воксел]]ей, кодированных 8-ю битами. Для сглаживания поверхности модели был применён [[пре-процессинг]]. «Дырка» в области [[Висок|виска]] является следствием [[пирсинг]]а обследуемого.]]

'''Marching cubes''' ({{tr-en|шагающие кубики}}) — [[алгоритм]] в [[Компьютерная графика|компьютерной графике]], впервые предложенный в [[1987 год]]у на конференции [[SIGGRAPH]]
Вильямом Лоренсеном 
и Харви Клайном<ref name="Originalpaper">William E. Lorensen, Harvey E. Cline: ''Marching Cubes: A high resolution 3D surface construction algorithm.'' In: ''Computer Graphics'', Vol. 21, Nr. 4, July 1987</ref>, для обработки полигональной сетки [[Скалярное поле#Поверхность уровня|изоповерхности]] трехмерного [[Скалярное поле|скалярного поля]] (чаще называемой сеткой [[воксел]]ей).

Аналогичный алгоритм на плоскости называется [[marching squares]].

== Принцип работы ==
Алгоритм пробегает скалярное поле, на каждой итерации просматривает 8 соседних позиций (вершины [[куб]]а, параллельного осям координат) и определяет [[Полигональная сетка|полигоны]], необходимые для представления части изоповерхности, проходящей через данный куб. Далее, на экран выводятся полигоны, образующие заданную изоповерхность.

Так как алгоритм выбирает полигоны, исходя только из положения вершин куба относительно изоповерхности, всего получается 256 (<math>2^8 = 256</math>) возможных конфигураций полигонов, которые можно вычислить заранее и сохранить в массиве. Поэтому каждый куб можно представить восьмибитным числом, сопоставив каждой вершине 1, если значение поля в точке больше, чем на изоповерхности, и 0 в противном случае. Полученное число используется в качестве индекса элемента массива, хранящего конфигурации полигонов.
Наконец, каждая вершина сгенерированного полигона помещается в подходящую позицию на том ребре куба, на котором она лежала изначально. Позиция вычисляется путём линейной интерполяции значений скалярного поля в концах ребра.
[[Файл:MarchingCubes.svg|thumb|right|350px|15 различных конфигураций куба.]]
Заранее вычисленный массив из 256 конфигураций полигонов можно получить поворотами и отражениями 15 различных конфигураций куба. Однако использование всего 15 базовых конфигураций не гарантирует получение замкнутой поверхности. Базовые конфигурации, лишенные этого недостатка, можно найти в специальной литературе{{Нет АИ|9|12|2013}}.

[[Градиент]] скалярного поля в каждой точке сетки также является нормальным вектором к предполагаемой изоповерхности, проходящей через эту точку. Поэтому возможно [[Линейная интерполяция|интерполировать]] эти нормали вдоль рёбер каждого куба, чтобы найти нормали сгенерированных вершин, для корректного отображения модели при использовании освещения.

Данный алгоритм широко используется в медицине, например, в [[Компьютерная томография|компьютерной]] и [[Магнитно-резонансная томография|магнитно-резонансной томографии]], а также для трёхмерного моделирования [[Metaballs|метасфер]] или других метаповерхностей.

== Патент ==
Алгоритм '''The Marching Cubes''' был первым примером в области компьютерной графики, спровоцировавшим скандал в области [[Патент на программное обеспечение|патентования ПО]]. Он был запатентован несмотря на относительную очевидность решения задачи генерации поверхности. Позднее был разработан похожий алгоритм, названный [[:en:Marching_tetrahedra|marching tetrahedrons]], который для того, чтобы обойти патент, использует вместо кубов тетраэдры. Срок действия патента истек в 2005 году, сейчас алгоритм можно свободно использовать. (Патент от 5 июня 1985 года<ref>{{US patent|4710876|Marching Cubes, US Patent Office entry}}</ref>).

== Примечания ==
{{Примечания}}

== См. также ==
* [[Image-based meshing]]

== Внешние ссылки ==
* [https://web.archive.org/web/20100310122316/http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/ Overview and source code by Paul Bourke]
* [https://web.archive.org/web/20100107113848/http://www.gamedev.net/reference/articles/article424.asp GameDev overview] by Matthew Ward of Worcester Polytechnic Institute
* [http://users.polytech.unice.fr/~lingrand/MarchingCubes/algo.html Introductory description with additional graphics]
* [http://www.marchingcubes.org/index.php/Marching_Cubes Some of the early history of Marching Cubes] {{Wayback|url=http://www.marchingcubes.org/index.php/Marching_Cubes |date=20190527115005 }}

[[Категория:Геометрические алгоритмы]]
[[Категория:Трёхмерная графика]]
[[Категория:Воксельная графика]]
{{Навигационная таблица/Портал/Русская Википедия}}
[[Категория:Русская Википедия]]
[[Категория:Википедия]]
[[Категория:Статья из Википедии]]
[[Категория:Статья из Русской Википедии]]

Русская Википедия:Marching cubes - История изменений