gwnavruntime/navmesh/intersections.h Source File

intersections.h
Go to the documentation of this file.
1 /*
2 * Copyright 2015 Autodesk, Inc. All rights reserved.
3 * Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 // ---------- Primary contact: JUBA - secondary contact: NOBODY
8 #ifndef Navigation_Intersections_H
9 #define Navigation_Intersections_H
10 
11 #include "gwnavruntime/navmesh/navmeshtypes.h"
12 #include "gwnavruntime/math/orientedbox2d.h"
13 #include "gwnavruntime/math/box2f.h"
14 #include "gwnavruntime/basesystem/logger.h"
15 
16 namespace Kaim
17 {
18 
19 
20 class Intersections // class with static functions only
21 {
22 public :
23  enum Clockwiseness { Clockwiseness_CCW = 0, Clockwiseness_CW = 1 };
24 
25 public:
26 
28 
29  // compute if vertical line that contains p intersects the plane defined by the triangle
30  static bool IsPointInsideTriangle2d(const Vec3f& p,const Vec3f& v1, const Vec3f& v2, const Vec3f& v3);
31  static bool IsPointInsideTriangle2d(const CoordPos64& p,const CoordPos64& v1, const CoordPos64& v2, const CoordPos64& v3);
32  static bool IsPointInsideTriangle2d(const CoordPos& p,const CoordPos& v1, const CoordPos& v2, const CoordPos& v3);
33  static bool IsOnTheLeftOfTheEdge2d(const CoordPos& p, const CoordPos& v1, const CoordPos& v1v2);
34  static bool IsStrictlyOnTheLeftOfTheEdge2d(const CoordPos& p, const CoordPos& v1, const CoordPos& v1v2);
35  static bool IsOnTheLeftOfTheEdge2d(const CoordPos64& p, const CoordPos64& v1, const CoordPos64& v1v2);
36  static bool IsStrictlyOnTheLeftOfTheEdge2d(const CoordPos64& p, const CoordPos64& v1, const CoordPos64& v1v2);
37 
38  static bool IsPointInsideTriangle2d_NotUnique(const CoordPos& p, const CoordPos& v1, const CoordPos& v2, const CoordPos& v3);
39 
40  // compute if p is on left of or uniquely aligned on v1v2,
41  // hence beware that if p is on v1v2, it won't be considered on v2v1.
42  static bool IsOnTheLeftOfSegment2d(const Vec3f& p, const Vec3f& v1, const Vec3f& v2);
43  static bool IsOnTheLeftOfSegment2d(const Vec2f& p, const Vec2f& v1, const Vec2f& v2);
44  // compute if p is strictly on left of the vector v1v2
45  static bool IsStrictlyOnTheLeftOfSegment2d(const Vec3f& p, const Vec3f& v1, const Vec3f& v2);
46  static bool IsStrictlyOnTheLeftOfSegment2d(const Vec2f& p, const Vec2f& v1, const Vec2f& v2);
47 
49 
50  // Intersections
51  // we test the intersection between convex polylines by using the Separated-Axes Theorem
52  static bool AABBVsAABB2d(const Box2LL& box1, const Box2LL& box2);
53  static bool AABBVsAABB2d(const Box2i& box1, const Box2i& box2);
54  static bool AABBVsAABB2d(const Box2f& box1, const Box2f& box2);
55  static bool AABBVsAABB3d(const Box3f& box1, const Box3f& box2);
56  static bool AABBVsAABB2d(const Box2f& box1, const Box3f& box2);
57 
59 
60  static bool AABBVsOrientedBox2d(const OrientedBox2d& orientedBox2d, const Box2f& box);
61  static bool AABBVsOrientedBox2d(const CoordPos64& o1, const Vec2LL& lengthVec, const Vec2LL& widthVec, const CoordBox64& aABbox);
62 
63  static bool SegmentVsDisk2d(const Vec3f& a, const Vec3f& b, const Vec3f& c, KyFloat32 radius);
64  static bool SegmentVsDisk2d(const Vec3f& a, const Vec3f& b, const Vec3f& c, KyFloat32 radius, Vec3f& intersection);
65 
66  // find first intersection between segment and circle arc encountered along ab
67  static bool SegmentVsCircle2d(const Vec3f& a, const Vec3f& b, const Vec3f& c, KyFloat32 radius, Vec3f& firstIntersection);
68 
69  // find first intersection between segment and circle arc respecting the rotation of the circle arc
70  // fullTurnToleranceSin is very technical: default is 0.01 ( = sin(~s0.57 Degrees )), must be let very small
71  static bool SegmentVsOrientedCircleArc2d(const Vec3f& segmentStart, const Vec3f& segmentEnd,
72  const Vec3f& circleCenter, KyFloat32 radius, Clockwiseness clockwiseness,
73  const Vec3f& circleArcStart, const Vec3f& circleArcEnd, Vec3f& firstIntersection, KyFloat32 fullTurnToleranceSin = 0.01f);
74 
75  static bool SegmentVsConvexQuad2D(const Vec3f& v1, const Vec3f& v2,
76  const Vec3f& pointOnStartSideLeft, const Vec3f& pointOnStartSideRight, const Vec3f& pointOnEndSideRight, const Vec3f& pointOnEndSideLeft);
77 
78  static bool SegmentVsOrientedBox2d(const Vec3f& v1, const Vec3f& v2, const OrientedBox2d& orientedBox2d);
79  static bool SegmentVsOrientedBox2d(const CoordPos64& v1, const CoordPos64& v2, const CoordPos64& o1, const Vec2LL& lengthVec, const Vec2LL& widthVec);
80 
81  // used during the Disk propagation. Tells is the segment is inside the box and the extended box
82  static bool SegmentVsExtendedOrientedBox2d(const Vec3f& v1, const Vec3f& v2, const OrientedBox2d& orientedBox2d, const KyFloat32 extralength, bool& outsideExtendedBox);
83 
84  static bool SegmentVsAABB2d(const Vec3f& v1, const Vec3f& v2, const Box2f& aabb2d);
85  static bool SegmentVsAABB2d(const Vec2i& v1, const Vec2i& v2, const Box2i& aabb2d);
86  static bool SegmentVsAABB2d(const CoordPos64& v1, const CoordPos64& v2, const CoordBox64& aabb2d);
87 
88  static bool SegmentVsCapsule2d(const Vec3f& v1, const Vec3f& v2, const Vec3f& center, const KyFloat32 radius, const Vec2f& normalizedDir2D, const KyFloat32 distCast);
89  // this function should be call by a visitor to avoid creating and computing orientedBox2d, center1 and center2 at each call as in the first function SegmentVsCapsule2d
90  static bool SegmentVsCapsule2d(const Vec3f& v1, const Vec3f& v2, const OrientedBox2d& orientedBox2d, const Vec3f& center1, const Vec3f& center2, const KyFloat32 radius);
91 
92  // test intersection between a segment and a Capsule that is truncated on the left and of the right along the middle axis.
93  static bool SegmentVsCrossSectionCapsule2d(const Vec3f& v1, const Vec3f& v2, const Vec3f& center, const KyFloat32 radius, const Vec2f& normalizedDir2D, const KyFloat32 distCast, const KyFloat32 distOnRight, const KyFloat32 distOnLeft);
94  // this function should be call by a visitor to avoid creating and computing 2 BoxBostacle and the center of the end Disk of the capsule
95  static bool SegmentVsCrossSectionCapsule2d(const Vec3f& v1, const Vec3f& v2, const OrientedBox2d& box, const Vec3f& centerOfEndDisk, const KyFloat32 radius, const OrientedBox2d& boxOfEndDisk);
96 
97  static bool SegmentVsTriangle2d(const Vec3f& a, const Vec3f& b, const Vec3f& v1, const Vec3f& v2, const Vec3f& v3);
98  static bool SegmentVsTriangle2d(const Vec2f& a, const Vec2f& b, const Vec2f& v1, const Vec2f& v2, const Vec2f& v3);
99  static bool SegmentVsTriangle2d(const CoordPos64& v1, const CoordPos64& v2, const CoordPos64& t1, const CoordPos64& t2, const CoordPos64& t3);
100 
101  static bool TriangleVsOrientedBox2d(const Vec3f& v1, const Vec3f& v2, const Vec3f& v3, const OrientedBox2d& orientedBox2d);
102  static bool TriangleVsOrientedBox2d(const CoordPos64& v1, const CoordPos64& v2, const CoordPos64& v3, const CoordPos64& o1, const Vec2LL& lengthVec, const Vec2LL& widthVec);
103 
104 
105  static bool TriangleVsTriangle2d(const Vec3f& v1, const Vec3f& v2, const Vec3f& v3, const Vec3f& u1, const Vec3f& u2, const Vec3f& u3);
106 
107 
108  static bool TriangleVsAABB2d(const Vec3f& v1, const Vec3f& v2, const Vec3f& v3, const Box2f& box);
109  static bool OverlappingOrientedBox2dVsTriangle3D(const Vec3f& v1, const Vec3f& v2, const Vec3f& v3, const OrientedBox2d& orientedBox2d, const KyFloat32 toleranceBelow, const KyFloat32 toleranceAbove);
110 
111  static bool SegmentVsSegment2d(const Vec2f& a, const Vec2f& b, const Vec2f& c, const Vec2f& d);
112  static bool SegmentVsSegment2d(const Vec2f& a, const Vec2f& b, const Vec2f& c, const Vec2f& d, Vec2f& intersection);
113 
114  static bool SegmentVsSegment2d(const Vec3f& a, const Vec3f& b, const Vec3f& c, const Vec3f& d);
115  static bool SegmentVsSegment2d(const Vec3f& a, const Vec3f& b, const Vec3f& c, const Vec3f& d, Vec3f& intersection);
116 
117  static bool SegmentVsSegment2d(const CoordPos& a, const CoordPos& b, const CoordPos& c, const CoordPos& d);
118  static bool SegmentVsSegment2d(const CoordPos64& a, const CoordPos64& b, const CoordPos64& c, const CoordPos64& d);
119 
120 
122  // segmebt [a,b] and segment [c,d]
123  // a < b && c < d for these functions
124  //
125  static bool DoSegmentsHaveOneComonExtremity(const CoordPos& a, const CoordPos& b, const CoordPos& c, const CoordPos& d);
126  static bool IsPointEqualToOneSegmentExtremity(const CoordPos& p, const CoordPos& a, const CoordPos& b, const CoordPos& c, const CoordPos& d);
127  static bool SegmentVsSegment2d(const CoordPos& a, const CoordPos& b, const CoordPos& c, const CoordPos& d, CoordPos& intersection);
128  static bool SegmentVsSegment2d(const CoordPos64& a, const CoordPos64& b, const CoordPos64& c, const CoordPos64& d, CoordPos64& intersection);
129  static bool SegmentVsSegment2d_Rounded(const CoordPos& a, const CoordPos& b, const CoordPos& c, const CoordPos& d, CoordPos& intersection);
130  static bool SegmentVsSegment2d_Rounded(const CoordPos64& a, const CoordPos64& b, const CoordPos64& c, const CoordPos64& d, CoordPos64& intersection);
131  static bool SegmentVsSegment2dWithoutExtremities_Rounded(const CoordPos& a, const CoordPos& b, const CoordPos& c, const CoordPos& d, CoordPos& intersection);
132  static bool SegmentVsSegment2dWithoutExtremities_Rounded(const CoordPos64& a, const CoordPos64& b, const CoordPos64& c, const CoordPos64& d, CoordPos64& intersection);
133 
134  static bool LineVsLine2d(const Vec3f& a, const Vec3f& b, const Vec3f& c, const Vec3f& d);
135  static bool LineVsLine2d(const Vec3f& a, const Vec3f& b, const Vec3f& c, const Vec3f& d, Vec3f& intersection);
136  static bool LineVsLine2d(const Vec2f& a, const Vec2f& b, const Vec2f& c, const Vec2f& d, Vec2f& intersection);
137 
138  static bool LineVsLine2d(const CoordPos64& a, const CoordPos64& b, const CoordPos64& c, const CoordPos64& d);
139  static bool LineVsLine2d(const CoordPos64& a, const CoordPos64& b, const CoordPos64& c, const CoordPos64& d, CoordPos64& intersection, bool& linesAreParallel);
140 
141  // these two functions compute the x or Y value of the intersection a 2d line and a vertical/horizontal line
142  // It assumes that there is an intersection, it does not test if there is an intersection.
143  static KyFloat32 GetYValueOfLineVsVerticalAxis(const Vec2f& pos1, const Vec2f& pos2, KyFloat32 wantedX);
144  static KyFloat32 GetXValueOfLineVsHorizontalAxis(const Vec2f& pos1, const Vec2f& pos2, KyFloat32 wantedY);
145 
146  // compute the altitude of point of intersection the vertical line that contains p and the plane defined by the triangle
147  static KyFloat32 ComputeAltitudeOfPointInPlane(const Vec2f& p,const Vec3f& planePoint, const Vec3f& planeNormal);
148  static KyFloat32 ComputeAltitudeOfPointInTriangle(const Vec3f& p,const Vec3f& v1, const Vec3f& v2, const Vec3f& v3);
149  static KyFloat32 ComputeAltitudeOfPointInTriangle(const Vec2f& p,const Vec3f& v1, const Vec3f& v2, const Vec3f& v3);
150 
151  // triangle v1, v2, v3 is CounterClockWise
152  static KyFloat32 ComputeInCircumCircleDeterminant(const Vec3f& v1, const Vec3f& v2, const Vec3f& v3, const Vec3f& p);
153  static bool IsPointInsideCircumCircle2d(const Vec3f& v1, const Vec3f& v2, const Vec3f& v3, const Vec3f& p);
154  static bool IsPointStrictlyInsideCircumCircle2d(const Vec3f& v1, const Vec3f& v2, const Vec3f& v3, const Vec3f& p);
155 
156  static KyInt64 ComputeInCircumCircleDeterminant(const CoordPos& a, const CoordPos& b, const CoordPos& c, const CoordPos& d);
157  static bool IsPointInsideCircumCircle2d(const CoordPos& v1, const CoordPos& v2, const CoordPos& v3, const CoordPos& p);
158  static bool IsPointStrictlyInsideCircumCircle2d(const CoordPos& v1, const CoordPos& v2, const CoordPos& v3, const CoordPos& p);
159 
160 public: // internal
161  static void SegmentVsSegment2d_RoundedIntersection(const CoordPos64& a, const CoordPos64& b, const CoordPos64& c, const CoordPos64& d, CoordPos64& intersection);
162  static void SegmentVsSegment2d_Intersection(const CoordPos64& a, const CoordPos64& b, const CoordPos64& c, const CoordPos64& d, CoordPos64& intersection);
163  static void SegmentVsSegment2d_RoundedIntersection(const CoordPos& a, const CoordPos& b, const CoordPos& c, const CoordPos& d, CoordPos& intersection);
164  static void SegmentVsSegment2d_Intersection(const CoordPos& a, const CoordPos& b, const CoordPos& c, const CoordPos& d, CoordPos& intersection);
165 };
166 
167 }
168 
169 #include "gwnavruntime/navmesh/intersections.inl"
170 
171 #endif // Navigation_Intersections_H
172 
Kaim::CoordBox64
Box2LL CoordBox64
A type that represents a bounding box in the integer 2D grid.
Definition: navmeshtypes.h:20
Kaim::CoordPos
Vec2i CoordPos
A type that represents the position of a point within the 2D integer grid.
Definition: navmeshtypes.h:23
Kaim::CoordPos64
Vec2LL CoordPos64
A type that represents the position of a point within the 2D integer grid.
Definition: navmeshtypes.h:19
Kaim
Definition: gamekitcrowddispersion.h:20
KyInt64
__int64 KyInt64
Type used internally to represent a 64-bit integer.
Definition: types.h:37
KyFloat32
float KyFloat32
Type used internally to represent a 32-bit floating-point number.
Definition: types.h:43
Please send us your comment about this page