More pages: 1 2 3
4 5
Triangulation
Wednesday, January 14, 2009 | Permalink
When you look at a highly tessellated model it's generally understood that it will be vertex processing heavy. Not quite as widely understood is the fact that increasing polygon count also adds to the fragment shading cost, even if the number of pixels covered on the screen remains the same. This is because fragments are processed in quads. So whenever a polygon edge cuts through a 2x2 pixel area, that quad will be processed twice, once for both of the polygons covering it. If several polygons cut through it, it may be processed multiple times. If the fragment shader is complex, it could easily become the bottleneck instead of the vertex shader. The rasterizer may also not be able to rasterize very thin triangles very efficiently. Since only pixels that have their pixel centers covered (or any of the sample locations in case of multisampling) are shaded the quads that need processing may not be adjacent. This will in general cause the rasterizer to require additional cycles. Some rasterizers may also rasterize at fixed patterns, for instance an 4x4 square for a 16 pipe card, which further reduces the performance of thin triangles. In addition you also get overhead because of less optimal memory accesses than if everything would be fully covered and written to at once. Adding multisampling into the mix further adds to the cost of polygon edges.
The other day I was looking at a particularly problematic scene. I noticed that a rounded object in the scene was triangulated pretty much as a fan, which created many long and thin triangles, which was hardly optimal for rasterization. While this wasn't the main problem of the scene it made me think of how bad such a topology could be. So I created a small test case to measure the performance of three different layouts of a circle. I used a non-trivial (but not extreme) fragment shader.
The most intuitive way to triangulate a circle would be to create a fan from the center. It's also a very bad way to do it. Another less intuitive but also very bad way to do it is to create a triangle strip. A good way to triangulate it is to start off with an equilateral triangle in the center and then recursively add new triangles along the edge. I don't know if this scheme has a particular name, but I call it "max area" here as it's a greedy algorithm that in every step adds the triangle that would grab the largest possible area out of the remaining parts on the circle. Intuitively I'd consider this close to optimal in general, but I'm sure there are examples where you could beat such a strategy with another division scheme. In any case, the three contenders look like this:
And their performance look like this. The number along the x-axis is the vertex count around the circle and the y-axis is frames per second.
Adding multisampling into the mix further adds to the burden with the first two methods, while the max area division is still mostly unaffected by the added polygons all the way across the chart.
Anonymous
Tuesday, March 24, 2009
PyFFI is a program that allows mesh optimization
http://sourceforge.net/projects/pyffi
hcpizzi
Tuesday, June 9, 2009
I guess this affects the workload of the rasterization stage and everything after that, not just pixel shading.
Also, It would be great to know more data about your experiment. I guess you were drawing a big circle, thus the small difference on the left hand side of the graph, because even the fan pattern yielded good quad coverage. So I guess drawing a lot of smaller circles would make the performance of the other two approaches fall even more abruptly with respect to your method.
Am I right?
Humus
Monday, June 15, 2009
I'm not very good at taking notes from my experiments, but I used a large circle at 1024x1024 resolution IIRC. I didn't test with smaller circles, but I would say you're right as long as you're not turning vertex shader bound or triangle setup bound when using many smaller circles.
Hobgoblin
Saturday, August 8, 2009
A few years ago in a Calculus class I came across this method whilst trying to work out how I could render certain shapes, using a method of rotating around the vertices and placing a triangle vertex at points that reduced in distance (along the vertex list) gradually, so the first triangle's vertices were x of the circles vertices apart, then the next tier of triangles had vertices that were x-1 of the circles vertices apart and so on.
At the time all I thought was that it was an interesting way to fill a circle, I didn't really think about actually applying it for tessellation, so nice job in that regard as it appears to be really effective as far as fragment shading is concerned.
Wish I had thought of actually applying it.
Nice job.
fuck
Friday, March 17, 2023
niggers
fuck
Friday, March 17, 2023
niggers
K
Saturday, March 18, 2023
<script>alert("Hello there!"
;</script>
K
Saturday, March 18, 2023
<script>alert("Hello there!"
;</script>
More pages: 1 2 3
4 5
