[ViewVC] Diff of: radiance/ray/src/hd/sm.c

Comparing ray/src/hd/sm.c (file contents):
Revision 3.8 by gwlarson, Tue Oct 6 18:16:54 1998 UTC vs.
Revision 3.14 by gwlarson, Fri Mar 5 16:33:17 1999 UTC

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

Diff Legend

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

Comparing ray/src/hd/sm.c (file contents): Revision 3.8 by gwlarson, Tue Oct 6 18:16:54 1998 UTC vs. Revision 3.14 by gwlarson, Fri Mar 5 16:33:17 1999 UTC

Diff Legend

Comparing ray/src/hd/sm.c (file contents):
Revision 3.8 by gwlarson, Tue Oct 6 18:16:54 1998 UTC vs.
Revision 3.14 by gwlarson, Fri Mar 5 16:33:17 1999 UTC