pipe2.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 1,160 行 · 第 1/3 页

        start = rend_obj_get_pt( other, 0 );
        end = rend_obj_get_pt( other, 1 );
        a = point_diff( start, end );
        norm = cross_prod( a, Yvect );
        if( _is_zero_norm( norm ) ) {
            norm = cross_prod( a, Xvect );
        }
        break;
    case REND_OBJ_POLY:
        norm = rend_obj_get_norm( other );
        break;
    }

    pt = rend_obj_get_pt( obj, 0 );
    norm.v[3] = 0 - (norm.v[0]*pt.p[0] + norm.v[1]*pt.p[1] +
                    norm.v[2]*pt.p[2]);

    return( norm );
}

static vector calc_line_norm(
/***************************/
    rend_obj *  obj,            // a line object
    rend_obj *  other
) {
    vector      norm;
    vector      line_vect;
    vector      other_vect;
    point       start;
    point       end;
    point       pt1;
    polygon *   poly;
    int         pt_num;

    pt1 = rend_obj_get_pt( obj, 0 );
    end = rend_obj_get_pt( obj, 1 );
    line_vect = point_diff( pt1, end );

    switch( _rend_obj_get_type( other ) ) {
    case REND_OBJ_PT:
        norm = cross_prod( line_vect, Yvect );
        if( _is_zero_norm( norm ) ) {
            norm = cross_prod( line_vect, Xvect );
        }
        break;
    case REND_OBJ_LINE:
        start = rend_obj_get_pt( other, 0 );
        end = rend_obj_get_pt( other, 1 );
        other_vect = point_diff( start, end );
        norm = cross_prod( line_vect, other_vect );
        if( _is_zero_norm( norm ) ) {
            norm = cross_prod( line_vect, Yvect );
            if( _is_zero_norm( norm ) ) {
                norm = cross_prod( line_vect, Xvect );
            }
        }
        break;
    case REND_OBJ_POLY:
        poly = rend_obj_get_poly( other );
        start = _polygon_get_pt( *poly, _polygon_get_num_pts( *poly ) - 1 );
        for( pt_num = 0; pt_num < _polygon_get_num_pts( *poly ); pt_num++ ) {
            end = _polygon_get_pt( *poly, pt_num );
            other_vect = point_diff( start, end );
            norm = cross_prod( line_vect, other_vect );
            if( !_is_zero_norm( norm ) ) {
        /**/    break;
            }
            start = end;
        }
        if( _is_zero_norm( norm ) ) {
            norm = cross_prod( line_vect, Yvect );
            if( _is_zero_norm( norm ) ) {
                norm = cross_prod( line_vect, Xvect );
            }
        }
        break;
    }

    norm.v[3] = 0 - (norm.v[0]*pt1.p[0] + norm.v[1]*pt1.p[1] +
                    norm.v[2]*pt1.p[2]);

    return( norm );
}

static vector calculate_object_norm(
/**********************************/
/* Calculates the normal for the plane of a given object. See */
/* check_half_space for how this is determined */
    rend_obj *  obj,
    rend_obj *  other
) {
    vector      norm;

    switch (_rend_obj_get_type( obj )) {
    case REND_OBJ_PT:
        norm = calc_pt_norm( obj, other );
        break;
    case REND_OBJ_LINE:
        norm = calc_line_norm( obj, other );
        break;
    case REND_OBJ_POLY:
        norm = rend_obj_get_norm( obj );
        break;
    }

    return( norm );
}

enum {
    SUB_PLANE_UNKNOWN,
    SUB_PLANE_NEG,
    SUB_PLANE_ZERO,
    SUB_PLANE_POS,
    SUB_PLANE_NONE                  // for objects that cross the plane
};
typedef unsigned sub_plane_rc;

/* sign should be the result of a _fuzzy_sign macro */
#define _get_sub_plane_rc( sign ) (((sign) == 0) ? SUB_PLANE_ZERO : \
                    (((sign) == -1) ? SUB_PLANE_NEG : SUB_PLANE_POS ))

static int sub_pt_in_plane(
/*************************/
/* subsitute pt into the plane defined by norm and return the sign of the */
/* result */
    point       pt,
    vector      norm
) {
    float       result;

    result = _dot_prod_vp( norm, pt );
    return( _fuzzy_sign( result, FUZZY_ZERO ) );
}

static sub_plane_rc sub_line_in_plane(
/************************************/
    rend_obj    *obj,
    vector      norm
) {
    int         start_sign;
    int         end_sign;

    start_sign = sub_pt_in_plane( rend_obj_get_pt( obj, 0 ), norm );
    end_sign = sub_pt_in_plane( rend_obj_get_pt( obj, 1 ), norm );

    if (start_sign == end_sign || end_sign == 0) {
        return( _get_sub_plane_rc( start_sign ) );
    } else if (start_sign == 0) {
        return( _get_sub_plane_rc( end_sign ) );
    } else {
        return( SUB_PLANE_NONE );
    }
}

static sub_plane_rc sub_poly_in_plane(
/************************************/
    rend_obj    *obj,
    vector      norm
) {
    int         old_sign;
    int         sign;
    int         curr_pt;
    int         num_pts;
    polygon     *poly;

    poly = rend_obj_get_poly( obj );
    num_pts = _polygon_get_num_pts( *poly );
    old_sign = 0;

    for (curr_pt = 0; curr_pt < num_pts; curr_pt++) {
        sign = sub_pt_in_plane( _polygon_get_pt( *poly, curr_pt ), norm );
        if (sign != 0) {
            if (old_sign == 0) {
                /* this is the first non-zero sign */
                old_sign = sign;
            } else if (sign != old_sign) {
                /* this sign does not agree with the first non-zero sign */
                return( SUB_PLANE_NONE );
            }
        }
    }

    return( _get_sub_plane_rc( old_sign ) );
}

static sub_plane_rc sub_obj_in_plane(
/***********************************/
/*
Subsitute the points of obj into the plane defined by norm and determine the
resulting sign. If the sign of all pts is 0 (they all lie in the plane) return
0. If the sign of all the pts is the same (and non-zero) return it. Otherwise
return 0. Since norm contains the equation of a plane dot_prod_vp of norm
and a pt substitutes that pt into the equation.
*/
    rend_obj *  obj,
    vector      norm
) {
    int         sign;

    switch (_rend_obj_get_type( obj )) {
    case REND_OBJ_PT:
        sign = sub_pt_in_plane( rend_obj_get_pt( obj, 0 ), norm );
        return( _get_sub_plane_rc( sign ) );
        break;
    case REND_OBJ_LINE:
        return( sub_line_in_plane( obj, norm ) );
        break;
    case REND_OBJ_POLY:
        return( sub_poly_in_plane( obj, norm ) );
        break;
    default:
        /* This case should not happen */
        return( SUB_PLANE_UNKNOWN );
    }
}

enum {
    HALF_SPACE_NEAR,
    HALF_SPACE_FAR,
    HALF_SPACE_SAME,            // the objects lie in the same plane
    HALF_SPACE_NONE
};
typedef unsigned check_half_space_rc;

static check_half_space_rc check_half_space(
/******************************************/
    rend_obj *  obj1,
    rend_obj *  obj2
/*
This procedure checks if obj1 is completly in one of the half spaces of
the plane of obj2. The plane of obj2 could be any plane that contains obj2
and is defined differently for different types of objects:
    point:      plane is parallel to x-y plane (i.e. norm is (0,0,1))
    line:       let  a  be vector from start to end of line
                then n (the normal vector) is give by  a x (0,1,0) or
                a x (1,0,0) if the first one = 0  (x is the vector
                cross product).
    polygon:    norm is given
The plane normal is used in homogeneous coordinates as described at the top of
pipe.h, so the D parameter is calculated after A B and C are known.

Once the plane of obj2 is known each point associated with obj1 is substituted
into the plane equation and the resulting sign is noted. If all the signs agree
then the object is completely in one or the other of the half spaces. If the
common sign agrees with the sign of the z-component of the norm then obj1 is
in the near half space; if the signs are opposite then obj1 is in the far
half space.

NOTE: This implimentation was suggested by exercise 15.6 on p. 718.
*/
) {
    vector          norm;
    sub_plane_rc    rel1;       /* relationship of obj1 to plane of obj2 */
    int             sign2_z;    /* sign of z-component of norm of obj2 */

    norm = calculate_object_norm( obj2, obj1 );

    sign2_z = _fuzzy_sign( norm.v[2], FUZZY_ZERO );
    if (sign2_z == 0) {
        /* the plane of obj2 is perpendicular to the x-y plane so has no */
        /* near or far half spaces */
        return( HALF_SPACE_NONE );
    }

    rel1 = sub_obj_in_plane( obj1, norm );

    switch (rel1) {
    case SUB_PLANE_NONE:
        return( HALF_SPACE_NONE );
        break;
    case SUB_PLANE_ZERO:
        return( HALF_SPACE_SAME );
        break;
    case SUB_PLANE_NEG:
        if (sign2_z == -1) {
            return( HALF_SPACE_NEAR );
        } else {
            return( HALF_SPACE_FAR );
        }
        break;
    case SUB_PLANE_POS:
        if (sign2_z == -1) {
            return( HALF_SPACE_FAR );
        } else {
            return( HALF_SPACE_NEAR );
        }
        break;
    default:
        /* this case should not happen */
        return( HALF_SPACE_NONE );
        break;
    }
}

static bool near_half_space(
/**************************/
/* This tests whether obj1 is completly in the near half space (as seen by */
/* the viewer) of the plane of obj2. */
    rend_obj                *obj1,
    rend_obj                *obj2
) {
    check_half_space_rc     rc;

    rc = check_half_space( obj1, obj2 );
    return( rc == HALF_SPACE_NEAR || rc == HALF_SPACE_SAME );
}

static bool far_half_space(
/*************************/
/* This tests whether obj1 is completly in the far half space (as seen by */
/* the viewer) of the plane of obj2. */
    rend_obj                *obj1,
    rend_obj                *obj2
) {
    check_half_space_rc     rc;

    rc = check_half_space( obj1, obj2 );
    return( rc == HALF_SPACE_FAR || rc == HALF_SPACE_SAME );
}

static bool proj_overlap_ln_ln(
/*****************************/
/* Tests whether 2 line objects overlap in their projection into the x-y plane*/
    rend_obj *  obj1,
    rend_obj *  obj2
) {
    point       line1[2];
    point       line2[2];

    line1[0] = rend_obj_get_pt( obj1, 0 );
    line1[1] = rend_obj_get_pt( obj1, 1 );
    line2[0] = rend_obj_get_pt( obj2, 0 );
    line2[1] = rend_obj_get_pt( obj2, 1 );

    return( proj_line_intersection( line1, line2 ) );
}

static bool proj_overlap_ln_poly(
/*******************************/
/* Test whether a line and a poly overlap in their projections */
    rend_obj *  line,
    rend_obj *  obj_poly
) {
    point       ln[2];
    point       edge[2];
    int         num_pts;
    int         curr_pt;
    polygon     *poly;

    ln[0] = rend_obj_get_pt( line, 0 );
    ln[1] = rend_obj_get_pt( line, 1 );
    poly = rend_obj_get_poly( obj_poly );

    num_pts = _polygon_get_num_pts( *poly );
    /* start with the edge between point 0 and point (num_pts-1) */
    edge[0] = _polygon_get_pt( *poly, num_pts-1 );
    for (curr_pt = 0; curr_pt < num_pts; curr_pt++) {
        edge[1] = _polygon_get_pt( *poly, curr_pt );
        if (proj_line_intersection( ln, edge )) {
            return( TRUE );
        }
        edge[0] = edge[1];
    }
    return( FALSE );
}

static bool proj_overlap_poly_poly(
/*********************************/
/* Test whether the projection into the x-y plane of two polygons overlap */
/*
    NOTE: This routine does not work the way it is supposed to. What it is
    supposed to do is to check if the intersection of the two polygons is
    non-empty. What it actually test for is whether the intersection of the
    edges is non-empty. The cases that get missed are the ones in which one
    polygon is contained in the other. One possible way to fix this would be
    to test one vertex from each polygon against the other polygon. If this
    test is performed after the edge test then a point in the other polygon
    means that the entire polygon is contained.

    One posible source of a method to carry out this testing could be
        Preparata, F. P., and M. I. Shamos. "Computational Geometry:
                An Introduction". Springer-Verlag, New York, 1985.
    I have not seen this book but the title suggests that it may contain
    what we need.

    S.Bosnick
*/