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 "Vulkan/VkDebug.hpp"
20 
21 namespace sw
22 {
computeClipFlags(const float4 & v)23 	unsigned int Clipper::computeClipFlags(const float4 &v)
24 	{
25 		return ((v.x > v.w)     ? CLIP_RIGHT  : 0) |
26 		       ((v.y > v.w)     ? CLIP_TOP    : 0) |
27 		       ((v.z > v.w)     ? CLIP_FAR    : 0) |
28 		       ((v.x < -v.w)    ? CLIP_LEFT   : 0) |
29 		       ((v.y < -v.w)    ? CLIP_BOTTOM : 0) |
30 		       ((v.z < 0)       ? CLIP_NEAR   : 0) |
31 		       Clipper::CLIP_FINITE;   // FIXME: xyz finite
32 	}
33 
clip(Polygon & polygon,int clipFlagsOr,const DrawCall & draw)34 	bool Clipper::clip(Polygon &polygon, int clipFlagsOr, const DrawCall &draw)
35 	{
36 		if(clipFlagsOr & CLIP_FRUSTUM)
37 		{
38 			if(clipFlagsOr & CLIP_NEAR)   clipNear(polygon);
39 			if(polygon.n >= 3) {
40 			if(clipFlagsOr & CLIP_FAR)    clipFar(polygon);
41 			if(polygon.n >= 3) {
42 			if(clipFlagsOr & CLIP_LEFT)   clipLeft(polygon);
43 			if(polygon.n >= 3) {
44 			if(clipFlagsOr & CLIP_RIGHT)  clipRight(polygon);
45 			if(polygon.n >= 3) {
46 			if(clipFlagsOr & CLIP_TOP)    clipTop(polygon);
47 			if(polygon.n >= 3) {
48 			if(clipFlagsOr & CLIP_BOTTOM) clipBottom(polygon);
49 			}}}}}
50 		}
51 
52 		if(clipFlagsOr & CLIP_USER)
53 		{
54 			int clipFlags = draw.clipFlags;
55 			DrawData &data = *draw.data;
56 
57 			if(polygon.n >= 3) {
58 			if(clipFlags & CLIP_PLANE0) clipPlane(polygon, data.clipPlane[0]);
59 			if(polygon.n >= 3) {
60 			if(clipFlags & CLIP_PLANE1) clipPlane(polygon, data.clipPlane[1]);
61 			if(polygon.n >= 3) {
62 			if(clipFlags & CLIP_PLANE2) clipPlane(polygon, data.clipPlane[2]);
63 			if(polygon.n >= 3) {
64 			if(clipFlags & CLIP_PLANE3) clipPlane(polygon, data.clipPlane[3]);
65 			if(polygon.n >= 3) {
66 			if(clipFlags & CLIP_PLANE4) clipPlane(polygon, data.clipPlane[4]);
67 			if(polygon.n >= 3) {
68 			if(clipFlags & CLIP_PLANE5) clipPlane(polygon, data.clipPlane[5]);
69 			}}}}}}
70 		}
71 
72 		return polygon.n >= 3;
73 	}
74 
clipNear(Polygon & polygon)75 	void Clipper::clipNear(Polygon &polygon)
76 	{
77 		const float4 **V = polygon.P[polygon.i];
78 		const float4 **T = polygon.P[polygon.i + 1];
79 
80 		int t = 0;
81 
82 		for(int i = 0; i < polygon.n; i++)
83 		{
84 			int j = i == polygon.n - 1 ? 0 : i + 1;
85 
86 			float di = V[i]->z;
87 			float dj = V[j]->z;
88 
89 			if(di >= 0)
90 			{
91 				T[t++] = V[i];
92 
93 				if(dj < 0)
94 				{
95 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
96 					T[t++] = &polygon.B[polygon.b++];
97 				}
98 			}
99 			else
100 			{
101 				if(dj > 0)
102 				{
103 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
104 					T[t++] = &polygon.B[polygon.b++];
105 				}
106 			}
107 		}
108 
109 		polygon.n = t;
110 		polygon.i += 1;
111 	}
112 
clipFar(Polygon & polygon)113 	void Clipper::clipFar(Polygon &polygon)
114 	{
115 		const float4 **V = polygon.P[polygon.i];
116 		const float4 **T = polygon.P[polygon.i + 1];
117 
118 		int t = 0;
119 
120 		for(int i = 0; i < polygon.n; i++)
121 		{
122 			int j = i == polygon.n - 1 ? 0 : i + 1;
123 
124 			float di = V[i]->w - V[i]->z;
125 			float dj = V[j]->w - V[j]->z;
126 
127 			if(di >= 0)
128 			{
129 				T[t++] = V[i];
130 
131 				if(dj < 0)
132 				{
133 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
134 					T[t++] = &polygon.B[polygon.b++];
135 				}
136 			}
137 			else
138 			{
139 				if(dj > 0)
140 				{
141 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
142 					T[t++] = &polygon.B[polygon.b++];
143 				}
144 			}
145 		}
146 
147 		polygon.n = t;
148 		polygon.i += 1;
149 	}
150 
clipLeft(Polygon & polygon)151 	void Clipper::clipLeft(Polygon &polygon)
152 	{
153 		const float4 **V = polygon.P[polygon.i];
154 		const float4 **T = polygon.P[polygon.i + 1];
155 
156 		int t = 0;
157 
158 		for(int i = 0; i < polygon.n; i++)
159 		{
160 			int j = i == polygon.n - 1 ? 0 : i + 1;
161 
162 			float di = V[i]->w + V[i]->x;
163 			float dj = V[j]->w + V[j]->x;
164 
165 			if(di >= 0)
166 			{
167 				T[t++] = V[i];
168 
169 				if(dj < 0)
170 				{
171 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
172 					T[t++] = &polygon.B[polygon.b++];
173 				}
174 			}
175 			else
176 			{
177 				if(dj > 0)
178 				{
179 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
180 					T[t++] = &polygon.B[polygon.b++];
181 				}
182 			}
183 		}
184 
185 		polygon.n = t;
186 		polygon.i += 1;
187 	}
188 
clipRight(Polygon & polygon)189 	void Clipper::clipRight(Polygon &polygon)
190 	{
191 		const float4 **V = polygon.P[polygon.i];
192 		const float4 **T = polygon.P[polygon.i + 1];
193 
194 		int t = 0;
195 
196 		for(int i = 0; i < polygon.n; i++)
197 		{
198 			int j = i == polygon.n - 1 ? 0 : i + 1;
199 
200 			float di = V[i]->w - V[i]->x;
201 			float dj = V[j]->w - V[j]->x;
202 
203 			if(di >= 0)
204 			{
205 				T[t++] = V[i];
206 
207 				if(dj < 0)
208 				{
209 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
210 					T[t++] = &polygon.B[polygon.b++];
211 				}
212 			}
213 			else
214 			{
215 				if(dj > 0)
216 				{
217 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
218 					T[t++] = &polygon.B[polygon.b++];
219 				}
220 			}
221 		}
222 
223 		polygon.n = t;
224 		polygon.i += 1;
225 	}
226 
clipTop(Polygon & polygon)227 	void Clipper::clipTop(Polygon &polygon)
228 	{
229 		const float4 **V = polygon.P[polygon.i];
230 		const float4 **T = polygon.P[polygon.i + 1];
231 
232 		int t = 0;
233 
234 		for(int i = 0; i < polygon.n; i++)
235 		{
236 			int j = i == polygon.n - 1 ? 0 : i + 1;
237 
238 			float di = V[i]->w - V[i]->y;
239 			float dj = V[j]->w - V[j]->y;
240 
241 			if(di >= 0)
242 			{
243 				T[t++] = V[i];
244 
245 				if(dj < 0)
246 				{
247 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
248 					T[t++] = &polygon.B[polygon.b++];
249 				}
250 			}
251 			else
252 			{
253 				if(dj > 0)
254 				{
255 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
256 					T[t++] = &polygon.B[polygon.b++];
257 				}
258 			}
259 		}
260 
261 		polygon.n = t;
262 		polygon.i += 1;
263 	}
264 
clipBottom(Polygon & polygon)265 	void Clipper::clipBottom(Polygon &polygon)
266 	{
267 		const float4 **V = polygon.P[polygon.i];
268 		const float4 **T = polygon.P[polygon.i + 1];
269 
270 		int t = 0;
271 
272 		for(int i = 0; i < polygon.n; i++)
273 		{
274 			int j = i == polygon.n - 1 ? 0 : i + 1;
275 
276 			float di = V[i]->w + V[i]->y;
277 			float dj = V[j]->w + V[j]->y;
278 
279 			if(di >= 0)
280 			{
281 				T[t++] = V[i];
282 
283 				if(dj < 0)
284 				{
285 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
286 					T[t++] = &polygon.B[polygon.b++];
287 				}
288 			}
289 			else
290 			{
291 				if(dj > 0)
292 				{
293 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
294 					T[t++] = &polygon.B[polygon.b++];
295 				}
296 			}
297 		}
298 
299 		polygon.n = t;
300 		polygon.i += 1;
301 	}
302 
clipPlane(Polygon & polygon,const Plane & p)303 	void Clipper::clipPlane(Polygon &polygon, const Plane &p)
304 	{
305 		const float4 **V = polygon.P[polygon.i];
306 		const float4 **T = polygon.P[polygon.i + 1];
307 
308 		int t = 0;
309 
310 		for(int i = 0; i < polygon.n; i++)
311 		{
312 			int j = i == polygon.n - 1 ? 0 : i + 1;
313 
314 			float di = p.A * V[i]->x + p.B * V[i]->y + p.C * V[i]->z + p.D * V[i]->w;
315 			float dj = p.A * V[j]->x + p.B * V[j]->y + p.C * V[j]->z + p.D * V[j]->w;
316 
317 			if(di >= 0)
318 			{
319 				T[t++] = V[i];
320 
321 				if(dj < 0)
322 				{
323 					clipEdge(polygon.B[polygon.b], *V[i], *V[j], di, dj);
324 					T[t++] = &polygon.B[polygon.b++];
325 				}
326 			}
327 			else
328 			{
329 				if(dj > 0)
330 				{
331 					clipEdge(polygon.B[polygon.b], *V[j], *V[i], dj, di);
332 					T[t++] = &polygon.B[polygon.b++];
333 				}
334 			}
335 		}
336 
337 		polygon.n = t;
338 		polygon.i += 1;
339 	}
340 
clipEdge(float4 & Vo,const float4 & Vi,const float4 & Vj,float di,float dj) const341 	inline void Clipper::clipEdge(float4 &Vo, const float4 &Vi, const float4 &Vj, float di, float dj) const
342 	{
343 		float D = 1.0f / (dj - di);
344 
345 		Vo.x = (dj * Vi.x - di * Vj.x) * D;
346 		Vo.y = (dj * Vi.y - di * Vj.y) * D;
347 		Vo.z = (dj * Vi.z - di * Vj.z) * D;
348 		Vo.w = (dj * Vi.w - di * Vj.w) * D;
349 	}
350 }
351