/***************************************************************************
                                 qsplot.cpp
                             -------------------
    begin                : 01-January-2000

    copyright            : (C) 2000 by Kamil Dobkowski
    email                : kamildobk@poczta.onet.pl
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#include"qsplot.h"
#include"qsaxis.h"
#include"qsaxes3d.h"
#include"qsprojection3d.h"
#include<assert.h>
#include<vector.h>
#include<algo.h>

QSPlot::QSPlot(QSAxes* parent, const char * name )
:QSAxesChild( parent, name )
 {
  assert( parent );
  m_busy = false;
  m_is_legend = true;
  m_axes = parent;
  m_drv = NULL;

  // default axes
  for( int axis_type=0; axis_type<5; axis_type++ ) m_daxes[axis_type] = m_axes->axisOfType((QSAxis::AxisType )axis_type);

  m_title_str = tr("Untitled plot");
  connect( m_axes, SIGNAL(sigChildRemoved(QSData*)), this, SLOT(axisRemoved(QSData*)) );
 }

//-------------------------------------------------------------//

QSPlot::~QSPlot()
 {
 }

//-------------------------------------------------------------//

void QSPlot::axisRemoved( QSData *axis )
// find another axis to bind to
 {
  for( int axis_type=0; axis_type<5; axis_type++ )
	if ( m_daxes[axis_type] == axis ) m_daxes[axis_type] = m_axes->axisOfType((QSAxis::AxisType )axis_type);
 }

//-------------------------------------------------------------//

void QSPlot::setDefaultAxis( QSAxis *axis )
 {
  if ( axis && axis->parentAxes() == m_axes )  SET_PROPERTY( m_daxes[axis->type()], axis );
 }

//-------------------------------------------------------------//

void QSPlot::setDefaultXAxis( int axisIndex )
 {
  setDefaultAxis( m_axes->axis(axisIndex) );
 }

//-------------------------------------------------------------//

void QSPlot::setDefaultYAxis( int axisIndex )
 {
  setDefaultAxis( m_axes->axis(axisIndex) );
 }

//-------------------------------------------------------------//

void QSPlot::setDefaultZAxis( int axisIndex )
 {
  setDefaultAxis( m_axes->axis(axisIndex) );
 }

//-------------------------------------------------------------//

void QSPlot::setDefaultVAxis( int axisIndex )
 {
   setDefaultAxis( m_axes->axis(axisIndex) );
 }

//-------------------------------------------------------------//

QSPt2f QSPlot::dataToWorld( const QSPt2f& p ) const
 {
  return QSPt2f( m_daxes[QSAxis::XAxisType]->dataToWorld(p.x),
		 m_daxes[QSAxis::YAxisType]->dataToWorld(p.y) );
 }

//-------------------------------------------------------------//

QSPt3f QSPlot::dataToWorld( const QSPt3f& p ) const
 {
  return QSPt3f( m_daxes[QSAxis::XAxisType]->dataToWorld(p.x),
		 m_daxes[QSAxis::YAxisType]->dataToWorld(p.y),
		 m_daxes[QSAxis::ZAxisType]->dataToWorld(p.z) );
 }

//-------------------------------------------------------------//

QSPt3f QSPlot::dataToWorldV( const QSPt3f& p ) const
 {
  return QSPt3f( m_daxes[QSAxis::XAxisType]->dataToWorld(p.x),
		 m_daxes[QSAxis::YAxisType]->dataToWorld(p.y),
		 m_daxes[QSAxis::VAxisType]->dataToWorld(p.z) );
 }

//-------------------------------------------------------------//

QSPt2f QSPlot::worldToData( const QSPt2f& p ) const
 {
  return QSPt2f( m_daxes[QSAxis::XAxisType]->worldToData(p.x),
		 m_daxes[QSAxis::YAxisType]->worldToData(p.y) );
 }

//-------------------------------------------------------------//

QSPt3f QSPlot::worldToData( const QSPt3f& p ) const
 {
  return QSPt3f( m_daxes[QSAxis::XAxisType]->worldToData(p.x),
		 m_daxes[QSAxis::YAxisType]->worldToData(p.y),
		 m_daxes[QSAxis::ZAxisType]->worldToData(p.z) );
 }

//-------------------------------------------------------------//

QSPt3f QSPlot::worldToDataV( const QSPt3f& p ) const
 {
  return QSPt3f( m_daxes[QSAxis::XAxisType]->worldToData(p.x),
		 m_daxes[QSAxis::YAxisType]->worldToData(p.y),
		 m_daxes[QSAxis::VAxisType]->worldToData(p.z) );
 }

//-------------------------------------------------------------//

void QSPlot::setLegendItemVisible( bool visible )
 {
  SET_PROPERTY( m_is_legend, visible );
 }

//-------------------------------------------------------------//

bool QSPlot::start()
 {
  allocRuntimeData();
  m_busy = true;
  return false;
 }

//-------------------------------------------------------------//

bool QSPlot::step()
 {
  return false;
 }

//-------------------------------------------------------------//

void QSPlot::end()
 {
  freeRuntimeData();
  m_busy = false;
 }

//-------------------------------------------------------------//

void QSPlot::allocRuntimeData()
 {
  assert( m_axes );
  m_cpos        = m_axes->m_cpos;
  m_csize       = m_axes->m_csize;
  m_bkg_handler = m_axes->m_bkg_handler;
  m_curr_dpi    = m_axes->run_dpi();
  m_drv         = m_axes->run_gDriver();
  m_proj        = m_axes->proj();
 }

//-------------------------------------------------------------//

void QSPlot::freeRuntimeData()
 {
  m_drv = NULL;
 }

//-------------------------------------------------------------//

bool QSPlot::getAxisRange( QSAxis*, double&, double& )
 {
  return false;
 }

 //-------------------------------------------------------------//

QString QSPlot::posInfo( QSPt2f& )
 {
  return QString::null;
 }

 //-------------------------------------------------------------//

QSPt2f QSPlot::legendItemSize( QSDrv * )
 {
  return QSPt2f(0,0);
 }

//-------------------------------------------------------------//

void QSPlot::drawLegendItem( const QSPt2f&, QSDrv * )
 {
 }

//-------------------------------------------------------------//

void QSPlot::setGradient( const QSGGradient& newGradient )
 {
  if ( m_gradient != newGradient ) {
	 parametersChanging();
	 m_gradient = newGradient;
	 parametersChanged();
	}
 }

//-------------------------------------------------------------//

void QSPlot::setGradientProperty( const QString& string )
 {
  setGradient( toQSGGradient(string) );
 }

//-------------------------------------------------------------//

void QSPlot::loadStateFromStream( QDataStream& stream, QSObjectFactory *factory )
 {
  QSAxesChild::loadStateFromStream( stream, factory );
 }

//-------------------------------------------------------------//

void QSPlot::saveStateToStream( QDataStream& stream, QSObjectFactory *factory )
 {
  QSAxesChild::saveStateToStream( stream, factory );
 }



//-------------------------------------------------------------//
//-------------------------------------------------------------//
//-------------------------------------------------------------//
//-------------------------------------------------------------//
//-------------------------------------------------------------//
//-------------------------------------------------------------//

QSPlot2D::QSPlot2D( QSAxes *parentAxes, const char *name )
:QSPlot( parentAxes, name )
 {
 }

//-------------------------------------------------------------//

QSPlot2D::~QSPlot2D()
 {
 }

//-------------------------------------------------------------//
//-------------------------------------------------------------//
//-------------------------------------------------------------//
//-------------------------------------------------------------//
//-------------------------------------------------------------//
//-------------------------------------------------------------//

#define MAX_BUFF_SIZE 60

struct QSPlot3D::plot3d_runtime_data {
	QSPlot3D *m_plot;
	const QSProjection *m_proj;
	double *first_level;
	double *last_level;
	double *after_last_level;
	int nlevels;
	double  *level_values;
	QSGFill *level_fills;
	QSGLine *level_lines;
	QSGFill polygon_fills[MAX_BUFF_SIZE];
	QSPt3f polygon_normals[MAX_BUFF_SIZE];
	QSPt3f canvas_buff[MAX_BUFF_SIZE];
	QSPt3f clip_buff_1[MAX_BUFF_SIZE];
	QSPt3f clip_buff_2[MAX_BUFF_SIZE];
	QSPt3f clip_buff_3[MAX_BUFF_SIZE];
	double clip_value_buff_1[MAX_BUFF_SIZE];
	double clip_value_buff_2[MAX_BUFF_SIZE];
	double clip_value_buff_3[MAX_BUFF_SIZE];
	bool edge_buff_1[MAX_BUFF_SIZE];
	bool edge_buff_2[MAX_BUFF_SIZE];
	bool edge_buff_3[MAX_BUFF_SIZE];
 	bool all_edges[MAX_BUFF_SIZE]; // filled with true
        QSDrv  *m_drv;
	QSDrv::CNormals  m_cnormals;
	QSDrv::CColors   m_ccolors;
	QSDrv::COrdering m_corder;
	int find_level_greater_than( double value );
        void draw_divided_polygon( const QSPt3f pts[], int npoints, const QSPt3f *norm, const bool *edges, int auto_color );
        void draw_4d_polygon( const QSPt3f pts[], int npoints, const QSPt3f *norm, const double *values, const bool *edges, int auto_color );
	inline void draw_simple_polygon( const QSPt3f pts[], int npoints,
					const QSPt3f *norm, const QSGFill& f,
					const bool *edges = NULL, int auto_color = 0 );
 	inline void draw_clipped_polygon( const QSPt3f pts[], int npoints,
					const QSPt3f *norm, const QSGFill& f,
					QSPt3f clip_pts[], int nclip_pts,
					bool *edges = NULL, int auto_color = 0 );
	void cut_polygon( double level, const QSPt3f *pts, int npts, const bool *in_edges,
			QSPt3f *above_pts, int *above_npts, bool *above_edges,
			QSPt3f *under_pts, int *under_npts, bool *under_edges );
	void cut_polygon4d( double level,
			    const QSPt3f *input_pts, int input_npts, const double *input_values, const bool *in_edges,
			    QSPt3f *above_pts, int *above_npts, double *above_values, bool *above_edges,
			    QSPt3f *under_pts, int *under_npts, double *under_values, bool *under_edges );
     };

 //-------------------------------------------------------------//

QSPlot3D::QSPlot3D( QSAxes* parent, const char * name )
:QSPlot( parent, name )
 {
  d  = NULL;
  m_edge_auto_color = -50;
  m_divide     = false;
  m_clipping   = true;
  m_topbottom  = true;
  m_colored    = true;

  #define FONTS_NUM	0
  #define FILLS_NUM	2
  #define LINES_NUM	1
  #define POINTS_NUM	1

  initAttributeTables( FONTS_NUM, FILLS_NUM, LINES_NUM, POINTS_NUM );
 }

//-------------------------------------------------------------//

QSPlot3D::~QSPlot3D()
 {
 }

//-------------------------------------------------------------//

void QSPlot3D::setEdgeAutoColor( int value )
 {
  SET_PROPERTY( m_edge_auto_color, value );
 }

//-------------------------------------------------------------//

void QSPlot3D::setClipping( bool clipping )
 {
  m_clipping = clipping;
 }

//-------------------------------------------------------------//

void QSPlot3D::setTopBottom( bool enabled )
  {
   SET_PROPERTY( m_topbottom, enabled );
  }

//-------------------------------------------------------------//

void QSPlot3D::setAutoDivide( bool enabled )
  {
   SET_PROPERTY( m_divide, enabled );
  }

//-------------------------------------------------------------//

void QSPlot3D::setColored( bool enabled )
  {
   SET_PROPERTY( m_colored, enabled );
  }

//-------------------------------------------------------------//

#define BOX_SPACE  2.0
#define BOX_WIDTH  20.0
#define BOX_HEIGHT 100.0

QSPt2f QSPlot3D::standardLegendItemSize( QSDrv *m_drv, QSAxis *axis, const QString& title )
 {
  double boxSpace = m_drv->toPixels(BOX_SPACE);
  QSPt2f boxSize( m_drv->toPixels(BOX_WIDTH),
  		  m_drv->toPixels(BOX_HEIGHT) );
  QSPt2f tsize = m_drv->rTextSize( 270, title );
  QSPt2f lsize;
  int nr_labels = 0;
  const list<QSAxisTic> *tics = axis->tics();
  list<QSAxisTic>::const_iterator curr = tics->begin();
  list<QSAxisTic>::const_iterator last = tics->end();
  while( curr != last ) {
         if ( !(*curr).m_major ) {
		curr++;
		continue;
		}
         if ( !(*curr).m_label.isEmpty() ) {
		QSPt2f size = m_drv->rTextSize( (*curr).m_angle, (*curr).m_label );
	 	lsize.x = QMAX(lsize.x, size.x);
	 	lsize.y = QMAX(lsize.y, size.y);
		}
         curr++;
         nr_labels++;
         }	

  boxSize.y = QMAX(boxSize.y,nr_labels*lsize.y);       	
  return QSPt2f( tsize.x+boxSpace+boxSize.x+boxSpace+boxSpace+boxSpace+lsize.x, QMAX(tsize.y,boxSize.y) );
 }

//-------------------------------------------------------------//

void QSPlot3D::drawStandardLegendItem( const QSPt2f& pos, QSDrv *m_drv, QSAxis *axis, const QString& title, const QSGGradient *gradient )
 {
  double boxSpace = m_drv->toPixels(BOX_SPACE);
  QSPt2f boxSize( m_drv->toPixels(BOX_WIDTH),
  		  m_drv->toPixels(BOX_HEIGHT) ); 		

  // title
  QSPt2f tsize = m_drv->rTextSize( 270, title );
  double height = boxSize.y = standardLegendItemSize(m_drv,axis,title).y;
  m_drv->drawRText( QSPt2f(pos.x,pos.y+height/2.0), 270, title, AlignHCenter | AlignTop );

  // gradient
  QSGFill f;
  int h=256;
  QSPt2f m_cpos( pos.x+tsize.x+boxSpace, pos.y+(height-boxSize.y)/2.0 );
  m_drv->setLine( QSGLine::invisibleLine );
  for ( int i=0; i<h; i++ ) {
		gradient->fill( double(h-i)/h, f );
                m_drv->setFill( f );
                QSPt2f p1( m_cpos.x, m_cpos.y+i*boxSize.y/h);
                QSPt2f p2( m_cpos.x+boxSize.x, m_cpos.y+(i+1)*boxSize.y/h);
                m_drv->drawRect( p1, p2 );
            }


  QSGLine l; m_drv->setLine( l );
  m_cpos.x = m_cpos.x+boxSize.x;

  // labels
  const list<QSAxisTic> *tics = axis->tics();
  list<QSAxisTic>::const_iterator curr = tics->begin();
  list<QSAxisTic>::const_iterator last = tics->end();
  while( curr != last ) {
	 double ypos = m_cpos.y+(1.0-(*curr).m_pos)*boxSize.y;
	 if ( (*curr).m_major ) m_drv->drawLine( QSPt2f(m_cpos.x,ypos), QSPt2f(m_cpos.x-2.0*boxSpace,ypos) );
			  else  m_drv->drawLine( QSPt2f(m_cpos.x,ypos), QSPt2f(m_cpos.x-0.5*boxSpace,ypos) );
         m_drv->drawRText( QSPt2f(m_cpos.x+boxSpace+boxSpace+boxSpace,ypos), (*curr).m_angle, (*curr).m_label, AlignLeft | AlignVCenter );
         curr++;
         }
 }

//-------------------------------------------------------------//

void QSPlot3D::allocRuntimeData()
 {
  QSPlot::allocRuntimeData();
  d = new plot3d_runtime_data();
  d->m_plot = this;
  d->m_drv = m_drv;
  d->m_proj = m_proj;
  if ( m_drv ) {
 	m_cnormals = d->m_cnormals = m_drv->cNormals();
  	m_ccolors  = d->m_ccolors  = m_drv->cColors();
  	m_corder   = d->m_corder   = m_drv->cOrdering();
  	if ( m_cnormals == QSDrv::NoNormals ) m_cnormals = d->m_cnormals = QSDrv::MeshNormal; // was && light()
	}

  QSAxis *axis = m_daxes[QSAxis::VAxisType];
  const list<QSAxisTic> *tics = m_daxes[QSAxis::VAxisType]->tics();

  d->nlevels = tics->size();
  d->level_values  = new  double[d->nlevels+2];
  d->level_fills   = new QSGFill[d->nlevels+2];
  d->level_lines   = new QSGLine[d->nlevels+2];

  // the first level at 0.0 ( everything under will be transparent
  d->level_lines[0]  = QSGLine::invisibleLine;
  d->level_fills[0]  = QSGFill::Transparent;
  d->level_values[0] = 0.0;
  d->nlevels = d->nlevels+1;

  // all tics from axis
  list<QSAxisTic>::const_iterator curr_tic = tics->begin();
  for( int i=1; i<d->nlevels; i++ ) {	
        d->level_lines[i]  = curr_tic->m_line;
  	d->level_values[i] = curr_tic->m_pos;
	d->level_fills[i]  = curr_tic->m_fill;	
	// put gradient to axis
        if ( !curr_tic->m_is_fill_defined ) {
		if ( colored() ) m_gradient.fill( d->level_values[i], d->level_fills[i] );
			   else  d->level_fills[i] = m_settings.fills[TMeshFill];
		}
  	curr_tic++;
  	}

  // the last level above the last tic
  if ( d->level_values[d->nlevels-1] < 1.0 ) {
	d->level_lines[d->nlevels]   = QSGLine::invisibleLine;
  	d->level_values[d->nlevels]  = 1.0;
	// take this in a special way
	if ( !axis->reversed() && axis->lastTic().m_is_fill_defined )
		d->level_fills[d->nlevels] = axis->lastTic().m_fill;
		else m_gradient.fill( 1.0, d->level_fills[d->nlevels] );
  	if ( !colored() ) d->level_fills[d->nlevels] = m_settings.fills[TMeshFill];	
	d->nlevels = d->nlevels+1;
	}

  d->first_level  = &d->level_values[0];
  d->last_level   = &d->level_values[d->nlevels-1];
  d->after_last_level = &d->level_values[d->nlevels];

  for( int i=0; i<MAX_BUFF_SIZE; i++ ) d->all_edges[i] = true;
  if ( d->m_drv ) {
	d->m_drv->setTopBottom( topBottom() );
	d->m_drv->setBottomFill( fill(BMeshFill) );
	}
 }

//-------------------------------------------------------------//

void QSPlot3D::freeRuntimeData()
 {
  delete[] d->level_lines;
  delete[] d->level_fills;
  delete[] d->level_values;
  QSPlot::freeRuntimeData();
  delete d; d=NULL;
 }

//-------------------------------------------------------------//

//
// WYKOSIC FILL I OBLICZAC WLASNORECZNIE
//
//


void QSPlot3D::drawPolygon( const QSPt3f pts[], int npoints, QSPt3f *norm, const double *values, const bool *edges )
// if tvertex != -1 then norm[0] is not nessesary
 {
  if ( !m_divide ) {
	if ( m_ccolors == QSDrv::VertexColors ) {
		for( int i=0; i<npoints; i++ )
			if ( colored() ) m_gradient.fill( pts[i].z, d->polygon_fills[i] );
			 	    else d->polygon_fills[i] = m_settings.fills[TMeshFill];	
		} else {
		 if ( colored() ) {
		 	double sum_z = 0.0; for( int i=0; i<npoints; i++ ) sum_z += pts[i].z;
		 	m_gradient.fill( sum_z/npoints, d->polygon_fills[0] );
			} else {
			 d->polygon_fills[0] = m_settings.fills[TMeshFill];
			}
		}
	m_drv->drawPoly3( pts, npoints, norm, d->polygon_fills, edges, m_edge_auto_color );
	} else {
	 if ( !values ) d->draw_divided_polygon( pts, npoints, norm, edges, m_edge_auto_color );
		  else  d->draw_4d_polygon( pts, npoints, norm, values, edges, m_edge_auto_color );
	}

 }

//-------------------------------------------------------------//

void QSPlot3D::plot3d_runtime_data::draw_divided_polygon( const QSPt3f pts[], int npoints, const QSPt3f *norm, const bool *edges, int auto_color )
// draws polygon cut by z levels
 {
  if ( npoints == 0 ) return;

  double min_z = pts[0].z;
  double max_z = pts[0].z;
  for( int i=1; i<npoints; i++ ) {	
	double curr_z = pts[i].z;
	min_z = QMIN( min_z, curr_z );
	max_z = QMAX( max_z, curr_z );
 	}


  // first level
  int  start_level = find_level_greater_than( min_z );

  // try to avoid complicated processing if it is not absolutely needed
  if ( start_level<nlevels && level_values[start_level]<max_z  ) {

     int ninput_pts = npoints;
     int nabove_pts = 0;
     int nunder_pts = 0;
     QSPt3f *input_pts = const_cast<QSPt3f*>(pts);
     QSPt3f *above_pts = clip_buff_1;
     QSPt3f *under_pts = clip_buff_2;
     bool *in_edges    = edges ? const_cast<bool*>(edges) : all_edges;	
     bool *under_edges = edge_buff_1;
     bool *above_edges = edge_buff_2;

	// the level plane crosses through out polygon
	int level_nr = start_level;
	while( level_nr<nlevels && ninput_pts > 0 ) {
		cut_polygon( level_values[level_nr],
			     input_pts, ninput_pts, in_edges,
			     above_pts, &nabove_pts, above_edges,
			     under_pts, &nunder_pts, under_edges );

                // draw polygon under the current level
		// TO CHECK: why it sometimes produces nunder_pts==0
                if ( level_nr>0 && nunder_pts>0 ) draw_clipped_polygon( pts, npoints, norm, level_fills[level_nr], under_pts, nunder_pts, under_edges, auto_color );

                // in first pass stop to use pts ( which is const )
		if ( input_pts == pts ) { input_pts = clip_buff_3; in_edges = edge_buff_3; }

                // rotate buffers: input_pts <-> above_pts
		QSPt3f *temp_pts = input_pts; input_pts = above_pts; above_pts = temp_pts; ninput_pts = nabove_pts;
		bool *temp_edges = in_edges; in_edges = above_edges; above_edges = temp_edges;
		level_nr++;
		}
    } else {
      // polygon contained in the level - no cuts or polygon above the highest level or below the lowest one ( out of drawing area )
      if ( start_level<nlevels && start_level>0 ) draw_simple_polygon( pts, npoints, norm, level_fills[start_level], edges, auto_color );
    }
 }

//-------------------------------------------------------------//

void QSPlot3D::plot3d_runtime_data::draw_4d_polygon( const QSPt3f pts[], int npoints, const QSPt3f *norm, const double *values, const bool *edges, int auto_color )
// dravs polygons cut by the v levels ( 4d data )
 {
  if ( npoints == 0 ) return;

  double min_v = values[0];
  double max_v = values[0];
  for( int i=1; i<npoints; i++ ) {	
	double curr_v = values[i];
	min_v = QMIN( min_v, curr_v );
	max_v = QMAX( max_v, curr_v );
 	}

  int level_nr = find_level_greater_than( min_v );
  if ( level_nr<nlevels && level_values[level_nr]<max_v ) {

	int ninput_pts = npoints;
	int nabove_pts = 0;
	int nunder_pts = 0;
	QSPt3f *input_pts = const_cast<QSPt3f*>(pts);
	double *input_val = const_cast<double*>(values);
	QSPt3f *above_pts = clip_buff_1;
	double *above_val = clip_value_buff_1;
	QSPt3f *under_pts = clip_buff_2;
	double *under_val = clip_value_buff_2;
	bool *in_edges    = edges ? const_cast<bool*>(edges) : all_edges;	
	bool *under_edges = edge_buff_1;
	bool *above_edges = edge_buff_2;
	
	while( level_nr<nlevels && ninput_pts>0  ) {
		cut_polygon4d( level_values[level_nr],
			       input_pts,  ninput_pts, input_val, in_edges,
			       above_pts, &nabove_pts, above_val, above_edges,
			       under_pts, &nunder_pts, under_val, under_edges );

                // draw polygon under the current level ( do not draw anything under level 0 )
                if ( level_nr>0 ) draw_clipped_polygon( pts, npoints, norm, level_fills[level_nr], under_pts, nunder_pts, under_edges, auto_color );

                // in first pass stop to use pts ( which is const )
		if ( input_pts == pts ) { input_pts = clip_buff_3; input_val = clip_value_buff_3; in_edges = edge_buff_3; }

                // rotate buffers: input_pts <-> above_pts
		QSPt3f *temp_pts = input_pts; input_pts = above_pts; above_pts = temp_pts;
		double *temp_val = input_val; input_val = above_val; above_val = temp_val;
  		bool *temp_edges = in_edges; in_edges = above_edges; above_edges = temp_edges;
		ninput_pts = nabove_pts;
		level_nr++;
		}
	} else {
	  // polygon is contained in some level or it is above all levels all it is under all levels ( not drawn in the last two cases )
          if ( level_nr<nlevels && level_nr>0 ) draw_simple_polygon( pts, npoints, norm, level_fills[level_nr], edges, auto_color );
	}

 }

//-------------------------------------------------------------//

inline void QSPlot3D::plot3d_runtime_data::draw_simple_polygon( const QSPt3f pts[], int npoints, const QSPt3f *norm, const QSGFill& f, const bool *edges, int auto_color )
 {
  polygon_fills[0] = f;
  if ( m_ccolors  == QSDrv::VertexColors  ) for( int i=1; i<npoints; i++ ) polygon_fills[i] = f;		
  m_drv->drawPoly3( pts, npoints, norm, polygon_fills, edges, auto_color );
 }

//-------------------------------------------------------------//

inline void QSPlot3D::plot3d_runtime_data::draw_clipped_polygon( const QSPt3f pts[], int npoints, const QSPt3f *norm, const QSGFill& f, QSPt3f clip_pts[], int nclip_pts, bool *edges, int auto_color )
 {
  polygon_fills[0] = f;
  if ( m_ccolors  == QSDrv::VertexColors  ) for( int i=1; i<nclip_pts; i++ ) polygon_fills[i] = f;
	
  polygon_normals[0] = norm[0];
  if ( m_cnormals == QSDrv::VertexNormals ) QSProjection::clipVertexNormals( pts, npoints, clip_pts, nclip_pts, &norm[1], &polygon_normals[1] );
			
  m_drv->drawPoly3( clip_pts, nclip_pts, polygon_normals, polygon_fills, edges, auto_color );
 }

//-------------------------------------------------------------//

int QSPlot3D::plot3d_runtime_data::find_level_greater_than( double value )
// find first level > value or return d->nlevels if all levels are lower then value
 {
  double *ptr = lower_bound( first_level, after_last_level, value );
  int result = ptr < after_last_level ? ptr-first_level : nlevels;
  return result;
 }

//-------------------------------------------------------------//

void QSPlot3D::plot3d_runtime_data::cut_polygon( double level, const QSPt3f *pts, int npts, const bool *in_edges,
					   QSPt3f *above_pts, int *above_npts, bool *above_edges,
					   QSPt3f *under_pts, int *under_npts, bool *under_edges )
 {
  bool p_under;
  bool s_under;
  *above_npts = 0;
  *under_npts = 0;
  const QSPt3f *p;
  const QSPt3f *s = &pts[npts-1]; s_under = ( s->z <= level );
  for( int i=0; i<npts; i++ ) {
  	p = &pts[i]; p_under = ( p->z <= level );
  	
  	if (  p_under &&  s_under )  { under_edges[(*under_npts)] = in_edges[i]; under_pts[(*under_npts)++] = *p; }
  	else
  	if ( !p_under && !s_under )  { above_edges[(*above_npts)] = in_edges[i]; above_pts[(*above_npts)++] = *p; }
  	else {
  	      double t = (level-s->z)/(p->z-s->z);
  	      QSPt3f c( s->x + t*(p->x-s->x),
  	      		s->y + t*(p->y-s->y),
  	      		level );

  	      if (  p_under ) under_edges[(*under_npts)] = false; else under_edges[(*under_npts)] = in_edges[i];
	      if ( !p_under ) above_edges[(*above_npts)] = false; else above_edges[(*above_npts)] = in_edges[i];
	      under_pts[(*under_npts)++] = c;
  	      above_pts[(*above_npts)++] = c;
  	
  	      if (  p_under ) { under_edges[(*under_npts)] = in_edges[i]; under_pts[(*under_npts)++] = *p; }
  	      if ( !p_under ) { above_edges[(*above_npts)] = in_edges[i]; above_pts[(*above_npts)++] = *p; }
             }

        s = p; s_under = p_under;
        }
 }

//-------------------------------------------------------------//

void QSPlot3D::plot3d_runtime_data::cut_polygon4d( double level,
		    const QSPt3f *input_pts, int input_npts, const double *input_val, const bool *in_edges,
		    QSPt3f *above_pts, int *above_npts, double *above_val, bool *above_edges,
		    QSPt3f *under_pts, int *under_npts, double *under_val, bool *under_edges )
 {
  bool p_under;
  bool s_under;
  *above_npts = 0;
  *under_npts = 0;

  const QSPt3f *p;
  const double *pv;
  const QSPt3f *s  = &input_pts[input_npts-1];
  const double *sv = &input_val[input_npts-1];
  s_under = ( *sv <= level );
  for( int i=0; i<input_npts; i++ ) {
  	p  = &input_pts[i];
	pv = &input_val[i];
	p_under = ( *pv <= level );
  	
  	if (  p_under &&  s_under ) { under_edges[(*under_npts)] = in_edges[i]; under_pts[*under_npts] = *p; under_val[*under_npts] = *pv; (*under_npts)++; }
  	else
  	if ( !p_under && !s_under ) { above_edges[(*above_npts)] = in_edges[i]; above_pts[*above_npts] = *p; above_val[*above_npts] = *pv; (*above_npts)++; }
  	else {
  	      double t = (level-*sv)/(*pv-*sv);
  	      QSPt3f c( s->x + t*(p->x-s->x),
			s->y + t*(p->y-s->y),
			s->z + t*(p->z-s->z) );

  	      if (  p_under ) under_edges[(*under_npts)] = false; else under_edges[(*under_npts)] = in_edges[i];
	      if ( !p_under ) above_edges[(*above_npts)] = false; else above_edges[(*above_npts)] = in_edges[i];
  	      under_pts[*under_npts] = c; under_val[*under_npts] = level; (*under_npts)++;
  	      above_pts[*above_npts] = c; above_val[*above_npts] = level; (*above_npts)++;
  	
  	      if (  p_under ) { under_edges[(*under_npts)] = in_edges[i]; under_pts[*under_npts] = *p; under_val[*under_npts] = *pv; (*under_npts)++; }
  	      if ( !p_under ) { above_edges[(*above_npts)] = in_edges[i]; above_pts[*above_npts] = *p; above_val[*above_npts] = *pv; (*above_npts)++; }
             }

        s = p; sv = pv; s_under = p_under;
        }
 }

//-------------------------------------------------------------//

void QSPlot3D::loadStateFromStream( QDataStream& stream, QSObjectFactory *factory )
 {
  QSPlot::loadStateFromStream( stream, factory );
 }

//-------------------------------------------------------------//

void QSPlot3D::saveStateToStream( QDataStream& stream, QSObjectFactory *factory )
 {
  QSPlot::saveStateToStream( stream, factory );
 }

//-------------------------------------------------------------//