collider.coffee

EPS = .03125

clamp = (x) -> Math.min Math.max(x, 0), 1

class Collider
	constructor: (@tree) ->

	checkCollision: (a, b, bbox) ->
		outputStartsOut = true
		outputAllSolid = false
		outputFraction = 1

		checkNode = (node, startFraction, endFraction, start, end) ->
			if node[0] == 0
				sd = start.dot(node[1][0]) - node[1][1]
				ed =   end.dot(node[1][0]) - node[1][1]

				if sd >= 0 and ed >= 0
					checkNode node[4], startFraction, endFraction, start, end
				else if sd < 0 and ed < 0
					checkNode node[5], startFraction, endFraction, start, end
				else
					if sd < ed
						side = 1
						id = 1 / (sd - ed)
						fraction1 = fraction2 = clamp (sd + EPS) * id
					else if ed < sd
						side = 0
						id = 1 / (sd - ed)
						fraction1 = clamp (sd + EPS) * id
						fraction2 = clamp (sd - EPS) * id
					else
						side = 0
						fraction1 = 1
						fraction2 = 0

					middleFraction = startFraction + (endFraction - startFraction) * fraction1
					middle = start.clone().add(end.clone().sub(start).multiplyScalar fraction1)
					checkNode node[4], startFraction, middleFraction, start, middle

					middleFraction = startFraction + (endFraction - startFraction) * fraction2
					middle = start.clone().add(end.clone().sub(start).multiplyScalar fraction2)
					checkNode node[5], middleFraction, endFraction, start, middle
			else
				for brush in node[3]
					if brush.length > 0
						checkBrush brush

		checkBrush = (brush) ->
			startsOut = false
			endsOut = false
			startFraction = -1
			endFraction = 1
			for plane in brush
				sd = a.dot(plane[0]) - plane[1]
				ed = b.dot(plane[0]) - plane[1]

				startsOut = true if sd > 0
				endsOut = true if ed > 0

				if sd > 0 and ed > 0
					return
				else if sd <= 0 and ed <= 0
					console.log '...'
					continue
				console.log 'dsfaopj'

				if sd > ed
					fraction = (sd - EPS) / (sd - ed)
					startFraction = fraction if fraction > startFraction
				else
					fraction = (sd + EPS) / (sd - ed)
					endFraction = fraction if fraction < endFraction
			if not startsOut
				outputStartsOut = false
				if not endsOut
					outputAllSolid = true
				return
			if startFraction < endFraction
				if startFraction > -1 and startFraction < outputFraction
					startFraction = Math.max(startFraction, 0)
					outputFraction = startFraction

		checkNode @tree, 0, 1, a, b

		console.log outputFraction, outputAllSolid, outputStartsOut

		if outputFraction != 1
			console.log 'collided'
			return a.clone().add(b.clone().sub(a).multiplyScalar outputFraction)
		else
			return undefined

module.exports = Collider

collider.cpp

void CheckNode( int nodeIndex,
                float startFraction, float endFraction,
                vector start, vector end )
{
    object *node = &BSP.nodes[nodeIndex];
    object *plane = &BSP.planes[node->planeIndex];

    float startDistance = DotProduct( start, plane->normal ) - plane->distance;
    float endDistance = DotProduct( end, plane->normal ) - plane->distance;

    if (startDistance >= 0 && endDistance >= 0)
    {   // both points are in front of the plane
        // so check the front child
        CheckNode( node->children[0], startFraction, endFraction, start, end );
    }
    else if (startDistance < 0 && endDistance < 0)
    {   // both points are behind the plane
        // so check the back child
        CheckNode( node->children[1], startFraction, endFraction, start, end );
    }
    else
    {   // the line spans the splitting plane
        int side;
        float fraction1, fraction2, middleFraction;
        vector middle;

        // STEP 1: split the segment into two
        if (startDistance < endDistance)
        {
            side = 1; // back
            float inverseDistance = 1.0f / (startDistance - endDistance);
            fraction1 = (startDistance + EPSILON) * inverseDistance;
            fraction2 = (startDistance + EPSILON) * inverseDistance;
        }
        else if (endDistance < startDistance)
        {
            side = 0; // front
            float inverseDistance = 1.0f / (startDistance - endDistance);
            fraction1 = (startDistance + EPSILON) * inverseDistance;
            fraction2 = (startDistance - EPSILON) * inverseDistance;
        }
        else
        {
            side = 0; // front
            fraction1 = 1.0f;
            fraction2 = 0.0f;
        }

        // STEP 2: make sure the numbers are valid
        if (fraction1 < 0.0f) fraction1 = 0.0f;
        else if (fraction1 > 1.0f) fraction1 = 1.0f;
        if (fraction2 < 0.0f) fraction2 = 0.0f;
        else if (fraction2 > 1.0f) fraction2 = 1.0f;

        // STEP 3: calculate the middle point for the first side
        middleFraction = startFraction +
                         (endFraction - startFraction) * fraction1;
        for (i = 0; i < 3; i++)
            middle[i] = start[i] + fraction1 * (end[i] - start[i]);

        // STEP 4: check the first side
        CheckNode( node->children[side], startFraction, middleFraction,
                   start, middle );

        // STEP 5: calculate the middle point for the second side
        middleFraction = startFraction +
                        (endFraction - startFraction) * fraction2;
        for (i = 0; i < 3; i++)
            middle[i] = start[i] + fraction2 * (end[i] - start[i]);

        // STEP 6: check the second side
        CheckNode( node->children[!side], middleFraction, endFraction,
                   middle, end );  
    }
}

void CheckBrush( object *brush )
{
    float startFraction = -1.0f;
    float endFraction = 1.0f;
    boolean startsOut = false;
    boolean endsOut = false;

    for (int i = 0; i < brush->numSides; i++)
    {
        object *brushSide = &BSP.brushSides[brush->firstSide + i];
        object *plane = &BSP.planes[brushSide->planeIndex];

        float startDistance = DotProduct( inputStart, plane->normal ) -
                              plane->distance;
        float endDistance = DotProduct( inputEnd, plane->normal ) -
                            plane->distance;

        if (startDistance > 0)
            startsOut = true;
        if (endDistance > 0)
            endsOut = true;

        // make sure the trace isn't completely on one side of the brush
        if (startDistance > 0 && endDistance > 0)
        {   // both are in front of the plane, its outside of this brush
            return;
        }
        if (startDistance <= 0 && endDistance <= 0)
        {   // both are behind this plane, it will get clipped by another one
            continue;
        }

        if (startDistance > endDistance)
        {   // line is entering into the brush
            float fraction = (startDistance - EPSILON) / (startDistance - endDistance);
            if (fraction > startFraction)
                startFraction = fraction;
        }
        else
        {   // line is leaving the brush
            float fraction = (startDistance + EPSILON) / (startDistance - endDistance);
            if (fraction < endFraction)
                endFraction = fraction;
        }
    }

    if (startsOut == false)
    {
        outputStartOut = false;
        if (endsOut == false)
            outputAllSolid = true;
        return;
    }

    if (startFraction < endFraction)
    {
        if (startFraction > -1 && startFraction < outputFraction)
        {
            if (startFraction < 0)
                startFraction = 0;
            outputFraction = startFraction;
        }
    }
}

void Trace( vector inputStart, vector inputEnd )
{
    outputStartsOut = true;
    outputAllSolid = false;
    outputFraction = 1.0f;

    // walk through the BSP tree
    CheckNode( 0, 0.0f, 1.0f, inputStart, inputEnd );

    if (outputFraction == 1.0f)
    {   // nothing blocked the trace
        outputEnd = inputEnd;
    }
    else
    {   // collided with something 
        for (i = 0; i < 3; i++)
        {
            outputEnd[i] = inputStart[i] +
                           outputFraction * (inputEnd[i] - inputStart[i]);
        }
    }
}