1 // Copyright 2016 The SwiftShader Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //    http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #include "Clipper.hpp"
16 
17 #include "Polygon.hpp"
18 #include "Renderer.hpp"
19 #include "Common/Debug.hpp"
20 
21 namespace sw
22 {
Clipper(bool symmetricNormalizedDepth)23 	Clipper::Clipper(bool symmetricNormalizedDepth)
24 	{
25 		n = symmetricNormalizedDepth ? -1.0f : 0.0f;
26 	}
27 
~Clipper()28 	Clipper::~Clipper()
29 	{
30 	}
31 
computeClipFlags(const float4 & v)32 	unsigned int Clipper::computeClipFlags(const float4 &v)
33 	{
34 		return ((v.x > v.w)     ? CLIP_RIGHT  : 0) |
35 		       ((v.y > v.w)     ? CLIP_TOP    : 0) |
36 		       ((v.z > v.w)     ? CLIP_FAR    : 0) |
37 		       ((v.x < -v.w)    ? CLIP_LEFT   : 0) |
38 		       ((v.y < -v.w)    ? CLIP_BOTTOM : 0) |
39 		       ((v.z < n * v.w) ? CLIP_NEAR   : 0) |
40 		       Clipper::CLIP_FINITE;   // FIXME: xyz finite
41 	}
42 
clip(Polygon & polygon,int clipFlagsOr,const DrawCall & draw)43 	bool Clipper::clip(Polygon &polygon, int clipFlagsOr, const DrawCall &draw)
44 	{
45 		if(clipFlagsOr & CLIP_FRUSTUM)
46 		{
47 			if(clipFlagsOr & CLIP_NEAR)   clipNear(polygon);
48 			if(polygon.n >= 3) {
49 			if(clipFlagsOr & CLIP_FAR)    clipFar(polygon);
50 			if(polygon.n >= 3) {
51 			if(clipFlagsOr & CLIP_LEFT)   clipLeft(polygon);
52 			if(polygon.n >= 3) {
53 			if(clipFlagsOr & CLIP_RIGHT)  clipRight(polygon);
54 			if(polygon.n >= 3) {
55 			if(clipFlagsOr & CLIP_TOP)    clipTop(polygon);
56 			if(polygon.n >= 3) {
57 			if(clipFlagsOr & CLIP_BOTTOM) clipBottom(polygon);
58 			}}}}}
59 		}
60 
61 		if(clipFlagsOr & CLIP_USER)
62 		{
63 			int clipFlags = draw.clipFlags;
64 			DrawData &data = *draw.data;
65 
66 			if(polygon.n >= 3) {
67 			if(clipFlags & CLIP_PLANE0) clipPlane(polygon, data.clipPlane[0]);
68 			if(polygon.n >= 3) {
69 			if(clipFlags & CLIP_PLANE1) clipPlane(polygon, data.clipPlane[1]);
70 			if(polygon.n >= 3) {
71 			if(clipFlags & CLIP_PLANE2) clipPlane(polygon, data.clipPlane[2]);
72 			if(polygon.n >= 3) {
73 			if(clipFlags & CLIP_PLANE3) clipPlane(polygon, data.clipPlane[3]);
74 			if(polygon.n >= 3) {
75 			if(clipFlags & CLIP_PLANE4) clipPlane(polygon, data.clipPlane[4]);
76 			if(polygon.n >= 3) {
77 			if(clipFlags & CLIP_PLANE5) clipPlane(polygon, data.clipPlane[5]);
78 			}}}}}}
79 		}
80 
81 		return polygon.n >= 3;
82 	}
83 
clipNear(Polygon & polygon)84 	void Clipper::clipNear(Polygon &polygon)
85 	{
86 		const float4 **V = polygon.P[polygon.i];
87 		const float4 **T = polygon.P[polygon.i + 1];
88 
89 		int t = 0;
90 
91 		for(int i = 0; i < polygon.n; i++)
92 		{
93 			int j = i == polygon.n - 1 ? 0 : i + 1;
94 
95 			float di = V[i]->z - n * V[i]->w;
96 			float dj = V[j]->z - n * V[j]->w;
97 
98 			if(di >= 0)
99 			{
100 				T[t++] = V[i];
101 
102 				if(dj < 0)
103 				{
104 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
105 					T[t++] = &polygon.B[polygon.b++];
106 				}
107 			}
108 			else
109 			{
110 				if(dj > 0)
111 				{
112 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
113 					T[t++] = &polygon.B[polygon.b++];
114 				}
115 			}
116 		}
117 
118 		polygon.n = t;
119 		polygon.i += 1;
120 	}
121 
clipFar(Polygon & polygon)122 	void Clipper::clipFar(Polygon &polygon)
123 	{
124 		const float4 **V = polygon.P[polygon.i];
125 		const float4 **T = polygon.P[polygon.i + 1];
126 
127 		int t = 0;
128 
129 		for(int i = 0; i < polygon.n; i++)
130 		{
131 			int j = i == polygon.n - 1 ? 0 : i + 1;
132 
133 			float di = V[i]->w - V[i]->z;
134 			float dj = V[j]->w - V[j]->z;
135 
136 			if(di >= 0)
137 			{
138 				T[t++] = V[i];
139 
140 				if(dj < 0)
141 				{
142 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
143 					T[t++] = &polygon.B[polygon.b++];
144 				}
145 			}
146 			else
147 			{
148 				if(dj > 0)
149 				{
150 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
151 					T[t++] = &polygon.B[polygon.b++];
152 				}
153 			}
154 		}
155 
156 		polygon.n = t;
157 		polygon.i += 1;
158 	}
159 
clipLeft(Polygon & polygon)160 	void Clipper::clipLeft(Polygon &polygon)
161 	{
162 		const float4 **V = polygon.P[polygon.i];
163 		const float4 **T = polygon.P[polygon.i + 1];
164 
165 		int t = 0;
166 
167 		for(int i = 0; i < polygon.n; i++)
168 		{
169 			int j = i == polygon.n - 1 ? 0 : i + 1;
170 
171 			float di = V[i]->w + V[i]->x;
172 			float dj = V[j]->w + V[j]->x;
173 
174 			if(di >= 0)
175 			{
176 				T[t++] = V[i];
177 
178 				if(dj < 0)
179 				{
180 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
181 					T[t++] = &polygon.B[polygon.b++];
182 				}
183 			}
184 			else
185 			{
186 				if(dj > 0)
187 				{
188 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
189 					T[t++] = &polygon.B[polygon.b++];
190 				}
191 			}
192 		}
193 
194 		polygon.n = t;
195 		polygon.i += 1;
196 	}
197 
clipRight(Polygon & polygon)198 	void Clipper::clipRight(Polygon &polygon)
199 	{
200 		const float4 **V = polygon.P[polygon.i];
201 		const float4 **T = polygon.P[polygon.i + 1];
202 
203 		int t = 0;
204 
205 		for(int i = 0; i < polygon.n; i++)
206 		{
207 			int j = i == polygon.n - 1 ? 0 : i + 1;
208 
209 			float di = V[i]->w - V[i]->x;
210 			float dj = V[j]->w - V[j]->x;
211 
212 			if(di >= 0)
213 			{
214 				T[t++] = V[i];
215 
216 				if(dj < 0)
217 				{
218 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
219 					T[t++] = &polygon.B[polygon.b++];
220 				}
221 			}
222 			else
223 			{
224 				if(dj > 0)
225 				{
226 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
227 					T[t++] = &polygon.B[polygon.b++];
228 				}
229 			}
230 		}
231 
232 		polygon.n = t;
233 		polygon.i += 1;
234 	}
235 
clipTop(Polygon & polygon)236 	void Clipper::clipTop(Polygon &polygon)
237 	{
238 		const float4 **V = polygon.P[polygon.i];
239 		const float4 **T = polygon.P[polygon.i + 1];
240 
241 		int t = 0;
242 
243 		for(int i = 0; i < polygon.n; i++)
244 		{
245 			int j = i == polygon.n - 1 ? 0 : i + 1;
246 
247 			float di = V[i]->w - V[i]->y;
248 			float dj = V[j]->w - V[j]->y;
249 
250 			if(di >= 0)
251 			{
252 				T[t++] = V[i];
253 
254 				if(dj < 0)
255 				{
256 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
257 					T[t++] = &polygon.B[polygon.b++];
258 				}
259 			}
260 			else
261 			{
262 				if(dj > 0)
263 				{
264 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
265 					T[t++] = &polygon.B[polygon.b++];
266 				}
267 			}
268 		}
269 
270 		polygon.n = t;
271 		polygon.i += 1;
272 	}
273 
clipBottom(Polygon & polygon)274 	void Clipper::clipBottom(Polygon &polygon)
275 	{
276 		const float4 **V = polygon.P[polygon.i];
277 		const float4 **T = polygon.P[polygon.i + 1];
278 
279 		int t = 0;
280 
281 		for(int i = 0; i < polygon.n; i++)
282 		{
283 			int j = i == polygon.n - 1 ? 0 : i + 1;
284 
285 			float di = V[i]->w + V[i]->y;
286 			float dj = V[j]->w + V[j]->y;
287 
288 			if(di >= 0)
289 			{
290 				T[t++] = V[i];
291 
292 				if(dj < 0)
293 				{
294 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
295 					T[t++] = &polygon.B[polygon.b++];
296 				}
297 			}
298 			else
299 			{
300 				if(dj > 0)
301 				{
302 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
303 					T[t++] = &polygon.B[polygon.b++];
304 				}
305 			}
306 		}
307 
308 		polygon.n = t;
309 		polygon.i += 1;
310 	}
311 
clipPlane(Polygon & polygon,const Plane & p)312 	void Clipper::clipPlane(Polygon &polygon, const Plane &p)
313 	{
314 		const float4 **V = polygon.P[polygon.i];
315 		const float4 **T = polygon.P[polygon.i + 1];
316 
317 		int t = 0;
318 
319 		for(int i = 0; i < polygon.n; i++)
320 		{
321 			int j = i == polygon.n - 1 ? 0 : i + 1;
322 
323 			float di = p.A * V[i]->x + p.B * V[i]->y + p.C * V[i]->z + p.D * V[i]->w;
324 			float dj = p.A * V[j]->x + p.B * V[j]->y + p.C * V[j]->z + p.D * V[j]->w;
325 
326 			if(di >= 0)
327 			{
328 				T[t++] = V[i];
329 
330 				if(dj < 0)
331 				{
332 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
333 					T[t++] = &polygon.B[polygon.b++];
334 				}
335 			}
336 			else
337 			{
338 				if(dj > 0)
339 				{
340 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
341 					T[t++] = &polygon.B[polygon.b++];
342 				}
343 			}
344 		}
345 
346 		polygon.n = t;
347 		polygon.i += 1;
348 	}
349 
clipEdge(float4 & Vo,const float4 & Vi,const float4 & Vj,float di,float dj) const350 	inline void Clipper::clipEdge(float4 &Vo, const float4 &Vi, const float4 &Vj, float di, float dj) const
351 	{
352 		float D = 1.0f / (dj - di);
353 
354 		Vo.x = (dj * Vi.x - di * Vj.x) * D;
355 		Vo.y = (dj * Vi.y - di * Vj.y) * D;
356 		Vo.z = (dj * Vi.z - di * Vj.z) * D;
357 		Vo.w = (dj * Vi.w - di * Vj.w) * D;
358 	}
359 }
360