Draw2d GL_POLYGON

[jorat1346]

Hi,

when drawing object using this:

view.draw2d GL_POLYGON, arrayOfPoint

the polygon is not drawn correctly. This link explain a bit the problem: http://www.codeproject.com/KB/openGL/OpenGL_Geometric.aspx#GL_POLYGON57

To solve that problem, we have to implement the two-ears algorithm.

My question is: as anyone here have already implemented that algorithm in ruby/skechup or an equivalent to solve that problem?

Thanks
Jo

[thomthom]

Can you give an example of an polygon not drawn correctly?

Are you referring to the likes of this?

If so - isn't that just because the points given in an order so that the lines cross? The shape would draw correct if the points had specified two triangular polygons.

[jorat1346]

I'm reffering to the shape 3:

There is definitely a problem with it. The link that i'm referring to is for a bug in opengl, but the same bug appear in sketchup when using draw2d.

[thomthom]

Oh... so convex shapes will all be drawn like that? That's a bit of a bugger...

[thomthom]

Appreciate it!
I've not had to draw such polygons - yet. But I'm sure I'd run into it in the near future as I've been using more and more of view.draw to make tool UI.

Thanks for the link to the original C++ - might be interesting to port into an Ruby C extension.

[Chris Fullmer]

Yeah, very cool. Thanks!

[jorat1346]

@thomthom said:

Oh... so convex shapes will all be drawn like that? That's a bit of a bugger...

In fact.

But good news, I applied my good still in ruby (started to program in ruby last friday) to translate an algorithm that fix just that which we call polygon triangulation.

I converted the algorithm from c++ to ruby:
(Original source code: http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml)

# @param contour is an array of Vector2d
# @return area
def triangulateArea(contour)
	n = contour.length
	a = 0
	p = n - 1
	for q in 0...n do
		c1 = contour[p]
		c2 = contour[q]
		a = a + c1.x * c2.y - c2.x * c1.y
		p = q
	end
	return a / 2
end

# Check is P is inside the triangle formed by A-B-C.
# @param A Point3d of the triangle
# @param B Point3d of the triangle
# @param C Point3d of the triangle
# @param P Point3d that have to be checked if inside A-B-C
# @return true if inside.
def triangulateInsideTriangle(ax, ay, bx, by, cx, cy, px, py)
	i_ax = cx - bx
	i_ay = cy - by
	i_bx = ax - cx
	i_by = ay - cy
	i_cx = bx - ax
	i_cy = by - ay
	apx = px - ax
	apy = py - ay
	bpx = px - bx
	bpy = py - by
	cpx = px - cx
	cpy = py - cy

	aCROSSbp = i_ax*bpy - i_ay*bpx
	cCROSSap = i_cx*apy - i_cy*apx
	bCROSScp = i_bx*cpy - i_by*cpx

	return aCROSSbp >= 0 && bCROSScp >= 0 && cCROSSap >= 0
end

# param contour is an array of Point3d where z is not used.
# param u is an index  in tV
# param v is an index  in tV
# param w is an index  in tV
# param n is the size of tV
# param tV is an array in index in contour.
def triangulateSnip(contour, u, v, w, n, tV)
	ax = contour[tV[u]].x
	ay = contour[tV[u]].y

	bx = contour[tV[v]].x
	by = contour[tV[v]].y

	cx = contour[tV[w]].x
	cy = contour[tV[w]].y

	if 0.0000000001 > (((bx-ax)*(cy-ay)) - ((by-ay)*(cx-ax)))
		return false
	end

	for p in 0...n do
		if p != u && p != v && p != w
			px = contour[tV[p]].x
			py = contour[tV[p]].y
			if triangulateInsideTriangle(ax,ay,bx,by,cx,cy,px,py)
				return false
			end
		end
	end

	return true
end

# @param contour is an array of Point3d for a polygon
# @return an array of Point3d where all 3 points is a triangle which
#		  can be drawn with "view.draw2d GL_POLYGON, result"
def triangulateProcess(contour)
	result = Array.new
	
	n = contour.length
	if n < 3
		puts "Error; contour.length < 3"
		return nil
	end

	# We want a counter-clockwise polygon in tV
	tV = Array.new
	if triangulateArea(contour) > 0
		for v in 0...n do
			tV << v
		end
	else
		for v in 0...n do
			tV << ((n - 1) - v)
		end
	end
	
	nv = n

	# Remove nv-2 Vertices, creating 1 triangle every time
	count = 2 * nv   # Error detection
	
	m = 0
	v = nv - 1
	while nv > 2
		# if we loop, it is probably a non-simple polygon
		if count <= 0
			# Triangulate; ERROR - probable bad polygon!
			puts "ERROR - probable bad polygon! ???"
			return nil
		end
		count -= 1

		# three consecutive vertices in current polygon, <u,v,w>
		u = v
		if u >= nv
			u = 0 # previous
		end
		v = u + 1
		if v >= nv
			v = 0 # new v
		end
		w = v + 1
		if w >= nv
			w = 0 # next
		end

		if triangulateSnip(contour,u,v,w,nv,tV)
			# true names of the vertices
			a = tV[u]
			b = tV[v]
			c = tV[w]

			# output Triangle
			result << contour[a]
			result << contour[b]
			result << contour[c]

			m += 1

			# remove v from remaining polygon
			s = v
			t = v + 1
			while t < nv
				tV[s] = tV[t]
				s += 1
				t += 1
			end
			nv -= 1

			# resest error detection counter
			count = 2 * nv
		end
	end
	
	return result
end

How to use:
You have to call triangulateProcess with an array of point that compose the polygon. It will return an array of point. But, this array is formed in a way that every 3 points create a triangle and can be used directly by view.draw2d GL_TRIANGLES. Ex:

array = [[0,20,0],[20,0,0],[30,30,0],[20,20,0]]
r = triangulateProcess(array)
if !r.nil?
	view.draw2d GL_TRIANGLES, r
end

I hope it will be help some of you,
Sincerely,
Jo

EDIT: Fixed errors in the code.