0001: /*
0002: * $RCSfile: Triangulator.java,v $
0003: *
0004: * Copyright (c) 2007 Sun Microsystems, Inc. All rights reserved.
0005: *
0006: * Redistribution and use in source and binary forms, with or without
0007: * modification, are permitted provided that the following conditions
0008: * are met:
0009: *
0010: * - Redistribution of source code must retain the above copyright
0011: * notice, this list of conditions and the following disclaimer.
0012: *
0013: * - Redistribution in binary form must reproduce the above copyright
0014: * notice, this list of conditions and the following disclaimer in
0015: * the documentation and/or other materials provided with the
0016: * distribution.
0017: *
0018: * Neither the name of Sun Microsystems, Inc. or the names of
0019: * contributors may be used to endorse or promote products derived
0020: * from this software without specific prior written permission.
0021: *
0022: * This software is provided "AS IS," without a warranty of any
0023: * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
0024: * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
0025: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
0026: * EXCLUDED. SUN MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL
0027: * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF
0028: * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
0029: * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR
0030: * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL,
0031: * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND
0032: * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR
0033: * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
0034: * POSSIBILITY OF SUCH DAMAGES.
0035: *
0036: * You acknowledge that this software is not designed, licensed or
0037: * intended for use in the design, construction, operation or
0038: * maintenance of any nuclear facility.
0039: *
0040: * $Revision: 1.4 $
0041: * $Date: 2007/02/09 17:20:21 $
0042: * $State: Exp $
0043: */
0044:
0045: // ----------------------------------------------------------------------
0046: //
0047: // The reference to Fast Industrial Strength Triangulation (FIST) code
0048: // in this release by Sun Microsystems is related to Sun's rewrite of
0049: // an early version of FIST. FIST was originally created by Martin
0050: // Held and Joseph Mitchell at Stony Brook University and is
0051: // incorporated by Sun under an agreement with The Research Foundation
0052: // of SUNY (RFSUNY). The current version of FIST is available for
0053: // commercial use under a license agreement with RFSUNY on behalf of
0054: // the authors and Stony Brook University. Please contact the Office
0055: // of Technology Licensing at Stony Brook, phone 631-632-9009, for
0056: // licensing information.
0057: //
0058: // ----------------------------------------------------------------------
0059: package com.sun.j3d.utils.geometry;
0060:
0061: import javax.vecmath.*;
0062: import java.util.*;
0063: import com.sun.j3d.utils.geometry.GeometryInfo;
0064: import com.sun.j3d.internal.J3dUtilsI18N;
0065:
0066: /**
0067: * Triangulator is a utility for turning arbitrary polygons into triangles
0068: * so they can be rendered by Java 3D.
0069: * Polygons can be concave, nonplanar, and can contain holes.
0070: * @see GeometryInfo
0071: */
0072: public class Triangulator extends Object {
0073:
0074: GeometryInfo gInfo = null;
0075:
0076: int faces[] = null;
0077: int loops[] = null;
0078: int chains[] = null;
0079: Point2f points[] = null;
0080: Triangle triangles[] = null;
0081: ListNode list[] = null;
0082:
0083: Random randomGen = null;
0084:
0085: int numPoints = 0;
0086: int maxNumPoints = 0;
0087: int numList = 0;
0088: int maxNumList = 0;
0089: int numLoops = 0;
0090: int maxNumLoops = 0;
0091: int numTriangles = 0;
0092: int maxNumTriangles = 0;
0093:
0094: int numFaces = 0;
0095: int numTexSets = 0;
0096: // int maxNumFaces = 0;
0097:
0098: int firstNode = 0;
0099:
0100: int numChains = 0;
0101: int maxNumChains = 0;
0102:
0103: // For Clean class.
0104: Point2f[] pUnsorted = null;
0105: int maxNumPUnsorted = 0;
0106:
0107: // For NoHash class.
0108: boolean noHashingEdges = false;
0109: boolean noHashingPnts = false;
0110: int loopMin, loopMax;
0111: PntNode vtxList[] = null;
0112: int numVtxList = 0;
0113: int numReflex = 0;
0114: int reflexVertices;
0115:
0116: // For Bridge class.
0117: Distance distances[] = null;
0118: int maxNumDist = 0;
0119: Left leftMost[] = null;
0120: int maxNumLeftMost = 0;
0121:
0122: // For Heap class.
0123: HeapNode heap[] = null;
0124: int numHeap = 0;
0125: int maxNumHeap = 0;
0126: int numZero = 0;
0127:
0128: // For Orientation class.
0129: int maxNumPolyArea = 0;
0130: double polyArea[] = null;
0131:
0132: int stripCounts[] = null;
0133: int vertexIndices[] = null;
0134: Point3f vertices[] = null;
0135: Object colors[] = null;
0136: Vector3f normals[] = null;
0137:
0138: boolean ccwLoop = true;
0139:
0140: boolean earsRandom = true;
0141: boolean earsSorted = true;
0142:
0143: int identCntr; // Not sure what is this for. (Ask Martin)
0144:
0145: // double epsilon = 1.0e-12;
0146: double epsilon = 1.0e-12;
0147:
0148: static final double ZERO = 1.0e-8;
0149: static final int EARS_SEQUENCE = 0;
0150: static final int EARS_RANDOM = 1;
0151: static final int EARS_SORTED = 2;
0152:
0153: static final int INC_LIST_BK = 100;
0154: static final int INC_LOOP_BK = 20;
0155: static final int INC_TRI_BK = 50;
0156: static final int INC_POINT_BK = 100;
0157: static final int INC_DIST_BK = 50;
0158:
0159: private static final int DEBUG = 0;
0160:
0161: /**
0162: * Creates a new instance of the Triangulator.
0163: * @deprecated This class is created automatically when needed in
0164: * GeometryInfo and never needs to be used directly. Putting data
0165: * into a GeometryInfo with primitive POLYGON_ARRAY automatically
0166: * causes the triangulator to be created and used.
0167: */
0168: public Triangulator() {
0169: earsRandom = false;
0170: earsSorted = false;
0171: }
0172:
0173: /**
0174: * Creates a new instance of a Triangulator.
0175: * @deprecated This class is created automatically when needed in
0176: * GeometryInfo and never needs to be used directly. Putting data
0177: * into a GeometryInfo with primitive POLYGON_ARRAY automatically
0178: * causes the triangulator to be created and used.
0179: */
0180: public Triangulator(int earOrder) {
0181: switch (earOrder) {
0182: case EARS_SEQUENCE:
0183: earsRandom = false;
0184: earsSorted = false;
0185: break;
0186: case EARS_RANDOM:
0187: randomGen = new Random();
0188: earsRandom = true;
0189: earsSorted = false;
0190: break;
0191: case EARS_SORTED:
0192: earsRandom = false;
0193: earsSorted = true;
0194: break;
0195: default:
0196: earsRandom = false;
0197: earsSorted = false;
0198: }
0199:
0200: }
0201:
0202: /**
0203: * This routine converts the GeometryInfo object from primitive type
0204: * POLYGON_ARRAY to primitive type TRIANGLE_ARRAY using polygon
0205: * decomposition techniques.
0206: * <p>
0207: * <pre>
0208: * Example of usage:
0209: * Triangulator tr = new Triangulator();
0210: * tr.triangulate(ginfo); // ginfo contains the geometry.
0211: * shape.setGeometry(ginfo.getGeometryArray()); // shape is a Shape3D.
0212: *<p></pre>
0213: * @param gi Geometry to be triangulated
0214: **/
0215: public void triangulate(GeometryInfo gi) {
0216: int i, j, k;
0217: int sIndex = 0, index, currLoop, lastInd, ind;
0218: boolean proceed;
0219: boolean reset = false, troubles = false;
0220:
0221: boolean done[] = new boolean[1];
0222: boolean gotIt[] = new boolean[1];
0223:
0224: if (gi.getPrimitive() != GeometryInfo.POLYGON_ARRAY) {
0225: throw new IllegalArgumentException(J3dUtilsI18N
0226: .getString("Triangulator0"));
0227: }
0228:
0229: gi.indexify();
0230:
0231: vertices = gi.getCoordinates();
0232: if (vertices != null)
0233: vertexIndices = gi.getCoordinateIndices();
0234: else
0235: vertexIndices = null;
0236:
0237: colors = gi.getColors();
0238: normals = gi.getNormals();
0239: this .gInfo = gi;
0240:
0241: stripCounts = gi.getStripCounts();
0242:
0243: faces = gi.getContourCounts();
0244: if (faces == null) {
0245: if (stripCounts == null)
0246: System.out
0247: .println("StripCounts is null! Don't know what to do.");
0248:
0249: faces = new int[stripCounts.length];
0250: for (i = 0; i < stripCounts.length; i++)
0251: faces[i] = 1;
0252: }
0253:
0254: numFaces = faces.length;
0255: numTexSets = gInfo.getTexCoordSetCount();
0256:
0257: // For debugging ...
0258: /*
0259: System.out.println("Faces (number " + faces.length + ") : ");
0260: for(i=0; i<faces.length; i++) {
0261: System.out.println(faces[i] + ", ");
0262: }
0263:
0264: System.out.println("StripCounts (number " + stripCounts.length + ") : ");
0265: for(i=0; i<stripCounts.length; i++) {
0266: System.out.println(stripCounts[i] + ", ");
0267: }
0268:
0269: System.out.println("Vertices (number " + vertices.length + ") : ");
0270: for(i=0; i<vertices.length; i++) {
0271: System.out.println(i + " x " + vertices[i].x + " y " + vertices[i].y +
0272: " z " + vertices[i].z);
0273: }
0274:
0275:
0276: System.out.println("VertexIndices (number " + vertexIndices.length + ") : ");
0277:
0278: for(i=0; i<vertexIndices.length; i++) {
0279: System.out.print(vertexIndices[i] + ", ");
0280: }
0281: */
0282:
0283: maxNumLoops = 0;
0284: maxNumList = 0;
0285: maxNumPoints = 0;
0286: maxNumDist = 0;
0287: maxNumLeftMost = 0;
0288: maxNumPUnsorted = 0;
0289:
0290: // Compute the length of loops and list.
0291: for (i = 0; i < faces.length; i++) {
0292: maxNumLoops += faces[i];
0293: for (j = 0; j < faces[i]; j++, sIndex++) {
0294: maxNumList += (stripCounts[sIndex] + 1);
0295: }
0296: }
0297:
0298: // Add some incase of bridges.
0299: maxNumList += 20;
0300:
0301: loops = new int[maxNumLoops];
0302: list = new ListNode[maxNumList];
0303: // maxNumPoints = vertices.length;
0304: //points = new Point2f[maxNumPoints];
0305:
0306: // Construct data for use in triangulation.
0307: numVtxList = 0;
0308: numReflex = 0;
0309:
0310: numTriangles = 0;
0311: numChains = 0;
0312: numPoints = 0;
0313: numLoops = 0;
0314: numList = 0;
0315: sIndex = 0;
0316: index = 0;
0317:
0318: for (i = 0; i < faces.length; i++) {
0319: for (j = 0; j < faces[i]; j++, sIndex++) {
0320:
0321: currLoop = makeLoopHeader();
0322: lastInd = loops[currLoop];
0323:
0324: for (k = 0; k < stripCounts[sIndex]; k++) {
0325: list[numList] = new ListNode(vertexIndices[index]);
0326: ind = numList++;
0327:
0328: insertAfter(lastInd, ind);
0329: list[ind].setCommonIndex(index);
0330:
0331: lastInd = ind;
0332: index++;
0333:
0334: } // index k.
0335:
0336: deleteHook(currLoop);
0337:
0338: } // index j.
0339: } // index i.
0340:
0341: // Done with constructing data. We can start to triangulate now.
0342:
0343: maxNumTriangles = maxNumList / 2;
0344: triangles = new Triangle[maxNumTriangles];
0345:
0346: // set the numerical precision threshold
0347: setEpsilon(ZERO);
0348:
0349: // process the polygonal faces of the polyhedron. for every face, we
0350: // check whether it is a triangle or a quadrangle in order to weed out
0351: // simple cases which do not require the full triangulation algorithm
0352:
0353: /*
0354: for(i=0; i<numLoops; i++)
0355: System.out.println("loops[" + i + "] " + loops[i]);
0356: printListData();
0357: */
0358:
0359: int i1 = 0;
0360: int i2 = 0;
0361: for (j = 0; j < numFaces; ++j) {
0362: ccwLoop = true;
0363: done[0] = false;
0364: i2 = i1 + faces[j];
0365:
0366: if (faces[j] > 1) {
0367: proceed = true;
0368: } else if (Simple.simpleFace(this , loops[i1]))
0369: proceed = false;
0370: else
0371: proceed = true;
0372:
0373: if (proceed) {
0374:
0375: // Do some preprocessing here.
0376:
0377: // System.out.println("faces["+j+"] "+faces[j]);
0378: for (int lpIndex = 0; lpIndex < faces[j]; lpIndex++)
0379: preProcessList(i1 + lpIndex);
0380:
0381: // project the polygonal face onto a plane
0382: Project.projectFace(this , i1, i2);
0383:
0384: // sort the points of this face in lexicographic order and discard
0385: // duplicates
0386:
0387: // System.out.println("Before cleaning ...");
0388: // printListData();
0389:
0390: int removed = Clean.cleanPolyhedralFace(this , i1, i2);
0391:
0392: // For debugging.
0393: /*
0394: System.out.println("After cleaning ...");
0395: printListData();
0396:
0397: System.out.println("\n***** " + removed +
0398: " duplicate points removed for face " +
0399: i1 + " *****\n");
0400: */
0401:
0402: // determine the orientation of the polygon; the default
0403: // orientation is CCW for the outer polygon
0404: if (faces[j] == 1) {
0405: // System.out.println("determineOrientation");
0406: Orientation.determineOrientation(this , loops[i1]);
0407: } else {
0408: // System.out.println("adjustOrientation");
0409: Orientation.adjustOrientation(this , i1, i2);
0410: }
0411:
0412: // CE2 only
0413: if (faces[j] > 1) {
0414: NoHash.prepareNoHashEdges(this , i1, i2);
0415: } else {
0416: noHashingEdges = false;
0417: noHashingPnts = false;
0418: }
0419:
0420: // mark those vertices whose interior angle is convex
0421: for (i = i1; i < i2; ++i) {
0422: EarClip.classifyAngles(this , loops[i]);
0423: }
0424:
0425: /*
0426: System.out.println("After classifyAngles ...");
0427: printListData();
0428: */
0429:
0430: // link the holes with the outer boundary by means of "bridges"
0431: if (faces[j] > 1)
0432: Bridge.constructBridges(this , i1, i2);
0433:
0434: // put all ears into a circular linked list
0435: resetPolyList(loops[i1]);
0436: NoHash.prepareNoHashPnts(this , i1);
0437: EarClip.classifyEars(this , loops[i1]);
0438: done[0] = false;
0439:
0440: /*
0441: System.out.println("Before clipEar (List)...");
0442: printListData();
0443: System.out.println("Before clipEar (vtxList)...");
0444: printVtxList();
0445:
0446: int counter = 0;
0447: */
0448:
0449: // triangulate the polygon
0450: while (!done[0]) {
0451: if (!EarClip.clipEar(this , done)) {
0452: /*
0453: System.out.println(" (False case) clipEar (vtxList)...");
0454: printListData();
0455: printVtxList();
0456: */
0457:
0458: if (reset) {
0459: // For debugging.
0460:
0461: // System.out.println("***** no further ear to clip! ***** \n");
0462: // System.out.println("***** not a simple polygon, isn't it? *****\n");
0463:
0464: ind = getNode();
0465: resetPolyList(ind);
0466:
0467: loops[i1] = ind;
0468: if (Desperate
0469: .desperate(this , ind, i1, done)) {
0470: // System.out.println("***** let's hope for the best *****\n");
0471: if (!Desperate.letsHope(this , ind)) {
0472: /*
0473: System.out.println("***** sorry, I can't do it! ***** \n");
0474: System.out.println("***** ask a triangulation wizard, or ");
0475: System.out.println("clean-up your polyhedron! ***** \n");
0476: */
0477: return;
0478: }
0479: } else {
0480: reset = false;
0481: }
0482: } else {
0483: // try again from scratch
0484: troubles = true;
0485: // System.out.println("\n***** re-classifying the ears! ***** \n");
0486: ind = getNode();
0487: resetPolyList(ind);
0488:
0489: // System.out.println("Before classifyEars(" + ind + ")");
0490: // printListData();
0491:
0492: EarClip.classifyEars(this , ind);
0493: reset = true;
0494: }
0495: } else {
0496: reset = false;
0497: /*
0498: System.out.println(" (True case) clipEar (vtxList)...");
0499:
0500: printVtxList();
0501: */
0502:
0503: }
0504:
0505: if (done[0]) {
0506: // System.out.println("In done[0] is true");
0507: ind = getNextChain(gotIt);
0508: if (gotIt[0]) {
0509: // at some point of the triangulation, we could not find
0510: // any ear and the polygon was split into two parts. now
0511: // we have to handle (one of) the remaining parts.
0512: resetPolyList(ind);
0513: loops[i1] = ind;
0514: noHashingPnts = false;
0515: NoHash.prepareNoHashPnts(this , i1);
0516: EarClip.classifyEars(this , ind);
0517: reset = false;
0518: done[0] = false;
0519: }
0520: }
0521: }
0522: }
0523:
0524: i1 = i2;
0525:
0526: }
0527:
0528: /*
0529: if (troubles)
0530: System.out.println("\n\nTriangulation completed!\n");
0531: else
0532: System.out.println("\n\nTriangulation successfully completed!\n");
0533: */
0534: // System.out.println("\n...writing the output data: ");
0535: // Output triangles here.
0536: writeTriangleToGeomInfo();
0537:
0538: }
0539:
0540: void printVtxList() {
0541: int i;
0542: System.out.println("numReflex " + numReflex
0543: + " reflexVertices " + reflexVertices);
0544: for (i = 0; i < numVtxList; i++)
0545: System.out.println(i + " pnt " + vtxList[i].pnt + ", next "
0546: + vtxList[i].next);
0547:
0548: }
0549:
0550: void printListData() {
0551: for (int i = 0; i < numList; i++)
0552: System.out.println("list[" + i + "].index " + list[i].index
0553: + ", prev " + list[i].prev + ", next "
0554: + list[i].next + ", convex " + list[i].convex
0555: + ", vertexIndex " + list[i].vcntIndex);
0556:
0557: }
0558:
0559: void preProcessList(int i1) {
0560: int tInd, tInd1, tInd2;
0561:
0562: resetPolyList(loops[i1]);
0563: tInd = loops[i1];
0564: tInd1 = tInd;
0565: tInd2 = list[tInd1].next;
0566: while (tInd2 != tInd) {
0567: if (list[tInd1].index == list[tInd2].index) {
0568: if (tInd2 == loops[i1])
0569: loops[i1] = list[tInd2].next;
0570: deleteLinks(tInd2);
0571: }
0572: tInd1 = list[tInd1].next;
0573: tInd2 = list[tInd1].next;
0574: }
0575:
0576: }
0577:
0578: void writeTriangleToGeomInfo() {
0579: int i, currIndex;
0580:
0581: // There are 2 approaches to take here : (1) Output all triangles as
0582: // a single face.(Easy) (2) Preserve the faces of the polyhedron and
0583: // sets of triangles per face. ( Seems to be the preferred approach, but
0584: // a check in GeometryInfo and the old GeomInfoConverter doesn't seems
0585: // to support this. Will check with Dan and Paul. Will take the easy way first.
0586:
0587: // For debugging ....
0588: if (DEBUG == 1) {
0589: System.out.println("List (number " + numList + ") : ");
0590: for (i = 0; i < numList; i++) {
0591: System.out.println("index " + list[i].index + " prev "
0592: + list[i].prev + " next " + list[i].next
0593: + " convex " + list[i].convex);
0594: System.out.println(" vertexIndex " + list[i].vcntIndex
0595: + " colorIndex " + list[i].vcntIndex
0596: + " normalIndex " + list[i].vcntIndex
0597: + " textureIndex " + list[i].vcntIndex);
0598: }
0599:
0600: System.out.println("Points (number " + numPoints + ") : ");
0601:
0602: for (i = 0; i < numPoints; i++) {
0603: System.out.println("x " + points[i].x + " y "
0604: + points[i].y);
0605: }
0606:
0607: System.out.println("Triangles (number " + numTriangles
0608: + ") : ");
0609:
0610: for (i = 0; i < numTriangles; i++) {
0611: System.out.println("v1 " + triangles[i].v1 + " v2 "
0612: + triangles[i].v2 + " v3 " + triangles[i].v3);
0613: }
0614: }
0615:
0616: gInfo.setPrimitive(GeometryInfo.TRIANGLE_ARRAY);
0617: gInfo.setContourCounts(null);
0618: gInfo.forgetOldPrim();
0619: gInfo.setStripCounts(null);
0620:
0621: currIndex = 0;
0622: int newVertexIndices[] = new int[numTriangles * 3];
0623: int index;
0624: for (i = 0; i < numTriangles; i++) {
0625: index = list[triangles[i].v1].getCommonIndex();
0626: newVertexIndices[currIndex++] = vertexIndices[index];
0627: index = list[triangles[i].v2].getCommonIndex();
0628: newVertexIndices[currIndex++] = vertexIndices[index];
0629: index = list[triangles[i].v3].getCommonIndex();
0630: newVertexIndices[currIndex++] = vertexIndices[index];
0631: }
0632: gInfo.setCoordinateIndices(newVertexIndices);
0633:
0634: /*
0635: for(i=0;i<newVertexIndices.length;) {
0636: System.out.println("v1 " + newVertexIndices[i++] +
0637: ", v2 " + newVertexIndices[i++] +
0638: ", v3 " + newVertexIndices[i++]);
0639: }
0640:
0641: System.out.println("Pysical point:");
0642: for(i=0;i<newVertexIndices.length;) {
0643: System.out.println("v1 " + vertices[newVertexIndices[i++]] +
0644: ", v2 " + vertices[newVertexIndices[i++]] +
0645: ", v3 " + vertices[newVertexIndices[i++]]);
0646: }
0647: */
0648:
0649: if (normals != null) {
0650: int oldNormalIndices[] = gInfo.getNormalIndices();
0651: int newNormalIndices[] = new int[numTriangles * 3];
0652: currIndex = 0;
0653: for (i = 0; i < numTriangles; i++) {
0654: index = list[triangles[i].v1].getCommonIndex();
0655: newNormalIndices[currIndex++] = oldNormalIndices[index];
0656: index = list[triangles[i].v2].getCommonIndex();
0657: newNormalIndices[currIndex++] = oldNormalIndices[index];
0658: index = list[triangles[i].v3].getCommonIndex();
0659: newNormalIndices[currIndex++] = oldNormalIndices[index];
0660: }
0661: gInfo.setNormalIndices(newNormalIndices);
0662: }
0663:
0664: if (colors != null) {
0665: currIndex = 0;
0666: int oldColorIndices[] = gInfo.getColorIndices();
0667: int newColorIndices[] = new int[numTriangles * 3];
0668: for (i = 0; i < numTriangles; i++) {
0669: index = list[triangles[i].v1].getCommonIndex();
0670: newColorIndices[currIndex++] = oldColorIndices[index];
0671: index = list[triangles[i].v2].getCommonIndex();
0672: newColorIndices[currIndex++] = oldColorIndices[index];
0673: index = list[triangles[i].v3].getCommonIndex();
0674: newColorIndices[currIndex++] = oldColorIndices[index];
0675: }
0676: gInfo.setColorIndices(newColorIndices);
0677: }
0678:
0679: for (int j = 0; j < numTexSets; j++) {
0680: int newTextureIndices[] = new int[numTriangles * 3];
0681: int oldTextureIndices[] = gInfo
0682: .getTextureCoordinateIndices(j);
0683: currIndex = 0;
0684: for (i = 0; i < numTriangles; i++) {
0685: index = list[triangles[i].v1].getCommonIndex();
0686: newTextureIndices[currIndex++] = oldTextureIndices[index];
0687: index = list[triangles[i].v2].getCommonIndex();
0688: newTextureIndices[currIndex++] = oldTextureIndices[index];
0689: index = list[triangles[i].v3].getCommonIndex();
0690: newTextureIndices[currIndex++] = oldTextureIndices[index];
0691: }
0692: gInfo.setTextureCoordinateIndices(j, newTextureIndices);
0693: }
0694: }
0695:
0696: void setEpsilon(double eps) {
0697: epsilon = eps;
0698: }
0699:
0700: // Methods of handling ListNode.
0701:
0702: boolean inPolyList(int ind) {
0703: return ((ind >= 0) && (ind < numList) && (numList <= maxNumList));
0704: }
0705:
0706: void updateIndex(int ind, int index) {
0707: // assert(InPolyList(ind));
0708: list[ind].index = index;
0709: }
0710:
0711: int getAngle(int ind) {
0712: return list[ind].convex;
0713: }
0714:
0715: void setAngle(int ind, int convex) {
0716: list[ind].convex = convex;
0717: }
0718:
0719: void resetPolyList(int ind) {
0720: // assert(InPolyList(ind));
0721: firstNode = ind;
0722: }
0723:
0724: int getNode() {
0725: // assert(InPolyList(first_node));
0726: return firstNode;
0727: }
0728:
0729: boolean inLoopList(int loop) {
0730: return ((loop >= 0) && (loop < numLoops) && (numLoops <= maxNumLoops));
0731: }
0732:
0733: void deleteHook(int currLoop) {
0734: int ind1, ind2;
0735:
0736: if (inLoopList(currLoop) == false)
0737: System.out
0738: .println("Triangulator:deleteHook : Loop access out of range.");
0739:
0740: ind1 = loops[currLoop];
0741: ind2 = list[ind1].next;
0742: if ((inPolyList(ind1)) && (inPolyList(ind2))) {
0743:
0744: deleteLinks(ind1);
0745: loops[currLoop] = ind2;
0746:
0747: } else
0748: System.out
0749: .println("Triangulator:deleteHook : List access out of range.");
0750: }
0751:
0752: /**
0753: * Deletes node ind from list (with destroying its data fields)
0754: */
0755: void deleteLinks(int ind) {
0756:
0757: if ((inPolyList(ind)) && (inPolyList(list[ind].prev))
0758: && (inPolyList(list[ind].next))) {
0759:
0760: if (firstNode == ind)
0761: firstNode = list[ind].next;
0762:
0763: list[list[ind].next].prev = list[ind].prev;
0764: list[list[ind].prev].next = list[ind].next;
0765: list[ind].prev = list[ind].next = ind;
0766:
0767: } else
0768: System.out
0769: .println("Triangulator:deleteLinks : Access out of range.");
0770:
0771: }
0772:
0773: void rotateLinks(int ind1, int ind2) {
0774: int ind;
0775: int ind0, ind3;
0776:
0777: // assert(InPolyList(ind1));
0778: // assert(InPolyList(ind2));
0779: ind0 = list[ind1].next;
0780: ind3 = list[ind2].next;
0781: // assert(InPolyList(ind0));
0782: // assert(InPolyList(ind3));
0783:
0784: // Swap.
0785: ind = list[ind1].next;
0786: list[ind1].next = list[ind2].next;
0787: list[ind2].next = ind;
0788:
0789: list[ind0].prev = ind2;
0790: list[ind3].prev = ind1;
0791:
0792: }
0793:
0794: void storeChain(int ind) {
0795: if (numChains >= maxNumChains) {
0796: // System.out.println("Triangulator:storeChain Expanding chain array ...");
0797: maxNumChains += 20;
0798: int old[] = chains;
0799: chains = new int[maxNumChains];
0800: if (old != null)
0801: System.arraycopy(old, 0, chains, 0, old.length);
0802: }
0803: chains[numChains] = ind;
0804: ++numChains;
0805:
0806: }
0807:
0808: int getNextChain(boolean[] done) {
0809: if (numChains > 0) {
0810: done[0] = true;
0811: --numChains;
0812: return chains[numChains];
0813: } else {
0814: done[0] = false;
0815: numChains = 0;
0816: return 0;
0817: }
0818: }
0819:
0820: void splitSplice(int ind1, int ind2, int ind3, int ind4) {
0821: list[ind1].next = ind4;
0822: list[ind4].prev = ind1;
0823: list[ind2].prev = ind3;
0824: list[ind3].next = ind2;
0825:
0826: }
0827:
0828: /**
0829: * Allocates storage for a dummy list node; pointers are set to itself.
0830: * @return pointer to node
0831: */
0832: int makeHook() {
0833: int ind;
0834:
0835: ind = numList;
0836: if (numList >= maxNumList) {
0837: maxNumList += INC_LIST_BK;
0838: // System.out.println("Triangulator: Expanding list array ....");
0839: ListNode old[] = list;
0840: list = new ListNode[maxNumList];
0841: System.arraycopy(old, 0, list, 0, old.length);
0842: }
0843:
0844: list[numList] = new ListNode(-1);
0845: list[numList].prev = ind;
0846: list[numList].next = ind;
0847: list[numList].index = -1;
0848: ++numList;
0849:
0850: return ind;
0851: }
0852:
0853: int makeLoopHeader() {
0854: int i;
0855: int ind;
0856:
0857: ind = makeHook();
0858: if (numLoops >= maxNumLoops) {
0859: maxNumLoops += INC_LOOP_BK;
0860: // System.out.println("Triangulator: Expanding loops array ....");
0861: int old[] = loops;
0862: loops = new int[maxNumLoops];
0863: System.arraycopy(old, 0, loops, 0, old.length);
0864: }
0865:
0866: loops[numLoops] = ind;
0867: i = numLoops;
0868: ++numLoops;
0869:
0870: return i;
0871: }
0872:
0873: /**
0874: * Allocates storage for a new list node, and stores the index of the point
0875: * at this node. Pointers are set to -1.
0876: * @return pointer to node
0877: */
0878: int makeNode(int index) {
0879: int ind;
0880:
0881: if (numList >= maxNumList) {
0882: maxNumList += INC_LIST_BK;
0883: //System.out.println("Triangulator: Expanding list array ....");
0884: ListNode old[] = list;
0885: list = new ListNode[maxNumList];
0886: System.arraycopy(old, 0, list, 0, old.length);
0887: }
0888:
0889: list[numList] = new ListNode(index);
0890:
0891: ind = numList;
0892: list[numList].index = index;
0893: list[numList].prev = -1;
0894: list[numList].next = -1;
0895: ++numList;
0896:
0897: return ind;
0898: }
0899:
0900: /**
0901: * Inserts node ind2 after node ind1.
0902: */
0903: void insertAfter(int ind1, int ind2) {
0904: int ind3;
0905:
0906: if ((inPolyList(ind1)) && (inPolyList(ind2))) {
0907:
0908: list[ind2].next = list[ind1].next;
0909: list[ind2].prev = ind1;
0910: list[ind1].next = ind2;
0911: ind3 = list[ind2].next;
0912:
0913: if (inPolyList(ind3))
0914: list[ind3].prev = ind2;
0915: else
0916: System.out
0917: .println("Triangulator:deleteHook : List access out of range.");
0918:
0919: return;
0920: } else
0921: System.out
0922: .println("Triangulator:deleteHook : List access out of range.");
0923:
0924: }
0925:
0926: /**
0927: * Returns pointer to the successor of ind1.
0928: */
0929: int fetchNextData(int ind1) {
0930: return list[ind1].next;
0931: }
0932:
0933: /**
0934: * obtains the data store at ind1
0935: */
0936: int fetchData(int ind1) {
0937: return list[ind1].index;
0938: }
0939:
0940: /**
0941: * returns pointer to the successor of ind1.
0942: */
0943: int fetchPrevData(int ind1) {
0944: return list[ind1].prev;
0945: }
0946:
0947: /**
0948: * swap the list pointers in order to change the orientation.
0949: */
0950: void swapLinks(int ind1) {
0951: int ind2, ind3;
0952:
0953: ind2 = list[ind1].next;
0954: list[ind1].next = list[ind1].prev;
0955: list[ind1].prev = ind2;
0956: ind3 = ind2;
0957: while (ind2 != ind1) {
0958: ind3 = list[ind2].next;
0959: list[ind2].next = list[ind2].prev;
0960: list[ind2].prev = ind3;
0961: ind2 = ind3;
0962: }
0963: }
0964:
0965: // Methods for handling Triangle.
0966:
0967: void storeTriangle(int i, int j, int k) {
0968: /*
0969: if (ccwLoop)
0970: triangles.add(new Triangle(i,j,k));
0971: else
0972: triangles.add(new Triangle(j,i,k));
0973: */
0974:
0975: if (numTriangles >= maxNumTriangles) {
0976: // System.out.println("Triangulator:storeTriangle Expanding triangle array..");
0977: maxNumTriangles += INC_TRI_BK;
0978: Triangle old[] = triangles;
0979: triangles = new Triangle[maxNumTriangles];
0980: if (old != null)
0981: System.arraycopy(old, 0, triangles, 0, old.length);
0982: }
0983:
0984: if (ccwLoop)
0985: triangles[numTriangles] = new Triangle(i, j, k);
0986: else
0987: triangles[numTriangles] = new Triangle(j, i, k);
0988: numTriangles++;
0989:
0990: }
0991:
0992: // Methods for handling Point.
0993:
0994: void initPnts(int number) {
0995: if (maxNumPoints < number) {
0996: maxNumPoints = number;
0997: points = new Point2f[maxNumPoints];
0998: }
0999:
1000: for (int i = 0; i < number; i++)
1001: points[i] = new Point2f(0.0f, 0.0f);
1002:
1003: numPoints = 0;
1004: }
1005:
1006: boolean inPointsList(int index) {
1007: return ((index >= 0) && (index < numPoints) && (numPoints <= maxNumPoints));
1008: }
1009:
1010: int storePoint(double x, double y) {
1011: int i;
1012:
1013: if (numPoints >= maxNumPoints) {
1014: // System.out.println("Triangulator:storePoint Expanding points array ...");
1015: maxNumPoints += INC_POINT_BK;
1016: Point2f old[] = points;
1017: points = new Point2f[maxNumPoints];
1018: if (old != null)
1019: System.arraycopy(old, 0, points, 0, old.length);
1020: }
1021:
1022: points[numPoints] = new Point2f((float) x, (float) y);
1023: // points[numPoints].x = (float)x;
1024: // points[numPoints].y = (float)y;
1025: i = numPoints;
1026: ++numPoints;
1027:
1028: return i;
1029: }
1030:
1031: }
|