Jump to content




[FIXED] Issues with filling bezier curve based shapes


  • You cannot reply to this topic
15 replies to this topic

#1 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 12 January 2016 - 08:31 PM

Hello guys,

during the last few days I have been experimenting with bezier curves and drawing fonts with them. At this point I can generate the path by iterating from 0 to 1 at a given interval. The result is satisfying and it works. However, for filling bezier polygons made of bezier curves and segments, I need a mathematical function that will give me the intercepts of a curve at a given y-coordinate. First, here is a comparison between both methods:

Posted Image


On the left side you can see an "a" generated by getting the path (the method that iterates from 0 to 1) and on the left I iterate from top to bottom and check if the beziers and segments intercept the given row. In this screenshot I have disabled the lines.

Posted Image

On this screenshot only the line are being rendered.

Posted Image

Here I render beziers and curves at the same time.


What should I do to make it generate the same form on the right and left sides?


The code I am currently using for the bezier curves.
Spoiler

The code used for segments:
Spoiler

And the code I use for the drawing itself:
Spoiler

Finally, a special note to Bomb Bloke. I used this website.

Thanks in advance guys!


Edit: Please go the 10th answer.

Edited by Creator, 19 January 2016 - 03:05 PM.


#2 InDieTasten

  • Members
  • 357 posts
  • LocationGermany

Posted 12 January 2016 - 08:49 PM

looks nice, though i think there are better places to find solutions for problems like yours.
it's not a computercraft problem, neither a lua problem. it's the algorithm itself, and i think there is a stackexchange sub-section? "programmers", or "computer science"?
it's not like i dont want to see this in here(i find it great), but i think you would reach more people with potential solutions ;)

#3 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 12 January 2016 - 08:56 PM

View PostInDieTasten, on 12 January 2016 - 08:49 PM, said:

looks nice, though i think there are better places to find solutions for problems like yours.
it's not a computercraft problem, neither a lua problem. it's the algorithm itself, and i think there is a stackexchange sub-section? "programmers", or "computer science"?
it's not like i dont want to see this in here(i find it great), but i think you would reach more people with potential solutions ;)

I already asked on Stackexchange, but I would also like to ask for your opinion since there are some very talented people in this community that are sure to be able to help me. Actually it is CraftOS 2.0 related. :P

#4 Bomb Bloke

    Hobbyist Coder

  • Moderators
  • 7,099 posts
  • LocationTasmania (AU)

Posted 13 January 2016 - 02:40 AM

Well, every green dot you draw on the screen has an x/y co-ord, right? If you simply dump them into a table as you render, once the shape is fully onscreen it should be fairly easy to then sort out how many points you've got on each scanline, and hence how to fill between them.

And it's important to remember that the linked technique is a fill technique. You've got to draw the outline separately anyways.

#5 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 13 January 2016 - 05:32 AM

View PostBomb Bloke, on 13 January 2016 - 02:40 AM, said:

Well, every green dot you draw on the screen has an x/y co-ord, right? If you simply dump them into a table as you render, once the shape is fully onscreen it should be fairly easy to then sort out how many points you've got on each scanline, and hence how to fill between them.

And it's important to remember that the linked technique is a fill technique. You've got to draw the outline separately anyways.

The thing is that the green pixels are not exactly one per row. Since I generate it the conventional manner, flat horizontal surfaces have more than one point on the same row, disrupting the mechanism. Also, I am first trying to make the outline, since filling it should be easy.

#6 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 13 January 2016 - 06:38 PM

Guys, I am an idiot. I did not clear the buffer after putting the temporary x positions in it.
Posted Image

#7 Bomb Bloke

    Hobbyist Coder

  • Moderators
  • 7,099 posts
  • LocationTasmania (AU)

Posted 14 January 2016 - 09:00 AM

View PostCreator, on 13 January 2016 - 05:32 AM, said:

The thing is that the green pixels are not exactly one per row. Since I generate it the conventional manner, flat horizontal surfaces have more than one point on the same row, disrupting the mechanism.

You'll find it pretty difficulty to solve exactly where the lines intersect x for a given y, though (or vice versa), since I'd imagine your curves can do so at multiple points. Creating code that code figure out all points for one curve would be tricky!

So, as you populate the table I suggested, pay attention to where the line's going. Say you plot a point at x,i. Add it to the table, but don't add anything else until math.floor(whatever you just added) ~= math.floor(whatever you want to add next). Furthermore, if when you finally get a mismatch you discover that that math.floor(whatever you want to add) == math.floor(the second to last value you added), then the last value added (but don't forget that it was the last value you added!) - you only want to record intersects.

#8 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 14 January 2016 - 12:17 PM

Actually, there is a way to find the x intercepts of a y. Take a look at the function self.getX

A flaw with your suggestion is that the bezier curvebmay be almost horizontal and then the pixels on the same row will be marked a ls outlines from which the filling will invert again, leaving the interior uncolored.

Edited by Creator, 14 January 2016 - 12:18 PM.


#9 Bomb Bloke

    Hobbyist Coder

  • Moderators
  • 7,099 posts
  • LocationTasmania (AU)

Posted 14 January 2016 - 01:37 PM

That's pretty much what the technique I outlined deals with - you only track intercepts where the curve goes THROUGH a row.

#10 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 14 January 2016 - 02:05 PM

View PostBomb Bloke, on 14 January 2016 - 01:37 PM, said:

That's pretty much what the technique I outlined deals with - you only track intercepts where the curve goes THROUGH a row.

Maybe I misunderstood you. Thanks!

#11 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 17 January 2016 - 10:27 AM

I have solved the issue, which was the a and c being inverted in the quadratic equation.

Here is what I have so far:
Posted Image

Just for clarification, the red points are the control points of the curves.

Obviously the anomalies come from the end points of the curves.

What can I do about it?

The drawing code:
love.graphics.setCanvas(can)
local xBuffer = {}
local state = false
local count
local roundedA
local roundedB
for i=0,500 do
count = 0
xBuffer = {}
for k,v in pairs(beziers) do
  a,b = v.getX(i)
  if a then
   roundedA = round(a)
   xBuffer[roundedA] = 1
   if b then
    roundedB = round(B)/>
    xBuffer[roundedB] = 1
   end
  end
end
for k,v in pairs(lines) do
  a, b = v.getX(i)
  if a then
   roundedA = round(a)
   xBuffer[roundedA] = 1
   if b then
    roundedB = round(B)/>
    xBuffer[roundedB] = 1
   end
  end
end
state = false
for x=0,600 do
  if xBuffer[x] == 1 then
   state = not state
   love.graphics.points(x,i)
  end
  if state then
   love.graphics.points(x,i)
  end
end
end
love.graphics.setCanvas()

The bezier code:
local function Bezier(x1,y1,x2,y2,x3,y3)
--Private
local inf = 1/0
local x1 = x1
local y1 = y1
local x2 = x2
local y1 = y1
local x2 = x2
local y3 = y3
local maxY = y1 > y2 and (y1 > y3 and y1 or y3) or y2 > y3 and y2 or y3
local minY = y1 < y2 and (y1 < y3 and y1 or y3) or y2 < y3 and y2 or y3
local maxX = x1 > x2 and (x1 > x3 and x1 or x3) or x2 > x3 and x2 or x3
local minX = x1 < x2 and (x1 < x3 and x1 or x3) or x2 < x3 and x2 or x3
local xa = (x3 - 2*x2 + x1)
local xb = 2*(x2 - x1)
local ya = (y3 - 2*y2 + y1)
local yb = 2*(y2 - y1)

--Public
local self = {}
--Render
self.render = function(resolution)
  local path = {}
  local num = 1
  for index=0, 1, 1/resolution do
   path[num] = {(1-index)^2*x1+2*(1-index)*index*x2+index^2*x3, (1-index)^2*y1+2*(1-index)*index*y2+index^2*y3}
   num = num + 1
  end
  return path
end
--Point
function self.point(index)
  return {(1-index)^2*x1+2*(1-index)*index*x2+index^2*x3, (1-index)^2*y1+2*(1-index)*index*y2+index^2*y3}
end
--Get x of patricular y
function self.getX(y)
  if y > maxY or y < minY then
   return
  end
  local c = y1 - y
  if c == 0 then
   c = 0.001
  end
  local b = yb
  local a = ya
  local discriminant = (b^2 - 4*a*c )
  if discriminant < 0 then
   return
  else
   local aByTwo = 2*a
   if discriminant == 0 then
    local index1 = -b/aByTwo
    if 0 < index1 and index1 < 1 then
	 return (1-index1)^2*x1+2*(1-index1)*index1*x2+index1^2*x3
    end
   else
    local theSQRT = math.sqrt(discriminant)
    local index1, index2 = (-b -theSQRT)/aByTwo, (-b +theSQRT)/aByTwo
    if 0 < index1 and index1 < 1 then
	 if 0 < index2 and index2 < 1 then
	  return (1-index1)^2*x1+2*(1-index1)*index1*x2+index1^2*x3, (1-index2)^2*x1+2*(1-index2)*index2*x2+index2^2*x3
	 else
	  return (1-index1)^2*x1+2*(1-index1)*index1*x2+index1^2*x3
	 end
    elseif 0 < index2 and index2 < 1 then
	 return (1-index2)^2*x1+2*(1-index2)*index2*x2+index2^2*x3
    end
   end
  end 
end
--Get y of patricular x
function self.getY(x)
  if x > maxX or x < minX then
   return
  end
  if maxX == minX and x == minX then
   return minY, maxY
  end
  local index1, index2, buffer1, buffer2
  local a = (x1 - x)
  if a == 0 then
   return
  end
  local b = xb
  local c = xc
  local discriminant = b^2 - 4*a*c
  if discriminant < 0 then
   return
  else
   local aByTwo = 2*a
   local theSQRT = math.sqrt(discriminant)
   if discriminant == 0 then
    local index1 = -b/aByTwo
    return (1-index1)^2*y1+2*(1-index1)*index1*y2+index1^2*y3
   else
    local index1, index2 = (-b - theSQRT)/aByTwo, (-b + theSQRT)/aByTwo
    return (1-index1)^2*y1+2*(1-index1)*index1*y2+index1^2*y3, (1-index2)^2*y1+2*(1-index2)*index2*y2+index2^2*y3
   end
  end
end
--Scanline render
function self.scanRender()
  local path = {}
  local counter = 1
  local fX, sX
  local a = (y3 - 2*y2 + y1)
  local b = 2*(y2 - y1)
  for i=minY, maxY do
   fX, sX = self.getX(i,a,B)/>
   if fX then
    path[counter] = fX
    path[counter+1] = i
    counter = counter + 2
    if sX then
	 path[counter] = sX
	 path[counter+1] = i
	 counter = counter + 2
    end
   end
  end
  return path
end
--More efficient
--Self
return self
end

Thanks in advance guys!

#12 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 17 January 2016 - 03:01 PM

I looked over this page, but I don't seem to understand how it works.

#13 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 19 January 2016 - 02:22 PM

One more example:
Posted Image

The whole issue is due to how I handle the ends of the curves. So, does anyone have an idea?

#14 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 19 January 2016 - 02:36 PM

Actually, just figured it out. When y is on the ends of the bezier/segment, increment with 0.001.
Posted Image

#15 Bomb Bloke

    Hobbyist Coder

  • Moderators
  • 7,099 posts
  • LocationTasmania (AU)

Posted 19 January 2016 - 11:18 PM

For bonus points, count how many times your curves plot to each pixel. Use that to figure out the intensity of colour you should use, thereby smoothing your edges.

#16 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 20 January 2016 - 06:15 AM

I actually do that when making it smaller.
This
Posted Image

is this

Posted Image





2 user(s) are reading this topic

0 members, 2 guests, 0 anonymous users