[flash] 3d engine; sorteren

[Verwijderd]

Ik ben bezig met een 3d engine in flash; nu gaat het positioneren goed, objecten krijgen een x,y,z waarde en aan de hand hiervan word de positie op het scherm bepaald. Nu is het probleem echter dat de sortering nog niet helemaal lekker loop; na een zoektoch op het net (zonder echt resultaat) bedacht ik zelf de volgende functie ... in het kort loopt hij alle objecten bijlangs, kijkt naar hun afstand tot het "oog" en zet deze in een array. De volgorde van de array word als volgt bepaald: de eerste waarde word in een nieuwe array gezet, vervolgens word gekeken voor elke waarde vergeleken met de waarde uit de array om zo de juiste volgeorde te bepalen, op deze manier komt 't object met de kleinste afstand waarde als eerste, en de hoogste als laatst. Zo kan ik vervolgens de nieuwe "volgorde" array doorlopen en nieuwe levels toekennen aan de objecten ... helaas wertk dit niet helemaal fijn.

code:

function zSorteren () {
    volgorde = new Array ();
    for (i=1;i<diepteObject;i++) {
        var pushed = false;
        if (i==1) {
            volgorde.push(i);
        }
        else {
            var lengte = volgorde.length;
            for (j=0;j<lengte;j++) {
                if ((this["object" + i].afstand < this["object" + volgorde[j]].afstand)
&& (Number(pushed) == 0) && (j < lengte)) {
                    volgorde.splice(j-1, 0, i);
                    pushed = true;
                }
                else if (Number(pushed) == 0) {
                    volgorde.push (i);
                    pushed = true;
                }
            }
        }
    }
    for (i=0;i<volgorde.length;i++) {
        this["object" + volgorde[i]].swapDepths (i + 1);
        trace (this["object" + volgorde[i]].getDepth());
    }
}

Overigens ben ik benieuwd dus waarom het niet werkt, maar ook of deze methode aan te raden is qua snelheid ed. Ik heb artikelen gevonden waarin verschillende methodes werden uitgelicht, zoals Quick Sort, the Bubble Sort, Selection Sort, the Merge Sort, the Heap Sort, the Binary Sort, en the Radix Sort. Nu is mijn vraag welke het beste is voor een 3d engine, of dat ik gewoon door kan gaan met mijn eigen?

[Bosmonster]

Zet nog eens wat breakjes in die if() wil je Maakt voor de code niet uit maar maakt je post een stuk leesbaarder.

[Verwijderd]

Ik zou toch een ander "zoek" algoritme aanraden voor de juist plaats in de array: Stel dat je N objecten moet sorteren duurt dat bij jou gemiddeld N^2 cycles (en da's best veel...)
Met een binary search duurt het maar N log N cycles. EN dat scheelt een slok op een borrel!

Hoe werkt een binary search: Begin niet vooraan in de array met zoeken, maar kijk naar het middelste element. Is dat te groot, kies dan het midden van de onderste helft, anders in het midden van de bovenste helft. Daarna dit proces herhalen.
Stel dat je iets in een array van 1.000.000 elementen moet zoeken, duurt dat met linear search gemiddeld 500.000 slagen, met binary search slechts 20(!!!).

[Verwijderd]

Ik zie dat mijn methode voor kleine arrays genoeg is, echter een 3d engine krijgt een groot aantal punten waar vlakken tussen getrokken moet worden en word daarom als snel te traag (helemaal wanneer de sort achter elkaar uitgveoerd moet wordne). Ik heb ook een voorbeeld van de quicksort methode gevonden ...
http://www.cs.usask.ca/re...s/sorting/quick/2-4.shtml

welke is aan te raden? binary of quicksort?

[Ericston]

Het antwoord is simpel: je moet datgene gebruiken wat het snelst is in Flash.
Hoe je uitvindt wat het snelste algoritme is zeg je? Twee algoritmes implementeren en benchmarken moet toch wel binnen afzienbare tijd te doen zijn?
Ik zou het zo niet weten in ieder geval.

[Verwijderd]

Snelst sorten in flash, inderdaad.....deze routine gebruikte ik als laatst.
Even wat code uit een oude source getrokken;

code:

movieclip.prototype.compareNumbers = function ( a, b){
    a = Number(a[2]);
    b = Number(b[2]);
                return(-((a > b) - (a < b)));
}

array.prototype.numsort = function(){
    this.sort(compareNumbers);
}

Het stukje waar a[2] en b[2] zit; hij gaat ervanuit dat je een multidimensionaal array gebruikt, en sort dus nu in de 2de dim op de 3de waarde...waar normaal je z point zit. Als je met poly's gaat werken zou je natuurlijk het normaal punt kunnen berekenen, en deze in een 4de positie in het array zetten.


Edit: dan zou je misschien nog kunnen kijken wat sneller is; de vorige of deze:
zou kunnen zijn dat array lookups in dit geval zo sneller zijn....

code:

movieclip.prototype.compareNumbers = function ( a, b){
                return(-((a[2] > b[2]) - (a[2] < b[2])));
}

array.prototype.numsort = function(){
    this.sort(compareNumbers);
}

[Verwijderd]

[quote]Verwijderd schreef op 24 oktober 2002 @ 09:59:
Ik zou toch een ander "zoek" algoritme aanraden voor de juist plaats in de array: Stel dat je N objecten moet sorteren duurt dat bij jou gemiddeld N^2 cycles (en da's best veel...)
Met een binary search duurt het maar N log N cycles. EN dat scheelt een slok op een borrel!

helaas gaat dit niet altijd op! in het ongunstigste geval duurt deze sorteer methode zelfs langer.
probeer eens te analyseren of je niet groepen objecten in 'boundingboxen' kunt onder brengen. en deze vervolgens te sorteren en vervolgens de polygonen binnen de afzonderlijke boudingboxen.
verder zou ik zeker 'backface culling' toepassen; wat je niet ziet hoef je ook niet te renderen.

[Verwijderd]

backface culling komt ook zeker; maar goed, laat ik eerst maar eens de sortering goed krijgen ... eerst moeten alle standaard functies zoals plaatsen van object, sortering, rotatie, bewegen etc. in orde zijn voordat ik aan dit soort dingen begin, en de sortering is dit nu het enige wat nog niet lekker loopt

[Verwijderd]

/me fronst en kijkt even naar zijn vorige post, en vraagt zich af of die al geprobeerd is?

Onderstaande benchmark even gedaan; gemiddeld 700ms op een PIII 1Ghz, maar op 500 punten zal je toch nooit uitkomen....40 als max is realistischer..

code:

movieclip.prototype.compareNumbers = function ( a, b){
    return(-((a[2] > b[2]) - (a[2] < b[2])));
}

array.prototype.numsort = function(){
    this.sort(compareNumbers);
}

testarr = new Array();
for(n = 0; n<500; n++){
    testarr[n] = new Array(random(100), random(100), random(100));
}

starttime=getTimer();
testarr.numsort();
totaltime = getTimer();
trace(totaltime);

Edit: de 2de bench met 40 punten toonde gemiddeld 60ms. (Houd er rekening mee dat dit reeel in je flash waarschijnlijk tot een echte tijd van 30/20ms kan worden gereduceerd) vanwegen de bench Methode is de meting niet helemaal accuraat.

[ Voor 0% gewijzigd door Verwijderd op 24-10-2002 11:53 . Reden: nog een bench gedaan ]

[Verwijderd]

Verwijderd schreef op 24 oktober 2002 @ 11:50:

testarr = new Array();
for(n = 0; n<500; n++){
testarr[n] = new Array(random(100), random(100), random(100));
}

als we toch op de ms gaan bezuiningen....

testarr = new Array();
for(n = 500; --n>=0;){
testarr[n] = new Array(random(100), random(100), random(100));
}

[Verwijderd]

Aangezien dat geen deel is van het gedeelte wat gebenched is niet geoptimized.
try this:

code:

n=500;
while(n--){
testarr[n] = new Array(random(100), random(100), random(100));
}

[NaliXL]

Hmm, je wilt dus eigenlijk hidden surface removal doen o.i.d.? Dan zou ik eens gaan kijken naar bijvoorbeeld http://www.gamedev.net/reference/articles/article414.asp . Op www.gamedev.net , www.gametutorials.com en www.gamasutra.com zul je waarschijnlijk nog veel meer kunnen vinden. Zou dat niet het geval zijn, dan zou dit je wel moeten helpen, niet? Succes!

[Verwijderd]

Ik denk dat het tekenen van vlakken nu de grootste bottleneck is, je kan razendsnel
10.000 punten z-sorteeren, maar als je al vetragingen krijgt van het tekenen van 100 vlakken, tja. Ok.

hier wat oude flash5 source met oa. quicksort en een 'simpele' backface culling
http://www.xs4all.nl/~elout/flash/
(maar deze kende je al waarschijnlijk)


Verder ben ik nu ook weer bezig in flashMX; composities met 6 'vlakken'.
http://www.xs4all.nl/~elout/10kub/
(-mouse/arrow keys-switch anims-)

[Janoz]

Mag ik trouwens vragen hoe je je punten transformeerd? Als je hier namelijk geen matrices voor gebruikt dan is er op dat vlak ook nog veel winst te halen.

Heb zelf deze een keertje in elkaar geklust in flash 5 om te kijken wat de mogenlijkheden waren. Omdat een kubus convex is en ik gebruik maak van backface removal hoef ik bij deze niet te sorteren . Deze draait ook op mijn PII266 vloeiend . Ben er trouwens mee gestopt toen ik doorhad dat de skew niet zo werkte als ik had gehoopt (de mc bleef niet even hoog). Omdat ik daardoor per driehoek een extra tangens uit zou moeten rekenen had ik er geen zin meer in .

[ Voor 0% gewijzigd door Janoz op 25-10-2002 10:52 . Reden: hmm ... mijn flash5 kubus is aanzienlijk sneller dan die van mijn bovenbuurman :) ]

[Verwijderd]

Topic kick ^dit is leuk...

Maar idd, ipv zsorten kan je idd beter backface culling gaan doen, aangezien een framedraw meestal langer kost dan alle as die je hebt.

[Verwijderd]

een kubus renderen omdat het rap gaat en je geen backfade culling/hidden surface removal nodig hebt lijkt me niet de ideale benadering van de vooruitgang

[Verwijderd]

mijn source tot nu toe staat op : http://www2.hku.nl/~patrick/experimental ... ik ben nu bezig met het roteren van de objecten. Zoals je ziet worden er nog geen vlakken getekend, enkel alleen objecten. De rotatie ging de vorige keer mis omdat er afrondingsfouten werden gemaakt en daardoor alle objecten langzaam naar elkaar toekwamen. Ik probeer dit nu op te lossen door alle startwaarden in een array op te slaan, en van hiervanuit de nieuwe posities te berekenen (zie ook hoe het bewegen in zijn werk gaat)

[ Voor 0% gewijzigd door Verwijderd op 25-10-2002 13:59 . Reden: 404: URL aangepast ]

[Verwijderd]

Verwijderd schreef op 25 oktober 2002 @ 13:53:
een kubus renderen omdat het rap gaat en je geen backfade culling/hidden surface removal nodig hebt lijkt me niet de ideale benadering van de vooruitgang

Huh????

[Verwijderd]

Ja ik moest ook 5x de zin lezen voordat ik door had wat er nou precies stond

[oh,when?]

Janoz schreef op 25 oktober 2002 @ 10:50:
Mag ik trouwens vragen hoe je je punten transformeerd? Als je hier namelijk geen matrices voor gebruikt dan is er op dat vlak ook nog veel winst te halen.

Heb zelf deze een keertje in elkaar geklust in flash 5 om te kijken wat de mogenlijkheden waren.

Janoz wijzigde dit bericht 25-10-2002 10:52: hmm ... mijn flash5 kubus is aanzienlijk sneller dan die van mijn bovenbuurman

gaan we nu allemaal onze 3d kubus posten, en dan kijken wie de snelste heeft want ik heb er hier nog een staan, en daarin zit een hele raw dirty zsort ( beetje moeilijk ontleden aangezien alles op 1 regel staat. ) source is te downloaden.

Ook leuk, dit dingetje is gemaakt nog in Flash 4, om 3d te simuleren in 2d omgeving

[cjs]

oh,when? schreef op 25 oktober 2002 @ 14:42:
[...]

gaan we nu allemaal onze 3d kubus posten, en dan kijken wie de snelste heeft

[spam] kubus, source-code [/spam]

[Verwijderd]

janoz> yes matrixes gebruik ik, en over die tangens, het is een beetje van de oude school om alles van te voren te pre-calculaten als het kan, ik gebruik ik nu nog steeds verschillende arrays voor sinus/cosinus, of voor zoiets als het bekende random().

Maar ik merk nu de laatste tijd, de bottle nek zit hem in tekenen, ik kan tienduizenden getallen supernel berekenen, of het nu flash/c of java is. maar het tekenen daarvan (c/opengl),lukt wel in 30 fps; in java gaat dat tig slomer, en ga eens 10.000 vlakken tekenen in flash per seconden (het is wel lekker anti-aliased. maar alles loopt sloom tot vast)

btop> backface culling is leuk, maar het werkt beter als je er ook painters-algo er tevens over gooit. Het is niet het een of het ander maar meer beide. Stel je hebt een vlak ver achter, maar toch in beeld, welke laat je dan toch als eerste zien.

cjs> als je source geeft noem ik het geen spam
(heb die source nog niet gezien btw)


kort verklaringen voor mensen die diverse termen nog niet kennen;

painters-algoritme / z-buffering/sorting;
voor elk 3D punt of vlak; probeer je de gemiddelde z-waarde te vinden, en probeer alles zo te sorteren,
dat dingen die ver weg staan als eerste getekend worden, daarna ga je dingen tekenen die dichterbij staan.
Er zijn diverse sorteer routine`s om dit snel voor je uit te rekenen, oa. bubble sort of quick sort.

Backface culling;
Iets ingewikkelder, maar daar is een mooie wiskundige formule voor; dit heeft met de vector/normaal van het vlak te maken, kort door de bocht, als deze van je af staat, zoals een achterkant van een kubus, dan hoef je het niet te tekenen, maar de voorkant weer wel. (correct me if I`m wrong.)

edit:

beetje offtopic, maar ik kan het niet laten; en al is het dan in java van tig jaar terug;
http://www.xs4all.nl/~elout/buf/buffie02.html
(click mouse for next effect)
source:http://www.xs4all.nl/~elout/buf/buffie02.java

een beetje 'dirty' edge-filler/z-buffer routine;
http://www.xs4all.nl/~elout/buf/buffie04.html
source:http://www.xs4all.nl/~elout/buf/buffie04.java
(puur voor de liefhebbers

edit:

- part 2 - en deze dingen komen ook weer terug nu ik ook in c/openGL zit te coden

[Verwijderd]

Verwijderd schreef op 26 oktober 2002 @ 01:24:
Backface culling;
Iets ingewikkelder, maar daar is een mooie wiskundige formule voor; dit heeft met de vector/normaal van het vlak te maken, kort door de bocht, als deze van je af staat, zoals een achterkant van een kubus, dan hoef je het niet te tekenen, maar de voorkant weer wel. (correct me if I`m wrong.)

de normaal staat doorgaans loodrecht op het oppervlak - tbv. phong shading wil de normaal nog wel eens 'minder loodrecht' op een oppervlak staan, maar dit even terzijde - waardoor je deze normaal kunt gebruiken om te kijken of een polygoon zichtbaar dan wel niet-zichtbaar is. niet-zichtbaar wil zeggen dat je naar de achterkant van de polygoon zit te kijken. bij gesloten objecten zoals een kubus wijzen de normalen van elke zijde naar buiten toe.
de normaal van de zijden die voor de toeschouwer aan de achterzijde zitten wijst dus het scherm in. wanneer de hoek met de toeschouwer en de normaal groter is als/dan negentig graden is de zijde niet zichtbaar en derhalve is het ook niet relevenant deze zijde voor het renderproces te gebruiken.
ook daar zijn weer uitzonderingen op te bedenken maar dan komt je al snel in het 'ruimtevaart technologie' domein terecht.