August 24, 2005
Section 314 of
Hearn/Baker
is titled, FillArea Primitives. These are almost as
essential to rendering graphics as points and lines. It is, of
course, a standard, builtin routine for OpenGL, but I want to
examine how it works, particularly for simple polygonal areas.
These are "simple" because they are planar and there are no
edgecrossings. However, when you're working in 3D, it may
happen that the vertices to define a polygon are not, in fact,
planar. Simple rounding errors can cause this, but you may be
working with points on curved surfaces too. Often,
simply dissecting the polygon into triangles can solve the problem
(since triangles are always planar,) but in the cases where that
won't do, methods have been methodically divined (or devised) as
needed. Let's see.
A polygon is convex if all
interior angles are less than 180 degrees. This turns out to
be equivalent (under Euclidean assumptions) to saying that every
point on the interior can be connected to every other point on the
interior by a straight line that lies entirely within the interior.
H/B claim that to be more
robust, a graphics package could reject polygons whose vertices are
colinear.
Given a set of planar polygonal vertices in counterclockwise order, how can it be determined whether
it be convex or, the opposite, concave? Hearn/Baker suggests
doing vector cross products for edge vectors emanating from each
vertex. For a convex polygon, all these cross products will be
the same sign. Alternatively, you can use the idea that all
vertices of a convex polygon will be on the same side of any give
edge.
Having established that a set of
ordered vertices defines a concave polygon, you can divide it into a
set of convex polygons. Again, edge vector cross products can
do this, or, vertex positions relative to some extended edge line.
I rode over to the Alkobar for a
newspaper with the H/B stuff about splitting concave polygons and
inside/outside tests on my mind and problems came to mind:
Given
three (ordered?) vertices in a bounded convex region, say, a convex
region like a unit square or circle, what is the probability that a
randomly chosen fourth point (in order?) will (1) form a concave
quadrilateral ? or (2) form a simple quadrilateral?
One approach is to get an
empirical estimate by performing lots of trials and computing the
Monte Carlo thingy.
The algorithm I have in mind for
computing the empirical probability is to find the average of
probabilities that the fourth point forms a convex quadrilateral
with a random set of three initial points. That is, given
three arbitrary triangles in a unit square
1. Determine the coordinates 6
points where the extended triangle edges intesect the perimeter of
the unit square.
2. Determine the vertices of polygons opposite the the triangle
vertices and compute their areas.
3. Compute the ratio of areas where the fourth point will produce a
convex polygon to the area of the unit square (1)
This ratio is the probability
that a randomly chosen fourth point will form a convex polygon.
So, for part 1:
first compute an equation for the extended line, say
and then plug in
x=0, x=1, y=0 and y=1 to determine where it
might intersect the boundary (only two of these will have value
second coordinates.) Assuming a nonzero slope m has
been computed, the coordinate pairs to consider are
(0, y_{0}–mx_{0}),
(x_{0}–y_{0}/m, 0), (1, y_{0}+(1–x_{0})m),
and (x_{0}+(1–y_{0})/m,
1).
To be on the
perimeter of the square, computed coordinates must be between 0 and
1.
Taking a visual approach, I come
up with the following code:
Here's the current deal:
// Based on code from OpenGl
Primer by Edward Angel
#include <GL/glut.h>
#include <math.h>
#include <iostream>
#include <ctime>
#include <cstdlib>
#define NULL 0
int doubleb; //window ids //singleb,
//prototypes
void display();
void keyIt(unsigned char, int, int);
void reshapeIt(int, int);
void display();
void quit_menu(int);
void drawObjects(GLenum);
////////////////////////////////////////
int main(int argc, char** argv) {
glutInit(&argc, argv);
//create a double buffered window
glutInitDisplayMode(GLUT_DOUBLE  GLUT_RGB);
doubleb = glutCreateWindow("double buffered");
//initIt();
glutDisplayFunc(display);
glutReshapeFunc(reshapeIt);
glutIdleFunc(display);
//glutMouseFunc(mouse);
//Enter event loop
glutMainLoop();
}
void display() {
glClear(GL_COLOR_BUFFER_BIT);
drawObjects(GL_RENDER);
glutSwapBuffers();
}
void drawObjects(GLenum mode) {
float t[3][2], temp, x, y;
float edgePts[6][2];
for(float i = 0; i < 1.0; i+=0.1) {
for(float j = 0; j < 1.0; j+=0.1) {
for(int k= 0;k<3;++k) {
t[k][0] = (float) rand()/(10*RAND_MAX)+i;
t[k][1] = (float) rand()/(10*RAND_MAX)+j;
}
glColor3f(1.0,0.0,0.0); //red
glBegin(GL_TRIANGLES);
glVertex2fv(t[0]);
glVertex2fv(t[1]);
glVertex2fv(t[2]);
glEnd();
}
}
// Sort the points in increasing order of x.
// Note: this should be tightened up with a bubble sort...
if(t[1][0]<t[0][0]) {
temp = t[0][0];
t[0][0] = t[1][0];
t[1][0] = temp;
temp = t[0][1];
t[0][1] = t[1][1];
t[1][1] = temp;
}
if(t[2][0]<t[1][0]) {
temp = t[1][0];
t[1][0] = t[2][0];
t[2][0] = temp;
temp = t[1][1];
t[1][1] = t[2][1];
t[2][1] = temp;
}
if(t[1][0]<t[0][0]) {
temp = t[0][0];
t[0][0] = t[1][0];
t[1][0] = temp;
temp = t[0][1];
t[0][1] = t[1][1];
t[1][1] = temp;
}
// compute where triangle lines intersect perimeter of unit square
// start by computing the three slopes:
float m[3];
m[0] = (t[0][1]  t[1][1])
/(t[0][0]  t[1][0]);
m[1] = (t[1][1]  t[2][1])
/(t[1][0]  t[2][0]);
m[2] = (t[2][1]  t[0][1])
/(t[2][0]  t[0][0]);
// for each vertex, compute the other two vertices of the
// polygon whose area we want, which are where the extended
// triangle edges meet the perimeter of the unit square.
// x0,y0
int next = 0;
//for each extended edge
for(int e = 0; e < 3; ++e) {
y = t[e][1]  m[e]*t[e][0];
if(0<y && y<1) {
edgePts[next][0] = 0;
edgePts[next][1] = y;
++next;
}
y = t[e][1] + m[e]*(1t[e][0]);
if(0<y && y<1) {
edgePts[next][0] = 1;
edgePts[next][1] = y;
++next;
}
x = t[e][0]  t[e][1]/m[e];
if(0<x && x<1) {
edgePts[next][0] = x;
edgePts[next][1] = 0;
++next;
}
x = t[e][0] +(1t[e][1])/m[e];
if(0<x && x<1) {
edgePts[next][0] = x;
edgePts[next][1] = 1;
++next;
}
}
// print out
}
void reshapeIt(int w, int h) {
glViewport(0,0,w,h);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0.0,1.0,0.0,1.0);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
}
// Both a keyboard and a mouse callback are illustrated here
/*void keyIt(unsigned char key, int x, int y) {
if(key == 'Q'  key == 'q') exit(0);
}
void quit_menu(int id) {
if(id == 1) exit(0);
}*/
