八叉树(Octree)是一种用于描述三维空间的树状数据结构。想象一个立方体,我们最少可以切成多少个相同等分的小立方体?答案就是8个。再想象我们有一个房间,房间里某个角落藏着一枚金币,我们想很快的把金币找出来,怎么找最高效?我们可以把房间当成一个立方体,先切成八个小立方体,然后排除掉没有放任何东西的小立方体,再把有可能藏金币的小立方体继续切八等份….如此下去,平均在Log8(房间内的所有物品数)的时间内就可找到金币。因此,八叉树就是用在3D空间中的场景管理,可以很快地知道物体在3D场景中的位置,或侦测与其它物体是否有碰撞以及是否在可视范围内。

八叉树(Octree)-LMLPHP

  VREP软件中可以在场景里创建八叉树(Add→Octree),通常用于简化表达复杂的形体或点云。An octree is an object that represents a spacial partitioning. It is made up by a tree data structure in which each node has exactly eight children. Occupied leaf nodes are represented as voxels. Octrees can be used to offer a simplified representation for shapes or point clouds, or can act as an occupancy grid/space:

  Octrees are collidable, measurable and detectable objects. This means that octrees:

  • can be used in collision detections with other collidable objects.
  • can be used in minimum distance calculations with other measurable objects.
  • can be detected by proximity sensors.

八叉树(Octree)-LMLPHP

  函数simInsertVoxelsIntoOctree可以向八叉树中插入Voxels (三维像素),它是一种基于体积概念的像素,通常的普通像素只需要X、Y轴两个坐标来定位它在空间中的方位,而它还需要加进一个额外的Z轴坐标,相当于空间中一个非常小的立方体。

simInsertVoxelsIntoOctree(number octreeHandle,number options,table points,table color=nil,table tag=nil)

  下面代码通过Octree创建了一个简单的围墙:

if (sim_call_type==sim_childscriptcall_initialization) then

    octree=simGetObjectAssociatedWithScript(sim_handle_self)

    local p = {-, , 0.05}
for i=,, do
color = {*math.random(),*math.random(),*math.random()}
simInsertVoxelsIntoOctree(octree, , {p[],p[]-*i/,p[]}, color, nil)
simInsertVoxelsIntoOctree(octree, , {p[]+*i/,p[],p[]}, color, nil)
simInsertVoxelsIntoOctree(octree, , {p[]+*i/,p[]-,p[]}, color, nil)
simInsertVoxelsIntoOctree(octree, , {p[]+,p[]-*i/,p[]}, color, nil)
end end if (sim_call_type==sim_childscriptcall_cleanup) then -- Put some restoration code here
simRemoveVoxelsFromOctree(octree, , nil) end
八叉树(Octree)-LMLPHP  其中两轮差速的机器人BubbleRob通过接近传感器来进行简单的避障行走。感知阶段调用simReadProximitySensor来获取接近传感器信息,如果检测到障碍物result返回1,没有检测到障碍物返回0,出错返回-1。同时计算传感器到障碍物的最小距离,结果保存在distance中。注意探测只会在探测区域(Detection Volume)内进行,所以注意设置传感器的属性(探测体形状、探测距离、角度等)。
number result,number distance = simReadProximitySensor(number sensorHandle)

八叉树(Octree)-LMLPHP

参考:

Octree—Wikipedia

Quadtrees and Octrees

游戏场景管理的八叉树算法是怎样的?

05-11 14:03