# Processing and JOGL - How are concave polygons and borders rendered?

Hello !

First of all, sorry for this post that is not really about Processing coding but about how processing itself is coded, and the JOGL library.

I’ve recently started working in OpenGL for a project, and I’m faced with the issue of polygonal rendering.

Basically, natively, OpenGL seems to only allow for primitive rendering (triangles, quads…), and rendering non convex polygons can therefore be complicated. Moreover, border rendering can only be done with line loops that suffer from alpha accumulation and that don’t have joins or caps. This isn’t an issue though, the algorithm for calculating joins and caps isn’t that hard (In fact, I already coded it in Processing to try it out, see this code section :

``````
PVector A = PVector.sub(points.get(0), points.get(1));
PVector B = PVector.sub(points.get(2), points.get(1));
float theta = PVector.angleBetween(A, B);
float signe = signe(A.cross(B).z);

int type = MITER;

//MITER
if (signe != 0) {
if (type == MITER) {
PVector orthoA = new PVector(signe * A.y, - signe * A.x);
orthoA.setMag(stroke/2);
PVector orthoB = new PVector(- signe * B.y, signe * B.x);
orthoB.setMag(stroke/2);
PVector spike = PVector.mult(PVector.add(A, B), -1);
spike.setMag(stroke * sqrt(1 / (2 * (1 - cos(theta)))));

fill(0, 100);
beginShape();
vertex(points.get(1).x + 0.5, points.get(1).y + 0.5);
vertex(points.get(1).x + orthoA.x + 0.5, points.get(1).y + orthoA.y +0.5);
if (theta > 0.205) vertex(points.get(1).x + spike.x + 0.5, points.get(1).y + spike.y + 0.5);
vertex(points.get(1).x + orthoB.x + 0.5, points.get(1).y + orthoB.y + 0.5);
vertex(points.get(1).x + 0.5, points.get(1).y + 0.5);
endShape(CLOSE);
} else if (type == BEVEL) {
PVector orthoA = new PVector(signe * A.y, - signe * A.x);
orthoA.setMag(stroke/2);
PVector orthoB = new PVector(- signe * B.y, signe * B.x);
orthoB.setMag(stroke/2);
PVector spike = PVector.mult(PVector.add(A, B), -1);
spike.setMag(stroke * sqrt(1 / (2 * (1 - cos(theta)))));

fill(0, 100);
beginShape();
vertex(points.get(1).x + 0.5, points.get(1).y + 0.5);
vertex(points.get(1).x + orthoA.x + 0.5, points.get(1).y + orthoA.y + 0.5);
vertex(points.get(1).x + orthoB.x + 0.5, points.get(1).y + orthoB.y + 0.5);
endShape(CLOSE);
}
}
``````

ROUND rendering isnt shown since it is really simple, just drawing a circle at each vertex).

This suffers from alpha accumulation and anti-aliasing artefacts (if the border is transparent for example).

I’ve checked, and apparently, there are two major ways to solve this issue :

• Tessellation : The first is to use the GLU tessellator, that is able to cut any polygon into primitives that can then be rendered with the OpenGL renderer. Apparently, this method is deprecated. I still tried implementing it :

TessellatorCallback.java

``````import com.jogamp.opengl.GL2;
import com.jogamp.opengl.glu.GLU;
import com.jogamp.opengl.glu.GLUtessellator;
import com.jogamp.opengl.glu.GLUtessellatorCallback;

public class TessellatorCallback implements GLUtessellatorCallback{

private GL2 gl;

public TessellatorCallback(GL2 gl) {
this.gl = gl;
}

public void bind(GLUtessellator tessellator) {
GLU.gluTessCallback(tessellator, GLU.GLU_TESS_BEGIN, this);

GLU.gluTessCallback(tessellator, GLU.GLU_TESS_EDGE_FLAG, this);

GLU.gluTessCallback(tessellator, GLU.GLU_TESS_COMBINE, this);

GLU.gluTessCallback(tessellator, GLU.GLU_TESS_END, this);

GLU.gluTessCallback(tessellator, GLU.GLU_TESS_ERROR, this);

GLU.gluTessCallback(tessellator, GLU.GLU_TESS_VERTEX, this);
}

//TESSELLATION CALLBACKS

@Override
public void begin(int type) {
gl.glBegin(type);
}

@Override
public void combine(double[] coords, Object[] data, float[] weight, Object[] outData) {
double[] vertex = new double;
vertex = coords;
vertex = coords;
vertex = coords;

outData = coords;
}

@Override
public void edgeFlag(boolean boundaryEdge) {}

@Override
public void end() {
gl.glEnd();
}

@Override
public void error(int errnum) {}

@Override
public void vertex(Object vertexData) {
double[] pointer;

if (vertexData instanceof double[]) {
pointer = (double[]) vertexData;
gl.glVertex3dv(pointer, 0);
}
}

@Override
public void beginData(int type, Object polygonData) {
begin(type);
}

@Override
public void combineData(double[] coords, Object[] data, float[] weight, Object[] outData, Object polygonData) {
combine(coords, data, weight, outData);
}

@Override
public void edgeFlagData(boolean boundaryEdge, Object polygonData) {
edgeFlag(boundaryEdge);
}

@Override
public void endData(Object polygonData) {
end();
}

@Override
public void errorData(int errnum, Object polygonData) {
error(errnum);
}

@Override
public void vertexData(Object vertexData, Object polygonData) {
vertex(vertexData);
}
}
``````

PanelListener that implements GLEventListener

``````import java.util.ArrayList;

import com.jogamp.opengl.GL;
import com.jogamp.opengl.GL2;
import com.jogamp.opengl.GLAutoDrawable;
import com.jogamp.opengl.GLEventListener;
import com.jogamp.opengl.awt.GLJPanel;
import com.jogamp.opengl.glu.GLU;
import com.jogamp.opengl.glu.GLUtessellator;

public class PanelListener implements GLEventListener{

GLJPanel panel;
GL2 gl;

ArrayList<SVector> shape;

public PanelListener(GLJPanel panel) {
super();
this.panel = panel;

shape = new ArrayList<SVector>();
}

public GLUtessellator initializeTessellator(boolean force) {
GLU.createGLU(gl);
GLUtessellator tessellator = GLU.gluNewTess();

TessellatorCallback tessCallback = new TessellatorCallback(gl);
tessCallback.bind(tessellator);

GLU.gluTessProperty(tessellator, GLU.GLU_TESS_WINDING_RULE, GLU.GLU_TESS_WINDING_NONZERO);

return tessellator;
}

public void beginShape() {
shape = new ArrayList<SVector>();
}

public void vertex(float x, float y) {
}

public void endShape() {
//FILL

gl.glColor4f(1f, 0f, 0.0f, 0.3f);

GLUtessellator tessellator = initializeTessellator(false);
tessBegin(tessellator);
tessBeginContour(tessellator);
for(SVector v: shape) tessVertex(tessellator, v.x, v.y);
tessEndContour(tessellator);
tessEnd(tessellator);
tessDelete(tessellator);

//STROKE WITH ROUND JOINS AND CLOSE SHAPE

gl.glColor3f(0f, 0f, 0f);

float stroke = 10;

tessellator = initializeTessellator(false);
tessBegin(tessellator);

for(SVector v: shape) {
tessBeginContour(tessellator);
//LOW NUMBER OF ELLIPSE POINTS FOR TESTING, USUALLY THIS NUMBER IS CALCULATED FROM THE ELLIPSE SIZE
int n_points = 7;
for(int i = 0; i < n_points; i++) {
float theta = (float) i * (float) Math.PI * 2.0f / (float) n_points;
tessVertex(tessellator, v.x + stroke / 2 * Math.sin(theta), v.y + stroke / 2 * Math.cos(theta));
}
tessEndContour(tessellator);
}

for(int i = 0; i < shape.size(); i++) {
tessBeginContour(tessellator);
SVector P0 = shape.get(i);
SVector P1 = shape.get((i+1) % shape.size());

SVector ortho = new SVector(P1.y - P0.y, P0.x - P1.x);
ortho.setMag(stroke / 2);

tessVertex(tessellator, P0.x + ortho.x, P0.y + ortho.y);
tessVertex(tessellator, P0.x - ortho.x, P0.y - ortho.y);
tessVertex(tessellator, P1.x - ortho.x, P1.y - ortho.y);
tessVertex(tessellator, P1.x + ortho.x, P1.y + ortho.y);
tessEndContour(tessellator);
}
tessEnd(tessellator);
tessDelete(tessellator);
}

public void tessBegin(GLUtessellator tessellator) {
GLU.gluBeginPolygon(tessellator);
}

public void tessBeginContour(GLUtessellator tessellator) {
GLU.gluTessBeginContour(tessellator);
}

public void glVertex(int x, int y) {
gl.glVertex2f(2f * (x + 0.5f) / (float) panel.getWidth() - 1f, 2f * ((float) panel.getHeight() - y - 1.5f) / (float) panel.getHeight() - 1f);
}

public void glVertex(float x, float y) {
gl.glVertex2f(2f * (x + 0.5f) / (float) panel.getWidth() - 1f, 2f * ((float) panel.getHeight() - y - 1.5f) / (float) panel.getHeight() - 1f);
}

public void glVertex(double x, double y) {
gl.glVertex2d(2f * (x + 0.5f) / (float) panel.getWidth() - 1f, 2f * ((float) panel.getHeight() - y - 1.5f) / (float) panel.getHeight() - 1f);
}

public void tessVertex(GLUtessellator tessellator, int x, int y) {
double[] coords = new double;
coords = 2f * (x + 0.5f) / (float) panel.getWidth() - 1f;
coords = 2f * ((float) panel.getHeight() - y - 1.5f) / (float) panel.getHeight() - 1f;
coords = 0;
GLU.gluTessVertex(tessellator, coords, 0, coords);
}

public void tessVertex(GLUtessellator tessellator, double x, double y) {
double[] coords = new double;
coords = 2f * (x + 0.5f) / (float) panel.getWidth() - 1f;
coords = 2f * ((float) panel.getHeight() - y - 1.5f) / (float) panel.getHeight() - 1f;
coords = 0;
GLU.gluTessVertex(tessellator, coords, 0, coords);
}

public void tessVertex(GLUtessellator tessellator, float x, float y) {
double[] coords = new double;
coords = 2f * (x + 0.5f) / (float) panel.getWidth() - 1f;
coords = 2f * ((float) panel.getHeight() - y - 1.5f) / (float) panel.getHeight() - 1f;
coords = 0;
GLU.gluTessVertex(tessellator, coords, 0, coords);
}

public void tessEndContour(GLUtessellator tessellator) {
GLU.gluTessEndContour(tessellator);
}

public void tessEnd(GLUtessellator tessellator) {
GLU.gluTessEndPolygon(tessellator);
}

public void tessDelete(GLUtessellator tessellator) {
GLU.gluDeleteTess(tessellator);
}

@Override
public void display(GLAutoDrawable displayable) {
//DISPLAY TEST

gl.glClearColor(
1f,
1f,
1f,
1.0f);

gl.glClear(GL2.GL_COLOR_BUFFER_BIT | GL2.GL_DEPTH_BUFFER_BIT | GL2.GL_STENCIL_BUFFER_BIT);

int N = 500;

beginShape();
for(int i = 0; i < N; i++) vertex((float) (panel.getWidth() * Math.random()), (float) (panel.getHeight() * Math.random()));
endShape();
}

public static float max(float a, float b) {
return Math.max(a, b);
}

public static float min(float a, float b) {
return Math.min(a, b);
}

public static float map(float x, float a, float b, float A, float B) {
return (B-A)*((x-a)/(b-a)) + A;
}

public static float constrain(float x, float a, float b) {
return min(max(x, a), b);
}

@Override
public void dispose(GLAutoDrawable displayable) {

}

@Override
public void init(GLAutoDrawable displayable) {
gl = displayable.getGL().getGL2();

gl.glEnable(GL2.GL_LINE_SMOOTH);
gl.glEnable(GL2.GL_POINT_SMOOTH);
gl.glEnable(GL2.GL_SMOOTH);

gl.glHint(GL2.GL_LINE_SMOOTH_HINT, GL2.GL_FASTEST);
gl.glHint(GL2.GL_POINT_SMOOTH_HINT, GL2.GL_NICEST);

gl.glEnable(GL2.GL_BLEND);
gl.glBlendFuncSeparate(GL2.GL_SRC_ALPHA, GL2.GL_ONE_MINUS_SRC_ALPHA, GL2.GL_ONE, GL2.GL_ONE);

gl.glClearColor(0.3f, 0.3f, 0.3f, 1f);
gl.glClear(GL2.GL_COLOR_BUFFER_BIT | GL.GL_DEPTH_BUFFER_BIT | GL.GL_STENCIL_BUFFER_BIT);

}

@Override
public void reshape(GLAutoDrawable displayable, int x, int y, int w, int h) {
panel.repaint();
}
}
``````

Although visually, this works perfectly, it is quite slow (even without the border tessellation). With a polygon with 500 vertices and without border, it runs at about 3 fps, where to achieve this frameRate in processing, I need to keep a 10px border and up the number of points to around 2000.

I also checked the Processing code on github and it seems that they are in fact using GLU Tessellation at some point (see processing/PJOGL.java at a6e0e227a948e7e2dc042c04504d6f5b8cf0c1a6 · processing/processing · GitHub from line 589). If in processing this is done through Tessellation, how can they achieve such speed ? And is there a trick to render joined and caped borders this fast without artefacts ?

• Stencil Buffer : Apparently, in the industry, the stencil buffer is mostly used instead of tessellation. An explanation of this technique can be found here : http://what-when-how.com/opengl-programming-guide/drawing-filled-concave-polygons-using-the-stencil-buffer-opengl-programming/. Basically, a data buffer bit in each pixel is used to determine the winding number mod 2 of the specified pixel (in the GPU potentially ?) and this can be used to implement an ODD_WINDING type “tessellation” that is advertized to be much faster. Is this how Processing implements polygon rendering ? If so, how do they achieve rendering with a NON_ZERO winding rule ? how does this technique work with transparency and anti-aliasing ? And finally, can this be used to render polygon borders ?

Sorry for this quite long post, I’ve been trying to figure all of this out for the past month ^^

If a long answer is too much, even just redirecting me to documentation could still be a huge help.

Thanks !

1 Like

Alright, I’ll add this here : I benchmarked processing aswell as the GLU tessellator with as input the number of vertices and here are the results :

It seems that the GLU Tessellator actually has a time complexity in O(N^3), which seems crazy to me (perhaps my code is very unefficient, let me know if so).