1 /***************************************
  2  * Copyright 2011, 2012 GlobWeb contributors.
  3  *
  4  * This file is part of GlobWeb.
  5  *
  6  * GlobWeb is free software: you can redistribute it and/or modify
  7  * it under the terms of the GNU Lesser General Public License as published by
  8  * the Free Software Foundation, version 3 of the License, or
  9  * (at your option) any later version.
 10  *
 11  * GlobWeb is distributed in the hope that it will be useful,
 12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 14  * GNU Lesser General Public License for more details.
 15  *
 16  * You should have received a copy of the GNU General Public License
 17  * along with GlobWeb. If not, see <http://www.gnu.org/licenses/>.
 18  ***************************************/
 19 
 20 define(['./Utils','./VectorRendererManager','./TiledVectorRenderable','./TiledVectorRenderer','./Numeric','./CoordinateSystem','./Triangulator'],
 21 	function(Utils,VectorRendererManager,TiledVectorRenderable,TiledVectorRenderer,Numeric,CoordinateSystem,Triangulator) {
 22 
 23 /**************************************************************************************************************/
 24 
 25 
 26 /** @constructor
 27  *	PolygonRenderable constructor
 28  */
 29 var PolygonRenderable = function( bucket, gl )
 30 {
 31 	TiledVectorRenderable.prototype.constructor.call(this,bucket,gl);
 32 	this.glMode = gl.TRIANGLES;
 33 }
 34 
 35 /**************************************************************************************************************/
 36 
 37 // Inheritance
 38 Utils.inherits(TiledVectorRenderable,PolygonRenderable);
 39 
 40 /**************************************************************************************************************/
 41 
 42 /**
 43  * Build children indices.
 44  * Children indices are used to render a tile children when it is not completely loaded.
 45  */
 46 PolygonRenderable.prototype.buildChildrenIndices = function( tile )
 47 {
 48 	this.childrenIndices = [ [], [], [], [] ];
 49 	this.childrenIndexBuffers = [ null, null, null, null ];
 50 }
 51 
 52 var PolygonCutter = function(points)
 53 {
 54 	this.points = points;
 55 	this.insidePolygons = [];
 56 	this.outsidePolygons = [];
 57 }
 58 
 59 PolygonCutter.prototype.reset = function()
 60 {
 61 	this.insidePolygons = [];
 62 	this.outsidePolygons = [];
 63 }
 64 	
 65 PolygonCutter.prototype._lineIntersection = function( p1, p2, p3, p4 )
 66 {
 67 	var x1 = p1[0];
 68 	var x2 = p2[0];
 69 	var x3 = p3[0];
 70 	var x4 = p4[0];
 71 	
 72 	var y1 = p1[1];
 73 	var y2 = p2[1];
 74 	var y3 = p3[1];
 75 	var y4 = p4[1];
 76 	
 77 	var det = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
 78 	if ( det == 0 )
 79 	{
 80 		var dist = this._pointLineDistance(p1,p2,p3);
 81 		if ( dist == 0 )
 82 		{
 83 			return [ 0, 0 ];
 84 		}
 85 		else
 86 		{
 87 			return [ -1, -1 ];
 88 		}
 89 	}
 90 	
 91 	var ua = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3);
 92 	var ub = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3);
 93 
 94 	ua /= det;
 95 	ub /= det;
 96 	
 97 	return [ ua, ub ];
 98 }
 99 
100 PolygonCutter.prototype._pointLineDistance = function( p, a , b )
101 {
102 	var ba0 = b[0] - a[0];
103 	var ba1 = b[1] - a[1];
104 	var abLength = Math.sqrt( ba0 * ba0 + ba1 * ba1 );
105 	return ((p[0] - a[0]) * ba1 - (p[1] - a[1]) * ba0) / abLength;
106 }
107 
108 PolygonCutter.prototype.cutMulti = function( polygons, a, b )
109 {
110 	this.reset();
111 	for ( var i = 0; i < polygons.length; i++ )
112 	{
113 		this._cut( polygons[i], a, b );
114 	}
115 }
116 
117 PolygonCutter.prototype.cut = function( polygon, a, b )
118 {
119 	this.reset();
120 	this._cut( polygon, a, b );
121 }
122 
123 PolygonCutter.prototype._cut = function( polygon, a, b )
124 {
125 	var EPS = 1e-6;
126 	if ( polygon.length < 3 )
127 	{
128 		return;
129 	}
130 		
131 	// Find all intersection between the line (a,b) and edges of polygon	
132 	var polygonWithIntersections = [];
133 	var intersections = [];
134 	
135 	for ( var i = 0; i < polygon.length - 1; i++ )
136 	{
137 		var p1 = this.points[ polygon[i] ];
138 		var p2 = this.points[ polygon[i+1] ];
139 		
140 		polygonWithIntersections.push( polygon[i] );
141 		
142 		var t = this._lineIntersection( a, b, p1, p2 );
143 		if ( t[1] > EPS && t[1] < 1.0 - EPS )
144 		{
145 			var newPoint = [ (1.0 - t[0]) * a[0] + t[0] * b[0], (1.0 - t[0]) * a[1] + t[0] * b[1] ];
146 			this.points.push( newPoint );
147 			var index = this.points.length-1;
148 			polygonWithIntersections.push( index );
149 			
150 			intersections.push( { index: polygonWithIntersections.length-1, t: t[0], crossIndex: -1, polygon: null } );
151 		} 
152 		else if ( Math.abs(t[1]) < EPS )
153 		{
154 			intersections.push( { index: polygonWithIntersections.length-1, t: t[0], crossIndex: -1, polygon: null } );
155 		}
156 	}
157 		
158 	// Sort intersections
159 	if ( intersections.length > 0 )
160 	{
161 		intersections.sort( function(a,b) { return a.t < b.t; } );
162 	}
163 	intersections.length = intersections.length & (~1);
164 		
165 	// Build cross
166 	var intersectionMap = new Array( polygonWithIntersections.length );
167 	for ( var i = 0; i < intersections.length; i+= 2 )
168 	{
169 		intersections[i].crossIndex = intersections[i+1].index;
170 		intersections[i+1].crossIndex = intersections[i].index;
171 		
172 		intersectionMap[ intersections[i].index ] = intersections[i];
173 		intersectionMap[ intersections[i+1].index ] = intersections[i+1];
174 	}
175 	
176 	var startIndex = 0;
177 	var firstPoint = this.points[ polygonWithIntersections[0] ];
178 	var dist = this._pointLineDistance(firstPoint,a,b);
179 	while (dist == 0)
180 	{
181 		startIndex++;
182 		firstPoint = this.points[ polygonWithIntersections[startIndex] ];
183 		dist = this._pointLineDistance(firstPoint,a,b);
184 	}
185 	
186 	// Builds outputPolygons
187 	var currentPolygons;
188 	var otherPolygons;
189 	if ( dist > 0 )
190 	{
191 		currentPolygons = this.insidePolygons;
192 		otherPolygons = this.outsidePolygons; 
193 	}
194 	else
195 	{
196 		currentPolygons = this.outsidePolygons;
197 		otherPolygons = this.insidePolygons; 
198 	}
199 	
200 	// Create a polygon and add it to the list
201 	var currentPolygon = [];
202 	currentPolygons.push( currentPolygon );
203 	
204 	for ( var i = 0; i < polygonWithIntersections.length; i++ )
205 	{
206 		var n = (i+startIndex) % polygonWithIntersections.length;
207 		var index = polygonWithIntersections[ n  ];
208 		currentPolygon.push( index );
209 		
210 		var intersection = intersectionMap[ n ];
211 		if ( intersection )
212 		{
213 			// Swap polygons 
214 			var temp = currentPolygons;
215 			currentPolygons = otherPolygons;
216 			otherPolygons = temp;
217 			
218 			var crossIntersection = intersectionMap[intersection.crossIndex];
219 			if ( !crossIntersection.polygon )
220 			{
221 				crossIntersection.polygon = currentPolygon;
222 			}
223 				
224 			if ( !intersection.polygon )
225 			{				
226 				// Create a new polygon
227 				var newPolygon = [];
228 				currentPolygons.push( newPolygon );
229 				
230 				intersection.polygon = newPolygon;
231 				
232 				currentPolygon = newPolygon;
233 			}
234 			else
235 			{
236 				currentPolygon = intersection.polygon;
237 			}
238 			
239 			currentPolygon.push( index );
240 		}
241 	}
242 	
243 	// Close all polygons
244 	for ( var i = 0; i < this.outsidePolygons.length; i++ )
245 	{
246 		var poly = this.outsidePolygons[i];
247 		poly.push( poly[0] );
248 	}
249 	for ( var i = 0; i < this.insidePolygons.length; i++ )
250 	{
251 		var poly = this.insidePolygons[i];
252 		poly.push( poly[0] );
253 	}
254 }
255 
256 var clipPolygonToTriGrid_O = function( polygons, points, a, b, c, level, res )
257 {
258 	if  ( level == 0 )
259 	{
260 		for ( var i = 0; i < polygons.length; i++ )
261 			res.push( polygons[i] );
262 		return;
263 	}
264 	
265 	var ab = [ (a[0] + b[0]) * 0.5, (a[1] + b[1]) * 0.5 ];
266 	var bc = [ (c[0] + b[0]) * 0.5, (c[1] + b[1]) * 0.5 ];
267 	var ca = [ (a[0] + c[0]) * 0.5, (a[1] + c[1]) * 0.5 ];
268 	
269 	var cutter = new PolygonCutter( points );
270 	cutter.cutMulti( polygons, bc, ab );
271 	
272 	if ( cutter.insidePolygons.length > 0 )
273 		clipPolygonToTriGrid_O( cutter.insidePolygons, points, bc, ab, b, level-1, res );
274 	
275 	if ( cutter.outsidePolygons.length > 0 )
276 	{
277 		cutter.cutMulti( cutter.outsidePolygons, ca, bc );
278 				
279 		if ( cutter.insidePolygons.length > 0 )
280 			clipPolygonToTriGrid_O( cutter.insidePolygons, points, ca, bc, c, level-1, res );
281 		
282 		if ( cutter.outsidePolygons.length > 0 )
283 		{
284 			cutter.cutMulti( cutter.outsidePolygons, ab, ca );
285 
286 			if ( cutter.insidePolygons.length > 0 ) clipPolygonToTriGrid_O( cutter.insidePolygons, points, ab, ca, a, level-1, res );
287 			if ( cutter.outsidePolygons.length > 0 ) clipPolygonToTriGrid_O( cutter.outsidePolygons, points, ca, ab, bc, level-1, res );
288 		}
289 	}
290 }
291 
292 var clipPolygonToTriGridStartUp = function( points, bounds, level )
293 {
294 	// Build an index polygon
295 	var poly = [];
296 	for ( var i = 0; i < points.length; i++ )
297 	{
298 		poly[i] = i;
299 	}
300 
301 	var cutter = new PolygonCutter( points );
302 	cutter.cut( poly, [ bounds[0], bounds[1] ], [ bounds[0], bounds[3] ] );
303 	cutter.cutMulti( cutter.insidePolygons, [ bounds[0], bounds[3] ], [ bounds[2], bounds[3] ] );
304 	cutter.cutMulti( cutter.insidePolygons, [ bounds[2], bounds[3] ], [ bounds[2], bounds[1] ] );
305 	cutter.cutMulti( cutter.insidePolygons, [ bounds[2], bounds[1] ], [ bounds[0], bounds[1] ] );
306 
307 //	return cutter.insidePolygons;
308 	
309 	cutter.cutMulti( cutter.insidePolygons, [ bounds[0], bounds[3] ], [ bounds[2], bounds[1] ] );
310 	var res = [];
311 	if ( cutter.insidePolygons.length > 0 ) clipPolygonToTriGrid_O( cutter.insidePolygons, points, [ bounds[0], bounds[1] ], [ bounds[0], bounds[3] ], [ bounds[2], bounds[1] ], level, res );
312 	if ( cutter.outsidePolygons.length > 0 ) clipPolygonToTriGrid_O( cutter.outsidePolygons, points, [ bounds[0], bounds[3] ], [ bounds[2], bounds[3] ], [ bounds[2], bounds[1] ], level, res );
313 	return res;
314 }
315 
316 /**************************************************************************************************************/
317 
318 /**
319  * Clamp a polygon on a tile
320  */
321 PolygonRenderable.prototype.buildVerticesAndIndices = function( tile, coordinates )
322 {
323 	//var coords = clipPolygon( coordinates, [ tile.geoBound.west, tile.geoBound.south, tile.geoBound.east, tile.geoBound.north ] );
324 	var points = coordinates.slice(0);
325 	var polygons = clipPolygonToTriGridStartUp( points, [ tile.geoBound.west, tile.geoBound.south, tile.geoBound.east, tile.geoBound.north ], 3 );
326 	if ( polygons.length > 0 )
327 	{
328 		for ( var n = 0; n < polygons.length; n++ )
329 		{
330 			var invMatrix = tile.inverseMatrix;
331 			var radius = CoordinateSystem.radius;
332 			var height = 100 * CoordinateSystem.heightScale;
333 			
334 			var vertexOffset = this.vertices.length;
335 			var indexOffset = this.vertices.length / 3;
336 			
337 			var coords = [];
338 			var polygon = polygons[n];
339 			for ( var i = 0; i < polygon.length; i++ )
340 			{
341 				coords[i] = points[ polygon[i] ];
342 				
343 				var cosLat = Math.cos( coords[i][1] * Math.PI / 180.0 );
344 				var x = (radius + height) * Math.cos( coords[i][0] * Math.PI / 180.0 ) * cosLat;
345 				var y = (radius + height) * Math.sin( coords[i][0] * Math.PI / 180.0 ) * cosLat;
346 				var z = (radius + height) * Math.sin( coords[i][1] * Math.PI / 180.0 );
347 				
348 				this.vertices[vertexOffset] = invMatrix[0]*x + invMatrix[4]*y + invMatrix[8]*z + invMatrix[12];
349 				this.vertices[vertexOffset+1] = invMatrix[1]*x + invMatrix[5]*y + invMatrix[9]*z + invMatrix[13];
350 				this.vertices[vertexOffset+2] = invMatrix[2]*x + invMatrix[6]*y + invMatrix[10]*z + invMatrix[14];
351 				
352 				vertexOffset += 3;
353 			}
354 			
355 			var tris = Triangulator.process( coords );
356 			if ( tris )
357 			{		
358 				for ( var i = 0; i < tris.length; i++ )
359 				{
360 					this.indices.push( tris[i] + indexOffset );
361 				}
362 			}
363 			else
364 			{
365 				console.log("Triangulation problem");
366 			}
367 		}
368 	}
369 }
370 
371 /**************************************************************************************************************/
372 
373 // Register the renderer
374 VectorRendererManager.registerRenderer({
375 	creator: function(globe) { 
376 			var polygonRenderer = new TiledVectorRenderer(globe.tileManager);
377 			polygonRenderer.id = "polygon";
378 			polygonRenderer.styleEquals = function(s1,s2) { return s1.isEqualForPoly(s2); };
379 			polygonRenderer.renderableConstuctor = PolygonRenderable;
380 			return polygonRenderer;
381 	},
382 	canApply: function(type,style) {return type == "Polygon" && style.fill; }
383 });
384 				
385 });
386