Return to Triangulator.c++ CVS log

Up to [Development] / inventor / apps / nodes / GeneralizedCylinder

Initial check-in based on 2.1.5 (SGI IRIX) source tree.

/*
 *
 *  Copyright (C) 2000 Silicon Graphics, Inc.  All Rights Reserved. 
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  Further, this software is distributed without any warranty that it is
 *  free of the rightful claim of any third person regarding infringement
 *  or the like.  Any license provided herein, whether implied or
 *  otherwise, applies only to this software file.  Patent licenses, if
 *  any, provided herein do not apply to combinations of this program with
 *  other software, or any other product whatsoever.
 * 
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 *  Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
 *  Mountain View, CA  94043, or:
 * 
 *  http://www.sgi.com 
 * 
 *  For further information regarding this notice, see: 
 * 
 *  http://oss.sgi.com/projects/GenInfo/NoticeExplan/
 *
 */

//
// 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/SoMFInt32.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, 
				int32_t e0p0, int32_t e0p1,  int32_t e1p0,  int32_t 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 SoMFInt32 &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, 
				 int32_t testPt, int32_t pt0, int32_t pt1, int32_t 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 SoMFInt32  &inVals, // indices describing the input
					         // polygons
		        SoMFInt32  &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(); ) {
	int j;
	for( 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) ) {
		int32_t *outIndices = outVals.startEditing();

		int32_t 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++;

		int32_t *outIndices = outVals.startEditing();

                int32_t 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

		int32_t 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 ); 

		    int32_t *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;
}