Har letat som en tok efter en bra algoritm som låter mig sätta in en roterad aabb (kub) i en 3d grid med precision, fylla celler som kuben täcker dvs. Har sett några skankonverteringsmetoder (rasterisering) men precisionen är dålig efter som dom missar celler. Finns det någon snabb med hyffsad bra precision? Ev är det bättre om den fyller fler celler än nödvändigt, bara den inte fyller samma flera gånger.
Axis aligned bounding box? Det är väl inte en axis aligned bounding box om den är roterad?
Med 3d grid, menar du en grid med kuber i 3D?
Om du menar en roterad kub som ska in i en grid med andra kuber så kolla vilka sidor i den roterade kuben som skär någon av sidorna i grid-kuberna samt kolla om någon av verticarna i den roterade kuben som är inne i en grid-kub. Då borde det vara ett komplett test. Om du vill snabba upp det så kolla först vilka av grid-kuberna som en axis-aligned box som wrappar runt den roterade kuben är i eftersom du då bara kan göra ett test per koordinat.
Det är en AABB som beräknas runt objekt när dom laddas in, därefter kan objekten roteras & flyttas, då gör AABBn det också. 3D-gridden består av celler eller voxels ja, liksidiga också då den är uniform.
Grejen är att jag inte ska testa onödiga kollisioner, dvs inte köra brute force på gridden... om jag försöker sätta in min kub så måste jag på nått vis avgöra vilka celler jag skall testa mot med nån sorts traverseringsalgoritm, bresenhams skankonverterinsalgoritm kommer att missa celler i vissa vinklar, Woo's kommer att överlappa och registrera flera gånger i samma celll... tänkte om det fanns någon standard färdig som brukar användas.
En bounding volume hierarchy brukar man väl använda för att minska antalet prylar att testa mot? Sedan köra brute force mot de som är kvar?
AABB trees? Kreation’s Edge AABB Trees: Best Axis Algorithm
Jag har redan träd med bv's, men det är inte detta det handlar om, gridden är en accelerationsstruktur, och det är i den dessa träds rootnoder används för att sätta in objekt.
se det som ett rutnät med vita pixlar, sen ska man sätta dit en svart box med lite rotation, man ska då rita alla pixlar i rutnätet svarta som boxen täcker, även halva täckta pixlar.
Då har jag nog inget "smart" svar med någon färdig snabb algoritm. Det enda svaret jag har är att filtrera bort så många "boxar" som möjligt med nån snabb dum algoritm och sedan köra brute force på de som är kvar.
