src/geometry.cpp

Mon, 20 Jun 2022 17:27:30 +0300

author
Teemu Piippo <teemu.s.piippo@gmail.com>
date
Mon, 20 Jun 2022 17:27:30 +0300
changeset 235
7ef03c2b46ab
parent 223
ce81db996275
child 250
2837b549e616
permissions
-rw-r--r--

Add a basic message log

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>
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
2 #include "geometry.h"
206
654661eab7f3 More refactor, merged main.h, basics.h and utility.h into one header file basics.h and removed plenty of unused code
Teemu Piippo <teemu@hecknology.net>
parents: 201
diff changeset
3 #include "basics.h"
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
4 #include "ring.h"
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
5
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
6 /**
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
7 * @brief Computes line-plane intersection
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
8 * @param line
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
9 * @param plane
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
10 * @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
11 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
12 std::optional<glm::vec3> linePlaneIntersection(
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
13 const Line<3>& line,
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
14 const Plane& plane,
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
15 const float epsilon)
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
16 {
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
17 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
18 if (std::abs(denominator) < epsilon)
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
19 {
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
20 return {};
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
21 }
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
22 else
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
23 {
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
24 const float d = glm::dot(plane.anchor - line.anchor, plane.normal) / denominator;
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
25 return line.anchor + d * line.direction;
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 /**
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
30 * @brief Computes the plane of a triangle
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
31 * @param triangle
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
32 * @return plane
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
33 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
34 Plane planeFromTriangle(const Triangle& triangle)
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
35 {
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
36 return Plane{normalVector(triangle), triangle.p1};
55
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 /**
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
40 * @brief Computes the normal vector of a triangle
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
41 * @param triangle
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
42 * @return normal vector
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
43 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
44 glm::vec3 normalVector(const Triangle& triangle)
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
45 {
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
46 return glm::normalize(
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
47 glm::cross(
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 187
diff changeset
48 triangle.p2 - triangle.p1,
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 187
diff changeset
49 triangle.p3 - triangle.p1));
55
cb81ecb5fb23 grid stuff
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
50 }
64
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 /**
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
53 * @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
54 * 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
55 * @param matrix Matrix to compute
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
56 * @return scaling vector and unscaled matrix
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
57 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
58 ScalingExtract extractScaling(const glm::mat4& matrix)
64
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
59 {
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
60 ScalingExtract result;
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
61 result.scaling = scalingVector(matrix);
64
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
62 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
63 return result;
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 /**
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
67 * @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
68 * @param matrix
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
69 * @return scaling vector
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
70 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
71 glm::vec3 scalingVector(const glm::mat4 matrix)
64
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
72 {
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
73 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
74 {
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
75 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
76 };
f99d52b1646b grid snapping now also works with transformed grids
Teemu Piippo <teemu@hecknology.net>
parents: 58
diff changeset
77 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
78 }
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
79
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
80 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
81 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
82 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
83 constexpr float epsilon = 1e-6f;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
84 if (std::abs(denominator) < epsilon)
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
85 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
86 return {};
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
87 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
88 else
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
89 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
90 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
91 const glm::vec2& p2 = line_1.anchor;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
92 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
93 const glm::vec2& p4 = line_2.anchor;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
94 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
95 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
96 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
97 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
98 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
99 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
100 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
101 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
102 return glm::vec2{x / denominator, y / denominator};
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 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
105
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
106 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
107 {
115
ed884a2fb009 fix too long lines
Teemu Piippo <teemu@hecknology.net>
parents: 71
diff changeset
108 std::optional<glm::vec2> result = lineLineIntersection(
ed884a2fb009 fix too long lines
Teemu Piippo <teemu@hecknology.net>
parents: 71
diff changeset
109 rayToLine(ray),
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 187
diff changeset
110 lineFromPoints(line.p1, line.p2));
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
111 if (result.has_value())
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
112 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
113 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
114 if (d1 < 0)
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
115 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
116 result.reset();
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
117 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
118 else
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
119 {
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 187
diff changeset
120 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
121 if (d2 > 0)
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
122 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
123 result.reset();
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 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
127 return result;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
128 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
129
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
130 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
131 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
132 std::optional<glm::vec2> position;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
133 std::optional<PointOnRectagle> result;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
134 // Try top
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
135 position = rayLineSegmentIntersection(ray, top(rectangle));
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
136 if (position.has_value())
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
137 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
138 result = {*position, RectangleSide::Top};
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
139 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
140 else
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
141 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
142 // Try bottom
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
143 position = rayLineSegmentIntersection(ray, bottom(rectangle));
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
144 if (position.has_value())
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
145 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
146 result = {*position, RectangleSide::Bottom};
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
147 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
148 else
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
149 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
150 // Try left
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
151 position = rayLineSegmentIntersection(ray, left(rectangle));
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
152 if (position.has_value())
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
153 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
154 result = {*position, RectangleSide::Left};
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
155 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
156 else
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
157 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
158 // Try right
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
159 position = rayLineSegmentIntersection(ray, right(rectangle));
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
160 if (position.has_value())
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
161 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
162 result = {*position, RectangleSide::Right};
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 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
167 return result;
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
168 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
169
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
170 LineSegment2D top(const QRectF& rectangle)
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
171 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
172 return {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
173 glm::vec2{rectangle.left(), rectangle.top()},
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
174 glm::vec2{rectangle.right(), rectangle.top()}
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 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
177
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
178 LineSegment2D bottom(const QRectF& rectangle)
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
179 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
180 return {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
181 glm::vec2{rectangle.left(), rectangle.bottom()},
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
182 glm::vec2{rectangle.right(), rectangle.bottom()}
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 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
185
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
186 LineSegment2D left(const QRectF& rectangle)
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
187 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
188 return {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
189 glm::vec2{rectangle.left(), rectangle.top()},
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
190 glm::vec2{rectangle.left(), rectangle.bottom()}
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 }
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
193
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
194 LineSegment2D right(const QRectF& rectangle)
71
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
195 {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
196 return {
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
197 glm::vec2{rectangle.right(), rectangle.top()},
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
198 glm::vec2{rectangle.right(), rectangle.bottom()}
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
199 };
198d25fe4e21 show axis directions on the screen
Teemu Piippo <teemu@hecknology.net>
parents: 64
diff changeset
200 }
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
201
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 bool isConvex(const Quadrilateral& quad)
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
203 {
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
204 glm::vec3 crosses[4] = {
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
205 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
206 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
207 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
208 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
209 };
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
210 return not std::any_of(
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
211 &crosses[1],
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
212 &crosses[4],
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
213 [&crosses](const glm::vec3& vector) {
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
214 return glm::dot(crosses[0], vector) < 1e-6;
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
215 });
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
216 }
ce81db996275 Use Mapbox's ear clipping algorithm to handle drawing any simple polygon
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 206
diff changeset
217
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
218 bool isConvex(const std::vector<glm::vec3>& polygon)
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
219 {
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
220 const int n = polygon.size();
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
221 auto polygonRing = iter::ring(polygon, n);
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
222 std::vector<glm::vec3> crosses;
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
223 crosses.resize(n);
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
224 for (int i = 0; i < n; i += 1)
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
225 {
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
226 crosses[i] = glm::cross(polygonRing[i - 1] - polygonRing[i], polygonRing[i + 1] - polygonRing[i]);
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
227 }
123
e3fe3617b631 refactor
Teemu Piippo <teemu@hecknology.net>
parents: 122
diff changeset
228 return not std::any_of(
e3fe3617b631 refactor
Teemu Piippo <teemu@hecknology.net>
parents: 122
diff changeset
229 crosses.begin() + 1,
e3fe3617b631 refactor
Teemu Piippo <teemu@hecknology.net>
parents: 122
diff changeset
230 crosses.end(),
e3fe3617b631 refactor
Teemu Piippo <teemu@hecknology.net>
parents: 122
diff changeset
231 [&crosses](const glm::vec3& vector)
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
232 {
123
e3fe3617b631 refactor
Teemu Piippo <teemu@hecknology.net>
parents: 122
diff changeset
233 return glm::dot(crosses[0], vector) < 1e-6;
e3fe3617b631 refactor
Teemu Piippo <teemu@hecknology.net>
parents: 122
diff changeset
234 });
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
235 }
168
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
236
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
237 /**
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
238 * @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
239 * @param polygon
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
240 * @return winding
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
241 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
242 Winding 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
243 {
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
244 // 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
245 double sum = 0.0;
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
246 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
247 {
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
248 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
249 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
250 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
251 }
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
252 return (sum < 0) ? Winding::Anticlockwise : Winding::Clockwise;
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
253 }
187
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
254
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
255 /**
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
256 * @brief computes the point on a Bezier curve
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
257 * @param curve
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
258 * @param t scalar between 0 and 1, with t=0 being P0 and t=1 being P3
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
259 * @return point on curve
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
260 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
261 glm::vec3 pointOnCurve(const BezierCurve &curve, float t)
187
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
262 {
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
263 // clamp t as rounding errors might make it slightly out of bounds
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
264 t = std::clamp(t, 0.0f, 1.0f);
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
265 const float t_2 = t * t;
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
266 const float t_3 = t * t * t;
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
267 const float coeffs[3] = {
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
268 -1*t_3 +3*t_2 -3*t +1,
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
269 +3*t_3 -6*t_2 +3*t,
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
270 -3*t_3 +3*t_2,
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
271 };
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
272 return coeffs[0] * curve[0] + coeffs[1] * curve[1] + coeffs[2] * curve[2] + t_3 * curve[3];
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
273 }
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
274
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
275 /**
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
276 * @brief computes the derivative of a point on a Bezier curve
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
277 * @param curve
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
278 * @param t scalar between 0 and 1, with t=0 being P0 and t=1 being P3
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
279 * @return point on curve
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
280 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
281 glm::vec3 derivativeOnCurve(const BezierCurve &curve, float t)
187
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
282 {
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
283 // clamp t as rounding errors might make it slightly out of bounds
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
284 t = std::clamp(t, 0.0f, 1.0f);
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
285 const float t_2 = t * t;
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
286 const float coeffs[4] = {
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
287 -3*t_2 + 6*t -3,
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
288 +9*t_2 -12*t +3,
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
289 -9*t_2 + 6*t,
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
290 +3*t_2
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
291 };
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
292 return coeffs[0] * curve[0] + coeffs[1] * curve[1] + coeffs[2] * curve[2] + coeffs[3] * curve[3];
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
293 }

mercurial