ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/sm.c
Revision: 3.7
Committed: Wed Sep 16 18:16:28 1998 UTC (25 years, 6 months ago) by gwlarson
Content type: text/plain
Branch: MAIN
Changes since 3.6: +130 -105 lines
Log Message:
implemented integer triangle tracing

File Contents

# User Rev Content
1 gwlarson 3.1 /* Copyright (c) 1998 Silicon Graphics, Inc. */
2    
3     #ifndef lint
4     static char SCCSid[] = "$SunId$ SGI";
5     #endif
6    
7     /*
8     * sm.c
9     */
10     #include "standard.h"
11     #include "sm_list.h"
12     #include "sm_geom.h"
13     #include "sm.h"
14    
15    
16     SM *smMesh = NULL;
17     double smDist_sum=0;
18     int smNew_tri_cnt=0;
19    
20 gwlarson 3.5 static int smBase_nbrs[4][3] = { {3,2,1},{3,0,2},{3,1,0},{1,2,0}};
21    
22 gwlarson 3.1 #ifdef TEST_DRIVER
23     VIEW Current_View = {0,{0,0,0},{0,0,-1},{0,1,0},60,60,0};
24     int Pick_cnt =0;
25 gwlarson 3.5 int Pick_tri = -1,Picking = FALSE,Pick_samp=-1;
26 gwlarson 3.1 FVECT Pick_point[500],Pick_origin,Pick_dir;
27     FVECT Pick_v0[500], Pick_v1[500], Pick_v2[500];
28     FVECT P0,P1,P2;
29     FVECT FrustumNear[4],FrustumFar[4];
30     double dev_zmin=.01,dev_zmax=1000;
31     #endif
32    
33     smDir(sm,ps,id)
34     SM *sm;
35     FVECT ps;
36     int id;
37     {
38     FVECT p;
39    
40     VCOPY(p,SM_NTH_WV(sm,id));
41     point_on_sphere(ps,p,SM_VIEW_CENTER(sm));
42     }
43 gwlarson 3.7 smDir_in_cone(sm,ps,id)
44     SM *sm;
45     FVECT ps;
46     int id;
47     {
48     FVECT p;
49    
50     VCOPY(p,SM_NTH_WV(sm,id));
51     point_on_sphere(ps,p,SM_VIEW_CENTER(sm));
52     }
53 gwlarson 3.1
54     smClear_mesh(sm)
55     SM *sm;
56     {
57     /* Reset the triangle counters */
58     SM_TRI_CNT(sm) = 0;
59     SM_NUM_TRIS(sm) = 0;
60     SM_FREE_TRIS(sm) = -1;
61     }
62    
63     smClear_flags(sm,which)
64     SM *sm;
65     int which;
66     {
67     int i;
68    
69     if(which== -1)
70     for(i=0; i < T_FLAGS;i++)
71     bzero(SM_NTH_FLAGS(sm,i),T_TOTAL_FLAG_BYTES(SM_MAX_TRIS(sm)));
72     else
73     bzero(SM_NTH_FLAGS(sm,which),T_TOTAL_FLAG_BYTES(SM_MAX_TRIS(sm)));
74     }
75    
76     smClear_locator(sm)
77     SM *sm;
78     {
79     STREE *st;
80    
81     st = SM_LOCATOR(sm);
82    
83     stClear(st);
84     }
85    
86     smInit_locator(sm,center,base)
87     SM *sm;
88     FVECT center,base[4];
89     {
90     STREE *st;
91    
92     st = SM_LOCATOR(sm);
93    
94     stInit(st,center,base);
95    
96     }
97    
98     smClear(sm)
99     SM *sm;
100     {
101     smClear_samples(sm);
102     smClear_mesh(sm);
103     smClear_locator(sm);
104     }
105    
106     int
107     smAlloc_tris(sm,max_verts,max_tris)
108     SM *sm;
109     int max_verts,max_tris;
110     {
111     int i,nbytes,vbytes,fbytes;
112    
113     vbytes = max_verts*sizeof(VERT);
114     fbytes = T_TOTAL_FLAG_BYTES(max_tris);
115     nbytes = vbytes + max_tris*sizeof(TRI) +T_FLAGS*fbytes + 8;
116     for(i = 1024; nbytes > i; i <<= 1)
117     ;
118     /* check if casting works correctly */
119     max_tris = (i-vbytes-8)/(sizeof(TRI) + T_FLAG_BYTES);
120     fbytes = T_TOTAL_FLAG_BYTES(max_tris);
121    
122     SM_BASE(sm)=(char *)malloc(vbytes+max_tris*sizeof(TRI)+T_FLAGS*fbytes);
123    
124     if (SM_BASE(sm) == NULL)
125     return(0);
126    
127     SM_TRIS(sm) = (TRI *)SM_BASE(sm);
128     SM_VERTS(sm) = (VERT *)(SM_TRIS(sm) + max_tris);
129    
130     SM_NTH_FLAGS(sm,0) = (int4 *)(SM_VERTS(sm) + max_verts);
131     for(i=1; i < T_FLAGS; i++)
132     SM_NTH_FLAGS(sm,i) = (int4 *)(SM_NTH_FLAGS(sm,i-1)+fbytes/sizeof(int4));
133    
134     SM_MAX_VERTS(sm) = max_verts;
135     SM_MAX_TRIS(sm) = max_tris;
136    
137     smClear_mesh(sm);
138    
139     return(max_tris);
140     }
141    
142    
143    
144     int
145     smAlloc_locator(sm)
146     SM *sm;
147     {
148     STREE *st;
149    
150     st = SM_LOCATOR(sm);
151    
152     st = stAlloc(st);
153    
154     if(st)
155     return(TRUE);
156     else
157     return(FALSE);
158     }
159    
160     /* Initialize/clear global smL sample list for at least n samples */
161     smAlloc(max_samples)
162     register int max_samples;
163     {
164     unsigned nbytes;
165     register unsigned i;
166     int total_points;
167     int max_tris;
168    
169     /* If this is the first call, allocate sample,vertex and triangle lists */
170     if(!smMesh)
171     {
172     if(!(smMesh = (SM *)malloc(sizeof(SM))))
173     error(SYSTEM,"smAlloc():Unable to allocate memory");
174     bzero(smMesh,sizeof(SM));
175     }
176     else
177     { /* If existing structure: first deallocate */
178     if(SM_BASE(smMesh))
179     free(SM_BASE(smMesh));
180     if(SM_SAMP_BASE(smMesh))
181     free(SM_SAMP_BASE(smMesh));
182     }
183    
184     /* First allocate at least n samples + extra points:at least enough
185     necessary to form the BASE MESH- Default = 4;
186     */
187     max_samples = smAlloc_samples(smMesh, max_samples,SM_EXTRA_POINTS);
188    
189     total_points = max_samples + SM_EXTRA_POINTS;
190     max_tris = total_points*2;
191    
192     /* Now allocate space for mesh vertices and triangles */
193     max_tris = smAlloc_tris(smMesh, total_points, max_tris);
194    
195     /* Initialize the structure for point,triangle location.
196     */
197     smAlloc_locator(smMesh);
198    
199     }
200    
201    
202    
203     smInit_mesh(sm,vp)
204     SM *sm;
205     FVECT vp;
206     {
207    
208     /* NOTE: Should be elsewhere?*/
209     smDist_sum = 0;
210     smNew_tri_cnt = 0;
211    
212     VCOPY(SM_VIEW_CENTER(smMesh),vp);
213     smClear_locator(sm);
214     smInit_locator(sm,vp,0);
215     smClear_aux_samples(sm);
216     smClear_mesh(sm);
217     smCreate_base_mesh(sm,SM_DEFAULT);
218     }
219    
220     /*
221     * int
222     * smInit(n) : Initialize/clear data structures for n entries
223     * int n;
224     *
225     * This routine allocates/initializes the sample, mesh, and point-location
226     * structures for at least n samples.
227     * If n is <= 0, then clear data structures. Returns number samples
228     * actually allocated.
229     */
230    
231     int
232     smInit(n)
233     register int n;
234     {
235     int max_vertices;
236    
237     /* If n <=0, Just clear the existing structures */
238     if(n <= 0)
239     {
240     smClear(smMesh);
241     return(0);
242     }
243    
244     /* Total mesh vertices includes the sample points and the extra vertices
245     to form the base mesh
246     */
247     max_vertices = n + SM_EXTRA_POINTS;
248    
249     /* If the current mesh contains enough room, clear and return */
250     if(smMesh && max_vertices <= SM_MAX_VERTS(smMesh))
251     {
252     smClear(smMesh);
253     return(SM_MAX_SAMP(smMesh));
254     }
255     /* Otherwise- mesh must be allocated with the appropriate number of
256     samples
257     */
258     smAlloc(n);
259    
260     return(SM_MAX_SAMP(smMesh));
261     }
262    
263    
264 gwlarson 3.7 smLocator_apply_func(sm,v0,v1,v2,edge_func,interior_func,arg1,arg2)
265     SM *sm;
266     FVECT v0,v1,v2;
267     int (*edge_func)();
268     int (*interior_func)();
269     int *arg1,arg2;
270 gwlarson 3.1 {
271     STREE *st;
272     FVECT p0,p1,p2;
273    
274     st = SM_LOCATOR(sm);
275    
276 gwlarson 3.5 VSUB(p0,v0,SM_VIEW_CENTER(sm));
277     VSUB(p1,v1,SM_VIEW_CENTER(sm));
278     VSUB(p2,v2,SM_VIEW_CENTER(sm));
279 gwlarson 3.1
280 gwlarson 3.7 stApply_to_tri(st,p0,p1,p2,edge_func,interior_func,arg1,arg2);
281 gwlarson 3.1
282     }
283    
284    
285     int
286 gwlarson 3.7 add_tri_expand(qtptr,q0,q1,q2,t0,t1,t2,n,arg,t_id,del_set)
287 gwlarson 3.5 QUADTREE *qtptr;
288     FVECT q0,q1,q2;
289     FVECT t0,t1,t2;
290     int n;
291     int *arg;
292     int t_id;
293 gwlarson 3.7 OBJECT *del_set;
294 gwlarson 3.5 {
295 gwlarson 3.7 OBJECT t_set[QT_MAXSET+1],*optr,*tptr,r_set[QT_MAXSET+1];
296 gwlarson 3.5 int i,id,found;
297     FVECT v0,v1,v2;
298 gwlarson 3.6 TRI *tri;
299 gwlarson 3.7
300 gwlarson 3.5 #ifdef DEBUG_TEST_DRIVER
301     Pick_tri = t_id;
302     Picking = TRUE;
303     #endif
304    
305     if(QT_IS_EMPTY(*qtptr))
306     {
307     *qtptr = qtaddelem(*qtptr,t_id);
308     return(TRUE);
309     }
310 gwlarson 3.7
311 gwlarson 3.5 optr = qtqueryset(*qtptr);
312 gwlarson 3.7 if(del_set)
313     {
314     setintersect(r_set,del_set,optr);
315     if(QT_SET_CNT(r_set) > 0)
316     {
317     qtgetset(t_set,*qtptr);
318     optr = QT_SET_PTR(r_set);
319     for(i = QT_SET_CNT(r_set); i > 0; i--)
320     {
321     id = QT_SET_NEXT_ELEM(optr);
322     deletelem(t_set,id);
323     }
324     qtfreeleaf(*qtptr);
325     *qtptr = qtnewleaf(t_set);
326     optr = t_set;
327     }
328     }
329 gwlarson 3.5 if(!inset(optr,t_id))
330     {
331     if(QT_SET_CNT(optr) < QT_MAXSET)
332     *qtptr = qtaddelem(*qtptr,t_id);
333     else
334     {
335     #ifdef DEBUG
336     eputs("add_tri_expand():no room in set\n");
337     #endif
338     return(FALSE);
339     }
340     }
341     optr = qtqueryset(*qtptr);
342     if(QT_SET_CNT(optr) >= QT_SET_THRESHOLD)
343     if (n < QT_MAX_LEVELS)
344     {
345 gwlarson 3.7 qtgetset(t_set,*qtptr);
346 gwlarson 3.5 /* If set size exceeds threshold: subdivide cell and reinsert tris*/
347     qtfreeleaf(*qtptr);
348     qtSubdivide(qtptr);
349    
350 gwlarson 3.7 for(optr = QT_SET_PTR(t_set),i=QT_SET_CNT(t_set); i > 0; i--)
351 gwlarson 3.5 {
352     id = QT_SET_NEXT_ELEM(optr);
353 gwlarson 3.6 tri = SM_NTH_TRI(smMesh,id);
354     VSUB(v0,SM_T_NTH_WV(smMesh,tri,0),SM_VIEW_CENTER(smMesh));
355     VSUB(v1,SM_T_NTH_WV(smMesh,tri,1),SM_VIEW_CENTER(smMesh));
356     VSUB(v2,SM_T_NTH_WV(smMesh,tri,2),SM_VIEW_CENTER(smMesh));
357     found = qtAdd_tri(qtptr,q0,q1,q2,v0,v1,v2,id,n);
358 gwlarson 3.5 #ifdef DEBUG
359     if(!found)
360     eputs("add_tri_expand():Reinsert\n");
361     #endif
362     }
363     return(QT_MODIFIED);
364     }
365     else
366     if(QT_SET_CNT(optr) < QT_MAXSET)
367     {
368     #ifdef DEBUG_TEST_DRIVER
369     eputs("add_tri_expand():too many levels:can't expand\n");
370     #endif
371     return(TRUE);
372     }
373     else
374     {
375     #ifdef DEBUG
376     eputs("add_tri_expand():too many tris inset:can't add\n");
377     #endif
378     return(FALSE);
379     }
380     }
381    
382    
383     int
384 gwlarson 3.7 add_tri(qtptr,fptr,t_id,del_set)
385 gwlarson 3.5 QUADTREE *qtptr;
386     int *fptr;
387     int t_id;
388 gwlarson 3.7 OBJECT *del_set;
389 gwlarson 3.5 {
390    
391 gwlarson 3.7 OBJECT *optr,*tptr;
392     OBJECT t_set[QT_MAXSET +1],r_set[QT_MAXSET +1];
393     int i,id,found;
394 gwlarson 3.5 #ifdef DEBUG_TEST_DRIVER
395     Pick_tri = t_id;
396     Picking = TRUE;
397     #endif
398     if(QT_IS_EMPTY(*qtptr))
399     {
400     *qtptr = qtaddelem(*qtptr,t_id);
401     if(!QT_FLAG_FILL_TRI(*fptr))
402     (*fptr)++;
403     }
404     else
405     {
406 gwlarson 3.7 optr = qtqueryset(*qtptr);
407     if(del_set)
408     {
409     setintersect(r_set,del_set,optr);
410     if(QT_SET_CNT(r_set) > 0)
411     {
412     qtgetset(t_set,*qtptr);
413     optr = QT_SET_PTR(r_set);
414     for(i = QT_SET_CNT(r_set); i > 0; i--)
415     {
416     id = QT_SET_NEXT_ELEM(optr);
417     deletelem(t_set,id);
418     }
419     qtfreeleaf(*qtptr);
420     *qtptr = qtnewleaf(t_set);
421     optr = t_set;
422     }
423     }
424     if(!inset(optr,t_id))
425 gwlarson 3.5 {
426 gwlarson 3.7 if(QT_SET_CNT(optr) < QT_MAXSET)
427     {
428     if(QT_SET_CNT(optr) >= QT_SET_THRESHOLD)
429     (*fptr) |= QT_EXPAND;
430     if(!QT_FLAG_FILL_TRI(*fptr))
431     (*fptr)++;
432     *qtptr = qtaddelem(*qtptr,t_id);
433     }
434     else
435     {
436 gwlarson 3.5 #ifdef DEBUG_TESTDRIVER
437 gwlarson 3.7 eputs("add_tri():exceeded set size\n");
438 gwlarson 3.5 #endif
439 gwlarson 3.7 return(FALSE);
440     }
441     }
442 gwlarson 3.5 }
443     return(TRUE);
444     }
445    
446    
447 gwlarson 3.7 smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id,del_set)
448 gwlarson 3.1 SM *sm;
449     int t_id;
450 gwlarson 3.7 int v0_id,v1_id,v2_id;
451     OBJECT *del_set;
452 gwlarson 3.1 {
453     STREE *st;
454 gwlarson 3.5 FVECT v0,v1,v2;
455 gwlarson 3.1
456     st = SM_LOCATOR(sm);
457    
458 gwlarson 3.5 VSUB(v0,SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm));
459     VSUB(v1,SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm));
460     VSUB(v2,SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm));
461 gwlarson 3.1
462 gwlarson 3.7 qtClearAllFlags();
463    
464     stApply_to_tri(st,v0,v1,v2,add_tri,add_tri_expand,t_id,del_set);
465 gwlarson 3.1
466     }
467    
468     /* Add a triangle to the base array with vertices v1-v2-v3 */
469     int
470     smAdd_tri(sm, v0_id,v1_id,v2_id,tptr)
471     SM *sm;
472     int v0_id,v1_id,v2_id;
473     TRI **tptr;
474     {
475     int t_id;
476     TRI *t;
477    
478    
479     if(SM_TRI_CNT(sm)+1 > SM_MAX_TRIS(sm))
480     error(SYSTEM,"smAdd_tri():Too many triangles");
481    
482     /* Get the id for the next available triangle */
483     SM_FREE_TRI_ID(sm,t_id);
484     if(t_id == -1)
485     return(t_id);
486    
487     t = SM_NTH_TRI(sm,t_id);
488     T_CLEAR_NBRS(t);
489    
490     if(SM_BASE_ID(sm,v0_id) || SM_BASE_ID(sm,v1_id) || SM_BASE_ID(sm,v2_id))
491     {
492     smClear_tri_flags(sm,t_id);
493     SM_SET_NTH_T_BASE(sm,t_id);
494     }
495     else
496     {
497     SM_CLEAR_NTH_T_BASE(sm,t_id);
498     SM_SET_NTH_T_ACTIVE(sm,t_id);
499     SM_SET_NTH_T_LRU(sm,t_id);
500     SM_SET_NTH_T_NEW(sm,t_id);
501     SM_NUM_TRIS(sm)++;
502     smNew_tri_cnt++;
503     }
504     /* set the triangle vertex ids */
505     T_NTH_V(t,0) = v0_id;
506     T_NTH_V(t,1) = v1_id;
507     T_NTH_V(t,2) = v2_id;
508    
509     SM_NTH_VERT(sm,v0_id) = t_id;
510     SM_NTH_VERT(sm,v1_id) = t_id;
511     SM_NTH_VERT(sm,v2_id) = t_id;
512    
513     if(t)
514     *tptr = t;
515     /* return initialized triangle */
516     return(t_id);
517     }
518    
519     int
520     smClosest_vertex_in_tri(sm,v0_id,v1_id,v2_id,p,eps)
521     SM *sm;
522     int v0_id,v1_id,v2_id;
523     FVECT p;
524     double eps;
525     {
526     FVECT v;
527     double d,d0,d1,d2;
528     int closest = -1;
529    
530     if(v0_id != -1)
531     {
532     smDir(sm,v,v0_id);
533     d0 = DIST(p,v);
534     if(eps < 0 || d0 < eps)
535     {
536     closest = v0_id;
537     d = d0;
538     }
539     }
540     if(v1_id != -1)
541     {
542     smDir(sm,v,v1_id);
543     d1 = DIST(p,v);
544     if(closest== -1)
545     {
546     if(eps < 0 || d1 < eps)
547     {
548     closest = v1_id;
549     d = d1;
550     }
551     }
552     else
553 gwlarson 3.5 if(d1 < d0)
554 gwlarson 3.1 {
555     if((eps < 0) || d1 < eps)
556     {
557     closest = v1_id;
558     d = d1;
559     }
560     }
561 gwlarson 3.5 }
562 gwlarson 3.1 if(v2_id != -1)
563     {
564     smDir(sm,v,v2_id);
565     d2 = DIST(p,v);
566     if((eps < 0) || d2 < eps)
567 gwlarson 3.5 if(closest == -1 ||(d2 < d))
568 gwlarson 3.1 return(v2_id);
569     }
570     return(closest);
571     }
572    
573    
574     int
575     smClosest_vertex_in_w_tri(sm,v0_id,v1_id,v2_id,p)
576     SM *sm;
577     int v0_id,v1_id,v2_id;
578     FVECT p;
579     {
580     FVECT v;
581     double d,d0,d1,d2;
582     int closest;
583    
584     VCOPY(v,SM_NTH_WV(sm,v0_id));
585     d = d0 = DIST(p,v);
586     closest = v0_id;
587    
588     VCOPY(v,SM_NTH_WV(sm,v1_id));
589     d1 = DIST(p,v);
590 gwlarson 3.5 if(d1 < d0)
591 gwlarson 3.1 {
592     closest = v1_id;
593     d = d1;
594     }
595     VCOPY(v,SM_NTH_WV(sm,v2_id));
596     d2 = DIST(p,v);
597     if(d2 < d)
598     return(v2_id);
599     else
600     return(closest);
601     }
602    
603     void
604 gwlarson 3.7 smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add_ptr,del_set)
605 gwlarson 3.1 SM *sm;
606     int t_id,t1_id;
607     int e,e1;
608 gwlarson 3.5 int *tn_id,*tn1_id;
609 gwlarson 3.7 LIST **add_ptr;
610     OBJECT *del_set;
611 gwlarson 3.1
612     {
613     TRI *t,*t1;
614     TRI *ta,*tb;
615     int verts[3],enext,eprev,e1next,e1prev;
616     TRI *n;
617     FVECT p1,p2,p3;
618     int ta_id,tb_id;
619     /* swap diagonal (e relative to t, and e1 relative to t1)
620     defined by quadrilateral
621     formed by t,t1- swap for the opposite diagonal
622     */
623     t = SM_NTH_TRI(sm,t_id);
624     t1 = SM_NTH_TRI(sm,t1_id);
625     enext = (e+1)%3;
626     eprev = (e+2)%3;
627     e1next = (e1+1)%3;
628     e1prev = (e1+2)%3;
629     verts[e] = T_NTH_V(t,e);
630     verts[enext] = T_NTH_V(t1,e1prev);
631     verts[eprev] = T_NTH_V(t,eprev);
632     ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&ta);
633 gwlarson 3.7 *add_ptr = push_data(*add_ptr,ta_id);
634 gwlarson 3.1 verts[e1] = T_NTH_V(t1,e1);
635     verts[e1next] = T_NTH_V(t,eprev);
636     verts[e1prev] = T_NTH_V(t1,e1prev);
637     tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&tb);
638 gwlarson 3.7 *add_ptr = push_data(*add_ptr,tb_id);
639 gwlarson 3.3
640 gwlarson 3.1 /* set the neighbors */
641     T_NTH_NBR(ta,e) = T_NTH_NBR(t1,e1next);
642     T_NTH_NBR(tb,e1) = T_NTH_NBR(t,enext);
643     T_NTH_NBR(ta,enext) = tb_id;
644     T_NTH_NBR(tb,e1next) = ta_id;
645     T_NTH_NBR(ta,eprev) = T_NTH_NBR(t,eprev);
646     T_NTH_NBR(tb,e1prev) = T_NTH_NBR(t1,e1prev);
647    
648     /* Reset neighbor pointers of original neighbors */
649     n = SM_NTH_TRI(sm,T_NTH_NBR(t,enext));
650     T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = tb_id;
651     n = SM_NTH_TRI(sm,T_NTH_NBR(t,eprev));
652     T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = ta_id;
653    
654     n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1next));
655     T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = ta_id;
656     n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1prev));
657     T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = tb_id;
658    
659     /* Delete two parent triangles */
660 gwlarson 3.7 if(remove_from_list(t_id,add_ptr))
661     smDelete_tri(sm,t_id);
662     else
663     insertelem(del_set,t_id);
664 gwlarson 3.5
665 gwlarson 3.7 if(remove_from_list(t1_id,add_ptr))
666     smDelete_tri(sm,t1_id);
667     else
668     insertelem(del_set,t1_id);
669    
670 gwlarson 3.1 *tn_id = ta_id;
671     *tn1_id = tb_id;
672     }
673    
674 gwlarson 3.7 smUpdate_locator(sm,add_list,del_set)
675 gwlarson 3.3 SM *sm;
676 gwlarson 3.7 LIST *add_list;
677     OBJECT *del_set;
678 gwlarson 3.3 {
679 gwlarson 3.7 int t_id,i;
680 gwlarson 3.3 TRI *t;
681 gwlarson 3.7 OBJECT *optr;
682    
683 gwlarson 3.3 while(add_list)
684     {
685     t_id = pop_list(&add_list);
686 gwlarson 3.6 t = SM_NTH_TRI(sm,t_id);
687 gwlarson 3.7 smLocator_add_tri(sm,t_id,T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2),del_set);
688 gwlarson 3.3 }
689 gwlarson 3.7
690     optr = QT_SET_PTR(del_set);
691     for(i = QT_SET_CNT(del_set); i > 0; i--)
692 gwlarson 3.3 {
693 gwlarson 3.7 t_id = QT_SET_NEXT_ELEM(optr);
694     smDelete_tri(sm,t_id);
695 gwlarson 3.3 }
696     }
697 gwlarson 3.1 /* MUST add check for constrained edges */
698 gwlarson 3.3 int
699 gwlarson 3.7 smFix_tris(sm,id,tlist,add_list,del_set)
700 gwlarson 3.1 SM *sm;
701     int id;
702     LIST *tlist;
703 gwlarson 3.7 LIST *add_list;
704     OBJECT *del_set;
705 gwlarson 3.1 {
706     TRI *t,*t_opp;
707 gwlarson 3.3 FVECT p,p1,p2,p3;
708     int e,e1,swapped = 0;
709 gwlarson 3.1 int t_id,t_opp_id;
710 gwlarson 3.3
711    
712     VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
713 gwlarson 3.1 while(tlist)
714     {
715 gwlarson 3.3 t_id = pop_list(&tlist);
716 gwlarson 3.1 t = SM_NTH_TRI(sm,t_id);
717     e = (T_WHICH_V(t,id)+1)%3;
718     t_opp_id = T_NTH_NBR(t,e);
719     t_opp = SM_NTH_TRI(sm,t_opp_id);
720 gwlarson 3.6 /*
721     VSUB(p1,SM_T_NTH_WV(sm,t_opp,0),SM_VIEW_CENTER(sm));
722     VSUB(p2,SM_T_NTH_WV(sm,t_opp,1),SM_VIEW_CENTER(sm));
723     VSUB(p3,SM_T_NTH_WV(sm,t_opp,2),SM_VIEW_CENTER(sm));
724     */
725 gwlarson 3.7 smDir_in_cone(sm,p1,T_NTH_V(t_opp,0));
726     smDir_in_cone(sm,p2,T_NTH_V(t_opp,1));
727     smDir_in_cone(sm,p3,T_NTH_V(t_opp,2));
728 gwlarson 3.1 if(point_in_cone(p,p1,p2,p3))
729     {
730     swapped = 1;
731     e1 = T_NTH_NBR_PTR(t_id,t_opp);
732     /* check list for t_opp and Remove if there */
733     remove_from_list(t_opp_id,&tlist);
734 gwlarson 3.3 smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id,
735 gwlarson 3.7 &add_list,del_set);
736 gwlarson 3.1 tlist = push_data(tlist,t_id);
737     tlist = push_data(tlist,t_opp_id);
738     }
739     }
740 gwlarson 3.7 smUpdate_locator(sm,add_list,del_set);
741 gwlarson 3.1 return(swapped);
742     }
743    
744     /* Give the vertex "id" and a triangle "t" that it belongs to- return the
745     next nbr in a counter clockwise order about vertex "id"
746     */
747     int
748     smTri_next_ccw_nbr(sm,t,id)
749     SM *sm;
750     TRI *t;
751     int id;
752     {
753     int t_id;
754     int tri;
755    
756     /* Want the edge for which "id" is the destination */
757     t_id = (T_WHICH_V(t,id)+ 2)% 3;
758     tri = T_NTH_NBR(t,t_id);
759     return(tri);
760     }
761    
762     void
763     smReplace_point(sm,tri,id,nid)
764     SM *sm;
765     TRI *tri;
766     int id,nid;
767     {
768     TRI *t;
769     int t_id;
770    
771     T_NTH_V(tri,T_WHICH_V(tri,id)) = nid;
772    
773 gwlarson 3.5 t_id = smTri_next_ccw_nbr(sm,tri,nid);
774     while((t = SM_NTH_TRI(sm,t_id)) != tri)
775 gwlarson 3.1 {
776     T_NTH_V(t,T_WHICH_V(t,id)) = nid;
777     t_id = smTri_next_ccw_nbr(sm,t,nid);
778     }
779     }
780    
781    
782     smClear_tri_flags(sm,id)
783     SM *sm;
784     int id;
785     {
786     int i;
787    
788     for(i=0; i < T_FLAGS; i++)
789     SM_CLEAR_NTH_T_FLAG(sm,id,i);
790    
791     }
792    
793     /* Locate the point-id in the point location structure: */
794     int
795     smReplace_vertex(sm,c,dir,p,tri_id,snew_id,type,which)
796     SM *sm;
797     COLR c;
798     FVECT dir,p;
799     int tri_id,snew_id;
800 gwlarson 3.5 int type,which;
801 gwlarson 3.1 {
802     int n_id,s_id;
803     TRI *tri;
804    
805     tri = SM_NTH_TRI(sm,tri_id);
806     /* Get the sample that corresponds to the "which" vertex of "tri" */
807     /* NEED: have re-init that sets clock flag */
808     /* If this is a base-sample: create a new sample and replace
809     all references to the base sample with references to the
810     new sample
811     */
812     s_id = T_NTH_V(tri,which);
813     if(SM_BASE_ID(sm,s_id))
814     {
815     if(snew_id != -1)
816     n_id = smAdd_sample_point(sm,c,dir,p);
817     else
818     n_id = snew_id;
819     smReplace_point(sm,tri,s_id,n_id);
820     s_id = n_id;
821     }
822     else /* If the sample exists, reset the values */
823     /* NOTE: This test was based on the SPHERICAL coordinates
824     of the point: If we are doing a multiple-sample-per
825     SPHERICAL pixel: we will want to test for equality-
826     and do other processing: for now: SINGLE SAMPLE PER
827     PIXEL
828     */
829     /* NOTE: snew_id needs to be marked as invalid?*/
830     if(snew_id == -1)
831     smInit_sample(sm,s_id,c,dir,p);
832     else
833     smReset_sample(sm,s_id,snew_id);
834     return(s_id);
835     }
836    
837    
838     /* Locate the point-id in the point location structure: */
839     int
840     smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id)
841     SM *sm;
842     COLR c;
843     FVECT dir,p;
844     int s_id,tri_id;
845     {
846     TRI *tri,*t0,*t1,*t2,*nbr;
847     int v0_id,v1_id,v2_id,n_id;
848     int t0_id,t1_id,t2_id;
849 gwlarson 3.7 LIST *tlist,*add_list;
850     OBJECT del_set[QT_MAXSET+1];
851 gwlarson 3.1 FVECT npt;
852    
853 gwlarson 3.7 add_list = NULL;
854     QT_CLEAR_SET(del_set);
855 gwlarson 3.1 if(s_id == SM_INVALID)
856     s_id = smAdd_sample_point(sm,c,dir,p);
857    
858     tri = SM_NTH_TRI(sm,tri_id);
859     v0_id = T_NTH_V(tri,0);
860     v1_id = T_NTH_V(tri,1);
861     v2_id = T_NTH_V(tri,2);
862    
863     n_id = -1;
864     if(SM_BASE_ID(sm,v0_id)||SM_BASE_ID(sm,v1_id)||SM_BASE_ID(sm,v2_id))
865     {
866     smDir(sm,npt,s_id);
867     /* Change to an add and delete */
868     t0_id = (SM_BASE_ID(sm,v0_id))?v0_id:-1;
869     t1_id = (SM_BASE_ID(sm,v1_id))?v1_id:-1;
870     t2_id = (SM_BASE_ID(sm,v2_id))?v2_id:-1;
871     n_id = smClosest_vertex_in_tri(sm,t0_id,t1_id,t2_id,npt,P_REPLACE_EPS);
872     }
873     t0_id = smAdd_tri(sm,s_id,v0_id,v1_id,&t0);
874 gwlarson 3.3 /* Add triangle to the locator */
875 gwlarson 3.6
876     add_list = push_data(add_list,t0_id);
877 gwlarson 3.3
878 gwlarson 3.1 t1_id = smAdd_tri(sm,s_id,v1_id,v2_id,&t1);
879 gwlarson 3.6 add_list = push_data(add_list,t1_id);
880    
881 gwlarson 3.1 t2_id = smAdd_tri(sm,s_id,v2_id,v0_id,&t2);
882 gwlarson 3.6 add_list = push_data(add_list,t2_id);
883 gwlarson 3.3
884 gwlarson 3.1 /* Set the neighbor pointers for the new tris */
885     T_NTH_NBR(t0,0) = t2_id;
886     T_NTH_NBR(t0,1) = T_NTH_NBR(tri,0);
887     T_NTH_NBR(t0,2) = t1_id;
888     T_NTH_NBR(t1,0) = t0_id;
889     T_NTH_NBR(t1,1) = T_NTH_NBR(tri,1);
890     T_NTH_NBR(t1,2) = t2_id;
891     T_NTH_NBR(t2,0) = t1_id;
892     T_NTH_NBR(t2,1) = T_NTH_NBR(tri,2);
893     T_NTH_NBR(t2,2) = t0_id;
894    
895     /* Reset the neigbor pointers for the neighbors of the original */
896     nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,0));
897     T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t0_id;
898     nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,1));
899     T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t1_id;
900     nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,2));
901     T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t2_id;
902    
903 gwlarson 3.7 insertelem(del_set,tri_id);
904 gwlarson 3.6
905 gwlarson 3.1 /* Fix up the new triangles*/
906     tlist = push_data(NULL,t0_id);
907     tlist = push_data(tlist,t1_id);
908     tlist = push_data(tlist,t2_id);
909    
910 gwlarson 3.7 smFix_tris(sm,s_id,tlist,add_list,del_set);
911 gwlarson 3.1
912     if(n_id != -1)
913     smDelete_point(sm,n_id);
914    
915     return(s_id);
916     }
917    
918    
919     int
920 gwlarson 3.5 smPointLocate(sm,pt,norm)
921 gwlarson 3.1 SM *sm;
922     FVECT pt;
923 gwlarson 3.5 int norm;
924 gwlarson 3.1 {
925     STREE *st;
926     int tri;
927     FVECT npt;
928    
929     st = SM_LOCATOR(sm);
930     if(norm)
931     {
932 gwlarson 3.5 VSUB(npt,pt,SM_VIEW_CENTER(sm));
933     tri = stPoint_locate(st,npt);
934 gwlarson 3.1 }
935     else
936 gwlarson 3.5 tri = stPoint_locate(st,pt);
937 gwlarson 3.1 return(tri);
938     }
939    
940     QUADTREE
941 gwlarson 3.4 smPointLocateCell(sm,pt,norm,v0,v1,v2)
942 gwlarson 3.1 SM *sm;
943 gwlarson 3.2 FVECT pt;
944 gwlarson 3.5 int norm;
945 gwlarson 3.4 FVECT v0,v1,v2;
946 gwlarson 3.1 {
947     STREE *st;
948 gwlarson 3.4 QUADTREE *qtptr;
949 gwlarson 3.1 FVECT npt;
950    
951     st = SM_LOCATOR(sm);
952     if(norm)
953     {
954 gwlarson 3.5 VSUB(npt,pt,SM_VIEW_CENTER(sm));
955 gwlarson 3.1
956 gwlarson 3.4 qtptr = stPoint_locate_cell(st,npt,v0,v1,v2);
957 gwlarson 3.1 }
958     else
959 gwlarson 3.4 qtptr = stPoint_locate_cell(st,pt,v0,v1,v2);
960 gwlarson 3.1
961 gwlarson 3.4 if(qtptr)
962     return(*qtptr);
963     else
964     return(EMPTY);
965 gwlarson 3.1 }
966    
967     int
968     smAdd_sample_to_mesh(sm,c,dir,pt,s_id)
969     SM *sm;
970     COLR c;
971     FVECT dir,pt;
972     int s_id;
973     {
974     int t_id;
975     double d;
976     FVECT p;
977    
978     /* If new, foreground pt */
979     if(pt)
980     {
981     /* NOTE: This should be elsewhere! */
982     d = DIST(pt,SM_VIEW_CENTER(smMesh));
983     smDist_sum += 1.0/d;
984     /************************************/
985 gwlarson 3.5 t_id = smPointLocate(smMesh,pt,TRUE);
986     if(t_id >= 0)
987 gwlarson 3.1 s_id = smInsert_point_in_tri(smMesh,c,dir,pt,s_id,t_id);
988     #ifdef DEBUG
989     else
990 gwlarson 3.5 {
991     c[0] = 255;c[1]=0;c[2]=0;
992     s_id = smAdd_sample_point(sm,c,dir,pt);
993     eputs("smAdd_sample_to_mesh(): not found fg\n");
994     }
995 gwlarson 3.1 #endif
996     }
997     else if(s_id != -1)
998     {
999     VCOPY(p,SM_NTH_WV(sm,s_id));
1000     if(SM_NTH_W_DIR(sm,s_id) != -1)
1001     {
1002     /* NOTE: This should be elsewhere! */
1003     d = DIST(p,SM_VIEW_CENTER(smMesh));
1004     smDist_sum += 1.0/d;
1005     /************************************/
1006     }
1007 gwlarson 3.5 t_id = smPointLocate(smMesh,p,TRUE);
1008     if(t_id != -1)
1009 gwlarson 3.1 s_id = smInsert_point_in_tri(smMesh,c,dir,p,s_id,t_id);
1010     #ifdef DEBUG
1011     else
1012 gwlarson 3.5 eputs("smAdd_sample_to_mesh():not found reinsert\n");
1013 gwlarson 3.1 #endif
1014     }
1015     /* Is a BG(sky point) */
1016     else
1017     {
1018 gwlarson 3.5 t_id = smPointLocate(smMesh,dir,FALSE);
1019     if(t_id != -1)
1020 gwlarson 3.1 s_id = smInsert_point_in_tri(smMesh,c,dir,NULL,s_id,t_id);
1021 gwlarson 3.5
1022 gwlarson 3.1 #ifdef DEBUG
1023     else
1024 gwlarson 3.5 eputs("smAdd_sample_to_mesh(): not found bg\n");
1025 gwlarson 3.1 #endif
1026     }
1027     return(s_id);
1028     }
1029    
1030     /*
1031     * int
1032     * smNewSamp(c, dir, p) : register new sample point and return index
1033     * COLR c; : pixel color (RGBE)
1034     * FVECT dir; : ray direction vector
1035     * FVECT p; : world intersection point
1036     *
1037     * Add new sample point to data structures, removing old values as necessary.
1038     * New sample representation will be output in next call to smUpdate().
1039     * If the point is a sky point: then v=NULL
1040     */
1041     int
1042     smNewSamp(c,dir,p)
1043     COLR c;
1044     FVECT dir;
1045     FVECT p;
1046    
1047     {
1048     int s_id;
1049 gwlarson 3.5 int debug=0;
1050 gwlarson 3.1
1051     /* First check if this the first sample: if so initialize mesh */
1052     if(SM_NUM_SAMP(smMesh) == 0)
1053     smInit_mesh(smMesh,odev.v.vp);
1054 gwlarson 3.5 if(!debug)
1055     s_id = smAdd_sample_to_mesh(smMesh,c,dir,p,-1);
1056 gwlarson 3.1 return(s_id);
1057    
1058     }
1059     /*
1060     * int
1061     * smFindsamp(orig, dir): intersect ray with 3D rep. and find closest sample
1062     * FVECT orig, dir;
1063     *
1064     * Find the closest sample to the given ray. Return -1 on failure.
1065     */
1066    
1067     /*
1068     * smClean() : display has been wiped clean
1069     *
1070     * Called after display has been effectively cleared, meaning that all
1071     * geometry must be resent down the pipeline in the next call to smUpdate().
1072     */
1073    
1074    
1075     /*
1076     * smUpdate(vp, qua) : update OpenGL output geometry for view vp
1077     * VIEW *vp; : desired view
1078     * int qua; : quality level (percentage on linear time scale)
1079     *
1080     * Draw new geometric representation using OpenGL calls. Assume that the
1081     * view has already been set up and the correct frame buffer has been
1082     * selected for drawing. The quality level is on a linear scale, where 100%
1083     * is full (final) quality. It is not necessary to redraw geometry that has
1084     * been output since the last call to smClean().
1085     */
1086    
1087    
1088     int
1089     smClear_vert(sm,id)
1090     SM *sm;
1091     int id;
1092     {
1093     if(SM_INVALID_POINT_ID(sm,id))
1094     return(FALSE);
1095    
1096     SM_NTH_VERT(sm,id) = SM_INVALID;
1097    
1098     return(TRUE);
1099     }
1100    
1101     int
1102     smAdd_base_vertex(sm,v,d)
1103     SM *sm;
1104     FVECT v,d;
1105     {
1106     int id;
1107    
1108     /* First add coordinate to the sample array */
1109     id = smAdd_aux_point(sm,v,d);
1110     if(id == -1)
1111     return(SM_INVALID);
1112     /* Initialize triangle pointer to -1 */
1113     smClear_vert(sm,id);
1114     return(id);
1115     }
1116    
1117    
1118    
1119     /* Initialize a the point location DAG based on a 6 triangle tesselation
1120     of the unit sphere centered on the view center. The DAG structure
1121     contains 6 roots: one for each initial base triangle
1122     */
1123    
1124     int
1125     smCreate_base_mesh(sm,type)
1126     SM *sm;
1127     int type;
1128     {
1129 gwlarson 3.5 int i,id,tri_id,nbr_id;
1130 gwlarson 3.1 int p[4],ids[4];
1131     int v0_id,v1_id,v2_id;
1132     TRI *tris[4];
1133     FVECT d,pt,cntr;
1134    
1135     /* First insert the base vertices into the sample point array */
1136    
1137     for(i=0; i < 4; i++)
1138     {
1139 gwlarson 3.5 VCOPY(cntr,stDefault_base[i]);
1140     cntr[0] += .01;
1141     cntr[1] += .02;
1142     cntr[2] += .03;
1143 gwlarson 3.6 VADD(cntr,cntr,SM_VIEW_CENTER(sm));
1144 gwlarson 3.7 d[0] = -1;
1145 gwlarson 3.6 id = smAdd_base_vertex(sm,cntr,d);
1146 gwlarson 3.1 /* test to make sure vertex allocated */
1147     if(id != -1)
1148     p[i] = id;
1149     else
1150     return(0);
1151     }
1152     /* Create the base triangles */
1153     for(i=0;i < 4; i++)
1154     {
1155     v0_id = p[stTri_verts[i][0]];
1156     v1_id = p[stTri_verts[i][1]];
1157     v2_id = p[stTri_verts[i][2]];
1158     if((ids[i] = smAdd_tri(sm, v0_id,v1_id,v2_id,&(tris[i])))== -1)
1159     return(0);
1160 gwlarson 3.7 smLocator_add_tri(sm,ids[i],v0_id,v1_id,v2_id,NULL);
1161 gwlarson 3.1 }
1162     /* Set neighbors */
1163    
1164 gwlarson 3.5 for(tri_id=0;tri_id < 4; tri_id++)
1165     for(nbr_id=0; nbr_id < 3; nbr_id++)
1166     T_NTH_NBR(tris[tri_id],nbr_id) = smBase_nbrs[tri_id][nbr_id];
1167 gwlarson 3.1
1168     return(1);
1169    
1170     }
1171    
1172    
1173     int
1174     smNext_tri_flag_set(sm,i,which,b)
1175     SM *sm;
1176     int i,which;
1177 gwlarson 3.5 int b;
1178 gwlarson 3.1 {
1179    
1180     for(; i < SM_TRI_CNT(sm);i++)
1181     {
1182    
1183 gwlarson 3.5 if(!SM_IS_NTH_T_FLAG(sm,i,which))
1184     continue;
1185 gwlarson 3.1 if(!b)
1186     break;
1187     if((b==1) && !SM_BG_TRI(sm,i))
1188     break;
1189     if((b==2) && SM_BG_TRI(sm,i))
1190     break;
1191     }
1192    
1193     return(i);
1194     }
1195    
1196    
1197     int
1198     smNext_valid_tri(sm,i)
1199     SM *sm;
1200     int i;
1201     {
1202    
1203     while( i < SM_TRI_CNT(sm) && !T_IS_VALID(SM_NTH_TRI(sm,i)))
1204     i++;
1205    
1206     return(i);
1207     }
1208    
1209    
1210    
1211 gwlarson 3.5 qtTri_from_id(t_id,v0,v1,v2,n0,n1,n2,v0_idp,v1_idp,v2_idp)
1212 gwlarson 3.1 int t_id;
1213     FVECT v0,v1,v2;
1214 gwlarson 3.5 FVECT n0,n1,n2;
1215     int *v0_idp,*v1_idp,*v2_idp;
1216 gwlarson 3.1 {
1217     TRI *t;
1218     int v0_id,v1_id,v2_id;
1219    
1220     t = SM_NTH_TRI(smMesh,t_id);
1221     v0_id = T_NTH_V(t,0);
1222     v1_id = T_NTH_V(t,1);
1223     v2_id = T_NTH_V(t,2);
1224    
1225 gwlarson 3.5 if(v0)
1226     {
1227 gwlarson 3.7 VSUB(v0,SM_NTH_WV(smMesh,v0_id),SM_VIEW_CENTER(smMesh));
1228     VSUB(v1,SM_NTH_WV(smMesh,v1_id),SM_VIEW_CENTER(smMesh));
1229     VSUB(v2,SM_NTH_WV(smMesh,v2_id),SM_VIEW_CENTER(smMesh));
1230 gwlarson 3.5 }
1231     if(n0)
1232     {
1233     smDir(smMesh,n0,v0_id);
1234     smDir(smMesh,n1,v1_id);
1235     smDir(smMesh,n2,v2_id);
1236 gwlarson 3.1
1237 gwlarson 3.5 }
1238     if(v0_idp)
1239     {
1240     *v0_idp = v0_id;
1241     *v1_idp = v1_id;
1242     *v2_idp = v2_id;
1243     }
1244 gwlarson 3.1 }
1245    
1246    
1247     /*
1248     * int
1249     * smFindSamp(FVECT orig, FVECT dir)
1250     *
1251     * Find the closest sample to the given ray. Returns sample id, -1 on failure.
1252     * "dir" is assumed to be normalized
1253     */
1254    
1255    
1256    
1257 gwlarson 3.5 smRebuild_mesh(sm,vp)
1258 gwlarson 3.1 SM *sm;
1259 gwlarson 3.5 FVECT vp;
1260 gwlarson 3.1 {
1261     int i;
1262     FVECT dir;
1263     COLR c;
1264     FVECT p,ov;
1265    
1266     /* Clear the mesh- and rebuild using the current sample array */
1267    
1268 gwlarson 3.5 VSUB(ov,vp,SM_VIEW_CENTER(sm));
1269     smInit_mesh(sm,vp);
1270 gwlarson 3.1
1271     SM_FOR_ALL_SAMPLES(sm,i)
1272     {
1273     if(SM_NTH_W_DIR(sm,i)==-1)
1274     VADD(SM_NTH_WV(sm,i),SM_NTH_WV(sm,i),ov);
1275     smAdd_sample_to_mesh(sm,NULL,NULL,NULL,i);
1276     }
1277     }
1278 gwlarson 3.5
1279     int
1280     intersect_tri_set(t_set,orig,dir,pt)
1281     OBJECT *t_set;
1282     FVECT orig,dir,pt;
1283     {
1284     OBJECT *optr;
1285     int i,t_id,id;
1286     int pid0,pid1,pid2;
1287     FVECT p0,p1,p2,p;
1288     TRI *t;
1289    
1290     optr = QT_SET_PTR(t_set);
1291     for(i = QT_SET_CNT(t_set); i > 0; i--)
1292     {
1293     t_id = QT_SET_NEXT_ELEM(optr);
1294    
1295     t = SM_NTH_TRI(smMesh,t_id);
1296     pid0 = T_NTH_V(t,0);
1297     pid1 = T_NTH_V(t,1);
1298     pid2 = T_NTH_V(t,2);
1299     VCOPY(p0,SM_NTH_WV(smMesh,pid0));
1300     VCOPY(p1,SM_NTH_WV(smMesh,pid1));
1301     VCOPY(p2,SM_NTH_WV(smMesh,pid2));
1302     if(ray_intersect_tri(orig,dir,p0,p1,p2,p))
1303     {
1304     id = closest_point_in_tri(p0,p1,p2,p,pid0,pid1,pid2);
1305    
1306     if(pt)
1307     VCOPY(pt,p);
1308     #ifdef DEBUG_TEST_DRIVER
1309     Pick_tri = t_id;
1310     Pick_samp = id;
1311     VCOPY(Pick_point[0],p);
1312     #endif
1313     return(id);
1314     }
1315     }
1316     return(-1);
1317     }
1318    
1319     int
1320     ray_trace_check_set(qtptr,orig,dir,tptr,os)
1321     QUADTREE *qtptr;
1322     FVECT orig,dir;
1323     int *tptr;
1324     OBJECT *os;
1325     {
1326     OBJECT tset[QT_MAXSET+1];
1327     double dt,t;
1328     int found;
1329     FVECT o;
1330    
1331    
1332     if(!QT_IS_EMPTY(*qtptr))
1333     {
1334     VADD(o,orig,SM_VIEW_CENTER(smMesh));
1335     qtgetset(tset,*qtptr);
1336     /* Check triangles in set against those seen so far(os):only
1337     check new triangles for intersection (t_set')
1338     */
1339     check_set(tset,os);
1340     if((found = intersect_tri_set(tset,o,dir,NULL))!= -1)
1341     {
1342     *tptr = found;
1343     return(QT_DONE);
1344     }
1345     }
1346     return(FALSE);
1347     }
1348    
1349     int
1350 gwlarson 3.6 smFindSamp(orig,dir)
1351 gwlarson 3.5 FVECT orig,dir;
1352     {
1353     FVECT b,p,o;
1354     OBJECT *ts;
1355     QUADTREE qt;
1356     int s_id;
1357     double d;
1358    
1359     /* r is the normalized vector from the view center to the current
1360     * ray point ( starting with "orig"). Find the cell that r falls in,
1361     * and test the ray against all triangles stored in the cell. If
1362     * the test fails, trace the projection of the ray across to the
1363     * next cell it intersects: iterate until either an intersection
1364     * is found, or the projection ray is // to the direction. The sample
1365     * corresponding to the triangle vertex closest to the intersection
1366     * point is returned.
1367     */
1368    
1369     /* First test if "orig" coincides with the View_center or if "dir" is
1370     parallel to r formed by projecting "orig" on the sphere. In
1371     either case, do a single test against the cell containing the
1372     intersection of "dir" and the sphere
1373     */
1374     /* orig will be updated-so preserve original value */
1375     if(!smMesh)
1376     return;
1377     point_on_sphere(b,orig,SM_VIEW_CENTER(smMesh));
1378     d = -DOT(b,dir);
1379     if(EQUAL_VEC3(orig,SM_VIEW_CENTER(smMesh)) || EQUAL(fabs(d),1.0))
1380     {
1381     qt = smPointLocateCell(smMesh,dir,FALSE,NULL,NULL,NULL);
1382     /* Test triangles in the set for intersection with Ray:returns
1383     first found
1384     */
1385     ts = qtqueryset(qt);
1386     s_id = intersect_tri_set(ts,orig,dir,p);
1387     #ifdef DEBUG_TEST_DRIVER
1388     VCOPY(Pick_point[0],p);
1389     #endif
1390     }
1391     else
1392     {
1393     OBJECT t_set[QT_MAXCSET+1];
1394     /* Test each of the root triangles against point id */
1395     QT_CLEAR_SET(t_set);
1396     VSUB(o,orig,SM_VIEW_CENTER(smMesh));
1397     ST_CLEAR_FLAGS(SM_LOCATOR(smMesh));
1398     s_id=stTrace_ray(SM_LOCATOR(smMesh),o,dir,ray_trace_check_set,&s_id,t_set);
1399     }
1400     return(s_id);
1401     }
1402    
1403    
1404    
1405    
1406    
1407    
1408    
1409    
1410    
1411    
1412 gwlarson 3.1
1413