碰撞偵測在物理動力模擬是不可缺少的功能，兩個複雜多邊形物體在執行碰撞偵測時需要做很多幾何運算，因此若要遊戲的畫面能夠流暢顯示，遊戲中的碰撞偵測就必須要能達到 real-time 的等級，目前能夠快速執行碰撞偵測的演算法[1][2]幾乎都是基於 Convex Collider 去計算(Unity 3D 使用的物理引擎 PhysX 也包括在內)。
現實世界裡大部份物體都不屬於 Convex 多邊形物體 (Nonconvex Polyhedra)，這些 Nonconvex 多邊形物體也稱為 Concave 多邊形物體，為了解決無法對 Concave Collider 進行碰撞偵測的問題，可以把 Concave 多邊形分解成多個 Convex 多邊形。V-HACD[3]就是一個分解 Concave 多邊形的演算法，它所產生的 Convex 多邊形並非完全等於原始多邊形，它的目標是以少量的 Convex 多邊形去近似原始的多邊形，能在不失真以及產生的 Convex 多邊形數目上取得平衡。
需要 7611 個 Convex 多邊形來組合成原始多邊形 (來源[3])
Unreal Engine 4 也使用 V-HACD 來分解 Concave 多邊形。(來源[4])
底下的步驟敘述如何編譯 V-HACD 並在 Unity 中使用 (macOS/Windows) :
1. V-HACD plugin for Unity macOS
1.1 xcode 編譯 vhacd
到
這裡取得 V-HACD 程式原始碼並確認已有安裝 python 及 cmake 之後，在 install 資料夾裡執行指令 (它會在 build/mac 底下建立 xcode 專案)
./run.py --cmake
執行成功之後在 build/mac 資料夾開啟專案檔案 VHACD.xcodeproj，然後編譯出 Library (Scheme 選擇 ALL_BUILD>My Mac)，編譯完成後會看到靜態連結檔 build/mac/VHACD_Lib/Release/libvhacd.a。
1.2 建立 Bundle 專案
在 xcode 另外建立新的 Bundle 專案。
選擇 macOS > Bundle
Linked Frameworks and Libraries 新增剛產生的 libvhacd.a
General > Linked Frameworks and Libraries 新增 libvhacd.a
ps. 後最編譯時若出現下列錯誤訊息則 Linked Frameworks and Libraries 再新增 OpenCL.framework
Undefined symbols for architecture x86_64:
"_clBuildProgram", referenced from:
VHACD::VHACD::OCLInit(void*, VHACD::IVHACD::IUserLogger*) in libvhacd.a(VHACD.o)
...
OpenCL.framework and libvhacd.a
Search Paths 的 Header Search Paths 新增指向 vhacd 原始碼路徑 src/VHACD_Lib/public，Library Search Paths 新增指向 vhacd 產生靜態連結Lib的路徑 build/mac/VHACD_Lib/Release。
指向 Header Search Path 及 Library Search Path 的相對路徑
新增 Header File stdafx.h :
#ifndef stdafx_h
#define stdafx_h
#ifdef _WIN32
#include "targetver.h"
#define WIN32_LEAN_AND_MEAN // Exclude rarely-used stuff from Windows headers
// Windows Header Files:
#include <windows.h>
#define MODULE_API __declspec(dllexport)
#define STD_CALL __stdcall
#else
#define MODULE_API
#define STD_CALL
#endif
// TODO: reference additional headers your program requires here
#include "VHACD_api.h"
#include "VHACD.h"
#include "ConvexDecompTool.h"
#include <string.h>
#include <stdio.h>
#endif /* stdafx_h */
新增 Header File targetver.h :
#ifndef targetver_h
#define targetver_h
#include <SDKDDKVer.h>
#endif /* targetver_h */
新增 Header File ConvexDecompTool.h :
#ifndef ConvexDecompTool_h
#define ConvexDecompTool_h
#include "stdafx.h"
using namespace VHACD;
class FVHACDProgressCallback : public IVHACD::IUserCallback
{
private:
CBFunc tmp_cb_func;
public:
FVHACDProgressCallback(CBFunc pCBFunc);
~FVHACDProgressCallback() {};
void Update(const double overallProgress, const double stageProgress, const double operationProgress, const char * const stage, const char * const operation);
};
#endif /* ConvexDecompTool_h */
新增 Cpp File ConvexDecompTool.cpp :
#include "stdafx.h"
FVHACDProgressCallback::FVHACDProgressCallback(CBFunc pCBFunc){
tmp_cb_func =pCBFunc;
}
void FVHACDProgressCallback::Update(const double overallProgress, const double stageProgress, const double operationProgress, const char * const stage, const char * const operation)
{
//process callback info.
if (tmp_cb_func !=nullptr){
char buff[255];
memset(buff, sizeof(char)*255, 0);
int strlen =sprintf(buff, "%s", stage);
tmp_cb_func(overallProgress, stageProgress, operationProgress, strlen, buff);
}
};
ConvexDecompTool 的作用是接收 v-hacd 處理時的進度及狀態資料，我們會將它傳回給 Unity 並且在 v-hacd 處理時顯示出來。
新增 Header File VHACD_api.h :
#ifndef VHACD_api_h
#define VHACD_api_h
#include "stdafx.h"
extern "C" {
typedef void (STD_CALL *CBFunc)(double overallProgress, double stageProgress, double operationProgress, int str_sz, char* str_buff);
}
#endif /* VHACD_api_h */
此處的 CBFunc 對應到 Unity C# 的 delegate，可以利用此 Callback Function 將處理進度及資訊傳給 Unity。
新增 Cpp File VHACD_api.cpp :
#include "stdafx.h"
using namespace VHACD;
static void InitParameters(IVHACD::Parameters &VHACD_Params, unsigned int InHullCount, unsigned int InMaxHullVerts, unsigned int InResolution)
{
VHACD_Params.m_resolution = InResolution;
VHACD_Params.m_maxNumVerticesPerCH = InMaxHullVerts;
VHACD_Params.m_concavity = 0;
VHACD_Params.m_maxConvexHulls = InHullCount;
VHACD_Params.m_oclAcceleration = false;
VHACD_Params.m_minVolumePerCH = 0.003f;
VHACD_Params.m_projectHullVertices = true;
};
struct DecomposedHullData{
int pts;
int tris;
double* pts_arr;
int* tris_arr;
};
DecomposedHullData* dhd =nullptr;
int num_dhd_sz =0;
extern "C" {
MODULE_API void DisposeHullData(){
if (dhd !=nullptr){
for (int i=0;i<num_dhd_sz;++i){
delete[] dhd[i].pts_arr;
delete[] dhd[i].tris_arr;
}
}
delete[] dhd;
dhd =nullptr;
num_dhd_sz =0;
}
MODULE_API int GetHullSize(){
return num_dhd_sz;
}
MODULE_API bool GetTrianglesData(int idx, int* tri_num, int** tri_data){
if (idx< num_dhd_sz && dhd !=nullptr){
*tri_num =dhd[idx].tris;
*tri_data =dhd[idx].tris_arr;
return true;
}
return false;
}
MODULE_API bool GetVerticesData(int idx, int* vertices_num, double** vertices_data){
if (idx< num_dhd_sz && dhd !=nullptr){
*vertices_num =dhd[idx].pts;
*vertices_data =dhd[idx].pts_arr;
return true;
}
return false;
}
//hull_count range (2~64)
//max_tri_count range (6~32)
//resolution range (10000 ~ 1000000)
MODULE_API bool DecomposeMeshToHulls(
unsigned int hull_count,
unsigned int max_tri_count,
unsigned int res,
const float* const Verts,
const unsigned int NumVerts,
const unsigned int* const Tris,
const unsigned int NumTris,
CBFunc pcb){
IVHACD* InterfaceVHACD =CreateVHACD();
IVHACD::Parameters VHACD_Params;
InitParameters(VHACD_Params, hull_count, max_tri_count, res);
FVHACDProgressCallback* VHACD_Callback =new FVHACDProgressCallback(pcb);
VHACD_Params.m_callback =VHACD_Callback;
bool bSuccess =InterfaceVHACD->Compute(Verts, NumVerts, Tris, NumTris, VHACD_Params);
if (bSuccess){
//iterate over each result hull
unsigned int NumHulls =InterfaceVHACD->GetNConvexHulls();
DisposeHullData();
dhd =new DecomposedHullData[NumHulls];
for (int HullIdx=0; HullIdx<NumHulls; HullIdx++){
IVHACD::ConvexHull Hull;
InterfaceVHACD->GetConvexHull(HullIdx, Hull);
dhd[HullIdx].pts =(int)Hull.m_nPoints;
dhd[HullIdx].tris =(int)Hull.m_nTriangles;
dhd[HullIdx].pts_arr =new double[3*Hull.m_nPoints];
dhd[HullIdx].tris_arr =new int[3*Hull.m_nTriangles];
memcpy(dhd[HullIdx].pts_arr, Hull.m_points, sizeof(double)*3*Hull.m_nPoints);
memcpy(dhd[HullIdx].tris_arr, Hull.m_triangles, sizeof(unsigned int)*3*Hull.m_nTriangles);
}
num_dhd_sz =NumHulls;
}else{
DisposeHullData();
}
InterfaceVHACD->Clean();
InterfaceVHACD->Release();
delete VHACD_Callback;
VHACD_Callback =nullptr;
return bSuccess;
}
}
其中 GetHullSize, GetTrianglesData, GetVerticesData 的作用是取得處理完成的資料，DecomposeMeshToHulls 的作用是初始化並呼叫執行 V-HACD。
將上述檔案加入至專案然後執行編譯即可取得 Unity 可呼叫之 bundle 檔案。
2. V-HACD plugin for Unity Windows
2.1 VisualStudio 編譯 vhacd
到
這裡取得 V-HACD 程式原始碼並確認已有安裝 python 及 cmake 之後，修改在 install 資料夾裡的 run.py 檔案，將第 11 行改成 :
cmd = "cmake -A x64 " + arg + " ../" + src_dir
-A x64 讓 cmake 產生 x64 平台的專案。
cmake 在安裝時選擇 Add CMake to the system PATH for all users 或者 Add CMake to the system PATH for the current user 之後在執行 run.py 時比較不會有問題。
執行 run.py (它會在 build/win32 底下建立 VisualStudio Solution)
py run.py --cmake
執行成功之後在 build/win32 資料夾開啟專案檔案 VHACD.sln，然後編譯出 Library (記得把 vhacd 和 testVHACD 的 C/C++ -> Code Generation -> Runtime Library 設定成 Multi-threaded)，編譯完成後會看到靜態連結檔 build/win32/VHACD_Lib/Release/vhacd.lib。
Runtime Library 選擇 Multi-threaded 以避免之後 Unity 載入 DLL 時發生無法載入問題。
2.2 建立 DLL 專案 (Visual C++ -> Windows Desktop -> Dynamic-Link Library (DLL) )
將專案目前的 solution platform 改成 x64。在 C/C++ -> General -> Additional Include Directories 新增路徑指向 V-HACD 資料夾 src\VHACD_Lib\public。
新增路徑指向 V-HACD public header 資料夾 (圖中的路徑要換成你電腦中的路徑)
C/C++ -> Code Generation -> Runtime Library 改成 Multi-threaded。
Linker -> General -> Additional Library Directories 新增路徑指向 V-HACD 資料夾 build\win32\VHACD_Lib\Release。
新增路徑指向 V-HACD lib 檔案資料夾 (圖中的路徑要換成你電腦中的路徑)
Linker -> Input -> Additional Dependencies 新增 lib 名稱 vhacd.lib (此檔名是 2.1 編譯產生的檔案)
新增 vhacd.lib 檔名
將 1.2 列出的檔案 stdafx.h，targetver.h，VHACD_api.h，ConvexDecompTool.h，ConvexDecompTool.cpp，WHACD_api.cpp，加入至專案中，並將檔案 ConvexDecompTool.cpp 的 sprintf 改成 sprintf_s
。最後執行編譯即可獲得 Unity 可呼叫使用的 DLL 檔案
。
3. Unity C#
3.1 設定 bundle/dll 檔案
把 VHACD_Bundle.bundle 或 VHACD_DLL.dll 複製到 Unity Assets 資料夾 (bundle 及 dll 檔案是 1.2 及 2.2 編譯產生的檔案，可能因為專案命名不同而產生不同檔名)，並且統一命名 VHACD_Lib，其 platform 設定參考如圖
。
VHACD_Lib.bundle platform 設定
VHACD_Lib.dll platform 設定
3.2 VHACD_Lib.cs 檔案
底下是 VHACD_Lib 在 Unity 裡簡單的使用範例 :
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEditor;
using System.Runtime.InteropServices;
public class VHACD_Lib : MonoBehaviour {
[DllImport("VHACD_Lib")]
private static extern void DisposeHullData();
[DllImport("VHACD_Lib")]
private static extern bool DecomposeMeshToHulls(
uint hull_count,
uint max_tri_count,
uint resolustion,
float[] verts,
uint num_verts,
int[] tris,
uint num_tris,
VHACD_CBFunc_Handler pHandler
);
[DllImport("VHACD_Lib")]
private static extern int GetHullSize();
[DllImport("VHACD_Lib")]
private static extern bool GetTrianglesData(int idx, ref int tri_num, ref System.IntPtr tri_data);
[DllImport("VHACD_Lib")]
private static extern bool GetVerticesData(int idx, ref int vert_num, ref System.IntPtr vert_data);
delegate void VHACD_CBFunc_Handler(double overallProgress, double stageProgress, double operationProgress, int str_sz, System.IntPtr str_buff);
public static void VHACD_CB_Handler(double overallProgress, double stageProgress, double operationProgress, int str_sz, System.IntPtr str_buff){
string data =Marshal.PtrToStringAnsi(str_buff);
EditorUtility.DisplayProgressBar("V-HACD", data+" ("+(int)stageProgress+"%)", (float)overallProgress/100f);
}
MeshCollider[] _convex_mesh_colliders =null;
Mesh[] _convex_mesh =null;
public uint hulls =8;
public uint tris_per_hull =16;
public uint resolution =100000;
float GetMax(Vector3 v){
return Mathf.Max(Mathf.Max(v.x, v.y), v.z);
}
float GetMin(Vector3 v){
return Mathf.Min(Mathf.Min(v.x, v.y), v.z);
}
// Use this for initialization
void Start () {
Debug.Log((int)(Mathf.Pow(8f, 1f/3f)+0.5f));
Mesh m =GetComponent<MeshFilter>().sharedMesh;
m.RecalculateBounds();
if (GetMax(m.bounds.size)<1f || GetMin(m.bounds.size)<0.1f){
EditorUtility.DisplayDialog("V-HACD", "Build Failed.\nThe largest dimension length is less then 1 unit, or the smallest length is less then 0.1.", "Ok");
return;
}
float[] verts =new float[m.vertexCount*3];
for (int i=0;i<m.vertexCount;++i){
verts[i*3+0] =m.vertices[i].x;
verts[i*3+1] =m.vertices[i].y;
verts[i*3+2] =m.vertices[i].z;
}
GameObject parent =new GameObject();
parent.name ="compound_collider";
parent.transform.SetParent(gameObject.transform, false);
int result_hull_num =0;
bool success =DecomposeMeshToHulls(hulls, tris_per_hull, resolution, verts, (uint)m.vertexCount, m.triangles, (uint)(m.triangles.Length/3), VHACD_CB_Handler);
if (success){
result_hull_num =GetHullSize();
_convex_mesh_colliders =new MeshCollider[result_hull_num];
_convex_mesh =new Mesh[result_hull_num];
for (int i=0;i<result_hull_num;++i){
int vert_ct =0;
System.IntPtr vert_arr_ptr =System.IntPtr.Zero;
GetVerticesData(i, ref vert_ct, ref vert_arr_ptr);
double[] vert_arr =new double[vert_ct*3];
Marshal.Copy(vert_arr_ptr, vert_arr, 0, vert_ct*3);
int tri_ct =0;
System.IntPtr tri_arr_ptr =System.IntPtr.Zero;
GetTrianglesData(i, ref tri_ct, ref tri_arr_ptr);
int[] tri_arr =new int[tri_ct*3];
Marshal.Copy(tri_arr_ptr, tri_arr, 0, tri_ct*3);
List<Vector3> vert_list =new List<Vector3>();
for (int j=0;j<vert_arr.Length/3;++j){
vert_list.Add(new Vector3(
(float)vert_arr[j*3+0],
(float)vert_arr[j*3+1],
(float)vert_arr[j*3+2]
));
}
Mesh tmp_m =new Mesh();
tmp_m.name =GetComponent<MeshFilter>().sharedMesh.name+"_"+i;
tmp_m.SetVertices(vert_list);
tmp_m.SetTriangles(tri_arr, 0);
tmp_m.RecalculateNormals();
MeshCollider mc =parent.AddComponent<MeshCollider>();
mc.sharedMesh =tmp_m;
mc.convex =true;
// mc.sharedMaterial =shared_physic_material;
// mc.isTrigger =isTrigger;
_convex_mesh_colliders[i] =mc;
_convex_mesh[i] =tmp_m;
}
}else{
//...
}
DisposeHullData();
EditorUtility.ClearProgressBar();
}
// Update is called once per frame
void Update () {
}
}
VHACD_Lib.cs 在程式啟動時從 MeshFilter 取得 Mesh 資料，接著呼叫 DecomposeMeshToHulls 函數將這些資料轉成數個 Convex MeshCollider。其中 hulls 表示最多可產生的 Convex Mesh，tris_per_hull 表示每個 Convex Mesh 最多三角面數，resolution 表示 VHACD 在執行時解析原始 Mesh 使用的方格數量。此外要注意的是原始的 Mesh 有數值大小的限制，若是太小則在 Import 時，將 Model Meshes Scale Factor 設定更大的倍率。
以 bunny 作為例子，使用 Unity 內建 MeshCollider 產生的 ConvexCollider 與 V-HACD 計算產生的 Compound Collider 比較如下圖 :
內建工具產生的 Convex Collider
V-HACD 計算產生的 Colliders
將 V-HACD 計算產生的 Colliders 視覺化 (各別著色)
ref 1: https://en.wikipedia.org/wiki/Hyperplane_separation_theorem
ref 2: https://en.wikipedia.org/wiki/Gilbert–Johnson–Keerthi_distance_algorithm
ref 3: https://github.com/kmammou/v-hacd
ref 4: https://forums.unrealengine.com/unreal-engine/announcements-and-releases/36410-engine-features-preview-4-02-2015
