// Vorosweep - Copyright (C) 2010-2014 T. Mouton // // See the LICENSE.txt file for license information. Please report all // bugs and problems to . #include "vorosweep.h" #include "border.h" using namespace vorosweep; Event *Graph::next_edgeswitch ( SweepEdge *se, double *pos, int gid ) { double exit[2]; int ngid; bucketgrid->compute_exit ( gid, pos, se->get_dir3d(), ngid, exit ); dbgprintf ( 5, "exit --> %lf %lf\n", exit[0], exit[1] ); // compute theorical time to next switch double tn = se->time_to_position ( exit ); Event *ne = econtainer->get(); ne->init ( se, exit, tn, Event::EDGESWITCH, ngid ); return ne; } Event *Graph::next_borderedgeswitch ( SweepEdge *se, Border *bo, double *pos, int gid ) { double exit[2]; int ngid; Grid1d *bordergrid = bo->get_grid(); bordergrid->compute_exit ( gid, pos, se->get_dir3d(), ngid, exit ); dbgprintf ( 2, "exit --> %lf %lf\n", exit[0], exit[1] ); // compute theorical time to next switch double tn = se->time_to_position ( exit ); Event *ne = econtainer->get(); ne->init ( se, bo, exit, tn, Event::BORDEREDGESWITCH, ngid ); return ne; } // Generate the edge crash events if any // Also check for the validity of events void Graph::next_edgecrashes ( SweepEdge *se ) { se->print(); dbgprintf ( 2, "--> generating next edge crashes\n" ); for ( int i = 0; i < 2; i++ ) { Front *fr = se->get_front ( i ); dbgprintf ( 5, "front %d --> %p\n", i, fr ); if ( fr ) { fr->print(); SweepEdge *secomp = fr->get_sweepedge ( i ); dbgprintf ( 2, "sweepedge secomp dir --> %lf %lf\n", secomp->get_dir2d() [0], secomp->get_dir2d() [1] ); dbgprintf ( 5, "front edges --> %p %p\n", se, secomp ); double crashpos[2]; if ( geom::lines2d_intersection ( se->get_start()->p, secomp->get_start()->p, se->get_dir2d(), secomp->get_dir2d(), Graph::epsilon, crashpos ) ) { double crashtime = se->time_to_position ( crashpos ); int ngid = bucketgrid->get_index ( crashpos ); Event *ne = econtainer->get(); ne->init ( se, secomp, crashpos, crashtime, Event::EDGE_EDGECRASH, ngid ); add_event ( ne ); } } } } void Graph::next_facetswitch ( SweepFacet *sf, double *pos, int gid, Event **eventlist, int &nbe ) { nbe = 0; // set nbe to zero !! FrontLine *fl = sf->get_frontline(); int i0, j0; bucketgrid->get_indices ( gid, i0, j0 ); dbgprintf ( 2, "cell --> %d %d\n", i0, j0 ); double npt[2]; int ngid[2]; // now we have a point and a line --> generate new events double *dir = sf->get_dir3d(); dbgprintf ( 2, "pos --> %lf %lf, dir --> %.20lf %.20lf\n", pos[0], pos[1], dir[0], dir[1] ); for ( int i = 0; i < 2; i++ ) { for ( int j = 0; j < 2; j++ ) { bucketgrid->get_vertex ( i0 + i, j0 + j, npt ); // if ( npt[0] != pos[0] && npt[1] != pos[1] && fl->valid_future_event ( npt ) ) if ( geom::sqrtdistance2d ( npt,pos ) > Graph::epsilon && fl->valid_future_event ( npt ) ) { if ( dir[0] == 0.0 ) // vertical { // printf ( "--> vertical\n" ); if ( dir[1] > 0.0 ) { ngid[0] = bucketgrid->get_index ( i0 + i, j0 + j ); ngid[1] = bucketgrid->get_index ( i0 + i - 1, j0 + j ); } else { ngid[0] = bucketgrid->get_index ( i0 + i, j0 + j - 1 ); ngid[1] = bucketgrid->get_index ( i0 + i - 1, j0 + j - 1 ); } double tn = sf->time_to_position ( npt ); for ( int k = 0; k < 2; k++ ) { if ( ngid[k] != -1 ) { Event *ne = econtainer->get(); ne->init ( sf, npt, tn, Event::FACETSWITCH, ngid[k] ); eventlist[nbe++] = ne; } } } else if ( dir[1] == 0.0 ) // vertical { // printf ( "--> horizontal\n" ); if ( dir[0] > 0.0 ) { ngid[0] = bucketgrid->get_index ( i0 + i, j0 + j ); ngid[1] = bucketgrid->get_index ( i0 + i, j0 + j - 1 ); } else { ngid[0] = bucketgrid->get_index ( i0 + i - 1, j0 + j ); ngid[1] = bucketgrid->get_index ( i0 + i - 1, j0 + j - 1 ); } double tn = sf->time_to_position ( npt ); for ( int k = 0; k < 2; k++ ) { if ( ngid[k] != -1 ) { Event *ne = econtainer->get(); ne->init ( sf, npt, tn, Event::FACETSWITCH, ngid[k] ); eventlist[nbe++] = ne; } } } else { // printf ( "--> general\n" ); if ( dir[0] > 0.0 ) { if ( dir[1] > 0.0 ) ngid[0] = bucketgrid->get_index ( i0 + i, j0 + j ); else ngid[0] = bucketgrid->get_index ( i0 + i, j0 + j - 1 ); } else { if ( dir[1] > 0.0 ) ngid[0] = bucketgrid->get_index ( i0 + i - 1, j0 + j ); else ngid[0] = bucketgrid->get_index ( i0 + i - 1, j0 + j - 1 ); } double tn = sf->time_to_position ( npt ); if ( ngid[0] != -1 ) { Event *ne = econtainer->get(); ne->init ( sf, npt, tn, Event::FACETSWITCH, ngid[0] ); eventlist[nbe++] = ne; } } } } } } void Graph::process_edge_events ( SweepEdge *se, double ctime, int gid ) { Bucket *buc = bucketgrid->get_bucket ( gid ); Event *eventlist[MAX_EVENT_LIST]; int nbe = 0; // generate facet crashes if ( se->is_init() ) buc->generate_facetcrash_events ( se, ctime, gid, econtainer, eventlist, nbe ); // only original edges should be able to generate crashfacet // generate border crashes buc->generate_bordercrash_events ( se, ctime, gid, econtainer, eventlist, nbe ); add_earliest_event ( se ); } void Graph::process_facet_events ( SweepFacet *sf, double ctime, int gid ) { // check for potential crash events in cell gid Bucket *buc = bucketgrid->get_bucket ( gid ); Event *eventlist[MAX_EVENT_LIST]; int nbe = 0; dbgprintf ( 2, "--> generating crash events :\n" ); buc->generate_facetcrash_events ( sf, ctime, gid, econtainer, eventlist, nbe ); dbgprintf ( 2, "--> %d edge events\n", nbe ); buc->generate_bordercrash_events ( sf, ctime, gid, econtainer, eventlist, nbe ); dbgprintf ( 2, "--> %d border events\n", nbe ); add_earliest_event ( sf ); dbgprintf ( 2, "--> listing %d crash events :\n", nbe ); for ( int i = 0; i < nbe; i++ ) { Event *ne = eventlist[i]; ne->print(); SweepEdge *se = ne->get_sweepedge (); se->print(); if ( se->get_earliest_event() == ne ) add_event ( ne ); } } void Graph::add_earliest_event ( SweepObject *so ) { so->print_event_queue (); Event *earliest = so->get_earliest_event(); dbgprintf ( 5, "--> earliest event add\n" ); if ( earliest ) add_event ( earliest ); }