基本的双轮廓理论

我一直在搜索谷歌，但找不到任何基本的东西。 在它最基本的forms中，如何实现双重轮廓（对于体素地形）？ 我知道它做了什么，为什么，但无法理解如何做到这一点。 JS或C＃（最好）是好的。有没有人之前使用过双轮廓线并且可以简单解释一下？

Answer 1

好。 所以今晚我感到无聊，并决定自己实施双重轮廓。 正如我在评论中所说，所有相关材料都在以下文件的第2部分：

http://www.frankpetterson.com/publications/dualcontour/dualcontour.pdf

特别是，网格的拓扑结构在以下部分的2.2部分中描述，引用：

1. 对于表现出符号变化的每个立方体，生成位于等式1的二次函数的最小化器处的顶点。

2. 对于表现出符号变化的每个边缘，生成连接包含边缘的四个立方体的最小顶点的四边形。

这里的所有都是它的！ 解决线性最小二乘问题以获得每个立方体的顶点，然后使用四边形连接相邻顶点。 因此，使用这个基本思想，我使用numpy在python中编写了一个双轮廓isosurface提取器（部分只是为了满足我自己对它如何工作的病态好奇心）。 这是代码：

import numpy as np import numpy.linalg as la import scipy.optimize as opt import itertools as it #Cardinal directions dirs = [ [1,0,0], [0,1,0], [0,0,1] ] #Vertices of cube cube_verts = [ np.array([x, y, z]) for x in range(2) for y in range(2) for z in range(2) ] #Edges of cube cube_edges = [ [ k for (k,v) in enumerate(cube_verts) if v[i] == a and v[j] == b ] for a in range(2) for b in range(2) for i in range(3) for j in range(3) if i != j ] #Use non-linear root finding to compute intersection point def estimate_hermite(f, df, v0, v1): t0 = opt.brentq(lambda t : f((1.-t)*v0 + t*v1), 0, 1) x0 = (1.-t0)*v0 + t0*v1 return (x0, df(x0)) #Input: # f = implicit function # df = gradient of f # nc = resolution def dual_contour(f, df, nc): #Compute vertices dc_verts = [] vindex = {} for x,y,z in it.product(range(nc), range(nc), range(nc)): o = np.array([x,y,z]) #Get signs for cube cube_signs = [ f(o+v)>0 for v in cube_verts ] if all(cube_signs) or not any(cube_signs): continue #Estimate hermite data h_data = [ estimate_hermite(f, df, o+cube_verts[e[0]], o+cube_verts[e[1]]) for e in cube_edges if cube_signs[e[0]] != cube_signs[e[1]] ] #Solve qef to get vertex A = [ n for p,n in h_data ] b = [ np.dot(p,n) for p,n in h_data ] v, residue, rank, s = la.lstsq(A, b) #Throw out failed solutions if la.norm(vo) > 2: continue #Emit one vertex per every cube that crosses vindex[ tuple(o) ] = len(dc_verts) dc_verts.append(v) #Construct faces dc_faces = [] for x,y,z in it.product(range(nc), range(nc), range(nc)): if not (x,y,z) in vindex: continue #Emit one face per each edge that crosses o = np.array([x,y,z]) for i in range(3): for j in range(i): if tuple(o + dirs[i]) in vindex and tuple(o + dirs[j]) in vindex and tuple(o + dirs[i] + dirs[j]) in vindex: dc_faces.append( [vindex[tuple(o)], vindex[tuple(o+dirs[i])], vindex[tuple(o+dirs[j])]] ) dc_faces.append( [vindex[tuple(o+dirs[i]+dirs[j])], vindex[tuple(o+dirs[j])], vindex[tuple(o+dirs[i])]] ) return dc_verts, dc_faces 

它不是很快，因为它使用SciPy的通用非线性根寻找方法来找到等值面上的边缘点。 但是，它似乎确实运行得相当好，并且以相当通用的方式运行。 为了测试它，我使用以下测试用例运行它（在Mayavi2可视化工具包中）：

 import enthought.mayavi.mlab as mlab center = np.array([16,16,16]) radius = 10 def test_f(x): d = x-center return np.dot(d,d) - radius**2 def test_df(x): d = x-center return d / sqrt(np.dot(d,d)) verts, tris = dual_contour(f, df, n) mlab.triangular_mesh( [ v[0] for v in verts ], [ v[1] for v in verts ], [ v[2] for v in verts ], tris) 

这将球体定义为隐式方程，并通过双轮廓线求解0-等值面。 当我在工具包中运行它时，结果如下：

总之，它似乎有效。