1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
2 // Licensed under the GNU General Public License version 2 ("the License").
3 // You may not use this file except in compliance with the License.
5 package org.ibex.graphics;
7 import java.util.collections.*;
8 import org.ibex.util.*;
11 * An incremental, adaptive, constrained Delaunay Triangulation.
12 * @see Kallmann, Bieri, and Thalmann: Fully Dynamic Constrained Delaunay Triangulations
14 public final class Mesh {
18 private static final float epsilon = (float)0.001;
19 private static final boolean debug = false;
21 private Vector triangles = new Vector();
23 public static float B = (float)5.0;
24 public static float Q = (float)0.4;
26 public static Hashtable nexter = new Hashtable();
27 public static LinkedList next(Vertex v) {
28 LinkedList hs = (LinkedList)nexter.get(new Integer(v));
29 if (hs == null) nexter.put(new Integer(v), hs = new LinkedList());
33 // Vertices //////////////////////////////////////////////////////////////////////////////
35 public Vertex v(float x, float y) {
36 if (numvertices >= this.x.length-1) {
37 if (debug) Log.debug(Mesh.class, "expanding vertex arrays from " + this.x.length + " to " + this.x.length*2);
38 float[] newx = new float[this.x.length * 2];
39 float[] newy = new float[this.y.length * 2];
40 System.arraycopy(this.x, 0, newx, 0, this.x.length);
41 System.arraycopy(this.y, 0, newy, 0, this.y.length);
45 this.x[numvertices] = x;
46 this.y[numvertices] = y;
49 public int numvertices = 0;
50 public float x[] = new float[255];
51 public float y[] = new float[255];
52 public String s(Vertex v) { return "("+x(v)+","+y(v)+")"; }
53 public float x(Vertex v) { return x[v]; }
54 public float y(Vertex v) { return y[v]; }
56 public static final Vertex NULLVERTEX = -1;
58 public Vertex newVertex(float x, float y) {
59 Vertex ret = NULLVERTEX;
60 for(int k=0; k<numvertices; k++) {
62 if (distance(v,x,y)<epsilon) if (ret==NULLVERTEX || distance(v,x,y) < distance(ret,x,y)) ret = v;
64 if (ret != NULLVERTEX) return ret;
65 Vector vec = new Vector();
66 boolean interior = false;
69 if (numvertices<=2) return v;
70 if (numvertices==3) { newTriangle(0, 1, 2, "first three points"); return v; }
71 for(int i=0; i<triangles.size(); i++) {
72 Triangle t = (Triangle)triangles.elementAt(i);
78 vec.addElement(newTriangle(v, t.v1, t.v2, "vertexinsertion " + v));
79 vec.addElement(newTriangle(v, t.v3, t.v2, "vertexinsertion " + v));
80 vec.addElement(newTriangle(v, t.v1, t.v3, "vertexinsertion " + v));
81 //#repeat t23/t31/t12 v1/v2/v3 v2/v3/v1 v3/v1/v2
82 } else if (t.t23 != null && isect(t.v2, t.v3, v)) {
84 Vertex va = tt.opposingVertex(t);
87 vec.addElement(newTriangle(v, t.v1, t.v3, "vertexinsertion " + v));
88 vec.addElement(newTriangle(v, t.v1, t.v2, "vertexinsertion " + v));
89 vec.addElement(newTriangle(v, t.v3, va , "vertexinsertion " + v));
90 vec.addElement(newTriangle(v, t.v2, va , "vertexinsertion " + v));
100 for(int j=0; j<triangles.size(); j++) {
101 Triangle t = (Triangle)triangles.elementAt(j);
102 if (t.v1==v || t.v2==v || t.v3==v) continue;
103 //#repeat t12/t23/t31 v3/v1/v2 v2/v3/v1 v1/v2/v3
106 for(int k=0; k<triangles.size(); k++) {
107 Triangle tt = (Triangle)triangles.elementAt(k);
108 if (tt.intersectsSegment(v, t.v1)) { bad = true; break; }
109 if (tt.intersectsSegment(v, t.v2)) { bad = true; break; }
112 vec.addElement(newTriangle(v,t.v1,t.v2, "hull expansion"));
120 if (!good) throw new Error("couldn't figure out where to put " + s(v));
125 public void fixup(Vector vec, Vertex v) {
126 while(vec.size() > 0) {
127 Triangle t = (Triangle)vec.lastElement();
128 vec.setSize(vec.size() - 1);
129 if (t.deleted) continue;
130 //if (t.wind(t.nextVertex(v), t.prevVertex(v)) != 0) continue; // FIXME
131 Triangle to = t.opposingTriangle(v);
132 if (to==null) continue; //throw new Error("fixup invoked with a triangle which does not have me as a vertex");
133 if (to.deleted) throw new Error("v should not happen");
134 if (to.r < distance(v,to.ccx, to.ccy)) continue;
135 Vertex v2 = to.opposingVertex(t);
138 vec.addElement(newTriangle(v, t.nextVertex(v), v2, "fixup"));
139 vec.addElement(newTriangle(v, t.prevVertex(v), v2, "fixup"));
143 // Static //////////////////////////////////////////////////////////////////////////////
145 public Triangle newTriangle(Vertex v1, Vertex v2, Vertex v3, String source) {
146 if (v1==v2 || v2==v3 || v3==v1) throw new Error("identical vertices");
147 for(int i=0; i<triangles.size(); i++) {
148 Triangle t = (Triangle)triangles.elementAt(i);
149 if (t.v1==v1&&t.v2==v2&&t.v3==v3) return t;
150 if (t.v1==v1&&t.v2==v3&&t.v3==v2) return t;
151 if (t.v1==v2&&t.v2==v3&&t.v3==v1) return t;
152 if (t.v1==v2&&t.v2==v1&&t.v3==v3) return t;
153 if (t.v1==v3&&t.v2==v1&&t.v3==v2) return t;
154 if (t.v1==v3&&t.v2==v2&&t.v3==v1) return t;
156 Triangle t = new Triangle(source, v1, v2, v3, false, false);
157 if (debug) checktri();
161 public void checktri() {
162 for(int i=0; i<triangles.size(); i++) {
163 Triangle t = (Triangle)triangles.elementAt(i);
164 if (t.t12 != null && (t.t12.t12 != t && t.t12.t23 != t && t.t12.t31 != t)) throw new Error("t12");
165 if (t.t23 != null && (t.t23.t12 != t && t.t23.t23 != t && t.t23.t31 != t)) throw new Error("t23");
166 if (t.t31 != null && (t.t31.t12 != t && t.t31.t23 != t && t.t31.t31 != t)) throw new Error("t31");
167 for(int j=0; j<triangles.size(); j++) {
168 Triangle t2 = (Triangle)triangles.elementAt(j);
170 if (t.v1==t2.v1&&t.v2==t2.v2&&t.v3==t2.v3) throw new Error("poo");
171 if (t.v1==t2.v1&&t.v2==t2.v3&&t.v3==t2.v2) throw new Error("poo");
172 if (t.v1==t2.v2&&t.v2==t2.v3&&t.v3==t2.v1) throw new Error("poo");
173 if (t.v1==t2.v2&&t.v2==t2.v1&&t.v3==t2.v3) throw new Error("poo");
174 if (t.v1==t2.v3&&t.v2==t2.v1&&t.v3==t2.v2) throw new Error("poo");
175 if (t.v1==t2.v3&&t.v2==t2.v2&&t.v3==t2.v1) throw new Error("poo");
180 // Vertex //////////////////////////////////////////////////////////////////////////////
182 public boolean triangulate(Vertex vv, HashSet orphans, Vertex v, boolean first) {
184 HashSet left = new HashSet();
185 HashSet right = new HashSet();
186 for(Iterator it=orphans.iterator(); it.hasNext();) {
187 Vertex o = ((Integer)it.next()).intValue();
188 if (o==v||o==vv) continue;
189 if (side(vv, v, o) == -1) left.add(new Integer(o));
190 else if (side(vv, v, o) == 1) right.add(new Integer(o));
191 else throw new Error("impossible "+vv+" "+v + " " + o);
193 triangulate(vv, left, v, false);
194 triangulate(v, right, vv, false);
197 Vertex farthest = NULLVERTEX;
199 if (orphans.size()==0) return true;
200 Vertex o = ((Integer)orphans.iterator().next()).intValue();
201 if (orphans.size()==1) {
202 Triangle t = newTriangle(vv, v, o, "triangulate2 " + v + " " + vv);
203 if (((t.v1==vv && t.v2==v)||(t.v1==v && t.v2==vv)) && t.t12==null) return true;
204 if (((t.v3==vv && t.v2==v)||(t.v3==v && t.v2==vv)) && t.t23==null) return true;
205 if (((t.v1==vv && t.v3==v)||(t.v1==v && t.v3==vv)) && t.t31==null) return true;
209 Vertex best = NULLVERTEX;
210 OUTER: for(Iterator it=orphans.iterator(); it.hasNext();) {
211 o = ((Integer)it.next()).intValue();
213 Triangle t = new Triangle("temp", vv, v, o, true);
214 for(Iterator it2=orphans.iterator(); it2.hasNext();) {
215 Vertex z = ((Integer)it2.next()).intValue();
219 if (distance(z,t.ccx,t.ccy) < t.r || t.contains(z)) continue OUTER;
221 if (best==NULLVERTEX || new Triangle("temp",vv,v,best,true).area() > new Triangle("temp",vv,v,o,true).area())
224 if (best==NULLVERTEX) throw new Error("notgood, #orphans = " + orphans.size());
226 HashSet left = new HashSet();
227 HashSet right = new HashSet();
228 for(Iterator it2=orphans.iterator(); it2.hasNext();) {
229 Vertex x = ((Integer)it2.next()).intValue();
230 if (o==x||vv==x||v==x) continue;
231 int side_of_x = side(o,(x(vv)+x(v))/2,(y(vv)+y(v))/2,x);
232 int side_of_v = side(o,(x(vv)+x(v))/2,(y(vv)+y(v))/2,v);
233 int side_of_vv = side(o,(x(vv)+x(v))/2,(y(vv)+y(v))/2,vv);
234 if (side_of_x==side_of_vv && side_of_vv!=0) right.add(new Integer(x));
235 else if (side_of_x==side_of_v && side_of_v!=0) left.add(new Integer(x));
236 else throw new Error("impossible "+vv+" "+v + " " + o + " ==> " + x);
239 doit &= triangulate(o, left, v, false);
240 doit &= triangulate(o, right, vv, false);
242 Triangle t = newTriangle(v, vv, o,"triangulate 0/0");
243 if (((t.v1==vv && t.v2==v)||(t.v1==v && t.v2==vv)) && t.t12==null) return true;
244 if (((t.v3==vv && t.v2==v)||(t.v3==v && t.v2==vv)) && t.t23==null) return true;
245 if (((t.v1==vv && t.v3==v)||(t.v1==v && t.v3==vv)) && t.t31==null) return true;
251 public void force() {
253 boolean redo = false;
254 for(int k=0; k<numvertices; k++) {
261 public boolean force(Vertex vv) {
263 OUTER: for(Iterator it=next(vv).iterator(); it.hasNext();) {
264 Vertex v = ((Integer)it.next()).intValue();
265 for(int k=0; k<numvertices; k++) {
267 if (v2==vv||v2==v) continue;
268 //if (next(vv).contains(v2) || next(v2).contains(vv)) continue;
269 if (isect(v,vv,v2)) {
270 if (debug) Log.debug(Mesh.class,"breaking line " + vv+"-"+v + " at vertex " + v2);
271 next(vv).remove(new Integer(v));
272 next(vv).add(new Integer(v2));
273 next(v2).add(new Integer(v));
278 boolean good = false;
279 for (int i=0; i<triangles.size(); i++)
280 if (((Triangle)triangles.elementAt(i)).hasEdge(vv,v)) { good = true; break; }
282 HashSet orphans = new HashSet();
283 for (int i=0; i<triangles.size(); i++) {
284 Triangle t = ((Triangle)triangles.elementAt(i));
285 if (t.deleted) continue;
286 if (t.intersectsSegment(vv, v)) {
287 if (debug) Log.debug(Mesh.class,"removing triangle " + t + " because it intersects segment " + vv+"-"+v);
288 Vector vec = new Vector();
289 orphans.add(new Integer(t.v1));
290 orphans.add(new Integer(t.v2));
291 orphans.add(new Integer(t.v3));
292 orphans.remove(new Integer(v));
293 orphans.remove(new Integer(vv));
299 orphans.remove(new Integer(vv));
300 orphans.remove(new Integer(v));
301 triangulate(vv, orphans, v, true);
307 public void makeNonDegenerate() {
309 boolean redo = false;
310 for(int k=0; k<numvertices; k++) {
311 Vector vec = new Vector();
313 redo |= makeNonDegenerate(vec, vx);
318 public boolean makeNonDegenerate(Vector vec, Vertex v1) {
319 for(int i2 = 0; i2<next(v1).size(); i2++) {
320 Vertex v2 = ((Integer)next(v1).get(i2)).intValue();
321 for(int i3 = 0; i3<numvertices; i3++) {
323 for(int i4=0; i4<next(v3).size(); i4++) {
324 Vertex v4 = ((Integer)next(v3).get(i4)).intValue();
325 if (v1==v3||v1==v4||v2==v3||v2==v4) continue;
326 if (isect(v1,v2,v3,v4)) {
327 float a1 = y(v2)-y(v1);
328 float a2 = y(v4)-y(v3);
329 float b1 = x(v1)-x(v2);
330 float b2 = x(v3)-x(v4);
331 float c1 = -1 * (a1*x(v1)+b1*y(v1));
332 float c2 = -1 * (a2*x(v3)+b2*y(v3));
335 // a2x-(a1x+c1)(b2/b1)+c2=0
336 // a2b1x-b2(a1x+c1)+b1c2=0
337 // a2b1x-a1b2x-b2c1+b1c2=0
338 // x(a2b1-a1b2)-b2c1+b1c2=0
339 // x(a2b1-a1b2)=b2c1-b1c2
340 // x=(b2c1-b1c2)/(a2b1-a1b2)
341 float xq = (b2*c1-c2*b1)/(b1*a2-b2*a1);
342 Vertex v0 = newVertex(xq, -1 * (a1*xq+c1) / b1);
343 //if (v0==v1||v0==v2||v0==v3||v0==v4) continue;
344 if (debug) Log.debug(this,"inserting new vertex " + v0+" between " + v1+"-"+v2 +" and "+ v3+"-"+v4);
345 next(v1).remove(new Integer(v2));
346 next(v1).add(new Integer(v0));
347 next(v0).add(new Integer(v2));
348 next(v3).remove(new Integer(v4));
349 next(v3).add(new Integer(v0));
350 next(v0).add(new Integer(v4));
359 // Triangle //////////////////////////////////////////////////////////////////////////////
361 private final class Triangle {
362 Triangle t12=null, t23=null, t31=null;
363 final Vertex v1, v2, v3;
365 boolean deleted = false;
366 boolean painted = false;
367 boolean special = false;
369 final float ccx, ccy, r;
371 public boolean hasEdge(Vertex a, Vertex b) { return a!=b && (a==v1||a==v2||a==v3) && (b==v1||b==v2||b==v3); }
372 public Vertex opposingVertex(Triangle t) { return t12==t ? v3 : t23==t ? v1 : t31==t ? v2 : NULLVERTEX; }
373 public Triangle opposingTriangle(Vertex v) { return v1==v ? t23 : v2==v ? t31 : v3==v ? t12 : null; }
374 public Vertex nextVertex(Vertex v) { return v1==v ? v2 : v2==v ? v3 : v3==v ? v1 : NULLVERTEX; }
375 public Vertex prevVertex(Vertex v) { return v1==v ? v3 : v2==v ? v1 : v3==v ? v2 : NULLVERTEX; }
376 public String toString() { return "<<"+v1+""+v2+""+v3+">>"; }
377 public boolean intersectsSegment(Vertex a, Vertex b) { return isect(v1,v2,a,b) || isect(v3,v2,a,b) || isect(v1,v3,a,b); }
378 public float area() {
379 float a = distance(v1,v2);
380 float b = distance(v2,v3);
381 float c = distance(v3,v1);
383 return (float)Math.sqrt(s*(s-a)*(s-b)*(s-c));
386 public boolean checkSkinny() {
387 if (!(r / Math.min(Math.min(distance(v1,v2), distance(v2,v3)), distance(v3,v1)) > B)) return false;
388 if (debug) Log.debug(this,"skinny triangle " + this);
389 for (Vertex v=0; v<numvertices; v++) {
390 for (Iterator nit = next(v).iterator(); nit.hasNext();) {
391 Vertex v2 = ((Integer)nit.next()).intValue();
392 float midx = (x(v)+x(v2))/2;
393 float midy = (y(v)+y(v2))/2;
394 if (distance(midx,midy,ccx,ccy) <= distance(v,midx,midy)) {
395 if (debug) Log.debug(this," but splitting it would encroach on a segment");
404 public void fill(PixelBuffer buf, Affine a, int color, boolean evenOdd, int count, boolean strokeOnly) {
406 if (deleted) throw new Error("gargh!");
409 buf.fillTriangle((int)a.multiply_px((float)x(v1), (float)y(v1)),
410 (int)a.multiply_py((float)x(v1), (float)y(v1)),
411 (int)a.multiply_px((float)x(v2), (float)y(v2)),
412 (int)a.multiply_py((float)x(v2), (float)y(v2)),
413 (int)a.multiply_px((float)x(v3), (float)y(v3)),
414 (int)a.multiply_py((float)x(v3), (float)y(v3)),
416 } else if ((evenOdd && count%2!=0) || (!evenOdd && count!=0)) {
417 buf.fillTriangle((int)a.multiply_px((float)x(v1), (float)y(v1)),
418 (int)a.multiply_py((float)x(v1), (float)y(v1)),
419 (int)a.multiply_px((float)x(v2), (float)y(v2)),
420 (int)a.multiply_py((float)x(v2), (float)y(v2)),
421 (int)a.multiply_px((float)x(v3), (float)y(v3)),
422 (int)a.multiply_py((float)x(v3), (float)y(v3)),
426 buf.fillTriangle((int)a.multiply_px((float)x(v1), (float)y(v1)),
427 (int)a.multiply_py((float)x(v1), (float)y(v1)),
428 (int)a.multiply_px((float)x(v2), (float)y(v2)),
429 (int)a.multiply_py((float)x(v2), (float)y(v2)),
430 (int)a.multiply_px((float)x(v3), (float)y(v3)),
431 (int)a.multiply_py((float)x(v3), (float)y(v3)),
432 0xff000000 | ((color & 0x00ffffff) >> 8));
436 //#repeat t12/t23/t31 v1/v2/v3 v2/v3/v1
437 if (t12 != null && !t12.painted) {
438 t12.fill(buf, a, color, evenOdd, count + wind(v1, v2), strokeOnly);
440 drawLine(buf, (x(v1)*2+x(v2))/3, (y(v1)*2+y(v2))/3, (x(v1)+2*x(v2))/3, (y(v1)+2*y(v2))/3, a,
441 wind(v2,v1)==0?0xff000000:0xff0000ff);
445 public int wind(Vertex a, Vertex b) {
446 if (next(a).contains(new Integer(b)) && next(b).contains(new Integer(a))) return 0;
447 if (y(a) < y(b) || (y(a)==y(b) && x(a)<x(b))) return wind(b, a);
448 if (next(a).contains(new Integer(b))) return 1;
449 if (next(b).contains(new Integer(a))) return -1;
452 public void clear() {
453 if (!painted) return;
455 if (t12 != null) t12.clear();
456 if (t23 != null) t23.clear();
457 if (t31 != null) t31.clear();
459 public Triangle(String source, Vertex v1, Vertex v2, Vertex v3) { this(source, v1, v2, v3, false, false); }
460 public Triangle(String source, Vertex v1, Vertex v2, Vertex v3, boolean fake) { this(source, v1,v2,v3,fake,false); }
461 public Triangle(String source, Vertex v1, Vertex v2, Vertex v3, boolean fake, boolean ignoreProblems) {
462 this.source = source;
464 for(int i=0; i<3; i++) {
465 a=(y(v2)-y(v3))*(x(v2)-x(v1))-(y(v2)-y(v1))*(x(v2)-x(v3));
467 Vertex t = v2; v2=v3; v3=v1; v1 = t;
469 if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3);
470 this.v1 = v1; this.v2 = v2; this.v3 = v3;
471 float a1=(x(v1)+x(v2))*(x(v2)-x(v1))+(y(v2)-y(v1))*(y(v1)+y(v2));
472 float a2=(x(v2)+x(v3))*(x(v2)-x(v3))+(y(v2)-y(v3))*(y(v2)+y(v3));
473 ccx=(a1*(y(v2)-y(v3))-a2*(y(v2)-y(v1)))/a/2;
474 ccy=(a2*(x(v2)-x(v1))-a1*(x(v2)-x(v3)))/a/2;
475 r = distance(v1,ccx, ccy);
477 for(int i=0; i<triangles.size(); i++) {
478 Triangle t = (Triangle)triangles.elementAt(i);
479 if ((t.v1==v1&&t.v2==v2)||(t.v1==v2&&t.v2==v1)) { if (t.t12!=null) throw new Error(); t.t12=this; t12=t; }
480 if ((t.v1==v2&&t.v2==v3)||(t.v1==v3&&t.v2==v2)) { if (t.t12!=null) throw new Error(); t.t12=this; t23=t; }
481 if ((t.v1==v3&&t.v2==v1)||(t.v1==v1&&t.v2==v3)) { if (t.t12!=null) throw new Error(); t.t12=this; t31=t; }
482 if ((t.v2==v1&&t.v3==v2)||(t.v2==v2&&t.v3==v1)) { if (t.t23!=null) throw new Error(); t.t23=this; t12=t; }
483 if ((t.v2==v2&&t.v3==v3)||(t.v2==v3&&t.v3==v2)) { if (t.t23!=null) throw new Error(); t.t23=this; t23=t; }
484 if ((t.v2==v3&&t.v3==v1)||(t.v2==v1&&t.v3==v3)) { if (t.t23!=null) throw new Error(); t.t23=this; t31=t; }
485 if ((t.v3==v1&&t.v1==v2)||(t.v3==v2&&t.v1==v1)) { if (t.t31!=null) throw new Error(); t.t31=this; t12=t; }
486 if ((t.v3==v2&&t.v1==v3)||(t.v3==v3&&t.v1==v2)) { if (t.t31!=null) throw new Error(); t.t31=this; t23=t; }
487 if ((t.v3==v3&&t.v1==v1)||(t.v3==v1&&t.v1==v3)) { if (t.t31!=null) throw new Error(); t.t31=this; t31=t; }
491 public void delete() {
494 triangles.remove(this);
495 if (t12 != null) { if (t12.t12==this) t12.t12=null; if (t12.t23==this) t12.t23=null; if (t12.t31==this) t12.t31=null; }
496 if (t23 != null) { if (t23.t12==this) t23.t12=null; if (t23.t23==this) t23.t23=null; if (t23.t31==this) t23.t31=null; }
497 if (t31 != null) { if (t31.t12==this) t31.t12=null; if (t31.t23==this) t31.t23=null; if (t31.t31==this) t31.t31=null; }
499 public boolean contains(Vertex v) {
502 if (v==v1) return false;
503 if (v==v2) return false;
504 if (v==v3) return false;
505 if (isect(v1,v2,v)) return false;
506 if (isect(v2,v3,v)) return false;
507 if (isect(v3,v1,v)) return false;
508 return (side(v1,v2,x,y)==side(v1,v2,v3)) && (side(v3,v2,x,y)==side(v3,v2,v1)) && (side(v1,v3,x,y)==side(v1,v3,v2));
512 // Constructor //////////////////////////////////////////////////////////////////////////////
514 public Mesh(Polygon p) {
516 triangles.setSize(0);
517 for(int i=0; i<p.numcontours-1; i++) {
518 Vertex last = NULLVERTEX, first = NULLVERTEX;
519 boolean good = false;
520 for(int j=p.contours[i]; j<p.contours[i+1]; j++) {
521 Vertex v = newVertex(p.x[j], p.y[j]);
522 if (v==last) continue;
523 if (v==first) continue;
524 if (last == NULLVERTEX) { last = v; continue; }
525 if (first == NULLVERTEX) { first = v; continue; }
529 if (debug) Log.debug(this,"contour " + i + " is " + (good?"good":"bad"));
531 last = NULLVERTEX; first = NULLVERTEX;
532 for(int j=p.contours[i]; j<p.contours[i+1]; j++) {
533 Vertex v = newVertex(p.x[j], p.y[j]);
534 if (v==last) continue;
535 if (first==NULLVERTEX) first=v;
536 if (last != NULLVERTEX) next(last).add(new Integer(v));
541 if (last!=first) next(last).add(new Integer(first));
549 for(int k=0; k<triangles.size(); k++) {
550 Triangle t = (Triangle)triangles.elementAt(k);
551 redo |= t.checkSkinny();
555 System.out.println("I now have " + numvertices + " vertices");
560 // Drawing //////////////////////////////////////////////////////////////////////////////
562 private void drawLine(PixelBuffer buf, float x1, float y1, float x2, float y2, Affine a, int color) {
563 buf.drawLine((int)a.multiply_px(x1, y1), (int)a.multiply_py(x1, y1),
564 (int)a.multiply_px(x2, y2), (int)a.multiply_py(x2, y2),
567 public void fill(PixelBuffer buf, Affine a, int color, boolean evenOdd, boolean strokeOnly) {
568 for (int i=0; i<triangles.size(); i++) ((Triangle)triangles.elementAt(i)).clear();
569 ((Triangle)triangles.elementAt(0)).fill(buf, a, color, evenOdd, 1, strokeOnly);
572 public void stroke(PixelBuffer buf, Affine a, int color) {
574 for (int i=0; i<numvertices; i++) {
576 for(Iterator it = next(v).iterator(); it.hasNext();) {
577 Vertex v2 = ((Integer)it.next()).intValue();
578 drawLine(buf, x(v), y(v), x(v2), y(v2), a, 0xffff0000);
581 for (int i=0; i<triangles.size(); i++) {
582 Triangle t = ((Triangle)triangles.elementAt(i));
586 if (debug||t.wind(v1,v2)!=0) drawLine(buf,x(v1),y(v1),x(v2),y(v2),a,(debug && t.wind(v1,v2)!=0) ?0xffffffff:color);
587 if (debug||t.wind(v3,v2)!=0) drawLine(buf,x(v3),y(v3),x(v2),y(v2),a,(debug && t.wind(v3,v2)!=0) ?0xffffffff:color);
588 if (debug||t.wind(v1,v3)!=0) drawLine(buf,x(v1),y(v1),x(v3),y(v3),a,(debug && t.wind(v1,v3)!=0) ?0xffffffff:color);
592 // Geometric Utility Functions //////////////////////////////////////////////////////////////////////////////
594 public float distance(Vertex v1, Vertex v2) { return distance(x(v1), y(v1), x(v2), y(v2)); }
595 public float distance(Vertex v1, float x, float y) { return distance(x(v1),y(v1),x,y); }
596 public float distance(float x1,float y1,float x2,float y2) {return (float)Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
597 public int side(Vertex v1, Vertex v2, Vertex v3) { return side(v1, v2, x(v3), y(v3)); }
598 public int side(Vertex v1, Vertex v2, float x, float y) { return side(v1, x(v2), y(v2), x, y); }
599 public int side(Vertex v1, float x, float y, Vertex v3) { return side(v1, x, y, x(v3), y(v3)); }
600 public int side(Vertex v1, float x, float y, float x2, float y2) {
601 float a = y-y(v1), b = x(v1)-x, c = -1 * (a*x(v1)+b*y(v1));
602 return (- (a*x2+c)/b > y2) ? -1 : (- (a*x2+c)/b < y2) ? 1 : 0;
605 public boolean isect(Vertex v1, Vertex v2, Vertex v3, Vertex v4) {
606 if (v1==v3 || v1==v4 || v2==v3 || v2==v4) return false;
607 float a = side(v1,v2,v3);
608 float b = side(v1,v2,v4);
609 float c = side(v3,v4,v1);
610 float d = side(v3,v4,v2);
611 return a!=b && c!=d && a!=0 && b!=0 && c!=0 && d!=0;
614 public boolean isect(Vertex v1, Vertex v2, Vertex v) {
617 x(v) - Math.max(x(v1),x(v2)) < 0 &&
618 x(v) - Math.min(x(v1),x(v2)) > 0 &&
619 y(v) - Math.max(y(v1),y(v2)) < 0 &&
620 y(v) - Math.min(y(v1),y(v2)) > 0;