Fast CSG

Blitz3D Forums/Blitz3D Programming/Fast CSG

JoshK

(Posted 2004) [#1]

39,600-poly sphere split in half, with caps, in 68 millisecs:
http://www.leadwerks.com/post/splitmesh.exe

RayTracer

(Posted 2004) [#2]

thats great ,are you going to release the source?

Zenith

(Posted 2004) [#3]

Dude, you need a wireframe mode :D

Jeroen

(Posted 2004) [#4]

you liar! You just one sphere mesh (b3d) and stuck them together as one!!!

Hehehe, no seriously, it's cool.

AntonyWells

(Posted 2004) [#5]

Let us see it on a abstract piece of geo.

Warren

(Posted 2004) [#6]

The shape shouldn't matter. It isn't like he can special case a sphere or something. Triangles are triangles.

AntonyWells

(Posted 2004) [#7]

I'm just interested to see how well it copes with true Csg(I.e carving one mesh into another etc) rather than splitting a round mesh. The csg funcs in the archives for example work great in some cases, and are totally 'messed' up in other circumstances. I'm guessing this is a part of a commercial lib, and if it does what it says fast across any geo then even I'd buy it. And I don't buy things apperantly..;)

And obviously real world siturations... I mean would you guys demo unreal 3 with a sphere? :)

RayTracer

(Posted 2004) [#8]

this would make geo-mod possible ,if halo is kind enough to release the source

AntonyWells

(Posted 2004) [#9]

if halo is kind enough to release the source

That's the best joke I've heard all year. ;)

But I'm sure he'll be releasing it as a lib..which is cool if reasonably priced.

Warren

(Posted 2004) [#10]

It's likely a part of Cartography Shop.

JoshK

(Posted 2004) [#11]

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:

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

CyberHeater

(Posted 2004) [#12]

Simply amazing. Thanks Halo.

Dreamora

(Posted 2004) [#13]

really fast stuff.

what made me wonder was the fact, that its going mad when it comes to cones, which shouldn't be any problem compared to the problems a sphere creates ...

JoshK

(Posted 2004) [#14]

I think what I am using in CShop is properly called "convex hulls". The objects are wireframes, where the lines are made out of triangles between only two vertices. It's a million times easier to split, because there is only one way to split a line, and there are three ways to split a triangle.

JoshK

(Posted 2004) [#15]

I AM A ****ING GENIUS!

I wrote a routine that will "cap" the faces of any object made out of wireframe lines (triangles between two vertices).

Nobody

(Posted 2004) Edit [#16]

Oh don't pat yourself on the back to hard there halo. There is always somebody else out there that can also accomplish great things as well... Not just you! I've seen some other peoples work too, And there is alot of ****ING GENIUS'S out there! Rob, Rob Farley, FredBorg, Skitchy, to name just a few!! I respect & appreciate these people and others on here because they don't go around Glorifying themselves as you so often do! If you know you create excellent work. Then let other people praise you for it! Don't brag & glorify yourself as this makes you look bad towards others! But hey! This is just my opinion though!

slenkar

(Posted 2004) [#17]

Halo you seem to have talent in this area but looking at the code archives you dont seem to make this available to people - except if they are lucky enough to spot your post on the forums.

Why dont you be a good chap and put all your functions (that you have posted) in the code archives.

You will gain lasting respect and admiration.
I only see 2 entries from you in the 3D sections.

As for the routine to cap any surface, WIngs3D (free app) has been doing that for a few years now,

JoshK

(Posted 2004) [#18]

Nobody, your screen name is appropriate.

Picklesworth

(Posted 2004) [#19]

That's pretty fast. Thanks, I think I'll be using that at some point for something...

Rook Zimbabwe

(Posted 2004) [#20]

Very impressive... I should send you some muscle pain reliever from patting yourself on the back ;)

Well organized and readable even for my poor addled brain.

Major Kudos halo
-RZ

CyberHeater

(Posted 2004) [#21]

[quote]halo (Posted 2004-06-19 21:18:53)
Nobody, your screen name is appropriate. [\quote]

I think that "Nobody" is displayed when the user is banned.

Rambus

(Posted 2004) [#22]

"Well organized and readable even for my poor addled brain.�

So true, all too many pieces of code that hit the forums don�t follow even the most basic indentation and variable naming rules. It's a big waist when some on has all the logic but writes out puke code; your pretty print is very much appreciated halo.

Kozmi

(Posted 2004) [#23]

halo

Nobody, your screen name is appropriate.

Hmmmmm... Sound's like "Nobody" didn't like your reply to you being a ****ing GENIUS there halo.

;)

Warren

(Posted 2004) [#24]

Who knew that God couldn't spell?

JoshK

(Posted 2004) [#25]

Here is a demo of a 32-sided cylinder set at a 45 degree angle carving a chunk out of a cube. The process takes 7 milliseconds(!). Hit any key to start:
http://www.leadwerks.com/post/fastcarve.zip

If I can do a complex boolean like this in basically no time, real-time processing for shadow volumes, BSP cuts, occlusion, etc., should be no problem.

For the CShop 5 lightmapper, I am going to attempt to use a shadow volume method rather than a raytracer. It's project the edges of brushes onto other brushes and trim away the overlaps. At this speed, it might be possible to perform lighting in a few seconds. Maybe even real-time. I don't know yet.

Rambus

(Posted 2004) [#26]

Very impressive carve demo halo. I was scoring from 7-8 milliseconds with a few apps open in the background.

Dreamora

(Posted 2004) [#27]

Halo: so you aren't planing to use any GI like stuff in CS5 again?

Zenith

(Posted 2004) [#28]

thats class again, nice halo

JoshK

(Posted 2004) [#29]

What is GI?

poopla

(Posted 2004) [#30]

Halo, your alot of things, but you aren't a genious ;). Talanted and smart yeah. But arrogance never gets anyone **** out of life. It gets them a kick in the arse m8.

Good work with the CSG though, especially if it's as fast as was said. I havn't had time to look myself, or keep up with this post.

JoshK

(Posted 2004) [#31]

All you Euros are so sensitive.

DarkEagle

(Posted 2004) [#32]

what about us damn brits. we never get any compliments!

(feel free to flame, stab, mutilate, burn, mail, brand, cook, demoralize, steal from, or kick me in the nuts with reference to this post)

Kozmi

(Posted 2004) [#33]

Halo, You link returns an invalid web page. Could you please fix this so I can check this out?

Rob	(Posted 2004) [#34]

ShatteredReality (Posted 2004-06-20 17:41:34)

Halo, your alot of things, but you aren't a genious ;). Talanted and smart yeah. But arrogance never gets anyone **** out of life. It gets them a kick in the arse m8.

match halo's skill or STFU.

AntonyWells

(Posted 2004) [#35]

Spoon?

Warren

(Posted 2004) [#36]

match halo's skill or STFU.

Many of us can match his skill. His ego, well, that's another matter...

JoshK

(Posted 2004) [#37]

You can't match. Unless "Bubble Blocks" is it.

DrakeX

(Posted 2004) [#38]

Otacon: "Spoon?"

agreed.

i find it amazing how you people find the smallest things to argue about. and this is just pointless arguing, not a "discussion" of any kind.

Mikel

(Posted 2004) [#39]

halo - you may well be a genius. Was it a FLASH of insight that hit you out of the blue? Your post was a prime example of WHY coding and designing software is so much freakin fun!

I understand where you were coming from. Keep up the good work.

JoshK

(Posted 2004) [#40]

It was the alien beings that tell me to do bad things.