Line drawing in SDL 1.3 (David Olofson)

SDL Development
1

David Olofson wrote:

Now, unless we’re switching to a Begin/…/End style interface, this would
mean something like this:

??? SDL_RenderLines(int npoints, int *x, int *y);
??? SDL_RenderLineStrip(int npoints, int *x, int *y);
??? SDL_RenderLinePolygon(int npoints, int *x, int *y);

(An odd number for ‘npoints’ to SDL_RenderLines() would be an error.)

Of course, one could keep the current SDL_RenderLine() as a convenient
shortcut for drawing a single line, or drop SDL_RenderLines() entirely. It’s
mostly a performance hack for certain backends.

These multi-point function calls irk me. Maybe it does not bother other people but often I would have a point structure of some kind (say struct Xy { int x, y}:wink: and I would have an array of these point structures for a polyline/polygon. If I had to call any of the above functions I’d have to mess about with ripping out each x and each y into their own arrays.

This is not the first time I have seen functions which expect x,y coordinates to be passed in this way which makes me wonder if this is because, down low, it is easier or faster to work with. Is that the case? I am just curious.

Robbert de Groot__________________________________________________________________
Looking for the perfect gift? Give the gift of Flickr!

http://www.flickr.com/gift/

2

[…]

SDL_RenderLines(int npoints, int *x, int *y);
SDL_RenderLineStrip(int npoints, int *x, int *y);
SDL_RenderLinePolygon(int npoints, int *x, int *y);

[…]

This is not the first time I have seen functions which expect x,y
coordinates to be passed in this way which makes me wonder if this is
because, down low, it is easier or faster to work with. Is that the case?

Yep - faster, more specifically. :slight_smile: (See my other post.)On Tuesday 08 December 2009, at 21.15.35, Robbert de Groot wrote:

–
//David Olofson - Developer, Artist, Open Source Advocate

.— Games, examples, libraries, scripting, sound, music, graphics —.
| http://olofson.net http://kobodeluxe.com http://audiality.org |
| http://eel.olofson.net http://zeespace.net http://reologica.se |
’---------------------------------------------------------------------’

3

[…]

SDL_RenderLines(int npoints, int *x, int *y);
SDL_RenderLineStrip(int npoints, int *x, int *y);
SDL_RenderLinePolygon(int npoints, int *x, int *y);

[…]

This is not the first time I have seen functions which expect x,y
coordinates to be passed in this way which makes me wonder if this is
because, down low, it is easier or faster to work with. Is that the case?

Yep - faster, more specifically. :slight_smile: (See my other post.)

I saw your other post, and I don’t see where passing separate arrays of Xs
and Ys would improve performance over passing a single array of Point
structs. Also, having two arrays increases the chance that something could
go wrong, such as one of them containing more values than the other.

Why not do something like this:

SDL_RenderLines(int npoints, SDL_Point* points);

Where SDL_Point is defined as {int X, int Y}? That would certainly make
it easier on the developers!>From: David Olofson

Subject: Re: [SDL] Line drawing in SDL 1.3 (David Olofson)
On Tuesday 08 December 2009, at 21.15.35, Robbert de Groot wrote:

4

[…]

SDL_RenderLines(int npoints, int *x, int *y);
SDL_RenderLineStrip(int npoints, int *x, int *y);
SDL_RenderLinePolygon(int npoints, int *x, int *y);

[…]

This is not the first time I have seen functions which expect x,y
coordinates to be passed in this way which makes me wonder if this is
because, down low, it is easier or faster to work with. Is that the
case?

Yep - faster, more specifically. :slight_smile: (See my other post.)

I saw your other post, and I don’t see where passing separate arrays of Xs
and Ys would improve performance over passing a single array of Point
structs.

Ah! Of course; the point is just avoiding function calls and other per-point
overhead. No matter how you format the data, it’s only going to match a few
implementations exactly - but that’s a minor issue anyway.

So, I think a single array of structs should be a perfectly fine alternative
from this POV. It’s just that it adds another datatype to the API, and it
still requires shoehorning to fit the design of any real application.

Also, having two arrays increases the chance that something could
go wrong, such as one of them containing more values than the other.

Yep… And twice the pointers to keep track of for the programmer as well; not
just the CPU.

Why not do something like this:

SDL_RenderLines(int npoints, SDL_Point* points);

Where SDL_Point is defined as {int X, int Y}? That would certainly make
it easier on the developers!

Yeah - and BTW, on the machine code level, that is actually identical to
passing a single int array where even values are x and odd values are y. That
is, only one pointer and better use of memory/cache, compared to the typical
"two arrays" model. Real nice for software implementations and possibly some
hardware implementations, but not so nice for backends that have to convert
back to “two arrays” format for some other API.On Tuesday 08 December 2009, at 21.45.19, Mason Wheeler wrote:

From: David Olofson <@David_Olofson>
Subject: Re: [SDL] Line drawing in SDL 1.3 (David Olofson)
On Tuesday 08 December 2009, at 21.15.35, Robbert de Groot wrote:

–
//David Olofson - Developer, Artist, Open Source Advocate

.— Games, examples, libraries, scripting, sound, music, graphics —.
| http://olofson.net http://kobodeluxe.com http://audiality.org |
| http://eel.olofson.net http://zeespace.net http://reologica.se |
’---------------------------------------------------------------------’

5

We could also do like bsearch() and qsort(). Each of these highly
common APIs dereferences members of an opaquely-typed vector, and ask
the programmer for the size of members in addition to the number of
members.

With C++ you can use templates to accomplish all of this implicitly at
compile time, provided you follow some naming conventions for x and y,
I guess.On Tue, Dec 8, 2009 at 3:15 PM, Robbert de Groot wrote:

These multi-point function calls irk me. Maybe it does not bother other people but often I would have a point structure of some kind (say struct Xy { int x, y}:wink: and I would have an array of these point structures for a polyline/polygon. If I had to call any of the above functions I’d have to mess about with ripping out each x and each y into their own arrays.

–
http://codebad.com/

6

David Olofson wrote:

So, I think a single array of structs should be a perfectly fine alternative
from this POV. It’s just that it adds another datatype to the API, and it
still requires shoehorning to fit the design of any real application.

An alternative would be to tell the function how to interpret one’s own
point structure:

void SDL_RenderLines(int npoints, void* points, int struct_size, int
x_offset, int y_offset);

…
SDL_RenderLines(x, points, sizeof(points[0]), (char*)&points[0].x -
(char*)&points[0], (char*)&points[0].y - (char*)&points[0]);
…

But that way one would still have to use the same data type for x and y
as used internally by SDL_RenderLines unless there are different
functions that accept different data types for them, a la OpenGL.

Cheers,

Andre

7

I was thinking about a similar approach; passing an array of pointers to
elements physically equivalent to struct { int x; int y; }, but I don’t think
there’s any point in anything like this.

Pointers are (at least) as large as integers, so the only case where you’d
gain anything is with the “one pointer per x/y struct” I suggested, and this
is only on 32 bit platforms. (64 bit platforms generally have 64 bit
pointers…) Even then, the pointer indirections will most likely eat anything
you gain by not copying, and then some.

Oh, and let’s not talk about all the ways you can get anything like this wrong
and get garbage data, segfaults and whatnot… :smiley:

So, just copy the values instead! It’s simpler, faster and safer. :-)On Tuesday 08 December 2009, at 23.40.37, Andre de Leiradella wrote:

David Olofson wrote:

So, I think a single array of structs should be a perfectly fine
alternative from this POV. It’s just that it adds another datatype to the
API, and it still requires shoehorning to fit the design of any real
application.

An alternative would be to tell the function how to interpret one’s own
point structure:

void SDL_RenderLines(int npoints, void* points, int struct_size, int
x_offset, int y_offset);

…
SDL_RenderLines(x, points, sizeof(points[0]), (char*)&points[0].x -
(char*)&points[0], (char*)&points[0].y - (char*)&points[0]);
…

But that way one would still have to use the same data type for x and y
as used internally by SDL_RenderLines unless there are different
functions that accept different data types for them, a la OpenGL.

–
//David Olofson - Developer, Artist, Open Source Advocate

.— Games, examples, libraries, scripting, sound, music, graphics —.
| http://olofson.net http://kobodeluxe.com http://audiality.org |
| http://eel.olofson.net http://zeespace.net http://reologica.se |
’---------------------------------------------------------------------’

8

David Olofson wrote:> On Tuesday 08 December 2009, at 23.40.37, Andre de Leiradella wrote:

David Olofson wrote:

So, I think a single array of structs should be a perfectly fine
alternative from this POV. It’s just that it adds another datatype to the
API, and it still requires shoehorning to fit the design of any real
application.

An alternative would be to tell the function how to interpret one’s own
point structure:

void SDL_RenderLines(int npoints, void* points, int struct_size, int
x_offset, int y_offset);

…
SDL_RenderLines(x, points, sizeof(points[0]), (char*)&points[0].x -
(char*)&points[0], (char*)&points[0].y - (char*)&points[0]);
…

But that way one would still have to use the same data type for x and y
as used internally by SDL_RenderLines unless there are different
functions that accept different data types for them, a la OpenGL.

I was thinking about a similar approach; passing an array of pointers to
elements physically equivalent to struct { int x; int y; }, but I don’t think
there’s any point in anything like this.

Pointers are (at least) as large as integers, so the only case where you’d
gain anything is with the “one pointer per x/y struct” I suggested, and this
is only on 32 bit platforms. (64 bit platforms generally have 64 bit
pointers…) Even then, the pointer indirections will most likely eat anything
you gain by not copying, and then some.

Oh, and let’s not talk about all the ways you can get anything like this wrong
and get garbage data, segfaults and whatnot… :smiley:

So, just copy the values instead! It’s simpler, faster and safer. :slight_smile:

There’s no difference between my approach and passing a pointer to an
array of points regarding memory access; both will have to read two
values from an offset to the beginning of the structure for each point.
And not having to copy values around is faster than having to.

But you’re right, things should be simpler and safer, and having the
user use the same data type as used internally by the function kind of
defeats the purpose.

Maybe having it implemented with ints for the coordinates and a simpler,
safer function which takes SDL_Points and passes it to the other? I
think ints would cover most other libraries and you get the speed
benefit of not copying values around.

Cheers,

Andre

9

[…]

So, just copy the values instead! It’s simpler, faster and safer. :slight_smile:

There’s no difference between my approach and passing a pointer to an
array of points regarding memory access; both will have to read two
values from an offset to the beginning of the structure for each point.

Right. I think I misunderstood your example the first time around. What you’re
actually doing is pass two pointers to “item 0”, and a stride for indexing?

The overhead of the stride calculations (two adds per point) would impact
either the caller or the callie anyway, so there’s not really a way to avoid
that in the general case anyway.

And not having to copy values around is faster than having to.

Sure, but I was still thinking “array of pointers”, which is a different
matter. :slight_smile:

But you’re right, things should be simpler and safer, and having the
user use the same data type as used internally by the function kind of
defeats the purpose.

Yes… And as always, one has to consider the 70/30 (or 90/10 or whatever)
rule, and consider how much overhead there is in relation to actual work
performed. Function calls, potentially chaining through multiple API layers,
are very expensive when we’re dealing with single pixel operations and the
like, and compared to that, any of the proposed “npoints” approaches would be
a massive improvement.

Maybe having it implemented with ints for the coordinates and a simpler,
safer function which takes SDL_Points and passes it to the other? I
think ints would cover most other libraries and you get the speed
benefit of not copying values around.

Not sure… I kind of prefer APIs that provide one single interface that is as
simple, clean, safe and flexible as possible. Alternative interfaces have to
be really nice and useful to be motivated, because they are add to the size of
the API that you have to learn and understand.

That said, sometimes one has to make exceptions to avoid substantial
performance issues, and I’d say the npoints deal (as opposed to one API call
per line) isi n that category.

I’m not so sure the way you pass the actual coordinates matter enough that one
can defend providing multiple variants. Maybe it does for pixels on software
surfaces, but lines over OpenGL or Direct3D…?On Wednesday 09 December 2009, at 00.00.29, Andre de Leiradella wrote:

–
//David Olofson - Developer, Artist, Open Source Advocate

.— Games, examples, libraries, scripting, sound, music, graphics —.
| http://olofson.net http://kobodeluxe.com http://audiality.org |
| http://eel.olofson.net http://zeespace.net http://reologica.se |
’---------------------------------------------------------------------’

10

(An odd number for ‘npoints’ to SDL_RenderLines() would be an error.)

Why? What if I want to draw a triangle, or a pentagon? :frowning:

11

David Olofson wrote:

Right. I think I misunderstood your example the first time around. What you’re
actually doing is pass two pointers to “item 0”, and a stride for indexing?

Yup.

The overhead of the stride calculations (two adds per point) would impact
either the caller or the callie anyway, so there’s not really a way to avoid
that in the general case anyway.

That’s correct. But it would be faster than copying bytes around, not to
count allocation overhead if a temporary array has to be allocated on
the heap.

Oh well, I’m here just for the kicks :slight_smile: Of course a simple API is
preferable.

I’m not so sure the way you pass the actual coordinates matter enough that one
can defend providing multiple variants. Maybe it does for pixels on software
surfaces, but lines over OpenGL or Direct3D…?

The problem is, suppose SDL_RenderLines expects coordinates as int32_t.
Now suppose I’ve just received an array of points I must render as
lines. In this array, coordinates are uint16_t. If I pass the array as a
void* along with the strides, SDL_RenderLines will try to cast the void
pointer to uint32_t* plus the stride and deference the pointer, getting
wrong values for the coordinate.

Cheers,

Andre

12

Then you’d use the *LineStrip() or *Polygon() variant, which is for "chained"
lines. The *Lines() variant is for individual lines, each one with four
parameters; start (x, y) and end (x, y).On Thursday 10 December 2009, at 02.24.48, “nfries88” wrote:

(An odd number for ‘npoints’ to SDL_RenderLines() would be an error.)

Why? What if I want to draw a triangle, or a pentagon? :frowning:

–
//David Olofson - Developer, Artist, Open Source Advocate

.— Games, examples, libraries, scripting, sound, music, graphics —.
| http://olofson.net http://kobodeluxe.com http://audiality.org |
| http://eel.olofson.net http://zeespace.net http://reologica.se |
’---------------------------------------------------------------------’

13

David Olofson wrote:
[…]

I’m not so sure the way you pass the actual coordinates matter enough
that one can defend providing multiple variants. Maybe it does for pixels
on software surfaces, but lines over OpenGL or Direct3D…?

The problem is, suppose SDL_RenderLines expects coordinates as int32_t.
Now suppose I’ve just received an array of points I must render as
lines. In this array, coordinates are uint16_t. If I pass the array as a
void* along with the strides, SDL_RenderLines will try to cast the void
pointer to uint32_t* plus the stride and deference the pointer, getting
wrong values for the coordinate.

Yes, but considering APIs of this type, one also has to consider where those
arrays of coordinates would come from.

In some cases (such as pixel formats), it might make sense to support multiple
formats in the API, but unless these formats provide significant advantages
(memory/bandwidth, compatibility with other popular APIs, making application
code implementation simpler etc), I think it’s better if one can find a single
"one size fits all" format.

For example, most relevant APIs for professional audio these days support only
one sample format: 32 bit float. That provides sufficient accuracy and dynamic
range for “anything” (short of internal accumulators in some DSP algorithms -
but that has no bearing on the API), and since floating point math is the only
sensible choice for audio DSP on workstations these days anyway, integer
formats would just add significant conversion overhead, dynamic range issues
and API and implementation complexity.

Anyway, the bottom line is that supporting multiple formats, multiple
interfaces etc, multiplies complexity and code size, so it has to be properly
motivated.On Thursday 10 December 2009, at 02.43.09, Andre de Leiradella wrote:

–
//David Olofson - Developer, Artist, Open Source Advocate

.— Games, examples, libraries, scripting, sound, music, graphics —.
| http://olofson.net http://kobodeluxe.com http://audiality.org |
| http://eel.olofson.net http://zeespace.net http://reologica.se |
’---------------------------------------------------------------------’

14

There are a couple of things that have not been mentioned in this
discussion so far, so I’ll mention them.

First off, over time programmers tend to bend their designs to fit the
APIs. If all you have are functions that take argument lists like (int
npoint, int *x, int *y) you start storing your point data that way.
Sure, adapting old code to the new API is a pain, but your next
project won’t have that problem because you will design to fit the
API.

I also dislike that style of API, but let’s face the fact that it is
dead simple to write code to call every graphics API I’ve ever seen to
get the work done if I start with values in the form (int npoint, int
*x, int *y).

The other thing we don’t think about is what goes on behind the scenes
of an API like

begin(LINE_STRIP);
vertex2i(int x, int y);
…
end();

That kind of interface implies buffering which implies hidden state.
A good software renderer has to count vertex2 calls and fire the line
drawer after every second call. If you are doing a LINE_STRIP you have
to save the next to last vertex. If you are doing a POLYGON you have
to save the first vertex so you can finish the polygon and you have to
save the previous vertex so you can draw a line segment when you get
the next vertex. A poor software renderer will just wait until it sees
the end() and then do the work which means it has to dynamically
allocate storage for all the data and then free it.

Then there is the little problem of clipping. Keeping clipping state
around, and getting it right, between vertex calls is a fun project.
Try it some time. On the other hand, working from nice precomposed
vectors of the vertex data isn’t so bad.

On the other hand, if you are passing the data to a hardware renderer
or over a network you have to buffer enough of the data to make the
transfer efficient. Having the data as (int npoint, int *x, int *y)
doesn’t help that much, but it doesn’t hurt either.

All that may seem more like philosophy than serious technical
problems, and it most is.

If you really want to look at a software renderer and see what goes on
inside it I recommend you take a look AT VOGLE. VOGLE is public domain
(although VOGL is not, not the E) and seems to still be available at
http://bund.com.au/~dgh/eric/

Bob Pendleton–
±----------------------------------------------------------

15

FYI, at least for now I opted to keep the semantic that both endpoints
will be included in the line, and in a single call to
SDL_RenderLines() each pixel is only drawn once (not actually true in
the software renderer FIXME).

This was easier than telling people that in certain cases one of the
endpoints will be missing, and oh BTW, which one is missing is
environment dependent. :slight_smile:

Also, I created an SDL_Point structure to facilitate this. It should
map fairly well to most common point structures, it’s just a pair of
ints for x and y. (Of course Windows uses long and X11 uses short,
but whatever)

Thank you everyone, for your feedback!On Fri, Dec 11, 2009 at 7:14 AM, Bob Pendleton wrote:

There are a couple of things that have not been mentioned in this
discussion so far, so I’ll mention them.

First off, over time programmers tend to bend their designs to fit the
APIs. If all you have are functions that take argument lists like (int
npoint, int *x, int *y) you start storing your point data that way.
Sure, adapting old code to the new API is a pain, but your next
project won’t have that problem because you will design to fit the
API.

I also dislike that style of API, but let’s face the fact that it is
dead simple to write code to call every graphics API I’ve ever seen to
get the work done if I start with values in the form ?(int npoint, int
*x, int *y).

The other thing we don’t think about is what goes on behind the scenes
of an API like

begin(LINE_STRIP);
vertex2i(int x, int y);
…
end();

That kind of interface implies buffering which implies hidden state.
A good software renderer has to count vertex2 calls and fire the line
drawer after every second call. If you are doing a LINE_STRIP you have
to save the next to last vertex. If you are doing a POLYGON you have
to save the first vertex so you can finish the polygon and you have to
save the previous vertex so you can draw a line segment when you get
the next vertex. A poor software renderer will just wait until it sees
the end() and then do the work which means it has to dynamically
allocate storage for all the data and then free it.

Then there is the little problem of clipping. Keeping clipping state
around, and getting it right, between vertex calls is a fun project.
Try it some time. On the other hand, working from nice precomposed
vectors of the vertex data isn’t so bad.

On the other hand, if you are passing the data to a hardware renderer
or over a network you have to buffer enough of the data to make the
transfer efficient. Having the data as (int npoint, int *x, int *y)
doesn’t help that much, but it doesn’t hurt either.

All that may seem more like philosophy than serious technical
problems, and it most is.

If you really want to look at a software renderer and see what goes on
inside it I recommend you take a look AT VOGLE. VOGLE is public domain
(although VOGL is not, not the E) and seems to still be available at
http://bund.com.au/~dgh/eric/

Bob Pendleton

–
±----------------------------------------------------------

SDL mailing list
SDL at lists.libsdl.org
http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

–
-Sam Lantinga, Founder and President, Galaxy Gameworks LLC

16

nfries88, you can still draw an odd number of lines, but the proposal
that an odd ‘npoints’ argument should be an error is meant to reflect
the proposal that SDL_RenderLines() render possibly unconnected lines.
Each line requires two points, so the number of points will always be
even. The other proposed APIs are for definitely connected lines, and
thus only require n or n+1 lines for connected and closed shapes
(polygon) or for connected and open shapes (a jaggedy line?)
respectively.On Thu, Dec 10, 2009 at 8:09 AM, David Olofson wrote:

On Thursday 10 December 2009, at 02.24.48, “nfries88” wrote:

(An odd number for ‘npoints’ to SDL_RenderLines() would be an error.)

Why? What if I want to draw a triangle, or a pentagon? :frowning:

Then you’d use the *LineStrip() or *Polygon() variant, which is for "chained"
lines. The *Lines() variant is for individual lines, each one with four
parameters; start (x, y) and end (x, y).

–
http://codebad.com/

17

err, “n or n+1 lines” is meant to be "n or n+1 points"On Fri, Dec 11, 2009 at 2:55 PM, Donny Viszneki <@Donny_Viszneki> wrote:

even. The other proposed APIs are for definitely connected lines, and
thus only require n or n+1 lines for connected and closed shapes

–
http://codebad.com/