Previous | Next --- Slide 2 of 46
Back to Lecture Thumbnails
BryceSummers

What is the storage cost of polygon soup?

doodooloo

3(V + T). Worst case is O(V^3) and best case is O(V).

BryceSummers

@doodooloo That looks good!

Another interesting (perhaps even more so!) question would be, "What is the worst case for manifold meshes?", since $\mathcal{O}(V^{3})$ seems somewhat degenerate for mesh applications.

If we were using this representation for graph theory applications, then we might want to use edge lists instead of triangle lists to avoid that prohibitive $\mathcal{O} \binom{V}{3} = \mathcal{O}(V^{3})$ and cut it down to $\mathcal{O} \binom{V}{2} = \mathcal{O}(V^{2})$

PandaX

When the triangle mesh grows to infinity: the ratio between V, E, F is equal to 1:3:2, and each face requires 3 indices to represent. So the total storage cost of triangle soup is 3(2V) = 6* V. Is this right?