dev.gamez.lv Forum Index dev.gamez.lv
Latvian Game Developers Community
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 

Vector - Voxel koliizija

 
dev.gamez.lv Forum Index -> Programmēšana
View previous topic :: View next topic  
Author Message
Storm



Joined: 11 Apr 2006
Posts: 742

PostPosted: Tue Jan 20, 2009 12:08 am    Post subject: Vector - Voxel koliizija

Meeginu izsecinaat no sii papiira un uztaisiit implementaaciju C# algoritmam, ideja vienkaarsa - mums ir nogrieznis (NE ar integer veertiibaam) un 2D/3D (saja gadijuma 2D) laukums ar iespejamam blokacijam un vajag atrast visus laucinjus ko noteiktais nogieznis apciemo, ieverojot secibu. (voxel traversal)

taisu pec papiira, kuraa gan ar reaalu implementaaciju skopojaas
www.cse.yorku.ca/~amana/research/grid.pdf

Sobriid man ir kods, kas itkaa pat dara kaut ko uz to pusi, bet dara diivainiibas kad stars sanaak pa vienu taisnu liiniju cauri laucinjiem un pec nenosakamiem principiem medz kadu laucinju panemt greizi...
Code:

public bool Trace(Vector2 rayBegin, Vector2 rayEnd)
{
    int X = Convert.ToInt32(rayBegin.X - 0.5f);
    int Y = Convert.ToInt32(rayBegin.Y - 0.5f);

    Vector2 ray = new Vector2(rayEnd.X - rayBegin.X, rayEnd.Y - rayBegin.Y);
    ray.Normalize();

    int stepX;
    int stepY;
    float tMaxX;
    float tMaxY;
    float tDeltaX;
    float tDeltaY;

    if (ray.X < 0)
    {
        stepX = -1;
        tDeltaX = 2.0f / -ray.X;
        tMaxX = (rayBegin.X - X) * tDeltaX;
    }
    else
    {
        stepX = 1;
        tDeltaX = 2.0f / ray.X;
        tMaxX = (X + 1.0f - rayBegin.X) * tDeltaX;
    }

    if (ray.Y < 0)
    {
        stepY = -1;
        tDeltaY = 2.0f / -ray.Y;
        tMaxY = (rayBegin.Y - Y) * tDeltaY;
    }
    else
    {
        stepY = 1;
        tDeltaY = 2.0f / ray.Y;
        tMaxY = (X + 1.0f - rayBegin.Y) * tDeltaY;
    }


    int curX = X;
    int curY = Y;

    Point endTile = new Point(Convert.ToInt32(rayEnd.X - 0.5f), Convert.ToInt32(rayEnd.Y - 0.5f));


    while (!(curX == endTile.X && curY == endTile.Y))
    {
        if (tMaxX < tMaxY)
        {
            curX += stepX;

            if (IsBlocked(curX, curY))
            {
                PLOT(Color.Red, curX, curY);
                //return false;
            }
            else
                PLOT(Color.Green, curX, curY);

            tMaxX += tDeltaX;
        }
        else
        {
            curY += stepY;

            if (IsBlocked(curX, curY))
            {
                PLOT(Color.Red, curX, curY);
                //return false;
            }
            else
                PLOT(Color.Green, curX, curY);

            tMaxY += tDeltaY;
        }
    }

    return true;
}




EDIT:

Izdevaas izveidot lai straadaa pareizi visos gadiijumos tikai viena lieta ->

Code:

while (!(curX == endTile.X && curY == endTile.Y))


sitais conditionals iisti neder jo dazados gadijumos kad rayEnd % 1.0f == 0 iestajas muzigais cikls... Varbut ir kads atrs veids ka noskaidrot to beigsanas bridi savadak, nevis salidzinot ar endTile? Apmekleto laucinju skaits varbut?
_________________
Izraadaas ka dazu dev.gamez.lv lietotaaju absurdaa ignorance meedz eksisteet arii augstaakas paakaapees : http://www.gamedev.net/community/forums/topic.asp?topic_id=411552
Back to top
View user's profile
bubu
Indago Uzvarētājs
Indago Uzvarētājs


Joined: 23 Mar 2004
Posts: 3223
Location: Riga

PostPosted: Tue Jan 20, 2009 2:04 am    Post subject:

Vispirms komentārs no C# performances viedokļa - rakstīt int X = Convert.ToInt32(floats) ir drausmīgi. Paskaties ar reflektoru, kas tur apakšā darās! Daudz performancīgāk un īsāk ir rakstīt kā C kodā: int X = (int)floats;

Atpakaļ pie tēmas - šitam algoritmam imho jau ar vokseļiem maz sakara (voxel traversal?). Vokseļi, imho, tie būtu, ja tev tas būtu jādara trijās dimensijās (kur rūtiņa ir x,y,z, nevis tikai x,y). Tad tā būtu vokesļu apstaigšāna. Bet tagad tas tev ir parastais Bresenham līnijas rasterizēšans algoritms, kuram korektu implementāciju netā atrast ir ļoti viegli, piemēram, rekur: http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Generalization (jā - tas darbojas arī ar float sākum/beigu-koordinātēm, aizstāj tik tos int ar float).

Edit:
Storm wrote:
rayEnd % 1.0f == 0

kas tā par operāciju?
Back to top
View user's profile Send e-mail
Storm



Joined: 11 Apr 2006
Posts: 742

PostPosted: Tue Jan 20, 2009 3:05 am    Post subject:

Nu nekaa!

X = Convert.ToInt32(floats) != int X = (int)floats; (!!!)

ideja tam Convert.ToInt32() ir apaljosana jo man vajag floor no taa floata dabuut (ko castosana ari dara, bet man vienaa vietaa bija vajadzeejis round-up - ko var izdariit, jaa, arii ar castu ( X = (int)floats + 0.999999f), itkaa es nezinaatu ka casts bus aatraaks...
Bet saja gadijuma tas viss ir bullshit, neko es tur nebiju pat saacis optimizeet low level liimenii, tikai algoritmus.

bubu wrote:

Storm wrote:
rayEnd % 1.0f == 0

kas tā par operāciju?


modf, bet tas vairs nav svariigi Very Happy Reaali bija taa ka ja stars beidzaas kaadaas koordinaataas uz 0 robezas piem floats 12.0 tad iestaajaas muuziigais cikls, atrisinaajums seko taalaak, sanaak pat aatraak (viens ifs ciklaa, tas pats saliidzina ar 0 + 2 prieks Abs, ja netiek izmantota abs instrukcija procesoraa)

Par liniju zimesanu te ir maz sakara -> tu domaa ka vinjas iziet cauri visiem laucinjiem, a nekaa. Man jau bija ne tikai piemineetais, bet arii Xiaolin Wu variants Laughing

izdomaaju ar distances formulu var izreekinaat
Code:


int CNT = (Math.Abs(-(int)rayEnd.X + X) + Math.Abs(-(int)rayEnd.Y + Y));

while (CNT > 0)
{
     CNT -= 1;
     ...
}

_________________
Izraadaas ka dazu dev.gamez.lv lietotaaju absurdaa ignorance meedz eksisteet arii augstaakas paakaapees : http://www.gamedev.net/community/forums/topic.asp?topic_id=411552
Back to top
View user's profile
bubu
Indago Uzvarētājs
Indago Uzvarētājs


Joined: 23 Mar 2004
Posts: 3223
Location: Riga

PostPosted: Tue Jan 20, 2009 9:22 am    Post subject:

Storm wrote:
Nu nekaa!

X = Convert.ToInt32(floats) != int X = (int)floats; (!!!)

Nē, nu protams, ja tev vajag precīzi dabūt vienādu rezultātu, tad raksti: int X = (int)(floats + 0.5f);
Imho vienalga ātrāk būs. ToInt32 darba vispirms castu uz double un tad vēl visādas mahinācijas ar if'iem, apaļošanām un vēl sazin ko tur.. Es tik to pēc būtības tev teicu - ka labāk lietot castošanu nevis ToInt32. Vienk ja tu tādu ToInt32 lieto vienmēr visā savā kodā, sakot - vēlāk mainīšu atpakaļ, tad īsti neredzu jēgu.. pēc tam veltīt milzums laika iet cauri visam kodam un "optimizēt" to. Nav prātīgāk rakstīt uzreizi kā vajag?

Storm wrote:
Par liniju zimesanu te ir maz sakara -> tu domaa ka vinjas iziet cauri visiem laucinjiem, a nekaa. Man jau bija ne tikai piemineetais, bet arii Xiaolin Wu variants :lol:

Nu kā maz sakara? Tev ir rūtiņas X-Y plaknē, un nogrieznis to rA un rB koordināti. Un tev jāapstaigā tās rūtiņas, kuras nogrieznis krusto sākot no rA punkta līdz rB punktam, pareizi sapratu? Tad pasaki kā gan tas nav līnijas rasterizēšanas algoritms? Reku bilde uzskatāmībai (no mana ielinkotā wikipēdijas linka):

Tas neizskatās pēc tava rA-rB nogriežņa un tā krustotiem lauciņiem X-Y plaknē? Bilde neizskatās ekvivalenta "Figure 1" tavā ielinkotajā pdf'ā?

Ar Wu variantu gan te nav nekāda sakara toč. Tas domāts antialiasētas līnijas rasterziēšanai, bet tev vajag viennozīmīgi apmeklēt konkrētus lauciņus nogriežņa ceļā, nevis ar kautkādus % nogriežņa apkārtnē.

Un ko nozīmē "tu domaa ka vinjas iziet cauri visiem laucinjiem, a nekaa"? Kā tad tas viss iziet? Bildi uzskatāmībai var dabūt, ja jau tev neder tā bilde, ko es esmu ielicis?

Storm wrote:
modf, bet tas vairs nav svariigi :D

doh, šitais jau sāk atgādināt dažu lapu citu foruma useri, kurš patvaļīgi izdomā savus terminus :) Tik tu izdomā savas operacijas - fmodf ar vektoru un floatu... Laiks iegādāties ebayā kristāla bumbu [atkal] :)
Back to top
View user's profile Send e-mail
Storm



Joined: 11 Apr 2006
Posts: 742

PostPosted: Tue Jan 20, 2009 5:10 pm    Post subject:

Xiaolin Wu izdomaaja gan antialiased liinijas gan ieveeroja paternu ziimeejot liinijas taadaa veidaa ieguustot aatraaku ziimeesanas algoritmu -> (lapas beigaas ) http://www.cs.unc.edu/~mcmillan/comp136/Lecture6/Lines.html

Un kas attiecas uz Bresenham - vins neapmeklee visus laucinjus ko apmeklee noteiktais stars, Uzziimee liiniju piemeeram no [0;0] lidz [4;2]


_________________
Izraadaas ka dazu dev.gamez.lv lietotaaju absurdaa ignorance meedz eksisteet arii augstaakas paakaapees : http://www.gamedev.net/community/forums/topic.asp?topic_id=411552
Back to top
View user's profile
snake5
Indago dalībnieks
Indago dalībnieks


Joined: 27 Jun 2007
Posts: 2590

PostPosted: Tue Jan 20, 2009 5:19 pm    Post subject:

Quote:

(!(curX == endTile.X && curY == endTile.Y))

Neder checkot vai esošās tile pozīcijas projekcija uz līnijas nedod rezultātā skaitli, kurš lielāks par līnijas garumu?
Back to top
View user's profile Visit poster's website
Storm



Joined: 11 Apr 2006
Posts: 742

PostPosted: Tue Jan 20, 2009 5:22 pm    Post subject:

Snake, nedomaaju ka tas buus aatraaks par jau esoso izdomaajumu par laucinju skaitu. (skat par to CNT ieprieks)
_________________
Izraadaas ka dazu dev.gamez.lv lietotaaju absurdaa ignorance meedz eksisteet arii augstaakas paakaapees : http://www.gamedev.net/community/forums/topic.asp?topic_id=411552
Back to top
View user's profile
snake5
Indago dalībnieks
Indago dalībnieks


Joined: 27 Jun 2007
Posts: 2590

PostPosted: Tue Jan 20, 2009 5:29 pm    Post subject:

Hmm
ar http://img183.imageshack.us/img183/8056/traverseyt8.png
CNT = abs( -5 + 1 ) + abs( -3 + 1 ) = 4 + 2 = 6
attēlā redzams, ka CNT ir 7

Mana ideja vismaz strādā. Wink
Back to top
View user's profile Visit poster's website
Storm



Joined: 11 Apr 2006
Posts: 742

PostPosted: Tue Jan 20, 2009 5:36 pm    Post subject:

snake5 wrote:
Hmm
ar http://img183.imageshack.us/img183/8056/traverseyt8.png
CNT = abs( -5 + 1 ) + abs( -3 + 1 ) = 4 + 2 = 6
attēlā redzams, ka CNT ir 7

Mana ideja vismaz strādā. Wink


Tas tapec ka ateelaa pirmais laucins netiek paarbaudiits ciklaa, lol. Taka vari nesatraukties, mana ideja straadaa un ir aatraaka par taveejo Mr. Green Bet vispaar ja nav slinkums iepostee kaadu kodinju ko tu tiesi domaaji ar to savu projekciju jo man tas izklausaas absaubaami Very Happy
_________________
Izraadaas ka dazu dev.gamez.lv lietotaaju absurdaa ignorance meedz eksisteet arii augstaakas paakaapees : http://www.gamedev.net/community/forums/topic.asp?topic_id=411552
Back to top
View user's profile
bubu
Indago Uzvarētājs
Indago Uzvarētājs


Joined: 23 Mar 2004
Posts: 3223
Location: Riga

PostPosted: Tue Jan 20, 2009 6:06 pm    Post subject:

Storm wrote:
Un kas attiecas uz Bresenham - vins neapmeklee visus laucinjus ko apmeklee noteiktais stars, Uzziimee liiniju piemeeram no [0;0] lidz [4;2]

Ah nu ja, tev vajadzīgas līnijas 8-connected veidā. ok, tagad sapratu. Mana kļūda.
(tam arī eksistē modificēts brezanhēma algoritms, bet nu whatever - tev tas nav vairs aktuāli :)
Back to top
View user's profile Send e-mail
Display posts from previous:   
dev.gamez.lv Forum Index -> Programmēšana All times are GMT + 2 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group