Channy's blog

//Description: V-HACD (Volumetric Hierarchical Approximate Convex Decomposition)

//Create Date: 2021-12-14 11:07:39

//Author: channy

概述

vhacd_flow

支持输入格式：.off和.obj

类 方法 功能 步骤
VHACD ComputeACD 主入口，包括各项子流程  
VHACD AlignMesh 初始化基本操作 模型对齐，体素化
Volume Voxelize 体素化 根据比例把mesh转化为体素数据，inside/on/outside surface
VHACD VoxelizeMesh 迭代性体素化以寻找最优dim  
VHACD ComputePrimitiveSet 把Volume转化成VoxelSet 基于voxel或tetrahedron
VHACD ComputeACD(const Parameters& params) pca  
VoxelSet ComputeConvexHull 基于ConvexHull计算ConvexHull  
VHACD ComputeConcavity 计算误差  
VHACD ComputePreferredCuttingDirection 计算w (Game Engine Gems 3. 11.10)  
VHACD ComputeBestClippingPlane 分割平面  
VHACD MergeConvexHulls 合并ConvexHulls (Game Engine Gems 3. 11.11)  
  SimplifyConvexHulls / SimplifyConvexHull 简化mesh，以不共面的四个顶点组成的四面体为基础，不断增加点  
VHACD ComputeCenterOfMass 质心  
  ComputeBB BoundingBox  

HACD vs V-HACD

HACD vs V-HACD

HACD (simplify from bullit library) too slow if there is no opt

VHACD

convexhullDownsampling默认为4 split threshold = concavity + balance + symmetry 其中， concavity = (volumeCH - volume) / TotalVolume concavity = concavityLeft + concavityRight balance = alpha * abs(volumeLeft - volumeRight) / TotalVolume symmetry = beta * w * distance(plane, cuttingDir)

改进思路

  1. 参考文档的说明建议： roblox参考文档使用原HACD算法(2010年)和roblox的算法(2020年)进行比较，而原HACD算法作者在2016年对HACD进行了改进，即Blockman现在使用的VHACD。 1.1 提取曲面采样点方式 原HACD：使用相同采样密度对每个三角面片进行采样，当三角面片面积大时采样点相对少，信息有丢失 roblox建议：使用网格点均匀分布在三角面片上进行采样，保证采样点数量和曲面大小成正比。 VHACD: 使用网格点均匀分布在三角面片上进行采样 1.2 concavity error的计算。 原HACD：原HACD使用了原始曲面采样点到该曲面凸包的最远距离作为该误差 roblox建议：使用目标面分成的两个曲面的凸包面积和与原始曲面凸包面积作差，结果的平方作为该误差 1.3 凸包生成方式 原HACD：使用Quickhull算法，当多点接近共面时无法很好地处理 roblox建议：增加考虑共面情况，同时实现2D Quickhull和3D Quickhull 1.4 其它（浮点数精度问题）
  2. 其它方向： 原HACD：使用concavity error误差大的点计算分割平面 VHACD：使用坐标轴所在平面进行分割 可改进方向：改回使用concavity error误差大的点计算分割平面，或其它方式分割平面

concavity error calculation

The original paper mentions that this error can be tracked many ways, and the implementation used the farthest distance from the original surface to the newly formed surface within the newly formed predictive convex hull. We will use the same definition.

计算concavity error的目的是评估去掉一条边后生成的convex hull相比原模型的“损失”。原论文中表示可以有多种方法追踪这个误差，并使用了原始曲面到新生成曲面的最远距离作为该误差。roblox使用同样的方法。
为了得到该误差需要两方面的信息：

原始模型可量化的特征量
去掉该边后的模型生成的精确的convex hull

The original HACD implementation used a few sample points per triangle as a representation of the original surface (During Step 1 from overview). These points would then be used to raycast from, along the face normals, to find the backface of a convex hull that is impeding concavities. The longest distance from the original surface to the backface was considered the error.

HACD使用一个三角面片中一系列的采样点来表示原始曲面，这些采样点将被用于在法线方向进行raycast检测，以找到影响convex hull的凹面。从原始曲面到凹面的最长距离即为误差。乍看是一回事，但基于不同的三角面片有不同的采样密度，大三角面片的简单模型会有大量的盲点
roblox基于网格距离对每个三角面片进行采样，然后使用BB快速过滤。
继续过滤当前convex hull边界附近的点，raycast。如果误差没有增加，所有返回距离都是0，但一个有问题的convex hull会使得raycasts碰撞

We will uniformly generate surface sample points for every triangle based on a configured grid distance

In summary, the error generation can be described as such:

  1. (During step 1 from algorithm overview) Uniformly sample points on each triangle and toss them into a spatial grid.
  2. Grab the bounding box of the convex hull we are testing and gather all points in the grid inside of this bounding box. From the gathered points, for every sample point INSIDE the convex hull, we do a raycast along the original surface normal to see if it hits the backface of the convex hull.
  3. The ray with the largest distance that hit a backface ends up being our concavity error.
  4. If the convex hull does not extrude outside of the original surface, the result should be 0.
  5. This can be optimized by exiting early as soon as the first sample raycast exceeds the maximum allowed global error, as this is enough to stop an edge from collapsing.

总结如下：
对每个三角面片进行采样，映射到一个特殊的网格
计算convex hull的BB并过滤所有在BB内部的点
raycast检测是否碰撞
最大距离计为concavity error
如果convex hull没有被挤出原始曲面，返回值应该是0
优化，尽早退出

This method only works well on 3D convex hulls. If the convex hull is flat, the sample points would never be aligned in the directions we would need to test during the formation of 2D convex hulls.

该方案提供了一个很好的稳定性，但只有在3D convex hull中才占优势。如果convex hull比较平滑，采样点将不会被对齐到2D方向上。

In order to properly resolve this, we would have to consider a completely different 2D error calculation process, which would be just as involved as the one we described.

为了解决该问题，roblox使用完全不同的2D error计算过程。

We can compare the area of the sum of the original two convex hulls to the area of the result. If the resulting hull has more area than the sum of the two source hulls, you know it may be closing a concavity, and therefore the square root of the extra area can be treated as the concavity error in this case!

通过比较结果和原始两个convex hull的面积和，如果结果的面积大，表明接近concavity，这时面积差的开方可以作为concavity error。

convex hull generation

After tweaking the concavity error calculation, we used the visual debugger to confirm that we still had issues:

Certain convex hulls that would seal large concavities would still pass the concavity error test with a result of 0. Combining two convex hulls would sometimes cause a vertex to disappear, leaving a hole in the original shape.

消除大凹面的convex hull依旧会返回concavity error = 0
合并convex hull有时会丢失顶点，形成空洞

HACD使用Quickhull算法，当有点共面/共线时有误差

Quickhull通过合并共面三角面片避免上述问题。然而这种方法不能用于区分原始三角面片。

As before with concavity error calculation, we must consider the 2D case as well. In order to protect your Convex Decomposition code from a variety of input data, you MUST implement a 2D Quickhull AS WELL as a 3D Quickhull to allow the combination of coplanar triangles. If we attempt to use the same process for coplanar triangles, it will not work and often delete input vertices or fail.

2D和3D Quickhull

Conclusions 结论

从三个方面改进：

  1. 面采样
  2. 在concavity error计算和convex hull生成过程中区分2D-3D不同计算（共面问题）
  3. 浮点数精度

总结

VHACD

input: triangleMesh (points, triangles)
output: convexHull
基本步骤：先计算整个大凸包，再选取平面切割成小凸包 steps:

HACD

input: triangleMesh (points, triangles)
output: convexHull
基本步骤：对每一个三角面看成一个凸包，不断合并，形成最终的凸包
steps:

reference

HACD V-HACD-SourceCode
V-HACD
ROHACD HACD vs. V-HACD