Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(71)

Side by Side Diff: ui/gfx/geometry/quad_f.cc

Issue 458173002: Optimize QuadF's PointIsInTriangle function (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Created 6 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #include "ui/gfx/geometry/quad_f.h" 5 #include "ui/gfx/geometry/quad_f.h"
6 6
7 #include <limits> 7 #include <limits>
8 8
9 #include "base/strings/stringprintf.h" 9 #include "base/strings/stringprintf.h"
10 10
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after
55 double determinant4 = static_cast<double>(p4_.x()) * p1_.y() 55 double determinant4 = static_cast<double>(p4_.x()) * p1_.y()
56 - static_cast<double>(p1_.x()) * p4_.y(); 56 - static_cast<double>(p1_.x()) * p4_.y();
57 57
58 return determinant1 + determinant2 + determinant3 + determinant4 < 0; 58 return determinant1 + determinant2 + determinant3 + determinant4 < 0;
59 } 59 }
60 60
61 static inline bool PointIsInTriangle(const PointF& point, 61 static inline bool PointIsInTriangle(const PointF& point,
62 const PointF& r1, 62 const PointF& r1,
63 const PointF& r2, 63 const PointF& r2,
64 const PointF& r3) { 64 const PointF& r3) {
65 // Compute the barycentric coordinates (u, v, w) of |point| relative to the 65 // Translate point and triangle so that point lies at origin.
66 // triangle (r1, r2, r3) by the solving the system of equations: 66 // Then checking if the origin is contained in the translated triangle.
67 // 1) point = u * r1 + v * r2 + w * r3 67 // The origin O lies inside ABC if and only if the triangles OAB, OBC,
68 // 2) u + v + w = 1 68 // and OCA are all either clockwise or counterclockwise.
69 // This algorithm comes from Christer Ericson's Real-Time Collision Detection. 69 // This algorithm is from Real-Time Collision Detection (Chaper 5.4.2).
70 70
71 Vector2dF r31 = r1 - r3; 71 Vector2dF a = r1 - point;
72 Vector2dF r32 = r2 - r3; 72 Vector2dF b = r2 - point;
73 Vector2dF r3p = point - r3; 73 Vector2dF c = r3 - point;
74 74
75 float denom = r32.y() * r31.x() - r32.x() * r31.y(); 75 double u = CrossProduct(b, c);
76 float u = (r32.y() * r3p.x() - r32.x() * r3p.y()) / denom; 76 double v = CrossProduct(c, a);
77 float v = (r31.x() * r3p.y() - r31.y() * r3p.x()) / denom; 77 double w = CrossProduct(a, b);
78 float w = 1.f - u - v; 78 return ((u * v < 0) || ((u * w) < 0) || ((v * w) < 0)) ? false : true;
79
80 // Use the barycentric coordinates to test if |point| is inside the
81 // triangle (r1, r2, r2).
82 return (u >= 0) && (v >= 0) && (w >= 0);
83 } 79 }
84 80
85 bool QuadF::Contains(const PointF& point) const { 81 bool QuadF::Contains(const PointF& point) const {
86 return PointIsInTriangle(point, p1_, p2_, p3_) 82 return PointIsInTriangle(point, p1_, p2_, p3_)
87 || PointIsInTriangle(point, p1_, p3_, p4_); 83 || PointIsInTriangle(point, p1_, p3_, p4_);
88 } 84 }
89 85
90 void QuadF::Scale(float x_scale, float y_scale) { 86 void QuadF::Scale(float x_scale, float y_scale) {
91 p1_.Scale(x_scale, y_scale); 87 p1_.Scale(x_scale, y_scale);
92 p2_.Scale(x_scale, y_scale); 88 p2_.Scale(x_scale, y_scale);
(...skipping 21 matching lines...) Expand all
114 return result; 110 return result;
115 } 111 }
116 112
117 QuadF operator-(const QuadF& lhs, const Vector2dF& rhs) { 113 QuadF operator-(const QuadF& lhs, const Vector2dF& rhs) {
118 QuadF result = lhs; 114 QuadF result = lhs;
119 result -= rhs; 115 result -= rhs;
120 return result; 116 return result;
121 } 117 }
122 118
123 } // namespace gfx 119 } // namespace gfx
OLDNEW
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698