005
28.02.2006, 11:46 Uhr
virtual
Sexiest Bit alive
(Operator)
|
1. Lösungsansatz
=============
Also wenn ich jetzt so ein Object habe (_ steht für Durchsichtig):
| Code: |
___XXXXXX___
___XYYYYX___
___XYYYYX___
___XYYYYX___
___XXXXXX___
|
Dann braucht man eigentlich nur den Umriß zu überprüfen, dh die mit X markierten Pixel. Vermutlich wirst Du ein fragileres Objekt haben, was nicht streng quadratisch ist. Aber möglicherweise ist es performanter, zu jdem Objekt eine Liste von Rechtecken zu verwalten, die solche Checks erlauben. zB:
| Code: |
__XXX___________________
__XXX___________________
__XXXXXXX_______________
__XXXXXXXXXXXXXX_______
_____XXXXXXX____________
_____XXXXXXXXXXXXXX____
_____XXXXXXXXXXXXXXXX__
_____XXXXXXXXXXXXXX____
_____XXXXXXX____________
__XXXXXXXXXXXXXX_______
__XXXXXXX_______________
__XXX___________________
__XXX___________________
|
Könnte man in die Rechteeck A-I wie folgt aufteilen:
| Code: |
__AAA___________________
__AAA___________________
__AAACCCC_______________
__AAADDDDDDDGGGG_______
_____DDDDDDD____________
_____DDDDDDDFFFFFFF____
_____DDDDDDDFFFFFFFII__
_____DDDDDDDFFFFFFF____
_____DDDDDDD____________
__BBBDDDDDDDHHHH_______
__BBBEEEE_______________
__BBB___________________
__BBB___________________
|
Ingesamt besteht das Objekt also aus den 9 Rechtecken A-I. Zu kollosionsabfrage sind pro rechteck 4 Vergleiche und eine AND Verknüpfung notwendig. Wenn die alle das gleiche kosten, komme ich auch 9*4+9 = 45.
Wenn die die Pixel einzeln vergleiche, dann ist die Rechteckfläche das Kostenmaß:
F(A)+...F(H) = 9 + 9 + 4 + 36 + 4 + 4 + 21 + 4 + 2 = 93 Also mindestens doppelt so teuer, die Pixel einzeln abzufragen.
Dann ist noch die Frage wichtig, wie teuer es ist, die einzelnen Pixel anzusprechen... Das kann auch enorm teuer sein.
Die Herausforderung dieses Ansatzes besteht darin, die Rechtecke zu finden.
2. Lösungsansatz
=============
Du erstellst BitMasken der nicht durchsichtigen (und damit zu überprüfenden objekte). Die sind recht kompakt, weil 1 Pixel == 1 Bit. Letztlich werden die Masken als unsigned werte gespeichert. Man kann das recht gut hinbekommen, denke ich. Eine Kollisionsabfrage zweier Objekte besteht darin, daß man die einzelnen, sie überlappenden Bitmasken UND verknüpft. Kommt da irgendwo was !=0 raus, handelt es sich um eine Kollision.
Die eigentliche Herausforderung dieses Ansatzes besteht in der Bitfummelei, weil man die bitmasken jeweils entsprechend der relativen Position der Objekte nochmal verschieben muß.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21) |
