Method for triangulating a polygon?

Blitz3D Forums/Blitz3D Programming/Method for triangulating a polygon?
Craig H. Nisbet
(Posted 2007) [#1]
Anyone know of a good techique for triangulating a multi(greater then 3) point polygon? The polygon I have doesn't exist as a renderable entity as far as blitz knows. It's just a list of points that define the outline of the polygon. When connected, the points define a 2d flat polygon shape.

I'd like to be able to convert this data into the 3d world as a mesh, but I don't know how to deal with the trangulation of the shape so it can be accurately displayed in 3d without having overlapping sections where the polygon go concave. Anyone know how to do this?
b32	(Posted 2007) [#2]
I translated a program a while back, written by Ian Garton. The original program was written in Java.
Click with left to draw points, and with right to triangulate the polygon.
;/*-------------------------------------------------------------------*/
;/*  BruteForceEarCut.java                                            */
;/*      This file contains the class needed for the implementation   */
;/*      of ear cutting for a simple polygon.                         */
;/*                                                                   */
;/*- Modification History---------------------------------------------*/
;/*  When:       Who:          Comments:                              */
;/*                                                                   */
;/*  97.12.09    Ian Garton    Final Implementation                   */
;/*-------------------------------------------------------------------*/

Type Triangle
	Field v0x#
	Field v0y#
	Field v1x#
	Field v1y#
	Field v2x#
	Field v2y#
End Type

Global 		npoints
Global		earCounter
Global		concaveCount
Dim			xpoints#	(1000), ypoints#	(1000)
Dim			xpointsTemp#(1000), ypointstemp#(1000)
Dim			ptType		(1000)

Dim ex#(4), ey#(4)


Graphics 800, 600, 0, 3
SetBuffer BackBuffer()

Dim xpoints(1000)
Dim ypoints(1000)
npoints = 0


Repeat

Cls

	;N
	If KeyHit(49) Then
		Delete Each triangle
		tel = 0
		npoints = 0
		ok = True
		done = False
	End If

	If MouseHit(1) Then
		xpoints(npoints) = MouseX()
		ypoints(npoints) = MouseY()
		npoints = npoints + 1
		xpoints(npoints) = xpoints(0)
		ypoints(npoints) = ypoints(0)
		ok = True
	End If
	
	tl = 0
	If done Then
	For ti.triangle = Each triangle
			filltri ti\v0x, ti\v0y, ti\v1x, ti\v1y, ti\v2x, ti\v2y, 0, 0, 255, 255, 255, 0
			Line ti\v2x, ti\v2y, ti\v0x, ti\v0y
			tl = tl + 1
	Next

	Else
	
	tel = npoints
	mtst = False
	For i = 0 To tel - 1
		Color 0, 255, 0
		Oval xpoints(i) - 5, ypoints(i) - 5, 10, 10
		Text xpoints(i), ypoints(i) - 15, i, True, True

		tst = False
		For j = 0 To tel - 1
			If j <> i Then tst = tst Or Kruisen(xpoints(i), ypoints(i), xpoints(i + 1), ypoints(i + 1), xpoints(j), ypoints(j), xpoints(j + 1), ypoints(j + 1))
		Next
					
		If tst Then Color 255, 0, 0 Else Color 0, 0, 255
		mtst = mtst Or tst
		Line xpoints(i), ypoints(i), xpoints(i + 1), ypoints(i + 1)
	Next
	
	End If

	If MouseHit(2) And (Not mtst) Then 
		If polygonClockwise() Then 
				For i = 0 To npoints - 1
					xpointstemp(i) = xpoints((npoints - 1) - i)
					ypointstemp(i) = ypoints((npoints - 1) - i)
					;pttpye
				Next

				For i = 0 To npoints - 1
					xpoints(i) = xpointstemp(i)
					ypoints(i) = ypointstemp(i)
				Next
				
			End If


		If ok Then
			npoints = npoints + 1
			xpoints(npoints - 1) = xpoints(0)
			ypoints(npoints - 1) = ypoints(0)
			ok = False
		End If
		
	on = npoints
	For i = 0 To on
		action "cut"
	Next
		
	done = True
	End If
	
	Text 0, 0,  "Use LMB to draw 'simple' polygon"
	Text 0, 20, "Lines that are intersecting are marked Red"
	Text 0, 40, "If no lines are intersecting, use RMB to triangulate"
	Text 0, 60, "This code was written by Ian Garton"

	
	Flip

Until KeyHit(1)

End


;    /*
;     * main:  This is to run outside of Netscape, using AppletFrame.
;     */
;    public static void main (String args())
;    {
;	runsInBrowser = False;
;	AppletFrame.startApplet("BruteForceEarCut",
;				"Brute Force Ear Cutting",
;				args);
;    }


;    /* finishNotify:  When user enters final point, variables are
;     *                initialized and the Cut Ear button is made
;     *                active.
;     */
Function FinishNotify()
		
	earCounter = 0
		
End Function


;    /* action:  Performs actions according to button user activates.
;     */	
Function action(actie$)

	If actie$ = "clear" Then
	
	    earCounter = 0
		Cls
		
	End If
	
	If actie$ = "cut" Then
	    If (npoints > 3) Then
	        classifyPoints
	        doCutEar
	        ;repaint
	    End If
	End If
		
End Function


;    /* paint:  Displays modified polygon
;     */
;Function repaint()
;
;    public void paint(Canvas caller, Graphics g)
;    {
;	if (transformedPoly == null) return;
;
;	for (int i = 0; i < earCounter; i++) {
;	    g.setColor(Color.yellow);
;	    g.fillPolygon(earPoly(i));
;	    g.setColor(Color.pink);
;	    g.drawPolygon(earPoly(i));
;	}
;
;	if (npoints > 3) {
;	    g.setColor(Color.black);
;	    g.drawPolygon(transformedPoly);
;        }
;    }


;    /* polygonClockwise:  Returns true if user inputted polygon in 
;     *                    clockwise order, false if counterclockwise.  
;     *                    The Law of Cosines is used to determine the
;     *                    angle.
;     */
Function polygonClockwise2()
    
	Local aa#, bb#, cc#, b#, c#, theta#
	Local convex_turn#
	Local convex_sum# = 0

	For i = 0 To npoints - 2
	
	    aa = ((xpoints(i+2) - xpoints(i)) * (xpoints(i+2) - xpoints(i))) + ((-ypoints(i+2) + ypoints(i)) * (-ypoints(i+2) + ypoints(i)))
	    
	    bb = ((xpoints(i+1) - xpoints(i)) * (xpoints(i+1) - xpoints(i))) + ((-ypoints(i+1) + ypoints(i)) * (-ypoints(i+1) + ypoints(i)))
	    
	    cc = ((xpoints(i+2) - xpoints(i+1)) * (xpoints(i+2) - xpoints(i+1))) + ((-ypoints(i+2) + ypoints(i+1)) * (-ypoints(i+2) + ypoints(i+1)))
	
	    b = Sqr(bb)
	    c = Sqr(cc)
	    theta = ACos((bb + cc - aa) / (2 * b * c))

	    If (convex(xpoints(i), ypoints(i),xpoints(i+1), ypoints(i+1),xpoints(i+2), ypoints(i+2))) Then
			convex_turn = Pi - theta
			convex_sum = convex_sum + convex_turn	
	    Else 
		convex_sum = convex_sum - (Pi - theta)
	    End If
	
	Next
	
	aa = ((xpoints(1) - xpoints(npoints-2)) * (xpoints(1) - xpoints(npoints-2))) + ((-ypoints(1) + ypoints(npoints-2)) * (-ypoints(1) + ypoints(npoints-2)))
	    
	bb = ((xpoints(0) - xpoints(npoints-2)) * (xpoints(0) - xpoints(npoints-2))) + ((-ypoints(0) + ypoints(npoints-2)) * (-ypoints(0) + ypoints(npoints-2)))
	    
	cc = ((xpoints(1) - xpoints(0)) * (xpoints(1) - xpoints(0))) + ((-ypoints(1) + ypoints(0)) * (-ypoints(1) + ypoints(0)));
	
	b = Sqr(bb)
	c = Sqr(cc)
	theta = ACos((bb + cc - aa) / (2 * b * c))
	
	If (convex(xpoints(npoints-2), ypoints(npoints-2), xpoints(0), ypoints(0), xpoints(1), ypoints(1))) Then
	    convex_turn = Pi - theta
	    convex_sum = convex_sum + convex_turn
	Else
	    convex_sum = convex_sum - (Pi - theta)
	End If

	If (convex_sum >= (2 * 3.14159)) Then Return True Else Return False
	
End Function

;    /* classifyPoints:  Classifies points as "convex" or "concave".  
;     *                  Convex points are represented as a "1" in the
;     *                  ptType array; concave points are represented as a
;     *                  "-1" in the array.
;     */
Function classifyPoints()
	
	concaveCount = 0


;	/* Before cutting any ears, we must determine if the polygon was
;         * inputted in clockwise order or not, since the algorithm for
;         * cutting ears assumes that the polygon's points are in clockwise
;         * order.  If the points are in counterclockwise order, they are
;         * simply reversed in the array.
;         */
	If (earCounter = 0) Then
	    If (Not polygonClockwise()) Then
			For i = 0 To npoints - 1
				xpointsTemp(i) = xpoints(npoints-1 - i)
				ypointsTemp(i) = ypoints(npoints-1 - i)
			Next
			For i = 0 To npoints - 1
				xpointsTemp(i) = xpoints(i)
				ypointsTemp(i) = ypoints(i)
			Next
		End If
	End If
	
	For i = 0 To npoints - 1
		If i = 0 Then
			If (convex(xpoints(npoints-2), ypoints(npoints-2), xpoints(i), ypoints(i), xpoints(i+1), ypoints(i+1))) Then
				ptType(i) = 1
			Else
				ptType(i) = -1
				concaveCount = concaveCount + 1
			End If
		Else
			If (convex(xpoints(i-1), ypoints(i-1), xpoints(i), ypoints(i), xpoints(i+1), ypoints(i+1))) Then
			    ptType(i) = 1;	/* point is convex */
			Else
				ptType(i) = -1
				concaveCount = concaveCount + 1
			End If
		End If
	Next
		
End Function

;    /* convex:  returns True If point (x2, y2) is convex
;     */
Function convex(x1#, y1#, x2#, y2#, x3#, y3#)
    
		If (area(x1, y1, x2, y2, x3, y3) < 0) Then Return True Else Return False
	
	End Function
	

;    /* area:  determines area of triangle formed by three points
;     */
Function area(x1#, y1#, x2#, y2#, x3#, y3#)
    
	Local areaSum# = 0

	areaSum = areaSum + (x1 * (y3 - y2))
	areaSum = areaSum + (x2 * (y1 - y3))
	areaSum = areaSum + (x3 * (y2 - y1))

	;/* for actual area, we need to multiple areaSum * 0.5, but we are
    ;     * only interested in the sign of the area (+/-)
    ;     */

	Return areaSum
	
    End Function


;    /* triangleContainsPoints:  returns true if the triangle formed by
;     *                          three points contains another point
;     */
Function triangleContainsPoint(x1#, y1#, x2#, y2#, x3#, y3#)
    
	Local i = 0
	Local area1#, area2#, area3#
	Local noPointInTriangle = True

	While ((i < npoints - 1) And (noPointInTriangle)) 
	
		;/* point is concave */ 
	    If ((ptType(i) = -1) And (((xpoints(i) <> x1) And (ypoints(i) <> y1)) Or ((xpoints(i) <> x2) And (ypoints(i) <> y2)) Or ((xpoints(i) <> x3) And (ypoints(i) <> y3)))) Then

			area1 = area(x1, y1, x2, y2, xpoints(i), ypoints(i))
			area2 = area(x2, y2, x3, y3, xpoints(i), ypoints(i))
			area3 = area(x3, y3, x1, y1, xpoints(i), ypoints(i))
	
			If (area1 > 0) Then
			    If ((area2 > 0) And (area3 > 0)) Then
				noPointInTriangle = False
				End If
			End If
			
			If (area1 < 0) Then
			    If ((area2 < 0) And (area3 < 0)) Then
				noPointInTriangle = False
				End If
		    End If
	
		End If
	
    i = i + 1

	Wend
	
	Return Not (noPointInTriangle)
    End Function


;    /* ear:  returns true if the point (x2, y2) is an ear, false
;     *       otherwise
;     */
Function ear(x1#, y1#, x2#, y2#, x3#, y3#)
	
	If (concaveCount <> 0) Then
	    If (triangleContainsPoint(x1, y1, x2, y2, x3, y3)) Then Return False Else Return True
	Else
	    Return True
	End If
    
	End Function


;    /* cutEar:  creates triangle that represents ear for graphics purposes
;     */
    Function cutEar(index)
    
	Local new_i = 0
	Local i = 0

	;Dim ex#(4), ey#(4)
	
	If (index = 0) Then
	    ex(0) = xpoints(npoints-2)
	    ey(0) = ypoints(npoints-2)
	    ex(1) = xpoints(index)
	    ey(1) = ypoints(index)
	    ex(2) = xpoints(index+1)
	    ey(2) = ypoints(index+1)
	ElseIf ((index > 0) And (index < npoints-2)) Then
	    ex(0) = xpoints(index-1)
	    ey(0) = ypoints(index-1)
	    ex(1) = xpoints(index)
	    ey(1) = ypoints(index)
	    ex(2) = xpoints(index+1)
	    ey(2) = ypoints(index+1)
	ElseIf (index = npoints-2) Then
	    ex(0) = xpoints(index-1)
	    ey(0) = ypoints(index-1)
	    ex(1) = xpoints(index)
	    ey(1) = ypoints(index)
	    ex(2) = xpoints(0)
	    ey(2) = ypoints(0)
	End If
	
	ex(3) = ex(0)
	ey(3) = ey(0)
	
	earPoly.triangle = New Triangle
	earPoly\v0x = ex(0)
	earPoly\v0y = ey(0)
	earPoly\v1x = ex(1)
	earPoly\v1y = ey(1)
	earPoly\v2x = ex(2)
	earPoly\v2y = ey(2)
	earCounter = earCounter + 1
	
    End Function


;    /* updatePolygon:  creates new polygon without the ear that was
;     *                 cut
;     */
Function updatePolygon(index)
    
	Local new_i = 0
	Local i = 0

	If (index = 0) Then i = i + 1

	While (i < npoints - 1)
	    If (i = index) Then i = i + 1
	    If (i < npoints - 1) Then
	
			xpoints(new_i) = xpoints(i)
			ypoints(new_i) = ypoints(i)
			
			new_i = new_i + 1
			i = i + 1
	    End If
	Wend
	
	xpoints(npoints-2) = xpoints(0)
	ypoints(npoints-2) = ypoints(0)
	
	npoints = npoints - 1
    
	End Function


;    /* doCutEar:  Performs all the functions needed to find and cut an
;     *            ear.
;     */
Function doCutEar()
    
	Local earHasBeenCut = False
	Local i = 0

	While ((i < npoints - 1) And (Not earHasBeenCut))
	
	    If (ptType(i) = 1) Then  ;/* point is convex */
			If (i = 0) Then
			    If (ear(xpoints(npoints-2), ypoints(npoints-2),xpoints(i), ypoints(i),xpoints(i+1), ypoints(i+1))) Then
					cutEar(i)
					updatePolygon(i)
					earHasBeenCut = True
		    	End If
			Else     ;/* i > 0 */
			    If (ear(xpoints(i-1), ypoints(i-1),xpoints(i), ypoints(i),xpoints(i+1), ypoints(i+1))) Then
					cutEar(i);
					updatePolygon(i);
					earHasBeenCut = True;
			    End If
			End If
		End If
		
	    
	    i = i + 1
	
  	Wend

	End Function


;Doom3 2D-Fake
;8.10.2004 by Triton
;http://www.silzium-net.de
;
Function filltri(x1,y1,x2,y2,x3,y3,r,g,b,borderr,borderg,borderb) 
For oft = 0 To 1 
If x1 > x2 Then 
p=x2 
x2=x1 
x1=p 
q=y2 
y2=y1 
y1=q 
End If 
If x1 > x3 Then 
p=x3 
x3=x1 
x1=p 
q=y3 
y3=y1 
y1=q 
End If 
If x2 > x3 Then 
p=x3 
x3=x2 
x2=p 
q=y3 
y3=y2 
y2=q 
End If 
Next 

Color r,g,b 
For bx1# = x1 To x2 
m13# = (Float(y3-y1)/(x3-x1)) 
n13# = -m13*x1+y1 
by1# = m13*bx1+n13 

m12# = (Float(y2-y1)/(x2-x1)) 
n12# = -m12*x1+y1 
by2# = m12*bx1+n12 
If by2-by1 > 0 Then Rect bx1,by1,1,by2-by1 
If by2-by1 < 0 Then Rect bx1,by2,1,by1-by2 
Next 
For bx2 = x2 To x3 
m13# = (Float(y3-y1)/(x3-x1)) 
n13# = -m13*x3+y3 
by3# = m13*bx2+n13 

m23# = (Float(y3-y2)/(x3-x2)) 
n23# = -m23*x2+y2 
by4# = m23*bx2+n23 
If by4-by3 > 0 Then Rect bx2,by3,1,by4-by3 
If by4-by3 < 0 Then Rect bx2,by4,1,by3-by4 
Next 

Color borderr,borderg,borderb 
Line x1,y1,x2,y2 
Line x1,y1,x3,y3 
Line x2,y2,x3,y3 
End Function 



;kruisen, determines if line x1,y1-x2,y2 and line x3,y3-x4,y4 are intersecting

Function Kruisen(x1#, y1#, x2#, y2#, x3#, y3#, x4#, y4#)

If (y2 <> y1) Then dx1# = (x2 - x1) / (y2 - y1)
If (y4 <> y3) Then dx2# = (x4 - x3) / (y4 - y3)

grens3 = x1 + (y3 - y1) * dx1
grens4 = x1 + (y4 - y1) * dx1
grens1 = x3 + (y1 - y3) * dx2
grens2 = x3 + (y2 - y3) * dx2

If y4 < y3 Then m34 = y4: n34 = y3 Else m34 = y3: n34 = y4
If y2 < y1 Then m12 = y2: n12 = y1 Else m12 = y1: n12 = y2

If (y2 <> y1) Then test3 = (x3 < grens3) Else test3 = (x3 < x1) And (x3 < x2)
If (y2 <> y1) Then test4 = (x4 < grens4) Else test4 = (x4 < x1) And (x4 < x2)
If (y3 <> y4) Then test1 = (x1 < grens1) Else test1 = (x1 < x3) And (x1 < x4)
If (y3 <> y4) Then test2 = (x2 < grens2) Else test2 = (x2 < x3) And (x2 < x4)

ok3 = (y3 > m12) And (y3 < n12)
ok4 = (y4 > m12) And (y4 < n12)
ok1 = (y1 > m34) And (y1 < n34)
ok2 = (y2 > m34) And (y2 < n34)

test = True

If ok1 And ok2 Then test = test1 = test2
If ok1 And ok3 Then test = test1 <> test3
If ok1 And ok4 Then test = test1 <> test4

If ok2 And ok1 Then test = test2 = test1
If ok2 And ok3 Then test = test2 <> test3
If ok2 And ok4 Then test = test2 <> test4

If ok3 And ok1 Then test = test3 <> test1
If ok3 And ok2 Then test = test3 <> test2
If ok3 And ok4 Then test = test3 = test4

If ok4 And ok1 Then test = test4 <> test1
If ok4 And ok2 Then test = test4 <> test2
If ok4 And ok3 Then test = test4 = test3

Return Not(test)

End Function




;    /* polygonClockwise:  Returns true if user inputted polygon in 
;     *                    clockwise order, false if counterclockwise.  
;     *                    The Law of Cosines is used to determine the
;     *                    angle.
;     */
    Function polygonClockwise()
    
	Local aa#, bb#, cc#, b#, c#, theta#
	Local convex_turn#
	Local convex_sum# = 0

	For i = 0 To npoints - 2
	    aa = ((xpoints(i+2) - xpoints(i)) * (xpoints(i+2) - xpoints(i))) + ((-ypoints(i+2) + ypoints(i)) * (-ypoints(i+2) + ypoints(i)))
	    bb = ((xpoints(i+1) - xpoints(i)) * (xpoints(i+1) - xpoints(i))) + ((-ypoints(i+1) + ypoints(i)) * (-ypoints(i+1) + ypoints(i)))
	    cc = ((xpoints(i+2) - xpoints(i+1)) * (xpoints(i+2) - xpoints(i+1))) + ((-ypoints(i+2) + ypoints(i+1)) * (-ypoints(i+2) + ypoints(i+1)))
		
	    b = Sqr(bb)
	    c = Sqr(cc)
	    theta = ACos((bb + cc - aa) / (2 * b * c))

	    If (convex(xpoints(i), ypoints(i), xpoints(i+1), ypoints(i+1), xpoints(i+2), ypoints(i+2))) Then
			convex_turn = Pi - theta;
			convex_sum = convex_sum + convex_turn
	    
	    Else 
		convex_sum = convex_sum - (Pi - theta)
	    End If
	Next
	
	aa = ((xpoints(1) - xpoints(npoints-2)) * (xpoints(1) - xpoints(npoints-2))) + ((-ypoints(1) + ypoints(npoints-2)) * (-ypoints(1) + ypoints(npoints-2)))
	    
	bb = ((xpoints(0) - xpoints(npoints-2)) * (xpoints(0) - xpoints(npoints-2))) + ((-ypoints(0) + ypoints(npoints-2)) * (-ypoints(0) + ypoints(npoints-2)))
	    
	cc = ((xpoints(1) - xpoints(0)) * (xpoints(1) - xpoints(0))) + ((-ypoints(1) + ypoints(0)) * (-ypoints(1) + ypoints(0)))
	
	b = Sqr(bb)
	c = Sqr(cc)
	theta = ACos((bb + cc - aa) / (2 * b * c))
	
	If (convex(xpoints(npoints-2), ypoints(npoints-2),xpoints(0), ypoints(0),xpoints(1), ypoints(1))) Then
	    convex_turn = Pi - theta
	    convex_sum = convex_sum + convex_turn
	Else 
	    convex_sum = convex_sum - Pi - theta
	End If

	If (convex_sum >= (2 * 3.14159)) Then
	    Return True
	Else
	    Return False
    End If

End Function
Stevie G
(Posted 2007) [#3]
Jeppe Neilson's Tesselate lib in the code archives is excellent and I use an upgraded version for my 2d in 3d landscape creation ...