gwnavruntime/navmesh/intersections.h Source File

intersections.h
Go to the documentation of this file.
1 /*
2 * Copyright 2016 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 #pragma once
8 
9 #include "gwnavruntime/math/vec2i.h"
10 #include "gwnavruntime/math/box2i.h"
11 #include "gwnavruntime/math/vec2ll.h"
12 #include "gwnavruntime/math/box2ll.h"
13 #include "gwnavruntime/math/vec2f.h"
14 #include "gwnavruntime/math/box2f.h"
15 #include "gwnavruntime/math/box3f.h"
16 #include "gwnavruntime/math/orientedbox2d.h"
17 #include "gwnavruntime/basesystem/logger.h"
18 
19 namespace Kaim
20 {
21 namespace Math
22 {
23 // ASYMMETRIC positioning integer, if P on AB, then P NOT on BA
24 bool IsLeftAsymEdge2i(const Vec2i& P, const Vec2i& A, const Vec2i& AB);
25 bool IsLeftAsymEdge2i(const Vec2LL& P, const Vec2LL& A, const Vec2LL& AB);
26 bool InTriangleAsym2i(const Vec2LL& P, const Vec2LL& A, const Vec2LL& B, const Vec2LL& C);
27 bool InTriangleAsym2i(const Vec2i& P, const Vec2i& A, const Vec2i& B, const Vec2i& C);
28 
29 // ASYMMETRIC positioning float, if P on AB, then P NOT on BA
30 bool IsLeftAsym2f(const Vec3f& P, const Vec3f& A, const Vec3f& B);
31 bool IsLeftAsym2f(const Vec2f& P, const Vec2f& A, const Vec2f& B);
32 bool InTriangleAsym2f(const Vec3f& P, const Vec3f& A, const Vec3f& B, const Vec3f& C); // used in closestpoint.cpp
33 
34 // SYMMETRIC positioning, if P on AB, then P on BA AS WELL
35 bool IsLeftStrict2f(const Vec3f& P, const Vec3f& A, const Vec3f& B);
36 bool IsLeftStrict2f(const Vec2f& P, const Vec2f& A, const Vec2f& B);
37 
38 // SYMMETRIC positioning, if P on AB, then P on BA AS WELL
39 bool IsLeftStrictEdge2LL(const Vec2LL& P, const Vec2LL& A, const Vec2LL& AB);
40 bool InTriangle2i(const Vec2i& P, const Vec2i& A, const Vec2i& B, const Vec2i& C);
41 
42 // separating integer
43 bool IsSegmentVsSegment2i(const Vec2i& A, const Vec2i& B, const Vec2i& C, const Vec2i& D);
44 bool IsSegmentVsSegment2LL(const Vec2LL& A, const Vec2LL& B, const Vec2LL& C, const Vec2LL& D);
45 bool IsSegmentVsBox2i(const Vec2i& A, const Vec2i& B, const Box2i& box2i);
46 bool IsSegmentVsBox2LL(const Vec2LL& A, const Vec2LL& B, const Box2LL& box2LL);
47 bool IsSegmentVsOrientedBox2LL(const Vec2LL& A, const Vec2LL& B, const Vec2LL& corner, const Vec2LL& vfwd, const Vec2LL& vleft);
48 bool IsBoxVsBox2i(const Box2i& box1, const Box2i& box2);
49 bool IsBoxVsBox2LL(const Box2LL& box1, const Box2LL& box2);
50 bool IsTriangleVsOrientedBox2LL(const Vec2LL& A, const Vec2LL& B, const Vec2LL& C, const Vec2LL& corner, const Vec2LL& vfwd, const Vec2LL& vleft);
51 
52 // separating float
53 bool IsSegmentVsSegment2f(const Vec2f& A, const Vec2f& B, const Vec2f& C, const Vec2f& D);
54 bool IsSegmentVsSegment2f(const Vec3f& A, const Vec3f& B, const Vec3f& C, const Vec3f& D);
55 bool IsSegmentVsTriangle2f(const Vec3f& A, const Vec3f& B, const Vec3f& T1, const Vec3f& T2, const Vec3f& T3);
56 bool IsSegmentVsTriangle2f(const Vec2f& A, const Vec2f& B, const Vec2f& T1, const Vec2f& T2, const Vec2f& T3);
57 bool IsSegmentVsConvexQuad2f(const Vec3f& A, const Vec3f& B, const Vec3f& Q1, const Vec3f& Q2, const Vec3f& Q3, const Vec3f& Q4);
58 bool IsSegmentVsOrientedBox2f(const Vec3f& A, const Vec3f& B, const OrientedBox2d& obox);
59 bool IsBoxVsBox3f(const Box3f& box1, const Box3f& box2);
60 bool IsBoxVsBox2f(const Box2f& box1, const Box3f& box2);
61 bool IsBoxVsBox2f(const Box2f& box1, const Box2f& box2);
62 bool IsTriangleVsBox2f(const Vec3f& A, const Vec3f& B, const Vec3f& C, const Box2f& box);
63 
64 // SegmentVsSegment floating point intersection
65 bool SegmentVsSegment2f(const Vec2f& A, const Vec2f& B, const Vec2f& C, const Vec2f& D, Vec2f& I);
66 bool SegmentVsSegment2f(const Vec3f& A, const Vec3f& B, const Vec3f& C, const Vec3f& D, Vec3f& I);
67 
68 // precondition A < B && C < D
69 bool DoSegmentsHaveOneCommonExtremity(const Vec2i& A, const Vec2i& B, const Vec2i& C, const Vec2i& D);
70 bool IsPointEqualToOneSegmentExtremity(const Vec2i& P, const Vec2i& A, const Vec2i& B, const Vec2i& C, const Vec2i& D);
71 
72 // SegmentVsSegment integer intersection
73 bool SegmentVsSegment2LL_TowardZero(const Vec2LL& A, const Vec2LL& B, const Vec2LL& C, const Vec2LL& D, Vec2LL& I); // used only in InsidePosFromOutsidePosQuery
74 bool SegmentVsSegment2i_Nearest(const Vec2i& A, const Vec2i& B, const Vec2i& C, const Vec2i& D, Vec2i& I); // calls the 64bits version
75 bool SegmentVsSegment2LL_Nearest(const Vec2LL& A, const Vec2LL& B, const Vec2LL& C, const Vec2LL& D, Vec2LL& I); //
76 bool SegmentVsSegment2i_Nearest_NoEnd(const Vec2i& A, const Vec2i& B, const Vec2i& C, const Vec2i& D, Vec2i& I);
77 
78 // preconditions: AB and CD do intersect and have no common end points
79 void SegmentVsSegment2i_Nearest_(const Vec2i& A, const Vec2i& B, const Vec2i& C, const Vec2i& D, Vec2i& I); // calls the 64bits version
80 
81 void SegmentVsSegment2LL_TowardZero_(const Vec2LL& A, const Vec2LL& B, const Vec2LL& C, const Vec2LL& D, Vec2LL& I); // preconditions: AB and CD do intersect
82 void SegmentVsSegment2i_(const Vec2i& A, const Vec2i& B, const Vec2i& C, const Vec2i& D, Vec2i& I); // calls the 64bits version
83 
84 // preconditions: AB and CD do intersect and have no common end points
85 void SegmentVsSegment2LL_Nearest_(const Vec2LL& A, const Vec2LL& B, const Vec2LL& C, const Vec2LL& D, Vec2LL& I);
86 
87 // Lines
88 bool LineVsLine2f(const Vec3f& A, const Vec3f& B, const Vec3f& C, const Vec3f& D);
89 bool LineVsLine2f(const Vec3f& A, const Vec3f& B, const Vec3f& C, const Vec3f& D, Vec3f& I);
90 bool LineVsLine2f(const Vec2f& A, const Vec2f& B, const Vec2f& C, const Vec2f& D, Vec2f& I);
91 
92 bool LineVsLine2LL(const Vec2LL& A, const Vec2LL& B, const Vec2LL& C, const Vec2LL& D);
93 bool LineVsLine2LL(const Vec2LL& A, const Vec2LL& B, const Vec2LL& C, const Vec2LL& D, Vec2LL& I, bool& linesAreParallel);
94 
95 // y = ax + b
96 KyFloat32 AffineAB_Y(const Vec2f& A, const Vec2f& B, KyFloat32 x); // ((B.y - A.y) / (B.x - A.x)) * (x - A.x) + A.y;
97 KyFloat32 AffineAB_X(const Vec2f& A, const Vec2f& B, KyFloat32 y); // ((B.x - A.x) / (B.y - A.y)) * (y - A.y) + A.x;
98 KyFloat32 AffineAd_Y(const Vec2f& A, const Vec2f& delta, KyFloat32 x); // (delta.y / delta.x) * (x - A.x) + A.y;
99 
100 // compute the altitude of point of intersection the vertical line that contains p and the plane defined by the triangle
101 KyFloat32 OnPlaneZ(const Vec2f& P, const Vec3f& planePoint, const Vec3f& planeNormal);
102 KyFloat32 OnTriangleZ(const Vec2f& P, const Vec3f& A, const Vec3f& B, const Vec3f& C);
103 inline KyFloat32 OnTriangleZ(const Vec3f& P, const Vec3f& A, const Vec3f& B, const Vec3f& C) { return OnTriangleZ(P.Get2d(), A, B, C); }
104 
105 // circum circle
106 KyInt64 InCircleDeterminant2i(const Vec2i& A, const Vec2i& B, const Vec2i& C, const Vec2i& P);
107 inline bool InCircle2i(const Vec2i& A, const Vec2i& B, const Vec2i& C, const Vec2i& P) { return InCircleDeterminant2i(A, B, C, P) >= 0; }
108 inline bool InCircleStrict2i(const Vec2i& A, const Vec2i& B, const Vec2i& C, const Vec2i& P) { return InCircleDeterminant2i(A, B, C, P) > 0; }
109 
110 //---------------------------------------------------------
111 // disk, circle, capsule
112 bool SegmentVsDisk2f(const Vec3f& A, const Vec3f& B, const Vec3f& C, KyFloat32 r);
113 bool SegmentVsDisk2f(const Vec3f& A, const Vec3f& B, const Vec3f& C, KyFloat32 r, Vec3f& I);
114 
115 // find first intersection between segment and circle arc respecting the rotation of the circle arc
116 // fullTurnToleranceSin is very technical: default is 0.01 ( = sin(~s0.57 Degrees )), must be let very small
117 bool SegmentVsOrientedCircleArc2f(const Vec3f& segmentStart, const Vec3f& segmentEnd, const Vec3f& circleCenter, KyFloat32 radius, Winding::Enum winding,
118  const Vec3f& circleArcStart, const Vec3f& circleArcEnd, Vec3f& firstIntersection, KyFloat32 fullTurnToleranceSin = 0.01f);
119 
120 // used during the Disk propagation. Tells is the segment is inside the box and the extended box
121 bool SegmentVsExtendedOrientedBox2f(const Vec3f& A, const Vec3f& B, const OrientedBox2d& obox, const KyFloat32 extraLength, bool& outsideExtendedBox);
122 
123 bool SegmentVsCapsule2f(const Vec3f& A, const Vec3f& B, const Vec3f& P, const KyFloat32 r, const Vec2f& dir, const KyFloat32 length);
124 
125 // 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 SegmentVsCapsule2f
126 bool SegmentVsCapsule2f(const Vec3f& A, const Vec3f& B, const OrientedBox2d& obox, const Vec3f& center1, const Vec3f& center2, const KyFloat32 radius);
127 
128 // test intersection between a segment and a Capsule that is truncated on the left and of the right along the middle axis.
129 bool SegmentVsCrossSectionCapsule2f(const Vec3f& A, const Vec3f& B, const Vec3f& P, const KyFloat32 r, const Vec2f& dir, const KyFloat32 length, const KyFloat32 distOnRight,
130  const KyFloat32 distOnLeft);
131 
132 // 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
133 bool SegmentVsCrossSectionCapsule2f(const Vec3f& A, const Vec3f& B, const OrientedBox2d& obox, const Vec3f& centerOfEndDisk, const KyFloat32 radius,
134  const OrientedBox2d& boxOfEndDisk);
135 }
136 }
137 
138 #include "gwnavruntime/navmesh/intersections.inl"
139 
140 
KyInt64
std::int64_t KyInt64
int64_t
Definition: types.h:25
Kaim
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17
KyFloat32
float KyFloat32
float
Definition: types.h:32
Please send us your comment about this page