Borttagning av dolda linjer
I 3D-datorgrafik är solida objekt vanligtvis modellerade av polyedrar . En yta av en polyeder är en plan polygon som begränsas av raka linjesegment, som kallas kanter . Böjda ytor är vanligtvis ungefärliga av ett polygonnät . Datorprogram för linjeteckningar av ogenomskinliga objekt måste kunna avgöra vilka kanter eller vilka delar av kanterna som döljs av ett objekt i sig eller av andra objekt, så att dessa kanter kan klippas under renderingen . Detta problem kallas för borttagning av dolda linjer .
Den första kända lösningen på problemet med dolda linjer utarbetades av LG Roberts 1963. Den begränsar dock modellen kraftigt: den kräver att alla objekt är konvexa . Ruth A. Weiss från Bell Labs dokumenterade sin lösning från 1964 på detta problem i en tidning från 1965. 1966 Ivan E. Sutherland 10 olösta problem inom datorgrafik. Problem nummer sju var "borttagning av dolda linjer" . När det gäller beräkningskomplexitet löstes detta problem av Devai 1986.
Modeller, t.ex. i datorstödd design , kan ha tusentals eller miljontals kanter. Därför är en beräkningskomplexitetsmetod som uttrycker resurskrav (som tid och minne) som funktionen av problemstorlekar avgörande. Tidskrav är särskilt viktiga i interaktiva system.
Problemstorlekar för borttagning av dolda linjer är det totala antalet n av kanterna på modellen och det totala antalet v av de synliga segmenten av kanterna. Sikten kan ändras vid skärningspunkterna för bilderna av kanterna. Låt k beteckna det totala antalet skärningspunkter för bilderna av kanterna. Både k = Θ( n 2 ) och v = Θ( n 2 ) i värsta fall, men oftast v < k .
Algoritmer
Algoritmer för dolda linjer publicerade före 1984 delar upp kanter i linjesegment efter skärningspunkterna för deras bilder och testar sedan varje segment för synlighet mot varje sida av modellen. Om man antar en modell av en samling polyedrar med gränsen för varje topologiskt ekvivalent med en sfär och med ytor topologiskt ekvivalenta med skivor, enligt Eulers formel, finns det Θ( n ) ytor . Att testa Θ( n 2 ) linjesegment mot Θ( n ) ytor tar Θ( n 3 ) tid i värsta fall. Appels algoritm är också instabil, eftersom ett fel i synlighet kommer att spridas till efterföljande segmentslutpunkter.
Ottmann och Widmayer och Ottmann, Widmayer och Wood föreslog O (( n + k ) log 2 n )-tid dolda linjer algoritmer. Sedan förbättrade Nurmi löptiden till O (( n + k ) log n ). Dessa algoritmer tar Θ( n 2 log 2 n ), respektive Θ( n 2 log n ) tid i värsta fall, men om k är mindre än kvadratisk, kan det vara snabbare i praktiken.
Alla dolda linjers algoritmer måste bestämma föreningen av Θ( n ) dolda intervall på n kanter i värsta fall. Eftersom Ω( n log n ) är en nedre gräns för att bestämma föreningen av n intervall, verkar det som att det bästa man kan hoppas på att uppnå är Θ( n 2 log n ) värsta fallet, och därför är Nurmis algoritm optimal.
Emellertid eliminerades log n- faktorn av Devai, som tog upp det öppna problemet om samma optimala O ( n 2 ) övre gräns fanns för borttagning av dold yta. Detta problem löstes av McKenna 1987.
De korsningskänsliga algoritmerna är främst kända inom beräkningsgeometrilitteraturen. De kvadratiska övre gränserna uppskattas också av datorgrafiklitteraturen: Ghali noterar att algoritmerna av Devai och McKenna " representerar milstolpar i synlighetsalgoritmer" och bryter en teoretisk barriär från O ( n 2 log n ) till O ( n 2 ) för bearbeta en scen med n kanter.
Det andra öppna problemet, som tagits upp av Devai, om huruvida det finns en O ( n log n + v )-tids dolda linjealgoritm, där v , som nämnts ovan, är antalet synliga segment, är fortfarande olöst vid tidpunkten för skrift.
Parallella algoritmer
1988 föreslog Devai en O (log n )-tidsparallellalgoritm som använder n 2 processorer för problemet med dolda linjer under beräkningsmodellen med parallell läs, exklusiv skrivning (CREW) parallell slumpmässig åtkomstmaskin (PRAM). Eftersom produkten av processornumret och körtiden är asymptotiskt större än Θ( n 2 ), den sekventiella komplexiteten för problemet, är algoritmen inte arbetsoptimal, men den visar att problemet med dolda linjer är i komplexitetsklassen NC , dvs det kan lösas i polylogaritmisk tid genom att använda ett polynomantal av processorer.
Algoritmer för dolda ytor kan användas för att ta bort dolda linjer, men inte tvärtom. Reif och Sen föreslog en O (log 4 n )-tidsalgoritm för problemet med dolda ytor, med O (( n + v )/log n ) CREW PRAM-processorer för en begränsad modell av polyedriska terränger, där v är utdatastorleken .
2011 publicerade Devai en O (log n )-time hidden-surface och en enklare, även O (log n )-time, hidden-line-algoritm. Algoritmen för dold yta, som använder n 2 /log n CREW PRAM-processorer, är arbetsoptimal.
Algoritmen för dolda linjer använder n 2 exklusiva läs, exklusiv skrivning (EREW) PRAM-processorer. EREW-modellen är den PRAM-variant som ligger närmast riktiga maskiner. Algoritmen för dolda linjer O ( n 2 log n ), vilket är den övre gränsen för de bästa sekventiella algoritmerna som används i praktiken.
Cook, Dwork och Reischuk gav en Ω(log n ) nedre gräns för att hitta det maximala antalet av n heltal, vilket tillåter oändligt många processorer av alla PRAM utan samtidiga skrivningar. Att hitta det maximala antalet av n heltal är konstant-tid reducerbart till problemet med dolda linjer genom att använda n processorer. Därför är hidden-line-algoritmen tidsoptimal.
Se även
externa länkar
- Patrick-Gilles Maillots avhandling , en förlängning av Bresenhams linjeritningsalgoritm för att utföra 3D-borttagning av dolda linjer; även publicerad i MICAD '87-förfaranden om CAD/CAM och datorgrafik, sidan 591, ISBN 2-86601-084-1 .
- Vector Hidden Line Removal , en artikel av Walter Heger med ytterligare beskrivning (av de patologiska fallen) och fler citat.