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

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