From 6e4dacaca0deac29fa3bef87abb5cd3671551701 Mon Sep 17 00:00:00 2001 From: NathanSweet Date: Mon, 9 Sep 2013 19:03:11 +0200 Subject: [PATCH] Added GeometryUtils so we don't stick everything in Intersector. --- .../gdx/tools/grapheditor/GraphRenderer.java | 34 ---------- gdx/src/com/badlogic/gdx/math/ConvexHull.java | 12 ++-- gdx/src/com/badlogic/gdx/math/GeometryUtils.java | 65 ++++++++++++++++++ gdx/src/com/badlogic/gdx/math/Intersector.java | 78 ++++++++-------------- 4 files changed, 101 insertions(+), 88 deletions(-) delete mode 100644 extensions/gdx-tools/src/com/badlogic/gdx/tools/grapheditor/GraphRenderer.java create mode 100644 gdx/src/com/badlogic/gdx/math/GeometryUtils.java diff --git a/extensions/gdx-tools/src/com/badlogic/gdx/tools/grapheditor/GraphRenderer.java b/extensions/gdx-tools/src/com/badlogic/gdx/tools/grapheditor/GraphRenderer.java deleted file mode 100644 index 1dec76430..000000000 --- a/extensions/gdx-tools/src/com/badlogic/gdx/tools/grapheditor/GraphRenderer.java +++ /dev/null @@ -1,34 +0,0 @@ -package com.badlogic.gdx.tools.grapheditor; - -import java.awt.Font; - -import com.badlogic.gdx.graphics.OrthographicCamera; -import com.badlogic.gdx.graphics.g2d.BitmapFont; -import com.badlogic.gdx.graphics.g2d.SpriteBatch; -import com.badlogic.gdx.graphics.g3d.shaders.graph.ShaderGraph; -import com.badlogic.gdx.graphics.glutils.ShapeRenderer; - -public class GraphRenderer { - private final OrthographicCamera camera; - private final ShapeRenderer shapeRenderer; - private final SpriteBatch batch; - private final BitmapFont font; - - public GraphRenderer() { - camera = new OrthographicCamera(); - camera.setToOrtho(false); - shapeRenderer = new ShapeRenderer(); - batch = new SpriteBatch(); - font = new BitmapFont(); - } - - public void resize(int width, int height) { - camera.viewportWidth = width; - camera.viewportHeight = height; - camera.update(); - } - - public void render(ShaderGraph graph) { - camera.update(); - } -} diff --git a/gdx/src/com/badlogic/gdx/math/ConvexHull.java b/gdx/src/com/badlogic/gdx/math/ConvexHull.java index 447265b9a..d7f071882 100644 --- a/gdx/src/com/badlogic/gdx/math/ConvexHull.java +++ b/gdx/src/com/badlogic/gdx/math/ConvexHull.java @@ -23,7 +23,7 @@ public class ConvexHull { /** Returns a list of points on the convex hull in counter-clockwise order. Note: the last point in the returned list is the * same as the first one. */ /** Returns the convex hull polygon for the given point cloud. - * @param points x,y pairs describing points. + * @param points x,y pairs describing points. Duplicate points will result in undefined behavior. * @param sorted If false, the points will be sorted by the x coordinate then the y coordinate, which is required by the * triangulation algorithm. Note in this case the input array is modified. * @return pairs of coordinates that describe the convex hull polygon in counterclockwise order. Note the returned array is @@ -31,10 +31,11 @@ public class ConvexHull { public FloatArray computePolygon (float[] points, int offset, int count, boolean sorted) { int end = offset + count; - if (!sorted) quicksortPairs(points, offset, end - 1); + if (!sorted) sort(points, offset, count); // Lower hull. FloatArray hull = this.hull; + hull.clear(); for (int i = offset; i < end; i += 2) { float x = points[i]; float y = points[i + 1]; @@ -69,9 +70,10 @@ public class ConvexHull { } /** Sorts x,y pairs of values by the x value, then the y value. - * @param lower Start x index. - * @param upper End x index. */ - private void quicksortPairs (float[] values, int lower, int upper) { + * @param count Number of indices, must be even. */ + private void sort (float[] values, int offset, int count) { + int lower = offset; + int upper = offset + count - 1; IntArray stack = quicksortStack; stack.add(lower); stack.add(upper - 1); diff --git a/gdx/src/com/badlogic/gdx/math/GeometryUtils.java b/gdx/src/com/badlogic/gdx/math/GeometryUtils.java new file mode 100644 index 000000000..8bc848592 --- /dev/null +++ b/gdx/src/com/badlogic/gdx/math/GeometryUtils.java @@ -0,0 +1,65 @@ + +package com.badlogic.gdx.math; + +public class GeometryUtils { + /** Computes the barycentric coordinates v,w for the specified point in the triangle. + * @return barycentricOut */ + static public Vector2 barycentric (Vector2 p, Vector2 a, Vector2 b, Vector2 c, Vector2 barycentricOut) { + Vector2 v0 = b.sub(a); + Vector2 v1 = c.sub(a); + Vector2 v2 = p.sub(a); + float d00 = v0.dot(v0); + float d01 = v0.dot(v1); + float d11 = v1.dot(v1); + float d20 = v2.dot(v0); + float d21 = v2.dot(v1); + float denom = d00 * d11 - d01 * d01; + barycentricOut.x = (d11 * d20 - d01 * d21) / denom; + barycentricOut.y = (d00 * d21 - d01 * d20) / denom; + return barycentricOut; + } + + /** Returns the lowest positive root of the quadric equation given by a* x * x + b * x + c = 0. If no solution is given + * Float.Nan is returned. + * @param a the first coefficient of the quadric equation + * @param b the second coefficient of the quadric equation + * @param c the third coefficient of the quadric equation + * @return the lowest positive root or Float.Nan */ + static public float getLowestPositiveRoot (float a, float b, float c) { + float det = b * b - 4 * a * c; + if (det < 0) return Float.NaN; + + float sqrtD = (float)Math.sqrt(det); + float invA = 1 / (2 * a); + float r1 = (-b - sqrtD) * invA; + float r2 = (-b + sqrtD) * invA; + + if (r1 > r2) { + float tmp = r2; + r2 = r1; + r1 = tmp; + } + + if (r1 > 0) return r1; + if (r2 > 0) return r2; + return Float.NaN; + } + + public static Vector2 triangleCentroid (float x1, float y1, float x2, float y2, float x3, float y3, Vector2 centroid) { + centroid.x = (x1 + x2 + x3) / 3; + centroid.y = (y1 + y2 + y3) / 3; + return centroid; + } + + public static Vector2 quadrilateralCentroid (float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, + Vector2 centroid) { + float avgX1 = (x1 + x2 + x3) / 3; + float avgY1 = (y1 + y2 + y3) / 3; + float avgX2 = (x1 + x4 + x3) / 3; + float avgY2 = (y1 + y4 + y3) / 3; + centroid.x = avgX1 - (avgX1 - avgX2) / 2; + centroid.y = avgY1 - (avgY1 - avgY2) / 2; + return centroid; + } + +} diff --git a/gdx/src/com/badlogic/gdx/math/Intersector.java b/gdx/src/com/badlogic/gdx/math/Intersector.java index f54bca34b..68518b210 100644 --- a/gdx/src/com/badlogic/gdx/math/Intersector.java +++ b/gdx/src/com/badlogic/gdx/math/Intersector.java @@ -16,48 +16,19 @@ package com.badlogic.gdx.math; -import java.util.Arrays; -import java.util.List; - import com.badlogic.gdx.math.Plane.PlaneSide; import com.badlogic.gdx.math.collision.BoundingBox; import com.badlogic.gdx.math.collision.Ray; +import java.util.Arrays; +import java.util.List; + /** Class offering various static methods for intersection testing between different geometric objects. * * @author badlogicgames@gmail.com * @author jan.stria * @author Nathan Sweet */ public final class Intersector { - /** Returns the lowest positive root of the quadric equation given by a* x * x + b * x + c = 0. If no solution is given - * Float.Nan is returned. - * - * @param a the first coefficient of the quadric equation - * @param b the second coefficient of the quadric equation - * @param c the third coefficient of the quadric equation - * @return the lowest positive root or Float.Nan */ - public static float getLowestPositiveRoot (float a, float b, float c) { - float det = b * b - 4 * a * c; - if (det < 0) return Float.NaN; - - float sqrtD = (float)Math.sqrt(det); - float invA = 1 / (2 * a); - float r1 = (-b - sqrtD) * invA; - float r2 = (-b + sqrtD) * invA; - - if (r1 > r2) { - float tmp = r2; - r2 = r1; - r1 = tmp; - } - - if (r1 > 0) return r1; - - if (r2 > 0) return r2; - - return Float.NaN; - } - private final static Vector3 v0 = new Vector3(); private final static Vector3 v1 = new Vector3(); private final static Vector3 v2 = new Vector3(); @@ -86,6 +57,16 @@ public final class Intersector { return true; } + /** Returns true if the given point is inside the triangle. */ + public static boolean isPointInTriangle (float px, float py, float ax, float ay, float bx, float by, float cx, float cy) { + float px1 = px - ax; + float py1 = py - ay; + boolean side12 = (bx - ax) * py1 - (by - ay) * px1 > 0; + if ((cx - ax) * py1 - (cy - ay) * px1 > 0 == side12) return false; + if ((cx - bx) * (py - by) - (cy - by) * (px - bx) > 0 != side12) return false; + return true; + } + public static boolean intersectSegmentPlane (Vector3 start, Vector3 end, Plane plane, Vector3 intersection) { Vector3 dir = end.tmp().sub(start); float denom = dir.dot(plane.getNormal()); @@ -96,23 +77,6 @@ public final class Intersector { return true; } - public static Vector2 triangleCentroid (float x1, float y1, float x2, float y2, float x3, float y3, Vector2 centroid) { - centroid.x = (x1 + x2 + x3) / 3; - centroid.y = (y1 + y2 + y3) / 3; - return centroid; - } - - public static Vector2 quadrilateralCentroid (float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, - Vector2 centroid) { - float avgX1 = (x1 + x2 + x3) / 3; - float avgY1 = (y1 + y2 + y3) / 3; - float avgX2 = (x1 + x4 + x3) / 3; - float avgY2 = (y1 + y4 + y3) / 3; - centroid.x = avgX1 - (avgX1 - avgX2) / 2; - centroid.y = avgY1 - (avgY1 - avgY2) / 2; - return centroid; - } - /** Determines on which side of the given line the point is. Returns -1 if the point is on the left side of the line, 0 if the * point is on the line and 1 if the point is on the right side of the line. Left and right are relative to the lines direction * which is linePoint1 to linePoint2. */ @@ -147,6 +111,22 @@ public final class Intersector { return oddNodes; } + /** Returns true if the specified point is in the polygon. */ + public static boolean isPointInPolygon (float[] polygon, int offset, int count, float x, float y) { + boolean oddNodes = false; + int j = offset + count - 2; + for (int i = offset, n = j; i <= n; i += 2) { + float yi = polygon[i + 1]; + float yj = polygon[j + 1]; + if (yi < y && yj >= y || yj < y && yi >= y) { + float xi = polygon[i]; + if (xi + (y - yi) / (yj - yi) * (polygon[j] - xi) < x) oddNodes = !oddNodes; + } + j = i; + } + return oddNodes; + } + /** Returns the distance between the given line segment and point. * * @param start The line start point -- 2.11.0