diff options
Diffstat (limited to 'src/glu/sgi/libnurbs/internals/monoTriangulationBackend.cc')
| -rw-r--r-- | src/glu/sgi/libnurbs/internals/monoTriangulationBackend.cc | 397 |
1 files changed, 397 insertions, 0 deletions
diff --git a/src/glu/sgi/libnurbs/internals/monoTriangulationBackend.cc b/src/glu/sgi/libnurbs/internals/monoTriangulationBackend.cc new file mode 100644 index 00000000000..b2a82d0ae26 --- /dev/null +++ b/src/glu/sgi/libnurbs/internals/monoTriangulationBackend.cc @@ -0,0 +1,397 @@ +/* +** 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. +** +** $Date: 2001/03/17 00:25:41 $ $Revision: 1.1 $ +*/ +/* +** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/internals/monoTriangulationBackend.cc,v 1.1 2001/03/17 00:25:41 brianp Exp $ +*/ + +#include "monoTriangulation.h" +#include "polyUtil.h" +#include "backend.h" +#include "arc.h" + +void reflexChain::outputFan(Real v[2], Backend* backend) +{ + Int i; + TrimVertex trimVert; + backend->bgntfan(); + + /* + trimVert.param[0]=v[0]; + trimVert.param[1]=v[1]; + backend->tmeshvert(&trimVert); + */ + backend->tmeshvert(v[0], v[1]); + + if(isIncreasing) { + for(i=0; i<index_queue; i++) + { + /* + trimVert.param[0]=queue[i][0]; + trimVert.param[1]=queue[i][1]; + backend->tmeshvert(&trimVert); + */ + backend->tmeshvert(queue[i][0], queue[i][1]); + } + } + else { + for(i=index_queue-1; i>=0; i--) + { + /* + trimVert.param[0]=queue[i][0]; + trimVert.param[1]=queue[i][1]; + backend->tmeshvert(&trimVert); + */ + backend->tmeshvert(queue[i][0], queue[i][1]); + } + } + backend->endtfan(); +} + +void reflexChain::processNewVertex(Real v[2], Backend* backend) +{ + Int i,j,k; + Int isReflex; + TrimVertex trimVert; + /*if there are at most one vertex in the queue, then simply insert + */ + if(index_queue <=1){ + insert(v); + return; + } + + /*there are at least two vertices in the queue*/ + j=index_queue-1; + + for(i=j; i>=1; i--) { + if(isIncreasing) { + isReflex = (area(queue[i-1], queue[i], v) <= 0.0); + } + else /*decreasing*/{ + isReflex = (area(v, queue[i], queue[i-1]) <= 0.0); + } + if(isReflex) { + break; + } + } + + /* + *if i<j then vertices: i+1--j are convex + * output triangle fan: + * v, and queue[i], i+1, ..., j + */ + if(i<j) + { + backend->bgntfan(); + /* + trimVert.param[0]=v[0]; + trimVert.param[1]=v[1]; + backend->tmeshvert(& trimVert); + */ + backend->tmeshvert(v[0], v[1]); + + if(isIncreasing) { + for(k=i; k<=j; k++) + { + /* + trimVert.param[0]=queue[k][0]; + trimVert.param[1]=queue[k][1]; + backend->tmeshvert(& trimVert); + */ + backend->tmeshvert(queue[k][0], queue[k][1]); + } + } + else { + for(k=j; k>=i; k--) + { + /* + trimVert.param[0]=queue[k][0]; + trimVert.param[1]=queue[k][1]; + backend->tmeshvert(& trimVert); + */ + backend->tmeshvert(queue[k][0], queue[k][1]); + } + } + + backend->endtfan(); + } + + /*delete vertices i+1--j from the queue*/ + index_queue = i+1; + /*finally insert v at the end of the queue*/ + insert(v); + +} + + +void monoTriangulationRec(Real* topVertex, Real* botVertex, + vertexArray* inc_chain, Int inc_current, + vertexArray* dec_chain, Int dec_current, + Backend* backend) +{ + assert( inc_chain != NULL && dec_chain != NULL); + assert( ! (inc_current>=inc_chain->getNumElements() && + dec_current>=dec_chain->getNumElements())); + Int inc_nVertices; + Int dec_nVertices; + Real** inc_array ; + Real** dec_array ; + Int i; + assert( ! ( (inc_chain==NULL) && (dec_chain==NULL))); + + if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/ + { + + dec_array = dec_chain->getArray(); + dec_nVertices = dec_chain->getNumElements(); + reflexChain rChain(20,0); + /*put the top vertex into the reflex chain*/ + rChain.processNewVertex(topVertex, backend); + /*process all the vertices on the dec_chain*/ + for(i=dec_current; i<dec_nVertices; i++){ + rChain.processNewVertex(dec_array[i], backend); + } + /*process the bottom vertex*/ + rChain.processNewVertex(botVertex, backend); + + } + else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/ + { + inc_array = inc_chain->getArray(); + inc_nVertices= inc_chain->getNumElements(); + reflexChain rChain(20,1); + /*put the top vertex into the reflex chain*/ + rChain.processNewVertex(topVertex, backend); + /*process all the vertices on the inc_chain*/ + for(i=inc_current; i<inc_nVertices; i++){ + rChain.processNewVertex(inc_array[i], backend); + } + /*process the bottom vertex*/ + rChain.processNewVertex(botVertex, backend); + } + else /*neither chain is empty*/ + { + inc_array = inc_chain -> getArray(); + dec_array = dec_chain -> getArray(); + inc_nVertices= inc_chain->getNumElements(); + dec_nVertices= dec_chain->getNumElements(); + /*if top of inc_chain is 'lower' than top of dec_chain, process all the + *vertices on the dec_chain which are higher than top of inc_chain + */ + if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0) + { + + reflexChain rChain(20, 0); + rChain.processNewVertex(topVertex, backend); + for(i=dec_current; i<dec_nVertices; i++) + { + if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0) + rChain.processNewVertex(dec_array[i], backend); + else + break; + } + rChain.outputFan(inc_array[inc_current], backend); + monoTriangulationRec(dec_array[i-1], botVertex, + inc_chain, inc_current, + dec_chain, i, + backend); + } + else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/ + { + + reflexChain rChain(20, 1); + rChain.processNewVertex(topVertex, backend); + for(i=inc_current; i<inc_nVertices; i++) + { + if(compV2InY(inc_array[i], dec_array[dec_current]) >0) + rChain.processNewVertex(inc_array[i], backend); + else + break; + } + rChain.outputFan(dec_array[dec_current], backend); + monoTriangulationRec(inc_array[i-1], botVertex, + inc_chain, i, + dec_chain, dec_current, + backend); + } + }/*end case neither is empty*/ +} + + +void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend) +{ + Int i; + /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain, + *then call monoTriangulationRec + */ + Arc_ptr tempV; + Arc_ptr topV; + Arc_ptr botV; + topV = botV = loop; + for(tempV = loop->next; tempV != loop; tempV = tempV->next) + { + if(compFun(topV->tail(), tempV->tail())<0) { + topV = tempV; + } + if(compFun(botV->tail(), tempV->tail())>0) { + botV = tempV; + } + } + + /*creat increase and decrease chains*/ + vertexArray inc_chain(20); /*this is a dynamic array*/ + for(i=1; i<=topV->pwlArc->npts-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/ + inc_chain.appendVertex(topV->pwlArc->pts[i].param); + } + for(tempV = topV->next; tempV != botV; tempV = tempV->next) + { + for(i=0; i<=tempV->pwlArc->npts-2; i++){ + inc_chain.appendVertex(tempV->pwlArc->pts[i].param); + } + } + + vertexArray dec_chain(20); + for(tempV = topV->prev; tempV != botV; tempV = tempV->prev) + { + for(i=tempV->pwlArc->npts-2; i>=0; i--){ + dec_chain.appendVertex(tempV->pwlArc->pts[i].param); + } + } + for(i=botV->pwlArc->npts-2; i>=1; i--){ + dec_chain.appendVertex(tempV->pwlArc->pts[i].param); + } + + monoTriangulationRecFunBackend(topV->tail(), botV->tail(), &inc_chain, 0, &dec_chain, 0, compFun, backend); + +} + +/*if compFun == compV2InY, top to bottom: V-monotone + *if compFun == compV2InX, right to left: U-monotone + */ +void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex, + vertexArray* inc_chain, Int inc_current, + vertexArray* dec_chain, Int dec_current, + Int (*compFun)(Real*, Real*), + Backend* backend) +{ + assert( inc_chain != NULL && dec_chain != NULL); + assert( ! (inc_current>=inc_chain->getNumElements() && + dec_current>=dec_chain->getNumElements())); + Int inc_nVertices; + Int dec_nVertices; + Real** inc_array ; + Real** dec_array ; + Int i; + assert( ! ( (inc_chain==NULL) && (dec_chain==NULL))); + + if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/ + { + + dec_array = dec_chain->getArray(); + dec_nVertices = dec_chain->getNumElements(); + reflexChain rChain(20,0); + /*put the top vertex into the reflex chain*/ + rChain.processNewVertex(topVertex, backend); + /*process all the vertices on the dec_chain*/ + for(i=dec_current; i<dec_nVertices; i++){ + rChain.processNewVertex(dec_array[i], backend); + } + /*process the bottom vertex*/ + rChain.processNewVertex(botVertex, backend); + + } + else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/ + { + inc_array = inc_chain->getArray(); + inc_nVertices= inc_chain->getNumElements(); + reflexChain rChain(20,1); + /*put the top vertex into the reflex chain*/ + rChain.processNewVertex(topVertex, backend); + /*process all the vertices on the inc_chain*/ + for(i=inc_current; i<inc_nVertices; i++){ + rChain.processNewVertex(inc_array[i], backend); + } + /*process the bottom vertex*/ + rChain.processNewVertex(botVertex, backend); + } + else /*neither chain is empty*/ + { + inc_array = inc_chain -> getArray(); + dec_array = dec_chain -> getArray(); + inc_nVertices= inc_chain->getNumElements(); + dec_nVertices= dec_chain->getNumElements(); + /*if top of inc_chain is 'lower' than top of dec_chain, process all the + *vertices on the dec_chain which are higher than top of inc_chain + */ + if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0) + { + + reflexChain rChain(20, 0); + rChain.processNewVertex(topVertex, backend); + for(i=dec_current; i<dec_nVertices; i++) + { + if(compFun(inc_array[inc_current], dec_array[i]) <= 0) + rChain.processNewVertex(dec_array[i], backend); + else + break; + } + rChain.outputFan(inc_array[inc_current], backend); + monoTriangulationRecFunBackend(dec_array[i-1], botVertex, + inc_chain, inc_current, + dec_chain, i, + compFun, + backend); + } + else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/ + { + + reflexChain rChain(20, 1); + rChain.processNewVertex(topVertex, backend); + for(i=inc_current; i<inc_nVertices; i++) + { + if(compFun(inc_array[i], dec_array[dec_current]) >0) + rChain.processNewVertex(inc_array[i], backend); + else + break; + } + rChain.outputFan(dec_array[dec_current], backend); + monoTriangulationRecFunBackend(inc_array[i-1], botVertex, + inc_chain, i, + dec_chain, dec_current, + compFun, + backend); + } + }/*end case neither is empty*/ +} |