8 |
|
* sm.c |
9 |
|
*/ |
10 |
|
#include "standard.h" |
11 |
< |
|
12 |
< |
#include "object.h" |
13 |
< |
|
11 |
> |
#include "sm_flag.h" |
12 |
|
#include "sm_list.h" |
13 |
|
#include "sm_geom.h" |
14 |
+ |
#include "sm_qtree.h" |
15 |
+ |
#include "sm_stree.h" |
16 |
|
#include "sm.h" |
17 |
|
|
18 |
|
|
19 |
|
SM *smMesh = NULL; |
20 |
|
double smDist_sum=0; |
21 |
|
int smNew_tri_cnt=0; |
22 |
+ |
double smMinSampDiff = 1.7e-3; /* min edge length in radians */ |
23 |
|
|
24 |
+ |
static FVECT smDefault_base[4] = { {SQRT3_INV, SQRT3_INV, SQRT3_INV}, |
25 |
+ |
{-SQRT3_INV, -SQRT3_INV, SQRT3_INV}, |
26 |
+ |
{-SQRT3_INV, SQRT3_INV, -SQRT3_INV}, |
27 |
+ |
{SQRT3_INV, -SQRT3_INV, -SQRT3_INV}}; |
28 |
+ |
static int smTri_verts[4][3] = { {0,1,2},{0,2,3},{0,3,1},{1,3,2}}; |
29 |
+ |
|
30 |
+ |
static int smBase_nbrs[4][3] = { {3,1,2},{3,2,0},{3,0,1},{1,0,2}}; |
31 |
+ |
|
32 |
|
#ifdef TEST_DRIVER |
24 |
– |
VIEW View = {0,{0,0,0},{0,0,-1},{0,1,0},60,60,0}; |
33 |
|
VIEW Current_View = {0,{0,0,0},{0,0,-1},{0,1,0},60,60,0}; |
34 |
|
int Pick_cnt =0; |
35 |
< |
int Pick_tri = -1,Picking = FALSE; |
35 |
> |
int Pick_tri = -1,Picking = FALSE,Pick_samp=-1; |
36 |
|
FVECT Pick_point[500],Pick_origin,Pick_dir; |
37 |
|
FVECT Pick_v0[500], Pick_v1[500], Pick_v2[500]; |
38 |
+ |
int Pick_q[500]; |
39 |
|
FVECT P0,P1,P2; |
40 |
|
FVECT FrustumNear[4],FrustumFar[4]; |
41 |
|
double dev_zmin=.01,dev_zmax=1000; |
46 |
|
FVECT ps; |
47 |
|
int id; |
48 |
|
{ |
49 |
< |
FVECT p; |
50 |
< |
|
42 |
< |
VCOPY(p,SM_NTH_WV(sm,id)); |
43 |
< |
point_on_sphere(ps,p,SM_VIEW_CENTER(sm)); |
49 |
> |
VSUB(ps,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); |
50 |
> |
normalize(ps); |
51 |
|
} |
52 |
|
|
53 |
< |
smClear_mesh(sm) |
54 |
< |
SM *sm; |
53 |
> |
smDir_in_cone(sm,ps,id) |
54 |
> |
SM *sm; |
55 |
> |
FVECT ps; |
56 |
> |
int id; |
57 |
|
{ |
58 |
< |
/* Reset the triangle counters */ |
59 |
< |
SM_TRI_CNT(sm) = 0; |
60 |
< |
SM_NUM_TRIS(sm) = 0; |
52 |
< |
SM_FREE_TRIS(sm) = -1; |
58 |
> |
|
59 |
> |
VSUB(ps,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); |
60 |
> |
normalize(ps); |
61 |
|
} |
62 |
|
|
63 |
|
smClear_flags(sm,which) |
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))); |
71 |
> |
bzero(SM_NTH_FLAGS(sm,i),FLAG_BYTES(SM_MAX_TRIS(sm))); |
72 |
|
else |
73 |
< |
bzero(SM_NTH_FLAGS(sm,which),T_TOTAL_FLAG_BYTES(SM_MAX_TRIS(sm))); |
73 |
> |
bzero(SM_NTH_FLAGS(sm,which),FLAG_BYTES(SM_MAX_TRIS(sm))); |
74 |
|
} |
75 |
|
|
76 |
< |
smClear_locator(sm) |
77 |
< |
SM *sm; |
76 |
> |
/* Given an allocated mesh- initialize */ |
77 |
> |
smInit_mesh(sm) |
78 |
> |
SM *sm; |
79 |
|
{ |
80 |
< |
STREE *st; |
81 |
< |
|
82 |
< |
st = SM_LOCATOR(sm); |
83 |
< |
|
84 |
< |
stClear(st); |
80 |
> |
/* Reset the triangle counters */ |
81 |
> |
SM_NUM_TRI(sm) = 0; |
82 |
> |
SM_SAMPLE_TRIS(sm) = 0; |
83 |
> |
SM_FREE_TRIS(sm) = -1; |
84 |
> |
smClear_flags(sm,-1); |
85 |
|
} |
86 |
|
|
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 |
< |
|
88 |
> |
/* Clear the SM for reuse: free any extra allocated memory:does initialization |
89 |
> |
as well |
90 |
> |
*/ |
91 |
|
smClear(sm) |
92 |
|
SM *sm; |
93 |
|
{ |
94 |
|
smClear_samples(sm); |
94 |
– |
smClear_mesh(sm); |
95 |
|
smClear_locator(sm); |
96 |
+ |
smInit_mesh(sm); |
97 |
|
} |
98 |
|
|
99 |
+ |
static int realloc_cnt=0; |
100 |
+ |
|
101 |
|
int |
102 |
< |
smAlloc_tris(sm,max_verts,max_tris) |
102 |
> |
smRealloc_mesh(sm) |
103 |
|
SM *sm; |
104 |
+ |
{ |
105 |
+ |
int fbytes,i,max_tris,max_verts; |
106 |
+ |
|
107 |
+ |
if(realloc_cnt <=0) |
108 |
+ |
realloc_cnt = SM_MAX_TRIS(sm); |
109 |
+ |
|
110 |
+ |
max_tris = SM_MAX_TRIS(sm) + realloc_cnt; |
111 |
+ |
fbytes = FLAG_BYTES(max_tris); |
112 |
+ |
|
113 |
+ |
if(!(SM_TRIS(sm) = (TRI *)realloc(SM_TRIS(sm),max_tris*sizeof(TRI)))) |
114 |
+ |
goto memerr; |
115 |
+ |
|
116 |
+ |
for(i=0; i< T_FLAGS; i++) |
117 |
+ |
if(!(SM_NTH_FLAGS(sm,i)=(int4 *)realloc((char *)SM_NTH_FLAGS(sm,i),fbytes))) |
118 |
+ |
goto memerr; |
119 |
+ |
|
120 |
+ |
SM_MAX_TRIS(sm) = max_tris; |
121 |
+ |
return(max_tris); |
122 |
+ |
|
123 |
+ |
memerr: |
124 |
+ |
error(SYSTEM, "out of memory in smRealloc_mesh()"); |
125 |
+ |
} |
126 |
+ |
|
127 |
+ |
/* Allocate and initialize a new mesh with max_verts and max_tris */ |
128 |
+ |
int |
129 |
+ |
smAlloc_mesh(sm,max_verts,max_tris) |
130 |
+ |
SM *sm; |
131 |
|
int max_verts,max_tris; |
132 |
|
{ |
133 |
< |
int i,nbytes,vbytes,fbytes; |
133 |
> |
int fbytes,i; |
134 |
|
|
135 |
< |
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); |
135 |
> |
fbytes = FLAG_BYTES(max_tris); |
136 |
|
|
137 |
< |
if (SM_BASE(sm) == NULL) |
138 |
< |
return(0); |
137 |
> |
if(!(SM_TRIS(sm) = (TRI *)realloc(NULL,max_tris*sizeof(TRI)))) |
138 |
> |
goto memerr; |
139 |
|
|
140 |
< |
SM_TRIS(sm) = (TRI *)SM_BASE(sm); |
141 |
< |
SM_VERTS(sm) = (VERT *)(SM_TRIS(sm) + max_tris); |
140 |
> |
if(!(SM_VERTS(sm) = (VERT *)realloc(NULL,max_verts*sizeof(VERT)))) |
141 |
> |
goto memerr; |
142 |
|
|
143 |
< |
SM_NTH_FLAGS(sm,0) = (int4 *)(SM_VERTS(sm) + max_verts); |
144 |
< |
for(i=1; i < T_FLAGS; i++) |
145 |
< |
SM_NTH_FLAGS(sm,i) = (int4 *)(SM_NTH_FLAGS(sm,i-1)+fbytes/sizeof(int4)); |
146 |
< |
|
143 |
> |
for(i=0; i< T_FLAGS; i++) |
144 |
> |
if(!(SM_NTH_FLAGS(sm,i)=(int4 *)realloc(NULL,fbytes))) |
145 |
> |
goto memerr; |
146 |
> |
|
147 |
|
SM_MAX_VERTS(sm) = max_verts; |
148 |
|
SM_MAX_TRIS(sm) = max_tris; |
149 |
|
|
150 |
< |
smClear_mesh(sm); |
150 |
> |
realloc_cnt = max_verts >> 1; |
151 |
|
|
152 |
+ |
smInit_mesh(sm); |
153 |
+ |
|
154 |
|
return(max_tris); |
155 |
+ |
memerr: |
156 |
+ |
error(SYSTEM, "out of memory in smAlloc_mesh()"); |
157 |
|
} |
158 |
|
|
159 |
|
|
135 |
– |
|
160 |
|
int |
161 |
< |
smAlloc_locator(sm) |
161 |
> |
smAlloc_tri(sm) |
162 |
|
SM *sm; |
163 |
|
{ |
164 |
< |
STREE *st; |
165 |
< |
|
166 |
< |
st = SM_LOCATOR(sm); |
167 |
< |
|
168 |
< |
st = stAlloc(st); |
169 |
< |
|
170 |
< |
if(st) |
171 |
< |
return(TRUE); |
172 |
< |
else |
173 |
< |
return(FALSE); |
164 |
> |
int id; |
165 |
> |
|
166 |
> |
/* First check if there are any tris on the free list */ |
167 |
> |
/* Otherwise, have we reached the end of the list yet?*/ |
168 |
> |
if(SM_NUM_TRI(sm) < SM_MAX_TRIS(sm)) |
169 |
> |
return(SM_NUM_TRI(sm)++); |
170 |
> |
|
171 |
> |
if((id = SM_FREE_TRIS(sm)) != -1) |
172 |
> |
{ |
173 |
> |
SM_FREE_TRIS(sm) = T_NEXT_FREE(SM_NTH_TRI(sm,id)); |
174 |
> |
return(id); |
175 |
> |
} |
176 |
> |
|
177 |
> |
/*Else: realloc */ |
178 |
> |
smRealloc_mesh(sm); |
179 |
> |
return(SM_NUM_TRI(sm)++); |
180 |
|
} |
181 |
|
|
182 |
+ |
smFree_mesh(sm) |
183 |
+ |
SM *sm; |
184 |
+ |
{ |
185 |
+ |
int i; |
186 |
+ |
|
187 |
+ |
if(SM_TRIS(sm)) |
188 |
+ |
free(SM_TRIS(sm)); |
189 |
+ |
if(SM_VERTS(sm)) |
190 |
+ |
free(SM_VERTS(sm)); |
191 |
+ |
for(i=0; i< T_FLAGS; i++) |
192 |
+ |
if(SM_NTH_FLAGS(sm,i)) |
193 |
+ |
free(SM_NTH_FLAGS(sm,i)); |
194 |
+ |
} |
195 |
+ |
|
196 |
+ |
|
197 |
|
/* Initialize/clear global smL sample list for at least n samples */ |
198 |
|
smAlloc(max_samples) |
199 |
|
register int max_samples; |
201 |
|
unsigned nbytes; |
202 |
|
register unsigned i; |
203 |
|
int total_points; |
204 |
< |
int max_tris; |
204 |
> |
int max_tris,n; |
205 |
|
|
206 |
+ |
n = max_samples; |
207 |
|
/* If this is the first call, allocate sample,vertex and triangle lists */ |
208 |
|
if(!smMesh) |
209 |
|
{ |
210 |
|
if(!(smMesh = (SM *)malloc(sizeof(SM)))) |
211 |
< |
error(SYSTEM,"smAlloc():Unable to allocate memory"); |
211 |
> |
error(SYSTEM,"smAlloc():Unable to allocate memory\n"); |
212 |
|
bzero(smMesh,sizeof(SM)); |
213 |
|
} |
214 |
|
else |
215 |
|
{ /* If existing structure: first deallocate */ |
216 |
< |
if(SM_BASE(smMesh)) |
217 |
< |
free(SM_BASE(smMesh)); |
218 |
< |
if(SM_SAMP_BASE(smMesh)) |
219 |
< |
free(SM_SAMP_BASE(smMesh)); |
174 |
< |
} |
216 |
> |
smFree_mesh(smMesh); |
217 |
> |
smFree_samples(smMesh); |
218 |
> |
smFree_locator(smMesh); |
219 |
> |
} |
220 |
|
|
221 |
|
/* First allocate at least n samples + extra points:at least enough |
222 |
|
necessary to form the BASE MESH- Default = 4; |
223 |
|
*/ |
224 |
< |
max_samples = smAlloc_samples(smMesh, max_samples,SM_EXTRA_POINTS); |
224 |
> |
SM_SAMP(smMesh) = sAlloc(&n,SM_EXTRA_POINTS); |
225 |
|
|
226 |
< |
total_points = max_samples + SM_EXTRA_POINTS; |
182 |
< |
max_tris = total_points*2; |
226 |
> |
total_points = n + SM_EXTRA_POINTS; |
227 |
|
|
228 |
+ |
max_tris = total_points*4; |
229 |
|
/* Now allocate space for mesh vertices and triangles */ |
230 |
< |
max_tris = smAlloc_tris(smMesh, total_points, max_tris); |
230 |
> |
max_tris = smAlloc_mesh(smMesh, total_points, max_tris); |
231 |
|
|
232 |
|
/* Initialize the structure for point,triangle location. |
233 |
|
*/ |
234 |
|
smAlloc_locator(smMesh); |
190 |
– |
|
235 |
|
} |
236 |
|
|
237 |
|
|
238 |
|
|
239 |
< |
smInit_mesh(sm,vp) |
239 |
> |
smInit_sm(sm,vp) |
240 |
|
SM *sm; |
241 |
|
FVECT vp; |
242 |
|
{ |
243 |
|
|
200 |
– |
/* NOTE: Should be elsewhere?*/ |
244 |
|
smDist_sum = 0; |
245 |
|
smNew_tri_cnt = 0; |
246 |
|
|
247 |
< |
VCOPY(SM_VIEW_CENTER(smMesh),vp); |
248 |
< |
smClear_locator(sm); |
249 |
< |
smInit_locator(sm,vp,0); |
250 |
< |
smClear_aux_samples(sm); |
208 |
< |
smClear_mesh(sm); |
247 |
> |
VCOPY(SM_VIEW_CENTER(sm),vp); |
248 |
> |
smInit_locator(sm,vp); |
249 |
> |
smInit_samples(sm); |
250 |
> |
smInit_mesh(sm); |
251 |
|
smCreate_base_mesh(sm,SM_DEFAULT); |
252 |
|
} |
253 |
|
|
268 |
|
{ |
269 |
|
int max_vertices; |
270 |
|
|
271 |
< |
sleep(10); |
230 |
< |
|
271 |
> |
|
272 |
|
/* If n <=0, Just clear the existing structures */ |
273 |
|
if(n <= 0) |
274 |
|
{ |
282 |
|
max_vertices = n + SM_EXTRA_POINTS; |
283 |
|
|
284 |
|
/* If the current mesh contains enough room, clear and return */ |
285 |
< |
if(smMesh && max_vertices <= SM_MAX_VERTS(smMesh)) |
285 |
> |
if(smMesh && (max_vertices <= SM_MAX_VERTS(smMesh)) && SM_MAX_SAMP(smMesh) <= |
286 |
> |
n && SM_MAX_POINTS(smMesh) <= max_vertices) |
287 |
|
{ |
288 |
|
smClear(smMesh); |
289 |
|
return(SM_MAX_SAMP(smMesh)); |
297 |
|
} |
298 |
|
|
299 |
|
|
300 |
< |
int |
301 |
< |
smLocator_apply_func(sm,v0,v1,v2,func,arg) |
302 |
< |
SM *sm; |
303 |
< |
FVECT v0,v1,v2; |
304 |
< |
int (*func)(); |
305 |
< |
char *arg; |
300 |
> |
smLocator_apply_func(sm,v0,v1,v2,edge_func,tri_func,argptr) |
301 |
> |
SM *sm; |
302 |
> |
FVECT v0,v1,v2; |
303 |
> |
int (*edge_func)(); |
304 |
> |
int (*tri_func)(); |
305 |
> |
int *argptr; |
306 |
|
{ |
307 |
|
STREE *st; |
266 |
– |
char found; |
308 |
|
FVECT p0,p1,p2; |
309 |
|
|
310 |
|
st = SM_LOCATOR(sm); |
311 |
|
|
312 |
< |
point_on_sphere(p0,v0,SM_VIEW_CENTER(sm)); |
313 |
< |
point_on_sphere(p1,v1,SM_VIEW_CENTER(sm)); |
314 |
< |
point_on_sphere(p2,v2,SM_VIEW_CENTER(sm)); |
312 |
> |
VSUB(p0,v0,SM_VIEW_CENTER(sm)); |
313 |
> |
VSUB(p1,v1,SM_VIEW_CENTER(sm)); |
314 |
> |
VSUB(p2,v2,SM_VIEW_CENTER(sm)); |
315 |
|
|
316 |
< |
found = stApply_to_tri_cells(st,p0,p1,p2,func,arg); |
316 |
> |
stApply_to_tri(st,p0,p1,p2,edge_func,tri_func,argptr); |
317 |
|
|
277 |
– |
return(found); |
318 |
|
} |
319 |
|
|
320 |
+ |
QUADTREE |
321 |
+ |
delete_tri_set(qt,optr,del_set) |
322 |
+ |
QUADTREE qt; |
323 |
+ |
OBJECT *optr,*del_set; |
324 |
+ |
{ |
325 |
|
|
326 |
< |
int |
327 |
< |
smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id) |
326 |
> |
int set_size,i,t_id; |
327 |
> |
OBJECT *rptr,r_set[QT_MAXSET+1]; |
328 |
> |
OBJECT *tptr,t_set[QT_MAXSET+1],*sptr; |
329 |
> |
|
330 |
> |
/* First need to check if set size larger than QT_MAXSET: if so |
331 |
> |
need to allocate larger array |
332 |
> |
*/ |
333 |
> |
if((set_size = MAX(QT_SET_CNT(optr),QT_SET_CNT(del_set))) >QT_MAXSET) |
334 |
> |
rptr = (OBJECT *)malloc((set_size+1)*sizeof(OBJECT)); |
335 |
> |
else |
336 |
> |
rptr = r_set; |
337 |
> |
if(!rptr) |
338 |
> |
goto memerr; |
339 |
> |
setintersect(rptr,del_set,optr); |
340 |
> |
|
341 |
> |
if(QT_SET_CNT(rptr) > 0) |
342 |
> |
{ |
343 |
> |
/* First need to check if set size larger than QT_MAXSET: if so |
344 |
> |
need to allocate larger array |
345 |
> |
*/ |
346 |
> |
sptr = QT_SET_PTR(rptr); |
347 |
> |
for(i = QT_SET_CNT(rptr); i > 0; i--) |
348 |
> |
{ |
349 |
> |
t_id = QT_SET_NEXT_ELEM(sptr); |
350 |
> |
qt = qtdelelem(qt,t_id); |
351 |
> |
} |
352 |
> |
} |
353 |
> |
/* If we allocated memory: free it */ |
354 |
> |
if(rptr != r_set) |
355 |
> |
free(rptr); |
356 |
> |
|
357 |
> |
return(qt); |
358 |
> |
memerr: |
359 |
> |
error(SYSTEM,"delete_tri_set():Unable to allocate memory"); |
360 |
> |
} |
361 |
> |
|
362 |
> |
QUADTREE |
363 |
> |
expand_node(qt,q0,q1,q2,optr,n) |
364 |
> |
QUADTREE qt; |
365 |
> |
FVECT q0,q1,q2; |
366 |
> |
OBJECT *optr; |
367 |
> |
int n; |
368 |
> |
{ |
369 |
> |
OBJECT *tptr,t_set[QT_MAXSET+1]; |
370 |
> |
int i,t_id,found; |
371 |
> |
TRI *t; |
372 |
> |
FVECT v0,v1,v2; |
373 |
> |
|
374 |
> |
if(QT_SET_CNT(optr) > QT_MAXSET) |
375 |
> |
tptr = (OBJECT *)malloc((QT_SET_CNT(optr)+1)*sizeof(OBJECT)); |
376 |
> |
else |
377 |
> |
tptr = t_set; |
378 |
> |
if(!tptr) |
379 |
> |
goto memerr; |
380 |
> |
|
381 |
> |
qtgetset(tptr,qt); |
382 |
> |
/* If set size exceeds threshold: subdivide cell and reinsert tris*/ |
383 |
> |
qtfreeleaf(qt); |
384 |
> |
qtSubdivide(qt); |
385 |
> |
|
386 |
> |
for(optr = QT_SET_PTR(tptr),i=QT_SET_CNT(tptr); i > 0; i--) |
387 |
> |
{ |
388 |
> |
t_id = QT_SET_NEXT_ELEM(optr); |
389 |
> |
t = SM_NTH_TRI(smMesh,t_id); |
390 |
> |
if(!T_IS_VALID(t)) |
391 |
> |
continue; |
392 |
> |
VSUB(v0,SM_T_NTH_WV(smMesh,t,0),SM_VIEW_CENTER(smMesh)); |
393 |
> |
VSUB(v1,SM_T_NTH_WV(smMesh,t,1),SM_VIEW_CENTER(smMesh)); |
394 |
> |
VSUB(v2,SM_T_NTH_WV(smMesh,t,2),SM_VIEW_CENTER(smMesh)); |
395 |
> |
qt = qtAdd_tri(qt,q0,q1,q2,v0,v1,v2,t_id,n); |
396 |
> |
} |
397 |
> |
/* If we allocated memory: free it */ |
398 |
> |
if( tptr != t_set) |
399 |
> |
free(tptr); |
400 |
> |
|
401 |
> |
return(qt); |
402 |
> |
memerr: |
403 |
> |
error(SYSTEM,"expand_node():Unable to allocate memory"); |
404 |
> |
} |
405 |
> |
|
406 |
> |
add_tri_expand(qtptr,f,argptr,q0,q1,q2,t0,t1,t2,n) |
407 |
> |
QUADTREE *qtptr; |
408 |
> |
int *f; |
409 |
> |
ADD_ARGS *argptr; |
410 |
> |
FVECT q0,q1,q2; |
411 |
> |
FVECT t0,t1,t2; |
412 |
> |
int n; |
413 |
> |
{ |
414 |
> |
int t_id; |
415 |
> |
OBJECT *optr,*del_set; |
416 |
> |
|
417 |
> |
t_id = argptr->t_id; |
418 |
> |
|
419 |
> |
if(QT_IS_EMPTY(*qtptr)) |
420 |
> |
{ |
421 |
> |
*qtptr = qtaddelem(*qtptr,t_id); |
422 |
> |
return; |
423 |
> |
} |
424 |
> |
if(!QT_LEAF_IS_FLAG(*qtptr)) |
425 |
> |
{ |
426 |
> |
optr = qtqueryset(*qtptr); |
427 |
> |
|
428 |
> |
if(del_set=argptr->del_set) |
429 |
> |
*qtptr = delete_tri_set(*qtptr,optr,del_set); |
430 |
> |
*qtptr = qtaddelem(*qtptr,t_id); |
431 |
> |
} |
432 |
> |
if (n >= QT_MAX_LEVELS) |
433 |
> |
return; |
434 |
> |
optr = qtqueryset(*qtptr); |
435 |
> |
if(QT_SET_CNT(optr) < QT_SET_THRESHOLD) |
436 |
> |
return; |
437 |
> |
*qtptr = expand_node(*qtptr,q0,q1,q2,optr,n); |
438 |
> |
} |
439 |
> |
|
440 |
> |
|
441 |
> |
|
442 |
> |
add_tri(qtptr,fptr,argptr) |
443 |
> |
QUADTREE *qtptr; |
444 |
> |
int *fptr; |
445 |
> |
ADD_ARGS *argptr; |
446 |
> |
{ |
447 |
> |
|
448 |
> |
OBJECT *optr,*del_set; |
449 |
> |
int t_id; |
450 |
> |
|
451 |
> |
t_id = argptr->t_id; |
452 |
> |
|
453 |
> |
|
454 |
> |
if(QT_IS_EMPTY(*qtptr)) |
455 |
> |
{ |
456 |
> |
*qtptr = qtaddelem(*qtptr,t_id); |
457 |
> |
if(!QT_FLAG_FILL_TRI(*fptr)) |
458 |
> |
(*fptr)++; |
459 |
> |
return; |
460 |
> |
} |
461 |
> |
if(QT_LEAF_IS_FLAG(*qtptr)) |
462 |
> |
return; |
463 |
> |
|
464 |
> |
optr = qtqueryset(*qtptr); |
465 |
> |
|
466 |
> |
if(del_set = argptr->del_set) |
467 |
> |
*qtptr = delete_tri_set(*qtptr,optr,del_set); |
468 |
> |
|
469 |
> |
if(!QT_IS_EMPTY(*qtptr)) |
470 |
> |
{ |
471 |
> |
optr = qtqueryset(*qtptr); |
472 |
> |
if(QT_SET_CNT(optr) >= QT_SET_THRESHOLD) |
473 |
> |
(*fptr) |= QT_EXPAND; |
474 |
> |
} |
475 |
> |
if(!QT_FLAG_FILL_TRI(*fptr)) |
476 |
> |
(*fptr)++; |
477 |
> |
*qtptr = qtaddelem(*qtptr,t_id); |
478 |
> |
|
479 |
> |
} |
480 |
> |
|
481 |
> |
|
482 |
> |
smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id,del_set) |
483 |
|
SM *sm; |
484 |
|
int t_id; |
485 |
< |
int v0_id,v1_id,v2_id; |
485 |
> |
int v0_id,v1_id,v2_id; |
486 |
> |
OBJECT *del_set; |
487 |
|
{ |
488 |
|
STREE *st; |
489 |
< |
FVECT p0,p1,p2; |
490 |
< |
|
489 |
> |
FVECT v0,v1,v2; |
490 |
> |
ADD_ARGS args; |
491 |
> |
|
492 |
|
st = SM_LOCATOR(sm); |
493 |
|
|
494 |
< |
smDir(sm,p0,v0_id); |
495 |
< |
smDir(sm,p1,v1_id); |
496 |
< |
smDir(sm,p2,v2_id); |
494 |
> |
#ifdef DEBUG |
495 |
> |
if((v0_id == INVALID) || (v1_id == INVALID) || (v2_id == INVALID)) |
496 |
> |
error(CONSISTENCY,"Invalid ids 1\n"); |
497 |
> |
#endif |
498 |
|
|
499 |
< |
stAdd_tri(st,t_id,p0,p1,p2); |
499 |
> |
VSUB(v0,SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm)); |
500 |
> |
VSUB(v1,SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm)); |
501 |
> |
VSUB(v2,SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm)); |
502 |
|
|
503 |
< |
return(1); |
503 |
> |
qtClearAllFlags(); |
504 |
> |
args.t_id = t_id; |
505 |
> |
args.del_set = del_set; |
506 |
> |
|
507 |
> |
stApply_to_tri(st,v0,v1,v2,add_tri,add_tri_expand,&args); |
508 |
> |
|
509 |
|
} |
510 |
|
|
511 |
|
/* Add a triangle to the base array with vertices v1-v2-v3 */ |
512 |
|
int |
513 |
< |
smAdd_tri(sm, v0_id,v1_id,v2_id,tptr) |
513 |
> |
smAdd_tri(sm, v0_id,v1_id,v2_id) |
514 |
|
SM *sm; |
515 |
|
int v0_id,v1_id,v2_id; |
306 |
– |
TRI **tptr; |
516 |
|
{ |
517 |
|
int t_id; |
518 |
|
TRI *t; |
519 |
+ |
#ifdef DEBUG |
520 |
+ |
if(v0_id==v1_id || v0_id==v2_id || v1_id==v2_id) |
521 |
+ |
{ |
522 |
+ |
eputs("smAdd_tri: invalid vertex ids\n"); |
523 |
+ |
return(INVALID); |
524 |
+ |
} |
525 |
+ |
#endif |
526 |
+ |
t_id = smAlloc_tri(sm); |
527 |
|
|
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); |
528 |
|
if(t_id == -1) |
529 |
|
return(t_id); |
530 |
|
|
531 |
|
t = SM_NTH_TRI(sm,t_id); |
532 |
+ |
|
533 |
|
T_CLEAR_NBRS(t); |
534 |
+ |
/* set the triangle vertex ids */ |
535 |
+ |
T_NTH_V(t,0) = v0_id; |
536 |
+ |
T_NTH_V(t,1) = v1_id; |
537 |
+ |
T_NTH_V(t,2) = v2_id; |
538 |
|
|
539 |
+ |
SM_NTH_VERT(sm,v0_id) = t_id; |
540 |
+ |
SM_NTH_VERT(sm,v1_id) = t_id; |
541 |
+ |
SM_NTH_VERT(sm,v2_id) = t_id; |
542 |
+ |
|
543 |
|
if(SM_BASE_ID(sm,v0_id) || SM_BASE_ID(sm,v1_id) || SM_BASE_ID(sm,v2_id)) |
544 |
|
{ |
545 |
|
smClear_tri_flags(sm,t_id); |
547 |
|
} |
548 |
|
else |
549 |
|
{ |
550 |
< |
SM_CLEAR_NTH_T_BASE(sm,t_id); |
550 |
> |
SM_CLR_NTH_T_BASE(sm,t_id); |
551 |
|
SM_SET_NTH_T_ACTIVE(sm,t_id); |
332 |
– |
SM_SET_NTH_T_LRU(sm,t_id); |
552 |
|
SM_SET_NTH_T_NEW(sm,t_id); |
553 |
< |
SM_NUM_TRIS(sm)++; |
553 |
> |
S_SET_FLAG(T_NTH_V(t,0)); |
554 |
> |
S_SET_FLAG(T_NTH_V(t,1)); |
555 |
> |
S_SET_FLAG(T_NTH_V(t,2)); |
556 |
> |
SM_SAMPLE_TRIS(sm)++; |
557 |
|
smNew_tri_cnt++; |
558 |
|
} |
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; |
559 |
|
|
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; |
560 |
|
/* return initialized triangle */ |
561 |
|
return(t_id); |
562 |
|
} |
563 |
|
|
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; |
564 |
|
|
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 |
– |
|
565 |
|
void |
566 |
< |
smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id) |
566 |
> |
smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add_ptr,delptr) |
567 |
|
SM *sm; |
568 |
|
int t_id,t1_id; |
569 |
|
int e,e1; |
570 |
< |
int **tn_id,**tn1_id; |
570 |
> |
int *tn_id,*tn1_id; |
571 |
> |
LIST **add_ptr; |
572 |
> |
QUADTREE *delptr; |
573 |
|
|
574 |
|
{ |
452 |
– |
TRI *t,*t1; |
453 |
– |
TRI *ta,*tb; |
575 |
|
int verts[3],enext,eprev,e1next,e1prev; |
576 |
< |
TRI *n; |
576 |
> |
TRI *n,*ta,*tb,*t,*t1; |
577 |
|
FVECT p1,p2,p3; |
578 |
|
int ta_id,tb_id; |
579 |
< |
/* swap diagonal (e relative to t, and e1 relative to t1) |
580 |
< |
defined by quadrilateral |
460 |
< |
formed by t,t1- swap for the opposite diagonal |
579 |
> |
/* form new diagonal (e relative to t, and e1 relative to t1) |
580 |
> |
defined by quadrilateral formed by t,t1- swap for the opposite diagonal |
581 |
|
*/ |
462 |
– |
t = SM_NTH_TRI(sm,t_id); |
463 |
– |
t1 = SM_NTH_TRI(sm,t1_id); |
582 |
|
enext = (e+1)%3; |
583 |
|
eprev = (e+2)%3; |
584 |
|
e1next = (e1+1)%3; |
585 |
|
e1prev = (e1+2)%3; |
586 |
< |
verts[e] = T_NTH_V(t,e); |
587 |
< |
verts[enext] = T_NTH_V(t1,e1prev); |
588 |
< |
verts[eprev] = T_NTH_V(t,eprev); |
589 |
< |
ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&ta); |
586 |
> |
verts[e] = T_NTH_V(SM_NTH_TRI(sm,t_id),e); |
587 |
> |
verts[enext] = T_NTH_V(SM_NTH_TRI(sm,t_id),enext); |
588 |
> |
verts[eprev] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1); |
589 |
> |
ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2]); |
590 |
> |
*add_ptr = push_data(*add_ptr,ta_id); |
591 |
> |
verts[e1] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1); |
592 |
> |
verts[e1next] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1next); |
593 |
> |
verts[e1prev] = T_NTH_V(SM_NTH_TRI(sm,t_id),e); |
594 |
> |
tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2]); |
595 |
> |
*add_ptr = push_data(*add_ptr,tb_id); |
596 |
|
|
597 |
< |
verts[e1] = T_NTH_V(t1,e1); |
598 |
< |
verts[e1next] = T_NTH_V(t,eprev); |
599 |
< |
verts[e1prev] = T_NTH_V(t1,e1prev); |
600 |
< |
tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&tb); |
477 |
< |
|
597 |
> |
ta = SM_NTH_TRI(sm,ta_id); |
598 |
> |
tb = SM_NTH_TRI(sm,tb_id); |
599 |
> |
t = SM_NTH_TRI(sm,t_id); |
600 |
> |
t1 = SM_NTH_TRI(sm,t1_id); |
601 |
|
/* set the neighbors */ |
602 |
|
T_NTH_NBR(ta,e) = T_NTH_NBR(t1,e1next); |
603 |
|
T_NTH_NBR(tb,e1) = T_NTH_NBR(t,enext); |
604 |
< |
T_NTH_NBR(ta,enext) = tb_id; |
605 |
< |
T_NTH_NBR(tb,e1next) = ta_id; |
606 |
< |
T_NTH_NBR(ta,eprev) = T_NTH_NBR(t,eprev); |
607 |
< |
T_NTH_NBR(tb,e1prev) = T_NTH_NBR(t1,e1prev); |
604 |
> |
T_NTH_NBR(ta,enext)= tb_id; |
605 |
> |
T_NTH_NBR(tb,e1next)= ta_id; |
606 |
> |
T_NTH_NBR(ta,eprev)=T_NTH_NBR(t,eprev); |
607 |
> |
T_NTH_NBR(tb,e1prev)=T_NTH_NBR(t1,e1prev); |
608 |
|
|
609 |
|
/* Reset neighbor pointers of original neighbors */ |
610 |
|
n = SM_NTH_TRI(sm,T_NTH_NBR(t,enext)); |
618 |
|
T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = tb_id; |
619 |
|
|
620 |
|
/* Delete two parent triangles */ |
621 |
< |
smDelete_tri(sm,t_id); |
622 |
< |
smDelete_tri(sm,t1_id); |
621 |
> |
if(remove_from_list(t_id,add_ptr)) |
622 |
> |
smDelete_tri(sm,t_id); |
623 |
> |
else |
624 |
> |
*delptr = qtaddelem(*delptr,t_id); |
625 |
> |
|
626 |
> |
if(remove_from_list(t1_id,add_ptr)) |
627 |
> |
smDelete_tri(sm,t1_id); |
628 |
> |
else |
629 |
> |
*delptr = qtaddelem(*delptr,t1_id); |
630 |
> |
|
631 |
|
*tn_id = ta_id; |
632 |
|
*tn1_id = tb_id; |
633 |
|
} |
634 |
|
|
635 |
+ |
smUpdate_locator(sm,add_list,del_set) |
636 |
+ |
SM *sm; |
637 |
+ |
LIST *add_list; |
638 |
+ |
OBJECT *del_set; |
639 |
+ |
{ |
640 |
+ |
int t_id,i; |
641 |
+ |
TRI *t; |
642 |
+ |
OBJECT *optr; |
643 |
+ |
|
644 |
+ |
while(add_list) |
645 |
+ |
{ |
646 |
+ |
t_id = pop_list(&add_list); |
647 |
+ |
t = SM_NTH_TRI(sm,t_id); |
648 |
+ |
smLocator_add_tri(sm,t_id,T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2),del_set); |
649 |
+ |
} |
650 |
+ |
|
651 |
+ |
optr = QT_SET_PTR(del_set); |
652 |
+ |
for(i = QT_SET_CNT(del_set); i > 0; i--) |
653 |
+ |
{ |
654 |
+ |
t_id = QT_SET_NEXT_ELEM(optr); |
655 |
+ |
#if 0 |
656 |
+ |
t = SM_NTH_TRI(sm,t_id); |
657 |
+ |
smLocator_remove_tri(sm,t_id,T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2)); |
658 |
+ |
#endif |
659 |
+ |
smDelete_tri(sm,t_id); |
660 |
+ |
} |
661 |
+ |
} |
662 |
|
/* MUST add check for constrained edges */ |
663 |
< |
char |
664 |
< |
smFix_tris(sm,id,tlist) |
663 |
> |
int |
664 |
> |
smFix_tris(sm,id,tlist,add_list,delptr) |
665 |
|
SM *sm; |
666 |
|
int id; |
667 |
< |
LIST *tlist; |
667 |
> |
LIST *tlist,*add_list; |
668 |
> |
QUADTREE *delptr; |
669 |
|
{ |
670 |
|
TRI *t,*t_opp; |
671 |
< |
FVECT p,p1,np,p2,p3; |
672 |
< |
int swapped = 0; |
514 |
< |
int e,e1,e_id; |
515 |
< |
char debug = 0; |
671 |
> |
FVECT p,p0,p1,p2; |
672 |
> |
int e,e1,swapped = 0; |
673 |
|
int t_id,t_opp_id; |
674 |
< |
|
675 |
< |
VCOPY(p,SM_NTH_WV(sm,id)); |
519 |
< |
VSUB(p,p,SM_VIEW_CENTER(sm)); |
674 |
> |
|
675 |
> |
VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); |
676 |
|
while(tlist) |
677 |
|
{ |
678 |
< |
t_id = (int)pop_list(&tlist); |
678 |
> |
t_id = pop_list(&tlist); |
679 |
> |
#ifdef DEBUG |
680 |
> |
if(t_id==INVALID || t_id > smMesh->num_tri) |
681 |
> |
error(CONSISTENCY,"Invalid tri id smFix_tris()\n"); |
682 |
> |
#endif |
683 |
|
t = SM_NTH_TRI(sm,t_id); |
684 |
< |
e = (T_WHICH_V(t,id)+1)%3; |
684 |
> |
e = T_WHICH_V(t,id); |
685 |
|
t_opp_id = T_NTH_NBR(t,e); |
686 |
< |
t_opp = SM_NTH_TRI(sm,t_opp_id); |
686 |
> |
#ifdef DEBUG |
687 |
> |
if(t_opp_id==INVALID || t_opp_id > smMesh->num_tri) |
688 |
> |
error(CONSISTENCY,"Invalid tri id smFix_tris()\n"); |
689 |
> |
#endif |
690 |
> |
t_opp = SM_NTH_TRI(sm,t_opp_id); |
691 |
|
|
692 |
< |
smDir(sm,p1,T_NTH_V(t_opp,0)); |
693 |
< |
smDir(sm,p2,T_NTH_V(t_opp,1)); |
694 |
< |
smDir(sm,p3,T_NTH_V(t_opp,2)); |
695 |
< |
if(point_in_cone(p,p1,p2,p3)) |
692 |
> |
smDir_in_cone(sm,p0,T_NTH_V(t_opp,0)); |
693 |
> |
smDir_in_cone(sm,p1,T_NTH_V(t_opp,1)); |
694 |
> |
smDir_in_cone(sm,p2,T_NTH_V(t_opp,2)); |
695 |
> |
if(point_in_cone(p,p0,p1,p2)) |
696 |
|
{ |
697 |
|
swapped = 1; |
698 |
|
e1 = T_NTH_NBR_PTR(t_id,t_opp); |
699 |
|
/* check list for t_opp and Remove if there */ |
700 |
|
remove_from_list(t_opp_id,&tlist); |
701 |
< |
|
702 |
< |
smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id); |
701 |
> |
smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id, |
702 |
> |
&add_list,delptr); |
703 |
|
tlist = push_data(tlist,t_id); |
704 |
|
tlist = push_data(tlist,t_opp_id); |
705 |
|
} |
706 |
|
} |
707 |
+ |
smUpdate_locator(sm,add_list,qtqueryset(*delptr)); |
708 |
|
return(swapped); |
709 |
|
} |
710 |
|
|
718 |
|
int id; |
719 |
|
{ |
720 |
|
int t_id; |
721 |
< |
int tri; |
721 |
> |
int nbr_id; |
722 |
|
|
723 |
|
/* Want the edge for which "id" is the destination */ |
724 |
< |
t_id = (T_WHICH_V(t,id)+ 2)% 3; |
725 |
< |
tri = T_NTH_NBR(t,t_id); |
726 |
< |
return(tri); |
724 |
> |
t_id = (T_WHICH_V(t,id)+ 1)% 3; |
725 |
> |
nbr_id = T_NTH_NBR(t,t_id); |
726 |
> |
return(nbr_id); |
727 |
|
} |
728 |
|
|
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 |
– |
|
729 |
|
smClear_tri_flags(sm,id) |
730 |
|
SM *sm; |
731 |
|
int id; |
733 |
|
int i; |
734 |
|
|
735 |
|
for(i=0; i < T_FLAGS; i++) |
736 |
< |
SM_CLEAR_NTH_T_FLAG(sm,id,i); |
736 |
> |
SM_CLR_NTH_T_FLAG(sm,id,i); |
737 |
|
|
738 |
|
} |
739 |
|
|
740 |
|
/* Locate the point-id in the point location structure: */ |
741 |
|
int |
742 |
< |
smReplace_vertex(sm,c,dir,p,tri_id,snew_id,type,which) |
742 |
> |
smInsert_samp(sm,s_id,tri_id) |
743 |
|
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; |
744 |
|
int s_id,tri_id; |
745 |
|
{ |
746 |
< |
TRI *tri,*t0,*t1,*t2,*nbr; |
747 |
< |
int v0_id,v1_id,v2_id,n_id; |
748 |
< |
int t0_id,t1_id,t2_id; |
749 |
< |
LIST *tlist; |
746 |
> |
int v0_id,v1_id,v2_id; |
747 |
> |
int t0_id,t1_id,t2_id,replaced; |
748 |
> |
LIST *tlist,*add_list; |
749 |
> |
OBJECT del_set[2]; |
750 |
> |
QUADTREE delnode; |
751 |
|
FVECT npt; |
752 |
+ |
TRI *tri,*nbr; |
753 |
|
|
754 |
< |
if(s_id == SM_INVALID) |
755 |
< |
s_id = smAdd_sample_point(sm,c,dir,p); |
754 |
> |
add_list = NULL; |
755 |
> |
|
756 |
> |
v0_id = T_NTH_V(SM_NTH_TRI(sm,tri_id),0); |
757 |
> |
v1_id = T_NTH_V(SM_NTH_TRI(sm,tri_id),1); |
758 |
> |
v2_id = T_NTH_V(SM_NTH_TRI(sm,tri_id),2); |
759 |
> |
|
760 |
> |
t0_id = smAdd_tri(sm,s_id,v0_id,v1_id); |
761 |
> |
/* Add triangle to the locator */ |
762 |
|
|
763 |
+ |
add_list = push_data(add_list,t0_id); |
764 |
+ |
|
765 |
+ |
t1_id = smAdd_tri(sm,s_id,v1_id,v2_id); |
766 |
+ |
add_list = push_data(add_list,t1_id); |
767 |
+ |
|
768 |
+ |
t2_id = smAdd_tri(sm,s_id,v2_id,v0_id); |
769 |
+ |
add_list = push_data(add_list,t2_id); |
770 |
+ |
|
771 |
+ |
/* CAUTION: tri must be assigned after Add_tri: pointers may change*/ |
772 |
|
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); |
773 |
|
|
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 |
– |
|
774 |
|
/* Set the neighbor pointers for the new tris */ |
775 |
< |
T_NTH_NBR(t0,0) = t2_id; |
776 |
< |
T_NTH_NBR(t0,1) = T_NTH_NBR(tri,0); |
777 |
< |
T_NTH_NBR(t0,2) = t1_id; |
778 |
< |
T_NTH_NBR(t1,0) = t0_id; |
779 |
< |
T_NTH_NBR(t1,1) = T_NTH_NBR(tri,1); |
780 |
< |
T_NTH_NBR(t1,2) = t2_id; |
781 |
< |
T_NTH_NBR(t2,0) = t1_id; |
782 |
< |
T_NTH_NBR(t2,1) = T_NTH_NBR(tri,2); |
783 |
< |
T_NTH_NBR(t2,2) = t0_id; |
775 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),0) = T_NTH_NBR(tri,2); |
776 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),1) = t1_id; |
777 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),2) = t2_id; |
778 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),0) = T_NTH_NBR(tri,0); |
779 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),1) = t2_id; |
780 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),2) = t0_id; |
781 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),0) = T_NTH_NBR(tri,1); |
782 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),1) = t0_id; |
783 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),2) = t1_id; |
784 |
|
|
785 |
|
/* Reset the neigbor pointers for the neighbors of the original */ |
786 |
|
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)); |
787 |
|
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t1_id; |
788 |
< |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,2)); |
788 |
> |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,1)); |
789 |
|
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t2_id; |
790 |
+ |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,2)); |
791 |
+ |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t0_id; |
792 |
|
|
793 |
< |
smDelete_tri(sm,tri_id); |
794 |
< |
|
793 |
> |
del_set[0] = 1; del_set[1] = tri_id; |
794 |
> |
delnode = qtnewleaf(del_set); |
795 |
> |
|
796 |
|
/* Fix up the new triangles*/ |
797 |
|
tlist = push_data(NULL,t0_id); |
798 |
|
tlist = push_data(tlist,t1_id); |
799 |
|
tlist = push_data(tlist,t2_id); |
800 |
|
|
801 |
< |
smFix_tris(sm,s_id,tlist); |
801 |
> |
smFix_tris(sm,s_id,tlist,add_list,&delnode); |
802 |
|
|
803 |
< |
if(n_id != -1) |
705 |
< |
smDelete_point(sm,n_id); |
803 |
> |
qtfreeleaf(delnode); |
804 |
|
|
805 |
< |
return(s_id); |
805 |
> |
return(TRUE); |
806 |
|
} |
807 |
|
|
808 |
|
|
809 |
|
int |
810 |
< |
smPointLocate(sm,pt,type,which,norm) |
810 |
> |
smTri_in_set(sm,p,optr) |
811 |
|
SM *sm; |
812 |
< |
FVECT pt; |
813 |
< |
char *type,*which; |
716 |
< |
char norm; |
812 |
> |
FVECT p; |
813 |
> |
OBJECT *optr; |
814 |
|
{ |
815 |
< |
STREE *st; |
816 |
< |
int tri; |
817 |
< |
FVECT npt; |
815 |
> |
int i,t_id; |
816 |
> |
FVECT n,v0,v1,v2; |
817 |
> |
TRI *t; |
818 |
|
|
819 |
< |
st = SM_LOCATOR(sm); |
723 |
< |
if(norm) |
819 |
> |
for (i = QT_SET_CNT(optr),optr = QT_SET_PTR(optr);i > 0; i--) |
820 |
|
{ |
821 |
< |
point_on_sphere(npt,pt,SM_VIEW_CENTER(sm)); |
822 |
< |
tri = stPoint_locate(st,npt,type,which); |
821 |
> |
/* Find the first triangle that pt falls */ |
822 |
> |
t_id = QT_SET_NEXT_ELEM(optr); |
823 |
> |
t = SM_NTH_TRI(sm,t_id); |
824 |
> |
if(!T_IS_VALID(t)) |
825 |
> |
continue; |
826 |
> |
VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm)); |
827 |
> |
VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm)); |
828 |
> |
VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm)); |
829 |
> |
|
830 |
> |
if(EQUAL_VEC3(v0,p) || EQUAL_VEC3(v1,p) || EQUAL_VEC3(v2,p)) |
831 |
> |
return(t_id); |
832 |
> |
|
833 |
> |
VCROSS(n,v0,v1); |
834 |
> |
if(DOT(n,p) >0.0) |
835 |
> |
continue; |
836 |
> |
VCROSS(n,v1,v2); |
837 |
> |
if(DOT(n,p) > 0.0) |
838 |
> |
continue; |
839 |
> |
|
840 |
> |
VCROSS(n,v2,v0); |
841 |
> |
if(DOT(n,p) > 0.0) |
842 |
> |
continue; |
843 |
> |
|
844 |
> |
return(t_id); |
845 |
|
} |
846 |
< |
else |
729 |
< |
tri = stPoint_locate(st,pt,type,which); |
730 |
< |
return(tri); |
846 |
> |
return(INVALID); |
847 |
|
} |
848 |
|
|
849 |
< |
QUADTREE |
850 |
< |
smPointLocateCell(sm,pt,v0,v1,v2,type,which,norm) |
849 |
> |
int |
850 |
> |
smPointLocateTri(sm,p) |
851 |
|
SM *sm; |
852 |
< |
FVECT pt,v0,v1,v2; |
737 |
< |
char *type,*which; |
738 |
< |
char norm; |
852 |
> |
FVECT p; |
853 |
|
{ |
854 |
< |
STREE *st; |
855 |
< |
QUADTREE qt; |
742 |
< |
FVECT npt; |
854 |
> |
QUADTREE qt,*optr; |
855 |
> |
FVECT tpt; |
856 |
|
|
857 |
< |
st = SM_LOCATOR(sm); |
858 |
< |
if(norm) |
859 |
< |
{ |
860 |
< |
point_on_sphere(npt,pt,SM_VIEW_CENTER(sm)); |
861 |
< |
|
862 |
< |
qt = stPoint_locate_cell(st,npt,v0,v1,v2,type,which); |
863 |
< |
} |
751 |
< |
else |
752 |
< |
qt = stPoint_locate_cell(st,pt,v0,v1,v2,type,which); |
753 |
< |
|
754 |
< |
return(qt); |
857 |
> |
VSUB(tpt,p,SM_VIEW_CENTER(sm)); |
858 |
> |
qt = smPointLocateCell(sm,tpt); |
859 |
> |
if(QT_IS_EMPTY(qt)) |
860 |
> |
return(INVALID); |
861 |
> |
|
862 |
> |
optr = qtqueryset(qt); |
863 |
> |
return(smTri_in_set(sm,tpt,optr)); |
864 |
|
} |
865 |
|
|
866 |
+ |
|
867 |
+ |
/* |
868 |
+ |
Determine whether this sample should: |
869 |
+ |
a) be added to the mesh by subdividing the triangle |
870 |
+ |
b) ignored |
871 |
+ |
c) replace values of an existing mesh vertex |
872 |
+ |
|
873 |
+ |
In case a, the routine will return TRUE, for b,c will return FALSE |
874 |
+ |
In case a, also determine if this sample should cause the deletion of |
875 |
+ |
an existing vertex. If so *rptr will contain the id of the sample to delete |
876 |
+ |
after the new sample has been added. |
877 |
+ |
|
878 |
+ |
ASSUMPTION: this will not be called with a new sample that is |
879 |
+ |
a BASE point. |
880 |
+ |
|
881 |
+ |
The following tests are performed (in order) to determine the fate |
882 |
+ |
of the sample: |
883 |
+ |
|
884 |
+ |
1) If the world space point of the sample coincides with one of the |
885 |
+ |
triangle vertex samples: The values of the triangle sample are |
886 |
+ |
replaced with the new values and FALSE is returned |
887 |
+ |
2) If the new sample is close in ws, and close in the spherical projection |
888 |
+ |
to one of the triangle vertex samples: |
889 |
+ |
pick the point with dir closest to that of the canonical view |
890 |
+ |
If it is the new point: mark existing point for deletion,and return |
891 |
+ |
TRUE,else return FALSE |
892 |
+ |
3) If the spherical projection of new is < REPLACE_EPS from a base point: |
893 |
+ |
add new and mark the base for deletion: return TRUE |
894 |
+ |
4) If the addition of the new sample point would introduce a "puncture" |
895 |
+ |
or cause new triangles with large depth differences:return FALSE |
896 |
+ |
This attempts to throw out points that should be occluded |
897 |
+ |
*/ |
898 |
|
int |
899 |
< |
smAdd_sample_to_mesh(sm,c,dir,pt,s_id) |
899 |
> |
smTest_sample(sm,tri_id,c,dir,p,o_id,rptr) |
900 |
|
SM *sm; |
901 |
+ |
int tri_id; |
902 |
|
COLR c; |
903 |
< |
FVECT dir,pt; |
904 |
< |
int s_id; |
903 |
> |
FVECT dir,p; |
904 |
> |
int o_id; |
905 |
> |
int *rptr; |
906 |
|
{ |
907 |
< |
int t_id; |
908 |
< |
char type,which; |
909 |
< |
double d; |
910 |
< |
FVECT p; |
911 |
< |
|
912 |
< |
/* If new, foreground pt */ |
913 |
< |
if(pt) |
907 |
> |
TRI *tri; |
908 |
> |
double d,d2,dnear,dspt,d01,d12,d20,s0,s1,s2,ds,dv; |
909 |
> |
int vid[3],i,nearid,norm,dcnt,bcnt; |
910 |
> |
FVECT diff[3],spt,npt; |
911 |
> |
int tonemap; |
912 |
> |
|
913 |
> |
*rptr = INVALID; |
914 |
> |
bcnt = dcnt = 0; |
915 |
> |
tri = SM_NTH_TRI(sm,tri_id); |
916 |
> |
vid[0] = T_NTH_V(tri,0); |
917 |
> |
vid[1] = T_NTH_V(tri,1); |
918 |
> |
vid[2] = T_NTH_V(tri,2); |
919 |
> |
|
920 |
> |
/* TEST 1: Test if the new point has the same world space point as |
921 |
> |
one of the existing triangle vertices |
922 |
> |
*/ |
923 |
> |
for(i=0; i<3; i++) |
924 |
|
{ |
925 |
< |
/* NOTE: This should be elsewhere! */ |
926 |
< |
d = DIST(pt,SM_VIEW_CENTER(smMesh)); |
927 |
< |
smDist_sum += 1.0/d; |
928 |
< |
/************************************/ |
929 |
< |
t_id = smPointLocate(smMesh,pt,&type,&which,TRUE); |
930 |
< |
if(type==GT_FACE) |
931 |
< |
s_id = smInsert_point_in_tri(smMesh,c,dir,pt,s_id,t_id); |
932 |
< |
else |
933 |
< |
if(type==GT_VERTEX) |
934 |
< |
s_id = smReplace_vertex(smMesh,c,dir,pt,t_id,s_id,type,which); |
935 |
< |
#ifdef DEBUG |
936 |
< |
else |
937 |
< |
eputs("smAdd_sample_to_mesh(): unrecognized type\n"); |
938 |
< |
#endif |
925 |
> |
if(SM_BASE_ID(sm,vid[i])) |
926 |
> |
{ |
927 |
> |
bcnt++; |
928 |
> |
continue; |
929 |
> |
} |
930 |
> |
if(SM_DIR_ID(sm,vid[i])) |
931 |
> |
dcnt++; |
932 |
> |
VSUB(diff[i],SM_NTH_WV(sm,vid[i]),p); |
933 |
> |
/* If same world point: replace */ |
934 |
> |
if(FZERO_VEC3(diff[i])) |
935 |
> |
{ |
936 |
> |
tonemap = (SM_TONE_MAP(sm) > vid[i]); |
937 |
> |
sInit_samp(SM_SAMP(sm),vid[i],c,dir,p,o_id,tonemap); |
938 |
> |
return(FALSE); |
939 |
> |
} |
940 |
|
} |
941 |
< |
else if(s_id != -1) |
941 |
> |
if(!dir) |
942 |
> |
return(TRUE); |
943 |
> |
/* TEST 2: If the new sample is close in ws, and close in the spherical |
944 |
> |
projection to one of the triangle vertex samples |
945 |
> |
*/ |
946 |
> |
norm = FALSE; |
947 |
> |
if(bcnt + dcnt != 3) |
948 |
|
{ |
949 |
< |
VCOPY(p,SM_NTH_WV(sm,s_id)); |
950 |
< |
if(SM_NTH_W_DIR(sm,s_id) != -1) |
949 |
> |
VSUB(spt,p,SM_VIEW_CENTER(sm)); |
950 |
> |
ds = DOT(spt,spt); |
951 |
> |
dnear = FHUGE; |
952 |
> |
for(i=0; i<3; i++) |
953 |
|
{ |
954 |
< |
/* NOTE: This should be elsewhere! */ |
955 |
< |
d = DIST(p,SM_VIEW_CENTER(smMesh)); |
956 |
< |
smDist_sum += 1.0/d; |
957 |
< |
/************************************/ |
954 |
> |
if(SM_BASE_ID(sm,vid[i]) || SM_DIR_ID(sm,vid[i])) |
955 |
> |
continue; |
956 |
> |
d = DOT(diff[i],diff[i])/ds; |
957 |
> |
if(d < dnear) |
958 |
> |
{ |
959 |
> |
dnear = d; |
960 |
> |
nearid=vid[i]; |
961 |
> |
} |
962 |
|
} |
963 |
< |
t_id = smPointLocate(smMesh,p,&type,&which,TRUE); |
964 |
< |
if(type==GT_FACE) |
965 |
< |
s_id = smInsert_point_in_tri(smMesh,c,dir,p,s_id,t_id); |
966 |
< |
else |
967 |
< |
if(type==GT_VERTEX) |
968 |
< |
s_id = smReplace_vertex(smMesh,c,dir,p,t_id,s_id,type,which); |
963 |
> |
|
964 |
> |
if(dnear <= smMinSampDiff*smMinSampDiff) |
965 |
> |
{ |
966 |
> |
/* Pick the point with dir closest to that of the canonical view |
967 |
> |
if it is the new sample: mark existing point for deletion |
968 |
> |
*/ |
969 |
> |
normalize(spt); |
970 |
> |
norm = TRUE; |
971 |
> |
VSUB(npt,SM_NTH_WV(sm,nearid),SM_VIEW_CENTER(sm)); |
972 |
> |
normalize(npt); |
973 |
> |
d = fdir2diff(SM_NTH_W_DIR(sm,nearid), npt); |
974 |
> |
d2 = 2. - 2.*DOT(dir,spt); |
975 |
> |
/* The existing sample is a better sample:punt */ |
976 |
> |
if(d2 > d) |
977 |
> |
return(FALSE); |
978 |
> |
else |
979 |
> |
{ |
980 |
> |
/* The new sample is better: mark the existing one |
981 |
> |
for deletion after the new one is added*/ |
982 |
> |
*rptr = nearid; |
983 |
> |
return(TRUE); |
984 |
> |
} |
985 |
> |
} |
986 |
> |
} |
987 |
> |
/* TEST 3: If the spherical projection of new is < S_REPLACE_EPS |
988 |
> |
from a base point |
989 |
> |
*/ |
990 |
> |
if(bcnt) |
991 |
> |
{ |
992 |
> |
dnear = FHUGE; |
993 |
> |
if(bcnt + dcnt ==3) |
994 |
> |
VSUB(spt,p,SM_VIEW_CENTER(sm)); |
995 |
> |
if(!norm) |
996 |
> |
normalize(spt); |
997 |
> |
|
998 |
> |
for(i=0; i<3; i++) |
999 |
> |
{ |
1000 |
> |
if(!SM_BASE_ID(sm,vid[i])) |
1001 |
> |
continue; |
1002 |
> |
VSUB(npt,SM_NTH_WV(sm,vid[i]),SM_VIEW_CENTER(sm)); |
1003 |
> |
d = DIST_SQ(npt,spt); |
1004 |
> |
if(d < S_REPLACE_EPS && d < dnear) |
1005 |
> |
{ |
1006 |
> |
dnear = d; |
1007 |
> |
nearid = vid[i]; |
1008 |
> |
} |
1009 |
> |
} |
1010 |
> |
if(dnear != FHUGE) |
1011 |
> |
{ |
1012 |
> |
/* add new and mark the base for deletion */ |
1013 |
> |
*rptr = nearid; |
1014 |
> |
return(TRUE); |
1015 |
> |
} |
1016 |
> |
} |
1017 |
> |
|
1018 |
> |
/* TEST 4: |
1019 |
> |
If the addition of the new sample point would introduce a "puncture" |
1020 |
> |
or cause new triangles with large depth differences:dont add: |
1021 |
> |
*/ |
1022 |
> |
if(bcnt || dcnt) |
1023 |
> |
return(TRUE); |
1024 |
> |
/* If the new point is in front of the existing points- add */ |
1025 |
> |
dv = DIST_SQ(SM_NTH_WV(sm,vid[0]),SM_VIEW_CENTER(sm)); |
1026 |
> |
if(ds < dv) |
1027 |
> |
return(TRUE); |
1028 |
> |
|
1029 |
> |
d01 = DIST_SQ(SM_NTH_WV(sm,vid[1]),SM_NTH_WV(sm,vid[0])); |
1030 |
> |
s0 = DOT(diff[0],diff[0]); |
1031 |
> |
if(s0 < S_REPLACE_SCALE*d01) |
1032 |
> |
return(TRUE); |
1033 |
> |
d12 = DIST_SQ(SM_NTH_WV(sm,vid[2]),SM_NTH_WV(sm,vid[1])); |
1034 |
> |
if(s0 < S_REPLACE_SCALE*d12) |
1035 |
> |
return(TRUE); |
1036 |
> |
d20 = DIST_SQ(SM_NTH_WV(sm,vid[0]),SM_NTH_WV(sm,vid[2])); |
1037 |
> |
if(s0 < S_REPLACE_SCALE*d20) |
1038 |
> |
return(TRUE); |
1039 |
> |
d = MIN3(d01,d12,d20); |
1040 |
> |
s1 = DOT(diff[1],diff[1]); |
1041 |
> |
if(s1 < S_REPLACE_SCALE*d) |
1042 |
> |
return(TRUE); |
1043 |
> |
s2 = DOT(diff[2],diff[2]); |
1044 |
> |
if(s2 < S_REPLACE_SCALE*d) |
1045 |
> |
return(TRUE); |
1046 |
> |
|
1047 |
> |
/* TEST 5: |
1048 |
> |
Check to see if triangle is relatively large and should therefore |
1049 |
> |
be subdivided anyway. |
1050 |
> |
*/ |
1051 |
> |
dv *= DIST_SQ(SM_NTH_WV(sm,vid[1]),SM_VIEW_CENTER(sm)); |
1052 |
> |
dv *= DIST_SQ(SM_NTH_WV(sm,vid[2]),SM_VIEW_CENTER(sm)); |
1053 |
> |
if (d01*d12*d20/dv > S_REPLACE_TRI) |
1054 |
> |
return(TRUE); |
1055 |
> |
|
1056 |
> |
return(FALSE); |
1057 |
> |
} |
1058 |
> |
|
1059 |
> |
|
1060 |
> |
int |
1061 |
> |
smAlloc_samp(sm,c,dir,pt,o_id) |
1062 |
> |
SM *sm; |
1063 |
> |
COLR c; |
1064 |
> |
FVECT dir,pt; |
1065 |
> |
int o_id; |
1066 |
> |
{ |
1067 |
> |
int s_id,replaced,cnt; |
1068 |
> |
SAMP *s; |
1069 |
> |
FVECT p; |
1070 |
> |
|
1071 |
> |
s = SM_SAMP(sm); |
1072 |
> |
s_id = sAlloc_samp(s,&replaced); |
1073 |
> |
|
1074 |
> |
cnt=0; |
1075 |
> |
while(replaced) |
1076 |
> |
{ |
1077 |
> |
if(smRemoveVertex(sm,s_id)) |
1078 |
> |
break; |
1079 |
> |
s_id = sAlloc_samp(s,&replaced); |
1080 |
> |
cnt++; |
1081 |
> |
if(cnt > S_MAX_SAMP(s)) |
1082 |
> |
error(CONSISTENCY,"smAlloc_samp():unable to find free samp\n"); |
1083 |
> |
} |
1084 |
> |
|
1085 |
> |
/* If sample is being added in the middle of the sample array: tone |
1086 |
> |
map individually |
1087 |
> |
*/ |
1088 |
> |
/* Initialize sample */ |
1089 |
> |
sInit_samp(s,s_id,c,dir,pt,o_id,(SM_TONE_MAP(sm)>s_id)); |
1090 |
> |
|
1091 |
> |
return(s_id); |
1092 |
> |
} |
1093 |
> |
|
1094 |
> |
int |
1095 |
> |
smAdd_samp(sm,c,dir,p,o_id) |
1096 |
> |
SM *sm; |
1097 |
> |
COLR c; |
1098 |
> |
FVECT dir,p; |
1099 |
> |
int o_id; |
1100 |
> |
{ |
1101 |
> |
int t_id,s_id,r_id; |
1102 |
> |
double d; |
1103 |
> |
FVECT wpt; |
1104 |
> |
|
1105 |
> |
r_id = INVALID; |
1106 |
> |
/* If sample is a world space point */ |
1107 |
> |
if(p) |
1108 |
> |
{ |
1109 |
> |
t_id = smPointLocateTri(sm,p); |
1110 |
> |
if(t_id == INVALID) |
1111 |
> |
{ |
1112 |
|
#ifdef DEBUG |
1113 |
< |
else |
805 |
< |
eputs("smAdd_sample_to_mesh(): unrecognized type\n"); |
1113 |
> |
eputs("smAddSamp(): unable to locate tri containing sample \n"); |
1114 |
|
#endif |
1115 |
+ |
return(INVALID); |
1116 |
+ |
} |
1117 |
+ |
/* if not a base id, Test to see if this sample should be added */ |
1118 |
+ |
if(!SM_BASE_ID(sm,o_id)) |
1119 |
+ |
{ |
1120 |
+ |
if(!smTest_sample(sm,t_id,c,dir,p,o_id,&r_id)) |
1121 |
+ |
return(INVALID); |
1122 |
+ |
/* Allocate space for a sample and initialize */ |
1123 |
+ |
s_id = smAlloc_samp(smMesh,c,dir,p,o_id); |
1124 |
|
} |
808 |
– |
/* Is a BG(sky point) */ |
1125 |
|
else |
1126 |
< |
{ |
1127 |
< |
t_id = smPointLocate(smMesh,dir,&type,&which,FALSE); |
1128 |
< |
if(type==GT_FACE) |
1129 |
< |
s_id = smInsert_point_in_tri(smMesh,c,dir,NULL,s_id,t_id); |
1130 |
< |
else |
1131 |
< |
if(type==GT_VERTEX) |
1132 |
< |
s_id = smReplace_vertex(smMesh,c,dir,NULL,t_id,s_id,type,which); |
1126 |
> |
s_id = o_id; |
1127 |
> |
} |
1128 |
> |
/* If sample is a direction vector */ |
1129 |
> |
else |
1130 |
> |
{ |
1131 |
> |
VADD(wpt,dir,SM_VIEW_CENTER(smMesh)); |
1132 |
> |
t_id = smPointLocateTri(sm,wpt); |
1133 |
> |
if(t_id == INVALID) |
1134 |
> |
{ |
1135 |
|
#ifdef DEBUG |
1136 |
< |
else |
819 |
< |
eputs("smAdd_sample_to_mesh(): unrecognized type\n"); |
1136 |
> |
eputs("smAddSamp(): unable to locate tri containing sample \n"); |
1137 |
|
#endif |
1138 |
< |
} |
1138 |
> |
return(INVALID); |
1139 |
> |
} |
1140 |
> |
/* Test to see if this sample should be added */ |
1141 |
> |
if(!smTest_sample(sm,t_id,c,NULL,wpt,o_id,&r_id)) |
1142 |
> |
return(INVALID); |
1143 |
> |
/* Allocate space for a sample and initialize */ |
1144 |
> |
s_id = smAlloc_samp(smMesh,c,NULL,wpt,o_id); |
1145 |
> |
} |
1146 |
> |
if(!SM_BASE_ID(sm,s_id) && !SM_DIR_ID(sm,s_id)) |
1147 |
> |
{ |
1148 |
> |
/* If not a base or sky point, add distance from the |
1149 |
> |
viewcenter to average*/ |
1150 |
> |
d = DIST(SM_NTH_WV(sm,s_id),SM_VIEW_CENTER(smMesh)); |
1151 |
> |
smDist_sum += 1.0/d; |
1152 |
> |
} |
1153 |
> |
smInsert_samp(smMesh,s_id,t_id); |
1154 |
> |
|
1155 |
> |
/* If new sample replaces existing one- remove that vertex now */ |
1156 |
> |
if(r_id != INVALID) |
1157 |
> |
{ |
1158 |
> |
smRemoveVertex(sm,r_id); |
1159 |
> |
sDelete_samp(SM_SAMP(sm),r_id); |
1160 |
> |
} |
1161 |
|
return(s_id); |
1162 |
|
} |
1163 |
|
|
1177 |
|
COLR c; |
1178 |
|
FVECT dir; |
1179 |
|
FVECT p; |
841 |
– |
|
1180 |
|
{ |
1181 |
|
int s_id; |
1182 |
< |
|
1182 |
> |
|
1183 |
|
/* First check if this the first sample: if so initialize mesh */ |
1184 |
|
if(SM_NUM_SAMP(smMesh) == 0) |
1185 |
< |
#ifdef TEST_DRIVER |
1186 |
< |
smInit_mesh(smMesh,View.vp); |
1187 |
< |
#else |
1188 |
< |
smInit_mesh(smMesh,odev.v.vp); |
1189 |
< |
#endif |
1190 |
< |
s_id = smAdd_sample_to_mesh(smMesh,c,dir,p,-1); |
1191 |
< |
#if 0 |
854 |
< |
{ |
855 |
< |
char buff[100]; |
856 |
< |
sprintf(buff,"Added sample %d\n",s_id); |
857 |
< |
eputs(buff); |
858 |
< |
} |
859 |
< |
#endif |
1185 |
> |
{ |
1186 |
> |
smInit_sm(smMesh,odev.v.vp); |
1187 |
> |
sClear_all_flags(SM_SAMP(smMesh)); |
1188 |
> |
} |
1189 |
> |
/* Add the sample to the mesh */ |
1190 |
> |
s_id = smAdd_samp(smMesh,c,dir,p,INVALID); |
1191 |
> |
|
1192 |
|
return(s_id); |
1193 |
|
|
1194 |
|
} |
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 |
– |
|
1195 |
|
int |
1196 |
< |
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) |
1196 |
> |
smAdd_base_vertex(sm,v) |
1197 |
|
SM *sm; |
1198 |
< |
FVECT v,d; |
1198 |
> |
FVECT v; |
1199 |
|
{ |
1200 |
|
int id; |
1201 |
|
|
1202 |
|
/* First add coordinate to the sample array */ |
1203 |
< |
id = smAdd_aux_point(sm,v,d); |
1204 |
< |
if(id == -1) |
1205 |
< |
return(SM_INVALID); |
1203 |
> |
id = sAdd_base_point(SM_SAMP(sm),v); |
1204 |
> |
if(id == INVALID) |
1205 |
> |
return(INVALID); |
1206 |
|
/* Initialize triangle pointer to -1 */ |
1207 |
|
smClear_vert(sm,id); |
1208 |
|
return(id); |
1220 |
|
SM *sm; |
1221 |
|
int type; |
1222 |
|
{ |
1223 |
< |
int i,id; |
1223 |
> |
int i,s_id,tri_id,nbr_id; |
1224 |
|
int p[4],ids[4]; |
1225 |
|
int v0_id,v1_id,v2_id; |
1226 |
< |
TRI *tris[4]; |
937 |
< |
FVECT d,pt,cntr; |
1226 |
> |
FVECT d,pt,cntr,v0,v1,v2; |
1227 |
|
|
1228 |
|
/* First insert the base vertices into the sample point array */ |
1229 |
|
|
1230 |
|
for(i=0; i < 4; i++) |
1231 |
|
{ |
1232 |
< |
VADD(cntr,stDefault_base[i],SM_VIEW_CENTER(sm)); |
1233 |
< |
point_on_sphere(d,cntr,SM_VIEW_CENTER(sm)); |
1234 |
< |
id = smAdd_base_vertex(sm,cntr,d); |
1235 |
< |
/* test to make sure vertex allocated */ |
1236 |
< |
if(id != -1) |
1237 |
< |
p[i] = id; |
949 |
< |
else |
950 |
< |
return(0); |
1232 |
> |
VCOPY(cntr,smDefault_base[i]); |
1233 |
> |
cntr[0] += .01; |
1234 |
> |
cntr[1] += .02; |
1235 |
> |
cntr[2] += .03; |
1236 |
> |
VADD(cntr,cntr,SM_VIEW_CENTER(sm)); |
1237 |
> |
p[i] = smAdd_base_vertex(sm,cntr); |
1238 |
|
} |
1239 |
|
/* Create the base triangles */ |
1240 |
|
for(i=0;i < 4; i++) |
1241 |
|
{ |
1242 |
< |
v0_id = p[stTri_verts[i][0]]; |
1243 |
< |
v1_id = p[stTri_verts[i][1]]; |
1244 |
< |
v2_id = p[stTri_verts[i][2]]; |
1245 |
< |
if((ids[i] = smAdd_tri(sm, v0_id,v1_id,v2_id,&(tris[i])))== -1) |
1246 |
< |
return(0); |
1242 |
> |
v0_id = p[smTri_verts[i][0]]; |
1243 |
> |
v1_id = p[smTri_verts[i][1]]; |
1244 |
> |
v2_id = p[smTri_verts[i][2]]; |
1245 |
> |
ids[i] = smAdd_tri(sm, v0_id,v1_id,v2_id); |
1246 |
> |
smLocator_add_tri(sm,ids[i],v0_id,v1_id,v2_id,NULL); |
1247 |
|
} |
1248 |
+ |
|
1249 |
|
/* Set neighbors */ |
1250 |
|
|
1251 |
< |
T_NTH_NBR(tris[0],0) = ids[3]; |
1252 |
< |
T_NTH_NBR(tris[0],1) = ids[2]; |
1253 |
< |
T_NTH_NBR(tris[0],2) = ids[1]; |
1251 |
> |
for(tri_id=0;tri_id < 4; tri_id++) |
1252 |
> |
for(nbr_id=0; nbr_id < 3; nbr_id++) |
1253 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,ids[tri_id]),nbr_id) = smBase_nbrs[tri_id][nbr_id]; |
1254 |
|
|
1255 |
< |
T_NTH_NBR(tris[1],0) = ids[3]; |
1256 |
< |
T_NTH_NBR(tris[1],1) = ids[0]; |
1257 |
< |
T_NTH_NBR(tris[1],2) = ids[2]; |
1255 |
> |
/* Now add the centroids of the faces */ |
1256 |
> |
for(tri_id=0;tri_id < 4; tri_id++) |
1257 |
> |
{ |
1258 |
> |
VCOPY(v0,SM_T_NTH_WV(sm,SM_NTH_TRI(sm,ids[tri_id]),0)); |
1259 |
> |
VCOPY(v1,SM_T_NTH_WV(sm,SM_NTH_TRI(sm,ids[tri_id]),1)); |
1260 |
> |
VCOPY(v2,SM_T_NTH_WV(sm,SM_NTH_TRI(sm,ids[tri_id]),2)); |
1261 |
> |
tri_centroid(v0,v1,v2,cntr); |
1262 |
> |
VSUB(cntr,cntr,SM_VIEW_CENTER(sm)); |
1263 |
> |
normalize(cntr); |
1264 |
> |
VADD(cntr,cntr,SM_VIEW_CENTER(sm)); |
1265 |
> |
s_id = smAdd_base_vertex(sm,cntr); |
1266 |
> |
smAdd_samp(sm,NULL,NULL,cntr,s_id); |
1267 |
> |
} |
1268 |
> |
return(1); |
1269 |
|
|
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 |
– |
|
1270 |
|
} |
1271 |
|
|
1272 |
|
|
1274 |
|
smNext_tri_flag_set(sm,i,which,b) |
1275 |
|
SM *sm; |
1276 |
|
int i,which; |
1277 |
< |
char b; |
1277 |
> |
int b; |
1278 |
|
{ |
1279 |
|
|
1280 |
< |
for(; i < SM_TRI_CNT(sm);i++) |
1280 |
> |
for(; i < SM_NUM_TRI(sm);i++) |
1281 |
|
{ |
992 |
– |
if(!SM_IS_NTH_T_FLAG(sm,i,which)) |
993 |
– |
continue; |
1282 |
|
|
1283 |
+ |
if(!T_IS_VALID(SM_NTH_TRI(sm,i))) |
1284 |
+ |
continue; |
1285 |
+ |
if(!SM_IS_NTH_T_FLAG(sm,i,which)) |
1286 |
+ |
continue; |
1287 |
|
if(!b) |
1288 |
|
break; |
1289 |
|
if((b==1) && !SM_BG_TRI(sm,i)) |
1302 |
|
int i; |
1303 |
|
{ |
1304 |
|
|
1305 |
< |
while( i < SM_TRI_CNT(sm) && !T_IS_VALID(SM_NTH_TRI(sm,i))) |
1305 |
> |
while( i < SM_NUM_TRI(sm) && !T_IS_VALID(SM_NTH_TRI(sm,i))) |
1306 |
|
i++; |
1307 |
|
|
1308 |
|
return(i); |
1310 |
|
|
1311 |
|
|
1312 |
|
|
1313 |
< |
qtTri_verts_from_id(t_id,v0,v1,v2) |
1313 |
> |
qtTri_from_id(t_id,v0,v1,v2) |
1314 |
|
int t_id; |
1315 |
|
FVECT v0,v1,v2; |
1316 |
|
{ |
1317 |
|
TRI *t; |
1026 |
– |
int v0_id,v1_id,v2_id; |
1318 |
|
|
1319 |
|
t = SM_NTH_TRI(smMesh,t_id); |
1320 |
< |
v0_id = T_NTH_V(t,0); |
1321 |
< |
v1_id = T_NTH_V(t,1); |
1322 |
< |
v2_id = T_NTH_V(t,2); |
1320 |
> |
if(!T_IS_VALID(t)) |
1321 |
> |
return(0); |
1322 |
> |
VSUB(v0,SM_T_NTH_WV(smMesh,t,0),SM_VIEW_CENTER(smMesh)); |
1323 |
> |
VSUB(v1,SM_T_NTH_WV(smMesh,t,1),SM_VIEW_CENTER(smMesh)); |
1324 |
> |
VSUB(v2,SM_T_NTH_WV(smMesh,t,2),SM_VIEW_CENTER(smMesh)); |
1325 |
> |
return(1); |
1326 |
> |
} |
1327 |
|
|
1033 |
– |
smDir(smMesh,v0,v0_id); |
1034 |
– |
smDir(smMesh,v1,v1_id); |
1035 |
– |
smDir(smMesh,v2,v2_id); |
1328 |
|
|
1329 |
< |
} |
1329 |
> |
smRebuild_mesh(sm,v) |
1330 |
> |
SM *sm; |
1331 |
> |
VIEW *v; |
1332 |
> |
{ |
1333 |
> |
int i,j,cnt; |
1334 |
> |
FVECT p,ov,dir; |
1335 |
> |
double d; |
1336 |
|
|
1337 |
+ |
#ifdef DEBUG |
1338 |
+ |
eputs("smRebuild_mesh(): rebuilding...."); |
1339 |
+ |
#endif |
1340 |
+ |
/* Clear the mesh- and rebuild using the current sample array */ |
1341 |
+ |
/* Remember the current number of samples */ |
1342 |
+ |
cnt = SM_NUM_SAMP(sm); |
1343 |
+ |
/* Calculate the difference between the current and new viewpoint*/ |
1344 |
+ |
/* Will need to subtract this off of sky points */ |
1345 |
+ |
VCOPY(ov,SM_VIEW_CENTER(sm)); |
1346 |
+ |
/* Initialize the mesh to 0 samples and the base triangles */ |
1347 |
|
|
1348 |
+ |
/* Go through all samples and add in if in the new view frustum, and |
1349 |
+ |
the dir is <= 30 degrees from new view |
1350 |
+ |
*/ |
1351 |
+ |
smInit_sm(sm,v->vp); |
1352 |
+ |
for(i=0; i < cnt; i++) |
1353 |
+ |
{ |
1354 |
+ |
/* First check if sample visible(conservative approx: if one of tris |
1355 |
+ |
attached to sample is in frustum) */ |
1356 |
+ |
if(!S_IS_FLAG(i)) |
1357 |
+ |
continue; |
1358 |
+ |
|
1359 |
+ |
/* Next test if direction > 30 from current direction */ |
1360 |
+ |
if(SM_NTH_W_DIR(sm,i)!=-1) |
1361 |
+ |
{ |
1362 |
+ |
VSUB(p,SM_NTH_WV(sm,i),v->vp); |
1363 |
+ |
normalize(p); |
1364 |
+ |
decodedir(dir,SM_NTH_W_DIR(sm,i)); |
1365 |
+ |
d = 2. - 2.*DOT(dir,p); |
1366 |
+ |
if (d > MAXDIFF2) |
1367 |
+ |
continue; |
1368 |
+ |
VCOPY(p,SM_NTH_WV(sm,i)); |
1369 |
+ |
smAdd_samp(sm,NULL,dir,p,i); |
1370 |
+ |
} |
1371 |
+ |
else |
1372 |
+ |
{ |
1373 |
+ |
VSUB(dir,SM_NTH_WV(sm,i),ov); |
1374 |
+ |
smAdd_samp(sm,NULL,dir,NULL,i); |
1375 |
+ |
} |
1376 |
+ |
|
1377 |
+ |
} |
1378 |
+ |
smNew_tri_cnt = SM_SAMPLE_TRIS(sm); |
1379 |
+ |
#ifdef DEBUG |
1380 |
+ |
eputs("smRebuild_mesh():done\n"); |
1381 |
+ |
#endif |
1382 |
+ |
} |
1383 |
+ |
|
1384 |
|
int |
1385 |
< |
smIntersectTriSet(sm,t_set,orig,dir,pt) |
1042 |
< |
SM *sm; |
1385 |
> |
intersect_tri_set(t_set,orig,dir,pt) |
1386 |
|
OBJECT *t_set; |
1387 |
|
FVECT orig,dir,pt; |
1388 |
|
{ |
1389 |
|
OBJECT *optr; |
1390 |
< |
int i,t_id,v_id; |
1391 |
< |
TRI *tri; |
1392 |
< |
FVECT p0,p1,p2; |
1393 |
< |
char type,which; |
1051 |
< |
int p0_id,p1_id,p2_id; |
1390 |
> |
int i,t_id,id; |
1391 |
> |
int pid0,pid1,pid2; |
1392 |
> |
FVECT p0,p1,p2,p; |
1393 |
> |
TRI *t; |
1394 |
|
|
1395 |
< |
for(optr = QT_SET_PTR(t_set),i = QT_SET_CNT(t_set); i > 0; i--) |
1395 |
> |
optr = QT_SET_PTR(t_set); |
1396 |
> |
for(i = QT_SET_CNT(t_set); i > 0; i--) |
1397 |
|
{ |
1398 |
|
t_id = QT_SET_NEXT_ELEM(optr); |
1399 |
< |
tri = SM_NTH_TRI(sm,t_id); |
1400 |
< |
p0_id = T_NTH_V(tri,0); |
1401 |
< |
p1_id = T_NTH_V(tri,1); |
1402 |
< |
p2_id = T_NTH_V(tri,2); |
1403 |
< |
VCOPY(p0,SM_NTH_WV(sm,p0_id)); |
1404 |
< |
VCOPY(p1,SM_NTH_WV(sm,p1_id)); |
1405 |
< |
VCOPY(p2,SM_NTH_WV(sm,p2_id)); |
1406 |
< |
if(type = ray_intersect_tri(orig,dir,p0,p1,p2,pt,&which)) |
1399 |
> |
if(SM_IS_NTH_T_BASE(smMesh,t_id)) |
1400 |
> |
continue; |
1401 |
> |
t = SM_NTH_TRI(smMesh,t_id); |
1402 |
> |
if(!T_IS_VALID(t)) |
1403 |
> |
continue; |
1404 |
> |
pid0 = T_NTH_V(t,0); |
1405 |
> |
pid1 = T_NTH_V(t,1); |
1406 |
> |
pid2 = T_NTH_V(t,2); |
1407 |
> |
VCOPY(p0,SM_NTH_WV(smMesh,pid0)); |
1408 |
> |
VCOPY(p1,SM_NTH_WV(smMesh,pid1)); |
1409 |
> |
VCOPY(p2,SM_NTH_WV(smMesh,pid2)); |
1410 |
> |
if(ray_intersect_tri(orig,dir,p0,p1,p2,p)) |
1411 |
|
{ |
1412 |
< |
if(type==GT_VERTEX) |
1413 |
< |
return(T_NTH_V(tri,which)); |
1414 |
< |
v_id = smClosest_vertex_in_w_tri(sm,p0_id,p1_id,p2_id,pt); |
1415 |
< |
return(v_id); |
1412 |
> |
id = closest_point_in_tri(p0,p1,p2,p,pid0,pid1,pid2); |
1413 |
> |
|
1414 |
> |
if(pt) |
1415 |
> |
VCOPY(pt,p); |
1416 |
> |
#ifdef DEBUG_TEST_DRIVER |
1417 |
> |
Pick_tri = t_id; |
1418 |
> |
Pick_samp = id; |
1419 |
> |
VCOPY(Pick_point[0],p); |
1420 |
> |
#endif |
1421 |
> |
return(id); |
1422 |
|
} |
1423 |
|
} |
1424 |
|
return(-1); |
1425 |
|
} |
1426 |
|
|
1427 |
< |
/* |
1428 |
< |
* int |
1429 |
< |
* 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; |
1427 |
> |
/* OS is constrained to be <= QT_MAXCSET : if the set exceeds this, the |
1428 |
> |
results of check_set are conservative |
1429 |
> |
*/ |
1430 |
|
|
1431 |
< |
/* Find the plane equation for the triangle defined by the edge v0v1 and |
1432 |
< |
the view center*/ |
1433 |
< |
VCROSS(n,v0,v1); |
1434 |
< |
/* Intersect the ray with this plane */ |
1435 |
< |
i = intersect_ray_plane(orig,dir,n,0.0,&(pt[0]),p[0]); |
1436 |
< |
if(i) |
1437 |
< |
which = 0; |
1438 |
< |
else |
1439 |
< |
which = -1; |
1440 |
< |
|
1441 |
< |
VCROSS(n,v1,v2); |
1442 |
< |
i = intersect_ray_plane(orig,dir,n,0.0,&(pt[1]),p[1]); |
1443 |
< |
if(i) |
1444 |
< |
if((which==-1) || pt[1] < pt[0]) |
1445 |
< |
which = 1; |
1446 |
< |
|
1447 |
< |
VCROSS(n,v2,v0); |
1448 |
< |
i = intersect_ray_plane(orig,dir,n,0.0,&(pt[2]),p[2]); |
1449 |
< |
if(i) |
1450 |
< |
if((which==-1) || pt[2] < pt[which]) |
1451 |
< |
which = 2; |
1452 |
< |
|
1453 |
< |
if(which != -1) |
1454 |
< |
{ |
1455 |
< |
/* Return point that is K*eps along projection of the ray on |
1456 |
< |
the sphere to push intersection point p[which] into next cell |
1457 |
< |
*/ |
1458 |
< |
normalize(p[which]); |
1459 |
< |
/* Calculate the ray perpendicular to the intersection point: approx |
1460 |
< |
the direction moved along the sphere a distance of K*epsilon*/ |
1461 |
< |
r_eps = -DOT(p[which],dir); |
1462 |
< |
VSUM(n,dir,p[which],r_eps); |
1463 |
< |
/* Calculate the length along ray p[which]-dir needed to move to |
1464 |
< |
cause a move along the sphere of k*epsilon |
1465 |
< |
*/ |
1466 |
< |
r_eps = DOT(n,dir); |
1467 |
< |
VSUM(r,p[which],dir,(20*FTINY)/r_eps); |
1468 |
< |
normalize(r); |
1469 |
< |
return(TRUE); |
1470 |
< |
} |
1471 |
< |
else |
1472 |
< |
{ |
1473 |
< |
/* Unable to find intersection: move along ray and try again */ |
1474 |
< |
r_eps = -DOT(orig,dir); |
1475 |
< |
VSUM(n,dir,orig,r_eps); |
1476 |
< |
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 |
< |
} |
1431 |
> |
ray_trace_check_set(qtptr,fptr,argptr) |
1432 |
> |
QUADTREE *qtptr; |
1433 |
> |
int *fptr; |
1434 |
> |
RT_ARGS *argptr; |
1435 |
> |
{ |
1436 |
> |
OBJECT tset[QT_MAXSET+1],*tptr; |
1437 |
> |
double dt,t; |
1438 |
> |
int found; |
1439 |
> |
|
1440 |
> |
if(QT_LEAF_IS_FLAG(*qtptr)) |
1441 |
> |
{ |
1442 |
> |
QT_FLAG_SET_DONE(*fptr); |
1443 |
> |
#if DEBUG |
1444 |
> |
eputs("ray_trace_check_set():Already visited this node:aborting\n"); |
1445 |
> |
#endif |
1446 |
> |
return; |
1447 |
> |
} |
1448 |
> |
if(!QT_IS_EMPTY(*qtptr)) |
1449 |
> |
{ |
1450 |
> |
tptr = qtqueryset(*qtptr); |
1451 |
> |
if(QT_SET_CNT(tptr) > QT_MAXSET) |
1452 |
> |
tptr = (OBJECT *)malloc((QT_SET_CNT(tptr)+1)*sizeof(OBJECT)); |
1453 |
> |
else |
1454 |
> |
tptr = tset; |
1455 |
> |
if(!tptr) |
1456 |
> |
goto memerr; |
1457 |
> |
|
1458 |
> |
qtgetset(tptr,*qtptr); |
1459 |
> |
/* Check triangles in set against those seen so far(os):only |
1460 |
> |
check new triangles for intersection (t_set') |
1461 |
> |
*/ |
1462 |
> |
check_set_large(tptr,argptr->os); |
1463 |
> |
if((found = intersect_tri_set(tptr,argptr->orig,argptr->dir,NULL))!= -1) |
1464 |
> |
{ |
1465 |
> |
argptr->t_id = found; |
1466 |
> |
if(tptr != tset) |
1467 |
> |
free(tptr); |
1468 |
> |
QT_FLAG_SET_DONE(*fptr); |
1469 |
> |
return; |
1470 |
> |
} |
1471 |
> |
if(tptr != tset) |
1472 |
> |
free(tptr); |
1473 |
> |
} |
1474 |
> |
return; |
1475 |
> |
memerr: |
1476 |
> |
error(SYSTEM,"ray_trace_check_set():Unable to allocate memory"); |
1477 |
|
} |
1478 |
|
|
1479 |
|
|
1484 |
|
* Find the closest sample to the given ray. Returns sample id, -1 on failure. |
1485 |
|
* "dir" is assumed to be normalized |
1486 |
|
*/ |
1487 |
+ |
|
1488 |
|
int |
1489 |
|
smFindSamp(orig,dir) |
1490 |
|
FVECT orig,dir; |
1491 |
|
{ |
1492 |
< |
FVECT r,v0,v1,v2,a,b,p; |
1493 |
< |
OBJECT os[MAXCSET+1],t_set[MAXSET+1]; |
1492 |
> |
FVECT b,p,o; |
1493 |
> |
OBJECT *ts; |
1494 |
|
QUADTREE qt; |
1495 |
|
int s_id; |
1496 |
|
double d; |
1510 |
|
either case, do a single test against the cell containing the |
1511 |
|
intersection of "dir" and the sphere |
1512 |
|
*/ |
1513 |
+ |
/* orig will be updated-so preserve original value */ |
1514 |
+ |
if(!smMesh) |
1515 |
+ |
return; |
1516 |
+ |
#ifdef TEST_DRIVER |
1517 |
+ |
Picking= TRUE; |
1518 |
+ |
#endif |
1519 |
|
point_on_sphere(b,orig,SM_VIEW_CENTER(smMesh)); |
1520 |
|
d = -DOT(b,dir); |
1521 |
|
if(EQUAL_VEC3(orig,SM_VIEW_CENTER(smMesh)) || EQUAL(fabs(d),1.0)) |
1522 |
|
{ |
1523 |
< |
qt = smPointLocateCell(smMesh,dir,v0,v1,v2,NULL,NULL,FALSE); |
1523 |
> |
qt = smPointLocateCell(smMesh,dir); |
1524 |
|
/* Test triangles in the set for intersection with Ray:returns |
1525 |
|
first found |
1526 |
|
*/ |
1527 |
< |
qtgetset(t_set,qt); |
1528 |
< |
s_id = smIntersectTriSet(smMesh,t_set,orig,dir,p); |
1529 |
< |
#ifdef TEST_DRIVER |
1527 |
> |
#ifdef DEBUG |
1528 |
> |
if(QT_IS_EMPTY(qt)) |
1529 |
> |
{ |
1530 |
> |
eputs("smFindSamp(): point not found"); |
1531 |
> |
return; |
1532 |
> |
} |
1533 |
> |
#endif |
1534 |
> |
ts = qtqueryset(qt); |
1535 |
> |
s_id = intersect_tri_set(ts,orig,dir,p); |
1536 |
> |
#ifdef DEBUG_TEST_DRIVER |
1537 |
|
VCOPY(Pick_point[0],p); |
1538 |
|
#endif |
1196 |
– |
return(s_id); |
1539 |
|
} |
1540 |
|
else |
1541 |
|
{ |
1542 |
< |
/* Starting with orig, Walk along projection of ray onto sphere */ |
1543 |
< |
point_on_sphere(r,orig,SM_VIEW_CENTER(smMesh)); |
1202 |
< |
qt = smPointLocateCell(smMesh,r,v0,v1,v2,NULL,NULL,FALSE); |
1203 |
< |
qtgetset(t_set,qt); |
1204 |
< |
/* os will contain all triangles seen thus far */ |
1205 |
< |
setcopy(os,t_set); |
1542 |
> |
OBJECT t_set[QT_MAXCSET + 1]; |
1543 |
> |
RT_ARGS rt; |
1544 |
|
|
1545 |
< |
/* Calculate ray perpendicular to dir: when projection ray is // to dir, |
1546 |
< |
the dot product will become negative. |
1547 |
< |
*/ |
1548 |
< |
VSUM(a,b,dir,d); |
1549 |
< |
d = DOT(a,b); |
1550 |
< |
while(d > 0) |
1551 |
< |
{ |
1552 |
< |
s_id = smIntersectTriSet(smMesh,t_set,orig,dir,p); |
1553 |
< |
#ifdef TEST_DRIVER |
1554 |
< |
VCOPY(Pick_point[0],p); |
1555 |
< |
#endif |
1556 |
< |
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 |
< |
qt = smPointLocateCell(smMesh,r,v0,v1,v2,NULL,NULL,FALSE); |
1223 |
< |
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); |
1545 |
> |
/* Test each of the root triangles against point id */ |
1546 |
> |
QT_CLEAR_SET(t_set); |
1547 |
> |
VSUB(o,orig,SM_VIEW_CENTER(smMesh)); |
1548 |
> |
ST_CLEAR_FLAGS(SM_LOCATOR(smMesh)); |
1549 |
> |
rt.t_id = -1; |
1550 |
> |
rt.os = t_set; |
1551 |
> |
VCOPY(rt.orig,orig); |
1552 |
> |
VCOPY(rt.dir,dir); |
1553 |
> |
stTrace_ray(SM_LOCATOR(smMesh),o,dir,ray_trace_check_set,&rt); |
1554 |
> |
s_id = rt.t_id; |
1555 |
> |
} |
1556 |
> |
return(s_id); |
1557 |
|
} |
1236 |
– |
|
1558 |
|
|
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; |
1559 |
|
|
1247 |
– |
/* Clear the mesh- and rebuild using the current sample array */ |
1248 |
– |
#ifdef TEST_DRIVER |
1249 |
– |
View = *vptr; |
1250 |
– |
#endif |
1560 |
|
|
1561 |
< |
VSUB(ov,vptr->vp,SM_VIEW_CENTER(sm)); |
1562 |
< |
smInit_mesh(sm,vptr->vp); |
1563 |
< |
|
1564 |
< |
SM_FOR_ALL_SAMPLES(sm,i) |
1565 |
< |
{ |
1566 |
< |
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 |
< |
} |
1561 |
> |
|
1562 |
> |
|
1563 |
> |
|
1564 |
> |
|
1565 |
> |
|
1566 |
> |
|
1567 |
|
|
1568 |
|
|