ivp_surbuild_pointsoup.cxx

hl2 source code. Do not use it illegal.

	      int max_index2 = 0;
	      for (int i0 = 0; i0 < point_indizes.len(); i0++){
		int in = int(point_indizes.element_at(i0));
		if (skip_list[in]) goto no_point_skipped;
		IVP_U_Point *p2 = plane->points.element_at( i0 );
		IVP_DOUBLE dist = plane->points.element_at( 0 )->quad_distance_to(p2);
		if (dist > max_dist){
		  max_index = i0;
		  max_dist = dist;
		}
	      }
	      // search point with a maximum distance to max_index
	      max_dist = -1.0;
	      {
		  for (int i1 = 0; i1 < point_indizes.len(); i1++){
		    *skip_point = IVP_TRUE;
		    IVP_U_Point *p2 = plane->points.element_at( i1 );
		    IVP_DOUBLE dist = plane->points.element_at( max_index )->quad_distance_to(p2);
		    if (dist > max_dist){
		      max_index2 = i1;
		      max_dist = dist;
		    }
		  }
	      }
	      IVP_ASSERT( max_dist < qedge_sum);
	      {
		  for (int i2 = 0; i2 < point_indizes.len(); i2++){
		    if (i2 != max_index2 && i2 != max_index) {
		      int in = int(point_indizes.element_at(i2));
		      skip_list[in]++;
		      IVP_ASSERT( use_list[in] );
		      //printf("point removed %i %i\n",in, points->len());

		      break;
		    }
		  }
	      }
	    no_point_skipped:;
	    } // for all facets
	    
	    qh_settempfree(&vertices);
	    IVP_IF(0) {
		IVP_IFDEBUG(IVP_DM_SURBUILD_POINTSOUP) {
		    ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "n_faces: %d\n", plane->points.len());
		    if ( plane->points.len() > 3 ) { //@@@SF: Debug [14.12.1999]
			ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "[Testing/Debug] Qhull : more than 3 points on plane!\n");
		    }
		}
	    }
	}

	IVP_Compact_Ledge *compact_ledge = NULL;
	// --------------------------------------------------
	// convert convex points & planes to polygon template
	// --------------------------------------------------
	if (*skip_point  == IVP_FALSE){
	  IVP_Template_Polygon *templ =  planes_to_template(points, &planes);
	  // -----------------------------------------
	  // convert polygon template to compact ledge
	  // -----------------------------------------
	  compact_ledge = IVP_SurfaceBuilder_Polygon_Convex::convert_template_to_ledge(templ);
	  IVP_IF(1) {
	    IVP_IFDEBUG(IVP_DM_SURBUILD_POINTSOUP) {
	      if ( !compact_ledge ) {
		error_output(templ);
	      }
	    }
	  }
	  P_DELETE(templ);
	}
	
 	// --------------------
	// intermediate cleanup
 	// --------------------
	int i;
	for (i=0; i<planes.len(); i++) {
	    IVP_SurMan_PS_Plane *plane = planes.element_at(i);
	    P_DELETE(plane);
	}

	return compact_ledge;
}

IVP_Compact_Ledge *IVP_SurfaceBuilder_Pointsoup::convert_pointsoup_to_compact_ledge_internal(IVP_U_Vector<IVP_U_Point> *points_in)
{
    IVP_IF(1) {
	IVP_IFDEBUG(IVP_DM_SURBUILD_POINTSOUP) {
	    ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "*** Starting building new convex hull from pointsoup.\n");
	}
    }


    // --------------
    // starting qhull
    // --------------
    int dim = 3;              // dimension of points

    // prepare points
    IVP_U_Vector<IVP_U_Point> points( points_in->len() );
    coordT *points2 = (coordT *)p_calloc(points_in->len() * (dim+1), sizeof(coordT));
    {  // copy vector and remove duplicated points
	IVP_I_Point_VHash point_hash( 1024 ); // very rough estimate
	int d = 0;
	for (int i=0; i<points_in->len(); i++) {
	    IVP_U_Point *p = points_in->element_at(i);
	    IVP_U_Point *found_point = point_hash.find_point(p);
	    if (found_point){
		continue;
	    }
	    point_hash.add_point( p );
	    points.add(p);
	    points2[d+0] = p->k[0];
	    points2[d+1] = p->k[1];
	    points2[d+2] = p->k[2];
	    d += dim;
	}
    }

    int numpoints = points.len();
    char *skip_list = (char *)p_calloc(numpoints, sizeof(char));
    char *use_list = (char *)p_calloc(numpoints, sizeof(char));

    // --------------
    // starting qhull
    // --------------

#if defined(PSXII) || defined(WIN32) || defined(LINUX) || defined(GEKKO)
    FILE *outfile = NULL;   // output from qh_produce_output() use NULL to skip qh_produce_output()
    FILE *errfile = NULL;   // error messages from qhull code
#else
    FILE *outfile = stderr;     // stdout // output from qh_produce_output() use NULL to skip qh_produce_output()
    FILE *errfile = stderr;     // stderr // error messages from qhull code
#endif
    boolT ismalloc = False;    // True if qhull should free points in qh_freeqhull() or reallocation
    
    char flags[250];
    //sprintf(flags, "qhull Qx Pp E7.9e-20"); // "qhull QbB Pp"
    //sprintf(flags, "qhull QJ Pp E7.9e-20"); // "qhull QbB Pp"


    // first loop, try to randomize point 0 until we get an result
    IVP_Compact_Ledge *res = NULL;
    IVP_BOOL try_unjumbled = IVP_TRUE;
    IVP_BOOL qhull_free_flag = IVP_FALSE;
    for ( IVP_DOUBLE random_eps = 1e-12f; random_eps < 0.02f;  ){  
      sprintf(flags, "qhull Qs Pp C-0 W1e-14 E1.0e-18"); // "qhull QbB Pp"
      int exitcode = 0;
      if (try_unjumbled){
	  if (qhull_free_flag)	  qh_freeqhull(!qh_ALL);                   /* free long memory  */
	  exitcode = qh_new_qhull(dim, numpoints, points2, ismalloc, flags, outfile, errfile);
	  qhull_free_flag = IVP_TRUE;
      }
      if ( exitcode || !try_unjumbled) {      
	IVP_IFDEBUG(IVP_DM_SURBUILD_POINTSOUP) {
	  ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "*** Qhull failed. Retrying with different parameters.\n");
	}

	sprintf(flags, "qhull Qs QJ%G C-0 Pp W1e-14 E1.0e-18",random_eps); // "qhull QbB Pp"
	if (qhull_free_flag)	  qh_freeqhull(!qh_ALL);                   /* free long memory  */
	exitcode = qh_new_qhull(dim, numpoints, points2, ismalloc, flags, outfile, errfile);
	qhull_free_flag = IVP_TRUE;
	if (exitcode){
    	    random_eps = ( random_eps + 1e-12f ) * 1.2f;
	    try_unjumbled = IVP_FALSE;
	    continue;
	}
      }      
      
      IVP_BOOL skip_point = IVP_FALSE;
      
      memset( use_list, 0, numpoints);  // reset list
      memset( skip_list, 0, numpoints);  // reset list
      res = try_to_build_convex_ledge_from_qhull_result(&points, &skip_point, skip_list, use_list);

      if (res) //@@CB
      {
	// associate points_in extra data with compact ledge points
	IVP_I_Point_VHash point_hash( 1024 );

	{
	    // add all non duplicate points to the hash for comparison
	    // against the actual compact ledge points (some points may
	    // get discarded by qhull)
	    for(int i = 0; i < points.len(); i++)
	    {
		point_hash.add_point(points.element_at(i));
	    }
	}

	// number of points in the compact ledge
	int compact_ledge_num_points = (res->get_size() / 16) - (res->get_n_triangles()) - 1;

	{
	    // cycle through the compact ledge points, find the corresponding point
	    // in the hash and copy the extra data (hesse_val) value to the compact
	    // point
	    for(int i = 0; i < compact_ledge_num_points; i++)
	    {
		IVP_Compact_Poly_Point* cpp = &((res->get_point_array())[i]);
		IVP_U_Point* associated_point = point_hash.find_point(reinterpret_cast<IVP_U_Point*>(cpp));

		if(associated_point)
		{
		    cpp->hesse_val = associated_point->hesse_val;
		}
	    }
	}

	break;
      }

      {
	int dest = 0;
	for (int x = 0; x < numpoints; x++){
	  if ( use_list[x] && !skip_list[x]){
	    points2[3*dest + 0] = points2[ 3*x + 0];
	    points2[3*dest + 1] = points2[ 3*x + 1];
	    points2[3*dest + 2] = points2[ 3*x + 2];
	    points.elems[dest] = points.elems[x];
	    dest ++;
	  }
	}
	points.n_elems = dest;
	if (numpoints == dest){
    	    random_eps = ( random_eps + 1e-12f ) * 1.2f;
	    try_unjumbled = IVP_FALSE;
	}
	numpoints = dest;
	if (numpoints == 3) {
	    res = convert_pointsoup_to_compact_ledge( &points );
	}	
	if (numpoints <= 3){
	  break;
	}
      }
    }

    // free all the memory
    {
	qh_freeqhull(!qh_ALL);                   /* free long memory  */
	int curlong, totlong;
	qh_memfreeshort( & curlong, &totlong );

	P_DELETE(points2);
	P_FREE(skip_list);
	P_FREE(use_list);
    }
    if (!res){
      IVP_IFDEBUG(IVP_DM_SURBUILD_POINTSOUP) {
	ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "*** IVP_SurfaceBuilder_Pointsoup::convert_pointsoup_to_template_polygon - couldn't build convex hull! Skipping object...\n");
	int i;
	for (i=0; i<points.len(); i++) {
	  //points->element_at(i)->print();
	}
      }

    }
    IVP_IFDEBUG(IVP_DM_SURBUILD_POINTSOUP) {
      ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "*** Done with convex pointsoup.\n\n");
    }
    return res;
}

IVP_Compact_Ledge *IVP_SurfaceBuilder_Pointsoup::single_tri_ledge = NULL;


void IVP_SurfaceBuilder_Pointsoup::cleanup(){
    if (single_tri_ledge){
	ivp_free_aligned( single_tri_ledge );
    }
    single_tri_ledge = NULL;
}

IVP_Compact_Ledge *IVP_SurfaceBuilder_Pointsoup::convert_triangle_to_compace_ledge( IVP_U_Point *p0, IVP_U_Point *p1, IVP_U_Point *p2){
    if ( !single_tri_ledge ){
	IVP_Template_Ledge_Polygon_Soup ledge_templ;
	IVP_Template_Triangle templ_tri;
	
	templ_tri.tri_points[0].set(0,0,1);
	templ_tri.tri_points[1].set(0,1,0);
	templ_tri.tri_points[2].set(0,0,-1);
	
	ledge_templ.ledge_is_open = IVP_FALSE; // create other side automatically
	ledge_templ.n_templ_triangles = 2;
	ledge_templ.templ_triangles_array = &templ_tri;	
	single_tri_ledge = IVP_SurfaceBuilder_Polygon_Convex::convert_templateledgepolygonsoup_to_ledge(&ledge_templ);
    }

    IVP_U_Hesse th;    th.inline_set_vert_to_area_defined_by_three_points(p0,p1,p2);
    if (th.quad_length() < P_DOUBLE_RES) return NULL;

    IVP_Compact_Ledge *cl = (IVP_Compact_Ledge *)ivp_malloc_aligned(single_tri_ledge->get_size(),16);
    memcpy( (void *)cl, (void *)single_tri_ledge, single_tri_ledge->get_size());

    IVP_Compact_Poly_Point *pa = cl->get_point_array();
    pa[0].set(p0);
    pa[1].set(p1);
    pa[2].set(p2);
    return cl;
}


IVP_Compact_Ledge *IVP_SurfaceBuilder_Pointsoup::convert_pointsoup_to_compact_ledge(IVP_U_Vector<IVP_U_Point> *points)
{
  /************************************************
  * FPU mode
  ************************************************/
  //doesnt work with threads !!
#ifdef WIN32
  WORD tmpflag;
  __asm FSTCW tmpflag;

  WORD newFPUflag = tmpflag | 0x0300;
  __asm FLDCW newFPUflag;
#endif
    int n_points = points->len();

    if (n_points <3) return NULL;
    if ( n_points == 3 ) { // special case: 2-dimensional triangles
	return convert_triangle_to_compace_ledge( points->element_at(0), points->element_at(1), points->element_at(2));
    } else { // use QHULL to convert pointsoup
	return IVP_SurfaceBuilder_Pointsoup::convert_pointsoup_to_compact_ledge_internal(points);
    }
#ifdef WIN32
  __asm FLDCW tmpflag;
#endif
}


IVP_Compact_Surface *IVP_SurfaceBuilder_Pointsoup::convert_pointsoup_to_compact_surface(IVP_U_Vector<IVP_U_Point> *points)
{
    IVP_Compact_Surface *compact_surface = NULL;

    IVP_Compact_Ledge *ledge = IVP_SurfaceBuilder_Pointsoup::convert_pointsoup_to_compact_ledge(points);
    if ( ledge ) {
#ifdef DEBUG
		IVP_Compact_Ledge_Solver::check_ledge(ledge);
#endif
	IVP_SurfaceBuilder_Ledge_Soup soup;
	soup.insert_ledge(ledge);
	compact_surface = soup.compile();
    }
    else {
	IVP_IF(1) {
	    IVP_IFDEBUG(IVP_DM_SURBUILD_POINTSOUP) {
		ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "*** IVP_SurfaceBuilder_Pointsoup::convert_pointsoup_to_compact_surface - skipping ledge due to invalid topology\n");
	    }
	}
    }

    return(compact_surface);
}