Polygon Raycast

Discuss issues specific the Java port of Box2D
toucansam
Posts: 356
Joined: Mon Jun 08, 2009 12:21 pm
Contact:

Re: Polygon Raycast

Postby toucansam » Wed Jul 22, 2009 8:51 am

That decomposition is great, by the way

Michiel
Posts: 34
Joined: Sat May 02, 2009 6:07 am

Re: Polygon Raycast

Postby Michiel » Fri Aug 21, 2009 2:41 am

Thanks for the steering code!

Ok, I promised to post the decomposition code so I will. But first I would like to draw attention to a new feature, the light!

Press F when running the demo to get something of a flashlight. Its useless but it looks kinda neat.

Ok the decomposition code:

Code: Select all

@Override
   public void destroy() {
      super.destroy();
      
      //Get the shape as if you would render it
      XForm xf = body.getXForm();
      Shape shape = body.getShapeList();
      Vec2[] vertices;
      
      if (shape.getType() == ShapeType.POLYGON_SHAPE) {
         PolygonShape poly = (PolygonShape)shape;
         int vertexCount = poly.getVertexCount();
         Vec2[] localVertices = poly.getVertices();
         
         assert(vertexCount <= Settings.maxPolygonVertices);
         vertices = new Vec2[vertexCount];

         //Transform
         for (int i = 0; i < vertexCount; ++i) {
            vertices[i] = XForm.mul(xf, localVertices[i]);
         }
   
         //Could check for the size of the piece to determine variables
//         if((CalculationTool.area(vertices) > x.xf)) {
//         }   

         //Make an array for the new shapes
         ArrayList<Vec2[]> newShapes = new ArrayList<Vec2[]>();
         //Add the vertices of the current shape
         newShapes.add(vertices);
         
         //Make an array for temporary shapes
         ArrayList<Vec2[]> tempShapes = new ArrayList<Vec2[]>();
         
         //Calculate boundry values
         Vec2 upperBound = CalculationTool.getUpperBound(vertices);
         Vec2 lowerBound = CalculationTool.getLowerBound(vertices);
         //System.out.println("upperBound:"+upperBound);
         //System.out.println("lowerBound:"+lowerBound);
         
         //Calculate size values
         float width = lowerBound.x - upperBound.x;
         float height = upperBound.y - lowerBound.y;    
         //System.out.println("width:"+width);
         //System.out.println("height:"+height);
            
         //Run this loop X times, means we will fire X random lines at the shape
         for(int i=0;i<4;i++) {
            //Make variables for the cutting lines
            Vec2 point1 = new Vec2(0.0f,0.0f);
            Vec2 point2 = new Vec2(0.0f,0.0f);
            
            //From here we lay out a line randomly over the shape
            float rand1 = 2 * (float) Math.random();
            float rand2 = 2 * (float) Math.random();
               
            if(rand1 > 1) {
               rand1 -= 1;
               
               point1.x = upperBound.x;
               point1.y = upperBound.y - (rand1 * height);
            }
            else {
               point1.x = upperBound.x + (rand1 * width);
               point1.y = lowerBound.y;
            }
               
            if(rand2 > 1) {
               rand2 -= 1;
               
               point2.x = lowerBound.x;
               point2.y = lowerBound.y + (rand2 * height);
            }
            else {
               point2.x = lowerBound.x - (rand2 * width);
               point2.y = upperBound.y;
            }
               
            //System.out.println("point1:"+point1);
            //System.out.println("point2:"+point2);
            
            //For every shape in newshapes (at the beginning it contains the original shape)
            for(Vec2[] s : newShapes) {
               //Split the shape with the random line
               ArrayList<Vec2[]> breakResult =  breakApart(point1,point2,s);
               
               //If the result is not null we temporarily store it
               if(breakResult != null) {
               //   System.out.println("breakResult containing: "+breakResult.size());
                  tempShapes.addAll(breakResult);
               }
            }
               
            //Transplant the temporary shapes into the newshapes array for the next loop
            newShapes.clear();
            newShapes.addAll(tempShapes);
            tempShapes.clear();
         }
            
         //Create all new pieces of debris
         for(Vec2[] s : newShapes) {
            WorldObjectFactory.createDebris(s,body.getLinearVelocity(),body.getAngularVelocity());
         }
      }
      
      //To avoid flickering
      render();
   }
   
   /**
    */
   public final ArrayList<Vec2[]> breakApart(Vec2 point1, Vec2 point2, Vec2[] vertices) {
      //Make an array for the new shapes after the breaking
      ArrayList<Vec2[]> newShapes = new ArrayList<Vec2[]>();
      
      //Store the array index of where the intersections arose
      int intersection1 = -1;
      int intersection2 = -1;
      
      //Make an array to store results
      ArrayList<Vec2> intersections = new ArrayList<Vec2>();

      //Load the number of lines in this Shape
      int linesCount = vertices.length;
         
      //This iterator represents the end point of a segment
      int ii = 1;
      //For the number of lines in the Shape
      for(int i=0;i<linesCount;i++) {
         //Call Java2D intersect method which tells us IF there is an intersection between the given lines
         if(Line2D.linesIntersect(
               //Supply the beginning and end point of the provided segment
               point1.x,point1.y,
               point2.x,point2.y,
               
               //The start-vertex of the Shape's segment
               vertices[i].x,vertices[i].y,
               //The end-vertex of the Shape's segment
               vertices[ii].x,vertices[ii].y)) {
            
            //Declare variables to store the slope of both segments
            float slope1;
            float slope2;
            
            //We need to know the horizontal difference to prevent divide by zero
            float xSlope1 = (point2.x - point1.x);
            float xSlope2 = (vertices[ii].x - vertices[i].x);
            
            //We check if it is not zero
            if(xSlope1 == 0) {
               //We will use the static horizontal position
               slope1 = point1.x;
            }
            //Else we calculate it
            else {
               slope1 = ((point2.y - point1.y) / (point2.x - point1.x));
            }
            //Same for the other segment
            if(xSlope2 == 0) {
               slope2 = vertices[i].x;
            }
            else {
               slope2 = ((vertices[ii].y - vertices[i].y) / (vertices[ii].x - vertices[i].x));
            }
            
            //Calculate the vertical interception-point
            float intercept1 = point1.y - (slope1 * point1.x);
            float intercept2 = vertices[i].y - (slope2 * vertices[i].x);
            
            //Calculate the intersection
            Vec2 intersection = new Vec2(0.0f,0.0f);
            intersection.x = ( (intercept2 - intercept1) / (slope1 - slope2) );
            intersection.y = (slope1 * intersection.x) + intercept1;
            //Add this intersection to the result-set
            intersections.add(intersection);
      
            //Store the place in the array where they took place
            if(intersection1 == -1) {
               intersection1 = i+1;
            }
            else {
               intersection2 = i+1;
            }
         }
            
         //Increment Shape's segment end-vertex
         ii++;
         //If it is greater than the array's length, we take the first vertex at index zero
         if(ii == linesCount) {
            ii=0;
         }
      }
      
      //At this points we either have intersected the shape or not.
      if(intersections.size() != 2) {
         //System.out.println("Returning old shape");
         newShapes.add(CalculationTool.resizePolygon(vertices,0.99f));
         return newShapes;
      }
      //System.out.println("intersections found : "+intersections.size());
      //System.out.println("intersection1 at : "+intersection1);
      //System.out.println("intersection2 at : "+intersection2);
      
      //Make two new polygons
      ArrayList<Vec2> newPolygon1 = new ArrayList<Vec2>();
      ArrayList<Vec2> newPolygon2 = new ArrayList<Vec2>();
      
      //Add all points to the first polygon that come before the first intersection
      for(int i=0;i<intersection1;i++) {
         newPolygon1.add(vertices[i]);
      }
      
      //Both polygons receive the first intersection
      newPolygon1.add(intersections.get(0));
      newPolygon2.add(intersections.get(0));
      
      //Add all points to the second polygon that come after the first intersection but before the second
      for(int i=intersection1;i<intersection2;i++) {
         newPolygon2.add(vertices[i]);
      }
      
      //Both polygons receive the second intersection
      newPolygon1.add(intersections.get(1));
      newPolygon2.add(intersections.get(1));
      
      //Add all points to the first polygon that come after the second intersection
      for(int i=intersection2;i<vertices.length;i++) {
         newPolygon1.add(vertices[i]);
      }
      
      //Check if the polygon is to complex, else we remove a vertex
      if(newPolygon1.size() > Settings.maxPolygonVertices) {
         newPolygon1.remove(4);
      }
      
      //Check if the polygon is to complex, else we remove a vertex
      if(newPolygon2.size() > Settings.maxPolygonVertices) {
         newPolygon2.remove(4);
      }
      
      //Pass the result from an arraylist to an simple array
      Vec2[] tmp = new Vec2[newPolygon1.size()];
      for(int i=0;i<newPolygon1.size();i++) {
         tmp[i] = newPolygon1.get(i);
      }
      //If the polygon big enough we will add it
      if((CalculationTool.area(tmp) > 0.04f)) {
         //Add the new polygon and shrink it a little
         newShapes.add(CalculationTool.resizePolygon(tmp,0.99f));
      }
      
      //Pass the result from an arraylist to an simple array
      tmp = new Vec2[newPolygon2.size()];
      for(int i=0;i<newPolygon2.size();i++) {
         tmp[i] = newPolygon2.get(i);
      }
      //If the polygon big enough we will add it
      if((CalculationTool.area(tmp) > 0.04f)) {
         //Add the new polygon and shrink it a little
         newShapes.add(CalculationTool.resizePolygon(tmp,0.99f));
      }

      //Return the new Shapes
      return newShapes;
   }


It has one helper method:

Code: Select all

public static final Vec2[] resizePolygon(Vec2[] vertices, float factor) {
      Vec2[] newVertices = new Vec2[vertices.length];
      
      float oldCircumverance = getCircumverance(vertices);

      float newCircumverance = oldCircumverance * factor;

      float r = newCircumverance / oldCircumverance;
      
      Vec2 centroid = center(vertices);

      Vec2 newVertex;
      for(int i=0;i<vertices.length;i++) {
         newVertex = new Vec2();
         
         newVertex.x = centroid.x + ( (vertices[i].x - centroid.x) * r );
         newVertex.y = centroid.y + ( (vertices[i].y - centroid.y) * r );
         
         newVertices[i] = newVertex;
      }
      
      return newVertices;
   }


Now for the flashlight code:

Code: Select all

public static void drawFlashlight() {
      //Specify the shape of the light
      float angle = Player.get().getActualAngle();
      float arc = (float)Math.PI/4;
      float range = 80.0f;
      
      //Calculate the origin of the light beam
      Vec2 origin = new Vec2();
      origin.x = (float) ((1.0) * Math.cos(angle) + Player.get().getBody().getPosition().x);
      origin.y = (float) ((1.0) * Math.sin(angle) + Player.get().getBody().getPosition().y);
      
      //Draw the light
      drawLight(angle,arc,range,origin);
      
      //To draw circular
//      Vec2 origin = Player.get().getBody().getPosition();
//      for(int i=0;i<8;i++) {
//         angle -= (float)Math.PI/4;
//         drawLight(angle,arc,range,origin);
//      }
   }

   public static void drawLight(float angle, float arc, float range, Vec2 origin) {
      
      //Left and right points of the light
      Vec2 left = new Vec2();
      Vec2 right = new Vec2();
      
      //Calculate left
      left.x = (float) ((range) * Math.cos(angle+(arc/2)) + Player.get().getBody().getPosition().x);
      left.y = (float) ((range) * Math.sin(angle+(arc/2)) + Player.get().getBody().getPosition().y);
      
      //Calculate right
      right.x = (float) ((range) * Math.cos(angle-(arc/2)) + Player.get().getBody().getPosition().x);
      right.y = (float) ((range) * Math.sin(angle-(arc/2)) + Player.get().getBody().getPosition().y);
      
      //Get bounds
      Vec2[] temp = {origin,left,right};
      Vec2 upperBound = CalculationTool.getUpperBound(temp);
      Vec2 lowerBound = CalculationTool.getLowerBound(temp);
      
      //Fill the list with the polygons that are significant
      LinkedList<Vec2[]> polygons = new LinkedList<Vec2[]>();
      for(Wall w : Level.getWorld().getWalls()) {
         Vec2[] polygon = w.getWorldVertices();
         if(CalculationTool.overlap(upperBound, lowerBound, polygon)) {
            polygons.add(polygon);
         }
      }
      
//      //FIXES PAINTING INSIDE SHAPES, people borrowing this code might not need this
//      if(!CalculationTool.isVisible(Player.get().getBody().getPosition(),origin,polygons)) {
//         return;
//      }
      
      //Find out if and where the starting lines intersect
      Vec2 left1 = CalculationTool.getClosestIntersect(origin,left,origin,polygons);
      Vec2 right2 = CalculationTool.getClosestIntersect(origin,right,origin,polygons);      
      
      boolean leftIntersects = false;
      boolean rightIntersects = false;
      
      if(left1 == null) {
         temp[1] = left;
      }
      else {
         temp[1] = left1;
         leftIntersects = true;
      }
      if(right2 == null) {
         temp[2] = right;
      }
      else {
         temp[2] = right2;
         rightIntersects = true;
      }
      
      //Find out if the back of the line intersects the geometry
      ArrayList<Vec2> endLineIntersections = CalculationTool.getIntersections(left, right, polygons);
      
      //Make pairs
      ArrayList<Vec2> allCorners = new ArrayList<Vec2>();
      for(Vec2[] vertices : polygons) {
         for(int i=0;i<vertices.length;i++) {
            allCorners.add(vertices[i]);
         }
      }
      
      //If there are no corners at all which means there can't be change to the light's shape
      if(allCorners.size() == 0) {
         //just draw a simple triangle
         getRenderer().fillPolygon(temp, temp.length, yellow, 40);
         return;
      }
      
      //Array for corner points that should be considered
      Vec2[] correctCorners = new Vec2[allCorners.size()];
      //Intersections from the origin, through the corner with the end line
      Vec2[] cornerEndLineIntersections = new Vec2[allCorners.size()];
      //Closest intersection with geometry from the corner, towards the end line
      Vec2[] cornerClosestIntersections = new Vec2[allCorners.size()];
      
      //End of line point to check intersections with the end line
      Vec2 lineEnd = new Vec2();
      
      int correctCornerCount = 0;
      for(Vec2 corner : allCorners) {
         
         float angleRelative = (float) Math.atan2(corner.y - origin.y,corner.x - origin.x);
         
         lineEnd.x = (float) ((range) * Math.cos(angleRelative) + corner.x);
         lineEnd.y = (float) ((range) * Math.sin(angleRelative) + corner.y);
      
         //Check if this intersects with the end line
         Vec2 intersection = Intersect.solveIntersect(left,right,corner,lineEnd);
         
         //If an intersection was found it mean this corner is inside of the light's shape
         if(intersection != null) {
            cornerEndLineIntersections[correctCornerCount] = intersection;
            correctCorners[correctCornerCount] = corner;
            
            //Check if there are intersections with the geometry from the corner outwards
            Vec2 closestIntersection = CalculationTool.getClosestIntersect(getCloserPoint(corner, intersection, -0.0001f),intersection,corner,polygons);
            if(closestIntersection != null) {
               cornerClosestIntersections[correctCornerCount] = closestIntersection;
            }
            
            correctCornerCount++;
         }
         
      }
      
      //SORT ON BASIS OF DISTANCE OF POINT LEFT
      
      //The number of distances to sort is the cornerEndLines and the other endLine intersections combined
      float[] distances = new float[correctCornerCount+endLineIntersections.size()];

      //Calculate the distances of the cornerEndLineIntersections and add them
      for(int i=0;i<correctCornerCount;i++) {
         distances[i] = CalculationTool.getDistance(left,cornerEndLineIntersections[i]);
      }
      
      int ii = correctCornerCount;
      for(int i=0;i<distances.length-correctCornerCount;i++) {
         distances[ii] = CalculationTool.getDistance(left,endLineIntersections.get(i));
         ii++;
      }
      
      //Final arrays
      Vec2[] backIntersections = new Vec2[distances.length];
      Vec2[] cornerPoints = new Vec2[distances.length];
      Vec2[] closestIntersections = new Vec2[distances.length];
      
      float shortest = Float.MAX_VALUE;
      int index = -1;
      
      for(int i=0;i<distances.length;i++) {
         shortest = Float.MAX_VALUE-100;
         for(ii=0;ii<distances.length;ii++) {
            if(distances[ii] < shortest) {
               index = ii;
               shortest = distances[ii];
            }
         }
         
         if(index < correctCornerCount) {
            backIntersections[i] = cornerEndLineIntersections[index];
            cornerPoints[i] = correctCorners[index];
            closestIntersections[i] = cornerClosestIntersections[index];
      
         }
         else {
            backIntersections[i] = endLineIntersections.get(index-correctCornerCount);       
         }
         
         distances[index] = Float.MAX_VALUE;
      }   
      
      //CREATE FINAL LIGHT
      ArrayList<Vec2> finalLight = new ArrayList<Vec2>();
      finalLight.add(origin);
      
      boolean drawingBack = true;
      
      if(leftIntersects) {
         finalLight.add(left1);
         drawingBack = false;
      }
      else {
         finalLight.add(left);
      }
      
      Vec2 lastBackIntersection = null;
      
      for(int i=0;i<backIntersections.length;i++) {
         if(i!=0) {
            if(backIntersections[i].x == lastBackIntersection.x && backIntersections[i].y == lastBackIntersection.y) {
               continue;
            }
         }
         lastBackIntersection = backIntersections[i];
         
         //When drawing back we look at the endline intersection before looking at the corner
         if(drawingBack) {
            
            //BACK INTERSECTION POINT
            if(CalculationTool.isVisible(getSlightlyOffPoint(getCloserPoint(backIntersections[i],origin,-0.0001f),origin,0.0002f),origin,polygons)) {
               finalLight.add(backIntersections[i]);
            }
         
            //CORNER POINT
            if(cornerPoints[i] != null) {
               if(CalculationTool.isVisible(getCloserPoint(cornerPoints[i],origin,-0.0001f),origin,polygons)) {
                  finalLight.add(cornerPoints[i]);
                  drawingBack = false;
               }
            }

         }
         //if drawingBack == false
         else {
            
            //CORNER POINT
            if(cornerPoints[i] != null) {
               int cases = 0;
               
               //Check if the corner is visible
               if(CalculationTool.isVisible(getCloserPoint(cornerPoints[i],origin,-0.0001f),origin,polygons)) {
                  
                  //If there is a intersection with geometry from the corner outward
                  if(closestIntersections[i] != null) {
                  
                     //Check if we can see it slightly left or right from the point,
                     //which will tell us in which order to paint the points
                     
                     if(CalculationTool.isVisible(getSlightlyOffPoint(getCloserPoint(closestIntersections[i],origin,-0.01f),origin,-0.00004f),origin,polygons)) {
                        cases = 2;
                     }
                     else if(CalculationTool.isVisible(getSlightlyOffPoint(getCloserPoint(closestIntersections[i],origin,-0.01f),origin,0.00004f),origin,polygons)) {
                        cases = 1;
                     }
                     
                  }
                  
                  //Put the points in place according to the sort of case
                  if(cases == 0) {
                     finalLight.add(cornerPoints[i]);
                  }
                  else if(cases == 1) {
                     finalLight.add(closestIntersections[i]);
                     finalLight.add(cornerPoints[i]);
                  }
                  else if(cases == 2) {
                     finalLight.add(cornerPoints[i]);
                     finalLight.add(closestIntersections[i]);
                  }
               }

            }
            
            //BACK INTERSECTION POINT
            if(CalculationTool.isVisible(getSlightlyOffPoint(getCloserPoint(backIntersections[i],origin,-0.0001f),origin,-0.0002f),origin,polygons)) {
               finalLight.add(backIntersections[i]);
               drawingBack = true;
            }
         }
         
      }
      
      //PUT IN THE LAST VERTEX
      if(rightIntersects) {
         finalLight.add(right2);
      }
      else {
         finalLight.add(right);
      }
   
      temp = new Vec2[finalLight.size()];
      for(int i=0;i<finalLight.size();i++) {
         temp[i] = finalLight.get(i);
         
      }

      //Paint the final result
      getRenderer().fillPolygon(temp, temp.length, yellow, 40);
   }


It has two helper methods:

Code: Select all

   public static Vec2 getCloserPoint(Vec2 point, Vec2 towardsPoint, float fraction) {
      Vec2 closerPoint = new Vec2();

      closerPoint.x = ( (point.x - towardsPoint.x) * (fraction) ) + point.x;
      closerPoint.y = ( (point.y - towardsPoint.y) * (fraction) ) + point.y;

      return closerPoint;
   }
   
   public static Vec2 getSlightlyOffPoint(Vec2 point, Vec2 towardsPoint, float offness) {
      float angleRelative = (float) Math.atan2(point.y - towardsPoint.y,point.x - towardsPoint.x);
      
      float distance = CalculationTool.getDistance(point,towardsPoint);
      
      Vec2 offPoint = new Vec2();
      offPoint.x = (float) ((distance) * Math.cos(angleRelative+offness) + towardsPoint.x);
      offPoint.y = (float) ((distance) * Math.sin(angleRelative+offness) + towardsPoint.y);

      return offPoint;
   }


Sorry Im just dumping it without much commentary but I'm in a hurry.


Return to “Java”



Who is online

Users browsing this forum: Baidu [Spider] and 1 guest