OptimizeMesh() ... ?

Is there a OptimizeMesh function somewhere? I have seen a Polygon Reduction in the archives. That's cool, but not exactly what I need here. OptimizeMesh will try to reduce the polycount without to alter the shape. This works especially with meshes that contain unneccessary fragmentation of planes.

I found this references to a OptimizeMesh function:
http://www.blitzbasic.com/codearcs/codearcs_bb/250.bb

Thanks. This is welding the mesh. I meant searching for an alternative set of triangles for the same shape. Like when you have a cylinder cap. In 3dsMax for example the cap will be made of as many tris as there are segments in the cylinder. Then when you choose the "Optimize" modifier, the cap will be made of less triangles, where their axis point is no longer the center of the cylinder, but one of the segment edges. Ehrm, hard to explain for me. Imagine the unoptimized cap is looking like a 2D sun with lots of rays. The optimized cap looks more like a quarter of such a sun, where all rays start in one corner and go across the entire cap to every segment edge.

jfk - I know exactly what you mean. I've never seen anything in Blitz to do this. If someone has made a generic poly 'filler' you could adapt it by searching for attached co-planar triangles, and using the resulting poly outline.

What a nice idea. Maybe you could add a parameter that controls the maximum difference between the normals of two triangles that should be treated as coplanar.

I read an article a few years ago on mesh optimization. It presenteda method for dynamically tessalating geometry, that handled LOD similar to what you are looking for. Rather than simply descimate the geometry it calculated the best representation of a geometric surface using the fewest triangles.

Check this link, it might get you going in the right direction.

http://research.microsoft.com/~hoppe/#meshopt

Allan

Some modellers I've used have a 'reduce triangles' function, but they are never that clever and always leave holes in the model.
I guess it would be a nightmare to code.

I would just use max and optimise your models pre-implementation, unless you want to do it dynamically or are creating a program specifically for it.

What i'd probubly do, is check a poly, then look at all adjacent polies and if it has the same or similar normal, then add the vertecies of that tri to a list, and after finding all coplanar tris, use some kind of algo to delete all points in the center of the plane and then connect the remaining vertecies accordingly.

If your doing it for performance reasons it is far far more efficent to create a high res model in your modelling package and then create 1-2 lower LOD models using the relevant tools and hide/unhide the relevant models in game, than trying to generate appropriate LOD on the fly.

From playing with some asteroid code, I found I only needed 2 LODs 1 high-res approx 4K polys and one low res approx 200 poly and I could have several thousand in use with little slow down, I tried a 2D sprite for very distant asteroids and didn't get any speed boost.

This is a translated java program written by Ian Garton. It triangulates a closed, simple polygon.

;/*-------------------------------------------------------------------*/
;/*  BruteForceEarCut.java                                            */
;/*      This file contains the class needed for the implementation   */
;/*      of ear cutting for a simple polygon.                         */
;/*                                                                   */
;/*- Modification History---------------------------------------------*/
;/*  When:       Who:          Comments:                              */
;/*                                                                   */
;/*  97.12.09    Ian Garton    Final Implementation                   */
;/*-------------------------------------------------------------------*/

Type Triangle
	Field v0x#
	Field v0y#
	Field v1x#
	Field v1y#
	Field v2x#
	Field v2y#
End Type

Global 		npoints
Global		earCounter
Global		concaveCount
Dim			xpoints#	(1000), ypoints#	(1000)
Dim			xpointsTemp#(1000), ypointstemp#(1000)
Dim			ptType		(1000)

Dim ex#(4), ey#(4)


Graphics 800, 600, 0, 3
SetBuffer BackBuffer()

Dim xpoints(1000)
Dim ypoints(1000)
npoints = 0


Repeat

Cls

	;N
	If KeyHit(49) Then
		Delete Each triangle
		tel = 0
		npoints = 0
		ok = True
		done = False
	End If

	If MouseHit(1) Then
		xpoints(npoints) = MouseX()
		ypoints(npoints) = MouseY()
		npoints = npoints + 1
		xpoints(npoints) = xpoints(0)
		ypoints(npoints) = ypoints(0)
		ok = True
	End If
	
	tl = 0
	If done Then
	For ti.triangle = Each triangle
			filltri ti\v0x, ti\v0y, ti\v1x, ti\v1y, ti\v2x, ti\v2y, 0, 0, 255, 255, 255, 0
			Line ti\v2x, ti\v2y, ti\v0x, ti\v0y
			tl = tl + 1
	Next

	Else
	
	tel = npoints
	mtst = False
	For i = 0 To tel - 1
		Color 0, 255, 0
		Oval xpoints(i) - 5, ypoints(i) - 5, 10, 10
		Text xpoints(i), ypoints(i) - 15, i, True, True

		tst = False
		For j = 0 To tel - 1
			If j <> i Then tst = tst Or Kruisen(xpoints(i), ypoints(i), xpoints(i + 1), ypoints(i + 1), xpoints(j), ypoints(j), xpoints(j + 1), ypoints(j + 1))
		Next
					
		If tst Then Color 255, 0, 0 Else Color 0, 0, 255
		mtst = mtst Or tst
		Line xpoints(i), ypoints(i), xpoints(i + 1), ypoints(i + 1)
	Next
	
	End If

	If MouseHit(2) And (Not mtst) Then 
		If polygonClockwise() Then 
				For i = 0 To npoints - 1
					xpointstemp(i) = xpoints((npoints - 1) - i)
					ypointstemp(i) = ypoints((npoints - 1) - i)
					;pttpye
				Next

				For i = 0 To npoints - 1
					xpoints(i) = xpointstemp(i)
					ypoints(i) = ypointstemp(i)
				Next
				
			End If


		If ok Then
			npoints = npoints + 1
			xpoints(npoints - 1) = xpoints(0)
			ypoints(npoints - 1) = ypoints(0)
			ok = False
		End If
		
	on = npoints
	For i = 0 To on
		action "cut"
	Next
		
	done = True
	End If
	
	Text 0, 0,  "Use LMB to draw 'simple' polygon"
	Text 0, 20, "Lines that are intersecting are marked Red"
	Text 0, 40, "If no lines are intersecting, use RMB to triangulate"
	Text 0, 60, "This code was written by Ian Garton"

	
	Flip

Until KeyHit(1)

End


;    /*
;     * main:  This is to run outside of Netscape, using AppletFrame.
;     */
;    public static void main (String args())
;    {
;	runsInBrowser = False;
;	AppletFrame.startApplet("BruteForceEarCut",
;				"Brute Force Ear Cutting",
;				args);
;    }


;    /* finishNotify:  When user enters final point, variables are
;     *                initialized and the Cut Ear button is made
;     *                active.
;     */
Function FinishNotify()
		
	earCounter = 0
		
End Function


;    /* action:  Performs actions according to button user activates.
;     */	
Function action(actie$)

	If actie$ = "clear" Then
	
	    earCounter = 0
		Cls
		
	End If
	
	If actie$ = "cut" Then
	    If (npoints > 3) Then
	        classifyPoints
	        doCutEar
	        ;repaint
	    End If
	End If
		
End Function


;    /* paint:  Displays modified polygon
;     */
;Function repaint()
;
;    public void paint(Canvas caller, Graphics g)
;    {
;	if (transformedPoly == null) return;
;
;	for (int i = 0; i < earCounter; i++) {
;	    g.setColor(Color.yellow);
;	    g.fillPolygon(earPoly(i));
;	    g.setColor(Color.pink);
;	    g.drawPolygon(earPoly(i));
;	}
;
;	if (npoints > 3) {
;	    g.setColor(Color.black);
;	    g.drawPolygon(transformedPoly);
;        }
;    }


;    /* polygonClockwise:  Returns true if user inputted polygon in 
;     *                    clockwise order, false if counterclockwise.  
;     *                    The Law of Cosines is used to determine the
;     *                    angle.
;     */
Function polygonClockwise2()
    
	Local aa#, bb#, cc#, b#, c#, theta#
	Local convex_turn#
	Local convex_sum# = 0

	For i = 0 To npoints - 2
	
	    aa = ((xpoints(i+2) - xpoints(i)) * (xpoints(i+2) - xpoints(i))) + ((-ypoints(i+2) + ypoints(i)) * (-ypoints(i+2) + ypoints(i)))
	    
	    bb = ((xpoints(i+1) - xpoints(i)) * (xpoints(i+1) - xpoints(i))) + ((-ypoints(i+1) + ypoints(i)) * (-ypoints(i+1) + ypoints(i)))
	    
	    cc = ((xpoints(i+2) - xpoints(i+1)) * (xpoints(i+2) - xpoints(i+1))) + ((-ypoints(i+2) + ypoints(i+1)) * (-ypoints(i+2) + ypoints(i+1)))
	
	    b = Sqr(bb)
	    c = Sqr(cc)
	    theta = ACos((bb + cc - aa) / (2 * b * c))

	    If (convex(xpoints(i), ypoints(i),xpoints(i+1), ypoints(i+1),xpoints(i+2), ypoints(i+2))) Then
			convex_turn = Pi - theta
			convex_sum = convex_sum + convex_turn	
	    Else 
		convex_sum = convex_sum - (Pi - theta)
	    End If
	
	Next
	
	aa = ((xpoints(1) - xpoints(npoints-2)) * (xpoints(1) - xpoints(npoints-2))) + ((-ypoints(1) + ypoints(npoints-2)) * (-ypoints(1) + ypoints(npoints-2)))
	    
	bb = ((xpoints(0) - xpoints(npoints-2)) * (xpoints(0) - xpoints(npoints-2))) + ((-ypoints(0) + ypoints(npoints-2)) * (-ypoints(0) + ypoints(npoints-2)))
	    
	cc = ((xpoints(1) - xpoints(0)) * (xpoints(1) - xpoints(0))) + ((-ypoints(1) + ypoints(0)) * (-ypoints(1) + ypoints(0)));
	
	b = Sqr(bb)
	c = Sqr(cc)
	theta = ACos((bb + cc - aa) / (2 * b * c))
	
	If (convex(xpoints(npoints-2), ypoints(npoints-2), xpoints(0), ypoints(0), xpoints(1), ypoints(1))) Then
	    convex_turn = Pi - theta
	    convex_sum = convex_sum + convex_turn
	Else
	    convex_sum = convex_sum - (Pi - theta)
	End If

	If (convex_sum >= (2 * 3.14159)) Then Return True Else Return False
	
End Function

;    /* classifyPoints:  Classifies points as "convex" or "concave".  
;     *                  Convex points are represented as a "1" in the
;     *                  ptType array; concave points are represented as a
;     *                  "-1" in the array.
;     */
Function classifyPoints()
	
	concaveCount = 0


;	/* Before cutting any ears, we must determine if the polygon was
;         * inputted in clockwise order or not, since the algorithm for
;         * cutting ears assumes that the polygon's points are in clockwise
;         * order.  If the points are in counterclockwise order, they are
;         * simply reversed in the array.
;         */
	If (earCounter = 0) Then
	    If (Not polygonClockwise()) Then
			For i = 0 To npoints - 1
				xpointsTemp(i) = xpoints(npoints-1 - i)
				ypointsTemp(i) = ypoints(npoints-1 - i)
			Next
			For i = 0 To npoints - 1
				xpointsTemp(i) = xpoints(i)
				ypointsTemp(i) = ypoints(i)
			Next
		End If
	End If
	
	For i = 0 To npoints - 1
		If i = 0 Then
			If (convex(xpoints(npoints-2), ypoints(npoints-2), xpoints(i), ypoints(i), xpoints(i+1), ypoints(i+1))) Then
				ptType(i) = 1
			Else
				ptType(i) = -1
				concaveCount = concaveCount + 1
			End If
		Else
			If (convex(xpoints(i-1), ypoints(i-1), xpoints(i), ypoints(i), xpoints(i+1), ypoints(i+1))) Then
			    ptType(i) = 1;	/* point is convex */
			Else
				ptType(i) = -1
				concaveCount = concaveCount + 1
			End If
		End If
	Next
		
End Function

;    /* convex:  returns True If point (x2, y2) is convex
;     */
Function convex(x1#, y1#, x2#, y2#, x3#, y3#)
    
		If (area(x1, y1, x2, y2, x3, y3) < 0) Then Return True Else Return False
	
	End Function
	

;    /* area:  determines area of triangle formed by three points
;     */
Function area(x1#, y1#, x2#, y2#, x3#, y3#)
    
	Local areaSum# = 0

	areaSum = areaSum + (x1 * (y3 - y2))
	areaSum = areaSum + (x2 * (y1 - y3))
	areaSum = areaSum + (x3 * (y2 - y1))

	;/* for actual area, we need to multiple areaSum * 0.5, but we are
    ;     * only interested in the sign of the area (+/-)
    ;     */

	Return areaSum
	
    End Function


;    /* triangleContainsPoints:  returns true if the triangle formed by
;     *                          three points contains another point
;     */
Function triangleContainsPoint(x1#, y1#, x2#, y2#, x3#, y3#)
    
	Local i = 0
	Local area1#, area2#, area3#
	Local noPointInTriangle = True

	While ((i < npoints - 1) And (noPointInTriangle)) 
	
		;/* point is concave */ 
	    If ((ptType(i) = -1) And (((xpoints(i) <> x1) And (ypoints(i) <> y1)) Or ((xpoints(i) <> x2) And (ypoints(i) <> y2)) Or ((xpoints(i) <> x3) And (ypoints(i) <> y3)))) Then

			area1 = area(x1, y1, x2, y2, xpoints(i), ypoints(i))
			area2 = area(x2, y2, x3, y3, xpoints(i), ypoints(i))
			area3 = area(x3, y3, x1, y1, xpoints(i), ypoints(i))
	
			If (area1 > 0) Then
			    If ((area2 > 0) And (area3 > 0)) Then
				noPointInTriangle = False
				End If
			End If
			
			If (area1 < 0) Then
			    If ((area2 < 0) And (area3 < 0)) Then
				noPointInTriangle = False
				End If
		    End If
	
		End If
	
    i = i + 1

	Wend
	
	Return Not (noPointInTriangle)
    End Function


;    /* ear:  returns true if the point (x2, y2) is an ear, false
;     *       otherwise
;     */
Function ear(x1#, y1#, x2#, y2#, x3#, y3#)
	
	If (concaveCount <> 0) Then
	    If (triangleContainsPoint(x1, y1, x2, y2, x3, y3)) Then Return False Else Return True
	Else
	    Return True
	End If
    
	End Function


;    /* cutEar:  creates triangle that represents ear for graphics purposes
;     */
    Function cutEar(index)
    
	Local new_i = 0
	Local i = 0

	;Dim ex#(4), ey#(4)
	
	If (index = 0) Then
	    ex(0) = xpoints(npoints-2)
	    ey(0) = ypoints(npoints-2)
	    ex(1) = xpoints(index)
	    ey(1) = ypoints(index)
	    ex(2) = xpoints(index+1)
	    ey(2) = ypoints(index+1)
	ElseIf ((index > 0) And (index < npoints-2)) Then
	    ex(0) = xpoints(index-1)
	    ey(0) = ypoints(index-1)
	    ex(1) = xpoints(index)
	    ey(1) = ypoints(index)
	    ex(2) = xpoints(index+1)
	    ey(2) = ypoints(index+1)
	ElseIf (index = npoints-2) Then
	    ex(0) = xpoints(index-1)
	    ey(0) = ypoints(index-1)
	    ex(1) = xpoints(index)
	    ey(1) = ypoints(index)
	    ex(2) = xpoints(0)
	    ey(2) = ypoints(0)
	End If
	
	ex(3) = ex(0)
	ey(3) = ey(0)
	
	earPoly.triangle = New Triangle
	earPoly\v0x = ex(0)
	earPoly\v0y = ey(0)
	earPoly\v1x = ex(1)
	earPoly\v1y = ey(1)
	earPoly\v2x = ex(2)
	earPoly\v2y = ey(2)
	earCounter = earCounter + 1
	
    End Function


;    /* updatePolygon:  creates new polygon without the ear that was
;     *                 cut
;     */
Function updatePolygon(index)
    
	Local new_i = 0
	Local i = 0

	If (index = 0) Then i = i + 1

	While (i < npoints - 1)
	    If (i = index) Then i = i + 1
	    If (i < npoints - 1) Then
	
			xpoints(new_i) = xpoints(i)
			ypoints(new_i) = ypoints(i)
			
			new_i = new_i + 1
			i = i + 1
	    End If
	Wend
	
	xpoints(npoints-2) = xpoints(0)
	ypoints(npoints-2) = ypoints(0)
	
	npoints = npoints - 1
    
	End Function


;    /* doCutEar:  Performs all the functions needed to find and cut an
;     *            ear.
;     */
Function doCutEar()
    
	Local earHasBeenCut = False
	Local i = 0

	While ((i < npoints - 1) And (Not earHasBeenCut))
	
	    If (ptType(i) = 1) Then  ;/* point is convex */
			If (i = 0) Then
			    If (ear(xpoints(npoints-2), ypoints(npoints-2),xpoints(i), ypoints(i),xpoints(i+1), ypoints(i+1))) Then
					cutEar(i)
					updatePolygon(i)
					earHasBeenCut = True
		    	End If
			Else     ;/* i > 0 */
			    If (ear(xpoints(i-1), ypoints(i-1),xpoints(i), ypoints(i),xpoints(i+1), ypoints(i+1))) Then
					cutEar(i);
					updatePolygon(i);
					earHasBeenCut = True;
			    End If
			End If
		End If
		
	    
	    i = i + 1
	
  	Wend

	End Function


;Doom3 2D-Fake
;8.10.2004 by Triton
;http://www.silzium-net.de
;
Function filltri(x1,y1,x2,y2,x3,y3,r,g,b,borderr,borderg,borderb) 
For oft = 0 To 1 
If x1 > x2 Then 
p=x2 
x2=x1 
x1=p 
q=y2 
y2=y1 
y1=q 
End If 
If x1 > x3 Then 
p=x3 
x3=x1 
x1=p 
q=y3 
y3=y1 
y1=q 
End If 
If x2 > x3 Then 
p=x3 
x3=x2 
x2=p 
q=y3 
y3=y2 
y2=q 
End If 
Next 

Color r,g,b 
For bx1# = x1 To x2 
m13# = (Float(y3-y1)/(x3-x1)) 
n13# = -m13*x1+y1 
by1# = m13*bx1+n13 

m12# = (Float(y2-y1)/(x2-x1)) 
n12# = -m12*x1+y1 
by2# = m12*bx1+n12 
If by2-by1 > 0 Then Rect bx1,by1,1,by2-by1 
If by2-by1 < 0 Then Rect bx1,by2,1,by1-by2 
Next 
For bx2 = x2 To x3 
m13# = (Float(y3-y1)/(x3-x1)) 
n13# = -m13*x3+y3 
by3# = m13*bx2+n13 

m23# = (Float(y3-y2)/(x3-x2)) 
n23# = -m23*x2+y2 
by4# = m23*bx2+n23 
If by4-by3 > 0 Then Rect bx2,by3,1,by4-by3 
If by4-by3 < 0 Then Rect bx2,by4,1,by3-by4 
Next 

Color borderr,borderg,borderb 
Line x1,y1,x2,y2 
Line x1,y1,x3,y3 
Line x2,y2,x3,y3 
End Function 



;kruisen, determines if line x1,y1-x2,y2 and line x3,y3-x4,y4 are intersecting

Function Kruisen(x1#, y1#, x2#, y2#, x3#, y3#, x4#, y4#)

If (y2 <> y1) Then dx1# = (x2 - x1) / (y2 - y1)
If (y4 <> y3) Then dx2# = (x4 - x3) / (y4 - y3)

grens3 = x1 + (y3 - y1) * dx1
grens4 = x1 + (y4 - y1) * dx1
grens1 = x3 + (y1 - y3) * dx2
grens2 = x3 + (y2 - y3) * dx2

If y4 < y3 Then m34 = y4: n34 = y3 Else m34 = y3: n34 = y4
If y2 < y1 Then m12 = y2: n12 = y1 Else m12 = y1: n12 = y2

If (y2 <> y1) Then test3 = (x3 < grens3) Else test3 = (x3 < x1) And (x3 < x2)
If (y2 <> y1) Then test4 = (x4 < grens4) Else test4 = (x4 < x1) And (x4 < x2)
If (y3 <> y4) Then test1 = (x1 < grens1) Else test1 = (x1 < x3) And (x1 < x4)
If (y3 <> y4) Then test2 = (x2 < grens2) Else test2 = (x2 < x3) And (x2 < x4)

ok3 = (y3 > m12) And (y3 < n12)
ok4 = (y4 > m12) And (y4 < n12)
ok1 = (y1 > m34) And (y1 < n34)
ok2 = (y2 > m34) And (y2 < n34)

test = True

If ok1 And ok2 Then test = test1 = test2
If ok1 And ok3 Then test = test1 <> test3
If ok1 And ok4 Then test = test1 <> test4

If ok2 And ok1 Then test = test2 = test1
If ok2 And ok3 Then test = test2 <> test3
If ok2 And ok4 Then test = test2 <> test4

If ok3 And ok1 Then test = test3 <> test1
If ok3 And ok2 Then test = test3 <> test2
If ok3 And ok4 Then test = test3 = test4

If ok4 And ok1 Then test = test4 <> test1
If ok4 And ok2 Then test = test4 <> test2
If ok4 And ok3 Then test = test4 = test3

Return Not(test)

End Function




;    /* polygonClockwise:  Returns true if user inputted polygon in 
;     *                    clockwise order, false if counterclockwise.  
;     *                    The Law of Cosines is used to determine the
;     *                    angle.
;     */
    Function polygonClockwise()
    
	Local aa#, bb#, cc#, b#, c#, theta#
	Local convex_turn#
	Local convex_sum# = 0

	For i = 0 To npoints - 2
	    aa = ((xpoints(i+2) - xpoints(i)) * (xpoints(i+2) - xpoints(i))) + ((-ypoints(i+2) + ypoints(i)) * (-ypoints(i+2) + ypoints(i)))
	    bb = ((xpoints(i+1) - xpoints(i)) * (xpoints(i+1) - xpoints(i))) + ((-ypoints(i+1) + ypoints(i)) * (-ypoints(i+1) + ypoints(i)))
	    cc = ((xpoints(i+2) - xpoints(i+1)) * (xpoints(i+2) - xpoints(i+1))) + ((-ypoints(i+2) + ypoints(i+1)) * (-ypoints(i+2) + ypoints(i+1)))
		
	    b = Sqr(bb)
	    c = Sqr(cc)
	    theta = ACos((bb + cc - aa) / (2 * b * c))

	    If (convex(xpoints(i), ypoints(i), xpoints(i+1), ypoints(i+1), xpoints(i+2), ypoints(i+2))) Then
			convex_turn = Pi - theta;
			convex_sum = convex_sum + convex_turn
	    
	    Else 
		convex_sum = convex_sum - (Pi - theta)
	    End If
	Next
	
	aa = ((xpoints(1) - xpoints(npoints-2)) * (xpoints(1) - xpoints(npoints-2))) + ((-ypoints(1) + ypoints(npoints-2)) * (-ypoints(1) + ypoints(npoints-2)))
	    
	bb = ((xpoints(0) - xpoints(npoints-2)) * (xpoints(0) - xpoints(npoints-2))) + ((-ypoints(0) + ypoints(npoints-2)) * (-ypoints(0) + ypoints(npoints-2)))
	    
	cc = ((xpoints(1) - xpoints(0)) * (xpoints(1) - xpoints(0))) + ((-ypoints(1) + ypoints(0)) * (-ypoints(1) + ypoints(0)))
	
	b = Sqr(bb)
	c = Sqr(cc)
	theta = ACos((bb + cc - aa) / (2 * b * c))
	
	If (convex(xpoints(npoints-2), ypoints(npoints-2),xpoints(0), ypoints(0),xpoints(1), ypoints(1))) Then
	    convex_turn = Pi - theta
	    convex_sum = convex_sum + convex_turn
	Else 
	    convex_sum = convex_sum - Pi - theta
	End If

	If (convex_sum >= (2 * 3.14159)) Then
	    Return True
	Else
	    Return False
    End If

End Function

Thanks a lot everybody. I was AFK. Thanks bram32, that is looking very interesting.

A few comments: I was not looking for a LOD system. The idea was to remove unneccessary triangulation. This would not reduce the level of details (tho LOD is a good thing, but that wasn't the idea).

I have made some tests with 3DS Max's optimation mesh modifier. Although it can reduce the Polycount to about 60%, a new problem pops up: blinking dots on the seams, seam-leaks. Where I got them in all meshes, it became much more worse when optimized.

So for now I leave the meshes unoptimized for the sake of leakless Tirangle-edges.

Those of you who think about to implement a runtime LOD system should check out the polygon reduction source from the archives. All it needs is automatic UV convertion.

Thanks for your help!

Wouldn't it be better to make the mesh the right way to begin with?

MeshViewer?