subdivider.cc

Mesa is an open-source implementation of the OpenGL specification - a system for rendering interacti

/*
** License Applicability. Except to the extent portions of this file are
** made subject to an alternative license as permitted in the SGI Free
** Software License B, Version 1.1 (the "License"), the contents of this
** file are subject only to the provisions of the License. You may not use
** this file except in compliance with the License. You may obtain a copy
** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
**
** http://oss.sgi.com/projects/FreeB
**
** Note that, as provided in the License, the Software is distributed on an
** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
**
** Original Code. The Original Code is: OpenGL Sample Implementation,
** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
** Copyright in any portions created by third parties is as indicated
** elsewhere herein. All Rights Reserved.
**
** Additional Notice Provisions: The application programming interfaces
** established by SGI in conjunction with the Original Code are The
** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
** Window System(R) (Version 1.3), released October 19, 1998. This software
** was created using the OpenGL(R) version 1.2.1 Sample Implementation
** published by SGI, but has not been independently verified as being
** compliant with the OpenGL(R) version 1.2.1 Specification.
*/

/*
 * subdivider.cxx
 *
 */

#include "glimports.h"
#include "myassert.h"
#include "mystdio.h"
#include "subdivider.h"
#include "arc.h"
#include "bezierarc.h"
#include "bin.h"
#include "renderhints.h"
#include "backend.h"
#include "mapdesc.h"
#include "quilt.h"
#include "patchlist.h"
#include "patch.h"
#include "nurbsconsts.h"
#include "trimvertpool.h"
#include "simplemath.h"

#include "polyUtil.h" //for function area()

//#define  PARTITION_TEST
#ifdef PARTITION_TEST
#include "partitionY.h"
#include "monoTriangulation.h"
#include "dataTransform.h"
#include "monoChain.h"

#endif


#define OPTIMIZE_UNTRIMED_CASE


Bin*
Subdivider::makePatchBoundary( const REAL *from, const REAL *to )
{ 
    Bin* ret = new Bin();
    REAL smin = from[0];
    REAL smax = to[0];
    REAL tmin = from[1];
    REAL tmax = to[1];

    pjarc = 0;

    Arc_ptr jarc = new(arcpool) Arc( arc_bottom, 0 );
    arctessellator.bezier( jarc, smin, smax, tmin, tmin );
    ret->addarc( jarc  );
    pjarc = jarc->append( pjarc );

    jarc = new(arcpool) Arc( arc_right, 0 );
    arctessellator.bezier( jarc, smax, smax, tmin, tmax );
    ret->addarc( jarc  );
    pjarc = jarc->append( pjarc );

    jarc = new(arcpool) Arc( arc_top, 0 );
    arctessellator.bezier( jarc, smax, smin, tmax, tmax );
    ret->addarc( jarc  );
    pjarc = jarc->append( pjarc );

    jarc = new(arcpool) Arc( arc_left, 0 );
    arctessellator.bezier( jarc, smin, smin, tmax, tmin );
    ret->addarc( jarc  );
    jarc->append( pjarc );

    assert( jarc->check() != 0 );
    return ret;
}

/*---------------------------------------------------------------------------
 * Subdivider - construct a subdivider
 *---------------------------------------------------------------------------
 */

Subdivider::Subdivider( Renderhints& r, Backend& b ) 
	: slicer( b ),
	  arctessellator( trimvertexpool, pwlarcpool ), 
	  arcpool( sizeof( Arc), 1, "arcpool" ),
 	  bezierarcpool( sizeof( BezierArc ), 1, "Bezarcpool" ),
	  pwlarcpool( sizeof( PwlArc ), 1, "Pwlarcpool" ),
	  renderhints( r ),
	  backend( b )
{
}

void
Subdivider::setJumpbuffer( JumpBuffer *j )
{
    jumpbuffer = j;
}

/*---------------------------------------------------------------------------
 * clear - reset all state after possible error condition
 *---------------------------------------------------------------------------
 */

void		
Subdivider::clear( void )
{
    trimvertexpool.clear();     
    arcpool.clear();
    pwlarcpool.clear();
    bezierarcpool.clear();
}

/*---------------------------------------------------------------------------
 * ~Subdivider - destroy a subdivider
 *---------------------------------------------------------------------------
 */

Subdivider::~Subdivider( void )
{
}

/*---------------------------------------------------------------------------
 * addArc - add a bezier arc to a trim loop and to a bin
 *---------------------------------------------------------------------------
 */
void
Subdivider::addArc( REAL *cpts, Quilt *quilt, long _nuid )
{
    BezierArc *bezierArc = new(bezierarcpool) BezierArc;
    Arc *jarc  		= new(arcpool) Arc( arc_none, _nuid );
    jarc->pwlArc	= 0;
    jarc->bezierArc	= bezierArc;
    bezierArc->order	= quilt->qspec->order;
    bezierArc->stride	= quilt->qspec->stride;
    bezierArc->mapdesc	= quilt->mapdesc;
    bezierArc->cpts	= cpts;
    initialbin.addarc( jarc );
    pjarc		= jarc->append( pjarc );
}

/*---------------------------------------------------------------------------
 * addArc - add a pwl arc to a trim loop and to a bin
 *---------------------------------------------------------------------------
 */

void
Subdivider::addArc( int npts, TrimVertex *pts, long _nuid ) 
{
    Arc *jarc 		= new(arcpool) Arc( arc_none, _nuid );
    jarc->pwlArc	= new(pwlarcpool) PwlArc( npts, pts );        
    initialbin.addarc( jarc  );
    pjarc		= jarc->append( pjarc );
}

void
Subdivider::beginQuilts( void )
{
    qlist = 0;
}

void
Subdivider::addQuilt( Quilt *quilt )
{
    quilt->next = qlist;
    qlist = quilt;
}

/*---------------------------------------------------------------------------
 * drawSurfaces - main entry point for surface tessellation
 *---------------------------------------------------------------------------
 */

void
Subdivider::drawSurfaces( long nuid )
{
    renderhints.init( );

    if (qlist == NULL) 
      {
	//initialbin could be nonempty due to some errors
	freejarcs(initialbin);
	return;
      }

    for( Quilt *q = qlist; q; q = q->next ) {
	if( q->isCulled( ) == CULL_TRIVIAL_REJECT ) {
	    freejarcs( initialbin );
	    return;
	}
    }


    REAL from[2], to[2];
    qlist->getRange( from, to, spbrkpts, tpbrkpts );
#ifdef OPTIMIZE_UNTRIMED_CASE
    //perform optimization only when the samplng method is 
    //DOMAIN_DISTANCE and the display methdo is either 
    //fill or outline_polygon.
    int optimize = (is_domain_distance_sampling && (renderhints.display_method != N_OUTLINE_PATCH));
#endif

    if( ! initialbin.isnonempty() ) {
#ifdef OPTIMIZE_UNTRIMED_CASE
        if(! optimize )
	  {	

	  makeBorderTrim( from, to );
	  }
#else
	makeBorderTrim( from, to );
#endif
    } else {
	REAL rate[2];
	qlist->findRates( spbrkpts, tpbrkpts, rate );

    	if( decompose( initialbin, min(rate[0], rate[1]) ) ) 
	    mylongjmp( jumpbuffer, 31 );
    }

    backend.bgnsurf( renderhints.wiretris, renderhints.wirequads, nuid );

#ifdef PARTITION_TEST
 if(    initialbin.isnonempty() && spbrkpts.end-2 == spbrkpts.start && 
	tpbrkpts.end-2 == tpbrkpts.start)
{
    for(int i=spbrkpts.start; i<spbrkpts.end-1; i++){
      for(int j=tpbrkpts.start; j<tpbrkpts.end-1; j++){
	Real pta[2], ptb[2];
	pta[0] = spbrkpts.pts[i];
	ptb[0] = spbrkpts.pts[i+1];
	pta[1] = tpbrkpts.pts[j];
	ptb[1] = tpbrkpts.pts[j+1];
	qlist->downloadAll(pta, ptb, backend);

	directedLine *poly;

	  {

	    poly = bin_to_DLineLoops(initialbin);
	    
	    poly=poly->deleteDegenerateLinesAllPolygons();	    	

    sampledLine* retSampledLines;
//printf("before MC_partition\n");	    
	    poly = MC_partitionY(poly, &retSampledLines);
//printf("after MC_partition\n");	    

	  }


	{
	  primStream pStream(5000,5000);
	  directedLine* temp;

	  for(temp=poly; temp != NULL; temp=temp->getNextPolygon())

	    monoTriangulation(temp, &pStream);

	  slicer.evalStream(&pStream);

	}
	//need to clean up space
      }
    }
    freejarcs( initialbin );
    backend.endsurf();
    return;

    /*
    printf("num_polygons=%i\n", poly->numPolygons());
    printf("num_edges=%i\n", poly->numEdgesAllPolygons());
    poly->writeAllPolygons("zloutputFile");
    return;
    {
      primStream pStream(20,20);
      for(directedLine* tempD = poly; tempD != NULL; tempD = tempD->getNextPolygon())
	monoTriangulation(tempD, &pStream);
    }
    return;
    */
}
#endif //PARTITION_TEST


#ifdef OPTIMIZE_UNTRIMED_CASE
    if( (!initialbin.isnonempty())  && optimize )
      {
	int i,j;
	int num_u_steps;
        int num_v_steps;
	for(i=spbrkpts.start; i<spbrkpts.end-1; i++){
	  for(j=tpbrkpts.start; j<tpbrkpts.end-1; j++){
	    Real pta[2], ptb[2];
	    pta[0] = spbrkpts.pts[i];
	    ptb[0] = spbrkpts.pts[i+1];
	    pta[1] = tpbrkpts.pts[j];
	    ptb[1] = tpbrkpts.pts[j+1];
	    qlist->downloadAll(pta, ptb, backend);
	   
            num_u_steps = (int) (domain_distance_u_rate * (ptb[0]-pta[0]));
            num_v_steps = (int) (domain_distance_v_rate * (ptb[1]-pta[1]));

            if(num_u_steps <= 0) num_u_steps = 1;
            if(num_v_steps <= 0) num_v_steps = 1;

	    backend.surfgrid(pta[0], ptb[0], num_u_steps, 
			     ptb[1], pta[1], num_v_steps);
	    backend.surfmesh(0,0,num_u_steps,num_v_steps);

        

	    continue;
	    /* the following is left for reference purpose, don't delete
	    {
	    Bin* tempSource;	
	      Patchlist patchlist(qlist, pta, ptb);
	      patchlist.getstepsize();

	      tempSource=makePatchBoundary(pta, ptb);

	      tessellation(*tempSource, patchlist);

	      render(*tempSource);
	      delete tempSource;
	    }
	    */
	  }
	}
      }
    else
      subdivideInS( initialbin );
#else

    subdivideInS( initialbin );
#endif

    backend.endsurf();

}

void
Subdivider::subdivideInS( Bin& source )
{
    if( renderhints.display_method == N_OUTLINE_PARAM ) {
	outline( source );
	freejarcs( source );
    } else {
	setArcTypeBezier();
	setNonDegenerate();
	splitInS( source, spbrkpts.start, spbrkpts.end );
    }
}


/*---------------------------------------------------------------------------
 * splitInS - split a patch and a bin by an isoparametric line
 *---------------------------------------------------------------------------
 */

void
Subdivider::splitInS( Bin& source, int start, int end )
{
    if( source.isnonempty() ) {
        if( start != end ) {
	    int	i = start + (end - start) / 2;
	    Bin left, right;
	    split( source, left, right, 0, spbrkpts.pts[i] );
	    splitInS( left, start, i );
	    splitInS( right, i+1, end );
        } else {
	    if( start == spbrkpts.start || start == spbrkpts.end ) {
		freejarcs( source );
	    } else if( renderhints.display_method == N_OUTLINE_PARAM_S ) {
		outline( source );
		freejarcs( source );
	    } else {
		setArcTypeBezier();
		setNonDegenerate();
		s_index = start;
		splitInT( source, tpbrkpts.start, tpbrkpts.end );
	    }
        }
    } 
}

/*---------------------------------------------------------------------------
 * splitInT - split a patch and a bin by an isoparametric line
 *---------------------------------------------------------------------------
 */

void
Subdivider::splitInT( Bin& source, int start, int end )
{
    if( source.isnonempty() ) {
        if( start != end ) {
	    int	i = start + (end - start) / 2;
	    Bin left, right;
	    split( source, left, right, 1, tpbrkpts.pts[i] );
	    splitInT( left, start, i );
	    splitInT( right, i+1, end );
        } else {
	    if( start == tpbrkpts.start || start == tpbrkpts.end ) {
		freejarcs( source );
	    } else if( renderhints.display_method == N_OUTLINE_PARAM_ST ) {
		outline( source );
		freejarcs( source );
	    } else {
		t_index = start;
		setArcTypeBezier();
		setDegenerate();

		REAL pta[2], ptb[2];
		pta[0] = spbrkpts.pts[s_index-1];
		pta[1] = tpbrkpts.pts[t_index-1];

		ptb[0] = spbrkpts.pts[s_index];
		ptb[1] = tpbrkpts.pts[t_index];
		qlist->downloadAll( pta, ptb, backend );
	    
		Patchlist patchlist( qlist, pta, ptb );
/*
printf("-------samplingSplit-----\n");
source.show("samplingSplit source");
*/
		samplingSplit( source, patchlist, renderhints.maxsubdivisions, 0 );
		setNonDegenerate();