Nearest neighbor search using compressed octrees representing high definition maps for autonomous vehicles

One or more non-transitory computer readable media storing instructions that in response to being executed by one or more processors, cause a computer system to perform operations, the operations comprising:

• receiving a search query for points near a query-point, the search query specifying a search space comprising the query-point and a search range;
• accessing a compressed octree representation of a point cloud comprising three-dimensional (3D) points of a region, the compressed octree representation comprising nodes, at least some of the nodes storing a sibling link to a sibling node having the same parent node;
• traversing the compressed octree representation to identify regions that overlap the search space, the traversing comprising:
• responsive to determining that a current node is a leaf node, marking the node as overlapping the search space,
• responsive to determining that a region represented by the current node overlaps the search space, identifying a child node of the current node and performing a nearest neighbor search in the child node, and
• responsive to determining that the region represented by the current node does not overlap the search space, identifying a sibling node of the current node using the sibling link and performing the nearest neighbor search in the sibling node;
• identifying at least one nearest neighbor node in a set of leaf nodes identified as overlapping the search space;
• and
• using the at least one nearest neighbor node for performing an operation on the point cloud.

A computer system comprising:

• one or more processors;
• and
• one or more non-transitory computer readable media storing instructions that in response to being executed by the one or more processors, cause the computer system to perform operations, the operations comprising:
• receiving a search query for points near a query-point, the search query specifying a search space comprising the query-point and a search range;
• accessing a compressed octree representation of a point cloud comprising three-dimensional (3D) points of a region, the compressed octree representation comprising nodes, at least some of the nodes storing a sibling link to a sibling node having the same parent node;
• traversing the compressed octree representation to identify regions that overlap the search space, the traversing comprising:
• responsive to determining that a current node is a leaf node, marking the node as overlapping the search space,
• responsive to determining that a region represented by the current node overlaps the search space, identifying a child node of the current node and performing a nearest neighbor search in the child node, and
• responsive to determining that the region represented by the current node does not overlap the search space, identifying a sibling node of the current node using the sibling link and performing the nearest neighbor search in the sibling node;
• identifying at least one nearest neighbor node in a set of leaf nodes identified as overlapping the search space;
• and
• using the at least one nearest neighbor node for performing an operation on the point cloud.