Triangulating a surface

Blitz3D Forums/Blitz3D Programming/Triangulating a surface

_33 (Posted 2007) [#1]

I'm in front of a sizable problem here. A problem that have stopped me from going further in my 3D development since mid April this year. I'm trying to find the proper algorythm to triangulate considering holes in the surface of the model. I'll link an image here... Basically, what I know is, it should take in all the corners, and it should analyse from there how to shoot the right connections between the corners, in order to do triangulation of the surface. This is of course a 2D exercise, but it's for building 3D surfaces. IE. The 2D surface will always be based on rectangle type edges. It's possible that the way I placed my triangles, it's not in logical steps where a procedure could be build around it, but I posted this image as a simple example of the triangulation need. I think it's close thoe to what a proper function could do. I tought working with a boundary, or division of the surface, say from top to bottom, keeping that horizontal boundary, and simply shooting lines downwards from there could be the way to go. But really, I don't know from there. Also, I'm making sure that this will generate a closed surface, and to me, that's a little puzzling. If anyone has a tutorial on closed vs open mesh, I'd read that through. Cheers :)

Stevie G (Posted 2007) [#2]

http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf There are some triangulate algorithms in the code archives ( one of which I adapted to produce my 3d/2d landscapes for Stramash ) but they do not deal with holes. I looked at the above paper in the past and it seems that the same methods can be used but the inner polygon vertices must be passed in the opposite order to that of the outer one. Whether that works or not - no idea I'm afraid. Stevie Not much help

_33 (Posted 2007) [#3]

Stevie, very very interesting concept with the ear tip, and stuff. If I understand this, what I should do is triangulate, and each time void some vertices for further usage. That way, I'll end up filling the space. At the same time, making sure the line's angle isn't between vert_end° and vert_start° (outside the figure). What do you think? I'll post the function if I ever get to make it working.

Stevie G (Posted 2007) [#4]

Yes, that's how basic triangulation works but getting it to work with holes will be quite tricky I reckon. I'd be interested to see if you can get this to work as this technique will also be a good start for a nice non-uniform pathfinding algo. Stevie

_33 (Posted 2007) [#5]

http://www.blitzbasic.com/Community/posts.php?topic=26708 If only I could take that and add possibility of holes in the routine. I'm positive it's not a big thing to add that in, as the code seems really clean. I'l dig that up some more, but don't hold your breath... EDIT: Actually that one is a little bogus as it doesn't seem to know the boundaries... I've had examples that I tried where it did what it tougth was right but messed it up bad. So I'll see what else I can dig up. EDIT 2: Here's something that actually works well, but will need to add possibility of holes in the figure, and see if that will work. But it's like 3/4 of the way to what I need. ; BruteForceEarCut ; by Ian Garton (97.12.09) 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, 2 SetBuffer BackBuffer() npoints = 0 Repeat Cls 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 If done Then For ti.triangle = Each triangle draw_fill_triangle 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 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 line_intersects(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 polygon_clockwise() 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 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 For i = 0 To npoints 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" Flip Until KeyHit(1) End 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 ; 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 polygon_clockwise() = False 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 EndIf EndIf 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 EndIf 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 EndIf EndIf 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 ; 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 EndIf 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 EndIf 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 EndIf EndIf EndIf i = i + 1 Wend 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) EndIf 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 ; 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) And (area2 > 0) And (area3 > 0) Then noPointInTriangle = False EndIf If (area1 < 0) And (area2 < 0) And (area3 < 0) Then noPointInTriangle = False EndIf EndIf i = i + 1 Wend Return Not (noPointInTriangle) End Function ;line_intersects: Determines if line x0,y0-x1,y1 and line x2,y2-x3,y3 are intersecting Function line_intersects(x0#,y0#, x1#,y1#, x2#,y2#, x3#,y3#) n# = (y0-y2) * (x3-x2) - (x0-x2) * (y3-y2) d# = (x1-x0) * (y3-y2) - (y1-y0) * (x3-x2) If Abs(d) < 0.0001 ; Lines are parallel Return False Else ; Lines might cross Sn# = (y0-y2) * (x1-x0) - (x0-x2) * (y1-y0) AB# = n / d If AB > 0.0 And AB < 1.0 CD# = Sn / d If CD>0.0 And CD<1.0 ; Intersection Point X# = x0 + AB * (x1-x0) Y# = y0 + AB * (y1-y0) Return True EndIf EndIf ; Lines didn't cross, because the intersection was beyond the end points of the lines EndIf Return False ; Lines do not cross End Function ; polygon_clockwise: Returns true if user inputted polygon in clockwise order, false if counterclockwise. ; The Law of Cosines is used to determine the angle. Function polygon_clockwise() 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))) theta = ACos((bb + cc - aa) / (2 * bb * bb * cc * cc)) 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))) theta = ACos((bb + cc - aa) / (2 * bb * bb * cc * cc)) 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 EndIf If (convex_sum >= (2 * 3.14159)) Then Return True Else Return False End Function Function draw_fill_triangle(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 EndIf If x1 > x3 Then p = x3 : x3 = x1 : x1 = p : q = y3 : y3 = y1 : y1 = q EndIf If x2 > x3 Then p = x3 : x3 = x2 : x2 = p : q = y3 : y3 = y2 : y2 = q EndIf 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 http://www.blitzbasic.com/Community/posts.php?topic=26539 The notions I'm trying to find in this is about outer node and inner node, and see what can be done to add the feature there. Here's something I meditate on: http://www.cs.cmu.edu/~quake/triangle.html More meditation: http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Mesh_2/Chapter_main.html

_33 (Posted 2007) [#6]

I've cleaned up and updated the code in the previous reply, for whoever needs it. Much cleaner, but still doesn't cover all the cases: - holes in surface - figure in hole in surface - hole in figure in hole in surface - multiple figures in surface The "hierarchies of polygons" concept is still blowing my mind, but I'm yet to fully understand the triangulation process to sort this out, so I'm far behind in this. Any help truely appreciated. Cheers.

Difference (Posted 2007) [#7]

@_33 : The "hierarchies of polygons" is simpler than you think. When you can triangulate and do hole(s) in polys you are almost done. Sort the polys by size. Take the biggest one and find it's hole(s) Triangulate those, disregarding the rest. Delete the biggest one and it's holes polys from the poly list. Start over until you've done all.