OSDev.org

Hi,

Does anyone know how to do curve shaped scanline filling?

I am stucked in fp coordinary intersection.
When rounding fp to int, several intersection points might appear.

(OT: /me never ceases to wonder: No matter how much you know, as soon as someone talks about an area of expertise you haven't touched yet, it sounds like {technobabble} all over again just like the first day...)

A scanline is always straight, i.e. not a curve.

Context please?

similar to polygon fill, but polygon edge is line, only one scanline intersection point per edge.

A quadratic curve may have 1 or 2 intersection point per scanline filling, and its coordinate is floating point. When rounding to integer, it produces 2+ integer intersection point, that makes scanline filling hard to work.

Assume to fill a half moon pattern on screen, which pixels to spot?

A quadratic polynomial curve has atmost two intersections with any line, and atmost two maxima with any plane intersection. Yes, those locations are floats, but conversion from float to integer only yields one and only one integer per float (which does differ based on the rounding used, but you use a fixed one for each edge, so each float maps to exactly one integer)

In addition, I have a raytracer which renders implicit quadratics with the help of scanline rendering, and from experience I only get atmost two float intersections, and thus atmost two integer intersections.

So I still fail to see the problem.

Regarding the half-moon object - it isn't a pure quadratic, it is a composition of two quadratic surfaces like you do constructive solid geometry. That means that for the total object, you get four intersections (atmost two for each base object), and you demand a certain property of the overlapping area, usually one of: both (intersection), either (union), or one but not the other (subtraction). The surface is then defined for each of the 5 segments between the points, and you get the answer by checking each segment of the scanline for the desired property.

hi, combuster,

how to make only one intersection point, when comparing to two floating point values.
it's rare that two floating point are the same exactly.

I set quadratic curve coefficent T, stepping in 0.01,
then I got points like [10.3 , 10.2], [11.1 , 10.4],
after rounding to integer, I got [10 , 10], [11 , 10]

so I got 2 adjacent intersection, that fails my scanline renderer.

scanlines share a (Y-)coordinate. You are trying to render a diagonal line as a horizontal line (which obviously does not work).

for scanline conversion:

y = ax²+bx+c
solve x coordinates for each y

x = b+V(b²-4ac) / 2a
and
x = b-V(b²-4ac) / 2a

which yields (x1, y) and (x2, y) as intersections.

I forget their math connection for a long time.

y = ax²+bx+c

could you please give me the detailed code?

and it looks like the curve could be rotated, to form the shape.

I am not good at math, but I have the feeling.

blackoil wrote:could you please give me the detailed code?

Not going to do your homework.

Hi,

blackoil wrote:and it looks like the curve could be rotated, to form the shape.

I get the feeling you're going about it the wrong way to begin with. Any curves get converted into vertexes and lines during pre-processing, and the rendering code never sees any curves (it just rotates/scales/translates vertexes, and follows lines between vertexes).


Cheers,

Brendan

I checked wikipedia, the curve I mentioned before was Quadratic Bezier Curve, not Quadratic Equation. If found good way to get valid intersections, it's not difficult to fill its area, even for higher degree curve.

Combuster wrote:A quadratic polynomial curve has atmost two intersections with any line, and atmost two maxima with any plane intersection. Yes, those locations are floats, but conversion from float to integer only yields one and only one integer per float (which does differ based on the rounding used, but you use a fixed one for each edge, so each float maps to exactly one integer)

In addition, I have a raytracer which renders implicit quadratics with the help of scanline rendering, and from experience I only get atmost two float intersections, and thus atmost two integer intersections.

So I still fail to see the problem.

Regarding the half-moon object - it isn't a pure quadratic, it is a composition of two quadratic surfaces like you do constructive solid geometry. That means that for the total object, you get four intersections (atmost two for each base object), and you demand a certain property of the overlapping area, usually one of: both (intersection), either (union), or one but not the other (subtraction). The surface is then defined for each of the 5 segments between the points, and you get the answer by checking each segment of the scanline for the desired property.

Wow...amazing.

*Visits Combuster's profile page, and bookmarks it. Begins drafting out how much $$ I'll offer Combuster to join my dev team when the time comes.*

Oh...and *makes threatening face at all other forum members to back off.*