openjscad-aurora-webapp

1
/*
2
## License
3

4
Copyright (c) 2013 Eduard Bespalov (edwbes@gmail.com): .solidFromSlices()
5
Copyright (c) 2013 Rene K. Mueller (http://OpenJSCAD.org): AMF export added, CSG.center([flag,flag,flag]);
6
Copyright (c) 2012 Joost Nieuwenhuijse (joost@newhouse.nl)
7
Copyright (c) 2012 Alexandre Girard (https://github.com/alx)
8
Copyright (c) 2011 Evan Wallace (http://evanw.github.com/csg.js/) -- original csg.js
9

10
All code released under MIT license
11

12
## Overview
13

14
For an overview of the CSG process see the original csg.js code:
15
http://evanw.github.com/csg.js/
16

17
CSG operations through BSP trees suffer from one problem: heavy fragmentation
18
of polygons. If two CSG solids of n polygons are unified, the resulting solid may have
19
in the order of n*n polygons, because each polygon is split by the planes of all other
20
polygons. After a few operations the number of polygons explodes.
21

22
This version of CSG.js solves the problem in 3 ways:
23

24
1. Every polygon split is recorded in a tree (CSG.PolygonTreeNode). This is a separate
25
tree, not to be confused with the CSG tree. If a polygon is split into two parts but in
26
the end both fragments have not been discarded by the CSG operation, we can retrieve
27
the original unsplit polygon from the tree, instead of the two fragments.
28

29
This does not completely solve the issue though: if a polygon is split multiple times
30
the number of fragments depends on the order of subsequent splits, and we might still
31
end up with unncessary splits:
32
Suppose a polygon is first split into A and B, and then into A1, B1, A2, B2. Suppose B2 is
33
discarded. We will end up with 2 polygons: A and B1. Depending on the actual split boundaries
34
we could still have joined A and B1 into one polygon. Therefore a second approach is used as well:
35

36
2. After CSG operations all coplanar polygon fragments are joined by a retesselating
37
operation. See CSG.reTesselated(). Retesselation is done through a
38
linear sweep over the polygon surface. The sweep line passes over the y coordinates
39
of all vertices in the polygon. Polygons are split at each sweep line, and the fragments
40
are joined horizontally and vertically into larger polygons (making sure that we
41
will end up with convex polygons).
42
This still doesn't solve the problem completely: due to floating point imprecisions
43
we may end up with small gaps between polygons, and polygons may not be exactly coplanar
44
anymore, and as a result the retesselation algorithm may fail to join those polygons.
45
Therefore:
46

47
3. A canonicalization algorithm is implemented: it looks for vertices that have
48
approximately the same coordinates (with a certain tolerance, say 1e-5) and replaces
49
them with the same vertex. If polygons share a vertex they will actually point to the
50
same CSG.Vertex instance. The same is done for polygon planes. See CSG.canonicalized().
51

52

53
Performance improvements to the original CSG.js:
54

55
Replaced the flip() and invert() methods by flipped() and inverted() which don't
56
modify the source object. This allows to get rid of all clone() calls, so that
57
multiple polygons can refer to the same CSG.Plane instance etc.
58

59
The original union() used an extra invert(), clipTo(), invert() sequence just to remove the
60
coplanar front faces from b; this is now combined in a single b.clipTo(a, true) call.
61

62
Detection whether a polygon is in front or in back of a plane: for each polygon
63
we are caching the coordinates of the bounding sphere. If the bounding sphere is
64
in front or in back of the plane we don't have to check the individual vertices
65
anymore.
66

67

68
Other additions to the original CSG.js:
69

70
CSG.Vector class has been renamed into CSG.Vector3D
71

72
Classes for 3D lines, 2D vectors, 2D lines, and methods to find the intersection of
73
a line and a plane etc.
74

75
Transformations: CSG.transform(), CSG.translate(), CSG.rotate(), CSG.scale()
76

77
Expanding or contracting a solid: CSG.expand() and CSG.contract(). Creates nice
78
smooth corners.
79

80
The vertex normal has been removed since it complicates retesselation. It's not needed
81
for solid CAD anyway.
82

83
*/
84

85
(function(module){
86

87
var _CSGDEBUG = false;
88

89
function fnNumberSort(a, b) {
90
	return a - b;
91
}
92

93
// # class CSG
94
// Holds a binary space partition tree representing a 3D solid. Two solids can
95
// be combined using the `union()`, `subtract()`, and `intersect()` methods.
96
var CSG = function() {
97
	this.polygons = [];
98
	this.properties = new CSG.Properties();
99
	this.isCanonicalized = true;
100
	this.isRetesselated = true;
101
};
102

103
CSG.defaultResolution2D = 32;
104
CSG.defaultResolution3D = 12;
105

106
// Construct a CSG solid from a list of `CSG.Polygon` instances.
107
CSG.fromPolygons = function(polygons) {
108
	var csg = new CSG();
109
	csg.polygons = polygons;
110
	csg.isCanonicalized = false;
111
	csg.isRetesselated = false;
112
	return csg;
113
};
114

115
// Construct a CSG solid from generated slices.
116
// Look at CSG.Polygon.prototype.solidFromSlices for details
117
CSG.fromSlices = function(options) {
118
	return (new CSG.Polygon.createFromPoints([
119
			[0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0]
120
	])).solidFromSlices(options);
121
};
122

123
// create from an untyped object with identical property names:
124
CSG.fromObject = function(obj) {
125
	var polygons = obj.polygons.map(function(p) {
126
		return CSG.Polygon.fromObject(p);
127
	});
128
	var csg = CSG.fromPolygons(polygons);
129
	csg = csg.canonicalized();
130
	return csg;
131
};
132

133
// Reconstruct a CSG from the output of toCompactBinary()
134
CSG.fromCompactBinary = function(bin) {
135
	if(bin['class'] != "CSG") throw new Error("Not a CSG");
136
	var planes = [],
137
		planeData = bin.planeData,
138
		numplanes = planeData.length / 4,
139
		arrayindex = 0,
140
		x, y, z, w, normal, plane;
141
	for(var planeindex = 0; planeindex < numplanes; planeindex++) {
142
		x = planeData[arrayindex++];
143
		y = planeData[arrayindex++];
144
		z = planeData[arrayindex++];
145
		w = planeData[arrayindex++];
146
		normal = new CSG.Vector3D(x, y, z);
147
		plane = new CSG.Plane(normal, w);
148
		planes.push(plane);
149
	}
150

151
	var vertices = [],
152
		vertexData = bin.vertexData,
153
		numvertices = vertexData.length / 3,
154
		pos, vertex;
155
	arrayindex = 0;
156
	for(var vertexindex = 0; vertexindex < numvertices; vertexindex++) {
157
		x = vertexData[arrayindex++];
158
		y = vertexData[arrayindex++];
159
		z = vertexData[arrayindex++];
160
		pos = new CSG.Vector3D(x, y, z);
161
		vertex = new CSG.Vertex(pos);
162
		vertices.push(vertex);
163
	}
164

165
	var shareds = bin.shared.map(function(shared) {
166
		return CSG.Polygon.Shared.fromObject(shared);
167
	});
168

169
	var polygons = [],
170
		numpolygons = bin.numPolygons,
171
		numVerticesPerPolygon = bin.numVerticesPerPolygon,
172
		polygonVertices = bin.polygonVertices,
173
		polygonPlaneIndexes = bin.polygonPlaneIndexes,
174
		polygonSharedIndexes = bin.polygonSharedIndexes,
175
		numpolygonvertices, polygonvertices, shared, polygon;//already defined plane,
176
	arrayindex = 0;
177
	for(var polygonindex = 0; polygonindex < numpolygons; polygonindex++) {
178
		numpolygonvertices = numVerticesPerPolygon[polygonindex];
179
		polygonvertices = [];
180
		for(var i = 0; i < numpolygonvertices; i++) {
181
			polygonvertices.push(vertices[polygonVertices[arrayindex++]]);
182
		}
183
		plane = planes[polygonPlaneIndexes[polygonindex]];
184
		shared = shareds[polygonSharedIndexes[polygonindex]];
185
		polygon = new CSG.Polygon(polygonvertices, shared, plane);
186
		polygons.push(polygon);
187
	}
188
	var csg = CSG.fromPolygons(polygons);
189
	csg.isCanonicalized = true;
190
	csg.isRetesselated = true;
191
	return csg;
192
};
193

194
CSG.prototype = {
195
	toPolygons: function() {
196
		return this.polygons;
197
	},
198

199
	// Return a new CSG solid representing space in either this solid or in the
200
	// solid `csg`. Neither this solid nor the solid `csg` are modified.
201
	//
202
	//     A.union(B)
203
	//
204
	//     +-------+            +-------+
205
	//     |       |            |       |
206
	//     |   A   |            |       |
207
	//     |    +--+----+   =   |       +----+
208
	//     +----+--+    |       +----+       |
209
	//          |   B   |            |       |
210
	//          |       |            |       |
211
	//          +-------+            +-------+
212
	//
213
	union: function(csg) {
214
		var csgs;
215
		if(csg instanceof Array) {
216
			csgs = csg;
217
		} else {
218
			csgs = [csg];
219
		}
220
		var result = this;
221
		for(var i = 0; i < csgs.length; i++) {
222
			var islast = (i == (csgs.length - 1));
223
			result = result.unionSub(csgs[i], islast, islast);
224
		}
225
		return result;
226
	},
227

228
	unionSub: function(csg, retesselate, canonicalize) {
229
		if(!this.mayOverlap(csg)) {
230
			return this.unionForNonIntersecting(csg);
231
		} else {
232
			var a = new CSG.Tree(this.polygons);
233
			var b = new CSG.Tree(csg.polygons);
234
			a.clipTo(b, false);
235

236
			// b.clipTo(a, true); // ERROR: this doesn't work
237
			b.clipTo(a);
238
			b.invert();
239
			b.clipTo(a);
240
			b.invert();
241

242
			var newpolygons = a.allPolygons().concat(b.allPolygons());
243
			var result = CSG.fromPolygons(newpolygons);
244
			result.properties = this.properties._merge(csg.properties);
245
			if(retesselate) result = result.reTesselated();
246
			if(canonicalize) result = result.canonicalized();
247
			return result;
248
		}
249
	},
250

251
	// Like union, but when we know that the two solids are not intersecting
252
	// Do not use if you are not completely sure that the solids do not intersect!
253
	unionForNonIntersecting: function(csg) {
254
		var newpolygons = this.polygons.concat(csg.polygons);
255
		var result = CSG.fromPolygons(newpolygons);
256
		result.properties = this.properties._merge(csg.properties);
257
		result.isCanonicalized = this.isCanonicalized && csg.isCanonicalized;
258
		result.isRetesselated = this.isRetesselated && csg.isRetesselated;
259
		return result;
260
	},
261

262
	// Return a new CSG solid representing space in this solid but not in the
263
	// solid `csg`. Neither this solid nor the solid `csg` are modified.
264
	//
265
	//     A.subtract(B)
266
	//
267
	//     +-------+            +-------+
268
	//     |       |            |       |
269
	//     |   A   |            |       |
270
	//     |    +--+----+   =   |    +--+
271
	//     +----+--+    |       +----+
272
	//          |   B   |
273
	//          |       |
274
	//          +-------+
275
	//
276
	subtract: function(csg) {
277
		var csgs;
278
		if(csg instanceof Array) {
279
			csgs = csg;
280
		} else {
281
			csgs = [csg];
282
		}
283
		var result = this;
284
		for(var i = 0; i < csgs.length; i++) {
285
			var islast = (i == (csgs.length - 1));
286
			result = result.subtractSub(csgs[i], islast, islast);
287
		}
288
		return result;
289
	},
290

291
	subtractSub: function(csg, retesselate, canonicalize) {
292
		var a = new CSG.Tree(this.polygons);
293
		var b = new CSG.Tree(csg.polygons);
294
		a.invert();
295
		a.clipTo(b);
296
		b.clipTo(a, true);
297
		a.addPolygons(b.allPolygons());
298
		a.invert();
299
		var result = CSG.fromPolygons(a.allPolygons());
300
		result.properties = this.properties._merge(csg.properties);
301
		if(retesselate) result = result.reTesselated();
302
		if(canonicalize) result = result.canonicalized();
303
		return result;
304
	},
305

306
	// Return a new CSG solid representing space both this solid and in the
307
	// solid `csg`. Neither this solid nor the solid `csg` are modified.
308
	//
309
	//     A.intersect(B)
310
	//
311
	//     +-------+
312
	//     |       |
313
	//     |   A   |
314
	//     |    +--+----+   =   +--+
315
	//     +----+--+    |       +--+
316
	//          |   B   |
317
	//          |       |
318
	//          +-------+
319
	//
320
	intersect: function(csg) {
321
		var csgs;
322
		if(csg instanceof Array) {
323
			csgs = csg;
324
		} else {
325
			csgs = [csg];
326
		}
327
		var result = this;
328
		for(var i = 0; i < csgs.length; i++) {
329
			var islast = (i == (csgs.length - 1));
330
			result = result.intersectSub(csgs[i], islast, islast);
331
		}
332
		return result;
333
	},
334

335
	intersectSub: function(csg, retesselate, canonicalize) {
336
		var a = new CSG.Tree(this.polygons);
337
		var b = new CSG.Tree(csg.polygons);
338
		a.invert();
339
		b.clipTo(a);
340
		b.invert();
341
		a.clipTo(b);
342
		b.clipTo(a);
343
		a.addPolygons(b.allPolygons());
344
		a.invert();
345
		var result = CSG.fromPolygons(a.allPolygons());
346
		result.properties = this.properties._merge(csg.properties);
347
		if(retesselate) result = result.reTesselated();
348
		if(canonicalize) result = result.canonicalized();
349
		return result;
350
	},
351

352
	// Return a new CSG solid with solid and empty space switched. This solid is
353
	// not modified.
354
	inverse: function() {
355
		var flippedpolygons = this.polygons.map(function(p) {
356
			return p.flipped();
357
		});
358
		return CSG.fromPolygons(flippedpolygons);
359
		// TODO: flip properties
360
	},
361

362
	// Affine transformation of CSG object. Returns a new CSG object
363
	transform1: function(matrix4x4) {
364
		var newpolygons = this.polygons.map(function(p) {
365
			return p.transform(matrix4x4);
366
		});
367
		var result = CSG.fromPolygons(newpolygons);
368
		result.properties = this.properties._transform(matrix4x4);
369
		result.isRetesselated = this.isRetesselated;
370
		return result;
371
	},
372

373
	transform: function(matrix4x4) {
374
		var ismirror = matrix4x4.isMirroring();
375
		var transformedvertices = {};
376
		var transformedplanes = {};
377
		var newpolygons = this.polygons.map(function(p) {
378
			var newplane;
379
			var plane = p.plane;
380
			var planetag = plane.getTag();
381
			if(planetag in transformedplanes) {
382
				newplane = transformedplanes[planetag];
383
			} else {
384
				newplane = plane.transform(matrix4x4);
385
				transformedplanes[planetag] = newplane;
386
			}
387
			var newvertices = p.vertices.map(function(v) {
388
				var newvertex;
389
				var vertextag = v.getTag();
390
				if(vertextag in transformedvertices) {
391
					newvertex = transformedvertices[vertextag];
392
				} else {
393
					newvertex = v.transform(matrix4x4);
394
					transformedvertices[vertextag] = newvertex;
395
				}
396
				return newvertex;
397
			});
398
			if(ismirror) newvertices.reverse();
399
			return new CSG.Polygon(newvertices, p.shared, newplane);
400
		});
401
		var result = CSG.fromPolygons(newpolygons);
402
		result.properties = this.properties._transform(matrix4x4);
403
		result.isRetesselated = this.isRetesselated;
404
		result.isCanonicalized = this.isCanonicalized;
405
		return result;
406
	},
407

408
	toStlString: function() {
409
		var result = "solid csg.js\n";
410
		this.polygons.map(function(p) {
411
			result += p.toStlString();
412
		});
413
		result += "endsolid csg.js\n";
414
		return result;
415
	},
416

417
	toAMFString: function(m) {
418
		var result = "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<amf"+(m&&m.unit?" unit=\"+m.unit\"":"")+">\n";
419
		for(var k in m) {
420
			result += "<metadata type=\""+k+"\">"+m[k]+"</metadata>\n";
421
		}
422
		result += "<object id=\"0\">\n<mesh>\n<vertices>\n";
423

424
		this.polygons.map(function(p) {                  // first we dump all vertices of all polygons
425
         for(var i=0; i<p.vertices.length; i++) {
426
            result += p.vertices[i].toAMFString();
427
         }
428
      });
429
      result += "</vertices>\n";
430

431
      var n = 0;
432
		this.polygons.map(function(p) {                  // then we dump all polygons
433
         result += "<volume>\n";
434
         if(p.vertices.length<3) 
435
            return;
436
			var r = 1, g = 0.4, b = 1, a = 1, colorSet = false;
437
			if(p.shared && p.shared.color) {
438
				r = p.shared.color[0];
439
				g = p.shared.color[1];
440
				b = p.shared.color[2];
441
            a = p.shared.color[3];
442
				colorSet = true;
443
			} else if(p.color) {
444
            r = p.color[0];
445
            g = p.color[1];
446
            b = p.color[2];
447
            if(p.color.length()>3) a = p.color[3];
448
				colorSet = true;
449
         }
450

451
   		result += "<color><r>"+r+"</r><g>"+g+"</g><b>"+b+"</b>"+(a!==undefined?"<a>"+a+"</a>":"")+"</color>";
452

453
         for(var i=0; i<p.vertices.length-2; i++) {      // making sure they are all triangles (triangular polygons)
454
            result += "<triangle>";
455
            result += "<v1>" + (n) + "</v1>";
456
            result += "<v2>" + (n+i+1) + "</v2>";
457
            result += "<v3>" + (n+i+2) + "</v3>";
458
            result += "</triangle>\n";
459
         }
460
         n += p.vertices.length;
461
         result += "</volume>\n";
462
		});
463
		result += "</mesh>\n</object>\n";
464
		result += "</amf>\n";
465
		return result;
466
	},
467

468
	toX3D: function() {
469
		// materialPolygonLists
470
		// key: a color string (e.g. "0 1 1" for yellow)
471
		// value: an array of strings specifying polygons of this color
472
		//        (as space-separated indices into vertexCoords)
473
		var materialPolygonLists = {},
474
		// list of coordinates (as "x y z" strings)
475
			vertexCoords = [],
476
		// map to look up the index in vertexCoords of a given vertex
477
			vertexTagToCoordIndexMap = {};
478

479
		this.polygons.map(function(p) {
480
			var red = 0,
481
				green = 0,
482
				blue = 1; // default color is blue
483
			if(p.shared && p.shared.color) {
484
				red = p.shared.color[0];
485
				green = p.shared.color[1];
486
				blue = p.shared.color[2];
487
			}
488

489
			var polygonVertexIndices = [],
490
				numvertices = p.vertices.length,
491
				vertex;
492
			for(var i = 0; i < numvertices; i++) {
493
				vertex = p.vertices[i];
494
				if(!(vertex.getTag() in vertexTagToCoordIndexMap)) {
495
					vertexCoords.push(vertex.pos._x.toString() + " " +
496
						vertex.pos._y.toString() + " " +
497
						vertex.pos._z.toString()
498
					);
499
					vertexTagToCoordIndexMap[vertex.getTag()] = vertexCoords.length - 1;
500
				}
501
				polygonVertexIndices.push(vertexTagToCoordIndexMap[vertex.getTag()]);
502
			}
503

504
			var polygonString = polygonVertexIndices.join(" ");
505

506
			var colorString = red.toString() + " " + green.toString() + " " + blue.toString();
507
			if(!(colorString in materialPolygonLists)) {
508
				materialPolygonLists[colorString] = [];
509
			}
510
			// add this polygonString to the list of colorString-colored polygons
511
			materialPolygonLists[colorString].push(polygonString);
512
		});
513

514

515
		// create output document
516
		var docType = document.implementation.createDocumentType("X3D",
517
			'ISO//Web3D//DTD X3D 3.1//EN" "http://www.web3d.org/specifications/x3d-3.1.dtd', null);
518
		var exportDoc = document.implementation.createDocument(null, "X3D", docType);
519
		exportDoc.insertBefore(
520
			exportDoc.createProcessingInstruction('xml', 'version="1.0" encoding="UTF-8"'),
521
			exportDoc.doctype);
522

523
		var exportRoot = exportDoc.getElementsByTagName("X3D")[0];
524
		exportRoot.setAttribute("profile", "Interchange");
525
		exportRoot.setAttribute("version", "3.1");
526
		exportRoot.setAttribute("xsd:noNamespaceSchemaLocation","http://www.web3d.org/specifications/x3d-3.1.xsd");
527
		exportRoot.setAttribute("xmlns:xsd", "http://www.w3.org/2001/XMLSchema-instance");
528

529
		var exportScene = exportDoc.createElement("Scene");
530
		exportRoot.appendChild(exportScene);
531

532
		/*
533
	  For each color, create a shape made of an appropriately colored
534
	  material which contains all polygons that are this color.
535

536
	  The first shape will contain the definition of all vertices,
537
	  (<Coordinate DEF="coords_mesh"/>), which will be referenced by
538
	  subsequent shapes.
539
	*/
540
		var coordsMeshDefined = false;
541
		for(var colorString in materialPolygonLists) {
542
			var polygonList = materialPolygonLists[colorString];
543
			var shape = exportDoc.createElement("Shape");
544
			exportScene.appendChild(shape);
545

546
			var appearance = exportDoc.createElement("Appearance");
547
			shape.appendChild(appearance);
548

549
			var material = exportDoc.createElement("Material");
550
			appearance.appendChild(material);
551
			material.setAttribute("diffuseColor", colorString);
552
			material.setAttribute("ambientIntensity", "1.0");
553

554
			var ifs = exportDoc.createElement("IndexedFaceSet");
555
			shape.appendChild(ifs);
556
			ifs.setAttribute("solid", "true");
557
			ifs.setAttribute("coordIndex", polygonList.join(" -1 ") + " -1");
558

559
			var coordinate = exportDoc.createElement("Coordinate");
560
			ifs.appendChild(coordinate);
561
			if(coordsMeshDefined) {
562
				coordinate.setAttribute("USE", "coords_mesh");
563
			} else {
564
				coordinate.setAttribute("DEF", "coords_mesh");
565
				coordinate.setAttribute("point", vertexCoords.join(" "));
566
				coordsMeshDefined = true;
567
			}
568
		}
569

570
		var x3dstring = (new XMLSerializer()).serializeToString(exportDoc);
571
		return new Blob([x3dstring], {
572
			type: "model/x3d+xml"
573
		});
574
	},
575

576
	// see http://en.wikipedia.org/wiki/STL_%28file_format%29#Binary_STL
577
	toStlBinary: function(p) {
578
		// first check if the host is little-endian:
579
		var buffer = new ArrayBuffer(4);
580
		var int32buffer = new Int32Array(buffer, 0, 1);
581
		var int8buffer = new Int8Array(buffer, 0, 4);
582
		int32buffer[0] = 0x11223344;
583
		if(int8buffer[0] != 0x44) {
584
			throw new Error("Binary STL output is currently only supported on little-endian (Intel) processors");
585
		}
586

587
		var numtriangles = 0;
588
		this.polygons.map(function(p) {
589
			var numvertices = p.vertices.length;
590
			var thisnumtriangles = (numvertices >= 3) ? numvertices - 2 : 0;
591
			numtriangles += thisnumtriangles;
592
		});
593
		var headerarray = new Uint8Array(80);
594
		for(var i = 0; i < 80; i++) {
595
			headerarray[i] = 65;
596
		}
597
		var ar1 = new Uint32Array(1);
598
		ar1[0] = numtriangles;
599
		// write the triangles to allTrianglesBuffer:
600
		var allTrianglesBuffer = new ArrayBuffer(50 * numtriangles);
601
		var allTrianglesBufferAsInt8 = new Int8Array(allTrianglesBuffer);
602
		// a tricky problem is that a Float32Array must be aligned at 4-byte boundaries (at least in certain browsers)
603
		// while each triangle takes 50 bytes. Therefore we write each triangle to a temporary buffer, and copy that
604
		// into allTrianglesBuffer:
605
		var triangleBuffer = new ArrayBuffer(50);
606
		var triangleBufferAsInt8 = new Int8Array(triangleBuffer);
607
		// each triangle consists of 12 floats:
608
		var triangleFloat32array = new Float32Array(triangleBuffer, 0, 12);
609
		// and one uint16:
610
		var triangleUint16array = new Uint16Array(triangleBuffer, 48, 1);
611
		var byteoffset = 0;
612
		this.polygons.map(function(p) {
613
			var numvertices = p.vertices.length;
614
			for(var i = 0; i < numvertices - 2; i++) {
615
				var normal = p.plane.normal;
616
				triangleFloat32array[0] = normal._x;
617
				triangleFloat32array[1] = normal._y;
618
				triangleFloat32array[2] = normal._z;
619
				var arindex = 3;
620
				for(var v = 0; v < 3; v++) {
621
					var vv = v + ((v > 0) ? i : 0);
622
					var vertexpos = p.vertices[vv].pos;
623
					triangleFloat32array[arindex++] = vertexpos._x;
624
					triangleFloat32array[arindex++] = vertexpos._y;
625
					triangleFloat32array[arindex++] = vertexpos._z;
626
				}
627
				triangleUint16array[0] = 0;
628
				// copy the triangle into allTrianglesBuffer:
629
				allTrianglesBufferAsInt8.set(triangleBufferAsInt8, byteoffset);
630
				byteoffset += 50;
631
			}
632
		});
633
      if(p&&p.webBlob) {      // -- want a blob direct
634
			return new Blob([headerarray.buffer, ar1.buffer, allTrianglesBuffer], {
635
			   type: "application/sla"
636
			});
637
      } else {
638
         // we differentiate, as binary string blobbing gives bad blob in web, we need binary string for CLI
639
         //    perhaps there is a way to make it working (see openjscad for stlb)\
640
         //
641
         // concat 3 buffers together -- don't make blob so early, we want data (non-blob) for nodejs too
642
         //    must be string data direct to write
643
         var stl = new Uint8Array(headerarray.buffer.byteLength + ar1.buffer.byteLength + allTrianglesBuffer.byteLength);
644
         var j = 0;
645
         for(var i=0; i<headerarray.buffer.byteLength; i++) { stl.buffer[j++] = headerarray.buffer[i]; }
646
         for(var i=0; i<ar1.buffer.byteLength; i++) { stl.buffer[j++] = ar1.buffer[i]; }
647
         for(var i=0; i<allTrianglesBuffer.byteLength; i++) { stl.buffer[j++] = allTrianglesBuffer[i]; }
648
         return String.fromCharCode.apply(null, new Uint8Array(stl.buffer)); 
649
         
650
      }   
651
	},
652

653
	toString: function() {
654
		var result = "CSG solid:\n";
655
		this.polygons.map(function(p) {
656
			result += p.toString();
657
		});
658
		return result;
659
	},
660

661
   center: function(c) {
662
      if(!c.length) c = [c,c,c];
663
      var b = this.getBounds();
664
      return this.translate([
665
         c[0]?-(b[1].x-b[0].x)/2-b[0].x:0,
666
         c[1]?-(b[1].y-b[0].y)/2-b[0].y:0,
667
         c[2]?-(b[1].z-b[0].z)/2-b[0].z:0]);
668
   },
669

670
	// Expand the solid
671
	// resolution: number of points per 360 degree for the rounded corners
672
	expand: function(radius, resolution) {
673
		var result = this.expandedShell(radius, resolution, true);
674
		result = result.reTesselated();
675
		result.properties = this.properties; // keep original properties
676
		return result;
677
	},
678

679
	// Contract the solid
680
	// resolution: number of points per 360 degree for the rounded corners
681
	contract: function(radius, resolution) {
682
		var expandedshell = this.expandedShell(radius, resolution, false);
683
		var result = this.subtract(expandedshell);
684
		result = result.reTesselated();
685
		result.properties = this.properties; // keep original properties
686
		return result;
687
	},
688

689
	// Create the expanded shell of the solid:
690
	// All faces are extruded to get a thickness of 2*radius
691
	// Cylinders are constructed around every side
692
	// Spheres are placed on every vertex
693
	// unionWithThis: if true, the resulting solid will be united with 'this' solid;
694
	//   the result is a true expansion of the solid
695
	//   If false, returns only the shell
696
	expandedShell: function(radius, resolution, unionWithThis) {
697
		var csg = this.reTesselated();
698
		var result;
699
		if(unionWithThis) {
700
			result = csg;
701
		} else {
702
			result = new CSG();
703
		}
704

705
		// first extrude all polygons:
706
		csg.polygons.map(function(polygon) {
707
			var extrudevector = polygon.plane.normal.unit().times(2 * radius);
708
			var translatedpolygon = polygon.translate(extrudevector.times(-0.5));
709
			var extrudedface = translatedpolygon.extrude(extrudevector);
710
			result = result.unionSub(extrudedface, false, false);
711
		});
712

713
		// Make a list of all unique vertex pairs (i.e. all sides of the solid)
714
		// For each vertex pair we collect the following:
715
		//   v1: first coordinate
716
		//   v2: second coordinate
717
		//   planenormals: array of normal vectors of all planes touching this side
718
		var vertexpairs = {}; // map of 'vertex pair tag' to {v1, v2, planenormals}
719
		csg.polygons.map(function(polygon) {
720
			var numvertices = polygon.vertices.length;
721
			var prevvertex = polygon.vertices[numvertices - 1];
722
			var prevvertextag = prevvertex.getTag();
723
			for(var i = 0; i < numvertices; i++) {
724
				var vertex = polygon.vertices[i];
725
				var vertextag = vertex.getTag();
726
				var vertextagpair;
727
				if(vertextag < prevvertextag) {
728
					vertextagpair = vertextag + "-" + prevvertextag;
729
				} else {
730
					vertextagpair = prevvertextag + "-" + vertextag;
731
				}
732
				var obj;
733
				if(vertextagpair in vertexpairs) {
734
					obj = vertexpairs[vertextagpair];
735
				} else {
736
					obj = {
737
						v1: prevvertex,
738
						v2: vertex,
739
						planenormals: []
740
					};
741
					vertexpairs[vertextagpair] = obj;
742
				}
743
				obj.planenormals.push(polygon.plane.normal);
744

745
				prevvertextag = vertextag;
746
				prevvertex = vertex;
747
			}
748
		});
749

750
		// now construct a cylinder on every side
751
		// The cylinder is always an approximation of a true cylinder: it will have <resolution> polygons
752
		// around the sides. We will make sure though that the cylinder will have an edge at every
753
		// face that touches this side. This ensures that we will get a smooth fill even
754
		// if two edges are at, say, 10 degrees and the resolution is low.
755
		// Note: the result is not retesselated yet but it really should be!
756
		for(var vertextagpair in vertexpairs) {
757
			var vertexpair = vertexpairs[vertextagpair],
758
				startpoint = vertexpair.v1.pos,
759
				endpoint = vertexpair.v2.pos,
760
			// our x,y and z vectors:
761
				zbase = endpoint.minus(startpoint).unit(),
762
				xbase = vertexpair.planenormals[0].unit(),
763
				ybase = xbase.cross(zbase),
764

765
			// make a list of angles that the cylinder should traverse:
766
				angles = [];
767

768
			// first of all equally spaced around the cylinder:
769
			for(var i = 0; i < resolution; i++) {
770
				angles.push(i * Math.PI * 2 / resolution);
771
			}
772

773
			// and also at every normal of all touching planes:
774
			for(var i = 0, iMax = vertexpair.planenormals.length; i < iMax; i++) {
775
				var planenormal = vertexpair.planenormals[i],
776
					si = ybase.dot(planenormal),
777
					co = xbase.dot(planenormal),
778
					angle = Math.atan2(si, co);
779

780
				if(angle < 0) angle += Math.PI * 2;
781
				angles.push(angle);
782
				angle = Math.atan2(-si, -co);
783
				if(angle < 0) angle += Math.PI * 2;
784
				angles.push(angle);
785
			}
786

787
			// this will result in some duplicate angles but we will get rid of those later.
788
			// Sort:
789
			angles = angles.sort(fnNumberSort);
790

791
			// Now construct the cylinder by traversing all angles:
792
			var numangles = angles.length,
793
				prevp1, prevp2,
794
				startfacevertices = [],
795
				endfacevertices = [],
796
				polygons = [];
797
			for(var i = -1; i < numangles; i++) {
798
				var angle = angles[(i < 0) ? (i + numangles) : i],
799
					si = Math.sin(angle),
800
					co = Math.cos(angle),
801
					p = xbase.times(co * radius).plus(ybase.times(si * radius)),
802
					p1 = startpoint.plus(p),
803
					p2 = endpoint.plus(p),
804
					skip = false;
805
				if(i >= 0) {
806
					if(p1.distanceTo(prevp1) < 1e-5) {
807
						skip = true;
808
					}
809
				}
810
				if(!skip) {
811
					if(i >= 0) {
812
						startfacevertices.push(new CSG.Vertex(p1));
813
						endfacevertices.push(new CSG.Vertex(p2));
814
						var polygonvertices = [
815
							new CSG.Vertex(prevp2),
816
							new CSG.Vertex(p2),
817
							new CSG.Vertex(p1),
818
							new CSG.Vertex(prevp1)];
819
						var polygon = new CSG.Polygon(polygonvertices);
820
						polygons.push(polygon);
821
					}
822
					prevp1 = p1;
823
					prevp2 = p2;
824
				}
825
			}
826
			endfacevertices.reverse();
827
			polygons.push(new CSG.Polygon(startfacevertices));
828
			polygons.push(new CSG.Polygon(endfacevertices));
829
			var cylinder = CSG.fromPolygons(polygons);
830
			result = result.unionSub(cylinder, false, false);
831
		}
832

833
		// make a list of all unique vertices
834
		// For each vertex we also collect the list of normals of the planes touching the vertices
835
		var vertexmap = {};
836
		csg.polygons.map(function(polygon) {
837
			polygon.vertices.map(function(vertex) {
838
				var vertextag = vertex.getTag();
839
				var obj;
840
				if(vertextag in vertexmap) {
841
					obj = vertexmap[vertextag];
842
				} else {
843
					obj = {
844
						pos: vertex.pos,
845
						normals: []
846
					};
847
					vertexmap[vertextag] = obj;
848
				}
849
				obj.normals.push(polygon.plane.normal);
850
			});
851
		});
852

853
		// and build spheres at each vertex
854
		// We will try to set the x and z axis to the normals of 2 planes
855
		// This will ensure that our sphere tesselation somewhat matches 2 planes
856
		for(var vertextag in vertexmap) {
857
			var vertexobj = vertexmap[vertextag];
858
			// use the first normal to be the x axis of our sphere:
859
			var xaxis = vertexobj.normals[0].unit();
860
			// and find a suitable z axis. We will use the normal which is most perpendicular to the x axis:
861
			var bestzaxis = null;
862
			var bestzaxisorthogonality = 0;
863
			for(var i = 1; i < vertexobj.normals.length; i++) {
864
				var normal = vertexobj.normals[i].unit();
865
				var cross = xaxis.cross(normal);
866
				var crosslength = cross.length();
867
				if(crosslength > 0.05) {
868
					if(crosslength > bestzaxisorthogonality) {
869
						bestzaxisorthogonality = crosslength;
870
						bestzaxis = normal;
871
					}
872
				}
873
			}
874
			if(!bestzaxis) {
875
				bestzaxis = xaxis.randomNonParallelVector();
876
			}
877
			var yaxis = xaxis.cross(bestzaxis).unit();
878
			var zaxis = yaxis.cross(xaxis);
879
			var sphere = CSG.sphere({
880
				center: vertexobj.pos,
881
				radius: radius,
882
				resolution: resolution,
883
				axes: [xaxis, yaxis, zaxis]
884
			});
885
			result = result.unionSub(sphere, false, false);
886
		}
887

888
		return result;
889
	},
890

891
	canonicalized: function() {
892
		if(this.isCanonicalized) {
893
			return this;
894
		} else {
895
			var factory = new CSG.fuzzyCSGFactory();
896
			var result = factory.getCSG(this);
897
			result.isCanonicalized = true;
898
			result.isRetesselated = this.isRetesselated;
899
			result.properties = this.properties; // keep original properties
900
			return result;
901
		}
902
	},
903

904
	reTesselated: function() {
905
		if(this.isRetesselated) {
906
			return this;
907
		} else {
908
			var csg = this.canonicalized();
909
			var polygonsPerPlane = {};
910
			csg.polygons.map(function(polygon) {
911
				var planetag = polygon.plane.getTag();
912
				var sharedtag = polygon.shared.getTag();
913
				planetag += "/" + sharedtag;
914
				if(!(planetag in polygonsPerPlane)) {
915
					polygonsPerPlane[planetag] = [];
916
				}
917
				polygonsPerPlane[planetag].push(polygon);
918
			});
919
			var destpolygons = [];
920
			for(var planetag in polygonsPerPlane) {
921
				var sourcepolygons = polygonsPerPlane[planetag];
922
				if(sourcepolygons.length < 2) {
923
					destpolygons = destpolygons.concat(sourcepolygons);
924
				} else {
925
					var retesselayedpolygons = [];
926
					CSG.reTesselateCoplanarPolygons(sourcepolygons, retesselayedpolygons);
927
					destpolygons = destpolygons.concat(retesselayedpolygons);
928
				}
929
			}
930
			var result = CSG.fromPolygons(destpolygons);
931
			result.isRetesselated = true;
932
			result = result.canonicalized();
933
			//      result.isCanonicalized = true;
934
			result.properties = this.properties; // keep original properties
935
			return result;
936
		}
937
	},
938

939
	// returns an array of two CSG.Vector3Ds (minimum coordinates and maximum coordinates)
940
	getBounds: function() {
941
		if(!this.cachedBoundingBox) {
942
			var minpoint = new CSG.Vector3D(0, 0, 0);
943
			var maxpoint = new CSG.Vector3D(0, 0, 0);
944
			var polygons = this.polygons;
945
			var numpolygons = polygons.length;
946
			for(var i = 0; i < numpolygons; i++) {
947
				var polygon = polygons[i];
948
				var bounds = polygon.boundingBox();
949
				if(i === 0) {
950
					minpoint = bounds[0];
951
					maxpoint = bounds[1];
952
				} else {
953
					minpoint = minpoint.min(bounds[0]);
954
					maxpoint = maxpoint.max(bounds[1]);
955
				}
956
			}
957
			this.cachedBoundingBox = [minpoint, maxpoint];
958
		}
959
		return this.cachedBoundingBox;
960
	},
961

962
	// returns true if there is a possibility that the two solids overlap
963
	// returns false if we can be sure that they do not overlap
964
	mayOverlap: function(csg) {
965
		if((this.polygons.length === 0) || (csg.polygons.length === 0)) {
966
			return false;
967
		} else {
968
			var mybounds = this.getBounds();
969
			var otherbounds = csg.getBounds();
970
         // [0].x/y  
971
         //    +-----+
972
         //    |     |
973
         //    |     |
974
         //    +-----+ 
975
         //          [1].x/y
976
         //return false;
977
         //echo(mybounds,"=",otherbounds);
978
			if(mybounds[1].x < otherbounds[0].x) return false;
979
			if(mybounds[0].x > otherbounds[1].x) return false;
980
			if(mybounds[1].y < otherbounds[0].y) return false;
981
			if(mybounds[0].y > otherbounds[1].y) return false;
982
			if(mybounds[1].z < otherbounds[0].z) return false;
983
			if(mybounds[0].z > otherbounds[1].z) return false;
984
			return true;
985
		}
986
	},
987

988
	// Cut the solid by a plane. Returns the solid on the back side of the plane
989
	cutByPlane: function(plane) {
990
		if(this.polygons.length === 0) {
991
			return new CSG();
992
		}
993
		// Ideally we would like to do an intersection with a polygon of inifinite size
994
		// but this is not supported by our implementation. As a workaround, we will create
995
		// a cube, with one face on the plane, and a size larger enough so that the entire
996
		// solid fits in the cube.
997
		// find the max distance of any vertex to the center of the plane:
998
		var planecenter = plane.normal.times(plane.w);
999
		var maxdistance = 0;
1000
		this.polygons.map(function(polygon) {
1001
			polygon.vertices.map(function(vertex) {
1002
				var distance = vertex.pos.distanceToSquared(planecenter);
1003
				if(distance > maxdistance) maxdistance = distance;
1004
			});
1005
		});
1006
		maxdistance = Math.sqrt(maxdistance);
1007
		maxdistance *= 1.01; // make sure it's really larger
1008
		// Now build a polygon on the plane, at any point farther than maxdistance from the plane center:
1009
		var vertices = [];
1010
		var orthobasis = new CSG.OrthoNormalBasis(plane);
1011
		vertices.push(new CSG.Vertex(orthobasis.to3D(new CSG.Vector2D(maxdistance, -maxdistance))));
1012
		vertices.push(new CSG.Vertex(orthobasis.to3D(new CSG.Vector2D(-maxdistance, -maxdistance))));
1013
		vertices.push(new CSG.Vertex(orthobasis.to3D(new CSG.Vector2D(-maxdistance, maxdistance))));
1014
		vertices.push(new CSG.Vertex(orthobasis.to3D(new CSG.Vector2D(maxdistance, maxdistance))));
1015
		var polygon = new CSG.Polygon(vertices, null, plane.flipped());
1016

1017
		// and extrude the polygon into a cube, backwards of the plane:
1018
		var cube = polygon.extrude(plane.normal.times(-maxdistance));
1019

1020
		// Now we can do the intersection:
1021
		var result = this.intersect(cube);
1022
		result.properties = this.properties; // keep original properties
1023
		return result;
1024
	},
1025

1026
	// Connect a solid to another solid, such that two CSG.Connectors become connected
1027
	//   myConnector: a CSG.Connector of this solid
1028
	//   otherConnector: a CSG.Connector to which myConnector should be connected
1029
	//   mirror: false: the 'axis' vectors of the connectors should point in the same direction
1030
	//           true: the 'axis' vectors of the connectors should point in opposite direction
1031
	//   normalrotation: degrees of rotation between the 'normal' vectors of the two
1032
	//                   connectors
1033
	connectTo: function(myConnector, otherConnector, mirror, normalrotation) {
1034
		var matrix = myConnector.getTransformationTo(otherConnector, mirror, normalrotation);
1035
		return this.transform(matrix);
1036
	},
1037

1038
	// set the .shared property of all polygons
1039
	// Returns a new CSG solid, the original is unmodified!
1040
	setShared: function(shared) {
1041
		var polygons = this.polygons.map(function(p) {
1042
			return new CSG.Polygon(p.vertices, shared, p.plane);
1043
		});
1044
		var result = CSG.fromPolygons(polygons);
1045
		result.properties = this.properties; // keep original properties
1046
		result.isRetesselated = this.isRetesselated;
1047
		result.isCanonicalized = this.isCanonicalized;
1048
		return result;
1049
	},
1050

1051
	/**
1052
	 * @param {Array} color [red, green, blue] color values are float numbers 0..1
1053
	 * @return {CSG} new CSG instance
1054
	 */
1055
	setColor: function(red, green, blue, alpha) { //for backward compatibility
1056
		var color = red instanceof Array ? red : [red||0, green||0, blue||0, isNaN(alpha) ? 1. : alpha];
1057
		var newshared = new CSG.Polygon.Shared(color);
1058
		return this.setShared(newshared);
1059
	},
1060

1061
	toCompactBinary: function() {
1062
		var csg = this.canonicalized(),
1063
			numpolygons = csg.polygons.length,
1064
			numpolygonvertices = 0,
1065
			numvertices = 0,
1066
			vertexmap = {},
1067
			vertices = [],
1068
			numplanes = 0,
1069
			planemap = {},
1070
			polygonindex = 0,
1071
			planes = [],
1072
			shareds = [],
1073
			sharedmap = {},
1074
			numshared = 0;
1075
		// for (var i = 0, iMax = csg.polygons.length; i < iMax; i++) {
1076
		// 	var p = csg.polygons[i];
1077
		// 	for (var j = 0, jMax = p.length; j < jMax; j++) {
1078
		// 		++numpolygonvertices;
1079
		// 		var vertextag = p[j].getTag();
1080
		// 		if(!(vertextag in vertexmap)) {
1081
		// 			vertexmap[vertextag] = numvertices++;
1082
		// 			vertices.push(p[j]);
1083
		// 		}
1084
		// 	}
1085
		csg.polygons.map(function(p) {
1086
			p.vertices.map(function(v) {
1087
				++numpolygonvertices;
1088
				var vertextag = v.getTag();
1089
				if(!(vertextag in vertexmap)) {
1090
					vertexmap[vertextag] = numvertices++;
1091
					vertices.push(v);
1092
				}
1093
			});
1094

1095
			var planetag = p.plane.getTag();
1096
			if(!(planetag in planemap)) {
1097
				planemap[planetag] = numplanes++;
1098
				planes.push(p.plane);
1099
			}
1100
			var sharedtag = p.shared.getTag();
1101
			if(!(sharedtag in sharedmap)) {
1102
				sharedmap[sharedtag] = numshared++;
1103
				shareds.push(p.shared);
1104
			}
1105
		});
1106
		var numVerticesPerPolygon = new Uint32Array(numpolygons),
1107
			polygonSharedIndexes = new Uint32Array(numpolygons),
1108
			polygonVertices = new Uint32Array(numpolygonvertices),
1109
			polygonPlaneIndexes = new Uint32Array(numpolygons),
1110
			vertexData = new Float64Array(numvertices * 3),
1111
			planeData = new Float64Array(numplanes * 4),
1112
			polygonVerticesIndex = 0;
1113
		for(var polygonindex = 0; polygonindex < numpolygons; ++polygonindex) {
1114
			var p = csg.polygons[polygonindex];
1115
			numVerticesPerPolygon[polygonindex] = p.vertices.length;
1116
			p.vertices.map(function(v) {
1117
				var vertextag = v.getTag();
1118
				var vertexindex = vertexmap[vertextag];
1119
				polygonVertices[polygonVerticesIndex++] = vertexindex;
1120
			});
1121
			var planetag = p.plane.getTag();
1122
			var planeindex = planemap[planetag];
1123
			polygonPlaneIndexes[polygonindex] = planeindex;
1124
			var sharedtag = p.shared.getTag();
1125
			var sharedindex = sharedmap[sharedtag];
1126
			polygonSharedIndexes[polygonindex] = sharedindex;
1127
		}
1128
		var verticesArrayIndex = 0;
1129
		vertices.map(function(v) {
1130
			var pos = v.pos;
1131
			vertexData[verticesArrayIndex++] = pos._x;
1132
			vertexData[verticesArrayIndex++] = pos._y;
1133
			vertexData[verticesArrayIndex++] = pos._z;
1134
		});
1135
		var planesArrayIndex = 0;
1136
		planes.map(function(p) {
1137
			var normal = p.normal;
1138
			planeData[planesArrayIndex++] = normal._x;
1139
			planeData[planesArrayIndex++] = normal._y;
1140
			planeData[planesArrayIndex++] = normal._z;
1141
			planeData[planesArrayIndex++] = p.w;
1142
		});
1143
		var result = {
1144
			"class": "CSG",
1145
			numPolygons: numpolygons,
1146
			numVerticesPerPolygon: numVerticesPerPolygon,
1147
			polygonPlaneIndexes: polygonPlaneIndexes,
1148
			polygonSharedIndexes: polygonSharedIndexes,
1149
			polygonVertices: polygonVertices,
1150
			vertexData: vertexData,
1151
			planeData: planeData,
1152
			shared: shareds
1153
		};
1154
		return result;
1155
	},
1156

1157
	// For debugging
1158
	// Creates a new solid with a tiny cube at every vertex of the source solid
1159
	toPointCloud: function(cuberadius) {
1160
		var csg = this.reTesselated();
1161

1162
		var result = new CSG();
1163

1164
		// make a list of all unique vertices
1165
		// For each vertex we also collect the list of normals of the planes touching the vertices
1166
		var vertexmap = {};
1167
		csg.polygons.map(function(polygon) {
1168
			polygon.vertices.map(function(vertex) {
1169
				vertexmap[vertex.getTag()] = vertex.pos;
1170
			});
1171
		});
1172

1173
		for(var vertextag in vertexmap) {
1174
			var pos = vertexmap[vertextag];
1175
			var cube = CSG.cube({
1176
				center: pos,
1177
				radius: cuberadius
1178
			});
1179
			result = result.unionSub(cube, false, false);
1180
		}
1181
		result = result.reTesselated();
1182
		return result;
1183
	},
1184

1185
	// Get the transformation that transforms this CSG such that it is lying on the z=0 plane,
1186
	// as flat as possible (i.e. the least z-height).
1187
	// So that it is in an orientation suitable for CNC milling
1188
	getTransformationToFlatLying: function() {
1189
		if(this.polygons.length === 0) {
1190
			return new CSG.Matrix4x4(); // unity
1191
		} else {
1192
			// get a list of unique planes in the CSG:
1193
			var csg = this.canonicalized();
1194
			var planemap = {};
1195
			csg.polygons.map(function(polygon) {
1196
				planemap[polygon.plane.getTag()] = polygon.plane;
1197
			});
1198
			// try each plane in the CSG and find the plane that, when we align it flat onto z=0,
1199
			// gives the least height in z-direction.
1200
			// If two planes give the same height, pick the plane that originally had a normal closest
1201
			// to [0,0,-1].
1202
			var xvector = new CSG.Vector3D(1, 0, 0);
1203
			var yvector = new CSG.Vector3D(0, 1, 0);
1204
			var zvector = new CSG.Vector3D(0, 0, 1);
1205
			var z0connectorx = new CSG.Connector([0, 0, 0], [0, 0, -1], xvector);
1206
			var z0connectory = new CSG.Connector([0, 0, 0], [0, 0, -1], yvector);
1207
			var isfirst = true;
1208
			var minheight = 0;
1209
			var maxdotz = 0;
1210
			var besttransformation;
1211
			for(var planetag in planemap) {
1212
				var plane = planemap[planetag];
1213
				var pointonplane = plane.normal.times(plane.w);
1214
				var transformation;
1215
				// We need a normal vecrtor for the transformation
1216
				// determine which is more perpendicular to the plane normal: x or y?
1217
				// we will align this as much as possible to the x or y axis vector
1218
				var xorthogonality = plane.normal.cross(xvector).length();
1219
				var yorthogonality = plane.normal.cross(yvector).length();
1220
				if(xorthogonality > yorthogonality) {
1221
					// x is better:
1222
					var planeconnector = new CSG.Connector(pointonplane, plane.normal, xvector);
1223
					transformation = planeconnector.getTransformationTo(z0connectorx, false, 0);
1224
				} else {
1225
					// y is better:
1226
					var planeconnector = new CSG.Connector(pointonplane, plane.normal, yvector);
1227
					transformation = planeconnector.getTransformationTo(z0connectory, false, 0);
1228
				}
1229
				var transformedcsg = csg.transform(transformation);
1230
				var dotz = -plane.normal.dot(zvector);
1231
				var bounds = transformedcsg.getBounds();
1232
				var zheight = bounds[1].z - bounds[0].z;
1233
				var isbetter = isfirst;
1234
				if(!isbetter) {
1235
					if(zheight < minheight) {
1236
						isbetter = true;
1237
					} else if(zheight == minheight) {
1238
						if(dotz > maxdotz) isbetter = true;
1239
					}
1240
				}
1241
				if(isbetter) {
1242
					// translate the transformation around the z-axis and onto the z plane:
1243
					var translation = [
1244
						-0.5 * (bounds[1].x + bounds[0].x),
1245
						-0.5 * (bounds[1].y + bounds[0].y),
1246
						-bounds[0].z];
1247
					transformation = transformation.multiply(CSG.Matrix4x4.translation(translation));
1248
					minheight = zheight;
1249
					maxdotz = dotz;
1250
					besttransformation = transformation;
1251
				}
1252
				isfirst = false;
1253
			}
1254
			return besttransformation;
1255
		}
1256
	},
1257

1258
	lieFlat: function() {
1259
		var transformation = this.getTransformationToFlatLying();
1260
		return this.transform(transformation);
1261
	},
1262

1263
	// project the 3D CSG onto a plane
1264
	// This returns a 2D CAG with the 'shadow' shape of the 3D solid when projected onto the
1265
	// plane represented by the orthonormal basis
1266
	projectToOrthoNormalBasis: function(orthobasis) {
1267
		var cags = [];
1268
		this.polygons.map(function(polygon) {
1269
			var cag = polygon.projectToOrthoNormalBasis(orthobasis);
1270
			if(cag.sides.length > 0) {
1271
				cags.push(cag);
1272
			}
1273
		});
1274
		var result = new CAG().union(cags);
1275
		return result;
1276
	},
1277

1278
	sectionCut: function(orthobasis) {
1279
		var plane1 = orthobasis.plane;
1280
		var plane2 = orthobasis.plane.flipped();
1281
		plane1 = new CSG.Plane(plane1.normal, plane1.w + 1e-4);
1282
		plane2 = new CSG.Plane(plane2.normal, plane2.w + 1e-4);
1283
		var cut3d = this.cutByPlane(plane1);
1284
		cut3d = cut3d.cutByPlane(plane2);
1285
		return cut3d.projectToOrthoNormalBasis(orthobasis);
1286
	},
1287

1288
	/*
1289
  fixTJunctions:
1290

1291
  Suppose we have two polygons ACDB and EDGF:
1292

1293
   A-----B
1294
   |     |
1295
   |     E--F
1296
   |     |  |
1297
   C-----D--G
1298

1299
  Note that vertex E forms a T-junction on the side BD. In this case some STL slicers will complain
1300
  that the solid is not watertight. This is because the watertightness check is done by checking if
1301
  each side DE is matched by another side ED.
1302

1303
  This function will return a new solid with ACDB replaced by ACDEB
1304

1305
  Note that this can create polygons that are slightly non-convex (due to rounding errors). Therefore the result should
1306
  not be used for further CSG operations!
1307
  */
1308
	fixTJunctions: function() {
1309
		var csg = this.canonicalized();
1310
		var sidemap = {};
1311
		for(var polygonindex = 0; polygonindex < csg.polygons.length; polygonindex++) {
1312
			var polygon = csg.polygons[polygonindex];
1313
			var numvertices = polygon.vertices.length;
1314
			if(numvertices >= 3) // should be true
1315
			{
1316
				var vertex = polygon.vertices[0];
1317
				var vertextag = vertex.getTag();
1318
				for(var vertexindex = 0; vertexindex < numvertices; vertexindex++) {
1319
					var nextvertexindex = vertexindex + 1;
1320
					if(nextvertexindex == numvertices) nextvertexindex = 0;
1321
					var nextvertex = polygon.vertices[nextvertexindex];
1322
					var nextvertextag = nextvertex.getTag();
1323
					var sidetag = vertextag + "/" + nextvertextag;
1324
					var reversesidetag = nextvertextag + "/" + vertextag;
1325
					if(reversesidetag in sidemap) {
1326
						// this side matches the same side in another polygon. Remove from sidemap:
1327
						var ar = sidemap[reversesidetag];
1328
						ar.splice(-1, 1);
1329
						if(ar.length === 0) {
1330
							delete sidemap[reversesidetag];
1331
						}
1332
					} else {
1333
						var sideobj = {
1334
							vertex0: vertex,
1335
							vertex1: nextvertex,
1336
							polygonindex: polygonindex
1337
						};
1338
						if(!(sidetag in sidemap)) {
1339
							sidemap[sidetag] = [sideobj];
1340
						} else {
1341
							sidemap[sidetag].push(sideobj);
1342
						}
1343
					}
1344
					vertex = nextvertex;
1345
					vertextag = nextvertextag;
1346
				}
1347
			}
1348
		}
1349
		// now sidemap contains 'unmatched' sides
1350
		// i.e. side AB in one polygon does not have a matching side BA in another polygon
1351
		var vertextag2sidestart = {};
1352
		var vertextag2sideend = {};
1353
		var sidestocheck = {};
1354
		var sidemapisempty = true;
1355
		for(var sidetag in sidemap) {
1356
			sidemapisempty = false;
1357
			sidestocheck[sidetag] = true;
1358
			sidemap[sidetag].map(function(sideobj) {
1359
				var starttag = sideobj.vertex0.getTag();
1360
				var endtag = sideobj.vertex1.getTag();
1361
				if(starttag in vertextag2sidestart) {
1362
					vertextag2sidestart[starttag].push(sidetag);
1363
				} else {
1364
					vertextag2sidestart[starttag] = [sidetag];
1365
				}
1366
				if(endtag in vertextag2sideend) {
1367
					vertextag2sideend[endtag].push(sidetag);
1368
				} else {
1369
					vertextag2sideend[endtag] = [sidetag];
1370
				}
1371
			});
1372
		}
1373

1374
		if(!sidemapisempty) {
1375
			// make a copy of the polygons array, since we are going to modify it:
1376
			var polygons = csg.polygons.slice(0);
1377

1378
			function addSide (vertex0, vertex1, polygonindex) {
1379
				var starttag = vertex0.getTag();
1380
				var endtag = vertex1.getTag();
1381
				if(starttag == endtag) throw new Error("Assertion failed");
1382
				var newsidetag = starttag + "/" + endtag;
1383
				var reversesidetag = endtag + "/" + starttag;
1384
				if(reversesidetag in sidemap) {
1385
					// we have a matching reverse oriented side.
1386
					// Instead of adding the new side, cancel out the reverse side:
1387
					// console.log("addSide("+newsidetag+") has reverse side:");
1388
					deleteSide(vertex1, vertex0, null);
1389
					return null;
1390
				}
1391
				//  console.log("addSide("+newsidetag+")");
1392
				var newsideobj = {
1393
					vertex0: vertex0,
1394
					vertex1: vertex1,
1395
					polygonindex: polygonindex
1396
				};
1397
				if(!(newsidetag in sidemap)) {
1398
					sidemap[newsidetag] = [newsideobj];
1399
				} else {
1400
					sidemap[newsidetag].push(newsideobj);
1401
				}
1402
				if(starttag in vertextag2sidestart) {
1403
					vertextag2sidestart[starttag].push(newsidetag);
1404
				} else {
1405
					vertextag2sidestart[starttag] = [newsidetag];
1406
				}
1407
				if(endtag in vertextag2sideend) {
1408
					vertextag2sideend[endtag].push(newsidetag);
1409
				} else {
1410
					vertextag2sideend[endtag] = [newsidetag];
1411
				}
1412
				return newsidetag;
1413
			}
1414

1415
			function deleteSide (vertex0, vertex1, polygonindex) {
1416
				var starttag = vertex0.getTag();
1417
				var endtag = vertex1.getTag();
1418
				var sidetag = starttag + "/" + endtag;
1419
				// console.log("deleteSide("+sidetag+")");
1420
				if(!(sidetag in sidemap)) throw new Error("Assertion failed");
1421
				var idx = -1;
1422
				var sideobjs = sidemap[sidetag];
1423
				for(var i = 0; i < sideobjs.length; i++) {
1424
					var sideobj = sideobjs[i];
1425
					if(sideobj.vertex0 != vertex0) continue;
1426
					if(sideobj.vertex1 != vertex1) continue;
1427
					if(polygonindex !== null) {
1428
						if(sideobj.polygonindex != polygonindex) continue;
1429
					}
1430
					idx = i;
1431
					break;
1432
				}
1433
				if(idx < 0) throw new Error("Assertion failed");
1434
				sideobjs.splice(idx, 1);
1435
				if(sideobjs.length === 0) {
1436
					delete sidemap[sidetag];
1437
				}
1438
				idx = vertextag2sidestart[starttag].indexOf(sidetag);
1439
				if(idx < 0) throw new Error("Assertion failed");
1440
				vertextag2sidestart[starttag].splice(idx, 1);
1441
				if(vertextag2sidestart[starttag].length === 0) {
1442
					delete vertextag2sidestart[starttag];
1443
				}
1444

1445
				idx = vertextag2sideend[endtag].indexOf(sidetag);
1446
				if(idx < 0) throw new Error("Assertion failed");
1447
				vertextag2sideend[endtag].splice(idx, 1);
1448
				if(vertextag2sideend[endtag].length === 0) {
1449
					delete vertextag2sideend[endtag];
1450
				}
1451
			}
1452

1453

1454
			while(true) {
1455
				var sidemapisempty = true;
1456
				for(var sidetag in sidemap) {
1457
					sidemapisempty = false;
1458
					sidestocheck[sidetag] = true;
1459
				}
1460
				if(sidemapisempty) break;
1461
				var donesomething = false;
1462
				while(true) {
1463
					var sidetagtocheck = null;
1464
					for(var sidetag in sidestocheck) {
1465
						sidetagtocheck = sidetag;
1466
						break;
1467
					}
1468
					if(sidetagtocheck === null) break; // sidestocheck is empty, we're done!
1469
					var donewithside = true;
1470
					if(sidetagtocheck in sidemap) {
1471
						var sideobjs = sidemap[sidetagtocheck];
1472
						if(sideobjs.length === 0) throw new Error("Assertion failed");
1473
						var sideobj = sideobjs[0];
1474
						for(var directionindex = 0; directionindex < 2; directionindex++) {
1475
							var startvertex = (directionindex === 0) ? sideobj.vertex0 : sideobj.vertex1;
1476
							var endvertex = (directionindex === 0) ? sideobj.vertex1 : sideobj.vertex0;
1477
							var startvertextag = startvertex.getTag();
1478
							var endvertextag = endvertex.getTag();
1479
							var matchingsides = [];
1480
							if(directionindex === 0) {
1481
								if(startvertextag in vertextag2sideend) {
1482
									matchingsides = vertextag2sideend[startvertextag];
1483
								}
1484
							} else {
1485
								if(startvertextag in vertextag2sidestart) {
1486
									matchingsides = vertextag2sidestart[startvertextag];
1487
								}
1488
							}
1489
							for(var matchingsideindex = 0; matchingsideindex < matchingsides.length; matchingsideindex++) {
1490
								var matchingsidetag = matchingsides[matchingsideindex];
1491
								var matchingside = sidemap[matchingsidetag][0];
1492
								var matchingsidestartvertex = (directionindex === 0) ? matchingside.vertex0 : matchingside.vertex1;
1493
								var matchingsideendvertex = (directionindex === 0) ? matchingside.vertex1 : matchingside.vertex0;
1494
								var matchingsidestartvertextag = matchingsidestartvertex.getTag();
1495
								var matchingsideendvertextag = matchingsideendvertex.getTag();
1496
								if(matchingsideendvertextag != startvertextag) throw new Error("Assertion failed");
1497
								if(matchingsidestartvertextag == endvertextag) {
1498
									// matchingside cancels sidetagtocheck
1499
									deleteSide(startvertex, endvertex, null);
1500
									deleteSide(endvertex, startvertex, null);
1501
									donewithside = false;
1502
									directionindex = 2; // skip reverse direction check
1503
									donesomething = true;
1504
									break;
1505
								} else {
1506
									var startpos = startvertex.pos;
1507
									var endpos = endvertex.pos;
1508
									var checkpos = matchingsidestartvertex.pos;
1509
									var direction = checkpos.minus(startpos);
1510
									// Now we need to check if endpos is on the line startpos-checkpos:
1511
									var t = endpos.minus(startpos).dot(direction) / direction.dot(direction);
1512
									if((t > 0) && (t < 1)) {
1513
										var closestpoint = startpos.plus(direction.times(t));
1514
										var distancesquared = closestpoint.distanceToSquared(endpos);
1515
										if(distancesquared < 1e-10) {
1516
											// Yes it's a t-junction! We need to split matchingside in two:
1517
											var polygonindex = matchingside.polygonindex;
1518
											var polygon = polygons[polygonindex];
1519
											// find the index of startvertextag in polygon:
1520
											var insertionvertextag = matchingside.vertex1.getTag();
1521
											var insertionvertextagindex = -1;
1522
											for(var i = 0; i < polygon.vertices.length; i++) {
1523
												if(polygon.vertices[i].getTag() == insertionvertextag) {
1524
													insertionvertextagindex = i;
1525
													break;
1526
												}
1527
											}
1528
											if(insertionvertextagindex < 0) throw new Error("Assertion failed");
1529
											// split the side by inserting the vertex:
1530
											var newvertices = polygon.vertices.slice(0);
1531
											newvertices.splice(insertionvertextagindex, 0, endvertex);
1532
											var newpolygon = new CSG.Polygon(newvertices, polygon.shared /*polygon.plane*/ );
1533
											polygons[polygonindex] = newpolygon;
1534

1535
											// remove the original sides from our maps:
1536
											// deleteSide(sideobj.vertex0, sideobj.vertex1, null);
1537
											deleteSide(matchingside.vertex0, matchingside.vertex1, polygonindex);
1538
											var newsidetag1 = addSide(matchingside.vertex0, endvertex, polygonindex);
1539
											var newsidetag2 = addSide(endvertex, matchingside.vertex1, polygonindex);
1540
											if(newsidetag1 !== null) sidestocheck[newsidetag1] = true;
1541
											if(newsidetag2 !== null) sidestocheck[newsidetag2] = true;
1542
											donewithside = false;
1543
											directionindex = 2; // skip reverse direction check
1544
											donesomething = true;
1545
											break;
1546
										} // if(distancesquared < 1e-10)
1547
									} // if( (t > 0) && (t < 1) )
1548
								} // if(endingstidestartvertextag == endvertextag)
1549
							} // for matchingsideindex
1550
						} // for directionindex
1551
					} // if(sidetagtocheck in sidemap)
1552
					if(donewithside) {
1553
						delete sidestocheck[sidetag];
1554
					}
1555
				}
1556
				if(!donesomething) break;
1557
			}
1558
			var newcsg = CSG.fromPolygons(polygons);
1559
			newcsg.properties = csg.properties;
1560
			newcsg.isCanonicalized = true;
1561
			newcsg.isRetesselated = true;
1562
			csg = newcsg;
1563
		} // if(!sidemapisempty)
1564
		var sidemapisempty = true;
1565
		for(var sidetag in sidemap) {
1566
			sidemapisempty = false;
1567
			break;
1568
		}
1569
		if(!sidemapisempty) {
1570
			throw new Error("!sidemapisempty");
1571
		}
1572
		return csg;
1573
	}
1574
};
1575

1576
// Parse an option from the options object
1577
// If the option is not present, return the default value
1578
CSG.parseOption = function(options, optionname, defaultvalue) {
1579
	var result = defaultvalue;
1580
	if(options) {
1581
		if(optionname in options) {
1582
			result = options[optionname];
1583
		}
1584
	}
1585
	return result;
1586
};
1587

1588
// Parse an option and force into a CSG.Vector3D. If a scalar is passed it is converted
1589
// into a vector with equal x,y,z
1590
CSG.parseOptionAs3DVector = function(options, optionname, defaultvalue) {
1591
	var result = CSG.parseOption(options, optionname, defaultvalue);
1592
	result = new CSG.Vector3D(result);
1593
	return result;
1594
};
1595

1596
// Parse an option and force into a CSG.Vector2D. If a scalar is passed it is converted
1597
// into a vector with equal x,y
1598
CSG.parseOptionAs2DVector = function(options, optionname, defaultvalue) {
1599
	var result = CSG.parseOption(options, optionname, defaultvalue);
1600
	result = new CSG.Vector2D(result);
1601
	return result;
1602
};
1603

1604
CSG.parseOptionAsFloat = function(options, optionname, defaultvalue) {
1605
	var result = CSG.parseOption(options, optionname, defaultvalue);
1606
	if(typeof(result) == "string") {
1607
		result = Number(result);
1608
	}
1609
	if(isNaN(result) || typeof(result) != "number") {
1610
		throw new Error("Parameter " + optionname + " should be a number");
1611
	}
1612
	return result;
1613
};
1614

1615
CSG.parseOptionAsInt = function(options, optionname, defaultvalue) {
1616
	var result = CSG.parseOption(options, optionname, defaultvalue);
1617
	result = Number(Math.floor(result));
1618
	if (isNaN(result)) {
1619
		throw new Error("Parameter " + optionname + " should be a number");
1620
	}
1621
	return result;
1622
};
1623

1624
CSG.parseOptionAsBool = function(options, optionname, defaultvalue) {
1625
	var result = CSG.parseOption(options, optionname, defaultvalue);
1626
	if(typeof(result) == "string") {
1627
		if(result == "true") result = true;
1628
		else if(result == "false") result = false;
1629
		else if(result == 0) result = false;
1630
	}
1631
	result = !! result;
1632
	return result;
1633
};
1634

1635
// Construct an axis-aligned solid cuboid.
1636
// Parameters:
1637
//   center: center of cube (default [0,0,0])
1638
//   radius: radius of cube (default [1,1,1]), can be specified as scalar or as 3D vector
1639
//
1640
// Example code:
1641
//
1642
//     var cube = CSG.cube({
1643
//       center: [0, 0, 0],
1644
//       radius: 1
1645
//     });
1646
CSG.cube = function(options) {
1647
	var c = CSG.parseOptionAs3DVector(options, "center", [0, 0, 0]);
1648
	var r = CSG.parseOptionAs3DVector(options, "radius", [1, 1, 1]);
1649
	var result = CSG.fromPolygons([
1650
		[
1651
			[0, 4, 6, 2],
1652
			[-1, 0, 0]
1653
		],
1654
		[
1655
			[1, 3, 7, 5],
1656
			[+1, 0, 0]
1657
		],
1658
		[
1659
			[0, 1, 5, 4],
1660
			[0, -1, 0]
1661
		],
1662
		[
1663
			[2, 6, 7, 3],
1664
			[0, +1, 0]
1665
		],
1666
		[
1667
			[0, 2, 3, 1],
1668
			[0, 0, -1]
1669
		],
1670
		[
1671
			[4, 5, 7, 6],
1672
			[0, 0, +1]
1673
		]
1674
	].map(function(info) {
1675
		//var normal = new CSG.Vector3D(info[1]);
1676
		//var plane = new CSG.Plane(normal, 1);
1677
		var vertices = info[0].map(function(i) {
1678
			var pos = new CSG.Vector3D(
1679
			c.x + r.x * (2 * !! (i & 1) - 1), c.y + r.y * (2 * !! (i & 2) - 1), c.z + r.z * (2 * !! (i & 4) - 1));
1680
			return new CSG.Vertex(pos);
1681
		});
1682
		return new CSG.Polygon(vertices, null /* , plane */ );
1683
	}));
1684
	result.properties.cube = new CSG.Properties();
1685
	result.properties.cube.center = new CSG.Vector3D(c);
1686
	// add 6 connectors, at the centers of each face:
1687
	result.properties.cube.facecenters = [
1688
		new CSG.Connector(new CSG.Vector3D([r.x, 0, 0]).plus(c), [1, 0, 0], [0, 0, 1]),
1689
		new CSG.Connector(new CSG.Vector3D([-r.x, 0, 0]).plus(c), [-1, 0, 0], [0, 0, 1]),
1690
		new CSG.Connector(new CSG.Vector3D([0, r.y, 0]).plus(c), [0, 1, 0], [0, 0, 1]),
1691
		new CSG.Connector(new CSG.Vector3D([0, -r.y, 0]).plus(c), [0, -1, 0], [0, 0, 1]),
1692
		new CSG.Connector(new CSG.Vector3D([0, 0, r.z]).plus(c), [0, 0, 1], [1, 0, 0]),
1693
		new CSG.Connector(new CSG.Vector3D([0, 0, -r.z]).plus(c), [0, 0, -1], [1, 0, 0])
1694
	];
1695
	return result;
1696
};
1697

1698
// Construct a solid sphere
1699
//
1700
// Parameters:
1701
//   center: center of sphere (default [0,0,0])
1702
//   radius: radius of sphere (default 1), must be a scalar
1703
//   resolution: determines the number of polygons per 360 degree revolution (default 12)
1704
//   axes: (optional) an array with 3 vectors for the x, y and z base vectors
1705
//
1706
// Example usage:
1707
//
1708
//     var sphere = CSG.sphere({
1709
//       center: [0, 0, 0],
1710
//       radius: 2,
1711
//       resolution: 32,
1712
//     });
1713
CSG.sphere = function(options) {
1714
	options = options || {};
1715
	var center = CSG.parseOptionAs3DVector(options, "center", [0, 0, 0]);
1716
	var radius = CSG.parseOptionAsFloat(options, "radius", 1);
1717
	var resolution = CSG.parseOptionAsInt(options, "resolution", CSG.defaultResolution3D);
1718
	var xvector, yvector, zvector;
1719
	if('axes' in options) {
1720
		xvector = options.axes[0].unit().times(radius);
1721
		yvector = options.axes[1].unit().times(radius);
1722
		zvector = options.axes[2].unit().times(radius);
1723
	} else {
1724
		xvector = new CSG.Vector3D([1, 0, 0]).times(radius);
1725
		yvector = new CSG.Vector3D([0, -1, 0]).times(radius);
1726
		zvector = new CSG.Vector3D([0, 0, 1]).times(radius);
1727
	}
1728
	if(resolution < 4) resolution = 4;
1729
	var qresolution = Math.round(resolution / 4);
1730
	var prevcylinderpoint;
1731
	var polygons = [];
1732
	for(var slice1 = 0; slice1 <= resolution; slice1++) {
1733
		var angle = Math.PI * 2.0 * slice1 / resolution;
1734
		var cylinderpoint = xvector.times(Math.cos(angle)).plus(yvector.times(Math.sin(angle)));
1735
		if(slice1 > 0) {
1736
			// cylinder vertices:
1737
			var vertices = [];
1738
			var prevcospitch, prevsinpitch;
1739
			for(var slice2 = 0; slice2 <= qresolution; slice2++) {
1740
				var pitch = 0.5 * Math.PI * slice2 / qresolution;
1741
				var cospitch = Math.cos(pitch);
1742
				var sinpitch = Math.sin(pitch);
1743
				if(slice2 > 0) {
1744
					vertices = [];
1745
					vertices.push(new CSG.Vertex(center.plus(prevcylinderpoint.times(prevcospitch).minus(zvector.times(prevsinpitch)))));
1746
					vertices.push(new CSG.Vertex(center.plus(cylinderpoint.times(prevcospitch).minus(zvector.times(prevsinpitch)))));
1747
					if(slice2 < qresolution) {
1748
						vertices.push(new CSG.Vertex(center.plus(cylinderpoint.times(cospitch).minus(zvector.times(sinpitch)))));
1749
					}
1750
					vertices.push(new CSG.Vertex(center.plus(prevcylinderpoint.times(cospitch).minus(zvector.times(sinpitch)))));
1751
					polygons.push(new CSG.Polygon(vertices));
1752
					vertices = [];
1753
					vertices.push(new CSG.Vertex(center.plus(prevcylinderpoint.times(prevcospitch).plus(zvector.times(prevsinpitch)))));
1754
					vertices.push(new CSG.Vertex(center.plus(cylinderpoint.times(prevcospitch).plus(zvector.times(prevsinpitch)))));
1755
					if(slice2 < qresolution) {
1756
						vertices.push(new CSG.Vertex(center.plus(cylinderpoint.times(cospitch).plus(zvector.times(sinpitch)))));
1757
					}
1758
					vertices.push(new CSG.Vertex(center.plus(prevcylinderpoint.times(cospitch).plus(zvector.times(sinpitch)))));
1759
					vertices.reverse();
1760
					polygons.push(new CSG.Polygon(vertices));
1761
				}
1762
				prevcospitch = cospitch;
1763
				prevsinpitch = sinpitch;
1764
			}
1765
		}
1766
		prevcylinderpoint = cylinderpoint;
1767
	}
1768
	var result = CSG.fromPolygons(polygons);
1769
	result.properties.sphere = new CSG.Properties();
1770
	result.properties.sphere.center = new CSG.Vector3D(center);
1771
	result.properties.sphere.facepoint = center.plus(xvector);
1772
	return result;
1773
};
1774

1775
// Construct a solid cylinder.
1776
//
1777
// Parameters:
1778
//   start: start point of cylinder (default [0, -1, 0])
1779
//   end: end point of cylinder (default [0, 1, 0])
1780
//   radius: radius of cylinder (default 1), must be a scalar
1781
//   resolution: determines the number of polygons per 360 degree revolution (default 12)
1782
//
1783
// Example usage:
1784
//
1785
//     var cylinder = CSG.cylinder({
1786
//       start: [0, -1, 0],
1787
//       end: [0, 1, 0],
1788
//       radius: 1,
1789
//       resolution: 16
1790
//     });
1791
CSG.cylinder = function(options) {
1792
	var s = CSG.parseOptionAs3DVector(options, "start", [0, -1, 0]);
1793
	var e = CSG.parseOptionAs3DVector(options, "end", [0, 1, 0]);
1794
	var r = CSG.parseOptionAsFloat(options, "radius", 1);
1795
	var rEnd = CSG.parseOptionAsFloat(options, "radiusEnd", r);
1796
	var rStart = CSG.parseOptionAsFloat(options, "radiusStart", r);
1797

1798
	if((rEnd < 0) || (rStart < 0)) {
1799
		throw new Error("Radius should be non-negative");
1800
	}
1801
	if((rEnd === 0) && (rStart === 0)) {
1802
		throw new Error("Either radiusStart or radiusEnd should be positive");
1803
	}
1804

1805
	var slices = CSG.parseOptionAsFloat(options, "resolution", CSG.defaultResolution2D);
1806
	var ray = e.minus(s);
1807
	var axisZ = ray.unit(); //, isY = (Math.abs(axisZ.y) > 0.5);
1808
	var axisX = axisZ.randomNonParallelVector().unit();
1809

1810
	//  var axisX = new CSG.Vector3D(isY, !isY, 0).cross(axisZ).unit();
1811
	var axisY = axisX.cross(axisZ).unit();
1812
	var start = new CSG.Vertex(s);
1813
	var end = new CSG.Vertex(e);
1814
	var polygons = [];
1815

1816
	function point(stack, slice, radius) {
1817
		var angle = slice * Math.PI * 2;
1818
		var out = axisX.times(Math.cos(angle)).plus(axisY.times(Math.sin(angle)));
1819
		var pos = s.plus(ray.times(stack)).plus(out.times(radius));
1820
		return new CSG.Vertex(pos);
1821
	}
1822
	for(var i = 0; i < slices; i++) {
1823
		var t0 = i / slices,
1824
			t1 = (i + 1) / slices;
1825
		if(rEnd == rStart) {
1826
			polygons.push(new CSG.Polygon([start, point(0, t0, rEnd), point(0, t1, rEnd)]));
1827
			polygons.push(new CSG.Polygon([point(0, t1, rEnd), point(0, t0, rEnd), point(1, t0, rEnd), point(1, t1, rEnd)]));
1828
			polygons.push(new CSG.Polygon([end, point(1, t1, rEnd), point(1, t0, rEnd)]));
1829
		} else {
1830
			if(rStart > 0) {
1831
				polygons.push(new CSG.Polygon([start, point(0, t0, rStart), point(0, t1, rStart)]));
1832
				polygons.push(new CSG.Polygon([point(0, t0, rStart), point(1, t0, rEnd), point(0, t1, rStart)]));
1833
			}
1834
			if(rEnd > 0) {
1835
				polygons.push(new CSG.Polygon([end, point(1, t1, rEnd), point(1, t0, rEnd)]));
1836
				polygons.push(new CSG.Polygon([point(1, t0, rEnd), point(1, t1, rEnd), point(0, t1, rStart)]));
1837
			}
1838
		}
1839
	}
1840
	var result = CSG.fromPolygons(polygons);
1841
	result.properties.cylinder = new CSG.Properties();
1842
	result.properties.cylinder.start = new CSG.Connector(s, axisZ.negated(), axisX);
1843
	result.properties.cylinder.end = new CSG.Connector(e, axisZ, axisX);
1844
	result.properties.cylinder.facepoint = s.plus(axisX.times(rStart));
1845
	return result;
1846
};
1847

1848
// Like a cylinder, but with rounded ends instead of flat
1849
//
1850
// Parameters:
1851
//   start: start point of cylinder (default [0, -1, 0])
1852
//   end: end point of cylinder (default [0, 1, 0])
1853
//   radius: radius of cylinder (default 1), must be a scalar
1854
//   resolution: determines the number of polygons per 360 degree revolution (default 12)
1855
//   normal: a vector determining the starting angle for tesselation. Should be non-parallel to start.minus(end)
1856
//
1857
// Example usage:
1858
//
1859
//     var cylinder = CSG.roundedCylinder({
1860
//       start: [0, -1, 0],
1861
//       end: [0, 1, 0],
1862
//       radius: 1,
1863
//       resolution: 16
1864
//     });
1865
CSG.roundedCylinder = function(options) {
1866
	var p1 = CSG.parseOptionAs3DVector(options, "start", [0, -1, 0]);
1867
	var p2 = CSG.parseOptionAs3DVector(options, "end", [0, 1, 0]);
1868
	var radius = CSG.parseOptionAsFloat(options, "radius", 1);
1869
	var direction = p2.minus(p1);
1870
	var defaultnormal;
1871
	if(Math.abs(direction.x) > Math.abs(direction.y)) {
1872
		defaultnormal = new CSG.Vector3D(0, 1, 0);
1873
	} else {
1874
		defaultnormal = new CSG.Vector3D(1, 0, 0);
1875
	}
1876
	var normal = CSG.parseOptionAs3DVector(options, "normal", defaultnormal);
1877
	var resolution = CSG.parseOptionAsFloat(options, "resolution", CSG.defaultResolution3D);
1878
	if(resolution < 4) resolution = 4;
1879
	var polygons = [];
1880
	var qresolution = Math.floor(0.25 * resolution);
1881
	var length = direction.length();
1882
	if(length < 1e-10) {
1883
		return CSG.sphere({
1884
			center: p1,
1885
			radius: radius,
1886
			resolution: resolution
1887
		});
1888
	}
1889
	var zvector = direction.unit().times(radius);
1890
	var xvector = zvector.cross(normal).unit().times(radius);
1891
	var yvector = xvector.cross(zvector).unit().times(radius);
1892
	var prevcylinderpoint;
1893
	for(var slice1 = 0; slice1 <= resolution; slice1++) {
1894
		var angle = Math.PI * 2.0 * slice1 / resolution;
1895
		var cylinderpoint = xvector.times(Math.cos(angle)).plus(yvector.times(Math.sin(angle)));
1896
		if(slice1 > 0) {
1897
			// cylinder vertices:
1898
			var vertices = [];
1899
			vertices.push(new CSG.Vertex(p1.plus(cylinderpoint)));
1900
			vertices.push(new CSG.Vertex(p1.plus(prevcylinderpoint)));
1901
			vertices.push(new CSG.Vertex(p2.plus(prevcylinderpoint)));
1902
			vertices.push(new CSG.Vertex(p2.plus(cylinderpoint)));
1903
			polygons.push(new CSG.Polygon(vertices));
1904
			var prevcospitch, prevsinpitch;
1905
			for(var slice2 = 0; slice2 <= qresolution; slice2++) {
1906
				var pitch = 0.5 * Math.PI * slice2 / qresolution;
1907
				//var pitch = Math.asin(slice2/qresolution);
1908
				var cospitch = Math.cos(pitch);
1909
				var sinpitch = Math.sin(pitch);
1910
				if(slice2 > 0) {
1911
					vertices = [];
1912
					vertices.push(new CSG.Vertex(p1.plus(prevcylinderpoint.times(prevcospitch).minus(zvector.times(prevsinpitch)))));
1913
					vertices.push(new CSG.Vertex(p1.plus(cylinderpoint.times(prevcospitch).minus(zvector.times(prevsinpitch)))));
1914
					if(slice2 < qresolution) {
1915
						vertices.push(new CSG.Vertex(p1.plus(cylinderpoint.times(cospitch).minus(zvector.times(sinpitch)))));
1916
					}
1917
					vertices.push(new CSG.Vertex(p1.plus(prevcylinderpoint.times(cospitch).minus(zvector.times(sinpitch)))));
1918
					polygons.push(new CSG.Polygon(vertices));
1919
					vertices = [];
1920
					vertices.push(new CSG.Vertex(p2.plus(prevcylinderpoint.times(prevcospitch).plus(zvector.times(prevsinpitch)))));
1921
					vertices.push(new CSG.Vertex(p2.plus(cylinderpoint.times(prevcospitch).plus(zvector.times(prevsinpitch)))));
1922
					if(slice2 < qresolution) {
1923
						vertices.push(new CSG.Vertex(p2.plus(cylinderpoint.times(cospitch).plus(zvector.times(sinpitch)))));
1924
					}
1925
					vertices.push(new CSG.Vertex(p2.plus(prevcylinderpoint.times(cospitch).plus(zvector.times(sinpitch)))));
1926
					vertices.reverse();
1927
					polygons.push(new CSG.Polygon(vertices));
1928
				}
1929
				prevcospitch = cospitch;
1930
				prevsinpitch = sinpitch;
1931
			}
1932
		}
1933
		prevcylinderpoint = cylinderpoint;
1934
	}
1935
	var result = CSG.fromPolygons(polygons);
1936
	var ray = zvector.unit();
1937
	var axisX = xvector.unit();
1938
	result.properties.roundedCylinder = new CSG.Properties();
1939
	result.properties.roundedCylinder.start = new CSG.Connector(p1, ray.negated(), axisX);
1940
	result.properties.roundedCylinder.end = new CSG.Connector(p2, ray, axisX);
1941
	result.properties.roundedCylinder.facepoint = p1.plus(xvector);
1942
	return result;
1943
};
1944

1945
// Construct an axis-aligned solid rounded cuboid.
1946
// Parameters:
1947
//   center: center of cube (default [0,0,0])
1948
//   radius: radius of cube (default [1,1,1]), can be specified as scalar or as 3D vector
1949
//   roundradius: radius of rounded corners (default 0.2), must be a scalar
1950
//   resolution: determines the number of polygons per 360 degree revolution (default 8)
1951
//
1952
// Example code:
1953
//
1954
//     var cube = CSG.roundedCube({
1955
//       center: [0, 0, 0],
1956
//       radius: 1,
1957
//       roundradius: 0.2,
1958
//       resolution: 8,
1959
//     });
1960
CSG.roundedCube = function(options) {
1961
	var center = CSG.parseOptionAs3DVector(options, "center", [0, 0, 0]);
1962
	var cuberadius = CSG.parseOptionAs3DVector(options, "radius", [1, 1, 1]);
1963
	var resolution = CSG.parseOptionAsFloat(options, "resolution", CSG.defaultResolution3D);
1964
	if(resolution < 4) resolution = 4;
1965
	var roundradius = CSG.parseOptionAsFloat(options, "roundradius", 0.2);
1966
	var innercuberadius = cuberadius;
1967
	innercuberadius = innercuberadius.minus(new CSG.Vector3D(roundradius));
1968
	var result = CSG.cube({
1969
		center: center,
1970
		radius: [cuberadius.x, innercuberadius.y, innercuberadius.z]
1971
	});
1972
	result = result.unionSub(CSG.cube({
1973
		center: center,
1974
		radius: [innercuberadius.x, cuberadius.y, innercuberadius.z]
1975
	}), false, false);
1976
	result = result.unionSub(CSG.cube({
1977
		center: center,
1978
		radius: [innercuberadius.x, innercuberadius.y, cuberadius.z]
1979
	}), false, false);
1980
	for(var level = 0; level < 2; level++) {
1981
		var z = innercuberadius.z;
1982
		if(level == 1) z = -z;
1983
		var p1 = new CSG.Vector3D(innercuberadius.x, innercuberadius.y, z).plus(center);
1984
		var p2 = new CSG.Vector3D(innercuberadius.x, -innercuberadius.y, z).plus(center);
1985
		var p3 = new CSG.Vector3D(-innercuberadius.x, -innercuberadius.y, z).plus(center);
1986
		var p4 = new CSG.Vector3D(-innercuberadius.x, innercuberadius.y, z).plus(center);
1987
		var sphere = CSG.sphere({
1988
			center: p1,
1989
			radius: roundradius,
1990
			resolution: resolution
1991
		});
1992
		result = result.unionSub(sphere, false, false);
1993
		sphere = CSG.sphere({
1994
			center: p2,
1995
			radius: roundradius,
1996
			resolution: resolution
1997
		});
1998
		result = result.unionSub(sphere, false, false);
1999
		sphere = CSG.sphere({
2000
			center: p3,
2001
			radius: roundradius,
2002
			resolution: resolution
2003
		});
2004
		result = result.unionSub(sphere, false, false);
2005
		sphere = CSG.sphere({
2006
			center: p4,
2007
			radius: roundradius,
2008
			resolution: resolution
2009
		});
2010
		result = result.unionSub(sphere, false, true);
2011
		var cylinder = CSG.cylinder({
2012
			start: p1,
2013
			end: p2,
2014
			radius: roundradius,
2015
			resolution: resolution
2016
		});
2017
		result = result.unionSub(cylinder, false, false);
2018
		cylinder = CSG.cylinder({
2019
			start: p2,
2020
			end: p3,
2021
			radius: roundradius,
2022
			resolution: resolution
2023
		});
2024
		result = result.unionSub(cylinder, false, false);
2025
		cylinder = CSG.cylinder({
2026
			start: p3,
2027
			end: p4,
2028
			radius: roundradius,
2029
			resolution: resolution
2030
		});
2031
		result = result.unionSub(cylinder, false, false);
2032
		cylinder = CSG.cylinder({
2033
			start: p4,
2034
			end: p1,
2035
			radius: roundradius,
2036
			resolution: resolution
2037
		});
2038
		result = result.unionSub(cylinder, false, false);
2039
		if(level === 0) {
2040
			var d = new CSG.Vector3D(0, 0, -2 * z);
2041
			cylinder = CSG.cylinder({
2042
				start: p1,
2043
				end: p1.plus(d),
2044
				radius: roundradius,
2045
				resolution: resolution
2046
			});
2047
			result = result.unionSub(cylinder);
2048
			cylinder = CSG.cylinder({
2049
				start: p2,
2050
				end: p2.plus(d),
2051
				radius: roundradius,
2052
				resolution: resolution
2053
			});
2054
			result = result.unionSub(cylinder);
2055
			cylinder = CSG.cylinder({
2056
				start: p3,
2057
				end: p3.plus(d),
2058
				radius: roundradius,
2059
				resolution: resolution
2060
			});
2061
			result = result.unionSub(cylinder);
2062
			cylinder = CSG.cylinder({
2063
				start: p4,
2064
				end: p4.plus(d),
2065
				radius: roundradius,
2066
				resolution: resolution
2067
			});
2068
			result = result.unionSub(cylinder, false, true);
2069
		}
2070
	}
2071
	result = result.reTesselated();
2072
	result.properties.roundedCube = new CSG.Properties();
2073
	result.properties.roundedCube.center = new CSG.Vertex(center);
2074
	result.properties.roundedCube.facecenters = [
2075
		new CSG.Connector(new CSG.Vector3D([cuberadius.x, 0, 0]).plus(center), [1, 0, 0], [0, 0, 1]),
2076
		new CSG.Connector(new CSG.Vector3D([-cuberadius.x, 0, 0]).plus(center), [-1, 0, 0], [0, 0, 1]),
2077
		new CSG.Connector(new CSG.Vector3D([0, cuberadius.y, 0]).plus(center), [0, 1, 0], [0, 0, 1]),
2078
		new CSG.Connector(new CSG.Vector3D([0, -cuberadius.y, 0]).plus(center), [0, -1, 0], [0, 0, 1]),
2079
		new CSG.Connector(new CSG.Vector3D([0, 0, cuberadius.z]).plus(center), [0, 0, 1], [1, 0, 0]),
2080
		new CSG.Connector(new CSG.Vector3D([0, 0, -cuberadius.z]).plus(center), [0, 0, -1], [1, 0, 0])];
2081
	return result;
2082
};
2083

2084
CSG.IsFloat = function(n) {
2085
	return(!isNaN(n)) || (n === Infinity) || (n === -Infinity);
2086
};
2087

2088
// solve 2x2 linear equation:
2089
// [ab][x] = [u]
2090
// [cd][y]   [v]
2091
CSG.solve2Linear = function(a, b, c, d, u, v) {
2092
	var det = a * d - b * c;
2093
	var invdet = 1.0 / det;
2094
	var x = u * d - b * v;
2095
	var y = -u * c + a * v;
2096
	x *= invdet;
2097
	y *= invdet;
2098
	return [x, y];
2099
};
2100

2101
// # class Vector3D
2102
// Represents a 3D vector.
2103
//
2104
// Example usage:
2105
//
2106
//     new CSG.Vector3D(1, 2, 3);
2107
//     new CSG.Vector3D([1, 2, 3]);
2108
//     new CSG.Vector3D({ x: 1, y: 2, z: 3 });
2109
//     new CSG.Vector3D(1, 2); // assumes z=0
2110
//     new CSG.Vector3D([1, 2]); // assumes z=0
2111
CSG.Vector3D = function(x, y, z) {
2112
	if(arguments.length == 3) {
2113
		this._x = parseFloat(x);
2114
		this._y = parseFloat(y);
2115
		this._z = parseFloat(z);
2116
	} else if(arguments.length == 2) {
2117
		this._x = parseFloat(x);
2118
		this._y = parseFloat(y);
2119
		this._z = 0;
2120
	} else {
2121
		var ok = true;
2122
		if(arguments.length == 1) {
2123
			if(typeof(x) == "object") {
2124
				if(x instanceof CSG.Vector3D) {
2125
					this._x = x._x;
2126
					this._y = x._y;
2127
					this._z = x._z;
2128
				} else if(x instanceof CSG.Vector2D) {
2129
					this._x = x._x;
2130
					this._y = x._y;
2131
					this._z = 0;
2132
				} else if(x instanceof Array) {
2133
					if((x.length < 2) || (x.length > 3)) {
2134
						ok = false;
2135
					} else {
2136
						this._x = parseFloat(x[0]);
2137
						this._y = parseFloat(x[1]);
2138
						if(x.length == 3) {
2139
							this._z = parseFloat(x[2]);
2140
						} else {
2141
							this._z = 0;
2142
						}
2143
					}
2144
				} else if(('x' in x) && ('y' in x)) {
2145
					this._x = parseFloat(x.x);
2146
					this._y = parseFloat(x.y);
2147
					if('z' in x) {
2148
						this._z = parseFloat(x.z);
2149
					} else {
2150
						this._z = 0;
2151
					}
2152
				} else ok = false;
2153
			} else {
2154
				var v = parseFloat(x);
2155
				this._x = v;
2156
				this._y = v;
2157
				this._z = v;
2158
			}
2159
		} else ok = false;
2160
		if(ok) {
2161
			if((!CSG.IsFloat(this._x)) || (!CSG.IsFloat(this._y)) || (!CSG.IsFloat(this._z))) ok = false;
2162
		}
2163
		if(!ok) {
2164
			throw new Error("wrong arguments");
2165
		}
2166
	}
2167
};
2168

2169
CSG.Vector3D.prototype = {
2170
	get x() {
2171
		return this._x;
2172
	}, get y() {
2173
		return this._y;
2174
	}, get z() {
2175
		return this._z;
2176
	},
2177

2178
	set x(v) {
2179
		throw new Error("Vector3D is immutable");
2180
	}, set y(v) {
2181
		throw new Error("Vector3D is immutable");
2182
	}, set z(v) {
2183
		throw new Error("Vector3D is immutable");
2184
	},
2185

2186
	clone: function() {
2187
		return new CSG.Vector3D(this);
2188
	},
2189

2190
	negated: function() {
2191
		return new CSG.Vector3D(-this._x, -this._y, -this._z);
2192
	},
2193

2194
	abs: function() {
2195
		return new CSG.Vector3D(Math.abs(this._x), Math.abs(this._y), Math.abs(this._z));
2196
	},
2197

2198
	plus: function(a) {
2199
		return new CSG.Vector3D(this._x + a._x, this._y + a._y, this._z + a._z);
2200
	},
2201

2202
	minus: function(a) {
2203
		return new CSG.Vector3D(this._x - a._x, this._y - a._y, this._z - a._z);
2204
	},
2205

2206
	times: function(a) {
2207
		return new CSG.Vector3D(this._x * a, this._y * a, this._z * a);
2208
	},
2209

2210
	dividedBy: function(a) {
2211
		return new CSG.Vector3D(this._x / a, this._y / a, this._z / a);
2212
	},
2213

2214
	dot: function(a) {
2215
		return this._x * a._x + this._y * a._y + this._z * a._z;
2216
	},
2217

2218
	lerp: function(a, t) {
2219
		return this.plus(a.minus(this).times(t));
2220
	},
2221

2222
	lengthSquared: function() {
2223
		return this.dot(this);
2224
	},
2225

2226
	length: function() {
2227
		return Math.sqrt(this.lengthSquared());
2228
	},
2229

2230
	unit: function() {
2231
		return this.dividedBy(this.length());
2232
	},
2233

2234
	cross: function(a) {
2235
		return new CSG.Vector3D(
2236
		this._y * a._z - this._z * a._y, this._z * a._x - this._x * a._z, this._x * a._y - this._y * a._x);
2237
	},
2238

2239
	distanceTo: function(a) {
2240
		return this.minus(a).length();
2241
	},
2242

2243
	distanceToSquared: function(a) {
2244
		return this.minus(a).lengthSquared();
2245
	},
2246

2247
	equals: function(a) {
2248
		return(this._x == a._x) && (this._y == a._y) && (this._z == a._z);
2249
	},
2250

2251
	// Right multiply by a 4x4 matrix (the vector is interpreted as a row vector)
2252
	// Returns a new CSG.Vector3D
2253
	multiply4x4: function(matrix4x4) {
2254
		return matrix4x4.leftMultiply1x3Vector(this);
2255
	},
2256

2257
	transform: function(matrix4x4) {
2258
		return matrix4x4.leftMultiply1x3Vector(this);
2259
	},
2260

2261
	toStlString: function() {
2262
		return this._x + " " + this._y + " " + this._z;
2263
	},
2264

2265
	toAMFString: function() {
2266
		return "<x>" + this._x + "</x><y>" + this._y + "</y><z>" + this._z + "</z>";
2267
	},
2268

2269
	toString: function() {
2270
		return "(" + this._x.toFixed(2) + ", " + this._y.toFixed(2) + ", " + this._z.toFixed(2) + ")";
2271
	},
2272

2273
	// find a vector that is somewhat perpendicular to this one
2274
	randomNonParallelVector: function() {
2275
		var abs = this.abs();
2276
		if((abs._x <= abs._y) && (abs._x <= abs._z)) {
2277
			return new CSG.Vector3D(1, 0, 0);
2278
		} else if((abs._y <= abs._x) && (abs._y <= abs._z)) {
2279
			return new CSG.Vector3D(0, 1, 0);
2280
		} else {
2281
			return new CSG.Vector3D(0, 0, 1);
2282
		}
2283
	},
2284

2285
	min: function(p) {
2286
		return new CSG.Vector3D(
2287
		Math.min(this._x, p._x), Math.min(this._y, p._y), Math.min(this._z, p._z));
2288
	},
2289

2290
	max: function(p) {
2291
		return new CSG.Vector3D(
2292
		Math.max(this._x, p._x), Math.max(this._y, p._y), Math.max(this._z, p._z));
2293
	}
2294
};
2295

2296
// # class Vertex
2297
// Represents a vertex of a polygon. Use your own vertex class instead of this
2298
// one to provide additional features like texture coordinates and vertex
2299
// colors. Custom vertex classes need to provide a `pos` property
2300
// `flipped()`, and `interpolate()` methods that behave analogous to the ones
2301
// defined by `CSG.Vertex`.
2302
CSG.Vertex = function(pos) {
2303
	this.pos = pos;
2304
};
2305

2306
// create from an untyped object with identical property names:
2307
CSG.Vertex.fromObject = function(obj) {
2308
	var pos = new CSG.Vector3D(obj.pos);
2309
	return new CSG.Vertex(pos);
2310
};
2311

2312
CSG.Vertex.prototype = {
2313
	// Return a vertex with all orientation-specific data (e.g. vertex normal) flipped. Called when the
2314
	// orientation of a polygon is flipped.
2315
	flipped: function() {
2316
		return this;
2317
	},
2318

2319
	getTag: function() {
2320
		var result = this.tag;
2321
		if(!result) {
2322
			result = CSG.getTag();
2323
			this.tag = result;
2324
		}
2325
		return result;
2326
	},
2327

2328
	// Create a new vertex between this vertex and `other` by linearly
2329
	// interpolating all properties using a parameter of `t`. Subclasses should
2330
	// override this to interpolate additional properties.
2331
	interpolate: function(other, t) {
2332
		var newpos = this.pos.lerp(other.pos, t);
2333
		return new CSG.Vertex(newpos);
2334
	},
2335

2336
	// Affine transformation of vertex. Returns a new CSG.Vertex
2337
	transform: function(matrix4x4) {
2338
		var newpos = this.pos.multiply4x4(matrix4x4);
2339
		return new CSG.Vertex(newpos);
2340
	},
2341

2342
	toStlString: function() {
2343
		return "vertex " + this.pos.toStlString() + "\n";
2344
	},
2345

2346
	toAMFString: function() {
2347
		return "<vertex><coordinates>" + this.pos.toAMFString() + "</coordinates></vertex>\n";
2348
	},
2349

2350
	toString: function() {
2351
		return this.pos.toString();
2352
	}
2353
};
2354

2355
// # class Plane
2356
// Represents a plane in 3D space.
2357
CSG.Plane = function(normal, w) {
2358
	this.normal = normal;
2359
	this.w = w;
2360
};
2361

2362
// create from an untyped object with identical property names:
2363
CSG.Plane.fromObject = function(obj) {
2364
	var normal = new CSG.Vector3D(obj.normal);
2365
	var w = parseFloat(obj.w);
2366
	return new CSG.Plane(normal, w);
2367
};
2368

2369
// `CSG.Plane.EPSILON` is the tolerance used by `splitPolygon()` to decide if a
2370
// point is on the plane.
2371
CSG.Plane.EPSILON = 1e-5;
2372

2373
CSG.Plane.fromVector3Ds = function(a, b, c) {
2374
	var n = b.minus(a).cross(c.minus(a)).unit();
2375
	return new CSG.Plane(n, n.dot(a));
2376
};
2377

2378
// like fromVector3Ds, but allow the vectors to be on one point or one line
2379
// in such a case a random plane through the given points is constructed
2380
CSG.Plane.anyPlaneFromVector3Ds = function(a, b, c) {
2381
	var v1 = b.minus(a);
2382
	var v2 = c.minus(a);
2383
	if(v1.length() < 1e-5) {
2384
		v1 = v2.randomNonParallelVector();
2385
	}
2386
	if(v2.length() < 1e-5) {
2387
		v2 = v1.randomNonParallelVector();
2388
	}
2389
	var normal = v1.cross(v2);
2390
	if(normal.length() < 1e-5) {
2391
		// this would mean that v1 == v2.negated()
2392
		v2 = v1.randomNonParallelVector();
2393
		normal = v1.cross(v2);
2394
	}
2395
	normal = normal.unit();
2396
	return new CSG.Plane(normal, normal.dot(a));
2397
};
2398

2399
CSG.Plane.fromPoints = function(a, b, c) {
2400
	a = new CSG.Vector3D(a);
2401
	b = new CSG.Vector3D(b);
2402
	c = new CSG.Vector3D(c);
2403
	return CSG.Plane.fromVector3Ds(a, b, c);
2404
};
2405

2406
CSG.Plane.fromNormalAndPoint = function(normal, point) {
2407
	normal = new CSG.Vector3D(normal);
2408
	point = new CSG.Vector3D(point);
2409
	normal = normal.unit();
2410
	var w = point.dot(normal);
2411
	return new CSG.Plane(normal, w);
2412
};
2413

2414
CSG.Plane.prototype = {
2415
	flipped: function() {
2416
		return new CSG.Plane(this.normal.negated(), -this.w);
2417
	},
2418

2419
	getTag: function() {
2420
		var result = this.tag;
2421
		if(!result) {
2422
			result = CSG.getTag();
2423
			this.tag = result;
2424
		}
2425
		return result;
2426
	},
2427

2428
	equals: function(n) {
2429
		return this.normal.equals(n.normal) && this.w == n.w;
2430
	},
2431

2432
	transform: function(matrix4x4) {
2433
		var ismirror = matrix4x4.isMirroring();
2434
		// get two vectors in the plane:
2435
		var r = this.normal.randomNonParallelVector();
2436
		var u = this.normal.cross(r);
2437
		var v = this.normal.cross(u);
2438
		// get 3 points in the plane:
2439
		var point1 = this.normal.times(this.w);
2440
		var point2 = point1.plus(u);
2441
		var point3 = point1.plus(v);
2442
		// transform the points:
2443
		point1 = point1.multiply4x4(matrix4x4);
2444
		point2 = point2.multiply4x4(matrix4x4);
2445
		point3 = point3.multiply4x4(matrix4x4);
2446
		// and create a new plane from the transformed points:
2447
		var newplane = CSG.Plane.fromVector3Ds(point1, point2, point3);
2448
		if(ismirror) {
2449
			// the transform is mirroring
2450
			// We should mirror the plane:
2451
			newplane = newplane.flipped();
2452
		}
2453
		return newplane;
2454
	},
2455

2456
	// Returns object:
2457
	// .type:
2458
	//   0: coplanar-front
2459
	//   1: coplanar-back
2460
	//   2: front
2461
	//   3: back
2462
	//   4: spanning
2463
	// In case the polygon is spanning, returns:
2464
	// .front: a CSG.Polygon of the front part
2465
	// .back: a CSG.Polygon of the back part
2466
	splitPolygon: function(polygon) {
2467
		var result = {
2468
			type: null,
2469
			front: null,
2470
			back: null
2471
		};
2472
		// cache in local vars (speedup):
2473
		var planenormal = this.normal;
2474
		var vertices = polygon.vertices;
2475
		var numvertices = vertices.length;
2476
		if(polygon.plane.equals(this)) {
2477
			result.type = 0;
2478
		} else {
2479
			var EPS = CSG.Plane.EPSILON;
2480
			var thisw = this.w;
2481
			var hasfront = false;
2482
			var hasback = false;
2483
			var vertexIsBack = [];
2484
			var MINEPS = -EPS;
2485
			for(var i = 0; i < numvertices; i++) {
2486
				var t = planenormal.dot(vertices[i].pos) - thisw;
2487
				var isback = (t < 0);
2488
				vertexIsBack.push(isback);
2489
				if(t > EPS) hasfront = true;
2490
				if(t < MINEPS) hasback = true;
2491
			}
2492
			if((!hasfront) && (!hasback)) {
2493
				// all points coplanar
2494
				var t = planenormal.dot(polygon.plane.normal);
2495
				result.type = (t >= 0) ? 0 : 1;
2496
			} else if(!hasback) {
2497
				result.type = 2;
2498
			} else if(!hasfront) {
2499
				result.type = 3;
2500
			} else {
2501
				// spanning
2502
				result.type = 4;
2503
				var frontvertices = [],
2504
					backvertices = [];
2505
				var isback = vertexIsBack[0];
2506
				for(var vertexindex = 0; vertexindex < numvertices; vertexindex++) {
2507
					var vertex = vertices[vertexindex];
2508
					var nextvertexindex = vertexindex + 1;
2509
					if(nextvertexindex >= numvertices) nextvertexindex = 0;
2510
					var nextisback = vertexIsBack[nextvertexindex];
2511
					if(isback == nextisback) {
2512
						// line segment is on one side of the plane:
2513
						if(isback) {
2514
							backvertices.push(vertex);
2515
						} else {
2516
							frontvertices.push(vertex);
2517
						}
2518
					} else {
2519
						// line segment intersects plane:
2520
						var point = vertex.pos;
2521
						var nextpoint = vertices[nextvertexindex].pos;
2522
						var intersectionpoint = this.splitLineBetweenPoints(point, nextpoint);
2523
						var intersectionvertex = new CSG.Vertex(intersectionpoint);
2524
						if(isback) {
2525
							backvertices.push(vertex);
2526
							backvertices.push(intersectionvertex);
2527
							frontvertices.push(intersectionvertex);
2528
						} else {
2529
							frontvertices.push(vertex);
2530
							frontvertices.push(intersectionvertex);
2531
							backvertices.push(intersectionvertex);
2532
						}
2533
					}
2534
					isback = nextisback;
2535
				} // for vertexindex
2536
				// remove duplicate vertices:
2537
				var EPS_SQUARED = CSG.Plane.EPSILON * CSG.Plane.EPSILON;
2538
				if(backvertices.length >= 3) {
2539
					var prevvertex = backvertices[backvertices.length - 1];
2540
					for(var vertexindex = 0; vertexindex < backvertices.length; vertexindex++) {
2541
						var vertex = backvertices[vertexindex];
2542
						if(vertex.pos.distanceToSquared(prevvertex.pos) < EPS_SQUARED) {
2543
							backvertices.splice(vertexindex, 1);
2544
							vertexindex--;
2545
						}
2546
						prevvertex = vertex;
2547
					}
2548
				}
2549
				if(frontvertices.length >= 3) {
2550
					var prevvertex = frontvertices[frontvertices.length - 1];
2551
					for(var vertexindex = 0; vertexindex < frontvertices.length; vertexindex++) {
2552
						var vertex = frontvertices[vertexindex];
2553
						if(vertex.pos.distanceToSquared(prevvertex.pos) < EPS_SQUARED) {
2554
							frontvertices.splice(vertexindex, 1);
2555
							vertexindex--;
2556
						}
2557
						prevvertex = vertex;
2558
					}
2559
				}
2560
				if(frontvertices.length >= 3) {
2561
					result.front = new CSG.Polygon(frontvertices, polygon.shared, polygon.plane);
2562
				}
2563
				if(backvertices.length >= 3) {
2564
					result.back = new CSG.Polygon(backvertices, polygon.shared, polygon.plane);
2565
				}
2566
			}
2567
		}
2568
		return result;
2569
	},
2570

2571
	// robust splitting of a line by a plane
2572
	// will work even if the line is parallel to the plane
2573
	splitLineBetweenPoints: function(p1, p2) {
2574
		var direction = p2.minus(p1);
2575
		var labda = (this.w - this.normal.dot(p1)) / this.normal.dot(direction);
2576
		if(isNaN(labda)) labda = 0;
2577
		if(labda > 1) labda = 1;
2578
		if(labda < 0) labda = 0;
2579
		var result = p1.plus(direction.times(labda));
2580
		return result;
2581
	},
2582

2583
	// returns CSG.Vector3D
2584
	intersectWithLine: function(line3d) {
2585
		return line3d.intersectWithPlane(this);
2586
	},
2587

2588
	// intersection of two planes
2589
	intersectWithPlane: function(plane) {
2590
		return CSG.Line3D.fromPlanes(this, plane);
2591
	},
2592

2593
	signedDistanceToPoint: function(point) {
2594
		var t = this.normal.dot(point) - this.w;
2595
		return t;
2596
	},
2597

2598
	toString: function() {
2599
		return "[normal: " + this.normal.toString() + ", w: " + this.w + "]";
2600
	},
2601

2602
	mirrorPoint: function(point3d) {
2603
		var distance = this.signedDistanceToPoint(point3d);
2604
		var mirrored = point3d.minus(this.normal.times(distance * 2.0));
2605
		return mirrored;
2606
	}
2607
};
2608

2609

2610
// # class Polygon
2611
// Represents a convex polygon. The vertices used to initialize a polygon must
2612
// be coplanar and form a convex loop. They do not have to be `CSG.Vertex`
2613
// instances but they must behave similarly (duck typing can be used for
2614
// customization).
2615
//
2616
// Each convex polygon has a `shared` property, which is shared between all
2617
// polygons that are clones of each other or were split from the same polygon.
2618
// This can be used to define per-polygon properties (such as surface color).
2619
//
2620
// The plane of the polygon is calculated from the vertex coordinates
2621
// To avoid unnecessary recalculation, the plane can alternatively be
2622
// passed as the third argument
2623
CSG.Polygon = function(vertices, shared, plane) {
2624
	this.vertices = vertices;
2625
	if(!shared) shared = CSG.Polygon.defaultShared;
2626
	this.shared = shared;
2627
	//var numvertices = vertices.length;
2628

2629
	if(arguments.length >= 3) {
2630
		this.plane = plane;
2631
	} else {
2632
		this.plane = CSG.Plane.fromVector3Ds(vertices[0].pos, vertices[1].pos, vertices[2].pos);
2633
	}
2634

2635
	if(_CSGDEBUG) {
2636
		this.checkIfConvex();
2637
	}
2638
};
2639

2640
// create from an untyped object with identical property names:
2641
CSG.Polygon.fromObject = function(obj) {
2642
	var vertices = obj.vertices.map(function(v) {
2643
		return CSG.Vertex.fromObject(v);
2644
	});
2645
	var shared = CSG.Polygon.Shared.fromObject(obj.shared);
2646
	var plane = CSG.Plane.fromObject(obj.plane);
2647
	return new CSG.Polygon(vertices, shared, plane);
2648
};
2649

2650
CSG.Polygon.prototype = {
2651
	// check whether the polygon is convex (it should be, otherwise we will get unexpected results)
2652
	checkIfConvex: function() {
2653
		if(!CSG.Polygon.verticesConvex(this.vertices, this.plane.normal)) {
2654
			CSG.Polygon.verticesConvex(this.vertices, this.plane.normal);
2655
			throw new Error("Not convex!");
2656
		}
2657
	},
2658

2659
	/**
2660
	 * @param {Array} color [red, green, blue, alpha] color values are float numbers 0..1
2661
	 * @return {CSG.Polygon} The current polygon
2662
	 */
2663
	setColor: function(red, green, blue, alpha) {
2664
		var color = red instanceof Array ? red : [red||0, green||0, blue||0, isNaN(alpha) ? 1. : alpha];
2665
		this.shared = new CSG.Polygon.Shared(color);
2666
		return this;
2667
	},
2668

2669
	// Extrude a polygon into the direction offsetvector
2670
	// Returns a CSG object
2671
	extrude: function(offsetvector) {
2672
		var newpolygons = [];
2673

2674
		var polygon1 = this;
2675
		var direction = polygon1.plane.normal.dot(offsetvector);
2676
		if(direction > 0) {
2677
			polygon1 = polygon1.flipped();
2678
		}
2679
		newpolygons.push(polygon1);
2680
		var polygon2 = polygon1.translate(offsetvector);
2681
		var numvertices = this.vertices.length;
2682
		for(var i = 0; i < numvertices; i++) {
2683
			var sidefacepoints = [];
2684
			var nexti = (i < (numvertices - 1)) ? i + 1 : 0;
2685
			sidefacepoints.push(polygon1.vertices[i].pos);
2686
			sidefacepoints.push(polygon2.vertices[i].pos);
2687
			sidefacepoints.push(polygon2.vertices[nexti].pos);
2688
			sidefacepoints.push(polygon1.vertices[nexti].pos);
2689
			var sidefacepolygon = CSG.Polygon.createFromPoints(sidefacepoints, this.shared);
2690
			newpolygons.push(sidefacepolygon);
2691
		}
2692
		polygon2 = polygon2.flipped();
2693
		newpolygons.push(polygon2);
2694
		return CSG.fromPolygons(newpolygons);
2695
	},
2696

2697
	translate: function(offset) {
2698
		return this.transform(CSG.Matrix4x4.translation(offset));
2699
	},
2700

2701
	// returns an array with a CSG.Vector3D (center point) and a radius
2702
	boundingSphere: function() {
2703
		if(!this.cachedBoundingSphere) {
2704
			var box = this.boundingBox();
2705
			var middle = box[0].plus(box[1]).times(0.5);
2706
			var radius3 = box[1].minus(middle);
2707
			var radius = radius3.length();
2708
			this.cachedBoundingSphere = [middle, radius];
2709
		}
2710
		return this.cachedBoundingSphere;
2711
	},
2712

2713
	// returns an array of two CSG.Vector3Ds (minimum coordinates and maximum coordinates)
2714
	boundingBox: function() {
2715
		if(!this.cachedBoundingBox) {
2716
			var minpoint, maxpoint;
2717
			var vertices = this.vertices;
2718
			var numvertices = vertices.length;
2719
			if(numvertices === 0) {
2720
				minpoint = new CSG.Vector3D(0, 0, 0);
2721
			} else {
2722
				minpoint = vertices[0].pos;
2723
			}
2724
			maxpoint = minpoint;
2725
			for(var i = 1; i < numvertices; i++) {
2726
				var point = vertices[i].pos;
2727
				minpoint = minpoint.min(point);
2728
				maxpoint = maxpoint.max(point);
2729
			}
2730
			this.cachedBoundingBox = [minpoint, maxpoint];
2731
		}
2732
		return this.cachedBoundingBox;
2733
	},
2734

2735
	flipped: function() {
2736
		var newvertices = this.vertices.map(function(v) {
2737
			return v.flipped();
2738
		});
2739
		newvertices.reverse();
2740
		var newplane = this.plane.flipped();
2741
		return new CSG.Polygon(newvertices, this.shared, newplane);
2742
	},
2743

2744
	// Affine transformation of polygon. Returns a new CSG.Polygon
2745
	transform: function(matrix4x4) {
2746
		var newvertices = this.vertices.map(function(v) {
2747
			return v.transform(matrix4x4);
2748
		});
2749
		var newplane = this.plane.transform(matrix4x4);
2750
		var scalefactor = matrix4x4.elements[0] * matrix4x4.elements[5] * matrix4x4.elements[10];
2751
		if(scalefactor < 0) {
2752
			// the transformation includes mirroring. We need to reverse the vertex order
2753
			// in order to preserve the inside/outside orientation:
2754
			newvertices.reverse();
2755
		}
2756
		return new CSG.Polygon(newvertices, this.shared, newplane);
2757
	},
2758

2759
	toStlString: function() {
2760
		var result = "";
2761
		if(this.vertices.length >= 3) // should be!
2762
		{
2763
			// STL requires triangular polygons. If our polygon has more vertices, create
2764
			// multiple triangles:
2765
			var firstVertexStl = this.vertices[0].toStlString();
2766
			for(var i = 0; i < this.vertices.length - 2; i++) {
2767
				result += "facet normal " + this.plane.normal.toStlString() + "\nouter loop\n";
2768
				result += firstVertexStl;
2769
				result += this.vertices[i + 1].toStlString();
2770
				result += this.vertices[i + 2].toStlString();
2771
				result += "endloop\nendfacet\n";
2772
			}
2773
		}
2774
		return result;
2775
	},
2776

2777
	toString: function() {
2778
		var result = "Polygon plane: " + this.plane.toString() + "\n";
2779
		this.vertices.map(function(vertex) {
2780
			result += "  " + vertex.toString() + "\n";
2781
		});
2782
		return result;
2783
	},
2784

2785
	// project the 3D polygon onto a plane
2786
	projectToOrthoNormalBasis: function(orthobasis) {
2787
		var points2d = this.vertices.map(function(vertex) {
2788
			return orthobasis.to2D(vertex.pos);
2789
		});
2790
		var result = CAG.fromPointsNoCheck(points2d);
2791
		var area = result.area();
2792
		if(Math.abs(area) < 1e-5) {
2793
			// the polygon was perpendicular to the orthnormal plane. The resulting 2D polygon would be degenerate
2794
			// return an empty area instead:
2795
			result = new CAG();
2796
		} else if(area < 0) {
2797
			result = result.flipped();
2798
		}
2799
		return result;
2800
	},
2801

2802
	/**
2803
	 * Creates solid from slices (CSG.Polygon) by generating walls
2804
	 * @param {Object} options Solid generating options
2805
	 *	- numslices {Number} Number of slices to be generated
2806
	 *	- callback(t, slice) {Function} Callback function generating slices.
2807
	 *			arguments: t = [0..1], slice = [0..numslices - 1]
2808
	 *			return: CSG.Polygon or null to skip
2809
	 *	- loop {Boolean} no flats, only walls, it's used to generate solids like a tor
2810
	 *
2811
	 *	by Eduard Bespalov AKA tedbeer (2013)
2812
	 */
2813
	solidFromSlices: function(options) {
2814
		var polygons = [],
2815
			csg = null,
2816
			prev = null,
2817
			bottom = null,
2818
			top = null,
2819
			numSlices = 2,
2820
			bLoop = false,
2821
			fnCallback,
2822
			flipped = null;
2823

2824
		if (options) {
2825
			bLoop = Boolean(options['loop']);
2826

2827
			if (options.numslices)
2828
				numSlices = options.numslices;
2829

2830
			if (options.callback)
2831
				fnCallback = options.callback;
2832
		}
2833
		if (!fnCallback) {
2834
			var square = new CSG.Polygon.createFromPoints([
2835
						[0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0]
2836
					]);
2837
			fnCallback = function(t, slice) {
2838
				return t == 0 || t == 1 ? square.translate([0,0,t]) : null;
2839
			}
2840
		}
2841
		for(var i = 0, iMax = numSlices - 1; i <= iMax; i++) {
2842
			csg = fnCallback.call(this, i / iMax, i);
2843
			if (csg) {
2844
				if (!(csg instanceof CSG.Polygon)) {
2845
					throw new Error("CSG.Polygon.solidFromSlices callback error: CSG.Polygon expected");
2846
				}
2847
				csg.checkIfConvex();
2848

2849
				if (prev) {//generate walls
2850
					if (flipped === null) {//not generated yet
2851
						flipped = prev.plane.signedDistanceToPoint(csg.vertices[0].pos) < 0;
2852
					}
2853
					this._addWalls(polygons, prev, csg, flipped);
2854

2855
				} else {//the first - will be a bottom
2856
					bottom = csg;
2857
				}
2858
				prev = csg;
2859
			} //callback can return null to skip that slice
2860
		}
2861
		top = csg;
2862

2863
		if (bLoop) {
2864
			var bSameTopBottom = bottom.vertices.length == top.vertices.length &&
2865
								bottom.vertices.every(function(v, index){
2866
									return v.pos.equals(top.vertices[index].pos)
2867
								});
2868
			//if top and bottom are not the same -
2869
			//generate walls between them
2870
			if (!bSameTopBottom) {
2871
				this._addWalls(polygons, top, bottom, flipped);
2872
			} //else - already generated
2873
		} else {
2874
			//save top and bottom
2875
			//TODO: flip if necessary
2876
			polygons.unshift(flipped ? bottom : bottom.flipped());
2877
			polygons.push(flipped ? top.flipped() : top);
2878
		}
2879
		return CSG.fromPolygons(polygons);
2880
	},
2881
	/**
2882
	 *
2883
	 * @param walls Array of wall polygons
2884
	 * @param bottom Bottom polygon
2885
	 * @param top Top polygon
2886
	 */
2887
	_addWalls: function(walls, bottom, top, bFlipped) {
2888
		var bottomPoints = bottom.vertices.slice(0),//make a copy
2889
			topPoints = top.vertices.slice(0),//make a copy
2890
			color = top.shared || null;
2891

2892
		//check if bottom perimeter is closed
2893
		if (!bottomPoints[0].pos.equals(bottomPoints[bottomPoints.length - 1].pos)) {
2894
			bottomPoints.push(bottomPoints[0]);
2895
		}
2896

2897
		//check if top perimeter is closed
2898
		if (!topPoints[0].pos.equals(topPoints[topPoints.length - 1].pos)) {
2899
			topPoints.push(topPoints[0]);
2900
		}
2901
		if (bFlipped) {
2902
			bottomPoints = bottomPoints.reverse();
2903
			topPoints = topPoints.reverse();
2904
		}
2905

2906
		var iTopLen = topPoints.length - 1,
2907
			iBotLen = bottomPoints.length - 1,
2908
			iExtra = iTopLen - iBotLen, //how many extra triangles we need
2909
			bMoreTops = iExtra > 0,
2910
			bMoreBottoms = iExtra < 0;
2911

2912
		var aMin = []; //indexes to start extra triangles (polygon with minimal square)
2913
		//init - we need exactly /iExtra/ small triangles
2914
		for (var i = Math.abs(iExtra); i > 0; i--) {
2915
			aMin.push({len: Infinity, index: -1});
2916
		}
2917

2918
		var len;
2919
		if (bMoreBottoms) {
2920
			for (var i = 0; i < iBotLen; i++) {
2921
				len = bottomPoints[i].pos.distanceToSquared(bottomPoints[i+1].pos);
2922
				//find the element to replace
2923
				for (var j = aMin.length - 1; j >= 0; j--) {
2924
					if (aMin[j].len > len) {
2925
						aMin[j].len = len;
2926
						aMin.index = j;
2927
						break;
2928
					}
2929
				}//for
2930
			}
2931
		} else if (bMoreTops) {
2932
			for (var i = 0; i < iTopLen; i++) {
2933
				len = topPoints[i].pos.distanceToSquared(topPoints[i+1].pos);
2934
				//find the element to replace
2935
				for (var j = aMin.length - 1; j >= 0; j--) {
2936
					if (aMin[j].len > len) {
2937
						aMin[j].len = len;
2938
						aMin.index = j;
2939
						break;
2940
					}
2941
				}//for
2942
			}
2943
		}//if
2944
		//sort by index
2945
		aMin.sort(fnSortByIndex);
2946
		var getTriangle = function addWallsPutTriangle (pointA, pointB, pointC, color) {
2947
			return new CSG.Polygon([pointA, pointB, pointC], color);
2948
			//return bFlipped ? triangle.flipped() : triangle;
2949
		};
2950

2951
		var bpoint = bottomPoints[0],
2952
			tpoint = topPoints[0],
2953
			secondPoint,
2954
			nBotFacet, nTopFacet; //length of triangle facet side
2955
		for (var iB = 0, iT = 0, iMax = iTopLen + iBotLen; iB + iT < iMax;) {
2956
			if (aMin.length) {
2957
				if (bMoreTops && iT == aMin[0].index) {//one vertex is on the bottom, 2 - on the top
2958
					secondPoint = topPoints[++iT];
2959
					//console.log('<<< extra top: ' + secondPoint + ', ' + tpoint + ', bottom: ' + bpoint);
2960
					walls.push(getTriangle(
2961
						secondPoint, tpoint, bpoint, color
2962
					));
2963
					tpoint = secondPoint;
2964
					aMin.shift();
2965
					continue;
2966
				} else if (bMoreBottoms && iB == aMin[0].index) {
2967
					secondPoint = bottomPoints[++iB];
2968
					walls.push(getTriangle(
2969
						tpoint, bpoint, secondPoint, color
2970
					));
2971
					bpoint = secondPoint;
2972
					aMin.shift();
2973
					continue;
2974
				}
2975
			}
2976
			//choose the shortest path
2977
			if (iB < iBotLen) { //one vertex is on the top, 2 - on the bottom
2978
				nBotFacet = tpoint.pos.distanceToSquared(bottomPoints[iB+1].pos);
2979
			} else {
2980
				nBotFacet = Infinity;
2981
			}
2982
			if (iT < iTopLen) { //one vertex is on the bottom, 2 - on the top
2983
				nTopFacet = bpoint.pos.distanceToSquared(topPoints[iT+1].pos);
2984
			} else {
2985
				nTopFacet = Infinity;
2986
			}
2987
			if (nBotFacet <= nTopFacet) {
2988
				secondPoint = bottomPoints[++iB];
2989
				walls.push(getTriangle(
2990
					tpoint, bpoint, secondPoint, color
2991
				));
2992
				bpoint = secondPoint;
2993
			} else if (iT < iTopLen) { //nTopFacet < Infinity
2994
				secondPoint = topPoints[++iT];
2995
				//console.log('<<< top: ' + secondPoint + ', ' + tpoint + ', bottom: ' + bpoint);
2996
				walls.push(getTriangle(
2997
					secondPoint, tpoint, bpoint, color
2998
				));
2999
				tpoint = secondPoint;
3000
			};
3001
		}
3002
		return walls;
3003
	}
3004
};
3005

3006
CSG.Polygon.verticesConvex = function(vertices, planenormal) {
3007
	var numvertices = vertices.length;
3008
	if(numvertices > 2) {
3009
		var prevprevpos = vertices[numvertices - 2].pos;
3010
		var prevpos = vertices[numvertices - 1].pos;
3011
		for(var i = 0; i < numvertices; i++) {
3012
			var pos = vertices[i].pos;
3013
			if(!CSG.Polygon.isConvexPoint(prevprevpos, prevpos, pos, planenormal)) {
3014
				return false;
3015
			}
3016
			prevprevpos = prevpos;
3017
			prevpos = pos;
3018
		}
3019
	}
3020
	return true;
3021
};
3022

3023
// Create a polygon from the given points
3024
CSG.Polygon.createFromPoints = function(points, shared, plane) {
3025
	var normal;
3026
	if(arguments.length < 3) {
3027
		// initially set a dummy vertex normal:
3028
		normal = new CSG.Vector3D(0, 0, 0);
3029
	} else {
3030
		normal = plane.normal;
3031
	}
3032
	var vertices = [];
3033
	points.map(function(p) {
3034
		var vec = new CSG.Vector3D(p);
3035
		var vertex = new CSG.Vertex(vec);
3036
		vertices.push(vertex);
3037
	});
3038
	var polygon;
3039
	if(arguments.length < 3) {
3040
		polygon = new CSG.Polygon(vertices, shared);
3041
	} else {
3042
		polygon = new CSG.Polygon(vertices, shared, plane);
3043
	}
3044
	return polygon;
3045
};
3046

3047
// calculate whether three points form a convex corner
3048
//  prevpoint, point, nextpoint: the 3 coordinates (CSG.Vector3D instances)
3049
//  normal: the normal vector of the plane
3050
CSG.Polygon.isConvexPoint = function(prevpoint, point, nextpoint, normal) {
3051
	var crossproduct = point.minus(prevpoint).cross(nextpoint.minus(point));
3052
	var crossdotnormal = crossproduct.dot(normal);
3053
	return(crossdotnormal >= 0);
3054
};
3055

3056
CSG.Polygon.isStrictlyConvexPoint = function(prevpoint, point, nextpoint, normal) {
3057
	var crossproduct = point.minus(prevpoint).cross(nextpoint.minus(point));
3058
	var crossdotnormal = crossproduct.dot(normal);
3059
	return(crossdotnormal >= 1e-5);
3060
};
3061

3062
// # class CSG.Polygon.Shared
3063
// Holds the shared properties for each polygon (currently only color)
3064
CSG.Polygon.Shared = function(color) {
3065
	this.color = color;
3066
};
3067

3068
CSG.Polygon.Shared.fromObject = function(obj) {
3069
	return new CSG.Polygon.Shared(obj.color);
3070
};
3071

3072
CSG.Polygon.Shared.prototype = {
3073
	getTag: function() {
3074
		var result = this.tag;
3075
		if(!result) {
3076
			result = CSG.getTag();
3077
			this.tag = result;
3078
		}
3079
		return result;
3080
	},
3081
	// get a string uniquely identifying this object
3082
	getHash: function() {
3083
		if(!this.color) return "null";
3084
		return "" + this.color[0] + "/" + this.color[1] + "/" + this.color[2] + "/" + this.color[3];
3085
	}
3086
};
3087

3088
CSG.Polygon.defaultShared = new CSG.Polygon.Shared(null);
3089

3090
// # class PolygonTreeNode
3091
// This class manages hierarchical splits of polygons
3092
// At the top is a root node which doesn hold a polygon, only child PolygonTreeNodes
3093
// Below that are zero or more 'top' nodes; each holds a polygon. The polygons can be in different planes
3094
// splitByPlane() splits a node by a plane. If the plane intersects the polygon, two new child nodes
3095
// are created holding the splitted polygon.
3096
// getPolygons() retrieves the polygon from the tree. If for PolygonTreeNode the polygon is split but
3097
// the two split parts (child nodes) are still intact, then the unsplit polygon is returned.
3098
// This ensures that we can safely split a polygon into many fragments. If the fragments are untouched,
3099
//  getPolygons() will return the original unsplit polygon instead of the fragments.
3100
// remove() removes a polygon from the tree. Once a polygon is removed, the parent polygons are invalidated
3101
// since they are no longer intact.
3102
// constructor creates the root node:
3103
CSG.PolygonTreeNode = function() {
3104
	this.parent = null;
3105
	this.children = [];
3106
	this.polygon = null;
3107
	this.removed = false;
3108
};
3109

3110
CSG.PolygonTreeNode.prototype = {
3111
	// fill the tree with polygons. Should be called on the root node only; child nodes must
3112
	// always be a derivate (split) of the parent node.
3113
	addPolygons: function(polygons) {
3114
		if(!this.isRootNode())
3115
			// new polygons can only be added to root node; children can only be splitted polygons
3116
			throw new Error("Assertion failed");
3117
		var _this = this;
3118
		polygons.map(function(polygon) {
3119
			_this.addChild(polygon);
3120
		});
3121
	},
3122

3123
	// remove a node
3124
	// - the siblings become toplevel nodes
3125
	// - the parent is removed recursively
3126
	remove: function() {
3127
		if(!this.removed) {
3128
			this.removed = true;
3129

3130
			if(_CSGDEBUG) {
3131
				if(this.isRootNode()) throw new Error("Assertion failed"); // can't remove root node
3132
				if(this.children.length) throw new Error("Assertion failed"); // we shouldn't remove nodes with children
3133
			}
3134

3135
			// remove ourselves from the parent's children list:
3136
			var parentschildren = this.parent.children;
3137
			var i = parentschildren.indexOf(this);
3138
			if(i < 0) throw new Error("Assertion failed");
3139
			parentschildren.splice(i, 1);
3140

3141
			// invalidate the parent's polygon, and of all parents above it:
3142
			this.parent.recursivelyInvalidatePolygon();
3143
		}
3144
	},
3145

3146
	isRemoved: function() {
3147
		return this.removed;
3148
	},
3149

3150
	isRootNode: function() {
3151
		return !this.parent;
3152
	},
3153

3154
	// invert all polygons in the tree. Call on the root node
3155
	invert: function() {
3156
		if(!this.isRootNode()) throw new Error("Assertion failed"); // can only call this on the root node
3157
		this.invertSub();
3158
	},
3159

3160
	getPolygon: function() {
3161
		if(!this.polygon) throw new Error("Assertion failed"); // doesn't have a polygon, which means that it has been broken down
3162
		return this.polygon;
3163
	},
3164

3165
	getPolygons: function(result) {
3166
		if(this.polygon) {
3167
			// the polygon hasn't been broken yet. We can ignore the children and return our polygon:
3168
			result.push(this.polygon);
3169
		} else {
3170
			// our polygon has been split up and broken, so gather all subpolygons from the children:
3171
			var childpolygons = [];
3172
			this.children.map(function(child) {
3173
				child.getPolygons(childpolygons);
3174
			});
3175
			childpolygons.map(function(p) {
3176
				result.push(p);
3177
			});
3178
		}
3179
	},
3180

3181
	// split the node by a plane; add the resulting nodes to the frontnodes and backnodes array
3182
	// If the plane doesn't intersect the polygon, the 'this' object is added to one of the arrays
3183
	// If the plane does intersect the polygon, two new child nodes are created for the front and back fragments,
3184
	//  and added to both arrays.
3185
	splitByPlane: function(plane, coplanarfrontnodes, coplanarbacknodes, frontnodes, backnodes) {
3186
		var children = this.children;
3187
		var numchildren = children.length;
3188
		if(numchildren > 0) {
3189
			// if we have children, split the children
3190
			for(var i = 0; i < numchildren; i++) {
3191
				children[i].splitByPlane(plane, coplanarfrontnodes, coplanarbacknodes, frontnodes, backnodes);
3192
			}
3193
		} else {
3194
			// no children. Split the polygon:
3195
			var polygon = this.polygon;
3196
			if(polygon) {
3197
				var bound = polygon.boundingSphere();
3198
				var sphereradius = bound[1] + 1e-4;
3199
				var planenormal = plane.normal;
3200
				var spherecenter = bound[0];
3201
				var d = planenormal.dot(spherecenter) - plane.w;
3202
				if(d > sphereradius) {
3203
					frontnodes.push(this);
3204
				} else if(d < -sphereradius) {
3205
					backnodes.push(this);
3206
				} else {
3207
					var splitresult = plane.splitPolygon(polygon);
3208
					switch(splitresult.type) {
3209
					case 0:
3210
						// coplanar front:
3211
						coplanarfrontnodes.push(this);
3212
						break;
3213

3214
					case 1:
3215
						// coplanar back:
3216
						coplanarbacknodes.push(this);
3217
						break;
3218

3219
					case 2:
3220
						// front:
3221
						frontnodes.push(this);
3222
						break;
3223

3224
					case 3:
3225
						// back:
3226
						backnodes.push(this);
3227
						break;
3228

3229
					case 4:
3230
						// spanning:
3231
						if(splitresult.front) {
3232
							var frontnode = this.addChild(splitresult.front);
3233
							frontnodes.push(frontnode);
3234
						}
3235
						if(splitresult.back) {
3236
							var backnode = this.addChild(splitresult.back);
3237
							backnodes.push(backnode);
3238
						}
3239
						break;
3240
					}
3241
				}
3242
			}
3243
		}
3244
	},
3245

3246

3247
	// PRIVATE methods from here:
3248
	// add child to a node
3249
	// this should be called whenever the polygon is split
3250
	// a child should be created for every fragment of the split polygon
3251
	// returns the newly created child
3252
	addChild: function(polygon) {
3253
		var newchild = new CSG.PolygonTreeNode();
3254
		newchild.parent = this;
3255
		newchild.polygon = polygon;
3256
		this.children.push(newchild);
3257
		return newchild;
3258
	},
3259

3260
	invertSub: function() {
3261
		if(this.polygon) {
3262
			this.polygon = this.polygon.flipped();
3263
		}
3264
		this.children.map(function(child) {
3265
			child.invertSub();
3266
		});
3267
	},
3268

3269
	recursivelyInvalidatePolygon: function() {
3270
		if(this.polygon) {
3271
			this.polygon = null;
3272
			if(this.parent) {
3273
				this.parent.recursivelyInvalidatePolygon();
3274
			}
3275
		}
3276
	}
3277
};
3278

3279

3280

3281
// # class Tree
3282
// This is the root of a BSP tree
3283
// We are using this separate class for the root of the tree, to hold the PolygonTreeNode root
3284
// The actual tree is kept in this.rootnode
3285
CSG.Tree = function(polygons) {
3286
	this.polygonTree = new CSG.PolygonTreeNode();
3287
	this.rootnode = new CSG.Node(null);
3288
	if(polygons) this.addPolygons(polygons);
3289
};
3290

3291
CSG.Tree.prototype = {
3292
	invert: function() {
3293
		this.polygonTree.invert();
3294
		this.rootnode.invert();
3295
	},
3296

3297
	// Remove all polygons in this BSP tree that are inside the other BSP tree
3298
	// `tree`.
3299
	clipTo: function(tree, alsoRemovecoplanarFront) {
3300
		alsoRemovecoplanarFront = alsoRemovecoplanarFront ? true : false;
3301
		this.rootnode.clipTo(tree, alsoRemovecoplanarFront);
3302
	},
3303

3304
	allPolygons: function() {
3305
		var result = [];
3306
		this.polygonTree.getPolygons(result);
3307
		return result;
3308
	},
3309

3310
	addPolygons: function(polygons) {
3311
		var _this = this;
3312
		var polygontreenodes = polygons.map(function(p) {
3313
			return _this.polygonTree.addChild(p);
3314
		});
3315
		this.rootnode.addPolygonTreeNodes(polygontreenodes);
3316
	}
3317
};
3318

3319
// # class Node
3320
// Holds a node in a BSP tree. A BSP tree is built from a collection of polygons
3321
// by picking a polygon to split along.
3322
// Polygons are not stored directly in the tree, but in PolygonTreeNodes, stored in
3323
// this.polygontreenodes. Those PolygonTreeNodes are children of the owning
3324
// CSG.Tree.polygonTree
3325
// This is not a leafy BSP tree since there is
3326
// no distinction between internal and leaf nodes.
3327
CSG.Node = function(parent) {
3328
	this.plane = null;
3329
	this.front = null;
3330
	this.back = null;
3331
	this.polygontreenodes = [];
3332
	this.parent = parent;
3333
};
3334

3335
CSG.Node.prototype = {
3336
	// Convert solid space to empty space and empty space to solid space.
3337
	invert: function() {
3338
		if(this.plane) this.plane = this.plane.flipped();
3339
		if(this.front) this.front.invert();
3340
		if(this.back) this.back.invert();
3341
		var temp = this.front;
3342
		this.front = this.back;
3343
		this.back = temp;
3344
	},
3345

3346
	// clip polygontreenodes to our plane
3347
	// calls remove() for all clipped PolygonTreeNodes
3348
	clipPolygons: function(polygontreenodes, alsoRemovecoplanarFront) {
3349
		if(this.plane) {
3350
			var backnodes = [];
3351
			var frontnodes = [];
3352
			var coplanarfrontnodes = alsoRemovecoplanarFront ? backnodes : frontnodes;
3353
			var plane = this.plane;
3354
			var numpolygontreenodes = polygontreenodes.length;
3355
			for(var i = 0; i < numpolygontreenodes; i++) {
3356
				var node = polygontreenodes[i];
3357
				if(!node.isRemoved()) {
3358
					node.splitByPlane(plane, coplanarfrontnodes, backnodes, frontnodes, backnodes);
3359
				}
3360
			}
3361
			if(this.front && (frontnodes.length > 0)) {
3362
				this.front.clipPolygons(frontnodes, alsoRemovecoplanarFront);
3363
			}
3364
			var numbacknodes = backnodes.length;
3365
			if(this.back && (numbacknodes > 0)) {
3366
				this.back.clipPolygons(backnodes, alsoRemovecoplanarFront);
3367
			} else {
3368
				// there's nothing behind this plane. Delete the nodes behind this plane:
3369
				for(var i = 0; i < numbacknodes; i++) {
3370
					backnodes[i].remove();
3371
				}
3372
			}
3373
		}
3374
	},
3375

3376
	// Remove all polygons in this BSP tree that are inside the other BSP tree
3377
	// `tree`.
3378
	clipTo: function(tree, alsoRemovecoplanarFront) {
3379
		if(this.polygontreenodes.length > 0) {
3380
			tree.rootnode.clipPolygons(this.polygontreenodes, alsoRemovecoplanarFront);
3381
		}
3382
		if(this.front) this.front.clipTo(tree, alsoRemovecoplanarFront);
3383
		if(this.back) this.back.clipTo(tree, alsoRemovecoplanarFront);
3384
	},
3385

3386
	addPolygonTreeNodes: function(polygontreenodes) {
3387
		if(polygontreenodes.length === 0) return;
3388
		var _this = this;
3389
		if(!this.plane) {
3390
			var bestplane = polygontreenodes[0].getPolygon().plane;
3391
			/*
3392
	  var parentnormals = [];
3393
	  this.getParentPlaneNormals(parentnormals, 6);
3394
//parentnormals = [];
3395
	  var numparentnormals = parentnormals.length;
3396
	  var minmaxnormal = 1.0;
3397
	  polygontreenodes.map(function(polygontreenode){
3398
		var plane = polygontreenodes[0].getPolygon().plane;
3399
		var planenormal = plane.normal;
3400
		var maxnormaldot = -1.0;
3401
		parentnormals.map(function(parentnormal){
3402
		  var dot = parentnormal.dot(planenormal);
3403
		  if(dot > maxnormaldot) maxnormaldot = dot;
3404
		});
3405
		if(maxnormaldot < minmaxnormal)
3406
		{
3407
		  minmaxnormal = maxnormaldot;
3408
		  bestplane = plane;
3409
		}
3410
	  });
3411
*/
3412
			this.plane = bestplane;
3413
		}
3414
		var frontnodes = [];
3415
		var backnodes = [];
3416
		polygontreenodes.map(function(polygontreenode) {
3417
			polygontreenode.splitByPlane(_this.plane, _this.polygontreenodes, backnodes, frontnodes, backnodes);
3418
		});
3419
		if(frontnodes.length > 0) {
3420
			if(!this.front) this.front = new CSG.Node(this);
3421
			this.front.addPolygonTreeNodes(frontnodes);
3422
		}
3423
		if(backnodes.length > 0) {
3424
			if(!this.back) this.back = new CSG.Node(this);
3425
			this.back.addPolygonTreeNodes(backnodes);
3426
		}
3427
	},
3428

3429
	getParentPlaneNormals: function(normals, maxdepth) {
3430
		if(maxdepth > 0) {
3431
			if(this.parent) {
3432
				normals.push(this.parent.plane.normal);
3433
				this.parent.getParentPlaneNormals(normals, maxdepth - 1);
3434
			}
3435
		}
3436
	}
3437
};
3438

3439
//////////
3440
// # class Matrix4x4:
3441
// Represents a 4x4 matrix. Elements are specified in row order
3442
CSG.Matrix4x4 = function(elements) {
3443
	if(arguments.length >= 1) {
3444
		this.elements = elements;
3445
	} else {
3446
		// if no arguments passed: create unity matrix
3447
		this.elements = [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1];
3448
	}
3449
};
3450

3451
CSG.Matrix4x4.prototype = {
3452
	plus: function(m) {
3453
		var r = [];
3454
		for(var i = 0; i < 16; i++) {
3455
			r[i] = this.elements[i] + m.elements[i];
3456
		}
3457
		return new CSG.Matrix4x4(r);
3458
	},
3459

3460
	minus: function(m) {
3461
		var r = [];
3462
		for(var i = 0; i < 16; i++) {
3463
			r[i] = this.elements[i] - m.elements[i];
3464
		}
3465
		return new CSG.Matrix4x4(r);
3466
	},
3467

3468
	// right multiply by another 4x4 matrix:
3469
	multiply: function(m) {
3470
		// cache elements in local variables, for speedup:
3471
		var this0 = this.elements[0];
3472
		var this1 = this.elements[1];
3473
		var this2 = this.elements[2];
3474
		var this3 = this.elements[3];
3475
		var this4 = this.elements[4];
3476
		var this5 = this.elements[5];
3477
		var this6 = this.elements[6];
3478
		var this7 = this.elements[7];
3479
		var this8 = this.elements[8];
3480
		var this9 = this.elements[9];
3481
		var this10 = this.elements[10];
3482
		var this11 = this.elements[11];
3483
		var this12 = this.elements[12];
3484
		var this13 = this.elements[13];
3485
		var this14 = this.elements[14];
3486
		var this15 = this.elements[15];
3487
		var m0 = m.elements[0];
3488
		var m1 = m.elements[1];
3489
		var m2 = m.elements[2];
3490
		var m3 = m.elements[3];
3491
		var m4 = m.elements[4];
3492
		var m5 = m.elements[5];
3493
		var m6 = m.elements[6];
3494
		var m7 = m.elements[7];
3495
		var m8 = m.elements[8];
3496
		var m9 = m.elements[9];
3497
		var m10 = m.elements[10];
3498
		var m11 = m.elements[11];
3499
		var m12 = m.elements[12];
3500
		var m13 = m.elements[13];
3501
		var m14 = m.elements[14];
3502
		var m15 = m.elements[15];
3503

3504
		var result = [];
3505
		result[0] = this0 * m0 + this1 * m4 + this2 * m8 + this3 * m12;
3506
		result[1] = this0 * m1 + this1 * m5 + this2 * m9 + this3 * m13;
3507
		result[2] = this0 * m2 + this1 * m6 + this2 * m10 + this3 * m14;
3508
		result[3] = this0 * m3 + this1 * m7 + this2 * m11 + this3 * m15;
3509
		result[4] = this4 * m0 + this5 * m4 + this6 * m8 + this7 * m12;
3510
		result[5] = this4 * m1 + this5 * m5 + this6 * m9 + this7 * m13;
3511
		result[6] = this4 * m2 + this5 * m6 + this6 * m10 + this7 * m14;
3512
		result[7] = this4 * m3 + this5 * m7 + this6 * m11 + this7 * m15;
3513
		result[8] = this8 * m0 + this9 * m4 + this10 * m8 + this11 * m12;
3514
		result[9] = this8 * m1 + this9 * m5 + this10 * m9 + this11 * m13;
3515
		result[10] = this8 * m2 + this9 * m6 + this10 * m10 + this11 * m14;
3516
		result[11] = this8 * m3 + this9 * m7 + this10 * m11 + this11 * m15;
3517
		result[12] = this12 * m0 + this13 * m4 + this14 * m8 + this15 * m12;
3518
		result[13] = this12 * m1 + this13 * m5 + this14 * m9 + this15 * m13;
3519
		result[14] = this12 * m2 + this13 * m6 + this14 * m10 + this15 * m14;
3520
		result[15] = this12 * m3 + this13 * m7 + this14 * m11 + this15 * m15;
3521
		return new CSG.Matrix4x4(result);
3522
	},
3523

3524
	clone: function() {
3525
		var elements = this.elements.map(function(p) {
3526
			return p;
3527
		});
3528
		return new CSG.Matrix4x4(elements);
3529
	},
3530

3531
	// Right multiply the matrix by a CSG.Vector3D (interpreted as 3 row, 1 column)
3532
	// (result = M*v)
3533
	// Fourth element is taken as 1
3534
	rightMultiply1x3Vector: function(v) {
3535
		var v0 = v._x;
3536
		var v1 = v._y;
3537
		var v2 = v._z;
3538
		var v3 = 1;
3539
		var x = v0 * this.elements[0] + v1 * this.elements[1] + v2 * this.elements[2] + v3 * this.elements[3];
3540
		var y = v0 * this.elements[4] + v1 * this.elements[5] + v2 * this.elements[6] + v3 * this.elements[7];
3541
		var z = v0 * this.elements[8] + v1 * this.elements[9] + v2 * this.elements[10] + v3 * this.elements[11];
3542
		var w = v0 * this.elements[12] + v1 * this.elements[13] + v2 * this.elements[14] + v3 * this.elements[15];
3543
		// scale such that fourth element becomes 1:
3544
		if(w != 1) {
3545
			var invw = 1.0 / w;
3546
			x *= invw;
3547
			y *= invw;
3548
			z *= invw;
3549
		}
3550
		return new CSG.Vector3D(x, y, z);
3551
	},
3552

3553
	// Multiply a CSG.Vector3D (interpreted as 3 column, 1 row) by this matrix
3554
	// (result = v*M)
3555
	// Fourth element is taken as 1
3556
	leftMultiply1x3Vector: function(v) {
3557
		var v0 = v._x;
3558
		var v1 = v._y;
3559
		var v2 = v._z;
3560
		var v3 = 1;
3561
		var x = v0 * this.elements[0] + v1 * this.elements[4] + v2 * this.elements[8] + v3 * this.elements[12];
3562
		var y = v0 * this.elements[1] + v1 * this.elements[5] + v2 * this.elements[9] + v3 * this.elements[13];
3563
		var z = v0 * this.elements[2] + v1 * this.elements[6] + v2 * this.elements[10] + v3 * this.elements[14];
3564
		var w = v0 * this.elements[3] + v1 * this.elements[7] + v2 * this.elements[11] + v3 * this.elements[15];
3565
		// scale such that fourth element becomes 1:
3566
		if(w != 1) {
3567
			var invw = 1.0 / w;
3568
			x *= invw;
3569
			y *= invw;
3570
			z *= invw;
3571
		}
3572
		return new CSG.Vector3D(x, y, z);
3573
	},
3574

3575
	// Right multiply the matrix by a CSG.Vector2D (interpreted as 2 row, 1 column)
3576
	// (result = M*v)
3577
	// Fourth element is taken as 1
3578
	rightMultiply1x2Vector: function(v) {
3579
		var v0 = v.x;
3580
		var v1 = v.y;
3581
		var v2 = 0;
3582
		var v3 = 1;
3583
		var x = v0 * this.elements[0] + v1 * this.elements[1] + v2 * this.elements[2] + v3 * this.elements[3];
3584
		var y = v0 * this.elements[4] + v1 * this.elements[5] + v2 * this.elements[6] + v3 * this.elements[7];
3585
		var z = v0 * this.elements[8] + v1 * this.elements[9] + v2 * this.elements[10] + v3 * this.elements[11];
3586
		var w = v0 * this.elements[12] + v1 * this.elements[13] + v2 * this.elements[14] + v3 * this.elements[15];
3587
		// scale such that fourth element becomes 1:
3588
		if(w != 1) {
3589
			var invw = 1.0 / w;
3590
			x *= invw;
3591
			y *= invw;
3592
			z *= invw;
3593
		}
3594
		return new CSG.Vector2D(x, y);
3595
	},
3596

3597
	// Multiply a CSG.Vector2D (interpreted as 2 column, 1 row) by this matrix
3598
	// (result = v*M)
3599
	// Fourth element is taken as 1
3600
	leftMultiply1x2Vector: function(v) {
3601
		var v0 = v.x;
3602
		var v1 = v.y;
3603
		var v2 = 0;
3604
		var v3 = 1;
3605
		var x = v0 * this.elements[0] + v1 * this.elements[4] + v2 * this.elements[8] + v3 * this.elements[12];
3606
		var y = v0 * this.elements[1] + v1 * this.elements[5] + v2 * this.elements[9] + v3 * this.elements[13];
3607
		var z = v0 * this.elements[2] + v1 * this.elements[6] + v2 * this.elements[10] + v3 * this.elements[14];
3608
		var w = v0 * this.elements[3] + v1 * this.elements[7] + v2 * this.elements[11] + v3 * this.elements[15];
3609
		// scale such that fourth element becomes 1:
3610
		if(w != 1) {
3611
			var invw = 1.0 / w;
3612
			x *= invw;
3613
			y *= invw;
3614
			z *= invw;
3615
		}
3616
		return new CSG.Vector2D(x, y);
3617
	},
3618

3619
	// determine whether this matrix is a mirroring transformation
3620
	isMirroring: function() {
3621
		var u = new CSG.Vector3D(this.elements[0], this.elements[4], this.elements[8]);
3622
		var v = new CSG.Vector3D(this.elements[1], this.elements[5], this.elements[9]);
3623
		var w = new CSG.Vector3D(this.elements[2], this.elements[6], this.elements[10]);
3624

3625
		// for a true orthogonal, non-mirrored base, u.cross(v) == w
3626
		// If they have an opposite direction then we are mirroring
3627
		var mirrorvalue = u.cross(v).dot(w);
3628
		var ismirror = (mirrorvalue < 0);
3629
		return ismirror;
3630
	}
3631
};
3632

3633
// return the unity matrix
3634
CSG.Matrix4x4.unity = function() {
3635
	return new CSG.Matrix4x4();
3636
};
3637

3638
// Create a rotation matrix for rotating around the x axis
3639
CSG.Matrix4x4.rotationX = function(degrees) {
3640
	var radians = degrees * Math.PI * (1.0 / 180.0);
3641
	var cos = Math.cos(radians);
3642
	var sin = Math.sin(radians);
3643
	var els = [
3644
	1, 0, 0, 0, 0, cos, sin, 0, 0, -sin, cos, 0, 0, 0, 0, 1];
3645
	return new CSG.Matrix4x4(els);
3646
};
3647

3648
// Create a rotation matrix for rotating around the y axis
3649
CSG.Matrix4x4.rotationY = function(degrees) {
3650
	var radians = degrees * Math.PI * (1.0 / 180.0);
3651
	var cos = Math.cos(radians);
3652
	var sin = Math.sin(radians);
3653
	var els = [
3654
	cos, 0, -sin, 0, 0, 1, 0, 0, sin, 0, cos, 0, 0, 0, 0, 1];
3655
	return new CSG.Matrix4x4(els);
3656
};
3657

3658
// Create a rotation matrix for rotating around the z axis
3659
CSG.Matrix4x4.rotationZ = function(degrees) {
3660
	var radians = degrees * Math.PI * (1.0 / 180.0);
3661
	var cos = Math.cos(radians);
3662
	var sin = Math.sin(radians);
3663
	var els = [
3664
	cos, sin, 0, 0, -sin, cos, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1];
3665
	return new CSG.Matrix4x4(els);
3666
};
3667

3668
// Matrix for rotation about arbitrary point and axis
3669
CSG.Matrix4x4.rotation = function(rotationCenter, rotationAxis, degrees) {
3670
	rotationCenter = new CSG.Vector3D(rotationCenter);
3671
	rotationAxis = new CSG.Vector3D(rotationAxis);
3672
	var rotationPlane = CSG.Plane.fromNormalAndPoint(rotationAxis, rotationCenter);
3673
	var orthobasis = new CSG.OrthoNormalBasis(rotationPlane);
3674
	var transformation = CSG.Matrix4x4.translation(rotationCenter.negated());
3675
	transformation = transformation.multiply(orthobasis.getProjectionMatrix());
3676
	transformation = transformation.multiply(CSG.Matrix4x4.rotationZ(degrees));
3677
	transformation = transformation.multiply(orthobasis.getInverseProjectionMatrix());
3678
	transformation = transformation.multiply(CSG.Matrix4x4.translation(rotationCenter));
3679
	return transformation;
3680
};
3681

3682
// Create an affine matrix for translation:
3683
CSG.Matrix4x4.translation = function(v) {
3684
	// parse as CSG.Vector3D, so we can pass an array or a CSG.Vector3D
3685
	var vec = new CSG.Vector3D(v);
3686
	var els = [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, vec.x, vec.y, vec.z, 1];
3687
	return new CSG.Matrix4x4(els);
3688
};
3689

3690
// Create an affine matrix for mirroring into an arbitrary plane:
3691
CSG.Matrix4x4.mirroring = function(plane) {
3692
	var nx = plane.normal.x;
3693
	var ny = plane.normal.y;
3694
	var nz = plane.normal.z;
3695
	var w = plane.w;
3696
	var els = [
3697
		(1.0 - 2.0 * nx * nx), (-2.0 * ny * nx), (-2.0 * nz * nx), 0,
3698
		(-2.0 * nx * ny), (1.0 - 2.0 * ny * ny), (-2.0 * nz * ny), 0,
3699
		(-2.0 * nx * nz), (-2.0 * ny * nz), (1.0 - 2.0 * nz * nz), 0,
3700
		(-2.0 * nx * w), (-2.0 * ny * w), (-2.0 * nz * w), 1
3701
	];
3702
	return new CSG.Matrix4x4(els);
3703
};
3704

3705
// Create an affine matrix for scaling:
3706
CSG.Matrix4x4.scaling = function(v) {
3707
	// parse as CSG.Vector3D, so we can pass an array or a CSG.Vector3D
3708
	var vec = new CSG.Vector3D(v);
3709
	var els = [
3710
	vec.x, 0, 0, 0, 0, vec.y, 0, 0, 0, 0, vec.z, 0, 0, 0, 0, 1];
3711
	return new CSG.Matrix4x4(els);
3712
};
3713

3714
///////////////////////////////////////////////////
3715
// # class Vector2D:
3716
// Represents a 2 element vector
3717
CSG.Vector2D = function(x, y) {
3718
	if(arguments.length == 2) {
3719
		this._x = parseFloat(x);
3720
		this._y = parseFloat(y);
3721
	} else {
3722
		var ok = true;
3723
		if(arguments.length == 1) {
3724
			if(typeof(x) == "object") {
3725
				if(x instanceof CSG.Vector2D) {
3726
					this._x = x._x;
3727
					this._y = x._y;
3728
				} else if(x instanceof Array) {
3729
					this._x = parseFloat(x[0]);
3730
					this._y = parseFloat(x[1]);
3731
				} else if(('x' in x) && ('y' in x)) {
3732
					this._x = parseFloat(x.x);
3733
					this._y = parseFloat(x.y);
3734
				} else ok = false;
3735
			} else {
3736
				var v = parseFloat(x);
3737
				this._x = v;
3738
				this._y = v;
3739
			}
3740
		} else ok = false;
3741
		if(ok) {
3742
			if((!CSG.IsFloat(this._x)) || (!CSG.IsFloat(this._y))) ok = false;
3743
		}
3744
		if(!ok) {
3745
			throw new Error("wrong arguments");
3746
		}
3747
	}
3748
};
3749

3750
CSG.Vector2D.fromAngle = function(radians) {
3751
	return CSG.Vector2D.fromAngleRadians(radians);
3752
};
3753

3754
CSG.Vector2D.fromAngleDegrees = function(degrees) {
3755
	var radians = Math.PI * degrees / 180;
3756
	return CSG.Vector2D.fromAngleRadians(radians);
3757
};
3758

3759
CSG.Vector2D.fromAngleRadians = function(radians) {
3760
	return new CSG.Vector2D(Math.cos(radians), Math.sin(radians));
3761
};
3762

3763
CSG.Vector2D.prototype = {
3764
	get x() {
3765
		return this._x;
3766
	}, get y() {
3767
		return this._y;
3768
	},
3769

3770
	set x(v) {
3771
		throw new Error("Vector2D is immutable");
3772
	}, set y(v) {
3773
		throw new Error("Vector2D is immutable");
3774
	},
3775

3776
	// extend to a 3D vector by adding a z coordinate:
3777
	toVector3D: function(z) {
3778
		return new CSG.Vector3D(this._x, this._y, z);
3779
	},
3780

3781
	equals: function(a) {
3782
		return(this._x == a._x) && (this._y == a._y);
3783
	},
3784

3785
	clone: function() {
3786
		return new CSG.Vector2D(this._x, this._y);
3787
	},
3788

3789
	negated: function() {
3790
		return new CSG.Vector2D(-this._x, -this._y);
3791
	},
3792

3793
	plus: function(a) {
3794
		return new CSG.Vector2D(this._x + a._x, this._y + a._y);
3795
	},
3796

3797
	minus: function(a) {
3798
		return new CSG.Vector2D(this._x - a._x, this._y - a._y);
3799
	},
3800

3801
	times: function(a) {
3802
		return new CSG.Vector2D(this._x * a, this._y * a);
3803
	},
3804

3805
	dividedBy: function(a) {
3806
		return new CSG.Vector2D(this._x / a, this._y / a);
3807
	},
3808

3809
	dot: function(a) {
3810
		return this._x * a._x + this._y * a._y;
3811
	},
3812

3813
	lerp: function(a, t) {
3814
		return this.plus(a.minus(this).times(t));
3815
	},
3816

3817
	length: function() {
3818
		return Math.sqrt(this.dot(this));
3819
	},
3820

3821
	distanceTo: function(a) {
3822
		return this.minus(a).length();
3823
	},
3824

3825
	distanceToSquared: function(a) {
3826
		return this.minus(a).lengthSquared();
3827
	},
3828

3829
	lengthSquared: function() {
3830
		return this.dot(this);
3831
	},
3832

3833
	unit: function() {
3834
		return this.dividedBy(this.length());
3835
	},
3836

3837
	cross: function(a) {
3838
		return this._x * a._y - this._y * a._x;
3839
	},
3840

3841
	// returns the vector rotated by 90 degrees clockwise
3842
	normal: function() {
3843
		return new CSG.Vector2D(this._y, -this._x);
3844
	},
3845

3846
	// Right multiply by a 4x4 matrix (the vector is interpreted as a row vector)
3847
	// Returns a new CSG.Vector2D
3848
	multiply4x4: function(matrix4x4) {
3849
		return matrix4x4.leftMultiply1x2Vector(this);
3850
	},
3851

3852
	transform: function(matrix4x4) {
3853
		return matrix4x4.leftMultiply1x2Vector(this);
3854
	},
3855

3856
	angle: function() {
3857
		return this.angleRadians();
3858
	},
3859

3860
	angleDegrees: function() {
3861
		var radians = this.angleRadians();
3862
		return 180 * radians / Math.PI;
3863
	},
3864

3865
	angleRadians: function() {
3866
		// y=sin, x=cos
3867
		return Math.atan2(this._y, this._x);
3868
	},
3869

3870
	min: function(p) {
3871
		return new CSG.Vector2D(
3872
		Math.min(this._x, p._x), Math.min(this._y, p._y));
3873
	},
3874

3875
	max: function(p) {
3876
		return new CSG.Vector2D(
3877
		Math.max(this._x, p._x), Math.max(this._y, p._y));
3878
	},
3879

3880
	toString: function() {
3881
		return "("+this._x.toFixed(2)+", "+this._y.toFixed(2)+")";
3882
	}
3883
};
3884

3885

3886
// # class Line2D
3887
// Represents a directional line in 2D space
3888
// A line is parametrized by its normal vector (perpendicular to the line, rotated 90 degrees counter clockwise)
3889
// and w. The line passes through the point <normal>.times(w).
3890
// normal must be a unit vector!
3891
// Equation: p is on line if normal.dot(p)==w
3892
CSG.Line2D = function(normal, w) {
3893
	normal = new CSG.Vector2D(normal);
3894
	w = parseFloat(w);
3895
	var l = normal.length();
3896
	// normalize:
3897
	w *= l;
3898
	normal = normal.times(1.0 / l);
3899
	this.normal = normal;
3900
	this.w = w;
3901
};
3902

3903
CSG.Line2D.fromPoints = function(p1, p2) {
3904
	p1 = new CSG.Vector2D(p1);
3905
	p2 = new CSG.Vector2D(p2);
3906
	var direction = p2.minus(p1);
3907
	var normal = direction.normal().negated().unit();
3908
	var w = p1.dot(normal);
3909
	return new CSG.Line2D(normal, w);
3910
};
3911

3912
CSG.Line2D.prototype = {
3913
	// same line but opposite direction:
3914
	reverse: function() {
3915
		return new CSG.Line2D(this.normal.negated(), -this.w);
3916
	},
3917

3918
	equals: function(l) {
3919
		return(l.normal.equals(this.normal) && (l.w == this.w));
3920
	},
3921

3922
	origin: function() {
3923
		return this.normal.times(this.w);
3924
	},
3925

3926
	direction: function() {
3927
		return this.normal.normal();
3928
	},
3929

3930
	xAtY: function(y) {
3931
		// (py == y) && (normal * p == w)
3932
		// -> px = (w - normal._y * y) / normal.x
3933
		var x = (this.w - this.normal._y * y) / this.normal.x;
3934
		return x;
3935
	},
3936

3937
	absDistanceToPoint: function(point) {
3938
		point = new CSG.Vector2D(point);
3939
		var point_projected = point.dot(this.normal);
3940
		var distance = Math.abs(point_projected - this.w);
3941
		return distance;
3942
	},
3943
	/*FIXME: has error - origin is not defined, the method is never used
3944
	closestPoint: function(point) {
3945
		point = new CSG.Vector2D(point);
3946
		var vector = point.dot(this.direction());
3947
		return origin.plus(vector);
3948
	},
3949
	*/
3950

3951
	// intersection between two lines, returns point as Vector2D
3952
	intersectWithLine: function(line2d) {
3953
		var point = CSG.solve2Linear(this.normal.x, this.normal.y, line2d.normal.x, line2d.normal.y, this.w, line2d.w);
3954
		point = new CSG.Vector2D(point); // make  vector2d
3955
		return point;
3956
	},
3957

3958
	transform: function(matrix4x4) {
3959
		var origin = new CSG.Vector2D(0, 0);
3960
		var pointOnPlane = this.normal.times(this.w);
3961
		var neworigin = origin.multiply4x4(matrix4x4);
3962
		var neworiginPlusNormal = this.normal.multiply4x4(matrix4x4);
3963
		var newnormal = neworiginPlusNormal.minus(neworigin);
3964
		var newpointOnPlane = pointOnPlane.multiply4x4(matrix4x4);
3965
		var neww = newnormal.dot(newpointOnPlane);
3966
		return new CSG.Line2D(newnormal, neww);
3967
	}
3968
};
3969

3970
// # class Line3D
3971
// Represents a line in 3D space
3972
// direction must be a unit vector
3973
// point is a random point on the line
3974
CSG.Line3D = function(point, direction) {
3975
	point = new CSG.Vector3D(point);
3976
	direction = new CSG.Vector3D(direction);
3977
	this.point = point;
3978
	this.direction = direction.unit();
3979
};
3980

3981
CSG.Line3D.fromPoints = function(p1, p2) {
3982
	p1 = new CSG.Vector3D(p1);
3983
	p2 = new CSG.Vector3D(p2);
3984
	var direction = p2.minus(p1).unit();
3985
	return new CSG.Line3D(p1, direction);
3986
};
3987

3988
CSG.Line3D.fromPlanes = function(p1, p2) {
3989
	var direction = p1.normal.cross(p2.normal);
3990
	var l = direction.length();
3991
	if(l < 1e-10) {
3992
		throw new Error("Parallel planes");
3993
	}
3994
	direction = direction.times(1.0 / l);
3995

3996
	var mabsx = Math.abs(direction.x);
3997
	var mabsy = Math.abs(direction.y);
3998
	var mabsz = Math.abs(direction.z);
3999
	var origin;
4000
	if((mabsx >= mabsy) && (mabsx >= mabsz)) {
4001
		// direction vector is mostly pointing towards x
4002
		// find a point p for which x is zero:
4003
		var r = CSG.solve2Linear(p1.normal.y, p1.normal.z, p2.normal.y, p2.normal.z, p1.w, p2.w);
4004
		origin = new CSG.Vector3D(0, r[0], r[1]);
4005
	} else if((mabsy >= mabsx) && (mabsy >= mabsz)) {
4006
		// find a point p for which y is zero:
4007
		var r = CSG.solve2Linear(p1.normal.x, p1.normal.z, p2.normal.x, p2.normal.z, p1.w, p2.w);
4008
		origin = new CSG.Vector3D(r[0], 0, r[1]);
4009
	} else {
4010
		// find a point p for which z is zero:
4011
		var r = CSG.solve2Linear(p1.normal.x, p1.normal.y, p2.normal.x, p2.normal.y, p1.w, p2.w);
4012
		origin = new CSG.Vector3D(r[0], r[1], 0);
4013
	}
4014
	return new CSG.Line3D(origin, direction);
4015
};
4016

4017

4018
CSG.Line3D.prototype = {
4019
	intersectWithPlane: function(plane) {
4020
		// plane: plane.normal * p = plane.w
4021
		// line: p=line.point + labda * line.direction
4022
		var labda = (plane.w - plane.normal.dot(this.point)) / plane.normal.dot(this.direction);
4023
		var point = this.point.plus(this.direction.times(labda));
4024
		return point;
4025
	},
4026

4027
	clone: function(line) {
4028
		return new CSG.Line3D(this.point.clone(), this.direction.clone());
4029
	},
4030

4031
	reverse: function() {
4032
		return new CSG.Line3D(this.point.clone(), this.direction.negated());
4033
	},
4034

4035
	transform: function(matrix4x4) {
4036
		var newpoint = this.point.multiply4x4(matrix4x4);
4037
		var pointPlusDirection = this.point.plus(this.direction);
4038
		var newPointPlusDirection = pointPlusDirection.multiply4x4(matrix4x4);
4039
		var newdirection = newPointPlusDirection.minus(newpoint);
4040
		return new CSG.Line3D(newpoint, newdirection);
4041
	},
4042

4043
	closestPointOnLine: function(point) {
4044
		point = new CSG.Vector3D(point);
4045
		var t = point.minus(this.point).dot(this.direction) / this.direction.dot(this.direction);
4046
		var closestpoint = this.point.plus(this.direction.times(t));
4047
		return closestpoint;
4048
	},
4049

4050
	distanceToPoint: function(point) {
4051
		point = new CSG.Vector3D(point);
4052
		var closestpoint = this.closestPointOnLine(point);
4053
		var distancevector = point.minus(closestpoint);
4054
		var distance = distancevector.length();
4055
		return distance;
4056
	},
4057

4058
	equals: function(line3d) {
4059
		if(!this.direction.equals(line3d.direction)) return false;
4060
		var distance = this.distanceToPoint(line3d.point);
4061
		if(distance > 1e-8) return false;
4062
		return true;
4063
	}
4064
};
4065

4066

4067
// # class OrthoNormalBasis
4068
// Reprojects points on a 3D plane onto a 2D plane
4069
// or from a 2D plane back onto the 3D plane
4070
CSG.OrthoNormalBasis = function(plane, rightvector) {
4071
	if(arguments.length < 2) {
4072
		// choose an arbitrary right hand vector, making sure it is somewhat orthogonal to the plane normal:
4073
		rightvector = plane.normal.randomNonParallelVector();
4074
	} else {
4075
		rightvector = new CSG.Vector3D(rightvector);
4076
	}
4077
	this.v = plane.normal.cross(rightvector).unit();
4078
	this.u = this.v.cross(plane.normal);
4079
	this.plane = plane;
4080
	this.planeorigin = plane.normal.times(plane.w);
4081
};
4082

4083
// The z=0 plane, with the 3D x and y vectors mapped to the 2D x and y vector
4084
CSG.OrthoNormalBasis.Z0Plane = function() {
4085
	var plane = new CSG.Plane(new CSG.Vector3D([0, 0, 1]), 0);
4086
	return new CSG.OrthoNormalBasis(plane, new CSG.Vector3D([1, 0, 0]));
4087
};
4088

4089
CSG.OrthoNormalBasis.prototype = {
4090
	getProjectionMatrix: function() {
4091
		return new CSG.Matrix4x4([
4092
			this.u.x, this.v.x, this.plane.normal.x, 0,
4093
			this.u.y, this.v.y, this.plane.normal.y, 0,
4094
			this.u.z, this.v.z, this.plane.normal.z, 0,
4095
			0, 0, -this.plane.w, 1]);
4096
	},
4097

4098
	getInverseProjectionMatrix: function() {
4099
		var p = this.plane.normal.times(this.plane.w);
4100
		return new CSG.Matrix4x4([
4101
			this.u.x, this.u.y, this.u.z, 0,
4102
			this.v.x, this.v.y, this.v.z, 0,
4103
			this.plane.normal.x, this.plane.normal.y, this.plane.normal.z, 0,
4104
			p.x, p.y, p.z, 1]);
4105
	},
4106

4107
	to2D: function(vec3) {
4108
		return new CSG.Vector2D(vec3.dot(this.u), vec3.dot(this.v));
4109
	},
4110

4111
	to3D: function(vec2) {
4112
		return this.planeorigin.plus(this.u.times(vec2.x)).plus(this.v.times(vec2.y));
4113
	},
4114

4115
	line3Dto2D: function(line3d) {
4116
		var a = line3d.point;
4117
		var b = line3d.direction.plus(a);
4118
		var a2d = this.to2D(a);
4119
		var b2d = this.to2D(b);
4120
		return CSG.Line2D.fromPoints(a2d, b2d);
4121
	},
4122

4123
	line2Dto3D: function(line2d) {
4124
		var a = line2d.origin();
4125
		var b = line2d.direction().plus(a);
4126
		var a3d = this.to3D(a);
4127
		var b3d = this.to3D(b);
4128
		return CSG.Line3D.fromPoints(a3d, b3d);
4129
	},
4130

4131
	transform: function(matrix4x4) {
4132
		// todo: this may not work properly in case of mirroring
4133
		var newplane = this.plane.transform(matrix4x4);
4134
		var rightpoint_transformed = this.u.transform(matrix4x4);
4135
		var origin_transformed = new CSG.Vector3D(0, 0, 0).transform(matrix4x4);
4136
		var newrighthandvector = rightpoint_transformed.minus(origin_transformed);
4137
		var newbasis = new CSG.OrthoNormalBasis(newplane, newrighthandvector);
4138
		return newbasis;
4139
	}
4140
};
4141

4142
function insertSorted(array, element, comparefunc) {
4143
	var leftbound = 0;
4144
	var rightbound = array.length;
4145
	while(rightbound > leftbound) {
4146
		var testindex = Math.floor((leftbound + rightbound) / 2);
4147
		var testelement = array[testindex];
4148
		var compareresult = comparefunc(element, testelement);
4149
		if(compareresult > 0) // element > testelement
4150
		{
4151
			leftbound = testindex + 1;
4152
		} else {
4153
			rightbound = testindex;
4154
		}
4155
	}
4156
	array.splice(leftbound, 0, element);
4157
}
4158

4159
// Get the x coordinate of a point with a certain y coordinate, interpolated between two
4160
// points (CSG.Vector2D).
4161
// Interpolation is robust even if the points have the same y coordinate
4162
CSG.interpolateBetween2DPointsForY = function(point1, point2, y) {
4163
	var f1 = y - point1.y;
4164
	var f2 = point2.y - point1.y;
4165
	if(f2 < 0) {
4166
		f1 = -f1;
4167
		f2 = -f2;
4168
	}
4169
	var t;
4170
	if(f1 <= 0) {
4171
		t = 0.0;
4172
	} else if(f1 >= f2) {
4173
		t = 1.0;
4174
	} else if(f2 < 1e-10) {
4175
		t = 0.5;
4176
	} else {
4177
		t = f1 / f2;
4178
	}
4179
	var result = point1.x + t * (point2.x - point1.x);
4180
	return result;
4181
};
4182

4183
// Retesselation function for a set of coplanar polygons. See the introduction at the top of
4184
// this file.
4185
CSG.reTesselateCoplanarPolygons = function(sourcepolygons, destpolygons) {
4186
	var EPS = 1e-5;
4187

4188
	var numpolygons = sourcepolygons.length;
4189
	if(numpolygons > 0) {
4190
		var plane = sourcepolygons[0].plane;
4191
		var shared = sourcepolygons[0].shared;
4192
		var orthobasis = new CSG.OrthoNormalBasis(plane);
4193
		var polygonvertices2d = []; // array of array of CSG.Vector2D
4194
		var polygontopvertexindexes = []; // array of indexes of topmost vertex per polygon
4195
		var topy2polygonindexes = {};
4196
		var ycoordinatetopolygonindexes = {};
4197

4198
		var xcoordinatebins = {};
4199
		var ycoordinatebins = {};
4200

4201
		// convert all polygon vertices to 2D
4202
		// Make a list of all encountered y coordinates
4203
		// And build a map of all polygons that have a vertex at a certain y coordinate:
4204
		var ycoordinateBinningFactor = 1.0 / EPS * 10;
4205
		for(var polygonindex = 0; polygonindex < numpolygons; polygonindex++) {
4206
			var poly3d = sourcepolygons[polygonindex];
4207
			var vertices2d = [];
4208
			var numvertices = poly3d.vertices.length;
4209
			var minindex = -1;
4210
			if(numvertices > 0) {
4211
				var miny, maxy, maxindex;
4212
				for(var i = 0; i < numvertices; i++) {
4213
					var pos2d = orthobasis.to2D(poly3d.vertices[i].pos);
4214
					// perform binning of y coordinates: If we have multiple vertices very
4215
					// close to each other, give them the same y coordinate:
4216
					var ycoordinatebin = Math.floor(pos2d.y * ycoordinateBinningFactor);
4217
					var newy;
4218
					if(ycoordinatebin in ycoordinatebins) {
4219
						newy = ycoordinatebins[ycoordinatebin];
4220
					} else if(ycoordinatebin + 1 in ycoordinatebins) {
4221
						newy = ycoordinatebins[ycoordinatebin + 1];
4222
					} else if(ycoordinatebin - 1 in ycoordinatebins) {
4223
						newy = ycoordinatebins[ycoordinatebin - 1];
4224
					} else {
4225
						newy = pos2d.y;
4226
						ycoordinatebins[ycoordinatebin] = pos2d.y;
4227
					}
4228
					pos2d = new CSG.Vector2D(pos2d.x, newy);
4229
					vertices2d.push(pos2d);
4230
					var y = pos2d.y;
4231
					if((i === 0) || (y < miny)) {
4232
						miny = y;
4233
						minindex = i;
4234
					}
4235
					if((i === 0) || (y > maxy)) {
4236
						maxy = y;
4237
						maxindex = i;
4238
					}
4239
					if(!(y in ycoordinatetopolygonindexes)) {
4240
						ycoordinatetopolygonindexes[y] = {};
4241
					}
4242
					ycoordinatetopolygonindexes[y][polygonindex] = true;
4243
				}
4244
				if(miny >= maxy) {
4245
					// degenerate polygon, all vertices have same y coordinate. Just ignore it from now:
4246
					vertices2d = [];
4247
				} else {
4248
					if(!(miny in topy2polygonindexes)) {
4249
						topy2polygonindexes[miny] = [];
4250
					}
4251
					topy2polygonindexes[miny].push(polygonindex);
4252
				}
4253
			} // if(numvertices > 0)
4254
			// reverse the vertex order:
4255
			vertices2d.reverse();
4256
			minindex = numvertices - minindex - 1;
4257
			polygonvertices2d.push(vertices2d);
4258
			polygontopvertexindexes.push(minindex);
4259
		}
4260
		var ycoordinates = [];
4261
		for(var ycoordinate in ycoordinatetopolygonindexes) ycoordinates.push(ycoordinate);
4262
		ycoordinates.sort(fnNumberSort);
4263

4264
		// Now we will iterate over all y coordinates, from lowest to highest y coordinate
4265
		// activepolygons: source polygons that are 'active', i.e. intersect with our y coordinate
4266
		//   Is sorted so the polygons are in left to right order
4267
		// Each element in activepolygons has these properties:
4268
		//        polygonindex: the index of the source polygon (i.e. an index into the sourcepolygons
4269
		//                      and polygonvertices2d arrays)
4270
		//        leftvertexindex: the index of the vertex at the left side of the polygon (lowest x)
4271
		//                         that is at or just above the current y coordinate
4272
		//        rightvertexindex: dito at right hand side of polygon
4273
		//        topleft, bottomleft: coordinates of the left side of the polygon crossing the current y coordinate
4274
		//        topright, bottomright: coordinates of the right hand side of the polygon crossing the current y coordinate
4275
		var activepolygons = [];
4276
		var prevoutpolygonrow = [];
4277
		for(var yindex = 0; yindex < ycoordinates.length; yindex++) {
4278
			var newoutpolygonrow = [];
4279
			var ycoordinate_as_string = ycoordinates[yindex];
4280
			var ycoordinate = Number(ycoordinate_as_string);
4281

4282
			// update activepolygons for this y coordinate:
4283
			// - Remove any polygons that end at this y coordinate
4284
			// - update leftvertexindex and rightvertexindex (which point to the current vertex index
4285
			//   at the the left and right side of the polygon
4286
			// Iterate over all polygons that have a corner at this y coordinate:
4287
			var polygonindexeswithcorner = ycoordinatetopolygonindexes[ycoordinate_as_string];
4288
			for(var activepolygonindex = 0; activepolygonindex < activepolygons.length; ++activepolygonindex) {
4289
				var activepolygon = activepolygons[activepolygonindex];
4290
				var polygonindex = activepolygon.polygonindex;
4291
				if(polygonindexeswithcorner[polygonindex]) {
4292
					// this active polygon has a corner at this y coordinate:
4293
					var vertices2d = polygonvertices2d[polygonindex];
4294
					var numvertices = vertices2d.length;
4295
					var newleftvertexindex = activepolygon.leftvertexindex;
4296
					var newrightvertexindex = activepolygon.rightvertexindex;
4297
					// See if we need to increase leftvertexindex or decrease rightvertexindex:
4298
					while(true) {
4299
						var nextleftvertexindex = newleftvertexindex + 1;
4300
						if(nextleftvertexindex >= numvertices) nextleftvertexindex = 0;
4301
						if(vertices2d[nextleftvertexindex].y != ycoordinate) break;
4302
						newleftvertexindex = nextleftvertexindex;
4303
					}
4304
					var nextrightvertexindex = newrightvertexindex - 1;
4305
					if(nextrightvertexindex < 0) nextrightvertexindex = numvertices - 1;
4306
					if(vertices2d[nextrightvertexindex].y == ycoordinate) {
4307
						newrightvertexindex = nextrightvertexindex;
4308
					}
4309
					if((newleftvertexindex != activepolygon.leftvertexindex) && (newleftvertexindex == newrightvertexindex)) {
4310
						// We have increased leftvertexindex or decreased rightvertexindex, and now they point to the same vertex
4311
						// This means that this is the bottom point of the polygon. We'll remove it:
4312
						activepolygons.splice(activepolygonindex, 1);
4313
						--activepolygonindex;
4314
					} else {
4315
						activepolygon.leftvertexindex = newleftvertexindex;
4316
						activepolygon.rightvertexindex = newrightvertexindex;
4317
						activepolygon.topleft = vertices2d[newleftvertexindex];
4318
						activepolygon.topright = vertices2d[newrightvertexindex];
4319
						var nextleftvertexindex = newleftvertexindex + 1;
4320
						if(nextleftvertexindex >= numvertices) nextleftvertexindex = 0;
4321
						activepolygon.bottomleft = vertices2d[nextleftvertexindex];
4322
						var nextrightvertexindex = newrightvertexindex - 1;
4323
						if(nextrightvertexindex < 0) nextrightvertexindex = numvertices - 1;
4324
						activepolygon.bottomright = vertices2d[nextrightvertexindex];
4325
					}
4326
				} // if polygon has corner here
4327
			} // for activepolygonindex
4328
			var nextycoordinate;
4329
			if(yindex >= ycoordinates.length - 1) {
4330
				// last row, all polygons must be finished here:
4331
				activepolygons = [];
4332
				nextycoordinate = null;
4333
			} else // yindex < ycoordinates.length-1
4334
			{
4335
				nextycoordinate = Number(ycoordinates[yindex + 1]);
4336
				var middleycoordinate = 0.5 * (ycoordinate + nextycoordinate);
4337
				// update activepolygons by adding any polygons that start here:
4338
				var startingpolygonindexes = topy2polygonindexes[ycoordinate_as_string];
4339
				for(var polygonindex_key in startingpolygonindexes) {
4340
					var polygonindex = startingpolygonindexes[polygonindex_key];
4341
					var vertices2d = polygonvertices2d[polygonindex];
4342
					var numvertices = vertices2d.length;
4343
					var topvertexindex = polygontopvertexindexes[polygonindex];
4344
					// the top of the polygon may be a horizontal line. In that case topvertexindex can point to any point on this line.
4345
					// Find the left and right topmost vertices which have the current y coordinate:
4346
					var topleftvertexindex = topvertexindex;
4347
					while(true) {
4348
						var i = topleftvertexindex + 1;
4349
						if(i >= numvertices) i = 0;
4350
						if(vertices2d[i].y != ycoordinate) break;
4351
						if(i == topvertexindex) break; // should not happen, but just to prevent endless loops
4352
						topleftvertexindex = i;
4353
					}
4354
					var toprightvertexindex = topvertexindex;
4355
					while(true) {
4356
						var i = toprightvertexindex - 1;
4357
						if(i < 0) i = numvertices - 1;
4358
						if(vertices2d[i].y != ycoordinate) break;
4359
						if(i == topleftvertexindex) break; // should not happen, but just to prevent endless loops
4360
						toprightvertexindex = i;
4361
					}
4362
					var nextleftvertexindex = topleftvertexindex + 1;
4363
					if(nextleftvertexindex >= numvertices) nextleftvertexindex = 0;
4364
					var nextrightvertexindex = toprightvertexindex - 1;
4365
					if(nextrightvertexindex < 0) nextrightvertexindex = numvertices - 1;
4366
					var newactivepolygon = {
4367
						polygonindex: polygonindex,
4368
						leftvertexindex: topleftvertexindex,
4369
						rightvertexindex: toprightvertexindex,
4370
						topleft: vertices2d[topleftvertexindex],
4371
						topright: vertices2d[toprightvertexindex],
4372
						bottomleft: vertices2d[nextleftvertexindex],
4373
						bottomright: vertices2d[nextrightvertexindex],
4374
					};
4375
					insertSorted(activepolygons, newactivepolygon, function(el1, el2) {
4376
						var x1 = CSG.interpolateBetween2DPointsForY(
4377
									el1.topleft, el1.bottomleft, middleycoordinate);
4378
						var x2 = CSG.interpolateBetween2DPointsForY(
4379
									el2.topleft, el2.bottomleft, middleycoordinate);
4380
						if(x1 > x2) return 1;
4381
						if(x1 < x2) return -1;
4382
						return 0;
4383
					});
4384
				} // for(var polygonindex in startingpolygonindexes)
4385
			} //  yindex < ycoordinates.length-1
4386
			//if( (yindex == ycoordinates.length-1) || (nextycoordinate - ycoordinate > EPS) )
4387
			if(true) {
4388
				// Now activepolygons is up to date
4389
				// Build the output polygons for the next row in newoutpolygonrow:
4390
				for(var activepolygon_key in activepolygons) {
4391
					var activepolygon = activepolygons[activepolygon_key];
4392
					var polygonindex = activepolygon.polygonindex;
4393
					var vertices2d = polygonvertices2d[polygonindex];
4394
					var numvertices = vertices2d.length;
4395

4396
					var x = CSG.interpolateBetween2DPointsForY(activepolygon.topleft, activepolygon.bottomleft, ycoordinate);
4397
					var topleft = new CSG.Vector2D(x, ycoordinate);
4398
					x = CSG.interpolateBetween2DPointsForY(activepolygon.topright, activepolygon.bottomright, ycoordinate);
4399
					var topright = new CSG.Vector2D(x, ycoordinate);
4400
					x = CSG.interpolateBetween2DPointsForY(activepolygon.topleft, activepolygon.bottomleft, nextycoordinate);
4401
					var bottomleft = new CSG.Vector2D(x, nextycoordinate);
4402
					x = CSG.interpolateBetween2DPointsForY(activepolygon.topright, activepolygon.bottomright, nextycoordinate);
4403
					var bottomright = new CSG.Vector2D(x, nextycoordinate);
4404
					var outpolygon = {
4405
						topleft: topleft,
4406
						topright: topright,
4407
						bottomleft: bottomleft,
4408
						bottomright: bottomright,
4409
						leftline: CSG.Line2D.fromPoints(topleft, bottomleft),
4410
						rightline: CSG.Line2D.fromPoints(bottomright, topright)
4411
					};
4412
					if(newoutpolygonrow.length > 0) {
4413
						var prevoutpolygon = newoutpolygonrow[newoutpolygonrow.length - 1];
4414
						var d1 = outpolygon.topleft.distanceTo(prevoutpolygon.topright);
4415
						var d2 = outpolygon.bottomleft.distanceTo(prevoutpolygon.bottomright);
4416
						if((d1 < EPS) && (d2 < EPS)) {
4417
							// we can join this polygon with the one to the left:
4418
							outpolygon.topleft = prevoutpolygon.topleft;
4419
							outpolygon.leftline = prevoutpolygon.leftline;
4420
							outpolygon.bottomleft = prevoutpolygon.bottomleft;
4421
							newoutpolygonrow.splice(newoutpolygonrow.length - 1, 1);
4422
						}
4423
					}
4424
					newoutpolygonrow.push(outpolygon);
4425
				} // for(activepolygon in activepolygons)
4426
				if(yindex > 0) {
4427
					// try to match the new polygons against the previous row:
4428
					var prevcontinuedindexes = {};
4429
					var matchedindexes = {};
4430
					for(var i = 0; i < newoutpolygonrow.length; i++) {
4431
						var thispolygon = newoutpolygonrow[i];
4432
						for(var ii = 0; ii < prevoutpolygonrow.length; ii++) {
4433
							if(!matchedindexes[ii]) // not already processed?
4434
							{
4435
								// We have a match if the sidelines are equal or if the top coordinates
4436
								// are on the sidelines of the previous polygon
4437
								var prevpolygon = prevoutpolygonrow[ii];
4438
								if(prevpolygon.bottomleft.distanceTo(thispolygon.topleft) < EPS) {
4439
									if(prevpolygon.bottomright.distanceTo(thispolygon.topright) < EPS) {
4440
										// Yes, the top of this polygon matches the bottom of the previous:
4441
										matchedindexes[ii] = true;
4442
										// Now check if the joined polygon would remain convex:
4443
										var d1 = thispolygon.leftline.direction().x - prevpolygon.leftline.direction().x;
4444
										var d2 = thispolygon.rightline.direction().x - prevpolygon.rightline.direction().x;
4445
										var leftlinecontinues = Math.abs(d1) < EPS;
4446
										var rightlinecontinues = Math.abs(d2) < EPS;
4447
										var leftlineisconvex = leftlinecontinues || (d1 >= 0);
4448
										var rightlineisconvex = rightlinecontinues || (d2 >= 0);
4449
										if(leftlineisconvex && rightlineisconvex) {
4450
											// yes, both sides have convex corners:
4451
											// This polygon will continue the previous polygon
4452
											thispolygon.outpolygon = prevpolygon.outpolygon;
4453
											thispolygon.leftlinecontinues = leftlinecontinues;
4454
											thispolygon.rightlinecontinues = rightlinecontinues;
4455
											prevcontinuedindexes[ii] = true;
4456
										}
4457
										break;
4458
									}
4459
								}
4460
							} // if(!prevcontinuedindexes[ii])
4461
						} // for ii
4462
					} // for i
4463
					for(var ii = 0; ii < prevoutpolygonrow.length; ii++) {
4464
						if(!prevcontinuedindexes[ii]) {
4465
							// polygon ends here
4466
							// Finish the polygon with the last point(s):
4467
							var prevpolygon = prevoutpolygonrow[ii];
4468
							prevpolygon.outpolygon.rightpoints.push(prevpolygon.bottomright);
4469
							if(prevpolygon.bottomright.distanceTo(prevpolygon.bottomleft) > EPS) {
4470
								// polygon ends with a horizontal line:
4471
								prevpolygon.outpolygon.leftpoints.push(prevpolygon.bottomleft);
4472
							}
4473
							// reverse the left half so we get a counterclockwise circle:
4474
							prevpolygon.outpolygon.leftpoints.reverse();
4475
							var points2d = prevpolygon.outpolygon.rightpoints.concat(prevpolygon.outpolygon.leftpoints);
4476
							var vertices3d = [];
4477
							points2d.map(function(point2d) {
4478
								var point3d = orthobasis.to3D(point2d);
4479
								var vertex3d = new CSG.Vertex(point3d);
4480
								vertices3d.push(vertex3d);
4481
							});
4482
							var polygon = new CSG.Polygon(vertices3d, shared, plane);
4483
							destpolygons.push(polygon);
4484
						}
4485
					}
4486
				} // if(yindex > 0)
4487
				for(var i = 0; i < newoutpolygonrow.length; i++) {
4488
					var thispolygon = newoutpolygonrow[i];
4489
					if(!thispolygon.outpolygon) {
4490
						// polygon starts here:
4491
						thispolygon.outpolygon = {
4492
							leftpoints: [],
4493
							rightpoints: []
4494
						};
4495
						thispolygon.outpolygon.leftpoints.push(thispolygon.topleft);
4496
						if(thispolygon.topleft.distanceTo(thispolygon.topright) > EPS) {
4497
							// we have a horizontal line at the top:
4498
							thispolygon.outpolygon.rightpoints.push(thispolygon.topright);
4499
						}
4500
					} else {
4501
						// continuation of a previous row
4502
						if(!thispolygon.leftlinecontinues) {
4503
							thispolygon.outpolygon.leftpoints.push(thispolygon.topleft);
4504
						}
4505
						if(!thispolygon.rightlinecontinues) {
4506
							thispolygon.outpolygon.rightpoints.push(thispolygon.topright);
4507
						}
4508
					}
4509
				}
4510
				prevoutpolygonrow = newoutpolygonrow;
4511
			}
4512
		} // for yindex
4513
	} // if(numpolygons > 0)
4514
};
4515

4516
////////////////////////////////
4517
// ## class fuzzyFactory
4518
// This class acts as a factory for objects. We can search for an object with approximately
4519
// the desired properties (say a rectangle with width 2 and height 1)
4520
// The lookupOrCreate() method looks for an existing object (for example it may find an existing rectangle
4521
// with width 2.0001 and height 0.999. If no object is found, the user supplied callback is
4522
// called, which should generate a new object. The new object is inserted into the database
4523
// so it can be found by future lookupOrCreate() calls.
4524
// Constructor:
4525
//   numdimensions: the number of parameters for each object
4526
//     for example for a 2D rectangle this would be 2
4527
//   tolerance: The maximum difference for each parameter allowed to be considered a match
4528
CSG.fuzzyFactory = function(numdimensions, tolerance) {
4529
	var lookuptable = [];
4530
	for(var i = 0; i < numdimensions; i++) {
4531
		lookuptable.push({});
4532
	}
4533
	this.lookuptable = lookuptable;
4534
	this.nextElementId = 1;
4535
	this.multiplier = 1.0 / tolerance;
4536
	this.objectTable = {};
4537
};
4538

4539
CSG.fuzzyFactory.prototype = {
4540
	// var obj = f.lookupOrCreate([el1, el2, el3], function(elements) {/* create the new object */});
4541
	// Performs a fuzzy lookup of the object with the specified elements.
4542
	// If found, returns the existing object
4543
	// If not found, calls the supplied callback function which should create a new object with
4544
	// the specified properties. This object is inserted in the lookup database.
4545
	lookupOrCreate: function(els, creatorCallback) {
4546
		var object;
4547
		var key = this.lookupKey(els);
4548
		if(key === null) {
4549
			object = creatorCallback(els);
4550
			key = this.nextElementId++;
4551
			this.objectTable[key] = object;
4552
			for(var dimension = 0; dimension < els.length; dimension++) {
4553
				var elementLookupTable = this.lookuptable[dimension];
4554
				var value = els[dimension];
4555
				var valueMultiplied = value * this.multiplier;
4556
				var valueQuantized1 = Math.floor(valueMultiplied);
4557
				var valueQuantized2 = Math.ceil(valueMultiplied);
4558
				CSG.fuzzyFactory.insertKey(key, elementLookupTable, valueQuantized1);
4559
				CSG.fuzzyFactory.insertKey(key, elementLookupTable, valueQuantized2);
4560
			}
4561
		} else {
4562
			object = this.objectTable[key];
4563
		}
4564
		return object;
4565
	},
4566

4567
	// ----------- PRIVATE METHODS:
4568
	lookupKey: function(els) {
4569
		var keyset = {};
4570
		for(var dimension = 0; dimension < els.length; dimension++) {
4571
			var elementLookupTable = this.lookuptable[dimension];
4572
			var value = els[dimension];
4573
			var valueQuantized = Math.round(value * this.multiplier);
4574
			valueQuantized += "";
4575
			if(valueQuantized in elementLookupTable) {
4576
				if(dimension === 0) {
4577
					keyset = elementLookupTable[valueQuantized];
4578
				} else {
4579
					keyset = CSG.fuzzyFactory.intersectSets(keyset, elementLookupTable[valueQuantized]);
4580
				}
4581
			} else {
4582
				return null;
4583
			}
4584
			if(CSG.fuzzyFactory.isEmptySet(keyset)) return null;
4585
		}
4586
		// return first matching key:
4587
		for(var key in keyset) return key;
4588
		return null;
4589
	},
4590

4591
	lookupKeySetForDimension: function(dimension, value) {
4592
		var result;
4593
		var elementLookupTable = this.lookuptable[dimension];
4594
		var valueMultiplied = value * this.multiplier;
4595
		var valueQuantized = Math.floor(value * this.multiplier);
4596
		if(valueQuantized in elementLookupTable) {
4597
			result = elementLookupTable[valueQuantized];
4598
		} else {
4599
			result = {};
4600
		}
4601
		return result;
4602
	}
4603
};
4604

4605
CSG.fuzzyFactory.insertKey = function(key, lookuptable, quantizedvalue) {
4606
	if(quantizedvalue in lookuptable) {
4607
		lookuptable[quantizedvalue][key] = true;
4608
	} else {
4609
		var newset = {};
4610
		newset[key] = true;
4611
		lookuptable[quantizedvalue] = newset;
4612
	}
4613
};
4614

4615
CSG.fuzzyFactory.isEmptySet = function(obj) {
4616
	for(var key in obj) return false;
4617
	return true;
4618
};
4619

4620
CSG.fuzzyFactory.intersectSets = function(set1, set2) {
4621
	var result = {};
4622
	for(var key in set1) {
4623
		if(key in set2) {
4624
			result[key] = true;
4625
		}
4626
	}
4627
	return result;
4628
};
4629

4630
CSG.fuzzyFactory.joinSets = function(set1, set2) {
4631
	var result = {}, key;
4632
	for(key in set1) {
4633
		result[key] = true;
4634
	}
4635
	for(key in set2) {
4636
		result[key] = true;
4637
	}
4638
	return result;
4639
};
4640

4641
//////////////////////////////////////
4642
CSG.fuzzyCSGFactory = function() {
4643
	this.vertexfactory = new CSG.fuzzyFactory(3, 1e-5);
4644
	this.planefactory = new CSG.fuzzyFactory(4, 1e-5);
4645
	this.polygonsharedfactory = {};
4646
};
4647

4648
CSG.fuzzyCSGFactory.prototype = {
4649
	getPolygonShared: function(sourceshared) {
4650
		var hash = sourceshared.getHash();
4651
		if(hash in this.polygonsharedfactory) {
4652
			return this.polygonsharedfactory[hash];
4653
		} else {
4654
			this.polygonsharedfactory[hash] = sourceshared;
4655
			return sourceshared;
4656
		}
4657
	},
4658

4659
	getVertex: function(sourcevertex) {
4660
		var elements = [sourcevertex.pos._x, sourcevertex.pos._y, sourcevertex.pos._z];
4661
		var result = this.vertexfactory.lookupOrCreate(elements, function(els) {
4662
			return sourcevertex;
4663
		});
4664
		return result;
4665
	},
4666

4667
	getPlane: function(sourceplane) {
4668
		var elements = [sourceplane.normal._x, sourceplane.normal._y, sourceplane.normal._z, sourceplane.w];
4669
		var result = this.planefactory.lookupOrCreate(elements, function(els) {
4670
			return sourceplane;
4671
		});
4672
		return result;
4673
	},
4674

4675
	getPolygon: function(sourcepolygon) {
4676
		var newplane = this.getPlane(sourcepolygon.plane);
4677
		var newshared = this.getPolygonShared(sourcepolygon.shared);
4678
		var _this = this;
4679
		var newvertices = sourcepolygon.vertices.map(function(vertex) {
4680
			return _this.getVertex(vertex);
4681
		});
4682
		return new CSG.Polygon(newvertices, newshared, newplane);
4683
	},
4684

4685
	getCSG: function(sourcecsg) {
4686
		var _this = this;
4687
		var newpolygons = sourcecsg.polygons.map(function(polygon) {
4688
			return _this.getPolygon(polygon);
4689
		});
4690
		return CSG.fromPolygons(newpolygons);
4691
	}
4692
};
4693

4694
//////////////////////////////////////
4695
// Tag factory: we can request a unique tag through CSG.getTag()
4696
CSG.staticTag = 1;
4697

4698
CSG.getTag = function() {
4699
	return CSG.staticTag++;
4700
};
4701

4702
//////////////////////////////////////
4703
// # Class Properties
4704
// This class is used to store properties of a solid
4705
// A property can for example be a CSG.Vertex, a CSG.Plane or a CSG.Line3D
4706
// Whenever an affine transform is applied to the CSG solid, all its properties are
4707
// transformed as well.
4708
// The properties can be stored in a complex nested structure (using arrays and objects)
4709
CSG.Properties = function() {};
4710

4711
CSG.Properties.prototype = {
4712
	_transform: function(matrix4x4) {
4713
		var result = new CSG.Properties();
4714
		CSG.Properties.transformObj(this, result, matrix4x4);
4715
		return result;
4716
	},
4717
	_merge: function(otherproperties) {
4718
		var result = new CSG.Properties();
4719
		CSG.Properties.cloneObj(this, result);
4720
		CSG.Properties.addFrom(result, otherproperties);
4721
		return result;
4722
	}
4723
};
4724

4725
CSG.Properties.transformObj = function(source, result, matrix4x4) {
4726
	for(var propertyname in source) {
4727
		if(propertyname == "_transform") continue;
4728
		if(propertyname == "_merge") continue;
4729
		var propertyvalue = source[propertyname];
4730
		var transformed = propertyvalue;
4731
		if(typeof(propertyvalue) == "object") {
4732
			if(('transform' in propertyvalue) && (typeof(propertyvalue.transform) == "function")) {
4733
				transformed = propertyvalue.transform(matrix4x4);
4734
			} else if(propertyvalue instanceof Array) {
4735
				transformed = [];
4736
				CSG.Properties.transformObj(propertyvalue, transformed, matrix4x4);
4737
			} else if(propertyvalue instanceof CSG.Properties) {
4738
				transformed = new CSG.Properties();
4739
				CSG.Properties.transformObj(propertyvalue, transformed, matrix4x4);
4740
			}
4741
		}
4742
		result[propertyname] = transformed;
4743
	}
4744
};
4745

4746
CSG.Properties.cloneObj = function(source, result) {
4747
	for(var propertyname in source) {
4748
		if(propertyname == "_transform") continue;
4749
		if(propertyname == "_merge") continue;
4750
		var propertyvalue = source[propertyname];
4751
		var cloned = propertyvalue;
4752
		if(typeof(propertyvalue) == "object") {
4753
			if(propertyvalue instanceof Array) {
4754
				cloned = [];
4755
				for(var i = 0; i < propertyvalue.length; i++) {
4756
					cloned.push(propertyvalue[i]);
4757
				}
4758
			} else if(propertyvalue instanceof CSG.Properties) {
4759
				cloned = new CSG.Properties();
4760
				CSG.Properties.cloneObj(propertyvalue, cloned);
4761
			}
4762
		}
4763
		result[propertyname] = cloned;
4764
	}
4765
};
4766

4767
CSG.Properties.addFrom = function(result, otherproperties) {
4768
	for(var propertyname in otherproperties) {
4769
		if(propertyname == "_transform") continue;
4770
		if(propertyname == "_merge") continue;
4771
		if((propertyname in result) &&
4772
				(typeof(result[propertyname]) == "object") &&
4773
				(result[propertyname] instanceof CSG.Properties) &&
4774
				(typeof(otherproperties[propertyname]) == "object") &&
4775
				(otherproperties[propertyname] instanceof CSG.Properties)) {
4776
			CSG.Properties.addFrom(result[propertyname], otherproperties[propertyname]);
4777
		} else if(!(propertyname in result)) {
4778
			result[propertyname] = otherproperties[propertyname];
4779
		}
4780
	}
4781
};
4782

4783
//////////////////////////////////////
4784
// # class Connector
4785
// A connector allows to attach two objects at predefined positions
4786
// For example a servo motor and a servo horn:
4787
// Both can have a Connector called 'shaft'
4788
// The horn can be moved and rotated such that the two connectors match
4789
// and the horn is attached to the servo motor at the proper position.
4790
// Connectors are stored in the properties of a CSG solid so they are
4791
// ge the same transformations applied as the solid
4792
CSG.Connector = function(point, axisvector, normalvector) {
4793
	this.point = new CSG.Vector3D(point);
4794
	this.axisvector = new CSG.Vector3D(axisvector).unit();
4795
	this.normalvector = new CSG.Vector3D(normalvector).unit();
4796
};
4797

4798
CSG.Connector.prototype = {
4799
	normalized: function() {
4800
		var axisvector = this.axisvector.unit();
4801
		// make the normal vector truly normal:
4802
		var n = this.normalvector.cross(axisvector).unit();
4803
		var normalvector = axisvector.cross(n);
4804
		return new CSG.Connector(this.point, axisvector, normalvector);
4805
	},
4806

4807
	transform: function(matrix4x4) {
4808
		var point = this.point.multiply4x4(matrix4x4);
4809
		var axisvector = this.point.plus(this.axisvector).multiply4x4(matrix4x4).minus(point);
4810
		var normalvector = this.point.plus(this.normalvector).multiply4x4(matrix4x4).minus(point);
4811
		return new CSG.Connector(point, axisvector, normalvector);
4812
	},
4813

4814
	// Get the transformation matrix to connect this Connector to another connector
4815
	//   other: a CSG.Connector to which this connector should be connected
4816
	//   mirror: false: the 'axis' vectors of the connectors should point in the same direction
4817
	//           true: the 'axis' vectors of the connectors should point in opposite direction
4818
	//   normalrotation: degrees of rotation between the 'normal' vectors of the two
4819
	//                   connectors
4820
	getTransformationTo: function(other, mirror, normalrotation) {
4821
		mirror = mirror ? true : false;
4822
		normalrotation = normalrotation ? Number(normalrotation) : 0;
4823
		var us = this.normalized();
4824
		other = other.normalized();
4825
		// shift to the origin:
4826
		var transformation = CSG.Matrix4x4.translation(this.point.negated());
4827
		// construct the plane crossing through the origin and the two axes:
4828
		var axesplane = CSG.Plane.anyPlaneFromVector3Ds(
4829
		new CSG.Vector3D(0, 0, 0), us.axisvector, other.axisvector);
4830
		var axesbasis = new CSG.OrthoNormalBasis(axesplane);
4831
		var angle1 = axesbasis.to2D(us.axisvector).angle();
4832
		var angle2 = axesbasis.to2D(other.axisvector).angle();
4833
		var rotation = 180.0 * (angle2 - angle1) / Math.PI;
4834
		if(mirror) rotation += 180.0;
4835
		transformation = transformation.multiply(axesbasis.getProjectionMatrix());
4836
		transformation = transformation.multiply(CSG.Matrix4x4.rotationZ(rotation));
4837
		transformation = transformation.multiply(axesbasis.getInverseProjectionMatrix());
4838
		var usAxesAligned = us.transform(transformation);
4839
		// Now we have done the transformation for aligning the axes.
4840
		// We still need to align the normals:
4841
		var normalsplane = CSG.Plane.fromNormalAndPoint(other.axisvector, new CSG.Vector3D(0, 0, 0));
4842
		var normalsbasis = new CSG.OrthoNormalBasis(normalsplane);
4843
		angle1 = normalsbasis.to2D(usAxesAligned.normalvector).angle();
4844
		angle2 = normalsbasis.to2D(other.normalvector).angle();
4845
		rotation = 180.0 * (angle2 - angle1) / Math.PI;
4846
		rotation += normalrotation;
4847
		transformation = transformation.multiply(normalsbasis.getProjectionMatrix());
4848
		transformation = transformation.multiply(CSG.Matrix4x4.rotationZ(rotation));
4849
		transformation = transformation.multiply(normalsbasis.getInverseProjectionMatrix());
4850
		// and translate to the destination point:
4851
		transformation = transformation.multiply(CSG.Matrix4x4.translation(other.point));
4852
		var usAligned = us.transform(transformation);
4853
		return transformation;
4854
	},
4855

4856
	axisLine: function() {
4857
		return new CSG.Line3D(this.point, this.axisvector);
4858
	},
4859

4860
	// creates a new Connector, with the connection point moved in the direction of the axisvector
4861
	extend: function(distance) {
4862
		var newpoint = this.point.plus(this.axisvector.unit().times(distance));
4863
		return new CSG.Connector(newpoint, this.axisvector, this.normalvector);
4864
	}
4865
};
4866

4867

4868
//////////////////////////////////////
4869
// # Class Path2D
4870
CSG.Path2D = function(points, closed) {
4871
	closed = !! closed;
4872
	points = points || [];
4873
	// re-parse the points into CSG.Vector2D
4874
	// and remove any duplicate points
4875
	var prevpoint = null;
4876
	if(closed && (points.length > 0)) {
4877
		prevpoint = new CSG.Vector2D(points[points.length - 1]);
4878
	}
4879
	var newpoints = [];
4880
	points.map(function(point) {
4881
		point = new CSG.Vector2D(point);
4882
		var skip = false;
4883
		if(prevpoint !== null) {
4884
			var distance = point.distanceTo(prevpoint);
4885
			skip = distance < 1e-5;
4886
		}
4887
		if(!skip) newpoints.push(point);
4888
		prevpoint = point;
4889
	});
4890
	this.points = newpoints;
4891
	this.closed = closed;
4892
};
4893

4894
/*
4895
Construct a (part of a) circle. Parameters:
4896
  options.center: the center point of the arc (CSG.Vector2D or array [x,y])
4897
  options.radius: the circle radius (float)
4898
  options.startangle: the starting angle of the arc, in degrees
4899
	0 degrees corresponds to [1,0]
4900
	90 degrees to [0,1]
4901
	and so on
4902
  options.endangle: the ending angle of the arc, in degrees
4903
  options.resolution: number of points per 360 degree of rotation
4904
  options.maketangent: adds two extra tiny line segments at both ends of the circle
4905
	this ensures that the gradients at the edges are tangent to the circle
4906
Returns a CSG.Path2D. The path is not closed (even if it is a 360 degree arc).
4907
close() the resultin path if you want to create a true circle.
4908
*/
4909
CSG.Path2D.arc = function(options) {
4910
	var center = CSG.parseOptionAs2DVector(options, "center", 0);
4911
	var radius = CSG.parseOptionAsFloat(options, "radius", 1);
4912
	var startangle = CSG.parseOptionAsFloat(options, "startangle", 0);
4913
	var endangle = CSG.parseOptionAsFloat(options, "endangle", 360);
4914
	var resolution = CSG.parseOptionAsFloat(options, "resolution", CSG.defaultResolution2D);
4915
	var maketangent = CSG.parseOptionAsBool(options, "maketangent", false);
4916
	// no need to make multiple turns:
4917
	while(endangle - startangle >= 720) {
4918
		endangle -= 360;
4919
	}
4920
	while(endangle - startangle <= -720) {
4921
		endangle += 360;
4922
	}
4923
	var points = [], point;
4924
	var absangledif = Math.abs(endangle - startangle);
4925
	if(absangledif < 1e-5) {
4926
		point = CSG.Vector2D.fromAngle(startangle / 180.0 * Math.PI).times(radius);
4927
		points.push(point.plus(center));
4928
	} else {
4929
		var numsteps = Math.floor(resolution * absangledif / 360) + 1;
4930
		var edgestepsize = numsteps * 0.5 / absangledif; // step size for half a degree
4931
		if(edgestepsize > 0.25) edgestepsize = 0.25;
4932
		var numsteps_mod = maketangent ? (numsteps + 2) : numsteps;
4933
		for(var i = 0; i <= numsteps_mod; i++) {
4934
			var step = i;
4935
			if(maketangent) {
4936
				step = (i - 1) * (numsteps - 2 * edgestepsize) / numsteps + edgestepsize;
4937
				if(step < 0) step = 0;
4938
				if(step > numsteps) step = numsteps;
4939
			}
4940
			var angle = startangle + step * (endangle - startangle) / numsteps;
4941
			point = CSG.Vector2D.fromAngle(angle / 180.0 * Math.PI).times(radius);
4942
			points.push(point.plus(center));
4943
		}
4944
	}
4945
	return new CSG.Path2D(points, false);
4946
};
4947

4948
CSG.Path2D.prototype = {
4949
	concat: function(otherpath) {
4950
		if(this.closed || otherpath.closed) {
4951
			throw new Error("Paths must not be closed");
4952
		}
4953
		var newpoints = this.points.concat(otherpath.points);
4954
		return new CSG.Path2D(newpoints);
4955
	},
4956

4957
	appendPoint: function(point) {
4958
		if(this.closed) {
4959
			throw new Error("Paths must not be closed");
4960
		}
4961
		var newpoints = this.points.concat([point]);
4962
		return new CSG.Path2D(newpoints);
4963
	},
4964

4965
	close: function() {
4966
		return new CSG.Path2D(this.points, true);
4967
	},
4968

4969
	// Extrude the path by following it with a rectangle (upright, perpendicular to the path direction)
4970
	// Returns a CSG solid
4971
	//   width: width of the extrusion, in the z=0 plane
4972
	//   height: height of the extrusion in the z direction
4973
	//   resolution: number of segments per 360 degrees for the curve in a corner
4974
	rectangularExtrude: function(width, height, resolution) {
4975
		var cag = this.expandToCAG(width / 2, resolution);
4976
		var result = cag.extrude({
4977
			offset: [0, 0, height]
4978
		});
4979
		return result;
4980
	},
4981

4982
	// Expand the path to a CAG
4983
	// This traces the path with a circle with radius pathradius
4984
	expandToCAG: function(pathradius, resolution) {
4985
		var sides = [];
4986
		var numpoints = this.points.length;
4987
		var startindex = 0;
4988
		if(this.closed && (numpoints > 2)) startindex = -1;
4989
		var prevvertex;
4990
		for(var i = startindex; i < numpoints; i++) {
4991
			var pointindex = i;
4992
			if(pointindex < 0) pointindex = numpoints - 1;
4993
			var point = this.points[pointindex];
4994
			var vertex = new CAG.Vertex(point);
4995
			if(i > startindex) {
4996
				var side = new CAG.Side(prevvertex, vertex);
4997
				sides.push(side);
4998
			}
4999
			prevvertex = vertex;
5000
		}
5001
		var shellcag = CAG.fromSides(sides);
5002
		var expanded = shellcag.expandedShell(pathradius, resolution);
5003
		return expanded;
5004
	},
5005

5006
	innerToCAG: function() {
5007
		if(!this.closed) throw new Error("The path should be closed!");
5008
		return CAG.fromPoints(this.points);
5009
	},
5010

5011
	transform: function(matrix4x4) {
5012
		var newpoints = this.points.map(function(point) {
5013
			return point.multiply4x4(matrix4x4);
5014
		});
5015
		return new CSG.Path2D(newpoints, this.closed);
5016
	}
5017
};
5018

5019
// Add several convenience methods to the classes that support a transform() method:
5020
CSG.addTransformationMethodsToPrototype = function(prot) {
5021
	prot.mirrored = function(plane) {
5022
		return this.transform(CSG.Matrix4x4.mirroring(plane));
5023
	};
5024

5025
	prot.mirroredX = function() {
5026
		var plane = new CSG.Plane(new CSG.Vector3D(1, 0, 0), 0);
5027
		return this.mirrored(plane);
5028
	};
5029

5030
	prot.mirroredY = function() {
5031
		var plane = new CSG.Plane(new CSG.Vector3D(0, 1, 0), 0);
5032
		return this.mirrored(plane);
5033
	};
5034

5035
	prot.mirroredZ = function() {
5036
		var plane = new CSG.Plane(new CSG.Vector3D(0, 0, 1), 0);
5037
		return this.mirrored(plane);
5038
	};
5039

5040
	prot.translate = function(v) {
5041
		return this.transform(CSG.Matrix4x4.translation(v));
5042
	};
5043

5044
	prot.scale = function(f) {
5045
		return this.transform(CSG.Matrix4x4.scaling(f));
5046
	};
5047

5048
	prot.rotateX = function(deg) {
5049
		return this.transform(CSG.Matrix4x4.rotationX(deg));
5050
	};
5051

5052
	prot.rotateY = function(deg) {
5053
		return this.transform(CSG.Matrix4x4.rotationY(deg));
5054
	};
5055

5056
	prot.rotateZ = function(deg) {
5057
		return this.transform(CSG.Matrix4x4.rotationZ(deg));
5058
	};
5059

5060
	prot.rotate = function(rotationCenter, rotationAxis, degrees) {
5061
		return this.transform(CSG.Matrix4x4.rotation(rotationCenter, rotationAxis, degrees));
5062
	};
5063
};
5064

5065
//////////////////
5066
// CAG: solid area geometry: like CSG but 2D
5067
// Each area consists of a number of sides
5068
// Each side is a line between 2 points
5069
var CAG = function() {
5070
	this.sides = [];
5071
};
5072

5073
// Construct a CAG from a list of `CAG.Side` instances.
5074
CAG.fromSides = function(sides) {
5075
	var cag = new CAG();
5076
	cag.sides = sides;
5077
	return cag;
5078
};
5079

5080
// Construct a CAG from a list of points (a polygon)
5081
// Rotation direction of the points is not relevant. Points can be a convex or concave polygon.
5082
// Polygon must not self intersect
5083
CAG.fromPoints = function(points) {
5084
	var numpoints = points.length;
5085
	if(numpoints < 3) throw new Error("CAG shape needs at least 3 points");
5086
	var sides = [];
5087
	var prevpoint = new CSG.Vector2D(points[numpoints - 1]);
5088
	var prevvertex = new CAG.Vertex(prevpoint);
5089
	points.map(function(p) {
5090
		var point = new CSG.Vector2D(p);
5091
		var vertex = new CAG.Vertex(point);
5092
		var side = new CAG.Side(prevvertex, vertex);
5093
		sides.push(side);
5094
		prevvertex = vertex;
5095
	});
5096
	var result = CAG.fromSides(sides);
5097
	if(result.isSelfIntersecting()) {
5098
		throw new Error("Polygon is self intersecting!");
5099
	}
5100
	var area = result.area();
5101
	if(Math.abs(area) < 1e-5) {
5102
		throw new Error("Degenerate polygon!");
5103
	}
5104
	if(area < 0) {
5105
		result = result.flipped();
5106
	}
5107
	result = result.canonicalized();
5108
	return result;
5109
};
5110

5111
// Like CAG.fromPoints but does not check if it's a valid polygon.
5112
// Points should rotate counter clockwise
5113
CAG.fromPointsNoCheck = function(points) {
5114
	var sides = [];
5115
	var prevpoint = new CSG.Vector2D(points[points.length - 1]);
5116
	var prevvertex = new CAG.Vertex(prevpoint);
5117
	points.map(function(p) {
5118
		var point = new CSG.Vector2D(p);
5119
		var vertex = new CAG.Vertex(point);
5120
		var side = new CAG.Side(prevvertex, vertex);
5121
		sides.push(side);
5122
		prevvertex = vertex;
5123
	});
5124
	return CAG.fromSides(sides);
5125
};
5126

5127
// Converts a CSG to a CAG. The CSG must consist of polygons with only z coordinates +1 and -1
5128
// as constructed by CAG.toCSG(-1, 1). This is so we can use the 3D union(), intersect() etc
5129
CAG.fromFakeCSG = function(csg) {
5130
	var sides = csg.polygons.map(function(p) {
5131
		return CAG.Side.fromFakePolygon(p);
5132
	});
5133
	return CAG.fromSides(sides);
5134
};
5135

5136
// see if the line between p0start and p0end intersects with the line between p1start and p1end
5137
// returns true if the lines strictly intersect, the end points are not counted!
5138
CAG.linesIntersect = function(p0start, p0end, p1start, p1end) {
5139
	if(p0end.equals(p1start) || p1end.equals(p0start)) {
5140
		var d = p1end.minus(p1start).unit().plus(p0end.minus(p0start).unit()).length();
5141
		if(d < 1e-5) {
5142
			return true;
5143
		}
5144
	} else {
5145
		var d0 = p0end.minus(p0start);
5146
		var d1 = p1end.minus(p1start);
5147
		if(Math.abs(d0.cross(d1)) < 1e-9) return false; // lines are parallel
5148
		var alphas = CSG.solve2Linear(-d0.x, d1.x, -d0.y, d1.y, p0start.x - p1start.x, p0start.y - p1start.y);
5149
		if((alphas[0] > 1e-6) && (alphas[0] < 0.999999) && (alphas[1] > 1e-5) && (alphas[1] < 0.999999)) return true;
5150
		//    if( (alphas[0] >= 0) && (alphas[0] <= 1) && (alphas[1] >= 0) && (alphas[1] <= 1) ) return true;
5151
	}
5152
	return false;
5153
};
5154

5155
/* Construct a circle
5156
   options:
5157
	 center: a 2D center point
5158
	 radius: a scalar
5159
	 resolution: number of sides per 360 degree rotation
5160
   returns a CAG object
5161
*/
5162
CAG.circle = function(options) {
5163
	options = options || {};
5164
	var center = CSG.parseOptionAs2DVector(options, "center", [0, 0]);
5165
	var radius = CSG.parseOptionAsFloat(options, "radius", 1);
5166
	var resolution = CSG.parseOptionAsInt(options, "resolution", CSG.defaultResolution2D);
5167
	var sides = [];
5168
	var prevvertex;
5169
	for(var i = 0; i <= resolution; i++) {
5170
		var radians = 2 * Math.PI * i / resolution;
5171
		var point = CSG.Vector2D.fromAngleRadians(radians).times(radius).plus(center);
5172
		var vertex = new CAG.Vertex(point);
5173
		if(i > 0) {
5174
			sides.push(new CAG.Side(prevvertex, vertex));
5175
		}
5176
		prevvertex = vertex;
5177
	}
5178
	return CAG.fromSides(sides);
5179
};
5180

5181
/* Construct a rectangle
5182
   options:
5183
	 center: a 2D center point
5184
	 radius: a 2D vector with width and height
5185
   returns a CAG object
5186
*/
5187
CAG.rectangle = function(options) {
5188
	options = options || {};
5189
	var c = CSG.parseOptionAs2DVector(options, "center", [0, 0]);
5190
	var r = CSG.parseOptionAs2DVector(options, "radius", [1, 1]);
5191
	var rswap = new CSG.Vector2D(r.x, -r.y);
5192
	var points = [
5193
	c.plus(r), c.plus(rswap), c.minus(r), c.minus(rswap)];
5194
	return CAG.fromPoints(points);
5195
};
5196

5197
//     var r = CSG.roundedRectangle({
5198
//       center: [0, 0],
5199
//       radius: [2, 1],
5200
//       roundradius: 0.2,
5201
//       resolution: 8,
5202
//     });
5203
CAG.roundedRectangle = function(options) {
5204
	options = options || {};
5205
	var center = CSG.parseOptionAs2DVector(options, "center", [0, 0]);
5206
	var radius = CSG.parseOptionAs2DVector(options, "radius", [1, 1]);
5207
	var roundradius = CSG.parseOptionAsFloat(options, "roundradius", 0.2);
5208
	var resolution = CSG.parseOptionAsFloat(options, "resolution", CSG.defaultResolution2D);
5209
	var maxroundradius = Math.min(radius.x, radius.y);
5210
	maxroundradius -= 0.1;
5211
	roundradius = Math.min(roundradius, maxroundradius);
5212
	roundradius = Math.max(0, roundradius);
5213
	radius = new CSG.Vector2D(radius.x - roundradius, radius.y - roundradius);
5214
	var rect = CAG.rectangle({
5215
		center: center,
5216
		radius: radius
5217
	});
5218
	if(roundradius > 0) {
5219
		rect = rect.expand(roundradius, resolution);
5220
	}
5221
	return rect;
5222
};
5223

5224
// Reconstruct a CAG from the output of toCompactBinary()
5225
CAG.fromCompactBinary = function(bin) {
5226
	if(bin['class'] != "CAG") throw new Error("Not a CAG");
5227
	var vertices = [];
5228
	var vertexData = bin.vertexData;
5229
	var numvertices = vertexData.length / 2;
5230
	var arrayindex = 0;
5231
	for(var vertexindex = 0; vertexindex < numvertices; vertexindex++) {
5232
		var x = vertexData[arrayindex++];
5233
		var y = vertexData[arrayindex++];
5234
		var pos = new CSG.Vector2D(x, y);
5235
		var vertex = new CAG.Vertex(pos);
5236
		vertices.push(vertex);
5237
	}
5238

5239
	var sides = [];
5240
	var numsides = bin.sideVertexIndices.length / 2;
5241
	arrayindex = 0;
5242
	for(var sideindex = 0; sideindex < numsides; sideindex++) {
5243
		var vertexindex0 = bin.sideVertexIndices[arrayindex++];
5244
		var vertexindex1 = bin.sideVertexIndices[arrayindex++];
5245
		var side = new CAG.Side(vertices[vertexindex0], vertices[vertexindex1]);
5246
		sides.push(side);
5247
	}
5248
	var cag = CAG.fromSides(sides);
5249
	cag.isCanonicalized = true;
5250
	return cag;
5251
};
5252

5253
function fnSortByIndex(a, b) {
5254
	return a.index - b.index;
5255
}
5256

5257
CAG.prototype = {
5258
	toString: function() {
5259
		var result = "CAG (" + this.sides.length + " sides):\n";
5260
		this.sides.map(function(side) {
5261
			result += "  " + side.toString() + "\n";
5262
		});
5263
		return result;
5264
	},
5265

5266
	toCSG: function(z0, z1) {
5267
		var polygons = this.sides.map(function(side) {
5268
			return side.toPolygon3D(z0, z1);
5269
		});
5270
		return CSG.fromPolygons(polygons);
5271
	},
5272

5273
	toDebugString1: function() {
5274
		this.sides.sort(function(a, b) {
5275
			return a.vertex0.pos.x - b.vertex0.pos.x;
5276
		});
5277
		var str = "";
5278
		this.sides.map(function(side) {
5279
			str += "(" + side.vertex0.pos.x + "," + side.vertex0.pos.y + ") - (" + side.vertex1.pos.x + "," + side.vertex1.pos.y + ")\n";
5280
		});
5281
		return str;
5282
	},
5283

5284
	toDebugString: function() {
5285
		//    this.sides.sort(function(a,b){
5286
		//      return a.vertex0.pos.x - b.vertex0.pos.x;
5287
		//    });
5288
		var str = "CAG.fromSides([\n";
5289
		this.sides.map(function(side) {
5290
			str += "  new CAG.Side(new CAG.Vertex(new CSG.Vector2D(" +
5291
					side.vertex0.pos.x + "," + side.vertex0.pos.y +
5292
				")), new CAG.Vertex(new CSG.Vector2D(" +
5293
					side.vertex1.pos.x + "," + side.vertex1.pos.y + "))),\n";
5294
		});
5295
		str += "]);\n";
5296
		return str;
5297
	},
5298

5299
	union: function(cag) {
5300
		var cags;
5301
		if(cag instanceof Array) {
5302
			cags = cag;
5303
		} else {
5304
			cags = [cag];
5305
		}
5306
		var r = this.toCSG(-1, 1);
5307
		cags.map(function(cag) {
5308
			r = r.unionSub(cag.toCSG(-1, 1), false, false);
5309
		});
5310
		r = r.reTesselated();
5311
		r = r.canonicalized();
5312
		cag = CAG.fromFakeCSG(r);
5313
		var cag_canonicalized = cag.canonicalized();
5314
		return cag_canonicalized;
5315
	},
5316

5317
	subtract: function(cag) {
5318
		var cags;
5319
		if(cag instanceof Array) {
5320
			cags = cag;
5321
		} else {
5322
			cags = [cag];
5323
		}
5324
		var r = this.toCSG(-1, 1);
5325
		cags.map(function(cag) {
5326
			r = r.subtractSub(cag.toCSG(-1, 1), false, false);
5327
		});
5328
		r = r.reTesselated();
5329
		r = r.canonicalized();
5330
		r = CAG.fromFakeCSG(r);
5331
		r = r.canonicalized();
5332
		return r;
5333
	},
5334

5335
	intersect: function(cag) {
5336
		var cags;
5337
		if(cag instanceof Array) {
5338
			cags = cag;
5339
		} else {
5340
			cags = [cag];
5341
		}
5342
		var r = this.toCSG(-1, 1);
5343
		cags.map(function(cag) {
5344
			r = r.intersectSub(cag.toCSG(-1, 1), false, false);
5345
		});
5346
		r = r.reTesselated();
5347
		r = r.canonicalized();
5348
		r = CAG.fromFakeCSG(r);
5349
		r = r.canonicalized();
5350
		return r;
5351
	},
5352

5353
	transform: function(matrix4x4) {
5354
		var ismirror = matrix4x4.isMirroring();
5355
		var newsides = this.sides.map(function(side) {
5356
			return side.transform(matrix4x4);
5357
		});
5358
		var result = CAG.fromSides(newsides);
5359
		if(ismirror) {
5360
			result = result.flipped();
5361
		}
5362
		return result;
5363
	},
5364

5365
	// see http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/ :
5366
	// Area of the polygon. For a counter clockwise rotating polygon the area is positive, otherwise negative
5367
	area: function() {
5368
		var polygonArea = 0;
5369
		this.sides.map(function(side) {
5370
			polygonArea += side.vertex0.pos.cross(side.vertex1.pos);
5371
		});
5372
		polygonArea *= 0.5;
5373
		return polygonArea;
5374
	},
5375

5376
	flipped: function() {
5377
		var newsides = this.sides.map(function(side) {
5378
			return side.flipped();
5379
		});
5380
		newsides.reverse();
5381
		return CAG.fromSides(newsides);
5382
	},
5383

5384
	getBounds: function() {
5385
		var minpoint;
5386
		if(this.sides.length === 0) {
5387
			minpoint = new CSG.Vector2D(0, 0);
5388
		} else {
5389
			minpoint = this.sides[0].vertex0.pos;
5390
		}
5391
		var maxpoint = minpoint;
5392
		this.sides.map(function(side) {
5393
			minpoint = minpoint.min(side.vertex0.pos);
5394
			minpoint = minpoint.min(side.vertex1.pos);
5395
			maxpoint = maxpoint.max(side.vertex0.pos);
5396
			maxpoint = maxpoint.max(side.vertex1.pos);
5397
		});
5398
		return [minpoint, maxpoint];
5399
	},
5400

5401
   center: function(c) {
5402
      if(!c.length) c = [c,c];
5403
      var b = this.getBounds();
5404
      return this.translate([
5405
         c[0]?-(b[1].x-b[0].x)/2-b[0].x:0,
5406
         c[1]?-(b[1].y-b[0].y)/2-b[0].y:0]);
5407
   },
5408

5409
	isSelfIntersecting: function() {
5410
		var numsides = this.sides.length;
5411
		for(var i = 0; i < numsides; i++) {
5412
			var side0 = this.sides[i];
5413
			for(var ii = i + 1; ii < numsides; ii++) {
5414
				var side1 = this.sides[ii];
5415
				if(CAG.linesIntersect(side0.vertex0.pos, side0.vertex1.pos, side1.vertex0.pos, side1.vertex1.pos)) {
5416
					return true;
5417
				}
5418
			}
5419
		}
5420
		return false;
5421
	},
5422

5423
	expandedShell: function(radius, resolution) {
5424
		resolution = resolution || 8;
5425
		if(resolution < 4) resolution = 4;
5426
		var cags = [];
5427
		var pointmap = {};
5428
		var cag = this.canonicalized();
5429
		cag.sides.map(function(side) {
5430
			var d = side.vertex1.pos.minus(side.vertex0.pos);
5431
			var dl = d.length();
5432
			if(dl > 1e-5) {
5433
				d = d.times(1.0 / dl);
5434
				var normal = d.normal().times(radius);
5435
				var shellpoints = [
5436
					side.vertex1.pos.plus(normal),
5437
					side.vertex1.pos.minus(normal),
5438
					side.vertex0.pos.minus(normal),
5439
					side.vertex0.pos.plus(normal)
5440
				];
5441
				//      var newcag = CAG.fromPointsNoCheck(shellpoints);
5442
				var newcag = CAG.fromPoints(shellpoints);
5443
				cags.push(newcag);
5444
				for(var step = 0; step < 2; step++) {
5445
					var p1 = (step === 0) ? side.vertex0.pos : side.vertex1.pos;
5446
					var p2 = (step === 0) ? side.vertex1.pos : side.vertex0.pos;
5447
					var tag = p1.x + " " + p1.y;
5448
					if(!(tag in pointmap)) {
5449
						pointmap[tag] = [];
5450
					}
5451
					pointmap[tag].push({
5452
						"p1": p1,
5453
						"p2": p2
5454
					});
5455
				}
5456
			}
5457
		});
5458
		for(var tag in pointmap) {
5459
			var m = pointmap[tag];
5460
			var angle1, angle2;
5461
			var pcenter = m[0].p1;
5462
			if(m.length == 2) {
5463
				var end1 = m[0].p2;
5464
				var end2 = m[1].p2;
5465
				angle1 = end1.minus(pcenter).angleDegrees();
5466
				angle2 = end2.minus(pcenter).angleDegrees();
5467
				if(angle2 < angle1) angle2 += 360;
5468
				if(angle2 >= (angle1 + 360)) angle2 -= 360;
5469
				if(angle2 < angle1 + 180) {
5470
					var t = angle2;
5471
					angle2 = angle1 + 360;
5472
					angle1 = t;
5473
				}
5474
				angle1 += 90;
5475
				angle2 -= 90;
5476
			} else {
5477
				angle1 = 0;
5478
				angle2 = 360;
5479
			}
5480
			var fullcircle = (angle2 > angle1 + 359.999);
5481
			if(fullcircle) {
5482
				angle1 = 0;
5483
				angle2 = 360;
5484
			}
5485
			if(angle2 > (angle1 + 1e-5)) {
5486
				var points = [];
5487
				if(!fullcircle) {
5488
					points.push(pcenter);
5489
				}
5490
				var numsteps = Math.round(resolution * (angle2 - angle1) / 360);
5491
				if(numsteps < 1) numsteps = 1;
5492
				for(var step = 0; step <= numsteps; step++) {
5493
					var angle = angle1 + step / numsteps * (angle2 - angle1);
5494
					if(step == numsteps) angle = angle2; // prevent rounding errors
5495
					var point = pcenter.plus(CSG.Vector2D.fromAngleDegrees(angle).times(radius));
5496
					if((!fullcircle) || (step > 0)) {
5497
						points.push(point);
5498
					}
5499
				}
5500
				var newcag = CAG.fromPointsNoCheck(points);
5501
				cags.push(newcag);
5502
			}
5503
		}
5504
		var result = new CAG();
5505
		result = result.union(cags);
5506
		return result;
5507
	},
5508

5509
	expand: function(radius, resolution) {
5510
		var result = this.union(this.expandedShell(radius, resolution));
5511
		return result;
5512
	},
5513

5514
	contract: function(radius, resolution) {
5515
		var result = this.subtract(this.expandedShell(radius, resolution));
5516
		return result;
5517
	},
5518

5519
	// extruded=cag.extrude({offset: [0,0,10], twistangle: 360, twiststeps: 100});
5520
	// linear extrusion of 2D shape, with optional twist
5521
	// The 2d shape is placed in in z=0 plane and extruded into direction <offset> (a CSG.Vector3D)
5522
	// The final face is rotated <twistangle> degrees. Rotation is done around the origin of the 2d shape (i.e. x=0, y=0)
5523
	// twiststeps determines the resolution of the twist (should be >= 1)
5524
	// returns a CSG object
5525
	extrude: function(options) {
5526
		if(this.sides.length == 0) {
5527
		// empty!
5528
		return new CSG();
5529
	}
5530
	var offsetvector = CSG.parseOptionAs3DVector(options, "offset", [0,0,1]);
5531
	var twistangle = CSG.parseOptionAsFloat(options, "twistangle", 0);
5532
	var twiststeps = CSG.parseOptionAsInt(options, "twiststeps", 10);
5533

5534
	if(twistangle == 0) twiststeps = 1;
5535
	if(twiststeps < 1) twiststeps = 1;
5536

5537
	var newpolygons = [];
5538
	var prevtransformedcag;
5539
	var prevstepz;
5540
	for(var step=0; step <= twiststeps; step++) {
5541
		var stepfraction = step / twiststeps;
5542
		var transformedcag = this;
5543
		var angle = twistangle * stepfraction;
5544
		if(angle != 0) {
5545
			transformedcag = transformedcag.rotateZ(angle);
5546
		}
5547
		var translatevector = new CSG.Vector2D(offsetvector.x, offsetvector.y).times(stepfraction);
5548
		transformedcag = transformedcag.translate(translatevector);
5549
		var bounds = transformedcag.getBounds();
5550
		bounds[0] = bounds[0].minus(new CSG.Vector2D(1,1));
5551
		bounds[1] = bounds[1].plus(new CSG.Vector2D(1,1));
5552
		var stepz = offsetvector.z * stepfraction;
5553
		if( (step == 0) || (step == twiststeps) ) {
5554
			// bottom or top face:
5555
			var csgshell = transformedcag.toCSG(stepz-1, stepz+1);
5556
			var csgplane = CSG.fromPolygons([new CSG.Polygon([
5557
				new CSG.Vertex(new CSG.Vector3D(bounds[0].x, bounds[0].y, stepz)),
5558
				new CSG.Vertex(new CSG.Vector3D(bounds[1].x, bounds[0].y, stepz)),
5559
				new CSG.Vertex(new CSG.Vector3D(bounds[1].x, bounds[1].y, stepz)),
5560
				new CSG.Vertex(new CSG.Vector3D(bounds[0].x, bounds[1].y, stepz))
5561
			])]);
5562
			var flip = (step == 0);
5563
			if(offsetvector.z < 0) flip = !flip;
5564
			if(flip) {
5565
				csgplane = csgplane.inverse();
5566
			}
5567
			csgplane = csgplane.intersect(csgshell);
5568
			// only keep the polygons in the z plane:
5569
			csgplane.polygons.map(function(polygon){
5570
				if(Math.abs(polygon.plane.normal.z) > 0.99) {
5571
					newpolygons.push(polygon);
5572
				}
5573
			});
5574
		}
5575
		if(step > 0) {
5576
			var numsides = transformedcag.sides.length;
5577
			for(var sideindex = 0; sideindex < numsides; sideindex++) {
5578
				var thisside = transformedcag.sides[sideindex];
5579
				var prevside = prevtransformedcag.sides[sideindex];
5580
				var p1 = new CSG.Polygon([
5581
					new CSG.Vertex(thisside.vertex1.pos.toVector3D(stepz)),
5582
					new CSG.Vertex(thisside.vertex0.pos.toVector3D(stepz)),
5583
					new CSG.Vertex(prevside.vertex0.pos.toVector3D(prevstepz))
5584
				]);
5585
				var p2 = new CSG.Polygon([
5586
					new CSG.Vertex(thisside.vertex1.pos.toVector3D(stepz)),
5587
					new CSG.Vertex(prevside.vertex0.pos.toVector3D(prevstepz)),
5588
					new CSG.Vertex(prevside.vertex1.pos.toVector3D(prevstepz))
5589
				]);
5590
				if(offsetvector.z < 0) {
5591
					p1 = p1.flipped();
5592
					p2 = p2.flipped();
5593
				}
5594
				newpolygons.push(p1);
5595
				newpolygons.push(p2);
5596
			}
5597
		}
5598
		prevtransformedcag = transformedcag;
5599
		prevstepz = stepz;
5600
	} // for step
5601
	return CSG.fromPolygons(newpolygons);
5602
	},
5603

5604
	// check if we are a valid CAG (for debugging)
5605
	check: function() {
5606
		var errors = [];
5607
		if(this.isSelfIntersecting()) {
5608
			errors.push("Self intersects");
5609
		}
5610
		var pointcount = {};
5611
		this.sides.map(function(side) {
5612
			function mappoint(p) {
5613
				var tag = p.x + " " + p.y;
5614
				if(!(tag in pointcount)) pointcount[tag] = 0;
5615
				pointcount[tag]++;
5616
			}
5617
			mappoint(side.vertex0.pos);
5618
			mappoint(side.vertex1.pos);
5619
		});
5620
		for(var tag in pointcount) {
5621
			var count = pointcount[tag];
5622
			if(count & 1) {
5623
				errors.push("Uneven number of sides (" + count + ") for point " + tag);
5624
			}
5625
		}
5626
		var area = this.area();
5627
		if(area < 1e-5) {
5628
			errors.push("Area is " + area);
5629
		}
5630
		if(errors.length > 0) {
5631
			var ertxt = "";
5632
			errors.map(function(err) {
5633
				ertxt += err + "\n";
5634
			});
5635
			throw new Error(ertxt);
5636
		}
5637
	},
5638

5639
	canonicalized: function() {
5640
		if(this.isCanonicalized) {
5641
			return this;
5642
		} else {
5643
			var factory = new CAG.fuzzyCAGFactory();
5644
			var result = factory.getCAG(this);
5645
			result.isCanonicalized = true;
5646
			return result;
5647
		}
5648
	},
5649

5650
	toCompactBinary: function() {
5651
		var cag = this.canonicalized();
5652
		var numsides = cag.sides.length;
5653
		var vertexmap = {};
5654
		var vertices = [];
5655
		var numvertices = 0;
5656
		var sideVertexIndices = new Uint32Array(2 * numsides);
5657
		var sidevertexindicesindex = 0;
5658
		cag.sides.map(function(side) {
5659
			[side.vertex0, side.vertex1].map(function(v) {
5660
				var vertextag = v.getTag();
5661
				var vertexindex;
5662
				if(!(vertextag in vertexmap)) {
5663
					vertexindex = numvertices++;
5664
					vertexmap[vertextag] = vertexindex;
5665
					vertices.push(v);
5666
				} else {
5667
					vertexindex = vertexmap[vertextag];
5668
				}
5669
				sideVertexIndices[sidevertexindicesindex++] = vertexindex;
5670
			});
5671
		});
5672
		var vertexData = new Float64Array(numvertices * 2);
5673
		var verticesArrayIndex = 0;
5674
		vertices.map(function(v) {
5675
			var pos = v.pos;
5676
			vertexData[verticesArrayIndex++] = pos._x;
5677
			vertexData[verticesArrayIndex++] = pos._y;
5678
		});
5679
		var result = {
5680
			'class': "CAG",
5681
			sideVertexIndices: sideVertexIndices,
5682
			vertexData: vertexData
5683
		};
5684
		return result;
5685
	},
5686

5687
	getOutlinePaths: function() {
5688
		var cag = this.canonicalized();
5689
		var sideTagToSideMap = {};
5690
		var startVertexTagToSideTagMap = {};
5691
		cag.sides.map(function(side) {
5692
			var sidetag = side.getTag();
5693
			sideTagToSideMap[sidetag] = side;
5694
			var startvertextag = side.vertex0.getTag();
5695
			if(!(startvertextag in startVertexTagToSideTagMap)) {
5696
				startVertexTagToSideTagMap[startvertextag] = [];
5697
			}
5698
			startVertexTagToSideTagMap[startvertextag].push(sidetag);
5699
		});
5700
		var paths = [];
5701
		while(true) {
5702
			var startsidetag = null;
5703
			for(var aVertexTag in startVertexTagToSideTagMap) {
5704
				var sidesForThisVertex = startVertexTagToSideTagMap[aVertexTag];
5705
				startsidetag = sidesForThisVertex[0];
5706
				sidesForThisVertex.splice(0, 1);
5707
				if(sidesForThisVertex.length === 0) {
5708
					delete startVertexTagToSideTagMap[aVertexTag];
5709
				}
5710
				break;
5711
			}
5712
			if(startsidetag === null) break; // we've had all sides
5713
			var connectedVertexPoints = [];
5714
			var sidetag = startsidetag;
5715
			var thisside = sideTagToSideMap[sidetag];
5716
			var startvertextag = thisside.vertex0.getTag();
5717
			while(true) {
5718
				connectedVertexPoints.push(thisside.vertex0.pos);
5719
				var nextvertextag = thisside.vertex1.getTag();
5720
				if(nextvertextag == startvertextag) break; // we've closed the polygon
5721
				if(!(nextvertextag in startVertexTagToSideTagMap)) {
5722
					throw new Error("Area is not closed!");
5723
				}
5724
				var nextpossiblesidetags = startVertexTagToSideTagMap[nextvertextag];
5725
				var nextsideindex = -1;
5726
				if(nextpossiblesidetags.length == 1) {
5727
					nextsideindex = 0;
5728
				} else {
5729
					// more than one side starting at the same vertex. This means we have
5730
					// two shapes touching at the same corner
5731
					var bestangle = null;
5732
					var thisangle = thisside.direction().angleDegrees();
5733
					for(var sideindex = 0; sideindex < nextpossiblesidetags.length; sideindex++) {
5734
						var nextpossiblesidetag = nextpossiblesidetags[sideindex];
5735
						var possibleside = sideTagToSideMap[nextpossiblesidetag];
5736
						var angle = possibleside.direction().angleDegrees();
5737
						var angledif = angle - thisangle;
5738
						if(angledif < -180) angledif += 360;
5739
						if(angledif >= 180) angledif -= 360;
5740
						if((nextsideindex < 0) || (angledif > bestangle)) {
5741
							nextsideindex = sideindex;
5742
							bestangle = angledif;
5743
						}
5744
					}
5745
				}
5746
				var nextsidetag = nextpossiblesidetags[nextsideindex];
5747
				nextpossiblesidetags.splice(nextsideindex, 1);
5748
				if(nextpossiblesidetags.length === 0) {
5749
					delete startVertexTagToSideTagMap[nextvertextag];
5750
				}
5751
				thisside = sideTagToSideMap[nextsidetag];
5752
			} // inner loop
5753
			var path = new CSG.Path2D(connectedVertexPoints, true);
5754
			paths.push(path);
5755
		} // outer loop
5756
		return paths;
5757
	},
5758

5759
	toDxf: function() {
5760
		var paths = this.getOutlinePaths();
5761
		return CAG.PathsToDxf(paths);
5762
	}
5763
};
5764

5765
CAG.PathsToDxf = function(paths) {
5766
	var str = "999\nDXF generated by OpenJsCad\n";
5767
	str += "  0\nSECTION\n  2\nHEADER\n";
5768
	str += "  0\nENDSEC\n";
5769
	str += "  0\nSECTION\n  2\nTABLES\n";
5770
	str += "  0\nTABLE\n  2\nLTYPE\n  70\n1\n";
5771
	str += "  0\nLTYPE\n  2\nCONTINUOUS\n  3\nSolid Line\n  72\n65\n  73\n0\n  40\n0.0\n";
5772
	str += "  0\nENDTAB\n";
5773
	str += "  0\nTABLE\n  2\nLAYER\n  70\n1\n";
5774
	str += "  0\nLAYER\n  2\nOpenJsCad\n  62\n7\n  6\ncontinuous\n";
5775
	str += "  0\nENDTAB\n";
5776
	str += "  0\nTABLE\n  2\nSTYLE\n  70\n0\n  0\nENDTAB\n";
5777
	str += "  0\nTABLE\n  2\nVIEW\n  70\n0\n  0\nENDTAB\n";
5778
	str += "  0\nENDSEC\n";
5779
	str += "  0\nSECTION\n  2\nBLOCKS\n";
5780
	str += "  0\nENDSEC\n";
5781
	str += "  0\nSECTION\n  2\nENTITIES\n";
5782
	paths.map(function(path) {
5783
		var numpoints_closed = path.points.length + (path.closed ? 1 : 0);
5784
		str += "  0\nLWPOLYLINE\n  8\nOpenJsCad\n  90\n" + numpoints_closed + "\n  70\n" + (path.closed ? 1 : 0) + "\n";
5785
		for(var pointindex = 0; pointindex < numpoints_closed; pointindex++) {
5786
			var pointindexwrapped = pointindex;
5787
			if(pointindexwrapped >= path.points.length) pointindexwrapped -= path.points.length;
5788
			var point = path.points[pointindexwrapped];
5789
			str += " 10\n" + point.x + "\n 20\n" + point.y + "\n 30\n0.0\n";
5790
		}
5791
	});
5792
	str += "  0\nENDSEC\n  0\nEOF\n";
5793
	return new Blob([str], {
5794
		type: "application/dxf"
5795
	});
5796
};
5797

5798
CAG.Vertex = function(pos) {
5799
	this.pos = pos;
5800
};
5801

5802
CAG.Vertex.prototype = {
5803
	toString: function() {
5804
		return "("+this.pos.x.toFixed(2)+","+this.pos.y.toFixed(2)+")";
5805
	},
5806
	getTag: function() {
5807
		var result = this.tag;
5808
		if(!result) {
5809
			result = CSG.getTag();
5810
			this.tag = result;
5811
		}
5812
		return result;
5813
	}
5814
};
5815

5816
CAG.Side = function(vertex0, vertex1) {
5817
	if(!(vertex0 instanceof CAG.Vertex)) throw new Error("Assertion failed");
5818
	if(!(vertex1 instanceof CAG.Vertex)) throw new Error("Assertion failed");
5819
	this.vertex0 = vertex0;
5820
	this.vertex1 = vertex1;
5821
};
5822

5823
CAG.Side.fromFakePolygon = function(polygon) {
5824
	if(polygon.vertices.length != 4) {
5825
		throw new Error("Assertion failed - 1");
5826
	}
5827
	var pointsZeroZ = [];
5828
	var indicesZeroZ = [];
5829
	for(var i = 0; i < 4; i++) {
5830
		var pos = polygon.vertices[i].pos;
5831
		if((pos.z >= -1.001) && (pos.z < -0.999)) {
5832
		} else if((pos.z >= 0.999) && (pos.z < 1.001)) {
5833
		} else {
5834
			throw new Error("Assertion failed - 2");
5835
		}
5836
		if(pos.z > 0) {
5837
			pointsZeroZ.push(new CSG.Vector2D(pos.x, pos.y));
5838
			indicesZeroZ.push(i);
5839
		}
5840
	}
5841
	if(pointsZeroZ.length != 2) {
5842
		throw new Error("Assertion failed - 3");
5843
	}
5844
	var d = indicesZeroZ[1] - indicesZeroZ[0];
5845
	var p1, p2;
5846
	if(d == 1) {
5847
		p1 = pointsZeroZ[1];
5848
		p2 = pointsZeroZ[0];
5849
	} else if(d == 3) {
5850
		p1 = pointsZeroZ[0];
5851
		p2 = pointsZeroZ[1];
5852
	} else {
5853
		throw new Error("Assertion failed - 4");
5854
	}
5855
	var result = new CAG.Side(new CAG.Vertex(p1), new CAG.Vertex(p2));
5856
	return result;
5857
};
5858

5859
CAG.Side.prototype = {
5860
	toString: function() {
5861
		return this.vertex0 + " -> "+ this.vertex1;
5862
	},
5863

5864
	toPolygon3D: function(z0, z1) {
5865
		var vertices = [
5866
			new CSG.Vertex(this.vertex0.pos.toVector3D(z0)),
5867
			new CSG.Vertex(this.vertex1.pos.toVector3D(z0)),
5868
			new CSG.Vertex(this.vertex1.pos.toVector3D(z1)),
5869
			new CSG.Vertex(this.vertex0.pos.toVector3D(z1))
5870
		];
5871
		return new CSG.Polygon(vertices);
5872
	},
5873

5874
	transform: function(matrix4x4) {
5875
		var newp1 = this.vertex0.pos.transform(matrix4x4);
5876
		var newp2 = this.vertex1.pos.transform(matrix4x4);
5877
		return new CAG.Side(new CAG.Vertex(newp1), new CAG.Vertex(newp2));
5878
	},
5879

5880
	flipped: function() {
5881
		return new CAG.Side(this.vertex1, this.vertex0);
5882
	},
5883

5884
	direction: function() {
5885
		return this.vertex1.pos.minus(this.vertex0.pos);
5886
	},
5887

5888
	getTag: function() {
5889
		var result = this.tag;
5890
		if(!result) {
5891
			result = CSG.getTag();
5892
			this.tag = result;
5893
		}
5894
		return result;
5895
	},
5896

5897
	lengthSquared: function() {
5898
		var x = this.vertex1.pos.x - this.vertex0.pos.x,
5899
		y = this.vertex1.pos.y - this.vertex0.pos.y;
5900
		return x*x + y*y;
5901
	},
5902

5903
	length: function() {
5904
		return Math.sqrt(this.lengthSquared());
5905
	}
5906
};
5907

5908
//////////////////////////////////////
5909
CAG.fuzzyCAGFactory = function() {
5910
	this.vertexfactory = new CSG.fuzzyFactory(2, 1e-5);
5911
};
5912

5913
CAG.fuzzyCAGFactory.prototype = {
5914
	getVertex: function(sourcevertex) {
5915
		var elements = [sourcevertex.pos._x, sourcevertex.pos._y];
5916
		var result = this.vertexfactory.lookupOrCreate(elements, function(els) {
5917
			return sourcevertex;
5918
		});
5919
		return result;
5920
	},
5921

5922
	getSide: function(sourceside) {
5923
		var vertex0 = this.getVertex(sourceside.vertex0);
5924
		var vertex1 = this.getVertex(sourceside.vertex1);
5925
		return new CAG.Side(vertex0, vertex1);
5926
	},
5927

5928
	getCAG: function(sourcecag) {
5929
		var _this = this;
5930
		var newsides = sourcecag.sides.map(function(side) {
5931
			return _this.getSide(side);
5932
		});
5933
		return CAG.fromSides(newsides);
5934
	}
5935
};
5936

5937
//////////////////////////////////////
5938
CSG.addTransformationMethodsToPrototype(CSG.prototype);
5939
CSG.addTransformationMethodsToPrototype(CSG.Vector2D.prototype);
5940
CSG.addTransformationMethodsToPrototype(CSG.Vector3D.prototype);
5941
CSG.addTransformationMethodsToPrototype(CSG.Vertex.prototype);
5942
CSG.addTransformationMethodsToPrototype(CSG.Plane.prototype);
5943
CSG.addTransformationMethodsToPrototype(CSG.Polygon.prototype);
5944
CSG.addTransformationMethodsToPrototype(CSG.Line3D.prototype);
5945
CSG.addTransformationMethodsToPrototype(CSG.Connector.prototype);
5946
CSG.addTransformationMethodsToPrototype(CSG.Path2D.prototype);
5947
CSG.addTransformationMethodsToPrototype(CSG.Line2D.prototype);
5948
CSG.addTransformationMethodsToPrototype(CAG.prototype);
5949
CSG.addTransformationMethodsToPrototype(CAG.Side.prototype);
5950

5951
/*
5952
  2D polygons are now supported through the CAG class.
5953
  With many improvements (see documentation):
5954
	- shapes do no longer have to be convex
5955
	- union/intersect/subtract is supported
5956
	- expand / contract are supported
5957

5958
  But we'll keep CSG.Polygon2D as a stub for backwards compatibility
5959
*/
5960
CSG.Polygon2D = function(points) {
5961
	var cag = CAG.fromPoints(points);
5962
	this.sides = cag.sides;
5963
};
5964
CSG.Polygon2D.prototype = CAG.prototype;
5965

5966

5967
module.CSG = CSG;
5968
module.CAG = CAG;
5969
})(this); //module to export to
5970