Polygon mit „Loch“: Rahmenlinien korrekt zeichnen

In der Hoffnung, dass es dem einen oder anderen hilft, der eine schnelle und einfache Lösung von wenigen Zeilen Code für ein kompliziert wirkendes Problem sucht … schreibe ich diesen langatmigen Beitrag und garniere ihn mit verwirrenden handgemalten Skizzen! Gern geschehen! (Kommentierter Code am Ende, dafür hat Google dich doch hierher geschickt, ha!)

Für einen Freund arbeite ich gerade an einem kleinen Malprogramm – eigentlich an einem recht komplexen Programm, aber auch ein Malprogramm wäre ja nicht zu unterschätzen. Der Pinsel soll beliebig geformt sein, aber zunächst reicht mir ein einfaches Quadrat. Eine Besonderheit soll aber die Möglichkeit sein, eine schon gemalte Fläche mit einem automatisch generierten Rahmen auszustatten. Das sollte nicht schwer sein, oder?!

Es sei denn, die Fläche ist eigentlich ein Polygon, das eine weitere Fläche umschließt. Das Ergebnis der „Zeichne eine Linie um das Polygon!“-Funktion sieht nämlich so aus:

Echtes Polygon mit "falscher" Linie

Woher kommt bloß diese Linie da oben links? Wie kriegt man sie weg? Um diese Frage zu beantworten, folgt hier eine kurze, wahrscheinlich mathematisch nicht präzise ausgeprägte Erklärung (und es kümmert mich nicht!), was ein Polygon überhaupt ist und wie der Computer die ihm gestellte Aufgabe bearbeitet.

So interpretiert der Mensch das obige Polygon:

Polygon-Fläche

Tatsächlich ist es jedoch eine Kette aufeinanderfolgender Punkte. Und um es explizit zu schließen, wird ihr der erste Punkt noch einmal als letzter Punkt hinzugefügt:

Punkte eines geschlossenen Polygons

Der Punkt 0 in diesem Bild ist die Wurzel des ganzen Polygons und der Startpunkt des „äußeren“ Rahmens. Die Punkte werden nun stur der Reihe nach miteinander verbunden, und wenn der Punkt 4 erreicht wurde, der dem Punkt 0 gleicht, wird von ihm eine Linie zu Punkt 5 gezogen, weil er für den Computer nur ein weiterer Punkt der Kette ist. Genau diese Linie soll aber nicht gezeichnet werden.

Zum Glück gibt es einen sicheren Beweis für das Ende des „äußeren“ Rahmens und den möglichen Beginn eines „inneren“ Rahmens, den auch der Computer akzeptieren kann: Der erstbeste Punkt der Kette, welcher dem Startpunkt eines Polygons gleicht, ist der Endpunkt eines Polygons. Alle Punkte, die danach kommen, müssen einem oder mehreren anderen Polygonen angehören. Wenn also ein Punkt dem Startpunkt gleicht, sagt man dem Programm: Von diesem Punkt bis zum nächsten Punkt darfst du keine Linie zeichnen. Und der nächste Punkt ist dann wiederum selber der neue Startpunkt – und der erstbeste Punkt danach, der ihm gleicht, ist der Endpunkt dieses neuen Polygons und so weiter.

Wichtig ist außerdem, dass derjenige Punkt, der nach dem Endpunkt eines solchen „Sub-Polygons“ in der Kette folgt, immer die Wurzel des gesamten Polygons ist. Das führt dazu, dass von diesem Punkt 0 zu den anderen Sub-Polygonen doch wieder Linien gezeichnet würden. Nach dem Endpunkt eines Sub-Polygons soll aber nicht nur einmal auf eine Linie verzichtet werden (Rückweg vom Sub-Polygon zur Wurzel), sondern wenn nötig auch ein zweites Mal (Hinweg von der Wurzel zu einem anderen Sub-Polygon).

Das ist aber leicht zu korrigieren: Wenn gerade der Endpunkt eines Polygons erreicht wurde, soll das Programm sich merken, dass dieser Endpunkt nicht mit dem nächsten Punkt verbunden werden soll, sondern er ohne Linie ab dem nächsten Punkt fortfahren soll – an diesem Punkt soll das Programm nun aber zusätzlich prüfen, ob es sich dabei zufällig um die Wurzel, also Punkt 0, handelt. Und wenn es sich um Punkt 0 handelt, soll das Programm diesmal gar nichts tun, sondern direkt zum nächsten Punkt in der Kette weiterspringen und den als neuen Startpunkt definieren.

Hier eine Darstellung des Algorithmus:

Polygon-Linien

Nun haben wir alle Linien zwischen der Wurzel und den Start-/Endpunkten der Sub-Polygone verhindert. So sieht das für den Menschen logischer wirkende Ergebnis aus:

Polygon mit "richtigen" Linien

Und so sieht meine Umsetzung in Python 3 und Qt 5 aus:

Posted in Programmieren | Tagged , , | Leave a comment

OpenMW: Kelhim spielt Morrowind mit einer Wagenladung von Mods

OpenMW-Test: Nachthimmel

Morrowind! Der dritte Teil der „The Elder Scrolls“-Reihe wird von vielen Spielern bis heute für den besten von allen gehalten. Warum stimme ich in den Lobgesang auf ein mittlerweile fast dreizehn Jahre altes Spiel ein, dessen Welt zu 80 % aus Ascheland, Einöden und Sümpfen besteht und von gottverdammt hässlichen NPCs mit Namen wie aus einem Fantasy-Namensgenerator bevölkert wird, wobei „bevölkern“ ein Euphemismus für „stocksteif in der Gegend rumstehen“ ist? Die außergewöhnliche Vielfalt, die Andersartigkeit sowie, ja, das Harsche und Abweisende der Landschaften und der Architektur ziehen mich immer wieder in diese harte Welt zurück. Auf den zweiten Blick entpuppt sie sich als erstaunlich lebendig, bunt, geschichtsträchtig und immer wieder: originell. Oblivion und Skyrim, die ihrem Vorgänger wenigstens technisch überlegen sind, wecken in mir nicht die gleiche Lust auf Abenteuer und Erkundung fremder Länder. Doch warum versuchen, meine Liebe zu diesem merkwürdigen Spiel zu beschreiben, wenn es ein viel talentierterer Schreiber schon getan hat? „Rutskarn“ fasst es in seiner Reihe The Altered Scrolls in wunderschöne Worte.

OpenMW

Auch unter Ubuntu spiele ich alle paar Jahre wieder Morrowind, zumal es mithilfe von Wine fantastisch unter Linux läuft. Seit einigen Jahren jedoch schreiben Programmierer im Projekt OpenMW an einer neuen und freien Engine für Spiele wie Morrowind, und eben dieses Spiel dient ihnen als Referenzspiel. Ein schöner Nebeneffekt dieses Projekts ist die angestrebte Betriebssystemunabhängigkeit, sodass OpenMW nicht nur unter Windows, sondern auch unter Mac OS X und Linux läuft. Das Aufregende ist dabei, dass Features, die bisher unter Windows umständlich in parallel zum Spiel laufenden Programmen wie dem MGE (Morrowind Graphics Extender) zur Verfügung gestellt werden, aber unter anderen Betriebssystemen nicht funktionieren, zukünftig direkt in die neue Engine OpenMW integriert werden könnten.

Seit Monaten lese ich die Wasserstandsmeldungen der Entwickler, wie gut sich Morrowind mit ihrer neuen Engine spielen lässt, und jetzt scheint ein normales Spiel ohne größere Fehler in Reichweite zu sein. Ich habe es einfach mal selbst probiert!

Für mich ist es ein doppelt interessantes Experiment. Glaubt es oder nicht, ich habe Morrowind noch nie mit Mods gespielt – keine Grafik-Mods, keine neuen Quests, selbst die offiziellen Add-ons habe ich nur mal ganz kurz angespielt. Aber für meinen Test der OpenMW-Fähigkeiten greifen nun zahlreiche Mods tief in Vanilla-Morrowind ein und verändern die Grafik, Logik und allgemeine Atmosphäre. Hier eine nach bestem Gewissen vollständige Liste der installierten Mods:

  • Vibrant Morrowind 4.0 – Ein umfassender Texturen-Replacer, der die standardmäßig manchmal sehr dröge Spielwelt mit wunderschönen hochauflösenden farbenprächtigen Texturen ausstattet. Landschaften, Gebäude und Inneneinrichtungen waren niemals so schön!
  • Grass Mod – Fügt zahlreichen Regionen endlich Gras hinzu. Ich verwende die nicht-animierte Version für meinen Test.
  • Vurts zahlreiche Tree-Mods, jeweils in Version II – Wunderschöne animierte Bäume schmücken zahlreiche Regionen.
  • LizTail’s New Beast Bodies – Argonier und Khajit haben bessere Modelle.
  • Illy’s Fresh Faces II – Ersetzt die Standard-Gesichter und -Frisuren von Elfen und Menschen durch hochauflösende und von bekannten Persönlichkeiten inspirierte Gesichter und Frisuren.
  • Barabus‘ Orcs – Ersetzt die Standard-Gesichter der Orks durch weniger bescheuert aussehende Gesichter.
  • Better Bodies – Bessere Körpertexturen und -modelle.
  • LizTail’s Fixed BB Meshes – Modellkorrekturen für Better Bodies.
  • Better Clothes – Bessere Kleidungstexturen und -modelle.
  • Darknut’s Clothes – Hochauflösende Kleidungstexturen für Better Clothes.
  • Darknut’s Armor – Hochauflösende Rüstungstexturen.
  • Darknut’s Weapons – Hochauflösende Waffentexturen.
  • Darknut’s Monsters – Hochauflösende Monstertexturen.
  • Ice‘ Robe Replacer für NioLiv-Modelle – Kreative und hochauflösende Roben als Ersatz für Standardroben.
  • Imperial Presence – Fügt dem Spiel deutlich mehr kaiserliche Wachen und Kasernen hinzu, um das Kaiserreich als Besatzungsmacht glaubwürdiger zu machen.
  • BTB’s Sorted Alchemy AOF – Ersetzt die Standardgrafiken, -modelle und -texturen von Tränken.
  • Graphic Herbalism – Pflanzen werden nicht mehr als kistenähnliche Container behandelt, sondern ihre Früchte können mit einem Klick gepflückt werden.
  • Animal Realism – Die meisten Tiere (und Monster) greifen nicht mehr ohne Sinn, Verstand und Grund an, was sich ihnen nähert, sondern fliehen oder wehren sich. 90 % WENIGER CLIFF RACERS!!!!!

OpenMW-Test: Seyda Neen

Trotz der dermaßen hochgerüsteten Morrowind-Installation läuft das Spiel unter Ubuntu 14.04 auf meinem ollen Intel Celeron der Haswell-Generation mit einer GeForce GTX 750 bisher flüssig und beinahe vollständig fehlerfrei: Von den animierten Bäumen sollen eigentlich Blätter herunterschweben, aber ich sehe nur hellgraue Würfel – fällt aber in der ganzen Schönheit der Landschaften nicht unangenehm auf. Nach Verlassen von Seyda Neen ist der Icarus-Rollen-Benutzer nicht vom Himmel gefallen, was er meiner Erinnerung nach eigentlich mit einem lauten Schrei tun sollte. Ansonsten ist mir bisher noch nichts negativ aufgefallen! Momentan halte ich mich in Balmora auf und entscheide mich, welcher Gilde ich zuerst beitreten soll. Ich spiele eine unter dem Sternzeichen Turm geborene bretonische Agentin, also bietet sich die Diebesgilde an – die neue Kaserne des Steuer- und Zensusbüros in Seyda Neen habe ich schon mal um teure Bücher, edle Getränke und schönere Kleidung erleichtert. 😀

Respekt an die OpenMW-Entwickler und (mit bis zu einem Jahrzehnt Verspätung) an die jeweiligen Modder!

Posted in RPG | Tagged , | Leave a comment

E-Books, Adobe-DRM und Linux – eine Anleitung

Der E-Reader trat also in mein Leben. Ein schönes weißes Modell mit integrierter Schutzklappe und mit zusätzlichen Drucktasten unterm Touchscreen, ein im Handel nicht mehr erhältlicher Sony PRS-T3. Natürlich wollte ich ihn sofort ausprobieren und mit einem E-Book füttern! Zuerst musste ich aber mal ein Buch auswählen.

(Zwei Stunden später … Ich bin SEHR wählerisch, was Romane angeht, und ich schäme mich nicht zu sagen, dass meine Kaufentscheidung auch davon abhängt, in welcher Schriftgröße mir der Buchtitel oder, schlimmer noch, der Name des Autors entgegenschreit und wie geschmacklos und einfallslos das Cover gestaltet ist, aber das ist eine andere Geschichte …)

Dann stellte sich die Frage, in welcher Online-Buchhandlung ich das Buch kaufe. Sicher hätte ich einen der als App in den Reader eingebunden Shops wählen können, aber ehrlich gesagt habe ich schon genug Benutzerkonten, darunter bei einer großen deutschen Buchhandlungskette, also warum nicht einfach dort kaufen? Natürlich ist das Buch kopiergeschützt, davon ging ich bereits aus, aber das dürfte kein Problem werden, schließlich habe ich das Buch ja ordentlich gekauft und besitze nun einen Reader. Das Buch muss jetzt nur noch aus dem Shop auf das Gerät. Und eine Kopie auf dem Rechner hätte ich auch gerne, falls das Gerät mal den Geist aufgibt, aber eine gewisse Anzahl an Kopien steht mir ja zu, was sollte also schiefgehen?

Stellte sich heraus, dass ich keine EPUB-Datei, sondern nur eine ACSM-Datei aus dem Shop herunterladen kann. Die war nur eineinhalb Kilobyte groß, das sah zu klein für ein Buch aus. Um die EPUB-Datei zu erhalten, brauchte ich erst einmal eine „Adobe-ID“, mit der ich mich ausweise und das mir noch gar nicht vorliegende Buch auf mich ausstelle. Fantastisch, so sprang bei der Sache doch noch ein weiteres Benutzerkonto heraus, ausgerechnet bei einem der unsympathischsten Software-Unternehmen, die mir einfallen. Aber nun gut, da musste ich wohl in den sauren Apfel beißen, wollte ich mich nicht von einem Großteil des E-Book-Marktes abschneiden.

Adobe Digital Editions

Doch die „Adobe-ID“ reichte natürlich nicht. Nein, ich brauchte auch zwingend die Software Adobe Digital Editions, die mich gnädigerweise kostenlos an den Konzern kettet. Nur, und hier kommt der Haken, nutze ich seit fast einem Jahrzehnt ausschließlich Linux, ein im Weltmaßstab sicher unbedeutendes Desktop-Betriebssystem, aber immerhin von vielen anderen nicht minder sympathischen Unternehmen doch leidlich gut unterstützt. Und ich bin mir sehr sicher, dass der Code innerhalb von Adobe Digital Editions, der für das eigentliche Nachladen des E-Books auf das Gerät und für das Signieren zuständig ist, sehr einfach plattformunabhängig geschrieben werden könnte, wenn er es nicht bereits ist. Aber das Programm als Ganzes gibt es nur für Windows und Mac, und wer als Linux-Nutzer Adobe-kopiergeschützte E-Books lesen möchte, kriegt von Adobe nichts als den Finger.

Und kommt mir nicht mit Amazon, das ist der gleiche Schwachsinn in Blau, nur mit noch größerer Abhängigkeit.

Nun gibt es einen Weg, unter Linux trotzdem sein rechtmäßig erworbenes E-Book zu erhalten: Man lädt sich nicht die „Adobe Digital Editions“-Versionen von der Adobe-Website herunter, sondern installt Wine und Winetricks mit dem Software-Center oder über die Kommandozeile. Wine ist ein Wrapper, der zur Laufzeit eines für Windows geschriebenen Programms Befehle aus der Windows-Welt (Windows, DirectX, …) in solche aus der Linux-Welt (Linux, OpenGL, OpenAL, …) übersetzt und dem Programm so vorgaukelt, auf Windows zu laufen. Wie gut das funktioniert, hängt vom Programm ab, und mit den neuen Versionen von ADE funktioniert es eben überhaupt nicht. Aber wenn man ADE mithilfe von Winetricks installiert, eine Sammlung von Installationsskripts für verschiedene Windows-Software und einigen Konfigurationsskripts, wird dafür die alte Version 1.7 heruntergeladen, die noch mit Wine läuft.

Nachdem man ADE nun in Linux startet, kann man die aus dem Buch-Shop heruntergeladene ACSM-Datei natürlich nicht einfach über das Programmmenü öffnen, importieren oder was auch immer. Nein, der einzige mir bekannte und wahnsinnig intuitive Weg, endlich an das verdammte E-Book zu gelangen, ist, die ACSM-Datei mit der Maus aus dem Dateimanager in das Fenster von Adobe Digital Editions zu ziehen. Nun erscheint ein Ladebalken, einen Augenblick später wird in der ADE-Bibliothek das Buch angezeigt, und im Ordner „My Digital Editions“ im persönlichen Verzeichnis findet man die EPUB-Datei. Diese Datei kann man sich auf seinen per USB angeschlossenen E-Reader kopieren, der sie in seinem eigenen Buchregal anzeigt.

Posted in Allgemein | Tagged , , , | Leave a comment

Umzug

Letzte Woche wollte ich einen Blick in meine Seitenstatistik werfen und bekam keine Daten für das laufende Jahr angezeigt – üblich wären monatliche Aufstellungen. Also schrieb ich eine freundliche E-Mail an meinen Provider, dass hier wohl ein Feature defekt oder abgeschaltet worden sei. Stellte sich heraus, dass ich schon vor einem Jahr meine Website sichern und den Umzug auf ein neues System einleiten sollte, worauf mein Provider mich auch wiederholt in seinen Newsletters hinwies.

Asche auf mein Haupt!

Hier ein entfernt dazu passender lustiger Comic, um den Eintrag aufzulockern!

xkcd.com | Update

xkcd.com | Update

Heute Morgen zog also meine Domain auf einen neuen Server um, und eben habe ich meine Backups hinterhergeschickt. Dieser Eintrag ist auch ein kleiner Test, ob alles wie erwartet funktioniert.

Danke an den Support meines Hosting-Unternehmens für die Geduld und dass dem Blog nicht stillschweigend der Stecker gezogen wurde!

Posted in Allgemein | Leave a comment

Death Note – Analyse #2: Episode 1 bis 12

Death_Note_logo

Viele Zuschauer lassen sich, gerade beim ersten Mal, von Lights demonstrativer Selbstsicherheit und seinen abgebrühten Erfolgen davon ablenken, dass ein Fehltritt immer tödlicher wird, je weiter er sich auf dieser Schneide fortbewegt. Zielten seine anfänglichen Vorsichtsmaßnahmen noch darauf ab, gar nicht erst in den Kreis der Verdächtigen zu geraten oder den Verdacht von sich zu weisen, muss er später zwar in ihrer Komplexität beeindruckende, aber von ihm nicht bevorzugte direkte Konfrontationen suchen. Der Mord an Raye Penber ist meisterhaft geplant, aber birgt trotzdem ein gewisses Risiko, dass irgendjemand sein Gespräch verfolgt und sich der Polizei als Hinweisgeber andient, irgendeine Kamera sein Gesicht unter der Kapuze einfängt oder Penber im letzten Moment doch noch einmal die Kraft findet, Lights Namen zu rufen. Von der Haaresbreite, die Light bei der Begegnung mit Penbers Verlobten Misora noch von dem angekündigten Schafott trennt, ganz zu schweigen.

Gehen wir die einzelnen Stationen der Reihe nach durch. Der Fund des Death Notes und die ersten Exekutionen aus der Sicherheit der Anonymität bis zur TV-Ansprache von L im Kantou-Sendegebiet. Von nun an weiß sich Light, zwar noch nicht als Person, aber als gesuchter „Kira“ unter Beobachtung und beginnt mit seinen inszenierten pseudo-okkultistischen Selbstmorden erste Verwirrspiele mit L und überprüft gleichzeitig seinen Handlungsspielraum bei der Art und Weise, mit dem Death Note zu töten. Außerdem verschafft er sich online Zugang zu den Dateien der japanischen Polizei über den Kira-Fall. Weil L schnell merkt, dass Kira über vertrauliche Informationen der Polizei verfügt, lässt er die mit dem Fall betrauten Polizeibeamten und ihre Angehörigen vom amerikanischen FBI beschatten, was erst auffliegt, als Light mit einem großangelegten Plan alle Agenten umbringt und ihre Existenz über die Medien dem japanischen Ermittlungsteam offenbart wird, dessen Mitglieder daraufhin erzürnt sind und vereinzelt beantragen, vom Fall abgezogen zu werden. Sieg für Light auf der ganzen Linie, nicht wahr?

death-note-task-force

Nur dass es nicht stimmt. Sicherlich ist L nicht so skrupellos, den Tod der FBI-Agenten bezweckt zu haben, aber anschließend besteht das Ermittlungsteam nur noch aus absolut dem Fall verpflichteten und nun sicher zu allem entschlossenen Beamten (und möglicherweise Kira), und darüber hinaus weiß L nun mit Bestimmtheit, dass die FBI-Agenten Kira gefährlich nahe gekommen sein müssen. Die Ermittlungen konzentrieren sich nun auf die Spitzen der japanischen Polizei und ihre Angehörigen, die am Schluss vom FBI beschattet wurden – darunter Light selbst, dessen Zimmer mit Wanzen und Kameras ausgestattet wird. Habt ihr nicht das Gefühl, dass er zunehmend Beinfreiheit verliert und mehr Energie als je zuvor aufwenden muss, sie sich wieder zu beschaffen?

Es gelingt ihm. L sieht sich gezwungen, die Überwachung der Familie Yagami zu beenden, aber … Er muss bereits genug gesehen haben. Wer die Videoübertragung sah, musste sich eigentlich über die wahnsinnige Beherrschtheit wundern, diese emotionale Leere, selbst wenn er vermeintlich für sich alleine war. Oh, natürlich, er blätterte in seinen speziellen Magazinen, um sich für die Kameras wie ein normaler, triebgesteuerter Junge darzustellen, aber … ich weiß nicht … Sammelt man solche Magazine, um dann nur darin zu blättern? Und hat Light als recht attraktiver, selbstbewusst auftretender und bekanntermaßen höchst erfolgreicher junger Mann das nötig? Sicher könnte er sich einfach mit solchen Schönheiten treffen und hat es nicht nötig, Hefte zu verstecken. Es passt einfach nicht zu Light, und obwohl es an keiner Stelle explizit erwähnt wird, halte ich diese aufgesetzte Normalität und seine ansonsten aalglatte Makellosigkeit für den Grund, die Ermittlungen gegen ihn mit anderen Mitteln fortzusetzen.

death-note-l-smiling

L legt sich nun de facto auf Light Yagami fest. Wie gering ist eine deutlich einstellige Wahrscheinlichkeit tatsächlich, wenn man nur einen konkreten Verdächtigen hat? Er besucht dieselbe Universität, wo er sich Light stellt, und beide beschließen (aus gegensätzlichen Interessen), eine oberflächliche Freundschaft zu unterhalten, um sich im Auge zu behalten. Dann betritt Misa Amane das Spielfeld und mischt es ordentlich auf, mit Blick auf den Plot eine gute Wendung, um das drohende Patt zu verhindern. Sie ist der „zweite Kira“, von dem sowohl Light als auch L schnell ausgehen, und zugleich der Grund, warum Light in das Ermittlungsteam aufgenommen wird: L hofft auf verwertbare Reaktionen Lights auf die merklich andere Vorgehensweise und Ideologie des zweiten Kira. Light hingegen sucht die Aufnahme ins Team, um mit dessen Mitteln den Kontakt zum zweiten Kira herstellen zu können, ohne sich sorgen zu müssen, von der Polizei dabei entdeckt zu werden, denn ab dem Moment ist er die Polizei. (Und natürlich bietet es ihm vielleicht bessere Chancen, L auszuschalten.)

Mit diesen beiden Ereignissen – dem Auftritt von Misa und dem Eintritt von Light ins Ermittlungsteam – haben sich die Regeln des Spiels geändert.

Posted in Anime | Tagged , | Leave a comment