stripifier.java

JAVA3D矩陈的相关类

		while (node != null) {
		    currStrip.add(currStrip.size(), node.face);
		    node = node.left;
		}

		// increase the number of strips
		ns++;
		// add the strip to the Vector
		strips.add(currStrip);
	    }
	}

	// put the ns and np in the "pointers to return
	numStrips[0] = ns;
	numPatches[0] = np;

	// return the strips
	return strips;
    }

    /**
     * creates the triangle strips
     */
    ArrayList stripe(ArrayList strips) {
	int numStrips = strips.size();  // the number of strips
	int count;  // where we are in the hamiltonian
	Face face;  // the face we are adding to the stream
	Face prev;  // the previous face added to the stream
	boolean done;  // whether we are done with the current strip
	boolean cont;  // whether we should continue the current stream
	ArrayList currStrip;  // the current hamiltonian
	Istream currStream;  // the stream we are building
	ArrayList istreams = new ArrayList();  // the istreams to return
	boolean ccw = true;;  // counter-clockwise
	int share;  // the shared edge
	Vertex[] buf = new Vertex[4]; // a vertex array to start the stream

	// create streams for each hamiltonian
	for (int i = 0; i < numStrips; i++) {
	    currStrip = (ArrayList)strips.get(i);
	    count = 0;
	    done = false;
	    face = getNextFace(currStrip, count++);

	    // while we are not done with the current hamiltonian
	    while (!done) {
		cont = true;

		// if the current face is the only one left in the current
		// hamiltonian
		if (stripDone(currStrip, count)) {
		    // create a new istream with the current face
		    currStream = new Istream(face.verts, 3, false);
		    // set the head of the strip to this face
		    currStream.head = face.key;
		    done = true;
		    // since we are done with the strip, set the tail to this
		    // face
		    currStream.tail = face.key;
		}

		else {
		    prev = face;
		    face = getNextFace(currStrip, count++);

		    // put the prev vertices in the correct order
		    // to add the next tri on
		    share = prev.findSharedEdge(face.key);
		    buf[0] = prev.verts[share];
		    buf[1] = prev.verts[(share+1)%3];
		    buf[2] = prev.verts[(share+2)%3];

		    // find the fourth vertex
		    if (CHECK_ORIENT) {
			// check for clockwise orientation
			if (checkOrientCWSeq(buf[2], buf[1], face)) {
			    share = face.findSharedEdge(prev.key);
			    buf[3] = face.verts[share];
			    currStream = new Istream(buf, 4, false);
			    // set the head of this strip to the prev face
			    currStream.head = prev.key;
			    // if this was the last tri in the strip, then
			    // we are done
			    if (stripDone(currStrip, count)) {
				done = true;
				// set the tail for the strip to current face
				currStream.tail = face.key;
			    }
			}
			else {
			    cont = false;
			    currStream = new Istream(buf, 3, false);
			    // set the head to the prev face
			    currStream.head = prev.key;
			    // since we are not continuing, set
			    // the tail to prev also
			    currStream.tail = prev.key;
			}

			// orientation starts counter-clockwise for 3rd face
			ccw = true;
		    }
		    else {
			share = face.findSharedEdge(prev.key);
			buf[3] = face.verts[share];
			currStream = new Istream(buf, 4, false);
			// set the head of this strip to the prev face
			currStream.head = prev.key;
			// if this was the last tri in the strip, then
			// we are done
			if (stripDone(currStrip, count)) {
			    done = true;
			    // set the tail for the strip to current face
			    currStream.tail = face.key;
			}
		    }

		    // while continue and the strip isn't finished
		    // add more faces to the stream
		    while (cont && !stripDone(currStrip, count)) {
			prev = face;
			face = getNextFace(currStrip, count++);
			share = face.findSharedEdge(prev.key);

			// if we can add the face without adding any
			// zero area triangles
			if (seq(currStream, face, share)) {
			    if (CHECK_ORIENT) {
				// if we can add the next face with the correct
				// orientation
				if (orientSeq(ccw, currStream, face)) {
				    // append the vertex opposite the
				    //shared edge
				    currStream.append(face.verts[share]);
				    // next face must have opposite orientation
				    ccw = (!ccw);
				    // if this was the last tri in the
				    //strip, then we are done
				    if (stripDone(currStrip, count)) {
					done = true;
					// since we are done with this strip,
					// set the tail to the current face
					currStream.tail = face.key;
				    }
				}
				// if we cannot add the face with the correct
				// orientation, do not continue with this
				// stream
				else {
				    cont = false;
				    // since we cannot continue with this strip
				    // set the tail to prev
				    currStream.tail = prev.key;
				}
			    }
			    else {
				// append the vertex opposite the
				//shared edge
				currStream.append(face.verts[share]);
				// if this was the last tri in the
				//strip, then we are done
				if (stripDone(currStrip, count)) {
				    done = true;
				    // since we are done with this strip,
				    // set the tail to the current face
				    currStream.tail = face.key;
				}
			    }
			}

			// need zero area tris to add continue the strip
			else {
			    if (CHECK_ORIENT) {
				// check the orientation for adding a zero
				// area tri and this face
				if (orientZAT(ccw, currStream, face)) {
				    // swap the end of the current stream to
				    // add a zero area triangle
				    currStream.swapEnd();
				    // append the vertex opposite the
				    // shared edge
				    currStream.append(face.verts[share]);
				    // if this was the last tri in the
				    // strip then we are done
				    if (stripDone(currStrip, count)) {
					done = true;
					// set the tail because we are done
					currStream.tail = face.key;
				    }
				}
				// if we cannot add the face with the correct
				// orientation, do not continue with this
				// stream
				else {
				    cont = false;
				    // since we cannot continue with this face,
				    // set the tail to the prev face
				    currStream.tail = prev.key;
				}
			    }
			    else {
				// swap the end of the current stream to
				// add a zero area triangle
				currStream.swapEnd();
				// append the vertex opposite the
				// shared edge
				currStream.append(face.verts[share]);
				// if this was the last tri in the
				// strip then we are done
				if (stripDone(currStrip, count)) {
				    done = true;
				    // set the tail because we are done
				    currStream.tail = face.key;
				}
			    }
			}
		    } // while (cont && !stripDone)
		} // else

		// add the current strip to the strips to be returned
		istreams.add(currStream);
	    } // while !done
	} // for each hamiltonian
	return istreams;
    } // stripe

    boolean stripDone(ArrayList strip, int count) {
	if (count < strip.size()) {
	    return false;
	}
	else return true;
    }

    boolean seq(Istream stream, Face face, int share) {
	int length = stream.length;
	Vertex v1 = face.edges[share].v1;
	Vertex v2 = face.edges[share].v2;
	Vertex last = stream.istream[length-1];
	Vertex prev = stream.istream[length-2];
	if (((v1.equals(prev)) && (v2.equals(last))) ||
	    ((v1.equals(last)) && (v2.equals(prev)))) {
	    return true;
	}
	else return false;
    }

    boolean orientSeq(boolean ccw, Istream stream, Face face) {
	int length = stream.length;
	Vertex last = stream.istream[length-1];
	Vertex prev = stream.istream[length-2];
	if ((ccw && checkOrientCCWSeq(last, prev, face)) ||
	    ((!ccw) && checkOrientCWSeq(last, prev, face))) {
	    return true;
	}
	else return false;
    }

    boolean orientZAT(boolean ccw, Istream stream, Face face) {
	int length = stream.length;
	Vertex last = stream.istream[length-1];
	Vertex swap = stream.istream[length-3];
	if ((ccw && checkOrientCWSeq(last, swap, face)) ||
	    ((!ccw) && checkOrientCCWSeq(last, swap, face))) {
	    return true;
	}
	else return false;
    }

    boolean checkOrientCWSeq(Vertex last, Vertex prev, Face face) {
	System.out.println("checkOrientCWSeq");
	System.out.println("last = " + last.index);
	System.out.println("prev = " + prev.index);
	System.out.print("face = ");
	face.printVertices();
	if (last.equals(face.verts[0])) {
	    if (!prev.equals(face.verts[1])) {
		if (DEBUG) System.out.println("ORIENTATION PROBLEM!");
		return false;
	    }
	}
	else if (last.equals(face.verts[1])) {
	    if (!prev.equals(face.verts[2])) {
		if (DEBUG) System.out.println("ORIENTATION PROBLEM!");
		return false;
	    }
	}
	else if (last.equals(face.verts[2])) {
	    if (!prev.equals(face.verts[0])) {
		if (DEBUG) System.out.println("ORIENTATION PROBLEM!");
		return false;
	    }
	}
	return true;
    }

    boolean checkOrientCCWSeq(Vertex last, Vertex prev, Face face) {
	System.out.println("checkOrientCCWSeq");
	System.out.println("last = " + last.index);
	System.out.println("prev = " + prev.index);
	System.out.print("face = ");
	face.printVertices();
	if (prev.equals(face.verts[0])) {
	    if (!last.equals(face.verts[1])) {
		System.out.println("ORIENTATION PROBLEM!");
		return false;
	    }
	}
	else if (prev.equals(face.verts[1])) {
	    if (!last.equals(face.verts[2])) {
		System.out.println("ORIENTATION PROBLEM!");
		return false;
	    }
	}
	else if (prev.equals(face.verts[2])) {
	    if (!last.equals(face.verts[0])) {
		System.out.println("ORIENTATION PROBLEM!");
		return false;
	    }
	}
	return true;
    }

    Face getNextFace(ArrayList currStrip, int index) {
	if (currStrip.size() > index) return (Face)currStrip.get(index);
	else return null;
    }

    /**
     * joins tristrips if their end triangles neighbor each other.  The
     * priority is performed in three stages: strips are concatenated to
     * save 2, 1, or no vertices
     */
    void concatenate(ArrayList strips, Face[] faces) {
	int numFaces = faces.length;
	int[] faceTable = new int[numFaces];
	Istream strm;

	// initialize the face table to empty
	for (int i = 0; i < numFaces; i++) {
	    faceTable[i] = EMPTY;
	}

	// set up the faceTable so that a face index relates to a strip
	// that owns the face as one of its end faces
	for (int i = 0; i < strips.size(); i++) {
	    strm = (Istream)strips.get(i);
	    faceTable[strm.head] = i;
	    faceTable[strm.tail] = i;
	}

	if (DEBUG) {
	    System.out.println("");
	    System.out.println("faceTable:");
	    for (int i = 0; i < faceTable.length; i++) {
		System.out.println(faceTable[i]);
	    }
	    System.out.println("");
	}

 	reduceCostByTwo(strips, faces, faceTable);
   	reduceCostByOne(strips, faces, faceTable);
   	reduceCostByZero(strips, faces, faceTable);
    }

    /**
     * find all the links that reduce the cost by 2
     */
    void reduceCostByTwo(ArrayList strips, Face[] faces, int[] faceTable) {
	//  	System.out.println("reduceCostByTwo");
	// number of faces in the face array
	int numFaces = faces.length;
	// possible adjacent strips
	int id, id1, id2;
	// Istreams
	Istream strm, strm1;
	// the length of the Istrem
	int len, len1;
	// vertex sequences for tristrips
	Vertex[] seq, seq1;
	// a face
	Face face;
	// the list of vertices for the face
	Vertex[] verts;
	// used to syncronize the orientation
	boolean sync, sync1;
	// a swap variable
	Vertex swap;

	for (int i = 0; i < numFaces; i++) {
	    id = faceTable[i];
	    if (id != EMPTY) {
		sync = false; sync1 = false;
		strm = (Istream)strips.get(id);
		len = strm.length;
		seq = strm.istream;
		face = faces[i];
		verts = face.verts;

		// sequential strips
		if (!strm.fan) {

		    // a singleton strip
		    if (len == 3) {

			// check all three neighbors
			for (int j = 0; j < 3; j++) {
			    int k = face.getNeighbor(j);
			    if ((k != EMPTY) &&
				((id1 = faceTable[k]) != EMPTY) &&
				(id1 != id)) {
				// reassign the sequence
				seq[0] = verts[j];
				seq[1] = verts[(j+1)%3];
				seq[2] = verts[(j+2)%3];

				// the neighboring stream
				strm1 = (Istream)strips.get(id1);
				len1 = strm1.length;
				if (k != strm1.head) {
				    strm1.invert();
				    // if the length is odd set sync1 to true
				    if ((len1 % 2) != 0) sync1 = true;
				}
				seq1 = strm1.istream;

				// append a singleton strip
				if (len1 == 3) {
				    //   				    System.out.println("reduce2");
				    int m = faces[k].findSharedEdge(i);
				    strm.append(faces[k].verts[m]);
				    strm1.length = 0;
				    strm1.istream = null;
				    strm.tail = k;
				    faceTable[k] = id;
				    i--;
				    break;
				}

				// append a strip of length over 2
				else {
				    if ((len1 == 4) &&
					(seq[1].index == seq1[0].index) &&
					(seq[2].index == seq1[2].index)) {

					// swap seq1[1] and seq1[2] so that
					// seq[1] == seq1[0] and
					// seq[1] == seq1[1]
					swap = seq1[1];
					seq1[1] = seq1[2];
					seq1[2] = swap;
				    }

				    // see if we can join the strips
				    if ((seq[1].index == seq1[0].index) &&
					(seq[2].index == seq1[1].index)) {
					//   					System.out.println("reduce2");
					// add the stream in
					strm.addStream(strm1);
					faceTable[k] = EMPTY;
					faceTable[strm.tail] = id;

					i--;
					break;
				    }
				    else if (sync1) {
					strm1.invert();
					sync1 = false;
				    }
				}
			    }
			}
		    }

		    // not a singleton strip

		    // can append a stream where the current face is the tail
		    // or is an even length so we can invert it
		    else if ((i == strm.tail) || ((len % 2) == 0)) {
			// if the current face isn't the tail, then
			// have to invert the strip
			if (i != strm.tail) {
			    strm.invert();
			    seq = strm.istream;
			}

			// 			System.out.println("seq.length = " + seq.length);
			// 			System.out.println("len = " + len);
			// 			System.out.print("seq = ");
			// 			for (int l = 0; l < seq.length; l++) {
			// 			    if (seq[l] == null) System.out.print(" null");
			// 			    else System.out.print(" " + seq[l].index);
			// 			}
			// 			System.out.println("");