Clipping

Mar 2, 2011 at 4:31 PM

Hi,

I have some large flat boxes with smaller boxes placed on it. Is it possible to prevent the large box from being clipped but

still retain the clipping on the smaller boxes ?

Thanks

Stuart

Mar 3, 2011 at 2:51 PM

Hi Stuart,
Could you post a screen shot?  I'd like to try and help but I'm not sure I fully understand what you are doing.

Mar 3, 2011 at 8:10 PM

Hi,

 

Thank for the reply. I have uploaded a screen shot here http://psnebg.bay.livefilestore.com/y1pewtECDFgZq0451q0jaKKrQAZ4pY_Ic_-LVn70ddMWSxaInQCcr6SOeTajvkhb8QOmCZ9c0O4CFA9xh8PCLoea-KpwvD9awff/map1.jpg?psid=1

If you take a look at  the image you can see a few green boxes the grey area is where the other boxes are getting clipped. The scene is driven by data so i have no idea how many levels of green blocks (in this example) or

the number or size of the shapes on them. I am only using basic primatives as the scene can have upto 5K of boxes and cylinders. All the textures are generated on the fly again from the data. Its a very early version at the moment

as you can see I am just sorting out the text scaling.

Thanks  Stuart

Mar 3, 2011 at 8:31 PM

Hi, I have uploaded a zoomed out 1.2k box map which may give you a better idea of the problem. You can see the clipping in the centre area of the picture.

http://orq2za.bay.livefilestore.com/y1pEnM36rBNQeTsoMo6ltmelehH_lsSD56OHKe_RRT_JI__uikUhvR7n5sULHIrkiMKVC2b33wQOCt6686MnoFKA-pNtchc1JJP/datamap2.jpg?psid=1

Mar 4, 2011 at 3:26 PM

Ahh yes I see it in that second photo.

I know of this bug well...   Balder does not work with triangles that are HUGE. This means that even small triangles that are close to the camera can get clipped. In this case the triangle isn't close to the camera, but it's still really large. If you have the ability to move around your world, you'll notice that as you approach shapes parts of the shape will disappear.

The only way I've found to fix this so far, and this isn't ideal, is to break the shapes into small triangles. This does create more triangles, but can help performance in some cases. It's a fine line between too many triangles and too few large ones.

My current game suffers from this. As I walk around, and near walls, they can disappear.

I have been working on and off with the creators of Balder on a fix, but so far there hasn't been one. If you'd like I can show you the two places in the Balder engine causing the trouble. If you have some math or 3d math background you might be able to solve it. So far it’s beyond my math knowledge.

Mar 4, 2011 at 3:34 PM

Thanks for the reply. I did try breaking down the shapes but the performance started to drop off. If you can point me a the two places in the engine causing the trouble Ill take a look.

Thanks again Stuart.

Mar 4, 2011 at 3:50 PM

Here is the first place:  Rendering/Silverlight/GeometryDetailLevel.cs
The red code, when removed fixes a lot of the trouble, but... leads to very very bad performance.
In the past I've multiplied the viewport width/height by 10 to *help* the issue, but each new multiplication level hurts performance just that much more.
The second place escapes me at the moment, I need to refind it.  (The code base is large)

If you do find a fix for this I would be very interested in it, if you would be willing to share.

		private bool IsFaceVisible(RenderFace face, Viewport viewport)
		{
			var a = _vertices[face.A];
			var b = _vertices[face.B];
			var c = _vertices[face.C];

			var mixedproduct = (b.ProjectedVector.X - a.ProjectedVector.X) * (c.ProjectedVector.Y - a.ProjectedVector.Y) -
							   (c.ProjectedVector.X - a.ProjectedVector.X) * (b.ProjectedVector.Y - a.ProjectedVector.Y);
			var visible = mixedproduct < 0 && 
							mixedproduct > -(viewport.Width*viewport.Height) &&
							IsFaceInView(viewport, face);
			if (null != face.Material)
			{
				visible |= face.Material.CachedDoubleSided;
			}

			

			return visible;
		}
Mar 4, 2011 at 4:01 PM

I will let you know how I get on and if I do find a fix I will pass in back.

Stuart

Coordinator
Mar 5, 2011 at 7:04 AM

I'm working on the clipping issue - there are several issues in fact, if anyone figures out a solution to the problem - I'd appreciate it if you let me know. :)

Thanks,

Einar

Mar 5, 2011 at 8:32 PM

Hi,

Can you give this a try. I still need to build a better test app but it has fixed my orignal app issue, I also had a little better response with the IsFaceInView Test First.

Stuart

private bool IsFaceVisible(RenderFace face, Viewport viewport)
		{
            if (IsFaceInView(viewport, face))
            {
                var a = _vertices[face.A];
                var b = _vertices[face.B];
                var c = _vertices[face.C];

                var mixedproduct = ((c.ProjectedVector.X - a.ProjectedVector.X) * (b.ProjectedVector.Y - a.ProjectedVector.Y)) >=
                                  ((c.ProjectedVector.Y - a.ProjectedVector.Y) * (b.ProjectedVector.X - a.ProjectedVector.X));

                var visible = mixedproduct;
 
                if (null != face.Material)
                {
                    visible |= face.Material.CachedDoubleSided;
                }

		        return visible;
            }

            return false;
        }
Mar 6, 2011 at 10:38 PM

Hi, My last post helped a little but did not fix the issue. This code seems to work better it still has an issue if the poly is bigger that the viewport but that may not be worth testing for.

My Math is not great so someone else may be able to provide some faster tests. I have broken down some of the tests to get an early exit if posible. Makes the code look messy

but seems to run faster this way.

	private bool IsFaceVisible(RenderFace face, Viewport viewport)
	{
            var a = _vertices[face.A];
            var b = _vertices[face.B];
            var c = _vertices[face.C];

            bool visible = ((c.ProjectedVector.X - a.ProjectedVector.X) * (b.ProjectedVector.Y - a.ProjectedVector.Y)) >=
                                 ((c.ProjectedVector.Y - a.ProjectedVector.Y) * (b.ProjectedVector.X - a.ProjectedVector.X));

            if (null != face.Material)
                {
                    visible |= face.Material.CachedDoubleSided;
                }

            return visible && (IsFaceInView(viewport, face));
	}
	private bool IsFaceInView(Viewport viewport, Face face)
	{
		    // Not looked at this yet but as we are going to test against the Near plane we may a well
		    // test now and exit early.
		    if (_vertices[face.A].ProjectedVector.Z < viewport.View.Near &&
		        _vertices[face.B].ProjectedVector.Z < viewport.View.Near &&
		        _vertices[face.C].ProjectedVector.Z < viewport.View.Near)
		    {
		        return false;
		    }

		    //At least One point is inside the viewport, Seperate tests to see if we get a little perfomace increase.
		    if ((0 < _vertices[face.A].ProjectedVector.X && _vertices[face.A].ProjectedVector.X < viewport.Width &&
		         0 < _vertices[face.A].ProjectedVector.Y && _vertices[face.A].ProjectedVector.Y < viewport.Height))
		        return true;

		    if ((0 < _vertices[face.B].ProjectedVector.X && _vertices[face.B].ProjectedVector.X < viewport.Width &&
		         0 < _vertices[face.B].ProjectedVector.Y && _vertices[face.B].ProjectedVector.Y < viewport.Height))
		        return true;

		    if ((0 < _vertices[face.C].ProjectedVector.X && _vertices[face.C].ProjectedVector.X < viewport.Width &&
		         0 < _vertices[face.C].ProjectedVector.Y && _vertices[face.C].ProjectedVector.Y < viewport.Height))
		        return true;

		    // If all the points are on one side of the viewport we can forget about this one.
		    if ((0 > _vertices[face.A].ProjectedVector.X && 0 > _vertices[face.B].ProjectedVector.X &&
		         0 > _vertices[face.C].ProjectedVector.X) &&
		        (viewport.Width < _vertices[face.A].ProjectedVector.X && viewport.Width < _vertices[face.B].ProjectedVector.X &&
		         viewport.Width < _vertices[face.C].ProjectedVector.X) &&
		        (viewport.Height > _vertices[face.A].ProjectedVector.Y &&
		         viewport.Height > _vertices[face.B].ProjectedVector.Y &&
		         viewport.Height > _vertices[face.C].ProjectedVector.Y) &&
		        (0 < _vertices[face.A].ProjectedVector.Y && 0 < _vertices[face.B].ProjectedVector.Y &&
		         0 < _vertices[face.C].ProjectedVector.Y))
		        return false;

		    //If we get here we need to test for any intersects.
		    if (VectorViewportIntersect(_vertices[face.A].ProjectedVector.X, _vertices[face.A].ProjectedVector.Y,
		                                _vertices[face.B].ProjectedVector.X, _vertices[face.B].ProjectedVector.Y,
		                                viewport.Width, viewport.Height)) return true;
		    if (VectorViewportIntersect(_vertices[face.B].ProjectedVector.X, _vertices[face.B].ProjectedVector.Y,
		                                _vertices[face.C].ProjectedVector.X, _vertices[face.C].ProjectedVector.Y,
		                                viewport.Width, viewport.Height)) return true;
		    return VectorViewportIntersect(_vertices[face.C].ProjectedVector.X, _vertices[face.C].ProjectedVector.Y,
		                                   _vertices[face.A].ProjectedVector.X, _vertices[face.A].ProjectedVector.Y,
		                                   viewport.Width, viewport.Height);
	}

	private static bool VectorViewportIntersect(float x0, float y0, float x1, float y1, int viewPortWidth,
	                                                int viewPortHeight)
	{
	        float topIntersection;
	        float bottomIntersection;
	        float topTrianglepoint;
	        float bottomTrianglepoint;

	        float m = (y1 - y0)/(x1 - x0);
	        float c = y0 - (m*x0);
	        if (m > 0)
	        {
	            topIntersection = (m + c);
	            bottomIntersection = (m*viewPortWidth + c);
	        }
	        else
	        {
	            topIntersection = (m*viewPortWidth + c);
	            bottomIntersection = (m + c);
	        }

	        if (y0 < y1)
	        {
	            topTrianglepoint = y0;
	            bottomTrianglepoint = y1;
	        }
	        else
	        {
	            topTrianglepoint = y1;
	            bottomTrianglepoint = y0;
	        }

	        float topoverlap = topIntersection > topTrianglepoint ? topIntersection : topTrianglepoint;
	        float botoverlap = bottomIntersection < bottomTrianglepoint ? bottomIntersection : bottomTrianglepoint;

	        return (topoverlap < botoverlap) && (!((botoverlap < 0) || (topoverlap > viewPortHeight)));
	 }
Let me know what you think.
Stuart
Coordinator
Mar 7, 2011 at 9:33 PM

Thanks for leading me down the right path. 

It turns out that the backface culling was the source of all evil. It was done on the 2D coordinates before any clipping had occured, which lead to crazy calculations and some faces dropping out completely and others not getting the proper clipping they needed. 

I've checked in my changes now. 

I'll look more closely at the optimizations you propose as they are very interesting!  

 

Thanks again for helping out here and clearing my head from the ideas I've been having. 

 

Anyways, the source is pushed - getting the latest should give a very accurate clipping scenario (I hope..)

Mar 8, 2011 at 1:32 AM
Edited Mar 8, 2011 at 1:43 AM

This thread is getting kind of long. 

Stuart: The fixes you suggested did help, but the rendering slowed down a lot with your changes applied.  Also, when I walk to a wall it still dissepears (though you did say that would happen.)

Mar 8, 2011 at 1:43 AM

Adept:
Thanks for taking a look at this again as well.  I'm afraid the fix has reduced my 35-50 fps to <1 fps :(  I have integrated your changes except for the following parts:

GeometryDetailLevel.cs line 406 and line 410

face.Transform(world, view);
and
var visible = face.IsVisible(viewport, _vertices);

Any advice?  Are your speed tests effected by this change?

Coordinator
Mar 8, 2011 at 5:04 PM

Those are the two most vital lines of my change. :) 

I've changed the whole way of doing back face culling, without those lines you're not getting back-face culling, nor proper clipping.

Mar 8, 2011 at 5:20 PM

It works for me when I am zoomed out from my models but the closer I get the slower it gets. So if i have large polys in view

it drops to 1-2 fps. Any advice where I can look to improve this.

 

Mar 8, 2011 at 5:55 PM

The back-face culling and clipping do work much better with your changes Adept. However, rendering seems to be much much slower for my case, with the new method. I'm working on a short little demo I hope to demonstrate the before and after effects of this change. It is possible that I’m not using Balder in the intended way, and as such I can’t get the performance I need out of it. I hope that is not the case, but I need to be prepared for that possibility. The old way, without the proper culling was getting me 35-50fps. Switching nothing but the code required to get to the new method of culling drops me to <1. I mean no offense, and I still think you offer a great framework, but all things being equal aside from those two lines make me believe the culling might still need work. Or, I’m not using Balder correctly :) I hope to have that test project up soon.

Thanks again for all your work and for making it public so we can see how it ticks!

Coordinator
Mar 8, 2011 at 6:42 PM

Sure, no problem.  Love the fact that people are picking up Balder and use it for their projects - very greatful for all the valuable input from you guys. 

I'm profiling the engine now to see if there is something obvious. 

 

StuartTrez : Did you have this speed issue with large polys before I did this new clipping thing?

Mar 8, 2011 at 7:40 PM

Hi, Yes I did have the same problem but this has got worse with the latest version but the culling issue has been resolved.

I did try and have a look today but no joy. I had a flat plane with 200 boxes on it that when zoomed out was stilling working

away at 30-40 fps but if i zoomed into about 10 boxes it dropped to 2-4 fps. All the objects or boxes in my case are being culled

correctly and all the 2D culling seems to be working !.

 

Mar 8, 2011 at 8:15 PM

I've noticed that large numbers of triangles behind the camera seem to cause the poor performance.  When you zoom out there are fewer, or no triangles behind the camera.  When you zoom in the system must cull out triangles that are behind the camera.  The z-buffer will ultimatly catch these triangles behind the camera, but the perspective transform will have blown them up and rasterization of the now larger triangles kills performance.  At least that's what I've seen so far.

Coordinator
Mar 8, 2011 at 8:44 PM

I've done some more work now - cleaned up a few things, found a bottleneck with regards to materials and how it was being applied to faces - should speed up things a bit, especially with scenes that has many triangles.

Also found some left overs from some old multithreading code that was doing some locking - removing it regained some valuable clock-cycles.

 

As for the clipping you mention for faces behind the Near clip - this seems to be working, so I'm not quite sure why there are any faces that would get crazy values now.

 

Anyways, I've done a few things this evening - so I might have sorted that out without knowing. :) 

Love it if you could pull the latest and see if things have resolved

Mar 8, 2011 at 10:33 PM

Only had chance for a quick test this evening, but.... its looking great so far. I have seen one small clipping issue when close up to large polys

but apart from that... fantatstic :)).

Mar 9, 2011 at 9:22 AM
Edited Mar 9, 2011 at 9:57 AM

Hi, it is running faster but still slow when you get close up to objects. Not sure if this is what Xersoft was talking about but if you take a quick look at this

very simple pic : http://l5ttfa.bay.livefilestore.com/y1p2-DKV_itNxIujF8Kem2Kdzx3t87aSG-hLwNnVsQLjgZCov0VaDJC8Vn7AqE0Y4nu27x9HShW4Z3ir9RcsmvEwUdJIv-HqU8X/ViewPortExample11.jpg?psid=1

The Green area is the current 2d ViewPort. The pic shows one object (inside a box) in this example each side of the box is made up of 2 polys but the same would be true for multiple polys that span back out of the viewport area.

 My question is does the red area get rasterized. If it is then thats the performance issue both myself and Xersoft are seeing.

Coordinator
Mar 9, 2011 at 7:54 PM

Glad to hear its running faster. 

The rasterizer is not doing a good enough job on clipping this - clipping is done in two places, one one a scanline level - anything above is skipped and it stops rendering when it comes to end. As for each scanline, the clipping is checked per pixel, so its still looping through everything. 

Neither of these are optimal - I have a branch locally were I've started fixing and optimizing this by doing proper clipping, so when I get that done we should see great perf improvements. 

I won't have time before the weekend to actually start working on that optimization - hang in there, we'll get there. . :)

 

Btw: Thanks for creating the illustration - makes it a lot easier to understand right off the bat! 

Mar 9, 2011 at 7:58 PM

Thanks again, no rush I have plenty to get on with. On a side note can you give me some idea of what tutorials or samples you may

want for balder. Stuart

Mar 9, 2011 at 8:44 PM

Thank you both for all your work.  Stuart, I almost have that demo app done that could be used to walk through a world and see the performance
in certain areas.  This might help find and address these issues.  I hope to upload that with a before and after example either later today or
tomorrow.

Stuart, one example I've always been looking for is camera handling in 3rd person.  First person cameras I get, but when you follow around
an object you can run into issues when you get close to walls.  The camera might end up on the other side of the wall!  Just a thought :)

Thanks again to you both!

Mar 9, 2011 at 11:02 PM

Ok, I have the demo ready. I hope this helps track down these clipping issues. I have two compiled version, one using Balder
before the new clipping code, and the other using Balder after the latest clipping code changes. I realize that this code is not the
best, this is my first engine of this scope and I’m new at it. It does work however, and it does express the issue before and after
the clipping changes. Along with the compiled Silverlight apps I have uploaded the code. In each case the code is the same
and only the version of Balder I’m using has changed. I hope this project can help make Balder better!

Notes:
You can move around with the WSAD keys. To ‘look’ around you need to right click on the game window and move the mouse.
It can take a bit of practice. Once you get the hang of it, it feels like any old FPS game. The mouse wheel can put you into third
person, but it’s a bit buggy at the moment. The world is limitless; when you get to the edge of a ‘chunk’ it will generate more for
you. This can take some time and you’ll notice a slight pause when this happens. This isn’t because of Balder. Also, page up and
page down allow you to fly around.

The before clipping version is pretty fast, about 45fps on my machine. When you get to close to a wall, or look at the ground you’ll see clipping.

The after clipping version is very slow, almost unusable. However, the clipping is perfect!

Before Clipping Changes
http://www.zerfservices.com/BeforeClippingChange/Test.html

After Clipping Changes
http://www.zerfservices.com/AfterClippingChange/Test.html

Source Code
http://www.zerfservices.com/Code/BalderDemo.zip

 

Coordinator
Mar 14, 2011 at 10:09 PM

Thanks a lot for the sample xersoft..  It really helped me out nailing this.  

I'm almost done - and your sample is running with 50 FPS on my computer at all times now, just some small artifacts on the 2D clipping that is left - but very very maintainable. Hopefully have it done today - otherwise tomorrow.

Coordinator
Mar 15, 2011 at 5:55 PM

Its official; Clipping is now done - as far as the tests I've been doing and with the sample Xersoft supplied here - its working out great. 

There is however one bug introduced that is unrelated to clipping - but changing properties on a material is not reflected after its done loading. I'm looking into this. The reason the bug is coming now is that during the clipping work I've optimized quite a bit as well - and one of them was related to materials. 

Mar 15, 2011 at 6:32 PM

Hi adept,

Good News: Its running FAST :)

Bad News: Its still clipping at the top of the viewport with large polys when all points are outside the viewport

Image here if it helps: http://lcascq.bay.livefilestore.com/y1pRERjl6VcyBUnalL0xSE00OJDt6unOjbstG_w35OJFFzp0y-QpkUSb-ak6gAOQrKumbAV6CcJfSf8GanEK_Y7i2UIXI0EkVvb/clipping.jpg?psid=1

Thanks for this , I now have the speed i needed.

Stuart

Coordinator
Mar 15, 2011 at 6:50 PM

Good to hear its running fast. Too bad about the clipping issue though. 

I'll go back and see if I can figure out why that scenario is not taken care of. 

Mar 17, 2011 at 1:50 AM

After integrating all the changes you made Adept, and then reapplying the customized changes I've added to support transparency, I'm happy to report clipping seems fixed! The demo app didn't have any collision detection, but with that turned on I can't get close enough to a wall to see it disappear! This is a happy day for me! I haven't been able to reproduce Stuart's clipping issues at the top of the viewport yet, but I will keep my eye out. Thanks again for all your hard work. Congrats on the massive reworks you did to solve this issue. Night and day difference!

Coordinator
Mar 17, 2011 at 7:15 AM

Very glad to hear that. 

Keep me posted on any problems you'll find.  

Thanks for all the help in nailing this..

Aug 2, 2012 at 10:13 AM

Hi,

Can you please update the Sample Code? Which will help me.

(http://www.zerfservices.com/Code/BalderDemo.zip)

Atleast "WSAD keys" functionality.

 

Thanks,

Raja.

Aug 2, 2012 at 10:16 AM

Hi,

Could you please tell me, How to move the camera using (left,right,front & back) arrow keys?  Code snippet please.

 

Thanks,

Raja