Dělicí povrch - Subdivision surface

V oblasti 3D počítačová grafika, a dělící povrch je metoda představující hladký povrch přes specifikaci hrubšího mnohoúhelníková síť. Hladký povrch lze vypočítat z hrubé sítě jako omezit iteračního procesu dělení každé polygonální tvář do menších ploch, které lépe přibližují hladký povrch.

První tři kroky Catmull-Clark dělení krychle s dělící plochou dole

Přehled

Algoritmus dělení ploch je rekurzivní v přírodě. Proces začíná danou polygonální sítí. A Schéma zdokonalování se pak aplikuje na tuto síť. Tento proces vezme tuto síť a rozdělí ji a vytvoří nové vrcholy a nové plochy. Pozice nových vrcholů v síti se počítají na základě pozic blízkých starých vrcholů. V některých schématech upřesnění mohou být také změněny polohy starých vrcholů (pravděpodobně na základě pozic nových vrcholů).

Tento proces vytváří hustší síť než původní síť, která obsahuje více polygonálních ploch. Tuto výslednou síť lze znovu projít stejným schématem zdokonalení atd.

Mezní dělící povrch je povrch vytvořený tímto procesem, který je opakovaně aplikován nekonečně mnohokrát. V praxi se však tento algoritmus používá pouze omezený a obvykle poměrně malý počet opakování.

Matematicky je sousedství mimořádného bodu (ne 4-valentního uzlu pro sítě se čtyřmi rafinovanými částmi) dělícího povrchu spline s parametrickým singulární bod [1].

Zušlechťovací schémata

Schémata dělení povrchových úprav lze obecně rozdělit do dvou kategorií: interpolační a přibližná. Interpolační schémata jsou nutná, aby odpovídala původní poloze vrcholů v původní síti. Aproximační schémata nejsou; mohou a budou upravovat tyto polohy podle potřeby. Obecně platí, že aproximační schémata mají větší plynulost, ale uživatel má menší celkovou kontrolu nad výsledkem. To je analogické k spline povrchy a křivky, kde Bézierovy křivky jsou povinni interpolovat určité kontrolní body, zatímco B-Splines nejsou.

Existuje také další rozdělení ve schématech dělení ploch: typ polygonu, na kterém operují. Některé fungují pro čtyřúhelníky (čtyřkolky), zatímco jiné fungují na trojúhelnících.

Aproximační schémata

Aproximace znamená, že mezní plochy se přibližují počátečním sítím a že po rozdělení se nově generované kontrolní body nenacházejí v mezních plochách. Existuje pět přibližných schémat dělení:

  • Catmull a Clark (1978) zobecňuje dvoukubický uniformní B-spline vložení uzlu. U libovolných počátečních sítí toto schéma generuje mezní plochy, které jsou C2 kontinuální všude kromě výjimečných vrcholů, kde jsou C1 kontinuální (Peters a Reif 1998) [2].
  • Doo-Sabine - Druhé dělící schéma vyvinuli Doo a Sabin (1978), kteří úspěšně rozšířili Chaikinovu metodu řezání rohů (George Chaikin, 1974)[3]) pro křivky k plochám. Použili analytický výraz bi-kvadratická uniforma B-spline povrchu, aby vygenerovaly svůj dělící postup k výrobě C1 omezit povrchy s libovolnou topologií pro libovolné počáteční sítě. Pomocný bod může zlepšit tvar dělení Doo-Sabin [4].
  • Smyčka „Triangles - Loop (1987) navrhl své dělící schéma založené na kvartice krabicový spline šesti směrových vektorů k poskytnutí pravidla pro generování C2 spojité mezní plochy všude kromě výjimečných vrcholů, kde jsou C1 kontinuální (Zorin 1997).
  • Schéma dělení Mid-Edge - Schéma dělení na střední hranici navrhla nezávisle Peters-Reif (1997) [5] a Habib-Warren (1999) [6]. První použil střed každého okraje k vytvoření nové sítě. Ten použil čtyřsměrný pole spline vybudovat schéma. Toto schéma generuje C1 spojité mezní plochy na počátečních sítích s libovolnou topologií.
  • √3 schéma dělení - Toto schéma vyvinul Kobbelt (2000)[7] a nabízí několik zajímavých funkcí: zpracovává libovolné trojúhelníkové sítě C2 nepřetržitý všude kromě výjimečných vrcholů, kde je C1 kontinuální a v případě potřeby nabízí přirozené přizpůsobení. Vykazuje alespoň dvě zvláštnosti: je to Dvojí schéma pro trojúhelníkové sítě a má pomalejší zdokonalení než prvotní. (Nejpomalejší dělení je dělení Midedge, které lze nazvat √2 dělení, protože dva kroky snižují vzdálenosti na polovinu.)

Interpolační schémata

Po rozdělení se řídicí body původní sítě a nově vygenerované kontrolní body interpolují na mezní ploše. Nejstarší práce byla tzv motýlí schéma autorů Dyn, Levin a Gregory (1990), kteří rozšířili čtyřbodové interpolační schéma dělení křivek na schéma dělení povrchu. Zorin, Schröder a Swelden (1996) si všimli, že motýlí schéma nemůže generovat hladké povrchy pro sítě nepravidelných trojúhelníků, a tak toto schéma upravilo. Kobbelt (1996) dále zobecnil čtyřbodové interpolační schéma dělení křivek na schéma dělení tenzorového produktu pro povrchy.

  • Doo-Sabine, Čtyřkolky - zobecnění dvoukvadratické uniformy B-splajny
  • Motýl, Trojúhelníky - pojmenované podle tvaru schématu
  • Midedge, Čtyřkolky
  • Kobbelt, Quads - variační metoda dělení, která se snaží překonat nevýhody jednotného dělení

Klíčový vývoj

externí odkazy

Reference

  1. ^ J. Peters a U. Reif: Dělení povrchů„Springerova řada Geometrie a výpočetní monografie 3, 2008, doi
  2. ^ J. Peters a U. Reif: Analýza zobecněných algoritmů dělení B-spline, SIAM J z Numer. Anální. 32 (2) 1998, str. 728-748
  3. ^ "Chaikinovy ​​křivky ve zpracování".
  4. ^ K. Karciauskas a J. Peters: Bodově rozšířený bikvadratický C.1 dělící povrchy, Grafické modely, 77, s. 18-26 [1]
  5. ^ J. Peters a U. Reif: Nejjednodušší schéma dělení pro vyhlazení mnohostěnů, ACM Transactions on Graphics 16 (4) (říjen 1997) str. 420-431, doi
  6. ^ A. Habib a J. Warren: Vkládání hran a vrcholů pro třídu C1 dělící povrchy, Computer Aided Geometric Design 16 (4) (květen 1999) str.223-247, doi
  7. ^ L. Kobbelt: √ 3 členění, 27. výroční konference o počítačové grafice a interaktivních technikách, doi
  8. ^ Ulrich Reif. 1995. Jednotný přístup k algoritmům dělení blízko mimořádných vrcholů. Počítačem podporovaný geometrický design. 12(2)153-174
  9. ^ Jos Stam, „Přesné vyhodnocení dělících povrchů Catmull-Clark při libovolných hodnotách parametrů“, Proceedings of SIGGRAPH'98. In Computer Graphics Proceedings, ACM SIGGRAPH, 1998, 395-404