Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Professional Discussion / Building Room Geometry from Grid

Author
Message
Jeff032
18
Years of Service
User Offline
Joined: 13th Aug 2007
Location:
Posted: 31st Mar 2010 22:31
Link
I'm looking for a way to build room geometry from a three dimensional array of booleans. (The rooms are grid based) Each boolean represents whether or not there is a block at that position in the room.

Creating 12 triangles for every block would be inefficient. I think I have an idea about how to combine at least some of the faces, but I'm wondering if anyone has any thoughts or if this sort of thing has been done before (and where to find explanations of how to do it).

(I'm also sort of wondering if I'd need some sort of spacial partitioning system in order to be able to draw the rooms at a decent speed. BSP looks complicated to calculate and I'm not sure I could use it anyway since a room could contain multiple levels. Any thoughts on this as well?)

Thanks.

Back to top
Profile PM
Hawkblood
16
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 31st Mar 2010 22:39
Link
Do you not want to use [make object cube]? That would be the easiest method. Another way would be to find the longest string of 1's, make a box to fill that area and turn those 1's into 0's. Wash, rinse, repeat. The last method would take longer, I think.

The fastest code is the code never written.
Back to top
Profile PM Email Website
Jeff032
18
Years of Service
User Offline
Joined: 13th Aug 2007
Location:
Posted: 1st Apr 2010 03:40 Edited at: 1st Apr 2010 03:41
Link
Correct, I do not want to use make object cube. I would rather create the world as one object (using memblocks). So I suppose I need some algorithm to find a way to build the world with as few triangles as possible. I'm not sure such a thing even exists.

All I've thought of so far is to take one side of a cube, and then see how far up/down the x axis I can extend it, and then how far up/down the y axis. I'm not sure this would work very well.

So ideally, given a region such as the red one in the image below, I want to find the least number of triangles needed to represent the shape.



Back to top
Profile PM
Jeff032
18
Years of Service
User Offline
Joined: 13th Aug 2007
Location:
Posted: 1st Apr 2010 03:49 Edited at: 1st Apr 2010 03:50
Link
The technique I mentioned above would create quads like this (started from the bottom). It's an improvement over 1 quad for every square, but it could be better. It also seems possible that the best solution might not be made out of quads, but out of some triangle fans or something else instead.



Back to top
Profile PM
Mnemonix
23
Years of Service
User Offline
Joined: 2nd Dec 2002
Location: Skaro
Posted: 1st Apr 2010 11:46
Link
Incidentally, why have you chose booleans to represent the level data. I understand it is the most efficient way for the wall/space thing, but wouldn't it be a good idea to use a byte so you can fit in more types of block?

Your signature has been erased by a mod because it's larger than 600x120
Back to top
Profile PM Email Website
Jeff032
18
Years of Service
User Offline
Joined: 13th Aug 2007
Location:
Posted: 1st Apr 2010 15:46
Link
Quote: "Incidentally, why have you chose booleans to represent the level data. I understand it is the most efficient way for the wall/space thing, but wouldn't it be a good idea to use a byte so you can fit in more types of block?"


It's entirely possible that I will be using bytes. I haven't started writing any code, and I just picked that to simplify the question.


I've been reading a paper on polygon triangulation by ear clipping. It seemed like it might work at first (even though it gets a bit more complicated when the polygons have holes in them, which is a possibility), but it turns out that triangulation of a polygon with n vertices always creates (n-2) triangles. I haven't thought of a case where this creates less triangles than my method above.

Still no ideas?

Thanks.

Back to top
Profile PM
Hawkblood
16
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 1st Apr 2010 16:40
Link
You would have to know a lot about making meshes. There's not only the vertices, but the order in which each face is made. For normal faces, you need to order the vertices counter clockwise in your index data. If you understand that, you are more than half way there.

Use your array to determine "block" size. Start with the first "1" in your loop and any "1" touching it branches off to it's adjacent 1's and so on... Each "1" that is inside the "box" will be taken into account and turned into a "0". Once the "box" can go no further, you take the 3 dimensions and make a box (or you can just store that info in a memblock or whatever). Repeat that process until there are no more 1's.

Once there are no more 1's, you can make a single mesh using the data you gathered earlier. This may make what you are wanting to make, but it's not the easiest to do.... Have fun!

The fastest code is the code never written.
Back to top
Profile PM Email Website
Back to top

Login to post a reply

Server time is: 2026-07-26 21:11:45
Your offset time is: 2026-07-26 21:11:45