--- ray/src/hd/sm.c 1998/12/28 19:30:27 3.10 +++ ray/src/hd/sm.c 1999/03/05 16:33:17 3.14 @@ -18,9 +18,12 @@ static char SCCSid[] = "$SunId$ SGI"; SM *smMesh = NULL; double smDist_sum=0; +#define S_INC 1000 int smNew_tri_cnt=0; -double smMinSampDiff = 4.25e-4; /* min edge length in radians */ +int smNew_tri_size=0; +#define SM_MIN_SAMP_DIFF 1e-4/* min edge length in radians */ + /* Each edge extends .5536 radians - 31.72 degrees */ static FVECT icosa_verts[162] = {{-0.018096,0.495400,0.868477},{0.018614,-0.554780,0.831789}, @@ -239,16 +242,6 @@ smDir(sm,ps,id) normalize(ps); } -smDir_in_cone(sm,ps,id) - SM *sm; - FVECT ps; - int id; -{ - - VSUB(ps,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); - normalize(ps); -} - smClear_flags(sm,which) SM *sm; int which; @@ -445,7 +438,7 @@ smAlloc(max_samples) total_points = n + SM_EXTRA_POINTS; - max_tris = total_points*4; + max_tris = total_points*2; /* Now allocate space for mesh vertices and triangles */ max_tris = smAlloc_mesh(smMesh, total_points, max_tris); @@ -488,7 +481,6 @@ smInit(n) { int max_vertices; - /* If n <=0, Just clear the existing structures */ if(n <= 0) { @@ -517,10 +509,11 @@ smInit(n) } -smLocator_apply(sm,v0,v1,v2,func) +smLocator_apply(sm,v0,v1,v2,func,n) SM *sm; FVECT v0,v1,v2; FUNC func; + int n; { STREE *st; FVECT tri[3]; @@ -530,12 +523,10 @@ smLocator_apply(sm,v0,v1,v2,func) VSUB(tri[0],v0,SM_VIEW_CENTER(sm)); VSUB(tri[1],v1,SM_VIEW_CENTER(sm)); VSUB(tri[2],v2,SM_VIEW_CENTER(sm)); - stVisit(st,tri,func); + stVisit(st,tri,func,n); } - -/* NEW INSERTION!!! ******************************************************/ QUADTREE insert_tri(argptr,root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale, s0,s1,s2,sq0,sq1,sq2,rev,f,n) @@ -568,7 +559,7 @@ insert_tri(argptr,root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21, /* If the set size is below expansion threshold,or at maximum number of quadtree levels : just add */ optr = qtqueryset(qt); - if(QT_SET_CNT(optr) < QT_SET_THRESHOLD || (n >= QT_MAX_LEVELS)) + if(QT_SET_CNT(optr) < QT_SET_THRESHOLD || (n > (QT_MAX_LEVELS-2))) return(qtadduelem(qt,t_id)); /* otherwise: expand node- and insert tri, and reinsert existing tris in set to children of new node @@ -697,22 +688,21 @@ int v0_id,v1_id,v2_id; SM_NTH_VERT(sm,v2_id) = t_id; if(SM_BASE_ID(sm,v0_id) || SM_BASE_ID(sm,v1_id) || SM_BASE_ID(sm,v2_id)) - { - smClear_tri_flags(sm,t_id); SM_SET_NTH_T_BASE(sm,t_id); - } - else - { - SM_CLR_NTH_T_BASE(sm,t_id); - SM_SET_NTH_T_ACTIVE(sm,t_id); - SM_SET_NTH_T_NEW(sm,t_id); - S_SET_FLAG(T_NTH_V(t,0)); - S_SET_FLAG(T_NTH_V(t,1)); - S_SET_FLAG(T_NTH_V(t,2)); - SM_SAMPLE_TRIS(sm)++; - smNew_tri_cnt++; - } + if(SM_DIR_ID(sm,v0_id) || SM_DIR_ID(sm,v1_id) || SM_DIR_ID(sm,v2_id)) + SM_SET_NTH_T_BG(sm,t_id); + + S_SET_FLAG(T_NTH_V(t,0)); + S_SET_FLAG(T_NTH_V(t,1)); + S_SET_FLAG(T_NTH_V(t,2)); + + SM_SET_NTH_T_ACTIVE(sm,t_id); + SM_SET_NTH_T_NEW(sm,t_id); + + SM_SAMPLE_TRIS(sm)++; + smNew_tri_cnt++; + /* return initialized triangle */ return(t_id); } @@ -769,6 +759,7 @@ smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add_p !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,1))) || !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,2)))) goto Ltri_error; + /* if(SM_NTH_TRI(sm,T_NTH_NBR(ta,0))==SM_NTH_TRI(sm,T_NTH_NBR(ta,1)) || SM_NTH_TRI(sm,T_NTH_NBR(ta,0))==SM_NTH_TRI(sm,T_NTH_NBR(ta,2)) || SM_NTH_TRI(sm,T_NTH_NBR(ta,1))==SM_NTH_TRI(sm,T_NTH_NBR(ta,2)) || @@ -776,6 +767,7 @@ smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add_p SM_NTH_TRI(sm,T_NTH_NBR(tb,0))==SM_NTH_TRI(sm,T_NTH_NBR(tb,2)) || SM_NTH_TRI(sm,T_NTH_NBR(tb,1))==SM_NTH_TRI(sm,T_NTH_NBR(tb,2)) ) goto Ltri_error; + */ #endif /* Reset neighbor pointers of original neighbors */ n = SM_NTH_TRI(sm,T_NTH_NBR(t,enext)); @@ -811,16 +803,10 @@ smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add_p remove_from_list(t_id,add_ptr); remove_from_list(t1_id,add_ptr); -#if 1 + smDelete_tri(sm,t_id); smDelete_tri(sm,t1_id); -#else - *del_ptr = push_data(*del_ptr,t_id); - *del_ptr = push_data(*del_ptr,t1_id); -#endif - - *tn_id = ta_id; *tn1_id = tb_id; @@ -850,9 +836,8 @@ smUpdate_locator(sm,add_list) SM *sm; LIST *add_list; { - int t_id,i; + int t_id; TRI *t; - OBJECT *optr; while(add_list) { @@ -872,7 +857,7 @@ LIST *tlist,*add_list; FVECT p,p0,p1,p2; int e,e1,swapped = 0; int t_id,t_opp_id; - LIST *del_list=NULL; + LIST *del_list=NULL,*lptr; VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); while(tlist) @@ -894,9 +879,9 @@ LIST *tlist,*add_list; if(!T_IS_VALID(t_opp)) error(CONSISTENCY,"Invalid trismFix_tris()\n"); #endif - smDir_in_cone(sm,p0,T_NTH_V(t_opp,0)); - smDir_in_cone(sm,p1,T_NTH_V(t_opp,1)); - smDir_in_cone(sm,p2,T_NTH_V(t_opp,2)); + smDir(sm,p0,T_NTH_V(t_opp,0)); + smDir(sm,p1,T_NTH_V(t_opp,1)); + smDir(sm,p2,T_NTH_V(t_opp,2)); if(point_in_cone(p,p0,p1,p2)) { swapped = 1; @@ -909,13 +894,7 @@ LIST *tlist,*add_list; tlist = push_data(tlist,t_opp_id); } } -#if 0 - while(del_list) - { - t_id = pop_list(&del_list); - smDelete_tri(sm,t_id); - } -#endif + smUpdate_locator(sm,add_list); return(swapped); @@ -967,7 +946,6 @@ smInsert_samp(sm,s_id,tri_id,on,which) FVECT npt; TRI *tri,*nbr,*topp; - add_list = NULL; for(i=0; i<3;i++) v_id[i] = T_NTH_V(SM_NTH_TRI(sm,tri_id),i); @@ -1226,12 +1204,6 @@ int *onptr,*whichptr; optr = qtqueryset(qt); tri_id = smTri_in_set(sm,tpt,optr,onptr,whichptr); -#ifdef DEBUG - if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tri_id),0))) || - !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tri_id),1))) || - !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tri_id),2)))) - eputs("Invalid tri nbrs smPointLocateTri()\n"); -#endif return(tri_id); } @@ -1285,29 +1257,22 @@ smTest_sample(sm,tri_id,dir,p,rptr) for(i=0; i<3; i++) { - if(SM_BASE_ID(sm,vid[i])) - { - bcnt++; - continue; - } - if(SM_DIR_ID(sm,vid[i])) - dcnt++; - VSUB(diff[i],SM_NTH_WV(sm,vid[i]),p); - /* If same world point: replace */ + if(SM_BASE_ID(sm,vid[i])) + bcnt++; + if(SM_DIR_ID(sm,vid[i])) + dcnt++; + } /* TEST 1: If the new sample is close in ws, and close in the spherical projection to one of the triangle vertex samples */ +#if 0 norm = FALSE; - if(bcnt + dcnt != 3) - { VSUB(spt,p,SM_VIEW_CENTER(sm)); ds = DOT(spt,spt); dnear = FHUGE; for(i=0; i<3; i++) { - if(SM_BASE_ID(sm,vid[i]) || SM_DIR_ID(sm,vid[i])) - continue; d = DOT(diff[i],diff[i])/ds; if(d < dnear) { @@ -1316,11 +1281,23 @@ smTest_sample(sm,tri_id,dir,p,rptr) } } - if(dnear <= smMinSampDiff*smMinSampDiff) + if(dnear <= SM_MIN_SAMP_DIFF*SM_MIN_SAMP_DIFF) { /* Pick the point with dir closest to that of the canonical view if it is the new sample: mark existing point for deletion */ + if(SM_BASE_ID(sm,nearid)) + { + *rptr = nearid; + return(TRUE); + } + if(SM_DIR_ID(sm,nearid)) + return(FALSE); + if(!dir) + { + *rptr = nearid; + return(TRUE); + } normalize(spt); norm = TRUE; VSUB(npt,SM_NTH_WV(sm,nearid),SM_VIEW_CENTER(sm)); @@ -1328,27 +1305,26 @@ smTest_sample(sm,tri_id,dir,p,rptr) d = fdir2diff(SM_NTH_W_DIR(sm,nearid), npt); d2 = 2. - 2.*DOT(dir,spt); /* The existing sample is a better sample:punt */ - if(d2 > d) + if(d2 > d) return(FALSE); - else - { - /* The new sample is better: mark the existing one + else + { + /* The new sample is better: mark the existing one for deletion after the new one is added*/ - *rptr = nearid; - return(TRUE); - } + *rptr = nearid; + return(TRUE); } - } + } + /* TEST 3: If the spherical projection of new is < S_REPLACE_EPS from a base point: Edge length is constrained to subtend <45 degrees: original base mesh edges are approx 32 degrees- so have about 13 degrees to work in: S_REPLACE_EPS is the square of the radian value */ + if(bcnt) { dnear = FHUGE; - if(bcnt + dcnt ==3) - VSUB(spt,p,SM_VIEW_CENTER(sm)); if(!norm) normalize(spt); @@ -1358,7 +1334,7 @@ smTest_sample(sm,tri_id,dir,p,rptr) continue; VSUB(npt,SM_NTH_WV(sm,vid[i]),SM_VIEW_CENTER(sm)); d = DIST_SQ(npt,spt); - if(d < S_REPLACE_EPS && d < dnear) + if(dnear <= SM_MIN_SAMP_DIFF*SM_MIN_SAMP_DIFF && d< near) { dnear = d; nearid = vid[i]; @@ -1371,22 +1347,81 @@ smTest_sample(sm,tri_id,dir,p,rptr) return(TRUE); } } +#else + { + FVECT nearpt; + dnear = FHUGE; + VSUB(spt,p,SM_VIEW_CENTER(sm)); + ds = DOT(spt,spt); + normalize(spt); + + for(i=0; i<3; i++) + { + VSUB(npt,SM_NTH_WV(sm,vid[i]),SM_VIEW_CENTER(sm)); + + if(!SM_BASE_ID(sm,vid[i]) && !SM_DIR_ID(sm,vid[i])) + normalize(npt); + + d = DIST_SQ(npt,spt); + if(d < SM_MIN_SAMP_DIFF*SM_MIN_SAMP_DIFF && d < dnear) + { + dnear = d; + nearid = vid[i]; + VCOPY(nearpt,npt); + } + + } + if(dnear != FHUGE) + { + /* Pick the point with dir closest to that of the canonical view + if it is the new sample: mark existing point for deletion + */ + if(SM_BASE_ID(sm,nearid)) + { + *rptr = nearid; + return(TRUE); + } + if(SM_DIR_ID(sm,nearid)) + return(FALSE); + if(!dir) + { + *rptr = nearid; + return(TRUE); + } + d = fdir2diff(SM_NTH_W_DIR(sm,nearid), nearpt); + d2 = 2. - 2.*DOT(dir,spt); + /* The existing sample is a better sample:punt */ + if(d2 > d) + return(FALSE); + else + { + /* The new sample is better: mark the existing one + for deletion after the new one is added*/ + *rptr = nearid; + return(TRUE); + } + } + } +#endif /* TEST 4: If the addition of the new sample point would introduce a "puncture" or cause new triangles with large depth differences:dont add: */ if(bcnt || dcnt) return(TRUE); + /* If the new point is in front of the existing points- add */ dv = DIST_SQ(SM_NTH_WV(sm,vid[0]),SM_VIEW_CENTER(sm)); if(ds < dv) return(TRUE); d01 = DIST_SQ(SM_NTH_WV(sm,vid[1]),SM_NTH_WV(sm,vid[0])); + VSUB(diff[0],SM_NTH_WV(sm,vid[0]),p); s0 = DOT(diff[0],diff[0]); if(s0 < S_REPLACE_SCALE*d01) return(TRUE); + d12 = DIST_SQ(SM_NTH_WV(sm,vid[2]),SM_NTH_WV(sm,vid[1])); if(s0 < S_REPLACE_SCALE*d12) return(TRUE); @@ -1394,9 +1429,11 @@ smTest_sample(sm,tri_id,dir,p,rptr) if(s0 < S_REPLACE_SCALE*d20) return(TRUE); d = MIN3(d01,d12,d20); - s1 = DOT(diff[1],diff[1]); + VSUB(diff[1],SM_NTH_WV(sm,vid[1]),p); + s1 = DOT(diff[1],diff[1]); if(s1 < S_REPLACE_SCALE*d) return(TRUE); + VSUB(diff[2],SM_NTH_WV(sm,vid[2]),p); s2 = DOT(diff[2],diff[2]); if(s2 < S_REPLACE_SCALE*d) return(TRUE); @@ -1413,29 +1450,41 @@ smTest_sample(sm,tri_id,dir,p,rptr) return(FALSE); } - -int -smAlloc_samp(sm) +smReplace_base_samp(sm,b_id,s_id,tri,t_id,which) SM *sm; +int b_id,s_id; +TRI *tri; +int t_id,which; { - int s_id,replaced,cnt; - SAMP *s; - FVECT p; + TRI *t; - s = SM_SAMP(sm); - s_id = sAlloc_samp(s,&replaced); - - cnt=0; - while(replaced) + SM_NTH_VERT(sm,s_id) = t_id; + T_NTH_V(tri,which) = s_id; + if(!(SM_BASE_ID(sm,T_NTH_V(tri,(which+1)%3)) || + SM_BASE_ID(sm,T_NTH_V(tri,(which+2)%3)))) + SM_CLR_NTH_T_BASE(sm,t_id); + if(!SM_IS_NTH_T_NEW(sm,t_id)) { - if(smRemoveVertex(sm,s_id)) - break; - s_id = sAlloc_samp(s,&replaced); - cnt++; - if(cnt > S_MAX_SAMP(s)) - error(CONSISTENCY,"smAlloc_samp():unable to find free samp\n"); + smNew_tri_cnt++; + SM_SET_NTH_T_NEW(sm,t_id); } - return(s_id); + t_id = smTri_next_ccw_nbr(sm,tri,b_id); + while(t_id != INVALID) + { + t = SM_NTH_TRI(sm,t_id); + which = T_WHICH_V(t,b_id); + T_NTH_V(t,which) = s_id; + /* Check if still a base triangle */ + if(!(SM_BASE_ID(sm,T_NTH_V(t,(which+1)%3)) || + SM_BASE_ID(sm,T_NTH_V(t,(which+2)%3)))) + SM_CLR_NTH_T_BASE(sm,t_id); + if(!SM_IS_NTH_T_NEW(sm,t_id)) + { + smNew_tri_cnt++; + SM_SET_NTH_T_NEW(sm,t_id); + } + t_id = smTri_next_ccw_nbr(sm,t,b_id); + } } int @@ -1445,7 +1494,7 @@ smReplace_samp(sm,c,dir,p,s_id,t_id,o_id,on,which) FVECT dir,p; int s_id,t_id,o_id,on,which; { - int tonemap,v_id; + int v_id,tri_id; TRI *t,*tri; tri = SM_NTH_TRI(sm,t_id); @@ -1454,58 +1503,110 @@ smReplace_samp(sm,c,dir,p,s_id,t_id,o_id,on,which) /* If it is a base id, need new sample */ if(SM_BASE_ID(sm,v_id)) { - tonemap = (SM_TONE_MAP(sm) > s_id); - sInit_samp(SM_SAMP(sm),s_id,c,dir,p,o_id,tonemap); - SM_NTH_VERT(sm,s_id) = t_id; - T_NTH_V(tri,which) = s_id; - if(!(SM_BASE_ID(sm,T_NTH_V(tri,(which+1)%3)) || - SM_BASE_ID(sm,T_NTH_V(tri,(which+2)%3)))) - SM_CLR_NTH_T_BASE(sm,t_id); - t_id = smTri_next_ccw_nbr(sm,tri,v_id); - while(t_id != INVALID) - { - t = SM_NTH_TRI(sm,t_id); - which = T_WHICH_V(t,v_id); - T_NTH_V(t,which) = s_id; - /* Check if still a base triangle */ - if(!(SM_BASE_ID(sm,T_NTH_V(t,(which+1)%3)) || - SM_BASE_ID(sm,T_NTH_V(t,(which+2)%3)))) - SM_CLR_NTH_T_BASE(sm,t_id); - t_id = smTri_next_ccw_nbr(sm,t,v_id); - } + sInit_samp(SM_SAMP(sm),s_id,c,dir,p,o_id); + smReplace_base_samp(sm,v_id,s_id,tri,t_id,which); return(s_id); } - else - if(on == ON_V || !p) + if(dir) + { + /* If world point */ + /* if existing point is a dir: leave */ + if(SM_DIR_ID(sm,v_id)) + return(INVALID); + if(on == ON_V) { - tonemap = (SM_TONE_MAP(sm) > v_id); - sInit_samp(SM_SAMP(sm),v_id,c,dir,p,o_id,tonemap); + sInit_samp(SM_SAMP(sm),v_id,c,dir,p,o_id); + + if(!SM_IS_NTH_T_NEW(sm,t_id)) + { + smNew_tri_cnt++; + SM_SET_NTH_T_NEW(sm,t_id); + } + tri_id = smTri_next_ccw_nbr(sm,tri,v_id); + while(tri_id != t_id) + { + t = SM_NTH_TRI(sm,tri_id); + if(!SM_IS_NTH_T_NEW(sm,tri_id)) + { + smNew_tri_cnt++; + SM_SET_NTH_T_NEW(sm,tri_id); + } + + tri_id = smTri_next_ccw_nbr(sm,t,v_id); + } return(v_id); } - else /* on == ON_P */ - { - FVECT spt,npt; - double d,d2; + /* on == ON_P */ + else + { + FVECT spt,npt; + double d,d2; - /* Need to check which sample is preferable */ - VSUB(spt,p,SM_VIEW_CENTER(sm)); - normalize(spt); + /* Need to check which sample is preferable */ + VSUB(spt,p,SM_VIEW_CENTER(sm)); + normalize(spt); - VSUB(npt,SM_NTH_WV(sm,v_id),SM_VIEW_CENTER(sm)); - normalize(npt); - d = fdir2diff(SM_NTH_W_DIR(sm,v_id), npt); - d2 = 2. - 2.*DOT(dir,spt); + VSUB(npt,SM_NTH_WV(sm,v_id),SM_VIEW_CENTER(sm)); + normalize(npt); + d = fdir2diff(SM_NTH_W_DIR(sm,v_id), npt); + d2 = 2. - 2.*DOT(dir,spt); /* The existing sample is a better sample:punt */ - if(d2 < d) - { - /* The new sample has better information- replace values */ - tonemap = (SM_TONE_MAP(sm) > v_id); - sInit_samp(SM_SAMP(sm),v_id,c,dir,p,o_id,tonemap); - } - return(v_id); + if(d2 < d) + { + /* The new sample has better information- replace values */ + sInit_samp(SM_SAMP(sm),v_id,c,dir,p,o_id); + if(!SM_IS_NTH_T_NEW(sm,t_id)) + { + smNew_tri_cnt++; + SM_SET_NTH_T_NEW(sm,t_id); + } + + tri_id = smTri_next_ccw_nbr(sm,tri,v_id); + while(tri_id != t_id) + { + t = SM_NTH_TRI(sm,tri_id); + if(!SM_IS_NTH_T_NEW(sm,tri_id)) + { + smNew_tri_cnt++; + SM_SET_NTH_T_NEW(sm,tri_id); + } + tri_id = smTri_next_ccw_nbr(sm,t,v_id); + } + } + return(v_id); + } + } + else + { /* New point is a dir */ + return(INVALID); } } +int +smAlloc_samp(sm) +SM *sm; +{ + int s_id,replaced,cnt; + SAMP *s; + FVECT p; + + s = SM_SAMP(sm); + s_id = sAlloc_samp(s,&replaced); + + cnt=0; + while(replaced) + { + if(smRemoveVertex(sm,s_id)) + break; + s_id = sAlloc_samp(s,&replaced); + cnt++; + if(cnt > S_MAX_SAMP(s)) + error(CONSISTENCY,"smAlloc_samp():unable to find free samp\n"); + } + return(s_id); +} + + /* Add sample to the mesh: the sample can be a world space or directional point. If o_id !=INVALID, @@ -1537,55 +1638,82 @@ smAdd_samp(sm,c,dir,p,o_id) /* If sample is a world space point */ if(p) { - t_id = smPointLocateTri(sm,p,&on,&which); - if(t_id == INVALID) + while(1) + { + t_id = smPointLocateTri(sm,p,&on,&which); + if(t_id == INVALID) { #ifdef DEBUG - eputs("smAddSamp(): unable to locate tri containing sample \n"); + eputs("smAddSamp(): unable to locate tri containing sample \n"); #endif + smUnalloc_samp(sm,s_id); + return(INVALID); + } + /* If spherical projection coincides with existing sample: replace */ + if((on == ON_V || on == ON_P)) + { + n_id = smReplace_samp(sm,c,dir,p,s_id,t_id,o_id,on,which); + if(n_id!= s_id) + smUnalloc_samp(sm,s_id); + return(n_id); + } + if((!(smTest_sample(sm,t_id,dir,p,&r_id)))) + { smUnalloc_samp(sm,s_id); return(INVALID); } - /* If spherical projection coincides with existing sample: replace */ - if((on == ON_V || on == ON_P)) - { - if((n_id = smReplace_samp(sm,c,dir,p,s_id,t_id,o_id,on,which))!= s_id) - smUnalloc_samp(sm,s_id); - return(n_id); + if(r_id != INVALID) + { + smRemoveVertex(sm,r_id); + sDelete_samp(SM_SAMP(sm),r_id); + } + else + break; } - if((!(smTest_sample(sm,t_id,dir,p,&r_id)))) - { - smUnalloc_samp(sm,s_id); - return(INVALID); - } /* If sample is being added in the middle of the sample array: tone map individually */ /* Initialize sample */ - sInit_samp(SM_SAMP(sm),s_id,c,dir,p,o_id,(SM_TONE_MAP(sm)>s_id)); + sInit_samp(SM_SAMP(sm),s_id,c,dir,p,o_id); } /* If sample is a direction vector */ else { VADD(wpt,dir,SM_VIEW_CENTER(sm)); - t_id = smPointLocateTri(sm,wpt,&on,&which); - if(t_id == INVALID) - { + while(1) + { + t_id = smPointLocateTri(sm,wpt,&on,&which); + if(t_id == INVALID) + { #ifdef DEBUG - eputs("smAddSamp(): unable to locate tri containing sample \n"); + eputs("smAddSamp(): can'tlocate tri containing samp\n"); #endif - smUnalloc_samp(sm,s_id); - return(INVALID); + smUnalloc_samp(sm,s_id); + return(INVALID); + } + if(on == ON_V || on == ON_P) + { + n_id=smReplace_samp(sm,c,NULL,wpt,s_id,t_id,o_id,on,which); + if(n_id !=s_id) + smUnalloc_samp(sm,s_id); + return(n_id); + } + if((!(smTest_sample(sm,t_id,NULL,wpt,&r_id)))) + { + smUnalloc_samp(sm,s_id); + return(INVALID); + } + if(r_id != INVALID) + { + smRemoveVertex(sm,r_id); + sDelete_samp(SM_SAMP(sm),r_id); + } + else + break; } - if(on == ON_V || on == ON_P) - { - if((n_id = smReplace_samp(sm,c,wpt,NULL,s_id,t_id,o_id,on,which))!= s_id) - smUnalloc_samp(sm,s_id); - return(n_id); - } /* Allocate space for a sample and initialize */ - sInit_samp(SM_SAMP(sm),s_id,c,wpt,NULL,o_id,(SM_TONE_MAP(sm)>s_id)); + sInit_samp(SM_SAMP(sm),s_id,c,NULL,wpt,o_id); } if(!SM_DIR_ID(sm,s_id)) { @@ -1596,12 +1724,6 @@ smAdd_samp(sm,c,dir,p,o_id) } smInsert_samp(sm,s_id,t_id,on,which); - /* If new sample replaces existing one- remove that vertex now */ - if(r_id != INVALID) - { - smRemoveVertex(sm,r_id); - sDelete_samp(SM_SAMP(sm),r_id); - } return(s_id); } @@ -1624,9 +1746,7 @@ FVECT p; { int s_id; - /* First check if this the first sample: if so initialize mesh */ - if(SM_NUM_SAMP(smMesh) == 0) { smInit_sm(smMesh,odev.v.vp); @@ -1700,63 +1820,6 @@ int type; } - -int -smNext_tri_flag_set(sm,i,which,b) - SM *sm; - int i,which; - int b; -{ - - for(; i < SM_NUM_TRI(sm);i++) - { - - if(!T_IS_VALID(SM_NTH_TRI(sm,i))) - continue; - if(!SM_IS_NTH_T_FLAG(sm,i,which)) - continue; - if(!b) - break; - if((b==1) && !SM_BG_TRI(sm,i)) - break; - if((b==2) && SM_BG_TRI(sm,i)) - break; - } - - return(i); -} - - -int -smNext_valid_tri(sm,i) - SM *sm; - int i; -{ - - while( i < SM_NUM_TRI(sm) && !T_IS_VALID(SM_NTH_TRI(sm,i))) - i++; - - return(i); -} - - - -qtTri_from_id(t_id,v0,v1,v2) -int t_id; -FVECT v0,v1,v2; -{ - TRI *t; - - t = SM_NTH_TRI(smMesh,t_id); - if(!T_IS_VALID(t)) - return(0); - VSUB(v0,SM_T_NTH_WV(smMesh,t,0),SM_VIEW_CENTER(smMesh)); - VSUB(v1,SM_T_NTH_WV(smMesh,t,1),SM_VIEW_CENTER(smMesh)); - VSUB(v2,SM_T_NTH_WV(smMesh,t,2),SM_VIEW_CENTER(smMesh)); - return(1); -} - - smRebuild_mesh(sm,v) SM *sm; VIEW *v; @@ -1768,6 +1831,7 @@ smRebuild_mesh(sm,v) #ifdef DEBUG fprintf(stderr,"smRebuild_mesh(): rebuilding...."); #endif + smCull(sm,v,SM_ALL_LEVELS); /* Clear the mesh- and rebuild using the current sample array */ /* Remember the current number of samples */ cnt = SM_NUM_SAMP(sm); @@ -1807,8 +1871,6 @@ smRebuild_mesh(sm,v) } } - - smNew_tri_cnt = SM_SAMPLE_TRIS(sm); #ifdef DEBUG fprintf(stderr,"smRebuild_mesh():done\n"); #endif @@ -1831,80 +1893,28 @@ intersect_tri_set(t_set,orig,dir,pt) { t_id = QT_SET_NEXT_ELEM(optr); t = SM_NTH_TRI(smMesh,t_id); - if(!T_IS_VALID(t)) + if(!T_IS_VALID(t) || SM_IS_NTH_T_BASE(smMesh,t_id)|| + SM_IS_NTH_T_BG(smMesh,t_id)) continue; pid0 = T_NTH_V(t,0); pid1 = T_NTH_V(t,1); pid2 = T_NTH_V(t,2); - if(base = SM_IS_NTH_T_BASE(smMesh,t_id)) - if(SM_BASE_ID(smMesh,pid0) && SM_BASE_ID(smMesh,pid1) && - SM_BASE_ID(smMesh,pid2)) - continue; 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)) { - if(!base) - { - d = DIST_SQ(p,p0); - d1 = DIST_SQ(p,p1); - if(d < d1) - { - d1 = DIST_SQ(p,p2); - id = (d1 < d)?pid2:pid0; - } - else - { - d = DIST_SQ(p,p2); - id = (d < d1)? pid2:pid1; - } - } + d = DIST_SQ(p,p0); + d1 = DIST_SQ(p,p1); + if(d < d1) + { + d1 = DIST_SQ(p,p2); + id = (d1 < d)?pid2:pid0; + } else { - if(SM_BASE_ID(smMesh,pid0)) - { - if(SM_BASE_ID(smMesh,pid1)) - id = pid2; - else - if(SM_BASE_ID(smMesh,pid2)) - id = pid1; - else - { - d = DIST_SQ(p,p1); - d1 = DIST_SQ(p,p2); - if(d < d1) - id = pid1; - else - id = pid2; - } - } - else - { - if(SM_BASE_ID(smMesh,pid1)) - { - if(SM_BASE_ID(smMesh,pid2)) - id = pid0; - else - { - d = DIST_SQ(p,p0); - d1 = DIST_SQ(p,p2); - if(d < d1) - id = pid0; - else - id = pid2; - } - } - else - { - d = DIST_SQ(p,p0); - d1 = DIST_SQ(p,p1); - if(d < d1) - id = pid0; - else - id = pid1; - } - } + d = DIST_SQ(p,p2); + id = (d < d1)? pid2:pid1; } if(pt) VCOPY(pt,p); @@ -2041,10 +2051,6 @@ FVECT orig,dir; #ifdef DEBUG_TEST_DRIVER VCOPY(Pick_point[0],p); #endif -#ifdef DEBUG - fprintf(stderr,"Simple pick returning %d\n",s_id); -#endif - return(s_id); } d = point_on_sphere(b,orig,SM_VIEW_CENTER(smMesh)); @@ -2058,9 +2064,6 @@ FVECT orig,dir; #ifdef DEBUG_TEST_DRIVER VCOPY(Pick_point[0],p); #endif -#ifdef DEBUG - fprintf(stderr,"Simple pick2 returning %d\n",s_id); -#endif return(s_id); } if(OPP_EQUAL_VEC3(b,dir)) @@ -2110,10 +2113,8 @@ FVECT orig,dir; F_ARGS(func) = (int *)(&rt); stTrace_ray(SM_LOCATOR(smMesh),o,dir,func); s_id = rt.t_id; + } -#ifdef DEBUG - fprintf(stderr,"Trace pick returning %d\n",s_id); -#endif return(s_id); Lerror: @@ -2124,11 +2125,20 @@ Lerror: } +null_func(argptr,root,qt,n) + int *argptr; + int root; + QUADTREE qt; + int n; +{ + /* do nothing */ +} -mark_active_tris(argptr,root,qt) +mark_active_tris(argptr,root,qt,n) int *argptr; int root; QUADTREE qt; + int n; { OBJECT *os,*optr; register int i,t_id; @@ -2145,43 +2155,51 @@ mark_active_tris(argptr,root,qt) t_id = QT_SET_NEXT_ELEM(optr); /* Set the render flag */ tri = SM_NTH_TRI(smMesh,t_id); - if(!T_IS_VALID(tri) || SM_IS_NTH_T_BASE(smMesh,t_id)) + if(!T_IS_VALID(tri)) continue; SM_SET_NTH_T_ACTIVE(smMesh,t_id); /* Set the Active bits of the Vertices */ S_SET_FLAG(T_NTH_V(tri,0)); S_SET_FLAG(T_NTH_V(tri,1)); S_SET_FLAG(T_NTH_V(tri,2)); - } + } } -mark_tris_in_frustum(view) +smCull(sm,view,n) + SM *sm; VIEW *view; + int n; { FVECT nr[4],far[4]; FPEQ peq; int debug=0; FUNC f; - F_FUNC(f) = mark_active_tris; - F_ARGS(f) = NULL; + /* First clear all the quadtree node flags */ + qtClearAllFlags(); + F_ARGS(f) = NULL; + /* If marking samples down to leaves */ + if(n == SM_ALL_LEVELS) + { /* Mark triangles in approx. view frustum as being active:set LRU counter: for use in discarding samples when out of space + */ + F_FUNC(f) = mark_active_tris; + smClear_flags(sm,T_ACTIVE_FLAG); + /* Clear all of the active sample flags*/ + sClear_all_flags(SM_SAMP(sm)); + } + else + /* Just mark qtree flags */ + F_FUNC(f) = null_func; + + /* calculate the world space coordinates of the view frustum: Radiance often has no far clipping plane: but driver will set dev_zmin,dev_zmax to satisfy OGL - */ - - /* First clear all the quadtree node and triangle active flags */ - qtClearAllFlags(); - smClear_flags(smMesh,T_ACTIVE_FLAG); - /* Clear all of the active sample flags*/ - sClear_all_flags(SM_SAMP(smMesh)); - - - /* calculate the world space coordinates of the view frustum */ + */ calculate_view_frustum(view->vp,view->hvec,view->vvec,view->horiz, view->vert, dev_zmin,dev_zmax,nr,far); @@ -2202,80 +2220,80 @@ mark_tris_in_frustum(view) Also set the triangles LRU clock counter */ - if(EQUAL_VEC3(view->vp,SM_VIEW_CENTER(smMesh))) + if(EQUAL_VEC3(view->vp,SM_VIEW_CENTER(sm))) {/* Near face triangles */ - smLocator_apply(smMesh,nr[0],nr[2],nr[3],f); - smLocator_apply(smMesh,nr[2],nr[0],nr[1],f); + smLocator_apply(sm,nr[0],nr[2],nr[3],f,n); + smLocator_apply(sm,nr[2],nr[0],nr[1],f,n); return; } /* Test the view against the planes: and swap orientation if inside:*/ tri_plane_equation(nr[0],nr[2],nr[3], &peq,FALSE); - if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) + if(PT_ON_PLANE(SM_VIEW_CENTER(sm),peq) < 0.0) {/* Near face triangles */ - smLocator_apply(smMesh,nr[3],nr[2],nr[0],f); - smLocator_apply(smMesh,nr[1],nr[0],nr[2],f); + smLocator_apply(sm,nr[3],nr[2],nr[0],f,n); + smLocator_apply(sm,nr[1],nr[0],nr[2],f,n); } else {/* Near face triangles */ - smLocator_apply(smMesh,nr[0],nr[2],nr[3],f); - smLocator_apply(smMesh,nr[2],nr[0],nr[1],f); + smLocator_apply(sm,nr[0],nr[2],nr[3],f,n); + smLocator_apply(sm,nr[2],nr[0],nr[1],f,n); } tri_plane_equation(nr[0],far[3],far[0], &peq,FALSE); - if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) + if(PT_ON_PLANE(SM_VIEW_CENTER(sm),peq) < 0.0) { /* Right face triangles */ - smLocator_apply(smMesh,far[0],far[3],nr[0],f); - smLocator_apply(smMesh,nr[3],nr[0],far[3],f); + smLocator_apply(sm,far[0],far[3],nr[0],f,n); + smLocator_apply(sm,nr[3],nr[0],far[3],f,n); } else {/* Right face triangles */ - smLocator_apply(smMesh,nr[0],far[3],far[0],f); - smLocator_apply(smMesh,far[3],nr[0],nr[3],f); + smLocator_apply(sm,nr[0],far[3],far[0],f,n); + smLocator_apply(sm,far[3],nr[0],nr[3],f,n); } tri_plane_equation(nr[1],far[2],nr[2], &peq,FALSE); if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) { /* Left face triangles */ - smLocator_apply(smMesh,nr[2],far[2],nr[1],f); - smLocator_apply(smMesh,far[1],nr[1],far[2],f); + smLocator_apply(sm,nr[2],far[2],nr[1],f,n); + smLocator_apply(sm,far[1],nr[1],far[2],f,n); } else { /* Left face triangles */ - smLocator_apply(smMesh,nr[1],far[2],nr[2],f); - smLocator_apply(smMesh,far[2],nr[1],far[1],f); + smLocator_apply(sm,nr[1],far[2],nr[2],f,n); + smLocator_apply(sm,far[2],nr[1],far[1],f,n); } tri_plane_equation(nr[0],far[0],nr[1], &peq,FALSE); - if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) + if(PT_ON_PLANE(SM_VIEW_CENTER(sm),peq) < 0.0) {/* Top face triangles */ - smLocator_apply(smMesh,nr[1],far[0],nr[0],f); - smLocator_apply(smMesh,far[1],far[0],nr[1],f); + smLocator_apply(sm,nr[1],far[0],nr[0],f,n); + smLocator_apply(sm,far[1],far[0],nr[1],f,n); } else {/* Top face triangles */ - smLocator_apply(smMesh,nr[0],far[0],nr[1],f); - smLocator_apply(smMesh,nr[1],far[0],far[1],f); + smLocator_apply(sm,nr[0],far[0],nr[1],f,n); + smLocator_apply(sm,nr[1],far[0],far[1],f,n); } tri_plane_equation(nr[3],nr[2],far[3], &peq,FALSE); - if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) + if(PT_ON_PLANE(SM_VIEW_CENTER(sm),peq) < 0.0) {/* Bottom face triangles */ - smLocator_apply(smMesh,far[3],nr[2],nr[3],f); - smLocator_apply(smMesh,far[3],far[2],nr[2],f); + smLocator_apply(sm,far[3],nr[2],nr[3],f,n); + smLocator_apply(sm,far[3],far[2],nr[2],f,n); } else { /* Bottom face triangles */ - smLocator_apply(smMesh,nr[3],nr[2],far[3],f); - smLocator_apply(smMesh,nr[2],far[2],far[3],f); + smLocator_apply(sm,nr[3],nr[2],far[3],f,n); + smLocator_apply(sm,nr[2],far[2],far[3],f,n); } tri_plane_equation(far[2],far[0],far[1], &peq,FALSE); - if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) + if(PT_ON_PLANE(SM_VIEW_CENTER(sm),peq) < 0.0) {/* Far face triangles */ - smLocator_apply(smMesh,far[0],far[2],far[1],f); - smLocator_apply(smMesh,far[2],far[0],far[3],f); + smLocator_apply(sm,far[0],far[2],far[1],f,n); + smLocator_apply(sm,far[2],far[0],far[3],f,n); } else {/* Far face triangles */ - smLocator_apply(smMesh,far[1],far[2],far[0],f); - smLocator_apply(smMesh,far[3],far[0],far[2],f); + smLocator_apply(sm,far[1],far[2],far[0],f,n); + smLocator_apply(sm,far[3],far[0],far[2],f,n); } }