Issue 266063003: cubicline intersection binary search

Keyboard Shortcuts

	File
u :	up to issue
j / k :	jump to file after / before current file
J / K :	jump to next file with a comment after / before current file
	Side-by-side diff
i :	toggle intra-line diffs
e :	expand all comments
c :	collapse all comments
s :	toggle showing all comments
n / p :	next / previous diff chunk or comment
N / P :	next / previous comment
<Up> / <Down> :	next / previous line

	Issue
u :	up to list of issues
j / k :	jump to patch after / before current patch
o / <Enter> :	open current patch in side-by-side view
i :	open current patch in unified diff view

	Issue List
j / k :	jump to issue after / before current issue
o / <Enter> :	open current issue

Issue 266063003: cubicline intersection binary search (Closed)

Created:
6 years, 7 months ago by caryclark

Modified:
6 years, 7 months ago

Reviewers:

CC:
skia-review_googlegroups.com

Base URL:
https://skia.googlesource.com/skia.git@master

Visibility:
Public.

More Reviews

Description

When solving the cubic line intersection directly fails, use binary search as a fallback. The cubic line intersection math empirically works 99.99% of the time (fails 3100 out of 1B random tests) but when it fails, an intersection may be missed altogether. The binary search is may not find a solution if the cubic line failed to find any solutions at all, but so far that case hasn't arisen. BUG=skia:2504 TBR=reed@google.com Committed: http://code.google.com/p/skia/source/detail?r=14614

Patch Set 1 #

Patch Set 2 : cubic line intersection uses binary search when the direct solution fails #

Patch Set 3 : typing cleanup #

Created: 6 years, 7 months ago

Download [raw] [tar.bz2]

	Unified diffs	Side-by-side diffs	Delta from patch set	Stats (+538 lines, -37 lines)			Patch
M	gyp/pathops_unittest.gyp	View	1 2	1 chunk	+1 line, -0 lines	0 comments	Download
M	src/pathops/SkDCubicLineIntersection.cpp	View	1	5 chunks	+58 lines, -20 lines	0 comments	Download
M	src/pathops/SkPathOpsCubic.h	View	1	4 chunks	+22 lines, -12 lines	0 comments	Download
M	src/pathops/SkPathOpsCubic.cpp	View	1	3 chunks	+71 lines, -1 line	0 comments	Download
M	src/pathops/SkPathOpsDebug.h	View	1 2	2 chunks	+2 lines, -0 lines	0 comments	Download
M	src/pathops/SkPathOpsTypes.h	View	1	1 chunk	+1 line, -3 lines	0 comments	Download
M	src/pathops/SkPathOpsTypes.cpp	View	1	1 chunk	+7 lines, -0 lines	0 comments	Download
A	tests/PathOpsCubicLineIntersectionIdeas.cpp	View	1 2	1 chunk	+283 lines, -0 lines	0 comments	Download
M	tests/PathOpsCubicLineIntersectionTest.cpp	View	2	3 chunks	+34 lines, -1 line	0 comments	Download
M	tests/PathOpsOpTest.cpp	View		1 chunk	+20 lines, -0 lines	0 comments	Download
M	tools/pathops_sorter.htm	View	1	1 chunk	+39 lines, -0 lines	0 comments	Download

Messages

Total messages: 3 (0 generated)

Expand Messages | Collapse Messages

commit-bot: I haz the power

CQ is trying da patch. Follow status at https://skia-tree-status.appspot.com/cq/caryclark@google.com/266063003/40001

6 years, 7 months ago (2014-05-07 15:25:24 UTC) #2

Message was sent while issue was closed.

Change committed as 14614

Expand Messages | Collapse Messages