November 28, 2020, 02:04:00 PM

Author Topic: [bb] Tree System by John J. [ 1+ years ago ]  (Read 740 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bb] Tree System by John J. [ 1+ years ago ]
« on: June 29, 2017, 12:28:40 AM »
Title : Tree System
Author : John J.
Posted : 1+ years ago

Description : This tree system is a fast, prop style tree system. The tree system dynamically optimizes the trees' level of detail for maximum performance.

The system is based on layers. Individual trees may not have their own textures, although each tree may be assigned to a different layer. For example, if you need 30,000 trees from 10 different tree textures, you would make 10 layers. Then you would assign each of the 10 textures to their own layer. Then, when each tree is created, it would be assigned to the desired layer for it's texture to be applied. The layer system helps to minimize surfaces, which increases performance.

The tree system also seperates trees into groups which are automatically hidden when out of view by Blitz3D's 3D engine. All this is done automatically, so all you have to worry about is the amount of "groups" for the tree system to use. The group grid size is 10x10 at default but may be adjusted for best performance.

A demo with source code and media can be downloaded <a href="http://www.alsbonsai.com/john/TreeSystemDemo.zip" target="_blank">here[/url].

The demo is a modified version of the Castle Demo included with Blitz3D. The demo creates 50,000 (fifty thousand) trees densely covering the surrounding hills of the castle. It runs at 30-40 FPS on a NVIDIA GeForce 2 MX/MX, and at 75-100 FPS on a NVIDIA GeForce Go 5200 FX.


Code :
Code: BlitzBasic
  1. ;*************************************************************************
  2. ;Fast Tree System
  3. ;                                                                                               Written by John Judnich
  4. ;*************************************************************************
  5.  
  6. ;Note: This tree system may perform poorly in debug mode
  7.  
  8. Const MAXLAYERS=100
  9. Global TS_bank,TS_xtiles,TS_ztiles,TS_layers,TS_x1#,TS_x2#,TS_z1#,TS_z2#,TS_LOD=1,TS_morph=True,TS_camera=-1
  10. Dim TS_layertexture(MAXLAYERS)
  11. Dim TS_layerFX(MAXLAYERS)
  12. ;Dim TS_layerLOD(MAXLAYERS)
  13. Const XPROP=1 ;Two polygons forming an 'X'
  14. Const IPROP=2 ;One polygon for flat props, sprites, etc.
  15.  
  16. Type PropGroup
  17.   Field mesh
  18.   Field props
  19.   Field propbank
  20.   Field polycount
  21. End Type
  22.  
  23. Type Prop
  24.   Field vertex,verts
  25.   Field surface
  26.   Field x#,y#,z#,yaw#,xs#,ys#,zs#
  27.   Field r,g,b,alpha#
  28. End Type
  29.  
  30. ;This function must be called before any of the tree system functions
  31. ;can be used. x1,z1,x2, And z2 are the bounds of the tree system. layers
  32. ;is the number of different trees that can be used (you can't texture Each
  33. ;tree individually). xtiles and ztiles are settings used for the occlusion
  34. Function InitTreeSystem(x1#,z1#,x2#,z2#,layers,xtiles=10,ztiles=10)
  35.   ;Setup variables
  36.   TS_xtiles=xtiles-1:TS_ztiles=ztiles-1:TS_layers=layers-1
  37.   TS_x1=x1:TS_x2=x2:TS_z1=z1:TS_z2=z2
  38.  
  39.   ;Create prop group handle bank
  40.   TS_bank=CreateBank((TS_xtiles+1)*(TS_ztiles+1)*(TS_layers+1)*5)
  41.  
  42.   ;Make all the prop groups needed
  43.   For z=0 To TS_ztiles
  44.         For x=0 To TS_xtiles
  45.           For l=0 To TS_layers
  46.                 group=CreatePropGroup()
  47.                 WriteTSBank(x,z,l,group)
  48.                 WriteTSBank2(x,z,l,IPROP) ;Default groups to low detail for faster loading
  49.                 HideEntity group ;Hide until used
  50.           Next
  51.         Next
  52.   Next
  53.   For l=1 To TS_layers+1
  54.         LayerFX(l,2+16)
  55.         ;LayerViewDist(l,10)
  56.   Next
  57. End Function
  58.  
  59. ;This function sets the camera to use for LOD calculations. Use this
  60. ;function to set the tree system camera to the main camera in your program.
  61. ;If no camera is set when UpdateTreeSystemLOD is called
  62. Function SetTreeSystemCamera(camera)
  63.   TS_camera=camera
  64. End Function
  65.  
  66. ;This function sets the level of detail for the tree system. The
  67. ;detail_level is actually the radius (in tiles) where trees will change
  68. ;to their higher detail level. Morph can be set to true or false, setting
  69. ;"morphing" on or off. Morphing actually just slowly changes trees from
  70. ;one detail level to another, instead of changing all that need to be
  71. ;changed at once (this smoothes out temporary frame rate drops when moving
  72. ;from one "tile" to another).
  73. Function SetTreeSystemLOD(detail_level,morph=True)
  74.   TS_LOD=detail_level
  75.   TS_morph=morph
  76. End Function
  77.  
  78. ;Use this function if you want to delete all trees for any reason
  79. Function DestroyTreeSystem()
  80.   ;Delete all the prop groups
  81.   For z=0 To TS_ztiles
  82.         For x=0 To TS_xtiles
  83.           For l=0 To TS_layers
  84.                 DestroyPropGroup(ReadTSBank(x,z,l))
  85.           Next
  86.         Next
  87.   Next
  88.  
  89.   ;Delete prop group bank
  90.   FreeBank TS_bank
  91. End Function
  92.  
  93. ;This textures a layer in the tree system
  94. Function LayerTexture(layer,texture)
  95.   TS_layertexture(layer-1)=texture
  96.   For z=0 To TS_ztiles
  97.         For x=0 To TS_xtiles
  98.           EntityTexture ReadTSBank(x,z,layer-1),texture
  99.         Next
  100.   Next
  101. End Function
  102.  
  103. ;This sets the EntityFX for a layer in the tree system
  104. Function LayerFX(layer,fx)
  105.   TS_layerFX(layer-1)=fx
  106.   For z=0 To TS_ztiles
  107.         For x=0 To TS_xtiles
  108.           EntityFX ReadTSBank(x,z,layer-1),fx
  109.         Next
  110.   Next
  111. End Function
  112.  
  113. ;This sets the maximum viewing distance (in tiles) for trees in a layer
  114. ;Function LayerViewDist(layer,dist)
  115. ;  TS_layerLOD(layer-1)=dist
  116. ;End Function
  117.  
  118. ;This makes a tree at the coordinates x,y,z with the specified layer. The
  119. ;x and z coordinates are permanent, but the y coordinate can be changed
  120. Function CreateTree(x#,y#,z#,layer)
  121.   ;Locate grid square to put tree
  122.   xg=TSXGridLoc(x)
  123.   zg=TSZGridLoc(z)
  124.  
  125.   ;Read group to put tree in and group detail level
  126.   group=ReadTSBank(xg,zg,layer-1)
  127.   detail=ReadTSBank2(xg,zg,layer-1)
  128.  
  129.   ;Create the prop with in the group with it's detail level
  130.   prop=CreateProp(group,detail)
  131.  
  132.   ;Position the tree at it's correction location
  133.   PositionProp(prop,x#,y#,z#)
  134.  
  135.   ;Randomly rotate the tree
  136.   RotateProp(prop,Rnd#(0,360))
  137.  
  138.   ;Show used group (by default groups are hidden to increase performance)
  139.   ShowEntity group
  140.  
  141.   Return prop
  142. End Function
  143.  
  144. ;This positions a tree along the y axis
  145. Function TreePositionY(tree,y#)
  146.   tmp.Prop=Object.Prop(tree)
  147.   MoveProp(tree,0,y#-tmpy,0)
  148. End Function
  149.  
  150. ;This scales a tree according to xs,ys, and zs
  151. Function ScaleTree(tree,xs#,ys#,zs#)
  152.   ScaleProp(tree,xs#,ys#,zs#)
  153. End Function
  154.  
  155. ;This colors a tree
  156. Function ColorTree(tree,r,g,b)
  157.   ColorProp(tree,r,g,b)
  158. End Function
  159.  
  160. ;This sets a tree's alpha (opacity)
  161. Function TreeAlpha(tree,alpha#)
  162.   PropAlpha(tree,alpha#)
  163. End Function
  164.  
  165. ;This rotates a tree along the y axis (yaw) relative to it's last rotation
  166. ;Function TurnTree(tree,yaw#)
  167.   ;TurnProp(tree,yaw#)
  168. ;End Function
  169.  
  170. ;Call this function just before the RenderWorld command. This function
  171. ;dynamicly updates trees' LOD (level of detail). This command will fail
  172. ;if no tree system camera has been set (see SetTreeSystemCamera)
  173. Function UpdateTreeSystem()
  174. ;tx=MilliSecs()
  175.   ;Check camera
  176.   If TS_camera=-1 Then RuntimeError "Error: UpdateTreeSystemLOD() function has been called, and no tree system camera has been set yet."
  177.  
  178.   ;Locate grid squares that the camera is in
  179.   xg=TSXGridLoc(EntityX(TS_camera,True))
  180.   zg=TSZGridLoc(EntityZ(TS_camera,True))
  181.  
  182.   ;Calculate the level of detail for each grid square and update it if it has changed
  183.   For z=0 To TS_ztiles
  184.         For x=0 To TS_xtiles
  185.           ;Calculate level of detail
  186.           xd=Abs(x-xg)
  187.           zd=Abs(z-zg)
  188.           If xd<=TS_LOD And zd<=TS_LOD Then detail=XPROP Else detail=IPROP
  189.           ;Hide tiles out of range
  190.           ;For l=0 To TS_layers
  191.                 ;If TS_LayerLOD(l)<>False And (xd>TS_LayerLOD(l) Or zd>TS_LayerLOD(l)) Then HideEntity ReadTSBank(x,z,l) Else ShowEntity ReadTSBank(x,z,l)
  192.           ;Next
  193.           ;Check if grid tile needs updating
  194.           If ReadTSBank2(x,z,0)<>detail Then
  195.                 ;Update grid tile
  196.             For l=0 To TS_layers
  197.                   RegenerateGroup(x,z,l,detail)
  198.             Next
  199.                 WriteTSBank2(x,z,0,detail)
  200.                 If TS_morph=True Then Return ;Don't change all at once
  201.           End If
  202.         Next
  203.   Next
  204. ;If MilliSecs()-tx>10 then DebugLog MilliSecs()-tx
  205. End Function
  206.  
  207.  
  208.  
  209. ;(Internal functions:)
  210. Function TSXGridLoc(x#)
  211.   n#=(x#-TS_x1#)/(TS_x2#-TS_x1#)
  212.   rtn=n#*TS_xtiles
  213.   Return rtn
  214. End Function
  215.  
  216. Function TSZGridLoc(z#)
  217.   n#=(z#-TS_z1#)/(TS_z2#-TS_z1#)
  218.   rtn=n#*TS_ztiles
  219.   Return rtn
  220. End Function
  221.  
  222. Function WriteTSBank(x,z,l,value)
  223.   pos=(l*(TS_xtiles+1)*(TS_ztiles+1))+(z*(TS_xtiles+1)+x)
  224.   PokeInt TS_bank,pos*5,value
  225. End Function
  226.  
  227. Function WriteTSBank2(x,z,l,value)
  228.   pos=(l*(TS_xtiles+1)*(TS_ztiles+1))+(z*(TS_xtiles+1)+x)
  229.   PokeByte TS_bank,(pos*5)+4,value
  230. End Function
  231.  
  232. Function ReadTSBank(x,z,l)
  233.   pos=(l*(TS_xtiles+1)*(TS_ztiles+1))+(z*(TS_xtiles+1)+x)
  234.   Return PeekInt(TS_bank,pos*5)
  235. End Function
  236.  
  237. Function ReadTSBank2(x,z,l)
  238.   pos=(l*(TS_xtiles+1)*(TS_ztiles+1))+(z*(TS_xtiles+1)+x)
  239.   Return PeekByte(TS_bank,(pos*5)+4)
  240. End Function
  241.  
  242. Function RegenerateGroup(x,z,l,detail)
  243.   ;Get the group from the bank
  244.   group=ReadTSBank(x,z,l)
  245.   grp.PropGroup=Object.PropGroup(EntityName(group))
  246.  
  247.   ;Create a new group
  248.   group2=CreatePropGroup()
  249.   grp2.PropGroup=Object.PropGroup(EntityName(group2))
  250.  
  251.   ;Copy all the trees from the old group to the new group, with the new detail level
  252.   props=BankSize(grppropbank)/4
  253.   For i=1 To props
  254.         ;Get the old and new prop
  255.         oldprop=PeekInt(grppropbank,(i*4)-4)
  256.         oldprp.Prop=Object.Prop(oldprop)
  257.         prop=CreateProp(group2,detail)
  258.         prp.Prop=Object.Prop(prop)
  259.        
  260.         PositionProp(prop,oldprpx,oldprpy,oldprpz)      ;Copy position
  261.         TurnProp(prop,oldprpyaw)                                                ;Copy rotation
  262.         ScaleProp(prop,oldprpxs,oldprpys,oldprpzs)      ;Copy scale
  263.         ColorProp(prop,oldprp
  264. ,oldprpg,oldprp)               ;Copy color
  265.         PropAlpha(prop,oldprpalpha)                                     ;Copy alpha
  266.   Next
  267.  
  268.   ;Copy texture and EntityFX
  269.   EntityFX group2,TS_layerFX(l)
  270.   EntityTexture group2,TS_layertexture(l)
  271.  
  272.   ;Delete the old group
  273.   DestroyPropGroup(group)
  274.  
  275.   ;Put the new prop group handle into the bank in place of the old one
  276.   WriteTSBank(x,z,l,group2)
  277. End Function
  278.  
  279. Function CreatePropGroup()
  280.   ;Create the new group
  281.   grp.PropGroup=New PropGroup
  282.  
  283.   ;Set up it's mesh with one surface
  284.   grpmesh=CreateMesh()
  285.   surface=CreateSurface(grpmesh)
  286.   NameEntity grpmesh,Handle(grp)
  287.   EntityFX grpmesh,2+16 ;Vert. colors + no culling
  288.  
  289.   ;Create the prop list bank
  290.   grppropbank=CreateBank()
  291.  
  292.   ;Return the mesh's handle
  293.   Return grpmesh
  294. End Function
  295.  
  296. Function DestroyPropGroup(group)
  297.   grp.PropGroup=Object.PropGroup(EntityName(group))
  298.  
  299.   FreeBank grppropbank
  300.   FreeEntity grpmesh
  301.  
  302.   Delete grp.PropGroup
  303. End Function
  304.  
  305. Function GetPropCount(group)
  306.   grp.PropGroup=Object.PropGroup(EntityName(group))
  307.   Return grpprops  
  308. End Function
  309.  
  310. Function GetProp(group,indx)
  311.   grp.PropGroup=Object.PropGroup(EntityName(group))
  312.   Return PeekInt(grppropbank,(indx*4)-4)
  313. End Function
  314.  
  315. Function CreateProp(group,proptype=XPROP)
  316.   ;Get the group's surface
  317.   grp.PropGroup=Object.PropGroup(EntityName(group))
  318.   surface=GetSurface(grpmesh,1)
  319.  
  320.   ;Resize the bank
  321.   grpprops=grpprops+1
  322.   ResizeBank grppropbank,grpprops*4
  323.  
  324.   ;Create the new prop 
  325.   prop.Prop=New Prop
  326.   propxs=1.0:propys=1.0:propzs=1.0
  327.   ;Side 1
  328.   propvertex=AddVertex(surface,0,-.54,0  ,.5,1.7) ;bottom
  329.                           AddVertex(surface,-1,.76,0  ,-.65,0) ;right
  330.                           AddVertex(surface,1,.76,0  ,1.65,0) ;left
  331.   AddTriangle(surface,propvertex+2,propvertex+1,propvertex+0)
  332.  
  333.   ;Side 2
  334.   If proptype=XPROP Then
  335.                           AddVertex(surface,0,-.54,0  ,.5,1.7) ;bottom
  336.                           AddVertex(surface,0,.76,-1  ,-.65,0) ;front
  337.                           AddVertex(surface,0,.76,1  ,1.65,0) ;back
  338.         AddTriangle(surface,propvertex+5,propvertex+4,propvertex+3)
  339.   End If
  340.   propsurface=surface
  341.  
  342.   If proptype=XPROP Then propverts=5
  343.   If proptype=IPROP Then propverts=2
  344.  
  345.   ;Put the new prop into the group's bank
  346.   PokeInt grppropbank,(grpprops*4)-4,Handle(prop)
  347.   grppolycount=grppolycount+2
  348.  
  349.   prop
  350. =255:propg=255:prop=255
  351.   propalpha#=1
  352.  
  353.   ;Return the prop's handle
  354.   Return Handle(prop)
  355. End Function
  356.  
  357. Function ColorProp(prop,r,g,b)
  358.   tmp.Prop=Object.Prop(prop)
  359.   tmp
  360. =r:tmpg=g:tmp=b
  361.   For i=0 To tmpverts
  362.         VertexColor tmpsurface,tmpvertex+i,r,g,b
  363.   Next
  364. End Function
  365.  
  366. Function PropAlpha(prop,alpha#)
  367.   tmp.Prop=Object.Prop(prop)
  368.   tmpalpha#=alpha#
  369.   For i=0 To tmpverts
  370.         VertexColor tmpsurface,tmpvertex+i,VertexRed(tmpsurface,tmpvertex+i),VertexGreen(tmpsurface,tmpvertex+i),VertexBlue(tmpsurface,tmpvertex+i),alpha#
  371.   Next
  372. End Function
  373.  
  374. Function PropTexCoords(prop,u1#,v1#,u2#,v2#)
  375.   tmp.Prop=Object.Prop(prop)
  376.  
  377. End Function
  378.  
  379. Function MoveProp(prop,mx#,my#,mz#)
  380.   tmp.Prop=Object.Prop(prop)
  381.   For i=0 To tmpverts
  382.         x#=VertexX(tmpsurface,tmpvertex+i)
  383.         y#=VertexY(tmpsurface,tmpvertex+i)
  384.         z#=VertexZ(tmpsurface,tmpvertex+i)
  385.         VertexCoords tmpsurface,tmpvertex+i,x#+mx#,y#+my#,z#+mz#
  386.   Next
  387.   tmpx=tmpx+mx#
  388.   tmpy=tmpy+my#
  389.   tmpz=tmpz+mz#
  390. End Function
  391.  
  392. Function PositionProp(prop,x#,y#,z#)
  393.   tmp.Prop=Object.Prop(prop)
  394.   MoveProp(prop,x#-tmpx,y#-tmpy,z#-tmpz)
  395. End Function
  396.  
  397. Function ScaleProp(prop,xs#,ys#,zs#)
  398.   tmp.Prop=Object.Prop(prop)
  399.   tmpxs=tmpxs*xs:tmpys=tmpys*ys:tmpzs=tmpzs*zs
  400.   For i=0 To tmpverts
  401.         dx#=VertexX(tmpsurface,tmpvertex+i)-tmpx
  402.         dy#=VertexY(tmpsurface,tmpvertex+i)-tmpy
  403.         dz#=VertexZ(tmpsurface,tmpvertex+i)-tmpz
  404.         x#=tmpx+dx#*xs#
  405.         y#=tmpy+dy#*ys#
  406.         z#=tmpz+dz#*zs#
  407.         VertexCoords tmpsurface,tmpvertex+i,x#,y#,z#
  408.   Next
  409. End Function
  410.  
  411. Function TurnProp(prop,yaw#)
  412.   tmp.Prop=Object.Prop(prop)
  413.   tmpyaw=tmpyaw+yaw#
  414.  
  415.   CosAY#=Cos(yaw)
  416.   SinAY#=Sin(yaw)
  417.  
  418.   For i=0 To tmpverts
  419.         x#=VertexX(tmpsurface,tmpvertex+i)-tmpx
  420.         y#=VertexY(tmpsurface,tmpvertex+i)-tmpy
  421.         z#=VertexZ(tmpsurface,tmpvertex+i)-tmpz
  422.  
  423.         ;Rotate around y axis
  424.         tx#=x*cosAY+z*sinAY
  425.         z=z*cosAY-x*sinAY
  426.         x=tx
  427.  
  428.         x=x+tmpx
  429.         y=y+tmpy
  430.         z=z+tmpz
  431.         VertexCoords tmpsurface,tmpvertex+i,x,y,z
  432.   Next
  433. End Function
  434.  
  435. Function RotateProp(prop,yaw#)
  436.   tmp.Prop=Object.Prop(prop)
  437.   TurnProp(prop,yaw#-tmpyaw#)
  438. End Function
  439.  
  440. Function UpdatePropGroupNormals(group)
  441.   grp.PropGroup=Object.PropGroup(EntityName(group))
  442.   UpdateNormals grpMesh
  443. End Function


Comments :


puki(Posted 1+ years ago)

 Jeez, that's a lot of trees!I was running the default demo of 50,00 at 200 FPS.Largness.


GQ(Posted 1+ years ago)

 This a really good way to represent props.I found this better for showing grass though.This would also be neat if used in conjunctionwith the grass map samples shown in boards.I wonder if this system can be easily modifiedto handle custom prop shapes. (like V-shaped props)It's a great prop system!


T-Head(Posted 1+ years ago)

 Works very well, but just in fullscreen mode! If I run it in windowed mode, the FPS is under 30!


Trader3564(Posted 1+ years ago)

 lol, i ran with 200.000 trees at 30FPS nice!!Trees look a bit cheap tough, but ofcorse we can put our own content there :)What would improve this system is that it would only display trees within rang and hide the others to optimaze speed.


Oiduts Studios(Posted 1+ years ago)

 I know this is old but I got 1,250,000 trees with 125 FPS, I love this code, and my computer.


Dreamora(Posted 1+ years ago)

 very nice :)due to the texture binding I wouldn't use it for trees, but for gras it definitely makes a pretty solid solution :)


ZJP(Posted 1+ years ago)

 Woaaa !!.Very good code. THXJP


Captain Wicker (crazy hillbilly)(Posted 1+ years ago)

 this is very good, May come in handy :)


Guy Fawkes(Posted 1+ years ago)

 WOH! First time seeing this! Does anyone have an example of how to use this?! O_O


Captain Wicker (crazy hillbilly)(Posted 1+ years ago)

 Here: <a href="http://www.alsbonsai.com/john/TreeSystemDemo.zip" target="_blank">http://www.alsbonsai.com/john/TreeSystemDemo.zip[/url]


Guy Fawkes(Posted 1+ years ago)

 O nvm. I thought this generated trees on the fly.


RemiD(Posted 1+ years ago)

 Hello,If anybody has the "TreeSystemDemo.zip" file, can you upload it somewhere and share a link, please ?Thanks,


RemiD(Posted 1+ years ago)

 here : http://web.archive.org/web/20070111180307/http://www.alsbonsai.com/john/TreeSystemDemo.zip


Rick Nasher(Posted 1+ years ago)

 Interesting one too.


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal