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