Voxel Hashing

Created On2020年8月6日

byskylook

1 Voxel Hashing

在大场景建图中，如果对于空间划分 Voxel 而实际上只有少量的 Voxel 存在点云，会存在内存和效率上的较大浪费，因此 Stanford University 在 2013 年提出了一种 Voxel Hashing 算法，只在有点云的表面划分 Voxel 而不在整个空间划分。使用 Hash 方式对空间中的坐标 $(x, y, z)$ 进行映射 Voxel 达到快速检索和稀疏表示的效果。

Voxel Hashing 结构如下：

其中 Voxel 保存的数据为 TSDF、颜色、权重。Voxel 数据结构为：

struct Voxel { 
	float sdf; // SDF数值
	uchar colorRGB[3]; // 颜色
	uchar weight; // 权重
};

struct Voxel {

float sdf; // SDF数值

uchar colorRGB[3]; // 颜色

uchar weight; // 权重

};

而在很多任务中常常需要查询相邻的 Voxel，因此比较简单的方式就是将相邻的 $8 \times 8 \times 8$ 个 Voxel 连接在一起组成 Voxel Block。而 Hash 实际对应的就是一个 Voxel Block。

Voxel Hash 的计算公式为：
$\begin{equation}H(x, y, z)=\left(x \cdot p_{1} \oplus y \cdot p_{2} \oplus z \cdot p_{3}\right) \bmod n\end{equation}$

其中， $p_{1}, p_{2}, p_{13}$ 是3个较大的素数，在文章中取值为：
$\begin{equation}\begin{matrix}p_{1}=73856093 \\p_{2}=19349669 \\p_{3}=83492791\end{matrix}\end{equation}$

相应代码为：

template<>
struct std::hash<ml::vec3i> : public std::unary_function<ml::vec3i, size_t> {
	size_t operator()(const ml::vec3i& v) const {
		//TODO larger prime number (64 bit) to match size_t
		const size_t p0 = 73856093;
		const size_t p1 = 19349669;
		const size_t p2 = 83492791;
		const size_t res = ((size_t)v.x * p0)^((size_t)v.y * p1)^((size_t)v.z * p2);
		return res;
	}
};

template<>

struct std::hash<ml::vec3i> : public std::unary_function<ml::vec3i, size_t> {

size_t operator()(const ml::vec3i& v) const {

//TODO larger prime number (64 bit) to match size_t

const size_t p0 = 73856093;

const size_t p1 = 19349669;

const size_t p2 = 83492791;

const size_t res = ((size_t)v.x * p0)^((size_t)v.y * p1)^((size_t)v.z * p2);

return res;

}

};

通过以上 Hash 函数我们就可以构造一个 Hash Table 完成映射。

在 Hash Table 中保存了 Hash Entry 作为指向对应 Voxel Block 的指针，具体数据结构如下：

struct HashEntry {
	short position[3]; // 体素块位置
	short offset; // 偏移量（用来存储超出 Hash Bucket 的情况）
	int pointer; // 指针
};

struct HashEntry {

short position[3]; // 体素块位置

short offset; // 偏移量（用来存储超出 Hash Bucket 的情况）

int pointer; // 指针

};

2 冲突解决

很显然任何 Hash 函数都有可能存在多个不同的 Voxel Block 映射到同一个 Hash 值的情况。类似上图中的红色块添加时，由于对应的位置已经有 Voxel Block，就产生了冲突的情况。解决此问题最简单的解决冲突的方式就是使用 Hash Bucket。每一个 Hash Bucket 存储了若干 Hash Entry，并通过 offset 指向下一个 Hash Entry 的位置。

在一个良好设计的 Hash 中，使用固定长度的 Hash Bucket 应该是不会出现溢出的，但是也不能排除异常的情况。上图演示了同一个 Hash 值产生冲突和解决的情况，这里 Hash Bucket 设计大小为 4。上图的 4 行就分别示意了 2 种插入和 2 种删除的情况。

插入 Hash Entry $(2,4,5)$ 时，如果出现溢出情况，则选择后面其他 Hash Bucket 中空余的位置插入（不能为该 Hash Bucket 的最后一个），并更新上一个 Hash Entry 的 offet 指向当前条目。
插入 Hash Entry $(8,1,7)$ 时，如果后面 Hash Bucket 空余的位置为最后一个，则不使用该位置插入（约定每个 Hash Bucket 的最后一个只存储当前 Hash 对应的 Hash Entry），跳到下一个 Hash Bucket 寻找位置。
删除一个 Hash Entry $(1,2,3)$ 时，如果偏移量显示有放入其他 Hash Bucket 的 Hash Entry $(2,4,5)$ 则直接用下一个替换当前被删除的。
删除一个 Hash Entry $(0,-2,3)$ 时，如果其后没有放入其他 Hash Bucket 的 Hash Entry，则直接删除即可。

参考材料

[1] Real-time 3D Reconstruction at Scale using Voxel Hashing
[2] https://blog.csdn.net/fuxingyin/article/details/51707057
[3] https://www.zhihu.com/search?type=content&q=voxel%20hash
[4] https://blog.csdn.net/shuang_yu_/article/details/105228997

Updated2022年8月6日

技术刘

Have a Question?

Voxel Hashing

1 Voxel Hashing

2 冲突解决

参考材料

Add a Comment