Vi undersöker arkitektoniska system, generalisera det av befintliga grafikmotorer, stödja snabb rendering av triangelmaskor. En mesh som definieras på n hörn återges genom att skicka hörn ner en grafik pipeline, varefter de trycks på en stack som ska poppas när det inte längre behövs. Endast enskilda trianglar vars hörn finns i stacken får återges, Lagringskostnaden för mesh rendering är storleken på den stack som krävs för att lagra nät hörn under renderingsprocessen. Detta kan vara betydligt mindre än n. Tidskostnaden för mesh rendering är antalet hörn som skickas ner grafik pipeline. Om en tillräckligt stor stack finns, räcker det att skicka varje vertex en gång. Om bara en liten stack finns tillgänglig, vissa hörn kan behöva skickas mer än en gång, så en tid / utrymme avsättning finns, Med vår arkitektur, en stack av storlek 0 (V) är tillräckligt för att göra någon triangel mesh definieras på n hörn, så att varje vertex skickas bara en gång genom grafik pipeline (tidskostnad = n J. Vi tillhandahåller en algoritm som genererar en lämplig "rendering sekvens" av kommandon för varje givet mesh. Dessutom visar vi att ingen algoritm kan göra bättre, det vill säga, Cl(\~) är en lägre gräns. Vissa n -vertex maskor kan återges med hjälp av en stack vars storlek är betydligt mindre än 0 (~n ). En algoritm som genererar en minsta tid renderingssekvens som kräver den minsta stackstorleken är en öppen fråga. Vi ger en approximation: om det är teoretiskt möjligt att göra en triangel mesh i minimal tid med en stack av storlek S, genererar vår algoritm en minimal tid rendering sekvens som kräver en stack av storlek inte större än 2S log~rln. Om bara en stack av storlek k är tillgänglig, tillhandahåller vi en algoritm som genererar en renderingssekvens som kräver en stack av storlek inte större än k, så att som mest n ( 1 + c/k) hörn måste skickas genom rörledningen, för vissa konstant c.
I REF är det bevisat att detta kräver en buffert av storlek minst 1 649 p n och högst 12:72 p n för en triangelmaska med n hörn.
Time/space tradeoffs for polygon mesh rendering
{'venue': 'TOGS', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}