logic to replace triangles which areadjacent/havethesamenormal by less triangles

Community Forums/General Help/logic to replace triangles which areadjacent/havethesamenormal by less triangles

RemiD

(Posted 2017) [#1]

Hello,

I am looking for the logic to replace triangles which are adjacent / have the same normal by less triangles.

For example i have a mesh (terrain) like this :

and the areas highlighted in yellow/pink are made of triangles which are adjacent and have the same normal, and there is no need to have so many triangles to have this level of details... So i want to find a logic to replace the unnecessary triangles by less triangle.

This is because linepick takes 11ms on such a high details terrain (20 000tris) and i need to pick the terrain several times each frame (for collisions detection)...

My current workaround is to have a transparent (alpha 0.0) plane, at the level of the ground (in yellow) where the characters can go, and pick this plane instead of the terrain, works well, very fast, but this does not allow me to detect the walls), so iam curious if there is a way to reduce the amount of triangles in a mesh by removing the triangles which are adjacent / have the same normal...

Don't need code, just the logic.
(I already know the code by JohnJ, but this alters the shape of the mesh too much, i just want to remove/replace the triangles which will not alter the shape.)

Thanks,

Derron

(Posted 2017) [#2]

Without checking for more simple approaches:

you want to "collapse" tris into a single bigger one if they do not have vertices differing in the third axis ?

 _____
|\ |\ |
|_\|_\|
|\ |\ |
|_\|_\|

becomes
 _____
|\    |
| \   |
|   \ |
|____\|

?

The problem is, that this reduction does not work with triangles aligned "non-mirrored". With Quads it works, as you can use "diamond shapes" and so on to reduce the amount of vertices or edges.

Let me explain what I mean with another sample. This time I marked every vertex as "o".

o--o--o--o--o
|\ |\ |\ |\ |
| \| \| \| \|
o--o--o--o--o
|\ |\ |\ |\ |
| \| \| \| \|
o--o--o--o--o
|\ |\ |\ |\ |
| \| \| \| \|
o--o--o--o--o

becomes
o--o--o--o--o
|\ |\ |\ |\ |
| \| \| \| \|
|  o--o--o--o
|   \ |\ |\ |
|    \| \| \|
|     o--o--o
|      \ |\ |
|       \| \|
o--------o--o

See the problem? The big one isn't a triangle but a polygon with 5 vertices.

BUT ... your vertices are layed out differently - does it help? nope.

o--o--o--o--o
|\ | /|\ | /|
| \|/ | \|/ |
o--o--o--o--o
| /|\ | /|\ |
|/ | \|/ | \|
o--o--o--o--o
|\ | /|\ | /|
| \|/ | \|/ |
o--o--o--o--o

becomes
o--o--o--o--o
|\    |    /|
| \   |   / |
o--o  o  o--o
| /|\ | /|\ |
|/ | \|/ | \|
o--o--o--o--o
|\ | /|\ | /|
| \|/ | \|/ |
o--o--o--o--o

Still polygons.

You could only convert planar tris to quads, but I do not know if it helps.

This approach only works for triangle-layouts containing "triangles in triangles" without further edges.

o---o---o
|  / \  |
| /   \ |
|/     \|
o-------o
|\\   //|
| \'o'/ |
|  \|/  |
o---o---o

could become
o---o---o
|  / \  |
| /   \ |
|/     \|
o-------o
|\     /|
| \   / |
|  \ /  |
o---o---o

So a simple algorithm "joining" together adjacent triangles wont be possible. Your best bet is an algorithm which recreates the same "shape" but with a different layout of triangles.

Maybe this is of help:
http://www.melax.com/polychop

But the basic idea is: remove edges if the triangle is coplanar to the neighbouring one (there is no "hill" or "sink" - both share a "plane"). To calculate this, you could use some vector math.

Another possiblility is to split the mesh into multiple parts. So if you find a bigger "planar area" you recreate that with two triangles (or a quad) and in your "detailed mesh" you then cut a hole of that area size.

o--o--o--o--o--o--o
|\ | /|\ | /|\ | /|
| \|/ | \|/ | \|/ |
o--o--o--o--o--o--o
| /|\ | /|\ | /|\ |
|/ | \|/ | \|/ | \|
o--o--o--o--o--o--o
|\ | /|\ | /|\ | /|
| \|/ | \|/ | \|/ |
o--o--o--o--o--o--o
| /|\ | /|\ | /|\ |
|/ | \|/ | \|/ | \|
o--o--o--o--o--o--o

becomes
o--o--o--o--o--o--o
|\ | /|\ | /|\ | /|
| \|/ | \|/ | \|/ |
o--x--o--o--o--o--x
| /|              |
|/ |              |
o--o              o
|\ |              |
| \|              |
o--o              o
| /|              |
|/ |              |
o--x--o--o--o--o--x

The "x" are vertices of the detailed mesh ("o") but overlayed by the 4 vertices needed for the "low-detail"-quad.

Of course things get complicated then with normal mapping ("clipping") and the likes.

bye
Ron

RemiD

(Posted 2017) [#3]

Well, after some thinking, i have decided to try an approach which should work but only for this kind of terrain (where there goal is to remove the triangles which are flat and adjacent)

It is similar to what you (Derron) suggested but i will try to group the more "flat cells" as possible in a square shape or a rectangle shape.

Stevie G

(Posted 2017) [#4]

To speed up the linepicks significantly split your terrain into smaller chunks. So, instead of a one large 100x100 terrain , split this into 5 x 5 (20x20) meshes or suchlike. Linepick will quickly discard most of the terrain meshes via bounding checks.

RemiD

(Posted 2017) [#5]

@Stevie>>good idea, i will try.

GW	(Posted 2017) [#6]

Look at the Lodmesh example from B3d

Kryzon

(Posted 2017) [#7]

Use a pivot with a long and thin EntityBox. Long as in "hundreds of units".
Collisions work with terrains, vide "castle" sample in Blitz3D/Samples/mak/castle/castle.bb, the shots collide with the terrain.

Then when you want to "linepick" the terrain, rotate that pivot along the picking direction (you can use VectorPitch and VectorYaw to get the angles) and move that pivot through enough space to intersect the terrain.
The CollisionX\Y\Z point should be what you want.

Matty

(Posted 2017) [#8]

You don't need a linepick on a regularly spaced mesh like that...you can calculate the height of the terrain simply with a mathematical calculation that takes the x/z coordinate and returns a y height...combine this with linepicks on individual obstacles - ie don't set the terrain mesh to pickable...just calculate the height of the terrain mesh with a bit of mathematics at a coordinate and compare to that.

RemiD

(Posted 2017) [#9]

It would not be that simple with maths because the camerapick/linepick is not a vector from top to down but rather a vector thrown from an isometric view.

The best approach i can think of is combining a low details mesh (after a polygons reduction of the initial mesh) + splitting the mesh in small parts (like StevieG suggested)

Of course an even better approach would be to create a custom linepick system where the triangles of big meshes would be grouped in small 3dareas (like bounding boxes) and only do the calculations on the triangles which are inside a 3darea which has been crossed by the 3dline.
Maybe later but not for the moment.

Other than that, surprisingly (or not), the rendering of a 20 000tris mesh terrain is faster than of a 5 000tris ROAM terrain when the GPU is better than the CPU and slower when the CPU is better than the GPU...