src/edu/berkeley/qfat/geom/Polygon.java

   1 package edu.berkeley.qfat.geom;
   2 import javax.media.opengl.*;
   3 import java.util.*;
   4 import edu.berkeley.qfat.Mesh;
   5
   6 // FIXME: numerical stability issues galore
   7 /** a planar, convex, possibly infinite/open polygon */
   8 public final class Polygon {
   9
  10     public final Plane plane;
  11
  12     private final HalfSpace[] halfSpaces;
  13
  14     public Polygon(Plane plane) { this(plane, new HalfSpace[0]); }
  15
  16     public Polygon(Plane plane, HalfSpace[] halfSpaces) {
  17         this.plane = plane;
  18         this.halfSpaces = halfSpaces;
  19     }
  20
  21     public Polygon intersect(HalfSpace hs) {
  22         HalfSpace[] newHalfSpaces = new HalfSpace[halfSpaces.length+1];
  23         System.arraycopy(halfSpaces, 0, newHalfSpaces, 0, halfSpaces.length);
  24         newHalfSpaces[newHalfSpaces.length-1] = hs;
  25         return new Polygon(plane, newHalfSpaces);
  26     }
  27
  28     private static final float EPSILON = 0.00001f;
  29     private static float round(float f) {
  30         return Math.round(f*1000)/1000f;
  31     }
  32     public Triangle[] tesselate(Mesh mesh) {
  33         // FIXME: check for closedness
  34         // find a starting point
  35         HashSet<Segment> segments = new HashSet<Segment>();
  36         int i;
  37         for(i=0; i<halfSpaces.length; i++) {
  38             Point p1=null, p2=null;
  39             for(int j=0; j<halfSpaces.length; j++) {
  40                 if (i==j) continue;
  41                 Point p = plane.intersect(halfSpaces[i], halfSpaces[j]);
  42                 if (p==null) continue;
  43
  44                 //p = new Point(round(p.x), round(p.y), round(p.z));
  45
  46                 for(int k=0; k<halfSpaces.length; k++) {
  47                     if (i==k || j==k) continue;
  48                     if (!halfSpaces[k].contains(p)) { p = null; break; }
  49                 }
  50                 if (p!=null) {
  51                     if (p1==null) p1 = p;
  52                     else if (p2==null) { if (p.distance(p1)>EPSILON) p2 = p; }
  53                     else if (p.distance(p1)>EPSILON && p.distance(p2)>EPSILON) throw new Error("three points! " + p + " " + p1 + " " + p2);
  54                 }
  55             }
  56             if (p1!=null && p2!=null) {
  57                 //System.out.println("new segment: " + p1 + " " + p2);
  58                 segments.add(new Segment(p1, p2));
  59             }
  60         }
  61         Vec cen = new Vec(0,0,0);
  62         for(Segment s : segments)
  63             cen = cen.plus(s.p1.minus(Point.ORIGIN)).plus(s.p2.minus(Point.ORIGIN));
  64         Point centroid = Point.ORIGIN.plus(cen.times(1f/(2*segments.size())));
  65         //centroid = new Point(round(centroid.x), round(centroid.y), round(centroid.z));
  66         if (segments.size() >= 3)
  67         for(Segment s : segments) {
  68             System.out.println("newt! " + s.p1 + " " + centroid + " " + s.p2 + " " + plane.norm.times(-1));
  69             mesh.newT(s.p1, centroid, s.p2, plane.norm.times(-1), 0);
  70         }
  71         System.out.println("done");
  72         return null;
  73     }
  74
  75 }