PDA

View Full Version : height field to sphere?

xoxos
05-05-2012, 06:21 PM
i haven't ventured further into 3d than the calculation of 3d points in the frustrum for wireframe graphics, so i'm not sure what i'm missing to answer this on my own.

accordingly, i understand the concept of projection (apart from cartographic references, projection is the introductory topic for this 2 hour movie on visualisation of higher dimensions.. modeled in pov-ray, where i have experienced the application of height fields to spheres :)
http://dimensions-math.org/

i've been mulling over exactly how one would apply a height field to a sphere, and i think i must have the basic idea wrong.

being aware that points towards the upper and lower edges of a 2d height field are applied to increasingly smaller diameters, what i am visualising is the generation of standard 2d noise image, then translating this to the spherical height field by using an increasingly smaller width of pixels towards the upper and lower edges, using a sinusoidal 'lemon' shaped region of the source height field.

to reword for clarity, the output 'product' height field is sourced from a region of a temporary 'source' height field that is shaped like a lemon, with the points tangent to the top and bottom. amplitude is scaled/reduced for samples towards the top and bottom.

well.. the obvious issue with this method is that if you are using a method of interpolation using more than the immediate samples (eg. the preferred bicubic interpolation for perlin noise) you are up a very complex creek (eg. as one would have to wrap points of interpolation, requiring having to perform stages of intermediary interpolation..)

i feel certain that the predominant method must be more sensible than what i am envisioning, which seems to be lemon shaped. :)

xoxos
05-05-2012, 06:27 PM
(kinda long but perhaps a good introductory link for this site)

waldronate
05-05-2012, 06:34 PM
Use a higher-dimensional noise (3D or 4D) to directly give you your height samples on the sphere (which can then be reprojected to a flat map using the projection of your choice). This technique also has no seams anywhere.

Another choice for working space is to use a square with the north and south poles at opposite corners. It isn't exactly perfect, but it's much simpler to manage if you're trying to paint onto the height field.

A popular choice is to use a set of height maps rather than a single height map. A basic cube map works well because the 6 sides can be done as individual height maps or they can be done with a single map (that loses a fair amount of space).

xoxos
05-05-2012, 06:41 PM
Use a higher-dimensional noise (3D or 4D) to directly give you your height samples on the sphere (which can then be reprojected to a flat map using the projection of your choice). This technique also has no seams anywhere.

! that's the proverbial ticket! :)

makes sense, really, sphere, 3 dimensions..

xoxos
05-06-2012, 02:42 PM
mr. waldronate -

i don't really want to get into this, because there is obviously a great discrepancy between our eruditions and experience, which cannot be translated in the course of a forum discussion, so no slight if you choose not to respond.

my perlin uses a base array of 256 so i can index with unsigned chars for faster bicubic interpolation.

2d requires five bicubic interpolation operations, 3d requires 21.

to create a bicubic 2048 * 1536 2d height field of 8 octaves takes my 1.6g processor about 8 seconds, which is going to take 4 times longer with 3d. in comparison, wilbur is practically instantaneous.

audio is a competitive field, so i'm fairly confident regarding the efficiency of my operations.. (my algo may have some slack in it, but i doubt a critical amount) so i see the difference as possibly due to..

using the graphics device for math, which i have no experience with yet, and may be the key factor
using a lower res/octave for editing, perhaps keeping an edit map with is applied to a higher octave render at output
(i doubt it, but possibly using a lower than screen image resolution for data)
(also doubt it, possibly using a faster interpolation technique as perhaps the artifacts aren't so obvious in 3d)

in five syllables or less, why are you awesome?

OT:
for those interested or have input that may result in a more useful product, i very much enjoy algorithmic generation, and i believe what i'm driving towards is ~a more/fully automatic world generator, with minimal parameterisation and climate, road and political mapping, none of which will be particularly refined as i'm more interested in the practice, still, it's always nice to have something that isn't completely worthless at the end.

waldronate
05-06-2012, 03:20 PM
Why am I so awesome? Practice!

Wilbur uses the basic Musgrave and Perlin code (well, slight variation, but not from a performance perspective). It stores the data as a floating-point surface and renders from there. Convenience of programming was always the important part. It's all C/C++ code, compiled with reasonable optimizations. Note that Wilbur always does a 3D noise solution rather than 2D.

(Assuming x86/x64): On any semi-modern processor, it may be faster to use native-sized variables rather than unsigned characters. Depending on your processor, floating-point multiplies may be faster than integer (but not a lot). Compiling with SSE2 (if available) may aso speed up float-based math a bit. Using OpenMP or other multi-threading library to share the work across all available cores will also help. Truncation float float to integer can eat a lot of time if you do float operations and aren't using SSE2. http://stackoverflow.com/questions/2550281/floating-point-vs-integer-calculations-on-modern-hardware has some good discussions on the subject.

My spiffy new i7-3770 calculates the 2048*1536 image (including generating displaying the lighted image) in under a second. Adjusting for number of cores, processor speed, architecture, and so on suggests that your code is in the ballpark of the Wilbur code speed.

If you want a less computationally expensive basis function that's reasonable, do an Internet search for "simplex noise".

xoxos
05-07-2012, 12:11 AM
Practice!

hehe, he's just kidding, folks. waldronate's secret is that he only uses Vim™ brand development tools.

thanks for the speed comparison. it's common to handle float to int with assembly in audio.. hosts used to include cpu meters making performance one of the most publicly criticised features (i remember metering someone's implementation and being able to discern the word length they were using for certain oscillator variables..)

expect i'll downsize my perlin array to 32^3. i was using 16 across for my lowest octave on the HF, looked okay. deliberating using floats ;)

Hai-Etlik
05-10-2012, 10:18 PM
hehe, he's just kidding, folks. waldronate's secret is that he only uses Vim™ brand development tools.

vi isn't a brand, it's a heinous cult that mocks the holy perfection that is EMACS.

xoxos
05-26-2012, 06:43 PM
documenting progress as such..

"equirectangular" projection commonly used for spherical height fields in ray tracing.

mapped to 4096 by 2048.. one octave takes my 1.6g about 11 seconds..
45127

proof of sphericality - imported to pov-ray, map_type 1
45128

8 octaves took 60-70 seconds. should i ever release this as an app, preinstallation requirements will include a bong (which i do not have) because there's no bloody way anyone's sticking around for it to finish otherwise.
45126

currently depending on manual editing to inhibit continents being a bunch of windy lines. considering a voronoi type process to define plates. i'd like to try an evolutionary algorithm that rotates the plates and/or produces aggregation or what have you. deliberating how involved i want to get considering the research.. fishing for a simpler solution (which could resolve to manual editing..)

Hai-Etlik
05-27-2012, 02:04 AM
currently depending on manual editing to inhibit continents being a bunch of windy lines. considering a voronoi type process to define plates. i'd like to try an evolutionary algorithm that rotates the plates and/or produces aggregation or what have you. deliberating how involved i want to get considering the research.. fishing for a simpler solution (which could resolve to manual editing..)

Yeah I did some digging into voronoi algorithms on the surface of a sphere too, but didn't get very far. The only implementation I recall finding was part of a pack of tools written in FORTRAN.

xoxos
05-27-2012, 03:09 PM
i don't see that as the challenging part.. my awareness of voronoi alg is cursory.. my conception was that each pixel is checked against n number of points and the distance relative to them is used (i assume taking the ratio of the two closest points would suffice). i'm sure several methods would work for distributing a desired number of points fairly evenly (eg. even equidistance along latitude with longitude randomised on the equirectangular map would still appear fairly random and could take some elementary improvements).

using the outcome to reduce the height field along edges would break up ridges, but going to the bother of improving the algorithmic model at all versus manual editing would invite continuing into developing the height field along continental seams.. and the amount of research there doesn't interest me :p

Hai-Etlik
05-27-2012, 05:56 PM
i don't see that as the challenging part.. my awareness of voronoi alg is cursory.. my conception was that each pixel is checked against n number of points and the distance relative to them is used (i assume taking the ratio of the two closest points would suffice). i'm sure several methods would work for distributing a desired number of points fairly evenly (eg. even equidistance along latitude with longitude randomised on the equirectangular map would still appear fairly random and could take some elementary improvements).

using the outcome to reduce the height field along edges would break up ridges, but going to the bother of improving the algorithmic model at all versus manual editing would invite continuing into developing the height field along continental seams.. and the amount of research there doesn't interest me :p

Ah yes, it would be a lot easier with spherical raster data, all you need is a spherical distance function. I was trying to find a vector algorithm which is a lot more complicated.

xoxos
05-29-2012, 12:15 PM
got around to watching a bunch of tectonic animations yesterday. feeling more deterred atm given the complexity of the approach and the diveristy of theories on tectonic formation. will let it sit for a few days in case some fancy filtering method occurs to me, otherwise i'll proceed with manual editing..

xoxos
06-09-2012, 11:52 PM
hehe.. this topic was resumed in another thread, but i thought i'd better continue it here.

discussion: me whining about my interpolation technique taking ages to compute on my non-top modern device. simplified interpolation was mentioned. it took about 3 minutes to make the modifications and try the alternative method.. documenting this to save other developers those minutes....

here's one octave rendered with fast and slow interpolation methods
45505

8 octaves (first two octaves are unridged, subsequent are ridged)
45506

..and just for fun, here's the fast interpolation without shaping the fractional component, as i've seen it described
45507

pretty pictures :) any more serious developers are advised to investigate the simplex noise method.

xoxos
06-10-2012, 11:34 AM
solved it!

adding a timer and a preview mode that renders only the pertinent octaves at a lower resolution. this should make it under a second even on my system say at 8x8, so that the globe can be 'spun' with the mouse.

thanks again to waldronate, i believe you'd mentioned a partial render and i'd noticed that wilbur uses a timer (still very new at this kind of task).

xoxos
06-14-2012, 10:15 PM
....i didn't want to do this, but it looks like i need to in order to move forward.

i'm going to have to ask a win32 SDK question....

only had one more feature to add before posting for early feedback, should have taken 5 minutes..

alright - my app has a main window. a dialog is selected from the menu to set height field params. i wanted to create a second dialog that also opens from the menu to set params associated with water. i haven't created a windows app with mor ethan one ancillary dialog before.

despite providing a unique name for *every* variable associated with the 2nd dialog, when it opens it displays the same gui as the first dialog. i can't seem to discretise it, even by going to silly lengths to provide a different name for everything.

certainly, i understand it less now than i did an hour ago (...)

so.... perhaps someone can guess where i've erred from that. otherwise, here's the horrible-to-pick-through code... as you'll observe, every hwnd et c. has it's own silly name... i've also tried using different #'s for the WNDCLASSEX wwc = {0}; statement to no avail. it compiles, it just shows the same panel on both dialogs.

/////////////////////////////////////////////////////////////////
//////////////// HEIGHT FIELD DIALOG
/////////////////////////////////////////////////////////////////

LRESULT CALLBACK HFDlgProc( HWND hdlg, UINT msg, WPARAM wParam, LPARAM lParam ) {
hhfdlg = hdlg;
HDC hdc;
PAINTSTRUCT ps;
HFONT hfont;

INITCOMMONCONTROLSEX InitCtrlEx; // for progress bar
InitCtrlEx.dwSize = sizeof(INITCOMMONCONTROLSEX);
InitCtrlEx.dwICC = ICC_PROGRESS_CLASS;
InitCommonControlsEx(&InitCtrlEx);

switch(msg) {
//DELETED DOESN'T MATTER
}
return (DefWindowProc(hdlg, msg, wParam, lParam));
}

void RegisterHFDlgClass(HWND hwnd) {
WNDCLASSEX wc = {0};
wc.cbSize = sizeof(WNDCLASSEX);
wc.lpfnWndProc = (WNDPROC) HFDlgProc;
wc.hInstance = ghInstance;
wc.hbrBackground = GetSysColorBrush(COLOR_3DFACE);
wc.lpszClassName = TEXT("DialogClass");
RegisterClassEx(&wc);
}

void CreateHFDlgBox(HWND hwnd) {
CreateWindowEx(WS_EX_DLGMODALFRAME | WS_EX_TOPMOST, TEXT("DialogClass"), TEXT("Height Field"),
WS_VISIBLE | WS_SYSMENU | WS_CAPTION , 0, 21, 192, 285,
NULL, NULL, ghInstance, NULL);
}

/////////////////////////////////////////////////////////////////
//////////////// WATER DIALOG
/////////////////////////////////////////////////////////////////

LRESULT CALLBACK WaterDlgProc( HWND hwdlg, UINT msg, WPARAM wParam, LPARAM lParam ) {
HDC hdc;
PAINTSTRUCT ps;
HFONT hfont;

switch(msg) {
//DELETED DOESN'T MATTER
}

return (DefWindowProc(hwdlg, msg, wParam, lParam));
}

void RegisterWaterDlgClass(HWND hwwnd) {
WNDCLASSEX wwc = {0};
wwc.cbSize = sizeof(WNDCLASSEX);
wwc.lpfnWndProc = (WNDPROC) WaterDlgProc;
wwc.hInstance = whInstance;
wwc.hbrBackground = GetSysColorBrush(COLOR_3DFACE);
wwc.lpszClassName = TEXT("DialogClass");
RegisterClassEx(&wwc);
}

void CreateWaterDlgBox(HWND hwwnd) {
CreateWindowEx(WS_EX_DLGMODALFRAME | WS_EX_TOPMOST, TEXT("DialogClass"), TEXT("Water"),
WS_VISIBLE | WS_SYSMENU | WS_CAPTION , 0, 306, 192, 285,
NULL, NULL, whInstance, NULL);
}

waldronate
06-15-2012, 01:24 AM
Have you considered using DialogBox() or CreateDialog() to create your dialogs? That way, you can pass in the dialog resource ID as the second parameter. It's been a fair few years since I've done raw Windows programming in straight C, so I may be remembering it incorrectly, but you'll definitely need some way to specify that resource ID that you created in your .rc file.

xoxos
06-15-2012, 01:54 AM
i don't use .rc files. the method i use is the only one i've found sufficiently documented. i own petzold but find 'programming windows' too windy and disparate to function as a reference, i simply cannot recall the contents of all 1200+ pages at once. my perception is that the method of the author is not intended to actually convey an understanding of the material either.

i resent that all win32 instructive material starts off building dialogs without using .rc and then switches to using them without fully documenting how to do things in the initial manner. borland fclt doesn't build them for you so i'd be at a greater loss attempting to use them.

it does seem to me that i've eliminated every variable as a discretisor, so i will have to address this at a greater scope (or simply aggregate all my params on one panel with a scroll bar).

waldronate
06-15-2012, 10:47 PM
If you're not using .rc files, how are you getting your child windows created? Issuing a CreateWindow() call for each one? Painful...

I think that the window class name needs to be unique acording to window type. If you're using the same class name for two different windows, then you'll get the first (or maybe the last) on registered. So instead of creating a "DialogClass" class, create a "WaterDlgClass" and "HFDlgClass". The window class name is associated with your window procedure in RegisterClassEx(), so using the same class name will get you only the same window procedure (if that helps).

In your example program you're setting a TOPMOST attribute for your pseudodialog, which makes it appear on top of all other windows in the system. This behavior is a little disturbing...

xoxos
06-16-2012, 02:42 AM
the intent was to keep it on top of the main window. the hf dialog creates its own entry on the taskbar, so it's not providing the conventional functionality i'd intended. i'll fish some more.

! well i'll be (i'll never run out of ways to feign surprise when presented with more information about how this sdk is intended to function..) i had presumed the string "DialogClass" registered it as such, in the same manner as "button", but you're right! it can indeed be modified. doing so on the water class resulted in the dialog disappearing.. so that's something else i can fix, but some other night)32wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww wwwwwwww32

(kitten)

yes on CreateWindow for each control. it's been fun using a minimal compiler (while simultaneously being a stubborn 'purist'). the internet is starting to have the referential mass required to actually support it. only took a decade :)

once again you have taken time to provide assistance i would not have been likely to receive otherwise. anytime you want those vst licenses... :p thank you!

Redrobes
06-16-2012, 08:22 AM
If you just want to keep it on top of the main window then you can use the SetWindowPos() func and put in the flags to set up the Z order so that its higher than the main window without being topmost. You can use topmost but they bug the hell out of me when using a dialog app. But sometimes they can be useful.

An RC file is a giant PITA because the format for them is very odd and there is no default editor with the free VC that you can download. So I tend not to use a visual editor for them and do it by text. The only downside to that is you have to keep track of the numbers and also drop down combo box default text items is done in hex... WTF.... anyway thats MS for you.

But all you do is take a valid RC file and compile it with the RCCompiler to a .res file and then link it just like compiling C to obj file and linking. Then within the main app you can create the dialog by passing in a value for the ID. Usually thats defined as an IDD_DialogWhatever in the resource.h file.

You should also read about the DDX or the dialog data exchange because that makes life easier passing values in and out of the dialog items. By setting up a few standard macros it will patch the windows message to a function callback and also manage to update variables set for the dialog item using the UpdateData( TRUE/FALSE ) calls.

Dialogs come in Modal and Modeless. Modal ones keep the user locked to it until they dismiss the dialog with the OK or Cancel button/widgets but a modeless one sticks around and you can carry one with the other user interface elements or other dialogs without dismissing it. Modeless ones are just a little harder to code for.

My advice is to program some easy stuff first and get used to the principles before trying to code up topmost modeless dialogs without using an RC file and by creating all the UI elements by hand and patching all the windows messages by hand. Its the super super long winded and hard method to use despite it being the more pure form of coding.

Given the direction you want to head to for your coding, you might even be better off looking into wxWidgets for your dialogs and not using MS style at all. a) its more like what your doing with no RC file and b) its cross platform so you can take the apps to unix, linux, Mac etc and they should compile a version for them as well.

xoxos
06-16-2012, 01:05 PM
If you just want to keep it on top of the main window then you can use the SetWindowPos() func and put in the flags to set up the Z order so that its higher than the main window without being topmost. You can use topmost but they bug the hell out of me when using a dialog app. But sometimes they can be useful.

choice tip.. i haven't seen that mentioned before and something you'd only intuit after having been round the course a few times.

i used vc++e for a while, so i'm familiar with resource files. imo it's the principle of a 5 meg compiler install being as effective as the microsoft install's analogue to the urban sprawl of phoenix or greater los angeles. identical audio routines often perform faster in fclt than vce (really!), which otherwise has nothing to offer me except 'kid gloves'.

having accumulated most of the commands to create and use standard controls in the .cpp file, i'm ~over the hump and things are generally easier now.

waldronate
06-16-2012, 06:44 PM
The best way to keep dialogs on top of the main window is to make the main window the parent window of the dialog. That way there won't be any confusion about Z ordering (child windows are on top of the parent and, if modeless, can swap Z order back and forth as the user clicks on them).

http://msdn.microsoft.com/en-us/library/windows/desktop/ms644994(v=vs.85).aspx is an excellent discussion on dialog boxes in Windows, including building dialog templates directly in memory without having to use a resource compiler (.rc) file.

xoxos
06-17-2012, 11:45 PM
The best way to keep dialogs on top of the main window is to make the main window the parent window of the dialog.

done. past the trauma of first app with dialogs (and learned what topmost means explicitly!)

added the updated app in itw thread, and now it's time for me to dig into procedural territory (ha).

..question (...)

obviously using a hacked bitblt code to display, (which i presume means to everyone that i'm using a pointer to write to the image array) and i've noticed that my RGB has to be written BGR... i was quite puzzled when my water was orange..

is this correct, or am i, as i suspect, writing one byte off? i'm sure i'll be able to adjust this when i've added the routine to export the fullsize bitmap and examine the top left and bottom right pixels...

as said, copied from someone who has a deeper understanding of what they were doing..

void deinit_framebuf(void) {
SelectObject(pDC,old);
DeleteDC(pDC);
DeleteObject(framebmp);
}

void init_framebuf(void) {
HDC hdc;
BITMAPINFO bitmapinfo;
hdc = CreateCompatibleDC(NULL);
framebmp = CreateDIBSection(hdc, &bitmapinfo, DIB_RGB_COLORS, (void**)&framebuf, 0, 0);
pDC = CreateCompatibleDC(NULL);
old = (HBITMAP)SelectObject(pDC, framebmp);
DeleteDC(hdc);
}

for (y = 0; y < 512; y++) {
z = y << 10;
for (x = 0; x < 1024; x++) {
*(framebuf + z + x) = RGB(blah);
} }

waldronate
06-18-2012, 03:49 AM
Windows does indeed do BGR as the default byte ordering. If you're using the RGB(), GetRValue(), GetGValue(), and GetBValue() macros then it's a non-issue from a programming standpoint. If you care about alpha, there are analogous macros for working with RGBA and alpha values (I think they were defined in the DirectX SDK). Alpha is usually defined as BGRA pixels, but some accelerators might use ABRG or other format; sticking with the DIB sections will ensure BGRA, though.

Depending on the processor, it may or may not be faster to make an array of pointers to the first pixel of each line and then address the line as framebuf[y][x]. For block clears, consider doing a 32-bit memset operation instead of pixel-by-pixel activities. If you know your instruction set, you can get even more performance by using MMX, SSE, or AVX instructions. If you're looking at that level of optimization, though, you probably ought to switch algorithms...

xoxos
06-18-2012, 07:34 PM
it's nice to know it's not me.. i'm used to muddling through such things (eg. the standard biquad reference for audio, the rbj cookbook inverts signs on a set of coefficients) as there are a lower percentage of people in audio willing to assist others. it's refreshing to have someone say, "this is the right format.."

..it could be a few more years before i become concerned with the other things you mentioned :lol: i think i have PTSD from the windows sdk and i own the hardcover..

Redrobes
06-18-2012, 07:48 PM
Yeah that looks about right. Dont forget about that SetDIBits call I said about in another post or thread some time back. It can update the whole kaboodle in one call and its optimized by windows to do that job.

http://msdn.microsoft.com/en-us/library/dd162973%28v=vs.85%29.aspx

but if its working ok with what you have then its not too bad.

xoxos
06-19-2012, 01:06 PM
i'm currently using BitBlt. it seems quite fast to me.. iirc my preview mode is still in the order of 6 million 2nd order interpolations and i'm getting ~2-4 frames per second on my lappy.. the app is in this thread - http://www.cartographersguild.com/showthread.php?19058-itw-spherical-mapping-software

thanks for the reminder... i admit to being a ~BASIC linear, inline coder.. very little use for structs and classes in 1 dimension so i haven't had much practical experience with many OO procedures :)

procedural terrain, climate, rivers et c. are next (so still playing catch up) then national regions, cities and roads.. (do not anticipate quality) which should stretch my legs some.

waldronate
06-19-2012, 11:45 PM
Procedural Terrain is easy. Good-looking procedural terrain is fairly easy. Physically plausible procedural terrain is hard.

Climate is easy, basically being a lookup into a table by seasonal rainfall and temperature. Moisture transport is hard. Heat transport is harder. Moisture transfer and heat transfer are interdependent, which makes them harder.

Rivers are straightforward: liquid water flows downhill. Getting the water uphill is hard (it's dependent on both moisture transport and heat transport).

xoxos
06-20-2012, 02:15 AM
TY :) i expect that if i complete the course i'll report the same. in physical modeling i am not a stickler for perfection.. too tedious. one of the most enjoyable self-relevant functions is the amount of correlation between reality and what can be produced by simple (sometimes 'ideal') methods. i expect you also got most of the enjoyment out of wilbur implementing each new function and gauging the results.

i like to be useful, but i'm not particularly ambitious about being "what people use". if public utility wasn't a part of it i'd spend all day outside.

having spent a decade emulating specific, mercurial items, emulation at a more encompassing scale should broaden my procedural thinking.. but given meagre accreditation (while i certainly have received enough praise for synthesizers, i am quite aware of where i am not qualified to claim accuracy as i do not have eg. academic funding requiring authoritative correctness.. which is most fortunate because this ultimately limits me to my own discretion) i know there is as much folly at either/any scale and am consigned to enjoy the process rather than sweat it (lol and the occasional, inevitable extricative whinging directed at the precedent..)

:p