Changeset 314 for trunk

Timestamp:

10/10/05 04:49:10 (19 years ago)

Author:

mattausch

Message:

added ray intersection for polygons

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• Polygon3.cpp (modified) (2 diffs)
• Polygon3.h (modified) (2 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -4 +4 @@
 #include "Mesh.h"
 #include "AxisAlignedBox3.h"
+#include "Ray.h"
 
 Polygon3::Polygon3(): mMaterial(NULL), mParent(NULL)
@@ -234 +235 @@
                 box.Include(*(*it));
 }
+
+// int_lineseg returns 1 if the given line segment intersects a 2D
+// ray travelling in the positive X direction.  This is used in the
+// Jordan curve computation for polygon intersection.
+inline int
+int_lineseg(float px,
+            float py,
+            float u1,
+            float v1,
+            float u2,
+            float v2)
+{
+        float t;
+        float ydiff;
+
+        u1 -= px; u2 -= px;       // translate line
+        v1 -= py; v2 -= py;
+
+        if ((v1 > 0 && v2 > 0) ||
+                (v1 < 0 && v2 < 0) ||
+                (u1 < 0 && u2 < 0))
+        return 0;
+
+        if (u1 > 0 && u2 > 0)
+        return 1;
+
+        ydiff = v2 - v1;
+
+        if (fabs(ydiff) < Limits::Small) 
+        {         // denominator near 0
+                if (((fabs(v1) > Limits::Small) || (u1 > 0) || (u2 > 0)))
+                        return 0;
+                return 1;
+        }
+
+        t = -v1 / ydiff;                  // Compute parameter
+
+        return (u1 + t * (u2 - u1)) > 0;
+}
+
+int Polygon3::CastRay(const Ray &ray, float &t, const float nearestT)
+{
+        Plane3 plane = GetSupportingPlane();
+        float dot = DotProd(plane.mNormal, ray.GetDir());
+
+        // Watch for near-zero denominator
+        // ONLY single sided polygons!!!!!
+        if (dot > -Limits::Small)
+        //  if (fabs(dot) < Limits::Small)
+        return Ray::NO_INTERSECTION;
+
+        t = (-plane.mD - DotProd(plane.mNormal, ray.GetLoc())) / dot;
+
+        if (t <= Limits::Small)
+        return Ray::INTERSECTION_OUT_OF_LIMITS;
+
+        if (t >= nearestT) {
+        return Ray::INTERSECTION_OUT_OF_LIMITS; // no intersection was found
+        }
+
+        int count = 0;
+        float u, v, u1, v1, u2, v2;
+        int i;
+
+        int paxis = plane.mNormal.DrivingAxis();
+
+        // Project the intersection point onto the coordinate plane
+        // specified by which.
+        ray.Extrap(t).ExtractVerts(&u, &v, paxis);
+
+        int size = (int)mVertices.size();
+
+        mVertices.back().ExtractVerts(&u1, &v1, paxis );
+
+        if (0 && size <= 4) 
+        {
+                // assume a convex face
+                for (i = 0; i < size; i++) 
+                {
+                mVertices[i].ExtractVerts(&u2, &v2, paxis);
+            
+                        // line u1, v1, u2, v2
+            
+                        if ((v2 - v1)*(u1 - u) > (u2 - u1)*(v1 - v))
+                                return Ray::NO_INTERSECTION;
+
+                        u1 = u2;
+                        v1 = v2;
+        }
+
+        return Ray::INTERSECTION;
+        }
+
+        // We're stuck with the Jordan curve computation.  Count number
+        // of intersections between the line segments the polygon comprises
+        // with a ray originating at the point of intersection and
+        // travelling in the positive X direction.
+        for (i = 0; i < size; i++) 
+        {
+                mVertices[i].ExtractVerts(&u2, &v2, paxis);
+
+                count += (int_lineseg(u, v, u1, v1, u2, v2) != 0);
+
+                u1 = u2;
+                v1 = v2;
+        }
+
+        // We hit polygon if number of intersections is odd.
+        return (count & 1) ? Ray::INTERSECTION : Ray::NO_INTERSECTION;
+}
+

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h

@@ -15 +15 @@
 class Intersectable;
 class AxisAlignedBox3;
+class Ray;
 //typedef Vertex3 Vector3;
 
@@ -81 +82 @@
         static void IncludeInBox(const PolygonContainer &polys, AxisAlignedBox3 &box);
 
+        /** Casts ray to polygon.
+        */
+        int CastRay(const Ray &ray, float &t, const float nearestT);
+
         /// vertices are connected in counterclockwise order.
         VertexContainer mVertices;