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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
#ifndef __MESH_H__
#define __MESH_H__
#include "intersect.h"
#include "geometry.h"
#define STACK_SIZE 500
/* Tests the intersection between a ray and a node in the bounding volume
hierarchy. If the ray intersects the bounding volume and `min_distance`
is less than zero or the distance from `origin` to the intersection is
less than `min_distance`, return true, else return false. */
__device__ bool
intersect_node(const float3 &origin, const float3 &direction,
Geometry *geometry, const int &i, const float &min_distance)
{
/* assigning these to local variables is faster for some reason */
float3 lower_bound = geometry->lower_bounds[i];
float3 upper_bound = geometry->upper_bounds[i];
float distance_to_box;
if (intersect_box(origin, direction, lower_bound, upper_bound,
distance_to_box)) {
if (min_distance < 0.0f)
return true;
if (distance_to_box > min_distance)
return false;
return true;
}
else {
return false;
}
}
/* Finds the intersection between a ray and `geometry`. If the ray does
intersect the mesh and the index of the intersected triangle is not equal
to `last_hit_triangle`, set `min_distance` to the distance from `origin` to
the intersection and return the index of the triangle which the ray
intersected, else return -1. */
__device__ int
intersect_mesh(const float3 &origin, const float3& direction,
Geometry *geometry, float &min_distance,
int last_hit_triangle = -1)
{
int triangle_index = -1;
float distance;
min_distance = -1.0f;
if (!intersect_node(origin, direction, geometry, geometry->start_node,
min_distance))
return -1;
unsigned int stack[STACK_SIZE];
unsigned int *head = &stack[0];
unsigned int *node = &stack[1];
unsigned int *tail = &stack[STACK_SIZE-1];
*node = geometry->start_node;
unsigned int i;
do
{
unsigned int first_child = geometry->node_map[*node];
unsigned int stop = geometry->node_map_end[*node];
while (*node >= geometry->first_node && stop == first_child+1) {
*node = first_child;
first_child = geometry->node_map[*node];
stop = geometry->node_map_end[*node];
}
if (*node >= geometry->first_node) {
for (i=first_child; i < stop; i++) {
if (intersect_node(origin, direction, geometry, i,
min_distance)) {
*node = i;
node++;
}
}
node--;
}
else {
// node is a leaf
for (i=first_child; i < stop; i++) {
if (last_hit_triangle == i)
continue;
Triangle triangle = get_triangle(geometry, i);
if (intersect_triangle(origin, direction, triangle,
distance)) {
if (triangle_index == -1) {
triangle_index = i;
min_distance = distance;
continue;
}
if (distance < min_distance) {
triangle_index = i;
min_distance = distance;
}
}
} // triangle loop
node--;
} // node is a leaf
} // while loop
while (node != head);
return triangle_index;
}
extern "C"
{
__global__ void
distance_to_mesh(int nthreads, float3 *positions, float3 *directions,
Geometry *g, float *distances)
{
int id = blockIdx.x*blockDim.x + threadIdx.x;
if (id >= nthreads)
return;
float3 position = positions[id];
float3 direction = directions[id];
direction /= norm(direction);
float distance;
int triangle_index = intersect_mesh(position, direction, g, distance);
if (triangle_index == -1)
distances[id] = 1e9;
else
distances[id] = distance;
}
__global__ void
color_solids(int first_triangle, int nthreads, int *solid_id_map,
bool *solid_hit, unsigned int *solid_colors, Geometry *geometry)
{
int id = blockIdx.x*blockDim.x + threadIdx.x;
if (id >= nthreads)
return;
int triangle_id = first_triangle + id;
int solid_id = solid_id_map[triangle_id];
if (solid_hit[solid_id])
geometry->colors[triangle_id] = solid_colors[solid_id];
}
} // extern "C"
#endif
|
