[Bf-blender-cvs] [da91575] master: Bevel: add width consistency pass.
Howard Trickey
noreply at git.blender.org
Mon Dec 2 13:29:41 CET 2013
Commit: da91575206cda63966fbd526378de98a866e8e5c
Author: Howard Trickey
Date: Mon Dec 2 07:16:49 2013 -0500
http://developer.blender.org/rBda91575206cda63966fbd526378de98a866e8e5c
Bevel: add width consistency pass.
When the desired widths (offsets) of beveled edges cannot be
satisfied, often because we want them to meet on an intermediate
non-beveled edge, we need to compromise on the widths somehow.
This code changes the compromise to minimize the sum of squares
of errors in the offsets. It also adds a global width consistency
pass: starting from a vertex that needed width adjustment, it
uses a breadth-first search to try to propagate the adjustments
and keep the bevel widths from having to taper along the edges.
Also fixed a case where a reflex angle would cause bad results.
Also fixed the way the 'percentage' width method was calculated.
===================================================================
M source/blender/bmesh/tools/bmesh_bevel.c
===================================================================
diff --git a/source/blender/bmesh/tools/bmesh_bevel.c b/source/blender/bmesh/tools/bmesh_bevel.c
index 5e68e46..7f39cbe 100644
--- a/source/blender/bmesh/tools/bmesh_bevel.c
+++ b/source/blender/bmesh/tools/bmesh_bevel.c
@@ -35,6 +35,7 @@
#include "BLI_array.h"
#include "BLI_alloca.h"
+#include "BLI_gsqueue.h"
#include "BLI_math.h"
#include "BLI_memarena.h"
@@ -75,6 +76,8 @@ typedef struct EdgeHalf {
int seg; /* how many segments for the bevel */
float offset_l; /* offset for this edge, on left side */
float offset_r; /* offset for this edge, on right side */
+ float offset_l_spec; /* user specification for offset_l */
+ float offset_r_spec; /* user specification for offset_r */
bool is_bev; /* is this edge beveled? */
bool is_rev; /* is e->v2 the vertex at this end? */
bool is_seam; /* is e a seam for custom loopdata (e.g., UVs)? */
@@ -117,6 +120,7 @@ typedef struct BevVert {
int selcount; /* number of selected edges around the vertex */
float offset; /* offset for this vertex, if vertex_only bevel */
bool any_seam; /* any seams on attached edges? */
+ bool visited; /* used in graph traversal */
EdgeHalf *edges; /* array of size edgecount; CCW order from vertex normal side */
VMesh *vmesh; /* mesh structure for replacing vertex */
} BevVert;
@@ -134,6 +138,7 @@ typedef struct BevelParams {
bool vertex_only; /* bevel vertices only */
bool use_weights; /* bevel amount affected by weights on edges or verts */
bool preserve_widths; /* should bevel prefer widths over angles, if forced to choose? */
+ bool limit_offset; /* should offsets be limited by collisions? */
const struct MDeformVert *dvert; /* vertex group array, maybe set if vertex_only */
int vertex_group; /* vertex group index, maybe set if vertex_only */
} BevelParams;
@@ -166,6 +171,11 @@ static BoundVert *add_new_bound_vert(MemArena *mem_arena, VMesh *vm, const float
return ans;
}
+BLI_INLINE void adjust_bound_vert(BoundVert *bv, const float co[3])
+{
+ copy_v3_v3(bv->nv.co, co);
+}
+
/* Mesh verts are indexed (i, j, k) where
* i = boundvert index (0 <= i < nv)
* j = ring index (0 <= j <= ns2)
@@ -216,21 +226,55 @@ static BevVert *find_bevvert(BevelParams *bp, BMVert *bmv)
}
/* Find the EdgeHalf representing the other end of e->e.
+ * Return other end's BevVert in *bvother, if r_bvother is provided.
* That may not have been constructed yet, in which case return NULL. */
-static EdgeHalf *find_other_end_edge_half(BevelParams *bp, EdgeHalf *e)
+static EdgeHalf *find_other_end_edge_half(BevelParams *bp, EdgeHalf *e, BevVert **r_bvother)
{
- BevVert *bvother;
+ BevVert *bvo;
EdgeHalf *eother;
- bvother = find_bevvert(bp, e->is_rev ? e->e->v1 : e->e->v2);
- if (bvother) {
- eother = find_edge_half(bvother, e->e);
+ bvo = find_bevvert(bp, e->is_rev ? e->e->v1 : e->e->v2);
+ if (bvo) {
+ if (r_bvother)
+ *r_bvother = bvo;
+ eother = find_edge_half(bvo, e->e);
BLI_assert(eother != NULL);
return eother;
}
+ else if (r_bvother) {
+ *r_bvother = NULL;
+ }
return NULL;
}
+static bool other_edge_half_visited(BevelParams *bp, EdgeHalf *e)
+{
+ BevVert *bvo;
+
+ bvo = find_bevvert(bp, e->is_rev ? e->e->v1 : e->e->v2);
+ if (bvo)
+ return bvo->visited;
+ else
+ return false;
+}
+
+static bool edge_half_offset_changed(EdgeHalf *e)
+{
+ return e->offset_l != e->offset_l_spec ||
+ e->offset_r != e->offset_r_spec;
+}
+
+static bool any_edge_half_offset_changed(BevVert *bv)
+{
+ int i;
+
+ for (i = 0; i < bv->edgecount; i++) {
+ if (edge_half_offset_changed(&bv->edges[i]))
+ return true;
+ }
+ return false;
+}
+
/* Return the next EdgeHalf after from_e that is beveled.
* If from_e is NULL, find the first beveled edge. */
static EdgeHalf *next_bev(BevVert *bv, EdgeHalf *from_e)
@@ -472,11 +516,14 @@ static void slide_dist(EdgeHalf *e, BMVert *v, float d, float slideco[3])
* When offsets are equal, the new point is on the edge bisector, with length offset/sin(angle/2),
* but if the offsets are not equal (allowing for this, as bevel modifier has edge weights that may
* lead to different offsets) then meeting point can be found be intersecting offset lines.
+ * If making the meeting point significantly changes the left or right offset from the user spec,
+ * record the change in offset_l (or offset_r); later we can tell that a change has happened because
+ * the offset will differ from its original value in offset_l_spec (or offset_r_spec).
*/
static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, float meetco[3])
{
float dir1[3], dir2[3], norm_v[3], norm_perp1[3], norm_perp2[3],
- off1a[3], off1b[3], off2a[3], off2b[3], isect2[3], ang;
+ off1a[3], off1b[3], off2a[3], off2b[3], isect2[3], ang, d;
/* get direction vectors for two offset lines */
sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co);
@@ -495,13 +542,17 @@ static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, float
normalize_v3(norm_perp1);
copy_v3_v3(off1a, v->co);
madd_v3_v3fl(off1a, norm_perp1, e1->offset_r);
+ if (e2->offset_l != e1->offset_r)
+ e2->offset_l = e1->offset_r;
copy_v3_v3(meetco, off1a);
}
else if (fabsf(ang - (float)M_PI) < 100.0f * BEVEL_EPSILON) {
/* special case e1 and e2 are antiparallel, so bevel is into
* a zero-area face. Just make the offset point on the
* common line, at offset distance from v. */
- slide_dist(e2, v, e2->offset_l, meetco);
+ slide_dist(e2, v, e1->offset_r, meetco);
+ if (e2->offset_l != e1->offset_r)
+ e2->offset_l = e1->offset_r;
}
else {
/* Get normal to plane where meet point should be,
@@ -532,45 +583,122 @@ static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, float
BLI_assert(!"offset_meet failure");
#endif
copy_v3_v3(meetco, off1a); /* just to do something */
+ d = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e2->e, v)->co);
+ if (fabsf(d - e2->offset_l) > BEVEL_EPSILON)
+ e2->offset_l = d;
}
}
}
-/* Like offset_in_two planes, but for the case where we prefer to solve the problem
- * of not meeting at the same point by choosing to change the bevel offset on one
- * of the appropriate side of either e1 or e2, in order that the lines can meet on emid. */
+/* Calculate the meeting point between e1 and e2 (one of which should have zero offsets),
+ * where e1 precedes e2 in CCW order around their common vertex v (viewed from normal side).
+ * If r_angle is provided, return the angle between e and emeet in *r_angle.
+ * If the angle is 0, or it is 180 degrees or larger, there will be no meeting point;
+ * return false in that case, else true */
+static bool offset_meet_edge(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, float meetco[3], float *r_angle)
+{
+ float dir1[3], dir2[3], fno[3], ang, sinang;
+
+ sub_v3_v3v3(dir1, BM_edge_other_vert(e1->e, v)->co, v->co);
+ sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co);
+ normalize_v3(dir1);
+ normalize_v3(dir2);
+
+ /* find angle from dir1 to dir2 as viewed from vertex normal side */
+ ang = angle_normalized_v3v3(dir1, dir2);
+ if (ang < BEVEL_EPSILON) {
+ if (r_angle)
+ *r_angle = 0.0f;
+ return false;
+ }
+ cross_v3_v3v3(fno, dir1, dir2);
+ if (dot_v3v3(fno, v->no) < 0.0f)
+ ang = 2.0f * (float)M_PI - ang; /* angle is reflex */
+ if (r_angle)
+ *r_angle = ang;
+
+ if (ang - (float)M_PI > BEVEL_EPSILON)
+ return false;
+
+ sinang = sinf(ang);
+ copy_v3_v3(meetco, v->co);
+ if (e1->offset_r == 0.0f)
+ madd_v3_v3fl(meetco, dir1, e2->offset_l / sinang);
+ else
+ madd_v3_v3fl(meetco, dir2, e1->offset_r / sinang);
+ return true;
+}
+
+/* Calculate the best place for a meeting point for the offsets from edges e1 and e2
+ * on the in-between edge emid. Viewed from the vertex normal side, the CCW
+ * order of these edges is e1, emid, e2.
+ * The offsets probably do not meet at a common point on emid, so need to pick
+ * one that causes the least problems. If the other end of one of e1 or e2 has been visited
+ * already, prefer to keep the offset the same on this end.
+ * Otherwise, pick a point between the two intersection points on emid that minimizes
+ * the sum of squares of errors from desired offset. */
static void offset_on_edge_between(BevelParams *bp, EdgeHalf *e1, EdgeHalf *e2, EdgeHalf *emid,
BMVert *v, float meetco[3])
{
+ float d, ang1, ang2, sina1, sina2, lambda;
+ float meet1[3], meet2[3];
+ bool visited1, visited2, ok1, ok2;
+
BLI_assert(e1->is_bev && e2->is_bev && !emid->is_bev);
-
- /* If have to change offset of e1 or e2, which one?
- * Prefer the one whose other end hasn't been constructed yet.
- * Following will choose to change e2 if both have already been constructed. */
- if (find_other_end_edge_half(bp, e1)) {
- offset_meet(e1, emid, v, e1->fnext, meetco);
- /* now e2's left offset is probably different */
- e2->offset_l = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e2->e, v)->co);
+
+ visited1 = other_edge_half_visited(bp, e1);
+ visited2 = other_edge_half_visited(bp, e2);
+
+ ok1 = offset_meet_edge(e1, emid, v, meet1, &ang1);
+ ok2 = offset_meet_edge(emid, e2, v, meet2, &ang2);
+ if (ok1 && ok2) {
+ if (visited1 && !visited2) {
+ copy_v3_v3(meetco, meet1);
+ }
+ else if (!visited1 && visited2) {
+ copy_v3_v3(meetco, meet2);
+ }
+ else {
+ /* find best compromise meet point */
+ sina1 = sinf(ang1);
+ sina2 = sinf(ang2);
+ lambda = sina2 * sina2 / (sina1 * sina1 + sina2 * sina2);
+ interp_v3_v3v3(meetco, meet1, meet2, lambda);
+ }
}
- else {
- offset_meet(emid, e2, v, emid->fnext, meetco);
- /* now e1's right offset is probably different */
- e1->offset_r = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e1->e, v)->co);
+ else if (ok1 && !ok2) {
+ copy_v3_v3(meetco, meet1);
+ }
+ else if (!ok1 && ok2) {
+ copy_v3_v3(meetco, meet2);
}
+ else {
+ /* Neither offset line met emid.
+ * This should only happen if all three lines are on top of each other */
+ slide_dist(emid, v, e1->offset_r, meetco);
+ }
+
+ /* offs
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list