Bygga kd-träd

I så fall tar det O(1) tid att sortera kortleken, oavsett val av algoritm.

Asymptotisk tidskomplexitet är meningslöst att prata om, om man inte får ändra om dem involverade variablerna.

Instämmer!

Man får dessutom inte glömma att även datorns jobb ökar snabbt även för dom enklaste sakerna, som att skriva till minnet tex. Ska elektronerna nå en minnesplats och minnet rymmer n objekt är det minst log(n) korsningar som ska passeras osv... Men i en riktig dator är det mycket värre givetvis, den har ju ännu fler begränsningar. Blir nog en ganska intressant tidskomplexitet om man inte räknar med att datorn gör alla sina operationer på konstant tid oavsett storlek på n...

Jag vill nästan gå så långt som att säga att det är meningslöst att prata om tidskomplexiteten om man kan ändra dom involverade variablerna hur man vill

Självklart, men man får ju hålla det inom rimliga gränser. Förutsättningarna (att sortera en kortlek) implicerade att problemet var litet nog för att en vanlig människa ska klara av en bucket sort. Det är klart att när minnet tar slut (som perost säger) så måste man byta algoritm, och då lär det bli en jämförelsesortering med O(nlogn) som teoretiskt minimum. Att minnet sen tar slut ganska fort för en människa är en annan sak.

Vad jag syftade på var "variablerna i formeln" och inte "reglerna". D.v.s. "n-et" i O(n*log(n)).

Att man passerar fler korsningar för att nå en minnesplats, om det finns fler minnesceller, är irrelevant. Operationen tar ändå (är begränsat av någon) konstant tid.

Hm... jag ser inte riktigt vad minnet har med saken att göra. Varken den hypotetiska människan eller den hypotetiska datorn har fått några sådana restriktioner.

Problemet med att fysiskt placera klöver 9 på rad 9 är inte om du kommer ihåg hur raden såg ut eller ej, utan hur du finner samma rad igen. Till skillnad från din dator är du inte förmögen att addressera en godtyglig position i en array på konstant tid.

Kortleksproblemet med rutnätslösningen är för mig detsamma som "hitta rätt ruta i en karta"-problemet. Det är min åsikt att du för en n*m karta hittar en godtyglig ruta på som bäst O(log(n) + log(m)) tid och som mer naivt på O(n + m) tid.

Det förutsätter att jag inte kommer ihåg hur kartan ser ut. Om jag kommer ihåg var varje ruta ligger (kan kanske liknas vid en hash) så kan jag givetvis också peka ut alla rutor på konstant tid.

Resonemanget är att även om du kommer ihåg hur kartan ser ut (numrera rutorna om du vill) så kan du fortfarande inte peka ut en godtyglig ruta på konstant tid.

Det är svårt att experimentera när vi har ett fåtal rutor som står på rad, men jag skulle väldigt starkt tippa på att du snabbare träffar rätt om det bara finns 5 rutor än om det finns 20 rutor. Ju fler rutor desto säkerligen mer "fladdrar" dina ögon när du gör din sökning; ett typiskt tecken på en logaritmisk algoritm.

Nej, att passera en "korsning" tar en viss tid. Visserligen väldigt fort i en dator eftersom det är elektroner som åker runt och det är korta avstånd men ändå, det tar tid. Det är helt enkelt en lägsta nivå på hur snabbt den kan flytta ett sorterat objekt till en minnescell. Men givetvis äts det upp av tusen andra saker som datorn gör i praktiken. Min poäng var bara att visserligen har en människa en begränsning på hur mycket hon kan hålla rätt på i "konstant" tid, men en dator har massor av andra begränsningar den med, och även om datorn var så gjord att den skulle klara valfritt n så skulle det ta en viss tid för den att accessa n olika minnesceller.

Så fort man lämnar teorin kommer en hel massa begränsningar och förenklingar fram, oavsett om det är en dator eller människa som ska utföra jobbet.

Varför inte? Det är helt och hållet en minnesfråga; det handlar om att komma ihåg var en given ruta är i relation till någon given utgångspunkt.

Tiden det tar att accessa en minnescell regleras idag av klock-generatorn och tillhörande inställningar, inte av hur snabbt elektronen färdas. Självklart kan man säga att dagens datorer "fuskar" genom att öka tidsgången för alla operationer till någon största gemensamma nämnare, men det är så det fungerar i praktiken och även hur den vanliga modellen är uppbyggd efter.

Om du vill ha en modell som fungerar för asynkrona datorer och tar hänsyn till detta är du mer än välkommen att göra det, precis som att man redan idag analyserar hypotetiska datorer med "oändlig" parallellism annorlunda. Ett exempel på användsområde för det senare är om du hade tänkt implementera algoritmen i hårdvara.

Läs den senare delen av posten:

Det är svårt att experimentera när vi har ett fåtal rutor som står på rad, men jag skulle väldigt starkt tippa på att du snabbare träffar rätt om det bara finns 5 rutor än om det finns 20 rutor. Ju fler rutor desto säkerligen mer "fladdrar" dina ögon när du gör din sökning; ett typiskt tecken på en logaritmisk algoritm.

Snyggt! Kör du direkt visualisering av photonmappen eller gör du någon post-operation (final gather etc.)?

Jag hävdar återigen att det handlar om hur mycket "minne" jag kan "addressera". Om jag kan träna mig att komma ihåg 100 decimaler på π, så kan jag förmodligen också träna mig till att komma ihåg var en ruta ligger. Att normala människor bara kan "addressera" ett relativt litet antal rutor är en annan sak (och då kommer vi tillbaks till den övre minnesgränsen, och slutar använda bucket sort).

Jag bara spånar lite i huvet men skulle det inte vara möjligt att sortera varje dimension en gång initialt och sedan använda de listorna i de följande iterationsstegen för att snabbare hitta rätt ordning. Jag har ingen idé om hur man skulle göra i praktiken eftersom jag själv brukar sortera i mina kd-träd implementationer, men det skulle vara trevligt om det gick.

Arggh! Förlorade just en lång och trevlig post nu när man kom åt fel knapp. Låt oss därför släppa diskussionen eftersom den trots allt har rört sig lite väl för mycket off-topic.

Ser trevligt ut!

Finns det föresten någon speciell orsak till varför du använder dig av KD-träd? Octrees är mycket enklarare att skapa och kan lätt modifieras till att ha en väldigt låg overhead.

Det är en alldeles utmärkt angreppsmetod.

Final gather brukar vara att du samplar hela din vy från den pixel du vill ljussätta. Monte Carlo hemisphere sampling om du så vill. Du behöver inte göra någon path tracing där eftersom du förmodligen låtit dina fotoner studsa tillräckligt redan.

Japp. Vad du vill kunna göra snabbt är att sampla i alla riktningar från din "final-pixel" och vikta ihop fotoner i närheten där du träffar, ofta gör man det genom någon form av elips-sampling i fotonträdet. Sedan har du som du säger ett estimat av den energi som reflekteras i riktning mot din final-pixel. Då kan du beräkna hur mycket som reflekterats mot ögat, beroende på vilken ljussättningsmodell du valt.

När det gäller KD vs Octree så kan Octree egentligen ses som ett specialfall av KD-träd där man splittar längs fixa axlar hela tiden.

Denna tråd får mig att tänka på Sorting out Sorting xD

Du kan hitta grannen i ett octree på amorterad logaritmisk tid. Den närmaste fotonen ligger i samma kub eller i en av grann-kuberna.

Det går även att bygga upp octreen:n med en grann-pekare för varje riktning och därmed få amorterad konstant tid. Jag är dock tveksam till om man i verkligheten verkligen tjänar något på det.

Edit: Jag säger inte att octree är en bättre struktur utan bara att man för dem enkelt kan få ner minnes-overheaden (på bekostnad av "teoretisk" körtid).

Jag testade Quickselect för att hitta medianen i en kd-träd implementation som jag har. Jag hade inte så mycket tid att testa men det verkade gå mycket fortare att bygga trädet jämfört med att sortera.

Jag använde Java:s inbyggda vilket är Merge Sort tror jag.