src/geometry.cpp

Wed, 29 Jun 2022 14:11:58 +0300

author
Teemu Piippo <teemu.s.piippo@gmail.com>
date
Wed, 29 Jun 2022 14:11:58 +0300
changeset 305
d891da20abca
parent 297
bc92f97498f7
child 369
57de8fab2237
permissions
-rw-r--r--

Add support for BFC CERTIFY statements

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 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
57 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
58 {
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
59 ScalingExtract result;
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
60 result.scaling = scalingVector(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 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
70 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
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
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
201 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
202 {
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 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
204 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
205 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
206 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
207 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
208 };
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 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
210 &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
211 &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
212 [&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
213 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
214 });
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
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
217 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
218 {
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
219 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
220 std::vector<glm::vec3> crosses;
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
221 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
222 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
223 {
297
bc92f97498f7 Remove ring.h
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 264
diff changeset
224 const glm::vec3 v1 = polygon[(i + n - 1) % n];
bc92f97498f7 Remove ring.h
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 264
diff changeset
225 const glm::vec3 v2 = polygon[i];
bc92f97498f7 Remove ring.h
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 264
diff changeset
226 const glm::vec3 v3 = polygon[(i + 1) % n];
bc92f97498f7 Remove ring.h
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 264
diff changeset
227 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
228 }
123
e3fe3617b631 refactor
Teemu Piippo <teemu@hecknology.net>
parents: 122
diff changeset
229 return not std::any_of(
e3fe3617b631 refactor
Teemu Piippo <teemu@hecknology.net>
parents: 122
diff changeset
230 crosses.begin() + 1,
e3fe3617b631 refactor
Teemu Piippo <teemu@hecknology.net>
parents: 122
diff changeset
231 crosses.end(),
e3fe3617b631 refactor
Teemu Piippo <teemu@hecknology.net>
parents: 122
diff changeset
232 [&crosses](const glm::vec3& vector)
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
233 {
123
e3fe3617b631 refactor
Teemu Piippo <teemu@hecknology.net>
parents: 122
diff changeset
234 return glm::dot(crosses[0], vector) < 1e-6;
e3fe3617b631 refactor
Teemu Piippo <teemu@hecknology.net>
parents: 122
diff changeset
235 });
122
b54b350dff5d Show concave polygons as red while drawing
Teemu Piippo <teemu@hecknology.net>
parents: 115
diff changeset
236 }
168
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 /**
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
239 * @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
240 * @param polygon
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
241 * @return winding
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
242 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
243 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
244 {
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
245 // 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
246 double sum = 0.0;
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
247 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
248 {
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
249 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
250 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
251 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
252 }
24590af32ad6 Draw tool now renders the winding of the new polygon
Teemu Piippo <teemu@hecknology.net>
parents: 123
diff changeset
253 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
254 }
187
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 /**
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
257 * @brief computes the point on a Bezier curve
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
258 * @param curve
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
259 * @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
260 * @return point on curve
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
261 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
262 glm::vec3 pointOnCurve(const BezierCurve &curve, float t)
187
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
263 {
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
264 // 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
265 t = std::clamp(t, 0.0f, 1.0f);
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
266 const float t_2 = t * t;
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
267 const float t_3 = t * t * t;
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
268 const float coeffs[3] = {
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
269 -1*t_3 +3*t_2 -3*t +1,
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
270 +3*t_3 -6*t_2 +3*t,
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
271 -3*t_3 +3*t_2,
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
272 };
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
273 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
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 /**
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
277 * @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
278 * @param curve
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
279 * @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
280 * @return point on curve
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
281 */
201
5d201ee4a9c3 Continue giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 200
diff changeset
282 glm::vec3 derivativeOnCurve(const BezierCurve &curve, float t)
187
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
283 {
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
284 // 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
285 t = std::clamp(t, 0.0f, 1.0f);
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
286 const float t_2 = t * t;
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
287 const float coeffs[4] = {
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
288 -3*t_2 + 6*t -3,
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
289 +9*t_2 -12*t +3,
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
290 -9*t_2 + 6*t,
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
291 +3*t_2
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
292 };
30204975694a work on circle tool
Teemu Piippo <teemu@hecknology.net>
parents: 168
diff changeset
293 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
294 }

mercurial