Metaballs

Blitz3D Forums/Blitz3D Programming/Metaballs

Sveinung
 #1
Have anyone tried to make real-time meatballs???
I'm just starting a metaball project...

Need some pointers...perhaps

Sveinung

Anthony Flack
 #2

Have anyone tried to make real-time meatballs???



:o)

sswift
 #3
That's-a spicy metaball-a! <smooch!>

Qcat
 #4
Sum one posted sum 2d mataball examples over a http://www.blitzcoder.com/ a while back.

Birdie
 #5
Hi

I wrote one a while ago But stopped the project due to the heavy copyrights attached to the marching cubes algorithm.

http://quill3d.users.btopenworld.com/proggies/metaballs.zip

If I can find the info that I used I'll post a link to it here. :)

cheers

poopla
 #6
Thats pretty pimp Birdie, nice work.

DarkEagle
 #7
what are metaballs?

Sveinung
 #8
-> Birdie
Hope you find it....nice work by the way!

Sveinung

DJWoodgate
 #9
DarkEagle, Apparently metaballs are representations of an isosurface in 3d space. (well it could be in 2d but who wants flat balls these days?) And its a bit mindblowing. Still you did ask so now you have to read this... http://www.olympus.net/personal/mortenson/preview/definitionsm/metaballs.html
and then this... http://www.siggraph.org/education/materials/HyperGraph/modeling/metaballs/metaballs.htm
and perhaps this... http://www.daimi.au.dk/~u950710/meta/metaball_eng.html
and some of this might be useful... http://www.unchainedgeometry.com/jbloom/papers/index.html
implementation... http://www.cfxweb.net/modules.php?name=News&file=article&sid=199
Paul Bourke again... http://astronomy.swin.edu.au/~pbourke/modelling/polygonise/
http://astronomy.swin.edu.au/~pbourke/modelling/implicitsurf/index.html
http://astronomy.swin.edu.au/~pbourke/modelling/polytetra/
Or you might decide to just download birdies demo and see it in all in action (note the wireframe option). I guess the tricky bit is polygonizing the isosurface. Hence the marching cubes algorithm. There are apparently other ways. I expect its the case that Marching cubes is the best though (or easiest), which is why its copyrighted.

[edit]
Long discussion on the patent (not copyright) issue.
Marching Cubes Patents and You
An alternative algo
Multiresolution Isosurface Extraction with Adaptive Skeleton Climbing

Anthony Flack
 #10
How do you copyright a bloody algorythm anyway? If it is mathematically proven to be the most efficient algo, what then?

sswift
 #11
Not cpyrighted. PATENTED. Blame the US patent office. I wish people would start suing them for allowing unlawful patents.

Birdie
 #12
All I will say is that is well documented and have most of (if not all)the variations of the same algorythm covered in the patent. Aparently they are pretty up on the taking peeps to court over use of the algo aswell. For that reason I decided to drop it lol.

Anyways heres the code I used, dont use it in any comercial projects for the above reasons ;)

If anyone finds another (legal) way of doing this I'd be intrested in hearing about it :)

Global MEtaPivot
Include "Constants.bb"
Const TargetValue#=.5
Const C_SPHERE	=1
Const C_CUBE	=2

Global TheStep#

Global GridSize
Global GridMapSize
Global HGridSize
Global GridBank			;this is to hold the computations

Function InitMetaGrid(size)
	MEtaPivot=CreateMesh()
	GridSize=size
	HGridSize=size/2
	GridMapSize=GridSize*GridSize
	GridBank=CreateBank(size*size*size)	; 1 byte to hold if its computed
End Function

Function ClearMetaGrid()
	For a=0 To BankSize(GridBank)-1 Step 4
		PokeInt GridBank,a,0
	Next
End Function

Function SetComputed(x#,y#,z#)
	pos=(GridMapSize*z)+((y*GridSize)+x)
	PokeByte GridBank,pos,1
End Function

Function IsComputed(x#,y#,z#)
	pos=(GridMapSize*z)+((y*GridSize)+x)
	If PeekByte(GridBank,pos)=1 Then Return True
	Return False
End Function 

Type mvec
	Field x#
	Field y#
	Field z#
End Type

Function GetNormal( n.mvec,x#,y#,z#)
	n\x=ComputeEnergy(x-0.01,y,z)-ComputeEnergy(x+0.01,y,z)
	n\y=ComputeEnergy(x,y-0.01,z)-ComputeEnergy(x,y+0.01,z)
	n\z=ComputeEnergy(x,y,z-0.01)-ComputeEnergy(x,y,z+0.01)
End Function

;------------------------------------------------------------------------------
;IntersectOnEdge finds the approximate point of intersection of the surface
;between two points with the values point1 and point2
Function IntersectOnEdge#(point1#,point2#,result#)
        difference# = point2 - point1
        If difference = 0.0
			Return 0.5;
        	EndIf
        Return (result - point1)/difference
End Function ;IntersectOnEdge

;Polygonise1() performs the Marching Cubes algorithm on a single cube
Function Polygonise(x#,y#,z#,surf)
        Local intersection#, ValueOfCube#[8];
        Local VertexOfEdge.mvec[12], NormalOfEdge.mvec[12]
        Local corner,vertex,edge,triangle,index,edgeFlags
        ;Make a Local copy of the values at the cube's corners
        For vertex = 0 To 7
			ValueOfCube[vertex] = ComputeEnergy#(x+CubeVertex(vertex,0)*TheStep,y + CubeVertex(vertex,1)*TheStep,z + CubeVertex(vertex,2)*TheStep);
        Next
        ;Find which vertices are inside of the surface And which are outside
        index = 0;
        For vertex = 0 To 7
			If ValueOfCube[vertex] <= TargetValue
				index = Index Or (1 Shl vertex)
			EndIf
		Next
		;Find which edges are intersected by the surface
        edgeFlags = CubeEdgeIntersect(index);
		;If the cube is entirely inside Or outside of the surface, Then there will be no intersections
        If edgeFlags = 0 Then Return
		;Find the point of intersection of the surface with Each edge
		;Then find the normal To the surface at those points
        For edge = 0 To 11
			;If there is an intersection on this edge
			If edgeFlags And (1 Shl edge)
				intersection=IntersectOnEdge(ValueOfCube[CubeEdge(edge,0)],ValueOfCube[CubeEdge(edge,1)],targetValue);
				VertexOfEdge[edge]=New mvec
				NormalOfEdge[edge]=New mvec
				VertexOfEdge[edge]\X=x+(CubeVertex(CubeEdge(edge,0),0)+intersection*EdgeDirection(edge,0))*TheStep;
				VertexOfEdge[edge]\Y=y+(CubeVertex(CubeEdge(edge,0),1)+intersection*EdgeDirection(edge,1))*TheStep;
				VertexOfEdge[edge]\Z=z+(CubeVertex(CubeEdge(edge,0),2)+intersection*EdgeDirection(edge,2))*TheStep;
                GetNormal NormalOfEdge[edge],VertexOfEdge[edge]\X, VertexOfEdge[edge]\Y, VertexOfEdge[edge]\Z
			EndIf
        Next
		;Draw the triangles that were found.  There can be up To 5 per cube
		c=CountVertices(surf)
        For triangle=0 To 4
			If CubeTriangles(index,3*triangle)>=0 Then
	            For corner=0 To 2
					vertex = CubeTriangles(index,3*triangle+corner)
					tv=AddVertex(surf,VertexOfEdge[vertex]\X, VertexOfEdge[vertex]\Y, VertexOfEdge[vertex]\z)
					c=c+1
					VertexNormal surf,tv,NormalOfEdge[vertex]\X, NormalOfEdge[vertex]\Y, NormalOfEdge[vertex]\Z
				Next
				AddTriangle surf,c-3,c-2,c-1
			EndIf
		Next
		Delete Each mvec
End Function ;Polyginise1()

Function Check_Corners(x#,y#,z#)
	For vertex = 0 To 7
 		If ComputeEnergy#(x+CubeVertex(vertex,0)*TheStep,y+CubeVertex(vertex,1)*TheStep,z+CubeVertex(vertex,2)*TheStep)>TargetValue
			Return True
		EndIf
	Next
	Return False
End Function

Function RenderMetaBalls(surf,stp)
	For be.Meta_Blob=Each meta_blob
		FindSetVoxel be\x,be\y,be\z,surf,stp
	Next
End Function


;WARNING RECURSIVE
Function FindSetVoxel(x,y,z,surf,stp)
	;if this one is computed then return
	If IsComputed(x/stp,y/stp,z/stp)=False Then
		;if none of the corners are within the surface return
		If Check_Corners(x,y,z)=False Then 
			SetComputed x,y,z
			Return
		Else
			SetComputed x/stp,y/stp,z/stp
			Polygonise(x,y,z,surf)
			;now check all the faces of the cube
			FindSetVoxel(x+stp,y,z,surf,stp)
			FindSetVoxel(x-stp,y,z,surf,stp)
			FindSetVoxel(x,y+stp,z,surf,stp)
			FindSetVoxel(x,y-stp,z,surf,stp)
			FindSetVoxel(x,y,z+stp,surf,stp)
			FindSetVoxel(x,y,z-stp,surf,stp)
		EndIf
	Else
		Return
	EndIf
End Function

Graphics3D 800,600,0,2
SetBuffer BackBuffer()
piv=CreatePivot()
PositionEntity piv,75,75,75
cam=CreateCamera(piv)
PositionEntity cam,0,0,-100
tex=LoadTexture("spheremap.jpg",65)
TheStep=8

m=CreateMesh()
EntityTexture m,tex
EntityFX m,1
FreeTexture tex
CameraClsColor cam,150,150,150

surf=CreateSurface(m)
l=CreateLight()

New_Metacube(75,75,75,20)
New_MetaSphere(50,45,75,10)
New_MetaSphere(50,45,75,10)

InitMetaGrid 200
w=1
While Not KeyDown(1)
ren=0
	tim=MilliSecs()
	If KeyDown(203) Then TurnEntity piv,0,6,0
	If KeyDown(205) Then TurnEntity piv,0,-6,0
	If KeyDown(200) Then TurnEntity piv,6,0,0
	If KeyDown(208) Then TurnEntity piv,-6,0,0
	If KeyHit(17) Then w=1-w
	WireFrame w
	t=MilliSecs()
	MoveBalls()	
	ClearSurface surf,True,True
	If KeyDown(57) =0 
		ClearMetaGrid
		RenderMetaBalls surf,TheStep
	EndIf
	RenderWorld
	
;	AppTitle "Meta Balls. David Bird. Press W for wireframe "+1000/(MilliSecs()-tim)+" FPS"
	If ren=1 Then Text 320,0,"High res Mesh Render.",1
	Flip 1
	If ren=1 Then WaitKey
Wend
End

Function MoveBalls()
	For b.Meta_Blob=Each Meta_Blob
		dx#=b\dx
		dy#=b\dy
		dz#=b\dz
		b\x=b\x+dx
		b\y=b\y+dy
		b\z=b\z+dz
		n=0
		If b\x<50 Or b\x>100 Then n=1
		If b\y<50 Or b\y>100 Then n=1
		If b\z<50 Or b\z>100 Then n=1
		If n=1 Then
			b\dx=-b\dx
			b\dy=-b\dy
			b\dz=-b\dz
		EndIf
		b\ax=b\ax+5
		b\ay=b\ay+5
		b\az=b\az+5
	Next
End Function

Type Meta_Blob
	Field typ					;
	Field mag#					;mass
	Field half_mag_inv_4th#		;
	Field mag_4th#				;
	Field rad#					;
	Field inner_rad#			;
	Field x#,y#,z#				;position
	Field ax#,ay#,az#			;rotation
	Field dx#,dy#,dz#
End Type

Function ComputeEnergy#(px#,py#,pz#)
	Local dist_in_xz#, dist_in_y#, dist_from_track_squared#;
	Local r_squared#,r_4th#,dx#,dy#,dz#
	Local q#,mag#
	For blob.Meta_Blob=Each Meta_Blob
		PositionEntity MEtaPivot,blob\x,blob\y,blob\z
		RotateEntity MEtaPivot,blob\ax,blob\ay,blob\az
		TFormPoint px,py,pz,0,MEtaPivot
		dx = TFormedX();px - blob\x;
		dy = TFormedY();py - blob\y;
		dz = TFormedZ();pz - blob\z;
		Select blob\typ
			Case C_SPHERE
				r_squared = dx*dx + dy*dy + dz*dz
				r_squared = blob\mag/r_squared
				q = q + r_squared
			Case C_CUBE
				dx = dx*dx*dx*dx
				dy = dy*dy*dy*dy
				dz = dz*dz*dz*dz
				r_4th = Abs(dx+dy+dz)
				r_4th = (blob\mag_4th/r_4th)
				q = q  + r_4th 
		End Select
	Next
	target=q
	Return q	;return the energy
End Function

Function UpdateMetaBlobs()
	For b.Meta_Blob=Each Meta_Blob
		Select b\typ
			Case C_SPHERE
				b\mag=b\rad*b\rad
			Case C_CUBE
				b\mag_4th=b\rad*b\rad*b\rad*b\rad
				b\half_mag_inv_4th=-b\mag_4th/2
		End Select
	Next
End Function 

Function New_MetaSphere.meta_blob(x#,y#,z#,rad#)
	b.meta_blob=New meta_blob
		b\typ=C_SPHERE
		b\x=x
		b\y=y
		b\z=z
		b\mag=(rad*rad)
		b\rad=rad
		b\dx=Rnd(-2,2)
		b\dy=Rnd(-2,2)
		b\dz=Rnd(-2,2)
	Return b
End Function

Function New_MetaCube.meta_blob(x#,y#,z#,rad#)
	b.meta_blob=New meta_blob
		b\typ=C_CUBE
		b\x=x
		b\y=y
		b\z=z
		b\rad=rad
		b\mag_4th=rad*rad*rad*rad
		b\half_mag_inv_4th=-b\mag_4th/2
		b\dx=Rnd(-2,2)
		b\dy=Rnd(-2,2)
		b\dz=Rnd(-2,2)
	Return b
End Function


and the constants.bb file

;------------------------------------------------------------------------------
;constants
Const DEG_TO_RAD = Pi / 180.0;
Const RAD_TO_DEG = 180.0 / Pi;
Const EPSILON = 0.000001
Const INFINITY = 1000000
;------------------------------------------------------------------------------
;These tables are used so that everything can be done in little loops that you can look at all at once
;rather than in pages and pages of unrolled code.

;CubeVertex lists the positions, relative to vertex0, of each of the 8 vertices of a cube
Dim CubeVertex#(8,3)
For a=0 To 7
	For b=0 To 2
		Read CubeVertex(a,b)
	Next
Next
Data 0.0, 0.0, 0.0 , 1.0, 0.0, 0.0 , 1.0, 1.0, 0.0 , 0.0, 1.0, 0.0
Data 0.0, 0.0, 1.0 , 1.0, 0.0, 1.0 , 1.0, 1.0, 1.0 , 0.0, 1.0, 1.0
;CubeEdge lists the index of the endpoint vertices For Each of the 12 edges of the cube
Dim CubeEdge(12,2)
For a=0 To 11
	For b=0 To 1
		Read CubeEdge(a,b)
	Next
Next
Data 0,1 , 1,2 , 2,3 , 3,0
Data 4,5 , 5,6 , 6,7 , 7,4
Data 0,4 , 1,5 , 2,6 , 3,7
;EdgeDirection lists the direction vector (vertex1-vertex0) For Each edge in the cube
Dim EdgeDirection#(12,3)
For a=0 To 11
	For b=0 To 2
		Read EdgeDirection(a,b)
	Next
Next
Data 1.0,0.0,0.0 , 0.0,1.0,0.0 , -1.0,0.0,0.0 , 0.0, -1.0,0.0
Data 1.0,0.0,0.0 , 0.0,1.0,0.0 , -1.0,0.0,0.0 , 0.0, -1.0,0.0
Data 0.0,0.0,1.0 , 0.0,0.0,1.0 ,  0.0,0.0,1.0 , 0.0,  0.0,1.0

;TetrahedronEdge lists the index of the endpoint vertices
;for each of the 6 edges of the tetrahedron
Dim TetrahedronEdge(6,2)
For a=0 To 5
	For b=0 To 1
		Read TetrahedronEdge(a,b)
	Next
Next
Data 0,1 , 1,2 , 2,0 , 0,3 , 1,3 , 2,3

;CubeTetrahedrons lists the index of vertices from a cube
;that made up each of the six tetrahedrons within the cube
Dim CubeTetrahedrons(6,4)
For a=0 To 5
	For b=0 To 3
		Read CubeTetrahedrons(a,b)
	Next
Next
Data  0,5,1,6 , 0,1,2,6 , 0,2,3,6 , 0,3,7,6 , 0,7,4,6 , 0,4,5,6 

Dim TetraEdgeIntersec(16)
For a=0 To 15
	Read TetraEdgeIntersec(a)
Next
Data $00,$0d,$13,$1e,$26,$2b,$35,$38,$38,$35,$2b,$26,$1e,$13,$0d,$00

;For each of the possible vertex states listed in TetraEdgeIntersec there is a specific triangulation
;of the edge intersection points.  TetrahedronTriangles lists all of them in the form of
;0-2 edge triples with the list terminated by the invalid value -1.
;I generated this table by hand

Dim TetrahedronTriangles(16,7)
For a=0 To 15
	For b=0 To 6
		Read TetrahedronTriangles(a,b)
	Next
Next
Data  -1, -1, -1, -1, -1, -1, -1
Data   0,  3,  2, -1, -1, -1, -1
Data   0,  1,  4, -1, -1, -1, -1
Data   1,  4,  2,  2,  4,  3, -1
Data   1,  2,  5, -1, -1, -1, -1
Data   0,  3,  5,  0,  5,  1, -1
Data   0,  2,  5,  0,  5,  4, -1
Data   5,  4,  3, -1, -1, -1, -1
Data   3,  4,  5, -1, -1, -1, -1
Data   4,  5,  0,  5,  2,  0, -1
Data   1,  5,  0,  5,  3,  0, -1
Data   5,  2,  1, -1, -1, -1, -1
Data   3,  4,  2,  2,  4,  1, -1
Data   4,  1,  0, -1, -1, -1, -1
Data   2,  3,  0, -1, -1, -1, -1
Data  -1, -1, -1, -1, -1, -1, -1

;// For any edge, if one vertex is inside of the surface and the other is outside of the surface
;//  then the edge intersects the surface
;// For each of the 8 vertices of the cube can be two possible states : either inside or outside of the surface
;// For any cube the are 2^8=256 possible sets of vertex states
;// This table lists the edges intersected by the surface for all 256 possible vertex states
;// There are 12 edges.  For each entry in the table, if edge #n is intersected, then bit #n is set to 1

Dim CubeEdgeIntersect(256)
For a=0 To 255
	Read CubeEdgeIntersect(a)
Next
Data $000, $109, $203, $30a, $406, $50f, $605, $70c, $80c, $905, $a0f, $b06, $c0a, $d03, $e09, $f00
Data $190, $099, $393, $29a, $596, $49f, $795, $69c, $99c, $895, $b9f, $a96, $d9a, $c93, $f99, $e90
Data $230, $339, $033, $13a, $636, $73f, $435, $53c, $a3c, $b35, $83f, $936, $e3a, $f33, $c39, $d30
Data $3a0, $2a9, $1a3, $0aa, $7a6, $6af, $5a5, $4ac, $bac, $aa5, $9af, $8a6, $faa, $ea3, $da9, $ca0
Data $460, $569, $663, $76a, $066, $16f, $265, $36c, $c6c, $d65, $e6f, $f66, $86a, $963, $a69, $b60
Data $5f0, $4f9, $7f3, $6fa, $1f6, $0ff, $3f5, $2fc, $dfc, $cf5, $fff, $ef6, $9fa, $8f3, $bf9, $af0
Data $650, $759, $453, $55a, $256, $35f, $055, $15c, $e5c, $f55, $c5f, $d56, $a5a, $b53, $859, $950
Data $7c0, $6c9, $5c3, $4ca, $3c6, $2cf, $1c5, $0cc, $fcc, $ec5, $dcf, $cc6, $bca, $ac3, $9c9, $8c0
Data $8c0, $9c9, $ac3, $bca, $cc6, $dcf, $ec5, $fcc, $0cc, $1c5, $2cf, $3c6, $4ca, $5c3, $6c9, $7c0
Data $950, $859, $b53, $a5a, $d56, $c5f, $f55, $e5c, $15c, $055, $35f, $256, $55a, $453, $759, $650
Data $af0, $bf9, $8f3, $9fa, $ef6, $fff, $cf5, $dfc, $2fc, $3f5, $0ff, $1f6, $6fa, $7f3, $4f9, $5f0
Data $b60, $a69, $963, $86a, $f66, $e6f, $d65, $c6c, $36c, $265, $16f, $066, $76a, $663, $569, $460
Data $ca0, $da9, $ea3, $faa, $8a6, $9af, $aa5, $bac, $4ac, $5a5, $6af, $7a6, $0aa, $1a3, $2a9, $3a0
Data $d30, $c39, $f33, $e3a, $936, $83f, $b35, $a3c, $53c, $435, $73f, $636, $13a, $033, $339, $230
Data $e90, $f99, $c93, $d9a, $a96, $b9f, $895, $99c, $69c, $795, $49f, $596, $29a, $393, $099, $190
Data $f00, $e09, $d03, $c0a, $b06, $a0f, $905, $80c, $70c, $605, $50f, $406, $30a, $203, $109, $000

;For each of the possible vertex states listed in CubeEdgeIntersec there is a specific triangulation
;of the edge intersection points.  a2iTriangleConnectionTable lists all of them in the form of
;0-5 edge triples with the list terminated by the invalid value -1.
;For example: a2iTriangleConnectionTable[3] list the 2 triangles formed when corner[0]
;and corner[1] are inside of the surface, but the rest of the cube is not.
;
;I found this table in an example program someone wrote long ago.  It was probably generated by hand

Dim CubeTriangles(256,16)
For a=0 To 255
	For b=0 To 15
		Read CubeTriangles(a,b)
	Next
Next
Data -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1
Data 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1
Data 3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1
Data 3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1
Data 9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1
Data 1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1
Data 9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1
Data 2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1
Data 8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1
Data 9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1
Data 4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1
Data 3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1
Data 1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1
Data 4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1
Data 4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1
Data 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1
Data 1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1
Data 5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1
Data 2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1
Data 9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1
Data 0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1
Data 2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1
Data 10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1
Data 4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1
Data 5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1
Data 5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1
Data 9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1
Data 0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1
Data 1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1
Data 10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1
Data 8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1
Data 2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1
Data 7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1
Data 9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1
Data 2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1
Data 11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1
Data 9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1
Data 5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1
Data 11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1
Data 11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1
Data 1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1
Data 9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1
Data 5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1
Data 2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1
Data 0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1
Data 5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1
Data 6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1
Data 0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1
Data 3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1
Data 6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1
Data 5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1
Data 1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1
Data 10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1
Data 6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1
Data 1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1
Data 8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1
Data 7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1
Data 3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1
Data 5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1
Data 0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1
Data 9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1
Data 8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1
Data 5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1
Data 0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1
Data 6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1
Data 10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1
Data 10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1
Data 8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1, -1, -1, -1
Data 1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1
Data 3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1
Data 0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1
Data 10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1
Data 0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1
Data 3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1
Data 6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1
Data 9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1
Data 8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1
Data 3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1
Data 6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1
Data 0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1
Data 10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1
Data 10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1
Data 1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1
Data 2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1
Data 7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1
Data 7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1
Data 2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1
Data 1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1
Data 11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1
Data 8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1
Data 0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1
Data 7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1
Data 10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1
Data 2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1
Data 6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1
Data 7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1
Data 2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1
Data 1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1
Data 10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1
Data 10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1
Data 0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1
Data 7, 6, 10, 7, 10, 8, 8, 10, 9, -1, -1, -1, -1, -1, -1, -1
Data 6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1
Data 8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1
Data 9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1
Data 6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1
Data 1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1
Data 4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1
Data 10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1
Data 8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1
Data 0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1
Data 1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1
Data 8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1
Data 10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1
Data 4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1
Data 10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1
Data 5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1
Data 11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1
Data 9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1
Data 6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1
Data 7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1
Data 3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1
Data 7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1
Data 9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1
Data 3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1
Data 6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1
Data 9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1
Data 1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1
Data 4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1
Data 7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1
Data 6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1
Data 3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1
Data 0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1
Data 6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1
Data 1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1
Data 0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1
Data 11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1
Data 6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1
Data 5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1
Data 9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1
Data 1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1
Data 1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1
Data 10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1
Data 0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1
Data 5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1
Data 10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1
Data 11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1
Data 0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1
Data 9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1
Data 7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1
Data 2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1
Data 8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1
Data 9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1
Data 9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1
Data 1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1
Data 9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1
Data 9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1
Data 5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1
Data 0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1
Data 10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1
Data 2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1
Data 0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1
Data 0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1
Data 9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1
Data 5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1
Data 3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1
Data 5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1
Data 8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1
Data 0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1
Data 9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1
Data 0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1
Data 1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1
Data 3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1
Data 4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1
Data 9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1
Data 11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1
Data 11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, -1
Data 2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, -1
Data 9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1
Data 3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1
Data 1, 10, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, -1
Data 4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, -1
Data 4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 9, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 3, 0, 9, 3, 9, 11, 11, 9, 10, -1, -1, -1, -1, -1, -1, -1
Data 0, 1, 10, 0, 10, 8, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1
Data 3, 1, 10, 11, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 1, 2, 11, 1, 11, 9, 9, 11, 8, -1, -1, -1, -1, -1, -1, -1
Data 3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1, -1, -1, -1
Data 0, 2, 11, 8, 0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 2, 3, 8, 2, 8, 10, 10, 8, 9, -1, -1, -1, -1, -1, -1, -1
Data 9, 10, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1, -1, -1, -1
Data 1, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data 0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Data -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1


jhocking
 #13
Darkeagle, metaballs are used to represent a liquid/blobby surface like water (duh, I just said "liquid") or organic flesh. The idea is that a mesh surface is created by "melting" together a whole bunch of metaballs. Specifically, the closer together two metaballs are the more the resulting surface blends the two together. Compare metaballs to water droplets; when distant the droplets are distinct and separate but when moved close together they merge into a single blobby shape. If the balls move around the surface is updated, resulting in an undulating liquid.

People used to be interested in metaballs as a technique for organic modeling but eventually the extremely dense and unweildy meshes which result forced metaballs out of favor. Now metaballs are mostly used for representing water with a particle system (with metaballs for particles.)

Anthony Flack
 #14
I can't believe that the algo, and all obvious variations is patented. Insane. Most mathematicians would be up in arms about that I would imagine. Is that patent only good for the US, btw?

Birdie
 #15

by Jeff Lander
Gamasutra
May, 23, 2000

The Marching Cubes Patent Question

As many of you who have met me and heard me rant on the topic know, I believe algorithmic software patents are totally wrong. I feel they completely halt continued development down interesting research pathways by shrouding a topic with legal pitfalls. Graphics researchers create progress by building on the work done by others before them. I like to imagine the state of the industry if Bresenham had patented his method for drawing a line on a graphic display and then charged a licensing fee for every line drawn.

The topic of volume rendering is an interesting case in point. As an obvious next step in the visualization of volume data, it was reported by researchers in several publications. However, General Electric apparently owns a patent on the technique via the Lorenson and Cline implementation (U.S. patent #4,710,876). As an actual apparatus to display medical imaging data, I can understand it. However, the patenting of a "method for displaying three-dimensional surface images" seems pretty broad to me.

I have been told by someone via e-mail that GE aggressively enforces this patent. However, it is not clear to me how this would apply to the rendering of an isosurface in a game. Does this mean that any modeling program using these techniques must pay a license to GE? If I create a game using a derivative of marching cubes and it is a big hit, am I going to receive a stealth patent letter in the mail demanding a percentage? How derivative does it need to be? The prior art on this topic seems limitless, but what can I use as a reference and still be safe?

With the record number of software patents being filed, this is going to become an increasingly difficult issue for game developers in the future. I am actively researching the issue and hope to report on the results in a later column. Anyone with information on the topic, please let me know. In the meantime, always document your research from public journals as best you can. Ignorance is not bliss in this situation.





I did read somewhere else that the patent doesn't just cover the US but its a global patent which in itself costs a fortune. So I cant see them letting anything go for free.

Rob
 #16
How can they tell? they cannot force you to reveal your sourcecode surely?

Madcap13
 #17
someone really needs to think up a marching hexagon formula.

sswift
 #18
Someone already came up with marching tetrahedrons.

I'm sure there's ways to do similar things as marching cubes, and get smoother results. Marching cubes isn't very good actually. It makes very blocky geometry. You actually need to then push the vertcies out or in a little so they lie on the actual surface, which then gives you nice round shapes.

Anthony Flack
 #19
Glad to hear I'm not the only one who is utterly disgusted by this. So much of current laws regarding intellectual property desperately need to be thrown on the furnace.

Zephar123
 #20
copy right laws are becoming stupid and are halting progress to no end. As noted above people need to sue the patent offices for allowing peopel to patent things that are unlawfull. HEck there was a guy who tried to sue the NFL for there was of drawing football allgorithyms, because he had a patent on it. I am not joking. Infact he woudl of won if the nfl did nto have so much money.

BlitzSupport
 #21
Click here if you want to use metaballs.

jfk EO-11110
 #22
Btw: GE = j.p. Morgan.

shawnus
 #23
Dear all

I am using blitz3d to visualise and interact with 3d medical models that I have created from 2d CT/MRI/fluoroscopic scans. I use a very narrow camera clip to 'move through' the structure, but as the structure is surface rendered, the object appears 'hollow'. I understand that metaballs are esentially objects volume rendered, so using the camera clip to move through this object, would the object appear 'solid'? Does anyone else have any experience with this? I am aware of the GE algorithm issue regarding patent, but does it apply to games or medical images?

Cheers Shawnus

sswift
 #24
No. Any metaballs generated with Blitz really just generate a 3D mesh, which is hollow.

If you want a 3D object you can move through, and view the inside of then what you want is voxels.

Voxels are basically little cubes, or quads that are rotated to face the camera. Each voxel represents what the color of the object is at that point in space.

Individual voxels will dissapear though if they pass beyond the camera. If you want volumes that appears totally solid, then you'll need to clip cubes against the near camera plane and reconstruct the surface there... I would reccomend having a specific surface just for capping polygons. You don't actually have to cut the cubes apart, just create new polygons inside them on a new surface that will lie flush with the camera view. But that won't let you view it from far away and slice a portion away, which seems like it would be much more useful.

There's a lot of ways to do what you want to do really, and none are particularly easy, and making it fast too is a challenge.

shawnus
 #25
sswift,
Do you know of any examples of this interactive 'cube clipping' that have been done in Blitz? Is there a game engine that will support volume rendering, or is this limited to just medical workstations? I think this challenge is well beyond me...
Cheers Shawnus

smilertoo
 #26
You cant have a global patent if a country doesnt recognise software algorithm patents.

Malice
 #27
I wanna patent the use of crap patents to screw people for no particular good reason.

Clyde
 #28
Lovelly example Birdie.

Are there other ways to do Metaballs?
If this ridiculous patent is implied.

Erroneouss
 #29
can you use the stuff if you dont sell it at all?
like just make a tool to use?
...

Clyde
 #30
Is there another way, with morphing the objects.
This is something I'd very much love to be able to do and espeically in B3D; as I've seen this in some top gfx demos. Any pointers, snippets etc would be grand.

Nilium
 #31
Actually, I contacted GE about the patents this summer. One of the two patents was dropped earlier this year, the second is still being held. You have to contact one of their lawyers/businessmen to purchase a license to use the patent. If anyone wants one of their lawyer's e-mail addresses to contact them, let me know. They're very straight-forward, so don't expect a whole bunch of legal crap from them if you're just asking about the patents.

Erroneouss
 #32
soooo can you use it just to make a tool that you arent selling?

Gabriel
 #33
soooo can you use it just to make a tool that you arent selling?


You have to contact one of their lawyers/businessmen to purchase a license to use the patent.


Dreamora
 #34
Stuff like is really annoying and the bad thing is that EU has a patent system for software and algorithm as well due to this US example :(

on the other hand this has it's good side: the 3D stuff won't progress much further, so I don't have to buy new hardware ;-)

Clyde
 #35
So is "marching cubes" the only way possible to make metaballs?

Nilium
 #36
No.

Among the others is one called marching triangles, but that isn't the only algorithm.

Regular K
 #37
I like meatballs.

Clyde
 #38
Cheers :)

What other ways are there then dude?