1 package edu.berkeley.qfat.geom;
2 import javax.media.opengl.*;
4 import edu.berkeley.qfat.Mesh;
6 // FIXME: numerical stability issues galore
7 /** a planar, convex, possibly infinite/open polygon */
8 public final class Polygon {
10 public final Plane plane;
12 private final HalfSpace[] halfSpaces;
14 public Polygon(Plane plane) { this(plane, new HalfSpace[0]); }
16 public Polygon(Plane plane, HalfSpace[] halfSpaces) {
18 this.halfSpaces = halfSpaces;
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);
28 private static final float EPSILON = 0.00001f;
29 private static float round(float f) {
30 return Math.round(f*1000)/1000f;
32 public Triangle[] tesselate(Mesh mesh) {
33 // FIXME: check for closedness
34 // find a starting point
35 HashSet<Segment> segments = new HashSet<Segment>();
37 for(i=0; i<halfSpaces.length; i++) {
38 Point p1=null, p2=null;
39 for(int j=0; j<halfSpaces.length; j++) {
41 Point p = plane.intersect(halfSpaces[i], halfSpaces[j]);
42 if (p==null) continue;
44 //p = new Point(round(p.x), round(p.y), round(p.z));
46 for(int k=0; k<halfSpaces.length; k++) {
47 if (i==k || j==k) continue;
48 if (!halfSpaces[k].contains(p, 0.0001f)) { p = null; break; }
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);
56 if (p1!=null && p2!=null) {
57 //System.out.println("new segment: " + p1 + " " + p2);
58 segments.add(new Segment(p1, p2));
61 Vec cen = new Vec(0,0,0);
62 for(Segment s : segments)
63 cen = cen.plus(s.p1.minus(Point.ZERO)).plus(s.p2.minus(Point.ZERO));
64 Point centroid = Point.ZERO.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);
71 System.out.println("done");