#pragma ident "@(#)meshifyLocal.c 1.2 97/10/31 SMI"

/*
 * meshifyLocal.c
 *
 *	@(#)meshifyLocal.c 1.8 96/12/20
 *
 * Copyright (c) 1997 by Mike M. Chow - All Rights Reserved 
 *
 *
 * Author: Mike M. Chow
 *
 *      This module contains local meshifying algorithms.
 */


#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include "types.h"
#include "triStrips.h"
#include "zdebug.h"
#include "meshify.h"
#include "meshifyLocal.h"


int MAX_STRIP_LEN = 12;
int TotalVerts = 0;
int TotalRefs = 0;
int TotalTris = 0;

int totalPartVerts = 0;
int totalPartRefs = 0;
int totalPartTris = 0;

int TotalPartStripLen = 0;
int TotalPartStrips = 0;
static Facet *lastFptr;

/* Forward prototypes */
int findBufferRefs(TriStrip *target, HeaderInfo *headerInfo, TriStrip *nextStrip);





/*
 * findBufferRefs
 *
 *      Determines whether each vertex in a strip of a gtmesh ought to be 
 * pushed onto the buffer or whether it is already in the mbuffer (thus a 
 * mesh buffer reference).      
 */

int 
findBufferRefs(TriStrip *target, HeaderInfo *headerInfo, TriStrip *nextStrip)
{
  int i, j;
  int mbrefs = 0;
  int index; 

  /* Go through each vertex of target strip. */
  for (j = 0; j < target->length; j++) {

    zdo6 printf("checking %d...", target->tri[j]);
    zdo6 meshBufferPrint(NULL);

    /* For each vertex, look it up in the mesh buffer. If it is present,
     * store its buffer index. 
     */
    if ((index = mbufferLookup(target->tri[j])) != -1){
      zdo6 printf("Found in buffer, index %d \n", index);
      zdo6 printf("mbref value is %d \n", mbref(index));
      headerInfo->header[j].mbref = index;
      mbrefs++;
    }
    else {
     
      /* If this vertex is not in the buffer, determine whether it ought
       * to be pushed in the buffer (using the next strip's vertices).
       */
      if (nextStrip != NULL) 
	for (i = 0; i < nextStrip->length; i++)
	  if (nextStrip->tri[i] == target->tri[j]) {
	    zdo6 printf("found in next strip, pushing %d \n",
		       target->tri[j]);
	    headerInfo->header[j].mbref = -1;
	    headerInfo->header[j].mbp = 1;
	    mbpush(target->tri[j]);
	  }
    }
  }
  zdo6 printf("%d mbrefs to prev strip. \n", mbrefs);  
  return mbrefs;
}  /* End of findBufferRefs */ 





/*
 * getBufferRefs
 *
 *     Given the sequential strip information of a mesh, finds mesh buffer
 * references for each vertex in the mesh.
 */
	  
void
getBufferRefs(GTMesh *gtmesh)
{
  TriStrip *strip, *prevStrip;

  prevStrip = NULL;
  for (strip = gtmesh->triStrips->strips; strip != NULL; strip = strip->next){
    HeaderInfo *headerInfo;
    TriStrip *nextStrip;
    
    headerInfo = headerInfoCreate();
    nextStrip = strip->next;
    totalPartVerts += strip->length;
    totalPartTris += strip->length - 2;
				       
    zdo6 printf("total part tris so far %d\n", totalPartTris);


    /* Each strip we call findBufferRefs() to figure out whether
     * each vertex in the strip ought to be pushed onto the mbuffer.
     */
    if (prevStrip != NULL) {
      int matches;
      int refs;

	  matches = matchStrips(strip, prevStrip);
	  zdo6 printf("Mesh buffer matches: %d.\n", 
		     matches);
	  refs = findBufferRefs(strip, headerInfo, nextStrip);
	  totalPartRefs += refs;
      }
      else {

	/* First Strip: Push onto mesh buffer any vertex that will be used by
	 the next strip. */
	int i, j;
	
	zdo6 printf("comparing 1st strip with nextStrip (leng %d)\n", 
		    nextStrip->length);

	if (nextStrip != NULL) 
	  for (j = 0; j < strip->length; j++) 
	    for(i = 0; i < nextStrip->length; i++){
	      zdo6 printf("Comparing %d with %d \n", 
			  strip->tri[j], nextStrip->tri[i]);

	      /* A match means we need to push this vertex onto the buffer. */
	      if (strip->tri[j] == nextStrip->tri[i]){
		zdo6 printf("Match, push %d \n", strip->tri[j]);
		mbpush(strip->tri[j]);
		headerInfo->header[j].mbp = 1;
		break;
	      }
	    }
	  }

      prevStrip = strip;
      headerInfosAdd(&gtmesh->headers, headerInfo);
  }
}  /* End of getBufferRefs*/



void
resetMeshifyTimeStamp()
{
  gettimeofday(&timeStamp, NULL);
  /* Make sure timestamp is unique. */
  timeStamp.tv_sec++;
}



void
resetNeighborAdjacency(Part *currPart, Facet *fptr)
{
  Edge *edge;
  int i;

  /* For each edge of this facet, get adjacent facet and test it
   * for non-visitedness.  Then minus its adjacency as well change
   * the edge to hard. */

  for (i = 0; i < fptr->numVerts; i++){
    Facet *look1Fptr;

    edge = fptr->edges[i];

    /* Get adjacent facet */
    if (edge->f1 == fptr)
      look1Fptr = edge->f2;
    else
      look1Fptr = edge->f1;

    
    if ((look1Fptr != NULL) && (look1Fptr->timeStamp != timeStamp.tv_sec)){
      look1Fptr->adjacencyCnt--;
      if (look1Fptr->adjacencyCnt == 2){
	zdo6 printf("Meshifier adding a corner facet.\n");
	flistAddFacet(&(currPart->cornerFacets), look1Fptr);
      }
      edge->hard = 1;
      look1Fptr->hasHardEdge = 1;
      currPart->hardEdgeCount++;
    }
  }
}  /* End of resetNeighborAdjacency*/




/*
 * stripFacetsResetNbrAdj
 *
 *     Resets neighbor adjacencies for a list of facets.
 */

void
stripFacetsResetNbrAdj(FacetList *stripFacets)
{
  FacetList *flptr;
  
  for (flptr = stripFacets; flptr != NULL; flptr = flptr->next)
    {
      Facet *fptr2;
      
      if (flptr->current != NULL){
	fptr2 = flptr->current;
	resetNeighborAdjacency(fptr2->owner, fptr2);
      }
    }
}  /* End of stripFacetsResetNbrAdj*/


#define STRIP_LEN_LOOKAHEAD 4

void
stripLengthLookahead(MeshRegion *currRegion, 
		     Facet *startFacet, Edge *startEdge, int distance, 
		     TriStrip *startStrip, 
		     int *currStripLen, int maxStripLen)
{
  int i;
  Facet *fptr;
  Edge *eptr;
  FacetList *flptr, *stripFacets;
  int totalMatches, bestMatches;
  int totalStripLen, totalStrips;
  TriStrip *triStrip, *prevStrip;
  Part *currPart;
  int cnt;

  fptr = startFacet;
  eptr = startEdge;
  totalMatches = 0;
  bestMatches = 0;
  totalStripLen = 0;
  totalStrips = 0;
  currPart = fptr->owner;
  prevStrip = startStrip;

  if (prevStrip != NULL)
    totalStrips++;

  for (i = 0; ((i < distance) && (fptr != NULL)); i++){
    
    stripFacets = flistNewNode();
    zdebugOff(
    triStrip = getTriStrip(currPart, currRegion, fptr, 
			   eptr, &lastFptr, 26, 1, &stripFacets);
    )


    /* Find the vertex matches between previous strip */
    if (prevStrip != NULL){
      int matches;

      matches = matchStrips(triStrip, prevStrip);
      zdo6 printf("lookahead %d strip len %d matches %d \n",
		 i, triStrip->length, matches);
       if (matches > bestMatches)
	bestMatches = matches;
      totalMatches += matches;
    }

    /* Free previous strip, if *not* the first strip (which is given to us)
       and prevStrip is not NULL */
    if ((i > 0) && (prevStrip != NULL)){
      free(prevStrip->tri);
    }
    prevStrip = triStrip;
    totalStripLen += triStrip->length;
    totalStrips++;

    /* Pick the next facet and edge to start. */
    meshPickNextEdge(currPart, currRegion, fptr, &fptr, &eptr, triStrip);
    
    /* Try alternating direction */
    if (fptr == NULL)
      meshPickNextEdge(currPart, currRegion, lastFptr, &fptr, &eptr, triStrip);

    cnt = 0;
    /* Reset time stamps of previous strip */
   for (flptr = stripFacets; flptr != NULL; flptr = flptr->next)
      {
	Facet *fptr2;

	if (flptr->current != NULL){
	  fptr2 = flptr->current;
	  cnt++;
	  /* Reset timestamp */
	  fptr2->timeStamp = 0;
	}
      }
   zdo6 printf("Unmarked %d facets \n", cnt);
   
   /* Get rid of current facetlist */
   flistDestroy(stripFacets);
  }

  if (totalStrips > 1) {
    *currStripLen = (totalMatches / (totalStrips - 1)) * 2;
    zdo6 printf("striplen lookahead got ave matches %d dist %d ave len %d \n",
	   *currStripLen, distance, *currStripLen);
  }

  if (*currStripLen < maxStripLen){
    zdo6 printf("striplen too short, use default %d \n", maxStripLen);
    *currStripLen = maxStripLen;
  }

}  /* End of stripLengthLookahead*/





    
/*
 * findMeshLocal
 *
 *      Given a starting facet, find a good generalized triangle mesh. 
 *
 * This local algorithm finds a triangle strip from the starting facet;
 * Next, it picks a new edge to continue the mesh (maximizing mesh buffer
 * reuse).  It continues finding strips until there is no more strip to
 * continue.
 *
 * The flag, testing, is either 0 or 1, telling findMeshLocal whether
 * to fake meshify or not (fake means we are doing shadow mesh lookaheads
 * and there is no need for actually building the gtmesh).  Along with 
 * testing is the return values, meshWidth and meshHeight, for scoring
 * the resulting mesh.
 */

void *
findMeshLocal(MeshRegion *currRegion, 
	      Facet *startFptr, Edge *startEdge,  MeshInfo *minfo, 
	      int testing, int *meshWidth, int *meshHeight)
{
    Facet *fptr; /* Facet ptr */
    Edge *eptr;  /* Edge ptr */
    TriStrip *triStrip, *prevStrip, *strip;
    int cnt;
    GTMesh *gtmesh;
    Part *currPart;
    int currStripLen;
    FacetList *stripFacets, *meshFacets, *flptr;
    int totalStrips = 0;
    int totalMatches = 0;
    int i;

    /* Starting facet */
    fptr = startFptr;
    currPart = fptr->owner;

    if (startEdge == NULL)
      eptr = fptr->edges[0];
    else
      eptr = startEdge;

    lastFptr = NULL;
    cnt = 0;

    prevStrip = NULL;

    stripFacets = NULL;
    meshFacets = flistNewNode();

    if (!testing){
      /* Create a new gtmesh. */
      gtmesh = gtmeshCreate();
      gtmesh->varray = fptr->owner->obj->varray;
    }

    currStripLen = MAX_STRIP_LEN;

    /* While there is more facets, keep adding triangles to the mesh. */

    while ((fptr != NULL) &&
	   (cnt++ < 1000000)){
      Facet *lastFptr;

      zdo6 printf("Local: Get tristrip starting from facet %x edge %x .\n",
		 fptr, eptr);
      
      if (0){
	if ((cnt % STRIP_LEN_LOOKAHEAD) == 0) {
	  stripLengthLookahead(currRegion, fptr, eptr, STRIP_LEN_LOOKAHEAD,
			       prevStrip,
			       &currStripLen, MAX_STRIP_LEN);
	  if (currStripLen == 0){
	    zdo printf("stripLookahead return 0; Breaking out!\n");
	    break;
	  }
	}
      }

      /* Get rid of the previous stripFacets */
      if (stripFacets != NULL)
	flistDestroy(stripFacets);

      stripFacets = flistNewNode();
      /* Get the strip starting from this facet. */
      zdebugOff(
		triStrip = getTriStrip(fptr->owner, currRegion, fptr, 
				       eptr, &lastFptr, currStripLen, 
				       1, &stripFacets);
		)
	if (triStrip == NULL)
	  break;

	if (testing) {

	  /* Add stripFacets to meshFacets */
	  for (flptr = stripFacets; flptr != NULL; flptr = flptr->next)
	    {
	      Facet *fptr2;

	      if (flptr->current != NULL){
		fptr2 = flptr->current;
		flistAddFacet(&meshFacets, fptr2);
	      }
	    }

	  /* Increment total strips */
	  totalStrips++;

	  /* Score the triStrip with prevStrip */
	  if (prevStrip != NULL){
	    int matches;
	    
	    matches = matchStrips(triStrip, prevStrip);
	    totalMatches += matches;
	  }
	} /* if (testing) ... */


	if (!testing){
	  resetNeighborAdjacency(currPart, fptr);
	  resetNeighborAdjacency(currPart, lastFptr);

	  /* For the first strip, also change boundary facets' adjacency */
	  if (prevStrip == NULL) {
	    stripFacetsResetNbrAdj(stripFacets);
	  }
	  
	  gtmesh->triStrips->triCnt += triStrip->triCnt - 2;

	  TotalPartStripLen += triStrip->triCnt;
	  TotalPartStrips++;
	  
	  triStripsAddStrip(gtmesh->triStrips, triStrip);
	  zdo6 triStripPrint(triStrip, fptr->owner->obj->varray);
	}

	/* Pick the next facet and edge to start. */
	meshPickNextEdge(currPart, currRegion, fptr, &fptr, &eptr, triStrip);

	/* Try alternating direction */
	if (fptr == NULL)
	  meshPickNextEdge(currPart, currRegion, lastFptr, &fptr, &eptr, triStrip);

	if ((prevStrip != NULL) && (testing)){
	  free(prevStrip->tri);
	}

	prevStrip = triStrip;

    }


    if (testing) {

    /* Unmark all the meshFacets */
      for (flptr = meshFacets; flptr != NULL; flptr = flptr->next)
	{
	  Facet *fptr2;

	  if (flptr->current != NULL){
	    fptr2 = flptr->current;
	    fptr2->timeStamp = 0;
	  }
	}

      /* Return mesh width and height */
      *meshWidth = totalMatches / totalStrips;
      *meshHeight = totalStrips;
    }
	  
    if (!testing){

      /* For the last strip, also change boundary facets' adjacency */
      if (prevStrip != NULL) {
	stripFacetsResetNbrAdj(stripFacets);
      }
      /* Find the mesh buffer references, given the strips */
      getBufferRefs(gtmesh);
      
      /* Add the gtmesh to meshInfo object */
      meshInfoAddMesh(minfo, gtmesh);
    }
    return NULL;
}  /* End of findMeshLocal*/
	




  
/*
 * meshifyLocal
 *
 *     Given a part, find all the gtmeshes in this part using the
 * local algorithm that finds adjacent facets to start meshifying.
 * This results in average of 30% to 40% reuse of the old vertices
 * from the mesh buffer.  A more global algorithm can achieve better
 * results.
 *
 */

void 
meshifyLocal(Part *part, int maxStripLen)
{
    Facet *fptr; /* Facet ptr */
    Edge *eptr;  /* Edge ptr */
    TriStrip *triStrip;
    LinkedList *lptr;
    int shadowMeshLookaheads = -1;

    MAX_STRIP_LEN = maxStripLen;

    /* Init counters */
    totalPartRefs = 0;
    totalPartVerts = 0;
    totalPartTris = 0;

    TotalPartStrips = 0;
    TotalPartStripLen = 0;

    for (lptr = part->regions; lptr != NULL; lptr = lptr->next){
      MeshRegion *region;

      region = (MeshRegion *) lptr->current;

      if (region != NULL) {

	zdo6 printf("meshifying region %x\n", region);

	/* Create mesh storage */
	region->meshInfo = meshInfoCreate();
	
	/* Make sure timestamp is unique. */
	timeStamp.tv_sec++;
	region->meshInfo->timeStamp.tv_sec = timeStamp.tv_sec;

	fptr = NULL;

	/* Pick the first facet and edge to start. */
	pickNextEdge(part, region, &fptr, &eptr, shadowMeshLookaheads);

	if (fptr == NULL) 
	  printf("meshify local's pick edge returned NULL \n");

	/* While there is more facets left, keep meshifying. */
	zdebugOn(
		 while (fptr != NULL){
		   /* No more ?*/
		   if (eptr == NULL)
		     break;

		   /* Meshify from the current facet and edge. */
		   findMeshLocal(region, fptr, eptr, region->meshInfo, 0, NULL, NULL);

		   /* Pick another facet and edge. */
		   pickNextEdge(part, region, &fptr, &eptr,
			        shadowMeshLookaheads);
		 }
		 fflush(stdout);
		 )

	  }
    }
      /* Do some statistics. */
    TotalVerts += totalPartVerts;
    TotalRefs += totalPartRefs;
    TotalTris += totalPartTris;

    zdo6 printf("Mesh ave strip len %f.\n", 
	   (float) TotalPartStripLen / (float) TotalPartStrips); 
	   
    zdo6 printf("Part %s tris %d, verts %d, mbrefs %d,\n %2.2f percent reuse, %2.3f verts/tris.\n",
	       part->name, totalPartTris, totalPartVerts, totalPartRefs, 
	   100.0 * ((float)totalPartRefs/(float)totalPartVerts),
	   ((float)(totalPartVerts - totalPartRefs)/(float)totalPartTris));

    zdo6 printf("Total tris %d, verts %d, mbrefs %d, %2.2f percent reuse, %2.3f verts/tris.\n\n",
	   TotalTris, TotalVerts, 
	   TotalRefs, 100.0 * ((float)TotalRefs/(float)TotalVerts),
	   ((float)(TotalVerts - TotalRefs)/(float)TotalTris));

}  /* End of meshifyLocal */
	
 /* End of meshifyLocal.c*/

