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 / ConvexObject.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.Color;
15 import java.awt.Graphics2D;
16 import java.awt.Shape;
17 import java.util.ArrayList;
18 import java.util.List;
19
20 import org.scilab.forge.scirenderer.tranformations.Vector3d;
21 import org.scilab.forge.scirenderer.tranformations.Vector4d;
22
23 /**
24  * @author Calixte DENIZET
25  *
26  * Class to represent a convex object.
27  * Collision and relative positions of convexs object are relatively easy to determinate.
28  * About the method isBehind, it could be interesting to use the algorithm of Chung-Wang.
29  */
30 public abstract class ConvexObject extends AbstractDrawable3DObject implements Clippable {
31
32     private List<ConvexObject> areas;
33
34     /**
35      * Default constructor
36      * @param vertices the vertices
37      * @param colors the colors
38      */
39     public ConvexObject(Vector3d[] vertices, Color[] colors) throws InvalidPolygonException {
40         super(vertices, colors);
41     }
42
43     /**
44      * Abstract method
45      * Break this ConvexObject against the ConvexObject o
46      * @param o a ConvexObject
47      * @return a list of ConvexObject.
48      */
49     public abstract List<ConvexObject> breakObject(ConvexObject o);
50
51     /**
52      * {@inheritDoc}
53      */
54     public abstract List<ConvexObject> breakObject(Vector4d v);
55
56     public void addArea(ConvexObject co) {
57         if (areas == null) {
58             areas = new ArrayList<ConvexObject>();
59         }
60         areas.add(co);
61     }
62
63     protected void drawAreas(Graphics2D g2d) {
64         if (areas != null) {
65             for (ConvexObject co : areas) {
66                 Shape oldClip = g2d.getClip();
67                 g2d.clip(this.getProjectedContour());
68                 co.draw(g2d);
69                 g2d.setClip(oldClip);
70             }
71         }
72     }
73
74     /**
75      * Test the coplanarity of two objects
76      * @param o a ConvexObject
77      * @return true if the two objects are coplanar
78      */
79     public boolean areCoplanar(ConvexObject o) {
80         if (!(this instanceof Segment)) {
81             double sc = vertices[0].scalar(v0v1);
82             if (o instanceof Segment) {
83                 return isEqual(sc, o.vertices[0].scalar(v0v1)) && isEqual(sc, o.vertices[1].scalar(v0v1));
84             }
85             return isEqual(sc, o.vertices[0].scalar(v0v1)) && isEqual(sc, o.vertices[1].scalar(v0v1)) && isEqual(sc, o.vertices[2].scalar(v0v1));
86         }
87
88         if (!(o instanceof Segment)) {
89             return o.areCoplanar(this);
90         }
91
92         if (o.vertices[0].equals(vertices[0]) || o.vertices[1].equals(vertices[0]) || o.vertices[0].equals(vertices[1]) || o.vertices[1].equals(vertices[1])) {
93             return true;
94         }
95
96         Vector3d v = Vector3d.product(v0, o.v0);
97         return isNull(v.scalar(vertices[0].minus(o.vertices[0])));
98     }
99
100     /**
101      * Check if o is behind this.
102      * Take care: the algorithms used are for convex objects (typically tri-tri, seg-seg or tri-seg)
103      * @return true if o is behind this
104      */
105     public int isBehind(ConvexObject o) {
106         BoundingBox bbox = getBBox();
107         BoundingBox obbox = o.getBBox();
108         // Quick test in using bounding boxes
109         if (!bbox.isIntersecting(obbox)) {
110             if (bbox.xCompare(obbox) != 0 || bbox.yCompare(obbox) != 0) {
111                 return 0;
112             }
113         }
114
115         // Check if the two objects intersect in projection plane or not
116         if (check2DIntersection(o)) {
117             // We have a strict intersection or an intersection on an edge
118             if (areCoplanar(o)) {
119                 return getPrecedence() > o.getPrecedence() ? 1 : -1;
120             }
121
122             // Quick test with bounding-box along z-axis
123             int ret = bbox.zCompare(obbox);
124             if (ret != 0) {
125                 return ret;
126             }
127
128             // In the most of the cases, one of the two following test are sufficient to determinate
129             // if one object is behind or on front of the plane containing this or o
130             ret = check(o, getNormal());
131             if (ret != 0) {
132                 return ret;
133             }
134
135             ret = check(o, o.getNormal());
136             if (ret != 0) {
137                 return ret;
138             }
139
140             // Check against the cross product of one edge of this and one edge of o
141             int M = vertices.length == 2 ? 1 : vertices.length;
142             int N = o.vertices.length == 2 ? 1 : o.vertices.length;
143             for (int j = 0; j < M; j++) {
144                 int l = (j + 1 < vertices.length) ? j + 1 : 0;
145                 Vector3d e = vertices[l].minus(vertices[j]);
146                 for (int k = 0; k < N; k++) {
147                     int m = (k + 1 < o.vertices.length) ? k + 1 : 0;
148                     Vector3d oe = o.vertices[m].minus(o.vertices[k]);
149                     ret = check(o, Vector3d.product(e, oe).getNormalized());
150                     if (ret != 0) {
151                         return ret;
152                     }
153                 }
154             }
155
156             // At this point: there is a collision between the two objects
157             return 2;
158         } else {
159             return 0;
160         }
161     }
162
163     /**
164      * Check the intersections of the projection on the xOy-plane of this and o
165      * The algorithm is the following: for each edge, determinate the normal vector and project all the points
166      * of this and o on the normal. If the intersection of [this.min,this.max] and [o.min, o.max] is empty, then
167      * we have a separating line so the two objects are separated.
168      * @param o the object to test with this
169      * @return true if there is a collision
170      */
171     public boolean check2DIntersection(final ConvexObject o) {
172         int ret = check2D(this, o);
173         if (ret != -1) {
174             return false;
175         }
176
177         ret = check2D(o, this);
178         if (ret != -1) {
179             return false;
180         }
181
182         return true;
183     }
184
185     /**
186      * Check the intersections of the projection on the xOy-plane of this and o
187      * The algorithm is the following: for each edge, determinate the normal vector and project all the points
188      * of this and o on the normal. If the intersection of [this.min,this.max] and [o.min, o.max] is empty, then
189      * we have a separating line so the two objects are separated.
190      * @param o the object to test with this
191      * @return true if there is a collision
192      */
193     public boolean check2DTrueIntersection(final ConvexObject o) {
194         int ret = check2D2(this, o);
195         if (ret == 1) {
196             return true;
197         } else if (ret == 0) {
198             return false;
199         }
200
201         ret = check2D2(o, this);
202         if (ret == 1) {
203             return true;
204         } else if (ret == 0) {
205             return false;
206         }
207
208         return true;
209     }
210
211     /**
212      * Check 2D intersection of two convex objects
213      * @param o1 first object
214      * @param o2 second object
215      * @return -1 if strict intersection, 1 if intersection on an edge and 0 if no intersection
216      */
217     private static final int check2D(final ConvexObject o1, final ConvexObject o2) {
218         // When o1 is a Segment (i.e. o1.vertices;length == 2) it is mandatory to check against ortho(v1-v0) and ortho(v0-v1)
219         int M = o1.vertices.length == 2 ? 1 : o1.vertices.length;
220         for (int i = 0; i < M; i++) {
221             int j = (i + 1 < o1.vertices.length) ? i + 1 : 0;
222             double xN = o1.vertices[i].getY() - o1.vertices[j].getY();
223             double yN = o1.vertices[j].getX() - o1.vertices[i].getX();
224             double n = Math.hypot(xN, yN);
225             xN /= n;
226             yN /= n;
227             double[] mM = minmax2D(o1, xN, yN);
228             double min = mM[0];
229             double max = mM[1];
230
231             mM = minmax2D(o2, xN, yN);
232             double omin = mM[0];
233             double omax = mM[1];
234
235             if (max < omin || omax < min) {
236                 return 0;
237             }
238
239             if (isEqual(max, omin) || isEqual(omax, min)) {
240                 return 1;
241             }
242         }
243
244         return -1;
245     }
246
247     /**
248      * Check 2D intersection of two convex objects
249      * @param o1 first object
250      * @param o2 second object
251      * @return -1 if strict intersection, 1 if intersection on an edge and 0 if no intersection
252      */
253     private static final int check2D2(final ConvexObject o1, final ConvexObject o2) {
254         // When o1 is a Segment (i.e. o1.vertices;length == 2) it is mandatory to check against ortho(v1-v0) and ortho(v0-v1)
255         int M = o1.vertices.length == 2 ? 1 : o1.vertices.length;
256         boolean bool = false;
257         for (int i = 0; i < M; i++) {
258             int j = (i + 1 < o1.vertices.length) ? i + 1 : 0;
259             double xN = o1.vertices[i].getY() - o1.vertices[j].getY();
260             double yN = o1.vertices[j].getX() - o1.vertices[i].getX();
261             double n = Math.hypot(xN, yN);
262             xN /= n;
263             yN /= n;
264             double[] mM = minmax2D(o1, xN, yN);
265             double min = mM[0];
266             double max = mM[1];
267
268             mM = minmax2D(o2, xN, yN);
269             double omin = mM[0];
270             double omax = mM[1];
271
272             if (max < omin || omax < min) {
273                 return 0;
274             }
275
276             if (!bool && (isEqual(max, omin) || isEqual(omax, min))) {
277                 bool = true;
278             }
279         }
280
281         if (bool) {
282             return 1;
283         }
284
285         return -1;
286     }
287
288     /**
289      * Check the intersection this and o against vector v.
290      * The algorithm is just to project this and o on the vector v and to check if the two projected sets
291      * can be separated.
292      * @param v the vector where to project
293      * @return 1 if o is behind this, 0 if it is undeterminated and -1 if this is behind o.
294      */
295     protected int check(final ConvexObject o, final Vector3d v) {
296         if (!v.isNearZero()) {
297             double[] mM = minmax3D(this, v);
298             double min = mM[0];
299             double max = mM[1];
300
301             mM = minmax3D(o, v);
302             double omin = mM[0];
303             double omax = mM[1];
304             double z = v.getZ();
305
306             if (Math.signum(z) == 0) {
307                 return 0;
308             }
309
310             if (isLowerOrEqual(max, omin)) {
311                 return (int) Math.signum(z);
312             }
313
314             if (isLowerOrEqual(omax, min)) {
315                 return (int) - Math.signum(z);
316             }
317         }
318
319         return 0;
320     }
321 }