@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.
