Add generic support for picking via raycast intersection and AABBox (or similar)

- New simple type Ray, denominating a .. ray

- Added PMVMatrix.gluUnProjectRay(..) similar to gluUnproject(..)
  however, result is a Ray.

- Added AABBox.intersectsRay(Ray) ..

5 files changed, 190 insertions, 25 deletions

diff --git a/src/jogl/classes/com/jogamp/graph/geom/Triangle.java b/src/jogl/classes/com/jogamp/graph/geom/Triangle.java
index 593d9cb24..de629dfc4 100644
--- a/src/jogl/classes/com/jogamp/graph/geom/Triangle.java
+++ b/src/jogl/classes/com/jogamp/graph/geom/Triangle.java
@@ -27,8 +27,6 @@
  */
 package com.jogamp.graph.geom;
 
-import com.jogamp.graph.curve.Region;
-
 import jogamp.graph.geom.plane.AffineTransform;
 
 public class Triangle {
diff --git a/src/jogl/classes/com/jogamp/opengl/math/Ray.java b/src/jogl/classes/com/jogamp/opengl/math/Ray.java
new file mode 100644
index 000000000..3fe7dd3b1
--- /dev/null
+++ b/src/jogl/classes/com/jogamp/opengl/math/Ray.java
@@ -0,0 +1,57 @@
+/**
+ * Copyright 2014 JogAmp Community. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification, are
+ * permitted provided that the following conditions are met:
+ *
+ *    1. Redistributions of source code must retain the above copyright notice, this list of
+ *       conditions and the following disclaimer.
+ *
+ *    2. Redistributions in binary form must reproduce the above copyright notice, this list
+ *       of conditions and the following disclaimer in the documentation and/or other materials
+ *       provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY JogAmp Community ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
+ * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JogAmp Community OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * The views and conclusions contained in the software and documentation are those of the
+ * authors and should not be interpreted as representing official policies, either expressed
+ * or implied, of JogAmp Community.
+ */
+package com.jogamp.opengl.math;
+
+import com.jogamp.opengl.math.geom.AABBox;
+
+/**
+ * Simple compound denoting a ray.
+ * <p>
+ * A ray, also known as a half line, consists out of it's <i>origin</i>
+ * and <i>direction</i>. Hence it is bound to only the <i>origin</i> side,
+ * where the other end is +infinitive.
+ * <pre>
+ * R(t) = R0 + Rd * t with R0 origin, Rd direction and t > 0.0
+ * </pre>
+ * </p>
+ * <p>
+ * A {@link Ray} maybe used for <i>picking</i>
+ * using a {@link AABBox#intersectsRay(Ray, float[]) bounding box}.
+ * </p>
+ */
+public class Ray {
+    /** Origin of Ray, float[3]. */
+    public final float[] orig = new float[3];
+
+    /** Normalized direction vector of ray, float[3]. */
+    public final float[] dir = new float[3];
+
+    public String toString() {
+        return "Ray[orig["+orig[0]+", "+orig[1]+", "+orig[2]+"], dir["+dir[0]+", "+dir[1]+", "+dir[2]+"]]";
+    }
+}
\ No newline at end of file
diff --git a/src/jogl/classes/com/jogamp/opengl/math/VectorUtil.java b/src/jogl/classes/com/jogamp/opengl/math/VectorUtil.java
index 778c17a53..3aaed2032 100644
--- a/src/jogl/classes/com/jogamp/opengl/math/VectorUtil.java
+++ b/src/jogl/classes/com/jogamp/opengl/math/VectorUtil.java
@@ -601,14 +601,16 @@ public class VectorUtil {
         return result;
     }
 
-    /** Compute intersection between two segments
+    /**
+     * Compute intersection between two segments
      * @param a vertex 1 of first segment
      * @param b vertex 2 of first segment
      * @param c vertex 1 of second segment
      * @param d vertex 2 of second segment
      * @return true if the segments intersect, otherwise returns false
      */
-    public static boolean testSeg2SegIntersection(final Vert2fImmutable a, final Vert2fImmutable b, final Vert2fImmutable c, final Vert2fImmutable d) {
+    public static boolean testSeg2SegIntersection(final Vert2fImmutable a, final Vert2fImmutable b,
+                                                  final Vert2fImmutable c, final Vert2fImmutable d) {
         final float[] A = a.getCoord();
         final float[] B = b.getCoord();
         final float[] C = c.getCoord();
diff --git a/src/jogl/classes/com/jogamp/opengl/math/geom/AABBox.java b/src/jogl/classes/com/jogamp/opengl/math/geom/AABBox.java
index 3be8a77f8..8a18ea4c4 100644
--- a/src/jogl/classes/com/jogamp/opengl/math/geom/AABBox.java
+++ b/src/jogl/classes/com/jogamp/opengl/math/geom/AABBox.java
@@ -30,6 +30,7 @@ package com.jogamp.opengl.math.geom;
 import jogamp.graph.geom.plane.AffineTransform;
 
 import com.jogamp.opengl.math.FloatUtil;
+import com.jogamp.opengl.math.Ray;
 import com.jogamp.opengl.math.VectorUtil;
 import com.jogamp.opengl.util.PMVMatrix;
 
@@ -38,6 +39,15 @@ import com.jogamp.opengl.util.PMVMatrix;
  * Axis Aligned Bounding Box. Defined by two 3D coordinates (low and high)
  * The low being the the lower left corner of the box, and the high being the upper
  * right corner of the box.
+ * <p>
+ * A few references for collision detection, intersections:
+ * <pre>
+ * http://www.realtimerendering.com/intersections.html
+ * http://www.codercorner.com/RayAABB.cpp
+ * http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter0.htm
+ * http://realtimecollisiondetection.net/files/levine_swept_sat.txt
+ * </pre>
+ * </p>
  *
  */
 public class AABBox implements Cloneable {
@@ -294,7 +304,7 @@ public class AABBox implements Cloneable {
      * @param h hight
      * @return true if this AABBox might have a common region with this 2D region
      */
-    public final boolean intersects(final float x, final float y, final float w, final float h) {
+    public final boolean intersects2DRegion(final float x, final float y, final float w, final float h) {
         if (w <= 0 || h <= 0) {
             return false;
         }
@@ -313,6 +323,56 @@ public class AABBox implements Cloneable {
                 y < y0 + _h);
     }
 
+    /**
+     * Check if {@link Ray} intersects this bounding box.
+     * <p>
+     * Versions uses the SAT[1], testing 6 axes.
+     * Original code for OBBs from MAGIC.
+     * Rewritten for AABBs and reorganized for early exits[2].
+     * </p>
+     * <pre>
+     * [1] SAT = Separating Axis Theorem
+     * [2] http://www.codercorner.com/RayAABB.cpp
+     * </pre>
+     * @param ray
+     * @return
+     */
+    public final boolean intersectsRay(final Ray ray) {
+        // diff[XYZ] -> VectorUtil.subVec3(diff, ray.orig, center);
+        //  ext[XYZ] -> extend VectorUtil.subVec3(ext, high, center);
+
+        final float dirX  = ray.dir[0];
+        final float diffX = ray.orig[0] - center[0];
+        final float extX  = high[0] - center[0];
+        if( Math.abs(diffX) > extX && diffX*dirX >= 0f ) return false;
+
+        final float dirY  = ray.dir[1];
+        final float diffY = ray.orig[1] - center[1];
+        final float extY  = high[1] - center[1];
+        if( Math.abs(diffY) > extY && diffY*dirY >= 0f ) return false;
+
+        final float dirZ  = ray.dir[2];
+        final float diffZ = ray.orig[2] - center[2];
+        final float extZ  = high[2] - center[2];
+        if( Math.abs(diffZ) > extZ && diffZ*dirZ >= 0f ) return false;
+
+        final float absDirY = Math.abs(dirY);
+        final float absDirZ = Math.abs(dirZ);
+
+        float f = dirY * diffZ - dirZ * diffY;
+        if( Math.abs(f) > extY*absDirZ + extZ*absDirY ) return false;
+
+        final float absDirX = Math.abs(dirX);
+
+        f = dirZ * diffX - dirX * diffZ;
+        if( Math.abs(f) > extX*absDirZ + extZ*absDirX ) return false;
+
+        f = dirX * diffY - dirY * diffX;
+        if( Math.abs(f) > extX*absDirY + extY*absDirX ) return false;
+
+        return true;
+    }
+
 
     /** Get the size of the Box where the size is represented by the
      * length of the vector between low and high.
@@ -399,7 +459,7 @@ public class AABBox implements Cloneable {
         if( null == obj || !(obj instanceof AABBox) ) {
             return false;
         }
-        final AABBox other = (AABBox) obj;        
+        final AABBox other = (AABBox) obj;
         return VectorUtil.isVec2Equal(low, 0, other.low, 0, FloatUtil.EPSILON) &&
                VectorUtil.isVec3Equal(high, 0, other.high, 0, FloatUtil.EPSILON) ;
     }
diff --git a/src/jogl/classes/com/jogamp/opengl/util/PMVMatrix.java b/src/jogl/classes/com/jogamp/opengl/util/PMVMatrix.java
index 6db726b01..44288256a 100644
--- a/src/jogl/classes/com/jogamp/opengl/util/PMVMatrix.java
+++ b/src/jogl/classes/com/jogamp/opengl/util/PMVMatrix.java
@@ -49,6 +49,9 @@ import com.jogamp.common.os.Platform;
 import com.jogamp.common.util.FloatStack;
 import com.jogamp.opengl.math.FloatUtil;
 import com.jogamp.opengl.math.Quaternion;
+import com.jogamp.opengl.math.Ray;
+import com.jogamp.opengl.math.VectorUtil;
+import com.jogamp.opengl.math.geom.AABBox;
 import com.jogamp.opengl.math.geom.Frustum;
 
 /**
@@ -453,7 +456,7 @@ public class PMVMatrix implements GLMatrixFunc {
     }
 
     @Override
-    public final void glGetFloatv(int matrixGetName, FloatBuffer params) {
+    public final void glGetFloatv(final int matrixGetName, final FloatBuffer params) {
         int pos = params.position();
         if(matrixGetName==GL_MATRIX_MODE) {
             params.put(matrixMode);
@@ -466,7 +469,7 @@ public class PMVMatrix implements GLMatrixFunc {
     }
 
     @Override
-    public final void glGetFloatv(int matrixGetName, float[] params, int params_offset) {
+    public final void glGetFloatv(final int matrixGetName, float[] params, final int params_offset) {
         if(matrixGetName==GL_MATRIX_MODE) {
             params[params_offset]=matrixMode;
         } else {
@@ -477,7 +480,7 @@ public class PMVMatrix implements GLMatrixFunc {
     }
 
     @Override
-    public final void glGetIntegerv(int pname, IntBuffer params) {
+    public final void glGetIntegerv(final int pname, final IntBuffer params) {
         int pos = params.position();
         if(pname==GL_MATRIX_MODE) {
             params.put(matrixMode);
@@ -488,7 +491,7 @@ public class PMVMatrix implements GLMatrixFunc {
     }
 
     @Override
-    public final void glGetIntegerv(int pname, int[] params, int params_offset) {
+    public final void glGetIntegerv(final int pname, final int[] params, final int params_offset) {
         if(pname==GL_MATRIX_MODE) {
             params[params_offset]=matrixMode;
         } else {
@@ -516,7 +519,7 @@ public class PMVMatrix implements GLMatrixFunc {
     }
 
     @Override
-    public final void glLoadMatrixf(java.nio.FloatBuffer m) {
+    public final void glLoadMatrixf(final java.nio.FloatBuffer m) {
         int spos = m.position();
         if(matrixMode==GL_MODELVIEW) {
             matrixMv.put(m);
@@ -624,7 +627,7 @@ public class PMVMatrix implements GLMatrixFunc {
     }
 
     @Override
-    public final void glMultMatrixf(float[] m, int m_offset) {
+    public final void glMultMatrixf(final float[] m, final int m_offset) {
         if(matrixMode==GL_MODELVIEW) {
             FloatUtil.multMatrixf(matrixMv, m, m_offset);
             dirtyBits |= DIRTY_INVERSE_MODELVIEW | DIRTY_INVERSE_TRANSPOSED_MODELVIEW | DIRTY_FRUSTUM ;
@@ -759,9 +762,9 @@ public class PMVMatrix implements GLMatrixFunc {
      * {@link #glMultMatrixf(FloatBuffer) Multiply} and {@link #glTranslatef(float, float, float) translate} the {@link #glGetMatrixMode() current matrix}
      * with the eye, object and orientation.
      */
-    public final void gluLookAt(float eyex, float eyey, float eyez,
-                          float centerx, float centery, float centerz,
-                          float upx, float upy, float upz) {
+    public final void gluLookAt(final float eyex, final float eyey, final float eyez,
+                                final float centerx, final float centery, final float centerz,
+                                final float upx, final float upy, final float upz) {
         projectFloat.gluLookAt(this, eyex, eyey, eyez, centerx, centery, centerz, upx, upy, upz);
     }
 
@@ -777,9 +780,9 @@ public class PMVMatrix implements GLMatrixFunc {
      * @param win_pos_offset
      * @return
      */
-    public final boolean gluProject(float objx, float objy, float objz,
-                            int[] viewport, int viewport_offset,
-                            float[] win_pos, int win_pos_offset ) {
+    public final boolean gluProject(final float objx, final float objy, final float objz,
+                                    final int[] viewport, final int viewport_offset,
+                                    final float[] win_pos, final int win_pos_offset ) {
         if(usesBackingArray) {
             return projectFloat.gluProject(objx, objy, objz,
                                            matrixMv.array(), matrixMv.position(),
@@ -805,11 +808,11 @@ public class PMVMatrix implements GLMatrixFunc {
      * @param viewport_offset
      * @param obj_pos
      * @param obj_pos_offset
-     * @return
+     * @return true if successful, otherwise false (failed to invert matrix, or becomes z is infinity)
      */
-    public final boolean gluUnProject(float winx, float winy, float winz,
-                                      int[] viewport, int viewport_offset,
-                                      float[] obj_pos, int obj_pos_offset) {
+    public final boolean gluUnProject(final float winx, final float winy, final float winz,
+                                      final int[] viewport, final int viewport_offset,
+                                      final float[] obj_pos, final int obj_pos_offset) {
         if(usesBackingArray) {
             return projectFloat.gluUnProject(winx, winy, winz,
                                              matrixMv.array(), matrixMv.position(),
@@ -825,12 +828,57 @@ public class PMVMatrix implements GLMatrixFunc {
         }
     }
 
-    public final void gluPickMatrix(float x, float y,
-                              float deltaX, float deltaY,
-                              int[] viewport, int viewport_offset) {
+    public final void gluPickMatrix(final float x, final float y,
+                                    final float deltaX, final float deltaY,
+                                    final int[] viewport, final int viewport_offset) {
         projectFloat.gluPickMatrix(this, x, y, deltaX, deltaY, viewport, viewport_offset);
     }
 
+    /**
+     * Map two window coordinates w/ shared X/Y and distinctive Z
+     * to a {@link Ray}. The resulting {@link Ray} maybe used for <i>picking</i>
+     * using a {@link AABBox#intersectsRay(Ray, float[]) bounding box}.
+     * <p>
+     * Notes for picking <i>winz0</i> and <i>winz1</i>:
+     * </p>
+     * <p>
+     * <a href="http://www.sjbaker.org/steve/omniv/love_your_z_buffer.html">Love Your Z-Buffer</a>
+     * <pre>
+     *  delta = z * z / ( zNear * (1&lt;&lt;N) - z )
+     *
+     *  Where:
+     *    N     = number of bits of Z precision
+     *    zNear = distance from eye to near clip plane
+     *    z     = distance from the eye to the object
+     *    delta = the smallest resolvable Z separation at this range.
+     * </pre>
+     * Another equation to determine winZ for 'orthoDist' > 0
+     * <pre>
+     *  winZ = (1f/zNear-1f/orthoDist)/(1f/zNear-1f/zFar);
+     * </pre>
+     * </p>
+     *
+     * @param winx
+     * @param winy
+     * @param winz0
+     * @param winz1
+     * @param viewport
+     * @param viewport_offset
+     * @param ray storage for the resulting {@link Ray}
+     * @return true if successful, otherwise false (failed to invert matrix, or becomes z is infinity)
+     */
+    public final boolean gluUnProjectRay(final float winx, final float winy, final float winz0, final float winz1,
+                                         final int[] viewport, final int viewport_offset,
+                                         final Ray ray) {
+        if( gluUnProject(winx, winy, winz0, viewport, viewport_offset, ray.orig, 0) &&
+            gluUnProject(winx, winy, winz1, viewport, viewport_offset, ray.dir, 0) ) {
+            VectorUtil.normalizeVec3( VectorUtil.subVec3(ray.dir, ray.dir, ray.orig) );
+            return true;
+        } else {
+            return false;
+        }
+    }
+
     public StringBuilder toString(StringBuilder sb, String f) {
         if(null == sb) {
             sb = new StringBuilder();