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