Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік графикалық алгоритм
Computer graphics algorithm
Маршингтік кубтар – 1987 жылы Лоренсен мен Клайнның SIGGRAPH материалдарында жарияланған, үш өлшемді дискретті скалярлық өрістен (элементтері кейде воксельдер деп аталады) изожағын көпбұрышты торға түрлендіруге арналған компьютерлік графикалық алгоритм. Бұл алгоритмнің қолданылуы көбінесе медициналық визуализация, мысалы, КТ және МРТ сканерлеу деректерінің бейнелері, сондай-ақ арнайы эффектілер немесе әдетте метаболдар немесе басқа метабеттер деп аталатын 3D модельдеу салаларында болады. Маршингтік кубтар алгоритмі 3D үшін жасалған, ал оның 2D нұсқасы маршингтік квадраттар алгоритмі деп аталады.
Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface from a three dimensional discrete scalar field (the elements of which are sometimes called voxels). The applications of this algorithm are mainly concerned with medical visualizations such as CT and MRI scan data images, and special effects or 3 D modelling with what is usually called metaballs or other metasurfaces. The marching cubes algorithm is meant to be used for 3 D; the 2 D version of this algorithm is called the marching squares algorithm.
Тарих
Алгоритмді Уильям Э. Лоренсен (1946–2019) және Харви Э. Клайн General Electric компаниясының зерттеулері нәтижесінде жасады. General Electric компаниясында олар компьютерлік томография және МРТ құрылғыларынан алынған деректерді тиімді визуализациялау жолын іздестірді. Алгоритмнің негізі – кіріс көлемін дискретті текшелер жиынтығына бөлу. Сызықтық реконструкциялық сүзгіні қолданғанда, әрбір текше, берілген изожағының бөлігін қамтитындықтан, оңай анықталады, себебі текше төбелеріндегі үлгілік мәндер мақсатты изожақ мәнін қамтуы тиіс. Изожақтың бір бөлігін қамтитын әрбір текше үшін, ішкі текшедегі трилинейлік интерполянттың мінез-құлқын шамалайтын үшбұрышты тор құрастырылады. Алгоритмнің алғашқы жарияланған нұсқасы айналу және көрістік симметрияны пайдаланды, сондай-ақ 15 бірегей жағдайдан тұратын кесте құру үшін өзгерістер енгізді. Дегенмен, текше беттеріндегі және ішіндегі трилинейлік интерполянттың мінез-құлқындағы белгісіздіктерге байланысты, Marching Cubes әдісімен құрастырылған торлар үздіксіздіктер мен топологиялық проблемаларды көрсетті. Тордың текшесін қарастыратын болсақ, беттік белгісіздік оның беттік төбелері кезектесіп, әртүрлі таңбаға ие болғанда пайда болады. Яғни, осы беттегі бір диагональдің төбелері оң, ал екіншісінің төбелері теріс болады. Байқаңыз, мұндай жағдайда беттік төбелердің таңбалары изожақты үшбұрыштаудың дұрыс тәсілін анықтау үшін жеткіліксіз. Сол сияқты, ішкі белгісіздік текше төбелерінің таңбалары дұрыс беттік үшбұрыштауды анықтау үшін жеткіліксіз болғанда, яғни бір текше конфигурациясы үшін бірнеше үшбұрыштау мүмкін болғанда пайда болады. Marching Cubes әдісінің танымалдылығы мен кеңінен қолданылуы алгоритмді жетілдіруге, белгісіздіктерді жоюға және интерполянттың мінез-құлқын дұрыс қадағалауға әкелді. 1988 жылы Дёрст Лоренсен мен Клайн ұсынған үшбұрышты кесте толық емес екенін және кейбір Marching Cubes жағдайлары бірнеше үшбұрыштауға мүмкіндік беретінін алғашқы болып атап өтті. Дёрсттің "қосымша сілтемесі" Вайвилл, Вайвилл және Макфитерстің бұрынғы, тиімді (де Араужоны қараңыз) изожақты көпбұрышқа түрлендіру алгоритміне қатысты. Кейін, 1991 жылы Нильсон мен Хаманн текше бетіндегі интерполянттың мінез-құлқындағы белгісіздіктердің бар екенін байқады. Олар асимптотикалық шешіш деп аталатын тест ұсынды, ол текше бетіндегі интерполянтты дұрыс қадағалайды. Натаражан 1994 жылы бұл белгісіздік мәселесі текшенің ішінде де пайда болатынын байқады. Автор өз жұмысында интерполянттың сындық нүктелеріне негізделген белгісіздікті жою тестін ұсынды және Marching Cubes үшбұрыштау кестесіне төрт жаңа жағдай қосты (3, 4, 6 және 7 жағдайлардың кіші жағдайлары). Бұл кезде алгоритмге және оның үшбұрышты кестесіне енгізілген барлық жақсартуларға қарамастан, Marching Cubes әдісімен құрастырылған торлар әлі де топологиялық сәйкессіздіктерге ие болды. 1995 жылы Черняев ұсынған Marching Cubes 33 трилинейлік интерполянттың топологиясын сақтауға бағытталған алғашқы изожақты алу алгоритмдерінің бірі болып табылады. Өз жұмысында Черняев үшбұрышты іздеу кестесіндегі жағдайлар санын 33-ке дейін арттырды. Содан кейін ол ішкі белгісіздіктерді шешудің басқа тәсілін ұсынды, ол асимптотикалық шешішке негізделген. Кейін, 2003 жылы Нильсон Черняевтің іздеу кестесі толық екенін және трилинейлік интерполянттың барлық мүмкін мінез-құлқын көрсете алатынын дәлелдеді, ал Левинер және басқалар алгоритмді іске асыруды ұсынды. Сондай-ақ 2003 жылы Лопес пен Бродли Натаражан ұсынған тесттерді кеңейтті, Черняев ұсынған Marching Cubes 33 алгоритмімен құрастырылған тордың топологиялық дұрыстығына зиян келтіретін алгоритмдік қателіктерді анықтап, түзетті.
The algorithm was developed by William E. Lorensen (1946 2019) and Harvey E. Cline as a result of their research for General Electric. At General Electric they worked on a way to efficiently visualize data from CT and MRI devices. The premise of the algorithm is to divide the input volume into a discrete set of cubes. By assuming linear reconstruction filtering, each cube, which contains a piece of a given isosurface, can easily be identified because the sample values at the cube vertices must span the target isosurface value. For each cube containing a section of the isosurface, a triangular mesh that approximates the behavior of the trilinear interpolant in the interior cube is generated. The first published version of the algorithm exploited rotational and reflective symmetry and also sign changes to build the table with 15 unique cases. However, due to the existence of ambiguities in the trilinear interpolant behavior in the cube faces and interior, the meshes extracted by the Marching Cubes presented discontinuities and topological issues. Given a cube of the grid, a face ambiguity occurs when its face vertices have alternating signs. That is, the vertices of one diagonal on this face are positive and the vertices on the other are negative. Observe that in this case, the signs of the face vertices are insufficient to determine the correct way to triangulate the isosurface. Similarly, an interior ambiguity occurs when the signs of the cube vertices are insufficient to determine the correct surface triangulation, i. e., when multiple triangulations are possible for the same cube configuration. The popularity of the Marching Cubes and its widespread adoption resulted in several improvements in the algorithm to deal with the ambiguities and to correctly track the behavior of the interpolant. Durst in 1988 was the first to note that the triangulation table proposed by Lorensen and Cline was incomplete, and that certain Marching Cubes cases allow multiple triangulations. Durst's 'additional reference' was to an earlier, more efficient (see de Araujo) isosurface polygonization algorithm by Wyvill, Wyvill and McPheeters. Later, Nielson and Hamann in 1991 observed the existence of ambiguities in the interpolant behavior on the face of the cube. They proposed a test called Asymptotic Decider to correctly track the interpolant on the faces of the cube. In fact, as observed by Natarajan in 1994, this ambiguity problem also occurs inside the cube. In his work, the author proposed a disambiguation test based on the interpolant critical points, and added four new cases to the Marching Cubes triangulation table (subcases of the cases 3, 4, 6 and 7). At this point, even with all the improvements proposed to the algorithm and its triangulation table, the meshes generated by the Marching Cubes still had topological incoherencies. The Marching Cubes 33, proposed by Chernyaev in 1995, is one of the first isosurface extraction algorithms intended to preserve the topology of the trilinear interpolant. In his work, Chernyaev extends to 33 the number of cases in the triangulation lookup table. He then proposes a different approach to solve the interior ambiguities, which is based on the Asymptotic Decider. Later, in 2003, Nielson proved that Chernyaev's lookup table is complete and can represent all the possible behaviors of the trilinear interpolant, and Lewiner et al. proposed an implementation to the algorithm. Also in 2003 Lopes and Brodlie extended the tests proposed by Natarajan. noted and corrected algorithmic inaccuracies that compromised the topological correctness of the mesh generated by the Marching Cubes 33 algorithm proposed by Chernyaev.
Алгоритм
Алгоритм скалярлық өріс бойынша сегіз көршілес нүктені бірден қарастырады (осылайша көзге көрінбейтін куб құрайды), содан кейін осы куб арқылы өтетін изожағының бөлігін бейнелеуге қажетті көпбұрыштарды анықтайды. Жеке көпбұрыштар кейін қажетті бетке біріктіріледі. Бұл куб ішіндегі 256 мүмкін көпбұрыш конфигурациясының (2⁸=256) алдын ала есептелген массивіне индекс жасау арқылы іске асырылады, мұнда әрбір 8 скалярлық мән 8 биттік бүтін санның биті ретінде қарастырылады. Егер скалярлық мән изомәнінен жоғары болса (яғни, беттің ішінде болса), тиісті бит 1-ге қойылады, ал егер төмен болса (сыртында), 0-ге қойылады. Барлық сегіз скаляр тексерілгеннен кейін алынған соңғы мән – көпбұрыш индекстер массивінің нақты индексі болады. Соңында, құрылған көпбұрыштардың әрбір төбесі кубтың қабырғасы бойымен тиісті орналасқан жерге, сол қабырғамен байланысты екі скалярлық мәнді сызықтық интерполяциялау арқылы орналастырылады. Скалярлық өрістің әрбір тор нүктесіндегі градиенті сол нүкте арқылы өтетін гипотетикалық изожақтың нормальдық векторы болып табылады. Сондықтан, осы нормальдарды әрбір кубтың қабырғалары бойынша интерполяциялау арқылы, алынған торды жарықтандыру моделімен көлеңдеу үшін қажетті төбелердің нормальдарын табуға болады.
The algorithm proceeds through the scalar field, taking eight neighbor locations at a time (thus forming an imaginary cube), then determining the polygon(s) needed to represent the part of the isosurface that passes through this cube. The individual polygons are then fused into the desired surface. This is done by creating an index to a precalculated array of 256 possible polygon configurations (28=256) within the cube, by treating each of the 8 scalar values as a bit in an 8 bit integer. If the scalar's value is higher than the iso value (i. e., it is inside the surface) then the appropriate bit is set to one, while if it is lower (outside), it is set to zero. The final value, after all eight scalars are checked, is the actual index to the polygon indices array. Finally each vertex of the generated polygons is placed on the appropriate position along the cube's edge by linearly interpolating the two scalar values that are connected by that edge. The gradient of the scalar field at each grid point is also the normal vector of a hypothetical isosurface passing from that point. Therefore, these normals may be interpolated along the edges of each cube to find the normals of the generated vertices which are essential for shading the resulting mesh with some illumination model.
Патент мәселелері
Маршылдаған кубтар алгоритмінің іске асырылуы АҚШ патенті 4,710,876 ретінде тіркелген. Патенттің қамқорлығын айналып өту және кейбір куб конфигурацияларында маршылдаған кубтардың туындайтын шағын екіұштылық мәселесін шешу мақсатында маршылдаған тетраэдр деп аталатын тағы бір ұқсас алгоритм әзірленді. Патент 2005 жылы қолданыстан шықты және одан бері 20 жылдан астам уақыт өткендіктен (1 желтоқсан 1987 ж.), графикалық қоғамдастық оны роялти төлеместен заңды түрде пайдалануға құқылы.
An implementation of the marching cubes algorithm was patented as United States Patent 4,710,876. Another similar algorithm was developed, called marching tetrahedra, in order to circumvent the patent as well as solve a minor ambiguity problem of marching cubes with some cube configurations. The patent expired in 2005, and it is now legal for the graphics community to use it without royalties since more than the 20 years have passed from its issue date (December 1, 1987).