Sign in to follow this  
gian92vbNET

boolean subtraction of two meshes in direct3D

Recommended Posts

gian92vbNET    100
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.

Share this post


Link to post
Share on other sites
Promit    13246
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.)

Share this post


Link to post
Share on other sites
rouncED    103
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].i[0]=i;
ll[i].i[1]=i+1;
}
else
{
ll[i].i[0]=i;
ll[i].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[i];j++)
{
lv[lvcount+j].pos=c->v2d[i][j];
v[lvcount+j].pos=c->v[i][j];
}
for(j=0;j<c->vs[i];j++)
{
ll[llcount+j].i[0]=lvcount+j;
if(j==c->vs[i]-1) ll[llcount+j].i[1]=lvcount;
else ll[llcount+j].i[1]=lvcount+j+1;
}
lvcount+=c->vs[i];
llcount+=c->vs[i];
}
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].i[0]==o[0]
|| p[i].i[1]==o[0]
|| p[i].i[2]==o[0])
&&(p[i].i[0]==o[1]
|| p[i].i[1]==o[1]
|| p[i].i[2]==o[1])
&&(p[i].i[0]==check
|| p[i].i[1]==check
|| p[i].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].i[0]==o[0] && ll[i].i[1]==check) || (ll[i].i[1]==o[0] && ll[i].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].i[0]].pos,lv[ll[i].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].i[0]==o[1] && ll[i].i[1]==check) || (ll[i].i[1]==o[1] && ll[i].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].i[0]].pos,lv[ll[i].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].i[0]==o[0] && ll[i].i[1]==check) || (ll[i].i[1]==o[0] && ll[i].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].i[0]].pos,lv[ll[i].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].i[0]==o[1] && ll[i].i[1]==check) || (ll[i].i[1]==o[1] && ll[i].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].i[0]].pos,lv[ll[i].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].i[0]].pos!=lv[o[0]].pos
&& lv[p[i].i[0]].pos!=lv[o[1]].pos
&& lv[p[i].i[0]].pos!=lv[check].pos
&& lv[p[i].i[1]].pos!=lv[o[0]].pos
&& lv[p[i].i[1]].pos!=lv[o[1]].pos
&& lv[p[i].i[1]].pos!=lv[check].pos
&& lv[p[i].i[2]].pos!=lv[o[0]].pos
&& lv[p[i].i[2]].pos!=lv[o[1]].pos
&& lv[p[i].i[2]].pos!=lv[check].pos)
{
int j;
for(j=0;j<3;j++)
{
VEC pos=lv[p[i].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].i[0]].pos!=lv[o[0]].pos
&& lv[ll[i].i[0]].pos!=lv[o[1]].pos
&& lv[ll[i].i[0]].pos!=lv[check].pos)
{
int ints=0;
int j;
for(j=0;j<3;j++)
{
VEC pos=lv[ll[i].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].i[0]==o[0]
//|| p[i].i[1]==o[0]
//|| p[i].i[2]==o[0]
//|| p[i].i[0]==check
//|| p[i].i[1]==check
//|| p[i].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].i[0]].pos;pos1=lv[p[i].i[1]].pos;break;
case 1:pos0=lv[p[i].i[1]].pos;pos1=lv[p[i].i[2]].pos;break;
case 2:pos0=lv[p[i].i[2]].pos;pos1=lv[p[i].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].i[0]==o[1]
//|| p[i].i[1]==o[1]
//|| p[i].i[2]==o[1]
//|| p[i].i[0]==check
//|| p[i].i[1]==check
//|| p[i].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].i[0]].pos;pos1=lv[p[i].i[1]].pos;break;
case 1:pos0=lv[p[i].i[1]].pos;pos1=lv[p[i].i[2]].pos;break;
case 2:pos0=lv[p[i].i[2]].pos;pos1=lv[p[i].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[i]].pos.x,lv[o[0]].pos.y-lv[pok[i]].pos.y);
if(dist<mindist)
{
mindist=dist;
check=pok[i];
}
}
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].i[0]==o[0] && ll[i].i[1]==check) || (ll[i].i[1]==o[0] && ll[i].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].i[0] && check==p[i].i[1]) || (o[0]==p[i].i[1] && check==p[i].i[0]))
&& ((o[0]==p[i].i[1] && check==p[i].i[2]) || (o[0]==p[i].i[2] && check==p[i].i[1]))
&& ((o[0]==p[i].i[2] && check==p[i].i[0]) || (o[0]==p[i].i[0] && check==p[i].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].i[0]==o[1] && ll[i].i[1]==check) || (ll[i].i[1]==o[1] && ll[i].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].i[0] && check==p[i].i[1]) || (o[1]==p[i].i[1] && check==p[i].i[0]))
&& ((o[1]==p[i].i[1] && check==p[i].i[2]) || (o[1]==p[i].i[2] && check==p[i].i[1]))
&& ((o[1]==p[i].i[2] && check==p[i].i[0]) || (o[1]==p[i].i[0] && check==p[i].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].i[0]]=true;
check[p[i].i[1]]=true;
check[p[i].i[2]]=true;
}
for(i=0;i<vs;i++)
{
if(check[i]==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[i].pos;
}
for(i=0;i<ps;i++)
{
op[ops+i].is=p[i].is;
op[ops+i].i[0]=p[i].i[0]+ovs;
op[ops+i].i[1]=p[i].i[1]+ovs;
op[ops+i].i[2]=p[i].i[2]+ovs;
op[ops+i].i[3]=p[i].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[b].vs;
a_v=model[b].v;
a_ts=model[b].ts;
a_t=model[b].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[b].vs;
b_v=model[b].v;
b_ts=model[b].ts;
b_t=model[b].t;
break;
case 1:
a_vs=model[b].vs;
a_v=model[b].v;
a_ts=model[b].ts;
a_t=model[b].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 weakness
because 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[b]

model[b].vs=o_vs;
model[b].ts=o_ts;

delete model[b].v;
delete model[b].t;

model[b].v=o_v;
model[b].t=o_t;
}



Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this