From 9d1031b011994f508c766593eb8b149077ebe84a Mon Sep 17 00:00:00 2001 From: Howard Trickey Date: Tue, 5 Nov 2019 13:23:20 -0500 Subject: Fixed delaunay check, was causing 'desperation' messages. Check was losing precision -- adjust by translating points before calculating circumcircle. Also, needed to check for flippability of edges before flipping. --- source/blender/blenlib/intern/delaunay_2d.c | 260 +++++++++++++++++++--------- 1 file changed, 181 insertions(+), 79 deletions(-) (limited to 'source/blender/blenlib') diff --git a/source/blender/blenlib/intern/delaunay_2d.c b/source/blender/blenlib/intern/delaunay_2d.c index af4fa9fa54e..f297d8cfeed 100644 --- a/source/blender/blenlib/intern/delaunay_2d.c +++ b/source/blender/blenlib/intern/delaunay_2d.c @@ -124,6 +124,17 @@ static int CCW_test(const double a[2], const double b[2], const double c[2], con /* This is twice the signed area of triangle abc. */ det = (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]); + if (eps == 0.0) { + if (det > 0) { + return 1; + } + else if (det < 0) { + return -1; + } + else { + return 0; + } + } ab = len_v2v2_db(a, b); if (ab <= eps) { return 0; @@ -617,8 +628,9 @@ static bool locate_point_final(const double p[2], double lambda, close[2]; bool done = false; #ifdef DEBUG_CDT - int dbglevel = 0; - if (dbglevel > 0) { + int dbg_level = 0; + + if (dbg_level > 0) { fprintf(stderr, "locate_point_final %d\n", try_neighbors); dump_se(tri_se, "tri_se"); fprintf(stderr, "\n"); @@ -628,7 +640,7 @@ static bool locate_point_final(const double p[2], i = 0; do { #ifdef DEBUG_CDT - if (dbglevel > 1) { + if (dbg_level > 1) { fprintf(stderr, "%d: ", i); dump_se(se, "search se"); } @@ -640,7 +652,7 @@ static bool locate_point_final(const double p[2], if (len_close_p < epsilon) { if (len_v2v2_db(p, a) < epsilon) { #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { fprintf(stderr, "OnVert case a (%.2f,%.2f)\n", F2(a)); } #endif @@ -651,7 +663,7 @@ static bool locate_point_final(const double p[2], } else if (len_v2v2_db(p, b) < epsilon) { #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { fprintf(stderr, "OnVert case b (%.2f,%.2f)\n", F2(b)); } #endif @@ -662,7 +674,7 @@ static bool locate_point_final(const double p[2], } else if (lambda > 0.0 && lambda < 1.0) { #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { fprintf(stderr, "OnEdge case, lambda=%f\n", lambda); dump_se(se, "se"); } @@ -682,7 +694,7 @@ static bool locate_point_final(const double p[2], } while (se != tri_se && !done); if (!done) { #ifdef DEBUG_CDT - if (dbglevel > 1) { + if (dbg_level > 1) { fprintf(stderr, "not done, dist_inside=%f %f %f\n", dist_inside[0], @@ -692,7 +704,7 @@ static bool locate_point_final(const double p[2], #endif if (dist_inside[0] >= 0.0 && dist_inside[1] >= 0.0 && dist_inside[2] >= 0.0) { #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { fprintf(stderr, "InFace case\n"); dump_se_cycle(tri_se, "tri", 10); } @@ -740,14 +752,14 @@ static bool locate_point_final(const double p[2], r_lr->edge_lambda = lambda; } #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { fprintf( stderr, "desperation case kind=%u lambda=%f\n", r_lr->loc_kind, r_lr->edge_lambda); dump_se(r_lr->se, "se"); BLI_assert(0); /* While developing, catch these "should not happens" */ } #endif - fprintf(stderr, "desperation!\n"); // TODO: remove + fprintf(stderr, "desperation! point=(%g,%g)\n", p[0], p[1]); // TODO: remove return true; } } @@ -769,9 +781,9 @@ static LocateResult locate_point(CDT_state *cdt, const double p[2]) int visit = ++cdt->visit_count; int loop_count = 0; #ifdef DEBUG_CDT - int dbglevel = 0; + int dbg_level = 0; - if (dbglevel > 0) { + if (dbg_level > 0) { fprintf(stderr, "locate_point (%.2f,%.2f), visit_index=%d\n", F2(p), visit); } #endif @@ -790,7 +802,7 @@ static LocateResult locate_point(CDT_state *cdt, const double p[2]) v = cdt->vert_array[i]; dist_squared = len_squared_v2v2_db(p, v->co); #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { fprintf(stderr, "try start vert %d, dist_squared=%f\n", i, dist_squared); dump_v(v, "v"); } @@ -806,7 +818,7 @@ static LocateResult locate_point(CDT_state *cdt, const double p[2]) BLI_assert(cur_se->face != cdt->outer_face); } #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { dump_se(cur_se, "start vert edge"); } #endif @@ -815,7 +827,7 @@ static LocateResult locate_point(CDT_state *cdt, const double p[2]) /* Find edge of cur_tri that separates p and t's centroid, * and where other tri over the edge is unvisited. */ #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { dump_se_cycle(cur_se, "cur search face", 5); } #endif @@ -826,10 +838,10 @@ static LocateResult locate_point(CDT_state *cdt, const double p[2]) a = cur_se->vert->co; b = cur_se->next->vert->co; c = cur_se->next->next->vert->co; - if (CCW_test(a, b, p, epsilon) >= 0 && CCW_test(b, c, p, epsilon) >= 0 && - CCW_test(c, a, p, epsilon) >= 0) { + if (CCW_test(a, b, p, 0.0) >= 0 && CCW_test(b, c, p, 0.0) >= 0 && + CCW_test(c, a, p, 0.0) >= 0) { #ifdef DEBUG_CDT - if (dbglevel > 1) { + if (dbg_level > 1) { fprintf(stderr, "p in current triangle\n"); } #endif @@ -844,28 +856,28 @@ static LocateResult locate_point(CDT_state *cdt, const double p[2]) b = next_se->next->vert->co; c = next_se->next->next->vert->co; #ifdef DEBUG_CDT - if (dbglevel > 1) { + if (dbg_level > 1) { dump_se(next_se, "search edge"); - fprintf(stderr, "tri centroid=(%.2f,%.2f)\n", F2(cur_tri->centroid)); + fprintf(stderr, "tri centroid=(%.3f,%.3f)\n", F2(cur_tri->centroid)); validate_face_centroid(next_se); } #endif next_se_sym = sym(next_se); - if (CCW_test(a, b, p, epsilon) <= 0 && next_se->face != cdt->outer_face) { + if (CCW_test(a, b, p, 0.0) <= 0 && next_se->face != cdt->outer_face) { #ifdef DEBUG_CDT - if (dbglevel > 1) { + if (dbg_level > 1) { fprintf(stderr, "CCW_test(a, b, p) <= 0\n"); } #endif #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { dump_se(next_se_sym, "next_se_sym"); fprintf(stderr, "next_se_sym face visit=%d\n", next_se_sym->face->visit_index); } #endif if (next_se_sym->face->visit_index != visit) { #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { fprintf(stderr, "found edge to cross\n"); } #endif @@ -890,32 +902,50 @@ static LocateResult locate_point(CDT_state *cdt, const double p[2]) return lr; } -/** return true if circumcircle(v1, v2, v3) does not contain p. */ +/** Return true if circumcircle(v1, v2, v3) does not contain p. + * To avoid possible infinite flip loops, we will say true even if p is inside the circle + * but less than epsilon from the boundary; or if v1, v2, v3, form a straight line. + */ static bool delaunay_check(CDTVert *v1, CDTVert *v2, CDTVert *v3, CDTVert *p, const double epsilon) { - double a, b, c, d, z1, z2, z3; - const double *p1, *p2, *p3; - double cen[2], r, len_pc; - /* To do epislon test, need center and radius of circumcircle. */ - p1 = v1->co; - p2 = v2->co; - p3 = v3->co; - z1 = dot_v2v2_db(p1, p1); - z2 = dot_v2v2_db(p2, p2); - z3 = dot_v2v2_db(p3, p3); - a = p1[0] * (p2[1] - p3[1]) - p1[1] * (p2[0] - p3[0]) + p2[0] * p3[1] - p3[0] * p2[1]; - b = z1 * (p3[1] - p2[1]) + z2 * (p1[1] - p3[1]) + z3 * (p2[1] - p1[1]); - c = z1 * (p2[0] - p3[0]) + z2 * (p3[0] - p1[0]) + z3 * (p1[0] - p2[0]); - d = z1 * (p3[0] * p2[1] - p2[0] * p3[1]) + z2 * (p1[0] * p3[1] - p3[0] * p1[1]) + - z3 * (p2[0] * p1[1] - p1[0] * p2[1]); - if (a == 0.0) { - return true; /* Not really, but this shouldn't happen. */ - } - cen[0] = -b / (2 * a); - cen[1] = -c / (2 * a); - r = sqrt((b * b + c * c - 4 * a * d) / (4 * a * a)); - len_pc = len_v2v2_db(p->co, cen); - return (len_pc >= (r - epsilon)); + double x1, y1, x2, y2, den, cenx, ceny, rad, pc, a, b, w, z, q, s; + + /* Find center and radius of circumcircle of v1,v2,v3. + * Transform coords so v3 is at origin to help reduce floating point error + * when coordinates are far from (0,0) but close together. + */ + x1 = v1->co[0] - v3->co[0]; + y1 = v1->co[1] - v3->co[1]; + x2 = v2->co[0] - v3->co[0]; + y2 = v2->co[1] - v3->co[1]; + den = 2.0 * (x1 * y2 - x2 * y1); + if (UNLIKELY(den == 0.0)) { + /* v1, v2, v3 are in a line. */ + return true; + } + /* cen[0] = det(x1**2 + y1**2, y1, x2**2 + y2**2, y2) / den + * cen[1] = det(x1, x1**2 + y1**2, x2, x2**2 + y2**2) / den + * den = 2 * det(x1, y1, x2, y2) + */ + a = x1 * x1 + y1 * y1; + b = x2 * x2 + y2 * y2; + cenx = (a * y2 - b * y1) / den; + ceny = (x1 * b - x2 * a) / den; + w = x1 - cenx; + z = y1 - ceny; + rad = sqrt(w * w + z * z); + q = p->co[0] - v3->co[0] - cenx; + s = p->co[1] - v3->co[1] - ceny; + pc = sqrt(q * q + s * s); + return (pc >= rad - epsilon); +} + +/* Return true if we can flip edge v1-v3 to edge v2-v4 inside quad v1v2v3v4 (in CCW order). + * We can do this if angles v4-v1-v2 and v2-v3-v4 are both CCW or straight. + */ +static inline bool can_flip(CDTVert *v1, CDTVert *v2, CDTVert *v3, CDTVert *v4) +{ + return CCW_test(v4->co, v1->co, v2->co, 0.0) >= 0 && CCW_test(v2->co, v3->co, v4->co, 0.0) >= 0; } /** Use LinkNode linked list as stack of SymEdges, allocating from cdt->listpool. */ @@ -955,12 +985,12 @@ static void flip(SymEdge *se, CDT_state *cdt) CDTFace *t1, *t2; CDTVert *v1, *v2; #ifdef DEBUG_CDT - const int dbglevel = 0; + const int dbg_level = 0; #endif sesym = sym(se); #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { fprintf(stderr, "flip\n"); dump_se(se, "se"); dump_se(sesym, "sesym"); @@ -975,7 +1005,7 @@ static void flip(SymEdge *se, CDT_state *cdt) csym = sym(c); dsym = sym(d); #ifdef DEBUG_CDT - if (dbglevel > 1) { + if (dbg_level > 1) { dump_se(a, "a"); dump_se(b, "b"); dump_se(c, "c"); @@ -1020,7 +1050,7 @@ static void flip(SymEdge *se, CDT_state *cdt) calc_face_centroid(sesym); #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { fprintf(stderr, "after flip\n"); dump_se_cycle(a, "a cycle", 5); dump_se_cycle(sesym, "sesym cycle", 5); @@ -1038,10 +1068,10 @@ static void flip_edges(CDTVert *v, Stack *stack, CDT_state *cdt) SymEdge *tri_without_p; bool is_delaunay; const double epsilon = cdt->epsilon; - int count = 0; + int count = 3; #ifdef DEBUG_CDT - const int dbglevel = 0; - if (dbglevel > 0) { + const int dbg_level = 0; + if (dbg_level > 0) { fprintf(stderr, "flip_edges, v=(%.2f,%.2f)\n", F2(v->co)); } #endif @@ -1052,17 +1082,17 @@ static void flip_edges(CDTVert *v, Stack *stack, CDT_state *cdt) } se = pop(stack, cdt); #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { dump_se(se, "flip_edges popped"); } #endif if (!is_constrained_edge(se->edge)) { /* Edge is not constrained; is it Delaunay? */ #ifdef DEBUG_CDT - if (dbglevel > 1) { + if (dbg_level > 1) { dump_se_cycle(se, "unconstrained edge", 5); } - else if (dbglevel > 0) { + else if (dbg_level > 0) { fprintf(stderr, "unconstrained edge\n"); } #endif @@ -1072,16 +1102,16 @@ static void flip_edges(CDTVert *v, Stack *stack, CDT_state *cdt) sesym = sym(se); d = sesym->next->next->vert; #ifdef DEBUG_CDT - if (dbglevel > 1) { - fprintf(stderr, "a=(%.2f,%.2f) b=(%.2f,%.2f)\n", F2(a->co), F2(b->co)); - fprintf(stderr, "c=(%.2f,%.2f) d=(%.2f,%.2f)\n", F2(c->co), F2(d->co)); + if (dbg_level > 1) { + fprintf(stderr, "a=(%.3f,%.3f) b=(%.3f,%.3f)\n", F2(a->co), F2(b->co)); + fprintf(stderr, "c=(%.3f,%.3f) d=(%.3f,%.3f)\n", F2(c->co), F2(d->co)); } #endif if (v == c) { tri_without_p = sesym; is_delaunay = delaunay_check(a, b, c, d, epsilon); #ifdef DEBUG_CDT - if (dbglevel > 1) { + if (dbg_level > 1) { fprintf(stderr, "v==c, delaunay(a,b,c,d)=%d\n", is_delaunay); } #endif @@ -1091,21 +1121,21 @@ static void flip_edges(CDTVert *v, Stack *stack, CDT_state *cdt) BLI_assert(d == v); is_delaunay = delaunay_check(b, a, d, c, epsilon); #ifdef DEBUG_CDT - if (dbglevel > 1) { + if (dbg_level > 1) { fprintf(stderr, "v!=c, delaunay(b,a,d,c)=%d\n", is_delaunay); } #endif } - if (!is_delaunay) { + if (!is_delaunay && can_flip(a, d, b, c)) { /* Push two edges of tri without p that aren't se. */ #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { fprintf(stderr, "maybe pushing more edges\n"); } #endif if (!is_border_edge(tri_without_p->next->edge, cdt)) { #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { dump_se(tri_without_p->next, "push1"); } #endif @@ -1113,13 +1143,20 @@ static void flip_edges(CDTVert *v, Stack *stack, CDT_state *cdt) } if (!is_border_edge(tri_without_p->next->next->edge, cdt)) { #ifdef DEBUG_CDT - if (dbglevel > 0) { + if (dbg_level > 0) { dump_se(tri_without_p->next->next, "\npush2"); } #endif push(stack, tri_without_p->next->next, cdt); } flip(se, cdt); +#ifdef DEBUG_CDT + if (dbg_level > 2) { + dump_cdt(cdt, "after flip"); + cdt_draw(cdt, "afer flip"); + validate_cdt(cdt, true); + } +#endif } } } @@ -1205,6 +1242,14 @@ static CDTVert *insert_point_in_face(CDT_state *cdt, SymEdge *e, const double p[ CDTEdge *he, *ie, *je; CDTFace *t1, *t2, *t3; Stack stack; +#ifdef DEBUG_CDT + int dbg_level = 0; + + if (dbg_level > 0) { + fprintf(stderr, "insert point in face, p=(%.3f,%.3f)\n", F2(p)); + dump_se_cycle(e, "insert face", 20); + } +#endif f = e->next; g = f->next; @@ -1257,6 +1302,20 @@ static CDTVert *insert_point_in_face(CDT_state *cdt, SymEdge *e, const double p[ calc_face_centroid(f); calc_face_centroid(g); +#ifdef DEBUG_CDT + if (dbg_level > 1) { + fprintf(stderr, "after initial insert:\n"); + dump_se_cycle(e, "e", 20); + dump_se_cycle(f, "f", 20); + dump_se_cycle(g, "g", 20); + if (dbg_level > 2) { + dump_cdt(cdt, "after initial insert, before flip"); + cdt_draw(cdt, "after initial insert, before flip"); + validate_cdt(cdt, true); + } + } +#endif + stack = NULL; if (!is_border_edge(e->edge, cdt)) { push(&stack, e, cdt); @@ -2318,7 +2377,7 @@ CDT_result *BLI_delaunay_2d_cdt_calc(const CDT_input *input, const CDT_output_ty CDTEdge *face_edge; SymEdge *face_symedge; #ifdef DEBUG_CDT - int dbg_level = 0; + int dbg_level = 1; #endif if ((nv > 0 && input->vert_coords == NULL) || (ne > 0 && input->edges == NULL) || @@ -2364,6 +2423,15 @@ CDT_result *BLI_delaunay_2d_cdt_calc(const CDT_input *input, const CDT_output_ty vert_co[0] = (double)input->vert_coords[i][0]; vert_co[1] = (double)input->vert_coords[i][1]; verts[i] = add_point_constraint(cdt, vert_co, i); +#ifdef DEBUG_CDT + if (dbg_level > 3) { + char namebuf[60]; + sprintf(namebuf, "after point %d = (%f,%f)\n", i, vert_co[0], vert_co[1]); + cdt_draw(cdt, namebuf); + dump_cdt(cdt, namebuf); + validate_cdt(cdt, true); + } +#endif } for (i = 0; i < ne; i++) { v1 = input->edges[i][0]; @@ -2436,7 +2504,7 @@ CDT_result *BLI_delaunay_2d_cdt_calc(const CDT_input *input, const CDT_output_ty add_face_ids(cdt, face_symedge, f, fedge_start, fedge_end); } #ifdef DEBUG_CDT - if (dbg_level > 1) { + if (dbg_level > 0) { validate_cdt(cdt, true); } if (dbg_level > 1) { @@ -2512,16 +2580,16 @@ static void dump_se(const SymEdge *se, const char *lab) { if (se->next) { fprintf( - stderr, "%s((%.2f,%.2f)->(%.2f,%.2f))\n", lab, F2(se->vert->co), F2(se->next->vert->co)); + stderr, "%s((%.3f,%.3f)->(%.3f,%.3f))\n", lab, F2(se->vert->co), F2(se->next->vert->co)); } else { - fprintf(stderr, "%s((%.2f,%.2f)->NULL)\n", lab, F2(se->vert->co)); + fprintf(stderr, "%s((%.3f,%.3f)->NULL)\n", lab, F2(se->vert->co)); } } static void dump_v(const CDTVert *v, const char *lab) { - fprintf(stderr, "%s(%.2f,%.2f)\n", lab, F2(v->co)); + fprintf(stderr, "%s(%.3f,%.3f)\n", lab, F2(v->co)); } static void dump_se_cycle(const SymEdge *se, const char *lab, const int limit) @@ -2551,22 +2619,47 @@ static void dump_id_list(const LinkNode *id_list, const char *lab) } } +static const char *vertname(CDTVert *v) +{ + static char vertnamebuf[20]; + + if (v->index < 4) { + sprintf(vertnamebuf, "[%c]", "ABCD"[v->index]); + } + else { + sprintf(vertnamebuf, "[%d]", v->index - 4); + } + return vertnamebuf; +} + # define PL(p) (POINTER_AS_UINT(p) & 0xFFFF) static void dump_cdt(const CDT_state *cdt, const char *lab) { LinkNode *ln; - CDTVert *v; + CDTVert *v, *vother; CDTEdge *e; CDTFace *f; SymEdge *se; - int i; + int i, cnt; fprintf(stderr, "\nCDT %s\n", lab); fprintf(stderr, "\nVERTS\n"); for (i = 0; i < cdt->vert_array_len; i++) { v = cdt->vert_array[i]; - fprintf(stderr, "%x: (%f,%f) symedge=%x\n", PL(v), F2(v->co), PL(v->symedge)); + fprintf(stderr, "%s %x: (%f,%f) symedge=%x\n", vertname(v), PL(v), F2(v->co), PL(v->symedge)); dump_id_list(v->input_ids, " "); + se = v->symedge; + cnt = 0; + if (se) { + fprintf(stderr, " edges out:\n"); + do { + vother = sym(se)->vert; + fprintf(stderr, " %s (e=%x, se=%x)\n", vertname(vother), PL(se->edge), PL(se)); + se = se->rot; + cnt++; + } while (se != v->symedge && cnt < 25); + fprintf(stderr, "\n"); + } } fprintf(stderr, "\nEDGES\n"); for (ln = cdt->edges; ln; ln = ln->next) { @@ -2578,12 +2671,13 @@ static void dump_cdt(const CDT_state *cdt, const char *lab) for (i = 0; i < 2; i++) { se = &e->symedges[i]; fprintf(stderr, - " se[%d] @%x: next=%x, rot=%x, vert=%x (%.2f,%.2f), edge=%x, face=%x\n", + " se[%d] @%x: next=%x, rot=%x, vert=%x [%s] (%.2f,%.2f), edge=%x, face=%x\n", i, PL(se), PL(se->next), PL(se->rot), PL(se->vert), + vertname(se->vert), F2(se->vert->co), PL(se->edge), PL(se->face)); @@ -2673,7 +2767,7 @@ static void cdt_draw(CDT_state *cdt, const char *lab) strokew = is_constrained_edge(e) ? 5 : 2; fprintf(f, "\n", + "x1=\"%.3f\" y1=\"%.3f\" x2=\"%.3f\" y2=\"%.3f\">\n", strokew, SX(u->co[0]), SY(u->co[1]), @@ -2687,7 +2781,7 @@ static void cdt_draw(CDT_state *cdt, const char *lab) for (; i < cdt->vert_array_len; i++) { v = cdt->vert_array[i]; fprintf(f, - "\n", + "\n", SX(v->co[0]), SY(v->co[1])); fprintf(f, " (%.3f,%.3f)\n", v->co[0], v->co[1]); @@ -2812,7 +2906,7 @@ static void validate_cdt(CDT_state *cdt, bool check_all_tris) int totedges, totfaces, totverts, totborderedges; CDTEdge *e; SymEdge *se, *sesym, *s; - CDTVert *v; + CDTVert *v, *v1, *v2, *v3; CDTFace *f; double *p; double margin; @@ -2867,6 +2961,14 @@ static void validate_cdt(CDT_state *cdt, bool check_all_tris) limit = 10000; } BLI_assert(reachable(se->next, se, limit)); + if (limit == 3) { + v1 = se->vert; + v2 = se->next->vert; + v3 = se->next->next->vert; + BLI_assert(CCW_test(v1->co, v2->co, v3->co, 0.0)); + BLI_assert(CCW_test(v2->co, v3->co, v1->co, 0.0)); + BLI_assert(CCW_test(v3->co, v1->co, v2->co, 0.0)); + } UNUSED_VARS_NDEBUG(limit); BLI_assert(se->next->next != se); s = se; -- cgit v1.2.3