MAINT: Unify calculation of normal vectors from polygons#12136
MAINT: Unify calculation of normal vectors from polygons#12136timhoffm merged 2 commits intomatplotlib:masterfrom
Conversation
|
Branch name hints that my goal here is to add shading to |
|
An alternate implementation with less duplication, but with less clarity, could look like: def _inplane_vectors(polygons, v1_out=None, v2_out=None):
n = polygons.shape[-2]
i1, i2, i3 = 0, n//3, 2*n//3
v1 = np.subtract(ps[..., i1, :], ps[..., i2, :], out=v1_out)
v2 = np.subtract(ps[..., i2, :], ps[..., i3, :], out=v2_out)
return v1, v2
if isinstance(polygons, np.ndarray):
# optimization: polygons all have the same number of points, so can
# vectorize
v1, v2 = _inplane_vectors(polygons)
else:
# The subtraction doesn't vectorize because polygons is jagged.
v1 = np.empty((len(polygons), 3))
v2 = np.empty((len(polygons), 3))
for poly_i, ps in enumerate(polygons):
_inplane_vectors(ps, v1_out=v1[poly_i, :], v2_out=v2[poly_i, :])
return np.cross(v1, v2)Let me know which is preferable |
50d898c to
a141762
Compare
a141762 to
dc75f7d
Compare
|
This fails because it changes the sense of the polygons. It seems that some functions use a right-hand-rule for the "front" face of a polygon, while others use a left-hand rule. Related: #12138 |
|
Just to give an update - this is now waiting on #12259 |
dc75f7d to
67fc7c1
Compare
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)
```
67fc7c1 to
5e6e837
Compare
|
Rebased and ready to go |
timhoffm
left a comment
There was a problem hiding this comment.
Looks good otherwise. Please rebase.
|
|
||
| Parameters | ||
| ---------- | ||
| polygons: list of (M_i, 3) array_like, or (..., M, 3) array_like |
There was a problem hiding this comment.
Because the value of M can change between each list item - polygons[0] has shape (M_0, 3), polygons[1] has shape (M_1, 3), and it is likely that M_1 != M_0
|
@timhoffm: merged using the web UI, since it was doc-only. Feel free to squash to elide the merge commit |
| n = polygons.shape[-2] | ||
| i1, i2, i3 = 0, n//3, 2*n//3 | ||
| v1 = polygons[..., i1, :] - polygons[..., i2, :] | ||
| v2 = polygons[..., i2, :] - polygons[..., i3, :] |
There was a problem hiding this comment.
Is there the sign change here intended? This is the convention of get_normals. _generate_normals had it the other way round. I know that there have been some orientation issues. But I don‘t know the state. Just want to make sure the sign change is notbslipping in unintendedly.
There was a problem hiding this comment.
Sign change is only in v1 and v2, it cancels out in the cross product, so it doesn't affect the return value.
I picked the convention from get_normals because that was easiest. If you want me to flip both subtractions here, I can, but it won't make any difference.
…12136) 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) ```
* upstream/master: (1723 commits) Correctly get weight & style hints from certain newer Microsoft fonts (matplotlib#12945) Remove some checks for Py<3.6 in the test suite. (matplotlib#12974) Fail-fast when trying to run tests with too-old pytest. Include scatter plots in Qt figure options editor. (matplotlib#12779) ENH: replace deprecated numpy header Minor simplifications. tickminorvisible-fix (matplotlib#12938) Remove animated=True from animation docs Update the documentation of Cursor Misc. cleanups. Add test for 3d conversion of empty PolyCollection Support ~ as nonbreaking space in mathtext. Deprecate public use of Formatter.pprint_val. MAINT: Unify calculation of normal vectors from polygons (matplotlib#12136) Fix the title of testing_api More table documentation Simplify bachelors degree example using new features. Avoid pyplot in showcase examples. Simplify argument checking in Table.__getitem__. (matplotlib#12932) Minor updates following bump to Py3.6+. ... # Conflicts: # lib/matplotlib/widgets.py
This combines
get_normalsand_generate_normals, and eliminates all other calls to np.cross. This came up in #9990, but I wanted to postpone it to (this) later PR.get_normalsand_generate_normalswere profiled, and it was found that vectorizingnp.crosslike inget_normalswas faster:PR Checklist
Do not apply, since this is just a refactor: