| 304 |
jab |
1 |
#pragma warning (disable: 4786)
|
|
|
2 |
// Created by Bent Dalgaard Larsen, Nov, 2003
|
|
|
3 |
|
|
|
4 |
#include "Ray.h"
|
|
|
5 |
#include "BBox.h"
|
|
|
6 |
|
|
|
7 |
using namespace std;
|
|
|
8 |
using namespace CGLA;
|
|
|
9 |
|
|
|
10 |
#define my_min(x,y) (x<y?x:y)
|
|
|
11 |
#define my_max(x,y) (x>y?x:y)
|
|
|
12 |
|
|
|
13 |
namespace Geometry
|
|
|
14 |
{
|
|
|
15 |
void BBox::intersect_min_max(Ray &ray, double &t_min, double &t_max) const
|
|
|
16 |
{
|
|
|
17 |
double tx1 = (min_corner[0]-ray.origin[0])/ray.direction[0];
|
|
|
18 |
double ty1 = (min_corner[1]-ray.origin[1])/ray.direction[1];
|
|
|
19 |
double tz1 = (min_corner[2]-ray.origin[2])/ray.direction[2];
|
|
|
20 |
|
|
|
21 |
double tx2 = (max_corner[0]-ray.origin[0])/ray.direction[0];
|
|
|
22 |
double ty2 = (max_corner[1]-ray.origin[1])/ray.direction[1];
|
|
|
23 |
double tz2 = (max_corner[2]-ray.origin[2])/ray.direction[2];
|
|
|
24 |
|
|
|
25 |
t_min = my_max(my_min(tx1, tx2), my_max(my_min(ty1, ty2), my_min(tz1,tz2)));
|
|
|
26 |
t_max = my_min(my_max(tx1, tx2), my_min(my_max(ty1, ty2), my_max(tz1,tz2)));
|
|
|
27 |
}
|
|
|
28 |
|
|
|
29 |
bool BBox::intersect(Ray &ray)
|
|
|
30 |
{
|
|
|
31 |
double t_min, t_max;
|
|
|
32 |
intersect_min_max(ray, t_min, t_max);
|
|
|
33 |
|
|
|
34 |
if(t_min <= t_max && t_min < ray.dist && t_min > f_eps)
|
|
|
35 |
return true;
|
|
|
36 |
else
|
|
|
37 |
return false;
|
|
|
38 |
}
|
|
|
39 |
|
|
|
40 |
bool BBox::ray_triangle(Vec3f &ray_start, Vec3f &ray_end, ISectTri &tri)
|
|
|
41 |
{
|
|
|
42 |
Vec3f origin = ray_start;
|
|
|
43 |
Vec3f direction = ray_end - ray_start;
|
|
|
44 |
double dist = direction.length();
|
|
|
45 |
direction.normalize();
|
|
|
46 |
|
|
|
47 |
Vec3f p;
|
|
|
48 |
Vec3f q;
|
|
|
49 |
Vec3f s;
|
|
|
50 |
double a, f, u, v, t;
|
|
|
51 |
|
|
|
52 |
p = cross(direction, Vec3f(tri.edge1));
|
|
|
53 |
a = dot(Vec3f(tri.edge0),p);
|
|
|
54 |
if (a>-f_eps && a<f_eps)
|
|
|
55 |
return false;
|
|
|
56 |
f = 1/a;
|
|
|
57 |
s = origin - Vec3f(tri.point0);
|
|
|
58 |
u = f*dot(s,p);
|
|
|
59 |
if (u<0.0 || u>1.0)
|
|
|
60 |
return false;
|
|
|
61 |
q = cross(s, Vec3f(tri.edge0));
|
|
|
62 |
v = f * dot(direction, q);
|
|
|
63 |
if (v<0.0 || u+v>1.0)
|
|
|
64 |
return false;
|
|
|
65 |
t = f*dot(Vec3f(tri.edge1), q);
|
|
|
66 |
if (t<0)
|
|
|
67 |
return false;
|
|
|
68 |
// if (t<eps)
|
|
|
69 |
// return false;
|
|
|
70 |
if (t>dist)
|
|
|
71 |
return false;
|
|
|
72 |
|
|
|
73 |
return true;
|
|
|
74 |
}
|
|
|
75 |
|
|
|
76 |
|
|
|
77 |
bool BBox::intersect_edge_box(Vec3f &ray_start, Vec3f &ray_end)
|
|
|
78 |
{
|
|
|
79 |
Ray test_ray;
|
|
|
80 |
test_ray.origin = ray_start;
|
|
|
81 |
test_ray.direction = ray_end - ray_start;
|
|
|
82 |
test_ray.dist = test_ray.direction.length();
|
|
|
83 |
test_ray.direction.normalize();
|
|
|
84 |
return intersect(test_ray);
|
|
|
85 |
}
|
|
|
86 |
|
|
|
87 |
bool BBox::in_interval(double min_limit, double test_value, double max_limit)
|
|
|
88 |
{
|
|
|
89 |
if (min_limit<=test_value && test_value<=max_limit)
|
|
|
90 |
return true;
|
|
|
91 |
return false;
|
|
|
92 |
}
|
|
|
93 |
/*
|
|
|
94 |
|
|
|
95 |
bool BBox::intersect_triangle_left(ISectTri &tri, double plane, int axis) {
|
|
|
96 |
if (tri.point0[axis]<=plane)
|
|
|
97 |
return true;
|
|
|
98 |
if (tri.point1[axis]<=plane)
|
|
|
99 |
return true;
|
|
|
100 |
if (tri.point2[axis]<=plane)
|
|
|
101 |
return true;
|
|
|
102 |
return false;
|
|
|
103 |
}
|
|
|
104 |
|
|
|
105 |
bool BBox::intersect_triangle_right(ISectTri &tri, double plane, int axis) {
|
|
|
106 |
if (tri.point0[axis]>=plane)
|
|
|
107 |
return true;
|
|
|
108 |
if (tri.point1[axis]>=plane)
|
|
|
109 |
return true;
|
|
|
110 |
if (tri.point2[axis]>=plane)
|
|
|
111 |
return true;
|
|
|
112 |
return false;
|
|
|
113 |
}
|
|
|
114 |
*/
|
|
|
115 |
bool BBox::intersect_triangle(ISectTri &tri)
|
|
|
116 |
{
|
|
|
117 |
Vec3f tmin_corner = min_corner - Vec3f(0.01f,0.01f,0.01f);
|
|
|
118 |
Vec3f tmax_corner = max_corner + Vec3f(0.01f,0.01f,0.01f);
|
|
|
119 |
|
|
|
120 |
// Vertex in box test:
|
|
|
121 |
// If any of the triangle vertices are inside the box then
|
|
|
122 |
// the triangle intersects the box
|
|
|
123 |
if (in_interval(tmin_corner[0],tri.point0[0],tmax_corner[0]) && in_interval(tmin_corner[1],tri.point0[1],tmax_corner[1]) && in_interval(tmin_corner[2],tri.point0[2],tmax_corner[2]))
|
|
|
124 |
return true;
|
|
|
125 |
if (in_interval(tmin_corner[0],tri.point1[0],tmax_corner[0]) && in_interval(tmin_corner[1],tri.point1[1],tmax_corner[1]) && in_interval(tmin_corner[2],tri.point1[2],tmax_corner[2]))
|
|
|
126 |
return true;
|
|
|
127 |
if (in_interval(tmin_corner[0],tri.point2[0],tmax_corner[0]) && in_interval(tmin_corner[1],tri.point2[1],tmax_corner[1]) && in_interval(tmin_corner[2],tri.point2[2],tmax_corner[2]))
|
|
|
128 |
return true;
|
|
|
129 |
|
|
|
130 |
// Triangle outside box test:
|
|
|
131 |
// If all of the triangle vertices are outside one of the planes
|
|
|
132 |
// defining the sides of the box then the triangle can be trivially
|
|
|
133 |
// rejected as outside
|
|
|
134 |
int i;
|
|
|
135 |
for(i=0;i<3;i++)
|
|
|
136 |
if (tri.point0[i]<tmin_corner[i] && tri.point1[i]<tmin_corner[i] && tri.point2[i]<tmin_corner[i])
|
|
|
137 |
return false;
|
|
|
138 |
|
|
|
139 |
for(i=0;i<3;i++)
|
|
|
140 |
if (tri.point0[i]>tmax_corner[i] && tri.point1[i]>tmax_corner[i] && tri.point2[i]>tmax_corner[i])
|
|
|
141 |
return false;
|
|
|
142 |
|
|
|
143 |
// Triangle edges - box intersection test
|
|
|
144 |
if (intersect_edge_box(tri.point0, tri.point1))
|
|
|
145 |
return true;
|
|
|
146 |
|
|
|
147 |
if (intersect_edge_box(tri.point1, tri.point2))
|
|
|
148 |
return true;
|
|
|
149 |
|
|
|
150 |
if (intersect_edge_box(tri.point2, tri.point0))
|
|
|
151 |
return true;
|
|
|
152 |
|
|
|
153 |
// Box diagonal - triangle intersection test, 4 tests in total
|
|
|
154 |
Vec3f corner0;
|
|
|
155 |
Vec3f corner1;
|
|
|
156 |
|
|
|
157 |
Vec3f tmin_corner_e = tmin_corner;
|
|
|
158 |
Vec3f tmax_corner_e = tmax_corner;
|
|
|
159 |
|
|
|
160 |
corner0.set(tmin_corner_e[0],tmin_corner_e[1],tmin_corner_e[2]);
|
|
|
161 |
corner1.set(tmax_corner_e[0],tmax_corner_e[1],tmax_corner_e[2]);
|
|
|
162 |
if (ray_triangle(corner0, corner1, tri))
|
|
|
163 |
return true;
|
|
|
164 |
|
|
|
165 |
corner0.set(tmax_corner_e[0],tmin_corner_e[1],tmin_corner_e[2]);
|
|
|
166 |
corner1.set(tmin_corner_e[0],tmax_corner_e[1],tmax_corner_e[2]);
|
|
|
167 |
if (ray_triangle(corner0, corner1, tri))
|
|
|
168 |
return true;
|
|
|
169 |
|
|
|
170 |
corner0.set(tmin_corner_e[0],tmax_corner_e[1],tmin_corner_e[2]);
|
|
|
171 |
corner1.set(tmax_corner_e[0],tmin_corner_e[1],tmax_corner_e[2]);
|
|
|
172 |
if (ray_triangle(corner0, corner1, tri))
|
|
|
173 |
return true;
|
|
|
174 |
|
|
|
175 |
corner0.set(tmin_corner_e[0],tmin_corner_e[1],tmax_corner_e[2]);
|
|
|
176 |
corner1.set(tmax_corner_e[0],tmax_corner_e[1],tmin_corner_e[2]);
|
|
|
177 |
if (ray_triangle(corner0, corner1, tri))
|
|
|
178 |
return true;
|
|
|
179 |
|
|
|
180 |
// None succeded
|
|
|
181 |
return false;
|
|
|
182 |
}
|
|
|
183 |
|
|
|
184 |
void BBox::compute_bbox(vector<ISectTri> &isectmesh)
|
|
|
185 |
{
|
|
|
186 |
min_corner.set(CGLA::BIG,CGLA::BIG,CGLA::BIG);
|
|
|
187 |
max_corner.set(-CGLA::BIG,-CGLA::BIG,-CGLA::BIG);
|
|
|
188 |
|
|
|
189 |
for(unsigned int i=0;i<isectmesh.size(); ++i)
|
|
|
190 |
{
|
|
|
191 |
const ISectTri& tri = isectmesh[i];
|
|
|
192 |
for(int j=0;j<3;j++) {
|
|
|
193 |
if (min_corner[j]>tri.point0[j])
|
|
|
194 |
min_corner[j]=tri.point0[j];
|
|
|
195 |
if (min_corner[j]>tri.point1[j])
|
|
|
196 |
min_corner[j]=tri.point1[j];
|
|
|
197 |
if (min_corner[j]>tri.point2[j])
|
|
|
198 |
min_corner[j]=tri.point2[j];
|
|
|
199 |
if (max_corner[j]<tri.point0[j])
|
|
|
200 |
max_corner[j]=tri.point0[j];
|
|
|
201 |
if (max_corner[j]<tri.point1[j])
|
|
|
202 |
max_corner[j]=tri.point1[j];
|
|
|
203 |
if (max_corner[j]<tri.point2[j])
|
|
|
204 |
max_corner[j]=tri.point2[j];
|
|
|
205 |
}
|
|
|
206 |
}
|
|
|
207 |
}
|
|
|
208 |
|
|
|
209 |
double BBox::area()
|
|
|
210 |
{
|
|
|
211 |
Vec3f size = max_corner - min_corner;
|
|
|
212 |
return size[0]*size[1]*2 +
|
|
|
213 |
size[1]*size[2]*2 +
|
|
|
214 |
size[0]*size[2]*2;
|
|
|
215 |
}
|
|
|
216 |
}
|
|
|
217 |
|