# LoopBlinn Cubic Curve Rendering - Serpentine arteffect

I am trying to implement the Loop-Blinn cubic curve in java using the following source codes GPU-Curve-Rendering and WebCore. Both of them are showing few arteffects and i cannot figure out why. Here are my source code:

public class CubicBezier {
public enum CurveType {
UNKNOWN, SERPENTINE, LOOP, CUSP, QUADRATIC, LINE
};

private FloatArray klm;
public Array<Vertex> tris;
public Array<Vertex> plainTris;
public final float M_EPS = .00001f;

public Vector2 start;
public Vector2 ctrl1;
public Vector2 ctrl2;
public Vector2 end;

boolean once = true;

public CubicBezier(Vector2 start, Vector2 ctrl1, Vector2 ctrl2, Vector2 end) {
this.start = start;
this.ctrl1 = ctrl1;
this.ctrl2 = ctrl2;
this.end = end;
tris = new Array<Vertex>();
plainTris = new Array<Vertex>();

compute(start.x, start.y, ctrl1.x, ctrl1.y, ctrl2.x, ctrl2.y, end.x, end.y, -1);
}

public void compute() {
tris.clear();
plainTris.clear();
compute(start.x, start.y, ctrl1.x, ctrl1.y, ctrl2.x, ctrl2.y, end.x, end.y, -1);
}

boolean flipSerpent = false;
public void compute(float x0, float y0, float x1, float y1, float x2, float y2, float x3, float y3,
int recursiveType) {
Float fd1 = new Float();
Float fd2 = new Float();
Float fd3 = new Float();
CurveType curve_type = determineType(fd1, fd2, fd3);
float d1 = fd1.value, d2 = fd2.value, d3 = fd3.value;
System.out.println(curve_type);
plainTris.clear();

float OneThird = 1.0f / 3.0f;
float TwoThirds = 2.0f / 3.0f;

float t1;
float ls;
float lt;
float ms;
float mt;

float ltMinusLs;
float mtMinusMs;
float lsMinusLt;
float ql;
float qm;

// bool flip
boolean flip = false;

// artifact on loop
int errorLoop = -1;
float splitParam = 0;

klm = new FloatArray(12);
for (int i = 0; i < 12; i++) {
}

switch (curve_type) {
case UNKNOWN:
break;
case SERPENTINE:
t1 = (float) Math.sqrt(9.0f * d2 * d2 - 12 * d1 * d3);
ls = 3.0f * d2 - t1;
lt = 6.0f * d1;
ms = 3.0f * d2 + t1;
mt = lt;
ltMinusLs = lt - ls;
mtMinusMs = mt - ms;

klm.set(0, ls * ms);
klm.set(1, ls * ls * ls);
klm.set(2, ms * ms * ms);

klm.set(3, OneThird * (3.0f * ls * ms - ls * mt - lt * ms));
klm.set(4, ls * ls * (ls - lt));
klm.set(5, ms * ms * (ms - mt));

klm.set(6, OneThird * (lt * (mt - 2.0f * ms) + ls * (3.0f * ms - 2.0f * mt)));
klm.set(7, ltMinusLs * ltMinusLs * ls);
klm.set(8, mtMinusMs * mtMinusMs * ms);

klm.set(9, ltMinusLs * mtMinusMs);
klm.set(10, -(ltMinusLs * ltMinusLs * ltMinusLs));
klm.set(11, -(mtMinusMs * mtMinusMs * mtMinusMs));
System.out.println("d1 " + d1);
for (int i = 0; i < 12; i++) {
System.out.println(i+": "+klm.get(i));
}
if (d1 < 0.0f) {
flip = true;
flipSerpent = true;
}
break;
case LOOP:
t1 = (float) Math.sqrt(4.0f * d1 * d3 - 3.0f * d2 * d2);
ls = d2 - t1;
lt = 2.0f * d1;
ms = d2 + t1;
mt = lt;

// Figure out whether there is a rendering artifact requiring
// the curve to be subdivided by the caller.
ql = ls / lt;
qm = ms / mt;
if (0.0f < ql && ql < 1.0f) {
errorLoop = 1;
splitParam = ql;
}

if (0.0f < qm && qm < 1.0f) {
errorLoop = 2;
splitParam = qm;
}

ltMinusLs = lt - ls;
mtMinusMs = mt - ms;

System.out.println(d1);

klm.set(0, ls * ms);
klm.set(1, ls * ls * ms);
klm.set(2, ls * ms * ms);
klm.set(3, OneThird * (-ls * mt - lt * ms + 3.0f * ls * ms));
klm.set(4, -OneThird * ls * (ls * (mt - 3.0f * ms) + 2.0f * lt * ms));
klm.set(5, -OneThird * ms * (ls * (2.0f * mt - 3.0f * ms) + lt * ms));
klm.set(6, OneThird * (lt * (mt - 2.0f * ms) + ls * (3.0f * ms - 2.0f * mt)));
klm.set(7, OneThird * (lt - ls) * (ls * (2.0f * mt - 3.0f * ms) + lt * ms));
klm.set(8, OneThird * (mt - ms) * (ls * (mt - 3.0f * ms) + 2.0f * lt * ms));
klm.set(9, ltMinusLs * mtMinusMs);
klm.set(10, -(ltMinusLs * ltMinusLs) * mtMinusMs);
klm.set(11, -ltMinusLs * mtMinusMs * mtMinusMs);

if (recursiveType == -1)
flip = ((d1 > 0.0f && klm.get(0) < 0.0f) || (d1 < 0.0f && klm.get(0) > 0.0f));
break;

case CUSP:
ls = d3;
lt = 3.0f * d2;
lsMinusLt = ls - lt;
klm.set(0, ls);
klm.set(1, ls * ls * ls);
klm.set(2, 1.0f);
klm.set(3, ls - OneThird * lt);
klm.set(4, ls * ls * lsMinusLt);
klm.set(5, 1.0f);
klm.set(6, ls - TwoThirds * lt);
klm.set(7, lsMinusLt * lsMinusLt * ls);
klm.set(8, 1.0f);
klm.set(9, lsMinusLt);
klm.set(10, lsMinusLt * lsMinusLt * lsMinusLt);
klm.set(11, 1.0f);
break;

klm.set(0, 0);
klm.set(1, 0);
klm.set(2, 0);
klm.set(3, OneThird);
klm.set(4, 0);
klm.set(5, OneThird);
klm.set(6, TwoThirds);
klm.set(7, OneThird);
klm.set(8, TwoThirds);
klm.set(9, 1);
klm.set(10, 1);
klm.set(11, 1);
if (d3 < 0)
flip = true;
break;
case LINE:
break;
}

if (errorLoop != -1 && recursiveType == -1) {
System.out.println("error");
float x01 = (x1 - x0) * splitParam + x0;
float x12 = (x2 - x1) * splitParam + x1;
float x23 = (x3 - x2) * splitParam + x2;
float y01 = (y1 - y0) * splitParam + y0;
float y12 = (y2 - y1) * splitParam + y1;
float y23 = (y3 - y2) * splitParam + y2;

float x012 = (x12 - x01) * splitParam + x01;
float x123 = (x23 - x12) * splitParam + x12;
float y012 = (y12 - y01) * splitParam + y01;
float y123 = (y23 - y12) * splitParam + y12;

float x0123 = (x123 - x012) * splitParam + x012;
float y0123 = (y123 - y012) * splitParam + y012;

if (errorLoop == 1) // flip second
{
compute(start.x, start.y, x01, y01, x012, y012, x0123, y0123, 0);
compute(x0123, y0123, x123, y123, x23, y23, end.x, end.y, 1);
} else if (errorLoop == 2) // flip first
{
compute(start.x, start.y, x01, y01, x012, y012, x0123, y0123, 1);
compute(x0123, y0123, x123, y123, x23, y23, end.x, end.y, 0);
}

return;
} else if (errorLoop == -1 && recursiveType == -1) {
}

if (recursiveType == 1)
flip = !flip;

if (flip) {
klm.set(0, -klm.get(0));
klm.set(1, -klm.get(1));
klm.set(3, -klm.get(3));
klm.set(4, -klm.get(4));
klm.set(6, -klm.get(6));
klm.set(7, -klm.get(7));
klm.set(9, -klm.get(9));
klm.set(10, -klm.get(10));
}

Triangulation(x0, y0, x1, y1, x2, y2, x3, y3, klm.toArray());

}

public CurveType determineType(Float fd1, Float fd2, Float fd3) {
float d1 = 0, d2 = 0, d3 = 0;
Vector3 b0 = new Vector3(start.x, start.y, 1f);
Vector3 b1 = new Vector3(ctrl1.x, ctrl1.y, 1f);
Vector3 b2 = new Vector3(ctrl2.x, ctrl2.y, 1f);
Vector3 b3 = new Vector3(end.x, end.y, 1f);

float a1 = b0.dot(b3.cpy().crs(b2).cpy());
float a2 = b1.dot(b0.cpy().crs(b3).cpy());
float a3 = b2.dot(b1.cpy().crs(b0).cpy());

d1 = a1 - 2 * a2 + 3 * a3;
d2 = -a2 + 3 * a3;
d3 = 3 * a3;

Vector3 d = new Vector3(d1, d2, d3);
d.nor();
d1 = d.x;
d2 = d.y;
d3 = d.z;
System.out.println("a1 "+ d1);
fd1.value = d1;
fd2.value = d2;
fd3.value = d3;

float D = 3.0f * d2 * d2 - 4.0f * d1 * d3;
float disc = d1 * d1 * D;

if(disc == 0) {
if (d1 == 0 && d2 == 0) {
if(d3 == 0)
return CurveType.LINE;
}
if(d1 == 0)
return CurveType.CUSP;
if(D < 0)
return CurveType.LOOP;
}
if (disc > 0)
return CurveType.SERPENTINE;

return CurveType.LOOP;
}

public void Triangulation(float x0, float y0, float x1, float y1, float x2, float y2, float x3, float y3, float[] klm) {

Vertex[] vertices = new Vertex[4];
vertices[0] = new Vertex(x0, y0, klm[0], klm[1], klm[2]);
vertices[1] = new Vertex(x1, y1, klm[3], klm[4], klm[5]);
vertices[2] = new Vertex(x2, y2, klm[6], klm[7], klm[8]);
vertices[3] = new Vertex(x3, y3, klm[9], klm[10], klm[11]);

for (int i = 0; i < 4; ++i) {
for (int j = i + 1; j < 4; ++j) {
if (approxEqual(vertices[i].xy, vertices[j].xy)) {
int indices[] = { 0, 0, 0 };
int index = 0;
for (int k = 0; k < 4; ++k)
if (k != j)
indices[index++] = k;

return;
}
}
}

for (int i = 0; i < 4; ++i) {
int indices[] = { 0, 0, 0 };
int index = 0;
for (int j = 0; j < 4; ++j)
if (i != j)
indices[index++] = j;

if (pointInTriangle(vertices[i].xy, vertices[indices[0]].xy, vertices[indices[1]].xy,
vertices[indices[2]].xy)) {

System.out.println("insude triangle");
return;
}
}

if (intersect(vertices[0].xy, vertices[2].xy, vertices[1].xy, vertices[3].xy)) {
if ((vertices[2].xy.cpy().sub(vertices[0].xy)).len2() < (vertices[3].xy.cpy().sub(vertices[1].xy)).len2()) {

} else {

}
}

else if (intersect(vertices[0].xy, vertices[3].xy, vertices[1].xy, vertices[2].xy)) {
if ((vertices[3].xy.cpy().sub(vertices[0].xy)).len2() < (vertices[2].xy.cpy().sub(vertices[1].xy)).len2()) {

System.out.println("true");
} else {

}
} else {
if ((vertices[1].xy.cpy().sub(vertices[0].xy)).len2() < (vertices[3].xy.cpy().sub(vertices[2].xy)).len2()) {

} else {

}
}

}

public boolean approxEqual(Vector2 v0, Vector2 v1) {
return (v0.cpy().sub(v1)).len2() < M_EPS * M_EPS;
}

public boolean pointInTriangle(Vector2 point, Vector2 a, Vector2 b, Vector2 c) {
float x0 = c.x - a.x;
float y0 = c.y - a.y;
float x1 = b.x - a.x;
float y1 = b.y - a.y;
float x2 = point.x - a.x;
float y2 = point.y - a.y;

float dot00 = x0 * x0 + y0 * y0;
float dot01 = x0 * x1 + y0 * y1;
float dot02 = x0 * x2 + y0 * y2;
float dot11 = x1 * x1 + y1 * y1;
float dot12 = x1 * x2 + y1 * y2;
float denominator = dot00 * dot11 - dot01 * dot01;
if (denominator == 0)
return false;

float inverseDenominator = 1.0f / denominator;
float u = (dot11 * dot02 - dot01 * dot12) * inverseDenominator;
float v = (dot00 * dot12 - dot01 * dot02) * inverseDenominator;

return (u > 0.0f) && (v > 0.0f) && (u + v < 1.0f);
}

public int orientation(Vector2 p1, Vector2 p2, Vector2 p3) {
float crossProduct = (p2.y - p1.y) * (p3.x - p2.x) - (p3.y - p2.y) * (p2.x - p1.x);
return (crossProduct < 0.0f) ? -1 : ((crossProduct > 0.0f) ? 1 : 0);
}

public boolean intersect(Vector2 p1, Vector2 q1, Vector2 p2, Vector2 q2) {
return (orientation(p1, q1, p2) != orientation(p1, q1, q2)
&& orientation(p2, q2, p1) != orientation(p2, q2, q1));

}


}

attribute vec3 a_position;
attribute vec3 a_texCoord;
uniform mat4 u_projTrans;
varying vec3 tex;
void main() {
tex = a_texCoord;
gl_Position =  u_projTrans * vec4(a_position.xy, 0.0, 1.0);
}


uniform vec4 u_color;
varying vec3 tex;

void main() {
vec3 uv = tex;
float val = pow(uv.x, 3) - uv.y * uv.z;

vec4 mycol = vec4(u_color.xyz, 1.0);

if(val < 0.0 )  mycol = vec4(1.0, 0.0, 0.0, 1.0);
gl_FragColor = mycol;
}


here are few screenshot of the problems:

They suppose to be like these This is an executable jar file of the application.

Can anyone tell me how to fix this issue? i'm pulling my hair for few weeks now.

• What artifacts are you seeing? Those curves look reasonable to me. Nov 15, 2018 at 21:24

found the problem, it was the shader. I am using following shader, that works fine

// Cubic.fsh
uniform vec4 insideColor;
varying vec4 v_textCoord;

void main(void) {
vec3 v_klm = v_textCoord.xyz;
float t = v_klm.x * v_klm.x * v_klm.x - v_klm.y * v_klm.z;
float alpha = clamp(sign(t), 0.0, 1.0);
gl_FragColor = insideColor * alpha;
}

• Please include the essential parts of the solution in the actual answer rather than just linking elsewhere. Nov 17, 2018 at 14:50