🔒 Locked

Brainlock

Started by Crispy May 23, 2003 at 2:28 PM 13 replies 700+ views

Original Post

170

May 23, 2003 at 2:28 PM

I''ve done lots of terrain rendering before with no problems whatsoever. Now, however, I need to render small patches, such as this:

T T 0 T T
T T T T T
0 T C T 0
T T T T T
T T 0 T T

where T and C can have varying values (the point here being a chance to demostrate the problem, not to bring a specific sample). When rendering the above patch using quads, it isn''t hard to see that some of them would be non-convex, ergo quads are a no-go. Rendering the patch using tiled trianges, such as this:

 __
| /|
|/_|

won''t make the problem go away though as both regions around the zeros as well as around C require the direction of the trianges to to change. My head can''t break how to render this patch properly and I''m sure this problem has some notorious name (along the lines of Gimbal Lock). Furthermore, I can''t think of the possiblity of a reliable algorithm existing that would be able to tell which way I should draw the triangles for any 4 point region. Further subdividing the quads won''t yield any success either. Regardless, this is done - can anyone provide a link or a phrase to look for in Google? Thanks!

Never do anything that is a waste of time and be prepared to wage long tedious wars over this principle - Michael O''Connor

Extrarius

234

Extrarius

May 23, 2003 at 2:49 PM

Are you looking for ways to make different terrain types blend well, ways to make holes in the terrain, or something else? I'm not sure I understand the problem from your post.

If you are just looking for a way to render it, why not use tiles? Each letter represents one space, and you use one quad for it.

[edited by - Extrarius on May 23, 2003 3:50:33 PM]

Mage2k

May 23, 2003 at 3:00 PM

Why not split every 2x2 section up into a triangle fan with 8 triangles? To build the index list for each fan start with the center vertex, then go around the outside in whatever direction you need (i.e. left- or right-hand system...). Like this:

___ ___
| \ | / |
|__\|/__|
| /|\ |
|_/_|_\_|

Ok, well, that drawing isn't exactly working out, but I think you know what I mean...

[edited by - Mage2k on May 23, 2003 4:01:25 PM]

[edited by - Mage2k on May 23, 2003 4:02:09 PM]

[edited by - Mage2k on May 23, 2003 4:03:43 PM]

Crispy

Author

170

Crispy

May 23, 2003 at 3:03 PM

The letter are height data for vertexes. Think of it as this:

your heightmap looks like this:


T 0 T
T T T

and you start renderin it by taking four verices at a time (each comprising two triangles), like this:


T__0__T
| /| /|
|/_|/_|
T  T  T

to make the final result look right, however, you''d need to render the trinagles as:


T__0__T
|\ | /|
|_\|/_|
T  T  T

resulting in a properly symmetrical depression centered on 0.

the problem is in determining how and when the trianges should be drawn differently.

hope this explains it in more detail - sorry for being too vague in the original post.

Never do anything that is a waste of time and be prepared to wage long tedious wars over this principle - Michael O''Connor

Extrarius

234

Extrarius

May 23, 2003 at 3:36 PM

What might work is to divide each square into 4 triangles like so:

+-----+
|\   /|
| \ / |
|  *  |
| / \ |
|/   \|
+-----+

With the * being located at the average of the 4 verticies. That can still have some problems if the top left and bottom right verticies are high and the other two are low (or vice versa), but for relatively small slope changes it should work(I think).

ironfroggy

May 23, 2003 at 3:44 PM

this wouldnt have to be a problem at all if everyone would agree on a way that a quad should be rendered if it is not planer.

Crispy

Author

170

Crispy

May 23, 2003 at 3:46 PM

Mage2k - see my second post on why it won''t work.

Extrarius: consider this:


A-----B
|\   /|
| \ / |
|  X  |
| / \ |
|/   \|
C-----D

Verices A, C and D are of height 1, vertex B is of height 0. Vertex X would then be of height 0.75, which yields a 25% error and would create a noticable dent in the patch. That''s why I added that further subdividing the quad won''t work in my original post...

Never do anything that is a waste of time and be prepared to wage long tedious wars over this principle - Michael O''Connor

ironfroggy

May 23, 2003 at 3:51 PM

so dont use an average. have the middle coordinate be the midline between two of the corners.

Mage2k

May 23, 2003 at 3:51 PM

Umm... I don''t see how what what you said in your second post will keep what I suggested from working. Use the algorithm I suggested to build a list of triangle fans, not strips.

Crispy

Author

170

Crispy

May 24, 2003 at 4:29 AM

quote:
Original post by ironfroggy
so dont use an average. have the middle coordinate be the midline between two of the corners.

Now the questiob becomes which two corners...

quote:
Original post by Mage2k
Umm... I don''t see how what what you said in your second post will keep what I suggested from working. Use the algorithm I suggested to build a list of triangle fans, not strips.

Sorry - my bad. Nevertheless, triangle fans won''t work either because I''d have to know the height of the middle vertex which I don''t...

Never do anything that is a waste of time and be prepared to wage long tedious wars over this principle - Michael O''Connor

yckx

115

yckx

May 24, 2003 at 4:53 PM

Not sure if you want concave or convex quads, but for

A-B
| |
D-C

you could determine the height difference between A and C, and between B and D, and split the quad along the diagonal with the largest (or smallest) gradient. If you''re wanting a specific terrain that requires a mix, then you''d need a list of some sort to keep track of which quads to render with an AC split, and any quads not in the list would be split along BD.

Does that make any sense?

yckx

Mage2k

May 25, 2003 at 2:38 AM

quote:
Original post by Crispy
Sorry - my bad. Nevertheless, triangle fans won''t work either because I''d have to know the height of the middle vertex which I don''t...

Never do anything that is a waste of time and be prepared to wage long tedious wars over this principle - Michael O''Connor

Ok, now I''m confused.. Why don''t you? You have the vertexes for the quads, right? I must be missing something...

Dreamforger

May 25, 2003 at 4:09 AM

quote:
Original post by ironfroggy
so dont use an average. have the middle coordinate be the midline between two of the corners.

Original post by Crispy
Now the questiob becomes which two corners...

Are you guys for real?

center = average of average of any two = average of all
X = ((A+B)/2 + (C+D)/2) /2 = (A+B+C+D) /2

note that my ABCD need not coincide with the ABCD from above

What you do there is called bilinear interpolation. Maybe you want bicubic or bi-cosine interpolation but that doesn''t change the value of X, as long as you don''t use stuff like hermite splines.

Trouble is that you have approximate as the ''correct'' value of X is not known. The proposal of Extrarius is suited to the problem

---------------------------
I may be getting older, but I refuse to grow up

Pipo DeClown

156

Pipo DeClown

May 25, 2003 at 6:23 AM

|/_\|/_\|
|\_/|\_/|
\___()___/

.lick

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.