CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
Path: blob/master/GPU/Software/Clipper.cpp
Views: 1401
// Copyright (c) 2013- PPSSPP Project.12// This program is free software: you can redistribute it and/or modify3// it under the terms of the GNU General Public License as published by4// the Free Software Foundation, version 2.0 or later versions.56// This program is distributed in the hope that it will be useful,7// but WITHOUT ANY WARRANTY; without even the implied warranty of8// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the9// GNU General Public License 2.0 for more details.1011// A copy of the GPL 2.0 should have been included with the program.12// If not, see http://www.gnu.org/licenses/1314// Official git repository and contact information can be found at15// https://github.com/hrydgard/ppsspp and http://www.ppsspp.org/.1617#include <algorithm>1819#include "GPU/GPUState.h"2021#include "GPU/Software/BinManager.h"22#include "GPU/Software/Clipper.h"23#include "GPU/Software/Rasterizer.h"24#include "GPU/Software/RasterizerRectangle.h"25#include "GPU/Software/TransformUnit.h"2627#include "Common/Profiler/Profiler.h"2829namespace Clipper {3031enum {32SKIP_FLAG = -1,33CLIP_NEG_Z_BIT = 0x20,34};3536static inline int CalcClipMask(const ClipCoords &v) {37// This checks `x / w` compared to 1 or -1, skipping the division.38if (v.z < -v.w)39return -1;40return 0;41}4243inline bool different_signs(float x, float y) {44return ((x <= 0 && y > 0) || (x > 0 && y <= 0));45}4647inline float clip_dotprod(const ClipVertexData &vert, float A, float B, float C, float D) {48return (vert.clippos.x * A + vert.clippos.y * B + vert.clippos.z * C + vert.clippos.w * D);49}5051inline void clip_interpolate(ClipVertexData &dest, float t, const ClipVertexData &a, const ClipVertexData &b) {52bool outsideRange = false;53dest.Lerp(t, a, b);54dest.v.screenpos = TransformUnit::ClipToScreen(dest.clippos, &outsideRange);55dest.v.clipw = dest.clippos.w;5657// If the clipped coordinate is outside range, then we throw it away.58// This prevents a lot of inversions that shouldn't be drawn.59if (outsideRange)60dest.v.screenpos.x = 0x7FFFFFFF;61}6263#define CLIP_POLY( PLANE_BIT, A, B, C, D ) \64{ \65if (mask & PLANE_BIT) { \66int idxPrev = inlist[0]; \67float dpPrev = clip_dotprod(*Vertices[idxPrev], A, B, C, D );\68int outcount = 0; \69\70inlist[n] = inlist[0]; \71for (int j = 1; j <= n; j++) { \72int idx = inlist[j]; \73float dp = clip_dotprod(*Vertices[idx], A, B, C, D ); \74if (dpPrev >= 0) { \75outlist[outcount++] = idxPrev; \76} \77\78/* Skipping w sign mismatches avoids inversions, but is incorrect. See #16131. */ \79/* For now, it's better to avoid inversions as they usually are undesired. */ \80if (different_signs(dp, dpPrev)) { \81auto &vert = Vertices[numVertices++]; \82if (dp < 0) { \83float t = dp / (dp - dpPrev); \84clip_interpolate(*vert, t, *Vertices[idx], *Vertices[idxPrev]); \85} else { \86float t = dpPrev / (dpPrev - dp); \87clip_interpolate(*vert, t, *Vertices[idxPrev], *Vertices[idx]); \88} \89outlist[outcount++] = numVertices - 1; \90} \91\92idxPrev = idx; \93dpPrev = dp; \94} \95\96if (outcount < 3) \97continue; \98\99{ \100int *tmp = inlist; \101inlist = outlist; \102outlist = tmp; \103n = outcount; \104} \105} \106}107108#define CLIP_LINE(PLANE_BIT, A, B, C, D) \109{ \110if (mask & PLANE_BIT) { \111float dp0 = clip_dotprod(*Vertices[0], A, B, C, D ); \112float dp1 = clip_dotprod(*Vertices[1], A, B, C, D ); \113\114if (mask0 & PLANE_BIT) { \115if (dp0 < 0) { \116float t = dp1 / (dp1 - dp0); \117clip_interpolate(*Vertices[0], t, *Vertices[1], *Vertices[0]); \118} \119} \120dp0 = clip_dotprod(*Vertices[0], A, B, C, D ); \121\122if (mask1 & PLANE_BIT) { \123if (dp1 < 0) { \124float t = dp1 / (dp1- dp0); \125clip_interpolate(*Vertices[1], t, *Vertices[1], *Vertices[0]); \126} \127} \128} \129}130131static inline bool CheckOutsideZ(ClipCoords p, int &pos, int &neg) {132constexpr float outsideValue = 1.000030517578125f;133float z = p.z / p.w;134if (z >= outsideValue) {135pos++;136return true;137}138if (-z >= outsideValue) {139neg++;140return true;141}142return false;143}144145static void RotateUV(const VertexData &tl, const VertexData &br, VertexData &tr, VertexData &bl) {146const int x1 = tl.screenpos.x;147const int x2 = br.screenpos.x;148const int y1 = tl.screenpos.y;149const int y2 = br.screenpos.y;150151if ((x1 < x2 && y1 > y2) || (x1 > x2 && y1 < y2)) {152std::swap(bl.texturecoords, tr.texturecoords);153}154}155156// This is used for rectangle texture projection, which is very uncommon.157// To avoid complicating the common rectangle path, this just uses triangles.158static void AddTriangleRect(const VertexData &v0, const VertexData &v1, BinManager &binner) {159VertexData buf[4];160buf[0] = v1;161buf[0].screenpos = ScreenCoords(v0.screenpos.x, v0.screenpos.y, v1.screenpos.z);162buf[0].texturecoords = v0.texturecoords;163164buf[1] = v1;165buf[1].screenpos = ScreenCoords(v0.screenpos.x, v1.screenpos.y, v1.screenpos.z);166buf[1].texturecoords = Vec3Packed<float>(v0.texturecoords.x, v1.texturecoords.y, v0.texturecoords.z);167168buf[2] = v1;169buf[2].screenpos = ScreenCoords(v1.screenpos.x, v0.screenpos.y, v1.screenpos.z);170buf[2].texturecoords = Vec3Packed<float>(v1.texturecoords.x, v0.texturecoords.y, v1.texturecoords.z);171172buf[3] = v1;173174VertexData *topleft = &buf[0];175VertexData *topright = &buf[1];176VertexData *bottomleft = &buf[2];177VertexData *bottomright = &buf[3];178179// DrawTriangle always culls, so sort out the drawing order.180for (int i = 0; i < 4; ++i) {181if (buf[i].screenpos.x < topleft->screenpos.x && buf[i].screenpos.y < topleft->screenpos.y)182topleft = &buf[i];183if (buf[i].screenpos.x > topright->screenpos.x && buf[i].screenpos.y < topright->screenpos.y)184topright = &buf[i];185if (buf[i].screenpos.x < bottomleft->screenpos.x && buf[i].screenpos.y > bottomleft->screenpos.y)186bottomleft = &buf[i];187if (buf[i].screenpos.x > bottomright->screenpos.x && buf[i].screenpos.y > bottomright->screenpos.y)188bottomright = &buf[i];189}190191RotateUV(v0, v1, *topright, *bottomleft);192193binner.AddTriangle(*topleft, *topright, *bottomleft);194binner.AddTriangle(*bottomleft, *topright, *topleft);195binner.AddTriangle(*topright, *bottomright, *bottomleft);196binner.AddTriangle(*bottomleft, *bottomright, *topright);197}198199void ProcessRect(const ClipVertexData &v0, const ClipVertexData &v1, BinManager &binner) {200if (!binner.State().throughMode) {201// If any verts were outside range, throw the entire prim away.202if (v0.OutsideRange() || v1.OutsideRange())203return;204205// We may discard the entire rect based on depth values.206int outsidePos = 0, outsideNeg = 0;207CheckOutsideZ(v0.clippos, outsidePos, outsideNeg);208CheckOutsideZ(v1.clippos, outsidePos, outsideNeg);209210// With depth clamp off, we discard the rectangle if even one vert is outside.211if (outsidePos + outsideNeg > 0 && !gstate.isDepthClampEnabled())212return;213// With it on, both must be outside in the same direction.214else if (outsidePos >= 2 || outsideNeg >= 2)215return;216217bool splitFog = v0.v.fogdepth != v1.v.fogdepth;218if (splitFog) {219// If they match the same 1/255, we can consider the fog flat. Seen in Resistance.220// More efficient if we can avoid splitting.221static constexpr float foghalfstep = 0.5f / 255.0f;222if (v1.v.fogdepth - foghalfstep <= v0.v.fogdepth && v1.v.fogdepth + foghalfstep >= v0.v.fogdepth)223splitFog = false;224}225if (splitFog) {226// Rectangles seem to always use nearest along X for fog depth, but reversed.227// TODO: Check exactness of middle.228VertexData vhalf0 = v1.v;229vhalf0.screenpos.x = v0.v.screenpos.x + (v1.v.screenpos.x - v0.v.screenpos.x) / 2;230vhalf0.texturecoords.x = v0.v.texturecoords.x + (v1.v.texturecoords.x - v0.v.texturecoords.x) / 2;231232VertexData vhalf1 = v1.v;233vhalf1.screenpos.x = v0.v.screenpos.x + (v1.v.screenpos.x - v0.v.screenpos.x) / 2;234vhalf1.screenpos.y = v0.v.screenpos.y;235vhalf1.texturecoords.x = v0.v.texturecoords.x + (v1.v.texturecoords.x - v0.v.texturecoords.x) / 2;236vhalf1.texturecoords.y = v0.v.texturecoords.y;237238VertexData vrev1 = v1.v;239vrev1.fogdepth = v0.v.fogdepth;240241if (binner.State().textureProj) {242AddTriangleRect(v0.v, vhalf0, binner);243AddTriangleRect(vhalf1, vrev1, binner);244} else {245binner.AddRect(v0.v, vhalf0);246binner.AddRect(vhalf1, vrev1);247}248} else if (binner.State().textureProj) {249AddTriangleRect(v0.v, v1.v, binner);250} else {251binner.AddRect(v0.v, v1.v);252}253} else {254// through mode handling255if (Rasterizer::RectangleFastPath(v0.v, v1.v, binner)) {256return;257} else if (gstate.isModeClear() && !gstate.isDitherEnabled()) {258binner.AddClearRect(v0.v, v1.v);259} else {260binner.AddRect(v0.v, v1.v);261}262}263}264265void ProcessPoint(const ClipVertexData &v0, BinManager &binner) {266// If any verts were outside range, throw the entire prim away.267if (!binner.State().throughMode) {268if (v0.OutsideRange())269return;270}271272// Points need no clipping. Will be bounds checked in the rasterizer (which seems backwards?)273binner.AddPoint(v0.v);274}275276void ProcessLine(const ClipVertexData &v0, const ClipVertexData &v1, BinManager &binner) {277if (binner.State().throughMode) {278// Actually, should clip this one too so we don't need to do bounds checks in the rasterizer.279binner.AddLine(v0.v, v1.v);280return;281}282283// If any verts were outside range, throw the entire prim away.284if (v0.OutsideRange() || v1.OutsideRange())285return;286287int outsidePos = 0, outsideNeg = 0;288CheckOutsideZ(v0.clippos, outsidePos, outsideNeg);289CheckOutsideZ(v1.clippos, outsidePos, outsideNeg);290291// With depth clamp off, we discard the line if even one vert is outside.292if (outsidePos + outsideNeg > 0 && !gstate.isDepthClampEnabled())293return;294// With it on, both must be outside in the same direction.295else if (outsidePos >= 2 || outsideNeg >= 2)296return;297298int mask0 = CalcClipMask(v0.clippos);299int mask1 = CalcClipMask(v1.clippos);300int mask = mask0 | mask1;301if ((mask & CLIP_NEG_Z_BIT) == 0) {302binner.AddLine(v0.v, v1.v);303return;304}305306ClipVertexData ClippedVertices[2] = { v0, v1 };307ClipVertexData *Vertices[2] = { &ClippedVertices[0], &ClippedVertices[1] };308CLIP_LINE(CLIP_NEG_Z_BIT, 0, 0, 1, 1);309310ClipVertexData data[2] = { *Vertices[0], *Vertices[1] };311if (!data[0].OutsideRange() && !data[1].OutsideRange())312binner.AddLine(data[0].v, data[1].v);313}314315void ProcessTriangle(const ClipVertexData &v0, const ClipVertexData &v1, const ClipVertexData &v2, const ClipVertexData &provoking, BinManager &binner) {316int mask = 0;317if (!binner.State().throughMode) {318// If any verts were outside range, throw the entire prim away.319if (v0.OutsideRange() || v1.OutsideRange() || v2.OutsideRange())320return;321// If all verts have negative W, we also cull.322if (v0.clippos.w < 0.0f && v1.clippos.w < 0.0f && v2.clippos.w < 0.0f)323return;324325mask |= CalcClipMask(v0.clippos);326mask |= CalcClipMask(v1.clippos);327mask |= CalcClipMask(v2.clippos);328329// We may discard the entire triangle based on depth values. First check what's outside.330int outsidePos = 0, outsideNeg = 0;331CheckOutsideZ(v0.clippos, outsidePos, outsideNeg);332CheckOutsideZ(v1.clippos, outsidePos, outsideNeg);333CheckOutsideZ(v2.clippos, outsidePos, outsideNeg);334335// With depth clamp off, we discard the triangle if even one vert is outside.336if (outsidePos + outsideNeg > 0 && !gstate.isDepthClampEnabled())337return;338// With it on, all three must be outside in the same direction.339else if (outsidePos >= 3 || outsideNeg >= 3)340return;341}342343// No clipping is common, let's skip processing if we can.344if ((mask & CLIP_NEG_Z_BIT) == 0) {345if (gstate.getShadeMode() == GE_SHADE_FLAT) {346// So that the order of clipping doesn't matter...347VertexData corrected2 = v2.v;348corrected2.color0 = provoking.v.color0;349corrected2.color1 = provoking.v.color1;350binner.AddTriangle(v0.v, v1.v, corrected2);351} else {352binner.AddTriangle(v0.v, v1.v, v2.v);353}354return;355}356357enum { NUM_CLIPPED_VERTICES = 3, NUM_INDICES = NUM_CLIPPED_VERTICES + 3 };358359ClipVertexData* Vertices[NUM_INDICES];360ClipVertexData ClippedVertices[NUM_INDICES];361for (int i = 0; i < NUM_INDICES; ++i)362Vertices[i] = &ClippedVertices[i];363364// TODO: Change logic when it's a backface (why? In what way?)365ClippedVertices[0] = v0;366ClippedVertices[1] = v1;367ClippedVertices[2] = v2;368369int indices[NUM_INDICES] = { 0, 1, 2, SKIP_FLAG, SKIP_FLAG, SKIP_FLAG };370int numIndices = 3;371372for (int i = 0; i < 3; i += 3) {373int vlist[2][2*6+1];374int *inlist = vlist[0], *outlist = vlist[1];375int n = 3;376int numVertices = 3;377378inlist[0] = 0;379inlist[1] = 1;380inlist[2] = 2;381382// mark this triangle as unused in case it should be completely clipped383indices[0] = SKIP_FLAG;384indices[1] = SKIP_FLAG;385indices[2] = SKIP_FLAG;386387// The PSP only clips on negative Z (importantly, regardless of viewport.)388CLIP_POLY(CLIP_NEG_Z_BIT, 0, 0, 1, 1);389390// transform the poly in inlist into triangles391indices[0] = inlist[0];392indices[1] = inlist[1];393indices[2] = inlist[2];394for (int j = 3; j < n; ++j) {395indices[numIndices++] = inlist[0];396indices[numIndices++] = inlist[j - 1];397indices[numIndices++] = inlist[j];398}399}400401for (int i = 0; i + 3 <= numIndices; i += 3) {402if (indices[i] != SKIP_FLAG) {403ClipVertexData &subv0 = *Vertices[indices[i + 0]];404ClipVertexData &subv1 = *Vertices[indices[i + 1]];405ClipVertexData &subv2 = *Vertices[indices[i + 2]];406407if (subv0.OutsideRange() || subv1.OutsideRange() || subv2.OutsideRange())408continue;409410if (gstate.getShadeMode() == GE_SHADE_FLAT) {411// So that the order of clipping doesn't matter...412subv2.v.color0 = provoking.v.color0;413subv2.v.color1 = provoking.v.color1;414}415416binner.AddTriangle(subv0.v, subv1.v, subv2.v);417}418}419}420421} // namespace422423424