ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/radiance/ray/src/hd/sm.c

Comparing ray/src/hd/sm.c (file contents):
Revision 3.4 by gwlarson, Tue Aug 25 11:03:27 1998 UTC vs.
Revision 3.13 by gwlarson, Sun Jan 10 10:27:48 1999 UTC

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

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines