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
33package com.jme3.terrain.geomipmap.picking;
34
35import com.jme3.collision.CollisionResult;
36import com.jme3.collision.CollisionResults;
37import com.jme3.math.Ray;
38import com.jme3.math.Triangle;
39import com.jme3.math.Vector2f;
40import com.jme3.math.Vector3f;
41import com.jme3.terrain.geomipmap.TerrainPatch;
42import com.jme3.terrain.geomipmap.TerrainQuad;
43import com.jme3.terrain.geomipmap.picking.BresenhamYUpGridTracer.Direction;
44import java.util.ArrayList;
45import java.util.Collections;
46import 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 */
59public 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