ivp_surbuild_pointsoup.cxx

hl2 source code. Do not use it illegal.

// Copyright (C) Ipion Software GmbH 1999-2000. All rights reserved.

// IVP_EXPORT_PUBLIC
#include <ivp_physics.hxx>

#include <qhull_a.hxx>

#include <ivp_betterdebugmanager.hxx>
#include <ivp_templates_intern.hxx>
#include <ivu_hash.hxx>
#include <ivp_i_point_vhash.hxx>
#include <ivp_surbuild_polygon_convex.hxx>
#include <ivp_compact_ledge.hxx>
#include <ivp_compact_ledge_solver.hxx>
#include <ivp_surbuild_ledge_soup.hxx>
#include <ivp_surbuild_pointsoup.hxx>

#if defined(WIN32) && !defined(_XBOX)
#include "wtypes.h"
#elif defined(_XBOX)
#	ifndef WINVER
#		define WINVER 0x0500
#	endif
#	ifndef _X86_
#		define _X86_
#	endif  /* _X86_ */
#	include <excpt.h>
#	include <stdarg.h>
#	include <windef.h>
#endif

int IVP_SurfaceBuilder_Pointsoup::get_offset_from_pointlist(IVP_Template_Point *points, int length, IVP_U_Point *point)
{
    int	i;

    for (i=0; i<length; i++) {

	if (
	    points[i].k[0] == point->k[0] &&
	    points[i].k[1] == point->k[1] &&
	    points[i].k[2] == point->k[2])
	{
	    return(i);
	}

    }
	
    return(0);
}


int IVP_SurfaceBuilder_Pointsoup::get_offset_from_lineslist(IVP_Template_Line *lines,
							    int length,
							    int pointnr1,
							    int pointnr2,
							    char *reverse)
{
    int	   x;

    for (x=0; x<length; x++) {
	if ( 
	     (pointnr1 == lines[x].p[0])
	  && (pointnr2 == lines[x].p[1])
	) {
	    *reverse = 0;
	    return((ushort)x);
	}
	if ( 
	     (pointnr1 == lines[x].p[1])
	  && (pointnr2 == lines[x].p[0])
	) {
	    *reverse = 1;
	    return(x);
	}
    }
	
    return(0);
}


struct point_hash_key2 {
    ushort offset_point1;
    ushort offset_point2;
};

IVP_Template_Polygon *IVP_SurfaceBuilder_Pointsoup::planes_to_template(IVP_U_Vector<IVP_U_Point> *points,
								       IVP_U_Vector<IVP_SurMan_PS_Plane> *planes)
{
    IVP_Template_Polygon *templ = new IVP_Template_Polygon();

    // ------------------------------------------------------------------------
    // Build Pointlist:
    // extract all points and add them to our
    // own pointlist. Merge all points within a certain distance (see also
    // 'get_offset_from_pointlist(...)'.

    int object_vertex_count = points->len();

    templ->n_points  = 0;
    templ->points   = new IVP_Template_Point[object_vertex_count];

    int x;
    for (x=0; x < object_vertex_count; x++) {

	IVP_U_Point *point = points->element_at(x);

	// check if point (or at least one extremely close to it) is already in list
	if ( get_offset_from_pointlist(templ->points, templ->n_points, point) == 0 ) {

	    // if not, insert it into our point list
	    templ->points[templ->n_points].set(point);
	    templ->n_points++;
	}

    }

    // At this point we have the pointlist completed (still missing are the linelist 
    // and the surfacelist).
    

    // ------------------------------------------------------------------------
    // Build Lineslist:

    IVP_Hash *lines_hash = new IVP_Hash(points->len()*2, 2*sizeof(ushort), 0);
    IVP_U_Vector<struct point_hash_key2> lines_vector;

    int face_count = planes->len();

    templ->n_surfaces = face_count;
    templ->surfaces = new IVP_Template_Surface[face_count];

    templ->n_lines = 0;

    for (x=0; x<face_count; x++) {

	IVP_SurMan_PS_Plane *plane = planes->element_at(x);
	
	int face_vertex_count = plane->points.len();

	// number of lines per polygon equals number of points per polygon
	templ->surfaces[x].n_lines = face_vertex_count;

	for (int pointnr=0; pointnr<face_vertex_count; pointnr++) {

	    IVP_U_Point *point;
	    
	    ushort offset_point1, offset_point2;

	    point = plane->points.element_at(pointnr);
	    offset_point1 = get_offset_from_pointlist(templ->points, templ->n_points, point);

	    if ( pointnr+1 == face_vertex_count ) {
		point = plane->points.element_at(0);
	    }
	    else {
		point = plane->points.element_at(pointnr+1);
	    }
	    offset_point2 = get_offset_from_pointlist(templ->points, templ->n_points, point);

	    // in 'offset_point1/2' we now have the points that build the current line...

	    // construct a unique hash key for the line (independent of pointoffset order)
	    struct point_hash_key2 phk;
	    if ( offset_point2 < offset_point1 ) {
		phk.offset_point1 = offset_point1;
		phk.offset_point2 = offset_point2;
	    }
	    else {
		phk.offset_point1 = offset_point2;
		phk.offset_point2 = offset_point1;
	    }

	    // add line to hash table (if not already there)
	    if ( lines_hash->find((char *)&phk) == 0 ) {
		lines_hash->add((char *)&phk, (void *)1);

		struct point_hash_key2 *nphk = (struct point_hash_key2 *)p_calloc(1, sizeof(struct point_hash_key2));
		nphk->offset_point1 = offset_point1;
		nphk->offset_point2 = offset_point2;
		lines_vector.add(nphk);

		templ->n_lines++;
	    }

	}

    }

    P_DELETE(lines_hash);
    
    // now we have all lines (without duplicates) in our 'lines_vector' list and just
    // need to copy the data to the IVP_Template_Line structure.

    templ->lines = new IVP_Template_Line[templ->n_lines];
    for (x=0; x<lines_vector.len(); x++) {
	struct point_hash_key2 *pphk = lines_vector.element_at(x);
	templ->lines[x].p[0] = pphk->offset_point1;
	templ->lines[x].p[1] = pphk->offset_point2;
	P_FREE(pphk);
    }

    // At this point we have the pointlist completed and the lineslist filled
    // with the appropriate linepoint indizes (still missing are major parts of 
    // the surfacelist and the linelist's 'left' and 'right' surface indizes)


    // ------------------------------------------------------------------------
    // Build Surfacelist:
    // NOTE: the surfacelist has already been (partially) initialized above!

    for (x=0; x<face_count; x++) {

	IVP_SurMan_PS_Plane *plane;
	
	plane = planes->element_at(x);

	templ->surfaces[x].templ_poly    = templ;
	templ->surfaces[x].normal.set(plane);
	templ->surfaces[x].lines         = (ushort *)p_calloc(templ->surfaces[x].n_lines, sizeof(ushort));
	templ->surfaces[x].revert_line   = new char[templ->surfaces[x].n_lines];


	int punktezahl = templ->surfaces[x].n_lines;
	ushort *offset_points = (ushort *)p_calloc(punktezahl+1, sizeof(ushort));

	int y;
	for (y=0; y<punktezahl; y++) {

	    IVP_U_Point *point;

	    point = plane->points.element_at(y);
	    offset_points[y] = get_offset_from_pointlist(templ->points, templ->n_points, point);

	}
	offset_points[y] = offset_points[0];


	// number of points equals number of lines!
	for (int pointnr=0; pointnr<punktezahl; pointnr++) {

	    char reverse;
	    int line_index = get_offset_from_lineslist(templ->lines, templ->n_lines,
						       offset_points[pointnr], offset_points[pointnr+1], &reverse);
	    templ->surfaces[x].lines[pointnr] = line_index;
	    templ->surfaces[x].revert_line[pointnr] = ((reverse*(-1))+1);

	}

	P_FREE(offset_points);

    }

    return(templ);
}

IVP_DOUBLE IVP_SurMan_PS_Plane::get_area_size(){
  IVP_DOUBLE sum = 0.0;
  IVP_U_Point *p0 = points.element_at(0);
  for (int i = 0; i< points.len(); i++){
    int in = (i+1) % points.len();
    IVP_U_Point *a = points.element_at(i);
    IVP_U_Point *b = points.element_at(in);
    IVP_U_Point diff0; diff0.subtract( b, a);
    IVP_U_Point diff1; diff1.subtract( a, p0);
    IVP_U_Point cross; cross.calc_cross_product( &diff0, &diff1);
    sum += cross.dot_product( this );
  }
  return sum;
}

IVP_DOUBLE IVP_SurMan_PS_Plane::get_qlen_of_all_edges(){
  IVP_DOUBLE sum = 0.0;
  for (int i = 0; i< points.len(); i++){
    int in = (i+1) % points.len();
    IVP_U_Point *a = points.element_at(i);
    IVP_U_Point *b = points.element_at(in);
    sum += a->quad_distance_to(b);
  }
  return sum;
}


void IVP_SurfaceBuilder_Pointsoup::error_output(IVP_Template_Polygon *templ)
{
//    ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "IVP_SurfaceBuilder_Pointsoup::convert_pointsoup_to_compact_ledge_internal() - failed to triangulize object!\n");
    ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "Object points:\n");
    int i;
    for (i=0; i<templ->n_points; i++) {
	ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "Point [%d] : ", i); 
	templ->points[i].print();
    }
    ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "Object edges:\n");
    for (i=0; i<templ->n_lines; i++) {
	int p0 = templ->lines[i].p[0];
	int p1 = templ->lines[i].p[1];
	ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "Distance [%d] - [%d] : %f\n", p0, p1, templ->points[p0].quad_distance_to(&templ->points[p1]));
    }
    ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "\n");
    return;
}

class IVP_SB_PS_DUMMY {
  int dummy;
};

IVP_Compact_Ledge *IVP_SurfaceBuilder_Pointsoup::try_to_build_convex_ledge_from_qhull_result(IVP_U_Vector<IVP_U_Point> *points, IVP_BOOL *skip_point, char *skip_list, char *use_list){
  *skip_point = IVP_FALSE;
  // DEBUG: Print all vertices of convex hull
	IVP_IF(1) {
	    IVP_IFDEBUG(IVP_DM_SURBUILD_POINTSOUP) {
		vertexT *vertex;	    /* set by FORALLvertices */
		FORALLvertices {
		    int point_index = qh_pointid(vertex->point);
		    ivp_debugmanager.dprint(IVP_DM_SURBUILD_POINTSOUP, "Point in convex hull: %f %f %f\n", points->element_at(point_index)->k[0], points->element_at(point_index)->k[1], points->element_at(point_index)->k[2]);
		}
	    }
	}
	
	IVP_U_Vector<IVP_SurMan_PS_Plane> planes;
	IVP_U_Vector<IVP_SB_PS_DUMMY> point_indizes; // array of point indizes
	
	facetT *facet;	    /* set by FORALLfacets */	
	FORALLfacets {
	    IVP_SurMan_PS_Plane *plane = new IVP_SurMan_PS_Plane();
	    planes.add(plane);
	    for (int k=0; k < qh hull_dim; k++) {
		plane->k[k] = facet->normal[k];
	    }
	    //plane->hesse_val = facet->offset;
	    
	    vertexT *vertex, **vertexp;
	    setT *vertices;
	    vertices= qh_facet3vertex (facet);
	    point_indizes.remove_all();
	    FOREACHvertex_(vertices) {
		int point_index = qh_pointid(vertex->point);
		point_indizes.add( (IVP_SB_PS_DUMMY *)point_index );
		plane->points.add(points->element_at(point_index));
		use_list[point_index] ++;
	    }
	    // check area size of facet
	    IVP_DOUBLE area_sum = plane->get_area_size();
	    IVP_DOUBLE qedge_sum = plane->get_qlen_of_all_edges();

	    // swap area
	    if (area_sum < 0){
		plane->mult(-1);
		area_sum *= -1;
		//plane->points.reverse();
		//point_indizes.reverse();
	    }
	    
	    if ( area_sum  <  0.5 * P_MIN_EDGE_LEN * IVP_Inline_Math::ivp_sqrtf(qedge_sum)){
	      // degenarete area -> find and delete interior point
	      // search point which is farest from point 0
	      IVP_DOUBLE max_dist = -1.0;
	      int max_index = 0;