8000 MAINT: Unify calculation of normal vectors from polygons · matplotlib/matplotlib@67fc7c1 · GitHub
[go: up one dir, main page]
Skip to content

Commit 67fc7c1

Browse files
eric-wiesereric-wieser
committed
MAINT: Unify calculation of normal vectors from polygons
This combines `get_normals` and `_generate_normals`, and eliminates all other calls to np.cross. `get_normals` and `_generate_normals` were profiled, and it was found that vectorizing `np.cross` like in `get_normals` was faster: ```python import numpy as np def get_normals(polygons): v1 = np.empty((len(polygons), 3)) v2 = np.empty((len(polygons), 3)) for poly_i, ps in enumerate(polygons): # pick three points around the polygon at which to find the # normal doesn't vectorize because polygons is jagged i1, i2, i3 = 0, len(ps)//3, 2*len(ps)//3 v1[poly_i, :] = ps[i1, :] - ps[i2, :] v2[poly_i, :] = ps[i2, :] - ps[i3, :] return np.cross(v1, v2) def _generate_normals(self, polygons): normals = [] for verts in polygons: v1 = np.array(verts[0]) - np.array(verts[1]) v2 = np.array(verts[2]) - np.array(verts[0]) normals.append(np.cross(v1, v2)) return np.array(normals) polygons = [ np.random.rand(np.random.randint(10, 1000), 3) for i in range(100) ] %timeit _generate_normals(polygons) # 3.14 ms ± 255 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) %timeit get_normals(polygons) # 452 µs ± 4.33 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) ```
1 parent 05c60cc commit 67fc7c1

File tree

1 file changed

+44
-33
lines changed

1 file changed

+44
-33
lines changed

‎lib/mpl_toolkits/mplot3d/axes3d.py

Lines changed: 44 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -1683,28 +1683,14 @@ def plot_surface(self, X, Y, Z, *args, norm=None, vmin=None,
16831683
if fcolors is not None:
16841684
colset.append(fcolors[rs][cs])
16851685

1686-
def get_normals(polygons):
1687-
"""
1688-
Takes a list of polygons and return an array of their normals
1689-
"""
1690-
v1 = np.empty((len(polygons), 3))
1691-
v2 = np.empty((len(polygons), 3))
1692-
for poly_i, ps in enumerate(polygons):
1693-
# pick three points around the polygon at which to find the
1694-
# normal doesn't vectorize because polygons is jagged
1695-
i1, i2, i3 = 0, len(ps)//3, 2*len(ps)//3
1696-
v1[poly_i, :] = ps[i1, :] - ps[i2, :]
1697-
v2[poly_i, :] = ps[i2, :] - ps[i3, :]
1698-
return np.cross(v1, v2)
1699-
17001686
# note that the striding causes some polygons to have more coordinates
17011687
# than others
17021688
polyc = art3d.Poly3DCollection(polys, *args, **kwargs)
17031689

17041690
if fcolors is not None:
17051691
if shade:
17061692
colset = self._shade_colors(
1707-
colset, get_normals(polys), lightsource)
1693+
colset, self._generate_normals(polys), lightsource)
17081694
polyc.set_facecolors(colset)
17091695
polyc.set_edgecolors(colset)
17101696
elif cmap:
@@ -1718,7 +1704,7 @@ def get_normals(polygons):
17181704
else:
17191705
if shade:
17201706
colset = self._shade_colors(
1721-
color, get_normals(polys), lightsource)
1707+
color, self._generate_normals(polys), lightsource)
17221708
else:
17231709
colset = color
17241710
polyc.set_facecolors(colset)
@@ -1729,21 +1715,48 @@ def get_normals(polygons):
17291715
return polyc
17301716

17311717
def _generate_normals(self, polygons):
1732-
'''
1733-
Generate normals for polygons by using the first three points.
1734-
This normal of course might not make sense for polygons with
1735-
more than three points not lying in a plane.
1718+
"""
1719+
Takes a list of polygons and return an array of their normals.
17361720
17371721
Normals point towards the viewer for a face with its vertices in
17381722
counterclockwise order, following the right hand rule.
1739-
'''
17401723
1741-
normals = []
1742-
for verts in polygons:
1743-
v1 = np.array(verts[1]) - np.array(verts[0])
1744-
v2 = np.array(verts[2]) - np.array(verts[0])
1745-
normals.append(np.cross(v1, v2))
1746-
return normals
1724+
Uses three points equally spaced around the polygon.
1725+
This normal of course might not make sense for polygons with more than
1726+
three points not lying in a plane, but it's a plausible and fast
1727+
approximation.
1728+
1729+
Parameters
1730+
----------
1731+
polygons: list of (M_i, 3) array_like, or (..., M, 3) array_like
1732+
A sequence of polygons to compute normals for, which can have
1733+
varying numbers of vertices. If the polygons all have the same
1734+
number of vertices and array is passed, then the operation will
1735+
be vectorized.
1736+
1737+
Returns
1738+
-------
1739+
normals: (..., 3) array_like
1740+
A normal vector estimated for the polygon.
1741+
1742+
"""
1743+
if isinstance(polygons, np.ndarray):
1744+
# optimization: polygons all have the same number of points, so can
1745+
# vectorize
1746+
n = polygons.shape[-2]
1747+
i1, i2, i3 = 0, n//3, 2*n//3
1748+
v1 = polygons[..., i1, :] - polygons[..., i2, :]
1749+
v2 = polygons[..., i2, :] - polygons[..., i3, :]
1750+
else:
1751+
# The subtraction doesn't vectorize because polygons is jagged.
1752+
v1 = np.empty((len(polygons), 3))
1753+
v2 = np.empty((len(polygons), 3))
1754+
for poly_i, ps in enumerate(polygons):
1755+
n = len(ps)
1756+
i1, i2, i3 = 0, n//3, 2*n//3
1757+
v1[poly_i, :] = ps[i1, :] - ps[i2, :]
1758+
v2[poly_i, :] = ps[i2, :] - ps[i3, :]
1759+
return np.cross(v1, v2)
17471760

17481761
def _shade_colors(self, color, normals, lightsource=None):
17491762
'''
@@ -1990,9 +2003,7 @@ def plot_trisurf(self, *args, color=None, norm=None, vmin=None, vmax=None,
19902003
polyc.set_norm(norm)
19912004
else:
19922005
if shade:
1993-
v1 = verts[:, 0, :] - verts[:, 1, :]
1994-
v2 = verts[:, 1, :] - verts[:, 2, :]
1995-
normals = np.cross(v1, v2)
2006+
normals = self._generate_normals(verts)
19962007
colset = self._shade_colors(color, normals, lightsource)
19972008
else:
19982009
colset = color
@@ -2039,9 +2050,9 @@ def _3d_extend_contour(self, cset, stride=5):
20392050
botverts[0][i2],
20402051
botverts[0][i1]])
20412052

2042-
v1 = np.array(topverts[0][i1]) - np.array(topverts[0][i2])
2043-
v2 = np.array(topverts[0][i1]) - np.array(botverts[0][i1])
2044-
normals.append(np.cross(v1, v2))
2053+
# all polygons have 4 vertices, so vectorize
2054+
polyverts = np.array(polyverts)
2055+
normals = self._generate_normals(polyverts)
20452056

20462057
colors = self._shade_colors(color, normals)
20472058
colors2 = self._shade_colors(color, normals)

0 commit comments

Comments
 (0)
0