Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


D.V.D

Member Since 20 Aug 2012
Offline Last Active Jul 02 2015 09:45 PM

Posts I've Made

In Topic: Compute cube edges in screenspace

08 June 2015 - 07:39 PM

So I was rethinking the problem and I think I found a faster way of going about this that still uses the idea of C0lumbo. So I'm using an octree and I figured that the node which is closest to the camera intersects with all of the visible nodes of my cube. Here are some examples:

 

XZvTXAa.png

 

Using this, I can almost instantly get the 3 faces which are visible to the camera. The problem however are off cases where 2 or 1 face are visible. The issue here is I don't have a quick and dirty way of getting which of these faces are visible so I might have to settle with rasterizing them or maybe using another property but I'm not sure. Below is an image illustrating 2 of these cases:

 

xm5pYQ1.png

 

If anyone has any other idea's, please write a post. I'm going to begin implementing this algo and will post the code later.


In Topic: Compute cube edges in screenspace

07 June 2015 - 01:46 PM

 


Is there a way to quickly compute those 6 edges ... ?

 

Not knowing how fast "quick" is, IMHO, the answer is "no," as it could require depth-testing/visibility checks, a series of line intersection tests, etc. There are a lot of ways to determine a polygon outline - google for terms like "compute" or "calculate polygon outline" or similar.

 

However, there may be a better solution to what you're trying to do. I.e., can you describe what problem you're trying to solve, rather than how you're trying to solve it? Depending on your needs, a graphical solution (though not necessarily "quick" or simple) may work.

 

 

So I'm doing software voxel rendering and I'm storing my voxels as octrees. My idea was to project the root to get the 6 silouhette edges and then for each subdivision, I would extrapolate the childrens 6 edges from the roots. I would traverse front to back and render each visible child and not render occluded nodes and their children. Its similar to this paper here but it doesn't go into how to calculate the cubes silouhette: https://www.cs.princeton.edu/courses/archive/spring01/cs598b/papers/greene96.pdf

 

I'm not sure how to deal with intersecting polygons though, its not well described in the paper.

 

Sounds like silhouette calculation. For each face of the cube you can calculate whether it is facing toward the camera or away from the camera. Then for each edge of the cube you can calculate if it connects a face that's pointing away and a face that's pointing toward the camera. If so, then it forms part of the silhouette.

 

Tricky to implement though, because you need to deal with floating point precision issues, and once you've figured out the silhouette edges, working out the correct ordering you want might be fiddly.

 

"Also, if I subdivide the cube into 8, would the same relative points for the smaller cubes also form an outline for each smaller cubes?" - With an orthographic view, I think yes. With a projection view, I think no.

For a projective view, I assumed there was a property of projective space where given 2 points and their depth, I can get a mid point but it would require a bit more calculation. I think it would require an extra divide or something due to the 1/z. I have a paper on projective space that I have to read but I'm very sure there is a way of doing it just that its not as simple as a midpoint between two points.

 

Hmm, okay I get it how that works. That seems tricky to implement but I'll google around for calculating silhouettes. I was previously googling edge computing but that didn't bring up what I was looking for.

 

The way I thought of doing it currently is cube specific which is fine for my application but I thought that I could calculate the 8 points distance from the cube's center and remove the 2 points which are closest to the cube. So for example:

 

uaMNCbr.png

 

In the above picture the 2 points which are closest to the center (the ones with the dark blue arrows pointing towards them) would be removed and then I would have the 6 points that form the outer edges. I'm less sure on how to get the edges order from that so that each half place is on the proper side. I was thinking that if I have the points in a array sorted by index and just remove the 2 closest ones, if I made edges by stepping through this array then I would get my proper edges but that might not work under certain rotations.

 

I think the biggest problem is getting the point order to have my half plane functions set up properly.


In Topic: Compute cube edges in screenspace

07 June 2015 - 11:21 AM

i dont know i dont understand but if you manage to know cube point in worldspace then

 

you multimply each: (model_matrix*view_matrix)*projection_matrix * vertex = VERT - this gives you NDC coordinates which are between -1..1

 

if you want to compute actual pixel you need to do PixelX = VERT.x * 0.5 + 0.5; //same for y which is your y pixel. i am not quite sure what z was (it gives you the depth, and i forgot alos that you could div all (xyz elements) by w component but i forgot what for.

Hmm here let me try to draw it out. I have a cube that I want to project but I want to figure out the 6 edges that make its outline in screen space:

 

b7y87AM.png

 

So in this picture, I have 6 edges that I want to find of my projected cube. There are some inner edges when you project a cube but only the 6 that are selected in the picture are necessary to figure out the outline of the projected cube. Is there a way to quickly compute those 6 edges when the cube could be in a arbitrary rotation and a arbitrary position on screen?


In Topic: Wrong projection near the camera

04 June 2015 - 05:29 AM

so I guess that artifact would have something to do with how I calculate my nodes screen size.

I also noticed that when my octree is close to the edge, it appears to be traversed deeper which I guess makes sense since perspective makes objects on the side of the screen larger.

Octrees should exist in world space. There is no reason things would move inside your octree just because of the perspective of your camera or location of your camera.L. Spiro

Yes but the octree is traversed until each nodes size is roughly 1 pixel. So if the perspective stretches a node to be larger on screen, its going to be traversed further.

In Topic: Wrong projection near the camera

03 June 2015 - 08:41 PM

Hey guys,

So I just did some tests in my scene. I made the octree nodes draw a certain color based on their level in the octree. Here is my picture (NOTE that the dark yellow and bright level are 2 separate levels):

R7lvPTO.png

Now what you might notice is how the octrees colors have borders but its not a clear cut border as it usually is in octrees. Instead I got a ton of little dots and wavy patterns that occur in motion. I know the wavy patterns occur because of how floats are encoded so I guess that artifact would have something to do with how I calculate my nodes screen size. Here is my current code:

struct OctNode{	uint32 Color;	OctNode* Children[8];};struct Octree{	OctNode Tree;};void RenderOctNode(OctNode* Node, ScreenBuffer* Screen, int32* Traversal, Vector3f Pos, Vector3f Deltas[8],	float32 rad_x, float32 rad_y, float32 rad_z, int32 level = 0){	++NumTraversals;	MaxLevel = Max(MaxLevel, level);	// If node is behind camera, return	if (Pos.z - rad_z <= 0.0f)	{		++NumBehindCam;		return;	}	// Check if node is entirely outside the screen (fairly accurate for screen size	int32 MinX, MinY, MaxX, MaxY;	GetOctantScreenSize(Screen, Pos, rad_x, rad_y, rad_z, MinX, MinY, MaxX, MaxY);	// If node outside of view, return	if ((MinX >= Screen->Width) || (MinY >= Screen->Height) || ((MaxX | MaxY) < 0))	{		++NumOutsideViewFrustum;		return;	}	// Clip the nodes	MaxX = ClipXToScreen(Screen, MaxX);	MaxY = ClipYToScreen(Screen, MaxY);	MinX = ClipXToScreen(Screen, MinX);	MinY = ClipYToScreen(Screen, MinY);	float32 MaxZ = ClipZToScreen(Pos.z - rad_z);	// Is node occluded	if (IsOctantVisibleYellowMice(Screen, MinX, MinY, MaxX, MaxY, MaxZ))	{		// If node is around 1 pixel, draw and return		if ((MaxX - MinX) <= 1 && (MaxY - MinY) <= 1)		{			++NumRendered;			for (int32 y = MinY; y <= MaxY; ++y)			{				for (int32 x = MinX; x <= MaxX; ++x)				{					int32 Index = MaxY * Screen->Width + MaxX;					Screen->DepthBuffer[Index] = MaxZ;					Screen->ColorBuffer[Index] = 5000000 * level;				}			}			return;		}		else if ((!Node->Children[0] && !Node->Children[1] && !Node->Children[2] && !Node->Children[3] && !Node->Children[4] && !Node->Children[5] &&			!Node->Children[6] && !Node->Children[7]) || level == 31) // If octant has no children, render and return		{			++NumRendered;			// Extract all 8 cube points			Vector3f Cube[8];			float32 temp_level = 1.0f / (float32)(1 << (level));			Cube[0] = FastPerspectiveTransform(Screen, (Pos + (Deltas[0] * temp_level)));			Cube[1] = FastPerspectiveTransform(Screen, (Pos + (Deltas[1] * temp_level)));			Cube[2] = FastPerspectiveTransform(Screen, (Pos + (Deltas[2] * temp_level)));			Cube[3] = FastPerspectiveTransform(Screen, (Pos + (Deltas[3] * temp_level)));			Cube[4] = FastPerspectiveTransform(Screen, (Pos + (Deltas[4] * temp_level)));			Cube[5] = FastPerspectiveTransform(Screen, (Pos + (Deltas[5] * temp_level)));			Cube[6] = FastPerspectiveTransform(Screen, (Pos + (Deltas[6] * temp_level)));			Cube[7] = FastPerspectiveTransform(Screen, (Pos + (Deltas[7] * temp_level)));			RenderCube(Screen, Cube, 0xFFFFFFFF);			return;		}		// Else Traverse through all children in front to back order		if (Pos.z + rad_z >= 0.0f && Pos.z - rad_z <= 0.0f) // If camera inside octree node		{			DrawChildrenInsideCam(Node, Screen, Pos, Deltas, Traversal, rad_x, rad_y, rad_z, level);		}		else		{			DrawChildren(Node, Screen, Traversal, Pos, Deltas, rad_x, rad_y, rad_z, level);		}	}	else	{		++NumOccluded;	}	return;}void RenderOctree(Octree* tree, ScreenBuffer* Screen, Mat4x4f Camera){	// Transform root to camera space	Vector3f Cube[8];	Cube[0] = Camera * Vector3f{ 0.5f, 0.5f, 0.5f };//TopRight	Cube[1] = Camera * Vector3f{ 0.5f, -0.5f, 0.5f };//BotRight	Cube[2] = Camera * Vector3f{ -0.5f, 0.5f, 0.5f };//TopLeft	Cube[3] = Camera * Vector3f{ -0.5f, -0.5f, 0.5f };//BotLeft	Cube[4] = Camera * Vector3f{ 0.5f, 0.5f, -0.5f };	Cube[5] = Camera * Vector3f{ 0.5f, -0.5f, -0.5f };	Cube[6] = Camera * Vector3f{ -0.5f, 0.5f, -0.5f };	Cube[7] = Camera * Vector3f{ -0.5f, -0.5f, -0.5f };	// Get cube data	Vector3f Deltas[8];	Vector3f Pos;	float32 rad_x, rad_y, rad_z;	CalcOctantAABB(Cube, Deltas, Pos, rad_x, rad_y, rad_z);	// Get the traversal order (front to back)	int32 Traversal[8];	GetOctreeOrder(rad_x, rad_y, rad_z, Traversal);	// Begin traversal	RenderOctNode(&tree->Tree, Screen, Traversal, Pos, Deltas, rad_x, rad_y, rad_z);}void DrawChildren(OctNode* Node, ScreenBuffer* Screen, int32* Traversal, Vector3f Pos, Vector3f Deltas[8], float32 rad_x,	float32 rad_y, float32 rad_z, int32 level){	level++;	rad_x /= 2.0f;	rad_y /= 2.0f;	rad_z /= 2.0f;	float32 temp_level = 1.0f / (float32)(1 << (level));	for (int i = 0; i < 8; ++i)	{		if (Node->Children[Traversal[i]] != nullptr)		{			RenderOctNode(Node->Children[Traversal[i]], Screen, Traversal, Pos + (Deltas[Traversal[i]] * temp_level), Deltas, 				rad_x, rad_y, rad_z, level);		}	}}void DrawChildrenInsideCam(OctNode* Node, ScreenBuffer* Screen, Vector3f Pos, Vector3f Deltas[8], int32 OldTraversal[8], float32 rad_x,	float32 rad_y, float32 rad_z, int32 level){	++level;	rad_x /= 2.0f;	rad_y /= 2.0f;	rad_z /= 2.0f;	float32 temp_level = 1.0f / (float32)(1 << (level));	for (int i = 0; i < 8; ++i)	{		if (Node->Children[OldTraversal[i]] != nullptr)		{			int32 Traversal[8];			GetOctreeOrder(rad_x, rad_y, rad_z, Traversal);			RenderOctNode(Node->Children[OldTraversal[i]], Screen, Traversal, Pos + (Deltas[OldTraversal[i]] * temp_level), Deltas,				rad_x, rad_y, rad_z, level);		}	}}void GetOctantScreenSize(ScreenBuffer* Screen, Vector3f Pos, float32 rad_x, float32 rad_y, float32 rad_z,	int32& MinX, int32& MinY, int32& MaxX, int32& MaxY){	Vector3f FrontFace = Pos;	Vector3f BackFace = Pos;	if (Pos.x > 0)	{		FrontFace.x += rad_x;		BackFace.x -= rad_x;	}	else	{		FrontFace.x -= rad_x;		BackFace.x += rad_x;	}	if (Pos.y > 0)	{		FrontFace.y += rad_y;		BackFace.y -= rad_y;	}	else	{		FrontFace.y -= rad_y;		BackFace.y += rad_y;	}	FrontFace.z -= rad_z;	FrontFace = ConvertFromNdcToScreen(FastPerspectiveTransform(Screen, FrontFace), Screen->Width, Screen->Height);	BackFace.z += rad_z;	BackFace = ConvertFromNdcToScreen(FastPerspectiveTransform(Screen, BackFace), Screen->Width, Screen->Height);	if (FrontFace.x < BackFace.x)	{		MinX = Round(FrontFace.x);		MaxX = Round(BackFace.x);	}	else	{		MinX = Round(BackFace.x);		MaxX = Round(FrontFace.x);	}	if (FrontFace.y < BackFace.y)	{		MinY = Round(FrontFace.y);		MaxY = Round(BackFace.y);	}	else	{		MinY = Round(BackFace.y);		MaxY = Round(FrontFace.y);	}}
I removed the unclipped traversal since I figured optimization could be done later and having 1 function to debug is much easier to do. I also noticed that when my octree is close to the edge, it appears to be traversed deeper which I guess makes sense since perspective makes objects on the side of the screen larger. Heres an example shot:

1Yrwfjq.png

The way the algo calcukates the screensize of a cube is to project its corners onto the screen that also form a screen space aabb around the projected cube. For rotated cubes, i just calculate the aabb of the cube and use its radiuses instead. This aabb calculation is done on the root and the radiuses are divided by 2 in object space for the children while keeping the center pos of the each children.

PARTNERS