标签: marching-cubes

我一直在尝试使用OpenGL和GLSL编写Marching Cubes算法的两遍GPU实现,类似于GPU Gems 3第一章中详述的算法.但是,glDrawArrays在我的第一次传球中的呼叫始终失败了GL_INVALID_OPERATION.

我查找了所有可以找到的文档,并发现这些条件glDrawArrays可以抛出该错误:

1. GL_INVALID_OPERATION如果非零缓冲区对象名称绑定到已启用的数组或GL_DRAW_INDIRECT_BUFFER绑定,并且缓冲区对象的数据存储当前已映射,则会生成.
2. GL_INVALID_OPERATION如果glDrawArrays在执行glBegin和相应的执行之间执行,则生成glEnd.
3. GL_INVALID_OPERATION将由glDrawArrays或glDrawElements当前程序对象中的任何两个活动采样器具有不同类型,但引用相同的纹理图像单元.
4. GL_INVALID_OPERATION 如果几何着色器处于活动状态且模式与当前安装的程序对象中几何着色器的输入基元类型不兼容,则会生成.
5. GL_INVALID_OPERATION如果模式是GL_PATCHES并且没有曲面细分控制着色器处于活动状态,则生成.
6. GL_INVALID_OPERATION如果将基元的顶点记录到用于变换反馈目的的缓冲区对象,则会生成超出任何缓冲区对象大小的限制,或者超出结束位置偏移+大小-1,如下所示glBindBufferRange.
7. GL_INVALID_OPERATIONglDrawArrays()如果不存在几何着色器,则生成变换反馈,并且模式不是允许的模式之一.
8. GL_INVALID_OPERATIONglDrawArrays()如果存在几何着色器,则生成变换反馈,并且几何着色器的输出基元类型与变换反馈primitiveMode不匹配.
9. GL_INVALID_OPERATION 如果绑定着色器程序无效,则生成.
10. GL_INVALID_OPERATION如果正在使用变换反馈,则生成编辑10/10/12:绑定到变换反馈绑定点的缓冲区也绑定到数组缓冲区绑定点.这是我遇到的问题,因为我绑定了缓冲区的拼写错误.虽然规范确实声明这是非法的,但在我发现的任何文档中,它都没有列在glDrawArrays下作为它可以抛出错误的原因之一.

不幸的是,我找不到任何一份官方文档,其中包括超过3篇.我不得不从众多来源收集这份清单.第7点和第8点实际上来自文档glBeginTransformFeedback,第9点似乎根本没有记录.我发现它在某个论坛帖子中提到过.但是,我仍然不认为这个列表是完整的,因为这些似乎都没有解释我得到的错误.

1. 我在任何地方的程序中都没有映射任何缓冲区.
2. 我使用的是核心配置文件,所以glBegin并glEnd没有提供连.
3. 我有两个采样器,它们有不同的类型,但它们肯定映射到不同的纹理.
4. 几何着色器处于活动状态,但它的输入布局是layout (points) in,并且glDrawArrays正在调用GL_POINTS.
5. 我没有使用GL_PATCHES任何类型的镶嵌着色器.
6. 我已经确定我正在分配我的几何着色器可能输出的最大空间量.然后我尝试了四倍.没有帮助.
7. 有一个几何着色器.看下一点.
8. 正在使用变换反馈,并且有一个几何着色器,但输出布局是layout (points) out …

我已经成功实现了行进立方体算法.我使用标准材料作为参考,但我完全从头开始重写.它有效,但我观察到导致网格中的洞的模糊性.

我正在考虑行进的四面体算法,据说这种算法不会产生歧义.我看不出这是怎么可能的.

行进四面体算法使用六个四面体代替立方体,每个四面体具有三角剖分.但是,假设我要实现行进立方体算法,但对于256个三角测量中的每一个,只需选择多维数据集四面体三角剖分的"和"(并集)？据我所知,这就是行军四面体的作用 -那为什么会神奇地修复模糊性？

我认为有16个独特的案例,其他240个只是那些16的反思/轮换.我记得在某个地方阅读一些解决含糊之处的文章,你需要33个案例.这可能与为什么行进四面体不会出现问题有关？

所以,问题:

1. 为什么行军四面体不会有歧义？
2. 如果没有,为什么人们不使用行进立方体算法,而是使用四面体的三角剖分？

我觉得我在这里错过了一些东西.谢谢.

我正在Unity中使用Marching Cubes实现.我的代码基于Paul Bourke的代码实际上有很多修改,但无论如何我正在检查一个位置的块是否为空,如果它不是调试纹理将放在它上面.

这是我的MC脚本

    public class MarchingCubes
{
private World world;
private Chunk chunk;
private List<Vector3> vertices = new List<Vector3> ();
private List<Vector3> normals = new List<Vector3> ();
private Vector3[] ns;
private List<int> triangles = new List<int> ();
private List<Vector2> uvs = new List<Vector2> ();
private Vector3[] positions = new Vector3[8];
private float[] corners = new float[8];
private Vector3i size = new Vector3i (16, 128, 16);

Vector3[] vertlist = new Vector3[12];

private float isolevel = 1f;

private float …

我正在尝试构建一个适当的可破坏地形,仅用于研究目的.好吧,一切都很顺利,但解决方案并不能令我满意.我已经看到了很多人们如何实现MC算法的例子,但据我所知,大多数人使用函数对最终网格进行三角测量,这对我来说并不合适.

我将简要地解释一下我是如何构建我的地形的,也许你们中的某个人会给我建议如何改进或提高最终地形的分辨率.

1)预先计算MC三角形.

我正在为每个案例(0-255)运行MC查找表的简单循环,并在愤怒中计算三角形:[0,0,0] - [1,1,1].这里没问题.

2)地形

我有地形类,它存储我的体素.一般来说,它看起来像这样:

int size = 32;//Size of each axis.
unsigned char *voxels = new unsigned char[(size * size * size)/8];

因此,每个轴的长度为32个单位,但是,我每位存储体素信息.意思是如果打开位(1),有东西,应该画一些东西.

我有几个功能:

TurnOn(x,y,z);
TurnOff(x,y,z);

打开或关闭体素的位置.(有助于使用位).

一旦分配了地形,我就会运行perlin噪声,并打开或关闭位.

我的地形类还有一个函数,用于从x,y,z位置提取Marching Cubes案例编号(0-255):

unsigned char GetCaseNumber(x,y,z);

通过确定该体素的邻居是打开还是关闭.这里没问题.

3)渲染部分

我循环每个轴,提取案例编号,然后按案例获得预先计算的三角形,转换为x,y,z坐标,并绘制这些三角形.这里没问题.

所以结果看起来像这样:

但正如您所看到的,在任何一个位置,分辨率都无法与此类似: MC http://www.angelfire.com/linux/myp/MCAdvanced/mcnormal.gif

我在MC的例子中看到人们正在使用一种叫做"iso值"的东西,我不明白.任何建议如何改进我的工作,或什么是iso值,以及如何在统一网格中实现它将是真正可爱的.

如果有人关心,我正在使用WPF ....

故事的开头:

我得到了一系列灰度图像(模型切片).用户输入灰度值的"范围"以构建3D模型.因此,我创建了一个3D bool数组,以便更容易地构建3D模型.此数组表示一个像素框,指示是否应构建/生成/填充每个像素.

领带:

使用a bool[,,],我想检索List<Point3D[]>每个Point3D[]长度为3的位置,并表示3D空间中的三角形.

附加信息:

生成的模型将进行3D打印.在bool[,,],true表示物质的存在,而false表明没有物质.我需要避免使用立方体模型,其中每个像素都被立方体替换(根据我的目的,这将是无用的).模型应尽可能平滑且尽可能准确.

我试图做的:

1-我实现了行进立方体算法,但似乎没有创建它来接受值的"范围".

2-我一直在努力制作自己的算法,但我部分失败了.(这真的很复杂.如果你想了解更多信息,请告知)

一些我不知道如何实现的预期解决方案:

1-修改Marching cube算法,以便使用a bool[,,]

2-修改Marching cube算法,以使其使用"范围" isolevel值的工作

3-展示如何在WPF中实现适合我的目的的另一种算法(可能是Ray-Casting算法).

4-请求我尝试实现的算法源,然后向我展示如何解决它.(它首先是将a多边形化bool[,,])

5-其他一些神奇的解决方案.

提前致谢.

编辑:

通过说

使用a bool[,,],我想检索List<Point3D[]>每个Point3D[]长度为3的位置,并表示3D空间中的三角形.

我的意思是我想要检索一组三角形.每个三角形应表示为3 Point3D秒.如果您不知道Point3D它是什么,它struct包含3个双打(X,Y和Z),用于表示3D空间中的位置.

行进立方体算法的问题在于它有点模糊.我的意思是,通过这样做,你有什么理解？

cubeindex = 0; 
if (grid.val[0] < isolevel) cubeindex |= 1; 
if (grid.val[1] < isolevel) cubeindex |= 2; 
if (grid.val[2] < isolevel) cubeindex |= …

我正在使用这个行进立方体算法绘制3D等值面(移植到C#,输出MeshGeomtry3Ds,但其他方面相同).结果表面看起来很棒,但需要很长时间才能计算出来.

有没有办法加速行进立方体？最明显的一个是简单地降低空间采样率,但这会降低结果网格的质量.我想避免这种情况.

我正在考虑一个双通道系统,第一次通过采样空间更粗糙,消除了场强远低于我的等级的体积.这是明智的吗？有什么陷阱？

编辑:代码已被分析,并且大部分CPU时间在行进立方体例程本身和每个网格单元角落的场强计算之间分配.现场计算超出了我的控制范围,因此加速立方体程序是我唯一的选择......

我仍然想到试图消除死区的想法,因为这会大大减少对两个系统的调用次数.

我使用行进立方体渲染等值面(或者可能是行进的正方形,因为这是2D),我想做集合操作,如设置差异,交集和联合.我认为这很容易实现,只需在两个不同的隐式曲面中选择两个顶点标量,但事实并非如此.

对于我的初步测试,我尝试了两个球体圆圈,以及设置的操作差异.即A - B.一个圆圈正在移动而另一个圆圈是静止的.这是我在选择顶点标量时以及在将角顶点分类为内部或外部时尝试的方法.代码是用C++编写的.OpenGL用于渲染,但这并不重要.没有任何CSG操作的正常渲染确实给出了预期的结果.

       void march(const vec2& cmin, //min x and y for the grid cell
                  const vec2& cmax, //max x and y for the grid cell
                  std::vector<vec2>& tri, 
                  float iso,
                  float (*cmp1)(const vec2&), //distance from stationary circle
                  float (*cmp2)(const vec2&) //distance from moving circle
)
{
  unsigned int squareindex = 0;
  float scalar[4];
  vec2 verts[8];
  /* initial setup of the grid cell */
  verts[0] = vec2(cmax.x, cmax.y);
  verts[2] = vec2(cmin.x, cmax.y); …

我已经在C#中实现了行进立方体,双行进立方体和自适应行进立方体,但却发现我需要双重轮廓以达到我的目的.我已经阅读了关于双轮廓的所有作品,除了双轮廓本身的核心之外,我得到的只是:最小化二次误差函数(QEF).

现在,我只是通过找到共享该单个顶点(3到6个边)的所有edgePoints之间的平均值来计算内部体素的顶点位置,并且它运行良好,但它显然不会在正确的位置创建内部顶点.

这是我要创建的代码片段.任何帮助将非常感激

/// <summary>
    /// ORIGINAL WORK: Dual Contouring of Hermite Data by Tao Ju (remember me of a MechCommander 2 character)
    /// 2.3 Representing and minimizing QEFs
    /// The function E[x] can be expressed as the inner
    /// product (Ax-b)T (Ax-b) where A is a matrix whose rows are the
    /// normals ni and b is a vector whose entries are ni*pi.  <------------ (dot product?)>
    /// Typically, the quadratic function E[x] is expanded into the form
    /// E[x] …

我正在开发 3D 重建系统，并希望使用 Python 3 从注册的点云数据生成三角形网格。我的对象不是凸的，因此行进立方体算法似乎是解决方案。

我更喜欢使用此类方法的现有实现，因此我尝试了scikit-image和Open3d，但这两个 API 都不接受原始点云作为输入（请注意，我不是这些库的专家）。我转换数据的尝试失败了，并且我已经没有想法了，因为文档没有阐明函数的输入格式。

这些是我想要的片段，这pcd_to_volume是我需要的。

scikit 图像

import numpy as np
from skimage.measure import marching_cubes_lewiner

N = 10000
pcd = np.random.rand(N,3)

def pcd_to_volume(pcd, voxel_size):
    #TODO

volume = pcd_to_volume(pcd, voxel_size=0.05)

verts, faces, normals, values = marching_cubes_lewiner(volume, 0)

开放3D

import numpy as np
import open3d

N = 10000
pcd = np.random.rand(N,3)

def pcd_to_volume(pcd, voxel_size):
    #TODO

volume = pcd_to_volume(pcd, voxel_size=0.05)

mesh = volume.extract_triangle_mesh()

我无法找到正确编写该pcd_to_volume函数的方法。我不喜欢图书馆，所以这两种解决方案对我来说都很好。

您对正确转换我的数据有什么建议吗？点云是一个Nx3矩阵，其中dtype=float.

您知道另一种适用于原始点云数据的[行进立方体算法]实现吗？我更喜欢 …

你好。

在过去的一个月里，我一直在从各种来源收集信息，但没有找到适合我的特定问题的想法。所以这里是问题的表述：

给定一个缓冲区几何形式的网格（顶点坐标和顶点索引的 32 位数组 + 附加数组，例如顶点法线、uvs 或切线），计算围绕网格的均匀点网格的有符号距离函数 (SDF)几何学。

更具体地说，我打算在 Maxon 的 Cinema4D 或 Blender 等 3D 引擎中创建类似于 MetaBall 对象的东西。我已经成功地为所有几何图元实现了距离函数，但是任意网格 SDF 需要我实现一种蛮力方法 - 测试每个网格点的每个网格三角形的距离 - 当然，对于复杂的，这变得非常慢网格。

现在，我回想起来，这些问题中的大多数都需要构建一个树状结构，例如八叉树、KD 树、BSP 树或 AABB 树。然后我发现了一些关于所谓的快速扫描算法 （用于求解 Eikonal 方程）的文章，该算法首先需要用 0 填充位于边界（在我的情况下为网格，或最接近网格）的网格点其余的值较大（Infinity），然后迭代求解非线性双曲边值问题（Gauss-Seidel）。我还在CGAL 库中找到了网格 SDF 方法的开源实现。或者，我也考虑过使用一些着色器库（如 GLSL），也许尝试使用 GPU 构建树，但我从未在 JS 或 TS 项目中使用过着色器。

我一直坚持的步骤不仅仅是选择最好的选择，而且实际上实际上至少有效地使用了这些方法中的一种。例如：

• 如果我想实现Fast-Marching Method，我必须遍历所有三角形，然后为每个三角形遍历所有网格点 Gijk，并使用类似于 Marching Cubes 查找表的东西来查找网格单元交叉点（但使用更多选项），我会为相交的单元格顶点插入接近 0 的值。我有一种感觉，这会花费不必要的时间，并且被证明不适合实时更新。

• 我设法在 Unity 中找到了一些Ray Marching SDF计算的例子。此外，由于我从未尝试过直接在 GPU 上计算任何内容，因此我不知道例如并行计算的限制实际上是什么，我也不了解此类计算是如何进行的。我可以并行计算到每个三角形的距离，然后对每个网格点 Gijk 的所有距离进行快速排序吗？如果是这样，我如何将它包含到 TypeScript 项目中？

• 假设我围绕网格中的所有三角形构建了一个AABB 树（应该是 O(n …