Graphics3D 800,600,32,1
SetBuffer BackBuffer()

Global FPSSEC = MilliSecs()
Global FPS
Global FRAMES
Global RETURNED

SeedRnd MilliSecs()

camera = CreateCamera()
light = CreateLight()
mesh = LoadMesh("map\rooms.b3d")
pitch# = 90
PositionEntity camera,60,170,-60


MoveMouse GraphicsWidth()/2,GraphicsHeight()/2
While Not KeyHit(1)
 Cls
 UpdateWorld
 RenderWorld

 Text 0,0,"Press Space to toggle WireFrame"
 Text 0,20,"Use Mouse and WASD to move"
 Text 0,40,"Tris: "+TrisRendered()
 Text 0,60,"Press Return to optimize the Map"
 Text 0,80,"Fps: "+Fps()

 If KeyHit(57) Then wire=1-wire
 WireFrame wire

 pitch# = pitch# + MouseYSpeed()*0.1
 yaw# = yaw# - MouseXSpeed()*0.1
 RotateEntity camera,pitch#,yaw#,0
 MoveMouse GraphicsWidth()/2,GraphicsHeight()/2

 If KeyDown(17) Then MoveEntity camera,0,0,0.8
 If KeyDown(31) Then MoveEntity camera,0,0,-0.8
 If KeyDown(30) Then MoveEntity camera,-0.8,0,0
 If KeyDown(32) Then MoveEntity camera,0.8,0,0

 If KeyHit(28) And pressed = 0 Then
  pressed = 1
  OptimizeMap(mesh,800)

  For o.optimize_mesh = Each optimize_mesh
   EntityColor o\mesh,Rand(100,255),Rand(100,255),Rand(100,255)
  Next
 EndIf

 Flip 0
Wend
ClearWorld
End

Function OptimizeMap(mesh,tris%=300)

   If CountTris(mesh) > tris% Then
    o.optimize_mesh = New optimize_mesh
    o\mesh = mesh
    o\optimized = 0
   
    Repeat
     count = 0
     For o.optimize_mesh = Each optimize_mesh
      If o\optimized = 0 Then
       count = count + 1
   
       DivideMesh(o\mesh)
   
       For d.divided_mesh = Each divided_mesh
        If d = Last divided_mesh Then
         For I = 0 To 3
          o2.optimize_mesh = New optimize_mesh
          o2\mesh = d\mesh[I]
          o2\optimized = 0
          If CountTris(o2\mesh) =< tris% Then o2\optimized = 1
         Next
         Delete d
        EndIf
       Next
   
       Delete o
   
      EndIf
     Next
    Until count = 0
   EndIf
   
   For d.divided_mesh = Each divided_mesh
    Delete d
   Next
   
   Return

End Function

Function DivideMesh(mesh)

   Local vertex_left#,vertex_right#,vertex_front#,vertex_back#
   Local divide_x#,divide_z#
   Local vX#,vZ#, tX#,tZ#

    ; Ausdehnung ermitteln
   For surfcount = 1 To CountSurfaces(mesh)
    surface = GetSurface(mesh,surfcount)
    For tricount = 0 To CountTriangles(surface)-1
   
     For I = 0 To 2
      in = TriangleVertex(surface,tricount,I)
      If surfcount=1 And tricount=0 And I=0 Then
       vertex_left = VertexX(surface,in)
       vertex_right = VertexX(surface,in)
       vertex_back = VertexZ(surface,in)
       vertex_front = VertexZ(surface,in)
      Else
       If vertex_left > VertexX(surface,in) Then vertex_left = VertexX(surface,in)
       If vertex_right < VertexX(surface,in) Then vertex_right = VertexX(surface,in)
       If vertex_back > VertexZ(surface,in) Then vertex_back = VertexZ(surface,in)
       If vertex_front < VertexZ(surface,in) Then vertex_front = VertexZ(surface,in)
      EndIf
     Next
   
    Next
   Next
   
   divide_x# = (vertex_right#+vertex_left#)/2
   divide_z# = (vertex_front#+vertex_back#)/2
   ; ***
   
   ; mesh erstellen
   d.divided_mesh = New divided_mesh
   For I = 0 To 3
    d\mesh[I] = CreateMesh()
   
    ; tris-positionen ermitteln
    For surfcount = 1 To CountSurfaces(mesh)
     surface = GetSurface(mesh,surfcount)
     For tricount = 0 To CountTriangles(surface)-1
   
      vX# = 0 : vZ# = 0
      For J = 0 To 2
       in = TriangleVertex(surface,tricount,J)
       vX# = vX# + VertexX(surface,in)
       vZ# = vZ# + VertexZ(surface,in)
      Next
      tX# = vX# / 3 : tZ# = vZ# / 3
   
      inarea = 0
      Select I
      Case 0
       If tX# < divide_x# And tZ# < divide_z# Then inarea = 1
      Case 1
       If tX# >= divide_x# And tZ# < divide_z# Then inarea = 1
      Case 2
       If tX# < divide_x# And tZ# >= divide_z# Then inarea = 1
      Case 3
       If tX# >= divide_x# And tZ# >= divide_z# Then inarea = 1
      End Select
   
      ; surface und vertizes speichern
      If inarea = 1 Then
   
       t.copy_triangle = New copy_triangle
       t\parent = surface
       For J = 0 To 2
        t\v[J] = TriangleVertex(surface,tricount,J)
       Next
   
       exist = 0
       For s.copy_surface = Each copy_surface
        If s\surface = surface Then exist = 1
       Next
       If exist=0 Then
        s.copy_surface = New copy_surface
        s\surface = surface
        s\brush = GetSurfaceBrush(s\surface)
       EndIf
   
       For J = 0 To 2
        in = TriangleVertex(surface,tricount,J)
        exist = 0
        For v.copy_vertex2 = Each copy_vertex2
         If v\vertex = in And v\parent = surface Then exist = 1
        Next
        If exist=0 Then
         v.copy_vertex2 = New copy_vertex2
         v\vertex = in
         v\parent = surface
        EndIf
       Next
   
      EndIf
   
     Next
    Next
   
    ; neuen mesh-block füllen
    For s.copy_surface = Each copy_surface
     count=0
     For v.copy_vertex2 = Each copy_vertex2
      If v\parent = s\surface Then count=1
     Next
     If count Then
   
      s\surf = CreateSurface(d\mesh[I])
      PaintSurface s\surf,s\brush
   
      For v.copy_vertex2 = Each copy_vertex2
       If v\parent = s\surface Then
        v\ver = AddVertex(s\surf,VertexX(s\surface,v\vertex),VertexY(s\surface,v\vertex),VertexZ(s\surface,v\vertex),VertexU(s\surface,v\vertex),VertexV(s\surface,v\vertex))
       EndIf
      Next
   
      For t.copy_triangle = Each copy_triangle
       If t\parent = s\surface Then
        
        For v.copy_vertex2 = Each copy_vertex2
         If v\parent = s\surface Then
          If v\vertex = t\v[0] Then v1 = v\ver
          If v\vertex = t\v[1] Then v2 = v\ver
          If v\vertex = t\v[2] Then v3 = v\ver
         EndIf
        Next
   
        AddTriangle s\surf,v1,v2,v3
   
         EndIf
      Next
     EndIf
    Next
    ; ***
   
    PositionEntity d\mesh[I],EntityX(mesh),EntityY(mesh),EntityZ(mesh)
    RotateEntity d\mesh[I],EntityPitch(mesh),EntityYaw(mesh),EntityRoll(mesh)
    UpdateNormals(d\mesh[I])
   
    For s.copy_surface = Each copy_surface
     Delete s
    Next
   
    For v.copy_vertex2 = Each copy_vertex2
     Delete v
    Next
   
    For t.copy_triangle = Each copy_triangle
     Delete t
    Next
   
   Next
   ; ***
   FreeEntity mesh
   
   Return

End Function

Function CountTris(mesh)

   Local count
   
   surf_count = CountSurfaces(mesh)
   For I = 1 To surf_count
    surf = GetSurface(mesh,I)
    tris_count = CountTriangles(surf)
    For E = 1 To tris_count
     count = count + 1
    Next
   Next
   
   Return count

End Function

Function FPS()
   FRAMES = FRAMES + 2
   RETURNED = 0
   If MilliSecs() - FPSSEC => 500 Then
      FPS = FRAMES
      RETURNED = 1
      FRAMES = 0
      FPSSEC = MilliSecs()
   EndIf
Return FPS
End Function

Type divided_mesh
 Field mesh[3]
End Type

Type copy_surface
 Field surface
 Field surf
 Field brush
End Type

Type copy_triangle
 Field parent
 Field v[2]
End Type

Type copy_vertex2
 Field parent
 Field vertex
 Field ver
End Type

Type optimize_mesh
 Field mesh
 Field optimized
End Type