Source code

001package com.fs.starfarer.api.impl.campaign.velfield;
002
003import java.awt.Color;
004import java.util.ArrayList;
005import java.util.Collections;
006import java.util.Comparator;
007import java.util.HashMap;
008import java.util.List;
009import java.util.Map;
010
011import org.lwjgl.opengl.GL11;
012import org.lwjgl.util.vector.Vector2f;
013
014import com.fs.starfarer.api.impl.campaign.velfield.SlipstreamTerrainPlugin2.SlipstreamSegment;
015import com.fs.starfarer.api.util.Misc;
016
017public class BoundingBox {
018        
019        public static BoundingBox create(List<SlipstreamSegment> segments) {
020                float padding = 0;
021                List<Vector2f> points = new ArrayList<Vector2f>();
022                SlipstreamSegment prev = null;
023                float unitsPerNormals = 2000f;
024                float distSoFar = unitsPerNormals;
025                //for (SlipstreamSegment seg : segments) {
026                for (int i = 0; i < segments.size(); i++) { 
027                        SlipstreamSegment seg = segments.get(i);
028                        if (distSoFar >= unitsPerNormals || i == segments.size() - 1) {
029                                distSoFar -= unitsPerNormals;
030                                Vector2f n1 = new Vector2f(seg.loc);
031                                Vector2f n2 = new Vector2f(seg.loc);
032                                n1.x += seg.normal.x * seg.width * 0.5f;
033                                n1.y += seg.normal.y * seg.width * 0.5f;
034                                n2.x -= seg.normal.x * seg.width * 0.5f;
035                                n2.y -= seg.normal.y * seg.width * 0.5f;
036                                points.add(n1);
037                                points.add(n2);
038                        } else {
039                                points.add(new Vector2f(seg.loc));
040                        }
041                        if (seg.width * 0.5f > padding) {
042                                padding = seg.width * 0.5f;
043                        }
044                        if (prev != null) {
045                                distSoFar += Misc.getDistance(seg.loc, prev.loc);
046                        }
047                        prev = seg;
048                }
049                padding *= 0.5f;
050                BoundingBox box = new BoundingBox(padding);
051                box.compute(points);
052                return box;
053        }
054
055        protected transient List<Vector2f> points;
056        protected transient List<Vector2f> convexHull;
057        protected List<Vector2f> box;
058        protected float padding;
059        protected float [] rotatedBox;
060        protected float angle;
061
062        protected boolean boxComputed = false;
063        protected Vector2f center = new Vector2f();
064        protected float radius;
065        
066        public BoundingBox(float padding) {
067                this.padding = padding;
068        }
069
070        public boolean pointNeedsDetailedCheck(Vector2f p) {
071                return pointNeedsDetailedCheck(p, 0f);
072        }
073        public boolean pointNeedsDetailedCheck(Vector2f p, float extraRange) {
074                float distSq = Misc.getDistanceSq(center, p);
075                if (distSq > (radius + extraRange) * (radius + extraRange)) return false;
076                
077                if (!boxComputed) return true;
078                
079                Vector2f check = Misc.rotateAroundOrigin(p, angle);
080                
081                return check.x > rotatedBox[0] - extraRange && check.x < rotatedBox[2] + extraRange &&
082                           check.y > rotatedBox[1] - extraRange && check.y < rotatedBox[3] + extraRange;
083        }
084        
085        
086        public void compute(List<Vector2f> points) {
087                boxComputed = false;
088                computeConvexHull(points);
089                computeBox();
090                computeCenterAndRadius();
091        }
092        
093        public void computeCenterAndRadius() {
094                center.set(0, 0);
095                for (Vector2f p : points) {
096                        center.x += p.x;
097                        center.y += p.y;
098                }
099                center.scale(1f / (float) Math.max(1f, points.size()));
100                
101                float maxDistSq = 0f;
102                for (Vector2f p : points) {
103                        float dist = Misc.getDistanceSq(center, p);
104                        if (dist > maxDistSq) maxDistSq = dist;
105                }
106                radius = (float) Math.sqrt(maxDistSq) + padding;
107                
108        }
109        
110        public void computeBox() {
111                if (boxComputed) return;
112                
113                if (convexHull == null || convexHull.size() < 3) {
114                        boxComputed = false;
115                        return;
116                }
117                
118                float minArea = Float.MAX_VALUE;
119                float [] best = null;
120                float bestAngle = 0f;
121                for (int i = 0; i < convexHull.size(); i++) {
122                        int e1 = i;
123                        int e2 = i + 1;
124                        if (i + 1 == convexHull.size()) e2 = 0;
125                        Vector2f p1 = convexHull.get(e1);
126                        Vector2f p2 = convexHull.get(e2);
127                        Vector2f edge = Vector2f.sub(p2, p1, new Vector2f());
128                        edge = Misc.normalise(edge);
129                        
130                    float angle = (float) Math.acos(edge.y) * Misc.DEG_PER_RAD;
131                    List<Vector2f> rotated = rotate(convexHull, angle);
132                    float [] box = getBoundingBox(rotated);
133                    float area = (box[2] - box[0]) * (box[3] - box[1]);
134                    if (area < minArea) {
135                        minArea = area;
136                        best = box;
137                        bestAngle = angle;
138                    }
139                }
140                
141                if (best == null) {
142                        boxComputed = false;
143                        return;
144                }
145                
146                best[0] -= padding;
147                best[1] -= padding;
148                best[2] += padding;
149                best[3] += padding;
150                
151                Vector2f p1 = new Vector2f(best[0], best[1]);
152                Vector2f p2 = new Vector2f(best[2], best[1]);
153                Vector2f p3 = new Vector2f(best[2], best[3]);
154                Vector2f p4 = new Vector2f(best[0], best[3]);
155                box = new ArrayList<Vector2f>();
156                box.add(p1);
157                box.add(p2);
158                box.add(p3);
159                box.add(p4);
160                
161                rotatedBox = best; 
162                this.angle = bestAngle;
163                
164                box = rotate(box, -bestAngle);
165                boxComputed = true;
166        }
167        
168        public static List<Vector2f> rotate(List<Vector2f> points, float angle) {
169                List<Vector2f> result = new ArrayList<Vector2f>();
170                for (Vector2f p : points) {
171                        result.add(Misc.rotateAroundOrigin(p, angle));
172                }
173                return result;
174        }
175        
176        public static float [] getBoundingBox(List<Vector2f> points) {
177                float minX = Float.MAX_VALUE;
178                float minY = Float.MAX_VALUE;
179                float maxX = -Float.MAX_VALUE;
180                float maxY = -Float.MAX_VALUE;
181                for (Vector2f p : points) {
182                        if (p.x < minX) minX = p.x;
183                        if (p.y < minY) minY = p.y;
184                        if (p.x > maxX) maxX = p.x;
185                        if (p.y > maxY) maxY = p.y;
186                }
187                return new float [] {minX, minY, maxX, maxY};
188        }
189        
190        public void computeConvexHull(List<Vector2f> points) {
191                this.points = new ArrayList<Vector2f>(points);
192                
193                if (points.size() < 3) {
194                        boxComputed = false;
195                        return;
196                }
197                
198                Vector2f p1 = null;
199                float minY = Float.MAX_VALUE;
200                for (Vector2f p : points) {
201                        if (p.y < minY) {
202                                p1 = p;
203                                minY = p.y;
204                        }
205                }
206                final Map<Vector2f, Float> angles = new HashMap<Vector2f, Float>();
207                for (Vector2f p : points) {
208                        if (p == p1) continue;
209                        float angle = Misc.getAngleInDegreesStrict(p1, p);
210                        //float angle = 1f;
211                        angles.put(p, angle);
212                }
213                
214                List<Vector2f> sorted = new ArrayList<Vector2f>(points);
215                sorted.remove(p1);
216                Collections.sort(sorted, new Comparator<Vector2f>() {
217                        public int compare(Vector2f o1, Vector2f o2) {
218                                float diff = angles.get(o1) - angles.get(o2);
219                                if (diff < 0) return -1; 
220                                if (diff > 0) return 1;
221                                return 0;
222                        }
223                });
224                
225                convexHull = new ArrayList<Vector2f>();
226                convexHull.add(p1);
227                for (Vector2f p : sorted) {
228                        if (convexHull.size() == 1) {
229                                convexHull.add(p);
230                                continue;
231                        }
232                        while (true) {
233                                float turnDir = getTurnDir(convexHull.get(convexHull.size() - 2),
234                                                                                   convexHull.get(convexHull.size() - 1),
235                                                                                   p);
236                                if (turnDir <= 0) {
237                                        convexHull.remove(convexHull.size() - 1);
238                                        if (convexHull.size() < 2) break;
239                                } else {
240                                        convexHull.add(p);
241                                        break;
242                                }
243                        }
244                }
245                
246                if (convexHull.size() < 3) {
247                        boxComputed = false;
248                        return;
249                }
250                
251        }
252        
253        public static float getTurnDir(Vector2f p1, Vector2f p2, Vector2f p3) {
254                float r = (p2.x - p1.x) * (p3.y - p1.y) - (p2.y  - p1.y) * (p3.x - p1.x);
255                if (r > 0) return 1f; // left turn
256                if (r < 0) return -1f; // right turn
257                return 0; // collinear
258        }
259        
260        
261        public void renderDebug(float alpha) {
262                GL11.glDisable(GL11.GL_TEXTURE_2D);
263                GL11.glEnable(GL11.GL_BLEND);
264                GL11.glBlendFunc(GL11.GL_SRC_ALPHA, GL11.GL_ONE_MINUS_SRC_ALPHA);
265                
266                GL11.glEnable(GL11.GL_POINT_SMOOTH);
267                GL11.glPointSize(10f);
268                GL11.glBegin(GL11.GL_POINTS);
269                Misc.setColor(Color.yellow);
270                if (points != null) {
271                        for (Vector2f p : points) {
272                                GL11.glVertex2f(p.x, p.y);
273                        }
274                }
275                GL11.glEnd();
276                
277                Misc.setColor(Color.white);
278                GL11.glEnable(GL11.GL_LINE_SMOOTH);
279                GL11.glLineWidth(3f);
280                GL11.glBegin(GL11.GL_LINE_LOOP);
281                if (convexHull != null) {
282                        for (Vector2f p : convexHull) {
283                                GL11.glVertex2f(p.x, p.y);
284                        }
285                }
286                GL11.glEnd();
287                
288                Misc.setColor(Color.cyan);
289                GL11.glEnable(GL11.GL_LINE_SMOOTH);
290                GL11.glLineWidth(3f);
291                GL11.glBegin(GL11.GL_LINE_LOOP);
292                if (box != null) {
293                        for (Vector2f p : box) {
294                                GL11.glVertex2f(p.x, p.y);
295                        }
296                }
297                GL11.glEnd();
298                
299        }
300        
301        
302        
303        
304}
305
306
307
308