b.inverse().union(a) example in more.html

[jceddy]

Noticed that the image labeled "b.inverse().union(a)" in the more.html page is actually generated by "a.subtract(b)" and that the former (b.inverse().union(a)) doesn't actually work because this "inverted solid inside another solid" gets all polygons eliminated in the first two clipTo() calls in union().

I think I understand why this happens (because both solids are completely "behind" the bsp node plane(s) of the other solid?? [correct me if I'm wrong]). Is this just a fundamental issue of the way the operations are set up, or do you think there's a fix?

[jceddy]

Suggested fix:

After the first two clipping operations in the CSG.prototype.union() function, add a sanity check to see if you've clipped out all of the polygons. If so, then check if either of the solids in the union is "inside-out" (a bit more on this below). If either of the solids is inside-out, then return the inverse of that solid subtracted from the other one. So basically, the union() function becomes:

union: function(csg) {
  var a = new CSG.Node(this.clone().polygons);
  var b = new CSG.Node(csg.clone().polygons);
  a.clipTo(b);
  b.clipTo(a);

  // check right here if we've lost all the polygons
  if((a.allPolygons().length + b.allPolygons().length) == ) {
    if(this.isInsideOut()) {
      return csg.subtract(this.inverse());
    }
    else if(csg.isInsideOut()) {
      return this.subtract(csg.inverse());
    }
  }

  // the rest of the original function
  b.invert();
  b.clipTo(a);
  b.invert();
  a.build(b.allPolygons());
  return CSG.fromPolygons(a.allPolygons());
}

This will at least solve the problem of the b.inverse().union(a) case...I suspect that there is a better solution but I haven't thought about it enough yet.

As far as detecting if a solid is "inside-out", I think that is pretty simply a case of: 1) pick a polygon in the solid's mesh 2) count how many other polygons in the mesh are intersected by a ray from the center of the polygon in the direction opposite the normal if the intersection count is odd, then the solid is "inside-out". I think this works for all closed meshes, regardless of whether they are convex.

Let me know what you think.

[jceddy]

Here's my first attempt at an isInsideOut() function:

  // Gets a flag indicating whether the solid is "inside-out".
  // This assumes a closed mesh.
  isInsideOut: function() {
    if(this.polygons.length == 0) {
        return false;
    }
    else {
        var intersectionCount = 0;

        // start at the center of the polygon, otherwise the ray will intersect
        // with the plane of any polygon that shares the vertex at t = 0
        var start = this.polygons[0].vertices[0].pos;
        for(var i = 1; i < this.polygons[0].vertices.length; i++) {
          start = start.plus(this.polygons[0].vertices[i].pos);
        }
        start = start.dividedBy(this.polygons[0].vertices.length);

        var direction = this.polygons[0].vertices[0].normal.negated();

        for(var i = 1; i < this.polygons.count; i++) {
            // check if the ray intersects with this polygon's plane
            // if denom is 0 the plane is parallel to the ray and there will be no intersection
            var denom = direction.dot(this.polygons[i].plane.normal);
            if(denom != 0) {
                var t = -(start.dot(this.polygons[i].plane.normal) + this.polygons[i].plane.w) / denom;
                if(t >= 0) {
                    // ray intersects the plane of the polygon,
                    // check if the point of intersection is on the polygon...
                    // we actually check for a list of triangles comprised by the polygon,
                    // this will only work properly for convex polygons
                    var p = start.plus(direction.times(t));  // intersection point
                    for(var j = 2; j < this.polygons[i].vertices.length; j++) {
                        var u0, v0, u1, u2, v1, v2;

                        if(Math.abs(this.polygons[i].plane.normal.x) > Math.abs(this.polygons[i].plane.normal.y)) {
                            // x or z is major axis
                            if(Math.abs(this.polygons[i].plane.normal.x) > Math.abs(this.polygons[i].plane.normal.z)) {
                                // x is major axis
                                u0 = p.y - this.polygons[i].vertices[j - 2].pos.y;
                                v0 = p.z - this.polygons[i].vertices[j - 2].pos.z;
                                u1 = this.polygons[i].vertices[j - 1].pos.y - this.polygons[i].vertices[j - 2].pos.y;
                                u2 = this.polygons[i].vertices[j].pos.y - this.polygons[i].vertices[j - 2].pos.y;
                                v1 = this.polygons[i].vertices[j - 1].pos.z - this.polygons[i].vertices[j - 2].pos.z;
                                v2 = this.polygons[i].vertices[j].pos.z - this.polygons[i].vertices[j - 2].pos.z;
                            }
                            else {
                                // z is major axis
                                u0 = p.x - this.polygons[i].vertices[j - 2].pos.x;
                                v0 = p.y - this.polygons[i].vertices[j - 2].pos.y;
                                u1 = this.polygons[i].vertices[j - 1].pos.x - this.polygons[i].vertices[j - 2].pos.x;
                                u2 = this.polygons[i].vertices[j].pos.x - this.polygons[i].vertices[j - 2].pos.x;
                                v1 = this.polygons[i].vertices[j - 1].pos.y - this.polygons[i].vertices[j - 2].pos.y;
                                v2 = this.polygons[i].vertices[j].pos.y - this.polygons[i].vertices[j - 2].pos.y;
                            }
                        }
                        else {
                            // y or z is major axis
                            if(Math.abs(this.polygons[i].plane.normal.y) > Math.abs(this.polygons[i].plane.normal.z)) {
                                // y is major axis
                                u0 = p.x - this.polygons[i].vertices[j - 2].pos.x;
                                v0 = p.z - this.polygons[i].vertices[j - 2].pos.z;
                                u1 = this.polygons[i].vertices[j - 1].pos.x - this.polygons[i].vertices[j - 2].pos.x;
                                u2 = this.polygons[i].vertices[j].pos.x - this.polygons[i].vertices[j - 2].pos.x;
                                v1 = this.polygons[i].vertices[j - 1].pos.z - this.polygons[i].vertices[j - 2].pos.z;
                                v2 = this.polygons[i].vertices[j].pos.z - this.polygons[i].vertices[j - 2].pos.z;
                            }
                            else {
                                // z is major axis
                                u0 = p.x - this.polygons[i].vertices[j - 2].pos.x;
                                v0 = p.y - this.polygons[i].vertices[j - 2].pos.y;
                                u1 = this.polygons[i].vertices[j - 1].pos.x - this.polygons[i].vertices[j - 2].pos.x;
                                u2 = this.polygons[i].vertices[j].pos.x - this.polygons[i].vertices[j - 2].pos.x;
                                v1 = this.polygons[i].vertices[j - 1].pos.y - this.polygons[i].vertices[j - 2].pos.y;
                                v2 = this.polygons[i].vertices[j].pos.y - this.polygons[i].vertices[j - 2].pos.y;
                            }
                        }

                        var alpha = 0, beta;
                        if(u1 == 0) {
                            beta = u0 / u2;
                            if((0 <= beta) && (beta <= 1)) {
                                alpha = (v0 - beta * v2) / v1;
                            }
                        }
                        else {
                            beta = (v0 * u1 - u0 * v1) / (v2 * u1 - u2 * v1);
                            if((0 <= beta) && (beta <= 1)) {
                                alpha = (u0 - beta * u2) / u1;
                            }
                        }

                        if((alpha >= 0) && (beta >= 0) && ((alpha + beta) <= 1)) {
                            // ray intersects polygon, increment intersection count
                            intersectionCount++;
                        }
                    }
                }
            }
        }

        // if there is an odd number of intersections, then
        // the solid is inside-out
        return ((intersectionCount % 2) == 0);
    }
  }

Anyway...I'll leave you alone for a while now. :)

[jceddy]

Oh, my, I feel stupid. The union in the example text SHOULD have no mesh geometry because it is everything.

Please excuse me and ignore the above unless you find you have a use for any of it. :)