Fast CSG

Blitz3D Forums/Blitz3D Programming/Fast CSG

The forum is locked. These are the original blitzbasic.com forums, kept so they can still be read. No new topics, replies or edits can be made here. To join in, head over to the Blitz3D+ forums.

Leadwerks
 #1
Carving is just splitting with one plane, delete one side, split the result with another plane, delete one side, etc.

I'm using a little different method for CShop.

This creates a lot of extra triangles and vertices on the capped face. It can only cap convex objects. The code is rather complicated, especially when ordering the cap surface vertices. I tested it out on some of our WWII weapon models, and it worked perfectly:

Open in online IDE
Graphics3D 800,600,0,2
SetBuffer BackBuffer()

nx#=0.5
ny#=-1
nz#=0.5
d#=2

cam=CreateCamera()
MoveEntity cam,0,0,-40

FlushKeys

TurnEntity CreateLight(),45,45,0

;m=CreateCube()
m=CreateSphere(50)
;EntityFX m,16
ScaleMesh m,10,10,10
;m=LoadMesh("carbine.3ds")

;WireFrame 1
RenderWorld
Text 0,0,"Press a key to split the sphere."
Flip
WaitKey

time=MilliSecs()
splitmesh m,nx,ny,nz,d,1
time=MilliSecs()-time

;UpdateNormals operanda()
;UpdateNormals operandb()

p=CreatePivot()

EntityParent operanda(),p
EntityParent operandb(),p
;EntityFX operanda(),16
;EntityFX operandb(),16

FreeEntity m

;

speed#=0.01

;MoveEntity OPERANDA(),nx*speed,ny*speed,nz*speed
;MoveEntity OPERANDB(),nx*-speed,ny*-speed,nz*-speed

;FreeEntity OPERANDB()

;TurnEntity p,0,90,0

;FreeEntity operandb()

While Not KeyHit(1)
	MoveEntity OPERANDA(),nx*speed,ny*speed,nz*speed
	MoveEntity OPERANDB(),nx*-speed,ny*-speed,nz*-speed

	TurnEntity p,.5,.5,0
	RenderWorld
	Text 0,0,"Split in "+time+" milliseconds."
	Flip
	Wend
End

Global OPERANDA
Global OPERANDB

Global VectorX#
Global VectorY#
Global VectorZ#

Function OperandA()
Return OPERANDA
End Function

Function OperandB()
Return OPERANDB
End Function

Function VectorX#()
Return VectorX#
End Function

Function VectorY#()
Return VectorY#
End Function

Function VectorZ#()
Return VectorZ#
End Function

Function PointOnPlane#(x#,y#,z#,nx#,ny#,nz#,d#)
Return d+nx*x+ny*y+nz*z
End Function

Function RayIntersectsPlane(Ax#,Ay#,Az#,Bx#,By#,Bz#,nx#,ny#,nz#,d#)
u#=(nx*Ax+ny*Ay+nz*Az+d)/(nx*(Ax-Bx)+ny*(Ay-By)+nz*(Az-Bz))
VectorX=Ax+(Bx-Ax)*u
VectorY=Ay+(By-Ay)*u
VectorZ=Az+(Bz-Az)*u
If u>=0.0 And u<=1.0 Return True
End Function

Function Normalize(nx#,ny#,nz#)
m#=Sqr(nx*nx+ny*ny+nz*nz)
VectorX=nx/m
VectorY=ny/m
VectorZ=nz/m
End Function

Function SplitMesh(m,nx#,ny#,nz#,d#,cap=False)
Normalize nx,ny,nz
nx=VectorX()
ny=VectorY()
nz=VectorZ()

OPERANDA=CreateMesh()
OPERANDB=CreateMesh()
PositionEntity OPERANDA,EntityX(m,1),EntityY(m,1),EntityZ(m,1),1
PositionEntity OPERANDB,EntityX(m,1),EntityY(m,1),EntityZ(m,1),1
EntityFX OPERANDA,2
EntityFX OPERANDB,2
If cap
	capa=CreateBank()
	capb=CreateBank()
	temp=CreatePivot()
	AlignToVector temp,nx,ny,nz,3
	MoveEntity temp,0,0,-d
	EndIf
For s=1 To CountSurfaces(m)
	surf=GetSurface(m,s) 
	surfa=CreateSurface(OPERANDA)
	surfb=CreateSurface(OPERANDB)
	If cap
		lista=CreateBank()
		listb=CreateBank()
		EndIf
	SplitSurface(surf,surfa,surfb,nx,ny,nz,d,lista,listb)
	If cap
		For n=0 To BankSize(lista)/20-1
			v=PeekInt(lista,n*20)
			TFormPoint VertexX(surfa,v),VertexY(surfa,v),VertexZ(surfa,v),operanda,temp
			exists=False
			epsilon#=0.0000001
			;For n2=0 To BankSize(capa)/16-1
			;	If Abs(TFormedX()-PeekFloat(capa,n2*16))<epsilon
			;		If Abs(TFormedY()-PeekFloat(capa,n2*16+4))<epsilon
			;			exists=True
			;			Exit
			;			EndIf
			;		EndIf
			;	Next
			If Not exists
				size=BankSize(capa)
				ResizeBank capa,size+16
				PokeFloat capa,size,TFormedX()
				PokeFloat capa,size+4,TFormedY()
				EndIf
			Next
			
			
		For n=0 To BankSize(listb)/20-1
			v=PeekInt(listb,n*20)
			TFormPoint VertexX(surfb,v),VertexY(surfb,v),VertexZ(surfb,v),operandb,temp
			exists=False
			epsilon#=0.0000001
			;For n2=0 To BankSize(capa)/16-1
			;	If Abs(TFormedX()-PeekFloat(capa,n2*16))<epsilon
			;		If Abs(TFormedY()-PeekFloat(capa,n2*16+4))<epsilon
			;			exists=True
			;			Exit
			;			EndIf
			;		EndIf
			;	Next
			If Not exists
				size=BankSize(capb)
				ResizeBank capb,size+16
				PokeFloat capb,size,TFormedX()
				PokeFloat capb,size+4,TFormedY()
				EndIf
			Next
		EndIf
	;ClearSurface surfa
	Next
UpdateNormals operanda
UpdateNormals operandb
If cap
	For n=0 To BankSize(capa)/16-1
		x#=PeekFloat(capa,n*16)
		y#=PeekFloat(capa,n*16+4)
		If x>maxx# Or n=0 maxx=x
		If y>maxy# Or n=0 maxy=y
		If x<minx# Or n=0 minx=x
		If y<miny# Or n=0 miny=y		
		Next
	cx#=(maxx-minx)/2.0+minx
	cy#=(maxy-miny)/2.0+miny
	For n=0 To BankSize(capa)/16-1
		x#=PeekFloat(capa,n*16)
		y#=PeekFloat(capa,n*16+4)
		x=x-cx#
		y=y-cy#
		a#=ATan2(y,x)
		PokeFloat capa,n*16+8,a
		Next
	bank=CreateBank()
	Repeat
		stillgoing=False
		index=0
		For n=0 To BankSize(capa)/16-1
			If PeekInt(lista,n*16+12)=0
				index=index+1
				stillgoing=True
				a#=PeekFloat(capa,n*16+8)
				If index=1 Or a<lowesta#
					lowesta#=a
					lowestslot=n
					EndIf
				EndIf
			Next
		If Not stillgoing Exit
		size=BankSize(bank)
		ResizeBank bank,size+4
		PokeInt bank,size,lowestslot
		PokeInt lista,lowestslot*16+12,1
		Forever
	capsurf=CreateSurface(OPERANDA)
	For n=0 To BankSize(bank)/4-1
		slot=PeekInt(bank,n*4)
		x#=PeekFloat(capa,slot*16)
		y#=PeekFloat(capa,slot*16+4)
		TFormPoint x,y,0,temp,0
		v=AddVertex(capsurf,TFormedX(),TFormedY(),TFormedZ())
		VertexNormal capsurf,v,-nx,-ny,-nz
		Next
	For n=1 To BankSize(bank)/4-2
		AddTriangle capsurf,0,n+1,n
		Next
	AddTriangle capsurf,BankSize(bank)/4-1,0,0
	FreeBank bank



	;Cap B======================================
	
	
		For n=0 To BankSize(capb)/16-1
		x#=PeekFloat(capb,n*16)
		y#=PeekFloat(capb,n*16+4)
		If x>maxx# Or n=0 maxx=x
		If y>maxy# Or n=0 maxy=y
		If x<minx# Or n=0 minx=x
		If y<miny# Or n=0 miny=y		
		Next
	cx#=(maxx-minx)/2.0+minx
	cy#=(maxy-miny)/2.0+miny
	For n=0 To BankSize(capb)/16-1
		x#=PeekFloat(capb,n*16)
		y#=PeekFloat(capb,n*16+4)
		x=x-cx#
		y=y-cy#
		a#=ATan2(y,x)
		PokeFloat capb,n*16+8,a
		Next
	bank=CreateBank()
	Repeat
		stillgoing=False
		index=0
		For n=0 To BankSize(capb)/16-1
			If PeekInt(listb,n*16+12)=0
				index=index+1
				stillgoing=True
				a#=PeekFloat(capb,n*16+8)
				If index=1 Or a<lowesta#
					lowesta#=a
					lowestslot=n
					EndIf
				EndIf
			Next
		If Not stillgoing Exit
		size=BankSize(bank)
		ResizeBank bank,size+4
		PokeInt bank,size,lowestslot
		PokeInt listb,lowestslot*16+12,1
		Forever
	capsurf=CreateSurface(operandb)
	For n=0 To BankSize(bank)/4-1
		slot=PeekInt(bank,n*4)
		x#=PeekFloat(capb,slot*16)
		y#=PeekFloat(capb,slot*16+4)
		TFormPoint x,y,0,temp,0
		v=AddVertex(capsurf,TFormedX(),TFormedY(),TFormedZ())
		VertexNormal capsurf,v,nx,ny,nz
		Next
	For n=1 To BankSize(bank)/4-2
		AddTriangle capsurf,0,n,n+1
		Next
	AddTriangle capsurf,BankSize(bank)/4-1,0,0
	
	;===========================================






	FreeBank lista
	FreeBank listb
	FreeBank capa
	FreeBank capb
	FreeEntity temp
	EndIf
	EntityFX operanda,16
End Function

Function SplitSurface(surf,surfa,surfb,nx#,ny#,nz#,d#,lista=0,listb=0) 
For t=0 To CountTriangles(surf)-1 
	A=TriangleVertex(surf,t,0) 
	B=TriangleVertex(surf,t,1) 
	C=TriangleVertex(surf,t,2) 
	SplitTriangle(surfa,surfb,VertexX(surf,A),VertexY(surf,A),VertexZ(surf,A),VertexX(surf,B),VertexY(surf,B),VertexZ(surf,B),VertexX(surf,C),VertexY(surf,C),VertexZ(surf,C),nx,ny,nz,d,lista,listb) 
	Next 
End Function 

Function SplitTriangle(surfa,surfb,Ax#,Ay#,Az#,Bx#,By#,Bz#,Cx#,Cy#,Cz#,nx#,ny#,nz#,d#,lista=0,listb=0) 
pa#=PointOnPlane(ax,ay,az,nx,ny,nz,d)
pb#=PointOnPlane(bx,by,bz,nx,ny,nz,d)
pc#=PointOnPlane(cx,cy,cz,nx,ny,nz,d)
If pa=0.0 And pb=0 And pc=0 Return
If (Sgn(pa)=Sgn(pb) And Sgn(pb)=Sgn(pc)) Or (Sgn(pb)=Sgn(pc) And pa=0) Or (Sgn(pb)=Sgn(pa) And pc=0) Or (Sgn(pa)=Sgn(pc) And pb=0)
	If pa>0.0 
		A=AddVertex(surfa,ax,ay,az) 
		B=AddVertex(surfa,bx,by,bz) 
		C=AddVertex(surfa,cx,cy,cz) 
		AddTriangle surfa,a,b,c 
		Else
		A=AddVertex(surfb,ax,ay,az) 
		B=AddVertex(surfb,bx,by,bz) 
		C=AddVertex(surfb,cx,cy,cz) 
		AddTriangle surfb,a,b,c 
		EndIf
	Return False 
	EndIf
If Sgn(pa)=Sgn(pb);AB|C 
	If pa<0.0 
		surf=surfa 
		surfa=surfb 
		surfb=surf
		list=lista
		lista=listb
		listb=list
		EndIf 
	RayIntersectsPlane(ax,ay,az,cx,cy,cz,nx,ny,nz,d) 
	dx#=VectorX() 
	dy#=VectorY() 
	dz#=VectorZ() 
	RayIntersectsPlane(bx,by,bz,cx,cy,cz,nx,ny,nz,d) 
	ex#=VectorX() 
	ey#=VectorY() 
	ez#=VectorZ()
	A=AddVertex(surfa,ax,ay,az) 
	B=AddVertex(surfa,bx,by,bz) 
	C=AddVertex(surfb,cx,cy,cz) 
	D=AddVertex(surfa,Dx,Dy,Dz) 
	E=AddVertex(surfa,Ex,Ey,Ez) 
	AddTriangle surfa,D,A,B 
	AddTriangle surfa,D,B,E 

	;VertexColor surfa,D,255,0,0
	;VertexColor surfa,E,255,0,0

	If lista
		size=BankSize(lista)
		ResizeBank lista,size+40
		PokeInt lista,size,D
		PokeInt lista,size+20,E
		EndIf	

	D=AddVertex(surfb,Dx,Dy,Dz) 
	E=AddVertex(surfb,Ex,Ey,Ez) 
	AddTriangle surfb,C,D,E

	
	;VertexColor surfb,D,255,0,0
	;VertexColor surfb,E,255,0,0

	If listb
		size=BankSize(listb)
		ResizeBank listb,size+40
		PokeInt listb,size,D
		PokeInt listb,size+20,E
		EndIf	
	
ElseIf Sgn(pa)=Sgn(pc);AC|B 
	If pa<0.0
		surf=surfa 
		surfa=surfb 
		surfb=surf 
		list=lista
		lista=listb
		listb=list
		EndIf 
	RayIntersectsPlane(ax,ay,az,bx,by,bz,nx,ny,nz,d) 
	dx#=VectorX() 
	dy#=VectorY() 
	dz#=VectorZ() 
	RayIntersectsPlane(bx,by,bz,cx,cy,cz,nx,ny,nz,d) 
	ex#=VectorX() 
	ey#=VectorY() 
	ez#=VectorZ() 
	A=AddVertex(surfa,ax,ay,az) 
	B=AddVertex(surfb,bx,by,bz) 
	C=AddVertex(surfa,cx,cy,cz) 
	D=AddVertex(surfa,Dx,Dy,Dz) 
	E=AddVertex(surfa,Ex,Ey,Ez) 
	
	;VertexColor surfa,D,255,0,0
	;VertexColor surfa,E,255,0,0

	If lista
		size=BankSize(lista)
		ResizeBank lista,size+40
		PokeInt lista,size,D
		PokeInt lista,size+20,E
		EndIf
	
	AddTriangle surfa,A,D,C 
	AddTriangle surfa,D,E,C 
	D=AddVertex(surfb,Dx,Dy,Dz) 
	E=AddVertex(surfb,Ex,Ey,Ez) 

	;VertexColor surfb,D,255,0,0
	;VertexColor surfb,E,255,0,0

	If listb
		size=BankSize(listb)
		ResizeBank listb,size+40
		PokeInt listb,size,D
		PokeInt listb,size+20,E
		EndIf	

	AddTriangle surfb,B,E,D
ElseIf Sgn(pb)=Sgn(pc);BC|A 
	If pa>0.0 
		surf=surfa 
		surfa=surfb 
		surfb=surf 
		list=lista
		lista=listb
		listb=list
		EndIf 
	RayIntersectsPlane(ax,ay,az,cx,cy,cz,nx,ny,nz,d) 
	dx#=VectorX() 
	dy#=VectorY() 
	dz#=VectorZ() 
	RayIntersectsPlane(bx,by,bz,ax,ay,az,nx,ny,nz,d) 
	ex#=VectorX() 
	ey#=VectorY() 
	ez#=VectorZ() 
	A=AddVertex(surfb,ax,ay,az) 
	B=AddVertex(surfa,bx,by,bz) 
	C=AddVertex(surfa,cx,cy,cz) 
	D=AddVertex(surfa,Dx,Dy,Dz) 
	E=AddVertex(surfa,Ex,Ey,Ez) 

	;VertexColor surfa,D,255,0,0
	;VertexColor surfa,E,255,0,0

	If lista
		size=BankSize(lista)
		ResizeBank lista,size+40
		PokeInt lista,size,D
		PokeInt lista,size+20,E
		EndIf

	AddTriangle surfa,B,C,D 
	AddTriangle surfa,B,D,E
	D=AddVertex(surfb,Dx,Dy,Dz) 
	E=AddVertex(surfb,Ex,Ey,Ez) 
	AddTriangle surfb,A,E,D 

	;VertexColor surfb,D,255,0,0
	;VertexColor surfb,E,255,0,0

	If listb
		size=BankSize(listb)
		ResizeBank listb,size+40
		PokeInt listb,size,D
		PokeInt listb,size+20,E
		EndIf

	EndIf 
Return True 
End Function

Function appendint(buffer,value)
ResizeBank buffer,BankSize(buffer)+4
PokeInt buffer,BankSize(buffer)-4,value
End Function