PureBasic Forums - English

Posted: **Wed Dec 25, 2013 1:41 am**

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.

Posted: **Wed Dec 25, 2013 1:19 pm**

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:

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

;--------------------------------------------------------------------------------------

You call Triangulate() with a point list and it outputs a triangle list.

Posted: **Wed Dec 25, 2013 3:19 pm**

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

PureBasic Forums - English

Triangualte Point List

Re: Triangualte Point List

Re: Triangualte Point List

Re: Triangualte Point List