merge.c

关于网格剖分的

	ridge->tested= True;
	ridge->nonconvex= False;
      }else if (neighbor->visitid != qh visit_id) {
        ridge->tested= True;
        ridge->nonconvex= False;
	neighbor->seen= True;      /* only one ridge is marked nonconvex */
	if (qh_test_appendmerge (facet, neighbor))
	  ridge->nonconvex= True;
      }
    }
  }
  nummerges= qh_setsize (qh facet_mergeset);
  if (qh ANGLEmerge)
    qsort(SETaddr_(qh facet_mergeset, mergeT), nummerges,sizeof(mergeT *),qh_compareangle);
  else
    qsort(SETaddr_(qh facet_mergeset, mergeT), nummerges,sizeof(mergeT *),qh_comparemerge);
  if (qh POSTmerging) {
    zadd_(Zmergesettot2, nummerges);
  }else {
    zadd_(Zmergesettot, nummerges);
    zmax_(Zmergesetmax, nummerges);
  }
  trace2((qh ferr, "qh_getmergeset: %d merges found\n", nummerges));
} /* getmergeset */


/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="getmergeset_initial">-</a>
  
  qh_getmergeset_initial( facetlist )
    determine initial qh.facet_mergeset for facets
    tests all facet/neighbor pairs on facetlist

  returns:
    sorted qh.facet_mergeset with nonconvex ridges
    sets facet->tested, ridge->tested, and ridge->nonconvex

  notes:
    uses visit_id, assumes ridge->nonconvex is False

  see:
    qh_getmergeset()

  design:
    for each facet on facetlist
      for each untested neighbor of facet
        test facet and neighbor for convexity
        if non-convex
          append merge to qh.facet_mergeset
          mark one of the ridges as nonconvex
    sort qh.facet_mergeset by angle
*/
void qh_getmergeset_initial (facetT *facetlist) {
  facetT *facet, *neighbor, **neighborp;
  ridgeT *ridge, **ridgep;
  int nummerges;

  qh visit_id++;
  FORALLfacet_(facetlist) {
    facet->visitid= qh visit_id;
    facet->tested= True;
    FOREACHneighbor_(facet) {
      if (neighbor->visitid != qh visit_id) {
        if (qh_test_appendmerge (facet, neighbor)) {
          FOREACHridge_(neighbor->ridges) {
            if (facet == otherfacet_(ridge, neighbor)) {
              ridge->nonconvex= True;
              break;	/* only one ridge is marked nonconvex */
            }
          }
        }
      }
    }
    FOREACHridge_(facet->ridges)
      ridge->tested= True;
  }
  nummerges= qh_setsize (qh facet_mergeset);
  if (qh ANGLEmerge)
    qsort(SETaddr_(qh facet_mergeset, mergeT), nummerges,sizeof(mergeT *),qh_compareangle);
  else
    qsort(SETaddr_(qh facet_mergeset, mergeT), nummerges,sizeof(mergeT *),qh_comparemerge);
  if (qh POSTmerging) {
    zadd_(Zmergeinittot2, nummerges);
  }else {
    zadd_(Zmergeinittot, nummerges);
    zmax_(Zmergeinitmax, nummerges);
  }
  trace2((qh ferr, "qh_getmergeset_initial: %d merges found\n", nummerges));
} /* getmergeset_initial */


/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="hashridge">-</a>
  
  qh_hashridge( hashtable, hashsize, ridge, oldvertex )
    add ridge to hashtable without oldvertex

  notes:
    assumes hashtable is large enough

  design:
    determine hash value for ridge without oldvertex
    find next empty slot for ridge
*/
void qh_hashridge (setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex) {
  int hash;
  ridgeT *ridgeA;

  hash= (int)qh_gethash (hashsize, ridge->vertices, qh hull_dim-1, 0, oldvertex);
  while (True) {
    if (!(ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
      SETelem_(hashtable, hash)= ridge;
      break;
    }else if (ridgeA == ridge)
      break;
    if (++hash == hashsize)
      hash= 0;
  }
} /* hashridge */


/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="hashridge_find">-</a>
  
  qh_hashridge_find( hashtable, hashsize, ridge, vertex, oldvertex, hashslot )
    returns matching ridge without oldvertex in hashtable 
      for ridge without vertex
    if oldvertex is NULL 
      matches with any one skip

  returns:
    matching ridge or NULL
    if no match,
      if ridge already in   table
        hashslot= -1 
      else 
        hashslot= next NULL index
        
  notes:
    assumes hashtable is large enough
    can't match ridge to itself

  design:
    get hash value for ridge without vertex
    for each hashslot
      return match if ridge matches ridgeA without oldvertex
*/
ridgeT *qh_hashridge_find (setT *hashtable, int hashsize, ridgeT *ridge, 
              vertexT *vertex, vertexT *oldvertex, int *hashslot) {
  int hash;
  ridgeT *ridgeA;

  *hashslot= 0;
  zinc_(Zhashridge);
  hash= (int)qh_gethash (hashsize, ridge->vertices, qh hull_dim-1, 0, vertex);
  while ((ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
    if (ridgeA == ridge)
      *hashslot= -1;      
    else {
      zinc_(Zhashridgetest);
      if (qh_setequal_except (ridge->vertices, vertex, ridgeA->vertices, oldvertex))
        return ridgeA;
    }
    if (++hash == hashsize)
      hash= 0;
  }
  if (!*hashslot)
    *hashslot= hash;
  return NULL;
} /* hashridge_find */


/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="makeridges">-</a>
  
  qh_makeridges( facet )
    creates explicit ridges between simplicial facets

  returns:
    facet with ridges and without qh_MERGEridge
    ->simplicial is False
  
  notes:
    allows qh_MERGEridge flag
    uses existing ridges
    duplicate neighbors ok if ridges already exist (qh_mergecycle_ridges)

  see:
    qh_mergecycle_ridges()

  design:
    look for qh_MERGEridge neighbors
    mark neighbors that already have ridges
    for each unprocessed neighbor of facet    
      create a ridge for neighbor and facet
    if any qh_MERGEridge neighbors
      delete qh_MERGEridge flags (already handled by qh_mark_dupridges)
*/
void qh_makeridges(facetT *facet) {
  facetT *neighbor, **neighborp;
  ridgeT *ridge, **ridgep;
  int neighbor_i, neighbor_n;
  boolT toporient, mergeridge= False;
  
  if (!facet->simplicial)
    return;
  trace4((qh ferr, "qh_makeridges: make ridges for f%d\n", facet->id));
  facet->simplicial= False;
  FOREACHneighbor_(facet) {
    if (neighbor == qh_MERGEridge)
      mergeridge= True;
    else
      neighbor->seen= False;
  }
  FOREACHridge_(facet->ridges)
    otherfacet_(ridge, facet)->seen= True;
  FOREACHneighbor_i_(facet) {
    if (neighbor == qh_MERGEridge)
      continue;  /* fixed by qh_mark_dupridges */
    else if (!neighbor->seen) {  /* no current ridges */
      ridge= qh_newridge();
      ridge->vertices= qh_setnew_delnthsorted (facet->vertices, qh hull_dim,
					                  neighbor_i, 0);
      toporient= facet->toporient ^ (neighbor_i & 0x1);
      if (toporient) {
        ridge->top= facet;
        ridge->bottom= neighbor;
      }else {
        ridge->top= neighbor;
        ridge->bottom= facet;
      }
#if 0 /* this also works */
      flip= (facet->toporient ^ neighbor->toporient)^(skip1 & 0x1) ^ (skip2 & 0x1);
      if (facet->toporient ^ (skip1 & 0x1) ^ flip) {
        ridge->top= neighbor;
        ridge->bottom= facet;
      }else {
        ridge->top= facet;
        ridge->bottom= neighbor;
      }
#endif
      qh_setappend(&(facet->ridges), ridge);
      qh_setappend(&(neighbor->ridges), ridge);
    }
  }
  if (mergeridge) {
    while (qh_setdel (facet->neighbors, qh_MERGEridge))
      ; /* delete each one */
  }
} /* makeridges */


/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="mark_dupridges">-</a>
  
  qh_mark_dupridges( facetlist )
    add duplicated ridges to qh.facet_mergeset
    facet->dupridge is true

  returns:
    duplicate ridges on qh.facet_mergeset
    ->mergeridge/->mergeridge2 set
    duplicate ridges marked by qh_MERGEridge and both sides facet->dupridge
    no MERGEridges in neighbor sets
    
  notes:
    duplicate ridges occur when the horizon is pinched,
        i.e. a subridge occurs in more than two horizon   ridges.
    could rename vertices that pinch the horizon
    uses qh.visit_id

  design:
    for all facets on facetlist
      if facet contains a duplicate ridge
        for each neighbor of facet
          if neighbor marked qh_MERGEridge (one side of the merge)
            set facet->mergeridge      
          else
            if neighbor contains a duplicate ridge 
            and the back link is qh_MERGEridge
              append duplicate ridge to qh.facet_mergeset
   for each duplicate ridge
     make ridge sets in preparation for merging
     remove qh_MERGEridge from neighbor set
   for each duplicate ridge
     restore the missing neighbor from the neighbor set that was qh_MERGEridge
     add the missing ridge for this neighbor
*/
void qh_mark_dupridges(facetT *facetlist) {
  facetT *facet, *neighbor, **neighborp;
  int nummerge=0;
  mergeT *merge, **mergep;
  

  trace4((qh ferr, "qh_mark_dupridges: identify duplicate ridges\n"));  
  FORALLfacet_(facetlist) {
    if (facet->dupridge) {
      FOREACHneighbor_(facet) {
        if (neighbor == qh_MERGEridge) {
	  facet->mergeridge= True;
	  continue;
	}
        if (neighbor->dupridge
	&& !qh_setin (neighbor->neighbors, facet)) { /* qh_MERGEridge */
	  qh_appendmergeset (facet, neighbor, MRGridge, NULL);
	  facet->mergeridge2= True;
	  facet->mergeridge= True;
	  nummerge++;
	}
      }
    }
  }
  if (!nummerge)
    return;
  FORALLfacet_(facetlist) {            /* gets rid of qh_MERGEridge */
    if (facet->mergeridge && !facet->mergeridge2)   
      qh_makeridges (facet);
  }
  FOREACHmerge_(qh facet_mergeset) {   /* restore the missing neighbors */
    if (merge->type == MRGridge) {
      qh_setappend (&merge->facet2->neighbors, merge->facet1);
      qh_makeridges (merge->facet1);   /* and the missing ridges */
    }
  }
  trace1((qh ferr, "qh_mark_dupridges: found %d duplicated ridges\n", 
                nummerge));
} /* mark_dupridges */

/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="maydropneighbor">-</a>
  
  qh_maydropneighbor( facet )
    drop neighbor relationship if no ridge between facet and neighbor

  returns:
    neighbor sets updated
    appends degenerate facets to qh.facet_mergeset
  
  notes:
    won't cause redundant facets since vertex inclusion is the same
    may drop vertex and neighbor if no ridge
    uses qh.visit_id

  design:
    visit all neighbors with ridges
    for each unvisited neighbor of facet
      delete neighbor and facet from the neighbor sets
      if neighbor becomes degenerate
        append neighbor to qh.degen_mergeset
    if facet is degenerate
      append facet to qh.degen_mergeset
*/
void qh_maydropneighbor (facetT *facet) {
  ridgeT *ridge, **ridgep;
  realT angledegen= qh_ANGLEdegen;
  facetT *neighbor, **neighborp;

  qh visit_id++;
  trace4((qh ferr, "qh_maydropneighbor: test f%d for no ridges to a neighbor\n",
	  facet->id));
  FOREACHridge_(facet->ridges) {
    ridge->top->visitid= qh visit_id;
    ridge->bottom->visitid= qh visit_id;
  }
  FOREACHneighbor_(facet) {
    if (neighbor->visitid != qh visit_id) {
      trace0((qh ferr, "qh_maydropneighbor: facets f%d and f%d are no longer neighbors during p%d\n",
	    facet->id, neighbor->id, qh furthest_id));
      zinc_(Zdropneighbor);
      qh_setdel (facet->neighbors, neighbor);
      neighborp--;  /* repeat, deleted a neighbor */
      qh_setdel (neighbor->neighbors, facet);
      if (qh_setsize (neighbor->neighbors) < qh hull_dim) {
        zinc_(Zdropdegen);
        qh_appendmergeset (neighbor, neighbor, MRGdegen, &angledegen);
        trace2((qh ferr, "qh_maydropneighbors: f%d is degenerate.\n", neighbor->id));
      }
    }
  }
  if (qh_setsize (facet->neighbors) < qh hull_dim) {
    zinc_(Zdropdegen);
    qh_appendmergeset (facet, facet, MRGdegen, &angledegen);
    trace2((qh ferr, "qh_maydropneighbors: f%d is degenerate.\n", facet->id));
  }
} /* maydropneighbor */