Төртбұрышты марш: Имплицитті беттерді көрсету алгоритмі

Кіріспе

Маршыр тетраэдрлер — компьютерлік графика саласындағы имплициттік беттерді көрсету алгоритмі. Ол кейбір куб конфигурацияларындағы маршыр текшелер алгоритмінің шағын беймаздығын жояды. Алғаш рет 1991 жылы ұсынылған. Алғашқы маршыр текшелер алгоритмі бағдарламалық патентпен қорғалғандықтан, маршыр тетраэдрлер патенттік лицензия қажет етпейтін балама алгоритм ұсынды. Патент тіркелген күннен (1985 жылдың 5 маусымы) бері 20 жылдан астам өтті, сондықтан маршыр текшелер алгоритмін қазір еркін пайдалануға болады. Кейбір конфигурациялардағы аталған беймаздықты түзету үшін маршыр тетраэдрлердің шағын жақсартуларын қолдануға болады. Маршыр тетраэдрлерде әрбір куб үш рет екіге бөлініп, қарама-қарсы жақтарының әрбір үш жұбы арқылы диагональ бойынша кесіледі, нәтижесінде алты ретсіз тетраэдр пайда болады. Осылайша, тетраэдрлердің барлығы кубтың бір негізгі диагоналін бөліседі. Кубтың он екі қырының орнына енді он тоғыз қырымыз бар: бастапқы он екі, алты жақ диагоналі және бір негізгі диагональ. Маршыр текшелердегідей, осы қырлардың изожағымен қиылысуы тор нүктелеріндегі мәндерді сызықтық интерполяциялау арқылы жуықталады. Жақын орналасқан кубтар жалғасқан жақтағы барлық қырларды, соның ішінде бірдей диагональды бөліседі. Бұл көрсетілген бетте жарықтардың пайда болуын болдырмау үшін маңызды қасиет, себебі жақтың екі бөлек диагоналінің интерполяциясы көбінесе сәл өзгеше қиылысу нүктелерін береді. Қосымша артықшылығы – көрші кубты өңдегенде есептелген қиылысу нүктелерінің беске дейін қайта қолданылуы мүмкін. Бұған қиылысу нүктелеріндегі есептелген беттік нормальдар және басқа графикалық атрибуттар кіреді. Әр тетраэдрдің он алты мүмкін конфигурациясы бар, олар үш классқа бөлінеді: қиылысу жоқ, бір үшбұрышта қиылысу және екі (іргелес) үшбұрышта қиылысу. Барлық он алты конфигурацияны тізімдеп, оларды тиісті үшбұрышты жолақты анықтайтын төбе индекстерінің тізімдерімен сәйкестендіру оңай.

Marching tetrahedra is an algorithm in the field of computer graphics to render implicit surfaces. It clarifies a minor ambiguity problem of the marching cubes algorithm with some cube configurations. It was originally introduced in 1991. While the original marching cubes algorithm was protected by a software patent, marching tetrahedrons offered an alternative algorithm that did not require a patent license. More than 20 years have passed from the patent filing date (June 5, 1985), and the marching cubes algorithm can now be used freely. Optionally, the minor improvements of marching tetrahedrons may be used to correct the aforementioned ambiguity in some configurations. In marching tetrahedra, each cube is split into six irregular tetrahedra by cutting the cube in half three times, cutting diagonally through each of the three pairs of opposing faces. In this way, the tetrahedra all share one of the main diagonals of the cube. Instead of the twelve edges of the cube, we now have nineteen edges: the original twelve, six face diagonals, and the main diagonal. Just like in marching cubes, the intersections of these edges with the isosurface are approximated by linearly interpolating the values at the grid points. Adjacent cubes share all edges in the connecting face, including the same diagonal. This is an important property to prevent cracks in the rendered surface, because interpolation of the two distinct diagonals of a face usually gives slightly different intersection points. An added benefit is that up to five computed intersection points can be reused when handling the neighbor cube. This includes the computed surface normals and other graphics attributes at the intersection points. Each tetrahedron has sixteen possible configurations, falling into three classes: no intersection, intersection in one triangle and intersection in two (adjacent) triangles. It is straightforward to enumerate all sixteen configurations and map them to vertex index lists defining the appropriate triangle strips.

Жүргізуші текшелермен салыстыру

Жүргізуші тетраэдр бір кубқа он тоғыз қабырға қиылысын есептейді, ал жүргізуші кубқа тек он екі ғана қажет. Бұл қиылыстардың тек біреуі ғана жақын текшемен (негізгі диагональдағысымен) ортақ болмайды, бірақ кубтың барлық жақтарында ортақтасу алгоритмді күрделендіреді және жадқа қажетті көлемді едәуір арттырады. Алайда, қосымша қиылыстар сәл жақсырақ үлгілеу ажыратымдылығын қамтамасыз етеді. Көп қолданылатын анықтама кестелерінің мөлшерін анықтайтын конфигурациялар саны әлдеқайда аз, себебі тетраэдр үшін сегіз емес, тек төрт жеке төбелік қатысады. Бір кубтың орнына алты тетраэдрді өңдеу қажет. Процесс нақты, сондықтан қосымша беймаздықтарды жою қажет емес. Керісінше, тетраэдрлермен кубты бөлу тетраэдрлердің бағдарына қатысты таңдау жасауды талап етеді, бұл жақ диагональдары бойынша интерполяция нәтижесінде изожақ бетінде жасанды "дөңгелектерге" әкелуі мүмкін.

Алмаздық торлы жасуша - альтернативті текше кесу әдісі

Кубикалық жасушаларды торға түсіру үшін, негіз ретінде (алмаз кубикалық) торды пайдаланып, 5 тетраэдрге бөлуге болады. Кубтардың әр жағына, тетраэдрдің куб центріне қатысты кері бағытта орналасқан басқа кубтар жалғастырылады. Кезектесіп орналасқан төбелерде тетраэдрлердің қиылысу саны әртүрлі болады, нәтижесінде олардың орналасуына байланысты тордың құрылымы сәл өзгеше болады. Осылай кескенде қосымша симметрия жазықтықтары пайда болады; куб центрінде тетраэдрдің болуы, сондай-ақ, беттің сыртындағы нүктелердің айналасында кеңістіктердің ашылуына себеп болады. Алмаз кубиктің әртүрлі визуализациялары бар. Бос жасушалардың орнына, әр жасуша кезектесіп ішкі тетраэдрлермен толтырылуы керек. Кубқа ішкі жазылған әр тетраэдр үшін, кубтың төбелерін және оның беттерін қиып өтетін қабырғаларын пайдаланып, тетраэдр 4 нүктеге ие болады; қалған 4 нүкте кері тетраэдрдің төбелерін құрайды; куб жасушалары (x+y+z+) орны тақ болса, бірін пайдалану арқылы, әйтпесе керісінше орналастырылады; әйтпесе, жақын жасушалар қиылысуды есептеу үшін басқа диагональды қолданады. Кеңістіктік текстура жүйесіне негізделген түстің есептелуі, ағымдағы фрагмент позициясын пайдаланып, (x, y), (y, z) және (x, z) Texel (графика) координаттарының жұптарына негізделген қайталанатын текстурадан таңдау арқылы және осы мәндерді тиісінше нормальдің z, x және y компоненттерінің абсолюттік мәнімен көбейту арқылы жүзеге асырылады. Текстуралық декаль қолдану, текстуралық шашырату ретінде, декаль нормалы бағытындағы ағымдағы фрагмент позициясын бастапқы нүкте мен нормамен берілген текстура жазықтығына проекциялау арқылы, содан кейін текстура координатасын есептеу үшін "жоғары" немесе "оңға" бағыттау векторын қолдану арқылы жүзеге асырылуы мүмкін. Бұл техника Isosurface астында тізілген қос контурлаумен (dual contouring) салыстырылады, потенциалды әдіс ретінде. DCL тетраэдрлері, қос контурлау жасамайтын куб беттеріндегі диагональдар үшін қосымша есептеулерді қамтиды. Бұл әдіс сондай-ақ, екі жақын нүкте беттің "ішінде" болғанда және олардың арақашықтығы 1-ден кем болғанда, 1 нүктенің орнына жиектің бойында 2 нүкте тудыруы керек; осыған байланысты түзету – екі жақты контурлау (Manifold Dual Contouring).

The cubical cells to be meshed can also be sliced into 5 tetrahedra, using a (Diamond cubic) lattice as a basis. Cubes are mated on each side with another that has an opposite alignment of the tetrahedron around the centroid of the cube. Alternating vertices have a different number of tetrahedra intersecting on it, resulting in a slightly different mesh depending on position. When sliced this way, additional planes of symmetry are provided; having a tetrahedron around the centroid of the cube also generates very open spaces around points that are outside of the surface. Diamond cubic has a variety of visualizations. Instead of empty cells, every cell should be filled, with alternating inner tetrahedrons. For each tetrahedron inscribed in a cube, using the vertices of the cube and edges that cross the faces of the cube, the tetrahedron will occupy 4 points; the other 4 points form the corners of an inverted tetrahedron; the cubic cells are tiled such that the position of the cell (x+y+z+ ) is odd, use one, else use the inverted; otherwise near cells would use a different diagonal to compute the intersection. Calculation of color based on a spacial texture system can be done using the current fragment position to select from a repeating texture based on the pairs of Texel (graphics) coordinates (x,y), (y,z) and (x,z) and scaling those values by the absolute value of each respective component of the normal z, x, and y respectively. Texture decalling can be applied as Texture splatting by projecting the position of the current fragment in the direction of the decal' normal, to the plane of the texture given by an origin point and normal, then using a 'up' or 'right' directional vector to compute the texture coordinate. This technique would be more closely compared with dual contouring which is listed under Isosurface, as a potential technique. DCL tetrahedra involves additional calculations for the diagonals across cube faces, where dual contouring does not. This technique also has not addressed when two near points 'inside' a surface are a combined distance < 1 from the surface, where they should generate two points on the edge instead of 1; the related modification is Manifold Dual Contouring.