Skip to content

fast_winding_number

fast_winding_number(Q, V, F, fwn_bvh=None)

Compute the winding number of a set of query points with respect to a triangle mesh.

Parameters:

Name Type Description Default
Q (n,3) numpy double array

Matrix of query points

required
V (m,3) numpy double array

Matrix of mesh vertices

required
F (p,3) numpy int array

Matrix of triangle indices

required
fwn_bvh gpytoolbox.fast_winding_number_precompute, optional (default None)

Precomputed BVH built via gpytoolbox.fast_winding_number_precompute(V, F). If provided, reuses the BVH across calls instead of rebuilding it, avoiding the O(n) precomputation cost on every query.

None

Returns:

Name Type Description
W (n,) numpy double array

Vector of winding numbers (0 if outside, 1 if inside)

See Also

lazy_cage, fast_winding_number_precompute.

Notes

This function is a wrapper around the C++ implementation of the winding number algorithm by Barrill et al. (2018).

Examples:

Standard one-shot call (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.fast_winding_number(P,v,f)
# W will be zero for points outside the mesh and one for points inside the mesh

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.fast_winding_number(P,v,f,fwn_bvh=bvh)
Source code in src/gpytoolbox/fast_winding_number.py
 3
 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
69
def fast_winding_number(Q,V,F,fwn_bvh=None):
    """Compute the winding number of a set of query points with respect to a triangle mesh.

    Parameters
    ----------
    Q : (n,3) numpy double array
        Matrix of query points
    V : (m,3) numpy double array
        Matrix of mesh vertices
    F : (p,3) numpy int array
        Matrix of triangle indices
    fwn_bvh : gpytoolbox.fast_winding_number_precompute, optional (default None)
        Precomputed BVH built via `gpytoolbox.fast_winding_number_precompute(V, F)`.
        If provided, reuses the BVH across calls instead of rebuilding it,
        avoiding the O(n) precomputation cost on every query.

    Returns
    -------
    W : (n,) numpy double array
        Vector of winding numbers (0 if outside, 1 if inside)

    See Also
    --------
    lazy_cage, fast_winding_number_precompute.

    Notes
    -----
    This function is a wrapper around the C++ implementation of the winding number algorithm by Barrill et al. (2018).

    Examples
    --------
    Standard one-shot call (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.fast_winding_number(P,v,f)
    # W will be zero for points outside the mesh and one for points inside the mesh
    ```

    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.fast_winding_number(P,v,f,fwn_bvh=bvh)
    ```
    """

    if fwn_bvh is not None:
        return fwn_bvh.winding_number(Q.astype(np.float64))

    # Try to import C++ binding
    try:
        from gpytoolbox_bindings import _fast_winding_number_cpp_impl
    except:
        raise ImportError("Gpytoolbox cannot import its C++ fast winding number binding.")

    S = _fast_winding_number_cpp_impl(V.astype(np.float64),F.astype(np.int32),Q.astype(np.float64))

    return S