Any have experience with writing a Octree recursive function(s)? I'm having the hardest time getting the space to devide correctly.
Octree Recursion
Blitz3D Forums/Blitz3D Programming/Octree Recursion I wrote an octree system in C++, which part do you have a problem with?
I'm just looking to break a rectagular portion of space down about 4 levels. The problem I have, is that I'm not all that good with writing recusive functions, I always get confused at some point. Anyway, I'm not sure what the best way is to get the recursion to stop at the forth level deep. Any suggestions?
func(4)
end
function func(depth)
if depth>0
func(depth-1)
endif
end function
end
function func(depth)
if depth>0
func(depth-1)
endif
end function
I'm startting to implement an octree but it's not finished. the code is not finished and developped with bmax and minib3d.
SuperStrict Import "../Inc/Inc_Minib3d.bmx" Const LE_MESH:String = "media\Patmaba.b3d" 'Profondeur toujours >= 1 Const LA_PROFONDEUR:Int = 4 ' ----------------------- ' Variable(s) globale(s) ' ----------------------- Global cam:TCamera Global D:TMesh Global Light1:TLight Global m:TMesh Global gi_CubeSize:Float = 0.0 '------------------------ 'Freelook cam Var '------------------------ Global Mouse_X_Speed:Float Global Mouse_Y_Speed:Float Global Camera_VelX:Float Global Camera_VelZ:Float Global Camera_Pitch:Float Global Camera_Yaw:Float Global oldmx:Int Global oldmy:Int Const AppFPS:Int = 50 Global FramePeriod:Int = 1000 / AppFPS Global FrameTime:Int = MilliSecs () - FramePeriod Global FrameElapsed:Int Global FrameTicks:Int Global FrameTween:Float ' --------------- ' Init la scene ' --------------- InitScene() ' --------------- ' Init les Agents ' --------------- Initoctree() ' ------------------------------------- ' Variables pour la gestion du fps ' ------------------------------------- Local old_ms:Int=MilliSecs() Local renders:Int Local fps:Int Global countbox:Int=0 Repeat ' -------------------------- ' Frame rate limiting ' -------------------------- Repeat FrameElapsed = MilliSecs () - FrameTime Until FrameElapsed FrameTicks = FrameElapsed / FramePeriod FrameTween:Float = Float (FrameElapsed Mod FramePeriod) / Float (FramePeriod) ' ----------------------- ' Update tweening ' ----------------------- For Local FrameLimit:Int = 1 To FrameTicks FrameTime = FrameTime + FramePeriod UpdateGame () UpdateWorld Next ' ------------------- ' Redraw world ' ------------------- RenderWorld ' --------------------- ' FPS Displaying ' --------------------- ' Proc_CinemaStrip() debugtext 10,10,"octree" debugtext 10,25," Use arrow keys" cube( -meshwidth(m)/2,meshwidth(m)/2,-meshheight(m)/2, meshheight(m)/2,-meshdepth(m)/2,meshdepth(m)/2) Flip False Until KeyHit (KEY_ESCAPE) Function UpdateGame() Proc_Freelook(1.03,0.03) PointEntity cam, m EndFunction ' --------------------------------- ' InitScene() ' Description de la scene ' --------------------------------- Function InitScene() Graphics3D 800,600,32,0 ' ------------------------------------- ' Setup camera ' ------------------------------------- cam=CreateCamera() PositionEntity cam,-11,70,-125 CameraRange cam,1,250000 CameraZoom cam,0.9 ' ------------------------------------- ' Setup Light and ambiance ' ------------------------------------- Light1=CreateLight(2) PositionEntity Light1,-1630,1630,1630 LightColor Light1,155,220,255 LightRange Light1,5500 EndFunction ' --------------------------------- ' InitAgent() ' Description des agents IA ' --------------------------------- Function Initoctree() m:TMesh = LoadMesh(LE_MESH) gi_CubeSize = 0.0 gi_CubeSize = MeshWidth( m ) If gi_CubeSize < MeshHeight( m ) Then gi_CubeSize = MeshHeight( m ) If gi_CubeSize < MeshDepth( m ) Then gi_CubeSize = MeshDepth( m ) PositionEntity cam,-gi_CubeSize /2,gi_CubeSize /2,-gi_CubeSize /2 PointEntity cam, m dessine_octree() DebugLog "countbox="+countbox End Function ' ------------------------------------------------------------------------------------------------------------------- ' This Function returns True If a point is inside an Object's oriented bounding box, and false if it is not. ' ------------------------------------------------------------------------------------------------------------------- Function Point_Inside_Box:Int(ThisEntity:TMesh, min_x:Float, max_x:Float, min_y:Float, max_y:Float, min_z:Float, max_z:Float ) ' Calculate the bounding box (in Object space) For this Object. ' You can precalculate this For every Object in your game For a huge speed increase! Local Surfaces:Int = CountSurfaces(ThisEntity) Local t:Int=0 For Local LOOP_Surface:Int = 1 To Surfaces Local Surface_Handle:TSurface = GetSurface(ThisEntity, LOOP_Surface) Local Verts:Int = CountVertices(Surface_Handle) - 1 For Local LOOP_Verts:Int = 0 To Verts-1 Local vx:Float = VertexX#(Surface_Handle, LOOP_Verts) Local vy:Float = VertexY#(Surface_Handle, LOOP_Verts) Local Vz:Float = VertexZ#(Surface_Handle, LOOP_Verts) ' Determine If the point (in Object space) is inside the bounding box (in Object space). If (vx# > min_x#) And (vx# < max_x#) And (vy# > min_y#) And (vy# < max_y#) And (Vz# > min_z#) And (vz# < max_z#) 'DebugLog "TRUE" Return True EndIf Next Next 'DebugLog "FALSE" Return False EndFunction '------------------------ 'Camera freelook '------------------------ Function Proc_Freelook(Velocity:Float,Speed:Float) Local flag:Int=False Mouse_X_Speed=(MouseXSpeed())*0.5 Mouse_Y_Speed=(MouseYSpeed())*0.5 MoveMouse GraphicsWidth()/2,GraphicsHeight()/2 Camera_Pitch=Camera_Pitch+Mouse_Y_Speed Camera_Yaw=Camera_Yaw+Mouse_X_Speed If flag=True RotateEntity cam,Camera_Pitch,-Camera_Yaw,0 EndIf If KeyDown(KEY_LEFT) Then Camera_VelX=Camera_VelX-Speed ElseIf KeyDown(KEY_RIGHT) Camera_VelX=Camera_VelX+Speed EndIf If KeyDown(KEY_DOWN) Then Camera_VelZ=Camera_VelZ-Speed ElseIf KeyDown(KEY_UP) Camera_VelZ=Camera_VelZ+Speed EndIf Camera_VelX=Camera_VelX/Velocity Camera_VelZ=Camera_VelZ/Velocity MoveEntity cam,Camera_VelX,0,Camera_VelZ If KeyDown(KEY_UP) Then MoveEntity cam,0,0,Speed EndIf If KeyDown(KEY_DOWN) Then MoveEntity cam,0,0,-Speed EndIf If KeyDown(KEY_RIGHT) Then MoveEntity cam,Speed,0,0 EndIf If KeyDown(KEY_LEFT) Then MoveEntity cam,-Speed,0,0 EndIf End Function Function cube (x0:Float, x1:Float, y0:Float, y1:Float, z0:Float, z1:Float) glBegin (GL_LINE_STRIP); glVertex3f (x0, y0, z0); glVertex3f (x1, y0, z0); glVertex3f (x1, y1, z0); glVertex3f (x0, y1, z0); glVertex3f (x0, y0, z0); glVertex3f (x0, y0, z1); glVertex3f (x1, y0, z1); glVertex3f (x1, y0, z0); glVertex3f (x1, y0, z1); glVertex3f (x1, y1, z1); glVertex3f (x1, y1, z0); glVertex3f (x1, y1, z1); glVertex3f (x0, y1, z1); glVertex3f (x0, y1, z0); glVertex3f (x0, y1, z1); glVertex3f (x0, y0, z1); glEnd (); EndFunction ' dessine l'octree recursivement Function dessine_8_cubes (lxmin:Float, lxmax:Float, lymin:Float, lymax:Float, lzmin:Float, lzmax:Float, pMaxLevel:Int, pCurrentLevel:Int, the_list:TList) Local lb_val:Int 'lb_val:Int = Point_Inside_Box(m, lxmin, lxmax, lymin, lymax, lzmin, lzmax ) Local my_list:TList = Point_Inside_List(lxmin, lxmax, lymin, lymax, lzmin, lzmax, the_list ) If my_list.count() = 0 lb_val = False Else lb_val = True EndIf ' si on est un noeud terminal on s'arrete If (pMaxLevel=pCurrentLevel) And ( lb_val = True) cube (lxmin, lxmax, lymin, lymax, lzmin, lzmax) ' Local c:TMesh = CreateCube() ' EntityAlpha c, 0.4 ' PositionEntity c, (lxmin + lxmax) / 2,(lymin + lymax) / 2,(lzmin + lzmax) / 2 ' ScaleEntity c, 1/MeshWidth(c)*(lxmax-lxmin), 1/MeshHeight(c)*(lymax-lymin), 1/MeshDepth(c)*(lzmax-lzmin) Local s:TMesh = CreateSphere() EntityAlpha s, 0.4 PositionEntity s, (lxmin + lxmax) / 2,(lymin + lymax) / 2,(lzmin + lzmax) / 2 ScaleEntity s, 1/MeshWidth(s)*(lxmax-lxmin), 1/MeshHeight(s)*(lymax-lymin), 1/MeshDepth(s)*(lzmax-lzmin) countbox=countbox+1 Return EndIf If lb_val= True And lb_val ' on rappelle rcursivement pour les 8 fils dessine_8_cubes (lxmin, (lxmin + lxmax) / 2, lymin, (lymin + lymax) / 2, lzmin, (lzmin + lzmax) / 2, pMaxLevel, pCurrentLevel + 1, my_list ) dessine_8_cubes (lxmin, (lxmin + lxmax) / 2, lymin, (lymin + lymax) / 2, (lzmin + lzmax) / 2, lzmax, pMaxLevel, pCurrentLevel + 1, my_list ) dessine_8_cubes (lxmin, (lxmin + lxmax) / 2, (lymin + lymax) / 2, lymax, lzmin, (lzmin + lzmax) / 2, pMaxLevel, pCurrentLevel + 1, my_list ) dessine_8_cubes (lxmin, (lxmin + lxmax) / 2, (lymin + lymax) / 2, lymax, (lzmin + lzmax) / 2, lzmax, pMaxLevel, pCurrentLevel + 1, my_list ) dessine_8_cubes ((lxmin + lxmax) / 2, lxmax, lymin, (lymin + lymax) / 2, lzmin, (lzmin + lzmax) / 2, pMaxLevel, pCurrentLevel + 1, my_list ) dessine_8_cubes ((lxmin + lxmax) / 2, lxmax, lymin, (lymin + lymax) / 2, (lzmin + lzmax) / 2, lzmax, pMaxLevel, pCurrentLevel + 1, my_list ) dessine_8_cubes ((lxmin + lxmax) / 2, lxmax, (lymin + lymax) / 2, lymax, lzmin, (lzmin + lzmax) / 2, pMaxLevel, pCurrentLevel + 1, my_list ) dessine_8_cubes ((lxmin + lxmax) / 2, lxmax, (lymin + lymax) / 2, lymax, (lzmin + lzmax) / 2, lzmax, pMaxLevel, pCurrentLevel + 1, my_list ) EndIf EndFunction Function dessine_octree () Local my_list:TList my_list = New TList glDisable (GL_TEXTURE_2D); glColor3ub (50, 255, 50); my_list = GetPointIntoList(m) dessine_8_cubes (-(gi_CubeSize/2), (gi_CubeSize/2), -(gi_CubeSize/2), (gi_CubeSize/2), -(gi_CubeSize/2), (gi_CubeSize/2),LA_PROFONDEUR, 1, my_list) glColor3ub (255, 255, 255); glEnable (GL_TEXTURE_2D); EndFunction Type TVertexInfo Field SurfIndex:Int Field VertIndex:Int EndType Function GetPointIntoList:TList(ThisEntity:TMesh ) ' Calculate the bounding box (in Object space) For this Object. ' You can precalculate this For every Object in your game For a huge speed increase! Local Surfaces:Int = CountSurfaces(ThisEntity) Local my_list:TList = New TList Local t:Int=0 For Local LOOP_Surface:Int = 1 To Surfaces Local Surface_Handle:TSurface = GetSurface(ThisEntity, LOOP_Surface) Local Verts:Int = CountVertices(Surface_Handle) - 1 For Local LOOP_Verts:Int = 0 To Verts-1 Local my_vi:TVertexInfo = New TVertexInfo my_vi.SurfIndex = LOOP_Surface my_vi.VertIndex = Loop_Verts my_list.AddLast my_vi Next Next Return my_list EndFunction Function Point_Inside_List:TList( min_x:Float, max_x:Float, min_y:Float, max_y:Float, min_z:Float, max_z:Float, thelist:TList ) Local my_list:TList = New TList For Local L:TVertexInfo = EachIn thelist Local Surface_Handle:TSurface = GetSurface(m, L.SurfIndex) Local vx:Float = VertexX#(Surface_Handle, L.VertIndex) Local vy:Float = VertexY#(Surface_Handle, L.VertIndex) Local Vz:Float = VertexZ#(Surface_Handle, L.VertIndex) ' Determine If the point (in Object space) is inside the bounding box (in Object space). If (vx# > min_x#) And (vx# < max_x#) And (vy# > min_y#) And (vy# < max_y#) And (Vz# > min_z#) And (vz# < max_z#) Local my_vi:TVertexInfo = New TVertexInfo my_vi.SurfIndex = L.SurfIndex my_vi.VertIndex = L.VertIndex my_list.AddLast my_vi EndIf Next Return my_list EndFunction 'f_bCheckSphereIntersect 'Return True If the two spheres intersect Function f_bCheckSphereIntersect:Int( p_fXCenter1:Float, p_fYCenter1:Float, p_fZCenter1:Float, p_fRadius1:Float, p_fXCenter2:Float, p_fYCenter2:Float, p_fZCenter2:Float, p_fRadius2:Float ) Local l_fXDiff:Float Local l_fYDiff:Float Local l_fZDiff:Float Local l_fDistance:Float ' Calculate distance between center points l_fXDiff = Abs(p_fXCenter2-p_fXCenter1) l_fYDiff = Abs(p_fYCenter2-p_fYCenter1) l_fZDiff = Abs(p_fZCenter2-p_fZCenter1) l_fDistance = Sqr(l_fXDiff*l_fXDiff+l_fYDiff*l_fYDiff+l_fZDiff*l_fZDiff) 'Return True If the two spheres intersect If(l_fDistance <= (p_fRadius1+p_fRadius2)) Then Return True 'No intersection Return False EndFunction