intersect.cc

Mesa is an open-source implementation of the OpenGL specification - a system for rendering interacti

#endif // NOTDEF
	}
	default:
	return -1; //picked -1 since it's not used
    }
}

/*----------------------------------------------------------------------------
 * pwlarc_intersect -  find intersection of pwlArc and isoparametric line
 *----------------------------------------------------------------------------
 */

static enum i_result
pwlarc_intersect(
    PwlArc *pwlArc,
    int param,
    REAL value,
    int dir,
    int loc[3] )
{
    assert( pwlArc->npts > 0 );

    if( dir ) {
	TrimVertex *v = pwlArc->pts;
	int imin = 0; 
	int imax = pwlArc->npts - 1;
	assert( value > v[imin].param[param] );
	assert( value < v[imax].param[param] );	
	while( (imax - imin) > 1 ) {
	    int imid = (imax + imin)/2;
	    if( v[imid].param[param] > value )
		imax = imid;
	    else if( v[imid].param[param] < value )
		imin = imid;
	    else {
		loc[1] = imid;
		return INTERSECT_VERTEX;
	    }
	}
	loc[0] = imin;
	loc[2] = imax;
	return INTERSECT_EDGE;
    } else {
	TrimVertex *v = pwlArc->pts;
	int imax = 0; 
	int imin = pwlArc->npts - 1;
	assert( value > v[imin].param[param] );
	assert( value < v[imax].param[param] );	
	while( (imin - imax) > 1 ) {
	    int imid = (imax + imin)/2;
	    if( v[imid].param[param] > value )
		imax = imid;
	    else if( v[imid].param[param] < value )
		imin = imid;
	    else {
		loc[1] = imid;
		return INTERSECT_VERTEX;
	    }
	}
	loc[0] = imin;
	loc[2] = imax;
	return INTERSECT_EDGE;
    }
}

/*----------------------------------------------------------------------------
 * arc_classify - determine which side of a line a jarc lies 
 *----------------------------------------------------------------------------
 */

#ifndef NDEBUG  // for asserts only
static int
arc_classify( Arc_ptr jarc, int param, REAL value )
{
    REAL tdiff, hdiff;
    if( param == 0 ) {
	tdiff = jarc->tail()[0] - value;
	hdiff = jarc->head()[0] - value;
    } else {
	tdiff = jarc->tail()[1] - value;
	hdiff = jarc->head()[1] - value;
    }

    if( tdiff > 0.0 ) {
	if( hdiff > 0.0 ) {
	    return 0x11;
	} else if( hdiff == 0.0 ) {
	    return 0x12;
	} else {
	    return 0x10;
	}
    } else if( tdiff == 0.0 ) {
	if( hdiff > 0.0 ) {
	    return 0x21;
	} else if( hdiff == 0.0 ) {
	    return 0x22;
	} else {
	    return 0x20;
	}
    } else {
	if( hdiff > 0.0 ) {
	    return 0x01;
	} else if( hdiff == 0.0 ) {
	    return 0x02;
	} else {
	    return 0;
	}
    }
}
#endif

void
Subdivider::classify_tailonleft_s( Bin& bin, Bin& in, Bin& out, REAL val )
{
    /* tail at left, head on line */
    Arc_ptr j;

    while( (j = bin.removearc()) != NULL ) {
	assert( arc_classify( j, 0, val ) == 0x02 );
	j->clearitail();

	REAL diff = j->next->head()[0] - val;
	if( diff > 0.0 ) {
	    in.addarc( j );
	} else if( diff < 0.0 ) {
	    if( ccwTurn_sl( j, j->next ) )
		out.addarc( j );
	    else
		in.addarc( j );
	} else {
	    if( j->next->tail()[1] > j->next->head()[1] ) 
		in.addarc(j);
	    else
		out.addarc(j);
	}
    }
}

void
Subdivider::classify_tailonleft_t( Bin& bin, Bin& in, Bin& out, REAL val )
{
    /* tail at left, head on line */
    Arc_ptr j;

    while( (j = bin.removearc()) != NULL ) {
	assert( arc_classify( j, 1, val ) == 0x02 );
	j->clearitail();

        REAL diff = j->next->head()[1] - val;
	if( diff > 0.0 ) {
	    in.addarc( j );
	} else if( diff < 0.0 ) {
	    if( ccwTurn_tl( j, j->next ) )
		out.addarc( j );
	    else
		in.addarc( j );
	} else {
	    if (j->next->tail()[0] > j->next->head()[0] )
		out.addarc( j );
	    else
		in.addarc( j );
	}
    }
}

void
Subdivider::classify_headonleft_s( Bin& bin, Bin& in, Bin& out, REAL val )
{
    /* tail on line, head at left */
    Arc_ptr j;

    while( (j = bin.removearc()) != NULL ) {
	assert( arc_classify( j, 0, val ) == 0x20 );

	j->setitail();

	REAL diff = j->prev->tail()[0] - val;
	if( diff > 0.0 ) {
	    out.addarc( j );
	} else if( diff < 0.0 ) {
	    if( ccwTurn_sl( j->prev, j ) )
		out.addarc( j );
	    else
		in.addarc( j );
	} else {
	    if( j->prev->tail()[1] > j->prev->head()[1] )
		in.addarc( j );
	    else
		out.addarc( j );
	}
    }
}

void
Subdivider::classify_headonleft_t( Bin& bin, Bin& in, Bin& out, REAL val )
{
    /* tail on line, head at left */
    Arc_ptr j;

    while( (j = bin.removearc()) != NULL ) {
	assert( arc_classify( j, 1, val ) == 0x20 );
	j->setitail();

	REAL diff = j->prev->tail()[1] - val;
	if( diff > 0.0 ) {
	    out.addarc( j );
	} else if( diff < 0.0 ) {
	    if( ccwTurn_tl( j->prev, j ) )
		out.addarc( j );
	    else
		in.addarc( j );
	} else {
	    if( j->prev->tail()[0] > j->prev->head()[0] )
		out.addarc( j );
	    else
		in.addarc( j );
	}
    }
}


void
Subdivider::classify_tailonright_s( Bin& bin, Bin& in, Bin& out, REAL val )
{
    /* tail at right, head on line */
    Arc_ptr j;

    while( (j = bin.removearc()) != NULL ) {
	assert( arc_classify( j, 0, val ) == 0x12);
	
	j->clearitail();

        REAL diff = j->next->head()[0] - val;
	if( diff > 0.0 ) {
	    if( ccwTurn_sr( j, j->next ) )
		out.addarc( j );
	    else
		in.addarc( j );
	} else if( diff < 0.0 ) {
	    in.addarc( j );
	} else {
	    if( j->next->tail()[1] > j->next->head()[1] ) 
		out.addarc( j );
	    else
		in.addarc( j );
	}
    }
}

void
Subdivider::classify_tailonright_t( Bin& bin, Bin& in, Bin& out, REAL val )
{
    /* tail at right, head on line */
    Arc_ptr j;

    while( (j = bin.removearc()) != NULL ) {
	assert( arc_classify( j, 1, val ) == 0x12);
	
	j->clearitail();

	REAL diff =  j->next->head()[1] - val;
	if( diff > 0.0 ) {
	    if( ccwTurn_tr( j, j->next ) )
		out.addarc( j );
	    else
		in.addarc( j );
	} else if( diff < 0.0 ) { 
	    in.addarc( j );
	} else {
	    if( j->next->tail()[0] > j->next->head()[0] ) 
		in.addarc( j );
	    else
		out.addarc( j );
	}
    }
}

void
Subdivider::classify_headonright_s( Bin& bin, Bin& in, Bin& out, REAL val )
{
    /* tail on line, head at right */
    Arc_ptr j;

    while( (j = bin.removearc()) != NULL ) {
	assert( arc_classify( j, 0, val ) == 0x21 );
    
	j->setitail();

        REAL diff = j->prev->tail()[0] - val;
	if( diff > 0.0 ) { 
	    if( ccwTurn_sr( j->prev, j ) )
		out.addarc( j );
	    else
		in.addarc( j );
	} else if( diff < 0.0 ) {
	    out.addarc( j );
	} else {
	    if( j->prev->tail()[1] > j->prev->head()[1] )
		out.addarc( j );
	    else
		in.addarc( j );
	}
    }
}

void
Subdivider::classify_headonright_t( Bin& bin, Bin& in, Bin& out, REAL val )
{
    /* tail on line, head at right */
    Arc_ptr j;

    while( (j = bin.removearc()) != NULL ) {
	assert( arc_classify( j, 1, val ) == 0x21 );
    
	j->setitail();

        REAL diff = j->prev->tail()[1] - val;
	if( diff > 0.0 ) { 
	    if( ccwTurn_tr( j->prev, j ) )
		out.addarc( j );
	    else
		in.addarc( j );
	} else if( diff < 0.0 ) {
	    out.addarc( j );
	} else {
	    if( j->prev->tail()[0] > j->prev->head()[0] )
		in.addarc( j );
	    else
		out.addarc( j );
	}
    }
}