很久以前，我制作了一个游戏，其中需要一种连接组件标记来实现 AI 部分。我当时在不知不觉中使用了 two-pass 算法。

最近，我知道我可以使用基于位扫描的方法来提高它们的速度。它使用每像素 1 位数据作为输入，而不是典型的每像素字节输入。然后它使用 BSF 指令找到每个扫描线中的每个线性块。请看下面的代码。 Cut 是一个结构体，用于保存扫描线中位 1 的线性块的信息。

Cut* get_cuts_in_row(const u32* bits,const u32* bit_final,Cut* cuts) {
    u32 working_bits = *bits;
    u32 basepos = 0,bitpos = 0;
    for (;; cuts++) {
        //find starting position
        while (!_BitScanForward(&bitpos,working_bits)) {
            bits++,basepos += 32;
            if (bits == bit_final) {
                cuts->start_pos = (short)0xFFFF;
                cuts->end_pos = (short)0xFFFF;
                return cuts + 1;
            }
            working_bits = *bits;
        }
        cuts->start_pos = short(basepos + bitpos);

        //find ending position
        working_bits = (~working_bits) & (0xFFFFFFFF << bitpos);
        while (!_BitScanForward(&bitpos,basepos += 32;
            working_bits = ~(*bits);
        }
        working_bits = (~working_bits) & (0xFFFFFFFF << bitpos);
        cuts->end_pos = short(basepos + bitpos);
    }
}

首先，它使用汇编BSF指令找到第1位出现的第一个位置。找到后，通过位反转和位掩码，找到该位置之后出现的第一个位置位0，然后重复此过程。

在每个扫描线中获得所有线性块的起始位置和结束位置（我更喜欢将它们称为“剪切”）后，它以 CCL 方式为它们提供标签。对于第一行，每次切割都有不同的标签。

对于其余行中的每个切口，它检查是否有首先连接到它的上切口。如果没有上切口连接到它，它将获得新标签。如果只有一个上切口连接到它，它会得到标签的副本。如果许多上切口连接到它，这些标签将被合并，并获得合并的标签。这可以使用上部块和下部块的两个进度指针轻松完成。这是完成该部分的完整代码。

Label* get_labels_8c(Cut* cuts,Cut* cuts_end,Label* label_next) {
    Cut* cuts_up = cuts;
    
    //generate labels for the first row
    for (; cuts->start_pos != 0xFFFF; cuts++) cuts->label = [GET NEW LABEL FROM THE POOL];
    cuts++;

    //generate labels for the rests
    for (; cuts != cuts_end; cuts++) {
        Cut* cuts_save = cuts;
        for (;; cuts++) {
            u32 start_pos = cuts->start_pos;
            if (start_pos == 0xFFFF) break;

            //Skip upper slices ends before this slice starts 
            for (; cuts_up->end_pos < start_pos; cuts_up++);

            //No upper slice meets this
            u32 end_pos = cuts->end_pos;
            if (cuts_up->start_pos > end_pos) {
                cuts->label = [GET NEW LABEL FROM THE POOL];
                continue;
            };

            Label* label = label_equiv_recursion(cuts_up->label);

            //Next upper slice can not meet this
            if (end_pos <= cuts_up->end_pos) {
                cuts->label = label;
                continue;
            }

            //Find next upper slices meet this
            for (; cuts_up->start_pos <= end_pos; cuts_up++) {
                Label* label_other = label_equiv_recursion(cuts_up->label);
                if (label != label_other) [MERGE TWO LABELS]
                if (end_pos <= cuts_up->end_pos) break;
            }
            cuts->label = label;
        }
        cuts_up = cuts_save;
    }
    return label_next;
}

在此之后，您可以将这些信息用于每条扫描线，以直接制作标签数组或任何他想要的输出。

我检查了这个方法的执行时间，然后我发现它比我之前使用的二次扫描方法要快得多。令人惊讶的是，即使输入数据是随机的，它也比两次扫描快得多。显然，位扫描算法最适合结构相对简单的数据，其中扫描线中的每个块都很大。它并非设计用于随机图像。

令我困惑的是，实际上没有人提及这种方法。坦率地说，这似乎并不是一个很难想出的想法。很难相信我是第一个尝试它的人。

也许虽然我的方法比原始的双扫描方法好，但比基于双扫描思想的更发达的方法要差，所以无论如何都不值得一提。

但是，如果可以改进二次扫描方法，那么位扫描方法也可以。我自己发现 8 连接有一个很好的改进。它在我使用位 OR 指令合并它们时分析相邻的两条扫描线。您可以在here找到完整的代码和详细说明。

我知道有一个名为 YACCLAB 的 CCL 算法基准。我将用最好的 CCL 算法测试我的算法，看看它们有多好。在此之前，我想在这里问几件事。

我的问题是，

1. 我发现的这些算法真的是新的吗？仍然很难相信没有人想过使用位扫描的 CCL 算法。如果它已经是一件事，为什么我找不到任何人说它？基于位扫描的算法是否被证明是糟糕的并且被遗忘了？

2. 如果我真的找到了一个新算法，接下来我该怎么做？当然，我会在更可靠的系统（如 YaccLAB）中对其进行测试。我在质疑我接下来应该做什么。我应该怎么做才能使这些算法挖掘并传播它们？