Subversion Repositories gelsvn

/* ----------------------------------------------------------------------- *

 * 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; 

  }

}