.[ ČeskéHry.cz ].
Celočíselná interpolace

 
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> C / C++
Zobrazit předchozí téma :: Zobrazit následující téma  
Autor Zpráva
frca



Založen: 28. 07. 2007
Příspěvky: 1498

PříspěvekZaslal: 10. leden 2022, 17:41:46    Předmět: Celočíselná interpolace Odpovědět s citátem

Zdravím,
přemýšlím, jak urychlit interpolaci, aby se v každém kroku nepoužívalo násobení a dělení. Prostě nějak rozdistribuovat ten zbytek... Netušíte? Díky.
kód:

#include <iostream>

void naiveLerp(int len, int value)
{
    for (int i = 0; i <= len; ++i)
    {
        std::cout << value * i / len << " "; // expensive
    }
    std::cout << std::endl;
}

// FIXME
void fastLerp(int len, int value)
{
    int q = value / len; // podíl (quotient)
    int m = value % len; // dá se nějak využít modulo?
    int sum = 0;
    for (int i = 0; i <= len; ++i)
    {
        std::cout << sum << " ";
        sum += q;
        // ?
    }
    std::cout << std::endl;
}

int main()
{
    naiveLerp(17, -27);
    fastLerp(17, -27);
    return 0;
}

_________________
www.FRANTICWARE.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Ladis



Založen: 18. 09. 2007
Příspěvky: 1508
Bydliště: u Prahy

PříspěvekZaslal: 10. leden 2022, 20:34:36    Předmět: Odpovědět s citátem

Můžeš optimalizovat výpočet nad tímto. Např. ve 3D se dá interpolace nahradit obyčejnými additions (víš odkud kam jdeš, tak si spočítáš jen přírůstky - samozřejmě s nějakými bity navíc pro přesnost).
_________________
Award-winning game developer
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
frca



Založen: 28. 07. 2007
Příspěvky: 1498

PříspěvekZaslal: 10. leden 2022, 20:57:32    Předmět: Odpovědět s citátem

Jasně, víc bitů, to mě napadlo. Ale já doufám v nějaký způsob, jak dotlačit fastLerp, aby měl identický výsledek jako naiveLerp.
_________________
www.FRANTICWARE.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
mar



Založen: 16. 06. 2012
Příspěvky: 577

PříspěvekZaslal: 11. leden 2022, 08:00:04    Předmět: Re: Celočíselná interpolace Odpovědět s citátem

záleží, jakých hodnot může value nabývat. s fixed pointem bys to měl sčítání plus shift

pokud bys šel do assembly, dalo by se udělat něco víc fancy, kdysi se používal takový trik, že ten fixed point byl uložený naopak, tzn.
fractional part byla uložená ve vyšších bitech, pak by ti stačilo třeba toto
kód:

add eax, ebx
adc eax, 0

tzn. pomocí carry vyteče fract part, kterou v dalším kroku přičteš s celočíselné
a v ax bys pak měl celočíselnou část, řekněme fp16:16
|fract_part 16 bits|int_part 16 bits|
a pokud by se ti povedlo uvnitř smyčky zachovat carry flag, tak ho stačí na začátku smyčky vymazat a pak se to smrskne ja jednu instrukci
kód:

adc eax, ebx


samozřejmě zajímavější je tento způsob o to víc, když interpoluješ dvě hodnoty, třeba uv pro texturování, se zachováním carry flagu:
|v_frac|u_int|
|u_frac|v_int|
kód:

adc eax, ecx
adc ebx, edx


cool, ne? Smile
EDIT: samozřejmě toto ale předpokládá, že ti celočíselná část nevyteče do fractional Smile takže s těmi negativními hodnotami by to bylo trochu tricky... i když pokud by počet pixelů byl relativně malý, tak ta chyba by asi mohla být přijatelná
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
frca



Založen: 28. 07. 2007
Příspěvky: 1498

PříspěvekZaslal: 11. leden 2022, 08:54:03    Předmět: Odpovědět s citátem

Hodně zajímavé, díky Idea
S tím UV jsem to ale asi nepochopil...
_________________
www.FRANTICWARE.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
mar



Založen: 16. 06. 2012
Příspěvky: 577

PříspěvekZaslal: 11. leden 2022, 09:21:56    Předmět: Odpovědět s citátem

no něco takového třeba:

kód:


   ...init...
   mov edx, [texture_ptr]
   // clear carry
   and edx,edx
loop_start:
   mov dl, al
   mov dh, bl
   adc eax, ebp
   // texture fetch
   mov dl, [edx]
   adc ebx, esi
   // buffer store
   mov [edi], dl
   inc edi
   dec ecx
   jnz loop_start

a samozřejmě toto je naivní smyčka, která by se dala rozrolovat/přeskládat/zjednodušit apod.

tady se předpokládá textura 256x256, pointer zarovnaný na 64kb
prostě to rozeskládání je důležité, aby přetékal u_frac to u_int a opačně, jak jsem psal
navíc můžeš v tomto konkrétním případě klidně FP8:24 pro lepší přesnost

EDIT: těch registrů je fakt málo Smile pokud bys během toho zakázal přerušení, dal by se využít i esp třeba jako čítač a uvolnilo by to ecx na něco zajímavého třeba Very Happy jako na temp akumulátor a v rozrolované smyče by pak uložení mohlo být třeba mov [edi+nn], cx, za předpokladu, že jedeš horizontálně, možností je spousta prostě

ještě jedna drobnost: add ničí carry, ale pak tu je lea, kterou se dá fejkovat třeba add reg,4 => lea reg, [reg+4] apod.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
OndraSej



Založen: 28. 07. 2007
Příspěvky: 765
Bydliště: Brandýs nad Labem

PříspěvekZaslal: 12. leden 2022, 00:41:14    Předmět: Odpovědět s citátem

Pokud bys chtěl zůstat ve floatech, můžeš zkusit nějakou variantu Kahanova algoritmu: https://en.wikipedia.org/wiki/Kahan_summation_algorithm
_________________
http://trionteam.net
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Zobrazit příspěvky z předchozích:   
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> C / C++ Časy uváděny v GMT + 1 hodina
Strana 1 z 1

 
Přejdi na:  
Nemůžete odesílat nové téma do tohoto fóra
Nemůžete odpovídat na témata v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete hlasovat v tomto fóru


Powered by phpBB © 2001, 2005 phpBB Group


Vzhled udelal powermac
Styl "vykraden" z phpBB stylu MonkiDream - upraveno by rezna