algorithm to reduce the number of vertices/triangl

Community Forums/General Help/algorithm to reduce the number of vertices/triangl

RemiD

(Posted 2015) [#1]

Hello,

Let's say that i have a 1000x1000terrain with heights each 1x1z, and i want to reduce the number of vertices/triangles to the minimum possible but at the same time keep the important reliefs of the terrain.

This is not ROAM because i don't care to have more details near the camera.

This is more like creating a low details version of a high details terrain.

The result should allow me to create a mesh.

Any idea of an existing algorithm to achieve that ?

Thanks,

BlitzSupport

(Posted 2015) [#2]

There's this one... sure there's another one somewhere...

http://www.blitzbasic.com/codearcs/codearcs.php?code=1285

RemiD

(Posted 2015) [#3]

Thanks, i will take a look.

Matty

(Posted 2015) [#4]

One way is to split it into patches. Do an analysis of the variation in y in each area and if there is a lot of variation split into a smaller higher resolution patch....if there is a small amount split into a low resolution area.

A simple statistical analysis of change in height between each point in a sample area would give a decent metric. Use change in height between adjacent nodes not raw height.

It is a minimisation problem...maximise quality (set error or difference between original at minimum for a given number of triangles)

Edit:with constraints that edges of patches line up.

Edit:least squares regression is the statistical method you want to use but in 2 dimensions not 1.

Matty

(Posted 2015) [#5]

You want the sum of the absolute value of the second derivative for each area given by y (xn+2) - 2y (xn+1) + y (xn) where i would like to use subscripts for the n .. ie the nth plus 2 x coordinate.

RemiD

(Posted 2015) [#6]

Thanks, not sure i understand what you mean, i will reread later.

Matty

(Posted 2015) [#7]

Take your 1000x1000 area.

Split into smaller subsections (in memory as a virtual representation such as a series of heightmaps)

Measure the variation in height in each subsection.

If the variation is large (ie lots of up and down bits) use a high resolution mesh.

If the variation is low (ie fairly flat) use a lower resolution mesh.

Thats the basic idea.

Imagine replacing your 1000x1000 heightmap by multiple smaller heightmaps of differing resolution depending upon the amount of 'jitter' for want of a better term.

I might do a b3d example later.

Matty

(Posted 2015) [#8]

Example:

note fully tested but it does an okay job as a first attempt...

Graphics 512,512,0,2
TFormFilter False
image = LoadImage("australia.jpg")
SetBuffer ImageBuffer(image)
ResizeImage image,1024,1024
maxvariation = 0
Dim variation#(64)
Dim imagen(64)
For i = 0 To 7
For j = 0 To 7
	sx = i*128
	sy = j*128
	fx = sx + 127
	fy = sy + 127
	;;;calculate the variation in the position....
	imagen(i+j*8) = CreateImage(128,128)
	CopyRect sx,sy,128,128,0,0,ImageBuffer(image),ImageBuffer(imagen(i+j*8))
	For x = sx+2 To fx
	For y = sy+2 To fy
		rgb = ReadPixel(x,y) And 255
		rgbx0 = ReadPixel(x-1,y) And 255
		rgby0 = ReadPixel(x,y-1) And 255
		rgbx1 = ReadPixel(x-2,y) And 255
		rgby1 = ReadPixel(x,y-2) And 255
		variation(i+j*8) = variation(i+j*8) + Abs(rgb + rgbx1 - rgbx0*2) + Abs(rgb + rgby1 - rgby0*2)
	Next
	Next
	If(variation(i+j*8)>maxvariation) Then maxvariation = variation(i+j*8)
Next
Next
Cls
SetBuffer BackBuffer()
For i = 0 To 63
	varies# = variation(i) / maxvariation
	div = 1+7*(varies^0.25) ;must be integer
	If(div>7) Then div = 7
	If(div<1) Then div = 1
	ResizeImage imagen(i),128 / (2^(7-div)),128 / (2^(7-div))
	SaveImage imagen(i),"imagen"+i+".bmp"
Next

For i = 0 To 7
	For j = 0 To 7
		ResizeImage imagen(i+j*8),128,128
		CopyRect 0,0,128,128,i*128,j*128,ImageBuffer(imagen(i+j*8)),ImageBuffer(image)
	Next
Next	
SaveImage image,"opt.bmp"
Notify "end"
End

Longwinded explanation to follow (don't read if you don't want to)....

Take an 1024x1024 heightmap.
Break it into 128x128 cells. (8x8)
Work out the variation in each cell by summing the second derivative in each direction.
Depending on the amount of variation (out of the maximum variation) resize the heightmap in that cell by a factor of 2^value where value is between 0 and 7.
Save the resulting image as a lower res heightmap for that region.
As a comparison the final heightmap(upon rescaling the images back up) is saved as opt.bmp...this is just to see the difference between the original and the optimised.

Matty

(Posted 2015) [#9]

Play around with the exponent in the varies^0.25....make it closer to 1 to make it more sensitive.

RemiD

(Posted 2015) [#10]

@Matty>>I will take a look, thanks.