PolyTry Blitz Version


Tweet blitz3d code-archives mesh
(Posted 4 months ago) RonTek

A Blitz implementation of the PolyTry code.

An example is located at the bottom of the source code. It's not exceptionally well commented, but I'm sure you will figure out how to use it, it's very easy. If you don't understand what it does, you probably have no use for it, so just walk away, whistling :)

It can be used for both 2D and 3D polygons, but since it is mostly geared at 3D it's located here in the 3D Graphics Code Archives.

Author: fredborg

Image

;
; Tesselate
;
; Converted from the original PolyTry source code by Peppino Sbargzeguti
; http://www.codeproject.com/useritems/polygon_tesselation.asp
;
; Blitz Version by Mikkel Fredborg
;

Const VERTEXLIMIT   = 999

Const DEGENERATE    = 0
Const CONCAVE       = 1
Const CONVEX        = 2

Type tessVert
    Field x#,y#,z#,u#,v#,n
End Type

Type tessSurf
    Field v0.tessVert[VERTEXLIMIT]
    Field v1.tessVert[VERTEXLIMIT]
    Field v2.tessVert[VERTEXLIMIT]
    Field n_tris
End Type

Dim tsv.tessVert(0)

Global mE0x#,mE0y#,mE0z#    
Global mE1x#,mE1y#,mE1z#                
Global mNx#,mNy#,mNz#,mA#
Global tessNx#,tessNy#,tessNz#

Function tess_Clean()

    Delete Each tessVert
    Delete Each tessSurf

End Function

Function tess_AddVert(x#,y#,z#=0.0,u#=0.0,v#=0.0)

    p.tessVert = Last tessVert
    If (p = Null)
        n = 0
    Else
        n = p\n+1
    End If

    p.tessVert = New tessVert
    p\x     = x
    p\y     = y
    p\z     = z
    p\u     = u
    p\v     = v
    p\n     = n

End Function

Function tess_ComputeNormal()

    tessNx# = 0.0
    tessNy# = 0.0
    tessNz# = 0.0

    For a.tessVert = Each tessVert
        b.tessVert = After a
        If b = Null Then Exit

        tessNx = tessNx + ((a\y - b\y ) * ( a\z + b\z))
        tessNy = tessNy + ((a\z - b\z ) * ( a\x + b\x))
        tessNz = tessNz + ((a\x - b\x ) * ( a\y + b\y))
    Next

    ; Normalize it, not really nescessary
    ; just nicer to look at :)
    Local d# = Sqr(tessNx*tessNx + tessNy*tessNy + tessNz*tessNz)
    If d>0.0
        tessNx = tessNx/d
        tessNy = tessNy/d
        tessNz = tessNz/d
    End If

End Function

Function tess_Triangulate()

    Local n_tris = 0
    Local n_verts = 0
    Local noErrors = True

    ; Close the polygon, by adding the first vert after the last
    p.tessVert = First tessVert
    If Not (p=Null)
        tess_AddVert(p\x,p\y,p\z,p\u,p\v)
    End If

    ; Get the normal of the entire polygon
    tess_ComputeNormal()

    ; Count number of vertices
    n_verts = -1
    For p.tessVert = Each tessVert
        n_verts = n_verts + 1
    Next

    ; Index the vertices
    Dim tsv(n_verts)
    n = 0
    For p.tessVert = Each tessVert
        tsv(n) = p
        n = n + 1
    Next

    ; Prepare a TessSurf
    surf.TessSurf   = New TessSurf
    surf\n_tris     = 0

    ; Now it gets funny
    While n_verts=>3 And noErrors = True

        noErrors = False

        i = 0
        j = 1
        k = 2
        While k<(n_verts+3)
            If n_verts=0 Then Exit

            ib = i Mod n_verts
            jb = j Mod n_verts
            kb = k Mod n_verts

            Select tess_TriangleArea(ib,jb,kb)
                Case CONVEX:
                    If tess_IsAnyPointInside(ib,jb,kb,n_verts) 
                        ; Triangle is ok, but it cross another part of the polygon
                        i = j
                        j = k
                        k = k + 1
                    Else
                        ; Triangle is ok, so build it
                        tess_AddTriangle(surf,ib,jb,kb)
                        n_tris   = n_tris + 1
                        n_verts  = tess_RemoveVertex(jb,n_verts)
                        noErrors = True
                    End If

                Case CONCAVE:
                    ; Triangle faces the wrong way
                    i = j
                    j = k
                    k = k + 1

                Case DEGENERATE:
                    ; Bad triangle (zero area)
                    n_verts  = tess_RemoveVertex(jb,n_verts)
                    noErrors = True

            End Select
        Wend

    Wend

    Return n_tris

End Function

Function tess_TriangleArea(i,j,k)

    Local v0.tessVert = tsv(i)
    Local v1.tessVert = tsv(j)
    Local v2.tessVert = tsv(k)

    mE0x# = v0\x-v2\x
    mE0y# = v0\y-v2\y
    mE0z# = v0\z-v2\z

    mE1x# = v1\x-v2\x
    mE1y# = v1\y-v2\y
    mE1z# = v1\z-v2\z               

    mNx# = mE0y * mE1z - mE0z * mE1y
    mNy# = mE0z * mE1x - mE0x * mE1z
    mNz# = mE0x * mE1y - mE0y * mE1x

    mA# = (mNx*mNx + mNy*mNy + mNz*mNz)

    If Abs(mA) < 0.000001
        Return DEGENERATE
    End If

    If (mNx#*tessNx# + mNy#*tessNy# + mNz#*tessNz#) < 0.0
        Return CONCAVE
    Else
        Return CONVEX
    End If

End Function

Function tess_RemoveVertex(j,n_verts)

    For i = j+1 To n_verts
        tsv(i-1)=tsv(i)
    Next
    Return n_verts-1

End Function

Function tess_AddTriangle(surf.tessSurf,i,j,k)

    surf\v0[ surf\n_tris ] = tsv(i)
    surf\v1[ surf\n_tris ] = tsv(j)
    surf\v2[ surf\n_tris ] = tsv(k)
    surf\n_tris = surf\n_tris + 1
    Return surf\n_tris

End Function

Function tess_IsAnyPointInside(i,j,k,n_verts)

    For ip=0 To n_verts
        If (ip<i) Or (ip>k)
            If tess_IsPointInside(tsv(ip),tsv(k))
                Return True
            End If
        End If
    Next

    Return False

End Function

Function tess_IsPointInside(point.tessVert,q2.tessVert)

    Local pmq2x# = point\x - q2\x
    Local pmq2y# = point\y - q2\y
    Local pmq2z# = point\z - q2\z       

    Local ntmpx# = 0.0
    Local ntmpy# = 0.0
    Local ntmpz# = 0.0

    Local b0# = 0.0
    Local b1# = 0.0

    ntmpx# = pmq2y * mE1z - pmq2z * mE1y
    ntmpy# = pmq2z * mE1x - pmq2x * mE1z
    ntmpz# = pmq2x * mE1y - pmq2y * mE1x
    b0# = mNx*ntmpx + mNy*ntmpy + mNz*ntmpz
    If b0 <= 0.0 Then Return False

    ntmpx# = mE0y * pmq2z - mE0z * pmq2y
    ntmpy# = mE0z * pmq2x - mE0x * pmq2z
    ntmpz# = mE0x * pmq2y - mE0y * pmq2x
    b1# = mNx*ntmpx + mNy*ntmpy + mNz*ntmpz
    If b1 <= 0.0 Then Return False

    If (mA-B0-B1)>0.0
        Return True
    Else
        Return False
    End If

End Function

Function tess_TriNormal(v0x#,v0y#,v0z#,v1x#,v1y#,v1z#,v2x#,v2y#,v2z#)

    ax#=v1x-v0x
    ay#=v1y-v0y
    az#=v1z-v0z

    bx#=v2x-v1x
    by#=v2y-v1y
    bz#=v2z-v1z

    tessNx#=(ay#*bz#)-(az#*by#)
    tessNy#=(az#*bx#)-(ax#*bz#)
    tessNz#=(ax#*by#)-(ay#*bx#)

End Function



;
; Example usage
;
; 
Graphics3D 640,480,0,2
SetBuffer BackBuffer()

wire=False
WireFrame wire

camera = CreateCamera()
PositionEntity camera,0,0,0

mesh = CreateMesh()
surf = CreateSurface(mesh)
EntityColor mesh,255,0,0

box = CreateCube()
PositionEntity box,1,0,3
ScaleEntity box,1,1,2
RotateEntity box,0,40,0
EntityPickMode box,2

Repeat

    TurnEntity box,KeyDown(200)-KeyDown(208),KeyDown(203)-KeyDown(205),0

    If MouseHit(1)

        If cleanme
            Cls 
            cleanme = False
            ClearSurface surf
        End If

        If CameraPick(camera,MouseX(),MouseY())
            x# = PickedX()+(PickedNX()*0.01)
            y# = PickedY()+(PickedNY()*0.01)
            z# = PickedZ()+(PickedNZ()*0.01)            
            tess_AddVert(x,y,z)
        End If

    End If

    If MouseHit(2)
        tris = tess_Triangulate()

        ;
        ; Build a real 3D surface from the tessSurf
        ClearSurface surf
        For tessVert.TessVert = Each TessVert
            AddVertex surf,tessVert\x,tessVert\y,tessVert\z
        Next
        tessSurf.TessSurf = First TessSurf
        For t = 0 To tessSurf\n_tris-1
            AddTriangle surf,tessSurf\v0[t]\n,tessSurf\v1[t]\n,tessSurf\v2[t]\n
        Next        
        UpdateNormals mesh

        ;
        ; Clean up :)
        tess_Clean()

        cleanme = True
    End If

    If KeyHit(17)
        wire = Not wire
        WireFrame wire
    End If

    If KeyHit(57)
        FlipMesh mesh
    End If

    RenderWorld

    ;
    ; Draw the building wire polygon thingy
    x1 = -1
    y1 = -1
    For tessvert.tessvert = Each tessvert
        Color 255,0,0
        CameraProject camera,tessvert\x,tessvert\y,tessvert\z
        x0 = ProjectedX()
        y0 = ProjectedY()
        Rect x0-1,y0-1,3,3
        If x1<>-1
            Color 255,255,255
            Line x0,y0,x1,y1
        End If
        x1 = x0
        y1 = y0
    Next

    ;
    ; Show Vertex normals
    n_verts = CountVertices(surf)-1
    For v = 0 To n_verts
        TFormPoint VertexX(surf,v),VertexY(surf,v),VertexZ(surf,v),mesh,0
        CameraProject camera,TFormedX(),TFormedY(),TFormedZ()
        x0 = ProjectedX()
        y0 = ProjectedY()

        TFormPoint VertexX(surf,v)+(VertexNX(surf,v)*0.1),VertexY(surf,v)+(VertexNY(surf,v)*0.1),VertexZ(surf,v)+(VertexNZ(surf,v)*0.1),mesh,0
        CameraProject camera,TFormedX(),TFormedY(),TFormedZ()
        x1 = ProjectedX()
        y1 = ProjectedY()

        Color 255,255,0
        Line x0,y0,x1,y1
    Next

    Color 255,255,255
    Text 320,  0,"Tris - "+tris+" | Time - "+ms+" ms",True
    Text 320,460,"Left Mouse - Add Vertex | Right Mouse - Triangulate | Space - Flip Mesh",True

    Flip

Until KeyHit(1)

End

Reply To Topic (minimum 10 characters)

Please log in to reply