stripifier.java

JAVA3D矩陈的相关类

	}
	if (i <= (edges.length-1)) edges[i].face = EMPTY;

	// check, for each face, if it is duplicated.  For a face that
	// neighbors its duplicate in the adjacency graph, it's possible
	// that two or more of its neighbors are the same (the duplicate).
	// This will be corrected to avoid introducing redundant faces
	// later on

	for (i = 0; i < faces.length; i++) {
	    face = faces[i];
 	    if (face.numNhbrs == 3) {
		if ((j1 = face.edges[1].face) == face.edges[0].face) {
		    face.edges[1].face = EMPTY;
		    face.numNhbrs--;
		    faces[j1].counterEdgeDel(face.edges[1]);
		}
		if ((j2 = face.edges[2].face) == face.edges[0].face) {
		    face.edges[2].face = EMPTY;
		    face.numNhbrs--;
		    faces[j2].counterEdgeDel(face.edges[2]);
		}
 		if ((face.edges[1].face != EMPTY) && (j1 == j2)) {
		    face.edges[2].face = EMPTY;
		    face.numNhbrs--;
		    faces[j1].counterEdgeDel(face.edges[2]);
		}
	    }
	}
    }

    /**
     * Sorts the edges using BubbleSort
     */
    void sortEdges(Edge[] edges) {
	int i = edges.length;
	boolean sorted = false;
	Edge temp = null;
	while ((i > 1) && !sorted) {
	    sorted = true;
	    for (int j = 1; j < i; j++) {
		if (edges[j].lessThan(edges[j-1])) {
		    temp = edges[j-1];
		    edges[j-1] = edges[j];
		    edges[j] = temp;
		    sorted = false;
		}
	    }
	    i--;
	}
    }

    /**
     * uses quicksort to sort the edges
     */
    void quickSortEdges(Edge[] edges, int l, int r) {
	if (edges.length > 0) {
	    int i = l;
	    int j = r;
	    Edge k = edges[(l+r) / 2];

	    do {
		while (edges[i].lessThan(k)) i++;
		while (k.lessThan(edges[j])) j--;
		if (i <= j) {
		    Edge tmp = edges[i];
		    edges[i] = edges[j];
		    edges[j] = tmp;
		    i++;
		    j--;
		}
	    } while (i <= j);

	    if (l < j) quickSortEdges(edges, l, j);
	    if (l < r) quickSortEdges(edges, i, r);
	}
    }

    /**
     * Takes a list of faces as input and performs a hybrid search, a
     * variated depth first search that returns to the highest level node
     * not yet fully explored.  Returns an array of pointers to the faces
     * found in order from the search.  The faceNodes parameter is an
     * array of the Nodes created for the faces.
     */
    Node[] hybridSearch(Face[] faces, Node[] faceNodes) {

	int numFaces = faces.length;
	int i = 0, j = 0, k = 0, ind = 0;

	// keep # of faces with certain # of neighbors
	int[] count = {0, 0, 0, 0};

	// faces sorted by number of neighbors
	int[] index = new int[numFaces];
	// the index of a certain face in the sorted array
	int[] rindex = new int[numFaces];

	// Control list pop up operation
	boolean popFlag = false;

	// queue of pointers to faces found in search
	Node[] queue = new Node[numFaces];
	// root of depth first tree
	Node source;
	// for the next node
	Node nnode;
	// a face
	Face face;
	// starting position for insertion into the list
	int start = 0;
	// list for search
	SortedList dlist;

	// count how many faces have a certain # of neighbors and
	// create a Node for each face
	for (i = 0; i < numFaces; i++) {
	    j = faces[i].numNhbrs;
	    count[j]++;
	    faceNodes[i] = new Node(faces[i]);
	}

	// to help with sorting
	for (i = 1; i < 4; i++) {
	    count[i] += count[i-1];
	}

	// decreasing i to make sorting stable
	for (i = numFaces - 1; i >= 0; i--) {
	    j = faces[i].numNhbrs;
	    count[j]--;
	    index[count[j]] = i;
	    rindex[i] = count[j];
	}

	// start the hybrid search
	for (i = 0; i < numFaces; i++) {
	    if (index[i] != EMPTY) {
		dlist = new SortedList();
		source = faceNodes[index[i]];
		source.setRoot();
		queue[ind] = source;
		ind++;
		index[i] = EMPTY;

		while (source != null) {
		    nnode = null;
		    // use the first eligible for continuing search
		    face = source.face;
		    for (j = 0; j < 3; j++) {
			k = face.getNeighbor(j);
			if ((k != EMPTY) &&
			    (faceNodes[k].notAccessed())) {
			    nnode = faceNodes[k];
			    break;
			}
		    }

		    if (nnode != null) {
			// insert the new node
			nnode.insert(source);
			if (!popFlag) {
			    start = dlist.sortedInsert(source, start);
			}
			else popFlag = false;
			source = nnode;
			queue[ind] = source;
			ind++;
			index[rindex[k]] = EMPTY;
		    }
		    else {
			source.processed();
			source = dlist.pop();
			popFlag = true;
			start = 0;
		    }
		} // while -- does popFlag need to be set to false here?
	    }
	}
	return queue;
    }

    Node[] dfSearch(Face[] faces, Node[] faceNodes) {
	int numFaces = faces.length;
	int i = 0, j = 0, k = 0, ind = 0;

	// keep certain # of faces with certain # of neighbors
	int[] count = {0, 0, 0, 0};

	// faces sorted by # of neighbors
	int[] index = new int[numFaces];
	// index of a certain face in the sorted array
	int[] rindex = new int[numFaces];

	// queue of pointers to faces found in the search
	Node[] queue = new Node[numFaces];
	// root of the depth first tree
	Node source;
	// the current node
	Node node;
	// for the next Node
	Node nnode;
	// a face
	Face face;

	// count how many faces have a certain # of neighbors and create
	// a Node for each face
	for (i = 0; i < numFaces; i++) {
	    j = faces[i].numNhbrs;
	    count[j]++;
	    faceNodes[i] = new Node(faces[i]);
	}

	// to help with sorting
	for (i = 1; i < 4; i++) count[i] += count[i-1];

	// dec i to make sorting stable
	for (i = numFaces-1; i >= 0; i--) {
	    j = faces[i].numNhbrs;
	    count[j]--;
	    index[count[j]] = i;
	    rindex[i] = count[j];
	}

	setNumNhbrs(faces);
	// start the dfs
	for (i = 0; i < numFaces; i++) {
	    if (index[i] != EMPTY) {
		source = faceNodes[index[i]];
		source.setRoot();
		queue[ind] = source;
		ind++;
		index[i] = EMPTY;
		node = source;

		do {
		    // if source has been done, stop
		    if ((node == source) && (node.right != null)) break;

		    nnode = null;
 		    face = node.face;

		    //  		    for (j = 0; j < 3; j++) {
		    //  			if (((k = face.getNeighbor(j)) != EMPTY) &&
		    //  			    (faceNodes[k].notAccessed())) {
		    //  			    nnode = faceNodes[k];
		    //  			    break;
		    //  			}
		    //  		    }

 		    k = findNext(node, faceNodes, faces);
 		    if (k != EMPTY) nnode = faceNodes[k];
 		    if (nnode != null) updateNumNhbrs(nnode);

		    if (nnode != null) {
			// insert new node
			nnode.insert(node);
			node = nnode;
			queue[ind] = node;
			ind++;
			index[rindex[k]] = EMPTY;
		    }
		    else {
			node.processed();
			node = node.parent;
		    }
		} while (node != source.parent);
	    }
	}
	freeNhbrTable();
	return queue;
    }

    int findNext(Node node, Node[] faceNodes, Face[] faces) {
	Face face = node.face;
	// this face has no neighbors so return
	if (face.numNhbrs == 0) return EMPTY;

	int i, j, count;
	int[] n = new int[3];  // num neighbors of neighboring face
	int[] ind = {-1, -1, -1}; // neighboring faces

	// find the number of neighbors for each neighbor
	count = 0;
	for (i = 0; i < 3; i++) {
	    if (((j = face.getNeighbor(i)) != EMPTY) &&
		(faceNodes[j].notAccessed())) {
		ind[count] = j;
		n[count] = numNhbrs[j];
		count++;
	    }
	}

	// this face has no not accessed faces
	if (count == 0) return EMPTY;

	// this face has only one neighbor
	if (count == 1) return ind[0];

	if (count == 2) {
	    // if the number of neighbors are the same, try reseting
	    if ((n[0] == n[1]) && (n[0] != 0)) {
		n[0] = resetNhbr(ind[0], faces, faceNodes);
		n[1] = resetNhbr(ind[1], faces, faceNodes);
	    }
	    // if one neighbor has fewer neighbors, return that neighbor
	    if (n[0] < n[1]) return ind[0];
	    if (n[1] < n[0]) return ind[1];
	    // neighbors tie.  pick the sequential one
	    Node pnode, ppnode;
	    Face pface, ppface;
	    if ((pnode = node.parent) != null) {
		pface = pnode.face;
		i = pface.findSharedEdge(face.key);
		if ((ppnode = pnode.parent) != null) {
		    ppface = ppnode.face;
		    if (pface.getNeighbor((i+1)%3) == ppface.key) {
			j = pface.verts[(i+2)%3].index;
		    }
		    else {
			j = pface.verts[(i+1)%3].index;
		    }
		}
		else {
		    j = pface.verts[(i+1)%3].index;
		}
		i = face.findSharedEdge(ind[0]);
		if (face.verts[i].index == j) return ind[0];
		else return ind[1];
	    }
	    else return ind[0];
	}
	// three neighbors
	else {
	    if ((n[0] < n[1]) && (n[0] < n[2])) return ind[0];
	    else if ((n[1] < n[0]) && (n[1] < n[2])) return ind[1];
	    else if ((n[2] < n[0]) && (n[2] < n[1])) return ind[2];
	    else if ((n[0] == n[1]) && (n[0] < n[2])) {
		if (n[0] != 0) {
		    n[0] = resetNhbr(ind[0], faces, faceNodes);
		    n[1] = resetNhbr(ind[1], faces, faceNodes);
		}
		if (n[0] <= n[1]) return ind[0];
		else return ind[1];
	    }
	    else if ((n[1] == n[2]) && n[1] < n[0]) {
		if (n[1] != 0) {
		    n[1] = resetNhbr(ind[1], faces, faceNodes);
		    n[2] = resetNhbr(ind[2], faces, faceNodes);
		}
		if (n[1] <= n[2]) return ind[1];
		else return ind[2];
	    }
	    else if ((n[2] == n[0]) && (n[2] < n[1])) {
		if (n[0] != 0) {
		    n[0] = resetNhbr(ind[0], faces, faceNodes);
		    n[2] = resetNhbr(ind[2], faces, faceNodes);
		}
		if (n[0] <= n[2]) return ind[0];
		else return ind[2];
	    }
	    else {
		if (n[0] != 0) {
		    n[0] = resetNhbr(ind[0], faces, faceNodes);
		    n[1] = resetNhbr(ind[1], faces, faceNodes);
		    n[2] = resetNhbr(ind[2], faces, faceNodes);
		}
		if ((n[0] <= n[1]) && (n[0] <= n[2])) return ind[0];
		else if (n[1] <= n[2]) return ind[1];
		else return ind[2];
	    }
	}
    }

    void setNumNhbrs(Face[] faces) {
	int numFaces = faces.length;
	numNhbrs = new int[numFaces];
	for (int i = 0; i < numFaces; i++) {
	    numNhbrs[i] = faces[i].numNhbrs;
	}
    }

    void freeNhbrTable() {
	numNhbrs = null;
    }

    void updateNumNhbrs(Node node) {
	Face face = node.face;
	int i;
	if ((i = face.getNeighbor(0)) != EMPTY) numNhbrs[i]--;
	if ((i = face.getNeighbor(1)) != EMPTY) numNhbrs[i]--;
	if ((i = face.getNeighbor(2)) != EMPTY) numNhbrs[i]--;
    }

    int resetNhbr(int y, Face[] faces, Node[] faceNodes) {
	int x = EMPTY;
	Face nface = faces[y];
	int i;
	for (int j = 0; j < 3; j++) {
	    if (((i = nface.getNeighbor(j)) != EMPTY) &&
		(faceNodes[i].notAccessed())) {
		if ((x == EMPTY) || (x > numNhbrs[i])) x = numNhbrs[i];
	    }
	}
	return x;
    }

    /**
     * generates hamiltonian strips from the derived binary spanning tree
     * using the path peeling algorithm to peel off any node wiht double
     * children in a bottom up fashion.  Returns a Vector of strips.  Also
     * return the number of strips and patches in the numStrips and
     * numPatches "pointers"
     */
    ArrayList hamilton(Node[] sTree, int[] numStrips, int[] numPatches) {
	// the number of nodes in the tree
	int numNodes = sTree.length;
	// number of strips
	int ns = 0;
	// number of patches
	int np = 0;
	// some tree node variables
	Node node, pnode, cnode;
	// the Vector of strips
	ArrayList strips = new ArrayList();
	// the current strip
	ArrayList currStrip;

	// the tree nodes are visited in such a bottom-up fashion that
	// any node is visited prior to its parent
	for (int i = numNodes - 1; i >= 0; i--) {
	    cnode = sTree[i];

	    // if cnode is the root of a tree create a strip
	    if (cnode.isRoot()) {
		// each patch is a single tree
		np++;
		// create a new strip
		currStrip = new ArrayList();
		// insert the current node into the list
		currStrip.add(0, cnode.face);

		// add the left "wing" of the parent node to the strip
		node = cnode.left;
		while (node != null) {
		    currStrip.add(0, node.face);
		    node = node.left;
		}

		// add the right "wing" of the parent node to the strip
		node = cnode.right;
		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);
	    }

	    // if the number of children of this node is 2, create a strip
	    else if (cnode.numChildren == 2) {
		// if the root has a single child with double children, it
		// could be left over as a singleton.  However, the following
		// rearrangement reduces the chances
  		pnode = cnode.parent;
  		if (pnode.isRoot() && (pnode.numChildren == 1)) {
  		    pnode = cnode.right;
  		    if (pnode.left != null) cnode = pnode;
  		    else cnode = cnode.left;
  		}

		// handle non-root case

 		// remove the node
 		cnode.remove();

		// create a new strip
		currStrip = new ArrayList();
		// insert the current node into the list
		currStrip.add(0, cnode.face);

		// add the left "wing" of cnode to the list
		node = cnode.left;
		while (node != null) {
		    currStrip.add(0, node.face);
		    node = node.left;
		}

		// add the right "wing" of cnode to the list
		node = cnode.right;