Money Mangled the Megabyte

Say What?!?

Some time ago, I was in an engineering meeting and we were discussing bandwidth and data rates.  I was waxing eloquent about how various IP blocks could deliver data at a rate of such and such megabytes per second.  I had just started my discourse and was building up to a full head of steam to deliver my prima facie case when one of the engineers in the room interrupted me and said “You mean mebibytes per second?”  I stopped for a moment squinted and wrinkled up my face and said to him whilst giving my very best ‘snooty waiter’ impression, “Excuse me?” He then demurely repeated himself because I was giving him ‘that look’ that bespoke me thinking quite loudly “Seriously?!? You just interrupted me when I was about to deliver a masterful and insightful comment?” Those of you who know me know ‘the look’ I am referring to that precedes me sucking all the air out of the room, but I digress – He said again “You mean mebibytes per second…you know…power of two and all that?”  Everyone in the meeting then turned to look at me, and not unlike watching a tennis tournament, waited to see how I was going to return the rather clumsily served ball.  I did what every well heeled, hot-blooded engineer would do in that case and  simply volleyed with a “Yeah…” and continued on my merry way with my brilliant, although now somewhat tarnished, point.

Elmer_FuddNow, two things were running through my head during this rather odd exchange.  Either this engineer had just said the word ‘megabytes’ twice the way Elmer Fudd would say it and therefore he had a speech impediment that I had never noticed before, and it was therefore prudent of me to not mock him and say very slowly and distinctly “yes…
M E G A B Y T E S” with the emphasis on the ‘G’ –or- perhaps I had no idea what the heck he was talking about and it was best to just nod and move on, because after all whilst unlikely it was possible that…well, you know.

I went back to my office and promptly decided to “research” this complete mispronunciation of the word ‘megabytes’.  Most of you probably thought I ran to Google as fast as frat boys to a keg – admit it…there’s no shame in that…but I say ‘nay nay’ (RIP John Pinette). Instead I went to the place that I always go to when I want ‘real’ answers – not answers ‘paid for’ by the highest bidder (ouch…too soon?)  Yes folks…I went to the ‘Dark Web’ which filled the void when Silk Road was “shut down”.

Accessing the Dark Web

Accessing the Dark Web

The answer to “are mebibytes a real thing?” came back very slowly and with a deet deet deet sound, you know the way computers work in the movies (because of the Matrix, Hollywood directors still think REAL computers connect to each other through telephone hard lines and run at 1200 baud (n,8,1)) but surprisingly my answer from the Dark Web did come back at like two characters per second and in green text– I guess it took that long because the folks running the dark web can’t see what the heck they are doing and are always running around looking for a flashlight.  Here is the answer – are you ready? NO – it was not 42 – stop that!  It was “B L A M E  T H E  I E C”.  Ooh…now I was getting somewhere!

So, what is this IEC…this oozing behemoth, this fibrous tumor, this monster of power and expense hatched from the simple human desire for engineering order? How did allegedly smart people spawn a vast, rampant cuttlefish of dominion with its tentacles in every orifice of the body of engineering policy? (my apologies to P.J. O’Rourke)

OK…so the International Electrotechnical (not a real word I fear) Commission, or IEC as they like to be called (because they are tired of people telling them that Electrotechnical is not a real word) have been around for 108 years (by way of contrast my Uncle Milton was around for 100 years and he always left “well enough alone” – which is probably why he was around for 100 years) and is comprised of 10,000+ engineers from 82 countries and they historically gave us the SI units from which such illustrious units as meter, kilogram, second, Kelvin, and candela were derived.  OK…so they also gave us radian, hertz, newton, pascal, joule, watt, volt, farad, Celsius, lumen, and… (I GET IT…they are smart people) – but THIS TIME they have gone TOO FAR I tell you!!!  The megabyte is sacrosanct.  How in the world did this happen? WHAT IN THE NAME OF ALL THINGS BINARY HAPPENED?

Blame the Hard Drive

Flux Capacitor

Flux Capacitor

There is a very famous saying that I applied liberally here to this tragedy. “Follow the money…”  Yep…in this case it absolutely turns out to be true – “Money Mangled the Megabyte”.  So…let’s just hop into our “way back” machine and head to the heady days of PCs when people bought hard drives to upgrade their computers.  Yes…a time of flux capacitors, proton packs (don’t cross the proton streams), Donkey Kong and Teddy Ruxpin (don’t judge).

 

It is the good old 80s and hard drive sizes were measured in mere megabytes…amazingly enough there was at one time a 32MB hard drive size limit ‘barrier’ in MS-DOS 3.x. I won’t go into a long winded discussion about this barrier – because someone else has already done so – click here for more info on this mind numbingly fascinating subject. Users had a huge hunger for bigger hard drives and they could buy them from peddlers advertising in Byte or PC Magazine and they often found when their hard drives arrived that they had to concern themselves with a dizzying array of complications like the fact that their new hard drives were physically organized into things like cylinders, heads, and sectors.  Now, I know that this is a bit difficult, but try to imagine such a thing as a 40MB hard drive (which cost ~$1000 at the time).

Cylinder Head Sector

Cylinder Head Sector

An example 40MB hard drive could have a ‘physical’ layout of 640 cylinders, 8 heads and 17 sectors per track with 512 bytes per sector. So that means that this hard drive had 4 “platters” with eight ‘heads’ that would rotate itself into and out of the gap between the cylinders and “fly” just above the magnetic field stored on the platters (top and bottom) – kind of like an old phonograph but without physically touching the media.  The data was stored in concentric circles and each of these concentric circles was called a ‘track’ – So if you had 640 ‘cylinders’ – the heads could seek discretely to one of the 640 concentric tracks on the platter. Each ‘track’ was further subdivided into 17 sectors – with each sector storing 512 bytes.

So, let’s do the math…640 cylinders x 8 heads x 17 sectors x 512 bytes per sector = 44,564,480 bytes.  Now…stay with me here…because this is the important bit.  The hard drive manufacturers would divide 44,564,480 by 1,048,576 (which in my book is a MB) because it is a power of two – 220 – which is what we computer folks like to think in when we think of computery types of numbers and this results in a product of ~42MB – which is what the hard drive manufacturers would then claim was the capacity of the hard drive. I am now climbing up onto my soapbox – so beware.

In the world that I come from it is quite simple.

1KB = 1,024 bytes or 2^10 bytes
1MB = 1,048,576 bytes or 2^20 bytes
1 GB = 1,073,741,824 bytes or 2^30 bytes
1TB = 1,099,511,627,776 bytes or 2^40 bytes

I don’t want to argue about this because this is the way it was from the beginning, is now and should be until we no longer need these units. I am now climbing off of my soapbox.

OK…back to our regularly scheduled programming.  The only rub was that in the good old days hard drives were fairly non-intelligent and they had to be ‘physically’ formatted by the hard disk controller. This little gem of technology was typically sold separately or already pre-installed in the computer (in the case of an upgrade).  Again…I won’t go into the lengthy discussion surrounding this but you can find out more here should you so choose. Once the physical format was completed it was up to the user to then apply the operating system’s file system to the hard drive in a process called ‘logical’ formatting – those of you who are over forty and used to use DOS surely remember the venerable fdisk and format utilities right?  During this logical formatting process, bad sectors might be found on the hard drive because hard drives are notorious for having some contaminants or imperfections on the platters that prevent data from being read or written to a particular physical location.  In this case, these bad spots were simply marked ‘bad’ by the logical formatting utility and the file system just worked around them.  Yes – this process resulted in ‘diminished’ storage capacity – but the amount of space reduction was miniscule because it represented the actual physical bad spots on the disk at the time – which were typically negligible in a brand new hard drive.  OK…got all that?

Now…another KEY thing to note here is that DOS and Windows reports (and likely always will??) storage device capacities as a “power of two” – which means 1MB = 1,048,576 bytes and so on…see and remember my ‘soapbox’ list above.  This is a VERY important piece of information to remember.

 

Furby

Furby

Time passes and hard drive technology advances at an almost breakneck pace.  Now we are in the 90s.  A time of Furbys, Beanie Babies, Pokémon and the rise of the hipster and the swelling of the dot com bubble.   Hard drives have become more and more intelligent until eventually – they start handling their OWN bad sectors instead of having to rely on the operating system to ‘work around’ bad sectors.  So in short, the hard drive simply reports back to the operating system how much storage is on the hard drive and there is no longer any tedious mucking about in hyperspace with cylinders, heads and sectors.

So – how was this accomplished? Several ways actually, but the practical upshot is that the hard drive simply ‘reserves’ sectors that are good – taking them away from the true physical storage capacity of the device – and makes them available for bad sector ‘remapping’ meaning that a few sectors of each track are reserved for the remapping of bad blocks.  Now…another interesting thing about hard drives is that bad spots on a hard drive can begin to ‘grow’ and start showing up in places where they weren’t detected before. That means that you can’t just reserve a fixed number of good sectors ahead of time to replace the actual number of bad sectors on the hard drive.  Instead, you have to come up with a very good estimate of how many sectors are likely to go bad over the life of the drive and reserve enough good sectors for those “sure to appear” bad spots as well.  Ah…did the light bulb come on?  NOW we start getting a glimpse of the crux of the problem…right?

hard_disk_drive1This reservation of sectors on every track to handle bad block remapping obviously results in a reduction of the actual usable space on the hard drive.  These new more intelligent hard drives report how much ‘real’ storage space is on the hard drive taking into account the reserved blocks for error handling.   So, once you connect the hard drive to your computer, your 100MB hard drive that you paid so much money for now actually shows up to the operating system as 93MB because ~7MB was reserved for bad block handling. Your 100GB hard drive suddenly becomes a 93GB hard drive and your 1TB hard drive becomes a 931GB hard drive.  Are you mad yet?  Well you might not have been – but a whole LOT of people were HOPPING mad.  Mad enough to actually file a lawsuit against Western Digital (a leading hard drive manufacturer) over this very issue.  Click here to add a little additional color to the matter.

So, the whole thing kind of went down like this. The hard drive engineers went to marketing and said “We have good news and bad news…”
Marketing folks said, “Good news first…” (They are always the optimists)
Engineers: “Our customers will never see bad blocks ever again on our hard drives…we fixed that.”
Marketing: “Great!!! What is the bad news?”
Engineers: “The hard drives are going to show up to the operating system smaller then you want them to be.”
Marketing – now furrowing their brows: “How much smaller?”
Engineers: “Small enough that you better not go out there saying that they are 512MB hard drives any more. They will be more like 498MB hard drives.”
Marketing: “Seriously?! We can’t do that…we can’t say 498 we have to say 500…we ALWAYS round up…it’s the way of our people.”
Engineers: “Well…don’t say we didn’t warn you…”
Marketing: “Fine…we will figure it out.” (which is code for “we are going to round up anyway” – but they  still round down the price from $800 to $799.99 which makes the consumer think it’s really only $700…right?)

However, somewhere on this long dusty road of storage technology a very smart marketing person figured out that a megabyte doesn’t really HAVE to be 1,048,576 bytes…what if it was…say…1,000,000 bytes?  Now the logic behind this is “if we say 100MB then since the hard drive thinks in power of two which means 104,857,600 bytes it should give us enough room factoring in bad block handling to say…” Well Mr. or Ms. Customer – you DO actually have an effective 100,000,000 bytes of storage which is in our book 100MB!” and therefore they just went ahead and stuck 100MB in the ads and on the box.  In effect the marketing folks simply just changed the definition of a megabyte from 1,048,576 bytes to 1,000,000 bytes.  Voila – problem solved and off to lunch.

Now those of you who are ‘engineering minded’ will do the math and say…wait 104,857,600 bytes is still less than the 7MB delta in your previous paragraph – so you STILL would have less than 100,000,000 actual usable bytes.  Clever catch…I kinda hoped you wouldn’t notice that – but since you did…I would like to point out that the ACTUAL physical storage is still based on cylinders, heads and sectors even though they are no longer exposed to the user.  Based on this method of storage organization a 100MB hard drive would usually have more storage capacity then a perfect 100MB and often times would hold 107MB or more once the numbers were run – so redefining 100MB to mean 100,000,000 bytes held sway – this is particularly true as you get to bigger drive sizes.  Now…enter REALLY big hard drives and the problem compounds.  Like I mentioned above – with a 1TB hard drive – when you factor in error handling and improper definitions – you might actually end up with a 1,000,000,000 byte drive (Terabyte) instead of a 1,099,511,627,776 byte drive (which you might have been expecting).  Worse still Windows is going to tell you that the drive you just hooked up to your PC is actually a 953MB hard drive…and well ain’t that special? That is a delta of almost 100 billion bytes that you thought you bought no matter HOW you slice it (assuming you think 1TB is a power of two…which it is).  This is a pretty big flippin’ deal and the proverbial fur started flying.

The IEC??

Now…enter the IEC.

IEC Headquarters in Geneva

IEC Headquarters in Geneva

In 1998 – this issue was somehow brought to their attention.  Perhaps they could smell this issue coming from 5823 miles away.  At any rate…I suspect that some rather high paid lawyer was looking for some legal justification to use at trial to defend the hard drive marketing folks’ declaration that they unilaterally changed the term MB from what we ALL know to be 1,048,576 bytes to 1,000,000 bytes.They searched high and low and came across the IEC and dared to ask THEIR opinion (this of course, after asking everyone from the plumber’s union to their favorite chefs in San Francisco what they thought).  After some highfalutin debate by the appropriately ordained IEC committee, I am quite sure that some engineer (NOT a computer programmer mind you) – said – “Well y’all…like we HAVE defined kilo to mean 10^3 and mega to mean 10^6 and giga to mean 10^9 for like something like 100 years give or take – like you know…the kilometer, kilogram, and so on…you feel me here?”  I imagine the debate went something exactly like that…led by a quite brilliant California valley girl who went to a very nice engineering college in Alabama and has hip hop leanings (the girl…not the college).

Officious IEC Meeting

Officious IEC Meeting

At this point, I am sure the illustrious committee handling this weighty matter agreed and said unanimously “yep…you are exactly right our brilliant fearless leader and your logic is flawless. A megabyte is now hereby and forever 1,000,000 bytes (and at that somebody then banged a gavel to add weightiness to the proceeding)…now that THAT is settled…what’s for lunch?”  Someone else at this point must have spoken up and said “Wait!!! We have to come up with a unit that the computery minded people can use to mean 1,048,576 bytes…after all…we just took away their precious megabyte.” Anxious to get to their buffet they must have not spent too much discussing this particular point because what they came up with was…and it is hard to type this with a straight face, much less SAY it with a straight face…the MEBIBYTE which they also cleverly abbreviated as ‘MiB’ (which silly me…I always thought was an abbreviation for ‘Men in Black’).

So what was the rationale for the made up word mebibyte? The IEC folks just took the starting letter of the word ‘binary’ and jammed it into the word megabyte replacing the ‘g’ with the ‘b’ and inexplicably replacing the ‘a’ with an ‘i’ apparently for some feeble attempt at engineering humor.  I mean…perhaps ‘mebabyte’ would have been better than ‘mebibyte’…it’s arguable – but any improvement in the term would have been…well…an improvement. As an aside…I am using Microsoft Word to write this tome and it keeps telling me that ‘mebibyte’ isn’t actually a word…the spell checker is having fits so that tells you how well accepted this silly unit is.  But…the IEC didn’t stop there…oh no…they went “all in” and just went ahead and messed up the REST of our venerable units.

So…what did our friends at the IEC come up with?  Here is the table:

IEC Unit Table

IEC Unit Table

Want to know my take on all this nonsense? ‘Kibibyte’ sounds like a treat for dogs.  ‘Yobibyte’ sounds like a cartoon character. ‘Mebibyte’ and ‘Tebibyte’ sounds like a cartoon character trying to say megabyte and terabyte.  ‘Gibibyte’ and ‘Zebibyte’ sound like folks who used to mess with the twelve tribes of Israel from the Bible.  Don’t get me started on what ‘pebibyte’ sounds like…

So…there we have it.  That is the story of how “Money Mangled the Megabyte”…I was going to call this “How I Met Your Mebibyte”…but for some reason an alliterative title appealed to me more.  Now we have this “official” silly sounding set of units that more and more computery people are thinking we have to use.  Worse still there is an increasing number of people who think a megabyte is 1,000,000 bytes.  It maketh me sad.  I say “Viva La Megabyte!!!!” -the power of 2 megabyte…you know…1,048,576 bytes…oh..never mind-.

Super Easy to Use 3D Engine (Su3De) – Binary File Format Part 5 – Textures

Peanut Butter Jelly Time

OK…its time for textures.  We have everything we need for a textured 3D model in the .SU3 format except for textures – yes…we will have to add color maps for models that don’t have textures…but all in due time.  Right now…textures.

So, lets say we have a 3D model with geometry:

Ford Flex Model Geometry

Now we want to add a texture map to it.

Ford Flex Model Texture

If all comes out right, we should get this when we render the model:

Ford Flex Model Rendered

A not so long winded texture discussion – hopefully

A texture is simply a bitmap. That’s it.  In the end, just a collection of pixels.  Usually the width and height of the bitmap (almost always) is a power of 2 – like 64×64, 128×128, 512×512, 512×128, etc.   The Ford Flex model texture is 512×512.  As you probably already know, the size of the texture is relatively unimportant – the larger the texture the more detail you can pack into it.  The problem is, the larger the texture, the more work the 3D renderer has to do to draw the model.  There is always a trade off between texture size and speed / performance.

So, what format can a texture be in?  THAT can end up being a complex question. Ultimately, the texture will end up in the format of the actual frame buffer of the graphics controller – but it will undergo a lot of changes along the way – getting sliced, diced, stretched, pulled, pushed, wrapped and mapped onto the triangles that make us the 3D model.  So, does it really matter what format the texture is in to start with? Well…actually yes…it does.  You see, the texture has to be pushed across the “host” memory interface into graphics memory prior to it getting used by the 3D renderer, so…in this case, while a bigger texture map gives you better visual results, smaller textures move across the host interface faster – again…a trade off.

Now…the first and obvious question that comes to mind is this…why can’t I just use PNG and JPG images for my texture map?  Well…you can…and…you can’t.  How’s that for an answer?

When you create your textures using whatever tool you use – PhotoShop, Z-Brush…whatever, you will most likely save out your texture as a pretty common format – like a JPG or PNG. You might even save out as a GIF (why…I don’t know…but you might). Most 3D engines, however, are going to require that you convert from one of these common formats into something it can actually understand and use.  SOME 3D engines will directly perform the JPG / PNG / GIF / blah blah conversion for you…but Su3De won’t.

Never fear, however, the Su3De .SU3 3D model conversion utility, however, will be DELIGHTED to do the texture conversion for you…

Now, the next question is – What will the SU3 model conversion utility convert the texture into?  Tongue in cheek answer – does it matter…do you really care?  Oh…you do? Well here is the answer then.

Bitmaps 101 – kind of

There are many different ways to express pixels in a bitmap.  Too many in fact.  For the purposes of further discussion R = Red component, G = Green component, B = Blue component and A = Alpha component.  As you are almost certainly aware, Alpha is the amount of transparency of the pixel with 0 being completely transparent and “maximum value” (whatever that is based on the bit depth) as fully opaque.

The lowest hanging fruit and simplest of the bitmap formats would be a straight 32-bit ARGB value.  This would mean that there would be 8 bits for each color component as well as the alpha component.  This ostensibly yields 4 billion possible color variations – again…kind of…but not really.  In reality, the number of possible color variations will be dictated by your LCD screen – or display device.  In many cases, the LCD panels are 18-bit yielding only 262,144 possible colors.  Most of the latest LCD panels are 24-bit wide which yields around 16.8 million possible colors. Simply food for thought when picking color depths for textures.

So…lets look at a 32-bit color depth texture:

32 bit frame buffer example

This is an example of “direct color”.  In this example, each pixel requires 4 bytes to represent the color information.  So, for our 16×8 texture, the requirement is 512 bytes.  Seems like a lot of memory for such a small bitmap, doesn’t it?  Now consider a texture that is 512×512 pixels. At 32 bit color, the memory requirement is a whopping 1MB – just for a single texture…like the Ford Flex texture above.  Is there a better way?  I daresay…there is.

What if we used LESS memory for each pixel…I mean do we REALLY need 8 bits for each component?  What if we cut the color depth in half?  Like use 16-bits per pixel instead?  Is this workable?  In fact, yes…it is.  Many / most of the 3D engines we work with will accept wither 32-bit or 16-bit color.  The trade-off?  The number of colors start becoming seriously limited.  Let me explain / show.

With 32-bit color, we have 8 bits for Red, 8 bits for Green and 8-bits for Blue and 8-bits for Alpha.  That means we have 256 SHADES of Red, 256 SHADES of Blue and 256 SHADES of Green to work with.  In many images, there are subtle color gradients that aren’t immediately obvious, because they blend together when we see them.  Our brain does that nifty little trick for us…  When we reduce the color depth, we reduce the number of “SHADES” of a particular color and this can create nasty artifacts called “banding” that makes images look…well…not so hot. Before we continue, lets talk about a couple of other color depth formats that are “common” and ones that we will likely be supporting with Su3De:

  • RGB565 – here we have 5 bits of Red (32 shades), 6 bits of Green (64 shades) and 5 bits of Blue (32 shades).  This results in 16 bits with no alpha channel.  This format is quite common.
  • RGB555 – 5 bits of Red (32 shades), 5 bits of Green (32 shades), 5 bits of Blue (32 shades) and an unused bit -or- the bit can be used for a “global” alpha value – i.e. on or off – interesting effects can be performed with this on the right graphics controller.
  • ARGB4444 – 4 bits of Alpha, 4 bits of Red (16 shades), 4 bits of Green (16 shades) and 4 bits of Blue (16 shades).  This is a format that is actually fairly common as well – for example the Sony Play Station Portable uses this format.

I want to give you an example of these formats with a “worst case” scenario – a fully saturated color (I chose green) gradient.  Here,  you can clearly see the banding in effect.  Then, I will show you a real texture – the Ford Flex – in the various formats.

First – lets look at a 32 / 24 bit example  - ARGB8888 – here we have 256 shades of green.

Green Gradient – ARGB8888

Now – lets take a look at RGB565 – here we have 64 shades of green and we can clearly see some banding. Remember – green has an extra bit for the other primary colors (red and blue) you lose half your colors – down to 32.

Green Gradient – RGB565

Here is RGB555 – 32 shades of green and wow…banding is pretty obvious. This is a common color format in embedded graphics systems.

Green Gradient – RGB555

Here is RGB444 – 16 shades of green…and well…it isn’t pretty.

Green Gradient – RGB444

OK…so this is an example of “worst case” scenarios. A saturated color gradient…but it is instructive to see. Now…I want to digress another moment and talk about 8-bit color.

8-bit “indexed” color and palettes

Wouldn’t it be nifty if we could store bitmaps using only a SINGLE byte?  If we could do this, a 512×512 texture would only be 256KBytes instead of 512KBytes for 16-bit color formats (RGB565/RGB555/RGB444) or 1MByte for 24/32-bit color.

Some graphics controllers DO allow you to use a single byte for a frame buffer / texture / bitmap – whatever.  This is called “indexed color” and it is like a “box of crayons”. Imagine a box of crayons (256 of them in fact) and every crayon is assigned a unique number from 0 to 255. Each crayon can be any color you want it to be – without color depth limitations (OK…it is usually RGB888). In this case, you can create high quality images using a small amount of memory. Take a look at the following example:

8-bit – “Indexed” color

When a value between 0 – 255 is written into the graphics controller’s memory, the graphics controller will go to a table called a “palette” and will index into that table and pull out the RGB value for that particular pixel. Clever, huh?

So…what does a green gradient look like with 256 colors? It looks JUST like its RGB888 counterpart because you can have 256 shades of green in an 8-bit color palette.  For more on indexed / palette color click here.

Back to our regularly scheduled programming

OK, so let’s look at our Ford Flex bitmap in the various color depths.

Here is full 24-bit / 32-bit color:

Ford Flex RGB888

Here it is in 16-bit color – RBB 565 format. You can see some image deterioration, but the image quality is quite acceptable given the fact that you knocked the memory size for the texture in HALF!!!

Ford Flex Texture RGB565

Here is the Ford Flex texture in RGB444 format. Now you can start to see some serious deterioration of image quality.

Ford Flex Texture RGB444

OK…and finally, here is an 8-bit version – which is indexed color / palette driven. You can see again, that this is quite acceptable and given the massive savings in memory and if you have a talented graphics artist around -or you are handy with PhotoShop – then you can probably “tweak” this image to make it work well. The savings in memory for this texture is 75% so it is certainly worth the effort if your graphics controller supports 8-bit textures.

Ford Flex Texture – 8-bit “Indexed” color

Dithering – a neat trick!

A neat trick that we often use when using 16-bit and even 8-bit color is “dithering”. Dithering – according to a nice wikipedia definition – is:

“…an intentionally applied form of noise used to randomize quantization error, preventing large-scale patterns such as color banding in images”

Click here to jump to the full wiki page on dithering.

So…how do you dither a 16-bit or 8-bit image?  One nifty way is a free PhotoShop plugin called “Depth Dither” from Graphest.  Graphest seems to be gone…but the plugin is still floating about in places like cnet and can be downloaded from here. Here is depth dither in action in PhotoShop:

Depth Dither in Action

Here is the result when we apply Depth Dither to the RGB444 Ford Flex texture. Compare this to the RGB444 image above. Pretty amazing…right?

Ford Flex Texture RGB444 dithered

Another way to apply “dither” to 16-bit and 8-bit images is to simply go into PhotoShop -or- Gimp and apply 1% or 2% Gaussian “noise” to the image. We have done this many times and it has yielded good results on SOME images.

Once again…back to our regularly scheduled programming

The purpose of all of these “bunny trails” is to form the basis for the 3D model SU3 conversion tool we are developing.  Specifically, what texture formats will we support and what, if any, conversions will we do on the image data?  These are key questions that must be answered.  So, to short circuit the long explanations, we plan to support the following “uncompressed” image formats in Su3De:

  • ARGB8888 – 8 bits each of alpha, red, green and blue. This format is surprisingly not all that common.  Usually, the red and the blue are swapped and this yields:
  • ABGR8888 – same as ARGB8888 except the red and blue values are swapped – this is a pretty common format.
  • BGRA8888 – yes…sometimes the alpha is the last byte and this changes the ordering of the data.
  • BGR888 – 8 bits of red, green and blue, no alpha – 24-bit format – not so common as a “direct” format – will need conversions on certain graphics controllers.
  • RGB888 – same as BGR888 with red and blue swapped
  • BGR565 – 16-bit format – no alpha.
  • RGB565 – 16-bit format – no alpha.
  • BGRX5551 – 16-bit format – no alpha – upper bit unused
  • BGRA4444 – 16-bit format with alpha – 4 bits of each
  • BGRA5551 – 16-bit format with 1 bit of alpha
  • BGRX8888 – 32-bit format with no alpha – essentially 24-bit color packed into 32-bits – upper 8 bits unused
  • I8 – 8-bit indexed color – palette entry must be supplied

Other formats might be added / supported as needed to round out color depth formats.

The methodology for conversion will be loading a PNG, JPG, GIF, whatever into the SU3 model conversion tool along with the .OBJ file – usually this will be automatically supplied in the corresponding .MTL file, then you will select the color depth for the texture based on a drop down list – and then voila…the SU3 will contain your model and texture in the desired format.

In the NEXT entry, I will show what the chunk header and chunk should look like for a texture and we will also cover COMPRESSED textures.  Texture compression is another very interesting topic and refers to the ability of the graphics controller to handle texture decompression in a hardware unit -rather than being handled by the processor directly – which would really defeat the purpose because then we could just use PNGs or JPGs directly…so something to look forward to.

One more thing

I wanted to give an example of the kind of 3D that Su3De will be doing on an actual embedded device…so here is a reference board with THREE LCDs running a demo that we developed using a basic graphics library with 3D primitives.  This is the Jade MB86R01 graphics controller driving the three displays.  This is EXACTLY the sort of thing Su3De is for.  Enjoy:

Super Easy to Use 3D Engine (Su3De) – Binary File Format Part 4 – Texture Maps

NOTE: There were a few minor errors in a couple of the previous posts.  I just wasn’t consistent in explaining the polygonal mesh with regards to vertices.  I have updated the posts and corrected the errors.  The problems were in the area of describing the vertices per triangle relationship.  So, to recap, there are three vertices per triangle and each vertex is comprised of an x, y and z coordinate.  Each coordinate is comprised of a float which requires four bytes.  So, each triangle of the polygonal mesh requires 36 bytes to describe.

Onward…

OK…finally we get to texture maps in the Su3De binary file format.  Texture maps are fairly straightforward to implement, however, there are lots of details that we have to deal with.  In no real order these details include:

  • Texture map color depth
  • Texture map compression
  • Multi-texturing
  • Texture animation
  • Live video as a texture map
  • Recorded or rendered video as a texture map
  • Texture map dimensions
  • Procedural textures

Something I want to also discuss is “terminology”…it can get muddy sometimes so I want to define the terms the way I want to use them with regards to Su3De.  This might result in a street fight…but that’s OK…I fight dirty.

Street fight over 3D terminology

A “texture map” refers to the coordinates (really just relative offsets into the texture bitmap itself) used to map the texture onto the 3D model’s polygonal mesh.

The term “texture” refers to the actual bitmap bits that are being mapped.

UV coordinates” are the values stored in the texture map (one for each vertex of each triangle and corresponding to each triangle) that are the relative offsets into the texture – normalized as values between 0 and 1.  We use the “U and V” to differentiate from X, Y, and Z that are used for mesh coordinates.

I have written a couple of articles / tech papers that you might find interesting if you are new to 3D and texture mapping.  They can be found here:

// Begin Soapbox

Now…at this point, I am going to climb up on my soap box and say a few things. Some of you have been kind enough to express your opinion with regards to the feature set of Su3De.  I want to remind you of the fact that this is to be a “SUPER EASY TO USE 3D ENGINE”.  This means that, at least in the first versions, there aren’t going to be a lot of powerful fancy features.  Yes, I know many of you are very smart…you have told me so…and that in order to be useful Su3De needs this feature or that.  Let’s get something straight…initially Su3De is being developed to satisfy a specific need that I have for a small feature set in a compact UI environment…nothing more.  I am making it “open source” so that you can freely add the features that you want and hopefully many of these new features will find their way into an official Su3De release in the future.  Yes, I know about shaders.  I know about bump / normal mapping.  I know about object physics, collision detection and reflection mapping and yes I know about open source 3D engines like Irrlicht and Ogre (they are awesome).  I appreciate the comments and PLEASE keep them coming…but bear in mind that the goal is a simple product and the feature set is going to be an extremely small subset of overall 3D functionality to achieve a specific goal.  BTW I REALLY liked the suggestion of converting FreeType text into a 3D object that can be used by Su3De…either statically using some tool -or- doing it at run time “on the fly”.  The “on the fly” method might add weight to Su3De that we don’t have the luxury of, however, this could be a compile option.

//End Soapbox

SU3 File format

Putting the texture map and the textures in the actual 3D model binary format along with the polygonal mesh has been a difficult decision.  Does it really belong there?  What about all the things outlined above – texture animation, live streaming video, recorded rendered video, various formats, etc.?  There are lots of good reasons to make the texture map and textures separate files instead of trying to cram everything into a single binary or a single “entity”.  With all this said, I really want a single file (analogous to a PNG as explained before) that contains the entire 3D object.  The “chunk” architecture of the .SU3 file format easily allows us to reference external files should we choose to implement some “advanced” features at a later time. So the decision is that we will have a texture map and a texture in the SU3 file format along with the mesh data (and other required chunks).

Texture Map

Ok, so remember our friend the cube?  Our cube has six sides and twelve faces because each side is made up of two triangles. This makes for thirty six vertices.  As a reminder the vertices look like this:

[sourcecode language="c"]
#pragma pack(1)
/* structure of floating point xyz coordinates */
typedef struct{
float x;
float y;
float z;
}SU3_VTX3F;

static SU3_VTX3F FlexVerts[] = {
{-10.000000f, 0.000000f, 10.000000f}, //triangle 1
{-10.000000f, 0.000000f, -10.000000f}, //triangle 1
{10.000000f, 0.000000f, -10.000000f}, //triangle 1
{10.000000f, 0.000000f, -10.000000f}, //triangle 2
{10.000000f, 0.000000f, 10.000000f}, //triangle 2
{-10.000000f, 0.000000f, 10.000000f}, //triangle 2
{-10.000000f, 20.000000f, 10.000000f}, //triangle 3
{10.000000f, 20.000000f, 10.000000f}, //triangle 3
{10.000000f, 20.000000f, -10.000000f}, //triangle 3
{10.000000f, 20.000000f, -10.000000f}, //triangle 4
{-10.000000f, 20.000000f, -10.000000f}, //triangle 4
{-10.000000f, 20.000000f, 10.000000f}, //triangle 4
{-10.000000f, 0.000000f, 10.000000f}, //triangle 5
{10.000000f, 0.000000f, 10.000000f}, //triangle 5
{10.000000f, 20.000000f, 10.000000f}, //triangle 5
{10.000000f, 20.000000f, 10.000000f}, //triangle 6
{-10.000000f, 20.000000f, 10.000000f}, //triangle 6
{-10.000000f, 0.000000f, 10.000000f}, //triangle 6
{10.000000f, 0.000000f, 10.000000f}, //triangle 7
{10.000000f, 0.000000f, -10.000000f}, //triangle 7
{10.000000f, 20.000000f, -10.000000f}, //triangle 7
{10.000000f, 20.000000f, -10.000000f}, //triangle 8
{10.000000f, 20.000000f, 10.000000f}, //triangle 8
{10.000000f, 0.000000f, 10.000000f}, //triangle 8
{10.000000f, 0.000000f, -10.000000f}, //triangle 9
{-10.000000f, 0.000000f, -10.000000f}, //triangle 9
{-10.000000f, 20.000000f, -10.000000f}, //triangle 9
{-10.000000f, 20.000000f, -10.000000f}, //triangle 10
{10.000000f, 20.000000f, -10.000000f}, //triangle 10
{10.000000f, 0.000000f, -10.000000f}, //triangle 10
{-10.000000f, 0.000000f, -10.000000f}, //triangle 11
{-10.000000f, 0.000000f, 10.000000f}, //triangle 11
{-10.000000f, 20.000000f, 10.000000f}, //triangle 11
{-10.000000f, 20.000000f, 10.000000f}, //triangle 12
{-10.000000f, 20.000000f, -10.000000f}, //triangle 12
{-10.000000f, 0.000000f, -10.000000f}, //triangle 12
};
#pragma pack()
[/sourcecode]

The wire mesh for the cube looks like the image below:

Cube with 36 vertices

As you can see, and as you know from previous posts, there are three vertices per triangle, so our texture map is also going to have three entries per triangle with each entry representing a UV texture map offset. Below is the code that describes the texture map for the cube.

[sourcecode language="c"]
#pragma pack(1)
static SU3_TEX2F FlexTexMap[36] = {
{0.001200f, 0.665600f}, //triangle 1
{0.001200f, 0.335200f}, //triangle 1
{0.331900f, 0.335200f}, //triangle 1
{0.331900f, 0.335200f}, //triangle 2
{0.331900f, 0.665600f}, //triangle 2
{0.001200f, 0.665600f}, //triangle 2
{0.664100f, 0.333200f}, //triangle 3
{0.333700f, 0.333200f}, //triangle 3
{0.333700f, 0.000800f}, //triangle 3
{0.333700f, 0.000800f}, //triangle 4
{0.664100f, 0.000800f}, //triangle 4
{0.664100f, 0.333200f}, //triangle 4
{0.999300f, 0.333400f}, //triangle 5
{0.665300f, 0.333400f}, //triangle 5
{0.665300f, 0.000800f}, //triangle 5
{0.665300f, 0.000800f}, //triangle 6
{0.999300f, 0.000800f}, //triangle 6
{0.999300f, 0.333400f}, //triangle 6
{1.000000f, 0.666000f}, //triangle 7
{0.665600f, 0.666000f}, //triangle 7
{0.665600f, 0.334200f}, //triangle 7
{0.665600f, 0.334200f}, //triangle 8
{1.000000f, 0.334200f}, //triangle 8
{1.000000f, 0.666000f}, //triangle 8
{0.663000f, 0.665300f}, //triangle 9
{0.334800f, 0.665300f}, //triangle 9
{0.334800f, 0.333800f}, //triangle 9
{0.334800f, 0.333800f}, //triangle 10
{0.663000f, 0.333800f}, //triangle 10
{0.663000f, 0.665300f}, //triangle 10
{0.331900f, 0.332100f}, //triangle 11
{0.000400f, 0.332100f}, //triangle 11
{0.000400f, 0.002000f}, //triangle 11
{0.000400f, 0.002000f}, //triangle 12
{0.331900f, 0.002000f}, //triangle 12
{0.331900f, 0.332100f}, //triangle 12
};
#pragma pack()
[/sourcecode]

The actual texture map for the cube we are describing here looks like the following:


No, there isn’t a problem with the bitmap. The top 1/3 is simply not going to be used. Our cube has six sides, therefore we are going to only use the bottom 2/3rds of our texture map area. The benefit of using a cube is that it is very easy to see each “side”.

With a more complex model, the triangle mapping obviously isn’t so straightforward. Speaking of triangle mapping, here is the same texture with the triangle mapping visually applied. This allows you to clearly see all twelve triangles and how they map to the texture.  OK, so the next thing we have to address is how we are going to add the texture map into the .SU3 binary format.

SU3 – Texture Map Chunk

The texture map chunk is defined simply with the chunk length as the number of bytes required to describe the UV coordinates and the chunk type defined as “MTXM”.  To add the texture map to a SU3 file from part 3′s example, we add the following code:

[sourcecode language="c"]
#define FOURCC_MTXM MAKEFOURCC(‘M’,’T’,’X’,’M’)
#pragma pack(1)
typedef struct{
float u;
float v;
}SU3_TEX2F;
static SU3_TEX2F FlexTexMap[36] = {
{0.001200f, 0.665600f}, //triangle 1
{0.001200f, 0.335200f}, //triangle 1
{0.331900f, 0.335200f}, //triangle 1
{0.331900f, 0.335200f}, //triangle 2
{0.331900f, 0.665600f}, //triangle 2
{0.001200f, 0.665600f}, //triangle 2
{0.664100f, 0.333200f}, //triangle 3
{0.333700f, 0.333200f}, //triangle 3
{0.333700f, 0.000800f}, //triangle 3
{0.333700f, 0.000800f}, //triangle 4
{0.664100f, 0.000800f}, //triangle 4
{0.664100f, 0.333200f}, //triangle 4
{0.999300f, 0.333400f}, //triangle 5
{0.665300f, 0.333400f}, //triangle 5
{0.665300f, 0.000800f}, //triangle 5
{0.665300f, 0.000800f}, //triangle 6
{0.999300f, 0.000800f}, //triangle 6
{0.999300f, 0.333400f}, //triangle 6
{1.000000f, 0.666000f}, //triangle 7
{0.665600f, 0.666000f}, //triangle 7
{0.665600f, 0.334200f}, //triangle 7
{0.665600f, 0.334200f}, //triangle 8
{1.000000f, 0.334200f}, //triangle 8
{1.000000f, 0.666000f}, //triangle 8
{0.663000f, 0.665300f}, //triangle 9
{0.334800f, 0.665300f}, //triangle 9
{0.334800f, 0.333800f}, //triangle 9
{0.334800f, 0.333800f}, //triangle 10
{0.663000f, 0.333800f}, //triangle 10
{0.663000f, 0.665300f}, //triangle 10
{0.331900f, 0.332100f}, //triangle 11
{0.000400f, 0.332100f}, //triangle 11
{0.000400f, 0.002000f}, //triangle 11
{0.000400f, 0.002000f}, //triangle 12
{0.331900f, 0.002000f}, //triangle 12
{0.331900f, 0.332100f}, //triangle 12
};

#pragma pack()

//build and write the texture map chunk
chk.chunkLength = sizeof(FlexTexMap);
chk.chunkType = FOURCC_MTXM;
fwrite(&chk, sizeof(SU3_CHUNK), 1, fp);
fwrite(&FlexTexMap, sizeof(FlexTexMap), 1, fp);
crc = 0×12345678; //bogus placeholder value
fwrite(&crc, sizeof(crc), 1, fp);

[/sourcecode]

After the texture is applied to the polygonal mesh we end up with the following rendered image:

Now…of course we haven’t yet written the actual texture data into the SU3 file, we have only written the texture map.  The texture itself is another complex topic and we will address that in the next post.

Housekeeping

So its time for a little bit of housekeeping for the project.  I have secured the domain name of Su3De.org for the project.  Su3De.org will be the official project page. For the source code we will be using GitHub for this project. The GitHub project site is: https://github.com/ricktewell/Su3De.

There is already quite a bit more code developed for this project then I have written about in the blogs.  It is likely that the GitHub repository will stay far ahead of the blog so if you want to “jump forward” a bit – then GitHub will be the place to go.  For example, the 3D OBJ to SU3 converter is starting to work at this point and I will be adding this source to GitHub soon.

So that’s it for now…see you in Su3De.

Super Easy to Use 3D Engine (Su3De) – Binary File Format Part 3 – File Format

In part 2, we talked about vertices in the Su3De binary model format. In this post I want to talk about the “overall” structure of the binary file and then add texture coords and texture maps to the format…in the NEXT post.  I know I said we would talk about textures here, but I got ahead of myself (hard hat area – be flexible and watch out for falling ideas).  We still need to talk a little more about the basic binary format first.  Jumping right in, the Portable Network Graphics (PNG) file format is an exceptionally well thought out binary format and was designed primarily with “network transmission” in mind and as a result has quite a few features geared to that. The PNG format is also equally well suited to being stored on a file system. You can probably tell by now where I am going with all of this talk about PNG. The plan is to use the PNG file format as a basic blueprint for the Su3De binary model format. You can learn more about the PNG format here. If you are knowledgeable in the ways of the PNG, the following will be eerily familiar to you.

Su3De File Header

In all good binary file formats, there should be a few bytes in the beginning that tell you that what you think you are reading is indeed actually what you are reading. For PNGs, this sequence is “0×89, 0×50, 0x4E, 0×47, 0x0D, 0x0A, 0x1A, 0x0A”. These 8 bytes tell you convincingly that you are dealing with a PNG file. Take a look at the hex file dump below of a very small PNG file.

PNG File Hex View

PNG File Header Table

Bytes Purpose
0×89 The high bit is set which is useful to identify a network transmission environment that supports 7-bit instead of 8-bit characters.  In this case, you would see a 0×09 and know that the rest of the file is bogus.
0×50, 0x4E, 0×47 The three ASCII characters representing the characters “PNG”.
0x0D, 0x0A ASCII “Carriage Return” (0x0D) and a “Line Feed”  (0x0A)
0x1A ASCII “Substitute” character which also happens to be a DOS text file “end of file” character
0x0A Another ASCII “Line Feed” (0x0A) perhaps for Unix / Linux text file environments?

A good bit of thought went into this sequence to insure that network transmission systems don’t fiddle with the data as it is transmitted and received.  For example, some file transfer systems change the 0x0D(Carriage Return), 0x0A(Line Feed) into just a Line Feed for example – stripping out the Carriage Return.  Some file transfer systems might ADD a Carriage Return to to the header ending Line Feed… At any rate, if you read the first 8 bytes and you get (in hexadecimal): 89 50 4E 47 0D 0A 1A 0A– then you can pretty much guarantee that the file isn’t being “tinkered with” – especially across a network.

So, what should the Su3De file header look like?  Should it copy the PNG format above or should it “be its own thing?”  I am highly inclined to go ahead and use the PNG file header format and simply replace the ASCII “PNG” with ASCII “SU3”. Why? The reason is simple…I intend to use many of the other elements of a PNG file as well moving forward…so this will make writing a SU3 “reader” simpler because you can use existing PNG reader code to read the SU3 files as well.

The Su3De file header will be:

0×89 – 0×53 – 0×55 – 0×33 – 0x0D – 0x0A – 0x1A – 0x0A

That was easy…wasn’t it?

Chunks of Data Goodness

Now, we are going to talk a bit about “chunks”. Chunks are “groups” of data that fall into a predefined category and are, for the most part, self contained “entities”. Chunks consist of a chunk header usually followed by a data field and ending with a CRC-32 value to insure that the chunk was read correctly (i.e. not corrupted in some way).  So the basic format of a PNG chunk (and now SU3 chunks) looks like the following:

[sourcecode language="c"]
typedef struct{
unsigned int chunkLength;
unsigned int chunkType;
unsigned char chunkData[];
unsigned int chunkCRC;
}CHUNK;
[/sourcecode]

chunkLength is a unsigned 32 bit value telling you how many bytes are in the chunkData field. A length of 0 means that there is no chunkData which is considered valid for some chunkTypes.

chunkType is a four character ASCII code.  The values can be any upper or lower case ASCII letter value – A-Z or a-z or any upper / lower case combination…although in some cases specific upper and lower case characters are meaningful – I will explain later.

chunkData is obviously the data that is meaningful relative to the chunkType. If chunkLength is 0, then there is no chunkData in the chunk.

chunkCRC is a CRC-32 value that protects the chunkType and chunkData fields.  This value is used to determine whether the chunk data that was read is valid or corrupted.  The CRC algorithm used (according to the “official” PNG specification) is defined by ISO 3309 and ITU-T V.42. Sample source code to generate this CRC value can be found here - among many other places I am sure.  It will, of course, be part of the Su3De engine.

NOTE: In PNGs, multi-byte sequences (shorts, ints, floats, etc.) are in big endian format.  In SU3 files, and as we discussed in a previous post, we will “stick to our guns” and use little endian for multi-byte sequences.

The great thing about this chunk architecture is that it is easily extensible.  You can add new chunks to the file format as needed without affecting previous readers / parsers.  If a reader doesn’t know about a particular chunk, it just ignores it.  As long as the “basic” required chunks are present…the model can be used. It is plain to see that you could easily add all kinds of features in the future without breaking the first binary format implementations.

Su3De Chunks

At this point, we are going to switch away from talking about PNG and start talking about Su3De’s binary model format SU3.  The chunk formats will be based on PNG and more about the actual PNG format (especially “chunking” can be found here and here.

Model Header Chunk

The first chunk that must be located in the SU3 is the header chunk identified as “MHDR“.  It is the first chunk in the file and will contain basic information about the model. It is a required chunk. In its initial defined form, it looks like this (subject to change – you are wearing your hardhat right?):

[sourcecode language="c"]
typedef struct{
unsigned int chunkLength;
unsigned int chunkType;
unsigned int faceCount;
unsgined int modelHints;
unsigned byte textureFormat;
unsigned byte vertexFormat;
unsigned int chunkCRC;
}SU3_MHDR;
[/sourcecode]

faceCount represents the number of faces in the model. Each face is comprised of three vertices with each vertex having a x, y and z coordinate. The vertices are defined in the MVTX chunk.

modelHints is a 32-bit bitfield that contains “hints” about the chunks that are in the SU3 model file.  This provides a kind of “heads up” to the model reader about the nature of the model.

textureFormat is a single byte value that indicates what format the texture data (if there is any) is in.  For example, the texture data could be 8-bit palettized, 16-bit direct color (555 or 565), 24-bit direct color, 32-bit direct color with alpha, some compressed data format, etc.

vertexFormat is a single byte value that indicates what format the vertex information is in.  Currently two formats are supported, floating point and fixed point.

Model Vertices Chunk

You read about this “chunk” in the last post, however, we weren’t calling them chunks then.  This chunk is identified as “MVTX” and is also a required chunk. By way of a refresher, here is the chunk format:

[sourcecode language="c"]
typedef struct{
float x;
float y;
float z;
}SU3_VTX3F;

typedef struct{
unsigned int chunkLength;
unsigned int chunkType;
SU3_VTX3F su3Vertices[3]; //x, y, z
unsigned int chunkCRC;
}SU3_MVTX;
[/sourcecode]

su3Vertices represent the polygonal mesh of the model.  Each entry in the SU3_VTX3 array represents a single vertex of a triangle.  The vertex entries are in x, y, z order so su3Vertices[0] would be the x entry of the first vertex of the first triangle, su3Vertices[1] would be the y entry of the first vertex of the first triangle, su3Vertices[2] would be the z entry of the first vertex of the first triangle, su3Vertices[3] would be the x entry of the second vertex of the first triangle…and so on.  It takes nine su3Vertices entries to fully describe one triangle.

Putting it all together “so far”…

Ok, so let’s use a basic 3D cube as an example.  Let’s build a SU3 file and look at it step by step.

First, we will have the file header:
0×89 – 0×53 – 0×55 – 0×33 – 0x0D – 0x0A – 0x1A – 0x0A

Next, we will have a MHDR chunk that will contain some key information:

[sourcecode language="c"]
SU3_MHDR su3mhdr;

su3mhdr.chunkLength = 10; //number of bytes in the data field
su3mhdr.chunkType = 0x5244484D; //ascii MHDR
su3mhdr.faceCount = 12; //a cube will have two triangles per side – and six sides
su3mhdr.modelHints = 0×0001; //bit 0 = mesh present (which is required)
su3mhdr.textureFormat = 0×0; //0 indicates no texture
su3mhdr.vertexFormat = 0×01; //1 indicates floating point format
su3mhdr.chunkCRC = crcval; //calculated CRC value for type + data fields
[/sourcecode]

After the MHDR chunk, we will have our vertex data in the form of a MVTX chunk:

[sourcecode language="c"]
SU3_VERTICES su3verts;
su3verts.chunkLength = numTriangles * (3 * 12); //3 verts per tri and (3 entries per vert (xyz) * 4 bytes per float
su3mhdr.chunkType = 0x5854564D; //ascii MVTX
//triangle 1
su3verts.vertices[0] = -10f; //tri 1 vertex 1 x
su3verts.vertices[1] = 0.0f; //tri 1 vertex 1 y
su3verts.vertices[2] = 10.0f; //tri 1 vertex 1 z

su3verts.vertices[3] = -10f; //tri 1 vertex 2 x
su3verts.vertices[4] = 0.0f; //tr1 1 vertex 2 y
su3verts.vertices[5] = -10.0f; //tri 1 vertex 2 z

su3verts.vertices[6] = 10f; //tri 1 vertex 3 x
su3verts.vertices[7] = 0.0f; //tri 1 vertex 3 y
su3verts.vertices[8] = -10.0f; //tri 1 vertex 3 z

//triangle 2
su3verts.vertices[9] = 10f; //tri 2 vertex 1 x
su3verts.vertices[10] = 0.0f; //tri 2 vertex 1 y
su3verts.vertices[11] = -10.0f; //tri 2 vertex 1 z

su3verts.vertices[12] = 10f; //tri 2 vertex 2 x
su3verts.vertices[13] = 0.0f; //tri 2 vertex 2 y
su3verts.vertices[14] = 10.0f; //tri 2 vertex 2 z

su3verts.vertices[15] = -10.0f; //tri 2 vertex 3 x
su3verts.vertices[16] = 0.0f; //tri 2 vertex 3 y
su3verts.vertices[17] = 10.0f; //tri 2 vertex 3 z

//…and so on for all 12 triangles
su3verts.chunkCRC = crcval; //calculated CRC value for type + data fields
[/sourcecode]

As with the MHDR chunk, a MVTX chunk is required.

The file ends with a chunk appropriately named MEND and it is a mandatory chunk with no data field that signals that “that’s all there is and there isn’t any more.”

[sourcecode language="c"]
typedef struct{
unsigned int chunkLength;
unsigned int chunkType;
unsigned int chunkCRC;
}SU3_MEND;

SU3_MEND su3End;

su3End.chunkLength = 0;
su3End.chunkType = 0x444E454D; //ascii MEND
su3End.chunkCRC = crcval; //calculated CRC value for type + data fields
[/sourcecode]

Quick and Easy Development Environment

I have started using the Bloodshed Dev-C++ development environment for quick code prototyping and testing.  Why…because it is AWESOME that’s why – despite the weird name.  You can find it here.  I use the Dev-C++ 4 version and haven’t tried Version 5 yet.

I wrote a “quick and dirty” SU3 file writer that will write out a 3D cube to a SU3 file using all the chunk stuff we talked about above.  This was done on a Windows XP system…but the code should compile pretty much anywhere. Here is the full source code to that writer:

[sourcecode language="c"]
#include <stdio.h>
#include <stdlib.h>

#define MAKEFOURCC(ch0, ch1, ch2, ch3)
((unsigned int)(unsigned char)(ch0) | ((unsigned int)(unsigned char)(ch1) << 8) |
((unsigned int)(unsigned char)(ch2) << 16) | ((unsigned int)(unsigned char)(ch3) << 24 ));

#define FOURCC_MHDR MAKEFOURCC(‘M’,’H’,’D’,’R’)
#define FOURCC_MVTX MAKEFOURCC(‘M’,’V’,’T’,’X’)
#define FOURCC_MEND MAKEFOURCC(‘M’,’E’,’N’,’D’)

#pragma pack(1)
/* structure of floating point xyz coordinates */
typedef struct{
float x;
float y;
float z;
}SU3_VTX3F;

typedef struct{
unsigned int chunkLength;
unsigned int chunkType;
}SU3_CHUNK;

typedef struct{
unsigned int faceCount;
unsigned int modelHints;
unsigned char textureFormat;
unsigned char vertexFormat;
}SU3_MHDR;

//header sequence including ‘SU3′
static unsigned char fileHeader[] = {0×89, 0×53, 0×55, 0×33, 0x0D, 0x0A, 0x1A, 0x0A};

static SU3_VTX3F FlexVerts[] = {
{-10.000000f, 0.000000f, 10.000000f}, //triangle 1
{-10.000000f, 0.000000f, -10.000000f}, //triangle 1
{10.000000f, 0.000000f, -10.000000f}, //triangle 1
{10.000000f, 0.000000f, -10.000000f}, //triangle 2
{10.000000f, 0.000000f, 10.000000f}, //triangle 2
{-10.000000f, 0.000000f, 10.000000f}, //triangle 2
{-10.000000f, 20.000000f, 10.000000f}, //triangle 3
{10.000000f, 20.000000f, 10.000000f}, //triangle 3
{10.000000f, 20.000000f, -10.000000f}, //triangle 3
{10.000000f, 20.000000f, -10.000000f}, //triangle 4
{-10.000000f, 20.000000f, -10.000000f}, //triangle 4
{-10.000000f, 20.000000f, 10.000000f}, //triangle 4
{-10.000000f, 0.000000f, 10.000000f}, //triangle 5
{10.000000f, 0.000000f, 10.000000f}, //triangle 5
{10.000000f, 20.000000f, 10.000000f}, //triangle 5
{10.000000f, 20.000000f, 10.000000f}, //triangle 6
{-10.000000f, 20.000000f, 10.000000f}, //triangle 6
{-10.000000f, 0.000000f, 10.000000f}, //triangle 6
{10.000000f, 0.000000f, 10.000000f}, //triangle 7
{10.000000f, 0.000000f, -10.000000f}, //triangle 7
{10.000000f, 20.000000f, -10.000000f}, //triangle 7
{10.000000f, 20.000000f, -10.000000f}, //triangle 8
{10.000000f, 20.000000f, 10.000000f}, //triangle 8
{10.000000f, 0.000000f, 10.000000f}, //triangle 8
{10.000000f, 0.000000f, -10.000000f}, //triangle 9
{-10.000000f, 0.000000f, -10.000000f}, //triangle 9
{-10.000000f, 20.000000f, -10.000000f}, //triangle 9
{-10.000000f, 20.000000f, -10.000000f}, //triangle 10
{10.000000f, 20.000000f, -10.000000f}, //triangle 10
{10.000000f, 0.000000f, -10.000000f}, //triangle 10
{-10.000000f, 0.000000f, -10.000000f}, //triangle 11
{-10.000000f, 0.000000f, 10.000000f}, //triangle 11
{-10.000000f, 20.000000f, 10.000000f}, //triangle 11
{-10.000000f, 20.000000f, 10.000000f}, //triangle 12
{-10.000000f, 20.000000f, -10.000000f}, //triangle 12
{-10.000000f, 0.000000f, -10.000000f}, //triangle 12
};
#pragma pack()

int main(int argc, char *argv[])
{
char *ptrVerts;
unsigned int crc;
SU3_CHUNK chk;
SU3_MHDR mHDR;

FILE *fp = NULL;

fp = fopen("c:\file.SU3", "wb");

fwrite(fileHeader, sizeof(fileHeader), 1, fp);

// build and write the model header chunk
chk.chunkLength = sizeof(mHDR);
chk.chunkType = FOURCC_MHDR;
fwrite(&chk, sizeof(SU3_CHUNK), 1, fp);
mHDR.faceCount = 12;
mHDR.modelHints = 0×01;
mHDR.textureFormat = 0×00;
mHDR.vertexFormat = 0×01;
fwrite(&mHDR, sizeof(SU3_MHDR), 1, fp);
crc = 0×12345678; //bogus placeholder value
fwrite(&crc, sizeof(crc), 1, fp);

//build and write the model vertex chunk
chk.chunkLength = sizeof(FlexVerts);
chk.chunkType = FOURCC_MVTX;
fwrite(&chk, sizeof(SU3_CHUNK), 1, fp);
fwrite(&FlexVerts, sizeof(FlexVerts), 1, fp);
crc = 0×12345678; //bogus placeholder value
fwrite(&crc, sizeof(crc), 1, fp);

//build and write the model end chunk
chk.chunkLength = 0;
chk.chunkType = FOURCC_MEND;
fwrite(&chk, sizeof(SU3_CHUNK), 1, fp);
crc = 0×12345678; //bogus placeholder value
fwrite(&crc, sizeof(crc), 1, fp);

system("PAUSE");
return EXIT_SUCCESS;
}
[/sourcecode]

Here is a hex dump of the file written by the code above:

SU3 File Hex Dump

If we had an actual reader / renderer (…like the Su3De engine itself), you would see the following:

Rendered Cube – as if from SU3 file

Wrap up for this post

We covered a lot of ground with this post.  In the next one, we will add texture coordinates and texture images to the SU3 format and start working on the .OBJ file converter that will build SU3 files from .OBJ and .MTL files. This will, of course, take several more posts to cover.  I hope you can see where we are going with all of this…and it is starting to make sense.

Thanks for reading and see you in Su3De!  Please add any comments if you think I am off in the weeds somehow and other things you might like to see here…

SUper Easy to Use 3D Engine (Su3De) – Binary File Format Part 2 – Outline

In part 1, I outlined some of the design goals for the Su3De model binary format.  Here, I am going to jump right in and start describing the format based on the work of the past week. The primary idea of the binary format is to be able to pass the object directly on to the Su3De engine so it can be used without any significant conversions or modifications.  This means that the IDEA is for Su3De to pass the model data onto the 3D driver level as intact as possible.  The benefits of this are obvious, speed – with a minor in simplicity. So, what do we need in the file format?  Here is the list I have started with:

  • Vertices
  • Normals
  • Color / Material Data
  • Texture Coords
  • Texture Image
  • Shaders?

Let’s go over these one by one (although vertices will be the focus of THIS post).

Vertices

Vertices are the only truly required objects in the binary format.  The vertices represent the polygonal mesh that makes up the structure of the model.  If all you have is vertices you can draw the 3D object, however, it won’t be very exciting.  It will be end up being flat shaded and will be drawn using a single color.

Ford Flex 3D model flat shaded

The point of all this is that it will be mandatory to have a list of vertices representing the polygonal mesh of the model. The chosen polygon format will be triangles. For now, there won’t be any attempt to “optimize” the mesh – like creating sequences of “triangle strips” or “triangle fans” to reduce the vertex count.  The binary format will be a STRAIGHT UP, three vertices for every triangle kind of thing to start with – meaning there will likely be future versions that will have some optimizations added.

The Ford Flex model shown above, is made up of  1560 triangles (also referred to as “faces”).  This means that there will be x, y, z coordinate entries for each vertex of each triangle. Each x, y, z coordinate entry will be a single precision floating point number requiring 4 bytes.  So each vertex requires 12 bytes and each triangle requires 36 bytes.  So the mesh size will be:

  • 1560 triangles X (12 bytes per vertex X 3 vertices) = 56,160 bytes

The representation of this model in ‘C’ code would look something like this:

[sourcecode language="javascript"]
static int g_numFlexVerts = 4680;

static SU3_VTX3F FlexVerts[12] = {
{-7.093400f, 6.617300f, -4.289700f}, //triangle 1 x
{-6.553800f, 7.036900f, -4.751400f}, //triangle 1 y
{-7.695800f, 2.596000f, -10.338000f}, //triangle 1 z
{-7.695800f, 2.596000f, -10.338000f}, //triangle 2 x
{-8.105300f, 2.607700f, -9.238200f}, //triangle 2 y
{-7.093400f, 6.617300f, -4.289700f}, //triangle 2 z
{0.000000f, -3.951100f, 23.106400f}, //triangle 3 x
{-3.790500f, -3.950100f, 22.999701f}, //triangle 3 y
{-3.790500f, -4.636200f, 22.999201f}, //triangle 3 z
{-3.790500f, -4.636200f, 22.999201f}, //triangle 4 x
{0.000000f, -4.634400f, 23.106400f}, //triangle 4 y
{0.000000f, -3.951100f, 23.106400f}, //triangle 4 z
//…and so on for the remaining triangles.
};
[/sourcecode]

Now, this is a binary format and one of the decisions we need to make is whether or not the .OBJ file converter will spit out a .H file for the model as an option. I don’t really see the disadvantage in having that as a feature of the Su3De object converter, so we are going to proceed with that as “very likely”. Being a binary format, however, we have to represent this data AS binary information. In this case, the data will look like this in memory:

[sourcecode language="javascript"]
0×22,0xfd,0xe2,0xc0,0xec,0xc0,0xd3,0×40,0×39,0×45,0×89,0xc0,0xbb,0xb8,0xd1,
0xc0,0×49,0x2e,0xe1,0×40,0×78,0x0b,0×98,0xc0,0xfe,0×43,0xf6,0xc0,0xdd,0×24,
0×26,0×40,0×73,0×68,0×25,0xc1,0xfe,0×43,0xf6,0xc0,0xdd,0×24,0×26,0×40,0×73,
0×68,0×25,0xc1,0x4f,0xaf,0×01,0xc1,0x8f,0xe4,0×26,0×40,0xab,0xcf,0×13,0xc1,
0×22,0xfd,0xe2,0xc0,0xec,0xc0,0xd3,0×40,0×39,0×45,0×89,0xc0,0×00,0×00,0×00,
0×00,0xd3,0xde,0x7c,0xc0,0xe8,0xd9,0xb8,0×41,0x8d,0×97,0×72,0xc0,0×70,0xce,
0x7c,0xc0,0×63,0xff,0xb7,0×41,0x8d,0×97,0×72,0xc0,0xc0,0x5b,0×94,0xc0,0x5d,
0xfe,0xb7,0×41,0x8d,0×97,0×72,0xc0,0xc0,0x5b,0×94,0xc0,0x5d,0xfe,0xb7,0×41,
0×00,0×00,0×00,0×00,0×01,0x4d,0×94,0xc0,0xe8,0xd9,0xb8,0×41,0×00,0×00,0×00,
0×00,0xd3,0xde,0x7c,0xc0,0xe8,0xd9,0xb8,0×41
[/sourcecode]

It is now time to digress and talk about endianness…

Endianness

After some thought, I have decided to simply go with a little endian format for the binary data. For those of you who might not know, endian ordering – which came from Gulliver’s Travels and the people of Lilliput.  Some people would crack their boiled eggs on the big end, while a previous Emperor decreed that you must crack your boiled eggs on the little end.  Therefore, there exists “little endians” and “big endians” in the world of Lilliput.
Endianessmap
Some clever person, decided that they would apply this terminology to the ordering of multi-byte sequences in computer systems.  Say, you have a 32 bit number (which is comprised of four 8 bit bytes…obviously).  How do you order the bytes?  If the number is 0×12345678 (305419896 in decimal) how does it “show up” in memory?  Does it show up as 0×12, 0×34, 0×56, 0×78 (big endian) -or- does it show up as 0×78, 0×56, 0×34, 0×12? It makes a HUGE difference.  There is a whole SLEW of processor systems out there that use big-endian and a whole SLEW of processor systems that use little-endian.  So, we had to make a choice and the choice is little endian for Su3De. For more information from Wikipedia on endianness, click here.

Here is a list of little endian systems – which is quite impressive – (list based on the previously mentioned Wikipedia article on endianness):

  • DragonFlyBSD on x86, and x86-64
  • FreeBSD on x86, x86-64, and Itanium
  • Linux on x86, x86-64, MIPSEL, Alpha, Itanium, S+core, MN103, CRIS, Blackfin, MicroblazeEL, ARM, M32REL, TILE, SH, XtensaEL and UniCore32
  • Mac OS X on x86, x86-64
  • iOS on ARM
  • NetBSD on x86, x86-64, Itanium, etc.
  • OpenBSD on x86, x86-64, Alpha, VAX, Loongson (MIPSEL)
  • OpenVMS on VAX, Alpha and Itanium
  • Solaris on x86, x86-64, PowerPC
  • Tru64 UNIX on Alpha
  • ESX on x86, x86-64
  • Windows on x86, x86-64, Alpha, PowerPC, MIPS and Itanium (and now ARM)

OK…so back to our regularly scheduled programming…

Vertices..again

We have determined that we will need three floats per vertex and three vertices per triangle, so that means that we should be able to just “open” a .SU3 file and start reading out vertices…right?  Well…of course it isn’t THAT simple.  We need a bit more information.  Like how many triangles are in the model.  So organizationally, we are going to need to know that. From a code standpoint then the first thing we read out of the file will be the triangle count (not actually a true statement…but let’s pretend for the moment). This brings us to this:

[sourcecode language="C"]
#pragma pack(1)

typedef struct{
float x;
float y;
float z;
}SU3_VTX3F;

typedef struct{
unsigned int triangleCount;
SU3_VTX3F vertices[1];
}SU3_VERTICES;

#pragma pack()
[/sourcecode]

Wait!!! Is this CODE I am starting to see. Methinks it is!!!

The #pragma pack(1) insures that the compiler will view the structure as being “byte aligned” and won’t add any clever “padding” that might interfere with our interpretation of the data as we read it. If the compiler pads the data, we won’t have any way of knowing this happened and we can easily get misaligned and the model will be read incorrectly.

Ford Flex with vertices showing…

OK…so NOW we have the beginnings, albeit ever so humble, of the Su3De binary file format. At this point, we can create a binary model that has everything we need to draw a 3D model like the Ford Flex example. In the next post, we will discuss the plan to incorporate some other things…starting with texture coordinates and textures.  This will be interesting for sure, so stay tuned.  See you in Su3De again soon.

Transit of Venus from My Back Yard

So,  yes…I am a little late in posting this.  On June 5, Venus (the planet and not the hot looking goddess) cleverly positioned itself directly between the Earth and the Sun causing itself to be seen as a little black spot on the Sun (cue music…) from various lucky locations on the Earth.   Now I happen to own a rather nice little telescope, so I decided to set it up in my backyard and check out the event. Apparently this is a rather rare event relative to the lifespans of human beings and won’t happen again until the year 2117 so I seriously doubt I will see it again. Yes, the smaller black dots are actually sunspots. Click on the pic for a high-res version.

OK…so a few technical details. The telescope. It is a Meade LX200 8″ Schmidt Cassegrain reflecting scope (which means it is short and squatty) as opposed to one of those LONG Newtonian reflector telescopes or one of those even longer refracting telescopes. The specifications (for those who are so inclined) are as follows:

  • Clear Aperature: 8″ (203mm)
  • Focal Length: 2000mm
  • Focal Ratio: f/10
  • Eyepiece: 1.25″ diagonal prism
  • Resolving Power: 0.570 arcseconds

To take the pictures of the event, I used my old trusty Nikon D100 digital camera. Yes…it is OLD and by today’s standards not very high resolution (coming in at a whopping 6 megapixels!!!) It is however, a Digital SLR and it works with all my old Nikon glass (lenses) and connects like a dream to my LX200.   It works fine and I like it. So there. Specs are as follows:

  • Sensor: CCD, 23.7 x 15.6 mm
  • Total Pixels: 3110×2030 (6.31 megapixels)
  • Lens Mount: Nikon F
  • Focal Length Multiplier: 1.5X
  • Storage: CompactFlash Type I/II
  • Sensitivity: ISO 200 – 1600
  • Shutter Speed: Bulb, 30 sec – 1/4000 sec

The first pictures I took were by simply holding the D100 with a 35mm lens up to the 28mm lens mounted in the telescope and moving the camera around until I could see the transit because I was too lazy to hook the camera up to the telescope directly (like above) and “dial it in” – which can be a pain sometimes.  The pictures came out kind of like you would imagine – not very good.  This was at the start of the event and you can see that Venus is on the lower left corner of the picture because the image is “inverted” when using a standard lens set up. After a few rather poor pictures it became clear to me that I should stop being lazy and use the camera adapter and directly connect the D100 to the optics of the telescope.

I then set the D100 to manual mode and simply adjusted the shutter speed until the pictures I took made sense.  I had to adjust the focal length of the camera adapter “barlow tube” and use the “focus” knob on the scope to get clean focus.  This took a little while.  Luckily the transit took several hours so I had plenty of time. Since there isn’t an “aperture” to speak of in a telescope set up (kind of fixed at F/10) the shutter speed and ISO settings are all you really have to work with.  I set the ISO to 800, which results in very little CCD noise and has good light gathering sensitivity.

Oh yeah…important safety tip.  I obviously had a solar filter installed on the telescope. This was important because a) you wouldn’t be able to see Venus without it due to the glare, b) you would go blind almost immediately and c) the telescope optics would melt.  Sighting in the scope was kind of interesting…since I didn’t have a solar filter on the “spotting scope” to see where to aim the scope to begin with.  Believe it or not, even with an object as big in the sky as the sun, training the optics to be precisely lined up with the sun is tricky when you can’t really look through the spotting scope.  This resulted in me using my hand and projecting the image of the spotting scope (in shadow) and the sun (bright spot on my hand through the spotting scope optics) and getting the bright dot in the middle of the shadow.  Sounds weird but it worked perfectly.

Here is a quick snap of my telescope set up in the backyard.

Now…for some of the pics I took with this setup. Hope you enjoy. The stuff that looks like “smoke” in some of the pictures are actually clouds. Enjoy the Transit of Venus! Most of us won’t see it again…

SUper Easy to Use 3D Engine (Su3De) – Binary File Format Part 1 – Outline

Over the course of the week as I have started work on Su3De, it has become obvious that we are going to need a binary file format for the 3D objects.  In many ways, this file format is at the heart of what Su3De is all about…a simple way to implement 3D graphics in an embedded environment.  The next step was to start investigating the properties of the binary file format and start work on a “converter” that can convert from a common 3D object format to the Su3De binary format, which I will refer to for the time being as the SU3 format.   The overriding rationale for the SU3 format is to create a 3D binary format that is optimized for embedded systems.  There are new 3D graphics engines that are coming that are quite simplified in nature and will be appropriate for simple MCUs (as opposed to the big SoCs found in smart phones and tablet computers – although Su3De will likely find a home here as well).  These new 3D graphics engines (and the older smaller OpenGL ES 1.1 ones) will benefit from Su3De and its simplified binary 3D object format.

Objectives

OK…so what are some of the objectives?  First, we want the format to be efficient for embedded systems.  That means that the format should be appropriate for being:

  1. Read as a file from the file system
  2. “Included” as a .H file into the graphics application’s code
  3. Stored in memory (Flash) at a set location / offset
  4. Beamed in from “outer space” – in other words it could come from anywhere – over a network link, for example

You might be wondering, why create a new file format? SURELY there must be a 3D file format that would be suitable for use without having to create something new.  I was actually hoping the same thing, but the only file format I could find that I thought might be appropriate is the .MOD file format which is a binary version of the Alias/Wavefront .OBJ file format (referred to from now on as simply .OBJ).  The problem is that the .MOD file format is proprietary and mostly undocumented and we aren’t really after a binary representation of the .OBJ file format anyway…but rather an extraction and reorganization of the data inside of the .OBJ file format…so a new file format it will be.

The first consideration was whether or not we should simply do an “on the fly” conversion and allow the Su3De user to just import an .OBJ file directly.  I quickly ruled this out, however, because it didn’t make a whole lot of sense.  Any “up front” conversions you can do to reduce processing makes a lot of sense and having the converter as part of the engine will add some fairly significant overhead.  Additionally, if new 3D formats get supported down the line, the Su3De engine will have to change to accommodate the new format(s).

2 ASCII or not 2 ASCII

Next, why not use an ASCII file format?  This would mean that you could conceivably (if you were a mutant) open a notepad app and type in a 3D object line by line.  Also, the object would be “human readable” and quite portable.  While all of this is certainly true, ASCII is an inefficient way to represent a 3D object inside of an embedded environment.  You immediately have to do all kinds of parsing of the ASCII data and then perform string to int, string to float, sting to ??? conversions and then BUILD the 3D object in memory (which would have to be dynamically allocated…meaning DRAM) for use.  You would lose any benefit of storing a bunch of 3D objects in flash memory and using them directly without doing any conversions.  So ASCII is not in any shape or form ideal for this kind of thing…so a binary file format it will be. I suspect that the data will also be much smaller in binary form than in ASCII form as well (yes, yes, yes you CAN compress ASCII data quite nicely…but then you have to add a decompresser to the Su3De engine and you still have all the ASCII related problems I outlined…so just drop it).

Decisions Decisions

This means that a few decisions have already been made (which is nice).

  1. There will be a converter application that will convert .OBJ files to .SU3 files.  This converter will ideally run on Windows, Linux and Macs.
  2. The  .SU3 file will be a binary format (as opposed to an ASCII format)
  3. The  .SU3 file format will be suitable for file system, direct flash memory storage, and include file use and will be immediately useful to Su3De without any further manipulation or conversions.

The two key pieces of information that the .SU3 file will carry initially are vertex and texture coordinates.  Additionally, triangles will be the preferred geometric mesh format – ideally suited for most OpenGL or basic 3D environments.  Each triangle in the 3D model will have three vertex coordinates and three texture coordinates.  For “shaded” 3D models, the texture coordinates will be absent and some kind of color information will be required – unless we pick some solid color to represent the 3D object as a “fallback” if the only data in the .SU3 file is geometry data.  This will be decided later.  Obviously, the .SU3 format will be “expandable” in some manner so we can add things like material information and normals as needed.  Since the “winding order” will be correct in the .OBJ file to begin with, when we create the vertex and texture coordinate lists for each triangle…the winding order will stay correct (kind of obvious isn’t it…but still worth stating…)

OK…so no actual code THIS post, but we are getting there. The next entry will discuss the .SU3 format in a little more concrete detail and will highlight some of the technical issues that we have run into along the way.  Should make for interesting reading…so stay tuned!

SUper Easy to Use 3D Engine (Su3De) – Project Start

Suede 3D Engine

So, I have a need for a VERY simple to use 3D engine for embedded systems and I have decided, after months of vacillating on the issue, to write one. It will be Open Source and the pieces will be published here as well as Source Forge. The engine will sit on top of three 3D architectures initially. OpenGL ES 1.1, OpenGL ES 2.0 and the Fujitsu V03 graphics access library for the Fujitsu Jade “MB86R01″ SoC. It will be developed entirely in ANSI ‘C’ and the goal is to make it abstract enough that it can move to other platforms like Direct3D with ease – but we will see.

First, the name. Every project must have a name. This one is “Su3De” which is an extremely FORCED acronym based on the phrase “Super Easy to Use 3D Engine”. It will, of course, be pronounced “Suede” and I will not use a cow for a logo…although cool cow textures might be sprinkled throughout some of the code samples…just because.  Who wouldn’t love a cow textured tea pot? Don’t judge.

What will make this 3D engine “easy to use”? The API. The plan is to make it as simple as possible. This means a lot of work will be done underneath the API to simplify things. Most of the work will be focused on two main categories.

Loading Objects
Transforming Objects

The plan is to have simple and obvious API calls like Load3DObject(), Rotate3DObject(), Translate3DObject(), Scale3DObject(), etc. Other API functions will be related to things like render contexts and housekeeping.

One of the “tricks” in developing Su3De is going to be in compositing 2D and 3D images together to form a scene. The goal is to do this efficiently and determine a way to do it so that you aren’t rendering the entire scene for every frame. I plan to rethink the way 3D engines work and will likely be bucking convention in several key areas – especially in the area of “Z” ordering – which is the “depth” component of the objects that are being rendered.

Initially the 3D object file format that will be supported by Su3De will be .OBJ files. After that, we will see where it goes. I also plan to support 2D file formats starting with .PNG – both for 2D “objects” as well as 3D object textures. 2D objects will be loaded and rendered as two polygons forming a square with the .PNG as the texture map.

There are many features in the Fujitsu V03 graphics access library that I will want to take advantage of, like using live video as a texture and the layering features of the display controller. These features are extremely useful – but aren’t present in the standard OpenGL APIs…so I will have to balance these somehow.

At any rate, welcome aboard. I hope you find the project interesting. Feel free to comment and tell me what you are thinking as I move forward. It is likely that I will barge forward and run straight into a brick wall and have to back up and change course from time to time, so be prepared for that. It should be fun… See you in Su3De! First “coding” post should be next week sometime. I am a big fan of the Processing Environment and will be using it to “prototype” the code and the initial APIs. Please download it and follow along! See you next week!!!!

Hi! Welcome to my little piece of the Net

Hello. My name is Rick Tewell and I am the Director of Engineering for Fujitsu Semiconductor America. My goal with this site is to write about all things “embedded engineering”…things like hardware design, software development, 2D & 3D graphics, GUI / HMI design, etc. I plan to also share things that I have found on the Net that I find interesting (and hope you do to) relative to all that stuff.

So, I often get asked by people – “How did you get involved with the type of engineering you do?” So, if you have a few minutes, go grab yourself and cup of coffee or tea and let me tell you a story. It is my first “real world” engineering project…and looking back on it, it was pretty interesting.

The date is sometime in 1984. The IBM PC was still fairly new and the XT had just arrived on the scene. For some reason, my geeky tech buddies and I found this computer called the Sanyo 550 in Byte magazine and went out and bought one. Probably because it was an inexpensive IBM PC “clone” and we didn’t have much money. It turned out that it was a “floppy disk only” machine. By that time, however, you could plug a hard disk controller and hard disk into the IBM PC/XT…in fact several companies were selling the controller and hard drive combos. So, we bought a “kit”. It was a whopping 10 Megabytes and was wicked expensive, but it was the absolutely coolest thing in the world. As an aside, the company making the hard drives was named “Rodime.”

Sanyo 550 – IBM PC Clone

Much to our dismay, we found out that you couldn’t plug a hard drive controller into the our brand new Sanyo 550! It just wasn’t possible. Why you ask? Because to our shock and horror…we discovered that there were no standard PC card slots in the machine – remember the old 8-bit ISA connector?

Original IBM PC insides

Original 8-bit PC Card Slot

Well…it turns out that Sanyo thought it might be nifty to not actually USE that connector in their PC clone, but rather use a dual row pin header instead. Most likely for cost reasons. Dual row pin headers are CHEAP.

Good ole’ dual row pin header

Now…we had to plug the hard disk controller below somehow into that dual row pin header. Here we are, a couple of 19 and 20 year old engineering students facing our first real world engineering challenge.

Western Digital Hard Disk Controller

The answer was obvious…we needed an adapter of some sort. Something that would plug into the dual row header and have a PC bus slot connector on the other side. Either that, or solder 64 wires from the dual row pin header connector to the card edge connector of the hard disk controller. Don’t think that we didn’t actually consider that…because we did.

We contacted a company that specialized in connectors and ordered what we needed as a “prototype”. Much to our surprise, the company flew from their location in Illinois to Nashville, Tennessee and drove out to our “office” with the prototypes. Well…they were surprised as well. A couple of kids basically in a garage. We were working in a “shop” connected to an office complex…so we, at least, had that. I could all but see the deflated looks on their faces when they realized that we weren’t some big company working on the next great thing for the PC world.

The connectors worked great (although they did sit in the Sanyo 550 kind of awkwardly). Our next great surprise came when we found out that the darn firmware on the Western Digital disk controller was pretty reliant on DMA and IRQs. Funny thing though, the Sanyo 550 didn’t have a DMA (Intel 8237) or IRQ (Intel 8259) controller. Go figure. That means that simply put, there was NO way, even though it was now electrically connected that the Sanyo 550 that it was going to work with that hard disk controller. If we could FIX this problem somehow, then that would be a GREAT market and the start of a great little company. Sell disk controllers and hard drives to the blossoming PC clone market! We would be millionaires within the year!!!! Then, reality set in.

You have to understand, that at that time, we had NO idea what a 8237 or 8259 actually was. All we knew was that the hard disk controller was electrically connected to the Sanyo 550 and nothing was happening. We saw the pretty little disk controller firmware message and then nothing…not even a blinking cursor. So, we called Sanyo and Western Digital. We finally got through to some folks at Sanyo who kindly sent us their schematics while the folks at Western Digital asked a lot of fresh questions about who the heck was calling them and why were we bothering them. After reviewing the Sanyo 5500 schematics and referencing the connector, we determined that there was a problem. A couple of key components were missing (yes…the DMA and IRQ controllers) from the Sanyo 550 – in fact the lines were labeled “no connects” on Sanyo’s dual row pin header disaster of a PC expansion slot thing. We determined this by cross referencing the FANTASTIC IBM PC/XT documentation that you were able to get at that time…complete with schematics and even FULL BIOS SOURCE CODE!!!! in “when times were simpler” 8088 assembler. It was a purple book (which I still own) and is still a whole lot of awesome geeky goodness.

The AWESOME PC Technical Reference Manual

So, now all we needed to do was to get the “source code” to the Western Digital Hard Drive Controller’s ROM BIOS. This code was programmed into an EPROM and installed on the hard disk controller board. So, now we needed some MORE things. We needed the source code from Western Digital. We needed some blank EPROMs, some tool to program them, and as it turned out an ultraviolet erase thing so we could erase and reprogram the EPROMs. Oh…we also needed a tool to pull the EPROM out of the board. I tried to do it with a pocket knife and the thing popped loose from the board and jumped deep into my finger…VERY painful. We had to order a new hard drive controller after that incident.

Western Digital final provided us the source code – a very nice guy who worked for Western Digital at the time named Jerry Little, accommodated us. We agreed to give Western Digital back the changes we made to their code in return for them giving it to us in the first place. That is when we found that we needed even MORE things, like Microsoft’s Macro Assembler. The source code was written in 8088 assembler. To our amazement, Microsoft’s Macro Assembler and Linker was actually provided from Sanyo with MS-DOS! Can you believe it? The Macro Assembler, Linker and even a Debugger (conveniently named Debug) came with the OS!

Sanyo 550 MS-DOS and included software

After a short time of work, we modified the Western Digital hard disk controller’s firmware to support polled operation (to get around the lack of IRQ support) and programmed I/O instead of DMA suppport. The hard drive controller started working! We could go into the firmware’s menu system and low level format the hard drive (required in those days) and build the bad block table! We were ECSTATIC! The only problem was that the version of MS-DOS from Sanyo had NO hard drive support at all. It had NO IDEA how to deal with a hard drive. Obviously, we were going to have to modify the operating system code to make this work. At this point, one might wonder “didn’t you just want to give up?” Amazingly enough, the thought never crossed our minds. We called Sanyo and asked them for the source code to MS-DOS. I guess enough years has now passed and the legal risk is gone…but Sanyo actually sent us the source code to their version of MS-DOS. Can you believe it?

In those days, MS-DOS was comprised of two primary kernel modules. MSDOS.SYS and IO.SYS. IO.SYS was the collection of device drivers that allowed MSDOS.SYS (the actual kernel) to talk to the outside world. In this case, the outside world was mostly communicated to via the BIOS built into the actual computer. IO.SYS would simply translate MSDOS requests into requests for the BIOS. So, the device driver that would support a hard drive simply wasn’t present inside of IO.SYS. We then thought about modifying the floppy disk driver to control the hard drive…that should be easy, right?

MS-DOS architecture

When we went to compile IO.SYS, much to our surprise a module called “sysinit” was missing. It just wasn’t there and you couldn’t build IO.SYS without it. We contacted Sanyo and apparently somebody there had come to their senses and they said “we can’t give you that.” To which I replied, “You gave us everything else!” The Sanyo engineer then simply said “we can’t and won’t send you sysinit…sorry” and he pretty much hung up. It was pretty bleak at that point. My partner in this caper suggested that we should just write a device driver and add it to CONFIG.SYS to handle the hard drive. It seemed at this point that this was the only way. We could read and write all day long to the hard drive, we just needed to teach MS-DOS how to do it. We had the floppy disk driver as a reference…how hard could it be? I found a great little book called “Writing MS-DOS Device Drivers” that had JUST been published.

Writing MS-DOS Device Drivers

With this book in hand and the sample device drivers out of IO.SYS from Sanyo, I proceeded to write my very first device driver. I got the device driver completed and working, but we came across another little problem. In order to use the hard drive, it had to be LOGICALLY formatted. In other words we had to write a file system to it so DOS could manage the files. Even though we had a hard drive device driver working, MS-DOS STILL couldn’t see the hard drive. I learned quickly about the File Allocation Table (FAT) file system that Microsoft was using, and I learned about clusters and directory entries and all sorts of things that it never occurred to me at the time I would need to know. We ended up having to actually write a hard disk FORMAT utility since clearly one didn’t come from Sanyo with their version of MS-DOS. I will NEVER forget the day that all of a sudden after ALL we had been through to make a hard drive work on a Sanyo 550, we ended up with a very simple “C:” on the screen. I then copied a file from the floppy to ‘C’ drive and MS-DOS responded with a very polite: “1 file(s) copied.”

I know this is going to sound NUTS…but it was an absolute RUSH. For me, that was my game winning touchdown or my series winning home run. It was amazing. At that moment in time, I knew that whether or not I got paid to do this stuff THIS is what I was going to do. Luckily, they pay people to do this kind of stuff…and since that day in 1984 I have done a LOT of stuff…

Deploying 3D Objects on Embedded Devices – source code

Here is the source code to Cube01 referenced in the article:

[sourcecode language="javascript"]

PImage img;

void setup() {
size(640, 480, P3D);
img = loadImage("cube.png");
noStroke();
}

void draw() {
background(0);
noFill();
translate(width / 2, height / 2, 360);
rotateX(map(mouseY, 0, height, -PI, PI));
rotateY(map(mouseX, 0, width, -PI, PI));
textureMode(NORMALIZED);
beginShape(TRIANGLES);
texture(img);
DrawVertices();
endShape();
}

void DrawVertices() {
// f 1/1 2/2 3/3
vertex(-10.000000, 0.000000, 10.000000, 0.9988, 0.3344); // 1/1
vertex(-10.000000, 0.000000, -10.000000, 0.9988, 0.6648); // 2/2
vertex( 10.000000, 0.000000, -10.000000, 0.6681, 0.6648); // 3/3
// f 3/3 4/4 1/1
vertex(10.000000, 0.000000, -10.000000, 0.6681, 0.6648); // 3/3
vertex(10.000000, 0.000000, 10.000000, 0.6681, 0.3344); // 4/4
vertex(-10.000000, 0.000000, 10.000000, 0.9988, 0.3344); // 1/1
// f 5/5 6/6 7/7
vertex(-10.000000, 20.000000, 10.000000, 0.3359, 0.6668); // 5/5
vertex(10.000000, 20.000000, 10.000000, 0.6663, 0.6668); // 6/6
vertex(10.000000, 20.000000, -10.000000, 0.6663, 0.9992); // 7/7
// f 7/7 8/8 5/5
vertex(10.000000, 20.000000, -10.000000, 0.6663, 0.9992); // 7/7
vertex(-10.000000, 20.000000, -10.000000, 0.3359, 0.9992); // 8/8
vertex(-10.000000, 20.000000, 10.000000, 0.3359, 0.6668); // 5/5
// f 1/9 4/10 6/11
vertex(-10.000000, 0.000000, 10.000000, 0.0007, 0.6666); // 1/9
vertex(10.000000, 0.000000, 10.000000, 0.3347, 0.6666); // 4/10
vertex(10.000000, 20.000000, 10.000000, 0.3347, 0.9992); // 6/11
// f 6/11 5/12 1/9
vertex(10.000000, 20.000000, 10.000000, 0.3347, 0.9992); // 6/11
vertex(-10.000000, 20.000000, 10.000000, 0.0007, 0.9992); // 5/12
vertex(-10.000000, 0.000000, 10.000000, 0.0007, 0.6666); // 1/9
// f 4/13 3/14 7/15
vertex(10.000000, 0.000000, 10.000000, -0.0000, 0.3340); // 4/13
vertex(10.000000, 0.000000, -10.000000, 0.3344, 0.3340); // 3/14
vertex(10.000000, 20.000000, -10.000000, 0.3344, 0.6658); // 7/15
// f 7/15 6/16 4/13
vertex(10.000000, 20.000000, -10.000000, 0.3344, 0.6658); // 7/15
vertex(10.000000, 20.000000, 10.000000, -0.0000, 0.6658); // 6/16
vertex(10.000000, 0.000000, 10.000000, -0.0000, 0.3340); // 4/13
// f 3/17 2/18 8/19
vertex(10.000000, 0.000000, -10.000000, 0.3370, 0.3347); // 3/17
vertex(-10.000000, 0.000000, -10.000000, 0.6652, 0.3347); // 2/18
vertex(-10.000000, 20.000000, -10.000000, 0.6652, 0.6662); // 8/19
// f 8/19 7/20 3/17
vertex(-10.000000, 20.000000, -10.000000, 0.6652, 0.6662); // 8/19
vertex(10.000000, 20.000000, -10.000000, 0.3370, 0.6662); // 7/20
vertex(10.000000, 0.000000, -10.000000, 0.3370, 0.3347); // 3/17
// f 2/21 1/22 5/23
vertex(-10.000000, 0.000000, -10.000000, 0.6681, 0.6679); // 2/21
vertex(-10.000000, 0.000000, 10.000000, 0.9996, 0.6679); // 1/22
vertex(-10.000000, 20.000000, 10.000000, 0.9996, 0.9980); // 5/23
// f 5/23 8/24 2/21
vertex(-10.000000, 20.000000, 10.000000, 0.9996, 0.9980); // 5/23
vertex(-10.000000, 20.000000, -10.000000, 0.6681, 0.9980); // 8/24
vertex(-10.000000, 0.000000, -10.000000, 0.6681, 0.6679); // 2/21
}

[/sourcecode]