SGI Developer Toolbox 6.1/SGI Developer Toolbox 6.1 - Disc 4.iso/src/exampleCode/inventor/noodle/Triangulator.c++

C/C++ Source or Header | 1994-08-02 | 18.9 KB | 486 lines

/*
 * Copyright (C) 1994, Silicon Graphics, Inc.
 * All Rights Reserved.
 *
 * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
 * the contents of this file may not be disclosed to third parties, copied or
 * duplicated in any form, in whole or in part, without the prior written
 * permission of Silicon Graphics, Inc.
 *
 * RESTRICTED RIGHTS LEGEND:
 * Use, duplication or disclosure by the Government is subject to restrictions
 * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
 * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
 * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
 * rights reserved under the Copyright Laws of the United States.
 */
//
// Code for a Generalized Cylinder class.  This is not really very
// robust or well-designed (or complete or...).
//

#include <stdio.h>
#include <Inventor/SbLinear.h>
#include <Inventor/fields/SoMFLong.h>
#include <Inventor/fields/SoMFVec3f.h>

#include "Triangulator.h"



//**********************************************************************
//
// Returns FALSE if the two line segments intersect each other at only
// one point.
// Returns TRUE if they are parallel or if they intersect at a point
//    external to either line segment.
//
//    Assumes that the four points lie in the y = 0 plane.
//
//**********************************************************************

SbBool
Triangulator::triangEdgeTest(const SoMFVec3f &coords,
                long e0p0, long e0p1,  long e1p0,  long e1p1 )
{
    float x00 = coords[(int) e0p0][0];
    float x10 = coords[(int) e1p0][0];
    float z00 = coords[(int) e0p0][2];
    float z10 = coords[(int) e1p0][2];

    float dx0 = coords[(int) e0p1][0] - x00;
    float dx1 = coords[(int) e1p1][0] - x10;
    float dz0 = coords[(int) e0p1][2] - z00;
    float dz1 = coords[(int) e1p1][2] - z10;

    float diffx = x10 - x00;
    float diffz = z10 - z00;

    float determ = dx0 * -dz1 - dz0 * -dx1;

    if (determ == 0) // lines are parallel
        return( TRUE );

    // otherwise, solve for intersection point
    // first, solve for parametric length on edge 1 from e0p0 to e0p1
    float parametric_val = (-dz1 * diffx + dx1 * diffz) / determ;

#define SMALL_VAL        0.00001

    if (parametric_val > 1.0 - SMALL_VAL  || parametric_val < SMALL_VAL)
        // value lies outside line segment
        return( TRUE );

    // next, solve for parametric length on edge 1 from e1p0 to e1p1
    parametric_val = (-dz0 * diffx + dx0 * diffz) / determ;

    if (parametric_val > 1.0 - SMALL_VAL || parametric_val < SMALL_VAL)
        // value lies outside line segment
        return( TRUE );

#undef SMALL_VAL

    // otherwise, intersection point lies within both segments
    return(FALSE);
}

SbBool
Triangulator::clockWiseTest( const SoMFVec3f &coords,
             const SoMFLong &indices, int startVert, int numVerts )
{
    // ARE THE COORDS GIVEN BY THIS POLYGON CLOCKWISE ORDERED WHEN VIEWED
    // FROM ABOVE?
    // ASSUME THAT ALL THE POINTS LIE IN THE Y=0 PLANE.
    // How do we know? Well, the total of the interior angles
    // for an n-sided polygon is:
    //         interior_angles = (PI * n) - (2 * PI)
    // while:
    //        exterior_angles = (PI * n) + (2 * PI)
    // So we total up the interior angles, and reverse the
    // order of the vertices if it is the wrong amount
    float angle_total = 0;
    for( int vNum = 0; vNum < numVerts; vNum++ ) {
    int nextP = (vNum == numVerts - 1) ? 0 : vNum + 1;
    int prevP = (vNum == 0) ? numVerts - 1 : vNum - 1;
    SbVec3f nextEdge = coords[(int) indices[startVert + nextP]] -
               coords[(int) indices[startVert + vNum]];
    SbVec3f prevEdge = coords[(int) indices[startVert + prevP]] -
               coords[(int) indices[startVert + vNum]];
    nextEdge.normalize();
    prevEdge.normalize();

    // WE WANT ALL ANGLES IN THE SENSE OF ROTATING ABOUT THE
    // POSITIVE Y AXIS
    SbVec3f crossProd = prevEdge.cross( nextEdge );
    if (crossProd[1] > 0.0) {
        angle_total += acos( prevEdge.dot( nextEdge ) );
    }
    else {
        angle_total += 2 * M_PI - acos( prevEdge.dot( nextEdge ) );
    }
    }
    if (  angle_total > M_PI * numVerts )
    return FALSE;
    else
    return TRUE;
}

//**********************************************************************
//
// Returns TRUE if the first point lies inside the triangle formed by
//    the other three.
//
// Assumes that all of the points lie in the plane y = 0
// Assumes that the triangle is ordered clockwise when viewed from above
// when travelling in the order: pt0 to pt1 to pt2
//
// Performs the check by doing a cross product between edges of the
// triangle and vectors connecting the vertices to the test point.
// If the point is inside the triangle, the cross products are positive.
// If any are negative, the point lies outside the trianggle.
// We only need to check the y values of the cross product, since the
// points lie in a horizontal plane.
//**********************************************************************

SbBool
Triangulator::triangInsideTest( const SoMFVec3f &coords,
                 long testPt, long pt0, long pt1, long pt2)
{
    SbVec3f edge0 = coords[(int)pt1] - coords[(int)pt0];
    SbVec3f edge1 = coords[(int)pt2] - coords[(int)pt1];
    SbVec3f edge2 = coords[(int)pt0] - coords[(int)pt2];

    SbVec3f ptEdge0 = coords[(int)testPt] - coords[(int)pt0];
    SbVec3f ptEdge1 = coords[(int)testPt] - coords[(int)pt1];
    SbVec3f ptEdge2 = coords[(int)testPt] - coords[(int)pt2];

#define TEENY_VAL        0.0000001

    if (     ptEdge0[2] * edge0[0] - ptEdge0[0] * edge0[2] > TEENY_VAL
      &&    ptEdge1[2] * edge1[0] - ptEdge1[0] * edge1[2] > TEENY_VAL
      &&    ptEdge2[2] * edge2[0] - ptEdge2[0] * edge2[2] > TEENY_VAL)
        return( TRUE );
    else
        return( FALSE );

#undef TEENY_VAL

}

//**********************************************************************
//
// 1] assume all points lie in the y = 0 plane
// 2] perform triangulation on the projected polygon, copy the order later
// 3] for each point, find two others that form a triangle which meets
//      the following conditions:
//        a] Doesn't cut through any other edges
//        b] Any new edges are on the interior
//
//**********************************************************************

SbBool
Triangulator::triangulate(
            const SoMFVec3f &coords,
                const SoMFLong  &inVals, // indices describing the input
                             // polygons
                SoMFLong  &outVals) // indices describing the output
                       // polygons
{
    // CHECK THAT ALL COORDS LIE IN THE y = 0.0 PLANE
    for( int i = 0; i < coords.getNum(); i++ ){
    if ( coords[i][1] != 0.0 ) {
        fprintf(stderr,"Error in triangulation: not all points \n");
        fprintf(stderr,"  lie in the y = 0 plane\n");
        return FALSE;
    }
    }

    // COPY THE INPUT INTO THE OUTPUT
    if ( outVals.getNum() < inVals.getNum() )
     outVals.insertSpace( 0, inVals.getNum() - outVals.getNum());
    else if ( outVals.getNum() > inVals.getNum() )
          outVals.deleteValues( 0, outVals.getNum() - inVals.getNum());
    outVals = inVals;


    int curInd0 = 0;
    int curNumVerts = 0;

    SbBool     got_a_tri, tri_ok, keep_going;
    SbVec3f    edge2, edge0, prevEdge, nextEdge;
    int        ind0, ind1, ind2, test_ind0, test_ind1;
    int        vNum;

    //***** WALK DOWN THE LIST OF POLYS *****

    int shift_count = 0;

    for ( curInd0 = 0; curInd0 < outVals.getNum(); ) {
    for( int j = curInd0, curNumVerts = 0; j < outVals.getNum(); j++ ) {
        if ( outVals[j] >= 0 )
        curNumVerts++;
        else
        break;
    }

    // IF ANY THREE CONSECUTIVE POINTS ARE COLINEAR, REMOVE THE
    // CENTER POINT
    // Note: we don't have to check that there are three points.
    // The algorithm will just wind up removing all the points
    // if there are two or less, or if all the points in the polygon
    // are colinear.
    for( vNum = 0; vNum < curNumVerts; vNum++ ) {
        int nextP = (vNum == curNumVerts - 1) ? 0 : vNum +1;
        int prevP = (vNum == 0) ? curNumVerts - 1 : vNum - 1;
        nextEdge = coords[(int) outVals[curInd0 + nextP]] -
               coords[(int) outVals[curInd0 + vNum]];
        prevEdge = coords[(int) outVals[curInd0 + prevP]] -
               coords[(int) outVals[curInd0 + vNum]];

        // CROSS PRODUCT IS ZERO IF THEY ARE CO-LINEAR
        SbVec3f crossProd = prevEdge.cross( nextEdge );

#define TEENY_VAL        0.0000001
#define IS_COORD_TEENY(a)  ( (a)[0] < TEENY_VAL && (a)[1] < TEENY_VAL \
              && (a)[2] < TEENY_VAL && (a)[0] > -TEENY_VAL \
              && (a)[1] > -TEENY_VAL && (a)[2] > -TEENY_VAL )

        if (IS_COORD_TEENY( crossProd) ) {
        // remove the index of this point from the poly
        outVals.deleteValues( curInd0 + vNum, 1);

        curNumVerts--;

        vNum--;  // decrement, because everyone's been shifted
             // down by 1
        }
#undef TEENY_VAL
#undef IS_COORD_TEENY
    }

    if ( curNumVerts == 0) {
        // The polygon has no vertices (this could happen because the
        // whole polygon was colinear and got removed in the step above.)
        // Remove the '-1' index that signals the end of the polygon.
        outVals.deleteValues( curInd0, 1 );

        // Do not increment curInd0. By removing the '-1' entry, the
        // next polygon moves up a slot to have *ITS* first index at
        // curInd0.
    }
    else if ( curNumVerts <= 3) {
        // Just move on to the next polygon.
        // (We add an extra 1, because each polygon has a
        // extra index entry of -1 to indicate the end of the poly
        curInd0 += curNumVerts + 1;
    }
    else {

        // REVERSE ORDER IF NECESSARY
        if ( !clockWiseTest( coords, outVals, curInd0, curNumVerts) ) {
        long *outIndices = outVals.startEditing();

        long tempI, early, late;
        for ( early = 0, late = curNumVerts - 1;
              early < late; early++, late-- ) {
            tempI = outIndices[curInd0 + early];
            outIndices[curInd0 + early] = outIndices[curInd0 + late];
            outIndices[curInd0 + late] = tempI;
        }

        outVals.finishEditing();
            }

            // find a triangle formed by the first point and two other points
            // The new triangle must satisfy the condition that no new
            // Edges intersect any already existing edges in the polygon
            ind0 = curInd0;
            keep_going = TRUE;
            for (ind1 = curInd0 + 1, ind2 = curInd0 + 2, got_a_tri = FALSE;
                 got_a_tri == FALSE && keep_going == TRUE;   ) {
                // TEST EACH NEW EDGE AGAINST ALL OTHER EDGES
                tri_ok = TRUE;

                // make sure ordering of new triangle is clockwise
                // Normal points down if (edge2 cross edge0)[1] < 0.0
                edge2 = coords[(int)outVals[ind2]] - coords[(int)outVals[ind0]];
                edge0 = coords[(int)outVals[ind1]] - coords[(int)outVals[ind0]];
                if (edge0[0] * edge2[2] - edge2[0] * edge0[2] < 0.0)
                    tri_ok = FALSE;

                // make sure no other points fall inside the newly formed
                // triangle
                if (tri_ok == TRUE) {
                    for( vNum = curInd0; vNum < curInd0 + curNumVerts; vNum++) {
                        if (vNum != ind0 && vNum != ind1 && vNum != ind2) {
                            if ( triangInsideTest(coords,outVals[vNum],outVals[ind0], outVals[ind1], outVals[ind2]))
                                tri_ok = FALSE;
                        }
                    }
                }

                // edge between ind0 and ind1
                if (ind1 != curInd0 + 1) {
                    // edge between point0 and point1 is ok, since part of
                    // original polygon
                    for( test_ind0 = curInd0, test_ind1 = curInd0 + 1;
                         tri_ok == TRUE && test_ind0 < curInd0 + curNumVerts;
                         test_ind0++, test_ind1++) {
                        if (test_ind1 == curInd0 + curNumVerts)
                            test_ind1 = curInd0;
                        tri_ok = triangEdgeTest(coords, outVals[ind0], outVals[ind1],
                                    outVals[test_ind0], outVals[test_ind1]);
                    }
                }

                // edge between ind1 and ind2 is part of the original polygon
                // except when forming tri between v0, v1, and final point
                if (ind2 != ind1 + 1) {
                    for( test_ind0 = curInd0, test_ind1 = curInd0 + 1;
                         tri_ok == TRUE && test_ind0 < curInd0 + curNumVerts;
                         test_ind0++, test_ind1++) {
                        if (test_ind1 == curInd0 + curNumVerts)
                            test_ind1 = curInd0;
                        tri_ok = triangEdgeTest(coords, outVals[ind1], outVals[ind2],
                                    outVals[test_ind0], outVals[test_ind1]);
                    }
                }

                // edge between ind2 and ind0
                if (ind2 != curInd0 + curNumVerts -1) {
                    // edge between point0 and last point in poly is ok,since
                    // part of original polygon
                    for( test_ind0 = curInd0, test_ind1 = curInd0 + 1;
                         tri_ok == TRUE && test_ind0 < curInd0 + curNumVerts;
                         test_ind0++, test_ind1++) {
                        if (test_ind1 == curInd0 + curNumVerts)
                            test_ind1 = curInd0;
                        tri_ok = triangEdgeTest(coords, outVals[ind2], outVals[ind0],
                                    outVals[test_ind0], outVals[test_ind1]);
                    }
                }
                if (tri_ok == TRUE)
                    got_a_tri = TRUE;
                else {
                    if (ind1 == curInd0 + 1 && ind2 == curInd0 + curNumVerts -1)
                        keep_going = FALSE;
                    ind1++;
                    ind2++;
                    if (ind2 == curInd0 + curNumVerts) {
                        // If none others worked, try the case where the
                        // the points are first, second, and last
                        ind1 = curInd0 + 1;
                        ind2 = curInd0 + curNumVerts - 1;
                    }
                }
            }

            if (got_a_tri == FALSE) {
                // Could not draw a triangle using the first vertex.
                // Shift all of the vertices in the polygon over and try again
                shift_count++;

        long *outIndices = outVals.startEditing();

                long temp_index = outIndices[ curInd0 + 0];

                for( vNum = curInd0; vNum < curInd0 + curNumVerts - 1; vNum++ )
                    outIndices[ vNum] = outIndices[ vNum + 1];
                outIndices[ curInd0 + curNumVerts - 1] = temp_index;

        outVals.finishEditing();

                if (shift_count >= curNumVerts) {
                    printf("Error: could not triangulate this polygon\n");
                    printf("It may look funny!\n");
            return(FALSE );
                }

        // Do not increment the value of curInd0.
        // This will mean that the 'for' loop will repeat the entire
        // process on this polygon (but THIS time, the indices have
        // been shifted in order.
            }
            else {

                shift_count = 0;

                // Create a new triangle which connects the first point
                // to these two new points
        // Add this new triangle to the end of the outVals

        long newIndices[4];
        newIndices[0] = outVals[ ind0];
        newIndices[1] = outVals[ ind1];
        newIndices[2] = outVals[ ind2];
        newIndices[3] = -1;

        outVals.setValues( outVals.getNum(), 4, newIndices );

                // Make necessary changes to the old polygon
                if (ind1 == curInd0 + 1 && ind2 == curInd0 + curNumVerts - 1) {
                    // triangle was first, second, and last points
                    // we need to get rid of first point in the current poly
            outVals.deleteValues( curInd0, 1);
                    curNumVerts--;
                }
                else if (ind1 == curInd0 + 1) {
                    // triangle was first three points
                    // we need to get rid of second point
            outVals.deleteValues( curInd0 + 1, 1 );
                    curNumVerts --;
                }
                else if (ind2 == curNumVerts - 1) {
                    // triangle was last three points
            // we need to get rid of last point
            outVals.deleteValues( curInd0 + curNumVerts - 1, 1 );
                    curNumVerts --;
                }
                else {
                    // we need to break the poly into 2, since we just created
                    // an interior-type triangle
                    // The first polygon will go from ind0 to ind1
                    // and will reside in the original polygon data structure
                    // The second will continue from ind2 back to ind0
                    // and will be added to the end of outVals.

            // FIRST, ADD THE LATTER POLY TO THE END OF outVals...

            int newPolNumVerts = curInd0 + curNumVerts - ind2 + 1;

            // Add an extra slot for the '-1' which signifies end
            // of polygon
            int newPolInd0 = outVals.getNum();
            outVals.insertSpace( newPolInd0, newPolNumVerts + 1 );

            long *outIndices = outVals.startEditing();
            // Copy the points from ind2 to the end of the poly
            for ( int j = newPolInd0, vNum = ind2;
              vNum < curInd0 + curNumVerts; j++, vNum++ ) {
              outIndices[j] = outIndices[vNum];
            }
            // Copy the initial point...
            outIndices[newPolInd0 + newPolNumVerts - 1]
            = outIndices[curInd0];

            // Add the -1 to signify the end
            outIndices[newPolInd0 + newPolNumVerts] = -1;

            outVals.finishEditing();


            // NEXT, REMOVE THE LATTER HALF OF  THE FIRST POLY...
            outVals.deleteValues( ind2, newPolNumVerts - 1 );

                    // Reduce the num of coords being used from the original
                    // polygon
                    curNumVerts -= newPolNumVerts - 1;
                }
            }
        }
    }

    return TRUE;
}