Skip to main content
gamedev.net
🔒 Locked

SOAR nested spheres

Started by Funkymunky Nov 7, 2004 at 1:06 AM 12 replies 1k views
Original Post
Funkymunky
Funkymunky
Alright guys, I'm back fiddling with this SOAR thing. I seem to have gotten the tesselation algorithm down pat, but now I'm struggling with the actual meat and potatos of the thing. What happens is that you pre-build a nested tree of bounding spheres, so that you can then calculate a projected position from a vertex and see if it is active. What I'm wondering is, what size should these bounding radii be (how should i go about building the tree)? If I have written a function to check the visibility of a 3D Vertex with my Camera class, how do I check the projected position according to the bounding radii? Thanks in advance, all replies greatly appreciated.
Jan Wassenberg
Jan Wassenberg
Preprocessing is tricky. Here's the deal:
- each bounding sphere completely contains the spheres of its children
- go bottom up, process all nodes belonging to a level in the tree. radius = max for i in range(4) { distance to child C + C.radius) }
- this requires efficient access to the children. a 2d matrix is advisable. afterwards, you need to convert to the embedded quadtree layout via simultaneous (recursive) traversal of both representations.
- on "odd" levels, edge nodes don't have 4 children. you can either check for this explicitly, or treat interior nodes differently (faster; this is what I do).

Lindstrom released a second paper describing this process in some more detail ("Terrain Simplification Simplified"). Have you read that?


The "3d Vertex visibility" routine is used during refinement, to discard whole spheres that aren't visible. What do you want with "projected position according to the bounding radii"?
E8 17 00 42 CE DC D2 DC E4 EA C4 40 CA DA C2 D8 CC 40 CA D0 E8 40E0 CA CA 96 5B B0 16 50 D7 D4 02 B2 02 86 E2 CD 21 58 48 79 F2 C3
Funkymunky
Funkymunky
Thanks I'm now piecing through the lindstrom article.

Currently my engine works by just adding indices, it doesn't maintain a list of children and parents. Therefore your second tip is like alien language to me.

I guess my real confusion is summed up by Lindstrom: "...where E is the actual geometric error measured by the object space metric"

What is meant by the term error? And by "object space metric"?
Jan Wassenberg
Jan Wassenberg
"Level" refers to the embedded quadtree accessed during refinement. Now if you were to build the tree top-down and find a child with a large error (e.g. spike in the terrain), you will need to propagate that up to higher levels. (Each node's sphere must completely enclose all child spheres.) To avoid that inefficiency, you go bottom-up.


Error of a node means how far its Z-coordinate (height) is off the mark, when the node isn't actually split.

Child node @ expanded:
./@\.
*___*

now @ not expanded (midpoint of its parents' height)
./ \.
*_@_*

Error:
./@\...\ this is it!
*_@_*../

(who don't love ASCII-art? ;P)

Therefore, the error tells us how much benefit there is to including a certain point, instead of averaging its parents' height. It increases with 'rougher' terrain.
E8 17 00 42 CE DC D2 DC E4 EA C4 40 CA DA C2 D8 CC 40 CA D0 E8 40E0 CA CA 96 5B B0 16 50 D7 D4 02 B2 02 86 E2 CD 21 58 48 79 F2 C3
Funkymunky
Funkymunky
So then, the error of a triangle is the distance from it's apex to the midpoint of it's two other vertices?
Jan Wassenberg
Jan Wassenberg
Yes, it boils down to that :)
E8 17 00 42 CE DC D2 DC E4 EA C4 40 CA DA C2 D8 CC 40 CA D0 E8 40E0 CA CA 96 5B B0 16 50 D7 D4 02 B2 02 86 E2 CD 21 58 48 79 F2 C3
Funkymunky
Funkymunky
Alright, so it works like this then:

To determine if a node is visible, I need this prebuilt set of spheres, where each parent sphere contains the children spheres. When checking a node, I first take the point on it's sphere that is closest to the camera, then project by this error (the distance from apex to midpoint) further toward the camera. If this is visible, then proceed, otherwise cull/stop refining?
Jan Wassenberg
Jan Wassenberg
hmm, better hit the paper again :)
To determine if visible, you check if a node's sphere is within the view frustum. If completely outside, you stop refining that node and all its children.
After preprocessing, the only use for error is when geomorphing (to reduce visual impact of LOD changes).
E8 17 00 42 CE DC D2 DC E4 EA C4 40 CA DA C2 D8 CC 40 CA D0 E8 40E0 CA CA 96 5B B0 16 50 D7 D4 02 B2 02 86 E2 CD 21 58 48 79 F2 C3
Funkymunky
Funkymunky
Hmm. Alright, can you help me out with how to construct the set of spheres then? Honestly I piece through the pascucci article once or twice a day now, but I still don't really understand how to make the nested set. My landscape is full of cracks. I also didn't understand your pseudocode about "going bottom up" and whatnot.

"going bottom up." ha, sounds like what my engine is about to be doing...

any help?
Jan Wassenberg
Jan Wassenberg
I feel your pain, man - that was hard to get right. I'll gladly post (GPL-ed) source here, but I doubt it'll help by itself: it's old (therefore bad), and optimized (harder to decipher). You'll probably be better off repeating: read_paper; bang_head_against_wall until you understand what's going on, rather than just looking at code.

Anyways, in the hope it is useful:

#define _nu	97.78f	/* = xres / fov / tolerance *//* dmax = e*nu[0]+r, dmin = e*nu[1]+r */float nu[2] = { _nu, _nu * 2.f/3.f };/* * is VAR available? * set by lod_init() if GL_NV_vertex_array_range is advertised */static uint use_VAR;/* preprocessed terrain vertex */typedef struct{	int16 r;	/* radius enclosing all descendants */	int8 dz;	/* z offset from z midpoint of triangle base points */	u8 e;	/* error */}V;V *v;/* terrain vertex coords (packed into 8 bytes for easier copying) */typedef struct{	int16 x, y;	float z;}VP;VP vp[9];	/* coords of nodes 0-9 *//***************************************************************************** * preprocessing *****************************************************************************/static int init();static uint w;	/* w == 2^(depth/2) + 1 */uint depth;static uint v_entries;static const u8* h;/* stripped down version of V for preprocessing */typedef struct{	int16 r;	u8 e;}PP_V;static PP_V* pp_v;/* * calculate radius of a sphere about m enclosing c and c's children * radius = (distance(m, c) + c's radius) */static int xy_dist_sq = 1;	/* parent's xy distance ^2 to its children */static inline int radius(const uint m, const uint c){	const int dz = h[m]-h[c];	const int dist = ceil(sqrtf((float)(xy_dist_sq+dz*dz)));	return dist+pp_v[c].r;}#define MAX_E	(u8)max(abs(h[m] - (h[b[0]]+h[b[1]])/2),				  max(max(pp_v[c1].e, pp_v[c2].e), max(pp_v[c3].e, pp_v[c4].e)))#define MAX_R	(int16)max(max(radius(m,c1), radius(m,c2)),				  max(radius(m,c3), radius(m,c4)))/* * calculate z-error and radius for each point on the terrain * * algorithm: *   for each level, bottom up *     for each point in the current level: *       error = max(current_error, max error of a child node) *       radius = max d (d = distance to a child node + child's radius) * * process whole levels (= all points at a certain depth in the qtree) * at once, bottom up; this means each point is only processed once. * * this requires access to all 4 (quadtree) children, * so we need the data in matrix order. * points in a level are then separated by xstep/ystep units; * xstep = ystep = 2 for the first even level. * xstep / ystep double before each odd / even level. * * points on an even level lie on a regular grid; each point has 4 children. * odd levels have every 2nd row shifted ystep to the right; * edge / non-edge points have 2 / 4 children, respectively. * the level loop is unrolled once to handle even/odd levels separately; * the "child valid" tests in odd levels are eliminated by * special casing the edge points. * * each loop carries along the children and base points * (used to calculate error) for speed. */static void calc_e_r(){	/* per level: */	uint start = 1;			/* x/y coord of first point in a level */	uint odd_start = 2*w+4;	/* current odd level's first non-edge point */	uint xstep = 2, ystep;	/* x/y distance to next point in level */	/* counters */	uint x, y;	uint count = (w-1)/2;	/* # points per row / rows per level (even) */	/* current point */	uint m;					/* current point */	uint b[2];				/* base points of m's triangle */	uint c1, c2, c3, c4;	/* m's children */	/*	 * for each level:	 * note: loop body handles 1 even and 1 odd level;	 *   there are depth-1 levels, and the bottom (odd) level	 *   is skipped (its d and r values are 0), so loop (depth-2)/2 times	 */	for(uint i = (depth-2)/2; i > 0; i--)	{		ystep = xstep;		/*********************************************************************		 * even level		 * points are a regular grid; children are always valid		 *********************************************************************/		m = (w+1)*start;		b[0] = 0; b[1] = 2*m;		c1 = start;						/*   N   */		c2 = start*w; c3 = start*(w+2);	/* W   E */		c4 = start*(2*w+1);				/*   S   */		/* for each row: */		for(y = count; y > 0; y--)		{			/* for each point in row: */			for(x = count; x > 0; x--)			{				pp_v[m].e = MAX_E;				pp_v[m].r = MAX_R;				/* go to next point in row */				m += xstep;				b[x&1] += 2*xstep;	/* \/\/ "spider walk" */				c1 += xstep; c2 += xstep;	/* alternative: new c2 = old c3 */				c3 += xstep; c4 += xstep;			}			/* go to next row */			uint next_row_ofs = (xstep-1)*w+1;			m += next_row_ofs;			b[0] += next_row_ofs; b[1] += next_row_ofs;			b[y&1] += xstep*w; b[1-(y&1)] -= xstep*w;			c1 += next_row_ofs; c2 += next_row_ofs;	c3 += next_row_ofs;	c4 += next_row_ofs;		}		xstep += xstep;		start += start;		count >>= 1;		xy_dist_sq += xy_dist_sq;	/* children are diagonally distanced */		/* offset to the left/right child */		const uint cl = (+w-1)*xstep/4, cr = (+w+1)*xstep/4;		/*********************************************************************		 * odd edge		 * points are regularly spaced but have only 2 children		 * special cased to simplify the main odd loop below		 *********************************************************************/		{			/*             N          S           W           E         */			uint m[4] = {start, start+(w-1)*w, start*w, start*w+(w-1)};			for(x = count; x > 0; x--) /* do all 4 edges at once */			{				/* calculate error */				pp_v[m[0]].e = (u8)max(abs(h[m[0]] - (h[m[0]-ystep]+h[m[0]+ystep])/2), max(pp_v[m[0]+cl].e, pp_v[m[0]+cr].e));				pp_v[m[1]].e = (u8)max(abs(h[m[1]] - (h[m[1]-ystep]+h[m[1]+ystep])/2), max(pp_v[m[1]-cr].e, pp_v[m[1]-cl].e));				pp_v[m[2]].e = (u8)max(abs(h[m[2]] - (h[m[2]-ystep*w]+h[m[2]+ystep*w])/2), max(pp_v[m[2]-cl].e, pp_v[m[2]+cr].e));				pp_v[m[3]].e = (u8)max(abs(h[m[3]] - (h[m[3]-ystep*w]+h[m[3]+ystep*w])/2), max(pp_v[m[3]-cr].e, pp_v[m[3]+cl].e));				/*				 * calculate radius such that all descendants				 * are contained in the resulting sphere				 */				pp_v[m[0]].r = (short)max(radius(m[0],m[0]+cl), radius(m[0],m[0]+cr));				pp_v[m[1]].r = (short)max(radius(m[1],m[1]-cr), radius(m[1],m[1]-cl));				pp_v[m[2]].r = (short)max(radius(m[2],m[2]-cl), radius(m[2],m[2]+cr));				pp_v[m[3]].r = (short)max(radius(m[3],m[3]-cr), radius(m[3],m[3]+cl));				/* go to next point on all edges */				m[0] += xstep; m[1] += xstep; m[2] += xstep*w; m[3] += xstep*w;			}		}		/*********************************************************************		 * odd level (excluding edges)		 * every 2nd row is shifted ystep to the right; all children are valid		 *********************************************************************/		m = odd_start;		b[0] = m-ystep*w; b[1] = m+ystep*w;		c1 = m-cr; c2 = c1+ystep;	/* NW NE */		c3 = m+cl; c4 = c3+ystep;	/* SW SE */		/* for each row: */		for(y = 2*count-1; y > 0; y--)	/* N, S edges already done */		{			/*			 * for each point in row:			 * NOTE: all points on the highest level are on an edge;			 *       this loop is skipped by the x = ...; x > 0 statement			 */			for(x = count-(y&1); x > 0; x--) /* 1 point less every other row */			{				pp_v[m].e = MAX_E;				pp_v[m].r = MAX_R;				/* go to next point in row */				m += xstep;				b[0] += xstep; b[1] += xstep;				c1 += xstep; c2 += xstep; c3 += xstep; c4 += xstep;			}			/* go to next row */			uint next_row_ofs = (ystep-1)*w+1+ystep;			m += next_row_ofs;			uint tmp = b[1];			b[1] = b[0]+(xstep-1)*w+1+xstep;			b[0] = tmp-w+1;			c1 += next_row_ofs; c2 += next_row_ofs;	c3 += next_row_ofs; c4 += next_row_ofs;		}		xy_dist_sq += xy_dist_sq;	/* next level has 2x distance*/		odd_start += odd_start;	}}/* convert (row major) pp_v to (embedded quadtree) v */static void traverseR(uint i, uint j, uint ml, uint ma, uint mr, uint l){start:	const uint mm = (ml+mr) >> 1;	/* fill v[m] */	v[j].dz = (signed char)((int)h[mm] - (((int)h[ml]+(int)h[mr])/2));	v[j].e = pp_v[mm].e;	v[j].r = pp_v[mm].r;	/* recurse for left/right children */	if(--l)		/* last level? */	{			/* no - recurse */		int a = (i+i)+j, b = (i << 2)-11;		traverseR(j, ((a-10)&3)+b, ml, mm, ma, l);		/* TRE: traverseR(j, ((a-9)&3)+b, ma, mm, mr, l); */		i = j;		j = ((a-9)&3)+b;		ml = ma;		ma = mm;		goto start;	}}int lod_preproc(const uint width, u8* hmap){	int i;	w = width;	h = hmap;	/* make sure width == 2^(depth/2) + 1, depth >= 4 */	if(((w-1) & (w-2)) || w < 5)		return -1;	depth = 2*log2(w-1);	v_entries = (int)(w*w*4./3.);	/* ~33% wasted ghost nodes */	int x[] = {0, w-1, w-1, 0, w/2, 0, w/2, w-1, w/2};	int y[] = {0, 0, w-1, w-1, w/2, w/2, 0, w/2, w-1};	for(i = 0; i < 9; i++)	{		vp.x = (short)x; vp.y = (short)y;		vp.z = h[x+y*w];	}	res_free(v);	pp_v = (PP_V*)calloc(v_entries, sizeof(PP_V));	v = (V*)res_malloc(v_entries * sizeof(V));	if(!pp_v || !v)		return -1;	calc_e_r();	/*	 * convert (row major) pp_v to (interleaved quadtree) v	 *	 * start triangles:	 * +-+-+	 * |\|/|	 * +-+-+	 * |/|\|	 * +-+-+	 */	uint m[9];	/* row major layout indices for vp */	for(i = 0; i < 9; i++)		m = (uint)(vp.x+vp.y*w);	for(uint n = 0; n < 4; n++)	{		uint j = (n+1)%4, i = j+5;		traverseR(i, 21-3*n, m[4], m, m[n], depth-2);		traverseR(i, 21-3*j, m[j], m, m[4], depth-2);	}	free(pp_v);	init();	return 0;}
E8 17 00 42 CE DC D2 DC E4 EA C4 40 CA DA C2 D8 CC 40 CA D0 E8 40E0 CA CA 96 5B B0 16 50 D7 D4 02 B2 02 86 E2 CD 21 58 48 79 F2 C3
Funkymunky
Funkymunky
damn, thanks dude. Yeah that's a little tricky to read, but I appreciate the help. Guess I better get started bangin my head against the wall...gonna be a looong night. ;)

Thanks.
Jan Wassenberg
Jan Wassenberg
Glad to help; pay it forward :)
Good luck!
E8 17 00 42 CE DC D2 DC E4 EA C4 40 CA DA C2 D8 CC 40 CA D0 E8 40E0 CA CA 96 5B B0 16 50 D7 D4 02 B2 02 86 E2 CD 21 58 48 79 F2 C3
Funkymunky
Funkymunky
Hey actually, could you help me with one more thing? The stumbling block I'm having with the paper is some of the mathematic equation notation.

For example, on page 4, the authors introduce i and j, and then on page 5 they start using crazy symbols to represent relationships, like j round E/pitchfork M ---> i round E/pitchfork M j round E/pitchfork Csubi?

or Upside-down Capital A sub j round E/pitchfork Csubi

I'm hoping you don't advise me to buy some math textbook because I switched my major to English freshman year bro.


:
By the way, for anyone else who might stumble across this thread in research, the paper in question can be found at pascucci's site. (here). Lindstrom's /a ga-tech seem to have taken it off line.
Jan Wassenberg
Jan Wassenberg
Don't get hung up on the greek letters - mathematicians love to use those; there's no special meaning attached.
Check out http://www.ibiblio.org/koine/greek/lessons/alphabet.html , then hunt for their definitions in the article :)

Some terms you may not know without a math course:
__
\/ = "gradient" (think of it as n-dimensional derivative)

||vector|| = "norm" (in this case Euclidean, which just means length of vector)

HTH
E8 17 00 42 CE DC D2 DC E4 EA C4 40 CA DA C2 D8 CC 40 CA D0 E8 40E0 CA CA 96 5B B0 16 50 D7 D4 02 B2 02 86 E2 CD 21 58 48 79 F2 C3

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.