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/Common/SplineCommon.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 <string.h>18#include <algorithm>1920#include "Common/Common.h"21#include "Common/CPUDetect.h"22#include "Common/Profiler/Profiler.h"23#include "GPU/Common/GPUStateUtils.h"24#include "GPU/Common/SplineCommon.h"25#include "GPU/Common/DrawEngineCommon.h"26#include "GPU/ge_constants.h"27#include "GPU/GPUState.h" // only needed for UVScale stuff2829class SimpleBufferManager {30private:31u8 *buf_;32size_t totalSize, maxSize_;33public:34SimpleBufferManager(u8 *buf, size_t maxSize)35: buf_(buf), totalSize(0), maxSize_(maxSize) {}3637u8 *Allocate(size_t size) {38size = (size + 15) & ~15; // Align for 16 bytes3940if ((totalSize + size) > maxSize_)41return nullptr; // No more memory4243size_t tmp = totalSize;44totalSize += size;45return buf_ + tmp;46}47};4849namespace Spline {5051static void CopyQuadIndex(u16 *&indices, GEPatchPrimType type, const int idx0, const int idx1, const int idx2, const int idx3) {52if (type == GE_PATCHPRIM_LINES) {53*(indices++) = idx0;54*(indices++) = idx2;55*(indices++) = idx1;56*(indices++) = idx3;57*(indices++) = idx1;58*(indices++) = idx2;59} else {60*(indices++) = idx0;61*(indices++) = idx2;62*(indices++) = idx1;63*(indices++) = idx1;64*(indices++) = idx2;65*(indices++) = idx3;66}67}6869void BuildIndex(u16 *indices, int &count, int num_u, int num_v, GEPatchPrimType prim_type, int total) {70for (int v = 0; v < num_v; ++v) {71for (int u = 0; u < num_u; ++u) {72int idx0 = v * (num_u + 1) + u + total; // Top left73int idx2 = (v + 1) * (num_u + 1) + u + total; // Bottom left7475CopyQuadIndex(indices, prim_type, idx0, idx0 + 1, idx2, idx2 + 1);76count += 6;77}78}79}8081class Bezier3DWeight {82private:83static void CalcWeights(float t, Weight &w) {84// Bernstein 3D basis polynomial85w.basis[0] = (1 - t) * (1 - t) * (1 - t);86w.basis[1] = 3 * t * (1 - t) * (1 - t);87w.basis[2] = 3 * t * t * (1 - t);88w.basis[3] = t * t * t;8990// Derivative91w.deriv[0] = -3 * (1 - t) * (1 - t);92w.deriv[1] = 9 * t * t - 12 * t + 3;93w.deriv[2] = 3 * (2 - 3 * t) * t;94w.deriv[3] = 3 * t * t;95}96public:97static Weight *CalcWeightsAll(u32 key) {98int tess = (int)key;99Weight *weights = new Weight[tess + 1];100const float inv_tess = 1.0f / (float)tess;101for (int i = 0; i < tess + 1; ++i) {102const float t = (float)i * inv_tess;103CalcWeights(t, weights[i]);104}105return weights;106}107108static u32 ToKey(int tess, int count, int type) {109return tess;110}111112static int CalcSize(int tess, int count) {113return tess + 1;114}115116static WeightCache<Bezier3DWeight> weightsCache;117};118119class Spline3DWeight {120private:121struct KnotDiv {122float _3_0 = 1.0f / 3.0f;123float _4_1 = 1.0f / 3.0f;124float _5_2 = 1.0f / 3.0f;125float _3_1 = 1.0f / 2.0f;126float _4_2 = 1.0f / 2.0f;127float _3_2 = 1.0f; // Always 1128};129130// knot should be an array sized n + 5 (n + 1 + 1 + degree (cubic))131static void CalcKnots(int n, int type, float *knots, KnotDiv *divs) {132// Basic theory (-2 to +3), optimized with KnotDiv (-2 to +0)133// for (int i = 0; i < n + 5; ++i) {134for (int i = 0; i < n + 2; ++i) {135knots[i] = (float)i - 2;136}137138// The first edge is open139if ((type & 1) != 0) {140knots[0] = 0;141knots[1] = 0;142143divs[0]._3_0 = 1.0f;144divs[0]._4_1 = 1.0f / 2.0f;145divs[0]._3_1 = 1.0f;146if (n > 1)147divs[1]._3_0 = 1.0f / 2.0f;148}149// The last edge is open150if ((type & 2) != 0) {151// knots[n + 2] = (float)n; // Got rid of this line optimized with KnotDiv152// knots[n + 3] = (float)n; // Got rid of this line optimized with KnotDiv153// knots[n + 4] = (float)n; // Got rid of this line optimized with KnotDiv154divs[n - 1]._4_1 = 1.0f / 2.0f;155divs[n - 1]._5_2 = 1.0f;156divs[n - 1]._4_2 = 1.0f;157if (n > 1)158divs[n - 2]._5_2 = 1.0f / 2.0f;159}160}161162static void CalcWeights(float t, const float *knots, const KnotDiv &div, Weight &w) {163#ifdef _M_SSE164const __m128 knot012 = _mm_loadu_ps(knots);165const __m128 t012 = _mm_sub_ps(_mm_set_ps1(t), knot012);166const __m128 f30_41_52 = _mm_mul_ps(t012, _mm_loadu_ps(&div._3_0));167const __m128 f52_31_42 = _mm_mul_ps(t012, _mm_loadu_ps(&div._5_2));168169// Following comments are for explains order of the multiply.170// float a = (1-f30)*(1-f31);171// float c = (1-f41)*(1-f42);172// float b = ( f31 * f41);173// float d = ( f42 * f52);174const __m128 f30_41_31_42 = _mm_shuffle_ps(f30_41_52, f52_31_42, _MM_SHUFFLE(2, 1, 1, 0));175const __m128 f31_42_41_52 = _mm_shuffle_ps(f52_31_42, f30_41_52, _MM_SHUFFLE(2, 1, 2, 1));176const __m128 c1_1_0_0 = { 1, 1, 0, 0 };177const __m128 acbd = _mm_mul_ps(_mm_sub_ps(c1_1_0_0, f30_41_31_42), _mm_sub_ps(c1_1_0_0, f31_42_41_52));178179alignas(16) float f_t012[4];180alignas(16) float f_acbd[4];181alignas(16) float f_f30_41_31_42[4];182_mm_store_ps(f_t012, t012);183_mm_store_ps(f_acbd, acbd);184_mm_store_ps(f_f30_41_31_42, f30_41_31_42);185186const float &f32 = f_t012[2];187188const float &a = f_acbd[0];189const float &b = f_acbd[2];190const float &c = f_acbd[1];191const float &d = f_acbd[3];192193// For derivative194const float &f31 = f_f30_41_31_42[2];195const float &f42 = f_f30_41_31_42[3];196#else197// TODO: Maybe compilers could be coaxed into vectorizing this code without the above explicitly...198float t0 = (t - knots[0]);199float t1 = (t - knots[1]);200float t2 = (t - knots[2]);201202float f30 = t0 * div._3_0;203float f41 = t1 * div._4_1;204float f52 = t2 * div._5_2;205float f31 = t1 * div._3_1;206float f42 = t2 * div._4_2;207float f32 = t2 * div._3_2;208209float a = (1 - f30) * (1 - f31);210float b = (f31 * f41);211float c = (1 - f41) * (1 - f42);212float d = (f42 * f52);213#endif214w.basis[0] = a * (1 - f32); // (1-f30)*(1-f31)*(1-f32)215w.basis[1] = 1 - a - b + ((a + b + c - 1) * f32);216w.basis[2] = b + ((1 - b - c - d) * f32);217w.basis[3] = d * f32; // f32*f42*f52218219// Derivative220float i1 = (1 - f31) * (1 - f32);221float i2 = f31 * (1 - f32) + (1 - f42) * f32;222float i3 = f42 * f32;223224float f130 = i1 * div._3_0;225float f241 = i2 * div._4_1;226float f352 = i3 * div._5_2;227228w.deriv[0] = 3 * (0 - f130);229w.deriv[1] = 3 * (f130 - f241);230w.deriv[2] = 3 * (f241 - f352);231w.deriv[3] = 3 * (f352 - 0);232}233public:234Weight *CalcWeightsAll(u32 key) {235int tess, count, type;236FromKey(key, tess, count, type);237const int num_patches = count - 3;238Weight *weights = new Weight[tess * num_patches + 1];239240// float *knots = new float[num_patches + 5];241float *knots = new float[num_patches + 2]; // Optimized with KnotDiv, must use +5 in theory242KnotDiv *divs = new KnotDiv[num_patches];243CalcKnots(num_patches, type, knots, divs);244245const float inv_tess = 1.0f / (float)tess;246for (int i = 0; i < num_patches; ++i) {247const int start = (i == 0) ? 0 : 1;248for (int j = start; j <= tess; ++j) {249const int index = i * tess + j;250const float t = (float)index * inv_tess;251CalcWeights(t, knots + i, divs[i], weights[index]);252}253}254255delete[] knots;256delete[] divs;257258return weights;259}260261static u32 ToKey(int tess, int count, int type) {262return tess | (count << 8) | (type << 16);263}264265static void FromKey(u32 key, int &tess, int &count, int &type) {266tess = key & 0xFF; count = (key >> 8) & 0xFF; type = (key >> 16) & 0xFF;267}268269static int CalcSize(int tess, int count) {270return (count - 3) * tess + 1;271}272273static WeightCache<Spline3DWeight> weightsCache;274};275276WeightCache<Bezier3DWeight> Bezier3DWeight::weightsCache;277WeightCache<Spline3DWeight> Spline3DWeight::weightsCache;278279// Tessellate single patch (4x4 control points)280template<typename T>281class Tessellator {282private:283const T *const p[4]; // T p[v][u]; 4x4 control points284T u[4]; // Pre-tessellated U lines285public:286Tessellator(const T *p, const int idx[4]) : p{ p + idx[0], p + idx[1], p + idx[2], p + idx[3] } {}287288// Linear combination289T Sample(const T p[4], const float w[4]) {290return p[0] * w[0] + p[1] * w[1] + p[2] * w[2] + p[3] * w[3];291}292293void SampleEdgeU(int idx) {294u[0] = p[0][idx];295u[1] = p[1][idx];296u[2] = p[2][idx];297u[3] = p[3][idx];298}299300void SampleU(const float weights[4]) {301if (weights[0] == 1.0f) { SampleEdgeU(0); return; } // weights = {1,0,0,0}, first edge is open.302if (weights[3] == 1.0f) { SampleEdgeU(3); return; } // weights = {0,0,0,1}, last edge is open.303304u[0] = Sample(p[0], weights);305u[1] = Sample(p[1], weights);306u[2] = Sample(p[2], weights);307u[3] = Sample(p[3], weights);308}309310T SampleV(const float weights[4]) {311if (weights[0] == 1.0f) return u[0]; // weights = {1,0,0,0}, first edge is open.312if (weights[3] == 1.0f) return u[3]; // weights = {0,0,0,1}, last edge is open.313314return Sample(u, weights);315}316};317318ControlPoints::ControlPoints(const SimpleVertex *const *points, int size, SimpleBufferManager &managedBuf) {319pos = (Vec3f *)managedBuf.Allocate(sizeof(Vec3f) * size);320tex = (Vec2f *)managedBuf.Allocate(sizeof(Vec2f) * size);321col = (Vec4f *)managedBuf.Allocate(sizeof(Vec4f) * size);322if (pos && tex && col)323Convert(points, size);324}325326void ControlPoints::Convert(const SimpleVertex *const *points, int size) {327for (int i = 0; i < size; ++i) {328pos[i] = Vec3f(points[i]->pos);329tex[i] = Vec2f(points[i]->uv);330col[i] = Vec4f::FromRGBA(points[i]->color_32);331}332defcolor = points[0]->color_32;333}334335template<class Surface>336class SubdivisionSurface {337public:338template <bool sampleNrm, bool sampleCol, bool sampleTex, bool useSSE4, bool patchFacing>339static void Tessellate(OutputBuffers &output, const Surface &surface, const ControlPoints &points, const Weight2D &weights) {340const float inv_u = 1.0f / (float)surface.tess_u;341const float inv_v = 1.0f / (float)surface.tess_v;342343for (int patch_u = 0; patch_u < surface.num_patches_u; ++patch_u) {344const int start_u = surface.GetTessStart(patch_u);345for (int patch_v = 0; patch_v < surface.num_patches_v; ++patch_v) {346const int start_v = surface.GetTessStart(patch_v);347348// Prepare 4x4 control points to tessellate349const int idx = surface.GetPointIndex(patch_u, patch_v);350const int idx_v[4] = { idx, idx + surface.num_points_u, idx + surface.num_points_u * 2, idx + surface.num_points_u * 3 };351Tessellator<Vec3f> tess_pos(points.pos, idx_v);352Tessellator<Vec4f> tess_col(points.col, idx_v);353Tessellator<Vec2f> tess_tex(points.tex, idx_v);354Tessellator<Vec3f> tess_nrm(points.pos, idx_v);355356for (int tile_u = start_u; tile_u <= surface.tess_u; ++tile_u) {357const int index_u = surface.GetIndexU(patch_u, tile_u);358const Weight &wu = weights.u[index_u];359360// Pre-tessellate U lines361tess_pos.SampleU(wu.basis);362if constexpr (sampleCol)363tess_col.SampleU(wu.basis);364if constexpr (sampleTex)365tess_tex.SampleU(wu.basis);366if constexpr (sampleNrm)367tess_nrm.SampleU(wu.deriv);368369for (int tile_v = start_v; tile_v <= surface.tess_v; ++tile_v) {370const int index_v = surface.GetIndexV(patch_v, tile_v);371const Weight &wv = weights.v[index_v];372373SimpleVertex &vert = output.vertices[surface.GetIndex(index_u, index_v, patch_u, patch_v)];374375// Tessellate376vert.pos = tess_pos.SampleV(wv.basis);377if constexpr (sampleCol) {378vert.color_32 = tess_col.SampleV(wv.basis).ToRGBA();379} else {380vert.color_32 = points.defcolor;381}382if constexpr (sampleTex) {383tess_tex.SampleV(wv.basis).Write(vert.uv);384} else {385// Generate texcoord386vert.uv[0] = patch_u + tile_u * inv_u;387vert.uv[1] = patch_v + tile_v * inv_v;388}389if constexpr (sampleNrm) {390const Vec3f derivU = tess_nrm.SampleV(wv.basis);391const Vec3f derivV = tess_pos.SampleV(wv.deriv);392393vert.nrm = Cross(derivU, derivV).Normalized(useSSE4);394if constexpr (patchFacing)395vert.nrm *= -1.0f;396} else {397vert.nrm.SetZero();398vert.nrm.z = 1.0f;399}400}401}402}403}404405surface.BuildIndex(output.indices, output.count);406}407408using TessFunc = void(*)(OutputBuffers &, const Surface &, const ControlPoints &, const Weight2D &);409TEMPLATE_PARAMETER_DISPATCHER_FUNCTION(Tess, SubdivisionSurface::Tessellate, TessFunc);410411static void Tessellate(OutputBuffers &output, const Surface &surface, const ControlPoints &points, const Weight2D &weights, u32 origVertType) {412const bool params[] = {413(origVertType & GE_VTYPE_NRM_MASK) != 0 || gstate.isLightingEnabled(),414(origVertType & GE_VTYPE_COL_MASK) != 0,415(origVertType & GE_VTYPE_TC_MASK) != 0,416cpu_info.bSSE4_1,417surface.patchFacing,418};419static TemplateParameterDispatcher<TessFunc, ARRAY_SIZE(params), Tess> dispatcher; // Initialize only once420421TessFunc func = dispatcher.GetFunc(params);422func(output, surface, points, weights);423}424};425426template<class Surface>427void SoftwareTessellation(OutputBuffers &output, const Surface &surface, u32 origVertType, const ControlPoints &points) {428using WeightType = typename Surface::WeightType;429u32 key_u = WeightType::ToKey(surface.tess_u, surface.num_points_u, surface.type_u);430u32 key_v = WeightType::ToKey(surface.tess_v, surface.num_points_v, surface.type_v);431Weight2D weights(WeightType::weightsCache, key_u, key_v);432433SubdivisionSurface<Surface>::Tessellate(output, surface, points, weights, origVertType);434}435436template void SoftwareTessellation<BezierSurface>(OutputBuffers &output, const BezierSurface &surface, u32 origVertType, const ControlPoints &points);437template void SoftwareTessellation<SplineSurface>(OutputBuffers &output, const SplineSurface &surface, u32 origVertType, const ControlPoints &points);438439template<class Surface>440static void HardwareTessellation(OutputBuffers &output, const Surface &surface, u32 origVertType,441const SimpleVertex *const *points, TessellationDataTransfer *tessDataTransfer) {442using WeightType = typename Surface::WeightType;443u32 key_u = WeightType::ToKey(surface.tess_u, surface.num_points_u, surface.type_u);444u32 key_v = WeightType::ToKey(surface.tess_v, surface.num_points_v, surface.type_v);445Weight2D weights(WeightType::weightsCache, key_u, key_v);446weights.size_u = WeightType::CalcSize(surface.tess_u, surface.num_points_u);447weights.size_v = WeightType::CalcSize(surface.tess_v, surface.num_points_v);448tessDataTransfer->SendDataToShader(points, surface.num_points_u, surface.num_points_v, origVertType, weights);449450// Generating simple input vertices for the spline-computing vertex shader.451float inv_u = 1.0f / (float)surface.tess_u;452float inv_v = 1.0f / (float)surface.tess_v;453for (int patch_u = 0; patch_u < surface.num_patches_u; ++patch_u) {454const int start_u = surface.GetTessStart(patch_u);455for (int patch_v = 0; patch_v < surface.num_patches_v; ++patch_v) {456const int start_v = surface.GetTessStart(patch_v);457for (int tile_u = start_u; tile_u <= surface.tess_u; ++tile_u) {458const int index_u = surface.GetIndexU(patch_u, tile_u);459for (int tile_v = start_v; tile_v <= surface.tess_v; ++tile_v) {460const int index_v = surface.GetIndexV(patch_v, tile_v);461SimpleVertex &vert = output.vertices[surface.GetIndex(index_u, index_v, patch_u, patch_v)];462// Index for the weights463vert.pos.x = index_u;464vert.pos.y = index_v;465// For texcoord generation466vert.nrm.x = patch_u + (float)tile_u * inv_u;467vert.nrm.y = patch_v + (float)tile_v * inv_v;468// Patch position469vert.pos.z = patch_u;470vert.nrm.z = patch_v;471}472}473}474}475surface.BuildIndex(output.indices, output.count);476}477478} // namespace Spline479480using namespace Spline;481482void DrawEngineCommon::ClearSplineBezierWeights() {483Bezier3DWeight::weightsCache.Clear();484Spline3DWeight::weightsCache.Clear();485}486487// Specialize to make instance (to avoid link error).488template void DrawEngineCommon::SubmitCurve<BezierSurface>(const void *control_points, const void *indices, BezierSurface &surface, u32 vertType, int *bytesRead, const char *scope);489template void DrawEngineCommon::SubmitCurve<SplineSurface>(const void *control_points, const void *indices, SplineSurface &surface, u32 vertType, int *bytesRead, const char *scope);490491template<class Surface>492void DrawEngineCommon::SubmitCurve(const void *control_points, const void *indices, Surface &surface, u32 vertType, int *bytesRead, const char *scope) {493PROFILE_THIS_SCOPE(scope);494495// Real hardware seems to draw nothing when given < 4 either U or V.496// This would result in num_patches_u / num_patches_v being 0.497if (surface.num_points_u < 4 || surface.num_points_v < 4)498return;499500SimpleBufferManager managedBuf(decoded_, DECODED_VERTEX_BUFFER_SIZE / 2);501502int num_points = surface.num_points_u * surface.num_points_v;503u16 index_lower_bound = 0;504u16 index_upper_bound = num_points - 1;505IndexConverter ConvertIndex(vertType, indices);506if (indices)507GetIndexBounds(indices, num_points, vertType, &index_lower_bound, &index_upper_bound);508509VertexDecoder *origVDecoder = GetVertexDecoder(GetVertTypeID(vertType, gstate.getUVGenMode(), decOptions_.applySkinInDecode));510*bytesRead = num_points * origVDecoder->VertexSize();511512// Simplify away bones and morph before proceeding513// There are normally not a lot of control points so just splitting decoded should be reasonably safe, although not great.514SimpleVertex *simplified_control_points = (SimpleVertex *)managedBuf.Allocate(sizeof(SimpleVertex) * (index_upper_bound + 1));515if (!simplified_control_points) {516ERROR_LOG(Log::G3D, "Failed to allocate space for simplified control points, skipping curve draw");517return;518}519520u8 *temp_buffer = managedBuf.Allocate(sizeof(SimpleVertex) * num_points);521if (!temp_buffer) {522ERROR_LOG(Log::G3D, "Failed to allocate space for temp buffer, skipping curve draw");523return;524}525526u32 origVertType = vertType;527vertType = NormalizeVertices((u8 *)simplified_control_points, temp_buffer, (u8 *)control_points, index_lower_bound, index_upper_bound, vertType);528529VertexDecoder *vdecoder = GetVertexDecoder(vertType);530531int vertexSize = vdecoder->VertexSize();532if (vertexSize != sizeof(SimpleVertex)) {533ERROR_LOG(Log::G3D, "Something went really wrong, vertex size: %d vs %d", vertexSize, (int)sizeof(SimpleVertex));534}535536// Make an array of pointers to the control points, to get rid of indices.537const SimpleVertex **points = (const SimpleVertex **)managedBuf.Allocate(sizeof(SimpleVertex *) * num_points);538if (!points) {539ERROR_LOG(Log::G3D, "Failed to allocate space for control point pointers, skipping curve draw");540return;541}542for (int idx = 0; idx < num_points; idx++)543points[idx] = simplified_control_points + (indices ? ConvertIndex(idx) : idx);544545OutputBuffers output;546output.vertices = (SimpleVertex *)(decoded_ + DECODED_VERTEX_BUFFER_SIZE / 2);547output.indices = decIndex_;548output.count = 0;549550int maxVerts = DECODED_VERTEX_BUFFER_SIZE / 2 / vertexSize;551552surface.Init(maxVerts);553554if (CanUseHardwareTessellation(surface.primType)) {555HardwareTessellation(output, surface, origVertType, points, tessDataTransfer);556} else {557ControlPoints cpoints(points, num_points, managedBuf);558if (cpoints.IsValid())559SoftwareTessellation(output, surface, origVertType, cpoints);560else561ERROR_LOG(Log::G3D, "Failed to allocate space for control point values, skipping curve draw");562}563564u32 vertTypeWithIndex16 = (vertType & ~GE_VTYPE_IDX_MASK) | GE_VTYPE_IDX_16BIT;565566UVScale prevUVScale;567if (origVertType & GE_VTYPE_TC_MASK) {568// We scaled during Normalize already so let's turn it off when drawing.569prevUVScale = gstate_c.uv;570gstate_c.uv.uScale = 1.0f;571gstate_c.uv.vScale = 1.0f;572gstate_c.uv.uOff = 0;573gstate_c.uv.vOff = 0;574}575576uint32_t vertTypeID = GetVertTypeID(vertTypeWithIndex16, gstate.getUVGenMode(), decOptions_.applySkinInDecode);577int generatedBytesRead;578if (output.count)579DispatchSubmitPrim(output.vertices, output.indices, PatchPrimToPrim(surface.primType), output.count, vertTypeID, true, &generatedBytesRead);580581if (flushOnParams_)582DispatchFlush();583584if (origVertType & GE_VTYPE_TC_MASK) {585gstate_c.uv = prevUVScale;586}587}588589590