這是一個關於矩形排樣問題和 WebAssembly 初體驗的故事，但一切還要從不學無術的小學妹説起……
1. 問題起因
小學妹的課題需要寫一個程序解決矩形排樣（即二維矩形裝箱）問題。
根據給定的一系列矩形，需要將它們打包到指定大小的二維箱子中，且要求任意兩個矩形不能相交或包含。
問：如何排列矩形可使需要的箱子數量最少，且利用率最大？
這是一個極具現實意義的問題，在工業應用中非常重要，排樣結果與經濟利益密切相關。
同時，這也是一個NP-Hard問題——既無法通過一個簡單公式計算，也不可能將所有情況枚舉（超級計算機也算不過來）。
2. 解決思路
小學妹不學無術，而我對算法一竅不通，因此只好借前人經驗遮蔭避涼。歷經重重曲折，終於找到一個 RectangleBinPack 庫。它提供了一篇介紹二維矩形裝箱問題的各種算法的文章，以及各種算法的具體實現。
對算法感興趣的夥伴可以自行獲取 Wasm 倉庫中的《算法介紹》文件瞭解。
Wasm 倉庫傳送器：https://github.com/ununian/RectangleBinPack-Wasm
目前瞭解到，解決二維矩形裝箱問題有 4 種算法，分別是：貨架算法、斷頭台算法、最大矩形算法、天際線算法，每個算法都有一些策略選項。
小課題不用宰牛刀，我將問題簡化，在此只考慮一個箱子的情況。
3.方案選擇
該庫是用 C++ 寫的，但是我對 C++ 並不熟悉，所以需要用我所熟悉的語言使用。在其他語言中使用 C++ 有兩種方案：
第一，直接改寫成對應語言，適用於簡單的庫。雖然這個庫很適合直接改寫，但卻無法（在學妹面前）展現我的高超水平❌
第二，將 C++ 庫編譯成靜態庫，再通過跨語言調用機制直接調用。這一看就是會吸引崇拜目光的高端玩法，I WANT YOU!✅
那麼，要在哪個語言中使用這個庫呢？
第一個想到的是 C#，畢竟在 C# 中調用 C++ 是很常見的操作，也有成熟的 Binding 工具（如 Swig）；而且之前也做過這樣的嘗試，整體準備工作量也會少一點。但使用 C# 有兩個問題:
- 使用過程麻煩。畢竟是桌面程序，涉及分發、安裝、兼容性等。
- 編譯結果不跨平台。雖然 C++ 和 C# 本身都能跨平台，但需要針對每個平台都編譯一次，而且 C# 的 GUI 部分跨平台寫起來有點麻煩……
緊接着，我想到了 WebAssembly——一個可以完美解決上述問題的方案，既不用擔心跨平台，又能直接使用前端技術完成 GUI 部分。方便又高端，還能在小學妹面前裝
（消音）
，簡直非它莫屬。
4. 具體實現
4.1 環境需求
最好使用 Linux 環境，可以避免許多奇怪的問題；如果是 Windows，可以試試 WSL。
安裝 Emscripten。具體請參考 Download and install - Emscripten 2.0.27 (dev) documentation
還需要 Node 以及網頁開發相關的工具。
4.2 項目結構
.
├── XXXX.cpp // 算法本身的 cpp 文件
├── XXXX.h // 算法本身的頭文件
├── Warp.cc // Warp文件，其中描述了需要導出的類和函數、枚舉等
├── compile.sh // 編譯腳本
├── package.json // package.json 文件，方便發佈到 npm 倉庫 4.3 Warp 文件的編寫
在 Warp 文件中顯式地告訴 Emscripten 需要導出哪些類和函數（這個步驟稱為 Binding），讓 Emscripten 生成相應的 wasm 代碼和 warp 代碼，以便在 Web 環境中使用。
本項目的 Warp 文件是：
#include "Rect.cpp"
// ... include<xxx.cpp> 引用各個算法的 cpp 文件
#include "emscripten/bind.h" // Emscripten Binding 需要的頭文件
using namespace emscripten; // Emscripten Binding 的命名空間
using namespace std; // C++ 標準庫命名空間 ，主要是為了使用 vector（可以理解為 C++ 中的可變長度數組）
using namespace rbp; // 這個算法庫的命名空間 RectangleBinPack
EMSCRIPTEN_BINDINGS(c) // 表示我們開始編寫 Emscripten 的 Binding
{
// 下面只要是字符串裏面的值都是在 wasm 裏面的名字，可以自己取，不要求和 C++ 中的一樣。
// 導出 Rect 和 RectSize 的 vector
register_vector<Rect>("VectorRect");
register_vector<RectSize>("VectorRectSize");
// Rect.cpp
class_<RectSize>("RectSize") // 導出 RectSize 類，他包括
.constructor<>() // 一個沒有參數的構造函數
.constructor<int, int>() // 一個有 2 個參數的構造函數，參數的類型分別是 int 和 int
.property("width", &RectSize::width) // 一個實例字段 width，對應的地址是 RectSize 的 width
.property("height", &RectSize::height);
// ...
emscripten::function("IsContainedIn", &IsContainedIn); // 導出了一個全局的函數
// SkylineBinPack.cpp
// 導出一個叫做 SkylineBinPack_LevelChoiceHeuristic 的枚舉，
// 他有 2 個值 LevelBottomLeft、LevelMinWasteFit
enum_<SkylineBinPack::LevelChoiceHeuristic>("SkylineBinPack_LevelChoiceHeuristic")
.value("LevelBottomLeft", SkylineBinPack::LevelChoiceHeuristic::LevelBottomLeft)
.value("LevelMinWasteFit", SkylineBinPack::LevelChoiceHeuristic::LevelMinWasteFit);
class_<SkylineBinPack>("SkylineBinPack")
.constructor<>()
.constructor<int, int, bool>()
.function("Init", &SkylineBinPack::Init) // 一個實例函數 Init
// 一個實例函數 Insert_Range，對應的是 Insert 函數的某個重載
.function("Insert_Range",select_overload<void(vector<RectSize> &, vector<Rect> &, SkylineBinPack::LevelChoiceHeuristic)>(&SkylineBinPack::Insert))
.function("Insert_Single",select_overload<Rect(int, int, SkylineBinPack::LevelChoiceHeuristic)>(&SkylineBinPack::Insert))
.function("Occupancy", &SkylineBinPack::Occupancy);
}Warp 文件的文件名和文件中字符串的具體值都是在 wasm 裏的名字，可以自定義，不要求與 C++ 中的一樣。
需要注意，這裏直接引入的是 cpp 文件，不是頭文件。下面説幾個重要部分的處理。
4.3.1 Vector 的處理
vector 是 C++ 標準庫提供的一個數據結構，是可以動態改變長度的數組。本項目主要用來傳遞待排版的 RectSize 數組和接收計算結果的 Rect 數組。
Emscripten 貼心地提供了 vector 自動綁定方法 register_vector，只需傳入 vector 的元素類型和導出名字即可。
4.3.2 枚舉的處理
JS 中沒有枚舉概念，所以在 JS 使用時需要用 Object 的形式。綁定也很簡單，使用 enum_ 指定名稱、類型和對應的值就行。
4.3.3 函數重載的處理
JS 中沒有函數重載的概念，因此導出重載函數需要指定不同的名稱，並使用 select_overload 函數找到對應的函數（指定函數的返回值、參數類型即可，沒有返回值就是 void）。
順帶一提，如果有多個構造函數也需要指定構造函數的參數類型（構造函數不能指定名稱和返回值）。
4.4 編譯 Wasm
接下來，將寫好的 Warp 文件編譯成 Wasm，編譯腳本如下：
emcc --bind -Oz Warp.cc -o dist/Warp.js \
-s WASM=1 \
-s MODULARIZE=1--bind表示需要使用 Embind 的綁定功能。-Oz表示優化等級，有O0、O1、O2 等，其中 Oz 表示優化等級最高。此處我們無需調試 Wasm，選Oz就行。-o用於指定輸出文件。如果指定的文件後綴名是js，就會生成wasm和相應的js warp 文件（包含一些膠水代碼，便於我們使用 wasm）。當然我們也可以指定html生成一個 demo 網頁；或指定wasm只生成 wasm 文件。-s WASM=1表示編譯到 wasm 。如果值為 0 會編譯到asm.js，值為 2 就同時編譯成兩者。-s MODULARIZE=1表示生成的 js 文件會導出一個可以傳參工廠函數（後續會看到），否則會直接賦值在 window 對象上。
值得一提的是，-s SINGLE_FILE=1 可以用 base64 的方式將 wasm 嵌入到 warpjs 文件中，使用時只需要引用 js 文件就行。
4.5 生成對應的 TypeScript 描述文件
工具地址：https://github.com/ted537/tsembind
生成 TypeScript 的描述文件在工程使用中非常重要，否則別人根本不知道怎麼用（還能減少寫文檔的工作量），但是目前還沒有十全十美的解決方案。
我選用的工具通過讀取 wasm 文件分析裏面的導出，因此無法獲取函數的形參名字；另外，生成的描述文件還需要小小的「後期加工」：
直接運行 tsembind ./dist/Warp.js > ./dist/Warp.d.ts ，修改最下面導出的部分，別忘了添加 @types/emscripten。
export interface CustomEmbindModule {
// ...
}
declare function factory(): Promise<CustomEmbindModule>;
export default factory;
// =========>
export interface RectangleBinPackModule extends EmscriptenModule {
// ...
}
declare const factory: EmscriptenModuleFactory<RectangleBinPackModule>;
export default factory;4.6 使用 Wasm
效果如下：
詳細的使用方法請參考 Demo 倉庫的代碼，下面補充一些注意事項。
import type { RectangleBinPackModule as PackModule } from 'rectanglebinpack-wasm'
// PackWasmInit 就是上面那個工廠函數
import PackWasmInit from 'rectanglebinpack-wasm';
// 我們需要獲取 wasm 文件的路徑。我們不需要用打包器的 wasm loader，
// 只需要這個wasm文件的 url 就行。這裏是 vite 的寫法，webpack 應該是 file-loader
import PackWasm from 'rectanglebinpack-wasm/dist/Warp.wasm?url'
// 方便獲取枚舉的值，主要是用來規避 ts 的類型檢查
const toEnumValue = (enumObj: any, value: any) => enumObj[value]
export class WasmPackService implements IPackService {
private wasm?: PackModule;
constructor() {
PackWasmInit({
// 這裏非常重要，我們需要告訴工廠方法 wasm 文件的位置在哪，
// 如果不寫，它會去網頁的根目錄下查找，一般情況下我們不希望這樣
locateFile: (url) => url.endsWith('.wasm') ? PackWasm : url
}).then(wasm => {
this.wasm = wasm; // 初始化完成後，就能獲取到 wasm 模塊的實例了
})
}
public async pack(
source: SourcePanelItem[], // width height 這裏因為只考慮 1 個箱子的情況，所以這裏肯定只有 1 個數據
target: TargetPanelItem[], // width height count
algorithms: Algorithms, // 算法
setting: Record<string, boolean | string> // 算法設置
) {
// ...
const m = this.wasm;
// 首先我們創建一個 RectSize 的 vector，然後把我們需要排版的小矩形都放進去
const targetSizes = new m.VectorRectSize();
target
.flatMap(t => range(0, Math.max(t.count, 0))
.map(_ => new m.RectSize(t.width, t.height)))
.forEach((i) => targetSizes.push_back(i));
// ...
let resultRects = new m.VectorRect(); // 創建一個用來接收結果的 Rect 的 vector
switch (algorithms) {
// ...
case "Skyline":
// 調用天際線算法類的構造函數，並傳遞一些設置，創建一個算法對象
const skyline = new m.SkylineBinPack(sourceWidth, sourceHeight, setting['UseWasteMap'] as boolean);
// 調用批量添加函數，函數內部會把結果添加到 resultRects 裏面
skyline.Insert_Range(
targetSizes,
resultRects,
toEnumValue(m.SkylineBinPack_LevelChoiceHeuristic, setting['LevelChoiceHeuristic'])
);
// 重要：手動釋放 skyline 對象。因為 wasm 需要我們手動管理內存，
// 所以創建了對象後一定要回收，不存在自動垃圾回收。
skyline.delete();
break;
}
const result: Rect[] = []
for (let i = 0; i < resultRects.size(); i++) {
const item = resultRects.get(i);
result.push({ x: item.x, y: item.y, width: item.width, height: item.height })
}
// 獲取結果後釋放掉 targetSizes、resultRects
targetSizes.delete();
resultRects.delete();
return { result }
}
}4.6.1 內存管理
Wasm 與 JS 相比最大的區別是對象內存需要手動創建（new 函數）和釋放（delete 函數），所以要注意 new 和 delete 的成對使用。
如果 vector 內存的不是指針，則會自動調用析構函數。
4.6.2 指定 wasm 文件的 Url
如果不指定 wasm 文件的 Url，那麼 warp 文件會從網站根目錄 /xx.wasm 加載。通常我們不希望這樣，因此需要在 wasm 加載時通過 locateFile 函數指定 Wasm 文件的 Url。
建議不要通過 webpack 或者 vite 的 loader 加載 wasm，那樣會自動轉換成 wasm 模塊。只獲取 wasm 文件的 url，可以在 vite 中的實在資源名後加上 ?url 或者在 webpack 中加上 !file-loader。
5.總結
本項目涉及的內容和知識還是蠻多的，包括 C++、編譯器、WebAssembly 、loader等。完成過程也踩了不少坑，主要是缺乏可用度高的相關資料——有些要麼特別簡單，只是導出一個全局函數，要麼就很複雜，如 ffmpeg 的 wasm 版本。
之前一直想學習 WebAssembly，這次也算是藉着難得的機會，簡單地瞭解了從編譯到使用的全過程。最後的完成效果也很不錯，具有一定的實際運用價值，當然小學妹也很滿意:)
後續可以改進的空間主要有兩點:
- 手動寫 warp 文件比較麻煩，而且大都是重複的體力勞動。如果能寫一個工具，通過分析 C++ 代碼，自動生成 warp 文件和 Typescript 定義，或許可以節省很多工作量；具體實現可以參考 Swig 的做法。
- 之前見過通過
Scope實現半自動內存管理，或許也可以加進內存管理中使用。
6.彩蛋 ：C# 的做法
6.1 編寫描述文件 Warp.idl
%module RectangleBinPack
%{
#include "Rect.h"
#include "GuillotineBinPack.h"
#include "SkylineBinPack.h"
#include "ShelfNextFitBinPack.h"
#include "ShelfBinPack.h"
#include "MaxRectsBinPack.h"
%}
%include <std_vector.i>
%template(vector_Rect) std::vector<rbp::Rect>;
%template(vector_RectSize) std::vector<rbp::RectSize>;
%include "Rect.h"
%include "GuillotineBinPack.h"
%include "SkylineBinPack.h"
%include "ShelfNextFitBinPack.h"
%include "ShelfBinPack.h"
%include "MaxRectsBinPack.h"確實比 Emscripten 方便很多，畢竟更加成熟。再調用
swig -c++ -csharp Warp.idl這一步會生成很多 cs 文件（C# 的源文件）和一個 warp.cxx 文件。
6.2 編譯 Dll
幸運的是，RectangleBinPack 自帶了 VisualStudio 的工程文件 RectangleBinPack.sln 。打開後將生成的 warp.cxx 文件加入工程，build 一個 x64 的版本即可。
6.3 使用
創建一個 C# GUI 項目，將步驟 6.1 生成的 cs 文件和步驟 6.2 生成的 Dll 複製到目錄下（Dll 需要選擇較新則複製）。
下面是部分重要代碼：
public (double, List<Rect>) PackImplement(PackRequestDto dto)
{
// ...
var targets = new vector_RectSize(dto.Target.SelectMany(target =>
Enumerable.Range(1, target.Count).Select(_ =>
new RectSize {width = target.Width, height = target.Height})));
var resultRects = new vector_Rect();
// ...
switch (dto.Algorithms)
{
case PackAlgorithms.Skyline:
var skylineBin = new SkylineBinPack(sourceWidth, sourceHeight,
dto.SkylineSetting.UseWasteMap);
skylineBin.Insert(targets, resultRects, dto.SkylineSetting.LevelChoiceHeuristic);
break;
// ...
}
return (occupancy, resultRects.ToList());
}可以看出，C# 和 JS 在調用階段都差不多，只是 swig 更為貼心地處理了內存管理部分。
7. 附錄
本文所提到代碼資源：
1. C++庫：https://github.com/juj/RectangleBinPack
2. Wasm：https://github.com/ununian/RectangleBinPack-Wasm
3. Demo：https://github.com/ununian/RectangleBinPack-Wasm-Demo
LigaAI 重視開發者文化的維護與構建，也將繼續分享更多技術分享和趣味技術實踐。關注 LigaAI@SegmentFault ，一起做大變強！
也歡迎點擊 LigaAI-新一代智能研發協作平台，在線申請體驗我們的產品，與我們交流 :)
