Source: tesselator.js

  1. /**
  2. * @module tesselator
  3. */
  4. import {GluTesselator, gluEnum, windingRule, primitiveType} from 'libtess';
  5. import {is_ccw, is_cw, normal} from './polygon';
  6. export const {
  7. GL_LINE_LOOP,
  8. GL_TRIANGLES,
  9. GL_TRIANGLE_STRIP,
  10. GL_TRIANGLE_FAN
  11. } = primitiveType;
  12. export const {
  13. GLU_TESS_WINDING_ODD,
  14. GLU_TESS_WINDING_NONZERO,
  15. GLU_TESS_WINDING_POSITIVE,
  16. GLU_TESS_WINDING_NEGATIVE,
  17. GLU_TESS_WINDING_ABS_GEQ_TWO
  18. } = windingRule;
  19. /**
  20. * Tesselator options.
  21. * @typedef {Object} TesselatorOptions
  22. * @property {Array} [polygons=[]] Array of polygons
  23. * @property {Array} [holes=[]] Array of holes
  24. * @property {Number} [vertexSize=2] Vertex size to use
  25. * @property {Number} [windingRule=GLU_TESS_WINDING_POSITIVE] Winding rule
  26. * @property {Boolean} [boundaryOnly=false] Whether to output boundaries only
  27. * @property {Array} [normal=null] Normal
  28. * @property {Boolean} [autoWinding=true] Whether to automatically set the correct winding on polygons
  29. */
  30. export const DEFAULT_OPTIONS = {
  31. polygons: [],
  32. holes: [],
  33. windingRule: GLU_TESS_WINDING_POSITIVE,
  34. boundaryOnly: false,
  35. normal: null,
  36. autoWinding: true
  37. };
  38. export class Tesselator extends GluTesselator {
  39. constructor (vsize=2) {
  40. super();
  41. this._vsize = vsize;
  42. this._current = [];
  43. this._out = [];
  44. this._primitiveType = 0;
  45. this.gluTessCallback(gluEnum.GLU_TESS_VERTEX_DATA, this._vertex);
  46. this.gluTessCallback(gluEnum.GLU_TESS_BEGIN, this._begin);
  47. this.gluTessCallback(gluEnum.GLU_TESS_END, this._end);
  48. this.gluTessCallback(gluEnum.GLU_TESS_ERROR, this._error);
  49. this.gluTessCallback(gluEnum.GLU_TESS_COMBINE, this._combine);
  50. this.gluTessCallback(gluEnum.GLU_TESS_EDGE_FLAG, this._edge);
  51. }
  52. start (polygons, holes) {
  53. this._current = [];
  54. this._out = [];
  55. this.gluTessBeginPolygon();
  56. for (let poly of polygons) {
  57. this.gluTessBeginContour();
  58. for (let v of poly) {
  59. this.gluTessVertex(v, v);
  60. }
  61. this.gluTessEndContour();
  62. }
  63. for (let poly of holes) {
  64. this.gluTessBeginContour();
  65. for (let v of poly) {
  66. this.gluTessVertex(v, v);
  67. }
  68. this.gluTessEndContour();
  69. }
  70. this.gluTessEndPolygon();
  71. }
  72. run (options=DEFAULT_OPTIONS) {
  73. let opts = Object.assign({}, DEFAULT_OPTIONS, options),
  74. {polygons, holes, autoWinding, boundaryOnly} = opts;
  75. if (!polygons || !polygons.length) {
  76. throw new Error('need at least a single polygon');
  77. }
  78. if (autoWinding) {
  79. polygons = polygons.map(p => {
  80. if (is_cw(p)) p.reverse();
  81. return p;
  82. });
  83. holes = holes.map(p => {
  84. if (is_ccw(p)) p.reverse();
  85. return p;
  86. });
  87. }
  88. let [nx, ny, nz] = opts.normal ? opts.normal : normal(polygons[0], true);
  89. this.gluTessNormal(nx, ny, nz);
  90. this.gluTessProperty(gluEnum.GLU_TESS_BOUNDARY_ONLY, boundaryOnly);
  91. this.gluTessProperty(gluEnum.GLU_TESS_WINDING_RULE, opts.windingRule);
  92. this.start(polygons, holes);
  93. return this._out;
  94. }
  95. _begin (type) {
  96. this._primitiveType = type;
  97. this._current = [];
  98. }
  99. _end_fan () {
  100. let c = this._current.shift(),
  101. p1 = this._current.shift();
  102. while (this._current.length) {
  103. let p2 = this._current.shift();
  104. this._out.push(c, p1, p2);
  105. p1 = p2;
  106. }
  107. }
  108. _end_strip () {
  109. let p1 = this._current.shift(),
  110. p2 = this._current.shift();
  111. while (this._current.length) {
  112. let p3 = this._current.shift();
  113. this._out.push(p1, p2, p3);
  114. p1 = p2;
  115. p2 = p3;
  116. }
  117. }
  118. _end () {
  119. switch (this._primitiveType) {
  120. case GL_TRIANGLE_FAN:
  121. this._end_fan();
  122. break;
  123. case GL_TRIANGLE_STRIP:
  124. this._end_strip();
  125. break;
  126. case GL_TRIANGLES:
  127. case GL_LINE_LOOP:
  128. default:
  129. this._out.push(this._current);
  130. break;
  131. }
  132. }
  133. _vertex (v) {
  134. this._current.push(v);
  135. }
  136. _edge () {}
  137. _error (errno) { console.error('error number: ' + errno); }
  138. _combine (v, data, w) {
  139. for (let i = 0; i < 4; ++i) {
  140. if (!data[i]) {
  141. data[i] = new Array(this._vsize);
  142. for (let j = 0; j < this._vsize; ++j) {
  143. data[i][j] = 0;
  144. }
  145. }
  146. }
  147. let r = new Array(this._vsize);
  148. for (let i = 0; i < this._vsize; ++i) {
  149. r[i] = data[0][i] * w[0] + data[1][i] * w[1] + data[2][i] * w[2] + data[3][i] * w[3];
  150. }
  151. return r;
  152. }
  153. }
  154. /**
  155. * Helper for triangulate
  156. * @private
  157. */
  158. function to_triangles (data) {
  159. let result = [];
  160. for (let i = 0; i < data.length; i += 3) {
  161. result.push([data[i], data[i+1], data[i+2]]);
  162. }
  163. return result;
  164. }
  165. /**
  166. * Runs the tesselator
  167. * @see http://www.glprogramming.com/red/chapter11.html
  168. *
  169. * @param {TesselatorOptions} [options=TesselatorOptions] Options
  170. *
  171. * @returns {Array}
  172. */
  173. export function run (options=DEFAULT_OPTIONS) {
  174. let tesselator = new Tesselator(options.vertexSize),
  175. result = tesselator.run(options);
  176. return options.boundaryOnly ? result : result.map(to_triangles);
  177. }