Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork8.1k
MAINT: Unify calculation of normal vectors from polygons#12136
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Uh oh!
There was an error while loading.Please reload this page.
Conversation
Uh oh!
There was an error while loading.Please reload this page.
eric-wieser commentedSep 16, 2018 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
Branch name hints that my goal here is to add shading to |
eric-wieser commentedSep 16, 2018
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//3v1=np.subtract(ps[...,i1, :],ps[...,i2, :],out=v1_out)v2=np.subtract(ps[...,i2, :],ps[...,i3, :],out=v2_out)returnv1,v2ifisinstance(polygons,np.ndarray):# optimization: polygons all have the same number of points, so can# vectorizev1,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))forpoly_i,psinenumerate(polygons):_inplane_vectors(ps,v1_out=v1[poly_i, :],v2_out=v2[poly_i, :])returnnp.cross(v1,v2) Let me know which is preferable |
50d898c toa141762Comparea141762 todc75f7dCompareeric-wieser commentedSep 17, 2018 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
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 |
eric-wieser commentedOct 31, 2018
Just to give an update - this is now waiting on#12259 |
dc75f7d to67fc7c1CompareThis 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:```pythonimport numpy as npdef 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 to5e6e837Compareeric-wieser commentedNov 11, 2018
Rebased and ready to go |
timhoffm left a comment
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
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.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Why the i index ?
eric-wieserNov 27, 2018 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
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 thatM_1 != M_0
eric-wieser commentedNov 27, 2018
@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.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
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.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Sign change is only inv1 andv2, it cancels out in the cross product, so it doesn't affect the return value.
I picked the convention fromget_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:```pythonimport numpy as npdef 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
Uh oh!
There was an error while loading.Please reload this page.
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: