标签: marching-cubes

你好。

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

给定一个缓冲区几何形式的网格（顶点坐标和顶点索引的 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 …

我刚刚完成了这些用于双行进立方体的桌子（由尼尔森制作）。VerticesNumberTable 包含为每个体素创建的顶点数组的长度（1 到 4 个内部顶点），而 EdgesTable 用于将这些顶点中的每一个分配给体素的右边缘，以便使用它们来计算内部顶点位置和正常。Edgetable 的工作原理有点像 triTable，用于原始的移动立方体算法。每组边与下一组边之间用 -1 分隔。该列表以-2 结束，因此该值可用于打破循环。

#region EdgesTable

    public static int[,] EdgesTable = new int[256, 16]
    {
            {-2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
            {0, 8, 3, -2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},  
            {0, 1, 9, -2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},  
            {1, 3, 8, 9, -2, -1, -1, -1, -1, …

我目前正致力于通过在OpenGL中渲染样本数据集来理解和实现使用C++的Marching Cubes算法.

我遇到了一个问题,我渲染的网格缺少三角形.我看到几乎一半的三角形丢失,可以在下面看到.

填写三角形和创建四边形是解决问题的正确方法,还是我错过了一些明显的东西？

我使用的边缘交叉表来自以下链接:http: //paulbourke.net/geometry/polygonise/

我没有使用12位条目的边标志数组,而是有12个if语句(其中显示了2个).我使用索引进入3D数组,根据边值确定x,y,z的值(0-11)

    if ((edge.point1 == 0 && edge.point2 == 1) ||
        (edge.point1 == 1 && edge.point2 == 0))
    {
        p1.x = x;   p1.y = y; p1.z = z;
        p2.x = x+1; p2.y = y; p2.z = z;
    }
    else if ((edge.point1 == 1 && edge.point2 == 2) ||
             (edge.point1 == 2 && edge.point2 == 1))
    {
        p1.x = x+1; p1.y = y;   p1.z = z;
        p2.x = x+1; p2.y = y+1; p2.z = …

我用Haskell OpenGL绘制了Barth sextic并且存在问题.我也用R(用包rgl和misc3d)绘制它,没有问题.这两种算法(在Haskell和R中)非常相似.Barth sextic是一个隐式曲面,在Haskell中我使用行进立方体算法计算这个曲面的三角剖分,我通过将其中一个转换misc3d为Haskell和C.我使用顶点法线,每个由隐式渐变定义方程.

这是问题所在:

我不想要这些黑色阴影.当我看到sextic的背面,通过180°旋转,没有这样的阴影:

这个Github仓库中提供了完整的代码.以下是与颜色相关的代码部分:

fuchsia :: Color4 GLfloat
fuchsia = Color4 1.00 0.00 1.00 1
discord :: Color4 GLfloat
discord = Color4 0.21 0.22 0.25 1

  renderPrimitive Triangles $ mapM_ drawTriangle triangles
  swapBuffers
  where
    drawTriangle ((v1,v2,v3), (n1,n2,n3)) = do
      materialDiffuse FrontAndBack $= fuchsia
      normal n1
      vertex v1
      normal n2
      vertex v2
      normal n3
      vertex v3

  clearColor $= discord
  materialAmbient FrontAndBack $= black
  materialDiffuse FrontAndBack $= white
  materialEmission FrontAndBack $= black …

我正在iso平面上运行行进方块(相对于行进立方体)算法,然后将数据转换为三角形网格.

这可行,但会创建非常复杂的网格数据.我想将其简化为所需的最小三角形,如下图所示:

我试过在轮廓周围循环(点 - >段 - >点 - > ...),但如果一个点有超过2个附加段,轮廓可能会反转.

理想情况下,解决方案应该相当快,以便可以在运行时完成.我使用的语言是C#,但可能从大多数其他类C语言中移植它.

计算固定大小的体素数据的梯度的最有效方法是什么,例如下面的源代码.请注意,我需要在空间的任何位置使用渐变.渐变将用于估计行进立方体实现中的法线.

#import <array>

struct VoxelData {
    VoxelData(float* data, unsigned int xDim, unsigned int yDim, unsigned int zDim)
    :data(data), xDim(xDim), yDim(yDim), zDim(zDim)
    {}

    std::array<float,3> get_gradient(float x, float y, float z){
        std::array<float,3> res;
        // compute gradient efficiently
        return res;
    }

    float get_density(int x, int y, int z){
        if (x<0 || y<0 || z<0 || x >= xDim || y >= yDim || z >= zDim){
            return 0;
        }
        return data[get_element_index(x, y, z)];
    }

    int get_element_index(int x, int y, int z){
        return x …

我正在尝试使用行进立方体算法渲染带有Gouraud着色的3D模型(来自volvis.org).到目前为止,我有每个顶点的法线:

GetNormalForVertex(vertex &b, vertex &a, vertex &c) {
    u.X = a.X - b.X;
    u.Y = a.Y - b.Y;
    u.Z = a.Z - b.Z;
    v.X = c.X - b.X;
    v.Y = c.Y - b.Y;
    v.Z = c.Z - b.Z;

    return  Cross(u,v);
}

渲染时我可以看到一个漂亮的平面阴影.现在,据我所知,我需要插入这些顶点法线以在交叉点找到法线以获得Gouraud阴影.我怎么能插入顶点法线？

我需要从同时支持圆角和尖锐几何体的八叉树或阵列中的体素块生成等值面。我搜索了似乎能够完成此任务的算法，并发现了几种算法，包括双重轮廓，扩展行进立方体和双重行进立方体。但是，前两个要求的Hermite数据似乎消耗大量内存。此外，我找不到这些中任何一个的实际算法，只能找到期刊和模糊描述中的方程式。任何能找到解决我的问题的算法的帮助将不胜感激。

关于行进立方体，我对其算法和实现有一些怀疑。我阅读了Pauling Bourke在Marching Cubes上的出色文章以及该站点上的可用源代码，但是，在理解以及如何以自己的方式实现算法方面，我仍然遇到一些问题。问题如下：

• 网格单元大小-我已经读过，网格单元大小会影响生成的3D模型的质量。例如，如果我拥有一堆尺寸为（200 * 200 * 200）的X射线图像集，那么将从2个相邻图像切片中构建一个网格单元平板。因此，平板中的网格单元总数为（200-1）*（200-1），每个网格单元角对应于图像的像素值/密度。它是否正确？？此外，我们如何实现不同大小的网格？

• 体素大小-我已经阅读了《游行立方体》的一些参考资料，但我似乎无法找到算法中如何处理体素大小。如果我错了，请纠正我，在我的情况下，相邻图像层之间的间隙为100万密耳；因此，我该如何照顾Marching Cubes算法中的那些功能？是否照顾到Gridcell的大小？（假设：一个像素在其xy坐标中的大小为19微米，而gap / z为25.4微米/ 1密耳长）

• 网格单元角的坐标（多维数据集的坐标）-我试图通过图像集尺寸（200 * 200 * 200）的嵌套循环为索引为ijk的网格单元的角坐标指定。它是否正确？？有没有更快的方法呢？

注意：我已经在VTK中看到了MC的实现，但是我很难消化它，因为它依赖于其他一些VTK类。

八叉树是行进立方体的特例吗？我的意思是八叉树使用相同的行进立方体的三角形立方体.我知道八叉树是四叉树的三维形式.我只是想知道我是否正确的方向.在树形成之后,八叉树如何形成三角形(用于创建表面)与行进立方体的步骤相同？

我正在使用行进立方体算法的Scikit Image实现来生成等值面。

verts, faces,normals,values = measure.marching_cubes(stack,0)

产生以下错误：

ValueError：需要两个以上的值才能解压

但

 verts, faces = measure.marching_cubes(stack,0)

如此看来算法根本就没有产生的值正常工作normals和values。有没有人有过这类问题的经验？

此外，我不了解faces算法输出的必要性，因为网格中每个三角形的一组3个顶点应该足以描述等值面？

以下Python源代码是Marching Square算法的实现：

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import math
import cv2
from PIL import Image, ImageDraw

class Square():
    A = [0, 0]
    B = [0, 0]
    C = [0, 0]
    D = [0, 0]
    A_data = 0.0
    B_data = 0.0
    C_data = 0.0
    D_data = 0.0

    def GetCaseId(self, threshold):
        caseId = 0
        if (self.A_data >= threshold):
            caseId |= 1
        if (self.B_data >= threshold):
            caseId |= 2
        if (self.C_data >= threshold):
            caseId …