/*
*
* 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;
}
![[BACK]](/icons/back.gif){kind=icon}
Return to Triangulator.c++ CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [Development] / inventor / apps / nodes / GeneralizedCylinder