From 987ce2334c6cb83f8e841903d8a601ed49d6f6a2 Mon Sep 17 00:00:00 2001 From: ellson Date: Fri, 29 Apr 2005 21:38:21 +0000 Subject: [PATCH] add bb to node_t ( ND_bb(n) ) and to splines compute bb in an initial graph traversal in emit_graphs() (we might want to change this eventually and compute ND_bb during layout instead of ND_lw, ND_rw, ND_ht) use bb in node_in_view() and edge_in_view() during emit_graph() use bb in mouse event -> object resolution --- lib/common/emit.c | 78 +++++++++++++++++++++------ lib/common/renderprocs.h | 9 ++-- lib/common/types.h | 3 ++ lib/common/utils.c | 67 +++++++++++++++++++---- lib/gvc/gvevent.c | 111 +++++++++++++++++++++++---------------- 5 files changed, 196 insertions(+), 72 deletions(-) diff --git a/lib/common/emit.c b/lib/common/emit.c index 895036d30..32643fc7c 100644 --- a/lib/common/emit.c +++ b/lib/common/emit.c @@ -429,16 +429,7 @@ fprintf(stderr,"pagesArrayElem = %d,%d pageSize = %g,%g pageOffset = %g,%g\n", static boolean node_in_view(GVJ_t *job, node_t * n) { - boxf b; - - if (boxf_contains(job->clip, job->pageBox) && job->numPages == 1) - return TRUE; - b.LL.x = ND_coord_i(n).x - ND_lw_i(n); - b.LL.y = ND_coord_i(n).y - ND_ht_i(n) / 2.; - b.UR.x = ND_coord_i(n).x + ND_rw_i(n); - b.UR.y = ND_coord_i(n).y + ND_ht_i(n) / 2.; - - return boxf_overlap(job->pageBoxClip, b); + return boxf_overlap(job->pageBoxClip, ND_bb(n)); } static boolean is_natural_number(char *sstr) @@ -684,13 +675,15 @@ static boolean edge_in_view(GVJ_t *job, edge_t * e) double sx, sy; boxf b; textlabel_t *lp; + splines *spl; - if (boxf_contains(job->clip, job->pageBox) && job->numPages == 1) - return TRUE; - if (ED_spl(e) == NULL) + spl = ED_spl(e); + if (spl == NULL) + return FALSE; + if (! boxf_overlap(job->pageBoxClip, spl->bb)) return FALSE; - for (i = 0; i < ED_spl(e)->size; i++) { - bz = ED_spl(e)->list[i]; + for (i = 0; i < spl->size; i++) { + bz = spl->list[i]; np = bz.size; p = bz.list; P2PF(p[0],pp); @@ -1124,7 +1117,7 @@ static void emit_colors(GVJ_t * job, graph_t * g) } } -static void emit_view(GVJ_t * job, graph_t * g, int flags) +void emit_view(GVJ_t * job, graph_t * g, int flags) { GVC_t * gvc = job->gvc; node_t *n; @@ -1607,6 +1600,58 @@ static FILE *file_select(char *str) return rv; } +static void init_bb_node(node_t *n) +{ + ND_bb(n).LL.x = ND_coord_i(n).x - ND_lw_i(n); + ND_bb(n).LL.y = ND_coord_i(n).y - ND_ht_i(n) / 2.; + ND_bb(n).UR.x = ND_coord_i(n).x + ND_rw_i(n); + ND_bb(n).UR.y = ND_coord_i(n).y + ND_ht_i(n) / 2.; +} + +static void init_bb_spl(splines *spl) +{ + int i, j; + bezier bz; + box bb; + boxf bbf; + + for (i = 0; i < spl->size; i++) { + bz = spl->list[i]; + bb.UR = bb.LL = bz.list[0]; + for (j = 1; j < bz.size; j++) { + bb.LL.x = MIN(bb.LL.x, bz.list[j].x); + bb.LL.y = MIN(bb.LL.y, bz.list[j].y); + bb.UR.x = MAX(bb.UR.x, bz.list[j].x); + bb.UR.y = MAX(bb.UR.y, bz.list[j].y); + } + B2BF(bb, bbf); + if (i == 0) + spl->bb = bbf; + else { + spl->bb.LL.x = MIN(spl->bb.LL.x, bbf.LL.x); + spl->bb.LL.y = MIN(spl->bb.LL.y, bbf.LL.y); + spl->bb.UR.x = MAX(spl->bb.UR.x, bbf.UR.x); + spl->bb.UR.y = MAX(spl->bb.UR.y, bbf.UR.y); + } + } +} + +static void init_bb(graph_t *g) +{ + node_t *n; + edge_t *e; + splines *spl; + + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + init_bb_node(n); + for (e = agfstout(g, n); e; e = agnxtout(g, e)) { + spl = ED_spl(e); + if (spl) + init_bb_spl(spl); + } + } +} + void emit_jobs (GVC_t * gvc, graph_t * g) { GVJ_t *job; @@ -1614,6 +1659,7 @@ void emit_jobs (GVC_t * gvc, graph_t * g) init_gvc_from_graph(gvc, g); init_layering(gvc, g); + init_bb(g); gvc->active_jobs = NULL; for (job = gvrender_first_job(gvc); job; job = gvrender_next_job(gvc)) { diff --git a/lib/common/renderprocs.h b/lib/common/renderprocs.h index 4c831a6ce..1d4e18bea 100644 --- a/lib/common/renderprocs.h +++ b/lib/common/renderprocs.h @@ -40,11 +40,14 @@ extern "C" { pointf p), pointf * sp, boolean left_inside); extern shape_desc *bind_shape(char *name, node_t *); - extern box boxof(int, int, int, int); + extern box boxof(int llx, int lly, int urx, int ury); + extern boxf boxfof(double llx, double lly, double urx, double ury); + extern box box_bb(box, box); + extern boxf boxf_bb(boxf, boxf); + extern box box_intersect(box, box); + extern boxf boxf_intersect(boxf, boxf); extern boolean box_overlap(box, box); extern boolean boxf_overlap(boxf, boxf); - extern boolean box_contains(box, box); - extern boolean boxf_contains(boxf, boxf); extern void cat_libfile(FILE *, char **, char **); extern void clip_and_install(edge_t *, edge_t *, point *, int, splineInfo *); diff --git a/lib/common/types.h b/lib/common/types.h index 197054ebc..923c73f0d 100644 --- a/lib/common/types.h +++ b/lib/common/types.h @@ -111,6 +111,7 @@ extern "C" { typedef struct splines { bezier *list; int size; + boxf bb; } splines; /* fp variants */ @@ -447,6 +448,7 @@ extern "C" { void *shape_info; point coord; double width, height; + boxf bb; int ht, lw, rw; textlabel_t *label; void *alg; @@ -493,6 +495,7 @@ extern "C" { #define ND_UF_parent(n) (n)->u.UF_parent #define ND_UF_size(n) (n)->u.UF_size #define ND_alg(n) (n)->u.alg +#define ND_bb(n) (n)->u.bb #define ND_clust(n) (n)->u.clust #define ND_coord_i(n) (n)->u.coord #define ND_dist(n) (n)->u.dist diff --git a/lib/common/utils.c b/lib/common/utils.c index 42c897bcc..6dd4812ad 100644 --- a/lib/common/utils.c +++ b/lib/common/utils.c @@ -270,6 +270,15 @@ box boxof(int llx, int lly, int urx, int ury) return b; } +boxf boxfof(double llx, double lly, double urx, double ury) +{ + boxf b; + + b.LL.x = llx, b.LL.y = lly; + b.UR.x = urx, b.UR.y = ury; + return b; +} + box mkbox(point p0, point p1) { box rv; @@ -595,6 +604,54 @@ void cat_libfile(FILE * ofp, char **arglib, char **stdlib) } } +box box_bb(box b0, box b1) +{ + box b; + + b.LL.x = MIN(b0.LL.x, b1.LL.x); + b.LL.y = MIN(b0.LL.y, b1.LL.y); + b.UR.x = MAX(b0.UR.x, b1.UR.x); + b.UR.y = MAX(b0.UR.y, b1.UR.y); + + return b; +} + +boxf boxf_bb(boxf b0, boxf b1) +{ + boxf b; + + b.LL.x = MIN(b0.LL.x, b1.LL.x); + b.LL.y = MIN(b0.LL.y, b1.LL.y); + b.UR.x = MAX(b0.UR.x, b1.UR.x); + b.UR.y = MAX(b0.UR.y, b1.UR.y); + + return b; +} + +box box_intersect(box b0, box b1) +{ + box b; + + b.LL.x = MAX(b0.LL.x, b1.LL.x); + b.LL.y = MAX(b0.LL.y, b1.LL.y); + b.UR.x = MIN(b0.UR.x, b1.UR.x); + b.UR.y = MIN(b0.UR.y, b1.UR.y); + + return b; +} + +boxf boxf_intersect(boxf b0, boxf b1) +{ + boxf b; + + b.LL.x = MAX(b0.LL.x, b1.LL.x); + b.LL.y = MAX(b0.LL.y, b1.LL.y); + b.UR.x = MIN(b0.UR.x, b1.UR.x); + b.UR.y = MIN(b0.UR.y, b1.UR.y); + + return b; +} + boolean box_overlap(box b0, box b1) { if ((b0.UR.x < b1.LL.x) || (b1.UR.x < b0.LL.x) @@ -611,15 +668,7 @@ boolean boxf_overlap(boxf b0, boxf b1) return TRUE; } -boolean box_contains(box b0, box b1) -{ - if ((b0.UR.x >= b1.UR.x) && (b0.UR.y >= b1.UR.y) - && (b0.LL.x <= b1.LL.x) && (b0.LL.y <= b1.LL.y)) - return TRUE; - return FALSE; -} - -boolean boxf_contains(boxf b0, boxf b1) +boolean boxf_contains_p(boxf b0, boxf b1) { if ((b0.UR.x >= b1.UR.x) && (b0.UR.y >= b1.UR.y) && (b0.LL.x <= b1.LL.x) && (b0.LL.y <= b1.LL.y)) diff --git a/lib/gvc/gvevent.c b/lib/gvc/gvevent.c index f17193775..bea2d5924 100644 --- a/lib/gvc/gvevent.c +++ b/lib/gvc/gvevent.c @@ -37,21 +37,13 @@ void gvevent_refresh(GVJ_t * job) emit_graph(job, job->g); } -static boolean inside_node_bb(node_t *n, pointf P) -{ - boxf bb; - - bb.UR.x = ND_coord_i(n).x + ND_rw_i(n); - bb.UR.y = ND_coord_i(n).y + ND_ht_i(n) / 2.; - bb.LL.x = ND_coord_i(n).x - ND_lw_i(n); - bb.LL.y = ND_coord_i(n).y - ND_ht_i(n) / 2.; - return (INSIDE(P, bb)); -} - -static boolean inside_node(node_t *n, pointf p) +static boolean inside_node(node_t *n, pointf P, pointf p) { inside_t ictxt; + if (! INSIDE(P, ND_bb(n))) + return FALSE; + ictxt.s.n = n; ictxt.s.bp = NULL; @@ -59,15 +51,33 @@ static boolean inside_node(node_t *n, pointf p) return TRUE; } -static boolean inside_edge_bb(edge_t *e, pointf P) +static boolean inside_label(edge_t *e, pointf p) +{ + textlabel_t *lp; + double sx, sy; + boxf bb; + + lp = ED_label(e); + if (lp == NULL) + return FALSE; + sx = lp->dimen.x / 2.; + sy = lp->dimen.y / 2.; + bb.LL.x = lp->p.x - sx; + bb.UR.x = lp->p.x + sx; + bb.LL.y = lp->p.y - sy; + bb.UR.y = lp->p.y + sy; + return INSIDE(p, bb); +} + +static boolean inside_spline(splines *spl, pointf P, pointf p) { int i, j, k; bezier bz; - boxf BB; box bb; + boxf bbf; - for (i = 0; i < ED_spl(e)->size; i++) { - bz = ED_spl(e)->list[i]; + for (i = 0; i < spl->size; i++) { + bz = spl->list[i]; for (j = 0; j < bz.size -1; j += 3) { /* compute a bb for the bezier segment */ bb.LL = bb.UR = bz.list[j]; @@ -77,17 +87,31 @@ static boolean inside_edge_bb(edge_t *e, pointf P) bb.UR.x = MAX(bb.UR.x,bz.list[k].x); bb.UR.y = MAX(bb.UR.y,bz.list[k].y); } - B2BF(bb,BB); - if (INSIDE(P,BB)) + B2BF(bb,bbf); + if (INSIDE(P,bbf)) { + /* FIXME - check if really close enough to actual curve */ return TRUE; + } } } return FALSE; } -static boolean inside_edge(edge_t *n, pointf p) +static boolean inside_edge(edge_t *e, pointf P, pointf p) { - return TRUE; + splines *spl; + + spl = ED_spl(e); + if (spl == NULL) + return FALSE; + if (! INSIDE(P, spl->bb)) + return FALSE; + if (inside_spline(spl, P, p)) + return TRUE; +// FIXME +// if (inside_arrow(e)) +// return TRUE; + return inside_label(e, p); } static graph_t *gvevent_find_cluster(graph_t *g, pointf P) @@ -107,34 +131,22 @@ static graph_t *gvevent_find_cluster(graph_t *g, pointf P) return NULL; } -static void * gvevent_find_obj(GVJ_t * job, pointf p) +static void * gvevent_find_obj(graph_t *g, pointf P, pointf p) { - graph_t *sg, *g = job->g; + graph_t *sg; node_t *n; edge_t *e; - pointf P; /* point in graph coordinates */ - - /* convert point to graph coordinates */ - if (job->rotation) { - P.x = job->focus.y - (p.y - job->height / 2.) / job->compscale.x; - P.y = (p.x - job->width / 2.) / job->compscale.y + job->focus.x; - } - else { - P.x = (p.x - job->width / 2.) / job->compscale.x + job->focus.x; - P.y = (p.y - job->height / 2.) / job->compscale.y + job->focus.y; - } + /* edges might overlap nodes, so search them first */ + for (n = agfstnode(g); n; n = agnxtnode(g, n)) + for (e = agfstout(g, n); e; e = agnxtout(g, e)) + if (inside_edge(e, P, p)) + return (void *)e; /* search graph backwards to get topmost node, in case of overlap */ - for (n = aglstnode(g); n; n = agprvnode(g, n)) { - if (inside_node_bb(n, P) && inside_node(n, p)) + for (n = aglstnode(g); n; n = agprvnode(g, n)) + if (inside_node(n, P, p)) return (void *)n; - for (e = agfstout(g, n); e; e = agnxtout(g, e)) { - if (inside_edge_bb(e, P) && inside_edge(e, p)) - return (void *)e; - } - } - /* no node or edge found, so - search for innermost cluster */ + /* search for innermost cluster */ sg = gvevent_find_cluster(g, P); if (sg) return (void *)sg; @@ -146,11 +158,22 @@ static void * gvevent_find_obj(GVJ_t * job, pointf p) static void gvevent_find_current_obj(GVJ_t * job, double x, double y) { void *obj; - pointf p; + pointf p, P; p.x = x; p.y = y; - obj = gvevent_find_obj(job, p); + + /* convert point to graph coordinates */ + if (job->rotation) { + P.x = job->focus.y - (p.y - job->height / 2.) / job->compscale.x; + P.y = (p.x - job->width / 2.) / job->compscale.y + job->focus.x; + } + else { + P.x = (p.x - job->width / 2.) / job->compscale.x + job->focus.x; + P.y = (p.y - job->height / 2.) / job->compscale.y + job->focus.y; + } + + obj = gvevent_find_obj(job->g, P, p); if (obj != job->current_obj) { job->current_obj = obj; fprintf(stderr,"obj=%x kind=%d\n",obj,agobjkind(obj)); -- 2.40.0