Intersection Triangle::intersect(const Ray& ray, float previousBestDistance) const
	{
		Vector a,b,c,rayO;
		a=tvertices[0]-Point(0,0,0);
		b=tvertices[1]-Point(0,0,0);
		c=tvertices[2]-Point(0,0,0);
		rayO=ray.o-Point(0,0,0);
		/*Vector nab=cross(tvertices[1]-ray.o,tvertices[0]-ray.o);
		Vector nbc=cross(tvertices[2]-ray.o,tvertices[1]-ray.o);
		Vector nca=cross(tvertices[0]-ray.o,tvertices[2]-ray.o);*/
		Vector nab=cross(b-rayO,a-rayO);
		Vector nbc=cross(c-rayO,b-rayO);
		Vector nca=cross(a-rayO,c-rayO);
		float dotab=dot(nab,ray.d);
		float dotbc=dot(nbc,ray.d);
		float dotca=dot(nca,ray.d);
		
		if((dotab>0 && dotbc>0 && dotca>0) ||(dotab<0 && dotbc<0 && dotca<0))
		{
			Vector vect0 = (b - a);
			Vector vect1 = (c - a);

			Vector tnormal = cross(vect0, vect1).normalize(); // triangle normal on vertix a

			float factor= dot(ray.d,tnormal);
			if(abs(factor-0.0)<0.00001) 
				return Intersection::failure();

			float sumIv = 1.0f / (dotab + dotbc + dotca);
			float l2 = dotab * sumIv;
			float l0 = dotbc * sumIv;
			float l1 = dotca * sumIv;

			Point pp = l0 * tvertices[0] + l1 * tvertices[1] + l2 * tvertices[2];

			Vector direction = pp - ray.o;

			float orientation = dot(direction, ray.d);
			float distance = direction.length();

			if(distance>previousBestDistance || orientation<0.000001) 
				return Intersection::failure();

			//Point p=ray.getPoint(distance);
			// here instead of p i can also give barycentric coordinates but why should I
			return Intersection(distance,ray,this,tnormal,Point(l0,l1,l2));
		}
		return Intersection::failure();
	}

	void configure() {
		unsigned int extraFlags = 0;
		if (!m_sigmaA->isConstant() || !m_alpha->isConstant())
			extraFlags |= ESpatiallyVarying;

		m_components.clear();
		for (int i=0; i<m_nested->getComponentCount(); ++i)
			m_components.push_back(m_nested->getType(i) | extraFlags);

		m_components.push_back(EGlossyReflection | EFrontSide | EBackSide
			| (m_specularReflectance->isConstant() ? 0 : ESpatiallyVarying));

		m_usesRayDifferentials = m_nested->usesRayDifferentials()
			|| m_sigmaA->usesRayDifferentials()
			|| m_alpha->usesRayDifferentials()
			|| m_specularReflectance->usesRayDifferentials();

		/* Compute weights that further steer samples towards
		   the specular or nested components */
		Float avgAbsorption = (m_sigmaA->getAverage()
			 *(-2*m_thickness)).exp().average();

		m_specularSamplingWeight = 1.0f / (avgAbsorption + 1.0f);

		/* Verify the input parameters and fix them if necessary */
		m_specularReflectance = ensureEnergyConservation(
			m_specularReflectance, "specularReflectance", 1.0f);

		if (!m_roughTransmittance.get()) {
			/* Load precomputed data used to compute the rough
			   transmittance through the dielectric interface */
			m_roughTransmittance = new RoughTransmittance(
				m_distribution.getType());

			m_roughTransmittance->checkEta(m_eta);
			m_roughTransmittance->checkAlpha(m_alpha->getMinimum().average());
			m_roughTransmittance->checkAlpha(m_alpha->getMaximum().average());

			/* Reduce the rough transmittance data to a 2D slice */
			m_roughTransmittance->setEta(m_eta);

			/* If possible, even reduce it to a 1D slice */
			if (m_alpha->isConstant())
				m_roughTransmittance->setAlpha(
					m_alpha->eval(Intersection()).average());
		}

		BSDF::configure();
	}

int main(int argc, char **argv) {
    struct LL list1, list2;

    list1.Next = NULL;
    list2.Next = NULL;

    ReadList("5_1.txt", &list1);
    ReadList("5_2.txt", &list2);

    Print(list1.Next);
    Print(list2.Next);

    Print(Intersection(list1.Next, list2.Next).Next);
    Print(Union(list1.Next, list2.Next).Next);
}

Intersection SquarePlane::pickSampleIntersection(std::function<float ()> randomf, const glm::vec3 *target_normal)
{
     float random1 = randomf();
     float random2 = randomf();
     auto point_obj = glm::vec3(random1 - 0.5f, random2 - 0.5f, 0.f);
     auto point = glm::vec3(this->transform.T() *
                      glm::vec4(point_obj, 1.f));
     auto normal = glm::normalize(glm::vec3(this->transform.invTransT() *
                             glm::vec4(0,0,1.f,0.f)));
     auto tangent = glm::normalize(glm::vec3(this->transform.invTransT() *
                             glm::vec4(1.f,0,0,0.f)));
     auto color = Material::GetImageColorInterp(this->GetUVCoordinates(point_obj), this->material->texture);

     return Intersection(point, normal, tangent, 0.f, color, this);
}

void UICurvePoint::ForceContinuousTanget()
{
    if(m_point->mOnCurve)
    {
        int numPts = m_contour->NumPoints();
        
        // find index of this point in the contour
        int ptIndex = -1;
        for(int i = 0; i < numPts; i++)
        {
            if(m_point == m_contour->GetPoint(i))
            {
                ptIndex = i;
                break;
            }
        }
        
        // this point should exist in the contour
        // otherwise theres a problem!
        assert(ptIndex != -1);
        
        TTPoint * ptM1 = m_contour->GetPoint(wrapTo(ptIndex-1, numPts));
        TTPoint * ptP1 = m_contour->GetPoint(wrapTo(ptIndex+1, numPts));
        if(!ptM1->mOnCurve && !ptP1->mOnCurve)
        {
            // translate to origin
            STVector2 trM1 = ptM1->mCoordinates - m_point->mCoordinates;
            // translate to origin
            STVector2 trP1 = ptP1->mCoordinates - m_point->mCoordinates;
            // normalize
            trP1.Normalize();
            // point previous tangent in opposite direction with same length
            trM1 = STVector2(-trP1.x, -trP1.y) * trM1.Length();
            // translate back
            ptM1->mCoordinates = m_point->mCoordinates + trM1;
            
            // don't disturb tangents of other points
            TTPoint * ptM2 = m_contour->GetPoint(wrapTo(ptIndex-2, numPts));
            if(ptM2->mOnCurve)
            {
                TTPoint * ptM3 = m_contour->GetPoint(wrapTo(ptIndex-3, numPts));
                Intersection(m_point->mCoordinates, ptM1->mCoordinates,
                             ptM2->mCoordinates, ptM3->mCoordinates,
                             ptM1->mCoordinates);
            }
        }
    }
}

std::vector<NumberRange> NumberSet::getIntersection(const NumberRange& r) const
{
    std::vector<NumberRange> Result;
    RangeListTypeConstItor ListItor;
    
    NumberRange Intersection(0,0);
    for (ListItor = _List.begin() ; ListItor != _List.end() ; ++ListItor )
    {
        Intersection = intersection( (*ListItor),r);
        if(!Intersection.isEmpty())
        {
            Result.push_back(Intersection);
        }
    }
    return Result;
}

void TextWidget::PaintRegion(const Rect& rct)
{
    RefPtr<Gdk::Pixbuf> pix = CanvasPixbuf();
    Rect drw_rct = Intersection(rct, PixbufBounds(pix));
    if( drw_rct.IsNull() )
        return;

    AlignCairoVsPixbuf(pix, drw_rct);

    RefPtr<Gdk::Window> p_win = get_window();
    Rect dst_rct = Planed::RelToDev(trans, drw_rct);
    p_win->draw_pixbuf(get_style()->get_black_gc(), CanvasPixbuf(),
                       drw_rct.lft, drw_rct.top, 
                       dst_rct.lft, dst_rct.top, dst_rct.Width(), dst_rct.Height(), 
                       Gdk::RGB_DITHER_NORMAL, 0, 0);
}

void Ctrl::DrawLine(const Vector<Rect>& clip, int x, int y, int cx, int cy, bool horz, const byte *pattern, int animation)
{
	if(cx <= 0 || cy <= 0)
		return;
	Vector<Rect> rr = Intersection(clip, RectC(x, y, cx, cy));
	for(int i = 0; i < rr.GetCount(); i++) {
		Rect r = rr[i];
		AddUpdate(r);
		if(horz)
			for(int y = r.top; y < r.bottom; y++)
				DDRect(framebuffer[y] + r.left, 1, pattern, r.left + animation, r.GetWidth());
		else
			for(int x = r.left; x < r.right; x++)
				DDRect(framebuffer[r.top] + x, framebuffer.GetWidth(), pattern, r.top + animation, r.GetHeight());
	}
}

	bool AABB_Tree_Node ::  intersect(Ray& ray, Intersection* in){
		if (child[0]){
			bool intersected1 = false;
			bool intersected2 = false;
			if ((*child[0]).b_box->intersect(ray)){
				intersected1 = (*child[0]).intersect(ray,in);
			}
			if ((*child[1]).b_box->intersect(ray)){
				intersected2 = (*child[1]).intersect(ray,in);
			}
			if (intersected1 || intersected2){
				return true;
			}else{
				return false;
			}
		}else{
			if(my_shapes.size() == 0){
				return false;
			} else{
				bool intersected = false;
				float t = in->t;
				vector<Shape*>::iterator shape;
				for (shape = my_shapes.begin(); shape != my_shapes.end(); shape++){
					Intersection temp = Intersection();
					if((*shape)->intersect(ray, &temp)){
						intersected = true;
						if (t == 0.0 || t > temp.t){
							t = temp.t;
							in->local = temp.local;
							in->shape = temp.shape;
							in->t = temp.t;
						}
						/*else if (t = temp.t){
							if((in->shape->brdf.caustic) && (!temp.shape->brdf.caustic)){
								t = temp.t;
								in->local = temp.local;
								in->shape = temp.shape;
								in->t = temp.t;
								intersected = true;
							}
						}*/
					}	
				}
				return intersected;
			}
		}
	}

Intersection intersectionRayTriangleOpt(const VEC3& P, const VEC3& Dir, const VEC3& Ta, const VEC3& Tb, const VEC3& Tc, VEC3& Inter)
{
	typedef typename VEC3::DATA_TYPE T ;

	VEC3 u = Ta - P ;
	VEC3 v = Tb - P ;
	VEC3 w = Tc - P ;

	T x = tripleProduct(Dir, u, v) ;
	T y = tripleProduct(Dir, v, w) ;
	T z = tripleProduct(Dir, w, u) ;

	unsigned int np = 0 ;
	unsigned int nn = 0 ;
	unsigned int nz = 0 ;

	if (x > T(0))
		++np ;
	else if (x < T(0))
		++nn ;
	else
		++nz ;

	if (y > T(0))
		++np ;
	else if (y < T(0))
		++nn ;
	else
		++nz ;

	if (z > T(0))
		++np ;
	else if (z < T(0))
		++nn ;
	else
		++nz ;

	if ((np != 0) && (nn != 0)) return NO_INTERSECTION ;

	T sum = x + y + z ;
	T alpha = y / sum ;
	T beta = z / sum ;
	T gamma = T(1) - alpha - beta ;
	Inter = Ta * alpha + Tb * beta + Tc * gamma ;

	return Intersection(FACE_INTERSECTION - nz) ;
}

static a_pro *analyseParents( a_state *state, a_pro *pro, a_word *reduce_set )
{
    a_pro *test_pro;
    a_pro *new_pro;
    a_sym *old_lhs;
    a_state *parent_state;
    a_state *new_state;
    a_parent *parent;
    a_parent *split_parent;
    a_reduce_action *raction;

    split_parent = NULL;
    new_pro = NULL;
    old_lhs = pro->sym;
    for( parent = state->parents; parent != NULL; parent = parent->next ) {
        parent_state = parent->state;
        new_state = findNewShiftState( parent_state, old_lhs );
        if( new_state == NULL ) {
            printf( "error! %u %s %u\n", state->sidx, old_lhs->name, parent_state->sidx );
            exit(1);
        }
        for( raction = new_state->redun; (test_pro = raction->pro) != NULL; ++raction ) {
            if( !test_pro->unit ) {
                continue;
            }
            if( EmptyIntersection( reduce_set, raction->follow ) ) {
                continue;
            }
            if( new_pro == NULL ) {
                new_pro = test_pro;
            } else if( new_pro != test_pro ) {
                new_pro = NULL;
                break;
            }
            /* we have a reduce of a unit rule on similar tokens */
            Intersection( reduce_set, raction->follow );
            break;
        }
        if( new_pro == NULL || test_pro == NULL ) {
            split_parent = parent;
        }
    }
    if( Empty( reduce_set ) || split_parent != NULL ) {
        new_pro = NULL;
    }
    return( new_pro );
}

bool AggregatePrimitive::intersect(Ray ray, float* t_hit, Intersection* in){
	Intersection nextIn = Intersection();
	float nextT = INFINITY;
	float currT = INFINITY;
	bool hit = false;
	for (size_t i = 0; i < primitives.size(); i++){
		if (primitives[i]->intersect(ray, &nextT, &nextIn)){
			hit = true;
			if (nextT < currT){
				currT = nextT;
				*t_hit = currT;
				*in = nextIn;
			}
		}
	}
	return hit;
}

bool A3DLine::Intersection(const A3DLine& line, A3DPoint *pt) const
{
	double t1 = 0.0, t2 = 0.0;
	bool   f1, f2;

	f1 = Intersection(line, &t1); 
	f2 = line.Intersection(*this, &t2);

	if (pt) {
		pt->x = pt->y = pt->z = 0.0;
		if (f1) *pt += Start      + t1 * Vector;
		if (f2) *pt += line.Start + t2 * line.Vector;
		if (f1 && f2) *pt *= .5;
	}

	return (f1 || f2);
}

  // Set non-zero velocity response if collision
  inline void clamp_response(Vector3D &p, Vector3D &v, double delta_t, BVHAccel *bvh) {
    Vector3D delta_p = v * delta_t;
    double total_l = delta_p.norm(), l = total_l;
    if (l <= EPS_D) {
      return;
    }
    Vector3D d = delta_p / l;
    // Viewing from plane x = -1.0, clip it as well
    bool intersect = false;
    if (d.z != 0.0) {
      double pt = (1.0 - p.z) / d.z;
      if (pt > 0.0 && pt < l) {
        l = pt;
        intersect = true;
      }
    }
    // light is at y = 1.49.
    // to avoid particles being stuck between light and ceiling, clip it
    if (d.y != 0.0) {
      double pt = (1.49 - p.y) / d.y;
      if (pt > 0.0 && pt < l) {
        l = pt;
        intersect = true;
      }
    }
    Ray r(p, d, 0.0, l);
    Intersection i;
    if (bvh->intersect(r, &i) || intersect) {
      p += (r.max_t - EPS_D) * d;
      // hack. redirect ONCE
      // if not perpendicular
      if (dot(d, i.n) > -1 && !intersect) { //TODO: INTERSECT = true case
        d = (delta_p - dot(delta_p, i.n) * i.n).unit();
        r = Ray(p, d, 0.0, (total_l - r.max_t) * 0.5);
        i = Intersection();
        bvh->intersect(r, &i);
        p += (r.max_t - EPS_D) * d;
      }

    } else {
      p += delta_p;
    }
    p.x = max(-1.0 + EPS_D, min(1.0 - EPS_D, p.x));
    p.y = max(0.0 + EPS_D, min(1.49 - EPS_D, p.y));
    p.z = max(-1.0 + EPS_D, min(1.0 - EPS_D, p.z));
  }

Intersection BVHTree::searchTree(BVHNode *n, Ray r) {
    if (n->leaf) {
        return n->shape->intersects(r);
    } else {
        if (n->bbox.intersects(r)) {
            Intersection i = searchTree(n->left, r);
            Intersection j = searchTree(n->right, r);

            if (i.hasIntersected() && j.hasIntersected()) {
                return i.getIntersectionPoint() < j.getIntersectionPoint() ? i : j;
            } else {
                return i.hasIntersected() ? i : j;
            }
        }
        return Intersection(r);
    }
}

bool Plane::All_Intersections(const Ray& ray, IStack& Depth_Stack, TraceThreadData *Thread)
{
	DBL Depth;
	VECTOR IPoint;

	if (Intersect(ray, &Depth, Thread))
	{
		VEvaluateRay(IPoint, ray.Origin, Depth, ray.Direction);

		if (Clip.empty() || Point_In_Clip(IPoint, Clip, Thread))
		{
			Depth_Stack->push(Intersection(Depth,IPoint,this));
			return(true);
		}
	}

	return(false);
}

bool Plane::All_Intersections(const Ray& ray, IStack& Depth_Stack, TraceThreadData *Thread)
{
    DBL Depth;
    Vector3d IPoint;

    if (Intersect(ray, &Depth, Thread))
    {
        IPoint = ray.Evaluate(Depth);

        if (Clip.empty() || Point_In_Clip(IPoint, Clip, Thread))
        {
            Depth_Stack->push(Intersection(Depth,IPoint,this));
            return(true);
        }
    }

    return(false);
}

 			Intersection intersect(Ray const& ray) const {
 				auto isec1 = t1_.intersect(ray);
 				auto isec2 = t2_.intersect(ray);

 				if (isec1.hit && isec2.hit) {
 					if (isec1.t < isec2.t) {
 						return isec1;
 					} else {
 						return isec2;
 					}
 				} else if (isec1.hit) {
 					return isec1;
 				} else if (isec2.hit) {
 					return isec2;
 				}

 				return Intersection();
 			}

bool Lathe::test_hit(const BasicRay &ray, IStack& Depth_Stack, DBL d, DBL w, int n, TraceThreadData *Thread)
{
    Vector3d IPoint;

    if ((d > DEPTH_TOLERANCE) && (d < MAX_DISTANCE))
    {
        IPoint = ray.Evaluate(d);

        if (Clip.empty() || Point_In_Clip(IPoint, Clip, Thread))
        {
            Depth_Stack->push(Intersection(d, IPoint, this, n, w));

            return(true);
        }
    }

    return(false);
}

bool Spank::CheckCollision(Ship* shipA, Astroid* astroidB)
{
    setValues(shipA, astroidB);
	SDL_Rect collisionRect = Intersection(boundsA, boundsB);

	if(collisionRect.w == 0 && collisionRect.h == 0)
		return false;

	SDL_Rect normalA = NormalizeBounds(collisionRect, true);//spriteA
	SDL_Rect normalB = NormalizeBounds(collisionRect, false);//spriteB

	for(int y = 0; y < collisionRect.h; y++)
		for(int x = 0; x < collisionRect.w; x++)
			if(GetAlphaXY(shipA, normalA.x + x, normalA.y + y) && GetAlphaXY(astroidB, normalB.x + x, normalB.y + y))
				return true;

	return false;
}