src/geometry.cpp

Tue, 11 Apr 2023 20:27:04 +0300

author
Teemu Piippo <teemu.s.piippo@gmail.com>
date
Tue, 11 Apr 2023 20:27:04 +0300
changeset 375
21a5ecbe34e4
parent 373
e34d6a30b96d
permissions
-rw-r--r--

Simplify signature of updateRenderPreferences

64
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
1 #include <glm/gtc/matrix_transform.hpp>
264
76a025db4948 Convert all includes to be relative to project root directory. Files that cannot be found in this manner use angle brackets.
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 250
diff changeset
2 #include "src/geometry.h"
76a025db4948 Convert all includes to be relative to project root directory. Files that cannot be found in this manner use angle brackets.
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 250
diff changeset
3 #include "src/basics.h"
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
4
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
5 /**
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
6 * @brief Computes line-plane intersection
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
7 * @param line
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
8 * @param plane
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
9 * @return point of intersection. Does not return a value if the line is in parallel to the plane.
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
10 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
11 std::optional<glm::vec3> linePlaneIntersection(
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
12 const Line<3>& line,
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
13 const Plane& plane,
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
14 const float epsilon)
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
15 {
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
16 const float denominator = glm::dot(line.direction, plane.normal);
58
b7841cd31fb7 use glm::project instead of figuring out the conversion manually...
Teemu Piippo <teemu@hecknology.net>
parents: 55
diff changeset
17 if (std::abs(denominator) < epsilon)
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
18 {
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
19 return {};
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
20 }
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
21 else
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
22 {
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
23 const float d = glm::dot(plane.anchor - line.anchor, plane.normal) / denominator;
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
24 return line.anchor + d * line.direction;
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
25 }
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
26 }
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
27
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
28 /**
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
29 * @brief Computes the plane of a triangle
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
30 * @param triangle
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
31 * @return plane
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
32 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
33 Plane planeFromTriangle(const Triangle& triangle)
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
34 {
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
35 return Plane{normalVector(triangle), triangle.p1};
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
36 }
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
37
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
38 /**
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
39 * @brief Computes the normal vector of a triangle
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
40 * @param triangle
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
41 * @return normal vector
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
42 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
43 glm::vec3 normalVector(const Triangle& triangle)
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
44 {
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
45 return glm::normalize(
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
46 glm::cross(
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 187
diff changeset
47 triangle.p2 - triangle.p1,
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 187
diff changeset
48 triangle.p3 - triangle.p1));
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
49 }
64
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
50
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
51 /**
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
52 * @brief Extracts the scaling component of the specified matrix into a vector and returns both the scaling
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
53 * components as well as the unscaled matrix.
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
54 * @param matrix Matrix to compute
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
55 * @return scaling vector and unscaled matrix
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
56 */
371
171d3f9638a9 rename some functions
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 369
diff changeset
57 unscaled_matrix unscale_matrix(const glm::mat4& matrix)
64
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
58 {
371
171d3f9638a9 rename some functions
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 369
diff changeset
59 unscaled_matrix result;
171d3f9638a9 rename some functions
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 369
diff changeset
60 result.scaling = calculate_matrix_scaling(matrix);
64
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
61 result.unscaled = glm::scale(matrix, 1.0f / result.scaling);
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
62 return result;
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
63 }
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
64
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
65 /**
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
66 * @brief Computes the scaling vector, which contains the scaling of the specified matrix
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
67 * @param matrix
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
68 * @return scaling vector
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
69 */
371
171d3f9638a9 rename some functions
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 369
diff changeset
70 glm::vec3 calculate_matrix_scaling(const glm::mat4 matrix)
64
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
71 {
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
72 auto component = [](const glm::mat4& matrix, const int i) -> float
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
73 {
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
74 return std::hypot(std::hypot(matrix[i][0], matrix[i][1]), matrix[i][2]);
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
75 };
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
76 return glm::vec3{component(matrix, 0), component(matrix, 1), component(matrix, 2)};
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
77 }
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
78
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
79 std::optional<glm::vec2> lineLineIntersection(const Line<2>& line_1, const Line<2>& line_2)
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
80 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
81 const float denominator = (line_1.direction.x * line_2.direction.y) - (line_1.direction.y * line_2.direction.x);
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
82 constexpr float epsilon = 1e-6f;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
83 if (std::abs(denominator) < epsilon)
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
84 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
85 return {};
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
86 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
87 else
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
88 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
89 const glm::vec2 p1 = line_1.anchor + line_1.direction;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
90 const glm::vec2& p2 = line_1.anchor;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
91 const glm::vec2 p3 = line_2.anchor + line_2.direction;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
92 const glm::vec2& p4 = line_2.anchor;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
93 const float a = glm::determinant(glm::mat2{{p1.x, p2.x}, {p1.y, p2.y}});
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
94 const float b = glm::determinant(glm::mat2{{p3.x, p4.x}, {p3.y, p4.y}});
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
95 const float c_x = glm::determinant(glm::mat2{{p1.x, p2.x}, {1, 1}});
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
96 const float c_y = glm::determinant(glm::mat2{{p1.y, p2.y}, {1, 1}});
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
97 const float d_x = glm::determinant(glm::mat2{{p3.x, p4.x}, {1, 1}});
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
98 const float d_y = glm::determinant(glm::mat2{{p3.y, p4.y}, {1, 1}});
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
99 const float x = glm::determinant(glm::mat2{{a, b}, {c_x, d_x}});
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
100 const float y = glm::determinant(glm::mat2{{a, b}, {c_y, d_y}});
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
101 return glm::vec2{x / denominator, y / denominator};
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
102 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
103 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
104
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
105 std::optional<glm::vec2> rayLineSegmentIntersection(const Ray<2>& ray, const LineSegment2D& line)
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
106 {
115
ed884a2fb009 fix too long lines
Teemu Piippo <teemu@hecknology.net>
parents: 71
diff changeset
107 std::optional<glm::vec2> result = lineLineIntersection(
ed884a2fb009 fix too long lines
Teemu Piippo <teemu@hecknology.net>
parents: 71
diff changeset
108 rayToLine(ray),
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 187
diff changeset
109 lineFromPoints(line.p1, line.p2));
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
110 if (result.has_value())
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
111 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
112 const float d1 = glm::dot(*result - ray.anchor, ray.direction);
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
113 if (d1 < 0)
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
114 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
115 result.reset();
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
116 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
117 else
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
118 {
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 187
diff changeset
119 const float d2 = glm::dot(*result - line.p1, *result - line.p2);
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
120 if (d2 > 0)
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
121 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
122 result.reset();
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
123 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
124 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
125 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
126 return result;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
127 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
128
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
129 std::optional<PointOnRectagle> rayRectangleIntersection(const Ray<2>& ray, const QRectF& rectangle)
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
130 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
131 std::optional<glm::vec2> position;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
132 std::optional<PointOnRectagle> result;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
133 // Try top
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
134 position = rayLineSegmentIntersection(ray, top(rectangle));
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
135 if (position.has_value())
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
136 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
137 result = {*position, RectangleSide::Top};
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
138 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
139 else
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
140 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
141 // Try bottom
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
142 position = rayLineSegmentIntersection(ray, bottom(rectangle));
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
143 if (position.has_value())
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
144 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
145 result = {*position, RectangleSide::Bottom};
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
146 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
147 else
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
148 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
149 // Try left
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
150 position = rayLineSegmentIntersection(ray, left(rectangle));
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
151 if (position.has_value())
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
152 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
153 result = {*position, RectangleSide::Left};
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
154 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
155 else
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
156 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
157 // Try right
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
158 position = rayLineSegmentIntersection(ray, right(rectangle));
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
159 if (position.has_value())
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
160 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
161 result = {*position, RectangleSide::Right};
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
162 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
163 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
164 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
165 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
166 return result;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
167 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
168
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
169 LineSegment2D top(const QRectF& rectangle)
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
170 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
171 return {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
172 glm::vec2{rectangle.left(), rectangle.top()},
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
173 glm::vec2{rectangle.right(), rectangle.top()}
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
174 };
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
175 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
176
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
177 LineSegment2D bottom(const QRectF& rectangle)
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
178 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
179 return {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
180 glm::vec2{rectangle.left(), rectangle.bottom()},
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
181 glm::vec2{rectangle.right(), rectangle.bottom()}
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
182 };
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
183 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
184
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
185 LineSegment2D left(const QRectF& rectangle)
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
186 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
187 return {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
188 glm::vec2{rectangle.left(), rectangle.top()},
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
189 glm::vec2{rectangle.left(), rectangle.bottom()}
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
190 };
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
191 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
192
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
193 LineSegment2D right(const QRectF& rectangle)
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
194 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
195 return {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
196 glm::vec2{rectangle.right(), rectangle.top()},
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
197 glm::vec2{rectangle.right(), rectangle.bottom()}
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
198 };
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
199 }
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
200
369
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
201 static convexity_e determine_convexity(const glm::vec3* begin, const glm::vec3* end)
223
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
202 {
369
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
203 auto test_concave_dot_product = [begin](const glm::vec3& vector) {
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
204 return glm::dot(*begin, vector) < 1e-6;
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
205 };
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
206 if (std::any_of(begin + 1, end, test_concave_dot_product))
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
207 {
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
208 return convexity_e::concave;
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
209 }
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
210 else
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
211 {
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
212 return convexity_e::convex;
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
213 }
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
214 }
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
215
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
216 convexity_e quadrilateral_convexity(const Quadrilateral& quad)
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
217 {
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
218 const glm::vec3 crosses[4] = {
223
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
219 glm::cross(quad.p4 - quad.p1, quad.p2 - quad.p1),
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
220 glm::cross(quad.p1 - quad.p2, quad.p3 - quad.p2),
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
221 glm::cross(quad.p2 - quad.p3, quad.p4 - quad.p3),
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
222 glm::cross(quad.p3 - quad.p4, quad.p1 - quad.p4),
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
223 };
369
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
224 return determine_convexity(&crosses[0], &crosses[4]);
223
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
225 }
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
226
369
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
227 convexity_e polygon_convexity(const std::vector<glm::vec3>& polygon)
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
228 {
250
2837b549e616 I felt that the compiler was too kind to me, so I enabled a big pile of warnings
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 223
diff changeset
229 const std::size_t n = polygon.size();
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
230 std::vector<glm::vec3> crosses;
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
231 crosses.resize(n);
250
2837b549e616 I felt that the compiler was too kind to me, so I enabled a big pile of warnings
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 223
diff changeset
232 for (std::size_t i = 0; i < n; i += 1)
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
233 {
297
bc92f97498f7 Remove ring.h
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 264
diff changeset
234 const glm::vec3 v1 = polygon[(i + n - 1) % n];
bc92f97498f7 Remove ring.h
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 264
diff changeset
235 const glm::vec3 v2 = polygon[i];
bc92f97498f7 Remove ring.h
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 264
diff changeset
236 const glm::vec3 v3 = polygon[(i + 1) % n];
bc92f97498f7 Remove ring.h
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 264
diff changeset
237 crosses[i] = glm::cross(v1 - v2, v3 - v2);
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
238 }
369
57de8fab2237 isConvex renamed to quadrilateral_convexity, refactor, now returns an enum instead of bool
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 297
diff changeset
239 return determine_convexity(&crosses[0], &crosses[n]);
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
240 }
168
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
241
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
242 /**
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
243 * @brief Determines the winding of a 2d polygon
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
244 * @param polygon
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
245 * @return winding
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
246 */
372
b2914aaeec1a Winding is now an enum class winding_e
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 371
diff changeset
247 winding_e calculate_polygon_winding(const QPolygonF &polygon)
168
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
248 {
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
249 // based on https://stackoverflow.com/a/1165943
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
250 double sum = 0.0;
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
251 for (int i = 0; i < polygon.size(); i += 1)
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
252 {
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
253 const QPointF& p1 = polygon[i];
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
254 const QPointF& p2 = polygon[(i + 1) % polygon.size()];
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
255 sum += (p2.x() - p1.x()) * (p2.y() + p1.y());
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
256 }
372
b2914aaeec1a Winding is now an enum class winding_e
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 371
diff changeset
257 return (sum < 0) ? winding_e::anticlockwise : winding_e::clockwise;
168
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
258 }

mercurial