Archived

This topic is now archived and is closed to further replies.

How do you convert a bitmap to a set of line segments?

This topic is 5511 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m working on a project for my Computer Graphics class this semester. I''m making a game that uses a Wolf3D style raycast engine. Instead of creating a level editor I''ve decided to create the levels as bitmaps (drawn in the paint program of my choice), and then write a program that scans the bitmaps and coverts the lines and curves in the bitmap into line segments that will represent the walls in the game. The trouble is my search for such an algorithm on Google has come up dry. I have some ideas, but I am also a firm believer in not reinventing the wheel, at least not without seeing what''s already been done first. Has anyone done this or something like it before, or do you know of any resources I could refer to, or do you just have a good idea. I''ve already got the code to crawl along the walls pixel-by-pixel in the bitmap. Just to make sure I''ve satisfied the "homework post" requirements: I''m going to, and want to do the entire project myself; I''m just stuck on an approach to take in a single portion of the project. I''m not even looking for code, just an algorithm.

Share this post


Link to post
Share on other sites
Thanks. Sometimes the hardest part of searching for information is knowing the terms!

By the way I''ve come up with an algo that works nicely (I thought of it just after I posted, of course...). If anyone''s interested, here goes:

Walk recursively through adjacent pixels. Anchor a point at your starting point (call it StartVertex), and then for each new pixel traverse the line from StarVertex to CurrentVertex and see how many of the desired pixels you hit. If the number of misses exceeds a tolerance setting, back up a pixel, anchor the StartVertex there, and create a line from the old StartVertex to the new StartVertex. There are a few more details to take care of but this is the general idea, and it does work (I coded it this morning). Thanks for the help, the project''s moving along nicely.

Share this post


Link to post
Share on other sites
I HIGHLY advise you to make a map editor instead. You are adventuring yourself in pretty complicated stuff. More complicated than programming a stupid editor and even more complicated than the engine itself, beleive me.

Some, people are making their Dr. thesis on image recognition.

Are you really making your engine like Wolf3D? Because all wolf3d walls are made with boxes, not vectors. Converting a bitmap to a set of boxes is easy, simply take each pixel and make a box with it. If you look carefully at wolf3d you will notice there are no 45 degrees walls... they are all right angles... boxes. You will also notice that all walls are the same height.

______________________________
Oooh, you found the horadric cube!

Share this post


Link to post
Share on other sites
Okay, I guess I fibbed a little. What I meant was that I will be raycasting and that I won''t be drawing the tops of walls (and all walls are uniform height). However I do (or did) intend to allow walls at arbitrary angles to each other, meaning curved walls are definitely an option. I realize this is not simple, but even if I don''t do this as my project, I do want to do it for fun. As for the complexity of the image converter, so far it hasn''t been bad at all. I''ve already got it 80% complete (in 3 or 4 days). The image files are bitmaps with walls drawn in a paint program as lines, circles, boxes and other such line-defined curves. All walls are a single pixel thick, so a line in the bitmap of a single pixel thickness is detected as a wall. There is a reserved color that is off limits for walls (it''s white right now <255,255,255>); any other color can be a wall, and the colors can be associated with textures and other properties. But like I said, the image detection/conversion has actually been pretty much a piece of cake, although getting it completely perfect is not. The reason I don''t want to build my own editor is that the features I would want in the editor are the same features found in any popular paint program. Since this software already exists, why build my own? The conversion program is not nearly as complicated as designing my own paint program featured editor.

Of course if I just used squares for the walls this wouldn''t be an issue... oh well, I guess I''m just a glutten for punishment!

Share this post


Link to post
Share on other sites
I must admit that with those restrictions, the problem is somewhat simplified And since you won''t be distributing the engine (I guess) this is enough for personnal uses.

Keep up the good work!

______________________________
Oooh, you found the horadric cube!

Share this post


Link to post
Share on other sites
Thanks. No I probably won''t be distributing the engine (I doubt it will turn out that good, and besides it''s going to be several steps behind the tech. curve now...), but it should be fun. I read LaMothe''s Tricks of the Game Programming Gurus among others and I''ve always wanted to make a ray-traced 3D game, so I figure this is as good a time as any, even if the technology is a bit dated.

Share this post


Link to post
Share on other sites