Vi visar en ray gjutning typ teknik för rendering algebraiska ytor med programmerbar grafik hårdvara (GPUs). Vårt tillvägagångssätt möjliggör realtidsutforskning och manipulation av godtyckliga verkliga algebraiska ytor, utan förbehandlingssteg, förutom en förändring av polynombasen. Algoritmen är baserad på den blommande principen av trivariat Bernstein-Bézier fungerar över en tetrahedron. Genom att beräkna blomman av den funktion som beskriver ytan med avseende på varje ray, får vi koefficienterna för en univariat Bernstein polynomial, som beskriver ytans värde längs varje ray. Vi använder sedan Bézier delsektion för att hitta den första roten av kurvan längs varje stråle för att visa ytan. Dessa beräkningar utförs parallellt för alla strålar och utförs på en GPU. För en funktion f : R 3 → R kan en implicit yta definieras av nivåuppsättningen av ekvationen f (x, y, z) = c, där x, y, z, c  till R. Genom att omordna termerna kan vi, utan förlust av generalitet, bara överväga nolluppsättningen av funktionen, t.ex. f (x, y, z) − c = 0. För detta arbete anses alla funktioner och ytor vara realvärderade. Om funktionen f är ett algebraiskt polynom kallas den resulterande ytan en algebraisk yta. Sådana ytor kan lätt beskriva invecklade, släta former med varierande topologi, och även möjliggöra interpolering och blandning av sådana ytor. Deras polynomiska natur gör det också lätt att hitta analytiska riktningsderivat, normaler och krökningar. Vår algoritm är baserad på den klassiska strålgjutningen, där strålarna passerar från ögat, och vi vill hitta platsen för varje strål första korsning med ytan. För en given algebraisk yta f (x, y, z) = 0 av total grad d, är vi bara intresserade av skärningspunkter inuti en vy volym V. Därför är det naturligt att bara överväga segmentet av varje stråle inuti V. Låt f och b representera den främre och bakre koordinaten av strålen när den går in och lämnar V. segmentet ges sedan av parametriseringen p(t) = (1 − t)f + tb, t  på [0, 1]. Vi kombinerar denna parametrisering med ekvationen algebraisk yta, vilket ger en univariat polynom g(t) = f (p(t)) av grad d. Nu problemet med att hitta den närmaste skärningspunkten till ögonpunkten, kan omformuleras till att hitta den minsta Genom att använda strålgjutning formulering, processen att extrahera noll uppsättningen av ett multivariat polynom, har ersatts av en mängd oberoende rotfyndsproblem. GPU är väl lämpad för sådana parallella beräkningar, och vi sammanfattar vår algoritm enligt följande: 1. Frågan spänner geometri till GPU. Den spänngeometri definierar vår syn volym V, och initierar rendering. 2. Utgångspunkten är följande: Låt GPU rasterisera spänngeometrin i en uppsättning fragment, vilket ger koordinaterna f och b för varje stråle. 3. Vad är det som händer? Hitta en univariat polynom, g(t), som representerar värdet av algebraisk yta längs varje stråle. 4. Vad är det som händer? Hitta den minsta t sådan att g(t) = 0. Om inga nollor hittas, slänger vi fragmentet. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. För de överlevande fragmenten, beräkna det slutliga djupet och färgen genom att använda information från algebraisk yta. pixelplan För varje strålesegment inuti vyn volym V, hittar vi de främre (f) och bakre (b) vektorer i barycentriska koordinater. Sedan använder vi blommande för att hitta koefficienterna för den unika BernsteinBézier funktionen längs varje stråle. Flera andra verk diskuterar strålgjutning som algoritmer på GPU, och nuvarande intresse är högt. Men direkt hårdvarustöd verkar fortfarande vara en lång väg, och de flesta strategier innebär en avsevärd mängd tweaking för att köra på en GPU. Donnelly [1] använder sfärspårning för att effektivt genomföra avgränsad deplacementkartläggning med hjälp av fragmentskuggare. Loop och Blinn [2] har visat att algebraiska ytor återges, vilket är mycket likt vårt tillvägagångssätt. Deras fokus har dock varit på att göra styckvisa ytor som spänner över ett stort antal tetrahedroner. De använder dock analytiska rotfyndsalgoritmer, vilket begränsar den maximala grad av ytor de kan visualisera till allmänna kvartiska ytor, eftersom det inte är möjligt att analytiskt lösa allmänna ekvationer av grad 5 och högre. FIGUR 2: En kvintisk yta med maximalt antal vanliga dubbla punkter, 31. Det är också känt som en Dervish yta. När det gäller verkliga polynom av total grad d är det välkänt att de kan uttryckas i Bernstein-Bézier (BB) bas, vilket är att föredra för användning i beräkningar eftersom det är numeriskt optimalt [3]. De Bernstein basfunktioner B d i grad d kan uttryckas som: Här betecknar β β β = β β β(x) = (β1(x),...,βs+1(x)) den barycentriska koordinaten för en punkt x  på R s med avseende på en uppsättning baspunkter, (v1,...,vs+1) R s, som bildar en icke-degenererad simplex  på = conv(v1,...,vs+1). Till exempel är 2-simplex en triangel och 3-simplex en tetrahedron. Ett polynom tar sedan formen f (x) =  tilli biB d i (β β β). De Casteljau algoritmen ger ett snabbt och numeriskt stabilt sätt att utvärdera ett BB-polynom. Låt bi betecknar koefficienterna för en algebraisk funktion i BB-form och beräkna upprepade konvexa kombinationer av baspunkter genom att ställa in: (2) De Casteljau algoritm medger också en uppdelning formel för Bézier kurvor, och kontrollen polygon av en sådan kurva konvergerar till kurvan själv. I synnerhet, en sådan kurva har inte fler rötter än det finns tecken förändringar i kontrollen polygon. Om vi modifierar de Casteljau algoritmen genom att införa en sekvens av parameterpunkter, (β β β1,...,β β βd) och använda en distinkt punkt på varje nivå av rekursion, kommer vi fram till blomman av polynomet, som vi betecknar som B. Blomman ges av: Nyckeln till att hitta en kurva som representerar värdet av f längs linjesegmentet xy är en överraskande egenskap hos blomman, som vi sammanfattar i följande lemma: Lemma 1 Med tanke på två punkter α α = β β β (x) och γ γ = β β β (y), x, y  tills och en multivariat BB-polynomial f (β β β). Sedan den raka linjen segment från x till y kartläggs till en univariat BB-polynom av grad d, och dess koefficienter ges genom upprepad blomning av slutpunkterna, För att sammanfatta, blomman ger oss de algoritmer som behövs för att omvandla en trivariat polynomial till en uppsättning univariat polynomials med avseende på varje ray.  För att initiera vår algoritm måste vi skicka geometrin som omfattar den barycentriska domänen till GPU. Teoretiskt alla konvexa form kommer att räcka, men i praktiken former som det är trivialt att beräkna de barycentriska främre och bakre koordinaterna för varje ray är bäst lämpade. Blossoming Den mest krävande deluppgiften i visualiseringen är beräkningen av koefficienterna för kurvan som representerar värdet av f längs varje stråle. Vi finner dessa koefficienter genom att blomma och bilda en algoritm baserad på (3). Om rekursionen hade fått stöd av GPU, kunde vi ha genomfört (3) direkt. Men nuvarande generation GPUs stöder inte rekursion, så för en given grad d, använder vi CPU för att rulla rekursionen och generera ett långt uttryck av skuggar källkod, som representerar blomman. Vi använder enhetliga variabler för att representera koefficienterna på ytan, och eftersom blomman omberäknas för varje ram, gör detta att vi enkelt ändra ytan genom att ändra koefficienterna, vilket möjliggör formmanipulation i realtid. Rotfynd På grund av dess enkla datastruktur bestämde vi oss för att använda en heuristisk rotfyndsmetod baserad på rekursiv indelning av koefficienterna, som beskrivs av Schneider [5]. Tanken är att rekursivt dela polynomet i hälften genom att använda de Casteljau algoritm (2). På varje rekursionsnivå räknar vi antalet teckenändringar i koefficienterna, och om båda uppsättningarna av koefficienter innehåller teckenändringar väljer vi att fortsätta att dela upp de vänstra största av dem, samtidigt som vi lagrar den andra eftersom vi kan behöva koppla av rekursionen om den första visar sig vara en falsk nolla. Om bara en uppsättning koefficienter har teckenändringar, väljer vi naturligtvis denna för ytterligare indelning. Detta använder effektivt Bézier konvexa skrovegenskaper för att säkerställa att en nolla ligger inom ett intervall som anges av koefficientens endpoints. Eftersom det kan hända att det finns en falsk nolla måste vi kunna varva ner rekursionen och välja ett annat intervall för att dela upp. På en vanlig CPU detta skulle vara trivialt, men som GPU saknar en stack vi lagrar de andra potentiella koefficienter och rekursionsnivå, och när vi upptäcker en falsk nolla vi avrulla till den sista uppsättningen potentiella koefficienter. Antalet möjliga falska nollor begränsas av graden av ytan, så vi vet i förväg hur många uppsättningar av koefficienter vi kan behöva lagra. Vi avslutar rekursionen när vi kan bestämma att det inte finns någon rot (inga tecken förändringar av koefficienterna), eller när vi når en fast nivå av underavdelningar. Vårt arbete presenterar en realtidsrenderingsstrategi för algebraiska ytor upp till totalt fem grader. I takt med att GPU-tekniken går framåt anser vi dock att den kan förbättras ytterligare. De två mest uppenbara frågorna, och därmed de främsta kandidaterna för ytterligare arbete, är att öka renderingshastigheten och graden av ytor vi kan visualisera. Med hjälp av vår nuvarande rotfyndsalgoritm kan vi stabilt isolera rötter för polynom upp till grad 10, den begränsande faktorn är att vi får slut på tillfälliga register på GPU. DX10 GPU kommer i hög grad att öka antalet sådana register. Vårt nuvarande tillvägagångssätt är beräkningsintensivt och vi experimenterar för närvarande med andra metoder, såsom B-spline-knutinsättning [4] eller hybridmetoder som Brent-Dekker. Dessa metoder är dock mycket dynamiska, och effektiva GPU-implementeringar är inte triviala, och kommer troligen att baseras på multipass-metoder. Vår nuvarande blommande algoritm är mycket dålig på att utnyttja vektorisering möjligt inom varje fragment pipeline. Tillvägagångssättet av [2] använder tensor kontraktion, som har en högre computational komplexitet än vår metod, men är mycket effektiv på en GPU. Effektiv blockering av diskreta Bsplinematriser kan vara ett sätt att få det bästa av båda världarna, och vara nyckeln för att effektivt göra hög beställa ytor.
Seland och Dokken REF gjorde låggradiga algebraiska ytor genom att använda blommor av trivariat Bernstein-Bézier funktioner över tetrahedra.
Real-Time Algebraic Surface Visualization
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}