1. 从“随机抓一把”到“均匀铺开”：为什么我们需要FPS？

大家好，我是老张，在3D视觉和点云处理这个行当里摸爬滚打了十来年。今天咱们不聊那些虚头巴脑的概念，就来聊聊一个几乎所有做点云的同学都绕不开，又爱又恨的算法——最远点采样，也就是大家常说的FPS。

想象一下这个场景：你面前有一大堆散落的乐高积木块，可能有成千上万个。你的任务是，只从中挑出100块，然后用这100块去拼出一个尽可能像原物的模型。你会怎么挑？如果闭着眼睛随机抓100块，很可能抓到的全是红色的，或者全是小方块，拼出来的东西肯定“四不像”。一个更聪明的办法是：第一块随便拿；然后，第二块就拿离第一块最远的那块；第三块呢，就拿离前两块中最近的那个距离最远的那块……如此反复。这样挑出来的积木，大概率会均匀地分布在原始那堆积木的各个角落，用它们去重建模型，轮廓和细节保留得就好得多。

FPS干的就是这个事儿。在点云处理中，无论是做三维重建、点云分类、分割还是配准，原始点云动辄几十万、上百万个点，直接处理计算量太大，显卡也吃不消。我们必须先对它进行下采样，也就是从海量点中选出有代表性的一个子集。FPS的核心优势就在于，它能最大程度地保证采样后点集的均匀性和覆盖度，避免点都挤在一坨，丢失了物体边缘和关键结构的信息。这对于后续神经网络理解点云的形状至关重要。

但FPS有个众所周知的“硬伤”：慢。它的计算复杂度是O(n²)级别的。假如你有1万个点要采样1000个，那可不是简单的算1000次，而是每次都要计算所有剩余点到当前已采样点集的最小距离，再找最大值。这个计算量，在追求实时性的应用里（比如自动驾驶的激光雷达感知），简直是灾难。

所以，今天这篇文章，我就结合自己这些年踩过的坑和优化的经验，跟大家掰开揉碎了讲讲，怎么把FPS这个“经典老将”用得又快又好。我们不只讲原理和基础代码，更要深入探讨在实战中，如何通过GPU并行加速、距离计算优化、算法策略改进等手段，让它飞起来。

2. 庖丁解牛：手把手实现并理解基础FPS

光说不练假把式，咱们先从一个最朴实无华的FPS实现开始，把每一行代码都吃透。这里我用PyTorch来写，因为它和GPU结合紧密，也是目前深度学习领域的主流。

2.1 核心代码逐行解读

我们先回顾一下最基础的FPS函数。别看代码不长，里面的门道可不少。

import torch

def farthest_point_sample(xyz, npoint):
    """
    输入：
        xyz: 点云数据，形状为 [B, N, 3]。B是批次大小，N是点云数量，3是xyz坐标。
        npoint: 需要采样的点数。
    返回：
        centroids: 采样点的索引，形状为 [B, npoint]。
    """
    device = xyz.device
    B, N, C = xyz.shape

    # 初始化一个全零张量，用来存放最终采样的点的索引
    centroids = torch.zeros(B, npoint, dtype=torch.long).to(device)

    # 初始化一个距离矩阵，记录每个点到当前采样点集的“最小距离”
    # 初始值设为一个很大的数（1e10），意味着一开始所有点都“离采样点集很远”
    distance = torch.ones(B, N).to(device) * 1e10

    # 第一步：随机初始化第一个采样点。为每个Batch随机选一个。
    farthest = torch.randint(0, N, (B,), dtype=torch.long).to(device)

    # 生成Batch的索引，方便后续操作
    batch_indices = torch.arange(B, dtype=torch.long).to(device)

    # 开始迭代，采样npoint个点
    for i in range(npoint):
        # 1. 登记：把本轮选出的最远点索引存入结果列表
        centroids[:, i] = farthest

        # 2. 取坐标：根据索引，取出这个最远点的三维坐标 [B, 3]
        #    然后扩展维度为 [B, 1, 3]，为了后面做广播计算
        centroid = xyz[batch_indices, farthest, :].view(B, 1, 3)

        # 3. 计算距离：计算所有点（N个）到这个新增采样点的欧氏距离的平方
        #    xyz形状是[B, N, 3]，centroid是[B, 1, 3]，广播后相减，得到[B, N, 3]
        #    对最后一个维度（坐标维度）求和，得到每个点到这个centroid的距离平方[B, N]
        dist = torch.sum((xyz - centroid) ** 2, -1)

        # 4. 更新最小距离：这是FPS算法的精髓所在！
        #    distance矩阵始终维护着：每个点 到 所有已采样点 的 最小距离。
        #    新来了一个采样点，我们计算所有点到它的距离dist。
        #    如果这个dist比distance里记录的旧“最小距离”还小，说明这个新采样点离它更近，那么就更新这个更小的值。
        #    用mask实现原地更新，非常高效。
        mask = dist < distance
        distance[mask] = dist[mask]

        # 5. 选择下一个：更新完distance后，从里面找出那个“最小距离”最大的点。
        #    也就是找那个离所有已采样点“最近距离”都最远的点，作为下一个采样点。
        #    torch.max返回（最大值，索引），我们取索引[1]。
        farthest = torch.max(distance, -1)[1]

    return centroids

我当年第一次写FPS时，就在第4步“更新最小距离”这里卡了很久。一定要理解，distance 这个矩阵的含义不是“距离之和”，而是 “每个点到其最近的那个已采样点的距离”。比如，已采样点有A和B，对于点P来说，它到A的距离是5，到B的距离是3，那么distance里记录的就是3。当新采样点C加入后，算出P到C的距离是4，因为4 > 3，所以P的“最小距离”保持不变，还是3。如果P到C的距离是2，那么distance里P的值就会被更新为2。

这个设计非常巧妙，它避免了每次迭代都需要计算一个点与所有已采样点的距离并求和（那复杂度就爆炸了），而是通过持续维护一个最小值，将计算复杂度降了下来。每次迭代，我们只需要计算所有点到“上一个新增采样点”的距离，然后和历史的“最小距离”比一比，取更小的那个就行。

2.2 一个生动的例子：眼见为实

为了让大家更有体感，我写个小脚本，用Matplotlib可视化一下FPS的过程。我们用一个简单的二维点云（原理和三维一样）来演示。

import numpy as np
import matplotlib.pyplot as plt

def fps_2d_demo(points, n_samples):
    """一个简单的2D FPS演示"""
    selected_indices = []
    remaining_indices = list(range(len(points)))

    # 1. 随机选第一个点
    first_idx = np.random.choice(remaining_indices)
    selected_indices.append(first_idx)
    remaining_indices.remove(first_idx)

    # 2. 初始化最小距离数组
    min_distances = np.full(len(points), np.inf)
    min_distances[first_idx] = 0
    # 更新所有点到第一个点的距离
    min_distances = np.minimum(min_distances, np.linalg.norm(points - points[first_idx], axis=1))

    for _ in range(1, n_samples):
        # 3. 找最小距离最大的那个点
        farthest_idx = remaining_indices[np.argmax(min_distances[remaining_indices])]
        selected_indices.append(farthest_idx)
        remaining_indices.remove(farthest_idx)

        # 4. 更新最小距离
        new_distances = np.linalg.norm(points - points[farthest_idx], axis=1)
        min_distances = np.minimum(min_distances, new_distances)

    return np.array(selected_indices)

# 生成随机点
np.random.seed(42)
points = np.random.rand(100, 2) # 100个2D点

# 运行FPS，选10个点
selected_idx = fps_2d_demo(points, 10)
selected_points = points[selected_idx]

# 画图
plt.figure(figsize=(10, 5))
plt.scatter(points[:, 0], points[:, 1], c='blue', alpha=0.5, label='原始点云 (100个)')
plt.scatter(selected_points[:, 0], selected_points[:, 1], c='red', s=100, marker='*', label='FPS采样点 (10个)')
plt.legend()
plt.title("2D点云上的FPS采样效果")
plt.xlabel("X")
plt.ylabel("Y")
plt.grid(True, alpha=0.3)
plt.show()

运行这段代码，你会看到红色的星号点均匀地散布在蓝色的点云中，而不会扎堆出现在某个区域。这就是FPS的魅力——用很少的点，抓住整体的形状骨架。理解了这个基础版本，我们才能谈优化。因为它的瓶颈很明显：那个for i in range(npoint)的循环是串行的，而且每次都要计算torch.sum((xyz - centroid) ** 2, -1)，当N很大时（比如10万点），这个计算和内存访问压力就上来了。

3. 性能瓶颈分析与优化方向

在动手优化之前，我们得像个老中医一样，先给基础FPS算法“把把脉”，找到它的“病灶”所在。我结合性能分析工具（如PyTorch Profiler）和实际项目经验，总结出以下几个主要的性能瓶颈：

1. 双重循环的复杂度：算法外层循环是采样点数 npoint，内层隐式循环是计算所有 N 个点到新采样点的距离。虽然我们通过维护 distance 矩阵避免了计算到所有已采样点的距离，但复杂度依然是 O(B * npoint * N)。当N和npoint都很大时，比如从10万个点中采样1万个点，计算量就达到百亿级别。
2. 内存访问模式：dist = torch.sum((xyz - centroid) ** 2, -1) 这行代码，每次迭代都要从显存中读取整个 xyz 张量（大小 [B, N, 3]），与一个小的 centroid 张量做广播计算。对于大点云，这会产生巨大的内存带宽压力。GPU虽然算力强，但如果数据搬运跟不上，算力也会被闲置。
3. 串行依赖：这是最要命的一点。FPS算法本质上是串行的！下一个采样点的选择，必须依赖于当前已采样点集更新后的 distance 矩阵。这意味着 for 循环的每次迭代无法并行，GPU强大的并行计算能力在这里被严重限制。你无法像处理矩阵乘法那样，把整个循环丢给成千上万个CUDA核心同时算。
4. 距离计算的冗余：在基础实现中，我们计算的是欧氏距离的平方 (x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2。开方操作 sqrt 被省略了，因为比较距离大小时，平方距离和真实距离的序关系一致，这已经是一个优化。但即便如此，乘加运算量依然可观。

面对这些瓶颈，我们的优化策略也得分层次、有重点地展开：

• 策略一：算法层面微调。比如，我们能不能接受“近似均匀”来换取速度？能不能用更快的距离度量？
• 策略二：计算层面优化。如何利用PyTorch和CUDA的特性，把能并行的部分榨干？如何优化内存访问？
• 策略三：工程化技巧。比如分批处理、混合精度计算等。

下面，我们就进入实战环节，看看具体怎么搞。

4. 实战优化一：拥抱GPU，让计算飞起来

基础版的代码虽然用了PyTorch张量，能在GPU上跑，但那个串行循环依然是性能杀手。我们的首要目标，就是尽可能把计算向量化，丢给GPU并行处理。

4.1 向量化距离计算与更新

基础版代码在这部分已经做得不错了，dist的计算和distance的更新都是向量化操作。这里没有太多优化空间。但我们可以注意一个细节：避免在循环中频繁创建新的张量。虽然PyTorch有高效的内存管理，但在极端性能追求下，我们可以尝试预分配内存。

不过，更重要的优化在于利用PyTorch的广播机制和高效算子。确保你的 xyz 张量在创建时就放在GPU上 (device=‘cuda‘)，避免在循环中发生GPU-CPU之间的数据拷贝。

4.2 批次处理（Batching）的威力

在深度学习任务中，我们通常是以批次（Batch）为单位处理数据的。FPS函数天然支持批次处理（输入维度中有B）。但这里有个技巧：当单个点云非常大时，可以考虑在点云维度（N）上进行分块（Chunk）计算。

为什么？因为计算 dist 时，xyz - centroid 会产生一个 [B, N, 3] 的临时张量。如果N极大（如>10万），这个临时张量会消耗大量显存，甚至导致OOM（内存溢出）。

我们可以将点云分成多个块，逐块计算距离，再合并结果。虽然会增加一些控制开销，但能处理更大的点云。

def fps_with_chunking(xyz, npoint, chunk_size=10000):
    """
    支持分块计算的FPS，用于处理超大点云。
    chunk_size: 每个块包含的点数。
    """
    device = xyz.device
    B, N, C = xyz.shape
    centroids = torch.zeros(B, npoint, dtype=torch.long).to(device)
    distance = torch.ones(B, N).to(device) * 1e10
    farthest = torch.randint(0, N, (B,), dtype=torch.long).to(device)
    batch_indices = torch.arange(B, dtype=torch.long).to(device)

    for i in range(npoint):
        centroids[:, i] = farthest
        centroid = xyz[batch_indices, farthest, :].view(B, 1, 3)

        # 分块计算距离
        dist_chunks = []
        for start in range(0, N, chunk_size):
            end = min(start + chunk_size, N)
            xyz_chunk = xyz[:, start:end, :]
            # 计算这个块的点到centroid的距离
            dist_chunk = torch.sum((xyz_chunk - centroid) ** 2, -1)
            dist_chunks.append(dist_chunk)

        # 将块拼接回完整的dist
        dist = torch.cat(dist_chunks, dim=1) # 形状恢复为 [B, N]

        mask = dist < distance
        distance[mask] = dist[mask]
        farthest = torch.max(distance, -1)[1]

    return centroids

提示：chunk_size需要根据你的GPU显存大小来调整。通常可以先设一个较大的值（如2万），如果爆显存再调小。现代GPU（如RTX 4090, A100）显存较大，很多时候可以直接处理完整点云。

4.3 混合精度计算（AMP）

对于支持Tensor Core的现代GPU（如NVIDIA Volta架构及以后的显卡），使用混合精度训练是提速的“大招”。其原理是，用半精度（FP16）进行存储和计算，用单精度（FP32）进行权重更新和损失计算，在几乎不损失精度的情况下，大幅提升计算速度并减少显存占用。

FPS中的距离计算主要是乘加操作，非常适合使用半精度。我们可以用PyTorch的自动混合精度（AMP）包来轻松实现。

from torch.cuda.amp import autocast

def fps_with_amp(xyz, npoint):
    device = xyz.device
    B, N, C = xyz.shape
    centroids = torch.zeros(B, npoint, dtype=torch.long).to(device)
    distance = torch.ones(B, N).to(device) * 1e10
    farthest = torch.randint(0, N, (B,), dtype=torch.long).to(device)
    batch_indices = torch.arange(B, dtype=torch.long).to(device)

    # 将输入转换为半精度以节省显存和加速计算
    # 注意：索引和布尔张量通常保持为默认类型（int/long, bool）
    xyz_half = xyz.half() # 或者使用 .to(torch.float16)

    for i in range(npoint):
        centroids[:, i] = farthest
        centroid = xyz_half[batch_indices, farthest, :].view(B, 1, 3)

        # 在autocast上下文中进行距离计算
        with autocast():
            dist = torch.sum((xyz_half - centroid) ** 2, -1)
            # autocast会自动将dist转换为FP16计算，但结果可能是FP16或FP32
            # 为了与distance（FP32）比较，可能需要转换
            dist = dist.float() # 确保dist是FP32

        mask = dist < distance
        distance[mask] = dist[mask]
        farthest = torch.max(distance, -1)[1]

    return centroids

注意：使用混合精度时要注意数值范围。FP16能表示的范围远小于FP32，距离平方值如果过大（比如坐标值很大），可能会溢出（变成inf）。如果遇到这种情况，可以考虑对输入点云进行归一化（Normalization），将坐标值缩放到一个合理的区间（如[-1, 1]）。

5. 实战优化二：改进采样策略与近似算法

如果经过上述GPU优化后，速度仍然不满足要求，我们就需要从算法本身动刀了。核心思想是：用一点点采样均匀性的损失，换取巨大的速度提升。在很多实际应用中，这是完全可以接受的。

5.1 随机初始化与批量化采样

基础FPS随机选择一个点开始。但有时，这个随机起点会影响最终采样的均匀性。一个改进是进行多次随机初始化，然后选择“最好”的一次（例如，最终采样点之间距离之和最大的一次）。但这会增加计算量。

更实用的策略是 “批量化FPS”。我们不再一次只选一个最远点，而是一次选一小批（比如k个）。如何选这一批呢？我们可以先按基础FPS选第一个点，然后剔除掉这个点周围一定半径内的所有点（认为它们已被“代表”），再从剩余点中继续选最远的。这样可以减少迭代次数。当然，这需要设定一个剔除半径，这个参数需要根据点云密度来调整。

def batch_fps(xyz, npoint, batch_size=5, radius=None):
    """
    批量化FPS：每次迭代采样batch_size个点。
    radius: 剔除半径。如果提供，则采样一个点后，会剔除该点半径内的所有点。
    """
    device = xyz.device
    B, N, C = xyz.shape
    centroids = torch.zeros(B, npoint, dtype=torch.long).to(device)
    distance = torch.ones(B, N).to(device) * 1e10
    farthest = torch.randint(0, N, (B,), dtype=torch.long).to(device)

    batch_indices = torch.arange(B, dtype=torch.long).to(device)
    selected_count = 0

    while selected_count < npoint:
        current_batch_size = min(batch_size, npoint - selected_count)
        for i in range(current_batch_size):
            idx_to_fill = selected_count + i
            if idx_to_fill == 0 and i == 0:
                # 第一次还是用随机点
                pass
            else:
                # 之后选择距离最大的点
                farthest = torch.max(distance, -1)[1]

            centroids[:, idx_to_fill] = farthest
            centroid = xyz[batch_indices, farthest, :].view(B, 1, 3)
            dist = torch.sum((xyz - centroid) ** 2, -1)

            mask = dist < distance
            distance[mask] = dist[mask]

            # 如果设置了剔除半径，将已采样点附近点的距离设为无穷大（负无穷），使其不会被再次选中
            if radius is not None:
                # 注意：这里radius应该是距离的平方，以匹配dist
                mask_too_close = dist < (radius ** 2)
                distance[mask_too_close] = -1e10 # 设置为一个很大的负数，使其在max中不会被选到

        selected_count += current_batch_size

    return centroids

这个方法通过减少循环迭代次数来提速，但均匀性会有所下降，尤其当batch_size较大时。radius参数需要谨慎调整。

5.2 使用近似最近邻搜索（ANN）

FPS的核心操作是“找距离最远的点”，这本质上是一个最远邻搜索问题。我们可以借助一些近似最近邻搜索库（如 FAISS、PyNNDescent）来加速。

思路是：我们维护一个已采样点集。每次迭代，我们不是计算所有点到所有已采样点的最小距离，而是用ANN库快速查询每个点到已采样点集的最近距离（注意，我们要的是最小距离，但找的是最近邻）。然后，再从这些“最近距离”中找最大值。

FAISS是Meta开源的向量相似性搜索库，对GPU支持极好。我们可以这样尝试：

1. 将已采样点集构建一个FAISS索引（例如FlatL2索引）。
2. 用这个索引搜索所有点的最近邻（1-NN），得到每个点到已采样点集的最小距离。
3. 从这个距离数组中找到最大值，对应的点就是下一个采样点。
4. 将该点加入已采样点集，更新索引。

由于FAISS的搜索是高度优化和并行的，尤其是对于大规模数据，速度会比纯PyTorch实现快很多。但缺点是需要引入额外的依赖，并且数据在PyTorch和FAISS之间转换会有开销。对于采样点集动态增长的情况，频繁重建索引也可能成为瓶颈。不过，对于npoint很大的情况，整体上可能有显著收益。

5.3 空间划分与分治策略

另一个思路是利用点云的空间局部性。我们可以先用一个快速的空间划分结构（如体素网格 Voxel Grid 或 八叉树 Octree）对原始点云进行预处理。

• 体素下采样 + FPS：先对点云进行体素下采样，将每个小体素内的点用一个中心点（或随机点）代表。这能大幅减少点云数量N。然后在体素下采样后的点集上运行FPS。这样做，FPS的速度会快很多，而且由于体素下采样本身也有一定的均匀化效果，最终结果往往不错。
• 分治FPS：将整个点云空间划分成多个区域（如8个象限），在每个区域内独立运行FPS，采样 npoint/k 个点，最后将所有区域采样的点合并。这种方法可以并行处理各个区域，非常适合分布式计算。但需要处理区域边界点可能被重复采样或丢失的问题。

这两种方法都是“预处理+精采样”的思路，在工业界非常常见，是平衡速度与效果的有效手段。

6. 效果对比与参数调优指南

优化了半天，到底哪个方法好？我们来做个简单的对比实验。假设我们有一个包含5万个点的点云（Batch Size=1），需要采样1024个点。我们在同一台机器（例如配备RTX 3090 GPU）上测试不同方法的耗时和效果。

方法	描述	预估耗时 (ms)	均匀性评价	适用场景
基础FPS	原始串行实现	500 - 1000	优秀	点云规模小 (<1万)，对均匀性要求极高
GPU向量化FPS	标准PyTorch GPU实现	50 - 200	优秀	通用场景，点云规模中等 (1万-10万)
GPU向量化 + AMP	启用混合精度计算	30 - 100	优秀 (需注意数值)	通用场景，追求极致速度，GPU支持Tensor Core
批量化FPS (k=10)	每次迭代采样10个点	20 - 60	良好	对均匀性要求稍低，追求速度
体素下采样 + FPS	先体素化到1万点，再FPS	10 - 30	良好	点云非常稠密，允许预处理，实时性要求高
FAISS 近似FPS	使用FAISS进行近邻搜索加速	40 - 150	优秀 (近似)	点云规模巨大 (>10万)，且已集成FAISS

注意：上表耗时仅为示意，实际性能受硬件、点云分布、具体参数影响巨大，请以实际测试为准。

参数调优心得：

1. 第一个点是否随机？ 大多数情况下，随机初始化即可。如果对结果稳定性有要求，可以尝试固定一个点（如点云的重心或边界点），或者运行多次FPS取平均。
2. 距离度量选择：欧氏距离平方是最常用的。在特定应用中，如果对方向敏感，可以考虑其他距离，如马氏距离，但计算会更复杂。
3. chunk_size怎么设？ 从你的GPU显存大小倒推。假设显存为 M MB，点云数据为FP32（4字节），那么 chunk_size ≈ (M * 0.5) / (B * C * 4)。乘以0.5是预留一半显存给模型和其他数据。例如24G显存，Batch=1，C=3，chunk_size ≈ (24*1024*0.5) / (1*3*4) ≈ 1024。这只是粗略估计，最好通过实验确定。
4. 体素下采样的粒度：这是“体素+FPS”方法的关键。体素太小，下采样后点数依然很多，加速不明显；体素太大，会丢失太多细节，影响后续FPS采样的代表性。通常根据点云的物理尺寸和密度来定。例如，对于室内场景，体素边长设为0.05m可能比较合适。
5. 批量化FPS的batch_size和radius：batch_size越大，速度越快，但均匀性越差。radius需要根据点云的平均间距来设定，通常可以设为平均点距的2-3倍。可以先计算点云的最近邻距离分布来估计。

7. 避坑指南：实际项目中容易遇到的问题

优化之路从来不是一帆风顺的。我总结了一些在项目中使用FPS时容易踩的坑，希望能帮你省点时间。

坑1：数值溢出与精度问题 当点云坐标值很大时（比如激光雷达点云，坐标范围可能是几十上百米），计算距离平方时很容易溢出，特别是使用FP16时。务必在FPS之前，对点云进行归一化。一个简单的做法是计算点云的包围盒，将点云平移并缩放至[-1, 1]或[0, 1]的区间内。采样完成后，如果需要，可以将采样点的索引映射回原始坐标。

坑2：采样点数npoint大于输入点数N 这是低级错误，但偶尔会发生。一定要在函数开头加个断言：assert npoint <= N, “Cannot sample more points than input.“。或者更友好地处理：如果npoint > N，直接返回所有点的索引（可能还需要补零或重复，具体看需求）。

坑3：Batch处理中的“独特点云” 我们的代码假设一个Batch内的所有点云共享相同的采样逻辑。但如果你的Batch里每个点云的有效点数不同（比如用零填充的），那么随机初始化的点可能会选到填充的零点上。这时，你需要一个mask来标识有效点，只在有效点范围内进行采样和距离计算。这会让代码复杂一些，但更鲁棒。

坑4：梯度中断 在PyTorch中，如果你只需要采样点的索引，然后用这些索引去索引原始点云（sampled_xyz = xyz[:, centroids, :]），这个操作是支持梯度回传的（只要xyz需要梯度）。但是，如果你的FPS实现中有任何不可微的操作（比如torch.max取索引在旧版本中不可微），或者你后续只使用索引值，那么梯度流可能会中断。在需要端到端训练的网络中（如PointNet++），要确保FPS步骤被正确地包含在计算图中。

坑5：确定性（Deterministic）问题 为了结果可复现，你可能需要固定随机种子。但注意，PyTorch的torch.randint在GPU上的行为在不同运行中可能不一致，即使设置了随机种子。如果需要确定性的FPS，可以考虑在CPU上生成随机索引，或者使用更确定性的方法选择第一个点（如始终选择第0个点）。

最后，我想说的是，没有“最好”的优化策略，只有“最适合”的。如果你的应用对均匀性要求是100分，那么老老实实用基础的GPU向量化FPS，并忍受它的速度。如果你要处理每秒几十帧的激光雷达流，那么“体素下采样+FPS”或者一个高度优化的近似算法可能是唯一的选择。多实验，多分析，根据你的数据和需求来做权衡。希望这些经验能帮你在3D点云处理的路上走得更顺一些。