1// This file is part of meshoptimizer library; see meshoptimizer.h for version/license details
2#include "meshoptimizer.h"
3
4#include <assert.h>
5#include <float.h>
6#include <string.h>
7
8// This work is based on:
9// Nicolas Capens. Advanced Rasterization. 2004
10namespace meshopt
11{
12
13const int kViewport = 256;
14
15struct OverdrawBuffer
16{
17 float z[kViewport][kViewport][2];
18 unsigned int overdraw[kViewport][kViewport][2];
19};
20
21#ifndef min
22#define min(a, b) ((a) < (b) ? (a) : (b))
23#endif
24
25#ifndef max
26#define max(a, b) ((a) > (b) ? (a) : (b))
27#endif
28
29static float computeDepthGradients(float& dzdx, float& dzdy, float x1, float y1, float z1, float x2, float y2, float z2, float x3, float y3, float z3)
30{
31 // z2 = z1 + dzdx * (x2 - x1) + dzdy * (y2 - y1)
32 // z3 = z1 + dzdx * (x3 - x1) + dzdy * (y3 - y1)
33 // (x2-x1 y2-y1)(dzdx) = (z2-z1)
34 // (x3-x1 y3-y1)(dzdy) (z3-z1)
35 // we'll solve it with Cramer's rule
36 float det = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
37 float invdet = (det == 0) ? 0 : 1 / det;
38
39 dzdx = (z2 - z1) * (y3 - y1) - (y2 - y1) * (z3 - z1) * invdet;
40 dzdy = (x2 - x1) * (z3 - z1) - (z2 - z1) * (x3 - x1) * invdet;
41
42 return det;
43}
44
45// half-space fixed point triangle rasterizer
46static void rasterize(OverdrawBuffer* buffer, float v1x, float v1y, float v1z, float v2x, float v2y, float v2z, float v3x, float v3y, float v3z)
47{
48 // compute depth gradients
49 float DZx, DZy;
50 float det = computeDepthGradients(DZx, DZy, v1x, v1y, v1z, v2x, v2y, v2z, v3x, v3y, v3z);
51 int sign = det > 0;
52
53 // flip backfacing triangles to simplify rasterization logic
54 if (sign)
55 {
56 // flipping v2 & v3 preserves depth gradients since they're based on v1
57 float t;
58 t = v2x, v2x = v3x, v3x = t;
59 t = v2y, v2y = v3y, v3y = t;
60 t = v2z, v2z = v3z, v3z = t;
61
62 // flip depth since we rasterize backfacing triangles to second buffer with reverse Z; only v1z is used below
63 v1z = kViewport - v1z;
64 DZx = -DZx;
65 DZy = -DZy;
66 }
67
68 // coordinates, 28.4 fixed point
69 int X1 = int(16.0f * v1x + 0.5f);
70 int X2 = int(16.0f * v2x + 0.5f);
71 int X3 = int(16.0f * v3x + 0.5f);
72
73 int Y1 = int(16.0f * v1y + 0.5f);
74 int Y2 = int(16.0f * v2y + 0.5f);
75 int Y3 = int(16.0f * v3y + 0.5f);
76
77 // bounding rectangle, clipped against viewport
78 // since we rasterize pixels with covered centers, min >0.5 should round up
79 // as for max, due to top-left filling convention we will never rasterize right/bottom edges
80 // so max >= 0.5 should round down
81 int minx = max((min(X1, min(X2, X3)) + 7) >> 4, 0);
82 int maxx = min((max(X1, max(X2, X3)) + 7) >> 4, kViewport);
83 int miny = max((min(Y1, min(Y2, Y3)) + 7) >> 4, 0);
84 int maxy = min((max(Y1, max(Y2, Y3)) + 7) >> 4, kViewport);
85
86 // deltas, 28.4 fixed point
87 int DX12 = X1 - X2;
88 int DX23 = X2 - X3;
89 int DX31 = X3 - X1;
90
91 int DY12 = Y1 - Y2;
92 int DY23 = Y2 - Y3;
93 int DY31 = Y3 - Y1;
94
95 // fill convention correction
96 int TL1 = DY12 < 0 || (DY12 == 0 && DX12 > 0);
97 int TL2 = DY23 < 0 || (DY23 == 0 && DX23 > 0);
98 int TL3 = DY31 < 0 || (DY31 == 0 && DX31 > 0);
99
100 // half edge equations, 24.8 fixed point
101 // note that we offset minx/miny by half pixel since we want to rasterize pixels with covered centers
102 int FX = (minx << 4) + 8;
103 int FY = (miny << 4) + 8;
104 int CY1 = DX12 * (FY - Y1) - DY12 * (FX - X1) + TL1 - 1;
105 int CY2 = DX23 * (FY - Y2) - DY23 * (FX - X2) + TL2 - 1;
106 int CY3 = DX31 * (FY - Y3) - DY31 * (FX - X3) + TL3 - 1;
107 float ZY = v1z + (DZx * float(FX - X1) + DZy * float(FY - Y1)) * (1 / 16.f);
108
109 for (int y = miny; y < maxy; y++)
110 {
111 int CX1 = CY1;
112 int CX2 = CY2;
113 int CX3 = CY3;
114 float ZX = ZY;
115
116 for (int x = minx; x < maxx; x++)
117 {
118 // check if all CXn are non-negative
119 if ((CX1 | CX2 | CX3) >= 0)
120 {
121 if (ZX >= buffer->z[y][x][sign])
122 {
123 buffer->z[y][x][sign] = ZX;
124 buffer->overdraw[y][x][sign]++;
125 }
126 }
127
128 // signed left shift is UB for negative numbers so use unsigned-signed casts
129 CX1 -= int(unsigned(DY12) << 4);
130 CX2 -= int(unsigned(DY23) << 4);
131 CX3 -= int(unsigned(DY31) << 4);
132 ZX += DZx;
133 }
134
135 // signed left shift is UB for negative numbers so use unsigned-signed casts
136 CY1 += int(unsigned(DX12) << 4);
137 CY2 += int(unsigned(DX23) << 4);
138 CY3 += int(unsigned(DX31) << 4);
139 ZY += DZy;
140 }
141}
142
143} // namespace meshopt
144
145meshopt_OverdrawStatistics meshopt_analyzeOverdraw(const unsigned int* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride)
146{
147 using namespace meshopt;
148
149 assert(index_count % 3 == 0);
150 assert(vertex_positions_stride >= 12 && vertex_positions_stride <= 256);
151 assert(vertex_positions_stride % sizeof(float) == 0);
152
153 meshopt_Allocator allocator;
154
155 size_t vertex_stride_float = vertex_positions_stride / sizeof(float);
156
157 meshopt_OverdrawStatistics result = {};
158
159 float minv[3] = {FLT_MAX, FLT_MAX, FLT_MAX};
160 float maxv[3] = {-FLT_MAX, -FLT_MAX, -FLT_MAX};
161
162 for (size_t i = 0; i < vertex_count; ++i)
163 {
164 const float* v = vertex_positions + i * vertex_stride_float;
165
166 for (int j = 0; j < 3; ++j)
167 {
168 minv[j] = min(minv[j], v[j]);
169 maxv[j] = max(maxv[j], v[j]);
170 }
171 }
172
173 float extent = max(maxv[0] - minv[0], max(maxv[1] - minv[1], maxv[2] - minv[2]));
174 float scale = kViewport / extent;
175
176 float* triangles = allocator.allocate<float>(index_count * 3);
177
178 for (size_t i = 0; i < index_count; ++i)
179 {
180 unsigned int index = indices[i];
181 assert(index < vertex_count);
182
183 const float* v = vertex_positions + index * vertex_stride_float;
184
185 triangles[i * 3 + 0] = (v[0] - minv[0]) * scale;
186 triangles[i * 3 + 1] = (v[1] - minv[1]) * scale;
187 triangles[i * 3 + 2] = (v[2] - minv[2]) * scale;
188 }
189
190 OverdrawBuffer* buffer = allocator.allocate<OverdrawBuffer>(1);
191
192 for (int axis = 0; axis < 3; ++axis)
193 {
194 memset(buffer, 0, sizeof(OverdrawBuffer));
195
196 for (size_t i = 0; i < index_count; i += 3)
197 {
198 const float* vn0 = &triangles[3 * (i + 0)];
199 const float* vn1 = &triangles[3 * (i + 1)];
200 const float* vn2 = &triangles[3 * (i + 2)];
201
202 switch (axis)
203 {
204 case 0:
205 rasterize(buffer, vn0[2], vn0[1], vn0[0], vn1[2], vn1[1], vn1[0], vn2[2], vn2[1], vn2[0]);
206 break;
207 case 1:
208 rasterize(buffer, vn0[0], vn0[2], vn0[1], vn1[0], vn1[2], vn1[1], vn2[0], vn2[2], vn2[1]);
209 break;
210 case 2:
211 rasterize(buffer, vn0[1], vn0[0], vn0[2], vn1[1], vn1[0], vn1[2], vn2[1], vn2[0], vn2[2]);
212 break;
213 }
214 }
215
216 for (int y = 0; y < kViewport; ++y)
217 for (int x = 0; x < kViewport; ++x)
218 for (int s = 0; s < 2; ++s)
219 {
220 unsigned int overdraw = buffer->overdraw[y][x][s];
221
222 result.pixels_covered += overdraw > 0;
223 result.pixels_shaded += overdraw;
224 }
225 }
226
227 result.overdraw = result.pixels_covered ? float(result.pixels_shaded) / float(result.pixels_covered) : 0.f;
228
229 return result;
230}
231