Open m-7761 opened 4 years ago
Update: I did some work adding connectivity information to triangles using pointers. I think pointers are probably the way to go here, and even using std::vector
for the vertex/triangle containers is probably not best. To use vector you'd want to basically use recycling vectors instead and mark elements as deleted.
The way I think I prefer is to use std::unordered_set
and so enumeration is limited to for-each style unless you're willing to walk the set. That removes the need to do memmove like operations in addition to updating indices. These are currently done one-by-one which is why performance is so bad.
Switching to pointers/unordered_set can keep the one-by-one behavior without having to rewrite the Undo system to try to batch changes (which is hard because it works one one undo type at a time, and changes tend to be mixed and undo operations often have their own heterogeneous operations that don't "combine" which perhaps is a problem in its own right.)
My intuition is unordered_set over marking deleted. I think that design will prove better and avoid not-deleted checks everywhere that enumerates the sets directly.
This will require a completely new API. I recommend trying to instead think of Model more like a STL container in a new API than a C style procedural API. The old API can be retained (somehow) for file read/write where its defensive style makes more sense. A lot of the internal methods should be farmed out to ModelUndo or prefixed with _
so they're invisible.
FYI to make MM3D scalable (edit midsize models) the data model must change. I haven't scoured the code, but in the code that is used by undo/redo to add/remove vertices the vertex/triangle arrays are treated as if they are linked-lists, so at some point they must have been so. I assume they used pointer indices at that stage.
In any case, reflecting on this made me to realize the best strategy has to be to get rid of the idea of indices that require bumping all elements/indices after a given element is inserted/removed. To that end what makes sense is to never really remove elements, but just to mark them deleted and add them to a recycling list that is local to the model.
My intuition is it would be best to use pointers instead of indices internally, but to also maintain the convenience APIs that use
int
indices. Except that the indices would be lifetime indices, and so cannot be assumed to be less than there are extant elements. In other words, it would be in error to create an index that is size of number of extant elements and proceed to index into it with theseint
indices.I think the interface should be simplified at the same time to look more like C++ and try to remove as many methods as possible. So that you can get a reference to the vertex container and its size can tell you the real number of vertices, live and dead.
It might be useful to assign the
int
indices through anunordered_map
so they can be used to specify how elements are ordered. Some of the tools/commands behave differently depending on the order, and there are legit reasons to reorder a model's elements. It adds some overhead, but I think that it's a good idea, and gives those indices an actual utility.EDITED: I really don't know about ordering. Those tools/commands really don't care about the order other than the fact that the selection list is in the same order as the elements. If you could specify the order of the selections that would work also, but that seems to me too cumbersome. Often elements are created in the order you want... but that might change if the indices are assigned randomly as a side-effect of a recycling regime. The indices could be decoupled I suppose, and occasionally compacted so not to exceed INT_MAX.
The basic idea is undo/redo must be efficient. Adding/removing should not be a huge/absurd job for the CPU. I think level 2 could be to treat the drawing data like how the surface-normal data is treated, that is to mark it invalid, and then rebuild a drawing buffer on demand, as the normals are. That buffer can then be reused by additional viewports, and between frames where not invalidated.