<?xml version="1.0"?>
<rss version="2.0">
	<channel>
		<title>optimisation problem</title>
		<link>http://www.allegro.cc/forums/view/586316</link>
		<description>Allegro.cc Forum Thread</description>
		<webMaster>matthew@allegro.cc (Matthew Leverton)</webMaster>
		<lastBuildDate>Tue, 11 Jul 2006 20:58:35 +0000</lastBuildDate>
	</channel>
	<item>
		<description><![CDATA[<div class="mockup v2"><div class="source-code"><div class="toolbar"></div><div class="inner"><table width="100%"><tbody><tr><td class="number">1</td><td><span class="k1">void</span> mode_7 <span class="k2">(</span><a href="http://www.allegro.cc/manual/BITMAP" target="_blank"><span class="a">BITMAP</span></a> <span class="k3">*</span>bmp, <a href="http://www.allegro.cc/manual/BITMAP" target="_blank"><span class="a">BITMAP</span></a> <span class="k3">*</span>tile, <a href="http://www.allegro.cc/manual/fixed" target="_blank"><span class="a">fixed</span></a> angle, <a href="http://www.allegro.cc/manual/fixed" target="_blank"><span class="a">fixed</span></a> cx, <a href="http://www.allegro.cc/manual/fixed" target="_blank"><span class="a">fixed</span></a> cy, <span class="k1">int</span> y_shift, MODE_7_PARAMS params<span class="k2">)</span></td></tr><tr><td class="number">2</td><td><span class="k2">{</span></td></tr><tr><td class="number">3</td><td>    <span class="c">// current screen position</span></td></tr><tr><td class="number">4</td><td>    <span class="k1">int</span> screen_x, screen_y<span class="k2">;</span></td></tr><tr><td class="number">5</td><td>&#160;</td></tr><tr><td class="number">6</td><td>    <span class="c">// the distance and horizontal scale of the line we are drawing</span></td></tr><tr><td class="number">7</td><td>    <a href="http://www.allegro.cc/manual/fixed" target="_blank"><span class="a">fixed</span></a> distance, horizontal_scale<span class="k2">;</span></td></tr><tr><td class="number">8</td><td>&#160;</td></tr><tr><td class="number">9</td><td>    <span class="c">// masks to make sure we don't read pixels outside the tile</span></td></tr><tr><td class="number">10</td><td>    <span class="k1">int</span> mask_x <span class="k3">=</span> <span class="k2">(</span>tile-&gt;w <span class="k3">-</span> <span class="n">1</span><span class="k2">)</span><span class="k2">;</span></td></tr><tr><td class="number">11</td><td>    <span class="k1">int</span> mask_y <span class="k3">=</span> <span class="k2">(</span>tile-&gt;h <span class="k3">-</span> <span class="n">1</span><span class="k2">)</span><span class="k2">;</span></td></tr><tr><td class="number">12</td><td>&#160;</td></tr><tr><td class="number">13</td><td>    <span class="c">// step for points in space between two pixels on a horizontal line</span></td></tr><tr><td class="number">14</td><td>    <a href="http://www.allegro.cc/manual/fixed" target="_blank"><span class="a">fixed</span></a> line_dx, line_dy<span class="k2">;</span></td></tr><tr><td class="number">15</td><td>&#160;</td></tr><tr><td class="number">16</td><td>    <span class="c">// current space position</span></td></tr><tr><td class="number">17</td><td>    <a href="http://www.allegro.cc/manual/fixed" target="_blank"><span class="a">fixed</span></a> space_x, space_y<span class="k2">;</span></td></tr><tr><td class="number">18</td><td>&#160;</td></tr><tr><td class="number">19</td><td>    <span class="k1">for</span> <span class="k2">(</span>screen_y <span class="k3">=</span> <span class="n">0</span><span class="k2">;</span> screen_y <span class="k3">&lt;</span> bmp-&gt;h<span class="k2">;</span> screen_y<span class="k3">+</span><span class="k3">+</span><span class="k2">)</span></td></tr><tr><td class="number">20</td><td>    <span class="k2">{</span></td></tr><tr><td class="number">21</td><td>        <span class="c">// first calculate the distance of the line we are drawing</span></td></tr><tr><td class="number">22</td><td>        distance <span class="k3">=</span> fmul <span class="k2">(</span>params.space_z, params.scale_y<span class="k2">)</span> <span class="k3">/</span></td></tr><tr><td class="number">23</td><td>            <span class="k2">(</span>screen_y <span class="k3">+</span> params.horizon<span class="k2">)</span><span class="k2">;</span></td></tr><tr><td class="number">24</td><td>        <span class="c">// then calculate the horizontal scale, or the distance between</span></td></tr><tr><td class="number">25</td><td>        <span class="c">// space points on this horizontal line</span></td></tr><tr><td class="number">26</td><td>        horizontal_scale <span class="k3">=</span> fdiv <span class="k2">(</span>distance, params.scale_x<span class="k2">)</span><span class="k2">;</span></td></tr><tr><td class="number">27</td><td>&#160;</td></tr><tr><td class="number">28</td><td>        <span class="c">// calculate the dx and dy of points in space when we step</span></td></tr><tr><td class="number">29</td><td>        <span class="c">// through all points on this line</span></td></tr><tr><td class="number">30</td><td>        line_dx <span class="k3">=</span> fmul <span class="k2">(</span><span class="k3">-</span>fsin<span class="k2">(</span>angle<span class="k2">)</span>, horizontal_scale<span class="k2">)</span><span class="k2">;</span></td></tr><tr><td class="number">31</td><td>        line_dy <span class="k3">=</span> fmul <span class="k2">(</span>fcos<span class="k2">(</span>angle<span class="k2">)</span>, horizontal_scale<span class="k2">)</span><span class="k2">;</span></td></tr><tr><td class="number">32</td><td>&#160;</td></tr><tr><td class="number">33</td><td>        <span class="c">// calculate the starting position</span></td></tr><tr><td class="number">34</td><td>        space_x <span class="k3">=</span> cx <span class="k3">+</span> fmul <span class="k2">(</span>distance, fcos<span class="k2">(</span>angle<span class="k2">)</span><span class="k2">)</span> <span class="k3">-</span> bmp-&gt;w<span class="k3">/</span><span class="n">2</span> <span class="k3">*</span> line_dx<span class="k2">;</span></td></tr><tr><td class="number">35</td><td>        space_y <span class="k3">=</span> cy <span class="k3">+</span> fmul <span class="k2">(</span>distance, fsin<span class="k2">(</span>angle<span class="k2">)</span><span class="k2">)</span> <span class="k3">-</span> bmp-&gt;w<span class="k3">/</span><span class="n">2</span> <span class="k3">*</span> line_dy<span class="k2">;</span></td></tr><tr><td class="number">36</td><td>&#160;</td></tr><tr><td class="number">37</td><td>        <span class="c">// go through all points in this screen line</span></td></tr><tr><td class="number">38</td><td>        <span class="k1">for</span> <span class="k2">(</span>screen_x <span class="k3">=</span> <span class="n">0</span><span class="k2">;</span> screen_x <span class="k3">&lt;</span> bmp-&gt;w<span class="k2">;</span> screen_x<span class="k3">+</span><span class="k3">+</span><span class="k2">)</span></td></tr><tr><td class="number">39</td><td>        <span class="k2">{</span></td></tr><tr><td class="number">40</td><td>            <span class="c">// get a pixel from the tile and put it on the screen</span></td></tr><tr><td class="number">41</td><td>            </td></tr><tr><td class="number">42</td><td>            </td></tr><tr><td class="number">43</td><td>            <span class="k1">if</span> <span class="k2">(</span> <a href="http://www.allegro.cc/manual/fixtoi" target="_blank"><span class="a">fixtoi</span></a><span class="k2">(</span>space_x<span class="k2">)</span> <span class="k3">&gt;</span> <span class="n">0</span> <span class="k3">&amp;</span><span class="k3">&amp;</span> <a href="http://www.allegro.cc/manual/fixtoi" target="_blank"><span class="a">fixtoi</span></a><span class="k2">(</span>space_y<span class="k2">)</span> <span class="k3">&gt;</span> <span class="n">0</span> <span class="k3">&amp;</span><span class="k3">&amp;</span></td></tr><tr><td class="number">44</td><td>                 <a href="http://www.allegro.cc/manual/fixtoi" target="_blank"><span class="a">fixtoi</span></a><span class="k2">(</span>space_x<span class="k2">)</span> <span class="k3">&lt;</span> tile-&gt;w <span class="k3">&amp;</span><span class="k3">&amp;</span> <a href="http://www.allegro.cc/manual/fixtoi" target="_blank"><span class="a">fixtoi</span></a><span class="k2">(</span>space_y<span class="k2">)</span> <span class="k3">&lt;</span> tile-&gt;h <span class="k2">)</span></td></tr><tr><td class="number">45</td><td>            <span class="k2">{</span></td></tr><tr><td class="number">46</td><td>                <span class="k1">if</span> <span class="k2">(</span> screen_y <span class="k3">+</span> y_shift <span class="k3">&lt;</span> <a href="http://www.allegro.cc/manual/SCREEN_H" target="_blank"><span class="a">SCREEN_H</span></a> <span class="k3">-</span> <span class="n">1</span> <span class="k2">)</span></td></tr><tr><td class="number">47</td><td>                <a href="http://www.allegro.cc/manual/_putpixel32" target="_blank"><span class="a">_putpixel32</span></a> <span class="k2">(</span>bmp, screen_x, screen_y <span class="k3">+</span> y_shift,</td></tr><tr><td class="number">48</td><td>                           <a href="http://www.allegro.cc/manual/_getpixel32" target="_blank"><span class="a">_getpixel32</span></a> <span class="k2">(</span>tile, <a href="http://www.allegro.cc/manual/fixtoi" target="_blank"><span class="a">fixtoi</span></a> <span class="k2">(</span>space_x<span class="k2">)</span>, <a href="http://www.allegro.cc/manual/fixtoi" target="_blank"><span class="a">fixtoi</span></a> <span class="k2">(</span>space_y<span class="k2">)</span><span class="k2">)</span><span class="k2">)</span><span class="k2">;</span></td></tr><tr><td class="number">49</td><td>            <span class="k2">}</span></td></tr><tr><td class="number">50</td><td>&#160;</td></tr><tr><td class="number">51</td><td>            <span class="c">// advance to the next position in space</span></td></tr><tr><td class="number">52</td><td>            space_x <span class="k3">+</span><span class="k3">=</span> line_dx<span class="k2">;</span></td></tr><tr><td class="number">53</td><td>            space_y <span class="k3">+</span><span class="k3">=</span> line_dy<span class="k2">;</span></td></tr><tr><td class="number">54</td><td>        <span class="k2">}</span></td></tr><tr><td class="number">55</td><td>    <span class="k2">}</span></td></tr><tr><td class="number">56</td><td><span class="k2">}</span></td></tr></tbody></table></div></div><p>

Is there a way to speed this up? The problem is because of a whole lot of _putpixel32 calls.
</p></div>]]>
		</description>
		<author>no-reply@allegro.cc (giewueron)</author>
		<pubDate>Fri, 07 Jul 2006 01:29:45 +0000</pubDate>
	</item>
	<item>
		<description><![CDATA[<div class="mockup v2"><div class="quote_container"><div class="title">Quote:</div><div class="quote"><p>
The problem is because of a whole lot of _putpixel32 calls.
</p></div></div><p>
Or the _getpixel32 calls.  What exactly is this function suppose to do?
</p></div>]]>
		</description>
		<author>no-reply@allegro.cc (Onewing)</author>
		<pubDate>Fri, 07 Jul 2006 01:42:17 +0000</pubDate>
	</item>
	<item>
		<description><![CDATA[<div class="mockup v2"><p><a href="http://img277.imageshack.us/my.php?image=ff5ee.jpg">http://img277.imageshack.us/my.php?image=ff5ee.jpg</a></p><p>Draws the football pitch in 3D.
</p></div>]]>
		</description>
		<author>no-reply@allegro.cc (giewueron)</author>
		<pubDate>Fri, 07 Jul 2006 01:57:47 +0000</pubDate>
	</item>
	<item>
		<description><![CDATA[<div class="mockup v2"><p>First is to use floats and not fixed, second is to use some bitshifts (dividing by 2 is the same as &gt;&gt; 1), and lastly some direct memory access may speed it up by using the line pointers. I also see a lot of use of sin/cos with the same angle value, I would call those once in a variable at the upmost level you can so you aren&#39;t calculating it all the time. Lowering your Bpp to 16-bits will also make an improvement but you will have less colors, but judging by your screenshot you could do it in 8-bpp.
</p></div>]]>
		</description>
		<author>no-reply@allegro.cc (Steve Terry)</author>
		<pubDate>Fri, 07 Jul 2006 03:28:08 +0000</pubDate>
	</item>
	<item>
		<description><![CDATA[<div class="mockup v2"><p>&quot;First is to use floats and not fixed, second is to use some bitshifts (dividing by 2 is the same as &gt;&gt; 1),&quot;</p><p>I think this won&#39;t give any significant speed. Those fix* routines maybe even do bitshifts themselves. <img src="http://www.allegro.cc/forums/smileys/smiley.gif" alt=":)" /></p><p>&quot;and lastly some direct memory access may speed it up by using the line pointers. I also see a lot of use of sin/cos with the same angle value, I would call those once in a variable at the upmost level you can so you aren&#39;t calculating it all the time.&quot;</p><p>Maybe direct memory access hmm. How to use it? How to apply it in 16 bits and 640x480?<br />Second... from Allegro Docs looks like fixed trigonometry already uses lookup tables.</p><p>&quot;Lowering your Bpp to 16-bits will also make an improvement but you will have less colors, but judging by your screenshot you could do it in 8-bpp.&quot;</p><p>Seems to work cool but no speed change. <img src="http://www.allegro.cc/forums/smileys/undecided.gif" alt=":-/" /></p><p>I thought about returning to my first idea and to use the textured polygon3d function from Allegro, but I don&#39;t know if it would be faster. Maybe I should really switch to OpenGL w/AllegroGL. Would it be possible to use sprites without some bilboarding tricks, just by simple stretch_draw_sprite? Models would take out the oldschool feeling. I wanted to make crappy graphics to make it run on slower PCs but with this routine it seems impossible. Or maybe there&#39;s somewhere on the net an addon Allegro library with a draw_sprite routine with skewing (deformation of the sprites border rectangle), stretching and rotating. There&#39;s one for AA sprites so maybe ;]
</p></div>]]>
		</description>
		<author>no-reply@allegro.cc (giewueron)</author>
		<pubDate>Fri, 07 Jul 2006 03:46:51 +0000</pubDate>
	</item>
	<item>
		<description><![CDATA[<div class="mockup v2"><p>The fixeds are fine, especially since he&#39;s using tight loops. Might be better to replace the fixtoi calls with &gt;&gt;16, though (not sure if Allegro inline&#39;s the function to do the same thing). Also, check out the exflame example for direct bitmap access. Specificly, you want the functions:
</p><div class="source-code snippet"><div class="inner"><pre>bmp_select
<a href="http://www.allegro.cc/manual/bmp_read_line" target="_blank"><span class="a">bmp_read_line</span></a>
<a href="http://www.allegro.cc/manual/bmp_write_line" target="_blank"><span class="a">bmp_write_line</span></a>
bmp_read32
bmp_write32
<a href="http://www.allegro.cc/manual/bmp_unwrite_line" target="_blank"><span class="a">bmp_unwrite_line</span></a>
</pre></div></div><p>
</p></div>]]>
		</description>
		<author>no-reply@allegro.cc (Kitty Cat)</author>
		<pubDate>Fri, 07 Jul 2006 08:59:30 +0000</pubDate>
	</item>
	<item>
		<description><![CDATA[<div class="mockup v2"><p>compute bmp-&gt;w/2 and bmp-&gt;h/2 outside the for(...) loop instead of computing it each loop.</p><p>Use a Table of cosinus&amp;sinus that you will have filled since the start of the program.(I dunno if fcos &amp; fsin already do EDIT: they already do)</p><p>Try to avoid this line if possible, it is inside the loop and it is not needed if you check boundary correctly before
</p><div class="source-code snippet"><div class="inner"><pre><span class="k1">if</span> <span class="k2">(</span> <a href="http://www.allegro.cc/manual/fixtoi" target="_blank"><span class="a">fixtoi</span></a><span class="k2">(</span>space_x<span class="k2">)</span> <span class="k3">&gt;</span> <span class="n">0</span> <span class="k3">&amp;</span><span class="k3">&amp;</span> <a href="http://www.allegro.cc/manual/fixtoi" target="_blank"><span class="a">fixtoi</span></a><span class="k2">(</span>space_y<span class="k2">)</span> <span class="k3">&gt;</span> <span class="n">0</span> <span class="k3">&amp;</span><span class="k3">&amp;</span>
                 <a href="http://www.allegro.cc/manual/fixtoi" target="_blank"><span class="a">fixtoi</span></a><span class="k2">(</span>space_x<span class="k2">)</span> <span class="k3">&lt;</span> tile-&gt;w <span class="k3">&amp;</span><span class="k3">&amp;</span> <a href="http://www.allegro.cc/manual/fixtoi" target="_blank"><span class="a">fixtoi</span></a><span class="k2">(</span>space_y<span class="k2">)</span> <span class="k3">&lt;</span> tile-&gt;h <span class="k2">)</span>
</pre></div></div><p>
</p></div>]]>
		</description>
		<author>no-reply@allegro.cc (GullRaDriel)</author>
		<pubDate>Fri, 07 Jul 2006 14:08:27 +0000</pubDate>
	</item>
	<item>
		<description><![CDATA[<div class="mockup v2"><p>So that direct memory access... I have 16 bits 640x480 bitmap so bmpread32 would get two pixels of the image at once and I would have to do a 320x480 loop -- correct? <img src="http://www.allegro.cc/forums/smileys/smiley.gif" alt=":)" />
</p></div>]]>
		</description>
		<author>no-reply@allegro.cc (giewueron)</author>
		<pubDate>Fri, 07 Jul 2006 19:32:44 +0000</pubDate>
	</item>
	<item>
		<description><![CDATA[<div class="mockup v2"><div class="quote_container"><div class="title">Quote:</div><div class="quote"><p>
I have 16 bits 640x480 bitmap so bmpread32 would get two pixels of the image at once and I would have to do a 320x480 loop
</p></div></div><p>
Yes, though you could use bmp_read16/bmp_write16 instead of having to worry about endian issues.
</p></div>]]>
		</description>
		<author>no-reply@allegro.cc (Kitty Cat)</author>
		<pubDate>Sat, 08 Jul 2006 09:22:46 +0000</pubDate>
	</item>
	<item>
		<description><![CDATA[<div class="mockup v2"><div class="quote_container"><div class="title">giewueron said:</div><div class="quote"><p>

&quot;First is to use floats and not fixed, second is to use some bitshifts (dividing by 2 is the same as &gt;&gt; 1),&quot;</p><p>I think this won&#39;t give any significant speed. Those fix* routines maybe even do bitshifts themselves. <img src="http://www.allegro.cc/forums/smileys/smiley.gif" alt=":)" />
</p></div></div><p>
If they did, they would first have to check to see if the number is a power of two. When multiplying and dvividing by powers of two, always use shifts. When using normal arithmetic, the compiler is smart enough to convert &quot;/2&quot; to &quot;&gt;&gt;1&quot;, but if the arithmetic is embedded inside a function such as fixdiv(), it is no longer possible for the compiler to optimize.</p><p>Also, once you&#39;ve followed the advice above and pre-calculated as much as you can outside the loop, you should acquire and release the bitmaps to save the bitmaps from having to be locked each time. If you are writing to a memory bitmap or if the screen-memory on your platform does not require a lock, you won&#39;t get a speed increase, but otherwise, you will. Have a look at the following functions:
</p><div class="source-code snippet"><div class="inner"><pre><a href="http://www.allegro.cc/manual/acquire_bitmap" target="_blank"><span class="a">acquire_bitmap</span></a>
<a href="http://www.allegro.cc/manual/release_bitmap" target="_blank"><span class="a">release_bitmap</span></a>
</pre></div></div><p>

Oh, and in case you haven&#39;t done so, use your compiler&#39;s optimization flags to optimize your code.
</p></div>]]>
		</description>
		<author>no-reply@allegro.cc (Andrei Ellman)</author>
		<pubDate>Tue, 11 Jul 2006 20:38:35 +0000</pubDate>
	</item>
	<item>
		<description><![CDATA[<div class="mockup v2"><div class="quote_container"><div class="title">Quote:</div><div class="quote"><p>
draw_sprite routine with skewing (deformation of the sprites border rectangle)
</p></div></div><p>

polygon3d[_f]() can do this. Give it your sprite as a texture and an array of 4 V3D[_f] for the corners.  I&#39;m not sure you want this tho. I suspect you just need stretch_sprite() to get the effect you want.
</p></div>]]>
		</description>
		<author>no-reply@allegro.cc (Matt Smith)</author>
		<pubDate>Tue, 11 Jul 2006 20:58:35 +0000</pubDate>
	</item>
</rss>
