Skip to content

winding_number

winding_number(O, V, F, fwn_bvh=None)

Compute the sum of solid angles subtended by the faces of a mesh at a set of points. In 2D, this outputs the exact winding number by summing up solid angles; in 3D, this uses the fast winding number approximation by Barrill et al. "Fast Winding Numbers for Soups and Clouds" (SIGGRAPH 2018).

Parameters:

Name Type Description Default
O (p,dim) numpy double array

Matrix of query point positions

 required
V (v,dim) numpy double array

Matrix of mesh/polyline/pointcloud coordinates (in 2D, this is a polyline)

 required
F (f,s) numpy int array

Matrix of mesh/polyline/pointcloud indices into V

 required
fwn_bvh gpytoolbox.fast_winding_number_precompute, optional (default None)

Precomputed BVH for the 3D fast winding number. Ignored in 2D. If provided, reuses the BVH across calls instead of rebuilding it.

 None

Returns:

Name Type Description
W (p,) numpy double array

Vector of winding numbers
See Also

signed_distance, squared_distance, fast_winding_number, fast_winding_number_precompute

Examples:

Standard one-shot call (in 3D, rebuilds the BVH internally each time):

v,f = gpytoolbox.read_mesh("bunny.obj") # Read a mesh
v = gpytoolbox.normalize_points(v) # Normalize mesh
# Generate query points
P = 2*np.random.rand(num_samples,3)-4
# Compute winding numbers
W = gpytoolbox.winding_number(P,v,f)

In 3D, when making many calls against the same mesh, build the BVH once and reuse it via the fwn_bvh= kwarg to avoid the O(n) precomputation cost on every call:

v,f = gpytoolbox.read_mesh("bunny.obj")
v = gpytoolbox.normalize_points(v)
bvh = gpytoolbox.fast_winding_number_precompute(v, f) # build once
for _ in range(num_iters):
    P = 2*np.random.rand(num_samples,3)-4
    W = gpytoolbox.winding_number(P,v,f,fwn_bvh=bvh)
Source code in src/gpytoolbox/winding_number.py 
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def winding_number(O, V, F, fwn_bvh=None):
    """
    Compute the sum of solid angles subtended by the faces of a mesh at a set of points. In 2D, this outputs the exact winding number by summing up solid angles; in 3D, this uses the fast winding number approximation by Barrill et al. "Fast Winding Numbers for Soups and Clouds" (SIGGRAPH 2018).

    Parameters
    ----------
    O : (p,dim) numpy double array
        Matrix of query point positions
    V : (v,dim) numpy double array
        Matrix of mesh/polyline/pointcloud coordinates (in 2D, this is a polyline)
    F : (f,s) numpy int array
        Matrix of mesh/polyline/pointcloud indices into V
    fwn_bvh : gpytoolbox.fast_winding_number_precompute, optional (default None)
        Precomputed BVH for the 3D fast winding number. Ignored in 2D. If
        provided, reuses the BVH across calls instead of rebuilding it.

    Returns
    -------
    W : (p,) numpy double array
        Vector of winding numbers

    See Also
    --------
    signed_distance, squared_distance, fast_winding_number, fast_winding_number_precompute

    Examples
    --------
    Standard one-shot call (in 3D, rebuilds the BVH internally each time):
    ```python
    v,f = gpytoolbox.read_mesh("bunny.obj") # Read a mesh
    v = gpytoolbox.normalize_points(v) # Normalize mesh
    # Generate query points
    P = 2*np.random.rand(num_samples,3)-4
    # Compute winding numbers
    W = gpytoolbox.winding_number(P,v,f)
    ```

    In 3D, when making many calls against the same mesh, build the BVH
    once and reuse it via the `fwn_bvh=` kwarg to avoid the O(n)
    precomputation cost on every call:
    ```python
    v,f = gpytoolbox.read_mesh("bunny.obj")
    v = gpytoolbox.normalize_points(v)
    bvh = gpytoolbox.fast_winding_number_precompute(v, f) # build once
    for _ in range(num_iters):
        P = 2*np.random.rand(num_samples,3)-4
        W = gpytoolbox.winding_number(P,v,f,fwn_bvh=bvh)
    ```
    """
    dim = V.shape[1]
    if dim == 2:
        # Compute solid angles
        VS = V[F[:, 0], :]
        VD = V[F[:, 1], :]

        # 2D vectors from O to VS and VD
        O2VS = np.expand_dims(O[:, :2], axis=1) - np.expand_dims(VS[:, :2], axis=0)
        O2VD = np.expand_dims(O[:, :2], axis=1) - np.expand_dims(VD[:, :2], axis=0)

        S = - np.arctan2(O2VD[:, :, 0] * O2VS[:, :, 1] - O2VD[:, :, 1] * O2VS[:, :, 0], O2VD[:, :, 0] * O2VS[:, :, 0] + O2VD[:, :, 1] * O2VS[:, :, 1])
        W = np.sum(S, axis=1) / (2 * np.pi)
    elif dim == 3:
        # Compute winding number. It would be nice to have the exact winding number using solid angle in 3D too, but for now this is good for most times I want it.
        W = fast_winding_number(O,V,F,fwn_bvh=fwn_bvh)
    return W