Triangulating a Polygon

BlitzMax Forums/BlitzMax Programming/Triangulating a Polygon

Armitage 1982 (Posted 2011) [#1]

Hi I like to attract your attention on a code archived by Warpy and improved by ima747 at this location : http://blitzbasic.com/codearcs/codearcs.php?code=2259 As stated in topic, it's a Polygon triangulation by Substracting ears algorithm. Unfortunately there is an issue in that version when you try to draw such polygon forms: This is due to the triangulation algorithm itself. Nothing to do with the last triangle (since you can reproduce this issue anywhere in the polygon). The default DrawPoly function from Max2D does not draw concave polygons. I know there is a tessellation algorithm in OpenGL GLU. The is also a lot of other Algorithm like Seidel or Delaunay... Here is a working demo of Warpy improved by ima747 code: 'TRIANGULATING A POLYGON BY SUBTRACTING EARS! 'Triangulation is the problem of how to cut up a polygon into triangles, so that all the triangles together make up the whole polygon. 'This method works by noticing that a polygon with no holes in it always has two ears. 'An 'ear' is a triangle consisting of two edges from the boundary of the polygon, and a third line on the inside of the polygon 'joining them up, but not crossing the boundary on the way. 'If you clip an ear off the polygon, you are left with a smaller polygon (or, more importantly, a polygon with fewer vertices) 'which you can perform the subtracting ears operation on again. You repeat the process until you are left with a 3-sided polygon, 'which of course is already triangulated! 'The set of all the ears you've clipped off forms a triangulation of the polygon. Function triangulate:TList(triPoints:TList) Local c:Int Local i:Int Local go:Int Local p1:triPoint, p2:triPoint, p3:triPoint Local midx:Float, midy:Float Local hits:Int Local ii:Int Local ix:Float Local n:Int Local x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float Local dx1:Float, dy1:Float, dx2:Float, dy2:Float Local lambda:Float, mu:Float Local l:TList = New TList 'this list will store all our triangles Local array:triPoint[] Local t:tri 'this function takes a list of the vertices of a polygon (in order) as input, and returns a list of triangles. triPoints = triPoints.Copy() 'this algorithm works by removing triPoints from the list, so we make a copy of it and leave the original intact c = triPoints.count() 'we keep track of how many triPoints are in our working polygon so that we know when to stop! If c < 3 Return New TList 'error-checking: fewer than 3 triPoints doesn't make a polygon While c>3 array = triPoint[] (triPoints.toarray()) 'make an array from the list of triPoints, for easier referencing i = 0 go = 0 While Not go p1=array[i] p2=array[(i+1) Mod c] p3 = array[(i + 2) Mod c] 'p1,p2,p3 are consecutive triPoints on the boundary of the polygon. 'consider the triangle p1->p2->p3 midx:Float = (p1.x + p2.x + p3.x) / 3.0 '(midx,midy) is a triPoint inside the candidate triangle midy:Float = (p1.y + p2.y + p3.y) / 3.0 'here we check if (midx,midy) is inside the polygon. An 'S'-bend in the polygon can cause the candidate triangle 'to actually be on the outside of the polygon, making it useless in a triangulation. 'This check works by counting the number of times a horizontal ray originating from (midx,midy) crosses the boundary of the polygon 'if hits is odd, then (midx,midy) is inside the polygon. hits=0 For ii = 0 To c - 1 x1=array[ii].x y1=array[ii].y x2=array[(ii+1) Mod c].x y2=array[(ii+1) Mod c].y If (y1-midy)*(y2-midy)<0 ix=x1+(x2-x1)*(midy-y1)/(y2-y1) If ix<midx hits:+1 EndIf Next If (hits Mod 2) 'tri is inside polygon 'We now know the triangle is inside the polygon, so the last thing we need to check is that the line p3->p1 'doesn't cross the boundary at any triPoint. x1=p1.x y1=p1.y x2=p3.x y2=p3.y dx1=x2-x1 dy1=y2-y1 go=1 n=(i+3) Mod c While n<>i x3=array[n].x y3=array[n].y dx2=x3-x2 dy2=y3-y2 If dx1<>dx2 Or x1<>x2 Or dy1<>dy2 Or y1<>y2 lambda=(y2-y1+dy2*(x1-x2)/dx2)/(dy1-dx1*dy2/dx2) mu=(x1-x2+lambda*dx1)/dx2 If lambda>0 And lambda<1 If mu>=0 And mu<=1 go=0 EndIf EndIf EndIf x2=x3 y2=y3 n=(n+1) Mod c Wend EndIf If Not go 'if go=0, then our line crossed the boundary at some triPoint, so this triangle isn't an ear. i=(i+1) Mod c If i=0 Return Null EndIf Wend 'by the time we get out of that while loop, we know that the triangle p1->p2->p3 is an ear, so can be clipped t = tri.Create(p1, p2, p3) 'remove p2 from the list of triPoints - this is the same as removing the whole ear from the polygon - now there is no way 'p1->p2->p3 will be considered again. triPoints.remove p2 l.addlast t 'add the triangle to our list of ears c:-1 'we've removed a triPoint Wend 'we're left with a single triangle, but it's not in our list of ears yet, so we need to add it array=triPoint[](triPoints.toarray()) t=tri.Create(array[0],array[1],array[2]) l.AddLast t 'done! return the list of triangles Return l End Function Function DrawTriPoly(triPointsList:TList) Local TrisList:TList Local t:tri If triPointsList.Count() < 3 Then Return ' Don't have enough triPoints TrisList = triangulate(triPointsList) If Not TrisList Or ListIsEmpty(TrisList) Then Return ' we killed too many tris For t = EachIn TrisList t.draw() Next End Function Type tri Field p1:triPoint,p2:triPoint,p3:triPoint Function Create:tri(p1:triPoint,p2:triPoint,p3:triPoint) Local t:tri=New tri t.p1=p1 t.p2=p2 t.p3=p3 Return t End Function Method draw() Local poly:Float[] poly =[p1.x, p1.y, p2.x, p2.y, p3.x, p3.y] DrawPoly poly End Method End Type Type triPoint Field x:Float,y:Float Function Create:triPoint(x:Float, y:Float) Local p:triPoint=New triPoint p.x=x p.y=y Return p End Function End Type 'Demo - left click to place points, right click to reset Graphics 800, 600, 0 SetBlend ALPHABLEND local points:TList = New TList Local oldPoint:triPoint = Null While Not (KeyHit(KEY_ESCAPE) Or AppTerminate()) SetColor(255, 255, 255) DrawText("Left click to place points, Right click to reset", 0, 0) If MouseHit(1) points.AddLast(triPoint.Create(MouseX(), MouseY())) End If If MouseHit(2) points = New TList oldPoint = Null End If ' Draw polygon SetColor(128, 128, 128) SetAlpha(0.7) DrawTriPoly(points) SetAlpha(1.0) ' Draw vertex and vertices For TP:triPoint = EachIn points SetColor(255, 255, 255) If oldPoint Then DrawLine(oldPoint.X, oldPoint.Y, TP.X, TP.Y) SetColor(255, 0, 0) SetHandle(-1.0, -1.0) DrawOval(TP.X, TP.Y, 2.0, 2.0) SetHandle(0.0, 0.0) oldPoint = TP Next Flip Cls WEnd And today, I take a moment to port the John W. Ratcliff Flipcode archive to BlitzMax (http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml) : I include a fake 2D Vector Class named b2Vec2 because I'm using this one in my games. It comes from the Box2D Module ported by Brucey and developed by Erin Catto at http://box2d.org/ ' This code try to triangulate / tessalate any polygon / contour (without holes) ' Entry submitted by John W. Ratcliff [jratcliff@...] ' Ported to BlitzMax by Michaël Lievens [http://www.arm42.com] ' Thanks to the flipcode archives file : <a href="http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml" target="_blank">http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml</a> ' Original source code of this algorithm is unknown. ' ' Permission is hereby granted, free of charge, to any person obtaining a copy ' of this software and associated documentation files (the "Software"), to deal ' in the Software without restriction, including without limitation the rights ' to use, copy, modify, merge, publish, distribute, sublicense, and/or sell ' copies of the Software, and to permit persons to whom the Software is ' furnished to do so, subject to the following conditions: ' ' The above copyright notice and this permission notice shall be included in ' all copies or substantial portions of the Software. ' ' THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR ' IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, ' FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE ' AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER ' LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, ' OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN ' THE SOFTWARE. ' Rem bbdoc: Fake 2D Vector Class End Rem Type b2Vec2 Field _x:Float Field _y:Float Function Create:b2Vec2(X:Int, Y:Int) Local v:b2Vec2 = New b2Vec2 v._x = X v._y = Y Return v End Function Method X:Float() Return _x End Method Method Y:Float() Return _y End Method End Type Rem bbdoc: Convenience function for creating a b2Vec2 object. End Rem Function Vec2:b2Vec2(x:Float, y:Float) Return New b2Vec2.Create(x, y) End Function Type TTriangulate Const EPSILON:Float = 0.0000000001 Rem bbdoc: compute area of a contour/polygon endrem Function Area:Float(contour:TList) Local N:Int = contour.Count() Local A:Float = 0.0 Local P:Int = N - 1 Local Q:Int = 0 While Q < N If Q > 0 Then P = Q Local B2P:b2Vec2 = b2Vec2(contour.ValueAtIndex(P)) Local B2Q:b2Vec2 = b2Vec2(contour.ValueAtIndex(Q)) A:+B2P.X() * B2Q.Y() - B2Q.X() * B2P.Y() Q:+1 Wend Return A * 0.5 End Function Rem bbdoc: InsideTriangle decides if a point P is Inside of the triangle defined by A, B, C. endrem Function InsideTriangle:Int(Ax:Float, Ay:Float, Bx:Float, By:Float, Cx:Float, Cy:Float, Px:Float, Py:Float) Local _ax:Float, _ay:Float, _bx:Float, _by:Float, _cx:Float, _cy:Float, apx:Float, apy:Float, bpx:Float, bpy:Float, cpx:Float, cpy:Float Local cCROSSap:Float, bCROSScp:Float, aCROSSbp:Float _ax = Cx - Bx _ay = Cy - By _bx = Ax - Cx _by = Ay - Cy _cx = Bx - Ax _cy = By - Ay apx = Px - Ax apy = Py - Ay bpx = Px - Bx bpy = Py - By cpx = Px - Cx cpy = Py - Cy aCROSSbp = _ax * bpy - _ay * bpx cCROSSap = _cx * apy - _cy * apx bCROSScp = _bx * cpy - _by * cpx Return ((aCROSSbp >= 0.0) & (bCROSScp >= 0.0) & (cCROSSap >= 0.0)) End Function Rem bbdoc: endrem Function Snip:Int(contour:TList, u:Int, o:Int, w:Int, n:Int, V:Int[] var) Local P:Int = 0 Local Ax:Float, Ay:Float, Bx:Float, By:Float, Cx:Float, Cy:Float, Px:Float, Py:Float Local B2U:b2Vec2 = b2Vec2(contour.ValueAtIndex(V[u])) Local B2O:b2Vec2 = b2Vec2(contour.ValueAtIndex(V[o])) Local B2W:b2Vec2 = b2Vec2(contour.ValueAtIndex(V[w])) Ax = B2U.X() Ay = B2U.Y() Bx = B2O.X() By = B2O.Y() Cx = B2W.X() Cy = B2W.Y() If EPSILON > (((Bx - Ax) * (Cy - Ay)) - ((By - Ay) * (Cx - Ax))) Return False While P < n If ((P = u) | (P = o) | (P = w)) P:+1 Continue EndIf Local B2P:b2Vec2 = b2Vec2(contour.ValueAtIndex(V[P])) Px = B2P.X() Py = B2P.Y() If TTriangulate.InsideTriangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py) Then Return False P:+1 WEnd Return True End Function Rem bbdoc: triangulate a contour/polygon, results in a series of triangles. endrem Function Process:TList(contour:TList) ' Allocate and initialize list of Vertices in polygon Local trisList:TList = CreateList() Local n:Int = contour.Count() If n < 3 Then Return trisList Local V:Int[n] Local o:Int = 0 ' We want a counter-clockwise polygon in V If 0.0 < TTriangulate.Area(contour) While o < n V[o] = o o:+1 Wend Else While o < n V[o] = (n - 1) - o o:+1 Wend EndIf Local nv:Int = n ' remove nv-2 Vertices, creating 1 triangle every time Local cnt:Int = 2 * nv 'error detection o = nv - 1 While nv > 2 cnt:-1 ' if we loop, it is probably a non-simple polygon If cnt <= 0 Then Return trisList ' Triangulate: ERROR - probable bad polygon! ' three consecutive vertices in current polygon, <u,v,w> Local u:Int = o If (nv <= u) Then u = 0 ' previous o = u + 1 If (nv <= o) Then o = 0 ' new o Local w:Int = o + 1 If (nv <= w) Then w = 0 ' next If Snip(contour, u, o, w, nv, V) Local S:Int, T:Int ' true names of the vertices Local B2U:b2Vec2 = b2Vec2(contour.ValueAtIndex(V[u])) Local B2O:b2Vec2 = b2Vec2(contour.ValueAtIndex(V[o])) Local B2W:b2Vec2 = b2Vec2(contour.ValueAtIndex(V[w])) ' output Triangle Local tris:tri = tri.Create(B2U, B2O, B2W) trisList.AddLast(tris) ' Remove v from remaining polygon S = o T = o + 1 While T < nv V[S] = V[T] S:+1 T:+1 Wend nv:-1 ' Reset error detection counter cnt = 2 * nv End If Wend V = Null Return trisList End Function End Type Type tri Field p1:b2Vec2, p2:b2Vec2, p3:b2Vec2 Function Create:tri(p1:b2Vec2, p2:b2Vec2, p3:b2Vec2) Local t:tri=New tri t.p1=p1 t.p2=p2 t.p3=p3 Return t End Function Method draw() Local poly:Float[] poly = [p1.X(), p1.Y(), p2.X(), p2.Y(), p3.X(), p3.Y()] DrawPoly poly End Method End Type 'Demo - left click to place points, right click to reset Graphics 800, 600, 0 SetBlend ALPHABLEND Local points:TList = New TList Local oldPoint:b2Vec2 = Null While Not (KeyHit(KEY_ESCAPE) Or AppTerminate()) SetColor(255, 255, 255) DrawText("Left click to place points, Right click to reset", 0, 0) If MouseHit(1) points.AddLast(Vec2(MouseX(), MouseY())) End If If MouseHit(2) points = New TList End If ' Tessalate polygon Local TrisList:TList = TTriangulate.Process(points) For P:b2Vec2 = EachIn points SetColor(255, 255, 255) If oldPoint Then DrawLine(oldPoint.X(), oldPoint.Y(), P.X(), P.Y()) SetColor(255, 0, 0) ' Draw vertex SetColor(255, 0, 0) SetHandle(2.0, 2.0) DrawOval(P.X(), P.Y(), 4.0, 4.0) SetHandle(0.0, 0.0) oldPoint = P Next For T:tri = EachIn TrisList ' Draw polygon SetColor(128, 128, 128) SetAlpha(0.7) T.draw() SetAlpha(1.0) Next DebugLog TrisList.Count() Flip Cls Wend Feel free to use this alternative code in whatever you want (I did not thoroughly test it and there is other issues than the one from Warpy and ima747). I know you can improve this algorithm in many ways (for example with a better counter-clockwise detection, with a Delaunay polygon reduction or by considering polygon holes) And if you can, I would love to see that :) That's why I do not put it right now to the code archive forum. Also: This function is mainly used in my Draw Textured Polygon function. Like many, I'm using the Odd2D.mod from David and there is a very nice DrawImagePoly() function for doing that. Unfortunately, like the DrawPoly function of Max2D it's only working with convex polygon. I'm wondering if we couldn't add an advancedDrawImagePoly() that would support every platforms out of the box so this function would exist once and for all. Thanks for reading me :)

Armitage 1982 (Posted 2011) [#2]

I also discover this open source alternative called poly2tri: http://code.google.com/p/poly2tri/ Looking nice and exist for several languages. I try the C++ version in BlitzMax and everything build so it's probably possible to get a module out of it (never did that before).

Hotshot2005 (Posted 2011) [#3]

So Cool! You must be Math Wizard!!! :) Last edited 2011