--- ray/src/hd/sm.c 1998/08/19 17:45:23 3.1 +++ ray/src/hd/sm.c 1998/09/11 11:52:25 3.5 @@ -8,9 +8,6 @@ static char SCCSid[] = "$SunId$ SGI"; * sm.c */ #include "standard.h" - -#include "object.h" - #include "sm_list.h" #include "sm_geom.h" #include "sm.h" @@ -20,11 +17,12 @@ SM *smMesh = NULL; double smDist_sum=0; int smNew_tri_cnt=0; +static int smBase_nbrs[4][3] = { {3,2,1},{3,0,2},{3,1,0},{1,2,0}}; + #ifdef TEST_DRIVER -VIEW View = {0,{0,0,0},{0,0,-1},{0,1,0},60,60,0}; VIEW Current_View = {0,{0,0,0},{0,0,-1},{0,1,0},60,60,0}; int Pick_cnt =0; -int Pick_tri = -1,Picking = FALSE; +int Pick_tri = -1,Picking = FALSE,Pick_samp=-1; FVECT Pick_point[500],Pick_origin,Pick_dir; FVECT Pick_v0[500], Pick_v1[500], Pick_v2[500]; FVECT P0,P1,P2; @@ -226,8 +224,6 @@ smInit(n) { int max_vertices; - sleep(10); - /* If n <=0, Just clear the existing structures */ if(n <= 0) { @@ -260,17 +256,17 @@ smLocator_apply_func(sm,v0,v1,v2,func,arg) SM *sm; FVECT v0,v1,v2; int (*func)(); -char *arg; +int *arg; { STREE *st; - char found; + int found; FVECT p0,p1,p2; st = SM_LOCATOR(sm); - point_on_sphere(p0,v0,SM_VIEW_CENTER(sm)); - point_on_sphere(p1,v1,SM_VIEW_CENTER(sm)); - point_on_sphere(p2,v2,SM_VIEW_CENTER(sm)); + VSUB(p0,v0,SM_VIEW_CENTER(sm)); + VSUB(p1,v1,SM_VIEW_CENTER(sm)); + VSUB(p2,v2,SM_VIEW_CENTER(sm)); found = stApply_to_tri_cells(st,p0,p1,p2,func,arg); @@ -279,23 +275,167 @@ char *arg; int +add_tri_expand(qtptr,q0,q1,q2,t0,t1,t2,n,arg,t_id) +QUADTREE *qtptr; +FVECT q0,q1,q2; +FVECT t0,t1,t2; +int n; +int *arg; +int t_id; +{ + OBJECT tset[QT_MAXSET+1],*optr; + int i,id,found; + FVECT v0,v1,v2; + +#ifdef DEBUG_TEST_DRIVER + Pick_tri = t_id; + Picking = TRUE; +#endif + + if(QT_IS_EMPTY(*qtptr)) + { + *qtptr = qtaddelem(*qtptr,t_id); + return(TRUE); + } + + optr = qtqueryset(*qtptr); + if(!inset(optr,t_id)) + { + if(QT_SET_CNT(optr) < QT_MAXSET) + *qtptr = qtaddelem(*qtptr,t_id); + else + { +#ifdef DEBUG + eputs("add_tri_expand():no room in set\n"); +#endif + return(FALSE); + } + } + optr = qtqueryset(*qtptr); + if(QT_SET_CNT(optr) >= QT_SET_THRESHOLD) + if (n < QT_MAX_LEVELS) + { + qtgetset(tset,*qtptr); + /* If set size exceeds threshold: subdivide cell and reinsert tris*/ + qtfreeleaf(*qtptr); + qtSubdivide(qtptr); + + for(optr = QT_SET_PTR(tset),i=QT_SET_CNT(tset); i > 0; i--) + { + id = QT_SET_NEXT_ELEM(optr); + qtTri_from_id(id,NULL,NULL,NULL,v0,v1,v2,NULL,NULL,NULL); + found=qtAdd_tri(qtptr,q0,q1,q2,v0,v1,v2,id,n); +#ifdef DEBUG + if(!found) + eputs("add_tri_expand():Reinsert\n"); +#endif + } + return(QT_MODIFIED); + } + else + if(QT_SET_CNT(optr) < QT_MAXSET) + { +#ifdef DEBUG_TEST_DRIVER + eputs("add_tri_expand():too many levels:can't expand\n"); +#endif + return(TRUE); + } + else + { +#ifdef DEBUG + eputs("add_tri_expand():too many tris inset:can't add\n"); +#endif + return(FALSE); + } +} + + +int +add_tri(qtptr,fptr,t_id) + QUADTREE *qtptr; + int *fptr; + int t_id; +{ + + OBJECT *optr; + +#ifdef DEBUG_TEST_DRIVER + Pick_tri = t_id; + Picking = TRUE; +#endif + if(QT_IS_EMPTY(*qtptr)) + { + *qtptr = qtaddelem(*qtptr,t_id); + if(!QT_FLAG_FILL_TRI(*fptr)) + (*fptr)++; + } + else + { + optr = qtqueryset(*qtptr); + if(!inset(optr,t_id)) + { + if(QT_SET_CNT(optr) < QT_MAXSET) + { + if(QT_SET_CNT(optr) >= QT_SET_THRESHOLD) + (*fptr) |= QT_EXPAND; + if(!QT_FLAG_FILL_TRI(*fptr)) + (*fptr)++; + *qtptr = qtaddelem(*qtptr,t_id); + } + else + { +#ifdef DEBUG_TESTDRIVER + eputs("add_tri():exceeded set size\n"); +#endif + return(FALSE); + } + } + } + return(TRUE); +} + + +int +stInsert_tri(st,t_id,t0,t1,t2) + STREE *st; + int t_id; + FVECT t0,t1,t2; +{ + int f; + FVECT dir; + + /* First add all of the leaf cells lying on the triangle perimeter: + mark all cells seen on the way + */ + ST_CLEAR_FLAGS(st); + f = 0; + VSUB(dir,t1,t0); + stTrace_edge(st,t0,dir,1.0,add_tri,&f,t_id); + VSUB(dir,t2,t1); + stTrace_edge(st,t1,dir,1.0,add_tri,&f,t_id); + VSUB(dir,t0,t2); + stTrace_edge(st,t2,dir,1.0,add_tri,&f,t_id); + /* Now visit interior */ + if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f)) + stVisit_tri_interior(st,t0,t1,t2,add_tri_expand,&f,t_id); +} + smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id) SM *sm; int t_id; int v0_id,v1_id,v2_id; { STREE *st; - FVECT p0,p1,p2; + FVECT v0,v1,v2; st = SM_LOCATOR(sm); - smDir(sm,p0,v0_id); - smDir(sm,p1,v1_id); - smDir(sm,p2,v2_id); + VSUB(v0,SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm)); + VSUB(v1,SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm)); + VSUB(v2,SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm)); - stAdd_tri(st,t_id,p0,p1,p2); + stUpdate_tri(st,t_id,v0,v1,v2,add_tri,add_tri_expand); - return(1); } /* Add a triangle to the base array with vertices v1-v2-v3 */ @@ -343,8 +483,6 @@ TRI **tptr; SM_NTH_VERT(sm,v1_id) = t_id; SM_NTH_VERT(sm,v2_id) = t_id; - /* Add triangle to the locator */ - smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id); if(t) *tptr = t; /* return initialized triangle */ @@ -385,7 +523,7 @@ double eps; } } else - if(d1 < d2) + if(d1 < d0) { if((eps < 0) || d1 < eps) { @@ -393,19 +531,13 @@ double eps; d = d1; } } - else - if((eps < 0) || d2 < eps) - { - closest = v2_id; - d = d2; - } - } + } if(v2_id != -1) { smDir(sm,v,v2_id); d2 = DIST(p,v); if((eps < 0) || d2 < eps) - if(closest== -1 ||(d2 < d)) + if(closest == -1 ||(d2 < d)) return(v2_id); } return(closest); @@ -428,7 +560,7 @@ FVECT p; VCOPY(v,SM_NTH_WV(sm,v1_id)); d1 = DIST(p,v); - if(d1 < d2) + if(d1 < d0) { closest = v1_id; d = d1; @@ -442,11 +574,12 @@ FVECT p; } void -smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id) +smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add,del) SM *sm; int t_id,t1_id; int e,e1; - int **tn_id,**tn1_id; + int *tn_id,*tn1_id; + LIST **add,**del; { TRI *t,*t1; @@ -469,12 +602,13 @@ smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id) verts[enext] = T_NTH_V(t1,e1prev); verts[eprev] = T_NTH_V(t,eprev); ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&ta); - + *add = push_data(*add,ta_id); verts[e1] = T_NTH_V(t1,e1); verts[e1next] = T_NTH_V(t,eprev); verts[e1prev] = T_NTH_V(t1,e1prev); tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&tb); - + *add = push_data(*add,tb_id); + /* set the neighbors */ T_NTH_NBR(ta,e) = T_NTH_NBR(t1,e1next); T_NTH_NBR(tb,e1) = T_NTH_NBR(t,enext); @@ -495,31 +629,71 @@ smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id) T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = tb_id; /* Delete two parent triangles */ - smDelete_tri(sm,t_id); - smDelete_tri(sm,t1_id); + + *del = push_data(*del,t_id); + if(SM_IS_NTH_T_NEW(sm,t_id)) + SM_CLEAR_NTH_T_NEW(sm,t_id); + else + SM_CLEAR_NTH_T_BASE(sm,t_id); + *del = push_data(*del,t1_id); + if(SM_IS_NTH_T_NEW(sm,t1_id)) + SM_CLEAR_NTH_T_NEW(sm,t1_id); + else + SM_CLEAR_NTH_T_BASE(sm,t1_id); *tn_id = ta_id; *tn1_id = tb_id; } +smUpdate_locator(sm,add_list,del_list) +SM *sm; +LIST *add_list,*del_list; +{ + int t_id; + TRI *t; + while(add_list) + { + t_id = pop_list(&add_list); + if(!SM_IS_NTH_T_NEW(sm,t_id) && !SM_IS_NTH_T_BASE(sm,t_id)) + { + SM_SET_NTH_T_NEW(sm,t_id); + smNew_tri_cnt--; + continue; + } + t = SM_NTH_TRI(sm,t_id); + smLocator_add_tri(sm,t_id,T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2)); + } + + while(del_list) + { + t_id = pop_list(&del_list); + if(SM_IS_NTH_T_NEW(sm,t_id)) + { + smDelete_tri(sm,t_id); + continue; + } + smLocator_remove_tri(sm,t_id); + smDelete_tri(sm,t_id); + } +} /* MUST add check for constrained edges */ -char +int smFix_tris(sm,id,tlist) SM *sm; int id; LIST *tlist; { TRI *t,*t_opp; - FVECT p,p1,np,p2,p3; - int swapped = 0; - int e,e1,e_id; - char debug = 0; + FVECT p,p1,p2,p3; + int e,e1,swapped = 0; int t_id,t_opp_id; - - VCOPY(p,SM_NTH_WV(sm,id)); - VSUB(p,p,SM_VIEW_CENTER(sm)); + LIST *add_list,*del_list; + + + add_list = del_list = NULL; + VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); while(tlist) { - t_id = (int)pop_list(&tlist); + t_id = pop_list(&tlist); t = SM_NTH_TRI(sm,t_id); e = (T_WHICH_V(t,id)+1)%3; t_opp_id = T_NTH_NBR(t,e); @@ -534,12 +708,13 @@ LIST *tlist; e1 = T_NTH_NBR_PTR(t_id,t_opp); /* check list for t_opp and Remove if there */ remove_from_list(t_opp_id,&tlist); - - smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id); + smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id, + &add_list,&del_list); tlist = push_data(tlist,t_id); tlist = push_data(tlist,t_opp_id); } } + smUpdate_locator(sm,add_list,del_list); return(swapped); } @@ -572,8 +747,8 @@ int id,nid; T_NTH_V(tri,T_WHICH_V(tri,id)) = nid; - t_id = smTri_next_ccw_nbr(sm,t,nid); - while((t= SM_NTH_TRI(sm,t_id)) != tri) + t_id = smTri_next_ccw_nbr(sm,tri,nid); + while((t = SM_NTH_TRI(sm,t_id)) != tri) { T_NTH_V(t,T_WHICH_V(t,id)) = nid; t_id = smTri_next_ccw_nbr(sm,t,nid); @@ -599,7 +774,7 @@ smReplace_vertex(sm,c,dir,p,tri_id,snew_id,type,which) COLR c; FVECT dir,p; int tri_id,snew_id; - char type,which; + int type,which; { int n_id,s_id; TRI *tri; @@ -670,9 +845,14 @@ smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id) n_id = smClosest_vertex_in_tri(sm,t0_id,t1_id,t2_id,npt,P_REPLACE_EPS); } t0_id = smAdd_tri(sm,s_id,v0_id,v1_id,&t0); + /* Add triangle to the locator */ + smLocator_add_tri(sm,t0_id,s_id,v0_id,v1_id); + t1_id = smAdd_tri(sm,s_id,v1_id,v2_id,&t1); + smLocator_add_tri(sm,t1_id,s_id,v1_id,v2_id); t2_id = smAdd_tri(sm,s_id,v2_id,v0_id,&t2); - + smLocator_add_tri(sm,t2_id,s_id,v2_id,v0_id); + /* Set the neighbor pointers for the new tris */ T_NTH_NBR(t0,0) = t2_id; T_NTH_NBR(t0,1) = T_NTH_NBR(tri,0); @@ -692,6 +872,7 @@ smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id) nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,2)); T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t2_id; + smLocator_remove_tri(sm,tri_id); smDelete_tri(sm,tri_id); /* Fix up the new triangles*/ @@ -709,11 +890,10 @@ smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id) int -smPointLocate(sm,pt,type,which,norm) +smPointLocate(sm,pt,norm) SM *sm; FVECT pt; -char *type,*which; -char norm; +int norm; { STREE *st; int tri; @@ -722,36 +902,39 @@ char norm; st = SM_LOCATOR(sm); if(norm) { - point_on_sphere(npt,pt,SM_VIEW_CENTER(sm)); - tri = stPoint_locate(st,npt,type,which); + VSUB(npt,pt,SM_VIEW_CENTER(sm)); + tri = stPoint_locate(st,npt); } else - tri = stPoint_locate(st,pt,type,which); + tri = stPoint_locate(st,pt); return(tri); } QUADTREE -smPointLocateCell(sm,pt,v0,v1,v2,type,which,norm) +smPointLocateCell(sm,pt,norm,v0,v1,v2) SM *sm; -FVECT pt,v0,v1,v2; -char *type,*which; -char norm; +FVECT pt; +int norm; +FVECT v0,v1,v2; { STREE *st; - QUADTREE qt; + QUADTREE *qtptr; FVECT npt; st = SM_LOCATOR(sm); if(norm) { - point_on_sphere(npt,pt,SM_VIEW_CENTER(sm)); + VSUB(npt,pt,SM_VIEW_CENTER(sm)); - qt = stPoint_locate_cell(st,npt,v0,v1,v2,type,which); + qtptr = stPoint_locate_cell(st,npt,v0,v1,v2); } else - qt = stPoint_locate_cell(st,pt,v0,v1,v2,type,which); + qtptr = stPoint_locate_cell(st,pt,v0,v1,v2); - return(qt); + if(qtptr) + return(*qtptr); + else + return(EMPTY); } int @@ -762,7 +945,6 @@ smAdd_sample_to_mesh(sm,c,dir,pt,s_id) int s_id; { int t_id; - char type,which; double d; FVECT p; @@ -773,15 +955,16 @@ smAdd_sample_to_mesh(sm,c,dir,pt,s_id) d = DIST(pt,SM_VIEW_CENTER(smMesh)); smDist_sum += 1.0/d; /************************************/ - t_id = smPointLocate(smMesh,pt,&type,&which,TRUE); - if(type==GT_FACE) + t_id = smPointLocate(smMesh,pt,TRUE); + if(t_id >= 0) s_id = smInsert_point_in_tri(smMesh,c,dir,pt,s_id,t_id); - else - if(type==GT_VERTEX) - s_id = smReplace_vertex(smMesh,c,dir,pt,t_id,s_id,type,which); #ifdef DEBUG else - eputs("smAdd_sample_to_mesh(): unrecognized type\n"); + { + c[0] = 255;c[1]=0;c[2]=0; + s_id = smAdd_sample_point(sm,c,dir,pt); + eputs("smAdd_sample_to_mesh(): not found fg\n"); + } #endif } else if(s_id != -1) @@ -794,29 +977,24 @@ smAdd_sample_to_mesh(sm,c,dir,pt,s_id) smDist_sum += 1.0/d; /************************************/ } - t_id = smPointLocate(smMesh,p,&type,&which,TRUE); - if(type==GT_FACE) + t_id = smPointLocate(smMesh,p,TRUE); + if(t_id != -1) s_id = smInsert_point_in_tri(smMesh,c,dir,p,s_id,t_id); - else - if(type==GT_VERTEX) - s_id = smReplace_vertex(smMesh,c,dir,p,t_id,s_id,type,which); #ifdef DEBUG else - eputs("smAdd_sample_to_mesh(): unrecognized type\n"); + eputs("smAdd_sample_to_mesh():not found reinsert\n"); #endif } /* Is a BG(sky point) */ else { - t_id = smPointLocate(smMesh,dir,&type,&which,FALSE); - if(type==GT_FACE) + t_id = smPointLocate(smMesh,dir,FALSE); + if(t_id != -1) s_id = smInsert_point_in_tri(smMesh,c,dir,NULL,s_id,t_id); - else - if(type==GT_VERTEX) - s_id = smReplace_vertex(smMesh,c,dir,NULL,t_id,s_id,type,which); + #ifdef DEBUG else - eputs("smAdd_sample_to_mesh(): unrecognized type\n"); + eputs("smAdd_sample_to_mesh(): not found bg\n"); #endif } return(s_id); @@ -841,22 +1019,13 @@ FVECT p; { int s_id; + int debug=0; /* First check if this the first sample: if so initialize mesh */ if(SM_NUM_SAMP(smMesh) == 0) -#ifdef TEST_DRIVER - smInit_mesh(smMesh,View.vp); -#else smInit_mesh(smMesh,odev.v.vp); -#endif - s_id = smAdd_sample_to_mesh(smMesh,c,dir,p,-1); -#if 0 -{ - char buff[100]; - sprintf(buff,"Added sample %d\n",s_id); - eputs(buff); -} -#endif + if(!debug) + s_id = smAdd_sample_to_mesh(smMesh,c,dir,p,-1); return(s_id); } @@ -930,7 +1099,7 @@ smCreate_base_mesh(sm,type) SM *sm; int type; { - int i,id; + int i,id,tri_id,nbr_id; int p[4],ids[4]; int v0_id,v1_id,v2_id; TRI *tris[4]; @@ -940,7 +1109,11 @@ int type; for(i=0; i < 4; i++) { - VADD(cntr,stDefault_base[i],SM_VIEW_CENTER(sm)); + VCOPY(cntr,stDefault_base[i]); + cntr[0] += .01; + cntr[1] += .02; + cntr[2] += .03; + VADD(cntr,cntr,SM_VIEW_CENTER(sm)); point_on_sphere(d,cntr,SM_VIEW_CENTER(sm)); id = smAdd_base_vertex(sm,cntr,d); /* test to make sure vertex allocated */ @@ -957,24 +1130,14 @@ int type; v2_id = p[stTri_verts[i][2]]; if((ids[i] = smAdd_tri(sm, v0_id,v1_id,v2_id,&(tris[i])))== -1) return(0); + smLocator_add_tri(sm,ids[i],v0_id,v1_id,v2_id); } /* Set neighbors */ - T_NTH_NBR(tris[0],0) = ids[3]; - T_NTH_NBR(tris[0],1) = ids[2]; - T_NTH_NBR(tris[0],2) = ids[1]; + for(tri_id=0;tri_id < 4; tri_id++) + for(nbr_id=0; nbr_id < 3; nbr_id++) + T_NTH_NBR(tris[tri_id],nbr_id) = smBase_nbrs[tri_id][nbr_id]; - T_NTH_NBR(tris[1],0) = ids[3]; - T_NTH_NBR(tris[1],1) = ids[0]; - T_NTH_NBR(tris[1],2) = ids[2]; - - T_NTH_NBR(tris[2],0) = ids[3]; - T_NTH_NBR(tris[2],1) = ids[1]; - T_NTH_NBR(tris[2],2) = ids[0]; - - T_NTH_NBR(tris[3],0) = ids[1]; - T_NTH_NBR(tris[3],1) = ids[2]; - T_NTH_NBR(tris[3],2) = ids[0]; return(1); } @@ -984,14 +1147,14 @@ int smNext_tri_flag_set(sm,i,which,b) SM *sm; int i,which; - char b; + int b; { for(; i < SM_TRI_CNT(sm);i++) { - if(!SM_IS_NTH_T_FLAG(sm,i,which)) - continue; + if(!SM_IS_NTH_T_FLAG(sm,i,which)) + continue; if(!b) break; if((b==1) && !SM_BG_TRI(sm,i)) @@ -1018,9 +1181,11 @@ smNext_valid_tri(sm,i) -qtTri_verts_from_id(t_id,v0,v1,v2) +qtTri_from_id(t_id,v0,v1,v2,n0,n1,n2,v0_idp,v1_idp,v2_idp) int t_id; FVECT v0,v1,v2; +FVECT n0,n1,n2; +int *v0_idp,*v1_idp,*v2_idp; { TRI *t; int v0_id,v1_id,v2_id; @@ -1030,121 +1195,25 @@ FVECT v0,v1,v2; v1_id = T_NTH_V(t,1); v2_id = T_NTH_V(t,2); - smDir(smMesh,v0,v0_id); - smDir(smMesh,v1,v1_id); - smDir(smMesh,v2,v2_id); - - } - - -int -smIntersectTriSet(sm,t_set,orig,dir,pt) - SM *sm; - OBJECT *t_set; - FVECT orig,dir,pt; -{ - OBJECT *optr; - int i,t_id,v_id; - TRI *tri; - FVECT p0,p1,p2; - char type,which; - int p0_id,p1_id,p2_id; - - for(optr = QT_SET_PTR(t_set),i = QT_SET_CNT(t_set); i > 0; i--) - { - t_id = QT_SET_NEXT_ELEM(optr); - tri = SM_NTH_TRI(sm,t_id); - p0_id = T_NTH_V(tri,0); - p1_id = T_NTH_V(tri,1); - p2_id = T_NTH_V(tri,2); - VCOPY(p0,SM_NTH_WV(sm,p0_id)); - VCOPY(p1,SM_NTH_WV(sm,p1_id)); - VCOPY(p2,SM_NTH_WV(sm,p2_id)); - if(type = ray_intersect_tri(orig,dir,p0,p1,p2,pt,&which)) - { - if(type==GT_VERTEX) - return(T_NTH_V(tri,which)); - v_id = smClosest_vertex_in_w_tri(sm,p0_id,p1_id,p2_id,pt); - return(v_id); - } - } - return(-1); -} - -/* - * int - * smTraceRay(SM *sm,FVECT orig, FVECT dir,FVECT v0,FVECT v1,FVECT v2,FVECT r) - * - * Intersect the ray with triangle v0v1v2, return intersection point in r - * - * Assumes orig,v0,v1,v2 are in spherical coordinates, and orig is - * unit - */ -char -smTraceRay(sm,orig,dir,v0,v1,v2,r) - SM *sm; - FVECT orig,dir; - FVECT v0,v1,v2; - FVECT r; -{ - FVECT n,p[3],d; - double pt[3],r_eps; - char i; - int which; - - /* Find the plane equation for the triangle defined by the edge v0v1 and - the view center*/ - VCROSS(n,v0,v1); - /* Intersect the ray with this plane */ - i = intersect_ray_plane(orig,dir,n,0.0,&(pt[0]),p[0]); - if(i) - which = 0; - else - which = -1; - - VCROSS(n,v1,v2); - i = intersect_ray_plane(orig,dir,n,0.0,&(pt[1]),p[1]); - if(i) - if((which==-1) || pt[1] < pt[0]) - which = 1; - - VCROSS(n,v2,v0); - i = intersect_ray_plane(orig,dir,n,0.0,&(pt[2]),p[2]); - if(i) - if((which==-1) || pt[2] < pt[which]) - which = 2; - - if(which != -1) + if(v0) { - /* Return point that is K*eps along projection of the ray on - the sphere to push intersection point p[which] into next cell - */ - normalize(p[which]); - /* Calculate the ray perpendicular to the intersection point: approx - the direction moved along the sphere a distance of K*epsilon*/ - r_eps = -DOT(p[which],dir); - VSUM(n,dir,p[which],r_eps); - /* Calculate the length along ray p[which]-dir needed to move to - cause a move along the sphere of k*epsilon - */ - r_eps = DOT(n,dir); - VSUM(r,p[which],dir,(20*FTINY)/r_eps); - normalize(r); - return(TRUE); + VCOPY(v0,SM_NTH_WV(smMesh,v0_id)); + VCOPY(v1,SM_NTH_WV(smMesh,v1_id)); + VCOPY(v2,SM_NTH_WV(smMesh,v2_id)); } - else + if(n0) { - /* Unable to find intersection: move along ray and try again */ - r_eps = -DOT(orig,dir); - VSUM(n,dir,orig,r_eps); - r_eps = DOT(n,dir); - VSUM(r,orig,dir,(20*FTINY)/r_eps); - normalize(r); -#ifdef DEBUG - eputs("smTraceRay:Ray does not intersect triangle"); -#endif - return(FALSE); + smDir(smMesh,n0,v0_id); + smDir(smMesh,n1,v1_id); + smDir(smMesh,n2,v2_id); + } + if(v0_idp) + { + *v0_idp = v0_id; + *v1_idp = v1_id; + *v2_idp = v2_id; + } } @@ -1160,7 +1229,7 @@ smFindSamp(orig,dir) FVECT orig,dir; { FVECT r,v0,v1,v2,a,b,p; - OBJECT os[MAXCSET+1],t_set[MAXSET+1]; + OBJECT os[QT_MAXCSET+1],t_set[QT_MAXSET+1],*ts; QUADTREE qt; int s_id; double d; @@ -1184,13 +1253,13 @@ FVECT orig,dir; d = -DOT(b,dir); if(EQUAL_VEC3(orig,SM_VIEW_CENTER(smMesh)) || EQUAL(fabs(d),1.0)) { - qt = smPointLocateCell(smMesh,dir,v0,v1,v2,NULL,NULL,FALSE); + qt = smPointLocateCell(smMesh,dir,FALSE,NULL,NULL,NULL); /* Test triangles in the set for intersection with Ray:returns first found */ - qtgetset(t_set,qt); - s_id = smIntersectTriSet(smMesh,t_set,orig,dir,p); -#ifdef TEST_DRIVER + ts = qtqueryset(qt); + s_id = intersect_tri_set(ts,orig,dir,p); +#ifdef DEBUG_TEST_DRIVER VCOPY(Pick_point[0],p); #endif return(s_id); @@ -1199,9 +1268,9 @@ FVECT orig,dir; { /* Starting with orig, Walk along projection of ray onto sphere */ point_on_sphere(r,orig,SM_VIEW_CENTER(smMesh)); - qt = smPointLocateCell(smMesh,r,v0,v1,v2,NULL,NULL,FALSE); - qtgetset(t_set,qt); + qt = smPointLocateCell(smMesh,r,FALSE,v0,v1,v2); /* os will contain all triangles seen thus far */ + qtgetset(t_set,qt); setcopy(os,t_set); /* Calculate ray perpendicular to dir: when projection ray is // to dir, @@ -1211,33 +1280,33 @@ FVECT orig,dir; d = DOT(a,b); while(d > 0) { - s_id = smIntersectTriSet(smMesh,t_set,orig,dir,p); -#ifdef TEST_DRIVER + s_id = intersect_tri_set(t_set,orig,dir,p); +#ifdef DEBUG_TEST_DRIVER VCOPY(Pick_point[0],p); #endif if(s_id != EMPTY) return(s_id); /* Find next cell that projection of ray intersects */ - smTraceRay(smMesh,r,dir,v0,v1,v2,r); - qt = smPointLocateCell(smMesh,r,v0,v1,v2,NULL,NULL,FALSE); + traceRay(r,dir,v0,v1,v2,r); + qt = smPointLocateCell(smMesh,r,FALSE,v0,v1,v2); qtgetset(t_set,qt); /* Check triangles in set against those seen so far(os):only check new triangles for intersection (t_set') */ check_set(t_set,os); - d = DOT(a,r); + d = DOT(a,r); } } -#ifdef DEBUG +#ifdef DEBUG eputs("smFindSamp():Pick Ray did not intersect mesh"); #endif return(EMPTY); } -smRebuild_mesh(sm,vptr) +smRebuild_mesh(sm,vp) SM *sm; - VIEW *vptr; + FVECT vp; { int i; FVECT dir; @@ -1245,12 +1314,9 @@ smRebuild_mesh(sm,vptr) FVECT p,ov; /* Clear the mesh- and rebuild using the current sample array */ -#ifdef TEST_DRIVER - View = *vptr; -#endif - VSUB(ov,vptr->vp,SM_VIEW_CENTER(sm)); - smInit_mesh(sm,vptr->vp); + VSUB(ov,vp,SM_VIEW_CENTER(sm)); + smInit_mesh(sm,vp); SM_FOR_ALL_SAMPLES(sm,i) { @@ -1259,5 +1325,139 @@ smRebuild_mesh(sm,vptr) smAdd_sample_to_mesh(sm,NULL,NULL,NULL,i); } } + +int +intersect_tri_set(t_set,orig,dir,pt) + OBJECT *t_set; + FVECT orig,dir,pt; +{ + OBJECT *optr; + int i,t_id,id; + int pid0,pid1,pid2; + FVECT p0,p1,p2,p; + TRI *t; + + optr = QT_SET_PTR(t_set); + for(i = QT_SET_CNT(t_set); i > 0; i--) + { + t_id = QT_SET_NEXT_ELEM(optr); + + t = SM_NTH_TRI(smMesh,t_id); + pid0 = T_NTH_V(t,0); + pid1 = T_NTH_V(t,1); + pid2 = T_NTH_V(t,2); + VCOPY(p0,SM_NTH_WV(smMesh,pid0)); + VCOPY(p1,SM_NTH_WV(smMesh,pid1)); + VCOPY(p2,SM_NTH_WV(smMesh,pid2)); + if(ray_intersect_tri(orig,dir,p0,p1,p2,p)) + { + id = closest_point_in_tri(p0,p1,p2,p,pid0,pid1,pid2); + + if(pt) + VCOPY(pt,p); +#ifdef DEBUG_TEST_DRIVER + Pick_tri = t_id; + Pick_samp = id; + VCOPY(Pick_point[0],p); +#endif + return(id); + } + } + return(-1); +} + +int +ray_trace_check_set(qtptr,orig,dir,tptr,os) + QUADTREE *qtptr; + FVECT orig,dir; + int *tptr; + OBJECT *os; +{ + OBJECT tset[QT_MAXSET+1]; + double dt,t; + int found; + FVECT o; + + + if(!QT_IS_EMPTY(*qtptr)) + { + VADD(o,orig,SM_VIEW_CENTER(smMesh)); + qtgetset(tset,*qtptr); + /* Check triangles in set against those seen so far(os):only + check new triangles for intersection (t_set') + */ + check_set(tset,os); + if((found = intersect_tri_set(tset,o,dir,NULL))!= -1) + { + *tptr = found; + return(QT_DONE); + } + } + return(FALSE); +} + +int +smFindSamp_opt(orig,dir) +FVECT orig,dir; +{ + FVECT b,p,o; + OBJECT *ts; + QUADTREE qt; + int s_id; + double d; + + /* r is the normalized vector from the view center to the current + * ray point ( starting with "orig"). Find the cell that r falls in, + * and test the ray against all triangles stored in the cell. If + * the test fails, trace the projection of the ray across to the + * next cell it intersects: iterate until either an intersection + * is found, or the projection ray is // to the direction. The sample + * corresponding to the triangle vertex closest to the intersection + * point is returned. + */ + + /* First test if "orig" coincides with the View_center or if "dir" is + parallel to r formed by projecting "orig" on the sphere. In + either case, do a single test against the cell containing the + intersection of "dir" and the sphere + */ + /* orig will be updated-so preserve original value */ + if(!smMesh) + return; + point_on_sphere(b,orig,SM_VIEW_CENTER(smMesh)); + d = -DOT(b,dir); + if(EQUAL_VEC3(orig,SM_VIEW_CENTER(smMesh)) || EQUAL(fabs(d),1.0)) + { + qt = smPointLocateCell(smMesh,dir,FALSE,NULL,NULL,NULL); + /* Test triangles in the set for intersection with Ray:returns + first found + */ + ts = qtqueryset(qt); + s_id = intersect_tri_set(ts,orig,dir,p); +#ifdef DEBUG_TEST_DRIVER + VCOPY(Pick_point[0],p); +#endif + } + else + { + OBJECT t_set[QT_MAXCSET+1]; + /* Test each of the root triangles against point id */ + QT_CLEAR_SET(t_set); + VSUB(o,orig,SM_VIEW_CENTER(smMesh)); + ST_CLEAR_FLAGS(SM_LOCATOR(smMesh)); + s_id=stTrace_ray(SM_LOCATOR(smMesh),o,dir,ray_trace_check_set,&s_id,t_set); + } + return(s_id); +} + + + + + + + + + +