Polygon in Dreiecke zerlegen
Übersicht BlitzBasic Codearchiv
NoobodyBetreff: Polygon in Dreiecke zerlegen |
Fr, Apr 17, 2009 9:08 Antworten mit Zitat |
|
---|---|---|
Da mich das schon lange interessiert hat, habe ich gestern nach Lektüre des Wikipediaartikels über die Subtracting Ears Method eine entsprechende Funktion dafür geschrieben.
Wofür ist das nützlich? Das ist zum Beispiel im 3D - Bereich manchmal praktisch, wenn man ein paar Vertices hat und diese nun mit Dreiecken verbinden will, damit man sie rendern kann. Die Eckpunkte werden in der Reihenfolge erstellt, in der sie im Polygon vorkommen, wobei jeder Punkt mit seinem Vorgänger und seinem Nachfolger verbunden ist. Dabei muss man aber aufpassen, dass alle Punkte im Uhrzeigersinn angegeben werden, da das Programm ansonsten in einer Endlosrekursion endet. Zur Veranschaulichung: Der Code: BlitzBasic: [AUSKLAPPEN] Graphics 800, 600, 0, 2 Bedienung ist relativ simpel: Mit Linksklick neuen Punkt erstellen, mit Leertaste das Ganze in Dreiecke zerlegen. |
||
- Zuletzt bearbeitet von Noobody am Mo, Apr 27, 2009 20:20, insgesamt 4-mal bearbeitet
Noobody |
Mi, Apr 22, 2009 19:22 Antworten mit Zitat |
|
---|---|---|
Ich hab die Funktion nochmals überarbeitet und es ist nun egal, ob die Vertices im Uhrzeigersinn angegeben werden oder nicht.
Das Problem lag nämlich bei der Funktion, die überprüft, ob eine Seite komplett in der Figur drinliegt oder nicht. Bislang arbeitete sie mit dem Winkel, in der neuen Version überprüft sie einfach, ob alle Punkte der Figur von der Seite aus gesehen auf der gleichen Hälfte liegen; wenn ja, liegt die Seite nicht in der Figur drin. Neuer Code findet sich im ersten Post. |
||
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun |
Who |
Fr, Apr 24, 2009 16:55 Antworten mit Zitat |
|
---|---|---|
Hi!
Du hast ein wahnsinniges Tempo beim Coden! Ich habe inzwischen auch eine solche Funktion geschrieben, allerdings haben beide zB bei folgendem Polygon ein Problem: Die Ecken sind im Uhrzeigersinn erstellt, frei Hand etwa gleich, der Startpunkt ist auch an der gleichen Stelle, und dann habe ich beide Fenster übereinandergeschoben zum besseren Vergleich. Die tatsächlich "hingeklickte" Linie sieht man bei mir (rechts) weiß, die erzeugten Dreiecke (WireFrame 1) grau, wobei die Außenkanten exakt von der 2D-Line verdeckt werden. Ich wäre sehr froh, wenn wir zusammenhelfen könnten, um den Fehler zu erkennen und zu beheben. Evtl lade ich auch noch meinen Code hoch. MFG Who |
||
Lies vor: Münsterländer, Hinsterbender, Enterbender, Hoffensterchen, Stiefenkelchen |
Silver_Knee |
Fr, Apr 24, 2009 17:14 Antworten mit Zitat |
|
---|---|---|
naja das was du da versuchst zerlegen zu lassen, lässt sogar den Hammer Editor (CSS Map-Editor) abschmieren. Sogesehen ist es nicht so schlimm wenns net klappt | ||
Who |
Fr, Apr 24, 2009 17:19 Antworten mit Zitat |
|
---|---|---|
na deswegen is es doch umso wichtiger das zu schaffen, damit ich behaupten kann, ich kann was, was der Valve Hammer-Editor nicht kann!
Und rein technisch muss sowas funktionieren. Ich will das in meinem Projekt verwenden, da kann ich den Nutzern nicht sagen: "Überseht mal den Fehler da, das können andre auch nicht." MFG |
||
Lies vor: Münsterländer, Hinsterbender, Enterbender, Hoffensterchen, Stiefenkelchen |
BtbN |
Fr, Apr 24, 2009 17:25 Antworten mit Zitat |
|
---|---|---|
Selbst OpenGL weigert sich, konkave Polygone darzustellen. | ||
Goodjee |
Fr, Apr 24, 2009 17:27 Antworten mit Zitat |
|
---|---|---|
ich hab hier nen code der das schafft, ist allerdings noch nicht einfach so benutzbar, aber wenns wen intressiert:
auf 1 startet man die zerlegung, die restliche bedienung steht oben links https://www.blitzforum.de/upload/file.php?id=5390 |
||
"Ideen sind keine Coladosen, man kann sie nicht recyclen"-Dr. House
http://deeebian.redio.de/ http://goodjee.redio.de/ |
Who |
Fr, Apr 24, 2009 18:02 Antworten mit Zitat |
|
---|---|---|
@BtbN: DX weigert sich auch bei so was, trotzdem ist auf dem rechten Bildschirmfoto ein Polygon in Wireframe-3D... was du da siehst ist ein (bzw. zwei) Ansätze, ein konkaves Polygon in einfache 08/15-Dreiecke zu verwandeln.
@Goodjee: Cooles Programm, aber 1. tu ich mir schwer mit fremden Codes und 2. ist deine Zerlegung auch nicht fehlerfrei. Ich habe ein Zimmer entworfen, das extrem unsinnig war (aber gültig aus meiner Sicht. Krumm und schief aber keine Überschneidungen) und leider gabs auch hier einen Fehler, bei dem die eine Dreiecksseite außerhalb von den Wänden / durch die Wand verlaufen ist. Nebenbei noch: Grad wollte ich schreiben ich konnte keinen Punkt auswählen, bis ich versehentlich einen Kasten gezogen hab. Bis auf den kleinen Fehler beim Triangulieren also sehr gelungen! MFG EDIT: Das Polygon von oben aus dem Bild wird bei dir korrekt trianguliert. |
||
Lies vor: Münsterländer, Hinsterbender, Enterbender, Hoffensterchen, Stiefenkelchen |
Goodjee |
Fr, Apr 24, 2009 20:21 Antworten mit Zitat |
|
---|---|---|
ich kenne den fehler, hab aber absolut keine ahnung warum er auftritt und er ist so gut wie nicht zu rekonstruieren...ich glaube der algorithmus ist ansich gut | ||
"Ideen sind keine Coladosen, man kann sie nicht recyclen"-Dr. House
http://deeebian.redio.de/ http://goodjee.redio.de/ |
Noobody |
Fr, Apr 24, 2009 22:18 Antworten mit Zitat |
|
---|---|---|
Ach herrje, da hab ich wohl einen Denkfehler gemacht, als ich die 'Reihenfolge-egal-Methode' eingebaut habe.
Die Hessesche Normalform ist wohl doch nicht für alles gut Naja, ich habe den Code wieder auf die alte Methode mit dem Winkelvergleich umgestellt, dein Polygon wird also wieder korrekt zerlegt, Who. Man muss die Vertices halt wieder im Uhrzeigersinn angeben (dafür kann die Funktion etwas, was selbst der Hammer Editor nicht kann *kicher*). |
||
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun |
Silver_Knee |
Sa, Apr 25, 2009 1:10 Antworten mit Zitat |
|
---|---|---|
was heißt nicht kann mann nimmt 2 Brushes und gut ist. | ||
Noobody |
Mo, Apr 27, 2009 20:14 Antworten mit Zitat |
|
---|---|---|
Dank einem Hinweis von Who habe ich noch einen kleinen Fehler eliminieren können, der ein konkaves Viereck falsch triangulierte, wenn man mit dem falschen Eckpunkt anfing.
Neue Version ist im ersten Post zu finden. |
||
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun |
Who |
Mo, Apr 27, 2009 20:17 Antworten mit Zitat |
|
---|---|---|
So, jetz hab ich die verbesserte Variante!
Der Fehler lag in einer Ausnahme, bei der alle Verbindungen im untersuchten Dreieck drin liegen. Hier haben alle unsere 3 Programme einfach das Dreieck gesetzt. Hier meine Variante: BlitzBasic: [AUSKLAPPEN] Graphics3D 1024, 768, 32, 2 Bedienung: - Linie mit gedrückter Maus malen - Triangulieren mit der Leertaste starten - der Vorgang läuft grafisch ab. Schnell wirds, wenn man den Code nach "Eckfindung animieren" auskommentiert. Man muss beachten, dass man im Uhrzeigersinn malt. Bei Überschneiden kommt eine Warnung. Leider kommt es doch noch selten vor, dass das Ganze nicht hinhaut. Für den Fall bricht das Programm ab, ohne dass fertig trianguliert wird. MFG Who |
||
Lies vor: Münsterländer, Hinsterbender, Enterbender, Hoffensterchen, Stiefenkelchen |
Übersicht BlitzBasic Codearchiv
Powered by phpBB © 2001 - 2006, phpBB Group