MIP-Map Level berechnen (für SoftwareRenderer)



  • Hi Leute,

    Mein Problem ist, dass mein SoftwareRenderer für jedes Dreieck die passende MIP-Map Stufe ermitteln soll und dann diese Texture nutzen.
    Ich weiß aber nicht, nach welchen nach welchen Mathematischen Formeln ich die MIP-Map Level errechnen soll (ich meine nicht MIP-Map Generation!).
    Natürlich in Abhängigkeit von der Größe des Dreiecks und Größe der Texture. Aber wie soll ich das mathematisch machen? Und muss man dann für jedes Dreieck in einer Schleife (0 bis 'Anzahl der MIP-Maps') alle durch prüfen bis ich eine passende gefunden habe?
    Achja und: ich will meinem SoftwareRenderer natürlich nicht mehr als Per-Triangle-MIP-Mapping zu muten ^^ Per-Pixel-MIP-Mapping wäre etwas zu viel XD
    Danke schon mal 😃


  • Mod

    flaeche_von_texel/flaeche_von_pixeln



  • Zum Thema Dreiecksflächen habe ich in Wikipedia einen sehr schönen Artikel gefunden, dass ich da nicht schon von alleine drauf gekommen bin XD
    http://de.wikipedia.org/wiki/Dreiecksfl%C3%A4che
    Danke schön 🙂



  • Wenn Du Scanlines rasterst kannst Du die Mipmap-Stufe am UV-Delta ablesen.



  • rapso schrieb:

    flaeche_von_texel/flaeche_von_pixeln

    Nicht ganz!

    Man berechnet d = das Maximum von (Länge und Breite) eines auf die Texturebene abgebildeten Bildschirmpixels.

    (Die Fläche würde zu falschen Ergebnissen führen (so eine Art Mittelung) bei sehr schmalen und sehr breiten (oder umgekehrt) abgebildeten Pixeln! Dadurch würde eine Mipmap Stufe die zu fein aufgelößt ist gewählt werden und man bekäme wieder dieses unangenehme "rauschen" durch zu hohe Frequenzen im Bild die man ja gerade umgehen will.)

    Dann kann man unterscheiden.
    Nearest: Man wählt die Auflösungsstufe (Mipmap) dessen Texelgröße d am nächsten liegt.

    Linear: Man wählt eine Mipmap deren Texelgröße kleiner ist und eine deren Texelgröße größer ist und interpoliert linear dazwischen.

    Dann überlegt man sich noch wie man das passende Pixel in der Mipmap bestimmt.
    Auch hier kann man das nächstliegende nehmen oder linear zwischen den benachbarten Texeln interpoloeren.


  • Mod

    hellihjb schrieb:

    Wenn Du Scanlines rasterst kannst Du die Mipmap-Stufe am UV-Delta ablesen.

    UV delta in proportion zum X delta der scanline.

    [quote="Andreas XXL"][quote="rapso"]flaeche_von_texel/flaeche_von_pixeln

    Nicht ganz!

    Man berechnet d = das Maximum von (Länge und Breite) eines auf die Texturebene abgebildeten Bildschirmpixels.

    LukasBanana schrieb:

    Achja und: ich will meinem SoftwareRenderer natürlich nicht mehr als Per-Triangle-MIP-Mapping zu muten ^^ Per-Pixel-MIP-Mapping wäre etwas zu viel

    erst lesen!

    (Die Fläche würde zu falschen Ergebnissen führen (so eine Art Mittelung) bei sehr schmalen und sehr breiten (oder umgekehrt) abgebildeten Pixeln!

    auch pro pixel wuerde immer noch zu falschen ergebnissen fuehren, aber es scheint niemanden zu stoeren dass selbst graphikkarten das nicht per pixel berechnen.

    Dadurch würde eine Mipmap Stufe die zu fein aufgelößt ist gewählt werden und man bekäme wieder dieses unangenehme "rauschen" durch zu hohe Frequenzen im Bild die man ja gerade umgehen will.)

    solange die proportionen nicht 1:1 sind hast du eh nur die wahl zwischen rauschen und matsch bei tri/bilinearer filterung.


  • Mod

    LukasBanana schrieb:

    Zum Thema Dreiecksflächen habe ich in Wikipedia einen sehr schönen Artikel gefunden, dass ich da nicht schon von alleine drauf gekommen bin XD
    http://de.wikipedia.org/wiki/Dreiecksfl%C3%A4che
    Danke schön 🙂

    du machst sicher backfaceculling, vermutlich berechnest du dabei schon die flaeche (aber achtest nur auf das vorzeichen). musst das selbe nur noch fuer UV machen.



  • Zitat:

    [quote="Andreas XXL"][quote="rapso"]flaeche_von_texel/flaeche_von_pixeln

    Nicht ganz!
    Zitat:

    Man berechnet d = das Maximum von (Länge und Breite) eines auf die Texturebene abgebildeten Bildschirmpixels.

    Ich verstehe nicht was Du mir damit sagen willst! (Falls es für mich bestimmt sein sollte.)

    Irgend was scheint mit dem Zitieren nicht zu stimmen. Wenn ich versuche deinen Beitrag (komplett) zu zitieren mit diesem "zitieren" Button, kommt da nur unleserliches bei rum! (viele Formatierungs Strings)


  • Mod

    Andreas XXL schrieb:

    Ich verstehe nicht was Du mir damit sagen willst! (Falls es für mich bestimmt sein sollte.)

    er hat explizit gesagt, dass er es nicht per pixel machen will, sondern per dreieck, deine antwort, dass meine "night ganz" ist, weil es per pixel gemacht ist, ist irgendwie..emm... void.

    desweiteren sage ich, dass selbst grakas es nicht per pixel machen, weil es eh falsch ausschaut, "anders falsch" ist somit keine wirkliche loesung.

    Irgend was scheint mit dem Zitieren nicht zu stimmen. Wenn ich versuche deinen Beitrag (komplett) zu zitieren mit diesem "zitieren" Button, kommt da nur unleserliches bei rum! (viele Formatierungs Strings)

    ja, liegt wohl an mir, hatte da irgendwoe ein quoute oder so falsch gesetzt.



  • Ahhh, ok.

    er hat explizit gesagt, dass er es nicht per pixel machen will, sondern per dreieck, deine antwort, dass meine "night ganz" ist, weil es per pixel gemacht ist, ist irgendwie..emm... void.

    Ich glaube da war ein Mißverständnis. Mit "nicht ganz", meinte ich einfach nur, das man in die Berechnung nicht die Fläche (größe der Fläche) einfließen läßt, sondern die Maxima der Seitenlängen! (Egal ob auf Pixelebene oder per Dreieck)

    sorry, fals "nicht ganz" für Irritationen gesorgt hat 😉

    (editiert)
    Vorher stand hier:

    Aber er kann es doch für einen Pixel in der Mitte des Dreiecks so berechnen und das dann auf das gesamte Dreieck anwenden.
    (Mit Flächenberechnungen haut das einfach nicht so hin)


  • Mod

    Andreas XXL schrieb:

    Ahhh, ok.

    Aber er kann es doch für einen Pixel in der Mitte des Dreiecks so berechnen und das dann auf das gesamte Dreieck anwenden.
    (Mit Flächenberechnungen haut das einfach nicht so hin)

    im besten fall (also seitenverhaeltnisse 1:1) ist das ergebnis gleich, im schlimmsten hat er mit deiner methode matsch und mit meinem vorschlag kriseln, ich wuerde keine als besser bezeichnen, sondern nur 'anders falsch' nennen.
    fuer mehr qualitaet hilft nur feiner zu entscheiden welche miplevel man nimmt oder supersampling, doch beides kostet performance.



  • im schlimmsten hat er mit deiner methode matsch und mit meinem vorschlag kriseln

    Aber genau das macht MipMapping doch. Matsch (weniger hohe Frequenzen) um das Krieseln (hohe Frequenzen) wegzumachen.

    Das d was man berechnet (du mit der Fläche, ich mit dem Maxima der Seitenlängen) gibt ja genau an, wie viel "Matsch" man braucht um das Krieseln wegzubekommen.

    Wenn man also im schlimmsten Fall das "Krieseln" beibehält, hat man nicht das erreicht was Mipmapping machen soll.

    (Feiner entscheiden als ein Level zu groß und eins zu klein und dann lineare Interpolation dazwischen geht bei Mipmapping nicht.)

    Super Sampling ist natürlich besser, geht aber nach einem anderen Prinzip an die Sache ran, braucht mehr Rechenpower und wurde deswegen erst später eingeführt.


  • Mod

    Andreas XXL schrieb:

    im schlimmsten hat er mit deiner methode matsch und mit meinem vorschlag kriseln

    Aber genau das macht MipMapping doch. Matsch (weniger hohe Frequenzen) um das Krieseln (hohe Frequenzen) wegzumachen.

    Das d was man berechnet (du mit der Fläche, ich mit dem Maxima der Seitenlängen) gibt ja genau an, wie viel "Matsch" man braucht um das Krieseln wegzubekommen.

    Wenn man also im schlimmsten Fall das "Krieseln" beibehält, hat man nicht das erreicht was Mipmapping machen soll.

    ich glaube das siehst du ein wenig falsch.
    mipmapping hat man nicht aus bildqualitaetsgruenden erfunden, sondern aus performance gruenden.
    Neben Mipmapping hat man auch mit Rimmapping experimentiert, bei dem man texturen nicht nur wie bei mipmaps in halben aufloesungen ablegte, sondern zusaetzlich nur in einer achse runterskalierte texturen nutzt. wuerdest du mipmapping weglassen, waere vermutlich kein spiel das du heute siehst noch fluessig.

    neben performance, ist es ein ziel eine gute bildqualitaet zu erreichen. wenn man nur krisseln wegbekommen wollen wuerde, koennte man auch ganz auf texturen verzichten. ziel ist jedoch sowohl krisseln als auch matsch zu vermeiden.

    ein trick den manche treiber machen ist z.b. die 'energie', kontrast usw. von texturen zu bestimmen und anhand dessen die mipmap-level auszuwaehlen.

    matsch ist garantiert nicht das ziel von mipmapping.

    (Feiner entscheiden als ein Level zu groß und eins zu klein und dann lineare Interpolation dazwischen geht bei Mipmapping nicht.)

    Super Sampling ist natürlich besser, geht aber nach einem anderen Prinzip an die Sache ran, braucht mehr Rechenpower und wurde deswegen erst später eingeführt.

    supersampling auf texturen nennt man anisotropisches filtern und es geht nach dem selben prinzip ran, es versucht die unter einem pixel vorhandene texelflaeche abzutasten.
    das macht bilineare filterung auch, das problem ist, dass nicht-lineare-verzerrungen nicht durch lineare interpolation kompensiert werden koennen.
    der trick liegt bei AF daran, dass man eine besser aufgeloeste mipmap-level auswaehlt und dafuer durch mehrmalliges samplen das rauschen mindert.
    das alles nur um die effekte der verzerrung von texturen zu lindern. wuerdest du alle texturen unverzerrt rendern (z.b. quadratische sprites mit quadratischen texturen) wuerdest du supersampling/AF nicht von bilinear-filtering unterscheiden koennen.



  • mipmapping hat man nicht aus bildqualitaetsgruenden erfunden, sondern aus performance gruenden

    OK, ich habe jetzt wirklich gelacht... aber wir haben nicht den 1. April.

    Ich denke mal du meinst das Ironisch. Ich wäre fast drauf reingefallen und hätte ne Diskussion gestartet.

    Somit beende ich diese Diskussion was mich angeht. (Ist nicht bös gemeint 😉 )

    PS.
    Hier sind einige Filme (Flash Videos). (Unten auf der Seite).
    Weiß nicht ob das Entsprechende dabei ist.
    Unterhaltsam ist es aber 😃

    http://www-lehre.inf.uos.de/~cg/2008/index.html


  • Mod

    Andreas XXL schrieb:

    mipmapping hat man nicht aus bildqualitaetsgruenden erfunden, sondern aus performance gruenden

    OK, ich habe jetzt wirklich gelacht... aber wir haben nicht den 1. April.

    Ich denke mal du meinst das Ironisch. Ich wäre fast drauf reingefallen und hätte ne Diskussion gestartet.

    Somit beende ich diese Diskussion was mich angeht.

    das einzige was deine ignoranz erreicht ist dein eigenes wissen zu limitieren.



  • rapso schrieb:

    Andreas XXL schrieb:

    mipmapping hat man nicht aus bildqualitaetsgruenden erfunden, sondern aus performance gruenden

    OK, ich habe jetzt wirklich gelacht... aber wir haben nicht den 1. April.

    Ich denke mal du meinst das Ironisch. Ich wäre fast drauf reingefallen und hätte ne Diskussion gestartet.

    Somit beende ich diese Diskussion was mich angeht.

    das einzige was deine ignoranz erreicht ist dein eigenes wissen zu limitieren.

    Klick einfach auf den Link und sieh dir die Videos an...
    (Kann man auch gut zum Einschlafen verwenden)


  • Mod

    Andreas XXL schrieb:

    rapso schrieb:

    Andreas XXL schrieb:

    mipmapping hat man nicht aus bildqualitaetsgruenden erfunden, sondern aus performance gruenden

    OK, ich habe jetzt wirklich gelacht... aber wir haben nicht den 1. April.

    Ich denke mal du meinst das Ironisch. Ich wäre fast drauf reingefallen und hätte ne Diskussion gestartet.

    Somit beende ich diese Diskussion was mich angeht.

    das einzige was deine ignoranz erreicht ist dein eigenes wissen zu limitieren.

    Klick einfach auf den Link und sieh dir die Videos an...
    (Kann man auch gut zum Einschlafen verwenden)

    lies du dir dafuer einfach das paper mit der erfindung von mipmaps durch.

    As the projected scale of the
    surface increases, interpolation between
    the original samples of the source image
    is necessary; as the scale is reduced,
    approximation of multiple samples in the
    source is required. Thus a constantly
    changing sampling window of view-dependent
    shape must traverse the source image.

    To reduce the computation implied by
    these requirements, a set of prefiltered
    source images may be created.



    Ich Diskutiere immer noch 😉

    Der Link ist ungefährlich (uos) steht für Universität Osnabrück.
    (Da sind Vorlesungsvideos) Falls du dich nicht traust da draufzuklicken.

    Steht in deinem Ausschnitt, das man Bilder mit verschiedener Auflösung (prefiltered = vorgefiltert) berechnen muß, um MipMapping effizient (schnell) durchführen zu können.
    Kein Mipmapping ist aber schneller als Mipmapping. Da hilft auch kein englischer Text der erläutert wie man Mipmapping beschleunigen kann.

    Falls du es lieber lesen möchtest als es anzusehen:
    http://www-lehre.inf.uos.de/~cg/2008/PDF/skript.pdf

    Um den korrekten
    perspektivischen Eindruck zu erzeugen, muß diese Tatsache durch Antialiasing berücksichtigt
    werden. Eine Möglichkeit, dies zu tun ist das Mip Mapping

    Seite 212

    Das bedeutet es sieht mit Mip Mapping besser "korrekter" aus.
    Nix schneller!

    So jetzt ist aber wirklich schluß für mich.


  • Mod

    Andreas XXL schrieb:

    Der Link ist ungefährlich (uos) steht für Universität Osnabrück.
    (Da sind Vorlesungsvideos) Falls du dich nicht traust da draufzuklicken.

    das dreht die tatsache nicht um weshalb mipmaps erfunden wurden.

    Steht in deinem Ausschnitt, das man Bilder mit verschiedener Auflösung (prefiltered = vorgefiltert) berechnen muß, um MipMapping effizient (schnell) durchführen zu können.

    scheint als haettest du probleme mit dem text, ich uebersetze dir gerne den ausschnitt den ich zittierte.

    As the projected scale of the 
    surface increases, interpolation between 
    the original samples of the source image 
    is necessary; as the scale is reduced,     wenn das bild runterskaliert wird
    approximation of multiple samples in the   werden [b]mehrere samples[/b] der quell-
    source is required. Thus a constantly      textur benoetigt. also ein sich
    changing sampling window of view-dependent wechselndes filter fenster, abhaengig
    shape must traverse the source image.      von der ansicht.
    
    To reduce the computation implied by       um den rechenaufwand der damit verbun-
    these requirements, a set of prefiltered   den ist zu reduzieren, werden 
    source images may be created.              vorberechnete bilder(mipmaps) erstellt
    

    Kein Mipmapping ist aber schneller als Mipmapping. Da hilft auch kein englischer Text der erläutert wie man Mipmapping beschleunigen kann.

    1. deine behauptung ist falsch in bezug auf graphikkarten, 10 bis 100mal mehr textur daten zu transferieren ist unmoeglich schneller.
    2. deine behauptung ist falsch in bezug auf unseren dialog hier, weshalb mipmaps erfunden wurden. oben steht was es zur auswahl gab, entweder viele samples oder mipmaps.
    3. es steht auch explizit im paper von vor 25 jahren

    The routines for creating and accessing
    mip maps at NYIT are based on simple
    box (Fourier) window prefiltering, bilinear
    interpolation of pixels within each
    map instance, and linear interpolation
    between two maps for each value of D (the
    pyramid's vertical coordinate).
    For each
    of the three components of a color mip
    map, this requires 8 pixel reads and 7
    multiplications. This choice of filters    Der Grund zur wahl dieser filterung 
    is strictly for the sake of speed.         ist ausschlisselich geschwindigkeit
    

    [quote]

    Falls du es lieber lesen möchtest als es anzusehen:
    http://www-lehre.inf.uos.de/~cg/2008/PDF/skript.pdf

    Um den korrekten
    perspektivischen Eindruck zu erzeugen, muß diese Tatsache durch Antialiasing berücksichtigt
    werden. Eine Möglichkeit, dies zu tun ist das Mip Mapping

    Seite 212

    Das bedeutet es sieht mit Mip Mapping besser "korrekter" aus.
    Nix schneller!

    lies nochmal "eine moeglichkeit", bevor diese moeglichkeit erfunden wurde, hat man mit filterkernel umengen von pixeln gewichtet und aufakkumuliert. Steht auch in deinem paper:

    Damit nicht zur Laufzeit f¨ur jedes Pixel die Summe ¨uber alle ¨uberdeckten Texel gebildet werden muß,
    werden im Speicher schlechter aufgel¨oste Versionen der Textur vorgehalten

    hardware heutzutage ist daraufhin gebaut, dass texturen als mipmaps vorliegen. mit linear steigender entfernung reduzieren mipmaps quadratisch die menge der daten die transferiert werden. das liegt daran, dass speicher nur cachelineweise gelesen werden kann, auf graphikkarten liegen die texturen sogar in speziellen layouts vor um cachelines weiter auszureizen.

    wenn du also ein texel liest, wird die graphikkarte auf einen schlag vielleicht 256 pixel in den cache laden, mit der annahme, dass der nachbarpixel auch ein nachbartexel lesen wird. das ist mit mipmapping gewaehrleistet. hast du z.b. nur noch 16*16pixel die dein dreieck abdeckt und du brauchst dafuer 16*16 texel, brauchst du vielleicht nur einen einzigen speichertransfer.
    hast du keine mipmap, sondern nur deine orginal 256256 textur, wird fuer jedes texel das du dann ausliesst jeweils 256texeln aus dem speicher in den cache geladen.
    nicht nur dass du dadurch 256mal mehr speicher transferieren wirst, du bringst die graphikkarte auch dazu nichts zu tun und zu warten. bei 16*16pixeln, kann eine graphikkarte eventuell die ganze latenz die benoetig wird um den speicher in den cache zu bekommen mit anderen operationen verstecken (z.b. eben lerp werte berechnen, perspektivische projektion durchfuehren fuer den naechsten 256pixel-block), doch sobald das getan ist fuer die 16*16pixel, erwartet die graphikkarte dass sie jetzt durchgaengig texel aus dem cache samplen kann.
    ist das nicht der fall, wartet die karte die weiteren 255mal.
    ein speichertransfer hat dabei ca 300cycle latenz. wie du dir denken kannst, kann man das relativ gut mit mathe fuer 256pixel versteken. hast du jedoch 256
    300cycles, also 75kCycles, hat dich graphikkarte nichts zu tun.
    falls dein bild 1920*1080 ist, hast du ca 8000 solcher kacheln und damit 600MHz deiner graphikkarte mit warten verschwendet.

    wenn dir das als erklaerung nicht reicht, geb ich auf.



  • Kein Mipmapping ist aber schneller als Mipmapping

    Selbst wenn Du lediglich Point-Sampling machst bringen Mip-Maps erhebliche Geschwindigkeitsvorteile.
    Verwendet man nicht die naechst-kleinere Mipmap wird die Haelfte^2 aller Texel nicht verwendet, laufen aber trotzdem durch den Cache.
    Dass das schaedlich ist hat rapso ja schon hinreichend beschrieben.

    Davon abgesehen weisst schon die Pyramidenstruktur auf einen Optimierungsansatz hin, vom Vorberechnen mal ganz zu schweigen.


Log in to reply