From 725cc3cd23890d5369ae20c27c97465c34168913 Mon Sep 17 00:00:00 2001 From: Jules Laplace Date: Tue, 22 Jul 2014 16:23:57 -0400 Subject: starting math tests --- .../assets/javascripts/rectangles/models/rect.js | 40 +++++++++++++++++++++- 1 file changed, 39 insertions(+), 1 deletion(-) (limited to 'public/assets/javascripts/rectangles/models/rect.js') diff --git a/public/assets/javascripts/rectangles/models/rect.js b/public/assets/javascripts/rectangles/models/rect.js index 315adef..f91e759 100644 --- a/public/assets/javascripts/rectangles/models/rect.js +++ b/public/assets/javascripts/rectangles/models/rect.js @@ -1,5 +1,25 @@ (function(){ + var vec2 + if ('window' in this) { + vec2 = window.vec2 + } + else { + vec2 = require('./vec2') + FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20 + TOP = CEILING, BOTTOM = FLOOR + function sidesToString(sides){ + var s = "" + if (sides & FRONT) s += "front " + if (sides & BACK) s += "back " + if (sides & LEFT) s += "left " + if (sides & RIGHT) s += "right " + if (sides & TOP) s += "top " + if (sides & BOTTOM) s += "bottom " + return s + } + } + var Rect = function (x0,y0,x1,y1){ if (x0 instanceof vec2) { this.x = x0 @@ -77,6 +97,12 @@ Rect.prototype.intersects = function(r){ return this.x.intersects(r.x) && this.y.intersects(r.y) } + Rect.prototype.adjacent = function(r){ + return this.x.adjacent(r.x) && this.y.adjacent(r.y) + } + Rect.prototype.eq = function(r){ + return this.x.eq(r.x) && this.y.eq(r.y) + } Rect.prototype.nearEdge = function (x, y, r) { var edges = 0 if (x < this.x.a+r) { @@ -173,6 +199,18 @@ if (r.intersects(rn)) { rn.sides = 0 } + // if (r.x.b == rn.x.a) { +// rn.sides &= ~LEFT +// } +// if (rn.x.b == r.x.a) { +// rn.sides &= ~RIGHT +// } +// if (r.y.b == rn.y.a) { +// rn.sides &= ~FRONT +// } +// if (rn.y.b == r.y.a) { +// rn.sides &= ~BACK +// } rn.focused = rz.focused splits.push(rn) }) @@ -183,7 +221,7 @@ if ('window' in this) { window.Rect = Rect } - else if ('module' in this) { + else { module.exports = Rect } -- cgit v1.2.3-70-g09d2 From 52d18ddb211a7f4ee814ef23ff09656134810519 Mon Sep 17 00:00:00 2001 From: Julie Lala Date: Wed, 23 Jul 2014 01:38:17 -0400 Subject: making things intersect more greedily --- Makefile | 6 ++ .../assets/javascripts/rectangles/models/rect.js | 64 ++---------- .../assets/javascripts/rectangles/models/vec2.js | 39 ++++++- test/01-test-vec2.js | 48 +++++++++ test/02-test-rect.js | 116 +++++++++++++++++++++ test/test-rect.js | 63 ----------- test/test-vec2.js | 48 --------- 7 files changed, 216 insertions(+), 168 deletions(-) create mode 100644 Makefile create mode 100644 test/01-test-vec2.js create mode 100644 test/02-test-rect.js delete mode 100644 test/test-rect.js delete mode 100644 test/test-vec2.js (limited to 'public/assets/javascripts/rectangles/models/rect.js') diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..b7e7836 --- /dev/null +++ b/Makefile @@ -0,0 +1,6 @@ + +test: + ./node_modules/.bin/mocha -R nyan + +.PHONY: test + diff --git a/public/assets/javascripts/rectangles/models/rect.js b/public/assets/javascripts/rectangles/models/rect.js index f91e759..8b6a666 100644 --- a/public/assets/javascripts/rectangles/models/rect.js +++ b/public/assets/javascripts/rectangles/models/rect.js @@ -95,7 +95,8 @@ return this.x.containsDisc(x,r) && this.y.containsDisc(y,r) } Rect.prototype.intersects = function(r){ - return this.x.intersects(r.x) && this.y.intersects(r.y) + var corner_intersect = (this.x.b === r.x.a && this.y.b === r.y.a) + return this.x.intersects(r.x) && this.y.intersects(r.y) && ! corner_intersect } Rect.prototype.adjacent = function(r){ return this.x.adjacent(r.x) && this.y.adjacent(r.y) @@ -137,70 +138,21 @@ Rect.prototype.split = function(r){ var rz = this var splits = [] - var split_contains = 0 - var x_intervals = [], y_intervals = [] var sides = this.sides - // Split vertically - if (this.x.contains(r.x.a) && r.x.contains(this.x.b)) { - x_intervals.push([ new vec2( this.x.a, r.x.a ), LEFT ]) - x_intervals.push([ new vec2( r.x.a, this.x.b ), RIGHT ]) - split_contains |= RIGHT - } - - else if (r.x.contains(this.x.a) && this.x.contains(r.x.b)) { - x_intervals.push([ new vec2( this.x.a, r.x.b ), LEFT ]) - x_intervals.push([ new vec2( r.x.b, this.x.b ), RIGHT ]) - split_contains |= LEFT - } - - else if (this.x.contains(r.x.a) && this.x.contains(r.x.b)) { - x_intervals.push([ new vec2( this.x.a, r.x.a ), LEFT ]) - x_intervals.push([ new vec2( r.x.a, r.x.b ), 0 ]) - x_intervals.push([ new vec2( r.x.b, this.x.b ), RIGHT ]) - split_contains |= LEFT | RIGHT - } - - else { // if (r.x.contains(this.x.a) && r.x.contains(r.x.b)) { - x_intervals.push([ new vec2( this.x.a, this.x.b ), LEFT | RIGHT ]) - split_contains |= LEFT | RIGHT - } - - // Split horizontally - if (this.y.contains(r.y.a) && r.y.contains(this.y.b)) { - y_intervals.push([ new vec2( this.y.a, r.y.a ), FRONT ]) - y_intervals.push([ new vec2( r.y.a, this.y.b ), BACK ]) - split_contains |= BACK - } - - else if (r.y.contains(this.y.a) && this.y.contains(r.y.b)) { - y_intervals.push([ new vec2( this.y.a, r.y.b ), FRONT ]) - y_intervals.push([ new vec2( r.y.b, this.y.b ), BACK ]) - split_contains |= FRONT - } - - else if (this.y.contains(r.y.a) && this.y.contains(r.y.b)) { - y_intervals.push([ new vec2( this.y.a, r.y.a ), FRONT ]) - y_intervals.push([ new vec2( r.y.a, r.y.b ), 0 ]) - y_intervals.push([ new vec2( r.y.b, this.y.b ), BACK ]) - split_contains |= FRONT | BACK - } - - else { // if (r.y.contains(this.y.a) && this.y.contains(r.y.b)) { - y_intervals.push([ new vec2( this.y.a, this.y.b ), FRONT | BACK ]) - split_contains |= FRONT | BACK - } + var x_intervals = this.x.split( r.x, LEFT, RIGHT ) + var y_intervals = this.y.split( r.y, FRONT, BACK ) x_intervals.forEach(function(x){ y_intervals.forEach(function(y){ var rn = new Rect(x[0], y[0]) rn.id = rz.id rn.sides = ((x[1] | y[1]) & sides) - if (r.intersects(rn)) { - rn.sides = 0 - } +// if (r.intersects(rn)) { +// rn.sides = 0 +// } // if (r.x.b == rn.x.a) { -// rn.sides &= ~LEFT +// rn.sides &= ~LEFT // } // if (rn.x.b == r.x.a) { // rn.sides &= ~RIGHT diff --git a/public/assets/javascripts/rectangles/models/vec2.js b/public/assets/javascripts/rectangles/models/vec2.js index 9c6fd99..4480473 100644 --- a/public/assets/javascripts/rectangles/models/vec2.js +++ b/public/assets/javascripts/rectangles/models/vec2.js @@ -80,7 +80,7 @@ return clamp(n, this.a+r, this.b-r) } vec2.prototype.intersects = function(v){ - if (this.a == v.a) { // || this.b == v.b || this.a == v.b || this.b == v.a) { + if (this.a == v.a || this.b == v.b || this.a == v.b || this.b == v.a) { return true } else if (this.a < v.a) { @@ -106,6 +106,43 @@ return new vec2( max(this.a,v.a), min(this.b, v.b) ) } } + + // given two vectors, test how they overlap + // return the set of overlapping segments in the initial vector, labelled with sides + vec2.prototype.split = function(v, left, right){ + var intervals = [] + + if (this.eq(v)) { + intervals.push([ new vec2( this.a, this.b ), left | right ]) + } + + // a---A===b---B (rightways overlap) + else if (this.contains(v.a) && v.contains(this.b)) { + intervals.push([ new vec2( this.a, v.a ), left ]) + intervals.push([ new vec2( v.a, this.b ), 0 ]) + } + + // A---a===B---b (leftways overlap) + else if (v.contains(this.a) && this.contains(v.b)) { + intervals.push([ new vec2( this.a, v.b ), 0 ]) + intervals.push([ new vec2( v.b, this.b ), right ]) + } + + // a---A===B---b (contains v) + else if (this.contains(v.a) && this.contains(v.b)) { + intervals.push([ new vec2( this.a, v.a ), left ]) + intervals.push([ new vec2( v.a, v.b ), 0 ]) + intervals.push([ new vec2( v.b, this.b ), right ]) + } + + // A---a===b---B (contained in v) + else { // if (v.contains(this.a) && v.contains(v.b)) { + intervals.push([ new vec2( this.a, this.b ), 0 ]) + } + + return intervals + } + vec2.prototype.toString = function(){ return "[" + ~~this.a + " " + ~~this.b + "]" } diff --git a/test/01-test-vec2.js b/test/01-test-vec2.js new file mode 100644 index 0000000..054d37b --- /dev/null +++ b/test/01-test-vec2.js @@ -0,0 +1,48 @@ +var assert = require("assert") +var vec2 = require("../public/assets/javascripts/rectangles/models/vec2.js") + +describe('vec2', function(){ + describe('#intersects()', function(){ + var vec = new vec2(0, 10) + + it('intersects itself', function(){ + assert.equal(true, vec.intersects( new vec2(0, 10) )); + }) + it('intersects w/ same startpoint (shorter)', function(){ + assert.equal(true, vec.intersects( new vec2(0, 5) )); + }) + it('intersects w/ same startpoint (longer)', function(){ + assert.equal(true, vec.intersects( new vec2(0, 15) )); + }) + it('intersects w/ same endpoint (shorter)', function(){ + assert.equal(true, vec.intersects( new vec2(5, 10) )); + }) + it('intersects w/ same endpoint (longer)', function(){ + assert.equal(true, vec.intersects( new vec2(-5, 10) )); + }) + it('intersects when contained', function(){ + assert.equal(true, vec.intersects( new vec2(-5, 15) )); + }) + it('does not intersect when before', function(){ + assert.equal(false, vec.intersects( new vec2(-10, -5) )); + }) + it('does not intersect when after', function(){ + assert.equal(false, vec.intersects( new vec2(15, 20) )); + }) + it('contains itself', function(){ + assert.equal(true, vec.contains( 0 )); + assert.equal(true, vec.contains( 5 )); + assert.equal(true, vec.contains( 10 )); + }) + it('does not contain before or after', function(){ + assert.equal(false, vec.contains( -5 )); + assert.equal(false, vec.contains( 15 )); + }) + it('intersects when only startpoint matches', function(){ + assert.equal(true, vec.intersects( new vec2(-5, 0) )); + }) + it('intersects when only endpoint matches', function(){ + assert.equal(true, vec.intersects( new vec2(10, 15) )); + }) + }) +}) diff --git a/test/02-test-rect.js b/test/02-test-rect.js new file mode 100644 index 0000000..39693f5 --- /dev/null +++ b/test/02-test-rect.js @@ -0,0 +1,116 @@ +var assert = require("assert") +var vec = require("../public/assets/javascripts/rectangles/models/vec2.js") +var Rect = require("../public/assets/javascripts/rectangles/models/rect.js") +var FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20 +var ALL = FRONT | BACK | LEFT | RIGHT + +describe('rect', function(){ + describe('#intersects()', function(){ + var rect = new Rect(0, 0, 10, 10) + + it('intersects itself', function(){ + assert.equal(true, rect.intersects( new Rect(0, 0, 10, 10) )); + }) + it('intersects more wide', function(){ + assert.equal(true, rect.intersects( new Rect(0, 0, 5, 10) )); + }) + it('intersects less wide', function(){ + assert.equal(true, rect.intersects( new Rect(0, 0, 15, 10) )); + }) + it('intersects more tall', function(){ + assert.equal(true, rect.intersects( new Rect(0, 0, 10, 5) )); + }) + it('intersects less tall', function(){ + assert.equal(true, rect.intersects( new Rect(0, 0, 10, 15) )); + }) + it('intersects if right-adjacent', function(){ + assert.equal(true, rect.intersects( new Rect(10, 0, 20, 10) )); + }) + it('intersects if bottom-adjacent', function(){ + assert.equal(true, rect.intersects( new Rect(0, 10, 10, 20) )); + }) + it('does not intersect if to the right', function(){ + assert.equal(false, rect.intersects( new Rect(20, 0, 40, 10) )); + }) + it('does not intersect if beneath', function(){ + assert.equal(false, rect.intersects( new Rect(0, 20, 10, 40) )); + }) + /* + it('does not intersect if corners intersect', function(){ + assert.equal(false, rect.intersects( new Rect(10, 10, 20, 20) )); + }) + */ + + }) + + var rect = new Rect( new vec(1,4), new vec(1,4) ) + + var east_in = new Rect( new vec(2,3), new vec(1,4) ) + var east_edge = new Rect( new vec(2,4), new vec(1,4) ) + var east = new Rect( new vec(2,5), new vec(1,4) ) + + var south_in = new Rect( new vec(1,4), new vec(2,3) ) + var south_edge = new Rect( new vec(1,4), new vec(2,4) ) + var south = new Rect( new vec(1,4), new vec(2,5) ) + + var corner = new Rect( new vec(3,5), new vec(3,5) ) + + function sides (s) { + return s.reduce(function(prev, curr){ + return prev | curr.sides + }, 0) + } + + describe('#split(rect, east)', function(){ + var s0 = rect.split(east) + var s1 = east.split(rect) + it('splits on all 4 sides', function(){ + assert.equal(ALL, sides(s0) | sides(s1)) + }) + it('rect is front/back/left', function(){ + assert.equal(FRONT | BACK | LEFT, sides(s0)) + }) + it('east is front/back/right', function(){ + assert.equal(FRONT | BACK | RIGHT, sides(s1)) + }) + }) + + describe('#split(rect, east_in)', function(){ + var s0 = rect.split(east_in) + var s1 = east_in.split(rect) + it('splits on all 4 sides', function(){ + assert.equal(ALL, sides(s0) | sides(s1)) + }) + it('rect is has all sides', function(){ + assert.equal(ALL, sides(s0)) + }) + it('east_in only has front/back', function(){ + assert.equal(FRONT | BACK, sides(s1)) + }) + }) + + describe('#split(rect, east_edge)', function(){ + var s0 = rect.split(east_edge) + var s1 = east_edge.split(rect) + + console.log("\n") + console.log(rect+"") + console.log(east_edge+"") + console.log(s0.map(function(r){ return r.toString() })) + console.log(s1.map(function(r){ return r.toString() })) + + it('splits on all 4 sides', function(){ + assert.equal(ALL, sides(s0) | sides(s1)) + }) + it('rect is front/back/left', function(){ + assert.equal(FRONT | BACK | LEFT, sides(s0)) + }) + it('east is front/back/right', function(){ + assert.equal(FRONT | BACK | RIGHT, sides(s1)) + }) + }) + +}) +/* +*/ + diff --git a/test/test-rect.js b/test/test-rect.js deleted file mode 100644 index 7dd7ae6..0000000 --- a/test/test-rect.js +++ /dev/null @@ -1,63 +0,0 @@ -var assert = require("assert") -var vec = require("../public/assets/javascripts/rectangles/models/vec2.js") -var Rect = require("../public/assets/javascripts/rectangles/models/rect.js") -var FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20 -var ALL = FRONT | BACK | LEFT | RIGHT - -describe('rect', function(){ - describe('#intersects()', function(){ - var rect = new Rect(0, 0, 10, 10) - - it('intersects itself', function(){ - assert.equal(true, rect.intersects( new Rect(0, 0, 10, 10) )); - }) - it('intersects more wide', function(){ - assert.equal(true, rect.intersects( new Rect(0, 0, 5, 10) )); - }) - it('intersects less wide', function(){ - assert.equal(true, rect.intersects( new Rect(0, 0, 15, 10) )); - }) - it('intersects more tall', function(){ - assert.equal(true, rect.intersects( new Rect(0, 0, 10, 5) )); - }) - it('intersects less tall', function(){ - assert.equal(true, rect.intersects( new Rect(0, 0, 10, 15) )); - }) - it('intersects if right-adjacent', function(){ - assert.equal(true, rect.intersects( new Rect(10, 0, 20, 10) )); - }) - it('intersects if bottom-adjacent', function(){ - assert.equal(true, rect.intersects( new Rect(0, 10, 10, 20) )); - }) - it('does not intersect if to the right', function(){ - assert.equal(false, rect.intersects( new Rect(20, 0, 40, 10) )); - }) - it('does not intersect if beneath', function(){ - assert.equal(false, rect.intersects( new Rect(0, 20, 10, 40) )); - }) - /* - it('does not intersect if corners intersect', function(){ - assert.equal(false, rect.intersects( new Rect(10, 10, 20, 20) )); - }) - */ - - }) - describe('#split()', function(){ - var rect = new Rect( 0, 0, 10, 10) - var east = new Rect( 5, 0, 15, 10) - var east_in = new Rect( 5, 0, 10, 10) - var east_edge = new Rect(10, 0, 20, 10) - var south = new Rect( 0, 5, 10, 15) - var south_in = new Rect( 0, 5, 10, 10) - var south_edge = new Rect( 0, 10, 10, 15) - var corner = new Rect( 5, 5, 15, 15) - - it('splits east', function(){ - var splits = rect.split(east) - var splits2 = east.split(rect) - console.log("\n") - console.log(rect+"") - console.log(splits.map(function(r){ return r.toString() })) - }) - }) -}) diff --git a/test/test-vec2.js b/test/test-vec2.js deleted file mode 100644 index 054d37b..0000000 --- a/test/test-vec2.js +++ /dev/null @@ -1,48 +0,0 @@ -var assert = require("assert") -var vec2 = require("../public/assets/javascripts/rectangles/models/vec2.js") - -describe('vec2', function(){ - describe('#intersects()', function(){ - var vec = new vec2(0, 10) - - it('intersects itself', function(){ - assert.equal(true, vec.intersects( new vec2(0, 10) )); - }) - it('intersects w/ same startpoint (shorter)', function(){ - assert.equal(true, vec.intersects( new vec2(0, 5) )); - }) - it('intersects w/ same startpoint (longer)', function(){ - assert.equal(true, vec.intersects( new vec2(0, 15) )); - }) - it('intersects w/ same endpoint (shorter)', function(){ - assert.equal(true, vec.intersects( new vec2(5, 10) )); - }) - it('intersects w/ same endpoint (longer)', function(){ - assert.equal(true, vec.intersects( new vec2(-5, 10) )); - }) - it('intersects when contained', function(){ - assert.equal(true, vec.intersects( new vec2(-5, 15) )); - }) - it('does not intersect when before', function(){ - assert.equal(false, vec.intersects( new vec2(-10, -5) )); - }) - it('does not intersect when after', function(){ - assert.equal(false, vec.intersects( new vec2(15, 20) )); - }) - it('contains itself', function(){ - assert.equal(true, vec.contains( 0 )); - assert.equal(true, vec.contains( 5 )); - assert.equal(true, vec.contains( 10 )); - }) - it('does not contain before or after', function(){ - assert.equal(false, vec.contains( -5 )); - assert.equal(false, vec.contains( 15 )); - }) - it('intersects when only startpoint matches', function(){ - assert.equal(true, vec.intersects( new vec2(-5, 0) )); - }) - it('intersects when only endpoint matches', function(){ - assert.equal(true, vec.intersects( new vec2(10, 15) )); - }) - }) -}) -- cgit v1.2.3-70-g09d2 From 8a8b78b3f6a4ce930263099fe14b0fe86d11597f Mon Sep 17 00:00:00 2001 From: Julie Lala Date: Wed, 23 Jul 2014 11:11:08 -0400 Subject: shorter stack traces --- .../assets/javascripts/rectangles/models/rect.js | 26 +++++----- .../assets/javascripts/rectangles/models/vec2.js | 21 ++++++-- test/00-setup.js | 2 + test/02-test-rect.js | 56 ++++++++++++++++++---- 4 files changed, 80 insertions(+), 25 deletions(-) create mode 100644 test/00-setup.js (limited to 'public/assets/javascripts/rectangles/models/rect.js') diff --git a/public/assets/javascripts/rectangles/models/rect.js b/public/assets/javascripts/rectangles/models/rect.js index 8b6a666..f724ecc 100644 --- a/public/assets/javascripts/rectangles/models/rect.js +++ b/public/assets/javascripts/rectangles/models/rect.js @@ -148,20 +148,22 @@ var rn = new Rect(x[0], y[0]) rn.id = rz.id rn.sides = ((x[1] | y[1]) & sides) -// if (r.intersects(rn)) { -// rn.sides = 0 -// } - // if (r.x.b == rn.x.a) { -// rn.sides &= ~LEFT -// } -// if (rn.x.b == r.x.a) { -// rn.sides &= ~RIGHT + + if (r.x.contains(rn.x.a)) { + rn.sides &= ~ LEFT + } + if (r.x.contains(rn.x.b)) { + rn.sides &= ~ RIGHT + } +// if (r.y.contains(rn.y.a)) { +// rn.sides &= ~ FRONT // } -// if (r.y.b == rn.y.a) { -// rn.sides &= ~FRONT +// if (r.y.contains(rn.y.a)) { +// rn.sides &= ~ BACK // } -// if (rn.y.b == r.y.a) { -// rn.sides &= ~BACK + +// if (r.intersects(rn)) { +// rn.sides = 0 // } rn.focused = rz.focused splits.push(rn) diff --git a/public/assets/javascripts/rectangles/models/vec2.js b/public/assets/javascripts/rectangles/models/vec2.js index 4480473..447c7a3 100644 --- a/public/assets/javascripts/rectangles/models/vec2.js +++ b/public/assets/javascripts/rectangles/models/vec2.js @@ -110,7 +110,7 @@ // given two vectors, test how they overlap // return the set of overlapping segments in the initial vector, labelled with sides vec2.prototype.split = function(v, left, right){ - var intervals = [] + var intervals = [], _len if (this.eq(v)) { intervals.push([ new vec2( this.a, this.b ), left | right ]) @@ -119,12 +119,12 @@ // a---A===b---B (rightways overlap) else if (this.contains(v.a) && v.contains(this.b)) { intervals.push([ new vec2( this.a, v.a ), left ]) - intervals.push([ new vec2( v.a, this.b ), 0 ]) + intervals.push([ new vec2( v.a, this.b ), right ]) } // A---a===B---b (leftways overlap) else if (v.contains(this.a) && this.contains(v.b)) { - intervals.push([ new vec2( this.a, v.b ), 0 ]) + intervals.push([ new vec2( this.a, v.b ), left ]) intervals.push([ new vec2( v.b, this.b ), right ]) } @@ -137,7 +137,20 @@ // A---a===b---B (contained in v) else { // if (v.contains(this.a) && v.contains(v.b)) { - intervals.push([ new vec2( this.a, this.b ), 0 ]) + intervals.push([ new vec2( this.a, this.b ), left | right ]) + } + + // cull empty vectors + _len = intervals.length + if (_len > 1) { + if (intervals[0][0].magnitude() == 0) { + intervals[1][1] |= intervals[0][1] + intervals.shift() + } + else if (intervals[_len-1][0].magnitude() == 0) { + intervals[_len-2][1] |= intervals[_len-1][1] + intervals.pop() + } } return intervals diff --git a/test/00-setup.js b/test/00-setup.js new file mode 100644 index 0000000..8d06a13 --- /dev/null +++ b/test/00-setup.js @@ -0,0 +1,2 @@ +Error.stackTraceLimit = 1 + diff --git a/test/02-test-rect.js b/test/02-test-rect.js index 39693f5..0ae59f7 100644 --- a/test/02-test-rect.js +++ b/test/02-test-rect.js @@ -64,6 +64,13 @@ describe('rect', function(){ describe('#split(rect, east)', function(){ var s0 = rect.split(east) var s1 = east.split(rect) + + console.log("\n") + console.log(rect+"") + console.log(east+"") + console.log(s0.map(function(r){ return r.toString() })) + console.log(s1.map(function(r){ return r.toString() })) + it('splits on all 4 sides', function(){ assert.equal(ALL, sides(s0) | sides(s1)) }) @@ -92,13 +99,16 @@ describe('rect', function(){ describe('#split(rect, east_edge)', function(){ var s0 = rect.split(east_edge) var s1 = east_edge.split(rect) - - console.log("\n") - console.log(rect+"") - console.log(east_edge+"") - console.log(s0.map(function(r){ return r.toString() })) - console.log(s1.map(function(r){ return r.toString() })) - + it('has no degenerate vectors', function(){ + s0.forEach(function(r){ + assert.notEqual(0, r.x.magnitude()) + assert.notEqual(0, r.y.magnitude()) + }) + s1.forEach(function(r){ + assert.notEqual(0, r.x.magnitude()) + assert.notEqual(0, r.y.magnitude()) + }) + }) it('splits on all 4 sides', function(){ assert.equal(ALL, sides(s0) | sides(s1)) }) @@ -110,7 +120,35 @@ describe('rect', function(){ }) }) + return + describe('#split(rect, south)', function(){ + var s0 = rect.split(south) + var s1 = south.split(rect) + it('splits on all 4 sides', function(){ + assert.equal(ALL, sides(s0) | sides(s1)) + }) + it('rect is front/left/right', function(){ + assert.equal(FRONT | LEFT | RIGHT, sides(s0)) + }) + it('south is back/left/right', function(){ + assert.equal(BACK | LEFT | RIGHT, sides(s1)) + }) + }) + + describe('#split(rect, corner)', function(){ + var s0 = rect.split(corner) + var s1 = corner.split(rect) + + it('splits on all 4 sides', function(){ + // assert.equal(ALL, sides(s0) | sides(s1)) + }) + it('rect is front/left/right', function(){ + // assert.equal(FRONT | LEFT | RIGHT, sides(s0)) + }) + it('corner is back/left/right', function(){ +// assert.equal(BACK| LEFT | RIGHT, sides(s1)) + }) + }) + }) -/* -*/ -- cgit v1.2.3-70-g09d2 From c3d855b3f0b6af000c0d359da6a2b774bcd0a5d5 Mon Sep 17 00:00:00 2001 From: Julie Lala Date: Wed, 23 Jul 2014 15:15:21 -0400 Subject: handling coplanar walls correctly --- .../assets/javascripts/rectangles/models/rect.js | 43 ++++++++++---- .../assets/javascripts/rectangles/models/vec2.js | 3 + test/01-test-vec2.js | 7 +++ test/02-test-rect.js | 65 +++++++++++++++++----- 4 files changed, 93 insertions(+), 25 deletions(-) (limited to 'public/assets/javascripts/rectangles/models/rect.js') diff --git a/public/assets/javascripts/rectangles/models/rect.js b/public/assets/javascripts/rectangles/models/rect.js index f724ecc..c14d62c 100644 --- a/public/assets/javascripts/rectangles/models/rect.js +++ b/public/assets/javascripts/rectangles/models/rect.js @@ -143,23 +143,46 @@ var x_intervals = this.x.split( r.x, LEFT, RIGHT ) var y_intervals = this.y.split( r.y, FRONT, BACK ) - x_intervals.forEach(function(x){ - y_intervals.forEach(function(y){ + x_intervals.forEach(function(x, i){ + y_intervals.forEach(function(y, i){ var rn = new Rect(x[0], y[0]) rn.id = rz.id rn.sides = ((x[1] | y[1]) & sides) - if (r.x.contains(rn.x.a)) { - rn.sides &= ~ LEFT + if (r.x.contains(rn.x.a) && r.x.contains(rn.x.b)) { + if (rz.y.a == rn.y.a && r.y.containsCenter(rn.y.a)) { // top edges + rn.sides &= ~ FRONT + } + if (rz.y.b == rn.y.b && r.y.containsCenter(rn.y.b)) { // bottom edges + rn.sides &= ~ BACK + } } - if (r.x.contains(rn.x.b)) { - rn.sides &= ~ RIGHT + + if (r.y.contains(rn.y.a) && r.y.contains(rn.y.b)) { + if (rz.x.a == rn.x.a && r.x.containsCenter(rn.x.a)) { // left edges + rn.sides &= ~ LEFT + } + + if (rz.x.b == rn.x.b && r.x.containsCenter(rn.x.b) ) { // right edges + rn.sides &= ~ RIGHT + } } -// if (r.y.contains(rn.y.a)) { -// rn.sides &= ~ FRONT + +// if (rz.x.contains(r.x.a) || rz.x.contains(r.x.b)) { +// if (r.x.contains(rn.x.b)) { +// rn.sides &= ~ LEFT +// } +// if (r.x.contains(rn.x.b)) { +// rn.sides &= ~ RIGHT +// } // } -// if (r.y.contains(rn.y.a)) { -// rn.sides &= ~ BACK +// if (rz.y.contains(r.y.a) || rz.y.contains(r.y.b)) { +// if (r.y.contains(rn.y.a)) { +// rn.sides &= ~ FRONT +// } +// if (r.y.contains(rn.y.b)) { +// rn.sides &= ~ BACK +// } // } // if (r.intersects(rn)) { diff --git a/public/assets/javascripts/rectangles/models/vec2.js b/public/assets/javascripts/rectangles/models/vec2.js index 447c7a3..5c2b519 100644 --- a/public/assets/javascripts/rectangles/models/vec2.js +++ b/public/assets/javascripts/rectangles/models/vec2.js @@ -70,6 +70,9 @@ vec2.prototype.contains = function(n){ return this.a <= n && n <= this.b } + vec2.prototype.containsCenter = function(n){ + return this.a < n && n < this.b + } vec2.prototype.containsDisc = function(n,r){ return this.a <= n-r && n+r <= this.b } diff --git a/test/01-test-vec2.js b/test/01-test-vec2.js index 054d37b..b38f052 100644 --- a/test/01-test-vec2.js +++ b/test/01-test-vec2.js @@ -38,6 +38,13 @@ describe('vec2', function(){ assert.equal(false, vec.contains( -5 )); assert.equal(false, vec.contains( 15 )); }) + it('containsCenter itself', function(){ + assert.equal(true, vec.containsCenter( 5 )); + }) + it('does not containsCenter its endpoints', function(){ + assert.equal(false, vec.containsCenter( 0 )); + assert.equal(false, vec.containsCenter( 10 )); + }) it('intersects when only startpoint matches', function(){ assert.equal(true, vec.intersects( new vec2(-5, 0) )); }) diff --git a/test/02-test-rect.js b/test/02-test-rect.js index 0ae59f7..55f1ec9 100644 --- a/test/02-test-rect.js +++ b/test/02-test-rect.js @@ -60,17 +60,15 @@ describe('rect', function(){ return prev | curr.sides }, 0) } + /* + console.log(s0.map(function(r){ return r.toString() })) + console.log(s1.map(function(r){ return r.toString() })) + */ describe('#split(rect, east)', function(){ var s0 = rect.split(east) var s1 = east.split(rect) - console.log("\n") - console.log(rect+"") - console.log(east+"") - console.log(s0.map(function(r){ return r.toString() })) - console.log(s1.map(function(r){ return r.toString() })) - it('splits on all 4 sides', function(){ assert.equal(ALL, sides(s0) | sides(s1)) }) @@ -99,6 +97,7 @@ describe('rect', function(){ describe('#split(rect, east_edge)', function(){ var s0 = rect.split(east_edge) var s1 = east_edge.split(rect) + it('has no degenerate vectors', function(){ s0.forEach(function(r){ assert.notEqual(0, r.x.magnitude()) @@ -113,17 +112,17 @@ describe('rect', function(){ assert.equal(ALL, sides(s0) | sides(s1)) }) it('rect is front/back/left', function(){ - assert.equal(FRONT | BACK | LEFT, sides(s0)) + assert.equal(ALL, sides(s0)) }) it('east is front/back/right', function(){ assert.equal(FRONT | BACK | RIGHT, sides(s1)) }) }) - return describe('#split(rect, south)', function(){ var s0 = rect.split(south) var s1 = south.split(rect) + it('splits on all 4 sides', function(){ assert.equal(ALL, sides(s0) | sides(s1)) }) @@ -135,18 +134,54 @@ describe('rect', function(){ }) }) + describe('#split(rect, south_in)', function(){ + var s0 = rect.split(south_in) + var s1 = south_in.split(rect) + it('splits on all 4 sides', function(){ + assert.equal(ALL, sides(s0) | sides(s1)) + }) + it('rect is has all sides', function(){ + assert.equal(ALL, sides(s0)) + }) + it('south_in only has left/right', function(){ + assert.equal(LEFT | RIGHT, sides(s1)) + }) + }) + + describe('#split(rect, south_edge)', function(){ + var s0 = rect.split(south_edge) + var s1 = south_edge.split(rect) + + it('has no degenerate vectors', function(){ + s0.forEach(function(r){ + assert.notEqual(0, r.x.magnitude()) + assert.notEqual(0, r.y.magnitude()) + }) + s1.forEach(function(r){ + assert.notEqual(0, r.x.magnitude()) + assert.notEqual(0, r.y.magnitude()) + }) + }) + it('splits on all 4 sides', function(){ + assert.equal(ALL, sides(s0) | sides(s1)) + }) + it('rect has all sides', function(){ + assert.equal(ALL, sides(s0)) + }) + it('south is back/left/right', function(){ + assert.equal(BACK | LEFT | RIGHT, sides(s1)) + }) + }) + describe('#split(rect, corner)', function(){ var s0 = rect.split(corner) var s1 = corner.split(rect) - it('splits on all 4 sides', function(){ - // assert.equal(ALL, sides(s0) | sides(s1)) - }) - it('rect is front/left/right', function(){ - // assert.equal(FRONT | LEFT | RIGHT, sides(s0)) + it('rect splits on all 4 sides', function(){ + assert.equal(ALL, sides(s0)) }) - it('corner is back/left/right', function(){ -// assert.equal(BACK| LEFT | RIGHT, sides(s1)) + it('corner splits on all 4 sides', function(){ + assert.equal(ALL, sides(s1)) }) }) -- cgit v1.2.3-70-g09d2 From c7e27b743eb8488ec71adaf365056ff500b458ab Mon Sep 17 00:00:00 2001 From: Julie Lala Date: Wed, 23 Jul 2014 17:03:04 -0400 Subject: preparing modules for clip test --- .../javascripts/rectangles/engine/rooms/_rooms.js | 196 +++++--- .../javascripts/rectangles/engine/rooms/builder.js | 529 +++++++++++---------- .../javascripts/rectangles/engine/rooms/clipper.js | 189 ++++---- .../assets/javascripts/rectangles/models/rect.js | 28 +- .../assets/javascripts/rectangles/models/room.js | 37 +- .../assets/javascripts/rectangles/models/tree.js | 85 ++-- public/assets/javascripts/rectangles/util/sort.js | 156 +++--- public/assets/javascripts/rectangles/util/uid.js | 31 +- test/03-test-clipping.js | 21 + 9 files changed, 719 insertions(+), 553 deletions(-) create mode 100644 test/03-test-clipping.js (limited to 'public/assets/javascripts/rectangles/models/rect.js') diff --git a/public/assets/javascripts/rectangles/engine/rooms/_rooms.js b/public/assets/javascripts/rectangles/engine/rooms/_rooms.js index e0033e3..f7fad3e 100644 --- a/public/assets/javascripts/rectangles/engine/rooms/_rooms.js +++ b/public/assets/javascripts/rectangles/engine/rooms/_rooms.js @@ -1,99 +1,139 @@ -var Rooms = new function(){ - - var base = this - - base.list = {} - base.walls = {} - base.regions = [] +(function(){ - base.init = function(){ - Rooms.builder.init() - Rooms.clipper.init() - Rooms.mover.init() + var vec2, Rect, Room, sort, UidGenerator, _ + if ('window' in this) { + vec2 = window.vec2 + Rect = window.Rect + Room = window.Room + sort = window.sort + UidGenerator = window.UidGenerator + _ = window._ + } + else { + vec2 = require('../../models/vec2') + Rect = require('../../models/rect') + Room = require('../../models/room') + sort = require('../../util/sort') + UidGenerator = require('../../util/uid') + _ = require('lodash') + FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20 + TOP = CEILING, BOTTOM = FLOOR + function sidesToString(sides){ + var s = "" + if (sides & FRONT) s += "front " + if (sides & BACK) s += "back " + if (sides & LEFT) s += "left " + if (sides & RIGHT) s += "right " + if (sides & TOP) s += "top " + if (sides & BOTTOM) s += "bottom " + return s + } } + + var Rooms = new function(){ + + var base = this - base.filter = function(f){ - return _.values(base.list).filter(f) - } + base.list = {} + base.walls = {} + base.regions = [] + + base.init = function(){ + Rooms.builder.init() + Rooms.clipper.init() + Rooms.mover.init() + } - base.add = function(room){ - base.list[room.id] = room - } + base.filter = function(f){ + return _.values(base.list).filter(f) + } - base.add_with_rect = function(rect){ - var room = new Room({ - rect: rect, - height: 500 - }) - base.add(room) - return room - } + base.add = function(room){ + base.list[room.id] = room + } - base.remove = function(room){ - delete base.list[room.id] - Rooms.clipper.update() - } + base.add_with_rect = function(rect){ + var room = new Room({ + rect: rect, + height: 500 + }) + base.add(room) + return room + } - base.removeAll = function(){ - base.list = {} - base.regions = [] - Rooms.clipper.update() - } + base.remove = function(room){ + delete base.list[room.id] + Rooms.clipper.update() + } - base.count = function(){ - return this.values().length - } + base.removeAll = function(){ + base.list = {} + base.regions = [] + Rooms.clipper.update() + } - base.forEach = function(f){ - return base.values().forEach(f) - } + base.count = function(){ + return this.values().length + } - base.map = function(f){ - return base.values().map(f) - } + base.forEach = function(f){ + return base.values().forEach(f) + } - base.values = function(){ - return _.values(base.list) - } + base.map = function(f){ + return base.values().map(f) + } - base.serialize = function(){ - var rooms = base.map(function(room){ - return room.serialize() - }) - return rooms - } + base.values = function(){ + return _.values(base.list) + } - base.deserialize = function(rooms_data){ - rooms_data.forEach(function(data){ - var rect = new Rect(data.rect.x[0], data.rect.y[0], data.rect.x[1], data.rect.y[1]) - var room = new Room({ - id: data.id, - rect: rect, - height: data.height + base.serialize = function(){ + var rooms = base.map(function(room){ + return room.serialize() }) - base.add(room) - }) - Rooms.clipper.update() - } + return rooms + } + + base.deserialize = function(rooms_data){ + rooms_data.forEach(function(data){ + var rect = new Rect(data.rect.x[0], data.rect.y[0], data.rect.x[1], data.rect.y[1]) + var room = new Room({ + id: data.id, + rect: rect, + height: data.height + }) + base.add(room) + }) + Rooms.clipper.update() + } - base.serializeWalls = function(){ - return [] - } + base.serializeWalls = function(){ + return [] + } - base.deserializeWalls = function(walls_data){ - return [] - } + base.deserializeWalls = function(walls_data){ + return [] + } + + base.uid = UidGenerator(base.list) - base.uid = UidGenerator(base.list) + base.sorted_by_position = function(){ + return sort.rooms_by_position( base.values() ) + } + base.sorted_by_height = function(){ + return sort.rooms_by_height( base.values() ) + } + base.sorted_by_area = function(){ + return sort.rooms_by_area( base.values() ) + } - base.sorted_by_position = function(){ - return sort_rooms_by_position( base.values() ) } - base.sorted_by_height = function(){ - return sort_rooms_by_height( base.values() ) + + if ('window' in this) { + window.Rooms = Rooms } - base.sorted_by_area = function(){ - return sort_rooms_by_area( base.values() ) + else { + module.exports = Rooms } - -} +})() diff --git a/public/assets/javascripts/rectangles/engine/rooms/builder.js b/public/assets/javascripts/rectangles/engine/rooms/builder.js index 49e55dc..6b565c2 100644 --- a/public/assets/javascripts/rectangles/engine/rooms/builder.js +++ b/public/assets/javascripts/rectangles/engine/rooms/builder.js @@ -1,295 +1,328 @@ +(function(){ -Rooms.builder = new function(){ - var base = this + var vec2, Rect, Room, sort, UidGenerator, _ + if ('window' in this) { + vec2 = window.vec2 + Rect = window.Rect + Room = window.Room + sort = window.sort + UidGenerator = window.UidGenerator + _ = window._ + } + else { + vec2 = require('../../models/vec2') + Rect = require('../../models/rect') + Room = require('../../models/room') + sort = require('../../util/sort') + UidGenerator = require('../../util/uid') + _ = require('lodash') + FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20 + TOP = CEILING, BOTTOM = FLOOR + function sidesToString(sides){ + var s = "" + if (sides & FRONT) s += "front " + if (sides & BACK) s += "back " + if (sides & LEFT) s += "left " + if (sides & RIGHT) s += "right " + if (sides & TOP) s += "top " + if (sides & BOTTOM) s += "bottom " + return s + } + } + + + Rooms.builder = new function(){ + var base = this - var els = [] + var els = [] - base.init = function(){ - base.bind() - } + base.init = function(){ + base.bind() + } - base.bind = function(){ - app.on("clip", rebuild) - } + base.bind = function(){ + app.on("clip", rebuild) + } - function rebuild(){ - if (window.scene) { - clear() - build() - bind() + function rebuild(){ + if (window.scene) { + clear() + build() + bind() + } } - } - function build (){ - Rooms.regions.forEach(function(region){ - build_walls(region).forEach(function(el){ - els.push(el) - scene.add(el) + function build (){ + Rooms.regions.forEach(function(region){ + build_walls(region).forEach(function(el){ + els.push(el) + scene.add(el) + }) }) - }) - Rooms.sorted_by_height().forEach(function(room){ - build_floors(room).forEach(function(el){ - els.push(el) - scene.add(el) + Rooms.sorted_by_height().forEach(function(room){ + build_floors(room).forEach(function(el){ + els.push(el) + scene.add(el) + }) }) - }) - } + } - function bind (){ - Rooms.forEach(function(room){ - room.walls = room.group_mx_walls() - room.walls.forEach(function(wall){ - Rooms.walls[ wall.id ] = wall - wall.bind() - wall.randomize_colors() + function bind (){ + Rooms.forEach(function(room){ + room.walls = room.group_mx_walls() + room.walls.forEach(function(wall){ + Rooms.walls[ wall.id ] = wall + wall.bind() + wall.randomize_colors() + }) }) - }) - } + } - function clear (){ - els.forEach(function(el){ - scene.remove(el) - el.destroy && el.destroy() - }) - els = [] - } + function clear (){ + els.forEach(function(el){ + scene.remove(el) + el.destroy && el.destroy() + }) + els = [] + } - function build_walls (region){ - var room = Rooms.list[ region.id ] + function build_walls (region){ + var room = Rooms.list[ region.id ] - var list = [], el = null + var list = [], el = null - var width = region.x.length() - var depth = region.y.length() - var height = room.height + var width = region.x.length() + var depth = region.y.length() + var height = room.height - if (region.sides & FRONT) { - el = make_wall('.front') - el.width = width - el.height = height - el.rotationY = PI - el.x = region.x.a + width/2 - el.y = height/2 - el.z = region.y.a - el.rect = region - el.side = FRONT - room.mx_walls.push(el) - list.push(el) - } - if (region.sides & BACK) { - var el = make_wall('.back') - el.width = width - el.height = height - el.rotationY = 0 - el.x = region.x.b - width/2 - el.y = height/2 - el.z = region.y.b - el.rect = region - el.side = BACK - room.mx_walls.push(el) - list.push(el) - } - if (region.sides & LEFT) { - el = make_wall('.left') - el.rotationY = HALF_PI - el.height = height - el.width = depth - el.x = region.x.a - el.y = height/2 - el.z = region.y.a + depth/2 - el.rect = region - el.side = LEFT - room.mx_walls.push(el) - list.push(el) - } - if (region.sides & RIGHT) { - el = make_wall('.right') - el.rotationY = -HALF_PI - el.height = height - el.width = depth - el.x = region.x.b - el.y = height/2 - el.z = region.y.b - depth/2 - el.rect = region - el.side = RIGHT - room.mx_walls.push(el) - list.push(el) - } + if (region.sides & FRONT) { + el = make_wall('.front') + el.width = width + el.height = height + el.rotationY = PI + el.x = region.x.a + width/2 + el.y = height/2 + el.z = region.y.a + el.rect = region + el.side = FRONT + room.mx_walls.push(el) + list.push(el) + } + if (region.sides & BACK) { + var el = make_wall('.back') + el.width = width + el.height = height + el.rotationY = 0 + el.x = region.x.b - width/2 + el.y = height/2 + el.z = region.y.b + el.rect = region + el.side = BACK + room.mx_walls.push(el) + list.push(el) + } + if (region.sides & LEFT) { + el = make_wall('.left') + el.rotationY = HALF_PI + el.height = height + el.width = depth + el.x = region.x.a + el.y = height/2 + el.z = region.y.a + depth/2 + el.rect = region + el.side = LEFT + room.mx_walls.push(el) + list.push(el) + } + if (region.sides & RIGHT) { + el = make_wall('.right') + el.rotationY = -HALF_PI + el.height = height + el.width = depth + el.x = region.x.b + el.y = height/2 + el.z = region.y.b - depth/2 + el.rect = region + el.side = RIGHT + room.mx_walls.push(el) + list.push(el) + } - return list - } + return list + } - function build_floors(room){ - var list = [], el = null + function build_floors(room){ + var list = [], el = null - var constructed = room.intersects.filter(function(room){ return room.constructed }) - sort_rooms_by_height(constructed) + var constructed = room.intersects.filter(function(room){ return room.constructed }) + sort.rooms_by_height(constructed) - if (constructed.length > 0) { - // render the regions that don't intersect with anything we've already rendered - // if the height is different, calculate the overlapping sides and render half-walls - room.regions.forEach(function(region){ - var intersected = false - for (var i = 0; i < constructed.length; i++) { - if (constructed[i].rect.contains(region)) { - intersected = true - // r.sides = 0xf - // half_sides - } - else if (constructed[i].rect.intersects(region)) { - intersected = true - if (room.height < constructed[i].height) { - var ceiling_walls = make_ceiling_walls( room, constructed[i], region ) - list = list.concat(ceiling_walls) + if (constructed.length > 0) { + // render the regions that don't intersect with anything we've already rendered + // if the height is different, calculate the overlapping sides and render half-walls + room.regions.forEach(function(region){ + var intersected = false + for (var i = 0; i < constructed.length; i++) { + if (constructed[i].rect.contains(region)) { + intersected = true + // r.sides = 0xf + // half_sides + } + else if (constructed[i].rect.intersects(region)) { + intersected = true + if (room.height < constructed[i].height) { + var ceiling_walls = make_ceiling_walls( room, constructed[i], region ) + list = list.concat(ceiling_walls) + } } } - } - if (! intersected) { - el = make_floor(room, region) - list.push( el ) - room.mx_floor.push(el) + if (! intersected) { + el = make_floor(room, region) + list.push( el ) + room.mx_floor.push(el) - el = make_ceiling(room, region) - list.push( el ) - room.mx_ceiling.push(el) - } - }) + el = make_ceiling(room, region) + list.push( el ) + room.mx_ceiling.push(el) + } + }) - } - else { - // render floor and ceiling for the entire rectangle - el = make_floor(room, room.rect) - list.push( el ) - room.mx_floor.push(el) + } + else { + // render floor and ceiling for the entire rectangle + el = make_floor(room, room.rect) + list.push( el ) + room.mx_floor.push(el) - el = make_ceiling(room, room.rect) - list.push( el ) - room.mx_ceiling.push(el) - } + el = make_ceiling(room, room.rect) + list.push( el ) + room.mx_ceiling.push(el) + } - room.constructed = true - return list - } + room.constructed = true + return list + } - function make_ceiling_walls( lo, hi, region ){ - var list = [] + function make_ceiling_walls( lo, hi, region ){ + var list = [] - var width = region.x.length() - var depth = region.y.length() - var height = hi.height - lo.height + var width = region.x.length() + var depth = region.y.length() + var height = hi.height - lo.height - if (! (region.half_sides & LEFT) && region.x.a == hi.rect.x.a) { - el = make_wall('.left') - el.rotationY = HALF_PI - el.height = height - el.width = depth - el.x = region.x.a - el.y = lo.height + height/2 - el.z = region.y.a + depth/2 - el.rect = region - list.push(el) - hi.mx_walls.push(el) - region.half_sides |= LEFT - el.half_side = LEFT - } + if (! (region.half_sides & LEFT) && region.x.a == hi.rect.x.a) { + el = make_wall('.left') + el.rotationY = HALF_PI + el.height = height + el.width = depth + el.x = region.x.a + el.y = lo.height + height/2 + el.z = region.y.a + depth/2 + el.rect = region + list.push(el) + hi.mx_walls.push(el) + region.half_sides |= LEFT + el.half_side = LEFT + } - if (! (region.half_sides & RIGHT) && region.x.b == hi.rect.x.b) { - el = make_wall('.right') - el.rotationY = -HALF_PI - el.height = height - el.width = depth - el.x = region.x.b - el.y = lo.height + height/2 - el.z = region.y.b - depth/2 - el.rect = region - list.push(el) - hi.mx_walls.push(el) - region.half_sides |= RIGHT - el.half_side = RIGHT + if (! (region.half_sides & RIGHT) && region.x.b == hi.rect.x.b) { + el = make_wall('.right') + el.rotationY = -HALF_PI + el.height = height + el.width = depth + el.x = region.x.b + el.y = lo.height + height/2 + el.z = region.y.b - depth/2 + el.rect = region + list.push(el) + hi.mx_walls.push(el) + region.half_sides |= RIGHT + el.half_side = RIGHT + } + + if (! (region.half_sides & FRONT) && region.y.a == hi.rect.y.a) { + el = make_wall('.front') + el.width = width + el.height = height + el.rotationY = PI + el.x = region.x.a + width/2 + el.y = lo.height + height/2 + el.z = region.y.a + el.rect = region + list.push(el) + hi.mx_walls.push(el) + region.half_sides |= FRONT + el.half_side = FRONT + } + + if (! (region.half_sides & BACK) && region.y.b == hi.rect.y.b) { + el = make_wall('.back') + el.width = width + el.height = height + el.rotationY = 0 + el.x = region.x.b - width/2 + el.y = lo.height + height/2 + el.z = region.y.b + el.rect = region + list.push(el) + hi.mx_walls.push(el) + region.half_sides |= BACK + el.half_side = BACK + } + return list } - if (! (region.half_sides & FRONT) && region.y.a == hi.rect.y.a) { - el = make_wall('.front') + function make_floor(room, region){ + var width = region.x.length() + var depth = region.y.length() + + var el = make_wall('.floor') + el.height = depth el.width = width - el.height = height - el.rotationY = PI el.x = region.x.a + width/2 - el.y = lo.height + height/2 - el.z = region.y.a + el.y = 0 + el.z = region.y.a + depth/2 + el.rotationX = PI/2 el.rect = region - list.push(el) - hi.mx_walls.push(el) - region.half_sides |= FRONT - el.half_side = FRONT + el.side = FLOOR + return el } + function make_ceiling(room, region){ + var width = region.x.length() + var depth = region.y.length() + var height = room.height - if (! (region.half_sides & BACK) && region.y.b == hi.rect.y.b) { - el = make_wall('.back') + var el = make_wall('.ceiling') + el.height = depth el.width = width - el.height = height - el.rotationY = 0 - el.x = region.x.b - width/2 - el.y = lo.height + height/2 - el.z = region.y.b + el.x = region.x.a + width/2 + el.y = height + el.z = region.y.a + depth/2 + el.rotationX = -PI/2 el.rect = region - list.push(el) - hi.mx_walls.push(el) - region.half_sides |= BACK - el.half_side = BACK + el.side = CEILING + return el } - return list - } - function make_floor(room, region){ - var width = region.x.length() - var depth = region.y.length() - - var el = make_wall('.floor') - el.height = depth - el.width = width - el.x = region.x.a + width/2 - el.y = 0 - el.z = region.y.a + depth/2 - el.rotationX = PI/2 - el.rect = region - el.side = FLOOR - return el - } - function make_ceiling(room, region){ - var width = region.x.length() - var depth = region.y.length() - var height = room.height + function make_wall(klass){ + var el = new MX.Object3D(".face" + (klass || "")) + el.width = el.height = el.scaleX = el.scaleY = el.scaleZ = 1 + el.z = el.y = el.x = 0 + el.side = 0 + el.type = "Face" + el.el.style.opacity = 1.0 + el.side = 0 + el.rect = null + el.destroy = function(){ + this.el = this.rect = null + } - var el = make_wall('.ceiling') - el.height = depth - el.width = width - el.x = region.x.a + width/2 - el.y = height - el.z = region.y.a + depth/2 - el.rotationX = -PI/2 - el.rect = region - el.side = CEILING - return el - } + // possible if walls are opaque + // el.el.classList.add("backface-hidden") - function make_wall(klass){ - var el = new MX.Object3D(".face" + (klass || "")) - el.width = el.height = el.scaleX = el.scaleY = el.scaleZ = 1 - el.z = el.y = el.x = 0 - el.side = 0 - el.type = "Face" - el.el.style.opacity = 1.0 - el.side = 0 - el.rect = null - el.destroy = function(){ - this.el = this.rect = null + return el } - // possible if walls are opaque - // el.el.classList.add("backface-hidden") - - return el } -} - +})() diff --git a/public/assets/javascripts/rectangles/engine/rooms/clipper.js b/public/assets/javascripts/rectangles/engine/rooms/clipper.js index e2bb894..cd45479 100644 --- a/public/assets/javascripts/rectangles/engine/rooms/clipper.js +++ b/public/assets/javascripts/rectangles/engine/rooms/clipper.js @@ -1,107 +1,134 @@ +(function(){ -Rooms.clipper = new function(){ - var base = this - - base.init = function(){ - base.bind() - base.update() + var Rooms, Tree, sort + if ('window' in this) { + Rooms = window.Rooms + Tree = window.Tree + sort = window.sort } - - base.bind = function(){ - map.ui && map.ui.mouse.tube.on("up", function(){ base.update() }) + else { + Rooms = require('./_rooms') + Tree = require('../../models/tree') + sort = require('../../util/sort') + FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20 + TOP = CEILING, BOTTOM = FLOOR + function sidesToString(sides){ + var s = "" + if (sides & FRONT) s += "front " + if (sides & BACK) s += "back " + if (sides & LEFT) s += "left " + if (sides & RIGHT) s += "right " + if (sides & TOP) s += "top " + if (sides & BOTTOM) s += "bottom " + return s + } } - base.update = function(){ - base.solve_rects() - app.tube("clip") - } - - var rooms, regions + Rooms.clipper = new function(){ + var base = this + + base.init = function(){ + base.bind() + base.update() + } - // Given a set of overlapping rooms, clip any intersections, then cull any duplicate polygons - base.solve_rects = function(){ - if (Rooms.count() == 0) { - Rooms.regions = regions = [] - return + base.bind = function(){ + map.ui && map.ui.mouse.tube.on("up", function(){ base.update() }) + } + + base.update = function(){ + base.solve_rects() + app.tube("clip") } + + var rooms, regions + + // Given a set of overlapping rooms, clip any intersections, then cull any duplicate polygons + base.solve_rects = function(){ + if (Rooms.count() == 0) { + Rooms.regions = regions = [] + return + } - base.reset_rects() - base.clip_rects() - base.cull_rects() + base.reset_rects() + base.clip_rects() + base.cull_rects() - Rooms.regions = sort_rects_by_position(regions) - } + Rooms.regions = sort.rects_by_position(regions) + } - // Reset the clipping/culling states of each of the rooms - base.reset_rects = function(){ - Rooms.forEach(function(room){ - room.reset() - }) - } + // Reset the clipping/culling states of each of the rooms + base.reset_rects = function(){ + Rooms.forEach(function(room){ + room.reset() + }) + } - // Compare each room to the rooms it overlaps, and subdivide - base.clip_rects = function(){ - var rooms = Rooms.sorted_by_position() - regions = [] + // Compare each room to the rooms it overlaps, and subdivide + base.clip_rects = function(){ + var rooms = Rooms.sorted_by_position() + regions = [] - var left, right - for (var i = 0; i < rooms.length; i++) { - left = rooms[i] - for (var j = i+1; j < rooms.length; j++) { - right = rooms[j] - if (left.rect.intersects(right.rect)) { - left.clipTo(right.rect) - right.clipTo(left.rect) - left.intersects.push(right) - right.intersects.push(left) - } - if (left.rect.x.b < right.rect.x.a) { - break + var left, right + for (var i = 0; i < rooms.length; i++) { + left = rooms[i] + for (var j = i+1; j < rooms.length; j++) { + right = rooms[j] + if (left.rect.intersects(right.rect)) { + left.clipTo(right.rect) + right.clipTo(left.rect) + left.intersects.push(right) + right.intersects.push(left) + } + if (left.rect.x.b < right.rect.x.a) { + break + } } } + for (var i = 0; i < rooms.length; i++) { + rooms[i].regions = rooms[i].regions.filter(function(r){ return !!r }) + regions = regions.concat(rooms[i].regions) + } } - for (var i = 0; i < rooms.length; i++) { - rooms[i].regions = rooms[i].regions.filter(function(r){ return !!r }) - regions = regions.concat(rooms[i].regions) - } - } - // Find overlapping regions (of the same size) and dedupe - base.cull_rects = function(){ - regions = sort_rects_by_area( regions ) + // Find overlapping regions (of the same size) and dedupe + base.cull_rects = function(){ + regions = sort.rects_by_area( regions ) - var ty = new Tree (regions[0].y.a, [regions[0]]) - var tx = new Tree (regions[0].x.a, ty) - var ttx, tty + var ty = new Tree (regions[0].y.a, [regions[0]]) + var tx = new Tree (regions[0].x.a, ty) + var ttx, tty - for (var i = 1; i < regions.length; i++) { - ttx = tx.add (regions[i].x.a, null) - if (ttx.data) { - tty = ttx.data.add (regions[i].y.a, null) - // duplicate polygon? - if (tty.data) { - tty.data.forEach(function(yy, ii){ - if (yy.intersects(regions[i])) { - if (yy.area() > regions[i].area()) { - regions[i].dupe = true - } - else { - yy.dupe = true - tty.data[ii] = regions[i] + for (var i = 1; i < regions.length; i++) { + ttx = tx.add (regions[i].x.a, null) + if (ttx.data) { + tty = ttx.data.add (regions[i].y.a, null) + // duplicate polygon? + if (tty.data) { + tty.data.forEach(function(yy, ii){ + if (yy.intersects(regions[i])) { + if (yy.area() > regions[i].area()) { + regions[i].dupe = true + } + else { + yy.dupe = true + tty.data[ii] = regions[i] + } } - } - }) + }) + } + else { + tty.data = [regions[i]] + } } else { - tty.data = [regions[i]] + ttx.data = new Tree (regions[i].y.a, [regions[i]]) } } - else { - ttx.data = new Tree (regions[i].y.a, [regions[i]]) - } } + + return base } - return base -} +})() diff --git a/public/assets/javascripts/rectangles/models/rect.js b/public/assets/javascripts/rectangles/models/rect.js index c14d62c..3341239 100644 --- a/public/assets/javascripts/rectangles/models/rect.js +++ b/public/assets/javascripts/rectangles/models/rect.js @@ -140,15 +140,20 @@ var splits = [] var sides = this.sides + // bisect (or trisect) two overlapping rectangles var x_intervals = this.x.split( r.x, LEFT, RIGHT ) var y_intervals = this.y.split( r.y, FRONT, BACK ) + // generate rectangular regions by crossing the two sets of vectors x_intervals.forEach(function(x, i){ y_intervals.forEach(function(y, i){ var rn = new Rect(x[0], y[0]) rn.id = rz.id rn.sides = ((x[1] | y[1]) & sides) + rn.focused = rz.focused + splits.push(rn) + // cull extra walls from overlapping regions if (r.x.contains(rn.x.a) && r.x.contains(rn.x.b)) { if (rz.y.a == rn.y.a && r.y.containsCenter(rn.y.a)) { // top edges rn.sides &= ~ FRONT @@ -168,30 +173,9 @@ } } -// if (rz.x.contains(r.x.a) || rz.x.contains(r.x.b)) { -// if (r.x.contains(rn.x.b)) { -// rn.sides &= ~ LEFT -// } -// if (r.x.contains(rn.x.b)) { -// rn.sides &= ~ RIGHT -// } -// } -// if (rz.y.contains(r.y.a) || rz.y.contains(r.y.b)) { -// if (r.y.contains(rn.y.a)) { -// rn.sides &= ~ FRONT -// } -// if (r.y.contains(rn.y.b)) { -// rn.sides &= ~ BACK -// } -// } - -// if (r.intersects(rn)) { -// rn.sides = 0 -// } - rn.focused = rz.focused - splits.push(rn) }) }) + return splits } diff --git a/public/assets/javascripts/rectangles/models/room.js b/public/assets/javascripts/rectangles/models/room.js index 61a7447..748b244 100644 --- a/public/assets/javascripts/rectangles/models/room.js +++ b/public/assets/javascripts/rectangles/models/room.js @@ -1,4 +1,28 @@ -window.Room = (function(){ + +(function(){ + var vec2, Rect, sort + if ('window' in this) { + vec2 = window.vec2 + Rect = window.Rect + sort = window.sort + } + else { + vec2 = require('./vec2') + Rect = require('./rect') + sort = require('../util/sort') + FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20 + TOP = CEILING, BOTTOM = FLOOR + function sidesToString(sides){ + var s = "" + if (sides & FRONT) s += "front " + if (sides & BACK) s += "back " + if (sides & LEFT) s += "left " + if (sides & RIGHT) s += "right " + if (sides & TOP) s += "top " + if (sides & BOTTOM) s += "bottom " + return s + } + } var Room = function(opt){ this.id = opt.id || Rooms.uid("room_") @@ -81,10 +105,10 @@ window.Room = (function(){ var side = pair[0], els = pair[1] if (side & LEFT_RIGHT) { - els.sort(compare_x) + els.sort(sort.compare_x) } else if (side & FRONT_BACK) { - els.sort(compare_z) + els.sort(sort.compare_z) } // wall holds state for the last wall we created/saw.. @@ -222,7 +246,12 @@ window.Room = (function(){ return collision } - return Room + if ('window' in this) { + window.Room = Room + } + else { + module.exports = Room + } })() diff --git a/public/assets/javascripts/rectangles/models/tree.js b/public/assets/javascripts/rectangles/models/tree.js index 8193988..7c698fe 100644 --- a/public/assets/javascripts/rectangles/models/tree.js +++ b/public/assets/javascripts/rectangles/models/tree.js @@ -1,37 +1,48 @@ -var Tree = function(n, data){ - this.lo = null - this.hi = null - this.value = n - this.data = data -} -Tree.prototype.find = function(n){ - if (n == this.value) return this - if (n < this.value) return this.lo ? this.lo.find(n) : this - if (n > this.value) return this.hi ? this.hi.find(n) : this -} -Tree.prototype.add = function(n, data){ - var closest = this.find(n) - if (n == closest.value) return closest - if (n < closest.value) return closest.lo = new Tree(n, data) - if (n > closest.value) return closest.hi = new Tree(n, data) -} -Tree.prototype.toArray = function(){ - var a = [] - if (this.lo) a = a.concat(this.lo.toArray()) - a.push(this.data) - if (this.hi) a = a.concat(this.hi.toArray()) - return a -} -Tree.prototype.toString = function(){ - var s = ""; - if (this.lo) s += this.lo.toString() - s += this.value + "," - if (this.hi) s += this.hi.toString() - return s -} -Tree.prototype.depth = function(){ - if (this.lo && this.hi) return 1 + max(this.lo.depth(), this.hi.depth()) - else if (this.lo) return 1 + this.lo.depth() - else if (this.hi) return 1 + this.hi.depth() - else return 0 -} +(function(){ + + var Tree = function(n, data){ + this.lo = null + this.hi = null + this.value = n + this.data = data + } + Tree.prototype.find = function(n){ + if (n == this.value) return this + if (n < this.value) return this.lo ? this.lo.find(n) : this + if (n > this.value) return this.hi ? this.hi.find(n) : this + } + Tree.prototype.add = function(n, data){ + var closest = this.find(n) + if (n == closest.value) return closest + if (n < closest.value) return closest.lo = new Tree(n, data) + if (n > closest.value) return closest.hi = new Tree(n, data) + } + Tree.prototype.toArray = function(){ + var a = [] + if (this.lo) a = a.concat(this.lo.toArray()) + a.push(this.data) + if (this.hi) a = a.concat(this.hi.toArray()) + return a + } + Tree.prototype.toString = function(){ + var s = ""; + if (this.lo) s += this.lo.toString() + s += this.value + "," + if (this.hi) s += this.hi.toString() + return s + } + Tree.prototype.depth = function(){ + if (this.lo && this.hi) return 1 + max(this.lo.depth(), this.hi.depth()) + else if (this.lo) return 1 + this.lo.depth() + else if (this.hi) return 1 + this.hi.depth() + else return 0 + } + + if ('window' in this) { + window.Tree = Tree + } + else { + module.exports = Tree + } + +})() diff --git a/public/assets/javascripts/rectangles/util/sort.js b/public/assets/javascripts/rectangles/util/sort.js index a0665ae..c0b5d54 100644 --- a/public/assets/javascripts/rectangles/util/sort.js +++ b/public/assets/javascripts/rectangles/util/sort.js @@ -1,86 +1,96 @@ +(function(){ - -function compare_rect_position(a,b){ - if (a[0].x.a < b[0].x.a) { - return -1 - } - if (a[0].x.a > b[0].x.a) { - return 1 + function compare_rect_position(a,b){ + if (a[0].x.a < b[0].x.a) { + return -1 + } + if (a[0].x.a > b[0].x.a) { + return 1 + } + if (a[0].y.a < b[0].y.a) { + return -1 + } + if (a[0].y.a > b[0].y.a) { + return 1 + } + return 0 } - if (a[0].y.a < b[0].y.a) { - return -1 + + function compare_car_reversed (a,b){ + if (a[0] < b[0]) { + return 1 + } + if (a[0] > b[0]) { + return -1 + } + return 0 } - if (a[0].y.a > b[0].y.a) { - return 1 + function compare_car (a,b){ + if (a[0] < b[0]) { + return -1 + } + if (a[0] > b[0]) { + return 1 + } + return 0 } - return 0 -} -function compare_car_reversed (a,b){ - if (a[0] < b[0]) { - return 1 + function room_id_tuple (r){ return [r.id, r] } + function room_height_tuple (r){ return [r.height, r] } + function room_area_tuple (r){ return [r.rect.area(), r] } + function rect_area_tuple (r){ return [r.area(), r] } + + function room_rect_tuple (r){ return [r.rect, r] } + function identity_tuple (r){ return [r, r] } + function car (r){ return r[0] } + function cdr (r){ return r[1] } + + var sort = {} + + sort.rooms_by_id = function (list){ + return list.map(room_id_tuple) + .sort(compare_car) + .map(cdr) } - if (a[0] > b[0]) { - return -1 + sort.rooms_by_height = function (list){ + return list.map(room_height_tuple) + .sort(compare_car_reversed) + .map(cdr) } - return 0 -} -function compare_car (a,b){ - if (a[0] < b[0]) { - return -1 + sort.rooms_by_position = function (list){ + return list.map(room_rect_tuple) + .sort(compare_rect_position) + .map(cdr) } - if (a[0] > b[0]) { - return 1 + sort.rooms_by_area = function (list){ + return list.map(room_area_tuple) + .sort(compare_car) + .map(cdr) } - return 0 -} - -function room_id_tuple (r){ return [r.id, r] } -function room_height_tuple (r){ return [r.height, r] } -function room_area_tuple (r){ return [r.rect.area(), r] } -function rect_area_tuple (r){ return [r.area(), r] } - -function room_rect_tuple (r){ return [r.rect, r] } -function identity_tuple (r){ return [r, r] } -function car (r){ return r[0] } -function cdr (r){ return r[1] } + sort.rects_by_position = function (list){ + return list.map(identity_tuple) + .sort(compare_rect_position) + .map(cdr) + } + sort.rects_by_area = function (list){ + return list.map(rect_area_tuple) + .sort(compare_car) + .map(cdr) + } -function sort_rooms_by_id(list){ - return list.map(room_id_tuple) - .sort(compare_car) - .map(cdr) -} -function sort_rooms_by_height(list){ - return list.map(room_height_tuple) - .sort(compare_car_reversed) - .map(cdr) -} -function sort_rooms_by_position(list){ - return list.map(room_rect_tuple) - .sort(compare_rect_position) - .map(cdr) -} -function sort_rooms_by_area(list){ - return list.map(room_area_tuple) - .sort(compare_car) - .map(cdr) -} + sort.compare_z = function (a,b){ + return a.rect.y.a < b.rect.y.a ? -1 : a.rect.y.a == b.rect.y.a ? 0 : 1 + } + sort.compare_x = function (a,b){ + return a.rect.x.a > b.rect.x.a ? -1 : a.rect.x.a == b.rect.x.a ? 0 : 1 + } -function sort_rects_by_position(list){ - return list.map(identity_tuple) - .sort(compare_rect_position) - .map(cdr) -} -function sort_rects_by_area(list){ - return list.map(rect_area_tuple) - .sort(compare_car) - .map(cdr) -} + if ("window" in this) { + window.sort = sort + } + else { + module.exports = sort + } -function compare_z(a,b){ - return a.rect.y.a < b.rect.y.a ? -1 : a.rect.y.a == b.rect.y.a ? 0 : 1 -} -function compare_x(a,b){ - return a.rect.x.a > b.rect.x.a ? -1 : a.rect.x.a == b.rect.x.a ? 0 : 1 -} +})() diff --git a/public/assets/javascripts/rectangles/util/uid.js b/public/assets/javascripts/rectangles/util/uid.js index ca22fb3..648bf0c 100644 --- a/public/assets/javascripts/rectangles/util/uid.js +++ b/public/assets/javascripts/rectangles/util/uid.js @@ -1,14 +1,25 @@ -var UidGenerator = function(list){ - var id = 0 - return function(s){ - s = s || "" - var ss - while (1) { - ss = s + (id++) - if (! (ss in list)) { - return ss +(function(){ + + var UidGenerator = function(list){ + var id = 0 + return function(s){ + s = s || "" + var ss + while (1) { + ss = s + (id++) + if (! (ss in list)) { + return ss + } } } } -} \ No newline at end of file + + if ('window' in this) { + window.UidGenerator = UidGenerator + } + else { + module.exports = UidGenerator + } + +})() diff --git a/test/03-test-clipping.js b/test/03-test-clipping.js new file mode 100644 index 0000000..1668bd1 --- /dev/null +++ b/test/03-test-clipping.js @@ -0,0 +1,21 @@ +var assert = require("assert") +var vec2 = require("../public/assets/javascripts/rectangles/models/vec2.js") +var Rect = require("../public/assets/javascripts/rectangles/models/rect.js") +var Room = require("../public/assets/javascripts/rectangles/models/room.js") +var Rooms = require("../public/assets/javascripts/rectangles/engine/rooms/_rooms.js") +var Clipper = require("../public/assets/javascripts/rectangles/engine/rooms/clipper.js") +var FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20 +var ALL = FRONT | BACK | LEFT | RIGHT + +describe('clipper', function(){ + describe('#intersects()', function(){ + // var rect = new Rect(0, 0, 10, 10) + + /* + it('intersects itself', function(){ + assert.equal(true, rect.intersects( new Rect(0, 0, 10, 10) )); + }) + */ + + }) +}) -- cgit v1.2.3-70-g09d2 From 9261438f86b1faf22a0f8d9a366fb0daa3dd090d Mon Sep 17 00:00:00 2001 From: Jules Laplace Date: Thu, 24 Jul 2014 14:45:22 -0400 Subject: iterative culling algorithm --- .../javascripts/rectangles/engine/rooms/clipper.js | 22 +++++++++++++++++- .../assets/javascripts/rectangles/models/rect.js | 3 +++ .../assets/javascripts/rectangles/models/vec2.js | 13 +++++++++++ public/assets/javascripts/rectangles/util/sort.js | 7 +++++- test/03-test-clipping.js | 26 ++++++++++++++++++---- 5 files changed, 65 insertions(+), 6 deletions(-) (limited to 'public/assets/javascripts/rectangles/models/rect.js') diff --git a/public/assets/javascripts/rectangles/engine/rooms/clipper.js b/public/assets/javascripts/rectangles/engine/rooms/clipper.js index 365ae8c..d67f6ad 100644 --- a/public/assets/javascripts/rectangles/engine/rooms/clipper.js +++ b/public/assets/javascripts/rectangles/engine/rooms/clipper.js @@ -52,7 +52,7 @@ base.reset_rects() base.clip_rects() - base.cull_rects() + base.cull_rects_iterative() Rooms.regions = sort.rects_by_position(regions) } @@ -131,6 +131,26 @@ return regions } + // Find overlapping regions and dedupe the smaller ones + base.cull_rects_iterative = function(){ + regions = sort.rects_by_area( regions ) + + var region_i, region_j, i, j, _len + + for (i = 0, _len = regions.length; i < _len-1; i++) { + region_i = regions[i] + for (j = i+1; j < _len; j++) { + region_j = regions[j] + if (region_j.dupe) continue; + if (region_i.overlaps(region_j)) { + region_i.dupe = true + } + } + } + + return regions + } + return base } diff --git a/public/assets/javascripts/rectangles/models/rect.js b/public/assets/javascripts/rectangles/models/rect.js index 3341239..590440a 100644 --- a/public/assets/javascripts/rectangles/models/rect.js +++ b/public/assets/javascripts/rectangles/models/rect.js @@ -94,6 +94,9 @@ Rect.prototype.containsDisc = function(x,y,r){ return this.x.containsDisc(x,r) && this.y.containsDisc(y,r) } + Rect.prototype.overlaps = function(rect){ + return this.x.overlaps(rect.x) && this.y.overlaps(rect.y) + } Rect.prototype.intersects = function(r){ var corner_intersect = (this.x.b === r.x.a && this.y.b === r.y.a) return this.x.intersects(r.x) && this.y.intersects(r.y) && ! corner_intersect diff --git a/public/assets/javascripts/rectangles/models/vec2.js b/public/assets/javascripts/rectangles/models/vec2.js index b0c88c1..ee02088 100644 --- a/public/assets/javascripts/rectangles/models/vec2.js +++ b/public/assets/javascripts/rectangles/models/vec2.js @@ -93,6 +93,19 @@ return (this.a < v.b && v.b <= this.b) || (v.a < this.b && this.b <= v.b) } } + vec2.prototype.overlaps = function(v){ + if (this.a == v.a || this.b == v.b) { + return true + } + if (this.a < v.a) { + return (v.a < this.b && this.b < v.b) || (this.a < v.b && v.b < this.b) + } + else if (v.a < this.a) { + return (this.a < v.b && v.b < this.b) || (v.a < this.b && this.b < v.b) + } + } + + vec2.prototype.adjacent = function(v){ if (this.a == v.a || this.b == v.b || this.a == v.b || this.b == v.a) { return true diff --git a/public/assets/javascripts/rectangles/util/sort.js b/public/assets/javascripts/rectangles/util/sort.js index c0b5d54..3b4771c 100644 --- a/public/assets/javascripts/rectangles/util/sort.js +++ b/public/assets/javascripts/rectangles/util/sort.js @@ -39,6 +39,7 @@ function room_height_tuple (r){ return [r.height, r] } function room_area_tuple (r){ return [r.rect.area(), r] } function rect_area_tuple (r){ return [r.area(), r] } + function rect_area_tuple_larger (r){ return [-r.area(), r] } function room_rect_tuple (r){ return [r.rect, r] } function identity_tuple (r){ return [r, r] } @@ -78,7 +79,11 @@ .sort(compare_car) .map(cdr) } - + sort.rects_by_larger_area = function (list){ + return list.map(rect_area_tuple_larger) + .sort(compare_car) + .map(cdr) + } sort.compare_z = function (a,b){ return a.rect.y.a < b.rect.y.a ? -1 : a.rect.y.a == b.rect.y.a ? 0 : 1 } diff --git a/test/03-test-clipping.js b/test/03-test-clipping.js index 037b5ff..20dadb3 100644 --- a/test/03-test-clipping.js +++ b/test/03-test-clipping.js @@ -89,6 +89,8 @@ describe('clipper', function(){ Rooms.add_with_rect( corner ) Rooms.add_with_rect( peninsula ) +/* + // this method uses a tree to match areas, which tends to leave extra overlapping regions describe('#cull_rects(rect, corner, peninsula)', function(){ Rooms.clipper.reset_rects() var regions = Rooms.clipper.clip_rects() @@ -96,10 +98,6 @@ describe('clipper', function(){ var culled_dupes = culled.filter(function(r){ return r.dupe }) var culled_regions = culled.filter(function(r){ return ! r.dupe }) - report(culled_dupes) - report([]) - report(culled_regions) - it('clipper returns 16 rects', function(){ assert.equal(16, regions.length) }) @@ -110,6 +108,26 @@ describe('clipper', function(){ assert.equal(14, culled_regions.length) }) }) +*/ + + // this method iterates to match areas, which omits regions in some cases + describe('#cull_rects_iterative(rect, corner, peninsula)', function(){ + Rooms.clipper.reset_rects() + var regions = Rooms.clipper.clip_rects() + var culled = Rooms.clipper.cull_rects_iterative() + var culled_dupes = culled.filter(function(r){ return r.dupe }) + var culled_regions = culled.filter(function(r){ return ! r.dupe }) + + it('clipper returns 16 rects', function(){ + assert.equal(16, regions.length) + }) + it('culling marks 3 duplicate', function(){ + assert.equal(3, culled_dupes.length) + }) + it('culling marks 14 non-duplicate', function(){ + assert.equal(13, culled_regions.length) + }) + }) }) -- cgit v1.2.3-70-g09d2