八叉树（Octree）

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

VREP软件中可以在场景里创建八叉树（Add→Octree），通常用于简化表达复杂的形体或点云。An octree is anobjectthat 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 forshapesorpoint clouds, or can act as an occupancy grid/space:

Octrees arecollidable,measurableanddetectable objects. This means that octrees:

• can be used incollision detectionswith other collidable objects.
• can be used inminimum distance calculationswith other measurable objects.
• can be detected byproximity sensors.

函数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 = {-1, 1, 0.05}
    for i=0,20,1 do
        color = {255*math.random(),255*math.random(),255*math.random()}
        simInsertVoxelsIntoOctree(octree, 0, {p[1],p[2]-2*i/20,p[3]}, color, nil)
        simInsertVoxelsIntoOctree(octree, 0, {p[1]+2*i/20,p[2],p[3]}, color, nil)
        simInsertVoxelsIntoOctree(octree, 0, {p[1]+2*i/20,p[2]-2,p[3]}, color, nil)
        simInsertVoxelsIntoOctree(octree, 0, {p[1]+2,p[2]-2*i/20,p[3]}, color, nil)
    end
end
if (sim_call_type==sim_childscriptcall_cleanup) then
    --Put some restoration code here
    simRemoveVoxelsFromOctree(octree, 0, nil)
end

View Code

　　其中两轮差速的机器人BubbleRob通过接近传感器来进行简单的避障行走。感知阶段调用simReadProximitySensor来获取接近传感器信息，如果检测到障碍物result返回1，没有检测到障碍物返回0，出错返回-1。同时计算传感器到障碍物的最小距离，结果保存在distance中。注意探测只会在探测区域（Detection Volume）内进行，所以注意设置传感器的属性（探测体形状、探测距离、角度等）。

number result,number distance = simReadProximitySensor(number sensorHandle)

参考：

Octree—Wikipedia

Quadtrees and Octrees

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