Menu
▾
▴
SF.net SVN: quesa:[3347] trunk/quesa
|
From: <jww...@us...> - 2016-09-27 17:06:34
|
Revision: 3347
http://sourceforge.net/p/quesa/code/3347
Author: jwwalker
Date: 2016-09-27 17:06:31 +0000 (Tue, 27 Sep 2016)
Log Message:
-----------
Implemented face tolerance when picking 2D geometry with window point or world ray picks.
Modified Paths:
--------------
trunk/quesa/Development/Source/Core/Geometry/E3GeometryTriMesh.c
trunk/quesa/Development/Source/Core/Geometry/E3GeometryTriangle.c
trunk/quesa/Development/Source/Core/Glue/QD3DMath.c
trunk/quesa/Development/Source/Core/Glue/QD3DPick.c
trunk/quesa/Development/Source/Core/System/E3Math.c
trunk/quesa/Development/Source/Core/System/E3Math_Intersect.cpp
trunk/quesa/Development/Source/Core/System/E3Math_Intersect.h
trunk/quesa/Development/Source/Core/System/E3Pick.c
trunk/quesa/Development/Source/Core/System/E3Pick.h
trunk/quesa/Development/Source/Core/System/E3View.c
trunk/quesa/SDK/Includes/Quesa/QuesaMathOperators.hpp
trunk/quesa/SDK/Includes/Quesa/QuesaPick.h
Modified: trunk/quesa/Development/Source/Core/Geometry/E3GeometryTriMesh.c
===================================================================
--- trunk/quesa/Development/Source/Core/Geometry/E3GeometryTriMesh.c 2016-08-09 23:40:33 UTC (rev 3346)
+++ trunk/quesa/Development/Source/Core/Geometry/E3GeometryTriMesh.c 2016-09-27 17:06:31 UTC (rev 3347)
@@ -5,7 +5,7 @@
Implementation of Quesa Pixmap Marker geometry class.
COPYRIGHT:
- Copyright (c) 1999-2014, Quesa Developers. All rights reserved.
+ Copyright (c) 1999-2016, Quesa Developers. All rights reserved.
For the current release of Quesa, please see:
@@ -52,6 +52,7 @@
#include "E3Geometry.h"
#include "E3GeometryTriMesh.h"
#include "E3ErrorManager.h"
+#include "QuesaMathOperators.hpp"
@@ -951,10 +952,10 @@
// e3geom_trimesh_pick_with_ray : TriMesh ray picking method.
//-----------------------------------------------------------------------------
static TQ3Status
-e3geom_trimesh_pick_with_ray(TQ3ViewObject theView,
+e3geom_trimesh_pick_with_ray( TQ3ViewObject theView,
TQ3PickObject thePick,
const TQ3Ray3D *theRay,
- const TQ3TriMeshData *geomData)
+ const TQ3TriMeshData *geomData )
{ TQ3Uns32 n, numPoints, v0, v1, v2;
TQ3Boolean haveUV, cullBackface;
TQ3Param2D hitUV, *resultUV;
@@ -965,10 +966,90 @@
TQ3Vector3D hitNormal;
TQ3Point3D hitXYZ;
TQ3Param3D theHit;
+ TQ3BoundingBox worldBounds;
+
- // Transform our points
+ // Check for face tolerance
+ float faceTolerance;
+ E3Pick_GetFaceTolerance( thePick, &faceTolerance );
+ float toleranceSquared = faceTolerance * faceTolerance;
+ bool useTolerance = toleranceSquared > kQ3RealZero;
+
+
+ // In case we are using face tolerance, find out whether we are doing a
+ // window point pick.
+ bool isWindowPointPick = (E3Pick_GetType( thePick ) == kQ3PickTypeWindowPoint);
+
+
+ // If using tolerance in window space, we will need to transform from
+ // world to window space.
+ TQ3Matrix4x4 worldToWindow;
+ if ( useTolerance && isWindowPointPick )
+ {
+ TQ3Matrix4x4 worldToFrustum, frustumToWindow;
+ E3View_GetWorldToFrustumMatrixState( theView, &worldToFrustum );
+ E3View_GetFrustumToWindowMatrixState( theView, &frustumToWindow );
+ worldToWindow = worldToFrustum * frustumToWindow;
+ }
+
+
+ // Test whether the ray hits the bounding box, as a first approximation.
+ const TQ3Matrix4x4* localToWorld = E3View_State_GetMatrixLocalToWorld(theView);
+ if (useTolerance)
+ {
+ if (isWindowPointPick)
+ {
+ TQ3Matrix4x4 localToWindow = *localToWorld * worldToWindow;
+ TQ3BoundingBox windowBounds;
+ E3BoundingBox_Transform( &geomData->bBox, &localToWindow, &windowBounds );
+ // Expand window bounds by tolerance in x and y directions.
+ windowBounds.min.x -= faceTolerance;
+ windowBounds.min.y -= faceTolerance;
+ windowBounds.max.x += faceTolerance;
+ windowBounds.max.y += faceTolerance;
+ // Get the original window point from the pick.
+ TQ3Point2D pickPt;
+ E3WindowPointPick_GetPoint( thePick, &pickPt );
+ // If the pick point is outside the window bounds, we know it is a miss.
+ if ( (pickPt.x < windowBounds.min.x) ||
+ (pickPt.x > windowBounds.max.x) ||
+ (pickPt.y < windowBounds.min.y) ||
+ (pickPt.y > windowBounds.max.y) )
+ {
+ return kQ3Success;
+ }
+ }
+ else // world space test
+ {
+ E3BoundingBox_Transform( &geomData->bBox, localToWorld, &worldBounds );
+ // expand world bounds by tolerance in each direction.
+ worldBounds.min.x -= faceTolerance;
+ worldBounds.min.y -= faceTolerance;
+ worldBounds.min.z -= faceTolerance;
+ worldBounds.max.x += faceTolerance;
+ worldBounds.max.y += faceTolerance;
+ worldBounds.max.z += faceTolerance;
+ if (! E3Ray3D_IntersectBoundingBox( theRay, &worldBounds, NULL ))
+ {
+ // The ray misses the bounds, so it misses the mesh.
+ return kQ3Success;
+ }
+ }
+ }
+ else // no tolerance to worry about, look for exact hit in world space
+ {
+ E3BoundingBox_Transform( &geomData->bBox, localToWorld, &worldBounds );
+ if (! E3Ray3D_IntersectBoundingBox( theRay, &worldBounds, NULL ))
+ {
+ // The ray misses the bounds, so it misses the mesh.
+ return kQ3Success;
+ }
+ }
+
+
+ // Transform our points from local to world coordinates
numPoints = geomData->numPoints;
worldPoints = (TQ3Point3D *) Q3Memory_Allocate(static_cast<TQ3Uns32>(numPoints * sizeof(TQ3Point3D)));
if (worldPoints == NULL)
@@ -993,8 +1074,8 @@
//
// Note we do not use any vertex/edge tolerances supplied for the pick, since
// QD3D's blue book appears to suggest neither are used for triangles.
- for (n = 0; n < geomData->numTriangles && qd3dStatus == kQ3Success; n++)
- {
+ for (n = 0; n < geomData->numTriangles && qd3dStatus == kQ3Success; ++n)
+ {
// Grab the vertex indicies
v0 = geomData->triangles[n].pointIndices[0];
v1 = geomData->triangles[n].pointIndices[1];
@@ -1003,21 +1084,56 @@
Q3_ASSERT(v1 >= 0 && v1 < geomData->numPoints);
Q3_ASSERT(v2 >= 0 && v2 < geomData->numPoints);
+ // For convenience, name the 3 world-space corners of the triangle
+ const TQ3Point3D& p0( worldPoints[v0] );
+ const TQ3Point3D& p1( worldPoints[v1] );
+ const TQ3Point3D& p2( worldPoints[v2] );
-
// Pick the triangle
- if (E3Ray3D_IntersectTriangle(theRay, &worldPoints[v0], &worldPoints[v1], &worldPoints[v2], cullBackface, &theHit))
+ TQ3Boolean didHit = kQ3False;
+ if (useTolerance)
+ {
+ if (E3Ray3D_NearTriangle( *theRay,
+ p0, p1, p2, cullBackface, theHit ))
{
+ TQ3Point3D triNearPt = (1.0f - theHit.u - theHit.v) * p0 +
+ theHit.u * p1 + theHit.v * p2;
+ TQ3Point3D rayNearPt = theRay->origin + theHit.w * theRay->direction;
+
+ if (isWindowPointPick)
+ {
+ TQ3Point3D triNearWin = triNearPt * worldToWindow;
+ TQ3Point3D rayNearWin = rayNearPt * worldToWindow;
+ triNearWin.z = rayNearWin.z = 0.0f;
+ float winDistSq = Q3LengthSquared3D( triNearWin - rayNearWin );
+ didHit = (winDistSq < toleranceSquared)? kQ3True : kQ3False;
+ }
+ else
+ {
+ float worldDistSq = Q3LengthSquared3D( rayNearPt - triNearPt );
+ didHit = (worldDistSq < toleranceSquared)? kQ3True : kQ3False;
+ }
+ }
+ }
+ else // require exact hits
+ {
+ didHit = E3Ray3D_IntersectTriangle( *theRay,
+ p0, p1, p2, cullBackface, theHit );
+ }
+
+ if (didHit)
+ {
// Create the triangle, and update the vertices to the transformed coordinates
e3geom_trimesh_triangle_new(theView, geomData, n, &worldTriangle);
- worldTriangle.vertices[0].point = worldPoints[v0];
- worldTriangle.vertices[1].point = worldPoints[v1];
- worldTriangle.vertices[2].point = worldPoints[v2];
+ worldTriangle.vertices[0].point = p0;
+ worldTriangle.vertices[1].point = p1;
+ worldTriangle.vertices[2].point = p2;
// Obtain the XYZ, normal, and UV for the hit point. We always return an
// XYZ and normal for the hit, however we need to cope with missing UVs.
- E3Triangle_InterpolateHit(theView,&worldTriangle, &theHit, &hitXYZ, &hitNormal, &hitUV, &haveUV);
+ E3Triangle_InterpolateHit(theView,&worldTriangle, &theHit,
+ &hitXYZ, &hitNormal, &hitUV, &haveUV);
resultUV = (haveUV ? &hitUV : NULL);
@@ -1028,11 +1144,10 @@
// Clean up
e3geom_trimesh_triangle_delete(&worldTriangle);
- }
}
+ }
-
// Clean up
Q3Memory_Free(&worldPoints);
@@ -1246,35 +1361,16 @@
//-----------------------------------------------------------------------------
static TQ3Status
e3geom_trimesh_pick_window_point(TQ3ViewObject theView, TQ3PickObject thePick, const TQ3TriMeshData *geomData)
-{ TQ3BoundingBox worldBounds;
- TQ3Point3D corners[8];
+{
TQ3Status qd3dStatus;
- TQ3WindowPointPickData pickData;
TQ3Ray3D theRay;
- // Get the pick data
- Q3WindowPointPick_GetData(thePick, &pickData);
-
-
-
- // Calculate the world-coordinate bounding box
- E3BoundingBox_Transform( &geomData->bBox,
- E3View_State_GetMatrixLocalToWorld(theView),
- &worldBounds );
- E3BoundingBox_GetCorners( &geomData->bBox, corners );
-
-
-
- // See if the pick ray falls within our bounding box
- //
- // If it does, we proceed to the actual triangle-level hit test.
E3View_GetRayThroughPickPoint(theView, &theRay);
- if (E3Ray3D_IntersectBoundingBox(&theRay, &worldBounds, NULL))
- qd3dStatus = e3geom_trimesh_pick_with_ray(theView, thePick, &theRay, geomData);
- else
- qd3dStatus = kQ3Success;
+
+ qd3dStatus = e3geom_trimesh_pick_with_ray( theView, thePick, &theRay,
+ geomData );
return(qd3dStatus);
}
@@ -1343,41 +1439,20 @@
static TQ3Status
e3geom_trimesh_pick_world_ray(TQ3ViewObject theView, TQ3PickObject thePick, const TQ3TriMeshData *geomData)
{
- TQ3BoundingBox worldBounds;
TQ3Status qd3dStatus;
- TQ3WorldRayPickData pickData;
- TQ3Point3D hitHYZ;
+ TQ3Ray3D pickRay;
// Get the pick data
- Q3WorldRayPick_GetData(thePick, &pickData);
+ E3WorldRayPick_GetRay(thePick, &pickRay);
- // Calculate the bounding box
- //
- // To get an exact bounding box, we'd have to transform all the points and then
- // use Q3BoundingBox_SetFromPoints3D, but that seems too much work for present
- // purposes.
- //
- // As a cheaper alternative we find the 8 corners of the local bounding box,
- // transform them, and then find the bounding box of those points.
- //
- // Note that simply transforming the min and max corners of the local bounding
- // box would be incorrect.
- E3BoundingBox_Transform( &geomData->bBox,
- E3View_State_GetMatrixLocalToWorld(theView),
- &worldBounds );
+ qd3dStatus = e3geom_trimesh_pick_with_ray( theView, thePick,
+ &pickRay, geomData );
-
- // See if we fall within the pick
- if (Q3Ray3D_IntersectBoundingBox(&pickData.ray, &worldBounds, &hitHYZ))
- qd3dStatus = e3geom_trimesh_pick_with_ray(theView, thePick, &pickData.ray, geomData);
- else
- qd3dStatus = kQ3Success;
-
return(qd3dStatus);
}
@@ -1435,7 +1510,8 @@
// e3geom_trimesh_bounds : TriMesh bounds method.
//-----------------------------------------------------------------------------
static TQ3Status
-e3geom_trimesh_bounds(TQ3ViewObject theView, TQ3ObjectType objectType, TQ3Object theObject, const void *objectData)
+e3geom_trimesh_bounds(TQ3ViewObject theView, TQ3ObjectType objectType,
+ TQ3Object theObject, const void *objectData)
{ TQ3Point3D boundCorners[8];
TQ3BoundingMethod boundingMethod;
const TQ3TriMeshData *geomData;
@@ -1483,10 +1559,10 @@
//-----------------------------------------------------------------------------
static TQ3AttributeSet *
e3geom_trimesh_get_attribute ( E3TriMesh* triMesh )
- {
+{
// Return the address of the geometry attribute set
return & triMesh->instanceData.geomData.triMeshAttributeSet ;
- }
+}
Modified: trunk/quesa/Development/Source/Core/Geometry/E3GeometryTriangle.c
===================================================================
--- trunk/quesa/Development/Source/Core/Geometry/E3GeometryTriangle.c 2016-08-09 23:40:33 UTC (rev 3346)
+++ trunk/quesa/Development/Source/Core/Geometry/E3GeometryTriangle.c 2016-09-27 17:06:31 UTC (rev 3347)
@@ -5,7 +5,7 @@
Implementation of Quesa Triangle geometry class.
COPYRIGHT:
- Copyright (c) 1999-2012, Quesa Developers. All rights reserved.
+ Copyright (c) 1999-2016, Quesa Developers. All rights reserved.
For the current release of Quesa, please see:
@@ -48,6 +48,8 @@
#include "E3Pick.h"
#include "E3Geometry.h"
#include "E3GeometryTriangle.h"
+#include "E3Math_Intersect.h"
+#include "QuesaMathOperators.hpp"
@@ -160,11 +162,11 @@
// e3geom_triangle_pick_with_ray : Triangle ray picking method.
//-----------------------------------------------------------------------------
static TQ3Status
-e3geom_triangle_pick_with_ray(TQ3ViewObject theView,
+e3geom_triangle_pick_with_ray( TQ3ViewObject theView,
TQ3PickObject thePick,
const TQ3Ray3D *theRay,
TQ3Object theObject,
- const void *objectData)
+ const void *objectData )
{ const TQ3TriangleData *instanceData = (const TQ3TriangleData *) objectData;
TQ3Boolean haveUV, cullBackface;
TQ3Param2D hitUV, *resultUV;
@@ -181,7 +183,8 @@
// Transform our points
for (n = 0; n < 3; n++)
- Q3View_TransformLocalToWorld(theView, &instanceData->vertices[n].point, &worldPoints[n]);
+ Q3View_TransformLocalToWorld(theView, &instanceData->vertices[n].point,
+ &worldPoints[n]);
@@ -191,12 +194,48 @@
+ // Check for face tolerance
+ float faceTolerance;
+ E3Pick_GetFaceTolerance( thePick, &faceTolerance );
+ float toleranceSquared = faceTolerance * faceTolerance;
+ bool useTolerance = toleranceSquared > kQ3RealZero;
+
+
// See if we fall within the pick
- //
- // Note we do not use any vertex/edge tolerances supplied for the pick, since
- // QD3D's blue book appears to suggest neither are used for triangles.
- if (Q3Ray3D_IntersectTriangle(theRay, &worldPoints[0], &worldPoints[1], &worldPoints[2], cullBackface, &theHit))
+ TQ3Boolean didHit = kQ3False;
+ if (useTolerance)
+ {
+ if (E3Ray3D_NearTriangle( *theRay,
+ worldPoints[0], worldPoints[1], worldPoints[2], cullBackface, theHit ))
{
+ TQ3Point3D triNearPt = (1.0f - theHit.u - theHit.v) * worldPoints[0] +
+ theHit.u * worldPoints[1] + theHit.v * worldPoints[2];
+ TQ3Point3D rayNearPt = theRay->origin + theHit.w * theRay->direction;
+
+ if (E3Pick_GetType( thePick ) == kQ3PickTypeWindowPoint)
+ {
+ TQ3Point2D triNearWin, rayNearWin;
+ E3View_TransformWorldToWindow( theView, &triNearPt, &triNearWin );
+ E3View_TransformWorldToWindow( theView, &rayNearPt, &rayNearWin );
+
+ float winDistSq = Q3LengthSquared2D( triNearWin - rayNearWin );
+ didHit = (winDistSq < toleranceSquared)? kQ3True : kQ3False;
+ }
+ else
+ {
+ float worldDistSq = Q3LengthSquared3D( rayNearPt - triNearPt );
+ didHit = (worldDistSq < toleranceSquared)? kQ3True : kQ3False;
+ }
+ }
+ }
+ else
+ {
+ didHit = E3Ray3D_IntersectTriangle( *theRay,
+ worldPoints[0], worldPoints[1], worldPoints[2], cullBackface, theHit );
+ }
+
+ if (didHit)
+ {
// Set up a temporary triangle that holds the world points
worldTriangle = *instanceData;
for (n = 0; n < 3; n++)
@@ -211,7 +250,7 @@
// Record the hit
qd3dStatus = E3Pick_RecordHit(thePick, theView, &hitXYZ, &hitNormal, resultUV, NULL, &theHit);
- }
+ }
return(qd3dStatus);
}
Modified: trunk/quesa/Development/Source/Core/Glue/QD3DMath.c
===================================================================
--- trunk/quesa/Development/Source/Core/Glue/QD3DMath.c 2016-08-09 23:40:33 UTC (rev 3346)
+++ trunk/quesa/Development/Source/Core/Glue/QD3DMath.c 2016-09-27 17:06:31 UTC (rev 3347)
@@ -6,7 +6,7 @@
then forwards each API call to the equivalent E3xxxxx routine.
COPYRIGHT:
- Copyright (c) 1999-2014, Quesa Developers. All rights reserved.
+ Copyright (c) 1999-2016, Quesa Developers. All rights reserved.
For the current release of Quesa, please see:
@@ -5138,7 +5138,9 @@
// Q3Ray3D_IntersectTriangle : Quesa API entry point.
//-----------------------------------------------------------------------------
TQ3Boolean
-Q3Ray3D_IntersectTriangle(const TQ3Ray3D *theRay, const TQ3Point3D *point1, const TQ3Point3D *point2, const TQ3Point3D *point3, TQ3Boolean cullBackfacing, TQ3Param3D *hitPoint)
+Q3Ray3D_IntersectTriangle(const TQ3Ray3D *theRay,
+ const TQ3Point3D *point1, const TQ3Point3D *point2, const TQ3Point3D *point3,
+ TQ3Boolean cullBackfacing, TQ3Param3D *hitPoint)
{
@@ -5161,7 +5163,8 @@
// Call our implementation
- return(E3Ray3D_IntersectTriangle(theRay, point1, point2, point3, cullBackfacing, hitPoint));
+ return(E3Ray3D_IntersectTriangle( *theRay, *point1, *point2, *point3,
+ cullBackfacing, *hitPoint));
}
Modified: trunk/quesa/Development/Source/Core/Glue/QD3DPick.c
===================================================================
--- trunk/quesa/Development/Source/Core/Glue/QD3DPick.c 2016-08-09 23:40:33 UTC (rev 3346)
+++ trunk/quesa/Development/Source/Core/Glue/QD3DPick.c 2016-09-27 17:06:31 UTC (rev 3347)
@@ -6,7 +6,7 @@
then forwards each API call to the equivalent E3xxxxx routine.
COPYRIGHT:
- Copyright (c) 1999-2014, Quesa Developers. All rights reserved.
+ Copyright (c) 1999-2016, Quesa Developers. All rights reserved.
For the current release of Quesa, please see:
@@ -236,6 +236,37 @@
//=============================================================================
+// Q3Pick_GetFaceTolerance : Quesa API entry point.
+//-----------------------------------------------------------------------------
+TQ3Status
+Q3Pick_GetFaceTolerance(TQ3PickObject pick, float *faceTolerance)
+{
+
+
+ // Release build checks
+ Q3_REQUIRE_OR_RESULT( E3Pick_IsOfMyClass ( pick ), kQ3Failure);
+ Q3_REQUIRE_OR_RESULT(Q3_VALID_PTR(faceTolerance), kQ3Failure);
+
+
+
+ // Debug build checks
+
+
+
+ // Call the bottleneck
+ E3System_Bottleneck();
+
+
+
+ // Call our implementation
+ return(E3Pick_GetFaceTolerance(pick, faceTolerance));
+}
+
+
+
+
+
+//=============================================================================
// Q3Pick_SetVertexTolerance : Quesa API entry point.
//-----------------------------------------------------------------------------
TQ3Status
@@ -296,6 +327,36 @@
//=============================================================================
+// Q3Pick_SetFaceTolerance : Quesa API entry point.
+//-----------------------------------------------------------------------------
+TQ3Status
+Q3Pick_SetFaceTolerance(TQ3PickObject pick, float faceTolerance)
+{
+
+
+ // Release build checks
+ Q3_REQUIRE_OR_RESULT( E3Pick_IsOfMyClass ( pick ), kQ3Failure);
+
+
+
+ // Debug build checks
+
+
+
+ // Call the bottleneck
+ E3System_Bottleneck();
+
+
+
+ // Call our implementation
+ return(E3Pick_SetFaceTolerance(pick, faceTolerance));
+}
+
+
+
+
+
+//=============================================================================
// Q3Pick_GetNumHits : Quesa API entry point.
//-----------------------------------------------------------------------------
TQ3Status
Modified: trunk/quesa/Development/Source/Core/System/E3Math.c
===================================================================
--- trunk/quesa/Development/Source/Core/System/E3Math.c 2016-08-09 23:40:33 UTC (rev 3346)
+++ trunk/quesa/Development/Source/Core/System/E3Math.c 2016-09-27 17:06:31 UTC (rev 3347)
@@ -8,7 +8,7 @@
speed, to avoid the trip back out through the Q3foo interface.
COPYRIGHT:
- Copyright (c) 1999-2014, Quesa Developers. All rights reserved.
+ Copyright (c) 1999-2016, Quesa Developers. All rights reserved.
For the current release of Quesa, please see:
@@ -4344,13 +4344,96 @@
else
{
const char* in = (const char*) points3D;
- TQ3Uns32 i;
+ TQ3Uns32 i = 0;
Q3FastBoundingBox_Set(bBox, points3D, points3D, kQ3False);
- in += structSize;
- for (i = 1; i < numPoints; ++i, in += structSize)
- e3bounding_box_accumulate_point3D(bBox, (const TQ3Point3D*)(const void*) in);
+ // We have already accounted for the first point, so if the number of
+ // points is odd, we can handle the other points in pairs, and need not
+ // look at the first point again. But if the number of points is even,
+ // we will start at the first point just so we can work in pairs.
+ if ( (numPoints % 2) == 1 )
+ {
+ in += structSize;
+ i = 1;
+ }
+
+ for (; i < numPoints; i += 2)
+ {
+ TQ3Point3D pt0 = *(const TQ3Point3D*)(const void*) in;
+ in += structSize;
+ TQ3Point3D pt1 = *(const TQ3Point3D*)(const void*) in;
+ in += structSize;
+
+ if (pt0.x < pt1.x)
+ {
+ if (pt0.x < bBox->min.x)
+ {
+ bBox->min.x = pt0.x;
+ }
+ if (pt1.x > bBox->max.x)
+ {
+ bBox->max.x = pt1.x;
+ }
+ }
+ else // pt1.x <= pt0.x
+ {
+ if (pt1.x < bBox->min.x)
+ {
+ bBox->min.x = pt1.x;
+ }
+ if (pt0.x > bBox->max.x)
+ {
+ bBox->max.x = pt0.x;
+ }
+ }
+
+ if (pt0.y < pt1.y)
+ {
+ if (pt0.y < bBox->min.y)
+ {
+ bBox->min.y = pt0.y;
+ }
+ if (pt1.y > bBox->max.y)
+ {
+ bBox->max.y = pt1.y;
+ }
+ }
+ else // pt1.y <= pt0.y
+ {
+ if (pt1.y < bBox->min.y)
+ {
+ bBox->min.y = pt1.y;
+ }
+ if (pt0.y > bBox->max.y)
+ {
+ bBox->max.y = pt0.y;
+ }
+ }
+
+ if (pt0.z < pt1.z)
+ {
+ if (pt0.z < bBox->min.z)
+ {
+ bBox->min.z = pt0.z;
+ }
+ if (pt1.z > bBox->max.z)
+ {
+ bBox->max.z = pt1.z;
+ }
+ }
+ else // pt1.z <= pt0.z
+ {
+ if (pt1.z < bBox->min.z)
+ {
+ bBox->min.z = pt1.z;
+ }
+ if (pt0.z > bBox->max.z)
+ {
+ bBox->max.z = pt0.z;
+ }
+ }
+ }
}
return(bBox);
Modified: trunk/quesa/Development/Source/Core/System/E3Math_Intersect.cpp
===================================================================
--- trunk/quesa/Development/Source/Core/System/E3Math_Intersect.cpp 2016-08-09 23:40:33 UTC (rev 3346)
+++ trunk/quesa/Development/Source/Core/System/E3Math_Intersect.cpp 2016-09-27 17:06:31 UTC (rev 3347)
@@ -8,7 +8,7 @@
speed, to avoid the trip back out through the Q3foo interface.
COPYRIGHT:
- Copyright (c) 1999-2014, Quesa Developers. All rights reserved.
+ Copyright (c) 1999-2016, Quesa Developers. All rights reserved.
For the current release of Quesa, please see:
@@ -73,7 +73,6 @@
kHalfPlaneResult_AllOutside
};
-const float kQ3Infinity = std::numeric_limits<float>::infinity();
//=============================================================================
@@ -169,6 +168,12 @@
// Internal functions
//-----------------------------------------------------------------------------
+static float Infinity()
+{
+ static float sInfinity = std::numeric_limits<float>::infinity();
+ return sInfinity;
+}
+
static TQ3Vector3D InfinitePointToVector( const TQ3RationalPoint4D& inInfinitePt )
{
TQ3Vector3D vec = {
@@ -204,7 +209,7 @@
{
outEdgeRay.ray.origin = FinitePointToPoint( inEdge.start );
outEdgeRay.ray.direction = InfinitePointToVector( inEdge.end );
- outEdgeRay.paramRange.maximum = kQ3Infinity;
+ outEdgeRay.paramRange.maximum = Infinity();
outEdgeRay.isRayAtInfinity = false;
}
else // both are finite points
@@ -259,7 +264,7 @@
if (originDotP <= 0.0f) // whole ray
{
solutions.minimum = 0.0f;
- solutions.maximum = kQ3Infinity;
+ solutions.maximum = Infinity();
}
else // no solution
{
@@ -275,7 +280,7 @@
else // dirDotP < 0.0f
{
solutions.minimum = std::max( 0.0f, - originDotP / dirDotP );
- solutions.maximum = kQ3Infinity;
+ solutions.maximum = Infinity();
}
return solutions;
@@ -292,7 +297,7 @@
{
Interval solution;
solution.minimum = 0.0f;
- solution.maximum = kQ3Infinity;
+ solution.maximum = Infinity();
for (int i = 0; i < 6; ++i)
{
@@ -319,7 +324,7 @@
{
Interval solution;
solution.minimum = 0.0f;
- solution.maximum = kQ3Infinity;
+ solution.maximum = Infinity();
// In order for a ray point, rayOrigin + t * rayDir, to be on the right side of the
// cylinder's base plane, we need
@@ -447,7 +452,7 @@
{
Interval solution;
solution.minimum = 0.0f;
- solution.maximum = kQ3Infinity;
+ solution.maximum = Infinity();
// In order for a ray point, rayOrigin + t * rayDir, to be on the right side of the
// cone's base plane, we need
@@ -565,7 +570,7 @@
// Note that here denom < 0, so we get the higher root
// by choosing the minus sign before rootDiscrim.
quadSol.minimum = (-B - rootDiscrim) * denom;
- quadSol.maximum = kQ3Infinity;
+ quadSol.maximum = Infinity();
}
else
{
@@ -1022,11 +1027,11 @@
{
if (theDot > 0.0f)
{
- theDot = kQ3Infinity;
+ theDot = Infinity();
}
else if (theDot < 0.0f)
{
- theDot = - kQ3Infinity;
+ theDot = - Infinity();
}
}
else
@@ -1293,21 +1298,45 @@
// Details at:
// <http://www.graphics.cornell.edu/pubs/1997/MT97.pdf>
//-----------------------------------------------------------------------------
+/*!
+ @function E3Ray3D_IntersectTriangle
+ @abstract Find the intersection between a ray and a triangle.
+ @discussion If the ray is in the plane of the triangle, we report no hit
+ even though there may mathematically be infinitely many points
+ of intersection.
+
+ If we do detect a hit, then hitPoint->u and hitPoint->v are two
+ barycentric coordinates of the intersection point, and
+ hitPoint->w is the distance along the ray. To be precise,
+ theRay->origin + hitPoint->w * theRay->direction ==
+ (1.0 - hitPoint->u - hitPoint->v) * point1 +
+ hitPoint->u * point2 + hitPoint->v * point3.
+
+ If the result is true, then the computed parameters will satisfy
+ u >= 0, v >= 0, u + v <= 1, and w >= 0.
+ @param theRay A ray.
+ @param point1 A point (a vertex of a triangle).
+ @param point2 A point (a vertex of a triangle).
+ @param point3 A point (a vertex of a triangle).
+ @param cullBackfacing Whether to omit a hit on the back face.
+ @param outHitPoint Receives intersection data as described above.
+ @result True if we detected a hit.
+*/
TQ3Boolean
-E3Ray3D_IntersectTriangle(const TQ3Ray3D *theRay,
- const TQ3Point3D *point1,
- const TQ3Point3D *point2,
- const TQ3Point3D *point3,
+E3Ray3D_IntersectTriangle( const TQ3Ray3D& theRay,
+ const TQ3Point3D& point1,
+ const TQ3Point3D& point2,
+ const TQ3Point3D& point3,
TQ3Boolean cullBackfacing,
- TQ3Param3D *hitPoint)
+ TQ3Param3D& outHitPoint)
{ TQ3Vector3D edge1, edge2, tvec, pvec, qvec;
float det, invDet;
// Calculate the two edges which share vertex 1
- Q3FastPoint3D_Subtract(point2, point1, &edge1);
- Q3FastPoint3D_Subtract(point3, point1, &edge2);
+ edge1 = point2 - point1;
+ edge2 = point3 - point1;
@@ -1315,56 +1344,54 @@
// determinant is near zero, the ray lies in the plane of the triangle.
// However, some care is needed; we can get a false positive on "near zero"
// if the triangle is small.
- Q3FastVector3D_Cross(&theRay->direction, &edge2, &pvec);
- det = Q3FastVector3D_Dot(&edge1, &pvec);
+ pvec = Q3Cross3D( theRay.direction, edge2 );
+ det = Q3Dot3D( edge1, pvec );
float testDet = det;
if (fabsf( det ) < kQ3RealZero)
{
- TQ3Vector3D faceNorm;
- Q3FastVector3D_Cross( &edge2, &edge1, &faceNorm );
- Q3FastVector3D_Normalize( &faceNorm, &faceNorm );
- testDet = Q3FastVector3D_Dot( &faceNorm, &theRay->direction );
+ TQ3Vector3D faceNorm = Q3Normalize3D( Q3Cross3D( edge2, edge1 ) );
+ testDet = Q3Dot3D( faceNorm, theRay.direction );
}
// Handle triangles with back-face culling
if (cullBackfacing)
- {
+ {
// Test for ray coinciding with triangle plane, or backface hit
if (testDet < kQ3RealZero)
return(kQ3False);
// Calculate the distance between vertex 1 and the ray origin
- Q3FastPoint3D_Subtract(&theRay->origin, point1, &tvec);
+ tvec = theRay.origin - point1;
// Calculate u, and test for a miss
- hitPoint->u = Q3FastVector3D_Dot(&tvec, &pvec);
- if (hitPoint->u < 0.0f || hitPoint->u > det)
+ outHitPoint.u = Q3Dot3D( tvec, pvec );
+ if (outHitPoint.u < 0.0f || outHitPoint.u > det)
return(kQ3False);
// Calculate v, and test for a miss
- Q3FastVector3D_Cross(&tvec, &edge1, &qvec);
- hitPoint->v = Q3FastVector3D_Dot(&theRay->direction, &qvec);
- if (hitPoint->v < 0.0f || (hitPoint->u + hitPoint->v) > det)
+ qvec = Q3Cross3D( tvec, edge1 );
+ outHitPoint.v = Q3Dot3D( theRay.direction, qvec );
+ if (outHitPoint.v < 0.0f || (outHitPoint.u + outHitPoint.v) > det)
return(kQ3False);
// Calculate w, and scale the parameters
- hitPoint->w = Q3FastVector3D_Dot(&edge2, &qvec);
+ outHitPoint.w = Q3Dot3D( edge2, qvec );
invDet = 1.0f / det;
- hitPoint->w *= invDet;
- hitPoint->u *= invDet;
- hitPoint->v *= invDet;
- }
+ outHitPoint.w *= invDet;
+ outHitPoint.u *= invDet;
+ outHitPoint.v *= invDet;
+ }
// Handle triangles with no culling
else
- {
+ {
// Test for ray coinciding with triangle plane
if (testDet > -kQ3RealZero && testDet < kQ3RealZero)
return(kQ3False);
@@ -1373,37 +1400,224 @@
// Calculate the distance between vertex 1 and the ray origin
- Q3FastPoint3D_Subtract(&theRay->origin, point1, &tvec);
+ tvec = theRay.origin - point1;
// Calculate u, and test for a miss
- hitPoint->u = Q3FastVector3D_Dot(&tvec, &pvec) * invDet;
- if (hitPoint->u < 0.0f || hitPoint->u > 1.0f)
+ outHitPoint.u = Q3Dot3D( tvec, pvec ) * invDet;
+ if (outHitPoint.u < 0.0f || outHitPoint.u > 1.0f)
return(kQ3False);
// Calculate v, and test for a miss
- Q3FastVector3D_Cross(&tvec, &edge1, &qvec);
- hitPoint->v = Q3FastVector3D_Dot(&theRay->direction, &qvec) * invDet;
- if (hitPoint->v < 0.0f || (hitPoint->u + hitPoint->v) > 1.0f)
+ qvec = Q3Cross3D( tvec, edge1 );
+ outHitPoint.v = Q3Dot3D( theRay.direction, qvec ) * invDet;
+ if (outHitPoint.v < 0.0f || (outHitPoint.u + outHitPoint.v) > 1.0f)
return(kQ3False);
// Calculate w
- hitPoint->w = Q3FastVector3D_Dot(&edge2, &qvec) * invDet;
- }
+ outHitPoint.w = Q3Dot3D( edge2, qvec ) * invDet;
+ }
// The ray intersects the triangle
- return (hitPoint->w >= 0.0f ? kQ3True : kQ3False);
+ return (outHitPoint.w >= 0.0f ? kQ3True : kQ3False);
}
+/*!
+ @function E3Ray3D_IntersectPlaneOfTriangle
+ @abstract Find the intersection between a ray and the plane of a triangle.
+ @discussion If the ray is in the plane of the triangle, we report no hit
+ even though there may mathematically be infinitely many points
+ of intersection.
+
+ This function is similar to E3Ray3D_IntersectTriangle, but finds
+ any intersection with the plane of the triangle. Therefore,
+ there are no constraints on the barycentric coordinates u and v,
+ but we do still require that w >= 0.
+
+ If we do detect a hit, then hitPoint->u and hitPoint->v are two
+ barycentric coordinates of the intersection point, and
+ hitPoint->w is the distance along the ray. To be precise,
+ theRay->origin + hitPoint->w * theRay->direction ==
+ (1.0 - hitPoint->u - hitPoint->v) * point1 +
+ hitPoint->u * point2 + hitPoint->v * point3.
+ @param theRay A ray.
+ @param point1 A point (a vertex of a triangle).
+ @param point2 A point (a vertex of a triangle).
+ @param point3 A point (a vertex of a triangle).
+ @param cullBackfacing Whether to omit a hit on the back face.
+ @param outHitPoint Receives intersection data as described above.
+ @result True if we detected a hit.
+*/
+TQ3Boolean E3Ray3D_IntersectPlaneOfTriangle(
+ const TQ3Ray3D& theRay,
+ const TQ3Point3D& point1,
+ const TQ3Point3D& point2,
+ const TQ3Point3D& point3,
+ TQ3Boolean cullBackfacing,
+ TQ3Param3D& outHitPoint)
+{
+ // Calculate the two edges which share vertex 1
+ TQ3Vector3D edge1 = point2 - point1;
+ TQ3Vector3D edge2 = point3 - point1;
+
+ // Begin calculating the determinant - also used to calculate u. If the
+ // determinant is near zero, the ray lies in the plane of the triangle.
+ // However, some care is needed; we can get a false positive on "near zero"
+ // if the triangle is small.
+ TQ3Vector3D pvec = Q3Cross3D( theRay.direction, edge2 );
+ float det = Q3Dot3D( edge1, pvec );
+ float testDet = det;
+ if (fabsf( det ) < kQ3RealZero)
+ {
+ TQ3Vector3D faceNorm = Q3Normalize3D( Q3Cross3D( edge2, edge1 ) );
+ testDet = Q3Dot3D( faceNorm, theRay.direction );
+ }
+
+ // Test for misses by back-face culling or ray parallel to plane
+ if (cullBackfacing)
+ {
+ if (testDet < kQ3RealZero)
+ {
+ return kQ3False;
+ }
+ }
+ else
+ {
+ if (fabsf( testDet ) < kQ3RealZero)
+ {
+ return kQ3False;
+ }
+ }
+
+ float invDet = 1.0f / det;
+
+ // Calculate the vector between vertex 1 and the ray origin
+ TQ3Vector3D tvec = theRay.origin - point1;
+
+ // Calculate u
+ outHitPoint.u = Q3Dot3D( tvec, pvec ) * invDet;
+
+ // Calculate v
+ TQ3Vector3D qvec = Q3Cross3D( tvec, edge1 );
+ outHitPoint.v = Q3Dot3D( theRay.direction, qvec ) * invDet;
+
+ // Calculate w
+ outHitPoint.w = Q3Dot3D( edge2, qvec ) * invDet;
+
+ return (outHitPoint.w >= 0.0f ? kQ3True : kQ3False);
+}
+
+
+
+
/*!
+ @function E3Ray3D_NearTriangle
+ @abstract Find the nearest points of a ray and a triangle.
+ @discussion This function can return kQ3False under 2 conditions:
+ (1) The triangle is edge-on to the ray, i.e.,
+ Dot( frontFaceVec, theRay.direction ) = 0.
+ (2) cullBackfacing == kQ3True, and the ray faces the back face
+ of the triangle, i.e.,
+ Dot( frontFaceVec, theRay.direction ) > 0.
+
+ Otherwise, we find parameters u, v, w such that
+ u >= 0,
+ v >= 0;
+ u + v <= 1;
+ w >= 0;
+ and the distance between the ray point
+ theRay.origin + w * theRay.direction
+ and the triangle point
+ (1 - u - v) * point1 + u * point2 + v * point3
+ is minimized.
+ @param theRay A ray.
+ @param point1 A point (a vertex of a triangle).
+ @param point2 A point (a vertex of a triangle).
+ @param point3 A point (a vertex of a triangle).
+ @param cullBackfacing Whether to omit a hit on the back face.
+ @param outHitPoint Receives intersection data as described above.
+ @result True if we detected a hit.
+*/
+TQ3Boolean E3Ray3D_NearTriangle(
+ const TQ3Ray3D& theRay,
+ const TQ3Point3D& point1,
+ const TQ3Point3D& point2,
+ const TQ3Point3D& point3,
+ TQ3Boolean cullBackfacing,
+ TQ3Param3D& outHitPoint )
+{
+ TQ3Param3D planeHit;
+ TQ3Boolean didHit = E3Ray3D_IntersectPlaneOfTriangle( theRay,
+ point1, point2, point3, cullBackfacing, planeHit );
+
+ if (didHit)
+ {
+ // If the ray hit inside the triangle, then the work is done.
+ if ( (planeHit.u >= 0.0f) && (planeHit.v >= 0.0f) &&
+ (planeHit.u + planeHit.v <= 1.0f) )
+ {
+ outHitPoint = planeHit;
+ }
+ else // missed the triangle, nearest point is along an edge
+ {
+ float rayParam12, segParam12;
+ E3Math_RayNearestLineSegment( theRay, point1, point2,
+ rayParam12, segParam12 );
+ TQ3Point3D rayPt12 = theRay.origin + rayParam12 * theRay.direction;
+ TQ3Point3D triPt12 = (1.0f - segParam12) * point1 + segParam12 * point2;
+ float lenSq12 = Q3LengthSquared3D( rayPt12 - triPt12 );
+
+ float rayParam13, segParam13;
+ E3Math_RayNearestLineSegment( theRay, point1, point3,
+ rayParam13, segParam13 );
+ TQ3Point3D rayPt13 = theRay.origin + rayParam13 * theRay.direction;
+ TQ3Point3D triPt13 = (1.0f - segParam13) * point1 + segParam13 * point3;
+ float lenSq13 = Q3LengthSquared3D( rayPt13 - triPt13 );
+
+ float rayParam23, segParam23;
+ E3Math_RayNearestLineSegment( theRay, point2, point3,
+ rayParam23, segParam23 );
+ TQ3Point3D rayPt23 = theRay.origin + rayParam23 * theRay.direction;
+ TQ3Point3D triPt23 = (1.0f - segParam23) * point2 + segParam23 * point3;
+ float lenSq23 = Q3LengthSquared3D( rayPt23 - triPt23 );
+
+ if ( (lenSq12 <= lenSq13) && (lenSq12 <= lenSq23) )
+ {
+ outHitPoint.w = rayParam12;
+ outHitPoint.u = segParam12;
+ outHitPoint.v = 0.0f;
+ }
+ else if ( (lenSq13 <= lenSq12) && (lenSq13 <= lenSq23) )
+ {
+ outHitPoint.w = rayParam13;
+ outHitPoint.u = 0.0f;
+ outHitPoint.v = segParam13;
+ }
+ else // (lenSq23 <= lenSq12) && (lenSq23 <= lenSq13)
+ {
+ outHitPoint.w = rayParam23;
+ outHitPoint.u = 1.0f - segParam23;
+ outHitPoint.v = segParam23;
+ }
+ }
+ }
+
+ return didHit;
+}
+
+
+
+
+
+/*!
@function E3Ray3D_IntersectCone
@abstract Compute the intersections between a ray and a cone surface.
@discussion This function computes the minimum and maximum values of t
@@ -1493,13 +1707,13 @@
if (isRayOriginInCone)
{
outMinParam = 0.0f;
- outMaxParam = kQ3Infinity;
+ outMaxParam = Infinity();
didIntersect = true;
}
else
{
outMinParam = diffLen;
- outMaxParam = kQ3Infinity;
+ outMaxParam = Infinity();
didIntersect = true;
}
}
@@ -1530,7 +1744,7 @@
if (isRayEndInCone)
{
outMinParam = t;
- outMaxParam = kQ3Infinity;
+ outMaxParam = Infinity();
didIntersect = true;
}
}
@@ -1539,7 +1753,7 @@
if (isRayEndInCone)
{
outMinParam = 0.0f;
- outMaxParam = kQ3Infinity;
+ outMaxParam = Infinity();
didIntersect = true;
}
}
@@ -1596,13 +1810,13 @@
if (root2 >= 0.0f)
{
outMinParam = root2;
- outMaxParam = kQ3Infinity;
+ outMaxParam = Infinity();
didIntersect = true;
}
else
{
outMinParam = 0.0f;
- outMaxParam = kQ3Infinity;
+ outMaxParam = Infinity();
didIntersect = true;
}
Q3_ASSERT( isRayEndInCone );
@@ -1618,6 +1832,157 @@
/*!
+ @function E3Math_LineNearestPoint
+
+ @abstract Find the point on a line that is nearest to a given point.
+
+ @discussion If what you really want is the point on a RAY nearest a given
+ point, then just clamp the result to be nonnegative.
+
+ @param inRay A 3D ray. The direction need not be normalized,
+ but must be nonzero.
+ @param inPt A point.
+ @result A number t such that inRay.origin + t * inRay.direction is as
+ near as possible to inPt.
+*/
+float E3Math_LineNearestPoint(
+ const TQ3Ray3D& inRay,
+ const TQ3Point3D& inPt )
+{
+ float t = Q3Dot3D( inPt - inRay.origin, inRay.direction ) /
+ Q3Dot3D( inRay.direction, inRay.direction );
+ return t;
+}
+
+
+
+
+
+/*!
+ @function E3Math_RayNearestLineSegment
+
+ @abstract Find points on a ray and a line segment that are as near as
+ possible to each other.
+
+ @discussion Find outRayParam >= 0 and outSegParam in [0,1] such that the
+ points inRay.origin + outRayParam * inRay.direction and
+ (1.0 - outSegParam) * inPtA + outSegParam * inPtB are as near
+ to each other as possible.
+
+ If the ray and the segment happen to be parallel, then the
+ solution is not unique, and this function just returns one of
+ the solutions.
+
+ @param inRay A 3D ray. The direction need not be normalized,
+ but must be nonzero.
+ @param inPtA A point.
+ @param inPtB A point.
+ @param outRayParam Returns a parameter for the ray, always nonnegative.
+ @param outSegParam Returns a parameter for the line segment, between
+ 0 and 1 inclusive.
+*/
+void E3Math_RayNearestLineSegment(
+ const TQ3Ray3D& inRay,
+ const TQ3Point3D& inPtA,
+ const TQ3Point3D& inPtB,
+ float& outRayParam,
+ float& outSegParam )
+{
+ TQ3Vector3D v = inPtB - inPtA;
+ // We want to find numbers s, t to minimize the distance between
+ // inRay.origin + s * inRay.direction and inPtA + t * v. In other words,
+ // we want to minimize the length of the vector
+ // inRay.origin + s * inRay.direction - (inPtA + t * v).
+ TQ3Vector3D g = inRay.origin - inPtA;
+ // Now we want to minimize the length of the vector
+ // w = g + s * inRay.direction - t * v.
+ // To keep thing briefer, let's use r to stand for inRay.direction, so that
+ // we want to minimize the length of w = g + s * r - t * v.
+ // This will happen when w is orthogonal to both r and v.
+ // That gives us two linear equations,
+ // 0 = Dot( w, r ) = Dot( g, r ) + s * Dot( r, r ) - t * Dot( v, r ), and
+ // 0 = Dot( w, v ) = Dot( g, v ) + s * Dot( r, v ) - t * Dot( v, v ).
+ // If we let a = Dot( r, r ), b = Dot( r, v ), c = Dot( v, v ),
+ // d = Dot( g, r ), and e = Dot( g, v ), then the equations are
+ // s * a - t * b = -d
+ // s * b - t * c = -e
+ // or in matrix form
+ // a -b | -d
+ // b -c | -e .
+ // This system has the solution
+ // s = (d*c - b*e) / (b*b - a*c), t = (b*d - a*e) / (b*b - a*c) .
+ // Of course, we need to avoid division by zero. The denominator is
+ // b*b - a*c = Dot( r, v ) * Dot( r, v ) - Dot( r, r ) * Dot( v, v )
+ // = |r|^2 |v|^2 cos^2(angle) - |r|^2 |v|^2
+ // = |r|^2 |v|^2 (cos^2(angle) - 1)
+ // = - sin^2(angle) |r|^2 |v|^2.
+ // This is zero when the sine of the angle is 0 (meaning that r and v have
+ // the same or opposite directions) or if r or v are zero. However we
+ // assumed that r is not zero.
+ float c = Q3Dot3D( v, v );
+ if (c < kQ3RealZero) // i.e., inPtA and inPtB are essentially the same
+ {
+ outRayParam = std::max( 0.0f, E3Math_LineNearestPoint( inRay, inPtA ) );
+ outSegParam = 0.0f;
+ }
+ else
+ {
+ float a = Q3Dot3D( inRay.direction, inRay.direction );
+ float b = Q3Dot3D( inRay.direction, v );
+ float denom = b*b - a*c;
+ if (fabsf( denom ) < kQ3RealZero) // ray & segment parallel or opposite
+ {
+ // Test segment ends
+ float rayParamA = std::max( 0.0f, E3Math_LineNearestPoint( inRay, inPtA ) );
+ TQ3Point3D rayPtA = inRay.origin + rayParamA * inRay.direction;
+ float rayParamB = std::max( 0.0f, E3Math_LineNearestPoint( inRay, inPtB ) );
+ TQ3Point3D rayPtB = inRay.origin + rayParamB * inRay.direction;
+ if ( Q3LengthSquared3D( inPtA - rayPtA ) <
+ Q3LengthSquared3D( inPtB - rayPtB ) )
+ {
+ outRayParam = rayParamA;
+ outSegParam = 0.0f;
+ }
+ else
+ {
+ outRayParam = rayParamB;
+ outSegParam = 1.0f;
+ }
+ }
+ else // general case
+ {
+ float d = Q3Dot3D( inRay.direction, g );
+ float e = Q3Dot3D( v, g );
+ outRayParam = (d*c - b*e) / denom;
+ outSegParam = (b*d - a*e) / denom;
+ if ( (outSegParam < 0.0f) || (outSegParam > 1.0f) )
+ {
+ TQ3Point3D segNearPt;
+ if (outSegParam < 0.0f)
+ {
+ outSegParam = 0.0f;
+ segNearPt = inPtA;
+ }
+ else
+ {
+ outSegParam = 1.0f;
+ segNearPt = inPtB;
+ }
+ outRayParam = E3Math_LineNearestPoint( inRay, segNearPt );
+ }
+ if (outRayParam < 0.0f)
+ {
+ outRayParam = 0.0f;
+ }
+ }
+ }
+}
+
+
+
+
+
+/*!
@function E3Cone_IntersectBoundingBox
@abstract Determine whether a cone intersects a bounding box.
@param inConeAxis Axis ray of cone with a normalized direction.
Modified: trunk/quesa/Development/Source/Core/System/E3Math_Intersect.h
===================================================================
--- trunk/quesa/Development/Source/Core/System/E3Math_Intersect.h 2016-08-09 23:40:33 UTC (rev 3346)
+++ trunk/quesa/Development/Source/Core/System/E3Math_Intersect.h 2016-09-27 17:06:31 UTC (rev 3347)
@@ -5,7 +5,7 @@
Header file for E3Math_Intersect.cpp.
COPYRIGHT:
- Copyright (c) 1999-2014, Quesa Developers. All rights reserved.
+ Copyright (c) 1999-2016, Quesa Developers. All rights reserved.
For the current release of Quesa, please see:
@@ -65,24 +65,98 @@
theRay->origin + hitPoint->w * theRay->direction ==
(1.0 - hitPoint->u - hitPoint->v) * point1 +
hitPoint->u * point2 + hitPoint->v * point3.
+
+ If the result is true, then the computed parameters will satisfy
+ u >= 0, v >= 0, u + v <= 1, and w >= 0.
@param theRay A ray.
@param point1 A point (a vertex of a triangle).
@param point2 A point (a vertex of a triangle).
@param point3 A point (a vertex of a triangle).
@param cullBackfacing Whether to omit a hit on the back face.
- @param hitPoint Receives intersection data as described above.
+ @param outHitPoint Receives intersection data as described above.
@result True if we detected a hit.
*/
-TQ3Boolean E3Ray3D_IntersectTriangle(const TQ3Ray3D *theRay,
- const TQ3Point3D *point1,
- const TQ3Point3D *point2,
- const TQ3Point3D *point3,
- TQ3Boolean cullBackfacing,
- TQ3Param3D *hitPoint);
+TQ3Boolean E3Ray3D_IntersectTriangle( const TQ3Ray3D& theRay,
+ const TQ3Point3D& point1,
+ const TQ3Point3D& point2,
+ const TQ3Point3D& point3,
+ TQ3Boolean cullBackfacing,
+ TQ3Param3D& outHitPoint);
+/*!
+ @function E3Ray3D_IntersectPlaneOfTriangle
+ @abstract Find the intersection between a ray and the plane of a triangle.
+ @discussion If the ray is in the plane of the triangle, we report no hit
+ even though there may mathematically be infinitely many points
+ of intersection.
+
+ This function is similar to E3Ray3D_IntersectTriangle, but finds
+ any intersection with the plane of the triangle. Therefore,
+ there are no constraints on the barycentric coordinates u and v,
+ but we do still require that w >= 0.
+
+ If we do detect a hit, then hitPoint->u and hitPoint->v are two
+ barycentric coordinates of the intersection point, and
+ hitPoint->w is the distance along the ray. To be precise,
+ theRay->origin + hitPoint->w * theRay->direction ==
+ (1.0 - hitPoint->u - hitPoint->v) * point1 +
+ hitPoint->u * point2 + hitPoint->v * point3.
+ @param theRay A ray.
+ @param point1 A point (a vertex of a triangle).
+ @param point2 A point (a vertex of a triangle).
+ @param point3 A point (a vertex of a triangle).
+ @param cullBackfacing Whether to omit a hit on the back face.
+ @param outHitPoint Receives intersection data as described above.
+ @result True if we detected a hit.
+*/
+TQ3Boolean E3Ray3D_IntersectPlaneOfTriangle(
+ const TQ3Ray3D& theRay,
+ const TQ3Point3D& point1,
+ const TQ3Point3D& point2,
+ const TQ3Point3D& point3,
+ TQ3Boolean cullBackfacing,
+ TQ3Param3D& outHitPoint );
+
/*!
+ @function E3Ray3D_NearTriangle
+ @abstract Find the nearest points of a ray and a triangle.
+ @discussion This function can return kQ3False under 2 conditions:
+ (1) The triangle is edge-on to the ray, i.e.,
+ Dot( frontFaceVec, theRay.direction ) = 0.
+ (2) cullBackfacing == kQ3True, and the ray faces the back face
+ of the triangle, i.e.,
+ Dot( frontFaceVec, theRay.direction ) > 0.
+
+ Otherwise, we find parameters u, v, w such that
+ u >= 0,
+ v >= 0;
+ u + v <= 1;
+ w >= 0;
+ and the distance between the ray point
+ theRay.origin + w * theRay.direction
+ and the triangle point
+ (1 - u - v) * point1 + u * point2 + v * point3
+ is minimized.
+ @param theRay A ray.
+ @param point1 A point (a vertex of a triangle).
+ @param point2 A point (a vertex of a triangle).
+ @param point3 A point (a vertex of a triangle).
+ @param cullBackfacing Whether to omit a hit on the back face.
+ @param outHitPoint Receives intersection data as described above.
+ @result True if we detected a hit.
+*/
+TQ3Boolean E3Ray3D_NearTriangle(
+ const TQ3Ray3D& theRay,
+ const TQ3Point3D& point1,
+ const TQ3Point3D& point2,
+ const TQ3Point3D& point3,
+ TQ3Boolean cullBackfacing,
+ TQ3Param3D& outHitPoint );
+
+
+/*!
@function E3Ray3D_IntersectCone
@abstract Compute the intersections between a ray and a cone surface.
@discussion This function computes the minimum and maximum values of t
@@ -112,6 +186,55 @@
/*!
+ @function E3Math_LineNearestPoint
+
+ @abstract Find the point on a line that is nearest to a given point.
+
+ @discussion If what you really want is the point on a RAY nearest a given
+ point, then just clamp the result to be nonnegative.
+
+ @param inRay A 3D ray. The direction need not be normalized,
+ but must be nonzero.
+ @param inPt A point.
+ @result A number t such that inRay.origin + t * inRay.direction is as
+ near as possible to inPt.
+*/
+float E3Math_LineNearestPoint(
+ const TQ3Ray3D& inRay,
+ const TQ3Point3D& inPt );
+
+
+/*!
+ @function E3Math_RayNearestLineSegment
+
+ @abstract Find points on a ray and a line segment that are as near as
+ possible to each other.
+
+ @discussion Find outRayParam >= 0 and outSegParam in [0,1] such that the
+ points inRay.origin + outRayParam * inRay.direction and
+ (1.0 - outSegParam) * inPtA + outSegParam * inPtB are as near
+ to each other as possible.
+
+ If the ray and the segment happen to be parallel, then the
+ solution is not unique, and this function just returns one of
+ the solutions.
+
+ @param inRay A 3D ray. The direction need not be normalized,
+ but must be nonzero.
+ @param inPtA A point.
+ @param inPtB A point.
+ @param outRayParam Returns a parameter for the ray, always nonnegative.
+ @param outSegParam Returns a parameter for the line segment, between
+ 0 and 1 inclusive.
+*/
+void E3Math_RayNearestLineSegment(
+ const TQ3Ray3D& inRay,
+ const TQ3Point3D& inPtA,
+ const TQ3Point3D& inPtB,
+ float& outRayParam,
+ float& outSegParam );
+
+/*!
@function E3Cone_IntersectBoundingBox
@abstract Determine whether a cone intersects a bounding box.
@param inConeAxis Axis ray of cone with a normalized direction.
Modified: trunk/quesa/Development/Source/Core/System/E3Pick.c
===================================================================
--- trunk/quesa/Development/Source/Core/System/E3Pick.c 2016-08-09 23:40:33 UTC (rev 3346)
+++ trunk/quesa/Development/Source/Core/System/E3Pick.c 2016-09-27 17:06:31 UTC (rev 3347)
@@ -5,7 +5,7 @@
Implementation of Quesa API calls.
COPYRIGHT:
- Copyright (c) 1999-2015, Quesa Developers. All rights reserved.
+ Copyright (c) 1999-2016, Quesa Developers. All rights reserved.
For the current release of Quesa, please see:
@@ -62,6 +62,7 @@
//=============================================================================
// Internal types
//-----------------------------------------------------------------------------
+#pragma mark struct TQ3PickHit
// Pick hit result
struct TQ3PickHit
{
@@ -88,28 +89,33 @@
TQ3Param3D hitBarycentric;
};
+struct TQ3WindowPointPickSpecificData
+{
+ TQ3Point2D point;
+};
-// Pick object instance data
-struct TQ3PickUnionData
+struct TQ3WorldRayPickSpecificData
{
- // Common data
+ TQ3Ray3D ray;
+};
+
+struct TQ3WindowRectPickSpecificData
+{
+ TQ3Area rect;
+};
+
+
+struct TQ3PickBaseData
+{
+ TQ3PickData commonData;
std::vector<TQ3PickHit*>* pickHits;
bool isSorted;
-
-
- // Pick specific. Note that we assume that a TQ3PickData structure
- // is the first item within each pick structure, since this lets us
- // use a union and have the common data overlap.
- union {
- TQ3PickData common;
- TQ3WindowPointPickData windowPointData;
- TQ3WindowRectPickData windowRectData;
- TQ3WorldRayPickData worldRayData;
- } data;
+ float vertexTolerance;
+ float edgeTolerance;
+ float faceTolerance;
};
-
struct CompPickNearToFar
{
bool operator()( TQ3PickHit* inOne, TQ3PickHit* inTwo ) const;
@@ -127,12 +133,11 @@
// the .c file rather than in the .h file, hence all
// the fields can be public as nobody should be
// including this file.
- {
+{
Q3_CLASS_ENUMS ( kQ3ObjectTypePick, E3Pick, OpaqueTQ3Object )
public :
-
- // There is no extra data for this class
- } ;
+ TQ3PickBaseData baseInstanceData;
+};
@@ -140,12 +145,12 @@
// so it can be here in the .c file rather than in
// the .h file, hence all the fields can be public
// as nobody should be including this file
- {
+{
Q3_CLASS_ENUMS ( kQ3PickTypeWindowPoint, E3WindowPointPick, E3Pick )
public :
- TQ3PickUnionData instanceData ;
- } ;
+ TQ3WindowPointPickSpecificData instanceData ;
+} ;
@@ -153,12 +158,12 @@
// so it can be here in the .c file rather than in
// the .h file, hence all the fields can be public
// as nobody should be including this file
- {
+{
Q3_CLASS_ENUMS ( kQ3PickTypeWindowRect, E3WindowRectPick, E3Pick )
public :
- TQ3PickUnionData instanceData ;
- } ;
+ TQ3WindowRectPickSpecificData instanceData ;
+} ;
@@ -166,12 +171,12 @@
// so it can be here in the .c file rather than in
// the .h file, hence all the fields can be public
// as nobody should be including this file
- {
+{
Q3_CLASS_ENUMS ( kQ3PickTypeWorldRay, E3WorldRayPick, E3Pick )
public :
- TQ3PickUnionData instanceData ;
- } ;
+ TQ3WorldRayPickSpecificData instanceData ;
+} ;
@@ -531,15 +536,15 @@
// e3pick_hit_find : Find the nth pick hit in a list.
//-----------------------------------------------------------------------------
static TQ3PickHit *
-e3pick_hit_find(TQ3PickUnionData *pickInstanceData, TQ3Uns32 n)
+e3pick_hit_find(TQ3PickBaseData *pickInstanceData, TQ3Uns32 n)
{
// Check we're not out of range
if (n >= pickInstanceData->pickHits->size())
return(NULL);
- if (pickInstanceData->data.common.numHitsToReturn != kQ3ReturnAllHits)
+ if (pickInstanceData->commonData.numHitsToReturn != kQ3ReturnAllHits)
{
- if (n >= pickInstanceData->data.common.numHitsToReturn)
+ if (n >= pickInstanceData->commonData.numHitsToReturn)
return(NULL);
}
@@ -547,7 +552,7 @@
// just in time sort
if (!pickInstanceData->isSorted)
{
- switch (pickInstanceData->data.common.sort)
+ switch (pickInstanceData->commonData.sort)
{
case kQ3PickSortNearToFar:
std::sort( pickInstanceData->pickHits->begin(),
@@ -584,8 +589,6 @@
static void
e3pick_set_sort_mask(TQ3PickData *pickData)
{
-
-
// Turn on the distance flag if any kind of sorting is requested
if (pickData->sort != kQ3PickSortNone)
pickData->mask |= kQ3PickDetailMaskDistance;
@@ -595,21 +598,26 @@
+#pragma mark -
//=============================================================================
-// e3pick_windowpoint_new : Window point pick new method.
+// e3pick_new : Base pick new method.
//-----------------------------------------------------------------------------
static TQ3Status
-e3pick_windowpoint_new(TQ3Object theObject, void *privateData, const void *paramData)
-{ TQ3PickUnionData *instanceData = (TQ3PickUnionData *) privateData;
- const TQ3WindowPointPickData *pickData = (const TQ3WindowPointPickData *) paramData;
+e3pick_new(TQ3Object theObject, void *privateData, const void *paramData)
+{ TQ3PickBaseData* instanceData = (TQ3PickBaseData *) privateData;
+ const TQ3PickData *pickData = (const TQ3PickData *) paramData;
// Initialise our instance data
instanceData->pickHits = new std::vector<TQ3PickHit*>;
- instanceData->data.windowPointData = *pickData;
+ instanceData->commonData = *pickData;
+ instanceData->isSorted = false;
+ instanceData->vertexTolerance = 0.0f;
+ instanceData->edgeTolerance = 0.0f;
+ instanceData->faceTolerance = 0.0f;
- e3pick_set_sort_mask(&instanceData->data.windowPointData.data);
+ e3pick_set_sort_mask( &instanceData->commonData );
return(kQ3Success);
}
@@ -619,17 +627,17 @@
//=============================================================================
-// e3pick_windowpoint_delete : Window point pick delete method.
+// e3pick_delete : Base pick delete method.
//-----------------------------------------------------------------------------
static void
-e3pick_windowpoint_delete(TQ3Object theObject, void *privateData)
+e3pick_delete(TQ3Object theObject, void *privateData)
{
// Empty the pick list
E3Pick_EmptyHitList(theObject);
// Free data held by the instance data
- TQ3PickUnionData* instanceData = (TQ3PickUnionData*) privateData;
+ TQ3PickBaseData* instanceData = (TQ3PickBaseData*) privateData;
delete instanceData->pickHits;
instanceData->pickHits = NULL;
}
@@ -639,6 +647,69 @@
//=============================================================================
+// e3pick_metahandler : Base pick metahandler.
+//-----------------------------------------------------------------------------
+static TQ3XFunctionPointer
+e3pick_metahandler(TQ3XMethodType methodType)
+{ TQ3XFunctionPointer theMethod = NULL;
+
+
+
+ // Return our methods
+ switch (methodType) {
+ case kQ3XMethodTypeObjectNew:
+ theMethod = (TQ3XFunctionPointer) e3pick_new;
+ break;
+
+ case kQ3XMethodTypeObjectDelete:
+ theMethod = (TQ3XFunctionPointer) e3pick_delete;
+ break;
+ }
+
+ return(theMethod);
+}
+
+
+
+
+
+#pragma mark -
+//=============================================================================
+// e3pick_windowpoint_new : Window point pick new method.
+//-----------------------------------------------------------------------------
+static TQ3Status
+e3pick_windowpoint_new(TQ3Object theObject, void *privateData, const void *paramData)
+{
+ TQ3WindowPointPickSpecificData* instanceData = (TQ3WindowPointPickSpecificData *) privateData;
+ const TQ3WindowPointPickData *pickData = (const TQ3WindowPointPickData *) paramData;
+ E3Pick* parentOb = (E3Pick*) theObject;
+
+
+ // Initialise our instance data
+ instanceData->point = pickData->point;
+ parentOb->baseInstanceData.vertexTolerance = pickData->vertexTolerance;
+ parentOb->baseInstanceData.edgeTolerance = pickData->edgeTolerance;
+
+ return(kQ3Success);
+}
+
+
+
+
+
+//=============================================================================
+// e3pick_windowpoint_delete : Window point pick delete method.
+//-----------------------------------------------------------------------------
+static void
+e3pick_windowpoint_delete(TQ3Object theObject, void *privateData)
+{
+}
+
+
+
+
+
+//=============================================================================
// e3pick_windowpoint_metahandler : Window point pick metahandler.
//-----------------------------------------------------------------------------
static TQ3XFunctionPointer
@@ -665,19 +736,20 @@
+#pragma mark -
//=============================================================================
// e3pick_windowrect_new : Window rect pick new method.
//-----------------------------------------------------------------------------
static TQ3Status
e3pick_windowrect_new(TQ3Object theObject, void *privateData, const void *paramData)
-{ TQ3PickUnionData *instanceData = (TQ3PickUnionData *) privateData;
+{
+ TQ3Area *instanceData = (TQ3Area *) privateData;
const TQ3WindowRectPickData *pickData = (const TQ3WindowRectPickData *) paramData;
// Initialise our instance data
- instanceData->pickHits = new std::vector<TQ3PickHit*>;
- instanceData->data.windowRectData = *pickData;
+ *instanceData = pickData->rect;
return(kQ3Success);
}
@@ -692,14 +764,6 @@
static void
e3pick_windowrect_delete(TQ3Object theObject, void *privateData)
{
- // Empty the pick list
- E3Pick_EmptyHitList(theObject);
-
-
- // Free data held by the instance data
- TQ3PickUnionData* instanceData = (TQ3PickUnionData*) privateData;
- delete instanceData->pickHits;
- instanceData->pickHits = NULL;
}
@@ -732,22 +796,23 @@
-
+#pragma mark -
//=============================================================================
// e3pick_worldray_new : World ray pick new method.
//-----------------------------------------------------------------------------
static TQ3Status
e3pick_worldray_new(TQ3Object theObject, void *privateData, const void *paramData)
-{ TQ3PickUnionData *instanceData = (TQ3PickUnionData *) privateData;
+{
+ TQ3WorldRayPickSpecificData* instanceData = (TQ3WorldRayPickSpecificData *) privateData;
const TQ3WorldRayPickData *pickData = (const TQ3WorldRayPickDa...
[truncated message content] |
