Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


how to draw a circle with 'Bresenham'


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

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

#1 tcige   Members   -  Reputation: 206

Like
0Likes
Like

Posted 26 April 2013 - 04:30 AM

first i use D3DFVF_XYZRHW, the effect is ok with D3DPT_POINTLIST, but i do not know how to arrange the vertex to draw the solid circle with D3DPT_TRIANGLELIST

 

then i move to D3DFVF_XYZ, i have to change the parameter of D3DXMatrixLookAtLH to suit the radius, but the drawing effect is awful



Sponsor:

#2 belfegor   Crossbones+   -  Reputation: 2715

Like
1Likes
Like

Posted 26 April 2013 - 05:57 AM

Why not with triangle fan?

 

 

D3DXVECTOR2* D3DXVec2Rotate(D3DXVECTOR2* vOut, D3DXVECTOR2* vIn, float rad, const D3DXVECTOR2* vCenter)
{
    float cr = std::cos(rad);
    float sr = std::sin(rad);

    float X = vIn->x;
    float Y = vIn->y;

    X -= vCenter->x;
    Y -= vCenter->y;

    vOut->x = X * cr - Y * sr;
    vOut->y = X * sr + Y * cr;

    vOut->x += vCenter->x;
    vOut->y += vCenter->y;

    return vOut;
}
 
...
struct VERTEX
    {
        D3DXVECTOR4 p;
    };

    static const std::size_t numPts = 20; // points cnt on circle
    std::vector<VERTEX> vVertices;
    d3d9device->SetFVF(D3DFVF_XYZRHW); // pre-tranformed vertex
    VERTEX center; // vertex in center of circle
    center.p = D3DXVECTOR4(500.0f, 400.0f, 0.0f, 1.0f); // set circle center on screen center (1000x800) / 2
    D3DXVECTOR2 ct(center.p.x, center.p.y);
    vVertices.push_back(center); // add center first beause of triangle fan "rule"
    static const float rad = 200.0f; // circle radius
    for(std::size_t i = 0; i < numPts; ++i)
    {
        float ang = (D3DX_PI * 2.0f) * ((float)i / (float)numPts);
        D3DXVECTOR2 pt(center.p.x + rad, center.p.y + rad);
        D3DXVec2Rotate(&pt, &pt, ang, &ct);
        VERTEX vert;
        vert.p = D3DXVECTOR4(pt.x, pt.y, 0.0f, 1.0f);
        vVertices.push_back(vert);
    }
    vVertices.push_back(vVertices[1]); // add first point (on circle) to close
    d3d9device->DrawPrimitiveUP( D3DPT_TRIANGLEFAN, numPts, &vVertices[0], sizeof(VERTEX) );

Edited by belfegor, 26 April 2013 - 06:00 AM.


#3 tcige   Members   -  Reputation: 206

Like
0Likes
Like

Posted 26 April 2013 - 06:10 AM

sinf and cosf is too slow



#4 kauna   Crossbones+   -  Reputation: 2832

Like
1Likes
Like

Posted 26 April 2013 - 06:12 AM


Check this thread: 

 

http://www.gamedev.net/topic/259860-drawing-circle-in-directx/

 

Maybe the source code does what you are looking for.

 

[edit] How many thousand / million circles you are planning to draw in order to be bottle necked by sin/cos ??? I'd say that sin&cos isn't the biggest problem here. Especially if you pre-create your geometry, the sin&cos won't have any effect while drawing.

 

Cheers!


Edited by kauna, 26 April 2013 - 06:15 AM.


#5 belfegor   Crossbones+   -  Reputation: 2715

Like
0Likes
Like

Posted 26 April 2013 - 06:20 AM

+1 What kauna said.

 

Alternative fast sin/cos

 

float fast_sin(float rad)
{
    static const float B = 4 / D3DX_PI;
    static const float C = -4 / (D3DX_PI * D3DX_PI);

    float y = B * rad + C * rad * std::abs(rad);
    return y;
}

float fast_cos(float rad)
{
    static const float B = 4 / D3DX_PI;
    static const float C = -4 / (D3DX_PI * D3DX_PI);

    rad += 1.57079632f;
    float y = B * rad + C * rad * std::abs(rad);
    return y;
}

 

http://devmaster.net/forums/topic/4648-fast-and-accurate-sinecosine/

 

My code above is just an example, you could precalculate most stuff at init time, no need to do that every frame.


Edited by belfegor, 26 April 2013 - 06:24 AM.


#6 tcige   Members   -  Reputation: 206

Like
0Likes
Like

Posted 26 April 2013 - 06:20 AM

i want to use Bresenham and D3DFVF_XYZ and D3DFILL_WIREFRAME, but no idea



#7 kauna   Crossbones+   -  Reputation: 2832

Like
0Likes
Like

Posted 26 April 2013 - 06:24 AM

Why not draw a line list then? You don't need to draw triangles in wireframe to get lines.

 

Cheers!



#8 tcige   Members   -  Reputation: 206

Like
0Likes
Like

Posted 26 April 2013 - 06:35 AM

wireframe is an example

 

using Bresenham, the vertex is out of order, i have no idea how to arrange the vertex

 

using cosf and sinf according to the angle is simple, but not effecitve



#9 kauna   Crossbones+   -  Reputation: 2832

Like
1Likes
Like

Posted 26 April 2013 - 06:47 AM

What is the thing with Bresenham's algorithm? Can you make a drawing for us what you want to accomplish?

 

You want to draw a circle using points? That's highly inefficient (even more inefficient than using sin and cos btw). 

 

Have you made some performance analysis which point out that sin and cos are your problem?

 

Best regards!



#10 tcige   Members   -  Reputation: 206

Like
0Likes
Like

Posted 26 April 2013 - 06:59 AM

that algorithm is simple, and it works fine with D3DFVF_XYZRHW and D3DPT_POINTLIST

 

i want to apply it to D3DFVF_XYZ and solid circle



#11 kauna   Crossbones+   -  Reputation: 2832

Like
0Likes
Like

Posted 26 April 2013 - 07:29 AM

So do I understand you correctly that you want to draw a filled shape (circle in this case) and use Bresenham's algorithm (which is used mostly for drawing circle contour) ?

 

The difference between D3DFVF_XYZRHW and D3DFVF_XYZ is that the RHW version skips vertex shader / projection part ie. it assumes that the data is already transformed. D3DFVF_XYZ doesn't skip transformation and projection so you'll need to provide a correct world, view and projection matrix in order to draw correctly.

 

If you are drawing 2d shapes on the screen then the RHW version should do the trick. However, you may accomplish the same with D3DFVD_XYZ but you'll need correct matrices for it to work correctly. Do you need to draw circles in 3d space?

 

Cheers!



#12 tcige   Members   -  Reputation: 206

Like
0Likes
Like

Posted 26 April 2013 - 07:41 AM

So do I understand you correctly that you want to draw a filled shape (circle in this case) and use Bresenham's algorithm (which is used mostly for drawing circle contour) ?

 

The difference between D3DFVF_XYZRHW and D3DFVF_XYZ is that the RHW version skips vertex shader / projection part ie. it assumes that the data is already transformed. D3DFVF_XYZ doesn't skip transformation and projection so you'll need to provide a correct world, view and projection matrix in order to draw correctly.

 

If you are drawing 2d shapes on the screen then the RHW version should do the trick. However, you may accomplish the same with D3DFVD_XYZ but you'll need correct matrices for it to work correctly. Do you need to draw circles in 3d space?

 

Cheers!

 

 

yeah, that's what i mean, in 3d space

 

even i increase the radius and adjust the parameter of D3DXMatrixLookAtLH to suit the radius, the effect is awful



#13 tcige   Members   -  Reputation: 206

Like
0Likes
Like

Posted 26 April 2013 - 08:00 AM

+1 What kauna said.

 

Alternative fast sin/cos

 

float fast_sin(float rad)
{
    static const float B = 4 / D3DX_PI;
    static const float C = -4 / (D3DX_PI * D3DX_PI);

    float y = B * rad + C * rad * std::abs(rad);
    return y;
}

float fast_cos(float rad)
{
    static const float B = 4 / D3DX_PI;
    static const float C = -4 / (D3DX_PI * D3DX_PI);

    rad += 1.57079632f;
    float y = B * rad + C * rad * std::abs(rad);
    return y;
}

 

http://devmaster.net/forums/topic/4648-fast-and-accurate-sinecosine/

 

My code above is just an example, you could precalculate most stuff at init time, no need to do that every frame.

 

 

is this fast cos/sin authoritative and cos/sin acceptable in reality?



#14 belfegor   Crossbones+   -  Reputation: 2715

Like
0Likes
Like

Posted 26 April 2013 - 08:06 AM

I am using it for my particle system, for me visually there is no noticeable difference between these and standard sin/cos. Why not try and see?


Edited by belfegor, 26 April 2013 - 08:07 AM.


#15 tcige   Members   -  Reputation: 206

Like
0Likes
Like

Posted 26 April 2013 - 08:13 AM

I am using it for my particle system, for me visually there is no noticeable difference between these and standard sin/cos. Why not try and see?

 

thanks, i will try and this remind me of the 'hacker's delight'

 

then what about Bresenham, can it be used in D3DFVF_XYZ


Edited by tcige, 26 April 2013 - 08:21 AM.


#16 belfegor   Crossbones+   -  Reputation: 2715

Like
0Likes
Like

Posted 26 April 2013 - 08:43 AM

Note for these function to work properly you must wrap your rad parameter -PI - PI



#17 kauna   Crossbones+   -  Reputation: 2832

Like
1Likes
Like

Posted 26 April 2013 - 08:55 AM

then what about Bresenham, can it be used in D3DFVF_XYZ

 

I don't think so. The Bresenham's circle algorithm is suitable to drawing a circles in 2d. It was developed when drawing single pixels to the screen was the slowest thing ever... that's like some decades ago. 

 

Just create a mesh using the given functions (as smooth as required) and I can guarantee that the sin and cos functions aren't the performance bottle neck. If you store the geometry inside a vertex buffer, it'll be enough to create the mesh once at the start up.

 

Give some screenshots to show what you want and what you have accomplished. It is really difficult to read people's mind you know. 

 

Cheers!


Edited by kauna, 26 April 2013 - 08:55 AM.


#18 tcige   Members   -  Reputation: 206

Like
0Likes
Like

Posted 26 April 2013 - 09:41 AM

then what about Bresenham, can it be used in D3DFVF_XYZ

 

I don't think so. The Bresenham's circle algorithm is suitable to drawing a circles in 2d. It was developed when drawing single pixels to the screen was the slowest thing ever... that's like some decades ago. 

 

Just create a mesh using the given functions (as smooth as required) and I can guarantee that the sin and cos functions aren't the performance bottle neck. If you store the geometry inside a vertex buffer, it'll be enough to create the mesh once at the start up.

 

Give some screenshots to show what you want and what you have accomplished. It is really difficult to read people's mind you know. 

 

Cheers!

 

thanks a lot

 

i'm new to directx, and someone says cosf/sinf's efficiency is much slower than Bresenham

 

finally i find difficult to apply it to 3d, and i'll be glad to use cosf/sinf because it needs only a few lines






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS