Hello,

When describing a filled polygon the borders of the pixels must be 
described.

But what if I want a "wired" polygon.

If I simply draw "lines" or "line loop" then opengl doesn't know if the 
pixel should be drawn on left side or right side of border/edge.

Or top or bottom of border/edge

This in itself is ofcourse a bit weird... because OpenGL does know how to do 
it for filled polygons but not for wired polygons ?!?

What if I want to make a game and draw a wired polygon ?!?

Currently I would have to modify coordinates to be at the center of pixels 
instead of borders which would be a bit weird... since top left, would be 
+0.5, +0.5 while bottom right would -0.5, -0.5 which means I would have to 
detect corners myself... which is a bit strange to do myself ?!?

But perhaps OpenGL has some kind of support for wired polygons ?

Perhaps even "contour polygons" to draw contours only ? Then again that last 
part would be a bit weird since it has triangles and convex polygons only... 
but still... even for a triangle fan or triangle strip it could leave out 
the inner edges...

So I wonder is there an easy way to render a "border/boundary/edge/wired" 
polygon ?
(Without too much hassle ?)

Bye,
  Skybuck. 

I tried the following:

  glPolygonMode( GL_FRONT_AND_BACK, GL_LINE);

  glBegin( GL_TRIANGLES );

    // shaded triangles (color per coordinate)
  glEnd();

This does not solve the problem and does something strange.

Instead of right side +1 pixel and bottom right side + 1 pixel it's now

top +1 pixel and right side +1 pixel.

So for now it seems opengl does not have an easy mode to simply draw 
pixels/wires on the inside of a triangle instead of some sides inside and 
some outside.

Bye,
  Skybuck. 

I also tried:

glPolygonMode( GL_FRONT, GL_LINE);

 glBegin( GL_TRIANGLES );

   glEdgeFlagv( @vFlag ); // set to GL_TRUE

    // shaded triangles (color per coordinate)
 glEnd();

Doesn't help... the wires are still one pixel to the top and right side.

So to me it seems OpenGL has a little bit of a problem with rendering wires 
for polygons/triangles... it's slightly inaccurate.

The problem could be corrected by me, but then I would have to modify 
coordinates on a per corner basis... which is kinda annoying isn't it ;)

(In my case it would be simply to do...) but in other cases it might not be 
so simple... like diagonals/all kinds of triangles... this disappoints me a 
little bit about opengl... apperently it doesn't consider polygon wires to 
be important enough to do it properly... I hope you understand that there is 
a difference between a line and a polygon_line. In the first case the 
coordinates need to be in center of pixels to be drawn properly... since 
there is no further information.
In the later case it's known and required to describe the boundaries of the 
pixels, and there is normal information available.. at least there should 
be... so it should be possible for opengl to draw the pixel at the correct 
side of the polygon_line.

Bye,
  Skybuck. 

On Thu, 23 Dec 2010 08:07:34 +0100, Skybuck Flying wrote:

> So to me it seems OpenGL has a little bit of a problem with rendering wires 
> for polygons/triangles... it's slightly inaccurate.

> I hope you understand that
> there is a difference between a line and a polygon_line.

No there isn't.

If you believe that there is, then OpenGL probably isn't going to do what
you expect.

"Nobody" <nobody@nowhere.com> wrote in message 
news:pan.2010.12.23.18.56.04.485000@nowhere.com...
> On Thu, 23 Dec 2010 08:07:34 +0100, Skybuck Flying wrote:
>
>> So to me it seems OpenGL has a little bit of a problem with rendering 
>> wires
>> for polygons/triangles... it's slightly inaccurate.
>
>> I hope you understand that
>> there is a difference between a line and a polygon_line.
>
> No there isn't.
>
> If you believe that there is, then OpenGL probably isn't going to do what
> you expect.

Conceptually there is and opengl should follow that concept since it follows 
it as well for filled polygons.

Filled polygons have the pixels on the inside, not the ouside.

So a wired polygon should have the pixels on the inside as well, it makes 
little sense to have them on the outside.

It would indeed be better if the lines were over the center but that's a bit 
impractical.

That would require two datasets, one for a surrounding around the pixels and 
one for through the pixels.

And therefore I would like it if opengl had better wire support for polygons 
so that at least the pixels would be on the inside instead of on the outside 
as it is now... it's actually half-half so that's bad.

For an opengl implementation it should be easy to understand if the pixels 
are supposed to be on the inside... and therefore opengl could simply 
adjusts the coordinates to be not on the inside but actually through the 
center.

Bye,
  Skybuck. 

On Thu, 23 Dec 2010 20:34:33 +0100, Skybuck Flying wrote:

> So a wired polygon should have the pixels on the inside as well, it makes 
> little sense to have them on the outside.

A line doesn't have an inside or an outside. Even if it's part of a
polygon, it might be the edge between two polygons (even if you're
only drawing one polygon at a time; the implentation can't know what
you're going draw in the future).

Setting glPolygonMode() to GL_LINE is supposed to produce identical
results to just drawing lines between each pair of vertices corresponding
to a polygon edge. IOW, glBegin(GL_POLYGON) and glBegin(GL_LINE_LOOP)
should be indistinguishable in this mode.

Trying to draw lines around the interior or exterior of a polygon is
actually quite problematic, particularly when you allow for non-square
pixels, smooth lines, wide lines, multi-sampling, etc.

"Nobody" <nobody@nowhere.com> wrote in message 
news:pan.2010.12.23.23.13.02.313000@nowhere.com...
> On Thu, 23 Dec 2010 20:34:33 +0100, Skybuck Flying wrote:
>
>> So a wired polygon should have the pixels on the inside as well, it makes
>> little sense to have them on the outside.
>
> A line doesn't have an inside or an outside.

Precisely.

> Even if it's part of a polygon,

Nope, there it's clear on what side the pixels should lie.

> it might be the edge between two polygons (even if you're
> only drawing one polygon at a time; the implentation can't know what
> you're going draw in the future).

Doesn't make any sense, because currently opengl seems to draw filled 
polygons just fine, and for filled polygons it does draw the pixels on the 
inside, so it doesn't seem to matter if there is another polygon next to it 
or not, so your point seems to be totally invalid.

> Setting glPolygonMode() to GL_LINE is supposed to produce identical
> results to just drawing lines between each pair of vertices corresponding
> to a polygon edge. IOW, glBegin(GL_POLYGON) and glBegin(GL_LINE_LOOP)
> should be indistinguishable in this mode.

It should not because that would be pointless.

> Trying to draw lines around the interior or exterior of a polygon is
> actually quite problematic, particularly when you allow for non-square
> pixels, smooth lines, wide lines, multi-sampling, etc.

It doesn't seem to be a problem... opengl fills polygons just fine... so all 
it might need to do is simply draw one pixel to the inner side as it's fill 
algorithm does and then simply stop drawing any further pixels.

If anybody has an opengl implementation, perhaps a software one, then give 
it a try... it would be most interesting to see the results of such a 
polygon-line drawing attempt.

Bye,
  Skybuck. 

On Fri, 24 Dec 2010 01:54:51 +0100, Skybuck Flying wrote:

>> Even if it's part of a polygon,
> 
> Nope, there it's clear on what side the pixels should lie.

Nope. Lines are lines.

>> it might be the edge between two polygons (even if you're
>> only drawing one polygon at a time; the implentation can't know what
>> you're going draw in the future).
> 
> Doesn't make any sense, because currently opengl seems to draw filled 
> polygons just fine, and for filled polygons it does draw the pixels on the 
> inside, so it doesn't seem to matter if there is another polygon next to it 
> or not, so your point seems to be totally invalid.

Well duh, it's a polygon.

Rasterising a polygon means generating the set of fragments whose centres
are inside the geometric polygon. Rasterising a line means generating the
contiguous set of fragments whose centres are closest to the geometric
line. Statistically, half of those fragments will be on one side of the
line and the other half on the other side. If you discard the fragments on
one side of the line, the remaining fragments won't be contiguous.

>> Setting glPolygonMode() to GL_LINE is supposed to produce identical
>> results to just drawing lines between each pair of vertices corresponding
>> to a polygon edge. IOW, glBegin(GL_POLYGON) and glBegin(GL_LINE_LOOP)
>> should be indistinguishable in this mode.
> 
> It should not because that would be pointless.

Nope. "Does not do what Skybuck wants" isn't the same thing as
"pointless", nor is it likely to be of any concern to the implementors of
OpenGL.

>> Trying to draw lines around the interior or exterior of a polygon is
>> actually quite problematic, particularly when you allow for non-square
>> pixels, smooth lines, wide lines, multi-sampling, etc.
> 
> It doesn't seem to be a problem... opengl fills polygons just fine...

Drawing lines and filling polygons are very different processes. Maybe if
you learned how these tasks are performed you might understand this.

> so all 
> it might need to do is simply draw one pixel to the inner side as it's fill 
> algorithm does and then simply stop drawing any further pixels.

A polygon filling algorithm is quite different to a line drawing
algorithm. Polygon filling traces the left and right edges vertically,
then fills in the horizontal strip between the edges for each scan line.

Line drawing chooses the longest axis as the independent variable then
calculates the displacement along the other axis as a linear function of
that (e.g. Bresenham's Algorithm). IOW, near-horizontal lines are drawn
using "foreach x: plot x, y(x)", near-vertical lines are drawn using
"foreach y: plot x(y), y".

The vertical case isn't that much different to how polygon filling works,
but the horizontal case is entirely different. Tracing the near-horizontal
edges of a polygon would require additional logic in the hardware, for a
feature which currently isn't provided by any standard graphics API
(DirectX doesn't do it either).

Also there seems to be a problem with the line drawing itself.

It does not draw the last pixel ?

For example a vertical line from (0.5,0.5) to (9.5,9.5) would not draw pixel 
the 10th pixel located at (9.5, 9.5). (9,9)

Bye,
  Skybuck. 

"Skybuck Flying" <IntoTheFuture@hotmail.com> wrote in message 
news:f1f62$4d1427db$54190f09$31475@cache1.tilbu1.nb.home.nl...
> Also there seems to be a problem with the line drawing itself.
>
> It does not draw the last pixel ?
>
> For example a vertical line from (0.5,0.5) to (9.5,9.5) would not draw 
> pixel the 10th pixel located at (9.5, 9.5). (9,9)

All kinds of weird problems with opengl... I must come to the conclusion 
that it's drawing routines, especially the lines are not suited for pixel 
perfect drawing... which at the moment I need to test something..

So back to TCanvas for me it is unfortunately ;)

Bye,
  Skybuck.

"Nobody" <nobody@nowhere.com> wrote in message 
news:pan.2010.12.24.03.10.03.516000@nowhere.com...
> On Fri, 24 Dec 2010 01:54:51 +0100, Skybuck Flying wrote:
>
>>> Even if it's part of a polygon,
>>
>> Nope, there it's clear on what side the pixels should lie.
>
> Nope. Lines are lines.

Nope,

Example Pixel 0 and Pixel 1.

The edge of those pixels is defined as:

C0   C1     C2
+-----+------+
   P0     P1

C1

Therefore if I tell opengl that my line lies on C1 it does not know where to 
draw the pixels.

It could either be P0 or P1

Any choice would be arbitrary.

Now so for a polygon.

If C1 is the edge on the right side it would make perfect sense to fill P0 
and not P1.

However currently this logic is not present in OpenGL which is a flaw.

There are further flaws, like not drawing the last pixel of a line it seems.

<rest of drivel snipped>

Bye,
  Skybuck. 

On Fri, 24 Dec 2010 06:35:51 +0100
"Skybuck Flying" <IntoTheFuture@hotmail.com> wrote:

> Nope,
> 
> Example Pixel 0 and Pixel 1.
> 
> The edge of those pixels is defined as:
> 
> C0   C1     C2
> +-----+------+
>    P0     P1
> 
> C1
> 
> Therefore if I tell opengl that my line lies on C1 it does not know
> where to draw the pixels.

Of course it know it, it's completely deterministic. For the very first
pixel of the line:

if(slope < 1):
	if(P0.x < P1.x):
		fill(P0)
	else:
		fill(P1)
else:
	if(P0.y < P1.y):
		fill(P0)
	else:
		fill(P1)

The rest follows from Bresenham's algorithm, which deals with _lines_.
The kind of lines GL_LINE provide are just that: Lines drawn using the
Bresenham algoritm, possible on a subpixel grid for antialiasing.

I think what you're looking for are _strokes_. OpenGL is not a vector
graphics API like, say OpenVG, so problems of this kind are out of the
scope of pure OpenGL, but can be implemented using it.

If you want to draw strokes, derive a quad or triangle strip along
the line having the desired width. But be carefull at steep angles,
there will be intersections happening. What you're doing, in
mathematical terms, is convoluting the line with a shape defining the
stroke.

And now it happened: I don't remember the name of the method, just
recall, that its inventors name started with an 'M' (I think). So sorry
for not giving you a link to Wikipedia.
 
> It could either be P0 or P1
> 
> Any choice would be arbitrary.

The choice is as arbitrary as rounding off 0.5 to an integer.
 
> Now so for a polygon.
> 
> If C1 is the edge on the right side it would make perfect sense to
> fill P0 and not P1.

Yes, but lines and polygons are drawn by completely different methods.
In the case of a polygon (or a triangle) the rasterizer sweeps the
lines, does it hit an edge it increments an counter. And if the counter
is odd, the sweep is inside a filled area. If we further say, that a
polygon may only be convex, then the counter can be replaced with a
single bit, hitting the opposite edge stopping the sweep for the
current line.

Remember that GL_LINE_LOOP will draw you a line for any number of
arbitrarily given vertices, as long as it's more than 2 vertices. For a
line loop there's no constraint on convexity.

GL_POLYGON sets up the constraint that things must be convex.

Triangles are always convex, so GL_TRIANGLES, GL_TRIANGLE_STRIP or
GL_TRIANGLE_FAN set up another constraint: You must pass a number of
vertices that whole triangles can be formed, so for GL_TRIANGLES these
are multiple of 3, the other two it's >=3 -- however each triangle is
drawn at it's own.

Which brings us back to GL_POLYGON. One can look at GL_POLYGON as a
GL_TRIANGLE_FAN with the start vertex placed somewhere in the polygon
and due to the "somewhere" in the interior it may as well mean: start
vertex is the first vertex of the polygon cycle. If you then remember
the implications GL_TRIANGLE_FAN on the edge flag and how edge flags
influence the polygon drawing mode, you see why in the case of a GL_LINE
polygon mode the whole thing must coerce down to Bresemham's algorithm.

> However currently this logic is not present in OpenGL which is a flaw.

It's only a flaw in your thinking. 

> There are further flaws, like not drawing the last pixel of a line it
> seems.

That's so by design. It has been designed that way with full intention.
And it's not only OpenGL behaving that way. You normally stop
Bresenham's algorithm one pixel short, so that if you continue the
strip you won't touch the starting/ending pixel twice.


Wolfgang

On Fri, 24 Dec 2010 05:59:32 +0100, Skybuck Flying wrote:

>> Also there seems to be a problem with the line drawing itself.
>>
>> It does not draw the last pixel ?
>>
>> For example a vertical line from (0.5,0.5) to (9.5,9.5) would not draw 
>> pixel the 10th pixel located at (9.5, 9.5). (9,9)

This is intentional. If you draw a line from (x1,y1) to (x2,y2) then
another line from (x2,y2) to (x3,y3), the pixel containing (x2,y2) must
not be drawn twice. Doing so would have undesirable consequences when
using e.g. alpha blending or glLogicOp(GL_XOR).

While OpenGL doesn't specify exactly which pixels must be drawn, it does
impose some constraints, and the "no duplicates" rule is one of them (the
standard only requires that no duplicates occur when either both lines are
x-major or both lines are y-major, but implementations are likely to
follow it in all cases if it doesn't impose an undue burden).

> All kinds of weird problems with opengl... I must come to the conclusion 
> that it's drawing routines,

OpenGL's "drawing routines" usually boil down to "send commands to the
video hardware". While software implementations exist, OpenGL was designed
to be implemented in hardware. For this reason, it allows a certain amount
of latitude to the implementation. You might want to read the "Invariance"
section of the specification to see what guarantees it provides (or
doesn't provide).

On Fri, 24 Dec 2010 06:35:51 +0100, Skybuck Flying wrote:

>> Nope. Lines are lines.
> 
> Nope,
> 
> Example Pixel 0 and Pixel 1.
> 
> The edge of those pixels is defined as:
> 
> C0   C1     C2
> +-----+------+
>    P0     P1
> 
> C1
> 
> Therefore if I tell opengl that my line lies on C1 it does not know where to 
> draw the pixels.
> 
> It could either be P0 or P1
> 
> Any choice would be arbitrary.

You would normally perturb the endpoint in the direction of slope. I.e. if
the next pixel will be in P1, you also draw the first pixel in P1. In any
case, it doesn't matter whether the line results from e.g.
glBegin(GL_LINES) or from glPolygonMode(GL_LINE).

> However currently this logic is not present in OpenGL which is a flaw.

It's not present in any graphics API I've ever encountered. Apart from
anything else, it would require the hardware to implement two
different line-drawing algorithms.

> Now so for a polygon.
> 
> If C1 is the edge on the right side it would make perfect sense to fill
> P0 and not P1.

This wouldn't have any effect if the point isn't exactly on the boundary
between pixels, which is the usual case. Particularly when the coordinates
have usually been subjected to affine transformation followed by
perspective division, both with finite precision.

> There are further flaws, like not drawing the last pixel of a line it seems.

That behaviour is dictated by the standard, and is likely to be assumed by
anyone with experience in graphics programming.

"Wolfgang Draxinger" <wdraxinger@darkstargames.de> wrote in message 
news:20101224113138.60ea0d70@narfi.yggdrasil.draxit.de...
> On Fri, 24 Dec 2010 06:35:51 +0100
> "Skybuck Flying" <IntoTheFuture@hotmail.com> wrote:
>
>> Nope,
>>
>> Example Pixel 0 and Pixel 1.
>>
>> The edge of those pixels is defined as:
>>
>> C0   C1     C2
>> +-----+------+
>>    P0     P1
>>
>> C1
>>
>> Therefore if I tell opengl that my line lies on C1 it does not know
>> where to draw the pixels.
>
> Of course it know it, it's completely deterministic. For the very first
> pixel of the line:

Ofcourse it does not know it for vertical lines.

>
> if(slope < 1):

Bresenham doesn't work with slopes.

Vertical lines don't even have slopes.

> if(P0.x < P1.x):
> fill(P0)
> else:
> fill(P1)
> else:
> if(P0.y < P1.y):
> fill(P0)
> else:
> fill(P1)

What if there is a vertical line running exactly from C1 downwards.

That's pretty much the example I was trying to give, here is better example:


C0   C1     C2
+-----+------+
   P0     P1
+-----+------+
   P2     P3
+-----+------+
C0   C1      C2

<rest of drivel snipped>

Bye,
  Skybuck. 

On Sat, 25 Dec 2010 03:01:55 +0100
"Skybuck Flying" <IntoTheFuture@hotmail.com> wrote:

> > if(slope < 1):
> 
> Bresenham doesn't work with slopes.

Bresenham accumulates an error with every step in the major direction
and increments the minor one the error 

> Vertical lines don't even have slopes.

Of course they have, it just can't be written down as a number in a
fixed coordinate system, but from a mathematical point of view it can be
written very well as a limit therein. By changing the coordinate system
that limit can be lifted.

Saying "vertical lines have no slope" is like saying "x^2 = -1 has no
solution". They seem not to have if you're mentally stuck, but by
looking it from an widened point of view they very well have.

> > if(P0.x < P1.x):
> > fill(P0)
> > else:
> > fill(P1)
> > else:
> > if(P0.y < P1.y):
> > fill(P0)
> > else:
> > fill(P1)
> 
> What if there is a vertical line running exactly from C1 downwards.

Then swap x<->y, actually you swap if the slope abs(delta_Y/delta_X)>1

And that's exactly the very first "if" statement of my pseudocode,
which you snipped.

> That's pretty much the example I was trying to give, here is better
> example:

Just implement a simple Bresenham yourself and test it with your
"pathologic" cases (which they are not). Use a step debugger to see
what happens.


Wolfgang

The point I was trying to make is not about, math, slopes, your code, or 
bresenham.

The point I am trying to make is on which side should a pixel lie, if the 
line goes vertical between the pixels itself.

You choose to ignore this problem, so be it.

Bye,
  Skybuck. 

On 12/23/2010 7:10 PM, Nobody wrote:
> On Fri, 24 Dec 2010 01:54:51 +0100, Skybuck Flying wrote:
> A polygon filling algorithm is quite different to a line drawing
> algorithm. Polygon filling traces the left and right edges vertically,
> then fills in the horizontal strip between the edges for each scan line.

 From what I heard, nowadays, rasterizing triangles consists 
more in rasterizing a quad and testing for triangle 
inside/outside for each fragment. This is much more adapted 
to the parallel graphics hardware...

Cheers

-- 
Nicolas Bonneel
http://cs.ubc.ca/~nbonneel/