Version: v1.5.0

# 空间稀疏数据结构

##### note

Prerequisite: please read the Fields, Fields (advanced), and SNodes first.

## 动机

##### note

The key to leveraging spatial sparsity is replacing dense grids with sparse grids.

• Access with indices, which just like accessing a dense data structure.
• 迭代时自动并行。
• 自动内存访问优化。
##### note

Backend compatibility: The LLVM-based backends (CPU/CUDA) offer the full functionality for performing computations on spatially sparse data structures. 在 Metal 后端，稀疏数据结构现在已被弃用。 对动态 SNode（dynamic SNode）的支持已在 v1.3.0 中移除，对指针（pointer）/位掩码（bitmasked）SNode 的支持将在 v1.4.0 中移除。

##### note

Sparse matrices are usually not implemented in Taichi via spatially sparse data structures. 请参阅 稀疏矩阵

## Taichi 中的空间稀疏数据结构

Taichi 中的空间稀疏数据结构由 `pointer``bitmasked``dynamic`，和 `dense` SNode 组成。 一个只由 `dense` SNode 组成的 SNode 树不是空间稀疏数据结构。

##### note

Reading an inactive pixel returns zero.

### 指针 SNode

pointer.py
``x = ti.field(ti.f32)block = ti.root.pointer(ti.ij, (4,4))pixel = block.dense(ti.ij, (2,2))pixel.place(x)@ti.kerneldef activate():    x[2,3] = 1.0    x[2,4] = 2.0@ti.kerneldef print_active():    for i, j in block:        print("Active block", i, j)    # output: Active block 1 1    #         Active block 1 2    for i, j in x:        print('field x[{}, {}] = {}'.format(i, j, x[i, j]))    # output: field x[2, 2] = 0.000000    #         field x[2, 3] = 1.000000    #         field x[3, 2] = 0.000000    #         field x[3, 3] = 0.000000    #         field x[2, 4] = 2.000000    #         field x[2, 5] = 0.000000    #         field x[3, 4] = 0.000000    #         field x[3, 5] = 0.000000``

### 位掩码 SNode

bitmasked.py
``x = ti.field(ti.f32)block = ti.root.pointer(ti.ij, (4,4))pixel = block.bitmasked(ti.ij, (2,2))pixel.place(x)@ti.kerneldef activate():    x[2,3] = 1.0    x[2,4] = 2.0@ti.kerneldef print_active():    for i, j in block:        print("Active block", i, j)    for i, j in x:        print('field x[{}, {}] = {}'.format(i, j, x[i, j]))``

### 动态 SNode

`dynamic` 的第一个参数是轴，第二个参数是最大长度，第三个参数（可选）是 `chunk_size`

`chunk_size` 指定了动态 SNode 在先前分配的空间用尽时分配多少空间。 例如，`chunk_size=4`，动态 SNode 在添加第 1 个元素时分配四个元素的空间，在添加第 5（第 9、第 13...）个元素时再分配四个元素的空间。

dynamic.py
``pair = ti.types.struct(a=ti.i16, b=ti.i64)pair_field = pair.field()block = ti.root.dense(ti.i, 4)pixel = block.dynamic(ti.j, 100, chunk_size=4)pixel.place(pair_field)l = ti.field(ti.i32)ti.root.dense(ti.i, 5).place(l)@ti.kerneldef dynamic_pair():    for i in range(4):        pair_field[i].deactivate()        for j in range(i * i):            pair_field[i].append(pair(i, j + 1))        # pair_field = [[],        #              [(1, 1)],        #              [(2, 1), (2, 2), (2, 3), (2, 4)],        #              [(3, 1), (3, 2), ... , (3, 8), (3, 9)]]        l[i] = pair_field[i].length()  # l = [0, 1, 4, 9]``

##### note

A dynamic SNode must have one axis only, and the axis must be the last axis. 动态 SNode 下不可再放置其他 SNode。 换言之，动态 SNode 必须直接放置在 field 中。 沿着从动态 SNode 到 SNode 树根节点的路径，其他 SNode 不能 具有与动态 SNode 相同的轴。

## 空间稀疏数据结构的计算

### 显式操作和查询稀疏性

Taichi 还提供可以显示操作数据结构稀疏性的 API。 你可以手动检查 SNode 的活跃度，激活 SNode，或者使 SNode 失活。 我们现在基于如下定义的 field 来说明这些功能。

``x = ti.field(dtype=ti.i32)block1 = ti.root.pointer(ti.ij, (3, 3))block2 = block1.pointer(ti.ij, (2, 2))pixel = block2.bitmasked(ti.ij, (2, 2))pixel.place(x)``

#### 1. 活跃度检查

``@ti.kerneldef activity_checking(snode: ti.template(), i: ti.i32, j: ti.i32):    print(ti.is_active(snode, [i, j]))for i in range(3):    for j in range(3):        activity_checking(block1, i, j)for i in range(6):    for j in range(6):        activity_checking(block2, i, j)for i in range(12):    for j in range(12):        activity_checking(pixel, i, j)``

#### 2. 激活

``@ti.kerneldef activate_snodes():    ti.activate(block1, [1, 0])    ti.activate(block2, [3, 1])    ti.activate(pixel, [7, 3])activity_checking(block1, 1, 0) # output: 1activity_checking(block2, 3, 1) # output: 1activity_checking(pixel, 7, 3)  # output: 1``

#### 3. 失活

• 使用 `ti.deactivate(snode, [i, j, ...])` 显式让 `snode[i, j, ...]` 的一个单元转为不活跃。
• 使用 `snode.deactivate_all()` 来取消激活 SNode `snode` 的所有单元。 这个操作也会递归地使其所有的子节点不再活跃。
• 使用 `ti.disactivate_all_snodes()` 来取消激活所有稀疏 SNode 的所有单元。

##### note

For performance reasons, `ti.activate(snode, index)` only activates `snode[index]`. 编程人员必须确保 `snode[index]` 的所有祖先容器已经激活。 否则，此操作会引起未定义的行为。

• 不会递归取消激活一个单元的所有后代。
• 不会触发取消激活其父容器，即使父容器的所有子容器都已取消激活。

#### 4. 祖先索引查询

``print(ti.rescale_index(x, block1, ti.Vector([7, 3]))) # output: [1, 0]print(ti.rescale_index(x, block2, [7, 3]))            # output: [3, 1]print(ti.rescale_index(x, pixel,  [7, 3]))            # output: [7, 3]print(ti.rescale_index(block2, block1, [3, 1]))       # output: [1, 0]``

## 扩展阅读

Taichi elements 是一个在 Taichi 稀疏网格上实现的高性能 MLS-MPM 求解器。