0001: /*
0002: * $RCSfile: Stripifier.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:20 $
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 com.sun.j3d.utils.geometry.GeometryInfo;
0062: import java.util.LinkedList;
0063: import java.util.ArrayList;
0064: import com.sun.j3d.internal.J3dUtilsI18N;
0065:
0066: /**
0067: * The Stripifier utility will change the primitive of the GeometryInfo
0068: * object to Triangle Strips. The strips are made by analyzing the
0069: * triangles in the original data and connecting them together.<p>
0070: * <p>
0071: * Normal Generation should be performed on the GeometryInfo object
0072: * <i>before</i> Stripification, for best results. Example:<p>
0073: * <p>
0074: * <pre>
0075: * GeometryInfo gi = new GeometryInfo(TRIANGLE_ARRAY);
0076: * gi.setCoordinates(coordinateData);
0077: *
0078: * NormalGenerator ng = new NormalGenerator();
0079: * ng.generateNormals(gi);
0080: *
0081: * Stripifier st = new Stripifier()
0082: * st.stripify(gi);
0083: *
0084: * Shape3D part = new Shape3D();
0085: * part.setAppearance(appearance);
0086: * part.setGeometry(gi.getGeometryArray());
0087: * </pre>
0088: */
0089: public class Stripifier {
0090:
0091: final boolean DEBUG = false;
0092: final boolean CHECK_ORIENT = false;
0093:
0094: static final int EMPTY = -1;
0095:
0096: boolean hasNormals = false;
0097: boolean hasTextures = false;
0098: int texSetCount = 0;
0099: boolean hasColors = false;
0100: boolean colorStrips = false;
0101:
0102: StripifierStats stats;
0103:
0104: int[] numNhbrs;
0105:
0106: /**
0107: * Indicates to the stripifier to collect statistics on the data
0108: */
0109: public static final int COLLECT_STATS = 0x01;
0110:
0111: /**
0112: * Creates the Stripifier object.
0113: */
0114: public Stripifier() {
0115: }
0116:
0117: /**
0118: * Creates the Stripifier object.
0119: * @param flags Flags
0120: * @since Java 3D 1.2.1
0121: */
0122: public Stripifier(int flags) {
0123: if ((flags & COLLECT_STATS) != 0) {
0124: stats = new StripifierStats();
0125: }
0126: }
0127:
0128: /**
0129: * Converts the geometry contained in the GeometryInfo object into an
0130: * array of triangle strips.
0131: */
0132: public void stripify(GeometryInfo gi) {
0133: // System.out.println("stripify");
0134: long time = System.currentTimeMillis();
0135: // setup
0136: gi.convertToIndexedTriangles();
0137: gi.forgetOldPrim();
0138:
0139: // write out the gi object
0140: // System.out.println("write out the object");
0141: // gi.writeObj();
0142:
0143: Face[] faces = createFaceArray(gi);
0144: Edge[] edges = createEdgeArray(faces);
0145: buildAdjacencies(edges, faces);
0146:
0147: // print out the adjacency information
0148: if (DEBUG) {
0149: for (int i = 0; i < faces.length; i++) {
0150: faces[i].printVertices();
0151: }
0152: System.out.println("");
0153: for (int i = 0; i < faces.length; i++) {
0154: faces[i].printAdjacency();
0155: }
0156: System.out.println("");
0157: }
0158:
0159: Node[] faceNodes = new Node[faces.length];
0160: // Node[] queue = hybridSearch(faces, faceNodes);
0161: Node[] queue = dfSearch(faces, faceNodes);
0162:
0163: // print out the queue
0164: if (DEBUG) {
0165: for (int i = 0; i < queue.length; i++) {
0166: queue[i].print();
0167: }
0168: System.out.println("");
0169: }
0170:
0171: // int "pointers" for the numbers of strips and patches from
0172: // hamiliton
0173: int[] ns = new int[1];
0174: int[] np = new int[1];
0175: ArrayList hamiltons = hamilton(queue, ns, np);
0176: int numStrips = ns[0];
0177: int numPatches = np[0];
0178:
0179: // print out the hamiltonians
0180: if (DEBUG) {
0181: for (int i = 0; i < hamiltons.size(); i++) {
0182: System.out.println("Hamiltonian: " + i);
0183: ArrayList list = (ArrayList) hamiltons.get(i);
0184: for (int j = 0; j < list.size(); j++) {
0185: Face face = (Face) list.get(j);
0186: face.printVertices();
0187: }
0188: System.out.println("");
0189: }
0190: }
0191:
0192: // now make strips out of the hamiltonians
0193: ArrayList strips = stripe(hamiltons);
0194:
0195: // print out the strips
0196: if (DEBUG) {
0197: for (int i = 0; i < strips.size(); i++) {
0198: System.out.println("Strip: " + i);
0199: Istream istream = (Istream) strips.get(i);
0200: for (int j = 0; j < istream.length; j++) {
0201: System.out.println("vertex: "
0202: + istream.istream[j].index);
0203: }
0204: System.out.println("");
0205: }
0206: }
0207:
0208: // concatenate the strips
0209: concatenate(strips, faces);
0210:
0211: // print out the new strips
0212: if (DEBUG) {
0213: System.out.println("");
0214: System.out.println("concatenated strips: ("
0215: + (strips.size()) + ")");
0216: System.out.println("");
0217: for (int i = 0; i < strips.size(); i++) {
0218: System.out.println("Strip: " + i);
0219: Istream istream = (Istream) strips.get(i);
0220: for (int j = 0; j < istream.length; j++) {
0221: System.out.println("vertex: "
0222: + istream.istream[j].index);
0223: }
0224: System.out.println("");
0225: }
0226: }
0227:
0228: // put the stripified data into the GeometryInfo object
0229: putBackData(gi, strips);
0230:
0231: // System.out.println("time: " + (System.currentTimeMillis()-time));
0232: // System.out.println("");
0233:
0234: // add to stats
0235: if (stats != null) {
0236: stats.updateInfo(System.currentTimeMillis() - time, strips,
0237: faces.length);
0238: }
0239:
0240: // Stat.printInfo();
0241:
0242: // print out strip count info
0243: // System.out.println("numStrips = " + strips.size());
0244: // System.out.println("stripCounts:");
0245: // int avg = 0;
0246: // for (int i = 0; i < strips.size(); i++) {
0247: // System.out.print(((Istream)strips.get(i)).length + " ");
0248: // avg += ((Istream)strips.get(i)).length;
0249: // }
0250: // System.out.println("Avg: " + ((double)avg/(double)strips.size()));
0251: }
0252:
0253: /**
0254: * Prints out statistical information for the stripifier: the number of
0255: * original triangles, the number of original vertices, the number of
0256: * strips created, the number of vertices, the total number of triangles,
0257: * the minimum strip length (in # of tris) the maximum strip length
0258: * (in number of tris), the average strip length (in # of tris), the
0259: * average number of vertices per triangle, the total time it took to
0260: * stripify, and the strip length (how many strips of a given length.
0261: * The data is cumulative over all the times the stripifier is called
0262: * until the stats are printed, and then they are reset.
0263: */
0264: // public static void printStats() {
0265: // // stats.toString();
0266: // }
0267: /**
0268: * Returns the stripifier stats object.
0269: * @exception IllegalStateException if the Stripfier has not
0270: * been constructed
0271: * with the COLLECT_STATS flag
0272: * @since Java 3D 1.2.1
0273: */
0274: public StripifierStats getStripifierStats() {
0275: if (stats == null) {
0276: throw new IllegalStateException(J3dUtilsI18N
0277: .getString("Stripifier0"));
0278: }
0279: return stats;
0280: }
0281:
0282: /**
0283: * Creates an array of faces from the geometry in the GeometryInfo object.
0284: */
0285: Face[] createFaceArray(GeometryInfo gi) {
0286: int[] vertices = gi.getCoordinateIndices();
0287: int[] normals = gi.getNormalIndices();
0288:
0289: int[][] textures = null;
0290: int[] t1 = null;
0291: int[] t2 = null;
0292: int[] t3 = null;
0293: texSetCount = gi.getTexCoordSetCount();
0294: if (texSetCount > 0) {
0295: hasTextures = true;
0296: textures = new int[texSetCount][];
0297: for (int i = 0; i < texSetCount; i++) {
0298: textures[i] = gi.getTextureCoordinateIndices(i);
0299: }
0300: t1 = new int[texSetCount];
0301: t2 = new int[texSetCount];
0302: t3 = new int[texSetCount];
0303: } else
0304: hasTextures = false;
0305:
0306: int[] colors = gi.getColorIndices();
0307: Face[] faces = new Face[vertices.length / 3];
0308: int n1, n2, n3, c1, c2, c3;
0309: Vertex v1, v2, v3;
0310: int count = 0;
0311: for (int i = 0; i < vertices.length;) {
0312: if (normals != null) {
0313: // System.out.println("hasNormals");
0314: hasNormals = true;
0315: n1 = normals[i];
0316: n2 = normals[i + 1];
0317: n3 = normals[i + 2];
0318: } else {
0319: // System.out.println("doesn't have normals");
0320: hasNormals = false;
0321: n1 = EMPTY;
0322: n2 = EMPTY;
0323: n3 = EMPTY;
0324: }
0325: if (hasTextures) {
0326: for (int j = 0; j < texSetCount; j++) {
0327: t1[j] = textures[j][i];
0328: t2[j] = textures[j][(i + 1)];
0329: t3[j] = textures[j][(i + 2)];
0330: }
0331: }
0332: if (colors != null) {
0333: hasColors = true;
0334: c1 = colors[i];
0335: c2 = colors[i + 1];
0336: c3 = colors[i + 2];
0337: } else {
0338: hasColors = false;
0339: c1 = EMPTY;
0340: c2 = EMPTY;
0341: c3 = EMPTY;
0342: }
0343: v1 = new Vertex(vertices[i], n1, texSetCount, t1, c1);
0344: v2 = new Vertex(vertices[i + 1], n2, texSetCount, t2, c2);
0345: v3 = new Vertex(vertices[i + 2], n3, texSetCount, t3, c3);
0346: if (!v1.equals(v2) && !v2.equals(v3) && !v3.equals(v1)) {
0347: faces[count] = new Face(count, v1, v2, v3);
0348: count++;
0349: }
0350: i += 3;
0351: }
0352:
0353: if (faces.length > count) {
0354: Face[] temp = faces;
0355: faces = new Face[count];
0356: System.arraycopy(temp, 0, faces, 0, count);
0357: }
0358: return faces;
0359: }
0360:
0361: /**
0362: * Creates an array of edges from the Face array.
0363: */
0364: Edge[] createEdgeArray(Face[] faces) {
0365: Edge[] edges = new Edge[faces.length * 3];
0366: Face face;
0367: for (int i = 0; i < faces.length; i++) {
0368: face = faces[i];
0369: edges[i * 3] = new Edge(face.verts[0], face.verts[1],
0370: face.key);
0371: edges[i * 3 + 1] = new Edge(face.verts[1], face.verts[2],
0372: face.key);
0373: edges[i * 3 + 2] = new Edge(face.verts[2], face.verts[0],
0374: face.key);
0375: }
0376: return edges;
0377: }
0378:
0379: /**
0380: * Builds the adjacency graph by finding the neighbors of the edges
0381: */
0382: void buildAdjacencies(Edge[] edges, Face[] faces) {
0383: // sortEdges(edges);
0384: quickSortEdges(edges, 0, edges.length - 1);
0385: // int i = 1;
0386:
0387: // set up the edge list of each face
0388: Edge edge;
0389: Face face;
0390: Vertex[] verts;
0391: boolean flag;
0392: int k;
0393: for (int i = 0; i < edges.length; i++) {
0394: // edges are kept in order s.t. the ith edge is the opposite
0395: // edge of the ith vertex
0396: edge = edges[i];
0397: face = faces[edge.face];
0398: verts = face.verts;
0399:
0400: flag = true;
0401: if ((!verts[0].equals(edge.v1))
0402: && (!verts[0].equals(edge.v2))) {
0403: face.edges[0] = edge;
0404: face.numNhbrs--;
0405: flag = false;
0406: } else if ((!verts[1].equals(edge.v1))
0407: && (!verts[1].equals(edge.v2))) {
0408: face.edges[1] = edge;
0409: face.numNhbrs--;
0410: flag = false;
0411: } else if ((!verts[2].equals(edge.v1))
0412: && (!verts[2].equals(edge.v2))) {
0413: face.edges[2] = edge;
0414: face.numNhbrs--;
0415: flag = false;
0416: } else {
0417: if (DEBUG)
0418: System.out.println("error!!! Stripifier.buildAdj");
0419: }
0420:
0421: // handle degenerencies
0422: if (flag) {
0423: Vertex i1;
0424: // triangle degenerated to a point
0425: if ((edge.v1).equals(edge.v2)) {
0426: face.edges[--face.numNhbrs] = edge;
0427: }
0428: // triangle degenerated to an edge
0429: else {
0430: if (verts[0].equals(verts[1])) {
0431: i1 = verts[1];
0432: } else {
0433: i1 = verts[2];
0434: }
0435: if (verts[0].equals(i1) && face.edges[0] == null) {
0436: face.edges[0] = edge;
0437: face.numNhbrs--;
0438: } else if (verts[1].equals(i1)
0439: && face.edges[1] == null) {
0440: face.edges[1] = edge;
0441: face.numNhbrs--;
0442: } else {
0443: face.edges[2] = edge;
0444: face.numNhbrs--;
0445: }
0446: }
0447: }
0448: }
0449:
0450: // build the adjacency information by pairing up every two triangles
0451: // that share the same edge
0452: int i = 0;
0453: int j = 0;
0454: int j1, j2;
0455: while (i < (edges.length - 1)) {
0456: j = i + 1;
0457: if (edges[i].equals(edges[j])) {
0458: // determine the orientations of the common edge in the two
0459: // adjacent triangles. Only set them to be adjacent if they
0460: // are opposite
0461: j1 = edges[i].face;
0462: j2 = edges[j].face;
0463: if (j1 != j2) { // set up the two faces as neighbors
0464: edge = edges[i];
0465: face = faces[j1];
0466: k = face.getEdgeIndex(edge);
0467: if ((edge.v1.equals(face.verts[(k + 1) % 3]))
0468: && (edge.v2.equals(face.verts[(k + 2) % 3]))) {
0469: flag = false;
0470: } else
0471: flag = true;
0472:
0473: edge = edges[j];
0474: face = faces[j2];
0475: k = face.getEdgeIndex(edge);
0476: if ((edge.v1.equals(face.verts[(k + 1) % 3]))
0477: && (edge.v2.equals(face.verts[(k + 2) % 3]))) {
0478: flag = flag;
0479: } else
0480: flag = (!flag);
0481:
0482: if (flag) {
0483: edges[i].face = j2;
0484: edges[j].face = j1;
0485: (faces[j1].numNhbrs)++;
0486: (faces[j2].numNhbrs)++;
0487: j++;
0488: } else
0489: edges[i].face = EMPTY;
0490: } else
0491: edges[i].face = EMPTY;
0492: } else
0493: edges[i].face = EMPTY;
0494: i = j;
0495: }
0496: if (i <= (edges.length - 1))
0497: edges[i].face = EMPTY;
0498:
0499: // check, for each face, if it is duplicated. For a face that
0500: // neighbors its duplicate in the adjacency graph, it's possible
0501: // that two or more of its neighbors are the same (the duplicate).
0502: // This will be corrected to avoid introducing redundant faces
0503: // later on
0504:
0505: for (i = 0; i < faces.length; i++) {
0506: face = faces[i];
0507: if (face.numNhbrs == 3) {
0508: if ((j1 = face.edges[1].face) == face.edges[0].face) {
0509: face.edges[1].face = EMPTY;
0510: face.numNhbrs--;
0511: faces[j1].counterEdgeDel(face.edges[1]);
0512: }
0513: if ((j2 = face.edges[2].face) == face.edges[0].face) {
0514: face.edges[2].face = EMPTY;
0515: face.numNhbrs--;
0516: faces[j2].counterEdgeDel(face.edges[2]);
0517: }
0518: if ((face.edges[1].face != EMPTY) && (j1 == j2)) {
0519: face.edges[2].face = EMPTY;
0520: face.numNhbrs--;
0521: faces[j1].counterEdgeDel(face.edges[2]);
0522: }
0523: }
0524: }
0525: }
0526:
0527: /**
0528: * Sorts the edges using BubbleSort
0529: */
0530: void sortEdges(Edge[] edges) {
0531: int i = edges.length;
0532: boolean sorted = false;
0533: Edge temp = null;
0534: while ((i > 1) && !sorted) {
0535: sorted = true;
0536: for (int j = 1; j < i; j++) {
0537: if (edges[j].lessThan(edges[j - 1])) {
0538: temp = edges[j - 1];
0539: edges[j - 1] = edges[j];
0540: edges[j] = temp;
0541: sorted = false;
0542: }
0543: }
0544: i--;
0545: }
0546: }
0547:
0548: /**
0549: * uses quicksort to sort the edges
0550: */
0551: void quickSortEdges(Edge[] edges, int l, int r) {
0552: if (edges.length > 0) {
0553: int i = l;
0554: int j = r;
0555: Edge k = edges[(l + r) / 2];
0556:
0557: do {
0558: while (edges[i].lessThan(k))
0559: i++;
0560: while (k.lessThan(edges[j]))
0561: j--;
0562: if (i <= j) {
0563: Edge tmp = edges[i];
0564: edges[i] = edges[j];
0565: edges[j] = tmp;
0566: i++;
0567: j--;
0568: }
0569: } while (i <= j);
0570:
0571: if (l < j)
0572: quickSortEdges(edges, l, j);
0573: if (l < r)
0574: quickSortEdges(edges, i, r);
0575: }
0576: }
0577:
0578: /**
0579: * Takes a list of faces as input and performs a hybrid search, a
0580: * variated depth first search that returns to the highest level node
0581: * not yet fully explored. Returns an array of pointers to the faces
0582: * found in order from the search. The faceNodes parameter is an
0583: * array of the Nodes created for the faces.
0584: */
0585: Node[] hybridSearch(Face[] faces, Node[] faceNodes) {
0586:
0587: int numFaces = faces.length;
0588: int i = 0, j = 0, k = 0, ind = 0;
0589:
0590: // keep # of faces with certain # of neighbors
0591: int[] count = { 0, 0, 0, 0 };
0592:
0593: // faces sorted by number of neighbors
0594: int[] index = new int[numFaces];
0595: // the index of a certain face in the sorted array
0596: int[] rindex = new int[numFaces];
0597:
0598: // Control list pop up operation
0599: boolean popFlag = false;
0600:
0601: // queue of pointers to faces found in search
0602: Node[] queue = new Node[numFaces];
0603: // root of depth first tree
0604: Node source;
0605: // for the next node
0606: Node nnode;
0607: // a face
0608: Face face;
0609: // starting position for insertion into the list
0610: int start = 0;
0611: // list for search
0612: SortedList dlist;
0613:
0614: // count how many faces have a certain # of neighbors and
0615: // create a Node for each face
0616: for (i = 0; i < numFaces; i++) {
0617: j = faces[i].numNhbrs;
0618: count[j]++;
0619: faceNodes[i] = new Node(faces[i]);
0620: }
0621:
0622: // to help with sorting
0623: for (i = 1; i < 4; i++) {
0624: count[i] += count[i - 1];
0625: }
0626:
0627: // decreasing i to make sorting stable
0628: for (i = numFaces - 1; i >= 0; i--) {
0629: j = faces[i].numNhbrs;
0630: count[j]--;
0631: index[count[j]] = i;
0632: rindex[i] = count[j];
0633: }
0634:
0635: // start the hybrid search
0636: for (i = 0; i < numFaces; i++) {
0637: if (index[i] != EMPTY) {
0638: dlist = new SortedList();
0639: source = faceNodes[index[i]];
0640: source.setRoot();
0641: queue[ind] = source;
0642: ind++;
0643: index[i] = EMPTY;
0644:
0645: while (source != null) {
0646: nnode = null;
0647: // use the first eligible for continuing search
0648: face = source.face;
0649: for (j = 0; j < 3; j++) {
0650: k = face.getNeighbor(j);
0651: if ((k != EMPTY)
0652: && (faceNodes[k].notAccessed())) {
0653: nnode = faceNodes[k];
0654: break;
0655: }
0656: }
0657:
0658: if (nnode != null) {
0659: // insert the new node
0660: nnode.insert(source);
0661: if (!popFlag) {
0662: start = dlist.sortedInsert(source, start);
0663: } else
0664: popFlag = false;
0665: source = nnode;
0666: queue[ind] = source;
0667: ind++;
0668: index[rindex[k]] = EMPTY;
0669: } else {
0670: source.processed();
0671: source = dlist.pop();
0672: popFlag = true;
0673: start = 0;
0674: }
0675: } // while -- does popFlag need to be set to false here?
0676: }
0677: }
0678: return queue;
0679: }
0680:
0681: Node[] dfSearch(Face[] faces, Node[] faceNodes) {
0682: int numFaces = faces.length;
0683: int i = 0, j = 0, k = 0, ind = 0;
0684:
0685: // keep certain # of faces with certain # of neighbors
0686: int[] count = { 0, 0, 0, 0 };
0687:
0688: // faces sorted by # of neighbors
0689: int[] index = new int[numFaces];
0690: // index of a certain face in the sorted array
0691: int[] rindex = new int[numFaces];
0692:
0693: // queue of pointers to faces found in the search
0694: Node[] queue = new Node[numFaces];
0695: // root of the depth first tree
0696: Node source;
0697: // the current node
0698: Node node;
0699: // for the next Node
0700: Node nnode;
0701: // a face
0702: Face face;
0703:
0704: // count how many faces have a certain # of neighbors and create
0705: // a Node for each face
0706: for (i = 0; i < numFaces; i++) {
0707: j = faces[i].numNhbrs;
0708: count[j]++;
0709: faceNodes[i] = new Node(faces[i]);
0710: }
0711:
0712: // to help with sorting
0713: for (i = 1; i < 4; i++)
0714: count[i] += count[i - 1];
0715:
0716: // dec i to make sorting stable
0717: for (i = numFaces - 1; i >= 0; i--) {
0718: j = faces[i].numNhbrs;
0719: count[j]--;
0720: index[count[j]] = i;
0721: rindex[i] = count[j];
0722: }
0723:
0724: setNumNhbrs(faces);
0725: // start the dfs
0726: for (i = 0; i < numFaces; i++) {
0727: if (index[i] != EMPTY) {
0728: source = faceNodes[index[i]];
0729: source.setRoot();
0730: queue[ind] = source;
0731: ind++;
0732: index[i] = EMPTY;
0733: node = source;
0734:
0735: do {
0736: // if source has been done, stop
0737: if ((node == source) && (node.right != null))
0738: break;
0739:
0740: nnode = null;
0741: face = node.face;
0742:
0743: // for (j = 0; j < 3; j++) {
0744: // if (((k = face.getNeighbor(j)) != EMPTY) &&
0745: // (faceNodes[k].notAccessed())) {
0746: // nnode = faceNodes[k];
0747: // break;
0748: // }
0749: // }
0750:
0751: k = findNext(node, faceNodes, faces);
0752: if (k != EMPTY)
0753: nnode = faceNodes[k];
0754: if (nnode != null)
0755: updateNumNhbrs(nnode);
0756:
0757: if (nnode != null) {
0758: // insert new node
0759: nnode.insert(node);
0760: node = nnode;
0761: queue[ind] = node;
0762: ind++;
0763: index[rindex[k]] = EMPTY;
0764: } else {
0765: node.processed();
0766: node = node.parent;
0767: }
0768: } while (node != source.parent);
0769: }
0770: }
0771: freeNhbrTable();
0772: return queue;
0773: }
0774:
0775: int findNext(Node node, Node[] faceNodes, Face[] faces) {
0776: Face face = node.face;
0777: // this face has no neighbors so return
0778: if (face.numNhbrs == 0)
0779: return EMPTY;
0780:
0781: int i, j, count;
0782: int[] n = new int[3]; // num neighbors of neighboring face
0783: int[] ind = { -1, -1, -1 }; // neighboring faces
0784:
0785: // find the number of neighbors for each neighbor
0786: count = 0;
0787: for (i = 0; i < 3; i++) {
0788: if (((j = face.getNeighbor(i)) != EMPTY)
0789: && (faceNodes[j].notAccessed())) {
0790: ind[count] = j;
0791: n[count] = numNhbrs[j];
0792: count++;
0793: }
0794: }
0795:
0796: // this face has no not accessed faces
0797: if (count == 0)
0798: return EMPTY;
0799:
0800: // this face has only one neighbor
0801: if (count == 1)
0802: return ind[0];
0803:
0804: if (count == 2) {
0805: // if the number of neighbors are the same, try reseting
0806: if ((n[0] == n[1]) && (n[0] != 0)) {
0807: n[0] = resetNhbr(ind[0], faces, faceNodes);
0808: n[1] = resetNhbr(ind[1], faces, faceNodes);
0809: }
0810: // if one neighbor has fewer neighbors, return that neighbor
0811: if (n[0] < n[1])
0812: return ind[0];
0813: if (n[1] < n[0])
0814: return ind[1];
0815: // neighbors tie. pick the sequential one
0816: Node pnode, ppnode;
0817: Face pface, ppface;
0818: if ((pnode = node.parent) != null) {
0819: pface = pnode.face;
0820: i = pface.findSharedEdge(face.key);
0821: if ((ppnode = pnode.parent) != null) {
0822: ppface = ppnode.face;
0823: if (pface.getNeighbor((i + 1) % 3) == ppface.key) {
0824: j = pface.verts[(i + 2) % 3].index;
0825: } else {
0826: j = pface.verts[(i + 1) % 3].index;
0827: }
0828: } else {
0829: j = pface.verts[(i + 1) % 3].index;
0830: }
0831: i = face.findSharedEdge(ind[0]);
0832: if (face.verts[i].index == j)
0833: return ind[0];
0834: else
0835: return ind[1];
0836: } else
0837: return ind[0];
0838: }
0839: // three neighbors
0840: else {
0841: if ((n[0] < n[1]) && (n[0] < n[2]))
0842: return ind[0];
0843: else if ((n[1] < n[0]) && (n[1] < n[2]))
0844: return ind[1];
0845: else if ((n[2] < n[0]) && (n[2] < n[1]))
0846: return ind[2];
0847: else if ((n[0] == n[1]) && (n[0] < n[2])) {
0848: if (n[0] != 0) {
0849: n[0] = resetNhbr(ind[0], faces, faceNodes);
0850: n[1] = resetNhbr(ind[1], faces, faceNodes);
0851: }
0852: if (n[0] <= n[1])
0853: return ind[0];
0854: else
0855: return ind[1];
0856: } else if ((n[1] == n[2]) && n[1] < n[0]) {
0857: if (n[1] != 0) {
0858: n[1] = resetNhbr(ind[1], faces, faceNodes);
0859: n[2] = resetNhbr(ind[2], faces, faceNodes);
0860: }
0861: if (n[1] <= n[2])
0862: return ind[1];
0863: else
0864: return ind[2];
0865: } else if ((n[2] == n[0]) && (n[2] < n[1])) {
0866: if (n[0] != 0) {
0867: n[0] = resetNhbr(ind[0], faces, faceNodes);
0868: n[2] = resetNhbr(ind[2], faces, faceNodes);
0869: }
0870: if (n[0] <= n[2])
0871: return ind[0];
0872: else
0873: return ind[2];
0874: } else {
0875: if (n[0] != 0) {
0876: n[0] = resetNhbr(ind[0], faces, faceNodes);
0877: n[1] = resetNhbr(ind[1], faces, faceNodes);
0878: n[2] = resetNhbr(ind[2], faces, faceNodes);
0879: }
0880: if ((n[0] <= n[1]) && (n[0] <= n[2]))
0881: return ind[0];
0882: else if (n[1] <= n[2])
0883: return ind[1];
0884: else
0885: return ind[2];
0886: }
0887: }
0888: }
0889:
0890: void setNumNhbrs(Face[] faces) {
0891: int numFaces = faces.length;
0892: numNhbrs = new int[numFaces];
0893: for (int i = 0; i < numFaces; i++) {
0894: numNhbrs[i] = faces[i].numNhbrs;
0895: }
0896: }
0897:
0898: void freeNhbrTable() {
0899: numNhbrs = null;
0900: }
0901:
0902: void updateNumNhbrs(Node node) {
0903: Face face = node.face;
0904: int i;
0905: if ((i = face.getNeighbor(0)) != EMPTY)
0906: numNhbrs[i]--;
0907: if ((i = face.getNeighbor(1)) != EMPTY)
0908: numNhbrs[i]--;
0909: if ((i = face.getNeighbor(2)) != EMPTY)
0910: numNhbrs[i]--;
0911: }
0912:
0913: int resetNhbr(int y, Face[] faces, Node[] faceNodes) {
0914: int x = EMPTY;
0915: Face nface = faces[y];
0916: int i;
0917: for (int j = 0; j < 3; j++) {
0918: if (((i = nface.getNeighbor(j)) != EMPTY)
0919: && (faceNodes[i].notAccessed())) {
0920: if ((x == EMPTY) || (x > numNhbrs[i]))
0921: x = numNhbrs[i];
0922: }
0923: }
0924: return x;
0925: }
0926:
0927: /**
0928: * generates hamiltonian strips from the derived binary spanning tree
0929: * using the path peeling algorithm to peel off any node wiht double
0930: * children in a bottom up fashion. Returns a Vector of strips. Also
0931: * return the number of strips and patches in the numStrips and
0932: * numPatches "pointers"
0933: */
0934: ArrayList hamilton(Node[] sTree, int[] numStrips, int[] numPatches) {
0935: // the number of nodes in the tree
0936: int numNodes = sTree.length;
0937: // number of strips
0938: int ns = 0;
0939: // number of patches
0940: int np = 0;
0941: // some tree node variables
0942: Node node, pnode, cnode;
0943: // the Vector of strips
0944: ArrayList strips = new ArrayList();
0945: // the current strip
0946: ArrayList currStrip;
0947:
0948: // the tree nodes are visited in such a bottom-up fashion that
0949: // any node is visited prior to its parent
0950: for (int i = numNodes - 1; i >= 0; i--) {
0951: cnode = sTree[i];
0952:
0953: // if cnode is the root of a tree create a strip
0954: if (cnode.isRoot()) {
0955: // each patch is a single tree
0956: np++;
0957: // create a new strip
0958: currStrip = new ArrayList();
0959: // insert the current node into the list
0960: currStrip.add(0, cnode.face);
0961:
0962: // add the left "wing" of the parent node to the strip
0963: node = cnode.left;
0964: while (node != null) {
0965: currStrip.add(0, node.face);
0966: node = node.left;
0967: }
0968:
0969: // add the right "wing" of the parent node to the strip
0970: node = cnode.right;
0971: while (node != null) {
0972: currStrip.add(currStrip.size(), node.face);
0973: node = node.left;
0974: }
0975:
0976: // increase the number of strips
0977: ns++;
0978: // add the strip to the Vector
0979: strips.add(currStrip);
0980: }
0981:
0982: // if the number of children of this node is 2, create a strip
0983: else if (cnode.numChildren == 2) {
0984: // if the root has a single child with double children, it
0985: // could be left over as a singleton. However, the following
0986: // rearrangement reduces the chances
0987: pnode = cnode.parent;
0988: if (pnode.isRoot() && (pnode.numChildren == 1)) {
0989: pnode = cnode.right;
0990: if (pnode.left != null)
0991: cnode = pnode;
0992: else
0993: cnode = cnode.left;
0994: }
0995:
0996: // handle non-root case
0997:
0998: // remove the node
0999: cnode.remove();
1000:
1001: // create a new strip
1002: currStrip = new ArrayList();
1003: // insert the current node into the list
1004: currStrip.add(0, cnode.face);
1005:
1006: // add the left "wing" of cnode to the list
1007: node = cnode.left;
1008: while (node != null) {
1009: currStrip.add(0, node.face);
1010: node = node.left;
1011: }
1012:
1013: // add the right "wing" of cnode to the list
1014: node = cnode.right;
1015: while (node != null) {
1016: currStrip.add(currStrip.size(), node.face);
1017: node = node.left;
1018: }
1019:
1020: // increase the number of strips
1021: ns++;
1022: // add the strip to the Vector
1023: strips.add(currStrip);
1024: }
1025: }
1026:
1027: // put the ns and np in the "pointers to return
1028: numStrips[0] = ns;
1029: numPatches[0] = np;
1030:
1031: // return the strips
1032: return strips;
1033: }
1034:
1035: /**
1036: * creates the triangle strips
1037: */
1038: ArrayList stripe(ArrayList strips) {
1039: int numStrips = strips.size(); // the number of strips
1040: int count; // where we are in the hamiltonian
1041: Face face; // the face we are adding to the stream
1042: Face prev; // the previous face added to the stream
1043: boolean done; // whether we are done with the current strip
1044: boolean cont; // whether we should continue the current stream
1045: ArrayList currStrip; // the current hamiltonian
1046: Istream currStream; // the stream we are building
1047: ArrayList istreams = new ArrayList(); // the istreams to return
1048: boolean ccw = true;
1049: ; // counter-clockwise
1050: int share; // the shared edge
1051: Vertex[] buf = new Vertex[4]; // a vertex array to start the stream
1052:
1053: // create streams for each hamiltonian
1054: for (int i = 0; i < numStrips; i++) {
1055: currStrip = (ArrayList) strips.get(i);
1056: count = 0;
1057: done = false;
1058: face = getNextFace(currStrip, count++);
1059:
1060: // while we are not done with the current hamiltonian
1061: while (!done) {
1062: cont = true;
1063:
1064: // if the current face is the only one left in the current
1065: // hamiltonian
1066: if (stripDone(currStrip, count)) {
1067: // create a new istream with the current face
1068: currStream = new Istream(face.verts, 3, false);
1069: // set the head of the strip to this face
1070: currStream.head = face.key;
1071: done = true;
1072: // since we are done with the strip, set the tail to this
1073: // face
1074: currStream.tail = face.key;
1075: }
1076:
1077: else {
1078: prev = face;
1079: face = getNextFace(currStrip, count++);
1080:
1081: // put the prev vertices in the correct order
1082: // to add the next tri on
1083: share = prev.findSharedEdge(face.key);
1084: buf[0] = prev.verts[share];
1085: buf[1] = prev.verts[(share + 1) % 3];
1086: buf[2] = prev.verts[(share + 2) % 3];
1087:
1088: // find the fourth vertex
1089: if (CHECK_ORIENT) {
1090: // check for clockwise orientation
1091: if (checkOrientCWSeq(buf[2], buf[1], face)) {
1092: share = face.findSharedEdge(prev.key);
1093: buf[3] = face.verts[share];
1094: currStream = new Istream(buf, 4, false);
1095: // set the head of this strip to the prev face
1096: currStream.head = prev.key;
1097: // if this was the last tri in the strip, then
1098: // we are done
1099: if (stripDone(currStrip, count)) {
1100: done = true;
1101: // set the tail for the strip to current face
1102: currStream.tail = face.key;
1103: }
1104: } else {
1105: cont = false;
1106: currStream = new Istream(buf, 3, false);
1107: // set the head to the prev face
1108: currStream.head = prev.key;
1109: // since we are not continuing, set
1110: // the tail to prev also
1111: currStream.tail = prev.key;
1112: }
1113:
1114: // orientation starts counter-clockwise for 3rd face
1115: ccw = true;
1116: } else {
1117: share = face.findSharedEdge(prev.key);
1118: buf[3] = face.verts[share];
1119: currStream = new Istream(buf, 4, false);
1120: // set the head of this strip to the prev face
1121: currStream.head = prev.key;
1122: // if this was the last tri in the strip, then
1123: // we are done
1124: if (stripDone(currStrip, count)) {
1125: done = true;
1126: // set the tail for the strip to current face
1127: currStream.tail = face.key;
1128: }
1129: }
1130:
1131: // while continue and the strip isn't finished
1132: // add more faces to the stream
1133: while (cont && !stripDone(currStrip, count)) {
1134: prev = face;
1135: face = getNextFace(currStrip, count++);
1136: share = face.findSharedEdge(prev.key);
1137:
1138: // if we can add the face without adding any
1139: // zero area triangles
1140: if (seq(currStream, face, share)) {
1141: if (CHECK_ORIENT) {
1142: // if we can add the next face with the correct
1143: // orientation
1144: if (orientSeq(ccw, currStream, face)) {
1145: // append the vertex opposite the
1146: //shared edge
1147: currStream
1148: .append(face.verts[share]);
1149: // next face must have opposite orientation
1150: ccw = (!ccw);
1151: // if this was the last tri in the
1152: //strip, then we are done
1153: if (stripDone(currStrip, count)) {
1154: done = true;
1155: // since we are done with this strip,
1156: // set the tail to the current face
1157: currStream.tail = face.key;
1158: }
1159: }
1160: // if we cannot add the face with the correct
1161: // orientation, do not continue with this
1162: // stream
1163: else {
1164: cont = false;
1165: // since we cannot continue with this strip
1166: // set the tail to prev
1167: currStream.tail = prev.key;
1168: }
1169: } else {
1170: // append the vertex opposite the
1171: //shared edge
1172: currStream.append(face.verts[share]);
1173: // if this was the last tri in the
1174: //strip, then we are done
1175: if (stripDone(currStrip, count)) {
1176: done = true;
1177: // since we are done with this strip,
1178: // set the tail to the current face
1179: currStream.tail = face.key;
1180: }
1181: }
1182: }
1183:
1184: // need zero area tris to add continue the strip
1185: else {
1186: if (CHECK_ORIENT) {
1187: // check the orientation for adding a zero
1188: // area tri and this face
1189: if (orientZAT(ccw, currStream, face)) {
1190: // swap the end of the current stream to
1191: // add a zero area triangle
1192: currStream.swapEnd();
1193: // append the vertex opposite the
1194: // shared edge
1195: currStream
1196: .append(face.verts[share]);
1197: // if this was the last tri in the
1198: // strip then we are done
1199: if (stripDone(currStrip, count)) {
1200: done = true;
1201: // set the tail because we are done
1202: currStream.tail = face.key;
1203: }
1204: }
1205: // if we cannot add the face with the correct
1206: // orientation, do not continue with this
1207: // stream
1208: else {
1209: cont = false;
1210: // since we cannot continue with this face,
1211: // set the tail to the prev face
1212: currStream.tail = prev.key;
1213: }
1214: } else {
1215: // swap the end of the current stream to
1216: // add a zero area triangle
1217: currStream.swapEnd();
1218: // append the vertex opposite the
1219: // shared edge
1220: currStream.append(face.verts[share]);
1221: // if this was the last tri in the
1222: // strip then we are done
1223: if (stripDone(currStrip, count)) {
1224: done = true;
1225: // set the tail because we are done
1226: currStream.tail = face.key;
1227: }
1228: }
1229: }
1230: } // while (cont && !stripDone)
1231: } // else
1232:
1233: // add the current strip to the strips to be returned
1234: istreams.add(currStream);
1235: } // while !done
1236: } // for each hamiltonian
1237: return istreams;
1238: } // stripe
1239:
1240: boolean stripDone(ArrayList strip, int count) {
1241: if (count < strip.size()) {
1242: return false;
1243: } else
1244: return true;
1245: }
1246:
1247: boolean seq(Istream stream, Face face, int share) {
1248: int length = stream.length;
1249: Vertex v1 = face.edges[share].v1;
1250: Vertex v2 = face.edges[share].v2;
1251: Vertex last = stream.istream[length - 1];
1252: Vertex prev = stream.istream[length - 2];
1253: if (((v1.equals(prev)) && (v2.equals(last)))
1254: || ((v1.equals(last)) && (v2.equals(prev)))) {
1255: return true;
1256: } else
1257: return false;
1258: }
1259:
1260: boolean orientSeq(boolean ccw, Istream stream, Face face) {
1261: int length = stream.length;
1262: Vertex last = stream.istream[length - 1];
1263: Vertex prev = stream.istream[length - 2];
1264: if ((ccw && checkOrientCCWSeq(last, prev, face))
1265: || ((!ccw) && checkOrientCWSeq(last, prev, face))) {
1266: return true;
1267: } else
1268: return false;
1269: }
1270:
1271: boolean orientZAT(boolean ccw, Istream stream, Face face) {
1272: int length = stream.length;
1273: Vertex last = stream.istream[length - 1];
1274: Vertex swap = stream.istream[length - 3];
1275: if ((ccw && checkOrientCWSeq(last, swap, face))
1276: || ((!ccw) && checkOrientCCWSeq(last, swap, face))) {
1277: return true;
1278: } else
1279: return false;
1280: }
1281:
1282: boolean checkOrientCWSeq(Vertex last, Vertex prev, Face face) {
1283: System.out.println("checkOrientCWSeq");
1284: System.out.println("last = " + last.index);
1285: System.out.println("prev = " + prev.index);
1286: System.out.print("face = ");
1287: face.printVertices();
1288: if (last.equals(face.verts[0])) {
1289: if (!prev.equals(face.verts[1])) {
1290: if (DEBUG)
1291: System.out.println("ORIENTATION PROBLEM!");
1292: return false;
1293: }
1294: } else if (last.equals(face.verts[1])) {
1295: if (!prev.equals(face.verts[2])) {
1296: if (DEBUG)
1297: System.out.println("ORIENTATION PROBLEM!");
1298: return false;
1299: }
1300: } else if (last.equals(face.verts[2])) {
1301: if (!prev.equals(face.verts[0])) {
1302: if (DEBUG)
1303: System.out.println("ORIENTATION PROBLEM!");
1304: return false;
1305: }
1306: }
1307: return true;
1308: }
1309:
1310: boolean checkOrientCCWSeq(Vertex last, Vertex prev, Face face) {
1311: System.out.println("checkOrientCCWSeq");
1312: System.out.println("last = " + last.index);
1313: System.out.println("prev = " + prev.index);
1314: System.out.print("face = ");
1315: face.printVertices();
1316: if (prev.equals(face.verts[0])) {
1317: if (!last.equals(face.verts[1])) {
1318: System.out.println("ORIENTATION PROBLEM!");
1319: return false;
1320: }
1321: } else if (prev.equals(face.verts[1])) {
1322: if (!last.equals(face.verts[2])) {
1323: System.out.println("ORIENTATION PROBLEM!");
1324: return false;
1325: }
1326: } else if (prev.equals(face.verts[2])) {
1327: if (!last.equals(face.verts[0])) {
1328: System.out.println("ORIENTATION PROBLEM!");
1329: return false;
1330: }
1331: }
1332: return true;
1333: }
1334:
1335: Face getNextFace(ArrayList currStrip, int index) {
1336: if (currStrip.size() > index)
1337: return (Face) currStrip.get(index);
1338: else
1339: return null;
1340: }
1341:
1342: /**
1343: * joins tristrips if their end triangles neighbor each other. The
1344: * priority is performed in three stages: strips are concatenated to
1345: * save 2, 1, or no vertices
1346: */
1347: void concatenate(ArrayList strips, Face[] faces) {
1348: int numFaces = faces.length;
1349: int[] faceTable = new int[numFaces];
1350: Istream strm;
1351:
1352: // initialize the face table to empty
1353: for (int i = 0; i < numFaces; i++) {
1354: faceTable[i] = EMPTY;
1355: }
1356:
1357: // set up the faceTable so that a face index relates to a strip
1358: // that owns the face as one of its end faces
1359: for (int i = 0; i < strips.size(); i++) {
1360: strm = (Istream) strips.get(i);
1361: faceTable[strm.head] = i;
1362: faceTable[strm.tail] = i;
1363: }
1364:
1365: if (DEBUG) {
1366: System.out.println("");
1367: System.out.println("faceTable:");
1368: for (int i = 0; i < faceTable.length; i++) {
1369: System.out.println(faceTable[i]);
1370: }
1371: System.out.println("");
1372: }
1373:
1374: reduceCostByTwo(strips, faces, faceTable);
1375: reduceCostByOne(strips, faces, faceTable);
1376: reduceCostByZero(strips, faces, faceTable);
1377: }
1378:
1379: /**
1380: * find all the links that reduce the cost by 2
1381: */
1382: void reduceCostByTwo(ArrayList strips, Face[] faces, int[] faceTable) {
1383: // System.out.println("reduceCostByTwo");
1384: // number of faces in the face array
1385: int numFaces = faces.length;
1386: // possible adjacent strips
1387: int id, id1, id2;
1388: // Istreams
1389: Istream strm, strm1;
1390: // the length of the Istrem
1391: int len, len1;
1392: // vertex sequences for tristrips
1393: Vertex[] seq, seq1;
1394: // a face
1395: Face face;
1396: // the list of vertices for the face
1397: Vertex[] verts;
1398: // used to syncronize the orientation
1399: boolean sync, sync1;
1400: // a swap variable
1401: Vertex swap;
1402:
1403: for (int i = 0; i < numFaces; i++) {
1404: id = faceTable[i];
1405: if (id != EMPTY) {
1406: sync = false;
1407: sync1 = false;
1408: strm = (Istream) strips.get(id);
1409: len = strm.length;
1410: seq = strm.istream;
1411: face = faces[i];
1412: verts = face.verts;
1413:
1414: // sequential strips
1415: if (!strm.fan) {
1416:
1417: // a singleton strip
1418: if (len == 3) {
1419:
1420: // check all three neighbors
1421: for (int j = 0; j < 3; j++) {
1422: int k = face.getNeighbor(j);
1423: if ((k != EMPTY)
1424: && ((id1 = faceTable[k]) != EMPTY)
1425: && (id1 != id)) {
1426: // reassign the sequence
1427: seq[0] = verts[j];
1428: seq[1] = verts[(j + 1) % 3];
1429: seq[2] = verts[(j + 2) % 3];
1430:
1431: // the neighboring stream
1432: strm1 = (Istream) strips.get(id1);
1433: len1 = strm1.length;
1434: if (k != strm1.head) {
1435: strm1.invert();
1436: // if the length is odd set sync1 to true
1437: if ((len1 % 2) != 0)
1438: sync1 = true;
1439: }
1440: seq1 = strm1.istream;
1441:
1442: // append a singleton strip
1443: if (len1 == 3) {
1444: // System.out.println("reduce2");
1445: int m = faces[k].findSharedEdge(i);
1446: strm.append(faces[k].verts[m]);
1447: strm1.length = 0;
1448: strm1.istream = null;
1449: strm.tail = k;
1450: faceTable[k] = id;
1451: i--;
1452: break;
1453: }
1454:
1455: // append a strip of length over 2
1456: else {
1457: if ((len1 == 4)
1458: && (seq[1].index == seq1[0].index)
1459: && (seq[2].index == seq1[2].index)) {
1460:
1461: // swap seq1[1] and seq1[2] so that
1462: // seq[1] == seq1[0] and
1463: // seq[1] == seq1[1]
1464: swap = seq1[1];
1465: seq1[1] = seq1[2];
1466: seq1[2] = swap;
1467: }
1468:
1469: // see if we can join the strips
1470: if ((seq[1].index == seq1[0].index)
1471: && (seq[2].index == seq1[1].index)) {
1472: // System.out.println("reduce2");
1473: // add the stream in
1474: strm.addStream(strm1);
1475: faceTable[k] = EMPTY;
1476: faceTable[strm.tail] = id;
1477:
1478: i--;
1479: break;
1480: } else if (sync1) {
1481: strm1.invert();
1482: sync1 = false;
1483: }
1484: }
1485: }
1486: }
1487: }
1488:
1489: // not a singleton strip
1490:
1491: // can append a stream where the current face is the tail
1492: // or is an even length so we can invert it
1493: else if ((i == strm.tail) || ((len % 2) == 0)) {
1494: // if the current face isn't the tail, then
1495: // have to invert the strip
1496: if (i != strm.tail) {
1497: strm.invert();
1498: seq = strm.istream;
1499: }
1500:
1501: // System.out.println("seq.length = " + seq.length);
1502: // System.out.println("len = " + len);
1503: // System.out.print("seq = ");
1504: // for (int l = 0; l < seq.length; l++) {
1505: // if (seq[l] == null) System.out.print(" null");
1506: // else System.out.print(" " + seq[l].index);
1507: // }
1508: // System.out.println("");
1509:
1510: swap = seq[len - 3];
1511:
1512: // find the neighboring strip
1513: int m = EMPTY;
1514: if (verts[0].index == swap.index)
1515: m = 0;
1516: else if (verts[1].index == swap.index)
1517: m = 1;
1518: else if (verts[2].index == swap.index)
1519: m = 2;
1520: if (m == EMPTY) {
1521: if (DEBUG)
1522: System.out
1523: .println("problem finding neighbor strip");
1524: }
1525: int j = face.getNeighbor(m);
1526: if (j == EMPTY)
1527: id1 = j;
1528: else
1529: id1 = faceTable[j];
1530: if ((id1 != EMPTY)
1531: && (((Istream) strips.get(id1)).fan != strm.fan)) {
1532: id1 = EMPTY;
1533: }
1534:
1535: if ((id1 != EMPTY) && (id1 != id)) {
1536: strm1 = (Istream) strips.get(id1);
1537: len1 = strm1.length;
1538:
1539: // if the shared face isn't the head, invert
1540: // the stream
1541: if (j != strm1.head) {
1542: strm1.invert();
1543: // set the sync var if the length is odd
1544: if ((len1 % 2) != 0)
1545: sync1 = true;
1546: }
1547: seq1 = strm1.istream;
1548:
1549: // append a singleton strip
1550: if (len1 == 3) {
1551: // System.out.println("reduce2");
1552: m = faces[j].findSharedEdge(i);
1553: strm.append(faces[j].verts[m]);
1554: strm1.length = 0;
1555: strm1.istream = null;
1556: strm.tail = j;
1557: faceTable[i] = EMPTY;
1558: faceTable[j] = id;
1559: }
1560:
1561: // append a non-singleton strip
1562: else {
1563: if ((len1 == 4)
1564: && (seq[len - 2].index == seq1[0].index)
1565: && (seq[len - 1].index == seq1[2].index)) {
1566:
1567: // swap seq1[1] and seq1[2] so that
1568: // seq[len-2] == seq1[0] and
1569: // seq[len-1] == seq1[1]
1570: swap = seq1[1];
1571: seq1[1] = seq1[2];
1572: seq1[2] = swap;
1573: }
1574:
1575: // see if we can append the strip
1576: if ((seq[len - 2].index == seq1[0].index)
1577: && (seq[len - 1].index == seq1[1].index)) {
1578: // System.out.println("reduce2");
1579: strm.addStream(strm1);
1580: faceTable[i] = EMPTY;
1581: faceTable[strm.tail] = id;
1582: faceTable[j] = EMPTY;
1583: } else if (sync1)
1584: strm1.invert();
1585: }
1586: }
1587: }
1588: }
1589: }
1590: }
1591: }
1592:
1593: /**
1594: * find all links that reduce cost by 1
1595: */
1596: void reduceCostByOne(ArrayList strips, Face[] faces, int[] faceTable) {
1597: // System.out.println("reduceCostByOne");
1598: // number of faces in the face array
1599: int numFaces = faces.length;
1600: // possible adjacent strips
1601: int id, id1, id2;
1602: // Istreams
1603: Istream strm, strm1;
1604: // the length of the Istream
1605: int len, len1;
1606: // vertex sequences for tristrips
1607: Vertex[] seq, seq1;
1608: // a face
1609: Face face;
1610: // the list of vertices for the face
1611: Vertex[] verts;
1612: // used to synchronize the orientation
1613: boolean sync, sync1;
1614: // a swap variable
1615: Vertex swap;
1616:
1617: for (int i = 0; i < numFaces; i++) {
1618: id = faceTable[i];
1619: if ((id != EMPTY) && !((Istream) strips.get(id)).fan) {
1620: sync = false;
1621: strm = (Istream) strips.get(id);
1622: seq = strm.istream;
1623: face = faces[i];
1624: verts = face.verts;
1625: len = strm.length;
1626:
1627: // a singleton strip
1628: if (len == 3) {
1629:
1630: // consider the three neighboring triangles
1631: for (int j = 0; j < 3; j++) {
1632: int k = face.getNeighbor(j);
1633: if ((k != EMPTY)
1634: && ((id1 = faceTable[k]) != EMPTY)
1635: && (id1 != id)
1636: && (!((Istream) strips.get(id1)).fan)) {
1637:
1638: // reassign the sequence
1639: seq[0] = verts[j];
1640: seq[1] = verts[(j + 1) % 3];
1641: seq[2] = verts[(j + 2) % 3];
1642:
1643: // the neighboring stream
1644: strm1 = (Istream) strips.get(id1);
1645: len1 = strm1.length;
1646: if (k != strm1.head) {
1647: strm1.invert();
1648: if ((len1 % 2) != 0)
1649: sync = true;
1650: }
1651: seq1 = strm1.istream;
1652:
1653: // see if we can join the strips
1654:
1655: if ((len1 == 4)
1656: && (((seq[1].index == seq1[2].index) && (seq[2].index == seq1[0].index)) || ((seq[1].index == seq1[0].index) && (seq[2].index == seq1[2].index)))) {
1657: swap = seq1[1];
1658: seq1[1] = seq1[2];
1659: seq1[2] = swap;
1660: }
1661:
1662: if ((seq[1].index == seq1[0].index)
1663: && (seq[2].index == seq1[1].index)) {
1664: // System.out.println("reduce1");
1665: strm.addStream(strm1);
1666: faceTable[k] = EMPTY;
1667: faceTable[strm.tail] = id;
1668: i--;
1669: break;
1670: }
1671:
1672: if ((seq[1].index == seq1[1].index)
1673: && (seq[2].index == seq1[0].index)) {
1674: // System.out.println("reduce1");
1675: strm.append(seq1[1]);
1676: strm.addStream(strm1);
1677: faceTable[k] = EMPTY;
1678: faceTable[strm.tail] = id;
1679: i--;
1680: break;
1681: }
1682:
1683: if ((seq[1].index == seq1[0].index)
1684: && (seq[2].index == seq1[2].index)) {
1685: // System.out.println("reduce1");
1686: seq1[0] = seq1[2];
1687: strm.append(seq1[1]);
1688: strm.addStream(strm1);
1689: faceTable[k] = EMPTY;
1690: faceTable[strm.tail] = id;
1691: i--;
1692: break;
1693: }
1694:
1695: if (sync) {
1696: strm1.invert();
1697: sync = false;
1698: }
1699: }
1700: }
1701: }
1702:
1703: // non-singleton strip
1704: else if ((i == strm.tail) || ((len % 2) == 0)) {
1705:
1706: // make sure the face i ends the id-th strip
1707: if (i != strm.tail) {
1708: strm.invert();
1709: seq = strm.istream;
1710: }
1711:
1712: swap = seq[len - 3];
1713:
1714: // find the neighboring strip
1715: int m = EMPTY;
1716: if (verts[0].index == swap.index)
1717: m = 0;
1718: else if (verts[1].index == swap.index)
1719: m = 1;
1720: else if (verts[2].index == swap.index)
1721: m = 2;
1722: if (m == EMPTY) {
1723: if (DEBUG)
1724: System.out
1725: .println("problem finding neighbor strip");
1726: }
1727: int j = face.getNeighbor(m);
1728: if (j == EMPTY)
1729: id1 = j;
1730: else
1731: id1 = faceTable[j];
1732: if ((id1 != EMPTY)
1733: && (((Istream) strips.get(id1)).fan != strm.fan)) {
1734: id1 = EMPTY;
1735: }
1736:
1737: // find another neighboring strip
1738: swap = seq[len - 2];
1739: m = EMPTY;
1740: if (verts[0].index == swap.index)
1741: m = 0;
1742: else if (verts[1].index == swap.index)
1743: m = 1;
1744: else if (verts[2].index == swap.index)
1745: m = 2;
1746: if (m == EMPTY) {
1747: if (DEBUG)
1748: System.out
1749: .println("problem finding neighbor strip.");
1750: }
1751: int k = face.getNeighbor(m);
1752: if (k == EMPTY)
1753: id2 = k;
1754: else
1755: id2 = faceTable[k];
1756: if ((id2 != EMPTY)
1757: && (((Istream) strips.get(id2)).fan != strm.fan)) {
1758: id2 = EMPTY;
1759: }
1760:
1761: // consider strip id1
1762: boolean success = false;
1763: if ((id1 != EMPTY) && (id1 != id)) {
1764: strm1 = (Istream) strips.get(id1);
1765: len1 = strm1.length;
1766: if (j != strm1.head) {
1767: strm1.invert();
1768: if ((len1 % 2) != 0)
1769: sync = true;
1770: }
1771: seq1 = strm1.istream;
1772:
1773: if ((len1 == 4)
1774: && (((seq[len - 2].index == seq1[2].index) && (seq[len - 1].index == seq1[0].index)) || (seq[len - 2].index == seq1[0].index)
1775: && (seq[len - 1].index == seq1[2].index))) {
1776: swap = seq1[1];
1777: seq1[1] = seq1[2];
1778: seq1[2] = swap;
1779: }
1780:
1781: // find matches
1782: if ((seq[len - 2].index == seq1[0].index)
1783: && (seq[len - 1].index == seq1[1].index)) {
1784: // System.out.println("reduce1");
1785: strm.addStream(strm1);
1786: faceTable[i] = EMPTY;
1787: faceTable[strm.tail] = id;
1788: faceTable[j] = EMPTY;
1789: success = true;
1790: }
1791:
1792: else if ((seq[len - 2].index == seq1[1].index)
1793: && (seq[len - 1].index == seq1[0].index)) {
1794: // System.out.println("reduce1");
1795: strm.append(seq1[1]);
1796: strm.addStream(strm1);
1797: faceTable[i] = EMPTY;
1798: faceTable[strm.tail] = id;
1799: faceTable[j] = EMPTY;
1800: success = true;
1801: }
1802:
1803: else if ((seq[len - 2].index == seq1[0].index)
1804: && (seq[len - 1].index == seq1[2].index)) {
1805: // System.out.println("reduce1");
1806: seq1[0] = seq1[2];
1807: strm.append(seq1[1]);
1808: strm.addStream(strm1);
1809: faceTable[i] = EMPTY;
1810: faceTable[strm.tail] = id;
1811: faceTable[j] = EMPTY;
1812: success = true;
1813: } else if (sync) {
1814: strm1.invert();
1815: sync = false;
1816: }
1817: }
1818:
1819: // now consider strip id2
1820: if (!success && (id2 != EMPTY) && (id2 != id)) {
1821: strm1 = (Istream) strips.get(id2);
1822: len1 = strm1.length;
1823: if (k != strm1.head) {
1824: strm1.invert();
1825: if ((len1 % 2) != 0)
1826: sync = true;
1827: }
1828: seq1 = strm1.istream;
1829:
1830: if ((len1 == 4)
1831: && (seq[len - 3].index == seq1[0].index)
1832: && (seq[len - 1].index == seq1[2].index)) {
1833: swap = seq1[1];
1834: seq1[1] = seq1[2];
1835: seq1[2] = swap;
1836: }
1837:
1838: // find matches
1839:
1840: if ((seq[len - 3].index == seq1[0].index)
1841: && (seq[len - 1].index == seq1[1].index)) {
1842: // System.out.println("reduce1");
1843: strm.swapEnd();
1844: strm.addStream(strm1);
1845: faceTable[i] = EMPTY;
1846: faceTable[strm.tail] = id;
1847: faceTable[k] = EMPTY;
1848: success = true;
1849: }
1850: if (!success && sync)
1851: strm1.invert();
1852: }
1853: }
1854: }
1855: }
1856: }
1857:
1858: /**
1859: * find all the links that reduce the cost by 0
1860: */
1861: void reduceCostByZero(ArrayList strips, Face[] faces,
1862: int[] faceTable) {
1863: // System.out.println("reduceCostByZero");
1864: // number of faces in the face array
1865: int numFaces = faces.length;
1866: // possible adjacent strips
1867: int id, id1, id2;
1868: // Istreams
1869: Istream strm, strm1;
1870: // the length of the Istream
1871: int len, len1;
1872: // vertex sequences for tristrips
1873: Vertex[] seq, seq1;
1874: // a face
1875: Face face;
1876: // the list of vertices for the face
1877: Vertex[] verts;
1878: // used to synchronize the orientation
1879: boolean sync, sync1;
1880: // a swap variable
1881: Vertex swap;
1882:
1883: for (int i = 0; i < numFaces; i++) {
1884: id = faceTable[i];
1885: if ((id != EMPTY) && !((Istream) strips.get(id)).fan) {
1886: sync = false;
1887: strm = (Istream) strips.get(id);
1888: seq = strm.istream;
1889: len = strm.length;
1890: face = faces[i];
1891: verts = face.verts;
1892:
1893: if (len == 3) {
1894: for (int j = 0; j < 3; j++) {
1895: int k = face.getNeighbor(j);
1896: if ((k != EMPTY)
1897: && ((id1 = faceTable[k]) != EMPTY)
1898: && (id1 != id)
1899: && !((Istream) strips.get(id1)).fan) {
1900: // reassign the sequence
1901: seq[0] = verts[j];
1902: seq[1] = verts[(j + 1) % 3];
1903: seq[2] = verts[(j + 2) % 3];
1904:
1905: // the neighboring stream
1906: strm1 = (Istream) strips.get(id1);
1907: len1 = strm1.length;
1908: if (k != strm1.head) {
1909: strm1.invert();
1910: if ((len1 % 2) != 0)
1911: sync = true;
1912: }
1913: seq1 = strm1.istream;
1914:
1915: // see if we can join the strips
1916: if ((seq[1].index == seq1[2].index)
1917: && (seq[2].index == seq1[0].index)) {
1918: // System.out.println("reduce0");
1919: seq1[0] = seq1[2];
1920: strm.append(seq1[0]);
1921: strm.append(seq1[1]);
1922: strm.addStream(strm1);
1923: faceTable[k] = EMPTY;
1924: faceTable[strm.tail] = id;
1925: i--;
1926: break;
1927: } else if (sync) {
1928: strm1.invert();
1929: sync = false;
1930: }
1931: }
1932: }
1933: } else if ((i == strm.tail) || ((len % 2) == 0)) {
1934: if (i != strm.tail) {
1935: strm.invert();
1936: seq = strm.istream;
1937: }
1938:
1939: swap = seq[len - 3];
1940:
1941: // find neighboring strip
1942: int m = EMPTY;
1943: if (verts[0].index == swap.index)
1944: m = 0;
1945: else if (verts[1].index == swap.index)
1946: m = 1;
1947: else if (verts[2].index == swap.index)
1948: m = 2;
1949: if (m == EMPTY) {
1950: if (DEBUG)
1951: System.out
1952: .println("problem finding neighbor strip");
1953: }
1954: int j = face.getNeighbor(m);
1955: if (j == EMPTY)
1956: id1 = j;
1957: else
1958: id1 = faceTable[j];
1959: if ((id1 != EMPTY)
1960: && (((Istream) strips.get(id1)).fan != strm.fan)) {
1961: id1 = EMPTY;
1962: }
1963:
1964: // find another neighboring strip
1965: swap = seq[len - 2];
1966: m = EMPTY;
1967: if (verts[0].index == swap.index)
1968: m = 0;
1969: else if (verts[1].index == swap.index)
1970: m = 1;
1971: else if (verts[2].index == swap.index)
1972: m = 2;
1973: if (m == EMPTY) {
1974: if (DEBUG)
1975: System.out
1976: .println("problem finding neighbor strip.");
1977: }
1978: int k = face.getNeighbor(m);
1979: if (k == EMPTY)
1980: id2 = k;
1981: else
1982: id2 = faceTable[k];
1983: if ((id2 != EMPTY)
1984: && (((Istream) strips.get(id2)).fan != strm.fan)) {
1985: id2 = EMPTY;
1986: }
1987:
1988: // consider strip id1
1989: boolean success = false;
1990: if ((id1 != EMPTY) && (id1 != id)) {
1991: strm1 = (Istream) strips.get(id1);
1992: len1 = strm1.length;
1993: if (j != strm1.head) {
1994: strm1.invert();
1995: if ((len1 % 2) != 0)
1996: sync = true;
1997: }
1998: seq1 = strm1.istream;
1999:
2000: // find matches
2001: if ((seq[len - 2].index == seq1[2].index)
2002: && (seq[len - 1].index == seq1[0].index)) {
2003: // System.out.println("reduce0");
2004: seq1[0] = seq1[2];
2005: strm.append(seq1[0]);
2006: strm.append(seq1[1]);
2007: strm.addStream(strm1);
2008: faceTable[i] = EMPTY;
2009: faceTable[strm.tail] = id;
2010: faceTable[j] = EMPTY;
2011: success = true;
2012: } else if (sync) {
2013: strm1.invert();
2014: sync = false;
2015: }
2016: }
2017:
2018: // consider strip id2
2019: if (!success && (id2 != EMPTY) && (id2 != id)) {
2020: strm1 = (Istream) strips.get(id2);
2021: len1 = strm1.length;
2022: if (k != strm1.head) {
2023: strm1.invert();
2024: if ((len1 % 2) != 0)
2025: sync = true;
2026: }
2027: seq1 = strm1.istream;
2028:
2029: if ((len1 == 4)
2030: && (((seq[len - 3].index == seq1[2].index) && (seq[len - 1].index == seq1[0].index)) || ((seq[len - 3].index == seq1[0].index) && (seq[len - 1].index == seq1[2].index)))) {
2031:
2032: swap = seq1[1];
2033: seq1[1] = seq1[2];
2034: seq1[2] = swap;
2035: }
2036:
2037: // find matches
2038: if ((seq[len - 3].index == seq1[1].index)
2039: && (seq[len - 1].index == seq1[0].index)) {
2040: // System.out.println("reduce0");
2041: strm.swapEnd();
2042: strm.append(seq1[1]);
2043: strm.addStream(strm1);
2044: faceTable[i] = EMPTY;
2045: faceTable[strm.tail] = id;
2046: faceTable[k] = EMPTY;
2047: } else if ((seq[len - 3].index == seq1[0].index)
2048: && (seq[len - 1].index == seq1[2].index)) {
2049: // System.out.println("reduce0");
2050: seq1[0] = seq1[2];
2051: strm.swapEnd();
2052: strm.append(seq1[1]);
2053: strm.addStream(strm1);
2054: faceTable[i] = EMPTY;
2055: faceTable[strm.tail] = id;
2056: faceTable[k] = EMPTY;
2057: } else if ((seq[len - 3].index == seq1[0].index)
2058: && (seq[len - 1].index == seq1[1].index)) {
2059: // System.out.println("reduce0");
2060: strm.swapEnd();
2061: strm.addStream(strm1);
2062: faceTable[i] = EMPTY;
2063: faceTable[strm.tail] = id;
2064: faceTable[k] = EMPTY;
2065: } else if (sync)
2066: strm1.invert();
2067: }
2068: }
2069: }
2070: }
2071: }
2072:
2073: /**
2074: * puts the stripified data back into the GeometryInfo object
2075: */
2076: void putBackData(GeometryInfo gi, ArrayList strips) {
2077: int[] tempStripCounts = new int[strips.size()];
2078: int ciSize = 0;
2079: int stripLength;
2080: for (int i = 0; i < strips.size();) {
2081: stripLength = ((Istream) strips.get(i)).length;
2082: if (stripLength != 0) {
2083: tempStripCounts[i] = stripLength;
2084: ciSize += stripLength;
2085: i++;
2086: } else {
2087: strips.remove(i);
2088: }
2089: }
2090: if (ciSize > 3) {
2091: gi.setPrimitive(gi.TRIANGLE_STRIP_ARRAY);
2092: int[] stripCounts = new int[strips.size()];
2093: System.arraycopy(tempStripCounts, 0, stripCounts, 0, strips
2094: .size());
2095: gi.setStripCounts(stripCounts);
2096:
2097: // create one array with all the strips
2098: int[] coords = new int[ciSize];
2099:
2100: // create arrays for normals, textures and colors if necessary
2101: int[] normals = null;
2102: int[][] textures = null;
2103: int[] colors = null;
2104: javax.vecmath.Color3b[] stripColors = null;
2105: if (hasNormals)
2106: normals = new int[ciSize];
2107: if (hasTextures) {
2108: textures = new int[texSetCount][ciSize];
2109: }
2110: if (hasColors)
2111: colors = new int[ciSize];
2112: if (colorStrips) {
2113: stripColors = new javax.vecmath.Color3b[ciSize];
2114: colors = new int[ciSize];
2115: }
2116: int count = 0;
2117: Istream currStrip;
2118: for (int i = 0; i < strips.size(); i++) {
2119: currStrip = (Istream) strips.get(i);
2120:
2121: if (currStrip.length < 3) {
2122: throw new RuntimeException("currStrip.length = "
2123: + currStrip.length);
2124: }
2125:
2126: java.awt.Color stripColor = null;
2127: if (colorStrips) {
2128: int r = ((int) (Math.random() * 1000)) % 255;
2129: int g = ((int) (Math.random() * 1000)) % 255;
2130: int b = ((int) (Math.random() * 1000)) % 255;
2131: stripColor = new java.awt.Color(r, g, b);
2132: }
2133:
2134: for (int j = 0; j < currStrip.length; j++) {
2135: coords[count] = currStrip.istream[j].index;
2136: if (hasNormals)
2137: normals[count] = currStrip.istream[j].normal;
2138: if (hasTextures) {
2139: for (int k = 0; k < texSetCount; k++) {
2140: textures[k][count] = currStrip.istream[j].texture[k];
2141: }
2142: }
2143: if (hasColors)
2144: colors[count] = currStrip.istream[j].color;
2145: if (colorStrips)
2146: stripColors[count] = new javax.vecmath.Color3b(
2147: stripColor);
2148: count++;
2149: }
2150: }
2151: gi.setCoordinateIndices(coords);
2152: if (hasNormals)
2153: gi.setNormalIndices(normals);
2154: if (hasTextures) {
2155: for (int i = 0; i < texSetCount; i++) {
2156: gi.setTextureCoordinateIndices(i, textures[i]);
2157: }
2158: }
2159: if (hasColors)
2160: gi.setColorIndices(colors);
2161: if (colorStrips) {
2162: gi.setColors(stripColors);
2163: colors = gi.getListIndices(stripColors);
2164: gi.setColorIndices(colors);
2165: }
2166: }
2167: }
2168:
2169: /**
2170: * Stores the infomration about a vertex
2171: */
2172: class Vertex {
2173:
2174: int index;
2175: int normal = EMPTY;
2176: int numTexSets = 0;
2177: int[] texture = null;
2178: int color = EMPTY;
2179:
2180: Vertex(int vertIndex) {
2181: this (vertIndex, EMPTY, 0, null, EMPTY);
2182: }
2183:
2184: Vertex(int vertIndex, int vertNormal, int vertNumTexSets,
2185: int[] vertTexture, int vertColor) {
2186: index = vertIndex;
2187: normal = vertNormal;
2188: numTexSets = vertNumTexSets;
2189: if (numTexSets > 0) {
2190: texture = new int[numTexSets];
2191: System
2192: .arraycopy(vertTexture, 0, texture, 0,
2193: numTexSets);
2194: }
2195: color = vertColor;
2196: }
2197:
2198: boolean equals(Vertex v) {
2199: for (int i = 0; i < numTexSets; i++) {
2200: if (texture[i] != v.texture[i]) {
2201: return false;
2202: }
2203: }
2204: return ((v.index == index) && (v.normal == normal) && (v.color == color));
2205: }
2206:
2207: // will this yield same results as c code ???
2208: boolean lessThan(Vertex v) {
2209: if (index < v.index)
2210: return true;
2211: if (index > v.index)
2212: return false;
2213: if (normal < v.normal)
2214: return true;
2215: if (normal > v.normal)
2216: return false;
2217: for (int i = 0; i < numTexSets; i++) {
2218: if (texture[i] < v.texture[i])
2219: return true;
2220: if (texture[i] > v.texture[i])
2221: return false;
2222: }
2223: if (color < v.color)
2224: return true;
2225: if (color > v.color)
2226: return false;
2227: return false;
2228: }
2229: }
2230:
2231: /**
2232: * Stores the information about an edge of a triangle
2233: */
2234: class Edge {
2235:
2236: Vertex v1, v2;
2237: int face;
2238:
2239: Edge(Vertex vertex1, Vertex vertex2, int faceIndex) {
2240: face = faceIndex;
2241:
2242: // this could be causing wrapping problem
2243: if (vertex1.lessThan(vertex2)) {
2244: v1 = vertex1;
2245: v2 = vertex2;
2246: } else {
2247: v1 = vertex2;
2248: v2 = vertex1;
2249: }
2250: }
2251:
2252: /**
2253: * Determine whether the edges have the same vertices
2254: */
2255: boolean equals(Edge edge) {
2256: return ((v1.equals(edge.v1)) && (v2.equals(edge.v2)));
2257:
2258: }
2259:
2260: /**
2261: * Used to sort the edges. If this is less than the edge parameter,
2262: * return true. First check if vertex1 is less than vertex1 of the
2263: * edge provided. If so, return true. If the first vertices are equal
2264: * then check vertex2.
2265: */
2266: boolean lessThan(Edge edge) {
2267: if (v1.lessThan(edge.v1))
2268: return true;
2269: else if (v1.equals(edge.v1))
2270: return (v2.lessThan(edge.v2));
2271: else
2272: return false;
2273: }
2274: }
2275:
2276: /**
2277: * Stores the information about the face of a triangle
2278: */
2279: class Face {
2280: int key;
2281: int numNhbrs = 0;
2282: Vertex[] verts = null;
2283: // edges are kept in order s.t. the ith edge is the opposite
2284: // edge of the ith vertex
2285: Edge[] edges = null;
2286:
2287: /**
2288: * Creates a new Face with the three given vertices
2289: */
2290: Face(int index, Vertex v1, Vertex v2, Vertex v3) {
2291: key = index;
2292:
2293: verts = new Vertex[3];
2294: verts[0] = v1;
2295: verts[1] = v2;
2296: verts[2] = v3;
2297:
2298: edges = new Edge[3];
2299: edges[0] = null;
2300: edges[1] = null;
2301: edges[2] = null;
2302: numNhbrs = 3;
2303: }
2304:
2305: /**
2306: * returns the index of the face that neighbors the edge supplied
2307: * by the parameter
2308: */
2309: int getNeighbor(int edge) {
2310: return edges[edge].face;
2311: }
2312:
2313: /**
2314: * returns the index of the edge that is shared by the triangle
2315: * specified by the key parameter
2316: */
2317: int findSharedEdge(int key) {
2318: if (edges[0].face == key)
2319: return 0;
2320: else if (edges[1].face == key)
2321: return 1;
2322: else if (edges[2].face == key)
2323: return 2;
2324: else
2325: return -1; /* error */
2326: }
2327:
2328: int getEdgeIndex(Edge edge) {
2329: if (edges[0].equals(edge))
2330: return 0;
2331: else if (edges[1].equals(edge))
2332: return 1;
2333: else
2334: return 2;
2335: }
2336:
2337: void counterEdgeDel(Edge edge) {
2338: if (DEBUG) {
2339: System.out.println("counterEdgeDel");
2340: }
2341: if ((edges[0]).equals(edge)) {
2342: edges[0].face = EMPTY;
2343: numNhbrs--;
2344: } else if ((edges[1]).equals(edge)) {
2345: edges[1].face = EMPTY;
2346: numNhbrs--;
2347: } else if ((edges[2]).equals(edge)) {
2348: edges[2].face = EMPTY;
2349: numNhbrs--;
2350: } else {
2351: if (DEBUG) {
2352: System.out.println("error in counterEdgeDel");
2353: }
2354: }
2355: }
2356:
2357: void printAdjacency() {
2358: System.out.println("Face " + key + ": ");
2359: System.out.println("\t numNhbrs = " + numNhbrs);
2360: System.out.println("\t edge 0: Face " + edges[0].face);
2361: System.out.println("\t edge 1: Face " + edges[1].face);
2362: System.out.println("\t edge 2: Face " + edges[2].face);
2363: }
2364:
2365: void printVertices() {
2366: System.out.println("Face " + key + ": (" + verts[0].index
2367: + ", " + verts[1].index + ", " + verts[2].index
2368: + ")");
2369: }
2370: }
2371:
2372: /**
2373: * stores the information for a face node
2374: */
2375: class Node {
2376: Face face; // the data: the face
2377: Node parent; // the parent node
2378: Node left; // the left child
2379: Node right; // the right child
2380: int depth; // the topological distance of the node from the root
2381: int numChildren; // the number of children
2382: int attrib; // characteristic of the node eg. color
2383:
2384: // the attributes - 3 states for the Node
2385: static final int WHITE = 0; // not being accessed yet
2386: static final int GREY = 1; // being accessed but not done yet
2387: static final int BLACK = 2; // done
2388:
2389: Node(Face f) {
2390: face = f;
2391: }
2392:
2393: /**
2394: * inserts this node below the parent supplied.
2395: */
2396: void insert(Node p) {
2397: parent = p;
2398: depth = p.depth + 1;
2399: attrib = GREY;
2400:
2401: if (parent.left == null)
2402: parent.left = this ;
2403: else
2404: parent.right = this ;
2405: (parent.numChildren)++;
2406: }
2407:
2408: /**
2409: * remove this node from its parent
2410: */
2411: void remove() {
2412: if (parent != null) {
2413: if (parent.left == this ) {
2414: parent.left = parent.right;
2415: parent.right = null;
2416: } else {
2417: parent.right = null;
2418: }
2419: (parent.numChildren)--;
2420: }
2421: }
2422:
2423: /**
2424: * sets the depth to 0 and the attrib to GREY
2425: */
2426: void setRoot() {
2427: depth = 0;
2428: attrib = GREY;
2429: }
2430:
2431: /**
2432: * returns true if the attrib is WHITE
2433: */
2434: boolean notAccessed() {
2435: return (attrib == WHITE);
2436: }
2437:
2438: /**
2439: * sets the color to BLACK
2440: */
2441: void processed() {
2442: attrib = BLACK;
2443: }
2444:
2445: /**
2446: * a node is the root if it doesn't have a parent
2447: */
2448: boolean isRoot() {
2449: return (parent == null);
2450: }
2451:
2452: /**
2453: * prints the information in this Node
2454: */
2455: void print() {
2456: System.out.println(this );
2457: System.out.println("Node depth: " + depth);
2458: face.printVertices();
2459: System.out.print("parent: ");
2460: if (parent != null)
2461: parent.face.printVertices();
2462: else
2463: System.out.println("null");
2464: System.out.print("left: ");
2465: if (left != null)
2466: left.face.printVertices();
2467: else
2468: System.out.println("null");
2469: System.out.print("right: ");
2470: if (right != null)
2471: right.face.printVertices();
2472: else
2473: System.out.println("null");
2474: System.out.println("attrib: " + attrib);
2475: System.out.println("");
2476: }
2477: }
2478:
2479: /**
2480: * sorts the Nodes by depth
2481: */
2482: class SortedList {
2483:
2484: ArrayList list;
2485:
2486: /**
2487: * create a new SortedList
2488: */
2489: SortedList() {
2490: list = new ArrayList();
2491: }
2492:
2493: /**
2494: * insert into the list sorted by depth. start looking at start
2495: * to save some time. Returns the index of the next item of the
2496: * inserted element
2497: */
2498: int sortedInsert(Node data, int start) {
2499: // adjust start to where insert sorted
2500: while ((start < list.size())
2501: && (((Node) list.get(start)).depth <= data.depth)) {
2502: start++;
2503: }
2504:
2505: // insert at start index
2506: list.add(start, data);
2507:
2508: // return start+1 -- the index of the next element
2509: return (start + 1);
2510: }
2511:
2512: /**
2513: * remove and return 1st element
2514: */
2515: Node pop() {
2516: if (!list.isEmpty())
2517: return (Node) list.remove(0);
2518: else
2519: return null;
2520: }
2521: }
2522:
2523: class Istream {
2524:
2525: // fan encoding
2526: boolean fan = false;
2527: // length of the strip
2528: int length = 0;
2529: // array that specifies triangle strip
2530: Vertex[] istream;
2531: // indices of the head and tail vertices
2532: int head, tail;
2533:
2534: /**
2535: * creates a new Istream to store the triangle strip
2536: */
2537: Istream(Vertex[] list, int size, boolean isFan) {
2538: if (size == 0)
2539: throw new RuntimeException("size is 0");
2540: fan = isFan;
2541: length = size;
2542: istream = new Vertex[length];
2543: int i;
2544: System.arraycopy(list, 0, istream, 0, length);
2545: }
2546:
2547: /**
2548: * adds a new vertex to the end of the stream
2549: * makes the int array bigger, if necessary
2550: */
2551: void append(Vertex vertex) {
2552: growArray();
2553: // add in new vertex
2554: istream[length] = vertex;
2555: length++;
2556: }
2557:
2558: /**
2559: * turns the encoding (..., -3, -2, -1) into (.... -3, -2, -3, -1)
2560: * so that zero-area triangle (-3, -2. -3) is added
2561: */
2562: void swapEnd() {
2563: growArray();
2564: istream[length] = istream[length - 1];
2565: istream[length - 1] = istream[length - 3];
2566: length++;
2567: }
2568:
2569: /**
2570: * makes the array bigger, if necessary
2571: */
2572: void growArray() {
2573: if (length >= istream.length) {
2574: Vertex[] old = istream;
2575: // for now add enough space to add three more vertices
2576: // may change this later
2577: istream = new Vertex[length + 3];
2578: System.arraycopy(old, 0, istream, 0, length);
2579: }
2580: }
2581:
2582: /**
2583: * inverts the istream
2584: */
2585: void invert() {
2586: Vertex[] tmp = new Vertex[istream.length];
2587: // reverse the stream
2588: for (int i = 0; i < length; i++) {
2589: tmp[i] = istream[length - i - 1];
2590: }
2591: // copy it back
2592: System.arraycopy(tmp, 0, istream, 0, istream.length);
2593: tmp = null;
2594: // swap the head and the tail
2595: int swap = head;
2596: head = tail;
2597: tail = swap;
2598: }
2599:
2600: /**
2601: * concats two streams into one big stream
2602: */
2603: void addStream(Istream strm) {
2604: // System.out.println("addStream");
2605: int strmLen = strm.length;
2606: int size = strmLen + length - 2;
2607:
2608: // make the istream bigger
2609: if (size >= istream.length) {
2610: Vertex[] old = istream;
2611: istream = new Vertex[size];
2612: System.arraycopy(old, 0, istream, 0, length);
2613: }
2614:
2615: // add the strm to istream
2616: System.arraycopy(strm.istream, 2, istream, length,
2617: strmLen - 2);
2618:
2619: tail = strm.tail;
2620: length = size;
2621: strm.length = 0;
2622: strm.istream = null;
2623: }
2624: }
2625: }
|