1 // Copyright (c) 2013- PPSSPP Project.
2
3 // This program is free software: you can redistribute it and/or modify
4 // it under the terms of the GNU General Public License as published by
5 // the Free Software Foundation, version 2.0 or later versions.
6
7 // This program is distributed in the hope that it will be useful,
8 // but WITHOUT ANY WARRANTY; without even the implied warranty of
9 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 // GNU General Public License 2.0 for more details.
11
12 // A copy of the GPL 2.0 should have been included with the program.
13 // If not, see http://www.gnu.org/licenses/
14
15 // Official git repository and contact information can be found at
16 // https://github.com/hrydgard/ppsspp and http://www.ppsspp.org/.
17
18 #include <algorithm>
19
20 #include "GPU/GPUState.h"
21
22 #include "GPU/Software/Clipper.h"
23 #include "GPU/Software/Rasterizer.h"
24 #include "GPU/Software/RasterizerRectangle.h"
25 #include "GPU/Software/TransformUnit.h"
26
27 #include "Common/Profiler/Profiler.h"
28
29 namespace Clipper {
30
31 enum {
32 SKIP_FLAG = -1,
33 CLIP_NEG_Z_BIT = 0x20,
34 };
35
CalcClipMask(const ClipCoords & v)36 static inline int CalcClipMask(const ClipCoords& v)
37 {
38 int mask = 0;
39 // This checks `x / w` compared to 1 or -1, skipping the division.
40 if (v.z < -v.w) mask |= CLIP_NEG_Z_BIT;
41 return mask;
42 }
43
different_signs(float x,float y)44 inline bool different_signs(float x, float y) {
45 return ((x <= 0 && y > 0) || (x > 0 && y <= 0));
46 }
47
clip_dotprod(const VertexData & vert,float A,float B,float C,float D)48 inline float clip_dotprod(const VertexData &vert, float A, float B, float C, float D) {
49 return (vert.clippos.x * A + vert.clippos.y * B + vert.clippos.z * C + vert.clippos.w * D);
50 }
51
52 #define POLY_CLIP( PLANE_BIT, A, B, C, D ) \
53 { \
54 if (mask & PLANE_BIT) { \
55 int idxPrev = inlist[0]; \
56 float dpPrev = clip_dotprod(*Vertices[idxPrev], A, B, C, D );\
57 int outcount = 0; \
58 \
59 inlist[n] = inlist[0]; \
60 for (int j = 1; j <= n; j++) { \
61 int idx = inlist[j]; \
62 float dp = clip_dotprod(*Vertices[idx], A, B, C, D ); \
63 if (dpPrev >= 0) { \
64 outlist[outcount++] = idxPrev; \
65 } \
66 \
67 if (different_signs(dp, dpPrev)) { \
68 if (dp < 0) { \
69 float t = dp / (dp - dpPrev); \
70 Vertices[numVertices++]->Lerp(t, *Vertices[idx], *Vertices[idxPrev]); \
71 } else { \
72 float t = dpPrev / (dpPrev - dp); \
73 Vertices[numVertices++]->Lerp(t, *Vertices[idxPrev], *Vertices[idx]); \
74 } \
75 outlist[outcount++] = numVertices - 1; \
76 } \
77 \
78 idxPrev = idx; \
79 dpPrev = dp; \
80 } \
81 \
82 if (outcount < 3) \
83 continue; \
84 \
85 { \
86 int *tmp = inlist; \
87 inlist = outlist; \
88 outlist = tmp; \
89 n = outcount; \
90 } \
91 } \
92 }
93
94 #define CLIP_LINE(PLANE_BIT, A, B, C, D) \
95 { \
96 if (mask & PLANE_BIT) { \
97 float dp0 = clip_dotprod(*Vertices[0], A, B, C, D ); \
98 float dp1 = clip_dotprod(*Vertices[1], A, B, C, D ); \
99 \
100 if (mask0 & PLANE_BIT) { \
101 if (dp0 < 0) { \
102 float t = dp1 / (dp1 - dp0); \
103 Vertices[0]->Lerp(t, *Vertices[1], *Vertices[0]); \
104 } \
105 } \
106 dp0 = clip_dotprod(*Vertices[0], A, B, C, D ); \
107 \
108 if (mask1 & PLANE_BIT) { \
109 if (dp1 < 0) { \
110 float t = dp1 / (dp1- dp0); \
111 Vertices[1]->Lerp(t, *Vertices[1], *Vertices[0]); \
112 } \
113 } \
114 } \
115 }
116
RotateUVThrough(const VertexData & tl,const VertexData & br,VertexData & tr,VertexData & bl)117 static void RotateUVThrough(const VertexData &tl, const VertexData &br, VertexData &tr, VertexData &bl) {
118 const int x1 = tl.screenpos.x;
119 const int x2 = br.screenpos.x;
120 const int y1 = tl.screenpos.y;
121 const int y2 = br.screenpos.y;
122
123 if ((x1 < x2 && y1 > y2) || (x1 > x2 && y1 < y2)) {
124 std::swap(bl.texturecoords, tr.texturecoords);
125 }
126 }
127
128 void ProcessTriangleInternal(VertexData &v0, VertexData &v1, VertexData &v2, const VertexData &provoking, bool fromRectangle);
129
CheckOutsideZ(ClipCoords p,int & pos,int & neg)130 static inline bool CheckOutsideZ(ClipCoords p, int &pos, int &neg) {
131 constexpr float outsideValue = 1.000030517578125f;
132 float z = p.z / p.w;
133 if (z >= outsideValue) {
134 pos++;
135 return true;
136 }
137 if (-z >= outsideValue) {
138 neg++;
139 return true;
140 }
141 return false;
142 }
143
ProcessRect(const VertexData & v0,const VertexData & v1)144 void ProcessRect(const VertexData& v0, const VertexData& v1)
145 {
146 if (!gstate.isModeThrough()) {
147 // We may discard the entire rect based on depth values.
148 int outsidePos = 0, outsideNeg = 0;
149 CheckOutsideZ(v0.clippos, outsidePos, outsideNeg);
150 CheckOutsideZ(v1.clippos, outsidePos, outsideNeg);
151
152 // With depth clamp off, we discard the rectangle if even one vert is outside.
153 if (outsidePos + outsideNeg > 0 && !gstate.isDepthClampEnabled())
154 return;
155 // With it on, both must be outside in the same direction.
156 else if (outsidePos >= 2 || outsideNeg >= 2)
157 return;
158
159 VertexData buf[4];
160 buf[0].clippos = ClipCoords(v0.clippos.x, v0.clippos.y, v1.clippos.z, v1.clippos.w);
161 buf[0].texturecoords = v0.texturecoords;
162
163 buf[1].clippos = ClipCoords(v0.clippos.x, v1.clippos.y, v1.clippos.z, v1.clippos.w);
164 buf[1].texturecoords = Vec2<float>(v0.texturecoords.x, v1.texturecoords.y);
165
166 buf[2].clippos = ClipCoords(v1.clippos.x, v0.clippos.y, v1.clippos.z, v1.clippos.w);
167 buf[2].texturecoords = Vec2<float>(v1.texturecoords.x, v0.texturecoords.y);
168
169 buf[3] = v1;
170
171 // Color and depth values of second vertex are used for the whole rectangle
172 buf[0].color0 = buf[1].color0 = buf[2].color0 = buf[3].color0;
173 buf[0].color1 = buf[1].color1 = buf[2].color1 = buf[3].color1;
174 buf[0].fogdepth = buf[1].fogdepth = buf[2].fogdepth = buf[3].fogdepth;
175
176 VertexData* topleft = &buf[0];
177 VertexData* topright = &buf[1];
178 VertexData* bottomleft = &buf[2];
179 VertexData* bottomright = &buf[3];
180
181 for (int i = 0; i < 4; ++i) {
182 if (buf[i].clippos.x < topleft->clippos.x && buf[i].clippos.y < topleft->clippos.y)
183 topleft = &buf[i];
184 if (buf[i].clippos.x > topright->clippos.x && buf[i].clippos.y < topright->clippos.y)
185 topright = &buf[i];
186 if (buf[i].clippos.x < bottomleft->clippos.x && buf[i].clippos.y > bottomleft->clippos.y)
187 bottomleft = &buf[i];
188 if (buf[i].clippos.x > bottomright->clippos.x && buf[i].clippos.y > bottomright->clippos.y)
189 bottomright = &buf[i];
190 }
191
192 // Four triangles to do backfaces as well. Two of them will get backface culled.
193 ProcessTriangleInternal(*topleft, *topright, *bottomright, buf[3], true);
194 ProcessTriangleInternal(*bottomright, *topright, *topleft, buf[3], true);
195 ProcessTriangleInternal(*bottomright, *bottomleft, *topleft, buf[3], true);
196 ProcessTriangleInternal(*topleft, *bottomleft, *bottomright, buf[3], true);
197 } else {
198 // through mode handling
199
200 if (Rasterizer::RectangleFastPath(v0, v1)) {
201 return;
202 }
203
204 VertexData buf[4];
205 buf[0].screenpos = ScreenCoords(v0.screenpos.x, v0.screenpos.y, v1.screenpos.z);
206 buf[0].texturecoords = v0.texturecoords;
207
208 buf[1].screenpos = ScreenCoords(v0.screenpos.x, v1.screenpos.y, v1.screenpos.z);
209 buf[1].texturecoords = Vec2<float>(v0.texturecoords.x, v1.texturecoords.y);
210
211 buf[2].screenpos = ScreenCoords(v1.screenpos.x, v0.screenpos.y, v1.screenpos.z);
212 buf[2].texturecoords = Vec2<float>(v1.texturecoords.x, v0.texturecoords.y);
213
214 buf[3] = v1;
215
216 // Color and depth values of second vertex are used for the whole rectangle
217 buf[0].color0 = buf[1].color0 = buf[2].color0 = buf[3].color0;
218 buf[0].color1 = buf[1].color1 = buf[2].color1 = buf[3].color1; // is color1 ever used in through mode?
219 buf[0].clippos.w = buf[1].clippos.w = buf[2].clippos.w = buf[3].clippos.w = 1.0f;
220 buf[0].fogdepth = buf[1].fogdepth = buf[2].fogdepth = buf[3].fogdepth = 1.0f;
221
222 VertexData* topleft = &buf[0];
223 VertexData* topright = &buf[1];
224 VertexData* bottomleft = &buf[2];
225 VertexData* bottomright = &buf[3];
226
227 // DrawTriangle always culls, so sort out the drawing order.
228 for (int i = 0; i < 4; ++i) {
229 if (buf[i].screenpos.x < topleft->screenpos.x && buf[i].screenpos.y < topleft->screenpos.y)
230 topleft = &buf[i];
231 if (buf[i].screenpos.x > topright->screenpos.x && buf[i].screenpos.y < topright->screenpos.y)
232 topright = &buf[i];
233 if (buf[i].screenpos.x < bottomleft->screenpos.x && buf[i].screenpos.y > bottomleft->screenpos.y)
234 bottomleft = &buf[i];
235 if (buf[i].screenpos.x > bottomright->screenpos.x && buf[i].screenpos.y > bottomright->screenpos.y)
236 bottomright = &buf[i];
237 }
238
239 RotateUVThrough(v0, v1, *topright, *bottomleft);
240
241 if (gstate.isModeClear()) {
242 Rasterizer::ClearRectangle(v0, v1);
243 } else {
244 // Four triangles to do backfaces as well. Two of them will get backface culled.
245 Rasterizer::DrawTriangle(*topleft, *topright, *bottomright);
246 Rasterizer::DrawTriangle(*bottomright, *topright, *topleft);
247 Rasterizer::DrawTriangle(*bottomright, *bottomleft, *topleft);
248 Rasterizer::DrawTriangle(*topleft, *bottomleft, *bottomright);
249 }
250 }
251 }
252
ProcessPoint(VertexData & v0)253 void ProcessPoint(VertexData& v0)
254 {
255 // Points need no clipping. Will be bounds checked in the rasterizer (which seems backwards?)
256 Rasterizer::DrawPoint(v0);
257 }
258
ProcessLine(VertexData & v0,VertexData & v1)259 void ProcessLine(VertexData& v0, VertexData& v1)
260 {
261 if (gstate.isModeThrough()) {
262 // Actually, should clip this one too so we don't need to do bounds checks in the rasterizer.
263 Rasterizer::DrawLine(v0, v1);
264 return;
265 }
266
267 int outsidePos = 0, outsideNeg = 0;
268 CheckOutsideZ(v0.clippos, outsidePos, outsideNeg);
269 CheckOutsideZ(v1.clippos, outsidePos, outsideNeg);
270
271 // With depth clamp off, we discard the line if even one vert is outside.
272 if (outsidePos + outsideNeg > 0 && !gstate.isDepthClampEnabled())
273 return;
274 // With it on, both must be outside in the same direction.
275 else if (outsidePos >= 2 || outsideNeg >= 2)
276 return;
277
278 VertexData *Vertices[2] = {&v0, &v1};
279
280 int mask0 = CalcClipMask(v0.clippos);
281 int mask1 = CalcClipMask(v1.clippos);
282 int mask = mask0 | mask1;
283 if (mask) {
284 CLIP_LINE(CLIP_NEG_Z_BIT, 0, 0, 1, 1);
285 }
286
287 VertexData data[2] = { *Vertices[0], *Vertices[1] };
288 data[0].screenpos = TransformUnit::ClipToScreen(data[0].clippos);
289 data[1].screenpos = TransformUnit::ClipToScreen(data[1].clippos);
290 Rasterizer::DrawLine(data[0], data[1]);
291 }
292
ProcessTriangleInternal(VertexData & v0,VertexData & v1,VertexData & v2,const VertexData & provoking,bool fromRectangle)293 void ProcessTriangleInternal(VertexData &v0, VertexData &v1, VertexData &v2, const VertexData &provoking, bool fromRectangle) {
294 if (gstate.isModeThrough()) {
295 // In case of cull reordering, make sure the right color is on the final vertex.
296 if (gstate.getShadeMode() == GE_SHADE_FLAT) {
297 VertexData corrected2 = v2;
298 corrected2.color0 = provoking.color0;
299 corrected2.color1 = provoking.color1;
300 Rasterizer::DrawTriangle(v0, v1, corrected2);
301 } else {
302 Rasterizer::DrawTriangle(v0, v1, v2);
303 }
304 return;
305 }
306
307 enum { NUM_CLIPPED_VERTICES = 33, NUM_INDICES = NUM_CLIPPED_VERTICES + 3 };
308
309 VertexData* Vertices[NUM_INDICES];
310 VertexData ClippedVertices[NUM_CLIPPED_VERTICES];
311 for (int i = 0; i < NUM_CLIPPED_VERTICES; ++i)
312 Vertices[i+3] = &ClippedVertices[i];
313
314 // TODO: Change logic when it's a backface (why? In what way?)
315 Vertices[0] = &v0;
316 Vertices[1] = &v1;
317 Vertices[2] = &v2;
318
319 int indices[NUM_INDICES] = { 0, 1, 2, SKIP_FLAG, SKIP_FLAG, SKIP_FLAG, SKIP_FLAG, SKIP_FLAG, SKIP_FLAG,
320 SKIP_FLAG, SKIP_FLAG, SKIP_FLAG, SKIP_FLAG, SKIP_FLAG, SKIP_FLAG,
321 SKIP_FLAG, SKIP_FLAG, SKIP_FLAG, SKIP_FLAG, SKIP_FLAG, SKIP_FLAG };
322 int numIndices = 3;
323
324 int mask = 0;
325 mask |= CalcClipMask(v0.clippos);
326 mask |= CalcClipMask(v1.clippos);
327 mask |= CalcClipMask(v2.clippos);
328
329 if (mask && !fromRectangle) {
330 // We may discard the entire triangle based on depth values. First check what's outside.
331 int outsidePos = 0, outsideNeg = 0;
332 for (int i = 0; i < 3; ++i) {
333 CheckOutsideZ(Vertices[i]->clippos, outsidePos, outsideNeg);
334 }
335
336 // With depth clamp off, we discard the triangle if even one vert is outside.
337 if (outsidePos + outsideNeg > 0 && !gstate.isDepthClampEnabled())
338 return;
339 // With it on, all three must be outside in the same direction.
340 else if (outsidePos >= 3 || outsideNeg >= 3)
341 return;
342
343 for (int i = 0; i < 3; i += 3) {
344 int vlist[2][2*6+1];
345 int *inlist = vlist[0], *outlist = vlist[1];
346 int n = 3;
347 int numVertices = 3;
348
349 inlist[0] = 0;
350 inlist[1] = 1;
351 inlist[2] = 2;
352
353 // mark this triangle as unused in case it should be completely clipped
354 indices[0] = SKIP_FLAG;
355 indices[1] = SKIP_FLAG;
356 indices[2] = SKIP_FLAG;
357
358 // The PSP only clips on negative Z (importantly, regardless of viewport.)
359 POLY_CLIP(CLIP_NEG_Z_BIT, 0, 0, 1, 1);
360
361 // transform the poly in inlist into triangles
362 indices[0] = inlist[0];
363 indices[1] = inlist[1];
364 indices[2] = inlist[2];
365 for (int j = 3; j < n; ++j) {
366 indices[numIndices++] = inlist[0];
367 indices[numIndices++] = inlist[j - 1];
368 indices[numIndices++] = inlist[j];
369 }
370 }
371 }
372
373 for (int i = 0; i + 3 <= numIndices; i += 3) {
374 if (indices[i] != SKIP_FLAG) {
375 VertexData data[3] = { *Vertices[indices[i]], *Vertices[indices[i+1]], *Vertices[indices[i+2]] };
376 data[0].screenpos = TransformUnit::ClipToScreen(data[0].clippos);
377 data[1].screenpos = TransformUnit::ClipToScreen(data[1].clippos);
378 data[2].screenpos = TransformUnit::ClipToScreen(data[2].clippos);
379
380 if (gstate.getShadeMode() == GE_SHADE_FLAT) {
381 // So that the order of clipping doesn't matter...
382 data[2].color0 = provoking.color0;
383 data[2].color1 = provoking.color1;
384 }
385
386 Rasterizer::DrawTriangle(data[0], data[1], data[2]);
387 }
388 }
389 }
390
ProcessTriangle(VertexData & v0,VertexData & v1,VertexData & v2,const VertexData & provoking)391 void ProcessTriangle(VertexData &v0, VertexData &v1, VertexData &v2, const VertexData &provoking) {
392 ProcessTriangleInternal(v0, v1, v2, provoking, false);
393 }
394
395 } // namespace
396