;==================================================================
;  Project Title : Simple Quadtree Demo
;
;  Author : Seyhajin
;
;  Email : seyhajin@hotmail.com
;
;  Website : http://www.seyhajin.com
;            http://bond357.free.fr/main/forums/viewtopic.php?id = 10
;
;  Version : 1.0
;
;  Date : 12/03/2006
;
;  Notes : Utilisation du Quadtree et du Frustum Culling, dans un univers 2D.
;
;  Commandes :
;      - Touches direct. : Bouge la camera
;      - Mouse : Definit l'orientation de la camera
;
;  References :
;      - mon poto Google :o)
;      - http://www.flipcode.com/articles/article_frustumculling.shtml
;      - http://deptinfo.unice.fr/twiki/bin/view/Minfo03/AlgosJeux3DRapportFrustum
;
;==================================================================


; Definit le Frustum
Global p1.POINT, p2.POINT

Macro CosD(x)
  Cos((x)*0.0174532)
EndMacro
Macro SinD(x)
  Sin((x)*0.0174532)
EndMacro

; Enfants du Quadtree
Enumeration
  #CHILD00
  #CHILD01
  #CHILD11
  #CHILD10
EndEnumeration


; CAMERA
Structure CAMERA
  x.l      ; Position de la camera
  y.l      ; Position de la camera
  fov.l      ; Angle de vue
EndStructure

; QUADTREE
Structure QUADTREE
  xmin.l              ; Coordonnées du sommet haut gauche
  ymin.l              ; Coordonnées du sommet haut gauche
  xmax.l              ; Coordonnées du sommet bas droite
  ymax.l              ; Coordonnées du sommet bas droite
  *Child.QUADTREE[4]  ; Les 4 enfants du quadtree
EndStructure

; creation d'une camera
; creation d'une camera
Procedure Camera(x, y, fov)
  *this.CAMERA = AllocateMemory(SizeOf(CAMERA))
  *this\x = x : *this\y = y : *this\fov = fov
  ProcedureReturn *this
EndProcedure

; Renvoie True si un point est dans le plan Left du Frustum
Procedure PointInFrustumL(*this.CAMERA, x, y)
  If(-(x - *this\x) *(p1\y - *this\y) +(y - *this\y) *(p1\x - *this\x) >= 0)
    ProcedureReturn #True
  Else
    ProcedureReturn #False
  EndIf
EndProcedure

; Renvoie True si un point est dans le plan Right du Frustum
Procedure PointInFrustumR(*this.CAMERA, x, y)
  If( -(x - *this\x) *(p2\y - *this\y) +(y - *this\y) *(p2\x - *this\x) <= 0)
    ProcedureReturn #True
  Else
    ProcedureReturn #False
  EndIf
EndProcedure

; Renvoie True si un point est dans le plan Front du Frustum (pas utilisé ici)
Procedure PointInFrustumF(*this.CAMERA, x, y)
  ProcedureReturn( -(x - *this\x) *(p3y - *this\y) +(y - *this\y) *(p3x - *this\x) >= 0)
EndProcedure

; Creation d'un quadtree de profondeur depth
; et associé à un carré de cotés xmax-xmin, ymax-ymin
Procedure Quadtree(xmin, ymin, xmax, ymax, depth)
  *this.QUADTREE = AllocateMemory(SizeOf(QUADTREE))
  *this\xmin = xmin
  *this\xmax = xmax
  *this\ymin = ymin
  *this\ymax = ymax

  If(depth > 0)
    ; On crée 4 enfants
    xmoy =(xmin + xmax) / 2
    ymoy =(ymin + ymax) / 2
    depth = depth - 1
    *this\Child[#CHILD00] = Quadtree(xmin, ymin, xmoy, ymoy, depth) ; Haut gauche
    *this\Child[#CHILD01] = Quadtree(xmin, ymoy, xmoy, ymax, depth) ; Bas gauche
    *this\Child[#CHILD11] = Quadtree(xmoy, ymoy, xmax, ymax, depth) ; Bas droite
    *this\Child[#CHILD10] = Quadtree(xmoy, ymin, xmax, ymoy, depth) ; Haut droite
  EndIf
  ProcedureReturn *this
EndProcedure

; On teste si un des 4 sommets du carré associé au quadtree
; est visible par la camera
Procedure QuadInFrustum(*this.QUADTREE, *cam.CAMERA)
  Define nbPlansInterieur

  ; Plan de gauche
  nbPlansInterieur = 0
  nbPlansInterieur = nbPlansInterieur + PointInFrustumL(*cam, *this\xmin, *this\ymin)
  nbPlansInterieur = nbPlansInterieur + PointInFrustumL(*cam, *this\xmin, *this\ymax)
  nbPlansInterieur = nbPlansInterieur + PointInFrustumL(*cam, *this\xmax, *this\ymin)
  nbPlansInterieur = nbPlansInterieur + PointInFrustumL(*cam, *this\xmax, *this\ymax)
  If nbPlansInterieur = 0 : ProcedureReturn #False : EndIf

  ; Plan de droite
  nbPlansInterieur = 0
  nbPlansInterieur = nbPlansInterieur + PointInFrustumR(*cam, *this\xmin, *this\ymin)
  nbPlansInterieur = nbPlansInterieur + PointInFrustumR(*cam, *this\xmin, *this\ymax)
  nbPlansInterieur = nbPlansInterieur + PointInFrustumR(*cam, *this\xmax, *this\ymin)
  nbPlansInterieur = nbPlansInterieur + PointInFrustumR(*cam, *this\xmax, *this\ymax)
  If nbPlansInterieur = 0 : ProcedureReturn #False : EndIf

  ProcedureReturn #True
EndProcedure

; Rendu du Quadtree
Procedure RenderQuadtree(*this.QUADTREE, *cam.CAMERA, depth)
  If QuadInFrustum(*this, *cam)
    If(depth > 1)
      FrontColor(#Gray)
      LineXY((*this\xmin +*this\xmax)/2, *this\ymin,(*this\xmin +*this\xmax)/2, *this\ymax)
      LineXY(*this\xmin,(*this\ymin +*this\ymax)/2, *this\xmax,(*this\ymin +*this\ymax)/2)
     
      depth = depth - 1
     
      RenderQuadtree(*this\Child[#CHILD00], *cam, depth)
      RenderQuadtree(*this\Child[#CHILD01], *cam, depth)
      RenderQuadtree(*this\Child[#CHILD11], *cam, depth)
      RenderQuadtree(*this\Child[#CHILD10], *cam, depth)
    Else
      FrontColor(RGB(196, 196, 196))
      Box(*this\xmin + 1, *this\ymin + 1, *this\xmax -*this\xmin - 1, *this\ymax -*this\ymin - 1)
    EndIf
  EndIf
EndProcedure

Procedure.f Atan2(y.f, x.f)
  !fld dword[p.v_y]
  !fld dword[p.v_x]
  !fpatan
  ProcedureReturn
EndProcedure

;==============================================================================================
; EXAMPLE
;==============================================================================================

InitSprite()
InitMouse()
InitKeyboard()
OpenScreen(800, 600, 32, "Simple Quadtree Demo - Seyhajin")
; Variables de configuration
QuadDepth = 6            ; Profondeur du quadtree (nb de fois qu'on decoupe le plan)
QuadSize = 599           ; Taille initiale du quadtree
CamSpeed.f = 2           ; Vitesse de deplacement de la camera
CamFOV.f = 60.0 / 2.0    ; Angle de vue de la camera (default = 90)
ViewLine = 200           ; Taille de la ligne des plans

; Creation de la camera
*cam.CAMERA = camera(QuadSize/2, QuadSize/2, CamFOV)
; Creation du Quadtree principale
*root.QUADTREE = Quadtree(0, 0, QuadSize, QuadSize, QuadDepth)

;----------------------------------
; BOUCLE PRINCIPALE
;----------------------------------
Repeat

  ClearScreen(#Black)
 

  ; Update Camera position
  ExamineKeyboard()
  If KeyboardPushed(#PB_Key_Up)
    *cam\y = *cam\y - CamSpeed
  ElseIf KeyboardPushed(#PB_Key_Down)
    *cam\y = *cam\y + CamSpeed
  EndIf
  If KeyboardPushed(#PB_Key_Left)
    *cam\x = *cam\x - CamSpeed
  ElseIf KeyboardPushed(#PB_Key_Right)
    *cam\x = *cam\x + CamSpeed
  EndIf
 
  If ExamineMouse()
    x.f = MouseX() - *cam\x
    y.f = MouseY() - *cam\y
    angle.f = 180 +(ATan2(- y, - x)*57.295779)
  EndIf

  ; Rendu du quadtree
  StartDrawing(ScreenOutput())
  Box(*root\xmin, *root\ymin, *root\xmax, *root\ymax, #White)
  RenderQuadtree(*root, *cam, QuadDepth)

  ; Dessine la pyramide de vue (Frustum)
  LineXY(*cam\x, *cam\y, *cam\x +(ViewLine/2)*CosD(angle), *cam\y +(ViewLine/2)*SinD(angle), #Yellow)
  ; Plan gauche
  p1\x = *cam\x + ViewLine*CosD(angle - CamFOV)
  p1\y = *cam\y + ViewLine*SinD(angle - CamFOV)
  LineXY(*cam\x, *cam\y, p1\x, p1\y, #Red)
  ; Plan droit
  p2\x = *cam\x + ViewLine*CosD(angle + CamFOV)
  p2\y = *cam\y + ViewLine*SinD(angle + CamFOV)
  LineXY(*cam\x, *cam\y, p2\x, p2\y, #Red)
  ; Dessine la camera
  Circle(*cam\x, *cam\y, 6, #Blue)
  StopDrawing()
  FlipBuffers()
Until KeyboardPushed(#PB_Key_Escape)