Zhlt 3.0 Beta

amckern · September 2004

<div class="IPBDescription">Download and test the lattest builds</div><span style="font-size:14pt;line-height:100%"><b>ZHLT 3.0</b></span>

Download > <a href="http://www.zhlt.tk" target="_blank">http://www.zhlt.tk</a>

<b>What is ZHLT 3.0?</b>
3.0 Is the next build of the ZHLT Tools, that xp-cagey left the community before he joined EA in Mid 2004

These tools, are designed to be the last complie tool version, for Half Life 1

<b>What do ZHLT do?</b>
Basicly they turn the raw .rmf, or .map into a playable .bsp map file, more info can be found at <a href="http://www.zhlt.info/what-the-compile-tools-do.html" target="_blank">http://www.zhlt.info/what-the-compile-tools-do.html</a>

<b>Should I download an use ZHLT? My q tools, are running quite well...</b>
As a rule of thumb you should always download, and run the lattest build of ZHLT

As for why, the q tools are over 6 years old, and where very powerful in there day and age, but as the world has progrssed, so has the tool set.

Orignal ZHLT was a coustom set of tools, writen by Zoner, who was an employee of GearBox at the time

Though to answer the qustion, ZHLT are very powerful, fast, and stable, not to mention that they do quite a bit more then the q tools can do, so yes, upgrade your tools, if you have not done so.

----------------------------------------

<span style="font-size:14pt;line-height:100%"><b>News</b></span>

2/November/2006

The NS forums are back!

----------------------------------------

<span style="font-size:14pt;line-height:100%"><b>Download The Tools</b></span>

Most people will want the 32-bit version, if you don't know which one you need, download this one. Even if you have a 64-bit processor (e.g. AMD Athlon 64) you are most probably running 32-bit Windows. If you have a 64-bit processors, and are running Windows 64-bit, download the version for 64-bit processors.

Windows 32
<a href="http://downloads.ammahls.com/zhlt/x86/zhlt34x86final.zip" target="_blank">http://downloads.ammahls.com/zhlt/x86/zhlt34x86final.zip</a> (715 KB)

Windows 64 (AMD 64 ONLY)
<a href="http://downloads.ammahls.com/zhlt/x64/zhlt34x64final.zip" target="_blank">http://downloads.ammahls.com/zhlt/x64/zhlt34x64final.zip</a> (357 KB)

You will also need to install the <a href="http://download.microsoft.com/download/d/3/4/d342efa6-3266-4157-a2ec-5174867be706/vcredist_x86.exe" target="_blank">Microsoft Visual C++ 2005 Redistributable Package (x32)</a> or the <a href="http://download.microsoft.com/download/9/1/4/914851c6-9141-443b-bdb4-8bad3a57bea9/vcredist_x64.exe" target="_blank">Microsoft Visual C++ 2005 Redistributable Package (x64)</a>

<b>System Requirements</b>

The Compile tools are built to be used with the below specifications, if your system dose not match these, you may experience lengthy compiles.

Pentium 4 or equivalent with SSE Support
128MB RAM
3MB Disk Space
Windows 98

----------------------------------------

<span style="font-size:14pt;line-height:100%"><b>Changelog</b></span>

<div class='quotetop'>QUOTE</div><div class='quotemain'>

ZHLT 3.0 For Half Life 1
Tool set Managed by amckern
amckern@yahoo.com
News Updates and downloads can be found at <a href="http://ammahls.com" target="_blank">http://ammahls.com</a>
View the Official ZHLT Docs at <a href="http://www.zhlt.info" target="_blank">http://www.zhlt.info</a>

You will also need to install the <a href="http://download.microsoft.com/download/d/3/4/d342efa6-3266-4157-a2ec-5174867be706/vcredist_x86.exe" target="_blank">Microsoft Visual C++ 2005 Redistributable Package (x32)</a> or the <a href="http://download.microsoft.com/download/9/1/4/914851c6-9141-443b-bdb4-8bad3a57bea9/vcredist_x64.exe" target="_blank">Microsoft Visual C++ 2005 Redistributable Package (x64)</a>

--------------------

BIG THANKS to Carl "XP-Cagey" Patrick, for helping us with code, to rectify the shadow code, and other support through the 3.0 beta stage, with out you ZHLT would not be where it is to day.

--------------------

3.4 Final (25 Feb 2006)

Testing is over, and no code changes have been made.

The tools are now safe for use, with 32 Bit, and Windows 64.

PLEASE, note that if you are going to run the 64 Bit tools, with a 32 Bit Operating System, you will get an error box telling you that you 'toolname.exe is not a valid Win32 Applaction'. - <a href="http://img517.imageshack.us/my.php?image=untitled1ty.png" target="_blank">http://img517.imageshack.us/my.php?image=untitled1ty.png</a>

Testing: Solokiller, x64, Puchi, Other Members of #mapping on GameSurge IRC

--------------------

3.4 Beta (10 Dec 2005)

All Tools
First Relase of 64 Bit Tools
Added Cpt_Andrew - Env_Sky code for SOHL Based Levels

--------------------

3.3 (9 Oct 2005)

CSG
Fixed
Some long standing Bugs - CSG Will no longer crash, unless there is some strange reason

RAD
Fixed
Some ZHLT Light Flag crashing - the ZHLT Flag Shadows are also slightly better

Package
Removed
All non SDK Power tools - keeping the tools up to date was/will be a pain

ALL TOOLS
Corrected
All .html page notes in the log file now point to www.zhlt.info.

Thanks to Wraiyth For the help with the bug we sorted out over MSN, and Animis Immortal for the motavation to get the bug fixes done

--------------------

3.2.1.1 (3 Apr 2005)

ALL TOOLS
I fixed some cosmetic changes up, such as giving the tools version 3.2.1

Package
Moved the .pl files for opt ENT data, to live in the power tools folder, as they should have! Sorry FragBait0

--------------------

3.2.1 (14 March 2005)

CSG
Removed HINTSKIP, this texture has been a bug, and appears to not work.

--------------------

3.2 (8 March 2005)

CSG
Fixed
HINTSKIP showing up in the world (AKA Getting rendered, and not discarded as it should have been).

RAD
Included the correct HLRAD.EXE Build

--------------------

3.1 (7 March 2005)

CSG
Added
Hint skip texture for GTK. Simply apply it as a group texture - WARNING! I do not have GTK, so this build might be not work as Planed - Thanks DeeTae for the idea.

RAD
Fixed
Some more RAD functions in relation to ZHLT Light Flags.

--------------------

3.0 Final (3 Feb 2005)

CSG
Fixed
Out Of World Errors in CSG, when the brushes where in-fact proper solids

RAD
Fixed
Primary Colour Bug, with light_env
Infinite v bug in HLRAD, when using odd sided texture lights
Black blotches, when Infinite v would spam

Package
Added
Opt_entdata
Hlfix
Makewad
Mapbackup
RESGen

Big Thanks to ts2do, for finding the small bit of code that has stoped Final from coming out for the past 6 months

--------------------

3.0 Beta 4 (11 Nov 2004)

Package
Added
ZHLT.wad This version fixes some issues when using a texture with capital letters
Lights.rad (Hammer 3.4)
Wad.cfg (1.7)

ALL TOOLS
Started converting functions to assembly, in other words, making each bit of code, as fast as it can go, by making it as Simple as possible

CSG and BSP
Cleaned up some tab spacing, so that built in command line options where displayed proper

RAD
Fixed
Crash bug when using Opaque entities
Added
Faster Rad Code by Nem, Improves compile time by about 15-27%

Ripent
Added
New command line switch (-parse), by Nem that Pareses and reformats entity data stripping all non-essential formatting, to cause less chance of a bug

--------------------

3.0 Beta 3

ALL TOOLS
This version was a test, for including the MSVC.lib code, it did not work, so was removed after a small internal beta test With members of #mapcore, and #svencoop on Game surge IRC

--------------------

3.0 Beta 2

ALL TOOLS
Updated Banner, with AJenbo's email address, for shared credits

CSG
Added AJenbo's CSG Code
This Code changed the default subdivide to 240, to save on Clip nodes by about 1.2%

--------------------

3.0 Beta 1

ALL TOOLS
Made the Banner look clean, and updated the Credits
Added an extra line, to the Bug Reports Banner, stating that if you have a mapping error, to ask at the modifications 'Nominated Mapping Help Forum', to help nub mapmakers Updated the compile error reference code to show Tommy14's Error Page that is much more comprehensive then the Standalone ZHLTProblems.html
Tweaked Tool's Complier optimising
Destroyed ALL errors at /w3 level compiles

VIS
Added faster Vis code, by Egir
This code changed the VIS Code to a basic form of assembly
Tested with AMD XP Chips, Not tested on Intel Chips or Older CPUs

--------------------

The Developers behind ZHLT 3.0 would also like to Thank

Torus Interactive, Razor Monkey Studios, Tommy14, Rae, Lego, Gugs, the Guys #countermap, James "Pongels1" Manfield, Unknown Worlds, Mum, Dad, EB Games Australia, The staff at Carmon Drive Takeaway, Chico Foods Australia, P&N Beverages, Paul Payne

</div>

-------------------------------

<span style="font-size:14pt;line-height:100%"><b>Bugs</b></span>

Please post any bugs you find, including

The complie log
Your machines cpu,
How much ram you have
Your os

-------------------------------

<span style="font-size:14pt;line-height:100%"><b>Links</b></span>

<a href="http://ammahls.com" target="_blank">http://ammahls.com</a>
Offical News, and Infomation on ZHLT 3.0

<a href="http://www.zhlt.tk" target="_blank">http://www.zhlt.tk</a>
Offical Download site for ZHLT 3.0

<a href="http://www.zhlt.info" target="_blank">http://www.zhlt.info</a>
Offical Docs Site, includes inks to web resources

Thanks
The ZHLT 3.0 Team

Thaldarin · September 2004

Good to see someone is keeping them going. I think your coding skills are better than your mapping skills <img src='http://www.unknownworlds.com/forums/html//emoticons/tounge.gif' border='0' style='vertical-align:middle' alt='tounge.gif' /> You should also think about reporting your tools update to other communities that might well use it. Or simply alert PHL.

amckern · September 2004

thanks

at the moment, the tools, are in very early BETA!

i'm wating for the code from ajenbo, for csg, so you dont have to 2 versions in the download

So the slower it seaps out the more chance i have of keeping the updates clean

once there is a stable beta, or a full final, i'll email the 300 addresses i have for half life news sites

amckern

Zyndrome · September 2004

Make sure to keep me updated too on this, amckern. <img src='http://www.unknownworlds.com/forums/html//emoticons/smile-fix.gif' border='0' style='vertical-align:middle' alt='smile-fix.gif' />

The_Real_Nem · September 2004

...or make an article similar to Merl's on the VERC.

Now to really confuse newbies with version numbers. Is it ZHLT? MHLT? AHLT? XHLT P Series? Ahhhh!

Tequila · September 2004

</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> (-Nem- @ Sep 20 2004, 07:35 PM)</td></tr><tr><td id='QUOTE'> ...or make an article similar to Merl's on the VERC.

Now to really confuse newbies with version numbers. Is it ZHLT? MHLT? AHLT? XHLT P Series? Ahhhh!  </td></tr></table><div class='postcolor'> 
It's ZHLTMHLTAHLTXHLT XXX Series.

Mendasp · September 2004

I'd say it is...

BoPHLT

Bunch of People's Half-Life Tools

wnn · September 2004

Nice, ill see how it works on my Intel processor.

Hibame · September 2004

Its

ATAI

amckern's try at insanity

amckern · September 2004

its ZHLT 3.0

Read ^^^ the thread topic

also, thanks, and please note that this is not a map, so treat me well...

FragBait0 · September 2004

Amckern, relating to your latest post on the "Get the latest compile tools" thread...

Try using the putting the libraries where your compiler (MSVC?) can find them and extract the netvis directory into....your netvis directory <img src='http://www.unknownworlds.com/forums/html//emoticons/smile-fix.gif' border='0' style='vertical-align:middle' alt='smile-fix.gif' />

I compiled one of the libs myself from the code of sourceforge and the other, zlib, i got from some random zip. Not sure where it came from...was a long night argh.

EDIT: and I put this post here because... I could. It seems to be a better place - is it?

amckern · September 2004

thanks fragbait0

i'll see if this fixes it, and if so, i'll consider making a beta 3 release soon, still need to work on some code

amckern

Thaldarin · September 2004

I am having to use a previous version of the tools in RAD, because for some reason your tools will not use the .rad file and create texture lights. Strange, rest is fine, although I have no idea if anyone else has this problem, keep up the good work.

PC Specs (Incase you need them for the RAD probs)

Win Xp Home
512MB DDR Ram
2.4GhZ Intel Celeron
Ati Radeon 9200 64MB DDR Ram, not sure but think its 4x AGP.

amckern · September 2004

ok

No 1 else is having problems with this, though there was a problem with the beta 1 tools, and opaque lighting, this has been fixed in beta 3, though beta 3 has other bugs, so its not out at the moment

amckern

amckern · September 2004

<div class='quotetop'>QUOTE</div><div class='quotemain'>Hey amckern, seeing as you're working on a modified version of the p15 tools, i would really appreciate if you could answer a question for me, i'm having alot of trouble with my leaves (97.4 fullness and about to go right over) and i need to know why func_walls generate leaves during bsp. Also what could i use alternatively that wouldn't generate more leaves? If i made a duplicated of some geometry, made if a func_illusionary and textured the original clip, would that create the effect of a func_wall without generating the leaves?</div>

I just did a google search, and found that one of my fellow coders has a in-depth look at Vis - <a href="http://www.egir.dk/index.php?page=hlvis/hlvis.htm" target="_blank">http://www.egir.dk/index.php?page=hlvis/hlvis.htm</a>

Look at your map, and see if you can do anything to reduce the leaves, such as cutting the brush with clip, and not letting vis do it for you -its allot of gl_wireframe 1, but well worth it, once its done, also null any sides of entities the player wont see

Making a square of brushes around a pipe, or such, will reduce the entity count, and also, make the leaf count smaller, and speed Vis up, as you can see by the MS Paint shown here -

<img src="http://ammahls.com/zhlt/helping_vis_with_leaves.JPG" border="0" alt="IPB Image" />
<span style="font-size:8pt;line-height:100%">Example of Brushwork</span>

At the end of doing this you should have a better map for Vis, that makes less leaves, and also speed the compile process up even more, Because you do some of the Grunt work that Vis would normally do.

amckern

Mendasp · September 2004

I thought beta 2 would fix this but it didn't. HLRAD keeps crashing when it says

</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>BuildFaceLights:
0 / XXXXXX</td></tr></table><div class='postcolor'>

This is compiling bast, btw.

</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> (HLRad log)</td></tr><tr><td id='QUOTE'>[Reading texlights from 'C:\Mapas\Rads\ns_bast.rad']
[24 texlights parsed from 'C:\Mapas\Rads\ns_bast.rad']

18457 faces
Create Patches : 99091 base patches
44 opaque faces
787791 square feet [113441984.00 square inches]
17377 direct lights

BuildFacelights:

----- END hlrad -----</td></tr></table><div class='postcolor'>

amckern · September 2004

opauce (sp?) lighting has issues

I'm FIXING them, in the mean time use the p15 rad, or tools

There beta, becuase they are in need of testing, so thanks medasp for leting me know its more then one map

amckern

The_Real_Nem · September 2004

I was playing with my BSP Viewer today (writing an export feature) and I noticed that there are A LOT of faces with unnecessary vertices (see attached). I noticed these vertices because I had to remove them and they were quite numerous (5%-10% of all faces had them).

So if you are looking for something to do, removing these could:<ol type='1'><li>Improve rendering performance.</li><li>Reduce BSP sizes (marginally).</li><li>Reduce compile times (I'm thinking of ray/polygon intersection).</li></ol>It shouldn't be too hard to do (let me know if there is some reason for these vertices).
Nem

amckern · September 2004

what tools are the bsps your looking at made with?

Stupid q, but if its a pre p15 complie, then cagey might have done something for this, in the p15 tools

The_Real_Nem · September 2004

Not sure what versions all the BSP files I tested use (as I didn't compile them) but I do have a p15 compiled BSP which does as I have explained (so the problem exists in p15).

Nem

Reve · September 2004

Hi everyone. Wow, I go away for a short time and suddenly there's a ZHLT 3 in the works! <img src='http://www.unknownworlds.com/forums/html//emoticons/smile-fix.gif' border='0' style='vertical-align:middle' alt='smile-fix.gif' />

Seeing as this is a new thread (the other was getting a <i>little</i> long), I'll reintroduce myself again - I'm the guy who wrote the merged docs for ZHLT 1.7 p14. I'd volunteered some time back to keep the docs up to date for you guys.

Well now I'm back, I've registered zhlt.info for the online docs. There's nothing there yet, but once I've got some hosting sorted I'll get going converting the docs and adding the new stuff.

I'll announce when the site is live in this thread. If anyone has anything they want added to the site apart from what exists in the p15 documentation (I'll also add the p15.5 notes and the ZHLT beta 1-3 notes), please post here or email me (is my email address on here?). Links to particularly good tutorials are particularly welcome - I'd like to make the site as good a resource as possible.

Thanks XP-Cagey for allowing me to link to the files on your site (er, when it comes back online that is <img src='http://www.unknownworlds.com/forums/html//emoticons/smile-fix.gif' border='0' style='vertical-align:middle' alt='smile-fix.gif' />).

It's good to be back - it's even better to see so much happen while I was away <img src='http://www.unknownworlds.com/forums/html//emoticons/biggrin-fix.gif' border='0' style='vertical-align:middle' alt='biggrin-fix.gif' />

Reve

amckern · September 2004

hey

Yeah, why not? I liked the p14 design better then the p13 stuff

<a href='http://ammahls.com/zhlt/helping_vis_with_leaves.html' target='_blank'>http://ammahls.com/zhlt/helping_vis_with_leaves.html</a> < thats a look at the above post, in a more designed space

my email is amckern@yahoo.com if you want to keep in contact with me, and about the only docs so far in the ZHLT 3.0 set is the changelog - that is in the download

amckern

Anpheus · September 2004

I remember reading that RAD uses a huge amount of very intensive matrix multiplication.

<b>Use Strassen or Coppersmith-Winograd algorithm and it can speed up 512x512 matrix multiplication by over 45 times</b>

Soylent_green · September 2004

Large maps are usually compiled with -sparse to avoid eating too much memory for a mosly empty matrix, could it be adapted to work effectively on this?(mostly zeros, probably run length compressed or something, edit: on second thought, not sure how it is stored, run-length seems so simple and so effective at compressing it, but we're not compressing for storage to a file here so other methods may be much more usefull).

Welcome to the forum by the way.

Anpheus · September 2004

Multiplication by 0 is the simplest operation possible. It wouldn't matter.

The size of the matrix by Strassen's method must be 2^x,2^x. So 256, 512, 1024. It is filled with zeroes to these dimensions.

To give an estimate, let's say 1024 operations were performed with 1024x1024 times 1024x1 dimension matrices.

This is in fact 1,048,576 multiplications per matrix by the normal method. That is, each row is multiplied by the column matrix, and each row has 1,024 values, so there are 1,024 multiplications per row, and 1,024 rows. Multiply this by another 1024 and you have approximately 1 billion (2^30) multiplications.

As map complexity increases, this value exponentially increases. For 2048 operations of 2048x2048 matrix times 2048x1 matrix, it would be eight billion (2^33) operations.

I do not personally know the actually mathematics of how many operations are performed. All I know is that for each patch, there are operations just like this.

This may require more memory, however I'm sure with smart programming it could be configured so that when the matrix is expanded to 2^n,2^n dimension, that the algorithm will not have to expand the matrix, and simply use assumed 0-filled 2x2 partitions (For Strassen's algorithm.)

I cannot come up with comparitive numbers, because unfortunately the pages I've looked at do not base the operation based on the size of each matrix, and instead the simply use the dimensions as though they were equal. Obviously 0 multiplication is irrelevant, so there's no way for me to guage the number of multiplications without replicating the algorithm and finding the relationship.

prsearle · September 2004

Fast matrix multiplys wouldn't affect the vismatrix speed at all because the vismatrix is never multiplied. The vismatrix is just a matrix of bits used to speed up patch-patch visibility tests (similar to the PVS system used for leaf-leaf visibility in Half-Life). The sparse option just enables compression of the bit string used to store the vismatrix and nomatrix disables it completely and computes patch visibility on-the-fly.

Soylent_green · September 2004

edit: bleh missed psearles reply.

Don't throw 'exponentially' around like that, If it increased exponentially then a matrix multiplication of 2 128x128 matrices would be 5*10^41 times more computationally expensive than the matrix multiplication of two 32x32 matrices.

There's a very simple way to sumarize what you just said: regular brute force matrix multiplication is O(n^3), Strassen is O(n^2.807), Copper Smith - Winograd is O(n^2.376).

Straight forward brute force is super simple to code but very slow for large matrices. From what I've read just now about Strassen and Copper Smith - Winograd they are rather tricky to implement well due to the structure of modern computer hardware(especially latencies) and due to the padding with zeros and similar which add overhead.

To get a sense of how quirky modern processors are: Memory reads have a latency of several hundred clock cycles, if the processor _must_ wait for a RAM memory access and has nothing to do it will sit idle for hundreds of cycles. On the pentium 4 you kind of suggest to it what to do, it will do it in some order it determines by itself and with an end result that's garuanteed to be the same as if it had done it in the order you presented code in your program. It breaks down the x86 instructions it recieves into micro ops, which are smaller instructions that are specific to this architecture.

In order to be able to run at higher clock frequencies operations such as multiplying or adding had to be pipelined, it's done in many smaller steps as in a car factory instead of doing one multiplication at a time, your doing a small part each cycle on different tasks, sort of like an assembly line in a factory. If every stage in the pipeline is kept busy it can crank out something like one multiplication in each clock cycle, but it is done in many stages each taking a cycle so there is a latency far larger than one cycle. When processors encounter a branch they first _guess_ the outcome of the operation and run as though it made an accurate guess, this is in order to keep busy with _something_ while it is waiting for the statement to be fully evaluated which may even need memory reads which are quick but with painfull latencies, if it can manage to predict what it needs next and stream it all from RAM it will work much faster. If it finds what it had been doing was wrong it scraps all that work, goes back and does it again, this hurts if you have a long pipeline like the pentium 4(particullarilly the prescott core which has 31 stages).

In order to read as little from the memory as possible it uses a bunch of cache memory on die, typically 2 layers of cache, one tiny, fast cache, and one bigger, slower cache. It caches both code and data, when some of it hasn't been used for a while it is overwritten by some arbitrary rule that seemed to work well in their simulations(e.g. first in last out).

Modern computers are very strange, and this seems to lead to some issues with this method that seems to take a fair bit of time to solve properly if you can't find workable code from a proper implementation which you are allowed to use.

I have no idea if a sloppy implementation would still be much faster than what we have now.

If there haven't been any performance profiles done on HLRAD it may even turn out that finding the components of the matrix takes up such a significant time that this optimization isn't worth any effort. When you actually have the matrix it takes very little time to do extra bounces, I take it each bounce is represented by a nxn * nx1 matrix multiplication, and this apparently takes very little time. Unless there is more significant multiplications done in other steps of the RAD alghoritm it would be insane to optimize to gain a few minutes.

Soylent_green · September 2004

Just out of curiosity, how does it determine visibillity? Does it first try and see if it can use the 'VIS data set'(whatever it might be called more technically, edit: PVS system?) to conclude that there is no visibillity and if that fails try to find any polys intercepting the line between the two patches in some clever way?

Anpheus · September 2004

</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> (prsearle @ Sep 30 2004, 06:15 PM)</td></tr><tr><td id='QUOTE'>Fast matrix multiplys wouldn't affect the vismatrix speed at all because the vismatrix is never multiplied. The vismatrix is just a matrix of bits used to speed up patch-patch visibility tests (similar to the PVS system used for leaf-leaf visibility in Half-Life). The sparse option just enables compression of the bit string used to store the vismatrix and nomatrix disables it completely and computes patch visibility on-the-fly.</td></tr></table><div class='postcolor'>
<a href='http://collective.valve-erc.com/index.php?doc=1046121871-81619100' target='_blank'>http://collective.valve-erc.com/index.php?...121871-81619100</a>

You can't tell me matrix multiplication isn't used.

Padding zeroes is relatively simple, and if you know that a cell (a 2x2 partition of a matrix) is composed of all 0s, you can code a way around it. You know that no matter what that cell will result in zeroes, there's no reason to use it for any mathematical purpose other than a placeholder.

Tricky to implement, but as far as I understand the code, the size of the array is equal to the number of patches within that patche's visibility. This can be an enormous number. I can easily believe that there are areas, particularly in large and outdoor spaces, where the number of patches are in excess of 512.

Even at a small matrix size, the operation is drastically more efficient in multiplications.

Yes, they do grow exponentially. To multiply two 32x32 matrices via the method taught in school, it takes 32,768 multiplications. A 128x128 matrix, on the other hand, would take 2,097,152 multiplications. That is, when the number of values increased by a factor of sixteen, the number of multiplications increased by a factor of sixty four.

That is an undeniable fact that it grows exponentially. It is a problem that cannot be solved in polynomial time, this has been demonstrated by Coppersmith and Winograd, from what I read they made it evident that there is no method that can achieve any less than O(n^2) on matrix multiplication of equally dimensioned matrices.

This method is faster in the performance of the calculation, and it results in a significant decrease in the amount of multiplications done. Yes, exponentially. Where you get 5*10^41 is absolutely beyond me. The number of multiplications has been demonstrated, you wrote down the figures in the paragraph immediately below that figure, yet it comes from nowhere.

Strassen's method requires 7 multiplications in each 2x2 cell, the standard method requires 8.

Perhaps all this is, is the bouncing. Regardless, an improvement in the speed of HLRad would be a blessing. I don't see how it is anything but this. Sloppy or not, these algorithm is demonstratably more efficient.

So I ask, <i>why not</i> implement them? To gain a few minutes is still a few minutes. What about the online compiler, albeit currently experiencing downtime. Time saved is time saved.

Soylent_green · October 2004

No, regular brute force is O(n^3), quit throwing "exponentially" around carelessly. If the number of multiplies increases exponentially with n, i.e. Ce^n, this means that Ce^128 / Ce^32 = e^96 = 5 * 10^41. I.e. if it did increase exponentially with n without some other factor in the exponent then a [128x128] * [128 x 128] matrix multiplication is 5*10^41 times worse than a [32x32] * [32x32] matrix multiplication, which is clearly insane.

If you want to be more general you can choose a constant other than unity in the exponent to try and adapt the exponential so that it fits with O(n^3) in the example I gave, but due to the properties of exponential functions I can choose another 2 matrices where it is inconsistent with O(n^3). Lets say you choose Ce^(n/m), where m is an integer constant. If I choose to compare the time it would take to mutiply two [(32*m)x(32*m)] matrices and the time it takes to multiply two [(128*m)x(128*m)] matrices I would again end up with the result that it takes 5x10^41 as many multiplications, of course since it is O(n^3) only ~4^3 = 64 times more multiplications are needed to do a matrix multiplication between matrices that have 4 times more colums and 4 times more rows.

You can easily see that it's O(n^3) by reasoning like this, have 2 matrices of nxn size, Then you need n multiplies per row and corresponding column to get an element and there are n^2 elements in the final matrix, i.e. it's O(n^3).

If you look at the MacLaurin series expansion of e^n you'll see why it doesn't correspond to O(n^3) if you still aren't convinced.

e^n = 1 + n + n^2/2! + n^3/3! +...
Which converges for all n.

Also look at the limit of e^n/n^m, when n tends to infinity and where m is any real positive number. It's zero, for large n, e^n grows faster than ANY power of n.

Also as has been said by psearle it can be compiled without the matrix which is mostly used as a lookup table for testing patch visibillities, haven't looked to close at the link yet, but all it seems to confirm glossing it over is that matrix multiplication is a minor performance issue here and that you read someones erroneous reply that O(n^2)([nxn] times a column matrix of size n) means it increases exponentially.

For CPU's you shouldn't assume multiplying takes much longer than adding and especially not conditional branching(e.g. in C: if ( <expression> == 0 ) {<do something>}).

Anpheus · October 2004

Not all examples of exponents are the same values. It is exponential... see, <i>n to the 3rd</i> versus <i>n to the 2.807</i>. Just because it is solved in <i>exponential time</i> doesn't mean it has to have a specific ratio of your choosing.

Dim. Of Matrices (n) 32
Normal (n^3) 32,768
Strassen (n^2.807) 16,786
Strassen/Norm 0.512278412

Dim. Of Matrices (n) 64
Normal (n^3) 262,144
Strassen (n^2.807) 117,475
Strassen/Norm 0.44813335

Dim. Of Matrices (n) 128
Normal (n^3) 2,097,152
Strassen (n^2.807) 822,126
Strassen/Norm 0.392020227

Dim. Of Matrices (n) 256
Normal (n^3) 16,777,216
Strassen (n^2.807) 5,753,466
Strassen/Norm 0.342933322

It can be demonstrated that the number of multiplications is <i>exponentially less</i>, describing the number of calculations fewer as approximately .3181n^3.1294.

What did I miss?

Zhlt 3.0 Beta

Comments