Home | History | Annotate | Download | only in picking 
      1 /*
      2  * Copyright (c) 2009-2010 jMonkeyEngine
      3  * All rights reserved.
      4  *
      5  * Redistribution and use in source and binary forms, with or without
      6  * modification, are permitted provided that the following conditions are
      7  * met:
      8  *
      9  * * Redistributions of source code must retain the above copyright
     10  *   notice, this list of conditions and the following disclaimer.
     11  *
     12  * * Redistributions in binary form must reproduce the above copyright
     13  *   notice, this list of conditions and the following disclaimer in the
     14  *   documentation and/or other materials provided with the distribution.
     15  *
     16  * * Neither the name of 'jMonkeyEngine' nor the names of its contributors
     17  *   may be used to endorse or promote products derived from this software
     18  *   without specific prior written permission.
     19  *
     20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     22  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     23  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
     24  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
     25  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
     26  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
     27  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
     28  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
     29  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
     30  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     31  */
     32 
     33 package com.jme3.terrain.geomipmap.picking;
     34 
     35 import com.jme3.math.Ray;
     36 import com.jme3.math.Vector2f;
     37 import com.jme3.math.Vector3f;
     38 
     39 /**
     40  * Works on the XZ plane, with positive Y as up.
     41  *
     42  * @author Joshua Slack
     43  * @author Brent Owens
     44  */
     45 public class BresenhamYUpGridTracer {
     46 
     47     protected Vector3f gridOrigin = new Vector3f();
     48     protected Vector3f gridSpacing = new Vector3f();
     49     protected Vector2f gridLocation = new Vector2f();
     50     protected Vector3f rayLocation = new Vector3f();
     51     protected Ray walkRay = new Ray();
     52 
     53     protected Direction stepDirection = Direction.None;
     54     protected float rayLength;
     55 
     56     public static enum Direction {
     57         None, PositiveX, NegativeX, PositiveY, NegativeY, PositiveZ, NegativeZ;
     58     };
     59 
     60     // a "near zero" value we will use to determine if the walkRay is
     61     // perpendicular to the grid.
     62     protected static float TOLERANCE = 0.0000001f;
     63 
     64     private int stepXDirection;
     65     private int stepZDirection;
     66 
     67     // from current position along ray
     68     private float distToNextXIntersection, distToNextZIntersection;
     69     private float distBetweenXIntersections, distBetweenZIntersections;
     70 
     71     public void startWalk(final Ray walkRay) {
     72         // store ray
     73         this.walkRay.set(walkRay);
     74 
     75         // simplify access to direction
     76         Vector3f direction = this.walkRay.getDirection();
     77 
     78         // Move start point to grid space
     79         Vector3f start = this.walkRay.getOrigin().subtract(gridOrigin);
     80 
     81         gridLocation.x = (int) (start.x / gridSpacing.x);
     82         gridLocation.y = (int) (start.z / gridSpacing.z);
     83 
     84         Vector3f ooDirection = new Vector3f(1.0f / direction.x, 1,1.0f / direction.z);
     85 
     86         // Check which direction on the X world axis we are moving.
     87         if (direction.x > TOLERANCE) {
     88             distToNextXIntersection = ((gridLocation.x + 1) * gridSpacing.x - start.x) * ooDirection.x;
     89             distBetweenXIntersections = gridSpacing.x * ooDirection.x;
     90             stepXDirection = 1;
     91         } else if (direction.x < -TOLERANCE) {
     92             distToNextXIntersection = (start.x - (gridLocation.x * gridSpacing.x)) * -direction.x;
     93             distBetweenXIntersections = -gridSpacing.x * ooDirection.x;
     94             stepXDirection = -1;
     95         } else {
     96             distToNextXIntersection = Float.MAX_VALUE;
     97             distBetweenXIntersections = Float.MAX_VALUE;
     98             stepXDirection = 0;
     99         }
    100 
    101         // Check which direction on the Z world axis we are moving.
    102         if (direction.z > TOLERANCE) {
    103             distToNextZIntersection = ((gridLocation.y + 1) * gridSpacing.z - start.z) * ooDirection.z;
    104             distBetweenZIntersections = gridSpacing.z * ooDirection.z;
    105             stepZDirection = 1;
    106         } else if (direction.z < -TOLERANCE) {
    107             distToNextZIntersection = (start.z - (gridLocation.y * gridSpacing.z)) * -direction.z;
    108             distBetweenZIntersections = -gridSpacing.z * ooDirection.z;
    109             stepZDirection = -1;
    110         } else {
    111             distToNextZIntersection = Float.MAX_VALUE;
    112             distBetweenZIntersections = Float.MAX_VALUE;
    113             stepZDirection = 0;
    114         }
    115 
    116         // Reset some variables
    117         rayLocation.set(start);
    118         rayLength = 0.0f;
    119         stepDirection = Direction.None;
    120     }
    121 
    122     public void next() {
    123         // Walk us to our next location based on distances to next X or Z grid
    124         // line.
    125         if (distToNextXIntersection < distToNextZIntersection) {
    126             rayLength = distToNextXIntersection;
    127             gridLocation.x += stepXDirection;
    128             distToNextXIntersection += distBetweenXIntersections;
    129             switch (stepXDirection) {
    130             case -1:
    131                 stepDirection = Direction.NegativeX;
    132                 break;
    133             case 0:
    134                 stepDirection = Direction.None;
    135                 break;
    136             case 1:
    137                 stepDirection = Direction.PositiveX;
    138                 break;
    139             }
    140         } else {
    141             rayLength = distToNextZIntersection;
    142             gridLocation.y += stepZDirection;
    143             distToNextZIntersection += distBetweenZIntersections;
    144             switch (stepZDirection) {
    145             case -1:
    146                 stepDirection = Direction.NegativeZ;
    147                 break;
    148             case 0:
    149                 stepDirection = Direction.None;
    150                 break;
    151             case 1:
    152                 stepDirection = Direction.PositiveZ;
    153                 break;
    154             }
    155         }
    156 
    157         rayLocation.set(walkRay.direction).multLocal(rayLength).addLocal(walkRay.origin);
    158     }
    159 
    160     public Direction getLastStepDirection() {
    161         return stepDirection;
    162     }
    163 
    164     public boolean isRayPerpendicularToGrid() {
    165         return stepXDirection == 0 && stepZDirection == 0;
    166     }
    167 
    168 
    169     public Vector2f getGridLocation() {
    170         return gridLocation;
    171     }
    172 
    173     public Vector3f getGridOrigin() {
    174         return gridOrigin;
    175     }
    176 
    177     public Vector3f getGridSpacing() {
    178         return gridSpacing;
    179     }
    180 
    181 
    182     public void setGridLocation(Vector2f gridLocation) {
    183         this.gridLocation = gridLocation;
    184     }
    185 
    186     public void setGridOrigin(Vector3f gridOrigin) {
    187         this.gridOrigin = gridOrigin;
    188     }
    189 
    190     public void setGridSpacing(Vector3f gridSpacing) {
    191         this.gridSpacing = gridSpacing;
    192     }
    193 }
    194