Du bist nicht angemeldet.

Werbeanzeige

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 187

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

1

13.09.2008, 11:48

#09: "Rechtecke", Geschwindigkeit, 12.10.2008

#09: "Rechtecke"
Typ: Geschwindigkeit
Deadline: 12.10.2008
Abgabe: contest@spieleprogrammierer.de

Bitte beachten:
- Ablauf und Regeln


Aufgabenstellung:
Gegeben ist eine Liste mit Rechtecken, die in ein "Bild" gezeichnet werden sollen. Die Rechtecke werden der Reihe nach gezeichnet. Das heißt, dass ein Rechteck, das weiter hinten in der Liste liegt, ein anderes Rechteck, das weiter vorne in der Liste liegt, überdecken kann. Es wird nicht verlangt, alle Rechtecke komplett zu zeichnen, sondern nur einen gewissen Ausschnitt (kann man sich wie ein Fenster vorstellen).
Rechtecke werden durch begin_x, begin_y sowie end_x und end_y beschrieben. Achtung: begin_x/y gehört zum Rechteck dazu, end_x/y hingegen nicht (so wie bei STL-Containern). end_x/y ist immer größer als begin_x/y. Übergeben werden ein Zeiger p_rectangles auf die Rechtecke und ihre Anzahl num_rectangles.
Der zu zeichnende Ausschnitt (der helle Bereich im Bild unten) wird durch die Position der linken oberen Ecke (view_x, view_y) und die Bildgröße image_size bestimmt.



Das Bild p_image ist ein Array von Integern, dessen Pixel zeilenweise aufeinander folgen. Das Pixel an Stelle x, y erhält man also mit p_image[y * image_size + x].
Korrekt ist das Bild, wenn jedes Pixel den Index des am weitesten hinten in der Liste liegenden Rechtecks enthält, das dieses Pixel beinhaltet. Die "Farbe" eines Rechtecks ist also einfach sein Index in der Rechteckliste.

Das klingt vielleicht kompliziert, ist aber eigentlich ganz einfach. Schaut euch die Referenzfunktion reference_painter an. Die zu implementierende Funktion sieht so aus:

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
// >>> DEINE FUNKTION - BITTE IMPLEMENTIEREN! <<<

void my_painter(const Rectangle* p_rectangles,
                uint32_t num_rectangles,
                uint32_t* p_image,
                uint32_t image_size,
                int32_t view_x,
                int32_t view_y)
{
}


Besonderheiten:
- p_rectangles und p_image sind 16-Byte-ausgerichtet, um mögliche Optimierungen mittels SSE zu vereinfachen.
- num_rectangles liegt zwischen 1 und MAX_NUM_RECTANGLES (10 Millionen).
- image_size ist eine Zweierpotenz und liegt zwischen MIN_IMAGE_SIZE (128) und MAX_IMAGE_SIZE (4096).
- Das erste Rechteck in der Liste überdeckt immer das gesamte Bild ("Hintergrundfarbe" ist 0).
- Für 16-Byte-ausgerichtete Speicherreservierungen, falls ihr welche benötigt, könnt ihr die Funktionen aligned_alloc und aligned_free aus der "utils.h" benutzen.

Bewertung:
Es zählt die Geschwindigkeit. Jede Lösung muss einen bestimmten Testparcours durchlaufen. Für jede Aufgabe werden Punkte entsprechend der benötigten Zeit verteilt. Wer am Ende die meisten Punkte hat, gewinnt. Die Aufgaben unterscheiden sich durch die Anzahl der Rechtecke, die Bildgröße und möglicherweise leicht durch die Verteilung der verschiedenen Rechtecktypen (zufällige Rechtecke, Punkte, Linien).

Paket hier herunterladen

Viel Spaß!

Lord-archimedes

Treue Seele

Beiträge: 234

Wohnort: Hannover

  • Private Nachricht senden

2

13.09.2008, 12:51

Dazu ein Kommentar:

Spongebob: Guck mal was ich hier habe
Patrick: RECHTECKEEE^^

In diesem Sinne wünsche ich allen viel erfolg^^

Haxx0r

Treue Seele

Beiträge: 209

Wohnort: Da!

Beruf: Rebell mit aktivem Lebensstil

  • Private Nachricht senden

4

13.09.2008, 16:11

jo, war er schon immer und auch in anderen foren ist er es :P
Devil Entertainment :: Your education is our inspiration
Der Spieleprogrammierer :: Community Magazin
Merlin - A Legend awakes :: You are a dedicated C++ (DirectX) programmer and you have ability to work in a team? Contact us!
Siedler II.5 RttR :: The old settlers-style is comming back!

Also known as (D)Evil

Gotbread

Alter Hase

Beiträge: 421

Wohnort: Kempen

Beruf: Student (Etechnik) + Hiwi

  • Private Nachricht senden

5

13.09.2008, 19:08

Re: #09: "Rechtecke", Geschwindigkeit, 12.10.2008

Zitat von »"David Scherfgen"«


Korrekt ist das Bild, wenn jedes Pixel den Listenindex des am weitesten hinten liegenden Rechtecks enthält, das dieses Pixel beinhaltet.


meinst du nicht das Rechteck, das am weitesten vorne liegt?

entsprechend der abbildung müsste es so sein

ansonsten super aufgabe! setze mich gleich mal ran ;)
Mfg Goti
www.gotbread.bplaced.net
viele tolle spiele kostenlos, viele hardware-basteleien :)

"Es ist nicht undicht, es läuft über" - Homer Simpson

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 187

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

6

13.09.2008, 19:12

Re: #09: "Rechtecke", Geschwindigkeit, 12.10.2008

Zitat von »"Gotbread"«

meinst du nicht das Rechteck, das am weitesten vorne liegt?

"Hinten" bezogen auf die Liste ...

Gotbread

Alter Hase

Beiträge: 421

Wohnort: Kempen

Beruf: Student (Etechnik) + Hiwi

  • Private Nachricht senden

7

13.09.2008, 19:33

oh :oops:

aber eine frage zur assembler-optimierung
wie sieht die syntax dafür auf den compilern aus, auf den
es laufen muss ?

unter dem msvc kenne ich das so:

Quellcode

1
__asm mov eax, ebp


der gcc macht es glaube ich so

Quellcode

1
asm("movl %ebp %eax");


kann man das irgentwie in ein makro oder so verpacken dass
man je nach platform das richtige schreibt ?
vermute mal nicht, da auch die syntax anders ist.

muss ich jetzt den gcc runterladen oder lässt sich das irgentwie anders lösen?
Mfg Goti
www.gotbread.bplaced.net
viele tolle spiele kostenlos, viele hardware-basteleien :)

"Es ist nicht undicht, es läuft über" - Homer Simpson

Das Gurke

Community-Fossil

Beiträge: 1 999

Wohnort: Pinneberg

Beruf: Schüler

  • Private Nachricht senden

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 187

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

9

13.09.2008, 19:40

Du kannst Intrinsics nutzen, dann brauchst du gar kein Assembler. Die Intrinsics sind bei beiden gleich, soweit ich weiß.

Crush

Alter Hase

Beiträge: 384

Wohnort: Stuttgart

Beruf: Softwareentwickler

  • Private Nachricht senden

10

13.09.2008, 22:22

Bei mir sind view_x und view_y immer negativ. So läge das Sichtfenster doch außerhalb vom Bildschirm.

Ist das richtig so?

Falls ja, wie berechnet man dann das Sichtfenster? Ich dachte, dass sich die linke obere Ecke vom Sichtfinster immer im Bildschirm befinden muß.

Werbeanzeige