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.6 by gwlarson, Mon Sep 14 10:33:46 1998 UTC vs.
Revision 3.11 by gwlarson, Wed Dec 30 13:44:15 1998 UTC

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

Diff Legend

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