Revert "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             area.add(new Area(stroke.createStrokedShape(contour)));
197             g2d.setStroke(EMPTYSTROKE);
198             g2d.setColor(colors[0]);
199             g2d.fill(area);
200         } else {
201             DrawTools.fillGouraud(g2d, this);
202         }
203
204         if (segments != null) {
205             for (Segment s : segments) {
206                 s.removeConvexObject(this);
207                 s.draw(g2d);
208             }
209         }
210
211         drawAreas(g2d);
212     }
213
214     @Override
215     public List<ConvexObject> breakObject(Vector4d v) {
216         double[] vv = v.getData();
217         Vector3d np = new Vector3d(vv);
218         int ret = isBehind(np, vv[3]);
219         if (ret == 1) {
220             List<ConvexObject> list = new ArrayList<ConvexObject>(1);
221             list.add(this);
222             return list;
223         } else if (ret == -1) {
224             return null;
225         }
226
227         Vector3d n = Vector3d.product(this.v0v1, np);
228         n = n.times(1 / n.getNorm2());
229         Vector3d u = Vector3d.product(np, n);
230         Vector3d w = Vector3d.product(n, this.v0v1);
231         Vector3d p = Vector3d.getBarycenter(u, w, this.v0v1.scalar(this.vertices[0]), -vv[3]);
232
233         List<ConvexObject> list1 = breakTriangleOnLine(this, p, np);
234         List<ConvexObject> list = new ArrayList<ConvexObject>(3);
235         for (ConvexObject o : list1) {
236             if (o.isBehind(np, vv[3]) == 1) {
237                 list.add(o);
238             }
239         }
240
241         return list;
242     }
243
244     protected boolean isPointInside(final Vector3d v) {
245         return isPointInside(v, true);
246     }
247
248     protected boolean isPointInside(final Vector3d v, final boolean checkCoplanarity) {
249         Vector3d v2 = v.minus(vertices[0]);
250         if (checkCoplanarity && !isNull(v2.scalar(v0v1))) {
251             return false;
252         }
253
254         Vector3d v0v1v2 = Vector3d.product(v0v1, v2);
255         double a = -v0v1v2.scalar(v1);
256         if (a < 0 || isNull(a)) {
257             return false;
258         }
259
260         double b = v0v1v2.scalar(v0);
261         if (b < 0 || isNull(b)) {
262             return false;
263         }
264
265         return a + b < nv0v1 || isEqual(a + b, nv0v1);
266     }
267
268     protected boolean isCoplanar(final Segment s) {
269         double sc = vertices[0].scalar(v0v1);
270         return isEqual(sc, s.vertices[0].scalar(v0v1)) && isEqual(sc, s.vertices[1].scalar(v0v1));
271     }
272
273     protected boolean isCoplanar(final Triangle t) {
274         double sc = vertices[0].scalar(v0v1);
275         return isEqual(sc, t.vertices[0].scalar(v0v1)) && isEqual(sc, t.vertices[1].scalar(v0v1)) && isEqual(sc, t.vertices[2].scalar(v0v1));
276     }
277
278     protected boolean isSegmentAcross(final Segment s) {
279         if (!isCoplanar(s)) {
280             // the segment and the triangle are not coplanar
281             return false;
282         }
283
284         return check2DTrueIntersection(s);
285     }
286
287     protected boolean isSegmentInside(final Segment s) {
288         if (!isCoplanar(s)) {
289             // the segment and the triangle are not coplanar
290             return false;
291         }
292
293         // Since there is a good probability that a segment is triangle border we check that
294         if ((s.vertices[0].equals(vertices[0]) || s.vertices[0].equals(vertices[1]) || s.vertices[0].equals(vertices[2]))
295                 && (s.vertices[1].equals(vertices[0]) || s.vertices[1].equals(vertices[1]) || s.vertices[1].equals(vertices[2]))) {
296             return true;
297         }
298
299         return isPointInside(s.vertices[0], false) || isPointInside(s.vertices[1], false) || check2DIntersection(s);
300     }
301
302     protected boolean isSegmentIntersects(final Segment s) {
303         Vector3d v3 = s.vertices[0].minus(vertices[0]);
304         Vector3d v4 = s.vertices[1].minus(vertices[0]);
305         double c = v3.scalar(v0v1);
306
307         if (Math.signum(c) == Math.signum(v4.scalar(v0v1))) {
308             return false;
309         }
310
311         Vector3d v2 = s.vertices[0].minus(s.vertices[1]);
312         Vector3d v1v2 = Vector3d.product(v1, v2);
313         double a = v3.scalar(v1v2);
314         double b = Vector3d.det(v3, v2, v0);
315         double detv0v1v2 = v0.scalar(v1v2);
316         double sign = Math.signum(detv0v1v2);
317
318         return Math.signum(a) == sign && Math.signum(b) == sign && Math.signum(c) == sign && a + b <= detv0v1v2 && c <= detv0v1v2;
319     }
320
321     protected double getSegmentIntersection(final Segment s) {
322         Vector3d v = s.vertices[1].minus(vertices[0]);
323         double c = v.scalar(v0v1) / s.v0.scalar(v0v1);
324
325         if (isNegativeOrNull(c) || isGreaterOrEqual(c, 1)) {
326             return Double.NaN;
327         }
328
329         Vector3d p = Vector3d.getBarycenter(s.vertices[0], s.vertices[1], c, 1 - c);
330         if (isPointInside(p, false)) {
331             return c;
332         }
333
334         return Double.NaN;
335     }
336
337     protected static List<ConvexObject> breakSegmentOnTriangle(final Triangle t, final Segment s) {
338         double c = t.getSegmentIntersection(s);
339         if (Double.isNaN(c)) {
340             return null;
341         }
342
343         List<ConvexObject> list = new ArrayList<ConvexObject>(2);
344         Vector3d p = Vector3d.getBarycenter(s.vertices[0], s.vertices[1], c, 1 - c);
345         Color cc = getColorsBarycenter(s.colors[0], s.colors[1], c, 1 - c);
346
347         try {
348             list.add(new Segment(new Vector3d[] {s.vertices[0], p}, new Color[] {s.colors[0], cc}, s.stroke));
349             list.add(new Segment(new Vector3d[] {p, s.vertices[1]}, new Color[] {cc, s.colors[1]}, s.stroke));
350         } catch (InvalidPolygonException e) { }
351
352
353         return list;
354     }
355
356     /**
357      * Break a triangle according to its intersection with a line containing p in the plane of the triangle and orthogonal to n
358      * The triangle and the line are supposed to be coplanar.
359      * @param t the triangle to break
360      * @param p a point of the line
361      * @param n a vector
362      * @return a list of triangles
363      */
364     protected static List<ConvexObject> breakTriangleOnLine(Triangle t, Vector3d p, Vector3d n) {
365         // aP0+(1-a)P1
366         double a = t.vertices[1].minus(p).scalar(n) / t.v0.scalar(n);
367         // bP0+(1-b)P2
368         double b = t.vertices[2].minus(p).scalar(n) / t.v1.scalar(n);
369         // cP1+(1-c)P2
370         Vector3d v2 = t.vertices[2].minus(t.vertices[1]);
371         double c = t.vertices[2].minus(p).scalar(n) / v2.scalar(n);
372
373         List<ConvexObject> list = new ArrayList<ConvexObject>(3);
374         int i = -1;
375         int j = -1;
376         int k = -1;
377         double weight = -1;
378         if (isNull(a)) {
379             // We are on P1
380             i = 1;
381             j = 2;
382             k = 0;
383             weight = b;
384         }
385
386         if (isNull(a - 1)) {
387             // We are on P0
388             if (weight != -1) {
389                 list.add(t);
390                 return list;
391             } else {
392                 i = 0;
393                 j = 1;
394                 k = 2;
395                 weight = c;
396             }
397         }
398
399         if (isNull(b)) {
400             // We are on P2
401             if (weight != -1) {
402                 list.add(t);
403                 return list;
404             } else {
405                 i = 2;
406                 j = 0;
407                 k = 1;
408                 weight = a;
409             }
410         }
411
412         if (i != -1) {
413             if (weight >= 0 && weight <= 1) {
414                 // We break into two triangles
415                 Vector3d vb = Vector3d.getBarycenter(t.vertices[j], t.vertices[k], weight, 1 - weight);
416                 Color cb = getColorsBarycenter(t.colors[j], t.colors[k], weight, 1 - weight);
417                 Vector3d[] vertices1 = new Vector3d[] {t.vertices[i], t.vertices[j], vb};
418                 Vector3d[] vertices2 = new Vector3d[] {t.vertices[i], vb, t.vertices[k]};
419                 Color[] colors1 = new Color[] {t.colors[i], t.colors[j], cb};
420                 Color[] colors2 = new Color[] {t.colors[i], cb, t.colors[k]};
421
422                 Vector3d[] tvertices1 = null;
423                 Vector3d[] tvertices2 = null;
424                 if (t.textureCoords != null) {
425                     Vector3d tvb = Vector3d.getBarycenter(t.textureCoords[j], t.textureCoords[k], weight, 1 - weight);
426                     tvertices1 = new Vector3d[] {t.textureCoords[i], t.textureCoords[j], tvb};
427                     tvertices2 = new Vector3d[] {t.textureCoords[i], tvb, t.textureCoords[k]};
428                 }
429
430                 try {
431                     Triangle t1 = new Triangle(vertices1, colors1, null);
432                     t1.setSprite(t.getSprite());
433                     list.add(t1);
434                     Triangle t2 = new Triangle(vertices2, colors2, null);
435                     t2.setSprite(t.getSprite());
436                     list.add(t2);
437                     if (t.textureCoords != null) {
438                         t1.textureCoords = tvertices1;
439                         t2.textureCoords = tvertices2;
440                         t1.image = t2.image = t.image;
441                         t1.filter = t2.filter = t.filter;
442                     }
443                 } catch (InvalidPolygonException e) { }
444
445                 addSegments(list, t, p, Vector3d.product(t.v0v1, n), n);
446
447                 return list;
448             } else {
449                 list.add(t);
450                 return list;
451             }
452         }
453
454         Color cu, cv;
455         Vector3d u, v;
456         Vector3d tu = null, tv = null;
457         // t has not been broken, so continue...
458         if (a < 0 || a > 1) {
459             i = 2;
460             j = 0;
461             k = 1;
462             u = Vector3d.getBarycenter(t.vertices[1], t.vertices[2], c, 1 - c);
463             v = Vector3d.getBarycenter(t.vertices[0], t.vertices[2], b, 1 - b);
464             cu = getColorsBarycenter(t.colors[1], t.colors[2], c, 1 - c);
465             cv = getColorsBarycenter(t.colors[0], t.colors[2], b, 1 - b);
466             if (t.textureCoords != null) {
467                 tu = Vector3d.getBarycenter(t.textureCoords[1], t.textureCoords[2], c, 1 - c);
468                 tv = Vector3d.getBarycenter(t.textureCoords[0], t.textureCoords[2], b, 1 - b);
469             }
470         } else if (b < 0 || b > 1) {
471             i = 1;
472             j = 2;
473             k = 0;
474             u = Vector3d.getBarycenter(t.vertices[0], t.vertices[1], a, 1 - a);
475             v = Vector3d.getBarycenter(t.vertices[1], t.vertices[2], c, 1 - c);
476             cu = getColorsBarycenter(t.colors[0], t.colors[1], a, 1 - a);
477             cv = getColorsBarycenter(t.colors[1], t.colors[2], c, 1 - c);
478             if (t.textureCoords != null) {
479                 tu = Vector3d.getBarycenter(t.textureCoords[0], t.textureCoords[1], a, 1 - a);
480                 tv = Vector3d.getBarycenter(t.textureCoords[1], t.textureCoords[2], c, 1 - c);
481             }
482         } else {
483             i = 0;
484             j = 1;
485             k = 2;
486             u = Vector3d.getBarycenter(t.vertices[0], t.vertices[2], b, 1 - b);
487             v = Vector3d.getBarycenter(t.vertices[0], t.vertices[1], a, 1 - a);
488             cu = getColorsBarycenter(t.colors[0], t.colors[2], b, 1 - b);
489             cv = getColorsBarycenter(t.colors[0], t.colors[1], a, 1 - a);
490             if (t.textureCoords != null) {
491                 tu = Vector3d.getBarycenter(t.textureCoords[0], t.textureCoords[2], b, 1 - b);
492                 tv = Vector3d.getBarycenter(t.textureCoords[0], t.textureCoords[1], a, 1 - a);
493             }
494         }
495
496         Vector3d[] vertices1 = new Vector3d[] {u, t.vertices[i], v};
497         Color[] colors1 = new Color[] {cu, t.colors[i], cv};
498         Vector3d[] vertices2 = new Vector3d[] {u, v, t.vertices[j]};
499         Color[] colors2 = new Color[] {cu, cv, t.colors[j]};
500         Vector3d[] vertices3 = new Vector3d[] {u, t.vertices[j], t.vertices[k]};
501         Color[] colors3 = new Color[] {cu, t.colors[j], t.colors[k]};
502
503         Vector3d[] tvertices1 = null;
504         Vector3d[] tvertices2 = null;
505         Vector3d[] tvertices3 = null;
506         if (t.textureCoords != null) {
507             tvertices1 = new Vector3d[] {tu, t.textureCoords[i], tv};
508             tvertices2 = new Vector3d[] {tu, tv, t.textureCoords[j]};
509             tvertices3 = new Vector3d[] {tu, t.textureCoords[j], t.textureCoords[k]};
510         }
511
512         try {
513             Triangle t1 = new Triangle(vertices1, colors1, null);
514             t1.setSprite(t.getSprite());
515             list.add(t1);
516             Triangle t2 = new Triangle(vertices2, colors2, null);
517             t2.setSprite(t.getSprite());
518             list.add(t2);
519             Triangle t3 = new Triangle(vertices3, colors3, null);
520             t3.setSprite(t.getSprite());
521             list.add(t3);
522             if (t.textureCoords != null) {
523                 t1.textureCoords = tvertices1;
524                 t2.textureCoords = tvertices2;
525                 t3.textureCoords = tvertices3;
526                 t1.image = t2.image = t3.image = t.image;
527                 t1.filter = t2.filter = t3.filter = t.filter;
528             }
529         } catch (InvalidPolygonException e) { }
530
531         addSegments(list, t, p, Vector3d.product(t.v0v1, n), n);
532
533         return list;
534     }
535
536     private static final void addSegments(List<ConvexObject> list, Triangle t, Vector3d p, Vector3d u, Vector3d n) {
537         if (t.segments != null) {
538             List<Segment> segs = new ArrayList<Segment>();
539             for (Segment s : t.segments) {
540                 s.removeConvexObject(t);
541                 List<Segment> l = s.breakObject(p, u, n);
542                 if (l != null && !l.isEmpty()) {
543                     segs.addAll(l);
544                     s.replaceSegment(l);
545                 }
546             }
547             t.textureCoords = null;
548
549             for (Segment s : segs) {
550                 for (ConvexObject tri : list) {
551                     ((Triangle) tri).addSegment(s);
552                 }
553             }
554         }
555     }
556
557     /**
558      * Get the broken triangles in following the intersection of the planes containing t1 and t2.
559      * The planes containing t1 and t2 are supposed to be secant.
560      * @param t1 the first triangle
561      * @param t2 the second triangle
562      * @return an array of length 2 containing the resulting triangles for t1 and t2.
563      */
564     protected static List<ConvexObject> breakIntersectingTriangles(Triangle t1, Triangle t2) {
565         Vector3d n = Vector3d.product(t1.v0v1, t2.v0v1);
566         n = n.times(1 / n.getNorm2());
567         Vector3d u = Vector3d.product(t2.v0v1, n);
568         Vector3d v = Vector3d.product(n, t1.v0v1);
569         Vector3d p = Vector3d.getBarycenter(u, v, t1.v0v1.scalar(t1.vertices[0]), t2.v0v1.scalar(t2.vertices[0]));
570
571         List<ConvexObject> list1 = breakTriangleOnLine(t1, p, t2.v0v1);
572         List<ConvexObject> list2 = breakTriangleOnLine(t2, p, t1.v0v1);
573         list1.addAll(list2);
574
575         return list1;
576     }
577
578     public String toString() {
579         return "Triangle: " + vertices[0].toString() + " " + vertices[1].toString() + " " + vertices[2].toString() + "\nColor: " + colors[0] + "\nPrecedence: " + precedence;
580     }
581 }