I've been working with triangulation methods for a while now and I've tried a couple different algorithms.
Some are easier to implement, but lack in the speed department. Others can be tougher to implement, but are very fast.
I'm talking 100,000 points in just a few seconds fast.
I'd say my favorite so far is the Delaunay triangulation which is a commonly used algorithm in this field.
It works with point lists and so far I've never seen a shape it can't triangulate.
The basic version only works for 2D shapes, but by changing circumcircles to circumspheres you can also use it for 3D shapes.
Here's a link if you'd like to read a little about it.
http://en.wikipedia.org/wiki/Delaunay_triangulation
Delaunay triangulation is most likely a little overboard for what your doing though.
No point in doing a lot of extra work if you'll never need it.
So, If your just trying to triangulate a closed bezier-path (like a road).
You could connect the points across from each other and then split that quad into two triangles.
Triangualte Point List
Re: Triangualte Point List
Here is a triangulation method from the book Computer Graphics for JAVA Programmers by Leen Ammeraal:
German forum:
- kleiner "Wavefront (.obj) to OGRE (.mesh)" - Konverter
The relevant part:
You call Triangulate() with a point list and it outputs a triangle list.
German forum:
- kleiner "Wavefront (.obj) to OGRE (.mesh)" - Konverter
The relevant part:
Code: Select all
Structure vtx_fce
x.f
y.f
z.f
face.i
EndStructure
Structure triangle
p1.vtx_fce
p2.vtx_fce
p3.vtx_fce
EndStructure
;--------------------------------------------------------------------------------------
; Triangulation of Polygons
;
; Book: Computer Graphics for JAVA Programmers
;
; by: Leen Ammeraal
;
; ISBN: 0-471-98142-7
;
; http://www.amazon.com/Computer-Graphics-Java-Programmers-Ammeraal/dp/0471981427/
;
;--------------------------------------------------------------------------------------
Procedure.f Area(*A.vtx_fce, *B.vtx_fce, *C.vtx_fce)
ProcedureReturn ( (*A\x - *C\x) * (*B\y - *C\y) - (*A\y - *C\y) * (*B\x - *C\x) )
EndProcedure
Procedure InsideTriangle(*A.vtx_fce, *B.vtx_fce, *C.vtx_fce, *P.vtx_fce)
; *A, *B, *C is assumed to be counter-clockwise
If Area(*A,*B,*P) >= 0 And Area(*B,*C,*P) >= 0 And Area(*C,*A,*P) >= 0
ProcedureReturn #True
EndIf
EndProcedure
Procedure ccw(Array P.vtx_fce(1))
Protected n = ArraySize( P() )
Protected k = 0, i = 1
While i < n
If (P(i)\x <= P(k)\x And (P(i)\x < P(k)\x Or P(i)\y < P(k)\y))
k = i
EndIf
i + 1
Wend
; P(k) is a convex vertex.
Protected _prev = k - 1, _next = k + 1
If (_prev = -1) : _prev = n - 1 : EndIf
If (_next = n) : _next = 0 : EndIf
If Area(@P(_prev), @P(k), @P(_next)) > 0.0
ProcedureReturn #True
EndIf
ProcedureReturn #False
EndProcedure
Procedure Triangulate(Array P.vtx_fce(1), List tri.triangle())
; P contains all n polygon verices in CCW order.
; the resulting triangles will be stored in linked list tri().
Protected n = ArraySize( P() )
If n < 3
ProcedureReturn #False
EndIf
ClearList( tri() )
Protected i = 0, j = n - 1
Protected iA, iB, iC
Dim _next.i(n)
While i < n
_next(j) = i
j = i
i + 1
Wend
Protected k
While k < n-2
; Find a suitable triangle, consisting of two edges
; and an internal diagonal:
Protected.vtx_fce A, B, C
Protected triaFound
Protected count
triaFound = #False
count = 0
While triaFound=#False And count < n
iB = _next(iA)
iC = _next(iB)
A = P(iA) : B = P(iB) : C = P(iC)
If Area(@A,@B,@C) >= 0.0
; Edges AB and BC; diagonal AC.
; Test to see of no other polygon vertex
; lies within triangle ABC:
j = _next(iC)
While j <> iA And InsideTriangle(@A, @B, @C, @P(j))=0
j = _next(j)
Wend
If j = iA
AddElement(tri())
tri()\p1 = A
tri()\p2 = B
tri()\p3 = C
_next(iA) = iC
triaFound = #True
EndIf
EndIf
iA = _next(iA)
count + 1
Wend
If count = n
;Debug "Not a simple polygon"
;ProcedureReturn
EndIf
k + 1
Wend
EndProcedure
;--------------------------------------------------------------------------------------Re: Triangualte Point List
Small example using 2D CanvasGadget. It displays 8 points that are added clockwise.
Code: Select all
Structure vtx_fce
x.f
y.f
z.f
face.i
EndStructure
Structure triangle
p1.vtx_fce
p2.vtx_fce
p3.vtx_fce
EndStructure
;--------------------------------------------------------------------------------------
; Triangulation of Polygons
;
; Book: Computer Graphics for JAVA Programmers
;
; by: Leen Ammeraal
;
; ISBN: 0-471-98142-7
;
; http://www.amazon.com/Computer-Graphics-Java-Programmers-Ammeraal/dp/0471981427/
;
;--------------------------------------------------------------------------------------
Procedure.f Area(*A.vtx_fce, *B.vtx_fce, *C.vtx_fce)
ProcedureReturn ( (*A\x - *C\x) * (*B\y - *C\y) - (*A\y - *C\y) * (*B\x - *C\x) )
EndProcedure
Procedure InsideTriangle(*A.vtx_fce, *B.vtx_fce, *C.vtx_fce, *P.vtx_fce)
; *A, *B, *C is assumed to be counter-clockwise
If Area(*A,*B,*P) >= 0 And Area(*B,*C,*P) >= 0 And Area(*C,*A,*P) >= 0
ProcedureReturn #True
EndIf
EndProcedure
Procedure ccw(Array P.vtx_fce(1))
Protected n = ArraySize( P() )
Protected k = 0, i = 1
While i < n
If (P(i)\x <= P(k)\x And (P(i)\x < P(k)\x Or P(i)\y < P(k)\y))
k = i
EndIf
i + 1
Wend
; P(k) is a convex vertex.
Protected _prev = k - 1, _next = k + 1
If (_prev = -1) : _prev = n - 1 : EndIf
If (_next = n) : _next = 0 : EndIf
If Area(@P(_prev), @P(k), @P(_next)) > 0.0
ProcedureReturn #True
EndIf
ProcedureReturn #False
EndProcedure
Procedure Triangulate(Array P.vtx_fce(1), List tri.triangle())
; P contains all n polygon verices in CCW order.
; the resulting triangles will be stored in linked list tri().
Protected n = ArraySize( P() )
If n < 3
ProcedureReturn #False
EndIf
ClearList( tri() )
Protected i = 0, j = n - 1
Protected iA, iB, iC
Dim _next.i(n)
While i < n
_next(j) = i
j = i
i + 1
Wend
Protected k
While k < n-2
; Find a suitable triangle, consisting of two edges
; and an internal diagonal:
Protected.vtx_fce A, B, C
Protected triaFound
Protected count
triaFound = #False
count = 0
While triaFound=#False And count < n
iB = _next(iA)
iC = _next(iB)
A = P(iA) : B = P(iB) : C = P(iC)
If Area(@A,@B,@C) >= 0.0
; Edges AB and BC; diagonal AC.
; Test to see of no other polygon vertex
; lies within triangle ABC:
j = _next(iC)
While j <> iA And InsideTriangle(@A, @B, @C, @P(j))=0
j = _next(j)
Wend
If j = iA
AddElement(tri())
tri()\p1 = A
tri()\p2 = B
tri()\p3 = C
_next(iA) = iC
triaFound = #True
EndIf
EndIf
iA = _next(iA)
count + 1
Wend
If count = n
;Debug "Not a simple polygon"
;ProcedureReturn
EndIf
k + 1
Wend
EndProcedure
;--------------------------------------------------------------------------------------
Dim points.vtx_fce(8)
NewList triangles.triangle()
If OpenWindow(0, 0, 0, 800, 600, "CanvasGadget", #PB_Window_SystemMenu | #PB_Window_ScreenCentered)
CanvasGadget(0, 0, 0, 800, 600)
points(0)\x = 400 : points(0)\y = 10
points(1)\x = 500 : points(1)\y = 200
points(2)\x = 700 : points(2)\y = 300
points(3)\x = 600 : points(3)\y = 350
points(4)\x = 400 : points(4)\y = 580
points(5)\x = 300 : points(5)\y = 400
points(6)\x = 100 : points(6)\y = 300
points(7)\x = 150 : points(7)\y = 150
Triangulate(Points(),triangles())
If StartDrawing(CanvasOutput(0))
ForEach triangles()
Circle(triangles()\p1\x, triangles()\p1\y, 10, RGB(0,0,255))
Circle(triangles()\p2\x, triangles()\p2\y, 10, RGB(0,0,255))
Circle(triangles()\p3\x, triangles()\p3\y, 10, RGB(0,0,255))
LineXY( triangles()\p1\x, triangles()\p1\y, triangles()\p2\x, triangles()\p2\y, RGB(0,255,0))
LineXY( triangles()\p2\x, triangles()\p2\y, triangles()\p3\x, triangles()\p3\y, RGB(0,255,0))
LineXY( triangles()\p3\x, triangles()\p3\y, triangles()\p1\x, triangles()\p1\y, RGB(0,255,0))
Next
StopDrawing()
EndIf
Debug ListSize( triangles() )
Repeat : Until WaitWindowEvent() = #PB_Event_CloseWindow
EndIf