Go to most recent revision | Blame | Last modification | View Log | RSS feed
/* ----------------------------------------------------------------------- *
* This file is part of GEL, http://www.imm.dtu.dk/GEL
* Copyright (C) the authors and DTU Informatics
* For license and list of authors, see ../../doc/intro.pdf
* ----------------------------------------------------------------------- */
// Created by Bent Dalgaard Larsen, Nov, 2003
#include "Ray.h"
#include "BBox.h"
using namespace std;
using namespace CGLA;
#define my_min(x,y) (x<y?x:y)
#define my_max(x,y) (x>y?x:y)
namespace Geometry
{
void BBox::intersect_min_max(Ray &ray, double &t_min, double &t_max) const
{
double tx1 = (min_corner[0]-ray.origin[0])/ray.direction[0];
double ty1 = (min_corner[1]-ray.origin[1])/ray.direction[1];
double tz1 = (min_corner[2]-ray.origin[2])/ray.direction[2];
double tx2 = (max_corner[0]-ray.origin[0])/ray.direction[0];
double ty2 = (max_corner[1]-ray.origin[1])/ray.direction[1];
double tz2 = (max_corner[2]-ray.origin[2])/ray.direction[2];
t_min = my_max(my_min(tx1, tx2), my_max(my_min(ty1, ty2), my_min(tz1,tz2)));
t_max = my_min(my_max(tx1, tx2), my_min(my_max(ty1, ty2), my_max(tz1,tz2)));
}
bool BBox::intersect(Ray &ray)
{
double t_min, t_max;
intersect_min_max(ray, t_min, t_max);
if(t_min <= t_max && t_min < ray.dist && t_min > f_eps)
return true;
else
return false;
}
bool BBox::ray_triangle(Vec3f &ray_start, Vec3f &ray_end, ISectTri &tri)
{
Vec3f origin = ray_start;
Vec3f direction = ray_end - ray_start;
double dist = direction.length();
direction.normalize();
Vec3f p;
Vec3f q;
Vec3f s;
double a, f, u, v, t;
p = cross(direction, Vec3f(tri.edge1));
a = dot(Vec3f(tri.edge0),p);
if (a>-f_eps && a<f_eps)
return false;
f = 1/a;
s = origin - Vec3f(tri.point0);
u = f*dot(s,p);
if (u<0.0 || u>1.0)
return false;
q = cross(s, Vec3f(tri.edge0));
v = f * dot(direction, q);
if (v<0.0 || u+v>1.0)
return false;
t = f*dot(Vec3f(tri.edge1), q);
if (t<0)
return false;
// if (t<eps)
// return false;
if (t>dist)
return false;
return true;
}
bool BBox::intersect_edge_box(Vec3f &ray_start, Vec3f &ray_end)
{
Ray test_ray;
test_ray.origin = ray_start;
test_ray.direction = ray_end - ray_start;
test_ray.dist = test_ray.direction.length();
test_ray.direction.normalize();
return intersect(test_ray);
}
bool BBox::in_interval(double min_limit, double test_value, double max_limit)
{
if (min_limit<=test_value && test_value<=max_limit)
return true;
return false;
}
/*
bool BBox::intersect_triangle_left(ISectTri &tri, double plane, int axis) {
if (tri.point0[axis]<=plane)
return true;
if (tri.point1[axis]<=plane)
return true;
if (tri.point2[axis]<=plane)
return true;
return false;
}
bool BBox::intersect_triangle_right(ISectTri &tri, double plane, int axis) {
if (tri.point0[axis]>=plane)
return true;
if (tri.point1[axis]>=plane)
return true;
if (tri.point2[axis]>=plane)
return true;
return false;
}
*/
bool BBox::intersect_triangle(ISectTri &tri)
{
Vec3f tmin_corner = min_corner - Vec3f(f_eps);
Vec3f tmax_corner = max_corner + Vec3f(f_eps);
// Vertex in box test:
// If any of the triangle vertices are inside the box then
// the triangle intersects the box
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]))
return true;
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]))
return true;
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]))
return true;
// Triangle outside box test:
// If all of the triangle vertices are outside one of the planes
// defining the sides of the box then the triangle can be trivially
// rejected as outside
int i;
for(i=0;i<3;i++)
if (tri.point0[i]<tmin_corner[i] && tri.point1[i]<tmin_corner[i] && tri.point2[i]<tmin_corner[i])
return false;
for(i=0;i<3;i++)
if (tri.point0[i]>tmax_corner[i] && tri.point1[i]>tmax_corner[i] && tri.point2[i]>tmax_corner[i])
return false;
// Triangle edges - box intersection test
if (intersect_edge_box(tri.point0, tri.point1))
return true;
if (intersect_edge_box(tri.point1, tri.point2))
return true;
if (intersect_edge_box(tri.point2, tri.point0))
return true;
// Box diagonal - triangle intersection test, 4 tests in total
Vec3f corner0;
Vec3f corner1;
Vec3f tmin_corner_e = tmin_corner;
Vec3f tmax_corner_e = tmax_corner;
corner0.set(tmin_corner_e[0],tmin_corner_e[1],tmin_corner_e[2]);
corner1.set(tmax_corner_e[0],tmax_corner_e[1],tmax_corner_e[2]);
if (ray_triangle(corner0, corner1, tri))
return true;
corner0.set(tmax_corner_e[0],tmin_corner_e[1],tmin_corner_e[2]);
corner1.set(tmin_corner_e[0],tmax_corner_e[1],tmax_corner_e[2]);
if (ray_triangle(corner0, corner1, tri))
return true;
corner0.set(tmin_corner_e[0],tmax_corner_e[1],tmin_corner_e[2]);
corner1.set(tmax_corner_e[0],tmin_corner_e[1],tmax_corner_e[2]);
if (ray_triangle(corner0, corner1, tri))
return true;
corner0.set(tmin_corner_e[0],tmin_corner_e[1],tmax_corner_e[2]);
corner1.set(tmax_corner_e[0],tmax_corner_e[1],tmin_corner_e[2]);
if (ray_triangle(corner0, corner1, tri))
return true;
// None succeded
return false;
}
void BBox::compute_bbox(vector<ISectTri> &isectmesh)
{
min_corner.set(CGLA::BIG,CGLA::BIG,CGLA::BIG);
max_corner.set(-CGLA::BIG,-CGLA::BIG,-CGLA::BIG);
for(unsigned int i=0;i<isectmesh.size(); ++i)
{
const ISectTri& tri = isectmesh[i];
for(int j=0;j<3;j++) {
if (min_corner[j]>tri.point0[j])
min_corner[j]=tri.point0[j];
if (min_corner[j]>tri.point1[j])
min_corner[j]=tri.point1[j];
if (min_corner[j]>tri.point2[j])
min_corner[j]=tri.point2[j];
if (max_corner[j]<tri.point0[j])
max_corner[j]=tri.point0[j];
if (max_corner[j]<tri.point1[j])
max_corner[j]=tri.point1[j];
if (max_corner[j]<tri.point2[j])
max_corner[j]=tri.point2[j];
}
}
}
double BBox::area()
{
Vec3f size = max_corner - min_corner;
return size[0]*size[1]*2 +
size[1]*size[2]*2 +
size[0]*size[2]*2;
}
}