Stocker une matrice 3D dans un octree

kelebrindae · Message par **kelebrindae** » lun. 02/déc./2013 17:07

Bonjour,

Suite à mes investigations dans le domaine des mondes cubiques, j'en suis arrivé à cette question: quand on a un monde vaste composé de petits cubes de 1x1x1, comment stocker ça plus efficacement que dans un gros tableau 3D.

Réponse: dans un octree, c'est-à-dire un arbre recursif 3D.
Prenons un bout de monde de 16x16x16. Ce cube peut être coupé en 8 morceaux de 8x8x8, eux-même divisibles en 8 morceaux de 4x4x4, etc. jusqu'aux blocs élémentaires de 1x1x1.

L'avantage, c'est que si un morceau ne contient qu'un seul type de blocs, on n'est pas obligé de le diviser => on gagne donc par rapport au tableau 3D qui fait toujours la même taille (16x16x16 = 4096).

L'inconvénient, c'est qu'on est obligé d'opérer à partir de morceaux cubiques dont la dimension est une puissance de 2. Et puis il y a forcément un petit coût algorithmique par rapport au simple adressage d'un tableau [x,y,z].

Je vous laisse tester pour vous faire une idée. C'est encore largement optimisable, mais ça donne une idée du concept. N'oubliez pas de récupérer l'include "Perlin" fourni par G-Rom (sous le code) et de le sauvegarder sous le nom "perlinGenerator.pbi".

Code : Tout sélectionner

;************************************************************************************
;  Test: Storing a cube world in an octree.
;  PB version: 5.21
;  Date: December, 02, 2013
;
;- In game:
;- O  -> Alternate classic / octree render
;- W -> Wireframe view
;
;************************************************************************************

; Great Perlin noise generator given by G-Rom!
XIncludeFile "perlinGenerator.pbi"

; Window size
#SCREENWIDTH = 800
#SCREENHEIGHT = 500

; Camera
#CAMERA = 0
#CAMERASPEED = 0.005

; Sides of a cube
Enumeration
  #TOPSIDE
  #BOTTOMSIDE
  #LEFTSIDE
  #RIGHTSIDE
  #FRONTSIDE
  #BACKSIDE
EndEnumeration

; Size of a chunk (group of cubes that are prepared/built/rendered at the same time)
#CHUNKSIZE = 15

; Size of the world, in chunks
#WORLDWIDTH = 100
#WORLDLENGTH = 100


; World infos
Structure cube_struct
  numMat.b
  solidity.b ; 127 = intact, 0 = destroyed
EndStructure

Structure chunkArray_struct
  
  ; Classic: 3D array
  Array chunk.cube_struct(#CHUNKSIZE+1,#CHUNKSIZE+1,#CHUNKSIZE+1)
  
  ; Octree root
  *ptrRoot.octree_struct
  
  
  queued.b
  state.b
  
  numMesh.i  
  boundingBoxEntity.i
EndStructure
Global Dim chunkArray.chunkArray_struct(#WORLDWIDTH,#WORLDLENGTH)

;- Octree structure
Structure octree_struct
  nummat.i
  *ptrSub.octree_struct[%111 + 1]
EndStructure

; Player
Structure player_struct
  x.f
  y.f
  z.f
EndStructure
Global player.player_struct

; Misc
Global wmain.i
Global mapSprite.i
Global cubeMesh.i, cubemat.i

EnableExplicit

;************************************************************************************
;-                                 ---- Macros ----
;************************************************************************************

Macro DISPLAY_FPS(timer)
    ; Display FPS
    If showFps = #True
      If timer - fpsTimer > 1000
        StartDrawing(SpriteOutput(fpsSprite))
        DrawText(0,0, Str(CountRenderedTriangles()/12) + " cubes, " +  Str(Engine3DFrameRate(#PB_Engine3D_Current))+ " FPS   " )
        DrawText(0,20,"W: Wireframe mode | O: alternate Classic/Octree mode")
        StopDrawing()
        fpsTimer = timer
      EndIf
      DisplayTransparentSprite(fpsSprite,0,0) 
    EndIf    
EndMacro


Macro CREATE_OCTREE_CELL(ptrNode, material)
    ptrNode = AllocateMemory(SizeOf(octree_struct))
    ptrNode\nummat = material
EndMacro

;************************************************************************************
;-                                 ---- Procedures ----
;************************************************************************************

Procedure setOctreeCell(xChunk.i,zChunk.i,xCell.i,yCell.i,zCell.i,nummat.b, *ptrCurrent.octree_struct, xOri.i=0,yOri.i=0,zOri.i=0, cellSize.i=#CHUNKSIZE+1)
  Protected x.i,y.i,z.i
  
  Debug "--------------------------"
  Debug "Octree level for size = " + Str(cellSize) + ": cell " + Str(xOri) + " => " + Str(xOri+cellSize) + "," + Str(yOri) + " => " + Str(yOri+cellSize) + "," + Str(zOri) + " => " + Str(zOri+cellSize)
  
  ; If we are at the deepest level (cellSize = 1), set the material and return.
  If cellSize = 1 Or *ptrCurrent\nummat = nummat
    Debug "material = " + nummat
    *ptrCurrent\nummat = nummat
    ProcedureReturn
  EndIf
  
  ; If current cell isn't subdivided
  If *ptrCurrent\nummat <> -1
    Debug "  Cell not subdivided => breaking it in 8 subcells"
    ; Subdivide it into 8 cells   
    CREATE_OCTREE_CELL(*ptrCurrent\ptrSub[%000],*ptrCurrent\nummat)
    CREATE_OCTREE_CELL(*ptrCurrent\ptrSub[%001],*ptrCurrent\nummat)
    CREATE_OCTREE_CELL(*ptrCurrent\ptrSub[%010],*ptrCurrent\nummat)
    CREATE_OCTREE_CELL(*ptrCurrent\ptrSub[%011],*ptrCurrent\nummat)
    CREATE_OCTREE_CELL(*ptrCurrent\ptrSub[%100],*ptrCurrent\nummat)
    CREATE_OCTREE_CELL(*ptrCurrent\ptrSub[%101],*ptrCurrent\nummat)
    CREATE_OCTREE_CELL(*ptrCurrent\ptrSub[%110],*ptrCurrent\nummat)
    CREATE_OCTREE_CELL(*ptrCurrent\ptrSub[%111],*ptrCurrent\nummat)
    
    ; And go down one level into the target cell with cellSize = cellSize / 2
    cellSize/2
    If xCell - xOri >= cellSize
      x=1
    EndIf
    If yCell - yOri >= cellSize
      y=1
    EndIf
    If zCell - zOri >= cellSize
      z=1
    EndIf
    setOctreeCell(xChunk,zChunk,xCell,yCell,zCell,nummat, *ptrCurrent\ptrSub[x<<2|y<<1|z],  xOri + x*cellSize,yOri + y*cellSize, zOri + z*cellSize, cellSize)
    
    ; Then, set material = -1 for the current cell (subdivided)
    *ptrCurrent\nummat = -1
  Else ; Current cell is already subdivided:
    Debug "  Cell already subdivided"
    ; And go down one level into the target cell with cellSize = cellSize / 2
    cellSize/2
    If xCell - xOri >= cellSize
      x=1
    EndIf
    If yCell - yOri >= cellSize
      y=1
    EndIf
    If zCell - zOri >= cellSize
      z=1
    EndIf
    setOctreeCell(xChunk,zChunk,xCell,yCell,zCell,nummat, *ptrCurrent\ptrSub[x<<2|y<<1|z],  xOri + x*cellSize,yOri + y*cellSize, zOri + z*cellSize, cellSize)

    ; If all the subdivisions have the same material, collapse them into the current cell
    ; => delete them and set current material = nummat.
    If *ptrCurrent\ptrSub[%000]\nummat > -1 And
       *ptrCurrent\ptrSub[%000]\nummat = *ptrCurrent\ptrSub[%001]\nummat  And *ptrCurrent\ptrSub[%001]\nummat = *ptrCurrent\ptrSub[%010]\nummat And
       *ptrCurrent\ptrSub[%010]\nummat = *ptrCurrent\ptrSub[%011]\nummat And *ptrCurrent\ptrSub[%011]\nummat = *ptrCurrent\ptrSub[%100]\nummat And
       *ptrCurrent\ptrSub[%100]\nummat = *ptrCurrent\ptrSub[%101]\nummat And *ptrCurrent\ptrSub[%101]\nummat = *ptrCurrent\ptrSub[%110]\nummat And
       *ptrCurrent\ptrSub[%110]\nummat = *ptrCurrent\ptrSub[%111]\nummat
      
      Debug "  Cell size = " + Str(cellSize) + ": cell " + Str(xOri) + " => " + Str(xOri+cellSize) + "," + Str(yOri) + " => " + Str(yOri+cellSize) + "," + Str(zOri) + " => " + Str(zOri+cellSize) + " is uniformly filled With mat " + Str(numMat) + " => collapsing to size "+Str(cellSize*2)

      
      FreeMemory(*ptrCurrent\ptrSub[%000])
      FreeMemory(*ptrCurrent\ptrSub[%001])
      FreeMemory(*ptrCurrent\ptrSub[%010])
      FreeMemory(*ptrCurrent\ptrSub[%011])
      FreeMemory(*ptrCurrent\ptrSub[%100])
      FreeMemory(*ptrCurrent\ptrSub[%101])
      FreeMemory(*ptrCurrent\ptrSub[%110])
      FreeMemory(*ptrCurrent\ptrSub[%111])
      *ptrCurrent\nummat = nummat
      
    EndIf
  EndIf
  
EndProcedure


; Return the content of a 1x1x1 block in the chunk.
Procedure.b getOctreeCell(xChunk.i,zChunk.i,xCell.i,yCell.i,zCell.i, *ptrCurrent.octree_struct, xOri.i=0,yOri.i=0,zOri.i=0, cellSize.i=#CHUNKSIZE+1)
  Protected x.i,y.i,z.i
  
  ; If the cell isn't sudivided, return its content
  If *ptrCurrent\nummat <> -1
    ProcedureReturn *ptrCurrent\nummat
  EndIf
  
  ; If it's subdivided, explore the target subcell.
  cellSize/2
  If xCell - xOri >= cellSize
    x=1
  EndIf
  If yCell - yOri >= cellSize
    y=1
  EndIf
  If zCell - zOri >= cellSize
    z=1
  EndIf
  ProcedureReturn getOctreeCell(xChunk,zChunk,xCell,yCell,zCell, *ptrCurrent\ptrSub[x<<2|y<<1|z],  xOri + x*cellSize,yOri + y*cellSize, zOri + z*cellSize, cellSize)

EndProcedure


; Create the entities needed to display the octree world
Procedure displayOctreeWorld(xChunk.i,zChunk.i,xCell.i,yCell.i,zCell.i, *ptrCurrent.octree_struct, xOri.i=0,yOri.i=0,zOri.i=0, cellSize.i=#CHUNKSIZE+1)
  Protected x.i,y.i,z.i
  
  ; If the cell isn't subdivided, create a cube and scale it to cellSize
  If *ptrCurrent\nummat <> -1
    If *ptrCurrent\nummat > 0
      ScaleEntity(CreateEntity(#PB_Any,MeshID(cubeMesh),MaterialID(cubeMat),xOri+cellSize/2,yOri+cellSize/2,zOri+cellSize/2,$00001),cellSize,cellSize,cellSize)    
    EndIf
  Else ; If it's subdivided, explore all the subcells    
    cellSize/2
    For x=0 To 1
      For y=0 To 1
        For z=0 To 1
          displayOctreeWorld(xChunk,zChunk,xCell,yCell,zCell, *ptrCurrent\ptrSub[x<<2|y<<1|z],  xOri + x*cellSize,yOri + y*cellSize, zOri + z*cellSize, cellSize)
        Next z
      Next y
    Next x
    
  EndIf    
  
EndProcedure


; Initialize a random world
Procedure prepareChunk(xChunk.i,zChunk.i)  
  Protected divW.f = 2 / (#WORLDWIDTH)
  Protected divL.f = 2 / (#WORLDLENGTH)
  Protected noise.d,height.i
  Protected x.i,y.i,z.i
  
  ; Initialize the root of the chunk's octree with material 0 (empty)
  CREATE_OCTREE_CELL(chunkArray(xChunk,zChunk)\ptrRoot,0)  
  
  ; Fill the chunk with perlin noise 
  For z = 0 To #CHUNKSIZE
    For x = 0 To #CHUNKSIZE
      noise  = PERLIN_unsigned(PERLIN_generateNoise2D(divW * (x + xChunk * (#CHUNKSIZE+1)), divL * (z + zChunk * (#CHUNKSIZE+1)), 4, 4, 10))
      height = Int(noise * (#CHUNKSIZE))
          
      ; Fill what's underground
       For y = height To 0 Step -1
         Debug "Filling cell: " + Str(x) + "," + Str(y) + "," + Str(z)
         
         ; 3D array
         chunkArray(xChunk,zChunk)\chunk(x,y,z)\numMat = 1
         
         ; Same thing with the octree
         setOctreeCell(xChunk,zChunk,x,y,z,1,chunkArray(xChunk,zChunk)\ptrRoot)
         
       Next y
    Next x
  Next z
  
EndProcedure


; "Classic" rendering: check every location in a 3D array and create the cube.
Procedure displayWorld(xChunk.i, zChunk.i, xOri.i=0,yOri.i=0,zOri.i=0,xEnd.i=#CHUNKSIZE,yEnd.i=#CHUNKSIZE,zEnd.i=#CHUNKSIZE)
  Protected x.i,y.i,z.i
  Protected numMat.b
  
  For y = yOri To yEnd
    For x = xOri To xEnd
      For z = zOri To zEnd
        
        ; Classic (3D array)
        numMat = chunkArray(xChunk, zChunk)\chunk(x,y,z)\numMat
        
        ; Get the value of a 1x1x1 block in the octree
        ;numMat = getOctreeCell(xChunk, zChunk,x,y,z,chunkArray(xChunk,zChunk)\ptrRoot)        
        
        If nummat > 0
          CreateEntity(#PB_Any,MeshID(cubeMesh),MaterialID(cubeMat),x+0.5,y+0.5,z+0.5)
        EndIf

      Next z
    Next x
  Next y
  
  FreeMesh(cubemesh)
EndProcedure



Procedure playGame()
  Protected wireframe.b, octreeMode.b = #True, dontQuit.b = #True, eventId.i
  Protected mouseX.f, mouseY.f
  Protected xdir.f,ydir.f,zdir.f
  Protected fpsSprite.i, fpsTimer.i, showFps.b = #True
  Protected timer.i, oldTimer.i, loopTime.f
  Protected oldx.f,oldy.f,oldz.f,newX.f,newY.f,newZ.f

  ;- Sprite used to display FPS
  fpsSprite = CreateSprite(#PB_Any,640,38)
  
  ;- Camera
  player\x = 16: player\y = 20:player\z = 40
  CreateCamera(#CAMERA, 0, 0, 100, 100)
  CameraBackColor(#CAMERA,$000000)
  MoveCamera(#CAMERA,player\x,player\y,player\z)
  CameraLookAt(#CAMERA,8,8,8)

  ;-Light
  CreateLight(1,$FFFFFF,CameraX(#CAMERA),CameraY(#CAMERA),CameraZ(#CAMERA))
  WorldShadows(#PB_Shadow_Additive)
  
  ;- Material
  CreateTexture(0,16,16)
  StartDrawing(TextureOutput(0))
  Box(0,0,16,16,$007700)
  DrawingMode(#PB_2DDrawing_Outlined)
  Box(0,0,16,16,$00FF00)
  StopDrawing()
  cubeMat = CreateMaterial(#PB_Any,TextureID(0))
  MaterialFilteringMode(cubeMat, #PB_Material_Anisotropic, 6)

  ;- World
  cubeMesh = CreateCube(#PB_Any,0.99)
  RandomSeed(123456789)
  prepareChunk(1,1)
  displayOctreeWorld(1,1,0,0,0,chunkArray(1,1)\ptrRoot)
  
  oldTimer = ElapsedMilliseconds()
  KeyboardMode(#PB_Keyboard_International)
  Repeat
    Delay(1)
    
    ; Windows events
    eventID = WindowEvent()
    While eventID <> 0 And dontQuit = #True
      eventID = WindowEvent()
    Wend
    ExamineKeyboard()
    
    ; Activate wireframe render
    If KeyboardReleased(#PB_Key_W)
      wireframe = 1-wireframe
      If wireframe = #True
        CameraRenderMode(0,#PB_Camera_Wireframe)
      Else
        CameraRenderMode(0,#PB_Camera_Textured)
      EndIf
    EndIf
    
    ; Activate classic / octree render
    If KeyboardReleased(#PB_Key_O)
      octreeMode = 1-octreeMode
      FreeEntity(#PB_All)
      cubeMesh = CreateCube(#PB_Any,0.99)

      If octreeMode = #True
        displayOctreeWorld(1,1,0,0,0,chunkArray(1,1)\ptrRoot)
      Else
        displayWorld(1,1)        
      EndIf
    EndIf
    
    
    ;- Movements (mouse + arrows)
    timer = ElapsedMilliseconds()
    loopTime = 1 + (timer - oldtimer)
    If looptime > 32
      looptime = 32
    EndIf
    oldtimer = timer
    
    ; Look around    
    If ExamineMouse()
      MouseX = -(MouseDeltaX()/20)
      MouseY = -(MouseDeltaY()/20)
      
      RotateCamera(#CAMERA, MouseY, MouseX, 0, #PB_Relative)
    EndIf   
    xdir = CameraDirectionX(#CAMERA)
    ydir = CameraDirectionY(#CAMERA)
    zdir = CameraDirectionZ(#CAMERA)
    
    oldx = player\x : oldy = player\y : oldz = player\z
    newX = oldX : newY = oldY : newZ = oldZ

    ; Zoom / Unzoom
    If KeyboardPushed(#PB_Key_Up)
      newX + xDir * (#CAMERASPEED * loopTime)
      newZ + zDir * (#CAMERASPEED * loopTime)
    EndIf
    If KeyboardPushed(#PB_Key_Down)
      newX - xDir * (#CAMERASPEED * loopTime)
      newZ - zDir * (#CAMERASPEED * loopTime)      
    EndIf
    
    ; Strafe
    If KeyboardPushed(#PB_Key_Left)
      newX + (xDir*Cos(Radian(90)) + zDir*Sin(Radian(90))) * (#CAMERASPEED * loopTime)
      newZ + (-xDir*Sin(Radian(90)) + zDir*Cos(Radian(90))) * (#CAMERASPEED * loopTime)      
    EndIf
    If KeyboardPushed(#PB_Key_Right)
      newX - (xDir*Cos(Radian(90)) + zDir*Sin(Radian(90))) * (#CAMERASPEED * loopTime)
      newZ - (-xDir*Sin(Radian(90)) + zDir*Cos(Radian(90))) * (#CAMERASPEED * loopTime)      
    EndIf
    
    player\x = newX : player\y = newY : player\z = newZ
    MoveCamera(#CAMERA,player\x,player\y,player\z,#PB_Absolute)
    
    
    ;- Render
    RenderWorld()
    
    ;- Display FPS
    DISPLAY_FPS(timer)        
    
    FlipBuffers()
  
  Until KeyboardPushed(#PB_Key_Escape) Or dontQuit = #False
    

  
EndProcedure


;************************************************************************************
;-                                 ---- Main program ----
;************************************************************************************

;- Initialization
InitEngine3D()
InitSprite()
InitKeyboard()
InitMouse()
UsePNGImageDecoder()

Add3DArchive("textures",#PB_3DArchive_FileSystem)
Add3DArchive("meshes",#PB_3DArchive_FileSystem)


;- Window
OpenWindow(Wmain,0, 0, #SCREENWIDTH,#SCREENHEIGHT ,"Octree environnement",#PB_Window_ScreenCentered)
OpenWindowedScreen(WindowID(Wmain), 0, 0, #SCREENWIDTH,#SCREENHEIGHT, 0, 0, 0,#PB_Screen_NoSynchronization)

;- Game
playGame()

End

Include "Perlin" à sauvegarder sous le nom "perlinGenerator.pbi"

Code : Tout sélectionner

;************************************************************************************
;-                       ---- Constants, structures, globals ----
;************************************************************************************
#PERLIN_B  = $100
#PERLIN_BM = $FF
#PERLIN_N  = $1000
#PERLIN_NP = 16   ;  2^N
#PERLIN_NM = $FF

Structure PERLIN_InnerDoubleArray
  d.d[0]
EndStructure

Global Dim  PERLIN_p.i(#PERLIN_B + #PERLIN_B + 1)
Global Dim PERLIN_g1.d(#PERLIN_B + #PERLIN_B + 1)
Global Dim PERLIN_g2.d(#PERLIN_B + #PERLIN_B + 1, 1)
Global Dim PERLIN_g3.d(#PERLIN_B + #PERLIN_B + 1, 2)
Global PERLIN_start.i = 1

;************************************************************************************
;-                                  ---- Macros ----
;************************************************************************************
Macro PERLIN_unsigned(value)
  ((value) + 1) / 2
EndMacro

Macro PERLIN_s_curve(t)
  ( t * t * ( 3 - 2 * t ) )
EndMacro

Macro PERLIN_lerp(t, a, b)
  ( a + t * (b - a) )
EndMacro

Macro PERLIN_setup(i,b0,b1,r0,r1)
  t  = vec(i) + #PERLIN_N
  b0 = Int(t) & #PERLIN_BM
  b1 = (b0 + 1) & #PERLIN_BM
  r0 = t - Int(t)
  r1 = r0 - 1.
EndMacro

Macro PERLIN_at2(rx,ry)
  ( rx * *q\d[0] + ry * *q\d[1] )
EndMacro

Macro PERLIN_at3(rx,ry,rz)
  ( rx * *q\d[0] + ry * *q\d[1] + rz * *q\d[2] )
EndMacro


;************************************************************************************
;-                                ---- Procedures ----
;************************************************************************************
Declare   PERLIN_initialize()
Declare.d PERLIN_noise1(arg.d)
Declare.d PERLIN_noise2(Array vec.d(1))
Declare.d PERLIN_noise3(Array vec.d(1))
Declare   PERLIN_normalize2(d.i)
Declare   PERLIN_normalize3(d.i)

Declare.d PERLIN_generateNoise1D(x.d, alpha.d, beta.d, n.i);
Declare.d PERLIN_generateNoise2D(x.d, y.d, alpha.d, beta.d, n.i);
Declare.d PERLIN_generateNoise3D(x.d, y.d, z.d, alpha.d, beta.d, n.i);


Procedure.d PERLIN_noise1(arg.d)
   Protected bx0.i, bx1.i
   Protected rx0.d, rx1.d, sx.d, t.d, u.d, v.d
   Protected Dim vec.d(1)

   vec(0) = arg
   If PERLIN_start <> 0
      PERLIN_start = 0
      PERLIN_initialize()
   EndIf

   PERLIN_setup(0,bx0,bx1,rx0,rx1)

   sx = PERLIN_s_curve(rx0)
   u = rx0 * PERLIN_g1( PERLIN_p( bx0 ) )
   v = rx1 * PERLIN_g1( PERLIN_p( bx1 ) )

   ProcedureReturn PERLIN_lerp(sx, u, v)
EndProcedure


Procedure.d PERLIN_noise2(Array vec.d(1))
  Protected bx0.i, bx1.i, by0.i, by1.i, b00.i, b10.i, b01.i, b11.i
  Protected rx0.d, rx1.d, ry0.d, ry1.d, *q.PERLIN_InnerDoubleArray, sx.d, sy.d, a.d, b.d, t.d, u.d, v.d
  Protected i.i, j.i
 
  If PERLIN_start <> 0
    PERLIN_start = 0
    PERLIN_initialize()
  EndIf
 
  PERLIN_setup(0, bx0,bx1, rx0,rx1)
  PERLIN_setup(1, by0,by1, ry0,ry1)
 
  i = PERLIN_p( bx0 )
  j = PERLIN_p( bx1 )
 
  b00 = PERLIN_p( i + by0 )
  b10 = PERLIN_p( j + by0 )
  b01 = PERLIN_p( i + by1 )
  b11 = PERLIN_p( j + by1 )
 
  sx = PERLIN_s_curve(rx0)
  sy = PERLIN_s_curve(ry0)
 
  *q = @PERLIN_g2( b00, 0 ) : u = PERLIN_at2(rx0,ry0)
  *q = @PERLIN_g2( b10, 0 ) : v = PERLIN_at2(rx1,ry0)
  a  = PERLIN_lerp(sx, u, v)
 
  *q = @PERLIN_g2( b01, 0 ) : u = PERLIN_at2(rx0,ry1)
  *q = @PERLIN_g2( b11, 0 ) : v = PERLIN_at2(rx1,ry1)
  b = PERLIN_lerp(sx, u, v)
 
  Protected rv.d = PERLIN_lerp(sy, a, b)
  ProcedureReturn rv
EndProcedure


Procedure.d PERLIN_noise3(Array vec.d(1))
  Protected bx0.i, bx1.i, by0.i, by1.i, bz0.i, bz1.i, b00.i, b10.i, b01.i, b11.i
  Protected rx0.d, rx1.d, ry0.d, ry1.d, rz0.d, rz1.d, *q.PERLIN_InnerDoubleArray, sy.d, sz.d, a.d, b.d, c.d, d.d, t.d, u.d, v.d
  Protected i.i, j.i

   If PERLIN_start <> 0
      PERLIN_start = 0
      PERLIN_initialize()
   EndIf

   PERLIN_setup(0, bx0,bx1, rx0,rx1);
   PERLIN_setup(1, by0,by1, ry0,ry1);
   PERLIN_setup(2, bz0,bz1, rz0,rz1);

   i = PERLIN_p( bx0 )
   j = PERLIN_p( bx1 )

   b00 = PERLIN_p( i + by0 )
   b10 = PERLIN_p( j + by0 )
   b01 = PERLIN_p( i + by1 )
   b11 = PERLIN_p( j + by1 )

   t  = PERLIN_s_curve(rx0)
   sy = PERLIN_s_curve(ry0)
   sz = PERLIN_s_curve(rz0)

   *q = @PERLIN_g3( b00 + bz0, 0 ) : u = PERLIN_at3(rx0,ry0,rz0)
   *q = @PERLIN_g3( b10 + bz0, 0 ) : v = PERLIN_at3(rx1,ry0,rz0)
   a = PERLIN_lerp(t, u, v)

   *q = @PERLIN_g3( b01 + bz0, 0 ) : u = PERLIN_at3(rx0,ry1,rz0);
   *q = @PERLIN_g3( b11 + bz0, 0 ) : v = PERLIN_at3(rx1,ry1,rz0);
   b = PERLIN_lerp(t, u, v);

   c = PERLIN_lerp(sy, a, b);

   *q = @PERLIN_g3( b00 + bz1, 0 ) : u = PERLIN_at3(rx0,ry0,rz1);
   *q = @PERLIN_g3( b10 + bz1, 0 ) : v = PERLIN_at3(rx1,ry0,rz1);
   a = PERLIN_lerp(t, u, v);

   *q = @PERLIN_g3( b01 + bz1, 0 ) : u = PERLIN_at3(rx0,ry1,rz1);
   *q = @PERLIN_g3( b11 + bz1, 0 ) : v = PERLIN_at3(rx1,ry1,rz1);
   b = PERLIN_lerp(t, u, v);

   d = PERLIN_lerp(sy, a, b);

   ProcedureReturn PERLIN_lerp(sz, c, d);
EndProcedure


Procedure PERLIN_normalize2(*v.PERLIN_InnerDoubleArray)
  Protected s.d = Sqr(*v\d[0] * *v\d[0] + *v\d[1] * *v\d[1])

  *v\d[0] = *v\d[0] / s
  *v\d[1] = *v\d[1] / s
EndProcedure


Procedure PERLIN_normalize3(*v.PERLIN_InnerDoubleArray)
  Protected s.d = Sqr(*v\d[0] * *v\d[0] + *v\d[1] * *v\d[1] + *v\d[2] * *v\d[2])

  *v\d[0] = *v\d[0] / s
  *v\d[1] = *v\d[1] / s
  *v\d[2] = *v\d[2] / s
EndProcedure


Procedure PERLIN_initialize()
  Protected i.i, j.i, k.i, tmp.i
  Protected *t.PERLIN_InnerDoubleArray
  
  i = 0
  While i < #PERLIN_B
    PERLIN_p(i)  = i
    tmp = ((Random(2147483647) % (#PERLIN_B + #PERLIN_B)) - #PERLIN_B)
    PERLIN_g1(i) = tmp / #PERLIN_B
   
 
    For j = 0 To 1
      tmp = ((Random(2147483647) % (#PERLIN_B + #PERLIN_B)) - #PERLIN_B)
      PERLIN_g2(i, j) = tmp / #PERLIN_B
    Next j
    PERLIN_normalize2(@PERLIN_g2(i, 0))
 
    For j = 0 To 2
      tmp = ((Random(2147483647) % (#PERLIN_B + #PERLIN_B)) - #PERLIN_B)
      PERLIN_g3(i, j) = tmp / #PERLIN_B
    Next j
    PERLIN_normalize3(@PERLIN_g3(i, 0))

    i + 1
  Wend 
 
  i - 1
  While i > 0
    i - 1
   
    k = PERLIN_p(i)
    j = Random(2147483647) % #PERLIN_B
    PERLIN_p(i) = PERLIN_p(j)
    PERLIN_p(j) = k;
  Wend
 
  i = 0
  While i < #PERLIN_B + 2
    PERLIN_p(#PERLIN_B + i) = PERLIN_p(i)
    PERLIN_g1(#PERLIN_B + i) = PERLIN_g1(i)

    For j = 0 To 1
      PERLIN_g2(#PERLIN_B + i, j) = PERLIN_g2(i, j)
    Next j
    For j = 0 To 2
      PERLIN_g3(#PERLIN_B + i, j) = PERLIN_g3(i, j)
    Next j

    i + 1
  Wend
EndProcedure


Procedure.d PERLIN_generateNoise1D(x.d, alpha.d, beta.d, iterations.i)
   Protected i.i
   Protected val.d = 0, sum.d = 0
   Protected p.d = 1, scale.d = 1

   p = x
   For i = 1 To iterations
      val = PERLIN_noise1(p)
      sum + val / scale
      scale * alpha
      p * beta
   Next i
   
   ProcedureReturn(sum)
EndProcedure


Procedure.d PERLIN_generateNoise2D(x.d ,y.d, alpha.d, beta.d, iterations.i)
   Protected i.i
   Protected val.d = 0, sum.d = 0
   Protected scale.d = 1
   Protected Dim args.d(1)

   args(0) = x
   args(1) = y
   For i = 1 To iterations
      val = PERLIN_noise2(args())
      sum + val / scale
      scale * alpha
      args(0) * beta
      args(1) * beta
   Next i
   
   ProcedureReturn(sum)
EndProcedure


Procedure.d PERLIN_generateNoise3D(x.d, y.d, z.d, alpha.d, beta.d, iterations.i)
   Protected i.i
   Protected val.d = 0, sum.d = 0
   Protected scale.d = 1
   Protected Dim args.d(2)

   args(0) = x
   args(1) = y
   args(2) = z
   For i = 1 To iterations
      val = PERLIN_noise3(args())
      sum = sum + (val / scale)
      scale * alpha
      args(0) * beta
      args(1) * beta
      args(2) * beta
   Next i
   
   ProcedureReturn(sum)
EndProcedure

Backup · Message par **Backup** » lun. 02/déc./2013 17:10

zetes des tronches quand meme

kelebrindae · Message par **kelebrindae** » lun. 02/déc./2013 17:26

Dixit le musicien + programmeur + spécialiste de la 3D anaglyphe + plein d'autres trucs...

Backup · Message par **Backup** » lun. 02/déc./2013 18:55

arf .. de l'esbrouffe , rien de plus

djes · Message par **djes** » lun. 02/déc./2013 19:18

Comment on dit en anglais ? Brilliant !

G-Rom · Message par **G-Rom** » lun. 02/déc./2013 19:36

Je ne suis pas l'auteur du bruit de perlin ^^
Vivement que tu mettes tout ca en place dans ton pb-mineclone ( avec les cavités

)

venom · Message par **venom** » lun. 02/déc./2013 21:08

Je ne suis pas assez connaisseur en 3d pour exploiter ton code, mais le résultat est top.
Bravo

@++

Ar-S · Message par **Ar-S** » lun. 02/déc./2013 22:04

Je suis de loin mais je reste vraiment hermetique à la prog 3D pour l'instant mais "Stocker une matrice 3D dans un octree" sera ma phrase du jour en tout cas

J'ai hâte de voir l'avancé de ton clonecraft

kelebrindae · Message par **kelebrindae** » mar. 03/déc./2013 18:18

Merci à tous!
Je vous tiens au courant dès que j'ai pu mettre ça dans "le clone" (avec les cavités

).

kelebrindae · Message par **kelebrindae** » ven. 21/mars/2014 18:13

[UPDATE]
Une rapide mise à jour pour corriger un bug qui ne se voyait pas dans l'exemple: quelquefois, des petits cubes se trouvaient à tort rassemblés en un plus gros alors qu'ils n'était pas uniformes.
[/UPDATE]

(Et désolé pour mon absence sur le forum récemment, j'ai trop de boulot pour pouvoir coder, ces derniers temps...

)

PureBasic

Stocker une matrice 3D dans un octree

Stocker une matrice 3D dans un octree

Re: Stocker une matrice 3D dans un octree

Re: Stocker une matrice 3D dans un octree

Re: Stocker une matrice 3D dans un octree

Re: Stocker une matrice 3D dans un octree

Re: Stocker une matrice 3D dans un octree

Re: Stocker une matrice 3D dans un octree

Re: Stocker une matrice 3D dans un octree

Re: Stocker une matrice 3D dans un octree

Re: Stocker une matrice 3D dans un octree