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.collision.CollisionResult; 36 import com.jme3.collision.CollisionResults; 37 import com.jme3.math.Ray; 38 import com.jme3.math.Triangle; 39 import com.jme3.math.Vector2f; 40 import com.jme3.math.Vector3f; 41 import com.jme3.terrain.geomipmap.TerrainPatch; 42 import com.jme3.terrain.geomipmap.TerrainQuad; 43 import com.jme3.terrain.geomipmap.picking.BresenhamYUpGridTracer.Direction; 44 import java.util.ArrayList; 45 import java.util.Collections; 46 import java.util.List; 47 48 /** 49 * It basically works by casting a pick ray 50 * against the bounding volumes of the TerrainQuad and its children, gathering 51 * all of the TerrainPatches hit (in distance order.) The triangles of each patch 52 * are then tested using the BresenhamYUpGridTracer to determine which triangles 53 * to test and in what order. When a hit is found, it is guaranteed to be the 54 * first such hit and can immediately be returned. 55 * 56 * @author Joshua Slack 57 * @author Brent Owens 58 */ 59 public class BresenhamTerrainPicker implements TerrainPicker { 60 61 private final Triangle gridTriA = new Triangle(new Vector3f(), new Vector3f(), new Vector3f()); 62 private final Triangle gridTriB = new Triangle(new Vector3f(), new Vector3f(), new Vector3f()); 63 64 private final Vector3f calcVec1 = new Vector3f(); 65 private final Ray workRay = new Ray(); 66 private final Ray worldPickRay = new Ray(); 67 68 private final TerrainQuad root; 69 private final BresenhamYUpGridTracer tracer = new BresenhamYUpGridTracer(); 70 71 BresenhamTerrainPicker(TerrainQuad root)72 public BresenhamTerrainPicker(TerrainQuad root) { 73 this.root = root; 74 } 75 getTerrainIntersection(Ray worldPick, CollisionResults results)76 public Vector3f getTerrainIntersection(Ray worldPick, CollisionResults results) { 77 78 worldPickRay.set(worldPick); 79 List<TerrainPickData> pickData = new ArrayList<TerrainPickData>(); 80 root.findPick(worldPick.clone(), pickData); 81 Collections.sort(pickData); 82 83 if (pickData.isEmpty()) 84 return null; 85 86 workRay.set(worldPick); 87 88 for (TerrainPickData pd : pickData) { 89 TerrainPatch patch = pd.targetPatch; 90 91 92 tracer.getGridSpacing().set(patch.getWorldScale()); 93 tracer.setGridOrigin(patch.getWorldTranslation()); 94 95 workRay.getOrigin().set(worldPick.getDirection()).multLocal(pd.cr.getDistance()-.1f).addLocal(worldPick.getOrigin()); 96 97 tracer.startWalk(workRay); 98 99 final Vector3f intersection = new Vector3f(); 100 final Vector2f loc = tracer.getGridLocation(); 101 102 if (tracer.isRayPerpendicularToGrid()) { 103 Triangle hit = new Triangle(); 104 checkTriangles(loc.x, loc.y, workRay, intersection, patch, hit); 105 float distance = worldPickRay.origin.distance(intersection); 106 CollisionResult cr = new CollisionResult(intersection, distance); 107 cr.setGeometry(patch); 108 cr.setContactNormal(hit.getNormal()); 109 results.addCollision(cr); 110 return intersection; 111 } 112 113 114 115 while (loc.x >= -1 && loc.x <= patch.getSize() && 116 loc.y >= -1 && loc.y <= patch.getSize()) { 117 118 //System.out.print(loc.x+","+loc.y+" : "); 119 // check the triangles of main square for intersection. 120 Triangle hit = new Triangle(); 121 if (checkTriangles(loc.x, loc.y, workRay, intersection, patch, hit)) { 122 // we found an intersection, so return that! 123 float distance = worldPickRay.origin.distance(intersection); 124 CollisionResult cr = new CollisionResult(intersection, distance); 125 cr.setGeometry(patch); 126 results.addCollision(cr); 127 cr.setContactNormal(hit.getNormal()); 128 return intersection; 129 } 130 131 // because of how we get our height coords, we will 132 // sometimes be off by a grid spot, so we check the next 133 // grid space up. 134 int dx = 0, dz = 0; 135 Direction d = tracer.getLastStepDirection(); 136 switch (d) { 137 case PositiveX: 138 case NegativeX: 139 dx = 0; 140 dz = 1; 141 break; 142 case PositiveZ: 143 case NegativeZ: 144 dx = 1; 145 dz = 0; 146 break; 147 } 148 149 if (checkTriangles(loc.x + dx, loc.y + dz, workRay, intersection, patch, hit)) { 150 // we found an intersection, so return that! 151 float distance = worldPickRay.origin.distance(intersection); 152 CollisionResult cr = new CollisionResult(intersection, distance); 153 results.addCollision(cr); 154 cr.setGeometry(patch); 155 cr.setContactNormal(hit.getNormal()); 156 return intersection; 157 } 158 159 tracer.next(); 160 } 161 } 162 163 return null; 164 } 165 checkTriangles(float gridX, float gridY, Ray pick, Vector3f intersection, TerrainPatch patch, Triangle store)166 protected boolean checkTriangles(float gridX, float gridY, Ray pick, Vector3f intersection, TerrainPatch patch, Triangle store) { 167 if (!getTriangles(gridX, gridY, patch)) 168 return false; 169 170 if (pick.intersectWhere(gridTriA, intersection)) { 171 store.set(gridTriA.get1(), gridTriA.get2(), gridTriA.get3()); 172 return true; 173 } else { 174 if (pick.intersectWhere(gridTriB, intersection)) { 175 store.set(gridTriB.get1(), gridTriB.get2(), gridTriB.get3()); 176 return true; 177 } 178 } 179 180 return false; 181 } 182 183 /** 184 * Request the triangles (in world coord space) of a TerrainBlock that 185 * correspond to the given grid location. The triangles are stored in the 186 * class fields _gridTriA and _gridTriB. 187 * 188 * @param gridX 189 * grid row 190 * @param gridY 191 * grid column 192 * @param block 193 * the TerrainBlock we are working with 194 * @return true if the grid point is valid for the given block, false if it 195 * is off the block. 196 */ getTriangles(float gridX, float gridY, TerrainPatch patch)197 protected boolean getTriangles(float gridX, float gridY, TerrainPatch patch) { 198 calcVec1.set(gridX, 0, gridY); 199 int index = findClosestHeightIndex(calcVec1, patch); 200 201 if (index == -1) 202 return false; 203 204 Triangle[] t = patch.getGridTriangles(gridX, gridY); 205 if (t == null || t.length == 0) 206 return false; 207 208 gridTriA.set1(t[0].get1()); 209 gridTriA.set2(t[0].get2()); 210 gridTriA.set3(t[0].get3()); 211 212 gridTriB.set1(t[1].get1()); 213 gridTriB.set2(t[1].get2()); 214 gridTriB.set3(t[1].get3()); 215 216 return true; 217 } 218 219 /** 220 * Finds the closest height point to a position. Will always be left/above 221 * that position. 222 * 223 * @param position 224 * the position to check at 225 * @param block 226 * the block to get height values from 227 * @return an index to the height position of the given block. 228 */ findClosestHeightIndex(Vector3f position, TerrainPatch patch)229 protected int findClosestHeightIndex(Vector3f position, TerrainPatch patch) { 230 231 int x = (int) position.x; 232 int z = (int) position.z; 233 234 if (x < 0 || x >= patch.getSize() - 1) { 235 return -1; 236 } 237 if (z < 0 || z >= patch.getSize() - 1) { 238 return -1; 239 } 240 241 return z * patch.getSize() + x; 242 } 243 } 244