The picture on the left shows how to compute the weighted average (convex combination) of a newly created vertex.
The picture on the right shows how to compute the weighted average of the new position of one of the original vertices.
Here is yet another description of Loop Subdivision.
BryceSummers
Since subdivision algorithms often depend only on a linear combination of particular input vertices it is possible to turbo charge the re-computation of a subdivision for meshes that are isomorphic to each other.
Step 1. Perform a subdivision on mesh $M_{in}$ and cache the indices of the vertices that each vertex's position depends on. Let the resulting mesh be $M_{out}$
Step 2. Given a mesh $M_{in}'$ that is isomorphic to $M_{in}$ (For instance, if it was created by merely changing the position vectors or vertices in $M_{in}$ but no connectivity information.
It is possible to update $M_{out}$ to be the subdivision of $M_{in}'$ instead of $M_{in}$ in linear time in the number of vertices with a constant factor equal to the size of the stencil.(A stencil is the region of a mesh that a given calculation depends on, in these lecture slides, whenever you see a blue triangle diagram trying to communicate an operation to you in terms of neighboring elements, that diagram is a stencil)
Step 2 can be done without the need for a specialized mesh structure, because it suffices to lookup the inputs for every vertex in the mesh in indexed order and derive the new location in terms of the locations in $M_{in}'$ We go in indexed order, because we are assuming that the vertices created in one subdivision iteration will all have higher indices than vertices present in previous iterations as would be the case if we were storing pointers to the vertices in an unbounded array.
In the awesome project here, hands are represented by meshes that are subdivided 60 frames per second via this re-computation algorithm, which is possible because the topology of the hand does not change, rather the only things that change are the locations of the vertices mapped to the user's hand.
The picture on the left shows how to compute the weighted average (convex combination) of a newly created vertex.
The picture on the right shows how to compute the weighted average of the new position of one of the original vertices.
Here is yet another description of Loop Subdivision.
Since subdivision algorithms often depend only on a linear combination of particular input vertices it is possible to turbo charge the re-computation of a subdivision for meshes that are isomorphic to each other.
Step 1. Perform a subdivision on mesh $M_{in}$ and cache the indices of the vertices that each vertex's position depends on. Let the resulting mesh be $M_{out}$
Step 2. Given a mesh $M_{in}'$ that is isomorphic to $M_{in}$ (For instance, if it was created by merely changing the position vectors or vertices in $M_{in}$ but no connectivity information.
It is possible to update $M_{out}$ to be the subdivision of $M_{in}'$ instead of $M_{in}$ in linear time in the number of vertices with a constant factor equal to the size of the stencil.(A stencil is the region of a mesh that a given calculation depends on, in these lecture slides, whenever you see a blue triangle diagram trying to communicate an operation to you in terms of neighboring elements, that diagram is a stencil)
Step 2 can be done without the need for a specialized mesh structure, because it suffices to lookup the inputs for every vertex in the mesh in indexed order and derive the new location in terms of the locations in $M_{in}'$ We go in indexed order, because we are assuming that the vertices created in one subdivision iteration will all have higher indices than vertices present in previous iterations as would be the case if we were storing pointers to the vertices in an unbounded array.
In the awesome project here, hands are represented by meshes that are subdivided 60 frames per second via this re-computation algorithm, which is possible because the topology of the hand does not change, rather the only things that change are the locations of the vertices mapped to the user's hand.
Mesh Operations are pretty cool.