Bug 12212 fixed: Export a polyline in 2D broke it into several segments
[scilab.git] / scilab / modules / scirenderer / src / org / scilab / forge / scirenderer / implementation / g2d / motor / Triangle.java
1 /*
2  * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
3  * Copyright (C) 2012 - Scilab Enterprises - Calixte Denizet
4  *
5  * This file must be used under the terms of the CeCILL.
6  * This source file is licensed as described in the file COPYING, which
7  * you should have received as part of this distribution.  The terms
8  * are also available at
9  * http://www.cecill.info/licences/Licence_CeCILL_V2.1-en.txt
10  */
11
12 package org.scilab.forge.scirenderer.implementation.g2d.motor;
13
14 import java.awt.BasicStroke;
15 import java.awt.Color;
16 import java.awt.Graphics2D;
17 import java.awt.RenderingHints;
18 import java.awt.Shape;
19 import java.awt.Stroke;
20 import java.awt.geom.Area;
21 import java.awt.geom.Path2D;
22 import java.awt.image.BufferedImage;
23 import java.util.ArrayList;
24 import java.util.List;
25 import java.util.Set;
26 import java.util.TreeSet;
27
28 import org.scilab.forge.scirenderer.texture.Texture;
29 import org.scilab.forge.scirenderer.tranformations.Vector3d;
30 import org.scilab.forge.scirenderer.tranformations.Vector4d;
31
32 /**
33  * @author Calixte DENIZET
34  */
35 public class Triangle extends ConvexObject {
36
37     private static final Color[] COLORS = new Color[] {Color.BLACK, Color.BLACK, Color.BLACK};
38     private static final Stroke stroke = new BasicStroke(1f, BasicStroke.CAP_BUTT, BasicStroke.JOIN_BEVEL);
39     private static final Stroke EMPTYSTROKE = new BasicStroke(0f, BasicStroke.CAP_BUTT, BasicStroke.JOIN_BEVEL);
40
41     private SpritedRectangle sprite;
42     private BufferedImage image;
43     private Vector3d[] textureCoords;
44     private Texture.Filter filter;
45
46     protected List<Segment> segments;
47
48     public Triangle(Vector3d[] vertices, Color[] colors, Vector3d normal) throws InvalidPolygonException {
49         super(vertices, colors);
50         if (vertices.length != 3) {
51             throw new InvalidPolygonException("Invalid triangle: must have 3 vertices.");
52         }
53     }
54
55     public Triangle(Vector3d[] vertices, Color[] colors) throws InvalidPolygonException {
56         this(vertices, colors, null);
57     }
58
59     public Triangle(Vector3d[] vertices, Vector3d[] textureCoords, BufferedImage image, Texture.Filter filter) throws InvalidPolygonException {
60         this(vertices, COLORS, null);
61         this.textureCoords = textureCoords;
62         this.image = image;
63         this.filter = filter;
64     }
65
66     @Override
67     public int isBehind(ConvexObject o) {
68         if (o instanceof Segment && isSegmentAcross((Segment) o)) {
69             return -1;
70         }
71
72         return super.isBehind(o);
73     }
74
75     public boolean isIn2D() {
76         return vertices[0].getZ() == 0 && vertices[1].getZ() == 0 && vertices[2].getZ() == 0;
77     }
78
79     public boolean addSegment(Segment s) {
80         if (isSegmentInside(s)) {
81             if (segments == null) {
82                 segments = new ArrayList<Segment>(3);
83             }
84             if (segments.contains(s)) {
85                 segments.remove(s);
86                 s.removeConvexObject(this);
87             }
88             segments.add(s);
89             s.addConvexObject(this);
90
91             return true;
92         }
93
94         return false;
95     }
96
97     public boolean pointOnVertices(Vector3d p) {
98         return p.equals(vertices[0]) || p.equals(vertices[1]) || p.equals(vertices[2]);
99     }
100
101     public void removeSegment(Segment s) {
102         if (segments != null) {
103             segments.remove(s);
104             s.removeConvexObject(this);
105         }
106     }
107
108     public void replaceSegment(Segment s, List<Segment> segs) {
109         segments.remove(s);
110         //s.removeConvexObject(this);
111         for (Segment ss : segs) {
112             if (segments.contains(ss)) {
113                 segments.remove(ss);
114                 ss.removeConvexObject(this);
115             }
116             segments.add(ss);
117             ss.addConvexObject(this);
118         }
119     }
120
121     @Override
122     public List<ConvexObject> breakObject(ConvexObject o) {
123         if (o instanceof Triangle) {
124             return breakObject((Triangle) o);
125         } else if (o instanceof Segment) {
126             return breakObject((Segment) o);
127         } else if (o instanceof SpritedRectangle) {
128             return ((SpritedRectangle) o).breakObject(this);
129         }
130
131         return null;
132     }
133
134     public List<ConvexObject> breakObject(Triangle o) {
135         Vector3d n = Vector3d.product(this.v0v1, o.v0v1);
136         n = n.times(1 / n.getNorm2());
137         Vector3d u = Vector3d.product(o.v0v1, n);
138         Vector3d v = Vector3d.product(n, this.v0v1);
139         Vector3d p = Vector3d.getBarycenter(u, v, this.v0v1.scalar(this.vertices[0]), o.v0v1.scalar(o.vertices[0]));
140
141         List<ConvexObject> list1 = breakTriangleOnLine(o, p, this.v0v1);
142         List<ConvexObject> list2 = breakTriangleOnLine(this, p, o.v0v1);
143
144         list1.addAll(list2);
145
146         return list1;
147     }
148
149     public List<ConvexObject> breakObject(Segment o) {
150         double c = this.getSegmentIntersection(o);
151         if (Double.isNaN(c)) {
152             return null;
153         }
154
155         List<ConvexObject> list = new ArrayList<ConvexObject>(5);
156         Vector3d p = Vector3d.getBarycenter(o.vertices[0], o.vertices[1], c, 1 - c);
157         Color cc = getColorsBarycenter(o.colors[0], o.colors[1], c, 1 - c);
158
159         try {
160             list.add(new Segment(new Vector3d[] {o.vertices[0], p}, new Color[] {o.colors[0], cc}, o.stroke));
161             list.add(new Segment(new Vector3d[] {p, o.vertices[1]}, new Color[] {cc, o.colors[1]}, o.stroke));
162         } catch (InvalidPolygonException e) { }
163
164         List<ConvexObject> list1 = breakTriangleOnLine(this, p, Vector3d.product(v0v1, vertices[0].minus(p)));
165         list.addAll(list1);
166
167         return list;
168     }
169
170     protected void setSprite(SpritedRectangle sprite) {
171         this.sprite = sprite;
172     }
173
174     protected SpritedRectangle getSprite() {
175         return sprite;
176     }
177
178     @Override
179     public void draw(Graphics2D g2d) {
180         if (sprite != null) {
181             Shape oldClip = g2d.getClip();
182             Path2D contour = getProjectedContour();
183             Area area = new Area(contour);
184             // Trick to paint the triangle and its outline
185             area.add(new Area(stroke.createStrokedShape(contour)));
186             g2d.clip(area);//getProjectedContour());
187             sprite.draw(g2d);
188             g2d.setClip(oldClip);
189         } else if (image != null) {
190             Object key = filter == Texture.Filter.LINEAR ? RenderingHints.VALUE_INTERPOLATION_BILINEAR : RenderingHints.VALUE_INTERPOLATION_NEAREST_NEIGHBOR;
191             DrawTools.drawTriangleTexture(g2d, image, new double[] {textureCoords[0].getX(), textureCoords[1].getX(), textureCoords[2].getX()}, new double[] {textureCoords[0].getY(), textureCoords[1].getY(), textureCoords[2].getY()}, new double[] {vertices[0].getX(), vertices[1].getX(), vertices[2].getX()}, new double[] {vertices[0].getY(), vertices[1].getY(), vertices[2].getY()}, key);
192         } else if (colors[0].equals(colors[1]) && colors[1].equals(colors[2])) {
193             Path2D contour = getProjectedContour();
194             Area area = new Area(contour);
195             // Trick to paint the triangle and its outline
196             // TODO: the newly created Area contains in fact two areas
197             // it should be better to have one area where its border
198             // is the external outline of the contour...
199             // (it would reduce eps/ps/pdf/svg file size)
200             area.add(new Area(stroke.createStrokedShape(contour)));
201             g2d.setStroke(EMPTYSTROKE);
202             g2d.setColor(colors[0]);
203             g2d.fill(area);
204         } else {
205             DrawTools.fillGouraud(g2d, this);
206         }
207
208         if (segments != null) {
209             for (Segment s : segments) {
210                 s.removeConvexObject(this);
211                 s.draw(g2d);
212             }
213         }
214
215         drawAreas(g2d);
216     }
217
218     @Override
219     public List<ConvexObject> breakObject(Vector4d v) {
220         double[] vv = v.getData();
221         Vector3d np = new Vector3d(vv);
222         int ret = isBehind(np, vv[3]);
223         if (ret == 1) {
224             List<ConvexObject> list = new ArrayList<ConvexObject>(1);
225             list.add(this);
226             return list;
227         } else if (ret == -1) {
228             return null;
229         }
230
231         Vector3d n = Vector3d.product(this.v0v1, np);
232         n = n.times(1 / n.getNorm2());
233         Vector3d u = Vector3d.product(np, n);
234         Vector3d w = Vector3d.product(n, this.v0v1);
235         Vector3d p = Vector3d.getBarycenter(u, w, this.v0v1.scalar(this.vertices[0]), -vv[3]);
236
237         List<ConvexObject> list1 = breakTriangleOnLine(this, p, np);
238         List<ConvexObject> list = new ArrayList<ConvexObject>(3);
239         for (ConvexObject o : list1) {
240             if (o.isBehind(np, vv[3]) == 1) {
241                 list.add(o);
242             }
243         }
244
245         return list;
246     }
247
248     protected boolean isPointInside(final Vector3d v) {
249         return isPointInside(v, true);
250     }
251
252     protected boolean isPointInside(final Vector3d v, final boolean checkCoplanarity) {
253         Vector3d v2 = v.minus(vertices[0]);
254         if (checkCoplanarity && !isNull(v2.scalar(v0v1))) {
255             return false;
256         }
257
258         Vector3d v0v1v2 = Vector3d.product(v0v1, v2);
259         double a = -v0v1v2.scalar(v1);
260         if (a < 0 || isNull(a)) {
261             return false;
262         }
263
264         double b = v0v1v2.scalar(v0);
265         if (b < 0 || isNull(b)) {
266             return false;
267         }
268
269         return a + b < nv0v1 || isEqual(a + b, nv0v1);
270     }
271
272     protected boolean isCoplanar(final Segment s) {
273         double sc = vertices[0].scalar(v0v1);
274         return isEqual(sc, s.vertices[0].scalar(v0v1)) && isEqual(sc, s.vertices[1].scalar(v0v1));
275     }
276
277     protected boolean isCoplanar(final Triangle t) {
278         double sc = vertices[0].scalar(v0v1);
279         return isEqual(sc, t.vertices[0].scalar(v0v1)) && isEqual(sc, t.vertices[1].scalar(v0v1)) && isEqual(sc, t.vertices[2].scalar(v0v1));
280     }
281
282     protected boolean isSegmentAcross(final Segment s) {
283         if (!isCoplanar(s)) {
284             // the segment and the triangle are not coplanar
285             return false;
286         }
287
288         return check2DTrueIntersection(s);
289     }
290
291     protected boolean isSegmentInside(final Segment s) {
292         if (!isCoplanar(s)) {
293             // the segment and the triangle are not coplanar
294             return false;
295         }
296
297         // Since there is a good probability that a segment is triangle border we check that
298         if ((s.vertices[0].equals(vertices[0]) || s.vertices[0].equals(vertices[1]) || s.vertices[0].equals(vertices[2]))
299                 && (s.vertices[1].equals(vertices[0]) || s.vertices[1].equals(vertices[1]) || s.vertices[1].equals(vertices[2]))) {
300             return true;
301         }
302
303         return isPointInside(s.vertices[0], false) || isPointInside(s.vertices[1], false) || check2DIntersection(s);
304     }
305
306     protected boolean isSegmentIntersects(final Segment s) {
307         Vector3d v3 = s.vertices[0].minus(vertices[0]);
308         Vector3d v4 = s.vertices[1].minus(vertices[0]);
309         double c = v3.scalar(v0v1);
310
311         if (Math.signum(c) == Math.signum(v4.scalar(v0v1))) {
312             return false;
313         }
314
315         Vector3d v2 = s.vertices[0].minus(s.vertices[1]);
316         Vector3d v1v2 = Vector3d.product(v1, v2);
317         double a = v3.scalar(v1v2);
318         double b = Vector3d.det(v3, v2, v0);
319         double detv0v1v2 = v0.scalar(v1v2);
320         double sign = Math.signum(detv0v1v2);
321
322         return Math.signum(a) == sign && Math.signum(b) == sign && Math.signum(c) == sign && a + b <= detv0v1v2 && c <= detv0v1v2;
323     }
324
325     protected double getSegmentIntersection(final Segment s) {
326         Vector3d v = s.vertices[1].minus(vertices[0]);
327         double c = v.scalar(v0v1) / s.v0.scalar(v0v1);
328
329         if (isNegativeOrNull(c) || isGreaterOrEqual(c, 1)) {
330             return Double.NaN;
331         }
332
333         Vector3d p = Vector3d.getBarycenter(s.vertices[0], s.vertices[1], c, 1 - c);
334         if (isPointInside(p, false)) {
335             return c;
336         }
337
338         return Double.NaN;
339     }
340
341     protected static List<ConvexObject> breakSegmentOnTriangle(final Triangle t, final Segment s) {
342         double c = t.getSegmentIntersection(s);
343         if (Double.isNaN(c)) {
344             return null;
345         }
346
347         List<ConvexObject> list = new ArrayList<ConvexObject>(2);
348         Vector3d p = Vector3d.getBarycenter(s.vertices[0], s.vertices[1], c, 1 - c);
349         Color cc = getColorsBarycenter(s.colors[0], s.colors[1], c, 1 - c);
350
351         try {
352             list.add(new Segment(new Vector3d[] {s.vertices[0], p}, new Color[] {s.colors[0], cc}, s.stroke));
353             list.add(new Segment(new Vector3d[] {p, s.vertices[1]}, new Color[] {cc, s.colors[1]}, s.stroke));
354         } catch (InvalidPolygonException e) { }
355
356
357         return list;
358     }
359
360     /**
361      * Break a triangle according to its intersection with a line containing p in the plane of the triangle and orthogonal to n
362      * The triangle and the line are supposed to be coplanar.
363      * @param t the triangle to break
364      * @param p a point of the line
365      * @param n a vector
366      * @return a list of triangles
367      */
368     protected static List<ConvexObject> breakTriangleOnLine(Triangle t, Vector3d p, Vector3d n) {
369         // aP0+(1-a)P1
370         double a = t.vertices[1].minus(p).scalar(n) / t.v0.scalar(n);
371         // bP0+(1-b)P2
372         double b = t.vertices[2].minus(p).scalar(n) / t.v1.scalar(n);
373         // cP1+(1-c)P2
374         Vector3d v2 = t.vertices[2].minus(t.vertices[1]);
375         double c = t.vertices[2].minus(p).scalar(n) / v2.scalar(n);
376
377         List<ConvexObject> list = new ArrayList<ConvexObject>(3);
378         int i = -1;
379         int j = -1;
380         int k = -1;
381         double weight = -1;
382         if (isNull(a)) {
383             // We are on P1
384             i = 1;
385             j = 2;
386             k = 0;
387             weight = b;
388         }
389
390         if (isNull(a - 1)) {
391             // We are on P0
392             if (weight != -1) {
393                 list.add(t);
394                 return list;
395             } else {
396                 i = 0;
397                 j = 1;
398                 k = 2;
399                 weight = c;
400             }
401         }
402
403         if (isNull(b)) {
404             // We are on P2
405             if (weight != -1) {
406                 list.add(t);
407                 return list;
408             } else {
409                 i = 2;
410                 j = 0;
411                 k = 1;
412                 weight = a;
413             }
414         }
415
416         if (i != -1) {
417             if (weight >= 0 && weight <= 1) {
418                 // We break into two triangles
419                 Vector3d vb = Vector3d.getBarycenter(t.vertices[j], t.vertices[k], weight, 1 - weight);
420                 Color cb = getColorsBarycenter(t.colors[j], t.colors[k], weight, 1 - weight);
421                 Vector3d[] vertices1 = new Vector3d[] {t.vertices[i], t.vertices[j], vb};
422                 Vector3d[] vertices2 = new Vector3d[] {t.vertices[i], vb, t.vertices[k]};
423                 Color[] colors1 = new Color[] {t.colors[i], t.colors[j], cb};
424                 Color[] colors2 = new Color[] {t.colors[i], cb, t.colors[k]};
425
426                 Vector3d[] tvertices1 = null;
427                 Vector3d[] tvertices2 = null;
428                 if (t.textureCoords != null) {
429                     Vector3d tvb = Vector3d.getBarycenter(t.textureCoords[j], t.textureCoords[k], weight, 1 - weight);
430                     tvertices1 = new Vector3d[] {t.textureCoords[i], t.textureCoords[j], tvb};
431                     tvertices2 = new Vector3d[] {t.textureCoords[i], tvb, t.textureCoords[k]};
432                 }
433
434                 try {
435                     Triangle t1 = new Triangle(vertices1, colors1, null);
436                     t1.setSprite(t.getSprite());
437                     list.add(t1);
438                     Triangle t2 = new Triangle(vertices2, colors2, null);
439                     t2.setSprite(t.getSprite());
440                     list.add(t2);
441                     if (t.textureCoords != null) {
442                         t1.textureCoords = tvertices1;
443                         t2.textureCoords = tvertices2;
444                         t1.image = t2.image = t.image;
445                         t1.filter = t2.filter = t.filter;
446                     }
447                 } catch (InvalidPolygonException e) { }
448
449                 addSegments(list, t, p, Vector3d.product(t.v0v1, n), n);
450
451                 return list;
452             } else {
453                 list.add(t);
454                 return list;
455             }
456         }
457
458         Color cu, cv;
459         Vector3d u, v;
460         Vector3d tu = null, tv = null;
461         // t has not been broken, so continue...
462         if (a < 0 || a > 1) {
463             i = 2;
464             j = 0;
465             k = 1;
466             u = Vector3d.getBarycenter(t.vertices[1], t.vertices[2], c, 1 - c);
467             v = Vector3d.getBarycenter(t.vertices[0], t.vertices[2], b, 1 - b);
468             cu = getColorsBarycenter(t.colors[1], t.colors[2], c, 1 - c);
469             cv = getColorsBarycenter(t.colors[0], t.colors[2], b, 1 - b);
470             if (t.textureCoords != null) {
471                 tu = Vector3d.getBarycenter(t.textureCoords[1], t.textureCoords[2], c, 1 - c);
472                 tv = Vector3d.getBarycenter(t.textureCoords[0], t.textureCoords[2], b, 1 - b);
473             }
474         } else if (b < 0 || b > 1) {
475             i = 1;
476             j = 2;
477             k = 0;
478             u = Vector3d.getBarycenter(t.vertices[0], t.vertices[1], a, 1 - a);
479             v = Vector3d.getBarycenter(t.vertices[1], t.vertices[2], c, 1 - c);
480             cu = getColorsBarycenter(t.colors[0], t.colors[1], a, 1 - a);
481             cv = getColorsBarycenter(t.colors[1], t.colors[2], c, 1 - c);
482             if (t.textureCoords != null) {
483                 tu = Vector3d.getBarycenter(t.textureCoords[0], t.textureCoords[1], a, 1 - a);
484                 tv = Vector3d.getBarycenter(t.textureCoords[1], t.textureCoords[2], c, 1 - c);
485             }
486         } else {
487             i = 0;
488             j = 1;
489             k = 2;
490             u = Vector3d.getBarycenter(t.vertices[0], t.vertices[2], b, 1 - b);
491             v = Vector3d.getBarycenter(t.vertices[0], t.vertices[1], a, 1 - a);
492             cu = getColorsBarycenter(t.colors[0], t.colors[2], b, 1 - b);
493             cv = getColorsBarycenter(t.colors[0], t.colors[1], a, 1 - a);
494             if (t.textureCoords != null) {
495                 tu = Vector3d.getBarycenter(t.textureCoords[0], t.textureCoords[2], b, 1 - b);
496                 tv = Vector3d.getBarycenter(t.textureCoords[0], t.textureCoords[1], a, 1 - a);
497             }
498         }
499
500         Vector3d[] vertices1 = new Vector3d[] {u, t.vertices[i], v};
501         Color[] colors1 = new Color[] {cu, t.colors[i], cv};
502         Vector3d[] vertices2 = new Vector3d[] {u, v, t.vertices[j]};
503         Color[] colors2 = new Color[] {cu, cv, t.colors[j]};
504         Vector3d[] vertices3 = new Vector3d[] {u, t.vertices[j], t.vertices[k]};
505         Color[] colors3 = new Color[] {cu, t.colors[j], t.colors[k]};
506
507         Vector3d[] tvertices1 = null;
508         Vector3d[] tvertices2 = null;
509         Vector3d[] tvertices3 = null;
510         if (t.textureCoords != null) {
511             tvertices1 = new Vector3d[] {tu, t.textureCoords[i], tv};
512             tvertices2 = new Vector3d[] {tu, tv, t.textureCoords[j]};
513             tvertices3 = new Vector3d[] {tu, t.textureCoords[j], t.textureCoords[k]};
514         }
515
516         try {
517             Triangle t1 = new Triangle(vertices1, colors1, null);
518             t1.setSprite(t.getSprite());
519             list.add(t1);
520             Triangle t2 = new Triangle(vertices2, colors2, null);
521             t2.setSprite(t.getSprite());
522             list.add(t2);
523             Triangle t3 = new Triangle(vertices3, colors3, null);
524             t3.setSprite(t.getSprite());
525             list.add(t3);
526             if (t.textureCoords != null) {
527                 t1.textureCoords = tvertices1;
528                 t2.textureCoords = tvertices2;
529                 t3.textureCoords = tvertices3;
530                 t1.image = t2.image = t3.image = t.image;
531                 t1.filter = t2.filter = t3.filter = t.filter;
532             }
533         } catch (InvalidPolygonException e) { }
534
535         addSegments(list, t, p, Vector3d.product(t.v0v1, n), n);
536
537         return list;
538     }
539
540     private static final void addSegments(List<ConvexObject> list, Triangle t, Vector3d p, Vector3d u, Vector3d n) {
541         if (t.segments != null) {
542             List<Segment> segs = new ArrayList<Segment>();
543             for (Segment s : t.segments) {
544                 s.removeConvexObject(t);
545                 List<Segment> l = s.breakObject(p, u, n);
546                 if (l != null && !l.isEmpty()) {
547                     segs.addAll(l);
548                     s.replaceSegment(l);
549                 }
550             }
551             t.textureCoords = null;
552
553             for (Segment s : segs) {
554                 for (ConvexObject tri : list) {
555                     ((Triangle) tri).addSegment(s);
556                 }
557             }
558         }
559     }
560
561     /**
562      * Get the broken triangles in following the intersection of the planes containing t1 and t2.
563      * The planes containing t1 and t2 are supposed to be secant.
564      * @param t1 the first triangle
565      * @param t2 the second triangle
566      * @return an array of length 2 containing the resulting triangles for t1 and t2.
567      */
568     protected static List<ConvexObject> breakIntersectingTriangles(Triangle t1, Triangle t2) {
569         Vector3d n = Vector3d.product(t1.v0v1, t2.v0v1);
570         n = n.times(1 / n.getNorm2());
571         Vector3d u = Vector3d.product(t2.v0v1, n);
572         Vector3d v = Vector3d.product(n, t1.v0v1);
573         Vector3d p = Vector3d.getBarycenter(u, v, t1.v0v1.scalar(t1.vertices[0]), t2.v0v1.scalar(t2.vertices[0]));
574
575         List<ConvexObject> list1 = breakTriangleOnLine(t1, p, t2.v0v1);
576         List<ConvexObject> list2 = breakTriangleOnLine(t2, p, t1.v0v1);
577         list1.addAll(list2);
578
579         return list1;
580     }
581
582     public String toString() {
583         return "Triangle: " + vertices[0].toString() + " " + vertices[1].toString() + " " + vertices[2].toString() + "\nColor: " + colors[0] + "\nPrecedence: " + precedence;
584     }
585 }