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

Diff Legend

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