algorithm - 建设性的实体几何网格

Question

如果我使用 constructive solid geometry 构建一个形状技术，如何构建用于渲染的线框网格？我知道直接渲染 CSG 形状的算法，但我只想将它转换为线框网格一次，以便我可以“正常”渲染它

添加更多细节。给定一个形状的描述，例如“这里是一个立方体，在这里与一个球体相交，在这里减去一个圆柱体”，我希望能够计算多边形网格。

Answer 1

主要有两种方法。如果您有一组多边形形状，则可以为每个形状创建一个 BSP 树，然后可以合并 BSP 树。来自维基百科，

1990 Naylor, Amanatides, and Thibault provide an algorithm for merging two bsp trees to form a new bsp tree from the two original trees. This provides many benefits including: combining moving objects represented by BSP trees with a static environment (also represented by a BSP tree), very efficient CSG operations on polyhedra, exact collisions detection in O(log n * log n), and proper ordering of transparent surfaces contained in two interpenetrating objects (has been used for an x-ray vision effect).

论文在这里找到Merging BSP trees yields polyhedral set operations .

或者，每个形状都可以表示为空间函数(例如到表面的有符号距离)。只要将曲面定义为函数等于零的地方，就可以使用 (MIN == intersection)、(MAX == union) 和 (NEGATION = not) 运算符组合函数来模拟集合运算。然后可以使用 Marching Cubes 等技术将生成的表面提取为组合函数等于零的位置。也可以使用更好的表面提取方法，例如 Dual Marching Cubes 或 Dual Contouring。当然，这将导致真实 CSG 表面的离散近似。我建议使用 Dual Contouring ，因为它能够重建尖锐的特征，例如立方体的角。