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