Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Weiße Teile eines binären Bildes verwenden

Werbeanzeige

Foaly

Treue Seele

  • »Foaly« ist der Autor dieses Themas

Beiträge: 136

  • Private Nachricht senden

1

28.11.2012, 17:23

Weiße Teile eines binären Bildes verwenden

Hallo alle zusammen,
Ich habe da ein Problem, das bei dem ich gerne mal hören was die Experten aus diesem Forum dazu zu sagen haben. Das Problem sieht wie folgt aus: Ich habe ein binäres Bild (also hat jeder Pixel entweder die Farbe schwarz oder weiß) Nun möchte ich alle weißen Pixel als Positionskoordinaten weiterverwenden. Das einzige was mir einfällt sieht so aus(Pseudocode):

C-/C++-Quelltext

 
1
2
3
4

for(x = 0; x <= width; x++)
   for(y = 0; y <= height; y++)
      if(image[x][y] == white)
          whitepixels.push_back(pair(x,y));

Das erscheint mir aber sehr kompliziert und uneffizient, weil das Bild relativ groß ist und jeden Frame geupdated wird. Daher wollte ich wissen, ob jemand hier eine effizientere Methode kennt, um in die weißen Bereiche des Bildes etwas zu zeichen.
Vielen Dank schon mal im voraus, Foaly :)

drakon

Supermoderator

Beiträge: 6 513

Wohnort: Schweiz

Beruf: Entrepreneur

  • Private Nachricht senden

2

28.11.2012, 17:52

Das scheint mir eigentlich schon das naheligenste zu sein.
Was man da natürlich tun kann ist mit SSE instructions gleich auf mehrere Pixel zugreifen. Zusätzlich lässt sich das ganze auch recht gut parallelisieren, da zwischen den Pixel keinerlei Abhängigkeiten bestehen.

Sofern du wirklich ständig alle Pixel durchgehen musst ist das eigentlich das Vorgehen. Wenn du mehr zum eigentlichen Problem verrätst, dann können wir vielleicht auch eine bessere Alternative zur Lösung deines Problemes geben.
http://www.drakon.ch | Weltweit 31. Bester Solitär Spieler (Standard XP)

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

3

28.11.2012, 18:04

Was genau meinst du mit "in die weißen Bereiche des Bildes etwas zeichnen"?
m4studios

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

4

28.11.2012, 19:26

Du schreibst ja, dass du die weißen Pixel als Positionen verwenden möchtest. So etwas wird schon mal gemacht um Maps zu laden und einfach zu erstellen, da dies mit einem einfachen Zeichenprogramm gelöst werden kann. Bei dir hört es sich so an, als wenn du das Bild dann im Spielverlauf weiterhin zum speichern der Map verwendest. Das ist eigentlich nicht so schön, da die Zugriffe auf die Textur normal recht lange benötigen. Besser wäre es denke ich, wenn du ein zweidimensionales Array oder eine andere Datenstruktur verwendest. Das alles basiert natürlich auf der Vermutung, was du tust. Wie schon geschrieben wäre es sinnvoll wenn du mal genau schreibst was du vor hast.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Foaly

Treue Seele

  • »Foaly« ist der Autor dieses Themas

Beiträge: 136

  • Private Nachricht senden

5

30.11.2012, 14:13

Vielen dank für die schnellen Antworten! Ich hab den den Code den ich oben beschrieben hab einmal versucheshalber implementiert und festgestellt, das er bei einem Bild der Größe 480x640 im Durchschnitt nur 1.8 Millisekunden braucht, das heißt, das ich mich erst mal darauf konzentriere die anderen Teile meines Programmes zu optimieren.
Es geht übrigens nicht um Maps, sondern um Bewegungenserkennung in Videos und Sprites, die sich dementsprechend bewegen. Ich poste demnächst mal ein Video.
Danke nochmal für die Hilfe :)

DeKugelschieber

Community-Fossil

Beiträge: 2 641

Wohnort: Rheda-Wiedenbrück

Beruf: Software-Entwickler

  • Private Nachricht senden

6

30.11.2012, 16:23

Ich würde dir nur noch empfehlen nicht push_back() zu benutzen wenn die Größe des vectors eh feststeht.
Und bei 480x640 Schleifendurchläufen ist das ganze auch eher ein triviales Problem.
Grüße, Kugel

GitHub Meine Firma Pirsch Analytics

NachoMan

Community-Fossil

Beiträge: 3 885

Wohnort: Berlin

Beruf: (Nachhilfe)Lehrer (Mathematik, C++, Java, C#)

  • Private Nachricht senden

7

30.11.2012, 16:28

Zitat von »DeKugelschieber«

Ich würde dir nur noch empfehlen nicht push_back() zu benutzen wenn die Größe des vectors eh feststeht.

Wenn er vorher Reserve aufruft ist das doch in ordnung.
"Der erste Trunk aus dem Becher der Erkenntnis macht einem zum Atheist, doch auf dem Grund des Bechers wartet Gott." - Werner Heisenberg
Biete Privatunterricht in Berlin und Online.
Kommt jemand mit Nach oMan?

Foaly

Treue Seele

  • »Foaly« ist der Autor dieses Themas

Beiträge: 136

  • Private Nachricht senden

8

30.11.2012, 17:03

Darüber hab ich mir auch gerade Gedanken gemacht... Momentan benutze ich ein std::vector<std::pair<int, int> >. Wäre es vielleicht sinnvoller eine std::list zu verwenden? Ich frage, weil ich reserve() nicht benutzen kann, da ich ja nicht weiß, wie viel Teile des Bildes weiß sind (sprich der Vektor ist bei jedem Durchlauf unterschiedlich groß). Das einzige was ich benötige ist ein schnelles hinzufügen am Ende und der zugriff per iterator.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Foaly« (30.11.2012, 17:09)

NachoMan

Community-Fossil

Beiträge: 3 885

Wohnort: Berlin

Beruf: (Nachhilfe)Lehrer (Mathematik, C++, Java, C#)

  • Private Nachricht senden

9

30.11.2012, 17:09

Das std::pair<int, int> wäre 8 Bytes groß, die Zeiger die pro Listenelement benötigt werden sind zusammen 8 oder 16 byte groß. Du bräuchtest also schonmal mindestens doppelt so viel speicher(dann reserviere lieber gleich das doppelte oder dreifache im vector :whistling: ). Ausserdem wwäre das Einfügen nicht unbedingt schneller. Immerhin muss bei einer Liste in jedem push_back new aufgerufen werden. Bei einem std::vector muss das nur alle paar mal gemacht werden. Wenn du abschätzen kannst wieviel es ca. werden reicht das auch. std::vector reserviert sowieso immer etwas mehr.
"Der erste Trunk aus dem Becher der Erkenntnis macht einem zum Atheist, doch auf dem Grund des Bechers wartet Gott." - Werner Heisenberg
Biete Privatunterricht in Berlin und Online.
Kommt jemand mit Nach oMan?

Foaly

Treue Seele

  • »Foaly« ist der Autor dieses Themas

Beiträge: 136

  • Private Nachricht senden

10

30.11.2012, 17:26

:D klingt schwer logisch... Ich werde lieber einen vector benutzen und von anfang an genug Speicher reservieren, wie maximal nötig (480x640). Das ist zwar ein wenig verschwenderisch, aber verhindert, das im schlimmsten Fall der komplette vektor umkopiert werden muss.

Werbeanzeige

Ähnliche Themen