Quadtree Raytracing Algorithmus

Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Neue Antwort erstellen

 

Boris1993

Betreff: Quadtree Raytracing Algorithmus

 BeitragSo, Jan 27, 2013 20:19
Antworten mit Zitat
Benutzer-Profile anzeigen
Dieses Programm schießt einen Strahl durch eine Quadtree Datenstruktur und überspringt die Kollisionsüberprüfung von leerem Raum weitestgehend. Dieser Algorithmus eignet sich auch für Octree Raytracing man muss nur eine weitere Dimension in das Programm einfügen.

Code: [AUSKLAPPEN]
SuperStrict

Framework BRL.GLMax2D
Import BRL.Random
Import BRL.StandardIO

SetGraphicsDriver GLMax2DDriver()
SeedRnd MilliSecs()

'Bildschirm-Breite/Höhe
Const ws:Float = 321

Graphics ws, ws, 0, 60
SetClsColor 255, 255, 255
SetBlend ALPHABLEND


Global size:Int = 16
Global maxlod:Byte = 4
Global lod:Byte = 4

'Create Map
Global qt:TQuadtree = New TQuadtree
qt.Write(14, 2, 16)
qt.Write(14, 4, 16)
qt.Write(4, 10, 16)
qt.Write(12, 6, 16)
qt.Write(9, 13, 16)


Global pos:Float[] = [0.5, 0.5]
Global dir:Float[] = [1.0, 0.0]
Global ang:Float

Global scl:Float = (ws-1)/size



Repeat
   Cls()
   
   Control()
   
   Ray(pos, dir)
   
   DrawOval(pos[0]*scl-2, pos[1]*scl-2, 5, 5)
   DrawLine(pos[0]*scl, pos[1]*scl, (pos[0]+dir[0]*20)*scl, (pos[1]+dir[1]*20)*scl)
   
   DrawQt(qt)
   
   DrawText("Movement: W,A,S,D", 5, 290)
   DrawText("Rotate: Left/Right-Keys", 5, 305)

   Flip(-1)
Until KeyHit(KEY_ESCAPE) Or AppTerminate()

End




Function Ray(pos:Float[], dir:Float[])
   Local x:Float = pos[0]
   Local y:Float = pos[1]
   Local dx:Float = dir[0]
   Local dy:Float = dir[1]
   Local bd:Float[4]
   Local tmx:Float
   Local tmy:Float
   Local ix:Int
   Local iy:Int
   
   
   For Local i:Int = 0 To 20
      If x >= size Then Exit
      If y >= size Then Exit
      If x <= 0.00001 Then Exit
      If y <= 0.00001 Then Exit
      
      If dx >= 0 Then
         ix = Int(x)
      Else
         ix = Int(x-0.00001)
      EndIf
      If dy >= 0 Then
         iy = Int(y)
      Else
         iy = Int(y-0.00001)
      EndIf
      
      SetAlpha 0.2
      SetColor 255, 0, 0
      BoxS(ix, iy, 1, scl)
      SetColor 0, 0, 0
      SetAlpha 1.0
      
      bd = New Float[4]
      
      If qt.GetState(ix, iy, size, bd) Then Exit
      bd[0] = bd[0]-x
      bd[1] = bd[1]-y
      bd[2] = x-bd[2]
      bd[3] = y-bd[3]
      
      If dx >= 0 Then
         tmx = bd[0]/dx
      Else
         tmx = bd[2]/Abs(dx)
      EndIf
      
      If dy >= 0 Then
         tmy = bd[1]/dy
      Else
         tmy = bd[3]/Abs(dy)
      EndIf
      
      If tmx < tmy Then
         x :+ tmx*dx
         y :+ tmx*dy
      Else
         x :+ tmy*dx
         y :+ tmy*dy
      EndIf
   Next
EndFunction


Function Control()
   If KeyHit(KEY_UP) And lod < maxlod Then lod:+1
   If KeyHit(KEY_DOWN) And lod > 1 Then lod:-1
   
   If KeyDown(KEY_RIGHT) Then
      ang:+1.2
      dir = [Float(Cos(ang)), Float(Sin(ang))]
   EndIf
   If KeyDown(KEY_LEFT) Then
      ang:-1.2
      dir = [Float(Cos(ang)), Float(Sin(ang))]
   EndIf
   If ang > 359.9 Then ang = 0
   If ang < 0 Then ang = 359.9
   
   If KeyDown(KEY_W) Then pos[1]:-0.2
   If KeyDown(KEY_A) Then pos[0]:-0.2
   If KeyDown(KEY_S) Then pos[1]:+0.2
   If KeyDown(KEY_D) Then pos[0]:+0.2
   
   If pos[0] < 0.01 Then pos[0] = 0.01
   If pos[1] < 0.01 Then pos[1] = 0.01
   If pos[0] > size-0.01 Then pos[0] = size-0.01
   If pos[1] > size-0.01 Then pos[1] = size-0.01
EndFunction


Function DrawQt(qt:TQuadtree, lvl:Byte = 0, sx:Int = 0, sy:Int = 0)
   Local order:Int[][] = [[0, 0], [1, 0], [0, 1], [1, 1]]
   Local ch:TQuadtree
   Local sh:Int[2]
   Local s:Int
   
   SetColor 0, 0, 0
   For Local i:Byte = 0 To 3
      ch = qt.child[i]
      sh = [sx, sy]
      s = (size/(2^(lvl+1)))
      For Local j:Byte = 0 To 1
         sh[j]:+order[i][j]*s
      Next
      
      BoxW(sh[0], sh[1], s, scl)
      
      If ch Then         
         If lvl < lod-1 Then
            DrawQt(ch, lvl+1, sh[0], sh[1])
         Else
            BoxS(sh[0], sh[1], s, scl)
         End If   
      End If
   Next
End Function


Function BoxW(x:Float, y:Float, size:Float, scale:Float)
   DrawLine x*scale, y*scale, (x+size)*scale, y*scale
   DrawLine (x+size)*scale, y*scale, (x+size)*scale, (y+size)*scale
   DrawLine (x+size)*scale, (y+size)*scale, x*scale, (y+size)*scale
   DrawLine x*scale, (y+size)*scale, x*scale, y*scale
End Function


Function BoxS(x:Float, y:Float, size:Float, scale:Float)
   DrawRect x*scale, y*scale, size*scale, size*scale
End Function



Type TQuadtree
   Field child:TQuadtree[4]
   
   Method Write(x:Int, y:Int, size:Int)
      Local half:Int = size/2
      If y < half Then
         If x < half Then
            If Not child[0] Then
               child[0] = New TQuadtree
            End If
            If half > 1 Then
               child[0].Write(x, y, half)
            End If
         Else
            If Not child[1] Then
               child[1] = New TQuadtree
            End If
            If half > 1 Then
               child[1].Write(x-half, y, half)
            End If
         End If
      Else
         If x < half Then
            If Not child[2] Then
               child[2] = New TQuadtree
            End If
            If half > 1 Then
               child[2].Write(x, y-half, half)
            End If
         Else
            If Not child[3] Then
               child[3] = New TQuadtree
            End If
            If half > 1 Then
               child[3].Write(x-half, y-half, half)
            End If
         End If
      End If
   End Method
   
   
   Method GetState:Int(x:Int, y:Int, size:Int, bd:Float[])
      Local half:Int = size/2
      If y < half Then
         If x < half Then
            If Not child[0] Then
               bd[0] :+ half
               bd[1] :+ half
               Return 0
            End If
            If half > 1 Then
               Return child[0].GetState(x, y, half, bd)
            Else
               Return 1
            End If
         Else
            If Not child[1] Then
               bd[0] :+ size
               bd[1] :+ half
               bd[2] :+ half
               Return 0
            End If
            If half > 1 Then
               bd[0] :+ half
               bd[2] :+ half
               Return child[1].GetState(x-half, y, half, bd)
            Else
               Return 1
            End If
         End If
      Else
         If x < half Then
            If Not child[2] Then
               bd[0] :+ half
               bd[1] :+ size
               bd[3] :+ half
               Return 0
            End If
            If size/2 > 1 Then
               bd[1] :+ half
               bd[3] :+ half
               Return child[2].GetState(x, y-half, half, bd)
            Else
               Return 1
            End If
         Else
            If Not child[3] Then
               bd[0] :+ size
               bd[1] :+ size
               bd[2] :+ half
               bd[3] :+ half
               Return 0
            End If
            If size/2 > 1 Then
               bd[0] :+ half
               bd[1] :+ half
               bd[2] :+ half
               bd[3] :+ half
               Return child[3].GetState(x-half, y-half, half, bd)
            Else
               Return 1
            End If
         End If
      End If
   End Method
End Type
  • Zuletzt bearbeitet von Boris1993 am Mi, Jan 30, 2013 23:21, insgesamt einmal bearbeitet

BladeRunner

Moderator

BeitragSo, Jan 27, 2013 20:37
Antworten mit Zitat
Benutzer-Profile anzeigen
Ein wenig mehr an Information wäre nett.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92
 

Boris1993

 BeitragSo, Jan 27, 2013 23:38
Antworten mit Zitat
Benutzer-Profile anzeigen
Da gibts nicht viel was ich noch sagen könnte probier das Programm aus. Der Strahl überprüft in jeder Node ob ein Voxel enthalten ist wenn in einer größeren Node keiner enthalten ist wird der ganze Bereich übersprungen was das Raytracing sehr sehr viel schneller macht. Es ist einfach ein kleines Testprogramm für den Algorithmus den ich mir überlegt hab. Leider hatte ich nicht sehr viel Lust drauf den Code zu kommentieren vielleicht mache ich das noch im nachhinein.

BladeRunner

Moderator

BeitragSo, Jan 27, 2013 23:43
Antworten mit Zitat
Benutzer-Profile anzeigen
Schau, Boris, genau dafür ist aber doch ein Codearchiv da: Code zeigen den man nutzen und auch verstehen kann. Idealerweise stark kommentiert und mit ausführlicher Funktionsbeschreibung.
Weil von Copy und Paste hat niemand was, und einlesen in unkommentierten Fremdcode ist immer sehr mühselig.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92
 

Boris1993

 BeitragSo, Jan 27, 2013 23:55
Antworten mit Zitat
Benutzer-Profile anzeigen
Du hast ja recht ich werd zusehen das ich das noch kommentiere aber darin bin ich nicht grad der beste und das macht meine Programme dann evtl noch unverständlicher Very Happy
Ich hoffe, dass es trozdem jemandem nutzen wird, der sich mit dem Thema beschäftigt

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group