Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/blenlib/intern/scanfill.c
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenlib/intern/scanfill.c')
-rw-r--r--source/blender/blenlib/intern/scanfill.c1234
1 files changed, 1234 insertions, 0 deletions
diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c
new file mode 100644
index 00000000000..a6a1771148f
--- /dev/null
+++ b/source/blender/blenlib/intern/scanfill.c
@@ -0,0 +1,1234 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * 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. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License. See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ * (uit traces) maart 95
+ */
+
+#include <stdio.h>
+#include <math.h>
+#include <stdlib.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_blenlib.h"
+
+#include "BLI_util.h"
+#include "DNA_listBase.h"
+#include "BLI_editVert.h"
+#include "BLI_arithb.h"
+#include "BLI_scanfill.h"
+#include "BLI_callbacks.h"
+
+/* callbacks for errors and interrupts and some goo */
+static void (*BLI_localErrorCallBack)(char*) = NULL;
+static int (*BLI_localInterruptCallBack)(void) = NULL;
+static void *objectref = NULL;
+static char *colourref = NULL;
+
+
+void BLI_setScanFillObjectRef(void* ob)
+{
+ objectref = ob;
+}
+
+void BLI_setScanFillColourRef(char* c)
+{
+ colourref = c;
+}
+
+void BLI_setErrorCallBack(void (*f)(char*))
+{
+ BLI_localErrorCallBack = f;
+}
+
+void BLI_setInterruptCallBack(int (*f)(void))
+{
+ BLI_localInterruptCallBack = f;
+}
+
+/* just flush the error to /dev/null if the error handler is missing */
+void callLocalErrorCallBack(char* msg)
+{
+ if (BLI_localErrorCallBack) {
+ BLI_localErrorCallBack(msg);
+ }
+}
+
+/* ignore if the interrupt wasn't set */
+int callLocalInterruptCallBack(void)
+{
+ if (BLI_localInterruptCallBack) {
+ return BLI_localInterruptCallBack();
+ } else {
+ return 0;
+ }
+}
+
+
+/* local types */
+typedef struct PolyFill {
+ int edges,verts;
+ float min[3],max[3];
+ short f,nr;
+} PolyFill;
+
+typedef struct ScFillVert {
+ EditVert *v1;
+ EditEdge *first,*last;
+ short f,f1;
+} ScFillVert;
+
+
+/* local funcs */
+int vergscdata(const void *a1, const void *a2);
+int vergpoly(const void *a1, const void *a2);
+void *new_mem_element(int size);
+void addfillvlak(EditVert *v1, EditVert *v2, EditVert *v3);
+int boundinside(PolyFill *pf1, PolyFill *pf2);
+int boundisect(PolyFill *pf2, PolyFill *pf1);
+void mergepolysSimp(PolyFill *pf1, PolyFill *pf2) /* pf2 bij pf1 */;
+EditEdge *existfilledge(EditVert *v1, EditVert *v2);
+short addedgetoscanvert(ScFillVert *sc, EditEdge *eed);
+short testedgeside(float *v1, float *v2, float *v3);
+short testedgeside2(float *v1, float *v2, float *v3);
+short boundinsideEV(EditEdge *eed, EditVert *eve) /* is eve binnen boundbox eed */;
+void testvertexnearedge(void);
+void scanfill(PolyFill *pf);
+void fill_mesh(void);
+ScFillVert *addedgetoscanlist(EditEdge *eed, int len);
+void splitlist(ListBase *tempve, ListBase *temped, short nr);
+
+/* This one is also used in isect.c Keep it here until we know what to do with isect.c */
+#define COMPLIMIT 0.0003
+
+ScFillVert *scdata;
+
+ListBase fillvertbase = {0,0};
+ListBase filledgebase = {0,0};
+ListBase fillvlakbase = {0,0};
+
+short cox, coy;
+
+/* **** FUNKTIES VOOR QSORT *************************** */
+
+
+int vergscdata(const void *a1, const void *a2)
+{
+ const ScFillVert *x1=a1,*x2=a2;
+
+ if( x1->v1->co[coy] < x2->v1->co[coy] ) return 1;
+ else if( x1->v1->co[coy] > x2->v1->co[coy]) return -1;
+ else if( x1->v1->co[cox] > x2->v1->co[cox] ) return 1;
+ else if( x1->v1->co[cox] < x2->v1->co[cox]) return -1;
+
+ return 0;
+}
+
+int vergpoly(const void *a1, const void *a2)
+{
+ const PolyFill *x1=a1, *x2=a2;
+
+ if( x1->min[cox] > x2->min[cox] ) return 1;
+ else if( x1->min[cox] < x2->min[cox] ) return -1;
+ else if( x1->min[coy] > x2->min[coy] ) return 1;
+ else if( x1->min[coy] < x2->min[coy] ) return -1;
+
+ return 0;
+}
+
+/* ************* MEMORY MANAGEMENT ************* */
+
+struct mem_elements {
+ struct mem_elements *next, *prev;
+ char *data;
+};
+
+void *new_mem_element(int size)
+{
+ /* Alleen als gedurende het werken duizenden elementen worden aangemaakt en
+ * nooit (tussendoor) vrijgegeven. Op eind is vrijgeven nodig (-1).
+ */
+ int blocksize= 16384;
+ static int offs= 0; /* het huidige vrije adres */
+ static struct mem_elements *cur= 0;
+ static ListBase lb= {0, 0};
+ void *adr;
+
+ if(size>10000 || size==0) {
+ printf("incorrect use of new_mem_element\n");
+ }
+ else if(size== -1) {
+ cur= lb.first;
+ while(cur) {
+ MEM_freeN(cur->data);
+ cur= cur->next;
+ }
+ BLI_freelistN(&lb);
+
+ return NULL;
+ }
+
+ size= 4*( (size+3)/4 );
+
+ if(cur) {
+ if(size+offs < blocksize) {
+ adr= (void *) (cur->data+offs);
+ offs+= size;
+ return adr;
+ }
+ }
+
+ cur= MEM_callocN( sizeof(struct mem_elements), "newmem");
+ cur->data= MEM_callocN(blocksize, "newmem");
+ BLI_addtail(&lb, cur);
+
+ offs= size;
+ return cur->data;
+}
+
+void BLI_end_edgefill(void)
+{
+ new_mem_element(-1);
+
+ fillvertbase.first= fillvertbase.last= 0;
+ filledgebase.first= filledgebase.last= 0;
+ fillvlakbase.first= fillvlakbase.last= 0;
+}
+
+/* **** FILL ROUTINES *************************** */
+
+EditVert *BLI_addfillvert(float *vec)
+{
+ EditVert *eve;
+
+ eve= new_mem_element(sizeof(EditVert));
+ BLI_addtail(&fillvertbase, eve);
+
+ if(vec) {
+ *(eve->co) = *(vec);
+ *(eve->co + 1) = *(vec + 1);
+ *(eve->co + 2) = *(vec + 2);
+ }
+/* VECCOPY(eve->co, vec); */
+
+ return eve;
+}
+
+EditEdge *BLI_addfilledge(EditVert *v1, EditVert *v2)
+{
+ EditEdge *newed;
+
+ newed= new_mem_element(sizeof(EditEdge));
+ BLI_addtail(&filledgebase, newed);
+
+ newed->v1= v1;
+ newed->v2= v2;
+
+ return newed;
+}
+
+void addfillvlak(EditVert *v1, EditVert *v2, EditVert *v3)
+{
+ /* maakt geen edges aan */
+ EditVlak *evl;
+
+ evl= new_mem_element(sizeof(EditVlak));
+ BLI_addtail(&fillvlakbase, evl);
+
+ evl->v1= v1;
+ evl->v2= v2;
+ evl->v3= v3;
+ evl->f= 2;
+ /* G.obedit is Object*, actcol is char */
+/* if(G.obedit && G.obedit->actcol) evl->mat_nr= G.obedit->actcol-1; */
+ if (objectref && colourref && *colourref) {
+ evl->mat_nr = *colourref - 1;
+ } else {
+ evl->mat_nr = 0;
+ }
+}
+
+
+int boundinside(PolyFill *pf1, PolyFill *pf2)
+{
+ /* is pf2 INSIDE pf1 ? met boundingbox */
+ /* eerst testen of poly's bestaan */
+
+ if(pf1->edges==0 || pf2->edges==0) return 0;
+
+ if(pf2->max[cox]<pf1->max[cox])
+ if(pf2->max[coy]<pf1->max[coy])
+ if(pf2->min[cox]>pf1->min[cox])
+ if(pf2->min[coy]>pf1->min[coy]) return 1;
+ return 0;
+}
+
+int boundisect(PolyFill *pf2, PolyFill *pf1)
+{
+ /* is pf2 aangeraakt door pf1 ? met boundingbox */
+ /* eerst testen of poly's bestaan */
+
+ if(pf1->edges==0 || pf2->edges==0) return 0;
+
+ if(pf2->max[cox] < pf1->min[cox] ) return 0;
+ if(pf2->max[coy] < pf1->min[coy] ) return 0;
+
+ if(pf2->min[cox] > pf1->max[cox] ) return 0;
+ if(pf2->min[coy] > pf1->max[coy] ) return 0;
+
+ /* samenvoegen */
+ if(pf2->max[cox]<pf1->max[cox]) pf2->max[cox]= pf1->max[cox];
+ if(pf2->max[coy]<pf1->max[coy]) pf2->max[coy]= pf1->max[coy];
+
+ if(pf2->min[cox]>pf1->min[cox]) pf2->min[cox]= pf1->min[cox];
+ if(pf2->min[coy]>pf1->min[coy]) pf2->min[coy]= pf1->min[coy];
+
+ return 1;
+}
+
+
+
+
+
+void mergepolysSimp(PolyFill *pf1, PolyFill *pf2) /* pf2 bij pf1 */
+/* PolyFill *pf1,*pf2; */
+{
+ EditVert *eve;
+ EditEdge *eed;
+
+ /* alle oude polynummers vervangen */
+ eve= fillvertbase.first;
+ while(eve) {
+ if(eve->xs== pf2->nr) eve->xs= pf1->nr;
+ eve= eve->next;
+ }
+ eed= filledgebase.first;
+ while(eed) {
+ if(eed->f1== pf2->nr) eed->f1= pf1->nr;
+ eed= eed->next;
+ }
+
+ pf1->verts+= pf2->verts;
+ pf1->edges+= pf2->edges;
+ pf2->verts= pf2->edges= 0;
+ pf1->f= (pf1->f | pf2->f);
+}
+
+
+
+EditEdge *existfilledge(EditVert *v1, EditVert *v2)
+/* EditVert *v1,*v2; */
+{
+ EditEdge *eed;
+
+ eed= filledgebase.first;
+ while(eed) {
+ if(eed->v1==v1 && eed->v2==v2) return eed;
+ if(eed->v2==v1 && eed->v1==v2) return eed;
+ eed= eed->next;
+ }
+ return 0;
+}
+
+
+short testedgeside(float *v1, float *v2, float *v3) /* is v3 rechts van v1-v2 ? Met uizondering: v3==v1 || v3==v2*/
+/* float *v1,*v2,*v3; */
+{
+ float inp;
+
+ inp= (v2[cox]-v1[cox])*(v1[coy]-v3[coy])
+ +(v1[coy]-v2[coy])*(v1[cox]-v3[cox]);
+
+ if(inp<0.0) return 0;
+ else if(inp==0) {
+ if(v1[cox]==v3[cox] && v1[coy]==v3[coy]) return 0;
+ if(v2[cox]==v3[cox] && v2[coy]==v3[coy]) return 0;
+ }
+ return 1;
+}
+
+short testedgeside2(float *v1, float *v2, float *v3) /* is v3 rechts van v1-v2 ? niet doorsnijden! */
+/* float *v1,*v2,*v3; */
+{
+ float inp;
+
+ inp= (v2[cox]-v1[cox])*(v1[coy]-v3[coy])
+ +(v1[coy]-v2[coy])*(v1[cox]-v3[cox]);
+
+ if(inp<=0.0) return 0;
+ return 1;
+}
+
+short addedgetoscanvert(ScFillVert *sc, EditEdge *eed)
+/* ScFillVert *sc; */
+/* EditEdge *eed; */
+{
+ /* zoek eerste edge die rechts van eed ligt en stop eed daarvoor */
+ EditEdge *ed;
+ float fac,fac1,x,y;
+
+ if(sc->first==0) {
+ sc->first= sc->last= eed;
+ eed->prev= eed->next=0;
+ return 1;
+ }
+
+ x= eed->v1->co[cox];
+ y= eed->v1->co[coy];
+
+ fac1= eed->v2->co[coy]-y;
+ if(fac1==0.0) {
+ fac1= 1.0e10*(eed->v2->co[cox]-x);
+
+ }
+ else fac1= (x-eed->v2->co[cox])/fac1;
+
+ ed= sc->first;
+ while(ed) {
+
+ if(ed->v2==eed->v2) return 0;
+
+ fac= ed->v2->co[coy]-y;
+ if(fac==0.0) {
+ fac= 1.0e10*(ed->v2->co[cox]-x);
+
+ }
+ else fac= (x-ed->v2->co[cox])/fac;
+ if(fac>fac1) break;
+
+ ed= ed->next;
+ }
+ if(ed) BLI_insertlinkbefore((ListBase *)&(sc->first), ed, eed);
+ else BLI_addtail((ListBase *)&(sc->first),eed);
+
+ return 1;
+}
+
+
+ScFillVert *addedgetoscanlist(EditEdge *eed, int len)
+/* EditEdge *eed; */
+/* int len; */
+{
+ /* voegt edge op juiste plek in ScFillVert list */
+ /* geeft sc terug als edge al bestaat */
+ ScFillVert *sc,scsearch;
+ EditVert *eve;
+
+ /* welke vert is linksboven */
+ if(eed->v1->co[coy] == eed->v2->co[coy]) {
+ if(eed->v1->co[cox] > eed->v2->co[cox]) {
+ eve= eed->v1;
+ eed->v1= eed->v2;
+ eed->v2= eve;
+ }
+ }
+ else if(eed->v1->co[coy] < eed->v2->co[coy]) {
+ eve= eed->v1;
+ eed->v1= eed->v2;
+ eed->v2= eve;
+ }
+ /* zoek plek in lijst */
+ scsearch.v1= eed->v1;
+ sc= (ScFillVert *)bsearch(&scsearch,scdata,len,
+ sizeof(ScFillVert), vergscdata);
+
+ if(sc==0) printf("Error in search edge: %x\n",eed);
+ else if(addedgetoscanvert(sc,eed)==0) return sc;
+
+ return 0;
+}
+
+short boundinsideEV(EditEdge *eed, EditVert *eve) /* is eve binnen boundbox eed */
+/* EditEdge *eed; */
+/* EditVert *eve; */
+{
+ float minx,maxx,miny,maxy;
+
+ if(eed->v1->co[cox]<eed->v2->co[cox]) {
+ minx= eed->v1->co[cox];
+ maxx= eed->v2->co[cox];
+ } else {
+ minx= eed->v2->co[cox];
+ maxx= eed->v1->co[cox];
+ }
+ if(eve->co[cox]>=minx && eve->co[cox]<=maxx) {
+ if(eed->v1->co[coy]<eed->v2->co[coy]) {
+ miny= eed->v1->co[coy];
+ maxy= eed->v2->co[coy];
+ } else {
+ miny= eed->v2->co[coy];
+ maxy= eed->v1->co[coy];
+ }
+ if(eve->co[coy]>=miny && eve->co[coy]<=maxy) return 1;
+ }
+ return 0;
+}
+
+
+void testvertexnearedge(void)
+{
+ /* alleen de vertices met ->h==1 worden getest op
+ nabijheid van edge, zo ja invoegen */
+
+ EditVert *eve;
+ EditEdge *eed,*ed1;
+ float dist,vec1[2],vec2[2],vec3[2];
+
+ eve= fillvertbase.first;
+ while(eve) {
+ if(eve->h==1) {
+ vec3[0]= eve->co[cox];
+ vec3[1]= eve->co[coy];
+ /* de bewuste edge vinden waar eve aan zit */
+ ed1= filledgebase.first;
+ while(ed1) {
+ if(ed1->v1==eve || ed1->v2==eve) break;
+ ed1= ed1->next;
+ }
+ if(ed1->v1==eve) {
+ ed1->v1= ed1->v2;
+ ed1->v2= eve;
+ }
+ eed= filledgebase.first;
+ while(eed) {
+ if(eve!=eed->v1 && eve!=eed->v2 && eve->xs==eed->f1) {
+ if(FloatCompare(eve->co,eed->v1->co, COMPLIMIT)) {
+ ed1->v2= eed->v1;
+ eed->v1->h++;
+ eve->h= 0;
+ break;
+ }
+ else if(FloatCompare(eve->co,eed->v2->co, COMPLIMIT)) {
+ ed1->v2= eed->v2;
+ eed->v2->h++;
+ eve->h= 0;
+ break;
+ }
+ else {
+ vec1[0]= eed->v1->co[cox];
+ vec1[1]= eed->v1->co[coy];
+ vec2[0]= eed->v2->co[cox];
+ vec2[1]= eed->v2->co[coy];
+ if(boundinsideEV(eed,eve)) {
+ dist= DistVL2Dfl(vec1,vec2,vec3);
+ if(dist<COMPLIMIT) {
+ /* nieuwe edge */
+ ed1= BLI_addfilledge(eed->v1, eve);
+
+ /* printf("fill: vertex near edge %x\n",eve); */
+ ed1->f= ed1->h= 0;
+ ed1->f1= eed->f1;
+ eed->v1= eve;
+ eve->h= 3;
+ break;
+ }
+ }
+ }
+ }
+ eed= eed->next;
+ }
+ }
+ eve= eve->next;
+ }
+}
+
+void splitlist(ListBase *tempve, ListBase *temped, short nr)
+/* ListBase *tempve,*temped; */
+/* short nr; */
+{
+ /* alles zit in de templist, alleen poly nr naar fillist schrijven */
+ EditVert *eve,*nextve;
+ EditEdge *eed,*nexted;
+
+ addlisttolist(tempve,&fillvertbase);
+ addlisttolist(temped,&filledgebase);
+
+ eve= tempve->first;
+ while(eve) {
+ nextve= eve->next;
+ if(eve->xs==nr) {
+ BLI_remlink(tempve,eve);
+ BLI_addtail(&fillvertbase,eve);
+ }
+ eve= nextve;
+ }
+ eed= temped->first;
+ while(eed) {
+ nexted= eed->next;
+ if(eed->f1==nr) {
+ BLI_remlink(temped,eed);
+ BLI_addtail(&filledgebase,eed);
+ }
+ eed= nexted;
+ }
+}
+
+
+void scanfill(PolyFill *pf)
+{
+ ScFillVert *sc = NULL, *sc1;
+ EditVert *eve,*v1,*v2,*v3;
+ EditEdge *eed,*nexted,*ed1,*ed2,*ed3;
+ float miny = 0.0;
+ int a,b,verts, maxvlak, totvlak;
+ short nr, test, twoconnected=0;
+
+ nr= pf->nr;
+ verts= pf->verts;
+
+ /* PRINTS
+ eve= fillvertbase.first;
+ while(eve) {
+ printf("vert: %x co: %f %f\n",eve,eve->co[cox],eve->co[coy]);
+ eve= eve->next;
+ }
+ eed= filledgebase.first;
+ while(eed) {
+ printf("edge: %x verts: %x %x\n",eed,eed->v1,eed->v2);
+ eed= eed->next;
+ } */
+
+ /* STAP 0: alle nul lange edges eruit */
+ eed= filledgebase.first;
+ while(eed) {
+ if(eed->v1->co[cox]==eed->v2->co[cox]) {
+ if(eed->v1->co[coy]==eed->v2->co[coy]) {
+ if(eed->v1->f==255 && eed->v2->f!=255) {
+ eed->v2->f= 255;
+ eed->v2->vn= eed->v1->vn;
+ }
+ else if(eed->v2->f==255 && eed->v1->f!=255) {
+ eed->v1->f= 255;
+ eed->v1->vn= eed->v2->vn;
+ }
+ else if(eed->v2->f==255 && eed->v1->f==255) {
+ eed->v1->vn= eed->v2->vn;
+ }
+ else {
+ eed->v2->f= 255;
+ eed->v2->vn= eed->v1;
+ }
+ }
+ }
+ eed= eed->next;
+ }
+
+ /* STAP 1: maak ahv van FillVert en FillEdge lijsten een gesorteerde
+ ScFillVert lijst
+ */
+ sc= scdata= (ScFillVert *)MEM_callocN(pf->verts*sizeof(ScFillVert),"Scanfill1");
+ eve= fillvertbase.first;
+ verts= 0;
+ while(eve) {
+ if(eve->xs==nr) {
+ if(eve->f!= 255) {
+ verts++;
+ eve->f= 0; /* vlag later voor connectedges */
+ sc->v1= eve;
+ sc++;
+ }
+ }
+ eve= eve->next;
+ }
+
+ qsort(scdata, verts, sizeof(ScFillVert), vergscdata);
+
+ sc= scdata;
+ eed= filledgebase.first;
+ while(eed) {
+ nexted= eed->next;
+ eed->f= 0;
+ BLI_remlink(&filledgebase,eed);
+ if(eed->v1->f==255) {
+ v1= eed->v1;
+ while(eed->v1->f==255 && eed->v1->vn!=v1) eed->v1= eed->v1->vn;
+ }
+ if(eed->v2->f==255) {
+ v2= eed->v2;
+ while(eed->v2->f==255 && eed->v2->vn!=v2) eed->v2= eed->v2->vn;
+ }
+ if(eed->v1!=eed->v2) addedgetoscanlist(eed,verts);
+
+ eed= nexted;
+ }
+ /*
+ sc= scdata;
+ for(a=0;a<verts;a++) {
+ printf("\nscvert: %x\n",sc->v1);
+ eed= sc->first;
+ while(eed) {
+ printf(" ed %x %x %x\n",eed,eed->v1,eed->v2);
+ eed= eed->next;
+ }
+ sc++;
+ }*/
+
+
+ /* STAP 2: FILL LUS */
+
+ if(pf->f==0) twoconnected= 1;
+
+ /* (tijdelijke) beveiliging: nooit veel meer vlakken dan vertices */
+ totvlak= 0;
+ maxvlak= 2*verts; /* 2*verts: cirkel in driehoek, beide gevuld */
+
+ sc= scdata;
+ for(a=0;a<verts;a++) {
+ /* printf("VERTEX %d %x\n",a,sc->v1); */
+ ed1= sc->first;
+ while(ed1) { /* connectflags zetten */
+ nexted= ed1->next;
+ if(ed1->v1->h==1 || ed1->v2->h==1) {
+ BLI_remlink((ListBase *)&(sc->first),ed1);
+ BLI_addtail(&filledgebase,ed1);
+ if(ed1->v1->h>1) ed1->v1->h--;
+ if(ed1->v2->h>1) ed1->v2->h--;
+ }
+ else ed1->v2->f= 1;
+
+ ed1= nexted;
+ }
+ while(sc->first) { /* zolang er edges zijn */
+ ed1= sc->first;
+ ed2= ed1->next;
+
+ if(callLocalInterruptCallBack()) break;
+ if(totvlak>maxvlak) {
+ /* printf("Fill error: endless loop. Escaped at vert %d, tot: %d.\n", a, verts); */
+ a= verts;
+ break;
+ }
+ if(ed2==0) {
+ sc->first=sc->last= 0;
+ /* printf("maar 1 edge aan vert\n"); */
+ BLI_addtail(&filledgebase,ed1);
+ ed1->v2->f= 0;
+ ed1->v1->h--;
+ ed1->v2->h--;
+ } else {
+ /* test rest vertices */
+ v1= ed1->v2;
+ v2= ed1->v1;
+ v3= ed2->v2;
+ /* hieronder komt voor bij serie overlappende edges */
+ if(v1==v2 || v2==v3) break;
+ /* printf("test verts %x %x %x\n",v1,v2,v3); */
+ miny = ( (v1->co[coy])<(v3->co[coy]) ? (v1->co[coy]) : (v3->co[coy]) );
+/* miny= MIN2(v1->co[coy],v3->co[coy]); */
+ sc1= sc+1;
+ test= 0;
+
+ for(b=a+1;b<verts;b++) {
+ if(sc1->v1->f==0) {
+ if(sc1->v1->co[coy] <= miny) break;
+
+ if(testedgeside(v1->co,v2->co,sc1->v1->co))
+ if(testedgeside(v2->co,v3->co,sc1->v1->co))
+ if(testedgeside(v3->co,v1->co,sc1->v1->co)) {
+ /* punt in driehoek */
+
+ test= 1;
+ break;
+ }
+ }
+ sc1++;
+ }
+ if(test) {
+ /* nieuwe edge maken en overnieuw beginnen */
+ /* printf("add new edge %x %x and start again\n",v2,sc1->v1); */
+
+ ed3= BLI_addfilledge(v2, sc1->v1);
+ BLI_remlink(&filledgebase, ed3);
+ BLI_insertlinkbefore((ListBase *)&(sc->first), ed2, ed3);
+ ed3->v2->f= 1;
+ ed3->f= 2;
+ ed3->v1->h++;
+ ed3->v2->h++;
+ }
+ else {
+ /* nieuwe driehoek */
+ /* printf("add vlak %x %x %x\n",v1,v2,v3); */
+ addfillvlak(v1, v2, v3);
+ totvlak++;
+ BLI_remlink((ListBase *)&(sc->first),ed1);
+ BLI_addtail(&filledgebase,ed1);
+ ed1->v2->f= 0;
+ ed1->v1->h--;
+ ed1->v2->h--;
+ /* ed2 mag ook weg als het een oude is */
+ if(ed2->f==0 && twoconnected) {
+ BLI_remlink((ListBase *)&(sc->first),ed2);
+ BLI_addtail(&filledgebase,ed2);
+ ed2->v2->f= 0;
+ ed2->v1->h--;
+ ed2->v2->h--;
+ }
+
+ /* nieuwe edge */
+ ed3= BLI_addfilledge(v1, v3);
+ BLI_remlink(&filledgebase, ed3);
+ ed3->f= 2;
+ ed3->v1->h++;
+ ed3->v2->h++;
+
+ /* printf("add new edge %x %x\n",v1,v3); */
+ sc1= addedgetoscanlist(ed3, verts);
+
+ if(sc1) { /* ed3 bestaat al: verwijderen*/
+ /* printf("Edge bestaat al\n"); */
+ ed3->v1->h--;
+ ed3->v2->h--;
+
+ if(twoconnected) ed3= sc1->first;
+ else ed3= 0;
+ while(ed3) {
+ if( (ed3->v1==v1 && ed3->v2==v3) || (ed3->v1==v3 && ed3->v2==v1) ) {
+ BLI_remlink((ListBase *)&(sc1->first),ed3);
+ BLI_addtail(&filledgebase,ed3);
+ ed3->v1->h--;
+ ed3->v2->h--;
+ break;
+ }
+ ed3= ed3->next;
+ }
+ }
+
+ }
+ }
+ /* test op loze edges */
+ ed1= sc->first;
+ while(ed1) {
+ nexted= ed1->next;
+ if(ed1->v1->h<2 || ed1->v2->h<2) {
+ BLI_remlink((ListBase *)&(sc->first),ed1);
+ BLI_addtail(&filledgebase,ed1);
+ if(ed1->v1->h>1) ed1->v1->h--;
+ if(ed1->v2->h>1) ed1->v2->h--;
+ }
+
+ ed1= nexted;
+ }
+ }
+ sc++;
+ }
+
+ MEM_freeN(scdata);
+}
+
+
+
+int BLI_edgefill(int mode) /* DE HOOFD FILL ROUTINE */
+{
+ /*
+ - fill werkt met eigen lijsten, eerst aanmaken dus (geen vlakken)
+ - geef vertices in ->vn de oude pointer mee
+ - alleen xs en ys worden hier niet gebruikt: daar kan je iets in verstoppen
+ - edge flag ->f wordt 2 als het nieuwe edge betreft
+ - mode: & 1 is kruispunten testen, edges maken (NOG DOEN )
+ */
+ ListBase tempve, temped;
+ EditVert *eve;
+ EditEdge *eed,*nexted;
+ PolyFill *pflist,*pf;
+ float *minp, *maxp, *v1, *v2, norm[3], len;
+ short a,c,poly=0,ok=0,toggle=0;
+
+ /* variabelen resetten*/
+ eve= fillvertbase.first;
+ while(eve) {
+ eve->f= 0;
+ eve->xs= 0;
+ eve->h= 0;
+ eve= eve->next;
+ }
+
+ /* eerst de vertices testen op aanwezigheid in edges */
+ /* plus flaggen resetten */
+ eed= filledgebase.first;
+ while(eed) {
+ eed->f= eed->f1= eed->h= 0;
+ eed->v1->f= 1;
+ eed->v2->f= 1;
+
+ eed= eed->next;
+ }
+
+ eve= fillvertbase.first;
+ while(eve) {
+ if(eve->f & 1) {
+ ok=1;
+ break;
+ }
+ eve= eve->next;
+ }
+
+ if(ok==0) return 0;
+
+ /* NEW NEW! projektie bepalen: met beste normaal */
+ /* pak de eerste drie verschillende verts */
+
+ /* DIT STUK IS NOG STEEDS TAMELIJK ZWAK! */
+
+ eve= fillvertbase.last;
+ len= 0.0;
+ v1= eve->co;
+ v2= 0;
+ eve= fillvertbase.first;
+ while(eve) {
+ if(v2) {
+ if( FloatCompare(v2, eve->co, 0.0003)==0) {
+ len= CalcNormFloat(v1, v2, eve->co, norm);
+ if(len != 0.0) break;
+ }
+ }
+ else if(FloatCompare(v1, eve->co, 0.0003)==0) {
+ v2= eve->co;
+ }
+ eve= eve->next;
+ }
+
+ if(len==0.0) return 0; /* geen fill mogelijk */
+
+ norm[0]= fabs(norm[0]);
+ norm[1]= fabs(norm[1]);
+ norm[2]= fabs(norm[2]);
+
+ if(norm[2]>=norm[0] && norm[2]>=norm[1]) {
+ cox= 0; coy= 1;
+ }
+ else if(norm[1]>=norm[0] && norm[1]>=norm[2]) {
+ cox= 0; coy= 2;
+ }
+ else {
+ cox= 1; coy= 2;
+ }
+
+ /* STAP 1: AANTAL POLY'S TELLEN */
+ eve= fillvertbase.first;
+ while(eve) {
+ /* pak eerste vertex zonder polynummer */
+ if(eve->xs==0) {
+ poly++;
+ /* nu een soort select connected */
+ ok= 1;
+ eve->xs= poly;
+
+ while(ok) {
+
+ ok= 0;
+ toggle++;
+ if(toggle & 1) eed= filledgebase.first;
+ else eed= filledgebase.last;
+
+ while(eed) {
+ if(eed->v1->xs==0 && eed->v2->xs==poly) {
+ eed->v1->xs= poly;
+ eed->f1= poly;
+ ok= 1;
+ }
+ else if(eed->v2->xs==0 && eed->v1->xs==poly) {
+ eed->v2->xs= poly;
+ eed->f1= poly;
+ ok= 1;
+ }
+ else if(eed->f1==0) {
+ if(eed->v1->xs==poly && eed->v2->xs==poly) {
+ eed->f1= poly;
+ ok= 1;
+ }
+ }
+ if(toggle & 1) eed= eed->next;
+ else eed= eed->prev;
+ }
+ }
+ }
+ eve= eve->next;
+ }
+ /* printf("aantal poly's: %d\n",poly); */
+
+ /* STAP 2: LOSSE EDGES EN SLIERTEN VERWIJDEREN */
+ eed= filledgebase.first;
+ while(eed) {
+ if(eed->v1->h++ >250) break;
+ if(eed->v2->h++ >250) break;
+ eed= eed->next;
+ }
+ if(eed) {
+ /* anders kan hierna niet met zekerheid vertices worden gewist */
+ callLocalErrorCallBack("No vertices with 250 edges allowed!");
+ return 0;
+ }
+
+ /* doet alleen vertices met ->h==1 */
+ testvertexnearedge();
+
+ ok= 1;
+ while(ok) {
+ ok= 0;
+ toggle++;
+ if(toggle & 1) eed= filledgebase.first;
+ else eed= filledgebase.last;
+ while(eed) {
+ if(toggle & 1) nexted= eed->next;
+ else nexted= eed->prev;
+ if(eed->v1->h==1) {
+ eed->v2->h--;
+ BLI_remlink(&fillvertbase,eed->v1);
+ BLI_remlink(&filledgebase,eed);
+ ok= 1;
+ }
+ else if(eed->v2->h==1) {
+ eed->v1->h--;
+ BLI_remlink(&fillvertbase,eed->v2);
+ BLI_remlink(&filledgebase,eed);
+ ok= 1;
+ }
+ eed= nexted;
+ }
+ }
+ if(filledgebase.first==0) {
+ /* printf("All edges removed\n"); */
+ return 0;
+ }
+
+
+ /* STAND VAN ZAKEN:
+ - eve->f :1= aanwezig in edges
+ - eve->xs :polynummer
+ - eve->h :aantal edges aan vertex
+ - eve->vn :bewaren! oorspronkelijke vertexnummer
+
+ - eed->f :
+ - eed->f1 :polynummer
+*/
+
+
+ /* STAP 3: POLYFILL STRUCT MAKEN */
+ pflist= (PolyFill *)MEM_callocN(poly*sizeof(PolyFill),"edgefill");
+ pf= pflist;
+ for(a=1;a<=poly;a++) {
+ pf->nr= a;
+ pf->min[0]=pf->min[1]=pf->min[2]= 1.0e20;
+ pf->max[0]=pf->max[1]=pf->max[2]= -1.0e20;
+ pf++;
+ }
+ eed= filledgebase.first;
+ while(eed) {
+ pflist[eed->f1-1].edges++;
+ eed= eed->next;
+ }
+
+ eve= fillvertbase.first;
+ while(eve) {
+ pflist[eve->xs-1].verts++;
+ minp= pflist[eve->xs-1].min;
+ maxp= pflist[eve->xs-1].max;
+
+ minp[cox]= (minp[cox])<(eve->co[cox]) ? (minp[cox]) : (eve->co[cox]);
+ minp[coy]= (minp[coy])<(eve->co[coy]) ? (minp[coy]) : (eve->co[coy]);
+ maxp[cox]= (maxp[cox])>(eve->co[cox]) ? (maxp[cox]) : (eve->co[cox]);
+ maxp[coy]= (maxp[coy])>(eve->co[coy]) ? (maxp[coy]) : (eve->co[coy]);
+ if(eve->h>2) pflist[eve->xs-1].f= 1;
+
+ eve= eve->next;
+ }
+
+ /* STAP 4: GATEN OF BOUNDS VINDEN EN SAMENVOEGEN
+ * ( bounds alleen om grote hoeveelheden een beetje in stukjes te verdelen,
+ * de edgefill heeft van zichzelf een adequate autogat!!!
+ * LET OP: WERKT ALLEEN ALS POLY'S GESORTEERD ZIJN!!! */
+
+ if(poly>1) {
+ short *polycache, *pc;
+
+ /* dus: eerst sorteren */
+ qsort(pflist, poly, sizeof(PolyFill), vergpoly);
+
+ /*pf= pflist;
+ for(a=1;a<=poly;a++) {
+ printf("poly:%d edges:%d verts:%d flag: %d\n",a,pf->edges,pf->verts,pf->f);
+ PRINT2(f, f, pf->min[0], pf->min[1]);
+ pf++;
+ }*/
+
+ polycache= pc= MEM_callocN(sizeof(short)*poly, "polycache");
+ pf= pflist;
+ for(a=0; a<poly; a++, pf++) {
+ for(c=a+1;c<poly;c++) {
+
+ /* als 'a' inside 'c': samenvoegen (ook bbox)
+ * Pas Op: 'a' kan ook inside andere poly zijn.
+ */
+ if(boundisect(pf, pflist+c)) {
+ *pc= c;
+ pc++;
+ }
+ /* alleen voor opt! */
+ /* else if(pf->max[cox] < (pflist+c)->min[cox]) break; */
+
+ }
+ while(pc!=polycache) {
+ pc--;
+ mergepolysSimp(pf, pflist+ *pc);
+ }
+ }
+ MEM_freeN(polycache);
+ }
+
+ pf= pflist;
+ /* printf("na merge\n");
+ for(a=1;a<=poly;a++) {
+ printf("poly:%d edges:%d verts:%d flag: %d\n",a,pf->edges,pf->verts,pf->f);
+ pf++;
+ } */
+
+ /* STAP 5: DRIEHOEKEN MAKEN */
+
+ tempve.first= fillvertbase.first;
+ tempve.last= fillvertbase.last;
+ temped.first= filledgebase.first;
+ temped.last= filledgebase.last;
+ fillvertbase.first=fillvertbase.last= 0;
+ filledgebase.first=filledgebase.last= 0;
+
+ pf= pflist;
+ for(a=0;a<poly;a++) {
+ if(pf->edges>1) {
+ splitlist(&tempve,&temped,pf->nr);
+ scanfill(pf);
+ }
+ pf++;
+ }
+ addlisttolist(&fillvertbase,&tempve);
+ addlisttolist(&filledgebase,&temped);
+
+ /* evl= fillvlakbase.first;
+ while(evl) {
+ printf("nieuw vlak %x %x %x\n",evl->v1,evl->v2,evl->v3);
+ evl= evl->next;
+ }*/
+
+
+ /* VRIJGEVEN */
+
+ MEM_freeN(pflist);
+ return 1;
+
+}
+
+/*
+ MOVED TO EDITMESH.C since it's really bad to leave it here
+
+void fill_mesh(void)
+{
+ EditVert *eve,*v1;
+ EditEdge *eed,*e1,*nexted;
+ EditVlak *evl,*nextvl;
+ short ok;
+
+ if(G.obedit==0 || (G.obedit->type!=OB_MESH)) return;
+
+ waitcursor(1);
+
+ / * alle selected vertices kopieeren * /
+ eve= G.edve.first;
+ while(eve) {
+ if(eve->f & 1) {
+ v1= addfillvert(eve->co);
+ eve->vn= v1;
+ v1->vn= eve;
+ v1->h= 0;
+ }
+ eve= eve->next;
+ }
+ / * alle selected edges kopieeren * /
+ eed= G.eded.first;
+ while(eed) {
+ if( (eed->v1->f & 1) && (eed->v2->f & 1) ) {
+ e1= addfilledge(eed->v1->vn, eed->v2->vn);
+ e1->v1->h++;
+ e1->v2->h++;
+ }
+ eed= eed->next;
+ }
+ / * van alle selected vlakken vertices en edges verwijderen om dubbels te voorkomen * /
+ / * alle edges tellen punten op, vlakken trekken af,
+ edges met vertices ->h<2 verwijderen * /
+ evl= G.edvl.first;
+ ok= 0;
+ while(evl) {
+ nextvl= evl->next;
+ if( vlakselectedAND(evl, 1) ) {
+ evl->v1->vn->h--;
+ evl->v2->vn->h--;
+ evl->v3->vn->h--;
+ if(evl->v4) evl->v4->vn->h--;
+ ok= 1;
+
+ }
+ evl= nextvl;
+ }
+ if(ok) { / * er zijn vlakken geselecteerd * /
+ eed= filledgebase.first;
+ while(eed) {
+ nexted= eed->next;
+ if(eed->v1->h<2 || eed->v2->h<2) {
+ remlink(&filledgebase,eed);
+ }
+ eed= nexted;
+ }
+ }
+
+ / * tijd=clock(); * /
+
+ ok= edgefill(0);
+
+ / * printf("time: %d\n",(clock()-tijd)/1000); * /
+
+ if(ok) {
+ evl= fillvlakbase.first;
+ while(evl) {
+ addvlaklist(evl->v1->vn, evl->v2->vn, evl->v3->vn, 0, evl);
+ evl= evl->next;
+ }
+ }
+ / * else printf("fill error\n"); * /
+
+ end_edgefill();
+
+ waitcursor(0);
+
+ countall();
+ allqueue(REDRAWVIEW3D, 0);
+}
+
+MOVED TO editmesh.c !!!!! (you bastards!)
+
+ */
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-17 06:02:48 +0300