bool Square::intersectLocal( const ray& r, isect& i ) const
{
	vec3f p = r.getPosition();
	vec3f d = r.getDirection();

	if( d[2] == 0.0 ) {
		return false;
	}

	double t = -p[2]/d[2];

	if( t <= RAY_EPSILON ) {
		return false;
	}

	vec3f P = r.at( t );

	if( P[0] < -0.5 || P[0] > 0.5 ) {	
		return false;
	}

	if( P[1] < -0.5 || P[1] > 0.5 ) {	
		return false;
	}

	i.obj = this;
	i.t = t;
	if( d[2] > 0.0 ) {
		i.N = vec3f( 0.0, 0.0, -1.0 );
	} else {
		i.N = vec3f( 0.0, 0.0, 1.0 );
	}

	return true;
}

bool Cone::intersectBody( const ray& r, isect& i ) const
{
	vec3f d = r.getDirection();
	vec3f p = r.getPosition();

	double a = (d[0]*d[0]) + (d[1]*d[1]) - (C*d[2]*d[2]);
	double b = 2.0 * (d[0]*p[0] + d[1]*p[1] - C*d[2]*p[2]) - B*d[2];
	double c = (p[0]*p[0]) + (p[1]*p[1]) - A - (B*p[2]) - (C*p[2]*p[2]);

	double disc = b*b - 4.0*a*c;

	if( disc <= 0.0 ) {
		return false;
	}

	disc = sqrt( disc );

	double t1 = (-b - disc) / (2.0 * a);
	double t2 = (-b + disc) / (2.0 * a);

	if( t2 < RAY_EPSILON ) {
		return false;
	}

	if( t1 > RAY_EPSILON ) {
		// Two intersections.
		vec3f P = r.at( t1 );
		double z = P[2];
		if( z >= 0.0 && z <= height ) {
			// It's okay.
			i.t = t1;
			double p3 = -C*P[2] + (b_radius - t_radius)*b_radius / height;
			i.N = vec3f(P[0], P[1], p3).normalize();
#ifdef _DEBUG
			printf("two intersections!\n");
#endif
			return true;
		}
	}

	vec3f P = r.at( t2 );
	double z = P[2];
	if( z >= 0.0 && z <= height ) {
		i.t = t2;
		double p3 = -C*P[2] + (b_radius - t_radius)*b_radius / height;
		i.N = vec3f(P[0], P[1], p3).normalize();
		// In case we are _inside_ the _uncapped_ cone, we need to flip the normal.
		// Essentially, the cone in this case is a double-sided surface
		// and has _2_ normals
	
		if( !capped && (i.N).dot( r.getDirection() ) > 0 )
				i.N = -i.N;
#ifdef _DEBUG
		printf("one intersection!\n");
#endif
        return true;
	}

	return false;
}

// Intersect ray r with the triangle abc.  If it hits returns true,
// and puts the t parameter, barycentric coordinates, normal, object id,
// and object material in the isect object
bool TrimeshFace::intersectLocal( const ray& r, isect& i ) const
{
  const Vec3d& a = parent->vertices[ids[0]];
  const Vec3d& b = parent->vertices[ids[1]];
  const Vec3d& c = parent->vertices[ids[2]];

  // tangent vectors
  Vec3d t1 = b - a;
  Vec3d t2 = c - a;
  
  Vec3d n = crossProd(t1,t2);

  double D = -n*a;

  // if the surface is parallel to the ray there is no intersection
  if(r.getDirection()*n == 0)
  {
    return false;
  }  

  double t = -(n*r.getPosition() + D)/(n*r.getDirection() );
  if (t <= RAY_EPSILON)
    return false;

  // point of intersection with the same plane (doesn't mean intersection with triangle) p(t)=p+t*d
  Vec3d p = r.at(t);

  // triangle area
  double A = n.length()/2.0;

  // barycentric coords
  double wa = crossProd(c-b, p-b).length() / (2.0*A);
  double wb = crossProd(a-c, p-c).length() / (2.0*A);
  double wc = crossProd(b-a, p-a).length() / (2.0*A);

  if((wa >= 0.0) && (wb >= 0.0) && (wc >= 0.0) && (wa+wb+wc-1.0 <= 0.00001)) {
    i.setT(t);
    i.setBary(wa, wb, wc);
    if (parent->normals.size() == 0) {
      i.setN(n);
    } else {
      Vec3d inter_n = wa*parent->normals[ids[0]] + wb*parent->normals[ids[1]]
                    + wc*parent->normals[ids[2]];
      inter_n.normalize();
      i.setN(inter_n);
    }
    i.setObject(this);
    if (parent->materials.size() == 0) {
      i.setMaterial(this->getMaterial() );
    } else {
      Material inter_m = wa*(*parent->materials[ids[0]]);
      inter_m += wb*(*parent->materials[ids[1]]);
      inter_m += wc*(*parent->materials[ids[2]]);
      i.setMaterial(inter_m);
    }
    return true;
  }

  return false;
}

double
circle::intersect(ray const& r) const
{
	double t;
	point3d v1, v2;
	v1=normalize(p1_-center_);
	v2=normalize(p2_-center_);
	point3d n=normalenvektor(v1, v2);
	double s=scaleproduct(n, center_);
	point3d dir=normalize(r.getDir());
	if (scaleproduct(n, dir)!=0)
	{
		double temp=(scaleproduct(n, r.getOrigin())+s)/scaleproduct(n, dir);
		point3d schnitt=r.getOrigin()+temp*dir;
		//std::cout<<"schnitt: "<<schnitt<<std::endl;
        if (is_inside(schnitt))
		{
		    //std::cout<<"Schnittpunkt mit dem Kreis"<<std::endl;
			return t=temp;
		}
		else
		{
		    //std::cout<<"Schnittpunkt mit Ebene aber nicht mit Kreis"<<std::endl;
			return t=-1;
		}

	}
	else
	{
	    //std::cout<<"Kein Schnittpunkt mit Kreisebene"<<std::endl;
		return t=-1;
	}
}

bool Sphere::intersectLocal( const ray& r, isect& i ) const
{
	Vec3d v = -r.getPosition();
	double b = v * r.getDirection();
	double discriminant = b*b - v*v + 1;

	if( discriminant < 0.0 ) {
		return false;
	}

	discriminant = sqrt( discriminant );
	double t2 = b + discriminant;

	if( t2 <= RAY_EPSILON ) {
		return false;
	}

	i.obj = this;

	double t1 = b - discriminant;

	if( t1 > RAY_EPSILON ) {
		i.t = t1;
		i.N = r.at( t1 );
		i.N.normalize();
	} else {
		i.t = t2;
		i.N = r.at( t2 );
		i.N.normalize();
	}

	return true;
}

        //! Intersect ray and sphere, returning true if there is an intersection.
        bool intersect(const ray<Type>& r, Type& tmin, Type& tmax) const
        {
            const vec3<Type> r_to_s = r.getOrigin() - m_center;

            //Compute A, B and C coefficients
            const Type A = r.getDirection().sqrLength();
            const Type B = 2.0f * r_to_s.dot(r.getDirection());
            const Type C = r_to_s.sqrLength() - m_radius * m_radius;

            //Find discriminant
            Type disc = B * B - 4.0 * A * C;

            // if discriminant is negative there are no real roots
            if (disc < 0.0)
                return false;

            disc = (Type)std::sqrt((double)disc);

            tmin = (-B + disc) / (2.0 * A);
            tmax = (-B - disc) / (2.0 * A);

            // check if we're inside it
            if ((tmin < 0.0 && tmax > 0) || (tmin > 0 && tmax < 0))
                return false;

            if (tmin > tmax)
                std::swap(tmin, tmax);

            return (tmin > 0);
        }

Segments CSGNode::intersectLocal(const ray& r) const{
	Segments ret;
	if (isLeaf){
		SegmentPoint pNear, pFar;
		isect i;
		ray backR(r.at(-10000), r.getDirection());
		if(!item->intersect(backR, i))return ret;
		pNear.t = i.t - 10000;
		pNear.normal = i.N;
		pNear.isRight = false;
		ray contiR(r.at(pNear.t+RAY_EPSILON*10),r.getDirection());
		if (!item->intersect(contiR, i))pFar = pNear;
		else {
			pFar.t = i.t + pNear.t;
			pFar.normal = i.N;
		}
		pFar.isRight = true;
		ret.addPoint(pNear);
		ret.addPoint(pFar);
		return ret;
	}
	else {
		if (!lchild || !rchild)return ret;
		Segments leftSeg, rightSeg;
		leftSeg = lchild->intersectLocal(r);
		rightSeg = rchild->intersectLocal(r);
		leftSeg.Merge(rightSeg,relation);
		return leftSeg;
	}
}

bool intersectCircle(const ray& r0, double& tnear, double& tfar, const vec3f& center)
{
	ray r(r0.getPosition() - center, r0.getDirection());

	vec3f v = -r.getPosition();
	double b = v.dot(r.getDirection());
	double discriminant = b*b - v.dot(v) + 1;

	if (discriminant < 0.0) {
		return false;
	}

	discriminant = sqrt(discriminant);
	double t2 = b + discriminant;

	if (t2 <= RAY_EPSILON) {
		return false;
	}



	double t1 = b - discriminant;

	if (t1 > RAY_EPSILON) {
		tnear = t1;
		tfar = t2;
	}
	else {
		tnear = 0;
		tfar = t2;
	}

	return true;
}

bool triangle::intersect(const point &p, const ray &r, point &i)
{
    point i_proj;
    matrix inv;
    float t = 0.0f;
    float alpha = 0.0f, beta = 0.0f;
    t = r.get_dir()*this->normal_;
    if (t == 0.0f)
    {
        return this->OBJECT_NO_INTERSECTION;
    }
    t = (this->plan_offset_ + vector(p)*this->normal_) / t;
    i = p - r.get_dir()*t;
    inv = this->basis_.inverse();
    i_proj = vector(i-this->vertices_[0]);
    i_proj = prod(i_proj, inv);
    alpha = i_proj[0];
    beta = i_proj[1];
    if ( (0.0f <= alpha && alpha <= 1.0f)
            && (0.0f <= beta && beta <= 1.0f)
            && (alpha+beta <= 1.0f) )
    {
        return this->OBJECT_INTERSECTION;
    } else {
        return this->OBJECT_NO_INTERSECTION;
    }
}

// Apply the phong model to this point on the surface of the object, returning
// the color of that point. Uses shaddowAttenuation which sends a shadow ray
// to check if there is an intersection that blocks the light sources.
Vec3d Material::shade( Scene *scene, const ray& r, const isect& i ) const
{
  Vec3d retVal = ke(i) + prod(ka(i), scene->ambient());
  
  // Applies calculations for each light source
  for (vector<Light*>::const_iterator litr = scene->beginLights(); 
       litr != scene->endLights(); ++litr) {
    Vec3d point = r.getPosition() + r.getDirection() * i.t;
    Light* pLight = *litr;
  
    Vec3d reflectionAngle = 2 * (i.N * pLight->getDirection(point)) * i.N - pLight->getDirection(point);

    Vec3d diffIntensity = kd(i) * (max(0, i.N * pLight->getDirection(point)));

    Vec3d viewerAngle = scene->getCamera().getEye() - point;
    viewerAngle.normalize();
    Vec3d specIntensity = ks(i) * pow(max(0, viewerAngle * reflectionAngle), shininess(i));

    Vec3d lcolor = pLight->getColor(point);

    Vec3d totalColor = prod(diffIntensity + specIntensity, lcolor);
    totalColor = totalColor * pLight->distanceAttenuation(point);
    totalColor = prod(totalColor, pLight->shadowAttenuation(point));

    retVal = retVal + totalColor;	
  }
  return retVal;
}

// Apply the Blinn-Phong model to this point on the surface of the object, 
//  returning the color of that point.
Vec3d Material::shade( Scene *scene, const ray& r, const isect& i ) const
{
	// YOUR CODE HERE

		// For now, this method just returns the diffuse color of the object.
		// This gives a single matte color for every distinct surface in the
		// scene, and that's it.  Simple, but enough to get you started.
		// (It's also inconsistent with the Phong model...)

		// Your mission is to fill in this method with the rest of the phong
		// shading model, including the contributions of all the light sources.
		// You will need to call both distanceAttenuation() and shadowAttenuation()
		// somewhere in your code in order to compute shadows and light falloff.
		if (debugMode)
			std::cout << "Debugging the Phong code (or lack thereof...)" << std::endl;

		// When you're iterating through the lights,
		// you'll want to use code that looks something
		// like this:
		Vec3d light = ke(i);
		Vec3d normal = i.N;
		Vec3d iDot = r.at(i.t);
		if (r.getDirection() * normal > 0) {
			normal = -normal;
			light += prod(prod(scene->ambient(), ka(i)), kt(i));
		}
		else {
			light += prod(scene->ambient(), ka(i));
		}

		for (vector<Light*>::const_iterator litr = scene->beginLights();
			litr != scene->endLights();
			++litr)
		{
			Light* pLight = *litr;

			double distAttenuation = pLight->distanceAttenuation(iDot);
			Vec3d shadowAttenuation = pLight->shadowAttenuation(iDot);
			Vec3d atten = distAttenuation * shadowAttenuation;
			Vec3d L = pLight->getDirection(iDot);


			if (L * normal > 0) {
				Vec3d H = (L + -1 * r.getDirection());
				if (H.length() != 0)
					H.normalize();

				double sDot = max(0.0, normal * H);
				Vec3d dTerm = kd(i) * (normal * L);
				Vec3d sTerm = ks(i) * (pow(sDot, shininess(i)));
				Vec3d newLight = dTerm + sTerm;
				newLight = prod(newLight, pLight->getColor());

				light += prod(atten, newLight);
			}
		}

	return light;
}

bool Cylinder::intersectCaps( const ray& r, isect& i ) const
{
	if( !capped ) {
		return false;
	}

	double pz = r.getPosition()[2];
	double dz = r.getDirection()[2];

	if( 0.0 == dz ) {
		return false;
	}

	double t1;
	double t2;

	if( dz > 0.0 ) {
		t1 = (-pz)/dz;
		t2 = (1.0-pz)/dz;
	} else {
		t1 = (1.0-pz)/dz;
		t2 = (-pz)/dz;
	}

	if( t2 < RAY_EPSILON ) {
		return false;
	}

	if( t1 >= RAY_EPSILON ) {
		vec3f p( r.at( t1 ) );
		if( (p[0]*p[0] + p[1]*p[1]) <= 1.0 ) {
			i.t = t1;
			if( dz > 0.0 ) {
				// Intersection with cap at z = 0.
				i.N = vec3f( 0.0, 0.0, -1.0 );
			} else {
				i.N = vec3f( 0.0, 0.0, 1.0 );
			}
			return true;
		}
	}

	vec3f p( r.at( t2 ) );
	if( (p[0]*p[0] + p[1]*p[1]) <= 1.0 ) {
		i.t = t2;
		if( dz > 0.0 ) {
			// Intersection with cap at z = 1.
			i.N = vec3f( 0.0, 0.0, 1.0 );
		} else {
			i.N = vec3f( 0.0, 0.0, -1.0 );
		}
		return true;
	}

	return false;
}

//
//  main.m
//  GC3AssignmentTwo
//
//  Created by Meraj Patel on 11/8/2013.
//  Copyright (c) 2013 Meraj Patel. All rights reserved.
//

#include <stdlib.h>
#include <GLUT/glut.h>
#include "MathLibrary.h"
#include "PhysicsEngine.h"
#include "Particle.h"
#include "Texture.h"
#include <math.h>
#include "ray.h"
#include "Texture.h"
#include "Points.h"

ray newRay;
bool hit1, hit2;
double transparentWall1 = 1;
double transparentWall2 = 1;
int orientation[3] = {0,1,0};
bool flip1, flip2;
float moveY = -2;
float angY = 9*sin(1.05);//roation around Y
double camera[3] = {0,9,9};//declares camera at position
double bounceY = 0;
int x = -1;
PhysicsEngine game;
Texture textureObeject;
bool cameraParticlePosition = false;
bool startStop = true;
bool lightswitch = true;
bool gameOver = false;

void Get3DPos(int x, int y, float winz, GLdouble point[3])
{
    GLint viewport[4];
    GLdouble modelview[16];
    GLdouble projection[16];

    //get the matrices
    glGetDoublev( GL_MODELVIEW_MATRIX, modelview );
    glGetDoublev( GL_PROJECTION_MATRIX, projection );
    glGetIntegerv( GL_VIEWPORT, viewport );

    //"un-project" the 2D point giving the 3D position corresponding to the provided depth (winz)
    gluUnProject( (float)x, (float)(viewport[3]-y), winz, modelview, projection, viewport, &point[0], &point[1], &point[2]);

}

///* rayCast - takes a mouse x,y, coordinate, and casts a ray through that point
// *   for subsequent intersection tests with objects.
// */
void rayCast(float x, float y)
{
    bool groundPlane = true;//check if hit on plane
    GLdouble pNear[3];//depth for z
    GLdouble pFar[3]; //depth for z
    float inter[3];//stores object intersection
    //count through number of objects to perform tests on each one
    //count through number of planes of each object to perform test on each one
    for (int count1 = 0; count1 < game.ActiveObjects.size(); count1++) {
        for(int count2 = 0; count2 < 6; count2++) {

            Get3DPos(x, y, 0.0, pNear);
            Get3DPos(x, y, 1.0, pFar);

            //store ray orgin
            newRay.org[0] = camera[0];
            newRay.org[1] = camera[1];
            newRay.org[2] = camera[2];

            //ray direction is the vector (pFar - pNear)
            newRay.dir[0] = pFar[0] - pNear[0];
            newRay.dir[1] = pFar[1] - pNear[1];
            newRay.dir[2] = pFar[2] - pNear[2];

            newRay.normalizeDirection();

            groundPlane = newRay.rayPlaneTest(count1, count2, game.ActiveObjects);
            //update the position of the object to the intersection point
            if ( groundPlane == true) {
                //check if object is hit between min and max bounds
                if ((game.ActiveObjects.at(count1).min + game.ActiveObjects.at(count1).translateX < newRay.inter[0] && newRay.inter[0] < game.ActiveObjects.at(count1).max + game.ActiveObjects.at(count1).translateX && game.ActiveObjects.at(count1).min + game.ActiveObjects.at(count1).translateZ < newRay.inter[2] && newRay.inter[2] < game.ActiveObjects.at(count1).max + game.ActiveObjects.at(count1).translateZ && inter[1] < game.ActiveObjects.at(count1).max + game.ActiveObjects.at(count1).translateY && game.ActiveObjects.at(count1).min + game.ActiveObjects.at(count1).translateY < newRay.inter[1])) {

                    game.ActiveObjects.at(count1).hit = true;
                    //check to see right click to delete object
                    break;
                }
                //return false hit else wise
                else {
                    game.ActiveObjects.at(count1).hit = false;
                }
            }
        }   //break out of cycle of object
        if(game.ActiveObjects.at(count1).hit == true) {
            for(int z = 0; z < game.ActiveObjects.size(); z++) {
//.........这里部分代码省略.........

bool Metaball::intersectLocal(const ray& r, isect& i) const
{
	bool inside = false;
	if (calvalue(r.getPosition(), ball1pos, ball2pos)>threshold)inside = true;

	//determine possible intersect range
	double t11=0, t12=0, t21=0, t22=0;
	double tmin, tmax;
	bool i1, i2;
	i1 = intersectCircle(r, t11, t12, ball1pos);
	i2 = intersectCircle(r, t21, t22, ball2pos);
	if (!i1 && !i2) return false;
	else if (!i1 && i2)
	{
		tmin = t21;
		tmax = t22;
	}
	else if (i1 && !i2)
	{
		tmin = t11;
		tmax = t12;
	}
	else
	{
		tmin = min(t11, t21);
		tmax = max(t12, t22);
	}

	for (double t = tmin; t < tmax; t += 0.001)
	{
		vec3f point = r.getPosition() + t * r.getDirection();
		double value = calvalue(point, ball1pos, ball2pos);

		if ((!inside && value > threshold) || (inside && value < threshold))
		{
			// prevent fake intersect
			if (inside && t < 0.01)return false;

			vec3f normal;
			normal += 2 * (point - ball1pos) / ((point - ball1pos).length()*(point - ball1pos).length());
			normal += 2 * (point - ball2pos) / ((point - ball2pos).length()*(point - ball2pos).length());
			normal = normal.normalize();
			i.t = t;
			i.N = normal;
			i.obj = this;
			return true;
		}
	}
	return false;
}

// Apply the phong model to this point on the surface of the object, returning
// the color of that point.
vec3f Material::shade( Scene *scene, const ray& r, const isect& i ) const
{
	// YOUR CODE HERE

	// For now, this method just returns the diffuse color of the object.
	// This gives a single matte color for every distinct surface in the
	// scene, and that's it.  Simple, but enough to get you started.
	// (It's also inconsistent with the phong model...)

	// Your mission is to fill in this method with the rest of the phong
	// shading model, including the contributions of all the light sources.
    // You will need to call both distanceAttenuation() and shadowAttenuation()
    // somewhere in your code in order to compute shadows and light falloff.
	
	//intersection point
	vec3f point = r.at(i.t);
	bool istransmissive = abs(index - 1.0) > NORMAL_EPSILON || !kt.iszero();
	vec3f rate = vec3f(1, 1, 1) - kt;

	vec3f I = ke;

	//ambient
	if (istransmissive) I += scene->ambient.time(ka).time(rate).clamp();
	else I += scene->ambient.time(ka).clamp();

	list<Light*>::const_iterator begin = scene->beginLights();
	list<Light*>::const_iterator end = scene->endLights();
	while (begin != end)
	{
		vec3f atten = (*begin)->shadowAttenuation(point) * (*begin)->distanceAttenuation(point);
		vec3f L = (*begin)->getDirection(point);
		double NL = i.N.dot(L);

		//diffuse
		if (istransmissive) I += (atten * NL).time(kd).time(rate).clamp();
		else I += (atten * NL).time(kd).clamp();

		//specular
		vec3f R = i.N * (2 * NL) - L;
		double RV = -R.dot(r.getDirection());
		
		//TODO: where is n£¿
		double n = 64;
		I += (atten * pow(RV, n)).time(ks).clamp();

		begin++;
	}

	return I;
}

bool triangle::intersect(ray const& Ray, intersection& Intersection) const
{
    glm::vec3 w = Ray.get_position() - A;
    glm::vec3 u = -(B - A);
    glm::vec3 v = -(C - A);
    float D = glm::dot(glm::cross(u, v), Ray.get_direction());
    float a = -glm::dot(glm::cross(w, v), Ray.get_direction()) / D;
    float b = -glm::dot(glm::cross(u, w), Ray.get_direction()) / D;
    float t = glm::dot(glm::cross(u, v), w) / D;

    if(a > 0.0f && b > 0.0f && a + b < 1.0)
        return true;
    return false;
}

bool plane::intersect(ray const& Ray, intersection& Intersection) const
{
	bool hit = false;

	if(glm::abs(Ray.get_direction().z) > 0.0f)
	{
		float t = -Ray.get_position().z / Ray.get_direction().z;
		if(t > glm::epsilon<float>() * 100.f)
		{
			Intersection.set_local_position(Ray.get_position() + Ray.get_direction() * t);
			hit = true;
		}
	}
	return hit;
}

ray_intersection plane::shoot_ray(const ray &r) const
{

	/**
	 * Planes go on forever, therefore there will
	 * 	always be an intersection. We will use the
	 * 	Config.MAX_RENDER_DISTANCE to trim plane's
	 * 	extending too far into the distance
	 */
	double distance = dot(normal, point - r.get_point())
                           / dot(normal, r.get_slope());
	ray_intersection ri(this, normal, r, distance);

    return ri;
}

// if the ray hits the box, put the "t" value of the intersection
// closest to the origin in tMin and the "t" value of the far intersection
// in tMax and return true, else return false.
// Using Kay/Kajiya algorithm.
bool BoundingBox::intersect(const ray& r, double& tMin, double& tMax) const
{
	vec3f R0 = r.getPosition();
	vec3f Rd = r.getDirection();

	tMin = -1.0e308; // 1.0e308 is close to infinity... close enough for us!
	tMax = 1.0e308;
	double ttemp;
	
	for (int currentaxis = 0; currentaxis < 3; currentaxis++)
	{
		double vd = Rd[currentaxis];
		
		// if the ray is parallel to the face's plane (=0.0)
		if( vd > -RAY_EPSILON && vd < RAY_EPSILON ) {
			if(R0[currentaxis] <= min[currentaxis] - RAY_EPSILON || R0[currentaxis] >= max[currentaxis] + RAY_EPSILON) {
				return false;
			}
			else {
				continue;
			}
		}

		double v1 = min[currentaxis] - R0[currentaxis];
		double v2 = max[currentaxis] - R0[currentaxis];

		// two slab intersections
		double t1 = v1/vd;
		double t2 = v2/vd;
		
		if ( t1 > t2 ) { // swap t1 & t2
			ttemp = t1;
			t1 = t2;
			t2 = ttemp;
		}

		if (t1 > tMin)
			tMin = t1;
		if (t2 < tMax)
			tMax = t2;

		if (tMin > tMax) // box is missed
			return false;
		if (tMax < -RAY_EPSILON) // box is behind ray
			return false;
	}
	return true; // it made it past all 3 axes.
}

bool tri::intersect(ray & _r, float & t) {
    //calculate t first
    t = inner_product(p[0] - _r.origin, nrml) / inner_product(_r.dir, nrml);
    if (t < 0)
        return false;
    //check inside the tri
    point x = _r.get_t(t);
    vect v2_1 = p[1] - p[0];
    vect v3_2 = p[2] - p[1];
    vect v1_3 = p[0] - p[2];
    vect vx_1 = x - p[0];
    vect vx_2 = x - p[1];
    vect vx_3 = x - p[2];
    /*special judge for debug
    if(abs(x.x) > 500 || abs(x.z) > 500)
        return false;
    return true;
     */
    if (inner_product(cross_product(v2_1, vx_1), nrml) > 0
        && inner_product(cross_product(v3_2, vx_2), nrml) > 0
        && inner_product(cross_product(v1_3, vx_3), nrml) > 0) {
        return true;
    }
    return false;
}