diff options
author | Campbell Barton <ideasman42@gmail.com> | 2012-02-19 22:31:04 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2012-02-19 22:31:04 +0400 |
commit | afc56a0b10b52d2c8bdfd44257624d776db72f79 (patch) | |
tree | 25d194e29b2708ac1143b3dde6dfbeec7ef1d876 /source/blender/bmesh/operators/bmo_join_triangles.c | |
parent | d6deca4e9d6bc7faff98644286571c7934324a9d (diff) |
copying bmesh dir on its own from bmesh branch
Diffstat (limited to 'source/blender/bmesh/operators/bmo_join_triangles.c')
-rw-r--r-- | source/blender/bmesh/operators/bmo_join_triangles.c | 373 |
1 files changed, 373 insertions, 0 deletions
diff --git a/source/blender/bmesh/operators/bmo_join_triangles.c b/source/blender/bmesh/operators/bmo_join_triangles.c new file mode 100644 index 00000000000..921c579447b --- /dev/null +++ b/source/blender/bmesh/operators/bmo_join_triangles.c @@ -0,0 +1,373 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * Contributor(s): Joseph Eagar. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#include "MEM_guardedalloc.h" + +#include "DNA_meshdata_types.h" + +#include "BKE_customdata.h" + +#include "BLI_math.h" +#include "BLI_array.h" + +#include "bmesh.h" + +#include "bmesh_operators_private.h" /* own include */ + +/* + * JOIN_TRIANGLES.C + * + * utility bmesh operators, e.g. transform, + * translate, rotate, scale, etc. + * + */ + +/* Bitflags for edges */ +#define T2QDELETE 1 +#define T2QCOMPLEX 2 +#define T2QJOIN 4 + +/* assumes edges are validated before reaching this poin */ +static float measure_facepair(BMesh *UNUSED(bm), BMVert *v1, BMVert *v2, + BMVert *v3, BMVert *v4, float limit) +{ + /* gives a 'weight' to a pair of triangles that join an edge to decide how good a join they would mak */ + /* Note: this is more complicated than it needs to be and should be cleaned up.. */ + float n1[3], n2[3], measure = 0.0f, angle1, angle2, diff; + float edgeVec1[3], edgeVec2[3], edgeVec3[3], edgeVec4[3]; + float minarea, maxarea, areaA, areaB; + + /* First Test: Normal differenc */ + normal_tri_v3(n1, v1->co, v2->co, v3->co); + normal_tri_v3(n2, v1->co, v3->co, v4->co); + + if (n1[0] == n2[0] && n1[1] == n2[1] && n1[2] == n2[2]) angle1 = 0.0f; + else angle1 = angle_v3v3(n1, n2); + + normal_tri_v3(n1, v2->co, v3->co, v4->co); + normal_tri_v3(n2, v4->co, v1->co, v2->co); + + if (n1[0] == n2[0] && n1[1] == n2[1] && n1[2] == n2[2]) angle2 = 0.0f; + else angle2 = angle_v3v3(n1, n2); + + measure += (angle1 + angle2) * 0.5f; + if (measure > limit) { + return measure; + } + + /* Second test: Colinearit */ + sub_v3_v3v3(edgeVec1, v1->co, v2->co); + sub_v3_v3v3(edgeVec2, v2->co, v3->co); + sub_v3_v3v3(edgeVec3, v3->co, v4->co); + sub_v3_v3v3(edgeVec4, v4->co, v1->co); + + /* a completely skinny face is 'pi' after halving */ + diff = 0.25f * (fabsf(angle_v3v3(edgeVec1, edgeVec2) - (float)M_PI_2) + + fabsf(angle_v3v3(edgeVec2, edgeVec3) - (float)M_PI_2) + + fabsf(angle_v3v3(edgeVec3, edgeVec4) - (float)M_PI_2) + + fabsf(angle_v3v3(edgeVec4, edgeVec1) - (float)M_PI_2)); + + if (!diff) { + return 0.0; + } + + measure += diff; + if (measure > limit) { + return measure; + } + + /* Third test: Concavit */ + areaA = area_tri_v3(v1->co, v2->co, v3->co) + area_tri_v3(v1->co, v3->co, v4->co); + areaB = area_tri_v3(v2->co, v3->co, v4->co) + area_tri_v3(v4->co, v1->co, v2->co); + + if (areaA <= areaB) minarea = areaA; + else minarea = areaB; + + if (areaA >= areaB) maxarea = areaA; + else maxarea = areaB; + + if (!maxarea) measure += 1; + else measure += (1 - (minarea / maxarea)); + + return measure; +} + +#define T2QUV_LIMIT 0.005f +#define T2QCOL_LIMIT 3 + +static int compareFaceAttribs(BMesh *bm, BMEdge *e, int douvs, int dovcols) +{ + MTexPoly *tp1, *tp2; + MLoopCol *lcol1, *lcol2, *lcol3, *lcol4; + MLoopUV *luv1, *luv2, *luv3, *luv4; + BMLoop *l1, *l2, *l3, *l4; + int mergeok_uvs = !douvs, mergeok_vcols = !dovcols; + + l1 = e->l; + l3 = e->l->radial_next; + + /* match up loops on each side of an edge corrusponding to each ver */ + if (l1->v == l3->v) { + l2 = l1->next; + l4 = l2->next; + } + else { + l2 = l1->next; + + l4 = l3; + l3 = l4->next; + } + + lcol1 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPCOL); + lcol2 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPCOL); + lcol3 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPCOL); + lcol4 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPCOL); + + luv1 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPUV); + luv2 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPUV); + luv3 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPUV); + luv4 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPUV); + + tp1 = CustomData_bmesh_get(&bm->pdata, l1->f->head.data, CD_MTEXPOLY); + tp2 = CustomData_bmesh_get(&bm->pdata, l2->f->head.data, CD_MTEXPOLY); + + if (!lcol1) + mergeok_vcols = 1; + + if (!luv1) + mergeok_uvs = 1; + + /* compare faceedges for each face attribute. Additional per face attributes can be added late */ + + /* do VCOL */ + if (lcol1 && dovcols) { + char *cols[4] = {(char *)lcol1, (char *)lcol2, (char *)lcol3, (char *)lcol4}; + int i; + + for (i = 0; i < 3; i++) { + if (cols[0][i] + T2QCOL_LIMIT < cols[2][i] - T2QCOL_LIMIT) + break; + if (cols[1][i] + T2QCOL_LIMIT < cols[3][i] - T2QCOL_LIMIT) + break; + } + + if (i == 3) + mergeok_vcols = 1; + } + + /* do UV */ + if (luv1 && douvs) { + if (tp1->tpage != tp2->tpage); /* do nothin */ + else { + int i; + + for (i = 0; i < 2; i++) { + if (luv1->uv[0] + T2QUV_LIMIT > luv3->uv[0] && luv1->uv[0] - T2QUV_LIMIT < luv3->uv[0] && + luv1->uv[1] + T2QUV_LIMIT > luv3->uv[1] && luv1->uv[1] - T2QUV_LIMIT < luv3->uv[1]) + { + if (luv2->uv[0] + T2QUV_LIMIT > luv4->uv[0] && luv2->uv[0] - T2QUV_LIMIT < luv4->uv[0] && + luv2->uv[1] + T2QUV_LIMIT > luv4->uv[1] && luv2->uv[1] - T2QUV_LIMIT < luv4->uv[1]) + { + mergeok_uvs = 1; + } + } + } + } + } + + if (douvs == mergeok_uvs && dovcols == mergeok_vcols) { + return TRUE; + } + + return FALSE; +} + +typedef struct JoinEdge { + float weight; + BMEdge *e; +} JoinEdge; + +#define EDGE_MARK 1 +#define EDGE_CHOSEN 2 + +#define FACE_MARK 1 +#define FACE_INPUT 2 + +static int fplcmp(const void *v1, const void *v2) +{ + const JoinEdge *e1 = (JoinEdge *)v1, *e2 = (JoinEdge *)v2; + + if (e1->weight > e2->weight) return 1; + else if (e1->weight < e2->weight) return -1; + + return 0; +} + +void bmesh_jointriangles_exec(BMesh *bm, BMOperator *op) +{ + BMIter iter, liter; + BMOIter siter; + BMFace *f1, *f2; + BMLoop *l; + BMEdge *e; + BLI_array_declare(jedges); + JoinEdge *jedges = NULL; + int dosharp = BMO_slot_int_get(op, "compare_sharp"), douvs = BMO_slot_int_get(op, "compare_uvs"); + int dovcols = BMO_slot_int_get(op, "compare_vcols"), domat = BMO_slot_int_get(op, "compare_materials"); + float limit = BMO_slot_float_get(op, "limit"); + int i, totedge; + + /* flag all edges of all input face */ + BMO_ITER(f1, &siter, bm, op, "faces", BM_FACE) { + BMO_elem_flag_enable(bm, f1, FACE_INPUT); + BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f1) { + BMO_elem_flag_enable(bm, l->e, EDGE_MARK); + } + } + + /* unflag edges that are invalid; e.g. aren't surrounded by triangle */ + BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) { + if (!BMO_elem_flag_test(bm, e, EDGE_MARK)) + continue; + + if (BM_edge_face_count(e) != 2) { + BMO_elem_flag_disable(bm, e, EDGE_MARK); + continue; + } + + f1 = e->l->f; + f2 = e->l->radial_next->f; + + if (f1->len != 3 || f2->len != 3) { + BMO_elem_flag_disable(bm, e, EDGE_MARK); + continue; + } + + if (!BMO_elem_flag_test(bm, f1, FACE_INPUT) || !BMO_elem_flag_test(bm, f2, FACE_INPUT)) { + BMO_elem_flag_disable(bm, e, EDGE_MARK); + continue; + } + } + + i = 0; + BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) { + BMVert *v1, *v2, *v3, *v4; + BMFace *f1, *f2; + float measure; + + if (!BMO_elem_flag_test(bm, e, EDGE_MARK)) + continue; + + f1 = e->l->f; + f2 = e->l->radial_next->f; + + v1 = e->l->v; + v2 = e->l->prev->v; + v3 = e->l->next->v; + v4 = e->l->radial_next->prev->v; + + if (dosharp && !BM_elem_flag_test(e, BM_ELEM_SMOOTH)) + continue; + + if ((douvs || dovcols) && compareFaceAttribs(bm, e, douvs, dovcols)) + continue; + + if (domat && f1->mat_nr != f2->mat_nr) + continue; + + measure = measure_facepair(bm, v1, v2, v3, v4, limit); + if (measure < limit) { + BLI_array_growone(jedges); + + jedges[i].e = e; + jedges[i].weight = measure; + + i++; + } + } + + if (!jedges) + return; + + qsort(jedges, BLI_array_count(jedges), sizeof(JoinEdge), fplcmp); + + totedge = BLI_array_count(jedges); + for (i = 0; i < totedge; i++) { + BMFace *f1, *f2; + + e = jedges[i].e; + f1 = e->l->f; + f2 = e->l->radial_next->f; + + if (BMO_elem_flag_test(bm, f1, FACE_MARK) || BMO_elem_flag_test(bm, f2, FACE_MARK)) + continue; + + BMO_elem_flag_enable(bm, f1, FACE_MARK); + BMO_elem_flag_enable(bm, f2, FACE_MARK); + BMO_elem_flag_enable(bm, e, EDGE_CHOSEN); + } + + BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) { + if (!BMO_elem_flag_test(bm, e, EDGE_CHOSEN)) + continue; + + f1 = e->l->f; + f2 = e->l->radial_next->f; + + BM_faces_join_pair(bm, f1, f2, e); + } + + BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) { + if (BMO_elem_flag_test(bm, e, EDGE_MARK)) { + /* ok, this edge wasn't merged, check if it's + * in a 2-tri-pair island, and if so merg */ + + f1 = e->l->f; + f2 = e->l->radial_next->f; + + if (f1->len != 3 || f2->len != 3) + continue; + + for (i = 0; i < 2; i++) { + BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, i ? f2 : f1) { + if (l->e != e && BMO_elem_flag_test(bm, l->e, EDGE_MARK)) { + break; + } + } + + /* if l isn't NULL, we broke out of the loo */ + if (l) { + break; + } + } + + /* if i isn't 2, we broke out of that loo */ + if (i != 2) { + continue; + } + + BM_faces_join_pair(bm, f1, f2, e); + } + } + + BLI_array_free(jedges); +} |