bprocessor-commit

[Nordholt <nor...@us...>]

Update of /cvsroot/bprocessor/model/src/net/sourceforge/bprocessor/model
In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv31556/src/net/sourceforge/bprocessor/model

Modified Files:
	Geometry.java 
Log Message:
added methods for simplifying geometry

Index: Geometry.java
===================================================================
RCS file: /cvsroot/bprocessor/model/src/net/sourceforge/bprocessor/model/Geometry.java,v
retrieving revision 1.49
retrieving revision 1.50
diff -C2 -d -r1.49 -r1.50
*** Geometry.java	29 Mar 2007 10:00:53 -0000	1.49
--- Geometry.java	29 Mar 2007 13:59:21 -0000	1.50
***************
*** 10,13 ****
--- 10,14 ----
  import java.util.ArrayList;
  import java.util.Collection;
+ 
  import java.util.Collections;
  import java.util.Comparator;
***************
*** 603,605 ****
--- 604,911 ----
      log.info(object);
    }
+   
+   /**
+    * Deletes all surfaces that have the same space assignment on each side
+    * @param surfaces a set of surfaces to delete from
+    * @return the set of surfaces that were deleted
+    */
+   public static Set<Surface> deleteRedundantSurfaces(Set<Surface> surfaces) {
+     Set<Surface> redundant = new HashSet<Surface>();
+     for (Surface s : surfaces) {
+       if (s.getFrontDomain() == s.getBackDomain()) {
+         redundant.add(s);
+         s.getFrontDomain().removeSurface(s);
+         s.delete();
+       }
+     }
+     return redundant;
+   }
+   
+   /**
+    * Deletes all surfaces that can be merged together and creates 
+    * new surfaces corresponding to the merge of those surfaces.
+    * @param surfaces a set of surfaces 
+    * @return the surfaces created by merging
+    */
+   public static Set<Surface> mergeAllPossibleSurfaces(Set<Surface> surfaces) {
+     Set<Surface> mergedSurfaces = new HashSet<Surface>();
+     Set<Surface> newSurfaces = new HashSet<Surface>();
+     for (Surface s : surfaces) {
+       Space front = s.getFrontDomain();
+       Space back = s.getBackDomain();
+       if (!mergedSurfaces.contains(s)) {
+         Set<Surface> merged = new HashSet<Surface>();
+         List<Edge> edgeList = mergeSurface(s, merged);
+         if (merged.size() > 1) {
+           mergedSurfaces.addAll(merged);
+           Surface newSurface = new Surface(edgeList);
+           for (Surface merge : merged) {
+             Collection<Surface> holes = merge.getHoles();
+             for (Surface hole : holes) {
+               newSurface.addHole(hole);
+             }
+           }
+           assignSame(s, newSurface, front, front);
+           assignSame(s, newSurface, back, back);
+           newSurfaces.add(newSurface);          
+         }
+       }
+     }
+     for (Surface s : mergedSurfaces) {
+       s.delete();
+     }
+     return newSurfaces;
+   }
+    
+   /**
+    * Merges a surface with all possible surrounding surfaces.
+    * @param surface the surface
+    * @param mergedSurfaces the surfaces that were allready merged, (for
+    * recursive calls.)
+    * @return a list of edges defining the contour of the merged surface
+    */
+   private static List<Edge> mergeSurface(Surface surface, Set<Surface> mergedSurfaces) {
+     List<Edge> edgeList = new LinkedList<Edge>(surface.getEdges());
+     mergedSurfaces.add(surface);
+     for (Edge e : surface.getEdges()) {
+       Set<Surface> surfaces = e.getSurfaces();
+       if (surfaces.size() == 2) {
+         surfaces.remove(surface);
+         Surface nextSurface = surfaces.iterator().next();
+         if (mergedSurfaces.contains(nextSurface)) {
+           edgeList.remove(e);
+         } else if (mergeTest(surface, nextSurface)) {
+           int index = edgeList.indexOf(e);
+           int listSize = edgeList.size();
+           Edge beforeIndex = edgeList.get((index - 1 + listSize) % listSize);
+           Edge afterIndex = edgeList.get((index + 1) % listSize);
+           
+           List<Edge> nextList = mergeSurface(nextSurface, mergedSurfaces);
+           if (!nextList.isEmpty()) {
+             Edge first = nextList.get(0);
+             Edge last = nextList.get(nextList.size() - 1);
+             if (Edge.commonVertex(first, beforeIndex) != null &&
+                 Edge.commonVertex(last, afterIndex) != null) {
+               edgeList.addAll(index, nextList);
+             } else if (Edge.commonVertex(last, beforeIndex) != null &&
+                        Edge.commonVertex(first, afterIndex) != null) {
+               Collections.reverse(nextList);
+               edgeList.addAll(index, nextList);
+             }
+           }
+           edgeList.remove(e);
+         }
+       }
+     }    
+     return edgeList; 
+   }
+ 
+   /**
+    * Tests if two surfaces can be merged. 
+    * The surfaces will be assumed to share an edge.
+    * @param s1 the first surface
+    * @param s2 the second surface
+    * @return wherther or not the surfaces can be merged.
+    */
+   private static boolean mergeTest(Surface s1, Surface s2) {
+     Vertex n1 = s1.normal();
+     Vertex n2 = s2.normal();
+     Plane p = s1.plane();
+     if (p.contains(s2)) {
+       Space front = s1.getFrontDomain();
+       Space back = s1.getBackDomain();
+       Space nextFront = s2.getFrontDomain();
+       Space nextBack = s2.getBackDomain();
+       if (n1.dot(n2) > 0) {
+         if (nextFront == front && nextBack == back) {
+           return true;
+         }
+       } else { 
+         if (nextBack == front && nextFront == back) {
+           return true;
+         }
+       }
+     }
+     return false;
+   }
+   
+   /**
+    * Collapses a set of vertices, so that all vertices that 
+    * lies in the same coordinates are replaced with one new vertex  
+    * @param vertices the set of vertices
+    */
+   public static void allPossibleCollapses(Set<Vertex> vertices) {
+     Set<Vertex> collapsable = firstCollapsSet(vertices);
+     while (!collapsable.isEmpty()) {
+       vertices.removeAll(collapsable);
+       collapsVertices(collapsable);
+       collapsable = firstCollapsSet(vertices);
+     }
+   }
+   
+   /**
+    * Finds the first vertex that has a collaps set in a set of vertices
+    * @param vertices the set of vertices
+    * @return the set of vertices that can be collapsed
+    */
+   private static Set<Vertex> firstCollapsSet(Set<Vertex> vertices) {
+     Set<Vertex> collapsable = new HashSet<Vertex>();
+     Set<Vertex> unChecked = new HashSet<Vertex>();
+     unChecked.addAll(vertices);
+     for (Vertex v1 : vertices) {
+       unChecked.remove(v1);
+       for (Vertex v2 : unChecked) {
+         if (v1.equalEps(v2)) {
+           collapsable.add(v2);
+         }
+       }
+       if (!collapsable.isEmpty()) {
+         collapsable.add(v1);
+         break;
+       }
+     }
+     return collapsable;
+   }
+   
+   /**
+    * Collapses a set of vertices  
+    * @param vertices vertices that should be collapsed to a single
+    *        vertex
+    */
+   private static void collapsVertices(Set<Vertex> vertices) {
+     if (vertices.size() > 0) {
+       Vertex collaps = vertices.iterator().next().copy();
+       for (Vertex v : vertices) {
+         Set<Edge> edges = v.getEdges();
+         for (Edge e : edges) {
+           if (e.getTo() == v) {
+             e.setTo(collaps);
+           } else if (e.getFrom() == v) {
+             e.setFrom(collaps);
+           }
+           e.changed();
+         }
+       }
+       for (Vertex v : vertices) {
+         v.delete();
+       }
+     }
+   }
+   
+   /**
+    * Finds edges in the set that can be extended and extends them 
+    * to their longest possible lenght (also if that means 
+    * replacing edges that are not in the set in which the method
+    * searches for extendable edges)
+    * @param edges the set of edges in which to search for extendable edges
+    */
+   public static void extendAllPossibleEdges(Set<Edge> edges) {
+     List<Edge> extendable = firstExtendList(edges);
+     while (!extendable.isEmpty()) {
+       log.info("extended");
+       extendEdges(extendable);
+       for (Edge e : extendable) {
+         e.delete();
+       }
+       edges.removeAll(extendable);
+       extendable = firstExtendList(edges);
+     }    
+   }
+   
+   /**
+    * Replaces a list of edges with a new edge. The list of edges are assummed
+    * to be a connected sequence of parrallel edges, that all longs to one 
+    * set of surfaces. The new edge will replace the sequence of edges in all of 
+    * the surfaces that the sequence belonged to.  
+    * @param extendable a list of extendable edges
+    */
+   private static void extendEdges(List<Edge> extendable) {   
+     if (extendable.size() > 1) {
+       Edge first = extendable.get(0);
+       Edge afterFirst = extendable.get(1);
+       Edge last = extendable.get(extendable.size() - 1);
+       Edge beforeLast = extendable.get(extendable.size() - 2);
+       Vertex from = first.otherVertex(Edge.commonVertex(first, afterFirst));
+       Vertex to = last.otherVertex(Edge.commonVertex(last, beforeLast));
+       Edge extendedEdge = new Edge(to, from);      
+       //All these edges should share all of their surfaces
+       Set<Surface> surfaces = first.getSurfaces();
+       for (Surface s : surfaces) {
+         s.replace(extendable, extendedEdge);
+         Space owner  = s.getOwner();
+         if (owner != null) {
+           owner.add(extendedEdge);
+         }
+       }
+     }
+   }
+ 
+   /**
+    * Returns the first set of extendable edges found
+    * @param edges the set of edges in wich to search for extendable edges
+    * @return a set of extendable edges
+    */
+   private static List<Edge>  firstExtendList(Set<Edge> edges) {
+     log.info("extend set size: " + edges.size());
+     List<Edge> extendable = new LinkedList<Edge>();
+     for (Edge e : edges) {
+       List<Edge> toList = extendList(e, e.getTo());
+       List<Edge> fromList = extendList(e, e.getFrom());
+       if (!toList.isEmpty() || !fromList.isEmpty()) {
+         log.info("break");
+         extendable.addAll(toList);
+         extendable.add(e);
+         extendable.addAll(fromList);
+         break;
+       }
+     }
+     log.info("extendable size: " + extendable.size());
+     return extendable;
+   }
+ 
+   /**
+    * Gives a list of all edges that extends an edge from 
+    * a given endpoint (to or from).
+    * @param e the edge 
+    * @param v an end point of the edge
+    * @return a list of edges that extends the edge from the given endpoint
+    * (notice, this is NOT including the first edge)
+    */
+   private static List<Edge> extendList(Edge e, Vertex v) {
+     List<Edge> extendList = new LinkedList<Edge>();
+     if (e.contains(v) && v.getEdges().size() == 2) {
+       Set<Edge> edges = v.getEdges();
+       edges.remove(e);
+       Edge otherEdge = edges.iterator().next();
+       if (e.parrallel(otherEdge) && 
+           e.getSurfaces().equals(otherEdge.getSurfaces())) {
+         extendList.add(otherEdge);
+         extendList.addAll(extendList(otherEdge, otherEdge.otherVertex(v)));
+       }
+     }
+     return extendList;
+   }
+   
+   /**
+    * Assign space sp2 to the same side of s2 as space sp1 is assigned to s1
+    * @param s1 first surface  
+    * @param s2 second surface
+    * @param sp1 first space 
+    * @param sp2 second space
+    */
+   public static void assignSame(Surface s1, Surface s2, Space sp1, Space sp2) {
+     if (s1.getFrontDomain() == sp1) {
+       if (s1.normal().dot(s2.normal()) > 0) {
+         s2.setFrontDomain(sp2);
+       } else {
+         s2.setBackDomain(sp2);
+       }
+     } else if (s1.getBackDomain() == sp1) {
+       if (s1.normal().dot(s2.normal()) > 0) {
+         s2.setBackDomain(sp2);
+       } else {
+         s2.setFrontDomain(sp2);
+       }
+     }   
+   }  
  }