Skip to main content

Optimizing concentric arcs

19 replies [Last post]
ser207
Offline
Joined: 2008-08-11

In an animation component that I am writing I have to draw colored concentric arcs. In each frame I draw a new outer arc, and the inner arc is what in the previous frame was the outer one and so on. (To help you understand, if I was drawing straight lines, instead of arcs, this would give a waterfall effect).

In the attached program, I am drawing as many concentric arcs so as to complete a circle.

The problem is that with each successive frame the rendering time increases to such an extent that this algorithm is unusable. Is there any way to improve the performance without reducing the diameter of the whole circle (1000px) and/or the angle of each segment (1 degree). (Note that if the segment angle is 90 degrees the performance is pretty bad too.)

If I were drawing lines instead of arcs the optimisation is easy, I’d just copy the previous image down one pixel and then paint the new top line. But with arcs I’m have to issue a drawArc() for every arc that has to appear.

I hope that somebody has some idea on how to optimize this.

<br />
package waterfall;</p>
<p>import java.awt.Color;<br />
import java.awt.Graphics;<br />
import java.awt.Graphics2D;<br />
import java.awt.event.ActionEvent;<br />
import java.awt.event.ActionListener;<br />
import java.awt.geom.Arc2D;<br />
import java.util.Iterator;<br />
import java.util.LinkedList;<br />
import java.util.Random;</p>
<p>public class WaterfallArc01 extends javax.swing.JPanel {</p>
<p>    private final int diameter = 1000; // pixels<br />
    private final int sectorExtent = 1;  // degree;<br />
    private final int numberSectors = 360/sectorExtent;<br />
    Random seed = new Random();</p>
<p>    LinkedList list = new LinkedList();</p>
<p>    public WaterfallArc01() {<br />
        ActionListener taskPerformer = new ActionListener()<br />
        {<br />
            public void actionPerformed(ActionEvent evt)<br />
            {<br />
                generateNewData();<br />
                repaint();<br />
            }<br />
        };<br />
        javax.swing.Timer t = new javax.swing.Timer(500, taskPerformer);<br />
        t.start();<br />
    }</p>
<p>    private void generateNewData()<br />
    {<br />
        Color[] sectors = new Color[numberSectors];</p>
<p>        for(int i=0; idiameter/2)<br />
        {<br />
            list.removeFirst();<br />
        }<br />
    }</p>
<p>    private Color getColor()<br />
    {<br />
        return new Color(seed.nextInt(0x1000000));<br />
    }</p>
<p>    @Override<br />
    protected void paintComponent(Graphics g)<br />
    {<br />
        render(g);<br />
    }</p>
<p>    private void render(Graphics g)<br />
    {<br />
        Graphics2D g2d = (Graphics2D)g;    </p>
<p>        long startTime = System.nanoTime();<br />
        int size = diameter;<br />
        int x=0;<br />
        int y = x;<br />
        double startAngle=0;<br />
        double oldX=x;</p>
<p>        // Erase background to white<br />
        g2d.setColor(Color.BLACK);<br />
        g2d.fillRect(0, 0, diameter, diameter);</p>
<p>        Color[] sectors;<br />
        Iterator it = list.descendingIterator();<br />
        while(it.hasNext())  // each update<br />
        {<br />
            sectors = it.next();</p>
<p>            for(int i=0; i< sectors.length; i++)  // all sectors<br />
            {<br />
                g2d.setColor(sectors[i]);<br />
                g2d.draw(new Arc2D.Double(x, y, size, size, startAngle,<br />
                    sectorExtent, Arc2D.OPEN));<br />
                startAngle += sectorExtent;<br />
            }<br />
            oldX = x;<br />
            do{<br />
                size = size - 1;<br />
                x = (diameter - size)/2;<br />
            } while(x == oldX);<br />
            y = x;<br />
            startAngle=0d;<br />
        }</p>
<p>        long estimatedTime = System.nanoTime() - startTime;<br />
        System.out.println(list.size()+" lines, render time: "+(double)estimatedTime/1e9);<br />
    }</p>
<p>}</p>
<p>---------------------------------------------------------------------------------------------------------------------------</p>
<p>package waterfall;</p>
<p>import java.awt.BorderLayout;</p>
<p>public class TestWaterfallArc01 extends javax.swing.JFrame {</p>
<p>    public TestWaterfallArc01() {<br />
        setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);<br />
        setMinimumSize(new java.awt.Dimension(1000, 1000));</p>
<p>        WaterfallArc01 waterfallArc011 = new WaterfallArc01();<br />
        getContentPane().setLayout( new BorderLayout());<br />
        add(waterfallArc011, BorderLayout.CENTER);<br />
        pack();<br />
    }</p>
<p>    public static void main(String args[]) {<br />
        java.awt.EventQueue.invokeLater(new Runnable() {<br />
            public void run() {<br />
                new TestWaterfallArc01().setVisible(true);<br />
            }<br />
        });<br />
    }<br />
}</p>
<p>

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
ser207
Offline
Joined: 2008-08-11

> A better optimized solution would be to look up for
> the right color in setRGB depending on the angle of
> the currently drawn pixel - this way you draw the
> circle only once, altering the color is bascially
> free :)
>

I modified the setRGB() method of your program as follows to get my optimized coloured concentrics arcs.

Is there an alternate, faster way to do the maths?

Thanks very much Ig for you input.
[code]
void setRGB(int x, int y, Color[] colors)
{
double angleInRadians = Math.atan2(y-cy, x-cx);
double angle = angleInRadians < 0 ? Math.toDegrees(angleInRadians + (2*Math.PI)) : Math.toDegrees(angleInRadians);
angle = Math.round(angle);
angle = angle == 360 ? 0 : angle;

int rgb = colors[(int)angle].getRGB();

int index = y * bimg.getWidth() + x;
if (index < data.length)
{
data[index] = rgb;
}
}
[/code]

Note. cx=500 and cy=500.

Message was edited by: ser207

linuxhippy
Offline
Joined: 2004-01-07

> Is there an alternate, faster way to do the maths?
The problem here is Math.round and Math.atan2, the Math class is optimized for high precission but often sacrifices speed.

Your original version took 205ms on my C2D, replacing atan2 with this unprecise version and removing the round braught it down to 35ms.
Be sure to use the server-runtime if possible, it gave me a solid 40% speed boost :)

[code]
private final double aTan2(double y, double x) {
double coeff_1 = Math.PI / 4d;
double coeff_2 = 3d * coeff_1;
double abs_y = Math.abs(y);
double angle;
if (x >= 0d) {
double r = (x - abs_y) / (x + abs_y);
angle = coeff_1 - coeff_1 * r;
} else {
double r = (x + abs_y) / (abs_y - x);
angle = coeff_2 - coeff_1 * r;
}
return y < 0d ? -angle : angle;
}
[/code]

However that method seems to be very unprecise, a slightly better looking result can be archived using this lookup-table based implementation, however its slower (45ms):
[code]
package waterfall;

public class TableMath
{
private static final int TABLE_SIZE = 10000;
static double[] atanTable = initAtanTable();

private static double[] initAtanTable()
{
double[] table = new double[TABLE_SIZE];

for(int i=0; i < TABLE_SIZE; i++)
{
table[i] = Math.atan(((double)i) / TABLE_SIZE);
}

return table;
}

private static double atan_1(int y,int x)
{
int index;
int vorz;
double erg = 0;

vorz = 1;
if (((x < 0) && (y < 0)) || ((x > 0) && (y > 0))) {vorz = 0;}
else x = -x;

/*atan of y/x */
index =(int) (((y*(TABLE_SIZE-1)*10)/x+5)/10); //+5 for rounding

erg = atanTable[index];

if (vorz == 0 ) return erg;
else return -erg;
}

public static double atan2(int y, int x) {
double result;

if(Math.abs(x) > Math.abs(y))
result = atan_1(y,x);
else
{
result = atan_1(x,y);
if(result < 0)
result = -Math.PI/2 - result;
else
result = Math.PI/2 - result;
}

if (x < 0)
if(y < 0)
result = result - Math.PI;
else
result = result + Math.PI;

return result;
}
}
[/code]

I don't know if any of those two implementations fit your needs, but they are definitily faster ;)

Another possible optimization would be multi-threading, so each thread could do a part of the total work - should be perfectly paralizeable. I am not sure if unsynchronized write-access is valid (if no one is reading), but I guess it is. That would bring the fastest version down to 20ms on my machine :)

lg Clemens

Ken Warner

My panorama viewers use a lot of the Math methods.
They are really slow and not all that precise.

http://pancyl.com/SittingRoom.htm

The trig functions are inaccurate near a multiple of
PI and zero. So much so that I have to check against
an Epsilon value and if the absolute returned value is
less than Epsilon then I manually set the value I need.

I also had to develop -- with some help -- an approximation
calculation for atan2() and I use a lookup table for asin().

I've found that lookup tables are not all that great near
a multiple of PI especially if you are trying to use a look
up table for tan/atan. They change very fast near their
asymptote. I use lookup tables "in the middle" but revert
to the real method near the poles with an Epsilon check.

I've wanted to gripe about the slowness and inaccuracy of
the Math package but who do I talk to?

java2d@JAVADESKTOP.ORG wrote:
>>Is there an alternate, faster way to do the maths?
>
> The problem here is Math.round and Math.atan2, the Math class is optimized for high precission but often sacrifices speed.
>
> Your original version took 205ms on my C2D, replacing atan2 with this unprecise version and removing the round braught it down to 35ms.
> Be sure to use the server-runtime if possible, it gave me a solid 40% speed boost :)
>
> [code]
> private final double aTan2(double y, double x) {
> double coeff_1 = Math.PI / 4d;
> double coeff_2 = 3d * coeff_1;
> double abs_y = Math.abs(y);
> double angle;
> if (x >= 0d) {
> double r = (x - abs_y) / (x + abs_y);
> angle = coeff_1 - coeff_1 * r;
> } else {
> double r = (x + abs_y) / (abs_y - x);
> angle = coeff_2 - coeff_1 * r;
> }
> return y < 0d ? -angle : angle;
> }
> [/code]
>
> However that method seems to be very unprecise, a slightly better looking result can be archived using this lookup-table based implementation, however its slower (45ms):
> [code]
> package waterfall;
>
> public class TableMath
> {
> private static final int TABLE_SIZE = 10000;
> static double[] atanTable = initAtanTable();
>
> private static double[] initAtanTable()
> {
> double[] table = new double[TABLE_SIZE];
>
> for(int i=0; i < TABLE_SIZE; i++)
> {
> table[i] = Math.atan(((double)i) / TABLE_SIZE);
> }
>
> return table;
> }
>
> private static double atan_1(int y,int x)
> {
> int index;
> int vorz;
> double erg = 0;
>
> vorz = 1;
> if (((x < 0) && (y < 0)) || ((x > 0) && (y > 0))) {vorz = 0;}
> else x = -x;
>
>
> /*atan of y/x */
> index =(int) (((y*(TABLE_SIZE-1)*10)/x+5)/10); //+5 for rounding
>
> erg = atanTable[index];
>
> if (vorz == 0 ) return erg;
> else return -erg;
> }
>
> public static double atan2(int y, int x) {
> double result;
>
> if(Math.abs(x) > Math.abs(y))
> result = atan_1(y,x);
> else
> {
> result = atan_1(x,y);
> if(result < 0)
> result = -Math.PI/2 - result;
> else
> result = Math.PI/2 - result;
> }
>
> if (x < 0)
> if(y < 0)
> result = result - Math.PI;
> else
> result = result + Math.PI;
>
> return result;
> }
> }
> [/code]
>
> I don't know if any of those two implementations fit your needs, but they are definitily faster ;)
>
> Another possible optimization would be multi-threading, so each thread could do a part of the total work - should be perfectly paralizeable. I am not sure if unsynchronized write-access is valid (if no one is reading), but I guess it is. That would bring the fastest version down to 20ms on my machine :)
>
> lg Clemens
> [Message sent by forum member 'linuxhippy' (linuxhippy)]
>
> http://forums.java.net/jive/thread.jspa?messageID=301636
>
> ===========================================================================
> To unsubscribe, send email to listserv@java.sun.com and include in the body
> of the message "signoff JAVA2D-INTEREST". For general help, send email to
> listserv@java.sun.com and include in the body of the message "help".
>

===========================================================================
To unsubscribe, send email to listserv@java.sun.com and include in the body
of the message "signoff JAVA2D-INTEREST". For general help, send email to
listserv@java.sun.com and include in the body of the message "help".

linuxhippy
Offline
Joined: 2004-01-07

> I've wanted to gripe about the slowness and
> inaccuracy of
> the Math package but who do I talk to?

I totally agree. It would be great if the programmer could choose between the StrictMath implementation which is hard-wired now and maybe something like, call ist FastMath.
FastMath could be implemented without any guarantees, and really 1:1 instrified in hotspot to a corresponding CPU instruction if there is any, that would be really cool :)

lg Clemens

Ken Warner

YES! Why not FPU acceleration? That's what it's there for.

Er... is StrictMath already FPU accelerated? If it is then, oh well...

The current Math package is really not very good. Especially
for low level graphics stuff where 5 significant digits is
the minimum accuracy that is useful.

java2d@JAVADESKTOP.ORG wrote:
>>I've wanted to gripe about the slowness and
>>inaccuracy of
>>the Math package but who do I talk to?
>
>
> I totally agree. It would be great if the programmer could choose between the StrictMath implementation which is hard-wired now and maybe something like, call ist FastMath.
> FastMath could be implemented without any guarantees, and really 1:1 instrified in hotspot to a corresponding CPU instruction if there is any, that would be really cool :)
>
> lg Clemens
> [Message sent by forum member 'linuxhippy' (linuxhippy)]
>
> http://forums.java.net/jive/thread.jspa?messageID=301657
>
> ===========================================================================
> To unsubscribe, send email to listserv@java.sun.com and include in the body
> of the message "signoff JAVA2D-INTEREST". For general help, send email to
> listserv@java.sun.com and include in the body of the message "help".
>

===========================================================================
To unsubscribe, send email to listserv@java.sun.com and include in the body
of the message "signoff JAVA2D-INTEREST". For general help, send email to
listserv@java.sun.com and include in the body of the message "help".

linuxhippy
Offline
Joined: 2004-01-07

> Er... is StrictMath already FPU accelerated? If it
> is then, oh well...
Its as far accalerated as the FPU produces acceptable results.
For example on x86 the sin-command is used only in a special range where its known to be correct.

> The current Math package is really not very good.
> Especially
> or low level graphics stuff where 5 significant
> digits is
> the minimum accuracy that is useful.
Almost can't believe that its so inaccurat, they do a great amount of work to ensure that as far as I know.
After all, using straight FPU commands, accuracy won't be any better, at least on x86.

lg Clemens

Ken Warner

Like I said, "...oh well..."

Might just be my old machine that is giving
me inaccurate results from StrictMath. It's
an old PIII. But I can't get back 0 or 1
from the sin() method when I need them to be 0 or 1.

Also, what should be a straight integer multiply
using real numbers for the integer value frequently
returns a non integer result. I'll get back a number
like (and this is a fabricated example for clarity not
an actual calculation) 9.9999 when I should get 10.0.

Stuff like that and the trig() methods are really slow.
I use a 7'th degree Legrange polynomial multiplication for an
approximation of atan2() because it's faster than atan2().
That's not right...

java2d@JAVADESKTOP.ORG wrote:
>>Er... is StrictMath already FPU accelerated? If it
>>is then, oh well...
>
> Its as far accalerated as the FPU produces acceptable results.
> For example on x86 the sin-command is used only in a special range where its known to be correct.
>
>
>>The current Math package is really not very good.
>> Especially
>>or low level graphics stuff where 5 significant
>>digits is
>>the minimum accuracy that is useful.
>
> Almost can't believe that its so inaccurat, they do a great amount of work to ensure that as far as I know.
> After all, using straight FPU commands, accuracy won't be any better, at least on x86.
>
> lg Clemens
> [Message sent by forum member 'linuxhippy' (linuxhippy)]
>
> http://forums.java.net/jive/thread.jspa?messageID=301778
>
> ===========================================================================
> To unsubscribe, send email to listserv@java.sun.com and include in the body
> of the message "signoff JAVA2D-INTEREST". For general help, send email to
> listserv@java.sun.com and include in the body of the message "help".
>

===========================================================================
To unsubscribe, send email to listserv@java.sun.com and include in the body
of the message "signoff JAVA2D-INTEREST". For general help, send email to
listserv@java.sun.com and include in the body of the message "help".

Jim Graham

You could also use the RadialGradient in 1.6 - it renders conentric
rings of gradient colors fairly quickly. All you'd have to do between
frames is edit the stops and the colors for the stops.

...jim

java2d@JAVADESKTOP.ORG wrote:
>> Well, this seems really hard to optimize ... tons of
>> very small primitives.
>
> i've calculated that when i'm dealing with a full set of data, thats after 250 frames, i need to do 90,000 draw-Arc calls.
>
>
>> The only advice I can give you is to grab the Raster
>> of a INT_RGB buffered image:
>> byte[]
>> data=((DataBufferByte)tex.getRaster().getDataBuffer())
>> .getData() (in your case its an int[] of course),
>> and write code that does the drawing on the
>> pixel-array itself.
>>
>> It should be really fast to colour those few pixels
>> if you don't have to walk through a general
>> framework, but instead do exactly what you need and
>> that optimized.
>> The downside of course is quite a lot of hand-written
>> low-level code.
>>
>> lg Clemens
> [Message sent by forum member 'ser207' (ser207)]
>
> http://forums.java.net/jive/thread.jspa?messageID=301129
>
> ===========================================================================
> To unsubscribe, send email to listserv@java.sun.com and include in the body
> of the message "signoff JAVA2D-INTEREST". For general help, send email to
> listserv@java.sun.com and include in the body of the message "help".

===========================================================================
To unsubscribe, send email to listserv@java.sun.com and include in the body
of the message "signoff JAVA2D-INTEREST". For general help, send email to
listserv@java.sun.com and include in the body of the message "help".

ser207
Offline
Joined: 2008-08-11

> Well, this seems really hard to optimize ... tons of
> very small primitives.

i've calculated that when i'm dealing with a full set of data, thats after 250 frames, i need to do 90,000 draw-Arc calls.

> The only advice I can give you is to grab the Raster
> of a INT_RGB buffered image:
> byte[]
> data=((DataBufferByte)tex.getRaster().getDataBuffer())
> .getData() (in your case its an int[] of course),
> and write code that does the drawing on the
> pixel-array itself.
>
> It should be really fast to colour those few pixels
> if you don't have to walk through a general
> framework, but instead do exactly what you need and
> that optimized.
> The downside of course is quite a lot of hand-written
> low-level code.
>
> lg Clemens

Jim Graham

Are these 1-pixel wide arcs or wider?

Currently we have 2 different paths for drawArc. If we determine that
the stroke size is "less than or equal to a pixel" then we trace along
the arc and use a bresenham-like algorithm to touch the pixels. If it
is wider then we invoke a "line widening" algorithm which takes the
original arc path and computes a path which surrounds the pixels touched
for stroking it. This widening algorithm can take comparatively much
longer to run than a simple single pixel arc or a filled arc.

If you want to get a fast "ring" to draw, it would be better to create a
path which can be filled to draw it. You would draw CW for the outer
part of the ring, then draw a line towards the center, then draw another
arc CCW for th inner part of the ring and close the path. Calculating
and filling that path would go much faster than "draw"ing an arc with a
wide stroke.

The Arc2D class can generate bezier paths for arcs of arbitrary size,
but it always generates them in the same direction so it would be hard
to use it to do the above. Alternatively you can google for the math to
create bezier curves to draw an arc - the math is pretty simple - and
create your own GeneralPath manually.

Hope that helps...

...jim

java2d@JAVADESKTOP.ORG wrote:
>> Well, this seems really hard to optimize ... tons of
>> very small primitives.
>
> i've calculated that when i'm dealing with a full set of data, thats after 250 frames, i need to do 90,000 draw-Arc calls.
>
>
>> The only advice I can give you is to grab the Raster
>> of a INT_RGB buffered image:
>> byte[]
>> data=((DataBufferByte)tex.getRaster().getDataBuffer())
>> .getData() (in your case its an int[] of course),
>> and write code that does the drawing on the
>> pixel-array itself.
>>
>> It should be really fast to colour those few pixels
>> if you don't have to walk through a general
>> framework, but instead do exactly what you need and
>> that optimized.
>> The downside of course is quite a lot of hand-written
>> low-level code.
>>
>> lg Clemens
> [Message sent by forum member 'ser207' (ser207)]
>
> http://forums.java.net/jive/thread.jspa?messageID=301129
>
> ===========================================================================
> To unsubscribe, send email to listserv@java.sun.com and include in the body
> of the message "signoff JAVA2D-INTEREST". For general help, send email to
> listserv@java.sun.com and include in the body of the message "help".

===========================================================================
To unsubscribe, send email to listserv@java.sun.com and include in the body
of the message "signoff JAVA2D-INTEREST". For general help, send email to
listserv@java.sun.com and include in the body of the message "help".

ser207
Offline
Joined: 2008-08-11

I don't modify the Graphics2D default stroke value, so I assume that the arcs are 1 pixel wide.

Jim Graham

In other words each new arc is effectively "underneath" all of the
previous arcs?

You could use intermediate images for this.

Create 2 INT_ARGB images the size of your drawing (or the portion with
this waterfall-ish effect). On each frame you have "the one that holds
all of the previous arcs" and "the one that you will draw the new arcs
into". Then you simply do:

BufferedImage oldframe;
BufferedImage newframe;
...
loop {
Graphics2D g = newframe.createGraphics();
if (need to clear new frame) {
g.setComposite(AlphaComposite.Clear);
g.fillRect(0, 0, w, h);
g.setComposite(AlphaComposite.SrcOver);
}
g.setColor(...);
g.fillOval(...); /* or g.fill(Ellipse2D); */
g.drawImage(oldframe, 0, 0, null);
g.dispose();
... render newframe to destination ...
BufferedImage tmp = newframe;
newframe = oldframe;
oldframe = tmp;
}

If your arcs are all opaque and each one is bigger than all of the
previous ones then you don't need the "clear" part, but if drawing the
new arc on each frame doesn't obliterate all of the old stuff drawn
there, then you should clear it for good measure...

...jim

java2d@JAVADESKTOP.ORG wrote:
> In an animation component that I am writing I have to draw colored concentric arcs. In each frame I draw a new outer arc, and the inner arc is what in the previous frame was the outer one and so on. (To help you understand, if I was drawing straight lines, instead of arcs, this would give a waterfall effect).
>
> In the attached program, I am drawing as many concentric arcs so as to complete a circle.
>
> The problem is that with each successive frame the rendering time increases to such an extent that this algorithm is unusable. Is there any way to improve the performance without reducing the diameter of the whole circle (1000px) and/or the angle of each segment (1 degree). (Note that if the segment angle is 90 degrees the performance is pretty bad too.)
>
> If I were drawing lines instead of arcs the optimisation is easy, I’d just copy the previous image down one pixel and then paint the new top line. But with arcs I’m have to issue a drawArc() for every arc that has to appear.
>
> I hope that somebody has some idea on how to optimize this.
>
> [code]
> package waterfall;
>
> import java.awt.Color;
> import java.awt.Graphics;
> import java.awt.Graphics2D;
> import java.awt.event.ActionEvent;
> import java.awt.event.ActionListener;
> import java.awt.geom.Arc2D;
> import java.util.Iterator;
> import java.util.LinkedList;
> import java.util.Random;
>
> public class WaterfallArc01 extends javax.swing.JPanel {
>
> private final int diameter = 1000; // pixels
> private final int sectorExtent = 1; // degree;
> private final int numberSectors = 360/sectorExtent;
> Random seed = new Random();
>
> LinkedList list = new LinkedList();
>
> public WaterfallArc01() {
> ActionListener taskPerformer = new ActionListener()
> {
> public void actionPerformed(ActionEvent evt)
> {
> generateNewData();
> repaint();
> }
> };
> javax.swing.Timer t = new javax.swing.Timer(500, taskPerformer);
> t.start();
> }
>
> private void generateNewData()
> {
> Color[] sectors = new Color[numberSectors];
>
> for(int i=0; i > {
> sectors[i] = getColor();
> }
>
> list.addLast(sectors);
>
> if (list.size()>diameter/2)
> {
> list.removeFirst();
> }
> }
>
>
> private Color getColor()
> {
> return new Color(seed.nextInt(0x1000000));
> }
>
>
> @Override
> protected void paintComponent(Graphics g)
> {
> render(g);
> }
>
> private void render(Graphics g)
> {
> Graphics2D g2d = (Graphics2D)g;
>
> long startTime = System.nanoTime();
> int size = diameter;
> int x=0;
> int y = x;
> double startAngle=0;
> double oldX=x;
>
> // Erase background to white
> g2d.setColor(Color.BLACK);
> g2d.fillRect(0, 0, diameter, diameter);
>
>
> Color[] sectors;
> Iterator it = list.descendingIterator();
> while(it.hasNext()) // each update
> {
> sectors = it.next();
>
> for(int i=0; i< sectors.length; i++) // all sectors
> {
> g2d.setColor(sectors[i]);
> g2d.draw(new Arc2D.Double(x, y, size, size, startAngle,
> sectorExtent, Arc2D.OPEN));
> startAngle += sectorExtent;
> }
> oldX = x;
> do{
> size = size - 1;
> x = (diameter - size)/2;
> } while(x == oldX);
> y = x;
> startAngle=0d;
> }
>
> long estimatedTime = System.nanoTime() - startTime;
> System.out.println(list.size()+" lines, render time: "+(double)estimatedTime/1e9);
> }
>
> }
>
> ---------------------------------------------------------------------------------------------------------------------------
>
> package waterfall;
>
> import java.awt.BorderLayout;
>
> public class TestWaterfallArc01 extends javax.swing.JFrame {
>
> public TestWaterfallArc01() {
> setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);
> setMinimumSize(new java.awt.Dimension(1000, 1000));
>
> WaterfallArc01 waterfallArc011 = new WaterfallArc01();
> getContentPane().setLayout( new BorderLayout());
> add(waterfallArc011, BorderLayout.CENTER);
> pack();
> }
>
> public static void main(String args[]) {
> java.awt.EventQueue.invokeLater(new Runnable() {
> public void run() {
> new TestWaterfallArc01().setVisible(true);
> }
> });
> }
> }
>
> [/code]
> [Message sent by forum member 'ser207' (ser207)]
>
> http://forums.java.net/jive/thread.jspa?messageID=300771
>
> ===========================================================================
> To unsubscribe, send email to listserv@java.sun.com and include in the body
> of the message "signoff JAVA2D-INTEREST". For general help, send email to
> listserv@java.sun.com and include in the body of the message "help".

===========================================================================
To unsubscribe, send email to listserv@java.sun.com and include in the body
of the message "signoff JAVA2D-INTEREST". For general help, send email to
listserv@java.sun.com and include in the body of the message "help".

ser207
Offline
Joined: 2008-08-11

> In other words each new arc is effectively
> "underneath" all of the
> previous arcs?
>

No, the opposite. Each new arc needs to be painted on the outside/on top, the previous arcs are 'effectively' pushed in towards the center. In any case I like your proposal.

Another observation from the program that I posted: if sectorExtent is set to 90 degrees (and with no other changes) the performance is pretty bad as well. But if it is set to 10 degrees the performance is much better than with 1 or 90 degrees. Unfortunately I need it to be 1 degree. :-(

I notice that in your response you use g.fillOval(...) or g.fill(Ellipse2D). Are these operations more efficient than g.draw(Arc2D)?

linuxhippy
Offline
Joined: 2004-01-07

Hi again,

It does not draw segments but I guess it should be easily extendable to do so - its late and I'll go to bed now instead of playing any further. Btw. it does 500 lines in 12ms on my C2D.
Did not think about the gradient solution, sounds really good :)

[code]

package waterfall;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.geom.Arc2D;
import java.awt.image.*;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;

public class WaterfallArc01 extends javax.swing.JPanel {

private final int diameter = 1000; // pixels
private final int sectorExtent = 1; // degree;
private final int numberSectors = 360/sectorExtent;
Random seed = new Random();

BufferedImage bimg = new BufferedImage(1000, 1000, BufferedImage.TYPE_INT_RGB);
int[] data=((DataBufferInt)bimg.getRaster().getDataBuffer()).getData();

LinkedList list = new LinkedList();

public WaterfallArc01() {
ActionListener taskPerformer = new ActionListener()
{
public void actionPerformed(ActionEvent evt)
{
generateNewData();
repaint();
}
};
javax.swing.Timer t = new javax.swing.Timer(50, taskPerformer);
t.start();
}

private void generateNewData()
{
Color[] sectors = new Color[numberSectors];

for(int i=0; i {
sectors[i] = getColor();
}

list.addLast(sectors);

if (list.size()>diameter/2)
{
list.removeFirst();
}
}

private Color getColor()
{
return new Color(seed.nextInt(0x1000000));
}

@Override
protected void paintComponent(Graphics g)
{
render(g);
}

void setRGB(int x, int y, Color[] colors)
{
// int angle = (int) Math.toDegrees(Math.atan2(x, y));
// angle = angle == 0 ? 1 : angle;
int rgb = colors[0].getRGB();

int index = y*bimg.getWidth() + x;
if(index < data.length)
{
data[index] = rgb;
}
}

void rasterCircle(int x0, int y0, int radius, Color[] colors)
{
int f = 1 - radius;
int ddF_x = 1;
int ddF_y = -2 * radius;
int x = 0;
int y = radius;

setRGB(x0, y0 + radius, colors);
setRGB(x0, y0 - radius, colors);
setRGB(x0 + radius, y0, colors);
setRGB(x0 - radius, y0, colors);

while(x < y)
{
if(f >= 0)
{
y--;
ddF_y += 2;
f += ddF_y;
}
x++;
ddF_x += 2;
f += ddF_x;
setRGB(x0 + x, y0 + y, colors);
setRGB(x0 - x, y0 + y, colors);
setRGB(x0 + x, y0 - y, colors);
setRGB(x0 - x, y0 - y, colors);
setRGB(x0 + y, y0 + x, colors);
setRGB(x0 - y, y0 + x, colors);
setRGB(x0 + y, y0 - x, colors);
setRGB(x0 - y, y0 - x, colors);
}
}

private void render(Graphics g)
{
Graphics2D g2d = (Graphics2D) bimg.getGraphics();

long startTime = System.nanoTime();
int size = diameter;
int x=500;
int y = x;
double startAngle=0;
double oldX=x;

// Erase background to white
g2d.setColor(Color.BLACK);
g2d.fillRect(0, 0, diameter, diameter);

Color[] sectors;
Iterator it = list.descendingIterator();
while(it.hasNext()) // each update
{
sectors = it.next();

/*for(int i=0; i< sectors.length; i++) // all sectors
{
g2d.setColor(sectors[i]);
g2d.draw(new Arc2D.Double(x, y, size, size, startAngle,
sectorExtent, Arc2D.OPEN));
startAngle += sectorExtent;
}*/
rasterCircle(500, 500, size/2, sectors);
oldX = x;
do{
size = size - 1;
x = (diameter - size)/2;
} while(x == oldX);
y = x;
startAngle=0d;
}

long estimatedTime = System.nanoTime() - startTime;
System.out.println(list.size()+" lines, render time: "+(double)estimatedTime/1e9);

g.drawImage(bimg, 0, 0, null);
}

}
[/code]

ser207
Offline
Joined: 2008-08-11

Ig thanks for your reply. I'm amazed by how much quicker your method is compared to g2d.draw( Ellipse2D)); There is a MASSIVE difference.

I have tried to adapt your solution to draw arcs; i've googled but have not been able to find an arcs algorithm that I can use (at least not one that works correctly). And not being a mathematician some of the algorithms meant nothing to me. Any help/pointers would be greatly appreciated.

linuxhippy
Offline
Joined: 2004-01-07

this thing is called midpoint circle algoyrthm.
There is also a version which draws the circly only in a defined angle, I was not able to find such a version with a quick look at search machines, but I think there are definitivly ready-to-use implementations available.

A better optimized solution would be to look up for the right color in setRGB depending on the angle of the currently drawn pixel - this way you draw the circle only once, altering the color is bascially free :)

lg Clemens

ser207
Offline
Joined: 2008-08-11

> this thing is called midpoint circle algoyrthm.
Yes after my previous post I found this: http://en.wikipedia.org/wiki/Midpoint_circle_algorithm
Which led me to hack your version of the waterfall code to do arcs.
Unfortunately I don't think it is accurate for small angles, for example less than 10 degrees. Any idea where I'm going wrong?

> A better optimized solution would be to look up for the right color in setRGB depending on the angle of the currently drawn pixel - this way you draw the circle only once, altering the color is bascially free
This is a cool idea!

[code]
package waterfall;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.Rectangle;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.geom.Point2D;
import java.awt.image.*;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;

public class WaterfallCircle01_LH_Arc extends javax.swing.JPanel {

private final int diameter = 1000; // pixels
private final int sectorExtent = 1; // degree;
private final int numberSectors = 360/sectorExtent;
Random seed = new Random();

BufferedImage bimg = new BufferedImage(1000, 1000, BufferedImage.TYPE_INT_RGB);
int[] data=((DataBufferInt)bimg.getRaster().getDataBuffer()).getData();

LinkedList list = new LinkedList();

public WaterfallCircle01_LH_Arc() {
ActionListener taskPerformer = new ActionListener()
{
public void actionPerformed(ActionEvent evt)
{
generateNewData();
repaint();
}
};
javax.swing.Timer t = new javax.swing.Timer(50, taskPerformer);
t.start();
}

private void generateNewData()
{
Color[] sectors = new Color[numberSectors];

for(int i=0; i {
sectors[i] = getColor();
}

list.addLast(sectors);

if (list.size()>diameter/2)
{
list.removeFirst();
}
}

private Color getColor()
{
return new Color(seed.nextInt(0x1000000));
}

@Override
protected void paintComponent(Graphics g)
{
render(g);
}

void setRGB(int x, int y, Color[] colors, Rectangle bounds)
{
int rgb = colors[0].getRGB();

if (bounds.contains(x, y))
{
int index = y * bimg.getWidth() + x;
if (index < data.length)
{
data[index] = rgb;
}
}
}

private Rectangle arcBoundingRectangle(Point startPoint, Point endPoint)
{
Rectangle r = new Rectangle(Math.min(startPoint.x, endPoint.x),
Math.min(startPoint.y, endPoint.y),
Math.abs(startPoint.x-endPoint.x),
Math.abs(startPoint.y-endPoint.y));
return r;
}

private Rectangle arcBoundingRectangle(Point2D startPoint, Point2D endPoint)
{
Rectangle r = new Rectangle((int)Math.round(Math.min(startPoint.getX(), endPoint.getX())),
(int)Math.round(Math.min(startPoint.getY(), endPoint.getY())),
(int)Math.round(Math.abs(startPoint.getX()-endPoint.getX())),
(int)Math.round(Math.abs(startPoint.getY()-endPoint.getY())));
return r;
}

private void rasterCircle(int x0, int y0, int radius, Color[] colors, Rectangle arcBounds)
{
int f = 1 - radius;
int ddF_x = 1;
int ddF_y = -2 * radius;
int x = 0;
int y = radius;

setRGB(x0, y0 + radius, colors, arcBounds);
setRGB(x0, y0 - radius, colors, arcBounds);
setRGB(x0 + radius, y0, colors, arcBounds);
setRGB(x0 - radius, y0, colors, arcBounds);

while (x < y)
{
if (f >= 0)
{
y--;
ddF_y += 2;
f += ddF_y;
}
x++;
ddF_x += 2;
f += ddF_x;

setRGB(x0 + x, y0 + y, colors, arcBounds);
setRGB(x0 - x, y0 + y, colors, arcBounds);
setRGB(x0 + x, y0 - y, colors, arcBounds);
setRGB(x0 - x, y0 - y, colors, arcBounds);
setRGB(x0 + y, y0 + x, colors, arcBounds);
setRGB(x0 - y, y0 + x, colors, arcBounds);
setRGB(x0 + y, y0 - x, colors, arcBounds);
setRGB(x0 - y, y0 - x, colors, arcBounds);
}
}

Point calcEndPoint(int anchorX, int anchorY, double radius, double angleRadians)
{
return new Point((int)Math.round(anchorX+(radius * Math.cos(angleRadians))), (int)Math.round(anchorY+(radius * Math.sin(angleRadians))));
}

Point2D calcEndPoint2D(int anchorX, int anchorY, double radius, double angleRadians)
{
return new Point2D.Double(anchorX+(radius * Math.cos(angleRadians)), anchorY+(radius * Math.sin(angleRadians)));
}

private void render(Graphics g)
{
Graphics2D g2d = (Graphics2D) bimg.getGraphics();

long startTime = System.nanoTime();
int size = diameter;
int radius = size/2;
int x=500;
int y = x;
double startAngle= Math.toRadians(0);
double endAngle = Math.toRadians(45);
double oldX=x;

int cx=500;
int cy=500;

// Erase background to white
g2d.setColor(Color.BLACK);
g2d.fillRect(0, 0, diameter, diameter);

Color[] sectors;
Iterator it = list.descendingIterator();
while(it.hasNext()) // each update
{
sectors = it.next();

/*for(int i=0; i< sectors.length; i++) // all sectors
{
g2d.setColor(sectors[i]);
g2d.draw(new Arc2D.Double(x, y, size, size, startAngle,
sectorExtent, Arc2D.OPEN));
startAngle += sectorExtent;
}*/
radius = size/2;
Point2D startPoint = calcEndPoint2D(cx, cy, radius, startAngle);
Point2D endPoint = calcEndPoint2D(cx, cy, radius, endAngle);
Rectangle bounds = arcBoundingRectangle(startPoint, endPoint);
rasterCircle(cx, cy, radius, sectors, bounds);
oldX = x;
do{
size = size - 1;
x = (diameter - size)/2;
} while(x == oldX);
y = x;
startAngle=0d;
}

long estimatedTime = System.nanoTime() - startTime;
System.out.println(list.size()+" lines, render time: "+(double)estimatedTime/1e9);

g.drawImage(bimg, 0, 0, null);
}

}
[/code]

linuxhippy
Offline
Joined: 2004-01-07

Well, this seems really hard to optimize ... tons of very small primitives.

The only advice I can give you is to grab the Raster of a INT_RGB buffered image:
byte[] data=((DataBufferByte)tex.getRaster().getDataBuffer()).getData() (in your case its an int[] of course), and write code that does the drawing on the pixel-array itself.

It should be really fast to colour those few pixels if you don't have to walk through a general framework, but instead do exactly what you need and that optimized.
The downside of course is quite a lot of hand-written low-level code.

lg Clemens

Ken Warner

lg -- this is exactly what I've been trying to tell
the Java2D guys for a couple of years now.

They just tell me that I'm too stupid to understand
the real value of BufferedImages.

My view of the "downside" is that's where
all the fun programming is.

java2d@JAVADESKTOP.ORG wrote:
> Well, this seems really hard to optimize ... tons of very small primitives.
>
> The only advice I can give you is to grab the Raster of a INT_RGB buffered image:
> byte[] data=((DataBufferByte)tex.getRaster().getDataBuffer()).getData() (in your case its an int[] of course), and write code that does the drawing on the pixel-array itself.
>
> It should be really fast to colour those few pixels if you don't have to walk through a general framework, but instead do exactly what you need and that optimized.
> The downside of course is quite a lot of hand-written low-level code.
>
> lg Clemens
> [Message sent by forum member 'linuxhippy' (linuxhippy)]
>
> http://forums.java.net/jive/thread.jspa?messageID=301094
>
> ===========================================================================
> To unsubscribe, send email to listserv@java.sun.com and include in the body
> of the message "signoff JAVA2D-INTEREST". For general help, send email to
> listserv@java.sun.com and include in the body of the message "help".
>

===========================================================================
To unsubscribe, send email to listserv@java.sun.com and include in the body
of the message "signoff JAVA2D-INTEREST". For general help, send email to
listserv@java.sun.com and include in the body of the message "help".