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