boolean subtraction of two meshes in direct3D
Author
Hi all,
i'm working on a simple 3D CAD to create complex 3D objects. This application uses:
1. Direct3D to render the objects
2. The methods contained in the Mesh class (such as Mesh.Box(...)) to create them
3. The Matrix class to apply some basic transformations (such as Translation or Rotation)
My issue is to do a boolean subtraction of a Mesh to another one to create a more complex Mesh, for example a Mesh with holes.
Can someone help me?
Thanks in advance.
Moved to Graphics Programming. You're going to have to do this on your own; D3D/D3DX don't have anything that would help you. (Well, I guess you could do some stenciling tricks, but I don't think that's what you're after.)
Maybe search for a Constructive Surface Modelling toolkit?
http://en.wikipedia.org/wiki/Constructive_solid_geometry
The GNU Triangulated Surface Library sounds promising.
http://en.wikipedia.org/wiki/Constructive_solid_geometry
The GNU Triangulated Surface Library sounds promising.
heres what csg looks like, if you want to code it yourself.
#include "csg.h"#include "construct.h"#include "model.h"#include "tritri.h"#include "mgeneral.h"//make the ear clipper, you can make this function in the sector editor//and just copy it here, then theres a few more problems in the rest of the algorythm.void earclip(sc* c, scv*& ov,scp*& op, UINT& ovs, UINT& ops){ /* you have multiple circuits in c. the first circuit is the outer ring, the following circuits are inner rings. as we know now, you can do the whole thing with one ring including holes. have a list of points and a list of lines indexing these points. */ int lls=0; scl* ll=new scl[10000]; int i; for(i=0;i<c->vs[0];i++) { if(i<c->vs[0]-1) { ll.i[0]=i; ll.i[1]=i+1; } else { ll.i[0]=i; ll.i[1]=0; } } delete ll;}void tesselate(sc* c, scv*& ov, scp*& op, UINT& ovs, UINT& ops){ sdo* first_do=NULL; UINT vs=0; UINT ps=0; scv* v=new scv[MAX_TESSELATE_VERTICES]; scp* p=new scp[MAX_TESSELATE_POLYGONS]; int lvs=0; int lls=0; scv* lv=new scv[10000]; scl* ll=new scl[10000]; int lvcount=0; int llcount=0; int i; for(i=0;i<c->cs;i++) { int j; for(j=0;j<c->vs;j++) { lv[lvcount+j].pos=c->v2d[j]; v[lvcount+j].pos=c->v[j]; } for(j=0;j<c->vs;j++) { ll[llcount+j].i[0]=lvcount+j; if(j==c->vs-1) ll[llcount+j].i[1]=lvcount; else ll[llcount+j].i[1]=lvcount+j+1; } lvcount+=c->vs; llcount+=c->vs; } lvs=lvcount; vs=lvcount; lls=llcount; if(1) { sdo* new_do=new sdo; new_do->o[0]=0; new_do->o[1]=1; new_do->next=first_do; first_do=new_do; int o[2]={0,1}; int check; int poks=0; int pok[100]; bool done=false; while(!done) {startagain: sdo* this_do=first_do; if(this_do==NULL) done=true; else { o[0]=this_do->o[0]; o[1]=this_do->o[1]; first_do=this_do->next; delete this_do; poks=0; int ii; for(ii=0;ii<vs;ii++) { if(ii!=o[0] && ii!=o[1]) { check=ii; bool ok=true; //check if polygon has been made yet for(i=0;i<ps;i++) { if((p.i[0]==o[0] || p.i[1]==o[0] || p.i[2]==o[0]) &&(p.i[0]==o[1] || p.i[1]==o[1] || p.i[2]==o[1]) &&(p.i[0]==check || p.i[1]==check || p.i[2]==check)) { ok=false; } } //intersect o[0]->check and o[1]->check to see if it intersects an ll or its along the border which means its ok if(ok==true) { bool found=false; //for(i=0;i<llcount;i++) //{ // if((ll.i[0]==o[0] && ll.i[1]==check) || (ll.i[1]==o[0] && ll.i[0]==check)) found=true; //} if(found==false) { for(i=0;i<llcount;i++) { bool found; VEC pos; float pt1,pt2; found=intersect_line(lv[o[0]].pos,lv[check].pos,lv[ll.i[0]].pos,lv[ll.i[1]].pos,pos,pt1,pt2); if(found && pt1>=0.001f && pt1<=0.999f) ok=false; } } } if(ok==true) { bool found=false; //for(i=0;i<llcount;i++) //{ // if((ll.i[0]==o[1] && ll.i[1]==check) || (ll.i[1]==o[1] && ll.i[0]==check)) found=true; //} if(found==false) { for(i=0;i<llcount;i++) { bool found; VEC pos; float pt1,pt2; found=intersect_line(lv[o[1]].pos,lv[check].pos,lv[ll.i[0]].pos,lv[ll.i[1]].pos,pos,pt1,pt2); if(found && pt1>=0.001f && pt1<=0.999f) ok=false; } } } //check containment of (o[0]->check)/2 and (o[1]->check)/2 inside the polygon if(ok==true) { bool found=false; for(i=0;i<llcount;i++) { if((ll.i[0]==o[0] && ll.i[1]==check) || (ll.i[1]==o[0] && ll.i[0]==check)) found=true; } if(found==false) { int ints=0; for(i=0;i<llcount;i++) { bool found; VEC pos; float pt1,pt2; found=intersect_line((lv[o[0]].pos+lv[check].pos)/2,VEC(-1000,-1000,0),lv[ll.i[0]].pos,lv[ll.i[1]].pos,pos,pt1,pt2); if(found) ints++; } if(ints%2==0) ok=false; } } if(ok==true) { bool found=false; for(i=0;i<llcount;i++) { if((ll.i[0]==o[1] && ll.i[1]==check) || (ll.i[1]==o[1] && ll.i[0]==check)) found=true; } if(found==false) { int ints=0; for(i=0;i<llcount;i++) { bool found; VEC pos; float pt1,pt2; found=intersect_line((lv[o[1]].pos+lv[check].pos)/2,VEC(-1000,-1000,0),lv[ll.i[0]].pos,lv[ll.i[1]].pos,pos,pt1,pt2); if(found) ints++; } if(ints%2==0) ok=false; } } //check if another polygons point is contained inside the new polygon if(ok==true) { for(i=0;i<ps;i++) { if(lv[p.i[0]].pos!=lv[o[0]].pos && lv[p.i[0]].pos!=lv[o[1]].pos && lv[p.i[0]].pos!=lv[check].pos && lv[p.i[1]].pos!=lv[o[0]].pos && lv[p.i[1]].pos!=lv[o[1]].pos && lv[p.i[1]].pos!=lv[check].pos && lv[p.i[2]].pos!=lv[o[0]].pos && lv[p.i[2]].pos!=lv[o[1]].pos && lv[p.i[2]].pos!=lv[check].pos) { int j; for(j=0;j<3;j++) { VEC pos=lv[p.i[j]].pos; int ints=0; int k; for(k=0;k<3;k++) { VEC pos0,pos1; switch(k) { case 0:pos0=lv[o[0]].pos;pos1=lv[o[1]].pos;break; case 1:pos0=lv[o[1]].pos;pos1=lv[check].pos;break; case 2:pos0=lv[check].pos;pos1=lv[o[0]].pos;break; } bool found; VEC pos2; float pt1,pt2; found=intersect_line(pos,VEC(-1000,-1000,0),pos0,pos1,pos2,pt1,pt2); if(found) ints++; } if(ints%2==1) ok=false; } } } } //check if a line is contained inside the new polygon if(ok==true) { for(i=0;i<llcount;i++) { if(lv[ll.i[0]].pos!=lv[o[0]].pos && lv[ll.i[0]].pos!=lv[o[1]].pos && lv[ll.i[0]].pos!=lv[check].pos) { int ints=0; int j; for(j=0;j<3;j++) { VEC pos=lv[ll.i[0]].pos; VEC pos0,pos1; switch(j) { case 0:pos0=lv[o[0]].pos;pos1=lv[o[1]].pos;break; case 1:pos0=lv[o[1]].pos;pos1=lv[check].pos;break; case 2:pos0=lv[check].pos;pos1=lv[o[0]].pos;break; } bool found; VEC pos2; float pt1,pt2; found=intersect_line(pos,VEC(-1000,-1000,0),pos0,pos1,pos2,pt1,pt2); if(found) ints++; } if(ints%2==1) ok=false; } } } //check if o[0]->check intersects with a polygon if(ok==true) { bool found=false; for(i=0;i<ps;i++) { //if(p.i[0]==o[0] //|| p.i[1]==o[0] //|| p.i[2]==o[0] //|| p.i[0]==check //|| p.i[1]==check //|| p.i[2]==check) //{ // found=true; //} if(found==false) { VEC pos0,pos1; int j; for(j=0;j<3;j++) { switch(j) { case 0:pos0=lv[p.i[0]].pos;pos1=lv[p.i[1]].pos;break; case 1:pos0=lv[p.i[1]].pos;pos1=lv[p.i[2]].pos;break; case 2:pos0=lv[p.i[2]].pos;pos1=lv[p.i[0]].pos;break; } bool found; VEC pos; float pt1,pt2; found=intersect_line(lv[o[0]].pos,lv[check].pos,pos0,pos1,pos,pt1,pt2); if(found && pt1>=0.001f && pt1<=0.999f) ok=false; } } } } //check if o[1]->check intersects with a polygon if(ok==true) { bool found=false; for(i=0;i<ps;i++) { //if(p.i[0]==o[1] //|| p.i[1]==o[1] //|| p.i[2]==o[1] //|| p.i[0]==check //|| p.i[1]==check //|| p.i[2]==check) //{ // found=true; //} if(found==false) { VEC pos0,pos1; int j; for(j=0;j<3;j++) { switch(j) { case 0:pos0=lv[p.i[0]].pos;pos1=lv[p.i[1]].pos;break; case 1:pos0=lv[p.i[1]].pos;pos1=lv[p.i[2]].pos;break; case 2:pos0=lv[p.i[2]].pos;pos1=lv[p.i[0]].pos;break; } bool found; VEC pos; float pt1,pt2; found=intersect_line(lv[o[1]].pos,lv[check].pos,pos0,pos1,pos,pt1,pt2); if(found && pt1>=0.001f && pt1<=0.999f) ok=false; } } } }// check the angle of o0->check and o1->check if its the same then ok=false if(ok) { VEC vec0=(lv[o[0]].pos-lv[check].pos); VEC vec1=(lv[o[1]].pos-lv[check].pos); D3DXVec3Normalize(&vec0,&vec0); D3DXVec3Normalize(&vec1,&vec1); float angle=acosf(D3DXVec3Dot(&vec0,&vec1)); if(angle<0.001f) ok=false; } //if ok add the polygon if(ok) { pok[poks]=check; poks++; } } } if(poks>0) { float mindist=100000; for(i=0;i<poks;i++) { float dist=(float)hypot(lv[o[0]].pos.x-lv[pok].pos.x,lv[o[0]].pos.y-lv[pok].pos.y); if(dist<mindist) { mindist=dist; check=pok; } } p[ps].is=3; p[ps].i[0]=o[0]; p[ps].i[1]=o[1]; p[ps].i[2]=check; p[ps].h[0]=0; p[ps].h[1]=0; p[ps].h[2]=0; VEC nor=calculate_normal(lv[p[ps].i[0]].pos,lv[p[ps].i[1]].pos,lv[p[ps].i[2]].pos); if(nor.z>0) { int swap=p[ps].i[0]; p[ps].i[0]=p[ps].i[2]; p[ps].i[2]=swap; } //check if o[0]->check is not a border, if not add a todo struct for it bool ok2=true; for(i=0;i<llcount;i++) { if((ll.i[0]==o[0] && ll.i[1]==check) || (ll.i[1]==o[0] && ll.i[0]==check)) ok2=false; } //check if o[0]->check doesnt belong on a polygon already made for(i=0;i<ps;i++) { if(((o[0]==p.i[0] && check==p.i[1]) || (o[0]==p.i[1] && check==p.i[0])) && ((o[0]==p.i[1] && check==p.i[2]) || (o[0]==p.i[2] && check==p.i[1])) && ((o[0]==p.i[2] && check==p.i[0]) || (o[0]==p.i[0] && check==p.i[2]))) { ok2=false; } } if(ok2) { new_do=new sdo; new_do->o[0]=o[0]; new_do->o[1]=check; new_do->next=first_do; first_do=new_do; } //check if o[1]->check is not a border, if not add a todo struct for it ok2=true; for(i=0;i<llcount;i++) { if((ll.i[0]==o[1] && ll.i[1]==check) || (ll.i[1]==o[1] && ll.i[0]==check)) ok2=false; } //check if o[1]->check doesnt belong on a polygon already made for(i=0;i<ps;i++) { if(((o[1]==p.i[0] && check==p.i[1]) || (o[1]==p.i[1] && check==p.i[0])) && ((o[1]==p.i[1] && check==p.i[2]) || (o[1]==p.i[2] && check==p.i[1])) && ((o[1]==p.i[2] && check==p.i[0]) || (o[1]==p.i[0] && check==p.i[2]))) { ok2=false; } } if(ok2) { new_do=new sdo; new_do->o[0]=o[1]; new_do->o[1]=check; new_do->next=first_do; first_do=new_do; } ps++; goto startagain; } } } } delete ll; delete lv;/* bool check[100]; memset(check,0,100); for(i=0;i<ps;i++) { check[p.i[0]]=true; check[p.i[1]]=true; check[p.i[2]]=true; } for(i=0;i<vs;i++) { if(check==false) { int bp=1; } }*/ if(ps!=vs-2) { int bp=1; } //copy it across for(i=0;i<vs;i++) { ov[ovs+i].pos=v.pos; } for(i=0;i<ps;i++) { op[ops+i].is=p.is; op[ops+i].i[0]=p.i[0]+ovs; op[ops+i].i[1]=p.i[1]+ovs; op[ops+i].i[2]=p.i[2]+ovs; op[ops+i].i[3]=p.i[3]+ovs; op[ops+i].h[0]=0; op[ops+i].h[1]=0; op[ops+i].h[2]=0; op[ops+i].h[3]=0; } ovs+=vs; ops+=ps; delete v; delete p;}void csg(int type, int a, int b){ int o_vs=0; int o_ts=0; sv* o_v=new sv[100000]; st* o_t=new st[100000]; int a_vs; int a_ts; sv* a_v; st* a_t; int b_vs; int b_ts; sv* b_v; st* b_t; int i; int is=0; ////////////////////////////////////////////////////// // CALCULATE ADJACENCY for(i=0;i<2;i++) { switch(i) { case 0: a_vs=model[a].vs; a_v=model[a].v; a_ts=model[a].ts; a_t=model[a].t; break; case 1: a_vs=model.vs; a_v=model.v; a_ts=model.ts; a_t=model.t; break; } int* vertpolys; int* vertpoly; vertpolys=new int[a_vs]; memset(vertpolys,0,sizeof(int)*a_vs); vertpoly=new int[a_vs*MAX_FAN]; //if theres a fan bigger than 10 triangles, itll crash int j; for(j=0;j<a_ts;j++) { int k; for(k=0;k<3;k++) { vertpoly[a_t[j].i[k]*MAX_FAN+vertpolys[a_t[j].i[k]]]=j; vertpolys[a_t[j].i[k]]++; } } for(j=0;j<a_ts;j++) { int k; for(k=0;k<3;k++) { a_t[j].adj[k]=-1; int vert[2]; vert[0]=a_t[j].i[k]; if(k==2) vert[1]=a_t[j].i[0]; else vert[1]=a_t[j].i[k+1]; int l; for(l=0;l<vertpolys[vert[0]];l++) { int tri=vertpoly[vert[0]*MAX_FAN+l]; if(tri!=j) { if((vert[0]==a_t[tri].i[0] || vert[0]==a_t[tri].i[1] || vert[0]==a_t[tri].i[2]) &&(vert[1]==a_t[tri].i[0] || vert[1]==a_t[tri].i[1] || vert[1]==a_t[tri].i[2])) { a_t[j].adj[k]=tri; } } } } } delete vertpolys; delete vertpoly; } output_vs=0; output_texts=0; screenvertex* sov; output_v->Lock(0,0,(void**)&sov,NULL); int tc=0; int circ=0; for(i=0;i<2;i++) { tc=0; circ=0; switch(i) { case 0: a_vs=model[a].vs; a_v=model[a].v; a_ts=model[a].ts; a_t=model[a].t; b_vs=model.vs; b_v=model.v; b_ts=model.ts; b_t=model.t; break; case 1: a_vs=model.vs; a_v=model.v; a_ts=model.ts; a_t=model.t; b_vs=model[a].vs; b_v=model[a].v; b_ts=model[a].ts; b_t=model[a].t; break; } int j; for(j=0;j<a_ts;j++) { //PLANE p1,p2; bool found_coplanar=false; int ctris=0; int ctri[1000]; int itris=0; int itri[1000]; VEC itri_nor[1000]; float tri0[3][3]; float tri1[3][3]; VEC nor[2]; tri0[0][0]=a_v[a_t[j].i[0]].pos.x; tri0[0][1]=a_v[a_t[j].i[0]].pos.y; tri0[0][2]=a_v[a_t[j].i[0]].pos.z; tri0[1][0]=a_v[a_t[j].i[1]].pos.x; tri0[1][1]=a_v[a_t[j].i[1]].pos.y; tri0[1][2]=a_v[a_t[j].i[1]].pos.z; tri0[2][0]=a_v[a_t[j].i[2]].pos.x; tri0[2][1]=a_v[a_t[j].i[2]].pos.y; tri0[2][2]=a_v[a_t[j].i[2]].pos.z; //D3DXPlaneFromPoints(&p1,&a_v[a_t[j].i[0]].pos,&a_v[a_t[j].i[1]].pos,&a_v[a_t[j].i[2]].pos); //D3DXPlaneNormalize(&p1,&p1); nor[0]=calculate_normal(a_v[a_t[j].i[0]].pos,a_v[a_t[j].i[1]].pos,a_v[a_t[j].i[2]].pos); int k; for(k=0;k<b_ts;k++) { //tri tri intersect a_t with b_t tri1[0][0]=b_v[b_t[k].i[0]].pos.x; tri1[0][1]=b_v[b_t[k].i[0]].pos.y; tri1[0][2]=b_v[b_t[k].i[0]].pos.z; tri1[1][0]=b_v[b_t[k].i[1]].pos.x; tri1[1][1]=b_v[b_t[k].i[1]].pos.y; tri1[1][2]=b_v[b_t[k].i[1]].pos.z; tri1[2][0]=b_v[b_t[k].i[2]].pos.x; tri1[2][1]=b_v[b_t[k].i[2]].pos.y; tri1[2][2]=b_v[b_t[k].i[2]].pos.z; //D3DXPlaneFromPoints(&p2,&b_v[b_t[j].i[0]].pos,&b_v[b_t[j].i[1]].pos,&b_v[b_t[j].i[2]].pos); //D3DXPlaneNormalize(&p2,&p2); nor[1]=calculate_normal(b_v[b_t[k].i[0]].pos,b_v[b_t[k].i[1]].pos,b_v[b_t[k].i[2]].pos); int found=false; int cp=0; float isp[2][3]; found=tri_tri_intersect_with_isectline(tri0[0],tri0[1],tri0[2],tri1[0],tri1[1],tri1[2],&cp,isp[0],isp[1]); VEC orig; VEC dir; //cp=plane2(p1,p2,orig,dir); //heres the tri tri fashion from the ray tri, and it didnt make a difference, there is still missing triangles. /* if(cp==0) { VEC orig,dir; float length; bool fnd=false; float t,u,v; orig=VEC(tri0[0][0],tri0[0][1],tri0[0][2]); dir=VEC(tri0[1][0],tri0[1][1],tri0[1][2])-orig; length=D3DXVec3Length(&dir); D3DXVec3Normalize(&dir,&dir); if(fnd==false) { fnd=intersect_triangle(orig,dir,VEC(tri1[0][0],tri1[0][1],tri1[0][2]) ,VEC(tri1[1][0],tri1[1][1],tri1[1][2]) ,VEC(tri1[2][0],tri1[2][1],tri1[2][2]),&t,&u,&v); if(t<0 || t>length) fnd=false; } if(fnd==false) { fnd=intersect_triangle(orig,dir,VEC(tri1[2][0],tri1[2][1],tri1[2][2]) ,VEC(tri1[1][0],tri1[1][1],tri1[1][2]) ,VEC(tri1[0][0],tri1[0][1],tri1[0][2]),&t,&u,&v); if(t<0 || t>length) fnd=false; } orig=VEC(tri0[1][0],tri0[1][1],tri0[1][2]); dir=VEC(tri0[2][0],tri0[2][1],tri0[2][2])-orig; length=D3DXVec3Length(&dir); D3DXVec3Normalize(&dir,&dir); if(fnd==false) { fnd=intersect_triangle(orig,dir,VEC(tri1[0][0],tri1[0][1],tri1[0][2]) ,VEC(tri1[1][0],tri1[1][1],tri1[1][2]) ,VEC(tri1[2][0],tri1[2][1],tri1[2][2]),&t,&u,&v); if(t<0 || t>length) fnd=false; } if(fnd==false) { fnd=intersect_triangle(orig,dir,VEC(tri1[2][0],tri1[2][1],tri1[2][2]) ,VEC(tri1[1][0],tri1[1][1],tri1[1][2]) ,VEC(tri1[0][0],tri1[0][1],tri1[0][2]),&t,&u,&v); if(t<0 || t>length) fnd=false; } orig=VEC(tri0[2][0],tri0[2][1],tri0[2][2]); dir=VEC(tri0[0][0],tri0[0][1],tri0[0][2])-orig; length=D3DXVec3Length(&dir); D3DXVec3Normalize(&dir,&dir); if(fnd==false) { fnd=intersect_triangle(orig,dir,VEC(tri1[0][0],tri1[0][1],tri1[0][2]) ,VEC(tri1[1][0],tri1[1][1],tri1[1][2]) ,VEC(tri1[2][0],tri1[2][1],tri1[2][2]),&t,&u,&v); if(t<0 || t>length) fnd=false; } if(fnd==false) { fnd=intersect_triangle(orig,dir,VEC(tri1[2][0],tri1[2][1],tri1[2][2]) ,VEC(tri1[1][0],tri1[1][1],tri1[1][2]) ,VEC(tri1[0][0],tri1[0][1],tri1[0][2]),&t,&u,&v); if(t<0 || t>length) fnd=false; } orig=VEC(tri1[0][0],tri1[0][1],tri1[0][2]); dir=VEC(tri1[1][0],tri1[1][1],tri1[1][2])-orig; length=D3DXVec3Length(&dir); D3DXVec3Normalize(&dir,&dir); if(fnd==false) { fnd=intersect_triangle(orig,dir,VEC(tri0[0][0],tri0[0][1],tri0[0][2]) ,VEC(tri0[1][0],tri0[1][1],tri0[1][2]) ,VEC(tri0[2][0],tri0[2][1],tri0[2][2]),&t,&u,&v); if(t<0 || t>length) fnd=false; } if(fnd==false) { fnd=intersect_triangle(orig,dir,VEC(tri0[2][0],tri0[2][1],tri0[2][2]) ,VEC(tri0[1][0],tri0[1][1],tri0[1][2]) ,VEC(tri0[0][0],tri0[0][1],tri0[0][2]),&t,&u,&v); if(t<0 || t>length) fnd=false; } orig=VEC(tri1[1][0],tri1[1][1],tri1[1][2]); dir=VEC(tri1[2][0],tri1[2][1],tri1[2][2])-orig; length=D3DXVec3Length(&dir); D3DXVec3Normalize(&dir,&dir); if(fnd==false) { fnd=intersect_triangle(orig,dir,VEC(tri0[0][0],tri0[0][1],tri0[0][2]) ,VEC(tri0[1][0],tri0[1][1],tri0[1][2]) ,VEC(tri0[2][0],tri0[2][1],tri0[2][2]),&t,&u,&v); if(t<0 || t>length) fnd=false; } if(fnd==false) { fnd=intersect_triangle(orig,dir,VEC(tri0[2][0],tri0[2][1],tri0[2][2]) ,VEC(tri0[1][0],tri0[1][1],tri0[1][2]) ,VEC(tri0[0][0],tri0[0][1],tri0[0][2]),&t,&u,&v); if(t<0 || t>length) fnd=false; } orig=VEC(tri1[2][0],tri1[2][1],tri1[2][2]); dir=VEC(tri1[0][0],tri1[0][1],tri1[0][2])-orig; length=D3DXVec3Length(&dir); D3DXVec3Normalize(&dir,&dir); if(fnd==false) { fnd=intersect_triangle(orig,dir,VEC(tri0[0][0],tri0[0][1],tri0[0][2]) ,VEC(tri0[1][0],tri0[1][1],tri0[1][2]) ,VEC(tri0[2][0],tri0[2][1],tri0[2][2]),&t,&u,&v); if(t<0 || t>length) fnd=false; } if(fnd==false) { fnd=intersect_triangle(orig,dir,VEC(tri0[2][0],tri0[2][1],tri0[2][2]) ,VEC(tri0[1][0],tri0[1][1],tri0[1][2]) ,VEC(tri0[0][0],tri0[0][1],tri0[0][2]),&t,&u,&v); if(t<0 || t>length) fnd=false; } if(fnd) found=1; }*/ if(found==1) { if(cp==1) { //coplanar found_coplanar=true; //add b_t[k] to a list of coplanar tris ctri[ctris]=k; ctris++; } else { //noncoplanar //add b_t[k] to a list of noncoplanar tris itri[itris]=k; itri_nor[itris]=nor[1]; itris++; } } } //if noncoplanar do the triangle scissor //if coplanar do the coplanar cut <- not implementing yet //if intersection isnt true then do containment test and reject else add it to o_vs if(itris==0 && ctris==0) { //do containment test, if it passes add it to the output primitive VEC raypos=VEC((a_v[a_t[j].i[0]].pos.x +a_v[a_t[j].i[1]].pos.x +a_v[a_t[j].i[2]].pos.x)/3.0f ,(a_v[a_t[j].i[0]].pos.y +a_v[a_t[j].i[1]].pos.y +a_v[a_t[j].i[2]].pos.y)/3.0f ,(a_v[a_t[j].i[0]].pos.z +a_v[a_t[j].i[1]].pos.z +a_v[a_t[j].i[2]].pos.z)/3.0f); VEC raydir=VEC(1,0,0); int ints=0; for(k=0;k<b_ts;k++) { float t,u,v; bool found; found=intersect_triangle(raypos,raydir,b_v[b_t[k].i[0]].pos,b_v[b_t[k].i[1]].pos,b_v[b_t[k].i[2]].pos,&t,&u,&v); if(t<0) found=false; if(found==false) { found=intersect_triangle(raypos,raydir,b_v[b_t[k].i[2]].pos,b_v[b_t[k].i[1]].pos,b_v[b_t[k].i[0]].pos,&t,&u,&v); } if(found && t>=0) ints++; } bool outside=false; if(ints%2==0) outside=true; bool add=false; bool invert=false; switch(i) { case 0: switch(type) { case 0://union if(outside) { add=true; invert=false; } break; case 1://subtraction if(outside==false) { add=true; invert=true; } break; case 2://intersection if(outside==false) { add=true; invert=false; } break; } break; case 1: switch(type) { case 0://union if(outside) { add=true; invert=false; } break; case 1://subtraction if(outside) { add=true; invert=false; } break; case 2://intersection if(outside==false) { add=true; invert=false; } break; } break; } if(add) { if(invert) { o_v[o_vs+0].pos=a_v[a_t[j].i[2]].pos; o_v[o_vs+1].pos=a_v[a_t[j].i[1]].pos; o_v[o_vs+2].pos=a_v[a_t[j].i[0]].pos; o_t[o_ts].i[0]=o_vs+0; o_t[o_ts].i[1]=o_vs+1; o_t[o_ts].i[2]=o_vs+2; o_vs+=3; o_ts+=1; } else { o_v[o_vs+0].pos=a_v[a_t[j].i[0]].pos; o_v[o_vs+1].pos=a_v[a_t[j].i[1]].pos; o_v[o_vs+2].pos=a_v[a_t[j].i[2]].pos; o_t[o_ts].i[0]=o_vs+0; o_t[o_ts].i[1]=o_vs+1; o_t[o_ts].i[2]=o_vs+2; o_vs+=3; o_ts+=1; } } } else { if(found_coplanar) { //dont do anything here yet } else { if(i==1 && j==7) { int bp=1; } int edges=0; int edge_end[100][2]; int edge_points[100]; VEC edge[100][100]; VEC edge2d[100][100]; VEC edge_nor[100]; int holes=0; int hole_points[100]; VEC hole[100][100]; VEC hole2d[100][100]; //start from itri[0] and keep grabbing adjacent triangles until theres none left //and thats the tri to start from. //if its a hole then youll finish where you started, so you can make 2 code paths. bool dtri[1000]; bool dntri[1000]; memset(dntri,0,1000); int t=0;donextedge: memset(dtri,0,1000); bool ishole=false; bool done=false; while(!done) { dtri[t]=true; bool found=false; int checks=0; int k; for(k=0;k<itris;k++) { if(t!=k) { if((b_t[itri[t]].adj[0]==itri[k] || b_t[itri[t]].adj[1]==itri[k] || b_t[itri[t]].adj[2]==itri[k]) && dntri[k]==false) { checks++; } if(dtri[k]==false && dntri[k]==false) { if(b_t[itri[t]].adj[0]==itri[k] || b_t[itri[t]].adj[1]==itri[k] || b_t[itri[t]].adj[2]==itri[k]) { t=k; found=true; goto skipout; } } } }skipout: if(found==false) { if(checks==0 && itris>1) { int bp=1; } if(checks==2) { ishole=true; } else { ishole=false; } done=true; } } int ccount=0; //make a poly by scissoring the intersecting tris with the a tri //your intersecting tris are in itri. if(ishole) { int bp=1; //scan in the hole //then check if it has gone outside //the triangle, if it has convert it to //an edge cut //you actually find these as you make the hole, and pass them //out as edges instead of holes. hole_points[holes]=0; holes++; } else { int ti=t; int cnt=0; PLANE pl[3]; VEC tri00,tri01,tri02; VEC tri10,tri11,tri12; VEC tri20,tri21,tri22; D3DXPlaneFromPoints(&pl[0],&a_v[a_t[j].i[0]].pos,&a_v[a_t[j].i[1]].pos,&a_v[a_t[j].i[2]].pos); D3DXPlaneNormalize(&pl[0],&pl[0]); tri00=a_v[a_t[j].i[0]].pos; tri01=a_v[a_t[j].i[1]].pos; tri02=a_v[a_t[j].i[2]].pos; memset(dtri,0,1000); //find start edge //D3DXPlaneFromPoints(&pl[1],&b_v[b_t[itri[t]].i[0]].pos,&b_v[b_t[itri[t]].i[1]].pos,&b_v[b_t[itri[t]].i[2]].pos); //D3DXPlaneNormalize(&pl[1],&pl[1]); tri10=b_v[b_t[itri[t]].i[0]].pos; tri11=b_v[b_t[itri[t]].i[1]].pos; tri12=b_v[b_t[itri[t]].i[2]].pos; int k; for(k=0;k<3;k++) { switch(k) { case 0: //D3DXPlaneFromPoints(&pl[2],&a_v[a_t[j].i[0]].pos,&a_v[a_t[j].i[1]].pos,&((a_v[a_t[j].i[0]].pos+a_v[a_t[j].i[1]].pos)/2+nor[0])); //D3DXPlaneNormalize(&pl[2],&pl[2]); tri20=a_v[a_t[j].i[0]].pos; tri21=a_v[a_t[j].i[1]].pos; tri22=((a_v[a_t[j].i[0]].pos+a_v[a_t[j].i[1]].pos)/2+nor[0]); break; case 1: //D3DXPlaneFromPoints(&pl[2],&a_v[a_t[j].i[1]].pos,&a_v[a_t[j].i[2]].pos,&((a_v[a_t[j].i[1]].pos+a_v[a_t[j].i[2]].pos)/2+nor[0])); //D3DXPlaneNormalize(&pl[2],&pl[2]); tri20=a_v[a_t[j].i[1]].pos; tri21=a_v[a_t[j].i[2]].pos; tri22=((a_v[a_t[j].i[1]].pos+a_v[a_t[j].i[2]].pos)/2+nor[0]); break; case 2: //D3DXPlaneFromPoints(&pl[2],&a_v[a_t[j].i[2]].pos,&a_v[a_t[j].i[0]].pos,&((a_v[a_t[j].i[2]].pos+a_v[a_t[j].i[0]].pos)/2+nor[0])); //D3DXPlaneNormalize(&pl[2],&pl[2]); tri20=a_v[a_t[j].i[2]].pos; tri21=a_v[a_t[j].i[0]].pos; tri22=((a_v[a_t[j].i[2]].pos+a_v[a_t[j].i[0]].pos)/2+nor[0]); break; } //VEC point=plane3(pl[0],pl[1],pl[2]); //int cpi; //VEC point=tritritri(tri00,tri01,tri02 // ,tri20,tri21,tri22 // ,tri10,tri11,tri12, cpi); VEC point; if(1) { VEC orig,dir; orig=tri20; dir=tri21; dir-=orig; float length; length=D3DXVec3Length(&dir); D3DXVec3Normalize(&dir,&dir); bool f; float t,u,v; f=intersect_triangle(orig,dir,tri10,tri11,tri12,&t,&u,&v); if(t<0 || t>length) f=false; if(f==false) { f=intersect_triangle(orig,dir,tri12,tri11,tri10,&t,&u,&v); } if(f && t>=0 && t<=length) point=orig+dir*t; else point=VEC(-100000,-100000,-100000); } bool outside=false; if(point==VEC(-100000,-100000,-100000)) outside=true; if(outside==false) { edge_end[edges][cnt]=k; edge[edges][cnt]=point; cnt++; } } if(cnt==2) { //the triangle has only one cutting triangle in it, which made 2 edge verts and that was it dntri[t]=true; edge_nor[edges]=itri_nor[ti]; ccount=2; } else { int corner=cnt; ccount=corner; edge_nor[edges]=itri_nor[ti]; done=false; while(!done) { done=true;getnextcorner: D3DXPlaneFromPoints(&pl[1],&b_v[b_t[itri[t]].i[0]].pos,&b_v[b_t[itri[t]].i[1]].pos,&b_v[b_t[itri[t]].i[2]].pos); D3DXPlaneNormalize(&pl[1],&pl[1]);// tri10=b_v[b_t[itri[t]].i[0]].pos;// tri11=b_v[b_t[itri[t]].i[1]].pos;// tri12=b_v[b_t[itri[t]].i[2]].pos; dntri[t]=true; dtri[t]=true; int checks=0; int k; for(k=0;k<itris;k++) { if(k!=t) { if((b_t[itri[t]].adj[0]==itri[k] || b_t[itri[t]].adj[1]==itri[k] || b_t[itri[t]].adj[2]==itri[k]) && dntri[k]==false) { checks++; } if(dtri[k]==false && dntri[k]==false) { if(b_t[itri[t]].adj[0]==itri[k] || b_t[itri[t]].adj[1]==itri[k] || b_t[itri[t]].adj[2]==itri[k]) { D3DXPlaneFromPoints(&pl[2],&b_v[b_t[itri[k]].i[0]].pos,&b_v[b_t[itri[k]].i[1]].pos,&b_v[b_t[itri[k]].i[2]].pos); D3DXPlaneNormalize(&pl[2],&pl[2]); //tri20=b_v[b_t[itri[k]].i[0]].pos; //tri21=b_v[b_t[itri[k]].i[1]].pos; //tri22=b_v[b_t[itri[k]].i[2]].pos; //check if the two planes are coplanar //if they are, then you skip this one and go to the next. //pl[1] and pl[2]/* if(fabs(pl[1].a-pl[2].a)<0.001f && fabs(pl[1].b-pl[2].b)<0.001f && fabs(pl[1].c-pl[2].c)<0.001f && fabs(pl[1].d-pl[2].d)<0.001f) { t=k; done=false; } else { */// VEC point=plane3(pl[0],pl[1],pl[2]); int cpi; VEC orig,dir; cpi=plane2(pl[1],pl[2],orig,dir); //int cpi; //VEC point=tritritri(tri10,tri11,tri12 // ,tri20,tri21,tri22 // ,tri00,tri21,tri02, cpi); VEC point=VEC(-100000,-100000,-100000); // if(cpi==0) lineplane(point, orig, dir, pl[0]); /* do a triangle intersection, if its outside the triangle then quit out and cut it off at the edge */ if(cpi==1) { //pl[1] and pl[2] are coplanar. /* this means the point is exactly where the two planes meet. make the line out of one of the adjacent edges make orig and dir from that. */ int side; if(b_t[itri[t]].adj[0]==itri[k]) side=0; if(b_t[itri[t]].adj[1]==itri[k]) side=1; if(b_t[itri[t]].adj[2]==itri[k]) side=2; switch(side) { case 0: orig=b_v[b_t[itri[t]].i[0]].pos; dir=b_v[b_t[itri[t]].i[1]].pos; dir-=orig; D3DXVec3Normalize(&dir,&dir); break; case 1: orig=b_v[b_t[itri[t]].i[1]].pos; dir=b_v[b_t[itri[t]].i[2]].pos; dir-=orig; D3DXVec3Normalize(&dir,&dir); break; case 2: orig=b_v[b_t[itri[t]].i[2]].pos; dir=b_v[b_t[itri[t]].i[0]].pos; dir-=orig; D3DXVec3Normalize(&dir,&dir); break; } cpi=0; } bool in=false; if(cpi==0) { bool f; float t,u,v; f=intersect_triangle(orig,dir,tri00,tri01,tri02,&t,&u,&v); if(t<0.0f) f=false; if(!f) { f=intersect_triangle(orig,dir,tri02,tri01,tri00,&t,&u,&v); } if(f && t>=0) {in=true;point=orig+dir*t;} else { f=intersect_triangle(orig,-dir,tri00,tri01,tri02,&t,&u,&v); if(t<0.0f) f=false; if(!f) { f=intersect_triangle(orig,-dir,tri02,tri01,tri00,&t,&u,&v); } if(f && t>=0) {in=true;point=orig-dir*t;} } } else { in=true; } if(in) { if(cpi==0) { edge[edges][corner]=point; corner++; ccount=corner; t=k; done=false; } //} goto getnextcorner; } else { checks=1; } } } } } if(checks==1 || checks==0) { //find end edge// D3DXPlaneFromPoints(&pl[1],&b_v[b_t[itri[t]].i[0]].pos,&b_v[b_t[itri[t]].i[1]].pos,&b_v[b_t[itri[t]].i[2]].pos);// D3DXPlaneNormalize(&pl[1],&pl[1]); tri10=b_v[b_t[itri[t]].i[0]].pos; tri11=b_v[b_t[itri[t]].i[1]].pos; tri12=b_v[b_t[itri[t]].i[2]].pos; int k; for(k=0;k<3;k++) { switch(k) { case 0: //D3DXPlaneFromPoints(&pl[2],&a_v[a_t[j].i[0]].pos,&a_v[a_t[j].i[1]].pos,&((a_v[a_t[j].i[0]].pos+a_v[a_t[j].i[1]].pos)/2+nor[0])); //D3DXPlaneNormalize(&pl[2],&pl[2]); tri20=a_v[a_t[j].i[0]].pos; tri21=a_v[a_t[j].i[1]].pos; tri22=((a_v[a_t[j].i[0]].pos+a_v[a_t[j].i[1]].pos)/2+nor[0]); break; case 1:// D3DXPlaneFromPoints(&pl[2],&a_v[a_t[j].i[1]].pos,&a_v[a_t[j].i[2]].pos,&((a_v[a_t[j].i[1]].pos+a_v[a_t[j].i[2]].pos)/2+nor[0]));// D3DXPlaneNormalize(&pl[2],&pl[2]); tri20=a_v[a_t[j].i[1]].pos; tri21=a_v[a_t[j].i[2]].pos; tri22=((a_v[a_t[j].i[1]].pos+a_v[a_t[j].i[2]].pos)/2+nor[0]); break; case 2:// D3DXPlaneFromPoints(&pl[2],&a_v[a_t[j].i[2]].pos,&a_v[a_t[j].i[0]].pos,&((a_v[a_t[j].i[2]].pos+a_v[a_t[j].i[0]].pos)/2+nor[0]));// D3DXPlaneNormalize(&pl[2],&pl[2]); tri20=a_v[a_t[j].i[2]].pos; tri21=a_v[a_t[j].i[0]].pos; tri22=((a_v[a_t[j].i[2]].pos+a_v[a_t[j].i[0]].pos)/2+nor[0]); break; } VEC point; if(1) { VEC orig,dir; orig=tri20; dir=tri21; dir-=orig; float length; length=D3DXVec3Length(&dir); D3DXVec3Normalize(&dir,&dir); bool f; float t,u,v; f=intersect_triangle(orig,dir,tri10,tri11,tri12,&t,&u,&v); if(t<0 || t>length) f=false; if(f==false) { f=intersect_triangle(orig,dir,tri12,tri11,tri10,&t,&u,&v); } if(f && t>0 && t<=length) point=orig+dir*t; else point=VEC(-100000,-100000,-100000); } bool outside=false; if(point==VEC(-100000,-100000,-100000)) outside=true; if(outside==false) { edge_end[edges][1]=k; edge[edges][corner]=point; corner++; ccount=corner; done=true; } } } else { int bp=1; } } } edge_points[edges]=ccount; edges++; for(k=0;k<itris;k++) { if(dntri[k]==0) { t=k; goto donextedge; } } } //make rotation D3DXMATRIX roty; D3DXMATRIX rot,temp,temp2; D3DXVECTOR3 rotter=D3DXVECTOR3(0.0f,0.0f,0.0f); D3DXVECTOR3 look=VEC((float)nor[0].x,(float)nor[0].y,(float)nor[0].z); rotter.y=(float)atan2(look.z, -look.x)+1.57f; D3DXMatrixRotationYawPitchRoll(&roty, -rotter.y, 0.0f, 0.0f); D3DXVec3TransformCoord(&look, &look, &roty); rotter.x=(float)atan2(look.z, look.y)+1.57f; D3DXMatrixRotationX(&temp, -rotter.x); D3DXMatrixRotationY(&temp2, -rotter.y); D3DXMatrixMultiply(&rot, &temp2, &temp); VEC tri2d[3]; TV(&tri2d[0],&a_v[a_t[j].i[0]].pos,&rot); TV(&tri2d[1],&a_v[a_t[j].i[1]].pos,&rot); TV(&tri2d[2],&a_v[a_t[j].i[2]].pos,&rot); tri2d[0].z=0.0f; tri2d[1].z=0.0f; tri2d[2].z=0.0f; VEC av=(tri2d[0]+tri2d[1]+tri2d[2])/3.0f; tri2d[0]-=av; tri2d[1]-=av; tri2d[2]-=av; //calculate the edges and holes 2d positions for(k=0;k<edges;k++) { TV(&edge_nor[k],&edge_nor[k],&rot); int l; for(l=0;l<edge_points[k];l++) { TV(&edge2d[k][l],&edge[k][l],&rot); //edge2d[k][l].x=av.x+rand()%100; //edge2d[k][l].y=av.y+rand()%100; edge2d[k][l].z=0.0f; edge2d[k][l]-=av; } } int bp; if(i==1 && j==7) { int bp=1; } //flip edges for(k=0;k<edges;k++) { float angle=(float)atan2(edge2d[k][1].x-edge2d[k][0].x,edge2d[k][1].y-edge2d[k][0].y); float norangle=(float)atan2(edge_nor[k].x,edge_nor[k].y)+1.570796; VEC pv1=VEC(sinf(angle),cosf(angle),0); VEC pv2=VEC(sinf(norangle),cosf(norangle),0); float dot=D3DXVec3Dot(&pv1,&pv2); if(acosf(dot)<1.5f) { int tedge_end[2]; VEC tedge[100]; VEC tedge2d[100]; memcpy(tedge_end,edge_end[k],4*2); memcpy(tedge,edge[k],sizeof(VEC)*edge_points[k]); memcpy(tedge2d,edge2d[k],sizeof(VEC)*edge_points[k]); int l; for(l=0;l<edge_points[k];l++) { edge[k][l]=tedge[edge_points[k]-(l+1)]; edge2d[k][l]=tedge2d[edge_points[k]-(l+1)]; } edge_end[k][0]=tedge_end[1]; edge_end[k][1]=tedge_end[0]; } } for(k=0;k<holes;k++) { int l; for(l=0;l<hole_points[k];l++) { } } //make ordered edge pointers //go through the edge list, and populate the sides with edge connections. int sides[3]={0,0,0}; int side[3][1000]; int side_end[3][1000]; if(i==1 && j==7) { int bp=1; } for(k=0;k<edges;k++) { side[edge_end[k][0]][sides[edge_end[k][0]]]=k; side_end[edge_end[k][0]][sides[edge_end[k][0]]]=0; sides[edge_end[k][0]]++; side[edge_end[k][1]][sides[edge_end[k][1]]]=k; side_end[edge_end[k][1]][sides[edge_end[k][1]]]=1; sides[edge_end[k][1]]++; } //order each side in order of distance from the starting vertex of the side of the triangle for(k=0;k<3;k++) { if(sides[k]>0) { VEC start,stop; switch(k) { case 0:start=a_v[a_t[j].i[0]].pos;stop=a_v[a_t[j].i[1]].pos;break; case 1:start=a_v[a_t[j].i[1]].pos;stop=a_v[a_t[j].i[2]].pos;break; case 2:start=a_v[a_t[j].i[2]].pos;stop=a_v[a_t[j].i[0]].pos;break; } VEC len=stop-start; len.x=fabs(len.x); len.y=fabs(len.y); len.z=fabs(len.z); bool usex=false,usey=false,usez=false; bool up=false; if(len.x>=len.y && len.x>=len.z){usex=true;} if(len.y>=len.x && len.y>=len.z){usey=true;} if(len.z>=len.x && len.z>=len.y){usez=true;} if(usex) {usey=false;usez=false;} if(usey) {usex=false;usez=false;} if(usez) {usex=false;usey=false;} if(usex) if(stop.x>=start.x) up=true; if(usey) if(stop.y>=start.y) up=true; if(usez) if(stop.z>=start.z) up=true; float magnitude[100]; //you have to sort side and side end int l; for(l=0;l<sides[k];l++) { VEC pos; if(side_end[k][l]==0) { pos=edge[side[k][l]][0]; } else { pos=edge[side[k][l]][edge_points[side[k][l]]-1]; } if(usex) magnitude[l]=pos.x; if(usey) magnitude[l]=pos.y; if(usez) magnitude[l]=pos.z; } int tside[1000]; int tside_end[1000]; bool fnd; float mag; int st=0; bool dsort=false; while(!dsort) { if(up) mag=1000000; else mag=-1000000; fnd=false; int sort; int l; for(l=0;l<sides[k];l++) { if(up) { if(magnitude[l]<mag) { mag=magnitude[l]; sort=l; fnd=true; } } else { if(magnitude[l]>mag) { mag=magnitude[l]; sort=l; fnd=true; } } } if(fnd) { if(up) { magnitude[sort]=1000000; } else { magnitude[sort]=-1000000; } tside[st]=side[k][sort]; tside_end[st]=side_end[k][sort]; st++; } else { dsort=true; } } for(l=0;l<sides[k];l++) { side[k][l]=tside[l]; side_end[k][l]=tside_end[l]; } } } if(i==1 && j==7) { int bp=1; } bool segmentdone[3*1000]; //once all the segments are done the triangle is fully scanned memset(segmentdone,0,3*1000); int segments[3]; int circuit[3][1000]; //the segments circuit index, for what circuit is at its end, if its null, its the last segment and it points to the next side. (1 point is // generated) int circuit_side[3][1000]; //whether the segment points to the start or the finish of the edge int side_follow_start[1000]; //which segment each circuit ends at, for going from the circuit to the edge of the triangle int side_follow_end[1000]; //which segment each circuit ends at, for going from the circuit to the edge of the triangle int seg_follow_start[1000]; //which segment each circuit ends at, for going from the circuit to the edge of the triangle int seg_follow_end[1000]; //which segment each circuit ends at, for going from the circuit to the edge of the triangle for(k=0;k<3;k++) { if(sides[k]==0) { segments[k]=1; circuit[k][0]=-1; circuit_side[k][0]=-1; } else { int l; segments[k]=sides[k]+1; for(l=0;l<sides[k];l++) { circuit[k][l]=side[k][l]; circuit_side[k][l]=side_end[k][l]; if(circuit_side[k][l]==0) { seg_follow_start[circuit[k][l]]=l+1; side_follow_start[circuit[k][l]]=k; } else if(circuit_side[k][l]==1) { seg_follow_end[circuit[k][l]]=l+1; side_follow_end[circuit[k][l]]=k; } } circuit[k][sides[k]]=-1; circuit_side[k][sides[k]]=-1; } } if(1) { float mul=1; float stick=5; //write segments to screen. VEC pos[2]; for(k=0;k<3;k++) { int l; for(l=0;l<segments[k];l++) { if(circuit[k][l]==-1) { int sd=k+1; if(sd==3) sd=0; pos[1]=tri2d[sd]; if(l>0 && circuit[k][l-1]!=-1) { if(circuit_side[k][l-1]==0) { pos[0]=edge2d[circuit[k][l-1]][0]; } else { pos[0]=edge2d[circuit[k][l-1]][edge_points[circuit[k][l-1]]-1]; } } else { int sd=k; if(sd==3) sd=0; pos[0]=tri2d[sd]; } } else { if(circuit_side[k][l]==0) { int ed=circuit[k][l]; int m; for(m=0;m<edge_points[ed]-1;m++) { VEC p[2]; p[0]=edge2d[ed][m]; p[1]=edge2d[ed][m+1]; float angle; if(m==0) { sov[output_vs+0].pos=VEC(tc*300,i*400+200,0.001f)+p[0]*mul; sov[output_vs+0].rhw=1.0f; sov[output_vs+1].pos=VEC(tc*300,i*400+200,0.001f)+p[1]*mul; sov[output_vs+1].rhw=1.0f; VEC av=(sov[output_vs+0].pos+sov[output_vs+1].pos)/2; //sov[output_vs+0].pos=sov[output_vs+0].pos*0.7f+av*0.3f; angle=(float)atan2(sov[output_vs+1].pos.x-sov[output_vs+0].pos.x,sov[output_vs+1].pos.y-sov[output_vs+0].pos.y)+1.570796; output_vs+=2; } else { sov[output_vs+0].pos=VEC(tc*300,i*400+200,0.001f)+p[0]*mul; sov[output_vs+0].rhw=1.0f; sov[output_vs+1].pos=VEC(tc*300,i*400+200,0.001f)+p[1]*mul; sov[output_vs+1].rhw=1.0f; angle=(float)atan2(sov[output_vs+1].pos.x-sov[output_vs+0].pos.x,sov[output_vs+1].pos.y-sov[output_vs+0].pos.y)+1.570796; output_vs+=2; } sov[output_vs+0].pos=VEC(tc*300,i*400+200,0.001f)+(p[0]+p[1])/2*mul; sov[output_vs+0].rhw=1.0f; sov[output_vs+1].pos=sov[output_vs+0].pos+VEC(sinf(angle),cosf(angle),0)*stick; sov[output_vs+1].rhw=1.0f; output_vs+=2; } pos[1]=edge2d[circuit[k][l]][0]; if(l>0 && circuit[k][l-1]!=-1) { if(circuit_side[k][l-1]==0) { pos[0]=edge2d[circuit[k][l-1]][0]; } else { pos[0]=edge2d[circuit[k][l-1]][edge_points[circuit[k][l-1]]-1]; } } else { int sd=k; if(sd==3) sd=0; pos[0]=tri2d[sd]; } } else { pos[1]=edge2d[circuit[k][l]][edge_points[circuit[k][l]]-1]; if(l>0 && circuit[k][l-1]!=-1) { if(circuit_side[k][l-1]==0) { pos[0]=edge2d[circuit[k][l-1]][0]; } else { pos[0]=edge2d[circuit[k][l-1]][edge_points[circuit[k][l-1]]-1]; } } else { int sd=k; if(sd==3) sd=0; pos[0]=tri2d[sd]; } } } sov[output_vs+0].pos=VEC(tc*300,i*400+200,0.001f)+pos[0]*mul; sov[output_vs+0].rhw=1.0f; sov[output_vs+1].pos=VEC(tc*300,i*400+200,0.001f)+pos[1]*mul; sov[output_vs+1].rhw=1.0f; float angle=(float)atan2(sov[output_vs+1].pos.x-sov[output_vs+0].pos.x,sov[output_vs+1].pos.y-sov[output_vs+0].pos.y)+1.570796; output_vs+=2; sov[output_vs+0].pos=VEC(tc*300,i*400+200,0.001f)+(pos[0]+pos[1])/2*mul; sov[output_vs+0].rhw=1.0f; sov[output_vs+1].pos=sov[output_vs+0].pos+VEC(sinf(angle),cosf(angle),0)*(l+1)*stick; sov[output_vs+1].rhw=1.0f; output_vs+=2; } } output_text_pos[output_texts]=VEC(tc*300,i*400+200,0.001f); itoa(segments[0]+segments[1]+segments[2],output_text_string[output_texts],10); output_texts++; } tc++; //now your up to scanning sc c; c.invert=false; c.use=true; c.cs=0; c.vs[0]=1000; c.v2d[0]=new VEC[c.vs[0]]; c.v[0]=new VEC[c.vs[0]]; scv* ov=new scv[10000]; scp* op=new scp[10000]; //ready to scan - as you scan them, scan the 2d point with the 3d point, you only //ever use circuit 0 unless its inserting a hole //keep scanning till all circuits are made done=false;getoutscan: while(!done) { c.cs=1; c.vs[0]=0; bool clockwise; int scan_side=0; int scan_seg=0; for(k=0;k<3;k++) { int l; for(l=0;l<segments[k];l++) { if(segmentdone[k*3+l]==false) { scan_side=k; scan_seg=l; goto foundseg; } } } done=true; goto getoutscan;foundseg: //this scanner can be used for the "perfect knife" also, and its not so big. bool dscan=false; while(!dscan) { segmentdone[scan_side*3+scan_seg]=true; if(scan_seg==segments[scan_side]-1) { switch(scan_side) { case 0://add corner 1 c.v[0][c.vs[0]]=a_v[a_t[j].i[1]].pos; c.v2d[0][c.vs[0]]=tri2d[1]; break; case 1://add corner 2 c.v[0][c.vs[0]]=a_v[a_t[j].i[2]].pos; c.v2d[0][c.vs[0]]=tri2d[2]; break; case 2://add corner 0 c.v[0][c.vs[0]]=a_v[a_t[j].i[0]].pos; c.v2d[0][c.vs[0]]=tri2d[0]; break; } c.vs[0]++; scan_side++; if(scan_side==3) scan_side=0; scan_seg=0; if(segmentdone[scan_side*3+scan_seg]) dscan=true; } else { int ed=circuit[scan_side][scan_seg]; int dir=circuit_side[scan_side][scan_seg]; if(dir==0) { clockwise=false; //add it from start to end int l; for(l=0;l<edge_points[ed];l++) { c.v[0][c.vs[0]]=edge[ed][l]; c.v2d[0][c.vs[0]]=edge2d[ed][l]; c.vs[0]++; } scan_side=side_follow_end[ed]; scan_seg=seg_follow_end[ed]; } else { clockwise=true; //add it from end to start int l; for(l=edge_points[ed]-1;l>=0;l--) { c.v[0][c.vs[0]]=edge[ed][l]; c.v2d[0][c.vs[0]]=edge2d[ed][l]; c.vs[0]++; } scan_side=side_follow_start[ed]; scan_seg=seg_follow_start[ed]; } if(segmentdone[scan_side*3+scan_seg]) dscan=true; } } bool outside; outside=!clockwise; bool add=false; bool invert=false; switch(i) { case 0: switch(type) { case 0://union if(outside) { add=true; invert=false; } break; case 1://subtraction if(outside==false) { add=true; invert=true; } break; case 2://intersection if(outside==false) { add=true; invert=false; } break; } break; case 1: switch(type) { case 0://union if(outside) { add=true; invert=false; } break; case 1://subtraction if(outside) { add=true; invert=false; } break; case 2://intersection if(outside==false) { add=true; invert=false; } break; } break; } if(0) { //write circuit to screen VEC pos[2]; int l; for(l=0;l<c.vs[0];l++) { if(l==c.vs[0]-1) { pos[0]=c.v2d[0][l]; pos[1]=c.v2d[0][0]; } else { pos[0]=c.v2d[0][l]; pos[1]=c.v2d[0][l+1]; } sov[output_vs+0].pos=VEC(circ*300,i*400+200,0.001f)+pos[0]*3; sov[output_vs+0].rhw=1.0f; sov[output_vs+1].pos=VEC(circ*300,i*400+200,0.001f)+pos[1]*3; sov[output_vs+1].rhw=1.0f; output_vs+=2; } } // if(circ==4) add=false; if(i==1 && circ==4) { int bp=1; } circ++; if(add) { //a new circuit //check if any holes are inside it and add them //then you tesselate it UINT ovs=0; UINT ops=0; tesselate(&c, ov, op, ovs, ops); if(circ==5) { int bp=1; } //output it to the model int l; for(l=0;l<ovs;l++) { o_v[o_vs+l].pos=ov[l].pos; } int pcnt=0; for(l=0;l<ops;l++) { if((circ==5) || circ!=5) { if(invert) { o_t[o_ts+l].i[0]=op[l].i[2]+o_vs; o_t[o_ts+l].i[1]=op[l].i[1]+o_vs; o_t[o_ts+l].i[2]=op[l].i[0]+o_vs; } else { o_t[o_ts+l].i[0]=op[l].i[0]+o_vs; o_t[o_ts+l].i[1]=op[l].i[1]+o_vs; o_t[o_ts+l].i[2]=op[l].i[2]+o_vs; } pcnt++; } } o_ts+=pcnt; o_vs+=ovs; } } delete ov; delete op; delete c.v[0]; delete c.v2d[0];skipadd: i=i; } } } } output_v->Unlock(); //proximity weld //tidy off vertices //delete degenerate triangles/*its almost working now, im not sure if its just the tesselator thats screwing it up.you proximity weld it with a grid.then you could generate adjacency and weld using the adjacency, but thats a weaknessbecause then the output has to be perfect.the fact that your using adjacency on input is the biggest weakness also.i think you should code the triangulator again.*/ //copy o_v and o_t into model model.vs=o_vs; model.ts=o_ts; delete model.v; delete model.t; model.v=o_v; model.t=o_t;}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
