It is currently Mon Dec 09, 2013 5:56 am

 All times are UTC

 Page 1 of 1 [ 6 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Boolean GeometryPosted: Mon Jan 23, 2012 6:03 am
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Hey bo-peeples,

I'm revisiting a project from a few months ago ( viewtopic.php?f=6&t=10715 ), in which I create a world out of 2D vector polygons. The idea is that you could start a maze with a polygon, and extrude that polygon to generate corridors and such.

Anyway, I want to expand upon that idea with Boolean geometry -- in other words, I want to be able to define a shape that can be combined with other shapes to add-to or subtract-from their geometry. Like this article: http://en.wikipedia.org/wiki/Constructi ... d_geometry

That's what I'm aiming for. Of course, I will be working in 2D.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Re: Boolean GeometryPosted: Mon Jan 23, 2012 3:06 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Did some major digging and found some good material. It took me a while, but I have it working -- I can take two polygons and combine them into one polygon.

In case it may be helpful to anyone, here is the code I wrote (in JavaScript):

Code:
function polyUnion(poly1, poly2) {
var i1 = 0,
i2 = 0,
i1Active = true,   //keep track of which polygon we're tracing
numLines = poly1.points.length + poly2.points.length,
res = {      // function result object
points : []
};

// This is where the magic begins.
for (var i = 0; i < numLines; i++) {
// If we go out of bounds, wrap the value
i1 %= poly1.points.length;
i2 %= poly2.points.length;

// Get the line data for intersection testing
// Add a "buried" property for splicing to remove extraneous (and problematic) points
var line1 = {
startPoint : {
x : poly1.points[i1].x,
y : poly1.points[i1].y,
buried : pointInPoly(poly2, poly1.points[i1])
},
endPoint : {
x : poly1.points[(i1 + 1) % poly1.points.length].x,
y : poly1.points[(i1 + 1) % poly1.points.length].y
}
};

var line2 = {
startPoint : {
x : poly2.points[i2].x,
y : poly2.points[i2].y,
buried : pointInPoly(poly1, poly2.points[i2])
},
endPoint : {
x : poly2.points[(i2 + 1) % poly2.points.length].x,
y : poly2.points[(i2 + 1) % poly2.points.length].y
}
};

var lineTest;

// Need to know which polygon we are currently following to know which test to do
if (i1Active) {
lineTest = linePolyTest(line1, poly2);
} else {
lineTest = linePolyTest(line2, poly1);
}

if (lineTest) {
// We have an intersection
if (i1Active) {
res.points.push({
x : line1.startPoint.x,
y : line1.startPoint.y,
buried : pointInPoly(poly2, line1.startPoint)
});
res.points.push(lineTest);
i1++;
} else {
res.points.push({
x : line2.startPoint.x,
y : line2.startPoint.y,
buried : pointInPoly(poly1, line2.startPoint)
});
res.points.push(lineTest);
i2++;
}
i1Active = !i1Active;   //since we have an intersection, we should switch polygons
} else {
// No intersection, just need to get the next point in the polygon
if (i1Active) {
res.points.push({
x : line1.startPoint.x,
y : line1.startPoint.y,
buried : pointInPoly(poly2, line1.startPoint)
});
i1++;
} else {
res.points.push({
x : line2.startPoint.x,
y : line2.startPoint.y,
buried : pointInPoly(poly1, line2.startPoint)
});
i2++;
}
}
}

// Now we can get rid of buried points to help prevent geometric glitches
var numSpliced = 0;
for (var i = 0, currPoint; currPoint = res.points[i]; i++) {
if (currPoint.buried == true) {
res.points.splice(i, 1);
numSpliced++;
}
}

return res;
}

function linePolyTest(line, poly) {
// This function tests to see if a line intersects a polygon
// It simply takes the line argument, and then iterates through the polygon
//      argument's points, building lines for simple intersection testing
for (var i = 0; i < poly.points.length; i++) {
var polyLine = {
startPoint : {
x : poly.points[i].x,
y : poly.points[i].y
},
endPoint : {
x : poly.points[(i+1) % poly.points.length].x,
y : poly.points[(i+1) % poly.points.length].y
}
};

// Perform the actual line intersection test and return the point of an intersection
var lineTest = lineIntersect(line, polyLine);
if (lineTest) {
return lineTest;
}
}
}

function pointInPoly(poly, point) {
// Tests whether a point is inside a polygon.
var i,
n = poly.points.length,
angle = 0.0,
p1, p2;

for (i = 0; i < n; i++) {
p1 = {
x : poly.points[i].x - point.x,
y : poly.points[i].y - point.y
};
p2 = {
x : poly.points[(i+1)%n].x - point.x,
y : poly.points[(i+1)%n].y - point.y
};
angle += getAngle(p1.x, p1.y, p2.x, p2.y);
}

if (Math.abs(angle) < Math.PI) {
return false;
} else {
return true;
}
}

function getAngle(x1, y1, x2, y2) {
// finds the angle between two points
var dtheta, theta1, theta2;

theta1 = Math.atan2(y1,x1);
theta2 = Math.atan2(y2,x2);
dtheta = theta2 - theta1;

while (dtheta > Math.PI) {
dtheta -= Math.PI * 2;
}
while (dtheta < -Math.PI) {
dtheta += Math.PI * 2;
}

return dtheta;
}

function lineIntersect(line1, line2) {
// Line Intersection test
// Thank you to Paul Bourke -- http://paulbourke.net/
var denom = ((line2.endPoint.y - line2.startPoint.y) * (line1.endPoint.x - line1.startPoint.x)) -
((line2.endPoint.x - line2.startPoint.x) * (line1.endPoint.y - line1.startPoint.y));

var nume_a = ((line2.endPoint.x - line2.startPoint.x) * (line1.startPoint.y - line2.startPoint.y)) -
((line2.endPoint.y - line2.startPoint.y) * (line1.startPoint.x - line2.startPoint.x));

var nume_b = ((line1.endPoint.x - line1.startPoint.x) * (line1.startPoint.y - line2.startPoint.y)) -
((line1.endPoint.y - line1.startPoint.y) * (line1.startPoint.x - line2.startPoint.x));

if (denom == 0.0) {
return false;
}

var ua = nume_a / denom;
var ub = nume_b / denom;

if (ua >= 0.0 && ua <= 1.0 && ub >= 0.0 && ub <= 1.0) {
return {
x : line1.startPoint.x + ua * (line1.endPoint.x - line1.startPoint.x),
y : line1.startPoint.y + ua * (line1.endPoint.y - line1.startPoint.y)
};
}

return false;
}

Probably not the most effective method... if anyone has any tips, I would appreciate it if you would pass them along!

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Re: Boolean GeometryPosted: Mon Jan 23, 2012 3:21 pm
 Bibliotherapist

Joined: Wed Nov 03, 2004 1:28 pm
Posts: 6881
Location: Wilts, Englandshire
Nice.
Is it a case of creating new points at the intersections and building new polygons? Can you do operations other than union? I always found subtract was the most useful operation.

_________________
20 GOTO 10

Top

 Post subject: Re: Boolean GeometryPosted: Mon Jan 23, 2012 8:19 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Is it a case of creating new points at the intersections and building new polygons?

That was the plan...

Of course, after my test case finally worked, I neglected to try more test cases...

In other words, it works just right -- but only when you give it the same two polygons I used in my test case.

Once you start with a shape that intersects more than the same one line on the other polygon, bizarre happens. And don't even think of trying to unite polygons, then try to do another union operation!

God I suck.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Re: Boolean GeometryPosted: Mon Jan 23, 2012 9:17 pm
 Bibliotherapist

Joined: Wed Nov 03, 2004 1:28 pm
Posts: 6881
Location: Wilts, Englandshire
It's pretty hardcore stuff. Do you really need to do this in-game? Is it for random level generation?

_________________
20 GOTO 10

Top

 Post subject: Re: Boolean GeometryPosted: Mon Jan 23, 2012 10:05 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
It's pretty hardcore stuff. Do you really need to do this in-game? Is it for random level generation?

Primarily the former -- I need a way to be able to modify the playing field (a la terrain deformation, in a way) in real-time.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 6 posts ]

 All times are UTC

#### Who is online

Users browsing this forum: No registered users and 1 guest

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ Forums    Forum Rules and Posting Guidelines Wiki Discussion    Help    Content Issues Game Programming Discussion    C and C++ Game Programming    Java Game Programming    Language Agnostic Programming    .NET Game Programming    VB Game Programming    Mobile Game Programming    Web-Based Game Programming    Other Languages    OpenGL Development    Direct X Development Game Development Discussion    Game Design    Game Media Off-Topic Discussion    Announcements    Off-Topic    Community Projects    News