1 |
/* Copyright (c) 1998 Silicon Graphics, Inc. */ |
2 |
|
3 |
#ifndef lint |
4 |
static char SCCSid[] = "$SunId$ SGI"; |
5 |
#endif |
6 |
|
7 |
/* |
8 |
* sm.c |
9 |
*/ |
10 |
#include "standard.h" |
11 |
#include "sm_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 = 4.25e-4; /* min edge length in radians */ |
23 |
|
24 |
/* Each edge extends .5536 radians - 31.72 degrees */ |
25 |
static FVECT icosa_verts[162] = |
26 |
{{-0.018096,0.495400,0.868477},{0.018614,-0.554780,0.831789}, |
27 |
{0.850436,0.011329,0.525956},{0.850116,0.048016,-0.524402}, |
28 |
{-0.850116,-0.048016,0.524402},{-0.850436,-0.011329,-0.525956}, |
29 |
{0.495955,0.867825,0.030147},{-0.555329,0.831118,0.029186}, |
30 |
{0.555329,-0.831118,-0.029186},{-0.495955,-0.867825,-0.030147}, |
31 |
{-0.018614,0.554780,-0.831789},{0.018096,-0.495400,-0.868477}, |
32 |
{0.000305,-0.034906,0.999391},{0.489330,0.297837,0.819664}, |
33 |
{0.510900,-0.319418,0.798094},{-0.488835,-0.354308,0.797186}, |
34 |
{-0.510409,0.262947,0.818744},{0.999391,0.034875,0.000914}, |
35 |
{0.791335,0.516672,0.326862},{0.791142,0.538234,-0.290513}, |
36 |
{0.826031,-0.460219,-0.325378},{0.826216,-0.481780,0.291985}, |
37 |
{-0.999391,-0.034875,-0.000914},{-0.826216,0.481780,-0.291985}, |
38 |
{-0.826031,0.460219,0.325378},{-0.791142,-0.538234,0.290513}, |
39 |
{-0.791335,-0.516672,-0.326862},{-0.034911,0.998782,0.034881}, |
40 |
{0.280899,0.801316,0.528194},{-0.337075,0.779739,0.527624}, |
41 |
{-0.337377,0.814637,-0.471746},{0.280592,0.836213,-0.471186}, |
42 |
{0.034911,-0.998782,-0.034881},{-0.280592,-0.836213,0.471186}, |
43 |
{0.337377,-0.814637,0.471746},{0.337075,-0.779739,-0.527624}, |
44 |
{-0.280899,-0.801316,-0.528194},{-0.000305,0.034906,-0.999391}, |
45 |
{0.510409,-0.262947,-0.818744},{0.488835,0.354308,-0.797186}, |
46 |
{-0.510900,0.319418,-0.798094},{-0.489330,-0.297837,-0.819664}, |
47 |
{0.009834,-0.306509,0.951817},{0.268764,-0.186284,0.945021}, |
48 |
{0.275239,-0.454405,0.847207},{-0.009247,0.239357,0.970888}, |
49 |
{0.244947,0.412323,0.877491},{0.257423,0.138235,0.956360}, |
50 |
{0.525850,-0.011345,0.850502},{0.696394,0.160701,0.699436}, |
51 |
{0.707604,-0.160141,0.688223},{-0.268186,0.119892,0.955878}, |
52 |
{-0.274715,0.394186,0.877011},{-0.244420,-0.472542,0.846737}, |
53 |
{-0.256843,-0.204627,0.944542},{-0.525332,-0.048031,0.849541}, |
54 |
{-0.695970,-0.209123,0.686945},{-0.707182,0.111718,0.698149}, |
55 |
{0.961307,0.043084,-0.272090},{0.941300,0.301289,-0.152245}, |
56 |
{0.853076,0.304715,-0.423568},{0.961473,0.024015,0.273848}, |
57 |
{0.853344,0.274439,0.443269},{0.941400,0.289953,0.172315}, |
58 |
{0.831918,0.554570,0.019109},{0.669103,0.719629,0.185565}, |
59 |
{0.669003,0.730836,-0.135332},{0.959736,-0.234941,0.153979}, |
60 |
{0.871472,-0.244526,0.425140},{0.871210,-0.214250,-0.441690}, |
61 |
{0.959638,-0.223606,-0.170573},{0.868594,-0.495213,-0.017555}, |
62 |
{0.717997,-0.671205,-0.184294},{0.718092,-0.682411,0.136596}, |
63 |
{-0.961307,-0.043084,0.272090},{-0.959638,0.223606,0.170573}, |
64 |
{-0.871210,0.214250,0.441690},{-0.961473,-0.024015,-0.273848}, |
65 |
{-0.871472,0.244526,-0.425140},{-0.959736,0.234941,-0.153979}, |
66 |
{-0.868594,0.495213,0.017555},{-0.718092,0.682411,-0.136596}, |
67 |
{-0.717997,0.671205,0.184294},{-0.941400,-0.289953,-0.172315}, |
68 |
{-0.853344,-0.274439,-0.443269},{-0.853076,-0.304715,0.423568}, |
69 |
{-0.941300,-0.301289,0.152245},{-0.831918,-0.554570,-0.019109}, |
70 |
{-0.669003,-0.730836,0.135332},{-0.669103,-0.719629,-0.185565}, |
71 |
{-0.306809,0.951188,0.033302},{-0.195568,0.935038,0.295731}, |
72 |
{-0.463858,0.837300,0.289421},{0.239653,0.970270,0.033802}, |
73 |
{0.403798,0.867595,0.290218},{0.129326,0.946383,0.296031}, |
74 |
{-0.029535,0.831255,0.555106},{0.136603,0.674019,0.725974}, |
75 |
{-0.184614,0.662804,0.725678},{0.129164,0.964728,-0.229382}, |
76 |
{0.403637,0.885733,-0.229245},{-0.464015,0.855438,-0.230036}, |
77 |
{-0.195726,0.953383,-0.229677},{-0.029855,0.867949,-0.495755}, |
78 |
{-0.185040,0.711807,-0.677562},{0.136173,0.723022,-0.677271}, |
79 |
{0.306809,-0.951188,-0.033302},{0.195726,-0.953383,0.229677}, |
80 |
{0.464015,-0.855438,0.230036},{-0.239653,-0.970270,-0.033802}, |
81 |
{-0.403637,-0.885733,0.229245},{-0.129164,-0.964728,0.229382}, |
82 |
{0.029855,-0.867949,0.495755},{-0.136173,-0.723022,0.677271}, |
83 |
{0.185040,-0.711807,0.677562},{-0.129326,-0.946383,-0.296031}, |
84 |
{-0.403798,-0.867595,-0.290218},{0.463858,-0.837300,-0.289421} |
85 |
,{0.195568,-0.935038,-0.295731},{0.029535,-0.831255,-0.555106}, |
86 |
{0.184614,-0.662804,-0.725678},{-0.136603,-0.674019,-0.725974}, |
87 |
{-0.009834,0.306509,-0.951817},{0.256843,0.204627,-0.944542}, |
88 |
{0.244420,0.472542,-0.846737},{0.009247,-0.239357,-0.970888}, |
89 |
{0.274715,-0.394186,-0.877011},{0.268186,-0.119892,-0.955878}, |
90 |
{0.525332,0.048031,-0.849541},{0.707182,-0.111718,-0.698149}, |
91 |
{0.695970,0.209123,-0.686945},{-0.257423,-0.138235,-0.956360}, |
92 |
{-0.244947,-0.412323,-0.877491},{-0.275239,0.454405,-0.847207}, |
93 |
{-0.268764,0.186284,-0.945021},{-0.525850,0.011345,-0.850502}, |
94 |
{-0.707604,0.160141,-0.688223},{-0.696394,-0.160701,-0.699436}, |
95 |
{0.563717,0.692920,0.449538},{0.673284,0.428212,0.602763}, |
96 |
{0.404929,0.577853,0.708603},{0.445959,-0.596198,0.667584}, |
97 |
{0.702960,-0.421213,0.573086},{0.611746,-0.681577,0.401523}, |
98 |
{-0.445543,0.548166,0.707818},{-0.702606,0.380190,0.601498}, |
99 |
{-0.611490,0.651895,0.448456},{-0.563454,-0.722602,0.400456}, |
100 |
{-0.672921,-0.469235,0.571835},{-0.404507,-0.625886,0.666814}, |
101 |
{0.404507,0.625886,-0.666814},{0.672921,0.469235,-0.571835}, |
102 |
{0.563454,0.722602,-0.400456},{0.611490,-0.651895,-0.448456}, |
103 |
{0.702606,-0.380190,-0.601498},{0.445543,-0.548166,-0.707818}, |
104 |
{-0.611746,0.681577,-0.401523},{-0.702960,0.421213,-0.573086}, |
105 |
{-0.445959,0.596198,-0.667584},{-0.404929,-0.577853,-0.708603}, |
106 |
{-0.673284,-0.428212,-0.602763},{-0.563717,-0.692920,-0.449538}}; |
107 |
static int icosa_tris[320][3] = |
108 |
{ {1,42,44},{42,12,43},{44,43,14},{42,43,44},{12,45,47},{45,0,46},{47,46,13}, |
109 |
{45,46,47},{14,48,50},{48,13,49},{50,49,2},{48,49,50},{12,47,43},{47,13,48}, |
110 |
{43,48,14},{47,48,43},{0,45,52},{45,12,51},{52,51,16},{45,51,52},{12,42,54}, |
111 |
{42,1,53},{54,53,15},{42,53,54},{16,55,57},{55,15,56},{57,56,4},{55,56,57}, |
112 |
{12,54,51},{54,15,55},{51,55,16},{54,55,51},{3,58,60},{58,17,59},{60,59,19}, |
113 |
{58,59,60},{17,61,63},{61,2,62},{63,62,18},{61,62,63},{19,64,66},{64,18,65}, |
114 |
{66,65,6},{64,65,66},{17,63,59},{63,18,64},{59,64,19},{63,64,59},{2,61,68}, |
115 |
{61,17,67},{68,67,21},{61,67,68},{17,58,70},{58,3,69},{70,69,20},{58,69,70}, |
116 |
{21,71,73},{71,20,72},{73,72,8},{71,72,73},{17,70,67},{70,20,71},{67,71,21}, |
117 |
{70,71,67},{4,74,76},{74,22,75},{76,75,24},{74,75,76},{22,77,79},{77,5,78}, |
118 |
{79,78,23},{77,78,79},{24,80,82},{80,23,81},{82,81,7},{80,81,82},{22,79,75}, |
119 |
{79,23,80},{75,80,24},{79,80,75},{5,77,84},{77,22,83},{84,83,26},{77,83,84}, |
120 |
{22,74,86},{74,4,85},{86,85,25},{74,85,86},{26,87,89},{87,25,88},{89,88,9}, |
121 |
{87,88,89},{22,86,83},{86,25,87},{83,87,26},{86,87,83},{7,90,92},{90,27,91}, |
122 |
{92,91,29},{90,91,92},{27,93,95},{93,6,94},{95,94,28},{93,94,95},{29,96,98}, |
123 |
{96,28,97},{98,97,0},{96,97,98},{27,95,91},{95,28,96},{91,96,29},{95,96,91}, |
124 |
{6,93,100},{93,27,99},{100,99,31},{93,99,100},{27,90,102},{90,7,101}, |
125 |
{102,101,30},{90,101,102},{31,103,105},{103,30,104},{105,104,10},{103,104,105}, |
126 |
{27,102,99},{102,30,103},{99,103,31},{102,103,99},{8,106,108},{106,32,107}, |
127 |
{108,107,34},{106,107,108},{32,109,111},{109,9,110},{111,110,33},{109,110,111}, |
128 |
{34,112,114},{112,33,113},{114,113,1},{112,113,114},{32,111,107},{111,33,112}, |
129 |
{107,112,34},{111,112,107},{9,109,116},{109,32,115},{116,115,36},{109,115,116}, |
130 |
{32,106,118},{106,8,117},{118,117,35},{106,117,118},{36,119,121},{119,35,120}, |
131 |
{121,120,11},{119,120,121},{32,118,115},{118,35,119},{115,119,36},{118,119,115}, |
132 |
{10,122,124},{122,37,123},{124,123,39},{122,123,124},{37,125,127},{125,11,126}, |
133 |
{127,126,38},{125,126,127},{39,128,130},{128,38,129},{130,129,3},{128,129,130}, |
134 |
{37,127,123},{127,38,128},{123,128,39},{127,128,123},{11,125,132},{125,37,131}, |
135 |
{132,131,41},{125,131,132},{37,122,134},{122,10,133},{134,133,40},{122,133,134}, |
136 |
{41,135,137},{135,40,136},{137,136,5},{135,136,137},{37,134,131},{134,40,135}, |
137 |
{131,135,41},{134,135,131},{6,65,94},{65,18,138},{94,138,28},{65,138,94}, |
138 |
{18,62,139},{62,2,49},{139,49,13},{62,49,139},{28,140,97},{140,13,46},{97,46,0}, |
139 |
{140,46,97},{18,139,138},{139,13,140},{138,140,28},{139,140,138},{1,44,114}, |
140 |
{44,14,141},{114,141,34},{44,141,114},{14,50,142},{50,2,68},{142,68,21}, |
141 |
{50,68,142},{34,143,108},{143,21,73},{108,73,8},{143,73,108},{14,142,141}, |
142 |
{142,21,143},{141,143,34},{142,143,141},{0,52,98},{52,16,144},{98,144,29}, |
143 |
{52,144,98},{16,57,145},{57,4,76},{145,76,24},{57,76,145},{29,146,92}, |
144 |
{146,24,82},{92,82,7},{146,82,92},{16,145,144},{145,24,146},{144,146,29}, |
145 |
{145,146,144},{9,88,110},{88,25,147},{110,147,33},{88,147,110},{25,85,148}, |
146 |
{85,4,56},{148,56,15},{85,56,148},{33,149,113},{149,15,53},{113,53,1}, |
147 |
{149,53,113},{25,148,147},{148,15,149},{147,149,33},{148,149,147},{10,124,105}, |
148 |
{124,39,150},{105,150,31},{124,150,105},{39,130,151},{130,3,60},{151,60,19}, |
149 |
{130,60,151},{31,152,100},{152,19,66},{100,66,6},{152,66,100},{39,151,150}, |
150 |
{151,19,152},{150,152,31},{151,152,150},{8,72,117},{72,20,153},{117,153,35}, |
151 |
{72,153,117},{20,69,154},{69,3,129},{154,129,38},{69,129,154},{35,155,120}, |
152 |
{155,38,126},{120,126,11},{155,126,120},{20,154,153},{154,38,155},{153,155,35}, |
153 |
{154,155,153},{7,81,101},{81,23,156},{101,156,30},{81,156,101},{23,78,157}, |
154 |
{78,5,136},{157,136,40},{78,136,157},{30,158,104},{158,40,133},{104,133,10}, |
155 |
{158,133,104},{23,157,156},{157,40,158},{156,158,30},{157,158,156},{11,132,121}, |
156 |
{132,41,159},{121,159,36},{132,159,121},{41,137,160},{137,5,84},{160,84,26}, |
157 |
{137,84,160},{36,161,116},{161,26,89},{116,89,9},{161,89,116},{41,160,159}, |
158 |
{160,26,161},{159,161,36},{160,161,159}}; |
159 |
static int icosa_nbrs[320][3] = |
160 |
{{3,208,21},{12,3,20},{14,209,3},{2,0,1},{7,12,17},{202,7,16},{201,13,7}, |
161 |
{6,4,5},{11,212,14},{198,11,13},{197,213,11},{10,8,9},{15,1,4},{9,15,6}, |
162 |
{8,2,15},{14,12,13},{19,224,5},{28,19,4},{30,225,19},{18,16,17},{23,28,1}, |
163 |
{250,23,0},{249,29,23},{22,20,21},{27,228,30},{246,27,29},{245,229,27}, |
164 |
{26,24,25},{31,17,20},{25,31,22},{24,18,31},{30,28,29},{35,261,53},{44,35,52}, |
165 |
{46,262,35},{34,32,33},{39,44,49},{197,39,48},{196,45,39},{38,36,37}, |
166 |
{43,265,46},{193,43,45},{192,266,43},{42,40,41},{47,33,36},{41,47,38}, |
167 |
{40,34,47},{46,44,45},{51,213,37},{60,51,36},{62,214,51},{50,48,49},{55,60,33}, |
168 |
{277,55,32},{276,61,55},{54,52,53},{59,217,62},{273,59,61},{272,218,59}, |
169 |
{58,56,57},{63,49,52},{57,63,54},{56,50,63},{62,60,61},{67,229,85},{76,67,84}, |
170 |
{78,230,67},{66,64,65},{71,76,81},{293,71,80},{292,77,71},{70,68,69}, |
171 |
{75,233,78},{289,75,77},{288,234,75},{74,72,73},{79,65,68},{73,79,70}, |
172 |
{72,66,79},{78,76,77},{83,309,69},{92,83,68},{94,310,83},{82,80,81},{87,92,65}, |
173 |
{245,87,64},{244,93,87},{86,84,85},{91,313,94},{241,91,93},{240,314,91}, |
174 |
{90,88,89},{95,81,84},{89,95,86},{88,82,95},{94,92,93},{99,234,117}, |
175 |
{108,99,116},{110,232,99},{98,96,97},{103,108,113},{192,103,112},{194,109,103}, |
176 |
{102,100,101},{107,226,110},{200,107,109},{202,224,107},{106,104,105}, |
177 |
{111,97,100},{105,111,102},{104,98,111},{110,108,109},{115,266,101}, |
178 |
{124,115,100},{126,264,115},{114,112,113},{119,124,97},{288,119,96}, |
179 |
{290,125,119},{118,116,117},{123,258,126},{296,123,125},{298,256,123}, |
180 |
{122,120,121},{127,113,116},{121,127,118},{120,114,127},{126,124,125}, |
181 |
{131,218,149},{140,131,148},{142,216,131},{130,128,129},{135,140,145}, |
182 |
{240,135,144},{242,141,135},{134,132,133},{139,210,142},{248,139,141}, |
183 |
{250,208,139},{138,136,137},{143,129,132},{137,143,134},{136,130,143}, |
184 |
{142,140,141},{147,314,133},{156,147,132},{158,312,147},{146,144,145}, |
185 |
{151,156,129},{272,151,128},{274,157,151},{150,148,149},{155,306,158}, |
186 |
{280,155,157},{282,304,155},{154,152,153},{159,145,148},{153,159,150}, |
187 |
{152,146,159},{158,156,157},{163,256,181},{172,163,180},{174,257,163}, |
188 |
{162,160,161},{167,172,177},{282,167,176},{281,173,167},{166,164,165}, |
189 |
{171,260,174},{278,171,173},{277,261,171},{170,168,169},{175,161,164}, |
190 |
{169,175,166},{168,162,175},{174,172,173},{179,304,165},{188,179,164}, |
191 |
{190,305,179},{178,176,177},{183,188,161},{298,183,160},{297,189,183}, |
192 |
{182,180,181},{187,308,190},{294,187,189},{293,309,187},{186,184,185}, |
193 |
{191,177,180},{185,191,182},{184,178,191},{190,188,189},{195,101,42}, |
194 |
{204,195,41},{206,102,195},{194,192,193},{199,204,38},{10,199,37},{9,205,199}, |
195 |
{198,196,197},{203,105,206},{6,203,205},{5,106,203},{202,200,201},{207,193,196}, |
196 |
{201,207,198},{200,194,207},{206,204,205},{211,138,0},{220,211,2},{222,136,211}, |
197 |
{210,208,209},{215,220,8},{48,215,10},{50,221,215},{214,212,213},{219,130,222}, |
198 |
{56,219,221},{58,128,219},{218,216,217},{223,209,212},{217,223,214}, |
199 |
{216,210,223},{222,220,221},{227,106,16},{236,227,18},{238,104,227}, |
200 |
{226,224,225},{231,236,24},{64,231,26},{66,237,231},{230,228,229},{235,98,238}, |
201 |
{72,235,237},{74,96,235},{234,232,233},{239,225,228},{233,239,230}, |
202 |
{232,226,239},{238,236,237},{243,133,90},{252,243,89},{254,134,243}, |
203 |
{242,240,241},{247,252,86},{26,247,85},{25,253,247},{246,244,245},{251,137,254}, |
204 |
{22,251,253},{21,138,251},{250,248,249},{255,241,244},{249,255,246}, |
205 |
{248,242,255},{254,252,253},{259,122,160},{268,259,162},{270,120,259}, |
206 |
{258,256,257},{263,268,168},{32,263,170},{34,269,263},{262,260,261}, |
207 |
{267,114,270},{40,267,269},{42,112,267},{266,264,265},{271,257,260}, |
208 |
{265,271,262},{264,258,271},{270,268,269},{275,149,58},{284,275,57}, |
209 |
{286,150,275},{274,272,273},{279,284,54},{170,279,53},{169,285,279}, |
210 |
{278,276,277},{283,153,286},{166,283,285},{165,154,283},{282,280,281}, |
211 |
{287,273,276},{281,287,278},{280,274,287},{286,284,285},{291,117,74}, |
212 |
{300,291,73},{302,118,291},{290,288,289},{295,300,70},{186,295,69}, |
213 |
{185,301,295},{294,292,293},{299,121,302},{182,299,301},{181,122,299}, |
214 |
{298,296,297},{303,289,292},{297,303,294},{296,290,303},{302,300,301}, |
215 |
{307,154,176},{316,307,178},{318,152,307},{306,304,305},{311,316,184}, |
216 |
{80,311,186},{82,317,311},{310,308,309},{315,146,318},{88,315,317}, |
217 |
{90,144,315},{314,312,313},{319,305,308},{313,319,310},{312,306,319}, |
218 |
{318,316,317}}; |
219 |
|
220 |
|
221 |
#ifdef TEST_DRIVER |
222 |
VIEW Current_View = {0,{0,0,0},{0,0,-1},{0,1,0},60,60,0}; |
223 |
int Pick_cnt =0; |
224 |
int Pick_tri = -1,Picking = FALSE,Pick_samp=-1; |
225 |
FVECT Pick_point[500],Pick_origin,Pick_dir; |
226 |
FVECT Pick_v0[500], Pick_v1[500], Pick_v2[500]; |
227 |
int Pick_q[500]; |
228 |
FVECT P0,P1,P2; |
229 |
FVECT FrustumNear[4],FrustumFar[4]; |
230 |
double dev_zmin=.01,dev_zmax=1000; |
231 |
#endif |
232 |
|
233 |
smDir(sm,ps,id) |
234 |
SM *sm; |
235 |
FVECT ps; |
236 |
int id; |
237 |
{ |
238 |
VSUB(ps,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); |
239 |
normalize(ps); |
240 |
} |
241 |
|
242 |
smDir_in_cone(sm,ps,id) |
243 |
SM *sm; |
244 |
FVECT ps; |
245 |
int id; |
246 |
{ |
247 |
|
248 |
VSUB(ps,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); |
249 |
normalize(ps); |
250 |
} |
251 |
|
252 |
smClear_flags(sm,which) |
253 |
SM *sm; |
254 |
int which; |
255 |
{ |
256 |
int i; |
257 |
|
258 |
if(which== -1) |
259 |
for(i=0; i < T_FLAGS;i++) |
260 |
bzero(SM_NTH_FLAGS(sm,i),FLAG_BYTES(SM_MAX_TRIS(sm))); |
261 |
else |
262 |
bzero(SM_NTH_FLAGS(sm,which),FLAG_BYTES(SM_MAX_TRIS(sm))); |
263 |
} |
264 |
|
265 |
/* Given an allocated mesh- initialize */ |
266 |
smInit_mesh(sm) |
267 |
SM *sm; |
268 |
{ |
269 |
/* Reset the triangle counters */ |
270 |
SM_NUM_TRI(sm) = 0; |
271 |
SM_SAMPLE_TRIS(sm) = 0; |
272 |
SM_FREE_TRIS(sm) = -1; |
273 |
SM_AVAILABLE_TRIS(sm) = -1; |
274 |
smClear_flags(sm,-1); |
275 |
} |
276 |
|
277 |
|
278 |
/* Clear the SM for reuse: free any extra allocated memory:does initialization |
279 |
as well |
280 |
*/ |
281 |
smClear(sm) |
282 |
SM *sm; |
283 |
{ |
284 |
smClear_samples(sm); |
285 |
smClear_locator(sm); |
286 |
smInit_mesh(sm); |
287 |
} |
288 |
|
289 |
static int realloc_cnt=0; |
290 |
|
291 |
int |
292 |
smRealloc_mesh(sm) |
293 |
SM *sm; |
294 |
{ |
295 |
int fbytes,i,max_tris,max_verts; |
296 |
|
297 |
if(realloc_cnt <=0) |
298 |
realloc_cnt = SM_MAX_TRIS(sm); |
299 |
|
300 |
max_tris = SM_MAX_TRIS(sm) + realloc_cnt; |
301 |
fbytes = FLAG_BYTES(max_tris); |
302 |
|
303 |
if(!(SM_TRIS(sm) = (TRI *)realloc(SM_TRIS(sm),max_tris*sizeof(TRI)))) |
304 |
goto memerr; |
305 |
|
306 |
for(i=0; i< T_FLAGS; i++) |
307 |
if(!(SM_NTH_FLAGS(sm,i)=(int4 *)realloc((char *)SM_NTH_FLAGS(sm,i),fbytes))) |
308 |
goto memerr; |
309 |
|
310 |
SM_MAX_TRIS(sm) = max_tris; |
311 |
return(max_tris); |
312 |
|
313 |
memerr: |
314 |
error(SYSTEM, "out of memory in smRealloc_mesh()"); |
315 |
} |
316 |
|
317 |
/* Allocate and initialize a new mesh with max_verts and max_tris */ |
318 |
int |
319 |
smAlloc_mesh(sm,max_verts,max_tris) |
320 |
SM *sm; |
321 |
int max_verts,max_tris; |
322 |
{ |
323 |
int fbytes,i; |
324 |
|
325 |
fbytes = FLAG_BYTES(max_tris); |
326 |
|
327 |
if(!(SM_TRIS(sm) = (TRI *)realloc(NULL,max_tris*sizeof(TRI)))) |
328 |
goto memerr; |
329 |
|
330 |
if(!(SM_VERTS(sm) = (VERT *)realloc(NULL,max_verts*sizeof(VERT)))) |
331 |
goto memerr; |
332 |
|
333 |
for(i=0; i< T_FLAGS; i++) |
334 |
if(!(SM_NTH_FLAGS(sm,i)=(int4 *)realloc(NULL,fbytes))) |
335 |
goto memerr; |
336 |
|
337 |
SM_MAX_VERTS(sm) = max_verts; |
338 |
SM_MAX_TRIS(sm) = max_tris; |
339 |
|
340 |
realloc_cnt = max_verts >> 1; |
341 |
|
342 |
smInit_mesh(sm); |
343 |
|
344 |
return(max_tris); |
345 |
memerr: |
346 |
error(SYSTEM, "out of memory in smAlloc_mesh()"); |
347 |
} |
348 |
|
349 |
|
350 |
int |
351 |
compress_set(os) |
352 |
OBJECT *os; |
353 |
{ |
354 |
int i,j; |
355 |
|
356 |
for (i = 1, j = os[0]; i <= j; i++) |
357 |
{ |
358 |
if(SM_T_ID_VALID(smMesh,os[i])) |
359 |
continue; |
360 |
if(i==j) |
361 |
break; |
362 |
while(!SM_T_ID_VALID(smMesh,os[j]) && (i < j)) |
363 |
j--; |
364 |
if(i==j) |
365 |
break; |
366 |
os[i] = os[j--]; |
367 |
} |
368 |
i--; |
369 |
|
370 |
os[0] = i; |
371 |
return(i); |
372 |
|
373 |
} |
374 |
|
375 |
int |
376 |
smAlloc_tri(sm) |
377 |
SM *sm; |
378 |
{ |
379 |
int id; |
380 |
|
381 |
/* First check if there are any tris on the free list */ |
382 |
/* Otherwise, have we reached the end of the list yet?*/ |
383 |
if(SM_NUM_TRI(sm) < SM_MAX_TRIS(sm)) |
384 |
return(SM_NUM_TRI(sm)++); |
385 |
if((id = SM_AVAILABLE_TRIS(sm)) != -1) |
386 |
{ |
387 |
SM_AVAILABLE_TRIS(sm) = T_NEXT_AVAILABLE(SM_NTH_TRI(sm,id)); |
388 |
return(id); |
389 |
} |
390 |
if((id = SM_FREE_TRIS(sm)) != -1) |
391 |
{ |
392 |
dosets(compress_set); |
393 |
SM_AVAILABLE_TRIS(sm) = T_NEXT_FREE(SM_NTH_TRI(sm,id)); |
394 |
SM_FREE_TRIS(sm) = -1; |
395 |
return(id); |
396 |
} |
397 |
/*Else: realloc */ |
398 |
smRealloc_mesh(sm); |
399 |
return(SM_NUM_TRI(sm)++); |
400 |
} |
401 |
|
402 |
smFree_mesh(sm) |
403 |
SM *sm; |
404 |
{ |
405 |
int i; |
406 |
|
407 |
if(SM_TRIS(sm)) |
408 |
free(SM_TRIS(sm)); |
409 |
if(SM_VERTS(sm)) |
410 |
free(SM_VERTS(sm)); |
411 |
for(i=0; i< T_FLAGS; i++) |
412 |
if(SM_NTH_FLAGS(sm,i)) |
413 |
free(SM_NTH_FLAGS(sm,i)); |
414 |
} |
415 |
|
416 |
|
417 |
/* Initialize/clear global smL sample list for at least n samples */ |
418 |
smAlloc(max_samples) |
419 |
register int max_samples; |
420 |
{ |
421 |
unsigned nbytes; |
422 |
register unsigned i; |
423 |
int total_points; |
424 |
int max_tris,n; |
425 |
|
426 |
n = max_samples; |
427 |
/* If this is the first call, allocate sample,vertex and triangle lists */ |
428 |
if(!smMesh) |
429 |
{ |
430 |
if(!(smMesh = (SM *)malloc(sizeof(SM)))) |
431 |
error(SYSTEM,"smAlloc():Unable to allocate memory\n"); |
432 |
bzero(smMesh,sizeof(SM)); |
433 |
} |
434 |
else |
435 |
{ /* If existing structure: first deallocate */ |
436 |
smFree_mesh(smMesh); |
437 |
smFree_samples(smMesh); |
438 |
smFree_locator(smMesh); |
439 |
} |
440 |
|
441 |
/* First allocate at least n samples + extra points:at least enough |
442 |
necessary to form the BASE MESH- Default = 4; |
443 |
*/ |
444 |
SM_SAMP(smMesh) = sAlloc(&n,SM_EXTRA_POINTS); |
445 |
|
446 |
total_points = n + SM_EXTRA_POINTS; |
447 |
|
448 |
max_tris = total_points*4; |
449 |
/* Now allocate space for mesh vertices and triangles */ |
450 |
max_tris = smAlloc_mesh(smMesh, total_points, max_tris); |
451 |
|
452 |
/* Initialize the structure for point,triangle location. |
453 |
*/ |
454 |
smAlloc_locator(smMesh); |
455 |
} |
456 |
|
457 |
|
458 |
|
459 |
smInit_sm(sm,vp) |
460 |
SM *sm; |
461 |
FVECT vp; |
462 |
{ |
463 |
|
464 |
smDist_sum = 0; |
465 |
smNew_tri_cnt = 0; |
466 |
|
467 |
VCOPY(SM_VIEW_CENTER(sm),vp); |
468 |
smInit_locator(sm,vp); |
469 |
smInit_samples(sm); |
470 |
smInit_mesh(sm); |
471 |
smCreate_base_mesh(sm,SM_DEFAULT); |
472 |
} |
473 |
|
474 |
/* |
475 |
* int |
476 |
* smInit(n) : Initialize/clear data structures for n entries |
477 |
* int n; |
478 |
* |
479 |
* This routine allocates/initializes the sample, mesh, and point-location |
480 |
* structures for at least n samples. |
481 |
* If n is <= 0, then clear data structures. Returns number samples |
482 |
* actually allocated. |
483 |
*/ |
484 |
|
485 |
int |
486 |
smInit(n) |
487 |
register int n; |
488 |
{ |
489 |
int max_vertices; |
490 |
|
491 |
|
492 |
/* If n <=0, Just clear the existing structures */ |
493 |
if(n <= 0) |
494 |
{ |
495 |
smClear(smMesh); |
496 |
return(0); |
497 |
} |
498 |
|
499 |
/* Total mesh vertices includes the sample points and the extra vertices |
500 |
to form the base mesh |
501 |
*/ |
502 |
max_vertices = n + SM_EXTRA_POINTS; |
503 |
|
504 |
/* If the current mesh contains enough room, clear and return */ |
505 |
if(smMesh && (max_vertices <= SM_MAX_VERTS(smMesh)) && SM_MAX_SAMP(smMesh) <= |
506 |
n && SM_MAX_POINTS(smMesh) <= max_vertices) |
507 |
{ |
508 |
smClear(smMesh); |
509 |
return(SM_MAX_SAMP(smMesh)); |
510 |
} |
511 |
/* Otherwise- mesh must be allocated with the appropriate number of |
512 |
samples |
513 |
*/ |
514 |
smAlloc(n); |
515 |
|
516 |
return(SM_MAX_SAMP(smMesh)); |
517 |
} |
518 |
|
519 |
|
520 |
smLocator_apply(sm,v0,v1,v2,func) |
521 |
SM *sm; |
522 |
FVECT v0,v1,v2; |
523 |
FUNC func; |
524 |
{ |
525 |
STREE *st; |
526 |
FVECT tri[3]; |
527 |
|
528 |
st = SM_LOCATOR(sm); |
529 |
|
530 |
VSUB(tri[0],v0,SM_VIEW_CENTER(sm)); |
531 |
VSUB(tri[1],v1,SM_VIEW_CENTER(sm)); |
532 |
VSUB(tri[2],v2,SM_VIEW_CENTER(sm)); |
533 |
stVisit(st,tri,func); |
534 |
|
535 |
} |
536 |
|
537 |
|
538 |
/* NEW INSERTION!!! ******************************************************/ |
539 |
QUADTREE |
540 |
insert_tri(argptr,root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale, |
541 |
s0,s1,s2,sq0,sq1,sq2,rev,f,n) |
542 |
int *argptr; |
543 |
int root; |
544 |
QUADTREE qt; |
545 |
BCOORD q0[3],q1[3],q2[3]; |
546 |
BCOORD t0[3],t1[3],t2[3]; |
547 |
BCOORD dt10[3],dt21[3],dt02[3]; |
548 |
unsigned int scale,s0,s1,s2,sq0,sq1,sq2,rev; |
549 |
FUNC f; |
550 |
int n; |
551 |
{ |
552 |
OBJECT *optr,*tptr,t_set[QT_MAXSET+1]; |
553 |
int i,t_id; |
554 |
TRI *t; |
555 |
FVECT tri[3]; |
556 |
BCOORD b0[3],b1[3],b2[3]; |
557 |
BCOORD tb0[3],tb1[3],tb2[3]; |
558 |
BCOORD db10[3],db21[3],db02[3]; |
559 |
BCOORD a,b,c,qa,qb,qc; |
560 |
FUNC tfunc; |
561 |
|
562 |
t_id = *argptr; |
563 |
|
564 |
/* If the set is empty - just add */ |
565 |
if(QT_IS_EMPTY(qt)) |
566 |
return(qtadduelem(qt,t_id)); |
567 |
|
568 |
/* If the set size is below expansion threshold,or at maximum |
569 |
number of quadtree levels : just add */ |
570 |
optr = qtqueryset(qt); |
571 |
if(QT_SET_CNT(optr) < QT_SET_THRESHOLD || (n >= QT_MAX_LEVELS)) |
572 |
return(qtadduelem(qt,t_id)); |
573 |
/* otherwise: expand node- and insert tri, and reinsert existing tris |
574 |
in set to children of new node |
575 |
*/ |
576 |
/* First tri compressing set */ |
577 |
#ifdef NEWSETS0 |
578 |
if(qtcompressuelem(qt,compress_set) < QT_SET_THRESHOLD) |
579 |
/* Get set: If greater than standard size: allocate memory to hold */ |
580 |
return(qtadduelem(qt,t_id)); |
581 |
#endif |
582 |
if(QT_SET_CNT(optr) > QT_MAXSET) |
583 |
{ |
584 |
if(!(tptr = (OBJECT *)malloc((QT_SET_CNT(optr)+1)*sizeof(OBJECT)))) |
585 |
goto memerr; |
586 |
} |
587 |
else |
588 |
tptr = t_set; |
589 |
qtgetset(tptr,qt); |
590 |
|
591 |
/* subdivide node */ |
592 |
qtfreeleaf(qt); |
593 |
qtSubdivide(qt); |
594 |
|
595 |
a = q1[0]; b = q0[1]; c = q0[2]; |
596 |
qa = q0[0]; qb = q1[1]; qc = q2[2]; |
597 |
/* First add current tri: have all of the information */ |
598 |
if(rev) |
599 |
qt = qtInsert_tri_rev(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale, |
600 |
s0,s1,s2,sq0,sq1,sq2,f,n); |
601 |
else |
602 |
qt = qtInsert_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale, |
603 |
s0,s1,s2,sq0,sq1,sq2,f,n); |
604 |
|
605 |
/* Now add in all of the rest; */ |
606 |
F_FUNC(tfunc) = F_FUNC(f); |
607 |
for(optr = QT_SET_PTR(tptr),i=QT_SET_CNT(tptr); i > 0; i--) |
608 |
{ |
609 |
t_id = QT_SET_NEXT_ELEM(optr); |
610 |
t = SM_NTH_TRI(smMesh,t_id); |
611 |
if(!T_IS_VALID(t)) |
612 |
continue; |
613 |
F_ARGS(tfunc) = &t_id; |
614 |
VSUB(tri[0],SM_T_NTH_WV(smMesh,t,0),SM_VIEW_CENTER(smMesh)); |
615 |
VSUB(tri[1],SM_T_NTH_WV(smMesh,t,1),SM_VIEW_CENTER(smMesh)); |
616 |
VSUB(tri[2],SM_T_NTH_WV(smMesh,t,2),SM_VIEW_CENTER(smMesh)); |
617 |
convert_tri_to_frame(root,tri,b0,b1,b2,db10,db21,db02); |
618 |
|
619 |
/* Calculate appropriate sidedness values */ |
620 |
SIDES_GTR(b0,b1,b2,s0,s1,s2,a,b,c); |
621 |
SIDES_GTR(b0,b1,b2,sq0,sq1,sq2,qa,qb,qc); |
622 |
if(rev) |
623 |
qt = qtInsert_tri_rev(root,qt,q0,q1,q2,b0,b1,b2,db10,db21,db02,scale, |
624 |
s0,s1,s2,sq0,sq1,sq2,tfunc,n); |
625 |
else |
626 |
qt = qtInsert_tri(root,qt,q0,q1,q2,b0,b1,b2,db10,db21,db02,scale, |
627 |
s0,s1,s2,sq0,sq1,sq2,tfunc,n); |
628 |
} |
629 |
/* If we allocated memory: free it */ |
630 |
if( tptr != t_set) |
631 |
free(tptr); |
632 |
|
633 |
return(qt); |
634 |
memerr: |
635 |
error(SYSTEM,"expand_node():Unable to allocate memory"); |
636 |
|
637 |
} |
638 |
|
639 |
|
640 |
|
641 |
smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id) |
642 |
SM *sm; |
643 |
int t_id; |
644 |
int v0_id,v1_id,v2_id; |
645 |
{ |
646 |
FVECT tri[3]; |
647 |
FUNC f; |
648 |
|
649 |
#ifdef DEBUG |
650 |
if(T_NTH_NBR(SM_NTH_TRI(sm,t_id),0)== -1 || |
651 |
T_NTH_NBR(SM_NTH_TRI(sm,t_id),1)== -1 || |
652 |
T_NTH_NBR(SM_NTH_TRI(sm,t_id),2)== -1) |
653 |
error("Invalid tri: smLocator_add_tri()\n"); |
654 |
|
655 |
if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t_id),0))) || |
656 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t_id),1))) || |
657 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,t_id),2)))) |
658 |
error("Invalid tri: smLocator_add_tri()\n"); |
659 |
#endif |
660 |
|
661 |
VSUB(tri[0],SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm)); |
662 |
VSUB(tri[1],SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm)); |
663 |
VSUB(tri[2],SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm)); |
664 |
|
665 |
F_FUNC(f) = insert_tri; |
666 |
F_ARGS(f) = &t_id; |
667 |
stInsert_tri(SM_LOCATOR(sm),tri,f); |
668 |
} |
669 |
|
670 |
/* Add a triangle to the base array with vertices v1-v2-v3 */ |
671 |
int |
672 |
smAdd_tri(sm, v0_id,v1_id,v2_id) |
673 |
SM *sm; |
674 |
int v0_id,v1_id,v2_id; |
675 |
{ |
676 |
int t_id; |
677 |
TRI *t; |
678 |
#ifdef DEBUG |
679 |
if(v0_id==v1_id || v0_id==v2_id || v1_id==v2_id) |
680 |
error(CONSISTENCY,"smAdd_tri: invalid vertex ids\n"); |
681 |
#endif |
682 |
t_id = smAlloc_tri(sm); |
683 |
|
684 |
if(t_id == -1) |
685 |
return(t_id); |
686 |
|
687 |
t = SM_NTH_TRI(sm,t_id); |
688 |
|
689 |
T_CLEAR_NBRS(t); |
690 |
/* set the triangle vertex ids */ |
691 |
T_NTH_V(t,0) = v0_id; |
692 |
T_NTH_V(t,1) = v1_id; |
693 |
T_NTH_V(t,2) = v2_id; |
694 |
|
695 |
SM_NTH_VERT(sm,v0_id) = t_id; |
696 |
SM_NTH_VERT(sm,v1_id) = t_id; |
697 |
SM_NTH_VERT(sm,v2_id) = t_id; |
698 |
|
699 |
if(SM_BASE_ID(sm,v0_id) || SM_BASE_ID(sm,v1_id) || SM_BASE_ID(sm,v2_id)) |
700 |
{ |
701 |
smClear_tri_flags(sm,t_id); |
702 |
SM_SET_NTH_T_BASE(sm,t_id); |
703 |
} |
704 |
else |
705 |
{ |
706 |
SM_CLR_NTH_T_BASE(sm,t_id); |
707 |
SM_SET_NTH_T_ACTIVE(sm,t_id); |
708 |
SM_SET_NTH_T_NEW(sm,t_id); |
709 |
S_SET_FLAG(T_NTH_V(t,0)); |
710 |
S_SET_FLAG(T_NTH_V(t,1)); |
711 |
S_SET_FLAG(T_NTH_V(t,2)); |
712 |
SM_SAMPLE_TRIS(sm)++; |
713 |
smNew_tri_cnt++; |
714 |
} |
715 |
|
716 |
/* return initialized triangle */ |
717 |
return(t_id); |
718 |
} |
719 |
|
720 |
|
721 |
void |
722 |
smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add_ptr) |
723 |
SM *sm; |
724 |
int t_id,t1_id; |
725 |
int e,e1; |
726 |
int *tn_id,*tn1_id; |
727 |
LIST **add_ptr; |
728 |
{ |
729 |
int verts[3],enext,eprev,e1next,e1prev; |
730 |
TRI *n,*ta,*tb,*t,*t1; |
731 |
FVECT p1,p2,p3; |
732 |
int ta_id,tb_id; |
733 |
/* form new diagonal (e relative to t, and e1 relative to t1) |
734 |
defined by quadrilateral formed by t,t1- swap for the opposite diagonal |
735 |
*/ |
736 |
enext = (e+1)%3; |
737 |
eprev = (e+2)%3; |
738 |
e1next = (e1+1)%3; |
739 |
e1prev = (e1+2)%3; |
740 |
verts[e] = T_NTH_V(SM_NTH_TRI(sm,t_id),e); |
741 |
verts[enext] = T_NTH_V(SM_NTH_TRI(sm,t_id),enext); |
742 |
verts[eprev] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1); |
743 |
ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2]); |
744 |
*add_ptr = push_data(*add_ptr,ta_id); |
745 |
verts[e1] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1); |
746 |
verts[e1next] = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1next); |
747 |
verts[e1prev] = T_NTH_V(SM_NTH_TRI(sm,t_id),e); |
748 |
tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2]); |
749 |
|
750 |
*add_ptr = push_data(*add_ptr,tb_id); |
751 |
ta = SM_NTH_TRI(sm,ta_id); |
752 |
tb = SM_NTH_TRI(sm,tb_id); |
753 |
t = SM_NTH_TRI(sm,t_id); |
754 |
t1 = SM_NTH_TRI(sm,t1_id); |
755 |
/* set the neighbors */ |
756 |
T_NTH_NBR(ta,e) = T_NTH_NBR(t1,e1next); |
757 |
T_NTH_NBR(tb,e1) = T_NTH_NBR(t,enext); |
758 |
T_NTH_NBR(ta,enext)= tb_id; |
759 |
T_NTH_NBR(tb,e1next)= ta_id; |
760 |
T_NTH_NBR(ta,eprev)=T_NTH_NBR(t,eprev); |
761 |
T_NTH_NBR(tb,e1prev)=T_NTH_NBR(t1,e1prev); |
762 |
|
763 |
|
764 |
#ifdef DEBUG |
765 |
if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,0))) || |
766 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,1))) || |
767 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,2))) || |
768 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,0))) || |
769 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,1))) || |
770 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,2)))) |
771 |
goto Ltri_error; |
772 |
if(SM_NTH_TRI(sm,T_NTH_NBR(ta,0))==SM_NTH_TRI(sm,T_NTH_NBR(ta,1)) || |
773 |
SM_NTH_TRI(sm,T_NTH_NBR(ta,0))==SM_NTH_TRI(sm,T_NTH_NBR(ta,2)) || |
774 |
SM_NTH_TRI(sm,T_NTH_NBR(ta,1))==SM_NTH_TRI(sm,T_NTH_NBR(ta,2)) || |
775 |
SM_NTH_TRI(sm,T_NTH_NBR(tb,0))==SM_NTH_TRI(sm,T_NTH_NBR(tb,1)) || |
776 |
SM_NTH_TRI(sm,T_NTH_NBR(tb,0))==SM_NTH_TRI(sm,T_NTH_NBR(tb,2)) || |
777 |
SM_NTH_TRI(sm,T_NTH_NBR(tb,1))==SM_NTH_TRI(sm,T_NTH_NBR(tb,2)) ) |
778 |
goto Ltri_error; |
779 |
#endif |
780 |
/* Reset neighbor pointers of original neighbors */ |
781 |
n = SM_NTH_TRI(sm,T_NTH_NBR(t,enext)); |
782 |
#ifdef DEBUG |
783 |
if(!T_IS_VALID(n)) |
784 |
goto Ltri_error; |
785 |
#endif |
786 |
T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = tb_id; |
787 |
n = SM_NTH_TRI(sm,T_NTH_NBR(t,eprev)); |
788 |
#ifdef DEBUG |
789 |
if(!T_IS_VALID(n)) |
790 |
goto Ltri_error; |
791 |
#endif |
792 |
T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = ta_id; |
793 |
|
794 |
n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1next)); |
795 |
#ifdef DEBUG |
796 |
if(!T_IS_VALID(n)) |
797 |
goto Ltri_error; |
798 |
#endif |
799 |
T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = ta_id; |
800 |
n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1prev)); |
801 |
#ifdef DEBUG |
802 |
if(!T_IS_VALID(n)) |
803 |
goto Ltri_error; |
804 |
#endif |
805 |
T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = tb_id; |
806 |
|
807 |
#ifdef DEBUG |
808 |
T_VALID_FLAG(SM_NTH_TRI(sm,t_id))=-1; |
809 |
T_VALID_FLAG(SM_NTH_TRI(sm,t1_id))=-1; |
810 |
#endif |
811 |
|
812 |
remove_from_list(t_id,add_ptr); |
813 |
remove_from_list(t1_id,add_ptr); |
814 |
#if 1 |
815 |
smDelete_tri(sm,t_id); |
816 |
smDelete_tri(sm,t1_id); |
817 |
#else |
818 |
*del_ptr = push_data(*del_ptr,t_id); |
819 |
*del_ptr = push_data(*del_ptr,t1_id); |
820 |
#endif |
821 |
|
822 |
|
823 |
|
824 |
*tn_id = ta_id; |
825 |
*tn1_id = tb_id; |
826 |
|
827 |
#ifdef DEBUG |
828 |
if(T_NTH_NBR(SM_NTH_TRI(sm,ta_id),0)== -1 || |
829 |
T_NTH_NBR(SM_NTH_TRI(sm,ta_id),1)== -1 || |
830 |
T_NTH_NBR(SM_NTH_TRI(sm,ta_id),2)== -1 || |
831 |
T_NTH_NBR(SM_NTH_TRI(sm,tb_id),0)== -1 || |
832 |
T_NTH_NBR(SM_NTH_TRI(sm,tb_id),1)== -1 || |
833 |
T_NTH_NBR(SM_NTH_TRI(sm,tb_id),2)== -1) |
834 |
goto Ltri_error; |
835 |
if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,ta_id),0))) || |
836 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,ta_id),1))) || |
837 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,ta_id),2)))) |
838 |
goto Ltri_error; |
839 |
if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tb_id),0))) || |
840 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tb_id),1))) || |
841 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tb_id),2)))) |
842 |
goto Ltri_error; |
843 |
#endif |
844 |
return; |
845 |
Ltri_error: |
846 |
error(CONSISTENCY,"Invalid tri: smTris_swap_edge()\n"); |
847 |
} |
848 |
|
849 |
smUpdate_locator(sm,add_list) |
850 |
SM *sm; |
851 |
LIST *add_list; |
852 |
{ |
853 |
int t_id,i; |
854 |
TRI *t; |
855 |
OBJECT *optr; |
856 |
|
857 |
while(add_list) |
858 |
{ |
859 |
t_id = pop_list(&add_list); |
860 |
t = SM_NTH_TRI(sm,t_id); |
861 |
smLocator_add_tri(sm,t_id,T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2)); |
862 |
} |
863 |
} |
864 |
|
865 |
int |
866 |
smFix_tris(sm,id,tlist,add_list) |
867 |
SM *sm; |
868 |
int id; |
869 |
LIST *tlist,*add_list; |
870 |
{ |
871 |
TRI *t,*t_opp; |
872 |
FVECT p,p0,p1,p2; |
873 |
int e,e1,swapped = 0; |
874 |
int t_id,t_opp_id; |
875 |
LIST *del_list=NULL; |
876 |
|
877 |
VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); |
878 |
while(tlist) |
879 |
{ |
880 |
t_id = pop_list(&tlist); |
881 |
#ifdef DEBUG |
882 |
if(t_id==INVALID || t_id > smMesh->num_tri) |
883 |
error(CONSISTENCY,"Invalid tri id smFix_tris()\n"); |
884 |
#endif |
885 |
t = SM_NTH_TRI(sm,t_id); |
886 |
e = T_WHICH_V(t,id); |
887 |
t_opp_id = T_NTH_NBR(t,e); |
888 |
#ifdef DEBUG |
889 |
if(t_opp_id==INVALID || t_opp_id > smMesh->num_tri) |
890 |
error(CONSISTENCY,"Invalid tri id smFix_tris()\n"); |
891 |
#endif |
892 |
t_opp = SM_NTH_TRI(sm,t_opp_id); |
893 |
#ifdef DEBUG |
894 |
if(!T_IS_VALID(t_opp)) |
895 |
error(CONSISTENCY,"Invalid trismFix_tris()\n"); |
896 |
#endif |
897 |
smDir_in_cone(sm,p0,T_NTH_V(t_opp,0)); |
898 |
smDir_in_cone(sm,p1,T_NTH_V(t_opp,1)); |
899 |
smDir_in_cone(sm,p2,T_NTH_V(t_opp,2)); |
900 |
if(point_in_cone(p,p0,p1,p2)) |
901 |
{ |
902 |
swapped = 1; |
903 |
e1 = T_NTH_NBR_PTR(t_id,t_opp); |
904 |
/* check list for t_opp and Remove if there */ |
905 |
remove_from_list(t_opp_id,&tlist); |
906 |
smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id, |
907 |
&add_list); |
908 |
tlist = push_data(tlist,t_id); |
909 |
tlist = push_data(tlist,t_opp_id); |
910 |
} |
911 |
} |
912 |
#if 0 |
913 |
while(del_list) |
914 |
{ |
915 |
t_id = pop_list(&del_list); |
916 |
smDelete_tri(sm,t_id); |
917 |
} |
918 |
#endif |
919 |
smUpdate_locator(sm,add_list); |
920 |
|
921 |
return(swapped); |
922 |
} |
923 |
|
924 |
/* Give the vertex "id" and a triangle "t" that it belongs to- return the |
925 |
next nbr in a counter clockwise order about vertex "id" |
926 |
*/ |
927 |
int |
928 |
smTri_next_ccw_nbr(sm,t,id) |
929 |
SM *sm; |
930 |
TRI *t; |
931 |
int id; |
932 |
{ |
933 |
int which; |
934 |
int nbr_id; |
935 |
|
936 |
/* Want the edge for which "id" is the destination */ |
937 |
which = T_WHICH_V(t,id); |
938 |
if(which== INVALID) |
939 |
return(which); |
940 |
|
941 |
nbr_id = T_NTH_NBR(t,(which + 1)% 3); |
942 |
return(nbr_id); |
943 |
} |
944 |
|
945 |
smClear_tri_flags(sm,id) |
946 |
SM *sm; |
947 |
int id; |
948 |
{ |
949 |
int i; |
950 |
|
951 |
for(i=0; i < T_FLAGS; i++) |
952 |
SM_CLR_NTH_T_FLAG(sm,id,i); |
953 |
|
954 |
} |
955 |
|
956 |
/* Locate the point-id in the point location structure: */ |
957 |
int |
958 |
smInsert_samp(sm,s_id,tri_id,on,which) |
959 |
SM *sm; |
960 |
int s_id,tri_id; |
961 |
int on,which; |
962 |
{ |
963 |
int v_id[3],topp_id,i; |
964 |
int t0_id,t1_id,t2_id,t3_id,replaced; |
965 |
int e0,e1,e2,opp0,opp1,opp2,opp_id; |
966 |
LIST *tlist,*add_list; |
967 |
FVECT npt; |
968 |
TRI *tri,*nbr,*topp; |
969 |
|
970 |
|
971 |
add_list = NULL; |
972 |
for(i=0; i<3;i++) |
973 |
v_id[i] = T_NTH_V(SM_NTH_TRI(sm,tri_id),i); |
974 |
|
975 |
/* If falls on existing edge */ |
976 |
if(on == ON_E) |
977 |
{ |
978 |
tri = SM_NTH_TRI(sm,tri_id); |
979 |
topp_id = T_NTH_NBR(tri,which); |
980 |
e0 = which; |
981 |
e1 = (which+1)%3; |
982 |
e2 = (which+2)%3; |
983 |
topp = SM_NTH_TRI(sm,topp_id); |
984 |
opp0 = T_NTH_NBR_PTR(tri_id,topp); |
985 |
opp_id = T_NTH_V(topp,opp0); |
986 |
opp1 = (opp0+1)%3; |
987 |
opp2 = (opp0+2)%3; |
988 |
|
989 |
/* Create 4 triangles */ |
990 |
/* /|\ /|\ |
991 |
/ | \ / | \ |
992 |
/ * \ ----> /__|__\ |
993 |
\ | / \ | / |
994 |
\ | / \ | / |
995 |
\|/ \|/ |
996 |
*/ |
997 |
t0_id = smAdd_tri(sm,s_id,v_id[e0],v_id[e1]); |
998 |
add_list = push_data(add_list,t0_id); |
999 |
t1_id = smAdd_tri(sm,s_id,v_id[e2],v_id[e0]); |
1000 |
add_list = push_data(add_list,t1_id); |
1001 |
t2_id = smAdd_tri(sm,s_id,v_id[e1],opp_id); |
1002 |
add_list = push_data(add_list,t2_id); |
1003 |
t3_id = smAdd_tri(sm,s_id,opp_id,v_id[e2]); |
1004 |
add_list = push_data(add_list,t3_id); |
1005 |
/* CAUTION: tri must be assigned after Add_tri: pointers may change*/ |
1006 |
tri = SM_NTH_TRI(sm,tri_id); |
1007 |
topp =SM_NTH_TRI(sm,topp_id); |
1008 |
|
1009 |
/* Set the neighbor pointers for the new tris */ |
1010 |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),0) = T_NTH_NBR(tri,e2); |
1011 |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),1) = t2_id; |
1012 |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),2) = t1_id; |
1013 |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),0) = T_NTH_NBR(tri,e1); |
1014 |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),1) = t0_id; |
1015 |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),2) = t3_id; |
1016 |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),0) = T_NTH_NBR(topp,opp1); |
1017 |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),1) = t3_id; |
1018 |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),2) = t0_id; |
1019 |
T_NTH_NBR(SM_NTH_TRI(sm,t3_id),0) = T_NTH_NBR(topp,opp2); |
1020 |
T_NTH_NBR(SM_NTH_TRI(sm,t3_id),1) = t1_id; |
1021 |
T_NTH_NBR(SM_NTH_TRI(sm,t3_id),2) = t2_id; |
1022 |
|
1023 |
/* Reset the neigbor pointers for the neighbors of the original */ |
1024 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,e1)); |
1025 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t1_id; |
1026 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,e2)); |
1027 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t0_id; |
1028 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(topp,opp1)); |
1029 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(topp_id,nbr)) = t2_id; |
1030 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(topp,opp2)); |
1031 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(topp_id,nbr)) = t3_id; |
1032 |
#ifdef DEBUG |
1033 |
T_VALID_FLAG(SM_NTH_TRI(sm,tri_id))=-1; |
1034 |
T_VALID_FLAG(SM_NTH_TRI(sm,topp_id))=-1; |
1035 |
#endif |
1036 |
tlist = push_data(NULL,t0_id); |
1037 |
tlist = push_data(tlist,t1_id); |
1038 |
tlist = push_data(tlist,t2_id); |
1039 |
tlist = push_data(tlist,t3_id); |
1040 |
} |
1041 |
else |
1042 |
{ |
1043 |
/* Create 3 triangles */ |
1044 |
/* / \ /|\ |
1045 |
/ \ / | \ |
1046 |
/ * \ ----> / | \ |
1047 |
/ \ / / \ \ |
1048 |
/ \ / / \ \ |
1049 |
/___________\ //_________\\ |
1050 |
*/ |
1051 |
|
1052 |
t0_id = smAdd_tri(sm,s_id,v_id[0],v_id[1]); |
1053 |
add_list = push_data(add_list,t0_id); |
1054 |
t1_id = smAdd_tri(sm,s_id,v_id[1],v_id[2]); |
1055 |
add_list = push_data(add_list,t1_id); |
1056 |
t2_id = smAdd_tri(sm,s_id,v_id[2],v_id[0]); |
1057 |
add_list = push_data(add_list,t2_id); |
1058 |
|
1059 |
/* CAUTION: tri must be assigned after Add_tri: pointers may change*/ |
1060 |
tri = SM_NTH_TRI(sm,tri_id); |
1061 |
/* Set the neighbor pointers for the new tris */ |
1062 |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),0) = T_NTH_NBR(tri,2); |
1063 |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),1) = t1_id; |
1064 |
T_NTH_NBR(SM_NTH_TRI(sm,t0_id),2) = t2_id; |
1065 |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),0) = T_NTH_NBR(tri,0); |
1066 |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),1) = t2_id; |
1067 |
T_NTH_NBR(SM_NTH_TRI(sm,t1_id),2) = t0_id; |
1068 |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),0) = T_NTH_NBR(tri,1); |
1069 |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),1) = t0_id; |
1070 |
T_NTH_NBR(SM_NTH_TRI(sm,t2_id),2) = t1_id; |
1071 |
|
1072 |
/* Reset the neigbor pointers for the neighbors of the original */ |
1073 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,0)); |
1074 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t1_id; |
1075 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,1)); |
1076 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t2_id; |
1077 |
nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,2)); |
1078 |
T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t0_id; |
1079 |
|
1080 |
tlist = push_data(NULL,t0_id); |
1081 |
tlist = push_data(tlist,t1_id); |
1082 |
tlist = push_data(tlist,t2_id); |
1083 |
} |
1084 |
/* Fix up the new triangles*/ |
1085 |
smFix_tris(sm,s_id,tlist,add_list); |
1086 |
|
1087 |
smDelete_tri(sm,tri_id); |
1088 |
if(on==ON_E) |
1089 |
smDelete_tri(sm,topp_id); |
1090 |
|
1091 |
return(TRUE); |
1092 |
|
1093 |
#ifdef DEBUG |
1094 |
Ladderror: |
1095 |
error(CONSISTENCY,"Invalid tri: smInsert_samp()\n"); |
1096 |
#endif |
1097 |
} |
1098 |
|
1099 |
int |
1100 |
smTri_in_set(sm,p,optr,onptr,whichptr) |
1101 |
SM *sm; |
1102 |
FVECT p; |
1103 |
OBJECT *optr; |
1104 |
int *onptr,*whichptr; |
1105 |
{ |
1106 |
int i,t_id,on0,on1,on2; |
1107 |
FVECT n,v0,v1,v2; |
1108 |
TRI *t; |
1109 |
double side; |
1110 |
|
1111 |
for (i = QT_SET_CNT(optr),optr = QT_SET_PTR(optr);i > 0; i--) |
1112 |
{ |
1113 |
/* Find the first triangle that pt falls */ |
1114 |
t_id = QT_SET_NEXT_ELEM(optr); |
1115 |
t = SM_NTH_TRI(sm,t_id); |
1116 |
if(!T_IS_VALID(t)) |
1117 |
continue; |
1118 |
VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm)); |
1119 |
VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm)); |
1120 |
VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm)); |
1121 |
|
1122 |
if(EQUAL_VEC3(v0,p)) |
1123 |
{ |
1124 |
*onptr = ON_V; |
1125 |
*whichptr = 0; |
1126 |
return(t_id); |
1127 |
} |
1128 |
if(EQUAL_VEC3(v1,p)) |
1129 |
{ |
1130 |
*onptr = ON_V; |
1131 |
*whichptr = 1; |
1132 |
return(t_id); |
1133 |
} |
1134 |
if(EQUAL_VEC3(v2,p)) |
1135 |
{ |
1136 |
*onptr = ON_V; |
1137 |
*whichptr = 2; |
1138 |
return(t_id); |
1139 |
} |
1140 |
|
1141 |
on0 = on1 =on2 = 0; |
1142 |
VCROSS(n,v0,v1); |
1143 |
side = DOT(n,p); |
1144 |
if(ZERO(side)) |
1145 |
on2 = TRUE; |
1146 |
else |
1147 |
if(side >0.0) |
1148 |
continue; |
1149 |
|
1150 |
VCROSS(n,v1,v2); |
1151 |
side = DOT(n,p); |
1152 |
if(ZERO(side)) |
1153 |
on0 = TRUE; |
1154 |
else |
1155 |
if(side >0.0) |
1156 |
continue; |
1157 |
|
1158 |
VCROSS(n,v2,v0); |
1159 |
side = DOT(n,p); |
1160 |
if(ZERO(side)) |
1161 |
on1 = TRUE; |
1162 |
else |
1163 |
if(side >0.0) |
1164 |
continue; |
1165 |
if(on0) |
1166 |
{ |
1167 |
if(on1) |
1168 |
{ |
1169 |
*onptr = ON_P; |
1170 |
*whichptr = 2; |
1171 |
} |
1172 |
else |
1173 |
if(on2) |
1174 |
{ |
1175 |
*onptr = ON_P; |
1176 |
*whichptr = 1; |
1177 |
} |
1178 |
else |
1179 |
{ |
1180 |
*onptr = ON_E; |
1181 |
*whichptr = 0; |
1182 |
} |
1183 |
return(t_id); |
1184 |
} |
1185 |
if(on1) |
1186 |
{ |
1187 |
if(on2) |
1188 |
{ |
1189 |
*onptr = ON_P; |
1190 |
*whichptr = 0; |
1191 |
} |
1192 |
else |
1193 |
{ |
1194 |
*onptr = ON_E; |
1195 |
*whichptr = 1; |
1196 |
} |
1197 |
return(t_id); |
1198 |
} |
1199 |
if(on2) |
1200 |
{ |
1201 |
*onptr = ON_E; |
1202 |
*whichptr = 2; |
1203 |
return(t_id); |
1204 |
} |
1205 |
*onptr = IN_T; |
1206 |
return(t_id); |
1207 |
} |
1208 |
return(INVALID); |
1209 |
} |
1210 |
|
1211 |
int |
1212 |
smPointLocateTri(sm,p,onptr,whichptr) |
1213 |
SM *sm; |
1214 |
FVECT p; |
1215 |
int *onptr,*whichptr; |
1216 |
{ |
1217 |
QUADTREE qt,*optr; |
1218 |
FVECT tpt; |
1219 |
int tri_id; |
1220 |
|
1221 |
VSUB(tpt,p,SM_VIEW_CENTER(sm)); |
1222 |
qt = smPointLocateCell(sm,tpt); |
1223 |
if(QT_IS_EMPTY(qt)) |
1224 |
return(INVALID); |
1225 |
|
1226 |
optr = qtqueryset(qt); |
1227 |
tri_id = smTri_in_set(sm,tpt,optr,onptr,whichptr); |
1228 |
|
1229 |
#ifdef DEBUG |
1230 |
if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tri_id),0))) || |
1231 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tri_id),1))) || |
1232 |
!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(SM_NTH_TRI(sm,tri_id),2)))) |
1233 |
eputs("Invalid tri nbrs smPointLocateTri()\n"); |
1234 |
#endif |
1235 |
return(tri_id); |
1236 |
} |
1237 |
|
1238 |
|
1239 |
/* |
1240 |
Determine whether this sample should: |
1241 |
a) be added to the mesh by subdividing the triangle |
1242 |
b) ignored |
1243 |
c) replace values of an existing mesh vertex |
1244 |
|
1245 |
In case a, the routine will return TRUE, for b,c will return FALSE |
1246 |
In case a, also determine if this sample should cause the deletion of |
1247 |
an existing vertex. If so *rptr will contain the id of the sample to delete |
1248 |
after the new sample has been added. |
1249 |
|
1250 |
ASSUMPTION: this will not be called with a new sample that is |
1251 |
a BASE point. |
1252 |
|
1253 |
The following tests are performed (in order) to determine the fate |
1254 |
of the sample: |
1255 |
|
1256 |
1) If the new sample is close in ws, and close in the spherical projection |
1257 |
to one of the triangle vertex samples: |
1258 |
pick the point with dir closest to that of the canonical view |
1259 |
If it is the new point: mark existing point for deletion,and return |
1260 |
TRUE,else return FALSE |
1261 |
2) If the spherical projection of new is < REPLACE_EPS from a base point: |
1262 |
add new and mark the base for deletion: return TRUE |
1263 |
3) If the addition of the new sample point would introduce a "puncture" |
1264 |
or cause new triangles with large depth differences:return FALSE |
1265 |
This attempts to throw out points that should be occluded |
1266 |
*/ |
1267 |
int |
1268 |
smTest_sample(sm,tri_id,dir,p,rptr) |
1269 |
SM *sm; |
1270 |
int tri_id; |
1271 |
FVECT dir,p; |
1272 |
int *rptr; |
1273 |
{ |
1274 |
TRI *tri; |
1275 |
double d,d2,dnear,dspt,d01,d12,d20,s0,s1,s2,ds,dv; |
1276 |
int vid[3],i,nearid,norm,dcnt,bcnt; |
1277 |
FVECT diff[3],spt,npt; |
1278 |
|
1279 |
*rptr = INVALID; |
1280 |
bcnt = dcnt = 0; |
1281 |
tri = SM_NTH_TRI(sm,tri_id); |
1282 |
vid[0] = T_NTH_V(tri,0); |
1283 |
vid[1] = T_NTH_V(tri,1); |
1284 |
vid[2] = T_NTH_V(tri,2); |
1285 |
|
1286 |
for(i=0; i<3; i++) |
1287 |
{ |
1288 |
if(SM_BASE_ID(sm,vid[i])) |
1289 |
{ |
1290 |
bcnt++; |
1291 |
continue; |
1292 |
} |
1293 |
if(SM_DIR_ID(sm,vid[i])) |
1294 |
dcnt++; |
1295 |
VSUB(diff[i],SM_NTH_WV(sm,vid[i]),p); |
1296 |
/* If same world point: replace */ |
1297 |
} |
1298 |
/* TEST 1: If the new sample is close in ws, and close in the spherical |
1299 |
projection to one of the triangle vertex samples |
1300 |
*/ |
1301 |
norm = FALSE; |
1302 |
if(bcnt + dcnt != 3) |
1303 |
{ |
1304 |
VSUB(spt,p,SM_VIEW_CENTER(sm)); |
1305 |
ds = DOT(spt,spt); |
1306 |
dnear = FHUGE; |
1307 |
for(i=0; i<3; i++) |
1308 |
{ |
1309 |
if(SM_BASE_ID(sm,vid[i]) || SM_DIR_ID(sm,vid[i])) |
1310 |
continue; |
1311 |
d = DOT(diff[i],diff[i])/ds; |
1312 |
if(d < dnear) |
1313 |
{ |
1314 |
dnear = d; |
1315 |
nearid=vid[i]; |
1316 |
} |
1317 |
} |
1318 |
|
1319 |
if(dnear <= smMinSampDiff*smMinSampDiff) |
1320 |
{ |
1321 |
/* Pick the point with dir closest to that of the canonical view |
1322 |
if it is the new sample: mark existing point for deletion |
1323 |
*/ |
1324 |
normalize(spt); |
1325 |
norm = TRUE; |
1326 |
VSUB(npt,SM_NTH_WV(sm,nearid),SM_VIEW_CENTER(sm)); |
1327 |
normalize(npt); |
1328 |
d = fdir2diff(SM_NTH_W_DIR(sm,nearid), npt); |
1329 |
d2 = 2. - 2.*DOT(dir,spt); |
1330 |
/* The existing sample is a better sample:punt */ |
1331 |
if(d2 > d) |
1332 |
return(FALSE); |
1333 |
else |
1334 |
{ |
1335 |
/* The new sample is better: mark the existing one |
1336 |
for deletion after the new one is added*/ |
1337 |
*rptr = nearid; |
1338 |
return(TRUE); |
1339 |
} |
1340 |
} |
1341 |
} |
1342 |
/* TEST 3: If the spherical projection of new is < S_REPLACE_EPS |
1343 |
from a base point: Edge length is constrained to subtend <45 degrees: |
1344 |
original base mesh edges are approx 32 degrees- so have about 13 degrees |
1345 |
to work in: S_REPLACE_EPS is the square of the radian value |
1346 |
*/ |
1347 |
if(bcnt) |
1348 |
{ |
1349 |
dnear = FHUGE; |
1350 |
if(bcnt + dcnt ==3) |
1351 |
VSUB(spt,p,SM_VIEW_CENTER(sm)); |
1352 |
if(!norm) |
1353 |
normalize(spt); |
1354 |
|
1355 |
for(i=0; i<3; i++) |
1356 |
{ |
1357 |
if(!SM_BASE_ID(sm,vid[i])) |
1358 |
continue; |
1359 |
VSUB(npt,SM_NTH_WV(sm,vid[i]),SM_VIEW_CENTER(sm)); |
1360 |
d = DIST_SQ(npt,spt); |
1361 |
if(d < S_REPLACE_EPS && d < dnear) |
1362 |
{ |
1363 |
dnear = d; |
1364 |
nearid = vid[i]; |
1365 |
} |
1366 |
} |
1367 |
if(dnear != FHUGE) |
1368 |
{ |
1369 |
/* add new and mark the base for deletion */ |
1370 |
*rptr = nearid; |
1371 |
return(TRUE); |
1372 |
} |
1373 |
} |
1374 |
|
1375 |
/* TEST 4: |
1376 |
If the addition of the new sample point would introduce a "puncture" |
1377 |
or cause new triangles with large depth differences:dont add: |
1378 |
*/ |
1379 |
if(bcnt || dcnt) |
1380 |
return(TRUE); |
1381 |
/* If the new point is in front of the existing points- add */ |
1382 |
dv = DIST_SQ(SM_NTH_WV(sm,vid[0]),SM_VIEW_CENTER(sm)); |
1383 |
if(ds < dv) |
1384 |
return(TRUE); |
1385 |
|
1386 |
d01 = DIST_SQ(SM_NTH_WV(sm,vid[1]),SM_NTH_WV(sm,vid[0])); |
1387 |
s0 = DOT(diff[0],diff[0]); |
1388 |
if(s0 < S_REPLACE_SCALE*d01) |
1389 |
return(TRUE); |
1390 |
d12 = DIST_SQ(SM_NTH_WV(sm,vid[2]),SM_NTH_WV(sm,vid[1])); |
1391 |
if(s0 < S_REPLACE_SCALE*d12) |
1392 |
return(TRUE); |
1393 |
d20 = DIST_SQ(SM_NTH_WV(sm,vid[0]),SM_NTH_WV(sm,vid[2])); |
1394 |
if(s0 < S_REPLACE_SCALE*d20) |
1395 |
return(TRUE); |
1396 |
d = MIN3(d01,d12,d20); |
1397 |
s1 = DOT(diff[1],diff[1]); |
1398 |
if(s1 < S_REPLACE_SCALE*d) |
1399 |
return(TRUE); |
1400 |
s2 = DOT(diff[2],diff[2]); |
1401 |
if(s2 < S_REPLACE_SCALE*d) |
1402 |
return(TRUE); |
1403 |
|
1404 |
/* TEST 5: |
1405 |
Check to see if triangle is relatively large and should therefore |
1406 |
be subdivided anyway. |
1407 |
*/ |
1408 |
dv *= DIST_SQ(SM_NTH_WV(sm,vid[1]),SM_VIEW_CENTER(sm)); |
1409 |
dv *= DIST_SQ(SM_NTH_WV(sm,vid[2]),SM_VIEW_CENTER(sm)); |
1410 |
if (d01*d12*d20/dv > S_REPLACE_TRI) |
1411 |
return(TRUE); |
1412 |
|
1413 |
return(FALSE); |
1414 |
} |
1415 |
|
1416 |
|
1417 |
int |
1418 |
smAlloc_samp(sm) |
1419 |
SM *sm; |
1420 |
{ |
1421 |
int s_id,replaced,cnt; |
1422 |
SAMP *s; |
1423 |
FVECT p; |
1424 |
|
1425 |
s = SM_SAMP(sm); |
1426 |
s_id = sAlloc_samp(s,&replaced); |
1427 |
|
1428 |
cnt=0; |
1429 |
while(replaced) |
1430 |
{ |
1431 |
if(smRemoveVertex(sm,s_id)) |
1432 |
break; |
1433 |
s_id = sAlloc_samp(s,&replaced); |
1434 |
cnt++; |
1435 |
if(cnt > S_MAX_SAMP(s)) |
1436 |
error(CONSISTENCY,"smAlloc_samp():unable to find free samp\n"); |
1437 |
} |
1438 |
return(s_id); |
1439 |
} |
1440 |
|
1441 |
int |
1442 |
smReplace_samp(sm,c,dir,p,s_id,t_id,o_id,on,which) |
1443 |
SM *sm; |
1444 |
COLR c; |
1445 |
FVECT dir,p; |
1446 |
int s_id,t_id,o_id,on,which; |
1447 |
{ |
1448 |
int tonemap,v_id; |
1449 |
TRI *t,*tri; |
1450 |
|
1451 |
tri = SM_NTH_TRI(sm,t_id); |
1452 |
v_id = T_NTH_V(tri,which); |
1453 |
|
1454 |
/* If it is a base id, need new sample */ |
1455 |
if(SM_BASE_ID(sm,v_id)) |
1456 |
{ |
1457 |
tonemap = (SM_TONE_MAP(sm) > s_id); |
1458 |
sInit_samp(SM_SAMP(sm),s_id,c,dir,p,o_id,tonemap); |
1459 |
SM_NTH_VERT(sm,s_id) = t_id; |
1460 |
T_NTH_V(tri,which) = s_id; |
1461 |
if(!(SM_BASE_ID(sm,T_NTH_V(tri,(which+1)%3)) || |
1462 |
SM_BASE_ID(sm,T_NTH_V(tri,(which+2)%3)))) |
1463 |
SM_CLR_NTH_T_BASE(sm,t_id); |
1464 |
t_id = smTri_next_ccw_nbr(sm,tri,v_id); |
1465 |
while(t_id != INVALID) |
1466 |
{ |
1467 |
t = SM_NTH_TRI(sm,t_id); |
1468 |
which = T_WHICH_V(t,v_id); |
1469 |
T_NTH_V(t,which) = s_id; |
1470 |
/* Check if still a base triangle */ |
1471 |
if(!(SM_BASE_ID(sm,T_NTH_V(t,(which+1)%3)) || |
1472 |
SM_BASE_ID(sm,T_NTH_V(t,(which+2)%3)))) |
1473 |
SM_CLR_NTH_T_BASE(sm,t_id); |
1474 |
t_id = smTri_next_ccw_nbr(sm,t,v_id); |
1475 |
} |
1476 |
return(s_id); |
1477 |
} |
1478 |
else |
1479 |
if(on == ON_V || !p) |
1480 |
{ |
1481 |
tonemap = (SM_TONE_MAP(sm) > v_id); |
1482 |
sInit_samp(SM_SAMP(sm),v_id,c,dir,p,o_id,tonemap); |
1483 |
return(v_id); |
1484 |
} |
1485 |
else /* on == ON_P */ |
1486 |
{ |
1487 |
FVECT spt,npt; |
1488 |
double d,d2; |
1489 |
|
1490 |
/* Need to check which sample is preferable */ |
1491 |
VSUB(spt,p,SM_VIEW_CENTER(sm)); |
1492 |
normalize(spt); |
1493 |
|
1494 |
VSUB(npt,SM_NTH_WV(sm,v_id),SM_VIEW_CENTER(sm)); |
1495 |
normalize(npt); |
1496 |
d = fdir2diff(SM_NTH_W_DIR(sm,v_id), npt); |
1497 |
d2 = 2. - 2.*DOT(dir,spt); |
1498 |
/* The existing sample is a better sample:punt */ |
1499 |
if(d2 < d) |
1500 |
{ |
1501 |
/* The new sample has better information- replace values */ |
1502 |
tonemap = (SM_TONE_MAP(sm) > v_id); |
1503 |
sInit_samp(SM_SAMP(sm),v_id,c,dir,p,o_id,tonemap); |
1504 |
} |
1505 |
return(v_id); |
1506 |
} |
1507 |
} |
1508 |
|
1509 |
/* Add sample to the mesh: |
1510 |
|
1511 |
the sample can be a world space or directional point. If o_id !=INVALID, |
1512 |
then we have an existing sample containing the appropriate information |
1513 |
already converted into storage format. |
1514 |
The spherical projection of the point/ray can: |
1515 |
a) coincide with existing vertex |
1516 |
i) conincides with existing sample |
1517 |
ii) projects same as existing sample |
1518 |
iii) hits a base vertex |
1519 |
b) coincide with existing edge |
1520 |
c) Fall in existing triangle |
1521 |
*/ |
1522 |
int |
1523 |
smAdd_samp(sm,c,dir,p,o_id) |
1524 |
SM *sm; |
1525 |
COLR c; |
1526 |
FVECT dir,p; |
1527 |
int o_id; |
1528 |
{ |
1529 |
int t_id,s_id,r_id,on,which,n_id; |
1530 |
double d; |
1531 |
FVECT wpt; |
1532 |
|
1533 |
r_id = INVALID; |
1534 |
|
1535 |
/* Must do this first-as may change mesh */ |
1536 |
s_id = smAlloc_samp(sm); |
1537 |
/* If sample is a world space point */ |
1538 |
if(p) |
1539 |
{ |
1540 |
t_id = smPointLocateTri(sm,p,&on,&which); |
1541 |
if(t_id == INVALID) |
1542 |
{ |
1543 |
#ifdef DEBUG |
1544 |
eputs("smAddSamp(): unable to locate tri containing sample \n"); |
1545 |
#endif |
1546 |
smUnalloc_samp(sm,s_id); |
1547 |
return(INVALID); |
1548 |
} |
1549 |
/* If spherical projection coincides with existing sample: replace */ |
1550 |
if((on == ON_V || on == ON_P)) |
1551 |
{ |
1552 |
if((n_id = smReplace_samp(sm,c,dir,p,s_id,t_id,o_id,on,which))!= s_id) |
1553 |
smUnalloc_samp(sm,s_id); |
1554 |
return(n_id); |
1555 |
} |
1556 |
if((!(smTest_sample(sm,t_id,dir,p,&r_id)))) |
1557 |
{ |
1558 |
smUnalloc_samp(sm,s_id); |
1559 |
return(INVALID); |
1560 |
} |
1561 |
/* If sample is being added in the middle of the sample array: tone |
1562 |
map individually |
1563 |
*/ |
1564 |
/* Initialize sample */ |
1565 |
sInit_samp(SM_SAMP(sm),s_id,c,dir,p,o_id,(SM_TONE_MAP(sm)>s_id)); |
1566 |
|
1567 |
} |
1568 |
/* If sample is a direction vector */ |
1569 |
else |
1570 |
{ |
1571 |
VADD(wpt,dir,SM_VIEW_CENTER(sm)); |
1572 |
t_id = smPointLocateTri(sm,wpt,&on,&which); |
1573 |
if(t_id == INVALID) |
1574 |
{ |
1575 |
#ifdef DEBUG |
1576 |
eputs("smAddSamp(): unable to locate tri containing sample \n"); |
1577 |
#endif |
1578 |
smUnalloc_samp(sm,s_id); |
1579 |
return(INVALID); |
1580 |
} |
1581 |
if(on == ON_V || on == ON_P) |
1582 |
{ |
1583 |
if((n_id = smReplace_samp(sm,c,wpt,NULL,s_id,t_id,o_id,on,which))!= s_id) |
1584 |
smUnalloc_samp(sm,s_id); |
1585 |
return(n_id); |
1586 |
} |
1587 |
/* Allocate space for a sample and initialize */ |
1588 |
sInit_samp(SM_SAMP(sm),s_id,c,wpt,NULL,o_id,(SM_TONE_MAP(sm)>s_id)); |
1589 |
} |
1590 |
if(!SM_DIR_ID(sm,s_id)) |
1591 |
{ |
1592 |
/* If not a base or sky point, add distance from the |
1593 |
viewcenter to average*/ |
1594 |
d = DIST(SM_NTH_WV(sm,s_id),SM_VIEW_CENTER(sm)); |
1595 |
smDist_sum += 1.0/d; |
1596 |
} |
1597 |
smInsert_samp(sm,s_id,t_id,on,which); |
1598 |
|
1599 |
/* If new sample replaces existing one- remove that vertex now */ |
1600 |
if(r_id != INVALID) |
1601 |
{ |
1602 |
smRemoveVertex(sm,r_id); |
1603 |
sDelete_samp(SM_SAMP(sm),r_id); |
1604 |
} |
1605 |
return(s_id); |
1606 |
} |
1607 |
|
1608 |
/* |
1609 |
* int |
1610 |
* smNewSamp(c, dir, p) : register new sample point and return index |
1611 |
* COLR c; : pixel color (RGBE) |
1612 |
* FVECT dir; : ray direction vector |
1613 |
* FVECT p; : world intersection point |
1614 |
* |
1615 |
* Add new sample point to data structures, removing old values as necessary. |
1616 |
* New sample representation will be output in next call to smUpdate(). |
1617 |
* If the point is a sky point: then v=NULL |
1618 |
*/ |
1619 |
int |
1620 |
smNewSamp(c,dir,p) |
1621 |
COLR c; |
1622 |
FVECT dir; |
1623 |
FVECT p; |
1624 |
{ |
1625 |
int s_id; |
1626 |
|
1627 |
|
1628 |
/* First check if this the first sample: if so initialize mesh */ |
1629 |
|
1630 |
if(SM_NUM_SAMP(smMesh) == 0) |
1631 |
{ |
1632 |
smInit_sm(smMesh,odev.v.vp); |
1633 |
sClear_all_flags(SM_SAMP(smMesh)); |
1634 |
} |
1635 |
/* Add the sample to the mesh */ |
1636 |
s_id = smAdd_samp(smMesh,c,dir,p,INVALID); |
1637 |
|
1638 |
return(s_id); |
1639 |
|
1640 |
} |
1641 |
int |
1642 |
smAdd_base_vertex(sm,v) |
1643 |
SM *sm; |
1644 |
FVECT v; |
1645 |
{ |
1646 |
int id; |
1647 |
|
1648 |
/* First add coordinate to the sample array */ |
1649 |
id = sAdd_base_point(SM_SAMP(sm),v); |
1650 |
if(id == INVALID) |
1651 |
return(INVALID); |
1652 |
/* Initialize triangle pointer to -1 */ |
1653 |
smClear_vert(sm,id); |
1654 |
return(id); |
1655 |
} |
1656 |
|
1657 |
|
1658 |
|
1659 |
/* Initialize a the point location DAG based on a 6 triangle tesselation |
1660 |
of the unit sphere centered on the view center. The DAG structure |
1661 |
contains 6 roots: one for each initial base triangle |
1662 |
*/ |
1663 |
|
1664 |
int |
1665 |
smCreate_base_mesh(sm,type) |
1666 |
SM *sm; |
1667 |
int type; |
1668 |
{ |
1669 |
int i,s_id,tri_id,nbr_id; |
1670 |
int p[SM_EXTRA_POINTS],ids[SM_BASE_TRIS]; |
1671 |
int v0_id,v1_id,v2_id; |
1672 |
FVECT d,pt,cntr,v0,v1,v2; |
1673 |
TRI *t; |
1674 |
|
1675 |
/* First insert the base vertices into the sample point array */ |
1676 |
|
1677 |
for(i=0; i < SM_EXTRA_POINTS; i++) |
1678 |
{ |
1679 |
VADD(cntr,icosa_verts[i],SM_VIEW_CENTER(sm)); |
1680 |
p[i] = smAdd_base_vertex(sm,cntr); |
1681 |
} |
1682 |
/* Create the base triangles */ |
1683 |
for(i=0;i < SM_BASE_TRIS; i++) |
1684 |
{ |
1685 |
v0_id = p[icosa_tris[i][0]]; |
1686 |
v1_id = p[icosa_tris[i][1]]; |
1687 |
v2_id = p[icosa_tris[i][2]]; |
1688 |
ids[i] = smAdd_tri(sm, v0_id,v1_id,v2_id); |
1689 |
/* Set neighbors */ |
1690 |
for(nbr_id=0; nbr_id < 3; nbr_id++) |
1691 |
T_NTH_NBR(SM_NTH_TRI(sm,ids[i]),nbr_id) = icosa_nbrs[i][nbr_id]; |
1692 |
|
1693 |
} |
1694 |
for(i=0;i < SM_BASE_TRIS; i++) |
1695 |
{ |
1696 |
t = SM_NTH_TRI(sm,ids[i]); |
1697 |
smLocator_add_tri(sm,ids[i],T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2)); |
1698 |
} |
1699 |
return(1); |
1700 |
|
1701 |
} |
1702 |
|
1703 |
|
1704 |
int |
1705 |
smNext_tri_flag_set(sm,i,which,b) |
1706 |
SM *sm; |
1707 |
int i,which; |
1708 |
int b; |
1709 |
{ |
1710 |
|
1711 |
for(; i < SM_NUM_TRI(sm);i++) |
1712 |
{ |
1713 |
|
1714 |
if(!T_IS_VALID(SM_NTH_TRI(sm,i))) |
1715 |
continue; |
1716 |
if(!SM_IS_NTH_T_FLAG(sm,i,which)) |
1717 |
continue; |
1718 |
if(!b) |
1719 |
break; |
1720 |
if((b==1) && !SM_BG_TRI(sm,i)) |
1721 |
break; |
1722 |
if((b==2) && SM_BG_TRI(sm,i)) |
1723 |
break; |
1724 |
} |
1725 |
|
1726 |
return(i); |
1727 |
} |
1728 |
|
1729 |
|
1730 |
int |
1731 |
smNext_valid_tri(sm,i) |
1732 |
SM *sm; |
1733 |
int i; |
1734 |
{ |
1735 |
|
1736 |
while( i < SM_NUM_TRI(sm) && !T_IS_VALID(SM_NTH_TRI(sm,i))) |
1737 |
i++; |
1738 |
|
1739 |
return(i); |
1740 |
} |
1741 |
|
1742 |
|
1743 |
|
1744 |
qtTri_from_id(t_id,v0,v1,v2) |
1745 |
int t_id; |
1746 |
FVECT v0,v1,v2; |
1747 |
{ |
1748 |
TRI *t; |
1749 |
|
1750 |
t = SM_NTH_TRI(smMesh,t_id); |
1751 |
if(!T_IS_VALID(t)) |
1752 |
return(0); |
1753 |
VSUB(v0,SM_T_NTH_WV(smMesh,t,0),SM_VIEW_CENTER(smMesh)); |
1754 |
VSUB(v1,SM_T_NTH_WV(smMesh,t,1),SM_VIEW_CENTER(smMesh)); |
1755 |
VSUB(v2,SM_T_NTH_WV(smMesh,t,2),SM_VIEW_CENTER(smMesh)); |
1756 |
return(1); |
1757 |
} |
1758 |
|
1759 |
|
1760 |
smRebuild_mesh(sm,v) |
1761 |
SM *sm; |
1762 |
VIEW *v; |
1763 |
{ |
1764 |
int i,j,cnt; |
1765 |
FVECT p,ov,dir; |
1766 |
double d; |
1767 |
|
1768 |
#ifdef DEBUG |
1769 |
fprintf(stderr,"smRebuild_mesh(): rebuilding...."); |
1770 |
#endif |
1771 |
/* Clear the mesh- and rebuild using the current sample array */ |
1772 |
/* Remember the current number of samples */ |
1773 |
cnt = SM_NUM_SAMP(sm); |
1774 |
/* Calculate the difference between the current and new viewpoint*/ |
1775 |
/* Will need to subtract this off of sky points */ |
1776 |
VCOPY(ov,SM_VIEW_CENTER(sm)); |
1777 |
/* Initialize the mesh to 0 samples and the base triangles */ |
1778 |
|
1779 |
/* Go through all samples and add in if in the new view frustum, and |
1780 |
the dir is <= 30 degrees from new view |
1781 |
*/ |
1782 |
smInit_sm(sm,v->vp); |
1783 |
for(i=0; i < cnt; i++) |
1784 |
{ |
1785 |
/* First check if sample visible(conservative approx: if one of tris |
1786 |
attached to sample is in frustum) */ |
1787 |
if(!S_IS_FLAG(i)) |
1788 |
continue; |
1789 |
|
1790 |
/* Next test if direction > 30 from current direction */ |
1791 |
if(SM_NTH_W_DIR(sm,i)!=-1) |
1792 |
{ |
1793 |
VSUB(p,SM_NTH_WV(sm,i),v->vp); |
1794 |
normalize(p); |
1795 |
decodedir(dir,SM_NTH_W_DIR(sm,i)); |
1796 |
d = 2. - 2.*DOT(dir,p); |
1797 |
if (d > MAXDIFF2) |
1798 |
continue; |
1799 |
VCOPY(p,SM_NTH_WV(sm,i)); |
1800 |
smAdd_samp(sm,NULL,dir,p,i); |
1801 |
} |
1802 |
else |
1803 |
{ |
1804 |
VSUB(dir,SM_NTH_WV(sm,i),ov); |
1805 |
VADD(SM_NTH_WV(sm,i),dir,SM_VIEW_CENTER(sm)); |
1806 |
smAdd_samp(sm,NULL,dir,NULL,i); |
1807 |
} |
1808 |
|
1809 |
} |
1810 |
|
1811 |
smNew_tri_cnt = SM_SAMPLE_TRIS(sm); |
1812 |
#ifdef DEBUG |
1813 |
fprintf(stderr,"smRebuild_mesh():done\n"); |
1814 |
#endif |
1815 |
} |
1816 |
|
1817 |
int |
1818 |
intersect_tri_set(t_set,orig,dir,pt) |
1819 |
OBJECT *t_set; |
1820 |
FVECT orig,dir,pt; |
1821 |
{ |
1822 |
OBJECT *optr; |
1823 |
int i,t_id,id,base; |
1824 |
int pid0,pid1,pid2; |
1825 |
FVECT p0,p1,p2,p; |
1826 |
TRI *t; |
1827 |
double d,d1; |
1828 |
|
1829 |
optr = QT_SET_PTR(t_set); |
1830 |
for(i = QT_SET_CNT(t_set); i > 0; i--) |
1831 |
{ |
1832 |
t_id = QT_SET_NEXT_ELEM(optr); |
1833 |
t = SM_NTH_TRI(smMesh,t_id); |
1834 |
if(!T_IS_VALID(t)) |
1835 |
continue; |
1836 |
pid0 = T_NTH_V(t,0); |
1837 |
pid1 = T_NTH_V(t,1); |
1838 |
pid2 = T_NTH_V(t,2); |
1839 |
if(base = SM_IS_NTH_T_BASE(smMesh,t_id)) |
1840 |
if(SM_BASE_ID(smMesh,pid0) && SM_BASE_ID(smMesh,pid1) && |
1841 |
SM_BASE_ID(smMesh,pid2)) |
1842 |
continue; |
1843 |
VCOPY(p0,SM_NTH_WV(smMesh,pid0)); |
1844 |
VCOPY(p1,SM_NTH_WV(smMesh,pid1)); |
1845 |
VCOPY(p2,SM_NTH_WV(smMesh,pid2)); |
1846 |
if(ray_intersect_tri(orig,dir,p0,p1,p2,p)) |
1847 |
{ |
1848 |
if(!base) |
1849 |
{ |
1850 |
d = DIST_SQ(p,p0); |
1851 |
d1 = DIST_SQ(p,p1); |
1852 |
if(d < d1) |
1853 |
{ |
1854 |
d1 = DIST_SQ(p,p2); |
1855 |
id = (d1 < d)?pid2:pid0; |
1856 |
} |
1857 |
else |
1858 |
{ |
1859 |
d = DIST_SQ(p,p2); |
1860 |
id = (d < d1)? pid2:pid1; |
1861 |
} |
1862 |
} |
1863 |
else |
1864 |
{ |
1865 |
if(SM_BASE_ID(smMesh,pid0)) |
1866 |
{ |
1867 |
if(SM_BASE_ID(smMesh,pid1)) |
1868 |
id = pid2; |
1869 |
else |
1870 |
if(SM_BASE_ID(smMesh,pid2)) |
1871 |
id = pid1; |
1872 |
else |
1873 |
{ |
1874 |
d = DIST_SQ(p,p1); |
1875 |
d1 = DIST_SQ(p,p2); |
1876 |
if(d < d1) |
1877 |
id = pid1; |
1878 |
else |
1879 |
id = pid2; |
1880 |
} |
1881 |
} |
1882 |
else |
1883 |
{ |
1884 |
if(SM_BASE_ID(smMesh,pid1)) |
1885 |
{ |
1886 |
if(SM_BASE_ID(smMesh,pid2)) |
1887 |
id = pid0; |
1888 |
else |
1889 |
{ |
1890 |
d = DIST_SQ(p,p0); |
1891 |
d1 = DIST_SQ(p,p2); |
1892 |
if(d < d1) |
1893 |
id = pid0; |
1894 |
else |
1895 |
id = pid2; |
1896 |
} |
1897 |
} |
1898 |
else |
1899 |
{ |
1900 |
d = DIST_SQ(p,p0); |
1901 |
d1 = DIST_SQ(p,p1); |
1902 |
if(d < d1) |
1903 |
id = pid0; |
1904 |
else |
1905 |
id = pid1; |
1906 |
} |
1907 |
} |
1908 |
} |
1909 |
if(pt) |
1910 |
VCOPY(pt,p); |
1911 |
#ifdef TEST_DRIVER |
1912 |
Pick_tri = t_id; |
1913 |
Pick_samp = id; |
1914 |
VCOPY(Pick_point[0],p); |
1915 |
#endif |
1916 |
return(id); |
1917 |
} |
1918 |
} |
1919 |
return(-1); |
1920 |
} |
1921 |
|
1922 |
/* OS is constrained to be <= QT_MAXCSET : if the set exceeds this, the |
1923 |
results of check_set are conservative |
1924 |
*/ |
1925 |
int |
1926 |
compare_ids(id1,id2) |
1927 |
OBJECT *id1,*id2; |
1928 |
{ |
1929 |
int d; |
1930 |
|
1931 |
d = *id2-*id1; |
1932 |
|
1933 |
if(d > 0) |
1934 |
return(-1); |
1935 |
if(d < 0) |
1936 |
return(1); |
1937 |
|
1938 |
return(0); |
1939 |
} |
1940 |
|
1941 |
ray_trace_check_set(qt,argptr,fptr) |
1942 |
QUADTREE qt; |
1943 |
RT_ARGS *argptr; |
1944 |
int *fptr; |
1945 |
{ |
1946 |
OBJECT tset[QT_MAXSET+1],*tptr; |
1947 |
double dt,t; |
1948 |
int found; |
1949 |
if(QT_IS_EMPTY(qt)) |
1950 |
return; |
1951 |
if(QT_LEAF_IS_FLAG(qt)) |
1952 |
{ |
1953 |
QT_FLAG_SET_DONE(*fptr); |
1954 |
#if DEBUG |
1955 |
eputs("ray_trace_check_set():Already visited this node:aborting\n"); |
1956 |
#endif |
1957 |
return; |
1958 |
} |
1959 |
else |
1960 |
QT_LEAF_SET_FLAG(qt); |
1961 |
|
1962 |
tptr = qtqueryset(qt); |
1963 |
if(QT_SET_CNT(tptr) > QT_MAXSET) |
1964 |
tptr = (OBJECT *)malloc((QT_SET_CNT(tptr)+1)*sizeof(OBJECT)); |
1965 |
else |
1966 |
tptr = tset; |
1967 |
if(!tptr) |
1968 |
goto memerr; |
1969 |
|
1970 |
qtgetset(tptr,qt); |
1971 |
/* Must sort */ |
1972 |
qsort((void *)(&(tptr[1])),tptr[0],sizeof(OBJECT),compare_ids); |
1973 |
/* Check triangles in set against those seen so far(os):only |
1974 |
check new triangles for intersection (t_set') |
1975 |
*/ |
1976 |
check_set_large(tptr,argptr->os); |
1977 |
|
1978 |
if(!QT_SET_CNT(tptr)) |
1979 |
return; |
1980 |
found = intersect_tri_set(tptr,argptr->orig,argptr->dir,NULL); |
1981 |
if(tptr != tset) |
1982 |
free(tptr); |
1983 |
if(found != INVALID) |
1984 |
{ |
1985 |
argptr->t_id = found; |
1986 |
QT_FLAG_SET_DONE(*fptr); |
1987 |
} |
1988 |
return; |
1989 |
memerr: |
1990 |
error(SYSTEM,"ray_trace_check_set():Unable to allocate memory"); |
1991 |
} |
1992 |
|
1993 |
|
1994 |
/* |
1995 |
* int |
1996 |
* smFindSamp(FVECT orig, FVECT dir) |
1997 |
* |
1998 |
* Find the closest sample to the given ray. Returns sample id, -1 on failure. |
1999 |
* "dir" is assumed to be normalized |
2000 |
*/ |
2001 |
|
2002 |
int |
2003 |
smFindSamp(orig,dir) |
2004 |
FVECT orig,dir; |
2005 |
{ |
2006 |
FVECT b,p,o; |
2007 |
OBJECT *ts; |
2008 |
QUADTREE qt; |
2009 |
int s_id,test; |
2010 |
double d; |
2011 |
|
2012 |
/* r is the normalized vector from the view center to the current |
2013 |
* ray point ( starting with "orig"). Find the cell that r falls in, |
2014 |
* and test the ray against all triangles stored in the cell. If |
2015 |
* the test fails, trace the projection of the ray across to the |
2016 |
* next cell it intersects: iterate until either an intersection |
2017 |
* is found, or the projection ray is // to the direction. The sample |
2018 |
* corresponding to the triangle vertex closest to the intersection |
2019 |
* point is returned. |
2020 |
*/ |
2021 |
|
2022 |
/* First test if "orig" coincides with the View_center or if "dir" is |
2023 |
parallel to r formed by projecting "orig" on the sphere. In |
2024 |
either case, do a single test against the cell containing the |
2025 |
intersection of "dir" and the sphere |
2026 |
*/ |
2027 |
/* orig will be updated-so preserve original value */ |
2028 |
if(!smMesh) |
2029 |
return; |
2030 |
#ifdef TEST_DRIVER |
2031 |
Picking= TRUE; |
2032 |
#endif |
2033 |
|
2034 |
if(EQUAL_VEC3(orig,SM_VIEW_CENTER(smMesh))) |
2035 |
{ |
2036 |
qt = smPointLocateCell(smMesh,dir); |
2037 |
if(QT_IS_EMPTY(qt)) |
2038 |
goto Lerror; |
2039 |
ts = qtqueryset(qt); |
2040 |
s_id = intersect_tri_set(ts,orig,dir,p); |
2041 |
#ifdef DEBUG_TEST_DRIVER |
2042 |
VCOPY(Pick_point[0],p); |
2043 |
#endif |
2044 |
#ifdef DEBUG |
2045 |
fprintf(stderr,"Simple pick returning %d\n",s_id); |
2046 |
#endif |
2047 |
|
2048 |
return(s_id); |
2049 |
} |
2050 |
d = point_on_sphere(b,orig,SM_VIEW_CENTER(smMesh)); |
2051 |
if(EQUAL_VEC3(b,dir)) |
2052 |
{ |
2053 |
qt = smPointLocateCell(smMesh,dir); |
2054 |
if(QT_IS_EMPTY(qt)) |
2055 |
goto Lerror; |
2056 |
ts = qtqueryset(qt); |
2057 |
s_id = intersect_tri_set(ts,orig,dir,p); |
2058 |
#ifdef DEBUG_TEST_DRIVER |
2059 |
VCOPY(Pick_point[0],p); |
2060 |
#endif |
2061 |
#ifdef DEBUG |
2062 |
fprintf(stderr,"Simple pick2 returning %d\n",s_id); |
2063 |
#endif |
2064 |
return(s_id); |
2065 |
} |
2066 |
if(OPP_EQUAL_VEC3(b,dir)) |
2067 |
{ |
2068 |
qt = smPointLocateCell(smMesh,orig); |
2069 |
if(QT_IS_EMPTY(qt)) |
2070 |
goto Lerror; |
2071 |
ts = qtqueryset(qt); |
2072 |
s_id = intersect_tri_set(ts,orig,dir,p); |
2073 |
#ifdef DEBUG_TEST_DRIVER |
2074 |
VCOPY(Pick_point[0],p); |
2075 |
#endif |
2076 |
if(s_id != INVALID) |
2077 |
{ |
2078 |
#ifdef DEBUG |
2079 |
fprintf(stderr,"Front pick returning %d\n",s_id); |
2080 |
#endif |
2081 |
return(s_id); |
2082 |
} |
2083 |
qt = smPointLocateCell(smMesh,dir); |
2084 |
if(QT_IS_EMPTY(qt)) |
2085 |
goto Lerror; |
2086 |
ts = qtqueryset(qt); |
2087 |
s_id = intersect_tri_set(ts,orig,dir,p); |
2088 |
#ifdef DEBUG_TEST_DRIVER |
2089 |
VCOPY(Pick_point[0],p); |
2090 |
#endif |
2091 |
#ifdef DEBUG |
2092 |
fprintf(stderr,"Back pick returning %d\n",s_id); |
2093 |
#endif |
2094 |
return(s_id); |
2095 |
} |
2096 |
{ |
2097 |
OBJECT t_set[QT_MAXCSET + 1]; |
2098 |
RT_ARGS rt; |
2099 |
FUNC func; |
2100 |
|
2101 |
/* Test each of the root triangles against point id */ |
2102 |
QT_CLEAR_SET(t_set); |
2103 |
VSUB(o,orig,SM_VIEW_CENTER(smMesh)); |
2104 |
ST_CLEAR_FLAGS(SM_LOCATOR(smMesh)); |
2105 |
rt.t_id = -1; |
2106 |
rt.os = t_set; |
2107 |
VCOPY(rt.orig,orig); |
2108 |
VCOPY(rt.dir,dir); |
2109 |
F_FUNC(func) = ray_trace_check_set; |
2110 |
F_ARGS(func) = (int *)(&rt); |
2111 |
stTrace_ray(SM_LOCATOR(smMesh),o,dir,func); |
2112 |
s_id = rt.t_id; |
2113 |
} |
2114 |
#ifdef DEBUG |
2115 |
fprintf(stderr,"Trace pick returning %d\n",s_id); |
2116 |
#endif |
2117 |
return(s_id); |
2118 |
|
2119 |
Lerror: |
2120 |
#ifdef DEBUG |
2121 |
eputs("smFindSamp(): point not found"); |
2122 |
#endif |
2123 |
return(INVALID); |
2124 |
|
2125 |
} |
2126 |
|
2127 |
|
2128 |
mark_active_tris(argptr,root,qt) |
2129 |
int *argptr; |
2130 |
int root; |
2131 |
QUADTREE qt; |
2132 |
{ |
2133 |
OBJECT *os,*optr; |
2134 |
register int i,t_id; |
2135 |
TRI *tri; |
2136 |
|
2137 |
if(QT_IS_EMPTY(qt) || QT_LEAF_IS_FLAG(qt)) |
2138 |
return; |
2139 |
|
2140 |
/* For each triangle in the set, set the which flag*/ |
2141 |
os = qtqueryset(qt); |
2142 |
|
2143 |
for (i = QT_SET_CNT(os), optr = QT_SET_PTR(os); i > 0; i--) |
2144 |
{ |
2145 |
t_id = QT_SET_NEXT_ELEM(optr); |
2146 |
/* Set the render flag */ |
2147 |
tri = SM_NTH_TRI(smMesh,t_id); |
2148 |
if(!T_IS_VALID(tri) || SM_IS_NTH_T_BASE(smMesh,t_id)) |
2149 |
continue; |
2150 |
SM_SET_NTH_T_ACTIVE(smMesh,t_id); |
2151 |
/* Set the Active bits of the Vertices */ |
2152 |
S_SET_FLAG(T_NTH_V(tri,0)); |
2153 |
S_SET_FLAG(T_NTH_V(tri,1)); |
2154 |
S_SET_FLAG(T_NTH_V(tri,2)); |
2155 |
} |
2156 |
} |
2157 |
|
2158 |
|
2159 |
mark_tris_in_frustum(view) |
2160 |
VIEW *view; |
2161 |
{ |
2162 |
FVECT nr[4],far[4]; |
2163 |
FPEQ peq; |
2164 |
int debug=0; |
2165 |
FUNC f; |
2166 |
|
2167 |
F_FUNC(f) = mark_active_tris; |
2168 |
F_ARGS(f) = NULL; |
2169 |
|
2170 |
/* Mark triangles in approx. view frustum as being active:set |
2171 |
LRU counter: for use in discarding samples when out |
2172 |
of space |
2173 |
Radiance often has no far clipping plane: but driver will set |
2174 |
dev_zmin,dev_zmax to satisfy OGL |
2175 |
*/ |
2176 |
|
2177 |
/* First clear all the quadtree node and triangle active flags */ |
2178 |
qtClearAllFlags(); |
2179 |
smClear_flags(smMesh,T_ACTIVE_FLAG); |
2180 |
/* Clear all of the active sample flags*/ |
2181 |
sClear_all_flags(SM_SAMP(smMesh)); |
2182 |
|
2183 |
|
2184 |
/* calculate the world space coordinates of the view frustum */ |
2185 |
calculate_view_frustum(view->vp,view->hvec,view->vvec,view->horiz, |
2186 |
view->vert, dev_zmin,dev_zmax,nr,far); |
2187 |
|
2188 |
#ifdef TEST_DRIVER |
2189 |
VCOPY(FrustumFar[0],far[0]); |
2190 |
VCOPY(FrustumFar[1],far[1]); |
2191 |
VCOPY(FrustumFar[2],far[2]); |
2192 |
VCOPY(FrustumFar[3],far[3]); |
2193 |
VCOPY(FrustumNear[0],nr[0]); |
2194 |
VCOPY(FrustumNear[1],nr[1]); |
2195 |
VCOPY(FrustumNear[2],nr[2]); |
2196 |
VCOPY(FrustumNear[3],nr[3]); |
2197 |
#endif |
2198 |
/* Project the view frustum onto the spherical quadtree */ |
2199 |
/* For every cell intersected by the projection of the faces |
2200 |
|
2201 |
of the frustum: mark all triangles in the cell as ACTIVE- |
2202 |
Also set the triangles LRU clock counter |
2203 |
*/ |
2204 |
|
2205 |
if(EQUAL_VEC3(view->vp,SM_VIEW_CENTER(smMesh))) |
2206 |
{/* Near face triangles */ |
2207 |
|
2208 |
smLocator_apply(smMesh,nr[0],nr[2],nr[3],f); |
2209 |
smLocator_apply(smMesh,nr[2],nr[0],nr[1],f); |
2210 |
return; |
2211 |
} |
2212 |
/* Test the view against the planes: and swap orientation if inside:*/ |
2213 |
tri_plane_equation(nr[0],nr[2],nr[3], &peq,FALSE); |
2214 |
if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) |
2215 |
{/* Near face triangles */ |
2216 |
smLocator_apply(smMesh,nr[3],nr[2],nr[0],f); |
2217 |
smLocator_apply(smMesh,nr[1],nr[0],nr[2],f); |
2218 |
} |
2219 |
else |
2220 |
{/* Near face triangles */ |
2221 |
smLocator_apply(smMesh,nr[0],nr[2],nr[3],f); |
2222 |
smLocator_apply(smMesh,nr[2],nr[0],nr[1],f); |
2223 |
} |
2224 |
tri_plane_equation(nr[0],far[3],far[0], &peq,FALSE); |
2225 |
if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) |
2226 |
{ /* Right face triangles */ |
2227 |
smLocator_apply(smMesh,far[0],far[3],nr[0],f); |
2228 |
smLocator_apply(smMesh,nr[3],nr[0],far[3],f); |
2229 |
} |
2230 |
else |
2231 |
{/* Right face triangles */ |
2232 |
smLocator_apply(smMesh,nr[0],far[3],far[0],f); |
2233 |
smLocator_apply(smMesh,far[3],nr[0],nr[3],f); |
2234 |
} |
2235 |
|
2236 |
tri_plane_equation(nr[1],far[2],nr[2], &peq,FALSE); |
2237 |
if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) |
2238 |
{ /* Left face triangles */ |
2239 |
smLocator_apply(smMesh,nr[2],far[2],nr[1],f); |
2240 |
smLocator_apply(smMesh,far[1],nr[1],far[2],f); |
2241 |
} |
2242 |
else |
2243 |
{ /* Left face triangles */ |
2244 |
smLocator_apply(smMesh,nr[1],far[2],nr[2],f); |
2245 |
smLocator_apply(smMesh,far[2],nr[1],far[1],f); |
2246 |
} |
2247 |
tri_plane_equation(nr[0],far[0],nr[1], &peq,FALSE); |
2248 |
if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) |
2249 |
{/* Top face triangles */ |
2250 |
smLocator_apply(smMesh,nr[1],far[0],nr[0],f); |
2251 |
smLocator_apply(smMesh,far[1],far[0],nr[1],f); |
2252 |
} |
2253 |
else |
2254 |
{/* Top face triangles */ |
2255 |
smLocator_apply(smMesh,nr[0],far[0],nr[1],f); |
2256 |
smLocator_apply(smMesh,nr[1],far[0],far[1],f); |
2257 |
} |
2258 |
tri_plane_equation(nr[3],nr[2],far[3], &peq,FALSE); |
2259 |
if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) |
2260 |
{/* Bottom face triangles */ |
2261 |
smLocator_apply(smMesh,far[3],nr[2],nr[3],f); |
2262 |
smLocator_apply(smMesh,far[3],far[2],nr[2],f); |
2263 |
} |
2264 |
else |
2265 |
{ /* Bottom face triangles */ |
2266 |
smLocator_apply(smMesh,nr[3],nr[2],far[3],f); |
2267 |
smLocator_apply(smMesh,nr[2],far[2],far[3],f); |
2268 |
} |
2269 |
tri_plane_equation(far[2],far[0],far[1], &peq,FALSE); |
2270 |
if(PT_ON_PLANE(SM_VIEW_CENTER(smMesh),peq) < 0.0) |
2271 |
{/* Far face triangles */ |
2272 |
smLocator_apply(smMesh,far[0],far[2],far[1],f); |
2273 |
smLocator_apply(smMesh,far[2],far[0],far[3],f); |
2274 |
} |
2275 |
else |
2276 |
{/* Far face triangles */ |
2277 |
smLocator_apply(smMesh,far[1],far[2],far[0],f); |
2278 |
smLocator_apply(smMesh,far[3],far[0],far[2],f); |
2279 |
} |
2280 |
|
2281 |
} |
2282 |
|
2283 |
|
2284 |
|
2285 |
|
2286 |
|
2287 |
|
2288 |
|
2289 |
|
2290 |
|
2291 |
|