基本的双轮廓理论 [英] Basic Dual Contouring Theory
问题描述
我一直在搜索谷歌，但找不到任何基本的东西。在它最基本的形式中，如何实现双重轮廓（对于体素地形）？我知道它做了什么，为什么，但无法理解如何做到这一点。 JS或C＃（最好）是好的。有没有人之前使用过双轮廓线并可以简单解释一下？
I've been searching on google, but cannot find anything basic. In it's most basic form, how is dual contouring (for a voxel terrain) implememted? I know what it does, and why, but cannot understand how to do it. JS or C# (preferably) is good.Has anyone used Dual contouring before and can explain it briefly?
推荐答案
好的。所以今晚我感到无聊，并决定自己实施双重轮廓。正如我在评论中所说，所有相关材料都在以下文件的第2部分中：
Ok. So I got bored tonight and decided to give implementing dual contouring myself a shot. Like I said in the comments, all the relevant material is in section 2 of the following paper:
http://www.frankpetterson.com/publications/dualcontour/dualcontour.pdf
特别是，网格的拓扑结构在以下部分的2.2部分中描述，引用：
In particular, the topology of the mesh is described in part 2.2 in the following section, quote:
-
对于表现出符号变化的每个立方体，生成一个位于等式1的二次函数的最小值处的顶点。
For each cube that exhibits a sign change, generate a vertex positioned at the minimizer of the quadratic function of equation 1.
对于每个表现出一个符号的边缘符号更改，生成连接包含边缘的四个立方体的最小顶点的四边形。
For each edge that exhibits a sign change, generate a quad connecting the minimizing vertices of the four cubes containing the edge.
这就是它的全部！解决线性最小二乘问题以获得每个立方体的顶点，然后使用四边形连接相邻顶点。因此，使用这个基本思想，我使用numpy在python中编写了一个双轮廓isosurface提取器（部分只是为了满足我自己对它如何工作的病态好奇心）。以下是代码：
That's all there is to it! You solve a linear least squares problem to get a vertex for each cube, then you connect adjacent vertices with quads. So using this basic idea, I wrote a dual contouring isosurface extractor in python using numpy (partly just to satisfy my own morbid curiosity on how it worked). Here is the code:
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(v-o) > 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可视化工具包中）运行它：
It is not very fast because it uses the SciPy's generic non-linear root finding methods to find the edge points on the isosurface. However, it does seem to work reasonably well and in a fairly generic way. To test it, I ran it using the following test case (in the Mayavi2 visualization toolkit):
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-等值面。当我在工具包中运行它时，结果如下：
This defines a sphere as an implicit equation, and solves for the 0-isosurface by dual contouring. When I ran it in the toolkit, this was the result:
总之，它似乎正在运作。
In conclusion, it appears to be working.
这篇关于基本的双轮廓理论的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
