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 startWalk(final Ray walkRay)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 next()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 getLastStepDirection()160 public Direction getLastStepDirection() { 161 return stepDirection; 162 } 163 isRayPerpendicularToGrid()164 public boolean isRayPerpendicularToGrid() { 165 return stepXDirection == 0 && stepZDirection == 0; 166 } 167 168 getGridLocation()169 public Vector2f getGridLocation() { 170 return gridLocation; 171 } 172 getGridOrigin()173 public Vector3f getGridOrigin() { 174 return gridOrigin; 175 } 176 getGridSpacing()177 public Vector3f getGridSpacing() { 178 return gridSpacing; 179 } 180 181 setGridLocation(Vector2f gridLocation)182 public void setGridLocation(Vector2f gridLocation) { 183 this.gridLocation = gridLocation; 184 } 185 setGridOrigin(Vector3f gridOrigin)186 public void setGridOrigin(Vector3f gridOrigin) { 187 this.gridOrigin = gridOrigin; 188 } 189 setGridSpacing(Vector3f gridSpacing)190 public void setGridSpacing(Vector3f gridSpacing) { 191 this.gridSpacing = gridSpacing; 192 } 193 } 194