On Tue, 5 Jun 2012 13:06:08 +0200 Antonio Ospite <[email protected]> wrote:
> On Tue, 5 Jun 2012 12:54:12 +0200 > Campbell Barton <[email protected]> wrote: > > > On Fri, Jun 1, 2012 at 3:06 PM, Antonio Ospite <[email protected]> > > wrote: > [...] > > > > > > On Wed, 15 Feb 2012 23:37:09 +0100 > > > Antonio Ospite <[email protected]> wrote: > > > > [...] > > >> I could use something like: > > >> scene.objects.sort(key=some key based on objects properties) > > >> mesh.faces.sort(key=some key [face index?] based on faces and vertices > > >> properties) > > > > > > This would be handy for my use case, maybe it is a bit of a stretch to > > > use modeling structures for rendering operations, so I will accept a > > > "you're doing it wrong" type of comments here :) > [...] > > > > > > This question boils down to: is the ability to sort faces arbitrarily > > > (or other elements) something modeling tools can make use of? > > > > replying on a single issue if face sorting, while you cant ensure > > order when adding faces - which may be added at any index. > > there is support for sorting: see > > BM_mesh_remap > > > > I'll take a look, thanks. > > > adding support for something like this isnt so hard: > > faces.sort(key=lambda f: f.calc_area()) > > > > I'll try to add this and will send a patch if I succeed. I've got an experimental patch for BMElemSeq.sort() but I have a doubt, when I iterate on the bmesh elements after sorting them I don't get the elements in the order of their indices, look at the attached BMElemSeq_sort.log file. I am attaching the test script too, see BMElemSeq_sort_test.py. And I am inlining the patch so you can comment it where needed like quoting a regular email, it is just a prototype, and it does not follow the blender style either, but it should illustrate the idea I have in mind for the implementation. With this patch VRM can implement the simple painter algorithm for the visibility problem, with just a call to: mesh.faces.sort(key=lambda f: max([v.co[2] for v in f.verts])) (just sorting on 'z' is enough because I do that in Normalized View Coordinates) Thanks, Antonio diff --git a/CMakeLists.txt b/CMakeLists.txt index 191fb61..8f591ed 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -1428,8 +1428,8 @@ elseif(APPLE) set(EXETYPE MACOSX_BUNDLE) - set(CMAKE_C_FLAGS_DEBUG "-fno-strict-aliasing -g") - set(CMAKE_CXX_FLAGS_DEBUG "-fno-strict-aliasing -g") + set(CMAKE_C_FLAGS_DEBUG "-fno-strict-aliasing -ggdb") + set(CMAKE_CXX_FLAGS_DEBUG "-fno-strict-aliasing -ggdb") if(CMAKE_OSX_ARCHITECTURES MATCHES "i386") set(CMAKE_CXX_FLAGS_RELEASE "-O2 -mdynamic-no-pic -ftree-vectorize -msse -msse2 -fvariable-expansion-in-unroller") set(CMAKE_C_FLAGS_RELEASE "-O2 -mdynamic-no-pic -ftree-vectorize -msse -msse2 -fvariable-expansion-in-unroller") diff --git a/source/blender/python/bmesh/bmesh_py_types.c b/source/blender/python/bmesh/bmesh_py_types.c index 053dac7..5ed67bc 100644 --- a/source/blender/python/bmesh/bmesh_py_types.c +++ b/source/blender/python/bmesh/bmesh_py_types.c @@ -2083,6 +2083,200 @@ static PyObject *bpy_bmelemseq_index_update(BPy_BMElemSeq *self) Py_RETURN_NONE; } +PyDoc_STRVAR(bpy_bmelemseq_sort_doc, +".. method:: sort(key=None, reverse=False)\n" +"\n" +" Sort the elements of this sequence.\n" +"\n" +" :arg key: Sequence of verts.\n" +" :type key: :function: returning a number\n" +" :arg reverse: Reverse the order of the elements\n" +" :type reverse: :boolean:\n" +"\n" +" .. code-block:: python\n" +"\n" +" mesh.faces.sort(key=lambda f: f.calc_area())\n" +"\n" +); +static PyObject *bpy_bmelemseq_sort(BPy_BMElemSeq *self, PyObject *args, PyObject *kw) +{ + PyObject *keyfunc = NULL; /* optional */ + int reverse = FALSE; /* optional */ + static const char *kwlist[] = {"key", "reverse", NULL}; + int n_elem = 0; + + BMIter iter; + BMElem *ele; + PyObject *py_elem = Py_None; + PyObject *index = NULL; + + const char htype = bm_iter_itype_htype_map[self->itype]; + + double *keys = NULL; + int *elem_idx = NULL; + int *elem_map_idx = NULL; + + int *vert_idx = NULL; + int *edge_idx = NULL; + int *face_idx = NULL; + int i; + int j; + + BMesh *bm = self->bm; + + BPY_BM_CHECK_OBJ(self); + if (args != NULL) { + if(!PyArg_ParseTupleAndKeywords(args, kw, + "|Oi:BMElemSeq.sort", + (char **)kwlist, + &keyfunc, &reverse)) + return NULL; + } + fprintf(stderr, "%s: key: %p\n", __func__, keyfunc); + fprintf(stderr, "%s: reverse: %d\n", __func__, reverse); + + n_elem = BM_mesh_elem_count(bm, htype); + fprintf(stderr, "%s: sequence size: %d\n", __func__, n_elem); + + keys = malloc(sizeof(*keys) * n_elem); + if (keys == NULL) + return NULL; + + elem_idx = malloc(sizeof(*elem_idx) * n_elem); + if (elem_idx == NULL) + goto out_free_keys; + + elem_map_idx = malloc(sizeof(*elem_map_idx) * n_elem); + if (elem_map_idx == NULL) + goto out_free_elem_idx; + + i = 0; + BM_ITER_BPY_BM_SEQ (ele, &iter, self) { + if (keyfunc != NULL) { + py_elem = BPy_BMElem_CreatePyObject(self->bm, (BMHeader *)ele); + if (py_elem == Py_None) { + fprintf(stderr, "%s: failed to create a python element!\n", __func__); + goto out; + } + index = PyObject_CallFunctionObjArgs(keyfunc, py_elem, NULL); + /* Check that the result is a number? */ + + keys[i] = PyFloat_AsDouble(index); + } else { + keys[i] = (double)i; + } + + i++; + } + + fprintf(stderr, "%s: original keys\n", __func__); + for (i = 0; i < n_elem; i++) { + fprintf(stderr, "%s: key: %g\n", __func__, keys[i]); + } + fprintf(stderr, "\n"); + + /* initialize the index array */ + for (i = 0; i < n_elem; i++) + elem_idx[i] = i; + + fprintf(stderr, "%s: elem_idx\n", __func__); + for (i = 0; i < n_elem; i++) { + fprintf(stderr, "%s: elem idx: %d\n", __func__, elem_idx[i]); + } + fprintf(stderr, "\n"); + + /* sort the index array according to the order of the 'keys' array */ + for (i = 0; i < n_elem - 1; i++) { + for(j = 0; j < n_elem - i - 1; j++) { + if (reverse == 0) { + if (keys[elem_idx[j]] > keys[elem_idx[j+1]]) { + int tmp; + tmp = elem_idx[j]; + elem_idx[j] = elem_idx[j+1]; + elem_idx[j+1] = tmp; + } + } else { + if (keys[elem_idx[j]] < keys[elem_idx[j+1]]) { + int tmp; + tmp = elem_idx[j]; + elem_idx[j] = elem_idx[j+1]; + elem_idx[j+1] = tmp; + } + } + } + } + + fprintf(stderr, "%s: elem_idx sorted\n", __func__); + for (i = 0; i < n_elem; i++) { + fprintf(stderr, "%s: elem idx: %d\n", __func__, elem_idx[i]); + } + fprintf(stderr, "\n"); + + fprintf(stderr, "%s: sorted keys\n", __func__); + for (i=0; i < n_elem; i++) { + fprintf(stderr, "%s: key: %g\n", __func__, keys[elem_idx[i]]); + } + fprintf(stderr, "\n"); + + /* print the mapping, just for debug */ + fprintf(stderr, "%s: mapping of elem_idx\n", __func__); + for (i = 0; i < n_elem; i++) { + fprintf(stderr, "%s: new_index <- orig_index: %-3d <- %3d\n", + __func__, i, elem_idx[i]); + } + fprintf(stderr, "\n"); + + /* initialize the map array + * + * whe need to know the index such that + * if used as the new_index in BM_mesh_remap() will give the + * order of the sorted keys like in elem_idx */ + for (i = 0; i < n_elem; i++) { + elem_map_idx[elem_idx[i]] = i; + } + + fprintf(stderr, "%s: elem_map_idx\n", __func__); + for (i = 0; i < n_elem; i++) { + fprintf(stderr, "%s: map idx: %d\n", __func__, elem_map_idx[i]); + } + fprintf(stderr, "\n"); + + + switch ((BMIterType)self->itype) { + case BM_VERTS_OF_MESH: + vert_idx = elem_map_idx; + break; + case BM_EDGES_OF_MESH: + edge_idx = elem_map_idx; + break; + case BM_FACES_OF_MESH: + face_idx = elem_map_idx; + break; + default: + fprintf(stderr, "%s: element type not supported (%d)!\n", + __func__, self->itype); + goto out; + } + + fprintf(stderr, "%s: Calling BM_mesh_remap (verts:%p, edges:%p, faces:%p)!\n", + __func__, vert_idx, edge_idx, face_idx); + + BM_mesh_remap(bm, vert_idx, edge_idx, face_idx); + BM_mesh_elem_index_ensure(bm, htype); + + fprintf(stderr, "%s: REMAPPING done!\n\n", __func__); + +out: + free(elem_map_idx); + +out_free_elem_idx: + free(elem_idx); + +out_free_keys: + free(keys); + + Py_RETURN_NONE; +} static struct PyMethodDef bpy_bmesh_methods[] = { /* utility */ @@ -2166,6 +2360,7 @@ static struct PyMethodDef bpy_bmloop_methods[] = { static struct PyMethodDef bpy_bmelemseq_methods[] = { /* odd function, initializes index values */ {"index_update", (PyCFunction)bpy_bmelemseq_index_update, METH_NOARGS, bpy_bmelemseq_index_update_doc}, + {"sort", (PyCFunction)bpy_bmelemseq_sort, METH_VARARGS | METH_KEYWORDS, bpy_bmelemseq_sort_doc}, {NULL, NULL, 0, NULL} }; @@ -2175,6 +2370,7 @@ static struct PyMethodDef bpy_bmvertseq_methods[] = { /* odd function, initializes index values */ {"index_update", (PyCFunction)bpy_bmelemseq_index_update, METH_NOARGS, bpy_bmelemseq_index_update_doc}, + {"sort", (PyCFunction)bpy_bmelemseq_sort, METH_VARARGS | METH_KEYWORDS, bpy_bmelemseq_sort_doc}, {NULL, NULL, 0, NULL} }; @@ -2186,6 +2382,7 @@ static struct PyMethodDef bpy_bmedgeseq_methods[] = { /* odd function, initializes index values */ {"index_update", (PyCFunction)bpy_bmelemseq_index_update, METH_NOARGS, bpy_bmelemseq_index_update_doc}, + {"sort", (PyCFunction)bpy_bmelemseq_sort, METH_VARARGS | METH_KEYWORDS, bpy_bmelemseq_sort_doc}, {NULL, NULL, 0, NULL} }; @@ -2197,12 +2394,14 @@ static struct PyMethodDef bpy_bmfaceseq_methods[] = { /* odd function, initializes index values */ {"index_update", (PyCFunction)bpy_bmelemseq_index_update, METH_NOARGS, bpy_bmelemseq_index_update_doc}, + {"sort", (PyCFunction)bpy_bmelemseq_sort, METH_VARARGS | METH_KEYWORDS, bpy_bmelemseq_sort_doc}, {NULL, NULL, 0, NULL} }; static struct PyMethodDef bpy_bmloopseq_methods[] = { /* odd function, initializes index values */ /* no: index_update() function since we cant iterate over loops */ + /* no: sort() function since we cant iterate over loops */ {NULL, NULL, 0, NULL} }; -- Antonio Ospite http://ao2.it A: Because it messes up the order in which people normally read text. See http://en.wikipedia.org/wiki/Posting_style Q: Why is top-posting such a bad thing?
BMElemSeq_sort.log
Description: Binary data
#!/usr/bin/env python
import bpy
import bmesh
def print_elems(elems, key=None):
print()
for e in elems:
print(e.index, key(e) if key else "")
print()
def print_elems_by_index(elems, key=None, reverse=False):
print()
sorted_elems = sorted(elems, key=lambda e: e.index, reverse=reverse)
for e in sorted_elems:
print(e.index, key(e) if key else "")
print()
cube = bpy.data .objects['Cube']
mesh = bmesh.new()
mesh.from_mesh(cube.data)
print(mesh)
print("\n\n")
print("A test on faces, sort according to face area")
print_elems(mesh.faces, key=lambda f: f.calc_area())
mesh.faces.sort(key=lambda f: f.calc_area())
print("When iterating over the sorted elements we don't get the new natural order")
print_elems(mesh.faces, key=lambda f: f.calc_area())
print("But if we sort by index then the order is right...")
print_elems_by_index(mesh.faces, key=lambda f: f.calc_area())
print("\n\n")
print("A test on vertices, sort according to x coordinate")
print_elems(mesh.verts, key=lambda v: v.co[0])
mesh.verts.sort(key=lambda v: v.co[0])
print("When iterating over the sorted elements we don't get the new natural order")
print_elems(mesh.verts, key=lambda v: v.co[0])
print("But if we sort by index then the order is right...")
print_elems_by_index(mesh.verts, key=lambda v: v.co[0])
mesh.to_mesh(cube.data)
mesh.free()
print("After exporting to mesh again the elements are properly sorted tho")
print_elems(cube.data.vertices, key=lambda v: v.co[0])
_______________________________________________ Bf-python mailing list [email protected] http://lists.blender.org/mailman/listinfo/bf-python
