Polygon in Dreiecke zerlegen

Übersicht BlitzBasic Codearchiv

Neue Antwort erstellen

Noobody

Betreff: Polygon in Dreiecke zerlegen

BeitragFr, Apr 17, 2009 9:08
Antworten mit Zitat
Benutzer-Profile anzeigen
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:
user posted image

Der Code: BlitzBasic: [AUSKLAPPEN]
Graphics 800, 600, 0, 2
SetBuffer BackBuffer()

Type TVertex
Field X
Field Y

Field Used
End Type

Type TTriangle
Field V1.TVertex
Field V2.TVertex
Field V3.TVertex
End Type

Timer = CreateTimer( 60 )

While Not KeyHit( 1 )
Cls

If MouseHit( 1 ) Then
Vertex.TVertex = New TVertex
Vertex\X = MouseX()
Vertex\Y = MouseY()
EndIf

If KeyHit( 57 ) Then SubtractingEarsMethod( First TVertex )

Render()

Flip 0
WaitTimer Timer
Wend
End

Function Render()
For Triangle.TTriangle = Each TTriangle
Line Triangle\V1\X, Triangle\V1\Y, Triangle\V2\X, Triangle\V2\Y
Line Triangle\V2\X, Triangle\V2\Y, Triangle\V3\X, Triangle\V3\Y
Line Triangle\V3\X, Triangle\V3\Y, Triangle\V1\X, Triangle\V1\Y
Next

For Vertex.TVertex = Each TVertex
WritePixel Vertex\X, Vertex\Y, $FFFFFF
Next
End Function

Function SubtractingEarsMethod( Vertex.TVertex )
Pred.TVertex = PredVertex( Vertex )
Succ.TVertex = SuccVertex( Vertex )

If LineInPolygon( Pred, Succ, Vertex ) Or VertexCount() = 3 Then
Triangle.TTriangle = New TTriangle
Triangle\V1 = Vertex
Triangle\V2 = Pred
Triangle\V3 = Succ

Vertex\Used = True
EndIf

If VertexCount() >= 3 Then SubtractingEarsMethod( Succ )
End Function

Function PredVertex.TVertex( Start.TVertex )
Vertex.TVertex = Start

While True
Vertex = Before Vertex
If Vertex = Null Then Vertex = Last TVertex

If Not Vertex\Used Then Return Vertex
Wend
End Function

Function SuccVertex.TVertex( Start.TVertex )
Vertex.TVertex = Start

While True
Vertex = After Vertex
If Vertex = Null Then Vertex = First TVertex

If Not Vertex\Used Then Return Vertex
Wend
End Function

Function VertexCount()
Local Count

For Vertex.TVertex = Each TVertex
If Not Vertex\Used Then Count = Count + 1
Next

Return Count
End Function

Function LineInPolygon( V1.TVertex, V2.TVertex, MidVertex.TVertex )
Angle = ( 360 + ATan2( V1\Y - MidVertex\Y, V1\X - MidVertex\X ) - ATan2( V2\Y - MidVertex\Y, V2\X - MidVertex\X ) ) Mod 360

If Angle > 180 Then Return False

For Vertex.TVertex = Each TVertex
Succ.TVertex = SuccVertex( Vertex )

If Vertex <> V1 And Vertex <> V2 And Succ <> V1 And Succ <> V2 Then
If LineCollision( V1\X, V1\Y, V2\X - V1\X, V2\Y - V1\Y, Vertex\X, Vertex\Y, Succ\X - Vertex\X, Succ\Y - Vertex\Y ) Then Return False
EndIf
Next

VX = V1\Y - V2\Y
VY = V2\X - V1\X

C = -V1\X*VX - V1\Y*VY

Local Sign = 0
For Vertex.TVertex = Each TVertex
If Vertex <> V1 And Vertex <> V2 Then
If Sign Then
If Sign <> Sgn( Vertex\X*VX + Vertex\Y*VY + C ) Then Exit
Else
Sign = Sgn( Vertex\X*VX + Vertex\Y*VY + C )
EndIf
EndIf
Next

If Vertex = Null Then Return False

Return True
End Function

Function LineCollision( X1#, Y1#, VX1#, VY1#, X2#, Y2#, VX2#, VY2# )
If VX1# = 0 Then VX1# = 0.001
If VY1# = 0 Then VY1# = 0.001
If VX2# = 0 Then VX2# = 0.001
If VY2# = 0 Then VY2# = 0.001

IntersectionX# = -( X1#*VX2#*VY1# - ( X2#*VY2# + ( Y1# - Y2# )*VX2# )*VX1# )/( VX1#*VY2# - VX2#*VY1# )
IntersectionT# = ( IntersectionX# - X1# )/VX1#

If IntersectionT# >= 0 And IntersectionT# <= 1 Then
IntersectionT# = ( IntersectionX# - X2# )/VX2#

If IntersectionT# >= 0 And IntersectionT# <= 1 Then
CollX# = IntersectionX#
CollY# = IntersectionT#*VY2# + Y2#

Return True
EndIf
EndIf
End Function


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

BeitragMi, Apr 22, 2009 19:22
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragFr, Apr 24, 2009 16:55
Antworten mit Zitat
Benutzer-Profile anzeigen
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:

user posted image

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

BeitragFr, Apr 24, 2009 17:14
Antworten mit Zitat
Benutzer-Profile anzeigen
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 Wink

Who

BeitragFr, Apr 24, 2009 17:19
Antworten mit Zitat
Benutzer-Profile anzeigen
na deswegen is es doch umso wichtiger das zu schaffen, damit ich behaupten kann, ich kann was, was der Valve Hammer-Editor nicht kann! Wink
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

BeitragFr, Apr 24, 2009 17:25
Antworten mit Zitat
Benutzer-Profile anzeigen
Selbst OpenGL weigert sich, konkave Polygone darzustellen.

Goodjee

BeitragFr, Apr 24, 2009 17:27
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragFr, Apr 24, 2009 18:02
Antworten mit Zitat
Benutzer-Profile anzeigen
@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

BeitragFr, Apr 24, 2009 20:21
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragFr, Apr 24, 2009 22:18
Antworten mit Zitat
Benutzer-Profile anzeigen
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 Razz

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

BeitragSa, Apr 25, 2009 1:10
Antworten mit Zitat
Benutzer-Profile anzeigen
was heißt nicht kann Wink mann nimmt 2 Brushes und gut ist.

Noobody

BeitragMo, Apr 27, 2009 20:14
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMo, Apr 27, 2009 20:17
Antworten mit Zitat
Benutzer-Profile anzeigen
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

Local Kamera, Licht
Kamera = CreateCamera()
PositionEntity Kamera, 0, 0, -512
Licht = CreateLight()

Local Zeit
Zeit = CreateTimer(100)

Type Ecke
Field X, Y
Field V
End Type

Local E1.Ecke, E2.Ecke

Local Modus

Local Mesh = CreateMesh()
Local Surface = CreateSurface(Mesh)
Local Wire, Abbruch

SeedRnd MilliSecs()

Global MX, MY
;==[Hauptschleife]===================================================
Repeat
MX = MouseX()
MY = MouseY()

If KeyHit(17) Then
Wire = 1 - Wire
WireFrame Wire
EndIf

If KeyHit(57) Then Modus = 1
If Modus = 0 Then
; If MouseHit(1) Then
If MouseDown(1) Then ; macht mehr Spaß!
Abbruch = 0
For E1 = Each Ecke
If E1\X = MX - 512 Then
If E1\Y = 384 - MY Then Abbruch = 1
EndIf
Next
If Abbruch = 0 Then
E1 = New Ecke
E1\X = MX - 512
E1\Y = 384 - MY
EndIf
EndIf
Else
ClearSurface Surface
FlushKeys()
PolyTria(Surface)
Modus = 0
EndIf

RenderWorld

E1 = First Ecke
Repeat
; For E1 = Each Ecke
If E1 <> Null Then E2 = After E1
If E2 = Null Or E1 = Null Then Exit
Line E1\X + 512, 384 - E1\Y, E2\X + 512, 384 - E2\Y
E1 = E2
Forever
; Next
Text 5, 5, TrisRendered() + " Tris; Bereit! [w] WireFrame"
Color 255, 0, 0
Oval MouseX() - 2, MouseY() - 2, 5, 5, 0
Color 255, 255, 255

Flip 0
WaitTimer Zeit
Until KeyHit(1)
End
;==[Funktionen]======================================================
Function PolyTria(Surface)
Local E1.Ecke, E2.Ecke, E3.Ecke, E4.Ecke, E5.Ecke
Local Anzahl, Abbruch, Durchlauf

;==[Ecken zählen, Schitte prüfen]
For E1 = Each Ecke
Anzahl = Anzahl + 1
E1\V = AddVertex(Surface, E1\X, E1\Y, 0)
E2 = After E1
If E2 <> Null Then
E3 = E2
E4 = After E3
While E4 <> Null
If Schnitt(E1\X, E1\Y, E2\X - E1\X, E2\Y - E1\Y, E3\X, E3\Y, E4\X - E3\X, E4\Y - E3\Y) = 1 Then
Color 255, 0, 0
;Rect E1\X + 512, 384 - E1\Y, 10, 10, 0
Line E1\X + 512, 384 - E1\Y, E2\X + 512, 384 - E2\Y
Text 50, 50, "FEHLER!"
Flip 0
Color 255, 255, 255
Delay 1000
Delete Each Ecke
Return 0
EndIf
E3 = E4
E4 = After E3
Wend
EndIf
Next

;==[Ecken durchiterieren]
While Anzahl > 3
Durchlauf = Durchlauf + 1
E1 = Last Ecke
E2 = First Ecke
E3 = After E2
If Seite(E1\X, E1\Y, E3\X - E1\X, E3\Y - E1\Y, E2\X, E2\Y) >= 0 Then
Abbruch = 0
;==[Wenn ein Eck nach innen geht abbrechen]
E4 = After E3
If Seite(E1\X, E1\Y, E3\X - E1\X, E3\Y - E1\Y, E4\X, E4\Y) = 1 Then
If Seite(E2\X, E2\Y, E3\X - E2\X, E3\Y - E2\Y, E4\X, E4\Y) = -1 Then Abbruch = 2
EndIf
;==[momentanes Eck auf alle Schnitte überprüfen]
E4 = E3
E5 = After E4
While E5 <> Null
If Schnitt(E1\X, E1\Y, E3\X - E1\X, E3\Y - E1\Y, E4\X, E4\Y, E5\X - E4\X, E5\Y - E4\Y) Then
Abbruch = 1
Exit
Else
E4 = E5
E5 = After E4
EndIf
Wend
;==[gültiges Eck -> weg damit!]
If Not Abbruch Then
Durchlauf = 0
AddTriangle(Surface, E1\V, E2\V, E3\V)
Delete E2
Anzahl = Anzahl - 1
EndIf
EndIf
Insert E2 After Last Ecke
;==[Eckfindung animieren]
RenderWorld
E1 = First Ecke
Repeat
If E1 <> Null Then E2 = After E1
If E2 = Null Or E1 = Null Then Exit
Line E1\X + 512, 384 - E1\Y, E2\X + 512, 384 - E2\Y
E1 = E2
Forever
Flip 0
;==[nichts hilft mehr...]
If Durchlauf = Anzahl * 2 Then RuntimeError "verdammt!"
Wend
;==[letztes Dreieck schließen]
If Anzahl = 3 Then
E1 = Last Ecke
E2 = First Ecke
E3 = After E2
AddTriangle(Surface, E1\V, E2\V, E3\V)
Delete Each Ecke
EndIf
End Function

;==[Bestimmen, ob sich die !Strecken! schneiden]-------------------------------
Function Schnitt(X1#, Y1#, rX1#, rY1#, X2#, Y2#, rX2#, rY2#)
Local nX#, nY#, Skal#
nX = -rY2
nY = rX2
If (nX * rX1 + nY * rY1) = 0 Then
If ((X2 - X1) / rX1) = ((Y2 - Y1) / rY1) Then Return 2 Else Return 0
EndIf
Skal = (nX * (X2 - X1) + nY * (Y2 - Y1)) / (nX * rX1 + nY * rY1)
If Skal >= 0 And Skal <= 1 Then
nX = -rY1
nY = rX1
Skal = (nX * (X1 - X2) + nY * (Y1 - Y2)) / (nX * rX2 + nY * rY2)
If Skal > 0 And Skal < 1 Then Return 1
EndIf
Return 0
End Function

;==[Bestimmen, auf welcher Seite der !Gerade! ein Punkt liegt]-----------------
Function Seite(X#, Y#, rX#, rY#, PX#, PY#)
Local nX#, nY#, Skal#
nX = -rY
nY = rX
Skal = nX * PX + nY * PY - X * nX - Y * nY
Return Sgn(Skal)
End Function


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

Neue Antwort erstellen


Übersicht BlitzBasic Codearchiv

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group