Algoritme sneller maken

[NickThissen]

Ik probeer een fysisch proces te simuleren met behulp van een heel erg simpel model. Helaas is mijn simpele aanpak net niet snel genoeg, het is prima om een aantal keer als test te draaien, maar het doel is uiteindelijk om de uitkomst van de simulatie te bekijken als functie van een van de parameters, welke ik over een grote range wil veranderen, en dat gaat veel te lang duren. Ik zou dus graag het algoritme verbeteren als dat mogelijk is om het sneller te maken.

Ik ben begonnen in Python maar heb het algoritme uiteindelijk over gezet naar C# wat toch wel VEEL sneller was. Misschien dat ik nog naar C++ ofzo kan overstappen maar ik denk dat die stap me veel minder brengt en dat het algoritme zelf nu de bottleneck is.


Het model is heel simpel: ik heb een grid van 1000x1000 cells wat een bepaald materiaal voorstelt (dit getal staat redelijk vast, ik wil niet veel kleiner en veel groter is niet nodig). Op dit materiaal ga ik één voor één een groot aantal "impacts" simuleren, die allemaal een krater achterlaten van een vaste grootte. Ik genereer dus een groot aantal (x, y) coordinaten, en voor elk van die coordinaten teken ik op de grid een circelvormige impact krater met een straal van bijvoorbeeld 20 cellen.

Uiteindelijk wil ik kijken naar de (oppervlakte) fractie van de krater (aantal cellen die in een krater liggen gedeeld door de rest).


Het meest voor de hand liggende algoritme dat ik kon bedenken was als volgt (pseudo code):

code:

// Straal van krater
radius = 20

// Grid van 1000x1000 cellen
// Cell waarde 0 is geen krater, waarde 1 is krater
cells = int[1000, 1000]

// Bijvoorbeeld 10000 impacts
for i = 0 to 10000
{
    // Kies random locatie
    x = random(0, 1000)
    y = random(0, 1000)
    
    // Definieer vierkant rondom impact punt waar binnen de krater moet liggen
    minX = x - radius
    maxX = x + radius
    minY = y - radius
    maxY = y + radius
    
    // Check elk punt of het binnen de krater ligt
    for xi = minX to maxX
    {
        for yi = minY to maxY
        {
            // Is de afstand van dit punt tot impact punt < radius?
            distance = sqrt((x-xi)^2 + (y-yi)^2)
            if (distance <= radius)
            {
                // Dit punt ligt binnen krater
                cells[xi, yi] = 1
            }
        }
    }
}

Voor elk (random) impact punt doe ik dus een loop door elke cell binnen de maximale 'bounding box' van de krater cirkel. Voor elke cell check ik de afstand tot het impact punt en als die kleiner of gelijk aan de gewenste straal is dan ligt het punt dus binnen de krater. In deze pseudo code negeer ik even rand condities waarbij de krater half buiten de grid valt (ik gebruik een 'wrap around' om de grid in principe oneindig te laten zijn, alles wat er links buiten valt komt rechts terug).


Helaas is dit dus langzaam, waarschijnlijk door de dubbele loop (voor elk impact punt moet hij weer opnieuw door alle cells loopen die in de buurt van het impact punt liggen). Hoe groter de straal van de kraters, hoe langer het duurt uiteraard, en de straal van de krater is nu juist een van de dingen die ik wil varieren, dat is dus niet optimaal.

Ik zie niet zo snel wat ik hier aan kan verbeteren. Eventueel zou ik de wortel weg kunnen laten bij de afstand check (en gewoon radius^2 vergelijken) maar dat maakt zowat geen verschil.


Ik ging op zoek naar oplossingen maar ik weet niet zo goed hoe ik dit moet verwoorden. Toch kwam ik een aantal tips tegen die wel logisch leken: het probleem nu is dat ik elke keer opnieuw door alle cellen in de buurt van het impact punt moet gaan loopen. Het zou veel sneller zijn als elke cell gewoon weet wat zijn buren zijn en dat ik die allemaal tegelijk op 1 kan zetten in plaats van eerst moet checken of ze wel binnen de straal vallen.

De makkelijkste manier om dat te doen is door na het opbouwen van de grid eerst voor elke cell deze loop uit te voeren en die cell te laten weten welke cellen er binnen de straal liggen. Dat was echter niet zo slim bedacht want het enige wat ik daarmee bereik is dat ik het langste gedeelte van de simulatie nu eerst op ELKE cell ga uitvoeren in plaats van op maar 10,000 cellen. Het opbouwen van de grid duurt dus een eeuwigheid (en hij raakt zelfs out of memory), dus dat werkt ook niet echt. Daarnaast zou ik die hele procedure steeds weer opnieuw moeten doorlopen als ik de gewenste straal van de kraters zou veranderen (wat ik dus van plan ben) en schiet ik er nog niks mee op.


Ten slotte heb ik nog bedacht of het parallel te maken was. Misschien is dat wel zo in het speciale geval wat ik nu omschrijf maar de werkelijke simulatie is net wat ingewikkelder, en volgens mij is het belangrijk dat elke impact achter elkaar gebeurt en niet tegelijk (de uitkomst van de impact hangt af van of er al een krater is op dat punt of niet). Dus ik zoek voornamelijk naar een beter algoritme en niet zozeer een parallel algoritme, maar als iemand daar een tip voor heeft dan kan ik daar misschien ook wel wat mee...


Kent iemand een betere manier om de grid op te bouwen zodat elke cell al meteen weet welke cellen er om zich heen liggen binnen de straal die ik wil? Of een andere manier om dit sneller te maken?

[storeman]

Er gebeuren geen hele ingewikkelde dingen, dus ik zou zeggen, snellere hardware eronder en gaan. Wellicht is het ook wat om op een GPU te doen, die moeten hier toch tamelijk goed mee overweg kunnen.

Maar wat bedoel je met "niet snel genoeg". Hoe snel is het nu en wat wil je bereiken? Ik verwacht namelijk niet dat je deze code nog 2 keer zo snel kan krijgen.

Verder zou je eens kunnen kijken wanneer je de gewenste snelheid wel haalt:
- haal de random eens uit de hoofdloop
- haal de distance berekening eens uit de geneste loop

Die twee subloopjes kunnen bijna het probleem niet zijn.

[HuHu]

Je bericht bevat heel veel tekst. Vat ik het zo correct samen: je wilt gevulde cirkels tekenen op een plaatje?

Je zou naar dit algoritme kunnen kijken: Wikipedia: Midpoint circle algorithm

Daarnaast zou je kunnen zoeken naar bestaande "image processing libraries" die deze functionaliteit al bevatten.

Wat is je uiteindelijke doel hiermee? Misschien is er wel een andere oplossing.

[TheDevilOnLine]

Als ik zo kijk dan is de sqrt op regel 27 je grootste vertrager. Doordat de radius van je kraters telkens het zelfde is, kan je van te voren al een lijst definiëren van cellen die beïnvloed worden door de inslag. Je maakt dan een lijst met x-y offsets waar je dan snel overheen kan loop-en. Dit zorgt ervoor dat je de berekening van de afstand maar radius^4 hoeft te doen, ipv radius^4 * aantal impacts. Daarnaast kan je voor cellen die al de waarde 1 hebben de gehele test natuurlijk overslaan.

Daarnaast kan je ook je algorithme aanpassen. Je kan eerst alle inslag posities berekenen en vervolgens over alle cellen heengaan. Per cel kijk je dan (eventueel dmv de lijst met offsets). Zodra je een inslag vindt ga je meteen door met de volgende cell. Bij die cell check je dan als eerste tegen de inslag die invloed had op je vorige cell (aangezien deze het meest waarschijnlijk is om ook invloed op de betreffende cell te hebben). Via deze weg verklein je het aantal tests nog verder.

[Voutloos]

De afstand op 1 as is constant voor de buitenste loop, dus die berekening kan je makkelijk naar de buitenste loop kunnen halen.

Je kan een strictere bounding box bepalen @ 45 graden waarbinnen je niet meer hoeft te rekenen. In je loopje kan je dan kijken of binnen die box, en zo nee, dan pas afstanden berekenen.

Of de bounding box aanpassen zodat je alleen de linkerboven hoek doet en indien een punt er aan voldoet ook het overeenkomende punt in de andere 3 kwarten aanraken.

[ Voor 15% gewijzigd door Voutloos op 11-03-2015 11:52 ]

[WouterKvG]

Als je het daadwerkelijk op een scherm wil laten zien kun je met OpenGL gemakkelijk en snel een rondje op het scherm tekenen met een center en een bepaalde radius.

Daarnaast zijn grote arrays niet heel efficiënt omdat ze veel geheugen innemen. Je zou op zoek kunnen gaan naar een andere datastructuur. Wikipedia: List of data structures Bijvoorbeeld een linkedlist met als startnode de impactlocatie.

[SaphuA]

.

[ Voor 108% gewijzigd door SaphuA op 31-01-2022 14:53 ]

[RobIII]

WouterKvG schreef op woensdag 11 maart 2015 @ 12:06:
Daarnaast zijn grote arrays niet heel efficiënt omdat ze veel geheugen innemen.

Veel efficiënter dan een array krijg je het niet hoor? Je kunt complete 'vlakken' in 1 keer uitmaskeren, bits (un)setten en ga zo maar door. Dat gaat je met een LinkedList e.d. niet lukken.

[HuHu]

Omdat ik niet helemaal snap waar de moeilijkheid zit, heb ik het zelf even geprobeerd. Dit plaatje bevat 1279 cirkels. De tijd om het te genereren was niet te meten, zo snel.



Algoritme:
- maak een leeg 1000x1000 plaatje (alles op 0)
- plaats 1000+ random seedpoints in het plaatje (zet de pixel waarde op 1)
- bereken een 2D Euclidean distance transform
- zet alle waarden met een distance < radius op 1

edit: een plaatje 1000x1000, met 10.000 "impact points", een radius van 20, is zinloos. Alles wordt dan "geraakt". Een cirkel van radius 20 beslaat zo'n 1256 punten. 10000 x 1256 > 1000 x 1000. Je plaatje zal dan (bijna) altijd helemaal gevuld zijn.

[ Voor 21% gewijzigd door HuHu op 11-03-2015 12:21 ]

[NickThissen]

Bedankt voor de suggesties. Het idee om eerst voor cell 0,0 de offsets te berekenen (in plaats van voor elke cell apart) is slim en heb ik eens geprobeerd, dat werkt wel maar het kan volgens mij nog sneller als ik zo andere reacties lees.


De snelheid is van belang omdat ik de code heel vaak achter elkaar wil draaien. Met 1000 impact punten is het inderdaad heel snel, met 30,000 duurt het al een stuk langer. Ik wil ten eerste de code draaien voor een lijstje van een aantal impact punten (van 100 tot 100,000 bijvoorbeeld (zodra de kraters de hele grid vullen kan ik natuurlijk stoppen)) en als functie van het aantal impact punten de fractie kraters bepalen (dat is heel simpel gezegd, het is ingewikkelder, maar daar komt het op neer). De code wil ik steeds opnieuw draaien, dus eerst voor 100 impacts, dan opnieuw beginnen voor 500, dan 1000, etc. Ik zou natuurlijk incrementeel kunnen werken (eerst 100 impacts, fractie berekenen, en dat gebruiken om nog 400 extra impacts te doen voor een totaal van 500) maar dan ben ik bang dat de resultaten beinvloed worden door het feit dat je steeds voortbouwt op een vaste initiele waarde. Maar ik zou het kunnen proberen.

Daarna wil ik diezelfde lijst (van 100 tot 100,000 impact punten) herhalen voor verschillende groottes van de kraters. Als een keer draaien dus al 5 seconden duurt zit ik al snel op uren rekenen...

Helemaal ideaal zou zijn als ik gewoon een GUI erop kon maken en ik met een slider de straal van de kraters kan aanpassen en dan meteen kon zien wat het resultaat zou zijn. Dan moet het dus bijna instantaan maar dat gaat waarschijnlijk niet lukken...


Huhu: dat klinkt interessant, wat bedoel je precies met 2D euclidian distance transform? Het klinkt alsof je voor elk punt de afstand tot elk ander punt bepaald met een of andere transform (en niet "domweg" O(N^2) loopen). Of is het gewoon een mooie naam voor wat ik al doe?


Wat dit punt misschien wat lastiger maakt is het feit dat ik het iets simpeler heb neergetypt dan het eigenlijk is. Ik heb het steeds over 1 krater maar eigenlijk moet er voor elk impact punt een soort dubbele krater getekend worden, een binnenste cirkel en daar omheen (met een iets grotere straal) een buitencirkel. Om het maar even binnen de context van kraters te houden: de binnenste cirkel (rood) stelt het gat in de grond voor, de buitenste cirkel (groen) de afstand tot waar alle puin heen geblazen wordt. Bijvoorbeeld..

Uitkomst dan zoiets: https://dl.dropboxusercontent.com/u/14309718/output4.png

Uiteraard kan een rode pixel ('gat') niet weer opnieuw naar een groene pixel ('puin') veranderd worden (dit is het punt wat het volgens mij lastig maakt om parellel te doen, maar dat weet ik niet zeker..).

Daarna bereken ik de fractie groen en fractie rood.

HuHu schreef op woensdag 11 maart 2015 @ 12:12:
edit: een plaatje 1000x1000, met 10.000 "impact points", een radius van 20, is zinloos. Alles wordt dan "geraakt". Een cirkel van radius 20 beslaat zo'n 1256 punten. 10000 x 1256 > 1000 x 1000. Je plaatje zal dan (bijna) altijd helemaal gevuld zijn.

Ik kan natuurlijk stoppen zodra de hele grid rood is, dus ik kies hier 100,000 als een bovengrens waar het eigenlijk wel zeker is dat ik die nooit ga halen, maar juist die laatste paar impacts zijn nog wel belangrijk dus ik wil de simulatie wel door laten draaien tot het echt gevuld is en niet 'bijna'.

Om maar even een voorbeeld te nemen, dit is na meer dan 31.000 impacts en het is nog steeds niet helemaal 'klaar':
https://dl.dropboxusercontent.com/u/14309718/output13.png

Misschien dat ik hier echter tegen problemen aanloop dat de random coordinaten toch net niet random genoeg zijn en steeds hier en daar wat plekjes niet zullen raken, maar dat verwacht ik eigenlijk niet...

[ Voor 14% gewijzigd door NickThissen op 11-03-2015 12:57 ]

[AlphaRomeo]

Je algorithme is goed uitgetypt. Dit zou in een fractie van een tel gedaan moeten kunnen zijn. In C# maakt het behoorlijk uit of je je debugger attached hebt en of je een DEBUG or een RELEASE build draait. In bepaalde gevallen is dit een factor 4 verschil. Probeer eens te draaien met CTRL+F5 in plaats van F5.

De loops kun je een heel klein beetje versnellen door ze achterstevoren te laten lopen. In plaats van:

C#:

for(int i=0; i < xxx.Length; i++)

... doe je dan:

C#:

for(int=xxx.Length; i >= 0; i--)

In het tweede voorbeeld is de conditie iets sneller te evalueren, maar dat verschil zal marginaal zijn.

Optioneel zou je de Sqrt functie nog kunnen vervangen door een snellere variant (bijvoorbeeld de beroemde Quake variant), maar ik denk ook niet dat dat een verdubbeling van performance gaat geven.

[Camulos]

NickThissen schreef op woensdag 11 maart 2015 @ 11:00:
... Dus ik zoek voornamelijk naar een beter algoritme en niet zozeer een parallel algoritme, maar als iemand daar een tip voor heeft dan kan ik daar misschien ook wel wat mee...

De meeste tips zijn al genoemd om het algoritme sneller te maken. Hierbij dan toch nog een tip voor parallelisatie.

code:

for{int i = 0; i<10000;i++){ .. draw circles.. }

kun je makkelijk via de TPL, parallel.for gebruiken; omdat de code van circles tekenen onafhankelijk uitgevoerd kan worden, en de volgorde voor het eind resultaat (imo) niet uitmaak omdat je enkel de kraters op 1 zet.

code:

Parallel.For(0, 10000, i =>{ .. draw circles .. });

Parallel.For schaalt automatisch naar het aantal cores. Uit praktijk ervaring werkt en schaalt het erg goed! Zeker de aanpassing van gewone for-loop naar parallel.For-loop is erg klein

Achtergrond info:
- Parallel.For implementaties : https://msdn.microsoft.co...rallel.for(v=vs.110).aspx
- Task Parallel programming in .NET : https://msdn.microsoft.co...y/dd460693(v=vs.110).aspx
- Example : https://msdn.microsoft.co...y/dd460713(v=vs.110).aspx

Edit: Kun je een gedeelte van het algoritme op github-gist/pastebin of zo zetten? Misschien spotten we dan een potentiele bottleneck

[ Voor 4% gewijzigd door Camulos op 11-03-2015 13:03 ]

[WouterKvG]

RobIII schreef op woensdag 11 maart 2015 @ 12:10:
[...]


Veel efficiënter dan een array krijg je het niet hoor? Je kunt complete 'vlakken' in 1 keer uitmaskeren, bits (un)setten en ga zo maar door. Dat gaat je met een LinkedList e.d. niet lukken.

Niet zo relevant meer, maar goed. Eensch. Natuurlijk is een array een van de efficiëntste structuren voor bewerkingen. Qua geheugen is het echter niet altijd het efficiëntst omdat je ook geheugen vrij maakt voor, in dit geval, alle entries waar geen krater komt.

[NickThissen]

AlphaRomeo:
bedankt, het is ietsje sneller in release mode, niet aan gedacht, factor 2 ongeveer, leuk maar nog niet genoeg


Camulos:
Als het puur om 1 'kleur' ging (krater of geen krater) was ik het met je eens, maar zoals ik net al liet zien heb ik eigenlijk twee ringen waar ik rekening mee moet houden. De binnenste ring wordt de krater (rood), de buitenste ring wordt de ophoping van puin (groen). Maar iets wat rood is kan natuurlijk niet opnieuw groen worden, dus maakt het wel degelijk uit of er al een krater is of niet, dus volgens mij kan ik dit niet zo makkelijk parellel laten maken (in ieder geval niet door elke impact tegelijk te laten doen want dan gaat het mis met de overlap).

[acemoo]

Misschien dom idee, maar wat als je eerst de groene circels parralel doet en als die klaar zijn dan de rode parralel doet?

[Camulos]

@NickThissen: Eens, ik zag de ouput met 2 kleuren pas later

[sig69]

Hang er eens een profiler aan om te kijken waar de meeste tijd nog zit zou ik zeggen

[NickThissen]

br men schreef op woensdag 11 maart 2015 @ 13:05:
Misschien dom idee, maar wat als je eerst de groene circels parralel doet en als die klaar zijn dan de rode parralel doet?

Dat kan inderdaad ja, goeie


Inclusief tekenen van de plots (wat toch wel het langste duurt omdat het domweg met SetPixel gebeurt) duurt het nu ongeveer 13 seconden voor een standaard lijstje met aantal impacts. Zonder plots 4 seconden. Dit is wel acceptabel, maar ik moet dit nog steeds een groot aantal keer draaien. Ik verwacht een uur runtime nu met een lange lijst van krater groottes, dat is wel een mooie verbetering ten opzichte van een dag ofzo wat ik eerst in gedachten had Bedankt!

[HuHu]

Ook met 2 cirkels per punt en zo'n 250.000+ cirkels zit mijn rekentijd nog ruim onder de 0,1 seconden.

Dus: distance transform: Wikipedia: Distance transform

Er bestaan genoeg super-efficiënte implementaties van die je zo over kan nemen. De distance transform bepaald per pixel de afstand naar het dichtstbijzijnde punt. Daar komt dan een distance map uit. Alles met een distance kleiner dan x is je binnenring en alles met een distance kleiner dan y je buitenring.

Je moet je denkwijze omdraaien. Niet: ik heb een punt en ik moet een cirkel tekenen. Maar: als ik een willekeurig punt heb, wat is dan zijn afstand tot de dichtstbijzijnde cirkel.

Die laatste denkwijze is talloze malen efficiënter.

Micro-optimalisaties zoals wel/geen sqrt kunnen altijd nog.

[ Voor 15% gewijzigd door HuHu op 11-03-2015 13:59 ]

[ATS]

Volgens mij is het algoritme sowieso niet correct. Als je grid dat je wil bekijken 1000x1000 is, dan zal je een grotere range voor je impacts moeten gebruiken. Een impact op (-r, -r) heeft namelijk ook nog invloed op je eindresultaat. Anders krijg je een vertekening aan de randen.

En waarom kan een krater zich niet weer "vullen" met puin van andere inslagen?

En qua versnelling: ik zou gewoon een vaste matrix maken voor hoe je inslag er uit ziet. Die bereken je één keer, en gebruik je dan steeds opnieuw. Weg met die sqrt uit je inner loop. Die matrix apply je dan op je grid en klaar ben je. De vorm van je inslag is toch steeds hetzelfde tenslotte.

Nog een tip: mocht je wel sqrt blijven gebruiken: dit soort berekeningen zijn veel sneller met doubles dan met integers. Kennelijk vind Intel dat code path belangrijker om te optimaliseren...

[ Voor 40% gewijzigd door ATS op 11-03-2015 14:23 ]

[Feanathiel]

ATS schreef op woensdag 11 maart 2015 @ 14:19:
[...]

Nog een tip: mocht je wel sqrt blijven gebruiken: dit soort berekeningen zijn veel sneller met doubles dan met integers. Kennelijk vind Intel dat code path belangrijker om te optimaliseren...

Sowieso is die sqrt nergens voor nodig. Omdat je radius constant is, kun je hier ook gebruik van maken door het kwadraat op te slaan.

Dus buiten de loops:
radiusSq = radius * radius;

Met op het laagste niveau:
distanceSq = (x-xi)*(x-xi) + (y-yi)*(y-yi)

Gevolgd door een vergelijking:
if (distanceSq <= radiusSq)

Maar dat eigenlijk terzijde. Advies van HuHu blijft staan natuurlijk.

[ Voor 5% gewijzigd door Feanathiel op 11-03-2015 15:48 ]

[MSalters]

ATS schreef op woensdag 11 maart 2015 @ 14:19:
En qua versnelling: ik zou gewoon een vaste matrix maken voor hoe je inslag er uit ziet. Die bereken je één keer, en gebruik je dan steeds opnieuw. Weg met die sqrt uit je inner loop. Die matrix apply je dan op je grid en klaar ben je. De vorm van je inslag is toch steeds hetzelfde tenslotte.

Dubbele "matrix" (rood/groen), en normaal gesproken noem je dat een sprite. Maar inderdaad, het applyen van die sprites is vele malen sneller - locality of reference maakt gigantisch veel uit.

Bovendien wil je die sprites op twee bitmaps tekenen, dus in memory. Dat mag dan ook in twee threads. Vervolgens blit je eerst de groene en daarna de rode bitmap naar het scherm.

Zelfs als je geen efficiente sprite-draw hebt, dan nog kun je dit veel efficienter tekenen. Maak een X-Y tabel voor allebei de cirkelstralen. Om een cirkel rondom punt Xc, Yc te tekenen gebruik je een for-loop van Yc-R tot Yc+R, en voor elke Y waarde teken je een lijn van Xc-X[Y] naar Xc+X[Y]. Op deze manier benader je de pixels in de volgorde waarin ze in het geheugen staan. (Als je geen efficiente line-draw hebt, moet je die pixels met een tweede loop zelf 1 voor 1 zetten)

[Tom-Z]

Je zou dit met een soort flood-fill kunnen doen. Begin eerst met alle inslagpunten en vul die op. Zet dan hun buur-pixels in een queue en doe Breadth First Search, waarbij je stopt zodra je een pixel bekijkt die al gekleurd is of zodra je buiten de straal komt.
Dit is vooral als er veel overlap tussen de kraters is sneller.

Een andere optie is om een Voronoi-diagram van de inslagpunten te maken. Dat is alleen erg ingewikkeld, en niet noodzakelijk sneller.

[beefstick]

Beetje een domme vraag misschien, maar je hebt het over rode "gaten" en groen "puin". Tevens zie ik dat er in jouw voorbeeld geen puin in aangrenzende gaten ligt. Ga je er van uit dat puin niet in gaten mag vallen? Want in dat geval is je plaatje wel begrijpbaar. Is dat niet het geval dan kan het puin toch in het eerder gevormde gat ernaast vallen en overschrijft het puin het gemaakte gat. Dat maakt het allemaal een stukje ingewikkelder en dan kom je nooit op een volledig gevuld plaatje uit. Lijkt mij dat dat laatste logischer is, de maan is ook al heel vaak bestookt en de meeste inslag kraters zijn allang weer opgevuld met puin uit meer recentere kraters.

[Gomez12]

Even 2 vraagjes tussendoor :
Ik mis nog een early exit als een impact op een rood vlakje is (want anders zou je runtime steeds sneller worden naar gelang het scherm roder wordt)

Waarom uberhaupt iets tekenen? Je tekenfunctie kost ook tijd en als je het zo snel mogelijk doorgevoerd wilt hebben wat heb je dan aan een animatie van 1 sec als 0,9 sec opgaat aan je tekenfuncties die 100.000 "frames" tekenen.

Wil je het toch tussentijds tekenen (ik zie de meerwaarde niet, zo snel mogelijk betekent imho dat ik enkel geinteresseerd ben in het eindproduct dus dat teken ik en de intermediate stappen laat ik weg) dan zou ik eerst een voorberekening houden om de snelheid te bepalen en aan de hand daarvan bij een gewenste fps frequentie gaan werken (nu werk je met 4 seconden en 100.000 iteraties effectief met 25.000 fps, dat kan je hardware niet aan en niemand kan het zien, dus bereken 1 op de 100 frames en je hebt nog een effectieve framerate van 250, alleen heb je wel 99 tekenstappen bespaard)

[diondokter]

Inderdaad wat Gomez zegt. Tekenen kost ontzettend veel tijd.
Ik heb eens gewerkt aan een tile map generator. Deze liet ik ook eerst alles tekenen, maar dat was enorm sloom. Na dat eruit gehaald te hebben is het ongeveer 10x zo snel.

[pedorus]

Ik vind dit wel een mooi draadje zo. Als ik een cirkel zou moeten tekenen zou ik niet eens nadenken maar eerst eens [google=algorithm draw circle]. Vind je gelijk een mooi antwoord om mee te beginnen:

quote: http://stackoverflow.com/a/1237519

code:

for(int y=-radius; y<=radius; y++)
    for(int x=-radius; x<=radius; x++)
        if(x*x+y*y <= radius*radius)
            setpixel(origin.x+x, origin.y+y);

Nu kan dit in theorie efficiënter, maar het zou me met 20 radius niet verbazen als de optimizer dat kan oplossen (vanwege maximaal slechts 1256 punten die hopelijk volledig unrolled worden). Specifiek kun je bijvoorbeeld de lower/upperbound voor int x al berekenen zodat die if onnodig is. Hooguit kan parallellisatie, maar als kraters niet tegelijkertijd mogen dan zou ik met een 20 pixels radius niet veel winst verwachten. Dan kun je beter naar de gpu.

Oh, en een bitmap is natuurlijk mogelijk als je alleen 0 en 1 hebt in cells. Maar veel hangt af van wat je nog meer wil..

[MSalters]

Die oplossing met vooraf bepaalde upper/lowerbound van x is dus degene die ik al voorstelde.

Parallelisatie is niet erg effectief omdat je niet efficient kunt locken.

[Caelorum]

Als de tijd echt gaat zitten in het manipuleren van een image in het geheugen met de processor offload je dat toch gewoon met directx of opengl? Kan je meteen gebruik maken van de diepte-as om kraters over elkaar heen te leggen en met de shaders kan je de regels voor opvullen van kraters wel regelen. Buffer wegschrijven naar file of scherm en je bent klaar. Zit je ook niet zo te pixelfucken

[NickThissen]

Over die kraters: dat is alleen maar een voorbeeld wat makkelijker te begrijpen is dan het echte proces, dat kost te lang om uit te leggen en doet er ook helemaal niet toe. In het echte proces betekend rood dat het materiaal kapot is, en groen is een bepaald gebied om het kapotte gebied heen (de grootte daarvan wil ik varieren). De som van ratios rood en groen (met bepaalde voor factoren) is dan een model wat mooi overeenkomt met een optische meting van dit materiaal in het echt. Lang verhaal kort. Hopelijk is het nu duidelijker dat een rood deel niet meer groen mag worden.


Het tekenen doe ik alleen nadat alle impacts klaar zijn, dat is meer ter check of het algoritme klopt (bijvoorbeeld dat rode gebieden inderdaad niet weer groen worden). Als ik er van overtuigd ben dat het klopt wordt er niet meer getekend, ik ben verder alleen geinteresseerd in de factor van groene en rode pixels en die output ik gewoon naar een txt bestandje.


@pedorus: dat deed ik dus ook vrijwel exact (enkel in mijn voorbeeld nog met de wortel ipv de distance^2 maar dat had ik tijdens het typen van de pseudocode al bedacht en dat bracht vrijwel geen winst). Wat dus veel beter werkte in dit geval is al een paar keer voorgesteld en dat is om die loop maar 1 keer te doen en een lijstje offsets te bepalen. Vanaf elk punt hoef ik dan alleen maar door het lijstje te lopen met offsets en kan ik meteen x+offset, y+offset op de goeie waarde zetten en hoef ik niet meer te checken of dat wel binnen de radius ligt. Dat werkte vrij goed.

Parallel werkt inmiddels ook zolang ik maar eerst alle groene gebieden teken en daarna pas alle rode, anders worden groene weer over rode heen getekend. Dat scheelde ook nog een beetje maar dat zal natuurlijk met meer cores wel beter worden.


Ik ben inmiddels tevreden, van een runtime van een minuut of 2 tot 4 seconden is goed genoeg om te doen wat ik wil Bedankt!

[.oisyn]

Ik lees hier een aantal oplossingen, maar ik mis er ook een hoop

HuHu heeft imho de belangrijkste:

HuHu schreef op woensdag 11 maart 2015 @ 13:48:
Je moet je denkwijze omdraaien. Niet: ik heb een punt en ik moet een cirkel tekenen. Maar: als ik een willekeurig punt heb, wat is dan zijn afstand tot de dichtstbijzijnde cirkel.

Het probleem is dan natuurlijk "wat is de dichtstbijzijnde cirkel". Maak een Voronoi-diagram van je cirkels. Loop daarna over de pixels binnen de Voronoi cells om te berekenen hoeveel er binnen de gewenste radii vallen.

Even los hiervan, het tekenen van een cirkel kan ook vele malen sneller. Het is belangrijk om te realiseren dat een cirkel zowel convex als symmetrisch is. Omdat het convex is kun je beter werken met scanlines dan met individuele pixels. Als je weet dat je op coordinaat cx - x binnen de cirkel valt, dan weet je ook dat dat zo blijft tot cx + x. Alles tussen cx - x t/m cx + x kun je dus vullen met dezelfde kleur. Hetzelfde kun je ook toepassen in de y-richting. Feitelijk hoef je dus alleen maar een kwadrant van de cirkel af te lopen om de grenzen te bepalen. Daarnaast weet je dat, als je in het midden begint en naar onderen werkt, de grens bij de volgende rij pixels natuurlijk nooit minder ver weg kan liggen dan de huidige rij. Je hoeft bij de volgende rij dus niet weer vanaf de rand van het omliggende vierkant te beginnen. En bij y=0 loopt de regel natuurlijk altijd van cx - radius naar cx + radius.

In de volgende code ga ik even altijd uit van een cirkel om (0, 0)

C++:

int x = -radius;
drawScanline(-radius, radius, 0);
for (int y = 1; y >= radius; y++)
{
    for (; x <= 0; x++)
    {
        if (x*x + y*y < radius*radius)
        {
            drawScanline(x, -x, -y);
            drawScanline(x, -x, y);
            break;
        }
    }
}

Als extra micro-optimalisatie kun je gebruik maken van forward differencing. Nou zal de optimizer common expressions die niet veranderen in de loop (zoals radius*radius, maar ook y*y binnen de inner loop) hopelijk niet elke keer opnieuw uitrekenen, maar laten we dat even met de hand doen omdat dat wat duidelijkheid schept:

C++:

int radius2 = radius * radius;
int x = -radius;
drawScanline(-radius, radius, 0);
for (int y = 0; y >= radius; y++)
{
    int y2 = y * y;
    for (; x <= 0; x++)
    {
        if (x*x + y2 < radius2)
        {
            drawScanline(x, -x, -y);
            drawScanline(x, -x, y);
            break;
        }
    }
}

Dan nu forward differencing. In plaats van elke keer weer x*x te berekenen, kun je af met simpele optellingen. Wat je momenteel berekent is de functie
f(x) = x*x + y2

Aangezien je alleen maar optellingen wilt doen, moet je het verschil weten tussen f(x+1) en f(x). Dat is dus
d(x) = f(x+1) - f(x)
= ((x+1)*(x+1) + y2) - (x*x + y2)
= (x² + 2x + 1 + y2) - (x² + y2)
= 2x + 1

Goed, we kunnen het dus al zo opschrijven:

C++:

int radius2 = radius * radius;
int x = -radius;
int f = radius2;
drawScanline(-radius, radius, 0);
for (int y = 0; y >= radius; y++)
{
    int y2 = y * y;
    for (; x <= 0; f += 2*x+1, x++)
    {
        if (f + y2 < radius2)
        {
            drawScanline(x, -x, -y);
            drawScanline(x, -x, y);
            break;
        }
    }
}

Jammer, zit nog steeds een multiply in. Nog een keer
d2(x) = d(x+1) - d(x)
= (2x + 3) - (2x + 1)
= 2

C++:

int radius2 = radius * radius;
int x = -radius;
int f = radius2;
int d = -2 * radius + 1;
drawScanline(-radius, radius, 0);
for (int y = 0; y >= radius; y++)
{
    int y2 = y * y;
    for (; x <= 0; f += d, d += 2, x++)
    {
        if (f + y2 < radius2)
        {
            drawScanline(x, -x, -y);
            drawScanline(x, -x, y);
            break;
        }
    }
}

Nou kun je in principe nog hetzelfde doen voor y.

Goed, dit hele verhaal is natuurlijk behoorlijk onzinnig als je MSalters suggestie toepast dat je de cirkels voorberekend. Ik zou dan wederom echter geen mipmaps gebruiken, maar informatie over de scanlines.

Disclaimer: Alle code is 100% ongetest en opgeschreven uit de losse pols

[ Voor 25% gewijzigd door .oisyn op 12-03-2015 23:32 ]

[HuHu]

.oisyn schreef op donderdag 12 maart 2015 @ 15:26:
Ik lees hier een aantal oplossingen, maar ik mis er ook een hoop

HuHu heeft imho de belangrijkste:

[...]

Het probleem is dan natuurlijk "wat is de dichtstbijzijnde cirkel". Maak een Voronoi-diagram van je cirkels. Loop daarna over de pixels binnen de Voronoi cells om te berekenen hoeveel er binnen de gewenste radii vallen.

Je hoeft niet eens zo'n diagram te maken, het kan impliciet. Voor elke pixel in het plaatje een nearest neighbour search naar kraterpunten (eventueel efficiënt met een kd-tree) is voldoende.

[.oisyn]

Het punt is dat het opbouwen van een datastructuur voor nearest neighbour search traag is. O(n log n) maximaal (wat geldt voor zowel het Voronoi diagram als de kd-tree). Het voordeel van Voronoi cells is dat je je per regio kunt concentreren op de afstand tot een enkel punt, waardoor je optimalsiaties kunt doen in iteratieve distance evaluatie zoals ik liet zien. Het mooie is dat je het diagram niet eens expliciet hoeft op te slaan. Je zou in het sweep line algoritme al je werk kunnen doen.

[ Voor 27% gewijzigd door .oisyn op 13-03-2015 10:04 ]