Quad Mesh Simplification in Frostbite

[Music] hello i'm ashlyn listen i am a software engineer and the Frostbite team at Electronic Arts and today I'm going to show you our quadrature simplification technology so we developed the technology in collaboration with Bioware beginning in early 2012 and this is a hand war third set of lots or levels of detail which I multiply by where artists and you can see that the lots have a very regular edge flow and a good quads apology even though they're quite low detail and at the time when Bioware artists asked us to develop this tool they were all always hand authoring their lives and this is why because they kind of want this regular topology and their lives as are shown so this is what you would get if you would feed a quad mesh model into LOD technology of the

time which was triangle based so to a triangulate the mesh and would reduce geometrically a very good result but with a completely different triangle base topology so here we can see the impact of that on the Left we've got a lot generates level of detail generated with triangles sorry quads and on the right we've got the same budget but with quads triangles and you can see that the quad version has better flexing where the character is skinned and it's deforming under skinning whereas the triangulated version has some strange artifacts even in the face where the triangulation is not matching the natural flow of the body and the it needs to flex here I've drawn the edges on the model so you can see hopefully what I mean that the the court

mesh has edges in the right places using what are called rigging rules where artists are told to and to put in rings of edges in the places where the mesh is going to flex particularly where as the triangulated mesh of course just has random triangles in those areas so the flexing is kind of a bit haphazard but there's another side to this as well which is that very often like tools are not perfect and so artists have to hand off of these models or tweet from a little bit after they've been generated and when they do that the model on the left is a much better starting point because it looks like the kind of thing the artists produce themselves so let's get started the young in the talk I'm gonna be covering three different aspects and then I'll show you some results the accident aspects are requirements that Bioware gave us for the generation for character models for four core measures so the first one is kind of to handle topology they wanted thee that generated lots to

preserve this edge flow this while structured quads apology which character models did and which they're handles that lots had so you could kind of say they wanted the lots to look like hand water models which at the time was a big ask then they also wanted the ability to hand paint priorities onto the models for example and Meyer and to those priorities to indicate that certain areas should be preserved in more detail than other areas and the reason they went at this was because they suspected that as brilliant as our tool would be they would probably still have to go in and hand paint some areas to kind of keep detail when they needed it and then the third requirement was to preserve symmetry on models so very often character models are symmetric topologically in other words they have the same edge structure at the same on the left and right just murder and so they wanted to retain that so it's apology here's a sort of well authored head model with a good quad structure so

how would we go about preserving the topology and the Lots like recall that at the time as I say triangulate certification tools with triangulation based and triangle based so they first first started off by triangulating the mesh from the left and then generated Lots on the right and this is the kind of thing we would have generated look at the time back in 2012 and as I said before this is great from a geometry point of view but doesn't have the rights apology but how does that process actually work like all other tools pretty much our tool for triangle mesh and education works like collapsing edges here on the Left we're collapsing the edge and white to a vertex which is located at a collapse point written in red and in the process from these two triangles in orange so by removing by classing and h2 a vertex he gets removed in general two triangles and this is all done using something called the quadric era metric which is a thing proposed by

garland and heck bird way back when which basically tells you where to put the collapse point to best approximate the original geometry with on your vertex instead of an edge and what the cost is of doing that like a kind of cost metric was tells you how much the geometry will suffer in that area by doing so say here's how that is used to simplify measures this is kind of an animation showing a large number of edge collapses in succession and each kind of edge collapse from use two triangles and there's a basically a big priority queue which has all the available edge collapse candidates sorted by cost metrics the garland enactment cost metric so that you favor the collapses which impact the mesh least so you you removed key triangles for the cheapest impact to the mesh and that's standard practices exactly how awesome the fire worked and so we kind of knew that we needed something similar but for quad missions we read a bunch of papers and we found

this paper by daniels at all from SIGGRAPH Asia in 2009 I think called quadrilateral mesh certification promising Lee and it proposes something called poly cord collapse which is kind of edge collapse on steroids for correlations so here's an example of what that paper does we've got a quad strip here in the squad measure like a sequence of adjacent quad separated by edges and we've collapsed that quad strip down to just a sequence of edges instead so and the process we've removed all of those quads in orange and the way it's done is by collapsing edges connecting so it's like a bunch of edge collapses done in tandem atomic link so each edge collapse can be done using the world operator that operates by replacing v-0 v1 with just a few 0 and v2 or v3 with just v2 and then moving the retained vertices V 0 V 2 to the

computed collapse point locations updating all the neighboring faces calculating the interpolated and v's and normals etc etc to basically well the mesh at that point and in the process the generate faces faces like the orange ones that degenerate and where two edges are removed and Bob's your uncle simplify - but it's not quite that simple because quad strips and therefore poly courts I should say poly cords are the sets of edges so in the previous example the poly cord it's the set of all the edges between all the quad phases they're all being collapsed together so poly cords aka quads for in this case can cross each other like they are here walk across themselves masaf intersect so when that happens things are a bit more complicated because it's no longer just a simple single collapse of a single edge instead you've got four edges here that are all

coincident they're all touching and all of those touching the edges get collapsed to just the single vertex and this is something that's Daniels at all do so you can imagine that as a sort of generalized wild operator well firstly a generalized edge collapse which is able to collapse more than one edge as long as they're touching and then also it can be implemented with a generalized world operator again which worlds by replacing any occurrence of v-0 v1 v2 or v3 with just v-0 and updating all the neighboring faces again it's not that simple because single poly cords can be arbitrarily long and in particular can sneak around the mesh many times like this single poly cord shown in orange on this asteroid so Daniels at all report that poly quad collapse in their experience as nuts enough to handle meshes like that with really long poly

cords and so they introduced a what's called a quad collapse operator which is different and not reducible to edge collapse and this operates by collapsing a quad by collapse by merging two of its opposite vertices in this case V 0 and V 1 it adjust v-0 and so again you can do that with a world operator but it's not an edge collapse it's collapsing a quad to two edges but in the process it untangles the poly quad because we're previously across that's off instead it meets itself so Daniels at all reckon that by mixing and quad collapse and poly or collapse you can untangle the mesh when you need to and then go get back to doing some poly core collapses but we actually found we don't need quad collapse and I'm not quite sure why but part of the reason might be because our world operator is quite robustly implemented and we do everything with the world operator but then part of it model city because we skirt the issue by

not only limiting us ask to cannot sing sing halt poly courts we can collapse parts of polygons which means we don't actually have to collapse this entire poly chord we can just go and do part of it so yeah the other thing to say is that edge collapse is just a special case of poly called collapse where the poly cord only has one edge and the set so if you know triangle mesh like this there are no quads so there are no quad strips and instead each poly cord which is just a single edge terminates at to incident triangles so it kind of means that if you can do poly quad collapse you can do edge collapse because it's just a simple special case of it so we dutifully implements that the poly cord collapse part of daniels at all and this is the kind of result you get so it looks pretty good and that we took the apology preservation box because the edge flow of the model the sort of flow

of edges around the model looks like an office north of it approximately but the problem with it if you like is that where our hands are tied at this point because at this point we were only collapsing entire poly cords or nothing like Daniels at all and that limits what you can do because single poly course can go through completely different parts of the match from the face to the back of the head across to the year so if you want to collapse part of the back of the head it forces you to collapse the part of the ear and which you might want to retain so your ability to locally refine the metrics have different detailed levels in different areas is limited so for that reason we we started to look at collapsing parts of pi chords which we call sub paulo chords and that was also hinted to us by the second requirement which was priority painting so probably painting again is where an artist comes

in and paints part of the match saying that like that pot to be retained at the expense of other areas so here's the kind of result we we wanted to get from that these two lights are both the same budget but on the right we've painted the face like I said I showed in the previous slide and so we've magically retained more detail and not in the face but you can see that doing that forces us to change the topology because we even be perfectly had to collapse only parts of these aligning poly cords stopping at the part where the face requires more detail and in the process we introduce usually a triangle and a singular vertex so that also hinted to us that we needed to collapse sub poly chords rather than poly course here's just a little illustration of a sub poly calculus so we've got a poly chord which extends down into the face and we only want to collapse the first five edges as little edge collapses and in doing so here's the results we end up introducing a triangle and a singular vertex and but

we've the payoff for changing the topology is a B they be enough to vary the detail they're locally but that does present us with a problem because whereas there's only a limited number of poly codes in the mesh there's a very large number of potential subhadda cores there's a lot of ways to select only some of the edges and a poly cord and connects just those and so there's a number of simplifications that make that feasible one is to only consider contiguous sub poly courts are he adjacent edges and not just random edges in the PI chord and the justification for that is that you can always go and do other edges later if you want to the next is that we don't do a sort of exhaustive search of every possible contiguous of polygons instead we do a greedy search where we first find a short sequence in this case three edges that is the cheapest part of the poly corner using a linear search and then we then incrementally improve

that by adding or removing an edge at either end as long as that improves the value of the results which is there a ratio of the benefits for the number of triangles removed by that collapse to the cost which is just the sum of the costs of the edge collapses and so we hope that that all sort of he'll climb to a good solution but we also as a safe cloud always also consider the solution of just collapsing the entire poly cord because quite often that's the right answer and you might not reach that the whole planning another thing we do to speed things up is we maintain a data structure which represents the partitioning of the sub poly cord edges into islands of connected edges because recall each island of connected edges collapses to a vertex in a sort of generalized multi-edge collapse so typically we when we're doing this search for the best sub poly cord we end up testing successive south poly cords

that differ by only one edge either added or removed so it makes a lot of sense to remember a lot of the information that you computed for the previous type poly cord which was only different by one edge so that's what we're doing here and then we add an edge we have to update that data structure but very often the new edge is not touching any existing edges creates a new single reg Wyland so that the common case is pretty cheap and then occasionally an edge comes in which has the effect of merging two items or something like that because it's incident to two of the edges already in there so that that update is more complicated but it's still worth doing because its own avoids of repeating a lot of calculations from one sub like probably called candidate to the next so here's just a quick example of that in the wild so on the Left we've got a sub poly cord in orange that we've been bowling with all its edges that we've selected in white and we're going to select this

edge here and test that candidate and when we do it's that edge is incident to existing - to existing edges to existing islands so they get merged into a single island of three edges and the way you can tell that that's happened is because there's a single collapse point computed for all three edges whereas previously these two edges had separate class points another thing we do is whenever we collapse the Paula chord we have to update all the candidates for the paula chords whose geometry or topology is affected by that welding of the mesh so there's kind of a neighborhood of poly cords that are no longer invalid because their cost would have changed and so we have to remove them from the priority queue and recompute their costs in riyadh them and we do that incrementally because you the area that we have to update it is smaller than that and all of the mesh in bad cases it can be quite expensive like this is approaching like a third of the mesh because the mesh is

very regular so the poly cords are quite long but some usually it's a lot cheaper than that so here's a result when we have sub quad core collapse and you can see it's an improvement over the previous was last we had and that's now we're able to choose to alter the topology of a mesh locally in order to keep detail at a reasonable level and so very the detail across that mesh depending where we wanted and in particular this gives us the ability to do priority painting but an issue with this results actually while we're here is that it's not symmetric you can see that the left and right sides of the faces are different in topology and that kind of leads into the third requirement which is that Bioware wanted us to keep the symmetry of symmetric measures intact and that's nice more feet because a lot of measures character measures are come for any partly symmetric like this one is symmetric in some areas but not

others and we also made life a little more difficult for us also we may be needed to and that we want to priority painting to be independent and orthogonal to use symmetry so you could choose to paint any half the face and have that part preserved even though that conflicts that the desire to preserve symmetry so in that sense our symmetry preservation is kind of soft in the Reed we don't mandate that you always have to do exactly the same on the left and the right and said we have a cross metric term which strongly favors collapses that treat that collapse both of the silhouette as if they are symmetric or don the collapsing so that's useful in that it alot buys us a lot of flexibility but it also ties into the fact that measures are not usually completely symmetric so a method which mandated doing exactly the same to the left and the right would not be feasible actually so the softer practicing the right way to go but it does context afire things of it so we

developed an algorithm for automatically identifying bilateral symmetry and measures and I won't go into the details but basically it does a search of the graph of the edges in the mesh looking for parts of the graph that are matching it topologically and so it's able to find symmetries within that are only partly symmetric and it's also able to find symmetries between different parts of the mesh so in this example it's the common case we find entire Polly core such exactly match but as I'm trying to show here this is actually more complicated than it seems because the actual symmetry map that we find it is per edge so we find that an individual edge is symmetric to another individual edge and in the case where entire Polly chords are thought to be symmetric that's because there's a one-to-one symmetry relationship between their edges but we don't actually find that poly-cotton solves a symmetric rather it's all about edges as in the slide we also found that it's important to handle symmetric pairs of polly

chords atomically so rather than that I can ask the left one chord and then the right chord immediately afterwards it's actually necessary to collapse both of them together as one generalized set of edges and the reason for that is because you in the case of the where they incident like this you only get to know about the whole information of that collapse if you have both Polly chords available so given the fact that most of the time we've expect to find pairs of Polly chords that are kind of exactly symmetric we needed a method to handle that and to find the best pair of sub Polly chords to collapse as a class candidate for that pair of Polly chords so we just generalized our previous algorithm which was for a single particle by just doing the obvious thing and having a finding first a pair of C pi chords C sub pi chords of a fixed length the cheapest area in each of the

polly chords and then growing those sub pi chords incrementally in the same way by adding or removing an added either and we can do that to both poly cords or just the one whichever produces the best value and then again we also consider the solution of just collapsing the entire pair because that's often a good idea but this rosy picture of exactly matching paired poly cords isn't quite true as I say because because we are dealing with meshes which are partially symmetric and because our symmetry therefore has to be per edge not per poly cord you can get situations arising particularly after a few classes where the edges the edge symmetries effectively make multiple poly courts related to each other rather than just pairs and in this case for example there are poly cords and the obvious left and right but there are other particles involved would become kind of entangled

with them by other collapses and so in general you can have what we call flux of poly cords where they're all any number of poly quads can be related by these per edge symmetry links so in this case you've got a poly cord on the left which is related to two other poly cords on the right and you can imagine that actually those two other poly poly cords may have been one PI cord but something else has happened some part of it that pi cord has been collapsed so that now there are three poly quads involved and we needed a way to handle this so the way we handle this is by finding the parts of the poly cords which are most symmetric and from that reducing finding pairs of poly cords in the flock which are nice symmetric because we we shouldn't forget that we're kind of expecting the mesh to be basically bilaterally symmetric if it is symmetric and so we expect to find matching left and right pairs or an approximation to

that so rather than coming up with an algorithm to find the best arbitrary way to collapse any set of edges from a flock of poly cords which would be very expensive instead we go and look for these pairs and we then do the pairwise seed supply cord greedy evaluation thing to each of those pairs and then we also consider each probably quadrat the flock individually using the non paired version of that algorithm so we're effectively hedging our bets and imagining that the mesh might not might be either not symmetric in which case we're going to have single PI cores or symmetric in which case we're going to find the good pairs so when we've got all of that in place we now have achieved all three of the requirements and in particular we can preserve topology we can also support priority painting by varying a topology when we

need to to likely adapt detail levels and we can preserve symmetry or kind of at the same time with soft sliders that choose how much topology is important how much symmetry is important and how much priority painting is important and the number of other things as well like we also have metrics and cost terms that try to preserve detail where it's needed for skinning and where it's needed for sort of wet preservation and things like that so lastly I'm just gonna rush through some results quickly so here we're comparing results from our tool at the top row is a result from the hottest the bottom row as they result from the artist authored Watterson authored models and the bottom row and you can see we do metrically look very similar to the artists models where they do deference that the artist has done things that we don't know about for example making the hands into mittens rather than keeping the fingers here we're comparing lot three the tool on the left and the artist or the model on the right and the idea here is you

can kind of see ignoring things like the mitten fingers but we match pretty well and we imagine looks quite a lot like it was authored by an artist which is the idea here we're doing a kind of switch test where we vary the distance to the lights and change between the lights according to the distance and what we're looking for is popping where we switch between the different lights and you can see the difference between them when they change so you'll notice that the artist or third model which is on the right pops more than the one on the Left which is generated with a tool and I think that's because the artist wasn't more effectively is not just a pedestal version of the original model but rather is remodeled slightly so you can see slight differences here's another dragon age model and again we're comparing the tool the result at the top with your artist author models at the bottom and you can see we're pretty similar here's a

classic of log three again and again pretty similar the big difference is that the artist has kind of done some broad simplifications of these silhouettes the big shapes at the top the other aspect is that the artist has retained detail in the tail which is needed because the tail and flexors when me and the Beast walks and we haven't done that we do have a costume to try and do that but we'd have to crank it up to you to get that kind of result this is just checking symmetry so the ability to preserve symmetry where the mesh is symmetric and you can see where we're getting the right sort of result it's just the same thing for the gun and then finally I thought I'd show you in Long character model because we ended up using this tool not just for characters and not just the quad measures but also for triangle based models and props and vehicles etc

through RTA and pretty much every studio and yeah uses this tool for all kinds of models and here we're comparing the tool results at the top with a competitor called simplygon a third-party tool called simply garden at the bottom and you can see for the same budgets we're producing pretty favorable results I think here I'm comparing simply gone on the left with the tool in the middle and an artist results artist source of mesh on the right and you can see that we kind of met the artist in the sense that we have a quad based understanding of the model which has allowed us to retain the broad features a lot be distracted by edges that are just there because of triangulation and I think that's what's allowing us to release this cleaner result yeah thanks for watching that's all for me and I hope you enjoy the talk just