-
Notifications
You must be signed in to change notification settings - Fork 8
/
query_ray.cpp
123 lines (101 loc) · 4.04 KB
/
query_ray.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include "csg_private.hpp"
#include <glm/gtx/intersect.hpp>
namespace csg {
static float signed_distance(const glm::vec3& point, const plane_t& plane) {
return glm::dot(plane.normal, point) + plane.offset;
}
static glm::vec3 projection_of_point_onto_plane(const glm::vec3& point,
const plane_t& plane)
{
return point - signed_distance(point, plane) * plane.normal;
}
static bool ray_intersects_box(const ray_t& ray,
const box_t& box,
const glm::vec3& one_over_ray_direction)
{
// branchless slab method
// https://tavianator.com/2015/ray_box_nan.html
float t1 = (box.min[0] - ray.origin[0])*one_over_ray_direction[0];
float t2 = (box.max[0] - ray.origin[0])*one_over_ray_direction[0];
float tmin = glm::min(t1, t2);
float tmax = glm::max(t1, t2);
for (int i = 1; i < 3; ++i) {
t1 = (box.min[i] - ray.origin[i])*one_over_ray_direction[i];
t2 = (box.max[i] - ray.origin[i])*one_over_ray_direction[i];
tmin = glm::max(tmin, glm::min(t1, t2));
tmax = glm::min(tmax, glm::max(t1, t2));
}
return tmax > glm::max(tmin, 0.0f);
}
static bool ray_intersects_plane(const ray_t& ray,
const plane_t& plane,
float& t)
{
return glm::intersectRayPlane(
ray.origin,
ray.direction,
projection_of_point_onto_plane(glm::vec3(0,0,0), plane),
plane.normal,
t
);
}
static bool point_inside_convex_polygon(const glm::vec3& point,
const std::vector<vertex_t>& vertices)
{
int n = vertices.size();
if (n < 3)
return false;
glm::vec3 v0 = vertices[0].position;
glm::vec3 v1 = vertices[1].position;
glm::vec3 v2 = vertices[2].position;
glm::vec3 normal = glm::cross(v1-v0, v2-v0);
for (int i=0; i<n; ++i) {
int j = (i+1) % n;
glm::vec3 vi = vertices[i].position;
glm::vec3 vj = vertices[j].position;
// if (glm::dot(normal, glm::cross(vj-vi, point-vi)) < 0.0f)
static constexpr float epsilon = 0.001f;
if (glm::dot(normal, glm::cross(vj-vi, point-vi)) < -epsilon)
return false;
}
return true;
}
std::vector<ray_hit_t> world_t::query_ray(const ray_t& ray) {
glm::vec3 one_over_ray_direction = 1.0f / ray.direction;
std::vector<ray_hit_t> result;
brush_t *b = first();
while (b) {
if (ray_intersects_box(ray, b->box, one_over_ray_direction)) {
for (size_t iplane=0; iplane<b->planes.size(); ++iplane) {
float t;
if (ray_intersects_plane(ray, b->planes[iplane], t)) {
glm::vec3 intersection = ray.origin + t * ray.direction;
face_t& face = b->faces[iplane];
if (point_inside_convex_polygon(intersection,
face.vertices)) {
for (fragment_t& fragment: face.fragments) {
if (point_inside_convex_polygon(intersection,
face.vertices)) {
ray_hit_t ray_hit;
ray_hit.brush = b;
ray_hit.face = &face;
ray_hit.fragment = &fragment;
ray_hit.parameter = t;
ray_hit.position = intersection;
result.push_back(ray_hit);
}
}
}
}
}
}
b = next(b);
}
std::sort(result.begin(), result.end(),
[](const ray_hit_t& hit0, const ray_hit_t& hit1) {
return hit0.parameter < hit1.parameter;
}
);
return result;
}
}