Jolt Physics
A multi core friendly Game Physics Engine
Loading...
Searching...
No Matches
ClipPoly.h
Go to the documentation of this file.
1// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
2// SPDX-FileCopyrightText: 2021 Jorrit Rouwe
3// SPDX-License-Identifier: MIT
4
5#pragma once
6
8
10
13template <class VERTEX_ARRAY>
14void ClipPolyVsPlane(const VERTEX_ARRAY &inPolygonToClip, Vec3Arg inPlaneOrigin, Vec3Arg inPlaneNormal, VERTEX_ARRAY &outClippedPolygon)
15{
16 JPH_ASSERT(inPolygonToClip.size() >= 2);
17 JPH_ASSERT(outClippedPolygon.empty());
18
19 // Determine state of last point
20 Vec3 e1 = inPolygonToClip[inPolygonToClip.size() - 1];
21 float prev_num = (inPlaneOrigin - e1).Dot(inPlaneNormal);
22 bool prev_inside = prev_num < 0.0f;
23
24 // Loop through all vertices
25 for (typename VERTEX_ARRAY::size_type j = 0; j < inPolygonToClip.size(); ++j)
26 {
27 // Check if second point is inside
28 Vec3Arg e2 = inPolygonToClip[j];
29 float num = (inPlaneOrigin - e2).Dot(inPlaneNormal);
30 bool cur_inside = num < 0.0f;
31
32 // In -> Out or Out -> In: Add point on clipping plane
33 if (cur_inside != prev_inside)
34 {
35 // Solve: (X - inPlaneOrigin) . inPlaneNormal = 0 and X = e1 + t * (e2 - e1) for X
36 Vec3 e12 = e2 - e1;
37 float denom = e12.Dot(inPlaneNormal);
38 if (denom != 0.0f)
39 outClippedPolygon.push_back(e1 + (prev_num / denom) * e12);
40 else
41 cur_inside = prev_inside; // Edge is parallel to plane, treat point as if it were on the same side as the last point
42 }
43
44 // Point inside, add it
45 if (cur_inside)
46 outClippedPolygon.push_back(e2);
47
48 // Update previous state
49 prev_num = num;
50 prev_inside = cur_inside;
51 e1 = e2;
52 }
53}
54
61template <class VERTEX_ARRAY>
62void ClipPolyVsPoly(const VERTEX_ARRAY &inPolygonToClip, const VERTEX_ARRAY &inClippingPolygon, Vec3Arg inClippingPolygonNormal, VERTEX_ARRAY &outClippedPolygon)
63{
64 JPH_ASSERT(inPolygonToClip.size() >= 2);
65 JPH_ASSERT(inClippingPolygon.size() >= 3);
66
67 VERTEX_ARRAY tmp_vertices[2];
68 int tmp_vertices_idx = 0;
69
70 for (typename VERTEX_ARRAY::size_type i = 0; i < inClippingPolygon.size(); ++i)
71 {
72 // Get edge to clip against
73 Vec3 clip_e1 = inClippingPolygon[i];
74 Vec3 clip_e2 = inClippingPolygon[(i + 1) % inClippingPolygon.size()];
75 Vec3 clip_normal = inClippingPolygonNormal.Cross(clip_e2 - clip_e1); // Pointing inward to the clipping polygon
76
77 // Get source and target polygon
78 const VERTEX_ARRAY &src_polygon = (i == 0)? inPolygonToClip : tmp_vertices[tmp_vertices_idx];
79 tmp_vertices_idx ^= 1;
80 VERTEX_ARRAY &tgt_polygon = (i == inClippingPolygon.size() - 1)? outClippedPolygon : tmp_vertices[tmp_vertices_idx];
81 tgt_polygon.clear();
82
83 // Clip against the edge
84 ClipPolyVsPlane(src_polygon, clip_e1, clip_normal, tgt_polygon);
85
86 // Break out if no polygon left
87 if (tgt_polygon.size() < 3)
88 {
89 outClippedPolygon.clear();
90 break;
91 }
92 }
93}
94
97template <class VERTEX_ARRAY>
98void ClipPolyVsEdge(const VERTEX_ARRAY &inPolygonToClip, Vec3Arg inEdgeVertex1, Vec3Arg inEdgeVertex2, Vec3Arg inClippingEdgeNormal, VERTEX_ARRAY &outClippedPolygon)
99{
100 JPH_ASSERT(inPolygonToClip.size() >= 3);
101 JPH_ASSERT(outClippedPolygon.empty());
102
103 // Get normal that is perpendicular to the edge and the clipping edge normal
104 Vec3 edge = inEdgeVertex2 - inEdgeVertex1;
105 Vec3 edge_normal = inClippingEdgeNormal.Cross(edge);
106
107 // Project vertices of edge on inPolygonToClip
108 Vec3 polygon_normal = (inPolygonToClip[2] - inPolygonToClip[0]).Cross(inPolygonToClip[1] - inPolygonToClip[0]);
109 float polygon_normal_len_sq = polygon_normal.LengthSq();
110 Vec3 v1 = inEdgeVertex1 + polygon_normal.Dot(inPolygonToClip[0] - inEdgeVertex1) * polygon_normal / polygon_normal_len_sq;
111 Vec3 v2 = inEdgeVertex2 + polygon_normal.Dot(inPolygonToClip[0] - inEdgeVertex2) * polygon_normal / polygon_normal_len_sq;
112 Vec3 v12 = v2 - v1;
113 float v12_len_sq = v12.LengthSq();
114
115 // Determine state of last point
116 Vec3 e1 = inPolygonToClip[inPolygonToClip.size() - 1];
117 float prev_num = (inEdgeVertex1 - e1).Dot(edge_normal);
118 bool prev_inside = prev_num < 0.0f;
119
120 // Loop through all vertices
121 for (typename VERTEX_ARRAY::size_type j = 0; j < inPolygonToClip.size(); ++j)
122 {
123 // Check if second point is inside
124 Vec3 e2 = inPolygonToClip[j];
125 float num = (inEdgeVertex1 - e2).Dot(edge_normal);
126 bool cur_inside = num < 0.0f;
127
128 // In -> Out or Out -> In: Add point on clipping plane
129 if (cur_inside != prev_inside)
130 {
131 // Solve: (X - inPlaneOrigin) . inPlaneNormal = 0 and X = e1 + t * (e2 - e1) for X
132 Vec3 e12 = e2 - e1;
133 float denom = e12.Dot(edge_normal);
134 Vec3 clipped_point = e1 + (prev_num / denom) * e12;
135
136 // Project point on line segment v1, v2 so see if it falls outside if the edge
137 float projection = (clipped_point - v1).Dot(v12);
138 if (projection < 0.0f)
139 outClippedPolygon.push_back(v1);
140 else if (projection > v12_len_sq)
141 outClippedPolygon.push_back(v2);
142 else
143 outClippedPolygon.push_back(clipped_point);
144 }
145
146 // Update previous state
147 prev_num = num;
148 prev_inside = cur_inside;
149 e1 = e2;
150 }
151}
152
155template <class VERTEX_ARRAY>
156void ClipPolyVsAABox(const VERTEX_ARRAY &inPolygonToClip, const AABox &inAABox, VERTEX_ARRAY &outClippedPolygon)
157{
158 JPH_ASSERT(inPolygonToClip.size() >= 2);
159
160 VERTEX_ARRAY tmp_vertices[2];
161 int tmp_vertices_idx = 0;
162
163 for (int coord = 0; coord < 3; ++coord)
164 for (int side = 0; side < 2; ++side)
165 {
166 // Get plane to clip against
167 Vec3 origin = Vec3::sZero(), normal = Vec3::sZero();
168 if (side == 0)
169 {
170 normal.SetComponent(coord, 1.0f);
171 origin.SetComponent(coord, inAABox.mMin[coord]);
172 }
173 else
174 {
175 normal.SetComponent(coord, -1.0f);
176 origin.SetComponent(coord, inAABox.mMax[coord]);
177 }
178
179 // Get source and target polygon
180 const VERTEX_ARRAY &src_polygon = tmp_vertices_idx == 0? inPolygonToClip : tmp_vertices[tmp_vertices_idx & 1];
181 tmp_vertices_idx++;
182 VERTEX_ARRAY &tgt_polygon = tmp_vertices_idx == 6? outClippedPolygon : tmp_vertices[tmp_vertices_idx & 1];
183 tgt_polygon.clear();
184
185 // Clip against the edge
186 ClipPolyVsPlane(src_polygon, origin, normal, tgt_polygon);
187
188 // Break out if no polygon left
189 if (tgt_polygon.size() < 3)
190 {
191 outClippedPolygon.clear();
192 return;
193 }
194
195 // Flip normal
196 normal = -normal;
197 }
198}
199
void ClipPolyVsPoly(const VERTEX_ARRAY &inPolygonToClip, const VERTEX_ARRAY &inClippingPolygon, Vec3Arg inClippingPolygonNormal, VERTEX_ARRAY &outClippedPolygon)
Definition: ClipPoly.h:62
JPH_NAMESPACE_BEGIN void ClipPolyVsPlane(const VERTEX_ARRAY &inPolygonToClip, Vec3Arg inPlaneOrigin, Vec3Arg inPlaneNormal, VERTEX_ARRAY &outClippedPolygon)
Definition: ClipPoly.h:14
void ClipPolyVsEdge(const VERTEX_ARRAY &inPolygonToClip, Vec3Arg inEdgeVertex1, Vec3Arg inEdgeVertex2, Vec3Arg inClippingEdgeNormal, VERTEX_ARRAY &outClippedPolygon)
Definition: ClipPoly.h:98
void ClipPolyVsAABox(const VERTEX_ARRAY &inPolygonToClip, const AABox &inAABox, VERTEX_ARRAY &outClippedPolygon)
Definition: ClipPoly.h:156
#define JPH_NAMESPACE_END
Definition: Core.h:367
#define JPH_NAMESPACE_BEGIN
Definition: Core.h:361
#define JPH_ASSERT(...)
Definition: IssueReporting.h:33
Axis aligned box.
Definition: AABox.h:16
Vec3 mMin
Bounding box min and max.
Definition: AABox.h:300
Vec3 mMax
Definition: AABox.h:301
Definition: Vec3.h:16
JPH_INLINE float Dot(Vec3Arg inV2) const
Dot product.
Definition: Vec3.inl:637
JPH_INLINE void SetComponent(uint inCoordinate, float inValue)
Set float component by index.
Definition: Vec3.h:140
JPH_INLINE Vec3 Cross(Vec3Arg inV2) const
Cross product.
Definition: Vec3.inl:582
JPH_INLINE float LengthSq() const
Squared length of vector.
Definition: Vec3.inl:653
static JPH_INLINE Vec3 sZero()
Vector with all zeros.
Definition: Vec3.inl:107