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.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 
     72     public BresenhamTerrainPicker(TerrainQuad root) {
     73         this.root = root;
     74     }
     75 
     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 
    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      */
    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      */
    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